Module two_queue 

2Q (two-queue) eviction policy — a scan-resistant alternative to LRU.

The 2Q algorithm maintains three queues:

Queue	Purpose
A1in	FIFO buffer for recently inserted items (first access)
A1out	Ghost queue: tracks keys recently evicted from A1in
Am	LRU queue for items accessed at least twice (promoted from A1in or A1out hit)

On a cache miss:

• If the key is in A1out (ghost hit), it is admitted directly to Am.
• Otherwise it enters A1in.

On a cache hit:

• If in Am, the entry is moved to the MRU position of Am.
• If in A1in, no promotion happens yet (FIFO within A1in).

This prevents sequential scans from polluting the long-term cache (Am).

Reference

Theodore Johnson and Dennis Shasha, “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm,” VLDB 1994.

Structs

TwoQueueCache

A 2Q cache with configurable total capacity and A1in/A1out sizing.

TwoQueueStats

Snapshot of 2Q cache statistics.