计算机数据存储领域中取得重要进展 设计出多项新式B+树类的数据结构

数据存储是计算机系统的基础。为了高速索引存储在计算机系统的数据，当前有多种数据结构可以实现。B+树作为上世纪70年代针对磁盘与单核处理器设计的数据结构，在现今多种数据库与文件系统中仍有着不可或缺的作用。

上海科技大学信息学院王春东课题组与合作者在计算机数据存储领域中取得重要进展，设计出多项新式B+树类的数据结构，在保持数据持久性与一致性的前提下，大幅提升B+树类结构在新型非易失性存储器上的性能。相关成果发表于学术期刊IEEE Transactions on Computers、ACM Transactions on Embedded Computing Systems和IEEE国际计算机设计会议（IEEE International Conference on Computer Design，ICCD '20)

为了维护针对传统主存—硬盘架构设计的B+树移植到新的非易失性存储设备上的崩溃一致性，要使用处理器厂商提供的持久化指令来保证处理器高速缓存块中，被修改的数据被持久化到非易失性主存中。这一过程会产生大量的性能开销。如何降低此类开销是当前设计面向非易失性存储器的存储系统的研究重点。针对这一问题，王春东课题组与合作者设计出了颠覆传统B+树节点线性结构的Circ-Tree，将线性节点结构改为环状结构，大幅度降低了数据持久化指令的使用次数与其所带来的性能开销。实验结果表明，相较于之前针对非易失性存储器设计的NV-Tree有1.6倍的性能提升，比最新的FAST-FAIR有高达8.6倍的性能提升。

非关系性数据库中的键值对在有序节点中有很强的存储依赖关系。在x86架构的处理器中，TSO（Total Store Ordering）内存一致性模型的设计保证了多线程之间的数据访问正确性。但另一类广泛使用的ARM架构采取non-TSO模型，需要在指令间插入额外的mfence指令来保证写操作的顺序性，但这一改动又会造成额外的性能损失。课题组与合作者针对ARMv8设计Crab-Tree，通过选择写时复制和批量数据转移策略将其中的性能开销降低到最低。实验表明Crab-Tree相对最先进的针对非易失性存储器的B+树设计，在读和写方面分别有3.2倍和2.6倍的性能提升。  

上述的研究虽然优化了B+树的写性能，但写操作所带来的数据移动依然需要大量的持久化指令。课题组与合作者提出了Isle-Tree减少数据移动，从而用以进一步减少指令的数量。Isle-Tree将节点的数据组织成单条高速缓存块内有序、多条缓存块之间无序的结构。每次移动的数据都在一个缓存块中，只需要一次clflush指令来保证数据的持久性。通过这种设计降低持久化指令的使用数量来优化B+树在非易失性存储器上的写性能。

以上成果由上海科技大学和新加坡科技设计大学合作完成。上海科技大学为第一完成单位。上海科技大学信息学院助理教授王春东为论文的第一作者。该研究获得上海科技大学、新加坡教育部和新加坡科技设计大学的大力支持。

图. Circ-Tree实验结果：六种不同的树形结构设计在1百万数据插入与搜索性能比较

IEEE Transactions on Computers由IEEE计算机协会于1952年创刊。该期刊涵盖了计算机设计各个方面，是中国计算机学会推荐A类期刊，也是计算机科学领域的经典顶级期刊之一。ACM Transactions on Embedded Computing Systems是ACM旗下针对嵌入系统方向的期刊，在行业领域享有很高的影响力。 ICCD是计算机体系结构与系统领域的主流会议，2020年录用率是28.6%。（文/上海科技大学）