Rate limiter: deep dives, failures and follow-ups

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: When the limiter is the problem

"The counter store stalled for nine seconds. The limiter waited for it on every request. For nine seconds, the whole API was down."

Kabir, on the incident that taught SwiftKart to add a timeout

Deep dive 1: which algorithm?

Kabir asks: "You said token bucket. Why not something simpler?" Compare four, with a limit of 100 a minute.

Weak: fixed window. Count per calendar minute and reset on the minute. One INCR (add one to a counter) per check, and it is very simple. It is fine for a rough daily quota, but weak for strict limits. The flaw: a client sends 100 calls at 12:00:59 and 100 more at 12:01:00. That is 200 in two seconds, twice the limit.

Good: sliding window. A sliding log keeps a timestamp for every call. It is exact, but a key at its limit of 1,000 a minute holds 1,000 timestamps, about 8 KB. For 10 million keys that is up to 80 GB, against 1 GB for a bucket. A sliding window counter keeps two counts and weights the old one. With 80 calls last minute, 50 so far this minute and 25% of the minute gone, the estimate is 80 x 0.75 + 50 = 110. That is over 100, so reject. It assumes calls were spread evenly in the last minute, so it is an estimate: close when traffic is steady, cheap in memory.

Great: token bucket. Two numbers per key, tokens and last refill time. It allows bursts up to the bucket size, and it lets a heavy call spend more tokens.

The fourth: leaky bucket. Requests join a queue that drains at a fixed rate, and overflow is dropped. Output is perfectly smooth, but a burst is delayed instead of answered quickly. It suits protecting a slow downstream, not an API gateway that wants to reject in under a millisecond.

Meera's wrong belief: "The sliding log is the most accurate, so it is the best." Accuracy costs memory, and a few percent is acceptable here. One more trade-off: a bucket needs elapsed time, so use the store's clock inside the script. A gateway with a wrong clock then cannot create or destroy tokens.

Deep dive 2: exact, or fast?

Every check pays a store trip of about 0.5 ms. For most calls that is fine. Two things can push back.

Hot keys. One abusive key can send 50,000 checks a second, and they all land on one shard that handles 25,000. Fix: when a key is rejected with a retry time of 3 seconds, remember "blocked until" in the gateway and reject locally for 3 seconds. Repeat calls never reach the store.

Batching. Each gateway can take a batch of 10 tokens from the store and spend them locally, returning to the store only when they run out. This saves most of the trips. The cost: the limit can be off by up to one batch per gateway, in either direction. With 12 gateways that is up to 120 tokens. Against 10,000 a minute, that is about 1%. Against a login limit of 5 a minute, it is far too loose.

So choose per rule, and say so. A read API accepts "roughly right" and batches. Login and OTP routes (a one-time password sent by SMS) need exact counts, so they pay for the trip.

Deep dive 3: when the store is down

The limiter runs on every request, so when it fails, your API fails in the same way.

Weak: wait for the store, and answer 500 when it is down. A short glitch becomes a full outage, caused by the part that exists to protect the API.

Good: a tight timeout of about 5 ms, then fail open, meaning allow the request and count the event. The API stays up. You are briefly unprotected.

Great: a fail mode per rule. Read routes fail open but switch to a coarse local bucket in each gateway: the limit divided by the gateways, so 1,000 a minute / 12 is about 83 per gateway. You keep rough protection. Login, OTP and payment routes fail closed, meaning block the request, because unlimited OTP texts cost money and invite abuse. Add a circuit breaker, a switch that stops calling a sick store for a few seconds, so you do not pay the 5 ms timeout on every request. Alert on the fail-open count, so nobody learns a week later that limits were off.

⚠️ Warning: Fail open trades protection for availability. Fail closed trades availability for safety. A single global switch is the answer of a candidate who has not thought about login.

Write the plan the way you would say it.

What breaks, and how you notice

  • A shard fails over. Replication is asynchronous, so the replica may miss a few recent decrements and some clients get a few extra calls. Acceptable for limiting. You see a failover event and a dip in 429s.
  • The whole store is unreachable. Timeouts, open circuit breakers, fail-open alerts.
  • A bad rule is pushed, such as 1 a minute on checkout. The 429 rate for that rule jumps. Roll back to the previous rules version; gateways pick it up within 30 seconds.
  • Clients retry 429s at once and multiply the load. Make your SDKs honour Retry-After and back off with jitter.

Watch four numbers: check latency, 429 rate per rule, store errors and fail-open count.

What Mid and Senior sound like, and the follow-ups

A Mid answer picks token bucket or sliding window, keeps counters in a shared fast store, returns 429 with Retry-After, and limits per key. A Senior answer also makes the check atomic, sizes four shards from 100,000 checks a second, decides fail open or closed per route, and changes rules without deploys.

Expect these follow-ups:

  • Limit across regions? Give each region its own share and sync loosely. A cross-region trip costs tens of milliseconds and breaks the budget.
  • A partner needs more? An overrides table with an expiry.
  • Test a new rule safely? Shadow mode: log what would be a 429, but allow it.
  • Bulk exports? Charge several tokens with the cost field.

📌 Summary: Token bucket gives bursts for two numbers per key. Batch tokens only on loose limits. Decide fail open or closed per route, with a 5 ms timeout and a local fallback, and alert on it.

What Meera learns next

The limiter protects the front door. Next question on Kabir's list is a chat app: messages that must arrive in order, phones that go offline, and connections that stay open for hours.

Check your understanding

  1. A fixed-window limit is 100 a minute. A client sends 100 calls at 12:00:59 and 100 more at 12:01:00. What happened, and which algorithm avoids it?
  2. A sliding window counter has 80 calls in the previous minute and 50 so far this minute, and 25% of the minute has passed. The limit is 100. What happens to the next call?
  3. The counter store is unreachable for 20 seconds. SwiftKart has a product-read route and an OTP-send route. What should each do?
  4. Each of 12 gateways batches 10 tokens from the store. Which rule must NOT use batching?
  5. After a deploy, the 429 rate on checkout jumps from 0.1% to 60%. A rule changed from 600 a minute to 1 a minute by mistake. What do you do first?