Towards Idempotent Rebuilds?
blog.josefsson.org
blog.josefsson.org
There is always going to be a degree of un-reproducibility just due to the nature of math. If you don't have the same system, same compiler version (down to the minor or patch level), same dependency versions, same build flags, filesystem ordering, OS handling etc. . .you're going to get differences.
The RB project has readily disclosed that there is a degree of "significantly reproducible" sussing that each end user is going to have to do. The fact that the Debian maintainers chose not to display the degree of reproducibility is probably because showing low reproducibility scores undermines the efforts to evangelize the movement.
I think that's understandable, but also is a bit of a two edged sword. If we don't disclose scores, we allow for the misrepresentation that "this is safe because it has the word reproducible in it". If we disclose scores, we get articles like this saying "wow, thats a really low score, wtf" and short lived paranoia gives way to ambivalence about the whole thing.
It's difficult to capture the nuance in this in pithy tidbits, hence blog post on HN with me explaining this :).
> There is always going to be a degree of un-reproducibility just due to the nature of math.
Fundamentally the math is deterministic (reproducible): if you do the same sequence of mathematical operations you get the same result. I gather you're getting at the non-associativity of floating point (eg additions), which is a fair point, but if you arrange to do your floating point operations in the same sequence then it will be reproducible.
This requires engineering on the part of compiler writers, but ultimately is solvable, given enough funding.
(About the compiler writers part: I'm thinking about GHC Haskell and the like... the Clangs/GCCs of the world will have no problems because of Translation Units. Things may change when Modules are a practical choice.)
Until then, those issues will continue to be lumped together with all the software reasons it wasn't reproducible.
My first Pentium could usually but not always math correctly until Intel replaced it during a recall.
Sitting in the middle results with additional downsides from modifying pipeline without core upsides of reproducible builds.
Clang works fine as a compiler for this--there is nothing in it that normally produces different results due to timing or whatever. When something does leak in, we fix it upstream. You do have to ensure that no one uses __DATE__ or similar macros, or that you redefine them to a known value on the command line.
You know what would be awesome? If someone could start from, let's say, live-bootstrap[1] and build towards matching the checksums for some distro kernel+toolchain.
It sounds like the same kind of problem, it all comes down to knowing what build conditions affect the resulting binaries, so I think you nailed the problem description on this and yes, it all feels very orthogonal from that perspective!
Thanks for writing this blog entry!
Since we already have "deterministic build" and "reproducible build" for this, there's no need to overload "idempotent" (which already causes confusion).
An idempotent build is when you type "make" twice and the second one doesn't do anything.
This stuff matters. You can't trust open source supply chains any more. There have been too many incidents of someone inserting a security hole.
For a software build it sounds like running `make` multiple times. But those builds will be idempotent even without reproducibility/determinism as they happen on the same system.
"Multiple runs of the same compiler on the same code produced the same output"
No more revolutionary a concept than a hash function. Valuable like a hash function, but not revolutionary.
The goal of reproducible/deterministic builds is typically to be able to produce the same output files without already having that output. (That's because the people interested in reproducible/deterministic builds are usually trying to prove something about the relationship between the source and the build output. Make doesn't really do that -- the only thing it can prove is that the mod times of output files are later than the mod times of the source files they depend on, according to the make file.)
So, yes, make is typically deterministic in a general sense (given a good makefile and certain assumptions that are pretty reasonable in the context of a developer doing development on a local machine). But isn't what people are looking for from reproducible/deterministic builds.
When a more systems-inclined person in computer science uses the word idempotent they very often mean something like “repeatable” or “deterministic”.
AFIAK this usage first gained traction in the theory of distributed systems, in which it (roughly) means that one application of an operation might change the state of the system, but subsequent applications will not change it further. Set union is sort of the canonical example.
For example, let’s consider a function that accepts a string as an argument and then writes that string to disk. We can consider the disk state as a side effect of the function.
The function itself is perfectly deterministic (output string is a predictable and consistent function of input string), but depending on the implementation of side effects it may not be idempotent. If, for example, this function room simply added the output to a file “output.txt”, this file would grow with every incantation, which is not idempotent. If instead we overwrote the output file so that it reflects only the singular output of the previous run, then the side effects would also be deterministic, that would be idempotent.
At a pedantic level you could redefine your scope of deterministic to not just include outputs, but also include the external state and side effects, but for practical purposes the above distinction is generally how deterministic and idempotent would be applied in practice in computing. I cannot speak to the math-centric view, if there is a different definition there.
But that simply means it's harder to implement true idempotency when it comes to disk usage.
This is why the problem is usually simplified to ignore unhappy paths.
The idempotent version of this function doesn't blindly write. Most of Ansible, for example, is Python code doing 'state machines' or whatever - checking if changes are needed and facilitating if so.
Where y'all assume one function is, actually, an entire script/library. Perhaps I'm fooled by party tricks?
Beyond all of this, the disk full example is nebulous. On Linux (at least)... if you open an existing file for writing, the space it is using is reserved. Writing the same data back out should always be possible... just kind of silly.
It brings about the risk of corruption in transit; connectors faulty or what-have-we. Physical failure like this isn't something we can expect software to handle/resolve IMO. Wargames and gremlins combined!
To truly tie all this together I think we have to consider atomicity
Depends on the implementation: maybe you open a temp file and then mv it into place after you are done writing (for increased atomicity)?
But as I already said, in practice we ignore these externalities because it makes the problem a lot harder for minor improvements — not because this isn't something software can "handle/resolve".
This is deterministic (doesn't change randomly), but not idempotent.
The reason they don't like Nix should be obvious; it blatantly and vocally doesn't even try to do the thing the authors want. It'd be just as relevant to bring up Gentoo or something -- another fine project, like Nix, but not especially helpful for the stated problem, and so obviously so that it shouldn't be worth paying lip service to in the article.
"When compiling from the same source on independent infrastructure yields bit-by-bit identical results, this gives confidence that the build infrastructure was not compromised and the artifact really does correspond to the source." - https://reproducible.nixos.org/
- Their homepage defines reproducibility to be something other than bitwise identical results.
- Getting actual bitwise reproducible builds is still hard for most large projects, even with the work Nix has done (note that the quote you pulled doesn't actually say that Nix _does_ provide such builds, and the rest of that linked text just tries to highlight some of the tools you have at your disposal to achieve that).
They do "try" insofar as they're aware of the desire for bitwise identical results, provide them in some cases, and provide tools to diagnose problems. They're also 20 years old and more than happy to call the current results reproducible. At the very least, it doesn't look like one of the top properties for the project.
It's not. That would be comparable to magic.
@Foxboron wrote a compelling if clickbaity post a few months back to poke at the bit-for-bit interpretation of what reproducibility means in nixland: https://linderud.dev/blog/nixos-is-not-reproducible/
It didn't get much traction here (https://news.ycombinator.com/from?site=linderud.dev) but there was more lively discussion on lobsters: https://lobste.rs/s/jpoy4q/nixos_is_not_reproducible
(That said, the nix ecosystem does have levers and practices for working to weed out common sources of build reproducibility problems and the community is reasonably interested/active here. But there isn't any magic in it that fixes all bit-for-bit issues. People still have to catch, tag, and fix them.)
Not going to lie, I either don't understand what you're saying, or don't understand the shade you're trying to throw.
Nix is going to do as good, or better a job, than any other solution other there. Probably with a lot less duck-tape.
Not to mention that much of Nix packages are reliably bit-for-bit reproducible.
Not to not to mention that bit-for-bit reproducability is really only beneficial for "trust", not reliability or re-playability.
And no, comparing Nix to Gentoo in this case only very much confirms you don't understand Nix. Maybe you should check out the talk from a past NixCon where the speaker rebuilds Firefox from 10 years ago and boots up Flash swfs.
There is none. Nix does lots of great things, like that Firefox demo you mentioned. TFA wants bitwise identical builds, and Nix isn't great at that in general, by their own admission.
> various praises for Nix
Yep, Nix is great.
> downplaying TFA's wants
That's worth writing somewhere probably, but not when arguing that Nix solves their problem. If their problem isn't real then potato peelers solve it just as well. Nix isn't really relevant at that point.
> Nix compared to Gentoo
The commonality is that neither solve TFA's problem, and neither try very hard to do so.
Bazel does this sort of thing remarkably well. Internal to google, it provides a multi-billion line monorepo with deterministic, highly-concurrent, bit-wise identical builds.
I'm not as familiar with Nix, but knowing what it takes for Bazel to do it, I would be surprised if Nix is as good.
> Probably with a lot less duck-tape.
And that is probably true.
We don't know that. Nobody has even attempted to build more then an incredibly small fraction of the packages `nixpkgs` provides.
This goes quite far along the path, building all the build tools and toolchain to the same version before building the packages.
Deterministic builds aren't always that straightforward
There's a long tail of tricky problems to solve for reproducible builds, but a specific build of a compiler producing different executable code from run to run hasn't really been one of them.
If what you're saying is true - stage 3 bootstrap wouldn't be possible.
So I'm reasonably sure it does produce bit-identical results.