Lock-free Concurrent Level Hashing for Persistent Memory
summary
Presents clevel hashing, a lock-free hash index for persistent memory (tested on Intel Optane DC PMM) aimed at reducing contention and crash-consistency overheads. Uses a multi-level layout so background threads can resize without blocking queries, and relies on atomic primitives plus context-aware schemes to make search/insert/update/delete lock-free and crash-consistent. Reports up to 4.2× speedup on YCSB workloads versus prior PM hashing indexes.
AI-written summary · about
chapters (22)
- 0:00Intro
- 0:19Persistent Memory (PM)
- 0:50PM Optimization 1. High overhead for writes
- 3:18Hashing Collisions and Resizing Hash collisions
- 3:58Concurrent PM Hashing The importance of concurrency -Fast indexing for TB-scale PM data
- 4:26PM Variants of Concurrent Hashing
- 5:31Level Hashing OSDI '18 PM-friendly hashing index
- 6:19Concurrency in Level Hashing
- 6:59Challenges for PM Hashing
- 7:34Our Approach: Clevel Hashing
- 8:20Dynamic Multi-level Structure
- 9:52Components
- 10:31Non-blocking Resizing Resizing steps
- 13:51Lock-free Search
- 15:16Lock-free Insertion
- 18:32Failures of Lock-free Update
- 19:37Lock-free Deletion
- 20:04Crash Recovery Crash consistency for lock-free Clevel hashing
- 20:44Experimental Setup
- 21:01Load Factor
- 21:27Micro-benchmarks
- 22:11Conclusion
related talks
25mMaking Hash Parallel, Thread-Safe and Fast!
21mEvery Data Structure Deserves Lock-Free Memory Reclamation
01h 38mLock-free Programming is Dead - Long Live Lock-free Programming!
55m “High Performance C++ Concurrent Transactional Data Structures"
15mHTMFS: Strong Consistency Comes for Free with Hardware Transactional Memory...
14mNap: A Black-Box Approach to NUMA-Aware Persistent Memory Indexes
01h 11mLock-Free Programming (or, Juggling Razor Blades), Part II
12mSPHT: Scalable Persistent Hardware Transactions