Design a Rate Limiter

A rate limiter controls how many requests a client can make in a given time window. Without one, a single bad actor (or a runaway client bug) can flood your servers, starving legitimate users and potentially crashing the system.

Three core use cases: (1) Prevent DoS/DDoS attacks — a user can write at most 2 posts per second; a device can create at most 10 accounts per day. (2) Reduce cost — for paid third-party APIs (payment processing, SMS, credit checks), each call costs money; rate limiting prevents runaway charges. (3) Protect server resources — bots and scrapers can overwhelm servers; rate limiting filters excess requests and keeps capacity available for real users.

Three options for placement:

Client-side: unreliable — clients can be forged or modified. Never use client-side limiting as the sole mechanism.

Server-side middleware: a dedicated rate limiting service sits in front of your API servers. When a request arrives, the middleware checks the client's rate counter. If the limit is exceeded, it returns HTTP 429 (Too Many Requests) and drops the request. Otherwise, it forwards the request to the API server. This is the most common production pattern.

API Gateway: cloud-native API gateways (AWS API Gateway, Nginx, Kong) have rate limiting built in. If you are already using an API gateway for authentication, SSL termination, and routing, enable rate limiting there to avoid deploying a separate service.

The choice depends on your technology stack. If you need fine-grained control over the algorithm, implement it server-side. If you want low operational overhead and your gateway supports the rules you need, use the gateway.

The token bucket is the most widely used rate limiting algorithm. Amazon and Stripe both use it. The concept: a bucket holds tokens up to a maximum capacity. Tokens are added to the bucket at a fixed refill rate (e.g., 10 tokens per second). Each incoming request consumes one token. If the bucket has tokens, the request proceeds. If not, the request is rejected.

Parameters: bucket size (maximum burst allowed) and refill rate (sustained throughput). A bucket size of 10 and refill rate of 2/second means a client can burst up to 10 requests instantly, then is limited to 2/second afterward.

Advantages: memory efficient (only two integers per bucket), allows bursting (good for legitimate burst traffic), easy to implement. Disadvantage: two parameters to tune — wrong values either block legitimate traffic or allow too much.

The leaking bucket processes requests at a fixed output rate, regardless of how quickly they arrive — like water leaking from a bucket at a constant drip. Implemented as a FIFO queue with a fixed size. Incoming requests join the queue. If the queue is full, the request is dropped. A processor drains the queue at a fixed rate (e.g., 5 requests/second).

Advantage: output is perfectly smooth — no bursts, which is ideal for use cases requiring stable outflow (e.g., payment processors, external API calls). Disadvantage: a burst of requests fills the queue with old requests; if they are not processed quickly enough, newer requests are dropped. Also two parameters to tune: queue size and outflow rate.

Divide time into fixed windows (e.g., one-minute windows at :00, :01, :02, ...). Each window has a counter starting at 0. Each request increments the counter. If the counter exceeds the limit before the window ends, new requests in that window are rejected. At the start of each new window, the counter resets.

Simple and memory efficient. The major flaw: a burst at the boundary of two windows can allow double the intended traffic. If the limit is 5 requests/minute and a client sends 5 requests at :59 and 5 more at :00 of the next minute, 10 requests go through in a 2-second span — twice the rate limit.

Eliminates the boundary problem of fixed windows by tracking the exact timestamp of each request. When a new request arrives, remove all timestamps older than the current window start, add the new timestamp, and check if the log size exceeds the limit.

Example: limit = 2 requests/minute. At 1:00:30, timestamps [1:00:01, 1:00:30] are in the log — size 2, allowed. At 1:00:50, add the timestamp — size 3, rejected. At 1:01:40, remove timestamps before 1:00:40 — log becomes [1:00:50], add 1:01:40 — size 2, allowed.

Advantage: accurate — never allows more than the limit in any rolling window. Disadvantage: memory intensive — rejected requests still occupy the log until they age out.

A hybrid that combines the memory efficiency of fixed window counters with the accuracy of sliding window logs. Formula: requests allowed = (requests in current window) + (requests in previous window) × (overlap percentage of rolling window and previous window).

Example: limit = 7/minute. Previous window had 5 requests. Current window has 3 so far. A new request arrives 30% into the current window. Rolling window request count = 3 + 5 × 0.7 = 6.5 ≈ 6 — below the limit, so the request is allowed.

Advantage: memory efficient (two counters), reasonably accurate. Disadvantage: the calculation is an approximation — it assumes requests in the previous window were evenly distributed, which may not be true. In practice, Cloudflare found only 0.003% of requests were incorrectly handled among 400 million requests.

In-memory stores (Redis) are the standard backing store for rate limiters because they are fast (sub-millisecond) and natively support atomic increment and expiry operations.

Two Redis commands enable rate limiting: INCR (atomically increment a counter for a key, e.g., "rate:user123:window:1625000000") and EXPIRE (set a TTL on the key so it automatically resets at the window boundary).

Architecture: the client sends a request → the rate limiter middleware fetches the counter from Redis → if below the limit, increment the counter and forward the request to the API server → if at or above the limit, return HTTP 429 with headers: X-RateLimit-Remaining (how many requests are left), X-RateLimit-Limit (the limit), and X-RateLimit-Retry-After (seconds until the window resets).

A single-server rate limiter is straightforward, but distributing it across many servers introduces two problems:

Race condition: two rate limiter servers read the same counter (value = 3), both check "3 < limit", both increment to 4, and both write 4 back to Redis. The counter should be 5. Fix: use Redis atomic operations (INCR is atomic) or Lua scripts to read-check-increment in a single atomic transaction.

Synchronization: if multiple rate limiter servers each maintain their own local state (not shared), a client routed to different servers on each request can exceed the limit. Fix: use a centralized data store (Redis) that all rate limiter instances share. Stateless rate limiters with a shared Redis backend is the standard production pattern.