Expand description
W-TinyLFU admission policy (Einziger, Friedman + Manes, ACM TOS 13(4), 2017).
Cache is split into:
Window (1% of capacity) - small LRU. New keys enter here. Main protected (80% of main) - LRU; the popular working set. Main probation (20% of main) - LRU; recent demotees + recent admits.
When the Window evicts an entry, that entry becomes a CANDIDATE. The candidate fights for admission against Main probation’s LRU VICTIM. We consult a count-min sketch (CMS) of recent access frequencies and admit the candidate iff its frequency >= victim’s frequency.
Doorkeeper: a small bloom filter that filters out “seen exactly once” candidates before they ever touch the CMS. Reduces sketch pressure.
CMS uses a periodic “aging” pass: every sample_size = 10*c
accesses, all counters halve. This bounds the influence of stale
popularity bursts.
The CMS implementation lives in this file rather than depending on
the sibling subms-count-min-sketch recipe. Reason: the cache is
a leaf in the dep graph; pulling in a sibling recipe would create
a cyclic-refresh risk on per-recipe releases and force consumers to
pull two crates for one feature. The local CMS is 4 rows of 32-bit
counters keyed by FNV-1a + linear probing, sized to 4 * c counters.
Structs§
- Tiny
LfuCache - W-TinyLFU cache.