Lock-Free, Zero-Allocations, and 21ns Ops: Under the Hood of EpochSketch

A deep dive into atomic Compare-And-Swap (CAS), bit-chipping eviction lotteries, and benchmarking concurrent data structures in Go.

In Part 1, we explored Interpreted Decay — calculating recency-weighted frequency on-the-fly at read time (count >> age) without spawning a background cleanup thread.

By packing tag:16, epoch:24, and count:24 into a single 64-bit word (uint64), every entry fits neatly inside a CPU register.

But architectural design is only half the battle. When dozens of goroutines race to update the same memory slots concurrently, three immediate systems questions arise:

1. How are multi-threaded writes handled without locks or GC pauses?
2. What happens when a bucket is completely full and a new key arrives?
3. What trade-offs occur when threads collide under heavy contention?

Here is a look under the hood at how these mechanics work, how the bit-chipping eviction lottery operates, and what the benchmark numbers look like.

1. The 3-Phase Lock-Free Protocol

Every write operation (sk.Observe(key)) executes a 3-phase lock-free state machine. Because each entry is a single 64-bit word, all state transitions are performed using atomic Compare-And-Swap (CAS) operations via Go’s sync/atomic package.

Incoming Request (Observe)
           │
           ▼
 ┌───────────────────┐     Found?
 │  Phase 1: Refresh │───────────────► CAS Increment & Return (Done)
 └───────────────────┘
           │ No
           ▼
 ┌───────────────────┐     Empty Slot?
 │  Phase 2: Claim   │───────────────► CAS Claim Slot (Done)
 └───────────────────┘
           │ Full Bucket
           ▼
 ┌───────────────────┐
 │  Phase 3: Evict   │───────────────► Run Chip-Mask Lottery (CAS Result)
 └───────────────────┘

Phase 1: Refresh

The thread scans the target bucket for a live slot carrying a matching 16-bit tag. If found, it reads the current count, applies any elapsed decay, increments the count by 1, updates the epoch timestamp, and attempts an atomic CAS write.

Phase 2: Claim

If no tag match exists, the thread scans for an empty or dead slot (effective count == 0). If an empty slot is found, it claims the slot via CAS for the new key.

Phase 3: Evict (When Buckets Are Full)

If all slots in the bucket are occupied by live keys, the engine cannot simply overwrite an existing entry. Doing so would make the data structure vulnerable to cache pollution (where a sudden burst of random keys wipes out legitimate high-frequency keys). Instead, it triggers the Bit-Chipping Eviction Lottery.

2. The Bit-Chipping Eviction Lottery

When a bucket is full, the thread nominates the "weakest" slot (the entry with the lowest effective count) to compete against the incoming key.

Instead of an immediate takeover, the challenger must win a hash-entropy lottery:

Challenger Key  ──► [ Hash Lottery ] ──► Outcome:
                                          ├── BOUNCE:   Challenger dropped (Victim intact)
                                          ├── CHIP:     Victim count reduced by 1 (Victim stays)
                                          └── TAKEOVER: Victim count hits 0 → Challenger claims slot!

There are three possible outcomes from this lottery:

1. Bounce: The challenger loses the lottery. The incoming request is dropped, leaving the existing victim slot completely untouched.
2. Chip: The challenger wins a partial victory! The victim slot is not evicted, but its count is "chipped" (reduced by 1: count--). The victim keeps its slot.
3. Takeover: The challenger wins, and the victim's count was already down to 1. Chipping it reduces the count to 0, allowing the challenger to claim the slot via CAS!

This bit-chipping mechanic ensures that established, high-frequency keys can easily survive occasional collisions, while persistent heavy callers gradually chip away resistance and claim their rightful slot.

3. Bounded CAS Retries & Safe Undercounting

What happens under heavy multi-threaded contention when multiple goroutines try to update the exact same bucket simultaneously?

In traditional lock-free designs, a thread that loses a CAS race loops infinitely until it succeeds. Under heavy core counts, this causes livelock and CPU thrashing.

To prevent this, EpochSketch bounds all CAS operations to a maximum of 3 retries.

If a goroutine exhausts 3 retries without committing its CAS update, it aborts the attempt and returns:

// Safe direction bias under contention:
// If CAS retries exhaust, drop the increment, return the read estimate,
// and set first = true (Fail-Open).

Why Fail-Open is Safe for Production:

In rate limiting, API gateways, and proxy defenses, dropping an increment under extreme contention results in slight undercounting.

• Undercounting (Fail-Open): At worst, a client gets one extra request allowed. The system stays responsive.
• Overcounting (Fail-Closed): Inflating counts causes false positives, accidentally blocking legitimate users.

By dropping the increment on CAS exhaustion, the system guarantees safety direction (under-counting, never over-counting) and bounds per-operation latency even under pathological contention.

4. Benchmark Numbers: 21ns & Zero Allocations

Benchmarking concurrent data structures requires rigorous measurement across core counts (GOMAXPROCS).

Here are production benchmarks recorded on an Apple M4 Pro (12 cores) running Go's native benchmark suite (go test -bench=. -benchmem):

1. Single-Threaded Throughput

BenchmarkSketch_Observe_SingleThreaded-12    1000000    20.95 ns/op    0 B/op    0 allocs/op

• ~21 nanoseconds per operation.
• Zero heap allocations (0 B/op).

2. Multi-Threaded Core Scaling across GOMAXPROCS

When worker goroutines operate across bucket windows, throughput scales near-linearly without latency degradation:

Per-operation latency stays flat (~30–32 ns) even as core count rises to 12, demonstrating zero lock contention across threads.

5. Lessons from the Benchmark Harness

Engineering open-source data structures often reveals subtle surprises during benchmarking.

When testing eviction salt sources across threads, early benchmarks showed unexpected performance degradation at high core counts. Upon deeper investigation into cache lines, it turned out that shared atomic counters were suffering from false sharing — where adjacent CPU cores invalidated each other's L1 cache lines.

By adding explicit cache-line padding ([cacheLineSize - 8]byte) to salt counter structs, CPU cache-line bouncing was completely eliminated.

Documenting these harness findings transparently in the design helped ground the design in empirical evidence.

Summary

Combining single-word 64-bit bit packing with atomic CAS operations delivers:

• Lock-free concurrency with 0 heap allocations.
• Bit-chipping eviction to protect against cache pollution.
• Fail-open safety that bounds latency under heavy contention.

💡 Watch it work live: You can dissect every Phase 1 refresh, Phase 2 claim, and Phase 3 bit-chipping eviction frame-by-frame using the interactive browser simulator at epochsketch.dev (or view epochsketch-simulator).

In **Part 3, the focus shifts to real-world applications: building **SketchProxy* — a zero-database, fixed-memory reverse proxy for API rate limiting, tarpitting, and wallet defense.*