Алгоритм Rsync - История изменений

Nordwind: /* Поиск сигнатур */

2013-07-15T13:02:26Z

Поиск сигнатур

Nordwind: /* Быстрая сигнатура */

2013-07-10T15:39:03Z

Быстрая сигнатура

Nordwind: /* Алгоритм */

2013-07-10T14:53:16Z

Алгоритм

Nordwind в 14:46, 10 июля 2013

2013-07-10T14:46:31Z

Nordwind: /* Для чего он нужен? */

2013-07-10T14:44:54Z

Для чего он нужен?

Nordwind: Новая страница: «==Для чего он нужен?== Современные средства и протоколы удалённого копирования файлов (на…»

2013-07-10T14:42:46Z

Новая страница: «==Для чего он нужен?== Современные средства и протоколы удалённого копирования файлов (на…»

Новая страница

==Для чего он нужен?==

Современные средства и протоколы удалённого копирования файлов (например, http, ftp, rcp), каждый раз полностью пересылают данные, несмотря на возможно уже существующею старую версию этих данных. Хотя и возможно воссоздать только изменения, например, с помощью утилиты diff, если существует старая копия наряду с новой, и тем самым пересылать только изменения, но в практике это не всегда удобно и часто приводит к ошибкам.

Задачи алгоритма <tt>rsync</tt>:

# Он должен работать с произвольными данными, не только с обычным текстом.
# Размер передаваемых данных должен быть примерно равен размеру diff файла.
# Он должен быстро работать с большими файлами.
# Алгоритм не должен иметь какие-либо предварительные знания о статусе этих файлов, но должен эффективно находить их возможные сходства.
# Использовать мало ресурсов.

Представим, что у нас имеются файлы '''A''' и '''B''', и мы хотим обновить '''B''' таким образом, чтобы его содержимое было идентично содержимому файла '''A'''. Самый простой и очевидный способ — это скопировать '''A''' в '''B'''.

Теперь представим, что эти файлы находятся на двух разных машинах, соединённых медленным каналом связи, например, с помощью <tt>dialup</tt> модема. Если файл '''A''' большой, копирование '''A''' в '''B''' будет происходить очень медленно. Чтобы сделать это быстрее, мы можем сжать '''A''', перед тем как пересылать его. Но обычный коэффициент сжатия колеблется от 2 до 4, что так же не подойдёт для нашей медленной связи.

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

Но проблема в том, что для получения этих изменений необходимо иметь возможность чтения обоих файлов. Поэтому нам нужно иметь оба файла на одной из сторон нашего соединения. В противном случае, этот алгоритм использоваться не может. Для решения этой проблемы и был разработан алгоритм <tt>rsync</tt>.

== Алгоритм ==

'''=== Общий алгоритм ==='''

На двух разных компьютерах ''Alpha'' и ''Beta'', соединённых медленным каналом связи (например, через модем), находятся два файла '''A''' и '''B'''.

Структура алгоритма:

# ''Beta'' отсылает некоторые данные '''S''' на компьютер ''Alpha''
# ''Alpha'' сравнивает эти данные с файлом '''A''' и отсылает некоторые данные '''D''' на компьютер ''Beta''
# ''Beta'' создаёт копию файла '''A''' на основе файла '''B''', данных '''S''' и '''D'''

Главный вопрос в том, какую форму примут данные '''S''', как компьютер ''Alpha'' будет использовать '''S''' для сопоставления с файлом '''A''', и как ''Beta'' будет реконструировать ''A''.

'''=== Алгоритм <tt>rsync</tt> ==='''

Алгоритм <tt>rsync</tt>:

# ''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'') используется для более точной проверки.
[[File:rsync.gif|link=http://www.openbsd.pw/files/openbsd_ru/docs/images/rsync.gif|Алгоритм rsync]]
Алгоритм rsync

== Стойкая сигнатура ==

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

Существует множество алгоритмов с такими свойствами, возможно, наиболее известный — это алгоритм хеширования ''Message Digest''. Он часто используется в криптографических программах.

== Быстрая сигнатура ==

Быстрая сигнатура очень важна для эффективности алгоритма <tt>rsync</tt>. Она работает как фильтр, предотвращая вычисление стойкой сигнатуры. Основная задача быстрой сигнатуры — это максимально быстрое её вычисление для каждого байтового смещения в файле.

Первоначально для создания быстрой сигнатуры в <tt>rsync</tt> было опробовано простое склеивание первых и последних 4 байт блока. Хотя такой алгоритм, в принципе, работал, но был выявлен его серьёзный недостаток. Для определённых типов данных, например, для <tt>tar</tt> файла, он слишком часто создавал одинаковые сигнатуры для разных частей файла, что приводило к многократному вычислению стойкой сигнатуры и, как следствие, падению производительности всего алгоритма.

Это привело к необходимости выбора нового алгоритма для вычисления быстрой сигнатуры, значение которого зависело бы от всех байт блока, но при этом вычисление оставалось таким же простым и быстрым. Им стал алгоритм, похожий на adler32 от Марка Адлера. Adler32 — алгоритм расчёта контрольных сумм, похожий на довольно распространённый алгоритм CRC32, но при этом более быстрый.
Поиск сигнатур
Для эффективности поиска используется хеширование быстрой сигнатуры и трехуровневый поиск. Ключом хеш-функции является значение 32 битной сигнатуры, а значением — сумма двух её (16 битных) половин.
Поиск сигнатур
Поиск сигнатур

На первом уровне формируется хеш-таблица размером в 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, это время ожидания может сыграть роковую роль. Чтобы избежать этого, мы можем пересылать, не ожидая подтверждения. Этот метод также известен, как конвейерная обработка.
Схема конвейерной обработки
Схема конвейерной обработки

Процесс разбивается на 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.

← Предыдущая		Версия 14:44, 10 июля 2013
Строка 1:		Строка 1:
		+	:Данная статья 100 % копипаст с [http://www.openbsd.ru www.openbsd.ru]<br />
		+
	==Для чего он нужен?==		==Для чего он нужен?==

@@ Строка 70: / Строка 70: @@
 Поиск сигнатур
 <gallery>
-Файл:Example.jpg|Описание1
+Файл:search.gif |Поиск сигнатур
 </gallery>
 Поиск сигнатур
@@ Строка 81: / Строка 80: @@
 На втором уровне происходит линейный поиск по сортированному списку сигнатур, начиная с элемента, указанного в хеш-таблице. Мы ищем быструю 32 битную сигнатуру, чьё значение совпадает с необходимым нам значением. Поиск прекращается при первом же несовпадении 16 битной сигнатуры. Если мы нашли такую 32 битную сигнатуру, алгоритм переходит на следующий уровень.
-На третьем уровне происходит вычисление стойкой сигнатуры для текущего смещения в файле и сравнение его со значением стойкой сигнатуры в сортированном списке. При совпадении предполагается, что мы нашли блок в файле A, который есть в файле B. Фактически, блоки могут быть различны, но вероятность этого очень мала.
+На третьем уровне происходит вычисление стойкой сигнатуры для текущего смещения в файле и сравнение его со значением стойкой сигнатуры в сортированном списке. При совпадении предполагается, что мы нашли блок в файле '''A''', который есть в файле '''B'''. Фактически, блоки могут быть различны, но вероятность этого очень мала.
-При совпадении блоков Alpha отсылает Beta данные из файла A между текущим смещением и предыдущим совпадением, а также индекс совпавшего блока, который есть в B. Эти данные отсылаются сразу же при нахождении совпадения.
+При совпадении блоков ''Alpha'' отсылает ''Beta'' данные из файла '''A''' между текущим смещением и предыдущим совпадением, а также индекс совпавшего блока, который есть в '''B'''. Эти данные отсылаются сразу же при нахождении совпадения.
-Если совпадения найдено не было для текущего смещения в файле A, вычисляется быстрая сигнатура для следующего байтового смещения и процедура поиска повторяется. При совпадении смещение увеличивается на размер совпавшего блока, и поиск продолжается.
+Если совпадения найдено не было для текущего смещения в файле '''A''', вычисляется быстрая сигнатура для следующего байтового смещения и процедура поиска повторяется. При совпадении смещение увеличивается на размер совпавшего блока, и поиск продолжается.
-Для реконструкции файла B нам необходимо последовательно вписывать полученные байты в файл и при получении сообщения о совпавшем блоке вписывать целый блок из старого файла. Реконструкция не производится непосредственно в старом файле, так как нам необходим произвольный доступ к старым данным. Для реконструкции создаётся временный файл, который затем переименовывается.
+== Реконструкция файла ==
 Конвейерная обработка
-Важным фактором быстродействия является задержка между пересылаемыми файлами. Обычно используемые протоколы передачи данных, такие как ftp, rcp или rdist обрабатывают каждый файл как отдельную операцию, тем самым ожидая подтверждения о доставке текущего файла, перед тем как обрабатывать следующий.
+Одна из простых частей алгоритма <tt>rsync</tt> — реконструкция файла. После того, как компьютер ''Beta'' отсылает сигнатуры, ''Alpha'' присылает байты из файла '''A''' или сообщения, которые содержат номера совпавших блоков.
 Схема конвейерной обработки
 Алгоритм rsync предоставляет эффективное решение проблемы удалённого обновления файлов. Метод двух сигнатур, используемый в алгоритме, позволяет эффективно находить совпадения на любом смещении файла. Алгоритм гарантирует точность передачи, подтверждая подлинность блока стойкой сигнатурой.
 Используемая литература
-    Rsync technical report. Andrew Tridgell и Paul Mackerras. 1998г.
+# [http://rsync.samba.org/tech_report/ Rsync technical report]. Andrew Tridgell и Paul Mackerras. 1998г.
-    Efficient Algorithms for Sorting and Synchronization. Andrew Tridgell. 2000г.
+# [http://www.samba.org/~tridge/phd_thesis.pdf Efficient Algorithms for Sorting and Synchronization]. Andrew Tridgell. 2000г.
-    Zlib Technical Details. Jean-loup Gailly и Mark Adler.
+# [http://www.gzip.org/zlib/zlib_tech.html Zlib Technical Details]. Jean-loup Gailly и Mark Adler.

@@ Строка 62: / Строка 62: @@
 Первоначально для создания быстрой сигнатуры в <tt>rsync</tt> было опробовано простое склеивание первых и последних 4 байт блока. Хотя такой алгоритм, в принципе, работал, но был выявлен его серьёзный недостаток. Для определённых типов данных, например, для <tt>tar</tt> файла, он слишком часто создавал одинаковые сигнатуры для разных частей файла, что приводило к многократному вычислению стойкой сигнатуры и, как следствие, падению производительности всего алгоритма.
-Это привело к необходимости выбора нового алгоритма для вычисления быстрой сигнатуры, значение которого зависело бы от всех байт блока, но при этом вычисление оставалось таким же простым и быстрым. Им стал алгоритм, похожий на adler32 от Марка Адлера. Adler32 — алгоритм расчёта контрольных сумм, похожий на довольно распространённый алгоритм CRC32, но при этом более быстрый.
+Это привело к необходимости выбора нового алгоритма для вычисления быстрой сигнатуры, значение которого зависело бы от всех байт блока, но при этом вычисление оставалось таким же простым и быстрым. Им стал алгоритм, похожий на <tt>adler32 от Марка Адлера. <tt>Adler32</tt> — алгоритм расчёта контрольных сумм, похожий на довольно распространённый алгоритм CRC32, но при этом более быстрый.
 Поиск сигнатур
-Для эффективности поиска используется хеширование быстрой сигнатуры и трехуровневый поиск. Ключом хеш-функции является значение 32 битной сигнатуры, а значением — сумма двух её (16 битных) половин.
+== Поиск сигнатур ==
 Поиск сигнатур
 Поиск сигнатур

@@ Строка 47: / Строка 47: @@
 Важно понимать, что ключом алгоритма является создание двух сигнатур — быстрой и стойкой. Быстрая ('''R''') используется как фильтр (на компьютере ''Alpha'' она вычисляется для каждого байтового смещения!). Стойкая (''S'') используется для более точной проверки.
-[[File:rsync.gif|link=http://www.openbsd.pw/files/openbsd_ru/docs/images/rsync.gif|Алгоритм rsync]]
+[[File:http://www.openbsd.pw/files/openbsd_ru/docs/images/rsync.gif|link=http://www.openbsd.pw/files/openbsd_ru/docs/images/rsync.gif|Алгоритм rsync]]
 Алгоритм rsync

@@ Строка 24: / Строка 24: @@
 == Алгоритм ==
-'''=== Общий алгоритм ==='''
+'''Общий алгоритм'''
 На двух разных компьютерах ''Alpha'' и ''Beta'', соединённых медленным каналом связи (например, через модем), находятся два файла '''A''' и '''B'''.
@@ Строка 36: / Строка 36: @@
 Главный вопрос в том, какую форму примут данные '''S''', как компьютер ''Alpha'' будет использовать '''S''' для сопоставления с файлом '''A''', и как ''Beta'' будет реконструировать ''A''.
-'''=== Алгоритм <tt>rsync</tt> ==='''
+'''Алгоритм <tt>rsync</tt>'''
 Алгоритм <tt>rsync</tt>: