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

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

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

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

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

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

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

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

Ответ 1

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

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

Обмен Merkle Tree будет выглядеть следующим образом:

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

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

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

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