Solving CI/CD Cache Invalidation at Scale

At sufficient fleet size, a distributed CI/CD runner pool does not fail gracefully — it fails as a herd. The specific failure mode is CI/CD cache invalidation storms: hundreds of ephemeral runners simultaneously detect a stale dependency cache, issue concurrent write-backs to the same object store key, and saturate the backing storage’s request rate limit within seconds. The result is a cascading pipeline slowdown that looks like an infrastructure outage but is actually a concurrency control failure in the cache layer itself. This article addresses the architecture required to eliminate CI/CD cache invalidation storms in high-throughput monorepo pipelines running on Kubernetes-backed runner fleets.

The problem is rarely the cache hit path. Object stores such as S3 or GCS handle read-heavy workloads at near-infinite scale. The bottleneck is the miss path — specifically what happens when many runners miss the cache at the same logical timestamp because a shared dependency (a lockfile, a base image digest, a monorepo build target) changed upstream. Without coordination, every runner independently rebuilds the artifact and independently attempts to write it back, producing redundant compute and a write amplification problem on the storage backend.

#Architectural Breakdown: Why Naive Cache Invalidation Fails

Most CI systems (GitHub Actions, GitLab CI, CircleCI) expose a single-tier key-value cache abstraction: you provide a cache key, usually a hash of a lockfile, and the system stores or restores a blob against that key. This model works acceptably at low concurrency but degrades badly under two conditions common in enterprise monorepos:

• High fan-out: a single commit triggers 200+ parallel jobs, all computing the same cache key simultaneously.
• Non-atomic invalidation: the cache key changes (a dependency bump), and every runner independently regenerates and re-uploads the same artifact within a narrow time window.

The correct architectural response borrows directly from distributed systems theory: treat the cache as a content-addressable store (CAS) layered with a distributed mutex to prevent redundant regeneration, and decouple invalidation from key rotation using a Merkle-tree-derived hash rather than a flat lockfile hash. This is precisely the model used internally by Bazel’s remote caching subsystem, and it generalises well beyond Bazel-specific toolchains.

#Tiered Cache Topology

A resilient design separates the cache into three tiers, each with different consistency and latency guarantees:

• L1 — Local ephemeral disk: scoped to the runner’s lifetime, sub-millisecond access, zero network cost, but zero cross-job sharing.
• L2 — Regional object store (S3/GCS bucket per region): shared across the runner fleet within a region, milliseconds-to-low-tens-of-milliseconds latency, eventual consistency risk on concurrent writes.
• L3 — Global CDN-fronted CAS: read-optimised, immutable content-addressed blobs, used for cross-region and cross-team artifact sharing.

Cache invalidation logic must operate differently at each tier. L1 requires no invalidation coordination because it dies with the runner. L2 and L3 require explicit coordination because multiple concurrent writers can target the same logical key. This is where most naive implementations collapse: they apply L1-style assumptions (fire-and-forget writes) to L2/L3 infrastructure, and the write amplification problem emerges precisely at the moment a shared dependency changes across the entire monorepo.

#Implementation Logic: Content-Addressable Keys and Stampede Locks

The fix decomposes into two independent mechanisms that must be implemented together, not in isolation.

#1. Content-Addressable Cache Keys

Rather than hashing a single lockfile, compute the cache key from a Merkle tree

1#!/usr/bin/env bash
2# compute_cache_key.sh - Merkle-style content hash for a build target
3set -euo pipefail
4
5TARGET_DIR="$1"
6TOOLCHAIN_VERSION=$(cat .toolchain-version)
7
8# Hash all tracked source files under the target, sorted for determinism
9FILE_HASH=$(git ls-files -s "$TARGET_DIR" 
10  | awk '{print $2, $4}' 
11  | sort 
12  | sha256sum 
13  | cut -d' ' -f1)
14
15# Combine with toolchain + resolved lockfile hash
16LOCK_HASH=$(sha256sum "$TARGET_DIR/package-lock.json" | cut -d' ' -f1)
17
18CACHE_KEY=$(printf "%s:%s:%s" "$FILE_HASH" "$LOCK_HASH" "$TOOLCHAIN_VERSION" 
19  | sha256sum | cut -d' ' -f1)
20
21echo "$CACHE_KEY"

#2. Distributed Stampede Lock

On a cache miss, before regenerating an artifact, a runner must acquire a distributed lock scoped to the computed cache key. Any subsequent runner missing the same key blocks (with a bounded timeout) rather than independently rebuilding. This is the single highest-leverage change for reducing redundant compute during a CI/CD cache invalidation event, since it converts an N-way stampede into a single build plus N cheap cache reads. Redis with the Redlock pattern is the standard implementation for this at fleet scale.

1-- redis lua script: acquire_build_lock.lua
2-- Atomically acquires a lock or returns the holder's identity
3local key = KEYS[1]
4local token = ARGV[1]
5local ttl_ms = ARGV[2]
6
7if redis.call('EXISTS', key) == 0 then
8  redis.call('SET', key, token, 'PX', ttl_ms)
9  return 1
10else
11  return redis.call('GET', key)
12end

Runners that fail to acquire the lock poll the L2 cache on a short backoff interval, checking for the artifact written by the lock-holder, rather than retrying the lock itself. This decouples build latency from lock contention and prevents a secondary thundering herd against Redis.

#Pipeline Configuration Example

At the pipeline definition layer, the cache key and fallback restore keys should be explicit rather than relying on the CI vendor’s implicit hashing. Below is a GitLab CI example that layers a content-hash primary key with a broader fallback to avoid full cold-cache rebuilds during transient invalidation:

1build_service:
2  stage: build
3  script:
4    - CACHE_KEY=$(bash compute_cache_key.sh services/payments)
5    - ./scripts/acquire-build-lock.sh "$CACHE_KEY" || ./scripts/wait-for-artifact.sh "$CACHE_KEY"
6    - ./scripts/build.sh services/payments
7  cache:
8    key: "$CACHE_KEY"
9    fallback_keys:
10      - "payments-toolchain-v3"
11    paths:
12      - services/payments/dist
13    policy: pull-push

This structure ensures that when the primary content hash misses, the pipeline still restores a partially warm cache from the fallback key, reducing rebuild time even under active CI/CD cache invalidation rather than falling back to a fully cold build.

#Failure Modes and Edge Cases

Several failure modes emerge specifically from the coordination layer introduced above, and each requires explicit handling rather than being left to default timeout behaviour.

• Orphaned locks: if a runner crashes or is preempted (common on spot-instance-backed runner pools) after acquiring the build lock but before writing the artifact, the lock TTL must expire deterministically. Set the TTL slightly above the 99th-percentile historical build duration, never above the median, or you introduce artificial serialisation.
• Cache poisoning: a non-deterministic build step (embedded timestamps, unseeded randomness, ambient environment leakage) can populate the cache with an artifact that passes checksum validation but is functionally incorrect. Mitigate by enforcing hermetic build sandboxes and validating output determinism via reproducible-build diffing in a canary lane before promoting to the shared cache tier.
• Hash collisions at scale: SHA-256 collision probability is cryptographically negligible, but key truncation for storage efficiency is not. If a system truncates cache keys to reduce object store path length, verify the truncated space against your actual fleet cardinality; a birthday-bound collision at 200,000 unique keys per day is not theoretical at 64-bit truncation.
• Clock skew across regions: TTL-based invalidation depends on synchronised clocks. Runners in regions with NTP drift beyond a few hundred milliseconds can prematurely expire or extend locks relative to the coordination store’s clock, reintroducing stampede behaviour intermittently and non-reproducibly.
• Stale positive hits: if the content hash omits an input that genuinely affects the build (a transitively imported environment variable, an implicit compiler flag), the pipeline will confidently serve a stale artifact. This class of bug is the most dangerous because it fails silently rather than triggering a visible invalidation storm.

#Scaling and Security Trade-offs

Once the coordination layer is in place, the remaining decisions are about where to spend latency budget and where to spend security engineering effort. These trade-offs should inform your broader architectural patterns for build infrastructure, not just the cache subsystem in isolation.

• L1 vs L2 latency: local disk cache resolves in under 5ms; regional object store resolves in 20–80ms depending on payload size. At 500+ concurrent jobs, the L2 tier’s request-per-second ceiling becomes the binding constraint, not raw latency.
• Lock granularity vs contention: coarse-grained locks (per-repository) minimise Redis key cardinality but serialise unrelated builds; fine-grained locks (per-target content hash) maximise parallelism but increase coordination overhead and Redis memory footprint.
• Consistency vs cost: strongly consistent cache writes (synchronous replication before acknowledging) eliminate race conditions but increase write latency 2–3x versus eventually consistent regional replication.
• Signed manifests vs throughput: cryptographically signing every cache artifact (to prevent supply-chain injection into the shared L2/L3 tiers) adds measurable CPU overhead per write but is non-negotiable for any cache tier shared across trust boundaries or teams.
• IAM scoping: grant write access to the L2/L3 cache buckets only to the CI service identity, never to developer-assumable roles; read access can be broader. This limits the blast radius of a compromised developer credential to cache poisoning detection rather than direct artifact injection.
• TTL aggressiveness vs storage cost: short TTLs reduce object store cost but increase the frequency of CI/CD cache invalidation events and associated rebuild compute; long TTLs reduce compute cost but increase the risk of serving artifacts built against outdated transitive dependencies with known CVEs.

None of these trade-offs have a universally correct answer; they are a function of fleet size, monorepo topology, and how much of your build graph is genuinely deterministic. What is non-negotiable is that CI/CD cache invalidation must be treated as a coordination problem with an explicit locking protocol, not as a side effect of key hashing left to the CI vendor’s default implementation.