Reduce LLVM Build Artifact Storage Costs by 50% with Content-Defined Chunking¶
One of the classic strategies to speed up a system is to avoid redundant work. Scalable build systems like Bazel and Buck2 heavily employ this strategy in various ways, with remote caching and content-addressable storage being two prominent examples. While remote caching prevents repeating redundant build actions, content-addressable storage (CAS) exists for the purpose of data deduplication. However, traditionally CAS operates at the granularity of a single file. When you modify a single byte in a file and store it in a CAS, the CAS stores a second, complete file. Deduplication at the file level is quite palatable for smaller files; a single build invocation typically contains many thousands of small files. Who cares if we store a couple more?
However, as file sizes increase, the cost of storing yet another slightly modified version of a file becomes more expensive. Instead of tossing a couple extra kilobytes into storage, you might be storing a few more gigabytes. Now, consider where these large files come from. These large files are often outputs of build actions, and those build actions depend on many smaller inputs. As those many inputs churn, the outputs also churn. Suddenly the cost of touching a tiny little source file isn’t just the cost of uploading a new version of the source file to CAS–it’s now also the cost of all the large outputs that are produced by the build. This dictates the growth rate of your CAS storage costs, which scales directly with the number of incoming builds. At AI-scale, these costs have become more important than ever before.
So what to do? When the new versions of these large artifacts are vastly different there’s not much you can do. However, for some file types there’s a good amount of redundant data as files experience minor churn. For example, an unoptimized C++ “Hello, world!” binary is 99% unchanged when the message is changed to “Hello, new world!”. While that might seem contrived, consider a case where a conditional branch is tweaked slightly from > to >= in a library deep in your build graph. Deduplicating redundant data between large outputs can quickly compound into a lot of data savings!
Devising solid inter-file deduplication¶
To deduplicate redundant data across files, we need to come up with a strategy to increase the granularity with which data is handled. The naive solution to this problem is to just split files every, say, 1 MB–enough to have decent granularity within truly large files without introducing excessive reassembly overhead. Unfortunately, this strategy quickly falls apart; when bytes are inserted or removed, they shift the byte stream in a way that immediately obliterates the effectiveness of deduplication within these smaller slices. Surely there’s a better way…
Enter content-defined chunking (CDC). CDC splits a file into a chain of smaller files through an algorithm that makes the slice boundaries more resilient to minor data churn. The simplified description of how this works is that an algorithm uses a rolling hash over a file to identify split points through content fingerprinting, and large regions of identical content across different files tend to result in identical chunk splits. This means no awareness of preexisting data is required; the algorithm just takes advantage of how identical data streams produce patterns in rolling hashes. If you’re interested in the finer details, Josh Leeb-du Toit has an excellent series on content-defined chunking (including FastCDC specifically) that covers how these algorithms actually work.
For our interests, the outcome is simple: instead of minor changes invalidating the pool of chunks that make up a larger file, minor binary differences tend to only invalidate a few chunks surrounding the changed data. There’s no need to upload the unchanged chunks of the original file if they’ve previously been stored in a CAS.
With CDC offering better granularity for data deduplication, we just need to update the storage pipelines to handle this. Recently, explicit protocol support for CDC was added to the remote execution protocol used by Bazel, Buck2 and many other build systems that use remote caching and execution. This allows build systems to more efficiently send and receive data that has been split using a CDC algorithm.
The process of uploading data using CDC is pretty straightforward:
- Split the big file into smaller files (chunks) using CDC.
- Check to see which of the chunks aren’t yet present in the remote CAS.
- Upload new/missing chunks to the remote CAS.
- Upload an ordered list of chunks that defines how to reconstruct the original file through the CDC RPC methods of the remote execution protocol.
Retrieving data stored with CDC is roughly the same but in reverse:
- Fetch the list of chunks for the file you want.
- Download any chunks that aren’t cached locally.
- Reassemble the final file.
Not only does this save on external storage, it also improves network performance since, theoretically, less data will be transferred.
So how well does this work in practice?
A quick case study: LLVM¶
All tests for this section were performed with Bazel 9.1.1 using the FastCDC2020 algorithm against an EngFlow remote caching cluster.
As I’ve been building out EngFlow’s CDC support, I wanted to find an interesting example to use for early testing. In particular, I wanted something with many build actions that would produce rather large outputs in a realistic scenario. LLVM came to mind, and https://github.com/hermeticbuild/hermetic-llvm makes this pretty easy to do with Bazel. For this exploration, we’ll build a complete LLVM toolchain from source, and measure various dimensions of cache performance.
A few versions of Bazel (>=9.1.0, 8.7.0) include preliminary CDC support behind the --experimental_remote_cache_chunking flag, so I warmed up a remote cache with CDC enabled and tested a cached build of LLVM using --remote_download_outputs=all. While downloading all outputs isn’t necessarily practical or useful, I figured it’d give the best chance at showing successful deduplication.
Initial results with CDC on and off were comically unimpressive:
If that seems wrong to you, your intuition is correct. CDC relies on caching the chunks that make up the larger files. If the chunks aren’t cached, they’re re-downloaded every time for each larger file that reuses a chunk. This means you effectively end up downloading the same amount of data using a different set of RPCs. This first comparison was done without the --disk_cache flag which would’ve allowed Bazel to cache downloaded files (and action results) to a local directory. To actually get CDC savings, we need to enable the local cache.
With --disk_cache enabled, the download savings is with CDC is staggering:
But even still, this isn’t the full picture. While a large amount of redundant data is no longer downloaded, how much of that is because of CDC? What if we’re really just preventing copies of the same file from getting re-downloaded?
Adding --disk_cache without CDC enabled clarifies how much work is being done by the disk cache, and how much is due to CDC:
Now that’s more like it! Just turning on the disk cache does prevent a lot of redundant downloads, but CDC takes things a step further. We’re downloading 58% less data from our baseline, but more importantly we saved 36% versus just using a disk cache. This does tell us a bit about this scenario’s build graph: there are redundant copies of data throughout the graph that must be re-downloaded throughout the span of a build. Enabling CDC makes this process more efficient.
But all of the tests thus far were done with --remote_download_outputs=all, which downloads all intermediate stages of data in the build graph required to produce the final build artifact. A much more practical scenario would be to use --remote_download_outputs=minimal, which will only download enough of the cached toolchain build to compile the hello-world binary.
If we switch to downloading just the cached toolchain, the results aren’t nearly as exciting:
Now that we’ve excluded the intermediate artifacts, there’s not enough duplicated data throughout the toolchain to realize much gain from CDC. If a minor change was made to the toolchain and we re-downloaded it, CDC would likely have more of an impact as only the unique chunks would need to be downloaded. But that sidesteps the intent of this illustration: not all datasets will magically result in savings when CDC is enabled.
The practical ramifications¶
Now that we’re acquainted with what CDC does at a network data transfer level, let’s dive a little deeper into some of the more practical ramifications. While the examples above illustrate how much data we’ve downloaded, they don’t directly demonstrate how that relates to a developer’s experience.
While I was running these tests, I happened to be on a poor network connection, which meant that downloading all this data had a very real cost:
With CDC and a disk cache, the time difference between a full and minimal download of the cached build was significant, but not drastic. Not taking advantage of these optimizations puts the full cached build at nearly 37 minutes, which was slower than not using the cache at all.
Another side-effect of CDC is how interruptions are handled. When chunks are stored into a local disk cache, they don’t need to be re-downloaded. This means that resuming a download for a large file naturally takes advantage of the disk cache. Without CDC, if a long-running download is abandoned when a build is interrupted, the next build must restart the download from scratch. This perk comes for free for all data sets–even ones that don’t deduplicate well.
With that said, on a stable 1 Gbps wired connection, the equation is different. A full download of the cached LLVM build with neither disk cache nor CDC only takes several minutes. In that scenario, CDC savings are more impactful from the perspective of cluster-side efficiency.
Savings at the remote CAS level¶
But what about the top-level question? How much do we save in cluster-side storage when doing a clean build of LLVM? At first glance, less than we’d hope:
6% storage savings may seem small, but remember: this is over the span of a single build. CDC’s promise is to save more across incremental changes. Let’s see how this changes as we bump the version of LLVM:
And there it is; after the first build, each subsequent build results in a 50% data storage savings in the remote CAS. This is a significant reduction, and the value that a project sees here depends on the artifacts produced by the codebase. Some codebases may see larger savings, while others may see smaller savings. But the important result here is that we’ve changed the growth rate. At a scale of hundreds of builds per hour across a massive monorepo, savings of this kind are much more valuable.
So is CDC ready today?¶
The remote execution protocol changes and newly introduced Bazel support for CDC has brought a lot of attention to this subject recently. However, support for the new RPC methods isn’t necessarily a fundamental requirement to perform CDC: the underlying ByteStream service used for file transfer could just quietly do this in the background. The protocol changes simply pave the way for the client side benefits of more efficient local caching and network transfers.
At EngFlow, we’re looking at this functionality at a deeper level: we’ve made our CAS systems aware of data uploaded through CDC. Any client, CDC-aware or not, can download these chunked files using the standard ByteStream service. This makes it possible for a remote execution cluster to take advantage of CDC without any user-side changes. We’re very excited about CDC, and are in the midst of testing to ensure robustness as we evolve this work.
Still, CDC for remote build caching and execution is in its early days. In fact, I wanted to take a moment to highlight how quickly things have been changing:
- Bazel 9.1.0 first introduces CDC, but should not be used with CDC enabled. It lacks digest validation of reconstructed blobs, and so is not safe to use in a production environment. Bazel 9.1.1 includes a fix for this.
- While not directly related to CDC, in Bazel 9.2.0, the gRPC receive message size limit was removed. This allows Bazel to read chunked blobs over 32 GB from servers using the default CDC algorithm tunings.
- There is a proposal to replace the current CDC RPC methods in the remote execution API with streaming variants. This change seeks to improve client’s abilities to upload large chunked blobs to remote execution services with smaller gRPC receive limits.
- A PR introducing RepMaxCDC, another CDC algorithm, was recently proposed to Bazel. This algorithm boasts slightly improved chunk deduplication over FastCDC.
Over time, we expect CDC to be considered a basic requirement for all remote execution services. Today, we’re paving the way to bring content-defined chunking to a cluster near you very soon.