CopyOnWriteArrayList 的故事--一起看看java原生的讀寫分離
CopyOnWriteArrayList 是JUC中，為了實現(xiàn)高并發(fā)而提供的list容器之一。
對于大部分的業(yè)務場景，都是讀多寫少，并發(fā)度也基本卡在了讀的位置。
通常支持并發(fā)的容器在解決并發(fā)時，采用是：
（1）數(shù)據(jù)分割，每個線程只操作屬于當前線程自己的數(shù)據(jù)，如ThreadLocal （感興趣的同學可以看我前文 《Java內(nèi)存模型及Java關鍵字 volatile的作用和使用說明》 http://www.rzrgm.cn/jilodream/p/9452391.html）
（2）元數(shù)據(jù)被操作時，通過鎖來進行并發(fā)控制。（如Hashtable 、concurrentHashMap 等）
今天要說的CopyOnWriteArrayList的思想是讀寫分離：
如圖，他的思路大概是這樣的，
（0）提供一個數(shù)組來作為隊列：
（1）所有的讀操作直接讀取數(shù)組，由于只有讀操作，因此不會存在數(shù)據(jù)安全問題。
（2）所有的寫操作是會將原始數(shù)據(jù)（數(shù)組）+改動操作（增刪數(shù)據(jù)） 直接體現(xiàn)到另外一個新的數(shù)組中。(防盜連接：本文首發(fā)自http://www.rzrgm.cn/jilodream/ )在寫操作完畢之前，替換為原有的，外部讀可以訪問的數(shù)組。
（3）由于寫操作才會有并發(fā)的問題，因此所有的寫操作是通過鎖來隔離的。而讀操作都是建立在一個完整的，不被改動的數(shù)組中的，因此讀也就不再需要鎖了。
先來看下命名
Copy 復制/拷貝
On 在...時間點
Write 寫
Array 數(shù)組
List 隊列
結(jié)合起來就是一個在寫數(shù)據(jù)時進行拷貝的數(shù)組隊列。一語道破該并發(fā)容器的核心。
怎么使用CopyOnWriteArrayList就不說了，他的常規(guī)使用與其他List并沒有太大的區(qū)別。
我們直接來看源碼（我這里采用的是JDK17）：
首先來看定義
public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
定義中首先指定該容器依次實現(xiàn)了
List<E>, ---> 隊列接口
RandomAccess, ---> 標記接口，支持隨機訪問
Cloneable, ---> 標記訪問，支持拷貝
java.io.Serializable ---> 標記接口，支持可序列化
至于什么是標記接口，可以看我的這篇文章（為什么這些java接口沒有抽象方法？淺談Java標記接口 http://www.rzrgm.cn/jilodream/p/5986519.html）。
（ps. 不知道大家發(fā)現(xiàn)沒有代表能力的接口jdk往往喜歡加-able，表示可以的。這在代碼簡潔之道這本書中也是推薦的命名方式之一。）
我們接下來看下它的核心源碼。
首先是元數(shù)據(jù)部分：
/** * The lock protecting all mutators. (We have a mild preference * for builtin monitors over ReentrantLock when either will do.) */ final transient Object lock = new Object(); /** The array, accessed only via getArray/setArray. */ private transient volatile Object[] array;
定義了一個Object lock作為全局鎖。用final transient 來修飾。
final 是為了防止鎖被亂改，導致出現(xiàn)安全問題。
transient 則是表示在自動序列化時，不要主動來序列化該字段。這里也是了為了數(shù)據(jù)安全考慮的，防止正反序列化后，實例中的lock對象暴露出去，導致有安全問題。
注意在JDK1.8中，鎖的實現(xiàn)使用的是ReentrantLock。但是在后續(xù)的版本中由于synchronized鎖的優(yōu)化，又使用了syncronized鎖。源碼中的注釋也有這樣寫：
/** * The lock protecting all mutators. (We have a mild preference * for builtin monitors over ReentrantLock when either will do.) */ 當內(nèi)置鎖和 ReentrantLock 都能用的時候，我們略微傾向于使用內(nèi)置鎖。
定義了用來存放Object[] array;使用了transient volatile來修飾。
使用transient 是為了解決序列化的問題。這里就會有一個疑問，為什么支持序列化，(防盜連接：本文首發(fā)自http://www.rzrgm.cn/jilodream/ )并且又要在array 前邊修飾transient，防止它序列化？這是為何，我們序列化不就是為了轉(zhuǎn)存數(shù)據(jù)么？
使用volatile修飾是為了保證array 發(fā)生變化時，所有直接使用的線程可以及時的感知到。這里需要對volatile有一定的認知才能明白，不太明白的同學請先了解
首先是構(gòu)造方法：
public CopyOnWriteArrayList() { setArray(new Object[0]); }
注意看CopyOnWriteArrayList是將一個len=0的數(shù)組初始化到容器中的。而并不像ArrayList一樣預留一個初始化大小的數(shù)組。這是為什么呢？
然后是核心的讀方法：
public E get(int index) { return elementAt(getArray(), index); } static <E> E elementAt(Object[] a, int index) { return (E) a[index]; }
很簡單，從指定的數(shù)組中直接讀出對應位置的元素，返回
核心的四個寫方法：
（1）隊列添加全新元素
public boolean add(E e) { synchronized (lock) { Object[] es = getArray(); int len = es.length; es = Arrays.copyOf(es, len + 1); es[len] = e; setArray(es); return true; } }
1、寫方法直接加了一把全局鎖。
2、然后在同步的代碼塊中，將元數(shù)據(jù)加入到一個（比當前數(shù)組長度+1長度的）新數(shù)組中。
3、接著將新元素添加到隊列的末尾中。
4、最后將新數(shù)組覆蓋到原數(shù)組中。
5、由于原數(shù)組在定義時，使用了volatile關鍵字修飾。因此下次的讀操作就會立刻感知到該元素，
（2）隊列指定位置添加全新元素
public void add(int index, E element) { synchronized (lock) { Object[] es = getArray(); int len = es.length; if (index > len || index < 0) throw new IndexOutOfBoundsException(outOfBounds(index, len)); Object[] newElements; int numMoved = len - index; if (numMoved == 0) newElements = Arrays.copyOf(es, len + 1); else { newElements = new Object[len + 1]; System.arraycopy(es, 0, newElements, 0, index); System.arraycopy(es, index, newElements, index + 1, numMoved); } newElements[index] = element; setArray(newElements); } }
1、寫方法直接加了一把全局鎖。
2、然后判斷當前添加位置的索引是否合法超出了len的合理范圍，如果是，那么就拋出異常。
3、然后判斷當前添加位置是不是數(shù)組的最后位置：
<1>如果是的話，就把原數(shù)組的所有元素拷貝到新數(shù)組的中。新數(shù)組的長度等于老數(shù)組+1。
<2>如果不是的話，就直接new 一個長度為len+1的數(shù)組。然后分別把老數(shù)組的前后兩部分拷貝到新數(shù)組中。
4、將添加位置的元素設置為新元素。
（3）移出指定位置的元素
public E remove(int index) { synchronized (lock) { Object[] es = getArray(); int len = es.length; E oldValue = elementAt(es, index); int numMoved = len - index - 1; Object[] newElements; if (numMoved == 0) newElements = Arrays.copyOf(es, len - 1); else { newElements = new Object[len - 1]; System.arraycopy(es, 0, newElements, 0, index); System.arraycopy(es, index + 1, newElements, index, numMoved); } setArray(newElements); return oldValue; } }
1、移出方法首先加入一把全局鎖
2、獲取指定位置的元素
3、判斷移出元素是不是隊列的末尾：
如果是的話，(防盜連接：本文首發(fā)自http://www.rzrgm.cn/jilodream/ )就把原數(shù)組的去除末尾元素的部分拷貝到新數(shù)組的中。新數(shù)組的長度等于老數(shù)組-1。
如果不是的話，就直接new 一個長度為len-1的數(shù)組。然后分別把老數(shù)組的前后兩部分拷貝到新數(shù)組中。
4、返回查詢到的指定元素
（4）移出指定元素
public boolean remove(Object o) { Object[] snapshot = getArray(); int index = indexOfRange(o, snapshot, 0, snapshot.length); return index >= 0 && remove(o, snapshot, index); } private boolean remove(Object o, Object[] snapshot, int index) { synchronized (lock) { Object[] current = getArray(); int len = current.length; if (snapshot != current) findIndex: { int prefix = Math.min(index, len); for (int i = 0; i < prefix; i++) { if (current[i] != snapshot[i] && Objects.equals(o, current[i])) { index = i; break findIndex; } } if (index >= len) return false; if (current[index] == o) break findIndex; index = indexOfRange(o, current, index, len); if (index < 0) return false; } Object[] newElements = new Object[len - 1]; System.arraycopy(current, 0, newElements, 0, index); System.arraycopy(current, index + 1, newElements, index, len - index - 1); setArray(newElements); return true; } }
1、先獲取當前元素的位置
2、獲取元素對應的位置（注意如果有多個相同的元素這里只取第一個找到的元素o），我們記為index
3、然后跳轉(zhuǎn)到另外一個remove 重載的方法中。
4、在重載方法中加入全局鎖
5、取出最新的數(shù)組current
6、判斷新數(shù)組的current和之前查找時用的數(shù)組是不是一個數(shù)組：
<1>如果不是，說明有其他線程并發(fā)寫操作了，此時開始重新找。
<2>首先在剛才index之前的元素都找一遍，如果找到，說明前移了，或者在index的更前方又插入該元素，此時這個新位置就是要移除的值。
<3>如果沒找到又判斷index>=新數(shù)組長度，那就說明是沒有這個元素o了，直接就返回false了（因為上一步找的是index的位置，如果index都>=新數(shù)組長度，那么其實就已經(jīng)遍歷了）。
<4>如果還沒有，那么判斷index的位置是否仍等于元素o，如果是那么也判斷找到了。
<5>如果還沒有就判斷index后邊的位置是否有元素等于o
這里其實相當于分了3部分，如果發(fā)生了寫操作就判斷 index之前，index的位置，index之后，這三塊分別有沒有o出現(xiàn)。
7、直接new 一個長度為len-1的數(shù)組。然后分別把老數(shù)組的前后兩部分拷貝到新數(shù)組中。
最后這個remove方法其實看的人覺得很繁瑣，為什么他沒有直接進來一把全局鎖，然后遍歷查找最后生成新數(shù)組即可。其實我覺得是可以的，jdk1.7也的確是這樣的。但是在后續(xù)的版本中將預查找的部分移出了鎖的范圍。
鎖的粒度更小。對寫的操作更友好。
以上就是CopyOnWriteArrayList的內(nèi)部核心實現(xiàn)了。
現(xiàn)在又回到最初的問題。(防盜連接：本文首發(fā)自http://www.rzrgm.cn/jilodream/ )為什么元數(shù)組array的len始終和當前存儲的元素數(shù)保持一致。而不是像arraylist等其他容器，給一定的預留空間方便，方便寫呢？
我認為主要基于以下考慮：
CopyOnWriteArrayList本質(zhì)是為了讀寫分離更準確的說是為了讀多寫少的場景設計的。盡可能的壓縮數(shù)組也為數(shù)組拷貝提供了優(yōu)勢。
array是及時變量，每次使用都是全新new一個出來，并不是在原有基礎上寫，沒有必要為了性能預留空間。（核心原因）
另外的一個疑問為什么支持序列化，又要在array 前邊修飾transient，防止它序列化？這是為何，我們序列化不就是為了轉(zhuǎn)存數(shù)據(jù)么？
這主要是由于CopyOnWriteArrayList是使用寫單獨拷貝的方式來處理并發(fā)的。而array前邊又有volatile修飾，也就是說array一旦發(fā)生變化，那么所有使用的線程在下次使用時就會立刻感知到。倘若我們序列化進行中，突然發(fā)生了寫操作，并已經(jīng)完成，我是應該接著序列化（此時就有錯誤），還是重新序列化（性能太差）？
因此又單獨實現(xiàn)了該方法配合序列化用：
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { s.defaultWriteObject(); Object[] es = getArray(); // Write out array length s.writeInt(es.length); // Write out all elements in the proper order. for (Object element : es) s.writeObject(element); }
也就是我單獨取出一份當前的數(shù)組放到es中，后邊不管容器怎么寫，我只序列化es中數(shù)據(jù)。
除此之外，隊列的迭代也會有類似的問題。
我們知道隊列的迭代，本質(zhì)上就是使用迭代器依次的迭代元數(shù)據(jù)。而在CopyOnWriteArrayList中，和序列化相似，在迭代時，是將當前的元數(shù)組的引用指向到snapshot變量中。后續(xù)的迭代操作都是對該snapshot來操作的。
也就是說，在并發(fā)迭代時，我們迭代的數(shù)據(jù)是當前緩存的歷史快照數(shù)據(jù)。如下：
public Iterator<E> iterator() { return new COWIterator<E>(getArray(), 0); } 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; COWIterator(Object[] es, int initialCursor) { cursor = initialCursor; snapshot = es; } .... }
可以看這個例子：
public class CopyOnWriteArrayListLearn { public static void main(String[] args) { CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList(); list.add(1); list.add(2); list.add(3); list.add(4); for (Integer item : list) { list.add(item * 10); System.out.println("item:" + item); } } }
輸出如下，只輸出了迭代開啟一瞬間的容器中的元素：
Connected to the target VM, address: '127.0.0.1:61377', transport: 'socket' item:1 item:2 item:3 item:4 Disconnected from the target VM, address: '127.0.0.1:61377', transport: 'socket'
同時，直接使用迭代器進行寫操作時，(防盜連接：本文首發(fā)自http://www.rzrgm.cn/jilodream/ )就會因為是快照數(shù)據(jù)而沒有意義，所以源碼中直接將迭代器的寫操作拋出異常了：
public void remove() { throw new UnsupportedOperationException(); } /** * Not supported. Always throws UnsupportedOperationException. * @throws UnsupportedOperationException always; {@code set} * is not supported by this iterator. */ public void set(E e) { throw new UnsupportedOperationException(); } /** * Not supported. Always throws UnsupportedOperationException. * @throws UnsupportedOperationException always; {@code add} * is not supported by this iterator. */ public void add(E e) { throw new UnsupportedOperationException(); }
如果你覺得寫的不錯，歡迎轉(zhuǎn)載和點贊。 轉(zhuǎn)載時請保留作者署名jilodream/王若伊_恩賜解脫（博客鏈接：http://www.rzrgm.cn/jilodream/
浙公網(wǎng)安備 33010602011771號