Edição colaborativa de texto: implementando sem CRDT nem OT

• Apresenta uma nova abordagem para resolver o problema da edição colaborativa de texto, viável mesmo sem algoritmos complexos
• Evita a complexidade e as limitações das abordagens CRDT e OT existentes, usando um método simples de inserção baseado em IDs
• Nesse método, o servidor processa diretamente instruções que especificam 'o que inserir e onde', o que traz mais flexibilidade
• Para atualizações locais otimistas, usa uma estratégia de reconciliação no servidor para resolver problemas de sincronização de estado
• Com escalabilidade e facilidade de compreensão, essa abordagem apresenta uma alternativa que pode ser implementada diretamente em apps colaborativos existentes

---

Collaborative Text Editing without CRDTs or OT

Apresentação do problema

• A edição colaborativa de texto é uma funcionalidade muito difícil de implementar, especialmente em edição simultânea, quando ocorre o problema de distorção dos índices de texto (index rebasing)
• As abordagens tradicionais, CRDT (tipos de dados replicados sem conflito) e OT (transformação operacional), se baseiam cada uma em modelos matemáticos complexos
  • CRDT: rastreia cada caractere por ID e usa ordenação baseada em árvore
  • OT: reajusta dinamicamente os índices para refletir a entrada de outros usuários
• Ambas as abordagens dependem fortemente de bibliotecas e dificultam customizações específicas para cada desenvolvedor

Nova abordagem

Ideia central

• Cada caractere recebe um ID único (UUID), e o cliente envia ao servidor um comando do tipo “insira tal caractere depois de tal ID”
• Exemplo: "insert ' the' after f1bdb70a" → f1bdb70a é o ID do caractere usado como referência para a inserção
• O servidor interpreta isso literalmente e insere o conteúdo, evitando conflitos

Tratamento de exclusão

• Mesmo quando um caractere é excluído, seu ID permanece na lista interna e é tratado com a flag isDeleted
• Ele não aparece no texto visível ao usuário, mas continua referenciável para operações futuras

Processamento no cliente e atualizações otimistas

• O usuário precisa ver o resultado logo após digitar, então a alteração é aplicada localmente antes da resposta do servidor (atualização otimista)
• Com a estratégia de reconciliação do servidor:
  1. Todas as operações locais ainda não confirmadas são desfeitas
  2. As operações do servidor são aplicadas
  3. Em seguida, as operações locais são reaplicadas para garantir o estado final sincronizado

Diferenças em relação às abordagens existentes

• O CRDT embute algoritmos de ordenação automática de IDs, enquanto esta abordagem envia ao servidor apenas a posição de inserção explícita
• Como resultado, ela é mais simples e garante um comportamento mais claro e previsível

Tratamento de inserções simultâneas

• Exemplo: em “My name is”, dois usuários inserem simultaneamente “ Charlie” e “ Dave” na mesma posição
  • Dependendo da ordem em que o servidor recebe, o resultado vira “My name is Dave Charlie”
• Isso é considerado um comportamento natural, e evita o fenômeno de interleaving no nível de caracteres que aparece em alguns CRDTs

Suporte a operações flexíveis

• Além de insert/delete básicos, é possível suportar várias outras operações:
  • insert-before
  • inserção sob condição específica (adicionar “u” somente se “color” existir)
  • reajuste de posição em drag & drop, entre outras
• Essa flexibilidade significa que a abordagem não fica presa a propriedades matemáticas pré-definidas

Suporte a rich text

• É possível aplicar formatação definindo intervalos com base em IDs (“bold do ID X ao ID Y”, por exemplo)
• Ao integrar com editores como ProseMirror, os conflitos podem ser resolvidos de forma simples
• A estrutura básica permanece a mesma, permitindo adicionar recursos de rich text

Versão descentralizada (Decentralized)

• Mesmo sem servidor central, se a ordem das operações for definida com base em timestamps de Lamport, o método pode funcionar da mesma forma
• Nesse caso, os resultados se aproximam dos de CRDTs como RGA, Peritext e Fugue
• Mesmo sem árvore ou provas matemáticas, ainda é possível atingir consistência em nível comparável ao de CRDTs

Biblioteca auxiliar: Articulated

• Uma biblioteca para lidar com eficiência com estruturas no formato Array<{ id, isDeleted }>
• Em vez de UUID, usa a estrutura { bunchId, counter } para otimização de memória
• Estrutura baseada em B+Tree para busca rápida de IDs e suporte eficiente a inserções
• Como estrutura de dados persistente (persistent), combina bem com a reconciliação no servidor

Conclusão

• Em comparação com CRDT/OT, esta abordagem é mais fácil de entender e pode ser implementada diretamente
• Ela permite aplicar com liberdade vários recursos de edição, permissões, restrições e formatação, sendo vantajosa para implementar editores colaborativos no mundo real
• A biblioteca Articulated é oferecida como uma ferramenta para tornar essa abordagem prática

[GN⁺]

Opiniões no Hacker News

• Esse algoritmo parece bem interessante. Explica uma abordagem em que cada caractere recebe um ID globalmente único (por exemplo, UUID), para que possa ser referenciado de forma consistente a qualquer momento; o cliente informa ao servidor que quer inserir um caractere após um ID específico, e o servidor processa a inserção naquela posição; exclusões só são ocultadas da tela e continuam preservadas internamente para referência de posição; também imagina que esse método poderia ser aplicado não só à edição de texto, mas a outras áreas, como sincronização de mundos de jogo

  • Isso parece ser, essencialmente, um CRDT simplificado; a forma de desempate e o uso de um servidor central lembram a arquitetura da época do Google Wave
  • Levantam a dúvida se o que foi descrito não é justamente um CRDT
  • Reação de que, na verdade, não há nada de tão novo assim: usar um processo central ao serializar um sistema distribuído é uma abordagem tradicional, e problemas como partição de rede (CAP etc.) ou ponto único de falha continuam existindo; acrescentam que gostariam de saber se o artigo discute desempenho
  • Piada desejando boa sorte com operações de seleção/cópia/colagem em massa, como ctrl+a, ctrl+x e ctrl+v

• Compartilham a visão de que a diferença em relação a CRDTs está em o servidor central assumir o papel de sincronização, como ordenação de sequência, sem precisar impor previamente uma ordem fixa à estrutura de dados; como só existe comunicação entre cliente e servidor, o servidor pode processar todas as operações locais do cliente antes de enviar atualizações remotas

• Opinião de que é surpreendente não haver discussão sobre outras estruturas de dados, como dict/map, ou arrays de tipos arbitrários; na prática, os apps precisam mais de estruturas colaborativas variadas do que de edição colaborativa de texto puro; há exemplos interessantes como validação de dados, carregamento parcial e operações de nível mais alto, mas consideram que a ausência desses recursos em coisas como Yjs talvez não seja por causa do próprio CRDT, e sim porque esses recursos já são difíceis de implementar por natureza

  • Concordam profundamente com a discussão sobre múltiplas estruturas de dados: ao criar um array de objetos “atômicos”, se não for possível alterar propriedades do objeto, então basta trocar o tipo em vez da string, e mudanças internas do objeto seriam apenas um problema um pouco mais complexo de navegação/armazenamento em árvore; também comentam que esperam que, do lado do usuário de bibliotecas auxiliares, seja possível conectar uma lógica própria de “modelo semântico” como hooks para evitar estados inválidos (por exemplo, um todo com isDone: true e ao mesmo tempo state: inProgress), em um contexto parecido com a formatação de rich text mencionada no texto linkado

  • CRDTs fazem merge escolhendo um dos lados de maneira consistente quando há conflito, mas o problema é que o resultado pode causar perda de dados ou gerar dados inválidos; seria como imaginar um conflito de merge no git sendo sempre resolvido escolhendo apenas um dos lados, o que na maioria dos casos produziria resultado incorreto ou erro de compilação; apontam que, só com resolução automatizada, a originalidade e o significado dos dados podem não ser preservados adequadamente, e acham que esse é um dos motivos de CRDTs ainda não serem amplamente usados

• Disseram que acharam divertido ler o texto explicando essa abordagem; também já usaram algo parecido há muito tempo e acham curioso que quase não seja mencionado na academia; afirmam que conseguiram implementar isso como um CRDT em um ambiente descentralizado, preservando propriedades como associatividade, imutabilidade e comutatividade

  • Perguntam, se isso foi desenvolvido como alternativa a CRDTs, qual foi o ganho real obtido

• Tentativa de resumir a mensagem principal do texto como: CRDT/OT complexos só são realmente necessários quando não há servidor central

  • Mesmo sem servidor central, opinam que é possível evitar a complexidade de CRDT/OT se houver um modo distribuído de concordar e aplicar uma ordem global das operações; apresentam um texto linkado; claro, isso ainda é uma forma de CRDT (num sentido mais geral), mas enfatizam que implementar undo/replay não é nada trivial e que vale considerar isso como alternativa quando CRDT/OT tradicionais parecem complexos demais

  • Mencionam que OT (Operational Transformation) exige um servidor central

• Essencialmente, também se enquadra como CRDT, mas com a diferença de que um servidor central determina a ordem das operações aplicadas ao documento; Google Docs e Zoho Writer também usam OT + servidor central; reconhecem que a abordagem proposta tem estilo de CRDT, mas na prática é mais útil para serviços baseados em servidor central

• Opinião de que a principal diferença em relação a CRDTs como o Automerge está na forma de coordenação pelo servidor; o Automerge ordena inserções concorrentes com uma ordem definida por número de sequência e ID do agente, enquanto a abordagem do texto processa na ordem de chegada ao servidor; citam a explicação do artigo referenciado: “não são necessários vários algoritmos fancy, então fica simplificado”; para muitos serviços, como de qualquer forma já se usará um servidor central, isso parece prático, mas como é preciso fazer undo/replay de edições locais durante a coordenação pelo servidor, não têm certeza de quanto isso realmente simplifica

  • Comentam que “rewind/replay” também parece uma abordagem fancy, e que uma Persistent B+Tree também não é exatamente simples

  • Explicam que o Automerge até consegue construir uma ordem total internamente, mas na prática trata operações de texto no estilo de CRDTs tradicionais (como RGA), justamente porque undo/replay não é simples

• Passa a sensação de ser um CRDT não otimizado; brincam se não seria algo como configurar max set size=1 e sair usando

  • Em resposta, alguém diz que justamente reduzir esse processo de complexidade torna a abordagem atraente por ficar mais próxima do que realmente acontece; mesmo sem otimização, ela tem seu apelo

• Se for usada reconciliação no servidor, há o risco de o problema de merge ficar difícil no lado do cliente; perguntam como manter a UX do editor fluida quando atualizações do servidor chegam em sequência — por exemplo, se uma requisição de inserção falhar, ela é reenviada? E se nesse meio-tempo outras atualizações chegarem, o que fazer? Como solução proposta, sugerem rebobinar o histórico de edição e reaplicar ou então esperar e esvaziar a fila; do ponto de vista de frontend, parece haver vários casos de borda de UI/UX não explicitados, e por isso CRDT talvez possa até ser mais simples; especialmente em ambientes com conexão instável (por exemplo, no metrô), gostariam de saber como fica a experiência do usuário

  • Explicam que ProseMirror e o CodeMirror moderno gerenciam mudanças de documento em unidades de step e atualizam as informações de posição (position map) em cada etapa, estruturando os dados para que as etapas do buffer possam ser aplicadas ao documento; enfatizam que isso funciona bem na prática em edição colaborativa e compartilham um link de referência

• Alguém sugere testar se um LLM (por exemplo, um modelo 4b etc.) poderia resolver conflitos de merge além de casos simples sem usar CRDT ou OT complexos; embora a eficiência energética possa ser ruim, talvez funcione surpreendentemente bem

  • No conflito do exemplo, em que tanto “Charlie” quanto “Dave” são inseridos após "is" em "My name is", questionam como exatamente o LLM faria o merge