LRU eviction
Least-Recently-Used: when the cache is full, evict the entry not used for the longest time. A simple, effective eviction policy assuming recently-used items will be used again. Implemented with a doubly-linked list + hash map for O(1).
- General-purpose caches with locality of reference.
- Default choice before measuring a need for LFU.
- Scan-heavy workloads (use LFU/tinyLFU).
- When you need strict size by bytes, not count.
Definition
LRU tracks access order; on capacity pressure it removes the least-recently-accessed item. Variants include LRU-K (recent K accesses), 2Q (separate queues for new vs hot), and ARC (adaptive between LRU and LFU).
Why it exists
Caches have finite memory. A good eviction policy keeps hot data and discards cold data; LRU is simple and works well for most access patterns exhibiting locality.
How it works
A hash map points to nodes in a doubly-linked list ordered by recency. On access, move the node to the head. On insert when full, remove the tail. O(1) per operation. Approximated LRU (sampled) is used in Redis to avoid contention.
Scaling limits
LRU struggles with scans (one-time access of many keys evicts hot data) — LFU or tinyLFU handle that better. Exact LRU under high concurrency needs careful locking; sampled approximations trade accuracy for throughput.
Cost shape
Memory overhead per entry for the list. Negligible compute. Blow-ups: scan workloads evicting the working set.
Alternatives
- LFU — Keeps frequently-used items, better for scans, slower to adapt.
- FIFO — Simplest, but ignores access patterns.
Failure modes
- Scan poisoning evicting the hot set.
- Approximation drift under concurrency.