zstd

Zstandard - Fast real-time compression algorithm

Star full 4f7b624809470f25b6493d5a7b30d9b9cb905931146e785d67c86ef0c205a402Star full 4f7b624809470f25b6493d5a7b30d9b9cb905931146e785d67c86ef0c205a402Star full 4f7b624809470f25b6493d5a7b30d9b9cb905931146e785d67c86ef0c205a402Star full 4f7b624809470f25b6493d5a7b30d9b9cb905931146e785d67c86ef0c205a402Star full 4f7b624809470f25b6493d5a7b30d9b9cb905931146e785d67c86ef0c205a402 (1 ratings)
Rated 5.0 out of 5
Subscribe to updates I use zstd


Statistics on zstd

Number of watchers on Github 6574
Number of open issues 23
Average time to close an issue 12 days
Main language C
Average time to merge a PR 1 day
Open pull requests 10+
Closed pull requests 33+
Last commit 5 months ago
Repo Created over 3 years ago
Repo Last Updated 5 months ago
Size 12.9 MB
Homepage http://www.zstd.net
Organization / Authorfacebook
Latest Releasev1.3.3
Contributors25
Page Updated
Do you use zstd? Leave a review!
View open issues (23)
View zstd activity
View on github
Latest Open Source Launches
Trendy new open source projects in your inbox! View examples

Subscribe to our mailing list

Evaluating zstd for your project? Score Explanation
Commits Score (?)
Issues & PR Score (?)
What people are saying about zstd Leave a review
best fast compression algorithm. solid source and support.

Zstandard

Zstandard, or zstd as short version, is a fast lossless compression algorithm, targeting real-time compression scenarios at zlib-level and better compression ratios. It's backed by a very fast entropy stage, provided by Huff0 and FSE library.

The project is provided as an open-source BSD-licensed C library, and a command line utility producing and decoding .zst, .gz, .xz and .lz4 files. Should your project require another programming language, a list of known ports and bindings is provided on Zstandard homepage.

Development branch status : Build Status Build status Build status

Benchmarks

For reference, several fast compression algorithms were tested and compared on a server running Linux Debian (Linux version 4.8.0-1-amd64), with a Core i7-6700K CPU @ 4.0GHz, using lzbench, an open-source in-memory benchmark by @inikep compiled with GCC 6.3.0, on the Silesia compression corpus.

Compressor name Ratio Compression Decompress.
zstd 1.1.3 -1 2.877 430 MB/s 1110 MB/s
zlib 1.2.8 -1 2.743 110 MB/s 400 MB/s
brotli 0.5.2 -0 2.708 400 MB/s 430 MB/s
quicklz 1.5.0 -1 2.238 550 MB/s 710 MB/s
lzo1x 2.09 -1 2.108 650 MB/s 830 MB/s
lz4 1.7.5 2.101 720 MB/s 3600 MB/s
snappy 1.1.3 2.091 500 MB/s 1650 MB/s
lzf 3.6 -1 2.077 400 MB/s 860 MB/s

Zstd can also offer stronger compression ratios at the cost of compression speed. Speed vs Compression trade-off is configurable by small increments. Decompression speed is preserved and remains roughly the same at all settings, a property shared by most LZ compression algorithms, such as zlib or lzma.

The following tests were run on a server running Linux Debian (Linux version 4.8.0-1-amd64) with a Core i7-6700K CPU @ 4.0GHz, using lzbench, an open-source in-memory benchmark by @inikep compiled with GCC 6.3.0, on the Silesia compression corpus.

Compression Speed vs Ratio Decompression Speed
Compression Speed vs Ratio Decompression Speed

A few other algorithms can produce higher compression ratios at slower speeds, falling outside of the graph. For a larger picture including slow modes, click on this link.

The case for Small Data compression

Previous charts provide results applicable to typical file and stream scenarios (several MB). Small data comes with different perspectives.

The smaller the amount of data to compress, the more difficult it is to compress. This problem is common to all compression algorithms, and reason is, compression algorithms learn from past data how to compress future data. But at the beginning of a new data set, there is no past to build upon.

To solve this situation, Zstd offers a training mode, which can be used to tune the algorithm for a selected type of data. Training Zstandard is achieved by providing it with a few samples (one file per sample). The result of this training is stored in a file called dictionary, which must be loaded before compression and decompression. Using this dictionary, the compression ratio achievable on small data improves dramatically.

The following example uses the github-users sample set, created from github public API. It consists of roughly 10K records weighing about 1KB each.

Compression Ratio Compression Speed Decompression Speed
Compression Ratio Compression Speed Decompression Speed

These compression gains are achieved while simultaneously providing faster compression and decompression speeds.

Training works if there is some correlation in a family of small data samples. The more data-specific a dictionary is, the more efficient it is (there is no universal dictionary). Hence, deploying one dictionary per type of data will provide the greatest benefits. Dictionary gains are mostly effective in the first few KB. Then, the compression algorithm will gradually use previously decoded content to better compress the rest of the file.

Dictionary compression How To:

1) Create the dictionary

zstd --train FullPathToTrainingSet/* -o dictionaryName

2) Compress with dictionary

zstd -D dictionaryName FILE

3) Decompress with dictionary

zstd -D dictionaryName --decompress FILE.zst

Build instructions

Makefile

If your system is compatible with standard make (or gmake), invoking make in root directory will generate zstd cli in root directory.

Other available options include:

  • make install : create and install zstd cli, library and man pages
  • make check : create and run zstd, tests its behavior on local platform

cmake

A cmake project generator is provided within build/cmake. It can generate Makefiles or other build scripts to create zstd binary, and libzstd dynamic and static libraries.

Meson

A Meson project is provided within contrib/meson.

Visual Studio (Windows)

Going into build directory, you will find additional possibilities:

  • Projects for Visual Studio 2005, 2008 and 2010.
    • VS2010 project is compatible with VS2012, VS2013, VS2015 and VS2017.
  • Automated build scripts for Visual compiler by @KrzysFR and @HaydnTrigg , in build/VS_scripts, which will build zstd cli and libzstd library without any need to open Visual Studio solution.

Status

Zstandard is currently deployed within Facebook. It is used continuously to compress large amounts of data in multiple formats and use cases. Zstandard is considered safe for production environments.

License

Zstandard is dual-licensed under BSD and GPLv2.

Contributing

The dev branch is the one where all contributions are merged before reaching master. If you plan to propose a patch, please commit into the dev branch, or its own feature branch. Direct commit to master are not permitted. For more information, please read CONTRIBUTING.

zstd open issues Ask a question     (View All Issues)
  • almost 2 years libzstd.so.1.1.2 are the same file
  • almost 2 years Could zstd be compatible with zlib?
  • almost 2 years "make install" creates libraries
  • almost 2 years Random access
  • almost 2 years zstdgrep & zstdless tools
  • almost 2 years We need an nginx binding
  • almost 2 years arm pzstd ThreadPool test segfault
  • almost 2 years Is zstd splitabble in hadoop/spark/etc?
  • almost 2 years pzstd does not compile on CentOS 6 based systems
  • almost 2 years How to compute memory usage?
  • almost 2 years Train on single file
  • almost 2 years pzstd uses significantly more memory
  • almost 2 years usage for mixed files archive
  • almost 2 years zstd doesn't preserve ownership, access, or modification times
  • almost 2 years Arch optimizations?
  • almost 2 years Patents?
  • almost 2 years plans for packaging on different platforms (package manager integration)
  • almost 2 years Content-Encoding and other HTTP Headers
  • almost 2 years Use relative #include paths for easier integration into other build systems
  • almost 2 years ZDICT_trainFromBuffer throws "Error (generic)" on data with all possible byte values
  • about 2 years zstd willing to (try to) compress non-files
  • about 2 years What do the "max" values refer to in the dictionary compression section?
  • about 2 years How to compress streamed items in batches of (roughly) the same (compressed) size?
  • about 2 years Add File Access Functions
  • over 2 years "Error 36 : Decoding error : Corrupted block detected" on OpenVMS
  • over 2 years Idea: adaptive compression
  • over 3 years Zstd library should be compatible with static allocation
zstd open pull requests (View All Pulls)
  • Change type of ZSTD_freeCStream to void
  • Add Tcl bindings
  • [libzstd] Allow users to define custom visibility
  • [RFC][decompress] Support BMI2
  • Updatable compression parameters
  • FIO_addFInfo: Fully initialize output 'total' struct
  • Add the packaging metadata to build the zstd snap
  • Restore setting loadedDictEnd
  • Continuously test selected /contrib projects
  • Use a single buffer in zstdmt
zstd list of languages used
zstd latest release notes
v1.3.3 Zstandard v1.3.3

This is bugfix release, mostly focused on cleaning several detrimental corner cases scenarios. It is nonetheless a recommended upgrade.

Changes Summary

  • perf: improved zstd_opt strategy (levels 16-19)
  • fix : bug #944 : multithreading with shared ditionary and large data, reported by @gsliepen
  • cli : change : -o can be combined with multiple inputs, by @terrelln
  • cli : fix : content size written in header by default
  • cli : fix : improved LZ4 format support, by @felixhandte
  • cli : new : hidden command -b -S, to benchmark multiple files and generate one result per file
  • api : change : when setting pledgedSrcSize, use ZSTD_CONTENTSIZE_UNKNOWN macro value to mean unknown
  • api : fix : support large skippable frames, by @terrelln
  • api : fix : re-using context could result in suboptimal block size in some corner case scenarios
  • api : fix : streaming interface was adding a useless 3-bytes null block to small frames
  • build: fix : compilation under rhel6 and centos6, reported by @pixelb
  • build: added check target
  • build: improved meson support, by @shawnl
v1.3.2 Zstandard v1.3.2 - Long Range Mode

Zstandard Long Range Match Finder

Zstandard has a new long range match finder written by our intern Stella Lau (@stellamplau), which specializes on finding long matches in the distant past. It integrates seamlessly with the regular compressor, and the output can be decompressed just like any other Zstandard compressed data.

The long range match finder adds minimal overhead to the compressor, works with any compression level, and maintains Zstandard's blazingly fast decompression speed. However, since the window size is larger, it requires more memory for compression and decompression.

To go along with the long range match finder, we've increased the maximum window size to 2 GB. The decompressor only accepts window sizes up to 128 MB by default, but zstd -d --memory=2GB will decompress window sizes up to 2 GB.

Example usage

# 128 MB window size
zstd -1 --long file
zstd -d file.zst

# 2 GB window size (window log = 31)
zstd -6 --long=31 file
zstd -d --long=31 file.zst
# OR
zstd -d --memory=2GB file.zst
ZSTD_CCtx *cctx = ZSTD_createCCtx();
ZSTD_CCtx_setParameter(cctx, ZSTD_p_compressionLevel, 19);
ZSTD_CCtx_setParameter(cctx, ZSTD_p_enableLongDistanceMatching, 1); // Sets windowLog=27
ZSTD_CCtx_setParameter(cctx, ZSTD_p_windowLog, 30); // Optionally increase the window log
ZSTD_compress_generic(cctx, &out, &in, ZSTD_e_end);

ZSTD_DCtx *dctx = ZSTD_createDCtx();
ZSTD_DCtx_setMaxWindowSize(dctx, 1 << 30);
ZSTD_decompress_generic(dctx, &out, &in);

Benchmarks

We compared the zstd long range matcher to zstd and lrzip. The benchmarks were run on an AMD Ryzen 1800X (8 cores with 16 threads at 3.6 GHz).

Compressors

  • zstd The regular Zstandard compressor.
  • zstd 128 MB The Zstandard compressor with a 128 MB window size.
  • zstd 2 GB The Zstandard compressor with a 2 GB window size.
  • lrzip xz The lrzip compressor with default options, which uses the xz backend at level 7 with 16 threads.
  • lrzip xz single The lrzip compressor with a single-threaded xz backend at level 7.
  • lrzip zstd The lrzip compressor without a backend, then its output is compressed by zstd (not multithreaded).

Files

  • Linux 4.7 - 4.12 This file consists of the uncompressed tarballs of the six Linux kernel release from 4.7 to 4.12 concatenated together in order. This file is extremely compressible if the compressor can match against the previous versions well.
  • Linux git This file is a tarball of the linux repo, created by git clone https://github.com/torvalds/linux && tar -cf linux-git.tar linux/. This file gets a small benefit from long range matching. This file shows how the long range matcher performs when there isn't too many matches to find.

Results

Both zstd and zstd 128 MB don't have large enough of a window size to compress Linux 4.7 - 4.12 well. zstd 2 GB compresses the fastest, and slightly better than lrzip-zstd. lrzip-xz compresses the best, and at a reasonable speed with multithreading enabled. The place where zstd shines is decompression ease and speed. Since it is just regular Zstandard compressed data, it is decompressed by the highly optimized decompressor.

The Linux git file shows that the long range matcher maintains good compression and decompression speed, even when there are far less long range matches. The decompression speed takes a small hit because it has to look further back to reconstruct the matches.

Compression Ratio vs Speed Decompression Speed
Linux 4.7 - 12 compression ratio vs speed Linux 4.7 - 12 decompression speed
Linux git compression ratio vs speed Linux git decompression speed

Implementation details

The long distance match finder was inspired by great work from Con Kolivas' lrzip, which in turn was inspired by Andrew Tridgell's rzip. Also, let's mention Bulat Ziganshin's srep, which we have not been able to test unfortunately (site down), but the discussions on encode.ru proved great sources of inspiration.

Therefore, many similar mechanisms are adopted, such as using a rolling hash, and filling a hash table divided into buckets of entries.

That being said, we also made different choices, with the goal to favor speed, as can be observed in benchmark. The rolling hash formula is selected for computing efficiency. There is a restrictive insertion policy, which only inserts candidates that respect a mask condition. The insertion policy allows us to skip the hash table in the common case that a match isn't present. Confirmation bits are saved, to only check for matches when there is a strong presumption of success. These and a few more details add up to make zstd's long range matcher a speed-oriented implementation.

The biggest difference though is that the long range matcher is blended into the regular compressor, producing a single valid zstd frame, undistinguishable from normal operation (except obviously for the larger window size). This makes decompression a single pass process, preserving its speed property.

More details are available directly in source code, at lib/compress/zstd_ldm.c.

Future work

This is a first implementation, and it still has a few limitations, that we plan to lift in the future.

The long range matcher doesn't interact well with multithreading. Due to the way zstd multithreading is currently implemented, memory usage will scale with the window size times the number of threads, which is a problem for large window sizes. We plan on supporting multithreaded long range matching with reasonable memory usage in a future version.

Secondly, Zstandard is currently limited to a 2 GB window size because of indexer's design. While this is a significant update compared to previous 128 MB limit, we believe this limitation can be lifted altogether, with some structural changes in the indexer. However, it also means that window size would become really big, with knock-off consequences on memory usage. So, to reduce this load, we will have to consider memory map as a complementary way to reference past content in the uncompressed file.

Detailed list of changes

  • new : long range mode, using --long command, by Stella Lau (@stellamplau)
  • new : ability to generate and decode magicless frames (#591)
  • changed : maximum nb of threads reduced to 200, to avoid address space exhaustion in 32-bits mode
  • fix : multi-threading compression works with custom allocators, by @terrelln
  • fix : a rare compression bug when compression generates very large distances and bunch of other conditions (only possible at --ultra -22)
  • fix : 32-bits build can now decode large offsets (levels 21+)
  • cli : added LZ4 frame support by default, by Felix Handte (@felixhandte)
  • cli : improved --list output
  • cli : new : can split input file for dictionary training, using command -B#
  • cli : new : clean operation artefact on Ctrl-C interruption (#854)
  • cli : fix : do not change /dev/null permissions when using command -t with root access, reported by @mike155 (#851)
  • cli : fix : write file size in header in multiple-files mode
  • api : added macro ZSTD_COMPRESSBOUND() for static allocation
  • api : experimental : new advanced decompression API
  • api : fix : sizeof_CCtx() used to over-estimate
  • build: fix : compilation works with -mbmi (#868)
  • build: fix : no-multithread variant compiles without pool.c dependency, reported by Mitchell Blank Jr (@mitchblank) (#819)
  • build: better compatibility with reproducible builds, by Bernhard M. Wiedemann (@bmwiedemann) (#818)
  • example : added streaming_memory_usage
  • license : changed /examples license to BSD + GPLv2
  • license : fix a few header files to reflect new license (#825)

Warning

bug #944 : v1.3.2 is known to produce corrupted data in the following scenario, requiring all these conditions simultaneously :

  • compression using multi-threading
  • with a dictionary
  • on large enough files (several MB, exact threshold depends on compression level)

Note that dictionary is meant to help compression of small files (a few KB), while multi-threading is only useful for large files, so it's pretty rare to need both at the same time. Nonetheless, if your application happens to trigger this situation, it's recommended to skip v1.3.2 for a newer version. At the time of this warning, the dev branch is known to work properly for the same scenario.

fuzz-corpora Zstandard Fuzz Corpora

Zstandard Fuzz Corpora

Other projects in C