写时复制与弱一致性--CopyOnWriteArrayList源码剖析

CopyOnWriteArrayList 是一个线程安全的ArrayList ，对其进行的修改操作都是在底层的一个复制的数组（快照）上进行的，也就是使用了写时复制策略。

在CopyOnWriteArrayList 的类图中，每个CopyOnWriteArrayList 对象里面有一个使用volatile修饰的array 数组对象用来存放具体元素，独占锁lock用来保证同时只有1个线程对array进行修改。

写操作

CopyOnWriteArrayList 的写操作需要上锁，下面是add(E e)添加元素的源码：

public boolean add(E e) {
    //获取独占锁
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        //获取array
        Object[] elements = getArray();
        int len = elements.length;
       	//复制array到新数组，添加元素到新数组
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        //使用新数组替换原数组
        setArray(newElements);
        return true;
    } finally {
        //释放独占锁
        lock.unlock();
    }
}
final Object[] getArray() {
    return array;
}
final void setArray(Object[] a) {
    array = a;
}

add(E e)操作是通过加锁-复制-添加-覆盖-解锁实现的，保证了线程安全。从代码可以知道，新数组的大小是原来数组大小加一，CopyOnWriteArrayList 是无界数组。

修改、删除、添加元素的这些写操作的思路都差不多，这里不进行赘述。

弱一致性的迭代器

在讨论读操作前，我们先讨论CopyOnWriteArrayList 中的迭代器的弱一致性。弱一致性是指返回迭代器后，其他线程对list 的增删改对迭代器是不可见的。例：

CopyOnWriteArrayList<Integer> copyOnWriteArrayList=
    new CopyOnWriteArrayList<>(Arrays.asList(0, 1, 2, 3));

Thread thread=new Thread(()->{
    //写操作
    copyOnWriteArrayList.remove(1);
    copyOnWriteArrayList.set(0,100);
});
//在写操作前获取迭代器
Iterator<Integer> iterator=copyOnWriteArrayList.iterator();
//启动线程
thread.start();
//等待线程执行完毕
thread.join();
//迭代元素
while (iterator.hasNext()){
    System.out.println(iterator.next());
}

源码剖析：

1
2
3

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

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

当调用iterator()方法获取迭代器时实际上会返回一个COWiterator 对象， COWiterator 对象的snapshot 变量保存了当前list 的内容， cursor 是遍历list 时数据的下标。

为什么说snapshot 是list 的快照呢？明明是指针传递的引用啊，而不是副本。如果在该线程使用返回的迭代器代器遍历元素的过程中，其他线程没有对list 进行增删改，那么snapshot 本身就是list 的array ，因为它们是引用关系。但是如果在遍历期间其他线程对该list 进行了增删改，那么snapshot 就是快照了，因为增删改后list 里面的数组被新数组替换了，这时候老数组被snapshot引用。这也说明获取迭代器后，使用该法代器元素时，其他线程对该list 进行的增删改不可见，因为它们操作的是两个不同的数组，这就是弱一致性。

读操作

CopyOnWriteArrayList 的读操作不会上锁，也就是说，读操作是允许多个线程进入的。下面是get(int index)获取元素操作的源码：

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

private E get(Object[] a, int index) {
    return (E) a[index];
}

在如上代码中，当线程x 调用get 方法获取指定位置的元素时，分两步走，首先获取array 数组（这里命名为步骤A ），然后通过下标访问指定位置的元素（这里命名为步骤B ) ，这是两步操作，但是在整个过程中并没有进行加锁同步。也就是说，假设这时候List 内容如图所示，里面有1、2 、3 三个元素。

由于执行步骤A 和步骤B 没有加锁，这就可能导致在线程x执行完步骤A 后执行步骤B前，另外一个线程y进行了remove 操作，假设要线程y要删除元素1， remove 操作首先会获取独占锁，然后进行写时复制操作，也就是复制一份当前array 数组，然后在复制的数组里面删除元素1 ，之后让array指向复制的新数组。而这时候array之前指向的数组的引用计数为1而不是0，因为线程x 还在使用它，这时线程x 开始执行步骤B ，步骤B 操作的数组是线程y 删除元素之前的数组。

所以，虽然线程y己经删除了index处的元素，但是线程x 的步骤B 还是有可能会返回index 处的元素，这其实就是写时复制策略产生的弱一致性问题。