Design a distributed API rate limiter

Questions first. What is limited: per API key, per user, per IP, per tenant, per route? Is the limit a hard contract or a protection, so is a small overshoot acceptable? Are bursts legitimate? What should a rejected caller see? Where does the limiter run, inside the gateway or as a service? What happens if the limiter's store is unreachable, for all routes alike?

Assumed scope: per API key and per tenant limits, 1,000 requests a minute per key, bursts allowed, three regions with users spread across them, enforcement at the gateway, a small overshoot tolerated, and a 2 ms budget. Out of scope: DDoS protection at the network layer, billing, and the dashboard for editing limits.

Planning figures for the exercise, not facts about any company.

• Traffic: assume 100,000 requests a second at peak across 50 gateway nodes, so 2,000 a second per node.
• Central check per request: every check is a read-modify-write. At the 5,000-writes-a-second planning figure for one durable node, 100,000 ÷ 5,000 = 20 shards. An in-memory store does better, so benchmark it, but the order of magnitude says one box is not enough.
• Latency budget: a same-AZ round trip is 0.5 ms and cross-AZ is 1 to 2 ms. One round trip to a same-AZ shard fits the 2 ms p99. A cross-region round trip is 70 to 90 ms, about 40 times the budget, so counting cannot cross regions on the request path.
• Denied traffic: one abusive key sending 5,000 requests a second against a 1,000-a-minute limit would land 5,000 checks a second on one shard. If each gateway remembers a denial locally for 1 s, that falls to 50 nodes × 1 = 50 checks a second, a 100-fold cut.
• State: 5 million active keys × about 100 B = 500 MB. Memory is not the constraint.
• Retries: a client that retries 3 times across 3 layers turns one blocked call into 3 × 3 × 3 = 27 requests, each costing a check. This is why the response must say when to come back.

Gateways enforce; a sharded in-memory store holds the counters; a config service holds the limits.

1. Algorithm. A token bucket per (api_key, route class). Refill rate is 1,000 ÷ 60 = 16.7 tokens a second; capacity is the burst size, the limit itself if bursts are legitimate or smaller if the limit is protective. Tokens are stored as a value plus a last-refill time.
2. Atomic check. One server-side script does read, refill, decide and write in a single round trip. The two-step "increment, then set expiry" pattern is wrong, because a crash between them leaves a key that never expires. The script takes time from the store, not from the caller, so a skewed client clock cannot refill its own bucket. It returns {allowed, remaining, retry_after_ms}. The key expires after a full refill time (60 s) plus slack, so idle keys disappear.
3. Sharding. The gateway library picks the shard by consistent hash of the tenant id, so a key's bucket and its tenant's bucket sit on the same shard and one script checks both levels. One call enforces a per-key and a per-tenant limit at once. Each shard has a replica for failover. The cost is that one very large tenant puts all its traffic on one shard, so watch per-shard load and give such a tenant its own shard or a local-bucket tier.
4. Request path. The gateway looks up the key in a local denial cache. If it is marked denied until a time still in the future, it returns 429 immediately. Otherwise it makes one call with a 5 ms timeout. On deny, it returns 429 with Retry-After and rate limit headers, and caches the denial for the smaller of the retry time and 1 s.
5. Config. Limits per plan live in a config store. Gateways cache them for 30 s. Changing a limit alters bucket parameters, not bucket state. New limits start in shadow mode, logging what they would have rejected, before enforcement.

Hard problem 1: three regions. A global count is out because of the 70 to 90 ms round trip. Split the quota instead. Each region gets a share of each key's limit that sums to the whole: 333, 333 and 334 requests a minute by default. Every few seconds a rebalancer reads each region's recent use per key (published asynchronously) and shifts unused quota to regions that are rejecting, keeping a floor per region. The invariant is that shares always sum to the limit, so the global total cannot be exceeded except briefly during a shift. Compare the alternative of every region holding the full 1,000 and syncing counts: up to 3 × 1,000 = 3,000 requests can be admitted against a limit of 1,000 before the first sync lands.

Hard problem 2: the limiter is down. Decide this before the outage. On timeout or error the gateway falls back to a local in-process bucket per key, sized at about twice the fair share (limit ÷ node count × 2), so protection continues with up to 2× looseness (a key whose traffic lands unevenly can be rejected early, which is the price of a fallback). Routes where abuse is costly, like login, password reset and SMS sending, fail closed. A circuit breaker stops the gateway from calling a sick shard at all, and the call is a single attempt with no retry, because retries at three layers would make the shard's problem 27 times worse.

Observability. Count allowed and denied per key class, fail-open events, store latency, and keys that hit the limit repeatedly.

• Central counting versus local buckets with async sync. Pick central, sharded counting for contractual limits, because it is exact and costs 0.5 ms in the same AZ. Flip to local buckets with periodic reconciliation when the extra round trip is not affordable or approximate enforcement is fine, accepting overshoot that grows with node count.
• Token bucket versus sliding window counter. Pick the token bucket because bursts are legitimate and state is two numbers. Flip to a sliding window counter when the contract is strictly "N in any rolling minute" and a short burst is a violation.
• Fail open versus fail closed. Pick fail open to a local bucket for general traffic, since a limiter outage should not be an API outage. Flip to fail closed for login and other abuse-sensitive routes, and say that you choose per route.
• Library in the gateway versus a separate limiter service. Pick the library to save a network hop in a 2 ms budget. Flip to a service when gateways are written in many languages or the policy changes often enough to need one deploy point, and pay the extra 0.5 ms.

Mistakes to avoid on this question:

• Doing "read the counter, compare, then write" in separate calls, which lets concurrent requests all pass.
• Incrementing and setting the expiry as two calls, so a crash leaves a key that never resets.
• Using each caller's clock to compute refills.
• Dividing the limit by the node count and calling it distributed, which punishes any user whose traffic lands unevenly.
• Never saying what happens when the store is down.
• Returning a bare 429 with no Retry-After, which invites the 27-fold retry storm.
• Putting a cross-region call on the request path.
• Limiting only by IP, which blocks a whole office behind one address and misses an attacker with many.