yxguang-knowledge-repo

java fail fast 机制研究

Fail-Fast vs Fail-Safe

Fail Fast 是Java集合的一种错误检测机制，当遇到操作错误时，最快速的暴露问题抛出异常，阻止操作继续进行。然而，Fail Safe 在遇到失败的情况下，尽最大可能不会终止操作。
例如：多线程对集合同时操作，线程1通过Iterator遍历集合A中的元素，线程2修改集合A中的结构，那么这种情况就会抛出 ConcurrentModificationException 异常，导致 fail fast 机制。

Fail-Fast Iterators

它是Java集合的一种错误检测机制。当多个线程对集合（非fail-safe的集合类）进行结构上的改变的操作时，有可能会产生fail-fast机制，这个时候就会抛出ConcurrentModificationException（当方法检测到对象的并发修改，但不允许这种修改时就抛出该异常）。

即使不是多线程环境，如果单线程违反了规则，同样也有可能会抛出改异常。

通过阅读集合类的源码发现，在集合中维护了一个内部计数器modCount用于标识集合的结构修改。每次集合add、remove操作，modCount都会增加。当Iterator在迭代过程中，每次调用next()方法都会调用checkForComodification函数对modCount与expectedModCount进行比对，如果两个值不相等，就会抛出ConcurrentModificationException异常终止代码继续执行，核心代码如下(以ArrrayList为例)：

    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];
        }

    final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

常见的Fast-Fail集合有List,Map,Set等:

  • List
    • ArrayList
    • LinkedList
    • Vector (线程安全)
  • Map
    • HashMap
    • LinkedHashMap
    • TreeMap
    • Hashtable (线程安全)
  • Set
    • HashSet
    • LinkedHashSet
    • TreeSet
  • Collections.synchronizedXXX() 创建的线程安全的集合

下面列举一些错误示例：

    @Test
    public void testFailFast2() {
        List<Integer> al = new ArrayList<Integer>();
        al.add(1);
        al.add(2);
        al.add(3);
        al.add(4);
        al.add(5);

        Iterator<Integer> itr = al.iterator();
        //情况一
        while (itr.hasNext()) {
            if (itr.next() == 2) {
                //不会抛出异常
                itr.remove();
            }
        }

        System.out.println(al);

        itr = al.iterator();
        //情况二
        while (itr.hasNext()) {
            if (itr.next() == 3) {
                //抛出异常
                al.remove(3);
            }
        }
    }
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

上面的例子中，通过Iterator对ArrayList进行遍历操作，并修改ArrayList的结构。但是第一种情况正常运行，第二种情况会抛出异常，这是为什么呢？下面我们来具体分析下原因：

通过对比以上代码我们可以发现，情况一调用的是Iterator的remove方法，而情况二调用的是ArrayList的remove，那么我们通过源码查看这两种方式有什么不同。

  • 示例一：
    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();
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们发现关键代码expectedModCount = modCount,这样再调用下次next()方法时checkForComodification()不会抛出异常。

  • 示例二：
    private void fastRemove(int index) {
        modCount++;
        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
    }
1
2
3
4
5
6
7
8

我们发现，核心代码中仅对modCount递增，并没有修改expectedModCount，因此会在下次next()方法中导致checkForComodification()抛出异常。

Fail-Safe Iterators

那什么是Fail-Safe呢？

it’s important to remember that there’s no such thing as a truly Fail-Safe iterator. The correct term is Weakly Consistent.

Fail-Safe机制不会抛出ConcurrentModificationException异常，主要原因有：

Fail-Safe类型的迭代器会对实际的集合创建一个副本，并且遍历这个副本，当任何修改操作改变时，副本是不可更改的，因此遍历可以继续进行下去。Fail-Safe类的集合有以下缺点：

  1. 因为工作在副本之上，迭代器并不保证返回已更新的数据。
  2. 由于需要创建副本，会额外耗费时间、内存。

常见的Fail-Safe机制集合有：ConcurrentHashMap、CopyOnWriteArrayList等。

示例：

   ConcurrentHashMap<String, Integer> map
               = new ConcurrentHashMap<String, Integer>();

       map.put("ONE", 1);
       map.put("TWO", 2);
       map.put("THREE", 3);
       map.put("FOUR", 4);

       // Getting an Iterator from map
       Iterator it = map.keySet().iterator();

       while (it.hasNext()) {
           String key = (String)it.next();
           System.out.println(key + " : " + map.get(key));

           // This will reflect in iterator.
           // Hence, it has not created separate copy
           map.put("SEVEN", 7);
       }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

上面示例中，我们使用的是Fail-Safe的迭代器。即使在遍历过程中，进行了修改操作，也不会抛出异常。

Fail-Fast 解决办法

通过前面的实例、分析，我们已经基本掌握了Fail-Fast产生的原因。有些时候我们需要过滤集合并进行一些修改，如进行增加、删除元素，那么应该怎么操作呢？有几种参考方案：

  1. 使用fori循环进行操作

普通fori循环并没有用到集合Iterator中的遍历，直接使用List中的remove方法，不会进行Fail-Fast检查。

   public void avoidFailFast1() {
       List<String> list = new ArrayList<String>(){{
           add("1");
           add("2");
           add("3");
       }};
       for (int i = 0; i < list.size(); i++) {
           //不抛出异常
           if ("2".equals(list.get(i))) {
               list.remove(i);
           }
       }
       System.out.println(list);
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  1. 直接使用Iterator进行操作
   public void avoidFailFast2() {
       List<String> list = new ArrayList<String>(){{
           add("1");
           add("2");
           add("3");
       }};
       Iterator itr = list.iterator();
       while (itr.hasNext()) {
           if ("2".equals(itr.next())) {
               itr.remove();
           }
       }
       System.out.println(list);
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  1. 使用Java 8 中的filter
    public void avoidFailFast3() {
        List<String> list = new ArrayList<String>(){{
            add("1");
            add("2");
            add("3");
        }};
        list = list.stream().filter(item -> !item.equals("2")).collect(Collectors.<String>toList());
        System.out.println(list);
    }
1
2
3
4
5
6
7
8
9
  1. 使用Fail-Safe集合
    public void testFailSafe1() {
        CopyOnWriteArrayList list = new CopyOnWriteArrayList<Integer>(new Integer[]{1, 3, 5, 7, 9});
        Iterator itr = list.iterator();

        while (itr.hasNext()) {
            Integer no = (Integer) itr.next();
            System.out.println(no);
            if (no == 5) {
                // 14 不会打印
                list.add(14);
            }
        }
        System.out.println(list);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  1. 使用增强for循环(foreach)，并在适当的时机退出

foreach循环是Java提供的一种语法糖，在实际编译后为While循环，但是在While循环内使用的却是集合的方法来进行修改，因此会抛出异常。为了解决这个问题，我们应该在合适的时机进行判断，并跳出循环，避免再调用next()方法进行checkForComodification()检查。参考示例：

  • 示例一
   public void testFailFast5() {
       List<String> list = new ArrayList<String>();
       list.add("1");
       list.add("2");
       list.add("3");
       for (String item : list) {
           if ("1".equals(item)) {
               // 抛出异常
               list.remove(item);
           }
       }
   }
1
2
3
4
5
6
7
8
9
10
11
12

查看编译后的结果，while循环中使用的是list的remove方法

    public void testFailFast5() {
        List<String> list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        Iterator var2 = list.iterator();

        while(var2.hasNext()) {
            String item = (String)var2.next();
            if("1".equals(item)) {
                list.remove(item);
            }
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们做一些调整后，代码运行正常。

public void avoidFailFast4() {
        List<String> list = new ArrayList<String>();
        list.add("1");
        list.add("2");
        list.add("3");
        for (String item : list) {
            if ("1".equals(item)) {
                // 不抛出异常
                list.remove(item);
                break;
            }
        }
        System.out.println(list);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

以上这五种方式都可以避免触发fail-fast机制，避免抛出异常。在并发场景下，建议使用concurrent包中的容器；在单线程场景下，优先使用Java8中Stream、filter，Java8以下版本，建议使用Iterator进行修改。

总结

在本文中，我们学习了Fail-Fast、Fail-Safe机制。完整的代码见GitHub

推荐阅读

Last Updated: 3/6/2019, 11:38:17 AM