寫(xiě)時(shí)復(fù)制(Copy-On-Write)在Java中是如何被應(yīng)用的嗎？

前言

寫(xiě)時(shí)復(fù)制（Copy-on-write，簡(jiǎn)稱COW）是一種計(jì)算機(jī)程序設(shè)計(jì)領(lǐng)域的優(yōu)化策略。

其核心思想是，如果有多個(gè)調(diào)用者同時(shí)請(qǐng)求相同資源（如內(nèi)存或磁盤(pán)上的數(shù)據(jù)存儲(chǔ)），他們會(huì)共同獲取相同的指針指向相同的資源，直到某個(gè)調(diào)用者試圖修改資源的內(nèi)容時(shí)，系統(tǒng)才會(huì)真正復(fù)制一份專用副本（private copy）給該調(diào)用者，而其他調(diào)用者所見(jiàn)到的最初的資源仍然保持不變。這個(gè)過(guò)程對(duì)其他的調(diào)用者是透明的（transparently）。

此作法的主要優(yōu)點(diǎn)是如果調(diào)用者沒(méi)有修改該資源，就不會(huì)有副本（private copy）被建立，因此多個(gè)調(diào)用者只是讀取操作時(shí)可以共享同一份資源。

COW（奶牛）技術(shù)的應(yīng)用場(chǎng)景很多，Linux通過(guò)Copy On Write技術(shù)極大地減少了Fork的開(kāi)銷(xiāo)。文件系統(tǒng)通過(guò)Copy On Write技術(shù)一定程度上保證數(shù)據(jù)的完整性。數(shù)據(jù)庫(kù)服務(wù)器也一般采用了寫(xiě)時(shí)復(fù)制策略，為用戶提供一份snapshot。

而JDK的CopyOnWriteArrayList/CopyOnWriteArraySet容器也采用了 COW思想，它是如何工作的是本文討論的重點(diǎn)。

Vector和synchronizedList

我們知道ArrayList是線程不安全的，而Vector是線程安全的容器。查看源碼可以知道，Vector之所以線程安全，是因?yàn)樗鼛缀踉诿總€(gè)方法聲明處都加了synchronized關(guān)鍵字來(lái)使整體方法原子化。

另外，使用Collections.synchronizedList(new ArrayList())修飾后，新建出來(lái)的ArrayList也是安全的，它是如何實(shí)現(xiàn)的呢？查看源碼發(fā)現(xiàn)，它也是幾乎在每個(gè)方法都加上synchronized關(guān)鍵字使方法原子化，只不過(guò)它不是把synchronized加在方法的聲明處，而是加在方法的內(nèi)部。

容器是線程安全的，并不意味著就可以在多線程環(huán)境下放心大膽地隨便用了，來(lái)看下面這段使用Vector的代碼。

@Test
public void testVectorConcurrentReadWrite() {
    Vector<Integer> vector = new Vector<>();
    vector.add(1);
    vector.add(2);
    vector.add(3);
    vector.add(4);
    vector.add(5);
    for (Integer item : vector) {
        new Thread(vector::clear).start();
        System.out.println(item);
    }
}

運(yùn)行結(jié)果如下：

在一個(gè)線程中使用Iterator迭代器遍歷vector，同時(shí)另一個(gè)線程對(duì)vector作修改時(shí)，會(huì)拋出java.util.ConcurrentModificationException異常。很多人不理解，因?yàn)閂ector的所有方法都加了synchronized關(guān)鍵字來(lái)修飾，包括迭代器方法，理論上應(yīng)該是線程安全的呀。

public synchronized Iterator<E> iterator() {
 //Itr是AbstractList的私有內(nèi)部類
    return new Itr();
}

看以上錯(cuò)誤的堆棧指向java.util.Vector$Itr.checkForComodification(Vector.java:1184)，源碼如下：

兩個(gè)關(guān)鍵變量：

• expectedModCount：表示對(duì)List修改次數(shù)的期望值，它的初始值與modCount相等
• modCount：表示List集合結(jié)構(gòu)被修改次數(shù)，是AbstractList類中的一個(gè)成員變量，初始值為0

看過(guò)ArrayList的源碼就知道，每次調(diào)用add()和remove()方法時(shí)就會(huì)對(duì)modCount進(jìn)行加1操作。而我們上面的測(cè)試代碼中調(diào)用了Vector類的clear()方法，這個(gè)方法中對(duì)modCount進(jìn)行了加1，而迭代器中的expectedModCount依然等于0，兩者不等，因此拋了異常。這就是集合中的fail-fast機(jī)制，fail-fast 機(jī)制用來(lái)防止在對(duì)集合進(jìn)行遍歷過(guò)程當(dāng)中，出現(xiàn)意料之外的修改，會(huì)通過(guò)Unchecked異常暴力的反應(yīng)出來(lái)。

雖然Vector的方法都采用了synchronized進(jìn)行了同步，但是實(shí)際上通過(guò)Iterator訪問(wèn)的情況下，每個(gè)線程里面返回的是不同的iterator，也即是說(shuō)expectedModCount變量是每個(gè)線程私有。如果此時(shí)有2個(gè)線程，線程1在進(jìn)行遍歷，線程2在進(jìn)行修改，那么很有可能導(dǎo)致線程2修改后導(dǎo)致Vector中的modCount自增了，線程2的expectedModCount也自增了，但是線程1的expectedModCount沒(méi)有自增，此時(shí)線程1遍歷時(shí)就會(huì)出現(xiàn)expectedModCount不等于modCount的情況了。

同樣地，SynchronizedList在使用迭代器遍歷的時(shí)候同樣會(huì)有問(wèn)題的，源碼中的注釋已經(jīng)提醒我們要手動(dòng)加鎖了。

foreach循環(huán)里不能調(diào)用集合的remove/add/clear方法這一條規(guī)約不僅對(duì)非線程安全的ArrayList/LinkedList適用，對(duì)于線程安全的Vector以及synchronizedList也同樣適用。

因此，要想解決以上問(wèn)題，只能在遍歷前（無(wú)論用不用iterator）加鎖。

synchronized (vector) {
    for (int i = 0; i < vector.size(); i++) {
        System.out.println(vector.get(i));
}
//或者
synchronized (vector) {
    for (Integer item : vector) {
        System.out.println(item);
}

僅僅是遍歷一下容器都要上鎖，性能必然不好。

其實(shí)并非只有遍歷前加鎖這一種解決方法，使用并發(fā)容器CopyOnWriteArrayList也能避免以上問(wèn)題。往期面試題匯總：250期面試資料

CopyOnWriteArrayList介紹

一般來(lái)說(shuō)，我們會(huì)認(rèn)為：CopyOnWriteArrayList是同步List的替代品，CopyOnWriteArraySet是同步Set的替代品。

無(wú)論是Hashtable–>ConcurrentHashMap，還是說(shuō)Vector–>CopyOnWriteArrayList。JUC下支持并發(fā)的容器與老一代的線程安全類相比，總結(jié)起來(lái)就是加鎖粒度的問(wèn)題。

• Hashtable與Vector加鎖的粒度大，直接在方法聲明處使用synchronized
• ConcurrentHashMap、CopyOnWriteArrayList的加鎖粒度小。用各種方式來(lái)實(shí)現(xiàn)線程安全，比如我們知道的ConcurrentHashMap用了CAS、+ volatile等方式來(lái)實(shí)現(xiàn)線程安全
• JUC下的線程安全容器在遍歷的時(shí)候不會(huì)拋出ConcurrentModificationException異常

所以一般來(lái)說(shuō)，我們都會(huì)使用JUC包下給我們提供的線程安全容器，而不是使用老一代的線程安全容器。

下面我們來(lái)看看CopyOnWriteArrayList是怎么實(shí)現(xiàn)的，為什么使用迭代器遍歷的時(shí)候就不用額外加鎖，也不會(huì)拋出ConcurrentModificationException異常。

實(shí)現(xiàn)原理

Copy-on-write是解決并發(fā)的的一種思路，指的是實(shí)行讀寫(xiě)分離，如果執(zhí)行的是寫(xiě)操作，則復(fù)制一個(gè)新集合，在新集合內(nèi)添加或者刪除元素。待一切修改完成之后，再將原集合的引用指向新的集合。

這樣的好處就是，可以高并發(fā)地對(duì)COW進(jìn)行讀和遍歷操作，而不需要加鎖，因?yàn)楫?dāng)前集合不會(huì)添加任何元素。

寫(xiě)時(shí)復(fù)制（copy-on-write）的這種思想，這種機(jī)制，并不是始于Java集合之中，在Linux、Redis、文件系統(tǒng)中都有相應(yīng)思想的設(shè)計(jì)，是一種計(jì)算機(jī)程序設(shè)計(jì)領(lǐng)域的優(yōu)化策略。

CopyOnWriteArrayList的核心理念就是讀寫(xiě)分離，寫(xiě)操作在一個(gè)復(fù)制的數(shù)組上進(jìn)行，讀操作還是在原始數(shù)組上進(jìn)行，讀寫(xiě)分離，互不影響。寫(xiě)操作需要加鎖，防止并發(fā)寫(xiě)入時(shí)導(dǎo)致數(shù)據(jù)丟失。寫(xiě)操作結(jié)束之后需要讓數(shù)組指針指向新的復(fù)制數(shù)組。

看一下CopyOnWriteArrayList基本的結(jié)構(gòu)。

看一下其讀寫(xiě)的源碼，寫(xiě)操作加鎖，防止并發(fā)寫(xiě)入時(shí)導(dǎo)致數(shù)據(jù)丟失，并復(fù)制一個(gè)新數(shù)組，增加操作在新數(shù)組上完成，將array指向到新數(shù)組中，最后解鎖。至于讀操作，則是直接讀取array數(shù)組中的元素。

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();
    }
}

final void setArray(Object[] a) {
    array = a;
}

public E get(int index) {
    return get(getArray(), index);
}

final Object[] getArray() {
    return array;
}

遍歷 - COWIterator

到現(xiàn)在，還是沒(méi)有解釋為什么CopyOnWriteArrayList在遍歷時(shí)，對(duì)其進(jìn)行修改而不拋出異常。

不管是foreach循環(huán)還是直接寫(xiě)Iterator來(lái)遍歷，實(shí)際上都是使用Iterator遍歷。那么就直接來(lái)看下CopyOnWriteArrayList的iterator()方法。

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

來(lái)看一下迭代器COWIterator的實(shí)現(xiàn)源碼。

可以發(fā)現(xiàn)的是，迭代器所有的操作都基于snapshot數(shù)組，而snapshot是傳遞進(jìn)來(lái)的array數(shù)組。

也就是說(shuō)在使用COWIterator進(jìn)行遍歷的時(shí)候，如果修改了集合，集合內(nèi)部的array就指向了新的一個(gè)數(shù)組對(duì)象，而COWIterator內(nèi)部的那個(gè)snapshot還是指向初始化時(shí)傳進(jìn)來(lái)的舊數(shù)組，所以不會(huì)拋異常，因?yàn)榕f數(shù)組永遠(yuǎn)沒(méi)變過(guò)，舊數(shù)組讀操作永遠(yuǎn)可靠且安全。往期面試題匯總：250期面試資料

CopyOnWriteArrayList與synchronizedList性能測(cè)試

寫(xiě)單元測(cè)試來(lái)對(duì)CopyOnWriteArrayList與synchronizedList的并發(fā)寫(xiě)性能作測(cè)試，由于CopyOnWriteArrayList寫(xiě)時(shí)直接復(fù)制新數(shù)組，可以預(yù)想到其寫(xiě)操作性能不高，會(huì)劣于synchronizedList。

@Test
public void testThreadSafeListWrite() {
    List<Integer> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
    List<Integer> synchronizedList = Collections.synchronizedList(new ArrayList<>());
    StopWatch stopWatch = new StopWatch();
    int loopCount = 10000;
    stopWatch.start();
    /**
     * ThreadLocalRandom:是JDK 7之后提供并發(fā)產(chǎn)生隨機(jī)數(shù)，能夠解決多個(gè)線程發(fā)生的競(jìng)爭(zhēng)爭(zhēng)奪。
     * ThreadLocalRandom不是直接用new實(shí)例化，而是第一次使用其靜態(tài)方法current()。
     * 從Math.random()改變到ThreadLocalRandom有如下好處：我們不再有從多個(gè)線程訪問(wèn)同一個(gè)隨機(jī)數(shù)生成器實(shí)例的爭(zhēng)奪。
     */
    IntStream.rangeClosed(1, loopCount).parallel().forEach(
            item -> copyOnWriteArrayList.add(ThreadLocalRandom.current().nextInt(loopCount)));
    stopWatch.stop();
    System.out.println(
            "Write:copyOnWriteList: " + stopWatch.getTime() + "，copyOnWriteList.size()=" + copyOnWriteArrayList
                    .size());

    stopWatch.reset();
    stopWatch.start();
    /**
     * parallelStream特點(diǎn)：基于服務(wù)器內(nèi)核的限制，如果你是八核
     * 每次線程只能起八個(gè)，不能自定義線程池
     */
    IntStream.rangeClosed(1, loopCount).parallel().forEach(
            item -> synchronizedList.add(ThreadLocalRandom.current().nextInt(loopCount)));
    stopWatch.stop();
    System.out.println(
            "Write:synchronizedList: " + stopWatch.getTime() + "，synchronizedList.size()=" + synchronizedList
                    .size());
}

運(yùn)行結(jié)果如下，可以看到同樣條件下的寫(xiě)耗時(shí)，CopyOnWriteArrayList是synchronizedList的30多倍。

同樣地，寫(xiě)單元測(cè)試來(lái)對(duì)CopyOnWriteArrayList與synchronizedList的并發(fā)讀性能作測(cè)試，由于CopyOnWriteArrayList讀操作不加鎖，可以預(yù)想到其讀操作性能明顯會(huì)優(yōu)于synchronizedList。

@Test
public void testThreadSafeListRead() {
    List<Integer> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
    List<Integer> synchronizedList = Collections.synchronizedList(new ArrayList<>());
    copyOnWriteArrayList.addAll(IntStream.rangeClosed(1, 1000000).boxed().collect(Collectors.toList()));
    synchronizedList.addAll(IntStream.rangeClosed(1, 1000000).boxed().collect(Collectors.toList()));

    int copyOnWriteArrayListSize = copyOnWriteArrayList.size();
    StopWatch stopWatch = new StopWatch();
    int loopCount = 1000000;
    stopWatch.start();
    /**
     * ThreadLocalRandom:是JDK 7之后提供并發(fā)產(chǎn)生隨機(jī)數(shù)，能夠解決多個(gè)線程發(fā)生的競(jìng)爭(zhēng)爭(zhēng)奪。
     * ThreadLocalRandom不是直接用new實(shí)例化，而是第一次使用其靜態(tài)方法current()。
     * 從Math.random()改變到ThreadLocalRandom有如下好處：我們不再有從多個(gè)線程訪問(wèn)同一個(gè)隨機(jī)數(shù)生成器實(shí)例的爭(zhēng)奪。
     */
    IntStream.rangeClosed(1, loopCount).parallel().forEach(
            item -> copyOnWriteArrayList.get(ThreadLocalRandom.current().nextInt(copyOnWriteArrayListSize)));
    stopWatch.stop();
    System.out.println("Read:copyOnWriteList: " + stopWatch.getTime());

    stopWatch.reset();
    stopWatch.start();
    int synchronizedListSize = synchronizedList.size();
    /**
     * parallelStream特點(diǎn)：基于服務(wù)器內(nèi)核的限制，如果你是八核
     * 每次線程只能起八個(gè)，不能自定義線程池
     */
    IntStream.rangeClosed(1, loopCount).parallel().forEach(
            item -> synchronizedList.get(ThreadLocalRandom.current().nextInt(synchronizedListSize)));
    stopWatch.stop();
    System.out.println("Read:synchronizedList: " + stopWatch.getTime());
}

運(yùn)行結(jié)果如下，同等條件下的讀耗時(shí)，CopyOnWriteArrayList只有synchronizedList的一半。

CopyOnWriteArrayList優(yōu)缺點(diǎn)總結(jié)

優(yōu)點(diǎn)：

• 對(duì)于一些讀多寫(xiě)少的數(shù)據(jù)，寫(xiě)入時(shí)復(fù)制的做法就很不錯(cuò)，例如配置、黑名單、物流地址等變化非常少的數(shù)據(jù)，這是一種無(wú)鎖的實(shí)現(xiàn)。可以幫我們實(shí)現(xiàn)程序更高的并發(fā)。
• CopyOnWriteArrayList并發(fā)安全且性能比Vector好。Vector是增刪改查方法都加了synchronized 來(lái)保證同步，但是每個(gè)方法執(zhí)行的時(shí)候都要去獲得鎖，性能就會(huì)大大下降，而CopyOnWriteArrayList只是在增刪改上加鎖，但是讀不加鎖，在讀方面的性能就好于Vector。

缺點(diǎn)：

• 數(shù)據(jù)一致性問(wèn)題。CopyOnWrite容器只能保證數(shù)據(jù)的最終一致性，不能保證數(shù)據(jù)的實(shí)時(shí)一致性。比如線程A在迭代CopyOnWriteArrayList容器的數(shù)據(jù)。線程B在線程A迭代的間隙中將CopyOnWriteArrayList部分的數(shù)據(jù)修改了，但是線程A迭代出來(lái)的是舊數(shù)據(jù)。
• 內(nèi)存占用問(wèn)題。如果CopyOnWriteArrayList經(jīng)常要增刪改里面的數(shù)據(jù)，并且對(duì)象比較大，頻繁地寫(xiě)會(huì)消耗內(nèi)存，從而引發(fā)Java的GC問(wèn)題，這個(gè)時(shí)候，我們應(yīng)該考慮其他的容器，例如ConcurrentHashMap。