Java集合系列[4]-fail-fast机制解析

发表于

概括

前面我们学习过了ArrayList 和 LinkedList，它们的迭代器都是快速失败的，也就是”fail-fast”机制。本文将以ArrayList为基础，对迭代器的”fail-fast”机制进行系统地学习。内容主要分为下面几个部分：

  • fail-fast简介
  • fail-fast示例
  • fail-fast解决方法
  • fail-fast原理
  • fail-fast解决原理

fail-fast简介

fail-fast是Java集合（Collection框架）中的一种错误机制。当多个线程对同一个集合的内容进行操作的时候，就可能会产生fail-fast事件。

例如：当线程A通过迭代器访问集合的过程中，线程B改变了集合的内容；那么当线程A访问集合的时候，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

fail-fast示例

“Talk is cheap, Show me the code!”，为了更进一步认识fail-fast机制，下面将会编写一个示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package com.archerda.FailFast;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
 * fail-fast机制示例
 * Created by luohd on 2016/8/24.
 */
public class FailFastTest {
    private static List<Integer> list = new ArrayList<>();
    public static void main(String[] args) {
        /* 同时启动两个线程 */
        new ThreadOne("ThreadOne").start();
        new ThreadTwo("ThreadTwo").start();
    }
    private static void printAll() {
    
        /* 用迭代器来遍历集合 */
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();
    }
    private static class ThreadOne extends Thread {
        ThreadOne(String name) {
            super(name);
        }
        @Override
        public void run() {
            for (int i = 0; i < 10; ++i) {
                list.add(i);
                printAll();
            }
        }
    }
    private static class ThreadTwo extends Thread {
        ThreadTwo(String name) {
            super(name);
        }
        @Override
        public void run() {
            for (int i = 10; i < 20; ++i) {
                list.add(i);
                printAll();
            }
        }
    }
}

结果：

1
Exception in thread "ThreadTwo" java.util.ConcurrentModificationException

结果分析：

  • FailFastTest通过启动来线程去操作list，ThreadOne往list里写入0-9,每写一个值立马遍历一次，ThreadTwo往list写入10-19，每写一个值也同样立马遍历一次list。
  • 当某个线程遍历list的过程中，list被另一个线程改变了，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

fail-fast解决办法

fail-fast机制，是一种错误检测机制（不是容错机制）。它只能用来检测错误，因为JVM并不保证fail-fast一定会发生。如果要在多线程环境中使用fail-fast机制的集合，建议使用java.util.concurrent包的类去替换java.util包的类。

上个示例，只需要把

1
private static List<Integer> list = new ArrayList<>();

修改为

1
private static List<Integer> list = new CopyOnWriteArrayList<>();

就可以解决该问题。

fail-fast原理

产生fail-fast事件，是通过抛出ConcurrentModificationException异常来触发的。那么，ArrayList是如何确定需要抛出ConcurrentModificationException异常的呢？

查看源码，我们可以看见ConcurrentModificationException是在操作Iterator的时候才抛出的(JDK1.8有几个额外的接口也会抛出，比如replaceAll(UnaryOperator operator)等)。我们看下Iterator的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
<!-- AbstractList.java -->
// AbstractList中唯一的属性
// 用来记录List修改的次数：每修改一次(添加/删除等操作)，将modCount+1
protected transient int modCount = 0;
<!-- ArrayList.java -->
// 返回List对应迭代器。实际上，是返回Itr对象。
public Iterator<E> iterator() {
    return new Itr();
}
 /**
 * 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;
    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;
        
        // i >= elementData.length，则说明集合已经被修改了
        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();
    }
    // 检查修改次数
    final void checkForComodification() {
        // 如果修改次数不等于该迭代器的期望修改次数，就抛出异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

从源码可以看出，无论是next(),remove()等，只要涉及到修改集合元素个数的操作，都会修改modCount的值。
接下来，我们再一步步分析是怎么产生fail-fast事件的：

  1. new了一个ArrayList，命名为list;
  2. 向list中添加元素；
  3. 启动线程A，并在线程A通过迭代器反复遍历list的元素；
  4. 启动线程B，并在线程B中删除其中的一个节点e；
  5. 这时，就有个有趣的事情发生了：在某个时刻，线程A创建list的迭代器。此时节点e还在list中，创建迭代器的时候，expectedModCount=modCount，假设为N。在线程A遍历list的某个时刻，线程B执行了删除节点e的操作，此时线程B执行了remove操作后，执行了modCount++，此时modCount = N+1。当线程A继续遍历的时候，expectedModCount还是N，而modCount是N+1，所以便抛出了ConcurrentModificationException异常，产生了fail-fast事件。

至此，我们已经完全理解了fail-fast事件是如何产生的了！

总结来说就是，当某个集合在多线程的环境中被操作时，某线程在访问集合的过程中，该集合的内容被其他线程修改了，导致线程独享的expectedModCount与集合的modCount不一样，这时就会抛出ConcurrentModificationException，产生了fail-fast事件。

fail-fast解决原理

上面说明了fail-fast是如何产生的。接下来，我们再来看看java.util.concurrent包下面的类是如何解决fail-fast事件的。同理，用ArrayList对应的线程安全类CopyOnWriteArrayList来说明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
<!-- CopyOnWriteArrayList.java，已省略部分源码 -->
public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    /* 可重入的互斥锁 */
    final transient ReentrantLock lock = new ReentrantLock();
    
    /* 线程间可见的数组 */
    private transient volatile Object[] array;
    
    /* remove操作是重新创建了一个数组，并把没删除的数组元素赋值到新数组，所以不影响原始数组 */
    public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }
    
    public Iterator<E> iterator() {
        /* 返回一个COW迭代器 */
        return new COWIterator<E>(getArray(), 0);
    }
        
    static final class COWIterator<E> implements ListIterator<E> {
            /** 数组元素的快照数组 */
            private final Object[] snapshot;
            
            /** 调用next()返回的索引值 */
            private int cursor;
    
            /* 新建COWIterator时，将集合中的元素保存到一个新的拷贝数组中。
26          这样，当原始集合的数据改变，拷贝数据中的值也不会变化。*/
            private COWIterator(Object[] elements, int initialCursor) {
                cursor = initialCursor;// 初始化光标
                snapshot = elements; //初始化快照数组
            }
    
            public boolean hasNext() {
                return cursor < snapshot.length;
            }
    
            public boolean hasPrevious() {
                return cursor > 0;
            }
    
            @SuppressWarnings("unchecked")
            public E next() {
                if (! hasNext())
                    throw new NoSuchElementException();
                return (E) snapshot[cursor++];
            }
    
            @SuppressWarnings("unchecked")
            public E previous() {
                if (! hasPrevious())
                    throw new NoSuchElementException();
                return (E) snapshot[--cursor];
            }
    
            public int nextIndex() {
                return cursor;
            }
    
            public int previousIndex() {
                return cursor-1;
            }
    
            public void remove() {
                throw new UnsupportedOperationException();
            }
            
            public void set(E e) {
                throw new UnsupportedOperationException();
            }
            
            public void add(E e) {
                throw new UnsupportedOperationException();
            }
    
            @Override
            public void forEachRemaining(Consumer<? super E> action) {
                Objects.requireNonNull(action);
                Object[] elements = snapshot;
                final int size = elements.length;
                for (int i = cursor; i < size; i++) {
                    @SuppressWarnings("unchecked") E e = (E) elements[i];
                    action.accept(e);
                }
                cursor = size;
            }
        }
    }

从中我们可以看出：

  1. CopyOnWriteArrayList没有继承AbstractList，而是直接实现List接口；
  2. CopyOnWriteArrayList创建迭代器的时候，把集合的数组引用直接给赋值给迭代器的snapshot数组，而当执行remove等改变集合元素的时候，会重新创建一个新数组给集合，所以不影响snapshot数组。也就是说，创建迭代器后，迭代器遍历的snapshot数组元素是不变的；
  3. 综上，当多个线程操作同一个集合的时候，线程A遍历集合的时候就已经把当时集合的所有元素快照下来了，而后线程B修改了集合的内容时，线程A遍历开始时的元素没有发生变化，因此不会抛出ConcurrentModificationException异常，也就不会发生fail-fast事件了。

ListIterator操作会产生fail-fast事件吗

我们知道，ListIterator有remove(),set(), add()方法，这个肯定会影响到列表的modCount属性，那ListIterator的expectedModCount会不会和modCount不相等而导致fail-fat事件呢？ 答案是否定的。

我们先看下ListIterator的数据结构:

1
2
3
int cursor;       // 光标所在位置,默认为0
int lastRet = -1; // 光标刚移过位置,默认为-1
int expectedModCount = modCount; //期望修改次数,默认和集合的修改数一致

我们看下add()方法的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//ArrayList.ListItr.add()
public void add(E e) {
    checkForComodification();
    try {
        int i = cursor;
        
        //在当前光标位置插入元素
        ArrayList.this.add(i, e);
        
        //光标向后移动一位,也就是说光标会跳过刚添加的元素;
        //从另一方面来说,add()后,previous()会返回刚添加的元素
        cursor = i + 1;
        
        //最后访问的位置重新赋为-1
        lastRet = -1;
        
        //修改期望修改数,避免引发fail-fast事件;
        //从这里我们可以看出,修改后列表迭代器的期望值是等于列表的修改数的,所以不会引发f-f事件.
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

从上面可以看出,迭代器的修改方法都会重新执行

1
expectedModCount = modCount;

所以是不会产生f-f事件的!

关于迭代器的操作,下面有个趣味代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package com.github.archerda.arraylist;
import java.util.ArrayList;
import java.util.Collections;
import java.util.ListIterator;
/**
 * Create by archerda on 2016/09/05
 */
public class ListIteratorTest {
    public static void main(String[] args) {
        String[] langs = {"Java", "iOS", "Golang"};
        ArrayList<Object> list = new ArrayList<>();
        Collections.addAll(list, langs);
        ListIterator<Object> lit = list.listIterator();
        while (lit.hasNext()) {
            System.out.println(lit.next());
            lit.add("-----split-----");
        }
        System.out.println("traverse reserve: ");
        while (lit.hasPrevious()) {
            System.out.println(lit.previous());
        }
    }
}

其执行结果如何呢?大家可以思考下.结合光标稍微分析下就应该会有答案了呢.

参考文档