Merkle trees and build systems [LWN.net]

Merkle trees and build systems

Posted Jun 7, 2020 12:10 UTC (Sun) by mathstuf (subscriber, #69389)
In reply to: Merkle trees and build systems by Cyberax
Parent article: Merkle trees and build systems

I wonder if anything ever came of this: <https://www.youtube.com/watch?v=bbTxdzbjv7I>. Sorry, I don't have a repo link for it.

to post comments

Merkle trees and build systems

Posted Jun 8, 2020 3:38 UTC (Mon) by pabs (subscriber, #43278) [Link] (3 responses)

This talk reminds me of how modern backup systems like restic and borg store filesystems; similar to git but without the commit hash chain (just independent snapshots) and with an additional layer of splitting files into chunks using rolling hashes.

Sadly the restic storage design misses out splitting directories into chunks of filenames, which means that there is some inefficiency around directories with many files in them.

I wonder when git is going to adopt the file chunking stuff.

Merkle trees and build systems

Posted Jun 8, 2020 4:07 UTC (Mon) by pabs (subscriber, #43278) [Link]

Ah, I see why it seemed familiar, the speaker mentions (31:40) that he stole most of the design for OCIv2 from restic.

Merkle trees and build systems

Posted Jun 8, 2020 12:19 UTC (Mon) by mathstuf (subscriber, #69389) [Link] (1 responses)

Are they always stored as a single object then I assume? I wonder if statistics on how large directory blobs are in a repository could be made. I doubt they tend to approach normal chunk sizes often which means that, statistically, you're unlikely to find a chunk boundary in a directory blob in the first place.

Merkle trees and build systems

Posted Jun 8, 2020 12:30 UTC (Mon) by pabs (subscriber, #43278) [Link]

Some details are in this bug:

https://github.com/restic/restic/issues/2446

Merkle trees and build systems

Posted Jun 8, 2020 3:44 UTC (Mon) by pabs (subscriber, #43278) [Link]

Website and git for the project:

https://umo.ci/ https://github.com/openSUSE/umoci

Merkle trees and build systems

Posted Jun 17, 2020 1:02 UTC (Wed) by cyphar (subscriber, #110703) [Link] (3 responses)

We are currently going through a more formalised specification process to hopefully get a properly specified version of the scheme I outlined in my talk. While the final scheme might not be the same as the one I outlined (which should be unsurprising given I hacked it together pretty last-minute), the general design should be similar. Unfortunately it will certainly be some time before we can point to production users of such a system.

Merkle trees and build systems

Posted Jun 17, 2020 1:54 UTC (Wed) by Cyberax (✭ supporter ✭, #52523) [Link] (1 responses)

All the ideas there are great!

But will Docker (or Moby or whatever they'll be called in a week) implement them?

Merkle trees and build systems

Posted Jun 17, 2020 5:28 UTC (Wed) by cyphar (subscriber, #110703) [Link]

Well, Docker has *finally* implemented OCI image support (which just boiled down to supporting the metadata blobs, since the layer blobs were designed to be identical between the Docker v2.2 image format and the OCIv1 image specification). So it's entirely possible they'll support the extensions we're working on, but I wouldn't hold out hope that it would be a quick transition. containerd and podman/cri-o will probably pick them up faster (though I think podman/cri-o will require more extensive changes to their storage internals since they're based on Docker's graphdriver code).

Merkle trees and build systems

Posted Jun 17, 2020 11:36 UTC (Wed) by pabs (subscriber, #43278) [Link]

This seems kind of similar to ostree, have you considered just using that?