Implementing Rate Limiting
1. Implementing Fixed Window Counter
Example: 100 req/min per user
local key = "rate:" .. user .. ":" .. minute
local c = redis.call('INCR', key)
if c == 1 then redis.call('EXPIRE', key, 60) end
return c <= 100| Property | Detail |
|---|---|
| Memory | O(users × windows) |
| Issue | Burst at window boundary |
2. Implementing Sliding Window Counter
| Approach | Detail |
|---|---|
| Hybrid | Current + previous window weighted |
| Memory | 2 counters per user |
| Accuracy | Good approximation |
3. Using Token Bucket Algorithm
Example: Token bucket via Lua
-- Refill tokens based on elapsed, deduct one
local h = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens, ts = tonumber(h[1]) or capacity, tonumber(h[2]) or now
tokens = math.min(capacity, tokens + (now - ts) * rate)
if tokens < 1 then return 0 end
redis.call('HMSET', KEYS[1], 'tokens', tokens - 1, 'ts', now)
redis.call('EXPIRE', KEYS[1], 3600)
return 14. Using Sorted Sets for Sliding Windows
| Step | Command |
|---|---|
| Add request | ZADD key now now |
| Drop expired | ZREMRANGEBYSCORE key -inf (now-window) |
| Count | ZCARD key |
| Expire key | EXPIRE key window |
5. Using Sliding Window Log Algorithm
| Property | Tradeoff |
|---|---|
| Precision | Exact |
| Memory | O(allowed_requests) per user |
6. Implementing Leaky Bucket Pattern
| Aspect | Detail |
|---|---|
| Behavior | Queue drains at constant rate |
| Storage | Hash with depth + last leak time |
7. Setting Rate Limit Expiration
| Strategy | Detail |
|---|---|
| TTL = window | Auto-cleanup; use EXPIRE on key creation |
8. Implementing Distributed Rate Limiting
| Approach | Notes |
|---|---|
| Central Redis | All app nodes share counter — strongest consistency |
| Cluster + hashtag | {rate}:user:42 pins all keys to one slot |
9. Handling Race Conditions
| Risk | Mitigation |
|---|---|
| Increment + check race | Wrap in Lua for atomicity |
| TTL set race | Conditional EXPIRE only when counter=1 |
10. Optimizing with Lua Scripts
| Benefit | Detail |
|---|---|
| One RTT | Single EVALSHA replaces multiple commands |
| Atomic | No interleaving from other clients |