Rate Limiting: Token Buckets and Sliding Windows

July 10, 2026 · distributed-systems · system-design · go

A rate limiter answers one question — "has this client done too much, too fast?" — and the naive answers are all subtly wrong. Here's the tour.

The algorithms

Algorithm	Idea	Weakness
Fixed window	Count requests per calendar minute	Bursts at the window edge allow 2× the limit
Sliding log	Store a timestamp per request	Exact, but memory grows with traffic
Sliding window counter	Weight the previous window's count	Approximate, but cheap and smooth
Token bucket	Refill tokens at a fixed rate, spend one per request	Allows bursts up to the bucket size
Leaky bucket	Queue requests, drain at a constant rate	Adds latency; shapes rather than rejects

The fixed window trap is worth seeing. With a limit of 100/minute, a client can send 100 requests at 00:59.9 and 100 more at 01:00.1 — 200 requests in 200 milliseconds, every one of them "within limits."

Token bucket, in detail

Token bucket is the workhorse: simple, burst-friendly, and cheap to store — just two numbers per client.

A bucket holds up to capacity tokens.
Tokens refill at rate per second, never exceeding the cap.
Each request spends one token. No token, no service.

You don't need a background timer to refill it — compute the refill lazily from elapsed time whenever a request arrives:

type Bucket struct {
    capacity, tokens, rate float64
    last                   time.Time
}

func (b *Bucket) Allow(now time.Time) bool {
    elapsed := now.Sub(b.last).Seconds()
    b.tokens = math.Min(b.capacity, b.tokens+elapsed*b.rate)
    b.last = now
    if b.tokens >= 1 {
        b.tokens--
        return true
    }
    return false
}

capacity sets how large a burst you tolerate; rate sets the steady state. A capacity of 10 with a rate of 1/s lets a quiet client save up ten requests and spend them at once, then settle to one per second.

Making it distributed

The code above is per-process. Behind a load balancer with ten app servers, each keeps its own bucket and the effective limit becomes 10× what you configured.

The usual fix is to move the counter into a shared store — Redis — and make the read-modify-write atomic, or two concurrent requests will both read "1 token left" and both spend it:

-- INCR-and-check as a single atomic step
local n = redis.call('INCR', KEYS[1])
if n == 1 then redis.call('EXPIRE', KEYS[1], window) end
return n

The trade-off is a network hop on every request and a hot key for noisy clients. Common middle grounds: shard the key across slots, or let each server enforce a local limit/N and reconcile asynchronously.

Tell the client

However you count, be honest at the edge. Return 429 Too Many Requests, a Retry-After header so well-behaved clients back off, and X-RateLimit-* headers so they can self-throttle before you have to:

HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0

A good limiter protects the service and tells clients exactly how to behave. That second part is what turns a retry storm into a polite queue.