Dalea:A Persistent Multi-Level Extendible Hashing with Improved Tail Performance  

作　　者：熊子威 蒋德钧 熊劲 Ren Ren Zi-Wei Xiong;De-Jun Jiang;Jin Xiong;Ren Ren(Center for Advanced Computer Systems,Institute of Computing Technology,Chinese Academy of Sciences Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 101408,China;Huawei Technology Co.,Ltd.,Shanghai 201206,China)

机构地区：[1]Center for Advanced Computer Systems,Institute of Computing Technology,Chinese Academy of Sciences Beijing 100190,China [2]University of Chinese Academy of Sciences,Beijing 101408,China [3]Huawei Technology Co.,Ltd.,Shanghai 201206,China

出　　处：《Journal of Computer Science & Technology》2023年第5期1051-1073,共23页计算机科学技术学报（英文版）

基　　金：supported by the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant No.XDB44030200;the Beijing Natural Science Foundation-Haidian Joint Fund for Original Innovation under Grant No.L192038.

摘　　要：Persistent memory(PM)promises byte-addressability,large capacity,and durability.Main memory systems,such as key-value stores and in-memory databases,benefit from such features of PM.Due to the great popularity of hash-ing index in main memory systems,a number of research efforts are made to provide high average performance persistent hashing.However,suboptimal tail performance in terms of tail throughput and tail latency is still observed for existing persistent hashing.In this paper,we analyze major sources of suboptimal tail performance from key design issues of persis-tent hashing.We identify the global hash structure and concurrency control as remaining explorable design spaces for im-proving tail performance.We propose Directory-sharing Multi-level Extendible Hashing(Dalea)for PM.Dalea designs an-cestor link-based extendible hashing as well as fine-grained transient lock to address the two main sources(rehashing and locking)affecting tail performance.The evaluation results show that,compared with state-of-the-art persistent hashing Dash,Dalea achieves increased tail throughput by 4.1x and reduced tail latency by 5.4x.Moreover,in order to provide de-sign guidelines for improving tail performance,we adopt Dalea as a testbed to identify different impacts of four factors on tail performance,including fine-grained rehashing,transient locking,memory pre-allocation,and fingerprinting.

关 键 词：persistent memory persistent hashing indexing structure 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]