CopyOnWrite容器
基本思想
Copy-On-Write，寫入時復(fù)制，這個技術(shù)，準確的說應(yīng)該是一種思想，在很多系統(tǒng)設(shè)計上都會用到，今天我們來談一談Java語言中，JDK運用這種寫入時復(fù)制的思想的數(shù)據(jù)結(jié)構(gòu)/容器，CopyOnWriteArrayList。
CopyOnWriteArrayList，是一個寫入時復(fù)制的容器，它是如何工作的呢？簡單來說，就是平時查詢的時候，都不需要加鎖，隨便訪問，只有在寫入/刪除的時候，才會從原來的數(shù)據(jù)復(fù)制一個副本出來，然后修改這個副本，最后把原數(shù)據(jù)替換成當(dāng)前的副本。修改操作的同時，讀操作不會被阻塞，而是繼續(xù)讀取舊的數(shù)據(jù)。這點要跟讀寫鎖區(qū)分一下。
我們來看看CopyOnWriteArrayList的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);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
- 首先可以看到CopyOnWriteArrayList中用到了ReentrantLock進行加鎖，
- 添加元素時，保證同時只有1個線程進行變更，在變更的時候，先拷貝出來一個副本，先操作這個副本，操作完成后，再把現(xiàn)有的數(shù)據(jù)替換成這個副本。
再來看一下CopyOnWriteArraySet源碼
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]))
return false;
if (indexOf(e, current, common, len) >= 0)
return false;
}
Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
可以看到，同樣使用了復(fù)制的數(shù)據(jù)進行數(shù)據(jù)的添加
優(yōu)點
對于一些讀多寫少的數(shù)據(jù)，這種做法的確很不錯，例如配置、黑名單、物流地址等變化非常少的數(shù)據(jù)，這是一種無鎖的實現(xiàn)?？梢詭臀覀儗崿F(xiàn)程序更高的并發(fā)。
缺點
這種實現(xiàn)只是保證數(shù)據(jù)的最終一致性，在添加到拷貝數(shù)據(jù)而還沒進行替換的時候，讀到的仍然是舊數(shù)據(jù)。如果對象比較大，頻繁地進行替換會消耗內(nèi)存，從而引發(fā)Java的GC問題，這個時候，我們應(yīng)該考慮其他的容器，例如ConcurrentHashMap。
Collections.synchronizedList
首先來看下Collections.synchronizedList的源碼：
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
這個方法回根據(jù)你傳入的List是否實現(xiàn)RandomAccess這個接口來返回的SynchronizedRandomAccessList還是SynchronizedList.
再看一下SynchronizedList的源碼
static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
private static final long serialVersionUID = -7754090372962971524L;
final List<E> list;
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
SynchronizedList(List<E> list, Object mutex) {
super(list, mutex);
this.list = 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);}
}
public int indexOf(Object o) {
synchronized (mutex) {return list.indexOf(o);}
}
public int lastIndexOf(Object o) {
synchronized (mutex) {return list.lastIndexOf(o);}
}
public boolean addAll(int index, Collection<? extends E> c) {
synchronized (mutex) {return list.addAll(index, c);}
}
public ListIterator<E> listIterator() {
return list.listIterator(); // Must be manually synched by user
}
public ListIterator<E> listIterator(int index) {
return list.listIterator(index); // Must be manually synched by user
}
public List<E> subList(int fromIndex, int toIndex) {
synchronized (mutex) {
return new SynchronizedList<>(list.subList(fromIndex, toIndex),
mutex);
}
}
@Override
public void replaceAll(UnaryOperator<E> operator) {
synchronized (mutex) {list.replaceAll(operator);}
}
@Override
public void sort(Comparator<? super E> c) {
synchronized (mutex) {list.sort(c);}
}
... ...
}
可以看到SynchronizedList類中對add，remove， get等方法都加了synchronized關(guān)鍵字修飾，在保證List相關(guān)機制不變的情況下，保證的線程安全
但是可以看到 listIterator（）獲取迭代器的相關(guān)方法并有使用synchronized關(guān)鍵字，因此在進行迭代遍歷的時候，需要加鎖
List<String> list = Collections.synchronizedList(new ArrayList<String>());
list.add("1");
list.add("2");
list.add("3");
synchronized (list) {
Iterator i = list.iterator(); // Must be in synchronized block
while (i.hasNext()) {
//foo(i.next());
System.out.println(i.next());
}
}
幾種同步List實現(xiàn)對比
ArrayList
ArrayList是非線性安全，此類的 iterator 和 listIterator 方法返回的迭代器是快速失敗的：在創(chuàng)建迭代器之后，除非通過迭代器自身的 remove 或 add 方法從結(jié)構(gòu)上對列表進行修改，否則在任何時間以任何方式對列表進行修改，迭代器都會拋出 ConcurrentModificationException。即在一方在便利列表，而另一方在修改列表時，會報ConcurrentModificationException錯誤。而這不是唯一的并發(fā)時容易發(fā)生的錯誤，在多線程進行插入操作時，由于沒有進行同步操作，容易丟失數(shù)據(jù)。
因此，在開發(fā)過程當(dāng)中，ArrayList并不適用于多線程的操作。
Vector
從JDK1.0開始，Vector便存在JDK中，Vector是一個線程安全的列表，采用數(shù)組實現(xiàn)。其線程安全的實現(xiàn)方式是對所有操作都加上了synchronized關(guān)鍵字，這種方式嚴重影響效率，因此，不再推薦使用Vector了，Stackoverflow當(dāng)中有這樣的描述：Why is Java Vector class considered obsolete or deprecated?。
Collections.synchronizedList
Collections.synchronizedList的源碼可知，其實現(xiàn)線程安全的方式是建立了list的包裝類，代碼如下：
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<T>(list) :
new SynchronizedList<T>(list));//根據(jù)不同的list類型最終實現(xiàn)不同的包裝類。
}
其中，SynchronizedList對部分操作加上了synchronized關(guān)鍵字以保證線程安全。部分SynchronizedList的代碼如下：
CopyOnWriteArrayList
從字面可以知道，CopyOnWriteArrayList在線程對其進行些操作的時候，會拷貝一個新的數(shù)組以存放新的字段。
CopyOnWriteArrayList和Collections.synchronizedList對比
CopyOnWriteArrayList和Collections.synchronizedList是實現(xiàn)線程安全的列表的兩種方式。兩種實現(xiàn)方式分別針對不同情況有不同的性能表現(xiàn)，其中CopyOnWriteArrayList的寫操作性能較差，而多線程的讀操作性能較好。而Collections.synchronizedList的寫操作性能比CopyOnWriteArrayList在多線程操作的情況下要好很多，而讀操作因為是采用了synchronized關(guān)鍵字的方式，其讀操作性能并不如CopyOnWriteArrayList。因此在不同的應(yīng)用場景下，應(yīng)該選擇不同的多線程安全實現(xiàn)類。
