Rate Limiters Explained: Token Buckets, Sliding Windows & the Redis Race

Intuition: why every backend needs a bouncer

“Design a rate limiter” shows up in almost every system-design interview — and most candidates fumble it, because they recite an algorithm instead of reasoning about the system. The interview is about what you protect, from whom, where the decision happens, and what breaks when the tradeoffs are wrong. By the end of this guide you’ll name the trap in the simplest design, derive two better ones, and know how the real systems build it.

Three reasons the limiter exists. First, abuse: your login endpoint is a credential-stuffing target — without a limiter, a script can brute-force accounts or burn your SMS budget all night. Second, cost: every request costs compute, and LLM APIs bill per token — an unbounded client can turn your invoice into a horror story. Third, fairness: one noisy tenant must not starve the other forty-nine sharing the same pool.

There are four classic ways to count, and the interview rewards you for reaching each one deliberately. Fixed window counts requests inside each clock minute — dead simple, but it bursts at the boundary. Sliding window counts the last sixty seconds relative to now — precise, but storing every timestamp costs real memory, so production versions approximate. Token bucket lets clients spend saved-up tokens and tolerates bursts. Leaky bucket drains at a constant drip and smooths everything into a steady stream.

How the four designs work — and the race at the heart of it

Fixed window: the trap at the boundary

The simplest counter: each key (a user, an IP, an API key) gets a counter and a one-minute window. First request sets the counter with a 60-second expiry; each request increments; past the cap, every request gets a 429 until the window rolls over. One integer per key — correct, cheap, and hiding a flaw you should volunteer before the interviewer asks.

A cap of 100 requests per minute. A client fires 100 at 12:00:59 — the last second of the window — then 100 more at 12:01:01, the first second of the next. Both counters saw at most 100, so both waves were admitted: 200 requests in 2 seconds against a stated limit of “100 per minute.” The counter never noticed, because windows are a bookkeeping convenience, not a physical fact. Any adversary, and any thundering retry loop, will discover this seam.

Sliding window log: exact, expensive

Fix the boundary by abandoning fixed windows entirely. Keep a sorted log of every request’s timestamp — a Redis sorted set is the canonical store. On each request, evict entries older than sixty seconds, count what remains, and admit only if the count is under the cap. There is no boundary, so there is no burst: the count always reflects exactly the last sixty seconds.

The cost is memory proportional to traffic. A client allowed a million requests per minute needs a million timestamp entries per key. For low-rate endpoints like login this is perfect; for a firehose API it is a Redis bill shaped like a hockey stick. Production systems therefore approximate.

Sliding window counter: the approximation that wins

Keep just two integers: the count for the finished minute and the count for the current minute. To estimate “requests in the last sixty seconds,” blend them: at 15 seconds into the current minute, the estimate is curr + 0.75 × prev, weighting the previous minute by how much of it still overlaps. Two integers per key — constant memory — and the error stays small.

Notice what happened: exactness traded for O(1) memory. In interviews, the follow-up is always “how much memory?” — the sliding-window log costs O(requests per window) per key, the counter costs O(1). Say both, then pick the counter for high-throughput keys and the log for precision-critical ones like login lockout.

Token bucket vs leaky bucket: cousins, opposite temperaments

The token bucket holds a fixed number of tokens — capacity B — and refills at a steady rate r tokens per second. Each request spends one token. Tokens arrive continuously, so a quiet client accumulates savings and spends them at once: a full bucket of 100 admits a 100-request burst instantly. The average rate is capped at r, but bursts up to B are legal. Empty bucket? 429.

The leaky bucket flips the idea. Requests pour into a queue and drain out at a fixed rate — ten per second, steady, no exceptions. A burst of 100 does not get through in one second; it gets processed ten per second, and overflow waits or drops. Where the token bucket absorbs bursts, the leaky bucket flattens them — ideal for a downstream service, a database, or a payment rail that needs a calm, steady drip.

The distributed race — and the Lua fix

One server? In-memory counters, done. But real systems run dozens of API servers, so the counters have to live somewhere shared. That is Redis. And that is where the interview gets interesting, because the naive implementation has a race.

The naive flow is two steps: read the counter, then increment it if under the limit. Two servers handle two requests from the same client at nearly the same instant. Both read 99 against a limit of 100. Both decide “under the limit.” Both increment. The limit was 100; 101 requests got through. Widen that gap across forty instances and the over-admission scales with the fleet. The check and the increment must be one indivisible operation.

Redis gives you exactly that with Lua scripts. Redis executes a Lua script atomically — no other command, from any client, can interleave with it — so a check-and-increment script reads the true current count, decides, and writes the increment before any other instance’s script may begin. Load the script once, invoke it per request with EVALSHA (the client library hashes the script body and sends only the hash after the first call, so the wire cost is about one INCR), and the race is structurally impossible rather than merely unlikely. One caveat worth naming: the atomicity holds per shard — and a failover can briefly lose the most recent writes, which over-admits rather than under-admits. The code section below is the real pattern.

Where the limiter lives — and how it says no

Enforce at the API gateway or edge, before the request touches your services: a rejected request should never consume backend compute. The gateway answers with 429 Too Many Requests — the status code RFC 6585 defined for exactly this (“the user has sent too many requests in a given amount of time”) — and a Retry-After header telling the client how long to wait before trying again. RFC 6585 also says 429 responses must not be stored by caches, which matters when a CDN sits in front of you.

Good APIs also advertise their headroom: OpenAI answers with x-ratelimit-remaining-requests and x-ratelimit-remaining-tokens headers, Anthropic with anthropic-ratelimit-requests-remaining, so well-behaved clients throttle themselves instead of discovering the cliff at full speed. If your gateway sets those headers too, say so — it is a small detail that signals production experience.

LLM APIs: rate limiting at planetary scale

The largest rate limiters in production right now meter AI traffic. OpenAI and Anthropic both enforce per-minute limits on two dimensions at once — requests per minute and tokens per minute — tiered by usage, and either dimension trips a 429. Their clients are the exact retry storms this guide is about: every inference server running continuous batching behind the limiter hammers retries the moment it gets throttled.

The rejection protocol itself is standardized: 429 says “too many requests in a given amount of time,” Retry-After says when to come back, and caches are forbidden from storing the response — so every layer of the stack, from browser to gateway to retry library, agrees on what a rate limit looks like.

Work the token bucket by hand

Bucket capacity 100, refill rate 10 tokens/sec, fully stocked. A 150-request burst arrives at once, then traffic keeps coming at 20 requests/sec.

Three quantities run every interview number: capacity sizes the burst, refill rate sets the sustainable rate, and deficit-over-rate is the Retry-After.

Three production shapes, in Python

A token bucket, the sliding-window-counter approximation, and the Redis Lua check-and-increment — the three patterns behind almost every “design a rate limiter” interview. The Redis script runs server-side and atomically.

import time
from collections import deque


class TokenBucket:
    def __init__(self, capacity, refill_per_sec):
        self.capacity = capacity
        self.refill_per_sec = refill_per_sec
        self.tokens = float(capacity)
        self.last = time.monotonic()

    def allow(self, cost=1):
        now = time.monotonic()
        # refill lazily: tokens earned since last request, capped
        self.tokens = min(
            self.capacity,
            self.tokens + (now - self.last) * self.refill_per_sec,
        )
        self.last = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False

    def retry_after(self, cost=1):
        # seconds until `cost` tokens exist — the Retry-After value
        deficit = max(0.0, cost - self.tokens)
        return deficit / self.refill_per_sec


class SlidingWindowCounter:
    # O(1) memory: two ints + the standard overlap blend.
    def __init__(self, limit, window_sec=60):
        self.limit = limit
        self.window = window_sec
        self.prev_count = 0   # finished window
        self.curr_count = 0   # in-progress window
        self.window_start = time.monotonic()

    def allow(self):
        now = time.monotonic()
        if now - self.window_start >= self.window:
            gap = now - self.window_start
            # roll windows; a long idle gap discards stale history
            self.prev_count = self.curr_count if gap < 2 * self.window else 0
            self.curr_count = 0
            self.window_start = now
        elapsed = (now - self.window_start) / self.window
        # approximate count over the last `window` seconds
        estimate = self.curr_count + self.prev_count * (1 - elapsed)
        if estimate < self.limit:
            self.curr_count += 1
            return True
        return False


# --- distributed: atomic check-and-increment in Redis ---
import redis

r = redis.Redis(host="localhost", port=6379)
# register_script loads once (SCRIPT LOAD) and calls via EVALSHA after;
# the body re-sends only if the server ever answers NOSCRIPT.
check_and_increment = r.register_script("""
local current = redis.call('INCR', KEYS[1])
if current == 1 then
    redis.call('EXPIRE', KEYS[1], tonumber(ARGV[2]))
end
local allowed = 1
if current > tonumber(ARGV[1]) then allowed = 0 end
return {allowed, current, redis.call('TTL', KEYS[1])}
""")

allowed, count, ttl = check_and_increment(
    keys=["ratelimit:login:203.0.113.44"],
    args=[100, 60],   # limit 100, window 60s
)
if not allowed:
    # 429 Too Many Requests, Retry-After: <ttl>
    print("rate limited; retry in", ttl)

Three shapes, three answers: the token bucket for bursty single-process limits, the sliding-window counter for O(1) boundary-safe counting, and the Lua script when the counter must be shared across a fleet without a race.

Six questions that test the real understanding

Key takeaways

1. Fixed window is simple but bursts at the boundary — 200 requests in 2 seconds against a 100/minute cap, and the counter never noticed.
2. Sliding window log is exact but costs O(requests) memory per key; the two-integer counter approximation keeps O(1) memory and kills the boundary seam.
3. Token bucket absorbs bursts up to capacity and caps the average at the refill rate; leaky bucket drains at a constant drip and smooths bursts for fragile downstreams.
4. Distributed limiters have a check-then-increment race — close it with an atomic Redis Lua script via EVALSHA, not two round trips.
5. Enforce at the API gateway, answer 429 with a computed Retry-After, and publish remaining-quota headers so good clients throttle themselves.
6. Compute Retry-After from the deficit and jitter the retries — a synchronized retry wave is the boundary burst wearing a new disguise.