See

(my thoughts and summary on the second paper I read this month as part of my endeavor to read ten research papers in June)

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

This research paper introduces readers to MemC3, which stands for Memcached with CLOCK and Concurrent Cuckoo Hashing. MemC3 is Memcached with modifications to make it faster and use less space. The researchers achieve the speed boost by allowing multiple reads and a single write to happen concurrently using their own concurrent implementation of Cuckoo Hashing. The space savings are gained by using the CLOCK algorithm to implement LRU cache eviction.

The authors begin by examining the existing use cases and design choices of Memcached. They notice that most Memcached use cases are read heavy, and that Memcached either (a) uses a single thread, or (b) (in newer versions) uses a single global lock. These two observations highlight areas where Memcached’s performance can be improved.

To improve the read and write performance and to enable concurrent operations the researchers replace Memcached hash table + linked list based cache with a 4-way set associate hash table that uses Cuckoo Hashing. I hadn’t heard of Cuckoo Hashing before reading this paper, and it is quite an interesting concept. To allow multiple readers and one writer the authors develop their own concurrent Cuckoo Hashing algorithm that combines lock striping and optimistic locking in a simple and easy to understand algorithm. This section (section 3.2) was the part of the paper that I enjoyed the most.

To save space and to implement an LRU cache eviction policy the authors use the CLOCK algorithm. The paper also describes how their cache eviction algorithm works safely with their concurrent cuckoo hashing algorithm.

The paper ends with an evaluation section that compares MemC3 and Memcached in a variety of configurations and workloads and shows that MemC3 almost always outperforms Memcached.