A rate limiter that works on a single process is easy. A rate limiter that works when the service behind it is ten replicas behind a load balancer — where consecutive requests from the same client can land on different machines with different memories — is a different problem entirely. Yet most production traffic today runs through horizontally scaled deployments, and the naive answer of “check a counter in memory” silently multiplies every client’s quota by the replica count.
This post walks through the standard limiting algorithms, where each one breaks, and how to build a limiter whose counter survives across instances: an in-process token bucket for the single-node case, and a Redis-backed counter with the atomicity done correctly for the distributed one.
Four Algorithms and Where They Break
Almost every limiter in production is a variation of one of four designs, and each has a characteristic failure mode:
- Fixed window counter. Count requests per discrete interval (say, one minute) and reject when the count exceeds the limit. Cheap and simple, but the window boundary is exploitable: a client can send a full quota at 10:59 and another full quota at 11:00, doubling its effective rate across the seam.
- Sliding window log. Store a timestamp per request and reject when the number of timestamps inside the trailing interval exceeds the limit. Exact, but memory cost scales with request rate — at thousands of requests per second per key, the log itself becomes the bottleneck.
- Sliding window counter. A weighted blend of the current and previous fixed windows, where the previous window contributes proportionally to how much of it has elapsed. It approximates the sliding log’s fairness at a fraction of the memory, at the cost of small approximation errors near the boundary.
- Token bucket. A bucket holds up to
bursttokens, refills continuously atratetokens per second, and each request consumes one. Its short-term bursts are absorbed by the bucket while the long-term average converges to the refill rate — which is exactly the shape most APIs want to allow. This is the algorithm behind most HTTP middleware limiters.
For single-process services, the token bucket is the right default, and in Go it is already implemented in the standard extended libraries. For distributed deployments, the counter has to live somewhere every replica can reach — which is where Redis comes in.
In-Process Token Buckets
The golang.org/x/time/rate package implements a thread-safe token bucket with two knobs: the sustained rate and the burst size. Wrapping it around an HTTP handler is a few lines:
package main
import (
"net/http"
"golang.org/x/time/rate"
)
func withRateLimit(next http.Handler, lim *rate.Limiter) http.Handler {
return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
if !lim.Allow() {
w.Header().Set("Retry-After", "1")
http.Error(w, "rate limit exceeded", http.StatusTooManyRequests)
return
}
next.ServeHTTP(w, r)
})
}
func main() {
// 100 requests/second sustained, bursts up to 200.
lim := rate.NewLimiter(rate.Limit(100), 200)
mux := http.NewServeMux()
mux.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
w.Write([]byte("ok"))
})
http.ListenAndServe(":8080", withRateLimit(mux, lim))
}Allow() is the drop-on-exceed variant. When you prefer queueing over rejecting, Wait(ctx) blocks until a token is available or the context is cancelled — useful for limiting calls to a downstream dependency, where slowing down is better than failing. The distinction matters: outbound throttling wants Wait, inbound protection wants Allow.
The catch is the one this post started with. Put this limiter behind a load balancer with N replicas and each replica enforces its own 100 req/s budget: the fleet-wide ceiling becomes N × 100, and per-client fairness disappears entirely because the load balancer decides which counter a given request sees.
Moving the Counter to Redis
The distributed version keeps the same algorithms but moves the state into a store every replica shares. Redis is the usual choice because its single-threaded command execution makes atomic check-and-increment straightforward — if you combine the steps correctly. The Go examples below use the official go-redis client. The classic mistake is doing INCR and EXPIRE as two separate commands from the client: between them, a crash or a race can leave a key with no TTL, which then blocks that client forever. The fix is a Lua script, which Redis executes atomically — the script mechanism is documented under the EVAL command, and INCR itself documents the counter pattern.
package main
import (
"context"
"fmt"
"github.com/redis/go-redis/v9"
)
const allowScript = `
local n = redis.call('INCR', KEYS[1])
if n == 1 then
redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return n
`
func allow(rdb *redis.Client, key string, limit, windowSec int) (bool, error) {
ctx := context.Background()
n, err := rdb.Eval(ctx, allowScript, []string{key}, windowSec).Int()
if err != nil {
return false, err
}
return n <= limit, nil
}
func main() {
rdb := redis.NewClient(&redis.Options{Addr: "localhost:6379"})
ok, err := allow(rdb, "rl:user:42:1731465600", 100, 60)
fmt.Println(ok, err)
}Several details in this small function carry most of the correctness weight. The key embeds the window’s start timestamp rather than a formatted wall-clock time, so every replica computes the same key regardless of local clock skew — the TTL does the timekeeping, not application clocks. The script returns the current count and lets the caller compare it against the limit, so the same script can enforce any quota. And because the counter lives in Redis with a TTL, replicas can come and go without the quota changing.
This is still the fixed window algorithm, so it inherits the boundary-burst problem. Upgrading to a sliding window in Redis is usually done with sorted sets: each request adds its timestamp as a member, old members are trimmed with ZREMRANGEBYSCORE, and the count comes from ZCARD — all inside one script so the read-modify-write stays atomic. The memory trade-off is real (one entry per request per window), so high-traffic keys often settle on the sliding window counter approximation instead: two fixed-window counters plus a weighted average of the previous one, computed in the same Lua script.
There is a third family worth knowing: GCRA (Generic Cell Rate Algorithm), borrowed from telecom traffic shaping. It stores only a single timestamp per key — the moment the bucket would next be full — and derives both the burst allowance and the sustained rate from that one value. It is what most industrial-strength distributed limiters implement, because it gives token-bucket semantics with O(1) memory per key. If your limiting needs outgrow simple counters, that is the design to study.
Production Considerations
A few decisions matter more than the algorithm choice itself:
- Key granularity. Per-API-key limits are fair but create unbounded key cardinality — every abusive client mints new keys. Combining per-key and per-IP (or per-route) counters bounds the blast radius of both quota exhaustion and key rotation.
- Fail-open or fail-closed. If Redis is down, does the limiter allow everything (fail-open, protecting the dependency but not your backend) or reject everything (fail-closed, protecting the backend but turning a cache outage into a full outage)? For inbound protection on non-critical paths, fail-open with an alert is the common choice; for expensive downstream calls, fail-closed.
- Client signaling. Rejecting with HTTP 429 and a
Retry-Afterheader turns a hard failure into a coordination mechanism — well-behaved clients back off instead of retrying into the limit. - Latency budget. A distributed limiter adds a network round trip to every request. If that is too much, the standard hybrid is an in-process token bucket sized at quota ÷ N as a fast path, with the Redis counter as the authoritative backstop — slightly lossy, but it keeps the hot path local.
Wrapping Up
The algorithm is rarely where distributed rate limiting goes wrong. Fixed windows, sliding logs, and token buckets are all well understood; the failures come from state that doesn’t survive a replica boundary, non-atomic check-and-increment sequences, and clock assumptions that break the moment more than one machine computes the window key. Keep the counter in one shared place, make the counter update atomic, let the store’s TTL do the timekeeping, and tell clients what happened with a proper 429 — the algorithm on top of that foundation is almost an implementation detail.