Zstd

Zstd (сокращение от Zstandard) — алгоритм сжатия данных без потерь и одноимённая кроссплатформенная библиотека, разработанная компанией Meta (организация признана экстремистской и запрещена в РФ). Zstd предназначен для достижения высокой степени сжатия при высокой скорости работы, сопоставимой с алгоритмами семейства LZ (например, LZ4), но с более эффективным сжатием. Алгоритм поддерживает настройку уровня сжатия от 1 (максимальная скорость) до 22 (максимальное сжатие), а также словарное сжатие и потоковый режим. Zstd широко применяется в системах хранения данных, базах данных, файловых системах, сетевых протоколах и архиваторах.

История

Разработка Zstd началась в 2015 году в компании Facebook (организация признана экстремистской и запрещена в РФ) инженером Янном Колле (Yann Collet), ранее создавшим алгоритм LZ4. Первая публичная версия (v0.1) была выпущена в августе 2015 года. В 2016 году алгоритм был стандартизирован как RFC 8478. В 2018 году вышла версия 1.3.0, в которой была добавлена поддержка многопоточного сжатия и улучшена производительность декомпрессии. В 2021 году Zstd стал частью ядра Linux (версия 5.16) для сжатия файлов подкачки и образов памяти. В 2023 году библиотека была включена в состав многих дистрибутивов Linux, а также в инструменты сжатия данных, такие как zstd (командная строка) и интеграции с архиваторами (например, tar --zstd).

Принцип работы

Основной механизм

Zstd основан на комбинации алгоритмов LZ77 (словарное сжатие с поиском повторяющихся последовательностей) и энтропийного кодирования (конечный автомат с конечным числом состояний — FSE, а также Huffman-кодирование для малых данных). В отличие от классических алгоритмов (gzip, bzip2), Zstd использует динамически подстраиваемое окно поиска (от 1 КБ до 128 МБ) и адаптивное кодирование, что позволяет балансировать между скоростью и степенью сжатия.

Уровни сжатия

Zstd поддерживает 22 уровня сжатия (от 1 до 22). Уровни 1–3 ориентированы на максимальную скорость сжатия, уровни 4–9 — на сбалансированный режим, уровни 10–19 — на высокое сжатие с умеренным замедлением, уровни 20–22 — на максимальное сжатие (значительно медленнее, но с лучшим коэффициентом). Для декомпрессии скорость практически не зависит от уровня сжатия.

Словарное сжатие

Zstd поддерживает предварительно обученные словари (dictionary compression). Словарь — это файл, содержащий статистически значимые последовательности байтов, характерные для определённого типа данных (например, текстовые файлы, JSON, базы данных). При сжатии с использованием словаря алгоритм может эффективно кодировать повторяющиеся шаблоны, что даёт дополнительное сжатие на 10–30% по сравнению с безсловарным режимом.

Потоковый режим

Zstd поддерживает потоковое сжатие и декомпрессию, что позволяет обрабатывать данные произвольного размера без загрузки всего объёма в память. Потоковый режим используется в сетевых протоколах (например, HTTP/2, WebSocket) и в системах реального времени.

Характеристики

Скорость и сжатие

Zstd демонстрирует скорость сжатия и декомпрессии, сопоставимую с LZ4 (один из самых быстрых алгоритмов), но при этом обеспечивает степень сжатия, близкую к gzip (уровень 9) и даже к bzip2 на высоких уровнях. В тестах на стандартных корпусах данных (Silesia, Canterbury) Zstd на уровне 3 сжимает в 2–3 раза медленнее LZ4, но даёт на 30–50% лучшее сжатие. На уровне 19 Zstd может превзойти gzip по степени сжатия на 10–20% при аналогичной или более высокой скорости декомпрессии.

Масштабируемость

Zstd поддерживает многопоточное сжатие (режим --threads), что позволяет эффективно использовать многоядерные процессоры. Декомпрессия по умолчанию однопоточная, но может быть распараллелена на уровне потоков данных.

Совместимость

Zstd имеет открытый исходный код (лицензия BSD-3-Clause) и реализован на языке C. Существуют биндинги для большинства языков программирования (C++, Python, Java, Rust, Go, JavaScript, C#). Алгоритм поддерживается в ядре Linux (с версии 5.16), в файловых системах Btrfs, ZFS, SquashFS, в базах данных MySQL, PostgreSQL, RocksDB, в архиваторах 7-Zip, WinRAR (начиная с версии 6.0), а также в формате контейнеров OCI (Docker).

Применение

Системы хранения данных

Zstd используется для сжатия данных в реальном времени в системах хранения, таких как ZFS (с версии 0.8.0), Btrfs, SquashFS. В ZFS Zstd позволяет добиться степени сжатия, близкой к gzip, при значительно меньшей нагрузке на процессор. В Btrfs Zstd используется по умолчанию для сжатия метаданных и данных.

Базы данных

Zstd применяется для сжатия строк, блоков данных и журналов транзакций в базах данных. MySQL (с версии 8.0.17) поддерживает Zstd для сжатия InnoDB-таблиц. PostgreSQL (с версии 15) использует Zstd для сжатия WAL-журналов и TOAST-данных. RocksDB (база данных от Facebook) использует Zstd как основной алгоритм сжатия для уровней L0–L6.

Сетевые протоколы

Zstd используется в HTTP/2 (через расширение zstd), в WebSocket (для сжатия сообщений), в SSH (протокол zstd), в TLS (через расширение zstd_compress). В протоколе HTTP/3 (QUIC) Zstd может применяться для сжатия заголовков.

Архивация

Zstd поддерживается в архиваторах 7-Zip (формат .tar.zst), WinRAR (формат .zst), а также в утилите tar (ключ --zstd). Формат .zst является самостоятельным контейнером, аналогичным .gz или .bz2. Архиватор zstd (командная строка) поддерживает многопоточное сжатие, словарное сжатие и потоковый режим.

Ядро Linux

С версии 5.16 ядро Linux использует Zstd для сжатия файлов подкачки (swap), образов памяти (zram, zswap) и initramfs. Это позволяет сократить время загрузки и уменьшить использование оперативной памяти.

Сравнение с другими алгоритмами

Примечание: данные приведены для типовых текстовых и бинарных файлов на процессоре x86-64. Реальные показатели зависят от типа данных и настроек.

Интересные факты

• Название «Zstandard» было выбрано как отсылка к «стандартному» алгоритму сжатия, который должен заменить устаревшие gzip и bzip2.
• Zstd поддерживает «ультра»-уровни сжатия (20–22), которые используют очень большие окна поиска (до 128 МБ) и могут занимать несколько минут на сжатие одного гигабайта данных.
• В 2020 году Zstd был включён в состав стандарта POSIX (IEEE 1003.1) как рекомендуемый алгоритм сжатия для архивов.
• Алгоритм используется в формате изображений JPEG XL (для сжатия метаданных) и в формате видео AV1 (для сжатия заголовков).
• Zstd поддерживает «тренировку» словарей на произвольных наборах данных — это позволяет добиться дополнительного сжатия на 10–30% для специфических типов файлов (например, логов, JSON, XML).

Критика

Основные критические замечания в адрес Zstd связаны с его происхождением от компании Meta (организация признана экстремистской и запрещена в РФ). Некоторые разработчики выражали опасения по поводу возможного включения в алгоритм скрытых функций (backdoors), однако код Zstd является полностью открытым и многократно проверен сообществом. Другая критика касается отсутствия встроенной поддержки сжатия с потерями (lossy compression), что ограничивает применение в мультимедиа. Кроме того, на высоких уровнях сжатия (20–22) Zstd может потреблять значительное количество оперативной памяти (до 1 ГБ для окна 128 МБ), что делает его непригодным для встраиваемых систем.

Источники

• RFC 8478: Zstandard Compression and the 'application/zstd' Media Type (2018)
• Yann Collet, «Zstandard: A Fast and Efficient Compression Algorithm», 2015
• Документация Zstd (https://github.com/facebook/zstd)
• Сравнение алгоритмов сжатия: Silesia Corpus, Canterbury Corpus
• Ядро Linux: документация по сжатию swap и zram (Linux 5.16)