Courses › System Design › Question Breakdowns

Design a Rate Limiter

Token bucket vs. sliding windows with memory math, distributed counters, IP vs. user limits.

A rate limiter controls how many requests a client can make in a time window, protecting services from abuse, runaway clients and overload. The interview usually asks for a distributed rate limiter used by an API gateway, which makes it a question about algorithms, shared state and failure handling.

Why rate limit?

  • Abuse: credential stuffing, scraping and fake sign-ups arrive as ordinary-looking HTTP requests, so a per-client budget is often the cheapest defense.
  • Fair sharing: in a multi-tenant API, one customer's nightly bulk export must not starve another customer's checkout calls.
  • Protecting dependencies: if your SMS provider allows 50 sends/second, your own API has to stay under that no matter what callers do.
  • Pricing: Free, Pro and Enterprise plans differ mostly in their quotas, so the limiter enforces the price list.
  • Graceful overload: during an incident, tighter limits keep the service partly up instead of fully down.

Requirements

Functional

  • Limit requests per client (user ID, API key or IP) according to configurable rules (e.g. 100 requests/minute)
  • Reject over-limit requests with HTTP 429 and helpful headers

Non-functional

  • Low latency — adds < 10ms to each request
  • Highly available — a rate-limiter failure must not take down the API
  • Works across a fleet of gateway servers with a consistent view of each client's usage
  • Scale: ~1M requests/second across all clients

Where it lives

user = client "Client" @0,0
gw = service "API Gateway" @1,0
rl = service "Rate Limiter" @1,1
redis = cache "Redis Cluster\n(counters)" @2,1
rules = store "Rules Config" @0,1
api = service "Backend Services" @2,0
user -> gw
gw <-> rl : allowed?
rl <-> redis
rules --> rl : cached rules
gw -> api : if allowed

Allowed requests go on to the backend; the rest get a 429 straight from the gateway.

Putting the limiter in the gateway rejects bad traffic before it costs the backend anything. Rules are loaded from configuration and cached in each gateway.

Algorithms

Strict or forgiving? A strict limit is a wall: request 1,001 of a 1,000/hour quota fails. Some APIs add a grace margin so a client that briefly overshoots by a few requests isn't cut off mid-job, and internal platforms sometimes let callers borrow unused capacity while the cluster is idle. Say which one you're building; public APIs almost always want the wall.

Fixed window, step by step

Use one Redis key per client and window, such as rl:{apiKey}:{minute}, and INCR it; the first INCR also sets a 60-second expiry. For API key k_77 with a limit of 4 per minute:

No reset logic is needed: the old minute's key simply expires. Each live key costs roughly 60–80 bytes in Redis (key string, integer value, expiry), so 5M active API keys ≈ 400 MB.

The catch is the window edges:

w1 = zone "minute 1" @0,0 2x1.3
w2 = zone "minute 2" @2,0 2x1.3
a = service "3 requests\nat 0:59" @1.05,0.2
b = service "3 requests\nat 1:00" @1.95,0.2
n = note "6 requests in 2 seconds,\nboth windows say OK" @1.5,1.3
a -> b

A sliding (rolling) window measures "the last 60 seconds from now" instead of clock-aligned minutes, which closes that gap.

Sliding window log

Store a timestamp for every request (a Redis sorted set per user). On each request: drop timestamps older than now - window, count the rest, reject if the count is at the limit, otherwise add now.

Exact, but expensive: with a 2,000 requests/day quota, a busy client holds up to 2,000 entries. A sorted-set entry costs roughly 60 bytes once you count the member, the score and the skip-list bookkeeping, so that's ~120 KB per client, ~60 GB for 500k busy clients. Memory grows with traffic, which is exactly what a limiter is supposed to contain.

Sliding window with counters

The middle ground keeps just two fixed-window counters, the current one and the previous one, and weights the previous window by how much of it still overlaps the last 60 seconds:

estimate = previous × (1 − elapsed_in_current / window) + current

At 14:23:15 (a quarter into the minute), with 8 requests last minute and 3 so far, the estimate is 8 × 0.75 + 3 = 9. Two integers per client is a couple of hundred bytes at most, roughly a thousand times less than the log, and the error stays small as long as traffic within a window is roughly even. Finer buckets (say six 10-second counters) trade a little memory for more accuracy.

Token bucket is a strong default: two numbers per client (tokens, last refill time), bursts are allowed up to capacity, and the refill happens lazily on each request — no background timer:

def allow(bucket, now, rate, capacity):
    elapsed = now - bucket.last_refill
    bucket.tokens = min(capacity, bucket.tokens + elapsed * rate)
    bucket.last_refill = now
    if bucket.tokens >= 1:
        bucket.tokens -= 1
        return True
    return False

Deep Dives

1. Shared state across gateways

Each gateway sees only part of a client's traffic, so counters must live in a shared store: Redis is the standard choice (sub-millisecond, in-memory, atomic operations).

The read-modify-write must be atomic or two gateways will both read "1 token left" and both allow the request. Run the token-bucket logic as a Lua script in Redis, which executes atomically.

g1 = service "Gateway 1" @0,0
redis = cache "Redis\ncount = 2 (limit 3)" @1,0.5
g2 = service "Gateway 2" @0,1
n = note "both write 3,\nboth allow:\n4 requests got through" @2,0.5
g1 <-> redis : read 2, write 3
g2 <-> redis : read 2, write 3

Locking each user's key for the read-update would also work, but it serializes that user's requests and adds latency. An atomic script (or INCR for simple counters) gives the same safety without the lock.

2. Scaling Redis

At ~1M requests/second, shard across a Redis Cluster by client key. Each client's state lives on one shard, so every check is a single round trip. Keep connections pooled and co-locate Redis with the gateways to minimize latency.

3. Failure handling

If Redis is slow or down:

  • Fail open — allow requests through. Protects availability; you lose protection temporarily. Usually right for general API limits.
  • Fail closed — reject requests. Right when the limiter protects something fragile or expensive (e.g. SMS sending, login attempts).
  • A local in-memory fallback limit per gateway (global limit ÷ number of gateways) gives approximate protection during outages.

4. Client experience

Return 429 Too Many Requests with Retry-After, plus X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset headers on every response so well-behaved clients can self-throttle.

5. Rules and tiers

Rules (per endpoint, per plan tier, per client) live in a config store and are pushed or polled by gateways. Different limits per pricing tier are just different rule parameters.

Rules usually stack: an account might get 10,000 requests/hour overall, 20/minute on the expensive POST /reports endpoint, and 5/minute on login. Each rule is its own counter, and a request must pass every rule that matches it.

6. Limit by IP, by user, or both?

  • Per IP: the only identity you have before authentication. Carrier-grade NAT puts thousands of phones behind one address, so set IP limits generously, and key IPv6 clients by their /64 prefix, since one machine can rotate through billions of addresses inside it.
  • Per API key or user: precise and fair once the caller is authenticated, and it's what pricing tiers attach to.
  • Login is the special case: a per-account limit alone lets an attacker lock a victim out on purpose. Key the limit on account and IP together, and slow repeated failures down (growing delays, then a CAPTCHA) rather than blocking the account outright.

7. Keeping the limiter fast

A Redis round trip on every request is usually fine (well under a millisecond in the same zone), but at very high volume you can pre-allocate: each gateway takes a slice of a client's budget, say 50 tokens, spends it locally, and goes back to Redis only for the next slice. Redis calls drop by roughly the slice size, at the cost of a client briefly exceeding the limit by up to one slice per gateway. Once a client is blocked, a short local "denied until 14:24:00" entry keeps rejected retries from hitting Redis at all.

What's expected at each level

  • Mid-level: a working algorithm, Redis for shared counters, 429 responses.
  • Senior: compares algorithms, ensures atomicity with Lua, discusses fail-open vs fail-closed.
  • Staff: multi-region limits (local enforcement with periodic global sync), hot-key clients, memory math for each algorithm, identity choices (IP, key, account) and operational concerns like rule rollout.