Rate Limiting

Why Rate Limiting Exists

Every API has a capacity ceiling. Whether that ceiling is set by CPU, memory, database connections, or downstream dependencies, there is a point beyond which additional requests degrade the experience for everyone. Rate limiting enforces that ceiling explicitly rather than letting the system discover it through failure.

Rate limiting serves three purposes. First, it protects backend services from being overwhelmed by a single client (intentionally or accidentally). Second, it ensures fair access across clients. Third, it provides a defense layer against abuse, including brute-force attacks, credential stuffing, and scraping.

The core question in rate limiting is simple: given a stream of incoming requests, how do you decide which ones to allow and which to reject? The answer depends on which algorithm you use.

Fixed Window Counter

The simplest approach. Divide time into fixed intervals (say, 1-minute windows). Maintain a counter per client per window. Increment on each request. If the counter exceeds the limit, reject.

The problem is boundary bursts. A client can send 100 requests at 12:00:59 and another 100 at 12:01:00. Both are within their respective windows, but the server just received 200 requests in 2 seconds. The fixed window sees two compliant windows. The server sees a spike.

Sliding Window Log

Instead of fixed intervals, keep a log of timestamps for each request. When a new request arrives, remove all timestamps older than the window size (e.g., older than 60 seconds). Count the remaining entries. If the count is at or above the limit, reject.

This eliminates the boundary burst problem entirely. The window slides with each request, so there is no artificial boundary to exploit. The cost is memory: you must store every request timestamp within the window. For high-volume APIs, this becomes expensive quickly.

Sliding Window Counter

A hybrid that approximates the sliding window without storing individual timestamps. It keeps counters for the current and previous fixed windows, then weights them based on how far into the current window you are.

If the previous window had 80 requests and the current window (30 seconds in, out of 60) has 40 requests, the estimated count is: 80 x 0.5 (remaining fraction of previous window) + 40 = 80. This gives you a reasonable approximation of a true sliding window at the memory cost of just two counters per client.

Token Bucket

The token bucket algorithm works by analogy. A bucket holds tokens up to a maximum capacity. Tokens are added at a fixed rate (the refill rate). Each request consumes one token. If the bucket is empty, the request is rejected.

The key property: the bucket can accumulate tokens during idle periods, up to its maximum capacity. This allows controlled bursts. A client that has been quiet for a while can briefly exceed the steady-state rate, up to the bucket's capacity, before being throttled back to the refill rate.

In practice, you do not run a background thread to add tokens. Instead, when a request arrives, you calculate how many tokens should have been added since the last request based on elapsed time. This is called "lazy refill" and is how most implementations work.

Leaky Bucket

The leaky bucket is the inverse. Requests enter a queue (the bucket). The queue drains at a fixed rate. If the queue is full, new requests are dropped.

Where the token bucket allows bursts up to the bucket capacity, the leaky bucket enforces a strictly uniform output rate. Bursts are absorbed by the queue rather than passed through. This is useful when your downstream dependency requires a constant request rate and cannot tolerate spikes at all.

Algorithm Comparison

Distributed Rate Limiting with Redis

A rate limiter running in a single process is straightforward. The challenge appears when your API runs on multiple servers behind a load balancer. Each server sees only a fraction of the total traffic. A per-server limit of 100 requests per minute, across 10 servers, means the actual limit is 1,000, not 100.

The standard solution is a centralized counter in Redis. Redis operations like INCR are atomic and fast (sub-millisecond). A typical pattern for a fixed window limiter:

1. Construct a key like ratelimit:{user_id}:{window_timestamp}.
2. INCR the key. If the result is 1 (first request in this window), set a TTL equal to the window size.
3. If the result exceeds the limit, reject with HTTP 429.

Race Conditions

The INCR-then-check pattern looks simple, but it has a race condition in the TTL step. Between the INCR and the EXPIRE commands, another request could arrive. If the process crashes between these two operations, the key persists forever with no expiry, and the client is permanently blocked.

The fix is to use a Lua script executed via Redis EVAL. Lua scripts in Redis are atomic: the entire script runs without interruption. This guarantees that the increment, the limit check, and the TTL set all happen as a single operation.

What Happens at Rejection

When a request exceeds the limit, the standard response is HTTP 429 (Too Many Requests). Good rate limiters also include response headers that help clients self-regulate:

• X-RateLimit-Limit: the maximum allowed requests in the window.
• X-RateLimit-Remaining: how many requests remain in the current window.
• X-RateLimit-Reset: the Unix timestamp when the window resets.
• Retry-After: how many seconds to wait before retrying.

These headers turn the rate limiter from a blunt wall into a communication channel. Well-behaved clients use them to back off gracefully rather than hammering the endpoint and collecting 429s.

Where to Place the Rate Limiter

Rate limiting can happen at multiple layers: the API gateway, a reverse proxy (Nginx, Envoy), a middleware layer in your application, or a dedicated service. The closer to the edge, the earlier you reject bad traffic and the less load reaches your application servers. Most architectures place the primary rate limiter at the API gateway or reverse proxy, with a secondary application-level limiter for business-logic-specific rules (e.g., "max 5 password attempts per hour").

Further Reading

• Build 5 Rate Limiters with Redis (Redis Official). Hands-on tutorial implementing all major algorithms with Redis and Lua scripts.
• Rate Limiting Algorithms Explained with Code (AlgoMaster). Clear code examples for each algorithm with complexity analysis.
• How to Build a Distributed Rate Limiting System Using Redis and Lua Scripts (freeCodeCamp). Covers the distributed case in detail, including race conditions.
• Rate Limiting Algorithms: System Design (GeeksforGeeks). Algorithm-by-algorithm breakdown with diagrams.