CopyOnWriteArrayList的源码分析

CopyOnWriteArrayList简介

熟悉Java开发的童鞋都知道ArrayList是线程不安全的，在多线程的环境下可能会发生fast-fail机制，抛出ConcurrentModificationException异常，虽然也有并发容器Vector，或者采用Collections的synchronizedCollection方法将ArrayList包装成线程安全类，但是这两种方式都是利用synchronized关键字修饰方法，利用独占锁来保证线程安全，由于独占锁在同一时刻只有一个线程能够获取到对象监视器即读写操作不能并行，所以效率不高。而CopyOnWriteArrayList则采用CopyOnWrite的原理来实现的一个线程安全的容器，读写分离，效率高。

环境

本源码基于JDK1.8

fast-fail机制

fast-fail是一种快速失败机制，在容器中有广泛的运用，我们都知道ArrayList是线程不安全的，当多个线程同时对集合进行结构上的修改时，就可能会产生fast-fail机制。例如：假设存在线程1，线程2，线程1通过Iterator对集合A进行遍历，线程2对集合A进行结构上的修改（不是仅仅修改一个元素）,这时候就会产生fail-fast机制，抛出ConcurrentModificationException异常。原因：线程对容器ArrayList进行修改时，比如添加元素会对modCount进行加一操作，删除一个元素会对modCount进行减一操作。迭代器（Iterator）对容器进行迭代时，会记下刚迭代时的modCount值并赋值给expectedModCount，调用next()时，会比较expectedModCount和modCount的值，如果不相等则抛出ConcurrentModificationException异常。所以如果在迭代过程中修改modCount值必然导致expectedModCount和modCount值不相等。

COW的设计思想

CopyOnWrite的简称是COW, 即将原有的容器复制一份，然后，在新的容器上进行写操作。COW容器写操作流程是当向容器中添加一个元素时，首先将原有的容器复制一份出来，新的容器的大小是原容器大小+1。然后在新容器上添加元素，添加完成之后再将原容器的引用指向新的容器。COW容器进行并发的读的时候，不需要加锁，因为当前容器不会添加或者删除任何元素。 COW本质上的思想是读写分离的思想，跟读写锁的思想相同，只是读写锁为了保证数据的实时一致性，读线程在写线程释放锁之前也会被阻塞，写线程也会在读线程释放锁之前也会被阻塞。而COW则牺牲数据的实时一致性，只保证数据的最终一致性，所以比读写锁效率更高

CopyOnWriteArrayList的实现原理

接下来我们就来看看CopyOnWriteArrayList的实现原理，重点专注下add方法和get方法。

private transient volatile Object[] array;

实际上CopyOnWriteArrayList内部维护的就是一个数组，该数组被volatile修饰，保证了引用的可见性。

add方法

接下来我们来看看CopyOnWriteArrayList如何添加元素的。

  public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        //使用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();
        }
    }

如上代码，我们可以看到：

1.采用ReentrantLock，这样就可以使得写操作是串行的。2.数组引用用是volatile修饰的，因此将旧的数组的引用指向新的数组，根据happen-before原则，写线程对数组引用的修改对读线程是可见的。

get方法

CopyOnWriteArrayList获取指定位置上的元素的方法比较简单，我们来看看。

 public E get(int index) {
        return get(getArray(), index);
    }

如上代码，没有任何的加锁或者CAS操作，因为，读操作都是针对当前容器的，而当前容器不会添加或者删除任何元素。

COW的优缺点

优点

1.读写分离，效率高。

缺点：

2.内存占用问题 因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存中会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意：在复制的时候只是复制容器的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存。），如果这些对象占用的内存比较大，比如说200M左右，那么在写入100M数据进去，内存就会占用300M,这时候就有可能会造成频繁的minor GC 和 major GC。3.数据的实时性问题 CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用 CopyOnWrite 容器。

COW与读写锁的比较

相同点：

4.两者都是通过读写分离，5.读线程间互不阻塞的 不同点：6.读写锁，对于读线程而言，为了实现数据实时性，在写锁被获取后，读线程会等待或者当读锁被获取后，写线程会等待，从而解决了“脏读”等问题，也就是说如果使用读写锁依然会出现读线程阻塞等待的情况。7.COW则牺牲数据的实时一致性，保证数据的最终一致性

总结

8.CopyOnWriteArrayList适用于那些读多写少的场景，比如，系统配置，白名单和黑名单等场景。9.CopyOnWrite的思想是读写分离的思想。

参考

并发容器之CopyOnWriteArrayList 聊聊并发-Java中的Copy-On-Write容器