Action Cache Keys and Shared Build Caches

A local content hash, as described in Content-Hash Caching and Early Cutoff, tells a build system whether an action it ran before produced the same bytes. A shared cache generalises the question to whether anyone, anywhere, has run that action. That generalisation is where most of the design difficulty lives: the local case tolerates a conservative answer, while the shared case requires the key to be complete enough that a hit from an unrelated machine is a valid answer.

Two levels, because they have different lifetimes

The standard architecture separates the mapping from action to result from the storage of the result itself. The first level, usually called the action cache, maps an action key to a record describing the outputs: their digests, their sizes, and often their permission bits. The second level, the content-addressed store, maps a digest to the bytes with that digest. Build systems that expose this separation over a network protocol keep the two as distinct services, one small and metadata-heavy, one large and byte-heavy.

The reason to split them is that the two levels have different access patterns. Reading an action-key entry is a small lookup, cheap enough to do for every action in the graph before deciding what to execute. Reading the bytes of an output is expensive and only necessary for actions that are cache hits, and even then only for the outputs the requested targets actually need. Splitting also permits different storage technologies: a key-value store for the action cache, an object store with deduplication for the bytes, since identical blobs appear repeatedly across an output set.

A third consequence of the split is that the two levels want different durability guarantees. A blob store can lose data without the build becoming incorrect, provided the loss is reported as a miss, because any evicted blob can be regenerated by the action that produced it. The action cache is closer to a record of work performed, and losing it costs time rather than correctness. That asymmetry justifies a small, well-replicated key-value store for the metadata and a large, cheap, deduplicated object store for the bytes, with the byte store sized for the working set of active builds rather than for every artefact ever produced. It also explains why the byte store can be shared between projects that never otherwise interact: a blob is just a blob, and the only thing that makes it useful is that some action record names its digest.

Because the byte level is addressed by content, it is self-verifying: a corrupted or truncated blob fails a digest check on read, and the entry can be discarded. The action level has no such property, which is why the correctness of the entire scheme reduces to the correctness of the key.

What has to be in the key

An action key must be a function of everything that can change the output, and of nothing else. In a hermetic system the input set is known exactly, so the key is a digest over a canonical serialisation of the command line, the digests of the declared inputs, and the identity of the tools. Because the tools are inputs in such a system, their digests are already in the input set, and the key changes when the compiler changes.

The hard part is not hashing more, it is hashing consistently. Two machines must serialise the same action to the same bytes. That means sorting file lists, using relative paths within the input root rather than absolute paths, and excluding anything that varies. A command line that names an output directory by absolute path produces different keys on machines with different working directories, so the tool either rewrites paths before hashing or the executor must guarantee a fixed layout.

import hashlib, os, json

def file_digest(path):
    h = hashlib.sha256()
    with open(path, 'rb') as f:
        for chunk in iter(lambda: f.read(1 << 20), b''):
            h.update(chunk)
    return h.hexdigest()

def action_key(argv, inputs, env, tool_digest):
    # inputs: mapping of relative path -> digest; env: only variables the
    # action is allowed to read, sorted so serialisation order is fixed.
    payload = {
        'argv': argv,
        'inputs': [[p, inputs[p]] for p in sorted(inputs)],
        'env': [[k, env[k]] for k in sorted(env)],
        'tool': tool_digest,
    }
    blob = json.dumps(payload, separators=(',', ':'),
                      sort_keys=True).encode()
    return hashlib.sha256(blob).hexdigest()

Two consequences follow from the requirement that the key cover everything. First, a tool that reads a configuration file must have that file declared as an input, or the key will not change when the configuration changes. Second, a tool that reads an environment variable must have that variable included, which is why hermetic execution matters here: an action run under a scrubbed environment cannot read variables the key does not mention, so the omission cannot silently change behaviour.

Hits across machines

Once a cache is shared, a hit means an output produced somewhere else, by a different toolchain installation on a different distribution, is being installed in the local tree. Four properties have to hold for that to be sound.

The inputs must be identical. Digest equality across machines requires the same hashing scheme, including the same treatment of directory entries, symlinks, line endings, and executable bits. If one machine stores a .sh script with the executable bit set and another does not, and the digest scheme covers permission bits, the two trees hash differently and the cache simply misses. If the digest scheme ignores permission bits, the two trees hash identically and an output built from a non-executable script may be served, harmless in most cases, wrong in some.

The environment must be identical, for the subset of it that affects the action. Environments differ between machines far more than file trees do: a user’s locale, their home directory path, and any site-specific variables all differ. The usual resolution is that the build system constructs the action environment from a fixed specification rather than inheriting the invoking shell, so the environment becomes a declared input.

The toolchain must be identical, which is why toolchains are distributed as content-addressed artefacts rather than assumed to exist at a conventional path. This is the practical reason a build system ends up packaging a compiler: without it, the key cannot distinguish two compiler builds that produce different object files.

The action must be deterministic. Determinism is not required for a local cache to be useful, but it is required for a shared one to be correct, because the first machine’s output becomes the answer for every subsequent machine. A deterministic action is one whose output is a pure function of its inputs; the failures of that assumption are the subject of Bit-Reproducible Builds and Nondeterministic Actions.

How shared caches go wrong

The most common defect is a key that is too small. An action whose behaviour depends on an unhashed input will receive cache hits for results it did not produce, and the resulting failures are proportional to the subtree above it and are invisible until someone changes that hidden input. The classic instance is a rule whose output depends on a file outside the input root, or on a registry of packages looked up at build time.

The second defect is nondeterminism that is only occasionally visible: an action that usually produces the same bytes and sometimes does not. With a shared cache this is worse than with a local one, because the wrong value propagates to every machine. Detection requires running the same action twice under identical conditions and comparing output digests, which is cheap for a build system to do systematically and rarely done.

The third is stale metadata in the action cache: the key-to-outputs mapping surviving while the underlying blob has been evicted. The read then fails rather than returning wrong data, and the action must be re-executed. Treating a dangling entry as a miss rather than an error is a small implementation detail that determines whether a missing blob costs a re-execution or an unusable cache.

Eviction interacts with all of this. Content-addressed stores can be evicted on any policy, commonly least-recently-used by byte volume, because no blob is unique in principle: any evicted blob can be regenerated by re-running the action that produced it. The action cache is less forgiving, since it encodes work as well as data, but it too can be evicted wholesale. Reference counting by closure, which counts how many live outputs reach a blob, avoids evicting a blob still needed by an installed output, and is the approach taken by package stores that are built on the same structure.

Finally, protocol details leak into behaviour. Caches served over HTTP inherit the semantics of that layer, which is why a cache protocol specifies request methods, conditional requests, and the distinction between a response that may be stored and one that must not be. The general framework for that distinction is HTTP caching.

# Fetch a known blob from a shared cache and verify it against its key.
# The digest in the URL is the expected content digest, so the check is
# not an optimisation but the only integrity guarantee on the transfer.
key=9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
curl -fsSL "https://cache.internal/cas/${key}" -o blob.bin
[ "$(sha256sum blob.bin | cut -d' ' -f1)" = "$key" ] || { echo corrupt; exit 1; }