【JDK1.8HashMap也会死循环？记一次线上问题排查经历】_hashmap 1.8死循环

JDK1.8HashMap也会死循环？记一次线上问题排查经历

前言

最近一次需求代码上线，发现线上机器cpu可用率逐步升高，线上机器cpu使用情况如图1，据此猜测因为代码中存在线程占用资源未释放而导致

图1 线上机器cpu使用情况

问题追踪

通过cpu上涨现象，怀疑是代码中出现了死循环导致，但由于cpu上涨不明显，因此命中该死循环的请求应该不多。但我还是按照正常的排查思路来进行排查：采用下列命令组合查看线上占用cpu最高的线程栈信息

1. top //查看，占用cpu比较高的进程id
2. top -H -p <pid> //查看当前进程下占用最高的线程栈，记录tid
3. printf "%x\n" <tid> //将tid转换为16进制
4. jstack <pid> | grep <tid~16> -A 50 //查看线程栈信息
1
2
3
4

在执行命令2时，可以看出cpu占用比较高的线程均为ForkJoinPool线程池（如图2所示）， 而本次提交代码中恰好使用了stream流的并发流parallelstream，而parallelstream流的底层线程池恰好就是使用的ForkJoinPool线程池。继续执行命令3和4，查看问题代码，发现果然问题来自本次提交代码

图2 线程栈信息 图3 堆栈对应代码信息

查看当日上线问题代码如下：

Map<Long, Map<String, Object>> stringObjectsMap = Maps.newHashMap();
dataInfo.entrySet()
		.parallelStream()
        .filter(entry -> null != entry.getKey() && null != entry.getValue())
        .forEach(entry -> {
        	String key = entry.getKey();
        	StoreInfo storeInfo = storeInfoMap.get(Long.parseLong(key));
        	Map<String, Float> featuresMap = Maps.newHashMap();
        	entry.getValue().getKVPairList()
        					.stream()
                            .filter(Objects::nonNull)
                            .filter(kvPair -> StringUtils.isNotEmpty(kvPair.getKeyStr())
                                    && CollectionUtils.isNotEmpty(kvPair.getValFltList()))
                            .forEach(kvPair -> {
                                // 解析kvPair中的特征
                                featuresMap.put(kvPair.getKeyStr(), kvPair.getValFlt(0));
                            });
                    storeInfo.getExtFeatures().putAll(featuresMap); //这里在第一次提交代码时，已改为线程安全
                    stringObjectsMap.put(Long.parseLong(key), featuresMap); //这里忘记更改为线程安全hashMap
         });
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

问题分析

温习jdk1.7链表环

在jdk1.8之前，并发下操作普通的hashMap有几率出现死循环的情况，导致机器cpu资源无法释放，根本原因在于jdk1.7在添加新元素时采用了头插法，而扩容时则需要逆序重新链接链表节点，对应源码如下：

//扩容resize方法中调用该方法，用于重新链接新链表到扩容后的新数组
void transfer(Entry[] newTable, boolean rehash) {
	int newCapacity = newTable.length;
	for (Entry<K,V> e : table) {
		while(null != e) {
			Entry<K,V> next = e.next; //1. 获取当前节点的next节点
			if (rehash) {
				e.hash = null == e.key ? 0 : hash(e.key);
			}
			int i = indexFor(e.hash, newCapacity);//2. 计算扩容后新下标
			e.next = newTable[i];  //3. 把当前节点的next节点指向新坐标的链表头部
			newTable[i] = e; //4. 把新坐标指向当前节点
			e = next; //5. 把next节点投入下次循环
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结来看，在jdk1.7中，HashMap扩容总共需要下面5个步骤：

获取当前节点的next节点
计算扩容后新下标
把当前节点的next节点指向新坐标的链表头部
把新坐标（链表头部）指向当前节点
将next节点投入下次循环
1
2
3
4
5

那么假设有x、y、z三个节点，开始在数组坐标为2的位置，如图6，那么按照上述步骤，扩容后的顺序为z、y、x

图4 x、y、z扩容前所在链表及hash桶位置 图5 x、y、z扩容后所在链表及hash桶位置 如果此时有两个线程同时在扩容，其中线程1已经执行完成，同时线程2刚好执行到第1步，即 e = x, next = y，则其继续执行第2步后有：

2、计算扩容后新下标 // i = 6
3、把当前节点的next节点指向新坐标的链表头部 // x -> null (此时新开辟的table[6] 为 null)
4、把新坐标（链表头部）指向当前节点 // table[6] = x
5、将next节点投入下次循环    // y 进入下一次循环，此时由于线程1的影响，y -> x

继续执行则有：
1、获取当前节点的next节点 // e = y, next = x
2、计算扩容后新下标 // i = 6
3、把当前节点的next节点指向新坐标的链表头部 // y -> table[6] = x
4、把新坐标（链表头部）指向当前节点  // table[6] = y
5、将next节点投入下次循环 // x 进入下次循环 此时x -> null， y -> x

继续执行：
1、获取当前节点的next节点 // e = x, next = null
2、计算扩容后新下标 // i = 6
3、把当前节点的next节点指向新坐标的链表头部 // x -> table[6] = y
4、把新坐标（链表头部）指向当前节点  // table[6] = x
5、将next节点投入下次循环 // null 进入下次循环 此时退出循环, x -> y 链表环形成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

图6 多线程下形成链表环

jdk1.8死循环现象复现

jdk1.8升级了hashmap的扩容机制，采用尾插法进行新元素的插入，部分源码参考如下，扩容计算hash值原理参考 探讨jdk1.8和1.7rehash计算方式，这样扩容前后，节点顺序是不变的，就不会出现jdk1.7那种链表环，所以很多八股文开始告诉我们jdk1.8以后并发场景不会出现死循环，只是会出现覆盖率不全的问题，那么事实果真如此吗？

if ((e = oldTab[j]) != null) {
	oldTab[j] = null;
	if (e.next == null) 
		newTab[e.hash & (newCap - 1)] = e; //如果此位置就只有一个元素, 直接放到新坐标
	else if (e instanceof TreeNode) //红黑树处理逻辑
		((TreeNode < K, V > ) e).split(this, newTab, j, oldCap);
	else { // preserve order //链表处理逻辑
		Node < K, V > loHead = null, loTail = null;
		Node < K, V > hiHead = null, hiTail = null;
		Node < K, V > next;
		do {
			next = e.next;
			if ((e.hash & oldCap) == 0) { //这里是判断最高位是否为0,如果是0,表示扩容未对其造成影响,		                            
				if (loTail == null)       //因为length-1 的二进制全是1, 扩容2倍只变化了最高位多了个1, 如 1001 从16扩容至32，
				loHead = e;               //可能出现两种情况：01001, 11001，区别只在于高位是1还是0，这里可以思考一下，(n-1)&hash
				else
					loTail.next = e;
				loTail = e;
			} else {
				if (hiTail == null)
					hiHead = e;
				else
					hiTail.next = e;    //关键 从尾部添加元素
				hiTail = e;
			}
		} while ((e = next) != null);
		if (loTail != null) {
			loTail.next = null;
			newTab[j] = loHead;
		}
		if (hiTail != null) {
			hiTail.next = null;
			newTab[j + oldCap] = hiHead;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

本次线上问题，明显是出现了无法释放cpu资源的线程，而最终定位到问题代码恰好是并发情况下使用了非线程安全的hashMap，而最终定位到的方法调用链路如图3，也恰好是扩容相关代码（resize -> split -> treeify -> balanceInsertion）。为了探究这个问题，本人在测试环境下对问题代码进行了复现，最终也是成功触发了死循环，代码一直处于执行状态。复现代码如下：

//死循环复现代码
public void testHashMap() {
        List<StoreInfo> storeInfos = TestObjectUtil.createStoreInfoList(500000);
        Map<Long, String> testMap = Maps.newHashMap();
        storeInfos.parallelStream().forEach(storeInfo -> {
            testMap.put(storeInfo.getId(), storeInfo.getName()); //并发往map中添加50万store信息
        });
}
1
2
3
4
5
6
7
8

此时我将jvm快照进行dump，并使用jprofiler软件分析发现，在转红黑树的过程中，出现了自我引用的对象（图7），并且其堆栈信息和线上问题代码一致，如图8所示：

图7 代码中转红黑树过程中自引用现象 图8 堆栈信息 通过debug balanceInsertion代码，发现在执行for循环时由于自我引用对象的存在，导致循环永远执行 图9 debug 死循环

问题原因分析

由于底层代码涉及红黑树和左旋右旋以及各种链表到树的转换，因此定位形成环的根因过于困难，但仍可对此进行合理推测，通过多次debug，本人发现问题的根本原因在于当前节点的自我引用（self.parent = self），我们来看下面一段代码：

K k = x.key;
int h = x.hash;
 Class<?> kc = null;
 for (TreeNode<K,V> p = root;;) {
 	int dir, ph;
 	K pk = p.key;
 	if ((ph = p.hash) > h)
 		dir = -1;
 	else if (ph < h)
 		dir = 1;
 	else if ((kc == null &&
 			(kc = comparableClassFor(k)) == null) ||
 			(dir = compareComparables(kc, k, pk)) == 0)
 		dir = tieBreakOrder(k, pk);
 		TreeNode<K,V> xp = p;
 		if ((p = (dir <= 0) ? p.left : p.right) == null) { //当线程1完成了树的构建，恰好线程2也来到了这里，将其左子节点或者右子节点赋值给自己，并且此时不为null，则会继续执行下次循环，此时x.parant = xp = p = x
 			x.parent = xp;
 			if (dir <= 0)
 				xp.left = x;
 			else
 				xp.right = x;
 			root = balanceInsertion(root, x);
 			break;
 		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

假如此时有两个线程，线程1刚好构建好了树，树的左（或右）子节点为当前节点x，那么刚好线程2又刚好走到当前节点并进行判断，那么p = p.left or right = x != null, 则线程2进入下次循环后，x.parent = xp = p = x，出现自我引用，则继续执行balanceInsertion，必将进入如图9所示死循环。至此可以得出结论：jdk1.8的HashMap虽然在扩容、数据结构等多方面进行了优化，但仍旧会出现死循环的问题

另外除了balanceInsertion代码会出现问题，下面代码也可能存在相互引用导致的死循环风险，线上代码排查过程中也已经发现该问题方法，但最终并未复现，因此先放在这里提醒自己：

 final TreeNode<K,V> root() {
 	for (TreeNode<K,V> r = this, p;;) {
 		if ((p = r.parent) == null) //相互引用不为null
 			return r;
 		r = p;
 	}
 }
1
2
3
4
5
6
7

参考链接：
hashMap扩容原理
jdk1.7hashMap死循环详解