Rate Limiting: Fixed Window, Sliding Window and Token Bucket
Three ways to cap request rates, compared on one burst: a fixed window let 20 of 20 through a 10-per-second limit, a sliding window 10, and a token bucket allowed a controlled burst.
Rate limiting caps how many requests a client may make in a period, rejecting the excess, usually with HTTP 429 and a Retry-After header. The detail interviewers expect: a fixed window counter can pass double the limit across a window boundary, a sliding window log is exact but stores timestamps, and a token bucket allows bursts up to its capacity.
Rate limiting protects a service from overload and abuse. A fixed window counter is simple but allows double the limit across a window boundary: 20 of 20 requests passed a 10-per-second limit. A sliding window log was exact (10 of 20), and a token bucket allows bursts up to its capacity while holding a steady average rate.
- A fixed window rate limiter with a limit of 10 per second allowed all 20 requests sent between times 0.90 and 1.09, double the intended rate, because they spanned a window boundary.
- A sliding window log rate limiter allowed exactly 10 of the same 20 boundary requests, at the cost of storing up to limit timestamps per client.
- A token bucket holds up to a capacity of tokens that refill at a fixed rate, each request spends one token, and only two numbers are stored per client.
- A token bucket with capacity 5 and rate 10 per second let 104 of 150 requests through from a client sending a steady 15 per second for 10 seconds.
- A leaky bucket queues requests and drains them at a constant rate for perfectly smooth output, while a token bucket lets short bursts through immediately.
- Rate limiting across many servers needs shared atomic counters, for example in Redis, or sticky routing, plus a decision to fail open or fail closed if the store is down.
01Why limit requests
Every service has a capacity. Without limits, one misbehaving client, a bug that retries in a tight loop, or a scraper can use it all and degrade the experience for everyone. A rate limiter decides, per client (API key, user id or IP address), how many requests are allowed in a period. Requests over the limit are rejected, usually with HTTP 429 (Too Many Requests) and a Retry-After header, or they are queued or slowed.
Two design questions come first. What is the key: user, API key, IP, endpoint? And what do you want to limit: a strict number per interval, an average rate with bursts allowed, or the number of concurrent requests? The algorithms below make different choices.
02Fixed window counter
import collections
class Fixed:
def __init__(self, limit, win):
self.l, self.w = limit, win
self.cnt = collections.Counter()
def allow(self, t):
k = int(t // self.w) # which window this request falls in
if self.cnt[k] < self.l:
self.cnt[k] += 1
return True
return FalseIt needs one counter per client and window, so memory and time are tiny. The flaw is at the boundary. With a limit of 10 per second, I sent 10 requests at times 0.90 to 0.99 and another 10 at 1.00 to 1.09. All 20 were allowed, because the first ten fell in window 0 and the second ten in window 1. The client made 20 requests inside 0.2 seconds, double the intended rate. If the backend can only handle the limit, this boundary burst can overload it.
03Sliding window log
import collections
class Sliding:
def __init__(self, limit, win):
self.l, self.w, self.q = limit, win, collections.deque()
def allow(self, t):
while self.q and self.q[0] <= t - self.w:
self.q.popleft() # forget requests older than the window
if len(self.q) < self.l:
self.q.append(t)
return True
return FalseOn the same 20 requests, this allowed exactly 10. At any moment, no more than 10 requests exist in the previous second, so there is no boundary loophole. The price is memory: it stores up to limit timestamps per client, which is costly for limits of thousands per minute. A common compromise is the sliding window counter, which keeps counts for the current and previous fixed windows and weights the previous one by how much of it still overlaps. It approximates the log with two numbers.
04Token bucket
class Bucket:
def __init__(self, cap, rate):
self.cap, self.rate, self.tok, self.t = cap, rate, cap, 0
def allow(self, t):
self.tok = min(self.cap, self.tok + (t - self.t) * self.rate)
self.t = t
if self.tok >= 1:
self.tok -= 1
return True
return FalseThe bucket holds up to cap tokens and gains rate tokens per second. A request needs one token. Idle clients accumulate tokens up to the cap, so a short burst is allowed, but the long-run average cannot exceed the rate. With capacity 10 and rate 10 per second, the same 20-request test allowed 11: the 10 stored tokens plus one refilled during the 0.1-second span.
Two more results. A client sending a steady 15 requests per second for 10 seconds into a bucket with capacity 5 and rate 10 got 104 of 150 requests through, about the rate times the duration (100) plus the initial burst of 5. And 20 requests arriving at the same instant with capacity 5 got exactly 5 through. Only two numbers are stored per client (tokens and last time), which makes it cheap, and it is the algorithm behind many API gateways and cloud limiters.
05Leaky bucket
A leaky bucket puts incoming requests in a queue that is processed at a constant rate. If the queue is full, new requests are dropped. It produces a perfectly smooth output rate, which is useful when the downstream system cannot take bursts at all. The token bucket instead lets bursts through immediately and limits the average. Use leaky when smoothing matters, token bucket when responsiveness to short bursts matters.
06Rate limiting across many servers
If each of 10 API servers keeps its own counter, a client that spreads requests across all of them can get 10 times the limit. Options: keep counters in a shared store such as Redis, using atomic increments or a small Lua script so that check and update cannot race; route each client to the same server (sticky routing); or accept an approximate limit by dividing it among servers.
The shared store becomes a dependency on the hot path. Decide what happens if it is down: fail open (allow requests, risking overload) or fail closed (reject them, risking an outage caused by the limiter). Many APIs fail open and raise an alarm, but for abuse-sensitive endpoints failing closed can be the right call. Return X-RateLimit-Remaining and Retry-After headers so well-behaved clients can slow down on their own, and use exponential backoff with jitter on the client side.
07Common interview questions
Q: Weakness of the fixed window counter?
A: A burst across a window boundary can pass twice the limit.
Q: How does a sliding window log avoid that?
A: It tracks exact timestamps, so any rolling window has at most the limit. It uses more memory.
Q: How does a token bucket work and why is it popular?
A: Tokens refill at a constant rate up to a capacity, and each request spends one. It allows controlled bursts, keeps an average rate, and stores two numbers per client.
Q: Token bucket versus leaky bucket?
A: Token bucket permits bursts. Leaky bucket smooths output to a constant rate.
Q: How do you rate limit in a distributed system?
A: Shared atomic counters (for example Redis), or sticky routing, with a decided policy for when the store is unavailable.
Q: What should a rejected response look like?
A: HTTP 429 with a Retry-After header.