Logo    
Деловая газета CitCity.ru CITKIT.ru - все об Open Source Форумы Все публикации Учебный центр Курилка
CitForum    CITForum на CD    Подписка на новости портала Море(!) аналитической информации! :: CITFORUM.RU
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

23.04.2017

Google
WWW CITForum.ru
С Новым годом!
2004 г

Алгоритм Rsync

www.openbsd.ru

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

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

Задачи алгоритма rsync:

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

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

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

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

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

Алгоритм

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

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

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

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

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

Алгоритм rsync

Алгоритм rsync:

  1. Beta разбивает файл B на блоки длиной L (последний блок может быть меньше L байт) и вычисляет две сигнатуры Rb и Sb для каждого блока, после чего пересылает эти сигнатуры к Alpha .
  2. Alpha вычисляет сигнатуры Ra для блоков длинной L , для каждого байтового смещения. После чего сравнивает их с Rb .
  3. Для блоков, чьи R сигнатуры совпали, Alpha вычисляет Sa и сравнивает с Sb .
  4. Если S сигнатуры совпадают, Alpha отсылает уведомление с номером совпавшего блока, в противном случае Alpha пересылает один байт.
  5. Beta получает номера совпавших блоков из B или одиночные байты из файла A и на основе этих данных создаёт копию файла A .

Важно понимать, что ключом алгоритма является создание двух сигнатур - быстрой и стойкой. Быстрая ( R ) используется как фильтр (на компьютере Alpha она вычисляется для каждого байтового смещения!). Стойкая ( S ) используется для более точной проверки.

Алгоритм rsync
Алгоритм rsync.

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

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

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

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

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

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

Это привело к необходимости выбора нового алгоритма для вычисления быстрой сигнатуры, значение которого зависело бы от всех байт блока, но при этом вычисление оставалось таким же простым и быстрым. Им стал алгоритм похожий на 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 предоставляет эффективное решение проблемы удалённого обновления файлов. Метод двух сигнатур используемый в алгоритме позволяет эффективно находить совпадения на любом смещении файла. Алгоритм гарантирует точность передачи подтверждая подлинность блока стойкой сигнатурой.

Используемая литература

  1. Rsync technical report . Andrew Tridgell и Paul Mackerras. 1998г.
  2. Efficient Algorithms for Sorting and Synchronization . Andrew Tridgell. 2000г.
  3. Zlib Technical Details . Jean-loup Gailly и Mark Adler.

Размещение рекламы — тел. +7 495 4119920, ICQ 232284597

Подписка на новости IT-портала CITForum.ru
(библиотека, CITKIT.ru, CitCity)

Новые публикации:

24 декабря

CITKIT.ru:

  • Новогодние поздравления
  • Сергей Кузнецов. Цикл Операционные системы: Ностальгия по будущему:

  • Алексей Федорчук. OpenSolaris 2008.11 Release

  • Сергей Голубев:

  • Евгений Чайкин aka StraNNik (Блогометки):

    17 декабря

  • С.Д.Кузнецов. Базы данных. Вводный курс

    10 декабря

    CITKIT.ru:

  • OpenSolaris 2008.11 Release

  • Альтернативные ОС: две грустные истории (С.Кузнецов)
  • Nokia N810 — доведение до ума
  • CitCity:

  • Платформа 2009: заоблачные перспективы Microsoft

    4 декабря

  • Лекция С.Д.Кузнецова Понятие модели данных. Обзор разновидностей моделей данных

    CITKIT.ru:

  • OpenSolaris 2008.11 Release. Первые впечатления

  • Linux vs FreeBSD: продолжим "Священные войны"?

  • Nokia N810 as is

  • Индульгенция для FOSS

  • Друзья СПО'2008

    26 ноября

  • Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

    CitCity:

    CITKIT.ru:

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • 19 ноября

  • Проблемы экономики производства крупных программных продуктов

  • Язык модификации данных формата XML функциональными методами

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Заметки к книге:

  • FreeBSD: монтирование сменных устройств и механизм HAL
  • Текстовый редактор ee

    12 ноября

  • Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила (Гоц Грейф, перевод: Сергей Кузнецов)

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:
  • OSS в России: взгляд правоведа (В.Житомирский)

  • Новая статья из цикла С.Голубева "Железный марш":

    29 октября

  • О некоторых задачах обратной инженерии

  • Веб-сервисы и Ruby

  • Тестирование web-приложений с помощью Ruby

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

  • PuppyRus Linux - беседа с разработчиком (С.Голубев)

  • Сергей Кузнецов. Заметка не про Linux

    22 октября

  • Обзор методов описания встраиваемой аппаратуры и построения инструментария кросс-разработки

    CITKIT.ru:

  • Сергей Кузнецов. Почему я равнодушен к Linux

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • Что надо иметь
    3. Базовые познания

    CitCity:

  • Управление IT-инфраструктурой на основе продуктов Microsoft

    15 октября

  • Методы бикластеризации для анализа интернет-данных

    CitCity:

  • Разъемы на ноутбуках: что они дают и зачем их так много?
  • AMD Puma и Intel Centrino 2: кто лучше?

    CITKIT.ru:

  • Новый цикл статей С.Голубева
    Железный марш:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    8 октября

  • Автоматизация тестирования web-приложений, основанных на скриптовых языках
  • Опыт применения технологии Azov для тестирования библиотеки Qt3

    Обзоры журнала Computer:

  • SOA с гарантией качества
  • Пикоджоуль ватт бережет
  • ICT и всемирное развитие

    CitCity:

  • Пиррова победа корпорации Microsoft

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Статья из архива:

  • Я живу в FreeBSD (Вадим Колонцов)

    Новые Блогометки:

  • Перекройка шаблона Blogger или N шагов к настоящему
  • Blogger. Comment style
  • Screenie или глянцевый снимок экрана

    2 октября

    CITKIT.ru:

  • Сага о FreeBSD (А. Федорчук)

    Zenwalk: пакет недели

  • Банинг — интеллектуальное развлечение (С.Голубев)

    CitCity:

    25 сентября

  • Клермонтский отчет об исследованиях в области баз данных

    CITKIT.ru:

  • Пользователям просьба не беспокоиться... (В.Попов)

  • Снова про ZFS: диск хорошо, а два лучше
  • Командная оболочка tcsh (А.Федорчук)

    Zenwalk: пакет недели

    17 сентября

  • T2C: технология автоматизированной разработки тестов базовой функциональности программных интерфейсов
  • Технология Azov автоматизации массового создания тестов работоспособности

    CITKIT.ru:

  • FreeBSD: ZFS vs UFS, и обе-две — против всех (А.Федорчук)

    Zenwalk: пакет недели

  • Дачнет — практика без теории (С.Голубев)

    10 сентября

  • За чем следить и чем управлять при работе приложений с Oracle
  • Планировщик заданий в Oracle
    (В.Пржиялковский)

    CITKIT.ru:

  • Microsoft: ответный "боян" (С.Голубев)

  • Причуды симбиоза, или снова "сделай сам" (В.Попов)

  • Файловые системы современного Linux'а: последнее тестирование
  • Zsh. Введение и обзор возможностей
    (А.Федорчук)

    Описания пакетов Zenwalk: Zsh, Thunar, Thunar-bulk-rename, Xfce4-places-plugin, Xfce4-fsguard-plugin

    Блогометки:

  • Google Chrome
  • Лончер для ASUS Eee PC 701

    3 сентября

    CITKIT.ru:

  • Заметки о ядре (А.Федорчук):

    Добавлены описания пакетов Zenwalk: Galculator, Screenshot, Gnumeric, Pidgin

    В дискуссинном клубе:

  • И еще о Википедии и Google Knol

  • Лекция для начинающего линуксоида (С.Голубев)

    26 августа

  • Транзакционная память (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Открыт новый проект Zenwalk: пакет недели

  • Статья Текстовые процессоры и их быстродействие: конец еще одной легенды?

    21 августа

    CITKIT.ru:

  • Почему школам следует использовать только свободные программы (Ричард Столлман)
  • Беседа Сергея Голубева с учителем В.В.Михайловым

  • Википедия или Гуглезнание? Приглашение к обсуждению (Алексей Федорчук)
  • Народная энциклопедия от Google (StraNNik)

  • Обзор Mandriva 2009.0 Beta 1 Thornicrofti
  • Новичок в Линукс: Оптимизируем Mandriva 2008.1

  • Книга Zenwalk. Приобщение к Linux:

    13 августа

    CitCity:

  • Мирный Atom на службе человеку. Обзор платы Intel D945GCLF с интегрированным процессором
  • Обзор процессоров Intel Atom 230 на ядре Diamondville

  • iPhone - год спустя. Скоро и в России?

    CITKIT.ru:

  • Интермедия 3.4. GRUB: установка и настройка (из книги Zenwalk. Приобщение к Linux)

    6 августа

  • СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности? (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Интермедия 2.2. Что неплохо знать для начала (из книги Zenwalk. Приобщение к Linux)

  • И снова про шрифты в Иксах (А.Федорчук)

  • 20 самых быстрых и простых оконных менеджеров для Linux

  • Дело о трех миллиардах (С.Голубев)

    30 июля

  • OLTP в Зазеркалье (Пересказ: С. Кузнецов)

    CitCity:

  • Будущее BI в облаках?
  • Тиражные приложения и заказная разработка. Преимущества для заказчика
  • Дискуссия со сторонниками заказной разработки

    CITKIT.ru:

  • Новые главы книги Zenwalk. Приобщение к Linux:
  • Глава 8. Пакеты: средства установки, системы управления, системы построения
  • Глава 9. Zenwalk: репозитории, пакеты, методы установки

    23 июля

    CITKIT.ru:

  • Все против всех. 64 vs 32, Intel vs AMD, tmpfs vs ext3
  • Две головы от Intel

  • Zenwalk: обзор штатных приложений (глава из книги "Zenwalk. Приобщение к Linux")

  • Нормально, Григорий...

    16 июля

    Обзоры журнала Computer:

  • Перспективы и проблемы программной инженерии в XXI веке
  • Большие хлопоты с большими объемами данных
  • Перспективы наноэлектроники

    CITKIT.ru:

  • Интермедия о лицензиях (А.Федорчук. "Zenwalk. Приобщение к Linux")

  • Есть ли будущее у KDE?

  • Linux в школе: альтернативный вариант в задачах

  • Шифр (приключения агента Никодима)

    10 июля

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия вступительная. Linux или GNU/Linux? Как вас теперь называть?
  • Глава 5. Среда Xfce
  • Глава 6. Xfce: приложения и плагины

  • ZUR (Zenwalk User Repository) FAQ

    2 июля

  • Персистентность данных в объектно-ориентированных приложениях (С. Кузнецов)

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия 1.2. Дорога к Zenwalk'у. Период бури и натиска
  • Интермедия 3.3. Немного о Linux'е и "железе"
  • Глава 4. Настройка: инструментами и руками
  • Интермедия 4.1. Zenpanel и конфиги: поиски корреляции

  • Интервью с Жан-Филиппом Гийоменом, создателем дистрибутива Zenwalk

  • Linux в школе: первые итоги (С. Голубев)

    25 июня

    CITKIT.ru:

  • Zenwalk. Приобщение к Linux (А. Федорчук)

  • Логика и риторика (С.Голубев)

  • Технология Tru64 AdvFS

  • Ханс Райзер предлагает отвести полицейских к телу Нины

    18 июня

  • Проекты по управлению данными в Google (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • ОС и поддержка "железа": мифы и реальность (А. Федорчук)

  • Linux в школе: другие дистрибутивы

  • Пинок (С. Голубев)

    4 июня

  • Ландшафт области управления данными: аналитический обзор (С. Кузнецов)

    CITKIT.ru:

  • Linux в школе: слово заинтересованным лицам

  • SlackBuild: пакеты своими руками

  • Linux от компании Novell. Установка и обзор openSUSE Linux

    Все публикации >>>




  • IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    Информация для рекламодателей PR-акции, размещение рекламы — тел. +7 495 4119920, ICQ 232284597 Пресс-релизы — pr@citcity.ru
    Послать комментарий
    Информация для авторов
    Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
    Copyright © 1997-2000 CIT, © 2001-2007 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...