PDL Abstract

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

Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI'13), Lombard, IL, April 2013. Supersedes Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-12-116. November 2012.

Bin Fan, David G. Andersen, Michael Kaminsky*

School of Computer Science
Carnegie Mellon University

*Intel Labs


This paper presents a set of architecturally and workloadinspired algorithmic and engineering improvements to the popular Memcached system that substantially improve both its memory eciency and throughput. These techniques—optimistic cuckoo hashing, a compact LRU-approximating eviction algorithm based upon CLOCK, and comprehensive implementation of optimistic locking—enable the resulting system to use 30% less memory for small key-value pairs, and serve up to 3x as many queries per second over the network. We have implemented these modifications in a system we call MemC3—Memcached with CLOCK and Concurrent Cuckoo hashing—but believe that they also apply more generally to many of today's read-intensive, highly concurrent networked storage and caching systems.

KEYWORDS: hashing, performance, memory efficiency, key-value store

FULL TR: pdf