CopyOnWriteArrayList 是如何保證執行緒安全的？

本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 提問。

前言

大家好，我是小彭。

在上一篇文章裡，我們聊到了ArrayList 的執行緒安全問題，其中提到了 CopyOnWriteArrayList 的解決方法。那麼 CopyOnWriteArrayList 是如何解決執行緒安全問題的，背後的設計思想是什麼，今天我們就圍繞這些問題展開。

本文原始碼基於 Java 8 CopyOnWriteArrayList。

小彭的 Android 交流群 02 群已經建立啦，掃描文末二維條碼進入~

思維導圖：

1. 回顧 ArrayList

ArrayList 是基於陣列實現的動態資料，是執行緒不安全的。例如，我們在遍歷 ArrayList 的時候，如果其他執行緒並行修改陣列（當然也不一定是被其他執行緒修改），在迭代器中就會觸發 fail-fast 機制，丟擲 ConcurrentModificationException 異常。

範例程式

List<String> list = new ArrayList();
list.add("xiao");
list.add("peng");
list.add(".");

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    // 可能丟擲 ConcurrentModificationException 異常
    iterator.next();
}

要實現執行緒安全有 3 種方式：

方法 1 - 使用 Vector 容器： Vector 是執行緒安全版本的陣列容器，它會在所有方法上增加 synchronized 關鍵字（過時，瞭解即可）；
方法 2 - 使用 Collections.synchronizedList 包裝類
方法 3 - 使用 CopyOnWriteArrayList 容器

Collections.synchronizedList 包裝類的原理很簡單，就是使用 synchronized 加鎖，原始碼摘要如下：

Collections.java

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}

// 使用 synchronized 實現執行緒安全
static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> {
    final List<E> list;

    public boolean equals(Object o) {
        if (this == o) return true;
        synchronized (mutex) {return list.equals(o);}
    }
    public int hashCode() {
        synchronized (mutex) {return list.hashCode();}
    }

    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);}
    }
    public void add(int index, E element) {
        synchronized (mutex) {list.add(index, element);}
    }
    public E remove(int index) {
        synchronized (mutex) {return list.remove(index);}
    }
		...
}

如果我們將 ArrayList 替換為 CopyOnWriteArrayList，即使其他執行緒並行修改陣列，也不會丟擲 ConcurrentModificationException 異常，這是為什麼呢？

2. CopyOnWriteArrayList 的特點

CopyOnWriteArrayList 和 ArrayList 都是基於陣列的動態陣列，封裝了運算元組時的搬運和擴容等邏輯。除此之外，CopyOnWriteArrayList 還是用了基於加鎖的「讀寫分離」和「寫時複製」的方案解決執行緒安全問題：

思想 1 - 讀寫分離（Read/Write Splitting）： 將對資源的讀取和寫入操作分離，使得讀取和寫入沒有依賴，在「讀多寫少」的場景中能有效減少資源競爭；
思想 2 - 寫時複製（CopyOnWrite，COW）： 在寫入資料時，不直接在原資料上修改，而是複製一份新資料後寫入到新資料，最後再替換到原資料的參照上。這個特性各有優缺點：
- 優點 1 - 延遲處理： 在沒有寫入操作時不會複製 / 分配資源，能夠避免瞬時的資源消耗。例如作業系統的 fork 操作也是一種寫時複製的思想；
- 優點 2 - 降低鎖顆粒度： 在寫的過程中，讀操作不會被影響，讀操作也不需要加鎖，鎖的顆粒度從整個列表降低為寫操作；
- 缺點 1 - 弱資料一致性： 在讀的過程中，如果資料被其他執行緒修改，是無法實時感知到最新的資料變化的；
- 缺點 2 - 有記憶體壓力： 在寫操作中需要複製原陣列，在複製的過程中記憶體會同時存在兩個陣列物件（只是參照，陣列元素的物件還是隻有一份），會帶來記憶體佔用和垃圾回收的壓力。如果是「寫多讀少」的場景，就不適合。

所以，使用 CopyOnWriteArrayList 的場景一定要保證是「讀多寫少」且資料量不大的場景，而且在寫入資料的時候，要做到批次操作。否則每個寫入操作都會觸發一次複製，想想就可怕。舉 2 個例子：

例如批次寫入一組資料，要使用 addAll 方法批次寫入；
例如在做排序時，要先輸出為 ArrayList，在 ArrayList 上完成排序後再寫回 CopyOnWriteArrayList。

3. CopyOnWriteArrayList 原始碼分析

這一節，我們來分析 CopyOnWriteArrayList 中主要流程的原始碼。

3.1 CopyOnWriteArrayList 的屬性

ArrayList 的屬性很好理解，底層是一個 Object 陣列，我要舉手提問