Дельта-синхронизация

Дельта-синхронизация — это метод передачи данных, при котором между источником и приёмником передаются только изменения (дельты) относительно последней известной версии данных, а не полный набор данных. Этот подход позволяет значительно сократить объём передаваемой информации, время передачи и нагрузку на каналы связи, особенно в системах с большими объёмами данных или ограниченной пропускной способностью сети.

Принцип работы

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

Процесс включает несколько этапов:

1. Идентификация версии: источник и приёмник согласовывают, какая версия данных является базовой (например, по контрольной сумме, временной метке или номеру версии).
2. Вычисление дельты: источник сравнивает свою текущую версию с базовой и выделяет изменённые, добавленные или удалённые фрагменты.
3. Передача дельты: по сети отправляется компактное описание изменений (например, список изменённых блоков или патч).
4. Применение дельты: приёмник вносит изменения в свою копию данных, получая актуальную версию.

Алгоритмы вычисления дельты

Существует несколько алгоритмов, используемых для вычисления дельты. Выбор конкретного алгоритма зависит от типа данных, требований к скорости и точности.

Алгоритм на основе хеширования (rsync)

Один из наиболее известных — алгоритм, лежащий в основе утилиты rsync. Он работает следующим образом:

• Приёмник разбивает свою версию файла на блоки фиксированного размера (например, 512 байт) и вычисляет для каждого блока два хеша: слабый (быстрый, циклический избыточный код, CRC) и сильный (криптостойкий, например MD5).
• Список хешей передаётся источнику.
• Источник сканирует свой файл, вычисляя для каждого возможного положения блока (с шагом в один байт) слабый хеш. При совпадении слабого хеша вычисляется сильный хеш для подтверждения.
• Если блок найден, он не передаётся; если нет — блок помечается как изменённый и подлежит передаче.
• В результате формируется дельта: инструкции по копированию уже имеющихся блоков и данные для новых блоков.

Алгоритмы на основе дифференциального сжатия (xdelta, bsdiff)

Эти алгоритмы (например, xdelta3, bsdiff) работают на уровне байтовых последовательностей, не разбивая данные на блоки фиксированного размера. Они строят дельту как серию команд «копировать» (copy) и «вставить» (insert):

• Копировать: указывает диапазон байтов, который уже есть в базовой версии.
• Вставить: содержит новые байты, которых нет в базовой версии.

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

Алгоритмы на основе деревьев (для синхронизации каталогов)

Для синхронизации целых файловых систем (например, в облачных хранилищах) используются алгоритмы, которые строят дерево изменений. Они сравнивают метаданные файлов (размер, дата изменения, хеш) и передают дельты только для изменённых файлов, а не для всего каталога.

Применение

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

Резервное копирование и восстановление

Системы резервного копирования (например, BorgBackup, Restic) используют дельта-синхронизацию для создания инкрементальных копий. При каждом новом запуске сохраняется только дельта изменений, что позволяет экономить дисковое пространство и ускорять процесс. Восстановление данных происходит путём последовательного применения дельт к базовой копии.

Обновление программного обеспечения

Пакетные менеджеры (apt, yum, pacman) и системы обновления игр (Steam, Battle.net) применяют дельта-синхронизацию для доставки обновлений. Вместо загрузки полной версии программы пользователь скачивает только изменившиеся файлы или их части. Это особенно актуально для крупных игр (десятки гигабайт), где обновление может составлять всего несколько мегабайт.

Облачные хранилища и файловые синхронизаторы

Сервисы вроде Яндекс.Диска, Google Drive, Dropbox и OneDrive используют дельта-синхронизацию для синхронизации файлов между устройствами. При изменении части файла (например, редактировании документа) загружается только изменённый фрагмент, а не весь файл. Это снижает нагрузку на сеть и ускоряет синхронизацию.

Репликация баз данных

В системах управления базами данных (СУБД) дельта-синхронизация используется для репликации изменений между мастер-сервером и репликами. Вместо передачи всей базы данных передаются только логи операций (например, бинарные логи MySQL) или изменённые страницы данных. Это позволяет поддерживать актуальность реплик с минимальной задержкой.

Системы контроля версий

Распределённые системы контроля версий, такие как Git, используют дельта-сжатие для хранения истории изменений. Каждый коммит хранит не полную копию файлов, а дельту относительно предыдущего коммита. Это позволяет компактно хранить историю разработки, даже для больших проектов.

Преимущества и недостатки

Преимущества

• Экономия пропускной способности: передаётся только изменённая часть данных, что особенно важно при медленных или дорогих каналах связи (например, мобильный интернет).
• Экономия времени: время передачи сокращается пропорционально объёму изменений.
• Экономия дискового пространства: при хранении версий (например, в резервных копиях) используется меньше места.
• Снижение нагрузки на сервер: серверу не нужно обрабатывать и отправлять полные копии данных.

Недостатки

• Вычислительные затраты: вычисление дельты требует процессорного времени, особенно для больших файлов или сложных алгоритмов.
• Сложность реализации: требуется поддержка версионирования, хеширования и корректного применения дельт.
• Зависимость от базовой версии: если базовая версия повреждена или утеряна, применить дельту невозможно, и требуется полная передача данных.
• Неэффективность для сильно изменяющихся данных: если файл изменяется целиком (например, зашифрованный файл), дельта может быть размером с полный файл.

Отличие от других методов

Дельта-синхронизацию часто путают с другими методами передачи данных, но между ними есть принципиальные различия.

• Инкрементальная синхронизация: передаёт только новые или изменённые файлы, но не изменения внутри файлов. Дельта-синхронизация работает на уровне файлов, передавая только изменённые фрагменты.
• Дифференциальная синхронизация: передаёт разницу между двумя версиями, но не требует наличия базовой версии у получателя. Дельта-синхронизация требует, чтобы у получателя была предыдущая версия.
• Сжатие данных: сжимает данные для уменьшения объёма, но не устраняет повторную передачу уже имеющихся данных. Дельта-синхронизация устраняет именно повторную передачу.

Примеры реализации

• rsync: утилита для синхронизации файлов в Unix-подобных системах, реализующая алгоритм дельта-синхронизации на основе хеширования.
• xdelta3: библиотека для создания и применения бинарных дельт, используемая в некоторых системах обновления.
• ZFS: файловая система, использующая дельта-синхронизацию для репликации снапшотов.
• Btrfs: файловая система с поддержкой дельта-синхронизации для отправки и получения изменений между подтомами.

Источники

• Tridgell, A., & Mackerras, P. (1996). The rsync algorithm. Technical Report TR-CS-96-05, Australian National University.
• Hunt, J. J., & McIlroy, M. D. (1976). An algorithm for differential file comparison. Computing Science Technical Report, Bell Laboratories.
• Percival, C. (2003). Naive differences of executable code. Proceedings of the 2003 ACM workshop on Digital rights management.
• Документация к утилитам rsync, xdelta3, BorgBackup.