SPHT: A scalable and high‐performance hashing scheme for persistent memory. (21st March 2022)

• Record Type: Journal Article
• Authors: Zou, Xiaomin; Wang, Fang; Feng, Dan; Yang, Feiyu; Lei, Mengya; Liu, Chaojie
• Is Part Of: Software, practice & experience. Volume 52:Number 7(2022)
• Page Start: 1679
• Page End: 1697
• Publication Date: 2022-03-21
• Subjects: concurrent index structure -- dynamic hashing structure -- high scalability -- persistent memory; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.3083
• Languages: English
• ISSNs: 0038-0644

Abstract

Abstract: The evolution of persistent memory (PM) has significantly affected the design of today's indexing structures. Hashing‐based structures are widely used in storage systems to achieve fast query responses. Recently, several concurrent and failure‐atomic hashing schemes for PM have been proposed to improve the scalability. However, these works still suffer from limited scalability, especially under write‐intensive workloads or at a high number of threads. Our empirical study concludes three issues harm the scalability of PM hashing schemes: the NUMA effects, the resizing operations, and the inter‐thread interference overhead in PM. Based on the above scalability issues, we present SPHT, a scalable and persistent hashing scheme for hybrid DRAM‐PM memory. To eliminate the NUMA effects, SPHT maintains a hash subtable for every NUMA node and stores the key‐value items in the designated nodes. By doing so, all operations can be executed in the local memory without cross‐node communication. The hash subtable consists of two components: the search layer in DRAM for fast accesses and the data layer in PM for efficient persistence. The data layer is organized in a log‐structured way and its log chunks own separate PM space, thus avoiding the resizing operations in PM. Meanwhile, the compacted log structure also supports batching multiple small items, which effectively reduces the persistence overhead. Furthermore, to maximize concurrency, we assign threads to different partitions in the data layer to reduce the inter‐thread interference overhead. On Intel Optane DCPMM, our evaluations show that SPHT scales well and achieves up to 2.7 × higher performance than state‐of‐the‐art PM hashing schemes under YCSB workloads.