Rate Limiting

important mid · part of Skills & Topics · Senior SWE Roadmap · related: API Design · Load Balancing · Design a Rate Limiter

Why rate limit

A rate limiter caps how many requests a client (a user, an API key, an IP, or the system as a whole) can make in a given time window. It exists to solve a handful of distinct problems, worth naming explicitly in an interview rather than lumping together as “prevent abuse”:

• Protect against abuse: brute-force login attempts, scraping, denial-of-service (intentional or accidental).
• Enforce a pricing/product tier: free-tier users get 100 requests/day, paid users get 100,000.
• Protect downstream systems: a database or third-party API that can only handle N requests/sec regardless of who’s asking — the limiter protects the system, not just fairness between clients.
• Fairness / noisy-neighbor protection: one client’s burst shouldn’t degrade latency for every other client sharing the same infrastructure.

Token bucket

A bucket holds up to capacity tokens. Tokens are added at a fixed refill_rate (e.g., 10/sec) up to capacity. Each incoming request consumes one token; if the bucket is empty, the request is rejected (or queued, depending on design).

flowchart TB
    subgraph Bucket["Token bucket (capacity = 10)"]
        direction TB
        T["●●●●●●●○○○<br/>7 tokens currently available"]
    end
    Refill["Refill: +1 token / 100ms<br/>(stops adding at capacity)"] -.fills.-> Bucket
    Req["Incoming request"] -->|"consumes 1 token<br/>if available"| Bucket
    Bucket -->|"token available"| Allow[Request allowed]
    Bucket -->|"bucket empty"| Reject["Request rejected (429)"]

• Allows bursts: if the bucket has been idle and full, a client can legitimately fire capacity requests instantly — this is a feature, not a bug (handles legitimate bursty traffic like a page load firing several API calls at once).
• Long-run rate is bounded by refill_rate regardless of burst — you can’t sustain more than the refill rate over time, you can only spend saved-up capacity faster than that in short bursts.
• Two tunable parameters (capacity, refill_rate) map directly and intuitively to product requirements (“allow bursts up to 20, sustained max 5/sec”) — this is why it’s the most commonly used algorithm in real systems (AWS, Stripe, and most API gateways use a token-bucket variant).

Leaky bucket

Requests enter a queue (the “bucket”) of fixed size and are processed (leak out) at a constant fixed rate, regardless of how bursty the input was. If the queue is full when a request arrives, it’s dropped.

flowchart TB
    In["Incoming requests<br/>(bursty arrival)"] --> Q["Queue / bucket<br/>(fixed capacity)"]
    Q -->|"queue full"| Drop["Request dropped"]
    Q -->|"leaks out at constant rate<br/>(e.g., 5 req/sec, always)"| Out["Processed request"]

• Smooths traffic to a constant output rate — downstream always sees exactly leak_rate, never a burst. This is the key difference from token bucket, which lets bursts pass through immediately as long as tokens are available.
• Better fit when the downstream system genuinely cannot handle any burst at all (e.g., a fixed-capacity worker pool) — token bucket protects against sustained overuse but still lets a burst hit the backend instantly; leaky bucket never does.
• Worse fit when legitimate clients are naturally bursty and burst absorption (not just eventual smoothing) is desired — a burst just queues and adds latency, or gets dropped if the queue’s full.

	Token bucket	Leaky bucket
Burst handling	Allows burst up to capacity, immediately	Queues/smooths, no burst passed through
Output rate	Variable, up to instantaneous burst	Constant, fixed
Typical use	API rate limiting (most common)	Traffic shaping in front of a fixed-capacity resource

Fixed window, sliding window log, sliding window counter

Fixed window counter

Count requests in discrete, non-overlapping windows (e.g., “requests this calendar minute”). Simple: one counter per window, reset at window boundary.

The boundary-burst problem, made concrete: limit = 100 requests/minute. A client sends 100 requests at 23:59:59.9 (all counted in the window ending at 00:00:00) and another 100 requests at 00:00:00.1 (all counted in the next window). Both batches are individually within the limit — but the system just absorbed 200 requests in a 200ms span, double the intended rate.

flowchart LR
    subgraph W1["Window 1: 23:59:00 – 23:59:59 (limit 100)"]
        R1["100 requests<br/>at 23:59:59.9"]
    end
    subgraph W2["Window 2: 00:00:00 – 00:00:59 (limit 100)"]
        R2["100 requests<br/>at 00:00:00.1"]
    end
    W1 --> Edge["200ms span straddling the boundary"]
    W2 --> Edge
    Edge --> Burst["200 requests actually allowed in ~200ms<br/>= 2x the intended rate"]

Simple and cheap (one integer counter per client per window), but this burst is a real exploitable gap, not a theoretical one — a client that knows the window boundary can deliberately time a double-burst around it.

Sliding window log

Store a timestamp for every request in a sorted structure (e.g., a Redis sorted set). On each new request: drop all timestamps older than now - window, count what’s left, allow if under limit, then add the new timestamp.

• Fully accurate — no boundary artifact, the window is always exactly “the last N seconds” measured continuously.
• Cost: O(window size) storage per client (one entry per request in the window) and O(log n) or O(n) work per check — expensive at high request volume.

Sliding window counter (approximation)

A practical middle ground: keep counts in fixed windows (like fixed-window counter), but weight the previous window’s count by how much it overlaps the current sliding window.

estimated_count = current_window_count + previous_window_count × (overlap_fraction)

Example: limit 100/min, currently 30% into the current window, previous window had 80 requests, current window has 20 so far → estimated = 20 + 80 × 0.7 = 76 — under the limit, request allowed. This assumes uniform distribution of requests within the previous window, which is an approximation, not exact — but it’s cheap (two counters, not a log of timestamps) and eliminates the sharp boundary-burst exploit almost entirely in practice. This is what most production rate limiters (Cloudflare, Kong, many API gateways) actually implement — it’s the sweet spot of accuracy vs cost.

Algorithm	Accuracy	Memory cost	Boundary burst?
Fixed window	Low	O(1) per client	Yes, up to 2x
Sliding window log	Exact	O(requests in window)	No
Sliding window counter	Approximate	O(1) per client	Effectively no
Token bucket	Exact, burst-tolerant by design	O(1) per client	N/A (burst is intentional, bounded by capacity)

Distributed rate limiting

Rate limiting is trivial on a single machine (an in-process counter). It gets hard the moment there’s more than one app server — the whole point of a rate limit (“this client gets 100/min total”) is violated if each of 10 servers independently allows 100/min, giving the client 1000/min in aggregate.

The naive approach and its race condition

The obvious fix: move the counter into a shared store (Redis) that every server hits. The naive implementation:

count = INCR(key)
if count == 1:
    EXPIRE(key, window_seconds)
if count > limit:
    reject

This has a real race: INCR and EXPIRE are two separate round trips. If a server crashes or is slow between them, the key can end up with no TTL set (leaking forever) or, more subtly, concurrent requests hitting INCR at the same instant can both read counts that momentarily allow overshoot depending on how the surrounding check-then-act logic is written outside a transaction.

sequenceDiagram
    participant S1 as App Server 1
    participant S2 as App Server 2
    participant R as Redis

    Note over R: key "user:42:count" doesn't exist yet
    S1->>R: INCR user:42:count
    R-->>S1: 1
    S2->>R: INCR user:42:count
    R-->>S2: 2
    Note over S1: about to call EXPIRE...
    Note over S1,S2: if S1 crashes here, key never gets a TTL —<br/>it counts forever instead of resetting each window
    S1->>R: EXPIRE user:42:count 60

The fix: atomicity

Two standard fixes, both making the whole check-and-increment sequence atomic:

1. Lua script (EVAL) — Redis executes a Lua script as a single atomic operation, no other command can interleave:

local count = redis.call("INCR", KEYS[1])
if count == 1 then
    redis.call("EXPIRE", KEYS[1], ARGV[1])
end
if count > tonumber(ARGV[2]) then
    return 0  -- reject
end
return 1  -- allow

This is the standard production pattern — one round trip, no race, and it implements fixed-window counting directly.

2. Sorted-set based sliding window — for a true sliding window log, use ZADD/ZREMRANGEBYSCORE/ZCARD wrapped in a Lua script or a MULTI/EXEC transaction:

sequenceDiagram
    participant App as App Server
    participant R as Redis

    App->>R: MULTI
    App->>R: ZREMRANGEBYSCORE key 0 (now - window)
    App->>R: ZADD key now now  (score = timestamp)
    App->>R: ZCARD key
    App->>R: EXPIRE key window
    App->>R: EXEC (atomic — all or nothing)
    R-->>App: count = ZCARD result
    Note over App: if count > limit, reject<br/>(optionally ZREM the entry just added)

Each member of the sorted set is one request timestamp; ZREMRANGEBYSCORE prunes anything outside the current sliding window before counting, giving an exact sliding-window-log result with Redis doing the heavy lifting atomically.

Key interview point: any distributed rate limiter that does a separate read-then-write against a shared store without atomicity (Lua script, MULTI/EXEC, or a single atomic command like INCR) has a race condition under concurrent load — this is the detail that separates a strong answer from a hand-wavy “just use Redis.”

Where to enforce it

Layer	Pros	Cons
Edge / API gateway (e.g., Kong, Envoy, cloud API Gateway)	Protects the whole system uniformly; stops abusive traffic before it consumes any backend resources; one place to configure/monitor	Coarse-grained — hard to apply different limits per internal operation cost
Per-service	Fine-grained — a service can rate-limit based on its own actual capacity/cost per request (e.g., an expensive search endpoint vs a cheap health check)	Duplicated logic across services; a client can still overwhelm a specific expensive service if the gateway-level limit is loose
Both (layered)	Gateway does coarse global/per-user limiting; hot/expensive endpoints add their own tighter limit	More moving parts to keep consistent

Common real-world answer: enforce a broad limit at the gateway/edge (cheap, stops obvious abuse immediately, protects shared infrastructure like load balancers and connection pools) and layer tighter, endpoint-specific limits per service for operations that are disproportionately expensive.

What to return to the client

• HTTP 429 Too Many Requests — the correct status code, not a generic 500 or a silent drop.
• Retry-After header — tells the client how long to wait before retrying (seconds, or an HTTP date). Well-behaved clients back off accordingly instead of hammering immediately.
• Rate limit headers (de facto convention, not a single RFC standard, but widely adopted — X-RateLimit-* or the newer standardized RateLimit-*):
  • X-RateLimit-Limit: the ceiling for the current window.
  • X-RateLimit-Remaining: how many requests are left.
  • X-RateLimit-Reset: when the window resets (Unix timestamp or seconds).
• Returning these headers on every response (not just 429s) lets well-behaved clients self-throttle proactively instead of finding the limit by trial and error — a meaningfully better API design, worth mentioning in API Design contexts too.

Multi-tier limits

A senior-level nuance often missed: real systems need more than one limit active simultaneously, at different scopes:

• Per-user limit: “this user gets 100 requests/min” — fairness between users.
• Per-IP limit: catches abuse from unauthenticated or spoofed-identity traffic that a per-user limit can’t see.
• Global/system limit: “this endpoint can handle 10,000 requests/sec total, no matter who’s asking” — protects the actual downstream capacity (a database, a third-party API with its own rate limit) regardless of how fairly traffic is distributed among users.

flowchart TD
    Req[Incoming request] --> L1{"Per-user limit<br/>ok?"}
    L1 -->|no| R1["429: user rate limited"]
    L1 -->|yes| L2{"Per-IP limit<br/>ok?"}
    L2 -->|no| R2["429: IP rate limited"]
    L2 -->|yes| L3{"Global system limit<br/>ok?"}
    L3 -->|no| R3["429: system overloaded<br/>(protect downstream regardless of who's asking)"]
    L3 -->|yes| Allow[Request proceeds]

Every layer must pass — a single well-behaved user can still get throttled if the system is globally overloaded, which is a deliberate and correct design choice (protecting shared infrastructure trumps any individual client’s fair share once the system is saturated). This is also why a rate limiter for a large system is rarely “one algorithm” — it’s a token-bucket-per-user check composed with a system-wide circuit breaker/limit underneath it.

Interview angles

• “Design a rate limiter” is a standalone system design question (see Design a Rate Limiter) — know the four core algorithms (token bucket, leaky bucket, fixed window, sliding window) cold, including their concrete failure modes, not just their names.
• “How would you rate-limit across multiple servers?” — the natural, harder follow-up. A strong answer names the shared-store approach (Redis), then immediately raises the atomicity race condition unprompted and names the fix (Lua script / atomic transaction) — this is the single detail that most distinguishes a senior answer here.
• “Show me the boundary-burst problem concretely” — be ready to work through a numeric example (as above: 100+100 straddling a minute boundary = 200 in ~200ms) rather than describing it abstractly.
• “What does the client see when they’re rate limited?” — 429, Retry-After, and the X-RateLimit-*/RateLimit-* header convention; bonus for mentioning these headers should appear on successful responses too.
• “A single user is well within their limit but the system is falling over — what happened?” — multi-tier limits: a per-user limit alone doesn’t protect against aggregate load across all users; needs a global/system-level limit as well.
• “Token bucket or leaky bucket — which do you pick?” — token bucket by default (matches how real traffic bursts, e.g. a page load), leaky bucket when the downstream resource genuinely cannot tolerate any burst at all.

My Notes