Rate limiter

A distributed rate limiter shared by many gateway servers, at about 100,000 requests a second. The questions are which algorithm to use, how many servers can update one counter without races (two updates overwriting each other), and what happens when the limiter itself fails.

Design a rate limiter for an API gateway, shared by many gateway servers, handling about 100,000 requests a second.

Requirements

Functional

  • Limit requests per API key, per user id, and per IP address for routes without login. Rules differ per route and plan, for example 100 a minute on login and 1,000 a minute on reads.
  • Allow short bursts above the steady rate, because a page load fires 10 calls at once.
  • Reject calls over the limit with HTTP 429 Too Many Requests and a Retry-After header (how long to wait). Add remaining-quota headers to every response.
  • Change rules without redeploying the gateways.

Non-functional

  • Throughput: about 100,000 checks a second, one per request, across all gateway servers.
  • Latency: the check adds under 1 ms at p50 (the median request) and under 5 ms at p99 (99 out of 100 requests).
  • Accuracy: a client should not exceed its limit by more than a few percent across all gateways together.
  • Availability: the limiter must never be the reason the API is down. Each rule defines whether it fails open (allows traffic) or fails closed (blocks traffic) when the limiter breaks.

Out of scope

  • DDoS protection at the network layer. That is the job of the CDN or a scrubbing service, which filters attack traffic.
  • Billing for API usage (it can read the same counters later).
  • Bot detection beyond simple limits.

Estimate

  • Checks: every request needs one check, so about 100,000 checks a second, the same as the gateway.
  • Store operations: one atomic script per check (read, refill, decrement in one round trip) → 100,000 operations a second on the counter store.
  • Shards: plan for about 25,000 operations a second per in-memory store node to leave headroom → 100,000 / 25,000 = 4 shards, each with a replica = 8 nodes.
  • Memory: about 10M active keys (keys, users, IPs) x ~100 bytes (key name, tokens, timestamp, overhead) ≈ 1 GB in total. Tiny.
  • Network: 100,000 checks x ~200 bytes ≈ 20 MB/s between gateways and the store. Fine.
  • Latency budget: a same-zone round trip is about 0.5 ms, which fits the 1 ms p50 budget; it rules out a cross-region store.

API

  • POST /v1/limits/check {key: "apikey:ak_42", rule: "orders.write", cost: 1} -> 200 {allowed, remaining, reset_ms, retry_after_ms}
  • GET /v1/rules?version= -> 200 {version, rules[]} (gateways poll every 30 s)
  • PUT /v1/rules/{id} {match: {route, method, plan}, algorithm, rate, burst, fail_mode} -> 200
  • GET /v1/limits/{key} -> 200 {rule, remaining, reset_at} (support and debugging)
  • POST /v1/orders (any client call over its limit) -> 429 {error} with Retry-After and RateLimit-Remaining headers

Data model

  • rules(id PK, route_pattern, method, plan, key_type (apikey|user|ip), algorithm, rate_per_s, burst, fail_mode (open|closed), version, updated_at): PostgreSQL, small, cached in every gateway.
  • Counter (in-memory store): rl:{rule_id}:{key} -> hash {tokens, last_refill_ms}, TTL = time to refill completely, so idle keys disappear.
  • overrides(key PK, rule_id, rate_per_s, burst, expires_at): raised limits for a partner, or a temporary block.
  • limit_events (stream, sampled): {key, rule, allowed, ts} for dashboards and abuse investigations.

A request, step by step

  1. A request for POST /orders arrives with API key ak_42. From its local copy of the rules, the gateway matches it to the rule "orders.write: 10 a second, burst 20, key = API key".
  2. The limiter runs one Lua script on the shard that owns rl:orders.write:ak_42. The script reads the tokens and the last refill time, then adds the rate times the elapsed time, capped at the burst. If at least 1 token is left, it subtracts 1.
  3. Read, refill and decrement happen atomically (as one step that nothing can interrupt) on the store. So two gateways cannot both spend the last token.
  4. The script returns {allowed, remaining, reset}. If the call is allowed, the gateway forwards it to the backend and adds RateLimit-Remaining headers. If not, it answers 429 with Retry-After, without touching the backend.
  5. Rules change through PUT /rules. Gateways poll the rules service every 30 seconds and switch to the new version, so no deploy is needed.
  6. If the counter store does not answer within 5 ms, the limiter applies the rule's fail mode. Normal APIs fail open with a coarse local bucket, where each gateway enforces its share of the limit. Login and OTP routes fail closed.

Deep dives

Choosing the algorithm

Weak: fixed window counter. Count requests per key per calendar minute, and reset at the start of each minute. It is simple and needs one INCR. But a client can send the full limit at 12:00:59 and again at 12:01:00. That doubles the rate across the boundary. Also, every client resets at the same instant.

Good: sliding window. A sliding log keeps a timestamp for every request. It is exact, but memory grows with the limit, which is bad at 1,000 a minute per key. A sliding window counter instead weights the previous window's count by how much of it still overlaps. It costs two counters per key and is accurate to within a few percent.

Great: token bucket. Each key has a bucket that holds up to "burst" tokens and refills at "rate" tokens per second. Each request spends one token. It needs only two numbers per key, and it allows the short bursts that real clients make, such as a page load firing 10 calls.

It also expresses both "average 10 a second" and "burst 20" directly. Expensive requests, such as a bulk export, can spend more tokens. The leaky bucket is a close relative that smooths output. It is more useful for shaping outgoing traffic than for an API gateway.

Trade-off: a token bucket needs the elapsed time, so clocks matter. Use the store's clock inside the script, not each gateway's clock. Then a gateway with a wrong clock cannot create extra tokens.

Sharing one counter across many gateways without races

Weak: a counter in each gateway's memory. Say 12 gateways sit behind a round-robin load balancer. Each one sees a twelfth of a client's traffic, so the client gets 12 times the limit. The factor also changes every time you scale.

Good: a shared store with read-then-write. Gateways GET the counter, check it and SET it back. Under load, two gateways read "1 token left" at the same moment and both allow the request. This is a classic race condition. Even INCR followed by a check is atomic only for a fixed window.

Great: one atomic script in a sharded in-memory store. The read, refill and decrement run as a single Lua script on the shard that owns the key, so they cannot interleave. Keys are hashed across 4 shards, so the 100,000 checks a second spread out. One key always lands on one shard, so there is never a race across shards.

For extremely hot keys or a tighter latency budget, add a local layer. Each gateway pre-fetches a small batch of tokens, say 10, and spends them locally. It syncs with the store when they run out.

Trade-off: the store hop costs about 0.5 ms per request and is a shared dependency. The batching layer saves that hop, but lets a client briefly exceed its limit by up to one batch per gateway. Choose by how exact the limit must be. Login protection needs an exact limit; a read API is fine with an approximate one.

When the limiter fails

The limiter runs on every request. So when the limiter fails, your API fails in the same way.

Weak: wait on the store, and return 500 when it is down. A short glitch in the counter store becomes a full API outage. The cause is a component that exists to protect the API.

Good: a tight timeout, then fail open. If the store does not answer in about 5 ms, allow the request and count the event. The API stays up, and you are briefly unprotected.

Great: a fail mode per rule, with a local fallback. Each rule says whether it fails open or fails closed. Read APIs fail open, but switch to a coarse local token bucket in each gateway: the limit divided by the number of gateways. You still have rough protection.

Sensitive routes such as login, OTP and payments fail closed, because unlimited OTP requests cost money and enable abuse. A circuit breaker (a switch that stops calls to a failing dependency for a while) stops calling a sick store for a few seconds. That avoids paying the timeout on every request. Alert on fail-open counts, so nobody discovers a week later that limits were off.

Trade-off: failing open trades protection for availability. Failing closed trades availability for safety. The senior answer decides per route and says why, instead of using one global switch.

What breaks

  • A counter-store shard fails over to its replica. Replication is asynchronous, so keys on that shard lose a few recent decrements, and some clients briefly get extra requests. That is acceptable for rate limiting. You notice it as a failover event and a short dip in the 429 rate.
  • The whole counter store is unreachable: limiters time out at 5 ms and open their circuit breakers. Depending on the rule, they use local buckets or fail closed. Fail-open count alerts fire.
  • A bad rule is pushed, such as a limit of 1 a minute on a busy route. The 429 rate for that rule jumps. Roll back to the previous rules version, which gateways pick up within 30 seconds.
  • One abusive key becomes a hot key on one shard, and shard CPU alerts fire. Cache a local "blocked until" decision in each gateway, so repeat calls never reach the store.
  • Clients retry 429s immediately and multiply the load. Make your own SDKs honour Retry-After, and document backoff with jitter.

What each level is expected to cover

Mid level: A Mid candidate should pick an algorithm, such as token bucket or sliding window, and explain it. They should keep counters in a shared fast store such as Redis, return 429 with Retry-After, and limit per API key, user or IP.

Senior: A Senior candidate also makes the check atomic with a script, to avoid races. They shard the store, size it from 100,000 checks a second, and keep the added latency under a millisecond or two. They decide fail open versus fail closed per route, with a local fallback. They handle clock skew and hot keys, and change rules without deploys.

Common mistakes

  • Counting in each gateway's memory, so the real limit grows with the number of gateways.
  • GET then SET on the shared counter, which races under load.
  • Fixed windows without mentioning the double burst at the window boundary.
  • Making the API depend on the limiter with no timeout or fail-open plan.
  • Putting the counter store in another region, so every request pays a cross-region round trip.
  • Returning 500 or 503 instead of 429, so clients cannot tell "slow down" from "broken".

Follow-up questions

  • How would you rate-limit across two regions with one global quota per customer?
  • A partner needs 10 times the default limit for a day. How do you support that?
  • How would you limit by cost (a bulk export costs 50 tokens) instead of by request count?
  • How do you test that the limiter is accurate at 100,000 requests a second?
  • What would you change if the check had to add less than 100 microseconds?

Lessons behind this answer