集合的Fail-Fast和Fail-Safe

集合的Fail-Fast和Fail-Safe

13 2019-05-22 18:05:06

## 背景
设想一个场景，我们需要将一个集合中满足条件的元素删除：
客户端提交了一个Array类型的数据，经过Spring框架的转换我们接收到的是ArrayList，其中某些数据在校验后不合法，需要去除，仅保留校验通过的数据。
这时候，我们通常有两种方案：
1. 遍历，并将不合法数据删除
2. 遍历，将合法数据保存在另一个集合中

假设在考虑不同集合增删元素的效率，实现复杂度，以及不合法元素所占比例后（如果绝大多数是合法数据，那么方案2明显效率偏低），我们决定使用遍历删除的方案。
这时候我们都会想到这个经典问题——如何在遍历List时删除其中元素。

很明显，我们都知道这样是错的：
```java
	// 例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);
		}
	}
```

常规做法是使用迭代器循环：
```java
	// 例3. 这个在单线程环境下正常
	Iterator<Item> itr = inputList.iterator();
	while (itr.hasNext()) {
		Item i = itr.next();
		if (!valid(i)) {
			itr.remove();
		}
	}
```

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

问题的本质是什么？是不能在遍历的同时修改集合的结构，这很危险。
那么是谁又是如何检测遍历过程中结构变化的呢？

## Fail-Fast
异常根源：
```java
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变量的值是否在遍历过程中被修改**。
```java
	final void checkForComodification() {
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();
	}
```

modCount会在ArrayList结构变化时被修改，比如add、remove、clear等方法。
而Java的foreach循环底层被转化为迭代器循环，即例1将展开为：
```java
	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. 解锁。

```java
	// 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可以处理遍历删除的问题，但是需要额外的复制数据的操作，只适合读操作远多于写操作的场景。

## 对比
|   | Fail-Fast | Fail-Safe |
| ------------ | ------------ | ------------ |
| 抛出ConcurrentModificationException | Y | N |
| 复制数据 | N | Y |
| 额外空间 | N | Y |
| 例子 | HashMap,Vector,ArrayList,HashSet | CopyOnWriteArrayList,ConcurrentHashMap |

## 参考资料
[java中fail-fast 和 fail-safe的区别 - ch717828的专栏 - CSDN博客](https://blog.csdn.net/ch717828/article/details/46892051)