Edição colaborativa em JavaScript: Uma introdução à transformação operacional

Eu me propus a criar um editor de código colaborativo robusto para a Web. Ele se chama Codr e permite que os desenvolvedores trabalhem juntos em tempo real, como o Google Docs para código. Para os desenvolvedores da Web, o Codr funciona como uma superfície de trabalho reativa compartilhada em que cada alteração é renderizada instantaneamente para todos os visualizadores. Confira o recém-lançado Codr Campanha no Kickstarter para saber mais.

Um editor colaborativo permite que várias pessoas editem o mesmo documento simultaneamente e vejam as edições e alterações de seleção umas das outras à medida que ocorrem. A edição simultânea de texto permite uma colaboração envolvente e eficiente que, de outra forma, seria impossível. A criação do Codr me permitiu entender melhor e (espero) transmitir como criar um aplicativo colaborativo rápido e confiável.

O desafio

Se o senhor já criou um editor colaborativo ou conversou com alguém que já o fez, sabe que lidar com edições simultâneas em um ambiente multiusuário é um desafio. No entanto, acontece que alguns conceitos relativamente simples simplificam muito esse problema. A seguir, compartilharei o que aprendi a esse respeito durante a criação do Codr.

O principal desafio associado à edição colaborativa é controle de simultaneidade. O Codr usa um mecanismo de controle de simultaneidade baseado na Transformação Operacional (OT). Se o senhor quiser ler sobre a história e a teoria da OT, consulte o site página da wikipedia. Apresentarei um pouco da teoria a seguir, mas esta postagem tem o objetivo de ser um guia para implementadores e é mais prática do que abstrata.

O Codr foi criado em JavaScript e os exemplos de código estão em JavaScript. Uma lógica significativa precisa ser compartilhada entre o servidor e o cliente para dar suporte à edição colaborativa, portanto, um backend node/iojs é uma excelente opção. Para facilitar a leitura, os exemplos de código estão em ES6.

Uma abordagem ingênua para a edição colaborativa

Em um ambiente de latência zero, o senhor pode escrever um editor colaborativo como este:

Cliente

editor.on('edit', (operation) => 
    socket.send('edit', operation));
socket.on('edit', (operation) => 
    editor.applyEdit(operation));

Servidor

socket.on('edit', (operation) => {
    document.applyEdit(operation);
    getOtherSockets(socket).forEach((otherSocket) => 
        otherSocket.emit('edit', operation)
    );
});

Toda ação é conceituada como uma inserir ou excluir operação. Cada operação é:

1. Aplicado localmente no componente de edição
2. Enviado para o servidor
3. Aplicado a uma cópia do documento no lado do servidor
4. Transmitir para outros editores remotos
5. Aplicado localmente à cópia do documento de cada editor remoto

A latência quebra as coisas

No entanto, quando o senhor introduz a latência entre o cliente e o servidor, surge um problema. Como o senhor provavelmente já previu, a latência em um editor colaborativo introduz a possibilidade de conflitos de versão. Por exemplo:

Iniciando o estado do documento:

bcd

Usuário 1 inserções a no início do documento. A operação é parecida com a seguinte:

{
    type: 'insert',
    lines: ['a'],
    range: {
        start: { row: 0, column: 0}
        end: {row: 0, column: 1}
    }
}

Ao mesmo tempo, Usuário 2 tipos e no final do documento:

{
    type: 'insert',
    lines: ['e'],
    range: {
        start: { row: 0, column: 3}
        end: {row: 0, column: 4}
    }
}

O que deve acontecer é que Usuário 1 e Usuário 2 terminam com:

abcde

Na realidade, Usuário 1 vê:

bcd    <-- Starting Document State
abcd   <-- Apply local "insert 'a'" operation at offset 0
abced  <-- Apply remote "insert 'e'" operation at offset 3

E Usuário 2 vê:

bcd    <-- Starting Document State
bcde   <-- Apply local "insert 'e'" operation at offset 3
abcde  <-- Apply remote "insert 'a'" operation at offset 0

Ops! 'abced' != 'abcde' – o documento compartilhado está agora em um estado inconsistente.

A correção fácil é muito lenta

O conflito acima ocorre porque cada usuário está aplicando edições localmente de forma “otimista” sem antes garantir que ninguém mais esteja fazendo edições. Como Usuário 1 mudou o documento de lugar Usuário 2, ocorreu um conflito. Usuário 2pressupõe um estado do documento que não existe mais no momento em que é aplicado ao Usuário 1do documento do senhor.

Uma solução simples é mudar para um modelo de controle de simultaneidade pessimista em que cada cliente solicita um bloqueio de gravação exclusivo do servidor antes de aplicar atualizações localmente. Isso evita totalmente os conflitos. Infelizmente, o atraso resultante dessa abordagem em uma conexão média com a Internet tornaria o editor inutilizável.

Transformação operacional para o resgate

A Transformação Operacional (OT) é uma técnica para dar suporte à edição simultânea sem comprometer o desempenho. Com a OT, cada cliente atualiza de forma otimizada seu próprio documento localmente e a implementação da OT descobre como resolver conflitos automaticamente.

A OT determina que, quando aplicamos uma operação remota, primeiro “transformamos” a operação para compensar as edições conflitantes de outros usuários. Os objetivos são duplos:

1. Assegurar que todos os clientes terminem com estados de documentos consistentes
2. Garantir que a intenção de cada operação de edição seja preservada

No meu exemplo original, gostaríamos de transformar Usuário 2para inserir no deslocamento de caracteres 4 em vez de deslocamento 3 quando o aplicamos ao Usuário 1do usuário. Dessa forma, respeitamos o Usuário 2‘s intenção para inserir e após d e garantir que ambos os usuários terminem com o mesmo estado de documento.

Usando OT, Usuário 1 verá:

bcd    <-- Starting Document State
abcd   <-- Apply local "insert 'a'" operation at offset 0
abcde  <-- Apply TRANSFORMED "insert 'e'" operation at offset 4

E Usuário 2 verá:

bcd    <-- Starting Document State
bcde   <-- Apply local "insert 'e'" operation at offset 3
abcde  <-- Apply remote "insert 'a'" operation at offset 0

O ciclo de vida de uma operação

Uma maneira útil de visualizar como as edições são sincronizadas usando OT é pensar em um documento colaborativo como um repositório git:

1. As operações de edição são commits
2. O servidor é o ramo principal
3. Cada cliente é uma ramificação de tópico do mestre

Mesclando edições no mestre (lado do servidor)
Quando o senhor faz uma edição no Codr, ocorre o seguinte:

1. O cliente Codr se ramifica de mestre e aplica localmente sua edição
2. O cliente Codr faz um fusão solicitação ao servidor

Aqui está o adorável diagrama do git (ligeiramente adaptado). As letras fazem referência aos commits (operações):

Antes da fusão:

      A topic (client)
     /
    D---E---F master (server)

Após a fusão:

      A ------ topic
     /         \
    D---E---F---G master

Para fazer a mesclagem, o servidor atualiza (transforma) a operação A para que ela ainda faça sentido à luz das operações anteriores E e Fe, em seguida, aplica a operação transformada (G) ao mestre. A operação transformada é diretamente análoga a um commit de mesclagem do git.

Rebaixamento para o mestre (lado do cliente)
Depois que uma operação é transformada e aplicada no lado do servidor, ela é transmitida para os outros clientes. Quando um cliente recebe a alteração, ele faz o equivalente a um git rebase:

1. Reverte todas as operações locais “pendentes” (não mescladas)
2. Aplica a operação remota
3. Reaplica operações pendentes, transformando cada operação em relação à nova operação do servidor

Ao rebasear o cliente em vez de mesclar a operação remota como é feito no lado do servidor, o Codr garante que as edições sejam aplicadas na mesma ordem em todos os clientes.

Estabelecimento de uma ordem canônica de operações de edição

A ordem em que as operações de edição são aplicadas é importante. Imagine que dois usuários digitem os caracteres a e b simultaneamente no mesmo deslocamento de documento. A ordem em que as operações ocorrem determinará se o ab ou ba é mostrado. Como a latência é variável, não podemos saber com certeza em que ordem os eventos realmente ocorreram, mas, mesmo assim, é importante que todos os clientes concordem com o mesma ordenação dos eventos. O Codr trata a ordem em que os eventos chegam ao servidor como a ordem canônica.

O servidor armazena um número de versão para o documento, que é incrementado sempre que uma operação é aplicada. Quando o servidor recebe uma operação, ele marca a operação com o número da versão atual antes de transmiti-la aos outros clientes. O servidor também envia uma mensagem ao cliente que está iniciando a operação indicando a nova versão. Dessa forma, cada cliente sabe qual é a sua “versão do servidor”.

Sempre que um cliente envia uma operação para o servidor, ele também envia a versão atual do servidor do cliente. Isso informa ao servidor onde o cliente “ramificou”, para que o servidor saiba em quais operações anteriores a nova alteração precisa ser transformada.

Transformando uma operação

O núcleo da lógica de OT do Codr é esta função:

function transformOperation(operation1, operation2) {
    // Modify operation2 such that its intent is preserved
    // subsequent to intervening change operation1
}

Não vou entrar na lógica completa aqui, pois ela é muito complexa, mas aqui estão alguns exemplos:

1. Se op1 linha(s) inserida(s) antes de op2aumenta a linha do op2‘s, aumente o deslocamento da linha de acordo.

2. Se op1 texto inserido antes de op2 na mesma linha, aumente op2de acordo com o deslocamento de caracteres.

3. Se op1 ocorreu inteiramente após op2, então não faça nada.

4. Se op1 insere texto em um intervalo que op2 exclui e depois aumenta op2para incluir o texto inserido e adicionar o texto inserido. Observação: Outra abordagem seria dividir o op2 em duas ações de exclusão, uma em cada lado do op1preservando, assim, o texto inserido.

5. Se op1 e op2 são ambas operações de exclusão de intervalo e os intervalos se sobrepõem, então shrink op2para incluir somente o texto NÃO excluído por op1.

Sincronização da posição e da seleção do cursor

Uma seleção de usuário é simplesmente um intervalo de texto. Se o start e end pontos do intervalo são iguais, então o intervalo é um cursor recolhido. Quando a seleção do usuário é alterada, o cliente envia a nova seleção para o servidor e o servidor transmite a seleção para os outros clientes. Assim como nas operações de edição, o Codr transforma a seleção contra operações conflitantes de outros usuários. A lógica de transformação de uma seleção é simplesmente um subconjunto da lógica necessária para transformar um insert ou delete operação.

Desfazer/Refazer

O Codr dá a cada usuário sua própria pilha de desfazer. Isso é importante para uma boa experiência de edição: caso contrário, o usuário poderia pressionar CMD+Z poderia desfazer a edição de outra pessoa em uma parte diferente do documento.

Dar a cada usuário sua própria pilha de desfazer também requer OT. Na verdade, esse é um caso em que a TO seria necessária mesmo em um ambiente de latência zero. Imagine o seguinte cenário:

abc     <-- User 1 types "abc"
abcde   <-- User 2 types "de"
ce      <-- User 1 deletes "bcd"
??      <-- User 2 hits CMD+Z

Usuário2A última ação do senhor foi:

{
    type: 'insert',
    lines: ['de'],
    range: {
        start: { row: 0, column: 3}
        end: {row: 0, column: 5}
    }
}

A ação inversa (desfazer) seria:

{
    type: 'delete',
    lines: ['de'],
    range: {
        start: { row: 0, column: 3}
        end: {row: 0, column: 5}
    }
}

Mas obviamente não podemos simplesmente aplicar a ação inversa. Graças ao Usuário 1não há mais um deslocamento de caracteres 3 no documento!

Mais uma vez, podemos usar a OT:

var undoOperation = getInverseOperation(myLastOperation);
getOperationsAfterMyLastOperation().forEach((operation) => 
    transformOperation(operation, undoOperation);
);
editor.applyEdit(undoOperation);
socket.emit('edit', undoOperation);

Ao transformar a operação de desfazer contra operações subsequentes de outros clientes, o Codr aplicará a seguinte operação no desfazer, obtendo o comportamento desejado.

{
    type: 'delete',
    lines: ['e'],
    range: {
        start: { row: 0, column: 1}
        end: {row: 0, column: 2}
    }
}

Implementar o desfazer/refazer corretamente é um dos aspectos mais desafiadores da criação de um editor colaborativo. A solução completa é um pouco mais complexa do que a que descrevi acima, pois o senhor precisa desfazer inserções e exclusões contíguas como uma unidade. Como as operações que foram contíguos podem se tornar não contíguos devido a edições feitas por outros colaboradores, o que não é trivial. O que é legal, porém, é que podemos reutilizar a mesma OT usada para sincronizar edições para obter históricos de desfazer por usuário.

Conclusão

A OT é uma ferramenta poderosa que nos permite criar aplicativos colaborativos de alto desempenho com suporte para edição simultânea sem bloqueio. Espero que este resumo da implementação colaborativa do Codr seja um ponto de partida útil para entender a OT. Agradeço imensamente ao David pelo convite para que eu compartilhasse este artigo em seu blog.

Deseja saber mais sobre o Codr? Dê uma olhada na seção Campanha no KickStarter ou envie um tweet para @CodrEditor para solicitar um convite.