RocksDB Inline skiplist的插入流程

在之前的文章中，主要梳理了一下RocksDB的写入流程与组提交，了解了多线程如何写WAL与MemTable。在这篇文章中，主要细致地梳理一下MemTable是如何写入的。

MemTable有很多的实现，RocksDB实现了一个InlineSkipList的数据结构，可以让多线程并行无锁的写入数据，其中核心的数据结构是SkipList。

之前提过，MemTable的写入最外层的调用是通过WriteBatchInternal::InsertInto来实现的，在该实现中，主要通过一个MemTableInserter，传入WriteBatch的Iterate来实现写入。它遍历该写请求组内所有的WriteBatch，调用对应的Iterate，所以我们这里主要看一下MemTableInsert和Iterate的实现。

MemTableInsert继承了WriteBatch::Handler，用于遍历该WriteBatch内的内容。当遇到该内容是一个PUT操作的时候，则会调用其的PutCF函数。其入参分别是column_family_id和key与value，首先我们要通过column_family_id找出对应的Column family，并通过inplace_update_support来判断是否支持inplace update。

InlineSkipList不支持inplace update，所以最终会调用MemTable::Add函数。首先需要对KV值进行编码，计算编码后的尺寸，通过InlineSkipList::AllocateKey分配对应尺寸的内存，而对于InlineSkipList来说，也就是分配对应的可容纳对应尺寸KV的Node。

在InlineSkipList中，分配Node，首先要产生一个随机的Height，该Height主要判断新分配的Node应当处于第几层。假设这里分配的Height为3，则有三层，其中另外两层分别是索引层，指向同层的下一个节点。而本层，这里称之为零层，则指向了本层的数据节点。由于这里的Height为3，我们需要分配另外两个Prefix node，另外，还需要分配一个本层的Node，加上后续的KV值的内存，总和就是所有需要分配的内存空间尺寸。在插入节点阶段，Node中的next_[0]会存储一个int类型的数据，用于暂时记录该节点对应的Height，在插入到SkipList之后该值会恢复成指向同层的下一个节点的指针。

此种分配方式非常紧凑，对应CPU缓存也友好，相对于LevelDB存储一个KV的指针性能有所提升。在上图，我们可知返回的地址是KV的地址，所以在最终Insert这个节点的时候，我们需要将基址偏移sizeof(Node)，从而得到Node的真实地址。同时我们可以在next_[0]中获取AllocateNode中临时存放的Height。

接下来，我们需要比较该Height和当前SkipList中的最大Height做比较，假设当前最大Height小于该值，则更新当前最大高度为该值，由于可能有多个线程在进行Insert，所以这里使用了CAS来做此操作，假设当前最大高度被其它线程更新至不小于该Node的Height，则会放弃更新。

在创建InlineSkipList的时候，第一个节点为Head节点，在初始化的时候会默认为max_height高度，也就是高度为12。所以有如下图所示的一个结构，同时它的KV所占的内存为0，这是一个特殊的节点，比所有的数据都小，在任何节点之前：

(缺)

初始化的时候，所有Level节点均指向空。虽然Head初始化的时候Height设置为了12，但是实际整个SkipList的高度设置的还是1，这个存储在变量max_height_中。当在空SkipList中想要插入一个新的元素的时候，首先需要比较新节点的高度和当前SkipList的高度，假设比当前的还要高，则需要更新当前SkipList的最大高度，这个在上面也提到了。

插入节点的时候，需要借助一个Splice对象，该对象主要保存着最近一次插入的节点快照，它保存着一个prev和next的节点指针数组，由Level可以索引到对应Level的节点。比如根据当前的Node节点生成的Splice对象，则对于任意合法的Level值i，都有prev[i] < Node value < next[i]，也就是对于每一对next和prev，都会把Node的值包含在其中。

Splice的分配和Node的分配类似，基础的成员变量分别为height_，prev_和next_，分别表示着当前splice的高度，对应的prev_指针数组和next指针数组，这两个数组是成对出现的，也就是假如是Level 0，则对应的prev和next分别是prev[0]和next_[0]。prev_和next_的分配，这里使用了个小技巧，将两个指针数组分配到了对应splice对象的结尾处，对应的内存布局如下：

(缺)

接着上面提到的插入流程。由于splice未曾被使用过，所以我们需要重新计算当前height的prev和next。除了该情况，假设插入节点的高度高于splice，也需要重新计算，重新计算的时候，会设置最大高度的prev为Head，next设置为null（在比较的时候视为无穷大），同时更新splice的最大高度。

接下来我们就需要重新构建splice了。该实现主要在RecomputeSpliceLevels中，假设当前我们的最大高度为3，则我们需要分别计算Level 2，Level 1，Level 0对应的prev和next，而计算这些Level的值，我们需要依赖上一层的结果来加速查找，所以在上面分配node array部分的时候，实际分配的内存实际是sizeof(Node) * (MaxHeight_ + 1)。

所以在上述设置的时候，实际上设置的是最大高度的prev和head，在我们假设的场景内，此Level则是3，虽然我们需要的是Level 0-2的值。在计算的时候，实际调用的实现是FindSpliceForLevel来实现的，它接受一个由before和after指定的一个范围，在此范围内寻找到将对应key包含在内的prev和next节点。

假设我们当前新插入的节点，值为1，高度为1，下图为插入时候Splice的情况：

(缺)

我们要插入的新节点，最终在Level 0层会落到上述两个节点之间，经过链表的插入，最终我们会形成如下的一个SkipList：

(缺)

在插入完成之后，我们将更新splice，将新节点Height下的prev节点都设置为该节点，因为原先的prev和next之间已经不连续了。

(缺)

然后我们继续插入一个新节点，值为0，高度依旧为1。由于splice之前已经有了数据，所以我们需要校验当前的splice，试图生成每一层都能包围新节点的最小范围。

假设需要重新计算splice，我们需要重新计算Level 0到Level Height - 1的包围范围。首先需要判断splice的prev和next之间是否紧密，由程序表示即是splice->prev_[recompute_height]->Next(recomputeheight) == splice->next[recompute_height]。假设不满足，在当前的实现内是直接跳过了该层，将需要重新计算的层数加一。

当满足该条件时候，我们就可以去判断要插入的新节点是否在此Level的prev和next包围中了，假设在包围中，则直接跳出，这样就可以减少需要重新计算包围的层数；假设不包含，悲观的将重新计算的层数设置为当前新插入节点的高度，重新计算所有的层数。

我们需要根据上述步骤算出的重新计算的层数来计算所有的包围范围。计算方式和之前提到过的是一样的，依旧需要高一层的信息来算出第一层的。所以我们需要注意，我们在计算Level 0的范围的时候，需要借助Level 1，而Level 1在第一次插入的时候已经设置为(Head, Infinite)了，所以我们可以看出，当前最大Level之上的一层，永远是(Head, Infinite)范围。算出了对应的范围之后，我们就可以将该节点插入链表来完成Insert了。

由于重新计算了包围范围，在Insert的时候的splice在Level 0应当是(Head, 1)。在Insert完成之后，splice的结构应当如下所示：

(缺)

在上面我们主要讨论了Height为1的场景。假设新插入了一个节点2，该节点的Height为2的时候，该怎么处理呢？由于之前已经分析了插入的步骤，所以这里跳过细节分析了。首先该SkipList的最大高度需要更新为2，同时由于该高度高于之前的splice了，所以我们需要设置max_height的prev和next在范围(Head, Infinite)中，同时也需要设置需要重新计算的层数为2。

在分配节点的时候，其实节点有一个属性，该属性就是该节点的Height，该Height曾暂时的保存于next_[0]中，但是在插入到SkipList中之后，该next_就指向了下一个节点，所以此节点从此丢失了高度属性。

那丢失了Height对于后续的处理有没有影响呢？答案当然是没有，原因在于所有层级的基地址均由链表头Head来提供，由链表头提供对应Level的首节点，首节点也链起了下一个同Level的节点，所以即使没有Height属性，也不影响我们去获取所有大于等于该Height的节点。

下图展示了Height为4的时候的SkipList的结构：

(缺)

由上图我们可知，只需要获得Head就可以获得某个层级下所有的节点，不关心特定节点的Height属性。

上述我们讨论的是单独一个请求串行写的场景。假设我们某次写入的写请求链表长度大于1，需要进行并行写入。并行写入的实现函数依旧是InlineSkipList::Insert，但是它的参数发生了改变：将使用CAS的方式将前一个节点链接到新插入的节点中，同时不会使用穿行插入使用的Splice，而是初始化一个全新的Splice栈上变量。插入流程没有改变，只是不会缓存之前的splice了，每次都需要重新计算。当使用CAS的时候，核心的链接逻辑也发生了变化。我们需要从Level 0开始，到新节点的Height-1位置，给每一个Level的节点进行节点的链接。

首先将新节点的next节点链接到对应splice level的next节点中，而通过CAS操作尝试将splice对应的prev节点链接到新节点。注意这里是多个线程并行的插入，所以有很大的可能性之前的节点已经链接到其它的新插入节点了：

(缺)

首先将新节点next指向对应的next节点，该操作只影响新节点的数据，所以不必加锁，也不需要强内存序

(缺)

下一步，我们需要将splice的prev节点指向新节点，这个时候假设有别的线程抢先使用了该splice范围，会使得该CAS失效。失效之后，我们需要重新获取合法的splice范围，再次进行CAS操作来尝试对新节点链接入当前的链表。由此可以看出，这里主要通过CAS实现无锁的并行插入，同时由于插入范围的不同，当插入的节点落入不同的插入范围的时候，可以无锁的并发插入而不必频繁的计算splice范围。