深入理解 JUC:CopyOnWriteArrayList

CopyOnWriteArrayList 是线程安全的 List 实现,底层依赖于数组作为存储结构,并基于 写时复制(CoW: Copy-on-Write)机制 保证线程安全性。CopyOnWriteArrayList 在执行修改操作时会将底层数组复制一份,并在副本上实施修改,最后再更新回底层数组。虽然这样的实现比较消耗内存,但却带来了较高的执行效率,属于拿空间换时间。

除了 CopyOnWriteArrayList,在 JUC 包中还有另外一个基于 CoW 机制实现的线程安全组件,即 CopyOnWriteArraySet,不过 CopyOnWriteArraySet 本质上还是基于 CopyOnWriteArrayList 实现的,所以理解了 CopyOnWriteArrayList 的实现机制,也就同时理解了 CopyOnWriteArraySet 的实现机制。

CopyOnWriteArrayList 实现内幕

CopyOnWriteArrayList 实现自 List 接口,所以我们可以像使用 ArrayList 一样使用 CopyOnWriteArrayList。CopyOnWriteArrayList 类的字段定义如下:

1
2
3
4
5
6
7
8
9
10
public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, Serializable {

/** 支撑同步操作的重入锁 */
final transient ReentrantLock lock = new ReentrantLock();
/** 底层数组 */
private transient volatile Object[] array;

// ... 省略方法定义

}

其中 CopyOnWriteArrayList#array 数组是 CopyOnWriteArrayList 的底层存储结构,CopyOnWriteArrayList 依赖于该数组对数据进行存储。字段 CopyOnWriteArrayList#lock 对应 ReentrantLock 类型,用于控制多个线程对底层数组的修改操作,保证同一时间只有一个线程对底层数组进行修改。CopyOnWriteArrayList 提供了相应的 CopyOnWriteArrayList#getArrayCopyOnWriteArrayList#setArray 方法用于访问该字段。

CopyOnWriteArrayList 定义了多个重载的构造方法来初始化构造一个 CopyOnWriteArrayList 对象,实现上比较简单,这里不再展开。下面重点来看一下 CopyOnWriteArrayList 之于 List 接口中声明的核心方法实现,即增(add)、删(remove)、改(set)、查(get)操作。

首先来看一下 添加元素 的操作,CopyOnWriteArrayList 定义了多个重载版本的 CopyOnWriteArrayList#add 的方法实现,包括:

  • CopyOnWriteArrayList#add(E)
  • CopyOnWriteArrayList#add(int, E)
  • CopyOnWriteArrayList#addIfAbsent(E)
  • CopyOnWriteArrayList#addAll(Collection<? extends E>)
  • CopyOnWriteArrayList#addAll(int, Collection<? extends E>)
  • CopyOnWriteArrayList#addAllAbsent

这些方法在实现上思想都是想通的,下面以 CopyOnWriteArrayList#add(E) 方法为例分析往 CopyOnWriteArrayList 中添加元素的运行机制,方法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean add(E e) {
final ReentrantLock lock = this.lock;
// 加锁,保证同一时间只有一个线程修改底层数组
lock.lock();
try {
// 获取底层数组
Object[] elements = this.getArray();
int len = elements.length;
// 复制出一份新的数组,长度加 1,以容纳待添加的元素
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
// 更新底层数组
this.setArray(newElements);
return true;
} finally {
// 释放锁
lock.unlock();
}
}

前面我们已经提及到 CopyOnWriteArrayList 对于数据的修改都是在副本上进行的,上述方法的实现印证了这一点。当往 CopyOnWriteArrayList 中添加一个元素时,方法的执行流程如下:

  1. 获取锁对象,保证同一时间只有一个线程在执行修改操作;
  2. 获取底层数组,基于该数组拷贝出一个新的数组,新数组长度加 1;
  3. 追加待添加元素到新数组的末尾位置,并更新底层数组;
  4. 释放锁对象。

再来看一下 获取元素 的操作,CopyOnWriteArrayList 仅定义了一个 CopyOnWriteArrayList#get 方法,用于获取指定下标的元素值,实现如下:

1
2
3
4
5
6
7
8
public E get(int index) {
// 直接返回底层数组 index 下标的元素
return this.get(this.getArray(), index);
}

private E get(Object[] a, int index) {
return (E) a[index];
}

实现上比较简单,没什么可说的,这里主要强调一下弱一致性问题,也就说 get 操作不一定能够返回最新的值。考虑这样一个场景,假设有线程 A 和 B,其中 A 调用 get 方法获取数据,B 调用 add 方法添加数据,当前数组长度为 5:

  1. 线程 B 获取底层数组 x,然后拷贝出一个长度为 6 的新数组 y,并将待追加的元素设置到 y[5] 的位置,此时还未更新底层数组;
  2. 因为读操作无需获取锁,如果此时线程 A 尝试获取下标为 5 的元素,则会抛出 IndexOutOfBoundsException,因为此时 A 获取到的底层数组还是 x,还没有更新成 y。

然而,大部分时候这种弱一致性并不会对我们的业务造成影响,但是我们需要知道其存在,以便在发生错误时快速定位问题。

继续来看一下 修改元素 的操作,CopyOnWriteArrayList 同样仅定义了一个 CopyOnWriteArrayList#set 方法,用于修改指定下标的元素值,实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
// 获取锁
lock.lock();
try {
// 获取底层数组
Object[] elements = this.getArray();
// 获取数组 index 下标值
E oldValue = this.get(elements, index);
// 待更新的元素值与数组中指定位置的元素值不同
if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
// 更新 index 位置的元素值
newElements[index] = element;
// 更新底层数组
this.setArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
// 待更新的元素值与数组中指定位置的元素值相同,无需执行更新操作
this.setArray(elements); // 保证 volatile 写语义
}
return oldValue;
} finally {
// 释放锁
lock.unlock();
}
}

上述方法的执行逻辑如代码注释,比较简单,但是当修改的目标元素值前后未发生变化时还是会调用 CopyOnWriteArrayList#setArray 方法更新一下底层数组,用意何在呢?

代码中给出的理由是 Not quite a no-op; ensures volatile write semantics,也就是说这里的更新操作不完全是一个无意义的操作,可以用来保证 volatile 的写语义,因为底层数组 array 是 volatile 类型。要理解其用意,可以参考 《深入理解 java 内存模型》一书中的示例(稍作修改):

1
2
3
4
5
6
7
8
9
10
11
12
13
private int a = 0;
private volatile boolean flag = true;

public void writer() {
a = 1; // 1
flag = true; // 2
}

public void reader() {
if (flag) { // 3
int i = a; // 4
}
}

假设线程 A 执行 writer 方法之后,线程 B 执行 reader 方法。根据 happens-before 原则,这个过程建立的 happens-before 关系为:

  1. 根据程序次序规则,1 happens before 2; 3 happens before 4。
  2. 根据 volatile 规则,2 happens before 3。
  3. 根据 happens before 的传递性规则,1 happens before 4。

这样就能保证线程 B 在 reader 方法中读取 a 变量时能够看见线程 A 在 writer 方法中对 a 的修改,即使在 writer 方法中对变量 flag 的修改同样看似多余。

最后来看一下 删除元素 的操作,CopyOnWriteArrayList 针对删除操作定义了多个重载版本的 CopyOnWriteArrayList#remove 的方法实现,包括:

  • CopyOnWriteArrayList#remove(int)
  • CopyOnWriteArrayList#remove(java.lang.Object)
  • CopyOnWriteArrayList#removeAll
  • CopyOnWriteArrayList#removeIf

下面以 CopyOnWriteArrayList#remove(int) 方法为例分析从 CopyOnWriteArrayList 中删除元素的运行机制,方法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public E remove(int index) {
final ReentrantLock lock = this.lock;
// 获取锁
lock.lock();
try {
// 获取底层数组
Object[] elements = this.getArray();
int len = elements.length;
// 获取指定下标元素
E oldValue = this.get(elements, index);
int numMoved = len - index - 1;
// 如果是删除最后一个元素,则直接 copy 即可,无需移动
if (numMoved == 0) {
this.setArray(Arrays.copyOf(elements, len - 1));
} else {
// 否则,分两次进行拷贝,去掉原 index 下标的元素
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index, numMoved);
this.setArray(newElements);
}
return oldValue;
} finally {
// 释放锁
lock.unlock();
}
}

删除的逻辑本质上还是在副本上进行,如上述代码注释,其过程与前面分析的操作类似。

除了上面分析的核心操作方法,CopyOnWriteArrayList 还实现了 CopyOnWriteArrayList#iterator 方法返回一个迭代器,实现如下:

1
2
3
public Iterator<E> iterator() {
return new COWIterator<E>(this.getArray(), 0);
}

关于 COWIterator 的实现不再继续深入,但是需要知晓的一点是,COWIterator 不支持在迭代过程中修改 CopyOnWriteArrayList 中的元素,对应的 COWIterator#removeCOWIterator#setCOWIterator#add 方法均直接抛出 UnsupportedOperationException 异常。此外,方法 CopyOnWriteArrayList#iterator 返回的是一个弱一致性迭代器,即在迭代期间,其它线程对于底层数组的修改并不会被迭代器看见。

总结

本文分析了 CopyOnWriteArrayList 的设计与实现,CopyOnWriteArrayList 对于数据的修改操作均在副本上完成,并基于 ReentrantLock 保证同一时间只有一个线程能够对底层数组执行修改操作。线程在读取 CopyOnWriteArrayList 时都是拿到底层数组的一个最新快照,并在快照上执行读取操作,所以期间的修改结果对于读操作是不可见的,这也就导致了读写的弱一致性。但是对于读多写少的场景来说,CopyOnWriteArrayList 能够在保证线程安全的同时媲美 ArrayList 的性能。

参考

  1. JDK 1.8 源码
  2. 深入理解 java 内存模型

转载声明 : 版权所有,商业转载请联系作者,非商业转载请注明出处
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议
Powered by hexo & Theme by hiero   Copyright © 2015-2019 浙ICP备 16010916  号,指 · 间 All Rights Reserved.