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

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

• Динамо
• Риак
• Кассандра

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

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

• Чтобы различать дерево Меркла, отправленное от однорангового узла, необходимо иметь собственное дерево Меркла.

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

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

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

Что мне не хватает?

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

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

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

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

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

Я не могу говорить о том, как Dynamo или Cassandra используют деревья Меркла, но Riak прекратил использовать их для внутрикластерной синхронизации (в большинстве случаев достаточно намеков на передачу и восстановление при чтении). Мы планируем добавить их позже, после того как будут изменены некоторые внутренние архитектурные элементы.

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