Expliquer les Arbres de Merkle pour une utilisation dans la Cohérence des résultats

Les Arbres De Merkle sont utilisés comme anti-entropie mécanisme dans plusieurs distribué, reproduit clé/valeur de magasins:

Sans aucun doute, un anti-entropie mécanisme est Une Bonne Chose - et transitoire des défaillances se produisent, dans la production.
Je ne suis pas sûr de comprendre pourquoi Merkle Arbres sont populaires approche.

  • L'envoi d'un complet d'arbre de Merkle à un pair implique l'envoi de la clé locale-espace pour que les pairs, ainsi que
    des tables de hachage de chaque valeur de la clé, stockées dans les niveaux les plus bas de l'arbre.

  • De comparaison d'un arbre de Merkle envoyé à partir d'un de ses pairs, nécessite d'avoir un arbre de Merkle de votre propre.

Depuis deux homologues, il faut déjà avoir un triées clé /valeur de hachage de l'espace à portée de main, pourquoi ne pas faire un linéaire de fusion de détecter les différences?

Je ne suis pas convaincu que la structure de l'arbre fournit tout type de l'épargne lorsque vous prenez en compte les frais d'entretien, et le fait
que linéaire passe sur les feuilles des arbres sont déjà en train de le faire juste pour sérialiser la représentation sur le fil.

À la masse de ce fait, une paille-homme autre solution pourrait être d'avoir des nœuds d'échange des tableaux de hachage digère,
qui sont mis à jour incrémentielle et placées dans un compartiment par modulo anneau position.

Ce qui me manque?

InformationsquelleAutor Johnny Graettinger | 2011-03-30
  1. 81

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

    1. Réseau I/O est plus onéreuses que les I/O + calcul du hash.
    2. Le transfert de l'ensemble de la triés espace clé est plus cher que progressivement en limitant la comparaison sur plusieurs étapes.
    3. La clé espaces ont de moins en moins de différences que de similitudes.

    Un Arbre de Merkle échange devrait ressembler à ceci:

    1. Commencer avec 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 des diff la liste des hachages à l'encontre de son propre, puis
      les demandes de sous-arbres qui sont différents. Si il n'y a pas
      les différences, la demande peut résilier.
    4. Répétez les étapes 2 et 3 jusqu'à ce que les nœuds feuilles sont atteintes.
    5. L'origine envoie les valeurs des clés dans le jeu de résultats.

    Dans le cas typique, la complexité de la synchronisation de la clé espaces seront log(N). Oui, à l'extrême, où il n'y a pas les clés en commun, l'opération sera équivalent à l'envoi de l'ensemble de la liste triée des hachages, O(N). On pourrait amortir le coût de construction de Merkle arbres en construisant dynamiquement comme l'écrit venir et de garder la forme sérialisée sur le disque.

    Je ne peux pas parler à la façon de la Dynamo ou de Cassandra utiliser des arbres de Merkle, mais Riak cessé de les utiliser pour les échanges intra-cluster de synchronisation (allusion transfert et la lecture de réparation sont suffisants dans la plupart des cas). Nous avons des plans pour ajouter plus tard après certains l'architecture interne de bits ont 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

    • Ahh, le va-et-vient d'échange était ce qui me manquait. Merci.
    • Ils ont été ré-introduit dans Riak 1.3 de l'AAE mise en œuvre.
    InformationsquelleAutor seancribbs