Rate Limiter

Understanding the Problem

Think of a highway on-ramp metering light — the kind that lets one car merge every few seconds during rush hour. It doesn't stop cars from wanting to get on; it just controls how fast they're let in, so the highway itself never gets so congested it grinds to a halt. A rate limiter does the same job for an API: it doesn't stop a client from sending requests, it just decides, request by request, how many actually get let through.

An API needs to cap how many requests each client can make in a given window, so that one noisy or abusive client can't degrade service for everyone else. The limiter has to make an allow/reject decision on the hot path of every request, so its own latency and availability matter as much as its correctness.

When it does reject, it needs to reject immediately rather than queue the request for later. Queuing would mean holding memory for a request that might never get served, and it would make response times unpredictable for every well-behaved client waiting behind it — the opposite of what a rate limiter is supposed to buy you.

With that shape in mind, here's what we actually need to build.

Functional Requirements

Non-Functional Requirements

• The check itself must add negligible latency to the request path — under 5ms at p99, since it runs in front of every API call, not just some of them.
• Assume 50,000 requests/sec at peak across all clients, with up to 10,000 distinct rate-limited identifiers active at any given moment.
• The limiter must not become the bottleneck it exists to prevent — it needs to survive at the same scale as the traffic it's gating.

These numbers are what the rest of this design leans on, especially the Capacity Estimation right below — worth pinning down before deciding anything about implementation.

Capacity Estimation

Redis memory footprint here is trivial by design: at up to 10,000 concurrent identifiers, and a sliding window counter needing at most two small counters per identifier (current window + previous window, each maybe 50 bytes including the key itself), that's on the order of 1MB total — nowhere near a capacity concern. The number that actually matters is throughput, not memory: 50,000 checks/sec, each a single Redis INCR, sits well within what a single, well-provisioned Redis node handles (Redis routinely sustains 100,000+ simple ops/sec). That's why this design can stay a single Redis instance rather than needing to shard the limiter itself — the constraint that would actually force sharding is a single identifier's traffic exceeding one node's throughput, not the aggregate across all 10,000 identifiers.

With the scale pinned down, here's the state that scale actually has to be stored in.

Core Entities

type RateLimitState = {
  identifier: string; // e.g. "apiKey:abc123"
  windowStart: number; // epoch ms
  count: number;
};

type RateLimitRule = {
  tier: "free" | "paid";
  limit: number; // requests allowed per window
  windowSeconds: number;
};

The FR above calls for different limits per client tier, and that needs its own small piece of state, separate from the live counter — a RateLimitRule can change (a client upgrades from free to paid) without touching the counter that's already mid-window for that client.

API Interface

POST /internal/rate-limit/check
  { identifier: string, limit: number, windowSeconds: number }
  -> { allowed: boolean, remaining: number, resetAt: number }

That's the internal contract between the gateway and the limiter. What the actual API client sees is different — plain HTTP, not a JSON envelope:

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1706812800
Retry-After: 42

{ "error": "rate_limit_exceeded" }

The gateway is what translates the internal check's { allowed, remaining, resetAt } into these headers — and it does it on every response, not just rejected ones. A client still under its limit gets the same X-RateLimit-Remaining header on a normal 200, so it can see how much room is left well before it ever gets a 429.

High-Level Design

Two questions shape this design: where does the check actually run, and what does it check against. Let's take them in order — the second only makes sense once the first is settled.

Where the check runs

Here's the in-process failure mode with real numbers. Say the limit is 100 requests/minute, and one client's traffic happens to land on 5 different app server instances behind a load balancer. Each server sees roughly 20 requests/minute from that client — comfortably under 100 by its own count — while the client's actual total across all 5 is already at the limit. No single counter ever crosses 100, and the effective limit for that client is 5x what was configured.

A dedicated service fixes that: one shared source of truth means the count is finally global. But it adds a full round trip to a separate service on every request, purely to ask "was this one allowed?" The gateway-integrated approach gets the same global correctness by talking to Redis directly from the gateway — a call the gateway needs to make either way, since it's already the thing deciding whether to forward the request. There's no separate rate-limiting service to add a hop to, deploy, or monitor on its own.

Chosen: gateway-integrated. That's why the diagram below draws the check as a step inside the gateway's own path through the request, not a detour to another service.

The check itself

The simplest working version is a fixed window: increment a Redis counter keyed by identifier and the current window, set to expire at the end of the window on the first increment of each window, and reject once the count exceeds the limit. Redis's atomic INCR means two concurrent requests for the same identifier can't both read a stale count and both get admitted — the increment itself is the check, with nothing to coordinate around it.

This is the same publicly-documented pattern behind APIs that expose their own rate limit state in response headers (a remaining/reset pair, the way a well-known payments API does) — the client-facing shape mirrors what the limiter itself has to track internally.

A fixed window is a fine starting point, but it has a real gap worth naming before it becomes the shipped version — which is exactly what the trade-offs below work through.

Trade-offs

Two decisions are worth defending if your interviewer pushes: which window algorithm to use, and whether a sliding window is even the right shape of algorithm compared to the alternative most real APIs reach for instead.

• Fixed window vs. sliding window counter: a fixed window is simple — one counter per identifier per window — but allows up to 2x the limit across a window boundary (a burst at 0:59 and another at 1:01 both pass, because they land in different windows). A sliding window counter approximates a true sliding log by weighting the previous window's count proportionally to how much of it overlaps the current moment, closing that gap at a small accuracy cost. Chosen: sliding window counter as the default, since the boundary-burst problem is a real gap for a limiter whose whole job is precision.

• Sliding window log (exact) vs. counter (approximate): an exact log — one timestamp stored per request — gives perfect accuracy, but costs memory proportional to the limit itself (a 10,000-request limit means up to 10,000 stored timestamps per identifier). The counter approximation trades a small amount of that accuracy for a fixed, tiny footprint — two counters per identifier, regardless of how high the limit is.

  That trade isn't just theoretical. At least one large CDN operator has published production numbers for exactly this approximation, measured against a true sliding log across hundreds of millions of real requests: on the order of a few percent average difference between the estimated and actual rate, and well under 1 in 10,000 requests ending up allowed or rejected incorrectly as a result. Rejected for this design's scale: at 10,000 concurrent identifiers, the exact log's memory footprint is a meaningfully larger cost than the counter's, for a level of precision the NFRs don't require — and that real-world error rate shows the extra precision isn't buying much even where it's been measured at real scale.

• Sliding window counter vs. token bucket: token bucket works differently from every algorithm above. Each client gets a bucket holding a maximum number of tokens (its burst capacity); tokens refill at a steady rate; every request spends one, and gets rejected if none are left. The real upside: a client that's been idle can burst — spend a pile of saved-up tokens all at once — while a client sending a slow, steady drip never runs dry, since it's never spending faster than the refill rate replenishes. That's not just theoretical: a well-known payments API runs token bucket in production specifically because its traffic is bursty by nature — a client scripting a quick batch of calls after being idle is normal, not abuse — and a hard per-window cap would reject legitimate spikes a token bucket absorbs for free.

  The real cost is on the state-update side. A sliding window counter's entire check is one atomic INCR — Redis does the read, increment, and write as a single indivisible step, so there's nothing to coordinate. A token bucket's check is read-then-compute-then-write: read the current token count and last refill time, compute how many tokens should have accrued since then, then write the new count back. Two gateway instances doing that at the same instant can both read the same starting token count, both compute "yes, a token's available," and both allow a request that should have exhausted the bucket after the first one — the exact race a single INCR has no room for. Fixing it means wrapping the whole read-compute-write sequence in one atomic unit — a Redis Lua script, not a single command. If you've never written one, don't worry — you don't need to reproduce it in an interview, just understand what it buys you: the entire sequence runs as one indivisible step, the same guarantee INCR gives you for free.

  Chosen: sliding window counter. Nothing in this design's FRs calls for letting an idle client bank unused quota and spend it in one burst later — the requirement is a clean, predictable cap that closes the boundary-burst loophole, not intentional burst tolerance. Given that, the simpler atomicity story (one INCR, no Lua script) is the better fit for the sub-5ms p99 NFR. If a future requirement specifically wanted burst tolerance — a client that legitimately needs to fire off a quick batch after sitting idle — that's exactly the case where token bucket would earn its extra complexity back.

Final Design

Put every piece from above together and this is the shape it settles into:

Each piece here scales — or doesn't need to — on its own terms:

• API Gateway instances scale horizontally behind a load balancer. None of them hold any rate-limit state themselves, so adding more instances never changes the answer to "is this client over the limit."
• Redis is the one piece every gateway instance shares. See the Follow-Up Questions below for what changes once its throughput — not the traffic it's gating — becomes the bottleneck.
• Backend Service never sees a request that was already going to be rejected, which is the entire point of checking at the gateway instead of after.

Operations & Observability

A rate limiter that only gets exercised in tests isn't finished — you need to know, in production, whether it's protecting the system or quietly breaking it for legitimate clients. Naming this without being asked is a senior/staff-level signal here, same as on every other design in this series.

Watch the rejected-request (429) rate, broken out by identifier and tier first — not just a global count, since a global spike could mean one abusive client or a limit set too strict for everyone, and those call for very different responses. Pair it with the near-threshold-but-allowed rate (the share of requests landing in, say, the last 10% of a client's quota) — a client trending toward that line is an early warning, both for reaching out before they start seeing 429s and for confirming the sliding window's weighting is actually behaving the way Trade-offs above assumed.

Watch Redis check latency (p99) directly, separate from overall API latency — since this check sits on the hot path of every single request, a creeping p99 here degrades every request the gateway handles, rate-limited or not, which is exactly the risk the sub-5ms NFR exists to catch early.

One subtler metric, specific to a sliding window: clock skew across gateway instances. The window key (rate:{id}:{window}) is only correct if every gateway instance agrees on which window "now" falls into. If two instances' clocks drift apart near a window boundary, they can write to two different window keys for what should be the same moment — silently splitting one client's count across two counters and letting them through at up to double the configured limit, without either counter ever looking wrong on its own.

Level Expectations

Mid-level: implements the fixed-window version correctly, understands why the increment needs to be atomic rather than a read-then-write, and — with a little prompting — can explain why the check runs at the gateway rather than inside each backend server.

Senior: proactively raises the window-boundary burst problem and proposes the sliding window counter without being asked, can weigh sliding window counter against token bucket by naming a real reason a client might prefer one over the other rather than asserting a single "right" answer, and names the rejected-request rate and Redis check latency as what they'd actually watch in production, not just what they'd build.

Staff: reasons about what happens when Redis itself is unavailable — whether the limiter fails open (risk: an outage becomes an abuse window) or fails closed (risk: an outage becomes a full API outage) — and can argue for one over the other given the system's actual risk profile. Additionally reasons about what changes once a single Redis node's throughput, not the traffic being gated, becomes the bottleneck, and can connect clock-skew- driven window-key drift to why it matters more once that scale is reached.

Follow-Up Questions

Try It Yourself