algorithm - Diferencias entre OT y CRDT

paxos operational-transform

Question

¿Alguien puede explicarme simplemente las principales diferencias entre la Transformación Operacional y la CRDT?

Según tengo entendido, ambos son algoritmos que permiten que los datos converjan sin conflicto en diferentes nodos de un sistema distribuido.

¿En qué caso de uso usaría qué algoritmo? Según tengo entendido, OT se usa principalmente para texto y CRDT es más general y puede manejar estructuras más avanzadas, ¿no?

¿Es CRDT más poderoso que OT?

Hago esta pregunta porque estoy tratando de ver cómo implementar un editor colaborativo para documentos HTML, y no estoy seguro en qué dirección mirar primero. Vi el proyecto ShareJS, y sus intentos de apoyar la colaboración de texto enriquecido en el navegador en elementos contenteditables . En ninguna parte de ShareJS veo ningún intento de usar CRDT para eso.

También sabemos que Google Docs usa OT y funciona bastante bien para la edición en tiempo real de documentos enriquecidos. ¿La elección de Google de usar OT porque CRDT no era muy conocida en ese momento? ¿O sería una buena opción hoy también?

También me interesa escuchar sobre otros casos de uso, como el uso de estos algoritmos en bases de datos. Riak parece utilizar CRDT. ¿Se puede utilizar OT para sincronizar los nodos de una base de datos y ser una alternativa a Paxos / Zab / Raft?

Answer 1

Ambos enfoques son similares en cuanto a que proporcionan una consistencia eventual. La diferencia está en cómo lo hacen. Una forma de verlo es:

• OT lo hace cambiando las operaciones . Las operaciones se envían por cable y las operaciones simultáneas se transforman una vez que se reciben.
• Las CRDT lo hacen cambiando de estado . Las operaciones se realizan en la CRDT local. Su estado se envía a través del cable y se fusiona con el estado de una copia. No importa cuántas veces o en qué orden se realicen las combinaciones: todas las copias convergen.

Tienes razón, OT se usa principalmente para texto y precede a las CRDT, pero la research muestra que:

muchos algoritmos de OT en la literatura no satisfacen las propiedades de convergencia a diferencia de lo que afirmaron sus autores

En otras palabras, la fusión de CRDT es conmutativa, mientras que las funciones de transformación OT a veces no lo son.

Del artículo de Wikipedia sobre CRDT :

Los OT son generalmente complejos y no escalables

Existen diferentes tipos de CRDT (conjuntos, contadores, ...) adecuados para diferentes tipos de problemas. Hay algunos que están diseñados para la edición de texto. Por ejemplo, Treedoc: un tipo de datos replicados conmutativos para la edición cooperativa .