迭代器的快速失败行为应该只用于检测错误
什么是fail-fast机制
原文
The iterators returned by this class’s {@link #iterator() iterator} and {@link #listIterator(int) listIterator} methods are fail-fast if the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own {@link ListIterator#remove() remove} or {@link ListIterator#add(Object) add} methods, the iterator will throw a {@link ConcurrentModificationException}. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
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 iterators throw {@code ConcurrentModificationException} on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
翻译
此类的 iterator() 和 listIterator(int) 方法返回的迭代器是快速失败的。如果在迭代器创建后的任何时间，列表的结构被修改，除了通过迭代器自己的 ListIterator#remove() 或 ListIterator#add(Object) 方法，迭代器将抛出一个 ConcurrentModificationException。因此，在面对并发修改时，迭代器会快速而干净地失败，而不是在未来不确定的时间冒任意的、不确定的行为的风险。
注意，迭代器的快速失败行为不能得到保证，因为它，一般来说，在非同步并发修改的情况下，不可能做出任何硬性保证。快速失败的迭代器在尽最大努力的基础上抛出 ConcurrentModificationException。 因此，编写一个依赖于这个异常的程序是错误的：迭代器的快速失败行为应该只用于检测错误。
举例
fail-fast 机制是集合世界中比较常见的错误检测机制，通常出现在遍历集合元素 的过程中 。下面通过校园生活中的一个例子来体会 fail-fast 机制。
上课前，班长开始点名。刚点到一半，这时从教室外三三两两进来若干同学，同学们起哄点错了！班长重新开始点名，点到中途，又出去几位同学，同学们又起哄说点错了，班长又需要重新遍历，这就是 fail-fast 机制。它是一种对集合(班级)遍历操作时的错误检测机制，在遍历中途出现意料之外的修改时，通过 unchecked 异常暴力地反馈出来。这种机制经常出现在多线程环境下，当前线程会维护一个计数比较器，即 expectedModCount，记录已经修改的次数。在进入遍历前，会把实时修改次数 modCount 赋值给 expectedModCount，如果这两个数据不相等，则抛出异常。java.util 下的所有集合类都是 fail-fast，而 concurrent 包中的集合类都是 fail-safe。与 fail-fast 不同， fail-safe 对于刚才点名被频繁打断的情形，相当于班长直接拿出手机快速照相，然后根据照片点名，不再关心同学们的进进出出。
什么时候会出现fail-fast？
在以下两种情况下会导致 fail-fast，抛出 ConcurrentModificationException
- 单线程环境
- 遍历一个集合过程中，集合结构被修改。注意，listIterator.remove() 方法修改集合结构不会抛出这个异常。
- 多线程环境
- 当一个线程遍历集合过程中，而另一个线程对集合结构进行了修改。
单线程
package com.czff.study.knowledge.collection;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* @author 疾风劲草
* @date 2022/11/30 20:13
* @description
*/
public class SingletonTreadFailFast {
public static void main(String[] args) {
try {
// 测试迭代器的remove方法修改集合结构会不会触发checkForComodification异常
itrRemoveTest();
System.out.println("----分割线----");
// 测试集合的remove方法修改集合结构会不会触发checkForComodification异常
listRemoveTest();
} catch (Exception e) {
e.printStackTrace();
}
}
private static void listRemoveTest() {
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
for (String temp : list) {
System.out.println(temp);
list.remove(temp);
}
//foreach循环等效于迭代器
/*Iterator<String> iterator=list.iterator();
while(iterator.hasNext()){
list.remove(iterator.next());
}*/
}
private static void itrRemoveTest() {
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
iterator.remove();
}
}
}
// 结果：
// 1
// 2
// 3
// ----分割线----
// 1
// java.util.ConcurrentModificationException
// at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
// at java.util.ArrayList$Itr.next(ArrayList.java:859)
// at com.czff.study.knowledge.collection.SingletonTreadFailFast.listRemoveTest(SingletonTreadFailFast.java:31)
// at com.czff.study.knowledge.collection.SingletonTreadFailFast.main(SingletonTreadFailFast.java:19)
从结果中可以看到迭代器 itr 的 remove 操作并没有出现 ConcurrentModificationException 异常。而集合的 remove 操作则产生了异常。
foreach循环为什么等效于迭代器？
public class FailFast {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
for (String temp : list) {
list.remove(temp);
}
}
}
- FailFast.class 文件反编译后的文件
public class FailFast {
public FailFast() {
}
public static void main(String[] args) {
List<String> list = new ArrayList();
list.add("1");
list.add("2");
list.add("3");
Iterator var2 = list.iterator(); // 迭代器
while(var2.hasNext()) {
String temp = (String)var2.next();
list.remove(temp);
}
}
}
- FailFast.class 可阅读的字节码指令文件
0 new #2 <java/util/ArrayList>
3 dup
4 invokespecial #3 <java/util/ArrayList.<init>>
7 astore_1
8 aload_1
9 ldc #4 <1>
11 invokeinterface #5 <java/util/List.add> count 2
16 pop
17 aload_1
18 ldc #6 <2>
20 invokeinterface #5 <java/util/List.add> count 2
25 pop
26 aload_1
27 ldc #7 <3>
29 invokeinterface #5 <java/util/List.add> count 2
34 pop
35 aload_1
36 invokeinterface #8 <java/util/List.iterator> count 1 // 迭代器
41 astore_2
42 aload_2
43 invokeinterface #9 <java/util/Iterator.hasNext> count 1
48 ifeq 72 (+24)
51 aload_2
52 invokeinterface #10 <java/util/Iterator.next> count 1
57 checkcast #11 <java/lang/String>
60 astore_3
61 aload_1
62 aload_3
63 invokeinterface #12 <java/util/List.remove> count 2
68 pop
69 goto 42 (-27)
72 return
多线程
/**
* @author 疾风劲草
* @date 2022/11/30 20:13
* @description
*/
public class MultiTreadFailFast {
private static List<String> list = new ArrayList<>();
/**
* 多线程情况测试
*/
public static void main(String[] args) {
list.add("1");
list.add("2");
list.add("3");
// 同时启动两个线程对list进行操作！
new ErgodicThread().start();
new ModifyThread().start();
}
/**
* 遍历集合的线程
*/
private static class ErgodicThread extends Thread {
@Override
public void run() {
int i = 0;
while (i < 10) {
printAll();
i++;
}
}
}
/**
* 修改集合的线程
*/
private static class ModifyThread extends Thread {
@Override
public void run() {
list.add("5");
}
}
/**
* 遍历集合
*/
private static void printAll() {
Iterator iter = list.iterator();
while (iter.hasNext()) {
System.out.print(iter.next() + ", ");
}
System.out.println();
}
}
// 结果：
// 1, 2, 3,
// 1, 2, 3,
// 1, 2, 3,
// 1, 2, 3,
// 1, 2, 3,
// 1, 2, Exception in thread "Thread-0" java.util.ConcurrentModificationException
// at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
// at java.util.ArrayList$Itr.next(ArrayList.java:859)
// at com.czff.study.knowledge.collection.failfast.MultiTreadFailFast.printAll(MultiTreadFailFast.java:57)
// at com.czff.study.knowledge.collection.failfast.MultiTreadFailFast.access$200(MultiTreadFailFast.java:12)
// at com.czff.study.knowledge.collection.failfast.MultiTreadFailFast$ErgodicThread.run(MultiTreadFailFast.java:35)
从结果中可以看出当一个线程遍历集合，而另一个线程对这个集合的结构进行了修改，确实有可能触发 ConcurrentModificationException 异常。
fail-fast实现原理
通过对 .class 文件反编译，可以发现对于List集合，foreach 实际上是调用了 itearator() 方式通过迭代器进行遍历。断点调试进入 java.util.ArrayList.Itr#next() 方法查看源码:
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
// 抛出异常原因 modCount != expectedModCount
final void checkForComodification() {
// modCount字段表示这个列表在结构上被修改的次数。
// 结构修改是指改变列表的大小，或者以某种方式扰乱列表，从而使进行中的迭代可能产生不正确的结果。
// 该字段由iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
// 如果该字段的值发生意外变化，迭代器(或列表迭代器)将抛出ConcurrentModificationException，
// 以响应next、remove、previous、set或add操作。
// 这提供了快速故障行为，而不是在迭代期间面对并发修改时的不确定性行为。
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
modCount 什么时候发生了改变?
断点调试list.remove(temp)当 java.util.ArrayList.Itr#next() 方法执行完，进入了 java.util.ArrayList#remove(int) 方法查看源码：
public E remove(int index) {
rangeCheck(index);
modCount++; // 每次list集合进行删除操作的时候 modCount+1
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
当循环再次进入 java.util.ArrayList.Itr#next() 方法中的 checkForComodification() 方法时 modCount != expectedModCount 抛出 ConcurrentModificationException 异常。
为什么使用Iterator不会抛出异常呢？
断点调试 iterator.remove() 会进入 java.util.ArrayList.Itr#remove() 迭代器的删除方法，得知java.util.ArrayList.Itr 是 ArrayList 的内部类，此类定义如下，并没有实现序列化接口，无法网络传输。
private class Itr implements Iterator<E> {}
查看 java.util.ArrayList.Itr#remove() 方法源码：
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet); // 此处调用 ArrayList 的删除操作 modCount+1
cursor = lastRet;
lastRet = -1;
// 将 modCount 赋值给 expectedModCount，再次调用 java.util.ArrayList.Itr#next() 方法中的 checkForComodification() 方法时不会抛异常
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
如何避免fail-fast？
- 普通的 for 循环，这种方案其实存在一个问题，那就是 remove 操作会改变 List 中元素的下标，可能存在漏删的情况。
public class Test {
public static void main(String[] args) {
List<String> userNames = new ArrayList<String>() ;
for (int i = 0; i < 1; i++) {
if (userNames.get(i).equals("czfff")) {
userNames.remove(i);
}
}
System.out.println(userNames);
}
}
- 使用迭代器的 fail-fast 机制进行遍历时的删除操作，如果是多线程并发，还需要在迭代器遍历时加锁。如下源码：
Iterator<String> iterator = list.iterator();
synchronized (对象) {
while(iterator.hasNext()){
if (删除元素的条件) {
iterator.remove();
}
}
}
- 使用 java.util.concurrent.CopyOnWriteArrayList 并发包下的 CopyOnWriteArrayList 代替 ArrayList，该容器内部会对 add、remove、clear 等方法进行加锁操作，是一个线程安全的 List。其实现原理在于，每次add、remove 等操作都是重新创建一个新的数组，再把引用指向新的数组。 如下源码 ：
public class FailSafe {
public static void main(String[] args) {
List<String> list = new CopyOnWriteArrayList<>();
list.add("1");
list.add("2");
list.add("3");
for (String temp : list) {
list.remove(temp);
}
}
}
认识一下COW家族
顺便简单介绍一个 COW（奶牛）家族，即 Copy-On-Write。它是并发的一种新思路，实行读写分离，如果是写操作，则复制一个新集合，在新集合内添加或删除元素。待一切修改完成之后，再将原集合的引用指向新的集合。这样做的好处是可以高并发地对 COW 进行读和遍历操作，而不需要加锁，因为当前集合不会添加任何元素。使用COW 时应注意两点：第一，尽量设置合理的容量初始值，它扩容的代价比较大；第二，使用批量添加或删除方法，如 addAll 或 removeAll 操作，在高并发请求下，可以攒一下要添加或 者删除的元素，避免增加个元素复制整个集 合。如果集合数据是 100MB，再写入 50MB，那么某个时间段内占用的内存就达到（100MB x 2）+50MB=250MB，内存的大量占用会导致GC的频繁发生，从而降低服务器的性能，我们观察如下代码：
public static void main(String[] args) {
List<String> list = new CopyOnWriteArrayList<>();
list.add("1");
list.add("2");
list.add("3");
for (String temp : list) {
list.remove(temp);
}
}
循环20万次，不断地进行数据插人，这对 Cow 类型的集合来说简直是灾难性的操作，本示例执行时间为97.8秒，如果换成 ArrayList，则只需39毫秒，差距巨大！要初始化这样的 COW 集合，建议先将数据填充到 ArayList 集合中去，然后把 ArrayList 集合当成 COW 的参数，这就是使用批量添加的另一种方式。这种一个接一个往里增加元素的场景，简直就是 COW 的阿喀珫斯之踵。所以明显 COW 适用于读多写极少的场景。
COW是 fail-safe 机制的，在并发包的集合中都是由这种机制实现的， fail-safe 是在安全的副本（或者没有修改操作的正本）上进行遍历，集合修改与副本的遍历是没有任何关系的，但是缺点也很明显，就是读取不到最新的数据。这也是 CAP 理论中 C （Consistency）与 A （Availability）的矛盾，即一致性与可用性的矛盾。
参考资料
- [1] 《码出高效》
- [2] fail-fast机制—高级用法与深入解读