# 2Q
**Feature:** `policy-two-q`
## Goal
Reduce scan pollution with a simple two-queue design that approximates "access twice before protection".
## Core Idea
Maintain:
- `A1` (in): FIFO queue for newly admitted items (probation)
- `Am`: LRU queue for items that were accessed again (protected/main)
Behavior:
- New items go to `A1`.
- If an item in `A1` is accessed again, it moves to `Am`.
- Eviction prefers `A1` (discard one-hit-wonders) before evicting from `Am`.
## Core Data Structures
Common implementation:
- `HashMap<K, NodePtr>` mapping keys to node pointers
- Two doubly-linked lists:
- FIFO list for `A1` (newest at front, oldest at back)
- LRU list for `Am` (MRU at front, LRU at back)
Optional (from the original paper):
- `A1out`: "ghost" history of recently evicted `A1` items to inform admission/tuning (see `TwoQWithGhost`)
## Operations
- `insert`: into `A1` front (new items enter; oldest at back for eviction)
- `get`:
- if in `A1`: promote to `Am` front (MRU position)
- if in `Am`: move to `Am` front (MRU position)
- `evict`:
- if `A1` exceeds its target size: evict from `A1` back (oldest)
- otherwise: evict from `Am` back (LRU)
- fallback: evict from `A1` even if under cap when `Am` is empty
## Complexity & Overhead
- O(1) operations with doubly-linked lists + hashmap index
- Requires tuning partition sizes (`|A1|` vs `|Am|`) via `a1_frac` parameter
## References
- Johnson, Shasha (1994): "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm".
- Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies