Zstandard

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 Vorlage:Date.

Features

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) 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.

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

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. 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

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).

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

Vorlage:Infobox file format The Linux kernel has included Zstandard since November 2017 (version 4.14) as a compression method for the btrfs and squashfs filesystems. This version of Linux has been used e.g. in Android since Pie.

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.

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

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".

In March 2018, Canonical announced plans to enable zstd as a deb package compression method by default, starting in version 18.10 of the Ubuntu Linux distribution. Compared with the xz compression previously used for deb packages, zstd at level 19 decompresses significantly faster, but at the cost of slightly larger package files.

License

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

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

See also

• Zlib
• LZFSE – a similar algorithm by Apple used since iOS 9 and OS X 10.11 made open source on Vorlage:Date
• LZ4 (compression algorithm) – a fast member of the LZ77 family

External links

• Vorlage:Official website
• Vorlage:Github
• "Smaller and faster data compression with Zstandard", Yann Collet and Chip Turner, 31 August 2016, Facebook Announcement
• The Guardian is using ZStandard instead of zlib