What's wrong with a fixed-window rate limiter?

Requests can bunch up at a window boundary: a client can use the full limit at the end of one window and again at the start of the next, getting about twice the limit in a short time. Sliding windows or token buckets smooth this out.

How do you keep a rate limit accurate across many app servers?

Keep the counters in a shared store such as Redis and update them atomically (a Lua script or INCR with EXPIRE), so concurrent requests on different servers can't both read the same count and both pass. Keys expire when idle.

Design a Rate Limiter — System Design Interviews, Step by Step

The question

"Design a rate limiter for a public API: each API key may make at most 100 requests per minute, across all our servers."

Clarify the requirements

Functional: limit by API key (and by IP for anonymous traffic); different limits per plan; answer 429 Too Many Requests with a Retry-After header when over the limit.
Scale: 50 app servers, 20,000 requests/s in total, 1 million API keys.
Non-functional: adds < 2 ms per request; limits roughly accurate (a few extra requests at a boundary are acceptable); if the limiter breaks, the API should keep working.
Out of scope: billing, abuse detection beyond simple limits.

Estimate the scale

20,000 checks per second: one Redis node handles ~100,000 simple operations/s, so a small Redis cluster is plenty.
Memory: 1 million keys × ~100 bytes of counter state ≈ 100 MB. Tiny.
The real constraint is latency: one network round trip to Redis (~0.5 ms) per request.

API and data model

The limiter isn't a public API; it's a check inside the request path (middleware or API gateway):

allow(key, limit, window) -> { allowed: bool, remaining: int, retry_after_s: int }

Response headers: X-RateLimit-Limit, X-RateLimit-Remaining, Retry-After (on 429)

Redis: ratelimit:{api_key}  ->  token count + last refill time   (expires when idle)
Config: plan -> { limit, window, burst }

High-level design

client ─► load balancer ─► app server ─► rate-limit middleware ──► Redis (shared counters)
                                     │           │
                                     │      over the limit? ──► 429 + Retry-After
                                     └──► handler (only if allowed)

Every server checks the same counters in Redis, so the limit holds across the fleet. Limits per plan are cached in each server's memory.

Deep dives

1. Which algorithm?

Algorithm	How	Good	Bad
Fixed window	Count per calendar minute	Simplest, one counter	Burst of 2× at the boundary (100 at 0:59, 100 at 1:00)
Sliding window log	Store each request's timestamp	Exact	Memory per request
Sliding window counter	Weighted mix of this and last window's counts	Smooth, cheap	Approximate
Token bucket	Bucket refills at a steady rate; each request takes a token	Allows short bursts, smooth average	Two numbers to tune

The token bucket is the usual answer: it allows a burst (a page that fires 10 calls at once) while capping the average.

Fixed window vs token bucket at a window boundaryTry it yourself

class FixedWindow:
    def __init__(self, limit, window):
        self.limit, self.window, self.counts = limit, window, {}

    def allow(self, now):
        bucket = int(now // self.window)
        self.counts[bucket] = self.counts.get(bucket, 0) + 1
        return self.counts[bucket] <= self.limit


class TokenBucket:
    def __init__(self, capacity, refill_per_second):
        self.capacity, self.rate = capacity, refill_per_second
        self.tokens, self.last = capacity, 0.0

    def allow(self, 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


# Limit: 10 per 60 s. A client sends 10 requests at t=59s and 10 more at t=61s.
times = [59.0] * 10 + [61.0] * 10
fixed = FixedWindow(limit=10, window=60)
bucket = TokenBucket(capacity=10, refill_per_second=10 / 60)

fixed_ok = sum(fixed.allow(t) for t in times)
bucket_ok = sum(bucket.allow(t) for t in times)
print(f"fixed window allowed {fixed_ok} of 20 within 2 seconds")
print(f"token bucket allowed {bucket_ok} of 20 within 2 seconds")

# Steady traffic: one request every 5 s for 2 minutes is under the limit for both.
steady = TokenBucket(capacity=10, refill_per_second=10 / 60)
print("steady traffic allowed:", sum(steady.allow(t * 5.0) for t in range(24)), "of 24")

class FixedWindow:
    def __init__(self, limit, window):
        self.limit, self.window, self.counts = limit, window, {}

def allow(self, now):
        bucket = int(now // self.window)
        self.counts[bucket] = self.counts.get(bucket, 0) + 1
        return self.counts[bucket] <= self.limit

class TokenBucket:
    def __init__(self, capacity, refill_per_second):
        self.capacity, self.rate = capacity, refill_per_second
        self.tokens, self.last = capacity, 0.0

def allow(self, 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

# Limit: 10 per 60 s. A client sends 10 requests at t=59s and 10 more at t=61s.
times = [59.0] * 10 + [61.0] * 10
fixed = FixedWindow(limit=10, window=60)
bucket = TokenBucket(capacity=10, refill_per_second=10 / 60)

fixed_ok = sum(fixed.allow(t) for t in times)
bucket_ok = sum(bucket.allow(t) for t in times)
print(f"fixed window allowed {fixed_ok} of 20 within 2 seconds")
print(f"token bucket allowed {bucket_ok} of 20 within 2 seconds")

# Steady traffic: one request every 5 s for 2 minutes is under the limit for both.
steady = TokenBucket(capacity=10, refill_per_second=10 / 60)
print("steady traffic allowed:", sum(steady.allow(t * 5.0) for t in range(24)), "of 24")

Output

fixed window allowed 20 of 20 within 2 seconds
token bucket allowed 10 of 20 within 2 seconds
steady traffic allowed: 24 of 24

The fixed window lets 20 requests through in two seconds because they straddle the minute boundary; the token bucket allows the burst of 10, then only what has refilled.

2. Making it distributed and atomic. Two servers reading and writing the same counter at once can both see "99" and both allow. Do the read-modify-write inside Redis in one step: a Lua script (or INCR with EXPIRE for a fixed window) runs atomically. Set a TTL so idle keys disappear.

3. Latency. One Redis round trip per request is ~0.5 ms. For very hot paths, servers can keep a small local allowance (e.g. take 10 tokens at a time from Redis) at the cost of a little accuracy.

4. When Redis is down. Choose fail open (allow requests, log loudly) for a general API so an outage in the limiter doesn't become a full outage; choose fail closed for endpoints where abuse is costly (login attempts, SMS sending).

Trade-offs

Accuracy vs cost: exact sliding logs cost memory; token buckets and sliding counters are approximate but cheap.
Central vs local: a central Redis gives accurate global limits; local in-memory limits are faster but only per server (N servers ≈ N× the limit).
Where to enforce: an API gateway centralises it; middleware in each service gives finer control.
Fail open vs closed: availability vs protection.

What interviewers look for

Knowing several algorithms and the boundary-burst problem.
An atomic, shared counter for a multi-server fleet.
Proper client feedback: 429, Retry-After, remaining-quota headers.
A failure-mode decision for the limiter itself.

Key points

Token bucket: bursts allowed, average capped; the common default.
Fixed windows can let 2× through at the boundary.
Shared state in Redis, updated atomically (Lua or INCR), with TTLs.
Decide fail-open vs fail-closed per endpoint.