## LRU Cache Benchmark

Real-world data distribution, fixed memory budget, comparing hit rate and effective OPS.

### Results

| Library | Hit Rate | Effective OPS | Perf | Memory |
|---------|----------|---------------|------|--------|
| size_lru | 69.83% | 1.85M/s | 100% | 16816.6KB |
| moka | 70.55% | 1.31M/s | 71% | 16044.9KB |
| mini-moka | 69.87% | 1.13M/s | 61% | 16023.3KB |
| clru | 55.19% | 1.27M/s | 69% | 16187.3KB |
| lru | 54.49% | 1.31M/s | 71% | 15551.5KB |
| hashlink | 54.43% | 1.30M/s | 70% | 15361.3KB |
| schnellru | 54.52% | 1.32M/s | 71% | 16443.8KB |

### Configuration

Memory: 16.0MB · Zipf s=1 · R/W/D: 90/9/1% · Miss: 5% · Ops: 30M×3

### Size Distribution

| Range | Items | Size |
|-------|-------|------|
| 16-100B | 40% | 0% |
| 100B-1KB | 35% | 2% |
| 1-10KB | 20% | 12% |
| 10-100KB | 4% | 24% |
| 100KB-1MB | 1% | 62% |

---

<details><summary>Notes</summary>

#### Data Distribution

Based on Facebook USR/APP/VAR pools and Twitter/Meta traces:

| Tier | Size | Items% | Size% |
|------|------|--------|-------|
| Tiny Metadata | 16-100B | 40% | ~0.3% |
| Small Structs | 100B-1KB | 35% | ~2.2% |
| Medium Content | 1-10KB | 20% | ~12% |
| Large Objects | 10-100KB | 4% | ~24% |
| Huge Blobs | 100KB-1MB | 1% | ~61% |

#### Operation Mix

| Op | % | Source |
|----|---|--------|
| Read | 90% | Twitter: 99%+ reads, TAO: 99.8% reads |
| Write | 9% | TAO: ~0.1% writes, relaxed for testing |
| Delete | 1% | TAO: ~0.1% deletes |

#### Environment

macOS 26.1 (arm64) · Apple M2 Max · 12 cores · 64.0GB · rustc 1.94.0-nightly (21ff67df1 2025-12-15)

#### Why Effective OPS?

Raw OPS ignores hit rate — a cache with 99% hit rate at 1M ops/s outperforms one with 50% hit rate at 2M ops/s in real workloads.

**Effective OPS** models real-world performance by penalizing cache misses with actual I/O latency.


#### Why NVMe Latency?

LRU caches typically sit in front of persistent storage (databases, KV stores). On cache miss, data must be fetched from disk.

Miss penalty: 1,377ns — measured via NVMe 4KB random read (16MB tempfile, 100 iterations)


Formula: `effective_ops = 1 / (hit_time + miss_rate × miss_latency)`

- hit_time = 1 / raw_ops

- Higher hit rate → fewer disk reads → better effective throughput

#### References

- [cache_dataset](https://github.com/cacheMon/cache_dataset)
- OSDI'20: Twitter cache analysis
- FAST'20: Facebook RocksDB workloads
- ATC'13: Scaling Memcache at Facebook
</details>