# 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
```rust
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
| 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
- Megiddo, Modha (2003): "ARC: A Self-Tuning, Low Overhead Replacement Cache", FAST 2003.
- Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies#Adaptive_replacement_cache_(ARC)