Design a distributed rate limiter

19 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Choose the algorithm per rule. Each algorithm fits different traffic: - token bucket for API quotas, because it allows short bursts and enforces a steady rate - sliding-window counter for coarse abuse limits, because it needs only two integers per key - exact log only for small, high-value limits such as login attempts
Make the read-modify-write atomic where the state lives. A Lua script or a single atomic command in the counter store removes the race in which two API servers both read "9 of 10 used" and both allow the request.
Check every tier before you consume any. A request is checked against per-key, per-user, per-IP, per-endpoint and global limits. A request denied at one tier must not use up budget at the others.
Decide what happens when the limiter is down. Usually you fail open with a local fallback limit. A limiter outage should never turn into an API outage.
Spend the latency budget carefully. The limiter sits on every request, so it gets under 1 ms at p99. That pushes the design toward in-region stores, connection pooling and, at the largest scale, local token leases.

Requirements

Functional

Limit requests by configurable keys: API key, user, IP, tenant, endpoint and global. Several rules can apply to one request.
Each rule has a limit, a window or refill rate, a burst size and an algorithm.
Return 429 with Retry-After and remaining-quota headers when a request is limited.
Rules change without a deploy. A shadow mode logs decisions without enforcing them.

Non-functional

Under 1 ms of added p99 latency. 99.99% availability, which in practice means failing open.
Accuracy within about 5% of the configured limit within a region. Across regions, a looser bound is acceptable.
Scale to 1M requests per second at peak and 10M active keys.

Out of scope: L3/L4 DDoS scrubbing, billing-grade metering, and adaptive load shedding (related, but a separate mechanism).

Back-of-envelope

Traffic: 1M req/s at peak and 400k req/s on average. Each request checks about 3 rules, so the counter store sees about 3M operations per second at peak.
Store throughput: one Redis shard runs a short Lua script at roughly 50k to 150k calls per second on one core, depending on script size. 3M / 100k = 30 shards, and doubling for headroom gives about 60 primaries. Each has a replica.
Memory, token bucket: two numbers plus key and overhead is about 100 bytes per key. 10M keys × 3 rules × 100 B ≈ 3 GB. That is small.
Memory, sliding log at 1,000 requests per minute per key: a Redis sorted-set entry costs roughly 50 to 80 bytes. 1,000 × 64 B ≈ 64 KB per key, so 10M keys would need about 640 GB. This arithmetic is why logs are reserved for small limits.
Network: about 300 bytes per check, so 3M × 300 B ≈ 900 MB/s fleet-wide, about 15 MB/s per shard.
Latency: a round trip within one availability zone takes about 100 to 300 µs, and the script runs for about 5 to 20 µs. One pipelined round trip per request fits the 1 ms budget. Crossing regions takes 30 to 100 ms and does not fit.

API

service RateLimiter {
  rpc ShouldAllow(CheckRequest) returns (CheckResponse);
}
message CheckRequest {
  string domain = 1;                       // "public-api"
  map<string, string> attributes = 2;      // api_key, user_id, ip, route
  uint32 cost = 3;                         // default 1; bulk endpoints cost more
}
message CheckResponse {
  bool allowed = 1;
  string limited_by = 2;                   // rule name, e.g. "per_user_route"
  uint32 remaining = 3;
  uint32 reset_after_ms = 4;
  uint32 retry_after_ms = 5;
}

The HTTP response to the client looks like this:

HTTP/1.1 429 Too Many Requests
Retry-After: 2
RateLimit-Policy: "per_user";q=100;w=1
RateLimit: "per_user";r=0;t=2

Status 429 comes from RFC 6585, which makes Retry-After optional and leaves how you identify callers and count requests entirely to you. The quota headers follow the IETF RateLimit fields draft: RateLimit-Policy names each policy with its quota q and window w, and RateLimit reports remaining units r and seconds until reset t. Earlier drafts used separate RateLimit-Limit, -Remaining and -Reset fields, and many APIs still send X-RateLimit-*, so clients should tolerate both.

The admin API is PUT /rules/{domain}/{name} with a body such as { fields: ["user_id","route"], algorithm: "token_bucket", capacity: 100, refill_per_sec: 10, mode: "enforce"|"shadow" }.

Data model

Rules live in a config store (etcd, or a database with a cache in front). They are versioned and pushed to every limiter node, where they are compiled into a matcher indexed by domain.

A rule is {name, domain, fields[], algorithm, params, mode, priority}. The number of rules is small, a few thousand at most, so every node keeps all of them in memory.

Counters live in a Redis Cluster. The key is rl:{rule}:{v1|v2}, for example rl:per_user_route:{u_42}|POST /charges. The partition key is the hash slot of the part inside the braces. Redis hashes only that substring, so every counter for one user lands on one shard. That makes a multi-tier check for that user a single script call.

The value depends on the algorithm:

Token bucket: a hash {tokens, ts_ms}.
Sliding-window counter: two integer keys, one per window index, ...:w{floor(now/window)}.
Sliding log: a sorted set scored by timestamp.

Every counter key gets PEXPIRE set to about twice its window or refill horizon. Idle keys then vanish on their own, and memory tracks active keys rather than all keys ever seen.

High-level design

flowchart LR
  C[Client] --> GW["API gateway / Envoy"]
  GW -->|"ShouldAllow (gRPC)"| RLS["Rate limit service"]
  RLS --> RC["Rule cache (in memory)"]
  RLS -->|"EVALSHA one script per shard"| R[("Redis Cluster")]
  CFG["Rule store (etcd)"] -->|watch| RC
  GW -->|allowed| API["Backend services"]
  GW -->|denied| E429["429 + headers"]
  RLS -.->|decisions, shadow hits| M["Metrics / logs"]

Request path.

The gateway extracts the attributes and calls ShouldAllow. It can also link the limiter in as a library to save a network hop.
The service matches the request's attributes against the rule set and builds one key per matching rule.
It groups the keys by Redis shard and sends one script call per shard. Each script checks all of its keys and, only if all of them pass, consumes from all of them.
The gateway forwards the request or returns 429 with headers.

Config path. Rule edits are written to etcd. Limiter nodes watch for changes and swap in a new matcher atomically. A new rule starts in shadow mode, so you can see how many requests it would have rejected before it rejects any.

Deep dives

1. Which algorithm

Fixed window counter (INCR plus expire). This is the cheapest option. Its flaw is the window boundary: a client can send the full limit at 0:59 and again at 1:00, which is 2× the limit inside two seconds.
Sliding log. It is exact over any window. Memory and work grow with the limit, though, and a flood of rejected requests can still grow the log unless rejected requests are not recorded.
Sliding-window counter. It estimates the count as prev × (1 − elapsed/window) + current. That costs two integers and assumes traffic was spread evenly through the previous window. Cloudflare tested it on 400 million requests from 270,000 sources: only 0.003% of requests were wrongly allowed or limited, and the estimated rate was off by 6% on average (Cloudflare). It works well for abuse limits.
Token bucket. It is described by a capacity B and a rate r. It allows bursts up to B and a sustained rate of r, which matches how people describe API quotas ("10 per second, bursts of 100"). The state is two numbers, updated lazily when a request arrives, with no background refill job. GCRA is an equivalent single-timestamp form. AWS API Gateway throttles this way, with the rate as the refill and the burst as the bucket size, and calls its limits best-effort targets rather than guaranteed ceilings (AWS docs).
Leaky bucket. Requests join a queue that drains at a fixed rate, so output is perfectly smooth but bursts wait instead of passing. NGINX limit_req works this way: excess requests are delayed up to burst, nodelay turns the delay into immediate rejection, and rejections return 503 unless you set limit_req_status 429 (NGINX docs). Choose it to protect a backend that needs an even arrival rate.
Concurrency limiter. It caps requests in flight per caller instead of requests per second. A rate limit cannot tell a 5 ms call from a 30 s report export; a cap such as 20 concurrent requests can. Stripe runs one beside its token bucket for expensive endpoints (Stripe). It needs a decrement when the request ends, plus a TTL so crashed requests do not leak slots.

Choice: token bucket by default, sliding-window counter for per-IP abuse limits, and a log only where limits are tiny and exactness matters, such as 5 password attempts in 15 minutes.

2. Atomic and distributed enforcement

Why GET then SET fails. Doing GET, deciding in the service and then SET loses updates under concurrency. Two nodes each read 9 tokens, and both write back 8.

Ways to make it atomic:

a Lua script, which Redis runs to completion while blocking all other server activity, so it is atomic (Redis docs)
INCR for fixed windows
a WATCH/MULTI retry loop, which works but suffers under contention

Shard placement. Hash tags keep all of a user's tiers on one shard, so the check-all-then-consume step is one atomic script. The global and per-IP tiers live on other shards. For those, the service checks them in a second call and refunds the first if the second denies. The refund window allows a very small overshoot, and that is acceptable here.

Very high rates. At 1M req/s with hot global keys, have each limiter node lease tokens in batches, for example take 50 tokens with one script call and spend them locally. This cuts store calls by about 50×. The cost is that up to nodes × batch tokens can be outstanding, so batch size is the knob that trades accuracy against load.

Multiple regions. Either split the quota per region in proportion to traffic, or run local limits and reconcile counts asynchronously every second or so. A global synchronous counter puts a cross-region round trip on every request, which fails the latency requirement.

3. Multi-tier keys and the order of checks

Rules form a hierarchy:

API key at 100/s
user at 300/s across that user's keys
tenant at 5k/s
endpoint POST /charges at 1k/s globally
a global safety limit

Evaluation is check-all-then-consume. If the per-user tier passes and consumes a token, but the tenant tier then rejects, the user has lost a token for a request that never ran. Under sustained rejection that drains honest budgets. Order the checks from most specific to least, because the specific tiers reject most often, which saves remote work.

Response headers report the tier with the lowest remaining fraction. Bulk endpoints charge cost = 10 instead of needing separate rules. Tenant overrides sit at a higher priority on the same rule name, so an enterprise customer's higher limit replaces the default rather than adding to it.

Down the stack

Layer 1The contract

For a token-bucket rule (B, r) on key k, over any interval of length t within one region, allowed cost is at most B + r·t, plus at most nodes × lease_batch when leases are on.
A denied request does not consume budget at any tier.
A decision takes at most 1 ms at p99. If the store does not answer within about 5 ms, the service falls back to a per-node local bucket set to limit / node_count and records a fail_open metric.
A rule change takes effect within about 5 seconds.

Layer 2The mechanism

The token-bucket script receives KEYS = [k1..kn] and ARGV = [now_ms, cost, cap1, rate1, ...]. It works in two passes:

For each key it runs HMGET k tokens ts, computes tokens = min(cap, tokens + (now − ts) × rate / 1000) and checks tokens ≥ cost.
If every check passed, it runs HSET k tokens (tokens−cost) ts now and PEXPIRE k horizon for each key.

It returns either the remaining tokens or the index of the rule that denied.

The service loads the script once with SCRIPT LOAD and calls it by SHA (EVALSHA), so each call carries 40 bytes of hash instead of the script body. The script cache is not persisted and can be empty after a restart or a replica promotion, so the client must handle NOSCRIPT by reloading, and inside a pipeline it should send plain EVAL (Redis docs). Every script must name its keys in KEYS, which is what lets Redis Cluster route it and reject keys that span slots.

Envoy's global rate limiting takes the same descriptor-based shape. The proxy sends a RateLimitRequest holding a list of descriptor entries, and a rate limit service answers OK or OVER_LIMIT for each descriptor. Envoy then returns 429, gives the call a 20 ms timeout by default, and lets traffic through on errors unless failure_mode_deny is set (Envoy filter docs, proto). Fail-open is the proxy default, not just a choice in this design.

Layer 3The machine

Redis execution. Redis runs commands on one thread. A 3-key script takes about 10 to 20 µs of CPU, which is where the 50k to 150k calls per second per core figure comes from. I/O threads can parse sockets in parallel, but scripts still run one at a time.
Network. In one availability zone a round trip costs about 100 to 300 µs, mostly kernel network stack and NIC interrupt work at each end. Persistent pooled connections avoid a TCP handshake per check. A request and response each fit in one segment, well under the roughly 1,460-byte MSS.
Which clock to use. Use the Redis server's clock (TIME), or pass in the caller's clock and accept skew. Within a service, measure elapsed time with CLOCK_MONOTONIC. Wall clocks can step backward under NTP, which would mint negative elapsed time. Clamp now − ts at 0.

Why it's built this way

Every request pays for the limiter, so it needs a sub-millisecond check. That rules out cross-region coordination and disk-backed stores.
A sub-millisecond check needs in-memory state with tiny entries, so the design uses token buckets (two numbers) rather than logs.
Many stateless API nodes share each key, so the state must live centrally and be updated atomically. That leads to a single-threaded store and a script.
One central store has limits on throughput and availability. That leads to sharding by hash tag, local leases for hot keys, and failing open.
Wrong limits hurt customers more than missing ones, which is why shadow mode, override priorities and limit headers exist.

Failure modes

Load at 10×, for example a retry storm from a broken client. Denials still cost a store call each. Mitigations: - Cache "denied until T" locally on each node for the key, so repeat offenders are rejected in memory. - Put a per-IP local limiter in front of the remote one. - Throttle in your own clients too. Google's SRE book describes clients that track requests and accepts over two minutes and start dropping requests locally once requests exceed about twice the accepts, because even a rejection costs the backend work (Google SRE book).
Hot key, for example the global limit or a large tenant's key. One shard saturates. Mitigations: - Split the key into N sub-buckets, each with limit/N, and pick one at random. - Or use local leases.
Store shard down. Fail open to local per-node buckets, and alert. If that shard holds limits that protect a fragile dependency, fail closed for that rule only. This is a per-rule setting.
Region outage. Traffic shifts to another region, which suddenly carries double the load. The per-region split quotas must be recomputed from the traffic share, or the other region rejects legitimate users.
Bad rule push. A typo sets the limit to 1/s. Mitigations: new rules go through shadow mode, a rule that would reject more than X% of traffic needs a second approver, and rollback is a version pointer flip.

In the wild

Google Cloud, 2025: the quota checker becomes the outage. Service Control checks authorization, policy and quota on every Google Cloud API request. On 12 June a policy record with blank fields replicated worldwide in seconds and hit a new quota-check code path that had no error handling and no feature flag, so the binary crash-looped in every region. The kill switch took about 40 minutes to roll out, but us-central1 needed up to 2 hours 40 minutes more because restarting tasks overloaded the backing Spanner table without randomized backoff. Google committed to making Service Control fail open and to feature-flagging such changes (Google Cloud incident report).
Cloudflare, 2017: approximate counting at edge scale. Cloudflare counts per-client rates in a memcache cluster in each data center using only GET and INCR, increments asynchronously so requests never wait on the counter, and once a client is over the limit stores a mitigation flag with a known expiry that every server caches locally. The sliding-window estimate was wrong on 0.003% of 400 million test requests (Cloudflare).
Stripe, 2017: four limiters, not one. Stripe runs a per-user token bucket in Redis, a concurrent-request limiter, and two load shedders that reserve capacity for critical calls such as creating charges. In one month the token bucket rejected millions of requests while the last-resort worker shedder rejected only about 100. Each limiter was dark-launched first, and every code path fails open on errors (Stripe).

Trade-offs

Option	Strengths	Weaknesses	Choose when
Token bucket	Bursts plus a steady rate, 2 numbers per key	Burst size is one more knob to explain	Public API quotas
Sliding-window counter	2 integers, smooth, no boundary spike	Approximate if traffic inside the window is uneven	Per-IP abuse, coarse limits
Sliding log	Exact over any window	Memory and CPU grow with the limit	Small, security-sensitive limits
Fixed window	Simplest, one `INCR`	2× burst at boundaries	Internal, non-critical limits
Central Redis	Accurate, simple	Extra hop, an availability dependency	Most deployments
Local leases	Few store calls, survives store blips	Overshoot up to nodes × batch	Very high rate global keys
Fail open	API stays up	Limits not enforced while the limiter is down	Quotas and fairness
Fail closed	Protects the downstream	Limiter outage becomes an API outage	Guarding a fragile dependency

Leadership lens

Build first: the in-process library with token bucket, rule matching, shadow mode and headers, backed by Redis. Add leases and multi-region split quotas when measurements show you need them.
Ownership: the platform or edge team owns the service and its SLO. Product teams own their rules as code with review. Support needs a self-serve view that answers "why was customer X limited".
Cost drivers: Redis memory and CPU, which grow with active keys × rules and with checks per second. The tail-latency budget the limiter consumes is the hidden cost on every endpoint.
Rollout: shadow mode for two weeks per new rule, then enforce for 1% of keys, then everyone. Watch the 429 rate per tenant and support tickets.
Design-review questions: What is each rule's fail mode? Do retries count? Are limits per region or global?

Check yourself

Why is a sliding log reserved for small limits such as login attempts, rather than used for a 1,000 per minute API quota?
Show answer
A log stores one sorted-set entry per request at roughly 64 bytes, so 1,000 per minute is about 64 KB per key and about 640 GB for 10M keys. A token bucket needs about 100 bytes per key, roughly 3 GB for 10M keys and 3 rules.
Why must a multi-tier check be check-all-then-consume rather than consuming tier by tier?
Show answer
If the per-user tier consumes a token and the tenant tier then rejects, the user loses budget for a request that never ran, and sustained rejection drains honest budgets. The script checks every key first and consumes from all of them only if all pass.
The Redis shard holding a set of counters goes down. What should the limiter do?
Show answer
By default fail open to a per-node local bucket of about limit / node_count, record a fail_open metric and alert, so a limiter outage does not become an API outage. Rules protecting a fragile dependency can be set to fail closed for that rule only.
What do local token leases buy at very high rates, and what do they cost?
Show answer
Each node takes a batch of tokens (for example 50) in one script call and spends them locally, cutting store calls by about 50 times. The cost is possible overshoot of up to nodes × batch tokens, so batch size trades accuracy against store load.

Sources and further study

Primary

RFC 6585, section 4: defines 429 Too Many Requests and deliberately leaves the counting method unspecified.
IETF draft-ietf-httpapi-ratelimit-headers-11: the current RateLimit-Policy and RateLimit field syntax with worked examples.

Systems docs

Envoy: global rate limit filter: descriptors, the 429 response and failure-mode behaviour.
envoyproxy/ratelimit: the reference descriptor service, with shadow mode and a local cache of over-limit keys.
Redis: Scripting with Lua: atomicity, the volatile script cache and key-declaration rules.
AWS API Gateway request throttling: token-bucket limits layered from per-client to account to Region.

Books

Site Reliability Engineering, Beyer et al. (Google), chapter 21 "Handling Overload": per-customer quotas, request criticality and client-side adaptive throttling.
System Design Interview, Volume 1, Alex Xu, chapter 4 "Design a Rate Limiter": the five classic algorithms and a Redis-backed design at interview depth.

Other curricula

Azure Architecture Center: Rate Limiting pattern: frames rate limiting from the caller's side, pacing outbound work through a queue and leased capacity partitions so you stay under someone else's throttle.
donnemartin/system-design-primer: has no rate limiter chapter of its own and points to Stripe's post as the reference answer.

Watch

Rate Limiting system design: Token Bucket, Leaky Bucket, Sliding Logs (Tech Dummies): a whiteboard walk through the algorithms and the distributed race.
Design a Distributed Rate Limiter (Hello Interview): an interview-paced breakdown with Redis, scaling and failure handling.

Free resources

Scaling your API with rate limiters (Stripe): the four limiter types Stripe runs, including load shedders, and how they roll them out.
How we built rate limiting capable of scaling to millions of domains (Cloudflare): the sliding-window counter approximation and its measured error.
An alternative approach to rate limiting (Figma): the memory cost of logs and a bucketed-window compromise.
Fairness in multi-tenant systems (AWS Builders' Library): how Amazon layers quotas, admission control and load shedding.
Rate limiting, cells, and GCRA (Brandur Leach): the single-timestamp form of the token bucket explained clearly.
RateLimit header fields for HTTP (IETF draft): the emerging standard for communicating quota to clients.

Open in the interactive app: practice, quiz, mock interview →