LZ4¶

LZ4 — это алгоритм сжатия данных без потерь, ориентированный на максимальную скорость сжатия и распаковки. Относится к классу алгоритмов LZ77 (Lempel-Ziv 1977) и обеспечивает компромисс между степенью сжатия и производительностью, что делает его популярным в системах реального времени, базах данных, файловых системах и сетевых протоколах.

¶История

Алгоритм LZ4 был разработан французским инженером Янном Колле (Yann Collet) в 2011 году. Первоначально он создавался как часть библиотеки сжатия для игрового движка, где требовалась высокая скорость обработки данных без значительных задержек. В 2012 году код был опубликован под лицензией BSD, что способствовало его широкому распространению в открытых проектах. В последующие годы алгоритм был интегрирован в ядро Linux (начиная с версии 3.11), файловые системы ZFS и Btrfs, а также в системы управления базами данных, такие как MongoDB и RocksDB. В 2015 году была выпущена спецификация LZ4 Frame Format (RFC 7937), стандартизирующая формат упаковки данных.

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

LZ4 основан на словарном методе сжатия. Алгоритм ищет повторяющиеся последовательности байтов (строки) в потоке данных и заменяет их ссылками на предыдущие вхождения. В отличие от более медленных алгоритмов (например, LZMA или Deflate), LZ4 использует упрощённый механизм поиска совпадений, что снижает вычислительную нагрузку.

¶Этапы сжатия

1. Сканирование входного потока: алгоритм последовательно обрабатывает байты, формируя токены.
2. Поиск совпадений: для каждого нового байта проверяется, встречалась ли такая последовательность в уже обработанных данных (скользящее окно). Размер окна по умолчанию — 64 КБ.
3. Кодирование: если совпадение найдено, записывается токен, содержащий длину совпадения и смещение (offset) относительно текущей позиции. Если совпадения нет, байт копируется без сжатия (литерал).
4. Формирование выходного потока: токены упаковываются в последовательность байтов, образуя сжатый блок.

¶Распаковка

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

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

¶Скорость

LZ4 демонстрирует одну из самых высоких скоростей сжатия и распаковки среди алгоритмов общего назначения. На современных процессорах скорость сжатия может достигать 500–800 МБ/с, а распаковки — 2–4 ГБ/с (в зависимости от типа данных и аппаратного обеспечения). Это достигается за счёт простого формата токенов и минимального количества операций на байт.

¶Степень сжатия

Степень сжатия LZ4 обычно ниже, чем у алгоритмов, ориентированных на максимальное уменьшение объёма (например, gzip или bzip2). Для текстовых данных коэффициент сжатия составляет 2–3:1, для бинарных данных — 1.5–2:1. Для несжимаемых данных (например, уже зашифрованных или случайных) LZ4 может увеличить объём на 0.1–0.5% из-за служебной информации.

¶Использование памяти

LZ4 требует минимального объёма оперативной памяти: для сжатия достаточно нескольких килобайт (для хранения скользящего окна и хеш-таблицы), для распаковки — только буфер для выходных данных. Это делает алгоритм пригодным для встраиваемых систем и микроконтроллеров.

¶Классификация

¶LZ4 (raw)

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

¶LZ4 Frame Format

Стандартизированный формат (RFC 7937), добавляющий заголовок, контрольные суммы и блоки. Обеспечивает совместимость между различными реализациями. Используется в большинстве библиотек и инструментов (например, lz4 CLI).

¶LZ4 HC (High Compression)

Вариант LZ4 с повышенной степенью сжатия за счёт более тщательного поиска совпадений. Скорость сжатия снижается в 5–10 раз, но степень сжатия может быть на 10–20% выше. Распаковка остаётся такой же быстрой, как в обычном LZ4.

¶LZ4 Streaming

Режим, предназначенный для сжатия непрерывных потоков данных (например, сетевых пакетов или логов). Позволяет обрабатывать данные по мере поступления без ожидания завершения всего потока.

¶Применение

¶Файловые системы и хранилища

LZ4 используется в файловых системах ZFS и Btrfs для сжатия данных на лету. В ZFS он является одним из рекомендуемых алгоритмов благодаря низкой задержке. В Btrfs LZ4 применяется по умолчанию для сжатия метаданных и пользовательских данных.

¶Базы данных

Системы управления базами данных, такие как MongoDB, RocksDB и LevelDB, поддерживают LZ4 для сжатия коллекций и журналов транзакций. Это позволяет сократить объём хранимых данных без существенного снижения производительности запросов.

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

LZ4 используется в протоколах передачи данных, где важна низкая задержка. Например, в протоколе HTTP/2 и в системах реального времени (VoIP, видеоконференции). В ядре Linux LZ4 применяется для сжатия сетевых пакетов в модуле zram.

¶Встраиваемые системы

Благодаря малому потреблению памяти и высокой скорости, LZ4 подходит для встраиваемых устройств (IoT, микроконтроллеры). Используется для сжатия прошивок, логов и конфигурационных файлов.

¶Игровая индустрия

LZ4 применяется для сжатия игровых ресурсов (текстур, моделей, звуков) и сохранений. Обеспечивает быструю загрузку уровней и минимальное время ожидания.

¶Реализации

¶Оригинальная библиотека (lz4)

Официальная реализация на языке C, доступная в репозитории GitHub. Включает инструменты командной строки (lz4, lz4cat, unlz4), а также API для интеграции в приложения. Поддерживает все режимы LZ4.

¶Реализации в других языках

Существуют порты LZ4 для Python (библиотека lz4), Java (пакет org.apache.commons.compress.compressors.lz4), Go (пакет github.com/pierrec/lz4), Rust (крейт lz4_flex), JavaScript (модуль lz4js) и других языков. Большинство реализаций совместимы с форматом LZ4 Frame.

¶Интеграция в ядро Linux

LZ4 встроен в ядро Linux начиная с версии 3.11. Используется в модулях сжатия (zram, zswap) и файловых системах (Btrfs, SquashFS). Поддерживается утилитами lz4 и lz4cat из пакета lz4-tools.

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

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

• LZ4 используется в протоколе сжатия данных для космических аппаратов NASA (например, в миссии Mars 2020), где важна надёжность и скорость.
• Алгоритм применяется в сжатии виртуальной памяти (zram) в операционных системах Android и Chrome OS, что позволяет увеличить объём доступной оперативной памяти.
• В 2019 году была выпущена версия LZ4 с поддержкой аппаратного ускорения (LZ4-HC), ориентированная на процессоры с инструкциями AVX-512.

¶Источники

• Yann Collet. LZ4 — Extremely Fast Compression algorithm. Официальный репозиторий и документация.
• RFC 7937 — LZ4 Frame Format.
• Документация ядра Linux: модули сжатия zram и zswap.
• Сравнительный анализ алгоритмов сжатия в системах реального времени (IEEE, 2018).
• Техническая документация MongoDB по сжатию данных.