HotRing: A Hotspot-Aware In-Memory Key-Value Store
summary
HotRing claims a 2.58× throughput win on highly skewed workloads by reordering hash chains into an ordered-ring hash and advancing per-bucket head pointers toward hot keys, detecting shifts with statistical sampling plus an inexpensive random movement fallback. It implements lock-free reads/updates and lock-free header moves and online ring rehashing, evaluated on 2 GB of memory with 64 threads and Zipf skew where ~1% of keys get ≈90% of accesses, and reports much lower memory-access counts per hit.
AI-written summary · about
chapters (8)
- 0:00Hot spot problem in caching
- 3:02Hash table limitations
- 6:24Proposed circular ring method
- 8:57Hot spot identification
- 10:53Lock-free concurrent operations
- 12:41Lock-free rehashing algorithm
- 14:13Performance evaluation
- 20:35Conclusion and Q&A
related talks
18mCuckoo for Clients: Disaggregated Cuckoo Hashing
37mBeyond Hot Spots: Revolutionising OpenSearch Performance Through Heat-Aware Operations
14mSEPH: Scalable, Efficient, and Predictable Hashing on Persistent Memory
15mOne-sided RDMA-Conscious Extendible Hashing for Disaggregated Memory
40m"Gaining Constant time Lookup over Unorganized Data"
15mImproving Performance of Flash Based Key-Value Stores Using Storage Class Memory...
24mWrite-Optimized Dynamic Hashing for Persistent Memory
22mPinK: High-speed In-storage Key-value Store with Bounded Tails