Design a Distributed Rate Limiter

Your company runs a public API behind an API gateway fleet of a few hundred nodes in three regions. Customers are on plans such as 100 requests per second per API key or 10,000 requests per day per endpoint, and some internal services need protection from retry storms.

Design the rate limiting layer: it decides for every request whether to let it through or reject it with HTTP 429, and it must enforce the same limit no matter which gateway node or region a customer hits. It sits on the hot path of every call, so it must add almost no latency and must never become the reason the API is down.

In 45 minutes, agree on what is being limited, compare limiting algorithms, decide where counters live and how gateways share them, and explain what happens across regions and when the counter store fails.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Core Building Blocks · problem 3 of 70

Ask before you design. Try answering each yourself, then compare.

1. What do we limit on?
   Typical answer

   API key primarily, plus per-IP for unauthenticated traffic and optional per-endpoint rules. Rules are configurable per plan.

2. How exact must limits be?
   Typical answer

   Within about 5-10% of the configured limit is fine. Billing-grade quotas (monthly totals) are a separate, exact system.

3. Are short bursts allowed?
   Typical answer

   Yes. A customer on 100 req/s may burst to 200 for a moment, then must settle back to 100.

4. What latency can the limiter add?
   Typical answer

   Under 1 ms at p50 and 5 ms at p99 per request.

5. Should a customer's limit be global across regions or per region?
   Typical answer

   Global in principle, but slightly exceeding it during cross-region lag is acceptable.

6. If the limiter cannot decide, do we allow or reject?
   Typical answer

   Allow (fail open) for most traffic; protecting availability matters more than precise limits.

7. What is the traffic?
   Typical answer

   About 10 billion requests a day, peaking near 600,000 per second, from roughly 50 million keys and IPs.

Requirements

Functional

• Decide allow or reject for each request based on configurable rules (key, IP, endpoint, plan).
• Return 429 with Retry-After and X-RateLimit-Limit/Remaining headers.
• Update rules without redeploying gateways.
• Expose per-key throttling metrics.

Non-functional

• Added latency under 1 ms p50, 5 ms p99.
• Handle 600k checks per second at peak, scaling horizontally.
• Limit accuracy within 10% under normal operation.
• The limiter must never take the API down: fail open within 5 ms if the counter store is unreachable.

Out of scope

• Billing and monthly quota accounting.
• DDoS mitigation at the network edge (L3/L4 floods).
• Authentication of API keys (assume the gateway already did it).

Back-of-the-envelope estimates

• Checks: 10 B requests/day ≈ 115k per second on average, around 600k at peak. Every one needs a decision.
• State: 50 M active keys × ~2 rules × ~100 bytes per counter ≈ 10 GB. All of it is hot and short-lived, so it belongs in memory with TTLs, not on disk.
• Counter store ops: one atomic script per check means 600k ops/s. A single in-memory shard comfortably handles 100k+ simple ops/s, so plan for 10-12 shards (with replicas) for headroom, or far fewer once gateways batch locally.
• Latency budget: an in-region round trip is ~0.3-0.5 ms; cross-region is 70-150 ms, which rules out synchronous global counters.

The latency budget, not storage, drives the design: in-region shared counters, local shortcuts for the hottest keys, and asynchronous cross-region reconciliation.

API

// called in-process by the gateway on every request
check(descriptor: {apiKey, ip, route, plan}, cost=1)
    -> {allowed: bool, limit, remaining, resetAt, retryAfterMs}

// admin
PUT  /v1/rules/{ruleId}  {match: {plan, route?}, algorithm, rate, burst, window}
GET  /v1/limits/{apiKey} -> current usage per rule

The check is a library call into a local agent rather than a remote service, so the common case adds no extra network hop beyond the counter store itself.

Data model

Counters live in an in-memory key-value cluster, sharded by hashing the counter key, e.g. rl:{apiKey}:{ruleId}. A token bucket stores {tokens, last_refill_ms}; a sliding window counter stores two integers keyed by window index. Every counter has a TTL a little longer than its window so idle keys disappear on their own. Putting the API key in a hash tag keeps all of one customer's counters on the same shard, so a multi-rule check is a single script call.

Rules are a small relational table (rules(rule_id, match, algorithm, rate, burst, window, version)), cached in every gateway and refreshed by push, because they change rarely and are read on every request.

High-level design

A client request lands on an API gateway node. After authentication, the gateway's limiter module builds the descriptors for the request (API key, IP, route) and matches them against the rules it holds in memory; the rules service pushes changes to every node within seconds.

For each matching rule the limiter runs one atomic script on the regional counter store: refill the token bucket based on elapsed time, try to take a token, and return the remaining count. The script makes read-modify-write a single step, so 300 gateways can share a counter without races. If the answer is allow, the gateway forwards the request to the backend service and attaches rate limit headers to the response; otherwise it returns 429 with Retry-After without touching the backend.

Very hot keys skip the round trip: a gateway leases a small batch of tokens and spends them locally. Every decision is also emitted as an event for dashboards and alerts. Each region has its own counter store, and a reconciler exchanges per-key usage between regions every second or so to approximate a global limit.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Choosing the algorithm

Fixed window counters are cheapest but allow 2× the limit across a window boundary. A sliding log of timestamps is exact but costs memory per request, which is unaffordable at 600k/s. The sliding window counter keeps the current and previous window counts and weights the previous one by how much it still overlaps, giving near-exact results with two integers. The token bucket stores a token count and last refill time; it naturally expresses "100/s with bursts of 200", which matches how plans are sold. Use token buckets for per-second rates and sliding window counters for longer windows such as per-day caps.

Sharing counters without races or latency

Two gateways reading 99, both writing 100, lets an extra request through. Doing the refill, check and decrement in a server-side script makes the update atomic and costs one round trip. To shave load further, a gateway can lease tokens: ask the store for 20 tokens at once for a hot key and spend them locally, returning to the store only when they run out. The cost is accuracy, since up to N_gateways × lease_size requests can slip past at the edge, so lease sizes scale with the key's rate and drop to 1 for small limits. Keys with tiny traffic always go to the store.

Limits across regions

A synchronous global counter would add 100 ms to every request, so each region enforces locally. Two workable options: static split, where each region gets a share of the limit based on recent traffic (simple, but a customer who shifts traffic to one region gets throttled early), or async sharing, where every region counts locally and a reconciler broadcasts per-key usage every 500 ms to 1 s, and each region subtracts the others' usage from its view of the budget. Async sharing can overshoot by about one sync interval's worth of traffic, which fits the 10% accuracy target.

Failing safely

The limiter protects the API; it must not become an outage itself. Calls to the counter store get a strict timeout of a few milliseconds and a circuit breaker. When the store is unreachable, fall back to a local in-memory bucket per gateway with the limit divided by the number of gateways in the region, which is crude but still blocks abuse. Rules default to the last known good copy if the rules service is down. Shadow mode, where a new rule logs would-be rejections without enforcing them, lets teams roll out limits safely.

Failure modes

• If a counter store shard fails, its replica is promoted within seconds; in the gap, gateways fall back to local per-node buckets.
• If the whole counter store is unreachable, the circuit breaker opens and gateways fail open with coarse local limits, alerting on-call.
• If the rules service is down, gateways keep enforcing the last rules they received; only rule changes are delayed.
• If cross-region sync stalls, each region enforces only its local view, so a customer could reach up to N_regions times the limit; cap with a static per-region ceiling.
• If a single huge customer key overloads one shard, split its counter into sub-keys across shards and sum them.

Core algorithm in code

import time


class TokenBucket:
    """Refills `rate` tokens per second up to `burst`. State is two numbers, so it fits one hash in Redis."""
    def __init__(self, rate, burst):
        self.rate, self.burst = rate, burst
        self.tokens, self.updated = float(burst), None

    def allow(self, now, cost=1):
        if self.updated is not None:
            self.tokens = min(self.burst, self.tokens + (now - self.updated) * self.rate)
        self.updated = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True, 0.0
        return False, (cost - self.tokens) / self.rate   # seconds until retry


class SlidingWindowCounter:
    """Two fixed windows blended by overlap: O(1) memory per key, smooth at window edges."""
    def __init__(self, limit, window_s):
        self.limit, self.window = limit, window_s
        self.counts = {}                                  # window index -> count

    def allow(self, now):
        idx = int(now // self.window)
        elapsed = (now % self.window) / self.window
        prev, cur = self.counts.get(idx - 1, 0), self.counts.get(idx, 0)
        estimate = prev * (1 - elapsed) + cur
        if estimate >= self.limit:
            return False
        self.counts[idx] = cur + 1
        for old in [k for k in self.counts if k < idx - 1]:
            del self.counts[old]
        return True


tb = TokenBucket(rate=5, burst=10)          # 5 req/s sustained, bursts of 10
t = 100.0
burst = [tb.allow(t)[0] for _ in range(12)]
print("token bucket, 12 requests at once:", burst.count(True), "allowed,", burst.count(False), "rejected")
ok, retry = tb.allow(t)
print("retry-after hint: %.2fs" % retry)
print("after 1s:", sum(tb.allow(t + 1.0)[0] for _ in range(10)), "allowed (refilled ~5)")

sw = SlidingWindowCounter(limit=100, window_s=60)
allowed = sum(sw.allow(59.0) for _ in range(100))      # 100 at the end of window 0
early = sum(sw.allow(60.0 + 6) for _ in range(100))      # 10% into window 1
late = sum(sw.allow(60.0 + 54) for _ in range(100))      # 90% into window 1
print("sliding window: end of w0 =", allowed, "| 6s into w1 =", early, "| 54s into w1 =", late)

Trade-offs

• A central counter store gives consistent limits across gateways but adds a network hop to every request.
• Local token leasing removes most round trips but lets traffic overshoot by up to gateways times lease size.
• Failing open keeps the API available when the limiter breaks but briefly removes protection from abusive clients.
• Async cross-region sharing keeps latency low but lets a customer exceed the global limit by one sync interval of traffic.
• Token buckets allow friendly bursts but make it harder to explain to customers exactly how many requests a window permits.

What a strong answer shows

• Compares at least three algorithms with their accuracy and memory costs.
• Makes counter updates atomic and explains the race being prevented.
• Keeps the added latency within budget, including tricks for hot keys.
• Chooses fail-open versus fail-closed deliberately and designs the fallback.
• Handles multi-region with an explicit accuracy trade-off.
• Returns useful 429 responses with Retry-After and remaining-quota headers.

Mistakes to avoid

• Keeping counters in each gateway's memory and ignoring that the load balancer spreads a client across nodes.
• Read-then-write counter updates that race under concurrency.
• Storing a timestamp per request (sliding log) at hundreds of thousands of requests per second.
• Making cross-region calls synchronously on the request path.
• Letting a counter store outage reject all traffic.

Follow-ups to expect

• How would you limit by cost rather than request count, e.g. expensive search calls? (Weighted cost per request; the bucket takes N tokens.)
• How do you rate limit an internal service that is overloaded rather than a customer? (Adaptive concurrency limits driven by latency, not fixed quotas.)
• How would you give clients a smooth experience instead of hard 429s? (Expose remaining quota headers, recommend backoff with jitter, optionally queue briefly.)
• How do you test a new rule safely? (Shadow mode logging would-be rejections before enforcing.)

Practice next