What a Build Cache Key Must Cover

A cache hit is a claim that the work need not be redone. The claim is only as good as the key that was looked up, and the key is a hash over whatever the build system decided were the action’s inputs. Every input left out of the key becomes a way for a cache hit to return an artifact produced under different conditions, and the resulting failure is not a crash but a stale output that compiles, links, and passes tests until it does not.

The key is a closure, not a list

A cache key must be derived from the transitive closure of everything the action reads. The action’s declared inputs are the starting point: source files, generated headers, resources. Those inputs are themselves the outputs of other actions, so their identities are their digests, not their paths. This is why a content-addressed store makes keying tractable: the digest of an input already summarizes everything upstream of it, so the key need not walk the graph again.

The closure has three parts that are easy to conflate.

Content inputs are bytes: source files, data files, the bodies of dependencies. Their contribution to the key is their digests. Paths matter only insofar as the tool’s behaviour depends on them, which it often does: a source file’s include path can change how a preprocessor resolves a header. A path is therefore usually included as a separate field rather than folded into the content digest.

Tool inputs are the programs that transform the bytes. The compiler, the linker, the code generator, the archive tool. The identity of a tool is its own content digest, not its version string. Two builds of a compiler with the same version number can differ by a distribution patch that changes code generation, and a version string cannot distinguish them. Substituting a version string for a digest is the single most common under-keying mistake in build systems that otherwise get the content part right.

Configuration inputs are everything that selects behaviour inside the tool: flags, target triples, feature defines, optimization levels, output format options, and the values of any environment variables the tool consults. This category is where keys leak, because it is defined by what the tool actually reads rather than by what the build system declares.

Environment variables are the usual leak

A build action inherits the environment of the process that spawns it. If the action reads an inherited variable that the key does not include, two invocations with different environments collide on one key and the cache returns the artifact from whichever ran first.

The variables that cause this are rarely the ones a build system thinks about. PATH is the classic case: a build script that invokes python or cc by bare name resolves through PATH, so the tool actually used depends on an inherited variable that is usually not in the key. LC_ALL and LANG change collation order and message text. TZ changes timestamps embedded in outputs, one of the leak classes catalogued in Sources of Nondeterminism in Build Output. SOURCE_DATE_EPOCH changes embedded timestamps deliberately, so it must be in the key when it is honoured. HOME and the user name appear in paths baked into debug information by some compilers.

There are three ways to deal with this and they have different costs.

Include the whole environment in the key. This is correct and cheap to implement: hash the sorted name-value pairs of the environment. It is also brutal to the hit rate, because CI injects variables that differ per run (a build number, a job identifier, a temporary directory) and every one of them partitions the cache. A cache keyed on a variable that changes every run never hits.

Whitelist the variables that matter. Enumerate the ones known to influence the tool and hash only those. This restores the hit rate and reintroduces the leak the moment someone adds a variable the list does not know about. It converts a correctness property into a maintenance obligation.

Clear the environment and pass exactly what the action needs. The action runs with a fixed, minimal environment, and the key hashes that environment. Anything not passed is not readable, so it cannot influence the output. This is what hermetic build systems do, and it is the only option that makes the key’s completeness checkable rather than hoped for. It requires the build to run in a sandbox or a container with a controlled environment, which is the real reason hermetic builds are expensive to adopt.

Over-keying is a real failure, not a safe default

The instinct after learning about under-keying is to hash everything. That instinct produces a cache that always misses, and a cache that always misses is strictly worse than no cache: it pays the cost of storing and looking up entries while returning nothing.

The specific over-keying errors are recognizable. Including the absolute path of the working directory makes the key differ between two checkouts of the same commit, which is exactly the case a shared cache is supposed to serve. Including file modification times makes the key differ after any re-checkout, even though mtimes are not inputs to a compiler’s output. Including the build’s own identifier or the invoking user’s identity makes the key unique per invocation.

The right test for an input is counterfactual: if this value changed and nothing else did, could the output bytes change? If yes, it belongs in the key. If no, it does not. Applying that test to mtimes gives a clear no for most tools — a compiler that does not embed timestamps produces the same object file regardless of source mtime — and a clear yes for archive tools that copy mtime into tar headers. The answer is per-action, not global, which is why a single global key policy tends to be either unsafe or useless.

Separating the action key from the output digest

There are two distinct hashes in a well-formed cache and conflating them causes trouble. The action key identifies the computation: inputs plus tool plus configuration. The output digest identifies the result: the bytes produced. The cache maps the first to the second.

Keeping them separate buys three things. The same output can be produced by two different action keys, for instance a source file reformatted without semantic change or two equivalent flag spellings, and a content-addressed store then holds one copy rather than two. An action key can be looked up without transferring the output, so a miss costs one small request rather than a full download. And an output digest can be verified independently of the key, so a corrupted or tampered cache entry fails verification rather than silently poisoning the build.

A compact key derivation that makes the three categories explicit:

import hashlib, json

def action_key(command, args, inputs, tools, env_whitelist, env):
    # inputs: {relative_path: digest} for every declared input, already
    # reduced to content digests by the caller.
    payload = {
        'command': command,
        'args': args,                       # ordered list, not a set: flag order can matter
        'inputs': sorted(inputs.items()),   # sorted so dict order cannot leak in
        'tools': sorted(tools.items()),     # tool name -> digest of the binary
        'env': {k: env[k] for k in sorted(env_whitelist) if k in env},
    }
    blob = json.dumps(payload, sort_keys=True, separators=(',', ':')).encode()
    return 'sha256:' + hashlib.sha256(blob).hexdigest()

Two details in that function are deliberate. Arguments are kept as an ordered list because -O2 -g and -g -O2 are the same to most compilers but not to all, and a key that sorts them is making a claim about the tool that the key cannot verify. The JSON serialization uses sorted keys and no whitespace so that two callers building the same logical payload produce identical bytes; a key function whose output depends on a dictionary’s insertion order is a bug waiting for a refactor.

Keys for whole stages versus keys for single actions

The granularity of the key determines what a hit can skip. A per-action key lets the cache return one object file and lets the scheduler skip exactly the work that produced it. A per-stage key, which hashes the whole source tree, the whole dependency set, and the stage’s script, returns a hit only when nothing in the stage changed, so a one-line edit to a single file invalidates the entire stage’s cache.

The coarse key is much cheaper to implement and much less effective. Its cost shows up in the tail: the common case is a small change to a large stage, and a coarse key misses on every one of those. Fine-grained keys are what make incremental builds feel incremental, and they depend on the build system knowing the dependency graph at action level rather than at file level.

Coarse keys are still correct, which is why they are a reasonable first step. The failure to avoid is a coarse key that is also incomplete: a stage key that hashes the source tree but not the base image or the dependency lockfile. That combination is the worst of both, because it misses often and returns wrong results when it hits.

What the key cannot express

A key covers declared inputs. It cannot cover an input the action reads without declaring: a file outside the sandbox, a network call, an environment variable read through a path the whitelist missed. In a non-hermetic build these undeclared reads are invisible, and the cache will happily return an artifact that does not correspond to the current world.

The practical consequences differ by what was missed. A missed source file produces an artifact that is stale but internally consistent, and the failure appears as a change that does not take effect. A missed tool produces an artifact built by a different compiler, which may be indistinguishable at the object level and divergent at the behaviour level. A missed configuration value produces an artifact with the wrong feature flags enabled, which is the most dangerous case because it usually builds and links.

The mitigations are ordering and verification rather than keying. Run actions in a sandbox that denies access to anything undeclared, so an undeclared read fails loudly instead of silently influencing the output. Verify the output digest on retrieval, so a corrupted entry cannot be used even if the key matched. And treat cache poisoning as an adversarial problem, not only an accidental one, which is why entries produced by untrusted builds need a separate namespace, the concern covered in Trust Boundaries in Shared Build Caches.

None of this makes the key complete in an absolute sense. It makes the incompleteness bounded and visible, which is the achievable goal. A key is a hypothesis about which inputs determine an output, and the engineering work is in shrinking the set of inputs the hypothesis gets wrong, then detecting the residue with sandboxing and verification rather than with hope.