Design a distributed rate limiter

Step 1 Understand it

Why interviewers ask this. It tests algorithms (token bucket and windows), shared state across servers, atomic updates and failure handling, all in one small system.

Watch it happen

Requirements

Estimates

• 10 million active clients × one counter each × about 100 bytes ≈ 1 GB in Redis: it easily fits in memory.

API

• Internal: allow(client_id, rule) → {allowed, remaining, retry_after}
• Response headers: X-RateLimit-Remaining, Retry-After

Data model

• One Redis key per client per rule: tokens and last refill time (token bucket), or a counter with a TTL (fixed window).

Start simple, then scale

1. Version 1: an in-memory counter per user on one server.
2. Version 2: many servers, so the counters move to Redis.
3. Version 3: atomic updates with a Lua script, a token bucket for bursts, and rules from configuration.
4. Version 4: several regions, a fail-open fallback, and monitoring of rejected requests.

Picture it

flowchart LR
  C["Clients"] --> G1["Gateway node 1<br/>(limiter)"]
  C --> G2["Gateway node 2<br/>(limiter)"]
  G1 <-->|"atomic update"| R[("Redis cluster<br/>token buckets")]
  G2 <-->|"atomic update"| R
  G1 --> S["Services"]
  G2 --> S
  CFG["Rules config"] -.-> G1
  CFG -.-> G2

The design, step by step

1. The limiter runs as middleware in the API gateway.
2. Rules are loaded from a config store and cached locally.
3. Counters live in a Redis cluster and are checked and updated atomically with a Lua script (or INCR plus EXPIRE for fixed windows).
4. 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

• Read-then-write counters with no atomicity.
• Limiting per server instead of across all servers.
• No answer to 'what if Redis is down?'.

Step 2 Go further (free, optional)

Optional. The notes above are written to be enough on their own. These free resources give a second explanation and extra practice.

• Watch

  ByteByteGo: rate limiter system design

  ByteByteGo · YouTube

• Read

  Hello Interview: design a rate limiter

  hellointerview.com · free guides

• Read

  Scaling your API with rate limiters

  Stripe blog

Step 3 Practise

Try each exercise yourself first: on paper, out loud or in code. Then open the answer and compare it with yours.

1. ExplainSay it in plain words in under a minute, with no notes.

   Explain where the limiter sits and what happens on each request.

   Show answer

   The limiter sits in the API gateway, as middleware that runs before the request is passed to any service, so blocked requests never cost the services anything.

   On each request:
   1. Identify who is asking: the API key, the user ID from the token, or the IP address if there is no login.
   2. Find the rule for this endpoint and client tier (for example, "search: 100 per minute"). Rules come from a config store and are cached in the gateway's memory.
   3. Check and update the client's counter in Redis in one atomic step (a Lua script, or INCR for a fixed window), so two gateways can't both think there is room.
   4. Allowed: forward the request, adding headers such as X-RateLimit-Remaining.
   5. Not allowed: reply 429 Too Many Requests with Retry-After, and don't call the service.

   The whole check should add a millisecond or two. If Redis is down, fall back to a local in-memory limit per gateway (fail open, but not unlimited).

2. DrawSketch the diagram (or class diagram) from memory.

   Draw clients → gateway (with the limiter) → services, with Redis beside the gateway.

   Show answer

   The limit is checked once, at the edge, and shared through Redis, so it holds whichever gateway a request lands on. Rules are read from the config store occasionally, never on every request.

   textCopy

   Clients
     │
     ▼
   Load balancer
     ├──────────────┬──────────────┐
     ▼              ▼              ▼
   Gateway 1      Gateway 2      Gateway 3
   [limiter]      [limiter]      [limiter]
     │  ▲             │              │
     │  │ atomic check and update    │
     └──┴──────► Redis cluster ◄─────┘
        │        (one counter per client per rule)
        │
        ├── over the limit → 429 + Retry-After
        └── allowed ──► Services
   
   Config store ── rules, cached in each gateway

3. ApplyUse it in a real design question and say exactly where it fits.

   Implement a sliding-window-log limiter in Python, then sketch the Redis commands you would use for it.

   Show answer

   The sliding-window log keeps, per client, the times of the requests it allowed in the last window. Each new request first forgets times older than the window, then is allowed only if fewer than the limit remain. Unlike a fixed window, there is no edge where a client can fire twice the limit.

   With a limit of 3 per 60 seconds: requests at 0, 10 and 20 s pass; 30 and 59 s are refused; at 60.5 s the request from 0 s has dropped out, so one more passes; at 61 s the window is full again; at 75 s the 10 s request has dropped out.

   In Redis, keep one sorted set per client, with timestamps as scores, and run these steps atomically in a Lua script:
   • ZREMRANGEBYSCORE rl:{client} 0 (now − 60000): drop entries older than the window.
   • ZCARD rl:{client}: count what is left.
   • If the count is below the limit: ZADD rl:{client} now {unique request id}, then PEXPIRE rl:{client} 60000, and allow; otherwise refuse.

   The cost: memory for every allowed request, per client. At high limits, a sliding-window counter (two fixed-window counts, weighted) is the cheaper approximation.

   pythonCopy

   from collections import deque
   
   
   class SlidingWindowLog:
       def __init__(self, limit, window_s, clock):
           self.limit, self.window, self.clock = limit, window_s, clock
           self.logs = {}                              # client -> times of allowed requests
   
       def allow(self, client):
           now = self.clock()
           log = self.logs.setdefault(client, deque())
           while log and log[0] <= now - self.window:  # forget requests outside the window
               log.popleft()
           if len(log) < self.limit:
               log.append(now)
               return True
           return False
   
   
   now = [0.0]                                         # a fake clock, in seconds
   limiter = SlidingWindowLog(limit=3, window_s=60, clock=lambda: now[0])
   results = []
   for t in [0, 10, 20, 30, 59, 60.5, 61, 75]:
       now[0] = t
       results.append((t, limiter.allow("key-1")))
   print(results)
   # [(0, True), (10, True), (20, True), (30, False), (59, False), (60.5, True), (61, False), (75, True)]

4. Trade-offsSay what it costs, when not to use it, and the alternative.

   Token bucket or sliding window for an API that should allow short bursts?

   Show answer

   Token bucket.

   It is built for exactly this: the bucket's size is the burst you allow, and the refill rate is the steady limit. A client that has been quiet can fire, say, 20 requests at once; a client that keeps hammering is held to 10 a second. Per client it stores just two numbers (tokens and last refill time), so it is cheap in memory and in Redis.

   Sliding window (log or counter) is about fairness over a moving window: never more than N in any 60 seconds. It allows a burst of up to N at once too, but then the client must wait for the whole window to slide before it gets capacity back, which feels stricter than a refill. The log version is exact but stores a timestamp per request; the counter version is cheap but approximate.

   So: token bucket when bursts are welcome and you care about the long-run rate (most public APIs); sliding window when the hard rule is "never more than N per window" (for example, a contract with a partner, or login attempts).

Step 4 Interview-ready, then prove it

Your interview answer

About 20 to 40 seconds, said out loud. Practise it until it sounds like you, not like notes.

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.

Follow-up questions

Tick each check when you can do it without notes