LRU Caches: Constant-Time Eviction for Real Systems

Introduction

An LRU (Least Recently Used) cache is a data store with a fixed capacity that tracks when each entry was last accessed. When the cache is full and new data arrives, the cache makes room by removing the entry that has gone unused for the longest time. This removal rule is called the eviction policy, and LRU is the most widely used one because data that was needed recently tends to be needed again.

We have already covered the two ingredients separately on this blog: HashMaps give us constant-time lookup by key, and linked lists give us constant-time reordering. An LRU cache is the classic payoff for learning both, because it needs each structure to cover the other one's weakness. This post builds one from those parts, shows the short version JavaScript gives you almost for free, and finishes with the workloads where LRU is the wrong choice.

Why Eviction Policy Is the Whole Game

A cache earns its keep through its hit rate: the fraction of reads it can answer without going to the slower layer behind it. Capacity being fixed, hit rate is decided almost entirely by what you choose to evict.

LRU bets on temporal locality: a key that was touched recently is likely to be touched again soon. That bet pays off in most request-driven systems. The same session hits the same user record on every request. The same handful of product pages absorbs most of a shop's traffic. Yesterday's blog post gets today's readers.

The policy sounds trivial to state. The engineering problem is doing it fast. On every read you must record "this key is now the most recent," and on every eviction you must find "the key touched longest ago." Do either of those in O(n) and the cache starts slowing down the hot path it exists to speed up.

The Naive Version and Where It Breaks

The direct translation of the policy keeps a timestamp per entry:

// The obvious approach: scan for the oldest timestamp. Do not ship this.
class NaiveLRU<K, V> {
  private entries = new Map<K, { value: V; touched: number }>();
  private tick = 0;

  constructor(private readonly capacity: number) {}

  get(key: K): V | undefined {
    const entry = this.entries.get(key);
    if (!entry) return undefined;
    entry.touched = ++this.tick;
    return entry.value;
  }

  set(key: K, value: V): void {
    if (!this.entries.has(key) && this.entries.size >= this.capacity) {
      let oldestKey: K | undefined;
      let oldestTick = Infinity;
      for (const [k, e] of this.entries) {
        if (e.touched < oldestTick) {
          oldestTick = e.touched;
          oldestKey = k;
        }
      }
      this.entries.delete(oldestKey as K);
    }
    this.entries.set(key, { value, touched: ++this.tick });
  }
}

Reads are fine. Eviction is a full scan: O(n) per insert once the cache is full, and a full cache is the steady state of every useful cache. At 100,000 entries and a few thousand writes per second, that loop is your CPU profile.

The fix is to stop searching for recency and start storing the entries in recency order, so the oldest one is always sitting at a known position.

The Classic Design: HashMap Plus Doubly-Linked List

The textbook structure keeps every entry in two places at once:

• A HashMap from key to list node, so any entry is reachable in O(1).
• A doubly-linked list of those same nodes, ordered from most to least recently used.

        HashMap                Recency list (most recent first)

  "a" ─────────────►  head ⇄ [a] ⇄ [c] ⇄ [b] ⇄ tail
  "b" ───────────────────────────────────┘
  "c" ─────────────────────────┘

Every operation is a small, fixed number of pointer moves:

• get(key): HashMap lookup, unlink the node, relink it at the head.
• set(key, value): insert at the head; if over capacity, unlink the node before the tail and delete its key from the map.

The doubly-linked list is essential. A singly-linked list can't unlink a node in O(1) because it can't reach the previous node; this is exactly the trade-off we covered in the linked lists post. Sentinel head and tail nodes remove every null check at the edges:

// src/utils/lru-cache.ts
interface LRUNode<K, V> {
  key: K;
  value: V;
  prev: LRUNode<K, V>;
  next: LRUNode<K, V>;
}

export class LRUCache<K, V> {
  private map = new Map<K, LRUNode<K, V>>();
  private head: LRUNode<K, V>; // sentinel: head.next is the most recent
  private tail: LRUNode<K, V>; // sentinel: tail.prev is the least recent

  constructor(private readonly capacity: number) {
    if (capacity < 1) throw new RangeError("capacity must be at least 1");
    this.head = {} as LRUNode<K, V>;
    this.tail = {} as LRUNode<K, V>;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  private unlink(node: LRUNode<K, V>): void {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  private linkAtHead(node: LRUNode<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.unlink(node);
    this.linkAtHead(node);
    return node.value;
  }

  set(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.unlink(existing);
      this.linkAtHead(existing);
      return;
    }
    if (this.map.size >= this.capacity) {
      const oldest = this.tail.prev;
      this.unlink(oldest);
      this.map.delete(oldest.key);
    }
    const node = { key, value } as LRUNode<K, V>;
    this.linkAtHead(node);
    this.map.set(key, node);
  }

  get size(): number {
    return this.map.size;
  }
}

Both operations are O(1), and the constant is small: one hash lookup and at most six pointer writes. This is the design running inside real infrastructure. The Linux page cache tracks recency with linked lists of pages. Memcached's LRU is segmented linked lists. It is also, not coincidentally, one of the most common systems interview questions ever asked.

The JavaScript Shortcut: Map Preserves Insertion Order

JavaScript hands you a large piece of this design for free. A Map iterates its entries in insertion order, and V8 implements delete-then-insert efficiently. So the Map itself can be the recency list: re-inserting a key moves it to the back, which makes the front the LRU position.

// src/utils/lru-cache-map.ts
export class LRUCacheMap<K, V> {
  private map = new Map<K, V>();

  constructor(private readonly capacity: number) {
    if (capacity < 1) throw new RangeError("capacity must be at least 1");
  }

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

  set(key: K, value: V): void {
    if (this.map.has(key)) {
      this.map.delete(key);
    } else if (this.map.size >= this.capacity) {
      // First key in iteration order is the least recently used.
      const oldest = this.map.keys().next().value as K;
      this.map.delete(oldest);
    }
    this.map.set(key, value);
  }

  get size(): number {
    return this.map.size;
  }
}

Same asymptotics as the pointer version, in about forty lines. For most application-level caching in Node or the browser, this is the one to write.

Two notes worth keeping in mind:

• Use has before get if undefined is a value you might store. map.get returns undefined for both "absent" and "present but undefined," and a cache that can't tell a miss from a hit will quietly hammer your backing store.
• The re-insertion trick relies on Map behavior the spec guarantees for ordering, but the O(1) cost of delete and re-insert is an engine property, not a spec promise. In practice V8, JavaScriptCore, and SpiderMonkey all deliver it. The linked-list version is the one to reach for when you need the guarantee in writing.

A Production-Shaped LRU with TTL

Real caches rarely ship with recency alone, because recency can keep a stale entry alive forever. A popular key that changed at the origin will happily serve its old value for as long as people keep asking for it. The usual fix is a TTL (time to live) checked lazily on read:

// src/utils/lru-cache-ttl.ts
interface TimedEntry<V> {
  value: V;
  expiresAt: number;
}

export class LRUCacheTTL<K, V> {
  private cache: LRUCacheMap<K, TimedEntry<V>>;

  constructor(capacity: number, private readonly ttlMs: number) {
    this.cache = new LRUCacheMap(capacity);
  }

  get(key: K, now = Date.now()): V | undefined {
    const entry = this.cache.get(key);
    if (!entry) return undefined;
    if (entry.expiresAt <= now) return undefined; // stale: treat as a miss
    return entry.value;
  }

  set(key: K, value: V, now = Date.now()): void {
    this.cache.set(key, { value, expiresAt: now + this.ttlMs });
  }
}

Lazy expiry keeps reads O(1): an expired entry is simply reported as a miss and gets overwritten on the next set, or evicted normally as it drifts toward the LRU position. Long-running processes with large caches usually add a periodic sweep as well, so memory is not held by entries nobody will ever ask for again.

Passing now as a parameter instead of calling Date.now() inside is a small habit with a large payoff: expiry logic becomes deterministic under test.

When LRU Is the Wrong Policy

LRU's bet on temporal locality loses to a few well-known workloads, and it loses badly enough that you should recognize them on sight.

• Sequential scans. A batch job that reads 200,000 rows once will march through an LRU cache and evict every hot key it was holding, replacing them with rows nobody will read twice. This is cache pollution, and it is why databases and operating systems use scan-resistant variants: segmented LRU, 2Q, or a small probationary segment new entries must survive before they can evict anything established.
• Frequency-skewed access. When a key is read constantly but on a period slightly longer than your cache's turnover, pure recency keeps evicting it just before it would hit. LFU (least frequently used) and hybrids like TinyLFU track frequency cheaply and dominate LRU on those traces.
• Anything at Redis scale. Exact LRU means bookkeeping on every read of every key. Redis instead samples a handful of keys and evicts the least recent among the sample: approximate LRU that captures most of the benefit at a fraction of the cost. That trade-off is worth stealing for very hot in-process caches too.

LRU is the right default. Whatever you pick, measure the hit rate before and after any cache change, including a size change. A cache without a hit-rate metric is a rumor.

Conclusion

An LRU cache pairs two simple structures so that each covers the other's weakness. The HashMap answers "where is this key" in O(1) but keeps no order; the doubly-linked list keeps perfect recency order but can't find anything. Wired together, every read and every eviction is a handful of pointer moves. That is why this exact composition sits inside operating systems, CDNs, and databases, and why JavaScript's insertion-ordered Map lets you collapse the whole design into forty lines when a written guarantee isn't required.

Key Takeaways

• The eviction policy is the main design decision in a cache, and hit rate is how you judge it.
• Naive LRU degrades to O(n) on the eviction path; the HashMap + doubly-linked-list composition makes both get and set O(1).
• JavaScript's Map preserves insertion order, so delete-and-re-insert gives you a compact LRU that is right for most application code.
• Add a TTL checked lazily on read, and inject the clock so expiry is testable.
• Know the failure modes: sequential scans pollute LRU, frequency-skewed traces favor LFU/TinyLFU, and at high scale approximate LRU by sampling is usually the better trade.