Rate Limiting Algorithms

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| Client

---

Components and Why They Exist

Clients

Represents the users or external systems making requests to the API. Dispatches API requests. Well-behaved clients should dynamically back off and wait when receiving a rate-limit error. In the demo, observe blue request particles leaving the client node and flowing into the Gateway.

Rate Limiter (API Gateway)

Serves as the first line of defense protecting internal network resources. Tracks request counts per client IP or token, executes rate-limiting algorithms, and returns HTTP 429 errors when thresholds are crossed. In the demo, notice how the limiter allows green particles to pass to the backend, but redirects red overflow particles back to the client.

Backend Servers

Processes the business logic and returns API responses. Handles the actual requests. Because the rate limiter blocks excess traffic, the backend remains protected from sudden traffic spikes or denial-of-service attempts. In the demo, you can see how the backend server remains steady and receives only clean, authorized traffic.

Redis Cache (Distributed Counter)

Provides a fast, centralized store to share rate limiting state across multiple gateway nodes. Stores atomic request counters and expirations. This prevents clients from bypassing local rate limiters by routing requests through different load balancers. In the demo, observe the lookup messages passing between the Gateway and Redis in Step 12 and Step 13.

---

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.