Dockerfile Layer Cache Invalidation

hardFREEContainer Images & BuildsSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

A Docker build reuses a cached layer only while nothing that layer depends on has changed. The moment one layer misses the cache, every layer after it is rebuilt too. This is why COPY . /app placed before RUN pip install turns a 30-second rebuild into a 6-minute one: touching any source file invalidates the copy, and the dependency install downstream of it is thrown away.

Given a Dockerfile as an ordered list of instructions and the set of files that changed in the build context, work out exactly which layers Docker has to rebuild.

Background

Docker's cache rules, simplified to the ones that matter here:

A COPY or ADD layer that reads from the build context misses the cache when any of its source paths cover a changed file.
A COPY --from=<stage> reads from another build stage, not from the build context, so a changed context file never invalidates it directly.
Every other instruction (FROM, RUN, WORKDIR, ENV, CMD, ...) is identical to last time, so it can only be invalidated by cascade.
Cascade rule: once a layer misses, all subsequent layers miss as well.

Source-path matching rule for this problem: split the instruction on whitespace. The last operand is the destination; all earlier operands that do not start with -- are sources. A source . (or ./) covers every changed file. Any other source s (after stripping a leading ./ and any trailing /) covers a changed file f when f == s or f starts with s + "/".

Your Task

Implement:

def rebuilt_layers(instructions, changed_files):

Return a list of the 1-based indices of the instructions that are rebuilt, in ascending order. Return [] when the whole build is a cache hit.

Input Format

instructions: list of strings, one Dockerfile instruction each, in order.
changed_files: list of build-context relative paths (strings) that changed.

Output Format

A list of ints — the 1-based positions of the rebuilt instructions.

Sample

insts = [
    "FROM python:3.13-slim",
    "WORKDIR /app",
    "COPY . /app",
    "RUN pip install -r requirements.txt",
    'CMD ["python", "app.py"]',
]
print(rebuilt_layers(insts, ["app.py"]))

Output:

[3, 4, 5]

COPY . /app covers app.py, so layer 3 misses; the cascade rule rebuilds 4 and 5 as well — including the expensive pip install.

Example

Input

insts = ["FROM python:3.13-slim", "WORKDIR /app", "COPY . /app", "RUN pip install -r requirements.txt", 'CMD ["python", "app.py"]']
print(rebuilt_layers(insts, ["app.py"]))

Output

[3, 4, 5]

Reasoning

Inputs: instructions is the Dockerfile as five strings, one layer each, numbered 1 to 5 in file order. changed_files holds a single path, app.py (the only edit).
Layers 1 (the base image) and 2 (the working directory) do not read the build context, so both are cache hits.
Layer 3 copies from the build context. Its operands are "." and "/app"; the last one is the destination, so the only source is ".", which covers every changed file. Because app.py changed, layer 3 misses.
Cascade: if layer $k$ misses, every layer $j > k$ misses too. Layer 4 (the dependency install) and layer 5 (the start command) never touch the context, yet both rebuild, giving [3, 4, 5].
Notice the cost: the install sits after a whole-context copy, so any edit throws it away. If layer 3 instead copied just a "src" folder, app.py would not be covered (a source $s$ covers $f$ only when $f = s$ or $f$ lies inside the folder $s$ ), and the answer would be [].

Constraints

1 <= len(instructions) <= 60
0 <= len(changed_files) <= 50
Instruction keywords are uppercase; operands are separated by single spaces
Only COPY and ADD read from the build context
A COPY --from=<stage> instruction is never invalidated directly by a changed context file
Indices in the returned list are 1-based and ascending

Learn this in

CI/CD & PipelinesSystems & Networking Docker & ContainerizationSystems & Networking

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Deduplicate Retried Pipeline Runs by Idempotency Keymedium Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium

Concept primer

1. Background Knowledge

Docker builds are optimized using a layer caching mechanism. Each instruction in a Dockerfile creates a new layer. If the inputs to an instruction (and all preceding instructions) remain unchanged from the previous build, Docker reuses the cached layer, skipping execution. This significantly speeds up iterative development. However, the cache is fragile: if any layer fails to match the cache, all subsequent layers are invalidated and must be rebuilt. This phenomenon is known as cache invalidation cascade.

The core challenge in this problem is determining which specific instructions trigger a cache miss based on file system changes. The primary culprit is usually the COPY or ADD instruction, which copies files from the build context (the local directory) into the image. If a file referenced by COPY has changed, that layer's content hash changes, causing a miss. Crucially, COPY --from=<stage> references another build stage's output, not the local build context, so local file changes do not directly invalidate these layers.

Understanding path matching is essential. A source path like . or ./ matches any file in the context. A specific path like src/ matches any file starting with src/. The problem simplifies this by defining strict rules: split the instruction, identify sources (operands not starting with -- and not the last operand), and check if any changed file falls under these sources. This requires careful string manipulation and logical comparison of file paths.

2. Algorithm Approach

The problem can be modeled as a sequential scan with state propagation. Since Docker processes instructions in order, we can iterate through the instructions list from first to last. We maintain a boolean flag, cache_missed, initialized to False.

For each instruction:

If cache_missed is already True, the current instruction is automatically rebuilt due to the cascade rule.
If cache_missed is False, we check if the current instruction itself causes a miss. This only applies to COPY or ADD instructions that read from the build context (i.e., do not have --from).
To check if a COPY/ADD misses, we parse its source paths and compare them against the changed_files set. If any changed file matches any source path, the layer misses.
If a miss is detected (either by cascade or direct match), we mark cache_missed as True and record the current instruction's index.

This approach is linear because each instruction is processed exactly once, and the state (cache_missed) is updated incrementally.

3. Step-by-Step Strategy

Initialize State: Create an empty list rebuilt_indices to store results. Set a boolean is_invalidated to False.
Iterate Instructions: Loop through instructions with index i (0-based). Convert to 1-based index for output.
Check Cascade: If is_invalidated is True, append i + 1 to rebuilt_indices and continue to the next instruction. No further parsing is needed for this layer.
Parse Instruction: If not invalidated, check if the instruction starts with COPY or ADD.

If it does not, the layer is a cache hit (assuming no prior invalidation). Continue.
If it does, check for --from. If --from is present, it reads from another stage, so it cannot be invalidated by local context changes. Continue.

Identify Sources: Split the instruction string by whitespace.

The last token is the destination.
Tokens before the destination that do not start with -- are source paths.

Match Changed Files: For each source path:

Normalize the source: strip leading ./ and trailing /.
If the normalized source is empty or ., it matches all changed files. If changed_files is not empty, the layer misses.
Otherwise, check if any file in changed_files equals the source or starts with source + "/".

Update State: If a match is found, set is_invalidated to True and append i + 1 to rebuilt_indices.
Return Result: After the loop, return rebuilt_indices.

4. Common Pitfalls

Misidentifying Sources: Remember that the last operand is the destination. In COPY src/ dest/, src/ is the source. In COPY --from=builder /app /local, /app is the source, but it’s from a stage, so ignore it for context changes.
Path Matching Logic: Be careful with directory prefixes. A source src matches src/file.txt but not src2/file.txt. Ensure you check for file.startswith(source + "/") or file == source.
Leading/Trailing Slashes: The problem specifies stripping leading ./ and trailing /. Failing to normalize ./src/ to src might cause mismatches if changed files are listed as src/file.txt.
COPY. /app: The source . (or ./) matches any changed file. Do not treat it as a literal filename match only.
1-Based Indexing: The problem requires 1-based indices. Ensure you add 1 to the loop index when appending to the result list.
Empty Changed Files: If changed_files is empty, no COPY from context will miss (unless the instruction itself changed, but the problem implies only file content changes matter for COPY cache). The cascade rule still applies if a previous layer missed.

5. Time & Space Complexity

Time Complexity: $O(N \cdot M \cdot L)$ , where $N$ is the number of instructions, $M$ is the number of changed files, and $L$ is the average length of file paths. In the worst case, for each COPY instruction, we compare every changed file against every source path. String matching takes $O(L)$ . If $M$ is large, this could be optimized with a trie or sorting, but for typical Dockerfiles, $M$ is small.
Space Complexity: $O(K)$ , where $K$ is the number of rebuilt layers, to store the result list. Auxiliary space for parsing instructions is $O(L)$ per instruction. The changed_files set lookup can be optimized to $O(1)$ average if converted to a set, but since we need prefix matching, a simple list iteration is often sufficient unless $M$ is very large.

solution.py

Python 3.13

Test results