Pattern card: rate limiting

The full lessons, with worked examples: Design: a rate limiter, OTP login and Tatkal booking. The full problem write-up: rate limiter.

What it is

Rate limiting caps how often one caller may do one thing: 5 login tries a minute, 3 OTPs an hour, 100 searches a minute. Beyond the cap the request is refused cheaply, before any real work.

• Everyday version: the water tank on your roof. Tank size is how big a burst you can have; the inlet pipe is your steady rate. One tank per flat, and every tap reads the same tank.
• What it protects: accounts from guessers, servers from floods, the company from bills (every SMS costs money), and other customers from one heavy user.
• What it is not: load shedding drops work when the whole system is overloaded, whoever sent it. A rate limiter judges each caller against their own allowance, even when the servers are idle.

When to use it

Use it when:

• An action costs money or risk: OTPs, logins, password resets, payments, calls to a paid AI or maps API.
• A public API serves many customers: one customer must not use up everyone's share. Limits per API key become the product's quota.
• A known rush attracts scripts: Tatkal at 10 AM, a flash sale at noon.
• Clients may loop: a buggy app retrying in a tight loop looks just like an attack.

Don't rely on it alone when:

• The flood is spread thin. 5,000 phones sending a few requests each pass every per-address limit. Add limits on what attackers can't multiply, and a total cap.
• Real demand is simply bigger than capacity. Limiting fair users just turns them away; use a waiting room, a queue or more servers.
• The work is already done. A limit checked after the database query saves nothing.

How it works

1. Sit at the front door. The limiter lives in or just after the API gateway, so a refusal costs about a millisecond and no database work.
2. Build the key. Who and what: "user 77, login", "phone 98xxxxxx21, OTP", "device abc, search". A request must pass every key that applies.
3. Check and take in one step. The counts live in a shared in-memory store so all gateway servers agree. The check and the decrement are one atomic operation (a single increment command or a small script run inside the store). Read-then-write from two servers is a race condition: both see "1 left" and both allow.
4. Refuse clearly. Reply with status code 429 Too Many Requests and a Retry-After header. Many APIs also send the limit and how many requests remain, so good clients slow down early.
5. Load rules from config. Limits per action live in a small config the gateways reload, so a change needs no deploy.

One request through a token bucket:

1. 1

   PhoneGateway

   Check seats (user 31877)

2. 2

   GatewayCounter store

   Add earned tokens, take 1, in one step

3. 3

   Counter storeGateway

   4 tokens left

4. 4

   GatewayApp servers

   Allowed

5. 5

   GatewayPhone

   Bucket empty later: 429, Retry-After 6

Variants

The counting methods:

• Fixed window. How: one counter per clock minute, reset at :00. Good for: cheap daily caps. Cost: the edge problem; with a limit of 100, a script sends 100 at 12:00:59 and 100 at 12:01:00, so 200 in two seconds. See fixed window.
• Sliding window log. How: store every request's time, count those in the last 60 seconds. Good for: exact limits on small, sensitive actions. Cost: memory; 100 timestamps is about 800 bytes per key against about 16.
• Sliding window counter. How: keep this minute's and last minute's counts and weight the old one. At 12:01:15, with 80 last minute and 30 so far: 80 × 45/60 + 30 = 90, under 100, allow. Good for: a clean "no more than N in any minute" rolling window with two numbers. Cost: assumes last minute's requests were spread evenly; close enough.
• Token bucket. How: a bucket of, say, 5 tokens refilled at 1 every 6 seconds; each request takes one, after first adding tokens earned since the last refill. Store: tokens left and last refill time. Good for: most APIs and user actions; allows a human burst, then a steady rate. Cost: two tuning knobs to get right. See token bucket.
• Leaky bucket. How: requests join a queue that drains at a fixed rate. Good for: pacing outgoing work, such as sending SMS to a provider. Cost: callers wait instead of being refused; the queue needs a cap. See leaky bucket.

Where the counts live:

• One shared store. Exact, one network hop per check, and a dependency that can fail.
• Local counts per server. No hop, but N servers give N times the limit unless each takes a share.
• Local allowance topped up from the store. Each gateway takes tokens in small batches and hands them out locally. Fast, with a little overshoot.
• Per region. Two regions each with full limits give a user double. Halve the limits per region, or send security limits to one home region.

Numbers to know

• Check cost: about 0.5–1 ms against a nearby in-memory store.
• Store capacity: roughly 1 lakh simple operations a second per machine. At 50,000 requests a second, two or three machines with users split between them give room.
• Memory sum: about 100 bytes per counter. 1 crore users × 3 rules × 100 bytes = about 3 GB. Idle keys expire, so memory tracks active users.
• Tatkal sum: 4,000 scripts firing 200 searches each in one second is 8 lakh requests. With a bucket of 5 per user, about 20,000 get through; the rest get 429 in under a millisecond.
• OTP guessing: 10 lakh possible 6-digit codes. 5 tries per code is a 1 in 2 lakh chance. At 3 codes an hour, that's 360 guesses a day, about 1 in 2,800. Capping wrong guesses at 10 a day per number brings it to about 1 in 1 lakh a day.
• SMS abuse sum: 5,000 phones sending 25,000 OTP requests a minute at say 20 paise each is about ₹5,000 a minute.
• Typical limits: 3–5 wrong OTP tries per code; a 30-second Resend wait; a few OTPs per number per hour; logins a handful a minute per account.

Pitfalls

• Checking after the expensive work. Bots still see 429s, but each one already cost a database query. Check at the gateway; do a finer check at the very start of the service if needed.
• One limit for every action. 100 a minute is fine for menus and ruinous for OTPs. Set limits by cost and risk; strict ones get a daily cap too.
• Non-atomic counting. Read, decide, write lets a burst through many times the limit exactly when an attack arrives.
• Limiting only by IP. Many real people share one address, and attackers rotate theirs. Use IP limits generously, and limit by account, phone number and device.
• No plan for a dead store. Decide per action in advance. Fail open with a rough local limit for browsing; fail closed or strict local limits for OTPs and logins. Alert when the limiter falls back.
• Retries that make it worse. Clients that retry a 429 at once cause a retry storm. Always send Retry-After; ask clients for exponential backoff with jitter; block keys that keep hammering.
• One giant customer on one counter. A hot key overloads its store machine. Split it into several sub-buckets, each with a share of the limit, or lease tokens to gateways in batches.
• Guessed numbers. Run new limits in watch-only mode first, logging who would have been refused, then set them comfortably above genuine heavy users.
• Hidden refusals. A 500 or a 200 with an error inside confuses monitoring and clients. Use 429 and chart it separately.

In an interview

Rate limiting is both a full question ("design a rate limiter") and a box you add to logins, OTPs, public APIs and booking sites.

• Requirements first: per-key limits, different rules per action, about a millisecond, shared across servers, safe when broken.
• Size it: checks a second and memory, showing the store is small.
• Place it: at the gateway, before real work.
• Pick an algorithm and say why: token bucket for bursts plus a steady rate; sliding window counter for a strict per-minute rule. Mention the fixed-window edge.
• Make it correct: shared counters, atomic check-and-take.
• Layer the keys: user, device, phone number, IP, and a global safety cap.
• Decide failure: fail open or closed, per action.

Follow-up: "Token bucket or sliding window counter?" Token bucket when short bursts are fine and you want a steady rate; sliding window counter when the rule is "never more than N in any minute". Both need two numbers per key.

Follow-up: "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 store, accepting slight overshoot.

Follow-up: "Stop someone guessing OTPs." A few tries per code, a few codes per number per hour, a daily cap on wrong guesses per number, and a lock after that. Limit by phone number and device, not just IP.

Follow-up: "The counter store is down." Browsing fails open with a local limit; OTPs and logins use a strict local limit or fail closed. Run the store with a standby.

For experienced engineers

A GCRA formulation stores one timestamp per key and is equivalent to a token bucket with less state. Use the store's clock, not each gateway's, to avoid skew, and give idle keys a TTL. Roll out tightened limits in shadow mode and expose RateLimit headers so well-behaved clients can pace themselves.