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

Question

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

• Динамо
• Riak
• Cassandra

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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