从源码看世界:深入淺出ConcurrentSkipListMap核心原理
前言
作为一个经常使(mian)用(shi)的数据结构:跳表,我们对其应该不会感到陌生了,特别是java的跳表实现ConcurrentSkipListMap,某度查找下它的解读更是一抓一大把。但如果你看完这些文章就以为完全理解跳表的话,那可能在面试中被问得哑口无言:跳表插入节点时如何判断是否要增加层级?按概率的话具体概率是多少呢?为什么要这样设计呢?删除节点时为什么要先增加标记节点?源码中充斥着大量重复代码,为什么不作优化呢.....今天就给大家深入解读ConcurrentSkipListMap的核心原理。
建议观看文章前先了解以下内容:
- 通读ConcurrentSkipListMap源码并有一定了解
- HM Linked List及其基于marker节点的优化方式
- 其它有序集合的数据结构
授之以渔
首先,解读一个数据结构或模式甚至服务,需要先了解它的作用是什么(解决的痛点),进而推测其比较容易理解的入口,最后带着问题去剖析其核心代码,即可快速入手,剩下就是边边角角的问题了。以跳表为例,它的作用是在高并发的场景下支持快速查找有序数据,自然可以推测其获取数据的方法get()最容易掌握。通过get()可以很快地了解其结构与性能提升的奥秘,最后带着如何建立起这种结构的问题去解读put与remove方法,基本上可以应付平时使(mian)用(shi)场景了。
put方法
这里只对部分问题与代码进行解读,首先我们来看put方法,在新增一个节点后如何判断是否需要增加层级?
// 以下是doPut关于level的部分 int rnd = ThreadLocalRandom.nextSecondarySeed(); if ((rnd & 0x80000001) == 0) { // test highest and lowest bits int level = 1, max; while (((rnd >>>= 1) & 1) != 0) ++level; } if (level <= (max = h.level)) { // 创建索引节点 } else { // try to grow by one level level = max + 1; // hold in array and later pick the one to use // 创建索引节点和头部节点 } }
通过ThreadLocalRandom.nextSecondarySeed()可以得出一个随机数,由此证明是否增加层级是根据概率计算出来的,那概率是多少呢?自然是(rnd & 0x80000001) == 0的时候了。0x80000001代表32位二进数的最高位与最低位均为1,rnd与其进行与操作后等于0相当于排除了负数(负数最高位是1),排除了奇数(奇数最低位是1),即为正偶数,因此确定是否增加层级的概率为25%
当确定了增加层级后,就需要计算到底增加多少层了:具体通过while (((rnd >>>= 1) & 1) != 0)算得,即将rnd不断右移(第一个0不算),level等于其二进制连续的1的个数;最后判断是否超过当前层级,超过即增加max+1层。
为什么要这样设计?
首先,通过level查询不再是一个个的 O(n).操作,而是逐级地以O(log n)查询,并且层级越高概率越低(50% are level 1, 25% are level 2, 12.5% are level 3 and so on),满足快速查询的最重要需求;另外,插入与删除只需要局部修改,影响范围小(可以用cas代替悲观锁),在高并发场景下尤为重要(参考红黑树)[1];最后,相比二叉树其节点更少,因而占用空间更少。
remove方法
了解完put方法,你已经理解了跳表的一大部分了,接下来我们再看看remove方法:
// 部分代码不在本讲范围内,以……代替 final V doRemove(Object key, Object value) { // …… outer: for (;;) { // 找到key的前置节点 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { // …… 各种判断是否被其它线程改掉 // 接下来是remove三部曲 // 1.将value设为null if (!n.casValue(v, null)) break; // 2.增加删除标记节点 // 3.将前置节点的next指向它的next,也就是删除key节点的引用 if (!n.appendMarker(f) || !b.casNext(n, f)) findNode(key); // retry via findNode else { // 最后做些收尾工作,删除index节点并判断是否需要降层级 findPredecessor(key, cmp); // clean index if (head.right == null) tryReduceLevel(); } @SuppressWarnings("unchecked") V vv = (V)v; return vv; } } return null; }
这部分对于习惯了单线程开发思维的我们很容易产成疑惑,为什么要分成三步走呢,直接删除不是更快影响更小吗?如果你也有这个疑问,不妨先来看看以下的场景[2]:
假设有这样的链表:a -> b -> c -> d
有两个线程同时进行删除操作,线程1想把b节点删除,同时线程2想删除c,伪代码如下:
thread 1: CAS(a.next, b, b.next);
thread 2: CAS(b.next, c, c.next);
两个线程都成功操作,但c并没有删除成功,结果并不正确。表面原因是CAS了不同next指针,实际问题在于CAS next指针时无法保证参与执行的节点没有被删除!因此在HM Linked List要求同时CAS next指针的节点状态
thread 1: CAS(b, [b.next, false], [b.next, true])
thread 1: CAS(a, [b, false], [b.next, false])
thread 2: CAS(c, [c.next, false], [c.next, true])
thread 2: CAS(b, [c, false], [c.next, false])
方括号表示next指针值和marker(true表示被删除,false表示存在)。再次执行后,最后一个CAS会出错,因为b被mark了。当然要增加节点状态就复杂多了,因此Doug直接在需要删除的节点后面加上marker节点作为标记,虽然代价是其它使用场景均要判断next是否等于marker。
既然增加marker即可解决问题,为什么还要将value设为null?
其实这并不是为了删除,但也跟删除有关,再次以例子说明:
假设线程1删除a节点,根据以上结论删除前先增加marker,同时线程2将a节点的value改为另一个值:
thread 1: CAS(a.next, b, marker);
thread 2: CAS(a.value, old, new);
thread 1: CAS(preA.next, a, b.next);
可以看出,“先删除再插入”导致插入的节点被莫名丢失了(若先插入再删除结果是正确的)。同样是无法感知节点的变化导致的,只不过这次变化的是value,因此只要在增加标记之前将value设为null,线程2在执行时便会失败,进而重新进行插入操作(这也是为何value不能为null的原因)。
总结ConcurrentSkipListMap的删除三步曲:
- 将待删除节点的value设为null
- 将待删除节点与其next节点中间插入marker
- 将待删除节点与marker的引用一并删除
注意:index节点在删除时并没有先增加marker就直接删除了,理论上会出现删除失败的问题,但这并不会影响data节点。而在删除headIndex时(即降级),采取了二次确认的步骤,防止删除时插入了新的节点:
private void tryReduceLevel() { HeadIndex<K,V> h = head; HeadIndex<K,V> d; HeadIndex<K,V> e; if (h.level > 3 && (d = (HeadIndex<K,V>)h.down) != null && (e = (HeadIndex<K,V>)d.down) != null && e.right == null && d.right == null && h.right == null && casHead(h, d) && // try to set h.right != null) // recheck casHead(d, h); // try to backout }
重复代码问题
纵观ConcurrentSkipListMap的源码,会发现好几个方法如findNode、doPut、doRemove等都有几行相似的代码,无非是由于删除方法所增加的步骤导致的判断,那为什么不能将它们统一到一个共同方法里呢?Doug在findNode的注释里有解释这个问题(不得不说大神果然严瑾,如此细微的点都考虑到)
They can't easily share code because each uses the reads of fields held in locals occurring in the orders they were performed.
若能理解前面的删除与替换过程,自然就明白注释的意思。这是因为不同方法的情况不同,例如doPut允许找不到节点、doRemove删除时需要前置节点与后置节点(若有)、findNode只需要直接对比即可等等。
最后留给大家一个问题,为什么实现高并发有序集合更多使用跳表而不用红黑树等其它的数据结构呢?聪明的你一定可以解答出来的
Refernces
[1] William Pugh. A Skip List Cookbook. University of Maryland, College Park. June, 1990
[2] Java并发研究 ConcurrentSkipListMap与HM Linked List. http://blog.gssxgss.me/java-concurrency-skip-list-map-and-hm-linked-list-1/
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
使用Docker发布blazor wasm
使用Docker发布blazor wasm Blazor编译后的文件是静态文件,所以我们只需要一个支持静态页面的web server即可。根据不同项目,会用不同的容器编排,本文已无网关的情况下为例,一步一步展示如何打包进docker 需求HTTPS既然无网关,直接面向互联网,所以HTTPS显得尤为重要 HTTP/2 TLS3.0既然都是静态资源,使用H2和TLS3.0的目的是进一步加快加载速度 Compress对静态资源的压缩的目的依然是进一步加快加载速度。压缩选型为Brotli和 Gzip 压缩 Dockerfile官方的Nginx镜像,默认不支持Brotli所以需要自己准备一个具有Brotli支持的镜像,这里推荐使用自卖自夸的Nginx镜像,不仅使用最新的openssl编译(避免漏洞),还支持TLS1.3 http2 brotli和默认东八时区,且配置文件里还有配置示例。欢迎访问Docker Hub rsnow/nginx,了解更多。 发布blazor wasm截至2020.05.26,VS还不能把blazor wasm直接发布到Docker镜像仓库,所以只能自己打包 首先发布Re...
- 下一篇
python自动发送邮件(上)
最近工作中的一个项目需要自动发送一些信息邮件到指定邮箱的需求,那么如何实现Python自动发送邮件的功能呢?接下来我们就来简单的介绍下如何利用Python来实现自动发送邮件的功能。 Python SMTP发送邮件 SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议 ,说白了就是发送邮件的协议,python的smplib库对SMTP协议进行了简单的封装,提供了对SMTP的支持,可以发送纯文本邮件、HTML文件以及带附件的邮件。 首先我们构建一个SendEmailManager类,也是遵循着面向对象编程的思想来做,大体结构如下: class SendEmailManager(object): def __init__(self, **kwargs): # 初始化参数 ... def _get_conf(self, key): # 获取配置参数 ... def _init_conf(self): # 初始化配置参数 ... def _login_email(self): # 登录邮箱服务器 ... def _...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8编译安装MySQL8.0.19
- CentOS关闭SELinux安全模块
- Linux系统CentOS6、CentOS7手动修改IP地址
- Docker安装Oracle12C,快速搭建Oracle学习环境
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- 设置Eclipse缩进为4个空格,增强代码规范
- Windows10,CentOS7,CentOS8安装Nodejs环境