s3fifo-cache 0.1.0

S3-FIFO cache eviction algorithm (SOSP 2023 Best Paper)

s3fifo

A pure-Python implementation of the S3-FIFO cache eviction algorithm from the SOSP 2023 Best Paper Award winner.

---

Python has functools.lru_cache and a dozen LRU/LFU libraries. None of them implement S3-FIFO — an algorithm published in 2023 that outperforms LRU, ARC, and TinyLFU on real-world traces while being simpler than all of them.

This library fills that gap.

---

Contents

• What is S3-FIFO?
• Installation
• Quickstart
• Usage Guide
  • Basic API
  • Dict-style interface
  • Statistics
  • Tuning parameters
  • Thread safety
• Benchmark Results
  • Running the benchmark
• Algorithm Overview
• Project Structure
• Running Tests
• Citation

---

What is S3-FIFO?

S3-FIFO (Simple, Scalable, Skew-aware FIFO) is a cache eviction policy introduced in:

Juncheng Yang, Yazhuo Zhang, Ziyue Qiu, Yao Yue, K.V. Rashmi. "FIFO Queues are All You Need for Cache Eviction." 29th ACM Symposium on Operating Systems Principles (SOSP), 2023. 🏆 Best Paper Award. https://dl.acm.org/doi/10.1145/3600006.3613147

The core insight: three plain FIFO queues are sufficient to achieve near-optimal hit ratios — no doubly-linked lists, no per-entry timestamps, no lock contention from pointer manipulation.

Why it beats LRU:

Property	LRU	S3-FIFO
Eviction data structure	Doubly-linked list	Three deques
Per-operation complexity	O(1) with locks	O(1) amortized, lock-free
Handles one-hit wonders	✗ pollutes cache	✓ filtered by Small queue
Scan resistance	✗ full cache eviction	✓ Ghost set re-routes
Hit rate on skewed traces	Baseline	+6–10 pp better

---

Installation

# From PyPI (once published)
pip install s3fifo

# From source
git clone https://github.com/gitSouvik/s3fifo
cd s3fifo
pip install -e .

Zero runtime dependencies. Pure Python 3.9+, stdlib only.

Optional, for benchmarking charts:

pip install matplotlib

---

Quickstart

from s3fifo import Cache

cache = Cache(capacity=1000)

cache.put("user:123", {"name": "Alice", "age": 30})
cache.put("session:abc", "token_data")

val  = cache.get("user:123")   # → {"name": "Alice", "age": 30}
miss = cache.get("user:999")   # → None  (not in cache)

stats = cache.stats()
print(f"Hit rate: {stats.hit_rate:.2%}")   # Hit rate: 50.00%
print(f"Entries:  {len(cache)}")           # Entries:  2

---

Usage Guide

Basic API

from s3fifo import Cache

cache = Cache(capacity=500)

# ── Write ──────────────────────────────────────────────────────────────
cache.put("key", "value")            # insert new entry
cache.put("key", "updated_value")    # update existing (freq++)

# ── Read ───────────────────────────────────────────────────────────────
val = cache.get("key")               # returns value, or None on miss
                                     # increments entry's frequency on hit

# ── Membership ─────────────────────────────────────────────────────────
"key" in cache                       # True / False — does NOT affect freq
len(cache)                           # current number of cached entries

# ── Maintenance ────────────────────────────────────────────────────────
cache.clear()                        # remove all entries, reset stats
cache.reset_stats()                  # zero hit/miss counters only

Storing None as a value

get() returns None both for cache misses and for entries whose value is None. Use __contains__ or __getitem__ to distinguish:

cache.put("nil_value", None)

# Ambiguous — could be a miss or a stored None:
result = cache.get("nil_value")      # → None

# Unambiguous alternatives:
"nil_value" in cache                 # → True
cache["nil_value"]                   # → None (no KeyError = it's a hit)

---

Dict-style interface

cache = Cache(capacity=100)

cache["product:7"] = {"price": 9.99, "stock": 42}   # same as put()
item = cache["product:7"]                             # same as get(), but raises
                                                      # KeyError on miss

try:
    _ = cache["product:99"]
except KeyError:
    print("not cached")

---

Statistics

from s3fifo import Cache

cache = Cache(capacity=1000)

# ... do some work ...
for key in my_keys:
    if cache.get(key) is None:
        cache.put(key, fetch_from_db(key))

stats = cache.stats()
print(stats)
# Stats(hit_rate=73.41%, hits=7341, misses=2659, total=10000,
#       small=100, main=900, ghost=312)

print(f"Hit rate  : {stats.hit_rate:.2%}")
print(f"Hits      : {stats.hits}")
print(f"Misses    : {stats.misses}")
print(f"In Small  : {stats.small_size}")
print(f"In Main   : {stats.main_size}")
print(f"In Ghost  : {stats.ghost_size}")

# Zero counters between measurement windows:
cache.reset_stats()

---

Tuning parameters

Cache(
    capacity   = 1000,   # total entries (required)
    small_ratio = 0.10,  # Small queue fraction; paper recommends 10%
    ghost_ratio = 1.0,   # ghost capacity = ghost_ratio × capacity
    max_freq    = 3,     # frequency cap per entry (paper uses 3)
)

small_ratio — The paper found 10 % optimal across many real-world traces. Increase it if your workload has very many one-hit wonders; decrease it if almost all accesses are repeated.

ghost_ratio — Ghost entries are just keys (no values), so they're cheap. A ratio of 1.0 means ghost capacity = full cache capacity. Increase for workloads with large working sets and repeated reuse patterns.

max_freq — Higher values make hot objects stickier in Main. The paper uses 3. Rarely needs changing.

---

Thread safety

Cache is not thread-safe. For concurrent access, wrap it:

import threading
from s3fifo import Cache

class ThreadSafeCache:
    def __init__(self, capacity: int):
        self._cache = Cache(capacity)
        self._lock  = threading.Lock()

    def get(self, key):
        with self._lock:
            return self._cache.get(key)

    def put(self, key, value):
        with self._lock:
            self._cache.put(key, value)

For high-concurrency production use, shard across multiple Cache instances (hash key → shard index) to minimise lock contention — exactly the approach the paper recommends for systems-level implementations.

---

Benchmark Results

All numbers below are from benchmarks/benchmark.py running on:

• 10,000 unique keys, 500,000 requests
• Zipf-distributed access trace (models real CDN/web workloads)
• Warmup: first 10 % of trace (not counted in hit rate)

Zipf α = 0.7 (moderately skewed)

Cache size	S3-FIFO	LRU	Δ (pp)
1% (100)	18.62%	8.42%	+10.20
2% (200)	24.07%	13.34%	+10.73
5% (500)	33.24%	22.71%	+10.53
10% (1,000)	42.11%	32.86%	+9.26
20% (2,000)	53.32%	46.67%	+6.66

Average advantage: +9.47 pp

Zipf α = 0.9

Cache size	S3-FIFO	LRU	Δ (pp)
1% (100)	38.27%	26.07%	+12.20
2% (200)	45.18%	33.80%	+11.39
5% (500)	55.08%	45.36%	+9.71
10% (1,000)	63.18%	55.43%	+7.75
20% (2,000)	72.06%	66.98%	+5.07

Average advantage: +9.22 pp

Zipf α = 1.1 (highly skewed, e.g. web traffic)

Cache size	S3-FIFO	LRU	Δ (pp)
1% (100)	62.35%	52.75%	+9.60
2% (200)	68.89%	60.78%	+8.12
5% (500)	76.72%	70.74%	+5.98
10% (1,000)	82.22%	77.94%	+4.28
20% (2,000)	87.38%	84.81%	+2.57

Average advantage: +6.11 pp

The advantage is largest at small cache sizes — exactly where eviction policy matters most in real deployments.

---

Running the benchmark

# Default: Zipf α ∈ {0.7, 0.9, 1.1}, 10k keys, 500k requests
python -m benchmarks.benchmark

# Custom working set and request count
python -m benchmarks.benchmark --n-unique 50000 --n-requests 2000000

# Single alpha value
python -m benchmarks.benchmark --alpha 1.0

# Sequential scan workload (LRU's worst case)
python -m benchmarks.benchmark --trace scan

# Custom cache size fractions
python -m benchmarks.benchmark --sizes 0.01 --sizes 0.05 --sizes 0.10

# Save chart (requires matplotlib)
pip install matplotlib
python -m benchmarks.benchmark   # benchmark_results.png written automatically

---

Algorithm Overview

See ALGORITHM.md for a deep-dive with diagrams.

The short version:

              ┌─────────────────────────────────────────────┐
              │              Cache (capacity N)              │
              │                                             │
  new key ───►│  Small (~0.1N) ──freq>0──► Main (~0.9N)   │
  in ghost ──►│               └──freq=0──► Ghost (≤N)      │
              │                                             │
              │  Main eviction:  freq>0 → reinsert (head)  │
              │                  freq=0 → gone              │
              └─────────────────────────────────────────────┘

1. Every new object enters Small. Small acts as a probationary filter.
2. When Small is full (FIFO eviction of tail):
   • freq > 0 (accessed at least once since insertion) → graduate to Main.
   • freq = 0 (one-hit wonder) → evict; remember key in Ghost.
3. When Main is full (FIFO eviction of tail):
   • freq > 0 → second-chance: reinsert at head with freq − 1.
   • freq = 0 → fully evict. No Ghost entry.
4. If an incoming key is in Ghost → skip Small, insert directly into Main. Ghost tells us "this was already filtered once; it deserves a second chance."

All operations are O(1) amortised: each entry's frequency can be decremented at most max_freq times across its entire lifetime in Main.

---

Project Structure

s3fifo/
├── s3fifo/
│   ├── __init__.py        # Public exports: Cache, Stats, BoundedGhost
│   ├── cache.py           # Cache — the main implementation (~180 lines)
│   ├── _entry.py          # Entry dataclass (key, value, freq)
│   └── _ghost.py          # BoundedGhost — O(1) FIFO key set
├── benchmarks/
│   ├── benchmark.py       # S3-FIFO vs LRU comparison script
│   ├── lru.py             # LRU reference implementation
│   └── traces.py          # Zipf, uniform, and scan trace generators
├── tests/
│   ├── test_cache.py      # 48 tests covering all Cache behaviour
│   └── test_ghost.py      # 16 tests covering BoundedGhost
├── ALGORITHM.md           # Deep-dive: proofs, diagrams, design decisions
├── pyproject.toml         # Packaging metadata
└── README.md              # This file

---

Running Tests

pip install pytest
pytest tests/ -v
# 64 passed in ~0.2s

With coverage:

pip install pytest-cov
pytest tests/ --cov=s3fifo --cov-report=term-missing

---

Citation

If you use this library in research or want to credit the original algorithm:

@inproceedings{yang2023s3fifo,
  title     = {{FIFO} Queues are All You Need for Cache Eviction},
  author    = {Yang, Juncheng and Zhang, Yazhuo and Qiu, Ziyue and
               Yue, Yao and Rashmi, K.V.},
  booktitle = {Proceedings of the 29th ACM Symposium on Operating
               Systems Principles (SOSP '23)},
  year      = {2023},
  doi       = {10.1145/3600006.3613147}
}

---

License

MIT © 2024