Объясните деревья Меркле для использования в конечной последовательности

Merkle Trees используются в качестве антиэнтропийного механизма в нескольких распределенных, реплицированных хранилищах ключей / значений:

без сомнения, антиэнтропийный механизм-это хорошая вещь-переходные сбои просто случаются в производстве. Я просто не уверен, что понимаю, почему Меркл деревьев популярные подход.

  • отправка полного дерева Merkle на одноранговый узел включает в себя отправку локального пространства ключей на этот одноранговый узел вместе с хэши каждого значения ключа, хранящиеся на самых низких уровнях дерева.

  • чтобы отличить Дерево Меркла, отправленное от сверстника, требуется иметь собственное дерево Меркла.

поскольку у обоих одноранговых узлов уже должно быть отсортированное пространство ключа / значения-хэша, почему бы не выполнить линейное слияние для обнаружения расхождения?

Я просто не уверен, что древовидная структура обеспечивает какую-либо экономию, когда вы учитываете расходы на содержание, и факт это линейные проходы над листьями дерева уже выполняются только для сериализации представления по проводу.

чтобы заземлить это, альтернативой соломенного человека может быть обмен узлами массивов хэш-дайджестов, которые постепенно обновляются и сгибаются по модулю положения кольца.

Что же Я скучаю?

1 72
algorithm nosql cassandra amazon-dynamodb riak

1 ответ:

деревья Меркла ограничивают количество передаваемых данных при синхронизации. Общие предположения:

  1. сетевой ввод-вывод стоит дороже, чем локальный ввод-вывод + вычисление хэшей.
  2. перенос всего отсортированного пространства ключей является более дорогостоящим, чем постепенное ограничение сравнения в течение нескольких шагов.
  3. ключевые пространства имеют меньше расхождений, чем сходства.

обмен Merkle Tree будет выглядеть так это:

  1. начните с корня дерева (список из одного хэш-значения).
  2. источник отправляет список хэшей на текущем уровне.
  3. назначение различает список хэшей против своего собственного, а затем запрашивает поддеревья, которые отличаются. Если нет различия, запрос может прекратиться.
  4. повторяйте шаги 2 и 3, пока не будут достигнуты конечные узлы.
  5. начало отсылает значения ключей в результирующем набор.

в типичном случае сложность синхронизации ключевых пространств будет log (N). Да, в крайнем случае, где нет общих ключей, операция будет эквивалентна отправке всего отсортированного списка хэшей, O(N). Можно было бы амортизировать расходы на создание деревьев Merkle, создавая их динамически по мере поступления записей и сохраняя сериализованную форму на диске.

Я не могу говорить о том, как Динамо или Кассандра используют деревья Меркла, но РИАК перестал использовать их для внутрикластерной синхронизации (в большинстве случаев достаточно намеков на передачу и восстановление чтения). Мы планируем добавить их позже, после того, как некоторые внутренние архитектурные биты изменились.

для получения дополнительной информации о Riak, мы рекомендуем вам присоединиться к списку рассылки:http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com

79