Rate limiter: ask, size and expose it

Part of the free System Design course on LogicWiz, in the chapter: Design a rate limiter. The interactive whiteboard exercises and simulations run in the app.

Week 11: Ask before you draw a counter

"We built the counter first. Ten minutes later the interviewer told us the limit was per API key, and we had counted IP addresses."

A candidate, in a mock interview Meera watched

What the interviewer is really asking

Kabir plays the interviewer. His first sentence is the whole prompt: "Design a rate limiter for an API gateway, shared by many gateway servers, handling about 100,000 requests a second."

A rate limiter is a gate that counts the calls each caller makes and turns away the ones over their allowance. SwiftKart's gateway serves the customer app, partner shops and an occasional scraper (a script that copies your data). The gateway is the front-door server that checks and forwards every call. At the festival peak SwiftKart runs 12 of them, and together they see about 100,000 requests a second.

Meera's first thought: "It is a counter and an if. Why does this get a whole chapter?" The counter is the easy part. Three things are hard: counting one caller across 12 servers, staying fast at 100,000 checks a second, and staying alive when the limiter itself breaks. You met the token bucket idea in the entry-layer chapter. Now you design the whole system around it.

Ask before you draw

Kabir's rule is to spend the first five minutes on questions. A candidate who draws first often builds the wrong thing. Ask these, and say why you ask.

  • Who is limited, and by what key? The key is the thing you count by.
  • Where does the check run? At the gateway, inside each service, or in the app?
  • How exact must it be? Never one request over, or within a few percent?
  • What does a limited caller see? A clear answer, or a silent drop?
  • What if the limiter breaks? Should the API keep working or stop?
  • Do rules differ, and can they change without a deploy?

Take the first question, because it is where the candidate in the cold open went wrong. An API key is a secret string that identifies one app or partner. Count by it for partners: each partner gets its own allowance, whichever servers it calls from. A user id exists after login and is the fairest key for the customer app. An IP address is the only key you have before login, for example on the login page itself.

The IP key has a trap. Meera said: "IP is the simplest, so I will use it everywhere." But an office of 300 people often shares one public IP address, and so do many customers of one mobile carrier. Set 100 requests a minute per IP, and that office gets 100 / 300 = 0.33 requests per person per minute, about one every three minutes. One busy person blocks the other 299. Attackers also change IP addresses easily.

So the answer is a mix. Use the API key for partners, the user id after login, and the IP only where nothing else exists. Often you use two keys together: the login route is limited by IP and also by the username being tried.

Requirements with numbers

Say these out loud as Kabir answers your questions.

Functional (what it does):

  • Limit by API key, user id or IP address. Rules differ per route and plan, for example 100 a minute on login and 1,000 a minute on reads.
  • Allow short bursts above the steady rate, because one page load fires 10 calls at once.
  • Reject calls over the limit with HTTP 429 Too Many Requests and a Retry-After header.
  • Change rules without redeploying the gateways.

Non-functional (how well it does it):

  • Throughput: about 100,000 checks a second, one per request.
  • Latency: the check adds under 1 ms at p50 (the median) and under 5 ms at p99 (99 out of 100 checks are faster).
  • Accuracy: a client may exceed its limit by a few percent, across all gateways together.
  • Availability: the limiter must never be the reason the API is down.

Out of scope: network-layer DDoS (the CDN or a scrubbing service filters that), billing, and bot detection beyond simple limits.

The estimate, step by step

Checks: 1 per request = 100,000 per second
Store operations: 1 atomic script per check = 100,000 per second
Shards: 100,000 / 25,000 per node = 4 shards; 1 replica each = 8 nodes
Memory: 10M active keys x 100 bytes = 1,000 MB = about 1 GB
Network: 100,000 checks x 200 bytes = 20 MB per second
Latency: same-zone round trip about 0.5 ms, inside the 1 ms budget

Read it line by line. Every request needs one check, so the limiter sees as many checks as the gateway sees requests. Each check is one atomic script, a small program the store runs as one step that nothing can interrupt. One script means one network trip.

A shard is one slice of the data, held by one node. Plan for about 25,000 operations a second per node, which leaves headroom. So 100,000 / 25,000 = 4 shards. Each shard gets a replica (a copy that takes over if the node dies), so 8 nodes.

A key is one caller under one rule. With 2M daily users, anonymous IP addresses and a few rules each, assume 10 million active keys.

Now the wrong belief. A candidate says: "It is only a counter, so one Redis box is enough." Memory does not decide this. A key holds about 100 bytes, so 10 million active keys fit in roughly 1 GB. Operations per second decide it, and 100,000 is four times what one node should take.

The last line rules out a store in another region. A same-zone round trip is about 0.5 ms. A cross-region trip costs tens of milliseconds, and the whole check must stay under 1 ms at p50.

The API, the data, and what a caller sees

The gateway talks to the limiter through a small contract. In practice the limiter often runs as a library inside the gateway, so the call is a function call and not a network hop. The shape is the same.

POST /v1/limits/check {key: "apikey:ak_42", rule: "orders.write", cost: 1}
  -> 200 {allowed, remaining, reset_ms, retry_after_ms}
GET /v1/rules?version= -> 200 {version, rules[]}   (gateways poll every 30 s)
PUT /v1/rules/{id} {match, algorithm, rate, burst, fail_mode} -> 200

The cost field lets a heavy call, such as a bulk export, spend 5 tokens instead of 1. Now the data. Rules are few and change rarely, so they live in SQL. Counters change 100,000 times a second, so they live in an in-memory store.

rules(id PK, route_pattern, method, plan, key_type, algorithm, rate_per_s, burst, fail_mode, version)
counter: rl:{rule_id}:{key} -> {tokens, last_refill_ms}; expires once fully refilled
overrides(key PK, rule_id, rate_per_s, burst, expires_at)

What does the caller see when it is over the limit?

HTTP/1.1 429 Too Many Requests
Retry-After: 3
RateLimit-Remaining: 0

A 429 means "slow down". A 5xx means "we are broken", and many clients retry those automatically, which adds load. Retry-After says how many seconds to wait. Send the remaining-quota header on every response, so polite clients slow down before they reach the limit.

Write your opening for Kabir below.

📌 Summary: Ask first: which key, how exact, what the caller sees, what happens when it fails. Size it from 100,000 checks a second: four shards, eight nodes. Memory is tiny; operations per second decide.

What Meera learns next

The questions are asked and the numbers are on the board. Now to draw it, simplest version first: where the counter lives, why twelve servers break a local counter, and how the race is closed.

Check your understanding

  1. A no-login SwiftKart route allows 100 requests a minute per IP address. A coworking space with 300 people shares one public IP. What happens?
  2. A store node handles about 25,000 operations a second. The limiter makes one operation per check at 100,000 checks a second. How many shards, and how many nodes with one replica each?
  3. The estimate says 10 million active keys at about 100 bytes each. What does that tell you about sizing the counter store?
  4. A caller goes over its limit. Which answer should the gateway send?