s3-fifo · research · also S3FIFO, S3 FIFO

S3-FIFO

S3-FIFO is a cache replacement policy that combines small and main resident FIFO queues with a nonresident ghost queue.

Related Observatory article: S3-FIFO on hesela.com

The small queue tests newly fetched objects before main-queue retention. Ghost entries retain identity, not payload: a ghost match is still a miss, but directs the fetched object to main. Hits update access counters without moving objects immediately. [1]

The paper starts counters at zero and caps them at three. Small-to-main promotion requires two hits after insertion; main reinsertion needs one and spends a counter credit. The prose resets the counter on promotion, although that reset is absent from the corresponding pseudocode branch. [1]

Quick demotion limits the time unpromising objects occupy probationary space; lazy promotion postpones ordering work until eviction. These mechanisms explain why a FIFO-based design is not equivalent to plain FIFO replacement. They do not establish a universal miss-ratio advantage over LRU. [2]

Implementation boundary: in the pinned author simulator, S3FIFO_can_insert accepts an object whose size equals the small queue's capacity, but the non-ghost branch of S3FIFO_insert rejects sizes greater than or equal to that capacity. A size check passing therefore does not guarantee insertion. This boundary belongs to that pinned implementation, not every S3-FIFO library. [3]

The linked transition examples distinguish promotion, ghost routing and bounded main-queue eviction work. They are constructed policy examples, not cache-trace measurements. [4]

Relations

related

First-in first-out cache replacement, Cache admission, Ghost cache entry, 2Q replacement, SIEVE cache eviction, TinyLFU

Limitations

• Objects reused only after leaving the small queue can miss on their second request; short probation is workload-dependent. A ring-buffer implementation can also leave deleted slots unavailable until eviction reaches them. [1]

Citations

1. Yang, Zhang, Qiu, Yue and Rashmi. FIFO Queues are All You Need for Cache Eviction. SOSP 2023, sections 4.1-4.2 and 5.2; DOI 10.1145/3600006.3613147. (accessed 2026-11-07)
2. Yang et al. FIFO can be Better than LRU: the Power of Lazy Promotion and Quick Demotion. HotOS 2023, sections 2-3; DOI 10.1145/3593856.3595887. (accessed 2026-11-07)
3. Author artifact S3FIFO.c, pinned commit 6bc49d9630572721b41cd08adfa982775f3cb1de: S3FIFO_can_insert and S3FIFO_insert. (accessed 2026-11-07)
4. Hesela: existing S3-FIFO transition method, assumptions and executable examples. (accessed 2026-11-07)

JSON: /data/terms/s3-fifo.json