Our gateway terminates traffic for public APIs, and the first thing every unauthenticated request hits is a per-API-key limiter. With 50k active keys and a sustained 100k req/s, the limiting decision has to be made in microseconds, correctly, on every one of them – and the moment we added a naive limiter with a global mutex, the limiter itself became the bottleneck instead of the thing that protects the bottleneck.

The token bucket is the right algorithm for this: a bucket that fills at rate tokens/sec up to capacity, where every request spends one token. Bursts up to capacity are absorbed; sustained load is capped at rate. This post walks through three implementations we shipped, in ascending order of complexity, with the benchmark numbers that decide which one you need.

Version one: mutex, lazy refill

The classic lazy-refill bucket keeps no background timer; it computes elapsed time on demand. A mutex makes it trivially correct:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
type Bucket struct {
	mu       sync.Mutex
	capacity float64
	tokens   float64
	rate     float64 // tokens per second
	last     time.Time
}

func (b *Bucket) Allow() bool {
	b.mu.Lock()
	defer b.mu.Unlock()
	now := time.Now()
	elapsed := now.Sub(b.last).Seconds()
	b.last = now
	b.tokens += elapsed * b.rate
	if b.tokens > b.capacity {
		b.tokens = b.capacity
	}
	if b.tokens >= 1 {
		b.tokens--
		return true
	}
	return false
}

Float drift is a non-issue because tokens are clamped to capacity on every refill. The problem is the lock: when a few thousand goroutines all hit the same key’s bucket at once, they serialize on one mutex and the Allow() call climbs from ~150ns uncontended to microseconds under contention. Under our load profile that was survivable, but it turned up in flame graphs as a flat wall we could not shave.

Version two: lock-free, single word

The insight is that a bucket can be represented as a single atomic value: the unix-nanosecond time at which the next token is available. Allow() is then a CAS loop that hands out a slot if it is close enough to “now”. No floats, no lock, no two-word races:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
type Bucket struct {
	next     int64 // unix nanos of the next available token slot, atomic
	interval int64 // nanos between tokens
	burst    int64
}

func (b *Bucket) Allow() bool {
	now := time.Now().UnixNano()
	for {
		next := atomic.LoadInt64(&b.next)
		if next < now {
			next = now
		}
		// More than (burst-1) intervals in the future means the bucket is empty.
		if next-now > b.interval*(b.burst-1) {
			return false
		}
		if atomic.CompareAndSwapInt64(&b.next, next, next+b.interval) {
			return true
		}
	}
}

This is the variant golang.org/x/time/rate reserves around, and it behaves slightly differently from version one: tokens are handed out evenly spaced rather than in arbitrary clusters. For API limiting that is usually better – it smooths traffic instead of admitting a burst of capacity requests in the same millisecond. Keep b.interval and b.burst adjacent and 64-bit aligned; CAS on a misaligned word panics on some platforms.

Uncontended, the lock-free version runs ~50ns per Allow() – about three times faster than the mutex version – and under contention it degrades gracefully: failed CAS attempts just retry, so nobody waits on a lock hold. That was enough to make our per-key path disappear from the flame graph.

Version three: distributed

A single-node bucket does not limit traffic spread across N gateway replicas; each replica happily spends from its own full bucket. For global hard limits we push the bucket into Redis and let a Lua script make the read-modify-write atomic:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
local key      = KEYS[1]
local rate     = tonumber(ARGV[1]) -- tokens per second
local capacity = tonumber(ARGV[2])
local now      = tonumber(ARGV[3])
local tokens   = tonumber(redis.call('GET', key) or capacity)
local last     = tonumber(redis.call('GET', key..':ts') or now)

tokens = math.min(capacity, tokens + (now - last) * rate / 1000)
redis.call('SET', key..':ts', now)
if tokens >= 1 then
    redis.call('SET', key, tokens - 1)
    return 1
else
    redis.call('SET', key, tokens)
    return 0
end

Call it with EVALSHA and reuse the script digest, not EVAL, or the script-cache miss on every call becomes its own bottleneck. A Redis round trip is ~0.5ms, so this is for coarse, low-rate hard limits – login attempts, signup floods – not for the 100k req/s per-key path. That path stays on the local buckets.

Production lessons

• Start with version one, profile, then reach for the CAS version only if the lock shows up in measurements. We over-engineered our first attempt and the lock was never the issue at low traffic.
• Shard buckets per key instead of one global bucket; we use 256 shards so a hot key cannot serialize traffic for all keys.
• Check the limiter before doing the expensive work it protects, and return 429 with a Retry-After header. A limiter checked after the work is just a timer for the abuse you already absorbed.
• Clock and timer pitfalls are real: time.Now() uses the monotonic clock for Sub since Go 1.9, so wall-clock jumps do not corrupt refills. Do not run a background refill timer; lazy refill on read is simpler and cheaper.