Desafios de system design: aprenda a implementar solução para um sistema inteiro

Rate Limiter - Apresentação

Apresentando o curso e objetivos

Seja muito bem-vinde a este curso na Alura. Meu nome é Vinícius Neves.

Neste curso, nós percorremos uma jornada de 8 casos de System Design (projeto de sistemas). São exercícios de Whiteboard (quadro branco): em cada exercício, apresentamos um problema e nós o solucionamos.

Há um ponto importante: o foco deste curso não é ensinar tecnologias em si. Não vamos falar de frameworks (estruturas de desenvolvimento) nem de conteúdos semelhantes. Vamos nos concentrar em como resolver problemas. Por isso, é muito importante verificar os pré-requisitos para maximizar seu aproveitamento neste curso.

Apresentando a ementa do curso

O que teremos nele? São 8 casos, um por aula. A seguir, apresentamos um “spoiler” positivo do conteúdo:

• Na Aula 1, vamos tratar de Rate Limiter (limitador de taxa), isto é, como protegemos nossas APIs (interfaces de programação de aplicações).
• Na Aula 2, vamos abordar um gerador de ID: como criar um mecanismo para gerar IDs de forma única.
• Depois, vamos projetar uma estrutura Key-Value (chave-valor) distribuída. Vamos analisar como planejar essa solução, quais topologias adotar e demais decisões.

Na sequência, vamos tratar de Web Crawler (rastreador da web): precisaremos de uma estratégia para monitorar os preços da concorrência.

Em seguida, vamos pensar em como realizar isso e avançar para um caso clássico de autocomplete (autocompletar): como executar uma busca com bom desempenho a cada vez que uma pessoa usuária digitar uma letra.

Falaremos também de tempo real: vamos sair do modelo tradicional da web, no qual o cliente pergunta e o servidor responde, para um mecanismo diferente, em que o servidor envia dados para o cliente sem solicitação, pois há uma conexão ativa entre ambos.

Concluindo a ementa e próximos passos

Depois, na Aula 7, vamos falar de streaming (transmissão contínua) de vídeo: como pensar o trabalho com arquivos de vídeo, lidar com arquivos maiores e entregá-los ao final com foco em custo.

Na Aula 8, vamos implementar a sincronização de arquivos. O ápice será utilizar pequenos blocos que nós aprendemos nas aulas anteriores.

É isso que vem por aí. Eu espero que você esteja com a mesma empolgação que eu. Eu prometo que o careca barbudo não vai sair daqui. Eu estou te esperando na sequência, no próximo vídeo desta aula. Até mais!

Rate Limiter - Protegendo a API do marketplace

Iniciando o exercício e preparando o ambiente

Vamos iniciar o nosso primeiro exercício.

Estamos no app.diagrams.net. Vamos disponibilizar esse link na seção "Preparando o ambiente" e também o link para download do arquivo base, que contém o estado inicial de cada um dos exercícios de arquitetura que vamos realizar.

Vamos abrir o arquivo com a opção Open from device e visualizar as abas iniciais.

Cada uma dessas abas corresponde a uma aula diferente. Temos um exercício por aula, e o primeiro que vamos abordar é o de Rate Limiter (limitador de taxa).

Vamos configurar a interface: do lado esquerdo, podemos escolher o que exibir; do lado direito, vamos ocultar o painel de formatação para termos mais espaço livre na tela.

Agora, podemos entrar no problema em si. Qual é o estado da arte hoje? Temos uma API (Interface de Programação de Aplicações) pública de um Marketplace (mercado online). Há pessoas fazendo requisições em excesso nessa API, o que está prejudicando outros clientes.

Precisamos desenhar um Rate Limiter para protegê-la.

Coletando requisitos por entrevista

Antes de iniciar o desenho e transformar este diagrama em outras caixas, vamos parar, pensar e responder perguntas que vão nos ajudar a definir a solução. Vamos adicionar um bloco de texto chamado “Notas”, que serão as nossas notas da entrevista, e começar a elencar pontos de atenção. Neste cenário, normalmente conversamos com uma ou mais pessoas que trarão essas respostas. Aqui, apresentaremos as perguntas e as respostas.

Notas da entrevista

• O limite é global ou por cliente que consome a API?
  O limite será por chave de API.

• Se é por chave, quantas chaves ativas existem?
  Existem por volta de 50 mil chaves.

• Qual é o limite solicitado?
  100 requisições por minuto por chave. Cada chave pode fazer 100 requisições por minuto sem ser bloqueada, sem ativar o limitador.

• Permitiremos que o cliente faça burst (rajada) ou não?
  Se temos 100 requisições para fazer em um minuto, é possível concentrá-las, por exemplo, nas primeiras dezenas de segundos, ou limitar para que esse número fique distribuído ao longo do minuto. Há clientes com padrões diferentes: um aplicativo móvel, por exemplo, pode fazer 20 requisições de uma vez para montar a tela, então precisa de burst. Vamos marcar o termo como burst (rajada), pois é comum usarmos o termo em inglês.

• O que acontece quando o limite estoura?
  Quando estourarmos o limite, queremos devolver um erro. Nesta anotação, vamos escrever sem itálico.

• A motivação inclui conter ataque DDoS (negação de serviço distribuída)?
  Não. DDoS está fora do nosso escopo; é tratado em outra camada.

Consolidando descobertas e iniciando estimativas

Observação: ainda não iniciamos a modelagem detalhada das caixas no diagrama, mas já descobrimos informações importantes para a solução. Sabemos que:

• O limite é por chave de API.
• Existem cerca de 50 mil chaves, então podemos começar a estimar o tamanho do estado (contadores).
• O limite é de 100 requisições por minuto por chave.
• Há clientes com comportamento diferente; o aplicativo móvel precisa de burst.
• Ao estourar o limite, devolveremos um erro.
• Não precisamos nos preocupar com DDoS aqui.

Isso já traz mais clareza ao cenário e facilita o trabalho.

Vamos ajustar o zoom para visualizar a estrutura inicial: o aplicativo móvel, o parceiro e a integração de cliente. Há um load balancer (balanceador de carga) exposto na frente, que encaminha as chamadas para os microsserviços. Agora, com mais informações, podemos começar a pensar nas estimativas.

Vamos adicionar outro bloco de texto chamado “Estimativas” e ajustar o zoom novamente.

Estimando carga e limites

Estimativas

• Pico de consumo: 20 mil requisições por segundo.

• Estado: com 50 mil chaves, teremos um contador por chave (50 mil contadores).

• Tamanho do contador em bytes: considerando 50 mil chaves, falamos de dezenas de bytes por contador e, portanto, de poucos megabytes para armazenar todo o estado.

• Latência: qual é o nosso orçamento de latência adicional por requisição? Podemos adicionar apenas 1 ou 2 milissegundos, no máximo.

Esses são cuidados fundamentais ao projetar um Rate Limiter para uma API.

Desenhando o rate limiter

A primeira tarefa no quadro é desenhar o nosso rate limiter (limitador de taxa).

Removemos o quadrado de interrogação, adicionamos um novo quadrado, posicionamos corretamente e rotulamos como rate limiter (limitador de taxa). Esse componente ficará posicionado para poupar acessos às APIs (interface de programação de aplicações). Se o limite for excedido, não chegaremos à API.

Definimos, então, o contrato do rate limiter (limitador de taxa). A entrada no input é a chave da API (interface de programação de aplicações) presente no header (cabeçalho). Para a saída, quando a requisição passa, ela segue normalmente para a API (interface de programação de aplicações). Quando barra, retornamos 429 — Too Many Requests (muitas requisições) —, junto com o Retry-After (tentar novamente após) e os cabeçalhos de cota. Assim, quem consome e quem avalia nosso desenho entende que estamos baseando a arquitetura em contratos.

O rate limiter (limitador de taxa) ficará entre o load balancer (balanceador de carga) e as APIs (interface de programação de aplicações), protegendo todos os serviços de uma vez. É possível colocar um sidecar (componente acoplado) por serviço, mas isso tem custo; como alternativa, adotaremos um rate limiter (limitador de taxa) global.

Precisamos de um local para armazenar o contador e sabermos quantas requisições cada chave fez dentro de um minuto. Armazenaremos esse contador em um banco chave-valor de alta velocidade, como o Redis. Conectamos o rate limiter (limitador de taxa) ao Redis com uma relação bidirecional. Isso é importante porque, com várias instâncias do rate limiter (limitador de taxa) e um Redis separado, o contador é compartilhado entre todas as instâncias.

Também precisamos de um local onde residem as regras de limite. Essa será a nossa terceira caixa: regras de limite. Essas regras alimentam o contador porque cada tipo de cliente pode ter uma regra diferente. Nem todo cliente aceita o mesmo comportamento; por exemplo, existe um aplicativo que opera em rajadas. Essas regras precisam existir de forma explícita.

Por fim, adicionamos mais uma caixa para a lógica de negação: a caixa 4, rotulada como 429, que referencia o código HTTP (protocolo de transferência de hipertexto) e o Retry-After (tentar novamente após), indicando quanto tempo deve-se esperar. O rate limiter (limitador de taxa) aponta para essa lógica e devolve o estado de erro quando necessário. Como partimos de um desenho orientado a contrato, o retorno ao cliente inclui informações sobre o consumo, inclusive o quanto resta da cota. Com essa visibilidade, a pessoa cliente pode reduzir as requisições quando se aproxima do limite, o que diminui o tráfego.

Consideramos também componentes relacionados ao nosso rate limiter (limitador de taxa), como um possível register (registro) no diagrama, que podemos reposicionar conforme a necessidade arquitetural.

Garantindo resiliência e consistência

Se o Redis cair, identificamos um ponto único de falha que pode derrubar o rate limiter (limitador de taxa). Precisamos de uma decisão para esse cenário. Podemos adotar uma regra de tolerância a falhas do tipo “fail-open”: se o Redis falhar, deixamos passar as requisições. Preferimos correr o risco de exceder o limite a derrubar a API (interface de programação de aplicações) por uma falha nossa.

Outro ponto importante: incrementar o contador e definir a expiração do contador são dois comandos distintos. Temos o valor do contador e um teto temporal (o próximo minuto). Entre executar um comando e outro, outra requisição pode chegar. Portanto, a operação de incremento e ajuste da expiração precisa ser atômica para evitar race condition (condição de corrida). Esse cuidado é fundamental.

Com a evolução do sistema, é provável que o escopo cresça e o limite deixe de ser apenas por cliente, passando a ser por serviço. Assim, podemos mudar a regra de limite sem afetar a arquitetura, pois temos a caixa de regras separada.

O ponto central, especialmente porque tratamos de janelas de segundos, é evitar race condition (condição de corrida) ao incrementar o contador. Há diversos fatores que influenciam o cenário. A solução proposta aqui é minimamente viável e coerente com os requisitos levantados.

Essa não é a única solução possível. O que se avalia, sobretudo em um processo de entrevista, é o raciocínio: perguntar se o limite é global, se todas as pessoas clientes têm o mesmo comportamento, entre outras questões, demonstra bagagem e pensamento arquitetural mais amplo do que apenas desenhar caixas no draw.io (ferramenta de diagramas).

Antecipando próximos passos

Para este primeiro exercício, a arquitetura está bem definida. Antes de avançarmos para a próxima atividade e o próximo desafio, conversaremos sobre algoritmos de persistência para implementar o rate limiter (limitador de taxa).

Vamos retomar esse assunto no próximo vídeo, pois temos alguns slides para apresentar.

Nos vemos lá.

Rate Limiter - Token bucket e sliding window por dentro

Interpretando o contrato de 100 requisições por minuto

Vamos detalhar o algoritmo de configuração do nosso Rate Limiter (limitador de taxa). Resolvemos o nosso case (caso) no quadro, e agora vamos aprofundar o raciocínio. O limite parece óbvio: 100 requisições por minuto. Em 60 segundos, 100 requisições — é comum ver isso em uma documentação de API. Mas o que esse contrato permite de fato? Qual é a leitura que podemos fazer dessas 100 requisições por minuto?

Pensamos em duas leituras de imediato. Podemos fazer as 100 requisições de uma só vez e esperar um minuto para repetir, ou podemos distribuí-las no tempo para obter uma média de 1,6 requisições por segundo. As duas abordagens respeitam o mesmo contrato. Em um gráfico, isso fica claro: no segundo 1, 100 requisições — podemos fazer a rajada, o burst (rajada); ou podemos espalhar as requisições ao longo do tempo, ainda dentro do mesmo contrato. São formas opostas de resolver o problema.

Vale mencionar que estamos usando o conceito de burst (rajada) desde o nosso exercício do board (quadro). O que é uma rajada? É quando encadeamos requisições muito próximas entre si, chegando juntas, em oposição a distribuí-las no tempo. No nosso exemplo, podemos ter 100 requisições espalhadas dentro de um minuto ou, no segundo 1, as 100 requisições de uma só vez.

Configurando rajada no Nginx

Utilizamos o termo burst (rajada) porque, em ferramentas como NGINX, essa configuração aparece explicitamente. Definimos ali qual é o limite de burst (rajada) que vamos permitir. Para visualizar isso de forma concreta, um exemplo típico de diretiva no NGINX seria:

limit_req zone=api burst=20 nodelay;

Esse trecho ilustra como declarar explicitamente a capacidade de rajada permitida.

Avaliando impactos de picos e necessidade de rajada

O servidor não sofre com o total distribuído ao longo do tempo; ele sofre com o que chega junto, com o pico de consumo.

Nesse cenário de pico, o que tende a estourar primeiro? O pool (conjunto) de conexões pode saturar, a CPU pode atingir o limite, o garbage collector (coletor de lixo) começa a pressionar o sistema e a latência sobe para todas as requisições, inclusive para aquelas que estão na fila enquanto outras consomem todos os recursos disponíveis. Por isso, precisamos ter cuidado com essas APIs, principalmente com APIs públicas. Sem essa preocupação, a média pode até fechar dentro do contrato, mas o sistema cai. Em essência, essa é a matemática do nosso rate limit (limite de taxa).

Rajada não significa necessariamente abuso. Pensemos em uma segunda-feira, às 8 horas da manhã: desbloqueamos o celular e abrimos um app (aplicativo). Nesse primeiro momento, o aplicativo busca no servidor tudo o que precisa para montar a primeira tela. Por exemplo, solicita perfil e sessão, notificações, configurações e feature flag (flag de recurso). Isso é normal; não é um ataque. É um aplicativo carregando a primeira tela da forma mais otimizada possível. Esse aplicativo que sincroniza no boot (inicialização) precisa de rajada.

Por outro lado, se o checkout (finalização de compra) suporta apenas 50 acessos simultâneos, não podemos permitir rajada nesse ponto, pois derrubaremos o serviço. A pergunta, portanto, não é “qual algoritmo?”, e sim a que fizemos no nosso exercício: precisamos permitir burst (rajada)? Se soubermos a resposta, então escolhemos o algoritmo.

Explorando algoritmos de rate limiting

Um desses algoritmos é o token bucket (balde de tokens). A ideia é termos um balde com capacidade definida (por exemplo, 20 tokens). Cada requisição consome 1 token. Se ainda há tokens, retornamos 200 OK; se o balde está vazio (zero tokens), retornamos erro. O balde é reabastecido por um mecanismo de refill (reabastecimento) — por exemplo, 10 tokens por segundo — até o limite máximo. Assim, enquanto há tokens disponíveis, as requisições passam; à medida que são consumidos, vamos reabastecendo continuamente até o teto configurado.

A capacidade do balde corresponde ao tamanho da rajada que queremos permitir. Se quisermos permitir uma burst (rajada) de 20, o tamanho do balde é 20. A refill rate (taxa de reabastecimento) é a vazão que vamos sustentar com o passar do tempo. Esses dois parâmetros são independentes: conseguimos permitir uma rajada grande com vazão baixa.

Existe outro cenário, que é o de janela de tempo fixa. Trata-se de um contador que é reiniciado na virada do intervalo configurado, independentemente de qual seja o período. É mais simples de implementar e barato de armazenar, por exemplo, como uma chave no Redis que já utilizamos. Porém, essa abordagem apresenta falhas. Se reiniciarmos o contador a cada 1 minuto, é possível fazer 100 requisições às 12:59 e mais 100 às 13:00. Em 2 segundos, teríamos 200 requisições, pois as chamadas ficaram coladas na borda entre janelas. Isso acontece porque a janela fixa só observa a si mesma; ela não considera o último minuto, apenas o minuto específico em curso.

Para resolver esse problema, precisamos guardar o timestamp (marca temporal) de cada requisição, descartar o que saiu da janela e manter o que ainda está dentro. A precisão precisa ser perfeita; quando trabalhamos com timestamp, a janela deixa de ser fixa. Por outro lado, o custo cresce conforme o tráfego.

Se utilizarmos um contador com janela que se move, estamos falando de uma abordagem de Sliding Window (janela deslizante). Nesse caso, observamos a janela anterior e a janela atual. Se houver 84 requisições na janela anterior, a janela atual permite apenas 36. Fazemos o cálculo proporcional, mas, por qualquer motivo, a janela deslizante também não deve olhar apenas para si.

Definindo onde manter o contador

Vamos sair da matemática e pensar em onde o contador deve residir na nossa infraestrutura. Se tivermos apenas uma instância, podemos manter tudo em memória. Com múltiplas instâncias atrás de um load balancer (balanceador de carga), o contador precisa ser compartilhado; caso contrário, cada instância teria o próprio limite, o que geraria inconsistências. Portanto:

• Com uma instância, podemos manter em memória.
• Com N instâncias, precisamos de um contador compartilhado.

Nesse ponto, entra o padrão com Redis: incrementamos a chave e definimos a expiração. Para ilustrar essa sequência com dois comandos separados:

INCR chave
EXPIRE chave 60

Contudo, há dois comandos, o que pode causar problemas. Entre incrementarmos e definirmos a expiração, cabe uma requisição, e duas requisições simultâneas podem passar na mesma verificação (check). Além disso, se o comando de expiração falhar, a chave pode “viver para sempre”, travando a pessoa cliente, pois o contador nunca será reiniciado. Precisamos, portanto, de algo que execute de forma atômica: ou fazemos tudo, ou não fazemos nada.

Garantindo atomicidade com script lua

Uma forma de garantir essa atomicidade no Redis é empacotar as operações em um script:

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

Com isso, a contagem e a definição de expiração são aplicadas como uma única unidade de trabalho.

Comunicando limites e escolhendo abordagens

Outro ponto importante é o tratamento da negação. Vamos retornar um 429, mas podemos ajudar a pessoa cliente com informações adicionais: por exemplo, “tente novamente em 30 segundos”, indicando que o limite sobrando é zero e que o contador será reiniciado em um determinado timestamp (marca temporal). Com essas informações, a pessoa que recebe o erro consegue tomar decisões, inclusive aplicar mecanismos de resiliência para o software se auto-recuperar e tentar novamente. Um exemplo de resposta seria:

HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1717171717

Resumindo o raciocínio (como em uma entrevista):

• Permite rajada? Utilizamos Token Bucket (balde de tokens).
• Não permite rajada? Utilizamos Sliding Window (janela deslizante).
• Se a escala é mais importante do que a precisão, utilizamos Sliding Window Counter (contador de janela deslizante).

Configurando limites por cliente

No nosso cenário, precisamos de um misto dessas abordagens. Criamos um bloco de configuração para, cliente a cliente, definir a regra de limite para cada API.

Com isso, concluímos o primeiro desafio e agora temos uma API que configura corretamente o rate limiter (limitador de taxa), retornando um 429 informativo.

Sobre o curso Desafios de system design: aprenda a implementar solução para um sistema inteiro

O curso Desafios de system design: aprenda a implementar solução para um sistema inteiro possui 235 minutos de vídeos, em um total de 51 atividades. Gostou? Conheça nossos outros cursos de Arquitetura de Software em Back-end, ou leia nossos artigos de Back-end.

Matricule-se e comece a estudar com a gente hoje! Conheça outros tópicos abordados durante o curso:

• Rate Limiter
• Gerador de ID distribuído
• Key-Value store distribuído
• Web Crawler
• Search Autocomplete
• Chat em tempo real
• Steaming de vídeo
• Sincronização de arquivos