Replacing the cache replacement algorithm in memcached

In this post we delve into a reworking of memcached’s Least Recently Used (LRU) algorithm which was made default when 1.5.0 was released. Most of these features have been available via the “-o modern” switch for years. The 1.5.x series has enabled them all to work in concert to reduce RAM requirements.

When memcached was first deployed, it was typically co-located on backend web servers, using spare RAM and CPU cycles. It was important that it stay light on CPU usage while being fast; otherwise it would affect the performance of the application it was attempting to improve.

Over time, the deployment style has changed. There are frequently fewer dedicated nodes with more RAM, but spare CPU. On top of this web requests can fetch dozens to hundreds of objects at once, with the request latency having a greater overall impact.

This post is focused on the efforts to reduce the number of expired items wasting cache space, general LRU improvements, as well as latency consistency.