震惊！ConcurrentHashMap 里面也有死循环，作者留下的“彩蛋”了解一下？

关注
发布于: 2020 年 07 月 14 日
震惊！ConcurrentHashMap里面也有死循环，作者留下的“彩蛋”了解一下？
JDK BUG这篇文章，聊一下我最近才知道的一个关于 JDK 8 的 BUG 吧。
首先说一下我是怎么发现这个 BUG 的呢？
大家都知道我对 Dubbo 有一定的关注，前段时间 Dubbo 2.7.7 发布后我看了它的更新点，就是下面这个网址：https://github.com/apache/dubbo/releases/tag/dubbo-2.7.7
其中有 Bugfixes 这一部分：
每一个我都去简单的看了一下，其他的 Bugfixes 或多或少都和 Dubbo 框架有一定的关联性。但是上面红框框起来的部分完全就是 JDK 的 Bug 了。
所以可以单独拎出来说。
这个 Bug 我也是看到了这个地方才知道的，但是研究的过程中我发现，这个怎么说呢：我怀疑这根本就不是 Bug ，这就是 Doug Lea 老爷子在钓鱼执法。
为什么这样的说呢，大家看完本文就知道了。
Bug 稳定复现点击 Dubbo 里面的链接，我们可以看到具体的描述就是一个链接：
打开这个链接：
https://bugs.openjdk.java.net/browse/JDK-8062841
我们可以看到：这个 Bug 是位于大名鼎鼎的 concurrent 包里面的 computeIfAbsent 方法。
这个 Bug 在 JDK 9 里面被修复了，修复人是 Doug Lea。
而我们知道 ConcurrentHashMap 就是 Doug Lea 的大作，可以说是“谁污染谁治理”。
要了解这个 Bug 是怎么回事，就必须先了解下面这个方法是干啥的：
java.util.concurrent.ConcurrentHashMap#computeIfAbsent
从这个方法的第二个入参 mappingFunction 我们可以知道这是 JDK 8 之后提供的方法了。
该方法的含义是：当前 Map 中 key 对应的值不存在时，会调用 mappingFunction 函数，并且将该函数的执行结果（不为 null）作为该 key 的 value 返回。
比如下面这样的：
初始化一个 ConcurrentHashMap ，然后第一次去获取 key 为 why 的 value，没有获取到，直接返回 null。
接着调用 computeIfAbsent 方法，获取到 null 后调用 getValue 方法，将该方法的返回值和当前的 key 关联起来。
所以，第二次获取的时候拿到了 “why技术”。
其实上面的代码的 17 行的返回值就是 “why技术”，只是我为了代码演示，再去调用了一次 map.get() 方法。
知道这个方法干什么的，接下来就带大家看看 Bug 是什么。
我们直接用这个问题里面给的测试用例，地址：
https://bugs.openjdk.java.net/secure/attachment/23985/Main.java
我只是在第 11 行和第 21 行加入了输出语句：
正常的情况下，我们希望方法正常结束，然后 map 里面是这样的：{AaAa=42，BBBB=42}
但是你把这个代码拿到本地去跑（需要 JDK 8 环境），你会发现，这个方法永远不会结束。因为它在进行死循环。
这就是 Bug。
提问的艺术知道 Bug 了，按理来说就应该开始分析源码，了解为啥出现了会出现这个 Bug。
但是我想先插播一小节提问的艺术。因为这个 Bug 就是一个活生生的示例呀。
这个链接，我建议你打开看看，这里面还有 Doug Lea 老爷子的亲自解答：
https://bugs.openjdk.java.net/browse/JDK-8062841
首先我们看提出问题的这个人对于问题的描述（可以先不用细看，反正看着也是懵逼的）：
通常情况下，被提问的人分为两类人：
1.遇到过并知道这个问题的人，可以看的明白你在说什么。
2.虽然没有碰见过这个问题，但感觉是自己熟悉的领域，可能知道答案，但是看了你的问题描述，也不知道你在说什么。
这个描述很长，我第一次看的时候很懵逼，很难理解他在说什么。我就是属于第二类人。
而且在大多数的问题中，第二类人比第一类人多很多。
但是当我了解到这个 Bug 的来龙去脉的时候，再看这个描述，其实写的很清楚了，也很好理解。我就变成第一类人了。
但是变成第一类人是有前提的，前提就是我已经了解到了这个地方 Bug 了。可惜，现在是提问，而被提问的人，还对这个 Bug 不是特别了解。
即使，这个被提问的人是 Doug Lea。
可以看到，2014 年 11 月 04 日 Martin 提出这个问题后， Doug Lea 在不到一个小时内就进行了回复，我给大家翻译一下，老爷子回复的啥：
首先，你说你发现了 ConcurrentHashMap 的问题，但是我没有看到的测试用例。那么我就猜测一下是不是有其他线程在计算值的时候被卡住了，但是从你的描述中我也看不到相应的点。
简单来说就是：Talk is cheap. Show me the code.（屁话少说，放码过来。）
于是另一个哥们 Pardeep 在一个月后提交了一个测试案例，就是我们前面看到的测试案例：
Pardeep 给 Martin 回复到下面这段话：
他开门见山的说：我注意这个 bug 很长时间了，然后我还有一个测试用例。
可以说这个测试案例的出现，才是真正的转折点。
然后他提出了自己的看法，这段描述简短有力的说出了问题的所在（后面我们会讲到），然后他还提出了自己的意见。
不到一个小时，这个回到得到了 Doug Lea 的回复：
他说：小伙子的建议还是不错的，但是现在还不是我们解决这个问题的时候。我们也许会通过代码改进死锁检查机制，以帮助用户 debug 他们的程序。但是目前而言，这种机制就算做出来，工作效率也是非常低下的，比如在当前的这个案例下。但是现在我们至少清楚的知道，是否要实现这种机制是不能确定的。
总之一句话：问题我知道了，但是目前我还没想到好的解决方法。
但是，在 19 天以后，老爷子又回来处理这个问题了：
这次的回答可谓是峰回路转，他说：请忽略我之前的话。我们发现了一些可行的改进方法，这些改进可以处理更多的用户错误，包括本报告中所提供的测试用例，即解决在 computeIfAbsent 中提供的函数中进行递归映射更新导致死锁这样的问题。我们会在 JDK 9 里面解决这个问题。
所以，回顾这个 Bug 被提出的过程。
首先是 Martin 提出了这个问题，并进行了详细的描述。可惜的是他的描述很专业，是站在你已经了解了这个 Bug 的立场上去描述的，让人看的很懵逼。
所以 Doug Lea 看到后也表示这啥呀，没搞懂。
然后是 Pardeep 跟进这个问题，转折点在于他抛出的这个测试案例。而我相信，既然 Martin 能把这个问题描述的很清楚，他一定是有一个自己的测试案例的，但是他没有展现出来。
所以，朋友们，测试案例的重要性不言而喻了。问问题的时候不要只是抛出异常，你至少给段对应的代码，或者日志，或者一次性描述清楚，写在文档里面发出来也行呀。
Bug 的原因导致这个 Bug 的原因也是一句话就能说清楚，前面的 Pardeep 老哥也说了：
问题在于我们在进行 computeIfAbsent 的时候，里面还有一个 computeIfAbsent。而这两个 computeIfAbsent 它们的 key 对应的 hashCode 是一样的。
你说巧不巧。
当它们的 hashCode 是一样的时候，说明它们要往同一个槽放东西。
而当第二个元素进来的时候，发现坑位已经被前一个元素占领了，可能就是这样的画风：
接下来我们就解析一下 computeIfAbsent 方法的工作流程：
第一步是计算 key 对应的 hashCode 应该放到哪个槽里面。
然后是进入1649 行的这个 for 循环，而这个 for 循环是一个死循环，它在循环体内部判断各种情况，如果满足条件则 break 循环。
首先，我们看一下 “AaAa” 和 “BBBB” 经过 spread 计算（右移 16 位高效计算）后的 h 值是什么：
哇塞，好巧啊，从框起来的这两部分可以看到，都是 2031775 呢。
说明他们要在同一个槽里面搞事情。
先是 “AaAa” 进入 computeIfAbsent 方法：
在第一次循环的时候 initTable，没啥说的。
第二次循环先是在 1653 行计算出数组的下标，并取出该下标的 node。发现这个 node 是空的。于是进入分支判断：
在标号为 ① 的地方进行 cas 操作，先用 r（即 ReservationNode）进行一个占位的操作。
在标号为 ② 的地方进行 mappingFunction.apply 的操作，计算 value 值。如果计算出来不为 null，则把 value 组装成最终的 node。
在标号为 ③ 的东西把之前占位的 ReservationNode 替换成标号为 ② 的地方组装成的node 。
问题就出现标号为 ② 的地方。可以看到这里去进行了 mappingFunction.apply 的操作，而这个操作在我们的案例下，会触发另一次 computeIfAbsent 操作。
现在 “AaAa” 就等着这个 computeIfAbsent 操作的返回值，然后进行下一步操作，也就是进行标号为 ③ 的操作了。
接着 “BBBB” 就来了。
通过前面我们知道了 “BBBB” 的 hashCode 经过计算后也是和 “AaAa” 一样。所以它也要想要去那个槽里面搞事情。
可惜它来晚了一步。
带大家看一下对应的代码：
当 key 为 “BBBB” 的时候，算出来的 h 值也是 2031775。
它也会进入 1649 行的这个死循环。然后进行各种判断。
接下来我要论证的是：
在本文的示例代码中，当运行到 key 为 “BBBB” 的时候，进入 1649 行这个死循环后，就退不出来了。程序一直在里面循环运行。
在标号为 ① 的地方，由于这个时候 tab 已经不为 null 了，所以不会进入这个分支。
在标号为 ② 的地方，由于之前 “AaAa” 已经扔了一个 ReservationNode 进去占位置了，所以不等于 null。所以，也就不会进入这个分支。
怕你懵逼，给你配个图，真是暖男作者石锤了：
接下来到标号为 ③ 的地方，里面有一个 MOVED，这个 MOVED 是干啥的呢？
表示当前的 ConcurrentHashMap 是否是在进行扩容。
很明显，现在还没有到该扩容的时候：
第 1678 行的 f 就是之前 “AaAa” 扔进去的 ReservationNode ，这个 Node 的 hash 是 -3，不等于MOVED（-1）。
所以，不会进入这个分支判断。
接下来，能进的只有标号为 ④ 的地方了，所以我们只需要把这个地方攻破，就彻底了解这个 Bug 了。
走起：
通过前面的分析我们知道了，当前案例情况下，只会进入 1672 行这个分支。
而这个分支里面，还有四个判断。我们一个个的攻破：
标号为 ⑤ 的地方，tabAt 方法取出来的对象，就是之前 “AaAa” 放进去的占位的 ReservationNode ，也就是这个 f 。所以可以进入这个分支判断。
标号为 ⑥ 的地方，fh >=0 。而 fh 是当前 node 的 hash 值，大于 0 说明当前是按照链表存储的数据。之前我们分析过了，当前的 hash 值是 -3。所以，不会进入这个分支。
标号为 ⑦ 的地方，判断 f 节点是否是红黑树存储。当然不是的。所以，不会进入这个分支。
标号为 ⑧ 的地方，binCount 代表的是该下标里面，有几个 node 节点。很明显，现在一个都没有。所以当前的 binCount 还是 0 。所以，不会进入这个分支。
完了。分析完了。
Bug 也就出来了，一次 for 循环结束后，没有 break。苦就苦在这个 for 循环还是个死循环。
再来一个上帝视角，看看当 key 为 “BBBB” 的时候发生了什么事情：
进入无限循环内：
①.经过 “AaAa” 之后，tab 就不为 null 了。
②.当前的槽中已经被 “AaAa” 先放了一个 ReservationNode 进行占位了，所以不为 null。
③.当前的 map 并没有进行扩容操作。
④.包含⑤、⑥、⑦、⑧。
⑤.tabAt 方法取出来的对象，就是之前 “AaAa” 放进去的占位的 ReservationNode，所以满足条件进入分支。
⑥.判断当前是否是链表存储，不满足条件，跳过。
⑦.判断当前是否是红黑树存储，不满足条件，跳过。
⑧.判断当前下标里面是否放了 node，不满足条件（“AaAa” 只有个占位的Node ，并没有初始完成，所以还没有放到该下标里面），进入下一次循环。
然后它就在死循环里面出不来了！
我相信现在大家对于这个 Bug 的来路了解清楚了。
如果你是在 idea 里面跑这个测试用例，也可以这样直观的看一眼：
点击这个照相机图标：
从线程快照里面其实也是可以看到端倪的，大家可以去分析分析。
有的观点说的是由于线程安全的导致的死循环，经过分析我觉得这个观点是不对的。
它存在死循环，不是由于线程安全导致的，纯粹是自己进入了死循环。
或者说，这是一个“彩蛋”？
或者......自信点，就说这事 Bug ，能稳定复现的那种。
那么我们如果是使用 JDK 8 怎么避免踩到这个“彩蛋”呢？
看看 Dubbo 里面是怎么解决的：
先调用了 get 方法，如果返回为 null，则调用 putIfAbsent 方法，这样就能实现和之前一样的效果了。
如果你在项目中也有使用 computeIfAbsent 的地方，建议也这样去修改。
说到 ConcurrentHashMap get 方法返回 null，我就想起了之前讨论的一个面试题了：
答案都写在这个文章里面了，有兴趣的可以了解一下《这道面试题我真不知道面试官想要的回答是什么》
Bug 的解决其实彻底理解了这个 Bug 之后，我们再来看一下 JDK 9 里面的解决方案，看一下官方源码对比：
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java?r1=1.258&r2=1.259&sortby=date&diff_format=f
﻿
就加了两行代码，判断完是否是红黑树节点后，再判断一下是否是 ReservationNode 节点，因为这个节点就是个占位节点。如果是，则抛出异常。
就这么简单。没有什么神秘的。
所以，如果你在 JDK 9 里面执行文本的测试用例，就会抛出 IllegalStateException。
这就是 Doug Lea 之前提到的解决方案：
了解了这个 Bug 的来龙去脉后，特别是看到解决方案后，我们就能轻描淡写的说一句：
害，就这？没听说过！
另外，我看 JDK 9 修复的时候还不止修复了一个问题：
http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/6dd59c01f011/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java
﻿
﻿
你去翻一翻。发现，啊，全是知识点啊，学不动了。
钓鱼执法为什么我在文章的一开始就说了这是 Doug Lea 在钓鱼执法呢？
因为在最开始提问的艺术那一部分，我相信，Doug Lea 跑完那个测试案例之后，心里也有点数了。
大概知道问题在哪了，而且从他的回答和他写的文档中我也有理由相信，他写的这个方法的时候就知道可能会出问题。
而且，Pardeep 的回复中提到了文档，那我们就去看看官方文档对于该方法的描述是怎样的：
https://docs.oracle.com/javase/8/docs/api/
文档中说函数方法应该简短，简单。而且不能在更新的映射的时候更新映射。就是说不能套娃。
套娃，用程序说就是recursive（递归），按照文档说如果存在递归，则会抛出 IllegalStateException 。
而提到递归，你想到了什么？
我首先就想到了斐波拉契函数。我们用 computeIfAbsent 实现一个斐波拉契函数如下：
public class Test {
﻿
static Map<Integer, Integer> cache = new ConcurrentHashMap<>();
﻿
    public static void main(String[] args) {
        System.out.println("f(" + 14 + ") =" + fibonacci(14));
    }
﻿
    static int fibonacci(int i) {
        if (i == 0)
            return i;
        if (i == 1)
            return 1;
        return cache.computeIfAbsent(i, (key) -> {
            System.out.println("Slow calculation of " + key);
            return fibonacci(i - 2) + fibonacci(i - 1);
        });
    }
}
﻿
这就是递归调用，我用 JDK 1.8 跑的时候并没有抛出 IllegalStateException，只是程序假死了，原因和我们前面分析的是一样一样的。我理解这个地方是和文档不符的。
所以，我怀疑是 Doug Lea 在这个地方钓鱼执法。
CHM一定线程安全吗？既然都说到 currentHashMap（CHM）了，那我说一个相关的注意点吧。
首先 CHM 一定能保证线程安全吗？
是的，CHM 本身一定是线程安全的。但是，如果你使用不当还是有可能会出现线程不安全的情况。
给大家看一点 Spring 中的源码吧：
org.springframework.core.SimpleAliasRegistry
在这个类中，aliasMap 是 ConcurrentHashMap 类型的：
﻿
在 registerAlias 和 getAliases 方法中，都有对 aliasMap 进行操作的代码，但是在操作之前都是用 synchronized 把 aliasMap 锁住了。
为什么？为什么我们操作 ConcurrentHashMap 的时候还要加锁呢？
这个是根据场景而定的，这个别名管理器，在这里加锁应该是为了避免多个线程操作 ConcurrentHashMap 。
虽然 ConcurrentHashMap 是线程安全的，但是假设如果一个线程 put，一个线程 get，在这个代码的场景里面是不允许的。
如果觉得不太好理解的话我举一个 redis 的例子。
redis 的 get、set 方法都是线程安全的吧。但是你如果先 get 再 set，那么在多线程的情况下还是会有问题的。
因为这两个操作不是原子性的。所以 incr 就应运而生了。
我举这个例子的是想说线程安全与否不是绝对的，要看场景。给你一个线程安全的容器，你使用不当还是会有线程安全的问题。
再比如，HashMap 一定是线程不安全的吗？
说不能说的这么死吧。它是一个线程不安全的容器。但是如果我的使用场景是只读呢？
在这个只读的场景下，它就是线程安全的。
总之，看场景。道理，就是这么一个道理。
最后说两句（求关注）﻿
才疏学浅，难免会有纰漏，如果你发现了错误的地方，还请你留言指出来，我对其加以修改。
感谢您的阅读，我坚持原创，十分欢迎并感谢您的关注。
我是 why，一个被代码耽误的文学创作者，不是大佬，但是喜欢分享，是一个又暖又有料的四川好男人。