Dónde vive el reloj: causalidad dentro de un CRDT

Las cuatro lecciones anteriores han construido una herramienta pequeña y precisa: una relación de precedencia, un contador que la respeta y un desempate que la completa. Falta ver dónde encaja todo eso, y la respuesta es más ubicua de lo que parece. Cuando abras las estructuras de los niveles siguientes, contadores, conjuntos, registros, mapas y secuencias, descubrirás que casi todas llevan un reloj dentro, a veces a la vista y a veces disuelto en la forma de sus identificadores. No es una coincidencia ni una moda de diseño: es la consecuencia directa de haber renunciado a un servidor. La autoridad que antes imponía un orden a las operaciones ha desaparecido, y el orden que aportaba hay que reconstruirlo dentro de los propios datos. Esta lección hace el mapa de esa reconstrucción y deja planteada la carencia que el nivel siguiente viene a cubrir.

Las tres preguntas que un CRDT le hace al orden

Todas las necesidades de orden de una estructura replicada se reducen a tres preguntas distintas, con exigencias muy distintas, y confundirlas es el origen de la mayoría de los diseños rotos.

Las tres están ordenadas por exigencia creciente, y esa jerarquía es en sí misma una guía de diseño: cada escalón cuesta más que el anterior en metadatos y en complejidad, de modo que la pregunta correcta al modelar no es cuál te gustaría responder sino cuál es la más barata que resuelve tu problema.

La primera es ninguna pregunta. Si las operaciones de la estructura conmutan, son asociativas e idempotentes, el resultado no depende del orden en que se apliquen y no hace falta ningún reloj. Es el caso de un conjunto que solo crece o de un contador que solo suma: la fusión es una unión o un máximo elemento a elemento, y da igual quién hizo qué antes. Es la situación ideal y la razón por la que estas estructuras se estudian primero.

La segunda es cuál gana. Cuando la estructura tiene que quedarse con un valor entre varios, necesita un orden total, y ese orden es exactamente el de la lección anterior: contador lógico y, en caso de empate, identificador de réplica. Basta un reloj de Lamport, porque lo único que se le pide es decidir siempre y decidir igual en todas partes.

La tercera es si hubo concurrencia, y es de otra naturaleza. Aquí no se quiere un ganador, se quiere saber si dos operaciones se conocían entre sí, y para eso hace falta poder distinguir un par ordenado causalmente de un par incomparable. Un reloj de Lamport no puede responderla, por lo que se estableció en la tercera lección: comprime el grafo en un entero y destruye la información de concurrencia. Responder esta tercera pregunta exige una estructura con una entrada por réplica, que es el asunto del nivel siguiente.

Identificar cuál de las tres necesita una entidad concreta es una decisión de modelado que conviene tomar antes de escribir código, y hay un criterio sencillo para acertar: mira qué querrías que ocurriera si dos personas la modifican a la vez sin verse. Si la respuesta es que ambas modificaciones deben conservarse, estás en el primer caso y buscas una operación que conmute. Si la respuesta es que solo tiene sentido una y da igual cuál mientras todos vean la misma, estás en el segundo. Y si la respuesta es que hay que avisar, mostrar las dos versiones o dejar que alguien decida, estás en el tercero y vas a necesitar más que un contador. Ese pequeño ejercicio, hecho campo por campo, ahorra reescrituras enteras.

flowchart TB
Q[Que le pide la estructura al orden] --> N[Nada porque las operaciones conmutan]
Q --> W[Cual gana entre dos valores]
Q --> C[Hubo concurrencia entre dos operaciones]
N --> N1[Contadores y conjuntos que solo crecen]
W --> W1[Basta contador de Lamport mas identificador]
C --> C1[Hace falta una entrada por replica]
style N1 fill:#a6e3a1,color:#11111b
style W1 fill:#89b4fa,color:#11111b
style C1 fill:#f9e2af,color:#11111b

Un recorrido por las estructuras

Antes del recorrido conviene fijar el vocabulario mínimo, porque las tres piezas que aparecen una y otra vez tienen nombre propio y verlas escritas ayuda a reconocerlas después bajo cualquier disfraz.

// 1. El sello de una escritura: contador logico e identificador de replica
const sello = { t: 17, replica: "r-7f3a" };

// 2. La marca unica de una adicion: identifica esa aportacion concreta
const marca = { replica: "r-7f3a", n: 42 };

// 3. El conjunto de marcas observadas al eliminar algo
const observadas = [
  { replica: "r-7f3a", n: 42 },
  { replica: "r-91bd", n: 8 },
];

Las tres son variaciones del mismo material. El sello sirve para decidir; la marca sirve para identificar; el conjunto de observadas sirve para recordar qué se sabía en el momento de actuar. La tercera es la única que crece, y no por casualidad: es la que responde a la tercera pregunta.

Los contadores son el caso limpio. Un contador que solo crece se representa como un mapa de réplica a cantidad, la fusión toma el máximo de cada entrada y el valor es la suma. No hay reloj, no hay conflicto y no hay desempate posible porque no hay nada que decidir. Conviene notar, eso sí, que ese mapa de réplica a número tiene exactamente la misma forma que un vector de versiones: la diferencia está en lo que cuenta cada entrada, no en la estructura.

Los conjuntos dependen por completo del borrado. Un conjunto que solo añade no necesita nada. En cuanto se puede eliminar, aparece la pregunta de qué ocurre si una réplica añade un elemento mientras otra lo borra, y la respuesta más usada consiste en que cada adición reciba una marca única, típicamente el par identificador de réplica y contador, y que la eliminación arrastre consigo el conjunto de marcas que estaba observando. Un elemento sigue presente si tiene alguna marca que nadie ha eliminado, con lo que una adición concurrente con un borrado sobrevive. Ahí ya hay causalidad: las marcas que la eliminación observó son un registro de lo que su réplica sabía.

Los registros son donde las dos últimas preguntas se separan con más nitidez, y la distinción merece atención porque es la trampa clásica. El registro de última escritura necesita solo la segunda pregunta y por eso se implementa con un sello de Lamport y desempate por identificador. El registro multivalor necesita la tercera: su propósito es conservar todos los valores escritos concurrentemente y descartar únicamente los que fueron sobrescritos por alguien que los había visto. Intentar construir un registro multivalor con un reloj de Lamport es un error frecuente y su síntoma es característico: la estructura no detecta conflictos que sí existen y se comporta como un registro de última escritura disfrazado.

Las secuencias, que son el caso difícil y ocuparán varios niveles, llevan el orden en el propio identificador de cada elemento. Cada carácter o elemento insertado recibe un identificador construido con un contador y el identificador de la réplica, y la posición se determina de forma relativa a un elemento previo. Cuando dos réplicas insertan concurrentemente en el mismo punto, la decisión de cuál va delante se toma comparando esos identificadores, es decir, con exactamente el mismo desempate arbitrario y determinista de la lección anterior. El reloj no está en un campo aparte: está disuelto en la identidad de cada elemento.

Esa disolución del reloj dentro del identificador es probablemente el motivo por el que tanta gente lee el código de una biblioteca de secuencias y no encuentra el reloj por ninguna parte. No hay ningún campo llamado así, no hay ninguna clase que lo represente y sin embargo está en todas partes: en cada identificador, en cada comparación de inserciones y en cada decisión sobre qué elemento va delante. Reconocerlo requiere haber hecho antes el camino de estas cuatro lecciones, y una vez reconocido ya no se deja de ver.

Los mapas y documentos anidados heredan la maquinaria de sus componentes y añaden un problema propio, el de la eliminación de claves, que vuelve a plantear la tercera pregunta con la misma forma que en los conjuntos. Y las estructuras que se sincronizan mediante incrementos, en lugar de enviar el estado completo, llevan un contexto causal explícito que describe qué actualizaciones ha visto ya la réplica, para poder pedir y aplicar solo lo que falta. La familia entera de estos tipos fue caracterizada y sistematizada por Shapiro, Preguiça, Baquero y Zawirski en 2011, pero el ingrediente que todas comparten es anterior y viene del artículo de Lamport de 1978, Time, Clocks, and the Ordering of Events in a Distributed System, publicado en Communications of the ACM 21, número 7, páginas 558 a 565.

Si abres el estado interno de cualquiera de las bibliotecas de uso extendido encontrarás siempre la misma pareja, con nombres distintos: un identificador de cliente o actor y un contador que crece con cada operación que ese cliente produce. Ese par identifica de manera única cada operación del sistema entero sin necesidad de coordinación, sirve de referencia estable para que otras operaciones apunten a ella y, cuando hace falta desempatar, se compara exactamente como se describió en la lección anterior. Reconocer esa pareja al leer código ajeno es la manera más rápida de orientarse en una implementación desconocida, porque a partir de ella se deduce casi todo lo demás.

El patrón, visto en conjunto, es nítido: cuanto más rica es la estructura y más operaciones admite, más causalidad necesita guardar. Un contador no guarda ninguna, un registro guarda un sello, un conjunto guarda una marca por elemento y una secuencia guarda una por posición.

El coste que arrastra el reloj

Los conjuntos que solo crecen y los registros de solo adición merecen una mención aparte por lo que enseñan: si tu modelo puede evitar el borrado y la sobrescritura, evita también toda la maquinaria. Un registro de eventos al que solo se añade converge por unión y no necesita reloj para fusionarse, aunque quiera uno para ordenarse al mostrarse, que es una necesidad muy distinta y mucho más barata. Reformular una entidad mutable como una secuencia de hechos inmutables es, con frecuencia, la forma más eficaz de eliminar un conflicto en lugar de resolverlo.

Nada de esto es gratis, y el precio se paga en metadatos, que es la magnitud que de verdad decide si una aplicación local-first es viable en un dispositivo real. Un reloj de Lamport cuesta un entero por réplica y es despreciable. Una estructura con una entrada por réplica crece con el número de réplicas que hayan escrito alguna vez, no con las que estén activas, y en una aplicación con años de uso y muchos dispositivos esa distinción importa. Las marcas por elemento de un conjunto o de una secuencia multiplican el coste por el número de elementos, y en documentos de texto es habitual que los metadatos superen con holgura al contenido.

Hay además un coste que no se mide en bytes y que suele aparecer más tarde: el de la compatibilidad. Los metadatos causales forman parte del formato en el que se guardan y se intercambian los datos, así que cambiar la forma del reloj es un cambio de formato, con su migración y su periodo en el que conviven réplicas viejas y nuevas. Pasar de un contador a una estructura por réplica no es una refactorización interna: obliga a que las dos representaciones se entiendan durante un tiempo, porque habrá dispositivos que no se abran en meses. Elegir bien la tercera pregunta desde el principio, aunque cueste más, es mucho más barato que responderla después.

A eso se suman las lápidas. Un elemento borrado no puede desaparecer del todo mientras alguna réplica pueda no haberse enterado del borrado, porque si desapareciera reaparecería en la siguiente fusión con quien todavía lo tenga. Recogerlas exige saber que todas las réplicas han visto ya cierto punto de la historia, una propiedad que se llama estabilidad causal y que solo se puede establecer con información por réplica. La consecuencia es incómoda y conviene anticiparla: la limpieza de metadatos requiere la misma maquinaria que la detección de concurrencia, así que una estructura que ahorra en relojes suele acabar sin poder liberar espacio.

// Un punto causal: quien lo produjo y cual de sus operaciones fue
const punto = { replica: "r-7f3a", n: 42 };

// Un contexto causal describe que puntos ha visto ya esta replica
const contexto = { "r-7f3a": 42, "r-91bd": 17 };

function yaVisto(ctx, p) {
  return (ctx[p.replica] ?? 0) >= p.n;
}

De ese coste se sigue una recomendación de diseño que atraviesa todo el track y que conviene adelantar aquí: no conviertas todo tu modelo de datos en un CRDT. La causalidad se paga por cada elemento que la lleva, y en una aplicación real solo una parte de los datos se edita de forma concurrente y sin conexión. El texto de un documento compartido lo necesita; el catálogo de países, las preferencias que solo toca su dueño en un dispositivo o los registros de auditoría que únicamente se añaden, no. Reservar la maquinaria para donde hay concurrencia verdadera y usar estructuras corrientes en el resto es lo que separa una aplicación que arranca en un segundo de una que tarda medio minuto en cargar sus metadatos.

Y conviene recordar que ese peso no se reparte por igual: recae entero sobre el dispositivo del usuario, que es quien guarda la réplica. Un coste que en un servidor sería anecdótico puede aquí agotar la cuota del navegador o alargar el arranque hasta hacerlo inaceptable.

Lo que falta y llega a continuación

Antes de cerrar conviene decir qué se hace con todo esto cuando uno no va a escribir su propio CRDT, que es la situación normal. La respuesta no es que el nivel sobre entonces, sino que cambia de uso: pasa de ser un manual de construcción a ser un manual de lectura. Elegir una biblioteca consiste en averiguar qué preguntas sobre el orden responde cada una, qué metadatos guarda por elemento, si puede recoger sus lápidas y qué expone al programador cuando dos ediciones fueron concurrentes. Esas cuatro preguntas se formulan en el vocabulario de este nivel, y sin él las comparaciones entre bibliotecas se quedan en listas de características que no dicen nada.

El resumen del nivel cabe en tres frases. La hora del sistema no ordena nada porque no es fiable ni comparable. La precedencia causal sí ordena, pero solo parcialmente, y esa parcialidad es una descripción exacta del mundo y no una carencia del método. Un contador de Lamport comprime esa relación en un entero, conserva la implicación en un sentido, pierde la del otro y, completado con el identificador de réplica, produce un orden total determinista suficiente para decidir ganadores.

Conviene subrayar que ninguna de esas tres frases depende de qué biblioteca elijas ni de qué motor de sincronización acabes usando. Son propiedades del problema, no de una implementación concreta, y por eso siguen siendo verdad cuando cambias de herramienta. Ese es el motivo por el que este nivel se estudia antes que cualquier estructura concreta: lo que se aprende aquí es lo único que no queda obsoleto cuando la biblioteca de moda es otra.

Lo que queda pendiente está localizado con precisión: no se puede distinguir un par causalmente ordenado de un par concurrente, y por tanto no se puede saber si hay conflicto. Esa carencia bloquea el registro multivalor, la recogida de lápidas, la sincronización eficiente por diferencias y cualquier interfaz que quiera mostrar al usuario que dos personas editaron a la vez. La solución conocida consiste en dejar de comprimir y guardar una entrada por réplica, con su coste en espacio y su necesidad de podar, y en combinar además esa información con el tiempo físico para recuperar algo parecido a una fecha legible sin renunciar a la corrección. Vectores de versiones y relojes lógicos híbridos son el contenido del nivel siguiente.