Identificadores de posición: el sitio como propiedad inmutable

Ya sabemos qué hay que abandonar. Toca construir el sustituto, y la idea es tan simple de enunciar que cuesta creer que sostenga treinta años de investigación: en el instante en que un elemento entra en la lista se le asigna un identificador que dice dónde está, y ese identificador no se modifica nunca, pase lo que pase alrededor. Si alguien borra veinte elementos anteriores, el identificador no cambia. Si alguien inserta cien delante, tampoco. La posición deja de ser el resultado de contar y pasa a ser una propiedad que el elemento lleva encima, como su contenido. Esta lección desarrolla esa idea hasta sus consecuencias: qué exigimos exactamente de esos identificadores, qué le ocurre al tipo lista cuando los adopta, y qué facturas empiezan a llegar en cuanto lo hace.

De contar a llevar el sitio encima

Compara las dos frases que puede pronunciar una operación de inserción. La primera es coloca esto en la cuarta posición, que obliga al receptor a contar y por tanto depende de lo que el receptor tenga. La segunda es coloca esto en el sitio p, donde p es un valor de un conjunto totalmente ordenado que el emisor eligió. La segunda frase no depende de nada que el receptor sepa: es una afirmación sobre el elemento, no sobre su entorno, y por eso puede llegar tarde, dos veces o antes que operaciones anteriores sin perder su sentido.

La diferencia entre ambas frases es la misma que hay entre dar una dirección postal y dar unas indicaciones para llegar. Las indicaciones dependen de dónde esté quien las recibe y de que el camino no haya cambiado; la dirección vale para cualquiera y desde cualquier sitio, y a cambio hay que escribirla entera.

El requisito que hace posible ese cambio de tipo de frase es la inmutabilidad, y hay que subrayarlo porque es donde fallan las medias tintas. Un campo numérico de orden que se reescribe al reordenar no es un identificador de posición: es un índice con otro nombre, y hereda todos sus problemas porque vuelve a ser una asignación concurrente sobre un valor compartido. Lo que da la propiedad es la promesa de no tocarlo, no el hecho de que sea un decimal en lugar de un entero.

flowchart LR
A[indice tres] --> B[hay que contar en el estado actual]
B --> C[el referente cambia si cambia el prefijo]
D[identificador p] --> E[no hay que contar nada]
E --> F[el referente es el mismo en toda replica]
style C fill:#f38ba8,color:#11111b
style F fill:#a6e3a1,color:#11111b

Conviene notar que el elemento pasa a tener dos identidades distintas y que confundirlas causa errores sutiles. Una es la identidad del elemento en sí, que sirve para saber si dos réplicas hablan del mismo objeto y para borrarlo; la otra es su identidad de posición, que sirve para ordenarlo frente a los demás. Muchos algoritmos las funden en un único valor por economía, y muchas implementaciones se enredan justamente ahí, cuando quieren mover un elemento y descubren que cambiarle la posición equivale a cambiarle el nombre.

Hay una segunda confusión que conviene desactivar ya, y es creer que el identificador guarda la posición numérica del elemento. No guarda nada parecido: guarda un punto de un espacio abstracto cuyo único cometido es poder compararse con los demás. Que el elemento sea el cuarto de la lista no es un dato almacenado en ninguna parte, es el resultado de contar cuántos identificadores vivos hay por delante en el momento de mirar. La consecuencia de diseño es importante y no siempre se anticipa: preguntar por el índice de un elemento pasa a ser una operación que cuesta, mientras que preguntar si un elemento va antes que otro pasa a ser gratis. Esa inversión de costes es la que obliga a repensar bastantes interfaces.

Las cuatro exigencias

No sirve cualquier valor como identificador de posición. La familia entera de algoritmos de secuencia se puede leer como distintas maneras de satisfacer estas cuatro condiciones a la vez, y perder cualquiera de ellas rompe algo concreto y demostrable.

Cada una de las cuatro se puede perder por separado y cada pérdida rompe algo distinto, lo cual es útil como lista de diagnóstico. Si pierdes el orden total, hay pares de elementos que ninguna réplica sabe ordenar y la lectura deja de ser determinista. Si pierdes la inmutabilidad, vuelven las asignaciones concurrentes sobre un valor compartido y con ellas todo el problema original. Si pierdes la unicidad, dos elementos ocupan el mismo punto y el orden entre ellos depende de qué haga cada réplica con el empate. Y si pierdes la densidad, llega un momento en que no se puede insertar entre dos vecinos y el sistema no tiene ninguna respuesta razonable que dar.

Las dos primeras ya están justificadas. La tercera se resuelve casi siempre del mismo modo: el identificador incluye el nombre de la réplica que lo creó, de forma que dos réplicas distintas no pueden colisionar aunque elijan la misma región del espacio de posiciones. Ese apéndice de réplica sirve además como desempate determinista, lo cual es imprescindible: cuando dos inserciones concurrentes eligen el mismo hueco, alguien tiene que ir primero, y esa decisión debe salir del propio dato para que todas las réplicas lleguen a la misma sin hablar entre sí.

La cuarta exigencia es la que decide si todo esto funciona o no, y es tan importante que tiene la lección siguiente entera para ella sola. Aquí basta con ver por qué es inevitable: si dos elementos son adyacentes y alguien quiere escribir entre ellos, hace falta un identificador estrictamente intermedio, y como esa situación puede repetirse indefinidamente, el espacio de identificadores no puede agotarse nunca.

Hay además dos exigencias implícitas que no suelen figurar en las listas y que muerden en producción. La primera es que la comparación sea barata, porque está en el camino crítico de cada inserción y de cada lectura ordenada; un identificador correcto pero costoso de comparar convierte el editor en un producto lento sin dejar de ser correcto. La segunda es que sea serializable de forma compacta, porque cada identificador viaja por la red en cada sincronización y se guarda en disco para siempre. Ambas son razones por las que las implementaciones serias acaban usando representaciones binarias comparables byte a byte en lugar de las estructuras legibles con las que se explica el concepto.

// Un identificador de posicion minimo: valor de orden mas replica para desempatar
function crearId(clave, replica) {
  return { clave, replica };
}

function comparar(a, b) {
  if (a.clave !== b.clave) return a.clave < b.clave ? -1 : 1;
  if (a.replica !== b.replica) return a.replica < b.replica ? -1 : 1;
  return 0; // identicos: es literalmente el mismo elemento
}

comparar(crearId("0.5", "movil"), crearId("0.5", "portatil")); // -1, sin hablar

La lista se convierte en un conjunto ordenado

Con los identificadores en su sitio, el tipo cambia de naturaleza y esa es la recompensa de todo el rodeo. Una lista replicada deja de ser una secuencia y pasa a ser un conjunto de pares formados por identificador de posición y contenido. Y de los conjuntos ya lo sabemos todo: se fusionan por unión, la unión es conmutativa, asociativa e idempotente, y la convergencia sale gratis del álgebra que el nivel de los conjuntos estableció.

// La lista replicada como conjunto de pares mas una lectura ordenada
function fusionar(a, b) {
  const salida = new Map(a);
  for (const [id, valor] of b) salida.set(id, valor);
  return salida; // union: conmutativa, asociativa e idempotente
}

function leer(mapa) {
  return [...mapa.entries()]
    .sort((x, y) => (x[0] < y[0] ? -1 : 1))
    .filter(([, v]) => v !== null) // los borrados dejan lapida
    .map(([, v]) => v);
}

Fíjate en dónde ha ido a parar cada responsabilidad, porque esa redistribución es el resultado importante. La fusión no sabe nada de orden y por eso es trivial de escribir y de demostrar. El orden vive íntegramente en la función de comparación de identificadores, que es una función pura sobre dos valores y no consulta el estado. Y la lectura es una ordenación corriente. Toda la dificultad del problema se ha concentrado en un único punto —cómo se generan los identificadores— y ese punto es exactamente el asunto de las dos lecciones que quedan.

Esta separación tiene además un beneficio de ingeniería que conviene aprovechar desde el primer día. Como el generador de identificadores es una función aislada con una firma pequeña, se puede sustituir sin tocar nada más: la fusión, el borrado, la lectura y las pruebas de convergencia siguen valiendo igual. Eso permite empezar con un generador ingenuo mientras se construye el resto del sistema, medir con datos reales, y cambiarlo después por uno serio sin reescribir la aplicación. Pocas decisiones de arquitectura admiten un aplazamiento tan limpio, y desaprovecharlo por querer elegir el algoritmo perfecto antes de tener usuarios es un error frecuente.

Las tres facturas que llegan de inmediato

Nada de esto es gratis, y merece la pena enumerar los costes antes de que aparezcan por sorpresa en un perfil de memoria. El primero es el espacio: cada elemento arrastra un identificador, y en una lista de caracteres ese identificador suele pesar más que el propio carácter. Un documento de texto puede acabar con varias veces su tamaño en metadatos de posición, y ese factor es el que decide si un editor colaborativo abre un fichero grande en medio segundo o en veinte.

Conviene además distinguir dos formas de medir ese espacio que suelen confundirse en las comparativas. Una cosa es lo que el documento ocupa en disco, donde la compresión y los formatos binarios hacen maravillas porque los identificadores de elementos vecinos comparten casi todos sus prefijos. Otra muy distinta es lo que ocupa en memoria mientras se edita, donde cada identificador vive expandido en estructuras con punteros y el factor de multiplicación puede ser considerable. Un algoritmo puede ganar holgadamente en la primera medida y perder en la segunda, y cuál de las dos importa depende de si tu problema es sincronizar o es abrir.

El segundo es la comparación. Ordenar por identificador exige compararlos, y si el identificador no es un número máquina sino una estructura de longitud variable, cada comparación recorre elementos hasta encontrar la diferencia. Como esa comparación está en el camino crítico de toda inserción, su coste se multiplica por el número de pulsaciones, y es el motivo por el que las representaciones compactas y comparables byte a byte son un asunto tan trabajado en las implementaciones serias.

El tercero es el borrado, y es el más incómodo porque no se arregla optimizando. Si borras un elemento y eliminas su identificador, pierdes el punto de referencia que otras réplicas podrían estar usando para insertar junto a él, y una inserción que llegue tarde no sabrá dónde iba. Por eso el borrado deja lápida: el par sigue en el conjunto con su contenido marcado como ausente. Las lápidas son las mismas del nivel de conjuntos, con el agravante de que aquí no se pueden podar alegremente, porque cada una sostiene la estructura del orden.

Hay un matiz que distingue los dos polos que veremos en la última lección y que conviene anticipar aquí, porque cambia mucho la severidad de esta tercera factura. Si el identificador es absoluto, es decir, si codifica la posición sin referirse a ningún otro elemento, la lápida solo necesita conservar la posición y puede tirar el contenido; incluso se puede llegar a tirar la lápida entera si se demuestra que ninguna réplica viva puede referirse a ella. Si el identificador es relativo, definido como justo detrás de aquel otro, entonces el ancla es estructuralmente necesaria y no se puede eliminar sin romper a quien llegue tarde. La misma factura, dos importes muy distintos.