Design a Rate Limiter: Token Bucket, Redis, and Real Trade-offs
How to design a distributed API rate limiter — token bucket vs sliding window, an atomic Redis implementation, capacity numbers, and fail-open trade-offs.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A rate limiter's job is one sentence: given a key and a rule like 100 requests per minute, decide allow or deny in under a millisecond, for millions of keys, without ever becoming the thing that takes your API down. Every interesting decision in the design falls out of that last clause — the limiter protects the backend, so it can never be a weaker link than the backend it guards.
The prompt looks trivial until you put it behind 50 servers sharing one budget. Then "just increment a counter" turns into questions about atomicity, network round trips, what happens when Redis blinks, and how a per-user limit, a per-tenant limit, and a global limit all hold at once. That's the design worth practicing, and it's what this guide walks through.
Functional and non-functional requirements
Start by pinning down what a caller can ask for and what it gets back:
- Enforce a limit per key — user ID, IP, API key, or tenant — configurable per endpoint (
POST /loginmight allow 5/min whileGET /searchallows 100/min). - When the limit is exceeded, return HTTP 429 Too Many Requests with a
Retry-Afterheader so a well-behaved client knows exactly when to try again. - Support multiple rules on one request — a single call can be subject to a user limit and a tenant limit simultaneously.
The non-functional bounds are what make it a systems problem, not a coding exercise:
| Requirement | Target | Why it matters |
|---|---|---|
| Added latency | < 1ms p99 | The limiter sits on every request; overhead multiplies across all traffic |
| Availability | Higher than the API it protects | A limiter outage must not become an API outage |
| Accuracy | "Good enough," tunable | Perfect global counting costs latency; most APIs trade a few percent for speed |
| Memory | O(1) per key ideally | Millions of active keys must fit in RAM cheaply |
The accuracy row is the subtle one. A limiter that is exactly correct requires every node to agree on a single counter before answering — which means a network hop on the hot path. Most production limiters accept a small, bounded overshoot in exchange for answering from local memory.
Where does the rate limiter live?
Put enforcement at the API gateway (or a thin middleware directly in front of your services). The gateway sees every public request before any downstream capacity is spent, so one policy there protects everything behind it and you avoid re-implementing limits in every service.
The client cannot be the enforcement point — it's untrusted. A mobile app can display "you have 3 requests left" as a courtesy, but an attacker just edits the app. Client-side limits are advisory; server-side limits are real. Internal services may still add their own quotas for defense in depth (an internal batch job shouldn't be able to hammer the database even if it slips past the gateway), but that supplements the gateway, it doesn't replace it.
Which algorithm? Token bucket, leaky bucket, and windows
Four algorithms show up constantly. They differ in how they treat bursts and how much memory they cost per key.
| Algorithm | Burst behavior | Memory/key | Accuracy | Best for |
|---|---|---|---|---|
| Token bucket | Allows bursts up to bucket size | O(1) — 2 numbers | Good | General API limiting |
| Leaky bucket | Smooths output to a fixed rate | O(1) | Good | Traffic shaping, queues |
| Fixed window | Up to 2× limit at boundaries | O(1) — 1 counter | Weak | Simplest possible counter |
| Sliding window log | Exact | O(N) — one timestamp/request | Perfect | Low-volume, high-stakes limits |
| Sliding window counter | Near-exact | O(1) | Very good | High-volume with tight accuracy |
Fixed window is the trap answer. A "100 per minute" fixed-window counter resets at each minute boundary, so a client that sends 100 requests at 11:00:59 and another 100 at 11:01:00 pushes 200 requests through in one second — double the intended rate, right at the seam.
Sliding window log fixes accuracy by storing the timestamp of every request and counting how many fall inside the trailing window. It's exact but costs one entry per request per key, which explodes for hot keys. The sliding window counter approximates it with two adjacent fixed-window counts and a weighted blend, recovering O(1) memory with only a small error.
For a general-purpose API, token bucket is the usual pick: it's O(1), it tolerates the natural burstiness of real clients, and it's easy to reason about. That's the algorithm the rest of this guide implements.
How token bucket works
Picture a bucket that holds up to capacity tokens and refills at refillRate tokens per second. Each request removes one token. If a token is available, allow it; if the bucket is empty, deny with a 429. Tokens accumulate up to the cap while the client is quiet, which is exactly what lets a bursty-but-well-behaved client fire a short burst and then settle.
You never run a background timer to add tokens. Instead you store two numbers per key — tokens and lastRefill — and compute the refill lazily on each request based on elapsed time:
function allow(state, now, capacity, refillRate) {
// Refill based on how long since we last touched this bucket
const elapsed = (now - state.lastRefill) / 1000; // seconds
state.tokens = Math.min(capacity, state.tokens + elapsed * refillRate);
state.lastRefill = now;
if (state.tokens >= 1) {
state.tokens -= 1;
return { allowed: true, remaining: Math.floor(state.tokens) };
}
return { allowed: false, retryAfter: (1 - state.tokens) / refillRate };
}Lazy refill is what makes this cheap: no cron, no per-key timers, just arithmetic on two stored values whenever a request arrives.
Walkthrough: capacity 5, refill 1 token/sec
Trace a single key with capacity = 5 and refillRate = 1/sec. The bucket starts full. The client fires five requests in the first half-second (a burst), then keeps knocking.
| Time (s) | Elapsed since last | Refilled | Tokens before | Request? | Verdict | Tokens after |
|---|---|---|---|---|---|---|
| 0.0 | — | — | 5.0 | yes | allow | 4.0 |
| 0.1 | 0.1 | +0.1 | 4.1 | yes | allow | 3.1 |
| 0.2 | 0.1 | +0.1 | 3.2 | yes | allow | 2.2 |
| 0.3 | 0.1 | +0.1 | 2.3 | yes | allow | 1.3 |
| 0.4 | 0.1 | +0.1 | 1.4 | yes | allow | 0.4 |
| 0.5 | 0.1 | +0.1 | 0.5 | yes | deny | 0.5 |
| 1.5 | 1.0 | +1.0 | 1.5 | yes | allow | 0.5 |
At t = 0.5 the bucket holds only 0.5 tokens — less than the 1 a request costs — so it's denied and the response carries Retry-After ≈ 0.5s. One second later at t = 1.5, lazy refill has added a full token, the balance clears 1, and the next request goes through. The burst of five was absorbed instantly; after that the client is paced to the 1/sec refill rate. That's the whole point of the bucket: reward accumulated quiet with a burst allowance, then throttle to the steady rate.
Making it atomic across many servers
One node with a local bucket is easy. The real system has 50 gateway nodes that must share one budget per key, and that's where correctness breaks. If two nodes both read tokens = 1, both subtract, and both write back tokens = 0, they've allowed two requests against a one-token balance. That's a lost update — a classic read-modify-write race.
The fix is to make read, refill, decide, and write one atomic operation. Store the state in Redis and run the logic inside a Lua script via EVAL. Redis executes a script single-threaded, start to finish, with no other command interleaving — so the whole check is indivisible without any explicit lock:
-- KEYS[1] = rl:{user}:{endpoint} ARGV = capacity, refillRate, now, cost
local bucket = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])
local tokens = tonumber(bucket[1]) or capacity
local ts = tonumber(bucket[2]) or now
tokens = math.min(capacity, tokens + (now - ts) * rate) -- lazy refill
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) + 1) -- reclaim idle keys
return { allowed and 1 or 0, tokens }Two details matter. The key is namespaced as rl:{user}:{endpoint} so each user's limit on each endpoint is independent. And the EXPIRE sets a TTL just longer than the time to fully refill an empty bucket — once a key is idle long enough that its bucket would be full anyway, Redis evicts it and reclaims the memory. With millions of keys, that TTL is what keeps the working set bounded.
Deep dive: don't let Redis become the bottleneck
Now the harder version. Fifty nodes enforcing a global 1,000 req/s per user limit, all hitting one Redis for every request, is a recipe for turning Redis into a hotspot — and every request now pays a network round trip.
Two escapes:
- Local budgets with periodic sync. Give each node a slice of the global budget — 20 req/s each across 50 nodes — served from local memory, and reconcile with Redis every ~100ms to rebalance unused allowance toward busy nodes. The hot path never touches the network; only the background sync does. The cost is a small, bounded imprecision at the edges of a window.
- Shard the keys. Partition limiter keys across a Redis Cluster by
hash(user_id). No single node owns all the traffic, and capacity scales horizontally with the cluster.
For the tightest latency, colocate a Redis replica in the same availability zone as the gateway so the round trip is ~0.3ms, use one Lua script per check (a single round trip, not several), and keep persistent pooled connections so you never pay a TCP handshake on the hot path. For ultra-hot keys, cache the allow verdict in a per-process LRU for a tiny window (say 10ms) so a burst of requests skips the network entirely — again trading a sliver of accuracy for speed.
Deep dive: fail-open or fail-closed?
When Redis is unreachable, the limiter must still answer, and the choice is a product decision, not just an ops toggle:
| Behavior | On limiter failure | Protects | Risks |
|---|---|---|---|
| Fail-open | Allow the request | Availability | Backends exposed to overload during the outage |
| Fail-closed | Reject (429/503) | Backends | User-visible outage tied to the limiter |
Most public APIs fail open, because a limiter outage shouldn't cascade into a full API outage — but they pair it with a small in-memory fallback bucket per node so a failure caps worst-case damage instead of removing all limits, and they wrap the Redis client in a circuit breaker so a flaky Redis doesn't drag every request into a timeout. Pick the behavior per operation: POST /payments might justify fail-closed, while GET /search almost never does.
Deep dive: tiered limits that hold together
Real APIs stack limits: per-user 100/min AND per-tenant 10k/min AND global 1M/min, all enforced on the same request. The danger is partial application — you decrement the user bucket, then discover the tenant bucket is empty, and now you've charged a token for a request you rejected.
Evaluate all applicable buckets inside one Lua script, cheapest and narrowest first. Do a two-phase check-then-commit: first confirm every bucket has room, and only then decrement them all. If any single level is exhausted, reject and decrement nothing. Because the whole thing runs atomically in Redis, there's no window where one bucket is spent and another rejects — the state stays consistent.
How this shows up in interviews
Rate limiter is a warm-up-to-medium system design question, and interviewers use it to see whether you reach for a familiar datastore before stating requirements. The strong signal is starting with the key, the rule, and the 429 contract, then choosing token bucket and saying why (bursts, O(1) memory) rather than reciting all four algorithms.
The follow-ups are predictable: "how do you make the counter correct across servers?" (atomic Lua script, Redis single-threaded execution), "what if Redis goes down?" (fail-open with a local fallback and a circuit breaker), and "how do you keep it under a millisecond?" (colocated replica, one round trip, local caching for hot keys). Walk one request end-to-end, name Redis as the source of truth, and state the one trade-off — accuracy for latency — you'd reverse if the workload demanded exactness.
Further learning
- Rate Limiting: Token Bucket, Leaky Bucket, Sliding Logs — Tech Dummies walks through each algorithm visually.
- Sliding Window Rate Limiting: Design and Implementation — Arpit Bhayani derives the sliding window counter and its memory trade-off in detail.
- Practice this topic on YeetCode — step through the design interactively.
Related designs that reuse these ideas: Design a Key-Value Store (the storage layer under the limiter), Design a Notification System, Design a Chat System, and Design a News Feed.
FAQ
Why is token bucket preferred over fixed window for API rate limiting?
Fixed window counters reset on a clock boundary, which lets a client push up to twice the intended rate across the seam — 100 requests at 11:00:59 and another 100 at 11:01:00 is 200 in one second under a "100/min" fixed window. Token bucket has no boundary to exploit because it refills continuously based on elapsed time, and it costs only two numbers per key (tokens and last-refill timestamp) versus the per-request timestamp storage a sliding window log needs. It also tolerates natural client burstiness, which is usually what you want from a general API limit.
How do you keep a rate limiter correct across many servers?
Store each bucket's state in a shared store like Redis and run the read-refill-decide-write logic as a single atomic operation, not as separate commands from the application. In Redis, that means a Lua script executed with EVAL: Redis runs scripts single-threaded from start to finish, so no two nodes can interleave and cause a lost update where both read the same token count and both decrement it. Without atomicity, 50 nodes racing on one key will allow more requests than the limit permits.
What happens to the rate limiter if Redis goes down?
You choose in advance between fail-open (allow the request) and fail-closed (reject it). Most public APIs fail open, because a limiter outage should never cascade into a full API outage, but they back it with a small per-node in-memory fallback bucket so limits don't vanish entirely, plus a circuit breaker so a slow Redis doesn't drag every request into a timeout. High-stakes endpoints like payments may justify fail-closed instead. The right answer is per-operation, and it's a product decision about which failure is more acceptable.
How can a rate limiter add less than a millisecond of latency?
Keep the state store close and the round trips minimal: colocate a Redis replica in the same availability zone as the gateway for a ~0.3ms round trip, do the entire check in one Lua script so it's a single hop rather than several, and hold persistent pooled connections to skip TCP handshakes. For extremely hot keys, cache the allow/deny verdict in a per-process LRU for a short window (around 10ms) so a burst of requests answers from local memory and never touches the network, accepting a tiny, bounded imprecision in exchange for the speed.
How do you enforce per-user, per-tenant, and global limits at the same time?
Evaluate every applicable bucket inside one atomic script, checking the narrowest and cheapest limit first, and use a two-phase approach: confirm all buckets have capacity before decrementing any of them. If even one level is exhausted, reject the request and decrement nothing. Running this atomically prevents the inconsistent state where you've already spent a token from the user bucket when the tenant bucket turns out to be full, which would otherwise leak allowance on rejected requests.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.