O que é um limitador de taxa?
A limitação de taxa refere-se a impedir que a frequência de uma operação exceda um limite definido. Em sistemas de grande graduação, a limitação de taxa é comumente usada para proteger serviços e recursos subjacentes. Em sistemas distribuídos, a limitação de taxa é usada porquê um mecanismo defensivo para proteger a disponibilidade de recursos compartilhados. Ele também é usado para proteger APIs contra uso excessivo não premeditado ou mal-intencionado, limitando o número de solicitações que podem chegar à nossa API em um determinado período de tempo.
Neste blog, veremos porquê abordar a questão de projetar um limitador de taxa em uma entrevista de design de sistema.
Exemplos de limitador de taxa
O Amazon EC2 limita as solicitações de API do EC2 para cada conta da AWS por região.
Ele usa o algoritmo token bucket para implementar a otimização da API.
- API Stripe (https://stripe.com/docs/rate-limits)
Para a maioria das APIs, o Stripe permite até 100 operações de leitura por segundo e 100 operações de gravação por segundo no modo ao vivo e 25 operações por segundo para cada uma no modo de teste.
- API do Twitter (https://developer.twitter.com/en/docs/twitter-api/rate-limits)
O Twitter tem vários limites de taxa para gerenciar tweets e pesquisar tweets
Por que o limitador de taxa é necessário?
A limitação de taxa é uma secção muito importante de qualquer sistema e APIs de grande graduação e pode ser usada para realizar o seguinte:
- Evitando a escassez de recursos
Isso pode suceder quando um grande número de solicitações chega em um período muito limitado de tempo ou devido a ataques de negação de serviço (DoS).
- Gerenciamento de políticas e cotas
Para permitir o aproximação exclusivamente a usuários autenticados para permitir o uso a eles com base em sua quota
Em sistemas complexos, pode ser usado para controlar o fluxo entre serviços vinculados para impedir que um serviço acumule todos os recursos
Se os recursos puderem escalar maquinalmente, a limitação de taxa será usada para controlar o excesso de dispêndio se um pouco transpor do controle
Algoritmos usados no limitador de taxa
- Balde Furado
O Leaky Bucket é uma maneira simples e intuitiva de implementar a limitação de taxa usando uma fileira. É uma fileira simples de primeiro a entrar, primeiro a transpor (FIFO). As solicitações recebidas são anexadas à fileira e, se não houver espaço para novas solicitações, elas são descartadas (vazadas).
Ele mantém um fluxo permanente quase uniforme para o servidor enquanto processa as solicitações a uma taxa permanente. É fácil de implementar em um balanceador de fardo e é eficiente em termos de memória para cada usuário.
- Token Bucket
No algoritmo Token Bucket, processamos um token do balde para cada solicitação. Novos tokens são adicionados ao balde com taxa r. O balde pode sofrear no sumo b tokens. Se chegar uma solicitação e o balde estiver pleno, ela será descartada.
- Janela Fixa
Mantemos um contador por um determinado período de tempo e o incrementamos a cada solicitação recebida. Uma vez atingido o limite, as próximas solicitações são descartadas até que o contador seja zerado em seguida o tempo.
- Registro Deslizante
O algoritmo Log deslizante mantém um registro com registro de data e hora para cada solicitação no nível do usuário. O sistema armazena esses logs em um conjunto ou tábua de hash classificados por tempo. Logs com timestamps além de um limite são descartados. Procuramos solicitações mais antigas e as descartamos. Em seguida, calculamos a soma dos logs para mandar a taxa de solicitação. Se a solicitação estiver aquém da taxa limite, ela será processada, caso contrário, será retida.
- Janela Deslizante
É mais eficiente em termos de memória do que o algoritmo de registro deslizante. Ele combina o grave dispêndio de processamento do algoritmo de janela fixa e as condições de perímetro aprimoradas do log deslizante. Mantemos uma janela deslizante de nossa duração de tempo e exclusivamente solicitações de serviço em nossa janela para a taxa fornecida. Se a soma dos contadores for maior que a taxa dada do limitador, portanto tomamos exclusivamente a primeira soma de entradas igual ao limite de taxa.
Uma vez que você projetará um limitador de taxa para sua API?
Suponha que lhe façam uma pergunta para projetar um limitador de taxa. Você deve primeiro saber os requisitos fazendo várias perguntas ao entrevistador.
Candidato: Que tipo de limitador de taxa vamos projetar? Será do lado do cliente ou do lado do servidor?
Entrevistador: Estaremos projetando um limitador de taxa do lado do servidor para nossa API.
Candidato: Vamos limitar a API com base em solicitações por segundo, IP ou qualquer outra coisa?
Entrevistador: Limitaremos a API com base em solicitações por segundo.
Candidato: Suponha que levante seja um trabalho assíncrono. Assim, temos algumas opções:
Opção 1: Limite no nível da API
Opção 2: Aligeirar em seguida Fileira de Solicitação
Cá estão algoritmos populares para limitação de taxa
- Balde Furado
- Token Bucket
- Contador de janela fixa
- Registro da janela deslizante
- Contador de janela deslizante
Você pode descrever os prós e contras desses algoritmos porquê supra.
