コンテンツ定義型チャンク分割によってバックアップデータの重複をどのように削減できるか？

コンテンツ定義型チャンク分割は、ファイルの内容からチャンク境界を選択することでバックアップの重複排除を向上させます。これにより、挿入や削除があった後でも変更されていない領域を再利用できます。

増分バックアップには、バージョン間でほとんど変更されない大容量ファイルが含まれることがよくあります。仮想ディスクイメージ、メールアーカイブ、ファイルとしてコピーされたデータベース、プロジェクトバンドル、エクスポートしたメディアライブラリなどです。すべてのチャンクが固定バイトオフセットから始まる場合、先頭付近に小さなヘッダーを挿入すると、後続のバイトが同一であっても、その後のすべての境界がずれてしまいます。コンテンツ定義型チャンク分割では、絶対位置ではなく局所的なバイトパターンに従って分割するため、変更された領域の後でバックアップを以前のチャンクに再同期できます。

固定サイズの境界では、1回の小さな編集が多数の新しいチャンクに変わる可能性がある

固定サイズのチャンク分割では、バイトの内容に関係なく、たとえば1 MiBごとの位置で分割します。先頭付近にバイトが挿入されると、元のストリームと新しいストリームの位置がずれるため、基盤となるコンテンツのほとんどが変わっていなくても、それ以降の各固定チャンクには異なるバイトの組み合わせが含まれます。

コンテンツ定義型チャンク分割は、コンテンツから導出したカットポイントによって、局所的な編集後に固定オフセットでは見逃しやすい冗長性を検出できるため、重複排除の目的で開発されました。CDCの利点は、どのファイル同士が似ているかを予測することではありません。位置がずれても維持できる分割方法を重複排除処理に与えることです。

ファイル全体が無関係なバイトに置き換えられた場合、どのチャンク分割アルゴリズムでも重複コンテンツを作り出すことはできません。CDCが最も効果を発揮するのは、バージョン間で大きな未変更のバイト領域を共有しているものの、それらの領域がファイル先頭からの相対位置に対して移動している場合です。

ローリングフィンガープリントでバイトストリーム内の局所的なカットポイントを検索する

CDCは入力上でウィンドウを移動させ、バイトがウィンドウに入るたび、また出るたびにフィンガープリントを更新します。フィンガープリントが設定された条件を満たすと境界が決定されます。ただし、極端に小さいチャンクや大きすぎるチャンクを防ぐため、最小および最大チャンクサイズのルールが適用されます。

Borgのチャンク分割では、ローリングコンテンツフィンガープリントを使用するため、次の候補境界を評価するたびにウィンドウ全体を最初からハッシュ化する必要がありません。フィンガープリントは近傍のバイトに依存するため、絶対的なファイルオフセットが変わっても、同じ局所シーケンスによって同じ位置で分割される可能性があります。

したがって、ローリングフィンガープリントは境界を見つけるための仕組みであり、保存されたバックアップデータの最終的な識別子ではありません。この2種類のハッシュを同一視すると、重複排除で実際に再利用が決定される場所についての説明が不正確になります。

最小、最大、平均のチャンクサイズも境界検索の形を決めます。これらは候補となるカットが検討される頻度と、リポジトリが管理する必要のあるメタデータ量を左右します。

CDCは編集後に再同期し、ずれた状態が永久に続くのを防ぐ

挿入や削除の後、ローリングウィンドウはまず異なるバイトを読み取るため、編集箇所周辺では異なるチャンク境界が生成されます。しかし、十分に長い未変更領域に完全に移動すると、同じ局所的なコンテンツパターンに遭遇し、以前のバージョンと整合する位置で分割を再開できます。

Borgは、別の場所でバイトが挿入または削除された場合でも、コンテンツ定義型の境界が未変更のコンテンツに対して安定し得ると説明しています。この再同期により、ファイルの残り全体が無効になるのではなく、多くの編集を少数の新しいチャンクに限定できます。

Resticも同様に、スライディングフィンガープリントを使用してファイルを可変長のblobに分割するため、変更されていない可変長blobをスナップショット間で再び参照できます。リポジトリには、保存済みのblobを認識するためのインデックスが必要です。

再同期までの距離は、チャンク分割のパラメーターと変更されたバイトパターンによって異なるため、CDCは編集ごとに必ず1つの新しいチャンクだけが生成されることを保証するものではありません。CDCの利点は統計的な局所性にあります。変更によって後続のすべての境界がずれる可能性を低減できるのです。

Featured

ZimaCube 2 パーソナルクラウドホームNAS

ZimaCube2

$799.00 - $2,499.00

Buy Now

強力なチャンク識別子が、境界の決定後に再利用を判断する

境界を見つけることで分かるのは、候補チャンクがどこで終わるかだけです。リポジトリはさらに、そのチャンク全体の内容がすでに存在するかどうかを判断する必要があります。この2つ目の判断では、完成したチャンクに対する強力なコンテンツ識別子または認証付きハッシュを使用し、リポジトリのインデックスで検索します。

Borgは、重複排除の基準として使用される暗号学的なチャンク識別子と、境界を決めるハッシュを明確に区別しています。Resticも同様に、ローリングフィンガープリントを2つのチャンクが同一である証拠として扱うのではなく、強力なコンテンツハッシュによって保存済みblobを参照します。

この2段階の設計により、保存処理の流れを明確に説明できます。ローリングハッシュが候補となる分割を選び、コンテンツハッシュが生成されたチャンクを識別し、リポジトリ検索が保存するか再利用するかを決定します。CDCによって編集後も一致が維持されやすくなるとはいえ、ストレージの節約が発生するのは最後の2段階です。

チャンクサイズとデータ変換が、計算コストと節約効果の境界を決める

平均チャンクサイズを小さくすると変更をより正確に分離できますが、フィンガープリント、インデックスエントリ、検索、メタデータオブジェクト、ストレージ参照の数が増加します。チャンクを大きくするとインデックスのオーバーヘッドは減りますが、小さな編集によって再利用可能なデータのより大きな単位が無効になる可能性があります。

FastCDCは、強力な冗長性検出を維持しながらローリングハッシュのCPUオーバーヘッドを削減することに重点を置いています。これは、重複したバイトが排除される前に、チャンク分割自体が大きなコストになり得ることを示しています。最適なパラメーターは、チャンク分割の処理量、インデックスサイズ、バックアップセットの類似パターンのバランスによって決まります。

チャンク分割前の変換によって、CDCが依存するバイトレベルの類似性が失われることもあります。異なるnonceを使った暗号化、小さな論理的変更の後にファイルの大部分を書き換える形式、一部の圧縮レイアウトなどでは、論理的には似た2つのバージョンがバイトレベルでは無関係に見える可能性があります。

ZimaSpaceによる重複排除インデックスのオーバーヘッド分析では、このトレードオフのもう一方の側面を取り上げています。再利用の粒度を細かくするほど、既存データを追跡するために多くのメタデータとメモリが必要になります。CDCに価値があるのは、可変サイズのチャンクが高度に聞こえるからではなく、得られるストレージ節約量が追加のチャンク分割およびインデックスコストを上回る場合です。