"記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備え、記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を備え、前記データ管理部は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、ストレージシステム。請求項1に記載のストレージシステムであって、前記データ管理部は、前記第二補助記憶装置に記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合して当該第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置から削除する、ストレージシステム。請求項2に記載のストレージシステムであって、前記データ管理部は、前記第二補助記憶装置に記憶保持されている前記複数単位のインデックスデータと前記主記憶装置に記憶保持されている前記インデックスデータとを結合して前記第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置及び前記主記憶装置から削除する、ストレージシステム。請求項2に記載のストレージシステムであって、前記データ管理部は、前記第二補助記憶装置に記憶された前記インデックスデータが存在するか否かを判定するために用いられる当該インデックスデータのデータ内容に基づく要素データを、前記主記憶装置に記憶する、ストレージシステム。請求項4に記載のストレージシステムであって、前記データ管理部は、前記第二補助記憶装置に記憶された前記インデックスデータをまとめて当該第二補助記憶装置に記憶し直す際に、前記主記憶装置に記憶された前記インデックスデータの前記要素データを解放する、ストレージシステム。請求項1に記載のストレージシステムであって、前記第一補助記憶装置はハードディスクドライブであり、前記第二補助記憶装置はSSDSolidStateDriveである、ストレージシステム。記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えた情報処理装置に、記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を実現させると共に、前記データ管理部は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、ことを実現させるためのプログラムを記憶した記憶媒体。請求項7に記載のプログラムを記憶した記憶媒体であって、前記データ管理部は、前記第二補助記憶装置に記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合して当該第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置から削除する、プログラムを記憶した記憶媒体。記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えたストレージシステムにて、記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照することにより、記憶対象データを管理し、新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定すると共に、記憶対象データを管理する際に、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、データ管理方法。請求項9に記載のデータ管理方法であって、記憶対象データを管理する際に、前記第二補助記憶装置に記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合して当該第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置から削除する、データ管理方法。これらの技術は適切な帯域幅を実現することは可能かもしれないが、次のような欠点がある。ブルームフィルタおよびプリフェッチの両方に追加のメモリが必要なため、サイズが著しく大きくなるメモリの消費については後に詳細に述べる。RAMを使用する動作もあればディスクへのアクセスが必要な動作もあるため、検索動作のレイテンシが安定しない。レイテンシが数ミリ秒のディスクの読出しは、用途によっては十分ではない例えばプライマリストレージ。重複する書込みがオリジナルの書込みと同じ順序で行われない場合、プリフェッチは事実上作業を停止し、スループットが数オーダーの規模で低下する。3番目の欠点が最も深刻だと思われる。上記非特許文献2によれば、重複を書き込む順序はパフォーマンスに多大な影響を与える。基盤システムは、重複がオリジナルの書き込みと同じ順序であれば22MB/秒の性能を達成するが、重複の順序が異なる場合は6KB/秒の性能しか達成されない。ここで問題となるのは、実際のバックアップに用いる際に順序通りでない重複がどの程度の頻度で発生するか、ということである。バックアップが行われる度に、データの断片が多少変化する。2回のバックアップ間での変化は小さくても、最初と最後のバックアップの間では、その違いはかなり大きくなると思われる。毎回、次のバックアップが行われる度に重複の順序の精度が低下し、最終的には順序が変わってしまうであろう。我々はこの分野に関する研究をまだ発見していないが、バックアップを何十回も繰り返せばこのような事態になると予想される。この問題は、同一データのバックアップの回数だけでなく、バックアップ群の数によっても悪化する。なぜなら、複数のバックアップ群に渡って、データが重複しうるからである。1つのバックアップが多数の小さなファイルで構成される場合、これらのファイルが異なる順序で書き込まれる可能性があるため、この問題は更に深刻になると思われる。このため、本発明の目的は、上述した課題である、メモリサイズの増大を抑制しつつ、レイテンシの安定化を図り、順序が異なる書き込みに対して効率的な重複排除を実現できるストレージシステムを提供することにある。本発明の一形態であるストレージシステムは、記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備え、記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を備え、前記データ管理部は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、という構成をとる。また、本発明の他の形態であるプログラムを記憶した記憶媒体は、記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えた情報処理装置に、記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を実現させると共に、前記データ管理部は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、ことを実現させるためのプログラムを記憶した記憶媒体である。また、本発明の他の形態であるデータ管理方法は、記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えたストレージシステムにて、記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照することにより、記憶対象データを管理し、新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定すると共に、記憶対象データを管理する際に、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、という構成をとる。本発明は、以上のように構成されることにより、メモリサイズの増大を抑制しつつ、レイテンシの安定化を図り、順序が異なる書き込みに対して効率的な重複排除を実現できるストレージシステムを提供することができる。<実施形態1>本願では、フラッシュベースのSSD用に設計された重複検索構造であるソリッドステート重複排除インデックスSolidStateDeduplicationIndex:SSDIを提案する。本願で提案する解決策は、前述の欠点を解決し、順序が異なる重複排除にも有効であり、検索動作に安定性がありかつレイテンシが短く、RAMの消費が少ない。また、重複排除を検索するためにSSDに基づく別の構造を提案している最近の研究とは異なり、本願における設計はSSDの削除制限と書込み耐性についても考慮し、またこの解決策に必要なRAMの定量化を行っている。本願は次のように構成されている。まず、フラッシュベースSSDの読出し/書込み動作の効率について説明する。次に、ClosedHash法について説明し、それをSSDに適用することによって発生する問題点を示す。次に、性能要件を満たす辞書構造であるSSDIを提示する。次に、提案した解決策の性能を評価し、他のアプローチと比較する。次に、関連技術を提示し、最後に、結論を出す。[SSDの特徴]重複識別構造をSSDに実装可能にするためには、毎秒十分な数の小さなランダムな読出しを行うことができるSSD装置を探す必要がある。SSD装置のその他の特徴は、本発明にとってはそれほど重要ではない。例えば停電耐性は必要ない。その理由は、データディスクに保存されている情報に基づいて構造を再構築することができると想定しているからである。さらに、本発明におけるシステムで使用するハードウェアの価格を抑えるため、この装置はかなり安価なものでなければならない。80GBのIntelX25-MSATASSDおよび1TBのHitachiUltra-start7200RPMSATAHDDで実行した性能テストの結果を示す。テストを行う前に、SSD装置をランダムなデータで満たしたSSDの状態が性能に影響を与える場合がある。例えば、装置にデータを入れた後では、装置外の書込みの帯域幅がかなり高くなる場合がある。このテストは、Linux上でダイレクトI/OとNativeCommandQueingを用いて行い、SSD上の書込みキャッシュを無効にした。その結果を図1に示す。ランダムな読出しとランダムな書込みの特徴はHDD用のものと似ているが、SSDではランダムな書込みはランダムな読出しよりもはるかに遅い。SSDはディスクよりも早く最大帯域幅に達するつまり、より小さなブロックについて。小さなSSDの読出しは、非常に高速なIOPSレートで良好な帯域幅に達する。一方、小さなSSDの書込みは特に非効率である。SSDの書込み帯域幅は、削除ブロックサイズ64KBを上限として要求サイズに合わせて拡大される。ランダムな書込みは、削除ブロックのサイズと同等またはそれより大きい場合に最適な帯域幅に達する。その理由は、小さな要求の書込みを行う場合、フラッシュトランザクションレイヤFTL:FlashTransactionLayerは通常、削除ブロック全体を削除して再び書き込む必要があるからである小さな連続書込みは装置の書込みキャッシュによってバッファリングされる。より安価な装置のFTLは一般的に削除ブロックレベルで動作する。そうでないと、FTLは変換を保存するためにSSDの内部RAMを過剰に消費することになる。通常、SSDが処理する小さなランダムな読出しの数は多いが、適切な書込み帯域幅を達成するために、SSDの書込みは大きなブロックで出される必要がある。[クローズドハッシュ法]ハッシュテーブルは、重複排除辞書とてして当然選択されるものである。データチャンクはそのハッシュ値によって識別されるため、データチャンクのハッシュ値はハッシュテーブルの鍵となる。各ハッシュテーブルのエントリには、1つのチャンクのメタデータ記録が保存される。チャンク毎に、少なくともそのハッシュ値例えばSHA-1は20バイト、SHA-256は32バイトとディスク上の場所を保存する必要があるため、各メタデータ記録は数十バイトを消費する。本願で提案する構造について、クローズドハッシュ法から推論を開始し、その後で、なぜフラッシュベースの重複辞書に直接利用できないのかを述べる。クローズドハッシュ法では、キーをエントリが保存されているテーブル内のインデックスに変換するハッシュ関数がある。効率的に機能させるために、ハッシュテーブルには開放されるエントリの一定の断片が必要である。本願で使用するメタデータ記録はかなり大きいため、記録の値をテーブルに直接保存するのは効率的でない。それを避けるために、ハッシュテーブルとメタデータテーブルの2つを利用する図2参照。キーに関するハッシュ関数がハッシュテーブル内のインデックスを決定し、データの衝突は線形走査法を用いて解決する。ハッシュテーブル内では、メタデータテーブルに対するインデックスのみが保存される。検索の際、メタデータテーブルからキーを読み出しそれを所望するキーと比較することによって、ハッシュテーブルからエントリを確認する。ハッシュ関数で得られたインデックスを持つエントリから順に1つずつ確認し、一致するメタデータ記録が得られるまで、またはハッシュテーブル内に空のエントリがあるまで、これを行う。上記の構造をフラッシュベースのソリッドステートドライブに適用する場合の効率について検討する。上記で述べた見解によれば、小さなランダムな読出しは効率的である。唯一懸念されることは、検索時にハッシュテーブルとメタデータテーブルの両方を確認する必要があることである。ハッシュテーブルからの読出しは、候補がグループ化されており1回の読出し要求ですむため、効率的である。しかし、候補となるメタデータ記録はメタデータテーブル全体にランダムに配置されているため、1回の要求では読み出すことができない。各候補について、メタデータテーブルからキーを得るために追加の読出し要求を発行しなければならない。所定のキーがあるかどうかを確認する読出し要求の数は、ハッシュテーブルの負荷率が増えるに従って増大する。例えば、図2に示すケースでは、chunk1の検索にメタデータテーブルから2回の読出しが必要となる。新たなエントリが入力されると、より深刻な問題が発生する。ハッシュの分散は一様であるため、入力する際に領域の局所性がない。ランダムな書込みのIOPS数は、すべての入力に対してSSD構造を更新可能にすることはできない。小さなランダムな書込みはコストがかかり、その帯域幅は狭く、削除されるデータ量が実際に修正および書込みされるデータよりもはるかに大きいため、早く更新回数の上限に達することがある。メタデータテーブルは一括書込みで更新できるため、問題となるのは主にハッシュテーブルに関するものである。本願では、書込み要求のサイズがより大きくなるように、好ましくは削除ブロックと等しいサイズになるように、構造を構築する必要がある。[ソリッドステート重複排除インデックス]ここでは、重複排除に関する性能の要件を満たすフラッシュベース構造であるソリッドステート重複排除インデックスについて説明する。この構造によると、上記段落で最後に述べた問題が解決されている。メタデータテーブルからの不要な読出しを避けるために、もう1つフィルタ機能を導入する。ハッシュテーブルの各エントリは、メタデータテーブルに対するインデックスだけでなく、このメタデータからのキーの小さな部分であるフィルタも保存する。メタデータテーブルからの読出しは、フィルタのビットが、検索されるキーの対応するビットと一致する場合にのみ実行される。図3に示す状況では、chunk1の検索時、key2用のメタデータ記録は、ffでない限り読み出されない。なお、このようなフィルタリングにより、誤ったキーでメタデータ記録が読み出される確率が効果的に減少する。各エントリで、フィルタに使用する容量が10ビットだけだとしても、誤ったキーのメタデータ記録が読み出される確率は1/1024である。ハッシュテーブルを拡大して同じ削減率を達成するには、何倍も大きくする必要がある。フラッシュのアーキテクチャは、ハッシュテーブルのインプレース更新を不可能にする。大きなブロックの書込みだけが満足できる帯域幅を達成する。したがって、ハッシュテーブルの更新はバッチモードで行う必要がある。そのために、本願では、RAMに保存する書込みキャッシュを導入する。更新の際、新たなキーはこのキャッシュにしか入力されない。書込みキャッシュは、効率的なキー検索を可能にするハッシュマップとして構築される。キーを検索する一方で、ハッシュテーブルの確認に加えて書込みキャッシュを確認する必要がある。図3では、key4のメタデータ記録のインデックスを書込みキャッシュから取得する。なお、書込みキャッシュ全体はメモリに保存されるため、追加の確認作業が性能に与える影響は無視できる程度である。キャッシュが完全にロードされたらスイープ動作を行う。つまりハッシュテーブルは、この処理での書込みキャッシュをクリアする、すべてのキャッシュされた修正の適用に伴って書き換えられる。スイープの実装を簡易にするために、本願ではハッシュテーブルを固定サイズの非連結領域に分割する。このサイズは、メモリ内に領域全体を読み込めるような小さなサイズでなければならない。書込みキャッシュはこのように分割されるため、各領域はRAM内に独自のキャッシュを有し、これは独立してスイープすることが可能である。また、インプレース更新を避けるために、メタデータテーブルの構成を修正する必要がある。そのために、まずディスクベースの重複排除ストレージシステムにおけるデータ構成について説明する。調査したすべてのシステムにおいて、データチャンク用コンテナの抽象的概念が導入されている。このコンテナに関して提案されている名称はシステムごとに異なる。例えば、アリーナ、メガブロック、コンテナ、synchrunコンポーネントコンテナSCCと言われることがある。コンテナ内のデータの詳細な構造はシステム毎に異なるが、コンテナはディスク上の個別のファイルに保存されるようになっている。コンテナ上の動作は、コンテナファイルへのアクセス時に連続して読取り/書込みができるように実行され、これにより次のようにディスクが効率的に使用される。数個のコンテナしか追加用に空いておらず新規書込みはそれらに直接行われるため、コンテナへの新規書込みは順次的に行われるログで構成されるファイルシステムと類似。チャンクが書込み時と同じ順序で読み込まれると、コンテナからの読出しも順次的になる。システムによって保存されているチャンクの修正または同期の動作により、すべてのコンテナが一度に更新される例えば、チャンクが削除済みとマークする、削除されたチャンクが占有している領域を再利用する、等本願における設計はコンテナのアプローチを採用している。1つのグローバルなメタデータテーブルではなく、コンテナ毎に個別のメタデータファイルを保存する。例えば、図3には3つのコンテナA、B、Cがあり、各々が対応する1つのメタデータファイルを含む。メタデータファイルはメタデータテーブルと同じ記録で構成されるチャンクのキーとコンテナ内でのチャンクの場所。各メタデータ記録はそのコンテナの修正に合わせて更新される。[RAM限定書込みキャッシュの制限]近年のMLCNANDフラッシュの書込み耐性は、通常5k~10kのプログラム削除サイクルが可能である。長年に渡り測定されたシステム寿命から考えると、ハッシュテーブルのスイープのために行われる書込みがフラッシュ装置の更新回数の上限に達しないようにするためには、RAM内にかなりの書込みキャッシュが必要となる。以下の等式は、書込みキャッシュのサイズ、SSDが使用不能になる時間、およびスイープによって消費されるSSDの読出し/書込み帯域幅の関係を表している。耐久性は、SSDのフラッシュセルのプログラム削除サイクルにおける書込み耐久性である。スイープ期間は、ハッシュテーブルの各スイープ間の時間的間隔であり、新たなチャンクの書込みで書込みキャッシュ全体を満たすのに必要な時間である。SSDの寿命を延ばすために、ハッシュテーブルを保存するSSD上の領域を拡張することができ、λはこの拡張のための因数である。スイープ帯域幅は、読出しと書込みの帯域幅で、ハッシュテーブルのスイープに利用される。SSDの性能はこれらの動作によって低下する1秒当たりのクエリー数が影響を受ける。等式2と3によれば、スイープ期間が長いほど寿命が長くなり、結果として性能の低下も少ない。しかし、等式1によれば、期間が長いほど大きな書込みキャッシュが必要となる。すべての書込みキャッシュはRAMに保存されるため、この等式はハードウェアのトレードオフを定めている。つまり、我々は大型化/高速化/SSD装置数の増加というコストと引き換えに、書込みキャッシュのためにRAMを確保することができる。上記で定めたストレージシステムの要件を見直してみる。このシステムは12台の1TBのディスクを装備し、非重複書込みに対するシステム全体の対象帯域幅は約350MB/秒1時間当たり約1億6000万チャンクの書き込みである。ハッシュテーブルのサイズは約16GBである容量が15億エントリ、最大負荷率75、エントリサイズが8バイトと想定すると、メタデータファイルの識別子とメタデータファイル内のチャンクのオフセットに54ビット、エントリ毎のフィルタにさらに10ビット。図4では、10kのフラッシュを使用する寿命6年のシステムを比較している。相対的な価格を計算するために、RAM用の1GB当たりコストはSSD用のものよりも11倍高いと仮定した下記1参照。1Kingstonの4GBECCフルバッファRAMとIntelのX25-MSSD80GBドライブとを比較図4は、システムの寿命が6年だと仮定すると、書込みキャッシュに1GB近くから4GBの間のRAMが必要なことを示している。最初の行は、RAMにハッシュテーブル全体を保存しているシステムを示している。SSDにハッシュテーブルを保存するとハードウェアのコストが大幅に削減される。さらに、ハッシュテーブルλの保存用にSSDの領域を増加すると書込みキャッシュに必要なRAMが減少するが、必ずしも使用するハードウェアの総コストが減少するわけではない。SSDに空き領域がある場合はλを増やして利用することができるが、λを増やすために、RAMの追加購入の代わりにSSDを追加購入しても経済的な違いはない。メモリ消費とハードウェア全体のコストとの両方を削減するように改良した書込みキャッシュ構成を以下に提案する。他の解決策の実際のコストについては第5章で比較する。[階層的書込みキャッシュ]メモリの一部をSSDに搭載することで、書込みキャッシュに必要なメモリのサイズを削減することができる。RAM内の書込みキャッシュについては、等しいサイズのバッファをSSDに配置し、このバッファを使用することで、RAM内のキャッシュが一杯になった場合はRAM内のキャッシュのコンテンツを廃棄することができる。このようなバッファはハッシュテーブルとしても構成される。RAM内のキャッシュとそのバッファとの両方が一杯になった場合にのみスイープを実行する。メインハッシュテーブルのスイープ数を維持したい場合は、このようなバッファを追加することでRAM内のキャッシュサイズを半分に減らすことができる。残念ながら、現在は各検索動作でのSSD上のバッファを確認する必要がある。この問題を軽減するためには、このSSDバッファにブルームフィルタを取り付けることができる。これにより、想定されるSSDの読出しの追加を大幅に減らすことができる。この解決策を数量化するため、偽陽性率1のブルームフィルタを使用すると仮定する。これにより、平均追加読出し数を100分の1に減らすことができる。かかるブルームフィルタのサイズビットは、そこに保存されるエントリ数の10倍の大きさが必要である。ハッシュテーブル内の1つのエントリのサイズは8バイトで、我々のハッシュテーブルの最高負荷率は75なので、このフィルタのサイズはその書込みキャッシュの約8分の1の大きさとなる。このようなSSDバッファ1つではなく、各々にブルームフィルタを取り付けた複数のSSDバッファを使用することもできる。バッファが増えればRAM内のキャッシュサイズを小さくすることができるが、ブルームフィルタの数が多くなるためRAM消費が増加する。より多くのバッファを追加すればトータルのRAM消費は最大8分の1減らすことができる。その理由は、RAM内の各書込みキャッシュが減少するため、この減少の1/8をブルームフィルタのRAM消費に還元する必要があるからだ。RAM内のキャッシュサイズを更に小さくするために、RAM内の書込みキャッシュ第1階層と、第2階層を構成する上述の読出し専用のバッファとの上に、第3階層のキャッシュを導入することを提案する。第3階層のキャッシュもハッシュテーブルとして構成される。3階層のキャッシュの構成は次の通りである図5参照。1.1つの書込みキャッシュがRAM内に保存され、lエントリを上限として保存することができる。2.SSD上のn2の書込みキャッシュを上限として、各々がlエントリを保存し、各々がブルームフィルタを含む。3.SSD上のn3の書込みキャッシュを上限として、各々がlエントリを保存し、ブルームフィルタは含まない。入力の際、エントリはRAM内に保存される第1階層の書込みキャッシュに入力される。このキャッシュが一杯になっている場合は、第2階層の書込みキャッシュとしてSSDに書き込まれ、その概要がRAM内のブルームフィルタに保存される。第2階層の書込みキャッシュの数には制限があるn2、図では制限数は4。他のRAMキャッシュの廃棄によりこの制限を超えた場合は、第1階層のキャッシュと第2階層のすべてのキャッシュが結合され第3階層のキャッシュとしてSSDに書き込まれる。結合する際、第1階層と第2階層にあるすべてのエントリが新たな第3階層の書込みキャッシュに書き込まれ、第1階層と第2階層のキャッシュはクリアされる。したがって、各第3階層の書込みキャッシュは、第1階層/第2階層のキャッシュよりもn21倍大きい。結合された第1階層と第2階層のキャッシュが第3階層のキャッシュの制限n3、図では第3階層のキャッシュ数の制限は2を超えた場合は、スイープを行う。すべてのキャッシュがスイープ領域と結合されて新たなスイープ領域が書き込まれる。なお、ここでは、第2階層キャッシュ用のメモリ内ブルームフィルタを維持しているが、第3階層のキャッシュ用は維持していない。このブルームフィルタのサイズはそのキャッシュのサイズに比例し、検索の際にほぼ必ず1つの不要なSSD読出しを回避する。第2階層のキャッシュは第3階層のキャッシュよりも数分の1の大きさのため、これによって第2階層のブルームフィルタがより効率的になる。検索の際は、すべての書込みキャッシュを確認する必要がある。図5において、領域Aをスイープするためには、第3階層の書込みキャッシュから2回の追加読出し、第2階層のキャッシュから最大4回の追加読出しが必要となる。この回数はブルームフィルタの偽陽性率によって決まる。また、第3階層の書込みキャッシュがなく第2階層の書込みキャッシュのみの領域Bをスイープするためには、追加の読出しは1回だけである。[複数階層の書込みキャッシュ構成の評価]様々な書込みキャッシュ構成の比較を、図6に示す。比較対象のすべての構成はk個のエントリを保存することを目的としている。偽陽性率1のブルームフィルタを使用すると仮定する。ファクタαalphaは、書込みキャッシュ負荷率のオーバーヘッドを含む、1つの書込みキャッシュメタデータ記録またはハッシュテーブルメタデータ記録の保存に必要な領域である。すべての階層での書込みキャッシュの最大負荷率は同じで、75であると仮定する。エントリサイズは8バイトに設定する。ファクタγgammaは、ソリッドステート重複排除インデックス全体に保存されている総エントリ数に対する、すべての階層の書込みキャッシュに保存されるエントリ数の割合である。本願では、γgammaが約0.2書込みキャッシュ内のエントリの5倍のエントリがハッシュテーブル内に保存されているになると想定している。第3階層の書込みキャッシュのみを使用する場合図6の2列目は、追加の読出し数の線形増加と引き換えに、RAMの線形減少が得られる。第2階層の書込みキャッシュのみを使用する場合3列目は、書込みキャッシュ用のRAMは削減されるがブルームフィルタ用に追加のRAMが必要となるため、総合的に見ると減少が制限される。第2階層と第3階層の書込みキャッシュの組み合わせが最も効率的である。第2階層と第3階層の書込みキャッシュによって実現されるRAMの減少が乗算される4列目。右端の列では、3階層のキャッシュ構成でn2=4、n3=2の場合に、メモリ消費が10分の1になり、それに伴う平均コストは検索時にSSDからの読出しが約1回増えるだけである。[エントリの削除]重複排除ストレージシステムからデータを削除することは重要な問題である。重複排除機能があるため、ユーザが削除を望むチャンクを本当にシステムから削除すべきかどうか判断することは難しい。そのため、システムはそのチャンクを直ちに削除せず、マークアンドスイープのガーベジコレクションと同様に、データチャンクを構築してオフライン処理として削除を実施する。削除処理はシステム全体に影響を与え、新たなシステム状態を計算するため、事実上、新たなバージョンのコンテナが計算される。ソリッドステート重複排除インデックスからエントリを削除する設計は、このアプローチにうまく適合する。削除処理はコンテナレベルで実行される。マーキングの段階では、メタデータファイル内の回収するチャンクを削除対象としてマークするが、直ちにそのチャンクをコンテナから削除するわけではない。領域の再利用はバックグラウンド処理であり、チャンクは独立して各コンテナから回収される。回収によってコンテナが書き換えられると、削除対象としてマークされていないチャンクのみが残る。各コンテナには固有の識別子があり、コンテナの識別子は回収の前後で異なる。回収の際、古い識別子を削除としてマークすることによって、その変換のすべてをハッシュテーブルから論理的に削除するなお、削除中にコアハッシュテーブルの状態が修正されることはない。新たなバージョン内に存在するチャンクは、通常の入力動作を用いて新たな識別子と共にハッシュテーブルに入力される。ハッシュテーブルは、ハッシュテーブルのスイープの間に古い場所localizationから更新され、古い識別子はスイープが終了した後、再利用することができる。ハッシュテーブル内に存在するエントリが、メタデータファイルから削除されることもあり得る。なぜならメタデータファイルの状態が上位にくるからである。検索の際に、そのような削除済みのエントリが発見された場合は、メタデータテーブルからの読出し後のキー検証に失敗した場合と同様に、ハッシュテーブルに戻って所定のキーの検索を継続する。すでに削除されたブロックの問い合わせを行うことは、検索時のパフォーマンスの低下SSDからの読出しの追加をもたらす場合がある。このようなパフォーマンスの低下は深刻なものではなく、最終的にハッシュテーブルの状態はスイープによって修正される。[性能評価]様々な解決策について、2ラックユニットボックスに搭載されるシステムを対象とすると仮定して評価する。これらのシステムは通常、DataDomainDD630またはNECHYDRAstorHS3-210と同様に、データ記憶装置用に12台の1TBディスクを搭載している。以下の4つの解決策を比較した。DataDomainDDシステム非特許文献1:偽陽性率0.3のブルームフィルタ2.3GBのRAMでチャンクがシステム内に存在しない場合の処理を高速化し、ストリームプリフェッチ1GBのRAMでチャンクがシステム内に存在する場合の処理を高速化する。この解決策については第1章で詳しく述べた。MicrosoftのChunkStashCS非特許文献3:cuckooハッシュテーブル1GBのRAMとストリームプリフェッチ1GBのRAMを使用。SSDIと同様に、CSは辞書構造をハッシュテーブルとコンテナのメタデータを持つファイル我々の解決策でのメタデータファイルに匹敵に分割する。ハッシュテーブルをRAMに保存し、メタデータファイルをSSDに保存する。ハッシュテーブルのサイズを削減するためにcuckooハッシュを使用し通常のハッシュよりも高負荷率が可能、テーブルエントリはメタデータファイルの識別子のみを含むファイル内の正確なオフセットについては不明。150億チャンク用のハッシュテーブルは約10GBのメモリを消費するエントリサイズは6バイト。ソリッドステート重複排除インデックスSSDI:ストリームプリフェッチを使用せず、メモリ内にすべての書込みキャッシュを保存する4GBのRAM、SSDには書込みキャッシュなし。ソリッドステート重複排除インデックス3階層SSDI:3階層の書込みキャッシュを使用し、n2=4、n3=20.4GBのRAM、約4GBのSSD。ストリームプリフェッチは使用しない。解決策を比較するために、ディスクとSSDの使用率を計算するシミュレータを実装した。シミュレータの結果と上記で説明したSSD/HHDの特徴に基づいて、各々の解決策の性能を推測したサーバが12台のHitachiUltrastart1TB7200RPMディスクと2台のIntelX25-5SSDを搭載し、最大15億チャンクを格納できると仮定。チャンクはSHA-256下記2参照で識別し、メタデータ記録のサイズは50バイトである。DataDomainサーバの設計にしたがって、ストレージディスクコンテナファイルおよびメタデータファイルの両方を格納はRAID-6で構成されると仮定した。この構成はディスクが2つ失われても耐えられる。DDとSSDIのシミュレーションでは、メタデータファイルのサイズは1MBで、CSについては64KBである下記3参照。コンテナファイルは5MBのチャンクにフラッシュされた下記4参照2チャンクの識別には任意の暗号ハッシュ関数を使用することができるが、本願ではSHA-1ではなくSHA-256に焦点を当てることに決定した。その理由は、SHA-1の弱点が発見されたため、攻撃の脅威が継続的に増していくからである。しかし、我々の解決策はSHA-1でも機能する。3CSはメタデータファイルのオフセットを保存しないため、DD/SSDIよりも小さなメタデータファイルを使用して読出し要求サイズを縮小する。4これは楽観的な推測である。フラッシュのチャンクサイズが大きいとレイテンシも大きくなり、バックアップアプリケーションにとっては厄介である。境界状態でのパフォーマンス最初の実験では、各解決策について次の2つのテストを実行した。新規fresh書込み重複0重複書込み重複100、ランダムな順序の重複各テストでは、8KBの複数のブロック内の計1TBのデータを書き込んだ。その結果を図7に示す。新規書込みについては、SSDIはDDおよびCSよりもわずかに良い結果となった。その理由は、SSDIではデータチャンクのコンテナファイルへの書込みによってディスクがほぼ完全に使用されているためである図8参照。DDはディスク常駐型ハッシュテーブルからの読出しにもディスクを使用してブルームフィルタの偽陽性に対応するが、CSはより小さなサイズのコンテナのメタデータファイルを実行するため、それらを書き込むためのディスクの使用が増加する。なお、我々の実験で測定されたDDに関する書込み性能は、上記1で述べたDD630システムの書込み性能1.1TB/時、つまり320MB/秒とほぼ確実に一致する。ランダムな重複図7については、SSDIには匹敵するものがない。なお、SSDIと比較して、3階層の書込みキャッシュによるパフォーマンスの低下はそれほど深刻ではなく約20、ランダムな重複は3階層のSSDIでも新規書込みより速く処理される。CSはメタデータファイルをRAMにプリフェッチし、DDと同様に、次の実行時の重複の順序が保存されるという事実に依存している。ランダムな重複の場合、ヒット毎にメタデータファイル全体を読み出す必要がある。実際のところ、ランダムな重複排除の帯域幅はディスクベースの解決策よりも良いが、しかし依然として劣っている。通常状態での性能2番目の実験は、SSDIへのメモリ内ストリームプリフェッチの実装が実現可能かどうかを判定するために行った。実際のバックアップからのデータを用いて、ストリームプリフェッチサイズが性能に与える影響を推測した。プリフェッチに保存するハッシュの数を、システム内に格納される全ハッシュの0.05~4に制限した32バイトのハッシュと仮定すると、RAM消費は375MBから3GBに相当する。この実験は、解決策がビジネスに利用できるかどうかを評価するものである。したがって、メモリ消費が多大なCSとSSDIは競争力がないため除外することに決定し、DDと3階層SSDIのみについて検討するCSは約10GBのRAMが必要、SSDIは約4GB。これは400MBしか必要としない3階層SSDIより多く、またDDは2.3GB必要だが、より小さなブルームフィルタを使用すれば実質的に削減することができる。プリフェッチは、LRULeastRecentlyUsed読出しキャッシュとして実装された。メタデータファイルのサイズは1MBで、これは1つ目の実験と同じであるが、プリフェッチのサイズは128KBであった各メタデータファイルは8つのプリフェッチを含む。3種類の実際のデータ群についてテストを行った。各データ群は次の一連のバックアップから構成される。Wikipedia:Wikipediaの5ヶ月分の月次バックアップで、各バックアップは約25GB、最後のバックアップでは40.9が重複。Mailboxes:ソフトウェア開発会社に勤務する従業員の約50のメールボックスの、32日分の日次バックアップ。各バックアップは約34GB、最後のバックアップでは94が重複。Homedirs:IT研究所に勤務する従業員約100人のホームディレクトリの、14週分の週次バックアップ。各バックアップは約78GBで、最後のバックアップでは98.6が重複。バックアップのストリームは、コンテンツ指定チャンク分割ContentDefinedChunkingと言われる技術を用いてチャンクに分割されたRabinのフィンガ-プリントは入力ストリームの小さな移動ウィンドウ上で計算され、フィンガープリントが特徴的な値に達したらチャンクの境界が設定される。平均チャンクサイズは8KBであった。このシーケンスの最後のバックアップの書込み性能を提示する。図9は、この結果を示している。Wikipediaは過半数が新たな書込みであり40.9が重複、これは書込み帯域幅に影響を及ぼす。プリフェッチのサイズにかかわらず、3階層SSDIはDDよりも3倍近い速さである。重複の順序は保存されるが、プリフェッチされたチャンクのかなりの部分は変更され、使用されない。性能はディスク帯域幅によって制限される。3階層SSDIは新たなデータの書込みにこの帯域幅を使用するが、DDは新たなデータの書込みとメタデータファイルの読み出しの両方にこれを使用する。Homedirsはほとんどが重複であり98.6、ここでは3階層SSDIはDDよりも5倍以上速い。Homedirsについては、性能は主にディスクとSSDからメタデータファイルを読み出す帯域幅によって制限される。WikipediaとHomedirsの双方に関して、LRUのプリフェッチサイズの増加に比例する性能の向上はあまり重要ではない。最も興味深い結果が観測されたのはMailboxesであった。メールボックスのバクアップは94が重複であったが、Eメールは小さなファイルに保存され、またアーカイブパリティ内のファイルの順序は、後続のバックアップの際には異なっている。これは書込みの局所性を損なう。したがって、DDのパフォーマンスは非常に悪かった。3階層SSDのパフォーマンスは約20~30倍優れていたが、ストリームプリフェッチのサイズはパフォーマンスに大きな影響を及ぼす。ストリームプリフェッチのサイズが0.5よりも小さい場合は逆効果であった。1つ目の実験でわかったように、プリフェッチなしも3階層SSDIは所定の重複率に関して400MB/秒を上回る。小さなプリフェッチに関するパフォーマンスは低かった。その理由は、SSDからの1回の読出し要求のサイズが512B5ではなく128KBだからである下記5参照。5この問題はLRUよりも精巧なプリフェッチアルゴリズムを使用することで解決される可能性が高いが、これは本発明の対象外である。コスト評価。様々な解決策のコストを比較するために、RAM価格は31.25/GBKingstonの4GBECC、フルバッファRAMが125であることに基づく、SSD価格は2.75/GBIntelのX25-MSSD80GBドライブが220であることに基づくと仮定した。この結果を図10に示す。我々はストリームプリフェッチなしの解決策を比較する。3階層SSDIはCSに比べて約1/2の価格だが、DDよりは約4倍高い。これは残念なことのように思われるが、3階層SSDIはDDよりもはるかにパフォーマンスが良く、SSDはRAMよりもはるかに早いスピードで価格が低下している。我々は、3階層SSDIおよびCSの全体的なコストが数年で一致すると予想している。[関連技術]インライン重複排除を高速化するためにフラッシュメモリを使用するアイデアは、ChunkStashCS非特許文献3に記載されている。CSについては上記で説明したが、我々の解決策よりもはるかに多くのメモリを消費し、ランダムな重複に関するパフォーマンスは我々のものよりもはるかに悪い。この文献の著者は、ハッシュテーブル内にチャンクの断片のみを保存することでハッシュテーブルのサイズを削減できる可能性があるとしているが、これは重複排除機能の信頼性を損なうことを意味する。非特許文献4に記載されているシステムdedupv1DDv1も、SSDベースの構造を用いてインライン重複排除を実施している。DDv1ではすべてのチャンクのメタデータをフラッシュベースのハッシュテーブルに直接保存する我々の解決策とは違い、メタデータファイルは個別に保存されない。ハッシュテーブルをインプレースで更新しない代わりに、メモリ内で修正がキャッシュされ、テーブル全体を書き換えることで、これが適用される我々の解決策のスイープと似ているが、このテーブルはスイープ領域に分割されることはない。一見すると、このような構成はランダムな重複をSSDIと同様に効率的に処理できるように思われる。しかし、非特許文献4はSSDの限られた削除/書込耐性により発生する問題に対処しておらず、またスイープによって発生するSSDのパフォーマンスの低下について研究しておらず、書込みキャッシュの保存に必要なRAMの容量についても論じていない。上記で述べたSSD耐性、SSD利用率、およびRAM消費に関する説明に続いて、ここでDDv1とSSDIとを比較する。DDv1でハッシュテーブルに保存されるエントリは、SSDIで保存されるエントリよりもはるかに大きい。SHA-256のハッシュ値については、DDv1のエントリは約50バイトだが、SSDIのエントリは8バイトである。負荷率が75と仮定するとcuckooハッシュは検索時のSSDの読出しを増加させるため、いずれもこのハッシュは使用できない、DDv1のハッシュテーブルは100GB消費するが、SSDIのハッシュテーブルはわずか16GBである。確かに、SSDIはメタデータファイルを保存するため更に75GB必要になるDDv1ではすべてがハッシュテーブルに含まれるため追加の領域は必要ない。図11は、SSDIとDDv1を比較したものである。ハッシュテーブルが大きくなれば、スイープによるSSDのパフォーマンスの低下も大きくなる。しかし、最も重要な違いは書込みキャッシュに必要なRAMである。DDv1のハッシュテーブルに保存されるエントリの方が大きいため、それに比例してDDv1の書込みキャッシュも大きくなる。全体として、DDv1が必要なRAMはSSDIが必要なRAMの6倍以上である。これは特に重要である。なぜなら、24GBというのは、ディスクベースの解決策非特許文献1,2に必要なRAMよりもはるかに大きく、またSSDIのハッシュテーブルよりも大きいため、DDv1の有用性を低下させるからである。重複識別問題に対するディスクベースの解決策は数多くあるが、そのすべてに何らかの弱点がある。まず、Ventiのシステム非特許文献5では、問題が認められているが解決されていない。非特許文献1,2に記載されている最も一般的な解決策は、メモリ内のブルームフィルタとストリームプリフェッチを使用している。ストリームプリフェッチは、重複の順序が当初の書込み時のものと異なる場合は有効に機能せず、その場合に書込み性能が著しく低下する。MAD2非特許文献6は、インライン重複排除を提供するディスクベースの解決策の1つである。ハッシュ領域はタンカtankersに分割され、時間的に近接して書き込まれたチャンクのハッシュ値は同じタンカに入力される。各タンカは自身のブルームフィルタを所有し、自身のチャンクが重複していると識別された場合、そのタンカはメモリにプリフェッチされる。このアプローチも重複の順序が当初の書込みの順序と同じであるという事実に依存しており、ランダムな重複については機能しない。SparseIndexing非特許文献7およびExtremeBinning非特許文献8は、後続のバックアップ内のデータの類似性に依存している。これらの技術は、システムに書き込まれるチャンクのハッシュ値を、事前に書き込まれたすべてのチャンクのハッシュ値と比較するのではなく、類似するチャンクのブロックからのハッシュ値とのみ比較する。これは、過半数の重複を識別することのみを目的としているためランダムな重複には機能しない、重複排除の信頼性に欠ける。ディスクベースの解決策の中には、HashJoin非特許文献9、Debar非特許文献10、またはDecentralizedDeduplication非特許文献11のように、オフラインでの重複排除を提案するものも多い。チャンクは常に新規のものとしてディスクに書き込まれ、オフラインでチェックと重複排除の処理を行う。このような解決策では、すべての重複チャンクは必要性がないにもかかわらず各バックアップ時に書き込まれることとなり、パフォーマンスに悪影響を及ぼす。非特許文献12で提案されているAlphardは、SSDを用いて書込みインセンティブwriteincentive作業負荷を効率的にサポートするキー値格納装置keyvaluestoreを提供する。Alphardの設計が目指したものは我々とは違っており、ディスクベースのストレージシステム用の低レイテンシチャンク書込みキャッシュとして機能する。Alphardはディスクベースのシステムよりも保存するチャンクが少ないため、Alphardに格納されるすべてのチャンクのインデックスをRAMに保存することができる。SSDIの設計は、DBMSでのインデック作成を目的とするPBFilter非特許文献13,14がその動機となった部分がある。PBFilterはSSD上にも保存されるが、ハッシュテーブルを使用する代わりに、インデックスを追加のみのログとして構成する。ブルームフィルタを使用して書込みキャッシュを集約するというアイデアは非特許文献15に記載されているが、キャッシュは階層的に構成されておらず、ディスク上に保存されている。フラッシュデバイス上の非常に小さなブロックに効率的に書込みを行う方法に関する興味深いアイデアが非特許文献16に記載されている。このアイデアはSSDIの設計に取り入れることもできたが、SATASSDによく利用されているは必要なインタフェースを持っていない。[結論]本願における研究により、2つの商用フラッシュベースSSDを持つ2Uサーバを使用すれば、インライン重複排除時にディスクがボトルネックになる問題を解決できることがわかった。SSDIと3階層SSDIによって達成された結果には期待が持てる。さらに、より多くのSSDドライブ、または1秒当たりのランダムな読出しを増やすことができるフラッシュベースの装置を使用し、提案した解決策とストリームプリフェッチを組み合わせることで、より優れたパフォーマンスが得られる可能性もある。プライマリストレージは、バックアップやアーカイブストレージに加えて、SSDIを適用できるもう1つの分野である。ランダムな読出しおよび書込み時における検索動作のレイテンシが低いことは、プライマリストレージの非常に大きな利点である。したがって、SSDIはプライマリストレージの重複排除機能を可能にする主要な技術の1つになり得る。<実施形態2>本発明の第2の実施形態を、図12乃至図19を参照して説明する。図12は、システム全体の構成を示すブロック図である。図13は、ストレージシステムの概略を示すブロック図であり、図14は、構成を示す機能ブロック図である。図15乃至図19は、ストレージシステムの動作を説明するための説明図である。ここで、本実施形態では、ストレージシステムがHYDRAstorといったシステムであり、複数台のサーバコンピュータが接続されて構成されている場合を説明する。但し、本発明におけるストレージシステムは、複数台のコンピュータにて構成されることに限定されず、1台のコンピュータで構成されていてもよい。図12に示すように、本発明におけるストレージシステム10は、ネットワークNを介してバックアップ処理を制御するバックアップシステム11に接続している。そして、バックアップシステム11は、ネットワークNを介して接続されたバックアップ対象装置12に格納されているバックアップ対象データ記憶対象データを取得し、ストレージシステム10に対して記憶するよう要求する。これにより、ストレージシステム10は、記憶要求されたバックアップ対象データをバックアップ用に記憶する。そして、図13に示すように、本実施形態におけるストレージシステム10は、複数のサーバコンピュータが接続された構成を採っている。具体的に、ストレージシステム10は、ストレージシステム10自体における記憶再生動作を制御するサーバコンピュータであるアクセラレータノード10Aと、データを格納する記憶装置を備えたサーバコンピュータであるストレージノード10Bと、を備えている。なお、アクセラレータノード10Aの数とストレージノード10Bの数は、図13に示したものに限定されず、さらに多くの各ノード10A,10Bが接続されて構成されていてもよい。さらに、本実施形態におけるストレージシステム10は、データを分割及び冗長化し、分散して複数の記憶装置に記憶すると共に、記憶するデータの内容に応じて設定される固有のコンテンツアドレスによって、当該データを格納した格納位置を特定するコンテンツアドレスストレージシステムである。このコンテンツアドレスストレージシステムについては、後に詳述する。なお、以下では、ストレージシステム10が1つのシステムであるとして、当該ストレージシステム10が備えている構成及び機能を説明する。つまり、以下に説明するストレージシステム10が有する構成及び機能は、アクセラレータノード10Aあるいはストレージノード10Bのいずれに備えられていてもよい。なお、ストレージシステム10は、図13に示すように、必ずしもアクセラレータノード10Aとストレージノード10Bとを備えていることに限定されず、いかなる構成であってもよく、例えば、1台のコンピュータにて構成されていてもよい。さらには、ストレージシステム10は、コンテンツアドレスストレージシステムであることにも限定されない。図14に、ストレージシステム10の構成を示す。この図に示すように、ストレージシステム10は、一般的な情報処理装置と同様に、所定の処理を行うための作業領域である主記憶装置としてRAM31を備えており、また、記憶対象となるバックアップ対象データ自体を記憶する第一補助記憶装置であるハードディスクドライブ33HDD:HardDiskDriveを備えている。さらに、一般的に例えば、比較的小さいサイズのデータの書き込みなどの一部の処理を除いて、HDD33よりもアクセス速度が高速な第二補助記憶装置としてSSDSolidStateDrive32を備えている。なお、RAM31は、HDD33及びSSD32よりもデータのアクセス速度が高速である。また、ストレージシステム10は、記憶対象となるデータの格納位置を管理するデータ管理部21と、新たに記憶されるデータが既にHDD33に記憶されているか否かを判定する重複判定部22と、を備えている。なお、実際には、上記データ管理部21と重複判定部22とは、図13に示したアクセラレータノード10A及びストレージノード10Bが備えているCPUCentralProcessingUnitなどの複数の演算装置にプログラムが組み込まれることで構成されている。また、HDD33は、主にストレージノード10Bが備えている記憶装置にて構成されている。ここで、上記プログラムは、例えば、CD-ROMなどの記憶媒体に格納された状態でストレージシステム10に提供される。あるいは、上記プログラムは、ネットワーク上の他のサーバコンピュータの記憶装置に記憶され、当該他のサーバコンピュータからネットワークを介してストレージシステム10に提供されてもよい。以下、上記データ管理部21と重複判定部22の構成について詳述する。まず、データ管理部21は、図16の矢印Y1に示すように、ストリームデータであるバックアップ対象データAの入力を受けると、図15及び図16の矢印Y2に示すように、当該バックアップ対象データAを、所定容量例えば、64KBのブロックデータDに分割する。そして、このブロックデータDのデータ内容に基づいて、当該データ内容を代表する固有のハッシュ値H特徴データを算出する矢印Y3。例えば、ハッシュ値Hは、予め設定されたハッシュ関数を用いて、ブロックデータDのデータ内容から算出する。なお、このデータ管理部21による処理は、アクセラレータノード10Aにて実行される。そして、上記重複判定部22は、バックアップ対象データAのブロックデータDのハッシュ値Hを用いて、当該ブロックデータDが既に記憶装置30に格納されているか否かを調べる。具体的には、まず、既に格納されているブロックデータDは、そのハッシュ値Hと格納位置を表すコンテンツアドレスCAが、関連付けてMFIMainFragmentIndexファイルに登録されている。従って、重複判定部22は、格納前に算出したブロックデータDのハッシュ値HがMFIファイル内に存在している場合には、既に同一内容のブロックデータDが格納されていると判断できる図16の矢印Y4。この場合には、格納前のブロックデータDのハッシュ値Hと一致したMFI内のハッシュ値Hに関連付けられているコンテンツアドレスCAを、当該MFIファイルから取得する。そして、このコンテンツアドレスCAを、記憶要求にかかるブロックデータDのコンテンツアドレスCAとして記憶する。あるいは、既に格納されているブロックデータDを参照するコンテンツアドレスCAをさらに参照する他のアドレスデータを、ツリー構造にて記憶する。これにより、このコンテンツアドレスCAにて参照される既に格納されているデータが、記憶要求されたブロックデータDとして使用されることとなり、当該記憶要求にかかるブロックデータDは記憶する必要がなくなる。なお、重複判定部22は、実際には、ブロックデータDのハッシュ値をさらにハッシュ計算したインデックスデータも用いて重複判定を行っているが、これについては後述する。また、データ管理部21は、は、上述したように重複判定部22にてまだ記憶されていないと判断されたブロックデータDを圧縮して、図16の矢印Y5に示すように、複数の所定の容量のフラグメントデータに分割する。例えば、図15の符号D1~D9に示すように、9つのフラグメントデータ分割データ41に分割する。さらに、データ管理部21は、分割したフラグメントデータのうちいくつかが欠けた場合であっても、元となるブロックデータを復元可能なよう冗長データを生成し、上記分割したフラグメントデータ41に追加する。例えば、図15の符号D10~D12に示すように、3つのフラグメントデータ冗長データ42を追加する。これにより、9つの分割データ41と、3つの冗長データとにより構成される12個のフラグメントデータからなるデータセット40を生成する。なお、上記データ管理部21による処理は、1つのストレージノード10Bによって実行される。そして、データ管理部21は、生成されたデータセットを構成する各フラグメントデータを、HDD33に形成された各記憶領域に、それぞれ分散して格納する。例えば、図15に示すように、12個のフラグメントデータD1~D12を生成した場合には、12個のHDD33内にそれぞれ形成したデータ格納ファイルF1~F12データ格納領域に、各フラグメントデータD1~D12を1つずつそれぞれ格納する図16の矢印Y6参照。また、データ管理部21は、上述したようにHDD33に格納したフラグメントデータD1~D12の格納位置、つまり、当該フラグメントデータD1~D12にて復元されるブロックデータDの格納位置を表す、コンテンツアドレスCAを生成して管理する。具体的には、格納したブロックデータDの内容に基づいて算出したハッシュ値Hの一部ショートハッシュ例えば、ハッシュ値Hの先頭8Bバイトと、論理格納位置を表す情報と、を組み合わせて、コンテンツアドレスCAを生成する。そして、このコンテンツアドレスCAを、ストレージシステム10内のファイルシステム、つまり、アクセラレータノード10Aに返却する図16の矢印Y7。すると、アクセラレータノード10Aは、バックアップ対象データのファイル名などの識別情報と、コンテンツアドレスCAとを関連付けてファイルシステムで管理する。このとき、コンテンツアドレスCAは、SSD32に形成されたメタデータテーブル内に格納される。また、データ管理部21は、さらに、格納したブロックデータDの格納位置を表すコンテンツアドレスに含まれるハッシュ値特徴データを参照するインデックスデータを生成して管理する。具体的には、ブロックデータDのハッシュ値のデータ内容をさらにハッシュ計算した値をインデックスデータとして算出してハッシュテーブルに格納し、このインデックスデータにて上記ブロックデータDのハッシュ値を参照する。ここで、上記ブロックデータDと、ハッシュ値を含むコンテンツアドレスCAと、インデックスデータと、の関係を図18に示す。以上のようにして、HDD33に格納されるブロックデータDは、まず、コンテンツアドレスCAにて参照され、そしてこのコンテンツアドレスCAがハッシュテーブルのインデックスデータにて参照された状態となる。従って、上述した重複判定部22は、新たに記憶しようとするデータを分割したブロックデータDのハッシュ値と、このハッシュ値をさらにハッシュ計算したインデックスから辿ることができる既に記憶されているメタデータテーブルに格納されたコンテンツアドレスCA内のハッシュ値と、を比較することで、重複判定を行うことができる。なお、本発明では、上記インデックスデータの格納方法に特徴を有するが、これについては後述する。また、データ管理部21は、ブロックデータDのコンテンツアドレスCAと、当該ブロックデータDのハッシュ値Hと、を関連付けて、各ストレージノード10BがMFIファイルにて管理する。さらに、データ管理部21は、上述したように格納したバックアップ対象データを読み出す制御を行う。例えば、ストレージシステム10に対して、特定のファイルを指定して読み出し要求があると図17の矢印Y11参照、まず、ファイルシステムに基づいて、読み出し要求にかかるファイルに対応するハッシュ値の一部であるショートハッシュと論理位置の情報からなるコンテンツアドレスCAを指定する図17の矢印Y12参照。そして、データ管理部21は、コンテンツアドレスCAがMFIファイルに登録されているか否かを調べる図17の矢印13参照。登録されていなければ、要求されたデータは格納されていないため、エラーを返却する。一方、読み出し要求にかかるコンテンツアドレスCAが登録されている場合には、上記コンテンツアドレスCAにて指定される格納位置を特定し、この特定された格納位置に格納されている各フラグメントデータを、読み出し要求されたデータとして読み出す図17の矢印Y14参照。このとき、各フラグメントが格納されているデータ格納ファイルF1~F12と、当該データ格納ファイルのうち1つのフラグメントデータの格納位置が分かれば、同一の格納位置から他のフラグメントデータの格納位置を特定することができる。そして、データ管理部21は、読み出し要求に応じて読み出した各フラグメントデータからブロックデータDを復元する図17の矢印Y15参照。さらに、データ管理部21は、復元したブロックデータDを複数連結し、ファイルAなどの一群のデータに復元して、読み出し制御を行っているアクセラレータノード10Aに返却する図17の矢印Y16参照。ここで、本発明におけるデータ管理部21は、上述したようにブロックデータDをHDD33に格納する際に、このブロックデータDのハッシュ値をさらにハッシュ計算して算出したインデックデータを、図19に示すようにRAM31とSSD32に格納する。これについて詳述する。まず、図19の斜線にて示すように、レベル1段階として、RAM31内に1エントリを上限としインデックスデータを保存する。すると、RAM31内に保存されたインデックスデータの量が上限に達するため、その後さらにインデックスデータを保存する際には、既にRAM31内に保存されているインデックスデータを、レベル2段階としてSSD32内に保存する。同時に、RAM31に保存されていたインデックスデータを削除することで、RAM31に空きができ、新たなインデックスデータを保存する。なお、上記では、レベル1段階でRAM31内にインデックスデータを保存する上限は、1エントリ単位である場合を例示したが、さらに多くの単位のインデックスデータを保存可能としてもよい。そして、RAM31からレベル2段階としてSSD32にインデックスデータを保存することを、当該レベル2段階としてSSD32に予め設定された保存量の上限となるまで繰り返す。ここでは、例えば、n2個の単位のインデックスデータを格納する。このとき、レベル2段階では、斜線にて示すように、SSD32に保存された各インデックスデータのブルームフィルタを、それぞれRAM31に保存する。なお、ブルームフィルタは、レベル2段階のSSD32に保存されているインデックスデータのデータ内容に基づいて算出されたデータ要素データであり、当該SSD32にインデックスデータが存在するか否かを高速に判定するために用いられるものである。つまり、新たに書き込まれるデータとの重複判定の際に使用される。その後、レベル2段階のSSD32に保存されたインデックスデータが、予め設定された上限量であるn2個に達すると、このレベル2段階のSSD32に保存されたn2個のインデックスデータと、RAM31に保存された1個のインデックスデータと、を結合する。そして、結合したn21のインデックスデータを、レベル3段階のSSD32に格納し直す。同時に、レベル2段階のSSD32に保存されたインデックスデータ及びRAM31に保存されたブルームフィルタ、さらに、レベル1段階のRAM31に保存された1個のインデックスデータを、それぞれ削除する。これにより、新たなにレベル1段階のRAM31とレベル2段階のSSD32に空きができ、新たなインデックスデータを保存できる。そして、上記レベル3段階のSSD32に保存したインデックスデータが、予め設定された上限、例えば、n3×n21個単位に達すると、全てのインデックスデータがスイープ領域に書き込まれる。なお、上記では、レベル2段階からレベル3段階のSSD32に保存される際に、レベル2段階のSSD32に保存されているインデックスデータに加えて、レベル1段階のRAM31に保存しているインデックスデータを結合する場合を例示したが、RAM31内のインデックスデータを結合することに限定されない。つまり、レベル2段階のSSD32に保存されている複数個単位のインデックスデータのみを結合して、レベル3段階としてもよい。また、上記では、レベル2段階のSSD32に保存されるインデックスデータのブルームフィルタをRAM31内に保存する場合を例示したが、ブルームフィルタは必ずしも保存しなくてもよい。<付記>上記実施形態の一部又は全部は、以下の付記のようにも記載されうる。以下、本発明におけるストレージシステム100図20参照、プログラムを記憶した記憶媒体、データ管理方法の構成の概略を説明する。但し、本発明は、以下の構成に限定されない。付記1記憶対象データを格納する第一補助記憶装置113と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置112と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置111と、を備え、記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部101と、新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部102と、を備え、前記データ管理部101は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、ストレージシステム100。付記2付記1に記載のストレージシステムであって、前記データ管理部は、前記第二補助記憶装置に記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合して当該第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置から削除する、ストレージシステム。付記3付記2に記載のストレージシステムであって、前記データ管理部は、前記第二補助記憶装置に記憶保持されている前記複数単位のインデックスデータと前記主記憶装置に記憶保持されている前記インデックスデータとを結合して前記第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置及び前記主記憶装置から削除する、ストレージシステム。付記4付記2に記載のストレージシステムであって、前記データ管理部は、前記第二補助記憶装置に記憶された前記インデックスデータが存在するか否かを判定するために用いられる当該インデックスデータのデータ内容に基づく要素データを、前記主記憶装置に記憶する、ストレージシステム。付記5付記4に記載のストレージシステムであって、前記データ管理部は、前記第二補助記憶装置に記憶された前記インデックスデータをまとめて当該第二補助記憶装置に記憶し直す際に、前記主記憶装置に記憶された前記インデックスデータの前記要素データを解放する、ストレージシステム。付記6付記1に記載のストレージシステムであって、前記第一補助記憶装置はハードディスクドライブであり、前記第二補助記憶装置はSSDSolidStateDriveである、ストレージシステム。付記7記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えた情報処理装置に、記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照するデータ管理部と、新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定する重複判定部と、を実現させると共に、前記データ管理部は、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、ことを実現させるためのプログラムを記憶した記憶媒体。付記8付記7に記載のプログラムを記憶した記憶媒体であって、前記データ管理部は、前記第二補助記憶装置に記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合して当該第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置から削除する、プログラムを記憶した記憶媒体。付記9記憶対象データを格納する第一補助記憶装置と、当該第一補助記憶装置よりもデータのアクセス速度が高速な第二補助記憶装置と、前記第一補助記憶装置及び前記第二補助記憶装置よりもデータのアクセス速度が高速な主記憶装置と、を備えたストレージシステムにて、記憶対象データを前記第一補助記憶装置に格納し、この記憶対象データの格納位置を当該記憶対象データのデータ内容に基づく特徴データを用いて管理すると共に、前記特徴データのデータ内容に基づくインデックスデータにて当該特徴データを参照することにより、記憶対象データを管理し、新たに記憶する記憶対象データのデータ内容に基づく前記特徴データ及び当該特徴データのデータ内容に基づく前記インデックスデータを用いて、前記新たに記憶する記憶対象データと同一の記憶対象データが既に前記第一補助記憶装置に格納されているか否かを判定すると共に、記憶対象データを管理する際に、前記第一補助記憶装置に記憶した前記記憶対象データの前記特徴データを参照して当該特徴データに基づく前記インデックスデータを前記主記憶装置に記憶保持すると共に、前記主記憶装置に対して記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該主記憶装置に記憶保持されている前記インデックスデータを前記第二補助記憶装置に記憶保持し、この第二補助記憶装置に記憶保持された前記インデックスデータを前記主記憶装置から削除する、データ管理方法。付記10付記9に記載のデータ管理方法であって、記憶対象データを管理する際に、前記第二補助記憶装置に記憶保持された前記インデックスデータが予め設定された量に達した場合に、当該第二補助記憶装置に記憶保持されている複数単位の前記インデックスデータを結合して当該第二補助記憶装置に記憶保持し直すと共に、結合される前の前記インデックスデータを前記第二補助記憶装置から削除する、データ管理方法。"