compress/zstd: add new package

[dsnet]

Zstandard (RFC 8878) is well-positioned to replaced GZIP (RFC 1952) as the de-facto compression format.

Zstandard:

• is faster to compress/decompress than GZIP,
• has much better compression ratios,
• is well-specified,
• is backed by a prominent company, and
• is seeing increased adoption in use with archives and as a browser content encoding.

Given the likely ubiquitous place Zstandard is going have in the future, I propose first-class adoption of Zstandard in the stdlib.

Existing Go implementations:

• @klauspost has an excellent Zstandard implementation at github.com/klauspost/compress/zstd, but the API is a somewhat complex and it makes use of native assembly.
• @ianlancetaylor implemented a Zstandard decompressor in internal/zstd without any use of unsafe or assembly.

Some goals for this package:

• The API be simple and similar to existing packages like compress/gzip.
• It does not use unsafe or assembly similar to the existing compress package.
  • Performance is always nice, but Go community surveys consistently shows security as more important than performance.
  • Users who just need a decently fast enough Zstandard implementation can use compress/zstd, while those want the best performance and/or advanced features of Zstandard can use @klauspost's package. Any stdlib packages (e.g., net/http that make use of compress/zstd should make it possible to swap over to a different zstd implementation).
  • Note that the same is already true of compress/gzip, which is generally good enough (although there is still room for performance optimizations), but power users can use github.com/klauspost/compress/gzip, which is much faster (as it makes use of assembly).

We could:

• adopt @klauspost's pure-Go (i.e., no assembly) implementation with a cleaned-up API
• extend @ianlancetaylor's work to support compressing
• do a combination of both

Related issues:

• proposal: net/http: add support for RFC8878 Content-Encoding: zstd to http.DefaultTransport #62492
• cmd/link: support for zstd-compressed DWARF sections #55107
• cmd/distpack: offer Zstandard-compressed archives in addition to gzip #62446

[dsnet]

Some comments on other popular compression formats and why Zstandard makes the cut, but not others:

• Brotli (RFC 7932) has many of the benefits of Zstandard, but has several detriments:
  • It uses a 120KiB static dictionary, which must be linked into every Go binary that uses brotli. This doesn't suite Go well which always aims for static binaries and avoids shared libraries.
  • The overall design seems geared towards web data, while Zstandard is more general purpose.
  • There is no framing format for Brotli, which makes its use as a standalone file format somewhat limited.
• XZ (or LZMA) has great compression ratios, but is really slow for compression and decompression. There is no specification.
• bzip2 has fairly good compression ratios, but is slow for compression and decompression. There is no specification. While there exists a decompression implementation in the stdlib (i.e., compress/bzip2), I don't believe bzip2 should have made the cut for inclusion into the stdlib.
• snappy is heavily geared towards very high speed compression and decompression, but sacrifices compression ratio. Somewhat of a niche use case.
• lz4 aims for similar goals to snappy.

Most compression formats (other than bzip2) are a combination of LZ77 with entropy encoding (and maybe other tricks like Markov chains for LZMA). The entropy encoding that GZIP uses is Huffman encoding, which can't compress better than 1-bit per byte. In terms of compression ratio, arithmetic encoding (which LZMA uses), range encoding, and ANS (which Zstandard uses) encoding provide better ratios. ANS has the benefit that is overcomes the limitations of Huffman encoding, is patent unencumbered (to my knowledge), and is also very fast. It seems unlikely a better entropy encoding than ANS will be discovered in the next decade.

IMO, the lack of a formal specification should bar inclusion in stdlib as it makes "correctness" somewhat undefined.

[ianlancetaylor]

IMO, the lack of a formal specification should bar inclusion in stdlib as it makes "correctness" somewhat undefined.

Makes sense but I have to say that I'm not sure that anybody could write a correct zstd decompressor based solely on reading RFC 8878.

[dsnet]

I'm not sure that anybody could write a correct zstd decompressor based solely on reading RFC 8878.

Heh... you're the expert there, having done it. I had written a Brotli decompressor solely from the draft RFC without looking at the implementation. This effort led to a number of updates to the draft so that it would be unambiguous when finalized.

[Jorropo]

To add to the list of good points zstd has an extremely really wide range of levels available, depending on the compressor options you can have lz4 or gzip like ratios which have very low resource usage.
Or by turning up a few knobs and or changing a few algorithms in the compressor you can get ratios slightly bellow xz while being transparently compatible with the decompressor (and by using less resources than xz).

[klauspost]

@dsnet Just to clarify some mistakes in your initial post.

zstd compression (nor deflate for that matter) uses any assembly or "unsafe" for compression. The assembly is used for decompression and can be fully disabled with a "noasm" tag. So obviously that is trivial to exclude.

the API is a somewhat complex

Could you elaborate what you find particularly complex?

I expect the stdlib would have the multithreading pulled out and only implement a fully synchronous mode, as well as possibly omitting dictionary features. Without that the API isn't really more complex than flate, gzip and similar. Without concurrency you can have the options on the Encoder (or Writer, whatever it is called), since you don't have any sharing to care about.

security as more important

I could interpret this as an underhanded way of implying my library isn't safe to use. Probably not the intention, but just to be clear there is continuous fuzzing running and there is third party security review being done.

Considering it doesn't use assembly, nor unsafe, I think it is fair to say that a battletested code is more secure than a freshly written code. If you want to write it, I will of course not take that fun from you - but to wrap it in an argument of "security" seems disingenuous or the very least not at all researched to me.

I do think that features like concurrent (de)compression and possibly dictionaries should be taken out from the stdlib. I think having the EncodeAll([]byte) []byte on an encoder is a good may to control allocations - and without concurrency it will be easier to control anyway.

[dsnet]

@klauspost, thanks for your thoughts.

I expect the stdlib would have the multithreading pulled out and only implement a fully synchronous mode, as well as possibly omitting dictionary features

Correct. There should be no usages of goroutines in the stdlib implementation. The example in klauspost/compress#479 should be perfectly thread safe (as it is with the other stdlib packages).

One "dictionary" feature we probably want to keep is the ability to specify the maximum window size.

I could interpret this as an underhanded way of implying my library isn't safe to use. Probably not the intention,

Not at all the intention; I use your package quite extensively myself.

That said, the stdlib avoids the use of assembly except for a few select places. Assembly can be a challenge to review and maintain. Continuous fuzzing is great, but takes a long time before confidence in the implementation is obtained. Fuzzing doesn't help when trying to review if a change to the assembly implementation is correct.

I should also mention the asynchronous nature zstd.NewWriter has actually lended itself to race conditions that could then lead to security problems. To be clear, it's not a race in zstd, but the API design made it easy for users to hold it wrong. In general, library code should be synchronous (from the perspective of the caller) unless the naming or the functionality makes it obvious that it operates in a asynchronous manner.

Considering it doesn't use assembly, nor unsafe, I think it is fair to say that a battletested code is more secure than a freshly written code.

I'm confused. Just above, you mentioned that assembly is used in your package for decompression, but here you saying it doesn't use assembly? Did you mean if you built it under noasm?

If you want to write it, I will of course not take that fun from you - but to wrap it in an argument of "security" seems disingenuous or the very least not at all researched to me.

I'm not itching to write a zstd implementation from scratch. My end goal is to see support for it in stdlib. In my proposal, I deliberately didn't make a statement about how this would come to be fulfilled. Using the pure Go (i.e., no assembly) implementation of your package would be a reasonable possibility.

I think having the EncodeAll([]byte) []byte on an encoder is a good may to control allocations - and without concurrency it will be easier to control anyway.

I personally find it rather strange that the Encoder is either a streaming encoder or essentially a variable to hold encoder settings and shared resources to use with EncodeAll.

Given the acceptance of #54078, I would rather see something like:

func AppendCompress(dst, src []byte, level int) ([]byte, error)
func AppendDecompress(dst, src []byte, maxSize int) ([]byte, error)

[klauspost]

One "dictionary" feature we probably want to keep is the ability to specify the maximum window size.

Yes. That is an essential security DOS mitigation. Though when I refer to dictionaries I only refer to predefined dictionaries that seeds the first blocks with backreferences and predefined entropy coders.

I'm confused. Just above, you mentioned that assembly is used in your package for decompression, but here you saying it doesn't use assembly? Did you mean if you built it under noasm?

I assumed you were only looking for compression given there already is an internal decompressor, which I unfortunately haven't had the time to test. But since everything is marked by tags, taking it out is extremely easy.

I should also mention the asynchronous nature zstd.NewWriter has actually lended itself to race conditions that could then lead to security problems.

I am not sure how you come to that. If you use it for streaming, you can only use it for one stream - that isn't different than a sync Writer. If you want writes to only happen when you are calling Write, yes, you need to disable concurrency - but that is an assumption you are making that doesn't hold. The documentation should be pretty clear on what you can expect. Either way, it is a non-issue since the concurrency should go.

Both the compressor and the decompressor have an "async" and "sync" code path. Ripping out the async one is a minor task. Of course some cleanup can probably be done, but that is cosmetics.

func AppendCompress(dst, src []byte, level int) ([]byte, error)
func AppendDecompress(dst, src []byte, maxSize int) ([]byte, error

So you want each of them to allocate, or try to hide the allocs with internal sync.Pools?

EncodeAll/DecodeAll are basically this (they also append), but it keeps the allocs within the Reader/Writer, and buffers, etc can be allocated with settings for the compression level needed.

Being able to use the same Reader/Writer for concurrent Encode/Decode operations would have to go, but it would at least give control over how each is reused. Sidenote, AppendCompress shouldn't need to return an error.

[dsnet]

So you want each of them to allocate, or try to hide the allocs with internal sync.Pools?

Stack allocate if possible, reusing the destination buffer if possible (e.g., we don't need to maintain the LZ77 window for decompression since it can be obtained from dst itself), and otherwise sync.Pool.

[dsnet]

To comment more on the EncodeAll hung off as methods where the pooling occurs within an Encoder: in a sufficiently large program, I'm observing multiple instances of global Encoder variables in various packages that each use more or less the same settings. It is somewhat silly that across packages, the resources is not shared since resource pooling occurs within an Encoder.

[silverwind]

While zstd is a noble goal, I woul like to highlight that it still has zero support in browsers as of today. So for anyone looking to use a more efficient Content-Encoding for HTTP than gzip, brotli is still the go-to:

• https://caniuse.com/zstd
• https://caniuse.com/brotli