LRU Cache (Doubly Linked List + Hash Map)

A bounded in-memory cache that, when full, throws away the entry that was used least recently. Every operation is O(1).

The problem and where it shows up

Memory is finite, and access patterns are usually skewed: a small hot set gets most of the reads. An eviction policy decides what to drop when the cache is full. Least-recently-used is the usual default because recency is a cheap, decent predictor of reuse. You find it in:

• Application caches in the process: Guava/Caffeine (Java), lru-cache (npm), functools.lru_cache (Python).
• Database buffer pools: InnoDB's buffer pool is an LRU list split into young and old sublists. PostgreSQL uses clock-sweep, which approximates LRU.
• Block caches: RocksDB's LRUCache (sharded, size-aware, with a high-priority pool for index/filter blocks).
• CDN and reverse-proxy caches: Nginx proxy_cache evicts by LRU once max_size is hit, and Varnish uses LRU for its malloc/file storage.
• OS page cache: Linux keeps active and inactive LRU lists (two-list approximation).

Design

map: key -> node                 (O(1) lookup)

head <-> [MRU] <-> ... <-> [LRU] <-> tail     (O(1) reorder / evict)
 ^ sentinel                         sentinel ^

• get(k): look up the node in the Map and splice it to the front.
• set(k, v): insert at the front (or update in place and move to front), then pop from the back until the bounds hold.
• Sentinel head and tail nodes mean _unlink and _pushFront never need null checks.
• The Map holds node references, so removing an arbitrary node (for delete or expiry) is O(1). A singly linked list can't do this.

Invariants (checked by _checkInvariants() and the tests)

1. Every list node is in the Map under its own key, and every Map entry is in the list.
2. node.next.prev === node for every node.
3. size <= maxEntries and calculatedSize <= maxSize after every public call returns.
4. List order is exactly recency order: the result of get / set. peek, has and keys do not change it.

Features

Expiry is lazy: an expired entry is removed when you touch it. There's also an explicit prune() sweep, the same split as Redis's passive and active expiry. When capacity eviction reaches an expired tail node, it reports it as expired, not capacity.

Oversized items (size > maxSize) are rejected (set returns false). Accepting one would flush the entire cache and still not fit it. Any older value under the same key is removed, so readers never see data the writer meant to replace.

Complexity

The per-entry overhead is roughly 100+ bytes in V8, which matters when values are small. Production caches often store entries in flat arrays indexed by integer slots to avoid per-node objects (lru-cache v7+ does this).

Failure modes and trade-offs

• Scan pollution: a one-off sequential scan (a batch job or a crawler) pushes the whole hot set out. LRU has no notion of frequency. Fixes: segmented LRU / midpoint insertion (InnoDB inserts new pages at the 3/8 point), 2Q, ARC, or W-TinyLFU (Caffeine), which admits a new item only if it's estimated to be more popular than the victim.
• Lock contention: every get writes (it reorders the list). A multithreaded LRU needs a lock on reads. Caffeine buffers reorders in ring buffers and replays them in batches. RocksDB and memcached shard the cache so each shard has its own lock.
• Stale reads with TTL-only invalidation: TTL bounds staleness but doesn't remove it. Pair with explicit invalidation on writes if correctness matters.
• Thundering herd on miss: when a hot key expires, many callers miss together and all hit the database. Use single-flight (request coalescing) or refresh-ahead. Not implemented here.
• Size estimation lies: sizeOf is only as accurate as you make it. JS object size is hard to measure, so a byte bound on objects is approximate.
• Callback reentrancy: onEvict runs synchronously after internal state is consistent, and exceptions it throws are swallowed. Calling back into the cache from it works, but it can cascade.

How production systems do it

• Redis (maxmemory-policy allkeys-lru / volatile-lru) keeps no linked list. Each object stores a 24-bit LRU clock. On eviction Redis samples maxmemory-samples keys (default 5) and evicts the oldest of the sample, using an eviction pool that carries candidates between rounds. It's approximate LRU with zero per-access list maintenance. allkeys-lfu uses a probabilistic log counter instead.
• Memcached uses a per-slab-class LRU. The modern "segmented LRU" splits it into HOT, WARM and COLD sublists maintained by a background thread, and items are bumped at most once every 60 s to limit lock traffic.
• Caffeine (Java) uses W-TinyLFU: a small admission window LRU, a Count-Min-style frequency sketch, and a segmented main LRU (probation and protected). Its hit rates are close to optimal on most traces.
• RocksDB block cache uses a sharded LRU (num_shard_bits) with a charge per block, plus a newer HyperClockCache that avoids a global list mutex entirely.
• Linux page cache uses active/inactive two-list LRU approximation, and more recently MGLRU (multi-generational LRU).

Extension exercises

1. Sampled LRU à la Redis: drop the list. Store lastAccess per entry and, on eviction, sample 5 random keys and evict the oldest. Measure the hit-rate loss against exact LRU on the demo's workload.
2. Scan resistance: implement midpoint insertion (new entries go into an "old" sublist and are promoted only on a second hit). Show that a 10k-key scan no longer destroys the hot set.
3. TinyLFU admission: add a 4-bit Count-Min sketch and admit a new key only if its estimated frequency is higher than the LRU victim's.
4. Single-flight loader: add async fetch(key, loader) so concurrent misses for the same key share one loader promise, with negative caching for errors.
5. Sharded cache: hash keys into N independent LRUCaches and discuss how that changes global LRU ordering, and why real systems accept that.