# 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
