面向非易失性内存的持久索引数据结构研究综述

面向非易失性内存的持久索引数据结构研究综述

王永锋, 陈志广

中山大学计算机学院，广东 广州 510006

 摘要：随着非易失性内存从理论走向实用，现代存储系统的设计与实现将迎来颠覆性变革。针对传统存储设备设计的存储系统并不能充分利用非易失性内存带来的性能红利。为了构建高吞吐、低时延、大规模的存储系统，迫切需要设计与非易失性内存硬件特性相匹配的持久索引数据结构，从而进一步提升性能。从持久索引数据结构出发，分别对B+-Tree和哈希表在非易失性内存上的设计和优化进行分析，比较其优缺点，并展望了该方向的机遇与面临的挑战。

关键词： 存储系统 ; 非易失性内存 ; 持久索引数据结构 ; 性能优化

论文引用格式：

王永锋, 陈志广. 面向非易失性内存的持久索引数据结构研究综述[J]. 大数据, 2021, 7(6): 78-88.

WANG Y F, CHEN Z G. A survey of persistent index data structures on non-volatile memory[J]. Big Data Research, 2021, 7(6): 78-88.

1 引言

非易失性内存是一种新兴的存储介质，其具备字节可寻址、内存级别读写时延的特性，这给当前大量的存储系统带来了根本性的变革。非易失性内存正在迅速发展，现有的大部分非易失性内存（如相变内存、STT-RAM等）仍处于研究阶段，但由美光科技有限公司和英特尔联合研制的傲腾持久内存（基于3D XPoint）已经发布，并且投入市场。由此，在存储系统中尽可 能发挥非易失性内存性能优势的需求越发迫切。其中，面向非易失内存研发新型持久索引数据结构是解决该问题的关键。

在存储系统的设计与实现中，持久索引数据结构是核心之一。文件系统中文件路径到索引节点的寻址、大文件中偏移量到指定数据块的寻址、键值存储系统中根据键寻找值的数据结构、数据库中的聚集索引等，都需要持久存储的索引数据结构，且这些持久索引数据结构的实现对系统本身的性能至关重要。但这些持久索引数据结构目前大多面向传统存储设备进行优化，而不能高效利用非易失性内存的硬件特性。将这些持久索引数据结构在非易失性内存上重新设计实现，并面向非易失性内存的硬件特性进行优化，能够大大降低存储系统的时延、提升吞吐量。

提高持久索引数据结构的性能是实现低时延、高吞吐的现代存储系统亟须解决的问题。针对大量在非易失性内存上优化持久索引数据结构的工作，笔者对其进行分类、汇总、对比，厘清索引数据结构的发展主线，总结其中的关键挑战，并对其发展趋势进行展望。

2 持久索引数据结构

2.1 索引数据结构的分类

在不同的场景中，对索引数据结构中存储的数据有不同的假定。构建在关系型数据库中的索引数据结构往往需要处理大量的范围查询，即查询在某个区间内的所有键值对。为了高效支持范围查询，索引数据结构需要维护数据的有序性，并针对范围查询进行优化。而在一些键值存储系统中，可能仅输入指定的键，要求系统返回对应的值，不需要范围查询，此时底层的索引数据结构就不需要额外的开销来维护数据的有序性，相邻的键值对可以存放在存储设备上的任意位置。因此，根据其内部数据结构对数据有序性的维护情况，可以将索引数据结构分为有序索引数据结构和无序索引数据结构。

有序索引数据结构需要严格维护数据结构中的有序性。对于每一次写入操作，有序索引数据结构都需要根据插入的数据对整体的结构进行修改以保证有序性，因此范围查询的性能最好。哈希表完全不维护数据结构中的有序性，因此一般而言额外开销最小，但无法对范围查询进行优化。另外，在有序索引数据结构中，维护有序性会带来大量开销，因此一些面向写优化的有序索引数据结构会放松一部分对有序性的约束，从而提升写性能。

除了传统索引，新兴的学习索引（learning index）将索引任务变为一个回归问题，能够根据输入数据自适应地调整数据的存放模式。

2.2 面向非易失性内存的索引数据结构关键问题

为了能够让索引数据结构在传统的存储设备（如机械硬盘、固态硬盘）中进行持久存储，并且高效地利用硬件特性，很多研究人员进行了大量的研究工作。随着新型存储设备（如非易失性内存）渐渐成熟，研究人员分析了非易失性内存和传统存储设备的差异，并且就索引数据结构的设计提出了不少新颖的方法。具体地说，在非易失性内存上实现持久索引数据结构，需要解决以下3个问题。

● 如何减少在操作持久索引数据结构时的软件开销p>

● 如何针对特定的持久化语义实现崩溃一致性保证p>

● 在非易失性内存上如何利用多核架构高效并发处理读写请求p>

索引数据结构的软件开销逐渐成为限制性能的关键因素。传统存储设备的持久化时延往往是微秒级甚至毫秒级，而内存的时延最多不过一百多纳秒，因此在传统存储设备上的持久索引数据结构并不需要过多地关注与内存读写相关的软件开销，而是更多地关注如何通过写聚合等方式尽可能减小持久化的开销。但在非易失性内存的背景之下，持久化开销与内存的读写相近，如傲腾内存的写时延为62 ns，而读时延为169~305 ns，过去的一些略微提高软件开销、降低持久化开销的优化手段无法被直接应用在非易失性内存中，软件开销对性能的影响大大增加。同时，缓存未命中、流水线停顿等体系架构层面的性能损失也会对构建在非易失性内存之上的索引数据结构有较大的影响。如为了进一步降低开销，MOD将持久化所需要的内存屏障进一步降低，以提升性能。另外，为了降低开销，还需要尽可能解决读写放大的问题，有工作指出，由于傲腾内存的内部读写粒度为256 byte，小于256 byte的读写均可能带来写放大，这会对索引数据结构的性能有所影响。

同时，需要重新思考崩溃一致性的实现。传统存储设备基于块设备的抽象、操作和读写都以块为单位（更具体地说，机械硬盘的读写粒度为扇区，大小一般是512 byte，固态硬盘的读写粒度为闪存页，大小一般是4 KB），只要相应的块或页被写入存储设备，即完成了持久化。但在非易失性内存中，一般的store指令原子操作粒度仅为8 byte，且该指令会由于CPU的乱序执行而难以按照开发者预想的顺序写入存储。另外，数据会首先写入CPU的L1/L2/L3缓存中，而CPU的缓存并不能保证持久化。因此，为了保证让数据在非易失性内存上持久化存储，需要在store指令后相应地加入内存屏障和刷写缓存行指令（如clflush或clwb），将缓存行从CPU缓存刷到非易失性内存里。由此，非易失性内存上需要新的方法来保证崩溃一致性。

另外，面对海量的读写请求，需要设计适合多核架构的索引数据结构。由于极低的时延以及字节可寻址的特性，与传统存储设备相比，构建在非易失性内存之上的索引数据结构的吞吐量有多个数量级的优势，在多核架构上非易失性内存的优势将更加显著。尽管如此，由于前面提到的两个问题，能够在动态随机存取存储器（dynamic random access memory， DRAM）上使用的并行索引数据结构并不能直接用于非易失性内存上。另外，由于非易失性内存额外引入的刷写缓存行操作，以及傲腾内存在线程数过多时带宽反而会下降，需要对索引数据结构上的并发读写做进一步的优化，才能够充分适应非易失性内存的特性。

3 有序索引数据结构在非易失性内存上的实现

有序索引数据结构能够高效地处理范围查询任务，其中的一种实现——B/B+Tree能够显著地减少磁盘I/O的次数，已经被广泛应用到InnoDB等存储引擎中。针对B/B+-Tree在非易失性内存上的实现，笔者总结了下面的工作，并分析了其优劣。其中2011—2018年的工作都是在模拟的非易失内存模拟器上完成的，之后的工作才开始在真实的傲腾内存上实现。

2011年Venkataraman S等人首次提出了针对非易失性内存设计的CDDS B-Tree。他们使用mfence（内存屏障）和clflush（刷写缓存行）的组合指令来保证数据按顺序写入非易失性内存中，在B-Tree的基础上，使用多版本机制实现更新操作，另外通过写时复制实现节点的分裂和合并，从而减少了额外的写入，无须通过写日志保证崩溃一致性。但是使用多版本和写时复制的代价是需要后台线程来进行垃圾回收，这会带来额外的性能开销。

2015年Yang J等人对非易失性内存上的B+-Tree进行了改进，提出了能够进一步降低维护一致性开销的NV-Tree。通过深入分析，他们发现在叶子节点维护顺序存放的键值需要刷写多个缓存行，另外还需要维护B+-Tree的内部节点的崩溃一致性，这些引入了大量开销。为了进一步优化，该文章提出可以让叶子节点存放的键值对乱序，具体的实现是使用日志结构写入。另外，由于内部节点可以重建，不需要额外维护内部节点的崩溃一致性。但由于叶子节点没有维护顺序，这种方法对读操作的性能造成了一定的影响。

2015年Chen S M等人基于参考文献[14]进一步优化了B+-Tree在非易失性内存上的实现，提出了wB+-Tree。如果叶子节点没有维护键值对的顺序，就会影响读操作的性能，因此该文章在叶子节点中使用位图记录槽的分配情况，并进一步增加槽数组（slot array）用于记录键值的顺序，优化读操作。另外针对崩溃一致性的实现，wB+-Tree在插入操作和更新操作中，都先在节点中寻找空的或无用的槽写入并保证持久化，然后通过一次8 byte的原子写入和持久化修改元数据，从而完成操作。这样的实现使用非易失性内存上的8 byte原子写入指令保证崩溃一致性，但节点分裂操作依然使用了传统的重做日志方法，带来了额外的写入。

2016年Oukid I等人结合参考文献[14]提到的分析，在非易失性内存上进一步优化了B+-Tree，提出了FPTree。基于内部节点可以通过叶子节点重建的原理， FPTree将所有内部节点都放在DRAM里，只将叶子节点持久化存放在非易失性内存中，减小维护崩溃一致性的开销。同时FPTree在叶子节点中存放了每个键各1 byte的指纹，用于快速判断指定键是否在该叶子节点中，从而降低叶子节点无序存放键值对读操作的影响。为了进一步降低软件开销，优化并发，FPTree将分配内存的开销分摊到多个节点上，并结合硬件事务内存降低了并发访问的开销。

2018年Arulraj J等人 基于PMwCAS在非易失性内存上实现了能够无锁并发的BzTree。比较并交换（compare and swap，CAS）指令是实现无锁并发算法的关键指令，其能够对单个字节进行原子的比较和交换操作，而PMwCAS将该操作扩展到多个字节且保证非易失性内存上的持久化。通过PMwCAS提供的原子性，开发者可以避免非易失性内存带来的编程细节，使用通用的方法在非易失性内存上实现支持崩溃一致性且无锁并发的BzTree。

2020年Chen Y M等人发现非易失性内存上的B+-Tre e有较严重的长尾时延，经过深入分析后，他们认为在非易失性内存中对叶子节点的结构进行改变的操作（排序和节点平衡）以及并发线程之间相互等待访问非易失性内存是造成长尾时延的根本原因。基于这样的分析，他们提出uTree。uTree的内部节点组织与一般B+-Tree相同，存放在内存上，而叶子节点分成内存中的数组层与存放在非易失性内存上的链表层。该设计能让造成长尾时延的操作在内存上完成，而在非易失性内存上可以并行操作链表的个别元素。这样的设计缓解了长尾时延，但也增加了索引数据结构的内存占用。

2020年Liu J H等人在3D XPoint上优化了B+-Tree，提出了LB+Trees。他们充分利用了3D XPoint上内部介质读写粒度为256 byte和持久化粒度为64 byte之间的差异，发现影响性能的是CacheLine的写入，在CacheLine写入数量相同的情况下，CacheLIne内部脏字写入是没有影响的，进而提出可以通过节点内部键值对的移动来减少内部介质读写。同时为了保证崩溃一致性，他们在wB+-Tree的实现上进一步扩展，基于类似的思路，利用8 byte的原子写保证了包括节点分裂和聚合在内的所有操作的崩溃一致性，无须写日志，并且还能够通过分布式头元数据的方式扩大叶子节点的大小（256 byte的倍数）而不牺牲崩溃一致性。

B/B+-Tre e在非易失内存上的实现及优缺点见表1。除了B/B+-Tree之外，在非易失性内存上进行优化的有序索引数据结构还包括基数树（radix tree）以及其变体，如WORT、P-ART、HART、DPTree、ROART等。这些工作从不同方面对上述3个关键问题给出了不同的解决方案。从这些工作可以发现，为了高效地利用非易失性内存的性能，减小软件开销、通过避免日志写入实现崩溃一致性、通过避免锁的使用来实现高效的并发、结合处理器体系架构和非易失性内存的硬件特性来进行优化，已经成为主流的方法。

5 结束语

最后，对在非易失性内存下高效实现索引数据结构的过程中存在的一些挑战进行总结。

一是如何在保留崩溃一致性的同时利用DRAM进一步优化索引数据结构的性能。目前的非易失性内存尽管性能接近DRAM，但是其时延仍然比DRAM高好几倍，且带宽更加受限。由于非易失性内存和DRAM之间的性能差距仍然不可忽略，现有的研究工作已经在尝试使用DRAM来优化索引数据结构的性能，但也有研究表明，在一些场景中，DRAM和非易失性内存混用可能会由于额外的数据迁移造成性能损失，因此如何高效地利用DRAM来优化索引数据结构仍然是一个需要深入研究的问题。

二是如何更进一步地利用非易失性内存的硬件特性对索引数据结构进行优化。非易失性内存与DRAM类似，但又有其独特的性质，之前的研究大多在使用DRAM模拟的非易失性内存上完成，近两年的研究工作大多基于英特尔傲腾持久内存，指出过去的研究中存在的问题，并对傲腾内存的硬件特性进行了一些适配。但一方面英特尔并没有公布傲腾持久内存的内部原理和架构，研究人员只能通过猜测其硬件特性进行优化，另一方面还有更多的新型非易失性内存存储介质未面市，这些存储介质可能具备不一样的特性，在这样的背景下，持久索引数据结构需要具有更灵活的设计才能适应存储介质的发展。

三是如何实现高效的非易失性内存空间分配器。在索引数据结构的设计和实现中，非易失性内存空间的动态分配是一个不可或缺的操作，其作为软件开销的一部分，对索引数据结构的性能有较大影响。同时一个高效的非易失性内存分配器要求避免永久性的内存泄露，并支持高效的并发操作。然而现有的研究中大多仅关注数据结构本身，忽略了这部分重要的软件开销，另外在DRAM中的内存分配器也需要更进一步的改进才能充分利用非易失性内存的特性。

王永锋（1998-），男，中山大学计算机学院博士生，主要研究方向为存储系统、分布式系统。

陈志广（1984-），男，博士，中山大学计算机学院副教授，主要研究方向为大数据存储与处理、并行与分布式计算、高性能计算与超级计算机。在并行文件系统、大规模并行I/O优化、大数据分析处理方面取得了关键技术突破。

联系我们:

Tel:010-81055448

       010-81055490

       010-81055534

E-mail:bdr@bjxintong.com.cn 

http://www.infocomm-journal.com/bdr

http://www.j-bigdataresearch.com.cn/

大数据期刊

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35170 人正在系统学习中