- CRDT (Conflict-free Replicated Data Type, tipo de dato replicado sin conflictos) es una estructura de datos distribuida que permite fusionar datos de forma consistente sin coordinación, incluso en situaciones de partición de red o modificaciones concurrentes
- Si la fusión de datos cumple conmutatividad, asociatividad e idempotencia, todas las réplicas terminan convergiendo al mismo estado
- Entre las formas más representativas están G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT y Logoot, cada una pensada para distintos requisitos de agregado, eliminación, re-agregado y preservación del orden
- Delta CRDT mejora la eficiencia al enviar solo los cambios en lugar del estado completo, y Garbage Collection es un desafío clave para resolver el problema de acumulación de metadatos
- CRDT no es una solución perfecta, pero se considera una opción poderosa en sistemas donde la disponibilidad es más importante que la consistencia inmediata
Conceptos básicos de CRDT
- CRDT es una estructura de datos que puede fusionarse sin coordinación aunque haya modificaciones concurrentes en entornos distribuidos
- Si la operación de fusión es conmutativa (commutative), asociativa (associative) e idempotente (idempotent), todas las réplicas convergen al mismo estado
- Se diseña con base en el concepto de lattice (retícula), de modo que el estado siempre avance solo “hacia arriba”
- Ejemplo: G-Counter fusiona el conteo de cada réplica con
max para garantizar una suma sin pérdida
- Existen dos enfoques de CRDT: State-based (CvRDT) y Operation-based (CmRDT)
- CvRDT fusiona el estado completo, mientras que CmRDT propaga operaciones
Principales tipos de CRDT
- G-Counter: contador que solo puede incrementarse; suma los valores de cada réplica
- PN-Counter: combina G-Counter para incrementos y decrementos para soportar conteo en ambos sentidos
- G-Set: conjunto al que solo se le pueden agregar elementos
- 2P-Set: permite agregar y eliminar, pero no volver a agregar
- LWW-Element-Set: basado en marcas de tiempo, donde gana la operación más reciente
- OR-Set: usa etiquetas únicas para fusionar sin pérdida de datos cuando hay agregados concurrentes, con comportamiento add-wins
- LWW-Register / MV-Register: para almacenar un solo valor; LWW deja un único ganador y MV conserva todos los valores concurrentes
- OR-Map: estructura de mapa que combina un OR-Set por clave
- RGA / WOOT / Logoot / LSEQ: CRDT para datos de secuencia con orden
- RGA se basa en árboles, WOOT en referencias bidireccionales y Logoot/LSEQ en identificadores de posición
Conceptos avanzados de CRDT
- Causal CRDTs: usan vectores de versión para rastrear relaciones causales y detectar conflictos con mayor precisión
- Delta CRDTs: envían solo los cambios (delta) en lugar del estado completo para mejorar la eficiencia de red
- Tree CRDTs: soportan la replicación de datos jerárquicos (como sistemas de archivos) y requieren mantener la relación padre-hijo
- Observed-Remove Shopping Cart: ejemplo de carrito de compras de comercio electrónico que combina OR-Set y PN-Counter
Problema de Garbage Collection
- Para lograr convergencia, los CRDT acumulan metadatos continuamente, lo que genera un problema de crecimiento infinito
- Ejemplo: las etiquetas de OR-Set y los tombstones de RGA
- Existen diversas estrategias, como expiración basada en tiempo, eliminación basada en consenso, seguimiento causal con vectores de versión, establecer un límite superior de metadatos y checkpoint/rebase
- Cada enfoque requiere un equilibrio entre seguridad (evitar la restauración de zombis) y eficiencia de espacio
Rendimiento y guía de selección
- La complejidad de espacio y tiempo varía según el tipo de CRDT, la cantidad de réplicas, elementos y etiquetas
- G/PN-Counter es proporcional al número de réplicas, OR-Set al número de etiquetas y RGA a la acumulación de tombstones
- Delta CRDT mejora de forma importante el rendimiento de fusión
- Criterios de elección:
- Solo se necesita agregar → G-Counter, G-Set
- Se necesita eliminar y no hace falta re-agregar → 2P-Set
- Se permite LWW → LWW-Set/Register
- Se quiere preservar modificaciones concurrentes → OR-Set, MV-Register
- Se necesita mantener el orden → RGA, Logoot
- Estructura anidada → OR-Map
Conclusión
- CRDT garantiza convergencia sin coordinación, pero tiene como desventajas el crecimiento de metadatos y la complejidad
- Es útil en sistemas que priorizan la disponibilidad, y cada CRDT está optimizado para un tipo de problema específico
- En la práctica se usa junto con bases de datos tradicionales, y una estrategia de recolección de basura es indispensable
- No existe un “CRDT perfecto”; la clave es elegir según los requisitos de la aplicación
1 comentarios
Opinión de Hacker News
Una de las cosas interesantes de los CRDT es que no se trata simplemente de una librería que combina varios CRDT de bajo nivel
Por ejemplo, Automerge es en sí mismo un CRDT completo, y garantiza la consistencia incluso bajo concurrencia mediante pruebas matemáticas
El equipo de Automerge valida el diseño con herramientas de demostración de teoremas como Isabelle, y busca una implementación rápida y precisa aplicando las técnicas de rendimiento más recientes del mundo de las bases de datos
Si estás creando un SaaS de colaboración en tiempo real, como Notion o Figma, puedes aplicar de inmediato estructuras de datos colaborativas sin necesidad de dominar la teoría compleja
El backend puede ser simplemente un almacenamiento key-value, y el frontend solo necesita una librería
Yo también hice una librería de automerge basada en Redis, y pude implementar un servidor de sincronización persistente completo usando pub/sub
Aprovechando la función de websocket de Webdis, también terminé rápidamente un demo de sincronización de documentos entre varios navegadores
Si quieres un mejor DX y una base de datos full-stack basada en CRDT, recomiendo Triplit.dev. El ritmo de desarrollo se ha vuelto algo más lento, pero las funciones ya están bastante completas
Personalmente también me gusta Loro, pero sigue teniendo una estructura basada en documentos, así que le falta un motor de consultas. Para obtener los datos que quieres, tienes que señalar directamente elementos anidados específicos
Fue un buen artículo, bien organizado desde los conceptos básicos de CRDT hasta las ideas más avanzadas
Como referencia, Riak todavía se mantiene en forma de OpenRiak
Desarrollé CRDT directamente durante los últimos dos años, pero me di cuenta de que había demasiados trade-offs, así que al final cambié a un framework OT basado en ID
Planeo lanzar Docnode.dev este martes. Me gustaría recibir comentarios
En el futuro también pienso agregar un modo CRDT para casos donde se necesite P2P
Los CRDT y OT son estructuras pensadas para resolver cuando varias personas editan el mismo párrafo al mismo tiempo, pero en la práctica eso casi nunca pasa
El OR-Set que menciona este artículo es similar al método de fusión que Monotone usaba desde 2005
Se puede ver material relacionado en la documentación de MarkMerge
Los CRDT siguen siendo un área que hay que implementar por cuenta propia
Hace dos meses yo también hice un motor CRDT basado en secuencias, inspirado en diamond types
Le pedí ayuda a la IA, pero no sirvió en absoluto para este tipo de problemas centrados en lógica
Sentí que hace falta una prueba de caja negra para verificar si un LLM puede entender una lógica nueva
El artículo fue excelente, pero creo que el glosario necesita sí o sí un índice (index)
Me queda la impresión de que los CRDT al final empujan los conflictos de fusión desde la base de datos hacia la lógica de la aplicación
Si están bien escritos, pueden lograr resolución automática de fusiones sin importar en qué capa estén
El mayor problema fue manejar los conflictos de UNIQUE/PRIMARY KEY
Se puede resolver asignando un namespace de ID a cada servidor, haciendo que gane la primera creación, y renombrando o eliminando en caso de conflicto
Si usas un esquema EAV, puedes implementar fácilmente el recorrido de grafos en SQL con CTE recursivos
Aun así, PostgreSQL no tiene tipo ANY, así que es difícil representar objetos con atributos variados, y la funcionalidad de FOREIGN KEY también hay que implementarla por cuenta propia
Aun así, la estructura EAV es favorable para el diseño de metaesquemas como la herencia
Sería bueno poder definir tipos CRDT directamente en PostgreSQL, pero por ahora no es posible restringir operaciones monoid
Al final, los CRDT para columnas que no son clave tienen que manejarse en la capa de la aplicación
En resumen, los CRDT sí pueden implementarse dentro de un RDBMS, pero el enfoque cambia según dónde pongas la lógica de negocio