HART: A Concurrent Hash-Assisted Radix Tree for DRAM-PM Hybrid Memory Systems
HART: A Concurrent Hash-Assisted Radix Tree for DRAM-PM Hybrid Memory Systems
复制标题
DOI：
10.1109/ipdps.2019.00100
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Wen Pan;Tao Xie;Xiaojia Song
中科院分区：
文献类型：
--
作者：
Wen Pan;Tao Xie;Xiaojia Song
持久内存 (PM) 在为应用程序提供混合内存系统方面展现出巨大的潜力，其中 DRAM 和 PM 都直接连接到 CPU。在这样的系统中，诸如持久树之类的高效索引数据结构成为不可或缺的组成部分。然而，设计一个强大的持久性树具有挑战性，因为它必须确保一致性、持久性和可扩展性，而不会显着降低性能。此外，它需要防止持久内存泄漏。虽然哈希表因其在随机查询方面的优越性能而被广泛用于主存索引，但 ART（自适应基数树）在 DRAM 和 PM 上的大多数基本操作中本质上优于 B/B^+ 树。为了利用它们的互补优点，在本文中，我们提出了一种新颖的并发持久树，称为 HART（哈希辅助 ART），它使用哈希表来管理 ART。 HART 采用选择性一致性/持久性机制和增强的持久性内存分配器，不仅可以优化其性能，还可以防止持久性内存泄漏。实验结果表明，在大多数情况下，HART 的性能明显优于 WOART 和 FPTree 这两种最先进的持久树。此外，它在并发场景中也能很好地扩展。
Persistent memory (PM) exhibits a huge potential to provide applications with a hybrid memory system where both DRAM and PM are directly connected to a CPU. In such a system, an efficient indexing data structure such as a persistent tree becomes an indispensable component. Designing a capable persistent tree, however, is challenging as it has to ensure consistency, persistence, and scalability without substantially degrading performance. Besides, it needs to prevent persistent memory leaks. While hash table has been widely used for main memory indexing due to its superior performance in random query, ART (Adaptive Radix Tree) is inherently better than B/B^+-tree in most basic operations on both DRAM and PM. To exploit their complementary merits, in this paper we propose a novel concurrent and persistent tree called HART (Hash-assisted ART), which employs a hash table to manage ARTs. HART employs a selective consistency/persistence mechanism and an enhanced persistent memory allocator, which can not only optimize its performance but also prevent persistent memory leaks. Experimental results show that in most cases HART significantly outperforms WOART and FPTree, two state-of-the-art persistent trees. Also, it scales well in concurrent scenarios.