当前位置: 首页 > Java > 正文

并发场景下HashMap.get导致cpu耗光的分析

1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

“出现死循环是因为map中的桶链表出现了循环链表,循环链表是因为并发put操作造成的,同时进行了resize();如果只有一个线程进行put操作,是不会出现循环链表,所以读写并发不会出现死循环,只有写写并发才有可能出现死循环。”

要造成HashMap.get中的那段for循环无限循环,只能是修改过e.next才有可能,而HashMap的代码中,主要是transfer方法中会进行修改,transfer就是在resize的时候才会触发,transfer方法的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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的HashMap(大多数人应该知道HashMap是采用数组的方式来存储key,value对象,基于对key的hashcode的hash来决定存储到数组的位置,冲突的情况下采用开放链表的方式来解决),目前里面有两个Entry,假设其存储在数组的同一位置,存储结构类似如下:
Entry[0] = A(.next) –> B(.next) –> null

假设同时有两个线程调用了put,同时触发resize。
第二个线程目前执行到Entry next = e.next这一行,此时其获取到的e为A,next为B。

第一个线程已执行完transfer动作,但还没执行完resize的剩余动作,如A和B在容量扩大为4时hash到的位置仍然相同,那么此时transfer中的newTable的结构变成:
Entry[0] = B(.next) –> A(.next) –> null

此时第二个线程继续执行,进入这段代码:

1
2
3
4
5
6
7
8
9
10
11
12
do {
    // 此时e为A,e.next为B,此行相当于next = B;
    Entry<K,V> next = e.next;  
    // 假设i=0
    int i = indexFor(e.hash, newCapacity); 
    // newTable[0]为null,此行相当于A.next = null;
    e.next = newTable[i]; 
    // 此行相当于newTable[0] = A;
    newTable[i] = e; 
    // 此行相当于e = B;
    e = next;
} while (e != null);

此时newTable的结构为:
Entry[0] = A(.next) –> null

e不为null,继续执行:

1
2
3
4
5
6
7
8
9
10
11
12
do {
    // 此时e为B,e.next为A(第一个线程修改的),此行相当于next = A;
    Entry<K,V> next = e.next;  
    // 假设i = 0
    int i = indexFor(e.hash, newCapacity); 
    // newTable[0]为A,此行相当于B.next = A;
    e.next = newTable[i]; 
    // 此行相当于newTable[0] = B;
    newTable[i] = e; 
    // 此行相当于e = A;
    e = next;
} while (e != null);

此时newTable的结构为:
Entry[0] = B(.next) –> A(.next) –> null

e不为null,继续执行:

1
2
3
4
5
6
7
8
9
10
11
12
do {
    // 此时e为A,A.next为null,此行相当于next = null
    Entry<K,V> next = e.next;  
    // 假设i = 0
    int i = indexFor(e.hash, newCapacity); 
    // newTable[0]为B,此行相当于A.next = B;
    e.next = newTable[i]; 
    // 此行相当于newTable[0] = A;
    newTable[i] = e; 
    // 此行相当于e = null;
    e = next;
} while (e != null);

此时newTable的结构为:
Entry[0] = A(.next) <--> B(.next)
无限循环就此造成,此时如果有线程要执行HashMap.get(A) ,就会直接进入无限循环,耗光CPU。

从上面的分析可以看出,要导致HashMap.get出现无限循环,还真有些不容易,至少要有两个线程在同时进行put,同时触发resize,并且之前一个桶里的两个相邻的对象在容量变了后仍然hash到了同样的数组位置中,这样才有可能导致问题,因此这现象只偶尔出现(不过我们以前曾经悲催的出现过一个集群重启,全部碰到了Velocity的那个错误使用HashMap的bug,导致严重故障)。

本文固定链接: http://www.chepoo.com/hashmap-get-cause-cpu-full.html | IT技术精华网

并发场景下HashMap.get导致cpu耗光的分析:等您坐沙发呢!

发表评论