Image creation reproducibility

[tpwrules]

Suppose I run tar --sort=name cf folder.tar folder && mkdwarfs -i folder -o image.dwarfs --order=path on two different computers at two different times with two different CPU architectures and OSes, but the same version of mkdwarfs, its shared libraries, and command line arguments. If the .tar files on both computers end up bit-identical (meaning file contents and metadata must have been identical, although I haven't verified that tar and mkdwarfs examine identical sets of metadata, but you get the idea), under what circumstances will the .dwarfs images be bit-identical too? Zstd notably guarantees reproducibility of its archives in this manner, even when using different numbers of threads to compress them.

I tried the test above using a folder structure with ~120k files totaling a few gigabytes and failed to reproduce the dwarfs image on the same computer. The mkdwarfs man page explicitly calls out the default order option as non-reproducible, which is why I used --order=path in my test, but clearly there are other factors.

Are creation timestamps embedded in the image? What if the two computers use a different number of threads? I would be willing to trade some creation time in order to perform sorting and guarantee reproducibility, but I'm not sure what engineering work would be involved or what constraints there are in the design.

It would additionally be nice to provide options to guarantee reproducibility even if the input folders are not exactly identical. In my use cases, I typically care about directory structure, file names and contents, and the executable bit, and would like to ignore all other metadata. There are already options to sort by path, remove timestamps and uid/gid values, and so forth, but it would be nice to document which of these are needed for reproducibility or combine them under one flag once the basic image format is reproducible.

[mhx]

Oh, this is super interesting! Thanks for your investigation!

I was actually somewhat optimistic that using --order=path (or even --order=similarity) would produce bit-identical images, but I was wrong. In fact, looking into this I think I even found a bug in one of the libraries used by DwarFS.

So here's where the differences come from:

• There is, as you guessed, a creation timestamp embedded in the image. I've already added an option to disable this.

• While most of the code typically ensures that elements are kept in a deterministic order, the code that assigned inode numbers was iterating a hash table, which by itself guaranteed FIFO semantics, but items were inserted from multiple threads when scanning the input file system. I've now changed the code to add a sorting step before assigning inode numbers. (This shouldn't be much of a performance hit.)

• Last but not least, DwarFS uses the fsst library for string compression and it turned out that the symbol tables generated by the library sometimes differed despite identical input. I believe I found the reason this, and I believe it is a bug. I am, however, not certain if my fix is entirely correct. I hope I'll get an update from the authors.

Once the last issue is fixed, I can release a version that can produce bit-identical images without too much effort.

[mhx]

Actually, as of v0.6.1 mkdwarfs supports creating bit-identical images.

[tpwrules]

I did a quick test with the new 0.7.0 RC1 and this appears to be fixed. I of course had to use --order=path --no-create-timestamp.

[mhx]

Indeed. I'll probably add a section to the manpage to describe how to produce bit-identical images. (--order=similarity should work as well, just not --order=nilsimsa)