中国计算机学会的A类国际会议USENIXATC2020近期录用了华中科技大学武汉光电国家研究中心华宇教授课题组的研究成果“Lock-free Concurrent Level Hashing for Persistent Memory”，此次会议投稿348篇，录用65篇，录用率18.7%。据悉这项研究成果也是国际顶级会议USENIX ATC 2020录用的来自中国地区科研机构独立完成的两篇论文之一。

面向持久内存的高性能索引结构是大规模存储系统提供快速查询的基础。和基于树的索引结构相比，基于哈希的索引结构将数据映射到扁平的空间（例如数组）以提供常数级别复杂度的单点查询。因此，哈希索引结构被广泛用于内存应用。现有的基于哈希的持久内存索引主要关注崩溃一致性和写优化，然而这些索引结构对非阻塞扩容和并发控制的考虑有限。为了实现持久内存索引结构的即时恢复，索引结构在任意时刻都需要处于一致的状态，这种要求被称为崩溃一致性保证。现有的持久内存哈希索引通过刷新缓存行和内存屏障以设计崩溃一致的结构。另外，许多持久化索引减少写操作以缓解非易失存储器寿命有限的问题。然而，现有的持久内存哈希索引仍面临两个问题：（1）扩容时的性能下降。哈希索引中，不同的关键字可能会被映射到同一个地方，称之为哈希冲突。当哈希索引无法解决哈希冲突时就需要扩容以增大容量。传统的扩容操作会分配一个新的哈希表，然后将所有元素从旧的哈希表迁移到新的哈希表中。对于并发哈希索引，粗粒度的锁虽然可以保护共享元数据在扩容期间的线程安全，但是也导致高的并发冲突并阻塞前端其它线程的操作。（2）基于锁的并发控制导致的较差的扩展性。哈希表通过锁来控制并发访问。锁虽然保护了哈希表的线程安全，但是也限制了索引的并发访问和扩展性。

图1. Clevelhashing的整体系统结构图

为了解决上面两个问题，武汉光电国家研究中心华宇教授课题组提出了面向持久内存的崩溃一致、无锁并发的哈希索引，称为clevelhashing，如图1所示。为了支持非阻塞的扩容，clevelhashing设计了多层的索引结构并使用异步重哈希。在并发控制方面，clevelhashing采用原子操作实现无锁的查询/插入/更新/删除操作。并发操作的正确性通过上下文感知方案保证。Clevelhashing继承了levelhashing的崩溃一致性和写优化操作，同时实现了可扩展性和非阻塞的扩容。基于真实的Intel傲腾数据中心级持久内存平台和YCSB负载的测试结果表明，相较于最新的持久内存哈希索引，clevelhashing可以达到最高4.2倍的性能提升。总的来说，如图2所示，clevelhashing实现了面向持久化索引的低开销和高并发等，这种设计思路也将启发其它索引结构的设计。

图2. Clevelhashing在YCSB负载下的并发性能

研究工作得到了国家重点研发计划(2016YFB1000202)和国家自然科学基金(61772212)等项目的资助。武汉光电国家研究中心华宇教授为论文通讯作者，其博士生陈章玉为第一作者。