Mentiras sobre edição colaborativa, parte 1: algoritmos para edição offline

• A avaliação da Moment sobre edição colaborativa para seu editor de texto principal mostrou que algoritmos das famílias CRDT e OT podem produzir resultados de mesclagem que usuários perceberiam como corrupção de dados em conflitos diretos offline
• Mesmo em um caso simples em que Alice apaga a frase inteira e Bob altera Color para Colour, surgem resultados não intencionados por humanos, como o documento final ficar apenas com a letra u
• Nos casos de uso da Moment, cerca de 20% a 30% dos conflitos diretos testados foram inaceitáveis, e a empresa considerou difícil defender isso como experiência de produto devido à frequência e à reação negativa
• Yjs, ShareJS e Peritext promovem edição offline, colaboração com longos atrasos ou mesclagem automática de cópias independentes, mas os algoritmos não conseguem conhecer a intenção nem a ordem desejada pelos usuários e dependem de heurísticas
• A edição colaborativa offline é menos um problema puramente algorítmico e mais um problema de UI/UX, exigindo experiências de mesclagem que humanos possam ler e julgar, como a UI de merge do git ou o collaborative history da Ink & Switch

---

Limitações reveladas pela avaliação de edição colaborativa da Moment

• No início de 2024, a Moment começou a investigar um sistema de edição colaborativa para usar em seu editor de texto principal
• Vários algoritmos afirmam resolver não só a edição simultânea online, mas também o caso offline, no qual usuários editam offline por um período ilimitado e, ao voltar a ficar online, suas alterações são mescladas automaticamente
• Ao ler artigos e assistir a apresentações inicialmente, parecia que a comunidade de edição colaborativa havia chegado à “resposta certa” para o problema como um todo
• Durante a avaliação, algoritmos das famílias CRDT e OT resolveram conflitos diretos de edição de forma pouco intuitiva, e usuários interpretaram o resultado como corrupção de dados
• Como a edição offline aumenta muito a possibilidade de conflitos diretos, apenas esses algoritmos não bastavam para criar a experiência de edição offline que a Moment queria

Um exemplo simples de conflito entre exclusão e correção ortográfica

• Alice e Bob editam o mesmo documento enquanto estão offline
• O documento contém o texto The Color of Pomegranates
• Bob muda a grafia de Color para a forma britânica Colour, e Alice apaga todo o texto
• Quando os dois ficam online depois, as duas edições entram em conflito, e o sistema precisa conciliá-las sem saber qual edição veio primeiro
• Nesse caso, Alice e Bob acabam recebendo um documento que contém apenas a letra u
  • Isso não é uma frase válida nem uma palavra válida
  • Usuários interpretariam esse resultado como a Moment tendo corrompido seus dados

Resultados estranhos de conflitos diretos não são raros

• Esse conflito é trivial e direto, mas está dentro do escopo que algoritmos populares de edição colaborativa poderiam ser considerados capazes de suportar
• O resultado real foi um documento que uma pessoa não escreveria por conta própria, interpretado como corrupção de dados pelo produto da Moment
• Embora varie conforme o caso de uso, aproximadamente 20% a 30% dos conflitos diretos testados pela Moment produziram resultados difíceis de aceitar para casos de edição offline
• Considerando o feedback negativo e a frequência de ocorrência, a Moment concluiu que seria difícil explicar e defender esses resultados para os usuários

O suporte a edição offline prometido pelas ferramentas

• No início, ao ver esses resultados, a equipe pensou que talvez tivesse entendido mal o que essas ferramentas ofereciam
• No entanto, as descrições de cada projeto podem ser lidas como incluindo esse cenário no escopo suportado
  • Yjs declara no README que oferece suporte a offline editing
  • ShareJS afirma que é possível colaborar com qualquer latência, desde zero até algo do tamanho de férias longas
  • Peritext explica que usuários podem editar cópias independentes de um documento e mesclá-las automaticamente de uma forma que preserve a intenção do usuário tanto quanto possível
• A Moment ainda busca uma solução para esse problema, mas considera difícil conciliar a frequência e os tipos de erros observados na prática com essas afirmações

Limites fundamentais dos algoritmos sem coordenação

• À medida que a avaliação avançava, a equipe chegou à conclusão de que esses algoritmos não produziam o comportamento desejado pela Moment
• A pergunta restante era se isso poderia ser corrigido por meio de contribuições ou se era uma limitação fundamental dos algoritmos
• Há três motivos para considerar que o problema é fundamental
  • O algoritmo não conhece as intenções de Alice e Bob, nem pode perguntar por e-mail o que eles queriam ou permitir uma revisão como na UI de Pull Request do GitHub
  • Ele precisa aceitar a proposta de Alice de apagar tudo e a proposta de Bob de corrigir a grafia, decidindo o resultado por meio de heurísticas
  • Ele opera no nível de caracteres e oferece apenas garantias muito fracas sobre a saída
  • Alice e Bob poderiam ter decidido editar de outra forma se soubessem o que o outro estava fazendo
• Esses algoritmos também estão ligados ao problema de não conseguir seguir a ordem causal

Edição offline é mais um problema de UI/UX

• A Moment esperava que implementar algoritmos sofisticados permitisse oferecer edição offline verdadeira como consequência, mas a avaliação tornou difícil sustentar essa visão
• Era razoável que usuários vissem os resultados do algoritmo como corrupção de dados; os resultados estranhos fazem parte do próprio algoritmo e podem ocorrer com frequência suficiente para se tornarem um problema real
• Outra interpretação é que a edição colaborativa exige um investimento considerável em recursos de UI/UX
• Algoritmos não conseguem resolver o problema por completo, mas podem cumprir parte do papel na solução

UI de merge do git e direções de pesquisa

• Já existe uma UI de mesclagem de documentos amplamente adotada: o git
• A questão de pesquisa se aproxima de quão mais acessível, compreensível e automatizável essa experiência pode se tornar
• Por volta de 2009, havia muita discussão sobre os algoritmos que o git usa para mesclar alterações automaticamente
  • O git adotou o Myers O(ND) diff algorithm, usado principalmente por biólogos em análises de sequência do tipo BLAST
  • Bram Cohen considerou que os resultados de diff não eram intuitivos e criou o patience diff algorithm, que foi adotado pelo bzr, uma ferramenta concorrente do git que hoje está descontinuada
• Na época, a discussão se concentrava em criar diffs legíveis por humanos, mas a discussão atual está mais próxima de saber se algoritmos conseguem alcançar esse resultado sem intervenção humana
• Pesquisas que tratam a edição colaborativa como um problema de UI/UX estão em andamento, como o collaborative history da Ink & Switch

[GN⁺]

Comentários do Hacker News

• Sou o autor do Eg-walker e do ShareJS. Embora o texto pareça ter um tom contrário ao meu trabalho, na verdade concordo totalmente e venho dizendo a mesma coisa no HN há alguns anos
  As ferramentas atuais de colaboração em tempo real funcionam bem quando todo mundo está editando junto online, mas, se os usuários editarem offline ou em branches de longa duração, é preciso haver marcação de conflitos e uma opção de revisão manual na hora do merge. Especialmente em código
  Felizmente, algoritmos como o egwalker armazenam o histórico de edições em nível de caractere de todos os usuários e a ordem causal, ou seja, a ordem das alterações como em um DAG do Git, então têm muito mais informações do que o Git. Portanto, deveria ser possível criar um CRDT que detecte e marque regiões de conflito ao fazer merge de branches, permitindo que o usuário resolva manualmente
  Parece um problema algoritmicamente interessante, mas perfeitamente solucionável, e, curiosamente, quase ninguém parece ter tentado isso ainda na área de edição de texto. Se você quer fazer uma contribuição original e valiosa nessa área, esse é um pedaço importante que falta no ecossistema de CRDTs; eu gostaria que alguém tentasse
  [1] Na parte de baixo deste comentário: https://news.ycombinator.com/item?id=19889174

  • Fazendo isso, você acaba colocando conflitos como parte do modelo de dados. É uma forma curiosa de alcançar o C de CRDT, ou seja, “conflict-free”, mas é totalmente legítima e talvez seja a única maneira
    O próximo desafio interessante é quando surgem conflitos em torno da própria resolução de conflitos
  • Joseph, eu não quis dizer que seu trabalho é ruim. A intenção era ajudar profissionais a entenderem o que podem esperar e motivar problemas como os que mencionei no final
    Avaliar sistemas assim já é, por si só, um problema técnico difícil o bastante para que muitas equipes sofram com isso. Por isso, elas merecem conselhos práticos, e sinto que nós também gostaríamos de ter sabido disso antes
  • Sou cético quanto à possibilidade de uma solução algorítmica, mas parece algo que dá para tratar na camada de UX acima disso. Por exemplo, o cliente poderia detectar conflitos com base no histórico de edições e mostrar uma caixa de diálogo de resolução de conflitos que transforma o resultado da resolução em uma nova edição
    A parte difícil é marcar que o conflito foi resolvido. Talvez seja tão simples quanto adicionar um campo ao CRDT, mas aí não sei se isso deveria ser considerado uma solução algorítmica
    [1] https://josephg.com/blog/crdts-go-brrr/
  • O texto trata de casos de splices simultâneos sobrepostos, que são um caso de borda estranho e bem conhecido
    Se estivermos falando de edição de código de programa, a coisa vira um buraco de coelho muito mais profundo, porque se espera que o resultado do merge seja um programa válido. Ouvi dizer que houve um projeto na JetBrains tentando resolver isso com merge baseado em AST, mas, depois de irem muito mais fundo, concluíram que não valia a pena
  • Acho que edição “offline” é um problema humano e não pode ser resolvido com automação. As pessoas encontram maneiras de quebrar ou contornar automações e sistemas
    A única “edição offline” que eu permitiria em documentos usados por pessoas é adicionar comentários. Não edição, e nada de merge automático
    Para “edição offline” de código-fonte, que é alvo de automação, usamos Git; e o Git não finge resolver merges, apenas mostra as revisões. O merge é algo feito sob supervisão humana ou por automação especializada com sua melhor estimativa, e verificar se deu certo ainda exige revisão e testes

• Algoritmos mecânicos de merge podem se sair melhor ou pior dependendo do tipo de conflito, mas, no fim, nenhum CRDT consegue julgar se o texto mesclado é aquilo que o usuário queria dizer
  O artigo do Upwelling trata com mais detalhe da diferença entre o que, na escrita, eles chamam de conflitos semânticos e conflitos gramaticais: https://inkandswitch.com/upwelling/
  Sinto que colaboração séria, no fim, também é um problema de revisão de documentos. Isso é especialmente verdade em jornalismo ou publicação científica; em atas de reunião, talvez em geral dê para ignorar

  • Peter, obrigado pelo ótimo comentário. Espero que tenha ficado claro que boa parte do texto termina motivando diretamente o trabalho da Ink & Switch que mencionei no final
    Eu queria linkar o Upwelling também, mas não consegui lembrar o nome e, por causa do prazo, usei outro link no lugar

• Outro lado sombrio das implementações de CRDT é a carga de infraestrutura. Escrevi sobre isso em profundidade antes[0], e fiquei feliz ao ver que a Supabase também chegou às mesmas conclusões que meus resultados empíricos em um texto de alguns anos atrás sobre uma extensão CRDT para Postgres[1]
  Se você for usar CRDT, é melhor usar algo como Redis ou, embora só pensar no uso de memória já doa, usar MyRocks[2] ou uma base em RocksDB/LevelDB. Faça o que fizer, não coloque um RDBMS, especialmente Postgres, como backend
  [0]: https://news.ycombinator.com/item?id=40834759
  [1]: https://supabase.com/blog/postgres-crdt
  [2]: http://myrocks.io

  • Estou criando algo eu mesmo com Yjs + Postgres, então isso parece realmente útil. Talvez um dia me ajude a evitar uma grande crise

• A observação deste texto é precisa. CRDT é um excelente modelo formal para estruturas de dados distribuídas, mas a ideia de que todos os conflitos precisam ser resolvidos automaticamente — a própria noção de tipos de dados replicados livres de conflito, como o nome sugere — sempre me incomodou
  Como o texto mostra, vejo isso como uma tentativa sem futuro. O que é necessário é uma boa representação estrutural que permita compartilhar conflitos e resolvê-los de forma colaborativa, devolvendo o controle ao usuário e apoiando o processo de resolução. Um dos meus artigos favoritos, “Turning Conflicts into Collaboration” [1], trata dessa ideia de forma convincente
  Como parte da minha pesquisa de doutorado em andamento, desenvolvi “Lazy Merging: From a Potential of Universes to a Universe of Potentials” [2], um modelo formal de representação estrutural de conflitos baseado na teoria dos reticulados. Por acaso, ele também é um CRDT, mas não tenta resolver conflitos automaticamente; ele os representa dentro do documento colaborativo. Ao abordar isso matematicamente, consegui chegar a um modelo conceitual simples que garante propriedades fortes como completude, minimalidade e unicidade da mesclagem mesmo após conflitos existentes terem sido mesclados repetidamente, e o cálculo da mesclagem também é muito fácil
  [1] https://doi.org/10.1007/s10606-012-9172-4
  [2] https://doi.org/10.14279/tuj.eceasst.82.1226

  • Quando aprendi CRDT pela primeira vez, a sigla significava commutative replicated data types, ou seja, tipos de dados replicados comutativos. Também era assim nos artigos de Shapiro e outros; é mais difícil de pronunciar, mas prefiro essa versão
    Conflito é um conceito complexo e, embora “conflict-free” seja tecnicamente correto como descrição do resultado, pode gerar mal-entendidos, como se vê neste texto e no comentário acima
    Comutatividade é a propriedade de Bob aplicar as alterações na ordem [Bob, Alice] e Alice aplicá-las na ordem [Alice, Bob], e ambos ainda assim chegarem ao mesmo documento. Não significa que o documento seja “sem conflitos” em algum sentido significativo em um nível mais alto de abstração

• Acho que a ideia de várias entidades diferentes terem autoridade simultânea sobre um mesmo pedaço de dados, sem coordenação em tempo real, não tem uma solução geral. Essa é uma lição que já aprendemos em sistemas distribuídos, e fica bem evidente também neste texto quando pensamos em edição distribuída de documentos
  O mesmo princípio provavelmente se aplica a exemplos diversos como comandos duplos em uma cabine de avião, criação de filhos e outros que se possa imaginar

  • Dá para resolver, mas exige informações de contexto mais complexas, que muita gente acharia chato inserir. Por exemplo: “esta palavra que acabei de mudar só faz sentido como parte desta frase inteira, e essa frase inteira não é indispensável para o parágrafo inteiro”
    E chamar isso de “resolver” também é engraçado, porque neste momento uma grande parte do planeta parece achar que a saída caótica de LLMs pode ser algo próximo de decidir o resultado final da computação
  • É o teorema CAP de Brewer para armazenamento de dados distribuído. Você só pode ter duas destas três coisas: consistência, disponibilidade e tolerância a partições

• CRDT e OT, algoritmos comumente usados em edição colaborativa de texto, têm requisitos algébricos rigorosos sobre o que as operações de edição fazem e como interagem
  Portanto, mesmo que o servidor fosse inteligente o bastante para tratar o exemplo de “Colour” de uma forma razoável do ponto de vista de UX, seria muito difícil projetar o CRDT/OT correspondente para edição otimista no lado do cliente
  Dá para contornar isso se não usar CRDT/OT. Por exemplo, o servidor processa as operações na ordem em que as recebe e aplica a lógica de UX desejada, enquanto o cliente usa uma estratégia de rebase/previsão por cima disso para permitir edição otimista. Referência: https://doc.replicache.dev/concepts/how-it-works
  Aplicar isso à edição de texto também tem suas dificuldades, mas elas são separadas dos problemas de CRDT/OT discutidos aqui

  • Este comentário está muito subestimado, e concordo totalmente

• Acho que isso acontece porque os conceitos matemático, causal e entrópico de conflito acabaram se misturando com conflito semântico. Eu mesmo já cometi o mesmo erro no sentido oposto, e ouvi de forma bem direta que eu não sabia do que estava falando
  Quando se começa a considerar árvores, fica muito mais bagunçado. Por exemplo, o yJS opera sobre documentos JSON. Se a UI mostra apenas um nível raso e não expande níveis mais profundos, o usuário pode nem ver uma edição apagada
  A classe de CRDTs que preserva conflitos — se bem me lembro, o caso em que registradores podem ter vários valores — parece ser a mais promissora. O usuário deveria receber esses conflitos para avaliar, e eles poderiam até ser mostrados de forma totalmente visual. Permitir que o usuário percorra o histórico também parece uma alternativa prática para ajudá-lo a entender como algo estranho aconteceu, ou como sua própria alteração desapareceu

  • Um bom nome para esse tipo de CRDT seria “Git”
  • Nesse aspecto, Loro parece promissor. Ele está lidando ativamente com esse problema

• Lembro que o próprio Torvalds era bastante pessimista quanto ao que se podia alcançar com merge automático. E essa avaliação estava correta.
  Ele disse que o Git rejeitava a ideia de que um sistema de controle de versão pudesse, ou devesse, “resolver o problema de merge” fazendo com que um algoritmo suficientemente inteligente fizesse automaticamente a coisa certa.
  Concordo que edição offline é um problema de UI/UX. A causa mais profunda é o hábito da indústria de computação de seguir soluções antigas, e a crença de que, “como em geral um saco de 5 libras é mais fácil de manusear do que um saco de 10 libras, deve-se colocar 10 libras de coisas em um único saco de 5 libras”.
  A imagem básica de um “editor de texto” é uma textarea do Mosaic, o MacWrite, ou algo no meio disso, então normalmente se tenta acrescentar merge em cima disso com mudanças mínimas. Algo como um item de menu ou algumas opções em uma pequena caixa de diálogo. Mesmo quando há suporte a merge em GUI enterrado nos menus, ele fica no nível de um terror de diff/merge para programadores, ou se limita a uma visualização instável baseada em texto riscado, como pilotar um barco no nevoeiro.
  Mas, em um editor de texto com colaboração offline, o merge parcialmente manual é o centro do processo, e também deveria estar no centro do design do editor. Infelizmente, o MacWrite é um ótimo local do qual é difícil escapar.

  • Fica a pergunta: qual é a alternativa?
    Por exemplo, a próxima coisa que alguém que fala em “imitação cargo cult” e “soluções antigas” costuma dizer é “não edite código como texto; edite-o como árvore sintática”, mas o problema continua o mesmo. Basta trocar “caractere” por “sentença”.
    Se Bob adicionou uma linha ao ramo else de uma instrução if e Alice apagou a instrução inteira, incluindo o ramo else, o que um sistema inteligente deveria fazer?
  • Acho que escrevi de forma confusa sobre merge automático. O que eu queria dizer é que, quando vários commits alteram um arquivo, o Git tenta mesclá-los, mas conflitos diretos precisam obrigatoriamente ser mostrados.
    No geral, parece que concordamos que essa abordagem está certa.

• Aceito perguntas ou feedback. Vou ficar em reuniões por uma ou duas horas, mas gosto de falar sobre esse tipo de coisa. Pode enviar por aqui ou por e-mail, como preferir: [e-mail]

  • Se vocês mantiverem suporte offline, casos mais interessantes acabarão aparecendo. Por exemplo: “eu estava trabalhando nisso no avião sem Wi‑Fi, não gostei do rumo que estava tomando, fechei o notebook e tirei uma soneca. Depois, nos dias seguintes, trabalhei no documento no desktop. No fim de semana, abri o documento no notebook e todas as alterações feitas no avião entraram no documento, bagunçando tudo. Socorro, eu não queria fazer merge!”
    O Git não mistura automaticamente alterações locais sem consentimento explícito. O bzr provavelmente também nunca sonharia em fazer isso. Mas coisas como o Google Docs fazem isso de bom grado.
    O progresso até agora é ótimo, e espero que o programa de acesso antecipado vá bem.
  • Por que simplesmente não adotar um merge no estilo patch/diff? Se edição de texto colaborativa offline é descrita apenas como um problema de otimização de UX, então esse é um problema resolvido há décadas.

• Implementei differential sync(https://neil.fraser.name/writing/sync/). Fiz isso porque não entendi as outras opções e, para o app grugnotes.com, essa parecia a mais simples.
  O app é bem tosco e nem é totalmente em tempo real, mas o merge do exemplo é tratado corretamente, independentemente de quem volte a ficar online primeiro. Se a exclusão chegar online primeiro, a versão colour é descartada e nem é armazenada no histórico de edição.
  Deve haver mais problemas, e não sei o que acontece com mais de dois usuários, mas, para o meu caso de uso, estou satisfeito.