Ecosystem · cache admission filter
Every TinyLFU-family cache needs two structures: a frequency estimator and a "doorkeeper" (usually a Bloom filter) to catch one-hit wonders before they ever touch the estimator. epochsketch.Sketch.Observe already returns both answers in one call — this package tests whether that actually eliminates the second structure, or just moves the cost somewhere else.
sk := epochsketch.New(epochsketch.Config{NumBuckets: 1 << 16, TickDuration: time.Second}) cache := admission.New[string](sk, admission.Config{Capacity: 10_000}) cache.Set("user:42", "profile-blob") val, ok := cache.Get("user:42")
One shared Sketch across all shards, sharded LRU for the resident set (independent mutex-guarded shards, count derived from GOMAXPROCS unless overridden) — the same contention-relief technique epochsketch's own ShardedEvictionSalt uses, not a from-scratch lock-free structure.
Same Zipfian stream (S=1.1, 10,000-key population) fed identically to all three.
| Cache size | epochsketch | go-tinylfu | plain LRU |
|---|---|---|---|
| 1% (100) | 64.63% | 63.14% | 52.98% |
| 5% (500) | 78.51% | 77.50% | 70.93% |
| 10% (1000) | 83.75% | 82.96% | 78.04% |
EpochSketch edges out go-tinylfu — a real, independently-built implementation (CM4 + doorkeeper + segmented LRU) — at every size tested, and both admission-filtered caches beat plain LRU by 6–12 points, largest at the smallest cache size, exactly where admission quality matters most.
Warm a 100-capacity cache on a skewed 1,000-key population, inject a 5,000-key burst of one-hit-wonders, then check whether the top-20 hottest keys are still resident.
20/20 survived. Plain LRU: 0/20. A scan key looks identical to a first-sighting challenger (estimate == 1), and a first-sighting challenger can never beat a warm resident — the whole population survives by construction, not by luck.
Both structures sized for ~65,536 entries.
| Structure | Bytes |
|---|---|
| Sketch, exact by construction | 4,194,304 |
| Sketch, measured heap delta | 4,194,576 |
| go-tinylfu, measured heap delta | 5,068,440 |
go-tinylfu's two-structure design costs about 21% more heap for a comparable configured size.
200,000 rows of a real Twitter CDN trace excerpt.
| Cache size | epochsketch | plain LRU |
|---|---|---|
| 1% (509) | 64.45% | 72.61% |
| 5% (2547) | 69.49% | 73.26% |
| 10% (5094) | 70.31% | 73.62% |
Plain LRU wins here — the opposite of the synthetic result, and not swept under the rug. The trace replays 200,000 events in well under a second, so no TickDuration epoch ever elapses — EpochSketch's actual headline advantage, intrinsic decay, never activates. What gets measured instead is admission quality on raw lifetime frequency alone, the exact no-clock failure mode a plain Count-Min Sketch has on any population with real time-varying popularity (this trace has one — keys rotate hourly). A real deployment has actual wall-clock time between requests, so decay does activate; this is a limitation of the test's methodology, flagged honestly rather than hidden.
Single-threaded, zero allocations except where an admission genuinely inserts a new entry.
| Benchmark | ns/op | allocs/op |
|---|---|---|
| Get (hit) | ~40 | 0 |
| Set, rejected challenger | ~37–73 | 0 |
| Set, admitted challenger | ~327 | 1 (69 B) |