Why Rate Limiting?
Rate limiting prevents abuse, ensures fair API usage, and protects backend services from being overwhelmed. Use cases: (1) Prevent brute-force auth attacks. (2) Enforce API tier quotas (free vs paid). (3) Protect against DDoS. (4) Limit expensive operations (ML inference, payment processing). Requirements: low latency (must not add > 1ms to request path), accurate, distributed (works across multiple servers), flexible rules (per-user, per-IP, per-endpoint).
Algorithm 1 — Fixed Window Counter
Divide time into fixed windows (e.g., 1-minute buckets). Each user has a counter per window. Allow up to N requests in a window. Problem: boundary spikes — a user can fire N requests at 11:59:59 and another N at 12:00:00, effectively sending 2N requests in 2 seconds while technically complying. Simple to implement but inaccurate at window edges.
Algorithm 2 — Sliding Window Log
Keep a sorted set (log) of timestamps of each request per user. On each request: (1) Remove all timestamps older than now - window_size. (2) If log size >= limit, reject. (3) Else add timestamp, allow. Perfectly accurate — no boundary spike problem. Memory cost: O(N × limit) per user since we store one timestamp per allowed request. At 1M users × 100 req/min = 100M entries ≈ 12 GB. Too expensive at scale.
Algorithm 3 — Sliding Window Counter (Optimal)
Hybrid approach. Maintain a counter for the current fixed window and the previous window. Estimate the rolling count as: count = prev_window_count × (time_remaining_in_prev / window_size) + current_window_count. This approximates the true sliding window. Very accurate in practice (error < 1%), and uses only 2 integers per user per window — roughly 1.6 GB for 1M users with 2 windows vs 12 GB for the log approach.
Implementation in Redis: INCR with EXPIRE. Two keys per user: rate:{user_id}:{current_window} and rate:{user_id}:{prev_window}.
graph LR
Request --> RateLimiter["Rate Limiter Middleware"]
RateLimiter --> Redis["Redis Cluster
(sliding window counters)"]
Redis --> Decision{Allow?}
Decision -->|Yes| Backend["Backend Service"]
Decision -->|No| HTTP429["HTTP 429
Too Many Requests"] Distributed Rate Limiting
When there are multiple app servers, each server cannot maintain its own counters — user A might hit server 1 five times and server 2 five times, bypassing a 5-request limit. Solution: use a centralized Redis cluster for all rate limit state. All servers read/write to the same Redis. Redis atomic operations (INCR, EXPIRE) ensure correctness without race conditions.
For very high throughput, use Redis Cluster with consistent hashing: user A's counter lives on a specific shard. Replica per shard for fault tolerance. If the Redis shard is down, fall back to allowing requests (fail open) rather than blocking all traffic.
Token Bucket and Leaky Bucket
Token Bucket: each user has a bucket that fills at a steady rate (1 token/sec, max 10 tokens). Each request costs 1 token. If the bucket is empty, reject. Allows short bursts up to bucket capacity. Simple and widely used (AWS and Stripe use this). Leaky Bucket: requests enter a FIFO queue (the "bucket"). Worker processes requests at a fixed rate. If the queue is full, new requests are dropped. Ensures a perfectly smooth outgoing rate. Good for payment systems where a steady rate is critical.
Sliding window counter is generally preferred for API gateways because it is accurate, memory-efficient, and easy to implement in Redis.