Cache eviction

Two caches of the same size get every request. A request is a hit when its key is already in the cache. Otherwise it is a miss: the value is loaded, from a database in a real system, and put in the cache, and if the cache is full one key is evicted first to make room. The two caches differ only in which key they throw out.

LRU (least recently used) lists its keys from the one used most recently to the one used longest ago. LFU (least frequently used) lists them by how many times each has been used, and on a tie puts the one used longest ago lower. In both lists the key at the bottom goes next. The traffic sends 68% of its requests to three keys and spreads the rest over seven. Those shares are made up for the lab, but real traffic is often this lopsided.

LRU bets on recency: a key used a moment ago will probably be used again soon. LFU bets on frequency: a key used often will keep being used often. When the same few keys stay popular, the frequency bet wins. From a fresh start, play traffic for a minute at a capacity of 4 and compare the hit ratios. LFU soon counts A, B and C up and holds on to them whatever else comes through. LRU drops one of them whenever four other keys are requested before it comes round again, and pays a miss to load it back.

Watch LFU's bottom slot too. A new key starts with a count of 1, the lowest there is, so it is the first to go at the next miss. That shields the popular keys, but it can also lock in the wrong one. Press Reset, request D three times, then play traffic: D's head start keeps it in the cache, and C, more than twice as popular, keeps dropping out of the bottom slot.

A scan reads many keys once each: a report, a backup, a batch job walking a table. Play traffic until both caches hold A, B and C, then press Scan. Each scan key is the most recent key when it arrives, so LRU pushes out its popular keys to keep keys nobody will ask for again. After six of them LRU holds nothing but scan keys, and it misses on A, B and C until each one is loaded again. LFU puts every scan key in with a count of 1, so the scan only pushes out other keys used once, mostly the scan keys before it. A, B and C stay.

LRU variants resist scans without counting every use. Segmented LRU splits the cache in two: a new key goes into a probation segment, and only a second hit moves it into a protected one, so a scan can only churn probation. 2Q keeps keys seen once in a small first-in, first-out queue in front of the main LRU list, to the same effect. MySQL's InnoDB buffer pool does something similar: a page read from disk goes into the middle of its LRU list, not the front, so a full table scan can't push out the pages that queries use most.

LFU's counts only ever go up. A key that was popular an hour ago keeps its high count and its slot, while the keys that are popular now arrive with a count of 1 and are the first to go. Play traffic for a minute, then switch Popular keys to H, I, J. LRU follows the new traffic within a few requests. LFU keeps A, B and C, which hardly anyone asks for now, while H, I and J take turns in its bottom slot. Watch the strip: LFU's misses pile up and its hit ratio falls.

So LFU caches in production let counts age. Redis's LFU mode decays its counters as time passes. Caffeine, a Java caching library, uses W-TinyLFU: approximate counts that are halved from time to time, and a small LRU window where new keys start, so they can be used again before they are judged. Both keep frequency's defence against scans without letting old popularity hold a slot forever.

“Design an LRU cache” with get and put in O(1) time is a classic coding question. The standard answer:

• a hash map from each key to a node, and a doubly linked list of the nodes, most recent at the head;
• get finds the node through the map, unlinks it and moves it to the head;
• put adds a node at the head, and if the cache is over capacity, removes the tail node and deletes its key from the map, which is why each node stores its key;
• the list is doubly linked because unlinking a node needs its neighbour on each side, and sentinel head and tail nodes save the checks for an empty list.

In JavaScript and TypeScript a Map already iterates in insertion order, which is what the code below relies on. Say so, then offer to build the linked list by hand, since that is usually what the interviewer wants to see. The LFU follow-up is O(1) too: map each count to its keys in recency order, and keep the lowest count at hand. This lab's LFU works that way.

In a system design round the cache sits in front of a database, and the questions are about running it:

• Cache-aside. The application reads the cache first; on a miss it reads the database and puts the value in the cache. On a write it updates the database and deletes the cached key rather than updating it, so two writes racing each other can't leave the older value cached.
• Eviction is not expiry. A key is evicted because the cache is full, and expires because its time to live (TTL) ran out, however much room is left. The TTL bounds how stale a value can get; the eviction policy decides what goes when memory runs out. In Redis, EXPIRE sets a TTL and maxmemory-policy sets the eviction: allkeys-lru and allkeys-lfu choose from every key, and the volatile- versions only from keys with a TTL. Redis's LRU and LFU are both approximate. It samples a few keys and evicts the best candidate among them, rather than keeping every key in order.
• Cache stampede. When a popular key expires, every request that arrives before it is loaded again misses at the same moment and goes to the database. Let one request rebuild the value while the rest wait or get the old one, refresh popular keys shortly before they expire, and add random jitter to TTLs so keys written together don't expire together.
• Hit ratio is the number to quote. At 90%, one read in ten reaches the database; at 99%, one in a hundred. Those nine points cut database reads tenfold.

The lab's LRU cache. Deleting a key and setting it again moves it to the end of the Map, so the first key is always the least recently used. put returns the key it evicted, which is how the lab names it.

1class LruCache<V> {2  private map = new Map<string, V>();3 4  constructor(private capacity: number) {}5 6  get(key: string): V | undefined {7    const value = this.map.get(key);8    if (value !== undefined) {9      // Set it again: it moves to the end, the most recent place.10      this.map.delete(key);11      this.map.set(key, value);12    }13    return value;14  }15 16  // Stores the value and returns the key it evicted, if any.17  put(key: string, value: V): string | null {18    let evicted: string | null = null;19    if (this.map.has(key)) {20      this.map.delete(key);21    } else if (this.map.size >= this.capacity) {22      // A Map's first key is the one set longest ago.23      const oldest = this.map.keys().next();24      if (!oldest.done) {25        evicted = oldest.value;26        this.map.delete(oldest.value);27      }28    }29    this.map.set(key, value);30    return evicted;31  }32}