Lesson 6.4• 8 min read

Eviction algorithms and memory management

LRU, LFU, FIFO, Adaptive Replacement Cache (ARC), and Redis memory policies.

What you will learn

Compare LRU, LFU, FIFO and ARC by what they evict and where each fails.
Choose a Redis maxmemory-policy.
Explain how slab allocation fights fragmentation, and what it wastes.

Memory constraints and eviction policies

In-memory caches operate under strict RAM limits. When memory fills (maxmemory limit reached), the cache engine must evict existing keys to accommodate new insertions.

Eviction algorithm comparison

Algorithm	How it is usually built	Evicts	Good for	Weakness
LRU (least recently used)	Hash map plus doubly linked list, $O(1)$ per operation	The item unused for longest	Workloads where recent items are reused	A one-off scan of many cold items pushes the hot items out
LFU (least frequently used)	Access counters	The item used least often	Stable popularity, where favorites stay popular	Items that were popular long ago can linger, unless counts decay over time
FIFO (first in, first out)	Queue	The oldest inserted item, however often it is used	Simple buffers	Evicts hot items just because they are old
ARC (adaptive replacement cache)	Two LRU lists: one for items seen once recently, one for items seen at least twice	Balances the two lists automatically as the workload changes	Workloads that shift between recency and frequency	More bookkeeping than LRU: it also remembers up to as many recently evicted keys as the cache holds

Redis `maxmemory-policy` options

When Redis reaches its maxmemory limit, it evicts keys according to the configured policy:

noeviction: Evict nothing; commands that would add data return an error, while reads keep working.
allkeys-lru / volatile-lru: Least recently used, among all keys / among keys with a TTL.
allkeys-lfu / volatile-lfu: Least frequently used, among all keys / among keys with a TTL.
allkeys-random / volatile-random: At random, among all keys / among keys with a TTL.
allkeys-lrm / volatile-lrm (Redis 8.6+): Least recently modified.
volatile-ttl: Among keys with a TTL, the one with the shortest remaining TTL.

If none of your keys has a TTL, the volatile-* policies behave like noeviction. Redis suggests allkeys-lru as a good default when a subset of keys is accessed far more often than the rest. Note that Redis's LRU and LFU are approximations: Redis samples a few keys and evicts the best candidate among them, and its LFU counters decay over time so old popularity fades.

Slab allocation & memory fragmentation

Allocating and freeing many items of arbitrary sizes fragments memory:

Memcached slab allocation: Memory is carved into chunks of fixed sizes, grouped into slab classes whose sizes grow by a factor (1.25 by default) from a small minimum; each item goes into the smallest chunk it fits. This avoids general-purpose allocator fragmentation, but wastes the unused part of each chunk (internal fragmentation). Chapter 14 goes deeper.
Redis: Uses the jemalloc allocator in its default Linux builds. Fragmentation still happens, so Redis offers active defragmentation (off by default), which copies values into contiguous memory while the server runs.

Eviction: LRU, LFU, FIFO and ARC

Query / insert key:

Cache contents (4 / 5 slots used)Ordered so the next eviction is on the right

ITEM_B#1

Last access: t=9 · inserted: t=2

ITEM_A#2

Last access: t=8 · inserted: t=1

ITEM_D#3

Last access: t=7 · inserted: t=4

ITEM_C#4

Last access: t=3 · inserted: t=3

Empty RAM slot

Hit ratio

83%

Cache hits

Cache misses

Last eviction

None yet

Data structure

A doubly linked list and a hash map (O(1) get and put)

Eviction rule

Discards key with oldest access timestamp (List Tail).

Primary strength

Excellent for temporal locality (recent items re-accessed soon).

Known trade-off

Vulnerable to sequential scan thrashing (full-table dump pollutes cache).

Key takeaways

LRU suits workloads that reuse recent items but is flushed by one large scan; LFU suits stable popularity but keeps old favorites unless counts decay; ARC adapts between the two.
In Redis, allkeys-lru is a good default when some keys are far hotter than others; the volatile-* policies act like noeviction if no key has a TTL.
Redis's LRU and LFU are approximations that sample a few keys.
Memcached's slab classes avoid allocator fragmentation but waste the unused part of each chunk; Redis uses jemalloc and can defragment while running.

Sources

Adapted from The System Design Primer by Donne Martin, licensed under CC BY 4.0. Changes were made.