02 · Design Spec v2

Supersedes: Design Specification v1. Change discipline: every amendment is marked [AMENDED] with the v1 position, the defect, and options for resolution. Items marked [NEW] cover contract obligations or failure modes v1 missed. Every resolution cites the constraint (C1–C6) it serves. Open choices are collected in §9 for sign-off.

Reading aid: every resolution ends with a 🧭 In plain terms block — a non-engineer-friendly walkthrough using the bouncer-and-notepad world from the problem statement (notepad row = cache-line bucket, name-line = slot, tally marks = count, hour stamp = epoch, walking to a shelf = a memory fetch). If a plain-terms block and the formal text ever disagree, the formal text wins — the blocks exist to build intuition, not to define behavior.

1. The Friction Points (unchanged framing, one addition)

The core engineering challenges emerge where constraints collide:

FP1: The Math of Intrinsic Decay (C2 vs C3). Decay without a background mutator, without floating-point math.
FP2: Concurrency of Time and State (C3 vs C4). Count and timestamp updated together, lock-free.
FP3: Safe Error Direction (C1 vs C5). Fixed-memory collisions must underestimate mice and never lose elephants.
[NEW] FP4: Boringly Correct Forever (C6). Finite-width fields (count, timestamp) must not produce wraparound or overflow surprises at any uptime.

2. Contract Compliance [NEW — v1 defect: dropped half the operation]

The contract defines: Observe(key) → (estimated recent frequency, first-sighting-this-window flag). v1 specified only the frequency path. The flag is restored as a first-class output with defined semantics for every code path:

Path taken by `Observe`	Flag value	Rationale
Fingerprint match, slot epoch == now	`false`	Seen this window already
Fingerprint match, slot epoch stale (fold occurs)	`true`	Fold detection is first-sighting — free (C3)
Empty slot claimed	`true`	New key tracked
Slot won via eviction	`true`	New key tracked
Eviction challenge lost (key untracked)	Choose — see below

Options for the eviction-loser flag:

Option A (Recommended): flag = true. “Not tracked” ⇒ structure has no evidence of frequency ⇒ treat as rare/first-seen. Fails open: consumers that use the flag as a “never go fully blind” guarantee (telemetry, rate-limit grace) remain safe even under table pressure. Consistent with C5’s spirit — error direction favors the small.
Option B: flag = false + separate tracked = false output. More honest API (three-valued truth), lets sophisticated consumers distinguish “first sighting” from “unknown.” Cost: wider API surface for a rare path; most consumers will just OR the two.
Option C: flag = true with probability decreasing per repeated loss. Rejected — requires remembering losers, which is the thing the structure cannot do (C1).

🧭 In plain terms: the bouncer’s notepad row is full of established regulars, and a new face shows up that he can’t record anywhere. What does he report? Option A says: “if I have no notes on you, I must assume you’re new” — so the new face gets first-timer treatment (waved through). This is the safe mistake: worst case, we’re slightly too generous to a stranger. The alternative — assuming an unrecorded face is a regular — would punish genuinely new arrivals, which is exactly the error direction the contract forbids.

3. Resolution of FP1 & FP2: The Packed Word and CAS Loop

3.1 The Packed Slot — layout ratified

Layout: [ 16-bit fingerprint | 24-bit timestamp | 24-bit count ] in one 64-bit word.

v2 endorses this v1 layout over the earlier 16|16|32 sketch: the 24-bit timestamp pushes wrap horizon from 65,536 ticks to 16.7M ticks, and 24-bit counts cover every row of the Tick Table (§3.4) once saturation (§3.3) is specified.

3.2 Intrinsic Decay via Bit-Shifting (unchanged, one portability amendment)

age          = (now − slot.timestamp) mod 2²⁴      // unsigned wrap subtraction
effective    = slot.count >> min(age, 63)          // [AMENDED] clamp — see below

[AMENDED] Shift clamp is mandatory, not stylistic. v1 stated “shifting by ≥24 guarantees 0.” True in Go (shifts ≥ width are defined to produce 0 for unsigned). Undefined behavior in C/C++ for shift ≥ word width; Rust masks shift counts in release. Any port that transcribes v1 literally inherits a UB landmine. The spec text therefore mandates the explicit min(age, 63) clamp in the reference algorithm. (C6: correctness must not depend on one language’s shift semantics.)

Evaporation: count physically zero after ≥24 epochs of silence — unchanged, now via the clamped shift.

🧭 In plain terms: the bouncer never erases tally marks — he just reads them as fainter the older they are. A guest has 800 tally marks stamped “hour 100.” At hour 101 the bouncer glances at the entry and mentally halves it: “worth 400 now.” At hour 102: “worth 200.” The ink on the page never changed; only its interpretation did. That’s why no cleanup crew (background thread) is ever needed. And because halving 24 times turns even the biggest number into zero, any entry ignored for 24 hours reads as completely blank — total amnesia, achieved without anyone touching the page. The min(age, 63) clamp is just the rule “if it’s ancient, don’t bother counting how ancient — it’s zero,” written so every programming language computes it the same way.

3.3 Saturating Add [NEW — v1 defect: unspecified overflow]

At count == 2²⁴−1, a plain increment wraps to 0: the largest elephant in the system instantly becomes invisible and evictable — a C5 and C6 double violation triggered by exactly the keys the structure exists to track.

Resolution (no options — this is a correctness requirement):

if count < MAX24 { count++ }        // one predictable branch

The equilibrium analysis (§3.4) shows saturation is reachable only when a single key exceeds the configured tick’s velocity ceiling; at saturation the count parks at max — the elephant stays maximally protected — and decays normally once pressure stops. This behavior is documented as the defined overflow semantics.

🧭 In plain terms: think of an old car odometer. A plain counter is the odometer that rolls over from 999,999 back to 000,000 — suddenly the most-driven car in the lot looks brand new. In our world that’s catastrophic: the single busiest guest in the club would instantly read as a first-timer and lose their protected status. Saturation is the fix: the needle simply parks at maximum. “More than 16 million tallies” and “16 million tallies” are treated the same — both mean “extremely frequent” — which loses nothing and breaks nothing.

3.4 System Limits — The Tick Table (ratified, graduated to permanent status)

Steady-state check: under per-epoch halving, sustained rate R converges to 2R; therefore R_max = 2²⁴/2 ≈ 8.38M events/epoch per key. Verified; table stands and becomes the canonical operator-facing sizing artifact:

Configured Tick (Half-Life)	Max Sustained Velocity (1 key)	Complete Evaporation	Use Case Fit
100 ms	83.8 M/s	2.4 s	DDoS packet filter
1 s	8.38 M/s	24 s	API rate limiting
1 min	139,810/s	24 min	Telemetry sampling
1 hour	2,330/s	24 h	Fraud/abuse velocity
1 day	97/s	24 d	Long-term trending

3.5 CAS Loop (unchanged, one amendment)

Read word → compute locally (fold, compare fingerprint, saturating increment) → CAS → retry on failure.

[AMENDED] Bounded retries + defined give-up semantics. v1 said the loop “rarely fails”; true, but unbounded retry has no place in a C2 guarantee. Spec: retry ≤ 3, then drop the increment (fail-open: a lost increment under extreme contention biases toward underestimation — the safe direction, C5) and bump a contention self-metric. Frequency estimates from the read path are unaffected.

🧭 In plain terms: two doormen try to update the same line of the notepad at the same instant. There’s no lock on the notepad; instead, each doorman photographs the line, writes his updated version, and swaps it in only if the line still matches his photo. If a colleague beat him to it, the swap is refused, he takes a fresh photo, and tries again. The amendment adds: after three refused swaps, shrug and skip the tally. Why is skipping safe? Because losing one tally mark out of thousands can only make a busy guest look very slightly less busy — the harmless direction of error — and it only ever happens on lines so busy that one mark is statistical dust anyway.

3.6 Alternative Bit Allocations (retained, one upgraded note)

Alt A — 128-bit atomics (cmpxchg16b): unchanged assessment; portability cost.
Alt B — Morris (logarithmic) counting: [AMENDED — v1 undersold it]. In log domain, exponential decay becomes integer subtraction: count = max(0, count − age). Decay and representation compose exactly — no shift, no clamp, evaporation horizon = count value itself. Still costs randomness on increment, so it remains an alternative rather than the default, but this synergy is flagged as a THEORY.md section: it may become the preferred layout for the 1-hour/1-day tick rows where increment rates are low and range needs are high.
Alt C — linear decay: unchanged assessment.

4. Resolution of FP3: Safe Error Direction

4.1 Pillar 1 — Eviction Logic [AMENDED — v1 recommendation has a lockout bug]

Defect in v1 Option A (strict weight comparison): incoming weight is 1; eviction requires 1 > decayed_occupant; therefore a slot turns over only when its occupant has decayed to zero. A brand-new heavy hitter — a fresh attack key, a suddenly-hot template — cannot be tracked for up to 24 epochs. In the DDoS row of the Tick Table, that is 2.4 s of structural blindness to precisely the key that matters most; in the telemetry row, 24 minutes. The failure mode is “never evict ⇒ new elephants can’t enter,” expressed as a comparison operator.

v1 rejected probabilistic eviction because “RNG on the hot path breaks C2.” That objection is overstated twice: (1) the roll executes only on the collision-miss path, never the common path; (2) no RNG is needed — the key’s own hash is free entropy. ~30 of the 64 computed hash bits are consumed by bucket index + fingerprint; the spare bits, mixed with the occupant’s current word (which changes every attempt), yield a per-attempt pseudo-random decision at zero additional cost.

Options:

Option A (Recommended): Hash-entropy chipping.
```
victim  = slot with min effective count in bucket
chip if:  (spareHashBits ⊕ victimWord) & mask(victim.count) == 0
on chip:  victim.count−−  ;  at 0 the challenger claims the slot (count=1, epoch=now)
```
mask(count) widens with the victim’s count, so chip probability falls roughly geometrically with victim strength — HeavyKeeper’s protection curve without HeavyKeeper’s RNG. Sustained challengers win slots in bounded expected attempts; one-off churn almost never chips anyone. Elephants (count in the thousands) are statistically unevictable. The exact mask schedule (step points, effective base b) is a THEORY.md deliverable with simulation validation. Pros: C2 (no RNG, no extra memory access — victim word already in-register), C5 (elephants protected, new elephants admissible in bounded time). Cons: entropy quality rests on hash avalanche (§4.3 requirement) and on the victim word churning; adversarial analysis required in THEORY.md.
Option B: Strict comparison + decay-floor assist. Keep v1’s strict rule but compare against effective_count after fold, and define a challenger-count parameter (if k_challenges_this_epoch > effective) — approximates “sustained pressure wins” without per-attempt randomness. Cons: counting challenges per epoch requires memory for losers — which C1 forbids — unless approximated by… a sketch. Circular; included for completeness, not recommended.
Option C: HeavyKeeper-classic (true RNG roll b^−count). The literature-validated baseline. Pros: published analysis to lean on. Cons: RNG on the miss path; measurable but small. Acceptable fallback if Option A’s entropy quality fails simulation.

Decision gate: Option A ships if and only if its error CDF on adversarial simulation streams is statistically indistinguishable from Option C’s. Otherwise Option C.

🧭 In plain terms — the v1 bug first: v1’s rule was “a newcomer takes a regular’s line only if the newcomer’s 1 tally beats the regular’s total.” But 1 never beats anything except 0 — so a line frees up only when its occupant has completely faded away. Picture a brand-new troublemaker hammering the door 10,000 times an hour while the bouncer literally cannot start a file on him for a whole day because the page is full of half-faded old names. That’s the lockout.

The chip fix: instead of all-or-nothing takeover, a rejected newcomer gets to erase one tally mark from the weakest name on the row — but only if he wins a lottery, and the lottery gets brutally harder the stronger that weakest name is. Concretely: chipping someone with 3 tallies succeeds about one attempt in 8; chipping someone with 5,000 tallies is like winning the lottery every day for a month — effectively never. So a persistent newcomer (10,000 knocks) grinds down a weak occupant in a handful of tries and gets his line fast, while a one-off visitor almost certainly loses his single lottery ticket and is forgotten. Regulars stay safe; genuinely new heavy hitters get in quickly.

The free lottery ticket: where do the random numbers come from without slowing down? From digits we already have. Every guest’s ID was already converted to a long random-looking number (the hash) to find their page — and we only used part of it. The leftover digits, combined with the ever-changing tally line itself, make a perfectly good lottery draw. No dice needed: the ticket was printed the moment the guest walked up.

4.2 Pillar 2 — Associativity [AMENDED — v1 regressed the memory model]

Defect in v1 (d=4 scattered hash locations): four independent locations = four cache-line fetches per observe = ~4× the memory stalls, invalidating the structure’s core C2 claim. v1’s cons for Pillar 1 (“two elephants permanently block each other in a 1D array”) is an artifact of scattering single slots; it is solved better by set-associativity than by more scattering.

Restored design: the bucket as the atom of layout.

bucket = 8 slots × 8 bytes = 64 bytes = exactly one cache line
index  = hash(key) mod numBuckets      → one line fetch
tag    = 16 further hash bits          → 8 candidate matches examined in-register

Eight elephants coexist in one bucket before any eviction pressure exists at all. Tag comparison across 8 slots is branch-light scalar code today and one AVX2 instruction later.

Options for bucket-level choices:

Option A (Recommended): Single bucket (1 line per observe). Maximal C2. Bucket-overflow probability under Zipfian load is a THEORY.md computation; expected to be negligible at sane sizing because heavy hitters are few by definition (§4.4).
Option B: Two candidate buckets (power-of-two-choices at bucket granularity). Key hashes to two buckets; observe checks both, inserts into the less-loaded. 2 lines touched, 16 candidates — still half of v1-d=4’s traffic with four times v1’s coexistence capacity. Adopt only if Option A’s overflow analysis fails; this is the designated escape hatch, pre-analyzed so adopting it later is a config change, not a redesign.
Option C: v1’s d=4 scattered slots. Retired with cause (above).

🧭 In plain terms: the expensive thing in modern computing isn’t reading — it’s walking to the shelf. A cache line is one armful: fetching 1 byte or 64 bytes from that shelf costs the same trip. v1’s design gave each guest four possible homes on four different pages — four walks to four shelves per guest. The bucket design gives each guest one page row holding eight name-lines: one walk, and once the row is in your hands, checking all eight names is free. It also fixes v1’s own worry (“two big regulars fighting over one line”) more thoroughly: eight regulars simply share the row with no fight at all. And if the math ever shows rows overflowing, the pre-approved escape hatch is “each guest gets two candidate rows, use the emptier one” — still only two walks, and sixteen lines of room.

4.3 Pillar 3 — Hashing [AMENDED — from global choice to threat-model requirement]

v1 framed hashing as one global pick (speed vs HashDoS). v2 reframes: the hash is a pluggable, per-deployment choice with a mandatory seed and a mandatory quality bar.

Requirements (non-negotiable):

Avalanche quality — Option 4.1-A’s entropy chipping consumes raw hash bits; the hash must pass avalanche/bias tests (SMHasher-class). This disqualifies FNV-1a for the default (poor avalanche), independent of speed.
Per-process random seed — always, regardless of algorithm. Costs nothing; removes the “predictable seed” half of HashDoS.

Defaults by threat model (guidance table for the README):

Deployment faces…	Default	Why
Internal keys (telemetry templates, internal IDs)	xxHash3 / rapidhash-class	ns-fast, avalanche-clean
Attacker-supplied keys (DDoS filter, public API limits)	SipHash-1-3 or AES-based keyed hash	HashDoS: adversary must not engineer bucket floods or chip-entropy bias

(Fact-check from v1: Go’s runtime map hash is AES-based on x86-64 with hardware support, not SipHash; the “used natively by Go” claim is corrected.)

🧭 In plain terms: the hash is the coat-check scheme — it turns any guest’s name into a shelf number. Two things can go wrong. First, a sloppy scheme sends similar names to nearby shelves, so shelves clump and overflow (that’s FNV-1a’s weakness — and worse for us, our eviction lottery borrows its randomness from these numbers, so sloppy numbers mean a rigged lottery). Second, a predictable scheme lets pranksters deliberately register a thousand names that all map to shelf 42, flooding it (HashDoS). The defenses map cleanly: demand a scheme with good scatter (avalanche quality), shuffle the scheme secretly every night (per-process random seed — free), and if your door faces the open internet where attackers choose their own names, pay a little speed for a scheme that’s unpredictable even to someone who knows the algorithm (keyed hash).

4.4 Sizing Rule (ratified — v1’s best insight, promoted)

Memory is sized by maximum expected concurrent heavy hitters × safety factor, never by total key cardinality. This is the conceptual unlock of heavy-hitter structures: mice are allowed to collide, evaporate, and churn — only elephants need stable residency, and elephants are few by definition. v2 adds the operator-facing formula: buckets ≥ (expected_concurrent_elephants × safety_factor) / slots_per_bucket, with safety_factor = 4 as the starting default pending THEORY.md occupancy analysis.

🧭 In plain terms: you don’t size the notepad for every human in the city — you size it for how many regulars can physically exist at once, and that number is small by arithmetic, not by hope. If the door sees a million knocks an hour and “regular” means “at least 1% of all knocks,” then there can’t be more than 100 regulars — 100 × 1% is already the whole hour. Everyone else is a mouse, and mice are allowed to be forgotten, miscounted, and overwritten; that’s the deal that makes fixed memory possible. So a page with a few hundred lines tracks a stream of millions of distinct names, forever.

5. Resolution of FP4: Wraparound and Long-Uptime Correctness [NEW]

Defect in v1: “unsigned subtraction wraps perfectly” is true for arithmetic, false for semantics. A slot untouched for a full wrap period (2²⁴ ticks — 19.4 days at the 100 ms tick) reappears with small apparent age: a dead elephant resurrects at near-full effective count (“zombie”), wins eviction defenses, and poisons estimates. The vulnerability window per wrap is small (apparent age < 24 of 2²⁴ positions) but the failure is spectacular and silent — exactly what C6 prohibits.

Wrap cannot be detected locally (indistinguishable by construction), so the fix must be structural. Options:

Option A (Recommended): Bucket-scrub-on-write. Any writer CASing a slot already holds the entire bucket’s cache line in L1. Amend the write path: before competing, opportunistically zero any sibling slot whose apparent age exceeds the evaporation horizon (≥24). Hot buckets scrub continuously for free; a fully idle bucket can harbor a zombie, but harms no one until touched — and the first toucher scrubs before competing. No background mutator (C3 intact), no extra memory traffic (line already resident), one extra in-register pass over 8 words. Residual risk: a zombie in an idle bucket is read (frequency query for a key hashing there) before any write scrubs it — returns an inflated estimate once. Mitigation: read path also treats apparent age ≥ 24 as count 0 (the clamp in §3.2 already guarantees this for ages 24…63; extend the treatment to the wrapped-small-age case by having the scrub be the authority — reads cannot distinguish, hence residual). Quantified in THEORY.md; expected negligible.
Option B: Widen the timestamp (Alt-A 128-bit layout or 32-bit time in a rebalanced word). 32-bit time at 100 ms tick wraps in 13.6 years — beyond C6 concern. Cons: steals 8 bits from count (velocity ceiling drops 256×) or forces 128-bit atomics. Reserved for ports where scrubbing is awkward.
Option C: Background lazy scrubber goroutine. Walks the table slowly, zeroing ancients. Rejected: reintroduces the background mutator C3 exists to eliminate — the structure’s founding thesis. Listed to record why it’s rejected.

🧭 In plain terms — the zombie first: the timestamp works like a wall clock with no date. An entry stamped “3 o’clock” that’s never touched again will, one full lap of the clock later, look like it was stamped just now — a guest who left 19 days ago suddenly reads as a fresh, powerful regular. Worse, this ghost defends its line: real newcomers can’t easily evict something that appears strong. And no one can spot the fake locally, because “stamped 3 o’clock” genuinely looks identical whether it was this lap or last lap — that’s the whole nature of a dateless clock.

The scrub fix: any doorman who’s about to write on a row is already holding that page in his hands — so the rule becomes: while you’re there, glance across the row’s eight lines and erase anything obviously ancient. Busy pages get cleaned constantly as a side effect of normal work, at no extra trips to the shelf. A page nobody touches for 19 days can harbor a ghost — but a page nobody touches also affects nobody, and the very first person to write there erases the ghost before it can defend its line. The janitor was eliminated, and the cleaning still happens.

6. Reference `Observe` — normative pseudocode (composed result of §§2–5)

Observe(key) → (estimate uint32, first bool):
  h        := seededHash(key)                       // §4.3
  bucket   := load cache line at h mod B            // §4.2 one line
  tag      := bits(h, 16)
  scrub any sibling with apparentAge ≥ 24 → 0       // §5 Option A
  if slot with matching tag:
      age  := (now − slot.ts) mod 2²⁴
      eff  := slot.ct >> min(age, 63)               // §3.2
      fold := age > 0
      new  := pack(tag, now, satAdd(eff, 1))        // §3.3
      CAS ≤3 retries, else drop increment           // §3.5
      return (eff+1, fold)
  if empty slot: claim via CAS → return (1, true)
  victim := min-effective slot
  if chip(h, victim):                               // §4.1 Option A
      victim.ct−− via CAS; if 0 → claim → return (1, true)
  return (1, true)                                   // untracked ⇒ rare ⇒ first (§2 Option A)

7. Self-Metrics (carried obligation)

cas_retries_exhausted, evictions, chips, scrubbed_zombies, bucket_overflow_pressure (challenges lost per interval). Cold-path counters; not in the packed word.

8. THEORY.md work queue generated by this spec

Chip-mask schedule vs HeavyKeeper b^−count: protection curve + admission-time bound for new elephants (§4.1 gate).
Bucket overflow probability under Zipfian + churn at recommended sizing; trigger condition for §4.2 Option B.
Fingerprint collision rate (16-bit, 8-way) and its estimate-inflation contribution vs C5.
Zombie residual-read probability under §5 Option A.
Morris-counter variant analysis for slow-tick deployments (§3.6).
Adversarial entropy analysis of hash-derived chipping (keyed-hash requirement boundary).

9. Decisions requiring sign-off

#	Question	Recommended	Alternates
D1	Eviction-loser flag semantics	§2 Option A (true / fail-open)	B (three-valued API)
D2	Eviction mechanism	Decided: Option A, chip-mask schedule M3 — see Document 04	C (HeavyKeeper RNG) — not adopted
D3	Associativity	§4.2 Option A (single bucket), B pre-approved as escape hatch	—
D4	Default hash	xxHash3-class + mandatory seed; keyed hash for adversarial deployments	—
D5	Wraparound defense	§5 Option A (scrub-on-write)	B (wider timestamp) for ports
D6	Word layout	16 FP	24 ts