Design a distributed rate limiter

"Design a rate limiter for an API gateway: 50,000 requests per second across 100 nodes, per-customer limits, and it must not become the bottleneck."

Step 1: clarify (3 minutes)

What is being limited, and what happens on the boundary? Three questions that determine the algorithm:

Limit granularity   Per API key? Per user? Per endpoint? Per (key,
                    endpoint) pair? The last multiplies your key count.
Burst policy        "100 requests per minute" can mean 100 evenly
                    spread, or 100 all at once then nothing for 59
                    seconds. These need different algorithms.
Over-limit action   Reject with 429, queue, or throttle? Rejecting is
                    usually right; queueing turns a rate limit into a
                    latency problem.

Assume: per (API key, endpoint class), burst allowed up to the limit, reject with 429 and a Retry-After header.

Is exactness required? The question behind the question:

STRICT     Never allow the 101st request in a window. Requires
           coordination on every request, which costs a round trip.
APPROXIMATE Allow occasional small overshoot (say 5%) in exchange
           for local decisions at microsecond latency.

Assume approximate, and be specific about the bound, because "approximate" without a number is not an engineering answer. Assume: overshoot bounded to roughly 10 percent under normal operation, and the design must state what makes that bound hold.

Where does it run? At the gateway, before authentication is fully resolved (so it can protect the auth service itself) but after enough parsing to identify the caller.

Scale       50,000 RPS across 100 gateway nodes = 500 RPS/node
Keys        ~50,000 API keys x ~6 endpoint classes = 300,000 limit keys
Skew        Heavily skewed: the top 20 keys are ~60% of traffic
Latency     Under 1 ms added at p99. This is a hard requirement:
            a rate limiter that adds 10 ms to every request has
            made the API worse than the abuse it prevents.

Step 2: capacity math (3 minutes)

Naive centralised approach
  Every request does a Redis INCR: 50,000 ops/sec.
  Redis handles ~100k ops/sec/node, so it fits on one node.
  But: every request now pays a network round trip.
  Same-AZ Redis RTT: ~0.5 ms. Cross-AZ: ~1.5 ms.
  -> 0.5 ms added to EVERY request, and a hard dependency on
     one Redis for the entire API. Both are unacceptable
     against the stated requirement.

State size
  300,000 limit keys x ~100 bytes = 30 MB. Trivial.
  This is not a storage problem.

Skew consequence
  The top 20 keys are 60% of traffic = 30,000 RPS across 20 keys
  = 1,500 RPS per hot key. A single Redis key at 1,500 ops/sec is
  fine; a single key needing STRICT coordination across 100 nodes
  at 1,500/sec is 1,500 round trips/sec on that one key, plus
  contention.
  -> The hot keys are exactly where centralised coordination hurts
     most, and they are also where accuracy matters most.

Local-only approach
  Each node enforces limit/100. Zero latency, zero dependency.
  Breaks completely under uneven load balancing: if a customer's
  requests hash to 3 of 100 nodes, they get 3% of their limit.
  -> Unusable alone, and the right BASE for a two-tier design.

The two numbers that force the design: 0.5 ms of round trip on every request, and a customer receiving 3 percent of their limit under uneven routing. Neither pure approach works, which is why the answer is two-tier.

Step 3: the algorithm

Four options. Two are wrong for this workload and it is worth saying why.

FIXED WINDOW
  Count per calendar minute, reset at the boundary.
  Cheap: one counter, one INCR.
  BROKEN: 100 requests at 11:59:59 and 100 at 12:00:01 is 200
  requests in two seconds against a "100 per minute" limit.
  The boundary burst is 2x the intended rate, always.

SLIDING WINDOW LOG
  Store a timestamp per request, count those in the window.
  EXACT, and O(n) memory per key. At 1,500 RPS on a hot key with
  a 60 s window that is 90,000 timestamps for one key.
  Correct and too expensive.

SLIDING WINDOW COUNTER
  Weighted blend of the current and previous fixed windows:
    count = curr + prev * (1 - elapsed_fraction)
  O(1) memory, and it smooths the boundary burst.
  Approximation error is small and bounded, and this is what
  Cloudflare published as their production choice.

TOKEN BUCKET
  Tokens refill at a constant rate up to a capacity.
  O(1) memory, expresses BURST (capacity) and SUSTAINED RATE
  (refill) as separate parameters, which is what an API product
  actually wants to offer.

Take token bucket, because burst and sustained rate are separately meaningful to a customer ("1,000 per minute, bursting to 100") and no other algorithm expresses both.

@dataclass
class TokenBucket:
    capacity: float          # max burst
    refill_per_sec: float    # sustained rate
    tokens: float
    last_refill: float

    def try_consume(self, n: float, now: float) -> bool:
        # Lazy refill: compute tokens on read rather than running a
        # timer per bucket. 300,000 timers would be absurd; this is
        # exact and costs one multiplication.
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity,
                          self.tokens + elapsed * self.refill_per_sec)
        self.last_refill = now
        if self.tokens >= n:
            self.tokens -= n
            return True
        return False

Lazy refill is the implementation detail that makes it practical: no background timers, no sweep over 300,000 buckets, and the arithmetic is exact rather than sampled.

Step 4: the two-tier design

This is the answer. Local buckets for the decision, a central authority for distributing capacity.

   ┌──────────────────────────────────────────────────────┐
   │  100 GATEWAY NODES                                    │
   │                                                        │
   │  Local token bucket per key.                          │
   │  Decision: in-memory, ~200 ns, no network.            │
   │                                                        │
   │  Each node holds a LEASE: a share of the global        │
   │  budget, granted for a short interval.                │
   └───────────────────────┬──────────────────────────────┘
                           │ async, batched, every 100-500 ms
                           │ "I used 43 of my 50; give me more"
                           ▼
   ┌──────────────────────────────────────────────────────┐
   │  CENTRAL AUTHORITY (Redis, sharded by key)            │
   │  Global budget per key per window.                    │
   │  Grants leases proportional to observed demand.       │
   └──────────────────────────────────────────────────────┘

class LeasedLimiter:
    def allow(self, key: str, now: float) -> bool:
        bucket = self.local.get(key)
        if bucket is None:
            # Cold key on this node: allow optimistically with a small
            # starter lease, and request a real one. Blocking on the
            # central authority for a first request would put the
            # network back in the hot path.
            bucket = self.local[key] = self._starter_bucket(key)
            self.pending_requests.add(key)

        if bucket.try_consume(1, now):
            self.used[key] += 1
            # Ask for more BEFORE running out, so the refill round
            # trip overlaps with the tokens we still have.
            if bucket.tokens < bucket.capacity * 0.2:
                self.pending_requests.add(key)
            return True

        return False        # locally out of budget: 429

    async def refill_loop(self):
        while True:
            await asyncio.sleep(0.1)
            keys = self.pending_requests.drain()
            if not keys:
                continue
            # ONE batched round trip for all keys needing refill,
            # not one per key. At 100 ms intervals this is 10
            # round trips/sec/node, not 500/sec.
            grants = await self.central.request_leases(
                node_id=self.node_id,
                usage={k: self.used.pop(k, 0) for k in keys})
            for k, tokens in grants.items():
                self.local[k].tokens += tokens

The central authority's allocation policy is where the design gets interesting:

# Redis Lua, atomic. Grant a share of the remaining global budget,
# proportional to what this node has been consuming.
ALLOCATE = """
local key, node, used, window = KEYS[1], ARGV[1], tonumber(ARGV[2]), tonumber(ARGV[3])
local limit = tonumber(ARGV[4])

redis.call('HINCRBY', key, 'consumed', used)
local consumed = tonumber(redis.call('HGET', key, 'consumed') or 0)
local remaining = limit - consumed
if remaining <= 0 then return 0 end

-- How many nodes are actively serving this key right now?
-- Allocating limit/100 when only 3 nodes see the key would give
-- the customer 3% of their limit, which is the failure mode of
-- naive local limiting.
redis.call('HSET', key .. ':nodes', node, ARGV[5])   -- heartbeat
local active = redis.call('HLEN', key .. ':nodes')

-- Grant a bounded slice: enough to cover the refill interval,
-- capped so one node cannot claim the whole remaining budget.
local fair_share = remaining / math.max(active, 1)
local grant = math.min(fair_share, remaining * 0.25)
return math.floor(grant)
"""

Three properties worth defending:

Grants are proportional to observed demand, not equal. A node serving 40 percent of a key's traffic gets roughly 40 percent of the budget, which is what makes the two-tier design work under uneven load balancing.

Grants are capped at a fraction of the remaining budget, so a node that suddenly receives a burst cannot claim everything and starve the others.

Node membership is heartbeated per key, so active reflects nodes actually serving that key rather than the whole fleet. This is the mechanism that fixes the 3-percent-of-limit failure.

The overshoot bound, derived rather than asserted: in the worst case every node holds an unused lease when the global budget is exhausted. With grants sized to cover one refill interval, the maximum outstanding un-consumed capacity is roughly active_nodes x rate x refill_interval. At 100 ms intervals, 10 active nodes and a 1,000 per minute limit, that is about 10 x 16.7 x 0.1 ≈ 17 requests of slack on a 1,000 limit, so under 2 percent. Shorter refill intervals tighten the bound and cost more round trips, which is the actual tuning knob and the honest way to answer "how approximate is it".

Step 5: hot keys and the skew

The top 20 keys are 60 percent of traffic, and they are the ones where naive designs fail.

For a hot key:
  Served by ~all 100 nodes, 1,500 RPS aggregate.
  With 100 ms refills, each node makes 10 refill calls/sec for
  that key = 1,000 calls/sec on ONE Redis key. Contention.

Fixes, in order:
  1. Adaptive refill interval: hot keys get LARGER grants less
     often. A node serving 300 RPS of a key takes a 30-request
     lease every 100 ms, or a 300-request lease every second.
     Fewer round trips, slightly looser bound.
  2. Shard the central counter for very hot keys:
     key:{id}:shard{0..7}, each holding 1/8 of the budget,
     nodes hashed to shards. Removes contention on one Redis key.
  3. For the hottest keys, sticky routing at the load balancer so
     fewer nodes serve each key, which makes local buckets more
     accurate and reduces coordination entirely.

Option 3 is the underrated one. If the load balancer routes by consistent hash on the API key, each key is served by a small number of nodes, local buckets become nearly accurate on their own, and the coordination tier does much less work. The cost is worse load balancing and a rebalance when nodes change, which is a real trade rather than a free win.

Step 6: the response, which is part of the design

HTTP/1.1 429 Too Many Requests
RateLimit-Limit: 1000
RateLimit-Remaining: 0
RateLimit-Reset: 43
Retry-After: 43

Retry-After is not a courtesy, it is a load-shedding mechanism. Without it, a rejected client retries immediately and the rejected traffic costs nearly as much as serving it would have.

And the headers must be present on successful responses too, so a well-behaved client can slow down before hitting the limit rather than discovering it by being rejected. The IETF RateLimit header draft standardises these names, and using the standard names rather than X- variants is worth doing.

Jitter the reset window across customers. If every customer's window resets at the top of the minute, you have built a synchronised thundering herd into your own API.

Step 7: failure modes

Central authority (Redis) unavailable
  -> FAIL OPEN, with a degraded local limit. Each node falls back
     to enforcing limit/expected_nodes locally. Customers with
     concentrated routing get less than their limit, which is
     wrong, and it is much better than the alternative: failing
     closed means a Redis outage takes down the entire API.
     Alert loudly, because the degraded mode is silently unfair.

A node dies holding an unused lease
  -> That capacity is lost until the window resets. With short
     leases this is bounded and small. It is the reason grants
     should cover about one refill interval rather than one
     window.

Clock skew between nodes
  -> Token bucket refill uses ELAPSED time on the local monotonic
     clock, never absolute wall time, so skew affects nothing.
     This is a real advantage of token bucket over window-based
     algorithms, which do depend on agreeing what "this minute" is.

Load balancer changes routing
  -> Per-key node heartbeats expire and `active` shrinks or grows,
     so allocation adapts within a couple of refill intervals.

A customer distributes across many API keys to evade limits
  -> Rate limiting is per identity, so identity has to be the right
     one. Layer limits: per key, per account, per IP, per ASN.
     Costly to evade all four.

Legitimate burst from a large customer
  -> This is the case where token bucket earns its place: capacity
     expresses the allowed burst explicitly, so the answer is a
     product decision encoded in a parameter rather than an
     incident.

Fail open is the right answer here and it is the opposite of the RAG access control design, which fails closed. Explaining why the two differ, that a rate limiter failing closed takes down the API while a permissions check failing open leaks data, demonstrates you are reasoning about consequences rather than applying a rule.

Step 8: what changes at ten times the scale

At 500,000 RPS across 1,000 nodes:

The refill traffic itself becomes significant. 1,000 nodes at 10 refills/sec is 10,000 Redis operations per second just for coordination, before any application traffic. The move is hierarchical: nodes coordinate with a regional aggregator, aggregators coordinate globally, so the fan-in at each level stays bounded.

Sticky routing becomes the primary mechanism rather than an optimisation. At 1,000 nodes, a key served by all of them has an unworkable coordination cost, so consistent-hash routing on the API key at the load balancer keeps each key on a handful of nodes and the local bucket becomes nearly authoritative.

Limit configuration becomes its own system. 500,000 keys with per-endpoint overrides, tiered plans and temporary increases is a configuration distribution problem with its own consistency requirements, and it needs to propagate in seconds without a gateway restart.

Global limits across regions get expensive. A cross-region round trip for coordination is 60 to 200 ms, which no rate limiter can pay per request. The practical answer is per-region budgets allocated from a global limit, rebalanced every few seconds, which accepts that a customer can exceed a global limit briefly while shifting regions.

Production evidence

Cloudflare's published rate limiter uses the sliding-window-counter approximation and their write-up reports the approximation error as negligible in practice against real traffic, which is the primary source for choosing an approximate algorithm over an exact one.

Stripe's published rate limiter design describes multiple layered limiters (a request rate limiter, a concurrency limiter, and a fleet-usage limiter) rather than a single one, which is the argument for layering by identity and by resource rather than a single counter.

Google's Site Reliability Engineering book, chapter 21 ("Handling Overload"), describes client-side throttling and per-customer quotas distributed to tasks, which is the two-tier lease model, and its discussion of why the central authority must not be in the request path is the direct justification for the design here.

Envoy's global rate limiting implements exactly this shape: local token buckets with an external rate-limit service, and its documentation is explicit that the local decision is what keeps latency acceptable.

The IETF RateLimit header fields draft standardises RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset, which is the basis for the response design.

Redis's Lua scripting model provides the atomicity the allocation function needs without a locking protocol, because Redis executes scripts single-threaded.

The debate

The case for centralised counting: exact, simple to reason about, and one place to look when a customer disputes their usage. At moderate scale a single Redis handles it, and the added latency is a fraction of a millisecond.

The case for purely local limits: zero latency, zero dependency, no failure mode. And it is wrong under uneven routing, which is normal, so a customer routed to 3 of 100 nodes gets 3 percent of their limit and complains legitimately.

The case for the two-tier lease design: local decisions at microsecond latency, approximately correct globally, and it degrades to local-only when the central authority is unavailable. The cost is a bounded overshoot and more machinery.

My position: two-tier leases with token buckets, an overshoot bound stated as a number, and fail-open on the central authority.

Token bucket rather than sliding window because burst capacity and sustained rate are separately meaningful to a customer, and an API product wants to sell both ("1,000 per minute, bursting to 100"). No window-based algorithm expresses that, and expressing it in the algorithm rather than in documentation is what makes the limit predictable to the caller.

The property I would insist on is that the overshoot bound is derived and stated, not hand-waved. With grants sized to one refill interval, worst-case slack is roughly active_nodes x rate x interval, so at 100 ms and ten active nodes on a 1,000-per-minute limit that is under 2 percent. "Approximate" without a number is not an engineering answer, and the refill interval is the knob that trades round trips for tightness.

And fail open, deliberately, contradicting what I would do for an authorisation check. A rate limiter that fails closed converts a Redis outage into a total API outage, which is a far worse outcome than a window of unenforced limits. The mitigation is a degraded local limit plus a loud alert, because the degraded mode is silently unfair to customers whose traffic is concentrated on few nodes.

Where I would push back on the framing: "do not become the bottleneck" is the actual requirement and it rules out the obvious design. A centralised counter adds half a millisecond and a hard dependency to every request, and teams build it because it is simple and then discover both. Starting from the latency requirement rather than from the counting problem is what produces the two-tier answer.

Follow-up Q&A

"Why not just use Redis INCR?" Because it adds a network round trip to every request, about half a millisecond same-AZ and one and a half cross-AZ, and it makes one Redis a hard dependency for the entire API. The requirement said the limiter must not become the bottleneck, and a centralised counter is exactly that. It is also worst where it matters most: the hot keys, where 1,500 requests per second means 1,500 coordinated round trips on one key.

"Why token bucket rather than sliding window?" Because burst and sustained rate are separately meaningful to a customer, and token bucket is the only one of the four that expresses both as explicit parameters: capacity is the burst, refill rate is the sustained rate. Sliding window counter is a fine approximation and it can only say "N per window", so any burst policy lives in documentation rather than in the algorithm. Fixed window is just broken, because 100 requests at 11:59:59 and 100 at 12:00:01 is double the intended rate at every boundary.

"How approximate is 'approximate'?" Bounded and derivable, which is the answer that distinguishes an engineering claim from a hope. Worst case, every active node holds an unused lease when the global budget runs out, so the slack is about active nodes times rate times refill interval. At 100 millisecond refills, ten active nodes and a thousand-per-minute limit, that is roughly seventeen requests of slack on a thousand, under two percent. Shortening the refill interval tightens it and costs more round trips, which is the actual tuning knob.

"How do you avoid giving a customer 3 percent of their limit?" That is the failure of naive local limiting, and the fix is that grants are proportional to observed demand rather than equal, and that node membership is heartbeated per key. So active counts the nodes actually serving that key, not the whole fleet, and a node serving forty percent of a key's traffic gets roughly forty percent of the budget. That is the mechanism that makes two-tier work under uneven routing.

"The top twenty keys are sixty percent of traffic. What breaks?" Coordination on those keys. If a hot key is served by all hundred nodes at 100 millisecond refills, that is a thousand Redis operations per second on one key. Three fixes: adaptive intervals so hot keys take larger grants less often, sharding the central counter for the very hottest keys so contention spreads, and sticky routing at the load balancer. That last one is the underrated answer, because consistent-hash routing on the API key keeps each key on a few nodes, which makes local buckets nearly accurate and removes most of the coordination.

"Redis goes down. Fail open or closed?" Open, with a degraded local limit of the global limit divided by the expected node count, and a loud alert. Failing closed converts a Redis outage into a total API outage, which is far worse than a window of unenforced limits. It is worth noting this is the opposite of what I would do for an authorisation check, where failing open leaks data. The rule is not "fail open" or "fail closed", it is "compare the consequences".

"Does clock skew affect this?" Not with token bucket, which is one of its advantages. Refill uses elapsed time on the local monotonic clock, so a node whose wall clock is wrong still refills at the correct rate. Window-based algorithms do depend on nodes agreeing what "this minute" is, and that dependency is real if the counting is distributed.

"What do you return to the client?" A 429 with Retry-After, and the RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset headers on successful responses too, using the IETF draft's standard names. Retry-After is a load-shedding mechanism rather than a courtesy: without it a rejected client retries immediately and the rejected traffic costs nearly as much as serving it. And I would jitter the reset windows across customers, so resetting everyone at the top of the minute does not build a synchronised thundering herd into the API.

Common misconceptions

"Rate limiting needs a central counter." It needs central allocation. The decision can be local, which is what keeps it out of the latency path.

"Fixed window is fine for simple cases." It permits double the intended rate at every window boundary, always, and a client that discovers this will exploit it.

"Approximate means unbounded." The bound is derivable from the grant size and refill interval, and stating it is what makes the design defensible.

"Fail closed is the safe default." For a rate limiter it converts a dependency outage into a total outage. Compare consequences rather than applying a rule.

"The 429 response is an error path." It is a load-shedding mechanism, and Retry-After plus limit headers are what make it work.

Interview delivery note

Start from the requirement that rules out the obvious answer: "The constraint that matters is 'must not become the bottleneck'. A centralised Redis counter adds about half a millisecond to every request and makes one Redis a hard dependency for the whole API, so that design is out. Which means local decisions and central allocation, not central counting."

Then commit to the algorithm with a product reason: "Token bucket rather than sliding window, because capacity and refill rate express burst and sustained rate separately, and that's what an API product actually sells: a thousand a minute, bursting to a hundred. No window algorithm can say that."

Give the two-tier mechanism and then the bound, because the bound is what makes it engineering: "Each node holds a lease covering roughly one refill interval, granted proportional to the demand it's been observing, with per-key node heartbeats so the allocation reflects nodes actually serving that key. Worst case, every node is holding an unused lease when the global budget runs out, so the slack is active nodes times rate times interval: at a hundred milliseconds and ten nodes on a thousand-per-minute limit, that's under two percent overshoot."

The line that shows judgement rather than pattern-matching: "and I'd fail open when the central authority is down, with a degraded local limit and a loud alert. That's the opposite of what I'd do for an authorisation check, where failing open leaks data. Here failing closed turns a Redis outage into a total API outage, which is much worse than a window of unenforced limits."

And the detail that shows you have shipped one: "and Retry-After isn't a courtesy, it's load shedding. Without it a rejected client retries immediately and the rejected traffic costs nearly as much as serving it would have."

The Staff & Team Lead Interview Reference