Write-Optimized Dynamic Hashing for Persistent Memory

Explore a 24-minute conference talk from FAST '19 that delves into Cacheline-Conscious Extendible Hashing (CCEH), a novel approach for optimizing hash-based indexing structures on persistent memory (PM). Learn how CCEH addresses the challenges of achieving efficiency and failure-atomicity in dynamic hash expansion and shrinkage for low latency storage media. Discover the benefits of CCEH, including reduced overhead in dynamic memory block management, constant hash table lookup time, and guaranteed failure-atomicity without explicit logging. Examine experimental results demonstrating CCEH's ability to adapt its size under fine-grained failure-atomicity constraints and its significant reduction in maximum query latency compared to state-of-the-art hashing techniques. Gain insights into topics such as static hashing, disk-based extendible hashing, persistent memory challenges, recovery mechanisms, and performance comparisons through a comprehensive syllabus covering various aspects of this innovative hashing approach.

Intro
Background: Static Hashing
Insertion Latency CDF
Disk-based Extendible Hashing
Extendible Hashing - Insertion
Extendible Hashing - Bucket Split
Extendible Hashing - Directory doubling
Persistent Memory
Challenge in In-Memory Extendible Hashing
Segment: Intemediate Level
Recovery: Split History Buddy Tree in CCEH
Segment Split: Legacy CoW
Segment Split: Lazy Deletion
Experimental Setup
CCEH VS Legacy Extendible Hash
Conclusion
Question?
Insertion Performance Breakdown
Load Factor