ユニークな手法で非重複化を行うData Domainのデータプロテクションストレージ【前編】

　D2D（Disk to Disk）によるバックアップが浸透しつつある今日、何世代ものバックアップデータを安価に保管する手段としてディスクストレージの非重複化（de-duplication）機能に注目が集まっている。非重複化機能は、ディスクストレージに保管されているデータの中から重複する部分を徹底的に取り除くことで、実質的なデータ容量を大幅に削減する。非重複化機能を備えたディスクストレージは、すでにいくつかのベンダーから登場しているが、その先駆者ともいえる存在がData Domainの製品だ。

　Data Domainの技術概要については本連載でもすでに取り上げているが（2006年3月27日付、「テープレス・バックアップを後押しするCOS（Capacity Optimized Storage）」）、脱稿後にData Domainの日本法人（データドメイン株式会社）が設立され、日本国内でも本格的にビジネスが展開されるようになった。そこで、技術や導入実績がさらに進んだ2008年末、データドメイン株式会社シニアシステムズエンジニアの村山雅彦氏にData Domainの技術詳細と最新動向をお聞きしてきた。今回より2回にわたって、Data Domain製品を支えるアーキテクチャとその構成技術について解説していく。

■ 従来型のディスクストレージでD2Dバックアップを実施するのは高コスト

　データバックアップは、例えば1日1回という典型的な頻度を想定すると、初日はフルバップアップによって起点となるデータを取得し、翌日からは日々の変更分だけを差分バックアップないしは増分バックアップで積み重ねていくという手順がとられる。バックアップウインドウの短縮を優先するなら前日からの変更分のみを取得する増分バックアップ、リストアのしやすさを優先するなら起点となる初日からの変更分を取得する差分バックアップが適している。筆者がこれまで多くのエンドユーザーを取材したところでは、迅速なリストアを重視した差分バックアップを採用する企業が圧倒的に多かった。もちろん、日々のバックアップウインドウ内でフルバックアップを確実に実行できるなら、毎日フルバックアップを実施すれば理想的といえよう。

通常の圧縮技術と非重複化技術を組み合わせることで、複数世代のバックアップデータを保管する用途では非常に高いデータ圧縮効果が生まれる（出典：データドメイン株式会社、以下同様）。最近では、いくつかのベンダーからデータの非重複化機能を搭載したディスクストレージが発売されるようになった

　いずれにせよ、こうした日々のデータバックアップをD2Dで実施する際に問題となるのがディスクストレージの容量設定だ。従来型のディスクストレージに何世代ものバックアップデータをそのまま保管すれば、バックアップ対象となる元データの何倍ものディスクスペースが必要になる。ごく一般的なZiv-Lempelアルゴリズムによってデータ圧縮を行ったとしても、せいぜい2倍程度にしか圧縮できない。もちろん実際の圧縮率はデータの種類によって左右されるが、Calgary Text Compression Corpusにおける計測結果によれば、主要なテープストレージの圧縮率は平均して2.09～2.2倍であることが分かっており、これはD2Dバックアップにおいてもそう変わるものではない。

　従って、例えばフルバックアップを10回繰り返したとすれば、10個の元データがそれぞれ2分の1に圧縮されたとしても、ディスクストレージに保管すべきデータは10個に増えている。つまり、トータルで見れば元データの5倍にも膨れあがる計算になるのだ。テープストレージではテープカートリッジの本数を増やせば済む話だが、ディスクストレージではHDDの台数を増やしたり、場合によってはコントローラを上位モデルに切り替えたりするなど、かなりのコストアップを余儀なくされてしまう。

■ セグメントごとに生成したフィンガープリントによって重複判定を実行

　このような中で登場したのが、非重複化または重複排除と呼ばれるデータ削減技術である（本稿では、非重複化という用語で統一する）。非重複化は、以前書かれたデータと重複するものを積極的に取り除き、まったく重複しないデータのみを新たに書き込む。従来のデータ圧縮技術はすべてのデータに対して一様に圧縮処理をかけるが、非重複化技術は2回目以降に書き込まれたデータに対して強く作用する。このため、通常のプライマリーストレージに使用しても効果は薄く、何世代ものデータを重ねて保管するバックアップやアーカイブ、ニアライン用途向けのセカンダリーストレージで威力を発揮する技術なのだ。Data Domainを例にとると、最初のフルバックアップ時には数倍程度の圧縮率にとどまるが、2回目からのフルバックアップでは50～60倍、平均すれば20倍もの圧縮効果が得られる。

2回目のバックアップデータを書き込むときには、すでに保管されているバックアップデータと比較して変更された部分や追加された部分だけを実際に書き込んでいく。いわばバックアップの世界でいう差分バックアップや増分バックアップにも似た考え方だが、実際には4～12KBという非常に小さな粒度（グラニュラリティー）で処理することから、そのデータ圧縮効果は驚くほどに高い

　どのベンダーの非重複化技術も、重複部を排除するための仕組みそのものはかなり似通っている。バックアップサーバーから送り込まれたバックアップイメージは、まず固定長または可変長の小さなセグメントに分割される。Data Domainでは、4～12KBの可変長セグメントに分割され、平均すると8KBの長さになる。次に、各セグメントに対して以前書き込まれたセグメントと同一のものがあるかどうかをチェックし、同一のものがあった場合には重複しているので書き込まず、同一のものがなかった場合には新規のデータとして書き込むようにする。

　セグメントの重複判定は、ディスク上からセグメントをすべて読み出し、しらみつぶしに比較していく方法が最も簡単なのだが、大量のセグメントを単純に読み出していてはまったく実用にならない。そこで、非重複化技術では、セグメントそれぞれのアイデンティティを表すフィンガープリント（いわば指紋のような役割を果たすもの、以下FP）をハッシュ関数によって生成する。例えば、Data Domainではハッシュ関数のアルゴリズムとしてSHA-1を採用しており、セグメントそれぞれに対して160ビット長のFPが作られる。このFP群をデータベース化したFPインデックスを設け、FPインデックスの参照によってセグメントの重複判定を行う。4～12KBのセグメントではなく160ビットのFPによって重複判定が可能になるので、比較時に読み出すべきデータは大きく削減される。

■ ディスクアクセスを前提とした重複判定ではスループットを高められない

　FPインデックスがすべてメモリー上に載るサイズであれば、インデックスの参照をスピーディーに行えるので重複判定のスループットも間違いなく向上する。しかし、大容量データに対するFPインデックスの総量は極めて大きい。例えば、80TBの実データを平均8KBのセグメントに分割した場合、これらのセグメントに対するFP値は総量で20GB（＝80TB÷8KB×160バイト）にも達する。これほどの巨大なインデックスをメモリー上に載せることは現時点のシステムではコスト的に見合わない。このため、FPインデックスをディスク上に配置している製品がほとんどである。

　ここで、ディスク上のFPインデックスがどれくらいのスループットを見込めるか、実際に計算してみよう。セカンダリーストレージで多く使われているSATA HDDは、1台あたりのI/O性能がおおむね120回とされる。セグメントの平均サイズを8KBとすると、1秒あたりのスループットは約1MB/秒（≒8KB×120回）と算出される。このため、100MB/秒のスループットを得ようとすれば、HDDが100本も必要になる。SATA HDDは1本あたりの容量が非常に大きいことから、多数のHDDを搭載してしまうと必要以上に大きなディスク容量になってしまう。そもそも、HDDの台数を減らしてコストを削減するために非重複化技術を導入するわけなので、データ転送のスループットを高めるために多数のHDDを組み合わせなければならないとなると本末転倒なのだ。

　「非重複化技術では、いかにHDD 1台あたりのスループットを高めるかが重要になります。そのためには、なるべくディスクアクセスに頼らない方法で重複判定を行う必要があります。Data Domainは、数学的なアルゴリズムを通じてCPUとメモリー上の計算だけで重複判定を行えるようなアーキテクチャを採用し、少ないHDD台数と高いスループットを両立しています。ここが、他社との絶対的な差別化ポイントになります。（村山氏）」

■ 重複していないデータを超高速に判別するサマリーベクター

　Data Domainの非重複化技術で中核となるのは、サマリーベクター（summary vector）とローカリティープリフェッチング（locality prefetching）という2つの要素技術である。多くのストレージではFPインデックスをディスク上に配置していると述べたが、Data Domainのストレージ製品では、このFPインデックスに加え、インメモリーでの高速な重複判定手段としてサマリーベクターを併用している。

サマリーベクターは、メモリー上に載せられる程度のサイズ（512MBから数GB）に設定されている。ハッシュ関数を用いてFP値からさらに3つの値を算出し、それぞれの値に対応するビット位置を1とする。サマリーベクターを利用すれば、160ビット長のFP値に代わり、3ビットの値だけで重複判定を行えるようになるのだ。ただし、ブルームフィルターが持つ偽陽性の特性により、誤って「重複している」と判断してしまうことがある。このため、最終的にはFP値を使用して本当に重複しているかどうかを判定する

　サマリーベクター上の値は、ブルームフィルターと呼ばれる数学的な手法によって生成される。サマリーベクターは、メモリー上に配置できる程度の大きさ（512MB～数GB）に設定されており、初期状態ではすべてのビットが0に初期化されている。ここで、入力された各セグメントのFP値に対して、さらにハッシュ関数をとって3つの値をはじき出す。そして、この3つの値に対応するビット位置を1とする。後続するセグメントのFP値に対しても同様の操作を行い、サマリーベクター上には数多くの1が並ぶようになる。サマリーベクターは、最初に決められたサイズのまま一定であり、ディスクストレージに保存される実データの容量にはまったく左右されない。

　そして、再度データを書き込む際には、各セグメントのFP値に対する3つの値を計算すると、内容が重複している（と思われる）セグメントに対応するビット位置はすでにすべてが1となっている。これに対し、初めて書き込むセグメントに対応するビット位置には0が含まれている。このように、対応するビット位置が1か0かを見ることによって、即座に重複判定を行えるわけだ。いずれにせよ、サマリーベクター自身はメモリー上に置かれているものなので、CPUとメモリー上の計算のみで高速に重複判定を行える。

　基本的に、対応する3つのビット位置のうち、どれか1つでも0が見つかればデータは絶対に重複していないことが保証される。しかし、3のビット位置がすべて1であっても、データが必ず重複していることは保証されない。実は、サマリーベクターのもとになるブルームフィルターは、原理的に偽陽性（false positive）による誤検出の可能性があり、誤って『重複している』と判断してしまうことがある。このため、サマリーベクターだけでは正確な重複判定を行うことはできず、最終的な判断はFPインデックスに委ねなければならない。とはいえ、少なくとも重複している可能性が高いセグメントのみがFPインデックスの参照対象となることから、他社の非重複化技術と比べればディスクアクセスはこの時点でもかなり削減される。

■ 最終的な重複判定を高速化するローカリティープリフェッチング

Data Domainのファイルシステムは、複数のセグメントとそれに対応するFP値がパックされた『コンテナ』をアクセス単位としている。コンテナのサイズは4.6MBなので、仮に平均8KBのセグメントが2倍の圧縮率で保管されていたとすれば、おおむね1000個分のセグメントとFP値が含まれることになる

　重複している可能性のあるセグメントの最終判定には、従来通りにFPインデックスが使用されるが、このときには2番目のローカリティープリフェッチングが威力を発揮する。Data Domainのファイルシステムは、4.6MBのサイズを持ったコンテナをアクセス単位としている。Data Domain製品では、データの器となる論理ドライブを14台のHDDによって構成している。RAIDレベルにはRAID 6を採用しており、ストライプサイズは384KBだ。実データは12台分に相当するため、最小のアクセス単位は4.6MB（＝384KB×12台）となる。コンテナには、Ziv-Lempelアルゴリズムなどによって圧縮されたセグメントと、このセグメントに対応するFP値がパックされる。仮に平均8KBのセグメントが2倍の圧縮率で保管されていたとすれば、1個のコンテナ中には約1000個分のセグメントとFP値がパックされている計算だ。

Data Domain独自の重複判定フロー。他社のようにFP値を直接参照する方法では、HDDの台数を増やさなければスループットを確保できない。これに対し、Data Domainは、最初のふるいとしてサマリーベクターを使用し、絶対に重複していない部分と重複している可能性のある部分を切り分ける。そして、重複している可能性のある部分を、ローカリティープリフェッチングによって確実に切り分ける。ほとんどの重複判定をインメモリーで実行できることから、少ないHDD台数でも非常に高いスループットが得られる

　ローカリティープリフェッチングは、このコンテナに含まれるFP値をキャッシュメモリーに先読みする技術である。サマリーベクターによって重複する可能性が高いと判定されたセグメントがあった場合（つまり、サマリーベクターの3つのビット位置がすべて1の場合）、最終的な重複判定のためにディスク上から当該セグメントのFP値を新たに読み出すが、コンテナごと読み出すことで前後する1000個ものFP値を一緒に読み出せる。データバックアップのストリームでは、隣接するセグメントが再び書き込まれる可能性が非常に高いことから、キャッシュメモリー上に先読みした隣接するFP値もそのまま使えてしまうわけだ。典型的なバックアップストリームではキャッシュのヒット率が99％にも達するという。つまり、ローカリティープリフェッチングを併用すれば、膨大なセグメントの重複判定をインメモリーでほとんど実行できるのだ。

　「Data Domainのアーキテクチャは、HDDの台数が少なくても、CPUの処理能力に比例してスループットが高まっていきます。シングルコアCPUの2年前には80MB/秒程度でしたが、デュアルコアCPUの1年前には160～180MB/秒、クアッドコアCPUの現在では300MB/秒にも達しています。今後、CPUのコア数が6コアや8コアに増えれば、さらにスループットが向上するでしょう。HDDは、容量こそ増え続けていきますが、I/O性能（1秒あたりのI/O数）はあまり向上しないと予想されます。このような中で、HDDの台数を増やすことなくスループットを高めていくには、Data Domainのようなアーキテクチャが圧倒的に有利なのです。（村山氏）」

Data Domainは、バックアップジョブと非重複化処理を同時に行えるインライン処理を採用している。つまり、バックアップの終了時には非重複化の処理も同時に終わっている。このため、バックアップ管理が容易であり、IT管理者の負担も軽減されるのだ

　Data Domainの非重複化技術でもうひとつ特徴的なのは、非重複化の処理をインラインで実行できることだ。他社製品の多くは、バックアップジョブが終了したあとに非重複化のプロセスが実行される。バックアップ時のスループットが低下しないメリットはあるものの、非重複化のプロセスがいつ終了するかまったく分からないのが問題だ。非重複化の作業中に次のバックアップウインドウが始まってしまう可能性もあることから、バックアップのスケジュール管理が非常に面倒になる。これに対し、Data Domain製品では、バックアップと非重複化を同時に実施する。つまり、バックアップジョブが終了したときには、非重複化のプロセスもすでに終了していることを意味する。

　後編では、Data Domain製品ならではの高度なデータ保護技術と災害対策（DR）に欠かせないレプリケーション機能について解説していく。

■ ＵＲＬ
　データドメイン株式会社
　 http://www.datadomain.com/jp/

■ 関連記事
　　・データドメイン、重複排除ストレージの最上位製品「DD690」（2008/10/02）
　　・ユニークな手法で非重複化を行うData Domainのデータプロテクションストレージ【後編】（2009/01/30）

（伊勢雅英）
2009/01/23 09:01

Enterprise Watch ホームページ