As vantagens de um sistema imperfeito: a timeline com perdas do Bluesky

• Ao projetar sistemas, é praticamente impossível satisfazer ao mesmo tempo consistência perfeita, alta disponibilidade, baixa latência e alta taxa de transferência
  • O importante é encontrar um ponto de equilíbrio adequado à aplicação para chegar a um projeto apropriado
• No design do feed/timeline de seguidores do Bluesky, foi adotado um trade-off que melhora o desempenho de escrita ao sacrificar parte da consistência
  • Como resultado, houve uma redução de mais de 96% na latência P99 sem impacto negativo para os usuários

Fan-out da timeline

• Quando um usuário publica uma postagem no Bluesky, ela é indexada pelo sistema, armazenada no banco de dados e disponibilizada nas respostas da API
• Ao mesmo tempo, essa postagem passa por um processo de “fan-out”, sendo inserida na tabela de timeline de cada seguidor
• Isso é feito consultando a lista de seguidores e, em seguida, realizando inserções em ordem reversa na tabela de timeline de cada seguidor
• As tabelas de timeline são particionadas por usuário e armazenadas em um banco de dados distribuído (ScyllaDB), sendo replicadas em vários shards para alta disponibilidade
  • Cada usuário pode ser alocado em um shard diferente
• Para economizar espaço de armazenamento, timelines que ultrapassam determinado tamanho removem periodicamente referências de postagens antigas

O problema dos hot shards

• O Bluesky tem cerca de 32 milhões de usuários, e o banco de dados de timelines é dividido em centenas de shards
• Em um sistema usado por milhões de pessoas, podem existir usuários com relações de following extremamente numerosas
  • Exemplo: usuários que seguem centenas de milhares de contas
• Em um único shard, várias timelines de usuários ficam armazenadas juntas
• Quando um usuário específico gera muitas escritas, aquele shard entra em estado de sobrecarga (“hot shard”)
• Esses hot shards concentram operações de leitura ou escrita, fazendo com que a latência se propague também para outros usuários no mesmo shard

Acúmulo de latência

• Se um usuário tiver 2.000.000 de seguidores, gravar sequencialmente pode levar mais de 20 minutos
• Para reduzir isso, o fan-out pode ser paralelizado, encurtando a latência média
• Porém, latências P99 (em torno de 15 milissegundos ou mais) podem ocorrer repetidamente e atrasar todo o conjunto de tarefas paralelas
• Quando há seguidores demais, a latência P99 ou P99.9 pode fazer o tempo total de fan-out crescer, no pior caso, de vários minutos para dezenas de minutos

Timeline com perdas

• Para usuários que seguem gente demais, é irrealista mostrar todas as postagens exatamente na ordem correta
• Na prática, também é difícil para uma pessoa consumir todas essas postagens
• Por isso, para timelines de usuários cujo número de follows ultrapassa um certo limite (por exemplo, reasonable_limit), foi introduzido um método que “descarta” probabilisticamente parte das escritas
• É usada a fórmula loss_factor = min(reasonable_limit / num_follows, 1)
• Durante o fan-out, é gerado um valor aleatório e, se ele for maior que loss_factor, a escrita na timeline é ignorada
• Com isso, limita-se a quantidade excessiva de escritas em timelines específicas e evita-se a degradação de desempenho do shard como um todo

Sobre cache

• Como as escritas de timeline passam de um milhão por segundo, consultar diretamente no banco de dados o número de follows do usuário a cada escrita geraria carga demais
• Em vez disso, contas com alta contagem de follows são armazenadas em cache no Redis como um sorted set
• As instâncias do serviço de fan-out carregam essas informações em memória a cada 30 segundos
• Com isso, mesmo durante o processo de fan-out é possível consultar rapidamente informações de usuários com muitos follows
• Como não é necessário que o cache esteja perfeitamente atualizado, o sistema aceita um pequeno grau de imperfeição em troca de mais desempenho e escalabilidade

Resultado

• Após a introdução da timeline com perdas, os hot shards praticamente desapareceram no banco de dados Timelines
• A latência P99 para processar uma página de fan-out caiu mais de 90%
• Considerando o tempo total do trabalho de fan-out, tarefas que levavam de 5 a 10 minutos no P99 passaram a levar menos de 10 segundos
• Isso mostra que, mesmo sacrificando parte da consistência, ainda é possível atender plenamente às expectativas dos usuários e manter escalabilidade em larga escala
• A arquitetura de timeline do Bluesky ainda tem espaço para melhorias, mas essa mudança já aumentou significativamente a taxa de transferência de escrita e a escalabilidade

[GN⁺]

Comentários do Hacker News

• Como entusiasta de sistemas, sou o tipo de pessoa que gosta desse tipo de artigo. É fácil cair na mentalidade de que “precisa ser perfeito”

  • No backend do mecanismo de busca Blekko, construímos um índice “eventualmente consistente”. Isso entrega atualizações mais rápido aos usuários, mas dois usuários executando a mesma consulta podem obter resultados ligeiramente diferentes
  • Há muita teoria de sistemas envolvida, e existe a possibilidade de oscilação quando há feedback positivo. Em um mecanismo de busca, o ranker que dá peso aos links clicados pelos usuários fornece esse feedback positivo
  • Era importante manter o sistema “criticamente amortecido”. Isso faz com que ele convirja rapidamente
  • Parece um espaço de problemas interessante a forma como a timeline do usuário é fragmentada e há loops de feedback (por exemplo, “curtidas” ou “reposts”)

• Fico pensando por que não implementar a timeline de forma híbrida com base na popularidade da conta

  • No caso de contas de celebridades, em vez de distribuir todas as mensagens para milhões de seguidores, seria mais barato buscar e mesclar as postagens da celebridade ao entregar a timeline do seguidor
  • Se milhões de seguidores fizerem isso, deve sair barato buscar só para leitura a partir de um hot cache

• Solução interessante para um problema interessante. Obrigado por compartilhar

  • Tive dificuldade para entender a parte em que o autor muda de “celebridade” para “bot”
  • Pareceu que o autor introduziu um conceito completamente diferente, o da “timeline com perdas”

• Tenho curiosidade sobre essa estratégia de sacrificar consistência. Fico pensando se há ideias para algo diferente de fanout completo na leitura ou na escrita

  • Em vez de escrever na timeline de todos os usuários, imagino escrever apenas uma vez em cada shard que tenha pelo menos um seguidor
  • Na leitura, busca-se o conteúdo do usuário em questão e filtra-se pelos seguidores reais
  • Como a leitura fica localizada dentro do shard, a latência é baixa
  • No caso de mega seguidores, a página não deixaria de ver itens antigos

• Não é necessário entregar tudo o que foi postado por milhares de usuários que todos seguem em ordem cronológica perfeita, mas faz sentido entregar conteúdo suficiente para que sempre haja conteúdo novo na timeline

  • A solução pareceu não ser uma ordem temporal imperfeita, mas sim postagens ausentes no feed

• Fico pensando como funcionaria limitar a quantidade de seguidores para evitar o problema de hot shard

  • Cada usuário teria uma timeline separada a cada 1.000 seguidores, e o cliente faria a mesclagem
  • Se necessário, seria possível carregar apenas parte da timeline real para aplicar a parte com perdas

• A AWS tem uma abordagem geral interessante para esse problema

  • Ela atribui cada usuário a vários shards, reduzindo a chance de que outros usuários compartilhem todos os shards
  • Se tivesse feito shuffle sharding desde o início, poderia ter resolvido novos problemas sem afetar muitos outros usuários

• Contas que seguem centenas de milhares de usuários claramente são bots que raspam conteúdo. Eu bloquearia e pronto

  • Gosto de ler sobre desafios técnicos. O Twitter tem uma arquitetura especial para celebridades com milhões de seguidores
  • Se o Bluesky é um clone semelhante, fico pensando por que não seguiram isso

• Ao ir diretamente ao perfil de um usuário para ver todas as postagens, às vezes há postagens que deveriam estar na timeline e não estão

  • Isso explica por que, no Bluesky, mesmo seguindo menos de 100 usuários, às vezes eu não vejo postagens de alguém na timeline

• Fico pensando por que implementaram o fanout de um jeito em que cada “página” bloqueia a busca da próxima página

  • A atividade de busca de páginas deveria poder buscar seguidores sequencialmente e não precisar esperar até que todos os itens da página fossem atualizados
  • Penso em ter um componente de busca que obtenha a página, armazene no S3 e publique os metadados e a localização no S3 em uma fila (SQS)
  • Nesse sistema, seria possível controlar melhor a concorrência e “desacelerar” o trabalho particionando na fila com o shard como chave