← Writing

Building Resilient Rate Limiters Without Killing Tail Latency

Practical trade-offs behind distributed token buckets, atomic Lua scripts, and graceful degradation when your quota store slows down.

On this page4 sections

Rate limiting looks deceptively simple on a whiteboard: count requests per key, reject anything over budget. In production, the hard parts show up at the edges—bursty clients, clock skew across instances, and what happens to your API’s p99 latency when the backing store hiccups.

This note walks through a clean token-bucket implementation in Go and the failure modes worth designing for up front.

Why Token Buckets Hold Up Well

A fixed-window counter resets abruptly on minute boundaries, letting a client send 2 × limit requests across a boundary second. A token bucket avoids boundary spikes while still allowing short, legitimate bursts up to a configured capacity.

Each key stores just two numbers:

  • tokens: remaining capacity at the last check
  • last_refill_ms: timestamp of the previous update

On every request, we calculate how many tokens have accrued since last_refill_ms, clamp the sum to capacity CC, and consume cost kk if available in O(1)O(1) time:

tavail=min⁡ ⁣(C,  tprev+r⋅max⁡(0,  now−tlast))t_{\text{avail}} = \min\!\Bigl(C,\; t_{\text{prev}} + r \cdot \max\bigl(0,\; \text{now} - t_{\text{last}}\bigr)\Bigr)

Distributed token bucket architecture showing client, API gateway, and Redis Lua script

Here is the end-to-end decision flow—including the bounded timeout path when Redis degrades:

Keeping the Read-Modify-Write Atomic

If multiple gateway replicas run GET, compute tokens locally, and call SET, concurrent requests will race and silently overshoot the quota. Moving the refill calculation into a single Redis Lua script eliminates the race and reduces network overhead to one round trip.

token_bucket.lua
local key = KEYS[1]
local rate = tonumber(ARGV[1]) -- tokens per millisecond
local capacity = tonumber(ARGV[2]) -- max burst size
local now_ms = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])
local state = redis.call("HMGET", key, "tokens", "ts")
local tokens = tonumber(state[1]) or capacity
local last_ts = tonumber(state[2]) or now_ms
local elapsed = math.max(0, now_ms - last_ts)
tokens = math.min(capacity, tokens + elapsed * rate)
if tokens < cost then
return {0, tokens}
end
tokens = tokens - cost
redis.call("HSET", key, "tokens", tokens, "ts", now_ms)
redis.call("PEXPIRE", key, math.ceil(capacity / rate) * 2)
return {1, tokens}

Using the server’s clock (or passing a monotonic-bounded timestamp) keeps refill math consistent across stateless API replicas.

Enforcing Tight Timeouts in Go

A rate limiter sits on the critical path of every incoming request. If Redis stalls for 300ms, your limiter should never drag down your entire service. Wrap the call in a strict context budget and choose an explicit failure policy (fail-open for user-facing read endpoints, fail-closed for sensitive or expensive write paths).

limiter.go
package limiter
import (
"context"
"time"
)
type Decision struct {
Allowed bool
Remaining float64
}
func (l *Limiter) Allow(ctx context.Context, key string) Decision {
// Cap quota check latency so a slow store never blocks the request path.
checkCtx, cancel := context.WithTimeout(ctx, 15*time.Millisecond)
defer cancel()
allowed, remaining, err := l.evalBucket(checkCtx, key)
if err != nil {
l.metrics.IncStoreError()
return Decision{Allowed: l.failOpen, Remaining: -1}
}
return Decision{Allowed: allowed, Remaining: remaining}
}

A rate limiter’s job is to protect downstream stability. If the limiter itself becomes your highest-latency dependency, it has inverted its purpose.

Practical Checklist

Before shipping a distributed limiter to production:

  1. Return Retry-After headers on 429 Too Many Requests responses so well-behaved clients back off cleanly.
  2. Add an in-process circuit breaker around the Redis client so a dead shard fails fast in microseconds instead of waiting for every 15ms timeout.
  3. Separate burst capacity from sustained rate—most interactive APIs feel noticeably smoother with a small burst allowance.
  4. Emit separate metrics for allowed, throttled, and store_error so you notice silent fail-open events immediately.