Ответ 1
Деревья Merkle ограничивают количество данных, передаваемых при синхронизации. Общие предположения:
- Сетевой ввод-вывод более дорогой, чем локальный ввод-вывод +, вычисляет хеширование.
- Перенос всего отсортированного пространства ключа более дорого, чем постепенное ограничение сравнения на несколько этапов.
- В ключевых пробелах меньше расхождений, чем сходств.
Обмен Merkle Tree будет выглядеть следующим образом:
- Начните с корня дерева (список одного хеш-значения).
- Происхождение отправляет список хэшей на текущем уровне.
- Назначение отличает список хэшей от своих собственных, а затем запрашивает поддеревья, которые различны. Если нет различия, запрос может завершиться.
- Повторяйте шаги 2 и 3 до тех пор, пока не будут достигнуты узлы листа.
- Происхождение отправляет значения ключей в результирующем наборе.
В типичном случае сложностью синхронизации ключевых пространств будет log (N). Да, в крайнем случае, когда нет общих ключей, операция будет эквивалентна отправке всего отсортированного списка хэшей O (N). Можно было бы амортизировать затраты на строительство деревьев Меркле, создавая их динамически, когда записи поступают и сохраняют сериализованную форму на диске.
Я не могу говорить о том, как Динамо или Кассандра используют деревья Меркле, но Riak прекратил использовать их для внутрикластерной синхронизации (в большинстве случаев достаточно намеченной передачи обслуживания и чтения-ремонта). Мы планируем добавить их позже после того, как некоторые внутренние архитектурные биты изменились.
Для получения дополнительной информации о Riak, мы рекомендуем вам присоединиться к списку рассылки: http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com