Explicar los árboles de Merkle para su uso en coherencia eventual

Los árboles Merkle se utilizan como un mecanismo anti-entropía en varios almacenes de clave / valor replicados y distribuidos:

• Dinamo
• Riak
• Casandra

Sin duda, un mecanismo anti-entropía es algo bueno: las fallas transitorias simplemente ocurren en la producción. Simplemente no estoy seguro de entender por qué Merkle Trees es el enfoque popular.

• Enviar un árbol Merkle completo a un par implica enviar el espacio de claves local a ese par, junto con los valores hash de cada valor de clave, almacenados en los niveles más bajos del árbol.

• Para diferenciar un árbol Merkle enviado por un compañero, es necesario tener un árbol Merkle propio.

Dado que ambos pares ya deben tener un espacio ordenado clave / valor-hash a mano, ¿por qué no realizar una fusión lineal para detectar discrepancias?

Simplemente no estoy convencido de que la estructura del árbol proporcione algún tipo de ahorro cuando se tienen en cuenta los costos de mantenimiento, y el hecho de que ya se están realizando pases lineales sobre las hojas del árbol solo para serializar la representación sobre el cable .

Para fundamentar esto, una alternativa de hombre de paja podría ser hacer que los nodos intercambien matrices de resúmenes de hash, que se actualizan y clasifican de forma incremental según la posición del anillo de módulo.

¿Qué me estoy perdiendo?

Los árboles Merkle limitan la cantidad de datos transferidos al sincronizar. Los supuestos generales son:

1. La E / S de red es más cara que la E / S local + calcular los valores hash.
2. Transferir todo el espacio de claves ordenado es más caro que limitar progresivamente la comparación en varios pasos.
3. Los espacios clave tienen menos discrepancias que similitudes.

Un intercambio de Merkle Tree se vería así:

1. Comience con la raíz del árbol (una lista de un valor hash).
2. El origen envía la lista de hashes en el nivel actual.
3. El destino diferencia la lista de hashes con la suya propia y luego solicita subárboles que son diferentes. Si no hay diferencias, la solicitud puede terminar.
4. Repita los pasos 2 y 3 hasta alcanzar los nodos de hoja.
5. El origen envía los valores de las claves en el conjunto resultante.

En el caso típico, la complejidad de sincronizar los espacios de claves será log (N). Sí, en el extremo, donde no hay claves en común, la operación será equivalente a enviar toda la lista ordenada de hashes, O (N). Uno podría amortizar el gasto de construir árboles Merkle construyéndolos dinámicamente a medida que ingresan las escrituras y manteniendo la forma serializada en el disco.

No puedo hablar de cómo Dynamo o Cassandra usan los árboles Merkle, pero Riak dejó de usarlos para la sincronización intra-clúster (la transferencia insinuada y la reparación de lectura son suficientes en la mayoría de los casos). Tenemos planes de volver a agregarlos más tarde, después de que hayan cambiado algunos bits arquitectónicos internos.

Para obtener más información sobre Riak, lo alentamos a unirse a la lista de correo: http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com