Мар
12
2013

Синхронизация файлов на python с использованием rsync алгоритма

Синхронизация файлов на python с использованием rsync алгоритмаНе так давно разбирался с такой dropbox-подобной задачей: вот у нас есть сервер на Python, который предоставляет некий API для работы с файлами, и есть куча клиентов, которые посредством данного API должны: a). грузить файлы на сервер, b). получать от сервера обновленные (другими клиентами) файлы. Причем клиенты естественно ничего не знают друг о друге, т.е. синхронизация данных идет только через сервер, и поверх самой синхронизации навёрнута определенная бизнес-логика (проверка прав доступа и т.п).

Сам серверный API по загрузке/скачиванию файлов проблем не вызывает, но вот не хотелось бы на каждый чих (т.е. малейшее изменение файла) гонять лишний траффик и грузить мегабайты данных. При этом если речь идет о работе с документами, то размер загружаемых/скачиваемых данных действительно исчисляется мегабайтами и конечно же не так велик, но вот если клиент редактирует видео и чуть ли не ежеминутно грузит обновленный файл на сервер, то одними мегабайтами тут так легко не отделаться. В этом случае на помощь приходит алгоритм rsync-а. Если кто не в курсе, что это за механизм, вот вырезка из википедии:

Это такой алгоритм, разработанный австралийским программистом Эндрю Триджеллом, для эффективной передачи структур (например, файлов) по коммуникационным соединениям в том случае, когда принимающий компьютер уже имеет отличающуюся версию этой структуры.

А вот кратенькое описание алгоритма, взятое с citforum-а. Путь у нас есть машина Beta, на которой содержится файл B, и машина Alpha, на которой содержится файл A (более поздняя версия файла B):

  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.

А теперь ближе к практике. На сервере будем придерживаться следующей структуры — для каждого загруженного файла будет храниться целочисленный номер его версии. Для примера, пусть для какого-то абстрактного Word-овского документа example.doc последней версией будет версия под номером 2. И путь есть два клиента — C1 и C2. Оба содержат у себя последнюю версию example.doc с номером 2. Клиент C1 решил изменить у себя файл example.doc. На основании исходного (с версией 2) и изменённого (с версией 3) файла клиент создает файл-дельту example_delta2_c1.doc и загружает его на сервер. Таким образом после загрузки и применения дельты example_delta2_c1.doc на сервере файл example.doc модифицируется и его версия возрастает до 3ки. Пусть аналогичным образом клиент C1 ещё раз модифицирует файл example.doc и поднимет версию файла на сервере до 4ки. А теперь клиент С2, который периодически опрашивает сервер на предмет обновлений, узнает, что файл example.doc изменился. Он отправляет посредством API сигнатуру своего локального файла example.doc версии 2 и в ответ скачивает к себе дельту (сформированную прямо на лету на сервере в рамках запроса) и у себя локально обновляет example.doc до последней 4ой версии. В рамках вышеприведенного примера предполагается, что и клиенты и сервер, при формировании сигнатуры и файлов-дельт используют одну длину разбиения файла на блоки.
Ну а теперь рассмотрим варианты, как можно все вышеперечисленные действия (создание сигнатур, дельт и т.п.) организовать в рамках нашей серверной бизнес логики на Python.

Первый и самый простой вариант — использовать консольную утилиту rdiff, которая по-моему, по умолчанию входит в состав практически всех дистрибутивов linux. Создание сигнатуры исходного файла делается следующим образом:

rdiff signature some-file.doc signature-file

Создания дельты для получения результирующего файла:

rdiff delta signature-file some-file-final.doc delta-file

И, наконец, получение результирующего из исходного с применением дельты:

rdiff patch some-file.doc delta-file some-file-new.doc

В принципе, данный способ не зависит от того, какой скриптовый язык используется на сервере. Конкретно в Python эти вызовы осуществляются через subprocess.call, а в PHP, например, через shell_exec. Минусы данного решения — лишняя зависимость от командной оболочки операционной системы и от сторонней утилиты. Лично мое мнение — обращаться к функциям типа subprocess.call стоит только в том случае, когда нативными средствами языка решить задачи в принципе невозможно (ну либо же очень затруднительно).

Второй способ — использовать реализацию алгоритма rsync, написанную непосредственно на самом Python-е. Как это выглядит — можно посмотреть вот по этой ссылке либо же взять с pypi какую-либо другую реализацию. С одной стороны — довольно просто и компактно, с другой стороны — такая реализация не должна отличаться высокой производительностью, плюс ко всему, например, в самом первом приведенном примере delta-структура представлена обычным python-овским list-ом, и перед её сохранением в файл нужно предварительно использовать сериализацию (например, pickle).

Третий способ — воспользоваться функционалом утилиты резервного инкрементального копирования rdiff-backup, которая, к слову, написана на Python, по умолчанию входит в состав базовых репозиториев для всех дистрибутивов linux, может быть собрана вручную из открытых исходников (ибо open source), а так же для особых извращенцев гурманов имеется windows-версия утилиты. В плане реализации алгоритма rsync есть ещё одна важная киллер-фича — утилита rdiff-backup предоставляет высокоуровневый интерфейс, т.е. грубо говоря python wrapper, для вызова низкоуровневых функций модуля _librsync, который написан на C (привет производительность!). В плане установки — ставится утилита довольно просто. На дистрибутиве Ubuntu это выглядит как-то так (естественно от root-а или из-под sudo):

apt-get install rdiff-backup

На CentOS-е тоже не особо-то сложно:

yum install rdiff-backup

Либо же можно установить через pip (самый true pythonic way):

pip install git+git://github.com/pgodel/rdiff-backup.git

Только в последнем случае нужно быть уверенным, что в системе установлена библиотека librsync, иначе rdiff-backup просто не соберётся. Cам функционал для создания дельт и восстановлениия по ним новых версий файлов выглядит так:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from rdiff_backup import librsync
from rdiff_backup.Rdiff import write_patched_fp
from rdiff_backup.rpath import copyfileobj
 
def create_delta(original_file_path, modified_file_path, delta_file_path):
    basis = open(original_file_path, "rb")
    new = open(modified_file_path, "rb")
    delta = open(delta_file_path, "wb")
 
    sig_obj = librsync.SigFile(basis)
    delta_obj = librsync.DeltaFile(sig_obj, new)
    copyfileobj(delta_obj, delta)
 
    basis.close()
    new.close()
    delta.close()
 
def restore_from_delta(original_file_path, modified_file_path, delta_file_path):
    unpatched = open(original_file_path, 'rb')
    save_to = open(modified_file_path, 'wb')
    delta = open(delta_file_path, 'rb')
 
    write_patched_fp(unpatched, delta, save_to)
 
    unpatched.close()
    save_to.close()
    delta.close()

Думаю, по коду все и так все понятно без особых комментариев. Из трех предложенных вариантов, на мой взгляд, третий — самый оптимальный способ.

Комментарии (2)

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

  • Хорошая и полезная статья. Спасибо за информацию!

Оставить комментарий

CAPTCHA image


Поля, отмеченные * обязательны для заполнения


XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">