Зачем распределённому хранилищу антиэнтропийная синхронизация с деревом хэшей, если реплики уже принимают записи?
Антиэнтропийная синхронизация нужна, чтобы обнаруживать и исправлять расхождения между репликами, возникшие из-за временной недоступности узлов, потери сообщений или локальных сбоев. Дерево хэшей позволяет сравнить реплики по крупным диапазонам данных и спуститься только в те ветви, где хэши различаются, поэтому не требуется передавать и сравнивать весь набор данных.
В распределённых хранилищах реплики часто обновляются асинхронно. Если узел был недоступен или сообщение об изменении потерялось, обычной доставки новых записей недостаточно: система должна позднее самостоятельно найти уже возникшее расхождение.
Для этого применяют периодическую антиэнтропийную синхронизацию. Деревья хэшей делают такую проверку экономичнее: сравнение начинается с одного корневого значения, а детали запрашиваются только для несовпадающих частей.
Пусть две реплики содержат один логический диапазон ключей, но одна из них не получила несколько изменений. Простое полное сравнение потребует прочитать и сопоставить все записи, создавая нагрузку на диск, сеть и процессор даже при единственном небольшом расхождении.
Если расхождение не обнаружить, чтения с разных реплик могут возвращать разные значения. Особенно опасны потерянные удаления: реплика, не получившая маркер удаления, может позднее снова выдать устаревшую запись или восстановить её при очередной синхронизации.
Данные логически разбивают на диапазоны или сегменты. Для каждого сегмента вычисляют хэш, затем из пар дочерних хэшей строят родительские хэши; верхний хэш становится кратким отпечатком всего набора.
Синхронизация сравнивает корневые хэши реплик. Если они совпадают, при предположении корректного хэширования соответствующие деревья считаются одинаковыми. Если корни различаются, система сравнивает хэши дочерних узлов и рекурсивно спускается только по несовпадающим ветвям.
На нижнем уровне определяются конкретные диапазоны, требующие восстановления. Реплика-источник передаёт для них актуальные записи, версии и, при необходимости, тумбстоуны — маркеры удалений, чтобы устаревшая запись не воскресла на отстающем узле.
Метод не обеспечивает сам по себе ни линейризуемость, ни отсутствие устаревших чтений во время ремонта. Он является механизмом обнаружения и исправления расхождений, обычно поддерживающим сходимость реплик с некоторой задержкой.
Важны одинаковая разбивка ключевого пространства, детерминированная сериализация данных и согласованные правила учёта удалений. Хэш теоретически может столкнуться для разных данных, поэтому он не является математическим доказательством равенства; на критическом этапе система может дополнительно сравнить записи.
Размер и структура дерева создают компромисс. Более мелкие сегменты точнее ограничивают передачу при локальном расхождении, но увеличивают объём метаданных и стоимость вычисления хэшей. Более крупные сегменты проще обслуживать, однако при несовпадении приходится передавать больше данных.
В распределённом каталоге товаров одна реплика была недоступна во время сетевого сбоя. После восстановления обычный поток изменений не устранил часть расхождений: несколько сообщений потерялись, а удаления не дошли до узла.
Рассматривались два варианта. Полная сверка всех ключей была простой, но создавала бы длительную нагрузку на хранилище и сеть. Сверка только журнала изменений была дешевле, однако зависела от полноты журнала и не исправляла расхождения, возникшие до его сохранения или после истечения периода хранения.
Выбрали периодическую антиэнтропийную проверку по деревьям хэшей, а для найденных диапазонов — передачу записей вместе с версиями и тумбстоунами. Журнал остался быстрым механизмом обычной доставки, а дерево хэшей — независимым механизмом обнаружения пропусков. В результате редкие расхождения исправлялись без полной передачи каталога, но система сохранила необходимость учитывать задержку ремонта и нагрузку от фоновых проверок.
Ответ: Практически это считается достаточным при корректной реализации хэширования и одинаковой сериализации, но абсолютной гарантии математически нет из-за возможности коллизии. Поэтому для критичных данных могут использоваться криптографически стойкие хэши, дополнительные проверки выбранных записей и контроль целостности самого дерева. Совпадение хэшей также не доказывает, что реплики одинаково обслуживают будущие записи или имеют одинаковую историю версий.
Ответ: Снимок может оказаться внутренне несогласованным: хэши разных уровней способны описывать данные, собранные в разные моменты. Это может привести к лишнему ремонту или к пропуску расхождения в конкретном цикле. Обычно используют согласованный снимок, версии сегментов, блокировку соответствующего диапазона или повторную проверку после сравнения; выбор зависит от допустимой нагрузки и требований к задержке.
Ответ: Если удаление представлено только физическим исчезновением записи, отстающая реплика может не узнать, что запись была удалена. При следующем обмене она способна распространить старую копию обратно. Поэтому удаление обычно сохраняют как тумбстоун на период, достаточный для доставки и ремонта всех реплик; слишком раннее удаление тумбстоуна снова создаёт риск воскрешения данных.