Design de sistema de edição colaborativa: OT vs CRDT, presença e sincronização

Duas pessoas digitam no mesmo parágrafo no mesmo instante. Em uma fração de segundo, as duas telas mostram o mesmo texto, e as palavras de ninguém sumiram. Fazer isso funcionar significa resolver um problema específico, edições concorrentes em um estado compartilhado, mais uma série de problemas comuns de infraestrutura: roteamento, persistência, presença e reconexão.

Este post projeta um editor colaborativo em tempo real: o problema de concorrência em um exemplo resolvido, transformação operacional (OT) e tipos de dados replicados livres de conflito (CRDTs) comparados, a abordagem em que o servidor tem a palavra final usada pelo Figma e a arquitetura em volta deles, com um diagrama.

O problema central, em cinco caracteres

Comece com o documento ABC. As posições contam a partir de zero.

• A Alice insere X na posição 1, e a tela dela fica com AXBC.
• No mesmo instante, o Bob apaga a posição 2, o C, e a tela dele fica com AB.

Agora cada cliente recebe a operação do outro e a aplica do jeito que veio:

• O Bob aplica “inserir X em 1” a AB e obtém AXB.
• A Alice aplica “apagar a posição 2” a AXBC, apaga o B e obtém AXC.

Os documentos divergiram, e a cópia da Alice perdeu um caractere que ninguém apagou. Todo editor colaborativo existe para evitar isso. Há duas famílias de soluções.

Transformação operacional

A OT mantém as operações como posições e transforma cada operação que chega em relação às operações concorrentes que ela não viu. O “apagar a posição 2” do Bob foi feito antes da inserção da Alice na posição 1, que desloca tudo o que vem depois uma casa para a direita. Transformado em relação à inserção, ele vira “apagar a posição 3”, e o AXBC da Alice vira AXB, igual ao do Bob.

Sistemas de OT em produção usam um servidor central para ordenar as operações, uma abordagem que remonta ao sistema Jupiter, de 1995, e que o Google Docs descreveu quando reconstruiu o editor em 2010:

1. Cada cliente envia as suas operações marcadas com a revisão do servidor em que se basearam.
2. O servidor transforma cada operação em relação a tudo o que aceitou desde aquela revisão, atribui o próximo número de revisão e transmite o resultado.
3. Cada cliente transforma as operações que chegam em relação às suas próprias, ainda não confirmadas.

Os pontos fortes da OT são operações compactas e um longo histórico com texto. O ponto fraco são as próprias funções de transformação: para texto rico, tabelas e estruturas aninhadas, acertar cada par de tipos de operação é notoriamente difícil, e o design depende de um servidor para definir a ordem.

CRDTs

Um CRDT é um tipo de dado projetado para que atualizações concorrentes possam ser aplicadas em qualquer ordem e, mesmo assim, todas as réplicas converjam; Shapiro e colegas o formalizaram em 2011. Em texto, cada caractere inserido recebe um identificador único e ordenado, como um ID de cliente e um contador, e uma inserção diz “depois do caractere com tal ID” em vez de “na posição 1”. As exclusões marcam os caracteres como removidos, deixando tombstones. Como as operações se referem a IDs estáveis, e não a posições que mudam, não há nada para transformar.

No exemplo, a inserção da Alice diz “X vem depois de A”, e a exclusão do Bob diz “remova C”. Aplicadas em qualquer ordem, as duas réplicas terminam com AXB.

Bibliotecas de CRDT como Yjs e Automerge tornam isso prático. Os pontos fortes: não é preciso uma ordem central, então edição offline e sincronização peer-to-peer funcionam naturalmente, e a mesclagem é possível a qualquer momento. Os custos: metadados extras por caractere, tombstones que precisam ser compactados e casos extremos em que o resultado mesclado é consistente, mas não é o que nenhum dos dois usuários pretendia. Um servidor continua útil para controle de acesso, persistência e fan-out; ele só não precisa decidir a ordem.

O meio-termo em que o servidor tem a palavra final

Nem todo editor edita texto longo. O Figma não escolheu nem OT clássica nem CRDTs de verdade: o servidor dele define a ordem dos eventos, os documentos são árvores de objetos com propriedades e, quando duas pessoas mudam a mesma propriedade do mesmo objeto, vence o último valor que o servidor recebe. Os servidores do Figma rodam um processo separado para cada documento multiplayer, e todos que editam aquele documento se conectam a ele. Para ferramentas de design, planilhas e quadros, em que os conflitos acontecem por propriedade, isso é mais simples que as duas alternativas.

A arquitetura

Qualquer que seja o algoritmo escolhido, o sistema em volta é parecido:

1. Os clientes se conectam por WebSocket a um serviço de colaboração e mantêm a conexão aberta enquanto o documento estiver aberto.
2. Um único servidor de sessão é dono de cada documento. Todos os clientes de doc-123 precisam chegar ao mesmo servidor, para que ele possa ordenar ou mesclar as edições em memória. Um diretório, por exemplo no Redis, mapeia documentos para servidores com um lease, e o balanceador de carga ou uma camada de roteamento manda as conexões para lá. Hashing consistente sobre o ID do documento também funciona, desde que dois servidores nunca possam acreditar ao mesmo tempo que são donos de um documento.
3. O servidor de sessão mantém o documento vivo em memória, aplica cada edição que chega e a transmite aos outros clientes.
4. Cada edição é anexada a um log de operações durável antes de o servidor confirmá-la. Um snapshot periódico do documento inteiro vai para o armazenamento de objetos, então carregar um documento significa ler o snapshot mais recente e as operações posteriores a ele.
5. As permissões são verificadas na conexão e em cada operação; a edição de um leitor é rejeitada, não apenas escondida.

Comentários, histórico de versões, busca e exportação são serviços separados que consomem o log de operações; eles não pertencem ao caminho de tempo real.

Presença é outro tipo de dado

Cursores, seleções e o “quem está aqui” mudam o tempo todo, só importam agora e não valem nada um minuto depois. Trate a presença como efêmera: transmita-a pelo mesmo servidor de sessão, limite-a a poucas atualizações por segundo por usuário, descarte-a quando um cliente se desconectar e nunca a grave no log de operações. O Yjs, por exemplo, mantém a presença em um canal de awareness separado, ao lado do estado do documento.

Edições offline e reconexão

Conexões caem o tempo todo, em trens e elevadores. O cliente guarda localmente as operações não confirmadas e as reenvia na reconexão:

• Com OT, o cliente envia as operações pendentes com a última revisão que viu; o servidor as transforma em relação a tudo o que veio depois.
• Com CRDTs, cliente e servidor trocam resumos compactos do que cada um já viu, muitas vezes chamados de vetores de estado (state vectors), e enviam um ao outro só as atualizações que faltam.

Longos períodos offline são onde os CRDTs brilham. Com OT, um cliente que ficou offline por um dia ainda consegue se reconectar, mas o servidor precisa transformar as operações dele em relação a um dia inteiro de operações.

Escala e falhas

• Documentos quentes. Um documento com milhares de leitores e poucos editores não deveria fazer o servidor de sessão empurrar sozinho cada tecla para milhares de sockets; distribua para os leitores por uma camada de pub/sub e agrupe as atualizações.
• Queda do servidor de sessão. Os clientes se reconectam, o lease do diretório expira, um novo servidor carrega o snapshot e o log de operações, e os clientes reenviam as operações pendentes. Confirmar só as edições gravadas de forma durável é o que torna isso sem perdas.
• Split brain. Dois servidores donos do mesmo documento aceitariam ordens conflitantes. Proteja a posse com o lease (fencing) e rejeite gravações de um servidor cujo lease expirou.
• Desfazer precisa desfazer a sua última alteração, não a do seu colega, então vira uma nova operação inversa, transformada ou mesclada como qualquer outra.

O diagrama de colaboração

Como ler:

• Dois clientes se conectam por WebSocket através do balanceador de carga.
• O diretório no Redis diz qual servidor de sessão é dono do doc-123; as duas conexões chegam ao servidor A.
• O servidor A ordena ou mescla as edições em memória e transmite edições e presença de volta aos dois clientes.
• Durabilidade: cada edição vai para o log de operações no Postgres antes de ser confirmada; os snapshots vão para o armazenamento de objetos.
• O provedor de identidade verifica o acesso quando os clientes se conectam; o servidor B é dono de outros documentos e mostra como o serviço escala horizontalmente.
• O bloco Markdown compara OT e CRDTs em três linhas.

Desenhar sistemas de tempo real com clareza

• Mostre quem é dono do quê. O fato mais importante aqui é que um servidor é dono de um documento; desenhe o diretório e o roteamento.
• Separe dados duráveis de dados efêmeros. Desenhe o log de operações e os snapshots, e rotule a presença como não persistida.
• Desenhe pelo menos dois clientes. A concorrência é o problema inteiro; um cliente só a esconde.
• Marque o ponto de confirmação: uma edição está segura assim que entra no log de operações.

Para conexões de longa duração e fan-out, o diagrama de arquitetura de app de chat cobre um terreno parecido. Rotear documentos para servidores aplica as ideias do diagrama de balanceador de carga, e o método geral está no exemplo de diagrama de design de sistemas.

Monte no Archboard

1. Entre com Google ou GitHub e crie um diagrama.
2. Adicione dois nós Dispositivo do pack Rede para os clientes e um Balanceador de carga na nuvem do pack Nuvem como entrada WebSocket.
3. Adicione uma Moldura do pack Básico para o serviço de colaboração, com dois nós Instância de computação dentro: o servidor de sessão A, dono do doc-123, e o servidor de sessão B.
4. Adicione um nó Redis do pack Dados para o diretório de documentos, um nó Postgres para o log de operações e um nó Armazenamento de objetos do pack Nuvem para os snapshots.
5. Adicione um Provedor de identidade do pack Segurança e ligue tudo com arestas rotuladas: WebSocket, edições e presença, append, snapshot, lease.
6. Adicione um bloco Markdown do pack Básico com o resumo de OT versus CRDT.

O exemplo usa 11 nós de diagrama e fica dentro do plano Free.

Perguntas frequentes

Qual é a diferença entre OT e CRDT? A OT transforma operações concorrentes umas em relação às outras, geralmente com um servidor definindo a ordem. Os CRDTs dão a cada elemento uma identidade estável, então as operações comutam e as réplicas convergem em qualquer ordem, sem ordenação central.

O Google Docs usa OT ou CRDTs? O Google descreveu a reescrita do editor em 2010 como baseada em transformação operacional, com um servidor ordenando as mudanças. Muitos editores mais novos usam bibliotecas de CRDT como Yjs ou Automerge.

Por que todos os editores de um documento precisam se conectar ao mesmo servidor? Esse servidor mantém o documento vivo e decide a ordem das edições. Se dois servidores aceitassem edições de um mesmo documento de forma independente, eles precisariam se coordenar a cada tecla.

Como a presença é armazenada? Na maior parte, não é. Cursores e seleções são transmitidos em tempo real, com limite de frequência, e descartados quando um cliente se desconecta. Persisti-los adiciona carga e nenhum valor.

Um editor colaborativo funciona offline? Sim. Os clientes enfileiram as operações localmente e sincronizam na reconexão. Os CRDTs lidam com longos períodos offline da forma mais natural; a OT também funciona, mas transforma mais operações na volta.

Comece grátis — um assento, sem cartão de crédito.