# LRU-K

**Feature:** `policy-lru-k`

## Goal
Improve scan resistance by evicting based on the K-th most recent access time, rather than last access time.

## Core Idea
Track the last `K` access timestamps for each key.
- If an entry has fewer than `K` accesses, treat it as “cold/probation”.
- Evict cold entries first (they haven’t demonstrated reuse).
- Otherwise, evict the entry with the oldest K-th most recent access (largest backward K-distance).

In `cachekit`, LRU-K is implemented in `src/policy/lru_k.rs` with segmented tracking for `< K` and `>= K` entries.

## Core Data Structures
Common LRU-K:
- `HashMap<K, EntryMeta>` where `EntryMeta` holds:
  - ring buffer / `VecDeque<u64>` of timestamps (size K)
  - membership in cold/hot segments (optional optimization)
- A store for values (often `HashMap<K, V>` or separate arena)

For efficient victim selection, many implementations maintain:
- Separate candidate structures for cold vs hot
- LRU ordering among cold entries (by first access) and among hot entries (by K-distance)

## Operations

### `touch/get(key)`
- Push current timestamp into the key’s history (keep only last K).
- If history length reaches K: promote to hot segment.
- Update segment ordering based on chosen tie-break rules.

### `pop_lru_k()`
Eviction priority:
1. any entry with `< K` accesses (cold): evict oldest by first access time
2. otherwise: evict the entry with the oldest K-distance (K-th most recent access is oldest)

## Complexity & Overhead
- More metadata than LRU: needs K timestamps per entry (or compressed form).
- Hot-path updates are heavier than LRU; keep operations O(1) by using small fixed K and fixed-size buffers.

## References
- O’Neil, O’Neil, Weikum (1993): “The LRU-K page replacement algorithm for database disk buffering”.
- Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies
