Design a Rate Limiter
Scenario prompt
Design a rate limiter for a public API gateway that sits in front of many backend services. It needs to:
- Enforce a per-client limit (e.g., 100 requests/minute) fairly, even under bursty traffic
- Work correctly across multiple gateway instances behind a load balancer (no single-instance-only counting)
- Add minimal latency to every request — the limiter sits on the hot path
- Fail in a safe, predictable way if its own storage backend is briefly unavailable
Mihir's attempt
[!todo] Write your own attempt here before reading the model solution below — algorithm choice, storage choice, and what you'd do on backend failure.
Model solution
Algorithm — token bucket or sliding window log/counter, not fixed window. A naive fixed-window counter (reset the count every clock-minute boundary) lets a client burst up to 2x the limit right across a window boundary (max requests at the end of one window plus max requests at the start of the next). A sliding window (log of timestamps, or an approximated sliding counter blending the previous and current window) or a token bucket (tokens refill continuously at a fixed rate, requests spend a token) both avoid that edge burst.
Storage — centralized, shared, fast key-value store (Redis is the standard choice), not per-instance memory. Since the gateway runs as multiple instances behind a load balancer, per-instance in-memory counters would let a client get the full limit per instance — the actual constraint (a global per-client cap) requires a shared source of truth all instances read/write against. Redis's INCR + EXPIRE (or a Lua script for atomicity) is the common implementation for exactly this reason: it's fast enough to sit on the hot path and naturally supports atomic increment-and-check.
Failure mode — fail open, not fail closed, with an alert. If Redis is briefly unreachable, the pragmatic default is to let requests through rather than reject all traffic — a false negative (occasionally over-serving a client) is far less damaging than a false positive (an outage in the rate limiter taking down the whole API). This should be a deliberate, documented choice, not an accident of how the client library happens to behave on timeout.
Where to enforce it — at the gateway/edge, not in each backend service. Centralizing it means one implementation to get right, one place to observe and tune, and backend services never have to reason about it individually.
Gaps to revisit
- How do you rate-limit fairly across clients of wildly different request costs (a search query vs. a health check) — token cost per endpoint, not a flat per-request count?
- What's the right key: per-API-key, per-IP, per-user, or some combination — and what happens behind shared NAT/corporate proxies?
- At extreme scale, does a single Redis instance become the new bottleneck/single point of failure the whole design was trying to avoid — and if so, what's the sharding strategy for the limiter's own storage?
Engineering Lens
Rate limiting is a small-sounding problem that's actually a distributed-systems problem in disguise — the moment you have more than one instance, "count requests" becomes "reach consensus on a shared count under latency and failure," which is the same class of problem that shows up in inventory counters, distributed locks, and leader election. Naming the fail-open/fail-closed decision explicitly, rather than leaving it as an accident of the client library's default timeout behavior, is a strong Principal-level signal in any review — it shows you've thought about the failure mode, not just the happy path. This maps just as cleanly onto a trading-order gateway throttling order submissions (Capital Markets) as it does onto a network device's traffic-shaping policy (Mihir's current domain) — the underlying reasoning is identical regardless of which industry it's applied in.