System design interview guide
Rate Limiter System Design Interview: Counting Requests Correctly Across a Fleet
A rate limiter is one of the few components that touches every single request before your real work begins. At the scale of a payments API or an edge network, that means tens or hundreds of thousands of decisions per second, each of which has to finish in well under a millisecond or it becomes the bottleneck it was meant to prevent. Cloudflare has described analyzing 400 million requests from roughly 270,000 distinct sources when validating their rate limiting accuracy, which gives a sense of the volume a real limiter sees.
The job sounds trivial, count requests per key and reject once the count crosses a limit, but almost everything hard is hidden in that sentence. You have to decide what a key is (user, IP, API key, or a tuple of endpoint and user), where the check runs (client, gateway, or service), and which algorithm to use (fixed window, sliding window log, sliding window counter, leaky bucket, or token bucket), each with a different memory and burst profile. The moment you run more than one limiter node, the counter has to live in shared state, usually Redis, and the read-modify-write becomes a race condition that lets requests slip through unless you make it atomic with a Lua script or an atomic INCR. Then you decide what happens when the shared store is slow or down, fail open and let traffic through, or fail closed and reject. On top of that you owe the caller a clean contract: a 429 status, a Retry-After header, and headers that tell them how many calls remain. A good answer treats the algorithm as the easy part and spends its time on atomicity, propagation delay, burst handling, and the failure modes.
Asked at: Asked at Stripe, Cloudflare, Amazon, Google, Uber, and most companies that run a public API or an API gateway. It shows up both as a standalone design question and as a subcomponent inside larger designs like an API gateway, a payments system, or a public developer platform.
Why this question is asked
Interviewers like this problem because it looks small enough to finish in 45 minutes yet it forces you through the full stack of distributed systems reasoning. A weak candidate names token bucket and stops. A strong candidate notices that as soon as there are two limiter processes sharing one counter, the naive get-then-set has a race, and they can explain how an atomic Redis operation or a Lua script fixes it. The problem tests whether you understand consistency versus latency (do you check the counter synchronously on the hot path or propagate counts asynchronously and accept some overshoot), whether you think about failure (what happens when Redis is unreachable), and whether you care about the client contract (429, Retry-After, limit and remaining headers). It rewards precise thinking about a component that is deceptively simple.
Requirements
Always clarify these in the first 5 minutes of the interview. Do not start drawing boxes until both lists are agreed.
Functional requirements
- Allow or reject each incoming request based on a configured limit per key, for example 100 requests per minute per API key.
- Support multiple key dimensions: per user, per IP address, per API key, and per endpoint, including composite keys like endpoint plus user.
- Support multiple rules layered together, such as a per-second burst limit and a per-day quota on the same caller.
- Return a clear rejection contract: HTTP 429 Too Many Requests with a Retry-After header and headers reporting the limit, remaining count, and reset time.
- Allow limits to be configured and changed at runtime without a redeploy, ideally per plan tier or per customer.
- Handle short bursts gracefully where the caller's average rate is under the limit but requests arrive clustered together.
- Expose counters and rejection metrics so operators can see who is being limited and tune thresholds.
- Support allowlisting and denylisting so trusted internal callers or abusive sources can bypass or be hard-blocked.
Non-functional requirements
- Very low added latency, on the order of a millisecond or less, since the check runs on every request before real work starts.
- High availability: the limiter must not become a single point of failure that takes down the API it protects.
- A defined behavior when the shared counter store is unavailable, chosen deliberately as fail-open or fail-closed.
- Accuracy that matches the business need; strict billing quotas need exactness, abuse protection tolerates small overshoot.
- Horizontal scalability so limiter capacity grows with API traffic without hotspotting a single counter.
- Memory efficiency in the counter store, since there can be millions of distinct keys, each needing bounded state.
- Correctness under concurrency: two nodes checking the same key at the same instant must not both consume the last unit.
Back-of-envelope scale estimates
Show your math. Pulling numbers from thin air signals you have not thought about the load.
Peak request rate through the limiter
~200,000 requests/sec (estimate)
Assume a large public API serving 10 billion requests/day. 10e9 / 86,400 ~= 116,000 req/sec average. Peak is usually 1.5x to 2x average, so roughly 200,000 req/sec. Every one of these hits the limiter first. Derived, illustrative.
Redis operations per second
~200,000+ ops/sec (estimate)
With a synchronous check, each request is at least one atomic Redis operation (INCR or a Lua eval). At 200,000 req/sec that is 200,000+ Redis ops/sec, which a single Redis node can handle but sits close to the practical ceiling, motivating sharding by key. Derived.
Distinct rate limit keys tracked
~10-50 million keys (estimate)
If the API has 5 million active API keys and you also limit per user and per endpoint, the number of live counter keys can reach tens of millions. Each with a short TTL so expired keys evict automatically. Derived from assumed customer counts.
Memory per counter key
~50-100 bytes (estimate)
A fixed window counter is a small integer plus key overhead. A token bucket stores two values (tokens and last-refill timestamp) in a Redis hash. A sliding window log stores a timestamp per request and is far heavier, which is exactly why it is avoided at scale. Roughly 50-100 bytes for the counter forms.
Counter store memory footprint
~1-5 GB (estimate)
30 million live keys times ~100 bytes ~= 3 GB, comfortably in RAM for a small Redis cluster. Short TTLs keep this bounded because idle keys expire rather than accumulate. Derived from the key count and per-key size above.
Latency budget for the check
< 1 ms target (estimate)
The limiter runs before useful work, so its budget is a fraction of the total request latency. An in-memory Redis lookup on the same network is typically a few hundred microseconds, which fits. If the check ever exceeds a few milliseconds it becomes the dominant cost and defeats the purpose.
High-level architecture
A request arrives at the edge and hits the rate limiting layer before it reaches application logic. That layer is usually middleware inside an API gateway or reverse proxy, or a thin library inside each service. The limiter first derives the key for this request from whatever dimension the rule cares about, for example the API key from the Authorization header, the client IP, or a composite of user plus endpoint. It looks up the current count or token state for that key. In a single-node deployment this state can live in local memory, but any real system runs many limiter processes behind a load balancer, so the state lives in a shared store, almost always Redis, reached over the local network. The critical detail is that the read of the current count and the write of the new count must happen as one atomic operation, either with an atomic INCR plus EXPIRE or, for token bucket and sliding window logic, a Lua script that runs the whole read-compute-write cycle inside Redis in a single round trip. The script returns an allow or deny decision plus the remaining budget and a reset time. If the decision is allow, the request continues to the application and the limiter attaches headers describing the remaining quota. If the decision is deny, the limiter short-circuits and returns 429 with a Retry-After header, never touching the backend. If Redis is unreachable, the limiter applies its configured failure policy, typically fail open so a limiter outage does not take down the API, and it emits a metric so operators know accuracy is degraded.
In a real interview, sketch this on the whiteboard before diving into any single box.
Core components
Walk through each service. The interviewer wants to hear what each one owns, not just the names.
Rule configuration store
Holds the limits themselves: which key dimension, what threshold, over what window, for which plan tier or customer. This is read-mostly and can be cached aggressively in each limiter process, refreshed periodically so limits can change at runtime without a redeploy. Keeping rules out of code lets support raise a customer's limit without a release.
Key extractor
Turns a raw request into the identity the rule limits on. It reads the API key, resolves the authenticated user, or falls back to client IP, and it composes tuples like endpoint plus user when a rule needs them. Getting this wrong is a common bug: limiting on a proxy's IP instead of the real client IP lets a whole network share one bucket, or breaks everyone behind a NAT at once.
Counter store (Redis)
The shared, in-memory home for per-key counters or token state, chosen for microsecond reads and writes and built-in key expiry via TTL. Redis is where the atomicity is enforced through INCR or Lua scripts. It is sharded by key using consistent hashing so that a given key always lands on the same node and load spreads evenly across the cluster.
Decision engine (algorithm)
The logic that turns counter state into an allow or deny, implementing fixed window, sliding window counter, leaky bucket, or token bucket. In a distributed setup this logic runs inside Redis as a Lua script so the whole read-compute-write is atomic. It returns the verdict plus the numbers needed for the response headers.
Response and header builder
Produces the caller-facing contract. On allow it adds headers reporting the limit, the remaining count, and the reset time so well-behaved clients can self-throttle. On deny it returns 429 with a Retry-After header telling the client how long to wait. A clear contract turns rate limiting from a mystery into something clients can integrate against.
Fallback and failure policy
The safety layer that decides what happens when the counter store is slow or down. It wraps every Redis call in a timeout and a try-catch, and on failure applies the configured policy, usually fail open, sometimes with a coarse local in-memory limiter as a degraded backstop. This is what keeps a Redis incident from becoming an API outage.
Metrics and observability
Emits counts of allowed and rejected requests broken down by key, rule, and reason, plus latency of the check itself and the health of the counter store. This lets operators see who is hitting limits, spot abuse, tune thresholds, and detect when the limiter has silently failed open and is no longer enforcing anything.
Data model
Pick the right store per table. Justify each choice with the access pattern, not by reflex.
rate_limit_rulesrule_idkey_dimensionlimitwindow_secondsplan_tierConfiguration, not hot-path counters. key_dimension is one of user, ip, api_key, or a composite. Read-mostly and cached in every limiter process. Changing a row changes the effective limit without a deploy.
fixed_window_counter (Redis)redis_keycountttlredis_key is like ratelimit:{apikey}:{window_start}. A single integer incremented with INCR, with EXPIRE set to the window length so the key self-cleans. Simplest and most memory efficient, but allows a 2x burst at window boundaries.
token_bucket_state (Redis hash)redis_keytokenslast_refill_tsttlStores two values per key in a hash: current token count and the timestamp of the last refill. On each request a Lua script computes how many tokens have dripped back since last_refill_ts, adds them, then tries to remove one. Handles bursts naturally up to bucket capacity.
sliding_window_counter (Redis)redis_key_currentredis_key_previouscount_currentcount_previousKeeps the count for the current fixed window and the previous one. The effective rate weights the previous window by how much it overlaps the trailing window. Far cheaper than storing every timestamp while staying close to a true sliding window.
sliding_window_log (Redis sorted set)redis_keymember_timestampscore_timestampA sorted set of request timestamps per key. Exact but expensive: memory grows with request volume and you must ZREMRANGEBYSCORE old entries on every call. Reserved for low-volume, high-value limits where exactness matters.
Deep dives
These are the conversations the interviewer is steering you toward. Practice each one until you can talk through it without notes.
Choosing the algorithm: fixed window, sliding window, leaky bucket, token bucket
Fixed window is the cheapest: one integer per key per time window, incremented atomically, expired by TTL. Its flaw is the boundary problem, a caller can send the full limit in the last second of one window and again in the first second of the next, so it permits close to double the intended rate across a boundary. The sliding window log fixes accuracy by storing every request timestamp and counting only those inside the trailing window, but its memory grows with traffic and it is slow, so it does not scale. The sliding window counter is the practical middle ground: keep the current and previous fixed-window counts and weight the previous count by how much the trailing window overlaps it, which Cloudflare showed approximates a true sliding window within a few percent while using two integers. Leaky bucket models a queue that drains at a constant rate, which smooths bursty input into a steady output and is what Figma runs in production for their API. Token bucket, used by Stripe, stores a token count that refills at a fixed rate up to a cap, letting callers burst up to the bucket size while enforcing a long-run average. The interview-strong move is to name the burst behavior each one gives and pick token bucket or sliding window counter for most real APIs.
Where the limiter sits: client, gateway, or service
Client-side limiting is a courtesy, not enforcement, because you do not control the client and a malicious one ignores it, though it usefully reduces wasted calls from well-behaved SDKs. The common enforcement point is the API gateway or reverse proxy, which sees every request, already terminates auth, and can reject before any backend is touched, which protects the whole fleet from a single chokepoint. Per-service limiting inside each microservice is useful when different services have different capacity and you want to protect a specific slow dependency rather than the front door. Many real systems layer these: a coarse limit at the gateway for abuse protection plus finer per-service limits for capacity protection. The tradeoff is that the closer to the edge you limit, the earlier you shed load and save work, but the further from the service you are, the less you know about that service's real-time health. A frequently missed point is that a gateway limiter needs the counter to be shared across all gateway instances, otherwise each instance enforces the limit independently and the effective limit is multiplied by the number of gateways.
Distributed counting with Redis and atomicity
The instant you have more than one limiter process, the counter cannot live in local memory or each process enforces its own private limit. It moves to a shared store, and Redis is the default because it is in-memory, single-threaded per shard, and gives sub-millisecond reads and writes with TTL-based expiry. The subtle part is that a naive sequence of GET count, check against limit, then SET count+1 is not atomic: two processes can both read the same value, both decide there is room, and both write, so the limit is exceeded. For a simple counter this is solved by INCR, which is atomic and returns the new value in one operation, paired with EXPIRE to bound the window. For token bucket or sliding window logic that needs several reads and a computation, you push the whole thing into a Lua script that Redis runs atomically as one command, so no other client can interleave. Stripe describes implementing their limiters on Redis for exactly this low-latency, centralized-counting reason. You also shard by key with consistent hashing so a given key always maps to the same node, which both keeps the counter consistent and spreads load; Cloudflare put Twemproxy in front of Memcached to do this key distribution.
Race conditions and why token bucket is not naturally atomic
Figma wrote candidly about this: the token bucket algorithm has a tiny memory footprint and elegant burst behavior, but its Redis operations are not atomic out of the box. Reading the current token count, computing the refill, and writing back the decremented count is a read-modify-write, and in a distributed environment two servers can interleave those steps. If one token remains and two requests arrive at once, both can read one token, both decide to allow, and both decrement, so you let through more than the limit permits, meaning the limiter runs too lenient. The fixes are to make the whole operation atomic with a Lua script, or to fall back to a simpler algorithm like a fixed window counter whose single INCR is inherently atomic. Figma weighed adding Lua, which means introducing another language to the codebase, against switching algorithms, and that tradeoff between operational simplicity and algorithmic elegance is exactly the kind of judgment interviewers want to hear. The general lesson is that any multi-step counter update in a shared store is a race unless you force it into a single atomic unit.
Synchronous checks versus asynchronous counter propagation
The strictest design checks and updates the shared counter synchronously on the request path, so the decision reflects the true global count, at the cost of a network round trip to Redis on every request. That is fine when Redis is on the local network and the limiter is co-located, but at very high rates the round trip and the load on a single hot key become the bottleneck. An alternative is to keep counts locally per node and propagate them asynchronously, either each node enforces a fraction of the global limit (global limit divided by node count) or nodes periodically sync their local counts to a central store. This removes Redis from the hot path and scales beautifully, but it trades accuracy: because propagation lags, the global count can temporarily overshoot the limit, and uneven traffic across nodes makes the divide-by-N approach either too strict or too loose. The right choice depends on the stakes. A hard billing quota wants the synchronous, exact path. Abuse protection that only needs to be roughly right can accept the eventually-consistent, higher-throughput path. Naming this tension, exactness versus throughput and latency, is a signal of maturity.
Handling bursts and smoothing traffic
Real traffic is bursty, so an algorithm's burst behavior matters as much as its average. A pure fixed or sliding window rejects everything once the count is reached, which is fine for a hard cap but harsh for clients that legitimately batch. Token bucket is popular precisely because it separates two knobs: the refill rate sets the sustained throughput, and the bucket capacity sets how large a burst you tolerate. A caller who has been idle accumulates tokens up to the cap and can spend them in a burst, then is throttled back to the refill rate, which matches how many clients actually behave. Leaky bucket takes the opposite stance: it drains at a constant rate regardless of how bursty the input is, so it smooths spiky input into a steady stream to the backend, which is what you want when the thing you are protecting cannot absorb spikes. The design question is whether you want to permit bursts (token bucket) or forcibly smooth them (leaky bucket), and the answer depends on whether the downstream can handle a spike or needs a flat rate. Stripe's use of token bucket reflects an API that wants to allow reasonable bursts while capping the average.
Failure modes: fail-open versus fail-closed and the client contract
Because the limiter sits in front of everything, its own failure is dangerous, so you must decide in advance what happens when the counter store is slow or unreachable. Fail-open means that on a Redis error you let the request through, accepting that during the incident the API is unprotected but staying available; Stripe emphasized wrapping the limiter so that a bug in the limiter code or a Redis outage would not take down request handling. Fail-closed means you reject on error, which protects a fragile backend from an unchecked flood but turns a limiter outage into a full API outage, appropriate only when uncontrolled traffic is more dangerous than downtime. Most public APIs fail open and page an operator, sometimes backed by a coarse local in-memory limiter as a degraded fallback. Separately, whatever the verdict, you owe the caller a clean contract. On rejection, return HTTP 429 Too Many Requests with a Retry-After header giving seconds to wait, and on every response include headers reporting the limit, the remaining count, and the reset time so disciplined clients throttle themselves instead of hammering and retrying. A good contract plus sensible retry-with-backoff on the client side prevents the limiter from creating the very thundering herd it exists to stop.
Trade-offs to discuss
Every senior interviewer expects you to surface at least 3 of these. Pick the decisions, state the alternatives, and justify your choice.
Token bucket versus fixed window counter
Token bucket allows controlled bursts and enforces a smooth long-run average, but its multi-step update is not atomic and needs a Lua script to be correct under concurrency. Fixed window is a single atomic INCR and trivially cheap, but permits nearly double the limit across a window boundary. Choose token bucket when burst behavior matters and you can afford the script; fixed window when simplicity and raw speed win and the boundary overshoot is tolerable.
Sliding window log versus sliding window counter
The log stores every timestamp and is exact, but memory grows with traffic and each check does range cleanup, so it does not scale. The counter keeps only two integers and weights the previous window, approximating the log within a few percent as Cloudflare measured. Use the counter almost always; reserve the log for low-volume limits where exactness is worth the cost.
Synchronous Redis check versus asynchronous local counting
A synchronous check against a shared counter is exact but puts a network round trip and a hot key on the request path. Local counting with periodic sync removes Redis from the hot path and scales far better, but lags mean the global limit can overshoot. Pick synchronous for hard quotas, asynchronous for high-volume abuse protection that tolerates slack.
Fail-open versus fail-closed on counter store failure
Fail-open keeps the API available during a limiter or Redis outage but leaves it unprotected. Fail-closed protects a fragile backend from an unchecked flood but converts a limiter outage into an API outage. Most public APIs fail open and alert; systems where an unbounded flood is catastrophic fail closed.
Limiting at the gateway versus inside each service
Gateway limiting sees all traffic and rejects early, protecting the whole fleet from one place, but is coarse and unaware of each service's real-time health. Per-service limiting protects specific slow dependencies with local knowledge but duplicates logic and misses cross-service abuse. Layering both, coarse at the gateway and fine per service, is common.
Redis shared counter versus per-node local limiter
A shared Redis counter gives one consistent global view but is a dependency on the request path and a potential hotspot. A per-node local limiter has no external dependency and the lowest possible latency, but with N nodes the effective limit is N times the configured value unless you divide the limit, which is fragile under uneven traffic. Shared state is the default for correctness; local is a fallback or a deliberate throughput optimization.
How Rate Limiter actually does it
Stripe published a detailed account of running rate limiters and load shedders on Redis, using a token bucket per user plus concurrent-request limiters, and stressing that the limiter must fail open so a bug or a Redis outage never takes down request handling. Cloudflare described building rate limiting for millions of domains using an approximation of the sliding window (current plus previous window counts, weighted by overlap), storing counters in Memcached fronted by Twemproxy that consistent-hashes keys across nodes, and validated the approximation against 400 million requests with only about 0.003% of requests wrongly allowed or limited and roughly a 6% average difference from the true rate. Figma wrote openly about picking between token bucket and simpler algorithms, explaining that token bucket's Redis operations are not atomic and create a race that makes the limiter too lenient, and that they weighed a Lua script against just using a fixed window; Figma's public API today runs a leaky bucket. These are three independent, primary engineering accounts that map directly onto the algorithm, atomicity, and failure-policy decisions in this design.
Lessons to study before this interview
If any of these topics are fuzzy, the interviewer will catch it. Each lesson is 15 to 60 minutes with diagrams, code, and a quiz.
Related system design interview questions
Practice these next. They lean on the same core building blocks as Rate Limiter.