Zstandard

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Zstandard
Zstandard logo.png
Original author(s) Yann Collet
Developer(s) Yann Collet, Przemysław Skibiński (inikep)
Initial release 23 January 2015 (2015-01-23)
Stable release
1.3.5 / 28 June 2018; 15 days ago (2018-06-28)[1]
Repository Edit this at Wikidata
Written in C
Operating system Cross-platform
Platform Portable
Type Data compression
License Dual: BSD License + GPLv2
Website facebook.github.io/zstd/

Zstandard (or Zstd) is a lossless data compression algorithm developed by Yann Collet at Facebook. The name also refers to the reference implementation in C. Version 1 of the implementation was released as free software on 31 August 2016.[2][3]

Features[edit]

Zstandard was designed to give compression comparable to that of DEFLATE algorithm (developed in 1991, used in original ZIP, gzip and other) with higher compression / decompression speeds. Zstandard combines use of a dictionary-type algorithm (LZ77) with large search window and fast implementations of entropy coding stage, using either very fast Finite State Entropy (tANS) or Huffman coding.[4] A feature of Zstandard implementations is backward direction of reading on entropy decompression.

Zstandard implements several compression levels for additional flexibility from -1 (fastest) to -22 (slowest in compression speed, but best compression ratio). There are also parallel (multi-threaded) implementations of both compression and decompression. Starting from 1.3.2 version from October 2017, Zstandard optionally implements very long range search and deduplication like rzip or lrzip.

According to LTCB compression benchmark compressing a single 1 GB text file, zstd at maximum levels shows compression ratio close to boz, yxz, tornado archivers, better than lza, brotli, or bzip2. With any compression level it has fast decompression.[5] Zstandard reaches the Pareto frontier, which means it decompresses faster than any other algorithm with similar or better compression ratio.[6][7]

Zstandard can use any user-defined pre-populated compression dictionary. It also offers a training mode, able to generate a dictionary from any set of samples. Dictionaries can have a large impact on the compression ratio of small files.[8][9]

Usage[edit]

Zstandard method is supported in Linux Kernel since version 4.14 (released November 2017) for usage as compression method for file systems like btrfs and squashfs.[10][11][12] It was also tested for FreeBSD with integration into OpenZFS file system.[13]

The algorithm is also deployed in datacenters, such as AWS Red Shift , and in databases, such as RocksDB.

Method of Zstandard and MIME type "application/zstd" were submitted to IETF as an Internet draft.[14]

License[edit]

The reference implementation is licensed under the BSD license, published at GitHub.[15] Since version 1.0, it had an additional Grant of Patent Rights.[16]

From version 1.3.1,[17] this patent grant was dropped and the license was changed to a BSD + GPLv2 dual license.[18]

See also[edit]

References[edit]

  1. ^ "Releases - facebook/zstd". Retrieved 1 July 2018 – via GitHub. 
  2. ^ Sergio De Simone, Facebook Open-Sources New Compression Algorithm Outperforming Zlib / InfoQ, 2 September 2016
  3. ^ "Life imitates satire: Facebook touts zlib killer just like Silicon Valley's Pied Piper". The Register. 2016-08-31. Retrieved 2016-09-06. 
  4. ^ https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#entropy-encoding
  5. ^ Matt Mahoney (2016-08-29). "Large Text Compression Benchmark, .2157 zstd". Retrieved 2016-09-01. 
  6. ^ TurboBench: Static/Dynamic web content compression benchmark, PowTurbo 
  7. ^ Matt Mahoney, Silesia Open Source Compression Benchmark 
  8. ^ https://indico.fnal.gov/event/15154/contribution/5/material/slides/0.pdf "Facebook developers report massive speedups and compression ratio improvements when using dictionaries"
  9. ^ https://code.facebook.com/posts/1658392934479273/smaller-and-faster-data-compression-with-zstandard/
  10. ^ https://lwn.net/Articles/733846/
  11. ^ https://kernelnewbies.org/Linux_4.14
  12. ^ https://www.phoronix.com/scan.php?page=news_item&px=Linux-4.14-Zstd-Pull
  13. ^ http://www.open-zfs.org/w/images/b/b3/03-OpenZFS_2017_-_ZStandard_in_ZFS.pdf
  14. ^ Collet, Yann; Kucherawy, Murray S. "Zstandard Compression and The application/zstd Media Type". IETF. Retrieved 2018-07-13. 
  15. ^ "Facebook open sources Zstandard data compression algorithm, aims to replace technology behind Zip". ZDnet. August 31, 2016. Retrieved 2016-09-01. 
  16. ^ zstd/PATENTS "Additional Grant of Patent Rights Version 2", Facebook
  17. ^ "Zstd v1.3.1 release", GitHub
  18. ^ "New license", GitHub

External links[edit]