two-queue-replacement · research · also 2Q, Two Queue, two-queue replacement

2Q replacement

2Q is a buffer replacement policy that uses FIFO admission, an LRU main queue and nonresident history to distinguish bursts from longer-term reuse.

In the full version, an A1in resident hit leaves its FIFO position and membership unchanged. The simplified version instead promotes that hit to Am. For read requests, an A1out history hit still requires a data read before admission to Am, whose resident hits refresh LRU order. If history expires first, a later request enters A1in again. [1]

Allocation: free slots can fill A1in beyond Kin. At full capacity, the original reclaim pseudocode evicts from A1in only when its length is strictly greater than Kin; otherwise it evicts from Am. Kin is a replacement threshold, not a permanently reserved partition. [1]

History lifetime: A1out ages when A1in evictions append identifiers, not once per request or after a wall-clock timeout. Resident hits do not advance that FIFO; Am evictions do not enter it. This event-driven filter can change its effective admission horizon without changing Kin or Kout. [1]

Queue-size choices can affect miss ratios. Later miniature-simulation work varied history capacity separately from resident capacity and observed workload-dependent gains and regressions from adaptation. Fixed percentages are not universal optima. [2]

Evidence scope: the 2017 tuning study used eight miniature simulations with sampling rate R=0.005 and Kin fixed at 25%. It selected Kout between 50% and 300% after each million references. Its miss-ratio gains and losses across cache sizes are not measurements of application latency. [2]

Worked example: with four slots, Kin=1 and Kout=2, reads A B C D A E A produce one resident hit in full 2Q and two in the simplified variant. The difference follows from whether the fifth request protects A before E arrives, not from faster storage. [3]

Relations

related

Cache pollution, Ghost cache entry, Cache admission

Limitations

• The original policy does not adjust its queue-size parameters automatically as the workload changes. [2]
• Ghost identifiers consume metadata memory even though their page payloads are absent. [2]
• More history need not reduce misses: with three resident slots and Kin=1, reads A B C D A E B C A need eight backing reads at Kout=1 but nine at Kout=2. This constructed counterexample does not measure workload frequency or device latency. [7]
• Comparisons at fixed resident capacity but different history sizes do not hold total memory use constant; ghost metadata also needs a budget. [2]

Citations

1. Theodore Johnson and Dennis Shasha. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. VLDB 1994, pp. 439-450, sections 2 and 4.1. (accessed 2026-10-31)
2. Waldspurger, Saemundsson, Ahmad and Park. Cache Modeling and Optimization using Miniature Simulations. USENIX ATC 2017, sections 2 and 4.2. (accessed 2026-10-31)
3. Hesela: seven-request 2Q admission example, method and limitations (accessed 2026-10-31)
7. Hesela: why larger 2Q history can increase reads, method and hand-traced transitions (accessed 2026-10-31)

Further reading

4. Hesela: read-only 2Q worked-example source (accessed 2026-10-31)
5. Hesela: worked-example regression tests (accessed 2026-10-31)
6. Hesela: exact full and simplified 2Q decision snapshots (accessed 2026-10-31)
8. Hesela: exact nine-request history-budget counterexample (accessed 2026-10-31)
9. Hesela: hand-traced history-budget transition tests (accessed 2026-10-31)

JSON: /data/terms/two-queue-replacement.json