深入解析CopyOnWriteArrayList的工作机制
# 写在文章开头
在多线程编程中，确保数据结构的安全性和高效性是一个重要的挑战。Java 提供了多种并发工具和数据结构来帮助开发者应对这一挑战。其中，CopyOnWriteArrayList 是一个非常有用且高效的线程安全列表实现，所以本文将从案例实践和源码剖析的角度深度解读CopyOnWriteArrayList，希望对你有帮助。
Hi，我是 sharkChili ，是个不断在硬核技术上作死的技术人，是 CSDN的博客专家 ，也是开源项目 Java Guide 的维护者之一，熟悉 Java 也会一点 Go ，偶尔也会在 C源码 边缘徘徊。写过很多有意思的技术博客，也还在研究并输出技术的路上，希望我的文章对你有帮助，非常欢迎你关注我的公众号： 写代码的SharkChili 。
同时也非常欢迎你star我的开源项目mini-redis:https://github.com/shark-ctrl/mini-redis (opens new window)
因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。
# 详解java中有序集合的并发容器
# Vector如何实现线程安全
对于并发操作的有序集合容器，相信大部分都会想到非常传统的容器Vector，原因很简单，查看源码时我们非常直观的看到其针对任何读写操作都上了一把synchronized 锁：
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
public synchronized E set(int index, E element) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# synchronizedList如何保证线程安全
Collections.synchronizedList同理，只不过synchronizedList这个方法是针对原生数组的封装，通过方法内部上一把对象锁来保证线程安全：
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
2
3
4
5
6
# Vector和synchronizedList真的可以保证并发操作安全吗？
尽管Vector和synchronizedList都通过加锁的方式完成并发操作的互斥，但是他们真的安全嘛？如下代码所示，在遍历时进行集合清除操作，就会出现ConcurrentModificationException异常：
Vector<Integer> vector = new Vector<>();
vector.add(1);
vector.add(2);
vector.add(3);
vector.add(4);
vector.add(5);
//迭代期间一个并发线程清除元素
for (Integer item : vector) {
new Thread(vector::clear).start();
System.out.println(item);
}
2
3
4
5
6
7
8
9
10
11
# 为什么Vector加了synchronized之后在多线程操作下还会出现异常呢？
本质上这是一种fail-fast（快速失败）思想，即针对可能发生的异常进行提前表明故障的一种工作机制，我们都知道util包下的集合默认情况下是不支持线程安全的，所以JDK设计者为了能够提前感知并发操作失败并抛出异常，提出通过检查迭代期间修改次数是否变化来实现fail-fast，由此保证在避免在异常时执行非必要的复杂代码。
在多线程情况下，线程1进行并发修改操作，不断修改当前集合的modCount ，在这期间，另一个线程初始化一个迭代器进行遍历，这是就会出现expectedModCount会初始化为线程1某个操作阶段的modCount不等，进而触发fail-fast告知用户当前非线程安全容器存在线程安全问题，需要注意：
# cow思想——高并发线程安全的最佳解决方案
# 什么是cow思想，如何保证的线程安全
从CopyOnWriteArrayList源码中可知，COW即通过采用写时复制的思想，在迭代时的修改通过复制一份快照数组，并基于该数组完成并发修改操作，完成操作后再原子替换调原来的数组，由此保证线程安全，因为该操作涉及写时复制以及大数组的拷贝操作，这其中的开销还是蛮大的，一般情况下的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;
//array指向新的数组
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 什么是fail-fast和fail-safe
fail-fast（快速失败）思想即针对可能发生的异常进行提前表明故障的一种工作机制，我们都知道util包下的集合默认情况下是不支持线程安全的，所以JDK设计者为了能够提前感知并发操作失败并抛出异常，提出通过检查迭代期间修改次数是否变化来实现fail-fast，由此保证在避免在异常时执行非必要的复杂代码。
对应的我们给出下面这样一段在迭代时删除元素的源码，在第一轮遍历并删除元素后，这段代码就会抛出ConcurrentModificationException：
ArrayList<Integer> list = new ArrayList<>();
//添加几个元素
for (int i = 0; i < 100; i++) {
list.add(i);
}
//迭代时删除模拟并发操作
for (Integer i : list) {
list.remove(i);
}
2
3
4
5
6
7
8
9
10
从反编译后的代码可知，这段代码遍历本质上就是通过迭代器进行遍历：
public static void main(String[] args) throws InterruptedException {
ArrayList<Integer> list = new ArrayList();
for(int i = 0; i < 100; ++i) {
list.add(i);
}
//通过迭代器进行编译
Iterator var4 = list.iterator();
while(var4.hasNext()) {
Integer i = (Integer)var4.next();
list.remove(i);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
我们在初始化时插入了100个元素，此时对应的修改次数为100，随后我们开始了迭代，在第一轮迭代时，我们进行了元素删除操作，此时对应的修改次数就变为101。
随后foreach第2轮循环发现modCount 为101，与预期的expectedModCount(值为100因为初始化插入了元素100个)不等，判定为并发操作异常，于是便快速失败，抛出ConcurrentModificationException：
对此我们也给出迭代器获取下一个元素时的next方法，可以看到其内部的checkForComodification具有针对修改次数比对的逻辑：
public E next() {
//检查是否存在并发修改
checkForComodification();
//......
//返回下一个元素
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
//当前循环遍历次数和预期修改次数不一致时，就会抛出ConcurrentModificationException
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
而fail-safe也就是安全失败的含义，该思想常运用于并发容器，最经典的实现我就是CopyOnWriteArrayList的实现，通过写时复制的思想保证在进行修改操作时复制出一份快照，基于这份快照完成添加或者删除操作后，将CopyOnWriteArrayList底层的数组引用指向这个新的数组空间，由此避免迭代时抛出异常，当然这种做法也使得进行遍历操作时无法获得实时结果：
对应我们也给出CopyOnWriteArrayList实现fail-safe的核心代码，可以看到它的实现就是通过getArray获取数组引用然后通过Arrays.copyOf得到一个数组的快照，基于这个快照完成添加操作后，修改底层array变量指向的引用地址由此完成写时复制：
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;
//array指向新的数组
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 与传统集合的性能比对
与传统集合相比，CopyOnWriteArrayList更适合读多写少的情况，例如：黑名单、配置等相关集合。如下代码所示，我们就能看出写操作CopyOnWriteArrayList确实开销更大。且CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性：
long start = System.currentTimeMillis();
List<Integer> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
int loopCount = 10_0000;
//添加10w个元素到copyOnWriteArrayList
for (int i = 0; i < loopCount; i++) {
copyOnWriteArrayList.add(1);
}
long end = System.currentTimeMillis();
System.out.println(end - start);
//添加10w个元素到synchronizedList
start = System.currentTimeMillis();
List<Integer> synchronizedList = Collections.synchronizedList(new ArrayList<>());
for (int i = 0; i < loopCount; i++) {
synchronizedList.add(1);
}
end = System.currentTimeMillis();
System.out.println(end - start);
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
输出结果：
3813
4
2
# 关于我
我是 sharkchili ，CSDN Java 领域博客专家，mini-redis的作者，我想写一些有意思的东西，希望对你有帮助，如果你想实时收到我写的硬核的文章也欢迎你关注我的公众号： 写代码的SharkChili 。
同时也非常欢迎你star我的开源项目mini-redis:https://github.com/shark-ctrl/mini-redis (opens new window)
因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。
# 参考
写时复制(Copy-On-Write)思想在Java中的应用：https://mp.weixin.qq.com/s/XGq3IyoGITxZbZ4fxH7bag (opens new window)
fail-fast（快速失败）机制和fail-safe（安全失败）机制的介绍和区别:https://blog.csdn.net/striner/article/details/86375684 (opens new window)
