Sources of Nondeterminism in Build Output

A build that produces a different digest on each run is not wrong in any way that a test suite detects. It is wrong in a way that invalidates the premises of everything built on top of it: caches that never hit, artifacts that cannot be compared across machines, and audits that cannot answer whether two releases contain the same code. The causes are few and unglamorous, and almost all of them come from the build reading something that was not an input.

The detector is two builds and a diff

Nondeterminism is found by building twice and comparing. The comparison has to be done carefully, because most tools that produce nondeterministic output also produce it in a way that a byte-for-byte cmp reports uselessly: the two files differ, and the difference is a few bytes in the middle of a section.

Two techniques make the difference readable. The first is to vary the things that should not matter — build directory, user, hostname, clock, parallelism — and hold everything else fixed. If varying one of those changes the output, that is the source. The second is to diff the artifacts with structure: objdump the sections of two object files and diff the disassembly and the symbol tables, or unpack an archive and compare member by member, so the differing bytes can be attributed to a named section rather than an offset.

The reproducibility project’s discipline adds a third element: build in two different directories on the same machine, and also on two different machines with different paths and users. A single-machine rebuild catches the timestamp class of problems and misses the path class, because both builds see the same path.

Timestamps are embedded in more places than expected

The obvious timestamp is __DATE__ and __TIME__ in C source, which expand to the compile moment. That one is easy to find because it is in the source, and easy to fix because the preprocessor honours SOURCE_DATE_EPOCH: when the variable is set, GCC and Clang substitute the value derived from it instead of the current time, so the macros become a function of a declared input.

The less obvious ones are written by tools rather than by source. An object file can carry no timestamp, but a static library does: the ar archive format stores a modification time per member, and the default ar behaviour records the current time. The fix is the deterministic mode, which records a fixed timestamp and fixed ownership and sorts members by name. Without it, two builds of identical objects produce different archives, and the difference propagates to every binary linked from them.

Compression adds another layer. A gzip stream carries an mtime field in its header and, unless told otherwise, a filename field. Compressing the same tar twice produces different bytes. gzip -n omits both. Zip archives similarly store per-entry timestamps, and the tooling that writes them has to be configured to use a fixed date rather than the file’s.

Build identifiers are a related case that is not a clock read at all. A linker that computes a build ID from the output is deterministic; one that incorporates a random or time-derived value is not. The distinction matters because a build ID is exactly the field a downstream verifier uses to identify a binary, so a nondeterministic build ID defeats the purpose of having one.

Paths, users, and the working directory

Compilers embed paths in debug information and in assertion messages. DW_AT_comp_dir records the compilation directory, and DW_AT_name records the source path as passed on the command line. Both are absolute in a default build, so two builds from /home/alice/src and /build/worker-7/src produce object files that differ throughout the debug sections.

There are two distinct fixes and they solve different problems.

Path remapping rewrites the recorded path at compile time, so the object file records a stable prefix instead of the real one. The mapping has to be identical on every machine, which means the build must know its own mapping — usually a fixed mount point inside a container — and the mapping must be part of the cache key, because it changes the output bytes.

Relative compilation avoids the problem instead of rewriting it. If the build runs with the source root as the working directory and passes relative paths to the compiler, the recorded paths are relative and identical everywhere. This requires the build to control its working directory, which is a stronger requirement than it sounds: many build scripts cd into a subdirectory and pass paths relative to that, so the recorded path depends on where the script was invoked from.

User and host names leak through the same channels. A #pragma or a compiler flag that records the build user, a generated file that includes whoami output, a shell script that writes $USER into a version string. These are not systematic and have to be found by searching generated output for the strings, which is why the two-build diff is the primary tool rather than a policy.

Iteration order, hash seeds, and parallelism

Directory iteration order is filesystem-dependent. readdir returns entries in whatever order the directory’s internal structure yields, which differs between filesystems and changes as files are created and deleted. Any build step that walks a directory and writes the results into a single output — a generated source file listing resources, an archive, a link command line — produces different output on different machines unless it sorts.

The same class of bug appears inside language runtimes. A program that iterates a hash table and serializes the result produces output that depends on insertion order and on the hash seed. Some runtimes randomize string hashing per process specifically to prevent algorithmic complexity attacks, which means the iteration order differs between two runs of the same program on the same machine. A code generator written in such a language must sort explicitly; the runtime will not do it.

Parallelism introduces a third variant. A build that runs independent actions concurrently and appends their outputs to one file gets an order determined by completion timing. This is nondeterministic even on a single machine and becomes more visible as the machine gets faster or the scheduler changes. The fix is to collect results by key and serialize at the end, rather than to serialize as each finishes.

A small illustration of the ordering bug and its repair:

import os, json

def manifest(root):
    # os.listdir order is filesystem-dependent and changes with history.
    names = os.listdir(root)
    return json.dumps([{'name': n, 'size': os.path.getsize(os.path.join(root, n))}
                       for n in names])

def manifest_stable(root):
    names = sorted(os.listdir(root), key=lambda n: n.encode())
    return json.dumps([{'name': n, 'size': os.path.getsize(os.path.join(root, n))}
                       for n in names], sort_keys=True)

The key=lambda n: n.encode() is not decoration. Sorting strings uses the locale’s collation rules in some languages and Unicode code-point order in others, and the two disagree on mixed case and on non-ASCII names. Sorting the encoded bytes gives the same order regardless of locale, which is the property an action key needs.

What cannot be removed, and what to do instead

Some nondeterminism is intrinsic to the tool and not fixable by configuration. A compiler that performs aggressive optimization may make choices that depend on scheduling or on addresses; a linker that lays out sections by hash may produce different layouts across runs if it uses a randomized seed. Uninitialized memory read by a code generator produces output that varies with whatever the allocator returned.

For these, the practical response is to narrow the surface. Fixing the seed where the tool exposes one, disabling the feature where it does not, and pinning the tool version so the behaviour at least does not change under the build’s feet. The remaining variation is then documented as a known limit rather than discovered later as a mystery.

There is also a class of nondeterminism that is deliberate and should not be removed: a build that embeds a commit identifier is producing different output for different commits, which is correct. The test is whether the variation corresponds to a difference in inputs. A build that varies with the clock varies without an input changing, and that is the defect. A build that varies with the source varies because the source is an input, and the output digest then legitimately identifies the source state.

The distinction is what makes Content-Addressed Artifact Identity meaningful. A digest is only a statement about inputs if the mapping from inputs to output is a function. When it is not, the digest still names bytes but no longer names a build, and a cache keyed on inputs will return artifacts that were produced under conditions the key did not describe. The same property decides whether an archived recipe can ever reproduce the bytes it names, which is the question taken up in Rebuilding a Pinned Artifact Without Its Original Environment. Determinism is the property that lets the rest of the pipeline reason about identity at all, and it is bought by removing reads of everything that is not an input.