不正當使用HashMap導致cpu 100%的問題追究
原文出處： 并發編程網
因最近hashmap誤用引起的死循環又發生了一些案例，左耳朵浩子寫了一篇blog 疫苗：Java HashMap的死循環，看了一下，大家的分析如出一轍。這篇blog也是好幾年前寫的了，之前在平臺技術部的博客上貼過，隨著組織結構的調整，那個博客可能不再維護，把這篇文章在這兒也保存一下。
李鵬同學在blog里寫了篇關于HashMap死鎖模擬的文章: http://blog.csdn.net/madding/archive/2010/08/25/5838477.aspx 做個糾正,那個不是死鎖問題,而是死循環。
這個問題,我們以前討論過。 校長之前的博客和淘寶的畢玄的《分布式Java應用:基礎與實踐》一書中都提到過 velocity導致cpu 100% 的bug,起因是HashMap的使用不當所致。
在之前的郵件列表里,校長提出過這個問題,當時我沒仔細看,不清楚這個問題究竟是對 HashMap的誤用,還是HashMap的潛在問題, 當時感覺不太可能是HashMap自身的問題,否則問題大了。應該是屬于在并發的場景下錯誤的 使用了HashMap。昨天看了李鵬的blog后,覺得這個事情還是應該搞清楚一下;雖然我推測是鏈表形成閉環,但 沒有去證明過。從網上找了一下: http://blog.csdn.net/autoinspired/archive/2008/07/16/2662290.aspx 里面也有提到:
產生這個死循環的根源在于對一個未保護的共享變量 — 一個”HashMap”數據結構的操作。當在 所有操作的方法上加了”synchronized”后,一切恢復了正常。檢查”HashMap”(Java SE 5.0)的源 碼,我們發現有潛在的破壞其內部結構最終造成死循環的可能。在下面的代碼中,如果我們使得 HashMap中的entries進入循環,那 么”e.next()”永遠都不會為null。
不僅get()方法會這樣,put()以及其他對外暴露的方法都會有這個風險,這算jvm的bug嗎?應該說不是的,這個現象很早以前就報告出來了(詳細見: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6423457)。Sun的工程師并不認為這 是bug,而是建議在這樣的場景下應用”ConcurrentHashMap”,在構建可擴展的系統時應將這點 納入規范中。
這篇翻譯提到了對HashMap的誤用,但它沒有點破HashMap內部結構在什么樣誤用情況下怎么被 破壞的;我想要一個有力的場景來弄清楚。再從李鵬的blog來看,用了2個線程來put就模擬出來了,最后堆棧是在transfer方法上(該方法是數據擴容時將數據從舊容器轉移到新容器)。 仔細分析了一下里面的代碼,基本得出了原因,證明了我之前的推測。
假設擴容時的一個場景如下(右邊的容器是一個長度 2 倍于當前容器的數組) 單線程情況。
我們分析數據轉移的過程,主要是鏈表的轉移。
執行過一次后的狀態:
最終的結果:
兩個線程并發情況下,擴容時可能會創建出 2 個新數組容器
順利的話,最終轉移完可能是這樣的結果
但并發情況下,出現死循環的可能場景是什么呢? 還要詳細的分析一下代碼,下面的代碼中重點在do/while循環結構中(完成鏈 表的轉移)。
// 擴容操作,從一個數組轉移到另一個數組
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next; //假設第一個線程執行到這里
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null); // 可能導致死循環
}
}
} 2 個線程并發情況下, 當線程 1 執行到上面第 9 行時,而線程 2 已經完成了一 輪 do/while 操作,那么它的狀態如下圖:
(上面的數組時線程 1 的,已經完成了鏈表數據的轉移;下面的是線程 2 的,它 即將開始進行對鏈表數據的轉移,此時它記錄 E1 和 E2 的首位已經被線程 1 翻 轉了)
后續的步驟如下:
1) 插入 E1 節點,E1 節點的 next 指向新容器索引位置上的值(null 或 entry)
2) 插入 E2 節點,E2 的 next 指向當前索引位置上的引用值 E1
3)因為 next 不為 null,鏈表繼續移動,此時 2 節點之間形成了閉環。造成了 死循環。
上面只是一種情況,造成單線程死循環,雙核 cpu 的話占用率是 50%,還有導致 100%的情況,應該也都是鏈表的閉環所致。
最終,這并不是 HashMap 的問題,是使用場景的不當,在并發情況下選擇非線程 安全的容器是沒有保障的。