Skip to content

arc.md

Latest commit

 

History

History
126 lines (89 loc) · 3.96 KB

arc.md

File metadata and controls

126 lines (89 loc) · 3.96 KB

ARC (Adaptive Replacement Cache)

Feature: policy-arc

Status

Implemented in src/policy/arc.rs

Goal

Adapt between recency and frequency automatically, without fixed partition tuning.

Core Idea

Maintain four lists:

  • T1: resident, recent (recency)
  • T2: resident, frequent (frequency-ish)
  • B1: ghost history of items evicted from T1
  • B2: ghost history of items evicted from T2

ARC maintains a target parameter p that controls the balance between T1 and T2. Hits in ghost lists adjust p:

  • hit in B1 ⇒ increase p (favor recency list T1)
  • hit in B2 ⇒ decrease p (favor frequency list T2)

Core Data Structures

Production ARC uses:

  • Hash index mapping K -> NonNull<Node>
  • Intrusive doubly-linked lists for T1, T2
  • Ghost lists B1, B2 (keys only, backed by GhostList)

Key Operations (High Level)

Get Operation

  • hit in T1 ⇒ move to T2 head (promote to frequent)
  • hit in T2 ⇒ move within T2 to head (update recency)
  • hit in B1 ⇒ adjust p upward, perform replacement, insert into T2, remove from B1
  • hit in B2 ⇒ adjust p downward, perform replacement, insert into T2, remove from B2
  • miss ⇒ insert into T1 and potentially evict via replacement step

Replacement Step

Chooses victim from T1 vs T2 depending on p and where the last hit occurred:

  • if |T1| >= max(1, p): evict from T1 LRU → move key to B1
  • else: evict from T2 LRU → move key to B2

Adaptation

The parameter p is adjusted based on ghost hits:

  • Ghost hit in B1: increase p by δ = max(1, |B2|/|B1|)
  • Ghost hit in B2: decrease p by δ = max(1, |B1|/|B2|)

This adaptation mechanism allows ARC to automatically favor recency or frequency depending on the workload's characteristics.

Complexity & Overhead

  • O(1) operations (with intrusive lists + hashmap)
  • More metadata than LRU/2Q/SLRU due to ghost lists and adaptivity
  • Ghost lists can hold up to capacity keys each (2× memory overhead in keys)

Example Usage

use cachekit::policy::arc::ArcCore;
use cachekit::traits::CoreCache;

// Create ARC cache with 100 entry capacity
let mut cache = ArcCore::new(100);

// Insert items (go to T1 - recent list)
cache.insert("page1", "content1");
cache.insert("page2", "content2");

// First access promotes to T2 (frequent list)
assert_eq!(cache.get(&"page1"), Some(&"content1"));

// Second access keeps in T2 (MRU position)
assert_eq!(cache.get(&"page1"), Some(&"content1"));

// Check list sizes
println!("T1 len: {}, T2 len: {}", cache.t1_len(), cache.t2_len());
println!("Adaptation parameter p: {}", cache.p_value());

When To Use

  • Mixed workloads with unknown or shifting balance between recency and frequency
  • Adaptive systems where manual tuning is impractical
  • Database buffer pools with varying access patterns
  • File system caches with diverse workload characteristics

When NOT To Use

  • Simple workloads with pure temporal locality (LRU is faster)
  • Memory-constrained systems (ghost lists add overhead)
  • Deterministic requirements (adaptation can make behavior harder to predict)
  • Known workload characteristics (tuned policies like 2Q may be sufficient)

Performance Characteristics

Metric Value
Get O(1)
Insert O(1) amortized
Remove O(1)
Space O(n) entries + O(n) ghost keys
Scan resistance High (via ghost lists)
Adaptivity Self-tuning

Implementation Notes

  • Uses raw pointer intrusive linked lists for T1/T2
  • Ghost lists implemented using cachekit::ds::GhostList
  • Adaptation parameter p starts at capacity / 2
  • Ghost lists are bounded to capacity each
  • Promotion from T1 to T2 on re-access
  • Update in T1 promotes to T2
  • Update in T2 moves to MRU

References