Token bucket, leaky bucket e janela deslizante: como os algoritmos de rate limiting se diferenciam

O que é

A parte de política (qual chave, quais cabeçalhos, qual status) é tratada em outro lugar; este artigo compara os algoritmos de contagem.

• Janela fixa: um contador por chave e por intervalo, zerado na fronteira. É a opção mais barata, mas um cliente pode gastar o limite inteiro no fim de uma janela e outro limite completo no início da seguinte: o dobro da taxa nominal em um intervalo curto.
• Log deslizante: guarda o timestamp de cada requisição e conta as que caem dentro do intervalo mais recente. É exato, mas a memória cresce com o volume.
• Contador de janela deslizante: guarda as contagens da janela atual e da anterior e estima o intervalo mais recente como previous * (1 - elapsed / window) + current. É aproximado, usa memória constante e não tem rajada na fronteira.
• Token bucket: um balde guarda até um número máximo de tokens e é reabastecido a uma taxa fixa; cada requisição consome um token e é rejeitada quando não resta nenhum. A configuração TokenBucket do Envoy nomeia exatamente esses parâmetros: max_tokens, tokens_per_fill e fill_interval, e o balde começa cheio.
• Leaky bucket: as requisições entram em uma fila que é esvaziada a uma taxa fixa; a fila tem uma capacidade, e o que a excede é rejeitado. O limit_req do nginx documenta esse como seu método, com rate, um tamanho de burst e nodelay ou delay para escolher se as requisições excedentes dentro do burst são atrasadas até a taxa configurada ou atendidas imediatamente.

Por que importa

O algoritmo determina a tolerância a rajadas, a memória por chave e se os clientes veem rejeição ou latência adicional. Clientes que tentam de novo no momento em que a janela fixa é zerada chegam todos juntos; um token bucket absorve uma rajada curta e depois impõe a média; um leaky bucket com atraso suaviza a carga do backend ao custo de tempo de espera na fila.

Como aplicar

• Use por padrão um token bucket por chave: armazene a contagem de tokens e o instante da última reposição, reponha de forma preguiçosa a cada requisição e torne a atualização atômica (um script Redis ou um lock em processo).
• Defina o tamanho do balde como a rajada que você aceita e a taxa de reposição como o limite sustentado; documente os dois números.
• Use um contador de janela deslizante quando a promessa for um simples "N requisições por minuto" e rajadas na fronteira forem inaceitáveis.
• Use um leaky bucket com atraso na frente de um backend, não na borda, onde clientes interativos preferem um 429 rápido com Retry-After.
• Em uma implantação distribuída, centralize o estado por chave ou aceite que os limites por instância se multipliquem pelo número de instâncias; use um relógio monotônico na aritmética de reposição.

Armadilhas

Saltos do relógio de parede corrompem a aritmética de reposição. Um balde que começa vazio bloqueia toda chave nova até se encher. Logs deslizantes são uma superfície de ataque à memória. Usar o IP do cliente como chave atrás de NAT ou de uma CDN limita a população errada. Regras de rajada não documentadas obrigam clientes bem-comportados a adivinhar.