system-design

Design a Distributed Rate Limiter

Difficulty: Tier 1 Asked at: Careem, Tabby, Stripe-style fintechs, Amazon, Google Time budget: 45 min

A rate limiter answers one question — “has this client made too many requests?” — millions of times per second, with almost no latency budget, across many servers that must agree. It’s a favourite because the naive answer (a counter) unravels fast under “what about across servers?” and “what about the boundary between windows?” This is where you show you know the rate-limiting algorithms cold.

Prerequisites: Rate Limiting, Caching / Redis, API Gateway

1. Requirements

Functional:

Allow N requests per client per time window; reject (HTTP 429) the rest.
Limits keyed by API key / user ID / IP.
Configurable rules (different limits per endpoint / tier — free vs paid).
Return useful headers: X-RateLimit-Remaining, Retry-After.

Non-functional:

Very low latency — the limiter is in every request’s critical path; it must add < 1–2 ms.
High throughput — millions of checks/sec.
Distributed & consistent-enough — many app servers/gateways must share the same view of a client’s count, or a client hits the limit on one server and sails through on another.
Highly available — if the limiter fails, decide: fail-open (allow) or fail-closed (block)?

Out of scope: the business logic being protected; billing.

2. Estimation

Suppose 1M requests/sec across the platform, each needing a limit check → 1M limiter ops/sec.
Each check is a tiny read-modify-write on a counter. In Redis, a counter op is ~sub-ms; a single Redis node does ~100K+ ops/sec, so you need sharding / a cluster to hit 1M/sec.
Memory: one counter per active client per window. Millions of clients × a few bytes = tens of MB — trivial; the challenge is ops/sec and latency, not storage.

3. API / integration

The rate limiter is usually a middleware in the API gateway or a sidecar the gateway calls, not a user-facing API. Conceptually:

allow(clientId, rule) → { allowed: bool, remaining: int, retryAfter: int }

Config API for rules:

PUT /rules  { key: "api-tier-free", limit: 100, window: "1m", algorithm: "sliding-window" }

4. The algorithms (the heart of this question)

🚨 Know these four and their trade-offs — the interviewer will push here. (Full detail: Rate Limiting.)

Algorithm	How	Pro	Con
Fixed window	Count per calendar window (e.g. per minute); reset at boundary	Dead simple, cheap (one counter)	Boundary burst — 2× limit across a window edge
Sliding window log	Store timestamp of every request; count those in the last window	Exact	Memory-heavy (stores every timestamp)
Sliding window counter ⭐	Weighted blend of current + previous fixed window	Smooth, cheap, no boundary burst	Slight approximation
Token bucket ⭐	Tokens refill at a steady rate; each request spends one; bucket has a max	Allows controlled bursts, smooth average	Two values to track (tokens, last-refill)
Leaky bucket	Requests queue and drain at a fixed rate	Smooths output perfectly	Adds latency; queue can fill

Recommendation: token bucket (allows bursts, which real clients need) or sliding window counter (smoothest simple option). State why: token bucket matches how APIs actually want to behave — steady average, tolerate short bursts.

🚨 The fixed-window boundary bug is the classic gotcha: limit 100/min, a client sends 100 at 12:00:59 and 100 at 12:01:00 → 200 requests in 2 seconds, “within limits.” Sliding window / token bucket fix this.

5. High-level design

flowchart LR
    Client --> GW[API Gateway<br/>+ rate-limit middleware]
    GW -->|check & increment| Redis[(Redis Cluster<br/>counters/buckets)]
    GW -->|allowed| Svc[Backend Service]
    GW -->|429 too many| Client
    Config[Rule Config] --> GW

Central store = Redis (in-memory, atomic ops, fast). Every gateway instance checks the same Redis so counts are shared across all servers. Rules are cached locally in each gateway and refreshed periodically.

6. Deep dives

6a. Making the check atomic

A check is read-count → compare → increment. Done naively across many servers, two concurrent requests both read “99”, both think they’re allowed, both increment → 101 allowed (a race, thundering herd flavor). Fixes:

Redis atomic INCR (fixed window) — increment-and-read in one atomic op.
For token bucket / sliding window, run a Lua script on Redis so the read-modify-write executes atomically server-side. 🚨 This is the standard production approach — one round trip, atomic, fast.

6b. The distributed-consistency problem

All gateways must agree on a client’s count. Options:

Central Redis (recommended): single source of truth, atomic, ~sub-ms. One extra network hop per request — acceptable, and co-locate Redis near the gateways.
Local counters + sync: each server keeps a local count and periodically reconciles. Lower latency but approximate — a client can exceed the limit during the sync gap. Acceptable if limits are soft.
🚨 The trade-off: perfect global accuracy (central store, one hop) vs lowest latency (local, approximate). Most systems accept the one hop for accuracy.

6c. Scaling Redis to millions of ops/sec

Shard the keyspace: hash(clientId) picks a Redis shard, so each client’s counter lives on one shard and load spreads across the cluster. A client’s ops always go to the same shard (its counter is there), so atomicity holds per-client. (Consistent Hashing)

6d. Failure mode: fail-open vs fail-closed

If Redis is unreachable, do you allow or block? 🚨 A real trade-off to state:

Fail-open (allow): protects user experience; risks overload if the limiter is down during a spike. Usually chosen for user-facing limits.
Fail-closed (block): protects the backend; risks blocking legitimate traffic. Chosen when the backend must be protected (e.g. an expensive downstream, fraud controls). Mitigate with a local fallback limiter (approximate) so you degrade gracefully rather than choosing a hard extreme.

7. Bottlenecks & scaling further

Redis throughput → shard/cluster by client key.
Network hop latency → co-locate Redis, use pipelining/Lua to minimize round trips, local caching of rules.
Hot client (one API key hammering) → its counter is one key on one shard; that shard can hotspot. Mitigate with local pre-checks (if already clearly over the limit locally, reject without hitting Redis).
Rule distribution → push config changes to gateways via a config service / pub-sub.

8. Trade-off summary

Decision	Chosen	Alternative	Why
Algorithm	Token bucket / sliding window counter	Fixed window	No boundary burst; allows controlled bursts
Store	Central Redis	Per-server local	Global accuracy across all gateways
Atomicity	Redis Lua / INCR	App-side read-modify-write	Avoids the race that over-admits
Failure	Fail-open (user-facing)	Fail-closed	Prioritize availability; local fallback softens it

9. Follow-up questions

Explain the fixed-window boundary problem and how token bucket avoids it.

Fixed window counts requests per calendar window (per minute) and resets at the boundary. A client can send the full limit at the very end of one window and the full limit at the very start of the next — e.g. 100 at 12:00:59.9 and 100 at 12:01:00.1 — passing 200 requests in a fraction of a second while never "exceeding 100/min" in either window. Token bucket avoids this because it doesn't reset on a boundary: tokens refill continuously at the limit rate, so after spending 100 tokens the client must *wait* for tokens to refill regardless of where the clock is — there's no magic boundary to exploit. Sliding-window approaches fix it differently, by counting over a rolling window rather than a fixed one.

Why not just keep the count in each app server's memory?

Because the count wouldn't be shared. With N servers behind a load balancer, a client's requests spread across all of them, so each server sees only ~1/N of the traffic and thinks the client is well under the limit — the client effectively gets N× the intended limit. A central store (Redis) gives every server one shared view. Local counters are only acceptable if you accept approximate limits and periodically reconcile, trading accuracy for latency.

How do you add ~1ms latency and not more?

Keep the limiter check to a single round trip to an in-memory store co-located with the gateway, execute the read-modify-write atomically server-side (Redis Lua) so it's one op not several, cache rules locally so rule lookups are free, and pipeline where possible. Sharding keeps each Redis node's load low so ops stay sub-ms. If you can reject clearly-over-limit clients from a local approximate counter without any network call, you save the hop entirely for the abusive case.

How would you support different limits for free vs paid tiers?

Attach a tier to each API key, and store rules per tier (free: 100/min, paid: 10,000/min). The limiter looks up the client's tier (cached) and applies the matching rule. Rules live in a config store, pushed to gateways on change. This also lets you do per-endpoint limits (expensive endpoints get tighter rules) by keying the counter on (client, endpoint).

10. What junior / mid / senior answers look like

Junior: proposes a counter per client, resets each window. Works for one server; misses the cross-server and boundary problems.
Mid: picks a proper algorithm (token bucket / sliding window), uses central Redis for shared state, makes the increment atomic, returns 429 with headers.
Senior: all that plus the fail-open/closed decision, sharding Redis for throughput, the atomicity race and the Lua-script fix, hot-key mitigation, and articulates the accuracy-vs-latency trade-off of central vs local counting. Knows the boundary bug by heart.