A frequency sketch, fused
Count, recency, and first-sighting were always three separate structures, kept painfully in sync. EpochSketch fuses them into a single packed word — one cache line, one atomic compare-and-swap per decision. Decay is never performed by anyone; it's interpreted at read time, so there is no background mutator at all.
sk := epochsketch.New(epochsketch.Config{ NumBuckets: 1 << 16, TickDuration: time.Second, }) est, first := sk.Observe("checkout:sku-42")
observe #1 -> estimate=1 first=true observe #2 -> estimate=2 first=false observe #3 -> estimate=3 first=false observe #4 -> estimate=4 first=false observe #5 -> estimate=5 first=false new key -> estimate=1 first=true
| Constraint | What it means | Evidence |
|---|---|---|
| Fixed memory | Allocated once at construction, independent of key cardinality | NumBuckets × 8 words, never resized |
| Nanosecond-scale | Cost comparable to a memory access; zero heap allocation per Observe | ~21 ns/op single-threaded, 0 allocs/op |
| Intrinsic decay | Recency is a read-time interpretation — no cleanup sweep, no reset pause | count >> age |
| Concurrent by construction | Many goroutines call Observe at once; no locks | Lock-free CAS, race-detector-clean |
| Safe error direction | When forced to approximate, underestimates the small, never loses the large | Fail-open: a lost eviction resolves to "first," never overcounts |
| If you reach for | It answers | What's different here |
|---|---|---|
| map[string]int | Exact counts, small keyspace | Grows without bound; EpochSketch trades exactness for fixed memory at any cardinality |
| HyperLogLog | How many distinct keys | A different question entirely — cardinality, not per-key frequency |
| Count-Min Sketch | How often, ever | No decay — a key hot last week looks as hot as one hot right now, until a full sweep |
| Caffeine / Ristretto | Cache admission decisions | Decay via periodic bulk halving, bundled inside a full cache — this is just the signal |