Design a Rate Limiter — Token Bucket, Sliding Window & Distributed Limits (with Production .NET Code)

"Design a rate limiter" sounds like a five-minute answer — count requests, block past the limit. Then the interviewer starts pulling threads: which algorithm, and what's the burst behaviour at the window edge? Where does the counter live when you have 500 app servers? What happens to two requests that read the same counter at the same millisecond? What if the counter store goes down — block everyone or let everyone through? Those follow-ups are the whole interview.

This is the condensed walkthrough; the full guide (all five algorithms, the distributed section, and the full production .NET 9 code) is on my site 👇

Full guide: https://prepstack.co.in/blog/design-a-rate-limiter-system-design

The design at a glance

Concern	Decision
Algorithm	Token bucket (bursts, O(1)) or sliding-window counter (accurate, smooth)
Where it lives	API gateway / middleware, in front of app servers
State store	Redis — shared across all servers so the limit is global
Atomicity	Redis + a Lua script (or INCR) so concurrent requests can't over-count
On store failure	Fail open for general throttling; fail closed for security limits
Response	429 + Retry-After and X-RateLimit-* headers

Why it's inline-on-every-request

A rate limiter runs on every request, so its cost is paid by all traffic, all the time. That reframes every choice: the algorithm must be O(1), the store lookup atomic and sub-millisecond, and the failure mode must not take your whole API down. Say the API peaks at 1M req/sec — the limiter must sustain 1M checks/sec at < 1 ms each.

The counting algorithms (the core of the interview)

1. Fixed window counter. INCR a per-window key; reset each window. Dead simple, O(1) — but the boundary burst: a client sends the full limit at 00:00:59 and again at 00:01:00 → 2× the limit in ~1 second. Know this trap.

2. Sliding window log. Store a timestamp for every request (Redis sorted set); drop old ones, count the rest. Perfectly accurate, no boundary burst — but memory grows with volume. Expensive for busy clients.

3. Sliding window counter (the sweet spot). Approximate the rolling window with two fixed-window counts weighted by overlap:

estimated = current_count + previous_count × (overlap fraction)
# 30s into the current minute: prev_count × 0.5 + current_count

O(1) memory, smooths the boundary burst, close enough for almost everything. What many CDNs use.

4. Token bucket (the industry default — Stripe, AWS). A bucket holds up to C tokens, refills at r tokens/sec; each request takes one, empty = reject.

allow(client):
  now = time()
  tokens = min(C, tokens + (now - lastRefill) * r)   # lazy refill
  lastRefill = now
  if tokens >= 1: tokens -= 1; return ALLOW
  return DENY

Stores only {tokens, lastRefill} (O(1)), allows controlled bursts up to C while holding the average at r, refills lazily (no timer).

5. Leaky bucket. FIFO queue processed at a constant rate; overflow rejected. Where token bucket allows bursts, leaky bucket smooths them into a steady stream — useful for shaping traffic to a rate-sensitive downstream.

What to pick: token bucket for a general API limiter; sliding-window counter when you want accuracy without the log's memory. Fixed window only when the boundary burst genuinely doesn't matter.

Making it distributed (the second hard part)

• Local counters don't add up. 500 servers each with their own bucket → client gets 500 × limit. Fix: a shared Redis store, one authoritative count.
• The read-modify-write race. Two requests hit two servers, both read tokens=1, both allow, both decrement → two through a bucket that had one. Fix: atomicity — INCR for fixed window, a Redis Lua script wrapping read-check-write for token bucket / sliding window (runs atomically, no interleaving).
• The Redis round trip on every request. Co-locate + pipeline; or a hybrid local approximation reconciled periodically; or sticky routing (hash each client to a fixed server so its local bucket is authoritative).
• Redis as a hot spot / SPOF. Shard counters by clientId, replicate for failover; shard a single extremely hot client's budget across keys.

Fail open vs fail closed

If Redis is unreachable, do you allow everything (fail open — protects availability, risks overload) or block everything (fail closed — protects the resource, risks an outage)? Default to fail open for general throttling; fail closed for security-critical limits like login or payment attempts. It's a one-sentence answer that shows judgment.

I shipped this in production

Our public API peaks at ~3,200 req/sec across tenants and originally had no per-tenant ceiling — a single runaway scraper could push p99 into the seconds and drag every other tenant down. Moving a per-tenant token bucket to the gateway (atomic Redis Lua, 200 burst / 100 req/s):

Metric	Before	After
API p95 latency	480 ms	120 ms
p99 during a single-tenant burst	multi-second spikes	flat, no cross-tenant spike
Blast radius of one abusive tenant	all tenants degraded	isolated (429 + Retry-After)
Per-tenant budget	none	token bucket, 200 burst / 100 req/s

The read-refill-check-decrement is a single atomic Redis Lua script, so concurrent gateway instances can never double-spend a tenant's budget, and the tenant id is read from the verified token (never a caller-supplied argument) so one client can't spend down another's bucket. (Full .NET 9 middleware + Lua script is in the post.)

The model to carry forward

A rate limiter is an algorithm choice wrapped in a distributed-consistency problem. Three habits it teaches: (1) name the boundary burst; (2) make the shared update atomic, always — the read-modify-write race is the bug that quietly lets everyone past; (3) decide the failure mode on purpose.

The full guide has all five algorithms in depth, the full distributed section, the design checklist, the complete production .NET 9 token-bucket middleware + Lua script, and the "when it's overkill" honest section:

https://prepstack.co.in/blog/design-a-rate-limiter-system-design

Originally published on PrepStack.