Backend # Algoritmos de Rate Limiting: De Token Buckets a Scripts Lua Distribuidos 2025-10-215 min lectura Lucio Durán Engineering Manager & AI Solutions Architect También disponible en: [English]() ## Fixed window counter: el approach naive El rate limiter más simple. Dividí el tiempo en ventanas fijas (ej: intervalos de 1 minuto), contá requests por ventana, rechazá cuando el conteo excede el límite. ```python import time, redis r = redis.Redis() def fixed_window(key: str, limit: int, window_seconds: int) -> bool: window = int(time.time() / window_seconds) redis_key = f"ratelimit:{key}:{window}" current = r.incr(redis_key) if current == 1: r.expire(redis_key, window_seconds + 1) return current <= limit ``` El problema: ráfaga en el borde. En el límite de dos ventanas, un cliente puede hacer ` 2 * limit ` requests en un lapso de ` window_seconds `. ## Sliding window log: exacto pero caro Manteners un sorted set de cada timestamp de request: ```lua -- sliding_window_log.lua local key = KEYS[1] local now = tonumber(ARGV[1]) local window = tonumber(ARGV[2]) local limit = tonumber(ARGV[3]) redis.call('ZREMRANGEBYSCORE', key, 0, now - window) local count = redis.call('ZCARD', key) if count < limit then redis.call('ZADD', key, now, now .. ':' .. math.random(1000000)) redis.call('PEXPIRE', key, window) return {1, limit - count - 1} else return {0, 0} end ``` Conteo exacto, sin problema de ráfaga en el borde. Pero guarda cada timestamp de request. A 1.000 req/s con una ventana de 60 segundos, son 60.000 entradas por key. ## Sliding window counter: el medio práctico Combiná dos ventanas fijas con conteo pesado: ```lua -- sliding_window_counter.lua local key = KEYS[1] local limit = tonumber(ARGV[1]) local window = tonumber(ARGV[2]) local now = tonumber(ARGV[3]) local current_window = math.floor(now / window) local previous_window = current_window - 1 local elapsed = (now % window) / window local current_count = tonumber(redis.call('GET', key .. ':' .. current_window) or '0') local previous_count = tonumber(redis.call('GET', key .. ':' .. previous_window) or '0') local estimated = previous_count * (1 - elapsed) + current_count if estimated < limit then redis.call('INCR', key .. ':' .. current_window) redis.call('PEXPIRE', key .. ':' .. current_window, window * 2) return {1, math.floor(limit - estimated - 1)} else return {0, 0} end ``` ## Token bucket: permitiendo ráfagas controladas ```lua -- token_bucket.lua local key = KEYS[1] local capacity = tonumber(ARGV[1]) local rate = tonumber(ARGV[2]) local now = tonumber(ARGV[3]) local requested = tonumber(ARGV[4]) local data = redis.call('HMGET', key, 'tokens', 'last_refill') local tokens = tonumber(data[1]) local last_refill = tonumber(data[2]) if tokens == nil then tokens = capacity last_refill = now end local elapsed = (now - last_refill) / 1000.0 tokens = math.min(capacity, tokens + elapsed * rate) local allowed = 0 if tokens >= requested then tokens = tokens - requested allowed = 1 end redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now) redis.call('PEXPIRE', key, math.ceil(capacity / rate * 1000) + 1000) return {allowed, math.floor(tokens)} ``` ## GCRA: el algoritmo de tasa de celdas GCRA viene del traffic shaping de redes ATM. En vez de trackear tokens, trackea cuándo debería permitirse el próximo request: ```lua -- gcra.lua local key = KEYS[1] local emission_interval = tonumber(ARGV[1]) local burst_offset = tonumber(ARGV[2]) local now = tonumber(ARGV[3]) local tat = tonumber(redis.call('GET', key)) if tat == nil then tat = now + emission_interval redis.call('SET', key, tat) redis.call('PEXPIRE', key, burst_offset + emission_interval) return {1, 0} end local allow_at = tat - burst_offset if now < allow_at then return {0, allow_at - now} else local new_tat = math.max(now, tat) + emission_interval redis.call('SET', key, new_tat) redis.call('PEXPIRE', key, burst_offset + emission_interval) return {1, 0} end ``` GCRA tiene propiedades hermosas: una sola key por cliente, operaciones O(1), sin ráfagas en los bordes, enforcement de tasa suave. Es lo que usa [Cloudflare]() internamente. ## El race condition distribuido Un bug común y peligroso en rate limiting distribuido involucra un race condition: ```python # ROTO: race condition entre check y decrement def check_rate_limit(key, limit, window): count = redis.get(key) or 0 if int(count) >= limit: return False # Entre este GET y el INCR, otros requests pueden pasar! redis.incr(key) return True ``` Con 100 requests concurrentes, todos leen count=0, todos pasan el check, todos incrementan. El límite no sirve para nada. La solución: operaciones atómicas via scripts Lua. Cada script Lua en Redis se ejecuta atómicamente. Todas las implementaciones Lua de arriba son atómicas por diseño. Cargalas una vez con ` SCRIPT LOAD `, después llamá con ` EVALSHA `: ```python class DistributedRateLimiter: def __init__(self, redis_client): self.r = redis_client self._script_sha = None def _load_script(self): self._script_sha = self.r.script_load(GCRA_SCRIPT) def allow(self, key: str, rate: float = 100.0, burst: int = 10) -> tuple[bool, int]: if self._script_sha is None: self._load_script() emission_interval = int(1000 / rate) burst_offset = emission_interval * burst now_ms = int(time.time() * 1000) try: result = self.r.evalsha(self._script_sha, 1, key, emission_interval, burst_offset, now_ms) except redis.exceptions.NoScriptError: self._load_script() result = self.r.evalsha(self._script_sha, 1, key, emission_interval, burst_offset, now_ms) return bool(result[0]), int(result[1]) ``` ## Rate limiting multi-capa En producción, un enfoque de tres capas funciona bien: 1. **Edge (Cloudflare/nginx)**: Basado en IP, límites altos (1.000/min), atrapa DDoS y scrapers 2. **API Gateway**: Basado en API key, límites por plan (free: 60/min, pro: 600/min) 3. **Por endpoint**: Límites específicos para operaciones caras (search: 10/min, export: 5/min) Cada capa corre independientemente con su propio namespace de keys de Redis. Un request tiene que pasar las tres para proceder. Después de cambiar a scripts Lua atómicos, el rate limiter se vuelve a prueba de balas. Doce meses de uso en producción, cero incidentes, cero race conditions. La implementación son menos de 50 líneas de Lua. A veces el fix más simple es el mejor. ## Preguntas frecuentes ### ¿Qué algoritmo de rate limiting debería usar? Para la mayoría del rate limiting de APIs, GCRA o sliding window counter. Token bucket si se desea permitir ráfagas controladas. Fixed window solo para límites simples y no críticos. ### ¿Cómo hago rate limiting en un sistema distribuido? Utilizar Redis con scripts Lua atómicos. Cada chequeo de rate limit debería ser una sola llamada EVALSHA que lea el estado actual, decida allow/deny, y actualice estado atómicamente. ### ¿Debería limitar por IP o por API key? Ambos, en diferentes capas. Limitación por IP en el edge para DDoS y abuso no autenticado. Limitación por API key en la capa de aplicación para cuotas por cliente. Son complementarios. ## Tips 1. **Tip:** Utilizar GCRA sobre token bucket cuando necesités rate limiting suave. Token bucket permite ráfagas hasta el tamaño del bucket; GCRA espacia requests uniformemente, que es lo que realmente se desea para protección de APIs. 2. **Tip:** Siempre incluir headers ` X-RateLimit-Limit `, ` X-RateLimit-Remaining `, y ` X-RateLimit-Reset ` en tus respuestas. Los clientes que los respetan reducen tu carga voluntariamente. 3. **Tip:** En setups distribuidos, utilizar un solo ` EVALSHA ` de Redis para check-and-decrement. Dos comandos separados (GET y después SET) crean un race condition donde requests concurrentes pasan el check antes de que alguno decremente. 4. **Tip:** Configurar el TTL de tu key de Redis a ` window_size + 1 segundo `, no exactamente ` window_size `. El clock skew entre servidores de aplicación y Redis puede causar que las keys expiren un request antes de tiempo. - rate-limiting - token-bucket - sliding-window - gcra - redis - lua - api-gateway - distributed-systems [Volver al Blog]()