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>