基于英特尔傲腾非易失性内存的持久索引结构回顾与展望
Revisiting Persistent Indexing Structures on Intel Optane DC Persistent Memory
-
摘要: 非易失性内存因其支持字节寻址访问、高性能、低延迟等特性,正在学术界获得着广泛的关注。由于高性能且非易失性,非易失性内存可以被用来替代或加速固态硬盘和机械硬盘等设备持久地保存数据。作为快速查找数据的关键,非易失性内存上的存储持久索引结构成为了比较热门的研究方向之一。
在非易失性内存出现之前,哈希表、基数树是在内存中比较常用的索引结构,B/B+树则为块存储设备而设计,常用于保存持久化数据。由于非易失性内存同时具备内存可字节寻址特性和存储的持久化能力,哈希表、基数树和B/B+树均被重新设计和实现为非易失性内存上的索引结构(即持久索引结构)。但由于当时非易失性内存商品尚未发布,这些对持久索引结构的研究均使用模拟的方法进行性能测试。模拟方法大多基于现有的内存硬件,通过增加额外的延迟来模拟非易失性内存略低的读写性能,包括在CLFLUSH指令后插入延迟来模拟写延迟、根据CACHE MISS数量估算读的次数从而插入设定的延迟来模拟读延迟、以及基于NUMA访问特性来增大读写延迟等。
2019年,英特尔发布了傲腾持久化内存模块(Intel® OptaneTM Persistent Memory Module)。真实的非易失性内存产品出现后,此前研究中的持久索引结构在真实硬件上的性能到底如何,成为了一个很重要的问题。因此,我们对先前研究中的持久索引结构在傲腾持久内存上进行重新测试,并尝试回答以下问题:
1. 现有研究中的持久索引结构在实际傲腾持久内存硬件上性能表现如何?
2. 此前研究中提出和使用的模拟方式与实际硬件的性能是否有差距?差距有多大?
3. 持久索引结构的性能在非易失内存上是否以及如何被进一步提升?
为了回答上述问题,我们首先对傲腾持久化内存进行了测试,来揭示其基础的性能及特性。接着我们在傲腾持久内存上对持久索引结构重新进行了性能测试,分别展示了其插入和搜索的性能,并对测试结果进行了详细的分析。我们还使用现有的模拟方法对这些持久索引结构进行了测试,并将测试结果与实际傲腾持久内存上的测试结果进行比对,验证它们的各种模拟方法的准确性。最后,我们对持久索引结构中的刷回指令进行了比对测试,展示了它们对索引结构性能的影响,并总结了三个傲腾持久内存的使用和优化建议。
根据以上测试结果,我们获得了以下发现:
1. 傲腾持久化内存的读写粒度为256B;
2. 在所测试的常见持久哈希表中,CCEH表现最优,相比于调用的CLFLUSH指令的数量,数据局部性对性能的影响更大,数据局部性越差的哈希表性能越差;相比于硬件性能,哈希表本身采取的锁机制对其扩展性更具有决定性意义;
3. 树形持久索引结构中,FAST和WORT取得了相近的插入和查询延迟,插入延迟与插入过程中调用的CLFLUSH指令近似成正比;
4. 所有的模拟方式都无法针对所有的索引结构提供统一的配置同时正确地模拟出非易失内存。
并总结出了如下三个性能优化建议:
1. 尽量使用CLFLUSHOPT/CLWB + SFENCE替代CLFLUSH;
2. 尽量成批刷回连续的非易失内存区域;
3. 避免在数据刚被刷回之后访问数据;
本文是第一个在实际非易失内存上对索引结构进行性能测试与分析的工作。我们基于傲腾持久内存对不同的持久索引结构进行了性能测试,并给出了不同类型的持久索引结构中表现最佳的索引。同时,我们还根据测试结果分析了各个索引结构设计与实现的优劣。另一方面,我们验证了现有的非易失性内存模拟方式的准确性,使得读者能更好地理解以往基于这些模拟方式的测试结果。最后,我们提出了三个傲腾持久内存的使用和优化建议,来提高非易失性内存系统的性能。Abstract: Persistent indexing structures are proposed in response to emerging non-volatile memory (NVM) to provide high performance yet durable indexes. However, due to the lack of real NVM hardware, many prior persistent indexing structures were evaluated via emulation, which varies a lot across different setups and differs from the real deployment. Recently, Intel has released its Optane DC Persistent Memory Module (PMM), which is the first production-ready NVM. In this paper, we revisit popular persistent indexing structures on PMM and conduct comprehensive evaluations to study the performance differences among persistent indexing structures, including persistent hash tables and persistent trees. According to the evaluation results, we find that Cacheline-Conscious Extendible Hashing (CCEH) achieves the best performance among all evaluated persistent hash tables, and Failure-Atomic ShifT B+-Tree (FAST) and Write Optimal Radix Tree (WORT) perform better than other trees. Besides, we find that the insertion performance of hash tables is heavily influenced by data locality, while the insertion latency of trees is dominated by the flush instructions. We also uncover that no existing emulation methods accurately simulate PMM for all the studied data structures. Finally, we provide three suggestions on how to fully utilize PMM for better performance, including using clflushopt/clwb with sfence instead of clflush, flushing continuous data in a batch, and avoiding data access immediately after it is flushed to PMM.
下载: