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.

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:

-- 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:

-- 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

-- 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:

-- 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:

# 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:

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.