Java CopyOnWriteArrayList

在 Java 的集合中, List 是一个很高频使用的集合中, 但是平时使用的 ArrayList, LinkedList 都是线程不安全的。线程可见性不支持, 内部的 fast-fail 机制等都是表明他们不适合高频发的场景使用。如果我们需要一个线程安全的列表集合

使用古老的集合类 Vector
通过 Collections.synchronizedList(List<T> list) 得到一个线程安全的列表

虽然他们的确可以处理高并发的场景, 但是性能却不太行 (内部几乎所有的操作都是通过加同步锁实现的), 那么是否有更好的选择吗 ?

如果你现在的业务场景是一种读多写少, 同时支持短时间的数据延迟的情况, 那么可以考虑使用一下 CopyOnWriteArrayList, 它是一个设计简单, 采用了写时复制 (Copy-On-Write) 的机制, 以确保在读取和写入操作之间的最终一致性的 List。

1 Copy-On-Write

Copy-On-Write 的特点概括起来就 2 个

读写分离
最终一致性

大体的实现如下:

在集合的内部统一维护着一个数组(链表) 的数据结构, 存储着用户的数据
用户读取数据时, 直接就从这个数据结构中获取数据即可
而在用户对内部的数据进行修改时, 则会对修改办法进行加锁, 串行地处理

3.1 获取到锁的线程, 会直接从内部维护的数据结构直接拷贝一份相同的数据
3.2 对拷贝的数据进行修改
3.3 将修改后的数据设置到集合内部统一维护的数据结构

这个过程中

变更的操作不会影响到读取的操作
变更后的数据, 也同样不会被立即读取到这就会造成一定时间的数据不一致
将变更后的数据, 重新设置到集合内部的统一的数据结构后, 最终都能读取到最新的数据, 也就是最终达到数据一致的效果

2 CopyOnWriteArrayList 的实现原理

经过上面的一大篇铺垫, 可能认为 CopyOnWriteArrayList 是一个很复杂的集合类, 实际就是一个简单的数组引用的修改。

下面通过分析源码的进行深入了解一下

public class CopyOnWriteArrayList<E> {

    /** 真正存储数据的数组 */
    private transient volatile Object[] array;

}

可以看到 CopyOnWriteArrayList 本质就是一个数组, 只是这个数组被 volatile 修饰了(volatile 只能保证对象的引用变更了, 能被所有线程感知到, 但是对引用里面的内容进行变更, 线程是无法感知到的)。

2.1 读取操作

我们先简单看一下 CopyOnWriteArrayList 的读操作

public class CopyOnWriteArrayList<E> {

    /**
     * 获取列表中第 index 位的内容
     */
    public E get(int index) {
        return elementAt(getArray(), index);
    }

    /**
     * 获取存储数据的数组
     */
    final Object[] getArray() {
        // 直接返回当前的数组变量 array
        return array;
    }

    /**
     * 获取指定数组对应位置的数据 
     */
    static <E> E elementAt(Object[] a, int index) {
        // 通过索引读取到入参的数组的指定位置的数据
        return (E) a[index];
    }
}

可以看出来整个 get 方法很简单, 没有任何针对并发场景的处理 (CAS, 加锁等)。
因为这个读的操作不涉及都任何的数据变更, 简单实现获取数据的逻辑即可。

2.2 新增数据

public class CopyOnWriteArrayList<E> {

    public boolean add(E e) {

        final ReentrantLock lock = this.lock;
        // 1. 通过一个可重入锁 lock, 保证写线程在同一时刻只有一个, 变为串行的执行
        lock.lock();

        try {
            // 2. 获取到原本存数据的数组的引用
            Object[] elements = getArray();
            // 3. 获取到原本数组的长度
            int len = elements.length;
            // 4. 创建新的数组, 并将旧数组的数据复制到新数组中
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            // 5. 往新数组最后一位添加新的数据
            newElements[len] = e;
            // 截至到这一步, 虽然看起来我们已经对集合里面的数据做了修改,
            // 但是在这之前所有的线程读操作, 还是读取旧数组的数据

            // 6. 将旧数组引用指向新的数组, 上面的数组变量通过 volatile 修饰了, 将新的数组设置过去, 其他线程都会感知到这个变量变了
            // 所以变更后的数据, 这时其他线程可以读取到了
            setArray(newElements);
            return true;
        } finally {
            // 锁释放
            lock.unlock();
        }
    }

    /**
     * 更新集合里面的数组
     */
    final void setArray(Object[] a) {
        // 直接将入参的数组赋值给当前的 array 属性
        array = a;
    }
}

整个 add 方法的逻辑整理如下

竞争锁, 获取锁成功的线程才能继续执行下面的逻辑
从旧的数组里面拷贝一个新的数组
追加新的数据到新数组的最后面
将新的数组替换集合里面的旧数组
释放锁

这里面涉及到 2 个并发相关的知识

可重入锁 ReentrantLock, 让整个写的操作变为串行
修饰 CopyOnWriteArrayList 数组变量的 array, 在数据替换后, 能构让其他线程感知到, 去读取最新的值

3 总结

3.1 Copy-On-Write vs 读写锁

Copy-On-Write 机制和读写锁都是通过读写分离的思想实现的, 但两者还是有些不同。

Copy-On-Write 对写操作做了锁控制, 确保写操作的数据正常, 而对读取操作不做任何的限制, 确保了读取的性能, 但是带来了一定时间 “脏数据” 的问题
读写锁: 对整个读写操作都加锁, 在有线程在读取数据, 写线程必须等待, 在写线程变更数据的过程, 读操作也必须等待写操作完成, 通过这种等待, 牺牲了一定的性能, 但是确保了数据的一致

3.2 Copy-On-Write 的缺点

内存占用问题: 因为 Copy-On-Write 的写时复制机制, 所以在进行写操作的时候, 内存里会同时存在新旧两个对象, 这个会导致的内存差不多两倍的消耗, 如果这些对象占用的内存比较大, 可能会造成内存问题
数据一致性问题: Copy-On-Write 机制只能保证数据的最终一致性, 不能保证数据的实时一致性