rsync in a nutshell

3 месяца назад, 30 лет тому, австралийский национальный университет дропает эту имбу. Алгоритм для модифицирования файла на удалённой машине для соответствия оригинальному. Если по-простому, то переносить диффы. Это если кто до этого про rsync не слышал.

У меня, если что, просто интернета нет. Со скуки нашёл откуда-то бумагу по нему. Вот и пишу теперь с хотспота. А вам читать.


Собственно, диффы. Можно, конечно, и их перекидывать, но есть проблема. Взяли ядро GNU/линукса версий 1.99.10 и 2.0.0, там 32к строк разницы. GNUшный diff выдал выхлопа на 2.1мб. Когда тестили rsync, в среднем там по сети перелетало 1.5мб (рекорд - 1.2мб). Так ещё и пока diff 4 минуты ебался, rsync за 2 минуты отфинишировал. Конкретно здесь - чем быстрее кончил, тем наоборот лучше.

Diff mogged. Особенно учитывая решаемую проблему - синхронизация файлов в условиях сети с высокой задержкой и низкой пропускной способностью.


Задачи выплёвывать человекочитаемые диффы не стояло, поэтому алгоритм прост как три пизды: есть компьютер А, есть компьютер Б. Компьютер А держит оригинал, Б хочет синхронизироваться. Недофайл, который лежит на Б, делится на блоки по S байт, для каждого считаем rolling checksum и MD5 хэш*. Они парами отправляются компьютеру А. Дальше А умным образом смотрит у себя, что из этого всего у него есть, и отправляет обратно Б инструкцию, что и куда записать, чтобы получить копию.

*в оригинальной бумаге используется MD4. MD5 вышел в 1991, а бумага по rsync - в 1996. Скорее всего, выбор был сделан на основе перфа - MD4 быстрее, а MD5 сильнее криптографически. Может, последний и правда уменьшает риск коллизий, ака ПОВЫШАЕТ ЭНТРОПИЮ. Тогда переход имел смысл, как только компьютеры стали шустрее калькуляторов из Техаса.

Ну так вот, умный образ. Он классный. Компьютер А проходится по всему файлу, и для каждого оффсета считает rolling checksum. Да, дороговато, мы пересчитываем чексумму для практически каждого байта в файле. Но это простенькая 32-битная чексумма, похожая на adler-32, и она определена, как взвешенная сумма байт. Поэтому, чтобы посчитать чексумму для следующего оффсета, из неё достаточно просто вычесть первый сумманд и прибавить новый. Таким образом и выходит быстро и дёшево пробежать по всему файлу и найти все блоки S байт, которые соответствуют оным в наличии у Б.

Естественно, это слабая чексумма. Я где-то оставлю документ, 3 раздел о ней. Но сила ей и не нужна, для силы есть MD5.

А дальше начинается самое интересное. Дальше начинается хэшмапа на открытой адрессации!

rsync использует трёхуровневую схему поиска совпадающих блоков. Когда А получает все пары чексумм-MD5, он считает 16-битный хэш от 32-битной чексуммы и сортирует пары, полученные от Б, по этому хешу. Получается хэшмапа на 2^16 слотов.

Вот и выходит: когда А считает чексумму, он сразу берёт от неё хэш и идёт в мапу. First-level check - проверка на то, что с таким хэшем вообще не-нулевой слот. Потом линейно ищется слот со совпадающей чексуммой - это second-level check (до тех пор, пока хэш чексуммы не перестанет совпадать с посчитанным). О мапах на открытой адрессации я подробнее здесь писал.

Когда находится совпадающая чексумма, наступает очередь считать и сравнивать MD5 хэши. Если ещё и он сходится, то тогда уже А выдает инструкцию Б записать данные от предыдущего мэтча до текущей позиции в файле - это данные, которых у Б нет. За ними следует индекс блока, который у Б есть. Чем-то на LZ77 похоже.

А главное - это работает хорошо для практически-идентичных файлов.

Под постом оставлю сниппет с псевдокодом на расте, как примерно устроена вся эта эпопея со скользящей чексуммой.