Why LRU Eviction Needs a Hash Map and a Linked List

Every cache with a size limit must answer one question on insertion: which existing entry to discard. Least-recently-used is the default answer because it matches a common access pattern — a working set plus a tail of one-shot reads — and because its behaviour is easy to explain. Implementing it exactly, however, requires maintaining a total order over every entry at all times, updated on every read. The data structure that makes that possible is the reason LRU caches carry a per-entry memory tax, and the reason approximations exist.

Two operations that must both be fast

A cache needs constant-time lookup by key and constant-time reordering by recency. A hash map alone gives the first and cannot give the second: finding the least recently used entry would require scanning all buckets, which is linear in the number of entries and would happen on every eviction.

The standard solution is a hash map from key to a node, where the node is simultaneously a member of a doubly linked list ordered by recency. Lookup is a hash probe. Recency update is a pointer splice. Eviction is removal of the list tail. All three are constant time, and the map’s value is a pointer rather than the payload, so the map does not duplicate the data.

The naive alternative, keeping a monotonically increasing timestamp on each entry and evicting the minimum, requires either a heap plus an index from entry to heap position, so that every touch can sift the entry in logarithmic time, or a scan. A sorted structure such as a balanced tree costs logarithmic per touch and allocates a node per entry anyway, so it is strictly worse than the list for the same asymptotic memory.

Ordering on hit without scanning

The invariant is that the list head is the most recently used entry and the tail is the least. A hit does not change the map at all; it detaches the node from its current position and reattaches it at the head.

struct entry {
    struct entry *prev, *next;   /* recency list links */
    struct entry *hnext;         /* hash bucket chain */
    uint64_t hash;
    size_t key_len, val_len;
    char data[];                 /* key bytes followed by value bytes */
};

static void touch(struct cache *c, struct entry *e) {
    /* Unlink from current position. */
    e->prev->next = e->next;
    e->next->prev = e->prev;
    /* Splice at head, between the sentinel and the first real node. */
    e->next = c->head.next;
    e->prev = &c->head;
    c->head.next->prev = e;
    c->head.next = e;
}

The splice is four stores and needs no locking of its own if the caller already holds the cache lock. That is cheap in instruction terms and expensive in memory terms: two pointers per entry, 16 bytes on a 64-bit build, on top of the map’s own bucket pointer and hash. A 100-byte value therefore costs on the order of 150 bytes resident. That ratio is why a cache measured in “number of entries” can exceed a memory budget it was supposed to respect.

Sentinel head and tail nodes remove the null checks from the splice. Without them the four pointer writes become a branch tree for the cases “first node”, “last node”, and “only node”. With them the list is never empty structurally and the update path is branch-free apart from the hit test.

Deletion, which has more cases than insertion

Removing an entry requires unlinking it from the recency list and from its hash bucket chain. The bucket chain is usually singly linked, which means removal needs the predecessor, so either the code keeps a back-pointer in each node or it walks the chain. A back-pointer costs another 8 bytes per entry; walking costs time proportional to the chain length, which is small if the load factor stays near one but degrades if the table is under-grown.

Expiry adds a third removal path. A key can leave the cache because it was evicted, because it was invalidated, or because its deadline passed and a reader noticed. All three must produce the same state change or the cache leaks nodes that are still in the list. A common bug is a lazy-expiry path that frees the value but leaves the node in the recency list, which converts the LRU order into a list of ghosts that are evicted repeatedly without freeing anything. The expiry semantics behind that path are set out in TTL expiry and the two ways an entry dies.

CLOCK: approximating recency with one bit

Exact LRU pays a pointer write per hit and 16 bytes per entry. CLOCK pays neither. Entries live in a circular buffer in insertion order, each with a single reference bit. A hit sets the bit; it does not move the entry. Eviction advances a hand around the ring: if the current entry’s bit is set, clear it and advance; if it is clear, evict and advance.

The cost is one bit per entry and one memory write per hit instead of four, with better locality because the hand walks the buffer sequentially. The policy is an approximation of “not recently used”: an entry survives one full pass of the hand for each time it was referenced, so a hot entry can survive several sweeps while a cold one is taken at the first opportunity. What CLOCK cannot do is distinguish an entry read once a second ago from one read a thousand times in the same period; both have a single set bit.

Clock-Pro and the second-chance variants used in operating system page reclaim add a second bit or a ghost list of recently evicted keys, which recovers some of the distinction at the cost of complexity. The design pressure is the same in a kernel page cache and in a userspace cache: the eviction hand runs on the allocation path, so its per-entry work must be bounded and predictable, which favours scans over pointer chases.

Frequency, scans, and the case against pure recency

Pure LRU has a well-known weakness: a sequential scan of data larger than the cache evicts everything useful, because every scanned key is by definition the most recently used. The same failure appears in application caches when a batch job walks a table. LRU-K addresses it by tracking the time of the K-th most recent reference rather than the most recent, so a key seen once ranks below a key seen several times regardless of ordering. That requires per-entry history, either K timestamps or a compact counter, and it makes the update path more expensive than a splice.

Frequency-based policies take the other side. LFU keeps a count per key and evicts the smallest, which resists scans but never forgets: a key that was hot yesterday outranks a key that is hot now. The usual repair is decay, either periodic halving of counters or windowed counting. TinyLFU, used by Caffeine, keeps a compact frequency sketch and admits a new key only if its estimated frequency exceeds that of the eviction candidate, which turns the admission decision into the main lever and lets the eviction policy be approximate. The sketch is a probabilistic counter array, so the per-key cost is a few bits rather than a full counter, and the error is bounded rather than zero.

Concurrency and the real cost of a hit

In a single-threaded cache the recency update is trivially correct. In a concurrent one it is the throughput bottleneck, because every read mutates shared ordering state. Options are coarse locking around the whole cache, per-bucket locking plus a lock-free list (hard to get right under removal), or buffering: record the hit in a lossy queue and let a single thread apply the reorderings in batches. The last is what many high-throughput JVM caches do, accepting that recency is approximate by a few milliseconds.

That approximation is not a defect. LRU is already an approximation of the workload’s future, and the difference between exact and batched ordering is far smaller than the difference between LRU and the actual optimal policy, which requires knowing the future. The engineering question is where the per-entry bytes and the per-hit writes are worth spending, and the answer depends on whether the cache is bounded by memory or by lock contention. A memory-bound in-process cache should count its overhead per entry, as in-process caches and retained heap sets out; a contention-bound shared cache should measure whether the recency update is on the hot path at all.