一、前言
CopyOnWriteArrayList作为并发容器集合，在窥探其原理之前，先想想，倘若让我们自己来开发一个并发集合，该如何设计？
加synchronized？加ReentrantLock？在哪加？如何加？
为确保线程安全，在读和写操作的方法上都加上synchronized或者ReentrantLock，保证在多线程情况下，只有一个线程访问集合。显而易见，读写互斥，读读互斥，写写互斥，性能极其低下，例如老牌并发集合java.util.Vector，java.util.Collections#synchronizedCollection(java.util.Collection<T>)，都是在读写方法上加了锁。
再者，加读写锁ReadWriteLock，读操作加读锁ReadLock，写操作加写锁WriteLock，读读不互斥，性能上有所提高，但是读写依然互斥，在读多写少的场景，大量的读势必会被一个写阻塞，从而影响性能。
二、何为 CopyOnWrite
对于并发容器集合，CopyOnWriteArrayList有更优的解决方案：
CopyOnWriteArrayList利用CopyOnWrite思想，即在写时复制一份副本进行修改，修改完成后，再将新值赋值给旧值，为保证线程安全，需要在所有的写操作加悲观锁或者乐观锁，而读操作不必加锁，这就使得读写分离，读读不互斥，读写不互斥，空间换时间，性能大大提升。
三、源码分析
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两个重要的成员变量lock和array，lock为写操作加锁，array数组被volatile修饰，通过volatile的语义 write happen-before read，使得在多线程场景下，一线程修改数组可立即通知其他线程数组已修改，获取最新值。
读操作一律没有加锁，所有的写操作加了锁，CopyOnWrite的思想也是在写操作中，故而只截取部分写操作的源码进行分析。
1、add(E e)添加元素
add 添加元素操作贯彻CopyOnWrite思想，先复制一份数组到新数组，将元素加到新数组，然后将新数组赋值给旧数组。
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(); }}
复制代码
2、add(int index, E element)在指定位置添加元素
如何在指定位置添加元素呢？通过index将原数组分成两半复制：
在index位置添加新元素，二次复制，相当于旧数组从index位开始元素纷纷向后移动一位。
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) // numMoved=0 即是在数组的最后加入element newElements = Arrays.copyOf(elements, len + 1); else { newElements = new Object[len + 1]; // elements 从0开始拷贝元素至 newElements（从0开始），length=index System.arraycopy(elements, 0, newElements, 0, index); // elements 从index开始拷贝元素至 newElements（从index+1开始），length=numMoved System.arraycopy(elements, index, newElements, index + 1, numMoved); } // newElements的index位置留给新元素element newElements[index] = element; // newElements 赋值给 旧数组array setArray(newElements); } finally { lock.unlock(); }}
复制代码
3、set(int index, E element)替换指定位置元素
public E set(int index, E element) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); E oldValue = get(elements, index);
// oldValue和element不相等，进行替换 if (oldValue != element) { int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len); newElements[index] = element; setArray(newElements); } else { // Not quite a no-op; ensures volatile write semantics // 二者相等，不是完全没有操作;确保volatile写语义，volatile write happen before read setArray(elements); } return oldValue; } finally { lock.unlock(); }}
复制代码
4、addIfAbsent(E e)添加元素时判断元素是否存在
addIfAbsent(E e)操作是两个操作，先判断数组中是否有新元素，有则返回 false 不添加，无则继续添加逻辑。添加逻辑是有锁线程安全的，而判断元素是否存在是不安全的，如何保证这两个操作加起来线程安全呢？答案是double check！
在单例模式-懒汉式中double check思想非常典型，先查该单例是否存在，存在直接返回，不存在，加锁，二次判断单例是否存在，存在则返回，不存在则新建赋值。
addIfAbsent(E e)运用了同样的思想：
首先获取原数组快照，判断新增元素是否存在，存在则返回 false。（first check）
新增元素不存在，则继续添加逻辑addIfAbsent(e, snapshot)。
addIfAbsent(e, snapshot)方法是加锁的，获取锁后首先判断当前数组和快照是否相等，相等则说明数组没有改动，可以直接进行新增元素的操作。如果有修改，则需要判断当前数组中是否有新增元素，有则返回 false，无则新增。（second check）
public boolean addIfAbsent(E e) { // 获取数组快照 Object[] snapshot = getArray(); return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : addIfAbsent(e, snapshot);}private boolean addIfAbsent(E e, Object[] snapshot) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] current = getArray(); int len = current.length; // 快照与当前数组比较，double-check， // 这里1.7和1.8不同，1.8对1.6进行了优化 // 看源码时需要对比不同版本的差异 if (snapshot != current) { // 数组可能已经被修改， // Optimize for lost race to another addXXX operation // remove common=len // add common=snapshot.length 先检查current中前snapshot.length个，然后检查新增的 int common = Math.min(snapshot.length, len); for (int i = 0; i < common; i++) if (current[i] != snapshot[i] && eq(e, current[i])) return false; if (indexOf(e, current, common, len) >= 0) return false; } Object[] newElements = Arrays.copyOf(current, len + 1); newElements[len] = e; setArray(newElements); return true; } finally { lock.unlock(); }}
复制代码
注意：java1.8 之前的addIfAbsent(E e)和 java8 之后的代码有些许不同，以下摘自 java7 源码，java7 中addIfAbsent(E e)并没有使用快照和double check的思想，而是直接将两个操作加锁，虽然保证了线程安全，但是因为方法一上来就加锁，性能比较。
所以 java8 中对其进行了优化，加了double check思想，第一次判断元素要是在数组中就不进行添加操作，也就不会加锁；而第二次判断，是先判断快照地址和当前数组地址，地址判断当然比遍历数组性能要高了。
public boolean addIfAbsent(E e) { final java.util.concurrent.locks.ReentrantLock lock = this.lock; lock.lock(); try { // Copy while checking if already present. // This wins in the most common case where it is not present Object[] elements = getArray(); int len = elements.length; Object[] newElements = new Object[len + 1]; for (int i = 0; i < len; ++i) { if (eq(e, elements[i])) return false; // exit, throwing away copy else newElements[i] = elements[i]; } newElements[len] = e; setArray(newElements); return true; } finally { lock.unlock(); }}
复制代码
5、remove(int index)删除指定位置元素
删除中间位置的元素，需要将 index 后面的元素前移填补空缺，同样使用分两半复制的方式达到删除元素并前移的效果。
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) // numMoved == 0 即是删除数组的最后一个元素，则不需要移动其他元素。 setArray(Arrays.copyOf(elements, len - 1)); else { // 新数组 length= len-1 Object[] newElements = new Object[len - 1]; System.arraycopy(elements, 0, newElements, 0, index); // 丢掉旧数组index位置的元素，达到删除的效果 System.arraycopy(elements, index + 1, newElements, index, numMoved); setArray(newElements); } return oldValue; } finally { lock.unlock(); }}
复制代码
6、remove(Object o)通过元素值删除元素
通过元素值删除元素，需要先查询数组中是否有该元素，无则不做操作，有则继续走删除逻辑，同样使用了double check的思想。
public boolean remove(Object o) { // 获取旧数组快照 Object[] snapshot = getArray(); // 判断需要删除的元素是否在数组中，不在则直接返回false，是则继续删除操作 int index = indexOf(o, snapshot, 0, snapshot.length); return (index < 0) ? false : remove(o, snapshot, index);}
private boolean remove(Object o, Object[] snapshot, int index) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] current = getArray(); int len = current.length; // double check // 快照与当前数组进行比较，不相等说明数组已经被其他线程修改 if (snapshot != current) findIndex: { int prefix = Math.min(index, len); // 遍历查找当前数组中是否有需要删除的元素 for (int i = 0; i < prefix; i++) { if (current[i] != snapshot[i] && eq(o, current[i])) { index = i; // 有则结束判断 break findIndex; } } // 上面找了一遍没有找到 // index >= len 说明上面查找的是当前整个数组，需要删除的元素已经被修改 if (index >= len) return false; // 当前数组变长了，current index位置的元素依然是需要删除的元素，停止判断 if (current[index] == o) break findIndex; // 走到这了数组变长了，index位置的元素也已经被删除，但是不代表其他线程新增的元素没有需要删除的元素，继续判断 index = indexOf(o, current, index, len); if (index < 0) return false; } // 新数组长度减一 Object[] newElements = new Object[len - 1]; // 从0开始复制旧数组index个元素到新数组的0至index-1位置 System.arraycopy(current, 0, newElements, 0, index); // 跳过index，从index+1复制旧数组剩下的元素到新数组的index至最后的位置。 System.arraycopy(current, index + 1, newElements, index, len - index - 1); // 新数组赋值给旧数组 setArray(newElements); return true; } finally { lock.unlock(); }}
复制代码
7、COWIterator 迭代器没有fail-fast检查
例如ArrayList在迭代器遍历想删除元素，只能使用迭代器的删除方法，而使用外部ArrayList删除方法会抛ConcurrentModificationException异常，为什么呢？
因为ArrayList成员变量维护了一个modCount，每次修改操作都会modCount++，而迭代器中也维护了一个expectedModCount，新建迭代器时modCount赋值给expectedModCount，在迭代器遍历时会检查modCount != expectedModCount，不相等则抛出ConcurrentModificationException，在迭代器遍历中调用迭代器外部的修改方法只会更新modCount，不会更新迭代器的expectedModCount，而迭代器内部提供的修改方法既更新了modCount，同时也将最新的modCount值赋值给expectedModCount。
然而这个限制在COWIterator中不存在！在使用COWIterator迭代器遍历时可以调用外部的修改方法，不会抛出异常。这是因为COWIterator迭代器中复制了一份原数组副本，外部修改数组只是修改了原数组，并不会影响迭代器中正在遍历的数组。
同时COWIterator迭代器也不支持调用迭代器内部的修改方法，全都会抛出UnsupportedOperationException。
如下摘取COWIterator部分源码：
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; /** * 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; }}
复制代码
既然COWIterator迭代器中遍历的数组是一个副本，修改原数组也不会影响到副本，这就出现一个问题：数据的实时一致性。
四、CopyOnWrite 利与弊
CopyOnWrite利用写时复制副本加锁修改，而读不加锁的思想达到读写分离的效果，以空间换时间，提升性能。而其弊端也正是其思想的体现：
缺陷决定了CopyOnWriteArrayList使用场景的局限性，CopyOnWriteArrayList适合读多写少，复制数据对象不宜过大的场景。
五、总结
CopyOnWrite是一个不错的解决并发安全的思路，在很多开源项目中都有用到类似复制写的思想。
CopyOnWrite利用写时复制副本加锁修改，而读不加锁的思想达到读写分离的效果，以空间换时间，提升性能。
CopyOnWrite缺陷明显，内存占用问题和数据一致性问题。
CopyOnWriteArrayList适合读多写少的场景。
addIfAbsent java8 中对 java7 做了优化，使用double check的思想保证线程安全。
COWIterator迭代器不支持调用迭代器内部修改方法，在COWIterator迭代器遍历时因为是遍历副本，所有调用外部修改方法也不会报错，但是也不会读取到最新值。
在使用CopyOnWriteArrayList添加、删除元素时，尽量使用addAll和removeAll批量新增和批量删除操作，因为频繁的复制数组降低性能，同时占用内存，可能会导致频繁 gc。
参考：
PS: 如若文章中有错误理解，欢迎批评指正，同时非常期待你的评论、点赞和收藏。我是徐同学，愿与你共同进步！
评论