Cache Eviction Policy

A cache eviction policy determines which cached entries are removed when the cache reaches its capacity. Common policies include LRU, LFU, FIFO, and size-based approaches, with the appropriate choice depending on access patterns and application goals.

A cache has finite capacity, so inserting a new entry may require removing an existing one. The eviction policy defines the rule used to choose that entry. Without an eviction policy, a bounded cache cannot decide what to discard when it is full.

LRU (Least Recently Used) removes the entry that has gone unused for the longest time. It is a common general-purpose choice because recently accessed data is often more likely to be accessed again. LFU (Least Frequently Used) instead considers how often entries have been accessed, while FIFO removes entries in insertion order.

In Java, an LRU cache can be implemented conveniently with `LinkedHashMap` by enabling access-order and overriding `removeEldestEntry`. This keeps recently accessed entries near the end of the ordering and allows the oldest entry in that ordering to be evicted when the configured capacity is exceeded.

The policy affects hit rate, memory usage, and performance. A policy that matches the application's workload can reduce cache misses, but no policy is universally optimal; sequential scans, repeated hot keys, and changing popularity patterns can favor different strategies.

Key points

• Eviction is necessary when a bounded cache has no room for a new entry.
• LRU removes the least recently accessed entry.
• LFU removes entries based on access frequency rather than recency.
• FIFO removes the oldest inserted entry regardless of later accesses.
• The best policy depends on the application's access pattern and cache goals.

Interview questions

What factors would you consider when choosing an eviction policy for a backend service?

I would first examine the access pattern, including locality, repetition, and whether popularity changes over time. I would measure cache hit rate and latency rather than assuming a policy is better from its name alone. I would also consider memory limits, entry sizes, expiration requirements, and concurrency. Finally, I would validate the choice with representative workload measurements.

What is a cache eviction policy, and why is it needed?

A cache eviction policy decides which cached entry should be removed when the cache needs to free space. It is needed because a bounded cache cannot retain every entry indefinitely. The policy attempts to keep entries that are most useful for future requests. Examples include LRU, LFU, and FIFO.

How does LRU work?

LRU stands for Least Recently Used. It evicts the entry that has not been accessed for the longest period when space is needed. Every qualifying access updates the entry's recency. This works well when recently used data is likely to be requested again.

How can you implement an LRU cache using Java's standard library?

One simple approach is `LinkedHashMap` configured with access-order by passing `true` as its third constructor argument. The `removeEldestEntry` method can be overridden to evict the eldest entry once the desired size is exceeded. Because access-order moves accessed entries toward the recent end, the eldest entry represents the least recently used entry. For production use, concurrency requirements and the application's cache semantics must also be considered.

What is the difference between LRU and LFU?

LRU uses recency, while LFU uses access frequency. LRU tends to favor entries that were used recently, which can adapt relatively quickly when the workload changes. LFU can favor consistently popular entries even when they have not been accessed in the immediate past. The appropriate choice depends on the application's request distribution.