Rate limiting: algorithms, keys and what to do when you hit the limit

Which algorithm should you use?

Token bucket is the default we reach for. It has two intuitive parameters — bucket size (how big a burst you tolerate) and refill rate (the sustained limit) — which map directly to how product owners think about limits.

What should you use as the rate limit key?

The most specific stable identity available: API key, then user id, then session, and IP address only as a last resort.

• IP addresses are shared by offices, universities, mobile carriers and NAT gateways. Limiting by IP throttles legitimate groups of users together.
• IPv6 clients can rotate addresses cheaply — limit by /64 prefix rather than exact address.
• For unauthenticated endpoints (signup, login, password reset), combine IP with the submitted identifier so one attacker cannot lock out a real account.
• Apply different limits per endpoint class: reads generous, writes tighter, expensive operations tightest.

How do you implement it across multiple instances?

-- Atomic token bucket in Redis (called via EVAL)
local tokens = tonumber(redis.call("HGET", KEYS[1], "tokens") or ARGV[1])
local last   = tonumber(redis.call("HGET", KEYS[1], "ts") or ARGV[3])
local delta  = math.max(0, ARGV[3] - last)
tokens = math.min(ARGV[1], tokens + delta * ARGV[2])
if tokens < 1 then return {0, tokens} end
redis.call("HSET", KEYS[1], "tokens", tokens - 1, "ts", ARGV[3])
redis.call("EXPIRE", KEYS[1], 3600)
return {1, tokens - 1}

The key requirement is atomicity. A naive GET-then-SET from multiple instances races, and under exactly the load you are trying to limit. Use a script, a Redis module built for this, or your platform's managed rate limiter.

How should limits be communicated?

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

{ "title": "Rate limit exceeded", "status": 429,
  "detail": "You have exceeded 100 requests per minute. Retry in 37 seconds." }

• Send limit headers on every response, not only on rejection, so clients can self-pace.
• Retry-After in seconds is the field client libraries actually read.
• Document limits publicly. Undocumented limits generate support tickets, not better behaviour.
• Consider a soft warning threshold — notify at 80% rather than only blocking at 100%.

What else belongs alongside rate limiting?

1. 1Request size limits — one 500MB body can hurt more than a thousand small requests.
2. 2Timeouts on every outbound call, so a slow dependency does not hold your workers.
3. 3Circuit breakers, so a failing dependency is skipped rather than retried into the ground.
4. 4Concurrency limits per client for long-running operations like exports.
5. 5Backpressure: return 503 with Retry-After when the queue is saturated rather than accepting work you cannot do.