Los tipos de datos replicados libres de conflictos (CRDT) son una clase de estructuras de datos que permiten una colaboración y sincronización de datos fluidas en sistemas distribuidos, lo que permite actualizaciones colaborativas sin conflictos. Los CRDT están diseñados para lograr coherencia eventual entre múltiples réplicas de datos, asegurando que incluso cuando las actualizaciones se produzcan de forma independiente, todas las réplicas converjan al mismo estado sin requerir mecanismos complejos de resolución de conflictos.

En esta publicación de blog, profundizaremos en qué son los CRDT, exploraremos sus usos y tipos, comprenderemos cómo funcionan y aprenderemos cómo implementarlos, con un enfoque en JavaScript y la poderosa biblioteca Yjs.

Casos de uso de CRDT

Los CRDT son particularmente útiles en escenarios donde la colaboración en tiempo real y el soporte fuera de línea son cruciales:

1. Editores de texto colaborativos: Google Docs, Notion y Etherpad utilizan estructuras similares a CRDT para la edición en tiempo real.
2. Herramientas de diseño colaborativo: Figma, una popular herramienta de diseño basada en web, utiliza CRDT para permitir la colaboración en tiempo real en proyectos de diseño. Varios diseñadores pueden trabajar en el mismo archivo simultáneamente y los cambios se sincronizan perfectamente entre todos los usuarios.
3. Bases de datos distribuidas: RxDB y Riak utilizan CRDT para una replicación sin conflictos.
4. Juegos multijugador: para mantener un estado de juego constante entre los jugadores.

Tipos de CRDT

Hay dos tipos principales de CRDT:

1. CRDT basados ​​en estado: Estos replican el estado completo de la estructura de datos. La fusión se realiza comparando y conciliando los estados de diferentes réplicas.
2. CRDT basados ​​en operaciones: Estos replican las operaciones realizadas en la estructura de datos. La fusión se realiza aplicando operaciones de diferentes réplicas de forma conmutativa.

Cómo funcionan los CRDT

Los CRDT (tipos de datos replicados libres de conflictos) funcionan según principios que garantizan la coherencia final en todas las réplicas de los datos, incluso cuando las actualizaciones se realizan simultáneamente o cuando se producen particiones de red. Profundicemos en la mecánica:

Propiedades clave

1. Conmutatividad: Esta propiedad asegura que el orden de las operaciones no afecte el resultado final. Por ejemplo, en un contador CRDT, incrementar en 2 y luego en 3 produce el mismo resultado que incrementar en 3 y luego en 2.
2. Asociatividad: Esto significa que no importa la agrupación de operaciones. Usando nuevamente el ejemplo del contador, (1 2) 3 es lo mismo que 1 (2 3).
3. Idempotencia: Aplicar la misma operación varias veces tiene el mismo efecto que aplicarla una vez. Esto es crucial para manejar mensajes duplicados en sistemas distribuidos.

Resolución de conflictos

Los CRDT resuelven conflictos automáticamente por diseño:

• Para los CRDT basados ​​en estados (CvRDT), esto se logra mediante una función de combinación que combina los estados de dos réplicas. Esta función de fusión debe ser conmutativa, asociativa e idempotente.
• Para los CRDT basados ​​en operaciones (CmRDT), las operaciones están diseñadas para ser conmutativas, lo que garantiza que su aplicación en cualquier orden conduzca al mismo estado final.

Relojes lógicos

Muchas implementaciones CRDT utilizan relojes lógicos (como vectores de versión o vectores de versión punteada) para rastrear el historial causal de las operaciones. Esto ayuda a determinar el orden de las operaciones simultáneas y a identificar qué actualizaciones ya ha visto una réplica.

Usando CRDT en JavaScript con Yjs

Implementar CRDT desde cero puede ser complejo. Sin embargo, hay bibliotecas disponibles que simplifican el proceso. Para JavaScript, una de las bibliotecas CRDT más populares es Yjs. Es una implementación CRDT de alto rendimiento que admite varios tipos de datos. Creemos una aplicación simple de lista de tareas pendientes usando Yjs, simulando múltiples usuarios trabajando en el mismo documento en la memoria.

Aquí hay un ejemplo de cómo implementar una lista de tareas compartida utilizando Yjs:

Usemos los ydocs creados:

En este ejemplo, creamos dos documentos Yjs (ydoc1 e ydoc2) para simular dos usuarios trabajando en la misma lista de tareas pendientes. Cada documento tiene su propio mapa compartido para todos.

Definimos funciones para agregar, actualizar y eliminar todos, así como una función syncDocs para sincronizar manualmente el estado entre los dos documentos. Esto simula lo que sucedería en un entorno de red donde se intercambian actualizaciones entre clientes.

Conclusión

Los CRDT proporcionan una solución poderosa para crear aplicaciones distribuidas y colaborativas que pueden funcionar sin problemas en línea y fuera de línea. Si bien los conceptos subyacentes pueden ser complejos, bibliotecas como Yjs facilitan a los desarrolladores aprovechar el poder de los CRDT en sus aplicaciones. A medida que los sistemas distribuidos se vuelvan más frecuentes, comprender y utilizar los CRDT se convertirá en una habilidad cada vez más valiosa para los desarrolladores.

Enlaces útiles

1. Yjs
2. CRDT
3. Tiptap: un editor de texto colaborativo