面向混合型PM-DRAM内存的高效可扩展完美哈希技术

《ACM Transactions on Architecture and Code Optimization》：Towards Efficient Extendible Perfect Hashing for Hybrid PM-DRAM Memory

持久内存哈希索引读性能优化研究，提出EEPMPH+方案通过可扩展哈希减少数据迁移、混合PM-DRAM布局降低随机访问、批量预取提升并行效率，实验表明其读吞吐量比现有方案高3.6倍，99th延迟高3.14倍。

　　

摘要

哈希是一种广泛使用且高效的键值存储索引机制。持久性内存（PM）的出现通过提供非易失性和类似DRAM的性能进一步增强了哈希索引的功能。然而，目前关于基于PM的哈希索引的研究主要集中在硬件特定的持久性优化或写入性能优化上，而忽视了读取性能这一关键方面。我们的研究表明，哈希冲突会显著降低基于PM的哈希索引的读取性能。因此，能够消除冲突的完美哈希技术有潜力提升读取性能。不过，由于PM的访问延迟较高，哈希表扩展过程中的数据移动开销以及完美哈希本身引入的随机访问都会导致性能瓶颈。

在本文中，我们提出了一种名为EEPH+的高效完美哈希方案，专门用于PM，可以有效消除哈希冲突从而提升读取性能。EEPH+采用了三种技术来缓解上述瓶颈并提升性能：一种可扩展的哈希技术，用于减少哈希表扩展时的数据移动开销；一种混合型PM-DRAM布局，将索引结构存储在DRAM中，并结合一种补全移动算法来最小化完美哈希固有的随机访问；以及一种批量处理和预取方案，以促进多次搜索过程中哈希计算和数据访问的并行执行，从而进一步提升读取性能。

我们通过对多个实际场景下的读密集型和读偏态工作负载进行全面的实验，将EEPH+与现有的基于PM的哈希索引进行了对比。实验结果证实了EEPH+的优越性，其在读取吞吐量上比现有方案高出最多3.6倍，在99百分位延迟上高出3.14倍。