Design a Rate Limiter
Compare fixed window, sliding window, and token bucket algorithms, implement two with an injected clock, and design where limits live in a distributed system.
intermediate45 min#rate-limiting#token-bucket#sliding-window#system-design#worked-example
Prerequisites: A Framework for System Design, Caching Strategies
Why it matters
Any public service eventually meets a client that sends too much: a buggy retry loop, a scraper, a password guesser, or one noisy customer who starves everyone else. A rate limiter caps how often a caller can act. It protects availability, keeps costs predictable, enforces fair use and paid tiers, and slows abuse. It is also a favorite interview problem because the algorithms are small but the distributed version is full of trade-offs.
Intuition
A bouncer at a club with a clicker allows a fixed number of people per hour. The question is how to count "per hour". Reset the clicker at the top of each hour (simple, but a crowd arriving at 9:59 and another at 10:00 doubles the intended rate)? Or look back over the last sixty minutes at every arrival (accurate, but you must remember arrivals)? Or hand out tokens that refill slowly and let people spend them as they like (allows short bursts but caps the long-run rate)? Those three answers are the main algorithms.
How it works
First, the requirements. Functional: limit by a key (user id, API key, or IP address), with configurable limits per rule, and return a clear rejection (HTTP 429 Too Many Requests, ideally with a Retry-After hint). Non-functional: very low added latency, high availability (should the limiter fail open or closed?), accuracy that is good enough, and correctness across many app servers.
Algorithms
- Fixed window counter: count requests in each clock window (for example each minute) and reject above the limit. One counter per key, very cheap. Weakness: a burst at the end of one window plus a burst at the start of the next can pass up to double the limit in a short span.
- Sliding window log: store the timestamp of every accepted request, drop those older than the window, and accept only if fewer than the limit remain. Exact, but memory grows with the limit per key.
- Sliding window counter: keep counts for the current and previous fixed windows and estimate the sliding total by weighting the previous count by how much of it still overlaps. Tiny memory, close approximation.
- Token bucket: a bucket holds up to
capacitytokens and refills at a steadyrate. Each request spends one token; with none left, it is rejected. It allows bursts up to the capacity while enforcing the average rate. Cheap: two numbers per key (token count and last refill time), refilled lazily on each request. - Leaky bucket: requests enter a queue that drains at a fixed rate, smoothing output. Good when downstream needs a steady flow.
token bucket (capacity 3, refill 1 per second)
t=0 [###] 3 requests allowed -> [ ] 4th rejected
t=1 [# ] 1 token refilled -> 1 request allowed
t=3 [## ] 2 tokens refilled -> up to 2 allowed
Here is that bucket (capacity 3, refill 1 per second) handling the same request times the code below uses: 0, 0, 0, 0, 1, 1, 3, 3, 3. Each filled circle is one token.
Spending drains the bucket instantly, refilling is slow and steady, and the bucket never holds more than 3. The result Y Y Y N Y N Y Y N matches the code.
Where it lives
- Local per server: fast and simple, but with N servers a client can get N times the limit unless traffic is pinned to a server.
- Central store (for example a shared in-memory store): all servers update one counter per key, giving a true global limit. The update must be atomic (use an atomic increment or a small server-side script) or two servers will both read the same value and both admit the request. The cost is a network hop per request and a dependency to keep available.
- Hybrid: each server keeps a local allowance and syncs with the center periodically. Faster and cheaper, slightly looser.
Place the limiter at the edge (API gateway or middleware) so rejected requests never reach your application. Decide the failure mode up front: fail open (allow traffic if the limiter is down, protecting availability) or fail closed (block, protecting the backend or security-critical endpoints like login).
| Operation | Time | Notes |
|---|---|---|
| Fixed window counter | O(1) time, O(1) space per key | Boundary bursts up to 2x |
| Sliding window log | O(1) amortized, O(limit) space per key | Exact but memory heavy |
| Sliding window counter | O(1) time, O(1) space per key | Approximate |
| Token bucket | O(1) time, O(1) space per key | Allows bursts up to capacity |
Code: token bucket and sliding window log
Both take an injected clock, so tests control time and the output is deterministic. Times are in seconds.
class Clock:
def __init__(self):
self.now = 0.0
class TokenBucket:
def __init__(self, capacity, refill_per_sec, clock):
self.capacity, self.rate, self.clock = capacity, refill_per_sec, clock
self.tokens = float(capacity)
self.last = clock.now
def allow(self):
now = self.clock.now
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
self.last = now
if self.tokens >= 1:
self.tokens -= 1
return True
return False
class SlidingWindowLog:
def __init__(self, limit, window, clock):
self.limit, self.window, self.clock = limit, window, clock
self.log = []
def allow(self):
now = self.clock.now
self.log = [t for t in self.log if t > now - self.window]
if len(self.log) < self.limit:
self.log.append(now)
return True
return False
def run(limiter, clock, times):
out = []
for t in times:
clock.now = t
out.append("Y" if limiter.allow() else "N")
return " ".join(out)
c1 = Clock()
bucket = TokenBucket(capacity=3, refill_per_sec=1, clock=c1)
times = [0, 0, 0, 0, 1, 1, 3, 3, 3]
print("token bucket: ", run(bucket, c1, times))
c2 = Clock()
window = SlidingWindowLog(limit=3, window=10, clock=c2)
times = [0, 1, 2, 3, 10, 11, 12, 13]
print("sliding window:", run(window, c2, times))class Clock { now = 0; }
class TokenBucket {
constructor(capacity, refillPerSec, clock) {
this.capacity = capacity;
this.rate = refillPerSec;
this.clock = clock;
this.tokens = capacity;
this.last = clock.now;
}
allow() {
const now = this.clock.now;
this.tokens = Math.min(this.capacity, this.tokens + (now - this.last) * this.rate);
this.last = now;
if (this.tokens >= 1) {
this.tokens -= 1;
return true;
}
return false;
}
}
class SlidingWindowLog {
constructor(limit, window, clock) {
this.limit = limit;
this.window = window;
this.clock = clock;
this.log = [];
}
allow() {
const now = this.clock.now;
this.log = this.log.filter((t) => t > now - this.window);
if (this.log.length < this.limit) {
this.log.push(now);
return true;
}
return false;
}
}
function run(limiter, clock, times) {
return times.map((t) => {
clock.now = t;
return limiter.allow() ? "Y" : "N";
}).join(" ");
}
const c1 = new Clock();
const bucket = new TokenBucket(3, 1, c1);
console.log("token bucket: ", run(bucket, c1, [0, 0, 0, 0, 1, 1, 3, 3, 3]));
const c2 = new Clock();
const win = new SlidingWindowLog(3, 10, c2);
console.log("sliding window:", run(win, c2, [0, 1, 2, 3, 10, 11, 12, 13]));Both versions print:
token bucket: Y Y Y N Y N Y Y N
sliding window: Y Y Y N Y Y Y N
Read the token bucket line against the diagram: three requests at time 0 drain the bucket and the fourth is rejected. At time 1 one token has refilled, so one passes. By time 3 two tokens have accumulated, so two of the three pass. In the window log, the request at time 10 is allowed because the one at time 0 has just left the 10-second window, and the one at time 13 is rejected because the window still holds three requests.
Here is the sliding window log from the code (limit 3, window 10 seconds) step by step. Each cell is one logged timestamp.
The log keeps only timestamps newer than now minus 10. Old entries expire one by one, which is why the t=10 request fits but t=13 does not. Output matches the code: Y Y Y N Y Y Y N.
Common pitfalls
- Race conditions in a shared store. Read-then-write on a counter lets concurrent requests slip through. Use atomic operations.
- Clock skew between servers. If servers disagree about the time, windows misalign. Use the shared store's clock or tolerate small error.
- Choosing the wrong key. Limiting by IP punishes users behind one shared address; limiting by account misses unauthenticated abuse. Often you limit on several keys.
- Unbounded memory. One log or bucket per key forever fills memory. Expire idle keys.
- Silent rejections. Return
429withRetry-Afterso well-behaved clients can back off instead of hammering. - No failure plan. Decide fail open or fail closed deliberately, per endpoint.
- Counting retries as new load. Clients that retry immediately worsen the problem. Encourage exponential backoff with jitter.
Practice
Show the fixed-window boundary problem easy
Hint
Place requests just before and just after a window boundary.
Show solution
With a limit of 100 per minute, a client sends 100 requests at 0:59 and another 100 at 1:00. Each fixed window sees exactly 100 and accepts all, yet 200 requests arrived within two seconds, double the intended rate. A sliding window or token bucket would reject the extras.
Token bucket parameters easy
Hint
Capacity controls burst size, refill rate controls the long-run average.
Show solution
To allow 10 requests per second on average with bursts of up to 50, use capacity 50 and refill 10 per second. A client that has been idle can send 50 at once, then is held to 10 per second. A smaller capacity makes traffic smoother; a larger one is more forgiving.
Make it work across servers medium
Hint
Where does the shared state live, and how do you update it safely?
Show solution
Keep each key's tokens and last-refill time in a shared store. Perform the refill-and-spend step atomically, for example in a single server-side script or with a compare-and-set loop, so two servers cannot both spend the last token. Add a short local cache of "this key is currently blocked" to cut round trips.
Sliding window counter hard
Hint
Weight the previous window by how much of it still overlaps the sliding window.
Show solution
Keep prev and curr counts for fixed windows of length W. If you are a fraction f (from 0 to 1) into the current window, estimate the sliding count as prev * (1 - f) + curr. Admit the request if that estimate is below the limit. It uses constant memory and is close to the exact log, assuming traffic was evenly spread across the previous window.
Interview questions
- Which algorithm would you choose? Token bucket is a strong default: constant memory, allows bursts, and enforces an average rate. Use a sliding window when bursts at boundaries are unacceptable and you want precise counts.
- How do you rate limit across many servers? A shared store with atomic updates for a global limit, or local limits with periodic syncing when slight looseness is fine.
- What do you return when a request is limited? HTTP
429with aRetry-Afterheader and a clear message. - Fail open or fail closed? Usually fail open for general API traffic to preserve availability, and fail closed for sensitive endpoints like login attempts. State the reasoning.
- How do you handle different limits for different users? Store a limit per key or plan, look it up (and cache it), and construct the bucket with those parameters.
Interviewers look for: comparing at least two algorithms with their trade-offs, thinking about atomicity and distribution, and explicitly choosing the failure mode.
Quick check
A token bucket has capacity 5 and refills 1 token per second. It is full, then 5 requests arrive at once, then 1 more arrives immediately. What happens?
Finished this lesson?
Further resources
- Token bucket (Wikipedia) (article)
- Rate limiting (Wikipedia) (article)
- Leaky bucket (Wikipedia) (article)