Design: a rate limiter

The full lesson, with a worked example: Design: a rate limiter.

Requirements

Functional

• Limit per key: each user, API key, phone number, device or IP address gets N requests per period, for example 5 login attempts a minute.
• Rules per action: viewing a menu is generous; sending an OTP, logging in or paying is strict.
• Refuse politely: status code 429 Too Many Requests with a Retry-After header.
• Change limits without a deploy, per plan or per customer.

Non-functional

• Fast: about 1 ms added per request.
• Shared: the limit is per key, not per server, so every gateway sees the same count.
• Never the cause of an outage: a broken limiter must fail in a planned way.
• Accurate enough: 102 through on a limit of 100 is fine; 1,000 is not.

Estimates

• Checks: say 1 crore daily users and 50,000 requests a second at the evening peak. One counter operation per rule per request, so about 50,000 to 1.5 lakh operations a second.
• Store capacity: one in-memory store does roughly a lakh simple operations a second, so two or three machines, each owning a share of the keys.
• Memory: about 100 bytes per counter (key plus two numbers). 1 crore users × 3 rules = 3 crore × 100 bytes ≈ 3 GB. Idle counters expire, so memory tracks active users.
• Sliding log cost: storing 100 timestamps per key is about 800 bytes instead of 16, which is gigabytes more at this scale.
• Latency budget: a same-zone round trip to the store is about 0.5 ms, which is why the store sits next to the gateways.

The verdict: size is easy. Speed, counting correctly under concurrency, and failure behaviour are the real work.

API

The limiter is invisible to well-behaved clients. What they see:

• Allowed: the normal response, plus RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset headers so careful clients slow down early.
• Refused: 429 with Retry-After: 6 (seconds) and a short reason. Never a 500 or a 200 with a hidden error.

Internal interface used by the gateway:

• check(key, rule, cost=1) → allowed true or false, tokens left, seconds until the next token.

Admin:

• PUT /v1/limits/:rule with capacity, refillPerSecond, keyBy (user, account, IP, device, global) and mode (enforce or shadow).
• GET /v1/limits/:rule/stats → checks, refusals and top refused keys over the last hour.

Data model

• Rule (in config, reloaded by gateways): rule_id, match (route and method), key_by, capacity, refill_per_second, on_store_failure (open, local-strict or closed), mode.
• Bucket state (in the counter store), key rl:login:user77: tokens, last_refill (store time). Expires after the bucket would be full again.
• Fixed or sliding window counter, key rl:search:user77:12:01: one integer, expires after two windows.
• Refusal events go to a log for dashboards and abuse review, never to the hot path's store.

High-level design

• Where it runs: inside or right after the API gateway, before any real work, so a refusal costs almost nothing. A second, finer check can run at the start of a service when the key needs data only the service has.
• Counters live in a fast shared key-value store in memory, split across machines by key, each with a standby copy.
• Rules live in config that gateways reload, so limits change in seconds.

One request through two rules:

1. 1

   ClientGateway

   POST /login for user 77

2. 2

   GatewayRules

   Which rules match? login per account, login per IP

3. 3

   GatewayCounter store

   One script: refill, then take a token from each bucket

4. 4

   Counter storeGateway

   Allowed, 4 left (about 0.5 ms)

5. 5

   GatewayApp server

   Forward, with RateLimit-Remaining 4

6. 6

   GatewayClient

   Next time, if empty: 429 and Retry-After 6

Deep dives

Algorithms

• Fixed window. One counter per clock minute, reset on the minute. Cheapest. Weakness at the edge: with 100 a minute, a script sends 100 at 12:00:59 and 100 at 12:01:00, so 200 arrive in about two seconds.
• Sliding window log. Store every request time; count those in the last 60 seconds. Exact, no edge problem, but about 50 times the memory of a counter.
• Sliding window counter. Keep this minute's and last minute's counts and weight the old one by overlap, giving a cheap rolling window. At 12:01:15 with 80 last minute and 30 so far: 80 × 45/60 + 30 = 90, under 100, so allow. Assumes last minute's requests were spread evenly; close enough.
• Token bucket. Capacity sets the burst, refill rate sets the steady pace. Example: 5 tokens, 1 back every 6 seconds, so a burst of 5 then 10 a minute. Two numbers per key. On each check: add tokens earned since last_refill up to capacity, then take one. The usual default for APIs.
• Leaky bucket. Requests join a queue that drains at a fixed rate. Smooths bursts instead of refusing them; suits pacing work such as sending SMS to a provider.

Atomic check-and-take

Ten gateways reading "1 left" and then writing 0 is a race condition: two requests pass on one token, and during a bot burst many more do. Make refill-check-take one atomic operation inside the store: a single increment-and-return command for windows, or a small script that runs as one unit for buckets. Use the store's clock, not each gateway's, so clock skew can't mint free tokens.

What to key by

• User or API key: fair and hard to dodge for logged-in traffic.
• Account or phone number: for logins and OTPs, so guesses from many devices still share one allowance.
• IP address: for logged-out traffic, set generously because many people share an address.
• Device: catches one phone cycling through many accounts.
• Global per action: a last safety net, such as "never more than 2,000 OTPs a second in total", with an alert as it nears.

A request must pass every rule that matches. Layering is what stops a bot farm of 5,000 phones that each stay under the per-IP limit.

Failure of the counter store

Decide per rule, in advance:

• Fail open with a local limit for reads and browsing: each gateway enforces a rough limit in its own memory.
• Local-strict or fail closed for OTP sends, logins and payments, where unlimited requests cost money or accounts.
• Alert loudly whenever any gateway falls back, because protection is reduced.

Hot keys and regions

• One huge customer can make 40% of calls, turning their bucket into a hot key on one store machine. Split it into N sub-buckets on different machines, each with capacity ÷ N, or lease that customer's tokens to gateways in batches.
• Two regions with separate stores give a user the full limit in each. For most rules, accept it or halve each region's limit. For security rules, route each account's checks to one home region.

Trade-offs

• Exact vs fast. One shared store is exact but costs a hop. Local allowances topped up in batches save the hop and allow a small, bounded overshoot.
• Fail open vs fail closed. Availability vs protection; choose per rule, not once for the whole app.
• Refuse vs queue. 429 keeps servers healthy; queuing is kinder but makes people wait and can hide overload.
• Burst size. Bigger buckets feel friendlier to real people and give attackers more per burst.
• Token bucket vs sliding window counter. Bucket for bursty traffic with a steady pace; window counter for a clean "no more than N in any minute" rule. Both need two numbers per key.

Interview talking points

• Clarify who is limited and for which actions before picking an algorithm.
• Estimate checks a second and memory, and show the store is small.
• Put the limiter at the gateway, before expensive work.
• Name the fixed-window edge problem, then choose token bucket or sliding window counter and say why.
• Make check-and-take atomic in the shared store.
• Layer keys: account, device, IP and a global cap.
• Return 429 with Retry-After, and ask clients for exponential backoff with jitter.
• Choose failure behaviour per rule.

For experienced engineers

GCRA stores one timestamp per key (the theoretical arrival time) and behaves like a token bucket with less state. Roll out new or tighter limits in shadow mode, logging would-be refusals against real traffic before enforcing.

Follow-up questions

Token bucket or sliding window counter? Token bucket when short bursts are fine but the steady rate must be capped, which suits most APIs. Sliding window counter when you want "no more than N in any rolling minute".

How do you avoid a network hop on every request? Give each gateway a small batch of tokens to spend locally and top it up from the shared store. You trade a little accuracy for speed.

Refused clients retry instantly and make it worse. What now? That is a retry storm. Always send Retry-After, publish backoff-with-jitter guidance, and give keys that keep hammering after a 429 a longer block.

How do you pick the numbers? Measure first. Run the rule in shadow mode, look at what genuine heavy users do, set the limit comfortably above that, then enforce and watch the 429 rate.

The limit check sits after the database query. Problem? Yes. Every refused request has already cost a full query, so a flood still sinks the database. Check at the gateway first, and use a finer check at the very start of the service if needed.

How do you stop OTP-bill fraud from thousands of addresses? Limit by what the attacker can't multiply cheaply: the destination phone number and the account. Add a global OTP cap with an alert, and ask for a CAPTCHA when patterns look suspicious.