Design a Rate Limiter: Where the Counter Lives Decides Everything (2026)

The interviewer writes one line on the board: “Design a rate limiter.” It sounds like the easy question. A counter, a limit, a 429. The candidate draws a box, writes “Redis” next to it, and says “token bucket”. Ten minutes later the interviewer asks: “What happens when you have twenty gateways?” and then: “What happens when Redis is down?”

Those two questions are the whole problem. A rate limiter is easy on one machine and a distributed-systems question everywhere else. This lesson walks it in 45 minutes; it is the box the URL shortener put in front of link creation.

Step 1: Pin Down the Problem#

Ask what is being limited, who it is limited by, and what happens to a request that goes over. Write the answers down.

Functional requirements:

1. Limit how many requests a client can make in a period, per rule (for example, link creation).
2. Reject requests over the limit with 429 Too Many Requests and tell the client when to retry.
3. Let an operator change limits without a deploy.

Out of scope (say these out loud):

• Billing quotas over months, bot detection, and network-level attack protection, which belong to other layers.

Ask first, because each answer changes the design: who is limited (user, API key, IP)? Is the limit per route, and do rules change at runtime? Must it be exact, or is a little overshoot fine? One region or many?

Non-functional requirements, each with a number. These are assumptions you announce:

• Fast: assume the check adds about 1 to 2 ms, since it runs on every request.
• Available: if the limiter breaks, the API keeps serving.
• Accurate enough: a few percent of error is fine; exactness costs latency.
• Scale: assume the limiter checks every request, redirects included, so about 12,000 checks a second at peak (the URL shortener’s peak) and 1 million client keys.

Underline the second line: the limiter protects the service, so it must never take it down.

Step 2: Entities and API#

The limiter is internal. The gateway calls it, and clients only ever see the response.

Rule    route, key, limit, period
check(key, rule)
  -> allowed, remaining, retry_in
 
Over the limit, the client sees:
  429 Too Many Requests
  Retry-After: <seconds>

One entity and one call. Retry-After matters because a client told nothing retries at once. RFC 6585 (April 2012) defines 429 and says it may carry Retry-After, but not how to identify the user or count requests; that is your design. RFC 9110 makes the seconds form a non-negative whole number, so round up. Envoy’s local filter, with an option that is off by default, sends the seconds until the next token, clamped to at least one.

Many APIs also say how much allowance is left. GitHub’s REST API sends these, per its rate-limit docs:

x-ratelimit-limit: 5000
x-ratelimit-remaining: 4999
x-ratelimit-reset: <UTC epoch s>

Standard RateLimit and RateLimit-Policy fields are still an IETF Internet-Draft as of October 2026 (draft 11, 23 May 2026), not an RFC. Name the idea; say it is not final.

The state is a key-value record, read and written once per request, with no range queries, so an in-memory store fits and a SQL database (a disk write per request) does not:

key   rl:{client}:route
value tokens, last_refill_ms
TTL   capacity / rate seconds

Step 3: A Design That Works#

First, where does the check run? Each place sees a different slice of traffic:

Pick the gateway: every route passes through it before any real work. A client-side limiter is a courtesy, never the control. Start with one gateway: it finds the client’s bucket in memory, spends a token, and forwards the request or answers 429.

Correct, fast, simple, and where many candidates stop.

Each gateway counts alone, so a limit of 10 a second becomes up to 200 across twenty. Dividing the limit by twenty does not fix it: a client that hits one gateway is held to a twentieth of its allowance.

Pinning a client to one gateway (sticky sessions) breaks on restarts and rebalancing. The counters must be shared.

Step 4: Estimate What Matters#

Assumptions: 12,000 checks/s peak,
1 million client keys, about
100 bytes per client
(key, tokens, last refill)
 
Checks: 12,000 /s peak
Memory: 1M x 100 B ≈ 100 MB
Latency: +1 to 2 ms per check
  (one round trip in-region)
Network: 12,000 x 200 B
  ≈ 2.4 MB/s

Each line decides something:

• 100 MB of counters fits in one machine’s memory, so size is not the problem.
• At an assumed 12,000 checks a second, one in-memory store is probably enough (check your own limits), but it pushes you to add a local bucket in front.
• 2.4 MB/s of check traffic is nothing, so bandwidth is not the limit; round trips are.
• Assume 1 to 2 ms per check, and treat it as the real cost. Pool connections (no handshake per check) and keep work local.

Cross-check: NGINX’s limit_req stores 128 bytes per key on 64-bit platforms, about 8 thousand per megabyte, so a million keys is 125 MB, the same order as our 100 MB. When its zone is full it drops the least recently used state and that client starts over, so size for the keys you expect.

Step 5: Deep Dives#

Four questions decide this design: the algorithm, where the counters live, what happens when they fail, and who is limited. Senior answers pull ahead on the production questions after them, which the follow-ups lesson collects.

Which Algorithm?#

Fixing the Window Boundary#

A log of 1,000 requests an hour is up to 1,000 timestamps per client (assumption). A sliding counter estimates previous × overlap + current, and Cloudflare’s 2017 write-up gives 42 × (45/60) + 18 = 49.5 and reports 0.003% of 400 million requests wrongly allowed or limited: a measurement on their 2017 traffic, not a general error bound.

A Token Bucket, Worked#

capacity 10, refill 5 per second
idle 2 s: min(10, 0 + 5 x 2)
  = 10 tokens
12 requests at once:
  10 allowed, 2 get 429
next token in 0.2 s, so
  Retry-After rounds up to 1

The formula is tokens = min(capacity, tokens + rate × seconds). Elapsed time is all you need; no timer runs per client.

Where Do the Counters Live?#

bucket has 1 token
A reads 1     B reads 1
A writes 0    B writes 0
-> both allowed, 1 token spent

When One Store Is Not Enough#

What Happens When the Limiter Is Down?#

This is the question that separates senior answers. A limiter that fails can either let everything through or stop everything.

Real gateways make this a setting. In Envoy’s global rate limit filter, failure_mode_deny: true returns a 500 when the limit service fails; the API reference shows a plain boolean, so unset means fail open, with a 20 ms default timeout. Stripe’s 2017 write-up also argued for failing open.

Who Is Limited, and What Do They See?#

When several rules match (per user, per route, per IP), check them all and let the most restrictive decide. On Redis Cluster one script can touch several keys only if they share a slot; a hash tag such as {user42} in each key name keeps one user’s buckets together.

A hot keyhot key: one key that gets far more traffic than the rest, overloading the server that holds it is a client that sends far more than the rest:

• An empty local bucket rejects without asking the store, so the shard is spared.
• Abusive sources go on a short-lived blocklist at the edge, before any counter is touched.
• A legitimate heavy user gets a bigger plan, not an exception.

Clients have a part too. GitHub’s guidance: wait for retry-after, else until x-ratelimit-reset, else at least a minute, then back off exponentially. Add jitter so clients do not retry in the same second.

The Final Design in One Picture#

One request: the gateway spends a local token, asks the shard that owns the key to run the atomic check, then forwards the request or answers 429 with Retry-After. If the shard is unreachable it uses the local bucket or rejects, by route.

Gateways load limits from a rules store, by polling (simple, slower) or push (instant, one more system), and keep the last good rules in memory.

What Comes After the Core Design#

The follow-up questions (what breaks, what is abused, what it costs) go deeper than the core answer. They live in Design a rate limiter: failure modes, security and follow-ups.

What Each Level Should Show#

Red Flags and Green Flags#

More red flags: limiting by IP only, a fixed window with no word on its boundary, no Retry-After, and failing closed everywhere. More green flags: every number comes with what it drives, and every component gets “what if it dies?”

Try It: Limit Login Attempts#

Key: account id, plus IP
Bucket: capacity 5
Refill: 1 per 3 min
  (15 min / 5 attempts)
Burst: 5 tries at once
Down: fail closed on login
Reply: 429 + Retry-After

Check Yourself#

In One Picture#

Requirements
  limit per key, 429 + retry,
  rules without a deploy
Scale
  12,000 checks/s · 100 MB
Algorithm
  token bucket, two numbers
Counters
  shared, atomic, sharded
Local bucket
  absorbs bursts first
Failure
  open or local; closed for
  login and creation
Operations
  shadow new rules first (see
  the follow-ups lesson)

Conclusion#

A rate limiter is a small data structure wrapped in a hard question: where do the counters live, and what happens when they cannot be reached? Share them, check atomically, shard by client, keep a local bucket in front, and choose the failure mode per route. That is the 60-second answer.

Which failure mode would you defend first in the room? Tell us in the comments.