ESH: Design and Implementation of an Optimal Hashing Scheme for Persistent Memory
Source abstract
Abstract
Recent advancements in memory technology have opened up a wealth of possibilities for innovation in data structures. The emergence of byte-addressable persistent memory (PM) with its impressive capacity and low latency has accelerated the adoption of PM in existing hashing-based indexes. As a result, several new hashing schemes utilizing emulators have been proposed. However, these schemes have proven to be suboptimal, lacking scalability when implemented on real devices. Only a handful of hash table designs have successfully addressed critical properties such as load factor, scalability, efficient memory utilization, and recovery. One of the main challenges in redesigning data structures for an effective hashing scheme in PM is minimizing the overhead associated with dynamic hashing operations in the hash table. To tackle this challenge, this paper introduces ESH, an efficient and scalable hashing scheme that significantly improves memory efficiency, scalability, and overall performance on PM. The ESH scheme maximizes the utilization of the hash table’s available space, thus reducing the frequency of full-table rehashing and improving performance. Consequently, this scheme achieves a high load factor while minimizing the need for rehashing. To evaluate the effectiveness of the ESH scheme, we compare it to widely used dynamic hashing schemes employing similar techniques on Intel Optane® DC persistent memory (DCPMM). The experimental results demonstrate that ESH outperforms CCEH and Dash in terms of data insertion performance, exhibiting a 30% improvement over CCEH and a 4% improvement over Dash. Furthermore, ESH improves the lookup operation by nearly 10% compared to Dash, while achieving a load factor of up to 91%, surpassing its competitors.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Advanced Data Storage Technologies · Caching and Content Delivery · Parallel Computing and Optimization Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Integrated Program of Smart City Global Convergence, Seoul National University, Seoul 08826, Republic of Korea
Department of Computer Science and Engineering, Seoul National University, Seoul 08826, Republic of Korea
Funding
National Research Foundation of Korea (NRF)
References (56)
Show source-provided references
1. Intel (2021). Intel® Optane™ DC Persistent Memory, Intel. Release 1.
2. Intel Corporation (2022). Intel® Optane™ DC Persistent Memory, Intel. Release 2.
3. BzTree: A high-performance latch-free range index for non-volatile memory10.1145/3187009.3164147 ↗
4. Chen, S., Gibbons, P.B., and Nath, S. (2011, January 9–12). Rethinking Database Algorithms for Phase Change Memory. Proceedings of the Conference on Innovative Data Systems Research (CIDR), Asilomar, CA, USA.
5. Oracle, S. (2018). Architectural Overview of the Oracle ZFS Storage Appliance, Oracle.
6. Patil, S., and Gibson, G. (2011, January 15–17). Scale and Concurrency of GIGA+: File System Directories with Millions of Files. Proceedings of the 9th USENIX Conference on File and Storage Technologies (FAST 11), San Jose, CA, USA.
7. The global file system
8. Whitehouse, S. (2007, January 27–30). The GFS2 filesystem. Proceedings of the Linux Symposium, Ottawa, ON, Canada.
9. Redis (2021). In-Memory Data Structure, Store. Redis Inc.
10. (2023, July 02). Memcached. Available online: https://memcached.org/.
11. Hwang, D., Kim, W.H., Won, Y., and Nam, B. (2018, January 12–15). Endurable transient inconsistency in byte-addressable persistent b+-tree. Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST 18), Oakland, CA, USA.
12. Yang, J., Wei, Q., Chen, C., Wang, C., Yong, K.L., and He, B. (2015, January 16–19). NV-Tree: Reducing consistency cost for NVM-based single level systems. Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST 15), Santa Clara, CA, USA.
13. Lee, S.K., Lim, K.H., Song, H., Nam, B., and Noh, S.H. (March, January 27). WORT: Write optimal radix tree for persistent memory storage systems. Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST 17), Santa Clara, CA, USA.
14. Nam, M., Cha, H., Choi, Y.r., Noh, S.H., and Nam, B. (2019, January 25–28). Write-optimized dynamic hashing for persistent memory. Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST 19), Boston, MA, USA.
15. Zuo, P., Hua, Y., and Wu, J. (2018, January 8–10). Write-optimized and high-performance hashing index scheme for persistent memory. Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), Carlsbad, CA, USA.
16. Lee, S.K., Mohan, J., Kashyap, S., Kim, T., and Chidambaram, V. (2019, January 27–30). Recipe: Converting concurrent DRAM indexes to persistent-memory indexes. Proceedings of the 27th ACM Symposium on Operating Systems Principles, Huntsville, ON, Canada.10.1145/3341301.3359635 ↗
17. Persistent b+-trees in non-volatile main memory10.14778/2752939.2752947 ↗
18. Lu, B., Hao, X., Wang, T., and Lo, E. (2020). Dash: Scalable hashing on persistent memory. arXiv.10.14778/3389133.3389134 ↗
19. Intel (2021). Intel and Micron Produce Breakthrough Memory Technology, Intel.
20. Intel Corporation® (2022). Enabling Persistent Memory Programming, Intel.
21. Ren, J., Hu, Q., Khan, S., and Moscibroda, T. (2017, January 2). Programming for non-volatile main memory is hard. Proceedings of the 8th Asia-Pacific Workshop on Systems, Mumbai, India.10.1145/3124680.3124729 ↗
22. Chandramouli, B., Prasaad, G., Kossmann, D., Levandoski, J., Hunter, J., and Barnett, M. (2018, January 10–15). Faster: A concurrent key-value store with in-place updates. Proceedings of the 2018 International Conference on Management of Data, Houston, TX, USA.10.1145/3183713.3196898 ↗
23. Fan, B., Andersen, D.G., and Kaminsky, M. (2013, January 2–5). MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13), Lombard, IL, USA.
24. Data structures in the multicore age10.1145/1897852.1897873 ↗
25. Sánchez Barrera, I., Black-Schaffer, D., Casas, M., Moretó, M., Stupnikova, A., and Popov, M. (July, January 29). Modeling and optimizing numa effects and prefetching with machine learning. Proceedings of the 34th ACM International Conference on Supercomputing, Barcelona, Spain.
26. Traffic management: A holistic approach to memory placement on NUMA systems10.1145/2499368.2451157 ↗
27. Diener, M., Cruz, E.H., Navaux, P.O., Busse, A., and Heiß, H.U. (2014, January 24–27). kMAF: Automatic kernel-level management of thread and data affinity. Proceedings of the 23rd International Conference on Parallel Architectures and Compilation, Edmonton, AB, Canada.10.1145/2628071.2628085 ↗
28. Characterizing communication and page usage of parallel applications for thread and data mapping10.1016/j.peva.2015.03.001 ↗
29. Memarzia, P., Ray, S., and Bhavsar, V.C. (2019). Toward Efficient In-memory Data Analytics on NUMA Systems. arXiv.
30. Majo, Z., and Gross, T.R. (2011, January 4–5). Memory management in numa multicore systems: Trapped between cache contention and interconnect overhead. Proceedings of the International Symposium on Memory Management, San Jose, CA, USA.10.1145/1993478.1993481 ↗
31. Contention-aware scheduling on multicore systems10.1145/1880018.1880019 ↗
32. Xu, J., Kim, J., Memaripour, A., and Swanson, S. (2019, January 13–17). Finding and fixing performance pathologies in persistent memory software stacks. Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, Providence, RI, USA.10.1145/3297858.3304077 ↗
33. Thomas, S., Hayne, R., Pulaj, J., and Mendes, H. (2020, January 9–11). Using Skip Graphs for Increased NUMA Locality. Proceedings of the 2020 IEEE 32nd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Porto, Portugal.10.1109/SBAC-PAD49847.2020.00031 ↗
34. Cphash: A cache-partitioned hash table10.1145/2370036.2145874 ↗
35. Calciu, I., Gottschlich, J., and Herlihy, M. (2013, January 24–25). Using elimination and delegation to implement a scalable NUMA-friendly stack. Proceedings of the 5th USENIX Workshop on Hot Topics in Parallelism (HotPar 13), San Jose, CA, USA.
36. Daly, H., Hassan, A., Spear, M.F., and Palmieri, R. (2018, January 25–27). NUMASK: High performance scalable skip list for NUMA. Proceedings of the 32nd International Symposium on Distributed Computing (DISC 2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Augusta, GA, USA.
37. Dong, M., Yu, Q., Zhou, X., Hong, Y., Chen, H., and Zang, B. (2016, January 4–5). Rethinking benchmarking for nvm-based file systems. Proceedings of the 7th ACM SIGOPS Asia-Pacific Workshop on Systems, Hong Kong, China.10.1145/2967360.2967379 ↗
38. Ma, S., Chen, K., Chen, S., Liu, M., Zhu, J., Kang, H., and Wu, Y. (2021, January 23–25). ROART: Range-query Optimized Persistent ART. Proceedings of the 19th USENIX Conference on File and Storage Technologies (FAST 21), Santa Clara, CA, USA.
39. Prout, A. (2023, July 02). The Story Behind Memsql’s Skiplist Indexes. Available online: https://www.singlestore.com/blog/what-is-skiplist-why-skiplist-index-for-memsql/.
40. Diaconu, C., Freedman, C., Ismert, E., Larson, P.A., Mittal, P., Stonecipher, R., Verma, N., and Zwilling, M. (2013, January 22–27). Hekaton: SQL server’s memory-optimized OLTP engine. Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, NY, USA.10.1145/2463676.2463710 ↗
41. Oukid, I., Lasperas, J., Nica, A., Willhalm, T., and Lehner, W. (July, January 26). FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. Proceedings of the 2016 International Conference on Management of Data, San Francisco, CA, USA.10.1145/2882903.2915251 ↗
42. Imamura, S., Sato, M., and Yoshida, E. (2017, January 9). Evaluating a Trade-Off between DRAM and Persistent Memory for Persistent-Data Placement on Hybrid Main Memory. Proceedings of the Workshop on Hardware/Software Techniques for Minimizing Data Movement, Portland, OR, USA.
43. Extendible hashing—A fast access method for dynamic files10.1145/320083.320092 ↗
44. Liu, Z., Calciu, I., Herlihy, M., and Mutlu, O. (2017, January 24–26). Concurrent Data Structures for Near-Memory Computing. Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, New York, NY, USA.10.1145/3087556.3087582 ↗
45. Intel (2023, July 02). Intel Threading Building Blocks Developer Reference. Available online: https://software.intel.com/en-us/tbb-reference-manual/.
46. clfB-tree: Cacheline friendly persistent B-tree for NVRAM10.1145/3129263 ↗
47. Revisiting hash table design for phase change memory10.1145/2883591.2883597 ↗
48. Cuckoo hashing10.1016/j.jalgor.2003.12.002 ↗
49. NV-Heaps: Making persistent objects fast and safe with next-generation, non-volatile memories10.1145/1961295.1950380 ↗
50. A write-friendly and cache-optimized hashing scheme for non-volatile memory systems10.1109/TPDS.2017.2782251 ↗
51. Intel (2023, July 16). Intel® Persistent Memory Development Kit. Available online: https://pmem.io/pmdk/libpmem/.
52. A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory10.14778/3583140.3583144 ↗
53. Level hashing: A high-performance and flexible-resizing persistent hashing index structure10.1145/3322096 ↗
54. Appleby, A. (2023, July 02). MurmurHash—MurmurHashUnaligned; Google Groups. Available online: https://chromium.googlesource.com/external/smhasher/+/58dd8869da8c95f5c26ec70a6cdd243a7647c8fc/MurmurHash3.cpp.
55. Herlihy, M., Shavit, N., Luchangco, V., and Spear, M. (2020). The Art of Multiprocessor Programming, Morgan Kaufmann.
56. Building blocks for persistent memory10.1007/s00778-020-00622-9 ↗