Rate limiting

A rate limiter caps how much work a client can ask for in a period of time. It protects capacity from runaway scripts and abusive clients, keeps one tenant from starving the rest, puts a ceiling on spend for expensive operations, and slows down attacks such as credential stuffing. The idea is simple; the details — which algorithm, which key, where the counters live, and what happens when the limiter itself fails — decide whether it protects you or becomes a new outage. (The DevSecOps API-gateway lesson configures limits at the edge; this lesson is about designing the limiter itself.)

#Decide what you're limiting

Before choosing an algorithm, answer four questions:

• Who is the client? An API key, a user ID or a tenant if you know who's calling; the IP address for anonymous traffic and login endpoints (accepting that many users can share one IP behind a NAT).
• What does a request cost? A search may cost 100 times a profile read. Charging requests a weight rather than counting them equally makes limits track real load.
• What are the limits for? A burst limit protects servers (20 per second); a quota protects the business (10,000 per day on the free plan). They're often separate rules on the same request.
• Where is it enforced? At the edge (CDN, load balancer or gateway) to stop floods cheaply; in the service for limits that need application knowledge, such as per-tenant plans; and in clients that call your dependencies, so you never exceed a partner API's limits yourself.

#Four algorithms on the same traffic

All four below allow limit requests per window in the long run. They differ in what they allow in the short run. See rate-limiting algorithms for a one-page comparison.

Fixed window. Count requests per aligned window: 12:00:00–12:00:59, 12:01:00–12:01:59, and so on. One counter per key, trivially cheap. The flaw is at the boundary: a client can send a full window's worth at 12:00:59 and another at 12:01:00, twice the limit within two seconds.

Sliding log. Store a timestamp for each accepted request and count those in the last window seconds. Exact — it never lets more than limit requests through in any span of length window — but it stores one entry per request, which is memory-hungry at high limits.

Sliding window counter. Keep fixed-window counters but estimate the sliding count by weighting the previous window by how much of it still overlaps:

estimate = previous_count × (1 − elapsed_in_current / window) + current_count

It needs just two counters per key and is very close to exact. Cloudflare reported it within a fraction of a percent of a true sliding window on real traffic. It slightly over-admits right after a boundary, as you'll see below.

Token bucket. Each key has a bucket holding up to capacity tokens, refilled continuously at rate tokens per second. A request takes a token or is rejected. Capacity sets the burst you tolerate, rate sets the sustained average, and the state is two numbers. It's the most common choice for APIs because "bursts are fine, sustained floods aren't" matches how real clients behave. (A leaky bucket is the mirror image: requests queue and drain at a fixed rate, smoothing output rather than rejecting bursts.)

Run the same traffic through all four. Start with the window-edge traffic and compare the last column of the table; then try the burst.

#Distributed rate limiting

With one server, an in-memory map of counters works. With twenty servers behind a load balancer, each would see only a twentieth of a client's traffic, so per-server counters let the client through at 20 times the intended rate. Three designs, in order of how often you'll see them.

A shared store. Keep the counters in Redis, which every server consults. A fixed window is two commands:

INCR   rl:{api_key}:202610271205      → returns the count for this minute
EXPIRE rl:{api_key}:202610271205 120  (set on the first increment)

Anything more complex must be atomic: if a server reads the token count, decides, and writes the new count in separate commands, two servers can both read "1 token left" and both admit a request. Run the whole decision as a Lua script, which Redis executes without interleaving other commands:

-- KEYS[1] = bucket key; ARGV = capacity, refill per second, cost
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

local t   = redis.call('TIME')                       -- Redis's clock, not each app server's
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts     = tonumber(state[2]) or now

tokens = math.min(capacity, tokens + (now - ts) / 1000 * rate)
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) + 1000)

local retry_ms = 0
if not allowed then retry_ms = math.ceil((cost - tokens) / rate * 1000) end
return { allowed and 1 or 0, math.floor(tokens), retry_ms }

var tokenBucket = redis.NewScript(tokenBucketLua) // the script above; EVALSHA with EVAL fallback

type Decision struct {
	Allowed    bool
	Remaining  int64
	RetryAfter time.Duration
}

func (l *Limiter) Allow(ctx context.Context, key string, cost int) (Decision, error) {
	res, err := tokenBucket.Run(ctx, l.rdb, []string{"rl:" + key}, l.capacity, l.ratePerSec, cost).Int64Slice()
	if err != nil {
		return Decision{}, err
	}
	return Decision{Allowed: res[0] == 1, Remaining: res[1], RetryAfter: time.Duration(res[2]) * time.Millisecond}, nil
}

Using Redis's own TIME avoids clock skew between app servers, which would otherwise let a server with a fast clock mint extra tokens. The key expires once a full bucket's refill time has passed, so idle clients cost no memory. In Redis Cluster, every key a script touches must live in one hash slot; a single key per bucket satisfies that.

Local limits with a global budget. Each server enforces limit / N locally and periodically syncs with the others. No network call per request, at the cost of accuracy when traffic is uneven across servers. Envoy and many gateways combine a local token bucket (cheap, approximate) with a global service for the limits that must be exact.

A dedicated rate-limit service. A small service (Envoy's ratelimit, or your own) owns the counters and answers "allowed?" over gRPC. It centralises rules and metrics, and it's one more dependency on the request path.

#When the limiter fails

If Redis is unreachable, the limiter must choose:

• Fail open (allow everything): the service stays up, but unprotected. Right for most limits that guard against overload, as long as other protections such as load shedding exist.
• Fail closed (reject everything): safe for limits that guard money or security — SMS sends, password attempts, expensive AI calls — where unlimited traffic does real damage.

Either way, give the Redis call a tight timeout (a few milliseconds) so a slow limiter can't slow every request.

#Telling clients what happened

A rejected request should return 429 Too Many Requests with enough information to back off correctly:

HTTP/1.1 429 Too Many Requests
Retry-After: 3
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1793098503
Content-Type: application/problem+json

{"type": "https://api.example.com/errors/rate-limited", "title": "Too many requests", "detail": "Limit of 100 requests per minute exceeded."}

Retry-After is standard HTTP and tells the client how long to wait. The X-RateLimit-* headers are a widespread convention (an IETF draft standardises them as RateLimit and RateLimit-Policy); sending remaining capacity on successful responses too lets well-behaved clients slow down before they hit the wall.

On the client side, the rules are: honour Retry-After; retry 429s and 503s with exponential backoff and jitter, never in a tight loop (retries, backoff and jitter); and run your own token bucket in front of any partner API with a published limit.

#Practice

Design rate limiting for a public REST API with three plans — Free (60 requests per minute, 5,000 per day), Pro (600 per minute, 200,000 per day) and Enterprise (custom). Search requests cost 5 units; everything else costs 1. The API runs on 30 instances behind a gateway. Also protect POST /login against credential stuffing.

Specify the algorithms, keys, where the state lives, the failure behaviour, and the responses.

#Key takeaways

• Decide the client key, the cost of each request, burst limits versus quotas, and where each limit is enforced before choosing an algorithm.
• Fixed windows are cheap but admit up to twice the limit at boundaries; sliding logs are exact but memory-hungry; sliding counters approximate them in two counters.
• Token buckets allow bursts up to capacity and a sustained rate equal to the refill — the usual choice for APIs.
• Distributed limiters need shared state with atomic updates (Redis plus Lua using Redis's clock), or local limits with a global budget.
• Decide deliberately whether to fail open or closed, and keep the limiter's timeout tight.
• Return 429 with Retry-After and remaining-capacity headers; clients should back off with jitter.