前言
大家好，我是小彭。
在上一篇文章里，我们聊到了ArrayList 的线程安全问题，其中提到了 CopyOnWriteArrayList 的解决方法。那么 CopyOnWriteArrayList 是如何解决线程安全问题的，背后的设计思想是什么，今天我们就围绕这些问题展开。
本文源码基于 Java 8 CopyOnWriteArrayList。
小彭的 Android 交流群 02 群已经建立啦，扫描文末二维码进入~
。这显然太表面了。数组的长度限制是被虚拟机固化的，CopyOnWriteArrayList 没有限制的原因是：它没有做额外扩容，而且不适合大数据的场景，所以没有限制的必要。
最后还剩下 1 个问题：
- 疑问 1：为什么 array 字段要使用 volatile 关键字？
volatile 变量是 Java 轻量级的线程同步原语，volatile 变量的读取和写入操作中会加入内存屏障，能够保证变量写入的内存可见性，保证一个线程的写入能够被另一个线程观察到。
添加方法
// 在数组尾部添加元素
public boolean add(E e) {
final ReentrantLock lock = this.lock;
// 获取锁
lock.lock();
// 复制新数组
Object[] elements = getArray();
int len = elements.length;
// 疑问 4：在添加方法中，为什么扩容只增大 1 容量，而 ArrayList 会增大 1.5 倍？
Object[] newElements = Arrays.copyOf(elements, len + 1 /* 容量 + 1*/);
// 在新数组上添加元素
newElements[len] = e;
// 设置新数组
setArray(newElements);
// 释放锁
lock.unlock();
return true;
}
// 在数组尾部添加元素
public void add(int index, E element) {
// 原理相同，省略
...
}
// 批量在数组尾部添加元素
public boolean addAll(Collection<? extends E> c) {
// 原理相同，省略
...
}
修改方法
// 修改数组元素
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
// 获取锁
lock.lock();
// 旧元素
Object[] elements = getArray();
E oldValue = get(elements, index);
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
setArray(elements);
}
// 释放锁
lock.unlock();
// 返回旧数据
return oldValue;
}
删除方法
// 删除数组元素
public E remove(int index) {
final ReentrantLock lock = this.lock;
// 获取锁
lock.lock();
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);
}
// 释放锁
lock.unlock();
// 返回旧数据
return oldValue;
}
3.4 CopyOnWriteArrayList 的读取方法
可以看到读取方法并没有加锁。
private E get(Object[] a, int index) {
return (E) a[index];
}
public E get(int index) {
return get(getArray(), index);
}
public boolean contains(Object o) {
Object[] elements = getArray();
return indexOf(o, elements, 0, elements.length) >= 0;
}
3.5 CopyOnWriteArrayList 的迭代器
CopyOnWriteArrayList 的迭代器 COWIterator 是 “弱数据一致性的” ，所谓数据一致性问题讨论的是同一份数据在多个副本之间的一致性问题，你也可以理解为多个副本的状态一致性问题。例如内存与多核心 Cache 副本之间的一致性，或者数据在主从数据库之间的一致性。
为什么是 “弱” 的呢？这是因为 COWIterator 迭代器会持有 CopyOnWriteArrayList “底层数组” 的引用，而 CopyOnWriteArrayList 的写入操作是写入到新数组，因此 COWIterator 是无法感知到的，除非重新创建迭代器。
相较之下，ArrayList 的迭代器是通过持有 “外部类引用” 的方式访问 ArrayList 的底层数组，因此在 ArrayList 上的写入操作会实时被迭代器观察到。
CopyOnWriteArrayList.java
// 注意看：有 static 关键字，直接引用底层数组
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;
}
}
ArrayList.java
// 注意看：没有 static 关键字，通过外部类引用来访问底层数组
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
...
}
3.6 CopyOnWriteArraySet 的序列化过程
与 ArrayList 类似，CopyOnWriteArraySet 也重写了 JDK 序列化的逻辑，只把 elements 数组中有效元素的部分序列化，而不会序列化整个数组。
同时，ReentrantLock 对象是锁对象，序列化没有意义。在反序列化时，会通过 resetLock() 设置一个新的 ReentrantLock 对象。
// 序列化过程
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
s.defaultWriteObject();
Object[] elements = getArray();
// 写入数组长度
s.writeInt(elements.length);
// 写入有效元素
for (Object element : elements)
s.writeObject(element);
}
// 反序列化过程
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
// 设置 ReentrantLock 对象
resetLock();
// 读取数组长度
int len = s.readInt();
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, len);
// 创建底层数组
Object[] elements = new Object[len];
// 读取数组对象
for (int i = 0; i < len; i++)
elements[i] = s.readObject();
// 设置新数组
setArray(elements);
}
// 疑问 5：resetLock() 方法不好理解，解释一下？
private void resetLock() {
// 等价于带 Volatile 语义的 this.lock = new ReentrantLock()
UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
}
// Unsafe API
private static final sun.misc.Unsafe UNSAFE;
// lock 字段在对象实例数据中的偏移量
private static final long lockOffset;
static {
// 这三行的作用：lock 字段在对象实例数据中的偏移量
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class<?> k = CopyOnWriteArrayList.class;
lockOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("lock"));
}
小朋友又是有太多问号，举手提问 🙋🏻♀️：
- 🙋🏻♀️疑问 5：
resetLock()方法不好理解，解释一下？
在 static 代码块中，会使用 Unsafe API 获取 CopyOnWriteArrayList 的 “lock 字段在对象实例数据中的偏移量” 。由于字段的偏移是全局固定的，所以这个偏移量可以记录在 static 字段 lockOffset 中。
在 resetLock() 中，通过 UnSafe API putObjectVolatile 将新建的 ReentrantLock 对象设置到 CopyOnWriteArrayList 的 lock 字段中，等价于带 volatile 语义的 this.lock = new ReentrantLock()，保证这个字段的写入具备内存可见性。
字段的偏移量是什么意思呢？简单来说，普通对象和 Class 对象的实例数据区域是不同的：
- 1、普通对象： 包括当前类声明的实例字段以及父类声明的实例字段，不包括类的静态字段。UnSafe API objectFieldOffset(Filed) 就是获取了参数 Filed 在实例数据中的偏移量，后续就可以通过这个偏移量为字段赋值；
- 2、Class 对象： 包括当前类声明的静态字段和方法表等。
对象内存布局
3.7 CopyOnWriteArraySet 的 clone() 过程
CopyOnWriteArraySet 的 clone() 很巧妙。按照正常的思维，CopyOnWriteArraySet 中的 array 数组是引用类型，因此在 clone() 中需要实现深拷贝，否则原对象与克隆对象就会相互影响。但事实上，array 数组并没有被深拷贝，哇点解啊？
- 🙋🏻♀️疑问 6：为什么 array 数组没有深拷贝？
这就是因为 CopyOnWrite 啊！没有 Write 为什么要 Copy 呢？（我觉得已经提醒到位了，只要你仔细阅读前文对 CopyOnWrite 的论证，你一定会懂的。要是是在不懂，私信我吧~）
public Object clone() {
try {
@SuppressWarnings("unchecked")
// 疑问 6：为什么 array 数组没有深拷贝？
CopyOnWriteArrayList<E> clone = (CopyOnWriteArrayList<E>) super.clone();
// 设置 ReentrantLock 对象（相当于 lock 字段的深拷贝）
clone.resetLock();
return clone;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}
4. CopyOnWriteArraySet 源码分析
在 Java 标准库中，还提供了一个使用 COW 思想的 Set 集合 —— CopyOnWriteArraySet。
CopyOnWriteArraySet 和 HashSet 都是继承于 AbstractSet 的，但 CopyOnWriteArraySet 是基于 CopyOnWriteArrayList 动态数组的，并没有使用哈希思想。而 HashSet 是基于 HashMap 散列表的，能够实现 O(1) 查询。
4.1 CopyOnWriteArraySet 的构造方法
看一下 CopyOnWriteArraySet 的构造方法，底层就是有一个 CopyOnWriteArrayList 动态数组。
CopyOnWriteArraySet.java
public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable {
// 底层就是 OnWriteArrayList
private final CopyOnWriteArrayList<E> al;
// 无参构造方法
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
// 带集合的构造方法
public CopyOnWriteArraySet(Collection<? extends E> c) {
if (c.getClass() == CopyOnWriteArraySet.class) {
// 入参是 CopyOnWriteArraySet，说明是不重复的，直接添加
CopyOnWriteArraySet<E> cc = (CopyOnWriteArraySet<E>)c;
al = new CopyOnWriteArrayList<E>(cc.al);
}
else {
// 使用 addAllAbsent 添加不重复的元素
al = new CopyOnWriteArrayList<E>();
al.addAllAbsent(c);
}
}
public int size() {
return al.size();
}
}
4.2 CopyOnWriteArraySet 的操作方法
CopyOnWriteArraySet 的方法基本上都是交给 CopyOnWriteArraySet 代理的，由于没有使用哈希思想，所以操作的时间复杂度是 O(n)。
CopyOnWriteArraySet.java
public boolean add(E e) {
return al.addIfAbsent(e);
}
public boolean contains(Object o) {
return al.contains(o);
}
CopyOnWriteArrayList.java
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : addIfAbsent(e, snapshot);
}
public boolean contains(Object o) {
Object[] elements = getArray();
return indexOf(o, elements, 0, elements.length) >= 0;
}
// 通过线性扫描匹配元素位置，而不是计算哈希匹配，时间复杂度是 O(n)
private static int indexOf(Object o, Object[] elements, int index, int fence) {
if (o == null) {
for (int i = index; i < fence; i++)
if (elements[i] == null) return i;
} else {
for (int i = index; i < fence; i++)
if (o.equals(elements[i])) return i;
}
return -1;
}
5. 总结
1、CopyOnWriteArrayList 和 ArrayList 都是基于数组的动态数组，封装了操作数组时的搬运和扩容等逻辑；
2、CopyOnWriteArrayList 还是 “读写分离” 和 “写时复制” 的方案解决线程安全问题；
3、使用 CopyOnWriteArrayList 的场景一定要保证是 “读多写少” 且数据量不大的场景，而且在写入数据的时候，要做到批量操作；
4、CopyOnWriteArrayList 的迭代器是 “弱数据一致性的” 的，迭代器会持有 “底层数组” 的引用，而 CopyOnWriteArrayList 的写入操作是写入到新数组，因此迭代器是无法感知到的；
5、CopyOnWriteArraySet 是基于 CopyOnWriteArrayList 动态数组的，并没有使用哈希思想。