Scaling the CAS

Who this is for: you run a CAS that real builds depend on, and it is running out of disk, running out of throughput, or both. What you'll have at the end: a store composition sized for your load, an eviction policy that doesn't thrash, and a clear-eyed view of what running more than one CAS process costs. Time: an afternoon to size and tune; longer if you go horizontal.

Scaling workers is the straightforward half of capacity. This is the other half, and it is a different problem: a worker holds nothing, so adding one is free. The CAS holds everything, so adding one is a design decision.

Start here: a CAS process is not stateless

Most guidance about scaling services assumes replicas are interchangeable. For NativeLink's CAS that assumption is wrong in five specific places, and every horizontal-scaling decision on this page follows from them.

In-flight resumable uploads live in one process. The ByteStream service keeps a registry of active uploads keyed by the upload's UUID, in memory, per process.

When a client asks QueryWriteStatus to resume an interrupted upload, the server looks the UUID up in that map. If the request lands on a replica that never saw the upload, the lookup misses, the fallback checks whether the blob is already complete in the store, and on a miss the client is told to start over from byte zero. The source comment at that branch says so in as many words. A large blob interrupted at 90% and resumed against a different replica is re-uploaded in full.

LRU state is per process. The eviction index (recency ordering, running size total, entry count) belongs to the process that built it.

Two replicas over the same logical dataset make independent eviction decisions and diverge.

The existence cache produces stale positives. An existence_cache store remembers "this digest exists" in memory and is invalidated by its backend's remove callbacks. Those callbacks are in-process for a filesystem or memory backend, and there is no cross-process path at all for S3, GCS or Azure, so a blob removed underneath one replica (an object lifecycle rule, another replica's eviction, an operator) leaves the other replicas answering "present". The client skips the upload, and a later fetch fails. The one backend with a cross-process signal is Redis: with notify-keyspace-events set to include K and A, every process subscribed to the store hears Redis-side evictions and TTL expiries and drops the entry.

A filesystem store cannot share a directory. Two processes pointed at the same content_path each build their own index at boot and each unlink files the other believes it owns. This is not a supported configuration.

Read deduplication is intra-process only. fast_slow collapses concurrent reads of the same digest into a single fetch from the slow tier, but only within one process. Three replicas asking for the same cold blob at once make three requests to S3.

It has no leader election, no gossip, no Raft or quorum protocol, no etcd and no ZooKeeper anywhere in NativeLink. Replicas are independent processes, and any coordination between them has to come from the semantics of the shared backing store you point them at.

Scale vertically first, by composing

The store graph is where most capacity problems are solved, and it is cheaper than adding processes because it changes nothing about consistency. Compose stores is the reference for the wrappers; what follows is which one relieves which pressure.

Three details of composition matter for capacity specifically and aren't apparent from the individual recipes.

fast_slow populates the fast tier on a read miss, streaming from the slow store to the caller and into the fast store at the same time. That's what makes the hot tier fill itself. It also means a single large cold blob can evict a lot of hot working set, which is what bypass_dedup_threshold_bytes is for: at or above that size the read goes straight to the slow store and does not populate. It defaults to 0, which disables the bypass.

size_partitioning splits at size, exclusive on the low side: a blob of exactly that many bytes goes to the upper store. It also rejects non-digest keys outright, so it must not sit anywhere string-keyed traffic flows.

A memory store silently drops blobs at or above its max_bytes. The write is skipped with a log line rather than an error, and the blob is served from the backing store instead. If a memory fast tier appears to be doing nothing, this is usually why.

Eviction is your capacity control, and its default thrashes

Four fields, all on EvictionPolicy, all defaulting to 0, and 0 means disabled in every case. A policy with no fields set is an unbounded store.

eviction_policy: {
  max_bytes: 500000000000,
  evict_bytes: 50000000000,
  max_seconds: 2592000,
  max_count: 0,
}

max_bytes is the ceiling. evict_bytes is the low watermark: when eviction triggers, keep going until the store is down to max_bytes - evict_bytes. max_seconds expires entries by age since last access. max_count caps the number of entries.

Two more behaviours to plan around:

No background eviction timer exists. Eviction runs on inserts and removals (and when a worker releases a lease on an input it was using). Reads perform a lazy per-key expiry check on the key being read and nothing else. The consequence is that an idle store never shrinks; a CAS that goes over quota and then stops receiving writes stays over quota, and max_seconds only takes effect on entries someone happens to ask for.

Eviction is whole entries, one at a time. It does no partial or chunked eviction; the unit is one blob, or one file for a filesystem store.

Size the AC and the CAS together

The Action Cache is just another store with its own EvictionPolicy; there is no separate mechanism. The shipped examples give it roughly a twentieth of the CAS budget, which is a reasonable starting ratio because AC entries are tiny.

That asymmetry creates the hazard. AC entries are small and survive eviction readily; the CAS blobs they point at are large and get evicted first. The result is an AC hit that resolves to missing content. completeness_checking exists precisely for this: it re-queries the CAS on every AC read and treats an incomplete result as a miss. It costs a CAS round trip per AC hit, and on a shared production cache it is worth it.

Sharding, and what changing it costs

shard distributes keys across several backends by hash, with an optional integer weight per shard. The weights are turned into a cumulative table over the u32 space at startup and the key is binary-searched into it.

Two properties decide whether it fits.

Placement includes the blob's size. The hash folds the digest and its declared size, so the same content at a different declared size lands in a different shard. This is fine (it's still deterministic), but it means you cannot reason about placement from the hash alone.

Nothing rebalances. No migration, no virtual-node consistent hashing, no read repair, no re-shard command. Adding, removing, or reweighting a shard moves the boundaries and remaps a large fraction of keys. The data is still physically where it was written; lookups just go somewhere else and never find it.

Sharding is the right tool when one backend is genuinely the ceiling: a single Redis instance's memory, one filesystem's IOPS. It is the wrong tool for capacity you could have bought by pointing at object storage instead.

Going horizontal

Everything above scales one process. If you have exhausted that, here is the order to add replicas in.

1. Move the backing store off local disk first. Replicas only make sense over storage they can share: S3 or a compatible object store, GCS, Azure, or Redis. A filesystem store cannot be shared between processes at all, so this is a prerequisite rather than an optimisation. S3 and compatible and Redis are the recipes.

2. Keep the per-replica fast tier local and private. Each replica gets its own fast_slow hot tier on its own disk, pointed at the shared slow store. This is the topology that works: shared truth underneath, independent caches above. Accept that the hot tiers diverge; they are caches of a cache.

3. Remove existence_cache from the replicated path, or accept that it will serve stale positives. No cross-process invalidation exists except for a Redis backend with keyspace notifications enabled. If FindMissingBlobs latency is why you wanted it, a fast_slow hot tier gets you most of the same benefit without the correctness hazard.

4. Make ByteStream uploads sticky. Configure your load balancer for session affinity so a client's upload stream and its QueryWriteStatus resume reach the same replica. Without it, every interrupted large upload restarts from zero. This is the single most common way a horizontally scaled CAS gets slower rather than faster.

5. Set readiness to account for the startup scan. A filesystem store scans its entire content_path at boot and builds its index before the process binds any socket. During that window there is nothing to connect to: not a degraded service, an absent one. The window grows with the number of files on disk, so give readiness and liveness probes an initial delay that reflects a full cache, not an empty one.

6. Scale in slowly, and prefer fewer larger replicas. Removing a replica throws away a warm fast tier that took hours to fill, and the actions that would have hit it now go to the slow store. The CAS is the opposite of the worker pool here: generous, patient, and biased toward vertical growth.

7. Only then consider shard, and only if a single shared backend is provably the ceiling. Re-read the cache-flush warning above before you commit to a shard count.

The ceilings you hit before you expect to

File descriptors, at 80% of what you configured. global.max_open_files defaults to 24576, and the process reserves a fifth of it for sockets and pipes, so the effective permit budget is about 19660.

Every filesystem operation that goes through the store's file helpers takes a permit, including metadata-only ones such as metadata, read_dir and rename. (The startup scan is the exception: it holds one permit for the directory handle and runs its 200-way parallel stat outside the semaphore.) Network sockets are not counted by this semaphore but are counted by the kernel, so the kernel's limit must exceed max_open_files plus your expected connection count.

One connection per gRPC endpoint. A grpc store's connections_per_endpoint defaults to 1, so all traffic to a remote store multiplexes over a single HTTP/2 connection. On a busy CAS-of-a-CAS topology this is usually the first thing to raise.

Redis permits and pool size. max_client_permits defaults to 500 in-flight operations and connection_pool_size to 3. The permit cap exists specifically to stop timeouts from unbounded in-flight work, so raise it deliberately rather than reflexively.

Object-store upload concurrency. multipart_max_concurrent_uploads defaults to 10 per request, with a 5 MB retry buffer per request.

Message size, which is not a blob size limit. The HTTP listener's max_decoding_message_size defaults to 4 MiB and bounds a single decoded gRPC message, so it caps BatchUpdateBlobs, not ByteStream. No configuration anywhere caps how large a blob a CAS will accept over ByteStream. Capacity is bounded by eviction and disk, not by an upload check.

Tuning has the full lever table for the storage path, including evict_page_cache and its caveat.

Metrics: nothing is on by default

This is the finding most likely to catch you out while you're trying to measure any of the above.

NativeLink defines a full set of cache instruments: operation duration, operation counts by result, bytes in and out, item size distribution, and (declared but never emitted) current size and entry count.

No store emits any of them unless you explicitly wrap it in the cache_metrics store. That wrapper is the only caller of the instruments, and the design is deliberately opt-in so unwrapped stores carry no timers or attribute allocation in their hot path. None of the shipped deployment configs wrap anything (the only cache_metrics block in the tree is in the config-parser coverage fixture nativelink-config/examples/stores-config.json5), so out of the box an operator gets zero hit rate and zero latency data.

{
  name: "CAS_MAIN_STORE",
  cache_metrics: {
    cache_type: "cas",
    backend: {
      // the composition you would otherwise have written here
    },
  },
},

Wrap the layer whose behaviour you want to see, and give each one a distinct cache_type; the recording rules group by it.

deployment-examples/metrics/prometheus-recording-rules.yml defines a nativelink_cache group that is genuinely useful once metrics are flowing: nativelink:cache_hit_rate, latency at p50/p95/p99, nativelink:cache_eviction_rate, read and write throughput, and nativelink:cache_error_rate. The same group also defines nativelink:cache_size_bytes and nativelink:cache_entry_count, which are built on the two instruments nothing emits and will stay empty.

Observability covers getting the telemetry out of the process at all, which is the prerequisite for any of this.

What the repository actually ships

Being explicit, because the gap between the examples and a production CAS is wide.

Every shipped deployment runs exactly one CAS process. The docker-compose single-node example, the multi-worker compose example, and the Kubernetes manifest all have one. docker-compose-multi-worker.yml replicates workers against one cas-server; the only thing replicated anywhere in the repository is the worker pool.

No multi-replica CAS example exists, no load balancer or Service fronting several CAS pods, no HPA for the CAS, and no readiness gate accounting for the startup scan. Anyone scaling the CAS horizontally is operating outside every path this repository exercises.

The Kubernetes example stores the CAS in the container. kubernetes/nativelink/nativelink.yaml is a single Deployment with replicas: 1, and its filesystem store points at a path under /tmp inside the container: no PersistentVolumeClaim, no StatefulSet, not even an emptyDir. Every pod restart wipes the CAS and the AC. It is a demo topology, and the composition inside its config is worth reading even though the storage isn't.

Sharding has no deployment example. The only shard block in the tree is a single-shard entry in a config-parser coverage fixture, which exercises no distribution behaviour at all.

The cas-data volume in the multi-worker compose file is vestigial. It is mounted into the CAS server and into all three workers at the same path, but the workers' config points their fast tier somewhere else entirely and reaches the CAS over gRPC. Don't read that mount as an endorsement of sharing a filesystem store directory between processes; it isn't one.

When it doesn't work