java並發之CopyOnWriteArrayList

• 2019 年 10 月 3 日
• 筆記

​ 我在前面總結了Java集合中ArrayList的源碼細節，其中也提到了ArrayList是執行緒不安全的(沒有做任何的同步保證)，也說到了fast-fail機制以及多執行緒下使用ArrayList的異常問題。當然也包括單執行緒下使用不當：這裡主要體現在使用增加for循環遍歷的時候在循環體內進行add/remove操作導致的modCount和ArrayList的迭代器中expectModCount值不一致導致異常拋出問題。

​ 那麼jdk中為我們提供的執行緒安全的List是什麼呢，就是下面要說的CopyOnWriteList這個並發安全的集合類，它主要採用的就是copy-on-write思想，個人理解的這個思想核心大概就是讀寫分離：讀時共享、寫時複製(原本的array)更新(且為獨佔式的加鎖)，而我們下面分析的源碼具體實現也是這個思想的體現。

​ 那先看看CopyOnWriteList集合的特點：是執行緒安全的集合類、對其進行修改都是在底層的數組副本上進行的，更新之後利用volatile的可見性保證別的執行緒可以看到更新後的數組。

概述

​ 還是先貼上CopyOnWriteList的繼承體系吧，可以看到其實現了Serializable、Cloneable和RandomAccess介面，具有隨機訪問的特點，實現了List介面，具備List的特性。

​ 我們單獨看一下CopyOnWriteList的主要屬性和下面要主要分析的方法有哪些。從圖中看出：

• 每個CopyOnWriteList對象裡面有一個array數組來存放具體元素

• 使用ReentrantLock獨佔鎖來保證只有寫執行緒對array副本進行更新。關於ReentrantLock可以參考我另一篇AQS的應用之ReentrantLock。

• CopyOnWriteArrayList在遍歷的使用不會拋出ConcurrentModificationException異常，並且遍歷的時候就不用額外加鎖

  下面還是主要看CopyOnWriteList的實現

成員屬性

//這個就是保證更新數組的時候只有一個執行緒能夠獲取lock，然後更新  final transient ReentrantLock lock = new ReentrantLock();  //使用volatile修飾的array，保證寫執行緒更新array之後別的執行緒能夠看到更新後的array.  //但是並不能保證實時性：在數組副本上添加元素之後，還沒有更新array指向新地址之前，別的讀執行緒看到的還是舊的array  private transient volatile Object[] array;  //獲取數組，非private的，final修飾  final Object[] getArray() {      return array;  }  //設置數組  final void setArray(Object[] a) {      array = a;  }

構造方法

(1)無參構造，默認創建的是一個長度為0的數組

//這裡就是構造方法，創建一個新的長度為0的Object數組  //然後調用setArray方法將其設置給CopyOnWriteList的成員變數array  public CopyOnWriteArrayList() {      setArray(new Object[0]);  }

(2)參數為Collection的構造方法

//按照集合的迭代器遍歷返回的順序，創建包含傳入的collection集合的元素的列表  //如果傳遞的參數為null，會拋出異常  public CopyOnWriteArrayList(Collection<? extends E> c) {      Object[] elements; //一個elements數組      //這裡是判斷傳遞的是否就是一個CopyOnWriteArrayList集合      if (c.getClass() == CopyOnWriteArrayList.class)          //如果是，直接調用getArray方法，獲得傳入集合的array然後賦值給elements          elements = ((CopyOnWriteArrayList<?>)c).getArray();      else {          //先將傳入的集合轉變為數組形式          elements = c.toArray();          //c.toArray()可能不會正確地返回一個 Object[]數組，那麼使用Arrays.copyOf()方法          if (elements.getClass() != Object[].class)              elements = Arrays.copyOf(elements, elements.length, Object[].class);      }      //直接調用setArray方法設置array屬性      setArray(elements);  }

(3)創建一個包含給定數組副本的list

public CopyOnWriteArrayList(E[] toCopyIn) {      setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));  }

上面介紹的是CopyOnWriteList的初始化，三個構造方法都比較易懂，後面還是主要看看幾個主要方法的實現

添加元素

​ 下面是add(E e)方法的實現 ，以及詳細注釋

public boolean add(E e) {      //獲得獨佔鎖      final ReentrantLock lock = this.lock;      //加鎖      lock.lock();      try {          //獲得list底層的數組array          Object[] elements = getArray();          //獲得數組長度          int len = elements.length;          //拷貝到新數組，新數組長度為len+1          Object[] newElements = Arrays.copyOf(elements, len + 1);          //給新數組末尾元素賦值          newElements[len] = e;          //用新的數組替換掉原來的數組          setArray(newElements);          return true;      } finally {          lock.unlock();//釋放鎖      }  }

​ 總結一下add方法的執行流程

• 調用add方法的執行緒會首先獲取鎖，然後調用lock方法對list進行加鎖（了解ReentrantLock的知道這是個獨佔鎖，所以多執行緒下只有一個執行緒會獲取到鎖）
• 只有執行緒會獲取到鎖，所以只有一個執行緒會去更新這個數組，此過程中別的調用add方法的執行緒被阻塞等待
• 獲取到鎖的執行緒繼續執行
  • 首先獲取原數組以及其長度，然後將其中的元素複製到一個新數組中(newArray的長度是原長度+1)
  • 給定數組下標為len+1處賦值
  • 將新數組替換掉原有的數組
• 最後釋放鎖

​ 所以總結起來就是，多執行緒下只有一個執行緒能夠獲取到鎖，然後使用複製原有數組的方式添加元素，之後再將新的數組替換原有的數組，最後釋放鎖（別的add執行緒去執行）。

​ 最後還有一點就是，數組長度不是固定的，每次寫之後數組長度會+1，所以CopyOnWriteList也沒有length或者size這類屬性，但是提供了size()方法，獲取集合的實際大小，size()方法如下

public int size() {      return getArray().length;  }

獲取元素

​ 使用get(i)可以獲取指定位置i的元素，當然如果元素不存在就會拋出數組越界異常。

public E get(int index) {      return get(getArray(), index);  }  final Object[] getArray() {      return array;  }  private E get(Object[] a, int index) {      return (E) a[index];  }

​ 當然get方法這裡也體現了copy-on-write-list的弱一致性問題。我們用下面的圖示簡略說明一下。圖中給的假設情況是：threadA訪問index=1處的元素

• ①獲取array數組
• ②訪問傳入參數下標的元素

​ 因為我們看到get過程是沒有加鎖的（假設array中有三個元素如圖所示）。假設threadA執行①之後②之前，threadB執行remove(1)操作，threadB或獲取獨佔鎖，然後執行寫時複製操作，即複製一個新的數組neArray，然後在newArray中執行remove操作(1)，更新array。threadB執行完畢array中index=1的元素已經是item3了。

​ 然後threadA繼續執行，但是因為threadA操作的是原數組中的元素，這個時候的index=1還是item2。所以最終現象就是雖然threadB刪除了位置為1處的元素，但是threadA還是訪問的原數組的元素。這就是若一致性問題

修改元素

​ 修改也是屬於寫，所以需要獲取lock，下面就是set方法的實現

public E set(int index, E element) {      //獲取鎖      final ReentrantLock lock = this.lock;      //進行加鎖      lock.lock();      try {          //獲取數組array          Object[] elements = getArray();          //獲取index位置的元素          E oldValue = get(elements, index);          // 要修改的值和原值不相等          if (oldValue != element) {              //獲取舊數組的長度              int len = elements.length;              //複製到一個新數組中              Object[] newElements = Arrays.copyOf(elements, len);              //在新數組中設置元素值              newElements[index] = element;              //用新數組替換掉原數組              setArray(newElements);          } else {              // Not quite a no-op; ensures volatile write semantics              //為了保證volatile 語義，即使沒有修改，也要替換成新的數組              setArray(elements);          }          return oldValue; //返回舊值      } finally {          lock.unlock();//釋放鎖      }  }

​ 看了set方法之後，發現其實和add方法實現類似。

• 獲得獨佔鎖，保證同一時刻只有一個執行緒能夠修改數組
• 獲取當前數組，調用get方法獲取指定位置的數組元素
• 判斷get獲取的值和傳入的參數
  • 相等，為了保證volatile語義，還是需要重新這隻array
  • 不相等，將原數組元素複製到新數組中，然後在新數組的index處修改，修改完畢用新數組替換原數組
• 釋放鎖

刪除元素

​ 下面是remove方法的實現，總結就是

• 獲取獨佔鎖，保證只有一個執行緒能夠去刪除元素
• 計算要移動的數組元素個數
  • 如果刪除的是最後一個元素，那麼上面的計算結果是0，就直接將原數組的前len-1個作為新數組替換掉原數組
  • 刪除的不是最後一個元素，那麼按照index分為前後兩部分，分別複製到新數組中，然後替換即可
• 釋放鎖

public E remove(int index) {      //獲取鎖      final ReentrantLock lock = this.lock;      //加鎖      lock.lock();      try {          //獲取原數組          Object[] elements = getArray();          //獲取原數組長度          int len = elements.length;          //獲取原數組index處的值          E oldValue = get(elements, index);          //因為數組刪除元素需要移動，所以這裡就是計算需要移動的個數          int numMoved = len - index - 1;          //計算的numMoved=0，表示要刪除的是最後一個元素，          //那麼舊直接將原數組的前len-1個複製到新數組中，替換舊數組即可          if (numMoved == 0)              setArray(Arrays.copyOf(elements, len - 1));          //要刪除的不是最後一個元素          else {              //創建一個長度為len-1的數組              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();//釋放鎖      }  }

迭代器

​ 迭代器的基本使用方式如下，hashNext()方法用來判斷是否還有元素，next方法返回具體的元素。

CopyOnWriteArrayList list = new CopyOnWriteArrayList();  Iterator<?> itr = list.iterator();  while(itr.hashNext()) {      //do sth      itr.next();  }

​ 那麼在CopyOnWriteArrayList中的迭代器是怎樣實現的呢，為什麼說是弱一致性呢(先獲取迭代器的，但是如果在獲取迭代器之後別的執行緒對list進行了修改，這對於迭代器是不可見的)，下面就說一下CopyOnWriteArrayList中的實現

//Iterator<?> itr = list.iterator();  public Iterator<E> iterator() {      //這裡可以看到，是先獲取到原數組getArray()，這裡記為oldArray      //然後調用COWIterator構造器將oldArray作為參數，創建一個迭代器對象      //從下面的COWIterator類中也能看到，其中有一個成員存儲的就是oldArray的副本      return new COWIterator<E>(getArray(), 0);  }  static final class COWIterator<E> implements ListIterator<E> {      //array的快照版本      private final Object[] snapshot;      //後續調用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;      }      //獲取元素      //hasNext()返回true，直接通過cursor記錄的下標獲取值      //hasNext()返回false，拋出異常      public E next() {          if (! hasNext())              throw new NoSuchElementException();          return (E) snapshot[cursor++];      }      //other method...  }

​ 在上面的程式碼中我們能看處，list的iterator()方法實際上返回的是一個COWIterator對象，COWIterator對象的snapshot成員變數保存了當前list中array存儲的內容，但是snapshot可以說是這個array的一個快照，為什麼這樣說呢

我們傳遞的是雖然是當前的array，但是可能有別的執行緒對array進行了修改然後將原本的array替換掉了，那麼這個時候list中的array和snapshot引用的array就不是一個了，作為原array的快照存在，那麼迭代器訪問的也就不是更新後的數組了。這就是弱一致性的體現

​ 我們看下面的例子

public class TestCOW {        private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList();        public static void main(String[] args) throws InterruptedException {          list.add("item1");          list.add("item2");          list.add("item3");            Thread thread = new Thread() {              @Override              public void run() {                  list.set(1, "modify-item1");                  list.remove("item2");              }          };          //main執行緒先獲得迭代器          Iterator<String> itr = list.iterator();          thread.start();//啟動thread執行緒          thread.join();//這裡讓main執行緒等待thread執行緒執行完，然後再遍歷看看輸出的結果是不是修改後的結果          while (itr.hasNext()) {              System.out.println(Thread.currentThread().getName() + "執行緒中的list的元素:" + itr.next());          }      }  }  

運行結果如下。實際上再上面的程式中我們先向list中添加了幾個元素，然後再thread中修改list，同時讓main執行緒先獲得list的迭代器，並等待thread執行完然後列印list中的元素，發現 main執行緒並沒有發現list中的array的變化，輸出的還是原來的list，這就是弱一致性的體現。

main執行緒中的list的元素:item1
main執行緒中的list的元素:item2
main執行緒中的list的元素:item3

總結

• CopyOnWriteArrayList是如何保證寫時執行緒安全的：使用ReentrantLock獨佔鎖，保證同時只有一個執行緒對集合進行寫操作
• 數據是存儲在CopyOnWriteArrayList中的array數組中的，並且array長度是動態變化的（寫操作會更新array）
• 在修改數組的時候，並不是直接操作array，而是複製出來了一個新的數組，修改完畢，再把舊的數組替換成新的數組
• 使用迭代器進行遍歷的時候不用加鎖，不會拋出ConcurrentModificationException異常，因為使用迭代器遍歷操作的是數組的副本（當然，這是在別的執行緒修改list的情況）

set方法細節

​ 注意到set方法中有一段程式碼是這樣的

else { //oldValue = element（element是傳入的參數）      // Not quite a no-op; ensures volatile write semantics      //為了保證volatile 語義，即使沒有修改，也要替換成新的數組      setArray(elements);  }

​ 其實就是說要指定位置要修改的值和數組中那個位置的值是相同的，但是還是需要調用set方法更新array，這是為什麼呢，參考這個帖子，總結就是為了維護happens-before原則。首先看一下這段話

java.util.concurrent 中所有類的方法及其子包擴展了這些對更高級別同步的保證。尤其是： 執行緒中將一個對象放入任何並發 collection 之前的操作 happen-before 從另一執行緒中的 collection 訪問或移除該元素的後續操作。

​ 可以理解為這裡是為了保證set操作之前的系列操作happen-before與別的執行緒訪問array（不加鎖）的後續操作，參照下面的例子

// 這是兩個執行緒的初始情況  int nonVolatileField = 0; //一個不被volatile修飾的變數  //偽程式碼  CopyOnWriteArrayList<String> list = {"x","y","z"}    // Thread 1  // (1)這裡更新了nonVolatileField  nonVolatileField = 1;  // (2)這裡是set()修改（寫）操作，注意這裡會對volatile修飾的array進行寫操作  list.set(0, "x");    // Thread 2  // (3)這裡是訪問（讀）操作  String s = list.get(0);  // (4)使用nonVolatileField  if (s == "x") {      int localVar = nonVolatileField;  }

假設存在以上場景，如果能保證只會存在這樣的軌跡：(1)->(2)->(3)->(4).根據上述java API文檔中的約定有

​ (2)happen-before與(3)，在執行緒內的操作有（1）happen-before與（2）,（3）happen-before與（4），根據happen-before的傳遞性讀寫nonVolatileField變數就有（1）happen-before與（4）

​ 所以Thread 1對nonVolatileField的寫操作對Thread 2中a的讀操作可見。如果CopyOnWriteArrayList的set的else里沒有setArray(elements)對volatile變數的寫的話，(2)happen-before與(3)就不再有了，上述的可見性也就無法保證。

​ 所以就是為了保證set操作之前的系列操作happen-before與別的執行緒訪問array（不加鎖）的後續操作，