Árbol de hashes: descender solo por las ramas que difieren

El mecanismo de la lección anterior es exacto y barato mientras se sostengan sus dos supuestos, y deja de servir en cuanto uno de los dos cae: cuando el historial se poda o cuando el censo de actores se desborda. Lo que hace falta entonces es un mecanismo que no recuerde nada sobre el interlocutor, que no dependa de que exista un registro de operaciones y que funcione comparando únicamente el estado presente de ambos lados. El nivel del Merkle DAG dejó demostrada la propiedad que lo hace posible: si dos identificadores coinciden, los subgrafos que cuelgan de ellos son idénticos. Aplicada no ya a un documento sino a un conjunto de claves, esa propiedad convierte la reconciliación en una búsqueda que descarta la mitad del espacio en cada comparación y localiza lo que difiere abriendo un puñado de nodos. La técnica es vieja, está probada en los almacenes distribuidos que sostienen internet y en el control de versiones que todo el mundo usa a diario, y tiene una precondición que casi nadie menciona al enseñarla y que es la que decide si funciona o no funciona: la forma del árbol tiene que ser una función del conjunto y no del camino por el que se llegó a él. Esta lección construye el mecanismo, cuantifica su coste con honestidad y explica esa precondición hasta el final.

Descender solo por lo que difiere

El punto de partida es colocar los elementos del conjunto en las hojas de un árbol de aridad fija y calcular el resumen de cada nodo interno a partir de los resúmenes de sus hijos, exactamente como establece la definición del nivel del Merkle DAG. Con esa estructura montada en ambos lados, la reconciliación empieza intercambiando dos raíces. Si coinciden, los conjuntos son idénticos y el protocolo termina con un mensaje de sesenta y cuatro bytes, que es el caso mayoritario en cualquier despliegue real. Si no coinciden, se pide el nodo raíz de cada lado, se comparan sus listas de resúmenes hijos y se conserva solo la lista de posiciones donde difieren.

Lo que hace que ese descenso sea barato no es la comparación en sí sino la poda, y conviene subrayar que la poda es una deducción y no una heurística. Descartar una rama porque su resumen coincide no es apostar a que probablemente sea igual: es concluir que lo es, con la fuerza de la resistencia a colisiones de la función de hash. Por eso el resultado del descenso no necesita verificación posterior, a diferencia de lo que ocurrirá en la lección siguiente con los filtros probabilísticos.

// La posicion de una clave la decide su hash, nunca el orden de llegada
function rutaDe(clave) {
  const h = hash(clave);                       // 32 bytes deterministas
  return [h[0] >> 4, h[0] & 15, h[1] >> 4];    // tres niveles de aridad 16
}

// Descenso comparativo: se abre solo lo que difiere
async function ramasQueDifieren(remoto, prefijo = []) {
  const [mio, suyo] = await Promise.all([nodo(prefijo), remoto.nodo(prefijo)]);
  if (mio.resumen === suyo.resumen) return [];
  if (mio.esHoja) return [{ prefijo, mias: mio.claves, suyas: suyo.claves }];
  const salida = [];
  for (let i = 0; i < mio.hijos.length; i++) {
    if (mio.hijos[i] !== suyo.hijos[i]) {
      salida.push(...await ramasQueDifieren(remoto, [...prefijo, i]));
    }
  }
  return salida;
}

La segunda línea de la primera función es toda la idea del mecanismo comprimida. La clave no se coloca en el árbol según cuándo llegó ni según su valor literal, sino según los bits de su resumen, que es un dato inmutable y calculable por cualquiera. Eso reparte las claves de forma uniforme, mantiene el árbol equilibrado sin rotaciones y, sobre todo, garantiza que dos réplicas con el mismo conjunto construyan el mismo árbol aunque hayan recibido las claves en orden distinto y en momentos distintos.

La condición que se olvida: la forma no puede depender de la historia

Aquí está el error de diseño que arruina más implementaciones de esta técnica, y es tan silencioso como caro. Si el árbol se construye con una estructura equilibrada convencional, de esas que rotan nodos al insertar, la forma final depende del orden de inserción. Dos réplicas con exactamente el mismo conjunto de claves, recibidas en orden distinto, producirán árboles con formas distintas y por tanto raíces distintas. El protocolo concluirá que divergen, descenderá por todas las ramas, encontrará que todas las hojas son iguales y habrá gastado un recorrido completo para acabar sin nada que transferir. Peor aún: lo hará en cada sincronización, para siempre.

La propiedad que hay que exigir tiene nombre en la literatura y es la independencia de la historia: la representación tiene que ser función únicamente del conjunto representado. Se consigue de tres maneras, y las tres se usan en producción. La primera es el árbol de prefijos sobre el resumen de la clave, como en el fragmento anterior, donde la posición está fijada de antemano y no hay nada que reequilibrar. La segunda es hacer que el nivel al que asciende cada clave lo decidan también los bits de su resumen, que es la idea de los árboles de búsqueda de Merkle publicados para este mismo problema. La tercera es cortar por contenido, la técnica de troceado que ya apareció al partir ficheros grandes, aplicada aquí a la frontera entre nodos.

flowchart TB
R[raiz distinta] --> N0[rama 0 resumen igual]
R --> N1[rama 1 resumen distinto]
R --> N2[rama 2 resumen igual]
N1 --> H4[hoja con cubo de claves]
N1 --> H5[hoja identica descartada]
H4 --> D[diferencia localizada]
style N0 fill:#a6e3a1,color:#11111b
style N2 fill:#a6e3a1,color:#11111b
style H5 fill:#a6e3a1,color:#11111b
style D fill:#f38ba8,color:#11111b

El coste real: rondas, mantenimiento y granularidad

La cuenta que se cita siempre es que localizar una diferencia cuesta el logaritmo del tamaño del conjunto, y es cierta con dos matices que cambian el resultado en la práctica. El primero es que las rutas de varias diferencias comparten los niveles altos, así que el coste de localizar mil diferencias no es mil veces el de localizar una, sino bastante menos. El segundo es que la aridad decide el reparto entre número de rondas y tamaño de cada mensaje, y ese reparto hay que elegirlo mirando el enlace real y no la elegancia asintótica.

Un millon de claves, cubos de 32 claves por hoja, resumenes de 32 bytes

  aridad 4 ....... profundidad 8   mensaje por nodo 128 B    8 rondas
  aridad 16 ...... profundidad 4   mensaje por nodo 512 B    4 rondas
  aridad 256 ..... profundidad 2   mensaje por nodo 8 KB     2 rondas

  con 150 ms de ida y vuelta, cada ronda ahorrada vale mas que 8 KB de trafico

Ese cuadro explica una decisión que sorprende cuando se ve por primera vez en un almacén distribuido real: en lugar de descender nodo a nodo, algunos sistemas se envían el árbol entero de profundidad fija en un solo mensaje de aproximadamente un megabyte y hacen toda la comparación en local. Están comprando cero rondas adicionales con ancho de banda, que es la elección correcta en un centro de datos y la equivocada en un móvil con datos limitados. El mismo algoritmo admite las dos configuraciones y la diferencia entre acertar y fallar está en haber medido la latencia antes.

La granularidad de las hojas es el otro parámetro que decide el suelo del coste. Si cada hoja cubre un cubo de treinta y dos claves, localizar una diferencia significa descubrir qué cubo difiere, y a partir de ahí hay que intercambiar los identificadores de las treinta y dos claves del cubo para saber cuál de ellas es. Hojas más pequeñas afinan la localización y engordan el árbol; hojas más grandes lo adelgazan y obligan a transferir más basura al final. Es el mismo compromiso que el tamaño de bloque en cualquier sistema de almacenamiento.

Por qué Git y los almacenes distribuidos lo hacen así

En Git la técnica está por todas partes aunque no se anuncie con este nombre. Comparar dos revisiones de un repositorio con cientos de miles de ficheros no lee cientos de miles de ficheros: compara los identificadores de los árboles de directorio y descarta enteros aquellos cuyo resumen coincide, de modo que el coste de una comparación es proporcional a lo que cambió y no al tamaño del proyecto. La estructura cumple la condición de independencia de la historia por construcción, porque un árbol de Git es la lista ordenada canónicamente de sus entradas y no depende en absoluto de en qué orden se crearon los ficheros.

En los almacenes de clave y valor distribuidos, la misma idea aparece con el nombre de reparación por antientropía. Cada nodo mantiene un árbol de resúmenes por cada rango del espacio de claves que le corresponde; dos réplicas del mismo rango comparan raíces periódicamente y solo se intercambian las claves de los cubos discrepantes. Es lo que permite que réplicas que llevan horas divergiendo por una partición se pongan al día sin leerse mutuamente los datos y sin depender de ningún registro de operaciones que alguien haya tenido que conservar.

La cuarta tarjeta es la propiedad que ninguno de los otros dos mecanismos del nivel tiene y que decide la elección en topologías abiertas. Con vectores de versiones hay que fiarse de que el otro extremo envíe de verdad todas las operaciones del intervalo pedido, porque nada permite comprobarlo. Con un árbol de resúmenes, cada dato que llega viene acompañado de la expectativa de su resumen, y si no cuadra se descarta al instante. Sincronizar con desconocidos solo es sensato con este mecanismo o con uno equivalente.