博客 / 詳情

返回

CopyOnWriteArrayList：寫時複製機制與高效併發訪問

前言

Vector無論是add方法還是get方法都加上了synchronized修飾，當多線程讀寫List必須排隊執行，很顯然這樣效率比較是低下的，CopyOnWriteArrayList是讀寫分離的，好處是提高線程訪問效率。

CopyOnWrite容器即寫時複製的容器。通俗的理解是當往一個容器添加元素的時候，不直接往當前容器添加，而是先將當前容器裏的值Copy到新的容器，然後再往新的容器裏添加元素，添加完元素之後，再將原容器的引用指向新的容器。這樣做的好處是我們可以對CopyOnWrite容器進行併發的讀 要加鎖，因為當前容器不會添加任何元素。所以CopyOnWrite容器也是一種讀寫分離的思想，讀和寫不同的容器。

底層原理

  1. CopyOnWriteArrayList的動態數組機制 -- 它內部有個volatile數組(array)來保持數據。在“添加/刪除”數據時，都會新建一個數組，並將更新後的數據拷貝到新建的數組中，最後再將該數組賦值給volatile數組。這就是它叫做CopyOnWriteArrayList的原因！
  2. 每一個CopyOnWriteArrayList都和一個監視器鎖lock綁定，通過lock，實現了對CopyOnWriteArrayList的互斥添加/刪除。

類的繼承關係

CopyOnWriteArrayList實現了List接口，List接口定義了對列表的基本操作；同時實現了RandomAccess接口，表示可以隨機訪問(數組具有隨機訪問的特性)；同時實現了Cloneable接口，表示可克隆；同時也實現了Serializable接口，表示可被序列化。

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

類的內部類

  • COWIterator類

COWIterator表示迭代器，其也有一個Object類型的數組作為CopyOnWriteArrayList數組的快照，這種快照風格的迭代器方法在創建迭代器時使用了對當時數組狀態的引用。此數組在迭代器的生存期內不會更改，因此不可能發生衝突，並且迭代器保證不會拋出 ConcurrentModificationException。創建迭代器以後，迭代器就不會反映列表的添加、移除或者更改。在迭代器上進行的元素更改操作(remove、set 和 add)不受支持。這些方法將拋出 UnsupportedOperationException。

static final class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array */
    // 快照
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    // 遊標
    private int cursor;
    // 構造函數
    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }
    // 是否還有下一項
    public boolean hasNext() {
        return cursor < snapshot.length;
    }
    // 是否有上一項
    public boolean hasPrevious() {
        return cursor > 0;
    }
    // next項
    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext()) // 不存在下一項，拋出異常
            throw new NoSuchElementException();
        // 返回下一項
        return (E) snapshot[cursor++];
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        if (! hasPrevious())
            throw new NoSuchElementException();
        return (E) snapshot[--cursor];
    }
    
    // 下一項索引
    public int nextIndex() {
        return cursor;
    }
    
    // 上一項索引
    public int previousIndex() {
        return cursor-1;
    }

    /**
        * Not supported. Always throws UnsupportedOperationException.
        * @throws UnsupportedOperationException always; {@code remove}
        *         is not supported by this iterator.
        */
    // 不支持remove操作
    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
        * Not supported. Always throws UnsupportedOperationException.
        * @throws UnsupportedOperationException always; {@code set}
        *         is not supported by this iterator.
        */
    // 不支持set操作
    public void set(E e) {
        throw new UnsupportedOperationException();
    }

    /**
        * Not supported. Always throws UnsupportedOperationException.
        * @throws UnsupportedOperationException always; {@code add}
        *         is not supported by this iterator.
        */
    // 不支持add操作
    public void add(E e) {
        throw new UnsupportedOperationException();
    }

    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        Object[] elements = snapshot;
        final int size = elements.length;
        for (int i = cursor; i < size; i++) {
            @SuppressWarnings("unchecked") E e = (E) elements[i];
            action.accept(e);
        }
        cursor = size;
    }
}

類的屬性

屬性中有一個可重入鎖，用來保證線程安全訪問，還有一個Object類型的數組，用來存放具體的元素。當然，也使用到了反射機制和CAS來保證原子性的修改lock域。

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // 版本序列號
    private static final long serialVersionUID = 8673264195747942595L;
    // 可重入鎖
    final transient ReentrantLock lock = new ReentrantLock();
    // 對象數組，用於存放元素
    private transient volatile Object[] array;
    // 反射機制
    private static final sun.misc.Unsafe UNSAFE;
    // lock域的內存偏移量
    private static final long lockOffset;
    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> k = CopyOnWriteArrayList.class;
            lockOffset = UNSAFE.objectFieldOffset
                (k.getDeclaredField("lock"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}

類的構造函數

  • 默認構造函數
public CopyOnWriteArrayList() {
    // 設置數組
    setArray(new Object[0]);
}
  • CopyOnWriteArrayList(Collection<? extends E>)
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class) // 類型相同
        // 獲取c集合的數組
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else { // 類型不相同
        // 將c集合轉化為數組並賦值給elements
        elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elements.getClass() != Object[].class) // elements類型不為Object[]類型
            // 將elements數組轉化為Object[]類型的數組
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    // 設置數組
    setArray(elements);
}

該構造函數的處理流程如下

  1. 判斷傳入的集合c的類型是否為CopyOnWriteArrayList類型，若是，則獲取該集合類型的底層數組(Object[])，並且設置當前CopyOnWriteArrayList的數組(Object[]數組)，進入步驟③；否則，進入步驟②

  2. 將傳入的集合轉化為數組elements，判斷elements的類型是否為Object[]類型(toArray方法可能不會返回Object類型的數組)，若不是，則將elements轉化為Object類型的數組。進入步驟③

  3. 設置當前CopyOnWriteArrayList的Object[]為elements。

  • CopyOnWriteArrayList(E[])：該構造函數用於創建一個保存給定數組的副本的列表。
public CopyOnWriteArrayList(E[] toCopyIn) {
    // 將toCopyIn轉化為Object[]類型數組，然後設置當前數組
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

核心函數分析

對於CopyOnWriteArrayList的函數分析，主要明白Arrays.copyOf方法即可理解CopyOnWriteArrayList其他函數的意義。

copyOf函數

該函數用於複製指定的數組，截取或用 null 填充(如有必要)，以使副本具有指定的長度。

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    // 確定copy的類型(將newType轉化為Object類型，將Object[].class轉化為Object類型；
    // 判斷兩者是否相等，若相等，則生成指定長度的Object數組
    // 否則,生成指定長度的新類型的數組)
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    // 將original數組從下標0開始，複製長度為(original.length和newLength的較小者),複製到copy數組中(也從下標0開始)
    System.arraycopy(original, 0, copy, 0,
                        Math.min(original.length, newLength));
    return copy;
}

add函數

public boolean add(E e) {
    // 可重入鎖
    final ReentrantLock lock = this.lock;
    // 獲取鎖
    lock.lock();
    try {
        // 元素數組
        Object[] elements = getArray();
        // 數組長度
        int len = elements.length;
        // 複製數組
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 存放元素e
        newElements[len] = e;
        // 設置數組
        setArray(newElements);
        return true;
    } finally {
        // 釋放鎖
        lock.unlock();
    }
}

此函數用於將指定元素添加到此列表的尾部，處理流程如下

  1. 獲取鎖(保證多線程的安全訪問)，獲取當前的Object數組，獲取Object數組的長度為length，進入步驟②。
  2. 根據Object數組複製一個長度為length+1的Object數組為newElements(此時，newElements[length]為null)，進入下一步驟。
  3. 將下標為length的數組元素newElements[length]設置為元素e，再設置當前Object[]為newElements，釋放鎖，返回。這樣就完成了元素的添加。

addIfAbsent方法

該函數用於添加元素(如果數組中不存在，則添加；否則，不添加，直接返回)，可以保證多線程環境下不會重複添加元素。

private boolean addIfAbsent(E e, Object[] snapshot) {
    // 重入鎖
    final ReentrantLock lock = this.lock;
    // 獲取鎖
    lock.lock();
    try {
        // 獲取數組
        Object[] current = getArray();
        // 數組長度
        int len = current.length;
        if (snapshot != current) { // 快照不等於當前數組，對數組進行了修改
            // Optimize for lost race to another addXXX operation
            // 取較小者
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++) // 遍歷
                if (current[i] != snapshot[i] && eq(e, current[i])) // 當前數組的元素與快照的元素不相等並且e與當前元素相等
                    // 表示在snapshot與current之間修改了數組，並且設置了數組某一元素為e，已經存在
                    // 返回
                    return false;
            if (indexOf(e, current, common, len) >= 0) // 在當前數組中找到e元素
                // 返回
                return false;
        }
        // 複製數組
        Object[] newElements = Arrays.copyOf(current, len + 1);
        // 對數組len索引的元素賦值為e
        newElements[len] = e;
        // 設置數組
        setArray(newElements);
        return true;
    } finally {
        // 釋放鎖
        lock.unlock();
    }
}

該函數的流程如下:

  1. 獲取鎖，獲取當前數組為current，current長度為len，判斷數組之前的快照snapshot是否等於當前數組current，若不相等，則進入步驟2；否則，進入步驟4

  2. 不相等，表示在snapshot與current之間，對數組進行了修改(如進行了add、set、remove等操作)，獲取長度(snapshot與current之間的較小者)，對current進行遍歷操作，若遍歷過程發現snapshot與current的元素不相等並且current的元素與指定元素相等(可能進行了set操作)，進入步驟5，否則，進入步驟3

  3. 在當前數組中索引指定元素，若能夠找到，進入步驟5，否則，進入步驟4

  4. 複製當前數組current為newElements，長度為len+1，此時newElements[len]為null。再設置newElements[len]為指定元素e，再設置數組，進入步驟5

  5. 釋放鎖，返回。

set函數

此函數用於用指定的元素替代此列表指定位置上的元素，也是基於數組的複製來實現的。

public E set(int index, E element) {
    // 可重入鎖
    final ReentrantLock lock = this.lock;
    // 獲取鎖
    lock.lock();
    try {
        // 獲取數組
        Object[] elements = getArray();
        // 獲取index索引的元素
        E oldValue = get(elements, index);

        if (oldValue != element) { // 舊值等於element
            // 數組長度
            int len = elements.length;
            // 複製數組
            Object[] newElements = Arrays.copyOf(elements, len);
            // 重新賦值index索引的值
            newElements[index] = element;
            // 設置數組
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            // 設置數組
            setArray(elements);
        }
        // 返回舊值
        return oldValue;
    } finally {
        // 釋放鎖
        lock.unlock();
    }
}

remove函數

此函數用於移除此列表指定位置上的元素。

public E remove(int index) {
    // 可重入鎖
    final ReentrantLock lock = this.lock;
    // 獲取鎖
    lock.lock();
    try {
        // 獲取數組
        Object[] elements = getArray();
        // 數組長度
        int len = elements.length;
        // 獲取舊值
        E oldValue = get(elements, index);
        // 需要移動的元素個數
        int numMoved = len - index - 1;
        if (numMoved == 0) // 移動個數為0
            // 複製後設置數組
            setArray(Arrays.copyOf(elements, len - 1));
        else { // 移動個數不為0
            // 新生數組
            Object[] newElements = new Object[len - 1];
            // 複製index索引之前的元素
            System.arraycopy(elements, 0, newElements, 0, index);
            // 複製index索引之後的元素
            System.arraycopy(elements, index + 1, newElements, index,
                                numMoved);
            // 設置索引
            setArray(newElements);
        }
        // 返回舊值
        return oldValue;
    } finally {
        // 釋放鎖
        lock.unlock();
    }
}

處理流程如下

  1. 獲取鎖，獲取數組elements，數組長度為length，獲取索引的值elements[index]，計算需要移動的元素個數(length - index - 1),若個數為0，則表示移除的是數組的最後一個元素，複製elements數組，複製長度為length-1，然後設置數組，進入步驟③；否則，進入步驟②
  2. 先複製index索引前的元素，再複製index索引後的元素，然後設置數組。
  3. 釋放鎖，返回舊值

CopyOnWriteArrayList是Fail Safe的

採用安全失敗機制的集合容器，在遍歷時不是直接在集合內容上訪問的，而是先複製原有集合內容，在拷貝的集合上進行遍歷。java.util.concurrent包下的容器都是安全失敗，可以在多線程下併發使用，併發修改。

原理：由於迭代時是對原集合的拷貝進行遍歷，所以在遍歷過程中對原集合所作的修改並不能被迭代器檢測到，所以不會觸發Concurrent Modification Exception。

缺點：基於拷貝內容的優點是避免了Concurrent Modification Exception，但同樣地，迭代器並不能訪問到修改後的內容，即：迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發生的修改迭代器是不知道的。

Vector無論是add方法還是get方法都加上了synchronized修飾，當多線程讀寫List必須排隊執行，很顯然這樣效率比較是低下的，CopyOnWriteArrayList是讀寫分離的，好處是提高線程訪問效率。

缺陷和使用場景

  • CopyOnWriteArrayList的寫效率比Vector慢。當CopyOnWriteArrayList寫元素時是通過備份數組的方式實現的，當多線程同步激烈，數據量較大時會不停的複製數組，內存浪費嚴重。如果原數組的內容比較多的情況下，可能導致young gc或者full gc

  • 弱一致性：不能用於實時讀的場景，像拷貝數組、新增元素都需要時間，所以調用一個set操作後，讀取到數據可能還是舊的，雖然CopyOnWriteArrayList 能做到最終一致性，但是還是沒法滿足實時性要求；

小結： CopyOnWriteArrayList合適讀多寫少的場景，例如黑名單白名單等

後端
user avatar
0 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.