Operational Transformation, el algoritmo de edición colaborativa en tiempo real

Este es el segundo post relacionado con Operational Transformation , el algoritmo de edición colaborativa en tiempo real. La primera publicación fue ¿Cómo funcionan los editores colaborativos en tiempo real? [Transformación Operacional] .

En esta publicación, profundizaría en la función de transformación, cómo los clientes esperan el reconocimiento del servidor antes de enviar más operaciones y la transformación operativa compuesta.

función de transformación

En resumen, para manejar operaciones concurrentes, usamos la función de transformación que toma dos operaciones que se han aplicado al mismo estado del documento (pero en diferentes clientes) y calcula una nueva operación que se puede aplicar después de la segunda operación y que conserva la primera. cambio previsto de la operación.

Básicamente, existen dos tipos de funciones de transformación:

• Transformación de Inclusión : denotada como IT(a, b), que transforma la Operación a contra otra operación b de tal manera que el impacto de b es efectivamente incluido.
• Transformación de Exclusión : denotada como ET(a, b), que transforma la operación a contra otra operación b de tal manera que el impacto de b es efectivamente excluido.

Las funciones de transformación se nombran de manera diferente en diferentes sistemas OT, y algunas funciones de transformación compuestas pueden combinar funcionalidades de TI y ET en una sola función. Uno de los documentos, Análisis de algoritmos de transformación operativa , es realmente bueno y analiza todos los diferentes sistemas de OT.

Función de transformación inteligente de caracteres

El algoritmo de una función de transformación de caracteres (para el mantenimiento de la consistencia) es simple. Como ejemplo, para un par de operaciones de caracteres Ins[p, c] (para insertar un carácter c en la posición p) y Del[p] (para eliminar un carácter en la posición p), cuatro funciones de TI, indicadas como Tii , Tid , Tdi , Tdd , se pueden definir de la siguiente manera:

 Tii(Ins[p1,c1], Ins[p2, c2]) { if p1 < p2 or (p1 = p2 and u1 > u2) // breaking insert-tie using user identifiers (u1, u2) return Ins[p1, c1]; // eg 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]; // eg 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, c2]) { if p1 < p2 return Del[p1]; // eg Tdi(Del[3], Ins[4, “b”]) = Del[3] else return Del[p1+1]; } // Tdi(Del[3], Ins[1, “b”]) = Del[4] Tdd(Del[p1], Del[p2]) { if p1 < p2 return Del[p1]; // eg Tdd(Del[3], Del[4]) = Del[3] else if p1 > p2 return Del[p1-1]; // Tdd(Del[3], Del[1]) = Del[2] else return I; } // breaking delete-tie using I (identity op) Tdd(Del[3]. Del[3]) = I

El algoritmo de la función de transformación de cadena es significativamente más desafiante que las operaciones de caracteres porque:

• una eliminación de cadena cubre un rango de eliminación, que puede incluir los caracteres de la cadena, así como las posiciones de intervalo entre los caracteres.
• las operaciones de eliminación de cadenas simultáneas pueden superponerse arbitrariamente entre sí e incluso con las operaciones de inserción simultáneas.
• una cadena insertada por una operación de inserción anterior puede cambiarse siguiendo (causalmente después) las operaciones de inserción y eliminación.

Deshacer aplicación relacionada

Por supuesto, Operational Transformation admite deshacer en editores colaborativos que imponen requisitos adicionales:

• Uno es el efecto de deshacer, que requiere que deshacer una operación O logre el efecto de eliminar el efecto de O pero conserva los efectos de otras operaciones en el documento. En otras palabras, el efecto de deshacer O es transform el estado del documento en uno al que habría ido si nunca se hubiera realizado O pero se hubieran realizado otras operaciones. Este efecto de deshacer es consistente con el efecto de deshacer lineal en entornos de edición de un solo usuario, y también es adecuado para deshacer no lineal (por ejemplo, "deshacer cualquier operación en cualquier momento") en entornos de edición multiusuario y concurrente.
• La otra es la propiedad de deshacer, que requiere que el documento se restaure a cualquier estado anterior deshaciendo todas las operaciones ejecutadas después de ese estado, independientemente del orden en que se deshagan esas operaciones. Esta propiedad es necesaria para garantizar la capacidad de "restaurar cualquier estado anterior", lo cual es esencial para que una solución de deshacer admita la recuperación de errores y la exploración alternativa.

Cliente: enfoque de reconocimiento del servidor

Solo para recapitular, lo que dice la teoría de la transformación operativa en ventanas dealta latencia y bajo ancho de banda en el sistema de colaboración de Júpiter es que un cliente puede enviar operaciones en una secuencia al servidor y viceversa. Esto significa que el cliente y el servidor pueden atravesar el espacio de estado a través de diferentes caminos de transformación operativa al mismo estado convergente dependiendo de cuándo reciben las otras operaciones.

Cuando varios clientes están conectados al servidor, cada pareja de cliente y servidor tiene su propio espacio de estado. Una desventaja de esto es que el servidor necesitaría llevar un espacio de estado para cada cliente conectado, lo que puede consumir mucha memoria. Además, esto complica el algoritmo del servidor al requerir que convierta las operaciones de los clientes entre espacios de estado.

Tener un servidor simple y eficiente es importante para que las olas sean confiables y escalables. Con este objetivo, el algoritmo de transformación operativa de Google modifica la teoría básica de OT al requerir que el cliente espere el reconocimiento del servidor antes de enviar más operaciones. Cuando un servidor reconoce la operación de un cliente, significa que el servidor transformó la operación del cliente, la aplicó a la copia del servidor de la wavelet y transmitió la operación transformada a todos los demás clientes conectados. Mientras el cliente espera el reconocimiento, almacena en caché las operaciones producidas localmente y las envía de forma masiva más tarde.

Con la adición de reconocimientos, un cliente puede inferir la ruta OT del servidor. Al tener esto, el cliente puede enviar operaciones al servidor que siempre están en la ruta OT del servidor.

Esto tiene el importante beneficio de que el servidor solo necesita tener un único espacio de estado , que es el historial de operaciones que ha aplicado. Cuando recibe la operación de un cliente, solo necesita transformar la operación contra el historial de operaciones, aplicar la operación transformada y luego transmitirla. Esta fuente de verdad también obliga al cliente a esperar a que el servidor reconozca la operación que el cliente acaba de enviar, lo que significaría que el cliente siempre permanece en la ruta OT del servidor. Esto ayudaría a mantener un único historial de operaciones sin tener que mantener un espejo del estado de cada cliente conectado. Eventualmente, eso significaría que la cantidad de clientes que están conectados al servidor tendrían solo una copia del documento en el servidor. Una compensación de este cambio es que un cliente verá fragmentos de operaciones de otro cliente en intervalos de aproximadamente un tiempo de ida y vuelta al otro cliente.

Transformación Operacional Compuesta

Un gran tutorial sobre Transformación Operacional Compuesta esComprender y Aplicar la Transformación Operacional por Daniel Spiewak . Uno debe leer esto para entender cómo funciona la Transformación Operacional Compuesta.

Conclusión

Como mencioné anteriormente, Operational Transformation es una herramienta muy poderosa que permite crear excelentes aplicaciones colaborativas con soporte para la edición simultánea sin bloqueo. Seguiría actualizando la publicación de blog con lo que aprendo más sobre OT y otros algoritmos de edición colaborativa en tiempo real.

Citando de la página de Wikipedia :

Si bien el enfoque clásico de OT de definir operaciones a través de sus compensaciones en el texto parece ser simple y natural, los sistemas distribuidos del mundo real plantean problemas serios. Es decir, que las operaciones se propagan con una velocidad finita, los estados de los participantes suelen ser diferentes, por lo que las combinaciones resultantes de estados y operaciones son extremadamente difíciles de prever y comprender. Como lo expresaron Li y Li, "Debido a la necesidad de considerar la cobertura de casos complicados, las pruebas formales son muy complicadas y propensas a errores, incluso para los algoritmos OT que solo tratan dos primitivas de carácter (insertar y eliminar)".

De manera similar, Joseph Gentle, ex ingeniero de Google Wave y autor de la biblioteca Share.JS, escribió: “Desafortunadamente, implementar OT apesta. Hay un millón de algoritmos con diferentes compensaciones, en su mayoría atrapados en trabajos académicos. Los algoritmos son realmente difíciles y consumen mucho tiempo para implementarlos correctamente. […] Wave tomó 2 años para escribir y si lo reescribimos hoy, tomaría casi el mismo tiempo para escribir una segunda vez”.

Para que OT funcione, se debe capturar cada cambio en los datos: “Obtener una instantánea del estado suele ser trivial, pero capturar ediciones es un asunto completamente diferente. […] La riqueza de las interfaces de usuario modernas puede hacer que esto sea problemático, especialmente en un entorno basado en navegador”. Una alternativa a OT es la sincronización diferencial.

Referencias

He leído los siguientes documentos y artículos para obtener información sobre la transformación operativa.

• Ventanas de alta latencia y bajo ancho de banda en el sistema de colaboración de Júpiter Escrito por David A. Nichols, Pavel Curtis, Michael Dixon y John Lamping.
• Transformación operativa en editores de grupos en tiempo real: problemas, algoritmos y logros Escrito por Chengzheng Sun y Clarence (Skip) Ellis.
• Documento técnico de Google sobre la transformación operativa
• Control de simultaneidad en sistemas de trabajo en grupo Creado por CA Ellis, SJ Gibbs
• Evaluación de CRDT para la edición de documentos en tiempo real Escrito por Mehdi Ahmed-Nacer, Claudia-Lavinia Ignat, G´erald Oster, Hyun-Gul Roh, Pascal Urso
• Fusión de algoritmos OT y CRDT Creado por Mehdi Ahmed-Nacer, Pascal Urso, Valter Balegas, Nuno Pregui¸ca
• Wikipedia sobre transformación operativa Sorprendentemente, uno de los artículos más informativos que he encontrado en wikipedia.