Rate Limiter
Chaar algorithms jaanne chahiye: FIXED WINDOW (simple, par boundary par 2x burst), SLIDING WINDOW LOG (accurate, par memory zyada), SLIDING WINDOW COUNTER (dono ka balance), aur TOKEN BUCKET (burst allow karta hai, sabse popular). Har ek ka trade-off batana hi is problem ka core hai.
Token bucket sabse zyada poocha jaata hai: bucket mein tokens fixed rate se bharte hain, har request ek token uthaati hai, token khatam to request reject. Distributed setup mein counter Redis mein rakhna padta hai aur check-and-decrement ATOMIC hona chahiye — Lua script ya INCR with EXPIRE.
interface RateLimiter { boolean allowRequest(String clientId); }
class TokenBucketLimiter implements RateLimiter {
private final long capacity, refillPerSecond;
public synchronized boolean allowRequest(String clientId) {
Bucket b = buckets.get(clientId);
long now = System.nanoTime();
// Beeta hua time -> utne tokens wapas bhar do (capacity tak)
long refill = (now - b.lastRefill) * refillPerSecond / 1_000_000_000L;
b.tokens = Math.min(capacity, b.tokens + refill);
b.lastRefill = now;
if (b.tokens < 1) return false;
b.tokens--;
return true;
}
}- Chaar algorithms aur unke trade-offs — yahi is problem ka core hai
- Token bucket burst allow karta hai, isliye sabse popular
- Distributed mein Redis + atomic Lua script, warna race condition
FIXED WINDOW: counter per window, reset on boundary. Memory O(1), par boundary par 2x burst possible.
SLIDING WINDOW LOG: har request ka timestamp store. Bilkul accurate, par memory O(requests) — heavy traffic par mehnga.
SLIDING WINDOW COUNTER: current aur previous window ka weighted average. Accuracy aur memory ka best balance — production mein sabse common.
TOKEN BUCKET: tokens fixed rate se refill, burst allowed. API gateways ka default choice.
Single server par in-memory counter kaafi hai. 10 servers par har server ka apna counter matlab actual limit 10x ho jaayegi. Isliye counter SHARED hona chahiye — Redis.
Redis mein check-and-increment ATOMIC hona chahiye. INCR + EXPIRE do alag commands hain aur beech mein race ho sakti hai — isliye Lua script use karo jo dono ek saath atomically chalaye.
-- Lua: atomic increment + expire
local current = redis.call('INCR', KEYS[1])
if current == 1 then
redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return current