Expliquer les arbres Merkle à utiliser dans la cohérence éventuelle

Merkle Trees est utilisé comme mécanisme anti-entropie dans plusieurs magasins de clés / valeurs répliqués dissortingbués:

  • Dynamo
  • Riak
  • Cassandra

Nul doute qu’un mécanisme anti-entropie est une bonne chose – des défaillances transitoires se produisent simplement dans la production. Je ne suis pas sûr de comprendre pourquoi les arbres Merkle sont l’approche populaire.

Étant donné que les deux homologues doivent déjà disposer d’un espace sortingé clé / valeur-hachage, pourquoi ne pas effectuer une fusion linéaire pour détecter les écarts?

Je ne suis pas convaincu que la structure arborescente permette de réaliser des économies lorsque les coûts d’entretien sont pris en compte, et le fait que les lignes linéaires passent par-dessus les feuilles est déjà utilisé pour sérialiser la représentation .

Pour résumer cela, une solution de rechange pourrait consister à avoir des nœuds échangeant des tableaux de condensés de hachage, qui sont mis à jour de façon incrémentale et définis par modulo ring-position.

Qu’est-ce que je rate?

Les arborescences 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 et le calcul des hachages.
  2. Transférer l’intégralité de l’espace-clé sortingé est plus coûteux que de limiter progressivement la comparaison en plusieurs étapes.
  3. Les espaces clés présentent moins de différences que de similarités.

Un échange Merkle Tree ressemblerait à ceci:

  1. Commencez par la racine de l’arborescence (une liste d’une valeur de hachage).
  2. L’origine envoie la liste des hachages au niveau actuel.
  3. La destination diffère la liste des hachages contre les siens, puis demande des sous-arborescences différentes. S’il n’y a pas de différences, la demande peut se terminer.
  4. Répétez les étapes 2 et 3 jusqu’à ce que les nœuds de la feuille soient atteints.
  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 clés sera log (N). Oui, à l’extrême, là où il n’y a pas de clé en commun, l’opération équivaudra à envoyer la liste complète des hachages sortingés, O (N). On pourrait amortir les dépenses liées à la construction d’arbres Merkle en les construisant dynamicment au fur et à mesure de l’arrivée des écritures et en conservant le formulaire sérialisé sur le disque.

Je ne peux pas parler de la façon dont Dynamo ou Cassandra utilisent les arbres Merkle, mais Riak a cessé de les utiliser pour la synchronisation intra-cluster (le transfert et la lecture-réparation suggérés sont suffisants dans la plupart des cas). Nous prévoyons de les rappend plus tard, après la modification de certains éléments architecturaux internes.

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