Merkle trees and build systems [LWN.net]

Merkle trees and build systems

Posted May 28, 2020 14:37 UTC (Thu) by ScienceMan (subscriber, #122508)
Parent article: Merkle trees and build systems

In more detail, dependencies can be represented as graphs, and ultimately as directed acyclic graphs (DAGs). The Spack package manger (https://spack.io) is based on this idea. From the documentation:

"Spack models the dependencies of packages as a directed acyclic graph (DAG). The spack find -d command shows the tree representation of that graph. We can also use the spack graph command to view the entire DAG as a graph.

[Example]

$ spack graph hdf5+hl+mpi ^mpich
o hdf5
|\
| o mpich
| |\
| | |\
| | | |\
| | o | | libxml2
| |/| | |
|/|/| | |
| | |\ \ \
o | | | | | zlib
/ / / / /
| o | | | xz
| / / /
| | o | libpciaccess
| |/| |
|/| | |
| | |\ \
| | o | | util-macros
| | / /
| | | o findutils
| | |/|
| | | |\
| | | | |\
| | | | | |\
| | | o | | | texinfo
| | | | | o | automake
| | | | |/| |
| | | |/| | |
| | | | | |/
| | | | | o autoconf
| | | | |/|
| | | |/|/
| | | o | perl
| | | o | gdbm
| | | o | readline
| | | o | ncurses
| |_|/ /
|/| | |
o | | | pkgconf
/ / /
| o | libtool
| |/
| o m4
| o libsigsegv
|
o libiconv
"

Link:
https://spack-tutorial.readthedocs.io/en/latest/tutorial_...

to post comments

Merkle trees and build systems

Posted May 28, 2020 16:31 UTC (Thu) by nim-nim (subscriber, #34454) [Link] (1 responses)

Yes, any working dependency system will essentially build a DAG then navigate it.

There’s no other reliable way to do things, you need the directed property because in the end the computer will need to compute a sequential execution plan, and you need the acyclic property to avoid looping indefinitely in the middle of this plan.

Component systems that break this (for example, when a parent introduces a dependency on its children by testing them in its unit tests) are nor automate-able. They need someone to construct manually a giant pile of poo (vendor) so the computer does not need to resolve the giant poo dependency graph to recreate it from scratch.

Merkle trees and build systems

Posted Jun 6, 2020 5:03 UTC (Sat) by rgh (guest, #13511) [Link]

a giant pile of poo

To use the technical term!

Merkle trees and build systems

Posted May 29, 2020 8:31 UTC (Fri) by drothlis (guest, #89727) [Link] (3 responses)

All build systems & packaging systems use dependency graphs, I would
imagine. The novel thing in this article is representing each individual
build artifact (be it a single executable, a package, or an entire tree
rootfs) as its own Merkle tree. Each of these trees is representing the
files & directories in a single build artifact, not dependencies between
artifacts. Dependencies are still handled by the underlying build system
(Ninja, in this case).

Merkle trees and build systems

Posted May 30, 2020 13:20 UTC (Sat) by nim-nim (subscriber, #34454) [Link] (2 responses)

It’s not especially innovative, BTW, it’s just using an uncompressed ostree instead of the compressed archive you find in traditional component systems (and then since people have been working on archiving ostrees to transfer them between systems you will ultimately get right back to the starting point).

The result certainly looks convenient but if it was more than an ostree transposition of how things were already done you would not have an apt2ostree in the middle of the article.

Merkle trees and build systems

Posted May 31, 2020 19:53 UTC (Sun) by MrWim (subscriber, #47432) [Link] (1 responses)

This seems like a strange comment to make on an article specifically describing the advantages of making such a transposition.

The only difference between storing source-code in git vs storing it as source tarballs is storage and performance characteristics. But: it's exactly those differences that make git so much more useful than source tarballs. You interact with it and think about it differently once certain operations are cheap.

At the risk of restating things already stated in the article:

Deployment is now incremental and cheap - you only need to transfer the blobs that have changed, not the whole tarball. The effect is you don't need a separate deployment mechanism during dev vs prod.
You can store many many different versions of your built images in a reasonable amount of space - so you just stop worrying about it what to keep and what the deletion policy should be
Your intermediate build steps now share storage with your final rootfses, so you don't need to worry about reducing the number of build steps or intermediate artefacts.
The cost of comparing two trees is now super cheap, so becomes a natural operation to do. Interested in how a particular change has affected your installed image? It's fine we run a diff on the whole tree for every PR. This is particularly useful for changes to the build system itself.
Maybe you're performing some transformation on your tree that only depends on one subdirectory? That's fine: extracting a subdir is cheap and because it's a merkle tree you know if you need to rerun your build steps, because you can find the SHA of the subtree cheaply.
Composing a new tree out of subtrees or partial trees is super cheap, so you do so wherever convenient.

You could implement all of the above with tarballs, but it would be so impractical that you wouldn't. With Merkle trees it's natural. Whether it's innovative or not is irrelevant.

Merkle trees and build systems

Posted Jun 5, 2020 10:03 UTC (Fri) by nim-nim (subscriber, #34454) [Link]

Well, rpm and apt systems implement all this from archives (cpio or or) so it’s perfectly practical and has been done for a long time now. Maybe ostree makes it more practical, maybe not. It’s hard to compare a mature ecosystem that had to solve the 20% of make-it-fully-work problems that take 80% of implementation energy with an ecosystem that implemented the 80% easy part and had not have to deal with the 20% hard part yet (and does not have the warts and scars resulting with this part).

And I strongly suspect that a lot of the parts where you would find existing systems inefficient, are inefficient because rpm and apt systems have to deal with the real world, where code maintenance and ownership is distributed, and you do no have a single dev entity owning the whole codebase that can do whatever it wants at all stages of the build in its own custom (ostree) sets.

From this POW the article (IMHO) mistakes the convenience of a single unified BSD-style build tree with the convenience of ostree itself. Unified build trees *are* definitely more convenient, they just do not scale to the messiness of real life dev organization structures.

Anyway, I did write that the result looked convenient, so no criticism of the ostree implementation on my part, just reacting to people that implied ostree invented hot water.