Designing a correct compile-cache key

A compile cache turns a slow compilation into a fast lookup. You hash everything that goes into building an artifact, and if you've seen that hash before, you return the stored result instead of running the compiler.

What we need from the key is fairly narrow. Two compilations that would produce the same artifact should get the same key, and compilations that would produce different artifacts should get different keys. When that holds, a hit is always a result you'd have computed anyway, and a miss is always work you actually needed to do.

The key can be wrong in two ways, and they aren't equally dangerous. A key that's too specific carries information that doesn't change the output, so two identical compilations end up with different keys and miss each other. That costs you a recompile you didn't need. A key that's too loose leaves out something that does change the output, so two different compilations share a key and the cache returns the wrong artifact. That second failure is obviously worse, the result is incorrect, rather than just slow. Moreover, and perhaps even worse, nobody notices the false positive cache hit.

The v0.5.0 release of kache covers a lot of ground, from Windows support to a reworked release pipeline, we left most of it out of scope for this post, but you can check the changelog here. What we want to focus on in this writing is the subset of special technical interest: the work that went into correcting these two kinds of error. Where the relevant input is visible in the compiler invocation, kache can handle it automatically.

As we'll explain below, there are situations where the input isn't visible at all. Automation doesn't help there, and we fall back to giving the user a configurable switch.

The key maps a compilation to a hash. Too loose collides two different compilations onto one key and returns the wrong artifact; too specific splits one compilation across two keys and forces a needless recompile.

When the key is too specific

The clearest example surfaced when we ran kache across two checkouts of Firefox at different paths and compared their keys. A lot of the divergence came from a flag whose whole purpose is portability.

Builds that care about reproducibility often pass --remap-path-prefix to rustc, or -ffile-prefix-map to clang. These rewrite the absolute source paths that get baked into an artifact, so a binary built under /home/alice/project doesn't carry that directory around in its debug info. The compiled output stops depending on where it was built.

The trouble is where the flag itself ends up. It travels inside RUSTFLAGS, which kache hashes, and its value contains the full path on the left-hand side, as in --remap-path-prefix=/home/alice/project=.. So a flag meant to remove the build path from the output was quietly putting it back into the key. It was due to this flag that two developers compiling identical code in different directories got different keys and never shared a cache hit. We now replace the absolute path with a sentinel before hashing to create the key, so the two hash the same while a genuinely different target still changes the key.

A related leak turned up in C and C++ compilation. When you run something like clang foo.c, you aren't really invoking the compiler directly, you're invoking a driver. The driver works out the platform defaults, the system include and library paths, and a long list of low-level flags you don't need to type, then hands all of that to its internal frontend as a single, much longer command. That expanded command is the -cc1 line, and running cc -### prints it without compiling anything. kache hashes this fully resolved invocation rather than the short one the user types, because the -cc1 line captures codegen settings the friendly command line hides. That resolved line is full of absolute paths: include directories, the output path, -D defines that embed paths. We were already normalizing the preprocessed source through the same path sentinels but not these tokens, which left half the key portable and half of it tied to the build location. Sending the resolved tokens through the same normalization fixed it.

Lastly, the trickiest case was generated source. Build systems like the one used in Firefox produce unified and generated .cpp files that live inside the build directory rather than in the source tree. kache derives its path sentinel from the common ancestor of the working directory and the source file, which for an ordinary compile is the repo root. However, when the source file sits in the build directory, the working directory and the source are both deep inside the objdir (the build directory), the common ancestor collapses to some narrow subdirectory, and absolute paths above it find their way back into the key. The repo root is still reachable from another signal, though: the -I include directories point back up into the source tree, so kache now grabs the information from there.

Before, the per-checkout path rides into the key and the two checkouts diverge. After, the path is replaced by a sentinel before hashing, so identical code at different paths produces the same key.

When the key is too loose

The other kind of error is harder to catch, because a too-specific key shows up as a slow build while a too-loose key gives no signal at all. It just occasionally returns the wrong object.

We went looking for these on purpose, auditing the rustc invocation for inputs that change the compiled output but weren't part of the key. Some stood out. --sysroot decides which standard library the crate links against, so the same compiler with a different sysroot could compile against a different std and still produce the same key. The -L and -l native link flags that build scripts emit are passed directly on the command line rather than through RUSTFLAGS, so a -sys crate relinked against a different native library kept its old key. A custom --target JSON specification was keyed by its file path but not its contents, so editing the spec in place looked like an unchanged build.

These flags are the sort of input we tend to overlook until a wrong artifact comes back, which is why we went hunting for them. All of them are now fed into the key, and the change bumps the key version so older entries built without them are dropped instead of trusted.

What the cache can't observe

Both of the fixes above rely on the input being somewhere kache can see it, in the flags, the resolved compiler line, or the dependency information rustc reports. The remaining cases are the ones where the input isn't visible from the invocation at all, and the hashing just does not see them.

One of the sources is the files the compiler reads on its own. A procedural macro is ordinary Rust code running inside the compiler, and it can open whatever files it wants. One of the examples we bumped into was sqlx's query! macro. It reads its offline query cache from .sqlx/ during compilation and generates code from it. rustc doesn't report that read, because it has no way to know the macro performed it, so kache never becomes aware that the JSON is an input. Edit the query cache and the source stays the same, the dependency information stays the same, the key doesn't move, and the cache (wrongly) returns a binary built from the old schema. rustc does offer an API for a macro to declare these reads, but it's been unstable for years, so libraries that need to run on stable Rust can't rely on it. That leaves the build tool as the only place to fix it. kache now lets a crate list the missing files in a co-located kache.toml, hashes their contents, and folds the result into that crate's key, so editing one of them produces a clean miss.

The other source is the toolchain beneath the compiler. kache keys on what the compiler reports about itself, including its version banner. The problem here is that this covers changes the compiler announces, but it doesn't cover a glibc bump or a swapped linker. The output changes and nothing kache can observe does. On Nix this fails in a particularly unpleasant way, where a nixpkgs bump followed by a garbage collection leaves a cached binary pointing at an interpreter that no longer exists, which cargo clean won't fix because the key never changed. For this, we made kache support a salt, an opaque string the user can tuck into every key and changes when the toolchain moves underneath it, ideally derived from the toolchain itself so it updates on its own.

We don't enable either of these by default. Inferring an unobservable input would mean inventing dependencies that aren't really there, which would cost hit rate for every user to cover a case most builds don't have. So both are opt-in, and both are built to fail toward a miss: a bad extra_inputs glob or an out-of-date salt can only cost you a needless recompile, not a wrong artifact.

Observable inputs flow into the key automatically. The two unobservable inputs only reach it through an opt-in switch the user sets by hand.

Where this leaves the key

The approach has been the same throughout. When kache can see an input, it should key on it correctly, no matter whether that means dropping noise that causes false misses or capturing something real that would otherwise cause a wrong hit. When an input can't be seen from the compiler invocation, we'd rather expose some configuration option, and arrange things so the cost of getting it wrong is a slower build instead of a broken one. For a compile cache, almost everything comes back to whether the key tells the truth about the compilation, which, as you can see, has its own set of difficulties.