How it works
Start with a capacity limit. A cache may hold at most a fixed number of entries or, more realistically, a byte budget that includes keys, values, and metadata. Before admitting a new entry, remove enough existing entries to stay within that budget.
Exact LRU uses a hash map and a doubly linked list. The map finds an entry in expected O(1) time; the list tracks access order. A successful read or an update moves the entry to the most-recently-used end, and eviction removes from the least-recently-used end.
For a three-entry cache, insert A, B, and C: the order from least to most recent is A, B, C. Read A and the order becomes B, C, A. Inserting D evicts B, leaving C, A, D.
Eviction and expiration answer different questions. Eviction frees capacity; a time-to-live (TTL) determines when an entry must stop being served. An expired entry must be treated as a miss even if background cleanup has not reclaimed its memory, and ordinary LRU accesses do not inherently extend TTL.
Compare policies against the access pattern. LFU favors frequently accessed entries, ideally with aging so old popularity fades. FIFO evicts the oldest insertion without updating order on reads. Random eviction has little bookkeeping, while approximate LRU or CLOCK-style policies reduce the cost of tracking recency.
In a distributed cache, each shard usually enforces its own memory budget and eviction policy rather than maintaining one global LRU list. On a miss, fetch from the backing store and consider admission separately: a one-off result need not displace a useful cached entry.
A worked example
A redirect cache under a bulk scan
Suppose a URL shortener allocates 1 GiB to cached redirects. If each entry averages 512 bytes including metadata, it fits roughly 2.1 million entries before additional headroom. Its active working set is 500,000 short codes, so LRU initially seems reasonable. A batch client then requests 3 million distinct, previously uncached codes. Admitting every result can flush the active working set even though the batch never reuses those entries. Keep the memory limit, but consider bypassing cache admission for identified batch traffic or using a frequency-aware admission policy. Compare normal-traffic hit rate and database load before changing the policy.
Trade-offs to say out loud
- Recent access is only a prediction
- LRU works well with temporal locality, but a large scan of one-time keys can evict a frequently reused working set.
- Exact LRU makes reads update metadata
- Moving entries on every hit adds synchronization and memory-access overhead, so approximate tracking can outperform exact ordering under concurrency.
- LFU needs adaptation
- Frequency tracking can preserve popular entries through scans, but counters need aging or another mechanism to adapt when popularity changes.
- Entry count is not memory usage
- Variable-sized values require byte-based accounting, and admitting one large value may force multiple smaller entries out.
- Local eviction cannot fix shard imbalance
- One shard can evict heavily while another has spare memory, requiring better placement, capacity changes, or separate handling of hot keys.
- Eviction changes backend load
- Aggressive eviction increases misses and refill traffic, while write-back caches must persist dirty entries before discarding them.
When to reach for it
- You introduce a bounded cache for redirects, feed pages, objects, or computed results and need to explain what happens when it fills.
- The interviewer asks how to implement constant-time cache lookup and eviction.
- A workload has changing popularity, bulk scans, or many one-time reads that could make a simple LRU policy ineffective.
- Cache memory pressure is increasing miss rates, backend traffic, or tail latency.
- You are designing a distributed cache and must separate capacity eviction from TTL expiration and data durability.
How to bring it up in the interview
- State the access-pattern assumption: choose LRU because recently accessed entries are likely to be requested again, not because it is universally best.
- Describe the hash map plus doubly linked list briefly, then address the system-level follow-up: exact recency updates can contend across threads.
- Define the memory budget in bytes, including metadata and operating headroom; expect questions about oversized values and repeated evictions.
- Separate eviction, admission, expiration, and invalidation explicitly: they decide what leaves, what enters, what has expired, and what is no longer valid.
- Defend the policy with measurements: hit rate, bytes served from cache, eviction rate, refill cost, backend load, and tail latency; expect a follow-up about scans or a sudden popularity shift.
Common mistakes
- Saying LRU removes the least frequently used entry; that describes LFU, not LRU.
- Treating TTL as a complete capacity policy or assuming an unexpired entry cannot be evicted.
- Claiming O(1) operations make exact LRU free under concurrency, while ignoring list updates and lock contention.
- Sizing only by entry count despite widely varying value sizes and metadata overhead.
- Allowing correctness-critical state, such as authoritative rate-limit counters or unpersisted writes, to disappear under an ordinary cache eviction policy.
Where it comes up
Interview questions where lru and cache eviction is part of a strong answer, and why.
- Design a distributed cacheBounded memory, eviction policy, expiration checks, and per-shard pressure are explicit requirements of the cache itself.
- Design a URL shortener like BitlyThe redirect read path needs a bounded cache that retains useful mappings without letting one-time lookups drive excessive database traffic.
- Design a news feed like FacebookFeed caches need a retention policy for inactive users so limited memory remains useful for active readers without making feed reconstruction too expensive.
Questions people ask
What is an LRU cache, and how is it implemented?
An LRU cache evicts the entry that was accessed least recently when it needs room. A standard implementation combines a hash map with a doubly linked list for expected O(1) lookup, recency updates, and single-entry eviction. A byte-bounded insertion may still require several evictions.
What is the difference between LRU, LFU, and FIFO?
LRU tracks the most recent access, LFU tracks access frequency, and FIFO tracks insertion order. LRU adapts naturally to recent activity but is vulnerable to scans; LFU can protect popular entries but needs aging to adapt. FIFO avoids recency updates on reads but can evict an entry that is still heavily used.
What is the difference between cache eviction and TTL?
Eviction removes entries to enforce capacity, while TTL expiration prevents entries from being served after a deadline. An entry can be evicted before its TTL expires, and expired memory may remain allocated until cleanup. Neither mechanism by itself guarantees immediate freshness after the source data changes.