詳解CopyOnWrite容器及其源碼 在jave.util.concurrent包下有這樣兩個類:CopyOnWriteArrayList和CopyOnWriteArraySet。 其中利用到了CopyOnWrite機制,本篇就來聊聊CopyOnWrite技術與Java中的CopyOnWrite容... ...
詳解CopyOnWrite容器及其源碼
在jave.util.concurrent
包下有這樣兩個類:CopyOnWriteArrayList
和CopyOnWriteArraySet
。
其中利用到了CopyOnWrite機制,本篇就來聊聊CopyOnWrite技術與Java中的CopyOnWrite容器。
主要包擴以下內容:
- 什麼是CopyOnWrite
- CopyOnWriteArrayList
- CopyOnWriteArraySet
- CopyOnWrite適用場景
什麼是CopyOnWrite
對於一般的容器,比如ArrayList,在進行併發操作時,如果一個線程讀,一個線程寫,會拋出java.util.ConcurrentModificationException異常。而CopyOnWrite容器則避免了這種情況。
CopyOnWrite,顧名思義,寫時複製,在修改集合中數據的時候,不直接修改當前容器,而是先將當前容器進行拷貝,複製出一個新的容器,然後在新的容器里完成修改,再將原容器的引用指向新的容器。
這樣做的好處是,可以不通過加鎖,實現對CopyOnWrite容器的併發讀寫。需要註意的是,CopyOnWrite技術並不保證實時一致性,因為在讀寫並行時,有可能會讀到過期的數據。CopyOnWrite技術保證的是最終一致性。
CopyOnWriteArrayList
CopyOnWriteArrayList的底層是通過數組來實現的,其包含兩個屬性:
1
|
final transient ReentrantLock lock = new ReentrantLock();
|
前者用於在對CopyOnWriteArrayList進行修改時加鎖,後者用於保存容器中的元素(允許null元素),對array加了volatile關鍵字,保證每次修改容器的時候對其他線程都是可見的。
在其各種介面的實現中,用的最多的是如下兩個方法:
1
|
final Object[] getArray() {
|
getArray()
方法返回當前數組,而setArray()
方法用於在CopyOnWriteArrayList變化時,將array執行修改後的數組記憶體地址。
CopyOnWriteArrayList提供了三種構造函數:
1
|
CopyOnWriteArrayList(); // 創建一個array長度為0的CopyOnWriteArrayList
|
根據實際的需要創建即可。
CopyOnWriteArrayList提供的讀方法與數組的讀方法並無什麼大的不同,因為CopyOnWriteArrayList本身解決的問題就不是讀讀併發的問題,所以重一下其寫方法。
首先看一下set()
方法,set()
方法為指定位置設置特定值,如下是其實現:
1
|
public E set(int index, E element) {
|
分別看一下以上代碼中的關鍵幾步:
- 可以看到CopyOnWriteArrayList為了保證在複製原容器時是加了一個可重入鎖的,在set完成後釋放該鎖;
- 獲取當前的數組;
- 判斷要設置的位置的舊值與新值是否相同,如果相同則免去容器的拷貝工作;
- 將原容器複製一份;
- 修改該處的值為新值;
- 重新創建CopyOnWriteArrayList容器,將舊容器的記憶體地址改為新容器所在記憶體地址;
- 完成set,釋放鎖。
再看一下add()
方法,向容器中添加一個元素,如下是其源碼:1
2
3
4
5
6
7
8
9
10
11
12
13
14public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock(); // 1
try {
Object[] elements = getArray(); // 2
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1); // 3
newElements[len] = e; // 4
setArray(newElements); // 5
return true;
} finally {
lock.unlock();
}
}
add操作與set操作的大體過程都是相同的,多了兩步的是,給新元素新增空間,即3~4步。
上面的add()
方法是在容器最後添加一個元素,如果是在指定位置添加一個元素呢,源碼如下:
1
|
public void add(int index, E element) {
|
add(int index, E element)相比於add(E e)又多了數組元素移位的過程,即3~10步。移位的時候用到了System.arraycopy()方法,以第9步為例,其意為將elements數組從0開始的index個元素拷貝到newElements數組的從0開始的位置上。System.arraycopy()是一個native方法,用於保證每次add操作對數組移位時的性能不至於太差。
那麼從容器中移除一個元素呢,請看其remove()
方法源碼:
1
|
public E remove(int index) {
|
remove(index)方法的實現與add(index, element) 方法的實現是類似的,區別在於前者是數組縮小。
除此之外,還提供了remove(Object o)方法用於移除特定值,remove(Object o, Object[] snapshot, int index)方法用於移除特定版本數組下的特定值,且前者的實現是以後者為基礎的,故而前者在自己的實現中沒有加鎖。這裡僅拿出第三個remove方法的源碼來作分析:
1
|
private boolean remove(Object o, Object[] snapshot, int index) {
|
這個remove方法給定要刪除的值和一個數組,以及結束的位置。這個snapshot數組可以認為是某一個版本的array數組,當二者相同時,remove方法和remove(o)就幾乎一樣了;當二者不同時,即3、4步,則是記錄當前數組中與要刪除的值相同的那個元素的位置,此時說明snapshot數組已經修改過了,所以相同位置的那個元素已經不同了。
以上是CopyOnWriteArrayList的源碼中重要屬性和函數的實現剖析。
CopyOnWriteArraySet
瞭解了CopyOnWriteArrayList的實現之後,CopyOnWriteArraySet的實現就比較簡單了,看一眼CopyOnWriteArraySet保存元素的結構就知道為何了:
1
|
private final CopyOnWriteArrayList<E> al;
|
可以看到CopyOnWriteArraySet的實現是基於CopyOnWriteArrayList來做的,CopyOnWriteArraySet提供的各種方法也都是通過CopyOnWriteArrayList來實現,原理基本相同,就不單獨詳細說明瞭。
CopyOnWrite適用場景
考慮到每次CopyOnWrite容器進行修改的時候都需要加鎖和對容器進行拷貝,寫的性能開銷較大,所以更適合使用在讀操作遠遠大於寫操作的場景里,比如緩存、搜索引擎對某些關鍵詞過濾使用的黑名單等。發生修改時候做copy,新老版本分離,保證讀的高性能,適用於以讀為主的情況。
因為CopyOnWrite容器只能保證最終一致性,所以不適用於對數據實時性要求較高的場景中,因為一個線程修改了數據,其他線程並不一定能夠馬上讀取到新的數據。