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 release23 January 2015 (2015-01-23)
Stable release
1.4.4 / 5 November 2019; 34 days ago (2019-11-05)[1]
Repository Edit this at Wikidata
Written inC
Operating systemCross-platform
PlatformPortable
TypeData compression
LicenseDual: BSD License + GPLv2
Websitefacebook.github.io/zstd/

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

Features[edit]

Zstandard was designed to give a compression ratio comparable to that of the DEFLATE algorithm (developed in 1991 and used in the original ZIP and gzip programs), but faster, especially for decompression. It is tunable with compression levels ranging from negative 5 (fastest)[4] to 22 (slowest in compression speed, but best compression ratio).

The zstd package includes parallel (multi-threaded) implementations of both compression and decompression. Starting from version 1.3.2 (October 2017), zstd optionally implements very long range search and deduplication similar to rzip or lrzip.

Compression speed can vary by a factor of 20 or more between the fastest and slowest levels, while decompression is uniformly fast, varying by less than 20% between the fastest and slowest levels.[5]

Zstd at its maximum compression level gives a compression ratio close to lzma, lzham, and ppmx, and performs better than lza, or bzip2.[6][7] Zstandard reaches the current Pareto frontier, as it decompresses faster than any other currently-available algorithm with similar or better compression ratio.[8][9]

Dictionaries can have a large impact on the compression ratio of small files, so Zstandard can use a user-provided compression dictionary. It also offers a training mode, able to generate a dictionary from a set of samples.[10][11] In particular, one dictionary can be loaded to process large sets of files with redundancy between files, but not necessarily within each file, e.g., log files.

Design[edit]

Zstandard combines a dictionary-matching stage (LZ77) with a large search window and a fast entropy coding stage, using both Finite State Entropy (a fast tabled version of ANS, tANS, used for entries in the Sequences section), and Huffman coding (used for entries in the Literals section).[12]

Because of the way that FSE carries over state between symbols, decompression involves processing symbols within the Sequences section of each block in reverse order (from last to first).

Usage[edit]

Zstandard
Filename extension.zst
Internet media typeapplication/zstd[13]
Type of formatData compression

The Linux kernel has included Zstandard since November 2017 (version 4.14) as a compression method for the btrfs and squashfs filesystems.[14][15][16]

As a proof-of-concept, in 2017 Allan Jude successfully integrated Zstandard into the FreeBSD kernel as a compression method for the OpenZFS file system.[5][17]

The AWS Redshift and RocksDB databases include support for field compression using Zstandard.[18]

In 2018 the algorithm was published as RFC 8478, which also defines an associated media type "application/zstd", filename extension "zst", and HTTP content encoding "zstd".[19]

In March 2018, Canonical announced considering[20] to enable zstd as a deb package compression method by default, starting in version 18.10 of the Ubuntu Linux distribution. Compared with xz compression of deb packages, zstd at level 19 decompresses significantly faster, but at the cost of slightly larger package files.[21][22] Arch Linux added support for zstd as a package compression method in October 2019 with the release of the pacman 5.2 package manager.[23]

Full implementation of the algorithm with option to choose the compression level used in the .NSZ / .XCZ[24] file formats, developed by the homebrew-community for the Nintendo Switch[25], a hybrid game console.

License[edit]

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

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

See also[edit]

References[edit]

  1. ^ "Releases - facebook/zstd". Retrieved 5 November 2019 – via GitHub.
  2. ^ Sergio De Simone (2 September 2016). "Facebook Open-Sources New Compression Algorithm Outperforming Zlib". InfoQ. Retrieved 20 April 2019.
  3. ^ "Life imitates satire: Facebook touts zlib killer just like Silicon Valley's Pied Piper". The Register. 31 August 2016. Retrieved 6 September 2016.
  4. ^ https://github.com/facebook/zstd/releases/tag/v1.3.4 Faster compression levels
  5. ^ a b "ZStandard in ZFS" (PDF). open-zfs.org. 2017. Retrieved 20 April 2019.
  6. ^ Matt Mahoney. "Silesia Open Source Compression Benchmark". Retrieved 10 May 2019.
  7. ^ Matt Mahoney (29 August 2016). "Large Text Compression Benchmark, .2157 zstd". Retrieved 1 September 2016.
  8. ^ TurboBench: Static/Dynamic web content compression benchmark, PowTurbo
  9. ^ Matt Mahoney, Silesia Open Source Compression Benchmark
  10. ^ "Facebook developers report massive speedups and compression ratio improvements when using dictionaries" (PDF).
  11. ^ "Smaller and faster data compression with Zstandard". Facebook. 31 August 2016.
  12. ^ "facebook/zstd". GitHub.
  13. ^ Zstandard Compression and the application/zstd Media Type. Tools.ietf.org. doi:10.17487/RFC8478. RFC 8478. Retrieved 13 June 2019.
  14. ^ "The rest of the 4.14 merge window [LWN.net]". lwn.net.
  15. ^ "Linux_4.14 - Linux Kernel Newbies". Kernelnewbies.org. Retrieved 16 August 2018.
  16. ^ "Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook - Phoronix". www.phoronix.com.
  17. ^ (Was Zstandard subsequently accepted into the main FreeBSD kernel source tree?[citation needed])
  18. ^ "Zstandard Encoding - Amazon Redshift". 20 April 2019.
  19. ^ Collet, Yann; Kucherawy, Murray (2018), RFC 8478: Zstandard Compression and the application/zstd Media Type, Internet Engineering Task Force Request for Comments, Menlo Park, CA: IETF Trust
  20. ^ Larabel, Michael (12 March 2018). "Canonical Working On Zstd-Compressed Debian Packages For Ubuntu". phoronix.com. Phoronix Media. Retrieved 29 October 2019. The developers at Canonical are considering a feature freeze exception to get this newly-developed Zstd Apt/Dpkg support in Ubuntu 18.04 LTS. In doing so, they mention they would be looking at enabling Zstd compression for packages by default in Ubuntu 18.10.
  21. ^ "New Ubuntu Installs Could Be Speed Up by 10% with the Zstd Compression Algorithm". Softpedia. 12 March 2018. Retrieved 13 August 2018.
  22. ^ "Canonical Working On Zstd-Compressed Debian Packages For Ubuntu". phoronix. 12 March 2018. Retrieved 13 August 2018.
  23. ^ https://www.phoronix.com/scan.php?page=news_item&px=Arch-Linux-Pacman-Zstd-Near
  24. ^ "RELEASE - nsZip - NSP compressor/decompressor to reduce storage". GBAtemp.net - The Independent Video Game Community. Retrieved 3 November 2019.
  25. ^ Bosshard, Nico (31 October 2019), nsZip is a tool to compress/decompress Nintendo Switch games using the here specified NSZ file format: nicoboss/nsZip, retrieved 3 November 2019
  26. ^ "Facebook open sources Zstandard data compression algorithm, aims to replace technology behind Zip". ZDnet. 31 August 2016. Retrieved 1 September 2016.
  27. ^ zstd/PATENTS "Additional Grant of Patent Rights Version 2", Facebook
  28. ^ "Zstd v1.3.1 release", GitHub "facebook/zstd"
  29. ^ "New license", GitHub "facebook/zstd"

External links[edit]