集合中的Fail-Fast/Fail-Safe

不念不忘少年蓝@ 2023-07-10 08:23 16阅读 0赞

## 背景 ##

设想一个场景，我们需要将一个集合中满足条件的元素删除：

客户端提交了一个Array类型的数据，经过Spring框架的转换我们接收到的是ArrayList，其中某些数据在校验后不合法，需要去除，仅保留校验通过的数据。

这时候，我们通常有两种方案：

1.  遍历，并将不合法数据删除
2.  遍历，将合法数据保存在另一个集合中

假设在考虑不同集合增删元素的效率，实现复杂度，以及不合法元素所占比例后（如果绝大多数是合法数据，那么方案2明显效率偏低），我们决定使用遍历删除的方案。

这时候我们都会想到这个经典问题——如何在遍历List时删除其中元素。

很明显，我们都知道这样是错的：

// 例1. 这是错的，会抛出ConcurrentModificationException
    	for (Item i : inputList) {
    		if (!valid(i)) {
    			inputList.remove(i);
    		}
    	}
    	
    	// 例2. 或者这个，虽然不会报错，但是结果很可能不正确，因为遍历时跳过了某些元素
    	for (int i = 0; i < inputList.size(); i++) {
    		if (!valid(inputList.get(i))) {
    			inputList.remove(i);
    		}
    	}

常规做法是使用迭代器循环：

// 例3. 这个在单线程环境下正常
    	Iterator<Item> itr = inputList.iterator();
    	while (itr.hasNext()) {
    		Item i = itr.next();
    		if (!valid(i)) {
    			itr.remove();
    		}
    	}

但是，即使使用迭代器，在多线程环境中多个线程同时修改集合结构，仍然有可能会抛出`ConcurrentModificationException`。

**问题的本质是什么？是不能在遍历的同时修改集合的结构，这很危险**。

那么是谁又是如何检测遍历过程中结构变化的呢？

## Fail-Fast ##

异常根源：

Exception in thread "main" java.util.ConcurrentModificationException
    	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)	// 这里抛的异常
    	at java.util.ArrayList$Itr.next(ArrayList.java:851)

这个异常是ArrayList的内部类`Itr`抛出的，Itr实现了`Iterator`接口。

在生成迭代器时，迭代器记录了ArrayList此时的`modCount`变量值；在迭代器的迭代过程中，也就是每次调用`next()`方法，都会调用`checkForComodification`判断**modCount变量的值是否在遍历过程中被修改**。

final void checkForComodification() {
    		if (modCount != expectedModCount)
    			throw new ConcurrentModificationException();
    	}

modCount会在ArrayList结构变化时被修改，比如add、remove、clear等方法。

而Java的foreach循环底层被转化为迭代器循环，即例1将展开为：

Item i;
        for(Iterator<Item> iterator = inputList.iterator(); iterator.hasNext();) {
            i = iterator.next();
    		if (!valid(i))
    			inputList.remove(i)
    	}

看上去跟例3中迭代器循环差不多，但是这里调用的是**ArrayList的remove方法**，例3中调用的**迭代器的remove方法**。没错，问题就在这里。

迭代器的remove方法并不会修改modCount，而ArrayList的remove方法会修改modCount，因此使用迭代器在迭代遍历时删除是正常的。 但是，多线程环境下，一旦其他线程的操作引起modCount变化，仍然会导致迭代器抛出异常。

这种检查modCount的迭代器叫做Fail-Fast迭代器，在ArrayList类的注释中有写到：

> Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification

简而言之，Fail-Fast机制只能用作bug判断，并不是一个强保证。也好理解，其实多线程环境下也不是一定会触发抛ConcurrentModificationException异常的条件。

那如果确实有这样多线程同时修改与遍历的应用场景，应该如何操作呢？

1.  读写均加锁，比如使用`Collections.SynchronizedList`
2.  使用Fail-Safe集合

## Fail-Safe ##

Fail-Safe类型的集合，比如`CopyOnWriteArrayList`，顾名思义可以边读边写。

CopyOnWriteArrayList在迭代遍历的过程中不检查modCount，因为根本没有modCount。

任何对结构或内容的修改，过程都是：

1.  加锁保证线程安全
2.  复制底层数组，保证不影响读线程
3.  写入
4.  将底层数组回写覆盖原数组
5.  解锁。

// CopyOnWriteArrayList的add方法
        public boolean add(E e) {
    		// 加锁
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Object[] elements = getArray();
                int len = elements.length;
    			// 复制
                Object[] newElements = Arrays.copyOf(elements, len + 1);
    			// 修改
                newElements[len] = e;
    			// 回写
                setArray(newElements);
                return true;
            } finally {
    			// 解锁
                lock.unlock();
            }
        }

虽然CopyOnWriteArrayList可以处理遍历删除的问题，但是需要额外的复制数据的操作，只适合读操作远多于写操作的场景。

## 对比 ##

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>Fail-Fast</th> 
   <th>Fail-Safe</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>抛出ConcurrentModificationException</td> 
   <td>Y</td> 
   <td>N</td> 
  </tr> 
  <tr> 
   <td>复制数据</td> 
   <td>N</td> 
   <td>Y</td> 
  </tr> 
  <tr> 
   <td>额外空间</td> 
   <td>N</td> 
   <td>Y</td> 
  </tr> 
  <tr> 
   <td>例子</td> 
   <td>HashMap,Vector,ArrayList,HashSet</td> 
   <td>CopyOnWriteArrayList,ConcurrentHashMap</td> 
  </tr> 
 </tbody> 
</table>