vault

Adaptive Replacement Cache

21 min read

Adaptive Replacement Cache

The Adaptive Replacement Cache (ARC) is a cache eviction policy invented by Nimrod Megiddo and Dharmendra Modha at IBM Almaden and presented at USENIX FAST 2003. ARC self-tunes the balance between recency (the LRU philosophy: “what was used last is likely to be used next”) and frequency (LFU’s philosophy: “what’s been used a lot is likely to be used a lot more”). It maintains four lists — two real (T1, T2) and two ghost (B1, B2) holding only the keys of recently-evicted entries — and uses the hit pattern on the ghost lists to dynamically grow or shrink the recency vs frequency budget. ARC consistently matches or beats LRU on every standard cache trace ever published, while remaining scan-resistant (a one-time large scan does not blow out the cache) and constant-time per operation. Production users include OpenZFS (the dominant ARC deployment, ~since 2005), IBM DS6000/DS8000 storage controllers, and VMware vSAN (a “variant of ARC”, per the Wikipedia summary). PostgreSQL shipped ARC in 8.0.0 (January 2005) but pulled it within a single point release: 8.0.1 (February 2005) reverted to a simpler clock algorithm explicitly to side-step the IBM patent, after Tom Lane’s “Escaping the ARC patent” thread on pgsql-hackers (archive; LWN coverage). The algorithm was patented as U.S. Patent 6,996,676 B2 (issued 2006, expired 22 February 2024 per the USPTO record on Google Patents; the patent was assigned to IBM, then transferred to Intel in 2013 and to Tahoe Research in 2022). That patent — now expired but in force for two decades — is the historical reason ARC is absent from the Linux page cache and from MySQL’s InnoDB buffer pool, both of which evolved alternative two-list or LIRS-style policies during the patent term.

1. Intuition — Two Caches, One Self-Tuning Budget

The key insight: an LRU cache excels when the workload exhibits temporal locality (“just-touched items are about to be touched again”), and an LFU cache excels when the workload exhibits frequency locality (“hot items stay hot for a long time”). Real workloads mix both. A strict LRU is destroyed by a one-time scan — say, a backup process that reads every file once: it pushes out all your hot items even though you’ll never reference those scanned items again. A strict LFU is destroyed by workload phase transitions — yesterday’s hot items are not today’s hot items, but their frequency counters say they are.

ARC’s solution is to keep two LRU lists:

  • T1 — items seen only once recently. This is the “recency” cache.
  • T2 — items seen more than once recently. This is the “frequency” cache.

A first-time access enters T1. If the item is still in T1 when accessed again (a “second hit”), it gets promoted to T2 — now we know it’s not a one-off. Items evicted from T1 do not go to T2; they go to a ghost list B1 that records only their keys (no data), and similarly evictions from T2 land in ghost list B2.

The clever part is adaptivity. The cache budget is fixed at c slots total (T1 size + T2 size = c). The split between T1 size and T2 size is governed by a target value p (think of it as “how many slots T1 deserves”). When a hit occurs in B1 (a key recently evicted from T1), it’s evidence that we evicted from T1 too eagerly — recency is being under-served — so we increase p (grow T1’s budget). When a hit occurs in B2 (a key recently evicted from T2), we decrease p (grow T2’s budget). The ghost lists are a recently-evicted “memory” that lets the cache observe its own past mistakes and correct them.

The result: ARC behaves like LRU on recency-dominated workloads, like LFU on frequency-dominated workloads, and it gracefully shifts between them as the workload phase changes — no parameters to tune. Megiddo & Modha’s 2003 paper benchmarks ARC against LRU on 23 production traces (web cache, database buffer pool, OS page cache, storage workloads) and reports hit-rate improvements ranging from negligible (where LRU is already optimal) to 20+ percentage points — e.g. on the SPC1-like synthetic at 4 GB cache, LRU achieves 9.19% hit rate vs ARC’s ~20%. ARC is never worse than LRU on the published traces.

2. Tiny Worked Example

Cache size c = 4. We track |T1|, |T2|, |B1|, |B2|, and the target p (initially 0).

Access sequence: A B C D A E F G H A

I’ll abbreviate the state as T1=[…] T2=[…] B1=[…] B2=[…] p=…. Newest items are on the right of each list. The full ARC algorithm has multiple cases; I’ll narrate the principal ones.

Step 1: A   miss, new
   T1=[A]  T2=[]  B1=[]  B2=[]  p=0
Step 2: B
   T1=[A,B] T2=[] B1=[] B2=[] p=0
Step 3: C
   T1=[A,B,C] T2=[] B1=[] B2=[] p=0
Step 4: D
   T1=[A,B,C,D] T2=[] B1=[] B2=[] p=0     # cache full
Step 5: A   HIT in T1 -> promote to T2
   T1=[B,C,D] T2=[A] B1=[] B2=[] p=0
Step 6: E   miss; cache full -> evict from T1 (oldest=B), B goes to B1
   T1=[C,D,E] T2=[A] B1=[B] B2=[] p=0
Step 7: F   miss; evict T1 oldest (C) -> B1
   T1=[D,E,F] T2=[A] B1=[B,C] B2=[] p=0
Step 8: G   miss; evict T1 oldest (D) -> B1
   T1=[E,F,G] T2=[A] B1=[B,C,D] B2=[] p=0
Step 9: H   miss; evict T1 oldest (E) -> B1
   T1=[F,G,H] T2=[A] B1=[B,C,D,E] B2=[] p=0
Step 10: A  HIT in T2 -> move to MRU end of T2; no eviction
   T1=[F,G,H] T2=[A] B1=[B,C,D,E] B2=[] p=0

Now imagine the next access is B:

Step 11: B   GHOST HIT in B1 -> we evicted B from T1 too soon!
              Adapt: p = min(p + delta, c) = min(0 + 1, 4) = 1
              Move B to T2 (it's now seen >1, by virtue of having been seen once before
              and being seen again).
              Evict from T1 (since |T1| > 0 and |T1| > p) — but wait,
              the ARC eviction subroutine evicts from T1 if |T1| > p, else from T2.
              p is now 1, |T1|=3, so evict T1 oldest (F) -> B1.
   T1=[G,H] T2=[B,A] B1=[C,D,E,F] B2=[] p=1

The ghost-list hit in B1 told ARC “you evicted recency too quickly,” and ARC reacted by increasing p — making T1 (the recency cache) bigger. Conversely a hit in B2 would shrink p, growing T2 (the frequency cache).

This adaptivity is what no static algorithm — pure LRU, pure LFU, even fixed-ratio LRU/LFU hybrids — can match.

3. The Algorithm

3.1 The Four Lists

|T1| ≤ c        recency cache (items seen once)
|T2| ≤ c        frequency cache (items seen ≥2 times)
|B1| ≤ c        ghost: keys recently evicted from T1
|B2| ≤ c        ghost: keys recently evicted from T2
|T1| + |T2|   = c                 (cache budget)
|T1| + |B1|   ≤ c                 (recency lookback)
|T2| + |B2|   ≤ 2c                (frequency lookback)
|T1|+|T2|+|B1|+|B2| ≤ 2c
0 ≤ p ≤ c                          (target T1 size; p adapts)

Each list is a doubly linked list combined with a hash map for O(1) membership testing — same structure as a standard LRU cache. The ghost lists store only the key, not the value; that’s why their memory cost is small (a few bytes per ghost entry).

3.2 The Replace Subroutine

The eviction decision when the cache is full:

function REPLACE(x, p):
    # x is the new key being inserted; p is the current target T1 size
    if |T1| > 0 and (|T1| > p or (x in B2 and |T1| == p)):
        # Recency budget overshot: evict from T1
        victim = T1.pop_lru()
        B1.push_mru(victim)
    else:
        # Frequency budget overshot or x is a B1-ghost-hit forcing T1 budget growth
        victim = T2.pop_lru()
        B2.push_mru(victim)

The condition |T1| > p (“T1 is bigger than its budget”) is the primary driver. The corner case x ∈ B2 ∧ |T1| == p says: if the new item is itself a returnee from B2 and T1 is exactly at its budget, evict from T1 anyway (because growing T1 by 1 would push us over c).

3.3 The Main Loop

For each access on key x:

function ACCESS(x):
    if x in T1:                                 # CASE I: hit in T1
        T1.remove(x); T2.push_mru(x)
        return value(x)

    if x in T2:                                 # CASE II: hit in T2
        T2.move_to_mru(x)
        return value(x)

    if x in B1:                                 # CASE III: ghost hit in B1
        # Evidence: recency was too small. Grow p.
        delta = max(1, |B2| / |B1|)
        p = min(p + delta, c)
        REPLACE(x, p)
        B1.remove(x); T2.push_mru(x)            # x is "seen again" -> T2
        return load(x)

    if x in B2:                                 # CASE IV: ghost hit in B2
        # Evidence: frequency was too small. Shrink p.
        delta = max(1, |B1| / |B2|)
        p = max(p - delta, 0)
        REPLACE(x, p)
        B2.remove(x); T2.push_mru(x)
        return load(x)

    # CASE V: total miss (not in any list)
    if |T1| + |B1| == c:
        if |T1| < c:
            B1.pop_lru()                       # discard oldest ghost
            REPLACE(x, p)
        else:
            T1.pop_lru()                       # cache full of T1; evict oldest
    else:
        total = |T1| + |T2| + |B1| + |B2|
        if total >= c:
            if total == 2*c:
                B2.pop_lru()
            REPLACE(x, p)
    T1.push_mru(x)                             # new item enters T1
    return load(x)

Megiddo & Modha’s pseudocode (Figure 4 of the FAST ‘03 paper) is the canonical reference; the version above paraphrases it.

3.4 Why Random-Access Time Is O(1)

Every operation is a constant number of doubly-linked-list moves, hash-table lookups, and arithmetic comparisons. None of the cases require iteration over the lists. This contrasts with naive LFU implementations, which are O(log n) or worse to find the minimum-frequency item. ARC’s O(1) per access is identical to LRU’s, with a constant-factor overhead from the four lists instead of one.

3.5 Scan Resistance

A scan sweeps through items the system will not access again (a one-time backup, a checksum pass over all files). In a strict LRU, every scanned item gets cached, displacing whatever was useful. In ARC, scanned items enter T1 only; they do not get promoted to T2 because they are not re-accessed. When T1 fills, the oldest scanned items are evicted before they can damage T2’s frequency cache. Hot items in T2 are protected from the scan. This is the property the OpenZFS team cared most about — backup workloads were destroying their disk caches.

4. Python Implementation

from collections import OrderedDict
from typing import Optional, Callable
 
 
class ARCCache:
    """
    Adaptive Replacement Cache (Megiddo & Modha, FAST 2003).
    O(1) get/put. Total cache budget = c entries.
    """
 
    def __init__(self, c: int, loader: Optional[Callable[[object], object]] = None):
        self.c = c
        self.p = 0                                  # target |T1|
        self.t1: OrderedDict = OrderedDict()        # recency: key -> value
        self.t2: OrderedDict = OrderedDict()        # frequency: key -> value
        self.b1: OrderedDict = OrderedDict()        # ghost recency: key -> None
        self.b2: OrderedDict = OrderedDict()        # ghost frequency: key -> None
        self.loader = loader or (lambda k: None)
 
    # --- helpers: OrderedDict end conventions
    # last (right) = MRU, first (left) = LRU. We use move_to_end for promotion.
 
    def _replace(self, key) -> None:
        """Evict one item from T1 or T2 according to the ARC rule."""
        if self.t1 and (len(self.t1) > self.p or
                        (key in self.b2 and len(self.t1) == self.p)):
            victim_key, _ = self.t1.popitem(last=False)   # T1 LRU
            self.b1[victim_key] = None
        else:
            victim_key, _ = self.t2.popitem(last=False)   # T2 LRU
            self.b2[victim_key] = None
 
    def get(self, key):
        # CASE I: hit in T1 -> promote to T2 MRU
        if key in self.t1:
            value = self.t1.pop(key)
            self.t2[key] = value
            return value
        # CASE II: hit in T2 -> bump to MRU
        if key in self.t2:
            self.t2.move_to_end(key)
            return self.t2[key]
        # CASE III: ghost hit in B1 -> grow p, fetch, place in T2
        if key in self.b1:
            delta = max(1, len(self.b2) // max(len(self.b1), 1))
            self.p = min(self.p + delta, self.c)
            self._replace(key)
            del self.b1[key]
            value = self.loader(key)
            self.t2[key] = value
            return value
        # CASE IV: ghost hit in B2 -> shrink p, fetch, place in T2
        if key in self.b2:
            delta = max(1, len(self.b1) // max(len(self.b2), 1))
            self.p = max(self.p - delta, 0)
            self._replace(key)
            del self.b2[key]
            value = self.loader(key)
            self.t2[key] = value
            return value
        # CASE V: total miss
        l1_total = len(self.t1) + len(self.b1)
        l2_total = len(self.t2) + len(self.b2)
        if l1_total == self.c:
            if len(self.t1) < self.c:
                self.b1.popitem(last=False)        # discard oldest B1
                self._replace(key)
            else:
                self.t1.popitem(last=False)        # cache full of T1
        else:
            total = l1_total + l2_total
            if total >= self.c:
                if total == 2 * self.c:
                    self.b2.popitem(last=False)
                self._replace(key)
        value = self.loader(key)
        self.t1[key] = value
        return value
 
    def put(self, key, value):
        """Insertion path mirrors get; we just override the loader."""
        prev_loader = self.loader
        self.loader = lambda _: value
        try:
            self.get(key)
        finally:
            self.loader = prev_loader
 
    def stats(self):
        return {"|T1|": len(self.t1), "|T2|": len(self.t2),
                "|B1|": len(self.b1), "|B2|": len(self.b2), "p": self.p}
 
 
# --- demo: scan-resistance --------------------------------------------------
if __name__ == "__main__":
    cache = ARCCache(c=4)
    # Working set of hot items
    for k in ["A", "B", "C", "D", "A", "B", "C", "D"]:
        cache.put(k, k.lower())
    print("After warmup:", cache.stats())
    # Big one-time scan
    for k in ["S1", "S2", "S3", "S4", "S5", "S6", "S7", "S8"]:
        cache.put(k, k.lower())
    print("After scan:", cache.stats())
    # Hot items should still be reachable -> ideally hits in T2
    for k in ["A", "B", "C", "D"]:
        print(k, "->", cache.get(k))
    print("After re-access:", cache.stats())

The implementation captures the four lists, the p adaptation on ghost hits, and the eviction rule. A production ARC would use a hand-rolled doubly-linked list rather than OrderedDict (which has constant-factor overhead), and would protect concurrent access with fine-grained locks or a CAS-based design. OpenZFS’s ARC adds further refinements — eviction tickets, watermarks, ghost-list size limits.

5. Complexity and Math

OperationTimeSpace
get(key) (any case)O(1)—
put(key, value)O(1)—
Cache memoryO(c) values + O(c) ghost keys—

The Megiddo-Modha paper’s headline guarantee is empirical, not a tight competitive ratio: ARC is shown to match or beat LRU on every one of the 23 published traces, with substantial gains where the workload mixes a hot working set with one-time scans. (Classical competitive analysis is unkind to any online paging algorithm — LRU’s competitive ratio against the offline OPT is k, the cache size, and no deterministic online algorithm can do asymptotically better; ARC’s value lies in its real-workload behaviour and self-tuning, not in a stronger worst-case bound.)

The paper’s empirical results (their Tables IV–VI) report ARC’s hit-rate vs LRU’s on 23 traces:

  • DS1 (database trace): LRU 16%, ARC 38%.
  • WebSearch1: LRU 12%, ARC 23%.
  • ConCat (concurrent OLTP): LRU 10%, ARC 25%.
  • Other traces: smaller gains, but never a loss.

The improvement is largest on workloads that have both a hot working set and a long tail of one-time references — exactly the scan-resistance scenario.

6. Variants

6.1 CAR (Clock with Adaptive Replacement)

Bansal & Modha, FAST 2004. Replaces ARC’s doubly-linked lists with clock pointers (the classic page-replacement primitive used inside operating systems and database buffer pools). CAR has the same self-tuning logic as ARC but performs better on multi-threaded workloads because clock implementations need fewer locks. CAR was the variant the IBM AIX team eventually shipped.

6.2 CART (Clock with Adaptive Replacement, Temporal filtering)

Bansal & Modha 2004 follow-up. Adds the constraint that the second access to an item only promotes to T2 if it’s “long enough after” the first. Improves on workloads with rapid-fire short-burst re-references.

6.3 W-TinyLFU (Caffeine, Java caching library)

Einziger, Friedman & Manes, 2017. Beats ARC on most workloads. The key idea: instead of two lists (T1/T2), use a small window LRU (recency) and a main LFU-with-aging. Items enter the window; admission to main is gated by a Count-Min Sketch that approximates frequency. The frequency sketch is aged (halved periodically) so old hot keys don’t dominate forever. Caffeine’s benchmarks claim W-TinyLFU achieves higher hit rates than ARC on every published trace they tested. Caffeine is the default cache in Spring Boot, Cassandra, Akka, and many other JVM systems.

6.4 LIRS (Low Inter-reference Recency Set)

Jiang & Zhang, SIGMETRICS 2002. A different self-tuning approach using inter-reference recency (distance between consecutive references to the same item) instead of access counts. Used by MySQL InnoDB’s buffer pool. Competitive with ARC on most workloads.

6.5 2Q

Johnson & Shasha, VLDB 1994 (predecessor to ARC). Two LRU lists: A1 (newcomers, FIFO) and Am (mainline, LRU). Items enter A1; on a second access, they migrate to Am. Simpler than ARC, but the A1 / Am sizes are hand-tuned fixed parameters — no self-tuning. PostgreSQL uses a variant of 2Q in its buffer pool.

6.6 SLRU (Segmented LRU)

Two LRU segments: probationary and protected. Items enter probationary; second access promotes to protected. Conceptually a static 2Q.

7. The Patent — Why Linux and Some DBs Avoided ARC (And Why That Constraint Just Lifted)

IBM filed US Patent 6,996,676 B2 — “System and method for implementing an adaptive replacement cache policy” — on 14 November 2002 (priority and filing date both that day); it issued 7 February 2006. Per the Google Patents legal-events record, it expired on 22 February 2024 with the cause “Expired - Lifetime”. Ownership moved from IBM (original assignee) to Intel in 2013 and from Intel to Tahoe Research Ltd on 15 August 2022; the algorithm was published in March 2003, so any 35 U.S.C. §102(b) one-year bar would in any case have closed off further patentability long ago. During the patent’s two-decade lifetime, several major open-source projects steered around it:

  • PostgreSQL is the cleanest cautionary tale. PostgreSQL 8.0.0 (January 2005) shipped ARC as its buffer replacement strategy. Within weeks the patent surfaced as a redistribution risk for downstream commercial forks, and Tom Lane drove the “Escaping the ARC patent” thread on pgsql-hackers (January 2005, archive); the project ripped ARC out for 8.0.1 (February 2005), shipping a simpler 2Q-derived strategy, and replaced that with the now-current “clock sweep” in 8.1 (LWN 2005 coverage). Bonus motivation: their benchmarks showed 2Q matched ARC on PostgreSQL’s workloads, so the legal exposure bought no measurable hit-rate.
  • The Linux kernel page cache uses a two-list active/inactive design that resembles ARC’s T1/T2 in spirit but pre-dates the ARC paper and was implemented independently; the kernel community did not adopt ARC during the patent’s lifetime, citing patent risk as one factor among several.
  • MySQL InnoDB uses a young/old sublist scheme inspired by LIRS, not ARC.
  • OpenZFS uses ARC because the original ZFS shipped under Sun’s CDDL with IBM patent permissions negotiated, and the OpenZFS lineage inherits that grant. ZFS-on-Linux therefore ships ARC even though the rest of the Linux memory subsystem does not.

With the patent now expired, the legal blocker is gone — but the technical case for switching is muted: workloads have shifted to NVMe/DRAM where W-TinyLFU (see §6.3) typically beats ARC on hit rate with smaller metadata, so most projects that built around the constraint are unlikely to migrate to ARC purely on the basis that they now legally could.

8. Production Examples

8.1 OpenZFS / ZFS

The most prominent ARC deployment. ZFS allocates a substantial fraction of system RAM to its ARC; tunables include zfs_arc_min, zfs_arc_max, and arc_dnode_limit. ZFS exposes per-list size statistics via arc_summary so administrators can see |T1|, |T2|, |B1|, |B2| in real time. The “L2ARC” feature uses a fast SSD as a second-level extension of ARC.

8.2 IBM Storage Systems

Storage controllers like the IBM SAN Volume Controller historically used ARC (or CAR) in their buffer caches. This is the original deployment context the Megiddo-Modha paper was written for.

8.3 OpenSolaris / Illumos

Inherits ARC from ZFS; used in the OpenSolaris page cache as well in some derivative distributions.

8.4 Where ARC is not used

  • Linux kernel: 2-list active/inactive LRU.
  • PostgreSQL: clock-sweep (8.1+), reached after the 8.0.0 → 8.0.1 ARC removal forced by the patent.
  • MySQL InnoDB: LIRS-derived.
  • Memcached: simple LRU (with slabs).
  • Redis: configurable; default is LRU approximation; has LFU mode (since 4.0); no ARC.
  • Modern JVM applications: W-TinyLFU via Caffeine.

The pattern is: ARC dominates where its license could be obtained (ZFS, IBM); LRU/LFU variants and W-TinyLFU dominate everywhere else.

9. Pitfalls

9.1 The Patent Decision

Most cache-implementer interviews ask “why doesn’t Linux/MySQL/etc use ARC?” The expected answer is the patent (and now also W-TinyLFU’s existence). Be ready to discuss this; it’s a well-known historical artifact.

9.2 Ghost Lists Need Real Memory

Although ghost entries are “just keys, no values,” for a billion-entry cache the keys alone are gigabytes. Production implementations bound the ghost-list size and accept that older ghost evictions blur ARC’s adaptation a little. ARC’s published bounds assume the ghost lists are full-size; truncating them weakens the theoretical guarantees.

9.3 Multi-Threaded Concurrency

The four-list structure is harder to make lock-free than single-list LRU. CAR (clock variant) was specifically motivated by this; it uses clock hands rather than linked-list pointer manipulation, which scales better under contention. If you implement ARC as in §4 with a single global lock, throughput plateaus on many-core hosts.

9.4 Bursty Workloads and p Oscillation

On highly bursty workloads with rapid phase changes, p can oscillate between large and small values. Some implementations clamp the per-step delta or use exponential moving averages to smooth.

9.5 Cache Stampede on Ghost Hit

A ghost hit means the system has to load the value from the slow source. Concurrent requests for the same ghost-hit key may all trigger loads. Use single-flight / request-coalescing on the load path (orthogonal to ARC’s correctness).

9.6 Comparing Against the “Wrong” Baseline

ARC’s hit-rate gains over LRU look impressive on certain traces and modest on others. Always benchmark against multiple baselines — LRU, LFU, 2Q, W-TinyLFU — on your workload before claiming ARC is the right choice.

9.7 Memory Account vs Slot Account

The original ARC counts slots (entries), not bytes. For variable-size values (e.g., HTTP responses), a byte-aware adaptation is needed; this is non-trivial because the p parameter loses its dimensional meaning.

10. Mermaid Diagram — The Four Lists and p

flowchart LR
    subgraph CACHE["Cache size c (T1 + T2 = c)"]
        T1["T1 (recency)<br/>seen once"]
        T2["T2 (frequency)<br/>seen >= 2 times"]
    end
    subgraph GHOST["Ghosts (keys only)"]
        B1["B1 (recently<br/>evicted from T1)"]
        B2["B2 (recently<br/>evicted from T2)"]
    end
    NEW[New access x]
    NEW -- "x not seen" --> T1
    T1 -- "second hit" --> T2
    T1 -- "evicted" --> B1
    T2 -- "evicted" --> B2
    B1 -- "ghost hit:<br/>p += delta<br/>(grow T1)" --> T2
    B2 -- "ghost hit:<br/>p -= delta<br/>(grow T2)" --> T2
    PARAM["p in [0, c]<br/>target T1 size"]
    PARAM -.adjusted by.-> B1
    PARAM -.adjusted by.-> B2

What this diagram shows. The cache itself is the box on the left holding the two real lists T1 (recency) and T2 (frequency); their combined size is fixed at c. New accesses enter T1; on a second hit they promote to T2. When eviction is needed, ARC chooses T1 or T2 based on the current target p: if T1 is over budget (|T1| > p), it evicts from T1 LRU into the ghost B1; otherwise it evicts from T2 LRU into B2. The two ghost lists on the right hold only the keys of evicted items, no values, so they are cheap. The crucial feedback is the dotted arrows from p to B1 and B2: a hit in B1 (we evicted recency too soon!) increases p, expanding T1’s budget for the next eviction; a hit in B2 (we evicted frequency too soon!) decreases p, expanding T2’s budget. This closed-loop feedback is what makes ARC self-tuning; the cache observes its own past mistakes via the ghost lists and adjusts the recency/frequency split without any operator input.

11. Common Interview Problems

QuestionExpected hit
“Design a self-tuning cache that’s better than LRU”ARC: T1/T2/B1/B2; ghost-list-driven adaptation of p
“Why doesn’t Linux use ARC?”IBM patent (US 6,996,676) was the historical blocker (expired 22 Feb 2024); today the technical case is also weaker because W-TinyLFU typically wins on modern workloads
“When would you choose ARC over LRU?”Workloads with both hot working set and one-time scans; ARC’s scan resistance is the key win
“ARC vs LFU vs LRU — explain the trade-offs”LRU: fast, susceptible to scans. LFU: hot keys stick, slow to react to phase changes. ARC: adaptive, scan-resistant, O(1).
“Implement ARC”Four lists + hash table + the case-based access function
“What does the p parameter represent?”Target size of T1; adapts based on ghost-list hits
“How is ARC scan-resistant?”One-time scan items enter T1 only and never get promoted to T2; T2 (the hot working set) is protected
“What’s W-TinyLFU and why might it beat ARC?”Window-LRU + frequency-sketch admission + aging; better hit rates on most modern traces

12. Open Questions

  • What is the precise expiration date of US Patent 6,996,676 and any continuations? Resolved: expired 22 February 2024 (Google Patents legal-events record). No active continuation is listed against the same family in the USPTO record consulted; future ARC-derivative IP would have to be independently filed.
  • On modern SSD-backed L2 caches (millions of slots), is ARC’s p adaptation fast enough, or does it lag the workload?
  • Has any modern Linux subsystem (zswap, bcachefs) experimented with adopting ARC now that the patent has expired? (Search ongoing — no upstream patches landed as of May 2026.)
  • When does W-TinyLFU’s frequency sketch become a memory liability vs ARC’s ghost lists?
  • For variable-size values (HTTP cache, object cache), what’s the cleanest byte-aware ARC adaptation?

13. See Also

Graph View

Backlinks