CopyOnWriteArrayList 源码解读

缘起

CopyOnWriteArrayList（下简称COW） 是常见的线程安全的集合类. 它的源码是比较好读的—— 从它的源码你也知道为什么它的名字会是”写时复制”，其实这里所谓的”写时”指的是”增删改”. 其基本思路是，从一开始大家都在共享同一个内容，当某个人想要修改这个内容的时候，才会加（可重入）锁然后把原内容 Copy 出去形成一个新的内容然后再改，从而不影响别的线程读（读操作不加锁, 所以提高了效率,支持并发读）. 所以也可以说COW借鉴了读写分离(读的和写的数据不是同一个)的思想.

分析

增

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock(); // 加（可重入）锁，因为COW支持的是并发读，但是不支持并发改
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1); // 先copy出去一份内容，然后在copy出去的内容的基础上修改.
            newElements[len] = e; // 在copy出去的内容上修改
            setArray(newElements); // 添加完元素之后，再将原数组的引用指向新的数组
            return true;
        } finally {
            lock.unlock(); // 释放锁
        }
    }

​ 源码1

其中源码1的第五行的源码如下

1
2
3
4
5
 /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array; 
final Object[] getArray() {
        return array;
    }

​ 源码2

注意，array就是真正COW中存储数据的. 它是transient的理由在我原先写的HashMap源码解读中讲过. 而且并不因为transient就不序列化了，因为COW自己实现了private的readObject和writeObject方法.

本文其实更加关注的是array的volitale属性.

源码1的其他部分都加了注释的，比较容易懂.

从源码1的add方法很容易看出COW的一个缺点——占用内存，写时 copy 效率低。因为 CopyOnWrite 的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以
有两份对象内存）。如果这些对象占用的内存比较大，比如说 200M 左右，那么再写入 100M数据进去，内存就会占用 300M，那么这个时候很有可能造成频繁的 Yong GC 和 Full GC。在高性能的互联网应用中，这种操作分分钟引起故障 .

查

1
2
3
4
5
6
public E get(int index) {
	return get(getArray(), index);
}
private E get(Object[] a, int index) {
        return (E) a[index];
    }

​ 源码3

COW查的算法很简单——简单的数组索引. 但是结合add方法就能看出COW第二个致命的缺点

为了效率牺牲了一致性

因为需要支持并发读，这就意味着读一定不能加锁. 但是这样的话，你在读的时候，写方法就可以进入导致其实你读的可能是过期的数据了（甚至COW的array都被清空了说不定）. 但是COW可以保证的是最终一致性. 即COW只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用 COW。

删

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 { // 原数组elements分成两截拷贝到新数组newElements
                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();
        }
    }

​ 源码4

迭代(因为COW实现了java.util.List接口，而List接口是Collection的子接口，Collection实现了Iterable接口)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }

static final class COWIterator<E> implements ListIterator<E> {
        /** Snapshot of the array */
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor;

        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }
    ...
    @SuppressWarnings("unchecked")
        public E next() {
            if (! hasNext())
                throw new NoSuchElementException();
            return (E) snapshot[cursor++];
        }

​ 源码5

源码5中的snapshot就是将当前数组array传进去. 考虑到增删改的方法，这里叫snapshot（快照）是再合适不过了.

改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public E set(int index, E element) {
    //(1)获得独占锁
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();//(2)获得array
        E oldValue = get(elements, index);//(3)根据下标,获得旧的元素
 
        if (oldValue != element) {//(4)如果旧的元素不等于新的元素
            int len = elements.length;//(5)获得旧数组的长度
            Object[] newElements = Arrays.copyOf(elements, len);//(6)复制出新的数组
            newElements[index] = element;//(7)修改
            setArray(newElements);//(8)替换
        } else {
            //(9)为了保证volatile 语义，即使没有修改，也要替换成新的数组
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();//(10)释放独占锁
    }
}

​ 源码6

其实源码6的其他代码都容易看懂，唯独第17行会令初学者费解. 因为这里不得不提及volatile关键字的内存语义（参见【1】）

如果有了【1】的认知，我们考虑下面一种情形就不难知道为什么需要第17行了（大师就是大师，考虑的如此精密！！！）

1
2
3
4
5
6
7
8
有2根线程 thread1和thread2
thread1:
 动作x:a = calValue;
 动作y:coal.set….
 ———————
 thread2:
 动作m:coal.get…
 动作n:int tmp = a;

假设y在m前发生，则根据happens-before规则，有happen-before(y,m),根据线程内的操作相关规定（happens-before准则之程序次序规则）有happen-before(x,y), happen-before(m,n)，根据happen-before的传递性读写a变量就有happen-before(x,n)，所以thread1对a的写操作对thread2中a的读操作可见。如果COW中的set的else里没有setArray(elements) 的话，happens-before(y,m)就不再有了，上述的可见性也就无法保证。
所以实际上else中的setArray(elements)不是为了保证COW本身的可见性，而是保证外部的非volatile变量的happens-before。

参考

【1】https://yfsyfs.github.io/2019/06/24/volatile%E5%85%B3%E9%94%AE%E5%AD%97%E7%9A%84%E5%86%85%E5%AD%98%E8%AF%AD%E4%B9%89/

【2】https://yfsyfs.github.io/2019/06/07/java-util-HashMap-%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/