2q.md

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