Sub-40ns Zero-Allocation Rate Limiting Engine

1. Overview

In high-velocity distributed gateways, rate limiters run on the critical path of every incoming request. Even a tiny 5µs overhead multiplied over 200,000 requests per second consumes an entire CPU core just performing boundary checks.

This laboratory document details the architecture and low-level Go runtime optimizations that enable RateShield to achieve 34.84 nanoseconds per decision with zero heap allocations (0 B/op).

2. The Problem: The Cost of Global Synchronization

Under high concurrency, Go’s sync.RWMutex suffers from CPU cache-line bouncing. When multiple OS threads attempt to read and write to a single synchronized memory location:

CPU cores invalidate their L1/L2 cache lines.
Goroutines are forced into runtime.gopark, triggering thread context switches.
Lock acquisition latency escalates exponentially from nanoseconds to tens of milliseconds.

3. Theory & Mechanics: 64-Shard Partitioning

To scale throughput linearly with CPU core counts, we partition state into $K = 64$ independent shards. Using a power-of-two shard count allows bitwise modulo masking (hash & 63 instead of the expensive hash % 64 division instruction):

$$S_k = \text{FNV-1a}_{64}(\text{key}) \ & \ 0\text{x}3\text{F}$$

Because each shard maintains its own sync.Mutex, concurrent callers with distinct client identifiers (client:ip_1, client:ip_2) operate concurrently without blocking each other.

4. Architecture

                       Request (Key: "tenant:42")
                                 │
                                 ▼
                     FNV-1a 64-bit Hash Function
                                 │
                          hash & 0x3F (0-63)
                                 │
                 ┌───────────────┼───────────────┐
                 ▼               ▼               ▼
           Shard 0 Mutex   Shard 10 Mutex   Shard 63 Mutex
                 │               │               │
                 ▼               ▼               ▼
           Bucket State    Bucket State    Bucket State

5. Implementation: Zero-Allocation Stack Discipline

To guarantee zero allocations, the Go compiler’s escape analysis must prove that local variables never outlive the calling stack frame:

// 1. Avoid returning pointers to short-lived evaluation results
type Result struct {
    Allowed    bool
    Remaining  int64
    Limit      int64
    ResetAfter time.Duration
}

// 2. Return value directly on stack (0 B/op)
func (s *ShardedEngine) Allow(key string, limit int64) (Result, error) {
    shardIdx := fnv1a64(key) & 63
    shard := s.shards[shardIdx]

    shard.mu.Lock()
    // In-place map lookup without temporary string conversion
    b := shard.buckets[key]
    now := time.Now().UnixNano()
    // Refill calculation using int64 arithmetic...
    shard.mu.Unlock()

    return Result{Allowed: true, Remaining: remaining, Limit: limit}, nil
}

6. Benchmarks & Verification

Run locally via go test -bench=. -benchmem:

BenchmarkTokenBucket-8          34458291        34.84 ns/op       0 B/op       0 allocs/op
BenchmarkFixedWindow-8          33890124        35.61 ns/op       0 B/op       0 allocs/op
BenchmarkSlidingWindowCounter-8 31409218        38.16 ns/op       0 B/op       0 allocs/op

Memory profiles (go tool pprof -alloc_space mem.pprof) confirm zero heap allocations during sustained token bucket evaluation.

7. What I Learned

Bitwise operations and pre-sized allocations eliminate compiler-generated heap escape.
Fine-grained mutex sharding often outperforms lock-free atomic CAS spinlocks under heavy write contention in Go because of lower CPU instruction pipeline stalls.
Keeping timestamps as raw int64 nanoseconds avoids monotonic clock struct overhead.

Throughput & Allocation Analyzer