cola: tecnologia de CRDT de texto para edição colaborativa em tempo real

• cola é um CRDT de texto para edição colaborativa em tempo real escrito em Rust, com foco em fazer documentos editados simultaneamente por vários peers convergirem para o mesmo estado sem um coordenador central
• Em vez de fixar posições no documento por deslocamentos simples, usa Anchor no formato ReplicaId.n, evitando que o significado da posição se perca com edições simultâneas
• Conflitos de inserção são resolvidos de forma consistente com Lamport timestamp e ordenação por ReplicaId, enquanto exclusões são tratadas com tombstones e version vector em vez de remoção física
• Na implementação, usa RLE baseado em EditRun e uma G-tree representada por índices em Vec para buscar e inserir em tempo logarítmico dentro do modelo seguro de ownership do Rust
• Nos benchmarks, cola foi comparado com diamond-types, automerge e yrs; no upstream, foi de 1,4x a 2x mais rápido que diamond-types e também mostrou desempenho muito rápido no downstream

---

O problema de edição colaborativa que o cola aborda

• cola é um CRDT de texto escrito em Rust e projetado para que múltiplas réplicas convirjam para o mesmo estado em edição colaborativa em tempo real sem autoridade central
• Na camada de rede, assume apenas o mínimo: que toda edição eventualmente chegue a todos os peers
  • As edições podem ser enviadas várias vezes
  • As edições podem chegar em ordem arbitrária
  • Todos os peers devem eventualmente receber todas as edições
• O objetivo não é apenas que o estado do documento fique igual após receber todas as edições, mas também que o documento resultante faça sentido do ponto de vista do usuário

Fixando posições com Anchor em vez de offset

• Edições baseadas em offset como insert "abc" at offset 8 podem mudar de significado se outro peer editar simultaneamente uma região anterior, fazendo as réplicas divergirem
• O cola referencia posições no documento com identificadores estáveis, e não com conteúdo textual nem offsets
  • Cada peer atribui números crescentes aos caracteres que insere
  • Cada peer tem um identificador único chamado ReplicaId
  • O par ReplicaId.n se torna o identificador único de posição do caractere, chamado Anchor
• O valor n pode garantir unicidade com o incremento de um contador local, mas garantir unicidade global de ReplicaId sem servidor central é mais difícil
  • O cola parte do princípio de usar inteiros aleatórios grandes, como UUIDs, com probabilidade de colisão desprezível
• Inserções usam um único Anchor para indicar posição, e exclusões usam dois Anchors, de início e fim, para indicar intervalo

Ordenando conflitos de inserção na mesma sequência

• Quando várias inserções acontecem no mesmo Anchor, o cola define a ordem com Lamport timestamp
• O relógio de Lamport é atualizado pelas seguintes regras
  • Ao inserir texto localmente, o clock é incrementado em 1
  • Ao receber uma inserção remota, ele vira max(current, remote_timestamp) + 1
• Se uma inserção A foi criada em um contexto que já havia integrado a inserção B, então o Lamport timestamp de A será maior que o de B
• Inserções em conflito são ordenadas por Lamport timestamp em ordem decrescente
• Para inserções simultâneas com o mesmo Anchor e o mesmo Lamport timestamp, não existe uma ordem mais correta do ponto de vista do usuário, então o desempate é feito por ReplicaId em ordem crescente para manter consistência entre os peers

Exclusões com tombstones e version vector

• A exclusão converte offsets de início e fim em Anchors antes de propagá-los para outros peers
• Se dois peers apagarem simultaneamente a mesma região, o resultado será equivalente a apagar uma vez, desde que se desconsidere undo
  • Atualmente, o cola não suporta undo de exclusão
• O tratamento de exclusão tem três dificuldades
  • Se o texto apagado for removido completamente, Anchors de edições que ainda não chegaram podem cair dentro dessa região
  • Se uma exclusão remota for integrada cedo demais, o conteúdo visto pelo peer que criou a exclusão e o conteúdo do peer receptor podem diferir, fazendo as réplicas divergirem
  • Mesmo dentro do intervalo excluído, caracteres que o peer autor da exclusão ainda não tinha visto não devem ser apagados
• O primeiro problema é resolvido com tombstones
  • Caracteres apagados permanecem no documento, mas marcados como deletados
  • Isso aumenta o uso de memória
• Os demais problemas são resolvidos incluindo um version vector na mensagem de exclusão
  • A chave é ReplicaId, e o valor é o timestamp do último caractere visto por quem criou a exclusão naquele momento
  • O peer receptor espera para integrar a exclusão até que seu version vector seja pelo menos igual ao da mensagem de exclusão
  • Caracteres com timestamp maior que o do version vector da exclusão são ignorados no alvo da exclusão
• No cola, version vector é chamado de version map

Separação entre Replica e buffer de texto

• O estado local do documento de cada peer é representado no cola por Replica
• O algoritmo de CRDT do cola não precisa conhecer o conteúdo real da string
  • As funções da API não recebem strings como argumento
  • O cola lida apenas com blocos numéricos, não com o conteúdo do documento
• Esse desenho separa o mecanismo de CRDT da implementação real do buffer de texto

RLE e EditRun para reduzir metadados

• Como adicionar metadados a cada caractere dificulta uma implementação de alto desempenho, o cola agrupa blocos com timestamps consecutivos usando run-length encoding
• Por exemplo, colar a página inteira do Manhattan Project na Wikipedia pode ser representado como um único bloco, em vez de 107 mil blocos
• Mesmo ao digitar uma frase caractere por caractere sem mover o cursor nem apagar, não é necessário criar um bloco por tecla; tudo pode ser representado como um único run
• No cola, esses blocos contíguos são chamados de EditRun
  • Um EditRun, depois de quebrado uma vez, permanece fixo pelo resto da vida do documento e não é mais expandido
  • Um run que ainda não foi quebrado está no estado active
• Inserir texto no meio de um EditRun existente divide o run em dois e coloca o novo texto entre eles
• Ao apagar texto, a parte correspondente é separada do run e marcada como tombstone
  • Runs deletados também podem usar RLE, reduzindo o custo de memória dos tombstones

De linked list para B-tree

• O caminho upstream das edições locais é o processo de transformar edições baseadas em offset em edições que podem ser enviadas a outros peers
  • Tanto em inserções quanto em exclusões, é preciso encontrar o run que contém o offset para gerar um Anchor
  • Se necessário, o run é dividido em até 2 partes na inserção e até 3 na exclusão
• Em uma linked list, dividir o run é O(1), mas encontrar o run que contém o offset exige varrer desde o início, o que custa tempo linear
• Dá para acelerar edições repetidas na mesma posição fazendo cache do run active atual e do seu offset, mas o pior caso continua linear
• Para garantir pior caso logarítmico, o cola considera uma estrutura de B-tree
  • Os runs são representados como folhas da B-tree
  • Cada inode armazena seus filhos e a soma dos comprimentos deles
  • Runs tombstone contribuem com comprimento 0
  • O comprimento da raiz é igual ao comprimento total do documento
• Com a B-tree, busca e inserção podem ser feitas em O(log n), permitindo tratar edições locais em tempo logarítmico
• Porém, para converter de forma eficiente Anchor -> run em edições remotas, é preciso localizar a folha que contém o Anchor

G-tree: uma B-tree representada por índices em Vec

• Ter apenas ponteiros para folhas em uma B-tree comum dificulta saber, no processo de inserção top-down, como descer até a folha
• Operações bottom-up exigem ponteiros para o pai de cada nó e, dentro do modelo seguro de ownership do Rust, isso pode exigir estruturas como Rc<RefCell<_>>, tornando tudo mais lento e mais complexo
• O cola armazena todos os nós em um array dinâmico como Vec e representa referências entre nós com índices, não com ponteiros
  • O vetor é dono de todos os nós
  • Cada nó pode guardar o índice do pai
  • Isso permite navegação bidirecional sem código unsafe
• Essa estrutura depende da premissa de que os índices dos nós não mudam
  • Novos nós são adicionados no fim do vetor
  • Como o cola não remove runs e os marca como tombstone, não há problema de invalidar índices
• O cola chama essa árvore grow-only dentro de vetor de G-tree
• O código Rust da G-tree mantém a estrutura pai-filho de uma B-tree, mudando apenas sua representação em memória

Características de desempenho da G-tree

• A G-tree realiza busca e inserção top-down em tempo logarítmico, assim como uma B-tree
• O índice da folha no vetor, LeafIdx, pode ser usado como identificador estável da folha
• O run active atual pode ser armazenado em cache como LeafIdx, e não como ponteiro
  • Se houver edições repetidas na mesma posição do cursor, o run active pode ser expandido e apenas os comprimentos dos ancestrais até a raiz precisam ser atualizados
  • Isso pode ser feito sem percorrer a árvore nem alocar novos objetos, apenas com algumas comparações inteiras e de 2 a 4 somas inteiras
• A G-tree do cola usa branching factor 32, e os inodes têm ocupação média de cerca de 20 filhos
  • Com apenas 4 níveis, normalmente dá para armazenar cerca de 160 mil EditRun distintos
  • Depois de processar o trace de edição automerge-paper, a G-tree do cola fica com cerca de 15 mil EditRun
  • Esse trace contém 260 mil edições registradas ao longo de vários dias
• Como os nós da G-tree já ficam em memória linear, serialização e desserialização também se tornam simples

Convertendo Anchor em LeafIdx

• O caminho downstream das edições remotas é o processo de transformar edições baseadas em Anchor, como insert 2.3..7 at 1.2 e delete between 3.4 and 2.2, em edições locais baseadas em offset
• Como a G-tree pode ser percorrida para cima e para baixo, se o LeafIdx do run que contém um Anchor for conhecido, é possível calcular o offset correspondente
• O ponto central é a conversão Anchor -> LeafIdx
• Um desenho simples seria manter uma G-tree ou B-tree auxiliar cujas folhas armazenem ReplicaId, intervalo temporal e o LeafIdx da G-tree principal
  • As folhas ficam totalmente ordenadas por ReplicaId e intervalo temporal
  • É possível descer a árvore com base no Anchor e encontrar o LeafIdx desejado
  • Tanto busca quanto inserção são O(log n)
• O código-fonte real do cola não usa exatamente essa G-tree auxiliar
  • Na implementação real, busca e inserção são O(log f)
  • f é o número de fragmentos em que o EditRun que contém o Anchor foi dividido ao longo do tempo
  • f é sempre menor ou igual a n e normalmente muito menor

Maturidade atual e trabalho restante

• O desenho do cola fornece uma base voltada para convergência, preservação de intenção e desempenho
• Para ficar pronto para produção, ainda faltam suporte a undo/redo e alguns trabalhos adicionais

Benchmarks de CRDT em Rust

• O cola foi comparado com 3 CRDTs baseados em Rust
  • diamond-types
  • automerge
  • yrs
• Os benchmarks medem o tempo para processar traces reais de edição caractere por caractere
  • Usam a biblioteca de benchmarking para Rust criterion
  • Medem tanto upstream quanto downstream
  • O código dos benchmarks está em crdt-benches
• Os gráficos usam como linha de base 100x o desempenho do cola e não mostram resultados mais de 100 vezes mais lentos que ele
• O ambiente de execução foi um MacBook Pro 2018 com Intel Core i7 de 6 núcleos a 2,2 GHz
  • Em outras máquinas, os números podem mudar, mas o desempenho relativo deve ser parecido

Resultados dos benchmarks

• No upstream, yrs e automerge ultrapassam a linha de base
• No upstream, o cola é de 1,4x a 2x mais rápido que diamond-types
• No downstream, diamond-types travou em todos os traces, então não foi possível obter medições
  • Há a ressalva de que, se o uso da biblioteca estiver incorreto, os resultados serão atualizados
• No downstream, o cola é cerca de 2x mais lento que no passado
  • Isso era esperado, porque integrar edições remotas costuma ser mais caro do que gerar edições locais
• O cola roda em nível semelhante ou superior ao de bibliotecas rápidas de rope em ambas as direções e é avaliado como a implementação de CRDT de texto mais rápida no momento

[GN⁺]

Opiniões no Hacker News

• Ainda vejo a G-tree como uma B-tree com ponteiros para os pais adicionados.
  O fato de ela ser armazenada em um array é apenas uma questão de representação, não muda fundamentalmente a estrutura.
  Ela ainda armazena ponteiros, só que não em unidades de bytes, e sim em unidades do tamanho dos nós; e são posições relativas ao primeiro elemento do array, não ao início do espaço de endereçamento.
  Por exemplo, uma árvore binária completa armazenada em um array sem referências explícitas, em que os filhos do índice x ficam em 2x + 1 e 2x + 2, ainda é chamada de árvore binária; é apenas uma representação implícita.

  • Ainda assim, é útil falar sobre a forma de representação.
    Isso vale especialmente em linguagens que incentivam referências relativas e autogerenciadas em vez de referências absolutas.
    Uma das formas de representar árvores que achei interessante é armazenar os nós em um array plano na ordem de busca em profundidade.
    Se for somente leitura e o leitor de qualquer forma pretende percorrer em profundidade, pode ser bastante eficiente.
    Isso me lembra S-expressions e HTML.

• A menos que eu tenha deixado passar algo na API, isto não parece oferecer suporte a intervalos de formatação como negrito e itálico.
  Até onde sei, em algoritmos de CRDT para rich text, o estado da arte ainda é o Peritext https://www.inkandswitch.com/peritext/
  Seria bom se este projeto também incorporasse os recursos de rich text do algoritmo Peritext.

  • Como alguém que acompanha um pouco a área de CRDTs, sempre me perguntei se seria possível criar um CRDT de dados estruturados mais genérico.
    Seria uma forma de o usuário definir um modelo ou esquema que descreva estados semanticamente válidos.
    Por exemplo, se você simplesmente mesclar JSON, pode acabar com um estado sintaticamente válido, mas semanticamente sem sentido.
    Assim como o algoritmo Peritext sabe que negrito, itálico e sublinhado são operações aditivas, enquanto cor de destaque não é, seria bom se o usuário pudesse declarar no esquema que state: notStarted e completionDate: 2023-09-04 não podem coexistir.
  • Pergunta: o texto diz que o Cola lida apenas com edições sem conflito em tipos de dados desconhecidos e, na prática, só trata fluxo de caracteres e posições.
    Então não daria para representar a própria formatação dentro do texto, como em HTML?
    Não conheço muito bem outras representações de rich text, então não tenho certeza.
    Além disso, ao olhar o documento do Peritext linkado acima, vi que ele trata exatamente dessas dificuldades próprias de RTF, e achei a leitura bastante interessante.

• Há diferenças de desempenho ou recursos em comparação com Automerge ou Y.js/Yrs?

  • A “terceira parte” do texto começa com “benchmarkei o cola contra três outros CRDTs implementados em Rust: diamond-types, automerge e yrs”.
    Esta biblioteca cola parece ter uma vantagem considerável em velocidade de operações.
    Também fico curioso sobre o uso de memória.

• Não confundir com o trabalho de mesmo nome de Ian Piumarta.
  https://www.piumarta.com/software/cola/
  https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...

  • Ou também há os Cache Oblivious Lookahead Arrays, que já foram considerados uma alternativa ao MergeTree (LSM), mas hoje não são usados https://github.com/giannitedesco/cola
  • Também existe o coda.io, um app no estilo clone do Notion.

• É um trabalho bem feito, mas não parece um benchmark justo.
  Ele não calcula nem armazena as operações, e também não armazena o texto real.
  Para criar um CRDT de texto com suporte a atualizações delta em cima disso, o usuário teria de armazenar OpID => Text em uma estrutura separada, e esse custo não é baixo.

• Usando o crate slotmap (https://docs.rs/slotmap/latest/slotmap/), dá para oferecer suporte a exclusões sem se preocupar com deslocamento de índices ou com um “índice” passando a apontar para outro valor.
  No slotmap, isso é chamado de chave, e a chave também inclui um número de versão.

  • Será que isso também funcionaria no contexto de CRDT?
    Fico curioso porque ordenar é difícil e a versão talvez só tenha significado localmente.

• Estou pensando em testar isso em um projeto que o Etherpad e o Word não conseguiram dar conta.

• Supondo que todos os clientes conectados recebam todas as edições, não daria para colocar o hash esperado do estado atual do texto antes dos offsets e dos comandos de inserir/excluir/substituir?
  Isso quase garantiria que a edição só fosse aplicada ao estado adequado, e alterações posteriores poderiam ser acumuladas em um dicionário cuja chave fosse o “hash do estado dos dados em que se espera que sejam aplicadas”.
  Claro que o custo seria alto, porque seria preciso recalcular hashes sobre os mesmos dados, mas seria muito simples de entender e implementar.

  • Com essa abordagem, edições assíncronas nunca seriam aplicadas.
    Se eu faço uma edição local no documento e você faz uma edição remota, o hash do seu “estado esperado” nunca mais vai coincidir com o estado do meu documento.
    Isso porque eu já fiz uma alteração local.
    Para que um CRDT garanta convergência, é verdade que todos os clientes precisam receber todas as edições, mas a propriedade de não precisar aplicar as atualizações em uma ordem específica é importante em casos reais de uso distribuído.

• Fico curioso se existe uma forma fácil de ativar edição colaborativa de formulários no navegador.
  Seria bom se, quando duas pessoas abrissem a mesma página ou formulário, desse para ver qual campo de entrada a outra pessoa está editando no momento, e campos de entrada de texto usassem um CRDT de texto.
  Tentei implementar algo parecido com Yjs, mas foi bem difícil e não funcionou direito.

  • Fiquei curioso para saber por que Yjs não serviu.
    Parece perfeito para esse uso.