面向持久性内存的写优化B+Tree索引结构
Write-Optimized B+ Tree Index Technology for Persistent Memory
-
摘要: 1 、研究背景（ context ）
近年来，以PCM为代表的持久性内存技术（Persistent Memory，PM）正在快速的发展，特别是Intel Optane DC Persistent Memory的商业使用，成为学术界和工业界近年来研究的热点。持久性内存具有可字节寻址的特点，这使得持久性内存可以直接挂载到内存总线上，并通过load/store指令对其直接访问。另外持久性内存具有类似DRAM的读写延迟以及高密度、低功耗等优点，有望取代DRAM成为新一代的主存设备。此外，持久性内存的非易失性，可以直接将数据持久化到上面。因此，持久化内存技术的出现在理论上可以将内存和主存合并，简化存储架构。
2 、目的（ Objective ）：
尽管持久性内存有诸多优点，但它也具有读写不对称，写次数有限以及掉电不易失引起的数据不一致问题。因此，持久性内存的出现虽然给计算机架构的发展带来了机遇，但是也给传统的软件技术带来了挑战。特别是以B+Tree为代表的索引技术，主要是针对DRAM和磁盘的特点设计的，直接将其迁移到持久性内存架构上，会导致其快速的磨破。比如，B+Tree中重排序会引起大量移位写操作，对于掉电易失、无擦写次数限制和读写对称的DRAM来说，它不会显著的影响索引性能。但是在持久性内存中，重排序和日志预写操作会引起大量的写操作。由于CPU的乱序写操作以及原子写粒度不匹配的问题，为了维护数据一致性，持久性内存中的写操作需要频繁的调用mfence和clflush指令，造成索引性能大幅下降。因此，针对持久性内存的特性设计一种面向持久性内存的B+Tree索引结构具有非常重要的应用价值。
3 、方法（ Method ）
针对持久性内存的特性，本文提出了一种面向持久性内存的写优化B+Tree索引技术WO-Tree。WO-Tree对叶子节点采用“追加写”机制，可以减少插入过程中维护节点内部有序性引起的大量写操作。WO-Tree对内部节点采用延迟刷新机制，以脏缓存行大小为刷新粒度，可以减少内部节点更新过程中的写次数。WO-tree在叶子节点分裂时，当所有的写操作完成后，再进行数据刷新操作，可以减少频繁的数据刷新。WO-Tree采用了部分写日志机制，只对叶子节点上的关键数据写日志，内部节点通过读操作识别数据不一致，并利用叶子节点数据进行索引重建，可以减少日志写开销。WO-Tree在内部节点采用无锁搜索，可以减少线程访问时的锁开销。
4 、结果（ Result&Findings ）：
在YCSB生成的负载上进行插入、删除等测试，实验结果表明，以插入操作为例，相比传统的B+Tree、wB Tree和Fast-Fair，当节点大小为1KB时，WO-Tree插入操作引起的cacheline的刷新次数分别减少了84.7%、22.2%和30.8%。在多线程并发的情况，当线程数为2时，相比传统的B+Tree、wB Tree和Fast-Fair插入操作完成的时间分别减少了84.3%、27.3%和44.7%，并且随着线程数的增加，WO-Tree表现出更显著的并发能力。
5 、结论（ Conclusions ）：
WO-Tree通过“追加写“的方式来解决重排序的问题，并且内部节点采取了延迟刷新的策略减少数据迁移引起的刷新操作。针对叶子节点分裂操作引起的大量写，同样采取了延迟刷新的机制。为了减少日志写开销，WO-Tree采取了部分写日志的方法，仅对叶子节点的操作进行写日志，内部节点通过读操作识别不一致状态，并通过叶子节点数据重建索引结构。WO-Tree在内部节点中，采用了无锁搜索的机制减少锁开销。实WO-Tree在插入、删除等操作中，都能有效的减少cacheline的刷新次数，并提升了执行效率。在并发能力测试时，相比wB-Tree等索引算法，WO-Tree也获得了显著的性能提升。WO-Tree能够减少对持久性内存的写操作，并充分的发挥新硬件的特性，具有十分显著的索引性能。Abstract: Due to its low latency, byte-addressable, non-volatile, and high density, persistent memory (PM) is expected to be used to design a high-performance storage system. However, PM also has disadvantages such as limited endurance, thereby proposing challenges to traditional index technologies such as B+ tree. B+ tree is originally designed for dynamic random access memory (DRAM)-based or disk-based systems and has a large write amplification problem. The high write amplification is detrimental to a PM-based system. This paper proposes WO-tree, a write-optimized B+ tree for PM. WO-tree adopts an unordered write mechanism for the leaf nodes, and the unordered write mechanism can reduce a large number of write operations caused by maintaining the entry order in the leaf nodes. When the leaf node is split, WO-tree performs the cache line flushing operation after all write operations are completed, which can reduce frequent data flushing operations. WO-tree adopts a partial logging mechanism and it only writes the log for the leaf node. The inner node recognizes the data inconsistency by the read operation and the data can be recovered using the leaf node information, thereby significantly reducing the logging overhead. Furthermore, WO-tree adopts a lock-free search for inner nodes, which reduces the locking overhead for concurrency operation. We evaluate WO-tree using the Yahoo! Cloud Serving Benchmark (YCSB) workloads. Compared with traditional B+ tree, wB-tree, and Fast-Fair, the number of cache line flushes caused by WO-tree insertion operations is reduced by 84.7%, 22.2%, and 30.8%, respectively, and the execution time is reduced by 84.3%, 27.3%, and 44.7%, respectively.
下载: