Cache algorithm — eviction policies and practical trade-offs

Core concepts and measurements

Understanding cache algorithms requires a few basic terms. A cache hit is when the requested item is present in the cache; a miss occurs when it is not. Misses may be compulsory (first-time requests), capacity-related (cache too small), or conflict-related (placement rules force eviction). Eviction policy is the rule used to select which entry to remove on a miss when space is needed. Metadata such as timestamps, counters or small bits may be stored for each entry to support a policy, but maintaining metadata has time and space overheads. Some caches also use admission policies (deciding whether a new item should enter the cache) and prefetching (proactively loading likely future items).

Common eviction policies

• Belady’s optimal (clairvoyant) algorithm: The theoretical optimum is to evict the item whose next use is farthest in the future. This policy yields the smallest possible miss rate for a given trace, but it requires perfect knowledge of future requests and so is not implementable in practice. It is useful as a lower bound for comparing real algorithms.
• Least Recently Used (LRU): Evict the item that has not been used for the longest time. LRU works well for workloads with strong temporal locality, and it is conceptually simple. Exact LRU can be expensive in hardware or large software caches because updating and tracking recency for many items costs time and memory. Variants and approximations exist to reduce overhead.
• Most Recently Used (MRU): Evict the most recently used item. MRU can be effective when recently referenced items are less likely to be reused soon — for example in some database access patterns — and it has the benefit of very simple implementation in specific contexts.
• Least Frequently Used (LFU): Evict items accessed least often over some time window. LFU captures long-term popularity but may keep stale items that were once very popular. Implementations often combine aging or decay mechanisms to avoid unfairly favoring old hot items.
• Pseudo-LRU (PLRU): An approximation of LRU that uses very little metadata (often a single bit per item or a small tree of bits). PLRU is commonly used in high-speed CPU caches where true LRU overhead would be too high. It favors implementation speed over perfect recency tracking.
• Set-associative and direct-mapped arrangements: In hardware caches the address of an item determines a restricted set of locations. A two-way set-associative cache allows two possible slots and evicts the less desirable of those two; direct-mapped caches map each address to exactly one slot and simply overwrite it. These are placement strategies combined with simple eviction rules that trade flexibility for access speed and simplicity.
• Adaptive and hybrid policies: Algorithms such as Adaptive Replacement Cache (ARC) and Multi-Queue (MQ) try to combine the strengths of recency-based and frequency-based approaches. ARC, for example, dynamically balances LRU and LFU behavior to adapt to changing workloads and often provides better practical performance than either approach alone.

Practical considerations and variants

Real-world cache design mixes eviction policy with other concerns. Items differ in size, fetch cost and validity lifetime; a good cache may prefer to keep large but cheap-to-fetch objects short-term while retaining small or expensive-to-generate objects longer. Size-aware eviction policies, cost-aware ranking and weighted replacement score entries by a composite metric instead of simple recency or frequency.

Time-to-live (TTL) or explicit expiration is common in networked caches: entries are valid only for a defined time and are discarded when stale regardless of recency. Admission policies decide whether a new item should enter the cache at all; for example, tiny or one-off objects may be excluded to avoid displacing reusable data. Maintenance overhead, concurrency support and predictability under adversarial patterns are also important: some policies can be forced into very poor performance by particular request sequences (a phenomenon known as thrashing).

Distributed caches and coherence

When multiple caches store copies of overlapping data — such as in content delivery networks, database clusters or multi-core CPUs — maintaining a consistent view of data adds complexity. Cache coherency mechanisms coordinate updates, invalidations and write propagation. Distributed caches must also consider network latency, replication, partitioning and consistency models when choosing eviction and replication strategies. Some systems combine local caches with a shared central store and use policies that respect both local access patterns and global cost metrics.

History, applications and examples

Cache research has deep roots in both operating systems and computer architecture. The page replacement problem studied in virtual memory systems produced many early algorithms, and Belady’s work established the optimal baseline. As hardware evolved, approximations like PLRU and set-associative layouts became standard in CPU caches to meet tight timing constraints. In software systems, LRU and variants dominate web, database and object-caching libraries, while LFU and hybrid schemes appear when long-term popularity matters. Modern content delivery networks, in-memory databases, web browsers, DNS resolvers and operating system buffers all use cache algorithms tuned to their specific workloads.

How to choose and tune a cache algorithm

1. Measure the workload: collect traces or representative request patterns to learn about locality, frequency and object sizes.
2. Define objectives: prioritize hit rate, tail latency, fairness, cost of misses or predictability according to application needs.
3. Select a candidate policy: use simple LRU or approximations where recency dominates; choose LFU or hybrid ARC for long-tail popularity; use size- and cost-aware rules if objects vary widely.
4. Implement instrumentation and test: compare against a baseline, and consider offline simulation with Belady’s optimal as a lower bound.
5. Iterate and adapt: workloads change, so adaptive policies or runtime-configurable settings can maintain good performance over time.

For additional technical detail on eviction policies and formal analysis see external resources: eviction policy overview, algorithmic foundations and models of caching performance; latency and workload characterization, guidance on measuring and modeling cache latency and miss costs; and database and application caching, practical advice for tuning caches in server and application environments.

In summary, cache algorithms are fundamental to system performance and resource efficiency. There is no one-size-fits-all solution: the best policy depends on access patterns, hardware constraints and the relative cost of misses. Understanding the trade-offs, measuring real workloads and choosing either a well-known policy or an adaptive hybrid typically yields the best results.