A system design interview guide to building a rate limiter: why you need one, where it sits, the classic algorithms and their tradeoffs, and how to make it correct and fast in a distributed setting.
Student edition · start with the guarantee
Turn a quota into an explicit admission rule, choosing whether it limits bursts, trailing-window traffic, or a long-run rate.
Correctness contract: A request is admitted only after atomic accounting under the chosen algorithm. State whether attempts or admitted requests consume quota, and whether failure is fail-open or fail-closed.
Basic HTTP, databases, and programming are assumed. Specialized terms are explained below. Named products motivate the problem; this is an educational design, not a claim about their current internals. Capacity numbers are illustrative decimal payload estimates, not benchmarks. Add indexes, protocol overhead, replicas, headroom, and failure capacity before provisioning.
A rate limiter controls how many requests a client may send to a service in a given window of time. When a client stays under its allowance, requests pass through to the service; when it exceeds the allowance, the limiter rejects or defers the extra requests instead of letting them reach the backend. This sounds simple, but a good design has to answer several harder questions: which algorithm decides what "too many" means, where the limiter physically lives, how it stays accurate when many requests arrive at once, and how multiple limiter instances agree on a single count. This guide walks through each of those decisions in the order an interview usually takes them.
Each definition includes a concrete example and the condition under which the mechanism is useful. You can read this guide without opening another guide.
Token bucket
A counter of available tokens that refills at rate r up to capacity B. An admitted request spends its cost. The bucket permits an initial burst but bounds admissions over duration T by approximately B+rT.
Example. B=10, r=1 token/s admits 10 calls immediately, then about one per second. It can admit 70 calls over 60 seconds, so this is not a hard 60-calls-per-minute rule.
Limit. A distributed hard limit needs atomic, durable shared accounting or safely partitioned budgets. Clamp clock rollback, validate costs, and state whether rejected attempts consume tokens.
Time windows
Tumbling windows are fixed, nonoverlapping intervals such as [12:00,12:01). Sliding windows cover a trailing duration and may overlap. Half-open boundaries assign an event exactly once to a tumbling interval.
Example. Two allowed calls at t=0 fall out of a 60-second trailing window at t=60, under the convention (now-60,now]. Fixed calendar buckets instead reset at their boundary.
Limit. A fixed window may allow nearly twice its limit across a boundary. A weighted sliding counter is an approximation; a timestamp log gives an exact count only within its stated clock and admission policy.
Atomic Redis scripts
Redis executes a script without interleaving other commands on that server. It can read state, decide, and update it as one isolated operation instead of a racy GET followed by SET.
Example. A script checks tokens, refills, and decrements before another request can observe the intermediate state.
Limit. Isolation is not rollback or replicated durability. A script error may leave earlier writes applied; asynchronous failover may lose state. Redis Cluster multi-key operations require a shared hash slot.
Wall and monotonic clocks
A wall clock maps to civil/epoch time and can jump because of correction. A monotonic clock measures elapsed time locally without wall-clock jumps, but its origin is not a shared global epoch.
Example. Use an epoch timestamp to label an event and a monotonic deadline to bound how long a process waits for the next usable timestamp.
Limit. Neither establishes causal order across machines. Monotonic readings cannot be compared between hosts or assumed to survive reboot with the same origin.
Backpressure and load shedding
Backpressure tells an upstream producer that the downstream stage cannot accept more work. Buffering delays that signal; shedding deliberately rejects or drops lower-priority work when a bound is reached.
Example. A sink accepts 100 events/s while input is 150/s. A 1000-event queue fills in 20 seconds. The system must then block, reject, or apply its documented drop policy.
Limit. A finite queue cannot absorb an infinite outage. Prioritized messages still need hard quotas, deadlines, and bounded client queues; otherwise an exemption can exhaust the system.
Leases
Time-limited permission issued by an authority. Expiry lets new work proceed after a client stops renewing; it does not prove that the previous holder is dead or unable to act.
Example. A 30-second lease expires while A is paused for 45 seconds. B can acquire a new lease, but A can still wake up and send a delayed write.
Limit. Heartbeats improve recovery time, not safety by themselves. Compare-and-renew/delete must verify a unique acquisition token atomically, and protected effects need fencing or equivalent serialization.
1. Why Rate Limit
Rate limiting is one of those features that looks like a tax on legitimate traffic until the day it saves the service. There are four distinct reasons to add one, and a strong answer names all of them rather than just "to stop abuse."
Motivation
What it protects against
Abuse and attacks
Brute-force login attempts, credential stuffing, scrapers, and denial-of-service floods. Capping requests per client makes these attacks slow and expensive instead of free.
Cost control
Every request consumes CPU, bandwidth, and downstream calls — some of which are billed. A limiter keeps a single noisy client from running up the bill or exhausting a paid third-party quota.
Fairness
Without a limit, one heavy user can starve everyone else of capacity. Per-client quotas keep the service responsive for the majority during a spike from a minority.
Cascading failure protection
An overloaded service slows down, retries pile up, and the slowness spreads to its callers. Shedding excess load at the edge keeps the backend inside its safe operating range and stops a local overload from becoming an outage.
A useful framing for an interview: rate limiting is a form of load shedding. You are deciding, deliberately and cheaply, to reject a small amount of traffic now so that you do not lose all of it later when the system falls over.
2. Requirements and Clarifying Questions
Before drawing anything, pin down what kind of limiter you are building. The answers change the algorithm, the storage and even where the limiter lives.
Client-side or server-side? Assume server-side, since only that is enforceable.
Limit by what key? User ID, API key, IP address, or a mix. IPs are shared behind NAT and easy to rotate, so authenticated keys are fairer where you have them.
How many rules, and how flexible? One global limit, or per-endpoint and per-plan rules (for example, 5 login attempts per minute, 1,000 API calls per hour for free users)?
Scale? Requests per second at peak and number of distinct clients drive the memory and throughput numbers below.
Single region or global? A global limit across regions is much harder than one limit per region.
Hard or soft limit? Is it acceptable to let a few extra requests through (soft), or must the limit never be exceeded (hard)?
Functional requirements
Non-functional requirements
Decide allow/reject for each request against configurable rules.
Low latency: the check adds at most about a millisecond to each request.
Support several rule types (per user, per IP, per endpoint).
High availability: if the limiter breaks, the API must keep working.
Tell rejected clients why and when to retry (HTTP 429 + headers).
Accuracy: close to the configured limit, even with many limiter nodes.
Let operators change rules without a deploy.
Small memory: state per client should be a few dozen bytes.
3. Back-of-the-Envelope Estimation
Assume a large public API: 1 million requests per second at peak and 1 million clients active in any given minute. Each check is one round trip to the counter store. These are assumptions for practice, not facts about any real service.
Quantity
Working
Result
Counter-store operations
1 check per request at 1,000,000 req/s
1M ops/s
Throughput per Redis shard
a simple script per call, about 100k ops/s is a safe planning number
100k ops/s
Shards needed for throughput
1,000,000 ÷ 100,000
10 shards
Token-bucket memory
1M active keys × ~100 B (key + 2 numbers + Redis overhead)
~100 MB
Sliding-log memory (limit 100/min)
1M keys × 100 timestamps × ~64 B per sorted-set entry
~6.4 GB
Conclusion
Memory is small for counters; throughput sets the shard count. The sliding log costs 64× more memory here.
~10 shards, <1 GB
Why estimate at all?
The numbers tell you the design is dominated by operations per second, not storage. That points you to an in-memory store sharded by client key, and away from the sliding log for high-limit clients.
4. API and Data Model
The limiter has two interfaces: the hot-path check, and a rules API for operators.
# internal hot-path call made by the gateway on every request
allow(client_key, rule_id, cost=1) -> {allowed: bool, remaining: int, reset_after_s: int}
# operator API (rarely called, stored durably)
PUT /v1/rules/{rule_id} body: {"match": {"endpoint": "/login"}, "key": "ip",
"algorithm": "token_bucket", "capacity": 5, "refill_per_s": 0.083}
GET /v1/rules
DELETE /v1/rules/{rule_id}
Data
Where
Shape
Rules
Durable store (a database or config files), cached in each limiter node
rl:{rule}:{client} → {tokens, ts}, with a TTL of the time to refill a full bucket
Sliding log
Redis sorted set
rl:{rule}:{client} → {request_id: timestamp}
Tip
Put the rule ID in the key. Then one client can be under several limits at once (per second and per day, for example) without the counters colliding.
5. Where to Place the Limiter
Before choosing an algorithm, decide where the check runs. There are three common placements, and they trade enforceability against blast radius and reuse.
Client side. The client throttles its own requests before sending them. This is cheap and saves a round trip, but it is unenforceable — anyone can modify the client or forge requests — so it is at best a courtesy, never a security control.
Server side, inside the application. The service checks the limit as part of handling each request. This is enforceable and has full request context, but every service has to reimplement the logic, and the rejected request still pays for connection setup and routing before it is dropped.
Middleware or an API gateway. A dedicated layer in front of the services inspects every request and applies the limit before forwarding it. This is the usual choice: it is enforceable, it is shared by all backends behind it, and it sheds excess load early, before it reaches application servers. The cost is one more component to operate and a network hop.
For most designs you choose the gateway/middleware placement. It centralizes the rules, keeps the limiting logic out of every individual service, and rejects bad traffic at the cheapest possible point in the path.
6. Algorithms and Tradeoffs
The heart of the design is the algorithm that decides whether a given request is allowed. Five are worth knowing. They differ in how they track usage, whether they permit bursts, and how much memory and accuracy they cost.
Algorithm
How it works
Tradeoffs
Token bucket
A bucket holds up to N tokens and is refilled at a fixed rate. Each request removes one token; if the bucket is empty the request is rejected. Unused tokens accumulate up to the cap.
Simple, memory-cheap (two numbers per client), and allows short bursts up to the bucket size — which is often what you want. Two parameters (capacity and refill rate) to tune.
Leaking bucket
Requests enter a FIFO queue of fixed size and are processed ("leak") at a constant rate. A full queue means the request is dropped.
A leaky-bucket queue absorbs bursts up to its finite capacity, then schedules departures at the configured rate; excess is rejected. It smooths output by adding queueing delay.
Fixed window counter
Time is split into fixed windows (e.g. each minute). One counter per window per client; increment on each request, reject once it passes the limit, reset at the window boundary.
Trivial to implement and very cheap. Its flaw is the boundary burst: a client can send the full limit at the end of one window and again at the start of the next, briefly doubling the allowed rate across the boundary.
Sliding window log
Store a timestamp for every request in a sorted set. On each new request, drop timestamps older than the window, then count what remains; allow only if the count is under the limit.
Exact — no boundary artifact, the limit holds over any rolling window. But it stores one entry per request, so memory grows with traffic, making it expensive for high-volume clients.
Sliding window counter
A hybrid that approximates the log using just two fixed-window counters. It weights the previous window's count by how much of it still overlaps the rolling window.
Cheap like fixed window, but smooths out the boundary burst. Slightly approximate (it assumes requests were spread evenly in the previous window), which is acceptable for almost all uses.
The boundary burst. Each fixed window stays under its limit, yet the client sends twice the limit across the boundary.
The sliding window counter is worth spelling out, because its formula is the part interviewers most often ask you to derive. The estimated request count for the current rolling window is:
# count over the rolling window =
estimate = current_window_count
+ previous_window_count * overlap_percentage_of_rolling_window
# overlap_percentage = fraction of the previous fixed window# that still falls inside the rolling window right now
allow if estimate < limit
For example, with a one-minute window and a limit of 100: if the previous minute saw 80 requests, the current minute has 30 so far, and 25% of the previous window still overlaps the rolling window, the estimate is 30 + 80 × 0.25 = 50, which is under 100, so the request is allowed. As the rolling window advances, the previous window's weight shrinks toward zero, smoothly retiring its contribution instead of dropping it all at once like the fixed window does.
Cloudflare reported a low error rate for its measured traffic under a weighted sliding-window estimator. This is an empirical workload result, not a universal error bound or a hard trailing-window guarantee.
Token bucket in one picture
Think of a jar that holds 10 coins and gains one coin per second. Each request costs a coin. A client that was quiet for a while can spend all 10 at once (a burst), but over any long period it can never average more than one request per second. With capacity 10 and refill 1/s, the most a client can send in 60 seconds is 10 + 60 = 70.
7. Architecture with Redis
Put the pieces together. A request from the client hits the rate limiter middleware. The middleware looks up the rules that apply to this client and the counters tracking its recent usage, runs the chosen algorithm, and either forwards the request to the API servers or rejects it. The counters need to be read and written on every request, so they live in a fast in-memory store; the rules change rarely, so they are cached and refreshed in the background.
Rejected work returns 429 and is not also enqueued for a side effect. A bounded asynchronously accepted job returns 202 and an ID/status contract. Queueing and rejection are distinct outcomes.
The components are:
Rate limiter middleware. Sits in front of the API servers. For each request it identifies the client (API key, user ID, or IP), fetches the relevant counter and rule, applies the algorithm, and decides allow or reject.
Redis (counters). An in-memory key-value store holding the per-client counters. It is chosen because the limiter touches a counter on every single request: an in-memory store gives sub-millisecond reads and writes, and Redis ships with INCR and key expiration that map directly onto window counting.
Rules cache and workers. The limiting rules (which client gets which limit) are kept in a durable rules store. Background workers periodically load them into an in-memory cache next to the middleware, so the hot path never queries the database. A rule change propagates on the next refresh.
Choose and benchmark an atomic state store for the actual latency/throughput/consistency contract. Redis is a common option, not proof that every disk-backed database is unsuitable.
The fixed-window check in Redis is two commands — increment the counter for the current window, and set it to expire when the window ends:
function allow(client_id):
key = client_id + ":" + current_window() # e.g. "user42:1719356400"
count = redis.INCR(key) # create at 1 or bump existing
if count == 1:
redis.EXPIRE(key, window_seconds) # auto-clean old windows
return count <= limit
With a fixed-window key that includes the window start, a failed expiry can leak an old key; a later window uses a different key. If one reused key is used instead, missing expiry can affect admission. Make increment/expiry atomic and state the actual key scheme.
-- Fixed-window admitted-request counter. Key MUST include window-start.
-- ARGV: window TTL seconds, positive integer limit. Single Redis authority.
local ttl, limit = tonumber(ARGV[1]), tonumber(ARGV[2])
if not ttl or not limit or ttl < 1 or limit < 1 or
ttl ~= math.floor(ttl) or limit ~= math.floor(limit) or
ttl > 2147483647 or limit > 2147483647 then
return redis.error_reply("invalid window parameters")
end
local raw = redis.call("GET", KEYS[1])
local count = 0
if raw then count = tonumber(raw) end
if raw and (not count or count < 0 or count ~= math.floor(count) or count > 2147483647) then
return redis.error_reply("invalid stored count")
end
if count >= limit then return 0 end
count = redis.call("INCR", KEYS[1])
if count == 1 then redis.call("EXPIRE", KEYS[1], ttl) end
return 1
The token bucket needs the read-decide-write pattern, so the script matters even more. It stores the token count and the time of the last update, and refills lazily on each call instead of running a timer:
-- Educational Redis token-bucket script: one key, trusted authority timestamp.
-- ARGV: capacity, refill_per_second, now_ms, cost. Counts admitted work.
local function finite(x)
return x ~= nil and x == x and x ~= math.huge and x ~= -math.huge
end
local cap, rate = tonumber(ARGV[1]), tonumber(ARGV[2])
local now, cost = tonumber(ARGV[3]), tonumber(ARGV[4])
if not finite(cap) or not finite(rate) or not finite(now) or not finite(cost)
or cap <= 0 or rate <= 0 or cost <= 0 or cost > cap then
return redis.error_reply("invalid bucket parameters")
end
local old = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens, ts = cap, now
if old[1] or old[2] then
tokens, ts = tonumber(old[1]), tonumber(old[2])
end
if not finite(tokens) or not finite(ts) or tokens < 0 or tokens > cap then
return redis.error_reply("invalid stored bucket state")
end
local next_ts = math.max(ts, now)
tokens = math.min(cap, tokens + math.max(0, now - ts) / 1000 * rate)
local allowed = 0
if tokens >= cost then tokens = tokens - cost; allowed = 1 end
-- Do not expire before a future stored timestamp has caught up and refill is full.
local ttl = math.ceil(math.max(0, next_ts - now) + cap / rate * 1000)
if not finite(ttl) or ttl < 1 or ttl > 2147483647 then
return redis.error_reply("TTL outside this example's supported range")
end
redis.call("HSET", KEYS[1], "tokens", tokens, "ts", next_ts)
redis.call("PEXPIRE", KEYS[1], ttl)
return allowed
With capacity 10 and a refill of 1 per second, 15 requests at time 0 give 10 allowed and 5 rejected. Three more requests 2.5 seconds later find 2.5 tokens, so 2 are allowed.
Common mistake
Use a trusted per-key time authority and handle rollback even with NTP or Redis TIME. Clamp negative elapsed time, preserve a nondecreasing stored timestamp, and do not expire state before a future timestamp has caught up plus full-refill duration. Multi-key/cluster clocks and failover remain explicit assumptions.
Atomicity is the detail that separates a correct rate limiter from a leaky one. Any algorithm above can be made safe this way: do the entire "read counter, decide, update counter" step inside one atomic unit — a Lua script, a Redis transaction, or an equivalent — so concurrent requests cannot both slip through on a stale read.
8. Responding to the Client
When a request is rejected, the limiter returns HTTP 429 Too Many Requests (defined in RFC 6585). The status code alone is not enough; a well-behaved client needs to know its limit and when it can try again, so the limiter attaches headers to the response.
Header
Meaning
Retry-After
The standard HTTP header (RFC 9110). Seconds to wait, or a date, before retrying. Send it with every 429.
X-RateLimit-Limit
The maximum number of requests allowed in the window. A widely used convention, not a standard.
X-RateLimit-Remaining
How many requests the client has left in the current window.
X-RateLimit-Reset
When the window resets. APIs disagree on whether this is seconds-from-now or a Unix timestamp, so document which one you use.
The IETF has a draft that standardizes these as RateLimit and RateLimit-Policy header fields without the X- prefix. Some interview books call the retry header X-RateLimit-Retry-After; the standard name is plain Retry-After.
Returning these headers on allowed responses too — not just on rejections — lets a well-behaved client slow itself down before it hits the wall, which reduces the number of 429s the system has to generate in the first place.
9. Handling Exceeded Requests
A rejected synchronous request returns 429 Too Many Requests, with useful retry guidance such as Retry-After when a delay is known. That response means the requested operation was not accepted. A leaky-bucket queue may instead accept a bounded burst and schedule it later: if processing is asynchronous, return 202, a job ID/status endpoint, and idempotent retry semantics. Do not both enqueue an effect and tell the client it was rejected, inviting a duplicate retry.
Retries use capped backoff/jitter and an overall deadline. Important requests can have a reserved budget, but every class still needs a bound so priority cannot exhaust the service.
10. Distributed Challenges
Per-node state is simple but does not enforce one global quota: requests can reach different nodes, and fresh/restarted buckets can add allowance. For a hard shared quota, the admission decision and counter update need one atomic authority with a defined durability/failover policy.
In Redis, use a validated Lua script or an appropriate conditional transaction. MULTI/EXEC alone does not make a read outside the transaction plus a later write atomic; WATCH requires conflict detection and retry. A multi-key script in Redis Cluster must use keys in the same hash slot. Scripts are isolated but not rollback transactions, and a primary failure before replication can lose admitted usage.
Prefer a monotonic local clock for elapsed time when state stays in that process. Shared Redis timestamps use wall time; clamp negative elapsed duration and store max(previous_timestamp, now). Validate capacity>0, rate>0, and 0<cost≤capacity before mutating state. Redis TIME and NTP do not prove time never moves backward.
Regional preallocation can preserve an aggregate limit if a durable allocator grants disjoint budgets and no two holders can spend the same allocation. It sacrifices utilization and needs safe reclamation. Approximate local counters and periodic synchronization give soft limits; explicitly bound overshoot only under stated traffic, delay, and failure assumptions.
11. Failure Modes and How to Handle Them
Failure
What goes wrong
How to handle it
Redis is down or slow
Every request waits on the limiter, so the limiter becomes the outage.
Use a tight timeout (a few ms). Then fail open (allow) for most APIs, or fail closed (reject) for security-critical ones like login. A per-node local limiter can act as a rough backup.
Hot key
One huge client sends all its traffic to one Redis shard.
Give that client a local pre-check on each node, or split its counter across several keys and sum them.
Clock skew
Nodes disagree on the current window or refill time.
Sync clocks with NTP, or take time from Redis inside the script.
Bad rule pushed
A typo sets a limit of 0 and blocks everyone.
Validate rules, roll them out gradually, and keep a quick rollback.
Retry storm
Rejected clients retry at once and make overload worse.
Send Retry-After and ask clients to use exponential backoff with jitter.
Many regions
A global limit needs cross-region round trips on every request.
Enforce per region with a share of the global limit, and sync totals in the background. Accept small overshoot.
Interview signal
Saying "what happens when Redis is down?" before the interviewer asks is one of the strongest signals you can send. Name fail-open vs fail-closed and pick one for this API.
12. Tradeoffs and Alternatives
Option
Pros
Cons
Use when
Central Redis with Lua
Accurate; stateless limiter nodes
Network hop per request; Redis is a dependency
Default choice for most APIs
Local in-memory limiter per node
No network hop; no dependency
Limit is per node, so the real limit is N× the rule and varies as nodes scale
Rough protection, or as a first layer in front of Redis
Local counters, synced to a central store in batches
Few network calls; scales very high
Can overshoot between syncs
Huge traffic where a soft limit is fine
Off-the-shelf gateway (for example, Envoy's global rate limit service, cloud API gateways)
No code to write; battle-tested
Less flexible rules; vendor limits
Standard per-key limits
Worked example: a ten-token bucket
Start full with B=10 and refill r=1 token/s; each request costs one token.
Read top to bottom. The table below explains the state and guarantee at each step.
Step
State, calculation, and reasoning
1. Spend the initial burst
Ten simultaneous calls consume ten tokens; an eleventh at the same time is rejected.
2. Advance by three seconds
The bucket refills to three tokens, so three more calls can pass. Rejected requests do not spend tokens in this model.
3. Handle a backward timestamp
Clamp elapsed time to zero and preserve the stored timestamp as max(previous,now). Do not mint refill twice as the wall clock catches up.
4. Choose a failure policy
If a state-store outage falls back to a full local bucket on every server, the global quota becomes soft. For a hard limit, fail closed or allocate nonoverlapping durable budgets.
Check your understanding: Can this bucket admit 70 calls over 60 seconds?
Yes: the initial 10-token burst plus 60 refilled tokens. Use an exact trailing-window counter if the requirement is at most 60 admissions in every 60-second interval.
Run a small, testable model
Download concepts.py. It uses only the Python 3.10+ standard library. From the directory where you saved it, run:
python3 concepts.py bucket
python3 concepts.py test
Try changing capacity and refill rate. The assertions cover rejection, bounded refill, and clock rollback.
The program contains deterministic assertions and failure traces. It is a learning model, not a production service: it does not implement network consensus, distributed durability, authentication, or third-party delivery. Read its contracts and try changing an input before extending it.
Clarify: server-side, key type, rules, scale, hard vs soft limit, single region or global.
5–10 min
Estimate: ops/s and memory. Conclude that throughput decides the shard count.
10–20 min
Place the limiter in a gateway. Draw client → limiter → API, with Redis and a rules cache.
20–30 min
Compare algorithms. Pick token bucket (bursts OK) or sliding window counter (smooth), and say why.
30–40 min
Deep dive: atomic Lua script, key design, 429 and headers, drop vs queue.
40–45 min
Failures and scale: Redis down, hot keys, multi-region, monitoring of rejects.
14. Common Mistakes
Relying on client-side limits. Clients can be modified, so these are never a security control.
Using a plain GET then SET. Two requests read the same value and both pass. Use one atomic script.
Forgetting the TTL. Counters that never expire leak memory, or block a client forever after a crash.
Keying only by IP. Many users share one IP behind NAT, and attackers rotate IPs cheaply.
Not planning for limiter failure. A limiter with no timeout and no fail-open rule can take down the API it protects.
Returning 403 or 503 instead of 429. Clients and proxies treat these codes differently; 429 plus Retry-After is the clear signal.
15. Summary
A rate limiter is a sequence of decisions, each building on the last:
Question
Answer
Why limit at all?
To stop abuse, control cost, keep usage fair, and protect the backend from cascading overload.
Where does it run?
Usually as middleware or an API gateway in front of the services — enforceable, shared, and cheap to reject early.
Which algorithm?
Token bucket for bursts, leaking bucket for smooth output, fixed window for simplicity, sliding window log for accuracy, sliding window counter for a cheap, accurate compromise.
Where do counters live?
An in-memory store such as Redis, using INCR + EXPIRE for window counting, with rules cached separately and refreshed by workers.
How is it kept correct?
Make the read-decide-update step atomic with a Lua script so concurrent requests cannot both slip through, and set the TTL in the same script.
What if the limiter fails?
Short timeout, then fail open for most APIs and fail closed for security-critical ones.
What does the client see?
HTTP 429 plus Retry-After and rate-limit headers (Limit, Remaining, Reset) so clients can back off.
What about the extra requests?
Drop them on interactive paths; enqueue them on asynchronous paths where deferral is fine.
How do many nodes agree?
A centralized shared counter keeps nodes stateless and the limit consistent; atomic updates handle the races.
The recurring theme: rate limiting is cheap, deliberate load shedding. Pick the algorithm that matches your burst tolerance, keep the counters in a fast shared store, make every update atomic, and tell the client clearly when and how to come back.
16. Check Yourself
A fixed-window limiter allows 100 requests per minute. What is the most a client can send in any 2-second span?
Answer
200. It can send 100 in the last second of one window and 100 in the first second of the next. This is the boundary burst.
A token bucket has capacity 20 and refills 2 tokens per second. The client has been idle for an hour. How many requests can it send in the next 10 seconds?
Answer
About 40. The full bucket allows 20 at once, and 10 seconds of refill adds 2 × 10 = 20 more.
Previous minute: 60 requests. Current minute so far: 20. We are 40% into the current minute. Limit 70. Using the sliding window counter, is the next request allowed?
Answer
The previous window still overlaps 60% of the rolling window. Estimate = 20 + 60 × 0.6 = 56, which is under 70, so yes.
With a fixed-window key that includes the window start, a failed expiry can leak an old key; a later window uses a different key. If one reused key is used instead, missing expiry can affect admission. Make increment/expiry atomic and state the actual key scheme.
Your Redis cluster is unreachable. Should a login endpoint fail open or fail closed? What about a product search endpoint?
Answer
Login: usually fail closed (or fall back to a strict local limit), since it guards against brute-force attacks. Search: fail open, since blocking all searches hurts users more than a short period without limits.
Which algorithm would you pick to protect a downstream payment processor that must see a steady rate?
Answer
Leaking bucket. It smooths bursty input into a constant output rate.
17. Key Terms
Rate limit
The maximum number of requests allowed per key per unit of time.
Token bucket
A counter of available tokens that refills at rate r up to capacity B. An admitted request spends its cost. The bucket permits an initial burst but bounds admissions over duration T by approximately B+rT. Example and limits above.
Leaking bucket
A fixed-size queue drained at a constant rate. Smooths output; no bursts.
Boundary burst
The flaw of fixed windows: up to 2× the limit across a window edge.
Fail open / fail closed
When the limiter itself fails: allow all traffic, or reject all traffic.
HTTP 429
The "Too Many Requests" status code for rate-limited responses.
Lua script (Redis)
Server-side code Redis runs atomically, with no other command in between.
Load shedding
Backpressure tells an upstream producer that the downstream stage cannot accept more work. Buffering delays that signal; shedding deliberately rejects or drops lower-priority work when a bound is reached. Example and limits above.
18. Further Reading
Alex Xu, System Design Interview – An Insider's Guide, Vol. 1, chapter "Design a Rate Limiter".
Stripe engineering blog, "Scaling your API with rate limiters" (token buckets on Redis, load shedders).
Cloudflare blog, "How we built rate limiting capable of scaling to millions of domains" (the sliding window counter at scale).
RFC 6585 (HTTP 429) and RFC 9110 (the Retry-After header).
Redis documentation for INCR (its "rate limiter" pattern) and EVAL (Lua scripting).
