Java ConcurrentModificationException及fail-fast机制简析

前言

最近还是很忙，写一些相对容易的大家都知道的知识点吧。

ConcurrentModificationException（下文简称CME），即并发修改异常，是Java集合操作中常见的一种异常。本文通过示例及JDK源码分析产生CME的内部机制，并提出解决方法。

CME的产生

java.util包下很多集合的操作都可能会抛出CME，这里就以ArrayList为例。下面的程序产生包含10个元素的ArrayList，遍历它，并在遍历过程中随机删掉其中一个元素。

public class CMEExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            list.add(String.valueOf(i));
        }
        String random = String.valueOf(new Random().nextInt(10) + 1);
        System.out.println(random);
        for (String s : list) {
            if (s.equals(random)) {
                list.remove(s);
            }
        }
    }
}

多次运行以上程序，发现大多数情况均会抛出CME，如以下输出：

6
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
    at java.util.ArrayList$Itr.next(ArrayList.java:859)
    at me.lmagics.CMEExample.main(CMEExample.java:19)

但是当要删除元素"9"时，就不会抛出异常，执行成功。为什么会有两种不同的情况？下面就通过JDK源码来分析。

CME原因分析（fail-fast机制）

CMEExample类中使用foreach循环来遍历List，也就相当于采用了迭代器。ArrayList的迭代器实现位于私有内部类Itr中，其源码如下。

    public Iterator<E> iterator() {
        return new 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();
        }

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

查看报错信息，CME是在调用Itr.next()方法时，从checkForComodification()方法抛出的，原因是modCount与expectedModCount的值不相等。由上面的代码可知，expectedModCount在Itr初始化时就赋值，其值等于modCount，所以modCount的值一定发生了变化。

modCount字段定义在ArrayList的父类AbstractList中。

protected transient int modCount = 0;

根据JavaDoc的解释，modCount记录了一个列表发生结构化修改（structurally modified，如改变大小或打乱顺序）的次数，类似于版本号。

下图展示了modCount字段会被ArrayList类中的哪些方法修改。注意添加元素的add()与addAll()方法并没有出现，但它们最终调用了ensureExplicitCapacity()方法，故也会修改modCount。

示例代码中调用remove(Object)方法后，嵌套的fastRemove()方法会增加modCount的值，变成11，而expectedModCount的值仍为10，就抛出了CME。

换句话说，ArrayList.remove()方法破坏了迭代器内维护的集合修改状态。如果在迭代过程中进行了任何使modCount改变的操作（不管是单线程还是多线程的环境下），为了防止继续迭代下去发生不可预见的状况，就会立即失败并抛出CME，这就是所谓的快速失败（fail-fast）机制。

那么为什么删除元素"9"就没问题？这与迭代器的hasNext()方法有关。迭代器内维护了指示当前元素的游标cursor，当cursor与列表的大小size相同时，表示没有下一个元素，迭代过程结束。删除掉元素“9”之后，cursor与size的值都是9，所以会退出迭代，next()方法根本不会执行，只是一种巧合而已。

CME的解决方法

就示例中的删除操作而言，正确的方式是不调用容器的remove()方法，而是调用迭代器本身的remove()方法，即：

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            if (s.equals(random)) {
                iterator.remove();
            }
        }

我们可以参考一下Itr.remove()方法的源码，它除了调用ArrayList.remove()方法之外，还做了两件额外的事：

  • 将游标cursor重置回上一个读取的元素下标。
  • 将expectedModCount重新赋值成当前的modCount。

这样在删除元素的同时，也维护了游标位置和修改状态，因此能够安全地继续迭代。如果需要迭代时添加元素，那么可以利用ArrayList提供的另一种迭代器ListIterator，它的功能更加丰富一点，并且机制几乎相同，不再赘述。

多线程环境

文章开头的例子是在单线程环境演示的，但从CME的命名“并发修改异常”来看，它似乎更偏向于多线程的情况。由于ArrayList本身就是线程不安全的，因此我们采用线程安全的列表Vector再做一次实验，以排除干扰。

public class CMEExample {
    public static void main(String[] args) {
        Vector<String> vector = new Vector<>();
        for (int i = 1; i <= 20; i++) {
            vector.add(String.valueOf(i));
        }
        String random = String.valueOf(new Random().nextInt(20) + 1);
        System.out.println("Random: " + random);

        Thread threadA = new Thread(() -> {
            ListIterator<String> iterator = vector.listIterator();
            while (iterator.hasNext()) {
                String s = iterator.next();
                System.out.println("Thread-A: " + s);
                if (s.equals(random)) {
                    iterator.add(s);
                }
            }
        }, "Thread-A");

        Thread threadB = new Thread(() -> {
            ListIterator<String> iterator = vector.listIterator();
            while (iterator.hasNext()) {
                System.out.println("Thread-B: " + iterator.next());
            }
        }, "Thread-B");

        threadA.start();
        threadB.start();
    }
}

这个示例创建了有20个元素的Vector与两个线程。线程A遍历该Vector，并从中随机选择一个元素，使用安全的ListIterator.add()方法再插入一个相同的元素；线程B则只做遍历。其输出如下：

Random: 16
Thread-A: 1
Thread-A: 2
Thread-A: 3
Thread-B: 1
Thread-B: 2
Thread-B: 3
Thread-B: 4
Thread-B: 5
Thread-A: 4
Thread-A: 5
Thread-A: 6
Thread-A: 7
Thread-B: 6
Thread-A: 8
Thread-A: 9
Thread-A: 10
Thread-A: 11
Thread-A: 12
Thread-A: 13
Thread-A: 14
Thread-A: 15
Thread-A: 16
Thread-B: 7
Thread-A: 17
Thread-A: 18
Thread-A: 19
Thread-A: 20
Exception in thread "Thread-B" java.util.ConcurrentModificationException
    at java.util.Vector$Itr.checkForComodification(Vector.java:1210)
    at java.util.Vector$Itr.next(Vector.java:1163)
    at me.lmagics.CMEExample.lambda$main$1(CMEExample.java:37)
    at java.lang.Thread.run(Thread.java:748)

可见，CME与容器本身线程安全与否并没有关系。在这种情况下，当线程A添加元素之后，线程A中迭代器的expectedModCount会随着modCount更新，但线程B中迭代器的expectedModCount并不会更新，进而抛出CME。

要解决多线程CME问题，可以考虑对迭代过程加锁，确保多个线程不会同时遍历列表，即：

        Thread threadB = new Thread(() -> {
            ListIterator<String> iterator = vector.listIterator();
            synchronized (vector) {
                while (iterator.hasNext()) {
                    System.out.println("Thread-B: " + iterator.next());
                }
            }
        }, "Thread-B");

我们还可以使用并发容器CopyOnWriteArrayList来替代普通的ArrayList与Vector。

CopyOnWriteArrayList（以及其他j.u.c包中的集合）是与快速失败相反的安全失败（fail-safe）机制的典型应用。它会在写操作时将集合复制一份副本，在副本上写数据，即COW（copy on write），写完成之后再将正本的引用指向副本，而读操作直接在正本上进行。这种读写分离的方法使得它不会抛出CME，之后有时间的话，也会详细地阅读它的源码。

fail-safe的容器比起fail-fast固然安全了很多，但是由于每次写都要复制，时间和空间的开销都更高，因此只适合读多写少的情景。在写入时，为了尽量保证效率，也应尽量做批量插入或删除，而不是单条操作。并且它的正本和副本有可能不同步，因此无法保证读取的是最新数据，这也是CAP理论中一致性（consistency）与可用性（availability）矛盾的体现。

The End

晚安晚安（但是凌晨有全链路压测，希望窝的流式计算任务们能挺过去，bless

顺便，今晚终于下定决心升级Catalina了，为毛下载这么慢呢……

最后与Mojave合影留念（

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,324评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,356评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,328评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,147评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,160评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,115评论 1赞 296
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,025评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,867评论 0赞 274
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,307评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,528评论 2赞 332
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,688评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,409评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,001评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,657评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,811评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,685评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,573评论 2赞 353