Java并发研究 ConcurrentSkipListMap与HM Linked List

本文是Java并发博客的第四篇。按照同步器和并发数据结构交替的顺序,本次是并发数据结构相关。之前介绍ConcurrentLinkedQueue的时候也提到过,并发数据结构不涉及同步器特有的问题,所以相对简单一些。分析的重点在于数据结构本身。

这次的主题是ConcurrentSkipListMap。老实说个人一开始也不知道这个类,既然有ConcurrentHashMap为什么还要有ConcurrentSkipListMap?单线程环境下的TreeMap用的次数本来就不多,并发环境下带排序的Map用得就更少了。话虽这么说,但在阅读了《the art of multiprocessor programming》第14章之后,个人发现ConcurrentSkipListMap是一个非常好的学习范本,特别是Java下HM Linked List(或者叫Harris Linked List)的实际产品代码。

如果你阅读过一些分析ConcurrentSkipListMap代码的文章的话,你可能会知道SkipList,因为名字里面就包括SkipList嘛。但实际上ConcurrentSkipListMap中维护正确性的不是SkipList,而是最底下的那一层HM Linked List。换句话说核心是在HM Linked List上,而不是帮助快速访问的SkipList。

个人建议在阅读ConcurrentSkipListMap的代码之前,了解以下内容

  1. HM Linked List
  2. HM Linked List基于marker节点的优化方式
  3. 普通的(非并发环境下的)SkipList

HM Linked List是一个比较有名的并发环境下的单向链表实现,有兴趣的人可以阅读相关论文。HM Linked List的实现要求,节点能够一次CAS marker和next两个字段。在Java里面对应AtomicMarkableReference。典型实现(《the art of multiprocessor programming》第9章)如下

这里是一个ListBasedSet,即基于链表的Set。实现了contains/add/remove三个方法。基本想法是构建一个排序的链表,然后从起始节点遍历,找到指定节点(contains, remove)或者位置插入节点(add)。

你可能认为这是一个效率不高的Set实现,因为最坏情况下的时间复杂度是O(N)。但是加上SkipList之后,时间复杂度会变成O(Log(N))。这也是ConcurrentSkipListMap内部所做的事情。

回到ListBasedSet。以上实现的正确性如何证明?或者说为什么单线程环境下的单向链表(只有next指针)在并发环境下会出问题?具体出什么问题?ListBasedSet是如何解决的?

考虑如下单向链表

假设只对next指针CAS的情况,线程1想把b节点删除,同时线程2想删除c。运行中出现如下情况

两次CAS都能成功,但是c没有被删除,结果不正确。其他还有邻接节点的remove与add也会出现这种某个操作被“忽略”的情况(理论上ConcurrentSkipListMap的Index会出现这种情况,但是这可以被接受,因为正确性是由HM Linked List保证的)。表面原因是CAS了不同next指针,实际问题在于CAS next指针时无法保证参与执行的节点没有被删除。所以HM Linked List要求同时CAS next指针的节点的marker

这里方括号表示next指针值和marker(true表示被删除,false表示存在)。再次执行后,最后一个CAS会出错。因为b被mark了。具体的正确性证明建议看原论文或者《the art of multiprocessor programming》。

代码上体现上述过程的可以看remove部分的代码。第一次CAS是一个逻辑删除,之后的CAS才是真正的删除。实际实现中,只要求第一个CAS即逻辑删除成功,物理删除允许失败。原因在于add/remove中调用的find看到逻辑删除的节点,会帮助物理删除(当然,如果没有其他线程帮忙的话,物理删除的CAS肯定会成功)。其次,逻辑删除失败时,代码会从起始节点重新开始遍历和尝试删除。逻辑删除失败,一般来说是因为同一个节点被两个线程同时删除。理论上结果必须一个成功,一个失败(这是另外一个只CAS next指针时出现的问题,因为不凑巧的话两次都会返回true)。速度比较慢的线程重试时调用find,内部帮忙删除或者早已被另外一个线程删除之后,访问不到指定的节点肯定会返回false。所以这么做是正确的。

虽然HM Linked List被证明是正确的,实际实现还是不太理想。特别是AtomicMarkableReference在每次变更时会创建新的对象。C/C++可能可以通过操作next指针的某个bit来模拟marker,但是何时回收链表的节点是一个问题(remove的同时有一个遍历的线程的话你不能简单地删除节点)。

ConcurrentSkipListMap中给出的一个优化方案是在需要删除的节点的后面增加一个marker节点(设置节点值为null是针对其他问题的设计,请不要搞混)。假如我要删除以下链表的节点b,我会在b后面增加一个marker节点。

只在删除的时候增加节点的话,比起原来AtomicMarkableReference的方式要好很多。但是代码会变得比较复杂。原来只需要看a, b, c三个节点,现在要看a, b, marker, c四个节点。

使用marker的参考实现

为了保持ListBasedSet1差不多的代码,ListBasedSet2用了一个签名为next(boolean[] markHolder)的方法,帮助跳过marker节点。同时,ListBasedSet2为了区分普通和marker节点,增加了NodeKind枚举。marker节点的内容无意义,所以简单的设置为null。注意,你需要很小心,不能在一个普通节点后面插入两个marker节点,也不能在普通节点和之后的marker节点中间插入节点。

你可能会注意到ListBasedSet1和ListBasedSet2使用了head和tail两个哨兵节点(sentinel node),以及按照hashCode大小排序。实际代码中tail不会被用到,其次由用户传入一个比较器(comparator)更好。以下是不使用tail和允许用户传入比较器的实现

以上代码比较麻烦的是,因为了没有了tail,你需要时刻注意当前节点current是否为null。

以下的ListBasedSet4是个人写的最终版本,与前面的类不同的地方在于允许替换值。注意,HM Linked List默认在碰到相等的值的时候,是不会对节点做任何操作的。在Set的范畴内是正确的,但是在Map中,这很难保证。用户可能会传入相同的key,但是不同的value。所以,你需要一种方式能够允许用户替换值。

在HM Linked List中,直接替换值会碰到一个问题:替换了逻辑删除的节点的值,考虑如下执行序列

理论上,逻辑删除了的节点你是不能去替换的。但是现有策略无法给以上这种执行策略一个先后顺序,所以,ConcurrentSkipListMap提供了第二个逻辑删除的策略,即设置CAS值为null。即删除过程变成了三步

  1. CAS item not null -> null
  2. append marker
  3. CAS predecessor’s next pointer to successor

这样做的好处是,第一步之后,替换的线程会失败。坏处是null不能作为节点值,以及代码会更加复杂。

你可以看到在所有值比较之前,必须先检查当前值是否null。以上代码实际上已经很接近ConcurrentSkipListMap里面Node的用法了。在看如何套上SkipList代码之前,看一下SkipList的基本实现

以上是《the art of multiprocessor programming》第14章使用的SkipList的简化版。老实说比ConcurrentSkipListMap简单太多了。有tail,不用一直检查null。最高层固定,使用随机数决定节点层数。

接下来是第14章中最终版本的SkipListBasedSet,使用HM Linked List(ListBasedSet1)+SkipList。

注意这个类的不变量:书中提到以最后一行为准。因为SkipList其实是多个List的层叠,要所有层都保证一致比较困难。另外具体上述代码的分析,有兴趣的人建议阅读原书。

准备知识至此为主结束。接下来,分析ConcurrentSkipListMap特有的一些设计。

最下层不用说,就是一个HM Linked List。使用marker节点标示删除,同时在设置marker节点之前会CAS item为null。SkipList

  • 一开始只有一层,随着节点插入,根据随机得到的层数增长层数,最大包括底层为32层
  • 节点被删除时,有可能会减少层数
  • 右侧没有tail,个人觉得是因为同时增长head和tail比较困难,以及实际运行中可以不需要
  • 底层以外,Index层不使用marker节点,可能会有并发问题,但是同样以底层为准,所以影响不大

包括以上所有特性的ConcurrentSkipListMap简化版

代码中contains/add/remove使用nextNotMarker,contains2/add2/remove2更接近ConcurrentSkipListMap源代码。

代码复杂度contains < remove < add。

首先讲一下contains。contains比contains2要简单,原因在底层HM Linked List时不会帮助删除节点。所以可以像普通单向链表直接遍历。跳过null和小于目标值的节点。获取起始节点findNode方法和ConcurrentSkipListMap的findNode没有关系,要说的话,更像findPredecessor。findNode会从最上层Index开始,帮助删除已删除节点的Index,同时一直向下得到离目标值最近的节点,包括节点本身,返回前置还是节点本身由参数onlyPredecessor决定。

contain2比contains要复杂一些。因为要帮助删除节点,所以需要得到前置节点。其次,在当前节点被逻辑删除时,会根据当前是哪一步决定做什么。假如值被设置为null的话,那么就增加marker节点。如果marker节点存在,那么就物理删除节点。这里是否可以一步到位,反正值已经被设置为null,直接物理删除是否可以?或者说marker节点不加可以么?个人觉得理论上可能可以,但是一定几率会造成值为null的节点没有被物理删除成为数据结构中的垃圾数据,比如之前说的邻接节点同时删除的情况。

接下来是remove2,删除同样有一段help delete的过程,在找到节点之后,首先CAS item为null,接下来根据successor的情况,加marker和物理删除。由于值为null已经是一次逻辑删除了。所以加marker可以失败,物理删除也是。删除最后有一个尝试降低层级的过程。ConcurrentSkipListMap在层数大于3,并且顶层3层都没有Index(除了Head)的时候,会尝试下降一级,如果此时有新Index插入,那么会放弃下降。

最后是最复杂的add2,说它复杂是因为代码很多,ConcurrentSkipListMap全部写在一起。个人按照功能分离了好几个方法出来。首先是常规的HM Linked List插入。允许值替换。如果值替换了,直接返回。接下来是创建索引。使用xorshift生成一个随机数,从尾部开始计算连续1的数量。这个randomLevel个人本地测试了下,大致满足level越大出现次数越小的分布。当然你插入节点的位置你不能控制,所以还是拼运气。根据randomLevel,Head有可能会增高一层。也有可能不变。增高时有可能同时碰到删除引起的高度下降,理论上会碰到ABA问题,应该使用AtomicStampedReference,个人认为这里不用是因为SkipList并不参与不变量,所以一定的不稳定可以忍受。最后在SkipList插入新节点的索引。注意,因为SkipList没有使用HM Linked List,所以理论上有可能会出现没有删除,或者没加成功的情况,但是一方面几率小,另一方面可以忍受。

最后小结一下ConcurrentSkipListMap。ConcurrentSkipListMap依赖HM Linked List,使用marker节点优化。SkipList本身是一种随机数据结构,在并发环境下,SkipList能和HM Linked List很好地结合起来,避开类似基于数组的Map的resize等问题。由于是两种数据结构的组合,代码会比较复杂,但是值得阅读和思考。