31 写入时复制(CopyOnWrite)机制实现线程安全的集合类
Diego38 61 1

1. 前言

ArrayList是我们最常用的集合类,但是它并不支持多线程修改,在多线程修改时会出现可见性问题、抛出ConcurrentModificationException。

目前有两种替换List可以满足多线程场景,一种是通过collections.synchronizedList(list)对原生ArrayList进行修饰,另一种是直接使用CopyOnWriteArrayList,后者具备较好的性能优势,目前已经成为主流。

相对应的HashSet,在多线程场景一般是通过CopyOnWriteArraySet来替换原生的HashSet。

2. 为什么要使用CopyOnWriteArrayList和CopyOnWriteArraySet

ArrayList是不适用与多线程的,我们看下面的案例,假设多线程修改是会出现什么。

public class ArrayListMultiThread {

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

    public static void main(String[] args) throws InterruptedException {


        for (int i =0 ; i < 10 ; i++) {
            new Thread(() -> {
                while (true) {
                    list.add(String.valueOf(ThreadLocalRandom.current().nextLong()));
                }
            }).start();
        }
    }

}

输出

Exception in thread "Thread-1" java.lang.ArrayIndexOutOfBoundsException: 21095
    at java.util.ArrayList.add(ArrayList.java:463)

ArrayList内部是以数组实现的,在增加元素达到扩容阈值时,会创建新的数组,多线程修改时数组的引用会发生变化,实际上操作了不同长度的数组,而数组下标的变量又是共享的,所以会产生数组越界错误。

除了数组越界错误,在遍历list的过程中,如果有其他线程修改,还会遇到ConcurrentModificationException。

将上面的代码修改下:

public class ArrayListMultiThread {

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

    public static void main(String[] args) throws InterruptedException {
        for (int i =0 ; i < 10000 ; i ++) {
            list.add(String.valueOf(i));
        }
        new Thread(() -> {
                while (true) {
                    list.add(String.valueOf(ThreadLocalRandom.current().nextLong()));
                }
            }).start();

        new Thread(() -> {
            //迭代开始时会记录modCount到临时变量expectedModCount
            for (String s : list) {
                //每次比较expectedModCount与当前modCount是否相等,不相等说明在迭代过程中发生了变化
                System.out.println(s);
            }
        }).start();
    }

}

输出:

0
1

.
.
.

12
13
14
Exception in thread "Thread-1" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)

这是因为ArrayList在遍历之前会生成一个迭代器,迭代器中expectedModCount记录着当前修改次数modCount,每次遍历一个元素前都会做下比对,如果发生了变化,则直接抛出异常,防止读到的数据不一致的情况。

将代码直接替换成CopyOnWriteArrayList再看看

public class CopyOnWriteArrayListMultiThread {

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

    public static void main(String[] args) throws InterruptedException {
        for (int i =0 ; i < 10000 ; i ++) {
            list.add(String.valueOf(i));
        }
        new Thread(() -> {
                while (true) {
                    list.add(String.valueOf(ThreadLocalRandom.current().nextLong()));
                }
            }).start();

        new Thread(() -> {
            //迭代开始时会记录modCount到临时变量expectedModCount
            for (String s : list) {
                //每次比较expectedModCount与当前modCount是否相等,不相等说明在迭代过程中发生了变化
                System.out.println(s);
            }
        }).start();
    }

}

运行后发现,输出结果一切正常,未出现ConcurrentModificationException异常。说明CopyOnWriteArrayList经受住了多线程场景的考验,多线程场景应当以CopyOnWriteArrayList替换ArrayList。

CopyOnWriteArraySet类似,它是多线程场景下HashSet的替换类,与HashSet不同的是,HashSet是基于HashMap实现,而CopyOnWriteArraySet是基于CopyOnWriteArrayList实现,在做add的过程中需要遍历list,会有一定的性能开销。

3. 写时复制机制集合类工作原理

写时复制(CopyOnWrite), 不对原集合进行修改,而是拷贝一份新的数组,完成后将数组引用指向新数组。

看下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();
        }
    }

做add操作时进行加锁,拷贝一份新的数组,通过setArray(newElements)将数组引用指向新数组。

而做get(index)操作时,实际上是读取了一份快照,get(index)并不需要加锁,迭代器返回的还是老数组的引用。这样读写互不影响。

用一张图表示就是: image

从图上来看CopyOnWrite的优缺点都比较明显:

  • 相比ArrayList,更适合多线程场景
  • 性能相比Collections.synchronizedList更好,在读场景比如get和size方法时不需要加锁
  • 高并发写场景对内存消耗较大,更适合读多写少场景

CopyOnWriteArraySet是基于CopyOnWriteArrayList实现

  • 相比HashSet,更适合多线程场景
  • 性能相比Collections.synchronizedSet更好,在读场景比如contains和size方法时不需要加锁
  • contains和add方法都需要遍历内部的CopyOnWriteArrayList,查询时间复杂度相比HashSet O(1)变成了O(N)。
  • 同时具备CopyOnWriteArrayList的缺点

    4. 总结

    通过写时复制机制完美解决了对集合类多线程并发问题,在ConcurrentHashMap中扩容时也有类似实现。写时复制机制避免了在原有数据结构上做并发控制,减少了读取时由加锁带来的性能开销,弊端也很明显,增加了内存的消耗。整体来讲,写时复制是一套优秀的并发解决方案。
预览图
评论区

索引目录