Expliquer les arbres de Merkle pour une utilisation dans la cohérence éventuelle

Question

Les arbres de Merkle sont utilisés comme mécanisme anti-entropie dans plusieurs magasins de clés/valeurs distribués et répliqués :

• Dynamo
• Riak
• Cassandra

Sans aucun doute, un mécanisme anti-entropie est une Bonne Chose - les défaillances transitoires arrivent, en production. Je ne suis juste pas sûr de comprendre pourquoi les arbres de Merkle sont l'approche populaire.

• Envoyer un arbre de Merkle complet à un pair implique d'envoyer l'espace clé local à ce pair, avec les hachages de chaque valeur de clé, stockés dans les niveaux inférieurs de l'arbre.

• Comparer un arbre de Merkle envoyé par un pair nécessite d'avoir son propre arbre de Merkle.

Puisque les deux pairs doivent déjà avoir un espace clé/valeur haché trié en main, pourquoi ne pas faire une fusion linéaire pour détecter les divergences?

Je ne suis simplement pas convaincu que la structure en arbre fournisse des économies quelconques lorsqu'on prend en compte les coûts de maintenance, et le fait que des passages linéaires sur les feuilles de l'arbre sont déjà effectués juste pour sérialiser la représentation sur le fil.

Pour approfondir, une alternative de type homme de paille pourrait être d'échanger des tableaux de condensats de hachage, qui sont mis à jour de manière progressive et regroupés par position d'anneau modulo.

Qu'est-ce que je rate ?

Answer 1

Les arbres de Merkle limitent la quantité de données transférées lors de la synchronisation. Les hypothèses générales sont les suivantes :

1. Les E/S réseau sont plus coûteuses que les E/S locales + le calcul des hachages.
2. Transférer l'ensemble de l'espace de clés triées est plus coûteux que de limiter progressivement la comparaison sur plusieurs étapes.
3. Les espaces de clés ont moins de divergences que de similitudes.

Un échange d'Arbre de Merkle aurait l'aspect suivant :

1. Commencer par la racine de l'arbre (une liste d'une valeur de hachage).
2. L'origine envoie la liste des hachages au niveau actuel.
3. La destination compare les listes de hachages avec les siennes et demande ensuite les sous-arbres qui sont différents. S'il n'y a pas de différences, la demande peut se terminer.
4. Répéter les étapes 2 et 3 jusqu'à ce que les feuilles soient atteintes.
5. L'origine envoie les valeurs des clés dans l'ensemble résultant.

Dans le cas typique, la complexité de la synchronisation des espaces de clés sera log(N). Oui, dans l'extrême, là où il n'y a pas de clés en commun, l'opération sera équivalente à envoyer l'ensemble complet et trié des hachages, O(N). On pourrait amortir le coût de construction des arbres de Merkle en les construisant dynamiquement au fur et à mesure que les écritures arrivent et en conservant la forme sérialisée sur le disque.

Je ne peux pas dire comment Dynamo ou Cassandra utilisent les arbres de Merkle, mais Riak a cessé de les utiliser pour la synchronisation intra-cluster (le transfert suggéré et la réparation de lecture sont suffisants dans la plupart des cas). Nous avons l'intention de les réintégrer plus tard après que certains éléments architecturaux internes auront changé.

Pour plus d'informations sur Riak, nous vous encourageons à rejoindre la liste de diffusion : http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com