Design a distributed rate limiter

A public API must stop any one client from sending more than its share: to protect the service, keep costs fair and blunt abuse. On one server, a counter in memory does it. With a hundred API servers behind a load balancer, the counters must be shared, fast, correct under concurrency, and must never become the thing that takes the API down. This is an infrastructure design: expect depth on algorithms, atomicity and failure modes. It follows the interview framework phase by phase.

1. The prompt

"Design a rate limiter for our public API. Each API key may make at most N requests per period; different endpoints and plans have different limits."

There's no product UI here: the "users" are other services. Interviewers want to see an algorithm chosen for a reason, counters that stay correct when 100 servers update them at once, a check that adds almost no latency, and a clear answer to "what happens when the limiter itself breaks?".

2. Frame the problem

3. What it must do

1. The gateway can allow or reject each request against the rules that match it (per client key, per endpoint and plan), allowing short bursts.
2. A rejected client gets a clear answer: 429 Too Many Requests with Retry-After and the remaining quota.
3. Operators can change rules (limits per plan or endpoint) without a deploy.

Not now:

• Monthly quotas and billing: a metering system with different accuracy needs.
• Network-layer DDoS protection: the CDN or WAF in front does that.
• Per-tenant concurrency limits: a related tool; mention it in follow-ups.

4. How well it must do it

5. Numbers that change the design

6. The nouns

• Rule: what to match, which algorithm, the numbers, and the failure mode.
• Client key: the API key, user or IP being limited.
• Bucket: the counter state per (rule, client).
• Decision: allow or reject, with remaining quota and reset time.

rules     rule_id, match (endpoint, plan), algorithm (token_bucket | sliding_window), rate, burst, window,
          key_by (api_key | user | ip), fail_mode (open | closed), version
redis     rl:{rule_id}:{client_key} → {tokens, last_refill_ms}     TTL ≈ time to refill completely

7. The contract

The limiter has three faces: an in-process call the gateway makes, the headers clients see, and an admin API for rules.

// inside the gateway (a library call, not a network hop)
allow(client_key, request) → {allowed, remaining, reset_after_ms, rule_id}

// what an API client sees when limited
HTTP/1.1 429 Too Many Requests
Retry-After: 12
RateLimit-Limit: 100
RateLimit-Remaining: 0

// admin API (operators)
PUT /v1/rules/{rule_id}   {match, algorithm, rate, burst, key_by, fail_mode}   If-Match: version

Retry-After is standard HTTP. The RateLimit-* header fields are being standardised by the IETF (still a draft in October 2026); many APIs use X-RateLimit-* names.

8. First working version

A limiter library in every gateway, a shared Redis for counters, and a config store for rules. Build each request.

8.1 Checking a request

The gateway finds the matching rule in its cached copy, reads the client's counter from Redis, and if it's under the limit, writes it back incremented and lets the request through.

8.2 Rejecting a request

When the count is at the limit, the gateway answers 429 at once with Retry-After. The services behind it never see the request, which is the point.

8.3 Changing a rule

An operator updates a rule through the admin API. It's stored in the config store with a new version; each gateway polls for changes every 30 seconds (or subscribes to change notifications) and swaps its cached copy.

9. Make it hold up

9.1 Choosing the algorithm accurate enough · cheap

The requirements allow bursts and a few percent of error, so token bucket is the default, with a sliding window counter for rules that must be strict over a window ("100 per minute, no bursts"). Cloudflare has described using the sliding window counter at very large scale.

9.2 Counting correctly with 100 servers accurate enough

-- token bucket, run atomically by Redis (KEYS[1] = bucket, ARGV = rate/s, burst, now_ms)
local b = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens, ts = tonumber(b[1]) or tonumber(ARGV[2]), tonumber(b[2]) or tonumber(ARGV[3])
tokens = math.min(tonumber(ARGV[2]), tokens + (tonumber(ARGV[3]) - ts) / 1000 * tonumber(ARGV[1]))
local ok = tokens >= 1
if ok then tokens = tokens - 1 end
redis.call("HSET", KEYS[1], "tokens", tokens, "ts", ARGV[3])
redis.call("PEXPIRE", KEYS[1], math.ceil(tonumber(ARGV[2]) / tonumber(ARGV[1]) * 1000))
return ok and 1 or 0

Pass the time in from one clock (or read Redis's own TIME), so gateways with slightly different clocks can't refill a bucket twice.

9.3 Keeping the overhead tiny cheap · scale

9.4 When the limiter itself fails never the outage

If Redis is slow or down, every API request waits on it. Give the call a tight timeout (a few milliseconds) and a circuit breaker (Module 24), and decide the fallback per rule:

• Fail open (allow, with a generous local limit per gateway) keeps the API up for paying customers. The right default for most endpoints.
• Fail closed (reject) protects a fragile backend or a security boundary: login attempts, password resets, expensive exports.

Alert when the breaker opens: running without the limiter is a risk that someone should know about.

9.5 Hot keys and abuse scale · cheap

• One abusive key sending 100,000 requests a second is a hot key on one Redis shard. Cache its "blocked until" decision locally on every gateway for a few seconds, so its requests are rejected without touching Redis.
• Limit on several dimensions: per API key, per user, per IP (for unauthenticated traffic), and globally per endpoint to protect the backend.
• Very large floods belong at the edge: CDN and WAF rate limits drop them before they reach your gateways.

9.6 Several regions, and pushing rules accurate enough · live rules

A global limit across regions needs either a cross-region round trip per request (far too slow) or an approximation:

• Split the limit: give each region a share. Simple, but slightly unfair if a client's traffic shifts between regions.
• Sync counters: keep local counters and sync them across regions every second. Eventually consistent, with a slight overshoot.

Most APIs accept per-region limits. Rules are versioned in the config store and pushed to gateways with a notification, plus a periodic poll as a backstop; gateways keep the last good copy if the store is down.

9.7 The whole design after the deep dives

A normal request, an abusive client, and a Redis outage, through the final design.

10. Interviewer follow-ups

11. When things break

12. Wrap-up and the clock

Trade-offs we made:

• Token bucket by default (bursts allowed, two numbers per key).
• Atomic scripts in a Redis cluster (one round trip, correct).
• Two-tier local counting for hot keys (a few percent of error for far less latency).
• Fail open by default.
• Per-region limits.

What we'd watch:

• Limiter latency p99.
• Redis errors and breaker state.
• 429s per rule and per client.
• The hottest shard's load.

At 10×:

• More shards.
• More keys on local buckets.
• Edge limits for floods.

Common mistakes:

• Per-server counters behind a load balancer.
• Read-then-write.
• A separate limiter service on every request.
• No plan for Redis being down.
• Ignoring hot keys.
• Promising exact global limits across regions.

13. Try it, check yourself, read more

Limit: 10 requests per 10 seconds (token bucket: burst 10, refill 1 per second). Pick a traffic pattern and compare the algorithms. Green = allowed, faded red = rejected.