API Rate Limiting Algorithms

The Sliding Window Algorithm

Fixed Window rate limiting (e.g., "100 requests per minute") allows an attacker to send 200 requests in a 1-second burst at the boundary of the minute window (100 at 0:59, 100 at 1:00). To prevent this burst traffic, we must use a Sliding Window.

Implementation in Redis via Sorted Sets

A highly accurate sliding window can be built using Redis Sorted Sets (ZSET). The key is the user's IP or API Key, the score is the current timestamp, and the value is a unique request ID (or the timestamp itself).

1. Remove all elements with a score older than current_time - window_size using ZREMRANGEBYSCORE.
2. Count the remaining elements in the set using ZCARD.
3. If the count is less than the limit, add the new request using ZADD and return HTTP 200.
4. If the count exceeds the limit, return HTTP 429 Too Many Requests.
5. Set an expiry (TTL) on the sorted set equal to the window size so inactive keys clean themselves up.

Note: To avoid race conditions, these steps must be executed atomically using a Redis Lua script or a MULTI/EXEC pipeline.