Алгоритм Rsync
- Данная статья 100 % копипаст с www.openbsd.ru
Для чего он нужен?
Современные средства и протоколы удалённого копирования файлов (например, http, ftp, rcp), каждый раз полностью пересылают данные, несмотря на возможно уже существующею старую версию этих данных. Хотя и возможно воссоздать только изменения, например, с помощью утилиты diff, если существует старая копия наряду с новой, и тем самым пересылать только изменения, но в практике это не всегда удобно и часто приводит к ошибкам.
Задачи алгоритма rsync:
- Он должен работать с произвольными данными, не только с обычным текстом.
- Размер передаваемых данных должен быть примерно равен размеру diff файла.
- Он должен быстро работать с большими файлами.
- Алгоритм не должен иметь какие-либо предварительные знания о статусе этих файлов, но должен эффективно находить их возможные сходства.
- Использовать мало ресурсов.
Представим, что у нас имеются файлы A и B, и мы хотим обновить B таким образом, чтобы его содержимое было идентично содержимому файла A. Самый простой и очевидный способ — это скопировать A в B.
Теперь представим, что эти файлы находятся на двух разных машинах, соединённых медленным каналом связи, например, с помощью dialup модема. Если файл A большой, копирование A в B будет происходить очень медленно. Чтобы сделать это быстрее, мы можем сжать A, перед тем как пересылать его. Но обычный коэффициент сжатия колеблется от 2 до 4, что так же не подойдёт для нашей медленной связи.
Предположим, что файлы A и B почти одинаковы (возможно, оба были получены из одного общего файла). Для увеличения производительности копирования мы можем воспользоваться преимуществом их сходства. Обычное решение этой проблемы заключается в том, чтобы пересылать только изменения между файлами A и B и затем использовать их для реконструкции фала B.
Но проблема в том, что для получения этих изменений необходимо иметь возможность чтения обоих файлов. Поэтому нам нужно иметь оба файла на одной из сторон нашего соединения. В противном случае, этот алгоритм использоваться не может. Для решения этой проблемы и был разработан алгоритм rsync.
Алгоритм
Общий алгоритм
На двух разных компьютерах Alpha и Beta, соединённых медленным каналом связи (например, через модем), находятся два файла A и B.
Структура алгоритма:
- Beta отсылает некоторые данные S на компьютер Alpha
- Alpha сравнивает эти данные с файлом A и отсылает некоторые данные D на компьютер Beta
- Beta создаёт копию файла A на основе файла B, данных S и D
Главный вопрос в том, какую форму примут данные S, как компьютер Alpha будет использовать S для сопоставления с файлом A, и как Beta будет реконструировать A.
Алгоритм rsync
Алгоритм rsync:
- Beta разбивает файл B на блоки длиной L (последний блок может быть меньше Lбайт) и вычисляет две сигнатуры Rb и Sb для каждого блока, после чего пересылает эти сигнатуры к Alpha.
- Alpha вычисляет сигнатуры Ra для блоков длиной L для каждого байтового смещения. После чего сравнивает их с Rb.
- Для блоков, чьи R сигнатуры совпали, Alpha вычисляет Sa и сравнивает с Sb.
- Если S сигнатуры совпадают, Alpha отсылает уведомление с номером совпавшего блока, в противном случае Alpha пересылает один байт.
- Beta получает номера совпавших блоков из B или одиночные байты из файла A и на основе этих данных создаёт копию файла A.
Важно понимать, что ключом алгоритма является создание двух сигнатур — быстрой и стойкой. Быстрая (R) используется как фильтр (на компьютере Alpha она вычисляется для каждого байтового смещения!). Стойкая (S) используется для более точной проверки. Алгоритм rsync Алгоритм rsync
Стойкая сигнатура
Стойкая сигнатура может не быть быстрой, так как вычисляется только при совпадении простой, быстрой сигнатуры. Главным свойством стойкой сигнатуры должна быть минимальная вероятность отказа, иначе говоря, наличие одной и той же сигнатуры для двух разных блоков.
Существует множество алгоритмов с такими свойствами, возможно, наиболее известный — это алгоритм хеширования Message Digest. Он часто используется в криптографических программах.
Быстрая сигнатура
Быстрая сигнатура очень важна для эффективности алгоритма rsync. Она работает как фильтр, предотвращая вычисление стойкой сигнатуры. Основная задача быстрой сигнатуры — это максимально быстрое её вычисление для каждого байтового смещения в файле.
Первоначально для создания быстрой сигнатуры в rsync было опробовано простое склеивание первых и последних 4 байт блока. Хотя такой алгоритм, в принципе, работал, но был выявлен его серьёзный недостаток. Для определённых типов данных, например, для tar файла, он слишком часто создавал одинаковые сигнатуры для разных частей файла, что приводило к многократному вычислению стойкой сигнатуры и, как следствие, падению производительности всего алгоритма.
Это привело к необходимости выбора нового алгоритма для вычисления быстрой сигнатуры, значение которого зависело бы от всех байт блока, но при этом вычисление оставалось таким же простым и быстрым. Им стал алгоритм, похожий на adler32 от Марка Адлера. Adler32 — алгоритм расчёта контрольных сумм, похожий на довольно распространённый алгоритм CRC32, но при этом более быстрый.
Поиск сигнатур
Для эффективности поиска используется хеширование быстрой сигнатуры и трехуровневый поиск. Ключом хеш-функции является значение 32-x битной сигнатуры, а значением — сумма двух её (16-ти битных) половин.
Поиск сигнатур
- Search.gif
Поиск сигнатур
Поиск сигнатур
На первом уровне формируется хеш-таблица размером в 2^16 элементов. Ключом хеш-функции является быстрая 32 битная сигнатура. Для каждой пары быстрой и стойкой сигнатуры, полученной от Beta, вычисляется 16 битный хеш 32 битной сигнатуры, после чего все это сортируется согласно 16 битному хешу. Каждый элемент хеш-таблицы указывает на первый элемент сортированных сигнатур, хеш значения которых совпадают, либо хранит в себе NULL, если сигнатур с таким хешом нет. Номер элемента хеш-таблицы соответствует значению хеш-функции, а именно сумме двух половин быстрой 32 битной сигнатуры.
Затем для каждого байтового смещения вычисляется быстрая 32 битная сигнатура и 16 битное хеш-значение. Если элемент хеш-таблицы для этого хеш-значения не равен NULL, алгоритм поиска переходит на следующий уровень.
На втором уровне происходит линейный поиск по сортированному списку сигнатур, начиная с элемента, указанного в хеш-таблице. Мы ищем быструю 32 битную сигнатуру, чьё значение совпадает с необходимым нам значением. Поиск прекращается при первом же несовпадении 16 битной сигнатуры. Если мы нашли такую 32 битную сигнатуру, алгоритм переходит на следующий уровень.
На третьем уровне происходит вычисление стойкой сигнатуры для текущего смещения в файле и сравнение его со значением стойкой сигнатуры в сортированном списке. При совпадении предполагается, что мы нашли блок в файле A, который есть в файле B. Фактически, блоки могут быть различны, но вероятность этого очень мала.
При совпадении блоков Alpha отсылает Beta данные из файла A между текущим смещением и предыдущим совпадением, а также индекс совпавшего блока, который есть в B. Эти данные отсылаются сразу же при нахождении совпадения.
Если совпадения найдено не было для текущего смещения в файле A, вычисляется быстрая сигнатура для следующего байтового смещения и процедура поиска повторяется. При совпадении смещение увеличивается на размер совпавшего блока, и поиск продолжается.
Реконструкция файла
Одна из простых частей алгоритма rsync — реконструкция файла. После того, как компьютер Beta отсылает сигнатуры, Alpha присылает байты из файла A или сообщения, которые содержат номера совпавших блоков.
Для реконструкции файла B нам необходимо последовательно вписывать полученные байты в файл и при получении сообщения о совпавшем блоке вписывать целый блок из старого файла. Реконструкция не производится непосредственно в старом файле, так как нам необходим произвольный доступ к старым данным. Для реконструкции создаётся временный файл, который затем переименовывается.
Конвейерная обработка
Важным фактором быстродействия является задержка между пересылаемыми файлами. Обычно используемые протоколы передачи данных, такие как ftp, rcp или rdist обрабатывают каждый файл как отдельную операцию, тем самым ожидая подтверждения о доставке текущего файла, перед тем как обрабатывать следующий.
При использовании большого количества маленьких файлов (например, обычное зеркалирование Web-сайта) для пересылки через Internet, это время ожидания может сыграть роковую роль. Чтобы избежать этого, мы можем пересылать, не ожидая подтверждения. Этот метод также известен, как конвейерная обработка.
Схема конвейерной обработки
- Pipe.gif
Схема конвейерной обработки
Процесс разбивается на 3 части — Generator, Sender и Receiver. Generator запускается на компьютере Beta и генерирует сигнатуры для всех файлов, которые необходимо переслать, и отсылает эти сигнатуры к Alpha. Sender, запущенный на Alpha получает сигнатуры и отсылает сообщения о совпавших блоках или целые байты Beta. Receiver, запущенный на Beta, реконструирует файл, после чего он связывается с Generator, чтобы сообщить об успешной передачи файла, либо передать ему, что определённый файл необходимо обработать заново.
Заключение
Алгоритм rsync предоставляет эффективное решение проблемы удалённого обновления файлов. Метод двух сигнатур, используемый в алгоритме, позволяет эффективно находить совпадения на любом смещении файла. Алгоритм гарантирует точность передачи, подтверждая подлинность блока стойкой сигнатурой. Используемая литература
- Rsync technical report. Andrew Tridgell и Paul Mackerras. 1998г.
- Efficient Algorithms for Sorting and Synchronization. Andrew Tridgell. 2000г.
- Zlib Technical Details. Jean-loup Gailly и Mark Adler.