Design a rate limiter

A rate limiter answers one question, millions of times a second: may this caller make one more request right now? It sits in front of your API and replies “yes” or “not yet, try again in 400 ms”. On a single server that is a counter and an if. The design gets interesting when the same API key lands on a hundred gateway pods at once, when the counter store stalls during the 10:00 tatkal booking rush, when one partner suddenly sends 40% of all traffic, or when a typo in a rule starts rejecting real UPI payments. In this problem you design a shared rate-limiting platform for a public API — payments, OTP sending, ticket booking — that every team can configure without writing code, that adds almost no latency, and that is never the reason the API is down.

Understand the problem

A rate limiter is a small policy engine with a counter attached, and weak answers design the counter before agreeing on the policy. Separate two ideas out loud. Rate limiting is about one caller: “you have used your share.” Load shedding is about the whole system: “we are overloaded, so low-priority work goes first, whoever sent it.” This design is about the first; the second has its own article on backpressure and load shedding.

Functional requirements

1. Clients should be limited per identity, per rule. For example, “a growth-tier API key may call POST /v1/payments 20 times a second, with bursts up to 40”. The identity can be an API key, user ID, tenant, or IP address for anonymous traffic such as a login page.
2. Clients should be told where they stand. Rejected requests get 429 Too Many Requests with Retry-After; successful responses show how much quota is left, so good clients slow down early.
3. Operators should be able to add or change rules per endpoint and tier without a deploy, live everywhere within about 30 seconds.
4. One request can be subject to several limits at once — a per-second burst limit, a daily quota and a per-IP guard. If any says no, the answer is no.

Non-functional requirements

• Low added latency. The check runs on every request, so it must add under 2 ms at p99 and under 1 ms at p50.
• High throughput. About 1M requests per second at peak, around 300k/s on a normal day. Peaks are sharp: booking traffic can jump 5–10× in the first minute after the 10:00 tatkal window opens.
• Availability above accuracy. The check path targets 99.99%, and the limiter must never take the API down. What happens when the counter store is unreachable is decided per rule in advance.
• Good-enough accuracy. Within about 5% of the configured limit. Brief over-admission during a failover is acceptable; steady false rejections of honest clients are not.
• Many keys. Around 100M distinct identity-and-rule combinations per day, a few million active in any minute.
• Fast, safe configuration. Rule changes and rollbacks visible on every limiter within 30 seconds.

Out of scope

• Volumetric DDoS at layers 3 and 4. Packet floods are absorbed upstream by network scrubbing and the CDN. This limiter works at layer 7, on parsed, usually authenticated requests.
• WAF rules and bot detection. They decide whether a request is malicious; we decide whether a legitimate caller has had enough.
• Billing-grade metering. Our counts may be a few percent off. Invoices come from a separate metering pipeline.
• Authentication. We assume the gateway has already turned a token into an API key, a user and a tier.
• System-wide load shedding based on CPU or queue depth, as noted above.

The set-up

Plan the approach

Satisfy each functional requirement with the simplest design, then spend most of your time in the deep dives — that is where this problem is won. Say the shape early: “a check on the hot path, a counter store behind it, and a control plane for rules off the hot path.” The deep dives follow naturally: algorithm, correct counting, scaling, failure, regions and safe rule changes.

Core entities

• Rule (policy). What to match (route, method, tier), which identity to count, the algorithm and its numbers, a mode (enforce or shadow), a failure mode (open, closed or local) and a version.
• Client key. The identity a rule counts against: an API key such as k_8f2a, a user ID, an IP address or IPv6 /64 prefix, a tenant ID.
• Counter state. Per rule and key: tokens plus a timestamp, or a window count. In memory with a TTL; nothing here needs to be durable.
• Decision. Allowed or not, which rule decided, quota left per rule, and how long to wait.

Written as configuration, two rules for the payments endpoint look like this:

- id: pay-burst
  match: { route: "POST /v1/payments", tier: growth }
  key: api_key
  algorithm: token_bucket
  rate_per_s: 20
  burst: 40
  mode: enforce            # or: shadow
  on_store_failure: local  # open | closed | local

- id: pay-daily
  match: { route: "POST /v1/payments", tier: growth }
  key: api_key
  algorithm: fixed_window
  limit: 10000
  window: 1d               # calendar day, Asia/Kolkata
  on_store_failure: open

API

There are three surfaces: the internal check, the contract clients see, and the rules admin API.

The check. In production this is gRPC; it is shown as HTTP for readability. The gateway sends descriptors — facts about the request — not counter keys. The rate-limit service owns the mapping to rules and keys, so a rule change never needs a gateway change.

POST /v1/limits:check
Content-Type: application/json

{
  "domain": "public-api",
  "descriptors": {
    "route": "POST /v1/payments",
    "api_key": "k_8f2a",
    "tier": "growth",
    "ip": "49.36.1.7"
  },
  "cost": 1
}

{
  "allowed": false,
  "decided_by": "pay-burst",
  "retry_after_ms": 50,
  "policies": [
    { "id": "pay-burst", "limit": 20,    "window_s": 1,     "remaining": 0,    "reset_s": 1 },
    { "id": "pay-daily", "limit": 10000, "window_s": 86400, "remaining": 7311, "reset_s": 50400 },
    { "id": "ip-guard",  "limit": 300,   "window_s": 60,    "remaining": 288,  "reset_s": 41 }
  ],
  "rules_version": 42
}

The client-facing contract. A rejected request gets 429 Too Many Requests (RFC 6585) with Retry-After, which RFC 9110 defines as an HTTP date or a whole number of seconds — so even a 50 ms wait becomes Retry-After: 1. For quota information, use the RateLimit-Policy and RateLimit fields from the IETF HTTP APIs draft (revision -11 at the time of writing). RateLimit-Policy describes each quota as q units per w seconds and stays stable; RateLimit reports what is left now: r remaining, and t seconds until that changes. Many APIs still send older X-RateLimit-* headers; if clients depend on them, send both during a migration.

HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Cache-Control: no-store
Retry-After: 1
RateLimit-Policy: "burst";q=20;w=1, "daily";q=10000;w=86400
RateLimit: "burst";r=0;t=1, "daily";r=7311;t=50400

{
  "type": "https://iana.org/assignments/http-problem-types#quota-exceeded",
  "title": "Payment requests for this API key are over the per-second limit",
  "violated-policies": ["burst"]
}

A 429 must not be cached, hence no-store. When Retry-After and RateLimit both appear, the draft tells clients to obey Retry-After, so make them agree. A token bucket does not map perfectly onto “q per w”: advertise the sustained rate and let r show the burst actually available. And use 503, not 429, when shedding load for everyone — 429 means “you, specifically, slow down”.

The rules admin API, low-traffic and off the hot path:

PUT  /v1/rules/pay-burst            create or replace a rule; returns the new version (43)
GET  /v1/rules?route=/v1/payments   list the rules that match a route
POST /v1/rules/pay-burst:shadow     evaluate and log, never reject
POST /v1/rules/pay-burst:enforce    start rejecting
POST /v1/rules:rollback             body: to_version = 42
GET  /v1/rules:status               which version each limiter pod has loaded

Back-of-envelope estimates

Show the arithmetic; these numbers decide how many Redis shards you need and whether the limiter should be a separate service. (For the method, see back-of-envelope estimation.)

Counter operations. 1M requests/s at peak. Most requests match two rules for the same API key (burst and daily), some also a per-IP rule. Rules for one identity share a Redis call (see below), so plan for about 1.2 script calls per request: 1M × 1.2 ≈ 1.2M script calls/s.

Shards. Redis executes commands on one thread per instance. A short script costs a few times a plain GET, and you want CPU near 50% so tail latency stays flat. Budget about 40k script calls/s per primary: 1.2M ÷ 40k = 30 primaries, plus one replica each, so 60 small nodes.

Memory. A token bucket is a tiny hash: a 40-byte key name, two fields, and overhead for the hash table and expiry entry — call it 150 bytes. Even if all 100M daily keys were alive at once: 100M × 150 B = 15 GB, about 500 MB per primary, and idle per-second buckets expire within seconds. Memory is not the constraint; operations per second are. For contrast, an exact sliding log for 1,000 requests per minute stores up to 1,000 timestamps per key — roughly 70 KB. A million such keys would need 70 GB, which is why the sliding log is kept for small limits.

Latency budget. Gateway to rate-limit service in the same zone: about 0.25 ms round trip. Service to Redis: another 0.25 ms. Script plus rule matching: under 0.1 ms. Total ≈ 0.6 ms at p50, around 1.5 ms at p99 under load, with a hard 3 ms deadline capping the worst case.

Service fleet. The service mostly waits on the network, so one pod handles about 20k checks/s: 1M ÷ 20k = 50 pods, doubled for headroom across three zones = 100 pods.

Connections. 100 pods × 30 primaries × 4 pooled connections = 12,000 connections, 400 per primary. If instead 600 gateway pods and 3,000 service pods talked to Redis directly: 3,600 × 30 × 4 ≈ 432,000 connections, over 14,000 per primary. Keep that number for the next section.

High-level design

Build the design one requirement at a time; by the end it works in one region at moderate traffic.

Clients should be limited per identity, per rule

First decide where the check runs. There are four reasonable places, and they can be combined.

Pick the gateway as the enforcement point and a separate, stateless rate-limit service as the brain. The gateway already knows the caller after authentication, and rejecting there means a throttled request never touches a backend (see API gateway). The separate service keeps policy logic in one codebase, so a new algorithm ships once, and the connection estimate seals it: 12,000 Redis connections instead of 432,000. The price is a hop of about 0.3 ms, which fits the 2 ms budget, and a new dependency that must fail gracefully. Services that need business-aware limits (“at most ₹2 lakh of payouts per hour per merchant”) call the same service from middleware; internal traffic can call it from a sidecar.

For the counters, use Redis: in memory, one command at a time, atomic increments, key expiry and small Lua scripts next to the data. A relational database is the wrong tool for a million throwaway writes a second.

The flow is short:

1. The client calls POST /v1/payments with its API key.
2. The gateway authenticates the key, looks up the tier, and sends the route, key, tier and IP to the rate-limit service.
3. The service finds the matching rules (hard-coded for now), builds one key per rule such as rl:{k_8f2a}:pay-burst, and runs a script on Redis that checks and updates the counter in one step.
4. If allowed, the gateway forwards the request; if not, it returns 429 straight away.

Clients should be told where they stand

The decision already holds what a client needs: which policy decided, what is left, and when it refills. The gateway turns that into headers on every response, so a client that sees r=2 can pace itself before it ever gets a 429.

Three rules of thumb keep the contract honest:

• Retry-After comes from the rule that said no. If several deny, use the longest wait, in whole seconds, rounded up.
• Decide whether rejected requests cost quota. For API limits, usually not. For abuse limits such as login attempts, yes — otherwise a script hammering the endpoint is never slowed further.
• Do not reveal more than you mean to. Headers tell an attacker exactly how hard to push; for login and OTP rules, send only the 429.

Operators should change rules without redeploying

Hard-coded rules turn every change into a deploy. Move them into a control plane: a Rules API that validates and versions changes, a Rules DB as the source of truth with history, and a config store holding immutable, numbered snapshots of the rule set. Each rate-limit pod watches the config store, loads snapshot v43 in the background and swaps it in with one pointer change.

The important property is that the hot path never reads the database. Rules sit in each pod’s memory, compiled into a lookup table keyed by route, so matching takes microseconds. If the config store goes down, pods keep the last snapshot (with a copy on local disk for restarts). etcd or ZooKeeper give you watches for push; a versioned file in object storage polled every 10 seconds also works. This is the classic control plane versus data plane split: the control plane may be slow and strongly consistent; the data plane must be fast and survive without it.

Per-customer overrides (“customer X gets 200/s”) are just more specific rules that replace the tier default rather than stacking on it.

One request can be subject to several limits at once

A payment call from k_8f2a might match three rules: a burst limit and a daily quota on the key, plus a per-minute guard on the IP. The request passes only if every rule allows it.

Two details make this both fast and correct:

• Same identity, one call. Wrap the identity in a Redis Cluster hash tag — the part in curly braces, {k_8f2a}. Only the tag is hashed, so every bucket for that key lands in the same slot and one script can check them atomically. The script checks every bucket first and only then takes from all of them, so a request rejected by the daily quota does not also burn a burst token.
• Different identities, parallel calls. The IP rule hashes to another slot, so it is a separate, parallel call, and the two cannot be atomic together. Accept the small leak (a request rejected by the IP rule may already have used a burst token), or check the cheap IP guard first — abusive traffic tends to trip it, so that also saves work.

You now have a working limiter: correct, configurable and fine for one region at modest traffic. The deep dives are about what breaks when you push it.

Deep dives

Which algorithm should we use?

The algorithms differ in state per key, treatment of bursts, accuracy, and Redis operations per check.

Fixed window counter. Keep one counter per key per window — rl:{k_8f2a}:min:1001 for the minute starting at 10:01 — INCR it, give it an expiry, compare with the limit. One integer, one round trip. Its flaw is the boundary: a client can send the full limit at the end of one window and again at the start of the next, and each window looks fine.

Fixed windows also synchronise clients: if every window resets at :00, every throttled client retries at :00 — a tatkal rush in miniature, once a minute. For long, calendar-shaped quotas that is a feature: “10,000 calls per day, resetting at midnight IST” is easy for customers and support to understand.

Sliding window log. Store a timestamp per request in a sorted set: drop old entries with ZREMRANGEBYSCORE, count with ZCARD, add with ZADD. It is exact, but state grows with the limit and each check is several commands. Use it where limits are small and exactness matters, such as “at most 5 OTP SMS per phone number per 15 minutes” — five entries, and every extra SMS costs real money.

Sliding window counter. Keep counts for the current and previous fixed windows, and estimate the rolling count by assuming the previous window’s requests were spread evenly. Twenty-five percent into the current minute, 75% of the previous minute still overlaps the rolling window, so it contributes 75% of its count.

Two integers per key, and the boundary burst is gone. The error comes from the evenness assumption: one large CDN analysed 400 million requests from 270,000 sources and found only 0.003% wrongly allowed or limited, with the estimate on average 6% off the true rate. A good default for “N per minute” and “N per hour” rules.

Token bucket. Each key has a bucket of up to b tokens that refills at r tokens per second. A request takes a token (or several, for expensive calls); an empty bucket means 429. No background job drips tokens in: store the count and the last update time, and add elapsed × r before deciding. Managed API gateways usually expose exactly two throttling knobs, rate and burst — the refill rate and bucket size.

The gain is explicit, tunable bursts: one app screen fires a dozen calls at once, and a bucket of 40 absorbs that while the long-run rate stays at 20 a second. The cost is two parameters to tune, and a backend that must survive a full bucket arriving in one instant.

Leaky bucket. Two things share this name. As a queue, requests join a FIFO and leave at a fixed rate: perfectly smooth output, but callers wait. That suits outbound calls, such as your OTP service feeding an SMS aggregator that accepts exactly 100 messages a second. As a meter, it is the token bucket upside down — a level that drains steadily and rises per request; common reverse proxies implement it with a burst allowance and a choice to delay or reject.

GCRA (generic cell rate algorithm). A leaky-bucket meter that stores one timestamp per key: the theoretical arrival time (TAT) of the next request at exactly the allowed rate. With emission interval T = period ÷ limit and burst B, a request at now is allowed when max(TAT, now) + T − now is at most B × T; then TAT becomes max(TAT, now) + T. One number per key, no drip. The cost: it is harder to explain than “20 per second”, and it needs a single clock.

The recommendation: token bucket for per-second rules, fixed calendar windows for daily and monthly quotas, a sliding log only for tiny security limits — three small, well-tested scripts.

Here is the token bucket as a Redis Lua script, called as EVALSHA <sha> 1 rl:{k_8f2a}:pay-burst 40 20 1:

-- Token bucket: check and take, atomically, inside Redis.
-- KEYS[1]  bucket key, e.g. rl:{k_8f2a}:pay-burst
-- ARGV[1]  capacity (largest burst, in tokens)
-- ARGV[2]  refill rate (tokens per second)
-- ARGV[3]  cost of this request (usually 1)
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

-- One clock for every caller: the Redis server's, in milliseconds.
local t   = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity   -- a missing key is a full bucket
local last   = tonumber(state[2]) or now

-- Lazy refill: add what dripped in since the last call, never above capacity.
tokens = math.min(capacity, tokens + math.max(0, now - last) * rate / 1000)

local allowed, retry_ms = 0, 0
if tokens >= cost then
  tokens  = tokens - cost
  allowed = 1
else
  retry_ms = math.ceil((cost - tokens) * 1000 / rate)
end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
-- Expire the key when the bucket would be full again: then it carries no information.
redis.call('PEXPIRE', KEYS[1], math.ceil((capacity - tokens) * 1000 / rate) + 1000)

return { allowed, math.floor(tokens), retry_ms }

Three choices are deliberate. The script reads time with Redis’s TIME command, because 100 pods never agree on the time to the millisecond. It refills lazily, so idle keys cost nothing. And it expires the key when the bucket would be full again: a missing key and a full bucket mean the same thing, so memory tracks recently active keys only.

How do we count correctly across many limiter servers?

Bad: local counters in each pod. Fast and dependency-free, but with 100 pods behind a round-robin load balancer, a client limited to 100 per minute can get 100 × 100 = 10,000. Dividing the limit by the pod count fails the other way: traffic is never spread perfectly, so one pod rejects honest clients while others sit on unused quota. Local counters are still useful as a coarse first stage, as you will see.

Better, but broken: shared Redis with read-then-write. Each pod reads the count, compares, and writes back count + 1. Two pods handling the same key at once both read 99, both write 100, and both allow: 101 requests admitted, counter says 100. When one key sends thousands of requests a second, this is normal behaviour, and the limiter over-admits exactly when it matters most.

There is a quieter race too: INCR a new key, then EXPIRE it separately, and a pod that crashes between the two leaves a counter that never expires. The Redis documentation calls out exactly this case in its rate-limiter pattern.

Good: atomic primitives. INCR is atomic, so “INCR, then compare the returned value with the limit” is race-free, and a MULTI/EXEC transaction around INCR and EXPIRE closes the expiry gap. Enough for fixed windows and sliding window counters.

Great: one Lua script per algorithm. A token bucket reads two values, computes, and writes two; no single command does that. Redis runs a Lua script atomically — nothing else runs on that instance meanwhile — so there is no interleaving to reason about. Load each script once with SCRIPT LOAD, call it by digest with EVALSHA, and re-send the source if Redis answers NOSCRIPT after a failover. The cost: a slow script blocks the whole shard, so keep scripts short and loop-free.

Optimistic locking (WATCH, then MULTI/EXEC, retry on conflict) looks tempting but collapses under contention: on a key with thousands of requests a second, most transactions fail and retry, multiplying load at the worst moment.

How do we scale Redis and handle hot keys?

Sharding. One instance cannot do 1.2M script calls a second, so shard. Redis Cluster splits the key space into 16,384 hash slots; a key’s slot is CRC16 of the key modulo 16,384, and each primary owns a range. If the key contains a hash tag in curly braces, only the tag is hashed — that is what puts one identity’s buckets on one shard. The cluster-aware client in each pod keeps the slot map and calls the right primary directly, with no proxy hop.

A client-side consistent hashing ring over standalone instances also works, but Redis Cluster gives you resharding and replica promotion out of the box.

Replicas are for failover, not reads. Replication is asynchronous, so a replica returns stale counts, and stale counts mean over-admission: send limiter traffic to primaries only. When a replica takes over, increments it had not yet received are lost and a few keys briefly get extra quota — within the 5% budget, though not for billing.

Hot keys. One partner sends 40% of all traffic: 400k requests a second on one API key. Because of the hash tag, all of it lands on one shard budgeted for 40k calls a second. The shard saturates, and every other key on it — thousands of innocent customers — starts timing out. A hot key is a noisy neighbour inside your own limiter (the general pattern is in hot keys and cache stampedes).

• Bad: a bigger machine. Redis runs commands on one thread; more cores do nothing for one key.
• Good: a local deny cache. Most hot keys are hot because they are over the limit — a runaway script or an attack. When a check says “deny, retry in 800 ms”, the pod and the gateway remember that in memory and reject locally until it expires, without calling Redis. One CDN goes further, counting asynchronously and checking only a cached “mitigate this client” flag on the request path. The cost: the key stays blocked for the cached period even if a token drips in, so cap it at the retry time or one second.
• Great: token leasing for legitimately hot keys. If the partner’s contract really is 500k/s, the key is hot and allowed. Let each pod lease 100 tokens in one script call and spend them locally: Redis traffic for that key drops from 400k to 4k calls a second. The cost is accuracy — up to 100 pods × 100 tokens = 10,000 outstanding, 2% of one second’s limit. Size leases at about 1% of the per-second rate, minimum 1, so ordinary keys still hit Redis every time.
• Also an option: split the key into 8 sub-buckets with different hash tags ({k_8f2a#0} to {k_8f2a#7}), each with an eighth of the limit, picked at random. One key spreads across shards, at the cost of false rejections near the limit when picks are uneven.

What happens when Redis is slow or down?

The counter store will have bad minutes: a failover, a slow shard, a network blip. One large payments API’s public write-up is blunt about the rule: catch errors at every level, so a limiter bug or an unavailable Redis makes the limiter fail open and the API keeps working.

• A tight timeout. Normal p99 for a script call is about 1 ms, so allow 3 ms and give up. Never retry on the hot path: a retry doubles load on a struggling Redis, which is how one slow shard becomes a retry storm. More in timeouts, retries and backoff.
• A circuit breaker per shard. If more than half the calls to a shard fail within 5 seconds, stop calling it for 10 seconds, then let a trickle of probes through — otherwise every request still waits 3 ms before falling back. More in circuit breaker.
• A failure mode per rule, chosen when the rule is written:
  • Fail open (the default): allow and alert. A few minutes without limits is far cheaper than an outage. Right for most APIs.
  • Fail closed: reject. Right for OTP sends — each SMS costs money, and an unlimited OTP endpoint invites SMS-pumping fraud — and for logins, where unlimited guesses enable credential stuffing. The cost: that feature is down while the shard is.
  • Local fallback: each pod enforces the limit divided by the pod count from an in-memory bucket. Roughly right when traffic is balanced, never wildly wrong.

Only keys on the sick shard degrade; the other 29 carry on, and Redis Cluster promotes a replica once the primary has been unreachable for longer than the cluster node timeout (15 seconds in the default config, often tuned lower). Finally, treat bugs like outages: a crash in rule matching must take the same fail-open path, and you need a kill switch, per rule and global, that turns enforcement off in one click.

How do we enforce limits across regions?

Suppose you run active-active in Mumbai, Hyderabad and Singapore, and a partner with servers in two data centres has a contract for 1,000 requests per minute in total. Where does the counter live? (See also multi-region and active-active.)

Bad: one global Redis in one region. Exact, but every check from elsewhere pays a cross-region round trip — tens of milliseconds within India, 100 ms or more between continents — many times the 2 ms budget. And when that region has a bad day, limiting breaks everywhere.

Good: independent per-region limits. Giving each region the full limit is fine if DNS or anycast pins each client to one region, but a client that spreads out gets up to 3×. Splitting the limit by expected traffic (600, 300, 100) has a trap: when a region fails and its traffic moves, clients are squeezed into the survivors’ smaller shares and throttled mid-incident. Recomputing shares every 10 seconds from observed traffic helps — Envoy’s quota-based mode uses the same idea of periodic load reports — at the cost of a central allocator.

Great: count locally, share counts asynchronously. Each region enforces against its own Redis and, once a second, ships deltas for busy keys (above, say, 10% of their limit) to the others. A region decides with its local count plus the latest remote counts it has heard.

Checks stay local and fast, and a lost link only means stale remote numbers, not an outage. The cost is accuracy: a client can overshoot by roughly its rate elsewhere times the sync delay — for 1,000 per minute and a one-second sync, a handful of requests. You are choosing availability and latency over exactness, the AP side of CAP and PACELC. With dozens of edge locations, replace point-to-point exchange with a gossip protocol.

How do we roll out rule changes safely?

A bad rule is an outage you cause yourself. Type window: 1d instead of window: 1m on the UPI collect endpoint, and at the evening peak almost every real payment gets a 429 within 30 seconds.

Bad: rules in code. Every change is an hours-long deploy, and so is the rollback. Nobody tunes limits that are this painful to change, so they rot.

Good: rules in a database, polled. Changes land in 30 seconds — and so does a mistake, on every pod at once, while pods briefly disagree about which rules apply.

Great: versioned snapshots and a release pipeline.

1. Validate. Check the schema and sanity bounds — a change that tightens a limit more than 10× needs a second approver — and replay the last hour of traffic to report who would have been rejected.
2. Publish an immutable snapshot, v43, to the config store.
3. Shadow. Pods evaluate the new rule and log “would deny” with the key, but always allow. The payments write-up in the references dark-launches every new limiter this way. Leave it for a day.
4. Canary. Enforce on one pod, then 10%, then all, watching 429 rate and latency — ordinary canary deployment, applied to configuration.
5. Roll back by pointing pods at v42. Each pod reports its loaded version, so a dashboard shows when the fleet has converged.

How should clients behave when they are limited?

• Slow down early. When r nears zero, spread the remaining calls over t seconds.
• Honour Retry-After. If it is missing, back off exponentially with full jitter and cap retries; without jitter, everyone throttled at 10:00:00 returns together at 10:00:01.
• Make retries safe. A retried POST /v1/payments carries an idempotency key, so it is never charged twice.
• Do not align resets on the server. Token buckets refill continuously, which spreads clients out. For short windows, start each key’s window at its first request; keep calendar resets for daily and monthly quotas, where predictability matters more.

The final design

Put the pieces together. The hot path is the gateway, the rate-limit service and Redis; everything else is either asynchronous or off to the side.

Follow one payment request through the system:

1. Edge guard. The request reaches a gateway pod, which first checks its in-memory deny cache and a coarse local token bucket set well above any real customer’s rate. Floods and already-blocked keys stop here at almost zero cost.
2. Check. The gateway sends descriptors — route, API key, tier, IP — to the rate-limit service over gRPC with a 3 ms deadline.
3. Count. The service matches rules from its in-memory snapshot, groups keys by identity, and runs one script per identity on the primary that owns the hash tag. Very hot keys spend leased tokens instead; if a shard is slow or its breaker is open, each rule’s failure mode decides.
4. Allow. The gateway forwards the request to the payments service and adds RateLimit headers to the response.
5. Reject. If any rule denies, the gateway returns 429 with Retry-After and RateLimit, and caches the denial until the retry time.
6. Share. Once a second, regions exchange deltas for busy keys, so global limits hold within a few percent with no cross-region call on the hot path.
7. Change. Operators edit rules through the Rules API, which validates them, stores them in the Rules DB and publishes a snapshot that the config store pushes to every pod — shadow, then canary, then enforce. Decision logs, including “would deny” events, feed the dashboards that show whether a rule does what you meant.

Check it against the requirements: about 0.6 ms typical latency, capped at 3 ms; 30 primaries at about 40k script calls/s each, with hot keys taken off them; no hot-path dependency without a timeout and a per-rule fallback; atomic counting within a region and a few percent across regions; rule changes in 30 seconds with one-click rollback.

What interviewers look for by level

Follow-up questions

What if we need per-tenant fairness rather than fixed limits?

Fixed limits stop one caller; fairness shares capacity when it is scarce. Use hierarchical buckets: a global bucket sized to what the backend can really take, with per-tenant buckets inside it. When the system is quiet, tenants may borrow unused capacity; when it is busy, each falls back to its guaranteed share, weighted by plan. That needs a capacity signal such as backend latency, which makes the limiter part load shedder. More in noisy neighbours and fairness.

What if a single customer is 40% of traffic?

Put their key on the leasing path so it never melts a shard. Then isolate them — dedicated Redis shards, ideally a dedicated cell — so their bad day stays theirs. And treat it as a business conversation: a customer that size needs a negotiated limit, a capacity plan and a contact you call before throttling them.

What if we must limit concurrent requests rather than rate?

Some endpoints are expensive for as long as they run, such as report exports. Limit how many are in flight per key: on start, add the request ID to a sorted set scored by an expiry time; on finish, remove it; before counting, drop expired entries so a crashed pod cannot leak a slot. Reject with 429 when the set is full; the RateLimit draft has a concurrent-requests quota unit to advertise it. The payments write-up in the references found a concurrency limiter cured contention on its most expensive endpoints while firing far less often than its rate limiter.

What if limits must be exact because they are tied to money?

Then it is not a rate-limiting problem. Prepaid credits or a paid monthly cap need a ledger: a strongly consistent store where each unit is debited in a transaction and audited later. Keep the rate limiter in front to absorb bursts, and let the usage-metering system produce invoice numbers. Mixing the two gives a limiter that is too slow and billing that is too loose.

What if the limiter itself is attacked?

Defend in layers, cheapest first. Scrubbing and the CDN absorb volumetric floods. The gateway’s local bucket and deny cache reject floods without touching the rate-limit service. Unauthenticated traffic is keyed on the IP — or the /64 prefix for IPv6, since one host can own millions of addresses — and expensive rule evaluation waits until after authentication. The service protects itself with its own concurrency limit and per-rule fallbacks. One CDN reported mitigating 400,000 requests per second against a single domain this way without slowing legitimate users.

How to say it in the interview

“I’ll design a shared rate limiter for a public API: about a million requests a second at peak, under 2 milliseconds of added latency, and the rule that the limiter must never take the API down.

Enforcement happens at the API gateway, which calls a small stateless rate-limit service over gRPC. The service holds rules in memory and maps the API key, route and IP to counter keys in Redis Cluster. For each identity, one Lua script checks and updates all its buckets atomically; a hash tag keeps those buckets in one slot. That removes the read-then-write race, and reading the clock inside Redis means pods never disagree on time.

Algorithm: token bucket for per-second limits because it gives an explicit burst, fixed calendar windows for daily quotas, and a sliding log only for tiny limits like OTP sends. Clients get 429 with Retry-After, plus RateLimit headers on every response so they can slow down early.

Sizing: about 1.2 million script calls a second at 40 thousand per primary is 30 shards. Memory is tiny. The real risks are hot keys and failures. For hot keys, a local deny cache handles abusers, and token leasing handles legitimately huge customers. For failures, a 3 millisecond timeout, a circuit breaker per shard, and a failure mode per rule: fail open by default, fail closed for OTP and login, or a local fallback bucket.

Across regions, each region decides locally and shares counts for busy keys every second, so a global limit holds within a few percent without a cross-region call. Rules live in a database and ship as versioned snapshots: validated, shadowed, canaried, and rolled back in one click.”

Concepts used in this design

• Rate limiting — the algorithms and vocabulary this design builds on.
• API gateway — the enforcement point for all external traffic.
• Redis — atomic counters, TTLs, Lua scripts and Redis Cluster.
• Consistent hashing — the alternative to hash slots for spreading counters.
• Hot keys, cache stampede and invalidation — why one key can sink a shard.
• Timeouts, retries and backoff with jitter — the 3 ms deadline and polite clients.
• Circuit breaker — failing fast when a shard is sick.
• Retry storm — why the hot path never retries.
• Backpressure and load shedding — the system-wide sibling of per-client limits.
• Multi-region and active-active — per-region budgets and count sharing.
• CAP theorem and PACELC — choosing availability over exact global counts.
• Gossip protocol — sharing counts across many locations.
• Control plane vs data plane — keeping rule management off the request path.
• Canary, blue-green and feature flags — shadow mode and canaries for rules.
• Noisy neighbours and fairness — sharing scarce capacity between tenants.
• Idempotency — making retries after a 429 safe.

References and further reading

1. RFC 6585, Section 4: 429 Too Many Requestsrfc-editor.orgDefines the 429 status code, the optional Retry-After, and the rule that 429 responses must not be cached.
2. RFC 9110, Section 10.2.3: Retry-Afterrfc-editor.orgExact syntax of Retry-After: an HTTP date or a whole number of seconds.
3. RateLimit header fields for HTTP (IETF draft-ietf-httpapi-ratelimit-headers)datatracker.ietf.orgThe RateLimit-Policy and RateLimit fields, their q/w/r/t parameters, and how they interact with Retry-After.
4. Redis INCR command, including the rate limiter patternredis.ioAtomic counters, and the INCR-then-EXPIRE race that a Lua script or MULTI/EXEC fixes.
5. Scripting with Lua (Redis documentation)redis.ioWhy scripts run atomically, EVALSHA and the script cache, and effects replication (why TIME is safe in scripts).
6. Redis Cluster specificationredis.io16,384 hash slots, CRC16 key hashing, hash tags, and asynchronous replication that can lose recent writes on failover.
7. Scaling your API with rate limitersstripe.comA payments API's four limiter types, token buckets in Redis, failing open, and dark-launching new limits.
8. How we built rate limiting capable of scaling to millions of domainsblog.cloudflare.comThe sliding window counter approximation and its measured error on 400 million requests; async counting with a cached mitigation flag.
9. Envoy proxy: global rate limitingenvoyproxy.ioA proxy calling a central rate-limit service, local token buckets as a first stage, and quota-based sharing across instances.
10. Rate limiting, cells, and GCRAbrandur.orgClear walk from fixed buckets to leaky bucket to GCRA, including why one shared clock matters.