持久性内存（PM）具有接近DRAM的性能和类似磁盘的持久性，因此具有替代DRAM的潜力。然而，为DRAM设计的散列表并不能直接应用于PM。之前基于Optane DC持久性内存模块（DCPMM）的散列表在可扩展性和写入性能方面并不是最优的，这是由于昂贵的并发控制锁开销和扩展导致的大量数据移动开销造成的。

实验室博士生胡静，在陈俭喜副教授的指导下，提出了一种名为PMEH的机会无锁并行多分裂可扩展哈希方案。首先，PMEH通过将哈希表划分为多个分区，并将每个分区分配给一个线程来实现对均匀分布数据的无锁操作。其次，PMEH采用机会无锁并行机制有效地处理倾斜数据分布。机会无锁并行机制通过无锁和加锁操作之间的有效动态切换，最大限度地提高了无锁操作的利用率。最后，PMEH使用逐步多分裂方式来减少哈希表扩展的频率，从而减少扩展过程中的数据移动。

在广泛使用的YCSB负载下的实验结果表明，PMEH具有良好的可扩展性，并且与数据分布无关。此外，与其他最先进的哈希方案相比，PMEH显著提高了插入速度（1.44倍~15.4倍）和删除速度（2.04倍~18.07倍）。此外，PMEH至少减少了52%的额外写操作，同时提供了即时恢复。

该研究成果于2023年4月发表在IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems (TCAD)上，题为“PMEH: A Parallel and Write-optimized Extendible Hashing for Persistent Memory”。该工作得到了国家自然科学基金（No.61832020, No.61821003）的支持。

图1： PMEH 整体架构

图2： PMEH与其它哈希机制在不同负载下的可扩展性对比