LRU is the default cache eviction policy for good reason: it's simple, cheap, and matches how most workloads actually behave. When the cache is full and a new item arrives, evict whichever item was accessed longest ago. The assumption is that recency predicts future access — if you touched something a millisecond ago, you'll probably touch it again soon; if you haven't touched it in an hour, you probably won't.

The classic implementation is a hash map plus a doubly-linked list. The hash map gives you O(1) key lookup. The linked list orders entries by recency: head is most recently used, tail is least. On every access, unlink the node and move it to the head. On eviction, drop the tail. Both operations are O(1) — no scanning, no sorting.

Concrete example: a database query result cache with capacity 1000. A user loads their dashboard, which fires 40 queries. Those 40 result sets land at the head. As other users hit the system, the 1000-entry list churns. If that first user reloads within a few seconds, their queries are almost certainly still cached — every access bumped them toward the head. If they come back an hour later, their queries have drifted to the tail and been evicted. That's the desired behavior.

Where LRU falls apart:

• Scans pollute the cache. A single query that reads a million rows will evict everything hot to make room for data you'll never see again. This is why databases like PostgreSQL use variants like Clock-Sweep instead.
• One-hit wonders get promoted equally. An item accessed once looks identical to an item accessed a hundred times — both sit at the head after their most recent touch. This is what W-TinyLFU and SLRU fix.
• Lock contention. Every read is a write to the linked list. Under high concurrency, that mutex becomes the bottleneck. Solutions: sharded LRU (N independent caches keyed by hash), or approximate LRU using CLOCK.

Rule of thumb for cache sizing: measure your working set at the 95th percentile of a typical hour. Size the cache to 1.5–2× that. Below 1×, hit rate collapses. Above 3×, you're paying for memory that only helps with cold starts. Track hit rate over time — if it drifts below 80% for a read-heavy workload, either the cache is undersized or your access pattern isn't recency-friendly (consider LFU-family policies).

Redis's allkeys-lru and volatile-lru policies are actually approximate LRU — they sample 5 random keys and evict the oldest of those. Close enough to true LRU for 99% of workloads, and it avoids maintaining the linked list at all.