Design a Rate Limiter

1Clarifying the requirements#

Before I draw a single box, I want to know what we are protecting and from whom. Strong candidates sprint to "token bucket in Redis" in the first 30 seconds and skip the only questions that change the design. Here is how I would open:

Candidate: Are we limiting per user, per IP, per API key, or all three? Interviewer: Assume per API key for authenticated traffic. IP is a fallback for anonymous requests.

Candidate: Is this one service protecting itself, or a shared limiter that many services call? Interviewer: Shared. Treat it like an internal platform component. Dozens of teams will use it.

Candidate: When someone goes over the limit, do we drop the request or queue it for later? Interviewer: Drop it. Return a 429 with a Retry-After header. No queueing.

Candidate: How strict are we? If a user sends 101 when the limit is 100, is one extra a bug or a rounding error I can ignore? Interviewer: Small overshoot is fine under load. We care way more about low latency and never taking the whole API down. Accuracy is a soft goal.

What those answers just told me:

• That last line is the thesis of the whole design, so I say it to the interviewer: "Great, that one line unlocks everything." I write it at the top of the board and circle it.
• Soft accuracy means I can trade a little precision for a lot of speed, which rules out the heaviest consistency machinery.
• "Shared platform component" means the config path and the check path are different animals, and I must not let them share a code path.

Functional requirements

• Allow or reject each request against a configured limit, for example 100 requests per minute per API key.
• Support several rules at once (per second, per minute, per day) and different limits per plan tier.
• Signal clearly on rejection: HTTP 429, plus headers for the limit, remaining count, and when to retry.
• Let teams change rules without a redeploy.

Non-functional requirements

• Low latency. The limiter is in the path on every call, so my budget is a couple of milliseconds. If I add 50 ms to every call to save the API from overload, I have become the overload.
• Highly available. If the limiter falls over, the API must not fall over with it. Fail open.
• Horizontally scalable across many app servers and many regions.
• Roughly accurate. A tiny overshoot during a burst is acceptable.

2Back-of-the-envelope estimation#

Size it so you know the one thing that decides the architecture: does a single Redis node survive, or do I need a cluster, and is the pressure on bytes, on disk, or on operations per second?

Users and traffic.

• 50 million daily active API keys.
• Peak traffic of 500,000 requests per second across all services. I design for the peak, not the average, because a rate limiter exists precisely for the peak.
• Every incoming request hits the limiter exactly once, so the limiter does 500k operations per second at peak. Read and write are the same op here: a read-modify-write on a counter.

Storage.

• One small counter record per key per rule window: a key string plus a count and a timestamp, call it about 100 bytes.
• 50M keys x 3 active rules x 100 bytes = 15 GB of hot state.
• Window records expire fast (a per-minute counter lives 60 seconds then evaporates), so the working set at any instant is a rolling few GB, well under 15 GB.
• That fits in memory on a modest cluster, so I do not persist to disk or think about durability tiers.

Bandwidth.

• The payload is trivial: a key in, an allow or deny out, say 200 bytes each way.
• 500,000 req/s x 200 bytes = 100 MB/s, about 0.8 Gbps. A single modern NIC handles that.

The number that drives the design.

• 500,000 ops/sec on counters, with a per-request budget of a few milliseconds.
• It is not bytes, not disk, not storage. It is ops/sec and tail latency on a shared mutable counter.
• A single Redis instance tops out around 100k to 200k ops/sec for a Lua-scripted operation.
• So 500k alone tells me I need roughly a 4 to 8 node cluster before I even think about headroom.

3Core APIs#

The limiter is mostly an internal check call, with a small config surface alongside. The hot path is one call, and I want it to be one call on purpose.

POST /v1/ratelimit/check
Content-Type: application/json

{
  "key": "apikey_8h2k",
  "rules": ["per_minute", "per_day"],
  "cost": 1
}

{
  "allowed": true,
  "results": {
    "per_minute": { "limit": 100, "remaining": 42, "reset_at": 1762152060 },
    "per_day":    { "limit": 50000, "remaining": 48211, "reset_at": 1762214400 }
  }
}

Two design choices worth defending:

• cost lets a heavy endpoint count as more than one unit. A bulk export costs 10, a health check costs 1. Without it, teams fake it by calling the limiter 10 times, which turns my 500k ops into 5M. One parameter keeps the ops budget honest.
• The check and config paths never share code. The check path is 500k ops/sec and must be boring and fast. The config path is a handful of ops per day.

On rejection, the caller surfaces this to the end client:

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
Retry-After: 18

And a config endpoint teams use to set rules. Low traffic (a few writes a day across the whole company), so it is a plain CRUD service on a normal relational database:

PUT /v1/ratelimit/rules/premium_tier
{
  "per_minute": 1000,
  "per_day": 500000
}

4High-level design#

The spine is standard, so draw it fast:

• App servers call a thin limiter library.
• The library talks to a shared in-memory store for counters.
• A separate config path pushes rules out.
• The counter store is the heart of it.

Request flow.

• The gateway hands off to the limiter middleware.
• The middleware loads the rule from its local cache, then runs an atomic counter update in Redis.
• On the answer it either forwards to the backend or returns 429.
• Rules load from the config database, push into Redis, and cache locally in each middleware instance, so the common case touches nothing but the counter.

Why middleware, not a standalone service.

• One extra network round trip per request is the single biggest latency cost I can avoid, and a dedicated limiter service adds exactly that hop for nothing.
• The middleware makes one Redis call, and that call is the only remote dependency on the hot path.
• If an interviewer pushes for a standalone service, the only reason to pull it out is polyglot clients that cannot share a library, and even then I reach for a sidecar before a central service.

Here is the decision path on a single check:

The fail-open branch is deliberate.

• If Redis is unreachable or slow past my timeout, I allow the request rather than block real traffic over a limiter problem.
• That is a conscious call, not a default, and I defend it in the trade-offs because it is one of the two or three things a good interviewer pokes hardest.

5Data model#

Two stores, on purpose. The counter store is Redis and holds ephemeral, high-churn state. The rules store is a normal relational database and holds config that rarely changes.

• Mixing them puts rarely-changing config behind a store tuned for raw throughput.
• And it puts hot counters behind a store tuned for durability.
• Keep them apart.

Counter state (Redis). Not rows: a key per key-plus-rule-plus-window.

• The TTL does quiet heavy lifting: every counter key self-expires at the end of its window, so I never run a cleanup job and never pay for stale state.
• That is why the 15 GB from the estimate is really a rolling few GB at any instant: old windows delete themselves.
• For the sliding-window-log approach I use a sorted set of request timestamps instead of a plain counter. More on that in the deep dive, including why I usually do not pay for it.

Rules (relational DB). Low write volume, read often, cached everywhere.

• Rules fit in a few megabytes for the whole company.
• Every middleware instance caches the entire table in a local hash and refreshes every few seconds, so a rule lookup is a local memory read, not a DB query or even a Redis round trip.
• That is why the flow diagram loads the rule from local cache before it ever touches Redis.

6Deep dives#

6.1 Which algorithm, and why not a fixed window#

The algorithm choice is the first real content of this question. Naming the four is table stakes; knowing exactly where each one breaks is the signal.

The two I rule out, and why:

• Fixed window counter. One counter per key per calendar minute: a single INCR with a TTL, dead simple. The flaw is the boundary. 100 requests at 12:00:59 and 100 more at 12:01:00 lets 200 through in two seconds. For a traffic-smoothing limiter that is a real 2x burst straight through the seam.
• Token bucket. A bucket refills at a steady rate up to a cap; a request takes a token or is rejected. Great when you want short bursts on top of a steady average ("1000/min sustained but tolerate a quick spike to 1500"). I reach for this only if the interviewer says "allow bursts."

So I state the pick out loud and tie it to requirements.

• Sliding window counter for traffic smoothing at our scale.
• If we are 25% into the current minute, the estimate is current_window_count + previous_window_count * 0.75.
• It smooths the boundary spike without storing per-request timestamps, memory stays at one small record per key, and the error is bounded and small.
• Token bucket instead if bursts are a desired feature.

Now the part that trips people: the whole check has to be atomic.

• Two concurrent requests both read "99," both decide "allowed," both write "100," and 101 slipped through on a hard limit.
• INCR alone is atomic, but my sliding-window math is read-then-compute-then-conditionally-write, which is three operations.
• So I run the read, the math, and the write as a single Lua script that executes as one indivisible unit on the server.

6.2 The hot key problem#

This is where scale actually bites, and the part I spend the most time on, because it is the signature hard part of this question.

• Most keys are quiet, but a handful are not. One enterprise customer, or one abusive client hammering a single endpoint, sends a huge share of all traffic to one API key.
• Since I shard counters by key, that one key lives on exactly one Redis shard.
• That shard melts at 200k ops/sec while the other seven sit nearly idle.
• Sharding by key, the thing that saved me in the estimate, is exactly what sinks me here, because a single key cannot be split across shards by the default hashing.

Two defenses, used together, because they cover different cases.

• Local pre-check with a short-lived local counter. Each middleware instance keeps a tiny in-memory counter per hot key and syncs to Redis periodically, say every 100 ms. If a key is clearly over its limit, the instance rejects locally without touching Redis. A flood against one key gets absorbed at the edge across all instances and never concentrates on one shard. The cost is a little accuracy, but a key 10x over its limit does not need precision to reject.
• Sharded counters for the hottest keys. Split a hot key's counter across N sub-counters (rl:key:0 through rl:key:N), spread deliberately across shards, and sum on read. The write load fans out across the cluster instead of landing on one node. Reads now cost N ops and accuracy loosens slightly (sub-counters read at slightly different instants), which is fine given soft accuracy. The key move: I promote a key to sharded mode only when monitoring flags it as hot, so millions of normal keys stay on the cheap single-counter path.

The two defenses stack.

• The local pre-check kills obvious floods for free at the edge.
• The sharded counter handles the legitimately high-volume key that is still under its (large) limit and genuinely needs to be counted across the cluster.

6.3 Distributed accuracy across regions#

With app servers in multiple regions, you face a fork: one global counter store, or one store per region.

• A single global store means every check in Tokyo makes a cross-ocean call to a Redis in Virginia, roughly 150 ms round trip.
• That alone is 70x my entire latency budget. It is a non-starter for an in-path limiter.

So I keep a Redis cluster per region.

• A global "100 per minute" becomes "roughly 100 per region per minute."
• For the vast majority of limits that is completely fine, because the goal is protection against overload, not exact accounting.
• A customer across 3 regions getting up to 300/min instead of 100/min still cannot take the API down, which is the actual objective.

If a customer truly needs a hard global cap, reconcile async.

• A background job sums regional counts every few seconds and tightens each region's local allowance as the global total approaches the limit.
• That is eventually consistent and can overshoot briefly during the sync interval, which the requirements explicitly permit.
• What I would not do is pay for synchronous global consensus on a limiter: the cure costs more than the disease, adding cross-region latency to every request to prevent a bounded, brief overshoot the interviewer already called acceptable.
• Recognizing when not to reach for strong consistency is exactly the staff-level signal here, so I say it out loud.

7Bottlenecks and trade-offs#

Redis is the single dependency on the hot path.

• If it is slow, every request is slow. I mitigate with a connection pool, pipelining, a hard timeout of a few milliseconds, and fail-open on timeout.
• Fail-open is deliberate: fail closed and a Redis blip returns 429 to every user, so my safety component became the outage. A limiter outage should degrade protection, not availability.
• The sharp counter-argument: fail-open briefly lets abusers through during an incident. I accept that, because an attacker mid-attack during the exact few seconds Redis is unreachable is far smaller and rarer than a self-inflicted total outage on every hiccup.
• If the protected thing were a payment or auth endpoint where over-admitting is dangerous, I would fail closed for that specific rule. Context decides.

Atomicity vs throughput.

• The Lua script is atomic but runs single-threaded on one shard, because Redis executes scripts to completion without interleaving.
• That caps per-shard throughput at the 100k to 200k ops/sec range.
• The answer is more shards and the hot-key handling above, not a cleverer script. You scale this horizontally, never vertically.

Clock skew.

• Window math depends on time, and if app servers disagree on "now," boundaries wobble and a request lands in the wrong bucket.
• I lean on time computed inside Redis using the TIME command inside the script, so all window math uses one authoritative clock.
• I never trust a client-supplied timestamp for window placement.

Config propagation lag.

• Rules are cached locally and refreshed every few seconds, so a limit change takes a few seconds to land everywhere. Fine trade for keeping lookups off the network entirely.
• For an emergency (cutting off an abusive key right now), the config service pushes an invalidation over a pub/sub channel instead of waiting for the poll. Urgent changes are immediate, routine ones stay cheap.

Accuracy vs cost, restated.

• I chose sliding window counter over the log, per-region counters over a single global one, and local pre-checks for hot keys. Every one trades a little precision for latency, memory, or availability.
• That is exactly the trade the interviewer handed me in the requirements.
• If they said instead "billing depends on exact counts," I reverse several: sliding window log, synchronous reconciliation or a hard global store, fail closed, and I warn them up front about the latency and cost bill. The design is a direct function of that one requirement.

Anchor every trade-off to one requirement line, and the design writes itself.

8Summary#

The decisions that matter:

• Middleware at the gateway. One atomic Redis call on the hot path, no extra network hop. A standalone service only for polyglot clients, and even then a sidecar first.
• Sliding window counter. Smooth like a log, cheap like a fixed window. Token bucket if bursts are a desired feature.
• Atomic check via one Lua script, so concurrent requests can never both slip past the limit.
• Fail open. A limiter outage must never become an API outage, with the one exception of endpoints where over-admitting is dangerous.
• Hot keys handled with local pre-checks and sharded sub-counters, promoted only when monitoring flags a key.
• Per-region counters with rough global limits; reconcile asynchronously only if a hard global cap is truly required.
• Rules in a normal database, cached locally, refreshed every few seconds, with pub/sub for emergency changes.

For how specific companies probe this one, see our related guides on the engineering interviews at major infra and platform companies.