1. 简介
java.util.concurrent.CopyOnWriteArrayList 写时复制顺序表，是一种采用写时复制技术（COW）实现的线程安全的顺序表，可以代替 java.util.ArrayList 用在并发环境中。写时复制，顾名思义，就是在写入的时候，会复制顺序表的新副本，在新副本中进行写入操作。这种写入操作是非常耗时，但在遍历操作远远多于写入操作的并发多线程场景，却非常高效。
2. 写时复制技术
假设我们有一个共享的数组，主要对其进行读和写操作，那么在多线程环境下，要保证其数据安全，就需要对其的并发访问操作进行同步，而对共享数组的并发访问主要有三种，并发读和读，并发写和写，并发读和写；如何同步呢？一般都是使用锁来保护这个数组，如果使用一个互斥锁来对这三种并发访问进行同步，那么同一时刻只能由一个线程访问数组（无论是读还是写），这会使线程对数组的访问串行化，是非常低效的，因为对于并发写和写操作来说，固然需要进行互斥访问，但读操作不会修改数据，所以互斥的并发读和读操作不仅仅低效，而且是完全没有必要的，当然为了避免数据不一致问题，并发读和写操作也是需要互斥访问的。为了解决互斥读和读操作的问题，我们可以使用读写锁，用写锁保证并发写和写的互斥访问，用读锁保证并发读和读操作的共享访问，用读锁和写锁的协作来保证并发写和读的互斥访问。读写锁解决了共享读的问题，而写入操作由于会修改数据，因此只能进行互斥访问，而并发读和写操作，由于为了避免数据不一致问题，也需要进行互斥，那么在一些场景下，如果读和写操作之间存在着大量竞争，而读写操作之间又采用互斥同步机制，那么对共享数组的访问就会非常低效。除了互斥同步机制以外，有没有其他方法对读和写操作进行同步呢？可以采用读写分离技术，让读和写操作分别面向不同的实体，这样就不会存在并发问题了。写时复制技术就是一种读写分离技术。
2.1 写时复制技术原理
写时复制技术是一种共享同步机制，它使并发的读和写操作可以同时进行，无需互相等待。采用写时复制技术，只需要一个写锁来对并发写和写操作进行互斥同步。我们先简单描述一下写时复制的操作流程，写时复制就是在每次修改共享数组的状态时，需要先复制原数组的副本，然后在副本上进行写入操作，写入完毕后，让共享数组的引用指向新的副本，所以基本流程如下：复制 - 写入 - 引用变量修改。其中复制操作对于原数组来说只是读取操作，不改变原数组状态，因此完全可以同其他读操作同时执行，而写入操作修改的是原数组副本，此刻共享数组的引用还未指向该副本，因此对其它线程来说是未知的，其它线程如果在此刻需要读取共享数组，那么通过共享数组的引用获取的数组是原数组对象，而原数组状态并未发生任何变化，所以这个阶段也可以同其他读操作同时执行，而最终的赋值操作，因为这一步操作特别快，只是修改了变量的值，并且对于引用变量的访问修改，本身都是同步的（是由底层硬件和操作系统控制），这一步对于共享数组本身来说，没有任何影响。
3. CopyOnWriteArrayList实现
3.1 写时复制策略的实现
首先我们先看看 CopyOnWriteArrayList 中的几个关键的成员变量
1. final transient ReentrantLock lock = new ReentrantLock(); //写锁
2. private transient volatile Object[] array; //指向数组的引用
-
lock是一个写锁，用于保证并发写操作的互斥访问，保证同一时刻只有一个线程能够对列表进行写入。 -
array是一个数组引用变量，它关联了一个数组对象，这个数组对象就是CopyOnWriteArrayList的实际存储空间，array关联的数组对象本质上是一个不会再改变的对象，因为一旦array指向了这个数组对象，那么CopyOnWriteArrayList就不会再对这个数组对象进行任何形式的修改。
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
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();
}
}
/**
* Appends all of the elements in the specified collection to the end
* of this list, in the order that they are returned by the specified
* collection's iterator.
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
* @see #add(Object)
*/
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 && cs.getClass() == Object[].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();
}
}
通过 CopyOnWriteArrayList 的 add 和 addAll 方法，我们看到，在需要插入新元素时，CopyOnWriteArrayList 会先加写锁，这样保证同一时刻只能有一个线程对列表进行修改，之后通过 Arrays.copyOf 方法复制一个原数组的副本，同时对数组进行扩容，增加要新增元素的容量，然后写入新增元素，最后修改 array 引用变量的值，让 array 指向新的数组对象。在整个过程，我们看到并没有对原数组对象进行任何形式上的修改，所以其他线程可以安全高效的对列表进行任何方式的读操作，而新的数组对象，在被 array 引用关联之前，都是线程私有的变量，只会被当前线程修改，而不会被其他线程访问，因此也是安全的。
3.2 基于快照的读写分离技术
通过对 CopyOnWriteArrayList 的写时复制策略的分析， 我们发现 CopyOnWriteArrayList 实际上应用了一种读写分离技术，它写入和读取的数组是不同的实体。CopyOnWriteArrayList 在写入的时候会复制一个新的数组副本，而在做读取操作的时候，都会先获取当前的数组实例，并且使用一个本地引用关联当前的数组实例，如 get，forEach 等方法，而在相关的读取操作期间，这个数组实例不会发生任何变化，这个数组实例就是 CopyOnWriteArrayList 的一个快照。因此，CopyOnWriteArrayList 的所有相关读操作，都是基于快照的读操作。通过 CopyOnWriteArrayList 迭代器 COWIterator 的实现源码，我们看到，对 CopyOnWriteArrayList 通过迭代器进行迭代操作时，实际上遍历的是创建迭代器的那个时刻的快照，因此在迭代过程中，如果对 CopyOnWriteArrayList 进行修改操作，将不会抛出 ConcurrentModificationException（因为读和写的是不同的实体，也就不存在同步问题了）。不过 COWIterator 迭代器本身，不支持对迭代器做任何修改操作，比如 remove，add 等方法，都会抛出 UnsupportedOperationException，这是为什么呢？因为 CopyOnWriteArrayList 使用的是基于快照的读写分离技术，COWIterator 本身是一个基于快照的迭代器，而快照是不可变的。
/**
* {@inheritDoc}
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
return get(getArray(), index);
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
/**
* Gets the array. Non-private so as to also be accessible
* from CopyOnWriteArraySet class.
*/
final Object[] getArray() {
return array;
}
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);
}
}
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator provides a snapshot of the state of the list
* when the iterator was constructed. No synchronization is needed while
* traversing the iterator. The iterator does <em>NOT</em> support the
* {@code remove} method.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
/**
* {@inheritDoc}
*
* <p>The returned iterator provides a snapshot of the state of the list
* when the iterator was constructed. No synchronization is needed while
* traversing the iterator. The iterator does <em>NOT</em> support the
* {@code remove}, {@code set} or {@code add} methods.
*/
public ListIterator<E> listIterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array */
private final Object[] snapshot;
/** Index of element to be returned by subsequent call to next. */
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;
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; {@code remove}
* is not supported by this iterator.
*/
public void remove() {
throw new UnsupportedOperationException();
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; {@code set}
* is not supported by this iterator.
*/
public void set(E e) {
throw new UnsupportedOperationException();
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; {@code add}
* is not supported by this iterator.
*/
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;
}
}
4. 总结
前面的内容我们分析了 CopyOnWriteArrayList 的实现，知道他采用了读写分离技术和写时复制技术，使读和写操作之间不会发生锁竞争，因此多线程环境下，当读操作（尤其是需要对列表进行迭代的读操作）远远多于写操作的时候，CopyOnWriteArrayList 会非常的高效。当然 CopyOnWriteArrayList 也会导致以下问题：
- 内存占用问题：由于每次写入的时候都会对数组对象进行复制，复制过程不仅会占用双倍内存，还需要消耗 CPU 等资源，所以当列表中的元素比较少的时候，这对内存和 GC 并没有多大影响，但是当列表保存了大量元素的时候，
CopyOnWriteArrayList的底层数组对象有可能会变成一个大对象，这时候，对CopyOnWriteArrayList每一次修改，都会重新创建一个大对象，并且原来的大对象也需要回收，这都可能会触发 GC，特别是大对象会触发 Full GC，引起应用程序长时间停顿。 - 数据一致性问题：由于
CopyOnWriteArrayList采用的是基于快照的读写分离技术，每次都是读取数据快照的内容，因此，当写线程更新了列表的数据后，读线程是无法立刻看到更新的内容的，需要等待当前的读操作完毕，在下一次读操作时，才能看到最新的内容，因此CopyOnWriteArrayList只能保证数据的最终一致性，而不能保证数据的实时一致性。所以如果希望写入的内容马上能够被读线程看到，那么CopyOnWriteArrayList是不合适的。
5. CopyOnWriteArraySet
java.util.concurrent.CopyOnWriteArraySet 是使用装饰器模式利用 CopyOnWriteArrayList 实现的线程安全的集合类，是一种集合，集合的最主要特性就是互异性（就是集合中任何两个元素都认为是不相同的，即每个元素只能出现一次），底层是一个 CopyOnWriteArrayList 实例，通过遍历比对的方式来判断集合内是否已经存在该元素了。所以如果需要对大量元素进行排重，CopyOnWriteArraySet 性能会很差。
