楞二

楞二

关注
发信
关注(28)粉丝(399)

ConcurrentHashMap 并发之美

一、前言

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

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

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

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

二、概述

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

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

三、整体介绍

3.1、模型介绍

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

  • 说明：此示意图仅为展示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 并发之美-LMLPHP

3.2、宏观认识

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

ConcurrentHashMap 并发之美-LMLPHP

注：本文中，橙色线表示执行时不加任何锁；蓝色表示CAS操作；绿色表示synchronized锁

3.3、初始化

ConcurrentHashMap 并发之美-LMLPHP

变量说明

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，其低4位及高4位都有设计理念，在讲到扩容部分时会详细介绍

质疑

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

3.4、数据插入

ConcurrentHashMap 并发之美-LMLPHP

变量说明

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个线程同时进入，不会导致数据丢失吗？

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

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

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

3.5、累加器

ConcurrentHashMap 并发之美-LMLPHP

整体思想

相信很多同学直观感受是：不就做个多线程计数器累加么，至于搞这么复杂？直接使用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 == 0及counterCells == as这2个判断吗？

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

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

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

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

附

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

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

3.6、扩容

ConcurrentHashMap 并发之美-LMLPHP

整体思想

多线程协助扩容是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 并发之美-LMLPHP

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

  • 红黑树转移
    ConcurrentHashMap 并发之美-LMLPHP

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

质疑

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

Ⅱ、问：[点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加锁，按理说这个表达式永远不会成立？

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

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

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

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 并发之美-LMLPHP

01-05 07:40
Powered by LMLPHP ©2024 楞二 0.068798