NBTree: a Lock-free PM-friendly Persistent B -Tree for eADR-enab(5)
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字节指纹(哈希值),这加快了对未排序数组的键搜索。