EHS: An Efficient Hashing Scheme for Persistent Memory
Dereje Regassa, Dong Kyu Sung, Sunggon Kim, Heon Young Yeom, Yongseok Son · 2023
This paper presents an efficient hashing scheme called EHS to improve the performance and space efficiency on PM. In our scheme, we delay expensive rehashing operations by using the free space in buckets maximally. To do this, 1) we search and utilize the available spaces in all the buckets 2) we devise metadata of the bucket to manage and track the available spaces in all the buckets. This scheme enables to delay the full table rehashing and use the full space in the hash table efficiently. We implement and evaluate EHS on a real device such as Intel Optane® DC Persistent Memory (DCPMM). The experiment result shows EHS improves the performance by up to 53% and 14% in the case of insert operation compared with state-of-art schemes such as CCEH and Dash, respectively. It also improves the load factor by up to 91.8% and 87% compared with CCEH and Dash, respectively.