# 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

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.