Balde furado (leaky bucket)

Um balde com um furo no fundo. A água entra na taxa que quiser, e sai pelo furo em uma taxa constante. Despeje mais rápido do que ele escoa e o balde enche; continue e ele transborda.

A água são as requisições. O furo é a sua taxa de processamento.

O balde furado (leaky bucket) mantém as requisições recebidas em uma fila e as processa em uma taxa fixa, então o que chega ao servidor é suave, não importa o quão irregular tenha sido a chegada.

Observando o balde encher e escoar

Capacidade de cinco requisições, processando duas por segundo, começando vazio:

Segundo	Chegam	Enfileiradas	Processadas	Na fila depois	Descartadas
1	4	4	2	2	0
2	4	3, então 5 na fila	2	3	1
3	0	0	2	1	0
4	0	0	1	0	0

É no segundo dois que a capacidade se mostra um problema. Quatro requisições chegam contra uma fila que já tem duas, e só cabem três. A oitava requisição é descartada de imediato.

Duas propriedades surgem daí:

• A taxa de saída nunca varia. Duas por segundo, tenham chegado oito requisições ou nenhuma.
• A fila é FIFO (primeiro a entrar, primeiro a sair). A requisição que chegou primeiro é processada primeiro.

Um token bucket diz: gaste seus tokens quando quiser. Um leaky bucket diz: entre na fila, eu te processo no meu ritmo.

JunoObservando o balde encher e escoar A diferença em relação a todos os algoritmos anteriores: uma requisição que chega quando o sistema está ocupado não é recusada, ela espera.

Requisições só são descartadas quando a própria fila está cheia, então o balde absorve uma rajada em vez de rejeitá-la.

JunoObservando o balde encher e escoar Esperar tem um custo real, e quem paga é o cliente. Uma requisição enfileirada atrás de outras quatro, a duas por segundo, espera dois segundos antes de qualquer coisa começar.

Do ponto de vista de quem fez a chamada, isso é indistinguível de um servidor lento.

Por isso uma requisição enfileirada ainda precisa de um timeout. Sem um limite máximo de espera, uma rajada vira uma pilha de clientes que já desistiram, mas ainda mantêm conexões abertas.

JunoObservando o balde encher e escoar Comportamento medido, para um balde de 20 escoando 5 por segundo: 25 requisições chegando de uma vez tiveram 20 aceitas e 5 descartadas, com a vigésima esperando 4 segundos antes de ser processada.

Esse último número é o que importa para o design. Uma fila cheia somada a um escoamento lento deixa as requisições do final esperando muito tempo, e 4 segundos já passou do ponto em que a maioria dos clientes já tentou de novo ou desistiu.

Capacidade não é de graça só porque essas requisições não foram recusadas.

O que sugere dimensionar a capacidade a partir da latência aceitável, não da memória disponível. A 5 por segundo, um pior caso de 2 segundos significa uma fila de 10, não de 20.

Em que é bom e em que é ruim

Pontos fortes	Pontos fracos
Suaviza rajadas em uma taxa de saída constante	Sem flexibilidade para um pico legítimo
A fila evita sobrecarga adiante no sistema	Prioriza a estabilidade do sistema em detrimento da experiência do usuário
Simples de entender e implementar	Clientes esperam mesmo quando o servidor teria conseguido atender
Carga previsível, seja lá o que chegar	A latência cresce com a profundidade da fila

Os pontos fracos são todos a mesma escolha vista de ângulos diferentes. Um leaky bucket protege o servidor fazendo os clientes esperarem, e faz isso mesmo quando o servidor tinha capacidade sobrando.

Isso combina bem com gerenciamento de banda de rede, streaming de vídeo e tratamento constante de requisições no servidor, onde uma taxa previsível vale mais do que uma resposta rápida a uma rajada.

JunoEm que é bom e em que é ruim Cada linha dessa tabela vem da mesma decisão: a taxa de saída é fixa e não se adapta.

Isso é o ponto forte quando você precisa de carga previsível, e o ponto fraco quando um cliente está esperando por algo que o servidor poderia ter atendido na hora.

JunoEm que é bom e em que é ruim Use isso quando o que você está protegendo não consegue absorver um pico: uma API downstream com seu próprio limite, um banco de dados que degrada sob concorrência, um provedor de pagamento que cobra por chamada.

Use um token bucket quando o que você está protegendo consegue lidar com uma rajada e você quer que os clientes sintam a resposta como ágil. A pergunta é o que está por trás do limitador, não o que está na frente dele.

JunoEm que é bom e em que é ruim O FIFO estrito é a parte que vale a pena questionar. Sob sobrecarga sustentada, ele produz head-of-line blocking, em que uma requisição lenta atrasa tudo o que vem atrás dela, por mais baratas que essas requisições fossem.

Isso também significa que um cliente que inundou a fila mantém prioridade sobre outro que chegou depois com uma única requisição, então um leaky bucket sozinho não garante nenhuma justiça entre clientes. Baldes por cliente resolvem isso e multiplicam seu estado.

Vale nomear a semelhança também: um leaky bucket é uma fila de trabalho limitada com um limite de taxa sobre o worker.

Se você já roda uma fila de jobs com limites de concorrência, você já tem quase tudo isso, e a questão passa a ser se o limitador deveria estar ali em vez de estar no caminho da requisição.

Coloque em prática

Um leaky bucket com capacidade 5, escoando 2 requisições por segundo, começando vazio.

1. Seis requisições chegam de uma vez. O que acontece com cada uma?
2. Quanto tempo a sexta requisição a chegar espera antes de ser processada, se é que ela consegue entrar?
3. As mesmas seis chegam, mas espalhadas uma por segundo. O que acontece?
4. Qual algoritmo seria mais adequado para um endpoint que chama um provedor de pagamento que cobra por requisição, e por quê?

Compare suas respostas

#	Resposta	Por quê
1	Cinco entram na fila, uma é descartada	A fila comporta cinco e nada escoou ainda, já que a rajada é instantânea
2	Ela nunca entra	A sexta é a que é descartada. A quinta é a última aceita, e a duas por segundo ela espera dois segundos e meio
3	Todas as seis são processadas, nenhuma descartada, nenhuma esperando	Uma por segundo é mais lento do que o escoamento de duas por segundo, então a fila nunca se acumula
4	Leaky bucket	A restrição está downstream e custa dinheiro por chamada, então uma taxa de saída previsível é o que você quer. Um token bucket transformaria uma rajada de requisições em uma rajada de cobranças

A pergunta três é a que vale a pena guardar: nenhum desses algoritmos faz absolutamente nada com o tráfego dentro do limite. Eles só ficam visíveis nas bordas.

Para onde isso vai a seguir

Cinco algoritmos, e todos eles terminam uma requisição que passa do limite com uma recusa ou uma espera imposta silenciosamente.

O throttling torna a espera deliberada e visível, desacelerando um cliente à medida que ele se aproxima de um limite em vez de recusá-lo justo no limite, e depois combina os dois em uma única solução.