CopyOnWriteArrayList源码学习

361 阅读5分钟

CopyOnWriteArrayList源码学习

1.Copy-On-Write 策略

Copy-On-Write 简称COW,意思是写入时复制;大家共享同一个变量,多个人读取的时候都是那一个变量;当有一个人要修改变量,则先复制一份,修改变量的副本,这个过程中不影响其他人读取原来的变量。 这种优化策略在Linux系统、Redis、文件系统中都有应用,这里我们讲解这种思想在Java中的应用。 CopyOnWrite容器,当向一个共享容器进行写入或修改操作时,不直接操作原有容器,先拷贝一份新容器,在新容器中进行写入或修改操作,最后将共享变量的地址指向新容器。这个过程中写操作不影响并发读,读和写是分离的。 Java中的CopyOnWriteArrayList和CopyOnWriteArraySet是对这种思想的实践。

2. CopyOnWriteArrayList

在Java中要保证一个List线程安全,要么使用Vector要么使用Collections.synchronizedList方法生成一个线程安全的包装类SynchronizedList。这两种方式都是通过加锁的方式实现了线程安全,区别在于Vector是在声明方法的时候加synchronized,而SynchronizedList是在包装方法内部添加synchronized实现。 这两种方式有个共同的缺点,增删改查方法都加锁了,在读多写少的情况下很影响性能。

特点:

线程安全,无须手动加锁;

通过锁+数组拷贝+violate保证了线程安全;

2.1 构成

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;
    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();
    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;
    //....
}

CopyOnWriteArrayList实现了List接口,内部数据存储和ArrayList同样使用数组实现,这里需要注意的是:

(1)这里使用ReentrantLock作为独占锁,相比于synchronized,ReentrantLock更灵活,但需要手动释放锁。

(2)array 使用volatile修饰,保证了可见性,有最终一致性,但不是实时一致的。

2.2 添加元素

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

写入操作的第一步是加锁,这里可以学习下ReentrantLock的使用,记得在finally语句中释放锁。剩下的就是拷贝数组,在新数组上添加元素,最后将array指向新数组。

这里有个点需要注意下:这里已经加锁了,为什么不直接在原数组上修改?

一是修改原数组会导致读取数据异常,二是violate修饰的是array变量,修改原数组虽然数组变了,但array指向的是同一块地址,无法触发其可见性。所以必须要复制新数组来实现元素新增。

在指定位置插入元素的源码如下:

public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+
                    ", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)// 移动元素数为0说明是在末尾插入元素。
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // 分两次插入元素。
            newElements = new Object[len + 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1,
                    numMoved);
        }
        newElements[index] = element;
        setArray(newElements);
    } finally {
        lock.unlock();
    }
}

这里总结一下:

(1)加锁保证了同一时刻,只能有一个线程进行修改操作。

(2)使用数组拷贝生成新的数组,在新数组上进行修改操作,不影响并发读取数据的一致性。

(3)使用violate修饰array,指向新数组时,其他线程可以立即读到最新值。

2.3 删除元素

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

指定索引删除元素的过程和按索引添加元素的过程类似,都是加锁判断位置进行拷贝最后解锁。

修改元素的过程同样也是加锁后对复制的新数组进行修改,最后更改数组引用,这里不贴代码了,直接看迭代的代码。

2.4 迭代过程

由于CopyOnWriteArrayList修改的都是老数组,所以对原数组在结构上时没有修改的,在迭代过程中修改元素不会抛ConcurrentModificationException异常。但需要注意的时一旦迭代开始,迭代器持有的数组时不变的,此时修改数组不会影响迭代的顺序。

static final class COWIterator<E> implements ListIterator<E> {
    // 迭代器持有的数组快照,
    private final Object[] snapshot;
    // 迭代的游标
    private int cursor;
	// 创建迭代器时就决定了快照的版本
    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }
    // 支持向后迭代
    public boolean hasNext() {
        return cursor < snapshot.length;
    }
    // 支持向前迭代
    public boolean hasPrevious() {
        return cursor > 0;
    }
    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }
    @SuppressWarnings("unchecked")
    public E previous() {
        if (! hasPrevious())
            throw new NoSuchElementException();
        return (E) snapshot[--cursor];
    }
    public int nextIndex() {
        return cursor;
    }
    public int previousIndex() {
        return cursor-1;
    }
    // 不支持修改操作
    public void remove() {
        throw new UnsupportedOperationException();
    }
    public void set(E e) {
        throw new UnsupportedOperationException();
    }
    public void add(E e) {
        throw new UnsupportedOperationException();
    }
	// 遍历操作同样只是针对快照操作
    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        Object[] elements = snapshot;
        final int size = elements.length;
        for (int i = cursor; i < size; i++) {
            @SuppressWarnings("unchecked") E e = (E) elements[i];
            action.accept(e);
        }
        cursor = size;
    }
}

2.5 小结

这里总结一下CopyOnWriteArrayList的特点,CopyOnWriteArrayList读写分离,适合读多写少的场景;使用ReentrantLock作为独占锁,保证增删改操作的互斥性。当然缺点也很明显,首先是占用内存多,每次修改都会复制新数组;其次正因为读写分离了,所以写操作不具有实时一致性,只有最终一致性,如果对读取数据有实时一致性要求则不要使用该容器;同样迭代过程读到的是快照数组中的值,同样不具备实时性。

3.CopyOnWriteArraySet

CopyOnWriteArraySet内部使用的是CopyOnWriteArrayList实现。

引用:

聊聊并发-Java中的Copy-On-Write容器,by 方腾飞

CopyOnWriteArrayList你都不知道,怎么拿offer?,by Java3y