Caching in system design series: 1. Multi-level cache and counters · 2. Rate limiting
Rate limiting caps how many requests a “subject” (user, API key, IP) may send in a period of time, to stop abuse and protect the systems behind it. This post compares five algorithms on the same example, builds a distributed token bucket on Redis, and answers the question “which algorithm should I pick?”
1. Where to put the rate limiter, and what to limit by
Key idea: the closer to the edge, the cheaper (API gateway, Nginx), but business limits (pricing plan, API type) need to live in the gateway or inside the service.
- By subject: API key, user id, IP (for requests that aren’t logged in), or a combination (user + endpoint).
- By layer: Nginx
limit_reqdoes coarse blocking by IP; the gateway (Spring Cloud Gateway, Kong) limits by API key and plan; the service limits expensive actions (sending an OTP: 3 times per 10 minutes). - Response:
429 Too Many RequestswithRetry-After, plus headers showing the remaining quota (RateLimit-Limit,RateLimit-Remaining,RateLimit-Reset) so clients can throttle themselves.
The running example in this post: a limit of 10 requests/minute per API key.
2. Five algorithms
Key idea: the algorithms differ in three ways: how they handle bursts at the boundary, how much memory they need per key, and whether requests have to wait.
2.1. Fixed window counter
One counter per minute, rl:{key}:{minute}; INCR it, and if it’s > 10, reject; the key expires after 60 s. Cheap and easy, but a client that sends 10 requests at 00:59 and 10 at 01:00 gets 20 requests through in 2 seconds.
2.2. Sliding window log
Store the timestamp of every request in a ZSET; on each request, remove entries older than 60 s and count. Perfectly accurate, but memory grows with the number of requests (10 timestamps per key; with a limit of 10,000/minute that’s 10,000 elements per key).
2.3. Sliding window counter
Keep the counters for the previous minute and the current one, and estimate:
estimate = count_this_minute + count_previous_minute × (share of the previous minute still inside the window)
At second 18 of the current minute (30% of the way in), with 8 requests in the previous minute and 3 in this one: estimate = 3 + 8 × 0.7 = 8.6 < 10 → allow. More accurate than fixed window, still just two numbers. The error comes from assuming the previous minute’s requests were spread evenly; Cloudflare reports a very small error on real traffic.
2.4. Leaky bucket
Requests go into a fixed-size queue; a worker takes them out at a fixed rate (10/minute). When the queue is full, reject. The output is very even, which fits when the backend can only handle a fixed rate (for example a third-party API). The downside: requests wait in the queue, so latency goes up; a message queue is a natural way to build it.
2.5. Token bucket
A “bucket” holds at most capacity tokens and is refilled at rate tokens per second. Each request takes one token; with no tokens left, reject. You only store two numbers: tokens left and the time of the last refill; when a request comes in, you top up tokens for the time that has passed.
| Fixed window | Sliding log | Sliding counter | Leaky bucket | Token bucket | |
|---|---|---|---|---|---|
| Memory / key | 1 number | N timestamps | 2 numbers | a queue | 2 numbers |
| Burst at the boundary | ×2 gets through | no | small | no | yes, up to capacity |
| Requests must wait | no | no | no | yes | no |
| Even output | no | no | no | very even | fairly even |
3. A distributed token bucket on Redis
Key idea: many gateway instances must share one bucket, so the state lives in Redis. Reading, computing and writing must happen inside one Lua script so there’s no race.
If the client GETs the token count, computes in Java and then SETs it, two instances can both read “1 token left” and both allow the request. Lua runs atomically on Redis (Redis executes commands one at a time), so it solves this. WATCH/MULTI (Redis’s optimistic locking) also works, but you have to retry on conflict; Lua is simpler and faster.
-- KEYS[1] = rl:{apiKey} ARGV: rate (tokens/s), capacity, now_ms, requested
local rate, cap, now, req = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])
local s = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or cap
local ts = tonumber(s[2]) or now
tokens = math.min(cap, tokens + (now - ts) / 1000 * rate) -- top up
local allowed = tokens >= req
if allowed then tokens = tokens - req end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate * 1000) + 1000)
return { allowed and 1 or 0, tostring(tokens) }
Note: take now from Redis (redis.call('TIME')) rather than from the caller, so clock skew between instances doesn’t break the math.
Memory estimate: each key is a small hash of ~100 bytes. 10 million active API keys ≈ 1 GB, which fits one Redis. Load: 200K requests/s through the gateway means 200K script calls/s, more than one node can do (~50–80K commands/s), so use Redis Cluster; keys are per API key, so they spread evenly across slots.
Fetching tokens in batches and local limits
One round-trip to Redis per request adds ~0.5–2 ms, and Redis load equals gateway load. Ways to cut it:
- Batch fetching: an instance calls the script with
requested = 20, keeps 20 tokens in memory and serves 20 requests without calling Redis. When they run out, it fetches a new batch. The cost: an instance may hold tokens it never uses (the global limit drifts a little), so keep batches small relative tocapacityand give them a short expiry. - Evenly split local limits: N instances, each limiting
limit / Nin memory with Guava or Bucket4j. No Redis needed, but it’s wrong when the load balancer distributes unevenly or the number of instances changes. - Two layers: local for coarse blocking (cheap DDoS protection), Redis for precise per-plan quotas.
Java libraries: Bucket4j (token bucket, with Redis/Hazelcast/JCache backends), Resilience4j RateLimiter (per-period limits, inside one JVM), Guava RateLimiter (smooth token bucket inside one JVM; acquire() blocks and waits, so it behaves like a leaky bucket if misused). Spring Cloud Gateway ships a RequestRateLimiter that uses a Redis + Lua token bucket.
4. Designing it in an interview
Key idea: present it in this order: requirements (what to limit by, how accurate), algorithm, where state lives, the request path, and failures.
flowchart LR
C[Client] --> G[API Gateway]
G -->|Lua script| R[(Redis Cluster)]
G -->|allow| S[Service]
G -->|429 + Retry-After| C
P[(Plans table)] -.->|cached config| G
Things worth saying without being asked:
- Per-plan quota config lives in the DB, cached in the gateway, and changes without a deploy.
- Multi-region: one Redis per region, split the quota per region or accept some drift; global sync on every request is too slow.
- Logs and metrics: blocked requests per key and endpoint, to spot buggy clients or attacks.
- Clients should retry with exponential backoff + jitter on a 429, and respect
Retry-After.
Exercises
Exercise 1: Rate limiting a public API with several plans
Task: an API has 3 plans: Free 60 requests/minute, Pro 1,000/minute, Enterprise 10,000/minute with a burst of 2,000. There are 5 million API keys and a peak of 150K requests/s through 30 gateway instances. Pick the algorithm, parameters, storage, and what to do when Redis is slow.
Solution to Exercise 1
- Algorithm: token bucket for every plan. Free:
rate = 1/s,capacity = 60. Pro:rate ≈ 16.7/s,capacity = 1,000. Enterprise:rate ≈ 167/s,capacity = 2,000(the burst in the contract). - Storage: Redis Cluster, key
rl:{apiKey}. Memory: 5M × ~100 B ≈ 500 MB. Load of 150K commands/s → 3–4 masters (each ~50K scripts/s), one replica per master. - Cutting load: Enterprise calls a lot → fetch tokens in batches of 50 per instance; Free/Pro call the script on every request (few requests per key).
- When Redis is slow: 10 ms timeout, circuit breaker opens at > 50% errors in 10 s; while open, use local Bucket4j with a
limit / 30quota. Fail-open for reads, fail-closed for endpoints that cost money (sending SMS). - Response:
429, aRetry-Aftercomputed from the time needed to get 1 token, plus the quota headers.
Remember
- Explain why fixed window lets through double at the boundary, and how the sliding window counter estimates.
- Compare leaky bucket and token bucket: which one makes requests wait, which one allows bursts.
- Write the core of the token bucket Lua script and explain why it has to run inside Redis.
- Know two ways to cut round-trips to Redis and what they cost.
- Decide fail-open or fail-closed for each kind of endpoint.
Interview questions
Mid
What’s wrong with a fixed window?
Bursts at the boundary: a client piles requests at the end of one window and the start of the next, and gets nearly double the limit through in a very short time.
A sliding window counter or a token bucket reduces the problem while still needing only a few numbers per key.
How do token bucket and leaky bucket differ?
A token bucket limits the average rate but allows bursts up to capacity and never makes requests wait; a leaky bucket queues requests and drains them at a fixed rate, giving even output but higher latency.
Token bucket suits user-facing APIs. Leaky bucket suits a backend that can only take a fixed rate, for example calling a partner limited to 100 requests/s.
Why is building a rate limiter with GET then SET on Redis wrong?
Two instances read the same old value, both decide to allow, and both write, so more requests get through than the limit (a read-modify-write race condition).
Use one atomic command (INCR for a fixed window) or a Lua script for multi-step algorithms; WATCH/MULTI also works but needs retries.
Senior
Design a distributed rate limiter for an API gateway at 200K requests/s.
A token bucket per API key, state in Redis Cluster, read-compute-write in one Lua script; add token batches and local limits to depend less on Redis.
Estimate: 200K scripts/s needs 3–4 masters. Quota config is cached in the gateway. When Redis fails: short timeout, circuit breaker, fall back to local limits; choose fail-open/closed per endpoint. Return 429 with Retry-After, and measure blocked requests.
How do you rate limit across several regions?
Don’t sync across regions on every request (too slow); split the quota per region, or let each region limit on its own and sync counters asynchronously, accepting a small drift.
If the quota is a billing contract, reconcile precisely from usage logs afterwards, not with the real-time limiter.
A slow Redis rate limiter is pushing up p99 for the whole API. What do you do?
Make fewer calls and cap the wait: fetch tokens in batches, a timeout of a few ms, a circuit breaker, and a local limit when Redis doesn’t answer in time.
Also check: hot keys (one API key carrying most of the load lands on one slot), heavy scripts, the network between gateway and Redis. For a hot key, give it a local limit or split its bucket.
Useful phrases for interviews
- “Rate limiting protects downstream services from abusive clients.”
- “A token bucket allows short bursts up to its capacity.”
- “A leaky bucket smooths output to a constant rate.”
- “Fixed windows let through a burst at the boundary.”
- “We throttle free-tier keys to sixty requests a minute.”
- “The Lua script makes the check-and-decrement atomic.”
- “For read endpoints we fail open if Redis is down.”
- “OTP sending fails closed because each SMS costs money.”
- “Each plan has its own quota stored in the database.”
- “Clients should retry with exponential backoff after a 429.”
Notes based on the System Design course (Ronin Engineer), rewritten in my own words.