Меню

Главная
Случайная статья
Настройки
Snappy (библиотека)
Материал из https://ru.wikipedia.org

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.


Сжатый поток: 
000000 51 f0 42 57 69 6b 69 70 65 64 69 61 20 69 73 20  >Q.BWikipedia is <
000010 61 20 66 72 65 65 2c 20 77 65 62 2d 62 61 73 65  >a free, web-base<
000020 64 2c 20 63 6f 6c 6c 61 62 6f 72 61 74 69 76 65  >d, collaborative<
000030 2c 20 6d 75 6c 74 69 6c 69 6e 67 75 61 6c 20 65  >, multilingual e<


Первые 2 байта 0x51 — это длина, выраженная в виде little-endian varint (см. также Protocol Buffers для спецификации varint — записи целого числа переменной длины). В нашем случае с пустым старшим битом равным нулю 0x51 = 81. Значит длина кодируемого сообщения 81 байт. Следующие два байта 0xF042 указывают, что далее следует указание типа 0xF0 = 0b11110000, младшие два бита 0b00, и длины кодируемого блока старшие 6 бит 0b111100, которые указывают, что длина сообщения указывается в единственном следующим за ним байте 0x42 = 66 байт. 
000040 6e 63 79 63 6c 6f 09 3f 1c 70 72 6f 6a 65 63 74  >ncyclo.?.project<
000050 2e


0x09 — это байт тега типа 01 с длиной 4 бита и сдвигом = 0x3F = 6310 или "pedia ";

В примере все повторения подстроки из четырёх и более символов были устранены процессом сжатия. Большинство других библиотек может сжать этот пример лучше. В отличие от классических архиваторов gzip или bzip2, в Snappy не применяется энтропийное кодирование (такое, как код Хаффмана) и символы алфавита не переупаковываются в более компактные битовые последовательности в соответствии с частотой их встречаемости.

Примечания
  1. Release 1.2.2 — 2025.
  2. https://www.theregister.co.uk/2011/03/24/google_open_sources_snappy/
  3. http://www.infoq.com/news/2011/04/Snappy
  4. https://github.com/google/snappy/blob/master/NEWS
  5. README.md # Introduction (англ.). Репозиторий Google на GitHub. Дата обращения: 16 октября 2018. Архивировано 16 октября 2018 года.
  6. Avram, Abel (6 апреля 2011). Google Snappy–A Fast Compressing Library. InfoQ (англ.). Архивировано 4 июля 2018. Дата обращения: 16 октября 2018.
  8. 1 2
  9. 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 года.
  10. ColumnStore Storage Architecture # Compression with Real-time Decompression (англ.). База знаний MariaDB. Дата обращения: 16 октября 2018. Архивировано 16 октября 2017 года.
  11. Storage Engine # CommitLog (англ.). Документация Apache Cassandra. Дата обращения: 16 октября 2018. Архивировано 17 марта 2018 года.
  12. Native Libraries Guide # Components (англ.). Документация Apache Hadoop. Дата обращения: 16 октября 2018. Архивировано 5 апреля 2018 года.
  13. README.md # Features (англ.). Репозиторий Google на GitHub. Дата обращения: 16 октября 2018. Архивировано 18 октября 2017 года.
  14. Glossary — MongoDB Documentation (англ.). Документация MongoDB. Дата обращения: 16 октября 2018. Архивировано 9 сентября 2018 года.
  15. Compression # Configuration (англ.). Репозиторий Facebook на GitHub. Дата обращения: 16 октября 2018. Архивировано 7 июля 2022 года.
  16. format_description.txt (англ.). Репозиторий Google на GitHub. Дата обращения: 16 октября 2018. Архивировано 30 апреля 2017 года.
Downgrade Counter