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

图2 Procedure of an insertion on an NBTree’s leaf. (The
fngerprints (fps) of the keys are set to key for brevity.)
Log-structured Insert.在NBTree中，插入操作以日志结构的方式执行。图2说明了在NBTree的叶子节点中插入一个新的键值对的步骤。首先，NBTree增加数量(①)来占用下一个空闲槽位。然后，NBTree将值(②)和键(③)写入已占用的槽。写入密钥后，新插入的代码可以在断电后继续工作。最后，NBTree更新fps(④)和bitmap(⑤)以使插入可见。我们观察到，插入中唯一的PM开销是存储键值对。此外，使用eADR，日志结构的插入方式还允许在同一个叶子上连续插入操作在CPU缓存中合并，从而减少PM写入。
In-place Update/Delete.传统的日志结构B -树，如NVTree和RNTree，通过添加新项来更新或删除键值项。另一方面，NBTree执行的是就地更新/删除。要更新一个键值对，NBTree会原地修改它的值。要删除一个条目，NBTree会将其键重置为0，使其无效。在eADR支持下，更新和删除可以通过修改和保持8字节的键或值来避免系统崩溃。就地更新方式在基于adr的PM系统中不受欢迎，因为对同一缓存行的重复融合会导致额外的延迟，特别是在倾斜工作负载[5]上运行时。使用eADR，就地更新方式充分利用CPU缓存并最小化PM行写入。

Efcient Search.搜索范围限于位图中指定的有效项。这确保了搜索操作找到的项是持久的和提交的。NBTree通过检查指纹进一步将候选条目的平均数量缩小为1。最后，NBTree扫描候选表项，筛选出未匹配的关键字和已删除的关键字。在大多数情况下，搜索操作只产生一次PM行读取，因为候选项通常是唯一的。
Crash Consistency.NBTree可以在崩溃后使用键值层恢复它的元数据层和内部节点。在恢复过程中，NBTree扫描键值块的列表，并将非零键的槽位标记为有效的键值项。然后，NBTree根据这些有效元数据重新构建元数据层和内部节点;从具有1600万个键值条目的持久叶节点中重建NBTree，单线程仅需0.32s，比从基础数据中恢复快32倍。即使在写操作(插入/更新/删除)过程中发生崩溃，NBTree也能保持一致性。如图2所示，在插入操作中，写入键(③)发生在写入值(②)之后。如果崩溃发生在写入键之后，那么完好无损的键值对仍然存在。否则，in-fight插入不会使NBTree处于不一致状态，因为被占用的槽位的key仍然是0，恢复后将被丢弃。对于更新和删除，它们可以原子完成。