Expiration and eviction solve different problems#
Expiration makes an entry unusable because its time or freshness policy ended. Eviction removes an entry because the cache needs capacity. A non-expired entry can still be evicted under memory pressure.
Small LRU example#
A four-item request against a three-item cache
Cache: [A] [B] [C]
Access: A
Insert: D
Possible LRU result: [A] [C] [D]
B was used least recently.| Policy | Signal | Strength | Failure mode |
|---|---|---|---|
| LRU | Recency | Adapts to a changing working set | A one-time burst can displace useful entries |
| LFU | Frequency | Protects a stable popular set | Historical popularity may outlive current demand |
| Random | None | Simple and low bookkeeping | May remove a valuable hot entry |
No policy always produces the best hit rate. Real implementations may approximate these policies; the interview-level decision is to connect the policy to access distribution, memory limits, and the cost of a miss.
- Calling TTL expiration “LRU eviction.”
- Assuming LRU is universally optimal.
- Ignoring object size, admission policy, and origin cost.
Use these prompts to extend the design. The useful answer is a reasoned change, not a memorized sentence.
- What happens when the working set exceeds memory?
- Would recency or frequency better match this workload?
- Which eviction metrics would trigger a capacity change?
Related practice problems
Use the manifest-backed prompts below to apply this lesson in a complete design.
- Caching challenges and strategiesAmazon Builders' Library
- Key evictionRedis Documentation
Reach this point to mark the lesson as read.