CopyOnWriteArrayList 寫時複製原理分析

寫時複製的基本原理

通過空間換時間,分離了對數據的讀和寫操作,併發讀操作不受寫操作的影響,提高併發讀性能。

寫時複製的缺點

內存空間耗費

典型的空間換時間策略,寫操作時會對原來數據區進行復制,必然會額外的耗費內存空間。

不是強一致性

由於內存空間拷貝機制的存在,讀操作讀取的是原數據,寫操作寫的是新拷貝的數據,因此,二者之間會有數據不一致的可能,但隨著寫操作執行完成,達到最終一致。

CopyOnWriteArrayList 實現原理分析

<code>// JDK實現類:java.util.concurrent.CopyOnWriteArrayList // 控制併發寫入的鎖對象 final transient ReentrantLock lock = new ReentrantLock(); // 數組,對象持有容器 // 通過volatile修飾,保證對array變量的修改的可見性和有序性 private transient volatile Object[] array;/<code>

對CopyOnWriteArrayList寫入原理類似,基本上遵循如下步驟:

獲取寫鎖:通過ReentrantLock進行併發寫入的同步根據操作拷貝原數組以生成新數組:Arrays.copyOf(......) 對新數組執行操作將新數組引用賦值給類中定義的
array變量釋放鎖

以CopyOnWriteArrayList.add(E e)方法為例,參考如下代碼和註釋。

<code>// 新增元素 public boolean add(E e) {     final ReentrantLock lock = this.lock;     // 寫操作,先加鎖     lock.lock();     try {         // 獲取舊對象數組引用         Object[] elements = getArray();         int len = elements.length;         // 拷貝新的數組,因為是添加一個元素,所以數組長度為 len + 1         Object[] newElements = Arrays.copyOf(elements, len + 1);         newElements[len] = e;         // 將array變量賦值為newElements         setArray(newElements);         return true;     } finally {         // 最後釋放鎖         lock.unlock();     } } // 數組引用直接賦值 final void setArray(Object[] a) {     array = a; } // 底層數組拷貝實現 public static native void arraycopy(Object src,  int  srcPos,          Object dest, int destPos, int length);/<code>

數據弱一致性問題

CopyOnWriteArrayList實現策略:併發寫加同步,併發讀無鎖。那麼,在併發寫入的同時,如果發生讀會產生數據不一致嗎?

從源碼可以看出,寫操作基於新生成的拷貝數組,讀操作基於原始數組。寫操作通過鎖機制進行同步,將併發寫串行化,所以併發寫入不會存在問題。對於讀而言,讀操作基於原有數組引用進行,讀取的任然是原數組中的數據,有點像數據的快照。因此,讀寫之間存在一定的數據不一致可能。

底層拷貝邏輯的實現

底層通過調用Arrays.copyOf()實現數組拷貝,參考如下源碼。需要注意的是,如果數組中存儲的是對象,則是引用拷貝。

<code>// java.util.Arrays public static int[] copyOf(int[] original, int newLength) {     int[] copy = new int[newLength];     System.arraycopy(original, 0, copy, 0,                      Math.min(original.length, newLength));     return copy; }/<code>