Design a Rate Limiter

The core behavior:

• Enforce a limit — allow at most N requests per client per time window (e.g. 100/minute, 5,000/hour).
• Identify the client — by API key, user id, or IP address, depending on who's calling.
• Reject over-limit requests — return 429 Too Many Requests, ideally with a Retry-After header telling the client when to try again.
• Support multiple rules — different limits for different endpoints or plan tiers (e.g. POST /login: 5/minute; GET /search: 100/minute).

Example. A client with a 100 req/min limit sends 100 requests in the first 10 seconds of a minute, then a 101st request 5 seconds later. The limiter rejects that 101st request with 429 and a Retry-After: 45 header, since a fresh window starts 45 seconds later.

Out of scope for a first pass: per-endpoint dynamic limit tuning and a self-serve dashboard for clients to see their own usage. Call these out so the interviewer knows you're scoping deliberately.

Always anchor the design with rough numbers. A reasonable set of assumptions:

• 10M active API keys/users, each with an independent limit.
• 50,000 requests/sec at peak across the whole platform — every one of them needs a rate-limit check.
• The limiter's own overhead must stay well under 1ms per check, since it sits on the hot path of every request.
• State per client is tiny — a counter and a timestamp, well under 100 bytes — but with 10M clients that's still worth keeping in memory (Redis), not a row-per-check relational table.

The big takeaway: this is a check-heavy, state-tiny system — the design challenge is keeping a shared counter fast and consistent under very high QPS, not storage volume.

We pull these from what a rate limiter is actually protecting:

• Low latency — the check happens on every request; it must add negligible overhead.
• High availability — if the limiter is down, requests should still get a sane default (fail open for most APIs; fail closed only for security-critical endpoints like login).
• Accuracy, with a bias toward availability — being off by a few requests around a window boundary is usually fine; falsely blocking a client who's under their limit is a worse failure than occasionally letting a client go slightly over.
• Horizontal scalability — the limiter must work correctly when requests for the same client land on different application servers.

This is the same shape as the URL shortener's read path — a shared, low-latency lookup that dominates the request volume — but here the state also changes on every request, not just on writes.

The state is intentionally minimal — this lives in memory (Redis), not a traditional database:

Rules are read-mostly and cached in each server's memory (refreshed periodically), so a rule lookup never adds a network hop to the hot path — only the per-client counter does.

The rate limiter is usually a check invoked by middleware, not a public API of its own:

GET /api/search?q=widgets
Authorization: Bearer <api_key>

-> 429 Too Many Requests
   Retry-After: 45
   X-RateLimit-Limit: 100
   X-RateLimit-Remaining: 0
   X-RateLimit-Reset: 1735689660

The X-RateLimit-* headers (a de facto standard) let well-behaved clients back off proactively instead of hammering the API until they get a 429. Internally, the check is a single function call: allow(client_id, rule) -> boolean, backed by a call to the shared counter store.

The request flow:

1. A request arrives at the API gateway (or a middleware layer in front of each service).
2. The gateway asks the rate limiter — identified by client id and the rule for this endpoint — "allow or reject?"
3. The rate limiter reads and atomically updates a counter in Redis, shared across all gateway instances.
4. If allowed, the request proceeds to the application server; if rejected, the gateway returns 429 immediately without touching the backend.

Because this check runs on every request, Redis (or an equivalent in-memory store) is doing double duty as both the shared source of truth and the low-latency path — there's no room for a full database round trip here.

This is the heart of the problem — how you count requests within a window changes both accuracy and cost.

• Fixed window counter (simplest) — increment a counter keyed by client_id + current_minute; reject once it exceeds the limit; the counter resets when the minute changes. Cheap (one INCR per request) but has a boundary burst problem: a client can send its full limit at 0:59 and its full limit again at 1:00, getting 2× the intended rate in a 2-second span.
• Sliding window log — store every request's timestamp (e.g. in a Redis sorted set), and count only the ones within the trailing window (now - window_size) on each check. Accurate — no boundary bursts — but stores one entry per request, which gets expensive at high volume per client.
• Sliding window counter (good default at this scale) — approximate the sliding window using two fixed windows: weight the previous window's count by how much of it still overlaps the trailing window, and add the current window's count. Worked example: limit is 100/minute; the previous minute had 80 requests, the current minute (30 seconds in, so 50% has elapsed) has 20 requests. Estimated count = 80 × (1 - 0.5) + 20 = 60 — under the limit, so the request is allowed. This is nearly as accurate as the log approach at a fraction of the memory (two counters instead of N timestamps).
• Token bucket — a bucket holds up to N tokens, refilled at a steady rate (e.g. 1.67 tokens/sec for 100/minute); each request consumes one token, and is rejected if the bucket is empty. Unlike fixed/sliding window, this naturally allows brief bursts up to the bucket size while still enforcing a long-run average rate — a good fit for APIs that expect occasional spiky-but-legitimate traffic (a client catching up after being offline).
• Leaky bucket — the mirror image of token bucket: requests enter a queue (the "bucket") and are processed at a fixed, steady rate; excess requests overflow and are dropped. This smooths bursts into a constant output rate, which suits protecting a downstream system that can't handle spikes at all, at the cost of added latency for queued requests.

What I'd pick and why: token bucket for a general-purpose API — it tolerates legitimate bursts without the boundary-burst bug of fixed windows. For a security-sensitive endpoint like login, a plain, stricter sliding window (no burst allowance) makes more sense — you don't want to give a credential-stuffing attacker even a brief burst allowance.

A rate limiter is only correct if every server enforcing the same client's limit agrees on the count. Two ways to get there:

• Centralized counter (Redis) (good default at this scale) — every gateway instance checks and increments the same Redis key. Redis's single-threaded execution makes INCR (or a small Lua script combining check + increment) atomic, so there's no race between two servers both reading "99" and both allowing request #100. The cost is a network round trip per request and a shared dependency every request now depends on.
• Local counters + periodic sync — each server keeps its own approximate counter and only occasionally reconciles with a shared store. Removes the per-request network hop, but is inherently approximate: with 10 gateway instances each independently enforcing "100/minute," a client could get up to ~10× the intended limit split across servers before the next sync catches up. Reasonable when the limit is a soft guardrail rather than a hard guarantee (e.g. protecting against runaway retries, not enforcing a billed quota).

On failure: if Redis becomes unreachable, most APIs should fail open (allow the request) rather than reject all traffic — a rate limiter's job is to protect the backend from abuse, and taking the whole API down because the limiter's dependency hiccuped is usually a worse outcome than temporarily under-enforcing the limit. The exception is limits that exist for security reasons (e.g. login attempts) where failing closed (reject) may be the safer default.

A solid answer hits these points:

• Token bucket (or sliding-window counter for stricter endpoints) as the counting algorithm — it avoids the fixed-window boundary-burst bug while staying cheap to compute.
• A shared, in-memory store (Redis) as the source of truth so every server enforcing the same client's limit agrees, using an atomic increment-and-check (a Lua script) to avoid races.
• Fail open by default so a limiter outage doesn't take down the whole API, with fail-closed reserved for security-sensitive endpoints.
• X-RateLimit-* headers so well-behaved clients can self-throttle instead of hitting 429s.

Common follow-ups: how to rate limit by multiple keys at once (per-IP and per-API-key), how to avoid the shared Redis instance becoming a single point of failure or a latency bottleneck under very high QPS (sharding the counter store by client id, or moving to local-approximate counters with periodic reconciliation), and how to distinguish a legitimate traffic spike from an abusive one.