Design a distributed rate limiter
A service that limits how many requests each client can make, enforced consistently across many API servers.
Why interviewers ask it
It tests algorithms (token bucket and windows), shared state across servers, atomic updates and failure handling, all in one small system.
Functional requirements
- Limit requests per user, API key or IP address per time window (for example 100 per minute).
- Different rules for different endpoints.
- Reject with 429 and tell the client when to retry.
Non-functional requirements
- Adds very little latency (1–2 ms at most).
- Highly available, and accurate enough across servers.
- Handles millions of clients.
From version 1 to the final design
- Version 1: an in-memory counter per user on one server.
- Version 2: many servers, so the counters move to Redis.
- Version 3: atomic updates with a Lua script, a token bucket for bursts, and rules from configuration.
- Version 4: several regions, a fail-open fallback, and monitoring of rejected requests.
The design, step by step
- The limiter runs as middleware in the API gateway.
- Rules are loaded from a config store and cached locally.
- Counters live in a Redis cluster and are checked and updated atomically with a Lua script (or INCR plus EXPIRE for fixed windows).
- Over the limit → 429 with Retry-After.
Deep dives
- Race conditions: two servers reading and writing the same counter at once → use atomic Redis operations or a Lua script.
- Multiple regions: a limit per region (slightly inaccurate) or a global store (slower).
- Redis failure: fail open, with a local in-memory limit as a backup.
- Hot clients: spread counters across Redis nodes by client ID.
Common mistakes
- Reading a counter and writing it back as two separate steps: two servers read the same value, and both let a request through.
- Limiting per server instead of across all servers.
- Having no answer to "what if Redis is down?". Decide in advance whether the limiter then lets requests through or blocks them.
Not true: Shared counter: read it, add one and write it back as separate steps; that works across servers.
In fact: Two servers can read the same value and both let a request through, so the limit is passed. Use one atomic operation, such as Redis INCR or a Lua script.
In the interview
I'd enforce limits in the API gateway using a token bucket per client and rule, with state in a Redis cluster updated atomically by a Lua script, adding about a millisecond. Rules come from configuration. Requests over the limit get 429 with Retry-After. If Redis is unavailable, the gateway fails open with a local backup limit.
Part of Unit 8: High-level design questions in the free System Design course.