Write-Optimized Dynamic Hashing for Persistent Memory
summary
Implements Cacheline-Conscious Extendible Hashing (CCEH): a three-level directory→segment→cacheline-pocket layout that finds items with two cacheline accesses, guarantees failure-atomic directory updates without logging via a split body tree, and avoids expensive full-table rehashes by allocating 64-byte pockets inside segments. Uses a RAM-based PM emulator on a dual Xeon testbed with 160M key-value inserts; lazy deletion halves cache-line flushes versus copy-on-write, yields tail latency an order of magnitude lower and reduces maximum query latency by over two-thirds compared to prior PM hashing.
AI-written summary · about
chapters (19)
- 0:00Intro
- 1:14Background: Static Hashing
- 2:18Insertion Latency CDF
- 3:27Disk-based Extendible Hashing
- 4:39Extendible Hashing - Insertion
- 5:08Extendible Hashing - Bucket Split
- 5:50Extendible Hashing - Directory doubling
- 6:54Persistent Memory
- 8:02Challenge in In-Memory Extendible Hashing
- 9:49Segment: Intemediate Level
- 11:43Recovery: Split History Buddy Tree in CCEH
- 13:57Segment Split: Legacy CoW
- 14:21Segment Split: Lazy Deletion
- 15:25Experimental Setup
- 15:53CCEH VS Legacy Extendible Hash
- 19:01Conclusion
- 19:39Question?
- 20:35Insertion Performance Breakdown
- 21:23Load Factor
related talks
14mSEPH: Scalable, Efficient, and Predictable Hashing on Persistent Memory
25mMemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing
15mOne-sided RDMA-Conscious Extendible Hashing for Disaggregated Memory
40m"Gaining Constant time Lookup over Unorganized Data"
20mMitigating Asymmetric Read and Write Costs in Cuckoo Hashing for Storage Systems
16mJohnny Cache: the End of DRAM Cache Conflicts (in Tiered Main Memory Systems)
20mRevisiting Secondary Indexing in LSM-based Storage Systems with Persistent Memory
01h 08mC++ and Persistent Memory Technologies, Like Intel's 3D-XPoint