Editor colaborativo (Google Docs)

01 · CONTEXTO

Várias pessoas, um só documento

O exercício clássico pede um editor de documentos no navegador em que várias pessoas editam o mesmo documento ao mesmo tempo, veem as mudanças umas das outras em tempo real e enxergam o cursor e a presença dos demais. A Hello Interview assume um editor de texto simples e deixa fora a estrutura sofisticada de documento.

O desafio central, segundo o time do Google Docs, é garantir que todas as sessões de edição acabem convergindo para a mesma versão correta do documento. Como a rede não é instantânea, quem edita cria temporariamente uma versão local diferente da que os colaboradores veem.

A Hello Interview lista como aprofundamentos a escala de conexões WebSocket e o controle do armazenamento. Este caso foca na convergência das edições.

02 · COMPARAR VERSÕES

Por que comparar versões não basta

O antigo Google Docs, como muitos processadores de texto colaborativos, comparava versões: o servidor encontra as diferenças entre a sua versão e a recebida e decide como mesclá-las da melhor forma possível. Quem tem mudanças ainda não enviadas precisa comparar a versão do servidor com a sua e mesclar localmente.

1. Os dois partem do mesmo texto. John coloca em negrito as duas últimas palavras, enquanto Luiz troca a última por outra.

2. A mudança de John chega primeiro ao servidor, que a envia a Luiz.

3. Luiz, que só tem duas versões para comparar, não tem informação suficiente para saber qual é a mescla correta; várias combinações são formas válidas de mesclar as duas versões.

4. O resultado correto combina o estilo de John com a troca de Luiz, mas só comparar versões não permite garantir que a mesclagem saia como quem edita espera.

Uma alternativa seria travar parágrafos para que só um editor digite em cada um por vez, mas o blog do Google considera que não é uma boa solução: contorna o desafio técnico em vez de resolvê-lo e prejudica a experiência de edição colaborativa.

03 · LOG E OT

Um log de mudanças e a transformação operacional

O novo editor deixou de calcular mudanças comparando versões. O documento é guardado como uma série cronológica de mudanças, e a versão é obtida reproduzindo esse histórico. Toda edição se reduz a três tipos de mudança: inserir texto, apagar texto e aplicar estilos a um trecho. Editar é acrescentar uma mudança ao fim do log de revisões; para exibir o documento, reproduz-se o log desde o início.

Como se conhece a revisão de cada mudança, dá para checar o que o editor via ao fazê-la e mesclá-la corretamente com o que mudou desde então. Por isso, segundo o blog, a intenção de quem edita nunca é ambígua.

Enviar as mudanças aos outros editores não basta, porque as pessoas saem de sincronia. No exemplo do blog, Luiz tinha dois caracteres no começo do texto que John desconhecia; se aplicasse a primeira mudança de John sem ajuste, apagaria os caracteres errados. Luiz precisa transformar as mudanças de John para que fiquem relativas ao documento local dele. O algoritmo que cuida desses deslocamentos é a transformação operacional, a OT.

Se a OT for implementada corretamente, garante que, quando todos os editores recebem todas as mudanças, todos veem a mesma versão do documento. Nem toda dupla de mudanças conflita: um estilo transformado contra um estilo de outro tipo não conflita, e intervalos de estilo se expandem quando transformados contra inserções de texto.

04 · PROTOCOLO

Cliente, servidor e a ordem das mudanças

Mesclar bem é um problema; garantir que cada mudança seja mesclada com as outras quando muitas acontecem ao mesmo tempo é outro, tratado pelo protocolo de colaboração. Cada cliente separa as mudanças locais ainda não enviadas das enviadas mas ainda não confirmadas, e o servidor guarda o histórico completo das mudanças processadas, o log de revisões.

1. Luiz digita uma palavra no começo do documento. O cliente a coloca na lista de pendentes, envia ao servidor e a move para a lista de enviadas.

2. Luiz continua digitando, e John digita um ponto de exclamação na versão vazia dele. A nova mudança de Luiz não é enviada: o cliente nunca manda mais de uma mudança pendente por vez e mantém as novas na lista de pendentes até receber a confirmação da primeira.

3. O servidor guarda a primeira mudança de Luiz no log de revisões, envia essa mudança a John e confirma a Luiz que a processou.

4. O cliente de John usa OT para transformar a mudança de Luiz contra a mudança que ele ainda tem pendente. O resultado desloca a posição da mudança pendente de John para abrir espaço, no começo do documento, para a palavra de Luiz.

5. Quando a mudança de John chega ao servidor, ele já gravou uma revisão naquela posição do log. O servidor a transforma contra as mudanças confirmadas desde a última sincronização de John antes de gravá-la como a revisão seguinte.

6. No fim, o servidor e os dois editores veem o mesmo documento.

Segundo o blog, o protocolo torna a colaboração rápida, porque cada editor aplica as próprias mudanças de forma otimista, sem esperar a confirmação do servidor, e a velocidade ou a confiabilidade da conexão não influencia a velocidade de digitação. O servidor não precisa saber nada sobre o estado de cada cliente, e só ele conhece o histórico, enquanto só os clientes conhecem as mudanças não confirmadas.

05 · OT, CRDT E FIGMA

Alternativas: CRDT e o caminho do Figma

Um CRDT, tipo de dado replicado livre de conflitos, é uma estrutura replicada em várias máquinas em que a aplicação pode atualizar qualquer réplica de forma independente, concorrente e sem coordenação, e as réplicas têm garantia de convergir. O desenvolvimento dos CRDTs foi motivado inicialmente pela edição colaborativa de texto e pela computação móvel.

O Figma optou por não usar OT, o algoritmo padrão popularizado por apps como o Google Docs, e a considerou complexa demais para o problema dele. Para o time, a OT é ótima para editar textos longos com pouca memória e sobrecarga de desempenho, mas é muito complicada e difícil de implementar corretamente, e leva a uma explosão combinatória de estados difícil de raciocinar.

O Figma também não usa CRDTs puros: eles são projetados para sistemas descentralizados, sem uma autoridade central que decida o estado final, e como o servidor do Figma é essa autoridade, o time simplificou o sistema e removeu a sobrecarga extra.

1. Os clientes são páginas web que falam com o servidor por WebSocket. Ao abrir um documento, o cliente baixa uma cópia, e a partir daí as atualizações nos dois sentidos seguem pela conexão.

2. Cada documento multiusuário tem um processo próprio no servidor, ao qual todos que o editam se conectam.

3. O conflito só existe quando dois clientes mudam a mesma propriedade do mesmo objeto; nesse caso o documento fica com o último valor enviado ao servidor.

4. Comentários, usuários, times e projetos ficam no Postgres, fora do sistema multiusuário, e são sincronizados com os clientes por um sistema completamente separado.

O custo aparece no texto: se uma pessoa muda o valor B para AB enquanto outra muda para BC, o resultado é AB ou BC, nunca ABC. Para o Figma isso é aceitável, porque é uma ferramenta de design, não um editor de texto.

O Figma permite ficar offline por um tempo arbitrário: ao voltar, o cliente baixa uma cópia nova do documento e reaplica as edições offline sobre o estado mais recente. No cliente, as mudanças de propriedade são aplicadas imediatamente, sem esperar a confirmação do servidor.

06 · NA ENTREVISTA

Como organizar a resposta

Pontos a cobrir: os requisitos (edição concorrente, mudanças em tempo real, cursor e presença); como representar a edição, seja como log de mudanças, seja como mapa de propriedades; quem define a ordem final; como o cliente fica responsivo e o que acontece quando alguém volta de uma desconexão; e a escala de conexões e o armazenamento.