Back To Schedule
Thursday, July 11 • 10:25am - 10:45am
Mitigating Asymmetric Read and Write Costs in Cuckoo Hashing for Storage Systems

Sign up or log in to save this to your schedule, view media, leave feedback and see who's attending!

In storage systems, cuckoo hash tables have been widely used to support fast query services. For a read, the cuckoo hashing delivers real-time access with $O(1)$ lookup complexity via open-addressing approach. For a write, most concurrent cuckoo hash tables fail to efficiently address the problem of endless loops during item insertion due to the essential property of hash collisions. The asymmetric feature of cuckoo hashing exhibits fast-read-slow-write performance, which often becomes the bottleneck from single-thread writes. In order to address the problem of asymmetric performance and significantly improve the write/insert efficiency, we propose an optimized Concurrent Cuckoo hashing scheme, called CoCuckoo. To predetermine the occurrence of endless loops, CoCuckoo leverages a directed pseudoforest containing several subgraphs to leverage the cuckoo paths that represent the relationship among items. CoCuckoo exploits the observation that the insertion operations sharing a cuckoo path access the same subgraph, and hence a lock is needed for ensuring the correctness of concurrency control via allowing only one thread to access the shared path at a time; Insertion operations accessing different subgraphs are simultaneously executed without collisions. CoCuckoo improves the throughput performance by a graph-grained locking to support concurrent writes and reads. We have implemented all components of CoCuckoo and extensive experiments using the YCSB benchmark have demonstrated the efficiency and efficacy of our proposed scheme.


Yuanyuan Sun

Huazhong University of Science and Technology

Yu Hua

Huazhong University of Science and Technology

Zhangyu Chen

Huazhong University of Science and Technology

Yuncheng Guo

Huazhong University of Science and Technology

Thursday July 11, 2019 10:25am - 10:45am PDT
USENIX ATC Track II: Grand Ballroom VII–IX