algorithm - Explique Merkle Trees para usar en eventual consistencia

nosql cassandra

Question

Merkle Trees se utilizan como mecanismo antientropía en varios almacenes de clave / valor distribuidos y replicados:

• Dynamo
• Riak
• Cassandra

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

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

• Diffing a Merkle tree enviado desde un par requiere tener un árbol Merkle propio.

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

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

Para fundamentar esto, una alternativa de "hombre de paja" podría ser que los nodos intercambiaran matrices de compendios de hash, que se actualizan de forma incremental y se incrustan por posición de anillo de módulo.

¿Qué me estoy perdiendo?

Answer 1

Merkle trees limita la cantidad de datos transferidos al sincronizar. Las suposiciones generales son:

1. La E / S de red es más costosa que la E / S local y calcula los valores hash.
2. Transferir todo el espacio de claves ordenadas es más costoso 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 de hash).
2. El origen envía la lista de hashes en el nivel actual.
3. El destino diffs la lista de hashes contra los suyos y luego solicita subárboles que son diferentes. Si no hay diferencias, la solicitud puede finalizar.
4. Repita los pasos 2 y 3 hasta llegar a los nodos de la 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 clave 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 entran escrituras y manteniendo el formulario serializado en el disco.

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

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