Java线程安全集合之COW

概述

java.util.concurrent.CopyOnWriteArrayList写时复制顺序表，一种采用写时复制技术（COW）实现的线程安全的顺序表，可代替java.util.ArrayList用于并发环境中。写时复制，在写入时，会复制顺序表的新副本，在新副本中进行写入操作。这种写入操作非常耗时，但在遍历操作远远多于写入操作的并发多线程场景，却非常高效。

COW

假设有一个共享的数组，对其进行读和写操作，在多线程环境下，要保证其数据安全，就需要对其的并发访问操作进行同步，而对共享数组的并发访问主要有三种，并发读和读，并发写和写，并发读和写。

同步一般都是使用锁来保护这个数组，如果使用一个互斥锁来对这三种并发访问进行同步，那么同一时刻只能由一个线程访问数组（无论是读还是写），这会使线程对数组的访问串行化，是非常低效的，因为对于并发写和写操作来说，固然需要进行互斥访问，但读操作不会修改数据，所以互斥的并发读和读操作不仅仅低效，而且是完全没有必要的，当然为了避免数据不一致问题，并发读和写操作也是需要互斥访问的。为了解决互斥读和读操作的问题，可以使用读写锁，用写锁保证并发写和写的互斥访问，用读锁保证并发读和读操作的共享访问，用读锁和写锁的协作来保证并发写和读的互斥访问。读写锁解决共享读的问题，而写入操作由于会修改数据，因此只能进行互斥访问，而并发读和写操作，由于为了避免数据不一致问题，也需要进行互斥，那么在一些场景下，如果读和写操作之间存在着大量竞争，而读写操作之间又采用互斥同步机制，那么对共享数组的访问就会非常低效。

除互斥同步机制外，还可采用读写分离技术，让读和写操作分别面向不同的实体，这样就不会存在并发问题。写时复制技术就是一种读写分离技术。

写时复制技术是一种共享同步机制，使并发的读和写操作可以同时进行，无需互相等待。采用写时复制技术，只需要一个写锁来对并发写和写操作进行互斥同步。也是空间换时间的实践。

写时复制就是在每次修改共享数组的状态时，需要先复制原数组的副本，然后在副本上进行写入操作，写入完毕后，让共享数组的引用指向新的副本，基本流程如下：复制 - 写入 - 引用变量修改。其中复制操作对于原数组来说只是读取操作，不改变原数组状态，因此完全可以同其他读操作同时执行，而写入操作修改的是原数组副本，此刻共享数组的引用还未指向该副本，因此对其它线程来说是未知的，其它线程如果在此刻需要读取共享数组，那么通过共享数组的引用获取的数组是原数组对象，而原数组状态并未发生任何变化，所以这个阶段也可以同其他读操作同时执行，而最终的赋值操作，因为这一步操作特别快，只是修改变量的值，并且对于引用变量的访问修改，本身都是同步的（是由底层硬件和操作系统控制），这一步对于共享数组本身来说，没有任何影响。

CopyOnWriteArrayList

不同JDK版本里，源码实现有不同。鉴于绝大多数公司（盲猜3个9，99.9%）还是使用JDK8，有必要先看看JDK8源码实现。

JDK8

2个成员变量

final transient ReentrantLock lock = new ReentrantLock(); // 写锁
private transient volatile Object[] array; // 指向数组的引用
/**
 * 获取数组，非私有，方便CopyOnWriteArraySet类访问
 */
final Object[] getArray() {
    return array;
}

解读：

lock是一个写锁，用于保证并发写操作的互斥访问，保证同一时刻只有一个线程能够对列表进行写入；
array是一个数组引用变量，关联数组对象，即CopyOnWriteArrayList的实际存储空间，array关联的数组对象本质上是一个不会再改变的对象，因为一旦array指向这个数组对象，那么CopyOnWriteArrayList就不会再对这个数组对象进行任何形式的修改。

核心方法：

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

public boolean addAll(Collection<? extends E> c) {
	Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ? ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
	if (cs.length == 0)
		return false;
	final ReentrantLock lock = this.lock;
	lock.lock();
	try {
		Object[] elements = getArray();
		int len = elements.length;
		if (len == 0 && (c.getClass() == CopyOnWriteArrayList.class || c.getClass() == ArrayList.class))
			setArray(cs);
		else {
			Object[] newElements = Arrays.copyOf(elements, len + cs.length);
			System.arraycopy(cs, 0, newElements, len, cs.length);
			setArray(newElements);
		}
		return true;
	} finally {
		lock.unlock();
	}
}

解读：add和addAll方法，用于插入新元素。CopyOnWriteArrayList会先加写锁，保证同一时刻只能有一个线程对列表进行修改，通过Arrays.copyOf复制一个副本，同时对数组进行扩容，增加要新增元素的容量，写入新增元素，最后修改array引用变量的值，让array指向新的数组对象。在整个过程，并没有对原数组对象进行任何形式上的修改，所以其他线程可以安全高效的对列表进行任何方式的读操作，而新的数组对象，在被array引用关联之前，都是线程私有的变量，只会被当前线程修改，而不会被其他线程访问，因此是安全的。

CopyOnWriteArrayList的写时复制策略，写入和读取的数组是不同的实体。在写入时会复制一个新的数组副本，而在读取时，都会先获取当前的数组实例，并且使用一个本地引用关联当前的数组实例，如get，forEach等方法，而在相关的读取操作期间，这个数组实例是CopyOnWriteArrayList的一个快照，不会发生任何变化。

获取元素方法：

public E get(int index) {
	return get(getArray(), index);
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
    return (E) a[index];
}

public void forEach(Consumer<? super E> action) {
    if (action == null) throw new NullPointerException();
    Object[] elements = getArray();
    int len = elements.length;
    for (int i = 0; i < len; ++i) {
        @SuppressWarnings("unchecked") E e = (E) elements[i];
        action.accept(e);
    }
}

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

// 遍历iterator时无需同步，不支持remove、set、add等方法
public ListIterator<E> listIterator() {
	return new COWIterator<E>(getArray(), 0);
}

删除元素方法：

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

所有相关读操作，都是基于快照的读操作。通过CopyOnWriteArrayList迭代器COWIterator的实现源码，对CopyOnWriteArrayList通过迭代器进行迭代操作时，实际上遍历的是创建迭代器的那个时刻的快照，因此在迭代过程中进行修改操作，不会抛出ConcurrentModificationException。

static final class COWIterator<E> implements ListIterator<E> {
	// 数组快照
	private final Object[] snapshot;
	// 调用next时返回的元素索引
	private int cursor;
	// 省略私有构造方法
	
	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;
	}
	
	@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;
	}
}

COWIterator迭代器不支持任何修改操作，如remove，add，set等方法，都会抛出UnsupportedOperationException，因为CopyOnWriteArrayList使用的是基于快照的读写分离技术，COWIterator本身是一个基于快照的迭代器，而快照是不可变的。

public void remove() {
	throw new UnsupportedOperationException();
}

public void set(E e) {
	throw new UnsupportedOperationException();
}

public void add(E e) {
	throw new UnsupportedOperationException();
}

缺点

内存占用：由于每次写入时都会对数组对象进行复制，复制过程不仅会占用双倍内存，还需要消耗CPU等资源，所以当列表中的元素比较少时，这对内存和GC并没有多大影响，但是当列表保存大量元素时，CopyOnWriteArrayList的底层数组对象有可能会变成一个大对象，这时对CopyOnWriteArrayList每一次修改，都会重新创建一个大对象，并且原来的大对象也需要回收，这都可能会触发GC，特别是大对象会触发Full GC；

JDK11

JDK8之后的下一个LTS版本JDK就是JDK11。发现还是2个成员变量，不过不再使用ReentrantLock而使用synchronized同步锁。

/**
 * 保护所有变量的锁。（当两者都可以时，我们更喜欢内置监视器而不是 ReentrantLock。）
 */
final transient Object lock = new Object();
private transient volatile Object[] array;

再看看add方法：

public boolean add(E e) {
	synchronized (lock) {
		Object[] es = getArray();
		int len = es.length;
		es = Arrays.copyOf(es, len + 1);
		es[len] = e;
		setArray(es);
		return true;
	}
}

其他方法也都是使用synchronized同步锁。

适用场景

CopyOnWriteArrayList非常适合读多写少的场景，例如缓存列表或事件监听器集合。创建副本的开销可被大量的读操作所抵消。

其他

CopyOnWriteArraySet

java.util.concurrent.CopyOnWriteArraySet使用装饰器模式利用CopyOnWriteArrayList实现的线程安全的集合类，通过遍历比对的方式来判断集合内是否已经存在该元素。所以如果需要对大量元素进行排重，CopyOnWriteArraySet性能会很差。

private final CopyOnWriteArrayList<E> al;
// 构造函数
public CopyOnWriteArraySet() {
	al = new CopyOnWriteArrayList<E>();
}

脏读

脏读是指一个线程在读取某个变量时，另一个线程可能正在修改该变量。导致读取到的数据可能是无效或不一致的。

CopyOnWriteArrayList不存在脏读问题：

当调用add、set或remove等修改操作时，CopyOnWriteArrayList会创建当前数组的一个新副本，在新副本上执行修改操作，最后用新数组替换旧数组。这个过程是原子性的（通过ReentrantLock或synchronized实现）；
在读操作中，CopyOnWriteArrayList直接访问当前数组，且不会被写操作阻塞。不会进行加锁，读取操作非常高效，且能够快速返回当前数组的内容。

{@inheritDoc}

看CopyOnWriteArrayList源码时
在这里插入图片描述
发现源码里注释是这样：

/**
 * {@inheritDoc}
 */
public int indexOf(Object o) {
	Object[] es = getArray();
	return indexOfRange(o, es, 0, es.length);
}

{@inheritDoc}出现在CopyOnWriteArrayList的很多方法。经过分析，想要看原始注释，需要去父类里对应方法找，如List.indexOf()。