Shared Build Cache Design: Action Keys, Content Store, and Eviction

A build cache that works for one developer on one machine and a build cache that works for a fleet of ephemeral workers are different systems. The single-machine version can keep everything forever and never evict; the fleet version must bound its size, survive concurrent writers, and remain correct while entries disappear underneath it. The design that satisfies all three is not one cache but two, with different keys, different lifetimes, and different consistency requirements.

Two stores behind one lookup

The first store answers “has this exact computation been done”. Its keys are action keys derived from inputs, toolchains, and configuration, and its values are small records listing the output digests. This store is a mapping and is therefore mutable: an entry can be replaced, invalidated, or evicted without affecting anything else.

The second store answers “give me the bytes named by this digest”. Its keys are content digests and its values are blobs. This store is write-once: a blob under a digest either exists with exactly those bytes or does not exist. Immutability removes the need for consistency protocols on writes, which is the reason the split exists. Two workers that upload the same blob simultaneously are not in conflict; both writes produce the same bytes, and the store can accept the second as a no-op.

The lookup protocol follows the split. Fetch the action record; if absent, the build runs and uploads. If present, read the output digests, fetch each blob, verify each digest, and use the result. The verification step is not optional, because the action record is metadata that could be stale while the blobs are immutable; a record pointing at a digest that no longer exists is a normal state after eviction and must be treated as a miss rather than an error.

Splitting also produces the property that makes the cache efficient: identical outputs are stored once regardless of how many action records point at them. Two branches that differ in a comment produce different action keys for the compilation of that file and the same output blob only if the compiler is insensitive to the comment, which it usually is not. Where deduplication actually pays is across near-identical builds and across the shared portions of many artifacts, which is a smaller fraction than intuition suggests and the reason cache size estimates derived from action counts are usually wrong.

Granularity, chunking, and the cost of large blobs

Blob size distribution determines what the storage layer must be good at. A cache for a large C++ or Rust codebase holds many small object files and a few large linked binaries; a cache for a container build holds a few very large layers.

Small blobs are metadata-bound. At a few kilobytes each, the request overhead and the metadata store dominate, and the practical optimizations are batching multiple digest lookups into one request and a compact existence filter so that a missing blob is discovered without a round trip per digest. The filter must be treated as a hint only: a false positive costs one wasted lookup, and a false negative would be a correctness bug, so the design always confirms against the store before reporting a miss on the fast path.

Large blobs are transfer-bound and, in a remote cache, the transfer may exceed the value of the hit. A cache that returns a two-gigabyte link output to save a four-minute link spends a minute of network to save three, and the accounting has to be per blob rather than per hit. Some caches decline to store blobs above a configured size for exactly this reason, and the configuration is a policy decision about the ratio of transfer cost to recomputation cost, not a technical constant.

Chunking addresses the large-blob case by splitting content into pieces at boundaries chosen from the content itself, so that an insertion near the beginning shifts only the chunks after it rather than all of them. Fixed-size chunking does not have this property: a one-byte insertion at offset zero changes every chunk. Content-defined boundaries are derived from a rolling hash over a window of bytes, with a target chunk size on the order of tens to hundreds of kilobytes; the exact parameters trade chunk count against deduplication ratio. The technique comes from backup and synchronization systems, and it applies to build outputs because build outputs are versioned large files.

Eviction under a size bound

A cache with a size limit must choose what to discard, and every policy is a bet about the future. The policies in use differ in which history they keep.

Least recently used discards the entry whose last access is oldest. It is the default because it is cheap to implement and behaves well on the access patterns that caches usually see, where recency predicts reuse. Its failure mode is the scan: a workload that touches a large number of entries once evicts the entire working set. A pipeline that rebuilds a release branch by recompiling everything does exactly this to a cache that has been keeping the development branch warm.

LRU-K counts the K most recent accesses and discards the entry whose K-th most recent access is oldest, so an entry must be accessed K times before it is protected. K=2 is the common choice and requires tracking two timestamps per entry rather than one. The cost is the bookkeeping; the benefit is resilience to scans, which is precisely the pattern a pipeline’s occasional full rebuild produces.

Frequency-based and segmented policies generalize the same idea. Segmented LRU keeps a probationary segment for entries seen once and a protected segment for entries seen twice, admitting new entries to the first and promoting on a second access. This approximates K=2 access counting with less metadata per entry.

Time-based expiry is orthogonal and useful for correctness rather than capacity. Entries whose validity is bounded by something external, such as a dependency that changed without the key changing, can be given a TTL as a safety net. The TTL is a statement that the key is known to be incomplete, which is a reason to fix the key rather than to rely on the TTL, but the TTL does limit the damage in the meantime.

The optimal policy for a known future access sequence discards the entry used furthest in the future, and it is unimplementable because the future is unknown. Its value is as a bound: a policy that keeps entries that will be accessed again within the window it has room for is doing about as well as possible, and the practical question is whether the working set of the pipeline fits.

Sizing, hit ratio, and the counter-metric

The working set is the set of entries touched between two uses of the same entry. If a pipeline’s entries are reused within the same day and the cache can hold a day’s worth, the hit ratio is high; if the cache holds an hour’s worth, the entries from this morning are gone. Since the working set changes with the pipeline’s behaviour, sizing is iterative: measure the hit ratio as a function of cache size, find the knee, and stop there.

The hit ratio alone is a misleading target. A cache that serves many tiny hits and no large ones has a high hit ratio and saves little time. The metric that corresponds to the pipeline’s wall clock is the recomputation time avoided, computed per hit as the duration the action would have taken, and aggregated. Two figures are needed for every cache decision: the fraction of lookups that hit, and the sum of the durations avoided. A change that improves the first while worsening the second is a regression.

Mirroring the hit ratio is its counter-metric: the cost of the cache. Storage for blobs, bytes transferred on upload and download, and the request rate on the metadata store. A cache can be made to hit on everything by storing everything, and the resulting transfer volume may cost more than the rebuilds it prevents.

Concurrency, and the fact that a cache is a hint

Two workers computing the same action at the same time both run it and both upload the same outputs. This is wasted work, and preventing it requires either a lock, which makes a failed worker block its peers, or request coalescing by key, which is a distributed single-flight. The common choice is to accept duplicate computation: the cost is bounded by the degree of concurrency, the alternative introduces a failure mode where a crashed worker holds a lock that must be detected and released. A build cache should never be on the critical path to correctness.

The related pathological case is the hot key that expires or is evicted and is then requested by every worker at once, each of which recomputes it. With eviction based on recency, hot keys are the last to go, so the case is rare; when it happens, the cost is a burst of duplicate work proportional to concurrency, which is bounded and self-limiting.

The governing contract is that every cache operation can fail and the build must proceed. A miss, an eviction during a read, a timeout, an unavailable service: all have the same remedy, which is to run the action. Designs that violate this by treating the cache as required infrastructure convert a performance dependency into an availability dependency, and the pipeline then fails for a reason unrelated to the code it is building.

from collections import OrderedDict

class SizeBoundedLRU:
    # Sketch of the eviction core. A real service adds per-tenant quotas,
    # a separate metadata store, and byte accounting for in-flight uploads.
    def __init__(self, capacity_bytes: int):
        self.capacity = capacity_bytes
        self.used = 0
        self.entries = OrderedDict()      # key -> size

    def get(self, key: str):
        if key not in self.entries:
            return None
        self.entries.move_to_end(key)      # most recently used at the end
        return key

    def put(self, key: str, size: int) -> None:
        if size > self.capacity:           # never admit an entry that cannot fit
            return
        if key in self.entries:
            self.used -= self.entries.pop(key)
        while self.used + size > self.capacity and self.entries:
            _, evicted_size = self.entries.popitem(last=False)
            self.used -= evicted_size
        self.entries[key] = size
        self.used += size

Two details in that sketch correspond to real design decisions. The refusal to admit an oversized entry prevents a single artifact from flushing the cache, and the eviction loop runs before the insert so that the cache never transiently exceeds its bound, which matters when the bound is a hard quota at the storage layer rather than a target.

Where the cache stops paying

A cache is a bet that recomputation is more expensive than storage and transfer. That bet is wrong in specific cases: outputs that are cheap to produce and large to store, actions whose inputs are so volatile that their keys never repeat, actions whose correctness depends on an input the key cannot capture, and pipelines whose total work is small enough that the cache’s own latency dominates. The fingerprint of an over-cached pipeline is a high hit ratio on trivial actions and a wall clock that does not improve, which is why the avoided-duration metric is the one to watch.

The one thing a shared cache cannot do is fix an incomplete key. It will faithfully return whatever was stored under the key it was given, including a result produced from a source the key did not describe. Making the key complete is a build-definition problem, covered in What a Build Cache Key Must Cover, and making the entries that the key may return trustworthy is a policy problem, covered in Trust Boundaries in Shared Build Caches. The cache service’s job is to be fast, bounded, and correct about the bytes it holds, and to do nothing else.