Por que o Rate Limit (limitação de uso) é necessário?
- Em um chat da Twitch com muitos participantes, se houver um spammer e não existir limitação de uso, ele pode dominar a conversa.
- Com a limitação de uso, cada usuário pode ter uma chance justa de participar.
- Um Rate Limiter (limitador de uso) controla o tráfego de um serviço bloqueando requisições que excedem um limite definido durante um determinado período. Isso é útil não só para controlar spam em chats.
- Por exemplo, em um formulário de login, a limitação de uso pode conter ataques de força bruta, ao mesmo tempo em que permite uma pequena quantidade de tentativas incorretas.
- Endpoints de API também costumam ter limitação de uso para evitar que um único usuário monopolize os recursos.
- Se um usuário só puder chamar um endpoint de API caro 100 vezes por minuto, um contador pode ser usado para rastrear 100 acessos por minuto, e as requisições seguintes são bloqueadas.
- Esse é um dos algoritmos de limitação de uso mais simples: o Fixed Window Limiter.
- É uma forma comum de controlar o tráfego de um serviço.
Algoritmo de Fixed Windows
- O número de requisições é limitado dentro de uma janela de tempo fixa.
- No início de cada janela de tempo, o contador de requisições é redefinido para 0.
- Vantagens
- É fácil de implementar e entender.
- É previsível para o usuário.
- Desvantagens
- Se as requisições começarem perto do fim da janela, pode ser permitido um burst de até 2 vezes o limite.
- Exemplo real: a API do GitHub usa um limitador de taxa com janela de tempo fixa que permite 5.000 requisições por hora.
- Em vez de definir o início da janela em intervalos fixos, cada janela de tempo pode ser criada no momento da primeira requisição do usuário dentro daquela janela.
- Nessa abordagem, é especialmente importante informar ao usuário quanto tempo falta até a próxima janela.
Algoritmo de Sliding Windows
- Em vez de renovar toda a capacidade de uma vez, a sliding window repõe a capacidade uma requisição por vez.
- Vantagens
- Suaviza a distribuição do tráfego de requisições.
- É adequada para alta carga.
- Desvantagens
- É menos previsível para o usuário do que a janela de tempo fixa.
- Armazenar o timestamp de cada requisição consome muitos recursos.
- Como a sliding window é mais útil em cenários de alto tráfego, o fato de o algoritmo básico consumir muitos recursos acaba sendo contraproducente.
- Por isso, a maioria dos limitadores de taxa com sliding window usados na prática utiliza uma aproximação.
- A aproximação calcula o número de requisições permitidas na janela fixa anterior e na janela fixa atual, e aplica um peso às requisições permitidas na janela anterior proporcionalmente à sobreposição com a janela de tempo flutuante que termina no momento atual.
- Essa aproximação limita as requisições quase na mesma proporção, mas é muito mais eficiente.
- Exemplo real: o rate limiter configurável da Cloudflare usa uma sliding window aproximada.
Algoritmo de Token Buckets
- Em vez da duração de uma janela de tempo, imagine um balde preenchido com "tokens" em uma taxa constante.
- Cada requisição retira um token desse balde, e quando o balde fica vazio, a próxima requisição é bloqueada.
- A capacidade do balde representa o número máximo de requisições que um burst pode suportar.
- O intervalo de reposição representa o intervalo médio permitido entre requisições no longo prazo.
- Uma das principais vantagens desse algoritmo é permitir capacidades separadas de burst e média sem precisar de vários limitadores de taxa.
- Vantagens
- Permite bursts de tráfego alto, ao mesmo tempo em que aplica uma taxa média de requisições no longo prazo.
- É mais flexível para o usuário, pois permite picos de tráfego dentro de limites aceitáveis.
- Desvantagens
- É mais difícil do que a janela de tempo fixa comunicar ao usuário quais são os limites e quando ocorrerá a reposição.
- Exemplos reais
- A Stripe usa um token bucket com limite de 500 e intervalo de reposição de 0,01 segundo, permitindo sustentar 100 requisições por segundo, mas com bursts de até 500 requisições.
- O tier gratuito do GPT-3.5 da OpenAI usa um token bucket com limite de 200 e intervalo de reposição de 86400 segundos/200, limitando o uso a 200 requisições por dia.
Pontos a considerar ao aplicar rate limiting
- É necessário criar um armazenamento persistente para o rate limiter.
- Se a conexão do servidor com o armazenamento persistente falhar, todas as requisições devem ser permitidas em vez de bloqueadas.
- Opcionalmente, é possível controlar tráfego em burst.
- É preciso escolher a chave adequada (ID do usuário, chave de API etc.).
- Devem ser exibidos erros úteis de limitação de taxa (tempo de espera até a próxima requisição, código de status HTTP 429, headers de resposta
x-ratelimit-* etc.)
2 comentários
Li o texto resumido em coreano e pensei: "Ok, entendi do que se trata, mas não é tudo a mesma coisa?" Aí fui ler o texto original no link e ele realmente explica muito bem, e a visualização também é extremamente satisfatória! 👍👍👍
Opiniões no Hacker News
Resumo da coletânea de comentários do Hacker News
Considerações adicionais obtidas com muitos anos de experiência:
Em ambientes multitenant, fair queuing é a melhor abordagem para evitar ataques DoS: atribui-se a cada cliente sua própria fila, e uma rotina em segundo plano percorre repetidamente cada fila para processar as requisições. Um cliente que envia requisições de spam só congestiona a própria fila.
Experiência implementando código do lado do cliente: sempre houve curiosidade sobre qual seria a melhor estratégia de backoff ao atingir o rate limit. Foi interessante ler sobre os trade-offs do ponto de vista do serviço.
Mensagem de parabéns: é a melhor visualização para conteúdo curto, muito informativa e com os pontos muito bem organizados.
Algoritmo GCRA: parece ser um algoritmo melhor para rate limiting. Seria bom se fosse mais conhecido e mais usado.
Ótimo trabalho: dá para perceber que muito tempo e esforço foram investidos nesta publicação. Muito bem.
Problema de rate limiting no AWS Lambda: tentaram implementar rate limiting em NodeJS, mas no AWS Lambda os timers se comportavam de forma estranha e ultrapassavam a meta. Nos testes locais passava, mas no Lambda falhava. Não está claro se o problema é dos timers ou da biblioteca.
O que fazer quando a camada de rate limiting fica saturada: ficou a dúvida se existem outras opções além de CF. Também há curiosidade sobre o quão eficazes regras de nftable seriam para defender um pequeno VPS contra ataques DoS.
Momentos em que este recurso teria sido necessário: é um recurso que teria sido útil várias vezes ao longo da carreira. É bom que agora ele exista.
Fã de visualização de dados: ficou a curiosidade se está usando D3.