La resolución automática de conflictos en un entorno con más de un nodo principal (en este artículo, un nodo principal se refiere a un nodo que acepta solicitudes de cambio de datos) es un área de investigación muy interesante. Existen varios enfoques y algoritmos diferentes, dependiendo de la aplicación, y este artículo discutirá la tecnología de Transformaciones Operacionales (OT) para resolver conflictos en aplicaciones de edición colaborativa como Google Docs y Etherpad.

1. Introducción

La colaboración es difícil desde un punto de vista técnico, porque varias personas pueden hacer diferentes cambios en la misma sección de texto en casi los mismos puntos de tiempo. Dado que la entrega de datos a través de Internet no es instantánea (la velocidad de transferencia de datos en la fibra tiene limitaciones), cada cliente trabaja con una versión local (réplica) del documento editado para simular una respuesta instantánea, que puede diferir de las versiones de otros participantes. Y el problema principal es garantizar la coherencia entre las versiones locales, o en otras palabras, cómo garantizar que todas las versiones locales converjan tarde o temprano en la misma versión correcta de un documento (no podemos exigir a todos los clientes que algunos momentos de tiempo simultáneamente tenían la misma versión, ya que el proceso de edición puede ser interminable).

Versión antigua de Google Docs

Inicialmente, Google Docs, como muchas otras aplicaciones colaborativas de edición de documentos, utilizaba una comparación simple de los contenidos de diferentes versiones de un documento. Supongamos que tenemos dos clientes: Petya y Vasya, y el estado actual del documento se sincroniza entre ellos. En la versión anterior del servidor de Google de Google, al recibir una actualización de Petya, calcula la diferencia (diff) entre su versión y la suya e intenta fusionar las dos versiones en una de la mejor manera posible. Luego, el servidor envía la versión recibida a Vasya. Si Vasya tiene cambios que no se envían al servidor, entonces el proceso se repite: debe fusionar la versión del servidor con la Vasina local y enviarla nuevamente al servidor.

Muy a menudo, este enfoque no funciona muy bien. Por ejemplo, supongamos que Petya, Vasya y el servidor comienzan con un documento sincronizado con el texto " El zorro marrón rápido ".

Petya resalta las palabras zorro marrón en negrita, mientras que Vasya reemplaza la palabra zorro por perro . Deje que Petina cambie primero al servidor y él envía la versión actualizada de Vasya. Está claro que el resultado final debería ser El perro marrón rápido , pero no hay suficiente información para que los algoritmos de fusión comprendan esto, las opciones El perro zorro marrón rápido , El perro marrón rápido , El zorro perro marrón rápido son absolutamente correctas. (Por ejemplo, en git en tales casos, obtendrá un conflicto de fusión y tendrá que gobernar con las manos). Este es el principal problema de este enfoque: no podrá estar seguro de los resultados de la fusión si se basa únicamente en el contenido del documento.

Puede intentar mejorar la situación y bloquear la capacidad de otros participantes para editar secciones de texto que alguien ya gobierna. Pero esto no es lo que queremos: este enfoque simplemente intenta evitar resolver un problema técnico al empeorar la experiencia del usuario, y también puede haber una situación en la que dos participantes comenzaron a editar la misma oración al mismo tiempo, y luego uno de ellos perderá los cambios o tendrá que combinar manualmente los cambios en caso de los conflictos anteriores.

Nueva versión de Google Docs

En la nueva versión de Google Docs, se usó un enfoque completamente diferente: los documentos se almacenan como una secuencia de cambios y, en lugar de comparar los contenidos, hacemos los cambios en orden (en lo sucesivo , la relación de orden ). Sabiendo cómo el usuario modificó el documento y teniendo en cuenta sus intenciones, podemos determinar correctamente la versión final después de combinar todas las ediciones.

Bien, ahora debemos entender cuándo aplicar los cambios; necesitamos un protocolo de colaboración .

En Google Docs, todas las ediciones de documentos se reducen a tres operaciones diferentes:

Inserción de texto
Eliminar texto
Aplicar estilos al texto

Por lo tanto, cuando edita un documento, todas sus acciones se almacenan exactamente en este conjunto de operaciones y se agregan al final del registro de cambios. Cuando se muestra el documento, el registro de cambios se ejecutará utilizando las operaciones registradas.

Una pequeña observación: el primer producto (público) de Google con soporte OT fue, aparentemente, Google Wave. Apoyó una gama mucho más amplia de operaciones.

Ejemplo

Deje que Petya y Vasya comiencen desde el mismo estado de "HABR 2017".
Petya cambia 2017 a 2018, esto en realidad crea 2 operaciones:

Al mismo tiempo, Vasya cambia el texto a "HOLA HABR 2017":

Vasya recibe la operación de Petin para eliminar, si solo la aplica, se obtendrá el texto incorrecto (el número 7 debería haberse eliminado):

Para evitar esto, Vasya debe transformar la operación de Petin de acuerdo con sus cambios locales actuales (en otras palabras, las operaciones son sensibles al contexto):

\ {Eliminar \ \ @ 8 \} \ rightarrow \ {Eliminar \ \ @ 15 \}

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

Hablando un poco más formalmente, considere este ejemplo:

Entonces:

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

Voila! El algoritmo descrito se llama transformación operacional.

2. Transformación operacional

Modelo de consistencia

Para garantizar la coherencia, se han desarrollado varios modelos de coherencia , considere uno de ellos: CCI.

El modelo CCI proporciona tres propiedades:

Convergencia: todas las réplicas de un documento común deben ser idénticas después de completar todas las operaciones:

En este ejemplo, ambos usuarios comienzan con réplicas idénticas. Luego cambian el documento y las réplicas divergen, de esta manera se logra el tiempo mínimo de respuesta. Después de enviar cambios locales a otros clientes, la propiedad de convergencia requiere que el estado final del documento para todos los clientes sea idéntico.
Conservación de la intención: la intención de una operación debe almacenarse en todas las réplicas, independientemente de si se superpone para realizar múltiples operaciones al mismo tiempo. La intención de una operación se define como el efecto de su ejecución en la copia donde se creó.

Considere un ejemplo donde esta propiedad falla:

Ambos clientes comienzan con las mismas réplicas, luego ambos realizan los cambios. Para Petya, la intención de su operación es insertar '12' en el primer índice, y para Vasya, eliminar los caracteres con los índices 2 y 3. Después de la sincronización con Petya Vasino, la intención y con Vasya Petino se viola la intención. Tenga en cuenta también que las réplicas han divergido, pero esto no es un requisito para la propiedad en cuestión. Se propone la versión final correcta para identificar al lector como un pequeño ejercicio.
Preservación de la causalidad: las operaciones deben realizarse en un orden causal (basado en la relación anterior ).

Considere un ejemplo donde esta propiedad falla:

Como puede ver, Petya envió a Vasya y al Agente Smith su cambio del documento, Vasya lo recibió primero y eliminó el último personaje. Debido al retraso de la red, Smith recibe la primera operación para que Vasin elimine un personaje que aún no existe.

OT no puede garantizar que se cumpla la propiedad de preservación de causalidad; por lo tanto, se utilizan algoritmos como un reloj vectorial para estos fines.

Diseño OT

Una de las estrategias de diseño del sistema OT es la división en tres partes:

Algoritmos de control de transformación: determinan cuándo la operación (objetivo) está lista para transformarse, con respecto a qué operaciones (referencia) deben realizarse las transformaciones y en qué orden ejecutarlas.
Funciones de transformación: transforma la operación de destino, teniendo en cuenta el impacto de las operaciones de referencia.
Requisitos y propiedades de las transformaciones (propiedades y condiciones): proporcione una conexión entre estos componentes y realice comprobaciones de corrección.

Funciones de conversión

Las funciones de conversión se pueden dividir en dos tipos:

Inclusión / Transformación directa: transformación de una operación $O_a$ antes de la cirugía $O_b$ para que el efecto de $O_b$ (por ejemplo, dos insertos)
Exclusión / Transformación hacia atrás: transformación de una operación $O_a$ antes de la cirugía $O_b$ para que el efecto de $O_b$ excluido (por ejemplo, insertar después de la eliminación)

Un ejemplo para operaciones simbólicas de inserción / eliminación (i - inserción, d - eliminación):

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 interacción en Google Docs

Veamos cómo funciona el protocolo de interacción en Google Docs con más detalle. Supongamos que tenemos un servidor, Petya y Vasya, y ellos tienen una versión sincronizada de un documento vacío.

Cada cliente recuerda la siguiente información:

Versión (id, revisión) del último cambio recibido del servidor.
Todos los cambios realizados localmente pero no enviados al servidor (pendiente de envío)
Todos los cambios realizados localmente, enviados al servidor, pero sin confirmación del servidor.
El estado actual del documento que ve el usuario.

El servidor, a su vez, recuerda:

Una lista de todos los cambios recibidos pero no procesados (procesamiento pendiente).
Historial completo de todos los cambios procesados (registro de revisión).
El estado del documento en el momento del último cambio procesado.

Entonces, Petya comienza con la palabra "Hola" al comienzo del documento:

El cliente primero agregó este cambio a la lista de espera, y luego lo envió al servidor y movió los cambios a la lista enviada.

Petya continúa escribiendo y ya ha agregado la palabra "Habr". Al mismo tiempo, Vasya escribió "!" en su documento vacío (aún no ha recibido los cambios de Petina).

Petino

\ {Insertar \ \ 'Habr', \ @ 5 \}

$\ {Insertar \ \ 'Habr', \ @ 5 \}$ se ha agregado a la lista pendiente, pero aún no se ha enviado, porque no estamos enviando más de un cambio a la vez, y el anterior aún no se ha confirmado . También notamos que el servidor guardó los cambios de Petit en su registro de revisión. Luego, el servidor los envía a Vasya y envía una confirmación a Petya (que los primeros cambios de Petina se procesaron con éxito)

El cliente de Vasya recibe los cambios de Petina del servidor y aplica OT con respecto a su envío pendiente al servidor

\ {Insertar \ \ '!', \ @ 0 \}

$\ {Insertar \ \ '!', \ @ 0 \}$ . El resultado es un cambio en el índice de inserción de 0 a 5. También notamos que ambos clientes actualizaron el número de la última revisión sincronizada con el servidor a 1. Finalmente, el cliente Petin elimina el cambio correspondiente de la lista de confirmación pendiente del servidor.

Entonces Petya y Vasya envían sus cambios al servidor.

El servidor recibe los cambios de Petina antes (con respecto al pedido ingresado) Vasinykh, por lo que primero los procesa y envía la confirmación a Petya. También los envía a Vasya, y su cliente los convierte con respecto a los cambios que aún no se han confirmado.

\ {Insertar \ \ '!', \ @ 5 \}

$\ {Insertar \ \ '!', \ @ 5 \}$ .

Luego viene el punto importante. El servidor comienza a procesar los cambios de Vasya, aquellos que, según Vasya, tienen la revisión número 2. Pero el servidor ya ha confirmado los cambios en el número 2, por lo que aplica la conversión a todos los cambios que el cliente de Vasya aún no conoce (en este caso -

\ {Insertar \ \ 'Habr', \ @ 5 \}

$\ {Insertar \ \ 'Habr', \ @ 5 \}$ ), y guarda el resultado en el número 3.

Como podemos ver, el índice en el cambio de Vasin se incrementó en 5 para acomodar el texto de Petin.

El proceso se completa para Petya, y Vasya necesita recibir un nuevo cambio del servidor y enviar una confirmación.

4. Etherpad

Veamos otra aplicación similar donde se usa OT: el proyecto de código abierto del editor en línea con coedición etherpad.org

En Etherpad, las funciones de conversión son ligeramente diferentes: los cambios se envían al servidor como un conjunto de cambios (conjunto de cambios) , definidos como

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

donde

$\ ell_1$ : longitud del documento antes de editarlo.
$\ ell_2$ : longitud del documento después de la edición.
c1,c2,c3,... - descripción del documento después de la edición. Si ci Es un número (o un rango de números), entonces estos son los índices de los caracteres del documento original que permanecerán después de la edición (retenidos), y si ci - un carácter (o cadena), entonces esto es inserción.

Un ejemplo:
1. $ inline $ `` "+ \ (0 \ rightarrow 6) [` `Hola”] = `` Hola "$ inline $
2. $ inline $ `` Beaver ”+ (4 \ rightarrow 4) [` `Ha”, \ 2-3] = `` Habr '$ inline $

Como ya comprende, el documento final se forma como una secuencia de dichos cambios aplicados para un documento vacío.

Tenga en cuenta que no podemos simplemente aplicar los cambios de otros participantes (esto, en principio, es posible en Google Docs), porque la longitud total de los documentos puede ser diferente.
Por ejemplo, si el documento fuente era de longitud n, y tenemos dos cambios:

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

entonces

$A (B)$ imposible porque

$A$ requiere longitud del documento

$n$ y despues

$B$ él será de longitud

$n_b$ .
Para resolver esta situación, Etherpad utiliza un mecanismo de fusión : es una función denotada por

$m (A, B)$ , acepta dos cambios en la entrada en el mismo estado del documento (en adelante denominado

$X$ ) y realiza un nuevo cambio.

Requerido que

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

Tenga en cuenta que para un cliente con cambios

$A$ quien recibió el cambio

$B$ no tiene sentido calcular

$m (A, B)$ desde

$m (A, B)$ aplica a

$X$ y

$A$ estado actual

$A (X)$ . De hecho, necesitamos calcular

$A ’$ y

$B ’$ tal que

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

Función de cálculo

$A ’$ y

$B ’$ se llama seguir y se define de la siguiente manera:

$f (A, B) (A) = f (B, A) (B) = m (A, B) = m (B, A)$
Algoritmo de construcción

$f (A, B)$ siguiente:

La inserción en A se convierte en los índices en $f (A, B)$
El inserto en B se convierte en el inserto en $f (A, B)$
Los índices coincidentes en A y B se transfieren a $f (A, B)$

Un ejemplo:

$$ display $$ X = (0 \ rightarrow 8) [`` baseball ”] \\ A = (8 \ rightarrow 5) [0 - 1,` `si”, 7] \ / \! \! / == `` basil ”\\ B = (8 \ rightarrow 5) [0,` `e", 6, `` ow "] \ / \! \ !! / ==` `debajo de" $$ 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)$ ofrecido como ejercicio.

El protocolo de interacción es esencialmente el mismo que Google Docs, a menos que los cálculos sean un poco más complicados.

5. Crítica de OT

Implementar OT es una tarea muy difícil en términos de programación. Citando de Wikipedia : Joseph Gentle, el desarrollador de la biblioteca Share.JS y ex ingeniero de Google Wave dijo: "Desafortunadamente, implementar OT es una mierda. Hay un millón de algoritmos con diferentes compensaciones, en su mayoría atrapados en documentos académicos. Los algoritmos son realmente difíciles y lentos de implementar correctamente. [...] Wave tardó 2 años en escribir y si lo reescribimos hoy, tomaría casi el mismo tiempo escribirlo por segunda vez ".

(Desafortunadamente, escribir OT es muy difícil. Hay un millón de algoritmos con sus pros y sus contras, pero la mayoría de ellos son solo estudios académicos. Los algoritmos en realidad son muy complejos y requieren mucho tiempo para su correcta implementación. [...] Pasamos 2 años en escribiendo Wave, y si tuviéramos que volver a escribirlo hoy, nos llevaría la misma cantidad de tiempo)
Debe guardar absolutamente cada cambio en el documento

Resolución automática de conflictos mediante transformaciones operativas.