# LFU (Least Frequently Used)
**Feature:** `policy-lfu`
## Goal
Evict the entry with the lowest access frequency; break ties by recency (common) or arbitrarily.
## Common Production Approach: Bucketed LFU (O(1))
The typical O(1) LFU design is:
- `HashMap<K, EntryId>` to locate entries
- Per-entry metadata: `freq`, plus pointers for an intrusive list inside its frequency bucket
- `HashMap<freq, BucketList>` (or `Vec<BucketList>` with bounded freq) storing LRU order within each frequency
- `min_freq` tracking the smallest frequency currently present
In `cachekit`, `src/policy/lfu.rs` implements LFU with O(1) eviction based on bucket + `min_freq`.
## Operations
### `get(key)`
- Return value and increment its frequency:
1. Remove entry from old frequency bucket list.
2. Increment `freq`.
3. Insert into new bucket list (typically at head as MRU within that freq).
4. If old bucket becomes empty and was `min_freq`, increment `min_freq`.
### `insert(key, value)`
- If present: update value and treat as an access (commonly increment frequency).
- Else:
- If full: evict from `min_freq` bucket (usually the LRU within that bucket).
- Insert new entry with `freq = 1` and set `min_freq = 1`.
### `pop_lfu()`
- Pop from the `min_freq` bucket; if it becomes empty, advance `min_freq`.
## Complexity & Overhead
- Lookup: O(1)
- Frequency bump: O(1)
- Eviction: O(1)
- Metadata: higher than LRU/FIFO due to frequency buckets and per-entry freq
## Aging / Decay (Important)
Pure LFU can keep “once-hot” items forever. To avoid this, add one of:
- Periodic global decay: divide all frequencies by 2 each interval (O(n) unless amortized)
- Time-decayed score: maintain `score = freq / f(age)` (more complex)
- Windowed LFU: only count accesses in a moving time window
See `lfu-aging.md` for common patterns.
## References
- Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies