Bazel に、コンテンツ定義によるチャンキング機能が追加されました。

目的：変更されたバイトだけを移動させ、全体を再アップロードするのではなく。

BuildBuddy のリモートキャッシュでは、コンテンツ定義チャンキング（Content-Defined Chunking; CDC）を採用することで、大規模なビルド出力をより「差分ベース」で動作させるようにしています。バイナリ、バンドル、パッケージ、またはアーカイブがほとんど変更されていない場合、BuildBuddy は既存に認識済みのチャンクを再利用でき、ファイル全体を上書きアップロードしたりダウンロードしたりする必要がなくなります。 BuildBuddy 自身のリポジトリを対象としたベンチマークにおいて、バazel チャンキング実装の PR では、アップロードデータ量が 40%、ディスクキャッシュの使用量も 40% 削減したことが確認されています。BuildBuddy でのクライアントサイド CDC を有効にするには、Bazel 8.7 または 9.1+ を使用し、

--experimental_remote_cache_chunking

オプションを指定してください。

背景と課題

ビルドキャッシュの次の frontier は、アクションをスキップすることだけでなく、「バイト単位」でデータを変えずにキャッシュすることにあります。

ビルドキャッシュは長足の進歩を遂げてきました。コードの每次編集後に全ファイルを再構築するのではなく、Bazel とリモートキャッシングにより、チーム全体が CI ジョブや異なるマシンの間でもアクションの結果物を再利用できるようになりました。現実には、ビルドの負荷はレポジトリ全体のサイズオーダー $O(\text{size of repo})$ から、変更分のサイズオーダー $O(\text{size of change})$ へと移行してきています。しかし、「変更分のサイズ」という表現は誤解を招く可能性があります。真に重要なのは、その編集によって影響を受ける「伝播するアクションの総体積」です。ソースコードの小さな変更であっても、各出力の中で実際には小さな部分しか変わっていないにもかかわらず、多くのバイナリ、パッケージ、バンドル、その他大規模な出力へと影響が波及することがあります。

この無効化（Invalidation）は予期されることですが、ビルドシステムはそのアクションを再実行すべきであり、リモートキャッシュの課題は「次」に起こることです：キャッシュ側では新しいダイジェストを検出するため、そのファイルのほとんどが前のバージョンと同一であっても、バイト全体に対するダイジェストが一新されてしまいます。

伝播するアクション

リンキング、バンドリング、パッケージ化、アーカイブ作成などは、この問題が顕著に現れる領域です。これらはいくつかの伝播する入力（transitive inputs）を一つの出力に統合します。そのため、これは限られた数目的ファイルに対して直接動作するアクションとは性質が異なります。通常のコンパイルアクションは、より小さな直接依存関係を持つ入力セットを用いて単一のソースファイルをコンパイルしますが、伝播型アクションは多くの依存関係の蓄積された出力を消費し、一つの最終的なバイナリやバンドル、パッケージ、アーカイブを生成します。

Bazel のルールにおいては、これは通常、「転送 depset を通じてファイルを集約し、その蓄積セットを単一のアクションに渡す」という形で現れます。例えば、単純化されたコンパイルアクションは以下のようになります：

ctx.actions.run(    inputs = [src] + direct_headers,    outputs = [obj],    executable = compiler,    arguments = ["-c", src.path, "-o", obj.path],)

一方、バンドリングまたはパッケージ化アクションは概ねこのように見えます：

transitive_inputs = depset(    direct = direct_files,    transitive = [dep[MyInfo].files for dep in ctx.attr.deps],)ctx.actions.run(    inputs = transitive_inputs,    outputs = [bundle],    executable = bundler,    arguments = ["--output", bundle.path],)

この後者のパターンにおいて、ソースコードの小さな変更が大きな出力の変化に波及する現象が発生します。最終出力内でバイト列の一部のみが変更されても、出力ダイジェストは依然として新しいものになります。CDC を用いない場合、キャッシュ側はこれを完全に新しい(blob) と扱い、バイナリやバンドル、パッケージ、アーカイブの大部分が前バージョンとバイト単位で同一であっても、全体を新しいオブジェクトとして扱ってしまいます。もし多くの最終出力がその変更された入力に依存している場合、それら全てが新たなダイジェストを持ちます。

リモートキャッシングにおいて高コストとなるのは、単に出力が大きいためという点のみではなく、「既にキャッシュにあるものと非常に似通っているにもかかわらず、バイト全体に対するダイジェストが新しい」ことが含まれる点です。これは以下の 2 つの課題を生み出します：

アップロードとダウンロードでは、小さな部分だけが変更されても、データ全体を移動してしまいます。
ストレージ側では、バイトの大部分が重複しているにもかかわらず、別のデータ全体としての blob を保持し続けてしまいます。

回避策の一つとして、これらのアクションに対するリモートキャッシングを無効化するという方法があります。これは予期されるキャッシュヒットを得るために大規模な出力を上書き書くコストの方が不経済と判断された場合に有効ですが、別の問題を生みます：そのアクションは毎回実行される必要があり、また RBE（Remote Build Execution）がアクションの入力・出力の移動効率に依存しているため、アクションをリモート実行へ移行しづらくなる傾向があります。つまり、ビルドシステムは高コストなキャッシュ書き込みを回避する一方、データの再利用全体を見失うことになります。

ソースコードの小さな変更でも、最終的な伝播型アクションが無効化されてしまうのです。

ケーススタディ：Go テスト

代表的な例として、多くの他のライブラリ（

bar1

bar2

, ...,

barN

）が導入する共有された

go_library

（例えば

foo

）を想定します。各

bar

ライブラリにも独自の

go_test

が存在する場合があります。

foo

における実装コードみの変更であっても、通常は

foo

の自身専用の

GoCompilePkg

アクションだけを再ビルドすれば済み、下流のコンパイルアクションは Go コンパイルが直接依存関係からエクスポートされたデータ（例：

foo.x

）に基づいているため、キャッシュヒットすることが可能です。

しかしリンキングでは事情が異なります。各

go_test

にはテスト用バイナリが必要であり、これは

GoLink

アクションによって生成されます。このリンキングアクションは

foo.a

のような Go アーカイブの伝播セットを消費します。もし

foo.a

が変更されても、ソースやコンパイルアクション自体が変更されなくても、多数の下流テストバイナリが新たなダイジェストを持つことになります。最後に、

TestRunner

アクションはそれを実行するためにはそのテストバイナリを入力として必要とします。つまり、小さなソース編集が多数の新しいテストバイナリのダイジェストを生み出すことになります。これらのテストバイナリは通常サイズが大きく、かつ多くの場合、前バージョンと同じバイト列を持つものです。CDC を用いない場合、それぞれが個別に完全な blob として転送・保存されてしまいます。

これを出力の問題と捉える

一つの方法は、アクション自体を「漸進的（incremental）」なものとして設計することですが：漸進的リンキング、ランタイムリンキング、知的なバンドリング、知的なパッケージ化などです。しかしこれは通常非常に困難で、リンカーやツールの本身に大規模な変更が必要です。たとえ一つのツールでのみこの課題を解決できたとしても、

GoLink

、C++ リンカー、JavaScript バンドラー、アプリパッケージャー、生成されたアーカイブなど、大規模な出力を生成できるあらゆるアクションに対して別々の解決策が必要となり、これがスケーラビリティの観点で成立しません。

代わりに、これを一般的な「出力の問題」と捉えるアプローチがあります：これらのアクションは大きなファイルを作成し、その中でコンテンツが変化するのは一部に過ぎません。コンテンツ定義チャンキング（CDC）を用いることで、アクション自体に変更を加えずとも、そうしたアクションを漸進的に扱うことによる多くのメリットを実現できます。

コンテンツ定義チャンキング (CDC)

CDC は、固定されたバイトオフセットではなくファイルのコンテンツに基づいてファイルをチャンクに分割する反復可能なプロセスです。大まかに言えば、「小さな窓（window）サイズのデータに対してローリングハッシュを計算し、そのハッシュが稀なパターンに一致したタイミングで分割を行う」仕組みです。ハッシュは疑似的にランダムな振る舞いを示すためこの条件は間欠的にしか満たされませんが、プロセスは決定論的であり、同じコンテンツからは常に同じチャンク境界が生じます。

平均的なチャンクサイズを 512 KiB にしたい場合は、各バイトにおいて約 512 KiB の確率で一致するパターン（例：$1/2^{19}$）を選択します。パターンが一致しなければウィンドウをずらして再試行し、結果として時間経過とともに望む平均的なチャンクサイズを得つつ、境界は常にコンテンツ定義のまま保つことができます。チャンクサイズが小さくすれば重複排除（deduplication）の効率は向上しますが、メタデータオーバーヘッドと RPC コストが増大するため、CDC の実装ではチャンクサイズと効率性のバランスを取る必要があります。

単純な例を挙げると、ローリングウィンドウの幅を 4 バイトとし、その 4 バイトのハッシュが末尾

で終わるたびに分割すると仮定します（具体的なハッシュ値は問わない）：

オリジナル:
```
aaaabbbbccccdddd
```
- ウィンドウ:
```
_bbbb_
```
  ,
```
_cccc_
```
  （どちらもパターンに一致）
- 分割点:
```
aaaa|bbbb|cccc|dddd
```

もし

bbbb

の中にいくつかのバイトを挿入した場合、近傍のウィンドウは変更され、そのチャンクも変化します：

アップデート:
```
aaaabbXXbbccccdddd
```

しかし、ローリングウィンドウが挿入されたバイトを過ぎた後、再び

cccc

に到達した際には、以前と同じ 4 バイトシーケンスを検知します。このシーケンスは同様のハッシュを生むため、アルゴリズムは以前の分割点と同一の位置を特定します。その後のチャンクは同じ境界とハッシュを保持し続けます。

実際の CDC ではより大きなローリングウィンドウとさらに稀な分割パターンを使用しますが、考え方は全く同様です。つまり、ファイルの所々に数バイトが追加または削除された大規模ファイルであっても、通常はその近傍のチャンクのみが変更され、ローリングウィンドウが変更されたバイトを過ぎた後再び不変のコンテンツに到達すると、以前のバイトシーケンスと同様のものを見るようになり、将来の分割点も同様に特定できます。

一般的な CDC アルゴリズムの一つに FastCDC があります。FastCDC のプレゼンテーションスライドは、視覚的な概要としても非常に有用です。 CDC を用いると、変更されたチャンクのみを上書きアップロードすればよいのです。

これがリモートキャッシングにどう役立つか

アクションが

GoLink

や

CppLink

といった大規模な出力を作成する場合でも、小さな入力の変更であっても、以前のものと大部分同一の新しい出力が生み出されることがあります。CDC を用いると、キャッシュはその出力をチャンクに分割でき、多くのチャンクが既に存在していることを発見できます。アップロード全体を再行する必要はありません；欠落したチャンクのみを上書きアップロードすればよいのです。これは特に CI や開発者ビルドにおいて効果的です： Nearby のコミットは、大規模な変化を生み出すことよりも、大部分類似した出力を生み出す傾向にあります。一度チャンクがアップロードされると、将来のビルドで関連する出力間で再利用できます。

出力の大部分も、既にキャッシュにあるチャンクにマッピング可能です。

成果

この直近の期間において、CDC は BuildBuddy キャッシュ書き込み対象のデータ全体の約 85% を重複排除（デダップ）することに成功しました。言い換えれば、大規模な出力に対する書き込みのほとんどは再利用可能なチャンクとして既に存在しており、残りの変更されたチャンクのみをアップロードするだけで済みました。

この 2 週間の期間では、CDC はライターのパスにおいて約 300 TiB の重複チャンクデータをアップロード処理からスキップしました（ピーク時に時速 4 TiB 以上）。これは BuildBuddy が管理するキャッシュ書き込みとエグゼキュータ出力アップロードにおける書き込み側チャンクデダップの成果です。読み取り側の節約（ディスクキャッシュやリージョナルキャッシュ、またはエグゼキュータファイルキャッシュからチャンクをサービスする場合）を含めないため、総体的なネットワークコスト削減はさらに大きいはずです。プロダクション環境では、すでに数百 TiB の重複チャンクアップロードが回避されています。BuildBuddy が保持する重複データ量が減少したため、実効的なキャッシュ保持期間も改善しました。

Bazel 実装の PR ベンチマーク（BuildBuddy リポジトリの 50 コミットを対象）では、約 40% のアップロード削減、約 40% のディスクキャッシュ縮小、およびベンチマーク内でのビルド速度向上が確認されました。現在 BuildBuddy は、2 MiB より大きな blob に対してチャンキングを適用しています。あるテストでは対象の 4.2% のオブジェクトだけがその閾値を超えていたため、大半の blob はチャンキングされていませんでした。その対象となるサブセット内では、CDC が書き込まれたバイトの約 85% を重複排除しました。キャッシュトラフィック全体で見ると、総体的な節約効果は通常 20〜40% の範囲にあります。

大まかな経験則として、CDC は「サイズが大きく、バージョン間のバイト安定性が高い出力」において最も効果的です。リンキングやバンドリングはこの点に優れた適性を示し、大半の大規模な出力もその大部分を再利用します。圧縮されていない場合はバンドリングも好適ですが、出力が圧縮化・オブリフュスケート（難読化）またはランダム化された場合でも同様です。圧縮自体は悪くありませんが、通常では churn（変動）が増大する傾向にあります。

tar.gz

アーカイブや Docker イメージ層といった圧縮形式は、小さな入力の変更でコンプレッストされたバイトストリームの大部分を再書き込む可能性があるため、チャンク化しにくいという特徴があります。重要な属性はファイル拡張子ではなく、バイトレベルでの類似性です。

実装

エンドツーエンドでこの仕組みを実現するには、変更が以下の 3 点にまたがる必要があります：

リモート API: クライアントとキャッシュ間においてチャンクに関する対話を可能にするため、共有された
```
SplitBlob
```
/
```
SpliceBlob
```
プロトコルを定義します。
BuildBuddy: サーバーサイドのキャッシュ振る舞いと、エグゼキュータでのチャンキングアップロード・ダウンロードを実装します。
Bazel: クライアントサイドの複合キャッシュパスを実装し、ローカルディスクキャッシュとリモートキャッシュがチャンクを共有できるようにします。

リモート API: Split と Splice

CDC をリモートキャッシングに有用にするためには、クライアントとサーバーはバイト全体ではなく「チャンク」について対話する手段を持つ必要があります。これは特にネットワークがボトルネックとなる場合に重要です：低速なネットワーク、VPN を使用しているユーザー、あるいはキャッシュへのレイテンシーが高いユーザーは、その出力の大部分が既にどこかに存在する場合でも、完全に新しい大規模な出力をアップロード・ダウンロードする必要がないようにすべきです。代わりに、クライアントは blob がどのチャンクにマッピングされているかを検知し、ローカルに既に存在するチャンクを確認し、欠けている部分のみを転送すればよいのです。

これが

SplitBlob

と

SpliceBlob

の役目です。

SplitBlob は読み込み側の API です。大規模な blob のダイジェストが与えられた場合、クライアントはキャッシュにその blob に関するチャンクレイアウトを知っているかを問い合わせています。もし分かっていれば、クライアントは既に持っているチャンク以外のもののみをダウンロードできます。
SpliceBlob は書き込み側の API です。アクションが大規模な出力を作成した後、Bazel またはエグゼキュータは欠けているチャンクをアップロードし、キャッシュにそれらのチャンクから全体を再構築する方法を伝達します。キャッシュはその再構築メタデータを保存するため、将来同じ blob ダイジェストに対する
```
SplitBlob
```
コールがチャンクレイアウトを返せます。

読み込みのパスは以下となります：

```
SplitBlob
```
を呼び出して大規模な blob のチャンクレイアウトを取得する。
ローカルキャッシュにどのチャンクが存在するかを確認する。
欠けているチャンクを
```
Read
```
または
```
BatchReadBlobs
```
でダウンロードする。

書き込みのパスはその逆です：

大規模な出力を生み出した後、クライアントまたはエグゼキュータが CDC アルゴリズムを実行し、チャンク境界とダイジェストを計算する。
```
FindMissingBlobs
```
を呼び出してキャッシュが欠けているチャンクを確認する。
```
Write
```
または
```
BatchUpdateBlobs
```
で欠けているチャンクのみを上書きアップロードする。
```
SpliceBlob
```
を呼び出して再構築メタデータを保存する。

このモデルでは、チャンクはそのダイジェストの下で通常の CAS blob として格納されます。再構築メタデータは元の大きな blob ダイジェストから派生したキーに基づいて管理されるため、将来の

SplitBlob

コールは既に知っているダイジェストから始めてチャンクレイアウトを検出できます。また、これはストレージの分散化にも寄与します：非常に大きなオブジェクトを indivisible なキャッシュエントリとして扱うのではなく、キャッシュは他の blob と同様に CAS 上で小さなチャンクとして保存・サービスできます。

Bazel の複合キャッシュ (Combined Cache)

Bazel は CDC を複合キャッシュ内で実装し、リモートキャッシュとディスクキャッシュの読み書きを調整します。リモートキャッシュがチャンキングサポートを提供すると、Bazel はチャンキング付きのアップロード・ダウンロードパスを作成します。サーバーから提供された閾値以上の大規模な blob はチャンキングパスを使用し、それ以下の小さな blob は通常のキャッシュパスをそのまま使用します。

実装上の重要な点として、Bazel は各チャンクの 2 つのコピー（メモリ上）を保持する必要はありません。出力は既にディスク上に存在するため、アップローダーは元のファイルをチャンクデータのソースとして利用でき、アップロード時に必要なバイト範囲だけをストリーミングさせることができます。同様に、クライアントも元のファイル内のバイト範囲を保ち続け、各チャンクの 2 つのコピーを保持しなくて済みます。

BuildBuddy の実装

BuildBuddy ではサーバーサイドとエグゼキュータで CDC を実装しています。

サーバーサイド

サーバーサイドでは

SplitBlob

と

SpliceBlob

を実装します。チャンクはそのダイジェストをキーとして通常の CAS エントリとして格納され、再構築メタデータは元の blob ダイジェストから派生したキーの下で個別に保存されます。

SpliceBlob

が呼び出された場合、BuildBuddy はチャンクの存在を確認し、それらを連結して元の blob ダイジェストを生成することを検証します。この処理がキャッシュ API の背後で行われるため、BuildBuddy は大規模な読み書きにおける転送量を削減しつつ、既存の非チャンキングキャッシュパスも引き続き動作させることができます。サーバーサイドのキャッシュパスでは、既に存在するチャンクをスキップし、欠けているチャンクのみを移動させ、それらのアップロードを並列で行います。

エグゼキュータ

エグゼキュータはアクション出力の大規模なデータをそのままチャンキングして直接アップロードできます。エグゼキュータは出力を通常通りトラバースし、交渉されたチャンキングパラメータを用いて大規模ファイルのチャンクダイジェストを計算し、

FindMissingBlobs

を呼び出して欠けているチャンクのみをアップロードします。アップローダーはメモリ内に 2 つの完全なコピーを保持する代わりに、必要なバイト範囲を元のファイルから読み込み、チャンクを並列にアップロードできます。これにより、CDC は複数のホップ（Bazel クライアント → BuildBuddy、エグゼキュータ → BuildBuddy、サーバー内キャッシュトラフィック）で役立ちます。ネイティブの Split/Splice 対応クライアントはエンドツーエンドのチャンキング転送が可能になり、既存のクライアントでも通常のキャッシュ API を引き続き使用できます。

利用可能性

Bazel に対する CDC サポートは bazelbuild/bazel#28437 で導入され、リモートキャッシング用の CDC は Bazel 8.7 および 9.1+ で利用可能です。 BuildBuddy を使用する Bazel クライアントは、以下のコマンドでローカルクライアント側でのアップロード/ダウンロードの節約をオプトインできます：

bazel build //... --experimental_remote_cache_chunking

現在 BuildBuddy サーバーでは、サーバーサイドキャッシュパスを通過する大規模なファイルに対して CDC が有効になっています。セルフホストされたエグゼキュータユーザーは完全な CDC 恩恵を受けるには BuildBuddy エグゼキュータ v2.261.0 以上を実行する必要があります。エグゼキュータ設定は不要で、CDC に適する実行リクエストを指定することで自動的に有効になります。

おわりに

CDC は、開発者が日常的に行っていること——大規模なコードベースに対して小さな変更を加えることで、時に大規模な出力を生み出すこと——においてリモートキャッシングをより良くします。同じバイトを再度アップロード・ダウンロードする代わりに、BuildBuddy と Bazel は未変更のチャンクを再利用できるようになり、キャッシュ転送量を大幅に削減できます。

今日から

--experimental_remote_cache_chunking

を BuildBuddy のキャッシュ有効な Bazel ビルドに設定し、Bazel 8.7 または 9.1+ で試してください。

さらに読む・参考文献

Bazel と BuildBuddy:

Bazel 実装 PR
推奨される Bazel パフォーマンスフラグ
BuildBuddy リモートビルド実行 (RBE)
Bazel リモートキャッシング

リモート API:

リモート実行 API:
```
SplitBlob
```
と
```
SpliceBlob
```
元の
```
SplitBlob
```
と
```
SpliceBlob
```
API を追加した PR
```
SplitBlob
```
と
```
SpliceBlob
```
のアップデートを施した PR
キャッシュチャンキング設定を追加した PR

コンテンツ定義チャンキング:

FastCDC, USENIX ATC 2016
FastCDC 2020, IEEE TPDS
Rabin Fingerprint
Google cdc-file-transfer