在最开始构思存储引擎的时候，首先想到的是实现一个B+树底层的数据结构设计，B+树各个页之间的结构基本上大家的设计差不多，都是通过指针（无论是逻辑还是物理的）的方式从上层指向下层，同层之间也可能有指针，考虑到动态的分裂和收缩，一般也不会采用满n叉的空间预留设计，还是需要存储指针的，毕竟如果不是这种设计可能也就不叫B+树了。

整体的外在结构没有很大的魔改空间，下面就是页内部的实现了，很多B+树的实现中，一个B+树的节点是一个锁的粒度单位，即同一个B+树节点，或者说一个页（page）上，最多只能有一个线程能进行修改。这种设计本身一方面是基于页内的并发写没有那么多，其次，页作为一个紧密的内存区间，本身可以被快速加载到cache中，完成相关操作，同时很多页内压缩、组装结构的调整是可能涉及到页内的多项记录，即使锁粒度拆到更细收益也很少。

这种设计是一种很好的精细化锁设计，因为一个B+树包含很多节点，这种冲突在随机写概率很低，但考虑到一个问题，如果一个处于写的线程，在持有锁的时候被中断了，其他读线程也需要等等，因为数据可能是不一致的。这就有可能会造成若干us的抖动（线程调度上下文切换时间），而且读线程不能通过简单retry完成读取。这时候无锁算法的优势就突出出来了，Bw-tree[1]的思路就是通过append log的方式，用逻辑指针+CAS物理指针方法解决这个问题，读取的时候重放这条链。或者有读者想到一篇论文[2]说到实际测试中，Bw-tree的性能反而不如精细设计的锁实现。这里我们放下这种性能争论，重新思考这种设计，Bw-tree的页可以抽象成一条无锁链表，用append的方式叠加新的修改，在实现中，我们可能需要考虑这种小内存分配、log重放状态机的维护以及何时压缩的问题。究其本质，他还是以页为单位的无锁链表，还是append only的，这就让我想到，既然都CAS操作链表了，为何不复杂一些直接构成一个跳表，不仅可以无锁操作，同时也能保证数据有序，实现快速数据检索，读取和写入可以并发进行。

有了这种奇思妙想的思路，我们就可以考虑下它的可行性：

看起来可行，先需要造个跳表的轮子，同时，为了代码的复用性，在设计中，我将跳表的Key、指针、实现、回收上下文全部都采用模板抽象，具体实现采用模板impl类实现的函数，达到类似虚函数作用的0代价调用。下面开始详细说明支持删除的无锁跳表实现。

本文中的跳表参考了RocksDB的InlineSkipList[4]和Rust的Crossbeam[5]，叠加了不少RocksDB对Splice构建的优化，将Crossbeam的删除算法融合进去。构建一个正确的无锁跳表是比较困难的，开发中期在长稳测试中发现了一个平均触发时间在数小时的并发bug，花费了近一个星期复现打dump才找到这个触发场景并修复，所以吃透现成实现中每一个分支都是至关重要的，特别是无锁算法还涉及到内存序的问题（跳表中的内存顺序模型还是比较简单的）。

言归正传，回到跳表的完整设计。

因为想一劳永逸的设计个可复用的无锁跳表，跳表的所有实现抽象出去，只实现算法。所有无锁跳表可能用到的具体实现抽象如下：

看到上面接口的compare和DecodedKey，估计熟悉RocksDB的小伙伴发现这个就是Comparator，涉及到支持无锁删除，需要在指针上加上删除标志位，同指针CAS原子操作，避免一些并发问题，同时节点需要记录指针高度和引用计数，用于节点内存回收，这里需要EBR和引用计数同时配合才能达到完全无锁安全，EBR将在后续文章中详细说明。

这里简单描述下跳表的基本原理，熟悉的读者可以直接跳过wiki图文部分，直接看本设计中结构图。

引用wiki[6]对skiplist的描述：

继续贴个wiki的图，展示跳表的结构示例。

总之跳表就是一个通过概率平衡各节点查找时间复杂度的数据结构，其本质还是对链表的扩展，基于链表的无锁算法，也能很好地推导出跳表的无锁算法，RocksDB的InlineSkipList[4]实现了个不可删除的无锁跳表，可以实现读写完全并发。但我们需要支持无锁删除，需要对节点做些扩展，也就是前面接口里面看到的delete标和引用计数。

上图所示即为支持删除的跳表节点的完整数据，该图展示一个正在设置删除标的节点状态，最上面的4个指针一般被称为tower，其中3个指针被链接到跳表中，删除flag处于指针最低bit以合指针进行原子操作，在删除前需要对tower中的所有已链接指针做原子and置位delete flag，如果不能同步原子进行，需要从上往下进行，图中为正好进行了2个delete flag置位的状态。如果没有接触过无锁链表删除的读者可能已经迷糊了，后文我们展开无锁删除操作。

首先是跳表的插入操作，引用wiki的gif。

这里我们引入一个结构体splice，顾名思义，就是记录跳表插入点位置的铰接点。

需要注意的是，CAS操作的指针上最低位的带有delete flag，用于标记当前节点处于删除状态，是不能进行CAS插入的。原因如下，如果不存在这个delete flag，存在如下并发情况，由于thread 1无法在插入时候感知到prev处于删除状态，造成target节点丢失。因此在删除prev节点的时候，需要先对其指针CAS（只有一个并发删除操作返回成功）打上delete flag。同理对于删除的情况，还可能会造成应本被删除的节点又被另一个删除操作链接进去了。

为了便于理解，这里给出对应insert代码，该部分基于RocksDB的InlineSkipList进行了一系列魔改以适应无锁删除。

和插入算法类似，先根据目标节点构建splice，此时，如果节点仍在跳表中，小于height记录高度的splice next指针都应指向目标节点。确定是要删除的节点，首先对其链接的全部level指针进行CAS删除打标，如果不能完全以原子操作完成打标，则从最高层向最低层依次原子打标，level 0层竞争成功的即为成功删除者（对于同一个数据有且只有一个成功删除者）。

之后删除逻辑就和插入逻辑类似了，遵循以下原则：

同样为了便于理解，上代码，该部分基于RocksDB的InlineSkipList，针对无锁删除也进行了适配。

跳表还有个基本功能就是查找，这里的查找何标准跳表基本没有本质区别，从上层开始，可能的跳过不符合条件的节点，减少遍历读取数据比较大小的代价。这里的主要优化点在预读，在做compare这种比较费CPU的流程前，先prefetch下一个节点的内存，将内存操作和CPU计算重叠起来。查找代码可以参考这里。

为了遍历方便，迭代器也是必不可少的，代码也是参考RocksDB的实现，适配了下，支持前向遍历和反向遍历（反向是查找的变种）。

引用计数和协同删除即为无锁可删除跳表的精髓所在了。熟悉java的小伙伴可能看过java的ConcurrentSkipListMap，得益于java的GC，我们不但不担心ABA问题，同时tower随意分配随意删除，完全不用考虑内存的生命周期，而非GC类语言就需要额外的手段精细化管理内存（追求性能的代价 ）。

首先我们从协同删除开始介绍，前面我们说到，如果链表中的节点指针上被打上了delete flag，是不能在它后面链接新节点的，但如果正好大小关系导致我们必须链接在它后面怎么办呢，无锁是不能让执行线程等待其他线程的，即我们要自己把他删掉，即协同删除，看过代码应该发现了代码中的read next是如此复杂。

简而言之，它其实就做了这些事情：

这种带协同删除的read next让我们在遍历跳表的时候，顺带清理了潜在可能造成插入或删除失败的情况。如果在插入或删除操作中，CAS发现prev节点存在delete flag，重新构建当前层的splice即可自动清理掉问题prev节点。

协同删除虽然解决了无锁的问题，但引入了个新问题，就是节点何时完全脱链，这个涉及到资源的回收。这时引入常用的引用计数即可，考虑到插入、删除、协同删除并发的情况，引用计数需要遵从以下原则：

相信看到这里，读者也能理解为何前面的insert和erase中为何有那么多奇怪的约束了。这些约束保证了：

至此，一套完整的无锁支持删除的跳表框架完成，代码已经放到github上，其中缺失的头文件非常容易补全，相信读者的动手能力（笑）。本跳表用模板高度抽象，可以适配于大部分需要使用跳表实现的场景。

回到文章最初的设想，我是想在B+树页中使用跳表，但这个跳表是通用的，其实现还是比较重的（对每个level的指针做单独处理CAS操作），对于多核CPU，CAS操作也是很重的，会限制多核的扩展能力，后续的文章会介绍我深度优化的u64_mini_skip_list，将上述所有跳表实现全部压到一个u64中，通过一系列优化减少可能的原子操作指令。

文中也提到，针对无锁算法，光引用计数回收后，资源并不能立刻回收，并发线程可能在任何地方还引用着这个指针，这时候就需要GC算法了，下一篇文章将介绍EBR(epoch based reclamation)[3]，并同时构建一套实用的通用EBR框架。配合上EBR，无锁可删除跳表就能多线程并发跑起来了。

（知乎的评论老是吞。。。不知道是不是一致性没做好，在这统一回复下

看到评论中有读者提到ART性能更好，对于纯内存KV确实如此，我选择跳表主要是因为：

另外版本号能解ABA，但解不了内存回收，GC选择EBR的原因会在下一章详述。