1. The Gatekeeper: Why We Rate Limit

1.1 System Availability Boundaries

APIs are backed by limited physical resources: database connection pools, thread executor pools, CPU cycles, and network bandwidth. If a single client (or an array of bot nodes) makes 10,000 requests per second, the backend databases will saturate, blocking legitimate users. A rate limiter intercepts incoming HTTP requests at the gateway level, validating client identifiers (such as API keys or IP addresses) against active rate limits.

If the request rate is within parameters, the gatekeeper passes the thread forward. If the client has exceeded their quota, the limiter blocks the request, returning an HTTP status code 429 Too Many Requests with a Retry-After response header.

1.2 Rate Limiting vs Request Throttling

Rate limiting drops exceeding traffic immediately (hard constraint). Request throttling queues exceeding traffic, slowing down delivery rates to match backend processing capacity (soft queue constraint).

Common Misconception — Rate limiting guarantees absolute DDoS protection: A common developer misconception is that rate limiters protect against all DDoS attacks. In reality, a rate limiter protects application layers from exhaustion, but it cannot prevent network-level volumetric attacks (such as SYN floods or DNS amplification) from saturating ingress internet pipes. Volumetric protection must be handled at the DNS/network level (e.g. Cloudflare or AWS Shield).

2. The Token Bucket Algorithm

2.1 Burst Capacity Dynamics

The Token Bucket algorithm is the most popular rate-limiting structure, utilized in platforms like Amazon Web Services (API Gateway) and Stripe. The algorithm models a bucket of capacity $B$ that holds tokens. Tokens are continuously added to the bucket at a constant rate of $r$ tokens per second. When a request arrives, the limiter checks if the bucket contains at least one token. If present, the token is consumed, and the request is passed forward. If the bucket is empty, the request is blocked.

Because the bucket can hold up to $B$ tokens, the system naturally allows short bursts of traffic (up to $B$ concurrent requests) before clamping the transmission rate to the steady-state replenishment speed $r$.

Mermaid Diagram: The logical decision flow of the Token Bucket rate limiter, showing token generation and consumption.

3. The Leaky Bucket Algorithm

3.1 Egress Smoothing Heuristics

The Leaky Bucket algorithm is an alternative approach that smooths outgoing traffic rates. The algorithm models a bucket with a small hole at the bottom. Requests arrive and are appended to a FIFO queue (the bucket capacity $B$ represents the maximum queue size). If the queue is full, incoming requests are dropped immediately.

Requests leak out of the bottom of the bucket at a constant rate $r$, moving forward to the application threads. Unlike the Token Bucket (which allows bursts), the Leaky Bucket enforces a rigid, constant processing speed, smoothing output spikes regardless of input volume fluctuations.

4. Fixed Window Counter Algorithm

4.1 Time Boundary Counters

The Fixed Window Counter algorithm divides timeline ranges into static blocks (e.g. 1-minute windows starting at 12:00:00, 12:01:00). Each window maintains a request counter. When a request arrives, the limiter increments the current window's counter. If the counter exceeds the allowed limit, subsequent requests are blocked until the next window boundary begins, which resets the counter to 0.

While extremely simple to implement and memory-efficient, Fixed Window counters suffer from a major design flaw: traffic spikes at window boundaries. A client can send their entire quota at the end of window $N$ and another full quota at the start of window $N+1$, doubling the allowed rate in a short time frame.

5. Sliding Window Log and Sliding Window Counter

5.1 Eliminating Boundary Spikes

To solve the boundary spike problem, systems implement sliding windows. The **Sliding Window Log** maintains a sorted set of request timestamps for each client. When a request arrives, the limiter deletes all timestamps older than the sliding window size (e.g. 1 minute ago). It then counts the remaining timestamps. If the log size is below the limit, the current timestamp is appended, and the request is passed forward. While accurate, keeping all timestamps in memory requires substantial RAM.

The **Sliding Window Counter** approximates this with low memory. It combines the count of the previous window and the current window, calculating a weighted average based on the current progress through the active window. This provides smooth rate-limiting boundaries with minimal memory footprint.

5.2 Redis Sorted Sets and Sliding Log Memory Calculations

To implement a Sliding Window Log in Redis, we represent each client's window using a **Sorted Set (ZSET)**. The score and value of each element in the set are both set to the request's Unix timestamp. When a request arrives at time $t_{\text{now}}$, the limiter executes a multi-command atomic transaction block:

• **Step 1**: Remove all elements with scores older than the sliding threshold ($t_{\text{now}} - W$):

• **Step 2**: Count the remaining elements in the sorted set:

• **Step 3**: If current_requests is less than the limit, log the current request and set key expiry:

While this provides perfect precision, its memory overhead is high. Each entry in a Redis sorted set contains internal pointers and metadata. For a system processing $N = 10,000$ requests per client window, storing 64-bit timestamps in a skip-list structure requires approximately:

If the system has 10,000 active clients, the rate-limiting keys will consume over 6.4 GB of Redis memory. The **Sliding Window Counter** reduces this footprint by only storing the request counts for the current and previous windows (2 integer variables per client), requiring less than 80 bytes per client. Below is a comparison table of sliding window strategies:

Pitfall — Sub-second sliding log performance: Inserting elements into Redis sorted sets has $O(\log N)$ complexity. If a client generates a massive burst of requests, the insertion search latency inside the skip-list increases, creating CPU spikes in the single-threaded Redis process. Prefer sliding window counters for extremely high-frequency endpoints.

6. Distributed Rate Limiting: Redis and Lua Scripting

6.1 Atomic Cache Mutations

In distributed microservices, APIs are served by multiple application nodes. If each node tracks rate limits locally, a client can bypass restrictions by round-robining requests across servers. We must maintain the rate-limiting state in a central cache, typically Redis.

However, querying the count, verifying limits, and incrementing values from multiple servers introduces race conditions. To prevent this, developers use **Lua Scripts** executed directly inside Redis. Because Redis runs Lua scripts atomically, the entire check-and-set sequence is isolated from other clients, preventing rate limit bypasses without requiring expensive distributed locks.

6.2 Distributed Race Conditions and Production Lua Script Implementation

When multiple server nodes update a shared Redis counter, they perform a **Read-Modify-Write** cycle. Suppose a client has a rate limit of 100 requests per minute and currently has 99 requests logged in Redis. If two requests from this client hit different server nodes (Node A and Node B) at the same millisecond, the following sequence occurs under non-atomic operations:

• **Step 1**: Node A queries Redis for the current count $\Rightarrow$ receives 99.
• **Step 2**: Node B queries Redis for the current count $\Rightarrow$ receives 99.
• **Step 3**: Node A evaluates $99 < 100 \Rightarrow$ approves request and increments Redis count to 100.
• **Step 4**: Node B evaluates $99 < 100 \Rightarrow$ approves request and increments Redis count to 101.

Both requests were allowed, bypassing the rate limit threshold. We prevent this by consolidating the read, evaluation, and increment operations into a single atomic execution block using Redis's embedded Lua interpreter. Redis is single-threaded, meaning it executes the entire Lua script sequentially without interruption from other concurrent commands.

Below is the production-grade Lua script for an atomic Token Bucket rate limiter, utilizing lazy replenishment parameters passed from the server node:

By executing this script via the Redis EVALSHA command, database overhead is minimized. Below is a comparison table of distributed coordination options:

Pitfall — Lua Script blocking inside Redis clusters: Because Redis is single-threaded, if a Lua script contains infinite loops or executes expensive operations (like iterating over large sorted sets using KEYS), it blocks all other incoming Redis queries. Keep Lua scripts simple, localized to single keys, and avoid large iterations.

7. Advanced: Sliding Window Counter Mathematical Interpolation

7.1 Overlapping Weight Equations

The Sliding Window Counter algorithm estimates the active request rate by interpolating between the previous window count and the current window count. Let $W$ be the sliding window duration (e.g. 60 seconds). Let $C_{\text{prev}}$ be the total requests logged during the previous window, and let $C_{\text{curr}}$ be the count in the current window.

Let $t_{\text{elapsed}}$ be the number of seconds elapsed since the start of the current window. The weight of the current window is $t_{\text{elapsed}} / W$, and the remaining weight attributed to the previous window is $1 - (t_{\text{elapsed}} / W)$. The estimated request count $C_{\text{est}}$ is calculated as:

If $C_{\text{est}}$ is less than the client's rate limit threshold $L$, the request is allowed, and $C_{\text{curr}}$ is incremented by 1. For example, if a client has a limit of 100 requests per minute, and in the previous minute they sent 80 requests ($C_{\text{prev}} = 80$), and in the current minute (30 seconds in, $t_{\text{elapsed}} = 30$) they have sent 10 requests ($C_{\text{curr}} = 10$), the estimated count is:

Because $50 < 100$, the request is approved. This mathematical interpolation provides an excellent approximation of the sliding window log with a constant $O(1)$ memory requirement of only two counter variables per client.

8. Advanced: Comparison of Rate Limiting Algorithms

8.1 Algorithmic Performance comparison

The table below compares the implementation complexity, memory footprint, and burst handling behavior of primary rate-limiting algorithms:

Pitfall — Memory exhaustion in sparse logs: If you use Sliding Window Logs to track rate limits for thousands of guest clients, storing individual 64-bit Unix timestamps for each request will exhaust Redis memory quickly. Evacuate inactive logs using Redis TTLs, or transition to Sliding Window Counters to protect cluster memory.

9. Complete Token Bucket Rate Limiter in JavaScript

9.1 Lazy Replenishment Class

The following JavaScript class implements a Token Bucket rate limiter, calculating replenishment lazily during request evaluations to bypass CPU-intensive cron tickers:

10. Interactive: Token Bucket Rate Limiter

Click "Send Request" to consume a token. Click "Replenish" to manually simulate the lazy refill interval:

Latency Overhead of Distributed Rate Limiters

The chart below compares the latency overhead (in milliseconds) added to API requests by different rate-limiting storage architectures:

12. Frequently Asked Questions