DOI ： 10.7544/issnl000-1239.2021.20200403
58(2) : 371 383, 2021
计算机研究与发展
Journal of Computer Rearch and Development
基于持久性内存的单向移动B +树
闫玮张兴军纪泽宇董小社姬辰肇
(西安交通大学计算机科学与技术学院西安710049)
(yanweiwei.002 @ stu. xj tu. edu. cn)
One-Direction Shift B +-Tree Bad on Persistent Memory
Yan Wei , Zhang Xingjun, Ji Zeyu, Dong Xiaoshe, and Ji Chenzhao
(School of C牢牢记
omputer Science and Technology , Xi'an Jiaotong University , Xi'an 710049)
Abstract The persistent memory (PM) fascinates many rearchers by its high scalability, byte
addressability and low static energy consumption which can contribute to the fusion of main memory
and condary memory. However , the interacting granularity between the volatile last level cache (LLC) and the non-volatile PM is normally 64B which is much larger than 8B, the granularity of the
atomic updating operations provided by the main memory. Once an outage takes place during the
process of transporting data from LLC to PM , data integration on the PM may be destroyed, which will lead to a breaking down of failure atomicity. Most rearches are ud to solve this problem by forcing the data persisted following some order implemented with flush and fence instructions which are always accompanied企业介绍文案
with large overhead. This overhead will be amplified especially in index updating which often leads to some transformation of index structures. In this paper, we focus on
reducing the persisting overhead for ensuring the failure atomicity of updating a PM-bad B +-Tree.
We propo a one direction shifting (ODS) algorithm bad on the real data layout in the tree node as well as the node utility, the persisting overhead of different updating mode and the relation between
different operations. This algorithm implements the in-place deletion to reduce the deleting overhead
and takes advantage of the pits generated by in-place deletion to further reduce the shifting overhead of inrtion. We redesign the rebalancing process of our persistent B+-Tree according to the ODS
algorithm. Experiments show that our propod ODS tree can outperform the state-of-the-art PM trees on single and synthetic workloads.
Key words persistent memory ； index structure ; failure atomicity ； index updating ； last level cache ;
persistent instruction
摘 要 由新型非易失存储介质构成的持久性内存(persistent memory, PM)具有扩展性强、按字节访
问与静态能耗低等特性，为未来主存与辅存融合提供了强大的契机.然而由于LLCdast level cache)具
有易失性且与主存交互粒度通常为64B，而PM 的原子持久化操作粒度为8B.因此，数据从LLC 更新到
PM 的过程中，若发生故障，则可能破坏更新操作的失败原子性，进而影响原始数据的完整性.为了保证
更新操作的失败原子性，目前研究主要采用显式调用持久化指令与内存屏障指令，将数据有序地持久化
收稿日期：2020—06—08；修回日期：2020-08-11基金项目：国家重点研发计划项目(2016YFB1000303)
This work was supported by the National Key Rearch and Development Program of China (2016YFB1000303).
通信作者：张兴军(**************** )
372计算机研究与发展2021,58（）
到PM上，但该操作会造成显著的开销，在索引更新中尤为明显.在对索引进行更新时，往往会涉及到索
引结构的变化，该变化需要大量的有序持久化开销.研究旨在减少基于PM的B树在更新过程中为保证失败原子性而引入的持久化开销.通过分析B树节点利用率、不同更新模式下持久化开销以及更新
操作之间的关系，提出了一种基于节点内数据真实分布的数据单向移动算法.通过原地删除的方式，减少删除带来的持久化开销.利用删除操作在节点内留下的空位，减少后续插入操作造成的数据移动，进而减少数据持久化开销.基于上述算法，对B树的重均衡操作进行优化.最后通过实验证明，相较于最新基于PM的B树，提出的单向移动B树能够显著提高单一负载与混合负载性能.
关键词持久性内存；索引结构；失败原子性；索引更新；LLC；持久化指令
中图法分类号TP309.2
由新型非易失存储介质如PCM1,ReRAM2, MRAM［3］等构成的持久性内存（persistent,memory, PM）具有按字节访问、非易失、存储密度高等特性，为计算机主存与外存融合提供了一个强大的契机.相较于传统内存，PM由于内部结构与制作工艺不同，具有更强的扩展性，同时由于其持久化特性,
PM 还能够大幅降低系统的静态能耗.相较于传统块设备，PM能够提供更快的访问速度，同时支持按字节访问.
在基于Cache+DRAM+HDD/SSD的存储架构中，为了保证数据的持久性，数据最终需要被保存到HDD/SSD中.为了防止数据持久化过程中发生故障导致的数据丢失或部分更新问题，通常采用日志、写时复制或日志结构存储来保证数据更新的原子性.由于传统HDD/SSD相对于DRAM具有较低的性能（延迟高、带宽低），上述持久化开销成为了制约存储系统的瓶颈之一.然而在基于Cache+PM的存储架构中，数据的持久化发生在PM上，因此数据可以在Cache与PM之间以cache line为单位直接传递，显著缩短了数据的访问路径.同时由于PM相较于HDD/SSD读写性能大幅提高，持久化开销也会相应降低.为了进一步降低数据持久化开销，提高存储系统性能，目前有大量研究利用PM按字节访问的特性，通过64b原子更新操作实现了无日志持久化操作.
为了大幅提高数据访问速度，存储系统通常需要根据访问需求及硬件特性设计高效的索引结构如树、散列、字典树等.B树以其扩展性好、性能稳定、缓存局部性较强等特点成为其中最受欢迎的索引结构之一，目前作为内存数据结构也得到了广泛应用.然而PM的出现并作为存储级内存设备为其设计带来了新的挑战：
1）失败原子性问题.目前常见Cache由易失存储介质构成，在系统故障后数据会完全丢失.因此在写回
式（write-back）Cache与PM交互时，cache line 内数据会根据Cache替换算法被写回到主存上，若发生故障，Cache内未及时写回到PM中的数据将会丢失.这可能会破坏PM中数据的完整性.另外为了满足内存级并行Cache中写回PM的cache line的顺序可能被打乱，进一步增加了数据恢复的难度.为了保证失败原子性，目前常见操作是使用clflush指令将cache line显式写回到主存之上，同时通过fence指令规定cache line的写回顺序.然而上述操作会显著降低内存的并发性能，进而降低整个系统的性能.
2）持久化开销问题.保证失败原子性会带来显著的持久化开销（mfence+elf1ush），这个开销在B 树中会被进一步放大，如若B树节点内数据有序，那么插入一个数据的排序操作会引起平均一半数据的移动，这些移动有明确的移动次序，意味着多次有序持久化操作；若B树内节点无序，需先持久化数据，再持久化相应元数据;B树节点的合并与分裂时，涉及到大量数据移动（拷贝）与部分指针的修改，数据移动（拷贝）必须在指针修改之前完成；若采用写时复制策略，亦涉及到大量数据移动（拷贝）与部分指针的修改.同时目前商用较为成功的持久性内存女如Intel Optane DC persistent,memory亦面临着使用寿命有限的问题［68］，过多的持久化操作亦会影响其设备的使用寿命.
虽然现存PM设备相较传统DRAM，延迟与吞吐量存在一定差距［910］，但随着新型非易失存储介质技术的不断发展，其性能差距必然会被不断缩小（ReRAM具有近似SRAM的性能）.同时在官方公布信息与文献口0］针对Intel Optane DC persistent.
闫 玮等：基于持久性内存的单向移动B 十树
373
memory 的测评中均无法得知其失败原子性的保证
粒度及机制，因此本文假定PM 的失败原子性保证
仍为8 B.本文聚焦基于单一 PM 架构的B +树设计， 旨在保证数据结构失败原子性的基础上，进一步减
少持久化开销，进而提高其性能并优化其使用寿命.
本文设计主要基于以下4个观察：
1) 使用无序数据布局能够大幅提咼写入性能，
但由于数据无序，查找速度会受到很大影响，同时也 会影响插入操作中节点内元素定位的过程•通过添
加元数据加快查找速度会带来额外的持久化开销. 节点内数据排序能够大幅提高数据访问性能，但排
序开销较大•
2) B +树节点占用率通常为70%左右
3) 在有序节点内，插入或删除一组数据会造成
平均50%的数据移动，这将带来大量的有序持久化 操作．
4) 同节点内，插入操作能够大概率与之前发生
的删除操作结合，进而减少数据的移动距离•
本文针对有序节点进行优化，主要贡献包括3 个方面：
1) 设计了一种基于节点内数据真实分布的数
据单向移动算法•通过原地删除的方式，减少删除带 来的持久化开销•利用删除操作在节点内留下的空 位，减少后续插入操作造成的数据移动，进而减少数 据持久化操作数量．
2) 基于该单向移动算法，设计了一个基于PM
的单向移动树(one-direction shifting tree, ODS -
Tree).ODS 树通过基于数据分布的分裂算法缓解
了节点空间利用率较低的问题，同时利用选择性重 均衡算法进一步节省了 ODS 树占用的空间•
3) 通过单一负载与混合负载验证本文所提出
的ODS 树空间利用的合理性及访问性能•
1研究背景
1.1节点更新方式
目前常见B +树节点更新的方式如图1所示，包 括原地更新(in-place 寅五行属什么
updates) A 日志式更新(log -
structured updates )和 写 时复制(copy-on - writes ,
COW).具体介绍如下：
1) 原地更新.原地更新是指增删查改等操作直
接作用于原始节点•如图1(a)所示，插入操作直接发
生在节点内，该过程需要日志来保证更新的原子性, 同时更新操作需要的空间较少•
2) 日志式更新.如图1(b)所示，增删查改等操
作均记录在日志内，以追加的方式存储在节点之后, 或存储在特定区域•该更新策略能够支持高效的顺
序读写，因此非常适合基于传统机械硬盘的存储.日 志式更新由于其产生的日志式结构，不需要额外日
志保证原子性，但读操作需要访问原节点以及其所 有日志并通过一定的计算才能获得正确结果•
3) 写时复制.如图1(c)所示，当我们要对节点
进行更新时，首先分配一个新的节点，将原始节点数
据拷贝到新节点中，然后将相应更新操作在新节点 内进行，更新完成后，通过修改父节点内指针使新节
点替换原始节点•写时复制不需要额外日志保证更 新的原子性，但会引起显著的写放大，在树结构中尤 为明显，如产生一个“自底而上”的拷贝.
文献［2］中通过对比分析在PM 环境下的3种
更新策略，提出原地更新方式更适用于基于PM 的
B +树节点更新.在原地更新条件下，由于节点内数
据排布方式不同，增删查改等操作细节也需要相应 的变化.
(a)采用原地更新方式插入131
4
6
11
151814********* 1 |45 | 77 89 1 45 77 891
46111518
]E0
146111518
(b)采用日志式更新将13追加到数组尾部
1 対5|77|89|—---＞原始指针—＞当前指针
11 15 18
叵 I ~1 |11丨13丨15|18| J |11丨15|18(c)米用写时复制插入13
Fig. 1 Updating the node with three strategies
图1节点的3种更新方法
1 |11|13】15|18| J
4
374计算机研究与发展2021,58（2）
1.2节点数据排布方式及其更新方式
树节点内常见数据排布方式包括有序排布与无序排布•有序排布是指所有数据按照数据key的大小升序
或降序排布，这有利于查找速度的提升，但插入操作会造成大量的数据移动（平均一半节点内数据），删除操作与插入操作类似，只是数据移动方向相反.无序排布是一种写优化排布，在此排布下插入操作直接将数据存储到数据组尾部（或数据组内部可用位置），删除操作将数据组内相应数据删除或在数据组尾部存储一个带删除标记的该数据•无序排布的写性能较高，但每次访问某一数据都需要遍历所有数据，造成大量的查找开销，写性能优势亦会相应下降，可以通过元数据高分
设计优化降低查找开销•
1・3失败原子性及其保证
原子性通常可分为并发原子性与失败原子性.并发原子性是指我们对数据的操作在多个事务看来具有原子性，这意味着任何事务无法看到操作过程中数据的中间状态•目前保证并发原子性的常见机制除利用显式内存屏障外还可通过硬件事务内存保证［3皿.
失败原子性是指在数据持久化的过程中，需要保证断电或系统故障后数据的完整性与正确性.其中一个破坏失败原子性的主要表现为数据从易失介质写入到非易失介质的过程中，若传输数据量大于非易失介质的原子写入粒度，此过程中发生断电或故障，未写入数据将会丢失，同时非易失介质内数据可能会出现无法识别的局部更新现象.在基于PM 的存储系统中，Cache与PM的交互粒度为一条cache line（通常为64B），原子性更新粒度为8B.因此故障既可能发生在单条cache line内字（word）更新之间
（在64位处理器中，word长度通常为8B），也可以能发生在多条cache line更新之间，同时由于粒度差距，日志会造成显著的写放大•结合图2分析，失败原子性的保证条件为：
1）若需要更新的数据量小于等于8B，则可直接对数据进行更新操作•
2）若需要更新的数据大小大于8B小于等于64B且位于一条cache line内，则需考虑在当前cache burst order（word写回顺序）情况下［5］，持久化一条cache line过程中发生故障是否会破坏数据的完整性.若单条cache line内所有word不存在依赖性，则需使用日志保证所有word在一个原子区间内完成持久化操作（不考虑额外硬件保证）.若word之间存在依赖性（原地更新场景下插入操作后数据移动），为减少日志开销，可通过选择特定的burst order通过一次持久化指令保证word有序持久化到PM上.
3）若需要更新的数据大于8B且跨多条cache line，则在每条cache line内需满足条件2）.同时由于多条cache line写回PM过程中可能会出现乱序问题，因此还需要保证多条cache line的写回顺序.若cache line之间不存在依赖性，则多条cache line 的更新需保证在一个原子区间内完成，通常采用日志方式完成（不考虑额外硬件保证）；若多条cache line之间存在依赖性（原地更新场景下插入操作后数据移动），为保证多条cache line之间的有序持久化，需要采用显式持久化指令+内存屏障的形式，保证多条cache line顺序持久化到PM上.
Fig.2Updated data after inrtion under different conditions 图2不同条件下插入操作更新的数据量
在B+树中，更新操作通常仅修改value值，而value值的长度通常为8B，插入操作需完成一次key, value对的插入，尺寸大于8B.在节点内数据有序排布的情况下，更新操作能够直接对数据进行原子更新操作；插入操作会造成大量的数据移动（平均移动节点内一清炒菜心
半的数据），这涉及到大量数据的修改，操作粒度通常远大于原子更新粒度，同时数据在移动过程中存在依赖性，因此需根据更新数据量大小
闫玮等：基于持久性内存的单向移动B+树375
选择2）或3）来保证失败原子性，即保证被更新数据的有序持久化.删除操作与插入操作类似，仅移动方向相反.由于节点内数据有序排布，查找操作可以通过顺序查找或二分查找进行，查找性能较高.
在节点内数据无序排布的情况下，更新操作可直接对原始数据进行.插入操作会将key,value对追加到尾部（或数据组内部可用位置），结合2）分析，该操作需要日志保护.但我们可以通过增加一个额外的位图表示数据的可见性，数据写入后，通过原子性更新位图来保证整个追加操作的原子性，另外也可通过该位图来快速完成删除操作（标记位图相应位置为0即可，无需在数据组尾部追加标记）.基于上述条件优化之后，插入操作的持久化保证可简化为先持久化key,value对，再持久化元数据（位图）.查找操作需要遍历所有有效数据，若数据存储设备与Cache直接交互，位图虽然能减少查找开销，但访存开销依旧较高.
如果更新数据量小于8B更新操作可以直接原子性完成，更新数据量大于8B则需要根据情况选择持久化策略：在有序节点内，若更新操作仅涉及修改一条cache line，则需保证cache line内每一个word的持久化顺序，若更新涉及到多条cac商标授权书模板
he line，则需要保证数据移动过程中相应修改的cache line 按一定顺序持久化；在无序节点内，需要先持久化数据，再持久化元数据.因此可得到结论：无论节点内数据如何排布，更新大于8B的失败原子性均需要通过有序的持久化操作来保证.
目前基于X86架构下，保证数据持久化的常用指令包括clflush,clflushopt,clwb[6].clflush能够显式地将一条包含指定地址的cache line写回到内存中同时使Cache中相应的cache line无效;clflushopt是一种并行版本的clflush；clwb在clflushopt功能的基础上，能够保证cache line在Cache中有效，进而能够在一定程度上保证Cache的命中率.为了保证数据持久化操作之间的有序性，我们可以通过mfence指令来规
定持久化的顺序，目前相关研究均假定clflush与store,clflush指令存在乱序现象，但最新Intel编程手册中指出clflush不会与上述指令乱序.由于mfence添加与否对本研究影响极小，为便于对照，故本研究采用clflush+mfence的方式保证数据有序持久化操作.为了进一步提高数据持久化效率，文献口7]提出了epoch barrier，通过硬件保证多个epoch之间的持久化顺序，同时epoch内flush操作可以并行执行.文献口8]在epoch barrier 的基础上，通过使strand内epoch可并发执行，进一步放松了持久化操作的顺序性.由于实验硬件条件限制，同时结合前人研究，本文采用clflush与mfence指令保证失败原子性.
除单个节点内情况外,B树的重均衡操作也会带来大量的持久化操作，因此亦需要保证其失败原子性.B树的分裂操作原子性保证与写时复制相似，但是由于B树为了支持高效范围查找，叶子节点间通过兄弟指针连接，这将导致一个新节点插入到树中需要修改2个指针（父节点内指针与兄弟节点内指针）.树节点合并操作亦涉及到上述2个指针.这将增大架空乘人装置
基于PM的B树的设计难度.
1.4相关研究
为了减少基于PM的B树持久化开销，目前相关研究根据存储架构不同可分为：基于DRAM+ PM的B树与基于单一PM架构的B树.基于DRAM PM架构的部分主要相关研究如下：1）NV-Tree[19].内部节点数据有序且存储在DRAM内，该设计能够大幅提高数据查找速度；叶子节点无序且存储在PM内，在该设计下每次数据插入仅需要一次持久化操作，能够大幅减少写入开销.然而，系统崩溃后，内部节点的重构需要消耗大量时间.
2）FP-Tree[20].与NV-Tree不同的是,FP-Tree 为叶子节点添加了一组元数据（指纹）用以管理无序的数据，每一个key对应一个1B的散列值.查找操作通过优先访问元数据，提高了Cache命中率.同时,FP-Tree还采用硬件事务内存来保证内部节点的并发性.
3）DP-Tree[21].设计了一种基于DRAM+PM 的，同时具有双阶段的索引架构.该设计基于真实硬件Intel Optane DC persistent,memory访问粒度为256B的特性，首先通过DRAM中的buffer tree对数据更新操作进行缓冲，同时将更新写入到位于PM的日志中.然后，当buffer tree达到一定尺寸后，合并到ba tree中.值得注意的是ba tree的内部节点也存在于DRAM中，且只允许合并之后进行修改.除此之外,DP-Tree还提出了一种粗粒度的锁，以保证索引结构的并发性.
4）FlatStore[22].结合新硬件特性，利用DRAM 中的B树或散列对更新请求进行缓冲，提出了一种横向steal的打包策略，将更新请求批量写入到PM 内，有效解决了Cache与Intel Optane DC persistent, memory访问粒度不同的问题，同时将每一个包填充
