06 · Salt Contention Decision

Status: decided — the eviction salt stays a single shared, cache-line-padded counter by default. §6 records a later addendum: a sharded opt-in now ships alongside it (Config.ShardedEvictionSalt), for deployments that hit this doc’s revisit trigger without waiting for it to become the only path forward. This document records the evidence. Scope: the production engine’s Phase 3 eviction salt (Doc 03.3 §3 Ingredient 3). Supersedes Doc 05 §4, whose table predates the benchmark-isolation fixes described in §2 below and whose conclusion was left open. Hardware: Apple M4 Pro (12 logical CPUs), darwin/arm64, go test -bench without the race detector. Date: 2026-08-02. Evidence: BenchmarkPhase3Evict_SharedSalt / BenchmarkPhase3Evict_PerGoroutineSalt, BenchmarkSketch_Observe_Parallel (benchmark_test.go); decision comment on evictionSalt in eviction.go.

1. Background: what the salt is and why contention was flagged

When a key hashes to a bucket entirely full of live entries, Observe runs the Phase 3 eviction lottery: the weakest occupant is nominated and the challenger wins the right to chip it down with probability 2⁻ᵏ. Hash bits alone would make that draw static — the same challenger meeting the same victim would draw the same number forever, so an unlucky pairing would stay unlucky permanently, and an adversary could hunt for such pairings.

The ratified fix (Doc 03.3 §3, Ingredient 3) is a structure-wide attempt counter: every eviction attempt increments one shared atomic.Uint64 and folds the fresh value into its draw. The counter never repeats, so no two draws are ever identical. That global uniqueness is the security property — which is why a per-goroutine counter is not a shippable alternative, only a benchmark instrument.

The ticket-dispenser picture. Think of a deli with one take-a-number dispenser. Every eviction attempt must pull a ticket, and the whole point is that ticket numbers are never reused — that is what keeps the lottery fair and ungameable. One dispenser for the entire store guarantees uniqueness, but at rush hour every clerk reaches for the same device. Padding the salt to its own cache line is giving the dispenser its own table so nobody bumps it by accident (no false sharing). But if eight clerks genuinely need tickets at once, they still queue at one dispenser — that queue is true sharing, and no amount of table-arranging removes it. The open question was: how fast can the dispenser go, and does the store ever get busy enough to care?

2. Measurement design

Two benchmarks run an identical eviction-saturated workload — a fully live 1,024-bucket table where every call goes straight to Phase 3 — differing in exactly one thing: variant A uses the real shared salt, variant B gives each goroutine a private one. Any parallel gap between them is the cost of sharing the word.

Two isolation fixes were required before the numbers meant anything (both are why Doc 05 §4’s earlier table is superseded):

Disjoint bucket windows. Workers previously walked buckets in lockstep, so bucket-word CAS contention dominated both variants identically and buried the salt signal. Each worker now owns a private 64-bucket range.
Per-worker stats. The shared metrics counters do an atomic add per successful evict — a second contended word contaminating the A/B. Each worker now gets private stats.

After both fixes, the salt is the only cross-core write in the shared variant. Whatever gap appears is the dispenser, and nothing else.

3. Results

GOMAXPROCS	Shared salt (ns/op)	Private salt (ns/op)	Shared (M attempts/s)	Private (M attempts/s)	5-run spread (shared / private)
1	12.69	12.73	78.8	78.6	12.53–12.84 / 12.76–12.88
2	19.34	7.54	51.7	132.7	single sweep
4	31.42	4.85	31.8	206.1	single sweep
8	41.35	3.44	24.2	290.4	37.4–41.7 / 1.71–4.81

(ns/op is wall-clock per completed operation system-wide under b.RunParallel, so throughput = 1 / ns/op across all cores. The private variant’s 8-core spread reflects scheduler placement; even its worst run is ~8× the shared ceiling.)

Context measurement — the demand side:

Measurement	ns/op	System throughput
Full `Observe`, parallel, production-size table, 8 cores	32.9	≈ 30.4 M ops/s
Shared-salt ceiling, 8 cores (5-run mean 39.2 ns/op)	39.2	≈ 25.5 M attempts/s

Three facts fall out:

At 1 core the shared salt is free. 12.69 vs 12.73 ns — an uncontended atomic add disappears next to the bucket scan. Whatever cost exists is purely a contention phenomenon.
Under contention it anti-scales. The shared variant gets slower with every core added: 8 cores complete fewer eviction attempts per second (24.2 M/s) than a single core does (78.8 M/s). Each add must yank the salt’s cache line, exclusive, from whichever core last held it — at 8 contenders that ping-pong costs ~40 ns per attempt. Cache-line padding demonstrably did not fix this; the dispenser tops out near 25 M tickets/s.
The isolated baseline confirms the attribution. With private salts and nothing else changed, the same code scales near-linearly to 290 M/s. The entire gap — roughly 12× at 8 cores — is the one shared word.

4. Why the shared salt stays anyway

The isolation benchmark is a deliberately impossible workload: a hot-in-cache loop where 100% of operations are eviction attempts. Real traffic reaches Phase 3 through the full Observe path — hash, bucket scan, refresh or claim — and at production table sizes that path is memory-bound at ≈ 30.4 M ops/s on this machine with all 8 benchmark cores. That number is the demand side of the dispenser.

Salt traffic is observe rate × phase-3 fraction. For the 25.5 M/s ceiling to bind at all, roughly 84% of every observe in the system would have to end in an eviction attempt — a table so undersized that nearly every key hashes into a full bucket. The design explicitly prevents this regime: THEORY.md item 2’s sizing analysis bounds bucket-overflow probability to the low single digits at recommended sizing. And even in the pathological worst case the failure is soft: throughput degrades from ~30 M/s to ~25 M/s — a ≈16% haircut, each call still ~40 ns, bounded, livelock-free, correctness untouched.

Worked example — the telemetry sampler (Doc 01 §4 example A). Put the sampler on this 8-core box at 5 million events/s — a heavy real-world load — with a correctly sized table where ~1% of observes overflow into Phase 3:

Salt demand: 5 M × 1% = 50,000 tickets/s
Dispenser capacity: 25,500,000 tickets/s
Utilization: 0.2% — the queue at the dispenser never forms.

Now break it on purpose: shrink the table 100× so every single observe fights for a full bucket. Demand becomes the full 30.4 M/s against a 25.5 M/s ceiling — the sampler drops to ~25 M events/s instead of 30. Painful, but that deployment’s real problem is a table 100× too small; the salt turned a gross misconfiguration into a 16% slowdown, not an outage.

What escalating would cost. The escalation path — per-core counters with distinct high bits — would likely preserve global uniqueness, but it amends a ratified design ingredient (Doc 03.3 §3) whose entropy properties were validated as-built by THEORY.md item 6’s adversarial analysis (PASS at ratio 0.9942). Changing the construction reopens that validation. Paying a re-derivation and re-validation bill to speed up a regime no target deployment can reach is the wrong trade.

5. Decision

The eviction salt stays a single shared, cache-line-padded counter. Evidence: its contended ceiling (~25.5 M adds/s at 8 cores) exceeds any phase-3 demand the full pipeline can generate (~30.4 M observes/s total, of which evictions are a small fraction at recommended sizing). Recorded in the evictionSalt comment in eviction.go; reproducible via go test -bench Phase3Evict -cpu=1,2,4,8.

Revisit trigger: the contended ceiling shrinks as core count grows while the memory-bound pipeline rises with it — the margin narrows on big machines. If a target deployment combines high core counts (≫8) with sustained heavy churn, re-run the A/B there before trusting this verdict.

6. Addendum: sharded opt-in ships (2026-08-03)

Rather than wait for the revisit trigger above to actually fire in some deployment, the escalation path is shipped now as an explicit opt-in — Config.ShardedEvictionSalt — coexisting with the default shared counter. §1–§5 above are left as the original, frozen analysis; this section records what shipped and why it doesn’t reopen anything §4 worried about reopening.

Mechanism. Not §4’s imagined “distinct high bits” — that spends bits on a shard ID and shrinks the per-shard counter’s range for no real benefit at 64 bits. What shipped instead: numShards cache-line-padded counters, shard i seeded to i and incremented by numShards per draw, so shard i’s sequence (i+numShards, i+2·numShards, ...) occupies residue class i mod numShards — disjoint from every other shard’s, using the full 64-bit space. numShards == 1 (the default) reproduces the original flat counter’s exact sequence.

Shard selection uses challengerSpare’s low bits (the hash’s top 32 bits, already independent of the bucket-index and fingerprint bits, and already folded into the draw) — no new parameter threading, no per-goroutine or thread-local state.

Why THEORY.md item 6 does not need to be re-run. Item 6’s adversarial analysis leans on the salt being a structure-wide counter guaranteed fresh — never repeating — per attempt. It does not depend on that counter being one physical word. The sharded construction’s disjoint-residue-class arithmetic guarantees the identical never-repeats property by construction: no two shards can ever emit the same value, and each shard’s own sequence is strictly increasing. What changed is which word a given attempt increments, not the contract item 6’s laundering argument relies on. No re-derivation, no re-validation bill.

Shard count. Derived once at New() time from runtime.GOMAXPROCS(0), rounded up to the next power of two, capped at 32. The cap matters honestly: this doc’s own benchmark hardware (§ intro) only goes to 12 cores, so effectiveness at higher shard/core counts up to the cap is a reasonable extrapolation, not a measured fact. Read once at construction, never re-checked — consistent with New() already not being purely deterministic (the default hasher self-seeds from crypto/rand per instance).

Measurements (same M4 Pro, 12 logical CPUs, go test -bench, 2026-08-03). An initial -benchtime=1s pass was cross-checked against -benchtime=5s and -benchtime=10s reruns before trusting any number here — short runs turned out to understate sharding’s benefit and produced one outright misleading data point (sharded end-to-end at 2 cores: 78.08 ns/op at 1s, worse than shared, vs. 48.38/48.33 ns/op at 5s/10s). The 5s and 10s numbers agree with each other within a few percent at every core count, for both variants, with no drift between them — the sharded advantage is a steady-state property, not a warm-up artifact or something that erodes under sustained load. The tables below report 5s and 10s side by side; the 1s pass is not reproduced.

Isolated eviction lottery (BenchmarkPhase3Evict_SharedSalt vs BenchmarkPhase3Evict_ShardedSalt, 8 shards, same eviction-saturated setup as §2):

GOMAXPROCS	Shared 5s (ns/op)	Shared 10s (ns/op)	Sharded 5s (ns/op)	Sharded 10s (ns/op)	Shared 10s (M/s)	Sharded 10s (M/s)
1	12.40	13.44	12.86	13.42	74.4	74.5
2	17.37	17.89	12.71	12.96	55.9	77.2
4	29.08	29.15	13.86	15.87	34.3	63.0
8	36.55	39.31	14.76	14.96	25.4	66.8

At 8 cores, sharding is 2.5–2.6× the dispenser’s throughput (25.4 → 66.8 M attempts/s at 10s) — real, and stronger than the 1s pass initially suggested, but still well short of the fully-isolated per-goroutine ceiling (§3’s instrument, ~234 M/s at 8 cores): 8 shards still means 8 counters absorbing traffic from potentially many more concurrent workers, so some residual contention within each shard is expected and matches the mechanism, not a bug.

End-to-end, through the public API (BenchmarkSketch_Observe_EvictionHeavy_SharedSalt vs ..._ShardedSalt): every bucket pre-filled fully live, keys chosen so essentially every Observe call falls through to Phase 3:

GOMAXPROCS	Shared 5s (ns/op)	Shared 10s (ns/op)	Sharded 5s (ns/op)	Sharded 10s (ns/op)
1	40.17	41.80	40.66	41.80
2	52.51	52.76	48.38	48.33
4	56.28	55.27	51.38	49.83
8	58.90	59.27	50.77	39.25

At 8 cores, sharding cuts the pathological (100%-Phase-3) worst case’s latency by 14–34% across the two longer runs (58.90→50.77 at 5s, 59.27→39.25 at 10s) — noisier than the isolated numbers since most of Observe’s cost (hash, bucket scan, CAS) is untouched by this change and the salt is only ever a fraction of it, per §4’s demand-side argument (the same reason §5 didn’t require this to ship alongside the shared default). Direction is consistent across every duration measured, including the discarded 1s pass: sharded never loses to shared at 8 cores.

Residual caveat, not a blocker. Shard selection reuses spare’s bits, already folded into the draw. Doc 03.3 §5’s threat model already assumes an adversary who knows the unkeyed hash and can bias spare’s low bits; such an adversary could concentrate their own attack traffic onto a single shard, locally reconstructing something like the single-counter contention profile for that traffic. This is a throughput caveat under a specific, already-accepted adversarial model — it does not weaken the never-repeats/uniqueness guarantee or any correctness property.

Guidance. Shared stays the default: it’s free until contended, and §4/§5’s demand-side argument (realistic phase-3 fractions rarely approach the contended ceiling at recommended sizing) still holds. Enable ShardedEvictionSalt if profiling shows real eviction-heavy contention at high core counts — not preemptively.