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

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

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

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

rsync

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

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



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

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

CDC

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

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



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

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

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



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

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

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

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

CDC File Transfer

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

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

▍ cdc_rsync

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


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

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

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

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

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

cdc_rsync C:\path\to\*.txt user@linux.device.com:~

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

cdc_rsync C:\path\to\assets\* C:\path\to\destination -vr

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

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

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

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

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