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

1 INTRODUCTION 字节可寻址持久性内存(PM)，如英特尔Optane DC持久性内存模块(DCPMM)现在已商用。PM提供类似dram的性能以及类似磁盘的持久性。一般来说，配备PM的平台都支持ADR (asynchronous DRAM refresh，异步DRAM刷新)特性，这可以确保PM内存中的内容，以及已经到达内存控制器的写挂起队列(write pending queues, WPQ)的写入不受掉电影响。但是，CPU高速缓存中的写操作仍然是不稳定的。因此，需要显式的cache line fush指令和内存屏障来保证PM写的持久性。最近，随着第3代Intel Xeon可扩展处理器和第2代Intel Optane DCPMM的推出，一个名为extended ADR (eADR)的新功能已经可用。
与ADR相比，eADR进一步保证了CPU cache中的数据在崩溃后能够通过预留的能量快速回退到PM。它确保了全局可见数据在CPU缓存中的持久化，并消除了同步刷写的需求。eADR的出现不仅有利于无锁数据结构的设计，而且降低了PM写开销。在PM中建立高效的索引结构有望为内存数据库提供高性能和数据持久性。

本文提出了NBTree，一种无锁的PM友好B -树，以提供高可扩展性和低PM开销。据我们所知，NBTree是基于支持eADR的PM系统的第一个PM索引。为了实现高可扩展性，NBTree提出了一种完全无锁的并发控制协议。对于叶子节点操作，NBTree采用日志结构的插入和原地更新/删除，结合CAS原语，支持无锁访问。当插入的叶子节点已满时，NBTree用新的叶子节点替换旧的叶子节点，通过结构修改操作(SMO)来保持节点的平衡。NBTree提出了三种新颖的技术(三相SMO、同步-写和同步-读)来处理叶子节点无锁访问过程中可能出现的异常:(1)叶子节点的并发更新和删除导致的更新丢失。NBTree通过三相SMO和写时同步技术解决了这一问题。在SMO期间，当更新或删除操作于叶子节点时，它首先会就地修改旧的叶子节点。
然后，通过三相SMO将修改被动地迁移到新的叶子节点，或者使用写时同步技术主动地将修改同步到新的叶子节点。(2)并发查找操作导致的脏读或过期读。SMO叶子节点上的无锁搜索可能读取未提交的脏数据或过期数据。NBTree使用读时同步技术来检测和解决这些异常。为了进一步降低尾部延迟，我们提出了协作式SMO方法，使同一SMO叶子节点上的并发插入协同工作。对于内部节点操作，NBTree采用硬件事务内存(hardware transactional memory, HTM)实现原子写操作。同时，NBTree设计了一种移位感知的搜索算法，确保无锁的内部节点搜索到达正确的叶子节点。