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

上一条微信消息中发了两个在并发场景下错误使用HashMap,导致出现了HashMap.get把CPU耗光的现象,虽然讲了是由于HashMap.get里面的for循环出现了无限循环,但没有讲明白为什么这个地方会出现无限循环,刚好博客上@fish也给我发了个专业的解释:“出现死循环是因为map中的桶链表出现了循环链表,循环链表是因为并发put操作造成的,同时进行了resize();如果只有一个线程进行put操作,是不会出现循环链表,所以读写并发不会出现死循环,只有写写并发才有可能出现死循环。”

@fish说的这个确实是根本原因,要造成HashMap.get中的那段for循环无限循环,只能是修改过e.next才有可能,而HashMap的代码中,主要是transfer方法中会进行修改,transfer就是在resize的时候才会触发,transfer方法的代码如下:
[code]
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { Entry e = src[j];
if (e != null) {
src[j] = null;
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
[/code]
这样纯粹看代码挺难看出根本原因,毕竟人脑是串行的,这里举例(这个例子来源于老外的一篇讲HashMap infinite loop的根本原因的文章)来说明下。

假设一个初始容量大小为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

此时第二个线程继续执行,进入这段代码:
[code]
do {
// 此时e为A,e.next为B,此行相当于next = B;
Entry 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);
[/code]
此时newTable的结构为:
Entry[0] = A(.next) –> null

e不为null,继续执行:
[code]
do {
// 此时e为B,e.next为A(第一个线程修改的),此行相当于next = A;
Entry 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);
[/code]
此时newTable的结构为:
Entry[0] = B(.next) –> A(.next) –> null

e不为null,继续执行:
[code]
do {
// 此时e为A,A.next为null,此行相当于next = null
Entry 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);
[/code]
此时newTable的结构为:
Entry[0] = A(.next) <--> B(.next)
无限循环就此造成,此时如果有线程要执行HashMap.get(A) ,就会直接进入无限循环,耗光CPU。

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

另外,关于之前发的Auto Box/Unbox,博客上@yongchun推荐了一篇不错的讲Java 5里Auto Box/Unbox的文章:
http://www.xyzws.com/Javafaq/what-should-i-know-about-autoboxing-and-unboxing-in-java-50/132

=============================
欢迎关注微信公众号:hellojavacases
关于此微信号:
用于分享Java的一些小知识点,Java问题排查的Cases,Java业界的动态,以及和大家一起互动讨论一些Java的场景和问题。

公众号上发布的消息都存放在http://hellojava.info上。

又一起并发场景下错误使用HashMap的Case

之前某天中午的时候突然收到一堆报警,有几台机器load过500了,赶紧到机器上排查是什么问题,先top看了下,cpu us接近100%,于是shift h看看线程的状况,发现没什么消耗高的线程,基本都在0.7%左右,但线程总数看起来很多,于是ps -eLf | grep java -c统计了下,总共有700+个线程,连续执行了几次jstack,然后先重启避免故障持续太久,重启完后看起来好了,查看之前jstack出来的线程信息,发现其中有600个线程处于RUNNABLE状态,并且都在执行HashMap.get,根据以往的经验,基本可以确定是在并发场景下错误使用HashMap造成的(关于常见的Java问题的排查方法可见此贴)。

根据堆栈信息找到相应的出问题的类名,然后根据classloader的装载机制(例如web应用通常在应用的war包/WEB-INF/lib下)找到相应的jar,用jd-gui反编译看了下相应的代码,代码中使用此HashMap的方式类似如下:
[code]
public class xxxxx{
private static Map> caches = new HashMap>();
public void load(){
caches = new HashMap>();
// 往此caches放东西
for…{
caches.put(…
}
}

public List get(String key){
return caches.get(key);
}
}
[/code]

当时堆栈中的信息显示600个线程均在执行caches.get(key),写这段代码的同学之前之所以在这个地方使用HashMap,并且没有加锁,是因为认为load这个方法只会在spring初始化当前这个bean的时候执行一次,但不幸的是后来由于业务发展,这个load方法在数据变更的时候会触发,于是就可能会出现正在往caches里put东西的时候,其他的线程在get,直接就导致并发问题,HashMap.get的并发问题有可能会导致get方法中的下面这段代码进入死循环:
[code]
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
[/code]
当然,出现这个现象不是HashMap的问题,主要还是使用的问题,因此这个问题的修复也很容易,就是用ConcurrentHashMap来替换。

这几天又在另外一个应用里造成出现了这个bug,有问题的代码类似如下:
[code]
private static Map… cache = new HashMap…

Object object = cache.get(key);

if(object == null){

object = 一个比较耗资源的获取Object动作…

cache.put(key,object);

}
[/code]
这段代码是在并发场景下执行的,因此同样是典型的bug,这段代码改造起来稍微麻烦点,即使是使用ConcurrentHashMap,也需要慎重处理,因此上面的整个动作是非原子性的操作(这个时候通常要引入Future)。

high cpu usage in hashmap.get是Google搜hashmap相关的词中的热词,可见这错误是挺容易犯的,诸如著名的Velocity、Hessian都犯过类似的错。
Hessian老版本中的类似bug:http://bugs.caucho.com/view.php?id=1588
Velocity老版本中的类似bug:https://issues.apache.org/jira/browse/VELOCITY-718

=====================华丽的分隔线

欢迎关注微信公众号:hellojavacases
关于此微信号:
用于分享Java的一些小知识点,Java问题排查的Cases,Java业界的动态,以及和大家一起互动讨论一些Java的场景和问题。

公众号上发布的消息都存放在http://hellojava.info上。