Алгоритм LZ4

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

История

Алгоритм LZ4 был разработан французским программистом Янном Колле (Yann Collet) в 2011 году. Первоначально он создавался как часть проекта по сжатию файлов для операционной системы FreeBSD, но быстро приобрёл самостоятельное значение. В 2013 году Колле выпустил эталонную реализацию на языке C под лицензией BSD, что способствовало широкому распространению алгоритма. В последующие годы LZ4 был включён в состав ядра Linux (начиная с версии 3.11), а также в библиотеки сжатия для многих языков программирования (C++, Python, Java, Go и др.). В 2015 году алгоритм был стандартизирован в RFC 7937 (LZ4 Frame Format).

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

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

Формат сжатых данных

Сжатый поток LZ4 состоит из последовательности элементов (токенов). Каждый токен может содержать:

• Литерал — последовательность байтов, не найденная в словаре. Кодируется непосредственно.
• Ссылка на совпадение — пара чисел: длина совпадения (match length) и смещение (offset) назад от текущей позиции.

Смещение кодируется как 16-битное значение (от 0 до 65535), что ограничивает максимальный размер окна поиска до 64 КБ. Длина совпадения может быть переменной: от 4 байтов (минимальная длина) до 255 байтов (с возможностью расширения с помощью дополнительного байта). Литералы также кодируются с переменной длиной.

Процесс сжатия

1. Инициализация: Устанавливается скользящее окно размером 64 КБ. Текущая позиция — начало входных данных.
2. Поиск совпадения: Для текущей позиции алгоритм ищет в окне (словаре) самую длинную последовательность, совпадающую с данными, начиная с текущей позиции. Поиск обычно осуществляется с помощью хеш-таблицы, что обеспечивает высокую скорость.
3. Кодирование: Если найдено совпадение длиной не менее 4 байтов, оно кодируется как ссылка (длина, смещение). Если совпадение не найдено или его длина меньше 4 байтов, текущий байт кодируется как литерал.
4. Продвижение: Текущая позиция смещается вперёд на длину закодированного фрагмента (литерала или совпадения). Словарь обновляется.
5. Повторение: Шаги 2–4 повторяются до конца входных данных.

Процесс распаковки

Распаковка LZ4 является симметричной и ещё более быстрой, чем сжатие. Она выполняется в один проход: считывается токен, если это литерал — он копируется в выходной буфер; если это ссылка — алгоритм копирует последовательность байтов из уже распакованной части выходного буфера (с учётом смещения и длины). Благодаря отсутствию сложных вычислений и обратных ссылок, распаковка может достигать скорости в несколько гигабайт в секунду на современных процессорах.

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

Скорость

LZ4 является одним из самых быстрых алгоритмов сжатия общего назначения. Скорость сжатия на современных процессорах может превышать 1 ГБ/с, а скорость распаковки — 5–10 ГБ/с. Это достигается за счёт простой логики, использования хеш-таблиц и минимального количества операций на байт.

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

Степень сжатия LZ4, как правило, ниже, чем у более медленных алгоритмов (например, gzip, zstd, bzip2). В среднем LZ4 сжимает текстовые данные в 2–3 раза, бинарные данные — в 1.5–2 раза. Для несжимаемых данных (например, уже зашифрованных или сжатых) коэффициент сжатия близок к 1 (то есть размер практически не уменьшается). Существует вариант LZ4 HC (High Compression), который обеспечивает более высокую степень сжатия за счёт более тщательного поиска совпадений, но при этом значительно медленнее.

Потребление памяти

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

Применение

LZ4 нашёл широкое применение в различных областях, где требуется быстрая обработка данных:

• Файловые системы: В Linux LZ4 используется для сжатия в файловых системах Btrfs и ZFS (с опцией compress=lz4). Позволяет экономить место на диске без существенного снижения производительности ввода-вывода.
• Базы данных: В системах управления базами данных, таких как MySQL, PostgreSQL, MongoDB, RocksDB, LZ4 применяется для сжатия таблиц, индексов и журналов транзакций. Это снижает объём хранимых данных и ускоряет операции чтения/записи.
• Сетевые протоколы: LZ4 используется в протоколах передачи данных, где важна низкая задержка, например, в Apache Kafka, Redis, HTTP/2 (через библиотеку lz4).
• Сжатие оперативной памяти: В некоторых операционных системах (например, в ядре Linux с модулем zswap) LZ4 применяется для сжатия страниц памяти, что позволяет увеличить эффективный объём RAM.
• Архивация: LZ4 может использоваться как самостоятельный архиватор (утилита lz4), а также как один из алгоритмов в форматах .tar.lz4 и .lz4.
• Игровая индустрия: В движках видеоигр (например, Unity, Unreal Engine) LZ4 применяется для сжатия игровых ассетов (текстур, моделей, звуков) для ускорения загрузки уровней.

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

• Алгоритм LZ4 является одним из немногих алгоритмов сжатия, который может быть реализован аппаратно на FPGA или ASIC, что позволяет достигать ещё более высоких скоростей.
• В 2016 году Янн Колле выпустил алгоритм Zstandard (zstd), который является развитием идей LZ4 и предлагает более гибкий компромисс между скоростью и степенью сжатия.
• LZ4 используется в ядре Linux для сжатия образов initramfs, что ускоряет загрузку системы.
• Алгоритм LZ4 не защищён патентами, что способствует его свободному использованию в коммерческих и открытых проектах.

Источники

• Yann Collet. LZ4 — Extremely Fast Compression algorithm. GitHub repository.
• RFC 7937: LZ4 Frame Format.
• Документация ядра Linux: Documentation/block/bfq-iosched.txt, Documentation/filesystems/btrfs.txt.
• Документация файловой системы ZFS: zfs.opensolaris.org.
• Стандарт сжатия в Apache Kafka: Kafka Documentation — Compression.