I'll take a shot. If I understand it correctly, basically components have dependencies. For example, A depends on B and B depends on C, etc. If you have A depends on B... and somehow along the path you have a cycle, eg. E depends on A, you have a problem because in order to install A, you need to install B, C,... E. But in order to install E you need to install A first. So you have to break the dependency cycle.
On top of what somerandomone said (which is already correct) imagine you have source packages A, B, C and D which depend on each other through the binary packages they build and the binary packages they build depend on like this: A->B->C->D->A
This would then form a simple cycle where a dependency has to be broken to make it acyclic. A strongly connected component now is a graph where every vertex is in the cycle with every other vertex in the graph.
So for example if we add a package E to the above simple cycle where B depends on E and E depends on D, then we would not have a simple cycle anymore. Now imagine scaling this up to a couple of hundred vertices and you see how this quickly becomes a hideous mess.
I once tried to visualize such a strongly connected component and it looks like this:
I don't know how big the strongly connected component has to become so that you might call bootstrapping Debian "nearly impossible" but last year there were just two new Debian ports: arm64 and ppc64el. So apparently it is still within human reach to build Debian as a whole from scratch. I think what the graph shows is just that it's getting harder and that we need automateable tools to do the whole thing for us. This is what the new "build profile" syntax is for that was introduced with Jessie.
This is interesting but not exactly surprising data. Of course as the distro has the core components have been linked to more often. I'm not sure what the purported utility of this is.
The purpose is, to have a somehow quantifiable measure how hard it becomes to bootstrap Debian. Because the larger the central strongly connected component, the more software is involved in the bootstrap process and has to either be cross compiled or compiled with fewer build dependencies to break cycles.
Ultimately I thought this graph to support the introduction of build profiles into Debian (now so happened with the Jessie release) as well as to promote that a tool like "botch" (you can `apt-get install` it) is necessary to automatically make this graph acyclic for you instead of doing this through year long manual work.
The larger that component is, the more work is needed to make it acyclic (to derive a linear build order). Ideally this "work" is done automatically but for that, more meta data has to be added. In Debian, source package dependencies can be annotated with "build profiles" to mark dependencies which are optional and can thus be used to break cycles. But more source packages need this information. The graph is supposed to be a visualization to convince people that it becomes increasingly hard to break cycles manually and that an automated way (using build profiles) is needed.
I arrived at similar data from another perspective: it's really hard to generate a truly minimal Debian (or Ubuntu) Docker base-image. Everything in the "Essential" package set needs everything else in "Essential" in weird cyclic ways, even though a lot of those dependencies are effectively "maintenance-time" or "configuration-time" rather than runtime dependencies.
Even then, from the perspective of building a Docker image in particular, a lot of "Essential" is truly inessential: a Docker app doesn't run any OS daemons, interact directly with the hardware, or perform startup functions. You don't need an hwdb or a charmap database, you don't need grub or mkinitramfs, etc.
Most interestingly, for a Docker production image that you're constructing with debootstrap, you don't need apt itself... but just try convincing debootstrap to not install apt.
Instead of using debootstrap to create your chroot environment, try using multistrap. Multistrap uses apt to do package selection and not the "stupid" dependency resolver that debootstrap uses. Thus, you have much more freedom in selecting which packages you want. For example with multistrap it is possible to create a chroot that only contains Essential:yes packages (that means no apt).
15 comments
[ 3.8 ms ] story [ 42.1 ms ] threadThis would then form a simple cycle where a dependency has to be broken to make it acyclic. A strongly connected component now is a graph where every vertex is in the cycle with every other vertex in the graph.
So for example if we add a package E to the above simple cycle where B depends on E and E depends on D, then we would not have a simple cycle anymore. Now imagine scaling this up to a couple of hundred vertices and you see how this quickly becomes a hideous mess.
I once tried to visualize such a strongly connected component and it looks like this:
http://blog.mister-muffin.de/images/hideous_mess.png
Ultimately I thought this graph to support the introduction of build profiles into Debian (now so happened with the Jessie release) as well as to promote that a tool like "botch" (you can `apt-get install` it) is necessary to automatically make this graph acyclic for you instead of doing this through year long manual work.
Is this bad? It it neutral?
I suppose it may suggest increasing code complexity and effort to maintain.
For what it's worth, I also tried to quantify how robust Debian is my measuring the ages of packages installed on my main computer.
My results are at
http://morse.kiwi.nz/kingsley/lib/exe/detail.php?id=technolo...
Even then, from the perspective of building a Docker image in particular, a lot of "Essential" is truly inessential: a Docker app doesn't run any OS daemons, interact directly with the hardware, or perform startup functions. You don't need an hwdb or a charmap database, you don't need grub or mkinitramfs, etc.
Most interestingly, for a Docker production image that you're constructing with debootstrap, you don't need apt itself... but just try convincing debootstrap to not install apt.
Instead of using debootstrap to create your chroot environment, try using multistrap. Multistrap uses apt to do package selection and not the "stupid" dependency resolver that debootstrap uses. Thus, you have much more freedom in selecting which packages you want. For example with multistrap it is possible to create a chroot that only contains Essential:yes packages (that means no apt).