查看原文
其他

震惊!ConcurrentHashMap里面也有死循环,作者留下的“彩蛋”了解一下?

why技术 why技术 2022-08-30

持续输出原创文章,点击蓝字关注我吧




这是why的第 52 篇原创文章


荒腔走板

大家好,我是why。


时间过的真是快,一周又要结束了。那么,你比上周更博学了吗?先来一个简短的荒腔走板,给冰冷的技术文注入一丝色彩。


上面这张图是我之前在南五环,路过南苑机场的时候拍的。


这是一架飞机在降落,拍的时候我一下就想起了李志的《天空之城》


飞机飞过天空,天空之城

落雨下的黄昏的我们

此刻我在异乡的夜里

感觉着你忽明忽暗

我想回到过去,沉默着欢喜

天空之城在哭泣越来越明亮的你


这位南京李先生算不上一个名人,只是在一个小圈子里面比较出名。但是呢,总有一些综艺会在节目里面未经许可直接使用他的歌曲。


简单来说就是被侵权了。他每次都会去维权。


有的时候会得到道歉,有的时候胳膊拧不过大腿。


李志维权的时候说过:我能做的其实挺少,但是每一次我试图去做一些事情时,都会有朋友跟我说,这样没用的,你看还是这个死样,所有人都很绝望,我当然也绝望,但是我始终想,能拯救一个是一个,能教育一个是一个,哪有什么事情一夜之间全改了,都要慢慢来。


现在他是一位 404 歌手了。


正如他之前说过的这样:我就怕我哪一天不爱这个世界了,只爱我自己,过自己小日子,跟他们一样,赚点钱,戴个面具。但是那一天真来的话我也没办法。


我记得网易云音乐里面他的歌下面有一条评论是这样的:关于李志我不想说太多,反正我知道,你听李志的歌的时候你想的那个人是不会和你在一起的。


我觉得不是这样的,我听李志的时候我没有想起谁。我只是想到了过往的真实而用力的生活。


所以,这句话应该是:关于李志我不想说太多,反正我知道,你听李志的歌的时候你想到的都是你正在经历的,或者怀念的而又回不去的生活。


总之逼哥牛逼。


好了,说回文章。


JDK BUG

这篇文章,聊一下我最近才知道的一个关于 JDK 8 的 BUG 吧。


首先说一下我是怎么发现这个 BUG 的呢?


大家都知道我对 Dubbo 有一定的关注,前段时间 Dubbo 2.7.7 发布后我看了它的更新点,就是下面这个网址:

https://github.com/apache/dubbo/releases/tag/dubbo-2.7.7


其中有 Bugfixex 这一部分:

每一个我都去简单的看了一下,其他的 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,一个被代码耽误的文学创作者,不是大佬,但是喜欢分享,是一个又暖又有料的四川好男人。


还有,重要的事情说三遍:


欢迎关注我呀。

欢迎关注我呀。

欢迎关注我呀。


往期推荐

mybatis 逆向工程使用姿势不对,把表清空了,心里慌的一比,于是写了个插件。


吐血输出:2万字长文带你细细盘点五种负载均衡策略。


mybatis开发,你用 xml 还是注解?我 pick ...


我告诉你这书的第 3 版到底值不值得买?


如何设置线程池参数?美团给出了一个让面试官虎躯一震的回答。


有读者叫我把这个放在赞赏之后,结果放不了。

但我还是非常感动,感谢读者提出的各种建议。

点亮"在看",别白嫖我,好吗?

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存