Limitação de taxa

O panorama: palavras que você vai encontrar

Um limitador de taxa (rate limiter) é um pequeno porteiro colocado na frente de um serviço. Para cada requisição ele faz uma pergunta: 'este cliente já usou a sua parte?'. Se não, a requisição entra. Se sim, ela é recusada. Tudo neste resumo trata de como o porteiro conta e do que acontece com quem ele recusa.

Palavras que você vai encontrar

• Chave (key): o nome sob o qual o limitador conta. Pode ser um endereço IP, um usuário, uma chave de API ou uma empresa cliente. Cada chave tem a sua própria contagem.
• Limite: o maior número de requisições permitidas, por exemplo 100.
• Janela: o pedaço de tempo a que o limite se refere, por exemplo 'por minuto'. Então '100 por minuto' significa limite 100 e janela de 60 segundos.
• Taxa: quantas requisições por unidade de tempo, por exemplo 5 por segundo.
• [[Rajada (burst)|muitas requisições que chegam quase no mesmo instante]]: muitas requisições juntas. Alguns limitadores permitem uma rajada pequena, outros não.
• Admitir e rejeitar: admitir uma requisição é deixá-la passar. Rejeitar é recusá-la (por exemplo, com a resposta 429).
• Vazão (throughput): quantas requisições por segundo realmente são concluídas.

As duas perguntas que todo limitador responde

Uma regra como '10 requisições por segundo' não diz o que acontece quando 20 requisições chegam em 200 milissegundos. Cada algoritmo responde isso do seu jeito, e essa resposta é o que você realmente escolhe ao escolher um algoritmo.

Por que e onde limitar

Por que um serviço recusaria requisições de propósito? Porque um servidor tem uma quantidade fixa de trabalho que consegue fazer por segundo. Se um cliente toma demais, os outros esperam ou recebem erros. Um limitador dá quatro coisas: mantém o serviço disponível, mantém os clientes justos entre si, mantém o custo sob controle (algumas requisições custam dinheiro de verdade) e atrapalha a força bruta (tentar milhares de senhas) e o scraping (copiar um site inteiro por máquina).

Qual chave contamos?

Cuidado com o cabeçalho X-Forwarded-For. Ele é uma linha comum da requisição, e quem envia a requisição escreve o que quiser nela. Só dá para confiar quando um proxy que você controla o preencheu. Se um serviço está aberto à Internet sem proxy na frente, ele deve usar o endereço da conexão de verdade. Se usar o cabeçalho, o atacante só muda o cabeçalho a cada vez e ganha chaves novas sem fim.

Empilhando limites

Um limitador só controla o total da chave que ele conta. Se cada usuário pode mandar 100 por minuto e uma empresa cliente tem 400 usuários, essa empresa pode mandar até 40.000 por minuto. Por isso sistemas grandes empilham chaves: um limite por usuário, um por tenant, às vezes um global. Uma requisição precisa passar por todos. Também ajuda ter um limite diferente para cada endpoint: POST /login e o envio de SMS devem ter limites bem baixos, porque cada tentativa é um risco ou custa dinheiro, enquanto uma leitura barata pode ter um limite alto. Um limite folgado para tudo acaba folgado demais para os endpoints sensíveis.

Onde o limitador mora?

cliente --> CDN/borda --> gateway --> aplicação --> dependência
  (1)         (2)           (3)          (4)           (5)

(1) no próprio cliente (educado, mas não obrigatório)
(2) na borda: barato para rejeitar, pouco contexto
(3) no gateway de API ou proxy reverso
(4) na aplicação: conhece usuário e operação
(5) logo antes de uma dependência cara (SMS, banco)

Quanto mais perto da origem do tráfego, mais barato é dizer não, mas menos o limitador sabe sobre a requisição. Por isso as camadas se combinam: um limite grosseiro e barato na borda, e limites finos por usuário e por operação na aplicação. Para proteger uma dependência de capacidade ou custo limitado (por exemplo um provedor de SMS que cobra por mensagem), coloque o limitador logo antes dela, conte na unidade que ela cobra (mensagens, não requisições) e compartilhe entre todos os caminhos de código, porque um job noturno pode chegar ao provedor sem passar pelo gateway.

Justo não é o mesmo que seguro

Imagine um serviço que aguenta 400 requisições por segundo e 10 clientes que podem mandar 100 por segundo cada. Os limites são justos, mas juntos permitem 1.000 por segundo, mais que 400. Limites por cliente normalmente são vendidos acima da capacidade, na esperança de que nem todos usem o máximo ao mesmo tempo. Para proteger o serviço você também precisa de um limite global ou de descarte de carga. E uma enxurrada de 200.000 endereços diferentes, cada um abaixo do seu limite, ainda derruba o serviço, porque o dano vem da soma. Um limitador dentro da aplicação também decide tarde: a requisição já usou uma conexão e algum trabalho.

Janela fixa

O jeito mais simples de contar é cortar o tempo em fatias iguais, como as páginas de um calendário, e guardar um placar por fatia. Cada fatia é uma janela de tamanho W. A janela de número k cobre do instante k vezes W até (sem incluir) k+1 vezes W. Para W = 10 segundos as janelas são [0,10), [10,20), [20,30) e assim por diante. O parêntese significa 'não incluído'. Então um instante exatamente em 10 pertence à janela que está começando.

A regra: quando uma requisição chega, ache a janela dela, olhe o contador dessa janela e admita a requisição se o contador estiver abaixo do limite. Depois some um. A cada fronteira o contador volta a zero. O estado é minúsculo: um contador e o número da janela por cliente. Essa é a grande qualidade do algoritmo. A memória não depende do limite nem do tamanho da janela, então passar de um limite de 500 para 5.000 não custa nada a mais.

O ponto fraco: a fronteira

  janela [0,10)            janela [10,20)
|------------------------|------------------------|
                   8 9 9 | 10 11 12
                   ^^^^^   ^^^^^^^^
                   3 admitidas  3 admitidas

contador: 0 .. 1 2 3     | 0 -> 1 2 3  (volta a zero)

Um cliente pode gastar todo o limite no fim de uma janela e de novo no começo da próxima. Num intervalo bem menor que W ele consegue passar até 2 vezes o limite. A regra parece prometer L por janela, mas permite o dobro perto de uma fronteira. Esse é o defeito clássico da janela fixa.

Onde as janelas começam?

Há dois jeitos comuns de montar isso no Redis. No primeiro, o número da janela vai no nome da chave (por exemplo rl:client42:7), então as janelas são alinhadas ao relógio e iguais para todos. No segundo há uma chave por cliente, a chave recebe um tempo de vida com EXPIRE só quando o INCR devolve 1, e a janela começa na primeira requisição do cliente:

local n = redis.call('INCR', KEYS[1])
if n == 1 then
	redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return n

As duas formas ainda permitem uma rajada dupla, só que em lugares diferentes. Na segunda forma a primeira rajada fica limitada ao limite, mas ainda há uma fronteira quando a chave expira. As duas linhas ficam juntas em um script para que a chave nunca fique sem expiração.

Pequenos detalhes que mudam os números

• Mesma média, janela diferente. '600 por minuto' como uma janela de 60 s permite até 1.200 perto de uma fronteira. '10 por segundo' como janelas de 1 segundo mantém a rajada pequena, mas rejeita um bom cliente que manda um lote pequeno de uma vez. O tamanho da janela escolhe o tamanho da rajada que você tolera.
• Contar requisições rejeitadas. Na janela fixa isso não muda quem é admitido, porque o contador zera na fronteira de qualquer jeito. Só muda o número guardado, que pode ser uma boa medida do excesso.
• Clientes sincronizados. Com janelas alinhadas ao relógio, todo mundo recebe o limite de volta no mesmo instante. Os clientes que esperam a renovação tentam de novo todos juntos, uma debandada na fronteira. Um atraso aleatório no cliente (jitter) ou um algoritmo sem fronteira ajuda.

Log deslizante e contador deslizante

A janela fixa esquece tudo na fronteira. E se a janela andasse junto com cada requisição? Em vez de 'esta hora do calendário', pergunte: 'nos últimos W segundos antes de agora, quantas requisições foram admitidas?'. Essa janela desliza para a frente o tempo todo, então não há fronteira para explorar. Há dois jeitos de fazer isso.

Log deslizante: exato, mas pesado

O log deslizante (sliding log) guarda o timestamp de cada requisição admitida, como um caderno onde o porteiro anota a hora em que cada convidado entrou. Quando uma requisição chega no instante t, ele apaga as anotações velhas demais, conta o que sobrou e admite a recém-chegada se a contagem estiver abaixo do limite L. A convenção usada aqui: uma anotação com exatamente W segundos já expirou, então a janela é (t - W, t]. Só as requisições admitidas são anotadas.

O log esquece cada requisição por conta própria, exatamente W segundos depois de admiti-la, então em qualquer intervalo de W segundos nunca há mais que L requisições admitidas. O preço é a memória: até L timestamps por cliente. Um limite de 10.000 por hora pode significar 10.000 entradas para um único cliente. No Redis isso costuma ser um sorted set por cliente, com o timestamp como score.

Contador deslizante: barato e quase exato

O contador deslizante (sliding counter) guarda só dois números por cliente: a contagem da janela fixa anterior (prev) e a da atual (cur). Para estimar os últimos W segundos ele usa uma parte da janela anterior mais toda a atual:

estimativa = prev * (1 - elapsed / W) + cur
admite quando estimativa < limite   (a estimativa é calculada antes de contar a nova requisição)

Exemplo: limite 100, W = 60 s, prev = 80, cur = 30, e a requisição chega 15 s depois do início da janela. Três quartos da janela anterior ainda contam (1 - 15/60 = 0,75), então a estimativa é 80 x 0,75 + 30 = 90, abaixo de 100: admitida. O peso da janela anterior cai de forma contínua de 1 até 0, então um cliente que gastou o limite recupera as vagas aos poucos, não todas de uma vez.

A estimativa depende de um palpite: que as requisições da janela anterior estavam espalhadas por igual nela, porque o contador só sabe quantas foram, não quando. Quando o palpite está errado, a resposta erra, de forma limitada:

• Requisições anteriores concentradas no fim da janela: todas ainda estão dentro dos últimos W segundos, mas só uma fração é contada. O contador subestima e pode admitir mais que o limite.
• Requisições anteriores concentradas no começo: nenhuma ainda está dentro dos últimos W segundos, mas uma fração ainda é contada. O contador superestima e rejeita requisições que o log exato admitiria.

Os três algoritmos de janela lado a lado

Balde de fichas (token bucket)

Imagine um balde de fichas de brinquedo. Para fazer uma requisição você paga uma ficha. Uma torneira solta fichas novas no balde numa velocidade constante, mas o balde só guarda um tanto, e as fichas extras transbordam. Se o balde está vazio, você espera a próxima ficha. Esse é o token bucket.

Os dois botões

Ter dois botões é a força do algoritmo: a rajada que você tolera e a média que você sustenta deixam de ser o mesmo número. Um balde vazio significa que o cliente gastou a sua rajada: a requisição é recusada (num limitador de API) ou atrasada (num modelador de tráfego) até aparecer uma ficha. Enquanto o balde fica vazio, a vazão é exatamente r.

O saldo e o teto

// saldo = min(B, saldo + r * decorrido)
function allow(b: { tokens: number; last: number }, now: number): boolean {
	const elapsed = now - b.last;
	b.tokens = Math.min(B, b.tokens + elapsed * r);
	b.last = now;
	if (b.tokens >= 1) { b.tokens -= 1; return true; }
	return false;
}

Ninguém precisa de um timer que solta uma ficha a cada instante. Como as fichas chegam em velocidade constante, o saldo anterior e o instante da última atualização bastam para calcular o saldo agora. Isso se chama reposição preguiçosa (lazy refill), e o estado por cliente são só dois campos. Frações de ficha contam: com r = 0,5 por segundo, dois segundos dão uma ficha inteira.

Quantas podem passar?

Em qualquer intervalo de T segundos um token bucket admite no máximo B + r x T requisições: a rajada guardada mais o que a torneira produziu no meio tempo. Quanto maior o intervalo, menos o termo B pesa, e a média se aproxima de r.

Por isso não dá para escolher r só pelo teto. Se uma API tolera no máximo N requisições em quaisquer T segundos, você precisa de B + r x T <= N, não só de r x T <= N. Exemplo: no máximo 100 a cada 10 segundos e uma rajada de 40 significa r x 10 <= 60, então r = 6 por segundo. Cada ficha dada à rajada é uma a menos para a taxa sustentada.

Mais ideias

• Tempo de espera. Se o saldo é s (abaixo de 1), a próxima requisição será admitida depois de (1 - s) / r segundos. É o número que um servidor pode mandar em Retry-After.
• Custo ponderado. Uma requisição pode custar mais de uma ficha. Uma exportação pode custar 25 fichas e uma leitura 1. A regra é: admite quando saldo >= custo, sem pagamento parcial. Com saldo baixo, as chamadas baratas continuam passando enquanto as caras esperam.
• Modelagem de tráfego com bytes. As fichas podem ser bytes. Com balde B = 16 MB, taxa de fichas R = 2 MB/s e um enlace que envia no máximo M = 10 MB/s, um balde cheio deixa o host enviar na velocidade máxima por B / (M - R) = 16 / 8 = 2 segundos, e depois cai para R.

Balde furado (leaky bucket)

Agora vire a figura do avesso. Imagine um balde com um furinho no fundo. Dá para despejar água tão rápido quanto você quiser, mas ela pinga pelo furo numa velocidade constante. Se você despeja demais, o balde transborda. Esse é o leaky bucket, e ele tem duas leituras que usam a mesma figura.

Leitura 1: uma fila (um modelador)

As requisições entram numa fila de espera de tamanho limitado. Elas saem da fila numa taxa constante, uma a cada intervalo fixo. Uma rajada não é recusada: ela espera na fila e sai de forma uniforme. Se a fila está cheia, a requisição que chega é descartada, como a água por cima da borda.

chegadas (9 de uma vez)
       |
       v
  +---------+
  | 6 vagas |  3 requisições não cabem: descartadas
  +----+----+
       | uma a cada 0,5 s
       v
  saída: 0,5  1,0  1,5  2,0  2,5  3,0 s

O sistema atrás do balde nunca recebe mais que a taxa de saída, por mais cheia de rajadas que seja a entrada. O preço é o atraso: se a fila escoa r requisições por segundo, a requisição com k - 1 na frente espera k / r segundos (a primeira saída acontece um intervalo depois da chegada a uma fila vazia). A pior espera possível é capacidade / r, então o tamanho da fila também é uma escolha de latência máxima.

Leitura 2: um medidor (um fiscalizador)

Como medidor (meter), o balde não guarda nenhuma requisição. Ele guarda só um número, o nível. Cada requisição admitida soma 1 ao nível, e o nível escoa numa taxa constante. Uma requisição é admitida quando nível + 1 <= capacidade, e a decisão é imediata: nada espera.

O medidor é a imagem no espelho do token bucket. Com fichas = capacidade - nível, as regras de um viram as regras do outro. Os dois admitem exatamente as mesmas requisições e os dois permitem uma rajada de até a capacidade com taxa média r. Só a leitura como fila se comporta de outro jeito, porque ela segura e atrasa requisições.

Modelar e fiscalizar

Nas palavras de Tanenbaum, modelar regula a taxa média e o tamanho da rajada de um fluxo antes de ele entrar na rede, em geral atrasando pacotes. Fiscalizar é a rede conferindo se o fluxo respeita o padrão combinado, e descartando ou marcando o excesso.

Token bucket ou leaky bucket?

Depois de muito tempo quieto, um cliente manda 10 requisições de uma vez. Um token bucket de capacidade 10 juntou fichas enquanto estava parado, então deixa as 10 passarem na hora. Um leaky bucket como fila não junta crédito nenhum: ele mantém as 10 na fila e as solta na sua taxa constante, digamos uma por segundo. O tempo parado rende fichas num e não rende nada no outro.

Limitação distribuída com Redis e atomicidade

Até aqui havia um programa com um contador. Serviços de verdade rodam em várias cópias, chamadas instâncias, atrás de um balanceador de carga. Se cada instância conta na sua própria memória, um cliente pode passar N vezes o limite por N instâncias: com 3 instâncias e limite de 100 por minuto, até 300 por minuto.

A solução é tirar o contador das instâncias e levá-lo para um armazenamento compartilhado que todas leem e escrevem. O Redis é a escolha usual. O Redis vira a única fonte da verdade, e as instâncias ficam simples e podem ser acrescentadas ou removidas sem mudar o limite.

Por que o INCR não perde contagens

O Redis executa comandos um de cada vez e nunca mistura dois comandos sobre os dados. Assim o INCR (soma um a um número) é uma leitura, soma e escrita atômicas. Se duas instâncias mandam INCR para a mesma chave no mesmo instante, nenhuma soma se perde. Atômico quer dizer 'tudo de uma peça, nada entra no meio'.

A armadilha: verificar e depois agir

contador = 9, limite = 10

instância A: GET   -> 9
instância B: GET   -> 9   (A ainda não escreveu)
instância A: 9 < 10, INCR, admite  -> 10
instância B: 9 < 10, INCR, admite  -> 11   <- acima do limite

Ler, decidir na aplicação e só então escrever é uma condição de corrida (race condition, um bug que depende de quem é mais rápido). No teste deste repositório, duas instâncias receberam 400 requisições concorrentes para um limite de 50 por minuto. A versão com um script Lua admitiu exatamente 50 em cada uma de cinco rodadas. A versão ingênua admitiu até 192 nas rodadas medidas, e exatamente 50 em algumas delas, e é por isso que esses bugs são difíceis de pegar.

A cura: um script Lua

O Redis consegue rodar um pequeno programa escrito em Lua com EVAL. Um script roda do início ao fim e nenhum outro comando é atendido no meio, então a leitura, a decisão e a escrita viram um único passo atômico. Ele também pode definir a expiração no mesmo passo do primeiro incremento, e assim um cliente que cai não deixa um contador que nunca expira.

Relógios e falhas

As janelas só concordam se todas as instâncias concordam com a hora. Os relógios de máquinas diferentes se afastam (clock skew). Se a instância B está 20 segundos adiantada, ela monta uma chave de janela diferente da instância A para o mesmo instante, e o contador compartilhado se divide em dois. A solução é ler a hora dentro do script com o comando TIME do Redis, para que todas as instâncias usem um só relógio.

Mais duas coisas podem dar errado. Primeiro, o Redis copia os dados para uma réplica de forma assíncrona: o primário confirma ao cliente e envia para a réplica depois. Se o primário cai e a réplica assume, os últimos incrementos podem ser perdidos e o limite é excedido por um instante. Esse desvio pequeno e raro costuma ser aceito. Segundo, o Redis pode ficar inalcançável, e o limitador precisa decidir de antemão o que fazer:

Um meio-termo comum é um limite local aproximado na memória de cada instância enquanto o Redis está ausente.

HTTP 429, cabeçalhos e backoff do cliente

Quando um limitador diz não, ele precisa dizer de um jeito que o cliente entenda. Na web isso se faz com um código de status HTTP, um número no começo da resposta (200 é OK, 404 é não encontrado). Para 'você mandou demais', o código é 429 Too Many Requests, acrescentado pela RFC 6585. A RFC não diz como o servidor descobre quem você é nem como conta. A resposta deve explicar a situação e pode dizer quando tentar de novo.

429 ou 503?

Um limitador por cliente responde 429. Um servidor que descarta carga porque está sobrecarregado responde 503. Uma resposta 429 nunca deve ser guardada por um cache, porque ela descreve um cliente em um instante: se um cache compartilhado (como uma CDN) a guardasse, outros clientes, ou o mesmo cliente depois de esperar, seriam recusados sem motivo. A RFC 6585 diz que respostas 429 não devem ser armazenadas.

Dizendo ao cliente quando voltar

HTTP/1.1 429 Too Many Requests
Retry-After: 30
Content-Type: application/json

{"error":"rate limit exceeded"}

O cabeçalho Retry-After diz ao cliente quanto esperar. A RFC 9110 permite duas formas: um número inteiro de segundos contados a partir do recebimento da resposta, ou uma HTTP-date absoluta. A forma em segundos não depende de os relógios do cliente e do servidor concordarem. O limitador deste repositório manda segundos inteiros, arredondados para cima.

Muitas APIs também mandam cabeçalhos sobre o próprio limite, como X-RateLimit-Limit, X-RateLimit-Remaining e X-RateLimit-Reset. Eles se espalharam por imitação e não têm padrão. O pior caso é o Reset: alguns serviços querem dizer 'segundos a partir de agora' e outros um timestamp Unix como 1791374400. Um cliente que lê um timestamp como segundos dormiria por décadas. O IETF trabalha num Internet-Draft (ainda não era uma RFC quando isto foi escrito) com os campos RateLimit-Policy e RateLimit. Um cliente genérico deve preferir o Retry-After, que é padrão, e ler a documentação antes de confiar nos campos X-.

O que um cliente educado faz

Um 429 pede que o cliente desacelere, não que insista nem que desista para sempre. Se há Retry-After, espere pelo menos esse tempo. Ele vem de quem controla o limite, então vale mais que o palpite do próprio cliente. Se não há Retry-After, use backoff exponencial: a espera dobra a cada falha. Com a convenção de que a primeira nova tentativa é n = 1:

espera(n) = min(teto, base * 2^(n-1))
base = 0,5 s, teto = 10 s

A 6ª nova tentativa seria 0,5 x 32 = 16 s, mas o teto a corta em 10 s. Diga sempre se você conta as tentativas a partir de 0 ou de 1, porque os números mudam. Defina também um número máximo de tentativas, para que um cliente nunca fique preso tentando para sempre.

Jitter: um pouco de aleatoriedade

Imagine 200 clientes recusados no mesmo instante, todos usando as mesmas esperas que dobram. Eles tentam de novo juntos em 1 s, 3 s, 7 s, em ondas, e o servidor é atingido de novo e de novo (uma manada trovejante, thundering herd). O jitter deixa cada espera aleatória. No full jitter a espera é sorteada entre 0 e min(teto, base x 2^tentativa). As tentativas se espalham e o servidor consegue atender uma parte delas a cada momento.

sem jitter:  |200|    |200|        |200|
             1s      3s           7s      (ondas)

com jitter:  |12|31|18|25|9|41|22|...      (espalhadas)

Tentar de novo pode machucar

Tentativas imediatas multiplicam a carga no pior momento. Se um serviço recebe 100 requisições por segundo e cada cliente repete uma requisição recusada até 3 vezes de uma vez, o serviço vê até 400 por segundo enquanto já está falhando. Isso é uma tempestade de retries (retry storm). Backoff, jitter, um limite de tentativas e respeito ao Retry-After quebram o ciclo.

Há mais uma regra de segurança. Tentar de novo só é seguro quando executar uma requisição duas vezes tem o mesmo efeito que executá-la uma vez, o que se chama ser idempotente. Um 429 diz que nada foi processado, mas depois de um timeout o cliente não sabe. Para algo como POST /charges, que cria uma cobrança, o cliente manda uma chave de idempotência, um código único que deixa o servidor reconhecer a repetição e não cobrar duas vezes.

Cotas, throttling e descarte de carga

O rate limiting tem vizinhos que protegem um sistema de outros jeitos. Saber qual faz o quê é metade do trabalho.

Três limites diferentes

Uma API costuma ter os três, e uma requisição precisa passar por cada um. Eles são verificados separadamente. Um cliente que obedece o limite de taxa o tempo todo ainda pode gastar a cota mensal cedo: com uma cota de 500.000 por dia e 10 requisições por segundo constantes, a cota acaba depois de 50.000 segundos, cerca de 13,9 horas. Por isso as APIs dizem aos clientes quanto da cota resta.

Por que o limite de concorrência é especial

O número médio de requisições em andamento é igual à taxa de chegada vezes o tempo que cada uma passa no sistema. Essa é a lei de Little. Se chegam 120 requisições por segundo e cada uma leva 0,5 s, cerca de 60 estão em andamento ao mesmo tempo. Se o serviço fica duas vezes mais lento, são 120 em andamento com a mesma taxa de chegada, e um limite de taxa não percebe nada.

Um limite de concorrência C com tempo de serviço S deixa passar no máximo C / S requisições por segundo. Com C = 30 e S = 0,25 s são 120 por segundo. Se o serviço fica lento e S cresce, a vazão admitida cai na mesma proporção, o que protege um servidor que já está sofrendo. Um limite de taxa fixo continuaria admitindo a mesma taxa e as requisições se acumulariam.

Controle de congestionamento, do lento ao rápido

Tanenbaum ordena as respostas ao congestionamento da mais lenta para a mais rápida: aumentar a capacidade, escolher rotas que evitam os pontos cheios, controle de admissão, estrangulamento de tráfego (traffic throttling) e descarte de carga (load shedding). O controle de admissão recusa trabalho novo antes de ele começar, o que é mais barato que aceitá-lo e jogá-lo fora no meio do caminho. A palavra throttling é usada de forma solta na documentação de APIs tanto para atrasar (modelar) quanto para recusar (fiscalizar).

Contrapressão (backpressure)

Imagine um produtor escrevendo numa fila de 1.000 vagas que um consumidor mais lento esvazia. Quando a fila enche, a chamada de escrita do produtor simplesmente espera até haver espaço, e nada é jogado fora. Isso é backpressure: a parte cheia diz ao remetente para desacelerar, com um sinal ou com uma chamada que bloqueia. O atraso viaja de volta até a origem. Quando a origem não pode esperar, como os usuários da Internet, o backpressure termina como uma rejeição na entrada, que é rate limiting ou descarte de carga.

Descarte de carga

O descarte de carga é a última defesa: o servidor recusa trabalho de propósito, normalmente com 503, para que o trabalho que aceitou termine a tempo. Ele difere do rate limiting porque olha a saúde do servidor, não o comportamento de um cliente. Um bom descarte é feito cedo e por prioridade, com o trabalho menos importante primeiro.

requisição --> [rejeita aqui: 1 ms] --> parse --> auth --> banco
                                              [rejeita aqui: 40 ms]

Um servidor que rejeita tarde pode gastar toda a sua capacidade dizendo não e continuar sobrecarregado. Por isso descarte antes de ler o corpo, antes de autenticar, antes de tocar numa dependência.

Quando a sobrecarga não é tratada

Suponha um servidor que atende 100 requisições por segundo mas recebe 150, com uma fila primeiro-a-chegar-primeiro-a-sair sem limite, e clientes que desistem depois de 2 segundos. A fila cresce, toda resposta chega atrasada, e o servidor segue atendendo requisições cujos clientes já foram embora. A vazão dele está no máximo, mas o goodput (respostas que chegam a tempo) cai para quase zero. A cura: uma fila limitada, um prazo para cada requisição (descartar o que já passou do timeout) e recusar o excesso na entrada.

Quem descartar? O vizinho barulhento

Tanenbaum descreve duas políticas para escolher quais pacotes descartar. A política do vinho (wine) prefere manter os pacotes velhos, porque vinho velho é melhor. Serve para transferência de arquivos, onde perder um pacote velho obriga a reenviar tudo o que vem depois. A política do leite (milk) prefere manter os novos, porque leite velho estraga. Serve para mídia em tempo real, onde dado atrasado é inútil. Servidores têm a mesma ideia: para descartar por prioridade você precisa saber quanto vale cada requisição.

Num serviço compartilhado, um tenant grande pode prejudicar todos os pequenos, o vizinho barulhento (noisy neighbour). Com descarte aleatório todos perdem na mesma proporção, então 30 tenants pequenos perdem metade das requisições por causa de um grande. O descarte justo atende os tenants pequenos por inteiro e tira o excesso de quem passou da sua parte. Isso exige contar por tenant, e é por isso que cotas e limites por plano andam junto com o descarte de carga.

Circuit breaker

Um circuit breaker (disjuntor) é o outro lado da mesma ideia. O serviço A chama o serviço B. Depois de 5 chamadas seguidas falharem, A para de chamar B por 30 segundos e responde com um valor alternativo (fallback), e depois deixa passar uma chamada de teste. Ele fica do lado de quem chama e observa resultados, para proteger de uma dependência doente. Um limitador de taxa fica do lado de quem é chamado e observa volume, para proteger de um cliente que pede demais.

Juntando tudo

No experimento de rajada deste repositório, os cinco algoritmos receberam as mesmas 80 requisições com as mesmas configurações (limite 10, janela de 1 s, então capacidade 10 e taxa de 10 por segundo para os baldes). O gráfico mostra o maior número de requisições admitidas encontrado em qualquer intervalo de 1 segundo.

A janela fixa deixou passar 20 perto de uma fronteira. O log deslizante nunca passou de 10. O contador deslizante chegou a 11, um erro pequeno. O token bucket chegou a 19 porque gasta primeiro as fichas guardadas e depois ganha mais enquanto a rajada continua. A saída do leaky bucket ficou em 10 porque ele solta as requisições num ritmo constante.

Erros comuns

• Achar que um limitador é autenticação, criptografia, cache ou balanceador de carga. Ele só conta.
• Contar por endereço IP atrás de NAT, ou por X-Forwarded-For sem proxy confiável.
• Usar um limite só para todos os endpoints, ou só limites por cliente e nenhuma proteção global.
• Esquecer o teto no token bucket, de modo que um cliente parado junta fichas sem fim.
• Fazer ler, decidir e escrever como comandos separados no Redis (uma corrida), ou INCR e EXPIRE como dois comandos (uma chave que nunca expira).
• Ler a hora em cada instância em vez de no Redis, e as janelas discordarem.
• Tentar de novo na hora, sem jitter, sem limite de tentativas e sem respeitar o Retry-After.
• Rejeitar tarde, depois de a requisição já ter usado as partes caras do servidor.

Como as ideias se conectam

O algoritmo decide quem é admitido. O Redis e um script atômico fazem essa decisão valer entre muitos servidores. O status 429 com Retry-After conta ao cliente o que aconteceu. O backoff do cliente com jitter evita que as suas novas tentativas virem um novo problema. Cotas, limites de concorrência e descarte de carga protegem o longo prazo e o serviço inteiro quando os limites por cliente não bastam.