S3-FIFO

Deep dive

How it works

In: a key (and its value on a miss) · Out: hit or miss; the evicted entry · State: small FIFO (10 %), main FIFO (90 %), ghost FIFO of keys, a 2-bit frequency per entry · Cost: O(1) amortized; a hit is one counter bump.

1. Read hit: freq = min(freq + 1, 3). Nothing moves.
2. Miss, insert: if the key is in the ghost queue → insert into main; else → insert into small. freq = 0.
3. Evict (cache full): if small holds ≥ 10 % of capacity, evict from small, else from main.
4. Evict from small: pop the oldest. If it was accessed during its stay (freq ≥ 1), move it to main with freq = 0; otherwise drop the value and push the key into ghost. Repeat until something is actually evicted.
5. Evict from main: pop the oldest. If freq > 0, decrement and reinsert at the tail (second chance); else evict.
6. Ghost is a bounded FIFO of keys; oldest keys fall off.

miss ─► [ small 10% ] ─ oldest, freq≥1 ─► [ main 90% ] ─ oldest, freq>0 ─► back of main (freq-1)
              │ freq=0                          │ freq=0
              ▼                                 ▼
        [ ghost keys ] ─ re-request ─► main    evicted

Code

use std::collections::{HashMap, VecDeque};
use std::hash::Hash;

struct Entry<V> { val: V, freq: u8 }

pub struct S3Fifo<K, V> {
    small: VecDeque<K>, main: VecDeque<K>,
    ghost: VecDeque<(K, u64)>, ghost_map: HashMap<K, u64>, ghost_seq: u64,
    map: HashMap<K, Entry<V>>,
    cap: usize, small_cap: usize,
}

impl<K: Hash + Eq + Clone, V> S3Fifo<K, V> {
    pub fn new(cap: usize) -> Self {
        assert!(cap >= 2);
        S3Fifo { small: VecDeque::new(), main: VecDeque::new(), ghost: VecDeque::new(),
                 ghost_map: HashMap::new(), ghost_seq: 0, map: HashMap::with_capacity(cap),
                 cap, small_cap: (cap / 10).max(1) }
    }

    pub fn get(&mut self, k: &K) -> Option<&V> {
        let e = self.map.get_mut(k)?;
        e.freq = (e.freq + 1).min(3);          // the only work on a hit
        Some(&e.val)
    }

    pub fn insert(&mut self, k: K, v: V) {
        if let Some(e) = self.map.get_mut(&k) { e.val = v; e.freq = (e.freq + 1).min(3); return; }
        while self.map.len() >= self.cap { self.evict(); }
        if self.ghost_map.remove(&k).is_some() { self.main.push_back(k.clone()); }
        else { self.small.push_back(k.clone()); }
        self.map.insert(k, Entry { val: v, freq: 0 });
    }

    fn evict(&mut self) {
        loop {
            if self.small.len() >= self.small_cap || self.main.is_empty() {
                let k = self.small.pop_front().expect("cache full implies non-empty queue");
                let e = self.map.get_mut(&k).unwrap();
                if e.freq >= 1 {               // reused during its trial: promote
                    e.freq = 0;
                    self.main.push_back(k);
                    continue;
                }
                self.map.remove(&k);
                self.push_ghost(k);
                return;
            }
            let k = self.main.pop_front().unwrap();
            let e = self.map.get_mut(&k).unwrap();
            if e.freq > 0 { e.freq -= 1; self.main.push_back(k); continue; } // second chance
            self.map.remove(&k);
            return;
        }
    }

    fn push_ghost(&mut self, k: K) {
        self.ghost_seq += 1;
        self.ghost_map.insert(k.clone(), self.ghost_seq);
        self.ghost.push_back((k, self.ghost_seq));
        let ghost_cap = self.cap - self.small_cap;
        while self.ghost_map.len() > ghost_cap {
            let (old, seq) = self.ghost.pop_front().unwrap();
            // Skip stale queue entries (key re-admitted or re-ghosted since).
            if self.ghost_map.get(&old) == Some(&seq) { self.ghost_map.remove(&old); }
        }
        // Bound stale entries too: drop leading ones that no longer match the map.
        while let Some((front, seq)) = self.ghost.front() {
            if self.ghost_map.get(front) == Some(seq) { break; }
            self.ghost.pop_front();
        }
    }
}

fn main() {
    let mut c = S3Fifo::new(100);
    for i in 0..10_000u32 {
        let k = if i % 2 == 0 { i % 50 } else { 1_000 + i }; // hot set + one-hit wonders
        if c.get(&k).is_none() { c.insert(k, ()); }
    }
    let hot = (0..50u32).filter(|k| c.get(k).is_some()).count();
    println!("hot keys resident: {hot}/50");                 // one-hit wonders don't flush them
}

The promotion threshold (freq ≥ 1, i.e. one hit during the trial) is a tunable; some implementations require two.

Complexity and constants

• Hit: one hash lookup + a counter bump. In a concurrent implementation that is an atomic on the entry, no shared list touched.
• Miss: O(1) amortized; each object moves small → main at most once and is reinserted in main at most 3 times per pass.
• Metadata: 2 bits of frequency + queue slot (8 B pointer/index in a ring) per object; ghost ≈ one hashed key (8-16 B) per main slot. Storing ghost entries as fingerprints in a hash table keeps it near 4-8 B each.
• Queues can be fixed-size ring buffers: no allocation, cache-friendly, and lock-free MPMC variants exist (ring buffers).

Efficiency

• Cost: A hit is a hash lookup plus a 2-bit counter increment (an atomic in a concurrent cache); no list is touched. Metadata is 2 bits plus an 8 B queue slot per object, and ghost keys take about 4-8 B each as fingerprints (order of). On 6,594 traces the paper reports lower miss ratios than LRU and about 6× LRU's throughput at 16 threads. The bound is hash-table memory latency.
• Levers:
  • 10 % small queue (quick demotion) — one-hit wonders leave early (SOSP 2023) — traces with many one-hit wonders.
  • Ghost as 32-bit fingerprints — 4-8 B per ghost entry instead of a full key — large caches.
  • Fixed-size ring buffers for the queues — no allocation, cache-friendly — in-memory caches.
  • Byte-weighted queue budgets — correct 10 %/90 % split — variable-size objects.
  • Single consumer evicts, hits are atomics — no read buffers or replay, unlike LRU designs — many threads.
• Naive → standard → state of the art:
  • Global-lock LRU · a list write per hit.
  • Sharded LRU with hit buffers · batched replay, more machinery.
  • S3-FIFO (SIEVE: one FIFO and a hand) · counter bump per hit, about 6× LRU throughput at 16 threads.

Implementation notes

• Small queue size: 10 % is the paper's default and works well across its traces; tune it on your own trace if you can replay one.
• Charge by bytes for variable-size objects: compare queue byte sizes against 10 %/90 % budgets.
• Ghost as a hash of 32-bit fingerprints with insertion timestamps lets you expire entries by "age > main size" without a separate queue.
• Concurrency: insertion appends to a ring; eviction is a single consumer (or small batch under a lock); hits are atomics. No read buffer or replay needed, unlike LRU-based designs.
• SIEVE (same group) is an even simpler single-FIFO variant: a hand moves from tail to head, retaining visited objects in place.

Pitfalls

• Promoting on insertion instead of on observed reuse: defeats quick demotion.
• Unbounded ghost queue (stale entries never trimmed): memory leak proportional to churn.
• Very small caches (tens of entries): 10 % small queue is one or two slots; use LRU.
• Loop/scan patterns slightly larger than main can thrash both FIFO and LRU; neither fixes them.

Variants and alternatives

In production

Cloudflare Pingora's TinyUFO (S3-FIFO queues with TinyLFU admission), foyer (Rust hybrid cache, S3-FIFO eviction option), quick_cache (Rust, S3-FIFO policy); the paper evaluates CDN, key-value and block-storage traces; libCacheSim (the authors' simulator) has reference implementations.

Implementations

Sources

• Juncheng Yang, Yazhuo Zhang, Ziyue Qiu, Yao Yue, Rashmi Vinayak, FIFO Queues are All You Need for Cache Eviction, SOSP 2023. paper · code · site
• Yazhuo Zhang, Juncheng Yang, Yao Yue, Ymir Vigfusson, K. V. Rashmi, SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches, NSDI 2024. paper
• Theodore Johnson, Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, VLDB 1994. paper