01 · Problem Statement

Document 01 of the EpochSketch project. This document defines the problem. It deliberately contains no solution — not a bit layout, not an algorithm. If a design decision can’t be traced back to a sentence in this document, the decision is suspect. (This separation is itself a data-structure-design discipline: the contract comes first, the mechanism serves it.)

1. The problem in one sentence

“How often has this thing been happening lately?” — answered in nanoseconds, for millions of distinct things, in a fixed amount of memory, by many threads at once, forever.

Every word in that sentence is load-bearing. The rest of this document unpacks why.

2. The plain-English version

Imagine you run the door at an enormous, very busy club. Thousands of faces per minute. Your job is to spot the regulars of the last hour — not the person who came every night in 2019 and stopped, not the one who showed up once tonight, but who is showing up a lot, recently.

Now the constraints:

You cannot write anything down per person. There are millions of possible faces; your notepad is one page, fixed size, bought once.
You must answer instantly. The line cannot stop while you think.
Memory must fade on its own. Last hour’s regular who stopped coming must automatically stop counting as a regular — you don’t get a nightly “erase the notepad” break, because the club never closes.
Several of you work the door at once, and you can’t huddle to compare notes between guests.

That’s the problem. Notice it is really three questions fused together, all about the same face at the same moment:

How often? — frequency
How recently? — freshness / decay
Have I seen this one in the current shift yet? — first-sighting detection

Existing tools answer these separately, each with its own memory and its own bookkeeping. The thesis of this project is that because all three questions are about the same key at the same instant, they can be answered by one structure, in one memory access — and that fusing them doesn’t just save space, it dissolves the coordination problems that keeping three structures in sync creates.

3. Why the obvious solutions fail

This section is the actual justification for the project’s existence. A new data structure is only warranted when the standard answers genuinely break — so we owe each one an honest hearing.

3.1 “Just use a hashmap of counters”

map[key]count, increment on every event.

Memory is unbounded. One counter per distinct key, and keys churn endlessly (new users, new sessions, new log lines). The map grows forever; in a garbage-collected language it also pressures GC with every insertion.
No notion of time. A key hammered a million times last month looks identical to one hammered a million times this minute. To fix that you bolt on timestamps per key (more memory) and a cleanup sweep (a background job that races your writers — now you need locks).
Locks. A shared map with many writers needs synchronization; sharding helps but the cleanup sweep still has to visit everything.

The hashmap is the right answer at small scale. This project only makes sense past the point where it breaks — roughly: unbounded key cardinality, millions of ops/second, always-on operation.

3.2 “Count in fixed windows and reset”

Keep counters, wipe them every minute.

The reset itself is the flaw: at the boundary, all history vanishes — a key that did 10,000 events at 11:59:59 looks brand new at 12:00:00. Decisions oscillate at every boundary (the classic “thundering window edge”).
The wipe is a global pause touching every counter — precisely the kind of stop-the-world background mutation that fights concurrent writers.

3.3 “Sliding window: keep recent events, expire old ones”

Exact and smooth — and the memory cost is proportional to the event rate, not the key count, because every event lives somewhere until it expires. At millions of events per second, a 60-second window means holding hundreds of millions of timestamps. This is the tail-sampling memory problem in miniature, and it’s the definition of not-fixed-memory.

3.4 “Use a probabilistic sketch (Count-Min Sketch)”

Now we’re close — CMS gives fixed memory and fast counts. But:

CMS has no clock. Counts only ever grow. “Frequent lately” is not a question it can answer; everyone bolts on external decay (a halving loop, window rotation, sketch swapping) — and that bolt-on reintroduces the background mutator racing concurrent writers, which is where the engineering pain actually lives.
CMS errs in the dangerous direction. Hash collisions only ever inflate a count. For most decisions built on top (“suppress the frequent, protect the rare”), inflating a rare key’s count means harming exactly the thing you were trying to protect.
No first-sighting answer. The diversity question needs yet another structure.

3.5 The pattern across all four

Tally the bolt-ons every path accumulates: a timestamp store, a cleanup sweep, a reset pause, a decay loop, a seen-this-window table. Every standard answer ends up maintaining time as a separate mechanism from counting — and the synchronization between the two mechanisms is where the memory blow-ups, the pauses, and the races come from. The problem, stated structurally:

Frequency and recency are treated as two facts requiring two systems, when they are one fact about one key at one moment.

4. Real-world examples (who has this problem)

Each example is the same three-question shape wearing different clothes.

A. Telemetry sampling (the origin story). A fleet of services emits millions of log lines per second; 95% are near-duplicates (health checks, retry chatter). To keep costs sane you want to drop most of the repetitive stuff and keep everything rare — but “repetitive” changes hour to hour, so the filter must learn and forget on its own. Per log line, at line rate: how frequent is this template lately (suppress proportionally), and is this its first appearance this window (always keep one — never go fully blind)?

B. API rate limiting. A gateway wants adaptive fairness: clients who are hammering right now get squeezed; a client who was noisy an hour ago but calmed down is forgiven automatically. A token bucket per client is the hashmap problem (unbounded map + expiry sweeps). Wanted: fixed memory, per-request speed, built-in forgetting.

C. Cache admission (“is this worth caching?”). When a cache is full and a new item arrives, admit it only if it’s hotter than what it would evict — otherwise one-hit wonders flush your working set. The question per lookup: recent frequency of this key, in nanoseconds, in memory that must be a tiny fraction of the cache itself. (State of the art — TinyLFU — uses a CMS plus a periodic global halving pause: the exact bolt-on pattern of §3.5.)

D. Hot-key / DDoS detection. A database, CDN, or packet filter needs to spot keys that suddenly go hot — trending content, an abusive IP, a celebrity row — while processing millions of ops/second. “Sudden” is the key word: it’s inherently a recency-weighted frequency question, and the answer must come from the smallest possible memory footprint because it runs on the hottest path in the system.

E. Fraud velocity checks. “Has this card / device / account been attempting things unusually often in the last few minutes?” Millions of entities, most seen once and never again (churn!), decisions inline with the transaction.

One table, because the shape really is identical:

	Key	“Frequent lately?” drives	“First this window?” drives
Telemetry	log template / trace key	suppression probability	never-go-blind guarantee
Rate limiting	client / tenant	throttle level	new-client grace
Cache admission	object key	admit vs reject	—
Hot-key detection	row / IP / URL	alarm / mitigation	first-seen alerting
Fraud velocity	card / device	risk score input	new-entity flag

5. The contract (what the structure must promise)

This is the distilled requirement — the section every design decision must trace back to.

Single operation: Observe(key) → (estimated recent frequency, first-sighting-this-window flag) — one call, made inline on the hot path, that both records the event and answers the questions.

Constraints:

#	Constraint	Meaning	Justified by
C1	Fixed memory	Allocated once at startup; independent of key cardinality and event rate	§3.1, §3.3
C2	Nanosecond-scale, allocation-free operation	Cost comparable to a single memory access; no per-event heap allocation	all examples run on hot paths
C3	Intrinsic decay	Recency weighting is a property of reading the structure, requiring no background mutation, no reset pause, no cleanup sweep	§3.2, §3.5
C4	Concurrent by construction	Many threads observe simultaneously; no locks, no stop-the-world moments	§3.1, §3.4
C5	Safe error direction	When the structure must err (it will — fixed memory forces approximation), it should underestimate the small and never lose track of the large	§3.4
C6	Graceful forever-operation	No unbounded counters, no epoch overflow surprises, no degradation over days of uptime	the club never closes

Explicitly permitted (the price of the constraints):

Approximation. Estimates, not exact counts, with stated error bounds.
Probabilistic guarantees. “With high probability” is acceptable; “always exactly” is not required.
Point queries only. The structure answers questions about a presented key; it need not enumerate keys, rank them, or report totals.

Non-goals

Named to prevent scope creep: exact counting; key enumeration / top-k reporting (a consumer can layer that on); distributed / cross-process consistency; persistence across restarts; lifetime totals (the structure’s counts are recency-weighted by design — that’s the feature).

6. What “success” means

THEORY.md exists and holds: written error bounds for every approximation, each traceable to C5, validated by simulation against exact ground truth on realistic (Zipfian, churning, bursty) and adversarial streams.
The contract benchmarks true: C1–C4 demonstrated with numbers — memory flat over 24h churn, ns-scale p99, zero allocations, linear scaling with writer threads.
A stranger can adopt it in an afternoon: one type, one method, one page of honest documentation including the non-goals.
At least one real consumer: the telemetry sampler (example A) gets built on top and works — the origin problem is the first acceptance test, not the definition.

7. Glossary (plain-terms anchors used throughout the project)

Key — the identity of a recurring thing: a log template, a client ID, a URL. Anything hashable.
Cardinality — how many distinct keys exist. The enemy of per-key memory.
Churn — keys constantly being born and abandoned. The enemy of “just clean up later.”
Heavy hitter / elephant — a key responsible for a large share of recent events. Mouse — a key seen rarely.
Decay / half-life — how fast the structure forgets: after one half-life, an untouched key counts half as much.
Sketch — a fixed-size structure giving approximate answers about an unbounded stream.
Hot path — code executed per event, where every nanosecond and every allocation is paid millions of times per second.