Expand description
An implementation of the Adaptive Replacement Cache (ARC) eviction policy.
ARC is a cache replacement policy that adaptively balances between LRU (recency) and LFU (frequency). It maintains four lists:
- T1: Pages accessed exactly once recently (the “recency” list).
- T2: Pages accessed more than once recently (the “frequency” list).
- B1: A “ghost list” of pages recently evicted from T1.
- B2: A “ghost list” of pages recently evicted from T2.
The algorithm adjusts a parameter p which represents the target size of T1,
thereby dynamically changing the balance between recency and frequency focus.
This implementation is adapted for variable-sized items by tracking bytes instead
of a fixed number of pages.
This implementation is lock-free, using a concurrent doubly-linked list and concurrent hash maps to allow multiple threads to access it without blocking.
Structs§
- ArcManager
- Manages the state for the ARC eviction policy.