Abstract: Non-Volatile Memory (NVM) attracts people's attention because of its large capacity, persistence, bit addressability and low read latency. However, it also has some disadvantages, such as limited writes and asymmetric reading and writing speed. When the traditional linear hash index is implemented directly on NVM, it will lead to a great number of random write operations. To solve this problem, a new NVM-friendly linear hash index called NVM-LH (NVM-oriented Linear Hashing) was proposed. The cache friendliness was achieved by NVM-LH through the cache line alignment during storing data. And a log-free data consistency guaranteeing strategy was presented in NVM-LH. In addition, the split and delete operations were optimized in NVM-LH to minimize the NVM write operations. Experimental results show that NVM-LH outperforms the state-of-the-art NVM-aware hash index CCEH (Cacheline-Conscious Extendible Hashing) in terms of space utilization (30% higher) and NVM write number (about 15% lower), showing better NVM-friendliness.

Key words: Non-Volatile Memory (NVM), dynamic hashing, linear hashing, cache line friendliness, data consistency

摘要： 非易失性内存（NVM）因其大容量、持久化、按位存取和读延迟低等特性而受到人们的关注，但它同时也具有写次数有限、读写速度不均衡等缺点。针对传统线性哈希索引直接在NVM上实现时会导致大量的随机写操作这一问题，提出了一种新的NVM友好的线性哈希索引NVM-LH。NVM-LH通过存储数据时的缓存行对齐实现了缓存友好性，同时提出了无日志的数据一致性保证策略。此外，NVM-LH还通过优化分裂和删除操作来减少NVM写操作。实验结果表明，NVM-LH在空间利用率上比CCEH高30%，在NVM写次数上比CCEH减少了15%左右，表现了更好的NVM友好性。

关键词: 非易失性内存, 动态哈希, 线性哈希, 缓存行友好性, 数据一致性