Сжатие Snappy

Сжатие Snappy — это библиотека для быстрого сжатия и распаковки данных, разработанная компанией Google. Относится к классу алгоритмов сжатия без потерь, ориентированных в первую очередь на высокую скорость операций, а не на максимальную степень сжатия. Snappy (ранее известная как Zippy) не предназначена для замены универсальных архиваторов (таких как gzip или bzip2), а используется в системах, где критична пропускная способность ввода-вывода и минимальная задержка, например, в базах данных, распределённых файловых системах и потоковых сервисах.

История

Разработка Snappy началась в 2011 году внутри Google для внутренних нужд. Основной целью было создание алгоритма, который мог бы обрабатывать данные со скоростью, близкой к скорости чтения с диска или передачи по сети, при этом обеспечивая хотя бы минимальное сжатие. Первая публичная версия (1.0.0) была выпущена под лицензией BSD в 2011 году. Исходный код был опубликован на GitHub, что позволило интегрировать Snappy в множество сторонних проектов. В 2013 году алгоритм был переименован из Zippy в Snappy из-за конфликта имён с другим проектом. С тех пор библиотека поддерживается и обновляется, в основном в рамках исправления ошибок и оптимизации под новые архитектуры процессоров.

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

Snappy использует алгоритм сжатия на основе словаря (LZ77), который ищет повторяющиеся последовательности байт в потоке данных и заменяет их ссылками на предыдущие вхождения. В отличие от более сложных алгоритмов (например, LZMA), Snappy не использует энтропийное кодирование (например, Хаффмана или арифметическое кодирование), что значительно упрощает и ускоряет как сжатие, так и распаковку.

Этапы сжатия

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

Распаковка

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

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

Скорость

• Сжатие: Обычно 250–500 МБ/с на одном ядре современного процессора (зависит от архитектуры и типа данных). Для сравнения, gzip (уровень 1) сжимает со скоростью около 50–100 МБ/с.
• Распаковка: 500–1000 МБ/с, что часто превышает скорость чтения с SSD-накопителей или сетевых интерфейсов.

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

• Текстовые данные: Обычно 40–60% от исходного размера (например, английский текст сжимается до 55–60%).
• Бинарные данные: Зависит от структуры. Для случайных данных сжатие может быть минимальным (95–100% от исходного размера).
• Сравнение с gzip: Snappy в среднем сжимает в 1.5–2 раза хуже, чем gzip на максимальном уровне сжатия, но в 5–10 раз быстрее.

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

• Сжатие: Требует около 32 КБ оперативной памяти для хеш-таблицы (настраивается).
• Распаковка: Практически не требует дополнительной памяти (используется только входной и выходной буферы).

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

• Snappy не является потоковым форматом в классическом смысле. Он сжимает блоки данных (обычно до 64 КБ), и каждый блок может быть распакован независимо. Это позволяет обрабатывать данные параллельно и поддерживать произвольный доступ к сжатым данным (при условии хранения индекса блоков).

Применение

Snappy широко используется в проектах, где скорость важнее степени сжатия. Основные области применения:

Базы данных и хранилища

• Apache Cassandra: Использует Snappy для сжатия SSTable-файлов, что снижает нагрузку на диск и ускоряет чтение.
• Apache HBase: Сжатие данных в HFiles для уменьшения объёма хранилища.
• Google Bigtable: Внутреннее использование в распределённой базе данных Google.
• MongoDB: В некоторых конфигурациях для сжатия коллекций (наряду с zlib и zstd).

Файловые системы и протоколы

• Google File System (GFS): Используется для сжатия данных на дисках.
• Apache Hadoop: Встроенная поддержка в формате SequenceFile и MapReduce.
• Apache Parquet: Формат хранения колоночных данных, где Snappy является одним из стандартных кодеков.
• Apache Avro: Формат сериализации данных, поддерживающий сжатие Snappy.

Потоковая обработка и сообщения

• Apache Kafka: Используется для сжатия сообщений в брокерах, что снижает сетевой трафик и нагрузку на диск.
• Apache Spark: Встроенная поддержка для сжатия промежуточных данных и RDD.
• Google Cloud Pub/Sub: Внутреннее сжатие сообщений.

Инструменты и библиотеки

• LevelDB: Внутреннее сжатие для SSTable-файлов.
• RocksDB: Вариант LevelDB от Facebook (продукт Meta, признанной экстремистской и запрещённой в РФ), также использует Snappy.
• Google Protocol Buffers: В некоторых реализациях поддерживается сжатие Snappy для сериализованных данных.

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

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

Критика и ограничения

• Низкая степень сжатия: Для многих приложений, где важна экономия места (например, архивация логов), Snappy неэффективен. В таких случаях предпочтительнее zstd или gzip.
• Отсутствие энтропийного кодирования: Это ограничивает сжатие, особенно на данных с высокой избыточностью (например, повторяющиеся шаблоны).
• Не потоковый формат: Необходимость разбиения на блоки может усложнить реализацию для потоковых данных (например, для сжатия в реальном времени).
• Зависимость от архитектуры: Скорость работы сильно зависит от кэша процессора и размера слова. На старых или мобильных процессорах производительность может быть ниже.

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

• Название «Snappy» (англ. «быстрый, энергичный») отражает основную цель алгоритма — скорость.
• Snappy не поддерживает сжатие с предсказанием (например, по образцу), что делает его менее эффективным для данных с известной структурой (например, числовых массивов).
• Библиотека написана на C++ и имеет привязки для многих языков: Python, Java, Go, Rust, C# и других.
• Внутри Google Snappy используется в таких продуктах, как Google Search, YouTube и Google Maps, для сжатия промежуточных данных.

Источники

• Официальный репозиторий Snappy на GitHub (Google).
• Документация Apache Cassandra, Apache Kafka, Apache Hadoop.
• Сравнительные бенчмарки алгоритмов сжатия (например, от Squash Compression Benchmark).
• Статья «Snappy: A Fast Compressor» в блоге Google Open Source (2011).
• Исходный код и описание формата в файле format_description.txt из репозитория Snappy.