Cache eviction policies face a fundamental tension: should you keep recently accessed data or frequently accessed data? Most systems pick one strategy and stick with it, but Adaptive Replacement Cache (ARC) continuously learns from access patterns to balance both approaches automatically.

The LRU-LFU Tradeoff

Least Recently Used (LRU) eviction assumes temporal locality—that recently accessed items are likely to be accessed again soon. It works well for sequential scans and recency-biased workloads but struggles with patterns where old but frequently accessed data gets evicted by a single large scan.

Least Frequently Used (LFU) tracks access counts and keeps the most popular items. This handles recurring access patterns well but responds slowly to workload shifts. An item accessed heavily in the past consumes cache space long after it stops being relevant.

Real workloads mix both patterns. A web cache might serve a small set of popular static assets alongside recently uploaded content that briefly spikes in traffic. No fixed policy handles both optimally.

How ARC Adapts

ARC maintains four lists instead of two. The cache itself is split into two LRU lists: T1 for items seen once recently, and T2 for items seen multiple times. The target size of T1 versus T2 adjusts dynamically based on observed performance.

Two additional “ghost” lists, B1 and B2, track metadata for recently evicted items from T1 and T2 respectively. These don’t hold actual data—just identifiers. When a request hits an entry in B1, the algorithm learns that giving more space to recency (T1) would have prevented that miss. A hit in B2 indicates frequency tracking (T2) should grow instead.

The adaptation mechanism shifts a single tuning parameter that controls the target size ratio between T1 and T2. On a B1 hit, increase T1’s target. On a B2 hit, increase T2’s target. The cache continuously adjusts its behavior to minimize the evidence it sees of making the wrong eviction choice.

Self-Tuning in Practice

This self-tuning property eliminates a significant operational burden. Database buffer pools, CDN edge caches, and distributed storage systems all face wildly varying workloads across deployments and over time. Manual tuning requires deep expertise and ongoing attention.

ARC converges on good behavior automatically. During morning hours when users scan recent content, it might allocate 70% to T1. As the day progresses and hot items accumulate repeated hits, T2 grows. A sudden traffic spike from a shared link doesn’t permanently skew the policy—the ghost entries prevent the cache from being overfitted to a temporary pattern.

The algorithm’s memory overhead is modest: the ghost lists only store metadata, typically just keys or hashes. Total tracking space is roughly twice the actual cache size in terms of entries tracked, but the ghost entries occupy a fraction of the memory since they hold no values.

Scan Resistance

Traditional LRU suffers badly from cache pollution during full-table scans or large file reads. A single sequential operation can flush the entire cache, evicting valuable data to temporarily hold items accessed once and never again.

ARC’s dual-list structure provides inherent scan resistance. Items from a scan enter T1 and remain there only if they receive a second hit, promoting them to T2. A pure scan never generates second hits, so its entries cycle through T1 and get evicted before displacing the established working set in T2. The frequently accessed data survives.

Patent Considerations and Adoption

IBM patented ARC in the early 2000s, which limited its adoption during the patent’s active period. ZFS famously implemented it in its Adaptive Replacement Cache module, leading to licensing discussions. Some systems adopted similar ideas under different names, while others stuck with simpler policies to avoid patent concerns.

The core patents have since expired, opening ARC to broader implementation. Modern storage systems and caching libraries increasingly offer ARC or ARC-inspired policies as an option, particularly when workload characteristics are unknown or highly variable.

When Simpler Policies Suffice

Despite its elegance, ARC isn’t always necessary. If your workload strongly favors recency or frequency, a well-tuned LRU or LFU performs similarly with less overhead. For tiny caches where every operation counts, the ghost list bookkeeping might not pay for itself.

ARC shines in environments where workload patterns shift unpredictably, operational overhead must stay low, and cache efficiency directly impacts performance or cost. That describes a growing share of modern infrastructure, making adaptive eviction an increasingly valuable tool.