Rate Limiter: requirements, scale and the five algorithms

The prompt: "Design a rate limiter for our public API."

Stop here. Set a 45-minute timer and work the four steps from Section 4 on paper before reading on. This is the best first case study in the course because the scope is small enough to finish and the hard part is genuinely hard.

This lesson covers the first half of the answer: what to ask, what to compute, and which algorithm to use. Four requirements and four numbers come first, and the numbers decide the algorithm more than any elegance argument does. The second lesson places the limiter in the architecture and makes it correct across many servers, which is the part interviewers actually probe.

What a rate limiter is

A rate limiter controls how many requests a client may make in a period of time, rejecting or delaying the rest. Without one, a single misbehaving client — a runaway retry loop, a scraper, or an attacker — consumes capacity that belongs to everyone else.

It exists for three reasons: cost control (each request costs money, and some cost a lot), availability (one client should not be able to saturate a shared service), and abuse prevention (brute-force login attempts, scraping, spam).

The five questions that shape everything

1. Client-side or server-side? Client-side limiting is a courtesy: an attacker controls the client and will remove it. Any limiter that matters is server-side. Say this quickly and move on — it takes ten seconds and shows you know the difference.

2. What is the limit key? This is the most consequential question, and candidates skip it.

The usual answer is a composite: user identifier when present, IP address when not, and a separate stricter limit on expensive or sensitive endpoints such as login and search.

3. What happens when a client exceeds the limit? Three options: reject immediately (HTTP 429), queue the request and serve it when capacity frees up, or throttle — degrade rather than refuse. Rejection is the default because queueing turns a rate problem into a latency problem and can exhaust memory. Queueing suits background jobs, not user-facing reads.

4. Is it distributed? If the API runs on more than one server — it does — then per-server counters are wrong, and Making it distributed is the whole reason this problem is interesting.

5. What are the limits? Ask for one concrete number. "100 requests per minute per user, 1,000 per hour" is enough to compute against. Also ask whether limits differ by customer tier, because per-tier limits change the storage from one number to a lookup.

Two more worth asking if time allows

Accuracy versus performance. Is it acceptable to occasionally allow 105 requests when the limit is 100? Almost always yes, and the answer unlocks much cheaper designs.

Fail open or fail closed? If the limiter itself is unavailable, do you let all traffic through or block it? For a public API, fail open is the standard choice: a limiter outage should not become an API outage. For a login endpoint or anything protecting money, fail closed. Say which and why.

Functional requirements

With the questions answered, write the contract down.

• Limit requests per client key over a time window, at a configurable rate.
• Return a clear signal when a client is limited, with enough information to back off.
• Support different limits for different endpoints and customer tiers.
• Work correctly when the API runs across many servers.

Non-functional requirements

• Low latency. The limiter sits in the path of every request. Its cost is added to every single one, so it needs to be a small fraction of the request budget.
• Low memory. It tracks state per active key, and there can be millions.
• Highly available and fail-open. The limiter must not become a new single point of failure for the API.
• Accurate enough. Exact counting is expensive; agree what "enough" means.

The numbers

Assume an invented but realistic service: 10 million registered users, a peak of 50,000 requests per second, and a limit of 100 requests per minute per user.

Active keys. Not all 10 million users are active in any given minute. Say 1 million are. That is the number of counters that must exist at once.

Memory, per algorithm. This is where the algorithm choice becomes concrete.

• Token bucket stores two values per key: a token count (4 bytes) and a last-refill timestamp (8 bytes). With the key string and store overhead, call it ~100 bytes per key. 1 million keys × 100 bytes = 100 MB. Trivial.
• Sliding window log stores a timestamp for every request in the window: up to 100 timestamps × 8 bytes = 800 bytes, plus overhead, call it ~1 KB per key. 1 million keys = 1 GB. Ten times more, for exactness.

That single comparison — 100 MB against 1 GB — is the memory argument, and it is worth stating with the arithmetic rather than as "the log uses more memory".

Throughput on the counter store. At 50,000 requests per second, every request performs at least one operation against the shared counter store. A single in-memory store node handles on the order of 100,000 simple operations per second, so 50,000 fits — with no headroom for growth, failover, or anything else using that node. Conclusion: shard the counter store by key, three or four nodes minimum. That is a real design decision derived from a real number.

Latency budget. A round trip to the counter store inside the same datacentre is roughly 0.5 ms (The numbers to memorise). If the API's target is 200 ms at the 99th percentile, 0.5 ms is 0.25% of the budget and is acceptable. If the API were a 5 ms internal service, adding 0.5 ms is a 10% tax and the design should change — that is the condition under which you would move to local counters with asynchronous synchronisation (Making it distributed).

Storage over time. Counters are ephemeral: each key expires after its window. There is no long-term storage requirement at all, which is unusual and worth saying — it means the counter store can be a pure in-memory cache with no persistence, and losing it means losing enforcement for one window, not losing data.

The five algorithms: token bucket

There are five standard algorithms. Each is a different answer to "what does 100 requests per minute mean?", and the differences show up as burst behaviour.

A token bucket holds up to B tokens and refills at r tokens per second. Each request removes one token; if the bucket is empty, the request is rejected.

With B = 100 and r = 100/60 ≈ 1.67 per second: a client that has been idle can fire 100 requests instantly (draining the bucket), then is limited to about 1.67 per second thereafter.

• Memory: two values per key.
• Bursts: allowed, up to the bucket size — usually a feature, since real clients are bursty.
• Where used: the most common choice in API gateways and cloud services.

Leaky bucket

Requests enter a fixed-size queue and are processed at a constant rate — like water leaking from a bucket at a steady drip. Overflow is rejected.

• Memory: the queue, so proportional to queue size.
• Bursts: smoothed away entirely; the output rate is perfectly constant.
• Cost: requests wait, so latency rises under load, and a full queue rejects. Right when you are protecting a downstream system that cannot absorb bursts; wrong for user-facing reads, where a waiting request is worse than a rejected one.

Fixed window counter

Divide time into fixed windows (each minute). Keep one counter per key per window. Increment on each request; reject above the limit; the counter resets at the window boundary.

• Memory: one integer per key. The cheapest possible.
• The flaw, concretely: with a limit of 100 per minute, a client sends 100 requests at 10:00:59 and another 100 at 10:01:00. Both windows are within their limit. The server received 200 requests in about one second — twice the intended rate, delivered as a spike. A client that discovers this can sustain double the limit indefinitely by timing its bursts to the boundary.

Sliding window log

Store a timestamp for every allowed request. On each new request, discard timestamps older than the window, count what remains, and allow if the count is under the limit.

• Memory: one timestamp per request in the window — 1 KB per key at a limit of 100, as computed in the numbers above.
• Accuracy: exact. No boundary effect at all.
• Cost: the memory, plus the work of trimming the log on every request.

Sliding window counter

The pragmatic compromise. Keep a counter for the current window and the previous one, and estimate the rate as a weighted blend.

count = current window count + previous window count × (fraction of the previous window still inside the sliding window)

Worked: limit 100/minute. The previous minute had 80 requests, the current minute has 30, and we are 25% into the current minute — so 75% of the sliding window lies in the previous minute.

estimate = 30 + (80 × 0.75) = 90 → under 100, allow.

• Memory: two integers per key.
• Accuracy: approximate. It assumes the previous window's requests were spread evenly, which they may not have been, so it can allow slightly more or slightly fewer than the true count. In practice the error is small and it removes the boundary burst entirely.

The comparison