MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing
summary
MemC3 replaces memcached’s chaining table and linked‑list LRU with optimistic cuckoo hashing (4‑way buckets, per‑key version counters, serialized inserts) and a CLOCK replacement LRU approximation, yielding a compact implementation that stores about 30% less memory for small key–value items and sustains up to ~3× the query throughput (measured end‑to‑end on a 12‑core server). The system is implemented and evaluated; the changes reduce pointer/header overhead and avoid get‑path locks while preserving correctness.
AI-written summary · about
chapters (24)
- 0:00Introduction
- 0:53Sharding
- 2:02What is MemCache
- 3:04How MemCache is used
- 3:42Takeaways
- 4:03RRU Eviction
- 4:14Problems
- 5:29Optimizations
- 5:59Other Optimizations
- 6:29Chaining Hash Table
- 7:07Linear probing
- 7:49Cuckoo hashing
- 8:20Insert
- 10:01Set Associativity
- 10:28Concurrency
- 10:42False Miss Problem
- 11:31TwoStep Insert
- 14:33Clock Base
- 15:16Solution
- 15:39Evaluation
- 17:18Performance
- 19:15Summary
- 19:54Questions
- 20:16Network Delay
related talks
49mCache à la carte: a framework for in-memory caching
24mWrite-Optimized Dynamic Hashing for Persistent Memory
37mMemtable Pluggability and Alternate Memtables (CEP-11 & CEP-19)
12mSegcache: a memory-efficient and scalable in-memory key-value cache for small objects
13mBMC: Accelerating Memcached using Safe In-kernel Caching and Pre-stack Processing
18mCuckoo for Clients: Disaggregated Cuckoo Hashing
20mMitigating Asymmetric Read and Write Costs in Cuckoo Hashing for Storage Systems
20mAdaptive Online Cache Capacity Optimization via Lightweight Working Set Size...