# 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](/concepts-you-should-know-about-system-designing-part-1); this is the part where you build the cache, not just use it.

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

```typescript
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.

```typescript
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:

```typescript
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.

```typescript
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.

```typescript
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.

```typescript
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](https://redis.io) 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:

```typescript
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](https://github.com/ben-manes/caffeine) uses it, and [Memcached](https://memcached.org/) 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:

```typescript
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.