"データストリームを任意の容量に分割したブロックデータを、当該ブロックデータのデータ内容に基づくアドレスデータにて参照して記憶装置に格納すると共に、記憶装置に既に記憶されている前記ブロックデータと同一のデータ内容の他のブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記ブロックデータを前記他のブロックデータとして参照する前記アドレスデータを記憶装置に格納して前記ブロックデータの重複記憶排除を行うブロックデータ重複排除部と、前記ブロックデータをさらに複数に分割した各サブブロックデータを、当該各サブブロックデータの各データ内容に基づく各サブアドレスデータにて参照して記憶装置に記憶すると共に、前記各サブアドレスデータからなるサブアドレスデータ群を所定の記憶装置に記憶し、記憶装置に既に記憶されている前記サブブロックデータと同一のデータ内容の他のサブブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記サブブロックデータを前記他のサブブロックデータとして参照する前記サブアドレスデータを前記所定の記憶装置に格納して前記サブブロックデータの重複記憶排除を行うサブブロックデータ重複排除部と、を備えた、ストレージシステム。請求項1に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記ブロックデータ重複排除部にて重複記憶排除されない前記他のブロックデータを複数に分割した前記各サブブロックデータに対して前記サブブロックデータの重複記憶排除を行う、ストレージシステム。請求項1に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記データストリーム内の一部の前記ブロックデータから当該ブロックデータのデータ内容に基づいて検出した特徴値が設定条件を満たす場合に、当該設定条件を満たす特徴値が検出された前記ブロックデータに隣接する別の前記ブロックデータを分割した前記各サブブロックデータを参照する前記サブアドレスデータ群を、前記設定条件を満たす特徴値に関連付けて前記所定の記憶装置に記憶する、ストレージシステム。請求項3に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記データストリーム内の一部の前記ブロックデータから検出した前記特徴値が前記所定の記憶装置に既に記憶されている場合に、当該特徴値に関連付けられて既に記憶されている前記サブアドレスデータ群と、前記特徴値が検出された前記ブロックデータに隣接する別の前記ブロックデータを形成する前記各サブブロックデータを参照する前記サブアドレスデータ群と、を比較して、前記サブブロックデータの重複記憶排除を行う、ストレージシステム。請求項4に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記サブアドレスデータ群の比較により、記憶装置に記憶されていない前記サブブロックデータが複数存在する場合に、当該複数のサブブロックデータをまとめて記憶装置に記憶する、ストレージシステム。請求項3に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記設定条件を満たす特徴値に、複数の前記サブアドレスデータ群を関連付けて前記所定の記憶装置に記憶する、ストレージシステム。請求項2に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記設定条件を満たす特徴値に関連付けた前記サブアドレスデータ群を、前記ブロックデータ及び前記サブブロックデータを記憶する記憶装置よりも読み書き速度が速い前記所定の記憶装置に記憶する、ストレージシステム。情報処理装置に、データストリームを任意の容量に分割したブロックデータを、当該ブロックデータのデータ内容に基づくアドレスデータにて参照して記憶装置に格納すると共に、記憶装置に既に記憶されている前記ブロックデータと同一のデータ内容の他のブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記ブロックデータを前記他のブロックデータとして参照する前記アドレスデータを記憶装置に格納して前記ブロックデータの重複記憶排除を行うブロックデータ重複排除部と、前記ブロックデータをさらに複数に分割した各サブブロックデータを、当該各サブブロックデータの各データ内容に基づく各サブアドレスデータにて参照して記憶装置に記憶すると共に、前記各サブアドレスデータからなるサブアドレスデータ群を所定の記憶装置に記憶し、記憶装置に既に記憶されている前記サブブロックデータと同一のデータ内容の他のサブブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記サブブロックデータを前記他のサブブロックデータとして参照する前記サブアドレスデータを前記所定の記憶装置に格納して前記サブブロックデータの重複記憶排除を行うサブブロックデータ重複排除部と、を実現させるためのプログラムを記憶した記憶媒体。請求項8に記載のプログラムを記憶した記憶媒体であって、前記サブブロックデータ重複排除部は、前記ブロックデータ重複排除部にて重複記憶排除されない前記他のブロックデータを複数に分割した前記各サブブロックデータに対して前記サブブロックデータの重複記憶排除を行う、ことを実現させるためのプログラムを記憶した記憶媒体。請求項8に記載のプログラムを記憶した記憶媒体であって、前記サブブロックデータ重複排除部は、前記データストリーム内の一部の前記ブロックデータから当該ブロックデータのデータ内容に基づいて検出した特徴値が設定条件を満たす場合に、当該設定条件を満たす特徴値が検出された前記ブロックデータに隣接する別の前記ブロックデータを分割した前記各サブブロックデータを参照する前記サブアドレスデータ群を、前記設定条件を満たす特徴値に関連付けて前記所定の記憶装置に記憶する、ことを実現させるためのプログラムを記憶した記憶媒体。データストリームを任意の容量に分割したブロックデータを、当該ブロックデータのデータ内容に基づくアドレスデータにて参照して記憶装置に格納すると共に、記憶装置に既に記憶されている前記ブロックデータと同一のデータ内容の他のブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記ブロックデータを前記他のブロックデータとして参照する前記アドレスデータを記憶装置に格納して前記ブロックデータの重複記憶排除を行い、前記ブロックデータをさらに複数に分割した各サブブロックデータを、当該各サブブロックデータの各データ内容に基づく各サブアドレスデータにて参照して記憶装置に記憶すると共に、前記各サブアドレスデータからなるサブアドレスデータ群を所定の記憶装置に記憶し、記憶装置に既に記憶されている前記サブブロックデータと同一のデータ内容の他のサブブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記サブブロックデータを前記他のサブブロックデータとして参照する前記サブアドレスデータを前記所定の記憶装置に格納して前記サブブロックデータの重複記憶排除を行う、情報処理方法。請求項11に記載の情報処理方法であって、重複記憶排除されない前記他のブロックデータを複数に分割した前記各サブブロックデータに対して前記サブブロックデータの重複記憶排除を行う、情報処理方法。請求項12に記載の情報処理方法であって、前記データストリーム内の一部の前記ブロックデータから当該ブロックデータのデータ内容に基づいて検出した特徴値が設定条件を満たす場合に、当該設定条件を満たす特徴値が検出された前記ブロックデータに隣接する別の前記ブロックデータを分割した前記各サブブロックデータを参照する前記サブアドレスデータ群を、前記設定条件を満たす特徴値に関連付けて前記所定の記憶装置に記憶する、情報処理方法。上述したCDCで作成されたチャンクは様々な長さのものがあるが、実際のサイズはCDCアルゴリズムのパラメータである想定チャンクサイズ値付近に集約される。CDCを用いる場合、あるバックアップストリームのシーケンスと特定のバックエンドについて、重複排除が最も機能する最適想定チャンク値がある。この値をどのように選択するかは、後続のストリームにおけるデータ修正のタイプと頻度、およびチャンク表示representationにかかるメタデータのオーバーヘッドによって異なる。メタデータのオーバーヘッドを考えると、小さなチャンクを使用するのは最適ではない。また小さなチャンクはパフォーマンスに悪影響を及ぼす恐れもある。一方、大きなチャンクも、後続のバックアップにおける修正の粒度が細かい場合は最適ではない。妥協点として、所定のストレージシステムでうまく機能する、適度な大きさの想定チャンク値を選択するのが良いと思われる。ただし、関連のない複数のシリーズのバックアップは言うまでもなく1つのバックアップシーケンスでも変更の粒度は一定ではない。このため、本発明の目的は、上述した課題である、データの重複排除のさらなる効率化を図ることができるストレージシステムを提供することにある。本発明の一形態であるストレージシステムは、データストリームを任意の容量に分割したブロックデータを、当該ブロックデータのデータ内容に基づくアドレスデータにて参照して記憶装置に格納すると共に、記憶装置に既に記憶されている前記ブロックデータと同一のデータ内容の他のブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記ブロックデータを前記他のブロックデータとして参照する前記アドレスデータを記憶装置に格納して前記ブロックデータの重複記憶排除を行うブロックデータ重複排除部と、前記ブロックデータをさらに複数に分割した各サブブロックデータを、当該各サブブロックデータの各データ内容に基づく各サブアドレスデータにて参照して記憶装置に記憶すると共に、前記各サブアドレスデータからなるサブアドレスデータ群を所定の記憶装置に記憶し、記憶装置に既に記憶されている前記サブブロックデータと同一のデータ内容の他のサブブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記サブブロックデータを前記他のサブブロックデータとして参照する前記サブアドレスデータを前記所定の記憶装置に格納して前記サブブロックデータの重複記憶排除を行うサブブロックデータ重複排除部と、を備えた、という構成をとる。また、本発明の他の形態であるプログラムを記憶した記憶媒体は、情報処理装置に、データストリームを任意の容量に分割したブロックデータを、当該ブロックデータのデータ内容に基づくアドレスデータにて参照して記憶装置に格納すると共に、記憶装置に既に記憶されている前記ブロックデータと同一のデータ内容の他のブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記ブロックデータを前記他のブロックデータとして参照する前記アドレスデータを記憶装置に格納して前記ブロックデータの重複記憶排除を行うブロックデータ重複排除部と、前記ブロックデータをさらに複数に分割した各サブブロックデータを、当該各サブブロックデータの各データ内容に基づく各サブアドレスデータにて参照して記憶装置に記憶すると共に、前記各サブアドレスデータからなるサブアドレスデータ群を所定の記憶装置に記憶し、記憶装置に既に記憶されている前記サブブロックデータと同一のデータ内容の他のサブブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記サブブロックデータを前記他のサブブロックデータとして参照する前記サブアドレスデータを前記所定の記憶装置に格納して前記サブブロックデータの重複記憶排除を行うサブブロックデータ重複排除部と、を実現させるためのプログラムを記憶した記憶媒体である。また、本発明の他の形態である情報処理方法は、データストリームを任意の容量に分割したブロックデータを、当該ブロックデータのデータ内容に基づくアドレスデータにて参照して記憶装置に格納すると共に、記憶装置に既に記憶されている前記ブロックデータと同一のデータ内容の他のブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記ブロックデータを前記他のブロックデータとして参照する前記アドレスデータを記憶装置に格納して前記ブロックデータの重複記憶排除を行い、前記ブロックデータをさらに複数に分割した各サブブロックデータを、当該各サブブロックデータの各データ内容に基づく各サブアドレスデータにて参照して記憶装置に記憶すると共に、前記各サブアドレスデータからなるサブアドレスデータ群を所定の記憶装置に記憶し、記憶装置に既に記憶されている前記サブブロックデータと同一のデータ内容の他のサブブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記サブブロックデータを前記他のサブブロックデータとして参照する前記サブアドレスデータを前記所定の記憶装置に格納して前記サブブロックデータの重複記憶排除を行う、という構成をとる。本発明は、以上のように構成されることにより、データの重複排除のさらなる効率化を図ることができるストレージシステムを提供することができる。<実施形態1>本実施形態では、ストレージシステムにおける重複排除の効率化を図るより良い方法を提案する。つまり、複数のバックアップにおいて、長期間に渡って変化しない長い一連のデータがあり、このようなデータには大きなサイズのチャンクの方が良い。その中に、変化のある領域が複数分散されており、これらは小さなサイズのチャンクの方が良い。従って、本願では、アンカー駆動型サブチャンク重複排除という新たなアルゴリズムについて述べる。この新しいアルゴリズムは、大きいチャンクとそのサブチャンクとの2段階で重複排除を行う。小さなチャンクでの重複排除は、サブチャンクからコンテナチャンクへの変換subchunktocontainerchunktranslationsにおける特別な重複排除コンテキスト情報を使用して行う。このコンテキストはバックエンドから読み出され、バックアップデータを書き込むプロセスで動的に更新される。このコンテキストは小さく、メインメモリに保存することができる。この新たなアプローチは、バックアップストリームに関するバックエンドの知識を必要とせず、あらゆるストリームにおいて小さなチャンクを使用する重複排除を可能にする。同時に、このコンテキストは、小さなチャンクを使用する重複排除を効果的に行う上で必要な、ほとんどのサブチャンク変換translationsを保持している。本願では、一連のバックアップトレースを使用してこの新たなアルゴリズムのシミュレーションを行い、その結果を、他のアルゴリズム、つまり従来のアルゴリズムを使用して得た様々な結果と比較することで、本願における主張を検証した。以下、本実施形態では、次のことを説明する。まず、この新たな重複排除アルゴリズムについて詳細に説明する。次に、一連の実際のバックアップトレースに基づいて行ったシミュレーションに基づく評価を述べる。次に、関連技術について説明し、最後に、結論と今後の研究について記載する。[アルゴリズム][システムモデル]本願のストレージシステムは、非特許文献9に挙げたHYDRAstorをモデルとして作成されている。HYDRAstorは、ファイルシステム抽象化abstractionをエクスポートするアクセスノードANsのフロントエンド構造と、多様なサイズのコンテンツアドレスブロックを保持するマルチノードブロックストレージstoreとしてのバックエンド構造と、により構成される。本願では、チャンクとデータのブロックとを区別する。チャンクは通常、連続する1つのユーザデータストリームであり、重複排除を最大限機能させるためにチャンク分割手段chunkerによって定められる境界線を持つ。ブロックは、バックエンドにより格納される基本ユニットである。ブロックは、このブロックのチャンクである1つのユーザデータと、関連付けられたバックエンドレベルのブロックメタデータを含む。ただし、チャンクも、他のブロックへのポインタを含むことができる。ポインタはハッシュアドレスとして表され、ファイルシステム構成を維持するツリーの構築を促進する。このシステムは、重複排除といったストレージシステムの特別な能力とは無関係な、標準的なバックアップアプリケーションを用いてバックアップの書込みと復元を行ういくつかのバックアップサーバからアクセスすることができる。このアルゴリズムについて議論する上では、上記のような拡張性を持つ分散型ストレージシステムを前提とする必要はない。ただし、様々な重複排除パターンを維持してバックアップを格納するためには、そのようなシステムの方が集約的なシステムよりも適している。そのため、すべての格納データに対して単一の想定チャンクサイズを使わない方がよい。なお、本発明にてストレージシステムで記憶するデータは、バックアップデータに限定されず、いかなるデータであってもよい。基本システムでは、バックアップストリームは、CDCアルゴリズムを使用してアクセスノードでチャンクに分割され、ブロックとしてブロックストレージに書き込まれる。書き込まれたチャンクが重複しないと判断されると、そのチャンクは圧縮され、復元力resiliencyのために冗長符号化され、得られたブロックフラグメントが別々のブロック格納サーバに格納される。なお、本システムでは、必ずしもデータを、分割、圧縮、冗長化しなくてもよい。このシステムは、ブロック毎の参照カウントを含み、オンデマンドでのデータ削除機能を持つ。削除は2つのフェーズで行われ、ブロックカウンタを再計算するガーベジ識別のフェーズと、カウンタ値がゼロのブロックをバックグラウンドで除去するスペース再利用のフェーズがある。重複排除アルゴリズムを設計する際は、削除処理との相互作用を考慮する必要がある。このようなシステムでは、重複排除アルゴリズムの評価に含めるべきメタデータの種類がいくつかある。最下位は、このブロックのコンテンツ由来アドレスを含むブロックメタデータで、次のレベルは、このブロックに属するポインタを含むメタデータである。また、更に高いレベルは、ファイルシステム構成と関連付けられたメタデータで、これには例えばinodeテーブルなどがある。ポインタを持つブロックが1つ失われると、複数のファイルまたはファイルシステム自体が不能になる場合がある非特許文献6。なぜなら、それらのブロックも重複排除される場合があるからである。したがって、すべてのシステムメタデータおよびポインタを持つブロックは、複数のコピーに保存される。ユーザデータについては、このシステムでは複数の冗長符号化された復元レベルに対応しており、ほとんどは非常に低いオーバーヘッドと復元レベルである。デフォルト値のオーバーヘッドは33で、3つのノードおよびディスク障害に耐えられる。[複数のチャンクサイズを使用する重複排除]複数のチャンクサイズを使用する重複排除に関する過去の2つの研究が、本願における研究の直接的な動機となった。バイモーダルbimodalアプローチ非特許文献10は、大小の2つのサイズのチャンクを使用する。デフォルトでは、新規のデータは大きいサイズのチャンクに分割される。さらに、重複しているチャンクと重複していないチャンクの間を移行する度に、1つまたは複数の隣接する大きなサイズのチャンクの新規データが小さなチャンクに分割され、これらの小さなチャンクがバックエンドに入力される。このアルゴリズムでは、小さなチャンク用のデータベースは必要ない。その代わりに、実際にどのチャンクを出力するかemitを決定する前に、バックエンドに対する既存のクエリーを用いて大きなチャンクの重複ステータスを確認する。Fingerdiffアルゴリズム非特許文献7は、データ群毎に、前回のバックアップで遭遇したが必ずしも出力されなかった、すべての小さなチャンクのデータベースを保持する。このデータベースは、バックエンドによって維持される、出力されたチャンクメタデータとは別に保持される。Fingerdiffは、小さなサイズのチャンクのレベルで重複を検出し、可能な限りこれらを合体するすべての新規データについて、小さなチャンクの最大可能数が限定されている。これらの2つのアプローチは改善の余地がある。バイモーダルアプローチは、重複排除された大きなチャンクに含まれる小さなチャンクの存在を忘れている。これは変化のある領域の境界線では特に重要である。Fingerdiffアルゴリズムは、前回のバックアップで見られたすべての小さなチャンクの実質的なデータベースが必要だが、変化の少ないデータに関しては、これはあまり有益ではない。また、このデータベースはメインメモリに適合しない場合があり、もしそうであればパフォーマンスに深刻な影響を及ぼす。さらに、Fingerdiffは、ストレージシステムがバックアップストリーム間の関係を特定できることを前提としているが、前述のようにそうではないことが多い。またFingerdiffは、関連性のないバックアップストリームにおいて、小さなチャンクのレベルでは重複を検出しない。[サブチャンクを使用する重複排除]本発明におけるアンカー駆動型サブチャンク重複排除という新たなアルゴリズムは、上記の従来のアプローチの欠点を解決する。概略を説明すると、サブチャンクを使用する重複排除は次の通りである。基本の重複排除は比較的大きい想定チャンクサイズ例えば64KBで行う。これは、良好なパフォーマンスを確実に行い、各SN上のローカルデータベースのサイズを管理可能な大きさに維持するためである。大きなサイズのチャンクが重複しないと判断されたら、そのサブチャンクについて重複排除を試みる。これらのサブチャンクは、より小さな想定ブロックサイズを用いてCDCアルゴリズムを実行することにより、所定のチャンク内に定義される。例えば、想定チャンクサイズが64KBの場合、想定サブチャンクサイズが8KBだとすると、1つのチャンク内に平均8つのサブチャンクが生成される。サブチャンクはブロックのメタデータをかなり共有しているため、分割されたサブチャンクを有するブロックのメタデータは、各サブチャンクが個別のブロックとして格納される場合よりもはるかに小さい。また、サブチャンクからコンテナチャンクへの変換を含む新たなメタデータは、ブロックのメタデータほど高い復元力は必要ない。これらの変換は、ユーザデータと等しい復元力を伴って維持されれば十分である。これらの変換が消失した場合、考えられる最悪のケースは重複排除効果の低下であるが、その規模は非常に限定的である。その理由は、ユーザデータの復元力のレベルが大規模な障害が引き起こすことはまずないからである。バックアップストリームを書き込む際、関連するサブチャンクからコンテナチャンクへの一連の変換のセットをアクセスノードに作成できるものとする。このセットをサブチャンク重複排除コンテキストと言い、その詳細を以下に説明する。新規の重複しないチャンクの各サブチャンクについて、このアクセスノードに対してローカルなサブチャンク重複排除コンテキスト内の関連する変換を検索する。そのような変換があった場合、ブロックストレージに対して1つまたは複数の重複排除クエリーを発行して、そこにコンテナチャンクがまだ存在し要求されたサブチャンクを含むかどうかを確認する。このステップが必要な理由は、変換が陳腐化したものである可能性があり、ガーベジコレクションによって使用しないサブチャンクが削除される可能性があるからである。ブロックストレージの中に重複排除されるデータがある場合に限り、この変換によって生成されたアドレスでサブチャンクが重複排除される。このプロセスで重複排除されないサブチャンクは、図1に示すように合体されて1つの大きなブロックとして出力される。その場合、個々のサブチャンク変換はコンテキストに追加される。つまり、新規ブロック出力の際には、図1に示すように近接する重複していない新規サブチャンクステータス:Nを合体して、サブチャンクp1とp2を指す2つのポインタを持つ単一のブロック出力となる。なお、ステータス:Nは、重複しているサブチャンクを示している。これについては以下に記載する。サブチャンク重複排除コンテキストサブチャンクを含むバックアップストリームの重複排除を行う際、これまでに生成されたすべてのサブチャンクにアクセスする必要はない。その代わりに、このバックアップの以前のバージョンからのサブチャンクであって、バックアップストリーム内で現在の位置に近接するサブチャンクにアクセスすればよい。この観測を用いることによって、アクセスノード上に、サブチャンク重複排除コンテキストを、そのサブチャンクからコンテナチャンクへの変換を保持するローカルキャッシュとして構築する。この重複排除コンテキストは、バックアップストリームを書き込む際に、いわゆるアンカーの助けを借りてオンザフライで構築される。アンカーとは、特別なタイプのブロックであり、図2に示すように、概念的に関連付けられた次の3つのアイテムを含む。すなわち、1書き込まれるバックアップストリーム内の隣接する大きなチャンクの短いシーケンス1~3であるアンカーシーケンス。2書き込まれるバックアップストリームの実質的な連続部分をカバーするアンカーウィンドウ。これらのウィンドウの大きさは通常数百MBであり、バックアップストリーム全体は非連結アンカーウィンドウでカバーされる。3アンカーウィンドウ内の非重複サブチャンクを含む、サブチャンクからコンテナチャンクへの変換を含むアンカーパック。これらの変換は、出現するすべてのチャンクおよびサブチャンクのバックアップデータを書き込む際に作成される。アンカーシーケンスは、バックアップストリーム内の固定数のチャンクで構成され、以下に定義する特別なハッシュ値は所定数の0の後続ビットを持つ。この特別なハッシュ値は、チャンク1つで構成されるアンカーシーケンスにおける通常のチャンクハッシュ値であり、このハッシュ値は、複数のチャンクで構成されるアンカーの各々のシーケンスチャンクの個々のハッシュ値のハッシュ値として定義される。なお、0である特別なハッシュ値のビット数でアンカーの頻度を制御し、ビットが少なければ少ないほどアンカーの頻度が多くなる。なお、アンカーシーケンスは、上述したようなチャンクで構成されていることに限定されず、他の特徴を有するチャンクにて構成されていてもよい。アンカーウィンドウは、通常、バックアップストリーム内の、このウィンドウに関連付けられたアンカーシーケンスよりもかなり前方にある。その理由は、データの書込みと分割を行う前に必要な変換をフェッチするための十分な時間を確保するためである。新たなバックアップストリームではアンカーがなくなることがあるため、各アンカーは、図2の実線矢印に示すように、ウィンドウ変換へのポインタだけでなく、図2の点線矢印に示すいくつかの後続のウィンドウ用のアンカーパックへのポインタも含んでいる。バックアップを書き込む一方、このアルゴリズムでは、現在のバックアップ用にアンカーを生成するのに加えて、以前に作成されたアンカーが検出されるかどうかを確認する。検出された場合、このアンカーからポインタで指されているすべてのパックは、重複排除コンテキストを構築するローカルキャッシュに読み込まれる。同時に、そのアンカーの新たな値を計算して出力し、古い値と交換する。上述したfingerdiffとは異なり、アンカーは、ブロックストレージにグローバルに格納されているため、この重複排除はストリーム毎ではなくグローバルに行われる。したがって、異なるバックアップサーバまたは異なるクライアント例えば、ワークステーションのバックアップの場合はオペレーティングシステムファイルからのバックアップストリームの類似部分を特定することができる。古いバックアップ内にあるアンカーシーケンスおよび関連付けられたアンカーウィンドウが新たなバックアップに変更されていない場合、新規のアンカーは古いものと同一となり、新規のアンカーは重複排除される。アンカーウィンドウ内のデータが変更されているのにアンカーブロックが修正されていない場合は、新規のアンカーが古いアンカーに上書きされて古いアンカーは回収される。また、定期的に例えば週1回すべてのアンカーを走査して、前回の走査以来、重複排除に全く利用されなかったアンカーを除去する必要がある。ストレージのオーバーヘッドに関しては、アンカーパック全体で、fingerdiffのバックアップ毎のデータベースに匹敵するスペースを占有する。大きな相違点は、アンカーパックは小さいため結合してメインメモリに適合する重複排除コンテキストを構築することができる一方、巨大なバックアップ用のfingerdiffのデータベースは大きくて、メインメモリには適合しない点である。また、fingerdiffの場合、バックアップストリーム同士の関係やストリームの境界を知る必要があるが、アンカー駆動型のアプローチではこれらの知識は必要ない。この新たなアプローチは、バイモーダルアプローチよりも広範囲に渡って重複データを検索することができる。バイモーダルアプローチとは異なり、この新たなアルゴリズムでは、非重複チャンクと重複チャンクの両方でこれまでに出現したサブチャンクを用いて重複排除のためのチェックを行う。これは、サブチャンク変換コンテキストにこれらのすべての変換が含まれるからである。バイモーダルアプローチでは、書き込まれるストリームの、少なくとも1つの重複チャンクに隣接する非重複チャンクのサブチャンクしかチェックしない。[詳細および改良点]基本システムでは、チャンク全体が圧縮されて冗長符号化される。サブチャンク重複排除では、個々のサブチャンクを読み出すことが可能でなければならない。そのためには、コンテナブロック全体を読み出して所望するサブチャンクを抽出すればよい。しかし、これはあまり効率的ではないため、個々のサブチャンクを圧縮して冗長符号化することを提案する。その結果、新たなフラグメントには、あるチャンクのすべてのサブチャンクのフラグメントが含まれる。そしてブロックメタデータを拡張し、チャンクフラグメント内のすべてのサブチャンクのフラグメントのオフセットを記憶する。バックアップ削除後は、死んで除去が必要となるサブチャンクと、生きていて保存が必要なサブチャンクが発生する。そのため、死んだチャンクを特定してそのスペースを再利用するためにガーベジコレクションのアルゴリズムを変える必要がある。スペース再利用後にチャンク内サブチャンクの位置検索を促進するためには、どのオリジナルチャンクがまだ存在しているのかを示す各ブロックメタデータを有するビットベクトルを維持する必要がある。また、各サブチャンクは、サブチャンクの回収を可能にするために小さな参照カウンタ数ビットを取得する必要がある。このカウンタは小さくてよい。なぜなら、オーバーフローするという稀なケースでは、ブロック全体が回収されるまでサブチャンクは回収されないからである。サブチャンクに基づく重複排除を可能にするために、サブチャンクセレクタでアドレスフォーマットを拡張する。サブチャンクセレクタは、様々な形式のものを使用することができる。一例として、単なるサブチャンクの順番がある。例えば、1つのチャンクに平均8つのサブチャンクがある場合、アドレスを4ビット拡張すれば、チャンク全体と15個までの個々のサブチャンクに対応することができる。可能な改良点の一例として、隣接するサブチャンクの合体がある。これは、大きなチャンクでは重複排除ができないが、複数の隣接するサブチャンクでは重複排除ができる場合に行う。これは変換のみに基づいて決定することができ、バックエンドへのクエリーを追加する必要はない。この場合、複数のサブチャンクを含む範囲に対してポインタを1つだけ生成する。これを可能にするためには、サブチャンクセレクタをサブチャンク範囲セレクタに変更する。サブチャンク範囲セレクタは2つのサブチャンクの番号を含み、上記の例ではアドレスを4ビットではなく1バイト拡張する。[評価]ここでは、以下に記載する3つのデータ群を用いて、本願で提案するサブチャンクアルゴリズム以下サブチャンクと言うを、上述したCDCおよびバイモーダル手法と対比させて評価する。実際のバックアップデータ上で直接動作させると非常に長い時間がかかるため、非特許文献10に記載されている特別なチャンク分割ツールを用いて、圧縮バックアップトレースを生成した。このツールは潜在的なすべての分割ポイントと、その間のデータチャンクのハッシュ値を排除する。このような前処理によって、テストデータのサイズと評価時間が大幅に削減される。平均すると20分未満で60GBのトレースを処理することができる。これは実際のデータでは1TBに相当する。あるデータ群とあるアルゴリズムについて、システムに格納されている全データのサイズを必要な全ディスクスペースで割った値を重複排除率DER:DuplicationEliminationRatioと定義する。DERはメタデータの有無にかかわらず計算できる。メタデータを含まないものをデータのみのDERと言い、メタデータを含むものを実DERという。データのみのDERは簡易で十分に定義されている。実DERとは異なり、実際のストレージシステムの特徴に依存しない。一方、実DERの計算では、実際のシステムで必要なストレージに影響を与える、あらゆる要因が考慮される。これには、データ冗長性レベル、圧縮率、およびあらゆる種類のメタデータに必要なスペース等がある。実DERの値は、実際のシステムモデルに大きく依存する。本願におけるモデルのメタデータのオーバーヘッドについては後述する。[テストデータ]図3に示す3つのデータ群に基づいて実験を行った。Wikiデータ群は、英語版ウィキペディアの5つの正式なXMLスナップショットで構成される。ファイルには通常のページの最新バージョンしか含まれず、変更履歴、特別ページ、画像などは含まれない。スナップショットが作成されるのは稀で、平均月1回である。バックアップの間隔が長く、バックアップ数が少ないこと、またwikiデータの特徴細かく頻繁に変更があるにより、このデータ群について測定される重複排除率は非常に低い。実DERは、選択するアルゴリズムによって1.06~1.52となる。2つ目のデータ群であるneclabは一般的なバックアップデータを表している。これは、非特許文献10で使用したものと同じデータ群であり、14個のユーザディレクトリのウィークリーNetwareバックアップで構成される。このデータ群について実際に測定されたDERは、3.16~3.76である。3つ目のデータ群であるmailは、9LivesDataでの52人のコンサルタントのメールボックスの、32個のデイリースナップショットで構成される。これは非常に限定されたデータ群である。一般的なユーザのメールボックスは日々それほど変化があるわけではないため、このデータ群に関して測定される重複排除は非常に高いと思われるバックアップ数に近い。しかし、ユーザのメールボックスの1つのスナップショットは、通常数千もの非常に小さなファイル1ファイル1メッセージを含むtarアーカイブとして保存されている。tarアーカイブ内でのこれらのファイルの順序はtarおよびファイルシステム内部の状態によって決まり、時々わずかに変化する。想定チャンクサイズが複数のファイルを含む場合は、その順序がわずかに置換しただけでも多くの重複排除アルゴリズムに悪影響を及ぼす可能性がある。さらに、データの順序が変わるとデータのフラグメント化が非常に高くなる可能性がある。このデータ群について実際に測定されたDERは13.08~18.37である。さらに、この3つのデータ群を連結して、人為的なデータ群である合計データを生成した。このデータ群の実DERは4.35~5.19である。[テストを行ったポリシ]全てのアルゴリズムについて、考えられる様々な構成でテストを行った。最初のアルゴリズムであるCDCについては、4KBから256KBまでのすべての2の乗数に設定された想定チャンクサイズでテストを行った。予想通り、CDCでは想定チャンクサイズ付近のサイズのチャンクが生成された。上述したバイモーダルでは、大きなチャンクは想定サイズ8KBから256KBのものを、小さなチャンクは常にその8分の1のサイズのものを使用した。本願で提案するアンカー駆動型の重複排除は、8KBから256KBまでのすべての2の乗数に設定された想定チャンクサイズで構成され、小さなチャンクの想定サイズは常に8分の1である。アンカー長は1チャンクに設定され、アンカーレベルは10に設定された。つまり、アンカー間の平均距離は、210=1024チャンクまたは8192の小さなチャンクとなる。キャッシュサイズは0.5mlnエントリ約64パックからの変換を格納可能、プリフェッチは16パック実際のデータストリーム1GBに相当に設定された。このような構成により、このアルゴリズムによって達成されるDERと実行に必要なリソースとの間で合理的なバランスを取ることができる。完全キャッシュと言われるアルゴリズムは、サブチャンクアルゴリズムと類似しているが、アンカーに基づくメカニズムを使用するのではなく現れるすべての変換を直接キャッシュに入れるものであり、この場合、現れる変換は無限である。このアルゴリズムは現実的ではないが、これによる重複排除はサブチャンクのアプローチにとっては最大限のものである。[データのみのDERを用いた比較]図4は、平均ブロックサイズに対するデータのみのDERを示す。これは3つのデータ群とすべてのアルゴリズムに関するものである。各グラフは個別のデータ群を表し、各曲線は個別のアルゴリズム、各点は個別の構成異なる想定チャンクサイズを表している。これらの表示は、望ましい重複排除アルゴリズムは高いDERを達成できるだけでなく大きな平均ブロックサイズが維持できるべきであるとの考えに基づくものである。これは、メタデータのオーバーヘッドとパフォーマンスのオーバーヘッドを許容されるレベルに維持するために必要である。平均ブロックサイズとは、システム内に格納されるすべてのユニークなブロックのサイズの合計を、ブロック数で割った値である多くのバックアップストリームに単一のブロックがある場合でも1つとかぞえる。これは後に詳細に説明する平均チャンクサイズとは異なる統計値である。当然ながら、メタデータが含まれない場合はブロックサイズが小さいほど重複排除がよく機能する。ほとんどの場合、データのみのDERは平均ブロックサイズに対してほぼ直線となる。本願で提案するアルゴリズムのパフォーマンスは、いかなるデータ群に関してもCDCやバイモーダルよりも良い。大きな平均ブロックサイズを維持しつつ、より小さなサブチャンクレベルで重複排除を行うため、DERが高くなる。完全キャッシュアルゴリズムの場合、これははっきりと示される。XKBのチャンクを用いてCDCで達成される重複排除は、XKBのサブチャンクを用いて完全キャッシュアルゴリズムで達成される重複排除とほぼ等しい。この関係は、完全キャッシュアルゴリズムで用いる想定チャンクサイズにかかわらず成り立ち、想定サブチャンクのサイズのみの問題である。しかし、完全キャッシュアルゴリズムは、すべてのサブチャンクについての膨大なインデックスを維持する必要がある。それには多くのリソースが必要であるため、簡単には実装できない。本願で提案するアルゴリズムで達成されるDERは、プリフェッチ変換に使用するアンカーに基づくメカニズムのパフォーマンスに大きく依存する。アンカーがよく機能すればするほど重複排除も高くなる。以上のように、アンカーに基づくサブチャンク重複排除は完全キャッシュアルゴリズムとかなり類似するが、プリフェッチ変換に関して、アンカーに基づくメカニズムは適切に機能することがわかる。アンカーに基づくメカニズムで発見された重複サブチャンク数を、完全キャッシュアルゴリズムで発見された重複サブチャンク数で割った値を、キャッシュヒット率と定義する。確かに、基本構成64KBのチャンクと8KBのサブチャンクでは、キャッシュヒット率は非常に高いwikiデータ群では81、neclabでは87、mailでは99。neclabデータについては、予想通りCDCよりもバイモーダルの方がよく機能する。これは非特許文献10で使用されたデータ群であり、我々の実験結果はこれと一致する。驚いたことに、他のデータ群に関しては、バイモーダルで達成されたDERはCDCで達成されたDERよりもわずかに低い。これは、ランダムな場所で数多くの小さな変化がある場合に見られる。大きなチャンクは、重複チャンクと隣接する場合にのみ小さなチャンクに再分割される。あるブロックが、1つのバックアップ内でチャンクに分割され次のバックアップストリームで変更がない場合、このブロックは、重複排除される機会を失わないように毎回再分割されなければならない。このような状況は、neclabのトレースではあまり発生しないが、wikiとmailではよく発生する。そのため、バイモーダルのパフォーマンスは少し低かった。[実DERを用いた比較]あらゆる種類のメタデータが含まれる場合、状況は著しく異なる。上記で説明したシステムモデルでは、各ブロックは冗長符号化され、12個のフラグメントとして格納される。ほとんどのデータは、オリジナルのフラグメントが9個で、冗長フラグメントが3個であるが、ポインタ付きのブロックは12個のコピーに保存される。圧縮レベルはブロックサイズの対数の線形関数としてグローバルに予測される64KBのブロックについては約0.77、8KBのブロックについては約0.80。格納される各ブロックは、それに関連付けられる124バイトのメタデータを含む。高いパフォーマンスと障害からの復元力を持つために、メタデータはすべて12個のコピーに格納されるため、メタデータのオーバーヘッドは1ブロック当たり1344バイトとなる。実際のシステムでは、ポインタ付きのブロックも重複排除されるため、特に小さなブロックではメタデータのオーバーヘッドは少なくなるが、このモデルでは、ポインタ付きブロックは重複排除されないという最悪のシナリオのみをエミュレートする。そのため、バックアップストリーム内の各チャンクにはポインタがなければならないこのチャンクが重複しているかどうかは関係ない。また、すべてのポインタも12個のコピーに格納される。サブチャンクアルゴリズムでは、変換パックを格納するための追加のスペースが必要である。1つの変換は、サブチャンク20バイト長のSHA-1、インデックス、およびチャンク全体のSHA-1を含む。チャンク全体のSHA-1は通常、いくつかの変換で共有されるため、1つの変換は容易に32バイトにおさまる。変換パックは低い復元力で格納することができる。データが消失した場合、DERはチャンク全体のCDCのレベルまでわずかに低下するが、システムは完全に機能する。したがって、本願における実験では、アンカーパックの復元力はユーザデータの復元力と同じであると仮定した。図5は、システム内に格納された平均ブロックサイズに対する実DERを示す。DERの計算にすべての種類のメタデータが含まれる場合、ブロックサイズが小さくなると、ある時点までは重複排除率が高くなるが、その後はメタデータの格納に必要なスペースが、重複排除によって得られるスペースを上回る。各データ群および各アルゴリズムについて、実DERが最も高くなると思われる最適なブロックサイズがある。任意のアルゴリズムメタデータのオーバーヘッドを低下させていないもの。通常これは簡単な作業ではないでは、より良いDERを得ることはできない。当然、最適なブロックサイズは選択するデータ群によって大きく異なる。様々なデータ群について異なる想定チャンクサイズを使用するには、追加の手動構成が必要となり、グローバルな重複排除が損なわれる恐れがある。その理由は、異なる分割ポリシでチャンクに分割されている2つのストリーム間では重複を発見できないからである。CDCでは、最適な想定チャンクサイズは、wikiについては8KBDER=1.20、neclabについては16KBDER=3.18、mailについては32KBDER-14.89である。これらの全データ群における平均チャンクサイズとしては、16KBが合理的な選択であろう。人為的な合計データ群ではDER=4.39である。バイモーダルは、neclabのデータ群に関しては良好なパフォーマンスを見せた。32KBの大きなチャンクと4KBの小さなチャンクについて、DERは3.38であったCDCより6改善された。しかし、wiki32KBの大きなチャンクではDER=1.07とmail64KBの大きなチャンクではDER=13.14では、悪かった。合計データ群では、大きなチャンクの想定サイズを32KBにするのが最善の選択である。本願で提案するサブチャンクアルゴリズムでは、著しく高いパフォーマンスが達成された。wikiデータ群の場合、最適な平均ブロックサイズは16KBで、DER=1.50となり、最適なCDCよりも25改善した。neclabデータ群については、最適な平均ブロックサイズは32KBで、DER=3.67となり、CDCよりも15改善した。また、mailデータ群についても、最適なサブチャンクアルゴリズムは64KBのブロックを使用してDER=18.45であり、最適なCDCよりも24改善した。合計データ群については、想定ブロックサイズが64KBの場合に最も良いパフォーマンスとなったDER=5.06、CDCより15改善。チャンクのサイズを非常に小さくすると、サブチャンクアルゴリズムのパフォーマンスは低下してCDCに近くなり、mailのトレースではCDCよりも低くなった。その理由は、小さなチャンク例えば8KBではサブチャンクが非常に小さくなる例えば1KBため、平均ブロックサイズが非常に短くなりメタデータが膨大になるからである。[読出し性能]バックアップデータの重複排除を行うと、連続するストリームではなく、データが多数の小さなチャンクとしてシステム全体に散らばって格納される場合がある。このようなフラグメント化された状態では、読み出す際のディスク動作検索が多くなる。一般的に、拡張性の高いストレージシステムは多数のリソースを保有しており、ディスクの検索が増えてもパフォーマンスに悪影響を与えることはない。特に、同時に1つまたはわずかなストリームを読み出すのであれば問題ない。しかし、重複アルゴリズムを設計する際には、そのアルゴリズムがデータのフラグメント化に与える影響を評価する必要がある。データのフラグメント化は広範囲に及ぶ主題であり、そのほとんどは本願の対象外であるが、本願が提案するアルゴリズムが他のアルゴリズムよりもフラグメント化に関して悪い結果をもたらすものではないことを示すために、基本的な評価の結果を提供する。ディスク読出し性能を評価するために、ストレージシステムのモデルを簡略化し、すべてのブロックが単一の物理的ディスクに位置する1つの連続ファイルに格納されていると仮定している。新規の重複しないブロックはすべてファイルの最後に書き込み、重複するブロックは単純にスキップする。このモデルではメタデータを格納することは考えない。本願では読出しを以下のようにシミュレートした。すなわち、ブロックは、バックアップストリームに現れる順序で一つずつ要求される。ブロックがディスクからフェッチされると、読出し動作を拡張して後続する複数のブロックも読み出す。1回の想定読出しサイズは256KBである。この制限に適合するブロックはすべて読出しキャッシュにロードされ、次のブロックは、その半分がこの制限に適合する場合に限りロードされる少し変だが、この条件はプリフェッチされたブロックが切り捨てられる問題を防ぐことができる。キャッシュのサイズは1GBに制限される。ブロックがすでにキャッシュ内にある場合は、追加のIO動作を行う必要はない。前回の最もフラグメント化されたバックアップの読出しに必要なIO動作の総数を、フラグメント化の一つの指標として使用する。サブチャンクアルゴリズムの場合、このモデルは多少異なる。同じ戦略に従って行うが、大きなブロックではなくサブチャンクを使用して実行する。その理由は、ブロック表示が変更されているおかげで個々のサブチャンクを読み出すことができるからである。すべてのアルゴリズムを比較するために、実DERに関する最適な設定を選択したサブチャンクアルゴリズムでは大きなチャンクが64KBで小さなチャンクが8KB,バイモーダルでは32KBと4KB、CDCでは16KB。図6は、前回の最もフラグメント化されたバックアップの読出しに必要なディスク動作数に対する、各アルゴリズムの実DERを示す。結果はデータ群によって大きく異なる。neclabについては、サブチャンクアルゴリズムはフラグメント化が最も低く実DERが最も高い、最高の結果が出た。このトレースは一般的なバックアップデータを反映しているため、これは良い結果である。一般的に、重複排除とフラグメント化はトレードオフの関係にある。重複排除率が高ければフラグメントが多くなるのだが、例外があることがわかった。mailとwikiのトレースについては、サブチャンクアルゴリズムでのフラグメント化は常に他の2つのアルゴリズムでのフラグメント化の中間であるが、実DERは常に最も高い。これらのトレースについては、フラグメント化を犠牲にして重複排除が改善されている。読出し性能に影響を与える可能性がある別の要因は、システム内に格納されている全データストリームの合計サイズをポインタの総数で割った、平均チャンクサイズである。平均チャンクサイズの計算では、平均ブロックの計算とは異なり、重複が複数回数えられる。平均チャンクが短いということは、同量のデータに対して、より多くの数のポインタを格納し処理する必要があることを意味する。図7は、各アルゴリズムにおける最適な例について、およびバイモーダルについてはさらに64KBの大きなチャンクについての、平均ブロックサイズを表し、図8は、その平均チャンクサイズを表している。この例はバイモーダルが効果的であることを示している。その理由は、64KBの大きなチャンクでのバイモーダルは、最適なバイモーダルよりもわずかしか重複排除率が下がらないが、平均ブロックサイズと平均チャンクサイズが著しく大きくなるからである。しかし、重複排除率が最も高いサブチャンクの例が、ほとんどのケースで64KBのチャンクのバイモーダルよりも大きい平均ブロックサイズおよび平均チャンクサイズを示している。サブチャンクアルゴリズムでは、デフォルトで大きなチャンクを出力するようにし、そのチャンクの残りが重複排除された場合にのみ、大きなチャンクよりも少ないデータ量を含むブロックを生成する。バイモーダルは、最初の効果についてはサブチャンクアルゴリズムと同様だが、バイモーダルは後で重複排除を行う際に使用することを期待して変化の境界線に小さなブロックを出力するため、2つ目の効果は得られない。しかし、このような予想が実現するとは限らない。その結果、サブチャンクアルゴリズムでは、CDCやバイモーダルで生成されるものよりもはるかに大きな平均サイズのブロックが生成される。また、サブチャンクを指すポインタがあるため、他の2つのアルゴリズムと比べて、サブチャンクアルゴリズムの場合は平均ブロックサイズと平均チャンクサイズと間に大きな差がある。[構成の調整]ここでは、サブチャンクアルゴリズムの基本構成上記で説明した想定チャンクサイズ64KBからパラメータを1つ変更することによって、実DERにどのような影響を与えるのかについて説明する。プロットを簡略化するために、合計のデータ群についてのみ述べる。通常、各データ群に関する結果もほぼ同じである。その結果を、図9の実DERと様々なパラメータの関係に示す。最初に調整するパラメータはアンカー長、つまりアンカーを構成する連続するチャンクの数である。驚くことに、単一のチャンクから作成されたアンカーが最も良い結果となった。その理由は、実DERは使用するチャンク数の対数に対して線形に低下するためである。アンカーが短いほど、その後のバックアップで変化がないことが多い。これは、適切な変換パックをダウンロードするのに必要である。次に調整するパラメータはアンカーレベルである。アンカーレベルがnに等しいとは、アンカー間の想定距離が2nチャンクに等しいことを意味する。アンカーレベルを変更すると、常に実データ1GBに相当する変換をプリフェッチするよう、プリフェッチするパック数も調整される。アンカーを数多く設定すると重複排除の性能も高くなるが、各アンカーが読出しおよび書込み動作を生成するため、アンカーが多すぎると性能が低下する。我々はアンカーレベル10を使用することに決定した。その結果、アンカー間の想定距離は64KBのブロックに対して64MBとなった。また、プリフェッチするパック数も修正した。一般的に、プリフェッチの長さを長くすると重複排除の性能が高まる。最高値の突然の低下は、変換キャッシュプルーニングpruningによってもたらされる。このキャッシュはキューとして機能し、プリフェッチのサイズが大きいと、必要な変換が使用前にキャッシュから除外される。このような場合は、キャッシュサイズを大きくすればよいと思われるため、より大きなキャッシュで実験をしたが、結果はそれほど改善されたわけではなく、妥当なサイズとして1GBのプリフェッチを維持した。さらに、他の想定サイズのサブチャンクでも実験を行ったが、それほど大きな改善は見られなかった。構成の調整の他に、このアルゴリズムにいくつか修正を加えてテストを行った。最初のテストは、余剰ブロック重複しないサブチャンクで構成されるブロックの合体である。各チャンクごとに1つの余剰ブロックを出力するのではなく、いくつかを合わせて単一のブロックを出力することができる。このような修正はDERに影響を与えることはほとんどない。その理由は、余剰ブロックは非常に稀で重複することはまずないからである。しかし、大きな平均ブロックサイズを維持することができる。もう1つのテストは、1つのチャンク内のサブチャンク数を制限することである。デフォルトのチャンク分割構成では最大サブチャンク数は24だが、想定サブチャンク数は8である。我々のシステムが一定サイズのメタデータ記録を必要とする場合、これはスペースの無駄になる。実際にサブチャンクがあるかどうかにかかわらず、各サブチャンク用に約3Bを取っておく必要があるからだ。しかし、ある限度を超えるすべてのサブチャンクを合体させることができる。実験により、サブチャンク数を12に制限すると重複排除にわずかな影響が出る合計データ群で、データのみのDERが6.01から5.95に低下が、16に制限すると全く影響がないデータのみのDERの低下は0.01未満ことがわかった。[関連技術]前述のfingerdiffとバイモーダルのチャンク分割に加えて、重複排除全般、特にチャンク分割に関連する様々な論文がある。Extremebinning非特許文献5は、単一サイズのチャンク分割を用いて類似するファイル内の重複を探し出す、効果的で拡張性のある技術である。しかし、この技術は代表チャンクを計算するためにファイルコンテンツ全体の知識を必要とするため、ストリーミングデータに直接適用することはできない。Sparseindex非特許文献13はextremebinningと類似しており、入力チャンクをセグメントに分割して選択されたセグメントチャンクに対して重複排除を行うことにより、ストリーミングデータに適用される。これは、複数のレベルのチャンク分割を用いてより粒度の細かい重複検出を行う技術は採用していない。Adaptivechuncking方式非特許文献12は、可動装置での必要な処理能力を最小限に抑えるためにCDCと固定サイズチャンク分割とを切り替える、興味深いアイデアである。EMCCentera非特許文献1はコンテンツアドレスを重複排除に利用できることを初めて証明した製品の1つである。しかし、すべてのファイルについてコンテンツアドレスを計算するので、サブファイルの重複排除を行うことはできない。Venti非特許文献21はアーカイバルファイルシステムにおける重複排除用のCASを初期に採用したものである。固定サイズのブロックを使用するため、シフトされたコンテンツの重複排除を行うことはできない。MAD2非特許文献26、HYDRAstor非特許文献9、およびDDFS非特許文献28は、CDCチャンク分割とコンテンツアドレスストレージを使用する、実装されているシステムの例である。Foundation非特許文献23は、コンテンツアドレスストレージを用いて、夜間のスナップショットにおけるハードディスク全体のバージョンを効果的に格納し重複排除を行う。REBL非特許文献11は、コンテンツ指定チャンク分割を用いる重複排除とデルタ符号化および圧縮を組み合わせて、実現しうる最高の圧縮率を得る。Pastiche非特許文献8は、コンテンツ指定チャンク分割、コンテンツアドレス、およびコンテンツに基づく暗号化を用いて、ピアツーピアpeertopeerネットワークにおけるクライアントシステムのバックアップの安全性を確保する一方、共有チャンクを検出して各チャンクにつき1つのコピーのみを格納することでストレージのオーバーヘッドを制限する。CZIP非特許文献18は、チャンク分割と汎用のCASを用いる一般的な圧縮ファイルフォーマットであり、例えば、コンテンツ分配サーザ、ファイル転送、またはウェブキャッシングに利用される。非特許文献24に記載されるネットワークトラフィック冗長性排除スキームは、Rabinのフィンガープリントの代表的なセットを使用してネットワーク通信における重複の可能性があるコンテンツの領域を検索する。これは、この論文に記載したアンカーと類似するところがある。LBFS非特許文献16は、ネットワークのリンク上での帯域幅の使用に制限を加えるために、コンテンツ指定チャンク分割とコンテンツ検証をネットワークファイルシステムに適用する例を示している。Rabinのフィンガープリントを使用してファイルをチャンクに分割し、その結果得られるRabinのハッシュによって重複の可能性があるものを検索する一方、SHA-1を用いてチャンクが本当に同じコンテンツかどうか、最終確認を行う。CASPER非特許文献25は、CASデータが入手可能な場合に低速リンクでのファイルシステムアクセスを高速化するためにCASを便宜的に利用する例を示している。RedFS分散型ファイルシステム非特許文献4は、ファイルグループに対する局所的重複排除と、レプリカと言われるグループのベクトルに基づく類似するファイルグループの検索とを組み合わせて、分散されたレプリカ間でのデータ転送を最小限にする。ProtecTierシステム非特許文献2は、代表的なRabinのフィンガープリントを採用し、大きなブロックのデータに対してコンテンツアドレスではなく類似性マッチングを用いて重複排除を行う。これにより、重複排除用の非常に小さなインデックスを格納することができる。コンテンツポインタを合体させる思想は、部分コンテンツ共有ファイルシステムの実装に関する技術で提案されている非特許文献3。この技術では、チャンクのメタデータのオーバーヘッドを最小限にするために、類似性検出に基づくオフライン重複排除を用いて、ファイルの共有部分に対してのみチャンク分割と重複排除を行う。非特許文献15と非特許文献19は、実在のデータに対するCDCおよび他の技術を用いた重複排除での可能なゲインの分析について記載している。文献14は、様々な重複排除技術に関する賛否を包括的に比較し、重複排除率、メタデータのオーバーヘッド、および再構築時間のトレードオフについて述べている。DeepStore非特許文献27は、重複排除におけるCASとデルタ圧縮の効果を比較し、重複排除されたデータの信頼性について述べている。非特許文献6では、重複排除を行った結果として、より少数のデータのチャンクを格納することに対する信頼性についても分析している。非特許文献17は、複数の種類のデータ間の共通性を探す上でのチャンクサイズの効果、メタデータのオーバーヘッドがスペースの節約に与える影響、およびCASストレージに1回しかチャンクを格納しないことによる回復力の低下、について述べている。[結論と今後の研究]本願では、動的にプリフェッチされる限られたサイズのサブチャンク重複排除コンテキストによって駆動されるサブチャンク重複排除アルゴリズムを提案した。このコンテキストは、サブチャンクレベルでの効果的な重複排除に必要なほとんどの変換を提供する。さらに、コンテキスト入力変換は、あまり重要でないメタデータとして、つまり復元力の低いオーバーヘッドとして、格納することができる。また、この新たなアルゴリズムは、可能な場合はすべてのチャンクを使用することによって有効なメタデータのオーバーヘッドを削減し、同じチャンクに属するサブチャンク間でほとんどのメタデータを共有する。その結果、多量のメタデータのオーバーヘッドを含むシステムでは、サブチャンクアルゴリズムは従来のCDCまたはバイモーダル等の他のアプローチと比べて実DERが優れており、また平均ブロックサイズおよびチャンクサイズが非常に大きい。同時に、標準的なバックアップトレースについては、この新たなアルゴリズムはフラグメント化が少ない。それ以外のデータストリームについては、フラグメントが多くなる場合もあるが、これは重複排除率を改善するためのコストである。今後は、より多くのバックアップトレースを使用してこの新たなアルゴリズムを評価し、また重複排除率を著しく低下させることなくフラグメント化の問題に対処する方法を詳細に研究することを計画している。<実施形態2>本発明の第2の実施形態を、図10乃至図18を参照して説明する。図10は、システム全体の構成を示すブロック図である。図11は、ストレージシステムの概略を示すブロック図であり、図12は、構成を示す機能ブロック図である。図13乃至図18は、ストレージシステムの動作を説明するための説明図である。ここで、本実施形態では、ストレージシステムが、複数台のサーバコンピュータが接続されて構成されている場合を説明する。但し、本発明におけるストレージシステムは、複数台のコンピュータにて構成されることに限定されず、1台のコンピュータで構成されていてもよい。図10に示すように、本発明におけるストレージシステム10は、ネットワークNを介してバックアップ処理を制御するバックアップシステム11に接続している。そして、バックアップシステム11は、ネットワークNを介して接続されたバックアップ対象装置12に格納されているバックアップ対象データ記憶対象データを取得し、ストレージシステム10に対して記憶するよう要求する。これにより、ストレージシステム10は、記憶要求されたバックアップ対象データをバックアップ用に記憶する。なお、ストレージシステム10は、必ずしもバックアップ対象データを記憶することに限定されず、いかなるデータを記憶してもよい。そして、図11に示すように、本実施形態におけるストレージシステム10は、複数のサーバコンピュータが接続された構成を採っている。具体的に、ストレージシステム10は、ストレージシステム10自体における記憶再生動作を制御するサーバコンピュータであるアクセラレータノード10Aと、データを格納する記憶装置を備えたサーバコンピュータであるストレージノード10Bと、を備えている。なお、アクセラレータノード10Aの数とストレージノード10Bの数は、図11に示したものに限定されず、さらに多くの各ノード10A,10Bが接続されて構成されていてもよい。さらに、本実施形態におけるストレージシステム10は、データを分割及び冗長化し、分散して複数の記憶装置に記憶すると共に、記憶するデータの内容に応じて設定される固有のコンテンツアドレスによって、当該データを格納した格納位置を特定するコンテンツアドレスストレージシステムである。このコンテンツアドレスストレージシステムについては、後に詳述する。なお、以下では、ストレージシステム10が1つのシステムであるとして、当該ストレージシステム10が備えている構成及び機能を説明する。つまり、以下に説明するストレージシステム10が有する構成及び機能は、アクセラレータノード10Aあるいはストレージノード10Bのいずれに備えられていてもよい。なお、ストレージシステム10は、図11に示すように、必ずしもアクセラレータノード10Aとストレージノード10Bとを備えていることに限定されず、いかなる構成であってもよく、例えば、1台のコンピュータにて構成されていてもよい。さらには、ストレージシステム10は、コンテンツアドレスストレージシステムであることにも限定されない。図12に、ストレージシステム10の構成を示す。この図に示すように、ストレージシステム10は、データを記憶する記憶装置31,32と、当該記憶装置31,32に対するデータの記憶及び読み出し動作を制御する制御装置20と、を備えている。そして、制御装置20は、記憶対象データとなるストリームデータをブロックデータ単位で記憶再生するブロックデータ処理部21と、上記ブロックデータをさらに複数に分割したサブブロックデータ単位で記憶再生するサブブロックデータ処理部22と、を備えている。また、記憶装置31,32として、ブロックデータやサブブロックデータを記憶するハードディスクドライブなどの補助記憶装置31と、後述するサブアドレスデータを記憶する主記憶装置32と、を備えている。なお、ここでは、記憶するデータに応じて格納先となる記憶装置を分けて記載しているが、いかなる記憶装置であってもよく、同じ記憶装置であってもよい。なお、実際には、上記ブロックデータ処理部21とサブブロックデータ処理部22とは、図11に示したアクセラレータノード10A及びストレージノード10Bが備えているCPUCentralProcessingUnitなどの複数の演算装置にプログラムが組み込まれることで構成されている。また、補助記憶装置31は、主に図11に示したストレージノード10Bが備えている補助記憶装置にて構成されており、主記憶装置32は、主に図11に示したアクセラレータノード10A及びストレージノード10Bが備えている主記憶装置にて構成されている。なお、上記プログラムは、例えば、CD-ROMなどの記憶媒体に格納された状態でストレージシステム10に提供される。あるいは、上記プログラムは、ネットワーク上の他のサーバコンピュータの記憶装置に記憶され、当該他のサーバコンピュータからネットワークを介してストレージシステム10に提供されてもよい。以下、上記ブロックデータ処理部21と上記サブブロックデータ処理部22の構成について詳述する。はじめに、ブロックデータ処理部21ブロックデータ重複排除部によるコンテンツアドレス方式のブロックデータ単位におけるストリームデータの記憶及び読み出し方法を、図13乃至図15を参照して説明する。まず、ブロックデータ処理部21は、図14の矢印Y1に示すように、ストリームデータであるバックアップ対象データAの入力を受けると、図13及び図14の矢印Y2に示すように、当該バックアップ対象データAを、可変容量例えば、平均64KBあるいは所定容量例えば、64KBのブロックデータDに分割する。そして、このブロックデータDのデータ内容に基づいて、当該データ内容を代表する固有のハッシュ値H内容識別情報を算出する矢印Y3。例えば、ハッシュ値Hは、予め設定されたハッシュ関数を用いて、ブロックデータDのデータ内容から算出する。なお、ブロックデータ処理部21による処理は、アクセラレータノード10Aにて実行される。そして、上記ブロックデータ処理部21は、バックアップ対象データAのブロックデータDのハッシュ値Hを用いて、当該ブロックデータDが既に記憶装置31に格納されているか否かを調べる。具体的には、まず、既に格納されているブロックデータDは、そのハッシュ値Hと格納位置を表すコンテンツアドレスCAが、関連付けてMFIMainFragmentIndexファイルに登録されている。従って、ブロックデータ処理部21は、格納前に算出したブロックデータDのハッシュ値HがMFIファイル内に存在している場合には、既に同一内容のブロックデータDが格納されていると判断できる図14の矢印Y4。この場合には、格納前のブロックデータDのハッシュ値Hと一致したMFI内のハッシュ値Hに関連付けられているコンテンツアドレスCAを、当該MFIファイルから取得する。そして、このコンテンツアドレスCAアドレスデータを、記憶要求にかかるブロックデータDのコンテンツアドレスCAとして記憶する。あるいは、既に格納されているブロックデータDを参照するコンテンツアドレスCAをさらに参照する他のアドレスデータをツリー構造にて記憶する。これにより、このコンテンツアドレスCAにて参照される既に格納されているデータが、記憶要求されたブロックデータDとして使用されることとなり、当該記憶要求にかかるブロックデータDは記憶する必要がなくなる。また、ブロックデータ処理部21は、は、上述したように重複チェック部23にてまだ記憶されていないと判断されたブロックデータDを圧縮して、図14の矢印Y5に示すように、複数の所定の容量のフラグメントデータに分割する。例えば、図13の符号D1~D9に示すように、9つのフラグメントデータ分割データ41に分割する。さらに、ブロックデータ処理部21は、分割したフラグメントデータのうちいくつかが欠けた場合であっても、元となるブロックデータを復元可能なよう冗長データを生成し、上記分割したフラグメントデータ41に追加する。例えば、図13の符号D10~D12に示すように、3つのフラグメントデータ冗長データ42を追加する。これにより、9つの分割データ41と、3つの冗長データとにより構成される12個のフラグメントデータからなるデータセット40を生成する。なお、上記ブロックデータ処理部21による処理は、1つのストレージノード10Bによって実行される。そして、ブロックデータ処理部21は、上記フラグメント生成部24にて生成されたデータセットを構成する各フラグメントデータを、記憶装置31に形成された各記憶領域に、それぞれ分散して格納する。例えば、図13に示すように、12個のフラグメントデータD1~D12を生成した場合には、12個の記憶装置31内にそれぞれ形成したデータ格納ファイルF1~F12データ格納領域に、各フラグメントデータD1~D12を1つずつそれぞれ格納する図14の矢印Y6参照。また、ブロックデータ処理部21は、上述したように記憶装置31に格納したフラグメントデータD1~D12の格納位置、つまり、当該フラグメントデータD1~D12にて復元されるブロックデータDの格納位置を表す、コンテンツアドレスCAを生成して管理する。具体的には、格納したブロックデータDの内容に基づいて算出したハッシュ値Hの一部ショートハッシュ例えば、ハッシュ値Hの先頭8Bバイトと、論理格納位置を表す情報と、を組み合わせて、コンテンツアドレスCAを生成する。そして、このコンテンツアドレスCAを、ストレージシステム10内のファイルシステム、つまり、アクセラレータノード10Aに返却する図14の矢印Y7。すると、アクセラレータノード10Aは、バックアップ対象データのファイル名などの識別情報と、コンテンツアドレスCAとを関連付けてファイルシステムで管理する。また、ブロックデータ処理部21は、ブロックデータDのコンテンツアドレスCAと、当該ブロックデータDのハッシュ値Hと、を関連付けて、各ストレージノード10BがMFIファイルにて管理する。このように、上記コンテンツアドレスCAは、ファイルを特定する情報やハッシュ値Hなどと関連付けられて、アクセラレータノード10Aやストレージノード10Bの記憶装置31に格納される。さらに、ブロックデータ処理部21は、上述したように格納したバックアップ対象データを読み出す制御を行う。例えば、ストレージシステム10に対して、特定のファイルを指定して読み出し要求があると図15の矢印Y11参照、まず、ファイルシステムに基づいて、読み出し要求にかかるファイルに対応するハッシュ値の一部であるショートハッシュと論理位置の情報からなるコンテンツアドレスCAを指定する図15の矢印Y12参照。そして、ブロックデータ処理部21は、コンテンツアドレスCAがMFIファイルに登録されているか否かを調べる図15の矢印13参照。登録されていなければ、要求されたデータは格納されていないため、エラーを返却する。一方、読み出し要求にかかるコンテンツアドレスCAが登録されている場合には、上記コンテンツアドレスCAにて指定される格納位置を特定し、この特定された格納位置に格納されている各フラグメントデータを、読み出し要求されたデータとして読み出す図15の矢印Y14参照。このとき、各フラグメントが格納されているデータ格納ファイルF1~F12と、当該データ格納ファイルのうち1つのフラグメントデータの格納位置が分かれば、同一の格納位置から他のフラグメントデータの格納位置を特定することができる。そして、ブロックデータ処理部21は、読み出し要求に応じて読み出した各フラグメントデータからブロックデータDを復元する図15の矢印Y15参照。さらに、ブロックデータ処理部21は、復元したブロックデータDを複数連結し、ファイルAなどの一群のデータに復元して、読み出し制御を行っているアクセラレータノード10Aに返却する図15の矢印Y16参照。次に、上記サブブロックデータ処理部22サブブロックデータ重複排除部について、図16乃至図18を参照して説明する。なお、以下では、上述したブロックデータ処理部21との関わりについても説明する。まず、図16に示すように、バックアップ対象データであるバックアップストリームが記憶される場合には、このバックアップストリームに対して、上述したようにブロックデータ処理部21にてブロックデータBへの分割が行われ、重複記憶排除を行いながら記憶装置31への記憶処理が実行される。加えて、サブブロックデータ処理部22は、以下の処理を行う。まず、サブブロックデータ処理部22は、バックアップストリームの一部である予め設定された個数からなる一連のブロックデータBの特徴値を算出し、この特徴値が予め設定された条件を満たすと、その一連のブロックをアンカーシーケンスと設定する。例えば、図16の斜線に示すように、3つのブロックデータBのハッシュ値を特徴値として算出し、この特徴値の下3桁のビット0となるなど設定条件を満たしたときに、これら3つのブロックデータをアンカーシーケンスとする。そして、図16に示すように、アンカーシークエンスが参照するアンカーを生成し、当該アンカーにはアンカーパックと呼ばれるデータ格納領域へのポインタを格納する。つまり、設定条件を満たした特徴値となるアンカーシーケンスが検出されると、その特徴値とアンカーパックとが関連付けられて記憶される。そして、サブブロックデータ処理部22は、上述したようにアンカーシーケンスを検出すると、これに隣接するブロックデータB、つまり、検出されたアンカーシーケンスが属するアンカーウインドウ内のブロックデータBを、さらに複数に分割して各サブブロックデータSBを生成する。例えば、ブロックデータBのデータ容量が64kBである場合に、当該ブロックデータBを複数のサブブロックデータSBに分割する例えば、平均して8kBの8つのサブブロックデータSBに分割する。また、サブブロックデータ処理部22は、各サブブロックデータのデータ内容に基づく値としてハッシュ値をそれぞれ算出して、これらハッシュ値を、各サブブロックデータを参照するポインタに対応付ける。そして、サブブロックデータ処理部22は、各サブブロックデータを記憶装置31に格納すると共に、各サブブロックデータを参照する各ポインタと各ハッシュ値との対応付けを、検出したアンカーシーケンスに関連付けられたアンカーパック内に順次格納する。ここでは、アンカーパックに格納されるサブブロックデータを参照するポインタとハッシュ値との対応付けを、当該サブブロックデータの格納先を表すサブアドレスデータとする。但し、サブブロックデータのハッシュ値自体を、当該サブブロックデータを参照するアドレスデータとしてもよい。なお、アンカーパックは、主記憶装置32に格納される。また、サブブロックデータ処理部22は、上述したようにアンカーシーケンスを検出し、このアンカーシークエンスの特徴値が既に主記憶装置32に存在する場合には、当該特徴値に関連付けられ既に主記憶装置32に格納されているアンカーパックを読み出し、サブブロックデータの重複記憶排除処理を行う。具体的には、バックアップストリームのブロックデータを分割したサブブロックデータのハッシュ値サブアドレスデータと、読み出したアンカーパック内のサブアドレスデータと、を比較して、同一の値がある場合には、サブブロックデータは既に記憶装置31に記憶されており、重複していると判定する。従って、アンカーパック内のサブアドレスデータを、バックアップストリームのサブブロックデータとして参照して記憶し、重複記憶を排除する。一方、バックアップストリームのブロックデータを分割したサブブロックデータのハッシュ値サブアドレスデータが、読み出したアンカーパック内にない場合には、サブブロックデータを新たに記憶装置31に記憶し、このサブブロックデータのハッシュ値を当該サブブロックデータを参照するサブアドレスデータとしてアンカーパック内に記憶する。なお、上述したブロックデータをサブブロックデータに分割して行う重複記憶排除は、上記ブロックデータ処理部21にて重複排除されなかったブロックデータに対してのみ行ってもよい。ここで、上述したサブブロックデータの重複記憶排除処理の具体例を、図17、図18を参照して説明する。まず、何もデータが記憶されていない状態で、バックアップストリーム1がストレージシステム10に記憶されたとする。このとき、各ブロックデータが記憶装置31に記憶されると共に、各ブロックデータのハッシュ値に基づく当該ブロックデータを参照するアドレスデータが記憶される。これと同時に、所定個数のブロックデータの特徴値が算出され、特徴値が設定条件を満たすアンカーシーケンスを検出すると、これに関連付けたアンカーパックを主記憶装置32に生成する。そして、アンカーシーケンスに隣接するブロックデータを各サブブロックデータに分割して補助記憶装置31に格納すると共に、各サブブロックデータのハッシュ値を算出して、これを各サブブロックデータを参照するサブアドレスデータとして、アンカーパックに順次格納する。続いて、上記バックアップストリーム1の更新データとして、バックアップストリーム2がストレージシステム10に記憶されたとする。すると、まず、バックアップストリーム2を順次ブロックデータに分割し、ブロックデータ単位にて重複記憶排除処理を行う。ここでは、符号B1’に示すブロックデータのみ、データ内容が更新されたとする。すると、ブロックデータB1’は記憶装置31に記憶されていないため、ブロックデータ単位での重複記憶排除は行われない。但し、本願では、ブロックデータB1’に対して、サブブロックデータ単位で重複記憶排除が実行されることとなる。上述したようにバックアップストリーム2がブロックデータ単位で処理されると同時に、所定個数のブロックデータの特徴値が算出され、特徴値が設定条件を満たすアンカーシーケンスを検出し、かかる特徴値が既出のもの、つまり、主記憶装置32に既に記憶されているか否かを調べる。検出したアンカーシーケンスの特徴値が既に記憶されている場合には、その特徴値に関連付けられた主記憶装置32内のアンカーパックを読み出す。つまり、ここでは、バックアップストリーム1の時に格納されたアンカーパックが読み出され、この中には、ブロックデータB1を分割した各サブブロックデータのハッシュ値がサブアドレスデータとして格納されている。また、上述したようにバックアップストリーム2のアンカーシーケンスを検出すると、この検出したアンカーシークエンスに隣接するブロックデータをサブブロックデータに分割して、そのハッシュ値を算出する。特に、この処理は、上述したようにブロックデータ単位で重複記憶排除が行われなかったブロックデータB1’について行われる。そして、算出したサブブロックデータB1’のハッシュ値と、上記読み出したアンカーパック内のサブアドレスデータと、を比較して、同一の値があるか否かを調べる。同一の値がある場合には、対応するサブブロックデータは既に記憶装置に記憶されているため、アンカーパック内のサブアドレスデータを、格納するサブブロックデータとして参照する。一方、同一の値がない場合には、対応するサブブロックデータを新たに記憶装置31に格納し、そのハッシュ値を格納したサブブロックデータを参照するサブアドレスデータとして、アンカーパックに含める。例えば、図18に示すように、ブロックデータ単位で重複記憶排除が行われなかったブロックデータB1’のうち、そのサブブロックデータSBのいくつかがサブブロックデータ単位で既に記憶されており符号D、網掛けで示すいくつかのサブブロックデータSBA,B,C,Dが記憶されていない場合には符号N、これら複数のサブブロックデータA,B,C,Dをまとめた状態でサブブロックデータが格納される。これにより、これらサブブロックデータを参照するメタデータを削減することができる。以上より、ブロックデータ単位のみでなく、サブブロックデータ単位で重複記憶排除を行った場合には、ブロックデータB1’の全てが記憶される場合を比較して、重複記憶排除の効率の向上を図ることができる。また、このとき、サブブロックデータが既に記憶されているか否かを調べるために用いるアンカーパック内のサブアドレスデータは、補助記憶装置31よりも記録再生速度が高速な主記憶装置32内に記憶されているため、サブブロック単位での重複記憶排除処理の高速化を図ることができる。但し、アンカーパックは、補助記憶装置31に記憶してもよく、いかなる記憶装置に記憶してもよい。また、上記アンカーパックは、所定のタイミングで例えば、定期的に、一旦、削除してもよい。これにより、使用されなくなったサブブロックデータを参照するサブアドレスデータを削除することができ、主記憶装置32の記憶容量の肥大化を抑制することができる。ここで、本実施形態では、アンカーシーケンスに対応するアンカーが参照するアンカーパックは、複数設定される。例えば、図16に示すように、符号A,Bに示すアンカーに対応するアンカーシーケンスが順に検出された場合には、符号Aのアンカーは、対応するアンカーパックを参照して関連付けられることはもちろんのこと実線矢印参照、この他にも、次に検出された符号Bのアンカーに対応するアンカーパックをも参照して関連付けられる点線矢印。これにより、検出されたアンカーシーケンスの位置に近接するサブブロックデータのアンカーパックに容易にアクセスすることができるため、重複データの発見がより容易となる。<付記>上記実施形態の一部又は全部は、以下の付記のようにも記載されうる。以下、本発明におけるストレージシステム図19参照、プログラムを記憶した記憶媒体、情報処理方法の構成の概略を説明する。但し、本発明は、以下の構成に限定されない。付記1データストリームを任意の容量に分割したブロックデータを、当該ブロックデータのデータ内容に基づくアドレスデータにて参照して記憶装置に格納すると共に、記憶装置に既に記憶されている前記ブロックデータと同一のデータ内容の他のブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記ブロックデータを前記他のブロックデータとして参照する前記アドレスデータを記憶装置に格納して前記ブロックデータの重複記憶排除を行うブロックデータ重複排除部101と、前記ブロックデータをさらに複数に分割した各サブブロックデータを、当該各サブブロックデータの各データ内容に基づく各サブアドレスデータにて参照して記憶装置に記憶すると共に、前記各サブアドレスデータからなるサブアドレスデータ群を所定の記憶装置に記憶し、記憶装置に既に記憶されている前記サブブロックデータと同一のデータ内容の他のサブブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記サブブロックデータを前記他のサブブロックデータとして参照する前記サブアドレスデータを前記所定の記憶装置に格納して前記サブブロックデータの重複記憶排除を行うサブブロックデータ重複排除部102と、を備えた、ストレージシステム100。付記2付記1に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記ブロックデータ重複排除部にて重複記憶排除されない前記他のブロックデータを複数に分割した前記各サブブロックデータに対して前記サブブロックデータの重複記憶排除を行う、ストレージシステム。付記3付記1に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記データストリーム内の一部の前記ブロックデータから当該ブロックデータのデータ内容に基づいて検出した特徴値が設定条件を満たす場合に、当該設定条件を満たす特徴値が検出された前記ブロックデータに隣接する別の前記ブロックデータを分割した前記各サブブロックデータを参照する前記サブアドレスデータ群を、前記設定条件を満たす特徴値に関連付けて前記所定の記憶装置に記憶する、ストレージシステム。付記4付記3に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記データストリーム内の一部の前記ブロックデータから検出した前記特徴値が前記所定の記憶装置に既に記憶されている場合に、当該特徴値に関連付けられて既に記憶されている前記サブアドレスデータ群と、前記特徴値が検出された前記ブロックデータに隣接する別の前記ブロックデータを形成する前記各サブブロックデータを参照する前記サブアドレスデータ群と、を比較して、前記サブブロックデータの重複記憶排除を行う、ストレージシステム。付記5付記4に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記サブアドレスデータ群の比較により、記憶装置に記憶されていない前記サブブロックデータが複数存在する場合に、当該複数のサブブロックデータをまとめて記憶装置に記憶する、ストレージシステム。付記6付記3に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記設定条件を満たす特徴値に、複数の前記サブアドレスデータ群を関連付けて前記所定の記憶装置に記憶する、ストレージシステム。付記7付記2に記載のストレージシステムであって、前記サブブロックデータ重複排除部は、前記設定条件を満たす特徴値に関連付けた前記サブアドレスデータ群を、前記ブロックデータ及び前記サブブロックデータを記憶する記憶装置よりも読み書き速度が速い前記所定の記憶装置に記憶する、ストレージシステム。付記8情報処理装置に、データストリームを任意の容量に分割したブロックデータを、当該ブロックデータのデータ内容に基づくアドレスデータにて参照して記憶装置に格納すると共に、記憶装置に既に記憶されている前記ブロックデータと同一のデータ内容の他のブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記ブロックデータを前記他のブロックデータとして参照する前記アドレスデータを前記記憶装置に格納して前記ブロックデータの重複記憶排除を行うブロックデータ重複排除部と、前記ブロックデータをさらに複数に分割した各サブブロックデータを、当該各サブブロックデータの各データ内容に基づく各サブアドレスデータにて参照して記憶装置に記憶すると共に、前記各サブアドレスデータからなるサブアドレスデータ群を所定の記憶装置に記憶し、記憶装置に既に記憶されている前記サブブロックデータと同一のデータ内容の他のサブブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記サブブロックデータを前記他のサブブロックデータとして参照する前記サブアドレスデータを前記所定の記憶装置に格納して前記サブブロックデータの重複記憶排除を行うサブブロックデータ重複排除部と、を実現させるためのプログラムを記憶した記憶媒体。付記9付記8に記載のプログラムを記憶した記憶媒体であって、前記サブブロックデータ重複排除部は、前記ブロックデータ重複排除部にて重複記憶排除されない前記他のブロックデータを複数に分割した前記各サブブロックデータに対して前記サブブロックデータの重複記憶排除を行う、ことを実現させるためのプログラムを記憶した記憶媒体。付記10付記8に記載のプログラムを記憶した記憶媒体であって、前記サブブロックデータ重複排除部は、前記データストリーム内の一部の前記ブロックデータから当該ブロックデータのデータ内容に基づいて検出した特徴値が設定条件を満たす場合に、当該設定条件を満たす特徴値が検出された前記ブロックデータに隣接する別の前記ブロックデータを分割した前記各サブブロックデータを参照する前記サブアドレスデータ群を、前記設定条件を満たす特徴値に関連付けて前記所定の記憶装置に記憶する、ことを実現させるためのプログラムを記憶した記憶媒体。付記11データストリームを任意の容量に分割したブロックデータを、当該ブロックデータのデータ内容に基づくアドレスデータにて参照して記憶装置に格納すると共に、記憶装置に既に記憶されている前記ブロックデータと同一のデータ内容の他のブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記ブロックデータを前記他のブロックデータとして参照する前記アドレスデータを前記記憶装置に格納して前記ブロックデータの重複記憶排除を行い、前記ブロックデータをさらに複数に分割した各サブブロックデータを、当該各サブブロックデータの各データ内容に基づく各サブアドレスデータにて参照して記憶装置に記憶すると共に、前記各サブアドレスデータからなるサブアドレスデータ群を所定の記憶装置に記憶し、記憶装置に既に記憶されている前記サブブロックデータと同一のデータ内容の他のサブブロックデータを記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記サブブロックデータを前記他のサブブロックデータとして参照する前記サブアドレスデータを前記所定の記憶装置に格納して前記サブブロックデータの重複記憶排除を行う、情報処理方法。付記12付記11に記載の情報処理方法であって、重複記憶排除されない前記他のブロックデータを複数に分割した前記各サブブロックデータに対して前記サブブロックデータの重複記憶排除を行う、情報処理方法。付記13付記12に記載の情報処理方法であって、前記データストリーム内の一部の前記ブロックデータから当該ブロックデータのデータ内容に基づいて検出した特徴値が設定条件を満たす場合に、当該設定条件を満たす特徴値が検出された前記ブロックデータに隣接する別の前記ブロックデータを分割した前記各サブブロックデータを参照する前記サブアドレスデータ群を、前記設定条件を満たす特徴値に関連付けて前記所定の記憶装置に記憶する、情報処理方法。"