articles / caching

Cache keys are a correctness problem

Most build caches today are content-addressed. Before running a step, the tool computes a key from everything that could influence the step's output and looks it up. If an entry exists, the stored outputs are reused; if not, the step runs and its outputs are stored under that key.

Bazel, Gradle, ccache, sccache, Nx and Turborepo all work some variation of this way, and so does the key: you type into a CI cache step. The hard part is always the key, and keys fail in two directions:

• A false hit: something that affects the output is missing from the key. The cache returns an artifact built from different inputs and nothing fails. You just ship the wrong thing.
• A false miss: something irrelevant is part of the key. The cache never hits, and you pay for uploads and downloads on top of the build.

Both are common. Only the first is dangerous, which is why we treat cache keys as a correctness problem first and a speed problem second.

What belongs in a key

Think of the key as the hash of a manifest, a canonical, ordered list of every input. For one build step:

• the exact command line, flags included;
• the contents, not the timestamps, of every input file;
• the toolchain's identity: a digest of the compiler or of the image the step runs in, not its name;
• the environment variables the tool actually reads;
• the platform, if output can differ between operating systems or architectures;
• the keys of the steps it depends on.

That last item makes the scheme compose: a change anywhere below a step changes its key automatically.

A minimal key function in Python shows the details that matter:

import hashlib

def file_digest(path):
    with open(path, "rb") as f:
        return hashlib.file_digest(f, "sha256").digest()

def action_key(argv, inputs, env, toolchain, platform, dep_keys):
    h = hashlib.sha256()

    def field(name, value: bytes):
        # Length-prefix each part: ("ab", "c") must not equal ("a", "bc").
        for part in (name.encode(), value):
            h.update(len(part).to_bytes(8, "big"))
            h.update(part)

    field("argv", "\0".join(argv).encode())
    for path in sorted(inputs):      # workspace-relative paths, sorted
        field("in:" + path, file_digest(path))
    for name in sorted(env):         # an allowlist, never os.environ
        field("env:" + name, env[name].encode())
    field("toolchain", toolchain)    # e.g. digest of the compiler binary
    field("platform", platform.encode())
    for key in sorted(dep_keys):
        field("dep", bytes.fromhex(key))
    return h.hexdigest()

Contents rather than metadata, sorted inputs, unambiguous field boundaries: those three choices carry most of the weight. (hashlib.file_digest needs Python 3.11 or later.)

Where keys go wrong

Undeclared inputs

The classic false hit. A compiler finds a header through an include path nobody hashed, a code generator reads a template nobody listed, a test loads a fixture from a sibling package. Change the undeclared input and the key stays the same.

Sandboxing is the structural fix: a step that can only see its declared files fails loudly instead of hitting silently. Bazel sandboxes actions by default where the platform supports it. Without a sandbox, trace which files a step opens and compare that with the declared list:

strace -f -e trace=openat -o opens.log make -C lib/parser
grep -o '"[^"]*"' opens.log | sort -u > opened.txt

The list deliberately keeps failed lookups: a header missing today from an earlier include directory would shadow the current one on the day someone adds it, so its absence is an input too.

A toolchain identified by name

A key that says gcc rather than which gcc keeps serving objects from last month's compiler after the CI image is updated. Hash the binary, or use the image digest. Even ccache's default compiler_check is a heuristic, comparing the compiler's modification time and size; it can be set to content or to a command such as %compiler% -v.

The environment: all or nothing

Hash the whole environment and you get false misses: HOME, job IDs and temporary directory names differ on every run. Hash none of it and you get false hits: CC, CFLAGS, NODE_ENV and LANG all change outputs. Use an explicit allowlist per step, and run the step with a scrubbed environment so it can't read anything else. Turborepo's env and globalEnv settings and Bazel's --incompatible_strict_action_env flag are versions of this idea.

Absolute paths

If /home/alice/src/app appears in a key, nobody else will ever hit Alice's entries. If it appears in an output (debug information, __FILE__, a source map), outputs differ between machines and everything downstream misses. Use workspace-relative paths in keys and remap paths in outputs: -ffile-prefix-map=$PWD=. for GCC and Clang, -trimpath for Go.

Timestamps instead of contents

Make compares modification times, and so does plenty of hand-written CI caching. Git doesn't store mtimes, so to an mtime-based scheme every fresh clone looks entirely new.

Coarse keys in CI configuration

Hand-written CI cache steps produce most of the false hits we see, because a human types the key. Keying a dependency download cache on the lockfile is fine. Keying build outputs on it restores stale outputs on every commit that leaves dependencies alone.

- uses: actions/cache@v4
  with:
    path: ~/.npm
    key: npm-${{ runner.os }}-${{ hashFiles('package-lock.json') }}
    restore-keys: |
      npm-${{ runner.os }}-

restore-keys is a prefix match that falls back to the most recent similar entry: right for a download cache, which verifies what it finds, and wrong for anything consumed unchecked.

Non-deterministic outputs

A step that embeds the current time writes new bytes every time it runs. That causes no false hits, but each re-execution gives every dependent step a new key, so the cache stops helping exactly where it should. Deterministic outputs deserve an article of their own.

Explaining a miss, or a hit you don't trust

A bare hash explains nothing. Store the manifest next to the key, and diffing two manifests shows which input, variable or compiler differed. Bazel's execution log (--execution_log_json_file and related flags) exists for this, and Gradle logs the input hashes behind each task's key when run with -Dorg.gradle.caching.debug=true. In a home-grown cache, write the manifest out from day one.

False hits are harder, because nothing looks wrong. The reliable way to catch one is a scheduled from-scratch build with the cache off, compared with what the cache would have served.

A short checklist

• Key on contents, never timestamps.
• Identify toolchains by digest.
• Allowlist environment variables.
• Keep absolute paths out of keys and outputs.
• Sandbox or trace to find undeclared inputs.
• Store manifests to explain misses.
• Compare with a cache-less build regularly.