Rate limiter: build the design step by step

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: One counter, twelve gateways

"The partner's limit was 100 a minute. Their dashboard showed 1,200 getting through. Nothing was broken: we had twelve counters."

Kabir, reviewing Meera's first draft

Version one: count in memory, and watch it break

Start with the simplest design. Each gateway keeps a counter in its own memory: one counter per key per minute, add one for each request, reject past 100.

SwiftKart has 12 gateways behind a load balancer that spreads requests in turn. A partner sends 1,200 calls in a minute. Each gateway sees about 100 of them, finds its own counter at 100 and allows them all. The partner's real limit is 100 x 12 = 1,200. Scale to 24 gateways and it becomes 2,400, so the limit changes every time you scale. The counters must live in one shared place.

Version two: a shared store, and the race

Meera's next idea was practical: "We already run a SQL database. Put the counters in it." Check the numbers. The orders database is comfortable at about 2,000 simple queries a second. The limiter needs 100,000 a second. That is 100,000 / 2,000 = 50 times its comfortable load, and a counter that stalls the orders database would be an odd way to protect it.

So use an in-memory store, a database that keeps its data in RAM and answers in a fraction of a millisecond, such as Redis. Now the next trap. Each gateway does three steps: read the tokens, decide, write the new value. Look at a key with 1 token left:

  1. Gateway A reads: 1 token.
  2. Gateway B reads: 1 token.
  3. A allows the call and writes 0.
  4. B allows the call and writes 0.

Two calls passed on one token. This is a race condition: two steps from different servers interleave and one overwrites the other. At 100,000 checks a second, it happens all the time.

The fix is to make read, decide and write atomic, one step that cannot be split. The store runs a small script that does all three. Two gateways calling at once are queued by the store, one after the other, and the second sees 0. Here is the script's logic for a token bucket with a rate of 10 a second and a burst of 20:

tokens = min(burst, tokens + rate x seconds since last refill). If tokens is at least 1, subtract 1 and allow. Otherwise reject.

Worked example: the key has 4 tokens and was last refilled 0.5 seconds ago. Refill adds 10 x 0.5 = 5, so 9. Spend 1, leaving 8. The call is allowed and remaining is 8.

Version three: shards, and where the limiter sits

One store node cannot take 100,000 scripts a second (lesson 1: plan 25,000 per node). So split the keys across 4 shards by hashing the key. The same key always hashes to the same shard. That matters: the atomic script is only atomic on one node, and one key lives on exactly one. Each shard has a replica that takes over if the primary dies. Replication is asynchronous, meaning the replica copies a moment later, so a failover can lose a few recent decrements. For rate limiting that is acceptable: a client gets a few extra calls and nothing is corrupted.

Next, where does the check run? Weigh four places.

  • In the client app. Politeness only. A bad caller ignores it.
  • Inside each service. Every team rewrites it, and no single place shows the rules.
  • A separate limiter service. One clean place, but every request pays an extra network hop and you must keep another service alive.
  • A library inside the gateway. The gateway already sees every request, so there is no extra hop. The cost: rule changes must reach all 12 gateways.

Choose the library in the gateway and say the trade-off. It keeps the check inside the 1 ms budget.

Version four: the rules, then one request end to end

Rules are small and change rarely: a few hundred rows in PostgreSQL, behind a rules service. Each gateway polls the service every 30 seconds and keeps a local copy, so no check ever reads the rules database. A new rule reaches all gateways within about 30 seconds, with no deploy. Meera asked whether the database should be read per request. No: that adds a trip to every call and ties the API's uptime to a table that almost never changes.

Follow one request:

sequenceDiagram
  participant C as Client
  participant G as Gateway
  participant S as Counter store
  participant B as Backend
  C->>G: POST /orders (ak_42)
  G->>G: match local rule
  G->>S: atomic script on rl:orders.write:ak_42
  S-->>G: allowed, remaining 8
  G->>B: forward request
  B-->>G: 201
  G-->>C: 201 + RateLimit-Remaining 8

The gateway matches the request to the rule "orders.write: 10 a second, burst 20, key = API key". The shard that owns that key runs the script. If the answer is allowed, the gateway forwards the call and adds the remaining-quota header. If not, it answers 429 with Retry-After and never touches the backend. That last part is the point: a rejection costs one script, not a database query.

💡 Tip: Retry-After is in whole seconds, so round the store's retry_after_ms up. A client told "0" will retry at once.

Now draw it on the board.

📌 Summary: Local counters multiply the limit by the number of gateways. Use a sharded in-memory store with one atomic script per check. Run the limiter inside the gateway and cache rules locally.

What Meera learns next

The design runs, but we only said "token bucket" without defending it. Next lesson compares the algorithms, tackles hot keys, and answers the hardest question: what happens when the counter store goes down?

Check your understanding

  1. SwiftKart keeps one counter per key in each gateway's memory. A partner limit is 100 a minute, with 12 gateways and requests spread evenly. The fleet grows to 24 gateways. What is the partner's effective limit?
  2. Two gateways read a key at the same moment and both see 1 token left. Each then writes back 0. What happened, and what prevents it?
  3. A teammate proposes keeping counters in the orders SQL database, which is comfortable at about 2,000 simple queries a second. The limiter needs 100,000 checks a second. What is the problem?
  4. Where should a gateway find a route's limit when a request arrives?