Cache Eviction Policies

Cache eviction policies decide which entries to remove when a cache needs room. Their effectiveness depends on access patterns, miss costs, and the overhead of tracking usage.

A cache has finite storage. When an insertion would exceed its capacity, an eviction policy chooses one or more entries to remove so the new data can be stored. The policy affects hit rate, latency, and the amount of bookkeeping the cache must perform.

LRU (least recently used) evicts the entry whose most recent access was furthest in the past. It works well when recently accessed data is likely to be requested again. LFU (least frequently used) evicts an entry with a low access count; implementations need to decide how to handle ties and whether old counts should decay.

FIFO (first in, first out) evicts the entry that has been in the cache longest, regardless of whether it was accessed recently. Random replacement chooses an entry at random and can be simpler to implement, though its hit rate may be less predictable. Some systems use policies such as segmented LRU or adaptive schemes to balance competing patterns.

No policy is best for every workload. For example, a scan that touches many one-off keys can displace useful entries under LRU. Choose based on observed access patterns, the cost of misses, and operational constraints; measure hit rate and resource use under representative traffic. In distributed caches, expiration time and eviction are separate mechanisms: expiration removes data because it is too old, while eviction frees space.

Key points

• Eviction frees capacity by selecting entries to remove when storage is full or constrained.
• LRU uses access recency; LFU uses access frequency; FIFO uses insertion order.
• Policy trade-offs depend on workload, miss cost, and tracking overhead.
• Expiration is time-based and distinct from capacity-driven eviction.
• Test candidate policies against representative traffic and monitor hit rate and resource usage.

Interview questions

How is eviction different from expiration?

Eviction is triggered by a need to reclaim capacity, whereas expiration removes an entry after a deadline or age condition. An entry may expire even when the cache has plenty of space, and a non-expired entry may be evicted under pressure. Some systems combine both mechanisms.

What is a cache eviction policy, and why does a cache need one?

Eviction chooses entries to remove when a cache needs room for additional data. A fixed-capacity cache cannot retain every value indefinitely, so it needs a replacement rule. The policy influences cache hit rate and the work required to track usage.

Compare LRU and LFU, including a weakness of each.

LRU removes the least recently accessed entry, while LFU removes an entry with the lowest recorded access count. LRU can react promptly when the workload changes, but LFU can preserve items that were popular earlier. LFU also needs a tie-break rule and may benefit from aging or decay so old popularity does not dominate forever.

Why can an LRU cache perform poorly during a large sequential scan?

A scan over many unique keys can push reusable entries out of an LRU cache because every scanned key becomes the most recently used. This is called scan pollution. Depending on the workload, a scan-resistant policy, admission filter, or separate cache region can limit the damage. Validate the choice using a representative trace rather than assuming a policy is universally superior.