Metadata-Version: 2.4
Name: s3fifo-cache
Version: 0.1.0
Summary: S3-FIFO cache eviction algorithm (SOSP 2023 Best Paper)
Author: gitSouvik
License-Expression: MIT
Project-URL: Homepage, https://github.com/gitSouvik/s3fifo
Project-URL: Repository, https://github.com/gitSouvik/s3fifo
Project-URL: Bug Tracker, https://github.com/gitSouvik/s3fifo/issues
Project-URL: Changelog, https://github.com/gitSouvik/s3fifo/releases
Project-URL: Paper, https://dl.acm.org/doi/10.1145/3600006.3613147
Keywords: cache,s3fifo,eviction,lru,fifo,algorithms
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Classifier: Topic :: System :: Distributed Computing
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Provides-Extra: benchmark
Requires-Dist: matplotlib>=3.7; extra == "benchmark"
Provides-Extra: dev
Requires-Dist: pytest>=7.0; extra == "dev"
Requires-Dist: pytest-cov>=4.0; extra == "dev"
Dynamic: license-file

# s3fifo

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

[![Python 3.9+](https://img.shields.io/badge/python-3.9%2B-blue.svg)](https://www.python.org/downloads/)
[![License: MIT](https://img.shields.io/badge/license-MIT-yellow.svg)](LICENSE)
[![Tests](https://img.shields.io/badge/tests-64%20passed-brightgreen.svg)](#running-tests)
[![Zero dependencies](https://img.shields.io/badge/dependencies-none-brightgreen.svg)](#installation)

---

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?](#what-is-s3-fifo)
- [Installation](#installation)
- [Quickstart](#quickstart)
- [Usage Guide](#usage-guide)
  - [Basic API](#basic-api)
  - [Dict-style interface](#dict-style-interface)
  - [Statistics](#statistics)
  - [Tuning parameters](#tuning-parameters)
  - [Thread safety](#thread-safety)
- [Benchmark Results](#benchmark-results)
  - [Running the benchmark](#running-the-benchmark)
- [Algorithm Overview](#algorithm-overview)
- [Project Structure](#project-structure)
- [Running Tests](#running-tests)
- [Citation](#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 `deque`s |
| 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

```bash
# 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:
```bash
pip install matplotlib
```

---

## Quickstart

```python
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

```python
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:

```python
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

```python
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

```python
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

```python
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:

```python
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

```bash
# 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`](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

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

With coverage:
```bash
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:

```bibtex
@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](LICENSE) © 2024
