データ重複排除

コンピューティングにおいて、データ重複排除は、繰り返されるデータの重複コピーを排除する技術です。この技術を適切に実装すると、ストレージの使用率が向上し、ストレージ容量のニーズを満たすために必要なストレージ メディアの総量が削減されるため、設備投資が削減される可能性があります。また、ネットワーク データ転送に適用して、送信する必要があるバイト数を削減することもできます。

重複排除プロセスでは、データの「チャンク」（「バイトパターン」とも呼ばれる）の比較が必要です。これは、一意で連続したデータブロックです。これらのチャンクは、分析プロセス中に識別されて保存され、既存のデータ内の他のチャンクと比較されます。一致が発生するたびに、冗長なチャンクは、保存されたチャンクを指す小さな参照に置き換えられます。同じバイトパターンが数十回、数百回、さらには数千回発生する可能性があることを考えると（一致頻度はチャンクサイズによって異なります）、保存または転送する必要があるデータの量を大幅に削減できます。^{[1] [2]}

関連する技術として、単一インスタンス（データ）ストレージがあります。これは、ファイル全体のレベルでコンテンツの複数のコピーを単一の共有コピーに置き換えます。これを他の形式のデータ圧縮や重複排除と組み合わせることもできますが、セグメントまたはサブブロック レベルで動作できるデータ重複排除の新しいアプローチとは異なります。

重複排除は、 LZ77 や LZ78などのデータ圧縮アルゴリズムとは異なります。圧縮アルゴリズムは個々のファイル内の冗長データを識別し、この冗長データをより効率的にエンコードしますが、重複排除の目的は、大量のデータを検査し、ファイル全体やファイルの大きなセクションなど、同一の大きなセクションを識別し、共有コピーに置き換えることです。

たとえば、一般的な電子メール システムには、同じ 1 MB (メガバイト) の添付ファイルが 100 個含まれている場合があります。電子メールプラットフォームがバックアップされるたびに、添付ファイルの 100 個のインスタンスがすべて保存され、100 MB のストレージ スペースが必要になります。データ重複排除では、添付ファイルのインスタンスは実際に 1 つだけ保存されます。後続のインスタンスは保存されたコピーを参照して、重複排除率が約 100 対 1 になります。重複排除は、追加のストレージ節約のためにデータ圧縮と組み合わせて使用​​されることがよくあります。重複排除は最初に大きな繰り返しデータのチャンクを削除するために使用され、次に圧縮を使用して保存された各チャンクを効率的にエンコードします。^[3]

コンピュータ コードでは、たとえば、情報を変数に格納して、個別に書き出す必要がなくなり、中央の参照場所で一度に変更できるようになることで重複排除が行われます。例としては、 CSS クラスやMediaWikiの名前付き参照があります。

ストレージベースのデータ重複排除により、特定のファイル セットに必要なストレージ容量が削減されます。これは、非常に類似した、または同一のデータのコピーが多数、単一のディスクに保存されるアプリケーションで最も効果的です。データ損失を防ぐために日常的に実行されるデータ バックアップの場合、特定のバックアップ内のほとんどのデータは、以前のバックアップから変更されていません。一般的なバックアップ システムでは、変更されていないファイルを省略 (またはハード リンク) するか、ファイル間の差分を保存することで、この状態を利用しようとします。ただし、どちらの方法でもすべての重複が捕捉されるわけではありません。ハード リンクは、電子メール データベースなど、変更がわずかしかない大きなファイルには役立ちません。差分では、単一ファイルの隣接するバージョン内の重複のみが検出できます (削除されて後で再度追加されたセクションや、多くのドキュメントに含まれるロゴ イメージなど)。

インライン ネットワーク データ重複排除は、エンドポイント間で転送する必要があるバイト数を削減するために使用され、必要な帯域幅の量を削減できます。詳細については、 WAN 最適化を参照してください。

仮想サーバーと仮想デスクトップは、重複排除によって、各仮想マシンの名目上は別々のシステム ファイルを 1 つのストレージ スペースに統合できるため、その恩恵を受けます。同時に、特定の仮想マシンがファイルをカスタマイズした場合、重複排除によって他の仮想マシンのファイルは変更されません。これは、ハード リンクや共有ディスクなどの代替手段では実現できないことです。仮想環境のバックアップや複製コピーの作成も同様に改善されます。

重複排除は、データが流れているときに「インライン」で実行される場合もあれば、データが書き込まれた後に「後処理」で実行される場合もあります。

ポストプロセス重複排除では、新しいデータが最初にストレージ デバイスに保存され、その後、プロセスによってデータが分析され、重複がないか調べられます。利点は、データを保存する前にハッシュ計算と検索が完了するのを待つ必要がないため、保存のパフォーマンスが低下しないことです。ポリシー ベースの操作を提供する実装では、ユーザーは「アクティブ」ファイルの最適化を延期したり、タイプと場所に基づいてファイルを処理したりできます。潜在的な欠点の 1 つは、重複データが不必要に短時間保存される可能性があることです。これは、システムの容量がいっぱいに近づいた場合に問題になる可能性があります。

あるいは、重複排除ハッシュ計算をインラインで実行することもできます。つまり、データがターゲット デバイスに入るときに同期されます。ストレージ システムがすでに保存されているブロックを識別した場合、新しいブロック全体ではなく、既存のブロックへの参照のみが保存されます。

インライン重複排除がポストプロセス重複排除よりも優れている点は、重複データが保存または転送されないため、必要なストレージとネットワーク トラフィックが少なくなることです。欠点としては、ハッシュ計算の計算コストが高くなる可能性があり、ストレージ スループットが低下することがあります。ただし、インライン重複排除を提供する一部のベンダーは、インライン重複排除を高速で実行する機器を実証しています。

後処理とインライン重複排除の方法は、しばしば激しい議論の的となっている。^{[4] [5]}

SNIA辞書では2つの方法が特定されています: ^[2]

• コンテンツに依存しないデータ重複排除 - 特定のアプリケーション データ形式を意識する必要のないデータ重複排除方法。
• コンテンツ認識型データ重複排除 - 特定のアプリケーション データ形式に関する知識を活用するデータ重複排除方法。

データ重複排除方法を分類するもう 1 つの方法は、発生する場所によって異なります。データが作成される場所の近くで発生する重複排除は、「ソース重複排除」と呼ばれます。データが保存される場所の近くで発生する場合は、「ターゲット重複排除」と呼ばれます。

ソース重複排除により、データ ソース上のデータが重複排除されます。これは通常、ファイル システム内で直接行われます。ファイル システムは定期的に新しいファイルをスキャンしてハッシュを作成し、既存のファイルのハッシュと比較します。同じハッシュを持つファイルが見つかると、ファイルのコピーが削除され、新しいファイルは古いファイルを指します。ただし、ハード リンクとは異なり、重複したファイルは別のエンティティと見なされ、重複したファイルの 1 つが後で変更された場合、コピー オン ライトと呼ばれるシステムを使用して、変更されたファイルまたはブロックのコピーが作成されます。重複排除プロセスは、ユーザーとバックアップ アプリケーションに対して透過的です。重複排除されたファイル システムをバックアップすると、重複が発生することが多く、バックアップがソース データよりも大きくなります。^{[6] [7]}

コピー操作では、ソースの重複排除を明示的に宣言できます。これは、コピーされたデータが重複排除を必要としているかどうかを知るための計算が不要であるためです。これにより、ファイルシステム上でreflink (Linux) またはclonefile (MacOS) と呼ばれる新しい形式の「リンク」が生まれ、1 つ以上のinode (ファイル情報エントリ) がそのデータの一部またはすべてを共有するようになります。これは、 inode レベルで機能するハードリンクや、ファイル名レベルで機能するシンボリックリンクに類似した名前です。 ^[8]個々のエントリは、エイリアシングのないコピーオンライト動作をします。つまり、後で 1 つのコピーを変更しても、他のコピーには影響しません。^[9] Microsoft のReFSもこの操作をサポートしています。^[10]

ターゲット重複排除は、データがその場所で生成されていない場合に重複データを削除するプロセスです。この例としては、SAN/NAS に接続されたサーバーが挙げられます。SAN/NAS はサーバーのターゲットになります (ターゲット重複排除)。サーバーは重複排除を認識しませんが、サーバーはデータ生成ポイントでもあります。2 番目の例はバックアップです。通常、これはデータ リポジトリや仮想テープ ライブラリなどのバックアップ ストアになります。

最も一般的なデータ重複排除の実装の 1 つは、データのチャンクを比較して重複を検出するというものです。そのためには、各データ チャンクに ID が割り当てられます。この ID はソフトウェアによって計算され、通常は暗号ハッシュ関数が使用されます。多くの実装では、ID が同一であればデータも同一であると想定されますが、ピジョンホール原理によりすべての場合に当てはまるとは限りません。他の実装では、同じ ID を持つ 2 つのデータ ブロックが同一であるとは想定せず、同じ ID を持つデータが同一で​​あることを実際に検証します。^[11]ソフトウェアが、実装に応じて、特定の ID が重複排除名前空間にすでに存在すると想定するか、2 つのデータ ブロックの ID を実際に検証すると、重複チャンクがリンクに置き換えられます。

データが重複排除されると、ファイルを読み戻す際にリンクが見つかった場合は、システムはそのリンクを参照されたデータ チャンクに置き換えるだけです。重複排除プロセスは、エンド ユーザーとアプリケーションに対して透過的になるように設計されています。

商用の重複排除の実装は、チャンキング方法とアーキテクチャによって異なります。

• チャンク化: 一部のシステムでは、チャンクは物理層の制約によって定義されます (例: WAFLの 4KB ブロック サイズ)。一部のシステムでは、完全なファイルのみが比較され、これはシングル インスタンス ストレージまたは SIS と呼ばれます。最もインテリジェントな (ただし CPU を集中的に使用する) チャンク化方法は、一般的にスライディング ブロック(コンテンツ定義チャンク化とも呼ばれます) であると考えられています。スライディング ブロックでは、より自然に発生する内部ファイル境界を探すために、ウィンドウがファイル ストリームに沿って渡されます。
• クライアント バックアップ重複排除: これは、重複排除ハッシュ計算が最初にソース (クライアント) マシン上で作成されるプロセスです。ターゲット デバイスに既に存在するファイルと同じハッシュを持つファイルは送信されず、ターゲット デバイスは重複データを参照するための適切な内部リンクを作成するだけです。この利点は、データがネットワーク経由で不必要に送信されるのを防ぎ、トラフィック負荷を軽減できることです。
• プライマリ ストレージとセカンダリ ストレージ: 定義上、プライマリ ストレージ システムは、可能な限り低コストではなく、最適なパフォーマンスを実現するように設計されています。これらのシステムの設計基準は、他の考慮事項を犠牲にしてパフォーマンスを向上させることです。さらに、プライマリ ストレージ システムは、パフォーマンスに悪影響を与える可能性のある操作に対して、はるかに許容度が低くなります。また、定義上、セカンダリ ストレージ システムには、主にデータの複製、つまりセカンダリ コピーが含まれます。これらのデータのコピーは通常、実際の運用操作には使用されず、結果として、効率性の向上と引き換えに、ある程度のパフォーマンス低下に対してより許容度が高くなります。

これまで、データ重複排除は主にセカンダリ ストレージ システムで使用されてきました。その理由は 2 つあります。まず、データ重複排除では重複データを検出して削除するためのオーバーヘッドが必要になります。プライマリ ストレージ システムでは、このオーバーヘッドがパフォーマンスに影響する可能性があります。重複排除がセカンダリ データに適用される 2 つ目の理由は、セカンダリ データには重複データが多く含まれる傾向があるためです。特にバックアップ アプリケーションでは、時間の経過とともに重複データが大量に生成されることがよくあります。

システム設計で大きなオーバーヘッドが必要なかったり、パフォーマンスに影響を与えなかったりする場合には、データ重複排除がプライマリ ストレージで正常に導入されています。

シングルインスタンスストレージ（SIS）は、コンテンツオブジェクトの複数のコピーを取得し、それらを単一の共有コピーに置き換えるシステムの機能です。これは、データの重複を排除し、効率を高める手段です。SISは、ファイルシステム、電子メールサーバーソフトウェア、データ バックアップ、およびその他のストレージ関連のコンピュータソフトウェアに頻繁に実装されています。シングルインスタンスストレージは、データ重複排除の単純なバリエーションです。データ重複排除はセグメントまたはサブブロックレベルで機能しますが、シングルインスタンスストレージはオブジェクトレベルで機能し、ファイル全体や電子メールメッセージなどのオブジェクトの重複コピーを排除します。^[12]

シングルインスタンス ストレージは、他のデータ複製またはデータ圧縮方法と併用 (または重ねて使用) することで、複雑さが増し、場合によってはストレージ スペース要件がわずかに増加する代わりにパフォーマンスを向上させることができます。

データの重複排除方法の 1 つは、暗号化ハッシュ関数を使用して重複するデータ セグメントを識別することです。2 つの異なる情報が同じハッシュ値を生成する場合、これは衝突と呼ばれます。衝突の確率は主にハッシュの長さによって決まります (誕生日攻撃を参照)。したがって、ハッシュ衝突が発生した場合に、データに違いがあるかどうかを検証するための追加の検証手段が使用されないと、データ破損が発生する可能性があるという懸念が生じます。インライン アーキテクチャとポストプロセス アーキテクチャの両方で、データの整合性を保証するために、元のデータのビット単位の検証を行うことができます。使用されるハッシュ関数には、SHA-1、SHA-256などの標準が含まれます。

プロセスの計算リソースの集中は、データ重複排除の欠点となる可能性があります。パフォーマンスを向上させるために、一部のシステムでは、弱いハッシュと強いハッシュの両方を使用しています。弱いハッシュは計算がはるかに高速ですが、ハッシュ衝突のリスクが高くなります。弱いハッシュを使用するシステムは、その後に強いハッシュを計算し、それが実際に同じデータであるかどうかを決定する要素として使用します。ハッシュ値の計算と検索に関連するシステム オーバーヘッドは、主に重複排除ワークフローの機能であることに注意してください。ファイルの再構成にはこの処理は必要なく、データ チャンクの再構築に関連するパフォーマンスの増分ペナルティがアプリケーションのパフォーマンスに影響を与える可能性は低いです。

もう 1 つの懸念は、圧縮と暗号化の相互作用です。暗号化の目的は、データ内の識別可能なパターンをすべて排除することです。したがって、基礎となるデータが冗長であっても、暗号化されたデータは重複排除できません。

データ重複排除の欠点ではありませんが、重複排除されたデータの大規模なリポジトリで不十分なセキュリティとアクセス検証手順が使用されると、データ侵害が発生しています。クラウドストレージに典型的な一部のシステムでは、^{[引用が必要]}攻撃者は目的のデータのハッシュ値を知るか推測することで、他人が所有するデータを取得できます。^[13]

重複排除は、 ZFSやWrite Anywhere File Layoutなどの一部のファイルシステムや、さまざまなディスク アレイモデルに実装されています。^{[引用が必要]これは、Windows サーバー上の}NTFSとReFS の両方で利用できるサービスです。

• Biggar, Heidi(2007.12.11). WebCast: データ重複排除効果
• データ重複排除に潜在的セマンティック インデックスを使用する。
• データを保存するより良い方法。
• データ重複排除、ファイル重複排除、データ圧縮の違いは何ですか? - eWeek のデータベース
• SNIA DDSR SIG
  • データ重複排除率を理解する
• 少ない労力でより多くの成果を上げる by Jatinder Singh
• 重複排除デモ