Show HN: Zeekstd – Rust Implementation of the ZSTD Seekable Format

It's not standardized as far as I know.

Thanks! I was also surprised that there are very few tools to work with the seekable format. I could imagine that at least some people have a use-case for it.

Yes, the name is a combination of zstd and seek. Funnily enough, I wanted to name it just zeek first before I knew that it already exists, so I switched to zeekstd. You're not the first person asking me if there is any relation to zeek and I understand how that is misleading. In hindsight the name is a little unfortunate.

Looking at the spec (https://github.com/facebook/zstd/blob/dev/contrib/seekable_f...), I don't see any mention of custom dictionaries like you describe.

The spec does mention:

> While only Checksum_Flag currently exists, there are 7 other bits in this field that can be used for future changes to the format, for example the addition of inline dictionaries.

so I don't think seekable zstd supports these dictionaries just yet.

With multiple inline dictionaries, one could detect when new chunks compress badly with the previous dictionary and train new ones on the fly. Could be useful for compressing formats with headers and mixed data (i.e. game files, which can contain a mix of text + audio + video, or just regular old .tar files I suppose).

The Zstd spec allows a stream to consist of multiple frames, but that alone isn't enough for efficient seeking. You would still need to read every frame header to determine which compressed frame corresponds to a particular byte offset in the uncompressed stream.

"Seekable Zstd" is basically just a multi-frame Zstd stream, with the addition of a "seek table" at the end of the file which contains the compressed and uncompressed sizes of every other frame. The seek table itself is marked as a skippable frame, so that seekable Zstd is backward-compatible with normal Zstd decompressors (the seek table is just treated as metadata and ignored).

https://github.com/facebook/zstd/blob/dev/contrib/seekable_f...

It depends on the frame size you choose. Every frame requires a few bytes of additional metadata, how much exactly depends on other compression settings (e.g. frame checksums, which are 4 byte, are only present if enabled). I just tested with a 1G file and compression level 3. zstd compresses it to 559M, zeekstd with a 2M frame to 565M. If I increase the frame size to 4M, zeekstd yields 562M.

I will add a section to the readme, this is a good question that other people might have too!

It depends on content and compression options. ZSTD has four different compression methods: Raw literals, RLE literals, Compressed literals and Treeless literals. I assume that the last two might suffer the most if content is splitted.

Correct me if I'm wrong, but it doesn't seem like you provide the equivalent of Seekable::decompress in zstd_seekable which decompresses at a specific offset, without having to calculate which frame(s) to decompress.

This is basically the only function I use from zstd_seekable, so it would be nice to have that in zeekstd as well.

For whatever it’s worth, zeekstd seems to come with a CLI tool: https://github.com/rorosen/zeekstd/tree/main/cli

If seeking to frames is good enough for random seeking, this can be done with zeekstd already. The cli sets a custom window log (ZSTD_c_windowLog) on the compression context when creating binary patches[1], I regularly use it with a window size above 1G.

[1] https://github.com/rorosen/zeekstd/blob/main/cli/src/compres...

That sounds like this with inline dictionaries added unless I’ve misunderstood you.

Rsyncable goes further: instead of having fixed size blocks, it makes the block split points deterministically content-dependent. This means that you can edit/insert/delete bytes in the middle of the uncompressed input, and the compressed output will only have a few compressed blocks change.

A seekable Zstd file contains a seek table, which contains the compressed and uncompressed size of all frames. That's enough information to figure out which frame contains your desired offset, and how far into that frame's decompressed data it occurs.

Not sure about zstd, but in xz the blocks (frames in zstd) are stored across the file and linked by offsets into a linked list, so you can just scan over the compressed file very quickly at the start, and in memory build a map of uncompressed virtual offsets to compressed file positions. Here's the code in nbdkit-xz-filter:

https://gitlab.com/nbdkit/nbdkit/-/blob/master/filters/xz/xz...

Zeekstd will just error when the seek table is corrupted. Scanning for frame boundaries should also be possible, though it isn't very efficient. If you don't need the seek table, you can just write it to /dev/null or not write it at all when using the lib.

It's true, using some rather non-obvious trickery: https://github.com/madler/zlib/blob/develop/examples/zran.c

I also wrote a tool to make a randomly modifiable gzipped disk image: https://rwmj.wordpress.com/2022/12/01/creating-a-modifiable-...

Sure, but zstd soundly beats gzip on every single metric except ubiquity, it is just straight up a better compression/decompression strategy.

You can decompress a complete file with "zeekstd d seekable.zst".

Piping a seekable file for decompression via stdin isn't possible unfortunately. Decompression of seekable files requires to read the seek table first (which is usually at the end of the file) and eventually seek to the desired frame position, so zeekstd needs to able to seek the file.

If you want to decompress the complete file, you can use the regular zstd tool: "cat seekable.zst | zstd -d"