API Rate Limiting Algorithms and Distributed Throttling

Rate Limiting Algorithms

1. Fixed Window

Reset counter every minute (e.g., 100 req/min) ❌ Boundary spike: up to 2x traffic at window edges

2. Sliding Window Log

Record timestamp of each request; count within last N seconds ✅ Accurate, no boundary spikes ❌ High memory usage

3. Sliding Window Counter

Weighted approximation across two fixed windows ✅ Memory-efficient with acceptable accuracy

4. Token Bucket

Tokens replenish at fixed rate; requests consume tokens ✅ Allows short traffic bursts

5. Leaky Bucket

Requests queue up and drain at fixed rate ✅ Perfectly smooth output; ideal for streaming

Distributed Implementation (Redis)

• INCR + EXPIRE: simple counter
• Lua Script: atomic operations
• Sorted Set: Sliding Window Log

Response Headers

X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, Retry-After (on 429)