CRDTs mais rápidos (2021)

CRDT 5000 vezes mais rápido: uma aventura de otimização

Introdução

• Há alguns anos, pesquisadores franceses publicaram um artigo comparando algoritmos de edição colaborativa em tempo real
• Eles implementaram vários algoritmos e fizeram benchmark de desempenho
• Alguns algoritmos levavam mais de 3 segundos para uma simples operação de colar
• O algoritmo problemático era o usado pelo ShareJS

Causa do problema

• No artigo, ao colar um texto grande, o processamento foi dividido em 1000 operações individuais
• Isso não era um problema do algoritmo em si, mas da implementação

O apelo dos CRDTs

• CRDTs (Conflict-Free Replicated Data Types) permitem que vários usuários editem dados ao mesmo tempo
• É possível trabalhar localmente sem latência e, na sincronização, a consistência é mantida automaticamente
• Também podem funcionar sem um servidor central

Problemas do Automerge

• Automerge é uma biblioteca para edição colaborativa baseada no algoritmo RGA
• Cada caractere do documento é gerenciado com um ID único, e ao inserir é especificado um item pai
• Por causa de problemas de desempenho, levaram-se 5 minutos para processar 260.000 operações de edição
• O uso de memória também era muito alto

Otimização de desempenho

• Os problemas de desempenho do Automerge eram causados pela estrutura de dados complexa baseada em árvore e pelo uso de Immutablejs
• Yjs melhorou bastante o desempenho usando uma única lista plana
• Yjs usa cache para encontrar a posição de inserção e uma lista duplamente encadeada para processar inserções com eficiência
• Yjs é 30 vezes mais rápido e usa menos memória

Migração para Rust

• Rust permite controlar o layout de memória, o que pode melhorar ainda mais o desempenho
• Com uma nova implementação de CRDT chamada Diamond types, foi possível alcançar desempenho 5 vezes superior ao do Yjs
• Diamond, implementado em Rust, processa 260.000 operações de edição em apenas 56 milissegundos

Conclusão

• Com estruturas de dados otimizadas e gerenciamento eficiente de memória, é possível melhorar muito o desempenho de CRDTs
• Usar uma linguagem de baixo nível como Rust pode levar a um desempenho ainda maior

Resumo do GN⁺

• CRDTs são o futuro da edição colaborativa e uma ferramenta poderosa para manter consistência mesmo sem servidor central
• Os problemas de desempenho do Automerge vinham de uma estrutura de dados complexa e do uso ineficiente de memória
• Yjs e Diamond types melhoram bastante o desempenho com estruturas de dados simples e eficientes
• Usar uma linguagem de baixo nível como Rust pode levar a um desempenho ainda maior
• Ao desenvolver ferramentas de edição colaborativa, vale a pena considerar Yjs e Diamond types

[GN⁺]

Comentários do Hacker News

• O motivo de 32 entradas serem as mais eficientes é que a linha de cache tem 64 bytes

  • Ao usar inteiros de 2 bytes, 32 entradas cabem exatamente em uma única linha de cache, o que pode reduzir transferências da memória principal

• É difícil encontrar exemplos de aplicações reais que usam CRDTs e oferecem uma boa experiência

  • O Notion tem usabilidade inferior à do Google Docs quando duas pessoas escrevem uma nota ao mesmo tempo

• CRDTs são poderosos, mas têm a desvantagem de preservar operações históricas (ou elementos)

  • Mesmo com compressão, isso ainda é uma desvantagem e gera preocupação quanto à adoção
  • Ainda assim, há interesse na possibilidade de provedores de armazenamento baseados em arquivos (Dropbox, Syncthing etc.) implementarem algoritmos sem conflitos

• Citação atual do README no GitHub:

  • Depois da publicação do post no blog, o desempenho melhorou de 10 a 80 vezes

• Mesmo sendo difícil em conteúdo, este artigo foi tão bem escrito que era impossível parar de ler

• Ao ver o uso de hierarquia, surgiu a dúvida se conjuntos aninhados não foram usados no lugar

  • Não há ideia se o ganho em operações de leitura compensaria a perda em operações de inserção

• Encontrei este post por acaso alguns anos atrás

  • Foi um dos posts mais divertidos dos últimos anos

• Fiquei curioso sobre o motivo de o WASM ser 4 vezes mais lento que a execução nativa

  • Achei que fosse porque todo o trabalho com strings precisa ser copiado para a memória do WASM e, depois que o resultado é calculado, copiado de volta para o JS
  • Fiquei na dúvida se entendi esse contexto errado

• Como a implementação em Rust do Automerge foi concluída, seria interessante ver benchmarks atualizados