ARC and 2Q Adaptive Caches — Mathematical Foundations and Analysis¶

Universe U of pages (keys). Cache holds at most c of them.
Request sequence sigma = r_1, r_2, ..., r_m  with r_t in U, revealed one at a time.

On request r_t:
  if r_t in cache            -> HIT,  cost 0
  else                       -> MISS (fault), cost 1; the page must be brought in,
                                and if the cache is full some page must be EVICTED.

Cost of a policy A on sigma:  cost_A(sigma) = number of faults.

An ONLINE policy must decide eviction at request t knowing only r_1..r_t.
The OFFLINE OPTIMAL policy OPT knows all of sigma in advance (Belady's MIN:
evict the page whose next use is farthest in the future).

Definition (ARC of capacity c). State is a tuple
        (T1, T2, B1, B2, p)
where T1, T2, B1, B2 are ordered lists (MRU at head) of pages and p in {0,1,...,c}.

  T1, T2  hold CACHED pages (with data).        L1 := T1 U B1,   L2 := T2 U B2.
  B1, B2  hold GHOST pages (key/metadata only).

Semantics:
  T1 = pages requested exactly once since entering the directory (recency).
  T2 = pages requested at least twice                          (frequency).
  B1 = pages recently evicted from T1.
  B2 = pages recently evicted from T2.
  p  = TARGET size of T1 (the recency budget); c - p targets T2.

Operation delta on request x updates the state by one of the four cases
(I: x in T1 U T2;  II: x in B1;  III: x in B2;  IV: x new), each invoking
the eviction subroutine REPLACE(x, p) defined in middle.md.

I1.  0 <= |T1| + |T2| <= c
I2.  0 <= |T1| + |B1| <= c                  (i.e. |L1| <= c)
I3.  0 <= |T1| + |T2| + |B1| + |B2| <= 2c   (|L1| + |L2| <= 2c)
I4.  T1, T2, B1, B2 are pairwise disjoint
I5.  if |T1| + |T2| < c, then B1 = B2 = empty
I6.  0 <= p <= c

Base: empty state T1=T2=B1=B2=empty, p=0 satisfies I1-I6 vacuously.

Inductive step. Assume I1-I6 before delta(x). We trace each case.

Case I (x in T1 U T2): x moves from its list to MRU of T2.
   |T1|+|T2| unchanged; no ghost change; p unchanged. I1-I6 preserved.

Case IV (x new):
   First, the size-management block enforces |L1| and the directory bound:
     - If |L1| = c: if |T1| < c drop LRU of B1 (so |B1| decreases) then REPLACE;
       else (|T1| = c, B1 empty) drop LRU of T1 directly.
       After: |L1| <= c, restoring I2.
     - Else if |T1|+|T2|+|B1|+|B2| >= c:
       if total = 2c drop LRU of B2 (restores room under I3), then REPLACE.
   REPLACE evicts one cached page from T1 or T2 into B1 or B2 respectively,
   so |T1|+|T2| decreases by 1 and the matching ghost increases by 1:
   directory total unchanged, I3 preserved; I1 preserved since we then add x to T1
   bringing |T1|+|T2| back up by 1 but only after eviction, so it never exceeds c.
   Finally x is inserted at MRU of T1.

Case II (x in B1): p := min(p + max(1,|B2|/|B1|), c) keeps I6.
   REPLACE evicts one cached page (I1/I3 as above). x is removed from B1
   (|B1| down by 1) and added to MRU of T2 (|T2| up by 1): directory total
   unchanged, |L1| does not increase, I2 preserved.

Case III (x in B2): symmetric to II; p := max(p - max(1,|B1|/|B2|), 0) keeps I6;
   x leaves B2, enters T2.

I4 (disjointness): every case removes x from its old list before inserting it
   elsewhere; REPLACE moves a page from a T-list to the matching B-list (removing
   first). No page is ever in two lists simultaneously.

I5: ghosts are only ever created by REPLACE, which the size-management logic only
   invokes once the cache data is full (|T1|+|T2| = c); below that, B1=B2 stay empty.
QED.

The deltas are  d_+ = max(1, |B2| / |B1|)   on a B1 hit,
                d_- = max(1, |B1| / |B2|)    on a B2 hit.
A B1 hit can only occur if B1 is nonempty, so the denominator |B1| >= 1; symmetric
for B2. Hence no division by zero. After clamping,
        p in [0, c]   (I6),
so p is always a valid target. QED.

A B1 ghost hit is direct evidence: a RECENCY page (evicted from T1) was needed
again -> T1 was too small -> increase p.
A B2 ghost hit is direct evidence: a FREQUENCY page (evicted from T2) was needed
again -> T2 was too small -> decrease p.

Define the drift  Delta p over a window = sum of (+d_+) over B1 hits
                                          - sum of (d_-) over B2 hits.
Sign(Delta p) = sign(g1-weighted - g2-weighted): p moves toward whichever side is
producing the evictable-but-needed pages. When the workload is balanced
(g1 ~ g2 with B1 ~ B2 sizes), the deltas are ~1 each and cancel: p settles.

Claim (anti-thrash). The magnitude of a p-update is inversely proportional to the
size of the SAME-side ghost list and proportional to the OPPOSITE side.

  On a B1 hit: d_+ = max(1, |B2|/|B1|).
  If recency mistakes are already frequent (|B1| large), each further B1 hit moves
  p by a SMALLER step (|B1| in the denominator) -> diminishing response prevents
  runaway. Simultaneously a large |B2| (many frequency mistakes outstanding)
  AMPLIFIES the B1 step, so p corrects faster precisely when both sides are under
  pressure. This negative-feedback shape gives bounded, convergent tracking rather
  than divergence. QED (informal).

t  event        |B1|  |B2|   delta                       p after
-------------------------------------------------------------------
0  (start)        20    20     -                          50
1  hit in B1      20    20    +max(1, 20/20) = +1         51   (recency nudge)
2  hit in B1      19    21    +max(1, 21/19) = +1         52
3  hit in B2      18    22    -max(1, 18/22) = -1         51   (frequency pull)
4  hit in B1       5    40    +max(1, 40/5)  = +8         59   (B2 large -> big push)
5  hit in B1       6    39    +max(1, 39/6)  = +6         65
6  hit in B2      40     6    -max(1, 40/6)  = -6         59   (symmetric)

Define an imbalance potential  Phi(t) = ( |B1(t)| - |B2(t)| )^2  >= 0.

Heuristic claim: the adaptation rule does not amplify imbalance without bound.
A B1 ghost hit (recency need) tends to follow a regime where T1 was too small;
raising p enlarges T1's target, which makes REPLACE prefer evicting T2, feeding
B2 and pulling |B1| - |B2| back toward 0 over subsequent steps. Symmetrically for
B2 hits. The step size shrinks as the SAME-side ghost grows (denominator),
so the system cannot run away in one direction: corrections become smaller exactly
as that side accumulates evidence. Thus Phi is driven toward a bounded equilibrium
band rather than diverging. (This is an intuition, not a worst-case theorem; an
adversary in the online model can still force faults, per the competitive lower
bound below. The point is that under STATIONARY-ish input, p settles.)

Definition (pure scan). A pure scan of length s is a request subsequence
   y_1, y_2, ..., y_s  of DISTINCT pages, none of which appears anywhere else in
   sigma (each is referenced exactly once, ever).

Theorem (Scan resistance of ARC). During a pure scan, no page in T2 immediately
before the scan is evicted, provided |T2| <= c - 1 stays within the c-budget and
the scan does not itself overflow what T1 can absorb under the running p.

Proof.
  Each scan page y_i is, at its single reference, NEW (not in any of the four lists,
  by the distinctness/uniqueness assumption). Hence every y_i triggers Case IV and
  is inserted at MRU of T1; none ever triggers Case I/II/III, so NONE enters T2.
  Eviction during the scan happens only via REPLACE. REPLACE evicts from T1 whenever
       |T1| >= 1 AND |T1| > p           (the typical branch during a scan).
  Because scan pages pile into T1, |T1| grows and stays > p, so REPLACE keeps
  selecting the LRU of T1 -- which is always a scan page (or a pre-scan T1 page),
  NEVER a T2 page. Therefore the contents of T2 are untouched throughout the scan.
  T2 pages are evicted only when REPLACE takes the else-branch, which requires
  |T1| <= p; a pure scan keeps |T1| > p, so that branch is not taken. QED.

A deterministic online paging policy A is k-COMPETITIVE if there is a constant b
such that for every request sequence sigma:
        cost_A(sigma) <= k * cost_OPT(sigma) + b.
The competitive ratio of A is the smallest such k.

Theorem (Sleator & Tarjan, 1985). LRU (and FIFO) is k-competitive, where k = c is
the cache size.

Proof idea (phase partition). Partition sigma into phases: a phase is a maximal
run containing at most c DISTINCT pages; a new phase starts at the first request
to a (c+1)-th distinct page.
  - In any phase, LRU faults at most c times (it can fault at most once per distinct
    page; touching a page makes it MRU so it is not re-evicted within the phase).
  - OPT must fault at least once per phase boundary: across a phase plus the first
    request of the next, c+1 distinct pages are referenced but the cache holds c,
    forcing OPT >= 1 fault attributable to each phase.
  Summing over phases: cost_LRU <= c * cost_OPT + O(1). QED.

Theorem (lower bound). No deterministic online paging policy is better than
c-competitive.

Proof (adversary). Restrict attention to c+1 fixed pages. At each step the adversary
requests the ONE page currently NOT in the online policy's cache. The online policy
faults on EVERY request. OPT, knowing the future, evicts the page used farthest in
the future and faults at most once every c requests. Hence the ratio approaches c.
QED.

Consequence for ARC. ARC is an online, demand-paging, deterministic policy, so it
inherits the SAME asymptotic worst-case guarantee: it is c-competitive, and by the
lower bound it cannot be asymptotically better in the worst case. NO deterministic
online policy can be (worst-case) better than LRU's k = c.

Therefore ARC's advantage is NOT a better worst-case competitive ratio. Its
advantage is on the LARGE CLASS OF REAL WORKLOADS where the worst case does not
occur: ARC distinguishes recency from frequency and resists scans, so on traces
with scans, mixed locality, and phase changes it achieves a hit ratio much closer
to OPT than LRU does -- while matching LRU's worst-case bound. Competitive analysis
(adversarial) is simply too pessimistic to separate good paging policies; the
separation is empirical and distributional, not worst-case.

Definition (stack algorithm / inclusion property). A paging policy has the STACK
property if, for every request sequence and every t, the set of pages a cache of
size c would hold is a SUBSET of what a cache of size c+1 would hold:
        Contents_c(t)  subseteq  Contents_{c+1}(t).

Theorem. LRU is a stack algorithm; therefore LRU is immune to BELADY'S ANOMALY
(more cache never causes more faults). LFU and OPT are also stack algorithms.
FIFO is NOT, and can exhibit the anomaly.

Let:  c = number of cached entries (values),
      v = average bytes per VALUE,
      k = average bytes per KEY (or per directory entry: key + a few pointers/bits),
      h = fixed bookkeeping per entry (list pointers, flags) ~ a small constant.

LRU memory:    M_LRU  = c*(v + k + h)
ARC memory:    M_ARC  = c*(v + k + h)            # T1 U T2 cached entries (data)
                       + |B1 U B2| * (k + h)     # ghosts: KEY ONLY, no value
By invariant I3, |B1| + |B2| <= c, so the ghost term is at most c*(k + h).

OVERHEAD:      M_ARC - M_LRU  <=  c*(k + h).
RELATIVE:      overhead / M_LRU  <=  (k + h) / (v + k + h).

- When values are LARGE relative to keys (v >> k), e.g. 4 KiB or 128 KiB ZFS blocks
  keyed by an 8-byte block id: overhead / M_LRU  ~  k/v  =  8 / 4096  ~  0.2%.
  The ghost directory is essentially free. This is the common storage case.
- When values are SMALL and comparable to keys (v ~ k), e.g. caching short ints
  keyed by long URLs: overhead can approach ~50%, doubling the directory footprint.
  Mitigation: HASH keys to fixed 8-16 byte tokens, restoring v >> k for the ghosts
  (collisions only cost a spurious ghost hit, never a correctness violation).
- Worst case |B1|+|B2| = c is rarely reached on stable workloads; ghosts only fill
  after sustained eviction pressure (I5).

Claim. Every ARC operation (Cases I-IV including REPLACE) costs O(1) WORST CASE,
hence O(1) amortized -- no amortization is even needed.

Proof. With a hash directory mapping key -> (list, node):
  - membership tests (which of T1/T2/B1/B2) : O(1) hash lookups
  - unlink a node from a doubly linked list : O(1)
  - push to MRU / read LRU tail of a list   : O(1)
  - REPLACE: one tail read + one unlink + one push to a ghost + one delete : O(1)
  - p update: two integer ops, one clamp     : O(1)
  - size-management trims: a bounded number (<= a small constant) of tail drops : O(1)
Each case performs a constant number of these. Therefore T(op) = O(1). QED.

Contrast: a naive LFU needs a priority queue (O(log c) per op) unless implemented
with the frequency-bucket doubly-linked-list trick; ARC achieves true O(1)
WITHOUT any heap, because all ordering is by list position, never by a numeric key.

Simplified 2Q with sizes |A1| = a (fixed), |Am| = c - a (fixed) is exactly ARC
with the adaptation DISABLED and p PINNED at a constant a:
        ARC with p := a, forall t, and B1=B2 ignored  ==  fixed-split 2Q-ish policy.

Full 2Q additionally distinguishes A1in (FIFO resident) from A1out (a ghost-like
"out" queue of recently evicted A1 keys). A1out plays the role of B1: a hit in
A1out promotes a key straight to Am. ARC GENERALIZES this by ALSO keeping B2 and,
crucially, by letting the split p MOVE in response to B1-vs-B2 hits instead of
fixing it.

Summary of the generalization:
    LRU          : one list, no notion of "proven".
    2Q (simple)  : two fixed lists; promotion on 2nd access; no adaptation.
    2Q (full)    : adds A1out ghost (= B1); still FIXED split.
    ARC          : adds B2 ghost AND makes the split p ADAPTIVE via ghost feedback.

1. WORST CASE: zero improvement is possible. By the competitive lower bound, an
   adversary makes ANY deterministic policy fault every step. So in the worst case
   ARC's hit ratio equals LRU's (both ~0 vs OPT). No improvement is guaranteed.

2. SCAN MODEL: arbitrarily large improvement is possible. Construct a workload:
   a hot set H of size c-1 reused R times, interleaved with scans S of length s >> c.
   - LRU: each scan evicts H entirely, so after each scan the next |H| reuses MISS.
     LRU faults ~ R * (#scans) * |H| extra times.
   - ARC: H lives in T2, untouched by scans (scan-resistance theorem). H reuses HIT.
     ARC avoids essentially ALL of those extra faults.
   The ratio of LRU faults to ARC faults can be made to grow without bound by
   increasing R and the scan frequency. Hence there is NO constant c' such that
   LRU is c'-competitive against ARC on real-shaped workloads.

3. REALISTIC TRACES (empirical, Megiddo-Modha 2003 and follow-ups): on database,
   file-system, web, and search traces, ARC's hit ratio is consistently a few to
   tens of percentage points above LRU at the same size, and close to offline OPT,
   WITHOUT per-trace tuning.

LFU must order by a NUMERIC frequency count -> a priority queue or bucketed list,
   naive: O(log c) per op; bucket trick: O(1) but with extra structure for ties/aging.

ARC orders ONLY by LIST POSITION (recency within T1/T2, FIFO age within nothing —
   T-lists are LRU). "More frequent" is encoded structurally as "is in T2," not as a
   number to compare. There is NOTHING to sort, so NO heap, and every operation is a
   constant number of pointer splices + hash ops -> O(1) WORST CASE.

Corollary: ARC sidesteps the classic LFU pathologies entirely:
   - no stale high counts pinning once-popular pages (a key in T2 still ages out by
     LRU position),
   - no count overflow, no aging-decay parameter to tune.
ARC captures "frequency" with a single bit of state (T1 vs T2) plus recency order,
which is precisely why it is both O(1) AND tuning-free.