NBTree: a Lock-free PM-friendly Persistent B -Tree for eADR-enab(5)

Lost Update/Stale Read.更新可能会永久丢失，读取可能会因为非原子状态更改而访问过时的数据。例如，结构修改操作，如分割，是B 树中最复杂的状态改变。在拆分过程中，B -Tree将旧节点的内容传输到新分配的节点中，然后用新节点替换旧节点。由于拆分不能原子性地完成，因此可能会在旧节点中发生并发更新，但在新节点中没有发生。在这种情况下，新节点面临着陈旧读取异常的风险，因为它们已经过时了。更糟糕的是，如果更新没有以适当的方式同步到新节点，它将永久丢失，导致丢失更新异常。因此，现有的B -树通常会在修改过程中锁定叶子节点。BzTree使用pmwca来保证写操作的原子性。然而，由于PMwCAS的高软件开销，BzTree的性能甚至低于基于锁的B 树。
Inconsistent Read.由于非原子状态的改变，线程可能会读取数据结构的不一致状态。例如，在B 树中保持结点排序的移位操作不能以原子方式完成。在插入或删除时，B -Tree需要通过调用一系列的加载和存储指令来移位数组元素。在移位过程中，同一个表项可能在不同的槽位出现两次，这是一种不一致的状态，可能导致读取不一致。FAST&FAIR提出了一种无锁搜索算法，能够容忍这种不一致性。在搜索过程中，如果键的左右子指针地址相同，则忽略该键。然而，当两次负载操作之间节点状态发生变化时，可能会出现读不一致的情况。

Dirty Read.由于非持久写入，读操作可能会访问未提交的脏数据。由于缺乏持久性功能的原子指令，更新何时变为全局可见和何时变为持久存在时间上的差距。在更新过程中，我们首先将数据存储在CPU缓存中，然后使用fush指令和内存屏障将其持久化。其他并发线程可能会在新的更新持续之前查看它。如果在这两个步骤之间停电，读取操作将得到未持久化的脏数据。之前的工作提出了几种方法来解决这个问题。ROART和PART使用非临时存储来防止未持久化的数据在全局可见，但这种方法不能从CPU缓存中获益。Link-and-persist和pmwca使用帮助机制，它允许读线程主动地推动未持久化的数据。然而，它增加了额外的软件开销和设计复杂性。使用eADR，脏读异常不太可能发生，因为全局可见的数据总是持久化的。
3 PM-FRIENDLY B -TREE3.1 NBTree Structure NBTree的整体架构如图1所示。在NBTree中，叶子节点的元数据和键值对分为两层。NBTree的元数据层和内部结点都在DRAM中维护。它们可以在恢复期间从PM中叶子节点的持久键值层重建。双层叶子节点设计使NBTree能够吸收DRAM中的元数据操作，大幅减少PM线访问次数。特别是叶子节点，元数据层和keyvalue层都被链接到一个单链表中。在键值层中，每个键值块都是键值条目的未排序数组。每个键值对存储一个64位的键和一个64位的负载。有效载荷的最高2个比特位(copy_bit和sync_bit)用于并发控制。对于可变长度的键值表项，NBTree存储了表示实际键或值的指针。每个叶子节点的元数据由以下字段组成:(1)fps存储叶子节点中每个键的1字节指纹(哈希值)，这加快了对未排序数组的键搜索。