Design URL Shortener & Rate Limiter

Two warm-ups, and the one with teeth

Interviewers love two small prompts as openers: "design a URL shortener" and "design a rate limiter". Both are bounded in scope but unbounded in depth. Either one fits comfortably into the sketch phase, and a good interviewer can then fill the whole deep dive (minutes 20 to 35 of a 45-minute slot, in the course's Interview Framework & Strategy) asking what happens at 10× the traffic, when a node dies, or when two servers race each other. Cheap to start, hard to fake.

They also exercise opposite shapes of data, which is why they are taught together:

The URL shortener has its own lesson: URL Shortener (e.g. TinyURL) covers key generation, code length, 301 vs 302, caching and expiry. This lesson is the rate limiter, in depth. It assumes you know what a load balancer, a cache and a replica are (Core Building Blocks).

The naive plans meet real load

Here is the prompt. A public REST API runs on 30 stateless servers behind a round-robin load balancer and peaks at 40,000 requests per second. Each API key may make 600 requests per minute. Protect the backend from any single customer.

Plan A: count in each server's memory. A dictionary of counters per server. No network hop, nanoseconds per check.

Plan B: count in the main database. Run INSERT INTO limits (api_key, minute, n) VALUES ($1, $2, 1) ON CONFLICT (api_key, minute) DO UPDATE SET n = limits.n + 1 RETURNING n on every request. Shared, atomic, exact.

Predict first: one customer's script goes rogue and sends 3,000 requests per second. Which plan fails, and how would you find out?

The fix takes Plan A's speed and Plan B's shared truth: a shared in-memory store with atomic operations (usually Redis), plus an algorithm chosen by what the requirements say about bursts. The rest of the lesson takes that sentence apart.

Before any algorithm: pin down the contract

"Add a rate limiter" is not a requirement. Five questions turn it into one, and each answer changes the design:

Add the scale (requests per second, number of keys) and how much latency the check may add, and you have enough to estimate.

"100 requests per minute" is ambiguous

Predict first: the limit is 100 per minute. A client sends 100 requests at 12:00:59.9 and 100 more at 12:01:00.1. Are all 200 allowed?

Identity: who is "the client"?

Limit on the most trustworthy identity you have. For authenticated traffic that is the API key, user or account, known after authentication. Before authentication all you have is the network address, and it is weaker than it looks:

• Many users can share one IP. Carrier-grade NAT, offices and campuses put thousands of people behind one address, so a tight per-IP limit blocks innocent users.
• One user can have many IPs. An IPv6 host normally sits in a /64 subnet (2 to the power of 64 addresses), and customers are often given a /56 or /48. Key IPv6 limits on the /64 prefix, and add a coarser limit per larger prefix.
• X-Forwarded-For is client-controlled. Anyone can send the header. Each proxy appends the address it saw, so only the entries your own proxies added are trustworthy, and they sit at the right-hand end. MDN's X-Forwarded-For page describes the safe ways to pick one: count your trusted proxies from the right, or skip known proxy addresses from the right. A limiter keyed on the leftmost entry lets an attacker invent a new identity for every request.

Protection limits and quotas

Two very different jobs both get called "rate limiting":

• Protection (abuse, fairness, overload): "no key may send more than 600 a minute." If the count is off by a few percent for a few seconds, nobody loses money. Latency and availability matter more than exactness.
• Quota (what a customer pays for): "the free tier gets 10,000 calls a month, and we bill above that." A lost increment is lost revenue or a wrong invoice, so the count must be durable and exact. Record usage in a database or an append-only usage log and bill from that. A fast in-memory counter can serve as an early warning, never as the record.

In the interview, say which one you are designing: "This is abuse protection, so I'll trade exactness for latency and availability. If there's also a billing quota, I'll count that separately, in a durable store."

The numbers: what a limiter costs

Estimate before you pick a store. Assumptions for the running example:

• Peak 40,000 requests per second, and every request checks two limits: per API key and per client IP.
• The limits (Move 3 explains the choice): per API key, a token bucket with capacity 100 and a refill of 10 per second (600 a minute on average); per IP, capacity 200 and a refill of 20 per second.
• 200,000 API keys and 500,000 IPs are active within any two-minute stretch. That overestimates the live keys, because an idle bucket expires about 11 seconds after its last request (capacity ÷ refill, plus one), so the memory figure below is an upper bound.
• A counter costs about 100 bytes in Redis. Measured with MEMORY USAGE on Redis 7.4: a string counter with a TTL used 72 bytes and a two-field hash used 104.
• A sliding-log entry costs about 120 bytes in a large log (about 50–60 bytes each while a sorted set is small), measured the same way with 32-character request IDs as members.
• Budget 50,000 limiter script calls per second per Redis primary. That is half of what a token-bucket script like the one in this lesson reached under redis-benchmark on a laptop (about 100,000 calls a second). Measure your own hardware and keep the same headroom.
• One round trip to Redis inside the data center: about 0.5 ms.

Two lessons hide in that table.

Counters cost memory per key; logs cost memory per request. A counter's size doesn't depend on traffic. A sliding log holds every allowed request inside its window, so stretching the window from a minute to an hour makes it 60 times bigger, while the counters stay at 70 MB.

Every check is a write, so replicas don't add capacity. Each call changes a counter and must go to the primary that owns it. Replicas buy failover, not throughput; you scale by adding primaries (shards). Latency, for its part, is why each limit must cost one round trip: a design that needs three sequential commands at 0.5 ms each adds 1.5 ms to every API call.

In the interview: "At peak that's 80k limiter calls a second, so two Redis primaries with replicas. Counters are about 70 MB, so memory isn't the constraint; round trips and the write path are."

Your turn: traffic grows 10× to 400,000 requests per second, with the same number of keys. What changes first?

Move 1: Fixed window counter

Pressure: a simple "N per minute", where an occasional burst at the edge of the minute is tolerable.

Cut time into windows (12:00:00 to 12:00:59, 12:01:00 to 12:01:59, and so on), keep one counter per key per window, and deny once it passes N. Put the window's start time in the key name, so each window gets a fresh counter and old ones simply expire.

import time
import redis

r = redis.Redis(decode_responses=True)  # a local Redis 7+, e.g. docker run -p 6379:6379 redis:7

def allow_fixed_window(key: str, limit: int, window_s: int) -> bool:
    window_start = int(time.time()) // window_s * window_s
    k = f"rl:fw:{key}:{window_start}"          # e.g. rl:fw:key42:1790265600
    pipe = r.pipeline()                        # MULTI/EXEC: the two commands run as one unit
    pipe.incr(k)                               # atomic; returns the new count
    pipe.expire(k, window_s * 2, nx=True)      # set a TTL only if the key has none yet
    count, _ = pipe.execute()
    return count <= limit

print(sum(allow_fixed_window("demo", 100, 60) for _ in range(105)))
# 100 (run it again within the same minute and you get 0: same window, same key)

Three details carry the correctness:

• INCR is atomic. Redis executes one command at a time, so 30 servers incrementing the same key never lose an update. Reading the count with GET and writing it back with SET can lose updates, because other servers' commands run in the gap; Move 3 shows the same race on a token bucket.
• The TTL is set once, in the same transaction. EXPIRE ... NX (Redis 7.0 and later) sets an expiry only if the key has none, and MULTI/EXEC means a crash between the two commands can't leave a counter that never expires. The TTL is twice the window as slack for servers whose clocks disagree slightly.
• Denied requests still increment. That is harmless here, because the key dies with its window.

The boundary burst

Predict first: the limit is 600 per minute. What is the most one key can get through in about one second?

When that burst matters, you need a sliding window (Move 2) or a token bucket with a small burst (Move 3). When it doesn't (a daily quota of 10,000, where 20,000 across midnight is harmless), fixed windows are the cheapest thing that works: one small counter per key and one round trip.

There is a second, quieter cost: synchronized resets. Every client that was denied comes back when the window resets, so blocked traffic returns as a spike at the start of each minute. Adding random jitter to the Retry-After you send spreads it out.

Two TTL traps

⚠️ No TTL at all. Every window leaves a key behind forever. With 200,000 keys active every minute, that is 200,000 × 1,440 minutes × 72 bytes, about 20.7 GB of dead counters a day. With Redis's defaults (maxmemory 0, policy noeviction) nothing stops it until the host runs out of memory; with a maxmemory set, Redis starts refusing writes, and the common volatile-* eviction policies never pick keys that have no TTL.

⚠️ A TTL that never fires. This version looks tidier, and it is badly broken:

# BROKEN: no window in the key, and the TTL is pushed back on every request
def allow_broken(user_id: str, limit: int = 100) -> bool:
    pipe = r.pipeline()
    pipe.incr(f"rate:{user_id}")
    pipe.expire(f"rate:{user_id}", 60)
    count, _ = pipe.execute()
    return count <= limit

The counter resets only after 60 seconds of silence. A client sending a steady 30 requests a minute, well under the 100-per-minute limit, never pauses for 60 seconds, so its count only climbs. It is denied from request 101, at t = 200 s, and stays denied for as long as it keeps calling, because denied requests push the TTL back too. In a one-hour simulation it got 100 of its 1,800 requests through. Keep the window in the key, or set the TTL only when the key is created.

Move 2: Sliding windows

Pressure: "never more than N in any W seconds", or at least no 2× bursts at the boundary.

The exact one: a sliding log

Keep a timestamp for every allowed request, in a Redis sorted set scored by time. To check a request: drop the entries older than W seconds, count the rest, and admit the request if the count is below N. The three steps must happen as one, so they go in a Lua script. Redis runs a script to completion before it runs anything else (Redis scripting docs).

import uuid
import redis

r = redis.Redis(decode_responses=True)

SLIDING_LOG = r.register_script("""
local limit  = tonumber(ARGV[1])
local window = tonumber(ARGV[2])                 -- seconds
local t      = redis.call('TIME')                -- Redis's clock, the same for every server
local now    = tonumber(t[1]) + tonumber(t[2]) / 1e6
redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', now - window)
if redis.call('ZCARD', KEYS[1]) < limit then
  redis.call('ZADD', KEYS[1], now, ARGV[3])      -- the member must be unique per request
  redis.call('EXPIRE', KEYS[1], math.ceil(window))
  return 1
end
return 0
""")

def allow_sliding_log(key: str, limit: int, window_s: int) -> bool:
    request_id = uuid.uuid4().hex
    return SLIDING_LOG(keys=[f"rl:log:{key}"], args=[limit, window_s, request_id]) == 1

print(sum(allow_sliding_log("demo", 10, 60) for _ in range(15)))   # 10

This version avoids two traps that show up in real code:

• Members must be unique. A sorted set stores each member once. If the timestamp is the member, two requests in the same microsecond collapse into one entry and the log undercounts. A random request ID avoids that.
• Log only allowed requests. If you add every request before checking, denied requests fill the log too, and a client that keeps hammering never sees its window drain: it stays blocked indefinitely. That can be a deliberate penalty, but then say so.

The cost is memory per request: 0.58 GB for one-minute windows at our traffic and 34.6 GB for one-hour windows. The log is the right tool when N is small or exactness is contractual, and a poor one for "5,000 per hour" across millions of keys.

The cheap one: a sliding window counter

Keep the two fixed-window counters you already have, this window's and the previous one's, and weight the previous one by how much of it still overlaps the sliding window:

estimate = previous_count × (1 − elapsed / W) + current_count

Cloudflare described this approach in "Counting things, a lot of different things" (2017). Their example: the limit is 50 per minute, there were 42 requests in the previous minute, and 18 so far in a current minute that started 15 seconds ago.

def sliding_estimate(prev_count: int, curr_count: int, elapsed_s: float, window_s: float = 60) -> float:
    overlap = (window_s - elapsed_s) / window_s   # share of the previous window still inside
    return prev_count * overlap + curr_count

print(sliding_estimate(42, 18, 15))   # 49.5: one more request pushes the key past 50

That is two counters per key, one script call (window start in the key name, as in Move 1, and in Redis Cluster the same hash tag on both so they live together, for example rl:{key42}:1790265540 and rl:{key42}:1790265600), and no 2× boundary burst. The price is an assumption: the formula treats the previous window's requests as evenly spread. Real traffic is close enough that Cloudflare reported only 0.003% of requests wrongly allowed or limited in their analysis of 400 million requests from 270,000 sources, with an average 6% gap between the real and the approximated rate. A client that crowds its requests into the end of a window can still beat it, as the next table shows.

Same traffic, five limiters

The limit is 100 per 60 seconds. Three traffic patterns, replayed against pure-Python versions of each algorithm with a simulated clock:

Read it column by column. Only the sliding log never admits more than 100 in any 60-second span. The sliding window counter kills the boundary burst but can be gamed by crowding. A token bucket with a big capacity is generous on purpose, which is the next move.

import math
from collections import deque

class FixedWindow:
    def __init__(self, limit, window):
        self.limit, self.window, self.current, self.count = limit, window, None, 0
    def allow(self, now):
        w = math.floor(now / self.window)
        if w != self.current:
            self.current, self.count = w, 0
        if self.count < self.limit:
            self.count += 1
            return True
        return False

class SlidingLog:
    def __init__(self, limit, window):
        self.limit, self.window, self.log = limit, window, deque()
    def allow(self, now):
        while self.log and self.log[0] <= now - self.window:
            self.log.popleft()
        if len(self.log) < self.limit:
            self.log.append(now)
            return True
        return False

class SlidingCounter:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.current, self.curr_count, self.prev_count = None, 0, 0
    def allow(self, now):
        w = math.floor(now / self.window)
        if w != self.current:
            self.prev_count = self.curr_count if self.current == w - 1 else 0
            self.current, self.curr_count = w, 0
        elapsed = now - w * self.window
        estimate = self.prev_count * (1 - elapsed / self.window) + self.curr_count
        if estimate + 1 <= self.limit:
            self.curr_count += 1
            return True
        return False

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity, self.rate, self.tokens, self.last = capacity, rate, capacity, None
    def allow(self, now):
        if self.last is not None:
            self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

def worst_60s(times):
    """Most admitted requests inside any 60-second span."""
    return max((sum(1 for u in times if t <= u < t + 60) for t in times), default=0)

limiters = {
    "fixed window":          lambda: FixedWindow(100, 60),
    "sliding log":           lambda: SlidingLog(100, 60),
    "sliding counter":       lambda: SlidingCounter(100, 60),
    "token bucket b=100":    lambda: TokenBucket(100, 100 / 60),
    "token bucket b=10":     lambda: TokenBucket(10, 100 / 60),
}
traffic = {
    "burst":    [59.9] * 150 + [60.1] * 150,
    "crowding": [59.9] * 100 + [119.0] * 150,
    "steady":   [i / 2 for i in range(600)],     # 2 per second for 5 minutes
}
for name, make in limiters.items():
    cells = []
    for pattern in traffic.values():
        limiter = make()
        admitted = [t for t in pattern if limiter.allow(t)]
        cells.append(f"{len(admitted)} (worst 60 s: {worst_60s(admitted)})")
    print(f"{name:20}", " | ".join(cells))

Move 3: Token bucket

Pressure: bursts are normal (an app opening fires a dozen calls at once), but the long-run average must hold.

A bucket holds up to b tokens: its capacity, or burst size. Tokens drip in at r per second. Each request takes a token; no token, no entry. A client that has been quiet has a full bucket and can send b requests at once. A client that sends steadily is held to r per second.

Why it works: the b + r·T bound

Over any interval of T seconds, a key can spend at most the tokens it had at the start (never more than b) plus the tokens that arrived during it (r·T). So:

admitted in any T seconds ≤ b + r·T

That one line answers most token-bucket interview questions.

Predict first: capacity 100, refill 10 per second. The product manager calls it "600 per minute". What is the most one key can send in any 60 seconds?

No timers: refill lazily

You don't need a background job adding tokens. Store two numbers per key, tokens and the time they were last updated, and on each request compute how many tokens would have arrived since then. The refill, the check and the decrement must be one atomic step, so this is a Lua script again:

import redis

r = redis.Redis(decode_responses=True)

TOKEN_BUCKET = r.register_script("""
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])               -- tokens per second
local t        = redis.call('TIME')              -- Redis's clock, shared by every server
local now      = tonumber(t[1]) + tonumber(t[2]) / 1e6
local state    = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens   = tonumber(state[1]) or capacity  -- a missing key is a full bucket
local ts       = tonumber(state[2]) or now
tokens = math.min(capacity, tokens + math.max(0, now - ts) * rate)
local allowed, retry_ms = 0, 0
if tokens >= 1 then
  tokens = tokens - 1
  allowed = 1
else
  retry_ms = math.ceil((1 - tokens) / rate * 1000)
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) + 1)
return {allowed, math.floor(tokens), retry_ms}
""")

def allow_token_bucket(key: str, capacity: int, rate: float):
    allowed, remaining, retry_ms = TOKEN_BUCKET(keys=[f"rl:tb:{key}"], args=[capacity, rate])
    return allowed == 1, remaining, retry_ms

results = [allow_token_bucket("demo", capacity=20, rate=5) for _ in range(25)]
print(sum(ok for ok, _, _ in results))   # 20
print(results[-1])                       # (False, 0, 19x): retry in just under 200 ms

The script makes four decisions you can defend:

• Redis's clock, not the app server's. Calling TIME inside the script means 30 servers with slightly different clocks all use one clock. (Scripts may call TIME because Redis replicates a script's effects rather than re-running it: the default since Redis 5.0 and the only mode since 7.0.)
• math.max(0, now - ts) guards against time running backwards, for example after a failover to a replica whose clock is a little behind. Without it, a negative elapsed time would remove tokens.
• The TTL is the time to refill completely (b ÷ r seconds, plus one). After that, a missing key and a full bucket mean the same thing, so Redis may delete idle keys for free.
• It returns what the client needs: the tokens left and, when denied, how long until the next token arrives. Those feed the response headers later in the lesson.

The race the script prevents

Run the same logic as separate commands from the app server (HGET, compute, HSET) and two servers can interleave:

Both requests pass on one token, and the store shows 0, not −1: B's write simply overwrote A's. That is a lost update, and for a busy key it happens constantly. Redis running one command at a time doesn't help, because the gap is between commands. The fixes are a Lua script (above) or an optimistic WATCH/MULTI transaction that retries when the key changed underneath it.

Where token buckets show up

Stripe has described running its request rate limiter as a token bucket in Redis (Scaling your API with rate limiters, 2017). AWS documents that API Gateway throttles with a token bucket: your "rate" is the refill rate and your "burst" is the capacity. It also says throttles are applied "on a best-effort basis and should be thought of as targets" (API Gateway throttling), a useful reminder that production limiters are rarely exact.

Weighted requests come almost free: charge a request more than one token. If a search costs ten times the backend work of a lookup, take ten tokens for it, and the bucket now limits cost instead of calls. (Pass the cost as an argument and compare and subtract it instead of 1.)

Move 4: Leaky bucket, when you must smooth instead of reject

Pressure: the downstream needs a steady rate, and waiting is better than being rejected, up to a bounded wait. The classic case is you calling someone else's limit: an SMS provider that accepts 50 messages a second, a partner API, a fragile legacy database.

A leaky bucket is a queue with a fixed drain rate. Requests join a FIFO queue of capacity Q; a worker takes them off at exactly r per second; when the queue is full, new arrivals are rejected. The output is perfectly smooth, however bursty the input.

The difference in one line: a token bucket polices (admits bursts up to b and rejects the rest at once), while a leaky bucket shapes (delays requests so the output is steady).

The cost is waiting. The last request in a full queue waits Q ÷ r seconds, which gives you the sizing rule:

queue capacity = drain rate × longest acceptable wait

For an SMS provider at 50 per second, where a login code must go out within 30 seconds, Q = 1,500. A bigger queue helps nobody: the requests at the back would time out after you spent effort holding them.

nginx's limit_req module is a well-known implementation; its documentation says the limitation "is done using the 'leaky bucket' method". Excess requests are delayed until the burst queue fills, and then rejected; nodelay serves a burst immediately instead of pacing it. Its default rejection status is 503, so set limit_req_status 429 if you mean "this client is over its limit" (nginx limit_req).

When the producers are many services and the requests must survive a crash, the "queue" becomes a real message queue and the drain a consumer pool with a shared rate. Messaging & Queues covers the delivery guarantees and retries that come with it.

🧠 Textbooks also describe a "leaky bucket as a meter" that rejects instead of queuing. It makes exactly the same decisions as a token bucket, mirrored: the bucket fills with requests instead of emptying of tokens. Implementations of it often store one timestamp per key, a scheme known as GCRA. If an interviewer says "leaky bucket", ask whether they mean the queue or the meter.

Your turn: a payments partner allows you 20 requests per second. Your checkout service produces a burst of 600 requests when a flash sale opens, and each checkout call times out after 10 seconds. Design the outbound limiter and say what happens to the burst.

Many servers, one limit

You've already seen Plan A fail: 30 servers counting locally let one key through 30 times over.

Predict first: you switch the load balancer from round robin to hashing on the API key, so each key always lands on the same server. Does per-server counting work now?

The main options, with what each costs:

Leases need numbers, because they only pay off at scale. With 30 servers and leases of 20 tokens, up to 30 × 19 = 570 tokens can sit unused on servers the client isn't hitting. For a key allowed 600 a minute that is 95% of its limit: useless. For an enterprise key allowed 60,000 a minute it is under 1%, and it cuts that key's Redis calls twentyfold.

The two-tier design is what Envoy's documentation describes: a local token bucket "can absorb very large bursts in load that might otherwise overwhelm a global rate limit service", and the global service finishes the job (Envoy global rate limiting). It is also your defense against a hot key. A flood of 500,000 requests a second from one IP, or on one leaked API key used from thousands of IPs, would land on the single Redis shard that owns that counter. A per-server local bucket for the same key turns most of it away before it reaches Redis, which is why the local tier needs buckets per API key as well as per IP: a per-IP bucket alone does nothing against a key spread across thousands of addresses.

The running example, assembled

Put together, one request in the running example takes this path:

client ──► load balancer ──► API server (1 of 30)
                               │
                               ├─ 1. local token buckets per IP and per key, in memory (turn floods away, no network)
                               │
                               ├─ 2. two Lua calls, sent in parallel, 5 ms timeout:
                               │        per-key bucket ──► Redis primary A ──► replica
                               │        per-IP  bucket ──► Redis primary B ──► replica
                               │
                               ├─ 3a. both allowed ──► handler ──► database
                               └─ 3b. either denied ──► 429 + Retry-After (no work done)

At peak, 40,000 requests a second enter and 80,000 script calls a second reach the two primaries (A and B are whichever primaries own the two keys' slots; sometimes they are the same one), for one round trip of about 0.5 ms per request. The local buckets are set generously, well above each server's fair share of the global limits, so only floods ever trip them. If a Redis call times out, the server applies the endpoint's failure policy (the next section) instead of waiting.

Sharding the counters

Counters shard by key. Redis Cluster assigns every key to one of 16,384 hash slots (CRC16 of the key, modulo 16,384), and each primary owns a set of slots. That is fixed-slot sharding, and the Redis documentation points out that it is not consistent hashing (Scale with Redis Cluster). Two practical consequences:

• A script may only touch keys in one slot. That is why the sliding window counter's two keys share a hash tag: only the part inside the braces is hashed.
• A per-key limit and a per-IP limit live in different slots, so they are two calls. Send them in parallel so the request pays one round trip, not two.

How consistent is it, really?

Redis replicates asynchronously. If a primary acknowledges three increments and crashes before its replica receives them, the promoted replica is three requests behind, and the client gets three extra requests in that window. The Redis Cluster documentation says plainly that it "does not guarantee strong consistency", for this reason. Executing one command at a time makes each operation atomic; it doesn't make a replicated deployment strongly consistent.

For protection limits this is the right trade. A few extra requests after a rare failover cost nothing. A consensus-backed (CP) store would put a quorum round trip on every API request and refuse to answer wherever it can't reach a quorum, at which point you would have to fail open or closed anyway. Most production limiters go further on purpose: Stripe's limiters fail open (next section), and AWS calls its throttles targets. Keep exactness for the quotas you bill, in a durable store. Key Concepts & Terminology covers CAP and consistency models precisely.

In the interview: "Counters live in Redis Cluster, one Lua call per limit, with the per-key and per-IP checks sent in parallel. Replication is asynchronous, so a failover can let a few extra requests through, and for abuse protection I accept that. The billing quota is counted separately, in the database." The likely follow-up is "what if Redis goes down?", which is the next section.

Your turn: go multi-region. The API now runs in three regions, 80 to 180 ms apart. Limits are global per key, and the check may add at most 5 ms. Keys usually stay in one region but may move. What do you do?

When the limiter itself fails

The limiter sits in front of every request, so its failure modes become your API's failure modes. Decide each one in advance.

Fail open or fail closed?

It is a per-endpoint business decision, and a strong answer makes it out loud:

• Fail open when the limiter protects capacity and a few minutes without it is survivable. Stripe wrote that it catches exceptions at all levels so that "any coding or operational errors would fail open and the API would still stay functional". Envoy's rate limit filter behaves the same way by default: its failure_mode_deny setting defaults to false, so traffic flows when the rate limit service doesn't answer.
• Fail closed, or fall back to a strict local limit, when every extra request costs money or security: sending SMS, password attempts, expensive AI calls. Blocking for three minutes is cheaper than giving an attacker three free minutes.

Whichever you choose, bound the wait. A limiter call that times out after 5 ms and then applies the policy keeps the API fast. One that waits for a one-second connection timeout on every request turns a Redis hiccup into a site-wide slowdown.

⚠️ Roll out in shadow mode. Stripe's advice is to "dark launch" each limiter: log what it would block, check that blocking it is the right decision, and only then enforce. A mis-sized limit is an outage you caused yourself.

Where to enforce

Limits can live at several layers, and real systems use more than one:

Two ordering rules:

• Limit before expensive work, after identification. A per-IP limit goes before authentication, because the login endpoint is itself a target. The per-key limit goes right after authentication and before any database work or side effect. A rejected request then did nothing, so the client can safely retry it.
• Rate is not concurrency. A burst of 100 two-second report queries occupies 100 workers at once, even if it fits within a rate limit. Stripe describes a separate concurrent requests limiter (at most 20 requests in flight per user, in their example) alongside its rate limiter, plus load shedders that protect the whole fleet. Rate limits keep clients fair to each other; load shedding (usually a 503) protects the service when everyone is busy.

Telling the client: 429 and friends

A limiter that rejects silently teaches clients to retry harder. Tell them what happened and when to come back:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 12
RateLimit-Policy: "per-key";q=600;w=60
RateLimit: "per-key";r=0;t=12

{"error": "rate_limited", "retry_after_seconds": 12}

• 429 Too Many Requests is defined in RFC 6585: the user "has sent too many requests in a given amount of time". The RFC deliberately doesn't say how you identify the user or count requests. Keep 503 for "the service is overloaded" (load shedding), not for one client's limit.
• Retry-After (defined in RFC 9110) takes either a number of seconds or an HTTP date. Compute it from your algorithm: the time until the window resets, or until the next token (the token-bucket script returns it).
• RateLimit and RateLimit-Policy come from an IETF draft (draft-ietf-httpapi-ratelimit-headers, version 11 in May 2026) that is not yet an RFC. In the policy, q is the quota and w the window in seconds; in the current state, r is the quota remaining and t the seconds in which it applies. The HTTP basics behind all this are in Networking Basics.
• Many APIs still send the older X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset headers, and they disagree on details. GitHub's x-ratelimit-reset is a UTC epoch timestamp, while Envoy's optional headers (based on an earlier draft) give the reset as seconds from now. GitHub also answers an exceeded limit with either 403 or 429 (GitHub REST rate limits). Whatever you send, document it.

The client's half of the deal: honor Retry-After, and when there isn't one, back off exponentially with random jitter so a thousand throttled clients don't all retry in the same millisecond.

In the interview: "Over the limit I return a 429 with Retry-After computed from the bucket, and remaining-quota headers on every response, so well-behaved clients slow down before they are rejected." A likely follow-up is "what stops clients from ignoring Retry-After?" Nothing does, which is why rejection must be cheap: the check runs before any real work, and persistent offenders can be blocked at the edge.

Final round: no label on the problem

Real prompts don't name the algorithm. For each one: pin down the contract, estimate where it matters, pick the move, and name what you give up.

Challenge 1: webhook delivery

Your platform sends webhooks to customers' servers. A customer's endpoint handles at most 20 requests per second, and a nightly batch produces 10,000 events for one customer within a minute. Events must not be lost.

Challenge 2: a free tier with overage billing

A freemium API: 10,000 calls a month free, billed per call above that, and never more than 10 requests a second per key.

Challenge 3: login attempts

Stop password guessing on a login endpoint. Attackers run credential stuffing from thousands of IPs, and sometimes hammer one account from one IP. Legitimate users must not be locked out by an attacker.

Cheat sheet: pressure → move → cost

Before moving on, design the running example aloud as the deep dive of a 45-minute interview: the 15 minutes from minute 20 to minute 35 on the Interview Framework & Strategy clock. Cover the contract questions you would ask; the numbers (80,000 calls a second, 2 primaries, 70 MB); the algorithm and why; the four decisions inside the Lua script; what happens when Redis fails over and when it disappears; and the response a throttled client sees. Then have someone interrupt with "what if one customer sends 100 times more than everyone else?" If you can answer that without notes, you have the rate limiter.

Next: URL Shortener (e.g. TinyURL), the other warm-up; Messaging & Queues for the queues behind leaky buckets and webhooks; and Mock Interviews & Communication to practise saying all of this against a clock.