Cache Eviction Policies

Cache eviction policies determine which cached entries are removed when a cache reaches its capacity or another configured limit. Common policies include LRU, LFU, FIFO, and TTL-based expiration, each making different assumptions about which entries are least valuable to retain.

A cache has finite memory, so inserting a new entry may require removing an existing one. An eviction policy defines how the cache chooses that entry. The policy is separate from the cache's lookup and storage operations.

LRU (Least Recently Used) evicts the entry that has gone unused for the longest time. It works well when recently accessed data is more likely to be accessed again. LFU (Least Frequently Used) instead considers access frequency, which can preserve repeatedly accessed entries even when they have not been used recently.

FIFO (First In, First Out) removes entries in insertion order, regardless of access behavior. TTL (Time To Live) removes entries after a configured lifetime; a TTL can be combined with another capacity policy rather than serving as the only eviction mechanism.

In distributed caching, eviction behavior is usually implemented by the cache system rather than by application code. Java applications commonly interact with caches through libraries or remote cache services, so the exact policy names, configuration options, and runtime behavior depend on the chosen implementation.

Key points

• LRU removes the least recently accessed entry.
• LFU removes entries based on access frequency.
• FIFO evicts entries according to insertion order.
• TTL expires entries after a configured lifetime and can coexist with capacity eviction.
• Eviction policies matter when finite cache capacity forces entries to be removed.

Interview questions

How does LRU work?

LRU tracks when entries are accessed and gives the lowest retention priority to the entry that has been unused for the longest period. When space is needed, that least-recently-used entry is evicted. A typical implementation needs an efficient way to update access order and identify the oldest entry.

What is the difference between LRU and LFU?

LRU ranks entries by how recently they were accessed, while LFU ranks them by how often they have been accessed. LRU responds quickly when the workload changes because a newly popular item becomes recent. LFU can retain items with consistently high demand even if they have not been accessed very recently.

Why can a cache need both TTL and an eviction policy?

TTL controls how long an entry is considered valid, while a capacity policy controls what happens when the cache needs space. An entry can therefore be removed because it has expired or because another entry must be displaced to satisfy a capacity limit. Combining the two provides both freshness control and bounded resource usage.

What is a cache eviction policy?

An eviction policy determines which cached entry should be removed when the cache cannot keep everything it currently contains. For example, LRU removes the entry that has been unused for the longest time. The goal is to keep entries that are more likely to provide useful cache hits.

How would you choose an eviction policy for a distributed cache?

I would first examine the application's access pattern, cache size, object cost, and tolerance for misses or stale data. LRU is a reasonable fit when recent accesses predict future accesses, while LFU can fit workloads with persistent hot keys. I would validate the choice using cache-hit metrics and production-like workload tests rather than assuming one policy is universally optimal.