# 2Q
## 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, EntryMeta>` where `EntryMeta` includes which queue it’s in and list pointers
- Two intrusive lists:
- FIFO list for `A1`
- LRU list for `Am`
Optional (from the original paper):
- `A1out`: “ghost” history of recently evicted `A1` items to inform admission/tuning
## Operations
- `insert`: into `A1` (FIFO tail)
- `get`:
- if in `A1`: move to `Am` (LRU head)
- if in `Am`: move to `Am` head
- `evict`:
- evict from `A1` if it exceeds its target size; otherwise evict from `Am`
## Complexity & Overhead
- O(1) operations with intrusive lists + hashmap index
- Requires tuning partition sizes (`|A1|` vs `|Am|`)
## References
- Johnson, Shasha (1994): “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm”.
- Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies