Rate Limiting Algorithms
Explore token bucket, sliding window, and leaky bucket algorithms. Watch how rate limiters protect APIs by tracking and throttling request rates in real time.
Continue with the guided workspace
Use the paired workspace to connect this guide's mental model with live component state, visible signals, and the outcome each step or scenario is meant to prove.
Mental Model
Rate limiting protects APIs and services from overload by enforcing a threshold on how many requests a client can make in a given timeframe.
Instead of writing custom throttle code inside every microservice, rate limiting is usually implemented as a middleware component in an API Gateway. The gateway inspects incoming client headers (like IP address or API key), evaluates if the client has exceeded their quota using an algorithm like Fixed Window, Sliding Window, or Token Bucket, and either forwards the request to the backend or rejects it immediately.
graph TD
Client[Clients] -->|GET /api| GW[API Gateway / Rate Limiter]
GW -->|Query Counter / Key| Cache[(Redis Store)]
Cache -->|Counter Value| GW
GW -->|Under Limit: Forward| Server[Backend Server]
GW -->|Over Limit: Reject| ClientComponents and Why They Exist
Clients
Clients represent the external users or automated systems making requests to the API. Blue request particles depart the client node toward the Gateway and back off whenever they receive an HTTP 429 Too Many Requests throttle response.
Rate Limiter (API Gateway)
The rate limiter in the API gateway serves as the first line of defense protecting internal services. It tracks request counts per client IP or API token, evaluates the configured rate-limiting algorithm, admits green request particles to the backend while quota remains, and rejects red overflow particles with HTTP 429 errors once thresholds are exceeded.
Backend Servers
Backend servers execute core business logic and return API responses. Because the rate limiter sheds excess traffic at the perimeter gateway, the backend server node remains steady and processes only admitted requests even during sudden client bursts.
Redis Cache (Distributed Counter)
The Redis cache provides a fast, centralized store to share rate-limiting state across multiple gateway instances. Atomic counter lookup messages between the Gateway and Redis maintain shared request counts, timestamps, and TTL expirations so clients cannot bypass limits by hitting different gateway nodes.
Edge Cases and Misconceptions
Fixed Window Boundary Bursts
A major flaw in the Fixed Window algorithm is that it reset counters at exact calendar intervals (e.g., at 12:00, 12:01). If a limit is set to 10 requests per minute, a client can send 10 requests at 12:00:59 and another 10 requests at 12:01:01. Both batches are accepted because they belong to separate windows, but the backend is hit with a burst of 20 requests in 2 seconds—double the intended limit.
Sliding Window Log Memory Overhead
The Sliding Window Log algorithm resolves the boundary burst problem by saving a timestamp for every request a client makes. When a new request arrives, it deletes timestamps older than the window (e.g., 1 minute) and counts the remaining logs. While highly accurate, storing every timestamp in memory (usually in a Redis sorted set) consumes massive RAM when scaling to millions of active users.
Distributed Synchronization Race Conditions
In distributed rate limiting, checking a counter value and then incrementing it (GET followed by INCR) is not atomic. If two concurrent requests hit two separate gateway nodes at the same time, both might read the counter under the limit and accept the request, causing the client to bypass the limit. To solve this, systems must use atomic Redis Lua scripts to evaluate and increment the counter in a single, blocking Redis thread.
Common Questions
How does the Fixed Window boundary burst occur?
Fixed Window algorithms divide time into static blocks (e.g., 1-minute windows). Counters are reset at the beginning of each block. If a client concentrates their requests at the end of one window and the beginning of the next, they can double their allowed limit in a short time frame, as the limiter only checks the current window's count.
Why use Redis Lua scripting for distributed rate limiting?
Redis Lua scripts are executed atomically on the Redis server. Instead of making multiple network roundtrips to fetch, increment, and set expirations on keys—which introduces race conditions under high concurrency—a Lua script runs the entire logic locally on Redis. No other command can run until the script finishes, ensuring absolute correctness.
What is the difference between Sliding Window Log and Sliding Window Counter?
Sliding Window Log stores exact timestamps of every request, which is highly accurate but memory-intensive. Sliding Window Counter optimizes this by storing only the request count of the current window and the previous window, then calculating a weighted average based on the current timestamp (e.g., if we are 30% into the current window, the request count = 70% of last window + 100% of current window). This provides a close approximation with minimal memory overhead.
What are the typical headers returned during a rate limit block?
When a client is throttled, well-designed APIs return an HTTP 429 Too Many Requests status code and include specific headers: - `X-RateLimit-Limit`: The maximum number of allowed requests in the window. - `X-RateLimit-Remaining`: The number of requests left before being blocked. - `Retry-After`: The number of seconds the client must wait before making another request.