Content-Hash Caching and Early Cutoff

A build cache answers one question: has exactly this action, with exactly these inputs, been performed before? Timestamps cannot answer it, because they describe when a file was written rather than what it contains. The alternative is to identify everything by the hash of its content, which turns the question into a comparison of fixed-length strings and, as a side effect, gives the build system a way to notice that a rebuild produced nothing new.

A digest is an identity, not a name

Hashing an input tree produces a value that depends on every byte in the tree. The standard construction is a Merkle tree: each file’s digest is computed from its contents, and a directory’s digest is computed from the sorted list of its entries’ names and digests. Changing one byte anywhere in the tree changes the root digest, and two trees with the same root digest are, up to collisions, the same tree.

The digests in this design carry no secrets, but they must be collision-resistant, because the correctness of the whole cache rests on “same digest implies same content” being true. SHA-256, standardised in FIPS 180-4, outputs 32 bytes and is written as 64 hexadecimal characters; any strong hash serves the same role. A non-cryptographic hash with a small output would be faster and would occasionally make two different input sets look identical, which in a build cache means serving the wrong artefact, a failure that is both silent and hard to attribute. The choice of a cryptographic function here is a correctness decision rather than a security one.

Sorting matters in the directory-digest construction for the same reason. A digest that depends on directory iteration order changes whenever the filesystem returns entries in a different order, so two identical trees would hash differently on different machines. Every content-addressed build system therefore canonicalises: entries sorted by name, and typically a length prefix or separator between names and digests so that a name cannot be extended to collide with the start of the next entry.

What belongs in the action key

Hashing a file gives its identity; hashing an action requires deciding which of its surroundings affect its result. The key is normally a digest over a canonical serialisation of: the command line as executed, the digests of the declared input files and directories, and the identity of the tools invoked. In systems that model the toolkit as ordinary inputs, the compiler binary and its supporting files are themselves hashed, so upgrading the compiler changes every key it participates in and no stale object survives.

What is deliberately excluded is as important as what is included. Output paths, absolute source paths where the tool does not embed them, host names, and the current time all vary between otherwise identical builds and would destroy cache reuse if hashed. The tension is that a tool may read an undeclared part of its environment (a locale setting, a value from the process environment, a file in a well-known location) and the build system, lacking that declaration, will produce the same key for two actions that behave differently. This is why hermetic execution and content hashing are complementary rather than redundant: hashing detects change in declared inputs, sandboxing makes undeclared inputs fail loudly instead of silently poisoning the cache.

Early cutoff

The second benefit of hashing appears after an action runs. Before the build, the tool records an output digest. After the action completes, it computes the digest of each output. If the new digest equals the recorded one, the output did not actually change, and anything that depends on it need not be rebuilt.

Consider a source tree where a widely included header gains a comment, or where a code generator is re-run with an input whose changed bytes do not reach the generated output. Under timestamp-based incrementality, the header’s newer modification time marks every translation unit that includes it stale, all of them recompile, then all of them relink because their object files were rewritten. Under hash-based incrementality with early cutoff, the translation units are recompiled because their input bytes did differ, but if the resulting object files are byte-identical, the digests match the recorded ones and the link step is skipped. The propagation of staleness stops at the first layer whose outputs are unchanged.

The terminology in the literature for this property is early cutoff, and it is the distinguishing feature of the “constructive trace” style of build system: the rebuild decision depends on the observed content of outputs, not on the fact that an action was re-executed. Nix’s derivations rely on a related observation, that a build result is identified by the closure of its inputs, so an unchanged input closure means an unchanged store path and nothing downstream needs touching.

# Early cutoff at the level of one action: re-run the generator, then ask
# whether the output actually changed before invalidating its dependents.
before=$(sha256sum generated.h | cut -d' ' -f1)
./gen --input schema.json --out generated.h
after=$(sha256sum generated.h | cut -d' ' -f1)
[ "$before" = "$after" ] && echo "output unchanged; dependents stay clean"

The limit of early cutoff is that it requires the action to have run. It saves downstream work, not the work of the action itself. A hash-based tool can go further and skip the action entirely: if the computed key is already present in a cache, the recorded outputs can be installed without executing anything, which is what makes shared caches across machines worthwhile.

Hashing cost and where it is paid

Hashing every input on every invocation reads the whole input set, which is the cost that timestamps avoid. A tree of a few thousand small files hashes in a fraction of the time a compiler takes on one translation unit, so the overhead is invisible; a tree of tens of gigabytes is a different matter, and reading it can cost more than the incremental compile it is being used to decide on.

Practical systems reduce the cost in three ways. A persistent digest cache keyed on path, size, and modification time avoids rehashing files whose metadata is unchanged, so the expensive operation runs only for files that plausibly changed. Directories and other grouping nodes are memoised so that each file is hashed at most once per invocation. And hashing is parallelised, because it is trivially data-parallel across files, whereas compilation is not.

The remaining cost is storage: a persistent mapping from action key to output, plus a content-addressed store holding the output bytes. The store can be deduplicated and garbage-collected by reference, since nothing in the scheme depends on where a blob came from. The structure of the key itself, including how it encodes the toolchain and what happens when two different actions collide on the same key, is taken up in Action Cache Keys and Shared Build Caches.

Where hashing stops helping

Three situations defeat content addressing, and all three are worth recognising early.

First, an action whose output embeds something varying, such as the wall-clock time of the build, a build path, or the identity of the machine. Such an action produces a different digest on every run even when its inputs are identical, so it invalidates every downstream action and makes early cutoff useless. This is the same defect that makes a build non-reproducible, treated in Bit-Reproducible Builds and Nondeterministic Actions, and the remedy is the same: normalise the varying input rather than the hash.

Second, an incomplete declaration of inputs. If the action reads a file the graph does not mention, the digest covers the wrong set of bytes, and a cache hit may return an output built from different content. Hashing is only as sound as the input declaration it is given.

Third, an input set that changes constantly for a trivial reason: a version file regenerated on each invocation, a generated header containing a commit identifier. Because the digest of a single leaf propagates to the root, one volatile byte invalidates the whole subtree above it. Mitigations are local: exclude the volatile file from the key when the tool does not genuinely depend on it, or arrange the graph so that the volatile value is injected as late as possible, near the leaves rather than the root.