ConcurrentHashMap 并发之美

一、前言

她如暴风雨中的一叶扁舟,在高并发的大风大浪下疾驰而过,眼看就要被湮灭,却又在绝境中绝处逢生

编写一套即稳定高效、且支持并发的代码,不说难如登天,却也绝非易事。

一直有小伙伴向我咨询关于ConcurrentHashMap(后文简写为CHM)的问题,常常抱怨说:其他源码懂就是懂了,不懂就是不懂,唯独CHM总给人一种似懂非懂的感觉,感觉抓住了精髓,却又若即若离。其实,之所以有这种感觉,并不难理解,因为本质上CHM是一套支持高并发的代码,同一个方法、同一个返回值,在不同的线程或不同并发场景都需要完美运行,之所以感觉似懂非懂,可能是因为只抓住了某一类场景。区别于其他源码,我们读CHM时,也一定让自己学会分身。

本文在介绍CHM原理时,会更多的以分身的角度去看她,我会尽量抛弃逐行读源码的方式,并抱着为CHM找bug的心态去读她(不存在完美的代码,CHM也不例外)

二、概述

本文介绍的CHM版本基于JDK1.8,源码洋洋洒洒共有6000+行代码,本文着重介绍put(初始化、累加器、扩容)、get方法

建议没有读过源码的同学先看一遍源码,然后带着问题来读,这样更容易读懂并吃透她

三、整体介绍

3.1、模型介绍

我们首先把1.8版本的CHM数据结构介绍下,让大家对她有个宏观认识
ConcurrentHashMap 并发之美

  • 说明:此示意图仅为展示CHM数据结构,并非真实场景,例如数据个数如果超过数组长度的3/4,会自动进行扩容;还有某节点下hash冲突严重,导致链表树化的时,数组长度至少要扩容至64

名词约定

分桶: 如上图所示,CHM的Node数组长度为16,我们把每一个数组元素及其相关节点称为一个分桶,可见一个分桶的数据结构可以是链表形式的,也可以是红黑树或者null

结构简述

在没有指定参数的情况下,CHM 会默认创建一个长度为 16 的 Node 数组,随着数据 put 进来,CHM 通过 key 计算其 hash(正数) 值,然后对数据长度取模,确认其将要插入的分桶后通过尾插法将新数据插入链表尾部,当链表长度超过8,CHM 会将其转换为红黑树,为之后的查询、插入等提速,红黑树的数据结构为 TreeBin,hash值固定为-2;当因发生节点删除导致红黑树总长度低于6时,便重新转换为链表。一旦数量超过 Node 数组长度的 3/4,CHM 便会发生扩容。

class Node<K,V> implements Map.Entry<K,V> {
   final int hash;	// hash值,正常节点的hash值都为正数
   final K key;	// map的key值
   volatile V val;	// map的value值
   volatile Node<K,V> next;	// 当前节点的下一个,如没有则为null
}

以上是 CHM 的操作梗概,很多细节都没展开来说,大家先有个宏观概念即可,另红黑树的操作本文不会展开来说,因本文主要侧重点为并发,而操作红黑树时一般都挂有synchronized锁,那多线程并发的场景便不会涉及,读者如果有兴趣可自行google、百度;或者参考本人的github工程git@github.com:xijiu/share.git,里面有关于红黑树、B树、B+树等详细用例,值得一提的是用例会直接在控制台打印树信息,方便调试、学习

ConcurrentHashMap 并发之美

3.2、宏观认识

put方法的流程如下图所示,其中涉及几个关键步骤:table初始化扩容数据写入总数累加。其实整体来看的话,流程很简单,没有初始化时,执行初始化,需要扩容时,帮助扩容,然后将数据写入,最后记录map总数。接下来我们逐个分析

ConcurrentHashMap 并发之美

注:本文中,橙色线表示执行时不加任何锁;蓝色表示CAS操作;绿色表示synchronized

3.3、初始化

ConcurrentHashMap 并发之美

变量说明

table 成员变量,volatile修饰,定义为 Node<K,V>[] table,初始默认值为null;Node的数据结构简单明晰,为map存储数据的主要数据结构,读者可自行参看jdk源码,此处不再赘述

sizeCtl int 类型的成员变量,volatile修饰,保证内存可见性,主要用来标记map扩容的阈值;例如map新创建时,table的长度为16,那么siteCtl=leng*3/4=12,即达到该阈值后,map就需要进行扩容;siteCtl 的初始默认值为 0。不过在table初始化或者扩容时,sizeCtl 会复用

  • -1 table初始化时,会将其通过CAS操作置为-1,用来标记初始化加锁成功
  • ≈ -2147024894 很大的一个负数,逼近int最小值,扩容时用到,主要用来标记参与扩容线程数量以及控制最大扩容并发线程。具体计算公式为((Integer.numberOfLeadingZeros(n) | (1 << 15)) << 16) + 2,其低16位及高16位都有设计理念,在讲到扩容部分时会详细介绍

质疑

Ⅰ、问:最后直接将 sizeCtl 修改为12时,是否存在漏洞?设想场景:当线程 A 执行到此处,并完成了对 table 的初始化操作,但还未对 sizeCtl 进行赋值。新的请求进来后,发现table不为null,那么便执行赋值操作(初始化线程还未执行完毕),在后续的扩容判断时,sizeCtl 的值一直为-1,导致CHM异常

答:其实这个问题质量很高,的确存在描述的情况,不过即便真的出现,也不会导致CHM异常,在扩容阶段有个关键判断(sc >>> RESIZE_STAMP_SHIFT) != rs会将扩容操作拦截,在讲到扩容部分时,会详细说明。所以在初始化线程 A 已经完成对table的初始化,但还未执行 sizeCtl 初始化就被hang住后,其他线程是可以正常插入数据,但却不会触发扩容,直到线程 A 执行完毕 (注:上述分析的案例发生的概率极低,但即便是再小的几率也会有可能触发,此处可见 Doug 老爷子编码之严谨)

3.4、数据插入

图片请放大看
ConcurrentHashMap 并发之美

变量说明

Node 及 hashCode 其实节点类型与hashCode一一对应

  • 1、null,即table新建后,还没有内容加入分桶
  • 2、List Node,hashCode >= 0;即桶内的链表长度没有超过8
  • 3、Tree Node,hashCode == -2;红黑树
  • 4、FWD Node,hashCode == -1;标记转移节点
  • 5、ReservationNode,hashCode == -3;在computeIfAbsent()等方法使用到,本文不再展开

质疑

Ⅰ、问:[点1] 如果当前分桶 f 如果为空,那么会新建 Node 节点并将其插入,如果2个线程同时进入,不会导致数据丢失吗?

答:不会。因为CAS操作确保了赋值成功时,f 节点必须为null,如果2个线程同时进入当前操作,一定会有一个失败,进而重试。此处有一个小点,即 CAS 失败后,程序重新轮训,new Node的操作岂不是白白浪费了空间?的确是这样,不过也不太好避免;除非是为其添加重量级synchronized锁,在锁内开辟空间,不过这样又会影响性能,类似场景的操作后文还会涉及

Ⅱ、问:[点1] 如果在执行当前操作时,map发生了扩容,而成员变量 table 已经指向了新数组;而此处会将新建的 node 节点赋值给老的 table,岂不是导致了当前数据的丢失?

答:不会。同样还是CAS的功劳,扩容时如果发现 f 节点为null,会通过CAS操作将其修改为 ForwardingNode 节点,不管是当前操作还是扩容,失败的话都会触发重试

Ⅲ、问:[点2] 如果在进行赋值操作时,map触发了扩容,成员变量table已经指向了新的数组,那此处添加的新节点岂不是要丢失?

答:不会。因为在扩容时,也需要对分桶加锁,也就是在分桶粒度看的话,添加新节点与扩容是互斥的关系,正在进行添加操作的过程中,当前分桶的扩容是无法进行的

Ⅳ、问:[点2] 无论是List Node还是Tree Node,虽然有synchronized加持,但在进行最终赋值操作时,都没有CAS控制,会不会导致最终数据的不一致?

答:不会。其实要回答这个问题,首先要分析Node涉及写操作的变更场景。如下:a、正常向分桶添加、修改数据;b、扩容;c、table初始化;d、节点删除。而table初始化一定发生在当前操作之前,否则当前线程会先执行初始化操作,其他a、b、d在操作伊始都会对桶添加同步锁synchronized,保证了修改操作的同步执行

3.5、累加器

图片请放大看
ConcurrentHashMap 并发之美

整体思想

相信很多同学直观感受是:不就做个多线程计数器累加么,至于搞这么复杂?直接使用AtomicInteger不香吗?其实此处作者为了提速还是用心了良苦。累加器的核心思想与LongAdder是一致的,其本质还是想尽力避免冲突,从而提高吞吐。与扩容不同,在并发比较大的场景下,累加器很快就能达到stable状态,原因是counterCells数组的长度超过了CPU核数时,便不会继续增长。

为什么使用LongAdder而不是AtomicInteger?首先两者实现累加的机理是不一致的,AtomicInteger只有一个并发点,好处是每次累加完,都可以拿到最新的数值;弊端是多CPU下,冲突严重。LongAdder则根据使用场景动态增加并发点,带来的最大收益便是提高了写入的吞吐,但因为冲突点变多,每次统计最新值时,煞费周章。两者谈不上好坏,或谁取代谁,都要视你的应用场景而定。而CHM的size()方法的更偏向写多读少,故采用LongAdder的处理方式。本节后有关于两者的对比实验

变量说明

baseCount 定义为private volatile long baseCount; CHM的成员变量,累加时如果出现冲突,会将压力打散

counterCells 定义为private volatile long baseCount; CHM的成员变量,map的总数便是由baseCount及counterCells联合存储的,定义为:

@sun.misc.Contended (解决缓存行伪共享问题)
static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

质疑

Ⅰ、问:[点1] 既然要进行CAS控制,可以不要cellBusy == 0counterCells == as这2个判断吗?

答:可以。因为在CAS加锁成功后,还会进行double check,查看counterCells是否已经被初始化。但是直接进行CAS加锁操作会影响效率,试想如果counterCells已经被另外一个线程初始化完毕,如果有这2个判断,就可以直接跳出本次循环,否则还要进行CAS抢锁

Ⅱ、问:[点2] 会有counterCells != as的场景吗?

答:会,例如2个线程都发现counterCells == null,都进来初始化,具体场景可参见上述流程图

Ⅲ、问:[点3] 如果执行cas期间发生counterCells扩容咋办?

答:其实累加器的扩容不同于map中table数组的扩容,table的扩容是会新建Node对象,而累加器的扩容则不会新建对象,而是直接复用已创建的CounterCell对象,且数组的下标都不会发生变化,所以即便是在执行CAS期间发生了扩容,也不会影响整体计数的准确性

Ⅳ、问:[点4] Doug 老爷子是不是写漏了?居然在CAS锁外直接创建对象,如果CAS失败,这个new操作岂不是无谓之举,影响性能?

答:其实看到这里第一反应就是不够严谨,在加锁前执行这个操作容易造成 r 的无谓牺牲;但再一仔细琢磨,作者此举是有深意的,主要为以下二点:1、new操作跟分支判断等语句是很耗时的操作,放在锁外,可减少当前线程对锁的占用;2、counterCells数组不同于table数组,其最大值max介于
CPU <= max < 2*CPU。在并发较大的情况下,很快就能达到stable状态,不会一直上涨。所以这块为了性能的提升,还是煞费苦心的

Ⅴ、问:[点5] 所有进入累加主逻辑的线程,在累加结束后,全部都直接返回了,也就是不再参与后续的扩容逻辑,如果恰好本次累加后,整体长度达到阈值而又不扩容,岂不是造成CHM过载?

答:又是一个精妙的细节!的确是这样,也就是CHM不严格保证在长度达到阈值后,马上进行扩容。为什么这样设计呢?其实主要还是为了避免频繁的调用sumCount()方法,因为计算总长度的方法采用的是LongAdder分散法,每次统计长度相对来说是比较耗时的,而能进入累加主逻辑的话,表明现在并发比较大,在大并发下每个进入的流量都计算长度是得不偿失的,所以此处牺牲了及时进行CHM扩容的代价,换取了累加的高性能;而其他协助扩容的线程仅是判断分桶 f hashChode == -1才会协助扩容,同样也不会调用sumCount()方法

LongAdderAtomicLong写入性能对比,将目标值从1多线程累加至10亿,分别统计2个并发类的耗时。本来打算将CHM中计数器累加部分的代码抠出来做性能对比,但其本质上是LongAdder的思想,所以我们直接抓其精要

并发数 1 2 3 4
AtomicLong 6311 19375 21209 27508
LongAdder 11003 5252 3647 2900

注:仅测试写入性能,单位(ms)。测试用例 git@github.com:xijiu/share.git

3.6、扩容

图片请放大看
ConcurrentHashMap 并发之美

整体思想

多线程协助扩容是CHM最难最重要的部分,同时也是存在bug的部分

具体实现思路我们可先打个比方:好比我们有100块砖头需要从A搬至B,但是每人每次只能搬运10块,路途花费5分钟,假如某人完成一次任务后,发现A地还有剩余砖块,那么他还将持续工作,直至A地没有剩余砖块,他的工作才算结束。每个人进入场地前首选需要领取一张工作许可证,而管理员手中共有20张许可证,即最多允许20人同时工作。当有人开始归还许可证时,并不代表所有的砖块已经从A搬运至了B,因为虽然此时A地已经没有砖头,但并不代表所有的砖头都已搬运至B,可能有些砖头正在路上,所以只有最后一张许可证归还时,才表示所有的工作已经做完

而体现在CHM上的话,则是由transferIndex字段控制,例如map中table的长度为16,步幅为4,transferIndex的初始值为16,每个线程进入后对其进行CAS加锁操作(transferIndex = transferIndex - 4),如果加锁成功话,当前线程便获取了转移此4个节点的唯一权限,转移完毕后,如 transferIndex > 0,当前线程还会尝试对transferIndex进行加锁并转移,直至transferIndex == 0;所以本例中transferIndex存在的5个状态:16、12、8、4、0

  • 链表转移
    ConcurrentHashMap 并发之美

    如上图所示,对节点6进行扩容,分桶内的数据只会对应新table中的2个分桶,即桶6跟桶22,然后分别将之前的数据拷贝一份,并形成2个list,然后挂在新table的对应分桶下。此处为什么要新建而不是直接引用?主要是为了保证get方法的吞吐,即便是在扩容阶段,get也不受影响

  • 红黑树转移
    ConcurrentHashMap 并发之美

    其主要思想与链表转移类似,唯一不同是,红黑树拆分后可能变成2个红黑树、或者1个树1个链表、或者2个链表

质疑

Ⅰ、问:[点1] 第一个进入扩容的线程,在抢到锁至为nextTable赋值是有一点gap的,假设某个后续线程在执行时,正好处于这个gap,那nextTable == null就会成立,这样岂不是会导致当前线程误以为扩容已经结束,然后直接返回了么?这是否是一个bug?

答:的确是问题描述的这种情况,不过是否是bug值得商榷。因为首先协助扩容并不是功能上强依赖的,即便是只有一个线程在扩容,其他线程一直在等待也不会对整体功能有影响;其次这个gap存在的时间相比较整个扩容来说还是比较短的,如果某个线程正好处于这个gap对整体性能的影响可控

Ⅱ、问:[点1] (sc >>> 16) != rs这个表达式什么时候会成立?直观看代码,好像(sc >>> 16)恒等于 rs 呀?

答:好问题,其实要回答这个问题还要看结合后续的扩容逻辑来看,在扩容结束后,最后一个线程会给成员变量赋新值,赋值的顺序为:

nextTable = null;
table = nextTab;
sizeCtl = n * 2 * 0.75;

可见,他们无法做到原子操作,而是有先后顺序;设想当程序已经为table赋了新值,而sizeCtl还未被赋值时(此时sizeCtl为一个很大的负数),某个线程处理新数据添加并判断是否要扩容时,便命中了此判断,因为此时sizeCtl的高16位标记的还是旧的table长度,所以此判断还是非常严谨的。让我不禁想到了不朽名著《红楼梦》的“草蛇灰线,伏脉千里”啊,叹叹!

Ⅲ、问:[点2] 此表达式在什么场景下会成立?前面会对 transferIndex 进行CAS加锁,按理说这个表达式永远不会成立?

答:仅当前的逻辑,此表达式确实永远不会成立。可是最后一个负责扩容的线程会对所有的节点进行一遍double check,来确保所有的节点的hash值都为-1,即所有节点都完成转移

Ⅳ、问:[点2] 既然每个线程都按照严格的加锁顺序将CHM已经转移完毕,为什么最后一个线程还要执行double check?

答:如果你读源码也注意到了这点,那么恭喜你,你发现了CHM的另一个bug!的确,最后一个线程再次double check是完全没有必要的,doug 本人已经实锤,是前一个版本遗留的,会在下个版本中删去;其实我本人读到这儿时,纠结了很长时间,一直不明白作者此举用意,心想是不是上下文有些漏读的信息,导致浪费了不少时间哈。此优化具体可参看: http://cs.oswego.edu/pipermail/concurrency-interest/2020-July/017171.html

Ⅴ、问:[点1] 流程图中标注在计算最大线程时存在bug,为什么CHM真正跑起来时从来没有遇到过?

答:CHM这个控制最大参与扩容并发线程树的bug,源码是

if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
   	transferIndex <= 0)

此处其实为想获取正常参与扩容的线程数,应修改为sc == (rs << 16) + 1 || sc == (rs << 16) + MAX_RESIZERS,之所以我们实际生产过程中很少碰到,是因为首先需要线程数达到MAX_RESIZERS65536个,才有可能出问题。此bug地址 https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8214427

3.7、get方法

get方法相对简单,先上源码

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

其实也就是直接获取值,是链表或红黑树,就直接寻找,如果分桶为空,也就直接返回空;能做到这么潇洒,还是得力于volatile关键字以及CHM在扩容时对数据进行复制新建

四、总结

文中的流程图算是比较重要的信息,CHM的功能、并发、知识点全都涵盖在里面,建议读者一边看图一边参照源码,这样更能加深印象,也更容易吃透CHM

本来想做个知识点总结的,结果发现赫赫有名的CHM仅仅用到了CAS、volatile、循环以及分支判断,让我们不禁对 doug 肃然起敬,他留给我们的东西太美了

ConcurrentHashMap 并发之美

原文地址:https://www.cnblogs.com/xijiu/p/14232442.html

发表评论

评论已关闭。

相关文章