Content-Addressed Build Cache Keys: What Must Go Into the Hash

A build cache that returns a stale object file is worse than no cache at all. The cache saves a compilation; the price is a binary that disagrees with its source while every step of the build reported success. The difference between a correct hit and a stale one is entirely in the key: a cache stores outputs under keys, and the key is a claim that this set of inputs determines this output. A key that omits an input produces a hit for a compilation that should have been redone. A key that includes too much produces misses and a cache that never hits, which is merely slow. The engineering question is therefore not how to hash, but which inputs are in the closure of things that can change the output.

The four categories of input

The first category is the source text of the translation unit itself, plus every file the preprocessor reads, plus the contents of those files rather than their timestamps. This is the same closure that header dependency discovery produces, and it is why the dependency list and the cache key are the same problem viewed twice.

The second category is the command line: the language, the target, the optimisation level, the warning flags that affect diagnostics rather than output, and the macros defined. The flags that affect output must be normalised before hashing, because -O2 -g and -g -O2 produce the same output and should produce the same key, while -O2 and -O3 must not. Normalisation is a real source of subtle bugs: a key computed over the raw command string will miss whenever flag order changes, and a key computed over a canonicalised form can collide if the canonicalisation drops a flag it does not recognise.

The third category is the compiler itself. The identity of the compiler binary is not its version string, because two builds of the same version can differ in configuration, in the patches applied, and in the default target. Hashing the compiler executable’s contents is the safe answer; hashing its version string is the fast answer that is wrong when distributions patch their compilers. A middle path is to hash a structured description of the compiler’s configuration, which is only as good as the description’s completeness.

The fourth category is everything in the environment that the compiler reads. Include search paths are the obvious one. The target sysroot and its headers are another. Locale settings can affect diagnostics and, in a few cases, the interpretation of source. And a compiler that reads a configuration file from a search path inherits whatever that file contains, which no command-line flag reveals.

What does not belong in the key

Absolute paths are the classic false input. A compilation that records the build directory in debug information does produce different bytes in two directories, but if the path is normalised by a prefix map then the recorded path is stable and the key can be too. Hashing the raw path means a cache shared across machines never hits, which defeats the purpose of sharing it.

The clock is the other one. Any input derived from the current time makes the key unique per invocation.

The output path is subtler. The object file’s name does not affect its contents in general, but it can affect a symbol name when the compiler derives one from the output filename, and it can affect debug information when the output name is recorded. A cache that keys on the output path gets correctness for free and loses sharing; a cache that excludes it must know that the compiler does not use it.

File metadata is the third. A key over modification times produces misses whenever a checkout rewrites timestamps without changing content, which is exactly what a fresh clone does. Content hashing costs one read per file and removes the entire class.

Two-level keys and the hit-rate consequence

The practical design separates a fast, cheap key from an expensive, precise one. The fast key is computed from the command line and the source file’s content, without opening any header. It indexes a small direct-mapped store that records the full key of the last compilation that matched, together with what that compilation read. A hit yields a candidate full key, used only after the recorded inputs have been rechecked. A miss skips the fast path, and the build computes the full key over the transitive header closure before consulting the main cache.

This design exists because computing the full key requires preprocessing, which is most of the front-end cost of a compilation. The saving is that the repeat avoids the preprocessor, not that it avoids the headers.

The recheck is what decides whether the scheme is sound. The fast key covers the command line and the main source file, so by construction it cannot distinguish two compilations whose headers differ; only the record can. The workable arrangement stores, with each fast-key entry, the identity of every file the previous compilation opened and the content it had. On a hit those files are checked, by content hash where correctness matters or by size and modification time where speed matters, and any difference sends the compilation down the slow path. Skipping the check, or reducing the record to the dependency file’s list of paths, is unsound: a header that gains a line without changing the set of headers included leaves both the fast key and the path list identical.

# The shape of a key: hash the canonical command, then the input contents
{ printf '%s\n' "$CANONICAL_CMD"; \
  find src include -name '*.[ch]' -print0 | sort -z | xargs -0 cat; } \
  | sha256sum

The snippet is illustrative rather than a complete key: it omits the compiler binary and the sysroot headers, both of which belong in the closure. It shows the two structural requirements, which are a canonical command string and a sorted, content-based input list.

Negative caching and the cost of a wrong hit

A cache that only stores successes is simpler and safer than one that stores failures, because a failed compilation may have failed for a reason that is not captured in the key: a missing file, an exhausted resource, a transient error. Storing a failure under a key and returning it later turns a transient problem into a permanent one.

The asymmetric cost of a wrong hit is the reason caches are conservative. A miss costs time proportional to the compilation. A hit on a wrong key costs a debugging session, because the artifact is present, the build succeeded, and the failure appears at run time in code that the programmer believes was compiled. The design should therefore err towards including an input rather than excluding it, and should be able to prove, for each excluded input, that the compiler cannot read it.

Two mechanisms help. The first is a key version: a change to the key’s definition bumps a version number, and all old entries become unreachable rather than wrong. This is cheap and it is what makes it safe to fix a key bug. The second is a verification mode that, when enabled, recomputes the compilation locally and compares it to the cached output, turning a wrong hit into a reported mismatch. Verification is too expensive to leave on, and it is exactly the right tool when a key’s definition changes.

Sharing a cache across machines

A local cache is a directory. A shared cache is a service, and the difference introduces the question of trust. A cached output that arrives from another machine is an executable artifact produced by a build whose inputs are claimed by a key. If the key is computed by the client, the server cannot verify the claim; it can only store and return bytes. That makes the key’s correctness a property of every client, and a single client with a buggy key can poison the cache for everyone.

The mitigations are structural: a cache scoped to a trusted set of clients, a key that includes a hash of the client’s key-computation code, or a cache that stores outputs alongside the inputs that produced them so that a client can re-verify the relationship before using the output. The third is the most expensive and the most convincing. The first is what most organisations use, and it works because the trust boundary is the organisation rather than the key. Enforcing the boundary in the other direction, by restricting what an action can read so that undeclared inputs fail loudly, is the subject of Hermetic Build Actions.

Cross-machine sharing also exposes the determinism question directly. Two machines with the same inputs must produce the same output for the cache to be sound, and that requires the compiler binary, the sysroot, and the environment to be identical. Where they are not, the key must capture the difference, and the practical way to capture it is to hash the toolchain image rather than to enumerate its properties. That is the same move as hashing the compiler binary rather than its version string, applied one level up.