Expand description
Adaptive Replacement Cache (Megiddo + Modha, 2003).
Four lists, total budget c:
T1 - recently-seen-once entries (LRU at the back). T2 - recently-seen-more-than-once entries (LRU at the back). B1 - ghost list of keys recently evicted from T1. B2 - ghost list of keys recently evicted from T2.
|T1| + |T2| <= c. |T1| + |B1| <= c, |T2| + |B2| <= 2c.
The split between T1 and T2 is governed by p (target |T1| size),
which adapts on ghost-list hits: a B1 hit grows p (recency
signal); a B2 hit shrinks p (frequency signal). Scan-resistant
because a one-shot scan only lifts entries into T1 and then evicts
them to B1 without polluting T2.
O(1) per access using a doubly-linked-list-by-index. We allocate a
Node pool keyed by a u32 slot id, and the four “lists” are just
head/tail pointers into that pool. Hashmap on K -> (list_tag, slot_id) for membership lookup.
Structs§
- ArcCache
- Adaptive replacement cache.
K: Hash + Eq + Clone.cis the resident budget; the ghost lists may hold up to anotherckeys combined.