JDK8的ConcurrentHashMap也會造成CPU 100%

 ​

現象

大家可能都聽過JDK7中的HashMap在多線程環境下可能造成CPU 100%的現象，這個由于在擴容的時候put時産生了死鍊，由此會在get時造成了CPU 100%。這個問題在JDK8中的HashMap獲得了解決。其實JDK7中的HashMap在多線程環境下不止隻有CPU 100%這一共怪異現象，它還可能造成插入的資料丢失，有興趣的讀者可以自行了解下。

對于HashMap多線程的問題，我們通常會這麼反問：HashMap設計上就不是多線程安全的，何必要去在多線程環境下用呢？的确如此，我們不會傻到顯式的在多線程環境下調用，但是又可能在你所關注的視角範圍外是多線程的，其隐式地讓HashMap置于多線程環境下了，這個又難以一下子察覺到。再者，對于HashMap多線程的問題，我們很多時候推薦使用ConcurrentHashMap來代替HashMap應用于多線程的環境，很不巧的是ConcurrentHashMap也有可能會造成CPU 100%的異常現象。這個怪異現象存在于JDK8的ConcurrentHashMap中，在JDK9中已經得到修複，可以參見：https://bugs.openjdk.java.net/browse/JDK-8062841

什麼情況下JDK8的ConcurrentHashMap會出現這個Bug呢？首先我們來運作一下這段代碼：

Map<String, String> map = new ConcurrentHashMap<>();
map.computeIfAbsent("AaAa",
        key -> map.
        computeIfAbsent("BBBB", key2 -> "value"));      

你會驚奇的發現這個程式一直處于Running狀态，我們通過top -Hp [pid]指令檢視到其中一個線程的CPU使用率接近100%，參考下圖：

可以看到pid為31417的東東，我們再通過jstack -l [pid]指令檢視到對應的線程為：

注意将nid=0x7ab9的16進制轉為10進制就是31417。可以看到問題是發生在了computeIfAbsent方法中，我們将示例中的程式換成下面這段程式也會同樣出現CPU 100%的Bug：

map.computeIfAbsent("AaAa",
        (String key) -> {
            map.put("BBBB", "value");
            return "value";
        });      

問題的關鍵在于遞歸使用了computeIfAbsent方法，筆者在stackoverflow上還搜尋到了同類型的問題，下面的示例程式中調用fibonacci方法同樣也會造成CPU 100%.

static Map<Integer, Integer> concurrentMap = new ConcurrentHashMap<>();

public static void main(String[] args) {
    System.out.println("Fibonacci result for 20 is" + fibonacci(20));
}

static int fibonacci(int i) {
    if (i == 0)
        return i;

    if (i == 1)
        return 1;

    return concurrentMap.computeIfAbsent(i, (key) -> {
        System.out.println("Value is " + key);
        return fibonacci(i - 2) + fibonacci(i - 1);
    });
}      

至于為什麼會發生這個BUG，答案就在ConcurrentHashMap中的computeIfAbsent方法中。

原因

map.computeIfAbsent(key1, mappingFunction)      

如果目前key1-hash對應的tab位(可以了解為槽)剛好是空的,在計算mappingFunction之前會

• step1: 先往對應位置放一個ReservationNode占位
• step2: 然後計算mappingFunction的值value,
• step3: 再将value組裝成最終NODE, 把占位的ReservationNode換成最終NODE;

這時如果:

mappingFunction 中用到了 目前map的computeIfAbsent方法, 很不巧 key2-hash的槽為和key1的是同一個,

因為key1已經在槽中放入了占位節點, 在處理key2時候for循環的是以處理條件都不符合 程式進入了死循環

但是如果:

key2-hash的槽位和key1的不一樣, 是不會發生死循環

多線程問題:

因為ConcurrentHashMap在處理上述step1-step3是同步的, 而且在處理時候會同步擷取的值, 是以是不存線上程不安全的, 純粹是目前線程死循環

Thread1 通過cas 在槽x放了個ReservationNode(RN1), 然後假設mappingFunction執行的很慢

Thread2 在槽x和Thread競争, cas失敗沒有搶到占位符; 進行下一輪for循環, 這是因為槽x中已經被放置了RN1, 是以Thread2擷取到這個RN1,在執行synchronized(RN1) 時候被thread1block住。

code sample:

public static void main(String[] args) throws IOException {
    ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
    //caseA: dead loop
//        map.computeIfAbsent("AA", key -> map.computeIfAbsent("BB", k->"bb"));

    //caseB: block, but no dead loop
    new Thread(()->map.computeIfAbsent("AA", key -> waitAndGet())).start();

    new Thread(()->{
        try {
            TimeUnit.SECONDS.sleep(3);  //delay 1 second
        } catch (InterruptedException e) {}
        map.computeIfAbsent("BB", key-> "bb");
    }).start();

}

private static String waitAndGet(){
   try {
       TimeUnit.SECONDS.sleep(20);
   } catch (InterruptedException e) {
   }
   return "AAA";
}      

解決