Adaptive Replacement Cache (ARC)

ARC maintains two adaptive lists instead of a single cache directory:

• List T1 (Recent Cache): Contains entries accessed only once recently (recency-focused, like LRU).
• List T2 (Frequent Cache): Contains entries accessed at least twice within a recent time window (frequency-focused, like LFU). A separate ghost list (B1, B2) for each tracks recently evicted entries, providing the algorithm with a 'history' of what was just removed to inform its adaptation.

The core of ARC's intelligence is a dynamic parameter p that represents the target size for the recent list (T1). The algorithm continuously adjusts p based on workload:

• Recency-favoring workload: Increases p, allocating more space to T1 (LRU-like behavior).
• Frequency-favoring workload: Decreases p, allocating more space to T2 (LFU-like behavior). This adjustment happens on every cache miss by checking the ghost lists, allowing ARC to converge on the optimal recency/frequency mix for the current access pattern without manual configuration.

For each main list (T1, T2), ARC maintains a corresponding ghost list (B1, B2). These are metadata-only lists that store the keys of recently evicted items, not their values.

• Ghost Hit: If a requested item is found in a ghost list, ARC interprets this as evidence that the corresponding main list (T1 or T2) is too small.
• This ghost hit triggers an adaptive resizing: ARC increases the target size (p) for the list that should have held the item, stealing a page from the other list. Ghost lists provide a low-overhead memory of past mistakes, enabling the algorithm to learn from near-misses.

ARC's eviction and adaptation logic is triggered on a cache miss. The algorithm decides which list to evict from and whether to adapt p:

1. If cache is full and a new item is inserted: Evict from T1 if |T1| ≥ p; otherwise, evict from T2.
2. On a miss that is a ghost hit in B1: Increase p (favor T1).
3. On a miss that is a ghost hit in B2: Decrease p (favor T2). This ensures the policy reacts in real-time to changing access patterns, constantly rebalancing its resources between recency and frequency.

ARC is highly resilient to one-time sequential scans (e.g., a full database table scan) that pollute and destroy the utility of traditional LRU caches.

• Mechanism: A scanned item enters T1 on its first access. Before it can be promoted to the frequent cache (T2), it is likely evicted by subsequent scanned items, as T1's size is controlled.
• The scanned items are recorded in the ghost list B1, but ARC correctly interprets this pattern and does not overreact by drastically resizing p. This makes ARC particularly effective for database buffer pools and file system caches where mixed workloads are common.

Despite its adaptive complexity, ARC maintains O(1) complexity for all operations (insert, access, evict), comparable to LRU.

• Data Structures: Typically implemented using doubly-linked lists and hash maps for constant-time lookups and moves.
• The adaptive logic based on ghost list checks adds minimal constant-time overhead. This efficiency makes ARC suitable for high-performance systems where cache management cannot become a bottleneck, such as operating system page caches, database buffers, and CDN edge caches.

Least Recently Used (LRU) is the foundational recency-based policy that ARC adaptively balances against. It evicts the item that has not been accessed for the longest time. While simple and effective for workloads with strong temporal locality, LRU can be exploited by sequential scans that pollute the cache and suffers under workloads with popular items that are accessed infrequently. ARC's T1 list initially behaves like an LRU list for newly seen items.

Least Frequently Used (LFU) is the frequency-based counterpoint to LRU, evicting the item with the lowest access count. It excels at retaining popular items but can be slow to adapt to changing access patterns, as historically frequent but now stale items can persist. ARC's T2 list functions as an LFU-style list for items that have been accessed more than once, allowing ARC to protect frequently accessed entries from eviction.

The working set model is a theoretical framework defining the set of memory pages a process actively needs within a specific time window to run efficiently without excessive page faults. ARC is a practical, online algorithm that implicitly learns and caches the dynamic working set of an application. By adapting the size of its recency (T1) and frequency (T2) lists, ARC directly optimizes for the currently active working set, minimizing cache misses as the workload changes.

The 2Q (Two-Queue) algorithm is a direct precursor to ARC, using two LRU queues: A1-in for single-access items and Am for multi-access (hot) items. Items enter A1-in; if accessed again before eviction, they move to Am. ARC generalizes and improves upon 2Q by making the boundary between its two lists adaptive based on workload, whereas 2Q uses a fixed-size buffer for new entries. ARC's adaptive parameter (p) dynamically resizes its equivalent lists, providing superior performance across diverse workloads.

Clock-Pro is a low-overhead, approximate implementation of the Adaptive Replacement Cache policy designed for operating system page replacement. It uses clock hands (circular pointers) to scan pages, approximating ARC's recency/frequency lists and adaptive parameter with reference bits and test periods. While more efficient to execute than ARC's exact list management, Clock-Pro provides similar self-tuning behavior, making ARC's principles practical for kernel-level memory management where computational overhead is critical.

A cache eviction policy is the overarching algorithmic rule that determines which item to remove when a cache reaches capacity. ARC is a specific, advanced eviction policy within this category. Key design considerations for any eviction policy include:

• Overhead: Computational cost of maintaining metadata (access counts, timestamps).
• Workload Sensitivity: Performance across scan-heavy, looping, or mixed access patterns.
• Predictability: Whether the policy's behavior is deterministic or adaptive. ARC is distinguished by its self-tuning nature, automatically adjusting its behavior without manual parameter tuning.