LRU — Least Recently Used — Cache Eviction

Overview

What this concept solves

LRU — Least Recently Used — is the default eviction policy for almost every cache in production. The idea is one sentence: when you need to evict, drop the entry that was accessed the longest time ago. The bet is that recently-touched items are likely to be touched again soon, and stale items are not.

It's the policy in lru_cache (Python), Caffeine, Guava, Redis's allkeys-lru, the Linux dentry cache, and most browser HTTP caches. It's well-understood, it performs well across a huge range of workloads, and it can be implemented in true O(1) per operation.

Mechanics

How it works

Two data structures, working together

A naive LRU is O(N) — to find the least-recently-used entry you scan the whole cache. The classic trick is to combine two structures:

A hash map from key → node, so lookups are O(1).
A doubly-linked list of nodes in access order, so moving a node to the front and dropping the tail are both O(1).

The list is ordered most-recent at the head, least-recent at the tail. The algorithm is:

Get(key) — look up the node in the map. If found, move it to the head of the list and return its value. If not, return a miss.
Put(key, value) — if the key exists, update its value and move to head. Otherwise, insert a new node at the head. If the cache is now over capacity, remove the tail node and delete it from the map.

Recency is a proxy, not the truth

LRU works because recency is usually a decent predictor of future access. It fails when it isn't — e.g. a one-shot scan of a million keys will evict everything you care about, even though those keys will never be touched again. That's the scan-resistance problem that 2Q and LIRS exist to solve.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › LRU — Least Recently Used

About this simulation

Capacity 4. Letters A–F act as keys. Each click is an access — hits jump to the front (left = most recent); on a miss when full, the entry at the back (right = least recent) is the one that dies. Hit Run demo to watch A, B, C, D fill the cache, then A bump to the front, then E evict the now-oldest tail entry.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Run the demo, watch the tail die

Hit Run demo. A, B, C, D fill the row left-to-right. Then A is re-accessed and jumps to the front — pushing the back slot one step closer to eviction. When E finally arrives, look at which letter actually gets evicted: it's the one that wasn't refreshed.

try 02

Refresh by hand

Click Reset. Fill the cache yourself: A, B, C, D. Now click the rightmost letter — watch it teleport to the front, and a totally different letter is suddenly next in line for eviction. Recency, not insertion order, decides who dies.

try 03

Thrash a working set bigger than the cache

Click A, B, C, D, E, F in order, then repeat A, B, C, D, E, F again. The cache only holds 4. Every single access is a miss — the hit rate stat sits at 0%. This is LRU's failure mode when the working set doesn't fit.

In practice

When to use it — and what you give up

When to reach for it

Any cache where you don't have a strong reason to pick something else. It's the safe default.
Web/app caches — request patterns are bursty and recency-correlated, which is exactly LRU's sweet spot.
CPU page caches at the OS level — though most kernels actually use a Clock variant for cheaper bookkeeping.

Real-world example

Redis under maxmemory-policy allkeys-lru evicts the least-recently-used key when memory fills up. It uses an approximate LRU (sampling 5 random keys and evicting the oldest of them) to avoid the bookkeeping cost of a strict linked list — close enough in practice, much cheaper.

Pros

True O(1) for get and put with the HashMap + DLL implementation.
Great hit rate on most realistic workloads — bursty, recency-correlated traffic.
Trivial to understand and explain, which means it's the policy people actually maintain correctly.
Well-supported in every language's standard library.

Cons

Scan-vulnerable — one big sequential read can flush the whole cache.
Strict LRU bookkeeping (moving a node on every hit) is contended in multi-threaded code. Caffeine and the Linux kernel both use lock-free approximations.
Doesn't distinguish a key accessed once from a key accessed a thousand times. Frequency information is lost.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

lru.ts

// Classic O(1) LRU using a Map.
// In JS, Map preserves insertion order — we delete and re-set
// to push an entry to the "most recent" end. Two lines of code,
// no DLL needed.
class LRU<K, V> {
  private store = new Map<K, V>();
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    if (!this.store.has(key)) return undefined;
    const value = this.store.get(key)!;
    this.store.delete(key);
    this.store.set(key, value); // re-insert as most-recent
    return value;
  }

  set(key: K, value: V): void {
    if (this.store.has(key)) this.store.delete(key);
    this.store.set(key, value);
    if (this.store.size > this.capacity) {
      const oldest = this.store.keys().next().value!;
      this.store.delete(oldest);
    }
  }
}

References & further reading

4 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Which two data structures combine to give LRU O(1) get and put?

question 02 / 03

An LRU cache of size 3 starts empty. We access: A, B, C, A, D. Which key was evicted to make room for D?

question 03 / 03

Why is LRU considered scan-vulnerable?

0/3 answered