并發容器之CopyOnWriteArrayList
Copy-On-Write簡稱COW,是一種用于程式設計中的優化政策。其基本思路是,從一開始大家都在共享同一個内容,當某個人想要修改這個内容的時候,才會真正把内容Copy出去形成一個新的内容然後再改,這是一種延時懶惰政策。從JDK1.5開始Java并發包裡提供了兩個使用CopyOnWrite機制實作的并發容器,它們是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器非常有用,可以在非常多的并發場景中使用到。
什麼是CopyOnWrite容器
CopyOnWrite容器即寫時複制的容器。通俗的了解是當我們往一個容器添加元素的時候,不直接往目前容器添加,而是先将目前容器進行Copy,複制出一個新的容器,然後新的容器裡添加元素,添加完元素之後,再将原容器的引用指向新的容器。這樣做的好處是我們可以對CopyOnWrite容器進行并發的讀,而不需要加鎖,因為目前容器不會添加任何元素。是以CopyOnWrite容器也是一種讀寫分離的思想,讀和寫不同的容器。
CopyOnWriteArrayList的實作原理
在使用CopyOnWriteArrayList之前,我們先閱讀其源碼了解下它是如何實作的。以下代碼是向CopyOnWriteArrayList中add方法的實作(向CopyOnWriteArrayList裡添加元素),可以發現在添加的時候是需要加鎖的,否則多線程寫的時候會Copy出N個副本出來。
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#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添加資料,讀還是會讀到舊的資料,因為寫的時候不會鎖住舊的CopyOnWriteArrayList。
public E get(int index) {
return get(getArray(), index);
}
JDK中并沒有提供CopyOnWriteMap,我們可以參考CopyOnWriteArrayList來實作一個,基本代碼如下:
import java.util.Collection;
import java.util.Map;
import java.util.Set;
public class CopyOnWriteMap<K, V> implements Map<K, V>, Cloneable {
private volatile Map<K, V> internalMap;
public CopyOnWriteMap() {
internalMap = new HashMap<K, V>();
}
public V put(K key, V value) {
synchronized (this) {
Map<K, V> newMap = new HashMap<K, V>(internalMap);
V val = newMap.put(key, value);
internalMap = newMap;
return val;
}
}
public V get(Object key) {
return internalMap.get(key);
}
public void putAll(Map<? extends K, ? extends V> newData) {
synchronized (this) {
Map<K, V> newMap = new HashMap<K, V>(internalMap);
newMap.putAll(newData);
internalMap = newMap;
}
}
}
實作很簡單,隻要了解了CopyOnWrite機制,我們可以實作各種CopyOnWrite容器,并且在不同的應用場景中使用。
CopyOnWrite的應用場景
CopyOnWrite并發容器用于讀多寫少的并發場景。比如白名單,黑名單,商品類目的通路和更新場景,假如我們有一個搜尋網站,使用者在這個網站的搜尋框中,輸入關鍵字搜尋内容,但是某些關鍵字不允許被搜尋。這些不能被搜尋的關鍵字會被放在一個黑名單當中,黑名單每天晚上更新一次。當使用者搜尋時,會檢查目前關鍵字在不在黑名單當中,如果在,則提示不能搜尋。實作代碼如下:
import java.util.Map;
import com.ifeve.book.forkjoin.CopyOnWriteMap;
/**
* 黑名單服務
*
* @author fangtengfei
*
*/
public class BlackListServiceImpl {
private static CopyOnWriteMap<String, Boolean> blackListMap = new CopyOnWriteMap<String, Boolean>(
1000);
public static boolean isBlackList(String id) {
return blackListMap.get(id) == null ? false : true;
}
public static void addBlackList(String id) {
blackListMap.put(id, Boolean.TRUE);
}
/**
* 批量添加黑名單
*
* @param ids
*/
public static void addBlackList(Map<String,Boolean> ids) {
blackListMap.putAll(ids);
}
}
代碼很簡單,但是使用CopyOnWriteMap需要注意兩件事情:
1. 減少擴容開銷。根據實際需要,初始化CopyOnWriteMap的大小,避免寫時CopyOnWriteMap擴容的開銷。
2. 使用批量添加。因為每次添加,容器每次都會進行複制,是以減少添加次數,可以減少容器的複制次數。如使用上面代碼裡的addBlackList方法。
CopyOnWrite的缺點
CopyOnWrite容器有很多優點,但是同時也存在兩個問題,即記憶體占用問題和資料一緻性問題。是以在開發的時候需要注意一下。
記憶體占用問題。因為CopyOnWrite的寫時複制機制,是以在進行寫操作的時候,記憶體裡會同時駐紮兩個對象的記憶體,舊的對象和新寫入的對象(注意:在複制的時候隻是複制容器裡的引用,隻是在寫的時候會建立新對象添加到新容器裡,而舊容器的對象還在使用,是以有兩份對象記憶體)。如果這些對象占用的記憶體比較大,比如說200M左右,那麼再寫入100M資料進去,記憶體就會占用300M,那麼這個時候很有可能造成頻繁的Yong GC和Full GC。之前我們系統中使用了一個服務由于每晚使用CopyOnWrite機制更新大對象,造成了每晚15秒的Full GC,應用響應時間也随之變長。
針對記憶體占用問題,可以通過壓縮容器中的元素的方法來減少大對象的記憶體消耗,比如,如果元素全是10進制的數字,可以考慮把它壓縮成36進制或64進制。或者不使用CopyOnWrite容器,而使用其他的并發容器,如
ConcurrentHashMap。
資料一緻性問題。CopyOnWrite容器隻能保證資料的最終一緻性,不能保證資料的實時一緻性。是以如果你希望寫入的的資料,馬上能讀到,請不要使用CopyOnWrite容器。