Cache Eviction Strategies: LRU, LFU, and FIFO in Redis, Memcached, Guava Cache, and Ehcache

1. LRU

Simple Redis

Redis 3.0 release notes claim a significant improvement in the LRU algorithm; however, the source reveals that the older “approximate LRU” implementation was extremely simple, randomly selecting three entries and deleting the one with the longest idle time, repeating until enough memory is freed.

In Redis 3.0 the algorithm was refined: five random entries are selected, inserted into a 16‑element sorted queue based on idle time, the head of the queue is evicted, and the process repeats, offering a modest improvement.

Standard Memcached

Memcached uses a textbook LRU implementation based on a doubly‑linked list stored in each slab; items are inserted at the head and removed from the tail when memory limits are exceeded.

Guava Cache

Guava Cache also maintains a doubly‑linked queue (AccessQueue in LocalCache) and evicts entries from the tail when the cache exceeds its capacity.

Ehcache (Redis‑like laziness)

Ehcache follows a similar “approximate LRU” approach as Redis 2.6, randomly picking eight entries, selecting the oldest, and writing it to disk before eviction.

Summary

Redis is not primarily designed as a cache; its default policy is no‑eviction, and the approximate LRU is a lightweight solution, whereas Ehcache is a dedicated cache system with a more elaborate eviction strategy.

2. Expired Key Deletion

One approach is to attach a timer to each expiring element, but the per‑key thread overhead is usually avoided.

Instead, systems use lazy checking (checking expiration on access) combined with periodic active eviction.

Redis

Redis implements active expiration in activeExpireCycle() , running every 100 ms in the main thread, sampling 20 random keys; if a quarter are expired, it immediately starts another cycle, limiting each cycle to 1 ms.

Memcached

Memcached runs an LRU “crawler” thread at configurable intervals (default 100 ms), scanning the tail of the LRU list; it checks a configurable number of entries per run, offering better hit rates than Redis’s random sampling but without immediate re‑triggering.

Guava Cache

Guava Cache stores all entries with the same expiration time; it walks the LRU queue without a limit, invoking cleanup during each write operation via preWriteCleanup() .

Ehcache

Ehcache performs lazy expiration in memory and active expiration only on disk; a background thread runs roughly every eight hours, scanning all disk entries, making its expiration handling the weakest among the examined systems.