Algoritmos de rate limiting para produção: Token Bucket, Leaky Bucket e Sliding Window

A necessidade fundamental de rate limiting

APIs em produção sem rate limiting estão vulneráveis a múltiplas ameaças: DDoS attacks, abuso por bots, esgotamento de recursos, e custos de infraestrutura inesperados. O objetivo não é apenas limitar acesso, mas proteger o sistema enquanto fornece experiência consistente para usuários legítimos.

Rate limiting eficaz equilibra três objetivos concorrentes:

1. Proteção: Prevenir esgotamento de recursos e abuso
2. Experiência: Permitir usuários legítimos dentro de limites razoáveis
3. Eficiência: Implementar com baixo overhead computacional

Para engenheiros de software, a escolha do algoritmo correto depende das características do workload, requisitos de latência e infraestrutura disponível.

Token Bucket: flexibilidade com burst tolerance

O algoritmo Token Bucket é amplamente utilizado por sua simplicidade e capacidade de permitir bursts temporários. Funciona como um bucket que se enche com tokens a uma taxa constante. Cada requisição consome um token do bucket.

Como funciona

Bucket com capacidade C
Taxa de refill R tokens por segundo

Requisição:
  Se bucket >= tokens_requeridos:
    Consumir tokens
    Permitir requisição
  Senão:
    Rejeitar requisição (rate limited)

Implementação em Redis

typescript// Token Bucket em Redis usando sorted set
class TokenBucketRateLimiter {
  constructor(
    private redis: Redis,
    private capacity: number,
    private refillRate: number // tokens por segundo
  ) {}

  async allowRequest(identifier: string, tokens: number = 1): Promise<boolean> {
    const now = Date.now();
    const bucketKey = `token_bucket:${identifier}`;

    const results = await this.redis
      .multi()
      // Limpar tokens expirados (mais antigos que capacity/refillRate segundos)
      .zremrangebyscore(
        bucketKey,
        '-inf',
        now - (this.capacity / this.refillRate) * 1000
      )
      // Contar tokens disponíveis
      .zcard(bucketKey)
      // Adicionar novo token (timestamp atual)
      .zadd(bucketKey, now, `${now}-${Math.random()}`)
      // Definir TTL para evitar key rotativo infinito
      .expire(bucketKey, Math.ceil(this.capacity / this.refillRate) + 1)
      .exec();

    const currentTokens = results[1];
    const newTokens = currentTokens + 1;

    if (newTokens <= this.capacity) {
      return true; // Request permitido
    }

    // Se excedeu capacidade, remover token adicionado
    await this.redis.zrem(bucketKey, `${now}-${Math.random()}`);
    return false; // Request rejeitado
  }

  async getTokensAvailable(identifier: string): Promise<number> {
    const now = Date.now();
    const bucketKey = `token_bucket:${identifier}`;

    // Limpar tokens expirados
    await this.redis.zremrangebyscore(
      bucketKey,
      '-inf',
      now - (this.capacity / this.refillRate) * 1000
    );

    return await this.redis.zcard(bucketKey);
  }
}

Quando usar Token Bucket

Trade-offs de configuração

typescript// Configurações típicas por tipo de API
const rateLimitConfigs = {
  // APIs públicas: permissivo, mas limitado
  publicApi: {
    capacity: 100, // 100 tokens no bucket
    refillRate: 10, // 10 tokens por segundo
    description: 'Permite burst de até 100 requisições, depois 10 req/s'
  },

  // APIs autenticadas: mais generosas
  authenticatedApi: {
    capacity: 500,
    refillRate: 50,
    description: 'Permite burst de 500 requisições, depois 50 req/s'
  },

  // Write operations: mais restritivas
  writeOperations: {
    capacity: 20,
    refillRate: 2,
    description: 'Permite burst de 20 escritas, depois 2 req/s'
  },

  // Recursos intensivos: altamente restritivos
  expensiveOperations: {
    capacity: 5,
    refillRate: 0.5, // 1 token a cada 2 segundos
    description: 'Permite burst de 5 operações, depois 1 a cada 2 segundos'
  }
};

Leaky Bucket: consistência sem bursts

O algoritmo Leaky Bucket processa requisições a uma taxa constante, enfileirando excessos e rejeitando quando a fila está cheia. Ao contrário do Token Bucket, Leaky Bucket não permite bursts—requisições acima da taxa são enfileiradas até a capacidade máxima da fila.

Como funciona

Fila com capacidade F
Taxa de processamento R requisições por segundo

Requisição:
  Se fila < capacidade F:
    Adicionar à fila
  Senão:
    Rejeitar requisição

Processamento (R requisições/seg):
  Remover da fila e processar

Implementação em Redis

typescript// Leaky Bucket em Redis usando list
class LeakyBucketRateLimiter {
  constructor(
    private redis: Redis,
    private queueCapacity: number,
    private processRate: number // requisições por segundo
  ) {}

  async allowRequest(identifier: string): Promise<boolean> {
    const now = Date.now();
    const queueKey = `leaky_bucket:${identifier}`;
    const lastProcessKey = `leaky_bucket:${identifier}:last`;

    const pipeline = this.redis.multi();

    // Processar itens da fila (leaky)
    const lastProcess = await this.redis.get(lastProcessKey);
    const lastProcessTime = lastProcess ? parseInt(lastProcess) : now;

    const timePassed = (now - lastProcessTime) / 1000; // em segundos
    const itemsToProcess = Math.floor(timePassed * this.processRate);

    if (itemsToProcess > 0) {
      // Remover itemsToProcess da fila
      for (let i = 0; i < itemsToProcess; i++) {
        pipeline.lpop(queueKey);
      }
      // Atualizar timestamp de último processamento
      pipeline.set(lastProcessKey, now);
    }

    // Verificar capacidade da fila
    pipeline.llen(queueKey);

    const results = await pipeline.exec();
    const queueLength = results[results.length - 1];

    if (queueLength < this.queueCapacity) {
      // Adicionar à fila
      await this.redis.rpush(queueKey, now);
      await this.redis.expire(queueKey, Math.ceil(this.queueCapacity / this.processRate) + 1);
      return true;
    }

    return false; // Fila cheia, rejeitar
  }

  async getQueueLength(identifier: string): Promise<number> {
    return await this.redis.llen(`leaky_bucket:${identifier}`);
  }
}

Quando usar Leaky Bucket

Token Bucket vs Leaky Bucket

typescript// Comparação prática
const scenarios = {
  // Cenário 1: Bursts permitidos
  burstScenario: {
    algorithm: 'Token Bucket',
    behavior: 'Burst de 100 req, depois 10 req/s',
    implementation: 'Permite picos temporários dentro da capacidade'
  },

  // Cenário 2: Taxa constante
  constantScenario: {
    algorithm: 'Leaky Bucket',
    behavior: 'Fila com processamento a 10 req/s',
    implementation: 'Taxa de saída constante, enfileira excessos'
  }
};

// Decisão: escolha baseada em se bursts são desejados

Sliding Window: precisão temporal

O algoritmo Sliding Window rastreia requisições em uma janela de tempo deslizante, oferecendo precisão superior a Fixed Window que sofre de edge effects (bursts nos limites da janela).

Como funciona

Janela de tempo W segundos
Limite L requisições por janela

Requisição:
  Contar requisições no intervalo [now - W, now]
  Se contagem < L:
    Permitir requisição
  Senão:
    Rejeitar requisição

Implementação em Redis (Sliding Window Log)

typescript// Sliding Window Log em Redis usando sorted set
class SlidingWindowRateLimiter {
  constructor(
    private redis: Redis,
    private windowSize: number, // em segundos
    private maxRequests: number
  ) {}

  async allowRequest(identifier: string): Promise<boolean> {
    const now = Date.now();
    const windowStart = now - (this.windowSize * 1000);
    const windowKey = `sliding_window:${identifier}`;

    const results = await this.redis
      .multi()
      // Remover requisições fora da janela
      .zremrangebyscore(windowKey, '-inf', windowStart)
      // Contar requisições na janela atual
      .zcard(windowKey)
      // Adicionar nova requisição
      .zadd(windowKey, now, `${now}-${Math.random()}`)
      // Definir TTL
      .expire(windowKey, this.windowSize + 1)
      .exec();

    const requestCount = results[1];
    const newCount = requestCount + 1;

    if (newCount <= this.maxRequests) {
      return true; // Request permitido
    }

    // Se excedeu limite, remover requisição adicionada
    await this.redis.zrem(windowKey, `${now}-${Math.random()}`);
    return false; // Request rejeitado
  }

  async getRequestCount(identifier: string): Promise<number> {
    const now = Date.now();
    const windowStart = now - (this.windowSize * 1000);
    const windowKey = `sliding_window:${identifier}`;

    // Limpar e contar na janela atual
    await this.redis.zremrangebyscore(windowKey, '-inf', windowStart);
    return await this.redis.zcard(windowKey);
  }

  async getResetTime(identifier: string): Promise<number> {
    const now = Date.now();
    const windowKey = `sliding_window:${identifier}`;

    // Obter timestamp da requisição mais antiga na janela
    const oldestRequest = await this.redis.zrange(windowKey, 0, 0, 'WITHSCORES');

    if (!oldestRequest || oldestRequest.length === 0) {
      return now;
    }

    const oldestTimestamp = parseInt(oldestRequest[1]);
    return oldestTimestamp + (this.windowSize * 1000);
  }
}

Sliding Window Counter: otimização de memória

Sliding Window Log pode consumir muita memória para janelas grandes. Sliding Window Counter aproxima com dois contadores fixos adjacentes.

typescript// Sliding Window Counter otimizado
class SlidingWindowCounterRateLimiter {
  constructor(
    private redis: Redis,
    private windowSize: number,
    private maxRequests: number
  ) {}

  async allowRequest(identifier: string): Promise<boolean> {
    const now = Date.now();
    const currentWindow = Math.floor(now / (this.windowSize * 1000));
    const previousWindow = currentWindow - 1;

    const currentKey = `swc:${identifier}:${currentWindow}`;
    const previousKey = `swc:${identifier}:${previousWindow}`;

    const pipeline = this.redis.multi();

    // Incrementar contador da janela atual
    pipeline.incr(currentKey);
    pipeline.expire(currentKey, this.windowSize * 2);

    // Obter contadores
    pipeline.get(currentKey);
    pipeline.get(previousKey);

    const results = await pipeline.exec();
    const currentCount = parseInt(results[2] || '0');
    const previousCount = parseInt(results[3] || '0');

    // Calcular peso da janela anterior baseado em quanto tempo passou
    const windowProgress = (now % (this.windowSize * 1000)) / (this.windowSize * 1000);
    const estimatedCount = currentCount + (previousCount * (1 - windowProgress));

    return estimatedCount <= this.maxRequests;
  }
}

Quando usar Sliding Window

Fixed Window: simplicidade com trade-offs

Fixed Window divide o tempo em janelas fixas (ex: 1 minuto) e conta requisições em cada janela. Simples, mas sofre de edge effects: bursts nos limites da janela.

Implementação simples

typescript// Fixed Window em Redis
class FixedWindowRateLimiter {
  constructor(
    private redis: Redis,
    private windowSize: number, // em segundos
    private maxRequests: number
  ) {}

  async allowRequest(identifier: string): Promise<boolean> {
    const now = Math.floor(Date.now() / (this.windowSize * 1000));
    const windowKey = `fixed_window:${identifier}:${now}`;

    const currentCount = await this.redis.incr(windowKey);

    if (currentCount === 1) {
      // Primeira requisição na janela, definir TTL
      await this.redis.expire(windowKey, this.windowSize);
    }

    return currentCount <= this.maxRequests;
  }
}

Trade-offs de Fixed Window

Vantagens:

• Implementação extremamente simples
• Baixo overhead computacional
• Fácil de entender e debugar

Limitações:

• Edge effects: bursts nos limites da janela (ex: 100 req no último segundo da janela + 100 req no primeiro segundo da próxima = 200 req em 2 segundos)
• Não smooth: requisições podem ser permitidas em cluster no início da janela e rejeitadas no final

Escolha do algoritmo: framework de decisão

typescript// Framework de decisão para rate limiting
function selectRateLimitAlgorithm(requirements: RateLimitRequirements): RateLimitAlgorithm {
  const {
    allowBursts,
    requireConsistency,
    memoryConstraints,
    temporalPrecision,
    distributedDeployment
  } = requirements;

  // Token Bucket: flexibilidade com bursts
  if (allowBursts && !requireConsistency) {
    return {
      algorithm: 'Token Bucket',
      rationale: 'Permite bursts temporários com taxa de refill constante',
      implementation: 'Redis com sorted set'
    };
  }

  // Leaky Bucket: consistência sem bursts
  if (!allowBursts && requireConsistency) {
    return {
      algorithm: 'Leaky Bucket',
      rationale: 'Taxa de saída constante, enfileira excessos',
      implementation: 'Redis com list'
    };
  }

  // Sliding Window: precisão temporal
  if (temporalPrecision === 'high' && !memoryConstraints) {
    return {
      algorithm: 'Sliding Window Log',
      rationale: 'Contagem exata em janela deslizante',
      implementation: 'Redis com sorted set'
    };
  }

  // Sliding Window Counter: precisão com otimização
  if (temporalPrecision === 'high' && memoryConstraints) {
    return {
      algorithm: 'Sliding Window Counter',
      rationale: 'Aproximação de Sliding Window com menos memória',
      implementation: 'Redis com contadores'
    };
  }

  // Fixed Window: simplicidade
  return {
    algorithm: 'Fixed Window',
    rationale: 'Implementação simples, edge effects aceitáveis',
    implementation: 'Redis com contadores simples'
  };
}

Rate limiting hierárquico

Em sistemas complexos, múltiplos níveis de rate limiting são aplicados em cascata:

typescript// Rate limiting hierárquico
class HierarchicalRateLimiter {
  private limiters: Array<{
    limiter: RateLimiter;
    identifier: string;
    priority: number;
  }>;

  constructor() {
    this.limiters = [
      // Nível 1: Global (todos os requests da aplicação)
      {
        limiter: new TokenBucketRateLimiter(redis, 10000, 1000),
        identifier: 'global',
        priority: 1
      },

      // Nível 2: Por IP (proteção contra DDoS)
      {
        limiter: new SlidingWindowRateLimiter(redis, 60, 100),
        identifier: 'ip',
        priority: 2
      },

      // Nível 3: Por usuário autenticado
      {
        limiter: new TokenBucketRateLimiter(redis, 500, 50),
        identifier: 'user',
        priority: 3
      },

      // Nível 4: Por endpoint específico
      {
        limiter: new FixedWindowRateLimiter(redis, 60, 50),
        identifier: 'endpoint',
        priority: 4
      }
    ];
  }

  async allowRequest(context: RequestContext): Promise<RateLimitResult> {
    const results = [];

    for (const { limiter, identifier, priority } of this.limiters) {
      const key = this.buildIdentifier(context, identifier);
      const allowed = await limiter.allowRequest(key);

      results.push({
        level: identifier,
        allowed,
        priority
      });

      if (!allowed) {
        // Rate limit atingido neste nível
        return {
          allowed: false,
          level: identifier,
          retryAfter: await limiter.getRetryAfter(key),
          details: results
        };
      }
    }

    return {
      allowed: true,
      details: results
    };
  }

  private buildIdentifier(context: RequestContext, level: string): string {
    switch (level) {
      case 'global':
        return 'global';

      case 'ip':
        return context.ipAddress;

      case 'user':
        return context.userId || context.ipAddress;

      case 'endpoint':
        return `${context.userId || 'anonymous'}:${context.method}:${context.path}`;

      default:
        return 'unknown';
    }
  }
}

Headers de resposta para clientes

Padronizar headers de resposta permite clientes implementarem retry respeitoso:

typescript// Headers de rate limit
interface RateLimitHeaders {
  'X-RateLimit-Limit': number; // Limite total
  'X-RateLimit-Remaining': number; // Requisições restantes
  'X-RateLimit-Reset': number; // Timestamp Unix de reset
  'Retry-After': number; // Segundos até retry (quando limitado)
}

function buildRateLimitHeaders(
  limit: number,
  remaining: number,
  resetTime: number
): RateLimitHeaders {
  return {
    'X-RateLimit-Limit': limit,
    'X-RateLimit-Remaining': Math.max(0, remaining),
    'X-RateLimit-Reset': resetTime,
    'Retry-After': Math.ceil((resetTime - Date.now()) / 1000)
  };
}

// Exemplo de uso em middleware
export async function rateLimitMiddleware(req, res, next) {
  const context = buildRequestContext(req);
  const result = await rateLimiter.allowRequest(context);

  // Adicionar headers
  const headers = buildRateLimitHeaders(
    result.limit,
    result.remaining,
    result.resetTime
  );

  Object.entries(headers).forEach(([key, value]) => {
    res.setHeader(key, value);
  });

  if (!result.allowed) {
    return res.status(429).json({
      error: 'RATE_LIMIT_EXCEEDED',
      message: 'Too many requests',
      retryAfter: headers['Retry-After']
    });
  }

  next();
}

Monitoramento e alertas

Métricas-chave para rate limiting

typescript// Métricas de rate limiting
interface RateLimitMetrics {
  // Taxa de rejeições
  rejectionRate: number; // % de requisições rejeitadas
  rejectionByLevel: {
    global: number;
    ip: number;
    user: number;
    endpoint: number;
  };

  // Identificadores problemáticos
  topRejectedIPs: Array<{
    ip: string;
    rejections: number;
    lastRejected: Date;
  }>;

  topRejectedUsers: Array<{
    userId: string;
    rejections: number;
    lastRejected: Date;
  }>;

  // Tendências
  rejectionTrend: Array<{
    timestamp: Date;
    rejectionRate: number;
    totalRequests: number;
  }>;

  // Configurações sub-ótimas
  sensitiveEndpoints: Array<{
    endpoint: string;
    rejectionRate: number;
    suggestedLimit: number;
  }>;
}

Alertas recomendados

yamlrate_limiting_alerts:
  high_rejection_rate:
    condition: "RejectionRate > 10% for 5 minutes"
    severity: warning
    action: "Review rate limit configurations"

  abuse_detection:
    condition: "Same IP rejected > 100 times in 1 minute"
    severity: critical
    action: "Investigate potential DDoS or abuse"

  configuration_issue:
    condition: "RejectionRate > 50% for single endpoint"
    severity: critical
    action: "Check if rate limit is too restrictive"

  global_limit_near:
    condition: "Global limit usage > 80%"
    severity: warning
    action: "Monitor for capacity issues"

Conclusão

Rate limiting eficaz não é sobre escolher o algoritmo mais sofisticado—é sobre escolher o algoritmo certo para o contexto. Token Bucket oferece flexibilidade com bursts. Leaky Bucket garante consistência. Sliding Window fornece precisão temporal. Fixed Window oferece simplicidade.

Para produção, o importante é:

1. Escolher o algoritmo baseado em requisitos reais
2. Implementar rate limiting em múltiplos níveis (global, IP, usuário, endpoint)
3. Expor headers de resposta para clientes
4. Monitorar métricas e ajustar configurações continuamente
5. Alertar sobre abuse e configurações sub-ótimas

Rate limiting não é feature de luxo—é salvaguarda essencial para qualquer API em produção.

Sua API precisa de proteção contra abuso e DDoS? Fale com especialistas em arquitetura da Imperialis para implementar rate limiting robusto com os algoritmos corretos para seu contexto.

Fontes

• Rate Limiting Algorithms (Cloudflare) — Visão geral de algoritmos
• Token Bucket Algorithm — Explicação matemática
• Leaky Bucket Algorithm — Explicação matemática
• Rate Limiting with Redis — Padrões de implementação