EEPH: An Efficient Extendible Perfect Hashing for Hybrid PMem-DRAM

Qi Chen1; Hao Hu1; Cai Deng1; Dingbang Liu1; Shiyi Li1; Bo Tang2; Ting Yao3; Wen Xia1

10.1109/ICDE55515.2023.00109

2023

1063-6382

979-8-3503-2228-6

2023 IEEE 39th International Conference on Data Engineering (ICDE)

2023-April

1366-1378

3-7 April 2023

Anaheim, CA, USA

In recent years, the performance of hash indexes has been significantly improved by exploiting emerging persistent memory (PMem). However, the performance improvement of hash indexes mainly comes from exploiting the hardware features of PMem. Only a few studies optimize the hash index itself to fully exploit the potential of PMem. Interestingly, many of these studies improve the performance of write, but disregard the performance of read, of hash indexes on PMem. With extensive experimental evaluation, we find the major reason for inefficient read in the hash index on PMem is that the overhead of hash collision processing is expensive.To address that, we propose a novel Efficient Extendible Perfect Hashing (EEPH) on PMem-DRAM hybrid data layout to improve read performance of hash indexes. Specifically, we reduce the overhead of dynamic perfect hashing extension on PMem by combing extendible hashing. We then design a hybrid data layout to unlock the inherent read strengths of perfect hashing (i.e., zero collision). Last, we devise a complement move algorithm to efficiently guarantee the zero collision of perfect hashing when data move is conducted on PMem. We compare EEPH with the state-of-the-art hash indexes on PMem by conducting comprehensive experiments on several real-world read-intensive and read-skew workloads. The experimental results confirm the superiority of our EEPH as it achieves up to 2.21× higher throughput and about 1/3 of the 99th percentile latency than state-of-the-art hash indexes.

hybrid PMem DRAM perfect hashing

其他

EI

20233314551558

Data Storage, Equipment and Techniques:722.1

IEEE

1.Harbin Institute of Technology, Shenzhen
2.Southern University of Science and Technology
3.Huawei, Shenzhen

Qi Chen,Hao Hu,Cai Deng,et al. EEPH: An Efficient Extendible Perfect Hashing for Hybrid PMem-DRAM[C],2023:1366-1378.