How Redis Cheats Logic to Scale: The Masterclass of Probabilistic Expiration

If you have ever implemented a cache with TTLs (time-to-live), you have likely faced a tricky balance: how do you efficiently expire entries without slowing down writes or wasting memory?

Redis — the in-memory data store famous for its sub-millisecond latency — has an elegant solution. It does not rely on complex data structures like heaps or sorted lists to manage expirations. Instead, it uses a little randomness and a lot of clever engineering.

Let’s unpack how it works.

The Naïve Approach

Imagine you are designing your own cache. You want every entry to expire after some duration. The straightforward solution is:

1. Keep a sorted list (or min-heap) of keys by expiration time.
2. Periodically check the earliest ones and delete any that are past due.

This works… but it is not cheap. Each insertion into a heap costs O(log n), and with millions of keys, that adds up.

Redis was designed for millions of writes per second; an O(log n) write path simply wouldn’t fly. So how does Redis avoid this?

Redis’ Two-Pronged Approach

Redis uses two complementary mechanisms to handle expirations efficiently:

1. Lazy Expiration

Every time a key is accessed (say, via GET or HGET), Redis checks whether it is expired.

If yes, it deletes it right away and pretends the key never existed. That is free cleanup, assuming the key is ever accessed again.

But what about keys that expire and are never touched? That is where the second mechanism kicks in.

2. Active Expiration (the “Random Cleanup Loop”)

Internally, Redis keeps a separate dictionary called expires, which maps keys to their expiration times:

expires["foo"] = 1730665000000  // Unix time in ms

Only keys with a TTL are in this dictionary.

About 10 times per second, Redis runs a background process (activeExpireCycle) that does this:

1. Sample 20 random keys from the expires dictionary.
2. If a sampled key’s TTL has passed, delete it.
3. If more than 25% of the sampled keys were expired, run another round, up to a CPU time limit.

Here is a simplified version of the logic:

for each db in redis:
    repeat:
        expired_count = 0
        for i in 1..20:
            key = random_key(db.expires)
            if key.is_expired():
                delete(key)
                expired_count++
        if expired_count < 5:  // <25%
            break

That is it. No global heap. No O(log n) operations. Just random sampling and adaptive cleanup.

How Does Redis Pick “Random” Keys?

This is where the design really shines. Redis’ hash tables support O(1) random sampling. Internally, random_key picks a random bucket in the hash table and returns the first key it finds there. That means Redis can fetch random keys without scanning the entire dictionary or maintaining a separate index. Do this 20 times, and you get 20 random TTL’d keys, fast!

Why Randomness Works

At first glance, this sounds too hand-wavy. What if Redis just keeps picking unexpired keys?

Here is the probabilistic magic:

If a large portion of keys are expired (say 30–40%), the chance of picking an expired key in 20 samples is very high. When that happens, Redis immediately runs another round. It keeps looping until fewer than 25% of sampled keys are expired.

Statistically, the system self-regulates:

Redis automatically cleans more aggressively when there is a backlog of expired keys, and relaxes when things are tidy. It is a feedback loop powered by probability.

The Payoff

This design yields three powerful benefits:

Tuning the Behavior

A few internal settings control this behavior:

These can be tuned for large deployments where millions of keys expire frequently, but defaults work beautifully for most workloads.

A Lesson in Systems Design

Redis’ key expiration strategy is a case study in probabilistic system design using randomness to balance performance and correctness.

Rather than maintaining a perfectly accurate expiration queue, Redis accepts approximate cleanup in exchange for blazing speed. And because of statistical feedback, it still converges to the right state.

It is a reminder that sometimes, the smartest engineering move isn’t to be perfect, it is to be good enough, fast.

Final Thought

Redis shows that randomness is not the enemy of determinism — when wielded carefully, it is a tool for building fast, self-correcting systems.

So the next time you are designing a cache or scheduler, ask yourself:

Do I really need a perfect global order… or can a bit of randomness do the job?