Snappy (библиотека) (Snappy (QnQlnkmytg))
Snappy | |||
---|---|---|---|
Тип | библиотека функций и программа для объединения[вд] | ||
Разработчик | |||
Написана на | C++ | ||
Операционная система | кроссплатформенность | ||
Первый выпуск | 18 марта 2011[2][3] | ||
Последняя версия | |||
Репозиторий | github.com/google/snappy | ||
| |||
| |||
Лицензия | модифицированная лицензия BSD[вд][4] | ||
Сайт | google.github.io/… (англ.) |
Snappy (ранее — Zippy)[5] — библиотека для быстрого сжатия и распаковки данных, написанная на C++ в Google на основе LZ77; открыта в 2011 году[6][7][8]. Основной целью стало достижение высокой скорости сжатия, при этом задач наибольшего сжатия или совместимости с другими библиотеками не ставилось. В 2011 году скорость сжатия на одном ядре Core i7 (2,26 ГГц, 64 бита) достигала 250 МБ/с и 500 МБ/с для распаковки[8], однако при этом коэффициент сжатия[англ.] оказался на 20 — 100 % ниже, чем у gzip[9].
Применяется в проектах Google, например, таких как BigTable, MapReduce и во внутренней системе RPC, используется в столбцовом движке для MariaDB[10], Cassandra[11], форматах файлов для экосистемы Hadoop[12], LevelDB[англ.][13], MongoDB[14], RocksDB[англ.][15]. Является хорошо переносимой, не использует ассемблерные вставки.
Распространяется в виде обёрток над Си и C++; существуют интерфейсы для ряда других языков, в том числе для C#, Лиспа, Erlang, Go, Haskell, Haxe, Java, Lua, Node.js, Perl, PHP, Python, R, Ruby, Rust, Smalltalk.
Формат потока
[править | править код]Кодирование в Snappy — побайтовое, в потоке могут быть только байты. Формат избегает энтропийного кодирования, используя алгоритм Хаффмана или арифметическое кодирование в зависимости от ситуации.
Первый байт в потоке определяет размер несжатых данных, хранится в виде little endian «varint», то есть целое число в коде переменной длины[англ.]. Первые семь бит каждого байта используются для данных, а восьмой бит — флаг конца поля, описывающего этот размер.
Остальные байты потока закодированы в виде одного из четырёх типов элемента. Тип элемента закодирован в первые два бита первого байта (байт тега — tag byte) элемента.[16]
Обозначения: код — ссылка на словарь; сдвиг — сдвиг от текущей позиции назад к уже распакованному потоку; длина — количество байтов кода из словаря.
00
— несжатые данные; последующие 6 битов используются для хранения размера данных; если размер занимает более 60 байтов, будет использован код нефиксированной ширины01
— код, хранящий длину (3 бита) и сдвиг (11 битов); один байт после тега используется для невместившейся части сдвига10
— код, хранящий длину (6 бит) тега и сдвиг в виде двухбайтового числа после тега11
— код, хранящий длину (6 бит) тега и сдвиг в виде четырёхбайтового числа после тега
Размер словаря ограничен байтами ( для версии 1.0).
Пример потока
[править | править код]Оригинальный текст:
Wikipedia is a free, web-based, collaborative, multilingual encyclopedia project.
Сжатый поток:
0000000: ca02 f042 5769 6b69 7065 6469 6120 6973 ...BWikipedia is
Первые 2 байта 0xCA02
— это длина, выраженная в виде little-endian varint (см. также Protocol Buffers для спецификации varint — записи целого числа переменной длины), таким образом, наиболее значимый байт здесь — это 02
. 0x02CA
(вид LE) = 0x014A
= 330 байт. Следующие два байта 0xF042
указывают, что далее будет этот же литерал на позиции 66+1
0000010: 2061 2066 7265 652c 2077 6562 2d62 6173 a free, web-bas 0000020: 6564 2c20 636f 6c6c 6162 6f72 6174 6976 ed, collaborativ 0000030: 652c 206d 756c 7469 6c69 6e67 7561 6c20 e, multilingual 0000040: 656e 6379 636c 6f09 3ff0 1470 726f 6a65 encyclo.?.proje
0x09
— это байт тега типа 01
с длиной 4 бита и сдвигом = 0x3F
= 6310 или "pedia "; 0xf014
— это литерал с длиной 20+1 байт
0000050: 6374 2e00 0000 0000 0000 0000 0000 0000 ct.
В примере все повторения подстроки из четырёх и более символов были устранены процессом сжатия. Большинство других библиотек может сжать этот пример лучше. В отличие от классических архиваторов gzip или bzip2, в Snappy не применяется энтропийное кодирование (такое, как код Хаффмана) и символы алфавита не переупаковываются в более компактные битовые последовательности в соответствии с частотой их встречаемости.
Примечания
[править | править код]- ↑ Release 1.2.1 — 2024.
- ↑ https://www.theregister.co.uk/2011/03/24/google_open_sources_snappy/
- ↑ http://www.infoq.com/news/2011/04/Snappy
- ↑ https://github.com/google/snappy/blob/master/NEWS
- ↑ README.md # Introduction (англ.). Репозиторий Google на GitHub. Дата обращения: 16 октября 2018. Архивировано 16 октября 2018 года.
- ↑ Avram, Abel (2011-04-06). "Google Snappy–A Fast Compressing Library". InfoQ (англ.). Архивировано 4 июля 2018. Дата обращения: 16 октября 2018.
- ↑ Metz, Cade (2011-03-24). "Google open sources MapReduce compression". The Register (англ.). Архивировано 3 июля 2018. Дата обращения: 16 октября 2018.
- ↑ 1 2 Ximen (2011-04-23). "Библиотека для сжатия данных от Google". linux.org.ru. Архивировано 3 июля 2015. Дата обращения: 16 октября 2018.
- ↑ Erdem Agaoglu. LZO vs Snappy vs LZF vs ZLIB, A comparison of compression algorithms for fat cells in HBase (англ.). Блог (14 апреля 2011). Дата обращения: 16 октября 2018. Архивировано 3 июля 2018 года.
- ↑ ColumnStore Storage Architecture # Compression with Real-time Decompression (англ.). База знаний MariaDB. Дата обращения: 16 октября 2018. Архивировано 16 октября 2017 года.
- ↑ Storage Engine # CommitLog (англ.). Документация Apache Cassandra. Дата обращения: 16 октября 2018. Архивировано 17 марта 2018 года.
- ↑ Native Libraries Guide # Components (англ.). Документация Apache Hadoop. Дата обращения: 16 октября 2018. Архивировано 5 апреля 2018 года.
- ↑ README.md # Features (англ.). Репозиторий Google на GitHub. Дата обращения: 16 октября 2018. Архивировано 18 октября 2017 года.
- ↑ Glossary — MongoDB Documentation (англ.). Документация MongoDB. Дата обращения: 16 октября 2018. Архивировано 9 сентября 2018 года.
- ↑ Compression # Configuration (англ.). Репозиторий Facebook на GitHub. Дата обращения: 16 октября 2018. Архивировано 7 июля 2022 года.
- ↑ format_description.txt (англ.). Репозиторий Google на GitHub. Дата обращения: 16 октября 2018. Архивировано 30 апреля 2017 года.