maxpack: межфайловая дедупликация на версионных данных

Представьте: у вас 100 файлов, 90% содержимого повторяется между ними. Вы пакуете их через tar | zstd. Получаете сжатие порядка 3.1x. А могли бы получить 10.0x.

Проблема в том, что обычная упаковка не знает, что файлы похожи. tar склеивает их в линейный поток и отдаёт компрессору. zstd работает в пределах окна и плохо сопоставляет одинаковые куски, если они разнесены по потоку на десятки мегабайт.

Идея maxpack в том, чтобы смотреть на набор файлов как на одно пространство данных и схлопывать повторы между файлами и версиями. Внутрь алгоритма сейчас не лезем, лучше посмотрим на цифры: на 100.1 МБ Node.js каждый новый мегабайт входа добавляет 26% нового содержимого, а на 10 ГБ — уже только 0.6%. Итоговая степень сжатия доходит до 50.1x. То есть на таких данных выигрыш растёт вместе с объёмом, а не упирается в потолок.

Где это полезно

• Несколько версий одного проекта. Несколько git-тегов часто содержат много одинакового кода. Обычная упаковка проходит по каждой версии почти заново, а межфайловая дедупликация позволяет сохранить общие куски один раз.

• Логи, дампы БД, CI-артефакты. Соседние выгрузки обычно отличаются на считанные проценты. Если архивировать их вместе, основная масса данных уже была увидена раньше.

• Снапшоты блокчейн-нод. База состояния растёт, но соседние снапшоты часто сильно пересекаются по содержимому. В таком случае архив растёт в основном за счёт нового и изменившегося контента.

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

• VM-снапшоты и контейнерные образы. Когда набор состоит из близких состояний одной системы, между ними обычно остаётся большой общий слой данных.

• Фронтенд-сборки и статика. Хеши в именах файлов меняются, но большие фрагменты содержимого могут оставаться теми же. Если смотреть не на имена, а на байты, часть повторов можно вернуть.

Коротко: чем больше пересечение содержимого между файлами, тем интереснее становится такая схема.

Бенчмарки

Apple M4, один прогон, тёплый кэш. Это не single-core замеры: headline-прогоны CPython и Go для maxpack шли с MAXPACK_THREADS=4. Наборы Diverse, Similar и High-dedup здесь нужны затем, чтобы контролировать долю повторов. Это не случайно сгенерированные байты, а специально собранные тестовые наборы с понятной структурой.

Масштабирование: 100 МБ → 10 ГБ (Node.js v20)

Один проект (Node.js v20), постепенно добавляем теги. На 100.1 МБ все три метода дают ~3.9x. На 10 ГБ maxpack доходит до 50.1x, а tar+zstd и 7z остаются на ~4.8x и ~8.6x. С ростом данных доля уникального содержимого падает, и maxpack это использует.

Реальные проекты: CPython 3.12 и Go 1.23

А теперь уже не контролируемые наборы, а обычные исходники: 8 релизных тегов CPython 3.12 (v3.12.6 — v3.12.13), 817.3 МБ исходников. И 8 тегов Go 1.23, 974.8 МБ.

CPython 3.12

На этом наборе maxpack даёт архив в 7 раз меньше, чем tar+zstd -3, а по времени упаковки и распаковки тоже оказывается впереди.

Go 1.23

Здесь картина похожая: по размеру архива maxpack оказывается в 2.3 раза меньше 7z, а по CPU на упаковке заметно дешевле.

Несколько реальных versioned-проектов сразу

На fd, lsd и bat картина повторяется: чем больше версий и чем выше пересечение между ними, тем сильнее эффект. По размеру архива здесь выигрыш от 41.6% до 70.3% относительно обычной упаковки, а дедупликация доходит до 81.3%.

Степень сжатия на контролируемых наборах

Главная строка здесь — High-dedup. 100 файлов, из которых 90% содержимого совпадает: tar+zstd даёт 3.1x, maxpack — 10.0x. Архив получается в 3.2 раза меньше.

На наборах без выраженного межфайлового повтора виден паритет или небольшой overhead. Главный выигрыш начинается там, где есть повторяющееся содержимое между версиями и файлами.

Скорость

Распаковка здесь стабильно быстрее: от 1.5x до 2.2x. По упаковке картина зависит от структуры данных. На Big (60 МБ, мало дупликатов) maxpack уже тратит время на анализ содержимого, который не успевает окупиться.

Итоговая оценка

Если свести всё в одну фразу, она такая: чем больше повторов между файлами, тем больше выигрыш. Если повторов почти нет, чудес не происходит.

Где подход не окупается

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

• Если набор маленький, служебные расходы и анализ содержимого могут съесть выигрыш.

• Если нужен очень частый мелкий random access по байтам, такой формат удобен меньше, чем специализированное хранилище.

То есть это не «лучший упаковщик вообще для всего подряд», а инструмент под конкретный класс задач: версии, снапшоты и любые наборы с сильным пересечением содержимого.

Где это находится относительно других инструментов

По смыслу maxpack находится где-то между обычной упаковкой файлов и snapshot-системами вроде borg/restic:

Обычные инструменты упаковки хорошо жмут поток, но не видят повторы между файлами. Snapshot-системы видят повторы, но обычно работают chunk-by-chunk и не ориентированы на один переносимый архив. maxpack — это попытка взять свойства обоих подходов в одном формате.

Как повторить у себя

Если хочется проверить идею на своих данных, достаточно сравнить две команды:

maxpack pack your_data/ -o test.maxpack
tar cf - your_data/ | zstd -3 > test.tar.zst
ls -lh test.maxpack test.tar.zst

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

Публичный репозиторий с бинарными релизами и коротким smoke-скриптом (в процессе еще fuse, ffi уже есть): github.com/MaxPer2005/maxpack