Token bucket

Todos os algoritmos vistos até agora tratam a rajada como um problema. Mas muitas rajadas são normais: uma página carregando seis coisas ao mesmo tempo, ou um cliente que ficou ocioso por um minuto e agora tem trabalho a fazer.

O token bucket permite isso de propósito. Os tokens se acumulam a uma taxa constante, uma requisição gasta um token, e um cliente que ficou quieto tem alguns guardados.

Folhas e lagartas

Uma planta segura no máximo cinco folhas e cresce três por dia. Cada lagarta que chega come uma folha, e uma lagarta sem folha disponível não sobrevive.

Dia	Folhas que crescem	Lagartas	Resultado	Folhas restantes
1	3	2	Ambas comem	1
2	3, total de 4	5	4 comem, 1 não	0
3	3	0	Nada acontece	3
4	2, limitado a 5	0	Nada acontece	5

Três ideias nessa tabela:

• Uma folha é um token, e uma requisição gasta um.
• Os tokens chegam a uma taxa fixa, quer alguém esteja pedindo ou não.
• A planta não consegue guardar mais do que sua capacidade, então no dia quatro crescem duas folhas em vez de três.

A capacidade é o que permite a rajada. Um bucket cheio pode ser gasto de uma só vez, então um cliente que ficou quieto pode enviar cinco requisições num instante e depois precisa esperar mais folhas crescerem.

A taxa de reabastecimento define a média em longo prazo. A capacidade define o tamanho da rajada que você tolera.

JunoFolhas e lagartas O dia quatro é o que vale a pena parar para pensar. Normalmente cresceriam três folhas, mas só crescem duas, porque a planta já está com quatro e não consegue guardar seis.

Esse teto é a razão de a rajada ter um tamanho limite. Sem ele, um cliente ocioso por uma hora voltaria podendo enviar de uma vez tudo o que acumulou naquela hora.

JunoFolhas e lagartas São dois ajustes, e eles cumprem funções diferentes. A taxa de reabastecimento é a taxa de transferência sustentada que você está disposto a atender. A capacidade é o quanto disso um cliente pode guardar e gastar de uma vez.

Então um bucket de 10, reabastecendo 6 a cada 3 segundos, tem média de 2 por segundo e tolera 10 de uma vez. Mesma média, mas uma sensação bem diferente de um bucket que reabastece 2 a cada segundo.

JunoFolhas e lagartas A capacidade também é o seu pior cenário, e ela deveria ser dimensionada de acordo com o que o endpoint consegue realmente absorver. Um bucket de 10.000 tem uma média tranquila e ainda assim pode disparar 10.000 requisições em um único instante, que é o número que o seu banco de dados vai enxergar.

O outro custo é o estado: um bucket por cliente significa uma contagem de tokens e um timestamp do último reabastecimento para cada cliente que você já viu, o que é mais do que o contador de uma janela fixa e menos do que a lista de timestamps de um log deslizante.

Implementações em produção geralmente dispensam o timer por completo e calculam os tokens de forma preguiçosa na leitura, a partir do tempo decorrido desde o último reabastecimento. Sem job em segundo plano, e buckets de clientes ociosos não custam nada até eles voltarem.

Construindo o bucket

O estado é composto por dois números, e a lógica é feita de duas decisões.

class TokenBucket {
  constructor(capacity, refillRate, refillInterval) {
    this.capacity = capacity
    this.refillRate = refillRate
    this.refillInterval = refillInterval
    this.tokens = capacity          // começa cheio
    this.secondsSinceLastRefill = 0
  }

  processRequests(numRequests) {
    this.secondsSinceLastRefill += 1

    if (this.secondsSinceLastRefill >= this.refillInterval) {
      this.tokens = Math.min(this.capacity, this.tokens + this.refillRate)
      this.secondsSinceLastRefill = 0
    }

    const accepted = Math.min(numRequests, this.tokens)
    const rejected = numRequests - accepted

    this.tokens -= accepted

    return { accepted, rejected }
  }
}

As duas chamadas de Math.min são as que fazem o trabalho de verdade.

A primeira limita o reabastecimento à capacidade, então os tokens nunca ultrapassam o teto. A segunda limita a aceitação aos tokens disponíveis, então uma requisição por nove tokens contra um bucket com apenas um aceita um e rejeita oito.

Usar >= na verificação do reabastecimento em vez de == é proposital. Se um tick for perdido por algum motivo, uma comparação exata pularia o reabastecimento e o bucket nunca mais se encheria.

JunoConstruindo o bucket Começar com o bucket cheio é uma escolha, e uma escolha gentil. Um cliente novo consegue agir imediatamente em vez de esperar seus primeiros tokens aparecerem.

Começar vazio seria mais rígido e faria a primeira visita de qualquer um parecer quebrada.

JunoConstruindo o bucket Repare que um atendimento parcial é possível: nove requisições contra um único token resultam em uma aceita e oito rejeitadas, em vez de recusar todas.

Isso importa para como o cliente deve reagir. Parte do trabalho dele teve sucesso, então tentar tudo de novo duplicaria a parte que já passou.

JunoConstruindo o bucket Essa versão avança o tempo contando rodadas, o que combina com um jogo baseado em turnos, mas não com um servidor. O tráfego real não chega em ticks, então o código em produção guarda um timestamp e calcula o acúmulo na leitura: tempo decorrido vezes a taxa, somado à contagem atual, limitado pela capacidade.

Isso também permite que os tokens sejam fracionários, o que importa em taxas baixas. Com acúmulo em números inteiros e uma taxa abaixo de um token por intervalo, um cliente pode arredondar para zero para sempre e nunca se recuperar.

Concorrência é a outra diferença. Duas requisições simultâneas que leem this.tokens antes que qualquer uma escreva serão ambas aceitas contra o mesmo token, o que é a mesma corrida de ler-decidir-escrever que deixou 400 requisições concorrentes passarem por um limite de 100 em um contador do Redis. A verificação precisa ser atômica.

Os parâmetros mudam tudo

Duas configurações, o mesmo algoritmo.

Capacidade 10, reabastecimento de 6 a cada 3 segundos. Aproximadamente duas por segundo sustentadas, com espaço para dez de uma vez. Acompanhando segundo a segundo:

Rodada	Solicitadas	Aceitas	Rejeitadas	Tokens restantes
1	3	3	0	7
2	5	5	0	2
3	7	7	0	1, depois de reabastecer para 8
4	9	1	8	0

Generoso. As rajadas são absorvidas, e esgotar o bucket exige um esforço deliberado.

Capacidade 8, reabastecimento de 2 a cada 10 segundos. Agora as primeiras oito requisições são de graça, e depois quase nada é. Envie cinco, depois mais cinco, e você fica vazio com oito segundos de espera para dois tokens.

Mesmo algoritmo, experiência completamente diferente. Um cliente sob a segunda configuração precisa pensar em quando gastar, porque os tokens são escassos e demoram para voltar.

JunoOs parâmetros mudam tudo Vale a pena testar mentalmente a segunda configuração antes de continuar lendo. Oito tokens, e depois mais dois a cada dez segundos.

Isso não é um limite de taxa que molda o tráfego. É um que faz o cliente racionar cada requisição, e o algoritmo não mudou em nada.

JunoOs parâmetros mudam tudo O intervalo de reabastecimento é o parâmetro que as pessoas configuram sem cuidado, e é ele que decide como o limite vai se comportar na prática. Seis tokens a cada três segundos e dois a cada segundo têm a mesma média, mas se comportam de formas completamente diferentes.

Intervalos longos significam longos períodos secos seguidos de um acúmulo de uma vez. Intervalos curtos parecem mais suaves. Prefira o intervalo mais curto que o seu armazenamento consiga suportar.

JunoOs parâmetros mudam tudo Medido contra um token bucket, 13 requisições chegando de uma vez contra um bucket de 10 aceitaram exatamente 10 e rejeitaram 3, retornando retryAfterMs: 500. Deixado ocioso por 3 segundos, o mesmo bucket acumulou 6 tokens.

Esse retryAfterMs é o que vale a pena expor. Um token bucket consegue calcular com precisão quando o próximo token vai chegar, o que uma janela fixa não consegue, então dá para dizer ao cliente exatamente quanto tempo esperar, em vez de deixá-lo adivinhar.

Retorne isso no cabeçalho Retry-After e um cliente bem-comportado para de martelar o seu serviço. Se você omitir isso, a única estratégia dele é tentar de novo imediatamente, exatamente o que você estava tentando evitar.

Coloque em prática

Um bucket com capacidade 5, reabastecendo 2 tokens a cada 2 segundos, começando cheio.

1. Um cliente envia 5 requisições de uma vez. Quantas são aceitas, e o que resta?
2. Dois segundos depois ele envia 3. O que acontece?
3. O cliente então espera 10 segundos. Quantos tokens ele tem?
4. Qual é a taxa sustentada que esse bucket permite, e qual é a maior rajada possível?

Compare suas respostas

1. Todas as 5 aceitas, 0 restantes. O bucket começa cheio e uma requisição gasta um token. Esvaziá-lo em um único instante é exatamente a rajada que a capacidade existe para permitir.

2. Duas aceitas, uma rejeitada. Dois segundos se passaram, então o bucket reabastece 2 tokens. Três requisições chegam contra 2 tokens, então Math.min(3, 2) aceita duas e a terceira é recusada.

3. Cinco, não dez. Dez segundos acumulariam 10 tokens, mas a capacidade limita isso a 5. Essa é a regra do dia quatro: o tempo ocioso não se acumula indefinidamente, o que é justamente o que impede um cliente que ficou quieto por muito tempo de voltar com uma rajada enorme.

4. Um por segundo sustentado, cinco de uma vez. Dois tokens a cada dois segundos é a média em longo prazo, e a capacidade 5 é a maior rajada instantânea possível.

A pergunta quatro é o par que vale a pena guardar. A taxa de reabastecimento e a capacidade respondem a duas perguntas diferentes, e resumir um token bucket a um único número perde uma dessas informações.

Para onde isso vai a seguir

O token bucket deixa o cliente decidir quando gastar, então o tráfego que chega ao seu servidor continua irregular. Limitado, mas irregular.

O leaky bucket segue outro caminho: aceitar a rajada e depois liberá-la a uma taxa constante, de modo que o que o servidor vê seja suave, não importa como o tráfego chegou.