Design a Rate Limiter

Rate Limiting covered the algorithms (token bucket, sliding window) in the abstract; this problem is about actually building the service that enforces them — specifically, where the counters live and how they stay correct when many application servers are checking and updating them concurrently. Following the framework from How to Answer a System Design Interview Question.

1. Requirements

Functional:

• Given a client identifier (API key, user ID, or IP) and a limit (e.g. 100 requests/minute), allow or reject each incoming request.
• Return 429 Too Many Requests when the limit is exceeded, with headers indicating the limit, remaining count, and reset time.

Non-functional:

• The limiter itself must add negligible latency — it sits in front of every request, so it can't become the bottleneck it's meant to prevent elsewhere.
• Must be correct under concurrency: many application server instances checking the same client's count at once must never let the client exceed its limit due to a race condition.
• Doesn't need strong global correctness at the level of the CAP Theorem — being briefly off by a small amount under extreme concurrency is an acceptable tradeoff for lower latency, discussed below.

Scale estimate: assume 50,000 requests/second across all clients needing a limit check — this is squarely a "many small, extremely fast operations" workload, which points directly at an in-memory store rather than a disk-backed database for the counters themselves.

2. API Design

The rate limiter is typically not a client-facing API at all — it's an internal check invoked by an API Gateway or middleware layer on every request:

check_limit(client_id: string, limit: int, window_seconds: int) -> { allowed: bool, remaining: int, reset_at: timestamp }

3. Data Model

A relational database is the wrong tool here — the access pattern is "increment a counter and check it, thousands of times a second, per client," which is exactly what an in-memory key-value store like Redis is built for. The data model is a simple key per client per window:

key:   rate_limit:{client_id}
value: current request count in this window
ttl:   window_seconds (auto-expires the key when the window ends)

4. High-Level Design

System Design Lab

Redis is the natural fit specifically because it's shared, in-memory, and — critically — supports atomic increment-and-check in a single operation, which is exactly what the concurrency requirement above demands.

5. Deep Dive: avoiding the race condition

The failure mode worth naming explicitly: if checking the current count and incrementing it are two separate operations, two concurrent requests can both read "99 out of 100" before either writes back "100," and both get allowed through — letting the client exceed its limit. Redis's INCR command is atomic — it increments and returns the new value in one indivisible step, so two concurrent requests are guaranteed to see different, correctly-ordered results (100 and 101) rather than racing on a stale read. This is the same class of problem ACID Transactions' isolation guarantees solve in a relational database, solved here instead by choosing an operation that's atomic by construction rather than wrapping a read-then-write in an explicit transaction.

A fixed window (simply resetting the counter to zero every 60 seconds, say) is simpler but has a real correctness gap worth naming: a client can send its full limit in the last second of one window and its full limit again in the first second of the next, getting roughly double its intended rate in a short burst straddling the boundary — a fixed window resets, it doesn't actually track "the last 60 seconds" on a rolling basis. A sliding window closes that gap by tracking requests relative to now, not to a fixed clock boundary. Redis sorted sets are a common implementation: each request is stored with its timestamp as the score, and checking the limit means counting entries within the trailing window and evicting anything older — still a small number of atomic Redis operations per check, not a database query.

6. Tradeoffs

Centralizing counters in one shared Redis instance (or cluster) directly trades a small amount of added network latency per request for correctness across every application server — the alternative, keeping counts in each application server's own local memory, would be faster per-check but wrong: a client could get roughly N times its limit by spreading requests across N application server instances, each enforcing the limit only against its own local, incomplete view of that client's traffic.

Centralized (Redis) vs. per-server local rate limiting: pros and cons

Pros

• ✓Enforces one true limit per client across every application server
• ✓Redis's atomic operations avoid the race condition a naive read-then-write has
• ✓A dedicated in-memory store is fast enough to add negligible latency per check

Cons

• ✕Adds a network hop to every single request, however small
• ✕The rate limiter store itself becomes a new dependency every request now relies on
• ✕Needs its own redundancy story, or a Redis outage means every request fails its check

Further Reading

• Stripe Engineering — Scaling your API with rate limiters — a detailed, production-grounded walkthrough of implementing several rate-limiting algorithms.
• Redis Docs — INCR — the atomic operation this design's correctness depends on.