Eviction: LRU, LFU and TTL

The problem: the cache is full

Snip has 600 million links, and its Redis cluster has room for about 40 million of them. Every new entry that goes in means an old one comes out. Which one? Choose well and the cache answers 99% of redirects; choose badly and it keeps links nobody clicks while the popular ones miss.

Two separate mechanisms remove entries:

• Expiry: an entry's TTL runs out. That's about freshness: how old a copy may be.
• Eviction: the cache is full and must make room. That's about space, and the eviction policy decides which entry goes.

The policies

The optimal policy can't be built, since no cache knows the next request. It's useful in a simulator, because it shows how much room for improvement is left.

Try it

The run sends 60,000 requests for 20,000 links whose popularity follows a power law, like real link clicks: a few links get most of the traffic. The hit rates are lower than Snip's real 99% because the run is short (every link's first request is a miss) and the cache holds only a few percent of the links. What matters is the comparison:

• Steady popularity (cache of 1,000): FIFO hits 42.9%, LRU 47.1%, LFU 54.4%, optimal 65.6%. Counting how often a link is used beats remembering when it was last used, because a popular link stays popular.
• Popularity shifts: LFU falls to 32.8% while LRU holds at 46.4%. After each shift, yesterday's links still have huge counts, so LFU keeps them and evicts today's links before they can build up counts. It never forgets.
• A crawler scan, where half the requests in the middle third are for old links requested once: LRU's hit rate falls to about 18% during the scan, LFU's to about 27%. Every one-off link is "recently used", so LRU throws out popular links to make room for them; LFU sees they've been used once and evicts them first.
• A bigger cache narrows the gaps: at 4,000 links, LRU and LFU are within a few points of each other. Policy matters most when memory is tight.

So neither LRU nor LFU wins everywhere. That's why real caches use something in between.

What real caches do

Redis doesn't run exact LRU, which would mean updating a linked list on every read. When it needs room, it samples a few keys at random (5 in its example configuration; 10 gets closer to true LRU) and evicts the least recently used of those, keeping a pool of good candidates between rounds. It's close to true LRU at a fraction of the cost. Since Redis 4.0 it also offers LFU, with two twists that fix the problem in the lab: the counter is logarithmic, so it saturates around a million reads instead of growing forever, and it decays over time (by default every minute), so old favourites fade.

Redis also asks you which keys may be evicted at all. allkeys-lru and allkeys-lfu consider every key; volatile-lru, volatile-lfu and volatile-ttl consider only keys with a TTL; and noeviction refuses new writes with an error when memory is full. For a pure cache, an allkeys policy is right. noeviction suits Redis used as a store, where silently losing data would be worse.

Caffeine, a widely used Java cache, uses W-TinyLFU: new entries go into a small LRU "window", and when one is pushed out of the window it's only admitted to the main cache if a compact frequency sketch says it's been used more often than the entry it would replace. The window lets brand-new popular keys in, and the frequency check keeps one-off scans out: the best of both lab results.

TTLs are part of the policy

A TTL bounds staleness, but it also shapes what the cache holds. An entry that expires frees its space whether or not the cache was full, so short TTLs keep the cache full of what's recently been asked for. When Twitter studied its production caches (below), it found TTLs were often what defined each cache's working set, more than eviction did.

Two rules of thumb:

• Give every entry a TTL, even if it's long. It's the safety net for every invalidation you forget (06.04 Invalidation and staleness).
• Add jitter. Entries filled at the same moment (a cache warm-up, a deploy) with the same TTL all expire at the same moment too. Use 3,600 seconds plus or minus 10% at random, and expiries spread out (06.05 Stampedes and request coalescing).

A small LRU cache with TTLs

A JavaScript Map remembers insertion order, which is enough for an LRU: move an entry to the end on every read, and evict from the front.

export class LruCache<V> {
  // A Map remembers insertion order, so its first key is always the least recently used.
  private entries = new Map<string, { value: V; expiresAt: number }>();

  constructor(
    private readonly capacity: number,
    private readonly ttlMs: number,
    private readonly now: () => number = Date.now,
  ) {}

  get(key: string): V | undefined {
    const entry = this.entries.get(key);
    if (!entry) return undefined;
    if (entry.expiresAt <= this.now()) {
      this.entries.delete(key); // expired: treat as a miss
      return undefined;
    }
    this.entries.delete(key); // move to the most recently used end
    this.entries.set(key, entry);
    return entry.value;
  }

  set(key: string, value: V, ttlMs = this.ttlMs) {
    this.entries.delete(key);
    if (this.entries.size >= this.capacity) {
      const oldest = this.entries.keys().next().value!;
      this.entries.delete(oldest); // evict the least recently used
    }
    this.entries.set(key, { value, expiresAt: this.now() + ttlMs });
  }

  delete(key: string) {
    this.entries.delete(key);
  }
}

Every operation is constant time. This is the kind of cache Snip's app servers use for viral codes: a few thousand entries with a TTL of five seconds. (Expired entries are only removed when read or pushed out; for a small cache that's fine.)

Recap

Interview questions