A resolução automática de conflitos em um ambiente com mais de um nó principal (neste artigo, um nó principal refere-se a um nó que aceita solicitações de alteração de dados) é uma área de pesquisa muito interessante. Existem várias abordagens e algoritmos diferentes, dependendo do aplicativo, e este artigo discutirá a tecnologia de Transformações Operacionais (OT) para resolver conflitos em aplicativos de edição colaborativa, como Google Docs e Etherpad.

1. Introdução

A colaboração é difícil do ponto de vista técnico, porque várias pessoas podem fazer alterações diferentes na mesma seção do texto quase nos mesmos momentos. Como a entrega de dados pela Internet não é instantânea (a velocidade de transferência de dados na fibra tem limitações), cada cliente trabalha com uma versão local (réplica) do documento editado para simular uma resposta instantânea, que pode diferir das versões de outros participantes. E o principal problema é garantir a consistência entre as versões locais, ou seja, como garantir que todas as versões locais converjam mais cedo ou mais tarde na mesma versão correta de um documento (não podemos exigir que todos os clientes alguns momentos tiveram simultaneamente a mesma versão, pois o processo de edição pode ser interminável).

Versão antiga do Google Docs

Inicialmente, o Google Docs, como muitos outros aplicativos de edição de documentos colaborativos, usava uma comparação simples do conteúdo de diferentes versões de um documento. Suponha que tenhamos dois clientes - Petya e Vasya, e o estado atual do documento esteja sincronizado entre eles. Na versão antiga do servidor do Google, ao receber uma atualização da Petya, calcula a diferença (diff) entre sua versão e a sua e tenta mesclar as duas versões em uma da melhor maneira possível. Em seguida, o servidor envia a versão recebida para o Vasya. Se o Vasya tiver alguma alteração não enviada ao servidor, o processo será repetido - você precisará mesclar a versão do servidor com o Vasina local e enviá-la de volta ao servidor.

Muitas vezes, essa abordagem não funciona muito bem. Por exemplo, suponha que Petya, Vasya e o servidor iniciem com um documento sincronizado com o texto " A raposa marrom rápida ".


Petya destaca as palavras raposa marrom em negrito, enquanto Vasya substitui a palavra raposa por cachorro . Deixe Petina mudar primeiro para o servidor e ele envia a versão atualizada do Vasya. Está claro que o resultado final deve ser O cão marrom rápido , mas não há informações suficientes para que os algoritmos de mesclagem compreendam isso, as opções O cão marrom raposa marrom , O cachorro marrom marrom , A raposa marrom marrom está absolutamente correto. (Por exemplo, no git, nesses casos, você terá um conflito de mesclagem e precisará governar com as mãos). Esse é o principal problema dessa abordagem - você não poderá ter certeza dos resultados da fusão se confiar apenas no conteúdo do documento.

Você pode tentar melhorar a situação e bloquear a capacidade de outros participantes de editar seções de texto que alguém já governa. Mas não é isso que queremos - essa abordagem simplesmente tenta evitar resolver um problema técnico, piorando a experiência do usuário, e também pode haver uma situação em que dois participantes começaram a editar a mesma frase ao mesmo tempo - e um deles perderá as alterações. ou ele terá que combinar manualmente as alterações no caso dos conflitos acima.

Nova versão do Google Docs

Na nova versão do Google Docs, foi utilizada uma abordagem completamente diferente: os documentos são armazenados como uma sequência de alterações e, em vez de comparar o conteúdo, rolamos as alterações na ordem (doravante denominada relação de ordem ). Sabendo como o usuário modificou o documento e levando em consideração suas intenções, podemos determinar corretamente a versão final depois de combinar todas as edições.

Ok, agora precisamos entender quando aplicar as alterações - precisamos de um protocolo de colaboração .

No Google Docs, todas as edições de documentos se resumem a três operações diferentes:

• Inserção de texto
• Excluir texto
• Aplicando estilos ao texto

Portanto, quando você edita um documento, todas as suas ações são armazenadas exatamente nesse conjunto de operações e adicionadas ao final do log de alterações. Quando o documento é exibido, o registro de alterações será executado usando as operações gravadas.

Uma pequena observação: o primeiro produto (público) do Google com suporte ao OT foi, aparentemente, o Google Wave. Ele apoiou uma gama muito maior de operações.

Exemplo

Que Petya e Vasya partam do mesmo estado de "HABR 2017".
Petya muda de 2017 para 2018, na verdade, cria 2 operações:


Ao mesmo tempo, Vasya altera o texto para "HELLO HABR 2017":


Vasya recebe a operação de Petin para excluir, se ele apenas a aplicar, o texto errado será obtido (o número 7 deveria ter sido excluído):


Para evitar isso, Vasya deve transformar a operação de Petin de acordo com as mudanças locais atuais (em outras palavras, as operações são sensíveis ao contexto):

$$

$$\ {Excluir \ \ @ 8 \} \ rightarrow \ {Excluir \ \ @ 15 \}$$

Falando um pouco mais formalmente, considere este exemplo:


Então:

$$

$$O1 '(O2 (X)) = O2' (O1 (X))$$

Voila! O algoritmo descrito é chamado Transformação Operacional.

2. Transformação Operacional

Modelo de Consistência

Para garantir consistência, vários modelos de consistência foram desenvolvidos, considere um deles - o CCI.

O modelo CCI fornece três propriedades:

1. Convergência: Todas as réplicas de um documento comum devem ser idênticas após a conclusão de todas as operações:
   
   
   
   Neste exemplo, os dois usuários começam com réplicas idênticas. Depois, eles alteram o documento e as réplicas divergem - dessa forma, o tempo mínimo de resposta é alcançado. Após enviar alterações locais para outros clientes, a propriedade convergence exige que o estado final do documento para todos os clientes se torne idêntico.
2. Preservação da intenção: a intenção de uma operação deve ser armazenada em todas as réplicas, independentemente de se sobrepor para executar várias operações ao mesmo tempo. A intenção de uma operação é definida como o efeito de sua execução na cópia em que foi criada.
   
   Considere um exemplo em que essa propriedade falha:
   
   
   
   
   Ambos os clientes começam com as mesmas réplicas e, em seguida, ambos fazem as alterações. Para Petya, a intenção de sua operação é inserir '12' no primeiro índice e, para Vasya, excluir os caracteres com os índices 2 e 3. Após a sincronização com Petya Vasino, a intenção e a intenção de Vasya Petino são violadas. Observe também que as réplicas divergiram, mas isso não é um requisito para a propriedade em questão. A versão final correta é proposta para identificar o leitor como um pequeno exercício.
   
3. Preservação de causalidade: As operações devem ser executadas em uma ordem causal (com base no relacionamento aconteceu antes ).
   
   Considere um exemplo em que essa propriedade falha:
   
   
   
   
   Como você pode ver, Petya enviou a Vasya e ao agente Smith sua alteração do documento, Vasya recebeu primeiro e excluiu o último caractere. Devido ao atraso na rede, Smith recebe a primeira operação para Vasin excluir um caractere que ainda não existe.
   
   OT não pode garantir que a propriedade de preservação de causalidade seja cumprida; portanto, algoritmos como um relógio de vetor são usados ​​para esses fins.
   

OT Design

Uma das estratégias de design do sistema OT é a divisão em três partes:

• Algoritmos de controle de transformação: determine quando a operação (destino) está pronta para transformar, em relação a quais operações (referência) as transformações devem ser executadas e em que ordem para executá-las.
• Funções de transformação: Transforma a operação de destino, levando em consideração o impacto das operações de referência.
• Requisitos e propriedades das transformações (propriedades e condições): forneça uma conexão entre esses componentes e realize verificações para correção.

Funções de conversão

As funções de conversão podem ser divididas em dois tipos:

• Inclusão / transformação avançada: transformando uma operação $$$O_a$ antes da cirurgia $$$O_b$ para que o efeito de $$$O_b$ (por exemplo, duas inserções)
• Exclusão / transformação reversa: transformação de uma operação $$$O_a$ antes da cirurgia $$$O_b$ para que o efeito de $$$O_b$ excluído (por exemplo, inserir após exclusão)

Um exemplo para operações simbólicas de inserção / exclusão (i - inserir, d - excluir):

Tii(Ins[p1, c1], Ins[p2, c2]) { if (p1 < p2) || ((p1 == p2) && (order() == -1)) // order() –   return Ins[p1, c1]; // Tii(Ins[3, 'a'], Ins[4, 'b']) = Ins[3, 'a'] else return Ins[p1 + 1, c1]; // Tii(Ins[3, 'a'], Ins[1, 'b']) = Ins[4, 'a'] } Tid(Ins[p1, c1], Del[p2]) { if (p1 <= p2) return Ins[p1, c1]; // Tid(Ins[3, 'a'], Del[4]) = Ins[3, 'a'] else return Ins[p1 – 1, c1]; // Tid(Ins[3, 'a'], Del[1]) = Ins[2, 'a'] } Tdi(Del[p1], Ins[p2, c1]) { //   ,    } Tdd(Del[p1], Del[p2]) { if (p1 < p2) return Del[p1]; // Tdd(Del[3], Del[4]) = Del[3] else if (p1 > p2) return Del[p1 – 1]; // Tdd(Del[3], Del[1]) = Del[2] else return Id; // Id –   } 

3. Protocolo de interação no Google Docs

Vamos ver como o protocolo de interação no Google Docs funciona com mais detalhes. Suponha que tenhamos um servidor, Petya e Vasya, e eles tenham uma versão sincronizada de um documento vazio.

Cada cliente lembra as seguintes informações:

• Versão (identificação, revisão) da última alteração recebida do servidor.
• Todas as alterações feitas localmente, mas não enviadas para o servidor (envio pendente)
• Todas as alterações feitas localmente, enviadas ao servidor, mas sem confirmação do servidor.
• O estado atual do documento que o usuário vê.

O servidor, por sua vez, lembra:

• Uma lista de todas as alterações recebidas, mas não processadas (processamento pendente).
• Histórico completo de todas as alterações processadas (log de revisão).
• O estado do documento no momento da última alteração processada.

Então, Petya começa com a palavra "Olá" no início do documento:


O cliente primeiro adicionou essa alteração à lista de espera e depois a enviou ao servidor e moveu as alterações para a lista enviada.

Petya continua digitando e já adicionou a palavra "Habr". Ao mesmo tempo, Vasya digitou "!" em seu documento vazio (ele ainda não recebeu as alterações de Petina).


Petino $$$\ {Inserir \ \ 'Habr', \ @ 5 \}$ foi adicionado à lista pendente, mas ainda não foi enviado, porque não estamos enviando mais de uma alteração por vez e a anterior ainda não foi confirmada . Também observamos que o servidor salvou as alterações do Petit em seu log de revisão. Em seguida, o servidor os envia para Vasya e envia uma confirmação para Petya (que as primeiras alterações de Petina foram processadas com êxito)


O cliente de Vasya recebe as alterações de Petina do servidor e aplica o OT em relação ao envio pendente para o servidor $$$\ {Inserir \ \ '!', \ @ 0 \}$ . O resultado é uma alteração no índice de inserção de 0 para 5. Também observamos que os dois clientes atualizaram o número da última revisão sincronizada com o servidor para 1. Por fim, o cliente Petin remove a alteração correspondente da lista de confirmação pendente do servidor.

Em seguida, Petya e Vasya enviam suas alterações para o servidor.


O servidor recebe as alterações de Petina antes (em relação à ordem inserida) Vasinykh, então ele as processa primeiro e envia a confirmação para Petya. Ele também os envia para Vasya, e seu cliente os converte em relação às alterações que ainda não foram confirmadas. $$$\ {Inserir \ \ '!', \ @ 5 \}$ .

Então vem o ponto importante. O servidor começa a processar as alterações de Vasya, aquelas que, de acordo com Vasya, têm o número de revisão 2. Mas o servidor já confirmou as alterações no número 2, portanto, aplica a conversão a todas as alterações que o cliente de Vasya ainda não está ciente (neste caso - $$$\ {Inserir \ \ 'Habr', \ @ 5 \}$ ) e salva o resultado no número 3.


Como podemos ver, o índice na alteração de Vasin foi aumentado em 5 para acomodar o texto de Petin.

O processo está concluído para Petya, e Vasya precisa receber uma nova alteração do servidor e enviar uma confirmação.

4. Etherpad

Vejamos outro aplicativo semelhante em que o OT é usado - o projeto de código aberto do editor on-line com a edição conjunta etherpad.org

No Etherpad, as funções de conversão são ligeiramente diferentes - as alterações são enviadas ao servidor como um conjunto de alterações (changeset) , definido como

$$

$$(\ ell_1 \ rightarrow \ ell_2) [c_1, c_2, c_3, ...],$$

onde

• $$$\ ell_1$ : comprimento do documento antes da edição.
• $$$\ ell_2$ : comprimento do documento após a edição.
• $$$c_1, c_2, c_3, ...$ - descrição do documento após a edição. Se $$$c_i$ Se for um número (ou um intervalo de números), esses são os índices dos caracteres do documento original que permanecerão após a edição (retidos) e, se $$$c_i$ - um caractere (ou string), então isso é inserção.
  
  Um exemplo:
  
  
  1. $$$ inline $ `` "+ \ (0 \ rightarrow 6) [` `Olá"] = `` Olá "$ inline $
  2. $$$ inline $ `` Beaver '' + (4 \ rightarrow 4) [`` Ha ”, \ 2-3] =` `Habr '$ inline $
  
  

Como você já entende, o documento final é formado como uma sequência dessas alterações aplicada a um documento vazio.

Observe que não podemos apenas aplicar alterações de outros participantes (isso, em princípio, é possível no Google Docs), porque o comprimento total dos documentos pode ser diferente.
Por exemplo, se o documento de origem tiver comprimento n e tivermos duas alterações:

$$

$$A = (n \ rightarrow n_a) [\ cdots] \\ B = (n \ rightarrow n_b) [\ cdots],$$

então $$$A (B)$ impossível, porque $$$A$ requer comprimento do documento $$$n$ e depois $$$B$ ele será de comprimento $$$n_b$ .
Para resolver essa situação, o Etherpad usa um mecanismo de mesclagem : é uma função indicada por $$$m (A, B)$ , aceita duas alterações na entrada no mesmo estado do documento (doravante referido como $$$X$ ) e faz uma nova alteração.

Exigido que

$$

$$m (A, B) = m (B, A)$$

Observe que para um cliente com alterações $$$A$ quem recebeu a mudança $$$B$ não faz sentido calcular $$$m (A, B)$ desde $$$m (A, B)$ aplica-se a $$$X$ e $$$A$ estado atual $$$A (X)$ . De fato, precisamos calcular $$$A '$ e $$$B '$ tal que

$$

$$B '(A (X)) = A' (B (X)) = m (A, B) (X)$$

Cálculo da função $$$A '$ e $$$B '$ é chamado follow e é definido da seguinte maneira:
$$$f (A, B) (A) = f (B, A) (B) = m (A, B) = m (B, A)$
Algoritmo de construção $$$f (A, B)$ seguinte:

• A inserção em A se torna os índices em $$$f (A, B)$
• A inserção em B se torna a inserção em $$$f (A, B)$
• Os índices correspondentes em A e B são transferidos para $$$f (A, B)$

Um exemplo:

$$$$ display $$ X = (0 \ rightarrow 8) [`` baseball ”] \\ A = (8 \ rightarrow 5) [0 - 1,` `si '', 7] \ / \! \! / == `` basil '\\ B = (8 \ rightarrow 5) [0, `` e ", 6,` `ow"] \ / \! \! / == `` abaixo "$$ display $$

Calculamos:

$$

$$A '= f (B, A) = (5 \ rightarrow 6) [0, 1, `` si ", 3, 4] \\ B' = f (A, B) = (5 \ rightarrow 6) [ 0, “e”, 2, 3, `` ow "] \\ m (A, B) = m (B, A) = A (B ') = B (A') = (8 \ rightarrow 6) [ 0, `` esiow "] \\ $$

Calcular $$$m (A, B) (X)$ oferecido como um exercício.

O protocolo de interação é essencialmente o mesmo do Google Docs, a menos que os cálculos sejam um pouco mais complicados.

5. Críticas ao AT

• A implementação do OT é uma tarefa muito difícil em termos de programação. Citando o Wikipedia : Joseph Gentle, o desenvolvedor da biblioteca Share.JS e ex-engenheiro do Google Wave, disse: “Infelizmente, implementar o OT é uma porcaria. Há um milhão de algoritmos com diferentes trocas, a maioria presas em trabalhos acadêmicos. Os algoritmos são realmente difíceis e demorados para serem implementados corretamente. [...] Wave demorou 2 anos para escrever e, se a reescrevéssemos hoje, levaria quase tanto tempo para escrever uma segunda vez. ”
  
  (Infelizmente, escrever OT é muito difícil. Existem milhões de algoritmos com seus prós e contras, mas a maioria deles são apenas estudos acadêmicos. Os algoritmos são realmente muito complexos e requerem muito tempo para sua correta implementação. [...] Passamos 2 anos em escrevendo Wave, e se tivéssemos que escrevê-lo novamente hoje, levaria a mesma quantidade de tempo)
  
• Você deve salvar absolutamente todas as alterações no documento
  

6. Referências

• Controle de simultaneidade em sistemas de groupware
• O que há de novo no novo Google Docs: trabalhando juntos, mesmo separados
• O que há de novo no novo Google Docs: resolução de conflitos
• Compreendendo e aplicando a transformação operacional
• Wikipedia: Transformação operacional
• Janela de alta latência e baixa largura de banda no sistema de colaboração Jupiter
• O que há de novo no novo Google Docs: Tornando a colaboração rápida
• Transformação Operacional em Editores de Grupo em Tempo Real: Problemas, Algoritmos e Conquistas
• Manual Técnico Etherpad e EasySync
• Google TechTalks: problemas e experiências no design de sistemas de edição colaborativa em tempo real
• Transformação operacional Perguntas e respostas frequentes