Algoritmos de janela deslizante

O estouro na fronteira da janela fixa vem de dividir o tempo em blocos. Uma requisição cai em um bloco ou em outro, e um intervalo de tempo que atravessa a divisa pode carregar o dobro do limite.

Pare de usar blocos e o problema desaparece. Os dois algoritmos aqui medem contra uma janela que termina na requisição que está sendo decidida, e eles se diferenciam apenas na quantidade de coisas que precisam lembrar.

Log de janela deslizante

Guarde um timestamp para cada requisição aceita. Quando uma nova chega, olhe para trás o comprimento de uma janela, conte o que há ali dentro e decida.

A janela é calculada do zero a cada vez, então ela desliza logo atrás de cada requisição. Mesmo estacionamento, janela de trinta segundos, limite de cinco:

Tempo	Chegam	Janela olha até	Contagem na janela	Resultado
0s	1	0s	0	Aceita
5s	2	0s	1	Ambas aceitas, contagem agora 3
15s	2	0s	3	Ambas aceitas, contagem agora 5
25s	1	0s	5	Rejeitada, no limite
35s	1	5s	4	Aceita, a requisição de 0s já saiu da janela
40s	3	10s	3	Duas aceitas, a terceira rejeitada

Aos 35 segundos a janela começa em 5, então a requisição de 0 fica fora dela e deixa de contar. Esse envelhecimento gradual é todo o mecanismo: a capacidade volta aos poucos, à medida que requisições antigas saem, em vez de tudo de uma vez em um reset.

Nenhum intervalo de trinta segundos jamais contém mais de cinco requisições. Essa é a garantia que uma janela fixa não consegue dar.

JunoLog de janela deslizante A diferença em relação a uma janela fixa está em onde fica a borda da janela. A borda de uma janela fixa fica presa ao relógio, no mesmo lugar para todo mundo.

Aqui a borda fica logo atrás da requisição que está sendo decidida, então ela se move a cada vez. Ninguém ganha um reset, e ninguém precisa esperar por um também.

JunoLog de janela deslizante Isso também resolve a seca. Um cliente que gasta todo o orçamento de uma vez recupera capacidade uma requisição de cada vez, conforme cada uma envelhece, em vez de esperar um bloco terminar.

Isso fica muito mais próximo do que as pessoas esperam que um rate limit pareça, e é por isso que vale a pena pagar pela precisão em endpoints onde recusar um cliente legítimo sai caro.

JunoLog de janela deslizante O que você paga é memória proporcional ao limite, por cliente. Um limite de 5 guarda cinco timestamps; um limite de 10.000 guarda dez mil, para cada cliente, e as entradas antigas precisam ser podadas ou a lista cresce sem parar.

No Redis isso costuma ser um sorted set por cliente indexado por timestamp, com o intervalo expirado cortado a cada requisição.

São várias operações onde uma janela fixa é um único incremento atômico, e ainda assim precisa ser atômico, ou requisições concorrentes acabam cada uma lendo uma contagem já desatualizada.

Em limites pequenos, é barato e claramente correto. Em limites grandes, é o algoritmo que faz do seu rate limiter a parte cara da requisição.

Contador de janela deslizante

O custo do log é a lista de timestamps. O contador consegue a maior parte da precisão usando apenas dois inteiros.

Volte às janelas fixas, mantenha uma contagem para a atual e para a anterior, e depois pondere a contagem anterior pela fração dela que ainda cai dentro de um olhar retrospectivo deslizante:

x        = quanto já avançamos na janela atual, como uma fração
weighted = (1 - x) * previousCount + currentCount

aceitar se weighted + 1 <= limit

Com uma janela de trinta segundos, um limite de 5, e uma janela anterior que se encheu completamente:

Tempo	Dentro da janela	1 - x	Ponderado	Mais esta requisição	Resultado
35s	5s, ou seja 1/6	5/6	5/6 × 5 + 0 = 4,17	5,17	Rejeitada, acima de 5
40s	10s, ou seja 1/3	2/3	2/3 × 5 + 0 = 3,33	4,33	Aceita
40s de novo	10s, ou seja 1/3	2/3	2/3 × 5 + 1 = 4,33	5,33	Rejeitada

O termo (1 - x) * previousCount é a estimativa: à medida que a janela atual se enche, menos da janela anterior permanece à vista, então a contribuição dela se esvai suavemente.

Dois contadores por cliente, e nenhum timestamp.

JunoContador de janela deslizante A fórmula está fazendo algo simples. No início de uma janela, a maior parte da janela anterior ainda conta contra você. Mais tarde, uma parte menor conta.

Em vez de checar quais requisições específicas ainda estão dentro do intervalo, ela assume que estavam distribuídas uniformemente e pega uma fração. Mais barato, e quase certo.

JunoContador de janela deslizante Repare na terceira linha. Duas requisições no mesmo instante recebem respostas diferentes, porque a primeira aceita incrementa currentCount e a segunda é medida contra o novo total.

O que está correto, e vale saber quando você estiver testando: disparar requisições em um loop apertado gera resultados que dependem de quantas já foram aceitas naquele milissegundo.

JunoContador de janela deslizante A aproximação é boa o suficiente para rodar em escala de internet. A Cloudflare publicou dados de 400 milhões de requisições vindas de 270.000 fontes: 0,003% foram permitidas ou limitadas de forma diferente de uma contagem exata, sem nenhum falso positivo.

Três fontes ligeiramente acima do limite foram deixadas passar, e a diferença média entre a taxa real e a aproximação foi de 6%.

Por esse erro você ganha dois inteiros por cliente em vez de uma lista, e é essa a troca que faz dele a escolha comum em produção.

Medindo contra os 200 de uma janela fixa numa fronteira, o log permite exatamente 100 e o contador 101. Essa uma requisição extra do contador é a aproximação aparecendo, e não é o que vai te prejudicar.

Onde eles discordam

O contador assume que as requisições da janela anterior estavam distribuídas uniformemente. Raramente é esse o caso, e qual algoritmo é mais permissivo depende de onde elas realmente se concentraram.

Requisições perto do início da janela anterior. O log olha para trás trinta segundos de verdade, vê que essas requisições iniciais ficam fora desse intervalo, e permite mais. O contador ainda cobra uma fração delas, então recusa.

O log é mais permissivo aqui, porque o contador está tratando a capacidade como mais restrita do que ela realmente é.

Requisições perto do fim da janela anterior. Agora o log ainda as tem à vista e recusa, enquanto o contador já esvaiu a maior parte da contagem anterior. Aqui o contador é mais permissivo, porque está subestimando o quão recente foi aquele tráfego.

Então o erro vai para os dois lados, e é isso que o torna aceitável. Não é um viés sistemático a favor dos clientes nem do servidor.

JunoOnde eles discordam O contador não está acompanhando quando cada coisa aconteceu. Ele só sabe quantas, e chuta o quando.

Às vezes esse chute é generoso e às vezes é rígido, e isso depende inteiramente de quando as requisições realmente chegaram.

JunoOnde eles discordam Vale conhecer a direção do erro na hora de escolher. Em um endpoint onde deixar passar um pouco demais é perigoso, a permissividade do contador contra tráfego concentrado no fim é o caso a se pensar.

Em um onde recusar um cliente legítimo sai caro, a rigidez dele contra tráfego concentrado no início é a que vai gerar chamados de suporte.

JunoOnde eles discordam Os dois são explorável em princípio moldando o tráfego para se ajustar à janela, e o contador ainda mais, já que seu ponto cego é previsível: agrupe requisições no fim de uma janela e a estimativa da próxima janela vai subestimá-las.

Na prática, isso exige que o atacante conheça o comprimento da sua janela e o alinhamento da fronteira, o que é dedutível mas trabalhoso, e o ganho é um punhado de requisições extras. Não vale a pena se defender diretamente disso.

Vale a pena se defender não dependendo de um único limitador. Um limite por segundo junto com um por minuto fecha a maioria dos jogos de manipulação de janela, porque um burst montado contra uma janela ainda é um burst contra a outra.

Experimente

Uma janela de trinta segundos, um limite de 5, e uma janela anterior que aceitou 5 requisições. Nenhuma requisição ainda na janela atual.

1. Usando o contador, uma requisição aos 33 segundos é aceita?
2. Em que ponto da janela atual a primeira requisição passa a ser aceitável?
3. Mesmo tráfego, mas as 5 requisições da janela anterior chegaram todas no primeiro segundo dela. Qual algoritmo permite a requisição aos 33 segundos, e por quê?

Compare suas respostas

1. Rejeitada. Aos 33 segundos você está 3 segundos dentro de uma janela de 30 segundos, então x é 1/10. A contagem ponderada é 0,9 × 5 + 0 = 4,5, e somando esta requisição dá 5,5, acima do limite de 5.

2. Aos 36 segundos. Você precisa que (1 - x) × 5 + 1 <= 5, então (1 - x) × 5 <= 4, então 1 - x <= 0,8 e x >= 0,2. Um quinto de uma janela de trinta segundos são 6 segundos, colocando a primeira requisição aceitável aos 36 segundos.

3. O log permite; o contador ainda recusa. O log olha para trás até os 3 segundos. As cinco requisições anteriores chegaram todas antes disso, então já saíram da janela e a contagem é 0.

O contador não tem ideia de quando elas chegaram, assume uma distribuição uniforme, e ainda cobra 4,5 contra elas. Esse é o custo concreto da aproximação: o cliente não enviou nada nos últimos trinta segundos e mesmo assim é recusado.

Para onde isso vai a seguir

Os dois algoritmos aplicam uma média, e os dois tratam um burst como algo a ser evitado. Só que boa parte do tráfego é legitimamente em bursts: uma página carregando seis recursos de uma vez não é abuso.

Token bucket adota a visão oposta, permitindo um burst de propósito e depois fazendo o cliente esperar para ganhar outro.