A tecnologia por trás de escalar o One Million Checkboxes até 650 milhões de marcações

 (eieio.games)
1 pontos por GN⁺ 2024-07-28 | 1 comentários | Compartilhar no WhatsApp
  • Lançado em 26 de junho de 2024, o One Million Checkboxes era um site em que todos manipulavam em tempo real os mesmos 1 milhão de checkboxes, e processou mais de 650 milhões de marcações antes de encerrar duas semanas depois
  • O estado em si tinha apenas 1 milhão de bits, ou 125 KB, mas a arquitetura inicial feita com nginx, Flask/gunicorn e Redis pubsub rapidamente atingiu seus limites diante de um tráfego inesperado
  • Quando dezenas de milhares de pessoas chegaram via Hacker News, Reddit, Mastodon e Twitter, surgiram em sequência problemas como esgotamento de conexões do Redis, explosão no uso de banda, falta de validação de entrada e aplicação de atualizações antigas
  • A resposta se concentrou em medidas que podiam ser aplicadas rapidamente, como expandir servidores e Redis, processar atualizações em lote, reduzir o formato de transmissão, impor um limite de banda de 250 Mbit/s com tc no Linux e usar scripts para reiniciar processos
  • Depois, o backend foi migrado para Go para estabilizar o serviço e, no fim, a lógica de congelamento dos checkboxes passou a ser tratada de forma atômica com scripts Lua no Redis, encerrando o site em 11 de julho de 2024 às 4:35 PM no horário do leste dos EUA

O site e o design inicial

  • One Million Checkboxes (OMCB) é um site lançado em 26 de junho de 2024 que oferecia 1 milhão de checkboxes globais
    • Quando um usuário marcava ou desmarcava um checkbox, a mudança aparecia imediatamente na tela de todos os usuários
    • A criação levou 2 dias, e a expectativa era de no máximo algumas centenas de usuários
  • A reação real foi muito maior do que o esperado
  • Parte dos logs do começo do primeiro dia não foi preservada
    • No início, só eram mantidos os 1 milhão de registros mais recentes por dia
    • A estabilização começou a partir do segundo dia, quando mais de 50 milhões de checkboxes foram marcados
    • Antes do encerramento do site, o total acumulado de marcações passou de 650 milhões

A arquitetura original centrada em Redis

  • O estado dos checkboxes era representado por 1 milhão de bits
    • Um checkbox marcado era 1, e um desmarcado era 0
    • O tamanho total do estado era 125 KB
    • O cliente armazenava esse bitset e o consultava na hora de renderizar
  • O cliente foi projetado para evitar sobrecarga no DOM
    • Os 1 milhão de elementos não eram inseridos todos no DOM
    • Usando react-window, eram renderizados apenas os checkboxes visíveis na tela e um pequeno buffer
  • A configuração do servidor era simples e pensada para expansão horizontal
    • O nginx servia o conteúdo estático e encaminhava requisições de API e conexões websocket para o servidor Flask
    • O servidor Flask rodava em duas instâncias com gunicorn
    • O Redis ficava responsável por armazenar o estado dos checkboxes e atuar como fila de mensagens
  • A forma de usar Redis também era direta
    • Primitivas de manipulação de bits do Redis eram usadas para alterar o estado de checkboxes individuais
    • Quando o cliente enviava um evento de marcação, o Flask invertia o bit no Redis e registrava o evento no pubsub
    • Os dois servidores Flask liam o pubsub e notificavam as mudanças aos clientes conectados a eles
  • O snapshot completo do estado servia para corrigir perda de atualizações
    • Era usado para ressincronizar clientes que tinham perdido updates por estarem com a aba em segundo plano
    • A implementação inicial enviava o estado completo a cada 30 segundos

Princípios de escala

  • O custo precisava ter um teto calculável
    • Evitou-se um modelo de autoscaling ilimitado que pudesse explodir os custos
    • A escolha foi deixar o sistema quebrar sob carga acima do esperado
  • Assumiu-se que a duração da popularidade seria curta
    • Em vez de priorizar soluções refinadas que levariam dias ou semanas, a preferência foi por respostas que pudessem ser feitas em poucas horas
    • A dívida técnica gerada por isso foi aceita
  • As escolhas técnicas privilegiaram simplicidade e operação direta
    • Preferiu-se uma configuração em que fosse possível entrar no servidor, rodar comandos e depurar manualmente
    • As dependências escolhidas eram principalmente aquelas que podiam ser operadas e depuradas diretamente
  • A experiência central do site era a sincronização global
    • Era importante que fosse possível ver mudanças imediatas em qualquer lugar
    • Não se optou por escalar enviando apenas os checkboxes visíveis para cada usuário

Primeiro dia: expansão de servidores e gargalo no Redis

  • A carga disparou em menos de 30 minutos após o lançamento, e o site ainda estava no ar, mas dificilmente aguentaria por muito tempo
    • A melhoria mais óbvia era adicionar mais servidores
    • O nginx podia facilmente fazer reverse proxy para instâncias Flask em outras VMs, e o estado já estava no Redis
  • Um segundo servidor foi adicionado por volta de 12:30 PM, e logo chegou a 100% de carga
    • No começo, parecia que bastaria adicionar um ou dois servidores
    • Na prática, o tráfego crescia na mesma medida em que a infraestrutura era expandida
    • O site chegou ao topo do Hacker News e a atividade no Twitter também disparou
  • As conexões entre os servidores Flask e o Redis viraram gargalo
    • Não havia pool de conexões Redis, e o Redis estava perto de esgotar as conexões disponíveis
    • A solução foi mudar para o envio de atualizações em lote
    • Compatibilidade com clientes antigos não foi considerada, assumindo que os usuários dariam refresh
  • Também foi adicionado um pool de conexões Redis, mas a combinação de gunicorn e Flask não funcionou de forma limpa
    • Ainda assim, isso aparentemente ajudou a reduzir o número de conexões Redis
    • Depois, em vez de investigar a fundo, a decisão foi seguir para a migração para Go
  • O rate limit de criação de sessão foi removido
    • O estado do rate limit era armazenado no Redis, e as conexões com o Redis já estavam se esgotando
    • O problema não era a explosão de novas sessões, mas sim o envio de muitos dados dentro de uma única sessão
    • No curto prazo, isso foi considerado arriscado, mas aceitável
  • A instância Redis também foi aumentada
    • Estava sendo usado o Redis gerenciado da Digital Ocean
    • A instância foi ampliada de uma configuração pequena com 1 CPU compartilhada e 2 GB de RAM para uma com 4 CPUs dedicadas e 32 GB de RAM
    • O redimensionamento levou cerca de 30 minutos

Problema de banda e redução do volume transmitido

  • No início, o custo de banda não foi suficientemente considerado
    • A Digital Ocean cobra $0.01 por GB acima da franquia gratuita de banda
    • Já havia 1 TB de banda gratuita por causa de um trabalho anterior, e a expectativa era que o OMCB não tivesse grande impacto
  • Snapshots completos do estado podiam consumir banda rapidamente
    • 1 milhão de bits correspondem a 1 Mbit
    • Enviar isso para 1.000 pessoas a cada 30 segundos equivale a cerca de 2 GB por minuto, ou 120 GB por hora
    • Esse cálculo nem considera as atualizações incrementais
  • A checagem de banda e a definição de teto de custo foram feitas na máquina do nginx
    • O número de bytes enviados era verificado com ip -s link show dev eth0
    • Como havia um único reverse proxy nginx, era fácil inferir a origem do uso de banda
  • A redução do volume transmitido seguiu por dois caminhos
    • A frequência dos snapshots completos foi reduzida
    • O formato das atualizações incrementais foi enxugado
  • O formato das atualizações em lote foi bastante comprimido
    • O formato anterior era uma lista de dicionários como { "index": 123, "value": true }
    • O formato final passou a ser um par de arrays com índices true e índices false, na forma [[123, 125], [124]]
    • Esse formato ficou 5 vezes menor que a implementação original
  • Um hard cap foi imposto com tc no Linux para evitar descontrole de custos
    • O tráfego da interface pública eth0 foi limitado a 250 Mbit/s
    • Isso equivale a cerca de 2 GB por minuto, ou pouco menos de 3 TB por dia
    • Considerando $0.01 por GB, isso evitava um cenário em que o custo crescesse de forma incontrolável durante a noite

Segundo dia: falta de validação de entrada e réplica do Redis

  • Na manhã seguinte, o site estava fora do ar, e a causa foi falta de validação de entrada
    • Não havia bloqueio para índices acima de 1 milhão
    • Alguém manipulou checkboxes com índices na casa das centenas de milhões
    • Isso fez parecer que o número de checkboxes marcados tinha chegado a 1 milhão e que o site havia terminado
  • Os dados no Redis também cresceram sem necessidade
    • Entre o bit de número 1 milhão e o bit de número 100 milhões, foram adicionados milhões de zeros
    • Os dados enviados ao cliente ficaram 100 vezes maiores
  • A recuperação foi rápida
    • O nginx foi parado
    • Apenas os primeiros 1 milhão de bits do bitset antigo foram copiados para um novo bitset
    • O bitset antigo foi preservado para depuração
    • O código passou a apontar para o novo bitset e a validação de entrada foi adicionada
  • O carregamento inicial da página também ficou lento
    • O Redis estava muito sobrecarregado, e um bug no pool de conexões criava conexões demais
    • Em vez de depurar o problema do pool, foi adicionada uma réplica Redis para distribuir a carga e as conexões do primário
  • O IP privado da réplica precisou ser encontrado manualmente
    • Seguindo a orientação da Digital Ocean, o prefixo replica- funcionava no DNS público, mas não no DNS privado
    • Usar o IP público parecia arriscado por envolver internet pública e possível cobrança de banda
    • Foram tentadas conexões para endereços próximos ao IP privado do primário e dos outros servidores, e o IP privado da réplica foi encontrado na terceira ou quarta tentativa
    • Depois disso, esse IP foi colocado diretamente no código

Reinício de processos e correção de stale update

  • Os processos Flask continuavam travando, e o motivo parecia ser a falta de conexões Redis
    • Em vez de fazer uma depuração detalhada, foi criado um script bash para verificar quantos processos Flask estavam em execução
    • Se houvesse menos de 3 processos rodando, a unit do systemd era reiniciada
    • O script foi colocado no crontab
  • A configuração do nginx também foi ajustada
    • Servidores fora do ar passaram a ser temporariamente removidos da rotação
    • Depois dessa mudança, o site se estabilizou
  • A sincronização de estado no cliente tinha um bug de stale update
    • O cliente recebia tanto atualizações incrementais quanto snapshots completos do estado
    • Como nenhuma delas tinha timestamp, era possível aplicar uma atualização incremental antiga depois de receber um snapshot novo
    • Como resultado, o usuário podia ver um estado completamente incorreto até o próximo snapshot completo
  • Foi adicionada uma mitigação baseada em timestamp
    • Um timestamp foi incluído no snapshot completo do estado
    • Cada atualização registrada no pubsub do Redis também passou a ter timestamp
    • O lote enviado ao cliente incluía o maior timestamp entre as atualizações incrementais contidas nele
    • O cliente foi alterado para descartar lotes mais antigos que o último snapshot completo recebido
  • Essa solução não era perfeita
    • Se houvesse pelo menos uma atualização nova dentro do lote, ele ainda podia ser aplicado mesmo que a maioria das atualizações fosse antiga
    • Ainda assim, foi uma melhora significativa em relação à situação anterior

Reescrita em Go e estabilização

  • Na manhã seguinte, o site estava no ar, e o foco passou a ser reescrever o backend
    • Um e-mail do Washington Post já tinha chegado
    • Também já se pensava em como encerrar o site
  • O plano de encerramento era congelar checkboxes que não fossem desmarcados rapidamente
    • Essa mudança poderia provocar pico de atividade e mais trabalho de infraestrutura
    • Não havia confiança de que a estrutura baseada em Flask conseguiria suportar isso
  • Junto com o amigo Eliot, o backend foi reescrito em Go
    • No domingo, das 2 PM às 2 AM, foi discutida a implementação e todo o backend foi portado
    • A estrutura foi migrada sem grandes mudanças
    • Um dos obstáculos foi encontrar uma biblioteca Go de socketio que suportasse o protocolo mais recente
  • O ganho de desempenho foi enorme
    • O sistema passou a escalar tão bem que bots conseguiram injetar tráfego em excesso
    • Isso criou a necessidade de um rate limit melhor
  • Também houve um DDoS na noite de domingo
    • A resposta foi colocar o site atrás do Cloudflare e ajustar um pouco a configuração do nginx

Lógica de encerramento do site

  • Depois da reescrita em Go, o site passou a operar de forma estável
    • Na semana seguinte, a atenção se voltou para entrevistas e ao interesse público
    • Depois disso, começou o trabalho de encerramento do site
  • O método de encerramento foi o congelamento dos checkboxes
    • Se um checkbox marcado não fosse desmarcado rapidamente, ele entrava em estado frozen
    • Com o passar do tempo, o site inteiro acabava completamente frozen
  • Estados adicionais foram adicionados ao Redis
    • Foi criada uma hash table para armazenar o horário da última marcação de cada checkbox
    • Era um estado grande demais para enviar ao cliente, mas aceitável para armazenar no Redis
    • O valor time_to_freeze também foi armazenado
  • A decisão sobre congelar era feita no momento do uncheck
    • Se now - last_checked > time_to_freeze, o checkbox não era desmarcado
    • Em vez disso, o frozen_bitset era atualizado para indicar que aquele checkbox estava frozen
    • O frozen_bitset era distribuído aos clientes da mesma forma que o estado checked
    • O cliente desativava checkboxes com o bit frozen ativado
  • Foi adicionado um trabalho separado para que o congelamento ocorresse mesmo sem ninguém desmarcando
    • Periodicamente, ele encontrava bits que já deveriam estar frozen, mas ainda não estavam marcados assim
    • A lógica correspondente foi colocada em um script Lua no Redis para execução atômica
    • Isso facilitava evitar race conditions
  • A mudança de encerramento foi aplicada 2 semanas e 1 dia após o lançamento
    • Em 11 de julho de 2024, às 4:35 PM no horário do leste dos EUA, o box 491915 foi marcado e o site foi encerrado

Custos e lições aprendidas

  • O custo de operar o site foi de cerca de $850
    • As doações chegaram bem perto desse valor
    • A conclusão foi que não houve um grande prejuízo
  • Houve satisfação com a escolha de Redis e nginx
    • Redis e nginx foram avaliados como tecnologias muito úteis
    • Operá-los diretamente facilitou depuração e correções
    • Por outro lado, foi um pouco incômodo não ter controle total sobre a instância Redis gerenciada
  • A decisão de não planejar por muito tempo uma grande escala desde o começo foi vista de forma positiva
    • Na internet, é difícil prever o que vai dar certo
    • Se semanas tivessem sido gastas pensando em escala desde o início, talvez o lançamento nem tivesse acontecido
    • A entrada de muitos usuários ajudou a motivar a manutenção e a definir prioridades
  • Também ficou claro que existe demanda por interações anônimas limitadas
    • As pessoas demonstraram interesse em sites que permitem interagir com desconhecidos de forma restrita
    • Isso aumentou a confiança para continuar criando esse tipo de site

Leituras relacionadas

1 comentários

 
GN⁺ 2024-07-28
Comentários no Hacker News

  • Foi um texto com muito a aprender, junto com conhecimento histórico de sistemas distribuídos
    Tirando armazenamento, parece que passou por quase todo tipo de interrupção e ponto de falha, e foi bom poder ver o processo de resolução
    Eu não sabia que o Redis suportava Lua, mas vendo isso fiquei com vontade de experimentar usá-lo como armazenamento de estado alternativo
    Largura de banda é uma das maiores reclamações em serviços de nuvem, porque não existe um limite rígido para impedir cobrança excedente

    • Armazenamento também apareceu, de um jeito sem graça. O logrotate não estava configurado direito, então o disco ficou quase cheio, e tive que criar um mecanismo para mover logs antigos para disco para evitar que o Redis explodisse enquanto eu enviava os logs do box-check para ele
      Mas nenhum dos dois virou um grande problema, e foi bem curioso um projeto em que armazenamento não foi um problema relevante. Para mim, pessoalmente, foi uma experiência nova
      Largura de banda foi realmente angustiante. Fiquei uns dois dias em tensão constante olhando os bytes transmitidos da NIC e refazendo as contas, e a ausência de um hard cap dava medo. Isso mesmo com a Digital Ocean sendo relativamente razoável em preço
      Não usei serviços serverless populares, mas entendo que lá o custo de largura de banda pode bater bem pesado
      E Lua dentro do Redis é realmente muito poderoso; se você aceitar uma pequena perda de desempenho, dá para pular muitos problemas difíceis e cheios de condições de corrida, e foi prazeroso trabalhar com isso

  • Ótimo texto, e o site também merece parabéns
    Mas, pessoalmente, acho que esta matéria escrita é a parte de que mais deveriam se orgulhar

    • Acabei gastando muito mais tempo escrevendo o texto do que criando o site antes do lançamento, e isso pareceu bem engraçado

  • Acho que o ponto principal é: “foi uma boa escolha construir o site em dois dias sem praticamente se preocupar com escalabilidade”
    Isso é algo que engenheiros, especialmente no começo da carreira, precisam aprender. Escalabilidade não é um problema até virar um problema
    E quando vira, na verdade é um bom problema, e normalmente não é tão difícil de corrigir quanto se imagina

    • Isso só é verdade se vier junto da ideia de manter o sistema simples e básico
      Já vi muitos sistemas em que microsserviços viraram a “escolha óbvia” não por escalabilidade ou separação de equipes, mas porque os desenvolvedores simplesmente queriam fazer assim
      Escalar esses sistemas é um verdadeiro suplício

  • Texto relacionado recente: One Million Checkboxes - https://news.ycombinator.com/item?id=40800869 - junho de 2024, 305 comentários

  • Projetos assim são divertidos
    Há uns 6 anos lancei o Pixmap no Android, um pequeno app colaborativo de edição de pixels que suportava grades maiores, como 1024x1024
    Eu tinha uma fila que aplicava cada evento a uma imagem PNG, e o cliente, ao conectar, carregava o PNG inicial; depois, cada evento de desenho de pixel recebia só um pequeno objeto
    Assim, no carregamento inicial dava para aproveitar a compressão da imagem, e depois o conjunto de mudanças ficava bem pequeno. Além disso, como todos os eventos eram salvos em log, também dava para “rebobinar” a imagem [0]
    [0] 22mb: https://blog.winricklabs.com/images/pixmap-rewind-demo.gif

    • Muito legal. Eu cheguei a olhar uma ideia parecida de enviar atualizações por pixel para vários clientes web, mas do jeito que eu queria fazer parecia que consumiria largura de banda e armazenamento demais
      Então estou brincando com uma tela endereçável por chamadas de API
      https://x.com/RussTheMagic/status/1816749136487588311

  • Bom texto. Fiquei curioso sobre quanto acabou custando no fim

    • Eu deveria ter incluído isso
      O custo total foi de cerca de 850 dólares, e as doações praticamente cobriram isso
      Depois de migrar para Go, cometi o erro de não derrubar a infraestrutura direito, e também poderia ter removido a segunda réplica extra do Redis. Se eu tivesse focado em custo, acho que daria para cortar pela metade
      Mas as doações estavam praticamente cobrindo os custos, e havia tantas outras coisas acontecendo que eu não foquei muito nisso
      Mesmo depois de encerrar o site, mantive a infraestrutura por um tempo para preparar gráficos e outras coisas, então saiu um pouco mais de dinheiro; agora estou com um pequeno prejuízo, mas nada muito grande

  • Como alguém que está aprendendo backend, fiquei me perguntando se existe uma arquitetura alternativa mais simples para esse projeto
    Seria bom ter um jeito mais fácil de hospedar o estado de 1 milhão de bits e sincronizá-lo com os clientes. Algumas soluções no texto foram difíceis de entender
    Os projetos do autor são excelentes

    • Se parte do texto ficou difícil, desculpe
      Eu queria explicar com mais detalhes as tecnologias que usei, mas o texto já estava muito longo e senti que não dava para colocar mais
      Se tiver perguntas, terei prazer em responder
      Sinceramente, não sei muito bem como simplificar bastante mais a arquitetura. Existem serviços que poderiam ser usados para isso, mas eu vejo isso mais como transferir a complexidade para outra pessoa
      No fim, o que você precisa é de um banco de dados para rastrear as caixas marcadas, uma forma de colocar os dados nesse banco, um jeito de informar o estado atual aos clientes, um jeito de o cliente avisar o servidor quando marcar uma caixa e atualizar o estado, um jeito de notificar os clientes quando uma caixa for marcada ou desmarcada, e uma forma de não renderizar 1 milhão de elementos DOM o tempo todo
      Aqui usei Redis para armazenar o estado das marcações, e, por simplicidade, armazenei diretamente os 1 milhão de bits, além de enviar os 1 milhão de bits completos para o cliente. Funcionou bem porque os dados não eram tão grandes
      Usei Flask e WebSocket para tratar os eventos de marcação e as atualizações, enviando tanto atualizações de caixas individuais quanto atualizações do conjunto completo de 1 milhão de caixas, e usei react-window para evitar o problema de renderização
      O restante — conteúdo estático no nginx e proxy reverso — servia principalmente para facilitar a escalabilidade, então dá para implementar sem esses detalhes e o site ainda funciona. Só não aguentaria a mesma carga
    • Também daria para enfiar tudo o que aparece no texto em um único processo
      Em vez de um banco de dados, você poderia salvar o conjunto de bits em um arquivo e fazer mmap. Em vez de um proxy reverso, o aplicativo poderia lidar diretamente com as requisições HTTP e as conexões WebSocket
    • Sinceramente, isso já está quase no nível mais simples possível
      É só algumas instâncias de servidor web com cache e uma fila de publicação/assinatura por trás
      Daria para colocar tudo em memória num host grande só, mas aí, se ele não aguentasse a demanda ou falhasse por qualquer motivo, tudo travaria por completo
    • Sinceramente, acho difícil ficar muito mais simples do que isso
      A não ser por uma abordagem nada escalável, tipo manter uma lista global de 1 milhão de booleanos dentro do mesmo processo da API backend
    • Dava para usar uma quadtree para resumir blocos inteiros de checkboxes com o mesmo estado em tuplas (checked, start_x, start_y, end_x, end_y). Não é o método mais óbvio?

  • Muito legal
    Fiquei pensando se o próximo texto vai ser uma análise estatística sobre quais checkboxes foram os menos ou os mais marcados
    Lembro de ficar um bom tempo rolando para baixo e escolhendo um checkbox, só para ele ser desmarcado quase imediatamente, o que foi meio triste

    • Em breve vou compartilhar os dados brutos
      Antes disso, ainda tenho mais uma história para contar sobre o site

  • Fiquei me perguntando se o jogo ainda estava vivo
    Quando entro em https://onemillioncheckboxes.com/, nada aparece marcado, e no console de JS só vejo isto
    {"total":0,"totalGold":0,"totalRed":0,"totalGreen":0,"totalPurple":0,"totalOrange":0,"recentlyChecked":false}

    • Segundo o texto original, “antes de encerrar o site duas semanas depois, passou de 650 milhões”

  • Como exemplo oposto de uma implementação escalável, existe uma implementação de 1 milhão de checkboxes em menos de 1000 caracteres. Versão em Deno
    https://gist.github.com/jeff-hykin/4cdebafd8698298d021f103e2...