Design a Rate Limiter
Problem
Design a rate limiter that protects a public API from abuse and overload. Each client is identified by an API key or, for anonymous traffic, by IP address, and each client has limits such as 100 requests per second and 10,000 per day. Limits can differ by endpoint and by pricing tier, and operators must be able to change them without a deploy. The API receives about 500,000 requests per second at peak across a fleet of gateway servers in several regions, and requests over the limit are rejected with HTTP 429 and a hint of when to retry.
- Is the limiter a shared service used by many APIs, or built into one API gateway?
- How strict must enforcement be? Is letting through a few percent over the limit acceptable during bursts?
- Are limits global across regions, or enforced per region?
- Should a burst above the steady rate be allowed, for example 200 requests in one second after an idle minute?
- What should happen if the limiter's backing store is unavailable: allow traffic or block it?
- Do clients need to see their remaining quota in response headers?
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Limit requests per client identity (API key or IP address) over configurable time windows.
- Support different limits per endpoint and per pricing tier.
- Reject over-limit requests with
429 Too Many Requestsand aRetry-Afterheader. - Let operators change rules at runtime without redeploying.
- Return
X-RateLimit-Limit,X-RateLimit-Remaining, andX-RateLimit-Resetheaders on every response. - Allow an operator to temporarily block or exempt a specific client.
Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.
- Handle 500,000 rate limit checks per second at peak.
- Add less than 2 ms at p99 to each request, since every API call pays this cost.
- Track about 50 million active client keys; at under 100 bytes each, the counter state is roughly 5 GB.
- Highly available: a limiter outage must not take the API down.
- Accuracy within a few percent of the configured limit is acceptable; exact global counts are not required.
- Rule changes reach all gateways within 30 seconds.
Rate limiting runs as middleware inside each API gateway instance, so a check needs no extra service hop. The middleware evaluates a token bucket per client and rule, stored in a sharded Redis cluster and updated atomically with a Lua script. Rules live in a configuration store and are pushed to gateways, and if Redis is unreachable the middleware falls back to a local in-memory limiter instead of failing requests.
Loading diagram...
Check a request. A request arrives at a gateway instance. The middleware extracts the client identity from the API key (or the source IP) and finds the matching rules for the route and tier from its in-memory rule cache. It runs one Lua script on the Redis shard that owns the client key, which refills the bucket based on elapsed time, tries to take a token, and returns the remaining tokens. If a token was taken, the request continues to the backend with rate limit headers attached. Otherwise the gateway returns 429 with Retry-After set to the time until the next token.
Change a rule. An operator edits a limit in the admin console. The rule is versioned in the rules store, and the config distributor pushes the new rule set to every gateway, which swaps its in-memory copy atomically.
Degrade gracefully. If a Redis call times out after 5 ms, the middleware switches to a local token bucket sized at the global limit divided by the number of gateway instances and records a metric. It retries Redis in the background and switches back when it recovers.
Library that runs inside every API gateway process and makes the allow or reject decision for each request.
- Envoy or NGINX with a custom filter, or middleware in a Go or Java gateway.
- A local circuit breaker around Redis calls.
API
check(identity, route, tier) -> { allowed, remaining, resetAt }, called in process.- Response headers:
X-RateLimit-Limit,X-RateLimit-Remaining,X-RateLimit-Reset, andRetry-Afteron429.
Scalability
Embedding the limiter in the gateway removes a network hop and a separate fleet to scale. Each gateway keeps a small local cache of clients that are currently blocked, so a client hammering the API after exceeding its limit is rejected without touching Redis at all.
Tradeoffs
A standalone rate limit service would centralize logic and let non-gateway callers use it, but it adds a hop and becomes a critical dependency on every request. In-process enforcement is faster and degrades better. The cost is that changing the algorithm means redeploying gateways, which is rare.
The counting algorithm that decides whether a request fits within the limit.
Diagram
Loading diagram...
Data Model
- Redis hash per client and rule:
rl:{apiKey}:{ruleId}with fieldstokensandts, and a TTL equal to the time needed to refill the bucket completely.
Scalability
Each bucket is two numbers, and the whole check is one atomic script call, so a single Redis shard can serve on the order of 100,000 checks per second.
Tradeoffs
A fixed window counter is simpler but allows double the limit at window boundaries. A sliding window log is exact but stores a timestamp per request, which is far too much memory at 500,000 requests per second. The sliding window counter (weighting the previous window's count) is a reasonable alternative with similar cost. The token bucket is chosen because it supports controlled bursts, which matches how real clients behave, while still enforcing the long-run rate. Daily quotas use a plain counter with a TTL, since bursts do not matter at that granularity.
Shared state for all buckets, so limits hold across every gateway instance.
- Redis Cluster with replicas, using Lua scripts (
EVALSHA) for atomic read-modify-write.
Scalability
Keys are hashed across shards by client identity, so load spreads evenly and 500,000 checks per second needs roughly 8 to 10 primary shards with headroom. Hash tags ({apiKey}) keep all of a client's rule keys on one shard, which allows checking several rules in one script call.
Tradeoffs
Counters are not replicated synchronously, so a failover can lose a few seconds of counts and briefly allow extra requests. That is acceptable for rate limiting, where small overages are harmless, and much cheaper than a strongly consistent store. For multiple regions, each region keeps its own cluster and enforces its share of the global limit, since cross-region round trips would blow the 2 ms budget.
Source of truth for limits, and the mechanism that delivers them to gateways.
- PostgreSQL for versioned rules with an audit trail.
- A watch-based config system such as etcd, or a simple pub/sub channel, to push updates.
API
PUT /rules/:idwith{ match: { route, tier }, limit, windowSeconds, burst }creates or updates a rule.POST /overrideswith{ identity, action: block | exempt, expiresAt }adds a temporary override.
Data Model
rules(id, route_pattern, tier, limit, window_seconds, burst, version, updated_by, updated_at)overrides(identity, action, expires_at, reason)
Scalability
The rule set is small (thousands of rows), so every gateway holds all of it in memory. Gateways also poll every 30 seconds as a backstop if a push is missed.
Tradeoffs
Reading rules from the database on every request would add latency and load for data that changes a few times a day. Pushing a full snapshot is simpler and safer than pushing diffs, because a gateway that missed an update converges on the next snapshot.
Visibility into who is being limited and whether the limiter itself is healthy.
- Counters exported to Prometheus, with sampled rejection events sent to a log pipeline.
Scalability
Gateways aggregate metrics locally and export them every few seconds, so monitoring adds no per-request network calls.
Tradeoffs
Logging every rejection would produce millions of events during an attack. Sampling plus per-client counters keeps the signal (which clients are throttled, and how often the Redis fallback triggers) at a tiny fraction of the cost.