Design a Rate Limiter

Understanding the problem

This is the design most teams reach for first when they want to protect something, so it shows up early and often in a senior round. The idea is small enough to state in a sentence and deep enough to fill an hour. A rate limiter guards a service from abuse and from accidental overload. Think of a client stuck in a retry loop, a scraper hammering an endpoint, a paid tier trying to spend more than it bought. The interviewer is rarely testing whether you know what a token bucket is. They are testing whether you can keep one limit correct when the service is a fleet of instances and the thing counting the requests can itself fail.

The Cisco angle

At a networking and infrastructure company, rate limiting is a control-plane primitive they build into the products they sell, not a toy prompt. A firewall polices flows. An API gateway in front of a security cloud or a monitoring service caps how hard any tenant can push. The dashboard API behind a cloud-managed network hands out a request budget per key, and the path-monitoring API does the same. So an interviewer here has almost certainly shipped or operated a limiter, and a generic token-bucket recital gets probed fast. The two places they push are the ones that separate a diagram from a system. Keeping the count exactly right when many instances share one limit. And deciding what the limiter does at the worst moment, when its own counter store is unreachable and traffic is still arriving. Get those two right and the rest follows.

Functional requirements

Keep the core tight and let the interviewer widen it. There are four jobs. First, decide allow or reject for every incoming request, fast, before it reaches the service. Second, enforce a limit per identity, usually per API key or client id, sometimes per IP for anonymous traffic. Third, support tiers, because a free caller does not share one number with a paying customer or an internal service. Fourth, when a request is rejected, return a 429 with a Retry-After so a well-behaved client backs off instead of hammering harder. One requirement carries more weight than it looks. The limit is global across the fleet, not per instance, so the count has to be shared.

Non-functional requirements

Reason each target from what the limiter is for. Added latency leads, because this thing sits in the hot path of every single request, so whatever it spends is spent on all of them. A budget under a millisecond is the goal, small enough to vanish against the work the service itself does. Correctness comes next, and here it means one thing: the limit holds across the whole fleet. A client with a hundred-per-second budget can't quietly collect a hundred from each of ten instances. Then availability, and this is the sharp one. The limiter guards the service, so if the limiter falls over it must not take the service down with it. That forces a decision, fail-open or fail-closed, that we come back to. Last, the numbers can be slightly soft. Letting a few requests over the line during a race is usually fine; being exact to the single request rarely is what matters.

Bank this slack now: approximate is often good enough. A limiter exists to stop abuse and overload, not to meter a billing charge to the exact request. If a client rated at a hundred a second occasionally gets a hundred and three because two instances raced, nothing breaks. That tolerance lets a limiter keep a small local cache and touch the shared store a little less often, trading a sliver of exactness for a lot of latency and load. We will spend that slack deliberately later, on local pre-checks and on the sliding-window approximation. Where it does not apply, on an endpoint that costs real money or mutates real state, we tighten back up and pay for exactness.

• ~100K/sec requests through the limiter. Every one pays a limit check, so the check has to be cheap in latency and in load. Illustrative teaching figure, not an audited count.
• < 1 ms added-latency budget per check. Small enough to disappear against the service's own work. The limiter is invisible on the happy path or it is a problem.
• ~1M keys registered clients. Roughly a hundred thousand active in any window, each needing a tiny scrap of counter state. Storage is trivial here.
• ~100 bytes state per active key. A token count and a timestamp. The store's op rate is the pressure, not the bytes it holds.

Sizing the check

Put the numbers on the board before the boxes, and derive them out loud, since a good interviewer redoes the arithmetic with you. Treat every figure as an illustrative teaching estimate. Say the fronted APIs peak at a hundred thousand requests a second. Every one of those requests hits the limiter first, so the limiter does a hundred thousand checks a second, all day and all night. That single fact sets the tone. The check has to be cheap in both latency and load, because it happens on everything, not on a sampled slice.

Now size the state, and watch where the pressure actually lands. A limit is enforced per key, and the state for one key is tiny. For a token bucket it's a couple of numbers, the tokens left and the instant they were last refilled, call it a hundred bytes. Say a million keys are registered and a hundred thousand are active in any given window. A hundred thousand keys at a hundred bytes is ten megabytes. Even all one million at once is a hundred megabytes. Storage is a rounding error. The pressure is somewhere else, and you should say where. It's the op rate against the shared store: a hundred thousand reads-and-writes a second aimed at a handful of hot keys, plus the network hop each one costs on the request path.

• The check rate: ~100K checks/sec. one per request. The limiter is in the hot path of everything, so the per-check cost, not the bytes stored, is the whole game.
• State size: ~10 MB active. a hundred thousand keys at ~100 bytes each. Memory is trivial. A rate limiter is not a storage problem.
• Store ops: ~100K ops/sec. if every check is a round trip to a shared counter, that is near the ceiling of a single store node, which is why hot keys and sharding come up.
• Added latency: < 1 ms target. a network round trip to the store is ~0.5 ms and up, enough to double a fast endpoint's latency, so you co-locate or you cache.

Two lines in that grid set the agenda. The check happens on every request, so its latency and its load on the counter store are the whole problem, not the bytes it stores. And a shared store touched a hundred thousand times a second is where correctness and hot keys collide. So the design keeps a few things true at once. The check stays under a millisecond. The count stays correct across every instance. And the limiter degrades to something safe when its store is unreachable. Each deep dive below is one of those.

The set-up

Core entities

Name the objects before drawing anything. Four carry this design, and the one to pin down first is the rule, because everything else is in service of enforcing it.

Pin the stores next, because the interviewer will ask where each piece lives. The counters live in a fast in-memory store, Redis, keyed by client and rule. Every request does a read-modify-write on a single tiny key, which is exactly what an in-memory store is built for. The limit rules live in a small durable config store the limiter loads and caches in process, since there are only a few and they change rarely. There is no big database here and no queue. A rate limiter is a decision on the request path, not a data pipeline, so adding storage it does not need only adds latency it cannot afford.

API

Keep the surface thin. The limiter is mostly invisible, a stage the request passes through, so its real interface is the decision it returns and the header it sets when it says no. There is also a small admin surface for the rules. Reference these by name in the deep dives.

One of these carries the design, and it is the first one. The allow-or-reject check runs on every request and has to finish in well under a millisecond. Everything hard about the limiter hides inside that one line. Where does the counter live, how does the count stay correct across instances, and what does the check return when the counter store is unreachable? The Retry-After on the reject path is the small detail that separates a limiter that calms traffic from one that amplifies it. Reject without it and clients retry in a tight loop, turning your defense into a second wave of load.

High-level design

Follow one request through. A Client sends a call, and it arrives at the API gateway + limiter before the service ever sees it. The limiter resolves the caller's identity, loads the matching Limit rules (cached in process), and does the real work: a read-modify-write against the Counter store to see whether this caller has budget left. If it does, the request passes to the Protected service and a token is spent. If it does not, the limiter stops the request right there and returns a 429 with a Retry-After. The diagram colors each box by role (blue for the client, violet for the gateway and the service, green for the two stores), and the walkthrough reuses the same tags.

1) The request arrives at the limiter first. A Client makes an ordinary API call, and the API gateway + limiter intercepts it before the Protected service sees it. The limiter resolves the caller's identity from the API key or client id on the request. Everything downstream keys off that identity, so getting it right, and not letting one caller pose as many to multiply its budget, is the quiet precondition for the whole design.

2) The rule is loaded, cheaply. The limiter looks up the caller's Limit rules: which tier, what rate, how much burst. Because there are only a handful of rules and they change rarely, the gateway caches them in process, so this step is a memory read and not a network call. The interviewer rarely lingers here, and that is the point of caching it. One less thing on the hot path.

3) The counter check is the real work. The limiter does a read-modify-write against the Counter store for this caller: how many requests or tokens are left in the current window, decrement, decide. This one operation is where the design lives. It has to be atomic, so two instances checking the same key at the same instant cannot both think there is room. And it has to be fast, because it happens on every request. The first two deep dives are both about this line: what the counter math should be, and how to make it correct across the fleet.

4a) Allowed: the request passes through. If the caller has budget, the limiter lets the request continue to the Protected service and records the spend. From the client's point of view nothing happened. The check added a fraction of a millisecond and got out of the way. That invisibility on the happy path is a requirement, not a nicety, because the happy path is almost all of the traffic.

4b) Rejected: a 429 with a Retry-After. If the caller is over its limit, the limiter stops the request at the gateway and returns a 429 with a Retry-After telling the client when its budget refills. The service never sees it. The Retry-After matters more than it looks. It is what turns a rejected client into a patient one, instead of one that retries in a tight loop and makes the overload worse.

5) When the counter store is unreachable. The one path the diagram does not draw is the failure path, and it is the most important call in the design. If the Counter store is down or slow, the limiter cannot do its check, and it has to decide in that instant whether to allow the request anyway (fail-open) or reject it (fail-closed). That decision, and the clock and hot-key problems that ride alongside it, is the last deep dive.

Technology choices

Naming the box is the easy part; the work is picking a concrete tool, defending why its class fits, and knowing how it breaks under this exact load. Put a common pick in each slot, and expect every follow-up to come out of the failure modes.

• Counter store is an in-memory data store: Redis, because the access pattern is a read-modify-write on one tiny key, millions of times a second, and an in-memory store serves that in microseconds. To make it correct, do the whole check inside a Lua script that Redis runs atomically. The read, the refill math, the decrement, and the decision happen as one indivisible step, and no two instances can race on the same key. The failure story is the store itself going down, which is the fail-open versus fail-closed decision, and a hot key overloading one shard, which pushes you toward local pre-checks and key sharding.
• The limiter runs inside an API gateway (Envoy or NGINX, or a managed cloud gateway), its natural home because the gateway already terminates every request and already knows the caller. Putting the limit there means rejected traffic never reaches the service or even its own connection pool. The failure mode to plan for is the gateway fleet scaling out: more instances means more concurrent hitters on the same hot key, which is why the shared-counter correctness cannot be hand-waved.
• The Limit rules live in a small config store (a Postgres table, a config service, even a versioned file) that the gateway loads and caches in process. Rules are few and change rarely, so this is not on the hot path. Get propagation right. When a tier's limit changes, every gateway instance should pick it up within seconds, so the cache carries a short TTL or a push invalidation rather than living forever.
• For the counter math itself, the default is a token bucket held as a couple of fields per key. It is the practical choice because it bounds the sustained rate while still allowing a controlled burst, which is how real traffic actually behaves. A sliding-window counter is the approximate alternative when you want smoother enforcement without storing every request. Both are a few bytes of state and an O(1) check, which is what keeps the limiter cheap on the hot path.

The Cisco angle

Reach for Redis with a Lua script here and be able to say why the script matters, because at an infrastructure company the interviewer knows the naive version has a race. A plain read-then-write against a shared counter (read the count, add one, write it back) is two round trips with a gap in the middle. Under real concurrency two gateway instances read the same value, and both allow a request that should have pushed the caller over. Folding the whole operation into one atomic script closes that gap. Redis hands you the atomic primitive, and a correct distributed limiter is still yours to build. Deciding what to make atomic, how to keep the round trip cheap, and what to do when Redis itself is unreachable is the design, and that is the part they are testing.

Potential deep dives

The deep dives are where the rest of the score gets decided. A rate-limiter round almost always pushes on the same three corners. Which counting algorithm do you pick and why, how do you keep one count correct across a fleet, and what does the limiter do when its own store fails? The middle one is the correctness bar an infrastructure company reaches for first. The last one is the judgment call they most want to watch you make.

1) The counting algorithm: from fixed windows to a token bucket

Start with how you actually count, because the naive version has a flaw the interviewer will find in about thirty seconds. The job sounds simple: allow a client up to N requests per window, reject the rest. The trouble is what "per window" means. A fixed clock window is the obvious reading and the wrong one, and walking from there to a token bucket is the arc the round wants to see. Show the counter math at each step, because that is where the flaw and the fix both live.

2) One limit across a fleet: the shared counter

Now put that algorithm behind a load balancer, because that is where a clean single-machine limiter quietly stops being correct. The service is not one process. It is many gateway instances, and a client's requests land on whichever one the balancer picks. If each instance counts on its own, the limit multiplies by the number of instances, which is not the limit anyone asked for. This whole dive is about making N instances enforce one number, and doing it without a round trip on every request wrecking the latency budget.

The Cisco angle

Networking and infrastructure interviewers listen for the distributed-counter correctness bar. It separates a limiter that works on a laptop from one that works behind a load balancer. Anyone can draw a token bucket. The senior signal is naming, unprompted, that a read-then-write against a shared counter races under concurrency, and reaching for a single atomic operation to close the gap. The reason it lands here is that this company runs fleets. The gateway fronting a monitoring API or a security cloud is dozens of instances. "Roughly a hundred a second" won't do when the limit protects a control plane or gates a paid tier. Walk from local counters to a shared store to one atomic script, and say what each step fixed and what it cost. That's the exact path their own systems took.

3) When the limiter fails: fail-open, clock skew and hot keys

The last dive is the one that separates a design from a system, and it starts with an uncomfortable question: what does the limiter do when its own counter store is down? This is not a rare hypothetical. Redis has a bad minute, the network to it hiccups, a failover is in progress, and in that window the limiter cannot do its check. It still has to answer every request, right now, allow or reject. There is no third option and no time to think. How you answer defines the whole system's behavior at its worst moment.

Two edges ride alongside the failure question, and the first is time. A token bucket refills based on elapsed seconds, and a sliding window is defined by "the last sixty seconds," so both depend on a clock. The moment the state is shared and many instances touch it, whose clock counts? If each gateway stamps the bucket with its own wall clock and the clocks disagree by even a little, the refill math drifts and the limit wobbles. The clean fix is to make the store the single source of time. Do the refill math inside the atomic script using Redis's own clock, so every instance reads the same "now" and no one's local skew leaks into the count.

The second edge is the hot key. Limits are per client, and clients are not equal. One big customer, or one abusive one, can send a huge share of all traffic against a single counter key. That concentrates load on whatever Redis shard owns that key, and a hundred thousand ops a second aimed at one slot can hot-spot a node while the rest sit idle. The mitigations stack. Pre-check locally so most requests never reach the shared key. Lean on the token lease from the last dive so a hot client is served from a local bundle. And if one key is still too hot, split it into a few sub-counters across shards and sum them, trading a little accuracy for spread. A hot key is where the abstract "shared counter" meets the physical reality that one key lives on one machine.

• Store is down: fail open, mostly. allow ordinary traffic through unchecked so a limiter blip never becomes a service outage; fail closed only on the few endpoints where an unlimited burst is dangerous.
• Local fallback: degrade, do not vanish. a small in-process approximate limiter catches the worst abuse while the shared store is unreachable, so failure means a looser limit, not no limit.
• Clock authority: one clock, not many. do the refill math with the store's own clock inside the atomic script, so no instance's skew wobbles the limit.
• Hot key: pre-check and shard. serve hot clients from a local lease and split a too-hot key across shards, so one client's key is not the whole system's bottleneck.

The Cisco angle

The fail-open call is the moment a networking company is really weighing your judgment, because they have lived the failure where a safeguard took down the thing it guarded. A limiter that fails closed on everything is the classic self-inflicted outage: the protection layer has a bad minute and rejects traffic to a healthy service. Fail open for the traffic where a brief unlimited window is survivable, which is nearly all of it. Fail closed for the handful of endpoints where an unlimited burst costs real money or breaks real state. And keep a local approximate limiter so a store outage degrades the limit rather than removing it. Say you decided this per endpoint ahead of time instead of finding out during the incident.

What is expected at each level

This design has less surface than a full data platform, which raises the bar on getting its few hard parts exactly right. Cisco keeps this round light below senior. At senior and above it becomes a genuine, level-gating discussion that often starts on a system you've shipped before moving to a prompt like this one. Picture the rungs as a gradient: a correct single-node limiter at mid, the distributed-counter correctness owned at senior, and the failure judgment carried at staff.

Mid-level engineer

Lean toward breadth, call it eighty to twenty. Land one coherent design: requests pass through a limiter at the gateway, the limiter checks a counter per client against a rule, and it returns allow or a 429 with a Retry-After. Know the algorithms and be able to say why a fixed window is not enough and why a token bucket is the usual default, with its rate and its burst. The phase that earns the pass is scale. When the interviewer says there are ten instances behind a load balancer, reason toward a shared counter store rather than local counting. A correct limiter you can defend, with the interviewer drawing out the harder corners, clears this rung.

Senior engineer

Depth takes over now, about sixty to forty, and this is the rung the round is built around. Raise the hard facts yourself. Derive the check rate out loud, note that the state is tiny but the store is hit on every request, and use that to justify an in-memory counter store and a sub-millisecond budget. Make the distributed-correctness call without being asked: a shared counter alone still races under concurrency, so the read-modify-write has to be one atomic operation, a Lua script in Redis. Flag the round-trip cost and reach for a local token lease to cut it. Reaching a near-complete design whose algorithm and shared-counter correctness and latency you handled on your own is the bar here.

Staff and beyond

Here depth runs through the whole picture, roughly forty to sixty. Own the failure story end to end. When the counter store is down, the limiter still has to answer. Fail open for ordinary traffic and fail closed only where an unlimited burst is dangerous, with a local approximate limiter as the backstop. Carry the edges too, the store as the single clock so skew cannot wobble the limit, hot keys kept off one shard with local leases and sub-counters. Hold the algorithm and the shared-counter correctness and the failure behavior as three separate levers, and know which bit of slack you are spending at each. You steer, and the interviewer nudges rather than rescues. The bar is keeping the check under a millisecond and the count correct across the fleet through every refinement, and having decided the failure behavior on purpose before the failure.