Adaptive cache replacement with online learning — no hand-tuned heuristics.
A portfolio project that implements a self-tuning cache eviction policy. CacheForge tracks both recency and frequency, uses EMA-adapted strategy weights, and includes an admission filter that learns to reject one-hit-wonder keys. Benchmarked against LRU, LFU, and TinyLFU (Caffeine) on 4 real-world-style workloads.
Every cache in the world uses one of:
- LRU — Simple but thrashes on scan workloads (one scan evicts all hot data)
- LFU — Adapts slowly, poisoned by frequency spikes
- TinyLFU (Caffeine) — Best-in-class but hand-tuned admission window
- ARC (Adaptive Replacement Cache) — Patented by IBM
Nobody ships a self-tuning cache that observes its own workload and adapts. The research exists (Learned Cache Replacement, 2020) but no readable, testable, portfolio-quality implementation.
Instead of a single eviction policy, CacheForge runs two strategies in competition:
On eviction:
1. Find LRU candidate (oldest access)
2. Find LFU candidate (lowest frequency)
3. EMA weights decide which candidate to evict
4. Track if eviction was "good" (evicted key wasn't accessed again)
5. Update weights based on success rate
The weights adapt in real-time:
- If recent evictions were "good" (key wasn't re-accessed) → weight increases
- If evictions were "bad" (key was re-accessed) → weight decreases
Before admitting a new key, CacheForge checks:
- Has this key been seen before? (Count-Min Sketch estimate)
- Is its estimated frequency ≥ the current victim's frequency?
This prevents cache pollution from one-hit-wonder keys (scan workloads, batch imports).
w_lru = decay * w_lru + (1 - decay) * lru_success_rate
w_lfu = decay * w_lfu + (1 - decay) * lfu_success_rate
# Normalize so w_lru + w_lfu = 1.0Default decay = 0.95 (smooth adaptation, no oscillation).
| Technique | Purpose |
|---|---|
| EMA (Exponential Moving Average) | Adaptive strategy weight selection |
| Count-Min Sketch | Streaming frequency estimation for admission |
| Online success tracking | Feedback loop for eviction quality |
| Competitive selection | Multi-strategy arbitration |
No training phase. No labeled data. No GPU. Pure streaming statistics.
All benchmarks: 500 capacity, 100K accesses, 4 workloads.
| Workload | LRU | LFU | TinyLFU | CacheForge |
|---|---|---|---|---|
| Zipf (s=0.9) | 99.5% | 99.5% | 99.5% | 99.5% |
| Zipf + Scan Bursts | 81.9% | 83.1% | 83.3% | 83.0% |
| Recency Shift | 89.4% | 89.4% | 89.4% | 86.9% |
| Mixed Workload | 84.1% | 85.8% | 86.0% | 85.9% |
- CacheForge matches TinyLFU on 3/4 workloads (Zipf, Scan, Mixed)
- Admission filter rejects 13K-17K one-hit-wonder keys on scan workloads
- CacheForge (no admission) matches LRU exactly — the admission filter is the differentiator
- Recency Shift is the hardest workload — the admission filter is slightly slow to adapt when the hot key set shifts
| Workload | Keys Rejected | Effect |
|---|---|---|
| Zipf | 43 | Minimal (most keys are hot) |
| Scan Bursts | 16,509 | Blocks scan pollution ✓ |
| Recency Shift | 12,572 | Slightly over-aggressive |
| Mixed | 13,563 | Blocks one-hit-wonders ✓ |
pip install -e .
# Run all benchmarks
python -m benchmarks.cli benchmark -c 500 -n 100000 -w all
# Quick test with Zipf
python -m benchmarks.cli quick -c 100 -n 10000
# Run tests
python -m pytest tests/ -v
# Generate charts
python benchmarks/generate_charts.py benchmarks/results/results.json docs/imagescacheforge/
├── cacheforge/
│ ├── __init__.py
│ ├── base.py # Base cache interface + stats
│ ├── lru.py # LRU (dict + doubly-linked list)
│ ├── lfu.py # LFU (dict + frequency buckets)
│ ├── tinylfu.py # TinyLFU (Count-Min Sketch + LRU)
│ └── cacheforge.py # CacheForge (adaptive, EMA, admission)
├── benchmarks/
│ ├── cli.py # Benchmark CLI
│ ├── generate_charts.py
│ └── results/
├── tests/
│ └── test_core.py # 23 tests
├── docs/images/ # Benchmark charts
├── pyproject.toml
├── LICENSE (MIT)
└── README.md
Shows you think about adaptive systems, not static heuristics.
Demonstrates streaming algorithm design — the cache learns which policy works better for this specific workload.
Shows you know probabilistic data structures and when to use them (O(1) memory, streaming, mergeable).
Honest benchmarking. You compared against the state-of-the-art and showed competitive results. Engineers respect honesty over inflated claims.
Demonstrates understanding of the scan workload problem — the #1 real-world cache pathology.
Shows engineering judgment — you chose the right tool (streaming stats) instead of over-engineering with ML.
| Typical Portfolio | CacheForge |
|---|---|
| "I built a cache" (LRU dict) | "I built an adaptive cache with online learning" |
| "I used Redis" | "I implemented TinyLFU from scratch" |
| "I fine-tuned GPT" | "I used EMA + Count-Min Sketch" |
| Toy project | Benchmarked against Caffeine (industry standard) |
This is systems engineering — the kind of work that gets you hired at CockroachDB, Redis Labs, ScyllaDB, or any team that cares about performance at the I/O path level.
- LRU, LFU, TinyLFU baselines implemented from scratch
- CacheForge: competitive eviction with EMA-adapted weights
- Count-Min Sketch admission filter
- 4 synthetic workload generators (Zipf, Scan, Shift, Mixed)
- Benchmarks on all 4 workloads
- Matched TinyLFU on 3/4 workloads
- Admission filter rejects 13K-17K one-hit-wonder keys
- 23 passing tests
- Benchmark visualization charts
- Comprehensive README with real results
MIT