Q31 — How does rate limiting work — and what are the failure modes of each algorithm?

Why does rate limiting exist?

Rate limiting caps how many requests a client (user, IP address, API key, service) can make in a given time window. Without it, a single client can consume an unlimited share of your resources — intentionally (abuse, scraping, DDoS) or accidentally (a buggy client in a retry loop, a misconfigured integration).

There are three distinct reasons to rate limit, and they imply different designs:

Abuse prevention: Stop a malicious actor from overwhelming your service. The constraint is per-client.

Fair use enforcement: Ensure no single client degrades the experience for others. Even legitimate customers shouldn't be allowed to monopolize capacity.

Capacity protection: Match request volume to what your backend can actually handle. Even if no individual client is malicious, total traffic can exceed capacity. This is flow control at the API layer.

Every rate limiting algorithm is a trade-off between accuracy, memory usage, fairness, and how well it handles bursts.

Fixed window counter — simple but has a boundary problem

The most intuitive approach: count requests within a fixed time window (say, 60 seconds). When the count exceeds the limit, reject requests. At the end of each window, reset the counter.

Implementation: counter[client_id][current_minute]++. If counter > limit, reject.

Why it's simple: One integer per client per window. Near-zero memory overhead. Easy to implement in Redis with INCR and EXPIRE.

The boundary problem: Suppose the limit is 100 requests per minute. A client sends 100 requests from 12:00:59 to 12:00:59 (filling the 12:00 window). The window resets at 12:01:00. The same client sends 100 more requests from 12:01:00 to 12:01:01. In a two-second span straddling the window boundary, the client sent 200 requests — double the limit — and both batches were accepted.

The fixed window treats the world as a sequence of discrete, non-overlapping buckets. Real traffic doesn't care about your bucket boundaries.

Sliding window log — accurate but memory-intensive

Fix the boundary problem by tracking exact timestamps: store a log of all request timestamps for each client, and count how many fall within the last 60 seconds.

On each request: append the current timestamp to the client's log, remove timestamps older than 60 seconds, count remaining entries, accept or reject based on the count.

Why it's accurate: The window always looks at exactly the last N seconds, not a fixed calendar window. There is no boundary artifact — the rate limit applies uniformly at every moment.

The memory problem: Every request timestamp must be stored. A client allowed 100 requests per minute and making exactly 100 requests per minute has 100 timestamps in memory. Scale to 1 million clients and you have 100 million stored timestamps — significant memory pressure. For high-traffic public APIs with large client populations, this is impractical.

Sliding window counter — the practical compromise

Combine the efficiency of fixed windows with an approximation of sliding window accuracy. Keep two counters: the current window and the previous window. When evaluating a request, compute a weighted count:

estimated_count = previous_window_count × (1 - elapsed_fraction) + current_window_count

If we're 70% through the current minute, the estimate weights the previous window at 30% (how much of it overlaps the last 60 seconds from now) and the current window at 100%.

Why this works: It approximates the sliding window calculation without storing individual timestamps. Memory usage is O(1) per client (two counters). The approximation has a small error (at most a few percent) under typical traffic patterns — acceptable for rate limiting, where precision to the exact request is not critical.

This is what Cloudflare and many large-scale rate limiters use. The small accuracy loss is worth the enormous memory savings.

Token bucket — smooth rate with burst tolerance

Token bucket is the algorithm most APIs actually use for per-client rate limiting, because it handles bursts in a principled way.

Conceptually: each client has a bucket that holds tokens. Tokens refill at a fixed rate (e.g., 10 tokens per second). Each request costs one token. If the bucket is empty, the request is rejected.

Key property: clients can accumulate tokens during quiet periods and spend them in bursts. A client that makes no requests for 10 seconds accumulates 100 tokens (up to the bucket's maximum capacity, say 100). They can then fire 100 requests instantly. The bucket limits the sustained rate (tokens per second) while allowing short bursts up to the bucket size.

This matches real-world usage patterns. A well-behaved API client might be idle for seconds, then fire a batch of requests, then be idle again. Rejecting the burst as "rate exceeded" when the client has been idle is overly harsh — the token bucket allows it if the client has accumulated capacity.

The failure mode: A client that continuously drains its bucket at exactly the refill rate will never be rejected. The token bucket is a rate limiter, not an instantaneous cap. It prevents sustained high rates but cannot prevent very short bursts at the beginning of a period.

Leaky bucket — smooth output, input queue

The leaky bucket is the inverse of token bucket in philosophy. Instead of smoothing the rate by letting bursts happen, it smooths the rate by queuing bursts and processing them at a fixed rate.

Conceptually: requests enter a bucket (queue) from the top at any rate. Requests leave the bucket at the bottom at a fixed, constant rate. If the bucket overflows (queue is full), incoming requests are dropped.

Why it's useful: The output is always perfectly smooth — exactly N requests per second, no matter what the input looks like. Useful when the downstream cannot handle any bursts and requires perfectly metered input (rate-limited external APIs, hardware interfaces).

The failure mode: Queuing introduces latency. A burst of requests doesn't fail fast — it waits in the queue. Under sustained overload, queue depth grows and latency climbs before requests finally get dropped when the queue fills. If your SLA requires fast failures on overload rather than delayed processing, the leaky bucket is the wrong choice.

Where to implement rate limiting — and the distributed problem

Rate limiting can live at multiple layers:

API gateway / load balancer: Centralized, sees all traffic, can enforce limits across all instances. The natural place for per-client rate limits. Tools like Kong, Nginx, Envoy, and AWS API Gateway have built-in rate limiting.

Application layer: The service itself enforces limits. More flexibility (per-endpoint limits, logic tied to business rules), but requires coordination across service instances.

The distributed coordination problem: If you have 10 service instances and each maintains its own rate limit counter, a client can send 10 requests per second to each instance — 100 total — while each instance believes the client is within the 10 req/s limit. Per-instance counters don't give you per-client global limits.

Solution: centralized counter store (Redis). Each instance increments a shared Redis counter for each client. INCR in Redis is atomic — no race conditions. The single counter represents the global client rate across all instances.

The cost: every request requires a Redis round trip (a few milliseconds). For high-throughput services, this overhead is non-negligible. Mitigation: local counters that periodically sync to Redis (approximate but fast), or consistent hashing so each client is always routed to the same service instance (which then handles rate limiting locally).

The mental model

Why rate limit: prevent abuse, ensure fairness, protect backend capacity

Fixed window:
  Cheap, simple: one counter per window
  Failure: boundary spike — 2x limit possible in 2 seconds straddling boundary

Sliding window log:
  Accurate: exact timestamps, true rolling window
  Failure: memory-intensive — one entry per request per client

Sliding window counter:
  Approximate but accurate enough: weighted blend of two windows
  Best balance of accuracy + memory → used at scale (Cloudflare etc.)

Token bucket:
  Fixed refill rate + burst capacity (bucket max)
  Handles real-world bursty clients naturally
  Most common for API rate limiting (Stripe, AWS, GitHub)
  Failure: allows initial burst up to bucket size

Leaky bucket:
  Queue input, smooth output at fixed rate
  Failure: queuing latency — slow failures, not fast ones

Distributed:
  Per-instance counters → bypass by hitting multiple instances
  Fix: centralized Redis counter (atomic INCR) → global limit
  Cost: Redis round trip per request → consider approximate local sync

Rate limiting is not a single algorithm — it's a choice of trade-offs between accuracy, memory, burst tolerance, and failure behavior. Knowing what each algorithm bets on lets you pick the one whose behavior matches what your system needs.