Skip to content
AfluidityAlgorithm Atlas
Data StructuresAll categories
CoreConcept & Pseudocode EntryAI Reviewed (ai-reviewed)

ARC Cache (Adaptive Replacement Cache)

Self-tuning cache eviction algorithm that dynamically balances recency (T1) and frequency (T2) lists using ghost history lists (B1, B2) to resist sequential scans.

Explore relationshipsOpen 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Data Structures
Difficulty
Advanced
Family
Cache Eviction & Indexing
Tier
Core
Status
Reviewed
Review
AI Reviewed
Sources
1
Formulas
1
Relationships
3
Code example
Not ready
Visualization
Ready
Aliases
Adaptive Replacement Cache, Megiddo-Modha ARC

Overview

Adaptive Replacement Cache (ARC) splits cache capacity c between a recency list T1 (items seen once recently) and a frequency list T2 (items seen at least twice), alongside ghost metadata lists B1 and B2 that remember recently evicted keys. Hits in B1 increase the target size p for T1 (favoring recency), while hits in B2 decrease p (favoring frequency), adapting online in O(1) time without manual tuning.

Core Concepts

recency list T1frequency list T2ghost history lists B1 and B2adaptive target parameter pscan resistance

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(1)

Worst

O(1)

Space

O(c)

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for ARC Cache (Adaptive Replacement Cache) across input scales.

Input Scale N:
JIT-compiled JS/TS (~350M primitive ops/sec)
Est. Average TimeO(1)

11 ns

Sub-microsecond~4
Est. Worst-Case TimeO(1)

11 ns

Sub-microsecond~4
Est. Working MemoryO(c)

1.53 MB

Standard Heap FitN=100,000

When to Use

  • Use ARC Cache when workloads mix recency-heavy bursts, stable high-frequency keys, and sequential scans that would wipe out a plain LRU cache.
  • Use it in storage engines and operating system caches where manual tuning of LRU/LFU partitions is impractical.

When Not to Use

  • Avoid when the extra memory overhead of maintaining 2c ghost directory entries (B1 and B2) is prohibitive for tiny values.

What It Does

  • Balances recency (LRU) and frequency (LFU) cache allocations online via a self-tuning target parameter p
  • Prevents one-time sequential table or file scans from evicting frequently reused working-set pages

Use Cases

  • Filesystem page caches (ZFS ARC) and storage array read caches
  • Database buffer pools facing mixed OLTP point lookups and sequential table scans
  • Zero-configuration caching where workload recency vs frequency bias changes dynamically

Inputs

  • Cache capacity c and stream of page/key requests

Outputs

  • Adaptive O(1) cache hit/miss handling with scan-resistant eviction

Key Formulas (1)

Ghost Hit Adaptation Rule

p ← min(c, p + max(1, |B2|/|B1|)) on B1 hit; p ← max(0, p − max(1, |B1|/|B2|)) on B2 hit
p <- min(c, p + max(1, |B2|/|B1|)) on B1 hit; p <- max(0, p - max(1, |B1|/|B2|)) on B2 hit

Shifts target T1 capacity p toward recency on B1 hits and toward frequency on B2 hits.

Pseudocode

  1. 1.Maintain cached lists T1 (seen once) and T2 (seen >= 2 times) with |T1| + |T2| <= c, ghost lists B1, B2, and target p in [0, c]
  2. 2.On hit in T1 or T2: move key to MRU of T2 and return value
  3. 3.On ghost hit in B1: increase p = min(c, p + max(1, |B2| / |B1|)), REPLACE(key, p), move key from B1 to MRU of T2
  4. 4.On ghost hit in B2: decrease p = max(0, p - max(1, |B1| / |B2|)), REPLACE(key, p), move key from B2 to MRU of T2
  5. 5.On complete miss: if |T1| + |T2| == c, REPLACE(key, p) moving evicted T1/T2 LRU key into B1/B2; insert new key at MRU of T1

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

  1. Maintain cached lists T1 (seen once) and T2 (seen >= 2 times) with |T1| + |T2| <= c, ghost lists B1, B2, and target p in [0, c]
  2. On hit in T1 or T2: move key to MRU of T2 and return value
  3. On ghost hit in B1: increase p = min(c, p + max(1, |B2| / |B1|)), REPLACE(key, p), move key from B1 to MRU of T2
  4. On ghost hit in B2: decrease p = max(0, p - max(1, |B1| / |B2|)), REPLACE(key, p), move key from B2 to MRU of T2
  5. On complete miss: if |T1| + |T2| == c, REPLACE(key, p) moving evicted T1/T2 LRU key into B1/B2; insert new key at MRU of T1

Canonical Example

Input
Working set in T2 followed by a one-pass sequential scan of c new pages
Output
Sequential scan cycles through T1 and B1 while T2's frequently accessed working set remains intact
Explanation
Because single-touch scan pages enter T1 and never hit B1, p does not grow and T2 is protected from scan pollution.

Implementation Notes

  • Store only keys (not full values) in the ghost lists B1 and B2.

Common Pitfalls

  • Failing to bound total directory size |T1| + |B1| <= c and |T1| + |T2| + |B1| + |B2| <= 2c during misses.
  • Updating the adaptation target p on T1/T2 cache hits instead of only on ghost list (B1/B2) hits.

Interactive Mechanism Walkthrough & State Debugger

Graph Frontier & Edge Relaxation
ARC Cache (Adaptive Replacement Cache) mechanism walkthrough step 1 of 5suvwxt
active vertexs
visited set V{ s }
frontier queue[ u ]
edges relaxed0 / 7
Step 1 of 5: Maintain cached lists T1 (seen once) and T2 (seen >= 2 times) with |T1| + |T2| <= c, ghost lists B1, B2, and target p in [0, c]

Sources (1)

What each reference supports for this entry.

Megiddo & Modha (2003) — ARC: A Self-Tuning, Low Overhead Replacement Cache (FAST '03)

Paper

USENIX FAST paper introducing the Adaptive Replacement Cache.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Alternative toLFU Cache

Data Structures · Core

Balances recency and frequency online without suffering from long-term LFU count pollution.

Compare with this
Improves onLRU Cache

Data Structures · Core

Adds frequency list T2 and ghost lists B1/B2 to make LRU scan-resistant and self-tuning.

Compare with this

Relationships

View full relationship page
Improves onLRU Cache

Adds frequency list T2 and ghost lists B1/B2 to make LRU scan-resistant and self-tuning.

Alternative toLFU Cache

Balances recency and frequency online without suffering from long-term LFU count pollution.

Related Algorithms

LRU CacheLFU CacheHash Table

Tags

CachingData StructuresAdaptiveSystems