- Em apps colaborativos baseados em servidor central, editar texto por índice de array faz as posições deslizarem durante edições simultâneas, então o estado no servidor é atualizado atribuindo um ID globalmente único a cada caractere e inserindo “depois de um ID específico”
- CRDT e OT, usados em serviços reais, são poderosos, mas algoritmos de ordenação total e regras de transformação de operações são complexos, o que dificulta adaptar o funcionamento interno às necessidades do app
- A abordagem proposta faz cliente e servidor manterem uma lista de IDs no formato
Array<{ id: ID; char?: string; isDeleted: boolean }> e deixa os caracteres excluídos como tombstones, para que referências de posição de inserção não quebrem depois
- Atualizações locais otimistas são tratadas com reconciliação com o servidor (server reconciliation): ao receber operações remotas, desfaz-se temporariamente as operações locais pendentes e reaplicam-se, em ordem, a operação remota e as operações locais ainda não confirmadas
- O texto também aborda ordem de inserções simultâneas, formatação rich text, variações distribuídas e a biblioteca
Articulated, mostrando que o servidor pode definir operações flexíveis além de inserção e exclusão, de acordo com a semântica do app
Por que a edição baseada em índice quebra com edições simultâneas
- Em edição colaborativa de texto, o cliente envia ao servidor as operações feitas pelo usuário, e o servidor precisa atualizar seu estado autoritativo
- Se o texto for tratado como um array de caracteres e forem enviadas operações como
inserir " the" no índice 17, inserções de outros usuários antes da chegada ao servidor podem fazer esse mesmo índice apontar para outra posição
- Por exemplo, se Alice inserir
" gray" mais à frente no começo do texto, o índice 17 de Bob já não será mais a posição original
- O servidor precisa rebasear a operação de Bob para
índice 22
- A questão central é: que operação o cliente deve enviar ao servidor, e como o servidor deve interpretá-la para atualizar o texto de forma “claramente correta”
- Esse problema de rebase de índice aparece não só em apps de colaboração em tempo real como Google Docs, mas também em formulários web que inserem itens em listas e até em apps locais de thread única que lidam com comentários inline ou histórico de edição
Onde CRDT e OT pesam na prática
- As soluções tradicionais se dividem, em geral, entre CRDT e OT
- CRDT atribui a cada caractere um ID imutável ou uma “position”, e ordena esses IDs com uma ordenação total matemática, como uma travessia especial de árvore
- OT transforma as próprias operações levando em conta edições simultâneas; no exemplo, muda
inserir no índice 17 para inserir no índice 22
- As duas abordagens já são usadas em produção
- O Google Docs usa OT
- A biblioteca CRDT Yjs é usada em vários apps
- O peso vem da complexidade conceitual
- A ordenação total em CRDTs de edição de texto costuma ser um algoritmo sutil definido em artigos acadêmicos
- Algoritmos de OT precisam satisfazer “propriedades de transformação” algébricas, os casos crescem quadraticamente e, sem verificação formal, bugs são frequentes
- Algoritmos complexos também tornam a implementação complexa, e normalmente você acaba usando bibliotecas feitas por especialistas como uma caixa-preta de rede
- Quando surge uma necessidade que a biblioteca não previu, a estrutura monolítica vira obstáculo
- Manter em memória só a parte necessária de um documento grande e deixar o resto em disco
- Fazer o servidor impor permissões em subdocumentos, como permissão de edição por parágrafo ou de uso de certos formatos
- Mostrar alterações sugeridas no estilo Google Docs dentro do texto ou ao lado dele
- Armazenar texto em uma representação fácil de sincronizar com um key-value store como o Replicache
- Suportar operações além de inserir/excluir, como mover texto, manipular a árvore do documento ou dividir/unir parágrafos
IDs de caracteres e a abordagem de “insert after”
- A ideia básica é usar IDs globalmente únicos em cada caractere em vez de índices de array
- A estrutura de dados principal tem o formato
Array<{ id: ID; char: string }>
- Em vez de
inserir no índice 17, o cliente envia ao servidor algo como inserir " the" depois de f1bdb70a
- O servidor encontra o ID-alvo e coloca os novos caracteres logo depois dele
- Os IDs dos novos caracteres também precisam ser definidos pelo cliente
- Ex.:
inserir " the" depois de f1bdb70a com ids [...]
- Se o cliente gera os IDs, pode referenciar esses novos IDs em operações posteriores de
insert after antes mesmo de receber resposta do servidor
- Se caracteres excluídos forem removidos por completo, a posição de inserção pode se perder
- Se Bob quiser inserir depois de
26085702 enquanto outro usuário apaga o caractere 26085702, o servidor não saberá mais onde inserir
- O servidor precisa manter os IDs excluídos na lista interna
- A representação corrigida do estado fica assim
Array<{ id: ID; char?: string; isDeleted: boolean }>
- O texto visível ao usuário pode ser montado concatenando apenas os itens não excluídos
list.filter(elt => !elt.isDeleted).map(elt => elt.char).join('')
Tratando inserções e exclusões
- Ao digitar um caractere, o comportamento de cliente e servidor é simples
- O cliente encontra
before, o ID do caractere imediatamente anterior ao ponto de inserção
- Gera para o novo caractere um ID globalmente único
id, como um UUID
- Envia ao servidor uma operação para inserir
char com o id depois de before
- O servidor encontra
before, incluindo itens excluídos, e insere { id, char, isDeleted: false } logo depois
- A exclusão de caracteres também é baseada em ID
- O cliente encontra o
id do caractere a ser excluído
- Envia ao servidor uma operação para excluir o item com aquele ID
- O servidor encontra o item e, se ele ainda não foi excluído, define
entry.isDeleted = true
- Essa abordagem resolve diretamente o problema de posicionamento das operações de edição enviadas ao servidor, sem seguir artigos de CRDT ou OT
- Uma implementação ingênua com array pode ser ineficiente, já que precisaria armazenar um UUID por caractere; as otimizações são tratadas em
Articulated
Atualizações otimistas e reconciliação com o servidor
- Em edição colaborativa no estilo Google Docs, o usuário precisa ver imediatamente o resultado do que digita, sem esperar resposta do servidor
- O ponto difícil é quando o cliente ainda tem operações locais pendentes que o servidor não aprovou, e nesse meio tempo recebe do servidor operações remotas concorrentes
- Nesse caso, CRDT não é obrigatório; dá para resolver com reconciliação com o servidor (server reconciliation)
- Desfazer todas as operações locais pendentes e rebobinar o estado do cliente para a perspectiva do estado anterior do servidor
- Aplicar a operação remota e alinhar o cliente ao estado do servidor
- Reaplicar as operações locais ainda não confirmadas
- Uma estratégia mais simples é o Wait for Ack, que proíbe processar operações remotas enquanto houver operações locais pendentes
- O cliente de Bob pode ignorar a primeira mensagem do servidor até receber um estado que já inclua sua própria mensagem processada
- Se Bob continuar digitando ou houver muita latência de rede, o atraso pode crescer indefinidamente, tornando essa opção menos em tempo real que a reconciliação com o servidor
Como isso difere de CRDT
- A abordagem proposta compartilha algumas características com CRDT, como atribuir um ID por caractere e usar a marcação
isDeleted
- A diferença está em como a ordem é tratada
- Aqui, o cliente diz ao servidor
insira X depois de Y, e o servidor faz isso literalmente ou de outro modo definido pelo desenvolvedor
- Em CRDTs de edição de texto, os IDs são ordenados por algoritmos complexos
- O principal elemento que diferencia vários CRDTs de texto entre si é justamente esse algoritmo de ordenação de IDs, e esta abordagem evita essa parte
O resultado de inserções simultâneas
- Quando vários usuários digitam ao mesmo tempo no mesmo lugar, o resultado é disposto na ordem inversa em que o servidor recebeu as operações
- Por exemplo, suponha que o texto seja
"My name is" e que Charlie digite " Charlie" e Dave digite " Dave" ao mesmo tempo
- Se a operação de Charlie chegar primeiro, o servidor produz
"My name is Charlie"
- Como a operação de Dave também insere depois do ID do
s em is, o resultado vira "My name is Dave Charlie"
- Operações de
insert after no mesmo ID-alvo ficam em ordem inversa de recebimento pelo servidor mesmo sem concorrência
- Ainda assim, palavras digitadas da esquerda para a direita não se embaralham no nível dos caracteres
- Mesmo que Dave envie cada caractere em uma operação separada,
a é inserido depois de D, v depois de a
- O estado no servidor evolui como
"My name is D Charlie" → "My name is Da Charlie" → "My name is Dav Charlie" → "My name is Dave Charlie"
- Em digitação da direita para a esquerda, se as operações de Charlie e Dave chegarem intercaladas ao servidor, o texto resultante também pode se intercalar
- Na prática, isso pode acontecer quando os dois estão online ao mesmo tempo e ignoram as edições em andamento um do outro
O servidor pode definir operações mais flexíveis
- Com reconciliação com o servidor, ele pode processar as operações do cliente praticamente da forma que quiser, e o cliente ainda assim acabará chegando ao mesmo estado
- Isso contrasta com CRDT e OT, que só permitem operações que obedecem regras algébricas estritas
- Para inserções simultâneas no mesmo lugar, o servidor pode responder de várias formas
- Ignorar a operação e tratá-la como no-op
- Adicionar o ID à lista interna, mas marcá-lo imediatamente como excluído, para que operações futuras de Dave ainda possam referenciar esse ID anterior
- Inserir o texto, mas aplicar uma formatação especial de revisão às duas palavras
- Transformar a edição de Dave em uma “sugestão” mostrada ao lado do texto principal
- Perguntar a um LLM como o texto deve ser ajustado
- O cliente também pode enviar operações que capturam melhor a intenção do usuário
insert before pode ser útil para criar um título acima de um parágrafo sem que ele acabe no meio de inserções simultâneas no fim do parágrafo anterior- Uma operação
fix typo pode carregar condições como insira u depois do o em color com ID X, mas apenas se a palavra ao redor ainda for color
- O servidor também pode definir operações cujo próprio local de inserção mude depois da chegada ao servidor
- Pode reordenar alfabeticamente inserções simultâneas no mesmo lugar
- Se adicionar uma operação
move para drag-and-drop, pode aplicar insert after dentro do texto movido, e não na posição original
Tratando formatação rich text
- Em rich text, entram formatos inline como negrito, tamanho da fonte e hyperlinks
- Formatação por intervalo também pode ser expressa com IDs de caractere em vez de índices
- Ex.:
aplicar bold do ID X ao ID Y
- Se for definido como
do ID X inclusive ao ID Y exclusive, inserções simultâneas no final do intervalo também podem ficar em negrito
- Em conjunto com um editor rich text como ProseMirror, o servidor pode localizar os índices atuais de array correspondentes aos IDs X e Y e instruir o estado local do ProseMirror a aplicar negrito nesse intervalo
- O ProseMirror pode então preservar o negrito também para texto inserido depois dentro dessa faixa
- Embora o servidor também possa tratar isso de outra forma, dependendo de operações de inserção como
bold set to false
- Para entender a semântica de rich text colaborativo, o ensaio Peritext essay é uma boa referência
Variação distribuída e a conexão com CRDT
- Até aqui, assume-se que um servidor central define a ordem total das operações pela ordem de recebimento e atualiza o estado autoritativo
- Em apps sem servidor central, ou em que o servidor é opcional, é possível atribuir uma ordem total final às operações de forma distribuída
- Por exemplo, ordenando operações com Lamport timestamps
- Cada cliente trata como estado autoritativo o resultado de processar em ordem as operações recebidas até ali
- Nesse caso, IDs por caractere e operações
insert after também funcionam em uma reconciliação distribuída “sem servidor”
- Tecnicamente, o resultado passa a ser um CRDT de edição de texto
- Porque se trata de um algoritmo distribuído de edição colaborativa de texto com consistência eventual
- Dependendo do esquema de ordenação usado, há conexões com CRDTs já existentes
- Se as operações forem ordenadas por Lamport timestamp, a ordem resultante da lista é equivalente a RGA / Causal Trees
- Se Lamport timestamp for combinado com operações de formatação, o comportamento fica bem parecido com o Peritext
- Se for usada ordenação topológica em profundidade, a ordem resultante da lista equivale ao Fugue
- Ainda não há uma prova detalhada por escrito dessa alegação de equivalência
Articulated: biblioteca auxiliar de implementação
- Em uma implementação real, o texto em si pode ficar armazenado em outro lugar, como em um estado do ProseMirror, e essa abordagem pode precisar apenas de uma lista de IDs neste formato
Array<{ id: ID; isDeleted: boolean }>
- Nessa lista, há quatro operações frequentes
- Converter entre IDs e o índice atual no array
- Inserir um novo ID depois de um ID específico
- Marcar um ID como excluído
- Serializar e restaurar o estado para persistência
- Um array simples não é adequado para isso
- As operações 1 a 3 levam tempo linear
- Como guarda um objeto e um UUID por caractere, consome bastante memória e espaço de armazenamento
- Articulated é uma pequena biblioteca npm que oferece a mesma funcionalidade desse array
- A estrutura principal,
IdList, usa otimizações parecidas com as de bibliotecas populares de CRDT para edição de texto
- Os IDs têm a forma
{ bunchId, counter }, em que bunchId é um UUID que pode ser compartilhado por vários IDs
- Quando IDs do mesmo bunch ficam lado a lado, como no caso comum de inserção da esquerda para a direita, eles são armazenados como um único objeto em memória e no estado serializado
- A estrutura principal não é um array, mas uma B+Tree, então as chamadas de método levam tempo
log ou log^2
IdList também é uma estrutura de dados persistente (persistent data structure)
- O cliente pode manter barato, ao mesmo tempo, o último estado recebido do servidor e o estado otimista
- Fica fácil fazer rollback para o último estado do servidor ao receber operações remotas
- Como material extra, há docs, demos iniciais e a implementação simples IdListSimple, com menos de 300 SLOC
IdListSimple omite as otimizações e a persistência, mas é funcionalmente equivalente e validado com fuzz tests
1 comentários
Opiniões no Hacker News
Bem elegante. O algoritmo anexa a cada caractere do texto um ID globalmente único, como um UUID, permitindo referenciá-lo de forma consistente ao longo do tempo em vez de usar índices de array que mudam continuamente
O cliente envia ao servidor uma operação “insert after” que referencia um ID existente, e o servidor encontra o ID de destino e insere o novo caractere logo depois. Exclusões apenas ocultam visualmente o caractere; ele continua armazenado para calcular posições de “insert after”. Parece ter potencial fora da edição de texto, por exemplo em sincronização de mundos de jogos
ctrl+a,ctrl+x,ctrl+v, é melhor torcer para dar sorteÉ bom ver um texto assim. Descobri o mesmo método alguns anos atrás e fiquei me perguntando por que ele quase não aparece na literatura acadêmica
Só que eu implementei isso como um CRDT em um contexto descentralizado, preservando propriedades como comutatividade, idempotência e associatividade
Achei surpreendente não haver menção a outras estruturas de dados, como dict/map ou arrays de tipos arbitrários. Seria bom se essas coisas também se expandissem facilmente. Pela minha experiência, apps precisam de estruturas de dados colaborativas com mais frequência do que de edição colaborativa de texto pura
Os exemplos de sincronização — validação de atualizações, carregamento parcial e operações de alto nível — são interessantes, mas não me parece muito convincente dizer que recursos assim não existem em algo como Yjs por causa da implementação CRDT subjacente, ou porque esses recursos seriam difíceis de criar desde o início
Nos termos do OP, sempre achei que o usuário de uma biblioteca auxiliar deveria poder inserir uma lógica leve de modelo semântico para impedir ou gerenciar estados inválidos. Por exemplo, um item de tarefa não pode ter
isDone: truee, ao mesmo tempo,state: inProgress. É parecido com a semântica de formatação de rich text mencionada no artigo linkadoImagine que todos os conflitos de merge do Git fossem resolvidos automaticamente escolhendo um dos lados. Na maioria das vezes o resultado seria errado e, às vezes, poderia até gerar código que não compila. Se não houver alguém ali para corrigir na hora, isso leva a resultados ainda mais confusos
Acho que é por isso que CRDTs não se disseminaram mais. CRDTs só consertam o “problema que você achava que tinha” e não resolvem o problema real: resolução de conflitos que preserve dados, validade e significado. Na verdade, dá até para dizer que pioram esse problema, porque restringem a resolução de conflitos a métodos que possam ser replicados de forma determinística
A diferença essencial em relação a CRDTs parece ser que, se há um servidor central, a sincronização — isto é, a definição da ordem entre eventos simultâneos — deve ser feita pelo servidor, e não pela estrutura de dados em si por meio de uma ordem lexicográfica
Como toda a comunicação acontece apenas entre cliente e servidor, e não entre clientes, quando um cliente se conecta ao servidor este pode garantir que processará primeiro todas as operações locais daquele cliente antes de enviar novas atualizações remotas
A mensagem central do artigo é que toda a complexidade de CRDT/OT só é necessária quando não há um servidor central?
Como outros comentários disseram, tecnicamente isso também é um CRDT, e uma forma bastante comum dele. Além disso, a própria implementação de desfazer e reproduzir operações não é trivial. Ainda assim, espero que seja mais simples do que usar CRDT/OT tradicional para cada tipo de dado
Não sou especialista nessa área, mas a principal diferença em relação a CRDTs como Automerge parece ser a coordenação pelo servidor. Por exemplo, este artigo [1] mostra que o Automerge usa números de sequência ao lidar com inserções simultâneas e, quando as inserções acontecem ao mesmo tempo, depende de uma ordem acordada de IDs de agentes. Já este método depende do servidor processar na ordem de chegada
O artigo diz: “em CRDTs de edição de texto, um algoritmo sofisticado define a ordem dos IDs. Esse algoritmo de ordenação é o que diferencia vários CRDTs de edição de texto e é a parte complexa dos artigos sobre CRDT. Nós evitamos isso completamente”. Como muitos apps já têm um servidor central de qualquer forma, faz sentido dizer que dá para evitar o “algoritmo sofisticado”. Mas a coordenação pelo servidor exige desfazer e reproduzir edições locais, então não tenho 100% de certeza de que isso seja muito mais simples. [1] https://josephg.com/blog/crdts-go-brrr/
Mas o Automerge não faz isso na prática; ele trata operações de texto com um CRDT tradicional, o RGA. Provavelmente, como você apontou, porque implementar desfazer e reproduzir operações não é fácil
Então é um CRDT não otimizado? Algo como definir o tamanho máximo do conjunto como 1 e seguir em frente?
Como usa coordenação pelo servidor, a coordenação no lado do cliente parece complicada. Como manter uma UX de editor fluida enquanto aplica cada atualização do servidor conforme ela chega?
Por exemplo, se uma solicitação de inserção de caractere enviada pelo cliente falhar, ele simplesmente tenta de novo? E se atualizações chegarem nesse meio-tempo? Edição: a seção “Client-Side” reconhece esse caso, sugere rebobinar e reproduzir, e também propõe uma alternativa mais simples: bloquear até que a fila pendente seja esvaziada. Do ponto de vista de frontend, exceções de UI/UX não especificadas podem se arrastar bastante, então, no geral, CRDTs talvez sejam mais simples. Também fico curioso sobre como seria a sensação de edição no metrô de Nova York, onde a conexão costuma cair
Na prática, funciona muito bem. Há mais detalhes aqui:
https://marijnhaverbeke.nl/blog/collaborative-editing.html
https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...