Snappy (compression)

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Daniel (talk | contribs) at 22:54, 10 December 2023 (Removing link(s) Wikipedia:Articles for deletion/Spark (software) closed as delete (XFDcloser)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Not to be confused with Snappii.
Original author(s)Jeff Dean, Sanjay Ghemawat, Steinar H. Gunderson
Developer(s)Google
Initial releaseMarch 18, 2011 (2011-03-18)
Stable release
1.1.10 / March 9, 2023; 14 months ago (2023-03-09)[1]
Repository
Written inC++
Operating systemCross-platform
PlatformPortable
Size2 MB
Typedata compression
LicenseApache 2 (up to 1.0.1)/New BSD
Websitegoogle.github.io/snappy/

Snappy (previously known as Zippy) is a fast data compression and decompression library written in C++ by Google based on ideas from LZ77 and open-sourced in 2011.[2][3] It does not aim for maximum compression, or compatibility with any other compression library; instead, it aims for very high speeds and reasonable compression. Compression speed is 250 MB/s and decompression speed is 500 MB/s using a single core of a circa 2011 "Westmere" 2.26 GHz Core i7 processor running in 64-bit mode. The compression ratio is 20–100% lower than gzip.[4]

Snappy is widely used in Google projects like Bigtable, MapReduce and in compressing data for Google's internal RPC systems. It can be used in open-source projects like MariaDB ColumnStore,[5] Cassandra, Couchbase, Hadoop, LevelDB, MongoDB, RocksDB, Lucene, Spark, and InfluxDB.[6] Decompression is tested to detect any errors in the compressed stream. Snappy does not use inline assembler (except some optimizations[7]) and is portable.

Stream format

Snappy encoding is not bit-oriented, but byte-oriented (only whole bytes are emitted or consumed from a stream). The format uses no entropy encoder, like Huffman coding or arithmetic coding.

The first bytes of the stream are the length of uncompressed data, stored as a little-endian varint,[8] which allows for use of a variable-length code. The lower seven bits of each byte are used for data and the high bit is a flag to indicate the end of the length field.

The remaining bytes in the stream are encoded using one of four element types. The element type is encoded in the lower two bits of the first byte (tag byte) of the element:[9]

  • 00 – Literal – uncompressed data; upper 6 bits are used to store length (len-1) of data. Lengths larger than 60 are stored in a 1-4 byte integer indicated by a 6 bit length of 60 (1 byte) to 63 (4 bytes).
  • 01 – Copy with length stored as 3 bits and offset stored as 11 bits; one byte after tag byte is used for part of offset;
  • 10 – Copy with length stored as 6 bits of tag byte and offset stored as two-byte integer after the tag byte;
  • 11 – Copy with length stored as 6 bits of tag byte and offset stored as four-byte little-endian integer after the tag byte;

The copy refers to the dictionary (just-decompressed data). The offset is the shift from the current position back to the already decompressed stream. The length is the number of bytes to copy from the dictionary. The size of the dictionary was limited by the 1.0 Snappy compressor to 32,768 bytes, and updated to 65,536 in version 1.1.

The complete official description of the snappy format can be found in the google GitHub repository.[10]

Example of a compressed stream

The text

Wikipedia is a free, web-based, collaborative, multilingual encyclopedia project.

may be compressed to this, shown as hex data with explanations: 

0000000: ca02 f042 5769 6b69 7065 6469 6120 6973  ...BWikipedia is

The first 2 bytes, ca02 are the length, as a little-endian varint (see Protocol Buffers for the varint specification).[8] Thus the most-significant byte is '02' . 0x02ca(varint) = 0x014a = 330 bytes. The next two bytes, 0xf042, indicate that a literal of 66+1 bytes follows 

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 is tag-byte of type 01 with length - 4 = 0102 = 210 and offset = 0x03f = 63 or "pedia ";
0xf014 is a literal with length of 20+1 bytes 

0000050: 6374 2e00 0000 0000 0000 0000 0000 0000  ct.

In this example, all common substrings with four or more characters were eliminated by the compression process. More common compressors can compress this better. Unlike compression methods such as gzip and bzip2, there is no entropy encoding used to pack alphabet into the bit stream.

Interfaces

Snappy distributions include C++ and C bindings. Third party-provided bindings and ports include[11] C#, Common Lisp, Crystal (programming language), Erlang, Go, Haskell, Lua, Java, Nim, Node.js, Perl, PHP, Python, R, Ruby, Rust, Smalltalk, and OpenCL.[12][13]

See also

References

  1. ^ "Releases - google/snappy". Retrieved 4 October 2023 – via GitHub.
  2. ^ "Google Snappy–A Fast Compressing Library". InfoQ. Retrieved August 1, 2011.
  3. ^ Google open sources MapReduce compression. In the name of speed // The Register, 2011-03-24
  4. ^ "Snappy: A fast compressor/decompressor: Readme". Google Code. Archived from the original on September 8, 2015. Retrieved August 1, 2011."Snappy vs lzo vs zlib".
  5. ^ "ColumnStore Storage Architecture". MariaDB KnowledgeBase.
  6. ^ snappy. A fast compressor/decompressor - Project page at Google Code
  7. ^ "Add a loop alignment directive to work around a performance regression. · google/snappy@824e671". GitHub.
  8. ^ a b "Encoding | Protocol Buffers". Google Developers.
  9. ^ "GitHub - google/snappy: A fast compressor/decompressor". November 11, 2019 – via GitHub.
  10. ^ "Introduction". GitHub. 26 October 2021.
  11. ^ "snappy". snappy.
  12. ^ "Xilinx". Xilinx.
  13. ^ "InAccel". InAccel.

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Snappy_(compression)&oldid=1189289227"