BzTree – A High-Performance Latch-free Range Index for Non-Volatile Memory

0x00 引言

Bw-tree是lock-free的B+tree中最著名的一个。为了到达lock free，Bw-tree算法的复杂程度(不是复杂度)也是很可怕，特别是要实现一个Bw-tree，估计代码量是ART的很多倍了。Bw-tree诸多的设计都是为了在只支持单一CAS操作的硬件上实现lock free，而BzTree的设计还是利用CAS实现lock free(数据库中叫做latch free)，由于没有硬件支持多个元素的CAS操作，这里BzTree使用是利用软件实现，这里就不具体说明这个是如果实现的了，可以参考[2]。

0x01 基本思路

BzTree的实质就是一棵B+ Tree，解决的问题就是加入有了一个可以支持Multi-CAS操作的库，如何讲B+ Tree变成latch free 的呢？先来看看PMwCAS(Persistent Multi-Word CAS)[2]的API:

• AllocateDescriptor(callback = default): Allocate a descriptor that will be used throughout the PMwCAS operation. The user can provide a custom callback function for recycling memory pointed to by the words in the PMwCAS operation.

• Descriptor::AddWord(address, expected, desired): Spec- ify a word to be modified. The caller provides the address of the word, the expected value and the desired value.

• Descriptor::ReserveEntry(addr, expected, policy): Similar to AddWord except the new value is left unspecified; returns a pointer to the new_value field so it can be filled in later. Memory referenced by old_value/new_value will be recycled according to the specified policy.

• Descriptor::RemoveWord(address): Remove the word previously specified as part of the PMwCAS.
• PMwCAS(descriptor): Execute the PMwCAS and return true if succeeded.

• Discard(descriptor): Cancel the PMwCAS (only valid before calling PMwCAS). No specified word will be modified.

BzTree Nodes

一个BzTree的节点由以下的部分组成，

• Header，一个固定长度的header，包含了一个node-size字段，表示这个node整个的长度；一个status word字段，表示保存一个元数据，被用于在协调更新这个节点的操作；一个sorted-count字段，表示最后一个已经排序好的index，这个之后的都是还没有排好序的。

• Record metadata array，记录每一个数据项的一些元数据，

  (1) flag bits (4 bits) that are broken into PMwCAS control bits (3 bits) used as internal metadata for the PMwCAS (e.g., to mark dirty words that require a flush) along with a visible flag (1 bit) used to mark a record as visible, (2) an offset value (28 bits) points to the full record entry in the key-value storage block, (3) a key length field (16 bits) stores the variable-length key size, and (4) a total length field (16 bits) stores the total length of the record block; subtracting key length from this value provides the record payload size.
  

• Free space，空闲的空间，用于调添加新的数据，

• Record storage block，保存的就是数据项，为key-value pair，

• Status word，在更新的时候使用的元数据，

  (1) PMwCAS control bits (3 bits) used to atomically update the word, (2) a frozen flag (1 bit) that signals that the node is immutable, (3) a record count field (16 bits) that stores the total number of entries in the record metadata array, (4) a block size field (22 bits) storing the number of bytes occupied by the record storage block at the end of the node, and (5) a delete size field (22 bits) that stores the amount of logically deleted space on the node, which is useful for deciding when to merge or reorganize the node. Status words for internal nodes only contain the first two fields; this is because we do not perform singleton updates on internal nodes and thus do not need the other fields.
  

  内部节点和叶子节点除了上面的status work字段不同之外，另外的不同之处在于内部节点一旦创建就是不可变的，它只保存一句排好序的key的记录，不包含空闲的空间，Free space。

  除了这些节点外，一个BzTree存在的结果就是：1. root pointer，指向root节点的指针；2. Global index epoch，在持久化模式的时候，即数据都保存在NVM上面的时候。这个字段会在每一个重启的时候自增，用于探明在crash的时候没有完全完成的工作。

Leaf Node Operations

• 添加操作，这一步先检查经典的Frozen标志，如果已经被设置，那么表示这个节点是不可变的，可能已经被删除了，不在是这个Tree结构的一部分，这个时候操作必须重试。如果找到了合适的节点，这里就要完成两个CAS的操作，一个是修改status字段的record count部分和Block Size的部分，一个是修改offset，翻转offset的高位的bit，把剩余的部分设置为global index epoch，这里这么做在crash之后的恢复中使用，这里使用offset的高位的bit来表明这个是一个allocation epoch还是一个offfset的含义，

   The offset field is overridden during this phase to remember the allocation’s index epoch. We refer to this value as the allocation epoch and use it for recovery purposes (explained later). We steal the high-order bit to signal whether the value is an allocation epoch (set) or actual record offset (unset).
  

  前面这里的操作是为了给添加的数据预留空间，预留成功之后，拷贝数据，将visible字段设置为可见。因为在CPU Cache中的数据持久化到NVM上，必须使用 CLWB or CLFLUSH指令刷洗一下Cahce。在此之后还要重新检查Frozen字段，如果已经被设置，这个操作就应该abort并重试。如果检查通过，这里还要进行两个CAS操作，一个就是设置visible字段和offset字段，一个就是设置status word为同一个值，这里的目的是为了探测与这个操作冲突的设置forzen bit的操作。如果操作成功，表示整个操作已经成功了，如果没有，则重新检查Frozen Bit。

  这里还有一个问题就是探测并发添加操作时候的相同的可以的问题，这里使用了一个乐观的机制，在检查了已经排序好的部分和没有排序的部分之后。然后如果发现了正在执行添加操作但是没有完成的，就设置一个re-check的表示，在自己添加完成之后，重新检查没有排序的部分。如果发现了相同的key，就通过清楚添加的数据和设置offset字段为0来撤销自己的操作。（这里咸鱼觉得可以有一个更加简单的办法,emmmm)。

• 删除操作，这里的也是2个CAS的操作，一个是设置visiable和offset字段为0，一个是设置增加delete size字段的值。如果这里由于并发的操作失败，就重试。

• 更新操作，这里要分为两种情况，1. 如果节点里面保存的是记录的指针，这个就可以直接更新，不过这里还是需要3个CAS操作，一个是设置这个值的指针为新的值，一个是设置这一个数据项的元数据为这个元数据相同的值，为的是检测并发的相冲突的操作，一个是status word为这个字段的相同的值，也为的是检测冲突的操作；2. 如果这个数据是inline在节点里面的，这个时候的操作就要麻烦一些，因为这些数据可能超过了64bit，这里和添加操作的方式类型，也是需要分配新的空间，这里保存的只会是数据的diff信息：

  If leaf nodes store full payloads, the update follows the same protocol as an insert by (1) allocating space in the metadata array and record storage block and (2) writing a (key, update_payload) record into the record block that describes the update. The update_payload can be either a full payload replacement or a “byte diff” describing only the part(s) of the payload that have changed.
  

• Upsert，如果不存在则添加，存在则更新，这里就是先判断存不存在，然后根据这个来执行相应到的操作即可。

• 读取操作和范围扫描，BzTree中的read操作不会被更新、添加的操作阻塞，在这里就是找到数据可能存在的节点，在已经排序的部分执行二分查找，在没有排序的部分执行顺序查找即可。读的操作不用关心frozen bit，可不会在visible 为false的节点数据中查找。对于范围操作来说，为了处理并发操作和一个节点中存在排序和没有排序的两部分的数据，这里使用的将这些数据拷贝到一个新的地方并排好序，然后处理。

Leaf Node Consolidation

这里要处理的就是经过了删除和添加操作的值，在一个节点里面的查找的操作的效率就会变低。这里使用的方式就是先设置这个frozen bit。然后开辟性的新的空间将这些存活的数据拷贝到这里面，如果这里需要的空间大于了节点最大的大小的限制的时候，就需要将这个节点分裂. 不需要分裂操作的时候，知道这个节点的父节点，执行下面的2个CAS的操作：

(1) the 64-bit child pointer in r to install the pointer to N′ and 

(2) P’s status word to detect a concurrent page freeze.

这个时候也并不能将旧的节点立即删除，这里使用的方法也是很常见的基于epoch的方法。另外，这里处理在进行这个操作的时候并发更新操作的策略是如果一个线程因为frozen bit的原因重试操作了，然后有在一次遇到了这个情况，这个时候这个线程自己也启动一个consolidation的操作，当然，这样的话最终只会有一个成功，

If they again land on a frozen node, this is a signal to help along to complete the consolidation instead of “spinning” by continuously re-traversing the index hoping for a live node. In this case, each thread will start its own consolidate process and attempt to install it at the parent. This effectively makes threads race to install a consolidated node, though one will ultimately win. Afterward, each thread resumes its original operation.

对于internal节点的操作，基本的方式和leaf节点的操作是基本相同的。不同的地方在于前面提到的internal的节点都是不可变的，所以这里的每一次的更新的操作都会产生一个新的版本。

Structure Modifications

这里讨论就是节点分裂和合并的问题，

• Node Split，分裂操作分为2步，1. 分配新的节点，这里就是选择一个合适的key将数据分为2个部分。这里不会在原来的节点上面修改，而是创建2个新的节点，2. 修改这个节点的父节点，原子性的将新的节点添加到Tree中，这里也是利用了和之前类似的CAS的操作,

  The installation is atomic and involves using a 3-word PMwCAS to modify the following words (1) the status word of P to set its frozen bit, failure to set the bit means it conflicts with another update to P, (2) the 64-bit child pointer to P at its parent G (N ’s grandparent) to swap in the new pointer to P′, and (3) G’s status word to detect a concurrent page freeze. 
  

• Node Merge，如果一个节点的数据小于了一定的值，这个时候就会检查它的左右兄弟，是否可以满足合并的条件。这里的条件就是它们必须是同一个父节点以及它们何必之后的数据也会小于导致节点分裂的数据大小。这里也是分为2步，1. 设置要合并的两个节点的frozen bit，然后根据要合并的节点创建新的节点，2. 修改这个节点的父节点。

0x02 Durability & Recovery

对于Durability主要要处理的就是和CPU Cache相关的一些问题，这里就是要注意mfence的时间，对于变长的数据，

That is, newly inserted record memory on a node is flushed before the atomic flip of its visible bit. Likewise, new node memory is flushed before it is “linked into” the index using a PMwCAS. This flush-before- visible protocol ensures that variable-length data in the BzTree is durable when it becomes readable to concurrent threads.

对于Word-size的数据，这里就是由PMwCAS操作来保证的。对于Recovery的操作，主要要处理的就是无用内存的回收的问题，因为crash，一些已经分配的内存的擦走并没有操作成功，这些数据有的需要被回收，还有的就是将已经标记为成功的PMwCAS持久化，向前推进完成。对于没有完成操作就会滚，

Then, the PMwCAS library executes its recovery algorithm to ensure that the effects of all successfully completed PMwCAS operations are persisted. As covered in Section 2.3, upon restart after a crash, any in-flight PMwCAS operations marked as succeeded will roll forward, otherwise they will roll back. 

0x03 评估

一个简单的性能数据，具体的可以参看[1],

参考

1. Joy Arulraj, Justin Levandoski, Umar Farooq Minhas,Per-Ake Larson. BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory. PVLDB, 11(4): xxxx-yyyy, 2018. DOI: https://doi.org/10.1145/3164135.3164147
2. Easy Lock-Free Indexing in Non-Volatile Memory, ICDE 2018.