New frame type containing dictionary

[remittor]

Zstd dictionaries are now completely separate from the main data stream (data file).
And to combine them, the developer must design a custom stream (file) format. And in this case, compatibility with the official zstd utility disappears.

There is absolutely no wish to refuse compatibility with the official zstd utility!

Therefore, there is an idea. It is necessary to add a new frame type to the zstd stream, which will contain the dictionary and its identifier. This frame can be located anywhere in the stream, but always before its use.

If this idea is approved by Yann Collet, then I can start doing pull request.

[felixhandte]

Hi @remittor,

This is an interesting idea. And I would love to make dictionaries easier to use. But I think there are a couple reasons we don't want to go in this direction:

1. Dictionaries are useful as an out-of-band message, but not really in-band. It will pretty much always be the case that sizeof(dict) + sizeof(compress_using_dict(msg, dict)) > sizeof(compress(msg)). That is to say, dictionaries only provide a benefit when they are used across many messages, which is not really supported by embedding them in a message. I guess you could embed a dictionary, and then a bunch of frames that all use the dictionary, all in one stream. (I'm guessing that's your use case?) But you could get similar performance from aggregating all those individual pieces into a single streamed frame.

2. This makes resource management difficult. During decompression, Zstd knows at the beginning of processing a frame exactly how much memory will be required to perform the decompression (driven mostly by the frame's window size). And any previous frames in the stream can be entirely discarded. If dictionaries were embeddable in a stream (making them implicitly available to subsequent frames in the stream), Zstd would have to store each dictionary for the lifetime of the stream, since any future frame could require any of them. This opens the door to resource exhaustion / denial of service issues.

Does that make sense? Can you describe a little more about your use case and why this would be useful?

[remittor]

@felixhandte

That is to say, dictionaries only provide a benefit when they are used across many messages, which is not really supported by embedding them in a message.

So you can embed a dictionary at the beginning of a file (after zero-frame).
A lot of dictionaries may be required when packing different types of data into one file/stream.

I guess you could embed a dictionary, and then a bunch of frames that all use the dictionary, all in one stream. (I'm guessing that's your use case?)

Nope! I want to use dictionaries to better compress metadata in TAR/PAX files. This metadata is very short (usually 512 ... 1536 bytes) and is scattered throughout the file.

But you could get similar performance from aggregating all those individual pieces into a single streamed frame.

Single streamed frame is not recommended when working with multi-file archives! I do not like solid archives!
In my PAXZ project, I pack metadata separately from the payload.
That is, two frames are allocated for each file (metadata and file-content).

Zstd would have to store each dictionary for the lifetime of the stream, since any future frame could require any of them. This opens the door to resource exhaustion / denial of service issues.

This is how I see the solution to this problem:

• Compression:
  • Stream
    A limited number of dictionary identifiers should be used (first for metadata, second for file content).
    Reuse of dictionary identifiers allowed.
  • File
    An unlimited number of dictionary identifiers can be used (you can access any part of the file).
    Reuse of dictionary identifiers allowed.
• Decompression:
  • Stream
    When the dictionary cache is overfull, an error should be thrown.
  • File
    When the dictionary cache is overfull, you should scan the file (from the beginning to the current frame) for the required dictionary.
    The decoder can save a complete list of all the dictionaries encountered with an indication of the offset in the file. This will reduce the size of the cache for dictionaries.

Even in the case of using a single dictionary, I would like to integrate it into a data file. For the user it is very convenient. And to accomplish this task, now you need to design your own file format, which will not be compatible with the official zstd utility.

[Cyan4973]

multi-file archives

I think that's a good use case for dictionary compression.
Indeed, sharing a dictionary between multiple files compressed individually will improve the ratio, while preserving the ability to decompress each file independently, which can be useful.

That being said, why should this be supported by zstd CLI directly ?
Archive is a different layer, with orthogonal responsibilities.
paxz is basically competing with tar on this front.

[remittor]

That being said, why should this be supported by zstd CLI directly ?

All for the sake of user convenience.

Archive is a different layer, with orthogonal responsibilities.

The presence of different types of frames has the potential to combine their seemingly different layers.

I would like the zstd CLI should turn into an analogue of gnutar ... with blackjack and hookers.

In general, I have an even more radical idea. You can train the zstd CLI to recognize TAR headers directly in the stream and pack the metadata and file-content into different frames.
The whole world suffered for decades when unpacking one file from solid tar.gz archives. Zstd CLI can immediately make life easier for users.

[Cyan4973]

It's certainly a good use case.

We could host this new format in the zstd repository if you want.
The closest thing we currently have is the seekable format. (note: it's closer to some kind of random access structure, so it's different from an archive which preserves directory structures and files metadata).
Hence we could create a new sub-directory, like contrib/paxz if you wish.

[remittor]

It's certainly a good use case.

What idea are you talking about? (splitting TAR-stream into frames or dictionaries between frames)

We could host this new format in the zstd repository if you want.

To begin with, I would like to know your vision of the further development of CLI (or zstd-format).

[Cyan4973]

This is a great project.
It aims at replacing tar, by proposing some more flexible extraction capabilities.
There are definitely scenarios where such a capability becomes desirable.
For example, maybe a system backup is saved as a gigantic tar archive, but all that's needed is to restore a small directory inside it. Streaming the entire archive to extract just the relevant part might prove prohibitively expensive over a long distance connexion.

zstd, as a CLI, is expected to remain comparable to gzip. It takes a "stream of bytes", and just compresses that, with no knowledge of the underlying format.
I'm pretty sure that there are a number of scenarios where this approach is not optimal, but it's a simple model, which is easy to combine in a larger pipeline. This is a role that zstd CLI must provide.

Note that there is simply no knowledge of a "file system" anywhere in this description. It's merely a stream of bytes, coming from any source, and pushed to any destination, both of which are controlled "externally", either through CLI commands or through pipes. The CLI may merely be compressing the output of some ls or grep command and send the outcome into an ssh connexion, for example.

This is in stark contrast with paxz intended scenarios. paxz wants to offer the ability to extract one file in the middle of an archive without the need to decompress everything before that point. Note that there are essential concepts which are added in these description, such as file and archive, and do not exist in a pipe scenario.
In such a design, the stream of descriptors and content cannot "just" be compressed by zstd as a generic stream of bytes, this would defeat the purpose. Rather, it's the other way round : paxz uses zstd internally, producing many independent frames, the whole package being possibly encapsulated into its own container format.

That's fine. I believe that paxz is much better when it comes to decompressing a file in an archive. But note that understanding the internal structure of a stream of bytes is a seismic change compared to the simpler "stream of bytes" model zstd fits in.

The most compatible way I can think of to support this scenario is an archive format which is effectively a concatenation of frames, where each file content is a zstd frame, and each file metadata is a separate skippable frame. Additional archive metadata frames might also be necessary, they should also be designed as skippable frames.
In this setup, when the current zstd CLI is requested to decompress the stream of frames, it ignores the content of the skippable frames (the metadata) and just output all content concatenated. So it's "compatible" in the stricter sense or word, meaning it may not provide the expected functionality.

But a more "evolved" decoder could detect the skippable frames, interpret them, determine that the next content must be stored in a file with a specified name, and directory level specified in the metadata, and eventually relative to some sort of "root directory context" which could be provided on command line, and apply some stored properties, such as read-only, execution mode, date of modification, etc.

As one can see, it's a much more complex task, which is not comparable with simpler setups, such as pipes, where "files" and "directories" do not exist.

Hence I suspect it makes more sense to start providing it in a dedicated CLI (which can shipped as part of the zstd repository). At some point, it could be considered useful to integrate it into zstd. But this shouldn't be a "condition" to get the first step. Getting integrated into zstd introduces much higher requirements, such as ensuring that the code is C90 compatible, and that it's highly portable (which can be hard with file systems). A dedicated CLI would not have to support such burden.

A good comparable example here would be pzstd, which started its life as the first multi-threaded implementation of zstd, and is still hosted within contrib/. It is written in C++. It experimented with some new ideas, and used skippable frames to store its own internal format. It was not portable on a nb of platforms, but it wasn't a design goal.
Once the feature proved its worth and was considered desirable inside zstd itself, it was rewritten in C90, and integrated, with a few design changes introduced to remain compatible with the "usual" zstd pipeline. Both version still exist, and are compatible with each other.

[felixhandte]

@remittor,

I agree with the path laid out by @Cyan4973. This kind of functionality should start in a separate tool that can define its own conventions, and we can look at integrating that functionality into the main zstd executable down the road, if it seems appropriate.

As such, I'm going to close this issue for now, but if you want to develop such a tool I think we would be happy to accept it under contrib/.