深入解析 CopyOnWriteArrayList 的工作機制
在多線程編程中，確保數(shù)據(jù)結(jié)構(gòu)的安全性和高效性是一個重要的挑戰(zhàn)。Java 提供了多種并發(fā)工具和數(shù)據(jù)結(jié)構(gòu)來幫助開發(fā)者應(yīng)對這一挑戰(zhàn)。其中，CopyOnWriteArrayList 是一個非常有用且高效的線程安全列表實現(xiàn)，所以本文將從案例實踐和源碼剖析的角度深度解讀CopyOnWriteArrayList，希望對你有幫助。
一、詳解Java中有序集合的并發(fā)容器
1.Vector如何實現(xiàn)線程安全
對于并發(fā)操作的有序集合容器，相信大部分都會想到非常傳統(tǒng)的容器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.synchronizedList如何保證線程安全
Collections.synchronizedList同理，只不過synchronizedList這個方法是針對原生數(shù)組的封裝，通過方法內(nèi)部上一把對象鎖來保證線程安全：
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);}
}3.Vector和synchronizedList真的可以保證并發(fā)操作安全嗎？
盡管Vector和synchronizedList都通過加鎖的方式完成并發(fā)操作的互斥，但是他們真的安全嘛？如下代碼所示，在遍歷時進行集合清除操作，就會出現(xiàn)ConcurrentModificationException異常：
Vector<Integer> vector = new Vector<>();
vector.add(1);
vector.add(2);
vector.add(3);
vector.add(4);
vector.add(5);
//迭代期間一個并發(fā)線程清除元素
for (Integer item : vector) {
new Thread(vector::clear).start();
System.out.println(item);
}4.為什么Vector加了synchronized之后在多線程操作下還會出現(xiàn)異常呢？
本質(zhì)上這是一種fail-fast（快速失敗）思想，即針對可能發(fā)生的異常進行提前表明故障的一種工作機制，我們都知道util包下的集合默認(rèn)情況下是不支持線程安全的，所以JDK設(shè)計者為了能夠提前感知并發(fā)操作失敗并拋出異常，提出通過檢查迭代期間修改次數(shù)是否變化來實現(xiàn)fail-fast，由此保證在避免在異常時執(zhí)行非必要的復(fù)雜代碼。
在多線程情況下，線程1進行并發(fā)修改操作，不斷修改當(dāng)前集合的modCount ，在這期間，另一個線程初始化一個迭代器進行遍歷，這是就會出現(xiàn)expectedModCount會初始化為線程1某個操作階段的modCount不等，進而觸發(fā)fail-fast告知用戶當(dāng)前非線程安全容器存在線程安全問題，需要注意：
二、cow思想——高并發(fā)線程安全的最佳解決方案
1.什么是cow思想，如何保證的線程安全
從CopyOnWriteArrayList源碼中可知，COW即通過采用寫時復(fù)制的思想，在迭代時的修改通過復(fù)制一份快照數(shù)組，并基于該數(shù)組完成并發(fā)修改操作，完成操作后再原子替換調(diào)原來的數(shù)組，由此保證線程安全，因為該操作涉及寫時復(fù)制以及大數(shù)組的拷貝操作，這其中的開銷還是蠻大的，一般情況下的CopyOnWriteArrayList更適用于一些讀多寫少的并發(fā)場景：
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
//獲取原有數(shù)組
Object[] elements = getArray();
int len = elements.length;
//基于原有數(shù)組復(fù)制出一份內(nèi)存快照
Object[] newElements = Arrays.copyOf(elements, len + 1);
//進行添加操作
newElements[len] = e;
//array指向新的數(shù)組
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}2.什么是fail-fast和fail-safe
fail-fast（快速失敗）思想即針對可能發(fā)生的異常進行提前表明故障的一種工作機制，我們都知道util包下的集合默認(rèn)情況下是不支持線程安全的，所以JDK設(shè)計者為了能夠提前感知并發(fā)操作失敗并拋出異常，提出通過檢查迭代期間修改次數(shù)是否變化來實現(xiàn)fail-fast，由此保證在避免在異常時執(zhí)行非必要的復(fù)雜代碼。
對應(yīng)的我們給出下面這樣一段在迭代時刪除元素的源碼，在第一輪遍歷并刪除元素后，這段代碼就會拋出ConcurrentModificationException：
ArrayList<Integer> list = new ArrayList<>();
//添加幾個元素
for (int i = 0; i < 100; i++) {
list.add(i);
}
//迭代時刪除模擬并發(fā)操作
for (Integer i : list) {
list.remove(i);
}從反編譯后的代碼可知，這段代碼遍歷本質(zhì)上就是通過迭代器進行遍歷：
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);
}
}我們在初始化時插入了100個元素，此時對應(yīng)的修改次數(shù)為100，隨后我們開始了迭代，在第一輪迭代時，我們進行了元素刪除操作，此時對應(yīng)的修改次數(shù)就變?yōu)?01。 隨后foreach第2輪循環(huán)發(fā)現(xiàn)modCount 為101，與預(yù)期的expectedModCount(值為100因為初始化插入了元素100個)不等，判定為并發(fā)操作異常，于是便快速失敗，拋出ConcurrentModificationException：
對此我們也給出迭代器獲取下一個元素時的next方法，可以看到其內(nèi)部的checkForComodification具有針對修改次數(shù)比對的邏輯：
public E next() {
//檢查是否存在并發(fā)修改
checkForComodification();
//......
//返回下一個元素
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
//當(dāng)前循環(huán)遍歷次數(shù)和預(yù)期修改次數(shù)不一致時，就會拋出ConcurrentModificationException
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}而fail-safe也就是安全失敗的含義，該思想常運用于并發(fā)容器，最經(jīng)典的實現(xiàn)我就是CopyOnWriteArrayList的實現(xiàn)，通過寫時復(fù)制的思想保證在進行修改操作時復(fù)制出一份快照，基于這份快照完成添加或者刪除操作后，將CopyOnWriteArrayList底層的數(shù)組引用指向這個新的數(shù)組空間，由此避免迭代時拋出異常，當(dāng)然這種做法也使得進行遍歷操作時無法獲得實時結(jié)果：
對應(yīng)我們也給出CopyOnWriteArrayList實現(xiàn)fail-safe的核心代碼，可以看到它的實現(xiàn)就是通過getArray獲取數(shù)組引用然后通過Arrays.copyOf得到一個數(shù)組的快照，基于這個快照完成添加操作后，修改底層array變量指向的引用地址由此完成寫時復(fù)制：
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
//獲取原有數(shù)組
Object[] elements = getArray();
int len = elements.length;
//基于原有數(shù)組復(fù)制出一份內(nèi)存快照
Object[] newElements = Arrays.copyOf(elements, len + 1);
//進行添加操作
newElements[len] = e;
//array指向新的數(shù)組
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}3.與傳統(tǒng)集合的性能比對
與傳統(tǒng)集合相比，CopyOnWriteArrayList更適合讀多寫少的情況，例如：黑名單、配置等相關(guān)集合。如下代碼所示，我們就能看出寫操作CopyOnWriteArrayList確實開銷更大。且CopyOnWrite容器只能保證數(shù)據(jù)的最終一致性，不能保證數(shù)據(jù)的實時一致性：
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);輸出結(jié)果：
3813
4
