El mapa: claves con semántica de conjunto observado y valores que son CRDT

El mapa es la pieza que convierte la clausura del teorema anterior en algo con lo que se puede trabajar de verdad, porque es la única de las tres formas de anidar cuyo conjunto de coordenadas cambia con el uso. Un producto de campos fijos no plantea preguntas: las claves existen desde el primer día y existirán siempre. Un mapa, en cambio, tiene que responder qué significa que una clave aparezca, qué significa que desaparezca y, sobre todo, qué significa que ambas cosas ocurran a la vez en réplicas distintas. La respuesta canónica combina dos mecanismos que ya conoces por separado —el conjunto con eliminación observada para las claves y la estructura convergente que corresponda para cada valor— y esa combinación es tan natural que resulta fácil pasar por alto el punto exacto donde deja de ser obvia. Ese punto tiene nombre propio: borrar una clave mientras otra réplica escribe dentro de ella. Es el caso que ninguna librería puede evitar, que todas resuelven de forma distinta y que decide buena parte de cómo se siente el producto.

Dos estructuras superpuestas

Un mapa convergente no es una estructura sino dos que comparten el mismo espacio de nombres. La primera gobierna la presencia: qué claves existen en este momento. La segunda gobierna el contenido: qué hay dentro de cada clave existente, y esa segunda es en realidad tantas estructuras como claves haya, cada una con su propia política.

La capa de presencia no puede ser un simple conjunto de cadenas, porque un conjunto de cadenas no sabe fusionarse: si una réplica añade la clave y otra la quita, unir los conjuntos da la clave presente y restar los conjuntos da la clave ausente, y ninguna de las dos operaciones es más justificable que la otra. La solución es la misma que ya se usó para los conjuntos: cada alta genera una etiqueta única y la baja solo elimina las etiquetas que quien borra tenía delante en ese momento. Una clave está presente si le queda al menos una etiqueta viva. Con eso, la presencia deja de ser una pregunta ambigua y pasa a ser una consecuencia mecánica de qué observó cada réplica.

Merece la pena descartar de forma explícita las dos alternativas más simples, porque ambas se proponen en cualquier discusión de diseño y ambas fallan por motivos instructivos. Un conjunto que solo crece converge sin esfuerzo pero no sabe eliminar, así que una clave puesta por error se queda para siempre. Un conjunto de dos fases sí elimina, pero su eliminación es definitiva, de modo que una clave borrada no puede volver a usarse nunca aunque alguien la fije otra vez mucho después con pleno conocimiento; en un mapa cuyas claves son nombres de campo o identificadores reutilizables, esa restricción es inaceptable. La eliminación observada es la estructura más simple que satisface las dos exigencias a la vez: borrar de verdad y poder volver a poner.

// Capa de presencia: la clave existe si conserva alguna etiqueta viva
function fijarClave(mapa, clave, replica) {
  const etiqueta = `${replica}:${crypto.randomUUID()}`;
  const vivas = new Set([...(mapa.presencia[clave] ?? []), etiqueta]);
  return { ...mapa, presencia: { ...mapa.presencia, [clave]: vivas } };
}

function borrarClave(mapa, clave) {
  const observadas = mapa.presencia[clave] ?? new Set();
  return {
    ...mapa,
    presencia: { ...mapa.presencia, [clave]: new Set() },
    lapidas: new Set([...mapa.lapidas, ...observadas]),
  };
}

La capa de contenido se apoya directamente en el teorema de clausura. Cada clave lleva asociada una estructura convergente cualquiera —un registro, un contador, un conjunto, una secuencia u otro mapa— y la fusión del mapa completo es la fusión de la presencia por unión de etiquetas más la fusión de cada valor con su propia política. Que el mapa entero converja no requiere ningún argumento nuevo: es el producto disperso de la lección anterior, con el conjunto de etiquetas actuando como capa de índice.

Borrar una clave es borrar un subárbol

Aquí conviene detenerse, porque la formulación ingenua del borrado esconde una recursión. Si el valor de la clave es un escalar, quitar sus etiquetas de presencia basta y no hay nada más que decir. Si el valor es a su vez una estructura compuesta —y en un documento real lo será casi siempre— entonces la clave es la raíz de un subárbol entero, y borrarla significa dar por eliminadas todas las operaciones que sostienen ese subárbol.

La semántica de eliminación observada se extiende al caso recursivo de la única forma que preserva sus propiedades: el borrado elimina exactamente las operaciones del subárbol que quien borra había observado, y no toca las demás. Dicho de otro modo, un borrado no es una orden absoluta sino una afirmación relativa a un contexto causal: quien borra dice que lo que él vio dentro de esa clave debe desaparecer. Lo que no vio queda fuera del alcance de su afirmación, y no porque la implementación sea perezosa, sino porque cualquier otra opción rompería la convergencia. Un borrado que eliminara también lo no observado dependería del momento de aplicación, y una operación cuyo efecto depende del momento de aplicación no conmuta.

// El borrado recoge el contexto causal de todo el subarbol
function contextoObservado(nodo, acumulado = new Set()) {
  for (const etiqueta of nodo.etiquetas ?? []) acumulado.add(etiqueta);
  for (const hijo of Object.values(nodo.hijos ?? {})) contextoObservado(hijo, acumulado);
  return acumulado;
}

// Y solo eso queda marcado como eliminado
function borrarSubarbol(mapa, clave) {
  return { ...mapa, lapidas: new Set([...mapa.lapidas, ...contextoObservado(mapa.valores[clave])]) };
}

La consecuencia práctica del carácter recursivo es que el coste de un borrado no es constante sino proporcional al tamaño del subárbol, y que el registro de lo eliminado tampoco es una marca sino un conjunto. En un documento con miles de nodos, borrar la raíz de una sección grande produce un contexto de eliminación de miles de identificadores, y ese contexto tiene que viajar y almacenarse hasta que se pueda demostrar que ya nadie lo necesita.

De ahí sale una consecuencia de rendimiento que sorprende la primera vez que se mide y conviene anticipar: en un documento convergente borrar es más caro que escribir, y a veces por mucho. Escribir toca un nodo y añade una operación; borrar recorre un subárbol, recoge su contexto completo y emite una operación cuyo tamaño es proporcional a lo eliminado. La interfaz que permite seleccionar cien elementos y borrarlos de un gesto está emitiendo, sin que nadie lo perciba, la operación más pesada que el sistema sabe producir. Vale la pena medirlo con volúmenes reales antes de ofrecer ese gesto, y considerar agrupar la eliminación masiva en una sola operación con un contexto compartido en lugar de cien operaciones independientes.

El caso difícil, en detalle

Vamos al escenario concreto, que conviene tener escrito con nombres y no en abstracto. Dos réplicas parten del mismo estado: el mapa tiene una clave con un valor compuesto que ambas han visto. Sin conexión entre ellas, la primera borra la clave completa. La segunda, sin haber visto ese borrado, escribe dentro del valor: añade un elemento a una lista anidada, incrementa un contador, cambia un campo. Cuando ambas sincronizan, la unión tiene que producir algo.

flowchart TD
E0[estado comun con la clave notas y su valor visto por las dos] --> A[replica A borra la clave notas]
E0 --> B[replica B escribe dentro del valor de notas]
A --> S[sincronizacion]
B --> S
S --> R1[la clave sobrevive con solo lo que A no habia observado]
S --> R2[la clave desaparece y la escritura de B se pierde]
R1 --> C1[el usuario ve un fragmento sin contexto]
R2 --> C2[el usuario ve desaparecer trabajo que hizo]
style R1 fill:#f9e2af,color:#11111b
style R2 fill:#f38ba8,color:#11111b

La primera salida es la que se sigue mecánicamente de la eliminación observada. El borrado de la primera réplica cubrió lo que ella vio; la escritura de la segunda no estaba en ese contexto, así que sobrevive. Y como el mapa dice que una clave existe cuando le queda algo vivo, la clave reaparece, pero no con su contenido anterior: reaparece con lo poco que la escritura concurrente introdujo. El resultado es un nodo mutilado —el elemento nuevo de una lista cuyos demás elementos ya no están, el contador con una única contribución, el registro con un solo campo— y ese estado es correcto según la definición, converge en todas las réplicas y a menudo es incomprensible para quien lo mira. Se le suele llamar resurrección parcial, y es el precio de no perder nada.

La segunda salida consiste en dar prioridad al borrado: si alguien eliminó la clave, la clave se va y con ella todo lo que hubiera dentro, observado o no. Es más fácil de explicar, produce documentos limpios y nunca deja fragmentos huérfanos. También destruye trabajo en silencio, porque la escritura concurrente desaparece sin dejar rastro y sin que quien la hizo reciba señal alguna. Y es exactamente el tipo de pérdida invisible que ya identificamos como el fallo más caro que puede cometer un sistema local-first.

Hay una tercera vía que no es una semántica sino una mitigación, y conviene distinguirla con cuidado de las dos anteriores para no creer que resuelve algo que no resuelve. Consiste en aceptar la primera salida y tratar el nodo mutilado como un objeto de primera clase en la interfaz: no se muestra mezclado con el contenido normal sino en una zona de recuperación, con la indicación de quién lo tocó, cuándo, y qué había antes si el registro lo permite. El algoritmo es idéntico y el estado del documento también; lo único que cambia es que el producto reconoce el fenómeno en vez de exponerlo crudo. Eso no elimina la disyuntiva —el usuario sigue teniendo que decidir— pero convierte una experiencia de sistema errático en una de sistema que explica lo que hizo, y esa diferencia es mucho mayor de lo que el coste de implementarla sugiere.

El residuo y su representación

La semántica observada tiene un coste de contabilidad que conviene mirar de frente, porque es la razón por la que un mapa convergente pesa mucho más que un mapa a secas. Para saber si una etiqueta sigue viva hay que recordar cuáles han sido eliminadas, y para saber si un borrado alcanza a una operación futura hay que recordar el contexto de ese borrado. Ambas cosas son lápidas, y las lápidas sobreviven a los datos que representan.

La representación habitual sustituye el conjunto explícito de lápidas por un resumen causal, que es mucho más barato. Si cada operación lleva un identificador de réplica y un número de secuencia, el conjunto de operaciones observadas por una réplica se describe con un vector, y preguntar si una etiqueta está eliminada se convierte en comparar su número contra ese vector. Se pasa así de guardar una entrada por elemento borrado a guardar una entrada por réplica, que es el cambio de escala que hace viable la técnica. El precio es el que ya vimos en el nivel de relojes: el vector crece con el número de réplicas y no admite poda segura sin apostar sobre el comportamiento de dispositivos reales.

// Con resumen causal, la pertenencia se decide comparando contra un vector
function claveViva(mapa, clave) {
  const etiquetas = mapa.presencia[clave] ?? [];
  return etiquetas.some((et) => !cubierta(et, mapa.contextoBorrado[clave]));
}

// Una etiqueta esta cubierta si el borrado ya habia visto esa operacion
function cubierta(etiqueta, contexto) {
  if (!contexto) return false;
  return (contexto[etiqueta.replica] ?? 0) >= etiqueta.secuencia;
}

Ese cambio de representación tiene además un efecto que suele pasar inadvertido y que conviene aprovechar: convierte la pregunta de si una clave está viva en una comparación de enteros, es decir, en algo que se puede evaluar sin materializar el conjunto de etiquetas eliminadas. En documentos con muchas claves eso es la diferencia entre recorrer el residuo en cada lectura y no tocarlo nunca, y es el motivo de que las implementaciones serias del mapa no guarden lápidas explícitas salvo en los casos en que el resumen causal no basta.

Hay una decisión de implementación que conviene tomar temprano y por escrito, porque después es cara de revertir: si el mapa permite reasignar una clave con un valor de tipo distinto. Fijar una clave que contenía una lista para que ahora contenga un texto no es una actualización sino un alta nueva con una estructura nueva, y la anterior queda como un subárbol cuyo contenido puede seguir recibiendo escrituras concurrentes. Las librerías que lo permiten acaban conservando las dos versiones y exponiendo una regla de desempate; las que lo prohíben trasladan el problema al esquema, que en documentos con vida larga es donde suele estar mejor.