1. Token Bucket & Leaky Bucket
A rate limiter's job is simple to state and easy to get subtly wrong: decide, per
request, whether to allow it or reject it, based on how many requests this client has
already made recently. Token bucket is the algorithm most production
APIs reach for first. Picture a bucket that holds up to capacity tokens
and refills at a fixed rate; each incoming request consumes one token,
and a request is only allowed if a token is available. Critically, unused tokens
accumulate up to the bucket's capacity, which means a client that's been quiet can
legitimately burst above its steady-state rate for a short period.
Bucket: capacity = 10 tokens, refill rate = 5 tokens/second
t=0.0s bucket has 10 tokens (full, client was idle)
t=0.0s client sends 10 requests instantly -> all 10 allowed,
bucket now at 0 tokens
t=0.0s client sends an 11th request -> rejected, bucket empty
t=1.0s bucket has refilled by 5 tokens (1 second * 5/sec) -> 5 available
t=1.0s client sends 5 requests -> all allowed, bucket at 0 again
That initial burst of 10 is a deliberate feature, not a bug: real clients are bursty (a page load might fire six API calls at once), and token bucket tolerates that as long as the client isn't sustained above its refill rate over time. Leaky bucket makes the opposite tradeoff. Requests enter a fixed-size queue and are processed — "leak out" — at a strictly constant rate, regardless of how bursty the arrivals were; a burst just makes the queue fill up faster, and once the queue is full, new requests are dropped outright.
requests --> [ queue, max 20 ] --> drains at fixed 5 req/sec --> backend
|
+-- queue full? incoming request is rejected
Ten requests arrive in the same instant:
queue holds all 10 (under capacity of 20)
backend still only ever sees 5 requests/second, smoothed out
The practical difference: token bucket protects the backend from sustained overload while still feeling responsive to legitimate bursty clients; leaky bucket protects the backend from bursts themselves, at the cost of added latency for requests sitting in the queue. Most public APIs (Stripe, AWS, GitHub) use token-bucket-flavored limits for exactly this reason — a burst from a client that's about to succeed shouldn't be penalized the same as sustained abuse.
An interviewer rarely wants a definition of both algorithms — they want to see you pick one for the system at hand and justify it against the requirements. "This is a payments API where I want to smooth traffic to a fragile downstream processor, so I'd lean leaky bucket" is a stronger answer than reciting both mechanisms and stopping.
2. Sliding Window Counters & Logs
The simplest rate limiter anyone reaches for is a fixed window counter: count requests in the current minute (or second), reset the counter when the clock rolls over to a new window. It's cheap to implement, but it has a well-known edge case that's worth being able to state precisely, because interviewers ask for it directly:
Limit: 100 requests per minute, window boundaries at :00
Window [0:00 - 1:00): client sends 100 requests at 0:59 -> all allowed
Window [1:00 - 2:00): client sends 100 requests at 1:01 -> all allowed
Result: 200 requests actually landed within a 2-second span
(0:59 to 1:01), even though the stated limit is 100 per minute.
A sliding window log fixes this exactly: store the timestamp of every request a client makes (in a sorted structure), and on each new request, count how many stored timestamps fall within the trailing window (e.g. the last 60 seconds), evicting anything older. It's precise, but it's also memory-hungry at scale — a high-traffic client needs a timestamp stored per request, which doesn't stay cheap once you're rate-limiting millions of clients.
The practical middle ground, and the one most real systems actually ship, is a sliding window counter: keep two fixed-window counters (current and previous) and estimate the trailing window's count as a weighted blend of the two, weighted by how far into the current window you are.
Limit: 100 requests/minute
Previous window [0:00-1:00): 80 requests
Current window [1:00-2:00): 30 requests so far
Now: 1:15 -> 25% into the current window
Estimated count in trailing 60s window:
= previous_window_count * (1 - elapsed_fraction) + current_window_count
= 80 * (1 - 0.25) + 30
= 80 * 0.75 + 30
= 60 + 30 = 90
90 < 100 -> request allowed. This approximates the sliding log's
accuracy at a fraction of the memory: two counters per client,
not one timestamp per request.
This is an approximation — it assumes requests were spread evenly through the previous window, which isn't always true — but the error is small in practice and the memory savings are large, which is exactly the kind of accuracy-for-cost tradeoff that shows up constantly in system design.
"What's wrong with a fixed window counter?" is one of the most common follow-up questions in this topic. Being able to state the 2x-burst-at-the-boundary problem precisely, with a concrete example like the one above, is a strong signal on its own — it shows you understand the algorithm's failure mode, not just its happy path.
3. The API Gateway's Responsibilities
An API gateway is the single entry point every external request passes through before reaching any backend service — a reverse proxy with opinions. Centralizing these responsibilities in one layer means every service behind it gets them for free, instead of every team reimplementing auth checks and throttling inside their own service:
[Client] --> [API Gateway] --> routes to --> [Orders Service]
| --> [Users Service]
| --> [Search Service]
|
+-- TLS termination
+-- Authentication (validate JWT / API key)
+-- Rate limiting / throttling (this week's Sections 1-2)
+-- Request routing (path/host -> backend service)
+-- Request shaping (header injection, response
| transformation, request/response logging)
+-- Basic observability (metrics, tracing IDs)
Rate limiting belongs at the gateway specifically because it's a cross-cutting policy, not a feature of any one service: the gateway sees every request before it fans out to Orders, Users or Search, so it's the one place that can enforce "this client gets 1,000 requests/minute total" without each downstream service needing to know about the others' traffic. The same logic applies to authentication — validating a token once at the edge is both simpler and more secure than trusting every internal service to do it correctly and consistently.
Putting everything in one entry point creates an obvious question: doesn't that just move the bottleneck? Yes, unless the gateway is designed as a stateless, horizontally scaled fleet behind a load balancer, exactly like the app servers in Week 3 — the gateway is a service like any other, not a magic singular box. A gateway that can't scale out becomes the single point of failure it was supposed to protect the rest of the system from.
4. Distributed Rate Limiting Across Multiple Servers
Every algorithm in Sections 1–2 assumed one thing quietly: that there's a single place tracking a client's request count. That assumption breaks the moment a load balancer spreads a client's requests across, say, five API servers, each keeping counters in its own local memory — the client can now make 5x its stated limit, once per server, and no single server ever sees a violation.
Client limit: 100 requests/minute
Load balancer spreads requests across 5 app servers, round robin
Server A: sees 100 requests -> local counter says "at limit," blocks more
Server B: sees 100 requests -> same
Server C, D, E: same
Actual total the client got through: 500 requests/minute
Stated limit was 100. Local counters were each individually
"correct" and still produced a 5x violation.
The fix is the same pattern Week 9 introduced for reasoning about shared state: move the count to a single, shared, low-latency store that every server reads and writes — typically Redis, chosen because in-memory counters are cheap to increment and Redis supports the atomic operations this needs. The critical detail is atomicity: a naive "read the counter, check if under limit, then increment" sequence has a race condition — two servers can both read the same pre-increment value and both allow a request that, combined, pushes the client over the limit.
-- Executed as a single atomic Lua script so no other client
-- request can interleave between the read and the write
local key = "ratelimit:" .. client_id
local count = redis.call("INCR", key)
if count == 1 then
redis.call("EXPIRE", key, 60) -- window resets after 60s
end
if count > 100 then
return "REJECTED"
else
return "ALLOWED"
end
Running this as one atomic script (rather than separate GET/check/INCR calls from the application) is what closes the race condition — Redis executes the whole script without interleaving another client's request in the middle. The cost is a network round trip to Redis on every request, which adds latency the purely local version didn't have; a common mitigation is letting each app server keep a small local cache of "definitely still under limit" and only hit Redis near the boundary, trading a little precision for lower average latency — the same kind of consistency-versus-latency tradeoff Week 9 formalized as CP vs. AP.
Centralizing rate-limit state in one Redis instance solves the correctness problem and creates an availability one — if that instance goes down, does every request get rejected, or every request get allowed? Neither extreme is usually right; a common answer is "fail open" (allow requests) for a short outage window, on the reasoning that briefly under-enforcing a rate limit is a much smaller risk than taking the entire API down. State that reasoning explicitly if asked — it's a judgment call, not a fact to recite.
5. Hands-on Exercise
Design a tiered rate limiter for a public API
A SaaS company exposes a public API with two pricing tiers: Free (100 requests/minute) and Pro (2,000 requests/minute), served by a fleet of stateless API servers behind a load balancer.
Requirements:
- Choose an algorithm (token bucket, leaky bucket, or sliding window counter) for this use case and justify the choice in 2–3 sentences, referencing the specific tradeoff that matters here.
- Decide what the rate-limit key is (per API key? per IP? both?) and explain what abuse case an IP-only key would fail to catch.
- Sketch where in the request path the check happens (Section 3) and what shared store holds the counters, given the multi-server problem from Section 4.
- Write the exact HTTP response (status code and at least one header) a client should get when they're rate-limited, and explain what that header lets a well-behaved client do.
- Write two sentences on what your design does if the shared counter store becomes unavailable, and why you chose that failure behavior.
A real API almost always returns 429 Too Many Requests with a Retry-After header telling the client how many seconds to wait — this turns a rejected request into something the client can programmatically recover from, rather than a mystery failure it has to guess about and blindly retry.
6. Knowledge Check
Four quick questions. Expand each to check your answer.
Q1
Why does token bucket allow a burst of requests while leaky bucket smooths them to a constant rate — and when would you want each behavior?
Why does token bucket allow a burst of requests while leaky bucket smooths them to a constant rate — and when would you want each behavior?
Token bucket lets unused capacity accumulate up to the bucket size, so an idle client can spend a burst of saved-up tokens all at once — appropriate when bursty-but-legitimate traffic (a page firing several calls on load) shouldn't be penalized. Leaky bucket enforces a strictly constant output rate regardless of how requests arrive, which is the right choice when the downstream system genuinely cannot tolerate bursts, such as a fragile legacy service behind the API.
Q2
What specifically goes wrong with a fixed window counter at the window boundary, and how does a sliding window counter improve on it?
What specifically goes wrong with a fixed window counter at the window boundary, and how does a sliding window counter improve on it?
Because the counter resets sharply at each window boundary, a client can send a full limit's worth of requests at the very end of one window and another full limit's worth at the very start of the next, getting up to 2x the stated limit within a span of seconds. A sliding window counter avoids this by blending the previous and current window counts weighted by elapsed time, producing an estimate that reflects the actual trailing period instead of a hard reset.
Q3
Why is rate limiting handled at the API gateway rather than inside each individual backend service?
Why is rate limiting handled at the API gateway rather than inside each individual backend service?
Rate limiting is a cross-cutting policy that needs visibility into a client's total traffic across every service, not just one — the gateway is the only layer every request passes through before fanning out, making it the sole place that can enforce a client-wide limit correctly. Pushing the logic into each service instead would mean duplicating it many times over and losing any single view of a client's aggregate usage.
Q4
Why does a naive "read the counter, then increment it" approach break under multiple concurrent API servers, and what fixes it?
Why does a naive "read the counter, then increment it" approach break under multiple concurrent API servers, and what fixes it?
Two servers can both read the same counter value before either has written back an increment, so both independently conclude the client is under the limit and both allow a request that, combined, exceeds it — a classic race condition. The fix is making the read-check-increment sequence atomic, typically by running it as a single Lua script inside Redis, so no other request can interleave between the read and the write.