并發(fā)容器之CopyOnWriteArrayList

本人免費(fèi)整理了Java高級(jí)資料，涵蓋了Java、Redis、MongoDB、MySQL、Zookeeper、Spring Cloud、Dubbo高并發(fā)分布式等教程，一共30G，需要自己領(lǐng)取。
傳送門：https://mp.weixin.qq.com/s/JzddfH-7yNudmkjT0IRL8Q

1. CopyOnWriteArrayList的簡(jiǎn)介

Java學(xué)習(xí)者都清楚ArrayList并不是線程安全的，在讀線程在讀取ArrayList的時(shí)候如果有寫線程在寫數(shù)據(jù)的時(shí)候，基于fast-fail機(jī)制，會(huì)拋出ConcurrentModificationException異常，也就是說ArrayList并不是一個(gè)線程安全的容器，當(dāng)然您可以用Vector,或者使用Collections的靜態(tài)方法將ArrayList包裝成一個(gè)線程安全的類，但是這些方式都是采用java關(guān)鍵字synchronzied對(duì)方法進(jìn)行修飾，利用獨(dú)占式鎖來保證線程安全的。但是，由于獨(dú)占式鎖在同一時(shí)刻只有一個(gè)線程能夠獲取到對(duì)象監(jiān)視器，很顯然這種方式效率并不是太高。

回到業(yè)務(wù)場(chǎng)景中，有很多業(yè)務(wù)往往是讀多寫少的，比如系統(tǒng)配置的信息，除了在初始進(jìn)行系統(tǒng)配置的時(shí)候需要寫入數(shù)據(jù)，其他大部分時(shí)刻其他模塊之后對(duì)系統(tǒng)信息只需要進(jìn)行讀取，又比如白名單，黑名單等配置，只需要讀取名單配置然后檢測(cè)當(dāng)前用戶是否在該配置范圍以內(nèi)。

類似的還有很多業(yè)務(wù)場(chǎng)景，它們都是屬于讀多寫少的場(chǎng)景。如果在這種情況用到上述的方法，使用Vector,Collections轉(zhuǎn)換的這些方式是不合理的，因?yàn)楸M管多個(gè)讀線程從同一個(gè)數(shù)據(jù)容器中讀取數(shù)據(jù)，但是讀線程對(duì)數(shù)據(jù)容器的數(shù)據(jù)并不會(huì)發(fā)生發(fā)生修改。很自然而然的我們會(huì)聯(lián)想到ReenTrantReadWriteLock，通過讀寫分離的思想，使得讀讀之間不會(huì)阻塞，無疑如果一個(gè)list能夠做到被多個(gè)讀線程讀取的話，性能會(huì)大大提升不少。

但是，如果僅僅是將list通過讀寫鎖（ReentrantReadWriteLock）進(jìn)行再一次封裝的話，由于讀寫鎖的特性，當(dāng)寫鎖被寫線程獲取后，讀寫線程都會(huì)被阻塞。

如果僅僅使用讀寫鎖對(duì)list進(jìn)行封裝的話，這里仍然存在讀線程在讀數(shù)據(jù)的時(shí)候被阻塞的情況，如果想list的讀效率更高的話，這里就是我們的突破口，如果我們保證讀線程無論什么時(shí)候都不被阻塞，效率豈不是會(huì)更高？

Doug Lea大師就為我們提供CopyOnWriteArrayList容器可以保證線程安全，保證讀讀之間在任何時(shí)候都不會(huì)被阻塞，CopyOnWriteArrayList也被廣泛應(yīng)用于很多業(yè)務(wù)場(chǎng)景之中，CopyOnWriteArrayList值得被我們好好認(rèn)識(shí)一番。

2. COW的設(shè)計(jì)思想

回到上面所說的，如果簡(jiǎn)單的使用讀寫鎖的話，在寫鎖被獲取之后，讀寫線程被阻塞，只有當(dāng)寫鎖被釋放后讀線程才有機(jī)會(huì)獲取到鎖從而讀到最新的數(shù)據(jù)，站在讀線程的角度來看，即讀線程任何時(shí)候都是獲取到最新的數(shù)據(jù)，滿足數(shù)據(jù)實(shí)時(shí)性。既然我們說到要進(jìn)行優(yōu)化，必然有trade-off,我們就可以犧牲數(shù)據(jù)實(shí)時(shí)性滿足數(shù)據(jù)的最終一致性即可。而CopyOnWriteArrayList就是通過Copy-On-Write(COW)，即寫時(shí)復(fù)制的思想來通過延時(shí)更新的策略來實(shí)現(xiàn)數(shù)據(jù)的最終一致性，并且能夠保證讀線程間不阻塞。

COW通俗的理解是當(dāng)我們往一個(gè)容器添加元素的時(shí)候，不直接往當(dāng)前容器添加，而是先將當(dāng)前容器進(jìn)行Copy，復(fù)制出一個(gè)新的容器，然后新的容器里添加元素，添加完元素之后，再將原容器的引用指向新的容器。對(duì)CopyOnWrite容器進(jìn)行并發(fā)的讀的時(shí)候，不需要加鎖，因?yàn)楫?dāng)前容器不會(huì)添加任何元素。所以CopyOnWrite容器也是一種讀寫分離的思想，延時(shí)更新的策略是通過在寫的時(shí)候針對(duì)的是不同的數(shù)據(jù)容器來實(shí)現(xiàn)的，放棄數(shù)據(jù)實(shí)時(shí)性達(dá)到數(shù)據(jù)的最終一致性。

3. CopyOnWriteArrayList的實(shí)現(xiàn)原理

現(xiàn)在我們來通過看源碼的方式來理解CopyOnWriteArrayList，實(shí)際上CopyOnWriteArrayList內(nèi)部維護(hù)的就是一個(gè)數(shù)組

/**?The?array,?accessed?only?via?getArray/setArray.?*/
private?transient?volatile?Object[]?array;

并且該數(shù)組引用是被volatile修飾，注意這里僅僅是修飾的是數(shù)組引用，其中另有玄機(jī)，稍后揭曉。關(guān)于volatile很重要的一條性質(zhì)是它能夠夠保證可見性，關(guān)于volatile的詳細(xì)講解可以看。對(duì)list來說，我們自然而然最關(guān)心的就是讀寫的時(shí)候，分別為get和add方法的實(shí)現(xiàn)。

3.1 get方法實(shí)現(xiàn)原理

get方法的源碼為：

public?E?get(int?index)?{
????return?get(getArray(),?index);
}
/**
?*?Gets?the?array.??Non-private?so?as?to?also?be?accessible
?*?from?CopyOnWriteArraySet?class.
?*/
final?Object[]?getArray()?{
????return?array;
}
private?E?get(Object[]?a,?int?index)?{
????return?(E)?a[index];
}

可以看出來get方法實(shí)現(xiàn)非常簡(jiǎn)單，幾乎就是一個(gè)“單線程”程序，沒有對(duì)多線程添加任何的線程安全控制，也沒有加鎖也沒有CAS操作等等，原因是，所有的讀線程只是會(huì)讀取數(shù)據(jù)容器中的數(shù)據(jù)，并不會(huì)進(jìn)行修改。

3.2 add方法實(shí)現(xiàn)原理

再來看下如何進(jìn)行添加數(shù)據(jù)的？add方法的源碼為：

public?boolean?add(E?e)?{
????final?ReentrantLock?lock?=?this.lock;
????//1\.?使用Lock,保證寫線程在同一時(shí)刻只有一個(gè)
????lock.lock();
????try?{
????????//2\.?獲取舊數(shù)組引用
????????Object[]?elements?=?getArray();
????????int?len?=?elements.length;
????????//3\.?創(chuàng)建新的數(shù)組，并將舊數(shù)組的數(shù)據(jù)復(fù)制到新數(shù)組中
????????Object[]?newElements?=?Arrays.copyOf(elements,?len?+?1);
????????//4\.?往新數(shù)組中添加新的數(shù)據(jù)???????????
????????newElements[len]?=?e;
????????//5\.?將舊數(shù)組引用指向新的數(shù)組
????????setArray(newElements);
????????return?true;
????}?finally?{
????????lock.unlock();
????}
}

add方法的邏輯也比較容易理解，請(qǐng)看上面的注釋。需要注意這么幾點(diǎn)：

1. 采用ReentrantLock，保證同一時(shí)刻只有一個(gè)寫線程正在進(jìn)行數(shù)組的復(fù)制，否則的話內(nèi)存中會(huì)有多份被復(fù)制的數(shù)據(jù)；

2. 前面說過數(shù)組引用是volatile修飾的，因此將舊的數(shù)組引用指向新的數(shù)組，根據(jù)volatile的happens-before規(guī)則，寫線程對(duì)數(shù)組引用的修改對(duì)讀線程是可見的。

3. 由于在寫數(shù)據(jù)的時(shí)候，是在新的數(shù)組中插入數(shù)據(jù)的，從而保證讀寫實(shí)在兩個(gè)不同的數(shù)據(jù)容器中進(jìn)行操作。

4. 總結(jié)

我們知道COW和讀寫鎖都是通過讀寫分離的思想實(shí)現(xiàn)的，但兩者還是有些不同，可以進(jìn)行比較：

COW vs 讀寫鎖

相同點(diǎn)：1. 兩者都是通過讀寫分離的思想實(shí)現(xiàn)；2.讀線程間是互不阻塞的

不同點(diǎn)：對(duì)讀線程而言，為了實(shí)現(xiàn)數(shù)據(jù)實(shí)時(shí)性，在寫鎖被獲取后，讀線程會(huì)等待或者當(dāng)讀鎖被獲取后，寫線程會(huì)等待，從而解決“臟讀”等問題。也就是說如果使用讀寫鎖依然會(huì)出現(xiàn)讀線程阻塞等待的情況。而COW則完全放開了犧牲數(shù)據(jù)實(shí)時(shí)性而保證數(shù)據(jù)最終一致性，即讀線程對(duì)數(shù)據(jù)的更新是延時(shí)感知的，因此讀線程不會(huì)存在等待的情況。

對(duì)這一點(diǎn)從文字上還是很難理解，我們來通過debug看一下，add方法核心代碼為：

1.Object[]?elements?=?getArray();
2.int?len?=?elements.length;
3.Object[]?newElements?=?Arrays.copyOf(elements,?len?+?1);
4.newElements[len]?=?e;
5.setArray(newElements);

假設(shè)COW的變化如下圖所示：

數(shù)組中已有數(shù)據(jù)1,2,3，現(xiàn)在寫線程想往數(shù)組中添加數(shù)據(jù)4，我們?cè)诘?行處打上斷點(diǎn)，讓寫線程暫停。讀線程依然會(huì)“不受影響”的能從數(shù)組中讀取數(shù)據(jù)，可是還是只能讀到1,2,3。如果讀線程能夠立即讀到新添加的數(shù)據(jù)的話就叫做能保證數(shù)據(jù)實(shí)時(shí)性。當(dāng)對(duì)第5行的斷點(diǎn)放開后，讀線程才能感知到數(shù)據(jù)變化，讀到完整的數(shù)據(jù)1,2,3,4，而保證數(shù)據(jù)最終一致性，盡管有可能中間間隔了好幾秒才感知到。

這里還有這樣一個(gè)問題：?為什么需要復(fù)制呢？ 如果將array 數(shù)組設(shè)定為volitile的， 對(duì)volatile變量寫happens-before讀，讀線程不是能夠感知到volatile變量的變化。

原因是，這里volatile的修飾的僅僅只是數(shù)組引用，數(shù)組中的元素的修改是不能保證可見性的。因此COW采用的是新舊兩個(gè)數(shù)據(jù)容器，通過第5行代碼將數(shù)組引用指向新的數(shù)組。

這也是為什么concurrentHashMap只具有弱一致性的原因，關(guān)于concurrentHashMap的弱一致性可以。

COW的缺點(diǎn)

CopyOnWrite容器有很多優(yōu)點(diǎn)，但是同時(shí)也存在兩個(gè)問題，即內(nèi)存占用問題和數(shù)據(jù)一致性問題。所以在開發(fā)的時(shí)候需要注意一下。

1. 內(nèi)存占用問題：因?yàn)镃opyOnWrite的寫時(shí)復(fù)制機(jī)制，所以在進(jìn)行寫操作的時(shí)候，內(nèi)存里會(huì)同時(shí)駐扎兩個(gè)對(duì) 象的內(nèi)存，舊的對(duì)象和新寫入的對(duì)象（注意:在復(fù)制的時(shí)候只是復(fù)制容器里的引用，只是在寫的時(shí)候會(huì)創(chuàng)建新對(duì) 象添加到新容器里，而舊容器的對(duì)象還在使用，所以有兩份對(duì)象內(nèi)存）。如果這些對(duì)象占用的內(nèi)存比較大，比 如說200M左右，那么再寫入100M數(shù)據(jù)進(jìn)去，內(nèi)存就會(huì)占用300M，那么這個(gè)時(shí)候很有可能造成頻繁的minor GC和major GC。

2. 數(shù)據(jù)一致性問題：CopyOnWrite容器只能保證數(shù)據(jù)的最終一致性，不能保證數(shù)據(jù)的實(shí)時(shí)一致性。所以如果你希望寫入的的數(shù)據(jù)，馬上能讀到，請(qǐng)不要使用CopyOnWrite容器。