Explicar los Árboles Merkle para su uso en Consistencia Eventual
Los árboles Merkle se utilizan como un mecanismo antientropía en varios almacenes de clave/valor distribuidos y replicados:
No hay duda de que un mecanismo antientropía es Algo Bueno: las fallas transitorias simplemente ocurren, en la producción. No estoy seguro de entender por qué Merkle Los árboles son el enfoque popular.
Enviar un árbol Merkle completo a un compañero implica enviar el espacio clave local para ese par, junto con hashes de cada valor clave, almacenados en los niveles más bajos del árbol.
Diffing un árbol Merkle enviado desde un par requiere tener un árbol Merkle de su propio.
Dado que ambos pares ya deben tener un espacio de hash de clave / valor ordenado a mano, ¿por qué no hacer una combinación lineal para detectar discrepancias?
Simplemente no estoy convencido de que la estructura de árbol proporciona ningún tipo de ahorro cuando se tienen en cuenta los costos de mantenimiento, y el hecho que pases lineales sobre las hojas del árbol ya se están haciendo solo para serializar la representación sobre el alambre.
Para fundamentar esto, una alternativa de straw-man podría ser hacer que los nodos intercambien matrices de digests de hash, que se actualizan de forma incremental y se abotonan por la posición del anillo del módulo.
¿Qué me estoy perdiendo?
1 answers
Los árboles de Merkle limitan la cantidad de datos transferidos al sincronizar. Los supuestos generales son:
- La E/S de red es más cara que la E/S + local que calcula los hashes.
- Transferir todo el espacio de claves ordenadas es más costoso que limitar progresivamente la comparación en varios pasos.
- Los espacios clave tienen menos discrepancias que similitudes.
Un intercambio de árboles Merkle se vería así:
- Comience con la raíz de la árbol (una lista de un valor hash).
- El origen envía la lista de hashes al nivel actual.
- El destino difunde la lista de hashes contra su propio y luego solicita subárboles que sean diferentes. Si no hay diferencias, la solicitud puede terminar.
- Repita los pasos 2 y 3 hasta que se alcancen los nodos de la hoja.
- 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 las escrituras y manteniendo la forma serializada en el disco.
No puedo hablar de cómo Dynamo o Cassandra usan árboles Merkle, pero Riak dejó de usarlos para la sincronización intra-cluster (transferencia insinuada y reparación de lectura son suficientes en la mayoría de los casos). Tenemos los planes para añadirlos de nuevo más tarde después de que algunos bits arquitectónicos internos han cambiado.
Para más información sobre Riak, le animamos a unirse a la lista de correo: http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-03-30 17:18:01