← Learnings

Why Redis Doesn't Implement "True" LRU

4 min·redis, caching, performance

One question that recently made me rethink cache eviction was this one.

If Redis uses LRU, why doesn't it maintain a heap, or a perfectly sorted list, of keys?

The answer comes down to optimizing the common case.

What a perfect ordering would cost

Imagine a Redis instance with 10 million keys. If Redis maintained a perfect LRU structure, every cache hit would have to update it.

WHAT A PERFECT LRU WOULD COST ON EVERY HIT GET user:123 O(1) THE LOOKUP — CHEAP update the LRU ordering O(log n) ON EVERY SINGLE READ, ON SHARED METADATA return the value
FIG 1 · THE ORDERING UPDATE SITS ON THE HOT PATH

Even though the lookup itself is O(1), updating a heap would be O(log n), and maintaining a doubly-linked LRU list would still mean modifying shared metadata on every single read. For a cache serving millions of requests per second, that is expensive — and it is expensive on the path that runs most often.

What Redis does instead: sample five

Rather than maintaining an exact ordering, Redis uses random sampling. When memory is full and a write arrives:

  1. Randomly sample a small number of keys — five, by default.
  2. Find the least recently used among them.
  3. Evict that key.

At first glance this seems inaccurate. What if all five sampled keys are hot? It's possible — but statistically very unlikely for most real-world workloads, and the cost of being wrong is one slightly premature eviction rather than a wrong answer.

The math: how unlikely are five hot keys?

A hot key is one that will be read again soon. If a share h of keys is hot, one random key is hot with chance h, and five are all hot with chance h × h × h × h × h = h5. The hash function scattered the keys, so five neighbours in the table are as good as five independent picks.

H TO THE FIFTHARITHMETIC
share hot   all five hot   about one
(h)         (h^5)          eviction in
10%         0.00001        100,000
20%         0.00032        3,125
50%         0.03125        32
80%         0.32768        3

Real traffic is skewed, so h is small and the top rows apply. The pool only lowers these odds, since it also holds colder keys from earlier rounds. The bottom row is where sampling struggles: raising maxmemory-samples to 10, as Redis suggests, takes it from 1 in 3 to about 1 in 9.

And “random” is looser than it sounds. To see why, picture how Redis stores keys. A Redis database is one big dictionary from key names to values, and underneath it sits a hash table: a long array of numbered positions in memory, called buckets. To store user:42, Redis runs the name through a hash function, which turns it into a bucket number, and puts the key in that bucket; to read it back, it hashes the name again and goes straight there. Redis adds buckets as keys arrive, so a bucket holds about one key, and many buckets are empty.

A HASH TABLE — THE NAME SAYS WHERE THE KEY LIVES store SET user:42 hash() bucket 5 read GET user:42 hash() bucket 5 THE NAME BECOMES A NUMBER SAME NAME, SAME NUMBER buckets cart:8362 0 1 2 sess:5467 3 4 user:42 5 order:3722 6 7 8 BUCKETS, 4 KEYS: REDIS ADDS BUCKETS AS KEYS ARRIVE, SO ABOUT ONE KEY EACH
FIG 2 · THE NAME DECIDES THE BUCKET

Sampling walks that array. Redis does not pick five buckets at random: it picks one random bucket and steps right, bucket by bucket, until it has collected five keys. Only the starting bucket is random, and that is still fair: the hash function placed each key by its name alone, not by how often it is read, so keys in neighbouring buckets have nothing to do with each other. Stepping to the next bucket is also much cheaper than jumping to a new random one.

SAMPLING — ONE RANDOM START, THEN A WALK RANDOM START buckets K X N A B D E R W C ONE BUCKET, TWO KEYS: THE WALK TAKES BOTH WALK FORWARD UNTIL IT HAS FIVE KEYS sample A B C D E NEIGHBOURS IN THE TABLE, YET UNRELATED KEYS
FIG 3 · ONLY THE STARTING BUCKET IS RANDOM

If you run Redis Cluster, don’t confuse those buckets with its 16,384 hash slots. A slot is how the cluster splits keys between servers: every key belongs to one slot (CRC16 of the key, mod 16,384), and each server owns a share of the slots. A bucket lives inside one server’s hash table: since Redis 7.4 every slot gets its own table, which adds buckets as its keys grow, so a bucket still holds about one key. Eviction picks a random slot first, then walks that slot’s buckets.

SLOT VS BUCKET — TWO HASHES, TWO JOBS key user:42 CRC16(KEY) MOD 16384 slots 0 1 2 … 15,880 … 16,383 16,384 SLOTS, FIXED: THEY PICK THE SERVER buckets cart:8362 sess:5467 user:42 order:3722 SLOT 15,880’S OWN HASH TABLE: BUCKETS GROW WITH ITS KEYS HASH(KEY) PICKS THE BUCKET · ABOUT ONE KEY EACH
FIG 4 · SLOTS PICK THE SERVER, BUCKETS PICK THE SPOT

The eviction pool

Redis goes one step further. Instead of discarding the remaining sampled keys after each eviction, it keeps the best candidates in a small eviction pool — sixteen entries, internally.

ITERATION 1 — SAMPLE FIVE, KEEP THE REST sample A B C D E pool A B C D E EVICT A — THE LEAST RECENTLY USED OF THE FIVE kept B C D E NOT DISCARDED — THEY ARE STILL GOOD CANDIDATES
FIG 5 · THE FOUR SURVIVORS ARE NOT THROWN AWAY

Need more memory? The next round samples five fresh keys and merges them into what the pool already holds.

ITERATION 2 — THE POOL IS ALREADY BETTER THAN RANDOM kept B C D E + sample F G H I J merged B C D E F G H I J evict ? THE WORST OF NINE, NOT THE WORST OF FIVE — STILL ONLY FIVE RANDOM READS
FIG 6 · NINE CANDIDATES FOR THE PRICE OF FIVE READS

The pool accumulates better candidates while the sampling cost stays flat. Every round still reads only a handful of random keys, but the set it chooses from has been filtered by every round before it.

That does not mean the pool grows forever. It has sixteen slots, kept in order from the key used most recently to the key unused longest. Once all sixteen are full, a sampled key gets in only if it has gone unused longer than the pool’s most recently used key, which it pushes out.

ONCE FULL — THE POOL STOPS AT SIXTEEN pool C D E F G H I J K L M N O P Q R ← USED MOST RECENTLY: C IS PUSHED OUT UNUSED LONGEST → sample S T U V W T WENT UNUSED LONGER THAN C · THE REST DID NOT after D E F T G H I J K L M N O P Q R STILL SIXTEEN · EVICT R, THE KEY UNUSED LONGEST
FIG 7 · ONCE FULL, A KEY GETS IN ONLY BY PUSHING ANOTHER OUT

Why this works

Redis is optimizing for the shape of real traffic: millions of GETs, and relatively few evictions. Paying a maintenance cost on every read buys accuracy in the rare event and charges for it in the common one. Sampling inverts that — it does a small amount of work only when memory is exhausted.

Accept a near-perfect approximation during rare events to keep the hot path extremely fast.

That is one of the reasons Redis continues to scale so well while delivering hit rates remarkably close to a true LRU implementation.