Mitigating Asymmetric Read and Write Costs in Cuckoo Hashing for Storage Systems
Talkat USENIX ATC '19 · on Thursday, 2019-07-11· at 10:25· USENIX ATC Track II: Grand Ballroom VII–IX·
summary
Describes CoCuckoo, a concurrent cuckoo-hashing design that reduces slow writes by detecting potential endless insertion loops using a directed pseudoforest of cuckoo paths and partitioning that graph into subgraphs. CoCuckoo applies graph-grained locking: threads lock a subgraph when inserting items that share a cuckoo path while allowing concurrent operations on different subgraphs, and the authors implemented the design and evaluated it with YCSB benchmarks.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:24Query Services in Cloud Storage Systems
- 0:52Hash structures
- 1:24Cuckoo Hashing
- 2:37Concurrency in Multi-core Systems
- 3:32Our Approach: CoCuckoo
- 4:12Pseudoforest
- 5:59Graph-grained Locking
- 8:16ZeroEmpty (Diff non non) 00
- 9:08ZeroEmpty (Same non)
- 10:06ZeroEmpty (Diff non max)
- 11:15Lock Granularity
- 11:51Subgraph Management
- 12:49Performance Evaluation
- 13:29Average Insertion Throughput
- 14:02Predetermination for Insertion
- 14:44Extra Space Overhead
- 16:05Conclusion
- 17:25Subgraph Implementation
related talks
18mCuckoo for Clients: Disaggregated Cuckoo Hashing
20mAdaptive Online Cache Capacity Optimization via Lightweight Working Set Size...
24mWrite-Optimized Dynamic Hashing for Persistent Memory
25mMemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing
01h 13mC++ Memory Model Meets High-Update-Rate Data Structures
18mPreview: KV-Stores and Databases
01h 08mDistributed Java Databases Under the Hood
43mImproving scalability; Reducing overhead in shared memory