Experimentos · JavaScript: From Closures to Autonomous Systems · Capítulo 17

Dos réplicas sin conexión

Tipos de datos replicados sin conflictos (CRDT)

Tema
PruébeloDos réplicas sin conexión
Cambia un contador, un carrito y reservas en dos réplicas y luego fusiónalas en cualquier orden, tantas veces como quieras. Verás cómo «gana el último en escribir» pierde una suma, cómo la unión devuelve la pelota eliminada y cómo un CRDT fusiona honradamente dos reservas para un asiento.

Todo se calcula en tu navegador; no se envía nada.

Sobre este experimento

¿Qué es un CRDT?

Un CRDT, tipo de datos replicado sin conflictos, es una estructura de datos pensada para que réplicas modificadas por separado siempre puedan fusionarse sin coordinación, y el resultado no depende del orden ni de cuántas veces las réplicas intercambian su estado. Las réplicas que han visto los mismos cambios llegan al mismo estado. Un G-Counter guarda una celda por réplica y las suma; un OR-Set etiqueta cada adición, y una eliminación borra solo las etiquetas que ha visto. Marc Shapiro y sus colegas formalizaron la idea en 2011. Un CRDT garantiza la convergencia, no que el estado fusionado respete las reglas de la aplicación.

Cuando un sistema elige la disponibilidad durante una partición de red, sus réplicas siguen trabajando por separado y hay que fusionarlas cuando vuelve la conexión. El artículo de Amazon sobre Dynamo, de 2007, tenía como ejemplo principal el carrito de la compra y fusionaba carritos divergentes por unión: un artículo añadido nunca se pierde y uno eliminado puede volver. Muchos almacenes simplemente dejan que gane la última escritura. Los CRDT llevan la regla de fusión a la propia estructura de datos.

Elige una pestaña y edita las dos réplicas, un móvil y un portátil, que no se ven entre sí. Luego pulsa «Fusionar A y B», «Fusionar otra vez» y «Fusionar en el otro orden», o reproduce el escenario del libro. El contador pone «gana el último en escribir» junto a un G-Counter. El carrito pone la unión de conjuntos junto a un OR-Set y permite quitar un artículo en una réplica mientras se vuelve a poner en la otra. La pestaña de asientos tiene un asiento libre, un botón de reserva en cada réplica, un enlace que se puede cortar y la elección entre responder ya y ponerse de acuerdo antes.

En el libro, en Node 24.16.0, un contador en 5 con +1 en cada réplica se fusionó en 6 con «gana el último en escribir» y en 7 como G-Counter, en cualquier orden y al fusionar otra vez. El carrito {libro, pelota}, con la pelota quitada en una réplica y un bolígrafo añadido en la otra, salió de la unión como libro, pelota y bolígrafo, y del OR-Set como libro y bolígrafo. Cuando la pelota se quitó en una réplica y se volvió a poner en la otra, ganó la adición. Un asiento libre reservado en las dos réplicas se convirtió en 2 reservas, y la regla «no más reservas que asientos» se rompió.

Lo esencial del capítulo está en la última pestaña. Un CRDT promete que las réplicas convergen, no que el resultado tenga sentido. Reglas como no vender más asientos de los que hay o no dejar una cuenta en negativo exigen que las réplicas se pongan de acuerdo antes de responder al usuario, y ninguna estructura de datos elimina esa exigencia. Dónde deben coordinarse las réplicas y cuánta latencia vale eso lo decide el programador.

Del libro

JavaScript: From Closures to Autonomous Systems · Capítulo 17

The Limits of Consistency

Junto a este experimento en el capítulo
The last mode of the experiment shows this. There is one free seat in the hall, and two people book it on two copies that cannot see each other at that moment. The bookings counter merges into two without a single conflict, because CRDTs have no conflicts by construction. Only there was one seat. In 2014 Peter Bailis and his co-authors worked out which data integrity rules can be preserved without coordination between copies and which cannot. A rule like «do not sell more seats than exist» or «do not let the account go negative» requires the copies to agree before answering the user. No data structure can remove that need.

El libro se muestra en inglés