CopyOnWriteArrayList内部工作原理剖析

1,801 阅读3分钟
原文链接: github.com

CopyOnWriteArrayList是由Doug Lea在JDK1.5引入的一个并发工具类,CopyOnWriteArrayList其实线程安全的ArrayList,但又有点不一样 和HashMap和ConcurrentHashMap的关系有点类似。所有的修改操作(add/set等)都会将底层依赖的数组拷贝一份并在其之上修改,但是我们知道数组的拷贝是一个比较耗时的操作,因此通常用于读多写少的场景下,例如随机访问、遍历等。

工作原理

首先CopyOnWriteArrayList有哪些重要的域, 首先有个可重入锁用于修改(add/set等)时保证其线程安全型,另外有一个array数组用于存储实际的数据,并用volatile修饰,保证可见性。

    final transient ReentrantLock lock = new ReentrantLock();
    private transient volatile Object[] array;

    final Object[] getArray() {
        return array;
    }

    final void setArray(Object[] a) {
        array = a;
    }

ADD()工作机制

如果看过ArrayList的代码,会发现CopyOnWriteArrayList的会简单很多。

    /**
     * Creates an empty list.
     */
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }


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

我们会发现CopyOnWriteArrayList默认会初始化一个空数组,而在add()方法中也没有想ArrayList一样去判断当前数组的容量并去扩容(比如ensureCapacity),添加元素到数组的基本步骤:

  • 会首先尝试去加锁

  • 会调用getArray()方法获取当前数组的引用并保存到一个本地变量中,采用这种方法,一方面可以去掉一次GETFIELD调用,另外相当于保存了当前引用的快照,这样就算有其他线程并发修改引用,但是至少保证本次方法执行的一致性,当然这里直接加锁保证了不会有并发修改,因此没有这个问题。

  • 将当前数组的内容复制到新数组中,新数组的大小是老数组的长度+1,因此每次新增操作都会导致CopyOnWriteArrayList的长度自增。

  • 拷贝完成后将元素添加到新数组中。

  • 用新数组替换当前数组,用volatile修饰保证后续对其他线程可见性

其他所有的修改方法也一样,都采用了相同的加锁机制:

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

读取

读取相对来说会简单很多,直接采用数组下标访问即可,但是这里读取并没有加锁,因此对于读取操作来说可能会存在延迟,读取不到最新的数据,这里读取通过getArray()方法获取的相当于是一个快照,在修改才做完成前,我们读取的都是这个快照数组的内容,对于遍历也是类似,其内部会利用这个快照数组构造一个新的构造器,因此这里遍历才不需要加锁,但是相对的,之后的add/remove/set等操作不会对迭代器造成任务影响,迭代器也不支持remove操作,也就不会抛出ConcurrentModificationException异常。

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

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

总结

CopyOnArrayList使用与读多写少的场景,而且存储的对象最好不要太多,加入CopyOnArrayList中存储的数据比较多,那么每一次修改才做都会造成一次大对象拷贝,造成YGC甚至是FULL GC,因此使用前一定要考虑好场景。另外一个是由于读取都是快照读,因此会存在一定的延时造成读取不到最新的数据。