Cache Eviction Strategies you should know

In part one we covered caching strategies - how the cache and the database talk on reads and writes. This is the other half: a cache is finite memory, so when it fills up, something has to be thrown out, and the eviction policy decides what. This time we do not just name the policies - we implement each one from scratch in TypeScript, with the data structures and the complexity, so you could write them yourself. Caching is one of the core system design building blocks; this is the part where you build the cache, not just use it.

Every implementation below satisfies the same interface and a fixed capacity:

interface Cache<K, V> {
  get(key: K): V | undefined;   // returns the value and counts as an access
  put(key: K, value: V): void;  // inserts/updates; evicts if over capacity
}

One clarification before we start: eviction is not expiration. Expiration (TTL) removes an entry after a time, for freshness; eviction removes an entry because you are out of space. Everything here is about the second. The goal of every policy is to maximize the hit rate - keep what you will ask for again, drop what you will not. Each policy is a different guess at which is which.

LRU - Least Recently Used

The algorithm. Keep entries in order of last use. On every get or put, move that entry to the "most recently used" end. When you must evict, remove the entry at the "least recently used" end. The bet is temporal locality: recently used implies soon-to-be-used.

The trick is doing both operations in O(1). A plain array would make "move to front" O(n). So you combine two structures: a hash map for O(1) lookup by key, and a doubly linked list for O(1) reordering. The map points at list nodes; the list holds usage order.

class DLLNode<K, V> {
  prev: DLLNode<K, V> | null = null;
  next: DLLNode<K, V> | null = null;
  constructor(public key: K, public value: V) {}
}

class LRUCache<K, V> implements Cache<K, V> {
  private map = new Map<K, DLLNode<K, V>>();
  // sentinel head/tail remove all null-edge checks
  private head = new DLLNode<K, V>(null as any, null as any);
  private tail = new DLLNode<K, V>(null as any, null as any);

  constructor(private capacity: number) {
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  private remove(node: DLLNode<K, V>): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private addToFront(node: DLLNode<K, V>): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  get(key: K): V | undefined {
    const node = this.map.get(key);
    if (!node) return undefined;
    this.remove(node);       // detach from current position
    this.addToFront(node);   // reinsert as most-recently-used
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.remove(existing);
      this.addToFront(existing);
      return;
    }
    if (this.map.size >= this.capacity) {
      const lru = this.tail.prev!;   // least-recently-used sits at the back
      this.remove(lru);
      this.map.delete(lru.key);
    }
    const node = new DLLNode(key, value);
    this.addToFront(node);
    this.map.set(key, node);
  }
}

Both get and put are O(1). This is the canonical implementation and a classic interview question in its own right.

The pragmatic version. In JavaScript, a Map already preserves insertion order, so you can lean on it and skip the linked list - re-inserting a key moves it to the newest position:

class LRUCacheSimple<K, V> implements Cache<K, V> {
  private map = new Map<K, V>();
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key)!;
    this.map.delete(key);        // re-insert to mark as most-recent
    this.map.set(key, value);
    return value;
  }

  put(key: K, value: V): void {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.capacity) {
      this.map.delete(this.map.keys().next().value); // first key = oldest
    }
    this.map.set(key, value);
  }
}

The weakness worth knowing: LRU is not scan-resistant. A one-pass scan of many cold keys looks "recently used" to LRU and marches the hot set right out of the cache.

LFU - Least Frequently Used

The algorithm. Count how many times each entry is accessed and evict the lowest count. The bet is popularity, not recency. The hard part is keeping get, put, and eviction all O(1) including "find the least-frequent entry."

The design: a map of key -> node (node holds value and frequency), plus a map of frequency -> ordered set of keys at that frequency, plus a running minFreq. On access, move the key from its frequency bucket to the next one up. On eviction, take the oldest key from the minFreq bucket. Using a JS Set per bucket gives O(1) add/delete and preserves insertion order, so the oldest key at the minimum frequency (an LRU tiebreak) is just the first element.

class LFUNode<K, V> {
  freq = 1;
  constructor(public key: K, public value: V) {}
}

class LFUCache<K, V> implements Cache<K, V> {
  private nodes = new Map<K, LFUNode<K, V>>();
  private buckets = new Map<number, Set<K>>(); // freq -> keys (insertion-ordered)
  private minFreq = 0;

  constructor(private capacity: number) {}

  private bump(node: LFUNode<K, V>): void {
    const oldFreq = node.freq;
    const bucket = this.buckets.get(oldFreq)!;
    bucket.delete(node.key);
    if (bucket.size === 0) {
      this.buckets.delete(oldFreq);
      if (this.minFreq === oldFreq) this.minFreq++; // the min bucket emptied
    }
    node.freq++;
    if (!this.buckets.has(node.freq)) this.buckets.set(node.freq, new Set());
    this.buckets.get(node.freq)!.add(node.key);
  }

  get(key: K): V | undefined {
    const node = this.nodes.get(key);
    if (!node) return undefined;
    this.bump(node);
    return node.value;
  }

  put(key: K, value: V): void {
    if (this.capacity === 0) return;
    const existing = this.nodes.get(key);
    if (existing) {
      existing.value = value;
      this.bump(existing);       // a write counts as an access
      return;
    }
    if (this.nodes.size >= this.capacity) {
      const bucket = this.buckets.get(this.minFreq)!;
      const evictKey = bucket.values().next().value; // oldest at min frequency
      bucket.delete(evictKey);
      if (bucket.size === 0) this.buckets.delete(this.minFreq);
      this.nodes.delete(evictKey);
    }
    this.nodes.set(key, new LFUNode(key, value));
    if (!this.buckets.has(1)) this.buckets.set(1, new Set());
    this.buckets.get(1)!.add(key);
    this.minFreq = 1;            // a brand-new key has frequency 1
  }
}

Every operation is O(1). The weakness: without decay, an entry that was popular long ago keeps its high count forever and never leaves (stale popularity), while a genuinely new hot key is evicted before it builds a count. Production LFU periodically ages counts (halve them on an interval) to fix this.

FIFO - First In, First Out

The algorithm. Evict the oldest inserted entry, regardless of use. Note the one-line difference from LRUCacheSimple: FIFO's get does not reorder, so the eviction order is pure insertion order.

class FIFOCache<K, V> implements Cache<K, V> {
  private map = new Map<K, V>();
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    return this.map.get(key);          // access does NOT change eviction order
  }

  put(key: K, value: V): void {
    if (this.map.has(key)) { this.map.set(key, value); return; }
    if (this.map.size >= this.capacity) {
      this.map.delete(this.map.keys().next().value); // first inserted
    }
    this.map.set(key, value);
  }
}

O(1), trivial to write - and usually a worse hit rate than LRU precisely because it ignores access. It is here mostly to show that the reordering in LRU is the whole point.

Random Replacement

The algorithm. Evict a uniformly random entry. It sounds crude but needs zero usage bookkeeping and holds up surprisingly well. The only interesting part is doing random removal in O(1): keep a keys array and store each key's index, then evict with the swap-with-last trick.

class RandomCache<K, V> implements Cache<K, V> {
  private map = new Map<K, { value: V; index: number }>();
  private keys: K[] = [];
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    return this.map.get(key)?.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) { existing.value = value; return; }
    if (this.map.size >= this.capacity) this.evictRandom();
    this.map.set(key, { value, index: this.keys.length });
    this.keys.push(key);
  }

  private evictRandom(): void {
    const i = Math.floor(Math.random() * this.keys.length);
    const victim = this.keys[i];
    const last = this.keys[this.keys.length - 1];
    this.keys[i] = last;                 // move last into the hole
    this.map.get(last)!.index = i;        // fix its recorded index
    this.keys.pop();                      // drop the tail
    this.map.delete(victim);
  }
}

Approximate LRU - what Redis actually does

Exact LRU needs a linked list node and pointer updates per access; at millions of keys, that metadata and bookkeeping cost real memory. So Redis does not keep a perfect order. It stores a last-access clock on each entry and, on eviction, samples a handful of random keys and evicts the oldest of the sample - approximate LRU (and approximate LFU) for a fraction of the memory. Here is the idea:

class ApproxLRUCache<K, V> implements Cache<K, V> {
  private map = new Map<K, { value: V; atime: number; index: number }>();
  private keys: K[] = [];
  private clock = 0;
  constructor(private capacity: number, private sampleSize = 5) {}

  get(key: K): V | undefined {
    const e = this.map.get(key);
    if (!e) return undefined;
    e.atime = ++this.clock;              // "touch" - newer access time
    return e.value;
  }

  put(key: K, value: V): void {
    const e = this.map.get(key);
    if (e) { e.value = value; e.atime = ++this.clock; return; }
    if (this.map.size >= this.capacity) this.evictSampled();
    this.map.set(key, { value, atime: ++this.clock, index: this.keys.length });
    this.keys.push(key);
  }

  private evictSampled(): void {
    let victim = this.keys[0];
    let oldest = Infinity;
    for (let i = 0; i < this.sampleSize; i++) {   // sample, don't scan
      const k = this.keys[Math.floor(Math.random() * this.keys.length)];
      const at = this.map.get(k)!.atime;
      if (at < oldest) { oldest = at; victim = k; }
    }
    const vi = this.map.get(victim)!.index;        // swap-remove from keys
    const last = this.keys[this.keys.length - 1];
    this.keys[vi] = last;
    this.map.get(last)!.index = vi;
    this.keys.pop();
    this.map.delete(victim);
  }
}

Redis exposes this as maxmemory-policy (allkeys-lru, allkeys-lfu, allkeys-random, the volatile-* variants that only touch keys with a TTL, volatile-ttl, and noeviction). A larger sampleSize gets closer to true LRU at more cost - Redis defaults to 5, which is already very close in practice.

The advanced policies

Plain LRU and LFU each track a single signal. The state-of-the-art policies combine both and add scan resistance. You will rarely hand-roll these, but you should know what they do:

• Segmented LRU / 2Q: split the cache into a probationary segment and a protected segment; a new entry lands in probation and is only promoted to protected when it is accessed again. A one-time scan never reaches the protected segment, so the hot set survives.
• ARC (Adaptive Replacement Cache): keeps both a recency list and a frequency list and continuously shifts the boundary between them based on which is producing hits - self-tuning between LRU and LFU. Used in ZFS.
• W-TinyLFU: the current best-in-class for in-memory caches (Caffeine uses it, and Memcached uses a segmented LRU). It estimates each key's frequency with a tiny count-min sketch and admits a new entry only if its estimated frequency beats the entry it would evict.

The frequency estimator at the heart of TinyLFU is small enough to sketch here - a count-min sketch trades exactness for a fixed, tiny footprint:

class CountMinSketch {
  private rows: Uint32Array[];
  constructor(private width: number, private depth: number) {
    this.rows = Array.from({ length: depth }, () => new Uint32Array(width));
  }
  private hash(key: string, row: number): number {
    let h = (2166136261 ^ row) >>> 0;              // per-row seed
    for (let i = 0; i < key.length; i++) {
      h = Math.imul(h ^ key.charCodeAt(i), 16777619) >>> 0;
    }
    return h % this.width;
  }
  increment(key: string): void {
    for (let r = 0; r < this.depth; r++) this.rows[r][this.hash(key, r)]++;
  }
  estimate(key: string): number {                  // min across rows = estimate
    let min = Infinity;
    for (let r = 0; r < this.depth; r++) min = Math.min(min, this.rows[r][this.hash(key, r)]);
    return min;
  }
}

TinyLFU increments the sketch on every access, periodically halves all counters to age them, and on admission compares estimate(candidate) against estimate(victim) - admitting only when the newcomer is genuinely more popular. That admission filter is what makes it beat plain LRU and LFU on nearly every real workload.

Complexity and what to reach for

Policy	get / put	Extra memory	Reach for it when
LRU	O(1)	map + linked list	General purpose default
LRU (Map-based)	O(1)	one Map	You want LRU in a few lines
LFU	O(1)	map + buckets + counts	Stable hotspots (add aging)
FIFO	O(1)	one Map	Simplicity, order-only
Random	O(1)	keys array + index	Huge cache, metadata matters
Approx LRU	O(1) sampled	atime per key	Memory-bound (what Redis does)
W-TinyLFU / ARC	O(1) amortized	sketch / two lists	Best hit rate, scan-heavy

Start from LRU, reach for LFU when your traffic has stable hotspots, and know that the adaptive policies (ARC, W-TinyLFU) exist for when a plain policy's blind spot is hurting your hit rate. Whatever you pick, the score is the same: measure the hit rate, because a cache with the wrong policy can do worse than random.

Together with part one - the read/write strategy that keeps the cache in sync with the source of truth - this is the full toolkit for using a cache well: how it stays correct, and how it decides what to keep.