Algoritmos de limitación de tasa: token bucket y más

Análisis a fondo de los algoritmos de limitación de tasa, con implementaciones, compromisos y cómo elegir el enfoque adecuado para tu API.

Publicado el 19 de enero de 2021Actualizado el 9 de septiembre de 20265 min de lectura

rate-limiting algorithms api-design backend distributed-systems

La limitación de tasa protege tu sistema de abusos y sobrecargas, pero el algoritmo que elijas determina cómo la perciben los usuarios legítimos. Un limitador mal elegido deja pasar ráfagas de tráfico cuando no debería, o bien restringe patrones de uso normales de forma innecesaria.

La mayoría de los desarrolladores recurre a un contador simple — "100 solicitudes por minuto" — sin considerar cómo se reinicia ese contador, si las ráfagas son aceptables o cómo se comporta en servidores distribuidos. La elección del algoritmo influye directamente en la experiencia del usuario.

Contador de Fixed Window

El enfoque más simple: dividir el tiempo en ventanas fijas y contar las solicitudes de cada ventana.

tstypescript

class FixedWindowLimiter {
  private windows = new Map<string, { count: number; expiry: number }>();
 
  constructor(
    private maxRequests: number,
    private windowMs: number
  ) {}
 
  isAllowed(key: string): boolean {
    const now = Date.now();
    const windowStart = Math.floor(now / this.windowMs) * this.windowMs;
    const windowKey = `${key}:${windowStart}`;
 
    const window = this.windows.get(windowKey);
    if (!window || now > window.expiry) {
      this.windows.set(windowKey, {
        count: 1,
        expiry: windowStart + this.windowMs,
      });
      return true;
    }
 
    if (window.count >= this.maxRequests) return false;
    window.count++;
    return true;
  }
}

El problema: las ráfagas en el límite de la ventana. Un cliente puede enviar 100 solicitudes a las 11:59:59 y 100 más a las 12:00:00 — 200 solicitudes en 2 segundos, manteniéndose técnicamente por debajo del límite de "100 por minuto".

tstypescript

// ❌ Fixed window boundary problem
// Window 1 (11:59:00-11:59:59): 100 requests at 11:59:58 ✅
// Window 2 (12:00:00-12:00:59): 100 requests at 12:00:01 ✅
// Result: 200 requests in 3 seconds — limit is effectively doubled

Fixed window funciona bien en casos simples donde las ráfagas ocasionales son aceptables. Para una aplicación más estricta del límite, usa sliding window.

Registro de Sliding Window

Registra la marca de tiempo de cada solicitud y cuenta cuántas caen dentro de la ventana. Preciso, pero con un alto consumo de memoria.

tstypescript

class SlidingWindowLog {
  private logs = new Map<string, number[]>();
 
  constructor(
    private maxRequests: number,
    private windowMs: number
  ) {}
 
  isAllowed(key: string): boolean {
    const now = Date.now();
    const windowStart = now - this.windowMs;
 
    let timestamps = this.logs.get(key) ?? [];
    // Remove expired entries
    timestamps = timestamps.filter((t) => t > windowStart);
 
    if (timestamps.length >= this.maxRequests) {
      this.logs.set(key, timestamps);
      return false;
    }
 
    timestamps.push(now);
    this.logs.set(key, timestamps);
    return true;
  }
}

Este enfoque es perfectamente preciso: no hay ráfagas en el límite. Pero almacenar cada marca de tiempo es costoso. Con 1000 solicitudes por minuto por usuario, estás almacenando 1000 marcas de tiempo por usuario en memoria.

Contador de Sliding Window

Un híbrido que combina la eficiencia de fixed window con la precisión de sliding window. Interpola entre dos ventanas fijas adyacentes según cuánto haya avanzado la ventana actual.

tstypescript

class SlidingWindowCounter {
  private windows = new Map<string, number>();
 
  constructor(
    private maxRequests: number,
    private windowMs: number
  ) {}
 
  isAllowed(key: string): boolean {
    const now = Date.now();
    const currentWindow = Math.floor(now / this.windowMs);
    const previousWindow = currentWindow - 1;
    const elapsed = (now % this.windowMs) / this.windowMs;
 
    const currentKey = `${key}:${currentWindow}`;
    const previousKey = `${key}:${previousWindow}`;
 
    const currentCount = this.windows.get(currentKey) ?? 0;
    const previousCount = this.windows.get(previousKey) ?? 0;
 
    // Weighted sum: full current + proportional previous
    const estimatedCount = currentCount + previousCount * (1 - elapsed);
 
    if (estimatedCount >= this.maxRequests) return false;
 
    this.windows.set(currentKey, currentCount + 1);
    return true;
  }
}

Este es el punto óptimo para la mayoría de las API. O(1) de memoria por usuario (dos contadores), sin el problema de ráfagas en el límite, y con un conteo casi exacto.

Token Bucket

Token bucket permite ráfagas controladas mientras mantiene una tasa promedio. Los tokens se añaden a un ritmo constante. Cada solicitud consume un token. Sin tokens, no hay solicitud. El bucket puede acumular tokens hasta un máximo, lo que permite ráfagas cortas.

tstypescript

class TokenBucket {
  private tokens: number;
  private lastRefill: number;
 
  constructor(
    private capacity: number,
    private refillRate: number, // tokens per second
  ) {
    this.tokens = capacity;
    this.lastRefill = Date.now();
  }
 
  isAllowed(cost: number = 1): boolean {
    this.refill();
 
    if (this.tokens >= cost) {
      this.tokens -= cost;
      return true;
    }
    return false;
  }
 
  private refill(): void {
    const now = Date.now();
    const elapsed = (now - this.lastRefill) / 1000;
    this.tokens = Math.min(
      this.capacity,
      this.tokens + elapsed * this.refillRate
    );
    this.lastRefill = now;
  }
}
 
// Example: 10 tokens max, refills at 2/sec
// Burst of 10 requests: allowed immediately
// Then: 2 requests per second sustained
const limiter = new TokenBucket(10, 2);

Token bucket es ideal cuando quieres permitir ráfagas (por ejemplo, cargas de página que disparan múltiples llamadas a la API) mientras limitas el rendimiento sostenido. AWS y la mayoría de los proveedores de nube usan este enfoque.

Limitación de Tasa Distribuida con Redis

Los limitadores en memoria fallan cuando tu aplicación se ejecuta en varios servidores. Redis ofrece operaciones atómicas para el estado compartido.

tstypescript

import { Redis } from 'ioredis';
 
class RedisRateLimiter {
  constructor(
    private redis: Redis,
    private maxRequests: number,
    private windowSec: number
  ) {}
 
  async isAllowed(key: string): Promise<{ allowed: boolean; remaining: number }> {
    const redisKey = `ratelimit:${key}`;
 
    // Atomic increment + expire using a Lua script
    const result = await this.redis.eval(
      `
      local current = redis.call('INCR', KEYS[1])
      if current == 1 then
        redis.call('EXPIRE', KEYS[1], ARGV[1])
      end
      return current
      `,
      1,
      redisKey,
      this.windowSec
    ) as number;
 
    return {
      allowed: result <= this.maxRequests,
      remaining: Math.max(0, this.maxRequests - result),
    };
  }
}

El script de Lua se ejecuta de forma atómica en Redis, sin condiciones de carrera entre las llamadas a INCR y EXPIRE. Esto es fundamental cuando varios servidores de la aplicación comparten el mismo limitador.

Encabezados de Respuesta

Los clientes necesitan conocer el estado de su límite de tasa. Devuelve encabezados estándar en cada respuesta.

tstypescript

// ❌ No rate limit headers — client has no idea why requests fail
app.use((req, res, next) => {
  if (!limiter.isAllowed(req.ip)) {
    return res.status(429).json({ error: 'Too many requests' });
  }
  next();
});
 
// ✅ Informative headers — client can adapt behavior
app.use(async (req, res, next) => {
  const result = await limiter.isAllowed(req.ip);
 
  res.set({
    'X-RateLimit-Limit': String(limiter.maxRequests),
    'X-RateLimit-Remaining': String(result.remaining),
    'X-RateLimit-Reset': String(result.resetAt),
    'Retry-After': result.allowed ? undefined : String(result.retryAfter),
  });
 
  if (!result.allowed) {
    return res.status(429).json({
      error: 'Rate limit exceeded',
      retryAfter: result.retryAfter,
    });
  }
  next();
});

El encabezado Retry-After indica a los clientes bien diseñados exactamente cuándo reintentar. Sin él, los clientes o bien saturan el servidor con reintentos, o bien esperan más de lo necesario.

Cómo Elegir el Algoritmo Adecuado

Algoritmo	Manejo de Ráfagas	Memoria	Precisión	Ideal para
Fixed Window	Permite el doble	O(1)	Baja	Casos simples, API internas
Sliding Window Log	Exacto	O(n)	Perfecta	Volúmenes de solicitudes pequeños
Sliding Window Counter	Bueno	O(1)	Muy buena	La mayoría de la limitación de tasa en API
Token Bucket	Explícito	O(1)	Buena	API públicas tolerantes a ráfagas

Para la mayoría de las API web, el contador de sliding window ofrece el mejor equilibrio. Para API donde la tolerancia a ráfagas es una característica deseada (subida de archivos, operaciones por lotes), usa token buckets.

Puntos Clave

Fixed window tiene un problema de ráfagas en el límite — el tráfico puede duplicarse en los límites de la ventana
El contador de sliding window es la mejor opción por defecto — memoria O(1) con una precisión casi perfecta
Token bucket es ideal para API tolerantes a ráfagas — controla explícitamente el tamaño de la ráfaga y la tasa sostenida
Usa Redis para la limitación distribuida — los scripts de Lua garantizan atomicidad entre servidores
Devuelve siempre encabezados de límite de tasa — X-RateLimit-Remaining y Retry-After permiten clientes bien diseñados

Algoritmos de limitación de tasa: token bucket y más

Contador de Fixed Window

Registro de Sliding Window

Contador de Sliding Window

Token Bucket

Limitación de Tasa Distribuida con Redis

Encabezados de Respuesta

Cómo Elegir el Algoritmo Adecuado

Puntos Clave

Publicaciones relacionadas

Limitación de tasa en APIs: algoritmos e implementación

APIs idempotentes: reintentar solicitudes de forma segura

Idempotencia en el diseño de APIs: reintentos seguros