并發(fā)容器（Map、List、Set）實戰(zhàn)及其原理分析—CopyOnWriteArrayList篇
1. JUC包下的并發(fā)容器
Java的集合容器框架中，主要有四大類別：List、Set、Queue、Map，大家熟知的這些集合類ArrayList、LinkedList、HashMap這些容器都是非線程安全的。
所以，Java先提供了同步容器供用戶使用。同步容器可以簡單地理解為通過synchronized來實現(xiàn)同步的容器，比如Vector、Hashtable以及SynchronizedList等容器。這樣做的代價是削弱了并發(fā)性，當(dāng)多個線程共同競爭容器級的鎖時，吞吐量就會降低。
因此為了解決同步容器的性能問題，所以才有了并發(fā)容器。java.util.concurrent包中提供了多種并發(fā)類容器：
圖片
CopyOnWriteArrayList
對應(yīng)的非并發(fā)容器：ArrayList
目標：代替Vector、synchronizedList
原理：利用高并發(fā)往往是讀多寫少的特性，對讀操作不加鎖，對寫操作，先復(fù)制一份新的集合，在新的集合上面修改，然后將新集合賦值給舊的引用，并通過volatile 保證其可見性，當(dāng)然寫操作的鎖是必不可少的了。
CopyOnWriteArraySet
對應(yīng)的非并發(fā)容器：HashSet
目標：代替synchronizedSet
原理：基于CopyOnWriteArrayList實現(xiàn)，其唯一的不同是在add時調(diào)用的是CopyOnWriteArrayList的addIfAbsent方法，其遍歷當(dāng)前Object數(shù)組，如Object數(shù)組中已有了當(dāng)前元素，則直接返回，如果沒有則放入Object數(shù)組的尾部，并返回。
ConcurrentHashMap
對應(yīng)的非并發(fā)容器：HashMap
目標：代替Hashtable、synchronizedMap，支持復(fù)合操作
原理：JDK6中采用一種更加細粒度的加鎖機制Segment“分段鎖”，JDK8中采用CAS無鎖算法。
ConcurrentSkipListMap
對應(yīng)的非并發(fā)容器：TreeMap
目標：代替synchronizedSortedMap(TreeMap)
原理：Skip list（跳表）是一種可以代替平衡樹的數(shù)據(jù)結(jié)構(gòu)，默認是按照Key值升序的。
2. CopyOnWriteArrayList
CopyOnWriteArrayList 是 Java 中的一種線程安全的 List，它是一個可變的數(shù)組，支持并發(fā)讀和寫。它通過在修改操作時創(chuàng)建底層數(shù)組的副本來實現(xiàn)線程安全，從而保證了并發(fā)訪問的一致性。
圖片
2.1 應(yīng)用場景
CopyOnWriteArrayList 的應(yīng)用場景主要有兩個方面：
- 讀多寫少的場景
由于 CopyOnWriteArrayList 的讀操作不需要加鎖，因此它非常適合在讀多寫少的場景中使用。例如，一個讀取頻率比寫入頻率高得多的緩存，使用 CopyOnWriteArrayList 可以提高讀取性能，并減少鎖競爭的開銷。
- 不需要實時更新的數(shù)據(jù)
由于 CopyOnWriteArrayList 讀取的數(shù)據(jù)可能不是最新的，因此它適合于不需要實時更新的數(shù)據(jù)。例如，在日志應(yīng)用中，為了保證應(yīng)用的性能，日志記錄的操作可能被緩沖，并不是實時寫入文件系統(tǒng)，而是在某個時刻批量寫入。這種情況下，使用 CopyOnWriteArrayList 可以避免多個線程之間的競爭，提高應(yīng)用的性能。
2.2 CopyOnWriteArrayList使用
基本使用
和 ArrayList 在使用方式方面很類似。
// 創(chuàng)建一個 CopyOnWriteArrayList 對象
CopyOnWriteArrayList phaser = new CopyOnWriteArrayList();
// 新增
copyOnWriteArrayList.add(1);
// 設(shè)置（指定下標）
copyOnWriteArrayList.set(0, 2);
// 獲取（查詢）
copyOnWriteArrayList.get(0);
// 刪除
copyOnWriteArrayList.remove(0);
// 清空
copyOnWriteArrayList.clear();
// 是否為空
copyOnWriteArrayList.isEmpty();
// 是否包含
copyOnWriteArrayList.contains(1);
// 獲取元素個數(shù)
copyOnWriteArrayList.size();IP 黑名單判定
當(dāng)應(yīng)用接入外部請求后，為了防范風(fēng)險，一般會對請求做一些特征判定，如對請求 IP 是否合法的判定就是一種。IP 黑名單偶爾會被系統(tǒng)運維人員做更新
public class CopyOnWriteArrayListDemo {
private static CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
// 模擬初始化的黑名單數(shù)據(jù)
static {
copyOnWriteArrayList.add("ipAddr0");
copyOnWriteArrayList.add("ipAddr1");
copyOnWriteArrayList.add("ipAddr2");
}
public static void main(String[] args) throws InterruptedException {
Runnable task = new Runnable() {
public void run() {
// 模擬接入用時
try {
Thread.sleep(new Random().nextInt(5000));
} catch (Exception e) {}
String currentIP = "ipAddr" + new Random().nextInt(6);
if (copyOnWriteArrayList.contains(currentIP)) {
System.out.println(Thread.currentThread().getName() + " IP " + currentIP + "命中黑名單，拒絕接入處理");
return;
}
System.out.println(Thread.currentThread().getName() + " IP " + currentIP + "接入處理...");
}
};
new Thread(task, "請求1").start();
new Thread(task, "請求2").start();
new Thread(task, "請求3").start();
new Thread(new Runnable() {
public void run() {
// 模擬用時
try {
Thread.sleep(new Random().nextInt(2000));
} catch (Exception e) {}
String newBlackIP = "ipAddr3";
copyOnWriteArrayList.add(newBlackIP);
System.out.println(Thread.currentThread().getName() + " 添加了新的非法IP " + newBlackIP);
}
}, "IP黑名單更新").start();
Thread.sleep(1000000);
}
}
圖片
2.3 原理
很多時候，我們的系統(tǒng)應(yīng)對的都是讀多寫少的并發(fā)場景。CopyOnWriteArrayList容器允許并發(fā)讀，讀操作是無鎖的，性能較高。至于寫操作，比如向容器中添加一個元素，則首先將當(dāng)前容器復(fù)制一份，然后在新副本上執(zhí)行寫操作，結(jié)束之后再將原容器的引用指向新容器。
- 線程安全的，多線程環(huán)境下可以直接使用，無需加鎖；
- 通過鎖 + 數(shù)組拷貝 + volatile 關(guān)鍵字保證了線程安全；
- 每次數(shù)組操作，都會把數(shù)組拷貝一份出來，在新數(shù)組上進行操作，操作成功之后再賦值回去。
圖片
從整體架構(gòu)上來說，CopyOnWriteArrayList 數(shù)據(jù)結(jié)構(gòu)和 ArrayList 是一致的，底層是個數(shù)組，只不過 CopyOnWriteArrayList 在對數(shù)組進行操作的時候，基本會分四步走：
- 加鎖；
- 從原數(shù)組中拷貝出新數(shù)組；
- 在新數(shù)組上進行操作，并把新數(shù)組賦值給數(shù)組容器；
- 解鎖
除了加鎖之外，CopyOnWriteArrayList 的底層數(shù)組還被 volatile 關(guān)鍵字修飾，意思是一旦數(shù)組被修改，其它線程立馬能夠感知到，代碼如下：
private transient volatile Object[] array;整體上來說，CopyOnWriteArrayList 就是利用鎖 + 數(shù)組拷貝 + volatile 關(guān)鍵字保證了 List 的線程安全。
優(yōu)點
讀操作（不加鎖）性能很高，因為無需任何同步措施，比較適用于讀多寫少的并發(fā)場景。Java的list在遍歷時，若中途有別的線程對list容器進行修改，則會拋ConcurrentModificationException異常。而CopyOnWriteArrayList由于其"讀寫分離"的思想，遍歷和修改操作分別作用在不同的list容器，所以在使用迭代器進行遍歷時候，也就不會拋出ConcurrentModificationException異常了。
缺點
- 內(nèi)存占用問題，畢竟每次執(zhí)行寫操作都要將原容器拷貝一份。數(shù)據(jù)量大時，對內(nèi)存壓力較大，可能會引起頻繁GC；
- 無法保證實時性，因為CopyOnWrite的寫時復(fù)制機制，所以在進行寫操作的時候，內(nèi)存里會同時駐扎兩個對象的內(nèi)存，舊的對象和新寫入的對象（注意：在復(fù)制的時候只是復(fù)制容器里的引用，只是在寫的時候會創(chuàng)建新對象添加到新容器里，而舊容器的對象還在使用，所以有兩份對象內(nèi)存）
2.4 擴展知識：迭代器的 fail-fast 與 fail-safe 機制
在 Java 中，迭代器（Iterator）在迭代的過程中，如果底層的集合被修改（添加或刪除元素），不同的迭代器對此的表現(xiàn)行為是不一樣的，可分為兩類：Fail-Fast（快速失敗）和 Fail-Safe（安全失敗）。
fail-fast 機制
fail-fast 機制是java集合(Collection)中的一種錯誤機制。當(dāng)多個線程對同一個集合的內(nèi)容進行操作時，就可能會產(chǎn)生 fail-fast 事件。例如：當(dāng)某一個線程A通過 iterator 去遍歷某集合的過程中，若該集合的內(nèi)容被其他線程所改變了；那么線程A訪問集合時，就會拋出ConcurrentModificationException異常，產(chǎn)生 fail-fast 事件。
在 java.util 包中的集合，如 ArrayList、HashMap 等，它們的迭代器默認都是采用 Fail-Fast 機制。
圖片
fail-fast解決方案
- 方案一：在遍歷過程中所有涉及到改變modCount 值的地方全部加上synchronized 或者直接使用 Collection#synchronizedList，這樣就可以解決問題，但是不推薦，因為增刪造成的同步鎖可能會阻塞遍歷操作。
- 方案二：使用CopyOnWriteArrayList 替換 ArrayList，推薦使用該方案（即fail-safe）。
fail-safe機制
任何對集合結(jié)構(gòu)的修改都會在一個復(fù)制的集合上進行，因此不會拋出ConcurrentModificationException。在 java.util.concurrent 包中的集合，如 CopyOnWriteArrayList、ConcurrentHashMap 等，它們的迭代器一般都是采用 Fail-Safe 機制。
缺點：
- 采用 Fail-Safe 機制的集合類都是線程安全的，但是它們無法保證數(shù)據(jù)的實時一致性，它們只能保證數(shù)據(jù)的最終一致性。在迭代過程中，如果集合被修改了，可能讀取到的仍然是舊的數(shù)據(jù)。
- Fail-Safe 機制還存在另外一個問題，就是內(nèi)存占用。由于這類集合一般都是通過復(fù)制來實現(xiàn)讀寫分離的，因此它們會創(chuàng)建出更多的對象，導(dǎo)致占用更多的內(nèi)存，甚至可能引起頻繁的垃圾回收，嚴重影響性能。
