java 对ConcurrentHashMap的简单分析

为什么使用ConcurrentHashMap?在JDK1.8中,ConcurrentHashMap为什么放弃了分段锁?

因为ConcurrentHashMap水很深,所以这篇文章我酝酿了很久。编写时我参考了大量同类文章,然后加上了自己的理解,终于还是总结出来了(参考文章我会在文中注明)。

 

一、为什么使用ConcurrentHashMap

在这篇文章中,我们提到HashMap不是线程安全的:

java 如何线程安全地使用HashMap?

如果我们使用SynchronizedMap/自己加同步方法,实现线程安全的HashMap(其实就是自己实现一个SynchronizedMap),在并发环境下对锁的竞争会非常激烈(同一时间只允许一个同步方法执行,相当于锁住了整个Map),导致并发效率低下。

为了解决该问题,concurrent包提供了ConcurrentHashMap。在JDK 7中,ConcurrentHashMap使用了分段锁技术提升并发效率。在JDK 8中,随着HashMap的重构,ConcurrentHashMap也随之发生了改变,使用了CAS算法来保证同步。

下面我们会对ConcurrentHashMap的内部原理进行简单分析。

二、JDK 1.7下的ConcurrentHashMap

(1)ConcurrentHashMap的结构

参考:http://blog.csdn.net/yyychyzzzz/article/details/54635260

上面也提到,“同一时间只允许一个同步方法执行,相当于锁住了整个Map”将导致并发效率低下。如何解决这个问题?

问题出在“锁住了整个Map”。既然“锁整体”有问题,那么我们转变思路,只“锁部分”如何?

如果我们能够控制Map的粒度,把Map分为数个(数量合理的)片段,那么在进行各种同步操作时,只需要锁住部分片段即可,不用锁住整个Map。

只有部分片段被锁住,没有被锁住的片段不会受到任何影响,从而提高Map的并发效率。

换句话说,“ConcurrentHashMap采用了分段锁的设计,只有在同一个分段内才存在竞态关系,不同的分段锁之间没有锁竞争。相比于对整个Map加锁的设计,分段锁大大的提高了高并发环境下的处理能力。”

相对的,因为Map被分为数段,所以一些需要遍历整个Map的方法就需要特殊的实现(比如size()方法,只能逐个统计所有片段中的键值对数量,才能计算出整个Map的大小),另外一些方法(如clear())甚至放弃了对一致性的要求(JDK 1.6中ConcurrentHashMap曾经是弱一致性的,后面的版本改善了此问题)。

(在JDK 1.6中,ConcurrentHashMap的“弱一致性”体现为get()方法不是同步方法,在使用put()方法插入一个元素后,可能无法即时获取该元素。相对的,强一致性应该体现为“put一个元素之后马上就能get到”,这一点在后面的版本中有所改善。我从别的资料中得知,1.7中似乎是使用了volitale,1.8则使用了CAS算法。这个问题具体可以参考:http://ifeve.com/concurrenthashmap-weakly-consistent/

至于JDK 1.7/1.8是如何实现“强一致性”的,我暂时还没有弄明白,有机会再补充。

这就是JDK 1.7下ConcurrentHashMap的思想,结构的示意图如下:

image

首先我们可以看到segments数组,数组中存放的是Segment对象,(在初始情况下)把整个segments数组分为了16段。Segment类继承了ReentrantLock类,如果操作哪一段,就锁住哪一段(比如我使用put()方法往segment1中插入数据,只需要锁住segment1对象即可)。

每个segment的结构都类似于HashMap。谈到HashMap,就会想起经典的bucket + 链表的设计,bucket中存放链表,链表中存放键值对HashEntry。

从结构上不难看出,ConcurrentHashMap的设计思想就是使用二次hash,第一次hash将key映射到对应的segment,而第二次hash则是映射到segment的不同bucket中。

(2)put()方法

ConcurrentHashMap中put()方法的源码为:

既然要插入一个元素,首先要知道这个元素应该被插入到哪个segment中。所以,先对key进行一次hash,求得segment的位置,然后调用内部类Segment的put()方法进行插入。

ConcurrentHashMap的put()方法中是没有加锁的。具体加锁步骤在Segment中的put()方法中,其源码为:

加锁的是整个Segment对象,锁的粒度为单个Segment。

如果线程A和线程B同时执行相同Segment对象的put()方法,就会有如下步骤:

1、线程A执行tryLock()方法成功获取锁,则把HashEntry对象插入到相应的位置。

2、线程B获取锁失败,则执行scanAndLockForPut()方法。

在scanAndLockForPut方法中,会通过重复执行tryLock()方法尝试获取锁,在多处理器环境下,重复次数为64,单处理器重复次数为1,当执行tryLock()方法的次数超过上限时,则执行lock()方法挂起线程B。

3、当线程A执行完插入操作时,会通过unlock()方法释放锁。如果此时线程B仍然在执行tryLock()方法,就会马上获取锁,否则将唤醒线程B继续执行。

通过以上方式,可以实现独立Segment对象中的同步。

(3)get()方法

ConcurrentHashMap中get()方法的源码为:

在调用get()方法时,首先做一次hash,找到Segment,再做一次hash,找到bucket,然后遍历bucket,找出对应的HashEntry(除第一次hash找Segment的位置以外,剩下的流程和HashMap中的实现几乎是一样的)。

(4)在ConcurrentHashMap中,key/value均不能为null

testConcurrentHashMap.java

使用put()方法时,如果检测到key/value为空,会直接抛出一个异常:

那么问题来了,从设计角度来看,为什么HashMap中key/value均可为null,而ConcurrentHashMap中却恰恰相反?

参考:https://laiqitech.com/?p=125

查了很多资料后,关于“value不可为null”,我看到这样一种说法:“在get(null)时,你无法分辨得到的null是“找不到键值对从而返回的null”/“键值对的value就是null”。因为此处存在歧义,所以干脆禁止value为null”。

既然value不可为null,那么“允许key为null”又有什么意义呢?由于编码中几乎不会出现“key为null”情况,所以干脆禁止key为null。

你可能不服:“HashMap为什么可以这样搞?你能区分得到的null是怎么回事吗?”

不好意思,HashMap可以区分这两种情况。存在一个containsValue()方法:

现在你可能更加不服了:“ConcurrentHashMap一样有containsValue()方法,怎么就不能区分了?”

不好意思,ConcurrentHashMap中的containsValue()方法参数不可为null(否则报错)。就算containsValue()方法参数可以为null,还记得找segment时需要做一次hash吗?你告诉我null怎么计算hash…..

总之,ConcurrentHashMap的key和value均不可为null,稍加留意即可(算是一个小坑?)。

(5)自旋锁

JDK 1.7下的ConcurrentHashMap使用了自旋锁:

如put源码所示,当put操作调用tryLock()方法失败时(尝试加锁没成功),当前线程没有直接进入等待状态,而是调用了scanAndLockForPut()方法。

可以看见,scanAndLockForPut中使用了一个while,一直尝试获取锁,直到超过了最大尝试次数才会停止,线程才会进入等待状态。

如果刚接触“自旋锁”这个名词,很容易理解为“自旋的锁”,现在看来,应该理解为“不断循环(自旋)尝试获取锁”。我个人认为“自旋锁”并不是一种“锁”,而是“不断循环尝试获取锁的一种解决方案”。

那么问题来了,当put()方法无法获取锁时,为什么不让当前线程直接进入等待状态,而是让其“自旋”?这样有什么好处?

举个例子,在一般情况下,一条线程A在获得锁后,如果再有线程B试图获取锁,那么线程B将会挂起(阻塞)。

但是,如果A、B两条线程资源竞争不是特别激烈,“处理器阻塞一个线程引起的线程上下文的切换的代价”可能会高于“一直自旋等待资源的代价”(锁的已保持者保持锁时间比较短),那么线程B可以不用放弃CPU时间片,而是在“原地自旋”(不挂起,而是一直请求锁),直到线程A释放了锁,线程B获取锁为止。

要注意的是,如果“线程B自旋的代价高于线程上下文的切换”/“自旋超过一定次数,判定为短时间内不太可能获取锁”,就应该主动终止线程B的自旋状态,让线程挂起,直到线程A释放锁后,才唤醒线程B。

总之,自旋锁节省了“CPU切换线程上下文的代价”,让ConcurrentHashMap的运行效率更高。

(要把自旋锁讲清楚真的不太容易,我这里只是说说个人理解,下次另开文章讨论一下这个问题)

三、JDK 1.8下的ConcurrentHashMap

参考:https://bentang.me/tech/2016/12/01/jdk8-concurrenthashmap-1/

我们都知道,在JDK 1.8中HashMap被重写了。ConcurrentHashMap也使用了HashMap的结构,在此基础上实现了线程安全。

因此,本节的重点应该为:“ConcurrentHashMap是如何在HashMap的基础上实现线程安全的?如果换成我们来设计,怎么设计才会有更好的效果?”

但是,在我看来,因为涉及线程安全,ConcurrentHashMap的实现比HashMap还要复杂很多。看懂已经不易,如果还要强行回答“如何设计”,难度还是太高了。所以本节我只分享一些我的理解,如果有错漏之处,烦请指正。

(1)ConcurrentHashMap的结构

变成了类似HashMap的结构:

999

对于此结构的理解,可以参考:

java 对java8中HashMap的简单分析

(2)put()方法

put()方法调用了putVal()方法,源码为:

我认为需要注意的是这里:

加锁的是bucket中的头结点,锁的粒度为单个bucket。

另外需要注意的是,这里使用了synchronized保证了同步操作。

这里可以拓展一个问题:为什么Jdk 1.8中使用synchronized代替了Lock?在常识中,使用synchronized效率应该是比较低的(并没有)。这里宁愿使用synchronized,不太清楚是出于什么考量。

(3)get()方法

在get()方法中,我们看不到任何同步锁(和JDK 1.7中的实现差不多)。一开始我感觉非常奇怪,如果get()不做同步处理,如何保证线程安全?

后来我查了下,发现了stackoverflow上的这个话题:

https://stackoverflow.com/questions/44460503/java-8-concurrenthashmap

同步是使用volitale关键字实现的,详情可以看该篇文章。

(4)CAS

之前和别人吹比的时候,他们总是说“CAS锁”、“CAS锁”,搞得我一直以为“CAS”是一种锁,现在看来并不是这么一回事。

CAS的概念为:

CAS(Compare And Swap):CAS算法包含三个参数CAS(V, E, N),判断预期值E和内存旧值是否相同(Compare),如果相等用新值N覆盖旧值V(Swap),否则失败。

当多个线程尝试使用CAS同时更新同一个变量时,只有其中一个线程能更新变量的值,其他线程失败(失败线程不会被阻塞,而是被告知“失败”,可以继续尝试)。

我个人理解:每条线程在执行操作前,都要和旧值比对。如果旧值不变,那么证明没有别的线程修改此值,允许操作。如果旧值改变了,那么证明有别的线程已经操作过,为了不影响别的线程的结果,应当中止操作。

(CAS一般被理解为原子操作。CAS需要接受原有期望值expected以及想要修改的新值x,只有在原有期望值与当前值相等时才会更新为x,否则为失败。在ConcurrentHashMap的方法中,大量使用CAS获取/修改互斥量,以达到多线程并发环境下的正确性。)

这里放个链接:http://cmsblogs.com/?p=2235,之后再深入学习。

(5)在JDK1.8中,ConcurrentHashMap为什么放弃了分段锁?

我个人理解:在JDK1.7中,ConcurrentHashMap锁的粒度为单个Segment。在JDK1.8中,锁的粒度为每个bucket,锁的粒度更细,并发效率更高。(升级了当然效率更好(废话))

(粒度更小可以有效减少锁的竞争,关于如何减少锁的竞争,可以参考http://yizhenn.iteye.com/blog/2303074

如果强行要问好在哪里?效果为什么更好?我暂时还感受不到,回答不了这个问题…我只知道JDK1.8中ConcurrentHashMap大概是如何实现线程安全的

四、总结

ConcurrentHashMap还是比较有难度,再加上我最近生病了,不知不觉就折腾了很久,终于还是把这篇文章折腾出来了。

回头看看这几天自己研究ConcurrentHashMap的过程,还算是有收获,但是很多细节问题都没有研究到,而且发现了更多的问题,感觉还是有点头疼。

总之,学无止境。还是要多写代码,多写文章才行。

发表评论

电子邮件地址不会被公开。 必填项已用*标注