RSync на стероидах с поддержкой Windows

На Хабре периодически рассказывают о новых инструментах для синхронизации данных. Это интересная тема. Такие программы используются:

• для синхронизации файлов на разных устройствах,
• дедупликации,
• резервного копирования,
• сжатия.

Малейшая оптимизация даёт экономию трафика, места, ускоряет синхронизацию и общую производительность любых систем. Всё, везде и сразу. В эпоху веб-приложений и клиент-серверной архитектуры со множеством девайсов, которые работают в единой инфраструктуре, синхронизация — Святой Грааль, одна из базовых технологий в компьютерной области.

Кроме того, инструменты синхронизации интересны с алгоритмической точки зрения. Любопытно, как люди умудряются оптимизировать базовые алгоритмы типа rsync, которые вроде бы работают идеально. Но нет, всегда можно придумать что-то получше.

rsync

Как известно, инструмент для быстрой синхронизации файлов rsync ^[2] разработан австралийским программистом Эндрю Триджеллом по кличке Тридж в 1996 году для его кандидатской диссертации ^[3].

Суть алгоритма заключается в том, что файл разбивается на куски фиксированного размера, для каждого из них вычисляется MD4-хеш и скользящий хеш (rolling hash). Хеши отправляются второму компьютеру для сверки. В упрощённом виде схема выглядит так:

Этот алгоритм и концепция скользящего хеша используются во многих программах для синхронизации файлов, включая rdiff, librsync (Dropbox), sftp, macOS 10.5+, zsync (Ubuntu и другие Linux-дистрибутивы), rclone и др.

В последующие годы для rsync было разработано множество оптимизаций, особенно в части сжатия данных при их передаче.

CDC

Главным улучшением стало изобретение блоков переменного размера, когда границы скользящего окна не смещаются по биту, а устанавливаются в зависимости от содержимого файла. Другими словами, если у нас в битовом потоке попадается одинаковый фрагмент до 64 бит, то рамки скользящего окна сдвигаются на границу этого фрагмента. То есть разбиение на блоки происходит в зависимости от контента. Так появился алгоритм CDC (Content Defined Chunking), который благодаря своей простоте и эффективности стал по-настоящему гениальным изобретением.

Для сравнения, вот схема работы CDC:

CDC решает «проблему сдвига границы», показанную на КДПВ.

А теперь мы переходим к самому интересному…

Помните, был такой игровой сервис Stadia ^[4], который повторил судьбу десятков замечательных проектов компании Google, прибитых на взлёте? Сегодня он встречает похоронной надписью на главной странице:

Проект закрылся 18 января 2023 года…

Главная инновация Stadia состояла в трансляции видео с серверов Google на тонкие клиенты пользователей с минимальной задержкой. Говорят, работало фантастически. И просто удивительно, что Google решила убить такой перспективный проект.

Так или иначе, одной из внутренних технологий Stadia была эффективная синхронизация данных между Windows-серверами (большинство игр работает под Windows) и облачными Linux-инстансами для разработчиков. Сами разработчики Stadia первоначально использовали обычный scp, но он всегда копировал полные файлы без режима копирования «дельты» изменений, и в нём не было быстрого сжатия. Поэтому разработчики Stadia написали внутренние инструменты, которые решают эту проблему.

И после закрытия Stadia они отдали эти инструменты во всеобщее пользование ^[5]!

CDC File Transfer

В репозитории CDC File Transfer ^[5] выложены две утилиты для синхронизации и стриминга файлов между машинами Windows → Windows или Windows → Linux. Это cdc_rsync и cdc_stream, соответственно. Обе используют упомянутый ранее алгоритм Content Defined Chunking (CDC) для максимально эффективного сжатия с учётом контента.

И теперь все желающие могут без проблем использовать эти инструменты для своих личных нужд, ставить на свои серверы и интегрировать в свои проекты. Чем многие не преминули воспользоваться: за несколько месяцев у проекта уже 75 форков и более 2700 звёзд на Github.

▍ cdc_rsync

Если вкратце, cdc_rsync работает примерно так же, как известная линуксовая утилита rsync ^[2]. В большинстве случаев она просто быстро копирует файлы с одной системы на другую, но оптимизирована для ситуаций, когда на целевой системе уже есть старые копии файлов. В этом случае программа быстро проверяет метку времени и размер файла (тогда файл игнорируется с минимальной тратой времени на проверку). Если файл существует, но изменился, то утилита определяет, какие конкретно части файла изменились — и обновляет только их. И во всех случаях используется быстрый алгоритм сжатия данных.

Алгоритм удалённой сверки файлов основан на CDC, а по внутренним тестам Google он работает примерно в 30 раз (!) быстрее, чем rsync. Причины такого ускорения заключаются в значительной оптимизации по сравнению со стандартным алгоритмом rsync ^[6], который при сравнении копий файла использует скользящее окно фиксированного размера.

Эта оптимизация сильно влияет на общее время синхронизации файлов. На следующей диаграмме из репозитория показаны результаты реального тестирования cdc_rsync и линуксового rsync под Cygwin в Windows.

В целом, cdc_rsync синхронизирует файлы примерно в три раза быстрее, чем rsync под Cygwin. В качестве тестовых данных использовались девелоперские билды игры общим размером 40-45 ГБ. На трёх билдах, вероятно, потерялись какие-то файлы, что резко увеличило время синхронизации.

В итоге получается, что алгоритм cdc_rsync гораздо быстрее, чем rsync, и при этом проще. Поскольку границы блоков перемещаются вместе со вставками или удалениями, задача сопоставления локального и удалённого хешей является тривиальной операцией разности множеств. Она больше не включает поиск побайтовой хеш-карты.

▍ cdc_stream

В свою очередь, cdc_stream — это инструмент для потоковой передачи файлов и каталогов с Windows на Linux. Концептуально он похож на sshfs, но оптимизирован для скорости чтения. Утилита не поддерживает запись файлов обратно из Linux в Windows. Каталог Linux доступен только для чтения.

Вот как работает программа:

А ниже сравнительные графики производительности: время запуска игры от начала операции до появления меню на экране. Тестировались разные игры для Stadia, но в целом процесс демонстрирует скорость потоковой передачи любых файлов:

Судя по проведённым тестам, cdc_stream копирует файлы примерно в 2–5 раз быстрее, чем sshfs. Как можно понять из объяснений выше, эта разница обеспечена преимуществом CDC над стандартным алгоритмом rsync ^[6]. Для эффективного диффиринга используется тот же алгоритм на основе CDC, что и в программе cdc_rsync.

Если файл изменился на Windows, то в систему Linux передаются только различия (дельта). Это происходит в момент считывания файла под Linux. Остальное считывается из кэша. Изменения в файлах Windows отражаются в Linux с задержкой от 0,5 с (плюс примерно 0,7 с на каждый гигабайт).

Операции stat выполняются очень быстро, поскольку метаданные (имена файлов, разрешения и т.д.) оптимизированы для потоковой передачи.

Более подробно об использовании инструментов cdc_rsync и cdc_stream и необходимой конфигурацией SSH и SFTP см. в документации ^[5] на Github, а также в документации/комментариях внутри кода ^[7]. В целом, cdc_rsync используется аналогично scp или rsync, с таким же синтаксисом, понимает стандартные виндовые заменители типа * и ?:

cdc_rsync C:pathto*.txt user@linux.device.com:~

Локальная синхронизация с Windows на Windows рекурсивно (-r) с визуальным индикатором прогресса (-v):

cdc_rsync C:pathtoassets* C:pathtodestination -vr

Примечание. Инструменты cdc_rsync и cdc_stream — не единственные, в которых реализован алгоритм разбиения на блоки с учётом контента (CDC). Его использует restic ^[8] и другие продвинутые инструменты для синхронизации и резервного копирования. В последние годы оптимальной реализацией CDC считалась FastCDC ^[9] с поддержкой Gear-based CDC (GC) со скользящими хешами для разного размера окон, что повышает производительность вычислений (с оптимизациями 2020 года ^[10]), есть версии на Rust ^[11], Python ^[12], C ^[13] и др.

Подобные инструменты можно использовать для дедупликации файлов и резервного копирования по дельте. В большом масштабе это высвободит большой объём дискового пространства, сэкономит время и повысит скорость операций.

Разработчики пишут ^[7], что софт сделан на основе FastCDC с учётом конкретной сферы применения: максимально быстрой инкрементальной синхронизации файлов. И кажется, что это наследие Stadia — действительно лучший вариант для синхронизации/стриминга с Windows на Linux.

По крайней мере, крах Stadia принёс какую-то пользу обществу.

Пол-лимона подарков от RUVDS. Отвечай на вопросы и получай призы ^[14]