# CLOCK-Pro
**Feature:** `policy-clock-pro`
## Goal
Improve Clock's scan behavior by tracking hot/cold classification and ghost entries using Clock-style hands.
## Core Idea
Maintain three conceptual groups:
- **Hot pages**: protected from eviction, frequently accessed
- **Cold pages**: resident but candidates for eviction
- **Ghost entries**: keys only, recently evicted cold pages (enables re-access detection)
Clock hands circulate and adjust status; sequential scans churn through cold pages rather than evicting hot pages.
## Core Data Structures
Implementation uses:
- `index: FxHashMap<K, usize>` mapping keys to slot index in entries buffer
- `entries: Vec<Option<Entry<K, V>>>` circular buffer of resident pages
- Each entry has: `key`, `value`, `status` (Hot/Cold), `referenced` bit
- `ghost: Vec<Option<GhostEntry<K>>>` circular buffer of ghost keys
- `ghost_index: FxHashMap<K, usize>` for O(1) ghost lookup
- Three clock hands:
- `hand_cold`: sweeps for cold page eviction
- `hand_hot`: sweeps for hot page demotion (used inline during eviction)
- `ghost_hand`: position for next ghost insertion
- `target_hot_ratio`: adaptive ratio (starts at 0.5, increases on ghost hits)
## Operations
- `get(key)`:
- If resident: set `referenced = true`, return value
- If in ghost: return miss (but next insert of this key → hot)
- Otherwise: return miss
- `insert(key, value)`:
- If key exists: update value, set `referenced = true`
- If key was in ghost: remove from ghost, insert as HOT
- Otherwise: insert as COLD
- If at capacity: run eviction
- `evict()`:
- Sweep with `hand_cold`:
- Cold + unreferenced → evict, add key to ghost ring
- Cold + referenced → promote to Hot, clear referenced
- Hot (if over `max_hot` limit) → demote to Cold or clear referenced
- Fallback: force evict at current hand position if stuck
## Scan Resistance
Clock-PRO resists scan pollution because:
1. New inserts start as cold (sequential scans only touch cold pages)
2. Cold pages need a second access to become hot
3. Hot pages are protected from eviction
4. Ghost hits boost re-accessed keys directly to hot status
## Complexity & Overhead
| `get` | O(1) | Hash lookup + bit operation |
| `insert` | O(1)* | *Amortized; eviction may sweep |
| `contains` | O(1) | Hash lookup only |
| `remove` | O(1) | Hash lookup + clear slot |
- Memory overhead: entries buffer + ghost buffer + two hash indexes
- Ghost capacity is configurable (default = resident capacity)
## Thread Safety
- `ClockProCache`: Not thread-safe, designed for single-threaded use
- For concurrent access, wrap in external synchronization
## References
- Jiang, Chen, Zhang (2005): "CLOCK-Pro: An Effective Improvement of the CLOCK Replacement"
- Wikipedia: https://en.wikipedia.org/wiki/CLOCK-Pro