Design a distributed API rate limiter

Category: system design Difficulty: 4 Asked: 2026-10-31 · system-design-01 · System design · Edit

○ Mark completed

Tip: answer aloud for ~5 minutes before reading the solution.

Question

Design rate limiting for a public API serving ~1M req/s across multiple regions: per-API-key limits, burst tolerance, and protection of the platform itself under overload. Where does it live, what algorithm, what store, and what happens when the limiter fails?

Step-by-step solution

1. Clarify: limit keys (API key, user, IP, endpoint), hard vs soft limits, accuracy needed, global vs per-region, response contract (429 + Retry-After, rate headers).
2. Distinguish request rate limiters (per customer) from load shedders (protect the fleet, drop low-priority traffic first) — Stripe runs both layers.
3. Choose algorithm: token bucket (allows bursts, Stripe's choice), or sliding-window counter (approximates a sliding log cheaply by weighting the previous window — Cloudflare's approach). Avoid fixed windows (2x burst at the boundary) and full sliding logs (memory).
4. Placement: at the edge/API gateway so rejected traffic is cheap; keep the decision path in-memory or one hop away.
5. State: centralized Redis with atomic Lua (INCR+EXPIRE / token math) sharded by key; or local counters per node with periodic async sync for scale, accepting slight over-admission.
6. Multi-region: per-region budgets (global limit / N or weighted) instead of synchronous cross-region coordination.
7. Failure mode: fail open on limiter-store errors (with tight timeouts) for customer limits; load shedder stays local.
8. Operate: dark-launch (log-only), dashboards on rejections per key, allowlists for internal traffic, client guidance (exponential backoff + jitter).

Final answer

Two layers at the edge: per-key token bucket (or sliding-window counter) backed by sharded Redis with atomic scripts, plus a local priority-based load shedder. Return 429 with Retry-After, fail open on limiter outages, partition global limits per region, and roll out in log-only mode first.

Trade-offs & common mistakes

• Accuracy vs latency: exact global counts need coordination; approximate is almost always fine.
• Fixed windows allow double bursts; sliding logs blow up memory.
• Failing closed turns a Redis blip into a full outage.
• Forgetting load shedding: per-customer limits don't save you when total traffic spikes.
• Non-atomic read-then-write races in Redis.

Key terms

token bucket, sliding window counter, load shedding, fail open, backoff with jitter

References

• Stripe — Scaling your API with rate limiters: https://stripe.com/blog/rate-limiters
• Cloudflare — How we built rate limiting capable of scaling to millions of domains: https://blog.cloudflare.com/counting-things-a-lot-of-different-things/
• Google SRE book — Handling Overload: https://sre.google/sre-book/handling-overload/

Deeper learning

• System Design Primer: https://github.com/donnemartin/system-design-primer
• AWS Builders' Library — Timeouts, retries, and backoff with jitter: https://aws.amazon.com/builders-library/timeouts-retries-and-backoff-with-jitter/

Video