Design a Distributed Rate Limiter and Counter

1Clarifying the requirements#

Never start drawing boxes. Start by pinning down what "rate limiter" actually means here, because the answer flips the whole design. A per-user API limiter and a generic counting service look alike on a whiteboard and share almost none of the hard problems.

Candidate: Is this a per-user API rate limiter, or a general-purpose distributed counter we expose as a service? Those are different problems.

Interviewer: Primarily a rate limiter for a public API. But other teams want to reuse the counting layer, so keep the counter generic.

Candidate: Got it. What limits are we enforcing? Something like "100 requests per minute per API key"?

Interviewer: Yes, per API key, and we also want per-IP limits for abuse. Rules should be configurable, not hardcoded.

Candidate: When a request is over the limit, do we hard-reject with a 429, or do we queue and slow it down?

Interviewer: Hard reject. Return 429 with a Retry-After header.

Candidate: Last big one: if the rate-limiter backend is down or slow, do we fail open (let traffic through) or fail closed (block everything)?

Interviewer: Fail open. We would rather serve a few extra requests than take the whole API offline.

What those answers just told me:

• Fail open means the limiter is a guardrail, not a security wall. I am free to favor availability over precision.
• I can approximate the count whenever that is cheaper, and never block a real request because my counter store hiccuped.
• Had the answer been "fail closed, this protects payments," I would be designing a slower, exact, completely different system.
• This one line decides half the later trade-offs, so I pin it down before anything else.

Functional requirements

• Allow or deny a request based on a rule keyed by API key, IP, or a custom bucket ID.
• Rules are configurable at runtime: limit, window, scope. No redeploy to change "100/min" to "200/min".
• Return remaining quota and a reset time so clients can self-throttle.
• Expose a generic atomic counter (increment, read, reset) that other teams reuse.
• Support multiple rule tiers: a free key gets 100/min, a paid key gets 10,000/min.

Non-functional requirements

• Added latency under 2 ms at p99. The limiter is in the hot path of every single request, so this budget is non-negotiable.
• Correct enough: a small overshoot under extreme concurrency is fine. Off by 2 percent is acceptable; off by 50 percent is not.
• Fail open on backend failure.
• Horizontally scalable to hundreds of thousands of decisions per second.
• Rule changes take effect within a few seconds globally.

2Back-of-the-envelope estimation#

Size this so the numbers drive the architecture instead of your gut. The point here is to find the one number that hurts, not to fill a table.

Traffic.

• The API behind us serves about 50,000 requests/second at average load. Every one hits the limiter, so that is 50k decisions/sec.
• Peak is spiky. Marketing fires a push, traffic triples. Call peak 150k decisions/sec.
• Each decision is one read-modify-write against a counter, so the store sees roughly 150k ops/sec at peak, each back in well under a millisecond.

Key count and memory (a pleasant surprise).

• Active distinct keys in any one-minute window: say 2 million API keys plus a few million IPs. Call it 5 million live counter keys.
• Each entry is tiny: key string (about 64 bytes), count (8 bytes), window timestamp (8 bytes), plus overhead. Round to about 150 bytes per key.
• 5M keys is about 750 MB of hot state. That fits in memory on a single beefy Redis node with room to spare.
• Memory is not my problem here, which is a relief and worth saying out loud.

Analytics storage (what we refuse to keep).

• Persisting every decision would be 50k/sec x 86,400 x 365, roughly 1.6 trillion events/year.
• We do NOT store those raw. We roll them up to per-minute counts, which cuts it by orders of magnitude.

3Core APIs#

Two surfaces: the internal "can this request proceed" call, and the generic counter other teams reuse.

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

{
  "key": "apikey_8fa3",
  "scope": "per_minute",
  "cost": 1
}

{
  "allowed": true,
  "limit": 100,
  "remaining": 42,
  "reset_at": 1730592000,
  "retry_after": null
}

POST /v1/counter/increment
{ "counter_id": "signups_2026_11", "delta": 1 }

GET  /v1/counter/signups_2026_11
POST /v1/counter/reset  { "counter_id": "signups_2026_11" }

Two design choices worth defending:

• The cost field means not every request is worth one token: a bulk endpoint can cost 10. Baking it in now saves a redesign when someone asks to charge heavy calls more later.
• The response always carries limit, remaining, and reset_at so a well-behaved client self-throttles instead of blindly retrying into a wall of 429s.

The check is not even a network call to a separate service:

• It is a library call inside the API gateway that talks straight to Redis.
• A separate service hop would add a serialization round trip and blow the 2 ms budget by itself.
• I will show both the gateway-embedded path and the central store, because the embedding is a real design decision, not an implementation detail.

4High-level design#

The shape, drawn fast:

• A thin limiter layer embedded in the gateway.
• A shared Redis cluster holding counters.
• A rules service that pushes config.
• An async pipeline that ships decision logs to analytics without touching the hot path.

Write path (the decision).

• Request arrives at the gateway.
• The limiter runs one atomic Lua script against Redis and gets allow/deny back. Done.
• That is the entire synchronous path: one network hop to Redis.

Read path (observability).

• Decisions are sampled and streamed to a queue, rolled up, and surfaced in dashboards.
• None of this is synchronous, so a backed-up queue never slows a decision.

Rules path (control plane).

• Edits go to a config store and get pushed to every gateway.
• Each gateway caches the current rules in memory and never reads a rule over the network on the hot path.

5Data model#

The counter state in Redis is intentionally dumb. Keep it minimal, because every extra field is memory multiplied across 5 million keys.

Redis counter entry (sliding window counter)

Redis token bucket entry

Rules config (in the config store, cached in gateway memory)

Analytics rollups (persisted)

Three stores, three access patterns, each matched to its job:

• Hot counter state goes in Redis, period. In-memory, single-threaded per shard (so increments are atomic for free, the keystone of the whole design), native TTL expiry, server-side Lua. No relational DB survives 150k read-modify-writes/sec on contended rows without row-lock contention eating you alive.
• Rules config goes in SQL/Postgres. Tiny and read-mostly, a few thousand rows that change a handful of times a day, and the gateways cache it.
• Analytics rollups go to a columnar or time-series store. The query is "show me denials for key X over 24h," a scan-and-aggregate, exactly what columnar is built for and Redis is bad at.

6Deep dives#

6.1 Token bucket vs sliding window, and why I pick the counter variant#

This is the signature algorithm decision. A strong answer names three contenders and the specific failure of each, not just "I'll use token bucket because it's popular."

Fixed window.

• Count per calendar minute, reset at the top of the minute. Dead simple, one INCR.
• The flaw is the boundary burst: 100 requests at 11:00:59 and another 100 at 11:01:00 sails 200 through in two seconds while technically respecting a 100/min limit.
• For abuse control that is unacceptable, because the abuser just aligns to the window edge.

Token bucket.

• A bucket holds N tokens, refills at a steady rate, each request spends one.
• It allows bursts up to the bucket size then smooths out, which is what you want for a friendly API: let people spike briefly, throttle sustained abuse.
• Cost: you track two values (tokens, last_refill) and do floating-point refill math every call, slightly more work and memory per key.

Sliding window counter (my default).

• A weighted blend of the current and previous fixed windows. At 25 percent into the current minute, your effective count is current_count + previous_count * 0.75.
• This kills the boundary burst almost entirely, costs about the same as fixed window (two reads and an increment), and is accurate to within a percent or two.
• That tiny imprecision is exactly the slack the interviewer granted me with "fail open, small overshoot is fine." I am spending correctness I was told I could spend.

Why I would not ship a true sliding log.

• Storing every request timestamp in a sorted set is exact, but at 150k/sec the per-key memory and the per-request ZADD plus ZREMRANGEBYSCORE cost is brutal.
• Worse, it grows with traffic instead of staying flat.
• The approximation buys 95 percent of the correctness for 5 percent of the cost, and I take that trade every time on a guardrail.

So: sliding window counter as the default, token bucket offered as a per-rule option for APIs that want burst-friendly behavior.

6.2 The race on concurrent decrements, and the Lua fix#

Here is the part that trips up most candidates, and it is the real meat of the question. Naive code:

1. count = GET key
2. if count < limit, INCR key, allow
3. else deny

Why this is broken under load.

• Twenty gateway processes all read count = 99 at the same instant.
• All see 99 < 100, all INCR, and now the counter is 119 and you let 20 requests through when you should have let one.
• The window between the read and the write is where correctness dies.
• At 150k/sec on a hot key that window is not a rare corner case. It is hit constantly. This is why the "one number that drives everything" from estimation was about contention.

The fix: make check-and-increment one atomic operation on the Redis side.

• Redis is single-threaded per shard, so a Lua script runs to completion with no other command interleaved.
• That single-threaded property, usually thought of as a limitation, is exactly what gives us atomicity for free: no distributed lock, no CAS retry loop, no Redlock.
• The script does the read, the compare, and the conditional increment as one indivisible unit.

-- KEYS[1]=counter key, ARGV[1]=limit, ARGV[2]=ttl
local c = tonumber(redis.call('GET', KEYS[1]) or '0')
if c + 1 > tonumber(ARGV[1]) then
  return {0, c}            -- denied
end
redis.call('INCR', KEYS[1])
redis.call('EXPIRE', KEYS[1], ARGV[2])
return {1, c + 1}          -- allowed

Now there is no gap. Every gateway's check serializes through the shard, and the counter is always exact.

The trade-off I call out before the interviewer does.

• All requests for one key serialize through one shard, so a single scorching-hot key can saturate one Redis thread, and sharding cannot help since the key maps to exactly one shard.
• My mitigation is deliberately NOT to split the key (that reintroduces the summation race).
• Instead I detect hot keys and switch them to local approximate counting with periodic sync: each gateway counts locally, allows based on limit / number_of_gateways, and flushes its local delta to Redis every few hundred milliseconds.
• You lose exactness, you gain the ability to absorb a DDoS without one Redis thread melting. For a fail-open guardrail that is clearly right, and I would not hesitate.

6.3 CDN edge vs central store, the latency and accuracy trade#

Where should the limiter actually live? Two extremes, and the senior answer is a blend, not a pick.

Central Redis.

• One source of truth, perfectly accurate within a region.
• Every decision pays a round trip: 0.3 to 0.5 ms inside one datacenter, fine, well within budget.
• Across regions it is 50 to 150 ms, which blows the 2 ms budget by two orders of magnitude and turns Redis into a cross-region bottleneck every request waits on.

Edge-local.

• Run the limiter at the CDN edge or per-region, each with its own local counter. Latency is near zero because the decision is made in the POP the request landed in.
• The cost is accuracy: if a user's requests spray across 10 edge locations, no single edge sees the global count, so a "100/min global" limit can leak up to 10x if you naively hand each edge the full 100 budget.

My answer is a tiered design, not a pick-one, and each tier earns its place:

• Edge enforces a generous local cap to stop obvious floods instantly, zero latency, fail open. It catches the 99 percent case, the dumb flood, before it ever costs a cross-region hop.
• Regional Redis enforces the real per-key limit for everything that passes the edge, accurate within the region, sub-millisecond.
• True global limit accepts eventual consistency: each region keeps a local counter and asynchronously syncs deltas to a global aggregator every second. The global number lags about a second, which for rate limiting is invisible to the user and the attacker.

The deliberate consistency call: strong inside a region, eventual across regions.

• Rate limiting tolerates a second of staleness because a second of overshoot on a guardrail is harmless. Payments would not tolerate it.
• A globally-synchronous counter would make every increment wait on cross-region consensus, making the limiter slower than the thing it protects, which is absurd.
• Knowing which guarantee the problem actually needs, and refusing to over-build the parts that do not, is the signal the interviewer is listening for.

6.4 Failing open without lying to yourself#

Fail open is easy to say and easy to do carelessly. The honest version has teeth.

• The limiter lib puts a hard 5 ms timeout on the Redis call.
• On timeout it allows the request and emits a metric, so we can see exactly how often we are leaking.
• During a Redis failover, for a second or two, decisions have no backend. That is precisely when fail-open earns its keep: leak a few requests for two seconds rather than 429 the entire planet.
• The metric matters as much as the behavior. A silent fail-open is a liability; a measured one is a conscious operating posture you can alert on.

7Bottlenecks and trade-offs#

What breaks first.

• The hot key, every time. 99 percent of traffic is fine, but during an incident a single API key or IP eats one Redis thread, and that one thread is the ceiling.
• That is exactly why the hot-key local-counting fallback from 6.2 exists.
• The second thing to fall over is the Redis cluster itself if a shard dies and traffic for its slots has nowhere to go for a moment.

Single points of failure.

• The Redis cluster is the obvious one. I run it with replicas and automatic failover (Sentinel or cluster mode).
• The honest part I volunteer: during failover, for a second or two, decisions have no backend, and that is when fail-open earns its keep (see 6.4).
• The rules service and analytics pipeline are not SPOFs because they sit off the hot path, so their death is a degraded-observability event, not an outage.

The consistency call I made on purpose.

• I chose approximate over exact in two places: the sliding-window approximation in 6.1, and cross-region eventual consistency in 6.3.
• Both are defensible because the requirement explicitly allowed small overshoot and fail-open, so I am spending exactly the correctness I was given permission to spend.
• For a billing meter where every count is money, I would flip all of it: exact counts, synchronous increments, fail closed, and I would eat the latency and tell the interviewer I am eating it on purpose.

Other real limits.

• Lua script cost. Each EVAL is a few microseconds of CPU on the single Redis thread, so 150k/sec is comfortable on one modern core. I keep scripts tiny and loop-free, because a slow script blocks every other command on that shard.
• Memory. 750 MB of hot keys with TTL stays bounded by expiry, but I still cap maxmemory and alert, because a key-explosion attack (an attacker inventing random API keys) could blow past memory and start evicting live counters.
• Clock skew. The sliding window uses the Redis server clock, not the gateway clock, so skew between gateways cannot corrupt windows. A quiet but important correctness detail.

Spend only the correctness the problem gives you permission to spend, and no more.

8Summary#

The defensible decisions, stated plainly, because the close is where you prove you know why you made each call:

• Sliding window counter as the default algorithm, token bucket as a per-rule option. It kills boundary bursts at near fixed-window cost.
• Redis with a Lua script for check-and-increment, because single-threaded execution makes the read-modify-write atomic and kills the decrement race with no distributed locks, no Redlock, no CAS retries.
• Limiter embedded in the gateway, not a separate service hop, to hold the 2 ms budget.
• Tiered edge plus regional plus async global, strong consistency inside a region and eventual across regions, matched to what rate limiting actually tolerates.
• Fail open with a hard 5 ms timeout and a leak metric, because this is a guardrail and availability beats precision here.
• Logging and rules push kept off the hot path, so their failure degrades observability, never availability.

For the payments-grade version of this (where counts are money and you cannot fail open), see the UPI and wallet system design guide and its two-leg atomicity deep dive.