Paper notes: MemC3, a better Memcached

MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing

Fan and Andersen, NSDI 2013

The big idea

This is a paper about choosing your data structures and algorithms carefully. By paying careful attention to the workload and functional requirements, the authors reimplement memcached to achieve a) better concurrency and b) better space efficiency. Specifically, they introduce a variant of cuckoo hashing that is highly amenable to concurrent workloads, and integrate the venerable CLOCK cache eviction algorithm with the hash table for space-efficient approximate LRU.

Optimistic cuckoo hashing

Cuckoo hashing has some problems under high-concurrency. Since each displacement requires accessing two buckets, careful locking is required to make sure that updates don’t conflict, or worse deadlock since you need to lock the entire path through the hash-table on each insert. Without this locking there’s a risk of false negatives due to missing a key move that’s in flight (note that keys can’t be moved atomically since they’re multi-byte strings). The idea in this paper is to serialise on a single writer (thereby avoiding deadlocks), and to search forward for a valid ‘cuckoo path’ (series of displacements), followed by tracing that path backwards and moving keys one at a time, effectively moving the hole, not the key. Therefore there’s no way the key can not be present in the table; in fact it might be in two places at once. Writer / reader conflicts might happen when a key gets moved out of the space in which the reader looks for it. The answer is to optimistically lock by using version numbers (striped across many keys, to stay cache and space efficient, nice idea), and an odd-even scheme. When a version is odd, the writer is moving the key and readers should retry their read from the start; when it is even, the key is correct as long as the version does not change during the read of the key (if it changes, they need to re-read the key). For more details, see David Andersen’s blog. See also the slides from NSDI.


Memcached spends 18-bytes for each key (!) on LRU maintenance; forward and backward pointers and a 2-byte reference counter. But why the need for strict LRU? Instead use CLOCK: 1-bit of recency that is set to 1 on every Update(). A ‘hand’ pointer moves around a circular buffer of entries. If the entry under the hand pointer has a recency value of 0, it is evicted, otherwise its recency value is set to 0 and the next item in the buffer is interrogated. The versioning scheme described above is used to coordinate when an item is being evicted (but may be concurrently read). If the eviction process decides to evict an entry, its version is incremented to indicate that it is being modified (i.e. to an odd value). Then the key is removed.


© - 2023 · Paper Trail · Theme Simpleness Powered by Hugo ·