SYS Системы и большие данные Алгоритм
Алгоритм rsync
Также: rsync · rsync algorithm · синхронизация файлов · file synchronization · скользящая контрольная сумма · rolling checksum · дельта-передача · delta transfer · rdiff · librsync · zsync
У сервера вчерашняя версия файла, у вас сегодняшняя, и никто из двоих не знает, что именно поменялось. rsync передаёт только новые куски: получатель присылает короткие суммы своих блоков, а отправитель катит по своему файлу окно и находит эти блоки на любом месте — сумма окна при сдвиге на байт обновляется за O(1). На пяти настоящих правках одной главы курса — от 4 до 38 процентов файла.
Глава базового курса «Парламент острова Паксос» за два дня правилась пять раз: правка стиля, неразрывные пробелы, проверка фактов, одно слово, более короткое описание. Каждый раз новая версия — около 97 КБ — должна была попасть на сервер, где лежит предыдущая. Сколько байт для этого нужно передать? Ниже — все пять правок, как их передал бы rsync, и для сравнения ещё одна: картинка, которую просто пересохранили.
Выберите «короче описание». В самом начале главы описание стало на 102 байта короче, и всё, что после него, сдвинулось. Если сравнивать блоки только на их прежних местах («блок только на своём месте»), совпадёт один блок из 140, и передавать придётся больше, чем весь файл: к новым байтам добавятся суммы блоков. rsync находит 139 блоков из 140 — на новых местах, на 102 байта левее — и отправляет 4 КБ, из которых новых байтов 598. А картинка, почти не изменившаяся на глаз, уходит целиком: от старой версии в новой не нашлось ничего, кроме одного блока в заголовке файла.
Идея
Получатель режет свою старую версию на блоки по B байт и присылает для каждого две контрольные суммы: слабую, 4 байта, и сильную, 16 байт. Отправитель катит по новой версии окно длиной B, сдвигая его на байт, и на каждом месте спрашивает: нет ли блока с такой слабой суммой? Слабая сумма окна при сдвиге пересчитывается за O(1), поэтому проверить все смещения стоит O(n), а не O(n·B). Совпала слабая — сверяем сильную. Совпала и она — отправляем номер блока и прыгаем на B байт; иначе байт уходит как есть, и окно сдвигается на один.
Задача, которую решает rsync, отличается от той, что решает diff. Чтобы найти разницу двух файлов, нужны оба файла на одной машине. А здесь файлы на разных машинах, и связь между ними — самое дорогое: передать старую версию к новой ради сравнения — значит передать файл целиком, то есть ровно то, чего хотелось избежать. Суммы блоков — сжатое описание старой версии: 20 байт на 700, в 35 раз меньше самого файла.
Почему не сравнить блоки на их местах — первый блок с первым, второй со вторым? Потому что правки сдвигают текст. Вставили слово в начале — и каждый байт после него стоит уже на другом смещении, хотя содержимое то же. Блоки из старой версии надо искать в новой на любом месте, и именно это делает скользящая сумма.
Сумма, которая катится
Слабая сумма rsync — пара 16-битных чисел. Для окна из байтов xk, …, xl:
$$a(k, l) = \sum_{i=k}^{l} x_i \bmod 2^{16}, \qquad b(k, l) = \sum_{i=k}^{l} (l - i + 1)\,x_i \bmod 2^{16}.$$a — просто сумма байтов, b — сумма с весами: первый байт окна входит L раз, последний — один, где L = l − k + 1 — длина окна. Когда окно сдвигается на байт, xk уходит, xl+1 приходит:
$$a(k+1, l+1) = a(k, l) - x_k + x_{l+1}, \qquad b(k+1, l+1) = b(k, l) - L\,x_k + a(k+1, l+1).$$Вторая формула видна, если выписать веса. Уходящий байт весил L, его вычитаем. У остальных байтов окна вес уменьшается на единицу — они стали на позицию «старше» — и это то же, что ещё раз вычесть их сумму; а прибавить новую a, где новый байт уже учтён с весом 1, значит вернуть каждому байту по единице веса. В итоге старые байты сохраняют прежние веса относительно конца окна, а новый получает вес 1. Проверьте на названии главы: окно из восьми байтов катится по строке, и после каждого сдвига обе суммы, посчитанные по формулам, совпадают с посчитанными заново.
В отчёте, где rsync был впервые описан, сказано, что эта сумма придумана по образцу контрольной суммы Adler-32 Марка Адлера: та тоже складывает байты и суммы сумм. Зачем вторая сумма? Одна a не видит порядка байтов: у «нос» и «сон» она одна и та же. В тексте главы байты распределены похоже от окна к окну, и суммы 700 байт ложатся в узкий диапазон. Листинг считает: если бы rsync проверял только a, на правке с проверкой фактов слабая сумма обманула бы его 88 раз. Пара (a, b) не обманула ни разу.
Слабая сумма — только фильтр. Она дешёвая, и её легко подобрать нарочно, поэтому совпадение подтверждает сильная: MD4 в первой версии rsync, MD5 и xxHash в нынешней. Её считают только тогда, когда совпала слабая, — на настоящих файлах это почти всегда настоящие совпадения. Поиск в статье 1996 года устроен в три ступени: 16-битный хеш слабой суммы указывает строку таблицы из 216 строк, в ней ищется точное совпадение 32-битной слабой суммы, и лишь затем сверяется сильная.
Скользящую сумму придумал не rsync. Полиномиальный хеш, который так же сдвигается за O(1), лежит в основе поиска подстроки Рабина — Карпа, а подробно о таких хешах — в статье о скользящем хеше. У суммы rsync другое достоинство: она проще и быстрее, а надёжность добирает сильная сумма.
Код
Листинг повторяет опыт сцены: для каждой из пяти правок строит суммы блоков старой версии, катит окно по новой, собирает новую версию из старой и присланных кусков и проверяет, что она совпала байт в байт. Учёт честный: туда — 20 байт сумм на каждый блок, обратно — по 4 байта на номер блока и на длину каждого куска новых байтов, плюс сами байты.
Таблица правок из листинга:
| Правка | Блоков найдено | Новых байтов | Ушло по сети | Блоков на своём месте |
|---|---|---|---|---|
| правка стиля | 92 из 140 | 33 211 | 36 483 Б (37,6 %) | 3 |
| неразрывные пробелы | 129 из 139 | 7065 | 10 393 Б (10,7 %) | 15 |
| проверка фактов | 125 из 139 | 10 088 | 13 420 Б (13,8 %) | 0 |
| одно слово | 139 из 140 | 705 | 4065 Б (4,2 %) | 135 |
| короче описание | 139 из 140 | 598 | 3958 Б (4,1 %) | 1 |
Последний столбец — сколько блоков нашлось бы, если сравнивать их только на прежних местах. В правке «одно слово» «тысячи» стало «сто тысяч» ближе к концу главы: всё, что до этого места, осталось на своих местах — 135 блоков, — а сдвинулись только последние. Во всех остальных правках длина текста меняется уже в начале главы, и почти всё после этого места сдвигается.
Сколько это стоит
Время. Суммы блоков старой версии — один проход, O(n). Отправитель на каждом смещении делает O(1) работы и один поиск в хеш-таблице, а сильную сумму считает только при совпадении слабой; каждое настоящее совпадение съедает B байт, поэтому вся сильная сумма стоит O(m) на новую версию длиной m. Память — таблица из ⌈n/B⌉ сумм.
Сеть — главное. Суммы весят s байт на блок, их ⌈n/B⌉. Каждое место правки портит блок, в который попало, и этот кусок уходит как есть — примерно B байт. Чем крупнее блок, тем меньше сумм и тем больше байт тянет за собой каждая правка. Сцена ниже показывает это на всех пяти правках.
Пусть правки — это k мест, далеко отстоящих друг от друга, и каждое портит один блок. Тогда по сети уходит примерно T(B) = ns/B + kB байт. Наименьшее значение — 2√(nsk), при B = √(ns/k).
Среднее арифметическое двух положительных чисел не меньше среднего геометрического: ns/B + kB ≥ 2√((ns/B)·(kB)) = 2√(nsk). Размер блока под корнем сократился, так что оценка верна при любом B, а равенство наступает, когда слагаемые равны: ns/B = kB, то есть B = √(ns/k).
Проверим на проверке фактов. Листинг насчитал k = 15 мест правок, файл — 97 323 байта, s = 20. Формула даёт B ≈ 360, а перебор в сцене — лучший блок 400 байт и 12,1 КБ по сети; в листинге из размеров 100, 200, 300, 500, 700 лучший — 300. Оценка 2√(nsk) ≈ 10,8 КБ ниже настоящих 12,1 КБ: модель не учитывает длину самих правок, а здесь некоторые из них длиннее блока. Зато при правке стиля мест правок много, и лучший блок меньше — 200 байт, — а при правках в одном-двух местах — 1500. Точный перебор по всем размерам — вторая задача статьи; в ней видно, что правки, идущие кучками, сдвигают ответ далеко от формулы.
Настоящий rsync не перебирает: для файлов до 490 КБ блок равен 700 байтам, для больших — примерно √n, кратно восьми, но не больше 128 КБ. Корень из n — та же оценка при постоянном отношении s/k. И суммы у него короче. Сильная сумма отправляется не целиком, а столько байт, сколько нужно, чтобы случайное совпадение было маловероятным для файла такого размера: для главы в 97 КБ — 2 байта. С 4 байтами слабой суммы это 6 байт на блок вместо 20. Если всё же случится ложное совпадение, его поймает сумма всего файла, которую отправитель присылает в конце; тогда файл передаётся заново, уже с полными суммами.
Что ещё нужно в жизни
- Не трогать то, что не менялось. Прежде чем считать суммы, rsync сравнивает размер файла и время последнего изменения. Совпали — файл пропускается вовсе. На каталоге из тысяч файлов, где поменялись три, это главная экономия.
- Не ждать друг друга. Пока отправитель ищет блоки одного файла, получатель уже считает суммы следующего. Обе стороны работают одновременно, и задержка сети платится один раз, а не на каждый файл.
- Сжатые файлы. Сжатие уничтожает то, на чём держится rsync. Сжатый поток зависит от всего, что было до него, и правка в начале меняет все байты после неё. Так вышло с картинкой: JPEG хранит не пиксели, а сжатые коэффициенты (как это устроено, рассказывает глава курса о сжатии). Для архивов gzip с версии 1.7 есть ключ
--rsyncable: он время от времени сбрасывает состояние сжатия в местах, которые зависят только от содержимого, и небольшая правка меняет лишь кусок архива рядом с собой. - Сжимать то, что ушло. Новые байты и номера блоков можно сжать по дороге, как обычный поток. На тексте это дополнительно уменьшает передачу в несколько раз.
Где работает
rsync — стандартный способ скопировать каталог на другую машину так, чтобы повторная копия передавала только разницу: резервные копии, зеркала, выкладка сайтов.
librsync разделяет три шага алгоритма на отдельные действия: снять сигнатуру старого файла, по сигнатуре и новому файлу построить дельту, применить дельту к старому файлу. Сигнатуру и дельту можно хранить. Так устроены инкрементные резервные копии в программе Duplicity: в архив кладутся только дельты.
zsync переворачивает роли. Суммы блоков новой версии заранее лежат на обычном веб-сервере в файле .zsync, а катит окно клиент — по своей старой версии — и скачивает по HTTP только недостающие куски. Серверу не нужна никакая особая программа.
Нарезка по содержимому. Блоки фиксированной длины хороши, когда одна сторона знает старую версию. Если нужно найти общие куски среди многих файлов и версий, границы кусков ставят по самому содержимому: там, где отпечаток скользящего окна удовлетворяет условию, например кончается нужным числом нулевых битов. Вставка байта тогда сдвигает лишь ближайшую границу, а остальные куски остаются прежними. С этого начинала сетевая файловая система LBFS (2001), где окно хешировалось отпечатками Рабина.
История
Эндрю Триджелл и Пол Маккеррас описали алгоритм в техническом отчёте «The rsync algorithm» в 1996 году; программа rsync вышла тогда же. В отчёте есть и замеры: два архива исходников ядра Linux, версий 1.99.10 и 2.0.0, по 24 МБ каждый, синхронизировались при блоке в 500 байт передачей примерно миллиона байт новых данных, а ложных совпадений слабой суммы на 47 тысяч найденных блоков было 64. Подробный разбор алгоритма и его улучшений вошёл в диссертацию Триджелла 1999 года — «Эффективные алгоритмы сортировки и синхронизации».
Задачи
Первая задача — сам поиск: найти блоки старой версии в новой на любом смещении, и так, чтобы огромные блоки не превращали проверку каждого смещения в копирование. Во второй нужно выбрать размер блока точно, а не по формуле.
Старые блоки в новом файле Размер блокаДанные: Версии главы базового курса и картинки из истории правок legost.in (git)