Design a stable build cache keys policy: inputs, stateless rules, and hashing.
- User
Design a stable build cache keys policy: inputs, stateless rules, and hashing.
- Assistant
We are designing a stable build cache keys policy. The goal is to define what inputs (dependencies) should be considered for generating a cache key, how to handle stateless rules (i.e., rules that don't produce outputs that are stored in the cache), and how to hash the inputs to create a stable key.
Key principles:
- Stability: The same set of inputs should always produce the same cache key, regardless of the order of files, timestamps, etc.
- Reproducibility: If the inputs haven't changed, the build should be cacheable.
- Sensitivity to changes: If any input that affects the output changes, the cache key should change.
Steps:
-
Identify the inputs (dependencies) for the build step. These typically include:
- Source files (code, configuration, etc.)
- Environment variables (that affect the build)
- Build tool version (e.g., compiler version, build system version)
- Dependencies (libraries, etc.) with their versions
- Build flags and options
-
Handle stateless rules: In some build systems, there are rules that don't produce outputs that are stored in the cache (e.g., a rule that only does validation or generates intermediate files that are not cached). We need to decide if such rules should be included in the cache key or if they should be executed every time. Typically, if a rule is stateless and its output is not cached, then it should not be part of the cache key because it doesn't produce a cacheable artifact. But note: if the rule's output is used by subsequent steps, then we must consider its input for the cache key of the dependent steps.
-
Hashing strategy:
- We want to avoid using timestamps or other non-reproducible data.
- We should use a content-based hash (like SHA256) of the actual content of the files, not their modification times.
- For directories, we can hash the list of files and their individual hashes in a deterministic order (e.g., sorted by path).
- For environment variables, we can sort them by name and then hash the concatenation of "key=value" pairs.
- For build flags, we should use a canonical representation (e.g., sorted order) to avoid order dependency.
-
Implementation considerations:
- We need to define a function that takes the set of inputs and produces a hash.
- The hash should be deterministic: same inputs -> same hash.
- The hash should be sensitive to any change in the inputs.
Let's break down the inputs:
a) File-based inputs: - We can compute a hash for each file (using a cryptographic hash of the content). - For a directory, we can compute the hash as: hash = hash_function( sorted list of (relative_path, file_hash) for all files in the directory ) - We must be cautious about symlinks: either follow symlinks and hash the target content, or treat the symlink as a file with its path and target? This depends on the build system. Usually, we want to follow symlinks because the content of the target matters.
b) Environment variables: - Only include the ones that are known to affect the build. Alternatively, we can have a whitelist or blacklist. - Sort by variable name to avoid order issues. - For each variable, we can hash the value (or the entire string "key=value") and then combine.
c) Build tool versions: - We can include the version string (e.g.,
gcc --versionoutput) as a string in the hash.d) Dependencies: - If dependencies are managed by a package manager (like npm, pip, etc.), we might use the lock file (package-lock.json, requirements.txt, etc.) as the input. - Alternatively, we can use the hash of the dependency specification (e.g., the content of the lock file or the set of dependencies with their resolved versions).
e) Build flags and options: - We can take the command line arguments (or the relevant subset) and sort them to avoid order dependency. But note: sometimes order matters (e.g., in linker flags). So we must be cautious. Alternatively, we can use the exact command line if order is known to matter.
-
Stateless rules:
- If a rule does not produce an output that is stored in the cache (i.e., its output is not used as a cacheable artifact in subsequent steps), then we do not need to include its output in the cache key. However, if the rule's output is used by a cacheable step, then the rule's inputs are already part of the cache key of the dependent step (because the dependent step's inputs include the rule's output? wait, no: if the rule's output is not cached, then it is not stored and must be regenerated. But then the dependent step would use the freshly generated output. So we have to ensure that the rule's inputs are part of the cache key of the dependent step? Actually, if the rule is run every time, then the dependent step's input (the output of the rule) is always fresh. So we don't need to cache the rule's output, but we must run the rule every time. However, if the rule's output is not used by any cacheable step, then it's fine.
But note: if the rule is part of the same build graph and its output is used by a cacheable step, then the cacheable step's cache key must be invalidated when the rule's input changes. So the rule's input must be part of the cache key of the dependent step. However, if the rule is stateless and we are not caching its output, then we don't have a stored artifact for the rule. Therefore, the dependent step must run the rule every time (or at least when the rule's input changes). But then the dependent step's cache key must include the rule's input so that when the rule's input changes, the dependent step's cache key changes and the step is re-run.
In summary, for a cacheable step (that produces an output we cache), we must include:
- All direct inputs (source files, etc.)
- The outputs of any prerequisite steps (if those outputs are cached, then we include the cache key of the prerequisite step? or the content?).
Actually, in a build system like Bazel or Buck, they use a technique called "action key" which is a hash of:
- The command (with arguments) and the environment.
- The content hashes of all declared inputs (including the outputs of prerequisite actions?).
But note: if we have a rule that produces an output that is used by another rule, then the second rule's cache key should include the first rule's output content (or the first rule's cache key). However, if the first rule is not cached (stateless and not cacheable), then we don't have a stored output for the first rule. So the second rule must depend on the first rule's output file (which will be regenerated every time). Then the second rule's cache key must include the content of that file? But then we are including the content of a file that is generated by a rule that is not cached. That's okay because we are hashing the content. However, if the first rule's input changes, the generated file changes, and then the second rule's cache key changes.
So the policy for a cacheable step is: include the content of all input files (whether they are source files or generated files from prerequisite steps). But note: if a prerequisite step is cacheable, then we can use the cache key of that step as a representation of its output (to avoid hashing large outputs). But if the prerequisite step is not cacheable, then we must hash its output file (which we have to generate first).
However, in a system that supports caching, we might want to avoid generating the output of a non-cacheable step just to hash it for the cache key of the next step. That would be inefficient. Therefore, we might want to make the non-cacheable step's output part of the cache key of the dependent step? But then we are forced to run the non-cacheable step to get the content? Alternatively, we can have the non-cacheable step's cache key be based on its inputs, and then the dependent step uses that cache key? But if the non-cacheable step is not cached, then its cache key is not stored. So we are stuck.
Let's re-think: In a typical build system, every step (rule) has an action that produces outputs. The cache key for that action is computed from:
- The action's configuration (command, environment, etc.)
- The content hashes of all declared inputs (which may include the outputs of other actions?).
But if we have a DAG of actions, then the cache key of an action that depends on another action's output should include the cache key of the prerequisite action? Or the content of the output? Both are equivalent if the prerequisite action is cacheable and we have stored its output. But if the prerequisite action is not cacheable, then we don't store its output, but we still have to run it to get the output. Then the dependent action's cache key must be computed after running the prerequisite action? That would break the ability to compute the cache key without running the action.
Therefore, it is common to require that all inputs to a cacheable action are either source files or the outputs of cacheable actions. If an action depends on a non-cacheable action, then the non-cacheable action must be run every time, and its output must be considered as an input to the cacheable action. But then the cacheable action's cache key must include the content of that output. However, to compute that hash we must have the content, which requires running the non-cacheable action. So we have to run the non-cacheable action first (every time) and then compute the cache key for the cacheable action.
This is acceptable if the non-cacheable action is fast and the cacheable action is expensive. But it might be inefficient if the non-cacheable action is expensive and the cacheable action is cheap? Then we might want to cache the non-cacheable action's output? But we said it's not cacheable because it's stateless? Actually, if it's stateless and its output is only used by one downstream action, then we can cache it as part of the downstream action? But then we are caching an intermediate.
Alternatively, we can change the design: make every action cacheable? But sometimes we have actions that are not safe to cache (e.g., they have side effects, or they depend on non-reproducible factors). Then we cannot cache them.
Given the complexity, let's assume we are designing for a system where:
- All actions that produce outputs that are used by cacheable actions must be cacheable? Not necessarily.
We can define:
- An action is cacheable if its output can be stored and reused.
- An action is stateless if it does not produce an output that is stored in the cache (or it produces an output that is not used by any cacheable action?).
But the problem says "stateless rules". In Bazel, a rule can be "starlark" and can be marked as
output_to_genfilesor not, and can be cached or not. But we are designing a policy.Let's simplify:
We will design the cache key for a cacheable action (rule) as:
cache_key = hash( command + environment + sorted list of (input_path, file_hash) for all declared inputs (including source files and outputs of prerequisite actions) )
But note: if an input is the output of a prerequisite action, then we need to get its file_hash. If the prerequisite action is cacheable, we can get its output from the cache (so we don't run it again) and then hash it. If the prerequisite action is not cacheable, then we must run it (every time) to get the output and then hash it.
This leads to:
- For a cacheable action, all its inputs must be available (either from cache or by running the prerequisite non-cacheable actions).
Now, how do we handle the case where a non-cacheable action produces an output that is used by multiple cacheable actions? We would run the non-cacheable action once and then use its output for all dependent cacheable actions? That's efficient.
But note: the non-cacheable action might be run multiple times if it is a dependency of multiple cacheable actions and we don't cache it? We can run it once and then reuse the output for all dependent actions in the same build? That's a separate issue (incremental build within one build). We are concerned with caching across builds.
So for the purpose of cache key generation, we need to consider:
- The set of inputs to the cacheable action, which includes the output of the non-cacheable action. But we don't have the non-cacheable action's output until we run it. So we must run the non-cacheable action in order to compute the cache key of the cacheable action? That seems inefficient.
Alternatively, we can define the cache key of the non-cacheable action as a function of its inputs (without running it). Then the cacheable action can use that cache key (which is a hash of the non-cacheable action's inputs) as a representation of the non-cacheable action's output. But that is only valid if the non-cacheable action is deterministic and its output is a pure function of its inputs. Then we can say:
cache_key(cacheable_action) = hash( command, environment, for each input: if input is from a non-cacheable action, then use cache_key(non_cacheable_action) else if input is a source file, then file_hash )
But wait: if the non-cacheable action is deterministic, then we can compute its output hash without running it? Not necessarily, because the non-cacheable action might be complex (e.g., a script). We would have to run it to get the output? But if we can compute the output hash without running it, then we can avoid running it. That's the whole point of caching.
However, if the non-cacheable action is not cached, then we cannot rely on having its output stored. But we can run it every time? Then we run it and then use its output as input to the cacheable action. Then we compute the cache key of the cacheable action by hashing the output of the non-cacheable action (which we just generated). But then we are running the non-cacheable action every time, which is what we wanted to avoid? No, we don't want to avoid it because it's not cacheable. We are okay with running it every time.
So the process for a cacheable action that depends on a non-cacheable action:
Step 1: Run the non-cacheable action (every time) to generate its output. Step 2: Compute the cache key for the cacheable action by hashing: - The command and environment of the cacheable action. - The hashes of all its input files (including the file generated by the non-cacheable action).
This means that the non-cacheable action must be run before we can compute the cache key of the cacheable action. But note: if the non-cacheable action's input changes, then its output changes, and then the cacheable action's cache key changes. That's correct.
But if the non-cacheable action's input hasn't changed, then its output is the same as last time? Not necessarily, because the non-cacheable action might not be deterministic? But if it's not deterministic, then we cannot cache the cacheable action either? Because the input (the output of the non-cacheable action) would be different even if the inputs to the non-cacheable action are the same? Then we have a problem.
Therefore, for a cacheable action to be safely cacheable, all its inputs (including the outputs of non-cacheable actions) must be deterministic functions of their own inputs. Otherwise, the cache key would not be stable.
So we must assume that non-cacheable actions are deterministic. If they are not, then we cannot cache any action that depends on them.
Given that, we can compute the cache key of a non-cacheable action as the hash of its own inputs (command, environment, and its input files). Then the output of the non-cacheable action is a deterministic function of its inputs. Therefore, the hash of the output (which we would get by running it) is also a deterministic function of the non-cacheable action's cache key? Not exactly: the output might be a complex function, but if it's deterministic, then the output hash is a function of the non-cacheable action's cache key? Not necessarily: two different sets of inputs to the non-cacheable action might produce the same output? That's unlikely if we use a good hash. But we don't need to know the output hash without running the non-cacheable action. We just need to run it and then hash the output.
However, if we want to avoid running the non-cacheable action when we are only computing the cache key (for example, to check if we have a cached output for the cacheable action without running any prerequisites), then we would need to know the output hash of the non-cacheable action without running it. That is only possible if the non-cacheable action's output hash is a deterministic function of the non-cacheable action's cache key. But we don't have that function.
Therefore, in practice, we must run the non-cacheable action to get its output and then hash that output for the cacheable action's cache key. This means that for every build, we must run all non-cacheable actions that are prerequisites of cacheable actions, even if we are going to use a cached version of the cacheable action? That defeats the purpose of caching because we are running the non-cacheable action every time.
So we have two options:
Option 1: Do not allow cacheable actions to depend on non-cacheable actions. Then we can compute the cache key without running any actions (only by hashing source files and other cacheable actions' cache keys). This is clean and efficient.
Option 2: Allow cacheable actions to depend on non-cacheable actions, but then we must run the non-cacheable actions every time (to get their outputs) to compute the cache key of the cacheable action. This might be acceptable if the non-cacheable actions are cheap and the cacheable actions are expensive, so that we run the non-cacheable actions every time but then we can skip the expensive cacheable action if the cache key matches.
But note: if the non-cacheable action is expensive, then we are running it every time and then possibly skipping the cacheable action? That's still running the expensive non-cacheable action every time. So we might as well not cache the cacheable action at all? Not exactly: if the non-cacheable action's output is the same as last time, then the cacheable action's output is the same and we can skip it. But we still ran the non-cacheable action.
Therefore, the best practice is to make every action cacheable if possible. But if an action must be non-cacheable (e.g., it has side effects, or it depends on non-reproducible factors), then we should not have cacheable actions depend on it? Or we accept that the non-cacheable action will run every time.
Given the problem, we are asked to design a policy for stable build cache keys. We are not asked to design the entire build system. So we can state:
-
For a cacheable action, the cache key is computed from:
- The action's command and environment (with a canonical representation, e.g., sorted environment variables, and the command exactly as run).
- The content hashes of all input files (including the outputs of prerequisite actions, whether they are from cacheable or non-cacheable actions). For non-cacheable actions, we must have the output file available (by running the non-cacheable action) to compute the hash.
-
However, if a non-cacheable action is a prerequisite, then we must run it to get its output, and then we can compute the cache key of the dependent cacheable action. But note: the non-cacheable action's output might be large, so we are hashing a large file. That could be expensive.
Alternatively, we can use the non-cacheable action's own cache key (based on its inputs) as a representation of its output? But that is not the same as the output content hash. Two different sets of inputs to the non-cacheable action could produce the same output? That's a collision. But if the non-cacheable action is deterministic, then the output is a function of the inputs. So if we have the same inputs, we get the same output. Therefore, the output hash is a function of the non-cacheable action's cache key? Not exactly: the non-cacheable action's cache key is a hash of its inputs. The output is a function of the inputs. So if we have the same non-cacheable action's cache key, we have the same inputs, so the output is the same. Therefore, we can use the non-cacheable action's cache key as a proxy for the output content? But note: the output content might be large, and we don't want to store the entire output in the cache key of the dependent action. Also, the non-cacheable action's cache key is a fixed-size hash, so it's efficient.
So we can do:
For a cacheable action that depends on a non-cacheable action, we use the cache key of the non-cacheable action (which is a hash of its own command, environment, and input files) as the representation of the non-cacheable action's output.
But wait: what if the non-cacheable action produces multiple outputs? Then we would need to hash all of them? But we are using the non-cacheable action's cache key, which is a single hash. That single hash must represent all the outputs? That's only valid if the non-cacheable action's outputs are all deterministic functions of its inputs, and we are okay with using the non-cacheable action's cache key (which is a hash of the inputs) as a proxy for all outputs. But note: two different sets of inputs might produce the same output for one file but different for another? Then the non-cacheable action's cache key (which is a hash of the inputs) would be different? Actually, if the inputs are different, the non-cacheable action's cache key is different. So it's safe.
However, the non-cacheable action's cache key does not directly depend on the content of the outputs. It depends on the inputs. So if the non-cacheable action's inputs are the same, then the non-cacheable action's cache key is the same, and we assume the outputs are the same. That is only true if the non-cacheable action is deterministic. So we must require that non-cacheable actions are deterministic.
Then, for a cacheable action, we can have:
cache_key = hash( command, environment, sorted list of (input_path, if input is from a non-cacheable action: cache_key_of_non_cacheable_action else: file_hash_of_input_file ) )
But note: if the input is from a cacheable action, we could also use the cacheable action's cache key? That would be more efficient because we don't have to hash the output file (which might be large). But then we are relying on the cacheable action's cache key to represent its output. That is safe because the cacheable action's output is a deterministic function of its inputs (which are already hashed in its cache key). So we can use the cache key of the prerequisite action (whether cacheable or not) as the representation of the output.
Therefore, we can design:
For any action (cacheable or not), we compute an action cache key that is a hash of: - The action's command (with arguments) and environment (canonicalized). - The cache keys of all its input actions (if the input is produced by another action) or the file hash of the input file (if it's a source file).
Then, for a cacheable action, we store the output files in the cache under that action's cache key.
For a non-cacheable action, we don't store the output in the cache, but we still compute its cache key (so that dependent actions can use it).
This way, we avoid having to hash large output files for the cache key of dependent actions. We only hash the cache keys of the prerequisite actions (which are fixed-size) and the source files.
But note: what if the same source file is used by multiple actions? We hash the file once and then reuse the hash? That's fine.
How about the case where an action has multiple outputs? The cache key is the same for all outputs of the same action? Yes, because the action is defined by its command and inputs, and it produces a set of outputs. We store all outputs under the same cache key.
Now, what about stateless rules? In this design, a stateless rule (non-cacheable) does not store its output in the cache, but it still has a cache key (based on its inputs) that is used by dependent actions. So it's not completely ignored.
However, if a rule is truly stateless (i.e., it doesn't produce any output that is used by any other rule), then it doesn't affect any cache key and we don't need to run it for caching purposes? But it might have side effects (like printing a warning) that we want to run every time. Then we run it every time, but it doesn't affect cache keys.
So the policy:
-
Every action (rule) has an action cache key computed from:
- The action's command (with arguments) and environment (canonicalized).
- For each declared input:
- If the input is a source file (or a file that is not produced by any action in the build), then use the file's content hash.
- If the input is produced by another action (say, action X), then use the cache key of action X.
-
The canonicalization of command and environment:
-
For the command: we use the exact command line as a string? But note: the same command can be written in different ways (e.g.,
-I/includevs-I /include). We need a canonical representation. This is tool-specific. We might rely on the build system to provide a canonical command string? Alternatively, we can split the command into arguments and sort the arguments that are known to be order-independent? This is tricky. -
For environment: we can sort the environment variables by name and then concatenate "key=value". We must also decide which environment variables to include. We should include only the ones that are known to affect the build. We can have a whitelist or blacklist.
-
-
For source files: we use a cryptographic hash (e.g., SHA256) of the file content.
-
For directories: we treat them as a set of files. We can compute a hash for the directory by:
- Listing all files recursively (with relative paths from the directory root).
- Sorting the list by the relative path.
- For each file, compute its file hash (as above).
- Then compute the hash of the concatenation of (relative_path + file_hash) for each file? Or we can do: hash = hash_function( "DIR", sorted( (rel_path, file_hash) for each file ) )
-
For other types of inputs (like symlinks): we can hash the symlink target (as a string) and the symlink path? Or we can follow the symlink? We should follow symlinks because the content of the target is what matters.
-
For actions that are not cacheable (stateless rules): we still compute their action cache key (as above) but we do not store their outputs in the cache. They are run every time. However, their cache key is used by dependent actions.
-
For cacheable actions: we store the output files in the cache under the action's cache key. When we run the build, we compute the cache key for every action (in dependency order). For each action, we check if we have a cached output for that action's cache key. If we do, we use the cached output. Otherwise, we run the action and then store the output in the cache (if the action is cacheable).
-
Note: If an action has multiple outputs, we store all of them in the cache under the same cache key (maybe as a tar ball or a directory). When we retrieve from cache, we get all the outputs.
-
If an action is not cacheable, we run it every time, but we still compute its cache key (for the benefit of dependent actions). However, note that if the non-cacheable action's inputs haven't changed, then its output will be the same as last time? Not necessarily, because the non-cacheable action might not be deterministic? But we require that non-cacheable actions are deterministic? Otherwise, we cannot rely on the cache key of dependent actions.
So we must require that all actions (cacheable or not) are deterministic with respect to their inputs (command, environment, and input files). Otherwise, caching would be incorrect.
But note: some actions might be non-deterministic (e.g., they embed timestamps). Then we must either: - Make them deterministic (by removing timestamps, etc.) - Or mark them as non-cacheable and also not allow any cacheable action to depend on them? Because if a cacheable action depends on a non-deterministic action, then the cacheable action's output might change even if the non-deterministic action's inputs are the same.
Therefore, we can state:
Only deterministic actions can be cacheable. Non-deterministic actions must be marked as non-cacheable and must not be used as inputs to cacheable actions? Actually, if a non-deterministic action is used as input to a cacheable action, then the cacheable action's cache key would be based on the non-deterministic action's cache key (which is based on its inputs). But if the non-deterministic action's output is different every time even with the same inputs, then the cacheable action's input (the output of the non-deterministic action) is different, so the cacheable action's cache key would be the same? Because the non-deterministic action's cache key is the same (same inputs) but the output is different. Then the cacheable action would use the same cache key and get the same cached output, which would be incorrect because its input (the non-deterministic action's output) is different.
So we must require that if an action is used as an input to a cacheable action, it must be deterministic. And if it is not deterministic, then we cannot allow it to be used as an input to a cacheable action.
How do we enforce this? We can have a rule that:
- An action that is a prerequisite for a cacheable action must be cacheable? Not necessarily: it can be non-cacheable but deterministic. But then we are running it every time (because it's non-cacheable) and then using its output as input to the cacheable action. That is safe because the output is deterministic.
But note: if the non-cacheable deterministic action is run every time, then we are computing the same output every time (if inputs are the same). Then the cacheable action's input is the same, so the cacheable action's cache key (which includes the cache key of the non-cacheable action) is the same. Then we can use the cached output of the cacheable action. That's correct.
However, if the non-cacheable deterministic action's inputs change, then its output changes, and then the cacheable action's cache key changes (because the cache key of the non-cacheable action changes). Then we run the cacheable action and cache the new output.
So it works.
But what if the non-cacheable deterministic action is expensive and we run it every time? That's the cost of having a non-cacheable action. We cannot avoid running it every time because we don't cache its output. But then we are running it to get the output to compute the cache key of the cacheable action? Actually, we don't need the output to compute the cache key of the cacheable action. We only need the cache key of the non-cacheable action. And the cache key of the non-cacheable action is computed from its own inputs (without running it). So we don't need to run the non-cacheable action to compute the cache key of the cacheable action? Wait, we said we use the cache key of the non-cacheable action. That cache key is computed from the non-cacheable action's inputs (command, environment, and its input files). So we don't need to run the non-cacheable action to get its cache key. Then we can compute the cacheable action's cache key without running the non-cacheable action? That would be ideal.
But then, when we go to run the cacheable action (if cache miss), we need the output of the non-cacheable action. So we run the non-cacheable action to get its output, then run the cacheable action. But note: the non-cacheable action is run every time (even if we have a cache hit for the cacheable action)? Because we need its output as input to the cacheable action? Actually, if we have a cache hit for the cacheable action, we don't run the cacheable action, but we still need the non-cacheable action's output? Because the cacheable action's output (from the cache) was produced using a specific output of the non-cacheable action. If we don't run the non-cacheable action, we don't have that output. But the cacheable action's output from the cache might have been produced with a different version of the non-cacheable action's output? No, because the cache key of the cacheable action includes the cache key of the non-cacheable action. So if the non-cacheable action's inputs are the same, then its cache key is the same, and then the cacheable action's cache key is the same. So if we have a cache hit for the cacheable action, we know that the non-cacheable action's inputs are the same as the last time we built the cacheable action. But we don't have the non-cacheable action's output from the last build? We only have the cacheable action's output. We need the non-cacheable action's output because it might be an input to the cacheable action? Actually, the cacheable action's output is stored in the cache, but the non-cacheable action's output is not stored (because it's non-cacheable). So when we restore the cacheable action's output, we don't have the non-cacheable action's output. But the cacheable action's output might have been built using a specific version of the non-cacheable action's output. If the non-cacheable action's output is not stored, then we cannot reproduce the cacheable action's output? Actually, we don't need to reproduce the non-cacheable action's output because we are not running the cacheable action. We are just using the cached output of the cacheable action. But the cached output of the cacheable action might be invalid if the non-cacheable action's output is different? But we know that the non-cacheable action's cache key is the same, so its output should be the same (if deterministic). So we don't need to have the non-cacheable action's output to use the cacheable action's output? The cacheable action's output is stored and we use it directly. But what if the non-cacheable action's output is a file that is read by the cacheable action during its execution? Then the cacheable action's output might depend on the non-cacheable action's output. But if the non-cacheable action's cache key is the same, then its output is the same, so the cacheable action's output is valid. We don't need the non-cacheable action's output to use the cacheable action's output? Actually, the cacheable action's output is stored and we use it. We don't need the non-cacheable action's output unless we run the cacheable action again. So it's okay.
However, if the non-cacheable action's output is needed by something else (e.g., by another action that is not cached, or by the final product), then we must run the non-cacheable action to generate that output. So in a build, we must run every action that produces an output that is needed (whether cached or not). The caching is about reusing the output of cacheable actions across builds.
So the process for a build:
We have a DAG of actions. We compute the cache key for every action (in dependency order). For each action:
If the action is cacheable and we have a cached output for its cache key, then we use the cached output and skip running the action. Otherwise, we run the action (and if it's cacheable, we store the output in the cache).For non-cacheable actions, we always run them.
But note: when we run an action, we need its inputs to be available. If an input is the output of a prerequisite action, we must have that output available (either from cache or by running the prerequisite).
So we must run the prerequisite actions first.
Therefore, the cache key computation is separate from running the action. We can compute the cache key without running the action (as long as we have the cache keys of the prerequisite actions and the hashes of the source files). But for non-cacheable actions, we run them every time, so we don't care about their cache key for skipping, but we need their output for dependent actions.
But wait: we said we use the cache key of the non-cacheable action in the cacheable action's cache key. So we must compute the non-cacheable action's cache key. And that is computed from its inputs (without running it). So we can compute the non-cacheable action's cache key without running it. That's good.
So the algorithm:
For every action in the build DAG (in topological order):
Compute the action's cache key as: hash( canonical_command, canonical_environment, sorted list of (input_path, if input is from an action X: cache_key(X) else: file_hash(input_path) ) ) Then, if the action is cacheable and we have a cached output for that cache key, then we use the cached output (and mark the action as up-to-date). Otherwise, we run the action (and if cacheable, store the output in the cache). For non-cacheable actions, we run them unconditionally.Note: when running an action, we must have all its inputs available. If an input is from a cacheable action that we had a cache hit for, then we have its output from the cache. If an input is from a non-cacheable action, then we must have run that non-cacheable action already (because we are in topological order) and we have its output.
This design requires that we can compute the cache key of an action without running it (except that for non-cacheable actions we run them every time, but we don't need their output to compute their cache key). That's good.
Now, what about the case where an action has multiple outputs? We store all outputs under the same cache key. When we restore from cache, we get all the outputs.
What about the case where an action's output is used by multiple actions? Then the cache key of the dependent actions will include the cache key of the producing action. That's fine.
Now, let's address the "stateless rules" in the problem. In our design, every rule (action) has a cache key, but only cacheable rules store their outputs. Stateless rules (non-cacheable) do not store outputs, but they still have a cache key that is used by dependent rules.
So the policy:
-
Inputs:
- For source files: use the file's content hash (with symlinks followed).
- For directories: recursively hash the list of files (sorted by path) with their hashes.
- For environment variables: use only the ones that affect the build, sorted by name, and hash the concatenation of "key=value".
- For command: use a canonical representation (e.g., the exact command line as a string, but we must ensure that equivalent command lines are represented the same). This is tool-specific. We might rely on the build system to provide a canonical command string, or we can split the command into argv and sort the arguments that are known to be order-independent? This is hard. Alternatively, we can use the command as a string and assume that the build system generates the same string for the same command.
-
Stateless rules: They are non-cacheable. They are run every time. Their cache key is computed from their inputs (as above) but their outputs are not stored. Their cache key is used by dependent cacheable actions.
-
Hashing:
- We use a cryptographic hash function (like SHA256) for the entire cache key computation.
- The cache key for an action is computed as:
H(
canonical_command ||
canonical_environment ||
sorted_list_of_inputs
)
where:
- canonical_command: a string representing the command in a canonical form.
- canonical_environment: a string of sorted environment variables of the form "key=value", one per line? Then we can hash the entire string.
- sorted_list_of_inputs: for each input, we have a tuple (input_path, input_hash). We sort the tuples by input_path (lexicographically). Then we concatenate the input_path and input_hash (as strings) for each tuple, and then concatenate all of them? Then hash the concatenation.
But note: the input_hash for a source file is the file's content hash (a fixed-size string). For an input that is the output of an action, the input_hash is the cache key of that action (which is also a fixed-size string).
We must be cautious about the concatenation: we need to avoid collisions. We can use a structured format, like:
For each input: encode the input_path (as UTF-8 string) then a delimiter (e.g., 0x00) then the input_hash (as raw bytes or as a hex string?). Then we concatenate all of them, and then hash.Alternatively, we can use a hash function that can take multiple inputs (like a Merkle tree). But for simplicity, we can do:
cache_key = SHA256( SHA256(canonical_command) || SHA256(canonical_environment) || for each input in sorted order: SHA256(input_path) || input_hash )But that's multiple hashes. We can just do:
data = canonical_command + canonical_environment for each input in sorted order: data += input_path + input_hash (with some delimiter to avoid ambiguity) cache_key = SHA256(data)We must ensure that the delimiter is unique and not appearing in the paths or hashes. We can use a non-printable character, or we can encode the path and hash in a way that is reversible? Actually, we don't need to reverse. We just need to avoid two different sets of inputs producing the same concatenated string.
Example: input1: path="a", hash=1234 input2: path="b", hash=5678
We can do: "a\0" + "1234" + "b\0" + "5678"But what if a path contains a null? We can use a different delimiter, or we can encode the path and hash in a length-prefixed way.
Alternatively, we can use a canonical serialization format like:
For each input: write the length of the path (as a varint) then the path (as bytes) write the length of the hash (as a varint) then the hash (as bytes) Then concatenate and hash.But that's more complex. Since we are using a cryptographic hash, we can just use a delimiter that is not allowed in paths (like 0x00) and hope that paths don't contain null. But in some systems, paths can contain any byte except 0? Actually, in Unix, paths are null-terminated strings, so they don't contain null. So we can use null as a delimiter.
However, we are also using the hash as a string (hex). We can use the raw bytes of the hash (which are 32 bytes for SHA256). Then we can do:
data = canonical_command (as bytes) + canonical_environment (as bytes) for each input in sorted order by path (as bytes): data += path_bytes + 0x00 + hash_bytes cache_key = SHA256(data)But note: the canonical_command and canonical_environment are strings. We must encode them to bytes consistently (e.g., UTF-8).
Given the complexity, we might rely on the build system to provide a canonical representation of the command and environment. But we are designing the policy, so we have to specify.
Alternatively, we can define:
cache_key = hash( command_string, environment_string, sorted_list_of_inputs ) where: command_string: the exact command line as a single string, but with environment variables expanded? Or the command as an array of arguments? We should use the array of arguments (as strings) and then sort the ones that are order-independent? This is very tool-specific. Given the difficulty, we might say: The build system must provide a canonical representation of the command and environment. We assume that the build system will produce the same string for the same logical command. But then we are not designing the hashing, we are relying on the build system.Given the problem, we are to design the policy. We can say:
The cache key is computed as a cryptographic hash (SHA256) of a canonical serialization of:
- The command (as an array of strings) and the environment (as a sorted list of key-value pairs). - The set of input files, each represented by a tuple (path, type, hash), where: * path: relative path from the workspace root (or absolute? but we want to avoid absolute paths because they are machine-specific). We should use relative paths within the build context. * type: is it a file or a directory? Actually, we don't need type because we are hashing the content. For a directory, we recursively list all files. * hash: for a file, the SHA256 of the file content (following symlinks). For a directory, the hash of the directory structure (as described above).And for inputs that are produced by other actions, we use the cache key of that action (which is a SHA256 hash) as the hash.
The serialization must be deterministic: - Sort the environment variables by key. - Sort the input list by the path (as strings, using a consistent locale and encoding? We should use byte-wise comparison? We can sort by the raw bytes of the path, which is deterministic if we use the same encoding (UTF-8). But note: on case-insensitive file systems, two paths that differ only in case are the same? We are hashing the content of the files, so if two paths point to the same file (via symlink or case-insensitivity) then we might have duplicates? We must decide: the build system should present a normalized view of the file system? We assume that the build system provides a set of input files with their absolute paths (or relative to a fixed root) and we use the path as given? But if the same file is reachable by two different paths, then we have two inputs? That would be a problem. So we must deduplicate by the real path (after following symlinks and resolving case?).
This is getting very complex.
Given the complexity, we might rely on the build system to provide a set of input files that are unique (by their real path) and then we use the real path (canonicalized) as the path in the cache key.
So we define:
For each input file (or directory), we canonicalize the path: - Resolve symlinks (follow them to the real file). - On case-insensitive systems, we might want to use a canonical case? But that's tricky. We can use the real path as returned by the system (which might be in a particular case). We should use the absolute path with all symlinks resolved and in a consistent case? But on Unix, paths are case-sensitive. On Windows, they are not. So we must be platform-independent.
Alternatively, we can use the inode number (or file ID) to identify files? But that is not portable.
Given the constraints, we might say:
The build system must provide the input files as a set of paths that are unique (by their real path after symlink resolution) and are represented in a canonical way (e.g., absolute path with symlinks resolved, and on case-insensitive systems, we use a consistent case, say lowercase). But this is still tricky.
Perhaps we can avoid this by having the build system (like Bazel) use a content-addressable storage for files? Then the cache key for an action is computed from the digests of the input files (which are content-based and already canonicalized). That is, the build system provides a function that maps a file path to its digest (hash of content). And for a directory, the digest is computed recursively.
Then the cache key for an action is:
H( command_digest, environment_digest, sorted_list_of_input_digests )
where: command_digest = SHA256(canonical_command_string) environment_digest = SHA256(canonical_environment_string) input_digests: for each input, we have a digest. For source files, the digest is the file content hash (computed by the build system). For outputs of other actions, the digest is the action's cache key.
Then we don't need to deal with paths at all? But we need to know which file corresponds to which input? Actually, we don't: the cache key of the action is just a hash of the digests of the inputs. But note: two different sets of files that have the same content (but different paths) would have the same set of digests? If we only use the digest, then we lose the path information. That might be okay if the action doesn't care about the path? But typically, an action might depend on the path (e.g., a compiler might use the file path in error messages, or the output might embed the path). So we must include the path in the cache key? Otherwise, if we change the path of an input file (but keep the content the same), the action might produce a different output (if the path is embedded). Therefore, we must include the path in the cache key.
So we go back to including the path.
Given the above, we define:
For each input (whether a source file or an output of another action), we have a tuple (path, digest). The path is the canonicalized absolute path (with symlinks resolved and in a consistent case). The digest is: - For a source file: the SHA256 of the file content. - For an output of another action: the cache key of that action (which is a SHA256).
Then we sort the tuples by the path (as bytes, using a consistent encoding, e.g., UTF-8) and then concatenate:
data = canonical_command_bytes + canonical_environment_bytes for each tuple (path, digest) in sorted order: data += path_bytes + 0x00 + digest_bytes cache_key = SHA256(data)This should be stable.
Now, about the canonical_command and canonical_environment:
We can define:
canonical_environment: sort the environment variables by key, then for each variable, output "key=value" (with the value exactly as in the environment) and then a newline? But note: the value might contain newlines. So we need a delimiter that is not in the keys or values? We can use a similar approach: for each env var, write the key, then a delimiter (0x00), then the value. Then sort by the key. Similarly, for the command: we have an array of arguments. We can sort the arguments that are known to be order-independent? But that's hard. Instead, we can use the command as an array of strings (in the order provided by the build system) and then serialize as: for each argument, write the length (varint) then the argument bytes. Then we don't need to sort. But note: the same command can be represented in different ways (e.g., `-I/include` and `-I /include` are the same to the compiler? Not necessarily). So we must rely on the build system to generate a canonical command string. Alternatively, we can define that the command is the exact argv array as passed to the execve (or equivalent) system call. Then the order matters and we don't sort. That is the safest: if two command lines are different, they are considered different. But then equivalent command lines (that are semantically the same) might have different cache keys. That's acceptable because we want to cache based on the exact command.So we can do:
canonical_command: the array of arguments (as strings) in the order they are passed. We serialize by writing each argument as a length-prefixed string (with the length as a varint) and then the bytes of the string. Then we concatenate. canonical_environment: sort the environment variables by the key (as bytes, using UTF-8 and byte-wise comparison). For each, write the key (as length-prefixed string), then a delimiter (0x00), then the value (as length-prefixed string)? But note: the value might be empty? We can do: For each env var (key, value): write length of key (varint) write key bytes write length of value (varint) write value bytes Then we have a sequence of these. Since we sort by key, the order is fixed. Then the entire data for the cache key is: data = [serialized command] + [serialized environment] + [for each input in sorted order by path: length of path (varint) + path bytes + length of digest (varint) + digest bytes ] Then cache_key = SHA256(data)This is deterministic.
However, note: the digest for a source file is the SHA256 of the file content, which is 32 bytes. The digest for an action is also a SHA256 (32 bytes). So the digest part is fixed-length? Not necessarily: if we use the raw bytes, it's 32 bytes. But if we use hex string, it's 64 bytes. We should use raw bytes for efficiency.
But wait: the cache key of an action is a SHA256, which is 32 bytes. We are using that as the digest. Then when we concatenate for the parent action, we are using 32 bytes.
So the input digest is always 32 bytes? Then we don't need to store the length? Actually, we do because the path is variable length. But the digest is fixed at 32 bytes? Then we can skip the length for the digest? But then we must know where the path ends and the digest begins. We have a delimiter? We used a delimiter (0x00) in an earlier proposal, but now we are using length-prefixed. We can do:
For the entire data, we can use a binary format that is self-delimiting. But we are just concatenating, so we need to know how to split. We are going to hash the entire byte string, so we don't need to split. But we do need to construct the byte string in a deterministic way. We can do: data = varint_serialize(len(command_args)) + for each arg in command_args: varint_serialize(len(arg)) + arg_bytes varint_serialize(len(env_vars)) + for each (key, value) in sorted(env_vars): varint_serialize(len(key)) + key_bytes + varint_serialize(len(value)) + value_bytes varint_serialize(len(inputs)) + for each (path, digest) in sorted(inputs by path): varint_serialize(len(path)) + path_bytes + digest_bytes (fixed 32 bytes, so no length needed? But then we must know that the digest is 32 bytes. That's okay because it's fixed.) But wait: the digest for a source file is 32 bytes, and for an action it's also 32 bytes. So we can assume fixed length. However, what if we change the hash function in the future? Then the digest length changes. So we might want to include the length. But if we are committed to SHA256, then it's fixed. Alternatively, we can store the digest as a fixed-length 32-byte array. Then for the inputs list, we have: for each input: write length of path (varint) + path_bytes + 32-byte digest But then when we read it, we know that after the path we have exactly 32 bytes. However, we are not reading it, we are just hashing. So we just need to produce the same byte string every time. We can do: data = b'' # command data += varint(len(command_args)) for arg in command_args: data += varint(len(arg)) + arg.encode('utf-8') # environment env_vars = sorted(environment.items(), key=lambda x: x[0]) data += varint(len(env_vars)) for key, value in env_vars: data += varint(len(key)) + key.encode('utf-8') data += varint(len(value)) + value.encode('utf-8') # inputs inputs_sorted = sorted(inputs, key=lambda x: x[0]) # sort by path data += varint(len(inputs_sorted)) for path, digest in inputs_sorted: data += varint(len(path)) + path.encode('utf-8') data += digest # digest is 32 bytes Then cache_key = SHA256(data)But note: the digest for an action is its cache key (which is a SHA256 hash, 32 bytes). For a source file, we compute the SHA256 of the file content (32 bytes). So we can represent both as 32-byte arrays.
However, we must be cautious: the cache key of an action is a SHA256 hash, but we are using it as a digest. That's fine.
But wait: the cache key of an action is itself computed by this same method? Then we have recursion. That's okay because we compute in topological order.
Now, what about the case where the same input file is used by multiple actions? We compute its file hash once and then reuse. That's efficient.
What about the case where an action has no inputs? Then the inputs list is empty.
What about the case where an action has a directory input? We treat the directory as a set of files. We recursively list all files (with their relative paths from the directory root) and then for each file, we compute its file hash. Then we sort the list of (relative_path, file_hash) and then compute the hash of the directory as:
dir_hash = SHA256( varint(len(files)) + for each (rel_path, file_hash) in sorted by rel_path: varint(len(rel_path)) + rel_path_bytes + file_hash ) Then we treat the directory as a single input with path = directory_path (absolute, canonical) and digest = dir_hash.But note: the directory path itself? We are using the directory path as the input path. But the content of the directory is the set of files. So we are hashing the content of the directory (the files) and then using the directory path as the key for that hash. That's okay.
Alternatively, we can treat the directory as a virtual file with the directory path and the digest of the entire directory tree.
Now, what about symlinks inside the directory? We follow symlinks when listing files? We should, because the content of the target is what matters.
So the policy for a directory:
- Canonicalize the directory path (resolve symlinks, absolute, consistent case).
- Recursively list all files (and symlinks? we follow symlinks to get the file content). But what about symlinks that point to directories? We follow them and then list the files in the target? That might cause cycles? We must avoid cycles. We can use a set of inodes (or file IDs) to avoid cycles? But that's complex. Alternatively, we can say that symlinks are not allowed in source trees? Or we treat symlinks as files? But then the content of a symlink is the path it points to. So if we have a symlink, we read the symlink target (as a string) and hash that string? Then we don't follow the symlink? That might be safer because we avoid cycles and we don't rely on the target's existence? But if the symlink points to a file, then the content of that file might be used by the build? Then we need the content of the target file? So we must follow the symlink to get the content? But then if the symlink points to a file that is outside the directory, we include that file? That might be intended.
Given the complexity, we might say:
The build system must provide a way to enumerate the input files (with their content) in a canonical way. We don't design that.
Since we are designing the cache key policy, we assume that the build system gives us a set of input files (with their absolute, canonical paths) and for each file, we can get its content (following symlinks). For directories, we can recursively expand them to the set of files.
So we leave the file enumeration to the build system.
Summary of the policy:
-
Inputs:
- The build system must provide a list of input files (with their absolute, canonical paths) and their content hashes (for source files) or the cache key of the producing action (for generated files).
- For directories, the build system must provide the set of files (with relative paths within the directory) and their content hashes, and then compute the directory hash as described.
-
Stateless rules:
- Rules that are marked as non-cacheable (stateless) are run every time and do not store their outputs in the cache.
- Their cache key is still computed (based on their inputs) and is used by dependent cacheable actions.
-
Hashing:
- The cache key for an action is the SHA256 hash of a canonical binary serialization of:
- The command (as an array of strings, in order) and environment (as a sorted list of key-value pairs).
- The sorted list of inputs, where each input is represented by its canonical path and its digest (content hash for source files, cache key for generated files).
- The serialization is done with length-prefixed strings for the command arguments and environment variables, and for the inputs, we include the path (length-prefixed) and then the fixed-length (32-byte) digest.
- The cache key for an action is the SHA256 hash of a canonical binary serialization of:
This policy should be stable and sensitive to changes.
However, note: the command and environment might contain absolute paths (e.g.,
-I/absolute/path). If we move the build directory, the absolute path changes and the cache key changes. That might be intended? Or we might want to make the paths relative? That is tool-specific. We can say that the build system must canonicalize the command and environment to be relative to the workspace root? But that's not always possible (e.g., system include paths). So we might have to accept that absolute paths in the command will cause cache invalidation when the build directory changes. That's a common problem.We can try to rewrite absolute paths in the command to be relative to a fixed root? But that's error-prone.
Alternatively, we can say that the build system must provide a way to normalize paths in the command and environment (e.g., by replacing the workspace root with a placeholder). But that's build-system specific.
Given the scope, we might leave that as an implementation detail of the build system.
So the policy is:
The cache key is computed from: - The command (as provided by the build system, in the order given). - The environment (as provided by the build system, with variables sorted by name). - The set of input files, each with a canonical path and a digest.
The build system is responsible for ensuring that the same logical command and environment (with the same effect) produce the same serialization.
This is a bit hand-wavy, but it's hard to be more specific without knowing the build system.
Let's try to be more concrete:
We assume the build system can provide:
- command: an array of strings (the argv). - environment: a dictionary of string -> string. - inputs: a list of tuples (path, digest), where: path: absolute, canonical (symlinks resolved, consistent case) path to a file. digest: 32-byte SHA256 hash of the file content (for source files) or the cache key of the action that produced the file (for generated files). And for directories, the build system must expand them to the set of files (as above).Then we compute:
def compute_cache_key(command, environment, inputs): # command: list of strings # environment: dict of string -> string # inputs: list of (path:str, digest:bytes) data = b'' # Serialize command data += varint(len(command)) for arg in command: arg_bytes = arg.encode('utf-8') data += varint(len(arg_bytes)) data += arg_bytes # Serialize environment env_items = sorted(environment.items(), key=lambda x: x[0]) data += varint(len(env_items)) for key, value in env_items: key_bytes = key.encode('utf-8') value_bytes = value.encode('utf-8') data += varint(len(key_bytes)) data += key_bytes data += varint(len(value_bytes)) data += value_bytes # Serialize inputs inputs_sorted = sorted(inputs, key=lambda x: x[0]) # sort by path data += varint(len(inputs_sorted)) for path, digest in inputs_sorted: path_bytes = path.encode('utf-8') data += varint(len(path_bytes)) data += path_bytes data += digest # digest is 32 bytes return hashlib.sha256(data).digest()We assume that the digest for generated files is exactly 32 bytes (the cache key of the producing action, which is a SHA256).
This is a stable and deterministic way to compute the cache key.
However, note: the varint encoding must be deterministic. We can use a standard varint (like LEB128) or we can use a fixed 8-byte integer for the length? Since the lengths are not huge (command arguments and paths are not thousands of bytes), we can use a fixed 8-byte big-endian integer for the length? That would be simpler.
Let's change to:
Instead of varint, we use a fixed 8-byte big-endian integer for the length. Then: data = b'' # command data += len(command).to_bytes(8, 'big') for arg in command: arg_bytes = arg.encode('utf-8') data += len(arg_bytes).to_bytes(8, 'big') data += arg_bytes # environment env_items = sorted(environment.items(), key=lambda x: x[0]) data += len(env_items).to_bytes(8, 'big') for key, value in env_items: key_bytes = key.encode('utf-8') value_bytes = value.encode('utf-8') data += len(key_bytes).to_bytes(8, 'big') data += key_bytes data += len(value_bytes).to_bytes(8, 'big') data += value_bytes # inputs inputs_sorted = sorted(inputs, key=lambda x: x[0]) data += len(inputs_sorted).to_bytes(8, 'big') for path, digest in inputs_sorted: path_bytes = path.encode('utf-8') data += len(path_bytes).to_bytes(8, 'big') data += path_bytes data += digest # 32 bytes cache_key = hashlib.sha256(data).digest()This is deterministic and easier to implement.
But note: the digest for a generated file is 32 bytes. We don't store its length because we know it's 32.
This policy should work.
However, we must ensure that the path is canonical. The build system must provide the absolute, canonical path (with symlinks resolved and consistent case). Otherwise, two paths that point to the same file but are written differently (e.g., with extra
.or..) would be considered different.So we require:
- For each input file, the path must be the real path (as returned by
os.path.realpathon Unix, or the equivalent on Windows) and must be absolute.
This should be stable.
Now, what about the case where the same physical file is reachable by two different logical paths in the build? Then we would have two inputs with different paths but the same content hash? That would be a problem because the action might depend on the path. But if the action only depends on the content, then it's okay? But if the action uses the path (e.g., for error messages), then it would produce different outputs. So we must include both paths? Then the action would have two inputs that are the same file? That would be a mistake in the build definition? The build system should not add the same file twice with different paths? Or it should canonicalize the paths.
So we rely on the build system to provide a set of unique (by real path) inputs. If the same real file is added twice (with different paths), then the build system should deduplicate? Or we should? We are just hashing the set of inputs. If we have two entries for the same file (with different paths) then the action will get two copies of the same file? That might be intended? Unlikely.
We can leave that to the build system: it should not add the same file twice with different paths.
So the policy is:
The build system must provide a set of input files that are unique by their canonical absolute path.
This is a reasonable requirement.
Finally, we must consider that the cache key must be the same across different machines and over time. So we must avoid machine-specific data (like hostname, current time, etc.) in the command and environment. The build system must strip such things.
We can say:
The build system must ensure that the command and environment do not contain any non-reproducible data (like timestamps, random numbers, host-specific information). If such data is needed, it must be removed or replaced with a stable value.
This is a general requirement for reproducible builds.
Putting it all together:
Stable Build Cache Keys Policy
1. Inputs - The build system must provide a list of input files for each action. Each input file is identified by its canonical absolute path (with symlinks resolved and in a consistent case). The set of paths must be unique (no duplicates). - For each input file, we compute a digest: * If the input file is a source file (not produced by any action in the current build), the digest is the SHA256 hash of the file's content (following symlinks). * If the input file is produced by another action (in the same build), the digest is the cache key of that action (which is also a SHA256 hash). - For directory inputs, the build system must expand the directory to the set of files (recursively) and compute a directory digest as the SHA256 of the sorted list of (relative_path, file_digest) for all files in the directory. Then the directory is treated as a single input with the directory's canonical absolute path and the directory digest.
2. Stateless Rules - A rule (action) that is marked as non-cacheable (stateless) is never stored in the cache. It is run every time. - However, its cache key is still computed (as described below) and is used by dependent cacheable actions.
3. Hashing - The cache key for an action is computed as follows:
Let: command: the array of command-line arguments (strings) as provided by the build system. environment: a dictionary of environment variables (string -> string) that affect the build. inputs: a list of tuples (path:str, digest:bytes) for all input files (as described above). Steps: a. Canonicalize the environment: sort the items by the key (string comparison). b. Sort the inputs by the path (string comparison). c. Serialize the data into a byte string with the following format: [8-byte big-endian integer: number of command arguments (N)] For each of the N command arguments: [8-byte big-endian integer: length of argument in bytes (L)] [L bytes: the argument encoded in UTF-8] [8-byte big-endian integer: number of environment variables (M)] For each of the M environment variables (key, value): [8-byte big-endian integer: length of key in bytes (K)] [K bytes: key encoded in UTF-8] [8-byte big-endian integer: length of value in bytes (V)] [V bytes: value encoded in UTF-8] [8-byte big-endian integer: number of inputs (P)] For each of the P inputs (path, digest): [8-byte big-endian integer: length of path in bytes (Lp)] [Lp bytes: path encoded in UTF-8] [32 bytes: digest] d. Compute the SHA256 hash of the serialized byte string. The result (32 bytes) is the cache key. - The build system must ensure that the command and environment are free of non-reproducible data (like timestamps, random numbers, machine-specific information). If such data is present, it must be removed or replaced with a stable value.This policy should produce stable cache keys that are sensitive to all relevant changes.
Note: the cache key is 32 bytes (SHA256). We can represent it as a hex string (64 characters) for storage and comparison.
Additional considerations:
-
The build system must compute the cache keys in topological order (dependencies first) because the cache key of an action depends on the cache keys of its dependencies.
-
For cacheable actions, the output files are stored in the cache under the cache key (e.g., in a directory named by the hex string of the cache key).
-
When restoring from cache, the build system must verify that the cached output is complete and matches the cache key.
-
The cache should be indexed by the cache key and also by the action's output paths? Not necessary: the cache key uniquely identifies the action and its inputs.
This is a comprehensive policy. However, in practice, build systems like Bazel and Buck have their own specific ways. But this policy should be a good foundation.
Let me know if there are any edge cases we missed. I'll design a comprehensive Stable Build Cache Keys Policy that balances reproducibility, performance, and practicality. This policy addresses inputs, stateless rules, and hashing strategies.
Policy Goals
- Stability: Same inputs → same cache key forever
- Sensitivity: Any meaningful change → different cache key
- Efficiency: Fast computation, minimal storage
- Security: Protection against hash collisions and poisoning
- Scalability: Works for large codebases and distributed builds
1. INPUTS CATEGORIZATION
A. Immutable/Content-Based Inputs (Primary Sources)
Input Type Hashing Strategy Notes Source files Content hash (SHA-256) Follow symlinks; exclude generated files Lock files Full content hash package-lock.json,Cargo.lock,go.sumConfiguration files Full content hash *.config,Dockerfile, CI configsBuild scripts Full content hash build.sh,CMakeLists.txt,BUILDfilesThird-party dependencies Lock file + source hash For dependencies without locks: hash of source tarball/commit B. Immutable but Volatile Inputs
Input Type Hashing Strategy Notes Toolchain versions Deterministic string gcc --versionoutput,java -versionCompiler flags Sorted, normalized flags Order-independent where possible; canonicalize paths Environment variables Whitelisted + sorted Only CC,CXX,CFLAGS, etc.Platform targets Canonical triple x86_64-unknown-linux-gnuC. Mutable/Stateful Inputs (Should be avoided or minimized)
Input Type Handling Notes Timestamps Excluded or normalized Use SOURCE_DATE_EPOCHUser-specific dirs Excluded ~/.m2,/home/userBuild directory paths Normalized Replace with placeholder /build/UUIDs/Random seeds Excluded or deterministic Use fixed seeds when possible
2. STATELESS RULES HANDLING
Definition
Stateless rules = transformations where output is purely a function of inputs, with no external state and no persistent side effects.
Classification & Policy
Rule Type Cacheable? Key Strategy Example Pure functions ✅ Yes Input content hash cat file.txt → output.txtDeterministic builders ✅ Yes Inputs + toolchain version gcc -c foo.c → foo.oNon-deterministic ❌ No N/A (bypass cache) date > timestamp.txtSide-effecting ❌ No N/A (bypass cache) echo "Build started"Opaque commands ⚠️ Conditional Command hash + inputs custom_build_tool --configImplementation Rules
- Default: Assume rules are cacheable unless proven otherwise
- Opt-out: Explicit
[no-cache]attributes or metadata - Validation:
- Run rule twice with same inputs → identical outputs (bitwise)
- No filesystem writes outside declared outputs
- No network calls (or deterministically mocked)
- Stateless rule signature (for automation):
def is_cacheable(rule): return ( rule.is_deterministic and rule.outputs_are_deterministic and not rule.has_side_effects and rule.inputs_are_stable )
3. HASHING STRATEGY
Core Principles
- Cryptographic hash: SHA-256 (or BLAKE3 for speed)
- Canonicalization: Always sort, normalize, eliminate noise
- Layering: Combine hashes hierarchically where appropriate
A. Single File Hash
def file_hash(path): # 1. Resolve symlinks (follow to real file) real_path = os.path.realpath(path) # 2. Read content (binary mode) with open(real_path, 'rb') as f: content = f.read() # 3. Compute hash return hashlib.sha256(content).digest()B. Directory Hash (Recursive)
def dir_hash(dir_path): entries = [] for root, dirs, files in os.walk(dir_path): # Sort for determinism dirs.sort() files.sort() for file in files: full_path = os.path.join(root, file) rel_path = os.path.relpath(full_path, dir_path) file_digest = file_hash(full_path) entries.append((rel_path, file_digest)) # Sort by path entries.sort(key=lambda x: x[0]) # Serialize and hash hasher = hashlib.sha256() for rel_path, digest in entries: hasher.update(rel_path.encode('utf-8')) hasher.update(digest) return hasher.digest()C. Composite Input Hash (For a build action)
def compute_cache_key( command_args, # List[str] - canonicalized env_vars, # Dict[str,str] - sorted, whitelisted input_files, # List[(str, bytes]] - (path, hash) toolchain_version, # str platform # str ): """ Format: [4-byte magic: 0x43534b43] # "CKSK" - cache key signature [1-byte version: 0x01] [32-byte toolchain hash] [32-byte platform hash] [8-byte: N_args] [for each arg: 4-byte len + arg bytes] [8-byte: N_env] [for each env (sorted by key): 4-byte len + key + 4-byte len + value] [8-byte: N_inputs] [for each input (sorted by path): 4-byte len + path + 32-byte hash] [32-byte: final hash of above?] # Or just hash the whole thing """ # Canonicalize command canonical_args = canonicalize_command_args(command_args) # Canonicalize environment canonical_env = canonicalize_env(env_vars) # Sort inputs by path sorted_inputs = sorted(input_files, key=lambda x: x[0]) # Serialize everything into byte buffer buffer = bytearray() buffer.extend(b'CKSK') # Magic buffer.append(0x01) # Version # Toolchain hash (precomputed) buffer.extend(toolchain_hash(toolchain_version)) buffer.extend(platform_hash(platform)) # Command args buffer.extend(len(canonical_args).to_bytes(8, 'big')) for arg in canonical_args: arg_bytes = arg.encode('utf-8') buffer.extend(len(arg_bytes).to_bytes(4, 'big')) buffer.extend(arg_bytes) # Environment env_items = sorted(canonical_env.items()) buffer.extend(len(env_items).to_bytes(8, 'big')) for key, value in env_items: key_bytes = key.encode('utf-8') value_bytes = value.encode('utf-8') buffer.extend(len(key_bytes).to_bytes(4, 'big')) buffer.extend(key_bytes) buffer.extend(len(value_bytes).to_bytes(4, 'big')) buffer.extend(value_bytes) # Input files buffer.extend(len(sorted_inputs).to_bytes(8, 'big')) for path, digest in sorted_inputs: path_bytes = path.encode('utf-8') buffer.extend(len(path_bytes).to_bytes(4, 'big')) buffer.extend(path_bytes) buffer.extend(digest) # 32 bytes # Final hash return hashlib.sha256(buffer).hexdigest()D. Optimization: Merkle Trees for Large Inputs
For builds with thousands of files:
Root hash = H(manifest) Manifest = sorted list of (path, file_hash) file_hash = H(file_content)- Store intermediate directory hashes in a side file (
.buildcache/merkle.json) - Recompute only changed subtrees when files change
4. NORMALIZATION RULES
Command Line Normalization
def canonicalize_command_args(args): """ - Split combined flags: `-I/usr/include` → `-I`, `/usr/include` - Sort order-independent flags: `-lfoo -lbar` → sorted alphabetically - Remove/replace non-deterministic elements: * `-ftime-trace` → remove * `-frandom-seed=` → replace with fixed seed * `--debug-prefix-map=` → normalize - Absolute paths → relative to workspace root (if possible) """ normalized = [] for arg in args: # Handle combined flags if arg.startswith('-') and len(arg) > 2 and arg[1] in 'IDFOILl': normalized.append(arg[:2]) normalized.append(arg[2:]) else: normalized.append(arg) # Sort known order-independent flags sorted_args = [] i = 0 while i < len(normalized): if normalized[i] in ('-l', '-L', '-I'): # Collect all consecutive library/include flags libs = [] while i < len(normalized) and normalized[i] in ('-l', '-L', '-I'): libs.append(normalized[i]) i += 1 if i < len(normalized) and not normalized[i].startswith('-'): libs.append(normalized[i]) i += 1 sorted_args.extend(sorted(libs)) else: sorted_args.append(normalized[i]) i += 1 return sorted_argsPath Normalization
def canonicalize_path(path, workspace_root): """ 1. Make absolute 2. Resolve symlinks (os.path.realpath) 3. Make relative to workspace root (if under it) 4. Normalize case (lowercase on case-insensitive FS) 5. Remove redundant `.` and `..` """ abs_path = os.path.abspath(path) real_path = os.path.realpath(abs_path) if real_path.startswith(workspace_root): rel_path = os.path.relpath(real_path, workspace_root) # Normalize to forward slashes rel_path = rel_path.replace('\\', '/') return rel_path else: # External dependency - keep absolute but normalize return real_path.replace('\\', '/').lower()
5. STATELESS RULE DETECTION & HANDLING
Automatic Detection Heuristics
def detect_stateless(rule): dangers = [] # Check for non-determinism patterns if re.search(r'\b(time|date|now|timestamp|random|uuid)\b', rule.command, re.I): dangers.append("temporal_reference") if re.search(r'\b(/dev/urandom|/proc/|/sys/)', rule.command): dangers.append("kernel_interface") # Check for network calls if any(tool in rule.command for tool in ['curl', 'wget', 'git', 'hg']): dangers.append("network_access") # Check for user/home directory if re.search(r'~|/home/|/Users/', ' '.join(rule.args)): dangers.append("user_specific_path") # Check output determinism (if we have previous runs) if rule.has_previous_runs: outputs = rule.get_outputs() if not all(outputs_are_identical(rule, outputs)): dangers.append("non_deterministic_outputs") return len(dangers) == 0 # True if no dangers detectedStateless Rule Bypass
For rules marked
[no-cache]or detected as non-stateless:- Never store in cache
- Always execute (but inputs still affect downstream cache keys)
- Outputs must be declared (for dependency tracking)
- Consider sandboxing to prevent accidental state leakage
6. CACHE KEY COMPUTATION PIPELINE
class CacheKeyBuilder: def __init__(self, workspace_root): self.workspace_root = workspace_root self._file_cache = {} # path → hash (for reused files) def build_key(self, action): # 1. Gather inputs input_entries = [] for input_spec in action.inputs: path = self.canonicalize(input_spec.path) if input_spec.is_directory: digest = self.dir_hash(path) else: digest = self.file_hash(path) input_entries.append((path, digest)) # 2. Get toolchain info toolchain = self.get_toolchain_hash(action.toolchain) platform = self.get_platform_hash(action.platform) # 3. Get environment (whitelisted + sorted) env = self.filter_and_sort_env(action.environment) # 4. Get command (canonicalized) cmd = self.canonicalize_command(action.command) # 5. Compute final hash return compute_cache_key( command_args=cmd, env_vars=env, input_files=input_entries, toolchain_version=toolchain, platform=platform ) def file_hash(self, path): if path not in self._file_cache: self._file_cache[path] = self._raw_file_hash(path) return self._file_cache[path]
7. EDGE CASES & SPECIAL HANDLING
Generated Files
- Never include in cache keys (they're outputs, not inputs)
- If generated file becomes an input to another rule:
- The generating rule must be cacheable
- Use the generating rule's cache key as the digest
Git/Mercurial Checkouts
Cache key components: 1. Repository URL (normalized) 2. Commit hash (exact) 3. Submodule commits (recursive) 4. .gitattributes (if affects checkout)NOT: branch name, dirty state, timestamps
Docker Layers
Cache key = H( base_image_digest, Dockerfile_content, build_context_hash (recursive) )Timestamps in Builds
- Never use file modification times
- Use
SOURCE_DATE_EPOCHenvironment variable if absolutely needed - For reproducible builds: strip timestamps from outputs
8. VALIDATION & MONITORING
Cache Key Stability Test
# 1. Build once ./build.sh # Save cache keys: find .buildcache -type f -exec sha256sum {} \; > keys1.txt # 2. Rebuild in clean environment git clean -fdx ./build.sh find .buildcache -type f -exec sha256sum {} \; > keys2.txt # 3. Compare diff keys1.txt keys2.txt # Should be emptyCache Key Coverage
- Log every cache key computed
- Alert on keys that change too frequently (flapping)
- Track cache hit/miss rates per rule type
9. IMPLEMENTATION CHECKLIST
Required
- All file paths canonicalized (realpath, relative to workspace)
- Symlinks followed to real files
- Environment variables whitelisted and sorted
- Command arguments normalized and sorted where appropriate
- Timestamps/randomness stripped from commands
- Directory hashes computed recursively
- Cache keys computed in topological order
- Stateless rules explicitly marked or auto-detected
Recommended
- Merkle tree for large directories
- Precomputed hashes for common toolchains
- Cache key versioning (when algorithm changes)
- Cache key provenance (what contributed to the hash)
- Deterministic archive format for multi-output rules
Forbidden
- ❌ File modification times in cache keys
- ❌ Absolute paths outside workspace (unless external dependency)
- ❌ User-specific directories (
~,/home/,/Users/) - ❌ Non-deterministic commands in cacheable rules
- ❌ Cache key based on build start time
10. MIGRATION STRATEGY
Phase 1: Detection
- Instrument existing build to log current cache keys
- Compare with proposed algorithm on sample builds
- Identify unstable patterns
Phase 2: Dual Keys
- Compute both old and new cache keys
- Use new keys for storage, old keys for lookup (gradual migration)
- Log mismatches
Phase 3: Cutover
- Switch entirely to new keys
- Keep old cache for 1-2 builds as fallback
- Document breaking changes
Summary Formula
CacheKey = SHA256( "CKSK" + version + toolchain_hash + platform_hash + sorted_canonical_command + sorted_whitelisted_env + sorted_input_entries(path_hash_pairs) )Where:
path_hash_pairs=(canonical_path, file_or_dir_hash)file_or_dir_hash= SHA256(content) for files, SHA256(manifest) for dirs- All strings UTF-8 encoded
- All multi-byte lengths big-endian
This policy ensures stable, reproducible, and efficient build caching while properly handling stateless rules through explicit classification and detection.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.