LRU cache architecture — linked list, hash map, admission, concurrency

Why architecture matters here

LRU fails on specific workloads. Sequential scans evict hot data. Zipfian workloads benefit more from LFU or W-TinyLFU. Naive locking makes the cache slower than not caching. Weightless capacity handles fixed-size entries but not variable ones.

The architecture matters because tuning + variant choice depend on your access pattern. Concurrency depends on your hit rate and thread count.

With the pieces mapped, you can build a cache that actually helps.

The architecture: every piece explained

The top strip is the core algorithm. Key lookup probes a hash map for O(1) find. Linked list maintains recency; on access, move the node to the head. Head / tail are the MRU and LRU endpoints. Eviction on full drops the tail.

The middle row is production concerns. Admission policy (TinyLFU) decides whether new candidates deserve to displace existing entries. Concurrency uses sharding by hash or lock-free structures. TTL + expiry handles time-based eviction alongside LRU. Weighted entries accommodate variable-sized items with size-aware capacity.

The lower rows are ops. Metrics track hit rate, eviction rate, and size. Variants — LFU, ARC, W-TinyLFU — handle different access patterns. Ops covers cache sizing, shard fan-out, and persistence.

End-to-end flow

End-to-end: an app cache uses W-TinyLFU with sharded concurrency. Request arrives; hash key + shard select; hash map probe; hit → return + move to MRU. Miss → fetch from DB; admission policy compares to a TinyLFU sketch to decide keeping; if kept, insert at head; if cache full, drop tail; if candidate loses, don't insert. Metrics show hit rate 82%, eviction rate steady. Under sequential scan, admission policy protects hot entries from being displaced.

The two structures, and why neither works alone

An LRU cache has to answer two questions in constant time, and they pull in opposite directions. Where is key k? is a lookup question, answered by a hash table. Which entry is least recently used? is an ordering question, answered by a sequence. A hash table alone has no notion of order: finding the coldest entry means scanning every bucket, which is O(n) per eviction. A list alone has order but no index: finding key k means walking from the head, which is O(n) per read. Neither structure is deficient; they are simply answering different questions, and a cache needs both answers on every operation.

The standard construction runs them over the same nodes. Each cache entry is a node holding the key, the value, and two pointers, prev and next. The nodes are threaded into a doubly-linked list ordered by recency, most recent at the head. The hash map does not store values; it maps key to node pointer. That single detail is what makes the whole thing O(1): a lookup lands you not on the value but on the exact list position of the value, so the reordering that follows needs no search.

This is an intrusive list, meaning the link pointers live inside the entry rather than in separate list cells that point at entries. The alternative - a general-purpose list of references to entries - costs an extra allocation and an extra pointer dereference per node, and it makes the reverse mapping from entry back to list position another thing to maintain. Intrusive linkage means the node is the entry, and every structure that touches the entry already has the handle it needs.

Why doubly linked, and why sentinels

The list must be doubly linked because the defining operation is unlink an arbitrary interior node. Removing a node from a singly-linked list requires the predecessor, and the only way to find the predecessor is to walk from the head - O(n), which destroys the whole point. With a prev pointer the unlink is two stores: node.prev.next = node.next and node.next.prev = node.prev. Splicing at the head is four more. Six pointer stores, no traversal, no allocation.

Sentinel nodes - a permanent dummy head and dummy tail that never hold data - remove every null check from those six stores. Without them, unlinking the first or last node is a special case, and the special cases are where the off-by-one bugs live. With them, every real node always has a non-null prev and next, so one code path handles all positions. The cost is two nodes of memory for the life of the cache.

The eviction node must also carry its own key. When you unlink the tail you have a node, but the hash map is keyed by key, and you need to delete the map entry too. If the node only carried a value you would have no way to find its map slot without a reverse index. Storing the key in the node is what closes the loop, and it is the reason entry objects in real caches are noticeably fatter than the value they hold: key, value, prev, next, plus whatever the policy needs - a weight, an access timestamp, a reference bit, a frequency counter.

def get(self, key):
    node = self.index.get(key)          # O(1) hash probe
    if node is None:
        return MISS
    self._unlink(node)                  # 2 pointer stores
    self._push_front(node)              # 4 pointer stores
    return node.value

def put(self, key, value, weight=1):
    node = self.index.get(key)
    if node is not None:
        self.total -= node.weight
        node.value, node.weight = value, weight
        self.total += weight
        self._unlink(node); self._push_front(node)
    else:
        node = Node(key, value, weight)
        self.index[key] = node
        self._push_front(node)
        self.total += weight
    while self.total > self.capacity and self.head.next is not self.tail:
        victim = self.tail.prev         # the LRU end
        self._unlink(victim)
        del self.index[victim.key]      # needs victim.key
        self.total -= victim.weight

Note that the eviction step is a loop, not a single pop. With uniform entries one insert evicts at most one victim, so the loop runs once and people write it as an if. The moment entries are weighted by byte size - which any cache holding serialized payloads must do - a single large insert can require evicting many small entries, and an if silently lets the cache exceed its budget. Weighted caches also need an admission check for the pathological case where one entry exceeds the entire capacity; without it the loop empties the cache and then still cannot fit the entry.

Every read is a write, and that is the real cost

The consequence practitioners underestimate is that a strict LRU has no read path. A cache hit does not merely read: it unlinks a node and splices it at the head, mutating up to six pointers across three or four distinct cache lines. At a 95% hit ratio, 100% of operations are still structural writes to a shared data structure. Read-mostly at the API surface, write-only underneath.

That inverts every optimization you would normally reach for. A read-write lock is useless because there are no readers. Copy-on-write is useless because the mutation rate equals the request rate. And the head sentinel is a single memory location that every thread on every hit must store to, so the cache line holding it ping-pongs between cores under the coherence protocol. On a multi-socket box the line crosses the interconnect. Once the list mutation is under a single mutex, the cache serializes the entire application at a point that was supposed to make it faster - which is how you end up with a cache that measurably lowers throughput while showing a perfectly healthy hit ratio.

The arithmetic is Amdahl's, and it is unforgiving. If the critical section is 100ns and every request enters it, the cache's ceiling is ten million operations per second across all cores combined, no matter how many cores you add. Worse, contention is not neutral: as threads pile up, lock handoff, park/unpark, and cache-line transfers make the critical section itself longer, so throughput does not plateau, it declines. Every serious cache implementation is fundamentally a set of answers to this one problem.

Mitigation 1: lock striping and sharding

The cheapest fix is to stop having one cache. Split into N independent caches, each with capacity C/N, and route by hash(key) % N. Each shard has its own lock, its own list, its own map, so N threads hitting different shards proceed in parallel and the contended head sentinel becomes N separate sentinels on separate cache lines. Throughput scales roughly linearly in N until you hit memory bandwidth. It is a handful of lines of code and it is why almost every production cache is sharded.

The cost is paid in hit ratio, and it is a real cost. Recency is now only tracked within a shard, so the entry evicted is the least-recently-used of its shard, not of the cache. If the key distribution is skewed - and cache workloads are skewed by definition, otherwise you would not be caching - a shard that happens to own several hot keys evicts useful entries while a cold shard sits half empty. Capacity cannot flow between shards. The effect grows with N: 4 shards on a large cache is usually invisible, 256 shards on a small one is not, and the worst case is a single dominant key whose shard is permanently thrashing while the other 255 are idle. Sharding trades a policy property for a concurrency property, and you should measure the hit ratio before and after rather than assuming it is free.

Mitigation 2: CLOCK and second-chance approximation

The deeper fix is to stop maintaining exact recency order at all. CLOCK keeps entries in a fixed circular array with a single reference bit per entry and a hand that points at the next eviction candidate. A hit sets the reference bit to 1. That is the entire read path: one byte store, to a location the reading thread is already touching, with no lock, no ordering requirement, and no harm if two threads do it at once because the store is idempotent. The read path has become genuinely read-mostly.

The work moves to eviction. When space is needed the hand advances: if the entry under it has its bit set, the bit is cleared and the hand moves on - the entry gets a second chance; if the bit is clear, that entry is evicted and the hand stops. Only the hand pointer is contended, and only on misses, which by construction are the rare case. CLOCK does not reproduce LRU exactly: it cannot distinguish an entry touched once at the start of a sweep from one touched a thousand times just now, so within a sweep it is order-insensitive. In practice the hit-ratio gap against true LRU is small on typical workloads, and it is the standard choice inside operating-system page replacement, PostgreSQL's buffer manager, and many embedded caches. Refinements exist - a small counter instead of a single bit gives graduated second chances, and CLOCK-Pro adds a reuse-distance signal to recover scan resistance - but the core trade is the one that matters: exactness surrendered to make the common path contention-free.

Mitigation 3: record the read, apply it later

The third approach keeps the exact list but stops touching it synchronously. On a hit, the thread appends a record of the access to a per-thread or striped ring buffer and returns immediately; the list is untouched. Some single thread later acquires the lock with tryLock, drains the buffers, and replays the accesses against the list in order. If no thread acquires the lock, nothing blocks - the work simply accumulates.

Two properties make this work. First, the buffers are lossy: when a ring buffer is full the new record is dropped rather than the writer blocking. Losing an access record perturbs the recency order slightly and costs a sliver of hit ratio; blocking a request thread costs latency, and latency is the thing the cache exists to protect. Under contention the structure gracefully degrades in accuracy instead of in throughput. Second, replay is amortized: draining a hundred buffered accesses under one lock acquisition costs far less than a hundred separate acquisitions, and the replay can coalesce - several accesses to the same key collapse into one move.

This is the design used by Caffeine on the JVM, and it is what lets a cache with a genuinely policy-accurate eviction order still scale across cores. It also generalizes: writes go through their own buffer, and expiry and eviction ride the same drain cycle, so all structural maintenance happens in one batched pass rather than on the request path. The mental model to carry away is that the policy state is eventually consistent with the access stream, and that this is a deliberate and correct choice.

Scan resistance: the arithmetic of the collapse

LRU's failure under a sequential scan follows directly from what it stores. The only evidence LRU keeps about an entry is its position, which encodes when it was last touched and nothing about how often. A one-time read and the thousandth read of the hottest key in the system produce exactly the same effect: both entries move to the head. LRU cannot represent the difference, so it cannot act on it.

Now run a table scan touching D distinct keys, none of them reused, against a cache of capacity C. Every scan access is a miss, so the scan's own hit ratio is zero - that part is unavoidable and fine. The damage is that each miss inserts and therefore evicts, so after C scan accesses the cache contains nothing but scan data and the entire prior working set is gone. If D is much larger than C, the scan spends the rest of its run evicting its own useless entries. The bill arrives afterward: the interactive workload that was running at a 95% hit ratio now runs at 0% and must re-fault its whole working set, one miss at a time, so recovery takes at least W misses where W is the working-set size, each paying full miss cost. A ninety-second scan can hand you a five-minute latency incident, and the cache's own hit-ratio graph will show the collapse only after the damage is done.

What makes this worse than it sounds is that the scan looks like a legitimate access pattern from inside the cache. There is no signal to detect it with, because the signal you would need - reuse - is precisely what LRU discards. Every scan-resistant policy is, at bottom, a way of storing one more bit of history than plain LRU does. The concrete instantiations are covered elsewhere on this site: database buffer pools ship midpoint insertion and ring buffers for exactly this reason, and the HBase block cache uses a priority tier so that a bulk scan cannot displace hot blocks.

SLRU: two segments, promotion on reuse

Segmented LRU is the smallest change that fixes the scan problem. Split the cache into a probationary segment and a protected segment, each maintained as its own LRU list. New entries always enter probation. An entry is promoted to protected only when it is hit again while in probation - that second reference is the evidence of reuse that plain LRU refuses to record. Eviction always takes the LRU end of probation, so an entry that was never reused dies without ever having threatened anything valuable.

Scan resistance falls out for free: scan entries enter probation, are never referenced a second time, and are evicted by the next scan entries. The scan churns through probation and the protected segment never notices. One bit of history - seen once versus seen twice - buys the entire property.

The protected segment is bounded, and when it is full a promotion demotes the protected LRU entry back to probation rather than evicting it, giving it another chance to prove itself. Sizing that boundary is the one real knob. A protected segment sized too small cannot hold the working set and promoted entries get demoted before they are used again, so you have paid for the machinery and still behave like LRU. Sized too large - approaching the whole cache - probation becomes too short for a genuinely warm entry to earn its second hit before being evicted, and the cache develops the opposite pathology: it becomes sticky, holding entries that were hot an hour ago against new arrivals that are hot now. Common splits put 20% in probation and 80% in protected. HBase's single-access, multi-access, and in-memory tiers are the same idea with a third, operator-pinned segment; see the HBase block cache writeup for how that plays out in practice.

LRU-K: how long ago was the K-th reference

LRU-K generalizes the "count the references" idea. Instead of one timestamp per entry it keeps the times of the last K references, and evicts the entry whose K-th most recent reference is oldest. Plain LRU is LRU-1. The interesting case is K=2, and the reason is that the second-to-last reference is what distinguishes a one-hit wonder from a genuinely warm entry: a scan entry has no second reference at all, so its K-th backward distance is effectively infinite and it is evicted first, regardless of how recently the scan touched it.

The subtlety that makes LRU-K work on real traces is the correlated reference period. Real access streams contain bursts - a page read three times in a row while a query processes it - and those three references say almost nothing about whether the page will be wanted again in ten minutes. If you count them as three independent references, a burst masquerades as a warm entry. LRU-K therefore collapses references that fall within a short correlation window into one, and only counts references separated by more than that window. This is why the policy needs a time parameter as well as K, and why getting the window wrong makes it behave either like LRU (window too long, everything collapses to one reference) or noisily (window too short, bursts inflate the counts).

The cost is metadata. K timestamps per entry, plus a history for keys that are not currently resident - because an entry evicted after one reference has to be remembered, or its second reference will look like a first one all over again. That out-of-cache history is real memory and real bookkeeping, and it is why K=2 is where nearly everyone stops: K=2 captures most of the achievable benefit, and K=3 roughly triples the metadata to move the hit ratio by a fraction of a point. If you want an adaptive answer to the same problem that tunes its own recency/frequency balance from evicted-key feedback rather than from a fixed K, see ARC.

TinyLFU admission: should this miss be allowed in at all

Every policy so far decides what to evict. TinyLFU adds an orthogonal question: given a miss, does the new entry deserve to displace the entry we were about to evict? A miss is not automatically an argument for admission. If the incoming key is rare and the victim is popular, admitting it makes the cache worse, and plain LRU does it anyway on every single miss.

The decision needs an estimate of how often each key has been seen, which is what a frequency sketch provides - a small approximate counter table sized to the request stream rather than the key space. At the eviction boundary the cache compares the estimated frequency of the candidate against that of the victim; if the candidate is not more frequent, it is rejected and the victim stays. The sketch's internals - the counter width, the collision behaviour, and the periodic halving that keeps it responsive to workload shift - are covered in depth in count-min sketch; the piece that belongs here is that the comparison happens only at eviction time, so its cost is paid on misses, not on hits.

Two refinements matter operationally. A doorkeeper - a small bloom filter in front of the sketch - absorbs first-time keys so the long tail of singletons does not consume sketch capacity, which is significant when most of the key space is seen exactly once. And a strict comparison is exploitable: an adversary or an unlucky hash collision can pin a hot key's estimate below a rival's forever, so implementations admit a losing candidate with a small random probability, which bounds the damage without meaningfully softening the policy.

W-TinyLFU assembles the pieces from the previous sections. Roughly 1% of the cache is a plain LRU window where every new entry lands unconditionally; the remaining 99% is an SLRU main region. Admission control runs only when an entry is evicted from the window and tries to enter main. The window is what saves W-TinyLFU from LFU's classic weakness - a genuinely new hot key has nowhere to build up frequency if it is rejected on arrival - and the SLRU main region supplies the scan resistance. This is the default in Caffeine, and it is why the same cache holds up under both a Zipfian point-lookup workload and a periodic bulk scan.

Redis: approximate LRU with no list at all

Redis takes the most aggressive position available: it maintains no recency list whatsoever. A global list would mean every GET mutating a shared structure and every key carrying two extra pointers - 16 bytes per key that, for a store holding hundreds of millions of small keys, is a serious fraction of the memory the cache exists to use. Instead each object carries a small clock field recording roughly when it was last accessed, updated in place on every access with a single store and no linkage at all.

Eviction then becomes sampling. When memory is over the limit, Redis picks a handful of random keys, looks at their idle times, and evicts the oldest of the sample. maxmemory-samples controls the handful; the default of 5 is a deliberate CPU/accuracy trade, and raising it to 10 moves the result close enough to true LRU that the difference is hard to see on a hit-ratio plot, at measurably more CPU per eviction. Since Redis 3.0 the sample is not thrown away: good candidates are retained in a small eviction pool across rounds and merged with each new sample, so the pool converges on genuinely idle keys instead of restarting the search each time.

The policy family is orthogonal to the mechanism. allkeys-lru samples the whole keyspace; volatile-lru samples only keys carrying a TTL, which is the right choice when the instance mixes cache data with data that must not disappear - and note that volatile-* with no expiring keys behaves like noeviction and will start returning write errors, a failure mode that surprises people. The LFU variants reuse the same field to hold a logarithmic access counter with a time-based decay, giving frequency-aware eviction under the same sample-and-compare mechanism. The general lesson generalizes past Redis: when per-key metadata is the dominant cost, sampled approximation buys most of LRU's benefit for none of LRU's structural overhead.

Sizing: read the curve, not the number

Hit ratio as a function of cache size is a concave curve, not a line, and the interesting question is never "what is my hit ratio" but "what would it be at 2x and at 0.5x". The curve typically rises steeply while the cache is smaller than the hot working set, then bends sharply and flattens once the hot set fits. Below the knee, capacity is the binding constraint and buying memory is the highest-leverage change available. Above it, you are paying for a long tail of rarely-reused keys and doubling the cache might buy a point of hit ratio - at which point policy improvements and admission control are worth more than memory.

You can measure the whole curve without running experiments at each size. LRU has the inclusion property: a cache of size C+1 always holds a superset of what size C would hold. That makes LRU a stack algorithm, and it means a single pass over an access trace computing each access's reuse distance - how many distinct keys were touched since this key was last touched - yields the hit ratio for every cache size at once, since an access hits at size C exactly when its reuse distance is less than C. Full reuse-distance computation is expensive on long traces, so production tooling samples the key space by hash and scales the result, which gets the curve's shape to within a percent or two for a small fraction of the cost. A useful side effect of the inclusion property is that LRU cannot exhibit Belady's anomaly - more cache is never worse - which is not true of FIFO.

Measuring honestly: hit ratio is the wrong single number

Hit ratio is the metric everyone reports and it is misleading whenever miss cost is not uniform. What the system actually pays is expected cost per request: the sum over key classes of miss rate times miss cost. A cache at 90% whose misses all hit a 5ms cross-region query is delivering far worse latency than one at 80% whose misses hit a 200 microsecond local read, and a hit-ratio dashboard scores it higher. If your misses have materially different costs - some served from a replica, some from cold object storage, some requiring a recomputation - then the policy should be cost-aware. GreedyDual-Size and its frequency-weighted variant do exactly this, ranking eviction candidates by retrieval cost divided by size so that expensive-to-refill and small entries survive longer, which is standard practice in CDN and web-proxy caches.

Three more measurement traps are worth naming. Aggregation hides everything: a global 92% can be one dominant key at 99.9% and everything else at 40%, so break the ratio down by key class or tenant before drawing conclusions. Window matters: a ratio computed since process start is dominated by ancient history and will not move when your cache falls over, so measure over a rolling window short enough to see an incident. And tail latency is the real customer-facing number: adding a cache almost always improves the mean while leaving p99 governed by the miss path, so a change that raises the hit ratio and does nothing to p99 has not improved what users experience. Track hit ratio, eviction rate, and the latency distribution of hits and misses separately; the three together tell you whether the cache is undersized, mis-policied, or fine.