8 Cache Eviction Strategies

__omp_shell("")

Cache eviction is a prediction problem: which item can we discard with the smallest chance of needing it again soon? No single policy wins everywhere because workloads differ. A social feed, a DNS resolver, and a database buffer cache see very different access patterns and freshness requirements.

LRU (Least Recently Used)

LRU evicts the item that has not been touched for the longest time. It works well when recent access predicts near future access, which is common for sessions, dashboards, and hot API keys. The hidden cost is bookkeeping because a strict LRU updates metadata on every read. It also performs badly during scans. A single large sequential read can push genuinely hot entries out of the cache.

MRU (Most Recently Used)

MRU does the opposite and evicts the most recently used entry first. That makes sense only for workloads that repeatedly scan data sets larger than the cache. In that case, the item you just touched may be the one least likely to be needed again soon. MRU is a niche tool because it punishes the more common case where recent access is valuable.

SLRU (Segmented LRU)

SLRU splits the cache into a probationary segment and a protected segment. New entries enter probation, and only entries that are accessed again get promoted to protected space. That extra step filters one hit wonders from data with real locality and helps against scan pollution. The tradeoff is tuning. If the protected segment is too large, new useful items struggle to survive. If it is too small, hot items churn before promotion helps.

LFU (Least Frequently Used)

LFU evicts the item with the lowest access count, which helps when long term popularity matters more than short term recency. Content metadata, reference tables, and product catalogues often fit this pattern. Pure LFU has two problems. Old favourites can stay resident long after demand fades, and keeping exact counters can be costly. Production systems usually add ageing or approximate counting so yesterday's hot key does not become tomorrow's squatter.

FIFO (First In First Out)

FIFO evicts the oldest resident entry, ignoring whether it was used a millisecond ago. Its advantage is simplicity. It is cheap to implement and easy to reason about, which can be enough in constrained systems where metadata overhead matters. The weakness is obvious: age is not the same as usefulness. FIFO will happily discard a hot object just because it arrived early.

TTL (Time-to-Live)

TTL is technically an expiry rule rather than an eviction algorithm, but many real caches rely on it heavily. Each entry gets a lifespan and becomes invalid after that time. TTL is excellent when freshness matters more than reuse, such as DNS records or configuration snapshots. The risk is stale data or premature churn. A TTL that is too short creates avoidable misses and can trigger stampedes when many clients refresh the same key together.

Two-Tiered Caching

Two tiered caching is a cache hierarchy rather than a single eviction policy. A small local cache sits close to the process, while a larger distributed cache sits behind it. This reduces network hops for the hottest keys and gives colder but still reusable keys another chance before the database. The complexity moves into coherence. Local caches can drift from shared state, and each tier may use a different policy.

RR (Random Replacement)

Random replacement chooses a victim at random. That simplicity is its strength. It has almost no metadata cost and avoids the lock contention of smarter policies. It can even behave reasonably under adversarial access patterns that defeat recency heuristics. The downside is variance. Random choice can evict a very hot key by bad luck, which makes tail behaviour less predictable.

In practice, policy selection should follow measured access patterns, not habit. Recency based policies reward locality, frequency based policies reward popularity, TTL rewards freshness, and multi tier designs trade coherence work for hit rate. The best cache is the one whose failure mode you understand.