"記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部を備え、前記データ格納制御部は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、ストレージシステム。請求項1に記載のストレージシステムであって、前記データ格納制御部は、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、ストレージシステム。請求項2に記載のストレージシステムであって、前記データ格納制御部は、前記特定の記憶装置から読み出した前記格納位置特定テーブルに基づいて、新たに記憶する記憶対象データを分割したブロックデータが記憶装置に既に記憶されているか否かの判定を行う、ストレージシステム。請求項3に記載のストレージシステムであって、前記データ格納制御部は、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データが前記特定の記憶装置から読み出した前記格納位置特定テーブル内に存在しない場合に、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、ストレージシステム。請求項1に記載のストレージシステムであって、複数の記憶装置に対する記憶対象データの記憶動作を制御する少なくとも1つの第一サーバと、前記複数の記憶装置を構成する複数の第二サーバと、を備え、前記データ格納制御部は、前記第二サーバから前記第一サーバに前記格納位置特定テーブルを読み出す、ストレージシステム。請求項5に記載のストレージシステムであって、前記記憶装置特定テーブルを記憶する複数の第三サーバを備え、前記データ格納制御部は、前記記憶装置特定テーブルを前記複数の第三サーバに分散して記憶する、ストレージシステム。情報処理装置に、記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部を実現させると共に、前記データ格納制御部は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、ことを実現させるためのプログラムを記憶した記憶媒体。請求項7に記載のプログラムを記憶した記憶媒体であって、前記データ格納制御部は、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、プログラムを記憶した記憶媒体。記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納方法であって、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、データ格納方法。請求項9に記載のデータ格納方法であって、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、データ格納方法。ディスクベースの重複排除におけるパフォーマンスの課題大規模な重複排除ストレージシステムを実装するためには、パフォーマンスに関するいくつかの重要な課題を解決する必要がある。大規模なシステムは膨大な数のブロックを保存するため、そのハッシュ値はメインメモリに収まらない。簡易なディスク上のハッシュインデックスを用いると、ランダムな読出しであるインデックスの検索によってパフォーマンスが著しく低下することになる。すべての入力ブロックを一時的に保存してオフラインで重複排除を行うことで、この問題を解決しているシステムもある。この場合、すべての新規ブロックが事前にわかるため、ハッシュ検索をハッシュの順序に再編成することによって、バッチで効率よく検索を行うことができる。しかし、オフラインで重複排除を行うには、一時的にブロックを保存する大規模かつ高性能な中継領域が必要となる。一方、インライン重複排除システムは、すべての重複ブロックをまとめて書き込まなくてもよいため、一般的な重複率が高いケースでは、より高い書込み性能を提供することができる。引用文献1に挙げるような多くのシステムでは、ストリーム局所性観測一般的に後続のバックアップ内の重複ブロックは、オリジナルのバックアップと同様の順序通りに現れることによってこの問題を解決している。バックアップストリームの局所性を保存することで、多くの重複ブロックのハッシュ値を効果的にプリフェッチできる。重複していないブロックは、メモリ内のブルームフィルタBloomfiltersを使用するか、またはパフォーマンスを高めるために多少の重複の可能性を犠牲にする近似重複排除で妥協することで、効率的に識別することができる。もう1つの問題は、ストリームの断片化によるストリーミング読出し性能の低下である。重複しているブロックは、新たに書き込まれたブロックとは別の場所に保存されているため、大きな連続する読出しは内部で複数の短い読出しに分割されると思われる。この問題は、正確な重複排除を行うシステムにはつきものである。その理由は、2つのストリームがシステムに保存されており一方が他方のランダムな置換えになっている場合、少なくとも1つのストリームは小さなランダムな読出しをしなければならないからである。実際には、効率的な重複排除を可能にする同じストリーム局所性観測を行うことで、このような最悪のケースが起こらないようにすることができる。しかし、システムが老朽化するにつれて通常は断片化が進むため、不適切なデータ配置によって内部の局所性が悪化することがないよう注意が必要である。拡張性のあるグローバルな重複排除非特許文献2に挙げるような集中型システムは、システムのサイズに関して拡張性が限られている。独立したシステムをいくつか構成して容量を拡張することはできるが、それらの間では重複排除機能は無効となり、またバックアップを孤立した記憶装置に置くことでメンテナンスの負荷が増大する。ブロックをそのハッシュ値に基づいてストレージノードに割り当てることによって、拡張性のあるグローバルな規模の重複排除を導入しているシステムもある非特許文献1。ここのシステムでは、大きなブロックのインデックスが全てのノードに有効に分割され、各ノードがハッシュ領域の一部を担当する。このアーキテクチャは、クライアントが単一である設定では拡張性と良好なパフォーマンスを提供するが、複数のクライアンドが同時に読出しまたは書込みを行うとパフォーマンスの問題が発生する恐れがある。ストリーム局所性の低下ブロックはすべてのノードに対して均等に分散化されるため、概して全てのノードが、システムサイズのファクタで縮小された入力ストリームの一部を受け取る。大規模なシステムでは、これによってストリームの局所性が著しく低下する。オリジナルのストリームが保持していたストリームの局所性は、各ノード内でもこのファクタによって低下する。あるストリームの重要な部分を読み出すには、システム内の全ノードの参加が必要である。多数のクライアントが同時に異なるストリームを読み出そうとすると、各ノード上で同じリソースを奪い合うことになる。高いスループットを達成するためには、ストレージノードはクライアント数に比例する読出しキャッシュのサイズが必要である。これはバッファ爆発問題bufferexplosionproblem非特許文献3として知られている。この問題はストリームの局所性の低下によってさらに悪化し、プリフェッチの効率を低下させる。その結果、非常に大規模なシステムでは、順次的なオリジナルストリームの読出しは、ストレージノード内でランダムな読出しに劣化する。重複排除の検索でも同じ問題がある。既存のブロックのハッシュ値のプリフェチもランダムな読出しに劣化する。しかし、ハッシュ値はブロックのデータよりもはるかに小さく、適当なサイズのキャッシュに容易に収まるため、重複排除に関する否定的な影響はあまり目立たない。対称ネットワークのスループットブロックはストレージノードに均等に分散化されるため、全てのノードがほぼ同じ数のブロックをクライアントから受け取る。クライアントの数が増加すると、重複していないすべてのブロックの書込みを収容するためにネットワークのスループット要件も増加する。その結果、高い書込みスループットを提供するためには、対称的な高い2地点間スループットを有するネットワークがシステムに必要となる。後に述べるが、大規模なシステム用にこのようなネットワークを構築することは難しい。このため、本発明の目的は、上述した課題である、重複排除機能を有するストレージシステムにおける性能の低下を抑制することにある。本発明の一形態であるストレージシステムは、記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部を備え、前記データ格納制御部は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、という構成をとる。また、本発明の他の形態であるプログラムを記憶した記憶媒体は、情報処理装置に、記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部を実現させると共に、前記データ格納制御部は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、ことを実現させるためのプログラムを記憶した記憶媒体である。また、本発明の他の形態であるデータ格納方法は、記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納方法であって、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、という構成をとる。本発明は、以上のように構成されることにより、重複排除機能を有するストレージシステムにおける性能の向上を図ることができる。<実施形態1>本願では、グローバルなインライン重複排除機能を持つ拡張可能なストレージシステムのための、新たなアーキテクチャを提案する。このシステムでは、データ記憶装置を重複のインデックスから切り離すことで、システム規模による復元力の低下や全ノード間での均一帯域幅の必要性といった、既存のシステムが持つ欠点が改善される。本願の実施形態1は、次のように構成されている。まず、システム設計の際に検討する要件と前提を述べる。次に、この要件を満たすアーキテクチャについて説明し、提案するデータ構成上の鍵となる動作を説明する。次に、提案するシステムが要求される特徴をどのように提供するのかを評価し、その設計時に直面するトレードオフの関係を提示する。[要件と前提]本願で提案するシステムアーキテクチャについて説明する前に、当該システムが機能する環境に関する要件と前提について概説する。ストレージシステムの要件の概要ストレージシステムの主な適用対象はバックアップデータである。重複排除を最大限節約するために、ストレージシステムは多数のクライアントシステムのバックアップデータを保存する。このような環境では、大容量、高信頼性、および特有の性能特徴が必要となる。短いバックアップ時間内にバックアップを完了させなければならないため、非常に高い総書込みスループットが必要である。このシステムは、ほぼ書込みを行い、つまりデータの読出しよりも書込みをはるかに頻繁に行うシステムである。読出しは、主にバックアップシステムに障害が発生し再構築を行う時に行われる。通常、システムの再構築にかかる時間は重要であることから、合理的な高い読出しスループットが必要とされる。上記で説明した理由により、このストレージシステムによって実装される重複排除機能は、次の基準を満たさなければならない。ブロックレベル同一ブロック多様なサイズのブロック:ブロックの境界はコンテンツ指定チャンク分割によって設定ハッシュによる比較正確性インライン分散型グローバルな範囲低コストを維持するため、このシステムは商用の装置で構成され、ペタバイト単位のrawストレージに対応して数百/数千のノードまで拡張可能なものでなければならない。インタフェースこのシステムは、クライアント装置に対して業界標準バックアップインタフェースを提供する必要がある。Disk-to-Diskバックアップの観点において、これは通常NASNetworkAttachedStorageまたはVTLVirtualTapelibraryとしてエクスポートされるファイルシステムである。NASまたはVTLの導入に関する詳細は本願のテーマとは関連がないため、ここでは、非特許文献1に記載されるものと類似する、より簡潔なブロック保存インタフェースに焦点を当てる。非特許文献4に記載されるように、ファイルシステムは、このブロック保存のトップに構築することができる。要するに、ブロック保存は多様なサイズのデータのブロックの保存を可能にする。ブロックは不変であり、ブロック保存によって生成されるアドレスを通して検索することができる。同一の内容を持つブロックに同じアドレスを割り当てることで、重複排除が実行される。特別なポインタブロックは、個々のデータブロックを大きなデータストリームとして構成するために使用される。これらのポインタブロックはポインタが指すブロックのアドレスを含み、指す対象は通常のデータブロックまたはポインタブロックのいずれでもよい。通常ブロックと同様に、ポインタブロックも不変であり、同一のものは重複排除される。データストリームを表すポインタブロックのツリー通常のデータブロックが葉になるを構築することができる。このツリーのルートにあるポインタブロックのアドレスで、そのストリーム全体を検索することができる。ネットワークモデルこのストレージシステムは、内部ネットワークをデータソース、つまりクライアントのバックアップ装置に接続することに加えて、必要とされる大容量にまで内部ネットワークを拡大する必要がある。ネットワークは、ストレージシステムのノード間およびデータソースへのリンクにおいて、高いスループットを提供する必要がある。システムの規模が大きくなるにつれ、すべてのノード間で高い総スループットを実現する大規模ネットワークを構築するのは難しく、また高価になってくる。大規模なデータセンタのネットワークは階層的に構築されており、個々の装置が第1階層のスイッチ例えば1Gビットで接続され、第1階層のスイッチは、より高速な第2階層のスイッチ例えば10Gビット等で接続されている。スイッチ間の接続は、合理的な総スループットを提供するためには高速化する必要があるが、より高速な内部接続を使用すればネットワークのハードウェアのコストが上昇し、また複数の物理的リンクを接合すればケーブル敷設が複雑化する。当然、小規模なシステムは階層構造にはならず、すべてのノードが同じ第一階層のスイッチに接続され、すべてのノード間で同一の高いスループットが達成される。また、十分なリソースがあれば、総スループットの高い大規模ネットワークを汎用ネットワークハードウェア以外で構築することもできる。したがって、ストレージシステムは以下の両方に適応可能でなければならない。スイッチ内スループットが高くスイッチ間の総スループットが低い、階層的ネットワーク。任意の2つのノード間で全断面wholecrosssection帯域幅が利用可能な対称ネットワーク。クライアントシステムのパフォーマンスの制約ストレージシステムに書き込まれる、またはそこから読み出されるデータは、結果的にクライアント装置バックアップサーバを通過しなければならない。各クライアントのバックアップサーバは、データの調達と受信のためのリソースが限られているため、ローカルディスクまたはネットワーク接続のいずれかがボトルネックとなる。したがって、ストレージシステムは単一のストリームに高いスループットを提供する必要はなく、単一のクライアント装置のリソースは、ストレージシステムの数少ないノードよりも少ない例えば12。しかし、複数のクライアント装置から同時に複数のストリームの読出し/書込みがあった場合には、良好な結合的なパフォーマンスを提供しなければならない。[アーキテクチャ]概要本願で提案するストレージシステムは以下の種類のノードで構成される。アクセスノード:システムへの入口の役割を果たし、またクライアント装置に接続する。ストレージノード:データブロックを実際に保存する。インデックスノード:重複の識別と位置特定を担当する。異なる機能を持つノードは、ハードウェアの条件例えば消費電力、冷却、使用するデータセンタ領域により有益であれば、選択的に同じ物理的装置に結合することができる。上記に定める要件を満たすために、本願では以下の設計目標を備えるストレージシステムを提案する。局所性保存記憶装置1つのストリームに属する非重複ブロックのシーケンスは、ストレージノードの小さなサブセット上に近接して保存される。これにより、上記で述べたストリームベースの局所性が保存され、再構築の際に効率的に順次読出しを行うことが可能となる。また、これは重複排除性能にとっても重要であり、重複ブロックのハッシュ値を効率的にプリフェッチすることができる。このアプローチは、引用文献1に挙げるようなインライングローバル重複排除システムとは対照的である。これまでのシステムは重複インデックスとブロック保存を組み合わせ、ブロックをシステム全体に均等に分散させていた。また、ストリームの局所性をストレージノード内に保存しようとしているが、当初の分割によってその効果が減少している。グローバルなハッシュベースのインデックスブロックが書き込まれるストレージノードは、ブロックのハッシュ値に依存しないので、別のブロックインデックスを維持しなければならない。このインデックスは、ブロックのハッシュ値に基づいて、システム内のすべてのインデックスノードに渡って分割される。ハッシュ領域には、いずれにしても局所性がないため、ここでハッシュ値を求めることは適切であり、それによって良好な拡張性、並列性、および負荷バランスが実現される。記憶容量のバランスストリーム局所性の保存は、ある程度の最大ストリーム長までしか意味をなさない。これは順次的なディスクへのアクセスの効率によって決定される。1つの場所に十分な順次的なブロックが累積されれば、それ以上のブロックはどこかに保存される。したがって、所定のストリームの非重複ブロックが書き込まれるノードは、時間と共に変化する。これは容量のバランスを良好な状態に保つ役割を果たし、あるストレージノードが他のノードよりも早くフルになってしまう事態が避けられる。非対称ネットワーク性能データの場所はブロックのハッシュ値によって決定されるわけではないため、本願で提案するシステムでは、データの書込みを行うクライアント装置の近くのストレージノード上にデータを保存することができる。これにより、より高い階層のスイッチを介するデータ転送とそれに関連するネットワークのスループットのボトルネックを避けることによって、非対称ネットワーク内での書込み帯域幅を大きく改善することができる。重複排除のクエリーだけは、ネットワーク内のすべてのノードに一様に送信する必要があるが、これらは非常に小さく、大きな帯域幅を必要としない。上述したシステムを構成する論理的構成要素を以下に記載する。フロントエンドフロントエンドは、ファイルシステム、VTLや類似形態のデータをクライアントにエクスポートする。また入力される書込みストリームを多様なサイズのブロックに分割し、重複排除および保存の処理を行うためにそれらを提供する。フロントエンドはアクセスノード上に設けられる。システムのこの部分は、非特許文献1に記載される現在のHYDRAstorと同じでもよい。DHTネットワークオーバーレイ分散されたコンセンサスを伴う分散型ハッシュテーブルを用いてネットワークオーバーレイ層を実装する。DHTはシステムの拡張性のベースとなるものである。ネットワークオーバーレイは、以下のものを提供する。オブジェクトの場所の仮想化。障害およびシステム再構築の際、物理的装置に論理オブジェクトを効率的にマッピングすることが可能となる。障害の検出および耐性負荷バランスDHTのキー領域内でオブジェクトが均等に分散化されていると仮定小さなシステム全体の状態グローバルな状態の伝播と維持スーパーノードを含むFPN本願で使用するDHTは、スーパーノードを備える固定プレフィックスネットワークFixedPrefixNetwork:FPN非特許文献5である。ストレージシステムにおけるFPNの使用については既に非特許文献1に記載されているため、ここでは本システムの内容におけるオーバーレイの機能についてのみ概説する。オーバーレイネットワークは、キーハッシュ値を、これらのキーに対して責任を持つ一連のノードにマッピングする。これをスーパーノードに編成する。各スーパーノードは一定数のスーパーノードコンポーネントから構成される。スーパーノードコンポーネントは物理的ノードに設けられるこの場合はインデックスノードとストレージノード。1スーパーノード当たりのコンポーネント数、つまりスーパーノード濃度SupernodeCardinalitySNCは、所定のFPNに対して固定されている。同じスーパーノードのメンバーであるコンポーネントをピアという。各スーパーノードは、ハッシュキー領域の一部、つまりスーパーノード間で分割されたハッシュ領域を担当する。その際、領域全体がカバーされ、かつスーパーノード間の担当が重複しないような方法を取る。ノードの障害はスーパーノード内で対処する。所定のスーパーノードのすべてのコンポーネントは互いに継続的に接続を確認することによって、障害を検出し、状態の変化を伝える。あるノードに障害が発生した場合、そのノードに設けられているコンポーネントは、それ以外のピアによって再生される。非特許文献6又は7に挙げる分散型のコンセンサスアルゴリズムは、すべてのコンポーネントにそのスーパーノードのメンバーシップの一貫した状態を確実に保つよう、使用される。コンセンサスの定足数を維持するためには、各スーパーノードのSNCコンポーネントの半数以上が常に生存していなければならない。これにより、ネットワーク分割が分離脳動作を起こすこともない。またFPNは負荷バランスのレベルも提供する。FPNは、物理装置間で、利用できるリソースに比例してコンポーネントの分配を試みる。これは、各スーパーノードがほぼ同量の負荷を受ける1秒当たりの使用容量および要求の両方においてことを前提としている。また、障害耐性を高めるために、同じ物理的ノード上のピアコンポーネントを同一場所へ配置することも回避する。障害耐性とグローバル状態のブロードキャストを提供するよう拡張されていれば、異なるDHTをFPNの代わりに簡単に実装することができる。本願がスーパーノードを備えるFPNを使用した理由は、HYDRAstorシステムでこの使用に成功しているからである。データFPNとインデックスFPN本システムでは、次の2つのDHTを使用する。データFPN論理的なデータの位置を、その保存を担当するストレージノードにマッピングする。データFPNのコンポーネントはストレージノード上に設けられている。このマッピングはデータ位置の仮想化を提供する。つまり、論理的な位置はシステムの再構築または障害時でも変更されず、データが設けられているストレージノードが変わった場合でも、変更されない。データFPNの詳細は後に説明する。インデックスFPNブロックのハッシュ値を、そのハッシュ値の変換を維持するインデックスノードに割り当てる。このネットワークのコンポーネントは、インデックスノード上に設置される。詳細は後に説明する。インデックスノードとストレージノードとで別々のFPNネットワークを用いることにより、これらのタイプのノードを異なるハードウェアに設置することが可能となる。例えば、インデックスノードはより多くのCPUパワー、RAM、およびIOPSを必要とする一方、ストレージノードは大きな記憶容量とディスクおよびネットワークの高いスループットを提供する。この2つのネットワークのコンポーネントが同じ物理的装置上に設置されたとしても、上記の通り各々が異なるリソースを使用するため、通常は各ネットワーク内で独自に負荷のバランスが取られる。また、この2つのネットワークは異なるスーパーノード濃度それぞれSNCIndexとSNCDataを持ち、独立して成長するFPNスプリットは互いに同期する必要はない。ブロック保存データ構成の概要このシステムに保存されるすべてのユーザデータは、データFPNコンポーネントによってブロックとして保存される。ブロックは冗長符号化されてSNCDataフラングメントとなる。これにはオリジナルのフラグメントと冗長フラグメントとが含まれる。オリジナルのフラグメントと冗長フラグメントとの割合はユーザがデータに割り当てたクラスによって決定される。ブロックは、書込み時にデータFPNスーパーノードに割り当てられる。割当ポリシの詳細は後に説明する。SynchrunとSCCデータFPNスーパーノード内において、保存されたブロックはSynchrunにグループ分けされる。同じブロックに属するフラグメントは、そのSynchrunの該当するSynchrunコンポーネントに入力される。各Synchrunには、フラグメント番号0からSNCData-1に対応する、SNCDataSynchrunコンポーネントがある。Synchrunとは、データ同期動作のための処理の原子単位である。ブロックは、バックグラウンドでのメンテナンス動作中は決してsynchrun境界を越えることはない。不可欠な数のSynchrunコンポーネントは、SynchrunコンポーネントコンテナSynchrunComponentContainer:SCCにグループ分けされ、SCCはストレージノードのデータディスクに保存される。SCCは付加のみであり、SCC全体が書き込まれた時点で不変となる。後続のバックグラウンド処理でのみSCCを書き換えて修正するができる。SynchrunコンポーネントのSCCへのグループ分けは、1つのストレージノードが追跡すべき主体数を固定するために行う。ブロックがシステムから削除されるとSynchrunのサイズは縮小する。SCCのサイズは、ほぼ1つのSynchrunコンポーネントの当初のサイズ約64MBに維持される。もし連続するSynchrunのサイズが縮小されたら、それらを連結してサイズを維持する。Streamrun複数の連続するSynchrunは、Streamrunにグループ分けされる。このグループ分けは静的であり、Synchrunが割り当てられた時点で決定される。Streamrunとは、良好な局所性を保つために同じスーパーノードに保持すべき同じストリームの一連のブロックに該当し、保存バランスを保つ単位である。局所性の保持と容量バランスに品質との間にはトレードオフの関係があり、これはStreamrunのサイズによって制御することができる。このトレードオフの関係については、後に詳細に検討する。Synchrunの識別各synchrunは64ビットの識別子で識別される。SynchrunのIDは、Synchrunが属するスーパーノードを静的に決定する。SynchrunのIDは論理的に次の3つの部分に分けられる。スーパーノードゾーンのプレフィックスそのスーパーノード内でのStreamrunのIDそのStreamrun内でのシーケンス番号シーケンス番号のビット数は固定されており、スーパーノードのプレフィックスとして解釈されるビット数は、システムが拡大しFPNゾーンのプレフィックスの長さが長くなるにつれて増加する。詳細については後に説明する。ブロック識別とフラグメント検索このシステムに保存されるすべてのブロックには、それが書き込まれたSynchrun内のシーケンス番号が割当てられる。このシーケンス番号とSynchrunのIDの組み合わせによって、システム全体に含まれるブロックを一意的に識別する。したがって、SynchrunID、BlockSeqNumのペアをユニークブロックアドレスという。このアドレスは、後にブロックが削除された場合でも再利用されることはない。書込みイニシエータ所定のスーパーノードに新規ブロックを保存する要求は、常にそのスーパーノードの固定のコンポーネント、つまり書込みイニシエータを経由する。イニシエータは、Synchrun内で一意のブロック識別子を割当て、書込み処理と、そのスーパーノードの他のコンポーネントおよびインデックスFPNとの間の調整を担当する。SCCインデックス未加工のフラグメントデータとは別に、各SCCは、そのSCCに属するフラグメントのメタデータを保存する。このメタデータには、例えばブロックのハッシュ値、一意のブロックID、サイズ、およびSCC内でのフラグメントのデータの位置等が含まれる。このメタデータは、データとは別にSCCインデックス内に保存される。したがって、SCCインデックスは読出しの更新を迅速に行うことができ、フラグメントデータを飛ばし読む必要がない。SCC内でのフラグメントの位置がわかれば、SCCインデックスから個々のブロックのメタデータを読み出すこともできる。ブロックの削除により、一意のブロックIDだけではフラグメントの位置が特定されないため、外部から探す必要がある。グローバルブロックインデックスグローバルブロックインデックスとは、保存されたブロックのハッシュ値を一意のブロック識別子例えばShnchrunID、BlockSeqNumのペアにマッピングする、分散型のハッシュテーブルである。これはインデックスFPNの上部に実装される。ハッシュテーブルは、ブロックハッシュキーのプレフィックスに基づいて分割される。所定のブロックのハッシュ値の保存を担当するノードは、インデックスFPNコンポーネントが設けられ、そのハッシュ値に対応ずるゾーンを有するノードである。1つのインデックスノード内において、マッピングはディスク上のハッシュテーブルに保存される。グローバルブロックインデックスは障害耐性を有し、各ゾーンは、スーパーノードのすべてのSNCIndexコンポーネント上に複製される。インデックスは、そのサイズによりディスクに保存される。更新はメモリ内に一時的に格納され、バックグラウンドで一括適用される。インデックスは、メモリ内のブルームフィルタを用いて存在しないブロックに関する安価なクエリーをサポートする。存在するブロックに関するクエリーは、1つのランダムなディスク読出しを必要とする。ディスク圧縮インデックス各ストレージノード内において、グローバルブロックインデックスはディスク圧縮インデックスDiskCompactedIndex:DCIというディスク上のデータ構造に保存される。DCIは高いパフォーマンスで非重複ブロックを識別する必要がある。DCIは、否定非重複クエリー用のメモリ内ブルームフィルタを備えるディスク上のハッシュテーブルと同様に、標準的なディスクの上部に実装することができる。これは非特許文献2に記載されているインデックスと類似する。この解決策において、すべての更新、つまり変換の入力と削除は、ランダムな書込みを避けるためにメモリ内バッファに入れられる。ディスク上のハッシュテーブル、書込みバッファ、およびブルームフィルタは、バケットに分割され、各バケットはキー領域の一部に相当する。書込みバッファが一杯になると、バックグラウンドスイープによって各バケットが以下の順序で処理される。ディスク上のハッシュテーブルのバケットを読み出す。書込みバッファから更新があれば適用する。バケット用のブルームフィルタ部分を再構築する。更新したバケットをディスクにフラッシュする。あるいは、インデックスをフラッシュベースのSSDに保存することもできる。これについては最近研究が行われており、RAM消費が削減される効果と、かなりの節電の可能性がある。ハッシュテーブルのサイズを縮小するために、DCIはすべてのキーブロックのハッシュ値を明示的に保存する必要はない。ハッシュテーブル内に衝突があった場合、照合する変換はすべて戻される。これらの候補ブロックは、適切なSCCインデックスからそのメタデータを読出し、すべてのブロックのハッシュ値が一致するかどうかを確認することによって、検証することができる。さらにキーの数ビットがDCIに追加保存された場合は、候補数は平均して1近くに維持することができる。ブロックインデックスの更新グローバルブロックインデックスは、ブロックのsynchrunへの書込みに成功し、それがガーベジコレクション処理によって削除された後、更新される。グローバルブロックインデックス内の、ブロックのゾーンのホスティングを担当するインデックスノードは、通常、実際にブロックを保存するストレージノードとは異なるため、インデックスの更新を慎重に同期させる必要がある。新規に書込まれる各ブロックについては、ブロックをデータFPNに書き込む書込みイニシエータによって、ハッシュキーからSynchrunID、BlockSeqNumへの変換が作成される。この変換は適切なブロックインデックスゾーンを備えるインデックスノードに送られ、送信先であるインデックスノードの変換ログ保存され、バックグラウンドでDCIに書き込まれる。変換ログ内に変換が維持される限り、インデックスノードは書込みイニシエータに返信する。変換入力要求を失う可能性があるため、各書込みイニシエータはグローバルブロックインデックスに入力すべき永続的な変換のログを維持する。ログからの変換の入力要求は、インデックスノードから成功の返信を受信するまで定期的に再送信される。インデックスノードは重複する変換の入力要求を受け取ることができる。SynchrunID、BlockSeqNumはすべての書込みに対して一意であるため、重複入力を安全に削除することができる。重複入力は通常、DCIの書込みバッファ内にあるうちに検出されるが、DCIのスイープ時に削除してもよい。削除変換は、ガーベジコレクションによってのみグローバルブロックインデックスから削除される。最も簡潔な解決策では、グローバルブロックインデックス全体を、ガーベジコレクション終了後に残っているブロックから再構築することができる。また、以下に述べる、より洗練された解決策もある。ガーベジコレクションの目的において、システムの寿命はエポックと言われるフェーズに分割される。システム内でのすべてのブロックの書込みは、あるエポック内で実行される。現在のエポック数はグローバル状態に維持され、ガーベジコレクションの処理が開始されると前進する。エポックは、エポックn-1からのすべてのブロックがGBIに追加された後にのみ、n1に前進することができる。エポックnでのガーベジコレクションでは、エポックn-2までに保存されたブロックのみつまり既に確実にGBI内にあるブロックのみを削除する。これらのフェーズは、GBI変換更新、ブロック削除、およびGBI変換削除の間での競争を避けるためのものである。GBI入力要求変換ログのエントリにはエポック番号が刻印され、古すぎるエポックからの要求は、受信するインデックスノードによって重複として排除される。ガーベジコレクションで、あるブロックを削除すべきと決定されると、その変換に対する削除要求が送信される。この要求には現在のエポックも刻印される。そのブロックが再び保存される場合は、別のsynchrunになるため、別の変換となる。ハッシュのリース変換は、ブロックのsynchrunへの保存に成功した場合にのみ、グローバルブロックインデックスに追加される。そのため、複数のクライアントが同時に同じブロックを書き込もうとすると競合が発生し、同じブロックが保存される可能性がある。競合を避けるために、クライアントは、ブロックを保存に提供する前にグローバルブロックインデックスからそのブロックのハッシュ値を借りるリースを取得する。リースの取得は、書込みを行う可能性のある他のクライアントに対して、そのブロックがすでに書き込まれており、オリジナルの書込みを行う者と同期する必要があることを示すものである。そのハッシュ値に対して実際の変換が入力された場合、書込みに失敗した場合、またはリースの期限が切れた場合例えば書込みを行うオリジナルのアクセスノードが応答を停止した場合に、リースは返却される。変換キャッシュ変換キャッシュとは、すでに保存されているブロックに対し効率的に重複排除を行うために使用する、SCCインデックスのメモリ内キャッシュであり、データストリーム内の重複ブロックの局所性を利用する通常の重複ブロックは、当初保存されたときと同じ順序で書き込まれる傾向がある。変換キャッシュはアクセスノード上に位置する。各アクセスノードは、ブロックが重複しているかどうかを決定する際にローカル変換キャッシュを調査する。キャッシュは、そのホストであるストレージノードからSCCインデックスをダウンロードすることによって追加入力される。キャッシュの容量は限られているため、最近変換が使用されていないSCCインデックスはキャッシュから削除することができる。変換キャッシュに保存されているSCCインデックスは、その基礎となるSCCが変更された場合には陳腐化する。変換キャッシュの内容は常に使用前にストレージノードで検証されるため、検証に失敗した場合はキャッシュから削除される。[動作]次に、上記のデータ構成における一般的な動作について説明する。書込みおよび重複排除ユーザからの書込みは、まずアクセスノードのフロントエンドで処理される。ここでは、書込みを多様なサイズのブロックに分割し、ブロックのツリーを構築する。各ブロックについて、SHA-1ハッシュキーを計算し、これを使用してブロックが唯一のものか、または重複しているのかを決定する。重複ブロックブロックのハッシュキーを、まず変換キャッシュ内で検索する。そこに存在する場合は、候補となるオリジナルのブロックのsynchrunとユニークブロックIDを検索する。synchrunIDを使用して、要求をストレージノードに送信し、変換キャッシュのエントリが陳腐化していないこと、またブロックが、それに対する重複書込みに十分な耐性を持つことを検証する。この検証に通れば、書込み処理が完了する。ブロックが変換キャッシュ内にない場合、または検証に通らない場合は、ブロックのハッシュキーに関するクエリーをグローバルブロックインデックスに送信する。クエリーがDHTを通って適切なインデックスノードに届けられると、グローバルブロックインデックスが読み出され、一連のブロック候補の位置が返信される。これらの候補を1つずつ検証する実際には、平均1つの候補しかない。各候補について、そのsynchrunが置かれているストレージノードに要求を送信する。ユニークブロックIDを用いて、フラグメントメタデータの位置を検索し、SCCインデックスから読み出す。フラグメントメタデータはブロックのハッシュ値を含む。これは新たなブロックのハッシュ値と比較することができる。これらが一致し、ブロックに十分な耐性がある場合は、重複を検索する。そうでない場合は残っている候補のチェックを行う。重複ブロックが排除されたら、次の重複排除を高速化するために、オリジナルブロックのSCCインデックスを変換キャッシュへ読み込むことを検討する。ユニークなブロック変換キャッシュが利用可能なエントリを含まない場合は、グローバルブロックインデックスを調査する。グローバルブロックインデックス内にブロックがなかった場合は、ブルームフィルタを使用しているおかげで、ディスクにアクセスせず否定回答が返信される可能性が高い。候補が発見されなかった場合、またはすべての候補ブロックが拒否された場合、そのブロックは唯一のものであり、保存される。アクセスノードは、書き込まれる各データストリームについて、1つのオープンなSynchrunを維持する。新規ブロックはすべてこのsynchrunに保存される。ストリームに対してオープンなsynchrunがない場合、または以前のsynchrunの容量を超えた場合は、新たなsynchrunが割り当てられる。オープンなsynchrunが選択されると、ブロックは冗長符号化されてSNCDataフラグメントになり、そのフラグメントはオープンなsynchrunが置かれているスーパーノードのコンポーネントに送信される。コンポーネントの1つである書込みイニシエータは、書込み処理の同期を担当し、保存するブロックの変換をグローバルブロックインデックスに入力するための要求を送信する。また、SNCDataフラグメントの保存の確認を回収し、成功か失敗かをアクセスノードに返信する。Synchrunの割当て新たなSynchrunは常に、そのSynchrunを担当するスーパーノードの書込みイニシエータによって作成される。書込みイニシエータは、以前に割り当てられていたStreamrunおよびその中のSynchrunを知っており、新たに割り当てられたSynchrunが一意なIDを持つことを保証することができる。アクセスノードは、以下の2つの場合にSynchrunを割り当てる必要がある。新たなストリームの、最初の唯一のブロックを書き込む前。以前のSynchrunがフルになった場合。アクセスノードが、そのストリームにオープンになっているSynchrunを既に所有している場合は、当然、同じStreamrun内に次のSynchrunを割り当てようとする。StreamrunIDはスーパーノードを決定するため、割当要求をデータFPNから適切な書込みイニシエータへ送信することができる。割当てに成功すると、書込みイニシエータは次のSynchrunIDを割り当て、それをアクセスノードに戻す。そしてアクセスノードは、このSynchrunIDを持つすべての新たな書込みを提供する。Streamrunがフルであるか、またはスーパーノードが不足しているとの理由で割当てに失敗した場合、アクセスノードは新たなStreamrunを割り当てなければならない。新たなStreamrunを割り当てるために、アクセスノードはまず、ホストとなる新たなスーパーノードを選択する。スーパーノードを選択するには、データFPN内のランダムなキーを検索し、そのキーを担当する書込みイニシエータに対して割当要求を送信する。割当てに成功したら、新たなStreamrunの最初のSynchrunのIDをアクセスノードに返信する。そうでない場合、アクセスノードは別のスーパーノードを選択する。この基本割当ポリシを修正して、後述する非対称ネットワークに対応する特徴を提供することができる。通常、各クライアントストリームに対して個別のSynchrunが割り当てられる。しかし、オープンなSynchrunはストレージノード側にいくつかのリソースを必要とするため、1スーパーノード当たりの同時にオープンになるストリームの最大数には制限がある。同時にあまりにも多くのストリームが書き込まれると、同じSynchrunが複数のストリームで使用されることにある。Synchrunの共有による不都合な点は、同じSynchrunに関連性のないデータが混在して、良い効果であるストリームの局所性が損なわれることである。我々は、実際には同時に書き込まれるストリームの数が膨大になるとは想定していないため、このケースに関して最適化する意図はない。重複ブロックの同時書込み複数のアクセスノードが同時に同じブロックを書き込もうとした場合、同じブロックの複数のコピーが保存される可能性がある。グローバルブロックインデックスのリースは、このような事態が実際に発生するのを防ぐために使用される。リースは常に、新たなブロックが書き込まれる前に取得される。つまり、リースは、グローバルブロックインデックスのクエリーが候補を返信しない場合、またはすべての候補が明らかに拒否された場合に、自動的に取得される。リースには、書き込まれるブロックのハッシュ値と、このブロックを書き込むアクセスノードのアドレスが含まれる。グローバルブロックインデックスのクエリー中に、要求するハッシュ値のアクティブなリースが発見されると、他のアクセスノードが同時に同じブロックを書き込んでいるという通知が返信される。その後の書き込みは、オリジナルのアクセスノードに連絡を取り、オリジナルブロックの書込みが終了するまで待つ。リースは、そのハッシュ値の変換がGBIに入力された場合、書込み処理に失敗した場合例えば容量不足、またはタイムアウトになった場合例えばアクセスノードの障害に、開放される。リースは、そのブロックのハッシュ値を担当するインデックスFPNのスーパーノード内の選択されたコンポーネントによってのみ付与される。また、リースは、そのコンポーネントがしばらくの間そのスーパーノード内のクオラムから連絡を受けなかった場合は、付与されない。これにより、インデックスFPNのコンポーネントが失敗した場合またはネットワークから分断された場合に、重複するブロックが同時に書き込まれる可能性が短時間に制限される。読出しブロックは、ポインタブロックにどのタイプのアドレスが保存されているかによって、ハッシュキーまたはユニークブロックIDのいずれかに基づいて読み出すことができるこれについては後に詳しく説明する。ブロックは、十分な数のフラグメントを読み出すことで再構築することができる。実際にデータを読み出すためには、まずSCC内のフラグメントのオフセットを検索する必要がある。ハッシュに基づいて読み出すには、ユニークブロックIDを検索するためのステップがさらに必要である。変換キャッシュとグローバルブロックインデックスを調べることによって、重複排除処理と同様に行うことができる。アクセスノード上の変換キャッシュは、SCCオフセットを探すために使用される。キャッシュ内にユニークブロックIDがある場合は、関連するエントリに既にデータオフセットが含まれている。このオフセットは陳腐化している可能性があるため、フラグメント読出し要求を処理する際に、ストレージノードで検証する。変換キャッシュ内にフラグメントに関するエントリがなかった場合、フラグメント読出し要求は、そのフラグメントのsynchrunを担当するストレージノードに提供される。ストレージノードは、変換キャッシュ内で発見されたオフセットを使用してデータを直接読み出すことができる。オフセットがわからない場合または無効である場合は、SCCインデックスのエントリを読み出さなければならない。これは、一般的にはコンポーネントの内の1つに対してのみ行えばよい。その理由は、同じブロックのフラグメントは、通常すべてのSNCDataSCC内で同じオフセットに保存されているからである。重複排除と同様に、その後の読出しを高速化させるために、十分な数のフラグメントを含んだSCCのインデックスが変換キャッシュにダウンロードされる。ブロックの再構築には、オリジナルのフラグメントのみを読み出せばよい。オリジナルのフラグメントが好ましい理由は、オリジナルのフラグメントからオリジナルのデータを再構築する場合は冗長符号の復号化が必要ないからである。しかし、複数のディスク内でより均等に読出し要求を展開するには、オリジナルではなくいくつか冗長フラグメントを読み出すことが有益である。障害回復インデックスとストレージノードの障害は適切なFPN層によって検出される。障害が発生したノードに設けられているFPNコンポーネントは、別のインデックス/ストレージノードに再形成されるコンセンサスを用いる。このノードの選択は、1ノード当たりのコンポーネント数のバランスが維持されるように行う。コンポーネントの位置が変更されると、そのコンポーネントに関連するすべてのデータSynchrunまたはグローバルブロックインデックスのエントリは、以前の位置から移行されるか、またはピアのコンポーネントから再構築される。この再構築処理はバックグラウンドで行われる。インデックスFPNでは、グローバルブロックインデックスの変換が複製され、簡単にコピーすることができる。データFPNでは、SCCは、残りのフラグメントを読み出し、オリジナルブロックを再構築し、不足しているフラグメントを再符号化し、不足しているSCCを新たなコンポーネントの位置に書き込むことで、再構築される。負荷バランスを維持するため、回復したコンポーネントは通常、複数のノードに渡って展開される。したがって、データ再構築では、複数のノードに平行して書き込みを行い、高い再生パフォーマンスを生み出して迅速に意図する耐性レベルを回復する。削除と領域の再利用ブロックの削除は分散型のガーベジコレクション処理を用いて行う。非特許文献1に記載されているアルゴリズムと同じものを本システムに適用することができる。分散型ガーベジコレクション概説すると、SCCインデックス内で、各ブロックについて参照カウンタを維持する。ブロックの参照カウンタは、そのブロックを参照するポインタブロックの数である。カウンタ値は、周期的なガーベジコレクション処理によってのみ変化する。ガーベジコレクションは段階的に実行され、グローバル状態メカニズムを用いてグローバルに同期される。第1段階では、前回のガーベジコレクション以降に書き込まれた新たなポインタブロックをすべて処理し、カウンタのインクリメント要求を、ポインタで指されているブロックが設けられているストレージノードに送信する。すべてのブロックの処理が行われたら、ユニークブロックIDによって参照カウンタの更新が保存され、所定のSCC内のすべてのブロックに対して一括適用される。そして、参照カウンタが0のポインタブロックを識別する。これらのブロックは削除対象であるため、これらのブロックが指しているすべてのブロックに、カウンタのデクリメント要求を送信する。参照カウンタの更新を再び適用し、他にも削除されたポインタブロックがある場合は、新たなデクリメント段階を開始する。エポックと言われる複数段階に分割することにより、グローバルブロックインデックスの更新とブロック書込みとの同期が簡潔になる。つまり、ブロックは、書き込まれたのと同じエポック内では削除されることはなく、次のエポックに進むためには、進行中のすべてのグローバルブロックインデックスの更新が完了する必要がある。領域の再利用ガーベジコレクションの処理は、ブロックを死んだものとマークするだけである。つまり、それらの変換がグローバルブロックインデックスから削除され、新たな重複が削除されることはないが、その保存領域はまだ開放されていない。この領域は、バックグラウンドで、一度に1つのSCCについて再利用が行われる。領域の再利用はSynchrunの平均サイズを縮小させる。SCC当たりのメタデータの量が無限に増加するのを防ぐために、連続するSCCを連結してバウンド内の平均SCCサイズを維持する。連続するSynchrunを含むSCCのみ連結可能である。同じStreamrunからのSynchrunの連結が優先され、異なるStreamrunからのSynchrunは、そのStreamrunからのデータを含む他のSCCがない場合は1つのSCCに入力される。システム成長システムに新たなストレージノードが追加され容量が増える場合は、良好な負荷バランスを保つためにFPNスーパーノードの数を増やす必要がある。そのためには、ゾーンプレフィックスの長さを長くすればよい。各FPNコンポーネントは、より長いプレフィックスを備える2つの新たなコンポーネントに分割される。グローバルブロックインデックスのエントリは、ハッシュキーに基づいて新たなコンポーネント間で分割される。Synchrunも、この新たなスーパーノード間で分割される。そのためには、ゾーンプレフィックスとして解釈されるSynchrun識別子のビット数を長くし、StreamrunIDの最も重要性が低いビットをゾーンプリフィックスに移動する。例えば、IDプレフィックス:streamrun:シーケンスNoが01:0:0、01:1:0、01:2:0、01:3:0、01:4:0、01:5:0であるSynchrunは、分割後は010:0:0、011:0:0、010:1:0、011:1:0、010:2:0、011:2:0と等しい。その結果、システムが成長すると、synchrunはStreamrunの処理単位で、新たなスーパーノード間で等しく分散される。分割後に異なるスーパーノードに属するSynchrunが1つのSCCと結合すると、そのSCCはバックグラウンド処理で分割されることになる。しかし、これはめったに発生しない。その理由は、Streamrun間の連結の前に、Streamrun内の連結が優先されるからである。コンポーネントおよびデータは、瞬時的な書込み帯域幅を提供するために、常に新たに追加されたノードに対して再びバランスを取るように設定される。データ構成の説明と評価Streamrunのサイズの影響Streamrunのサイズによって、データのストリームに対して新たなスーパーノードが選択される頻度が決まる。Streamrunのサイズの選択に関連してトレードオフの関係がある。負荷バランスを考えると、新たなスーパーノードへのスイッチが頻繁に行われる例えば各synchrunの後方が良い。ただし、次の点を考慮する必要がある。システム成長後、スーパーノード間でデータが拡散されるディスクのスピンダウンが回避される。各synchrunの後にスイッチングを行う場合とスーパーノードがフルになった後にのみスイッチングを行う場合との、正しいバランスを探る必要がある。容量のバランススーパーノードのコンポーネントは、システム内の容量のバランスを取るために使用される。コンポーネントは、ストレージノードに対して、そのストレージノードの記憶容量に比例して割り当てられる。すべてのコンポーネントは常に移転するため、各ストレージノードに複数のコンポーネントが存在し、それによってバランスの規模を保っている。スーパーノードのコンポーネントのレベルでバランスを取ることによって、すべてのスーパーノードがほぼ同じサイズであれば、使用される容量のバランスが保たれる。Streamrunをスーパーノードに対して均等にランダムに割り当てることによって、著しくバランスの取れないサイズのスーパーノードが形成されることが抑制される。入力データと削除方式との間に関連性があれば、スーパーノードのバランスは保たれる。ハッシュ値を用いてブロックを分散させるシステムと比較すると、割当ユニットは比較的大きい。我々が提案するシステムではStreamrun全体が割り当てられており、これは少なくとも3オーダーの規模でブロックよりも大きい。Streamrunが大きすぎると、スーパーノードに対するシンプルな均等割当が行われた場合に、システムの最大利用が損なわれると思われる。割当ユニットのサイズの選択によって、ランダムな割り当てによって達成される最大利用にどのような影響が出るのかを評価する実験を行った。Streamrunは、満杯のスーパーノードが出てくるまで、ランダムに選択されたスーパーノードに割り当てられる。この実験は、各スーパーノードのサイズが1.5TBの、48TBのシステムを想定している。64MBのStreamrunでは、スーパーノード間のアンバランスは平均2である。厳密に均等なランダム割当ポリシでは、容量の98に書込みが行われた場合にシステムがフルになると思われる。しかし、当初選択されたスーパーノードの容量が不足した場合に別のスーパーノードへの割り当てを試みることで改善できる。これにより、新規書込みによって使用がほぼ100に達することが可能になる一方、データの削除により著しいアンバランスが発生することもほとんどない。冗長性と並列性データFPNのスーパーノード濃度により、以下の事項が決定される。データFPNの冗長性。アクティブなFPNコンポーネントの半分以下しか永久的な故障は許されない。そうでないとコンセンサスのクオラムが失われる。利用可能なデータ復元クラスの数。冗長符号化は0からSNCData-1までの冗長フラグメントを作成するよう構成することができる。1つのストリームに割り当てられる並列性の数。各ブロックの書込みでは、SNCDataフラグメントの書込みが必要であり、ブロックの読出しでは、少なくともそのブロックのオリジナルフラグメントの読出しが必要である。したがって、1つのデータストリームが実際にはSNCDataのストレージノードに分散化される。この分散化により、SNCDataストレージディスクまでのデータアクセスが並列化され、1ストリーム当たりのスループットが改善する。単一のストリームのスループットがさらに高いシステムを構成するために、SNCDataを増やすことができる。しかし、SNCDataが過剰になると、1つのブロックを読み出すのに多くのディスクにアクセスしなければならないため、ストリームの局所性とランダムな読出し性能が低下する。標準的なスーパーノード濃度の値は12であり、これは、良好なストリームの局所性とランダムな読出し性能を維持しつつ、1つのクライアントのスループットを飽和させるのに十分な並列性を提供する。インデックスFPNのスーパーノード濃度はこれより低くてもよい。その理由は、グローバルブロックインデックス変換が冗長符号化されるのではなく、複製されるからである。並列性は、本質的にハッシュベースの負荷分散によって提供されている。そのため、このケースではネットワークの生存可能性と利用可能性のみを検討すればよい。ポインタブロック内のブロックアドレスポインタブロックは、既に保存されている他のブロックを参照するブロックである。ポインタブロックは、個々のデータブロックを、ファイルまたはファイルシステム全体のスナップショットのようなデータ構造に組み込むために使用される。システムに保存される各ブロックは、コンテンツ由来のハッシュアドレスまたは位置に依存するユニークブロックアドレスのいずれかによってアクセスすることができる。これらのアドレスはいずれも、原則的にはポインタブロックに保存される。ポインタの種類の選択にはいくつかのトレードオフがある。これを図1に示す。アドレスサイズハッシュアドレスは、何らかのメタデータ例えば復元クラスと連結したブロックのコンテンツのハッシュ値である。このアドレスは、想定されるサイズのシステムにおいて、ハッシュ衝突の可能性を無視するのに十分な大きさでなければならない。SHA-1ハッシュ関数を使用すると仮定すると、ハッシュアドレスは20バイトである。ユニークブロックアドレスはSynchrunId、blocksequencenumberのペアで、システム内のブロックを一意に識別する。SynchrunIDは体系的に割り当てられるため衝突の可能性がないことから、このアドレスはハッシュ値よりもはるかに小さくすることができる。ブロックを一意に識別するのに必要なビット数は、システムの寿命が続く間にシステムに書き込まれる非重複ブロックの数に依存する。ブロックのサイズがわずか1Kで1Synchrun当たり216ブロックと仮定すると、64ビットのSynchrun識別子領域は、240ペタバイトの非重複データが書き込まれるまで使い果たすことはない。読出し性能ブロックのデータを読み出す前に、ブロックの位置を検索する必要がある。複数のブロックを、当初書き込まれたときと同じ順序で順次読み出す場合、これらの検索のほとんどは、ディスクにアクセスすることなく変換キャッシュで対応する。しかし、変換キャッシュはストリームの最初の数ブロックストリームのSCCインデックスがプリフェッチされるまでの変換を含まない場合があり、またキャッシュはランダムな読出しには全く効果がない。この場合、コストの高いフラグメント位置検索を行う必要がある。ポインタブロックがハッシュアドレスの場合、この検索はグローバルブロックインデックスを介して行わなければならず、ディスク捜索が発生する。ユニークブロックアドレスの場合は、SynchrunIDがアドレス内に含まれているため、ディスク捜索は必要ない。ブロック再配置Synchrunからスーパーノードへの静的なマッピングを用いる場合、ブロックを別のSynchrunに移動させたほうが良いケースもあり、非対称ネットワークでは負荷バランスを改善するために必要な場合がある。ポインタブロック内でハッシュアドレスを使用する場合、ブロックのSynchrunは、それを指しているポインタブロックの内容を変えることなく、変更されることがある。一方、ユニークブロックアドレスを使用する場合、再配置されたブロックを指すすべてのポインタブロックを更新しなければならない。ポインタブロックに保存されているアドレスはポインタブロックのハッシュ値の計算に含まれているため、更新した場合は、ブロックツリーのルートまでこれを伝える必要がある。ハッシュ検索の要件ハッシュアドレスによるブロックの読出しは、グローバルブロックインデックスに存在する変換に依存する。これがブロックを読み出す唯一の方法である場合、システムは、ブロック書込み処理が完了する前にGBIの更新に成功したことを保証しなければならない。これにより、ブロック書込み処理のレイテンシが増えるか、またはハッシュリースの持続性が要求される。システム回復システムに、構成上耐えられる以上の障害が発生した場合、読出し不能になるブロックが出てくる可能性がある。重複排除により、読出し不能のブロックを含むすべてのファイルシステムのスナップショットが影響を受ける。多くの場合、消失したデータもオリジナルのシステム内に存在し、次のバックアップ時にシステムに書き込まれる。そのブロックは、同じハッシュアドレスで新たなSynchrunに再び保存される。ポインタブロックに、ユニークブロックアドレスではなくハッシュアドレスが含まれている場合、この新たなブロックは、当初は読出し不能のブロックを指していた古いファイルシステムを読み出す際にも使用されることがある。事実上、失ったブロックを再度書き込むことで、システムは自動的に回復すると思われる。ヒントhintを持つポインタブロックポインタブロック内の各ポインタ用のハッシュアドレスとユニークブロックアドレスとを保存することで、ハッシュアドレスの利点ブロック再配置、システム回復とユニークブロックアドレスの利点より良いランダム読出し性能、ハッシュ検索に関する緩やかな要件とを組み合わせることができる。ハッシュアドレスは信頼性がありポインタブロックのハッシュ値にしか影響を与えない。ユニークブロックアドレスはヒントであり、ヒントが最新のものである場合にグローバルブロックインデックスの更新を回避するために使用される。ヒントは陳腐化することがあり指されたブロックの位置が変わったか、または読出し不能になった場合、その場合にヒントはゆっくり更新される。このアプローチの不都合な点は、ほとんどの記憶容量がポインタブロック用に必要となることである。ユニークなブロックの書込み性能上記で説明した通り、バックアップシステムでは読出しよりも書込みの方が多く行われ、このシステムを実現可能にするためには高い書込みスループットが不可欠である。本願で提案するアーキテクチャでは、ユニークなデータのすべてのストリームが、当初書き込まれるときにSNCDataディスクを越えて分散化される。一方、ハッシュベースのブロック分散を行うシステムでは、書込みはすべてのディスクに渡って均等に展開される。したがって、本願が提案するシステムが提供する単一ストリーム書込みスループットは非常に低い。しかし、上記に記載した通り、一般的に1つのクライアントシステムがそのような高いスループットを利用することはできないため、我々はこの制限は重要ではないと認識している。負荷バランス大規模なシステムでは、一般的に複数のストリームが同時に書き込まれる。Synchrunは、各ストリームに対してランダムにかつ独立して割り当てられる。そのため、同じスーパーノードが複数のSynchrunのホストとして選択されることがあり、いくつかのストリームが1つのストレージノードのスループットを共有しなければならないことがある。このような負荷のアンバランスは、Synchrun割当てアルゴリズムにおいて複数のランダムな選択を使用すれば緩和できる。新たなスーパーノードを選択する場合、ランダムに選択されたd個のスーパーノードに対してクエリーを送信し、アクティブに書き込まれたStreamrunの数が最も少ないスーパーノードを選択する。複数のランダムな選択を用いることで、ランダム化された負荷バランスを著しく改善することができることが示される。図2及び図3は、システムのサイズの拡大に伴う負荷のアンバランスが書込み帯域幅に与える影響を示している。様々な数のスーパーノードと割当てクエリーに関して、n個のStreamrunのn個のスーパーノードへの割り当てをシミュレートした。なお、スーパーノードの数は常にシステムのサイズに比例する。図2は1つのスーパーノードに割り当てられるStreamrunの最大数の平均を示している。予想した通り、割当てクエリーを1つ追加しただけで、スーパーノードに含まれるStreamrunの最大数が大きく減少する。しかし、クエリーが多くなっても、複数のアクティブなStreamrunを含むスーパーノードが発見される可能性は高い。Streamrunがそのようなスーパーノードに割り当てられたストリームは、そのStreamrunを使い果たして新たなものが割り当てられるまで、書込みスループットが低下したままとなる。しかし、図3を参照すると、個々のストリームはいくらか遅延するものの、総合的な書込み帯域幅に対して負荷のアンバランスが与える影響は大きくないことを示している。書込み帯域幅は、少なくとも1つのStreamrunを割り当てられたスーパーノードの数を数えることで計算された1つのスーパーノードのスループットを飽和させるには1つのストリームで十分であるとの前提に基づく。非常に大規模なシステムでも、10のクエリーの場合、達成された帯域幅は最大値の5以内であった。ストリームのソートハッシュベースの分散を行うシステムにおいて、異なるストリームに属する書込みは同じストレージコンテナ内で多重化される。同じストリームが一緒に読み出されることはないと思われるため、このような多重化されたコンテナを読み出すのは効率が悪い。その理由は、不要なデータストリームを飛ばす必要があるからである。非特許文献1では、ストリームのソートを用いて、ストリームからのデータを合体して大きなチャンクにすることによって、将来の読出しを改善する。しかし、ストリームのソートは、書込み処理中にインラインで実行した場合はレイテンシが増加する。または、バックグラウンド処理で、すべてのデータをストリームがソートされた順序に書き直す必要がある。本願が提案するアーキテクチャでは、ストリーム毎に個別のStreamrunが作成されるため、異なるストリームからのデータをまとめて多重化することはない。読出しスループット本願で提案するアーキテクチャの主な目的は、ストリーム局所性の保存性を高めて大規模なシステムにおける読出しスループットを改善することである。ストリーム局所性の保存正確な重複排除処理を行うストレージシステムでは、当然ストリーム局所性が低下する。本願の焦点は、ストレージシステムの内部データ構成に起因する更なる性能の低下であるため、ユニークなデータブロックのストリームに関して局所性がどのように保存されるかを分析することで、重複排除の影響を取り除く。まず、入力ストリームをSynchrunのサイズに分割して、その各部分を順次ディスク上に置く。1つのSynchrunの想定サイズは数メガバイトから数十メガバイトの範囲であるため、入力ストリームの順次読込みは、保存ディスクをほんのわずかしか探さなくてよい。削除処理では、Synchrunsの中央からブロックを削除することができる。そしてガーベジコレクションによりSynchrunのサイズが縮小される。Synchrunのサイズが順次読出しの性能に多大な影響を与えるほど縮小する前に、上記で説明したように連続するSynchrunを連結する。連結により、Streamrunのサイズまでデータの局所性を保存する。Streamrunのサイズになったデータストリームの部分からあまりに多くのブロックが削除され、Synchrunの半分しか残らなくなると、連結は、別のStreamrunに属するSynchrunを統合し始める。そのため、オリジナルのストリームの局所性の保存に関しては有効性がなくなる。システムが成長すると、使用容量のバランスを保つために既存のデータが新たなノードに転送される。しかし、上述したように、Streamrunは常に1つのユニットとして一緒に保存される。したがって、新たなストレージノードが追加されてもストリームの局所性は影響を受けない。ハッシュベースのブロック分散との比較ハッシュベースのブロック分散および本願で提案するストリーム毎のブロック分散のいずれにおいても、読出しスループットは、書込み時および読出し時の双方でのアクセスパターンに大きく依存する。この2つのアーキテクチャ間のトレードオフをよりわかりやすくするために、いくつかの典型的なシナリオでこれらのシステムがどのように機能するかを分析する。単一ストリームの書込み、単一ストリームの読出し大規模なシステムではまずあり得ないと思われる最もシンプルなシナリオは、当初保存されたときに唯一書き込まれたストリームであった1つのストリームを、順次読み出すものである。この場合、ハッシュベースの分散は非常に効率的であり、すべてのストレージノードの混合スループットを提供する。本願で提案するアーキテクチャのパフォーマンスも十分に良好で、SNCDataストレージノードの並列性を有し、単一のクライアントの需要を十分満たすと思われる。複数ストリームの書込み、単一ストリームの読出し同時に複数のストリームが書き込まれ、後にその内の1つしか読み出されない状況は、実際のシステムでは間違いなく極めて一般的である。このような状況は、共有バックアップ時間に複数のシステムのバックアップを平行して行い、その後、その内の1つだけに障害が発生してバックアップから回復させる場合によく発生する。この状況は、ハッシュベースの分散を用いるシステムにはあまり好ましくない。すべてのストリームに属するブロックが同じディスク上コンテナに均等に分散されているため、1つのストリームだけを読み出すのに、他のブロックを探索するかまたは飛ばすかのどちらかが必要となる。非特許文献1では、ブロックが書込みバッファに提供されるのを待っているときに、バックグラウンドおよび書込み中はインラインの両方でストリームIDにしたがってコンテナ内でブロックをソートすることにより、この問題の解決を図っている。このようなストリームのソートの効果はコンテナのサイズによって制限される。本願が提案するアーキテクチャは、異なるデータストリームからの書込みが独自のコンテナにソートされるため、この問題の影響を受けない。このケースでの読出しスループットは、やはりSNCDataストレージノードの結合スループットである。複数ストリームの読出し複数のバックアップシステムに大規模な障害が発生した後、複数のバックアップが画像を平行して復元させる場合に、複数のストリームを同時に読み出すことがある。しかし高度に断片化された重複排除されたストリームを読み出す際には、1つの外部読出しストリームでもシステムにとっては複数のストリームを読み出すのと同じようなものである。ハッシュベースで分散されたシステムでは、すべてのストレージノードが各ストリームの縮小バージョンを効果的に保存している。ストリーム全体を再形成するためには、これらの縮小化された各ストリームを並行して読み出さなければならない。すべてのストレージノードが、システム内の読み出される各ストリームからのアクセスに対応しなければならない。ストレージノードおよびアクセスノードの両方とも、読出しを一時格納するための固定量のメモリを備えているため、同時に読み出すストリームの数が増えればより、小さなディスク読出しサイズを使用しなければならない。小さなサイズのディスク読出しを使用するとスループットが大幅に減少し、最終的には順次的な読出しがランダムなブロック読出しに劣化する。本願で提案するシステムでは、各データストリームはほんのわずかなストレージノード群に対してのみ分散化されているため、同じ問題に直面することはない。しかし、ハッシュベースの分散とは異なり、不完全な負荷バランスの問題がある。小さなストレージノード群から多数のストリームを読み出すことは可能だが、他のストレージノードがアイドル状態になる。いくつかのオリジナルのフラグメントの代わりに冗長フラグメントを読み出す方法を採用すれば、冗長符号化アルゴリズムによりCPUの消費が増加するが、それを犠牲にして負荷バランスを改善することができる。それでも、多数のストリームを同時に読み出す場合は、ハッシュベースのブロック分散を用いるよりも読出し性能は著しく高くなる。グローバルブロックインデックスの更新上記で説明したように、グローバルブロックインデックスはハッシュ値をブロックのユニークブロックアドレスSynchrunIdとsynchrun内のシーケンス数にマッピングする。この決定により、データ位置が変わった場合またはガーベジコレクションが実行された場合でも、グローバルブロックインデックスの変換を変更する必要はなく、ブロックアドレスはそのブロックが削除されるまで有効である。別の解決策としては、SCCIdおよびそのSCC内のブロックのオフセットを維持する方法がある。これにより、SynchrunId、sequencenumberからSCCId、Offsetへの変換を行わないことでランダムな読出しの性能が改善される可能性がある。しかし、SCC内のフラグメントのオフセット領域再利用、連結を変更するバックグラウンド処理の後でGBI変換を更新する必要があるため、インデックスノードに対する負荷が増大する。非対称ネットワーク対応ハッシュベースの分散は、データストリームのブロックをすべてのストレージノードに均等に展開する。そのため、アクセスノードは各ストレージノードへ同じ量のデータを送信する必要がある。データストリームを書き込む帯域幅は、アクセスノードとストレージノードとの間の最も遅いネットワークリンクによって制限される。本願で提案するアーキテクチャでは、アクセスノードはスーパーノードおよびデータを保存するストレージノードの選択に関して、より自由度が高い。この特徴は非対象ネットワークにおける書込み性能の改善に役立つ。上記で説明したように、本願では、ネットワークがノード群から構成されると仮定している。1つのグループ内のノードは、二地点間のスループットが高い状態で通信を行うことができる。一方、グループ間のリンクでは1ノード当たりのスループットが低下する。アクセスノードは、自身のグループ内のストレージノード上にのみStreamrunを割り当てるようにして、書込みにグループ間のリンクを使用しない。Streamrunはストレージノードに直接割り当てられるのではなくスーパーノードに割り当てられるため、データFPNキー領域は、データFPN内のプレフィックスの範囲が1つのグループ群に対応するように分割される。スーパーノードが、あるノード群に割り当てられると、そのコンポーネントはすべてそのグループに属するストレージノード上に保持される。Streamrun割当アルゴリズムは、同じグループ内のスーパーノードのみをアクセスノードとみなすように修正される。選択されたスーパーノードがフルの場合のみ、ノード群の制約を受けない通常の割り当てが行われる。このグループ特定割当ポリシは、速度の遅いリンクを介した帯域幅集約型データ転送を排除する。グループシステムの容量を使い果たさない限り、ブロックの書込みはアクセスノードと同じグループのストレージノードによってのみ行われる。この場合でもGBIクエリーはすべてのインデックスノードに均等に送信されるが、これらはそれほど帯域幅を消費しない。同様に、重複ブロックを書き込む際に変換キャッシュによって行われるSCCインデックスのプリフェッチは、重複が別のグループに保存されている場合はグループ間帯域幅を使用することができる。しかし、SCCインデックスはデータのサイズに比べて小さいため、これらはグループ間スループットを超えることはない。障害後のデータ再構築も、スーパーノードのコンポーネントがすべて同じグループ内にあるため、それほど多くのグループ間帯域幅を必要としない。しかし、このポリシはいくつかのトレードオフを伴う。容量のバランス保持は1つのノード群内でのみ行われる。いくつかのクライアントが他のクライアントよりも多くのデータを書き込んだ場合、それらのグループ内のフリー領域は他のグループよりも早く使い果たされる。同じグループ内のストレージノードの障害が独立したものでなければ、システムの冗長性が損なわれることがある。その理由は、1つのスーパーノードのすべてのコンポーネントは同じノード群に含まれるからである。新たな書込みがグループ間のネットワークのトラフィックを生成することはないが、読出しの効果は重複排除パターンに依存する。例えば、あるアクセスノードが、異なるグループに接続された他のアクセスノードが既に書き込んだデータを書き込んだ場合、そのデータはオリジナルのグループにしか保存されない。2番目のアクセスノードからのデータを読み出すには、オリジナルのグループからすべてのデータを転送しなければならない。その場合、データがすべてのスーパーノードに均等に展開されている場合よりも、読出し性能が悪化する場合がある。最悪のケースでは読出しスループットが低下するが、非対称ネットワークの展開は、ネットワークのコストを最も低くすることを考慮するなら意味がある、というのが本願での主張である。その理由は、第1に、1つのネットワークグループ内のアクセスノードを介して同じクライアントのシステムが常にバックアップされる場合、そのシステムにしか存在しないユニークなデータは、そのグループに保存される可能性が高い。このデータを高いスループットで読み出すことができる。第2に、障害が発生したクライアントのシステムを復旧させる場合、通常はいくつかのバックアップ画像のみを読み出す。いくつかのストリームを同時に読み出す場合、グループ間のリンクは、データが他のノード群に保存されていたとしてもボトルネックにならないよう高速でなければならない。最後に、リモートのノード群からデータを読み出すには、同時書込みを伴うグループ間のネットワークスループットを競う必要がない。レイテンシとマローダーに対する復元力本願で提案するアーキテクチャは、ハッシュベースの分散よりもブロックの書込みに対してレイテンシが増大する可能性がある。その理由は、グローバルブロックインデックスの問い合わせを行うのに余分なネットワークのホップが必要だからである。また、複数の比較的速度の遅いクライアントに対して、より高い書込みレイテンシを持つ可能性もある。順次的な書込み用の、より大きなバッファを蓄積するには、より長い時間が必要であるが、これは異なるストリームのブロックを混合しないからである。均等にハッシュベースの分散を行うシステムでは、すべてのストリームのブロックを同じ書込みバッファに蓄積して順次ディスクにフラッシュする。一方、ハッシュベースの分散システムで必要なインラインでのストリームのソートは書込みレイテンシを大幅に増加させるが、これは本システムでは必要ない。また、本願で提案するアーキテクチャはマローダー、つまり障害を宣言されない速さで機能するが他よりは動作の遅いノード、に対する復元力が高い。このアーキテクチャでは、特定のノードにアクセスするストリームのみが、そのノードの遅さまたは障害の影響を受ける。ハッシュベースの分散では、システム全体のパフォーマンスがそのネットワーク内で最も遅いノードによって決定される。1つのストリームの書込み要求に対応するのは幾つかのストレージノードのみであるため、ストリーム内の未処理データの明白なフラッシュを要求してレイテンシを下げることが可能である。これは、例えば、提供されたすべてのデータが書き込まれるまでそれ以降の処理を阻止することが多い、クライアントからのNFS同期要求を処理する場合に役立つ。アクセスノードは、明白な優先順位の高いフラッシュを要求することができる。なぜなら、書き込みは、1つのストリームによって一度に1つのSynchrunにしか送信されないからである。ハッシュベースの分散システムではすべてのストレージノードに対する要求を送信する必要があるため、これは実現不可能である。Synchrunからスーパーノードへの静的割当てvs動的割当て本願で提示する解決策では、Synchrunは静的にスーパーノードに割り当てられる。この割当てはSynchrunのIDのみに基づき、SynchrunのIDが変更されなければ変わることはない。Synchrunからスーパーノードへの動的なマッピングを検討することもできる。その場合は、Synchrunのデータが保存されているストレージノードを検索しなければならず、SynchrunのIDによって静的に決定されることはない。このような動的マッピングの利点は、個々のスーパーノードが、システム内の変更に合わせて位置を変えられることである。例えば、非対称ネットワークでは、Synchrunは、最も頻繁にアクセスしてくるアクセスノードの近くに移動することができる。本願では、提案するシステム内に追加のマッピングを行わないことに決定した。その理由は、追加のマッピングを行うためにはSynchrunからストレージノードへの検索のために追加のネットワークホップを導入することになり、読出しレイテンシの増加につながるからである。結論本願では、効果的な拡張性を持つ高性能なインライン重複排除処理のための新たなアーキテクチャを提案した。このアーキテクチャでは、正確な重複排除処理に使用するDHTベースのグローバルブロックインデックスを、ストリーム認識型の順次的なデータ配置と区別している。上述したように、本願が提案するアーキテクチャは、大規模システムにおいて同時に読み出すストリームの数がシステムの規模に伴い増加する場合に、既存の解決策と比べて読出し性能が改善される。このシステムは、データの削除やノードの追加がある場合でもストリームの局所性を保存する一方、ストレージノード間の容量バランスを良好な状態に保つ。また、複数のストリームを同時に書き込む場合に、異なるストリームからのブロックをインターリーブすることがない。対称ネットワークでは、ハッシュベースの分散の方が書込みスループットはわずかに高いが、読出し性能にかなりのコストがかかる。本願が提案するアーキテクチャでは、読出し性能はアクセスパターンに大きく依存するものの、同時読出しがある場合でも非対称ネットワークにおける読出し性能が非常に高い。ハッシュベースでブロック分散を行う既存のシステムは、負荷バランスやホットスポットの問題がないため、小規模から中規模のシステムではより効果的である。しかし高いマルチストリーム読出しスループットが要求される大規模なシステムでは、本願の提案するアーキテクチャの方が適している。<実施形態2>本発明の第2の実施形態を、図4乃至図10を参照して説明する。図4は、システム全体の構成を示すブロック図である。図5は、ストレージシステムの概略を示すブロック図であり、図6は、構成を示す機能ブロック図である。図7乃至図10は、ストレージシステムの動作を説明するための説明図である。ここで、本実施形態では、ストレージシステムがHYDRAstorといったシステムであり、複数台のサーバコンピュータが接続されて構成されている場合を説明する。但し、本発明におけるストレージシステムは、複数台のコンピュータにて構成されることに限定されず、1台のコンピュータで構成されていてもよい。図4に示すように、本発明におけるストレージシステム10は、ネットワークNを介してバックアップ処理を制御するバックアップシステム11に接続している。そして、バックアップシステム11は、ネットワークNを介して接続されたバックアップ対象装置12に格納されているバックアップ対象データ記憶対象データを取得し、ストレージシステム10に対して記憶するよう要求する。これにより、ストレージシステム10は、記憶要求されたバックアップ対象データをバックアップ用に記憶する。そして、図5に示すように、本実施形態におけるストレージシステム10は、複数のサーバコンピュータが接続された構成を採っている。具体的に、ストレージシステム10は、ストレージシステム10自体における記憶再生動作を制御するサーバコンピュータであるアクセスノード10A第一サーバと、データを格納する記憶装置を備えたサーバコンピュータであるストレージノード10B第二サーバと、データの格納先を表すインデックスデータを記憶するインデックスノード10C第三サーバと、を備えている。なお、アクセスノード10A、ストレージノード10B、インデックスノード10Cの数は、図5に示したものに限定されず、さらに多くの各ノード10A,10B,10Cが接続されて構成されていてもよい。さらに、本実施形態におけるストレージシステム10は、記憶対象データを分割して、複数の記憶装置であるストレージノード10Bに分散して記憶する機能を有する。また、ストレージシステム10は、記憶対象データブロックデータの特徴を表す固有のハッシュ値を用いて、同一内容のデータが既に記憶されているか否かを調べ、既に記憶されているデータについては、かかるデータの格納場所を参照することで重複記憶を排除する、という機能を有する。具体的な記憶処理については、後に詳述する。図6に、ストレージシステム10の構成を示す。この図に示すように、ストレージシステム10を構成するアクセスノード10Aは、記憶対象となるデータの記憶再生を制御するデータ格納制御部21を備えている。なお、上記データ格納制御部21は、図5に示したアクセスノード10Aが備えているCPUCentralProcessingUnitなどの演算装置にプログラムが組み込まれることで構成されている。ここで、上記プログラムは、例えば、CD-ROMなどの記憶媒体に格納された状態でストレージシステム10に提供される。あるいは、上記プログラムは、ネットワーク上の他のサーバコンピュータの記憶装置に記憶され、当該他のサーバコンピュータからネットワークを介してストレージシステム10に提供されてもよい。以下、上記データ格納制御部21の構成について詳述する。まず、データ格納制御部21は、バックアップ対象データAであるストリームデータの入力を受けると、図7に示すように、当該バックアップ対象データAを、所定容量例えば、64KBのブロックデータDに分割する。そして、このブロックデータDのデータ内容に基づいて、当該データ内容を代表する固有のハッシュ値H特徴データを算出する。例えば、ハッシュ値Hは、予め設定されたハッシュ関数を用いて、ブロックデータDのデータ内容から算出する。そして、データ格納制御部21は、新たに記憶するブロックデータDが既にストレージノード10Bつまり記憶装置に記憶されていないかといった重複判定を行う。このとき、後述するように、アクセスノード1AにSCCインデックスB2が近頃読み込まれている場合には、いずれかのSCCインデックスB2内にブロックデータDのハッシュ値が存在するか調べる。そして、いずれのSCCインデックスB2内にもブロックデータDのハッシュ値が存在しない場合には、データ格納制御部21は、さらにインデックスノード10Cに記憶されているグローバルブロックインデックスC1内に、新たに記憶するブロックデータDのハッシュ値が存在するか調べる。また、アクセスノード1AにSCCインデックスB2が読み込まれていない場合にも、インデックスノード10Cに記憶されているグローバルブロックインデックスC1内に、新たに記憶するブロックデータDのハッシュ値が存在するか調べる。データ格納制御部21は、インデックスノード10Cに記憶されているグローバルブロックインデックスC1内に、新たに記憶するブロックデータDのハッシュ値が存在しない場合には、ストリームデータのブロックデータを、ストレージノード10Bに新規に保存する。具体的に、データ格納制御部21にてブロックデータDをストレージノード10Bに記憶するときの様子を、図7及び図8を参照して説明する。データ格納制御部21は、バックアップ対象データAであるデータストリームを分割したブロックデータD1等を、順次、特定のストレージノード10B内に形成されたSCCファイルB1に格納する。このとき、使用されている記憶容量が最も少なかったり、オープンとなっているSCCファイルB1が存在するなどのストレージノード10Bを、ブロックデータD1等を格納する特定のストレージノード10Bとする。但し、ブロックデータD1等を格納するストレージノード10Bは、他の方法により決定してもよい。そして、データ格納制御部21は、格納するデータストリーム内で連続する複数のブロックデータD1,D2,D3等を、SCCファイルB1内に格納する。このとき、データ格納制御部21は、SCCファイルB1内における各ブロックデータD1,D2,D3等の格納位置を表す格納位置情報と、格納した各ブロックデータD1,D2,D3のハッシュ値Hとをそれぞれ関連付けて、SCCインデックスB2格納位置特定テーブルとしてブロックデータD1,D2,D3を格納したストレージノード10B内に格納しておく。また、データ格納制御部21は、各ブロックデータD1,D2,D3を格納したストレージノード10Bを特定する識別情報記憶装置識別情報であるID例えば、特定のSCCファイルB1内の特定領域を示すID図8参照と、各ブロックデータD1,D2,D3のハッシュ値とを関連付けて、グローバルブロックインデックスC1記憶装置特定テーブルとしてインデックスノード10Cに記憶しておく。なお、ここでは、ハッシュ値自体ではなく、ハッシュ値の一部とストレージノード10Bを特定するIDとを関連付けて記憶することとする。このとき、データ格納制御部21は、グローバルブロックインデックスC1を、複数存在するインデックスノード10Cに分散して記憶する。なお、ハッシュ値とIDとを分散して記憶する方法は任意である。以上のように格納することで、バックアップ対象データAの連続する複数のブロックデータD1,D2,D3等が、同一のストレージノード10Bに連続して格納されると共に、それらの格納位置を示すデータも連続してSCCインデックスB2に格納される。また、ブロックデータD1,D2,D3等が格納されたストレージノード10B特定のSCCファイルB1内の特定領域がグローバルブロックインデックスC1にて管理される。なお、上述した各ブロックデータD1,D2,D3等の記憶処理は、実際には、各ブロックデータD1,D2,D3等を、複数のストレージノード10B群スーパーノードを特定のストレージノード10Bとして分散して記憶することにより行う。ここで、ブロックデータをさらに分散して記憶するときの様子を、図7を参照して説明する。また、データ格納制御部21は、上述したように新規に記憶するブロックデータDを圧縮して、図7に示すように、複数の所定の容量のフラグメントデータに分割する。例えば、図7の符号E1~E9に示すように、9つのフラグメントデータ分割データ41に分割する。さらに、データ格納制御部21は、分割したフラグメントデータのうちいくつかが欠けた場合であっても、元となるブロックデータを復元可能なよう冗長データを生成し、上記分割したフラグメントデータ41に追加する。例えば、図7の符号E10~E12に示すように、3つのフラグメントデータ冗長データ42を追加する。これにより、9つの分割データ41と、3つの冗長データとにより構成される12個のフラグメントデータからなるデータセット40を生成する。そして、データ格納制御部21は、生成されたデータセットを構成する各フラグメントデータを、スーパーノードであるストレージノード10B群に形成された各記憶領域31に、それぞれ分散して格納する。例えば、図7に示すように、12個のフラグメントデータE1~E12を生成した場合には、12個の記憶領域31内にそれぞれ形成したデータ格納ファイルF1~F12データ格納領域に、各フラグメントデータE1~E12を1つずつそれぞれ格納する。次に、上述したデータストリームAとほぼ同一のデータ内容のバックアップ対象データA’のデータストリームが、新たな記憶対象データとして入力された場合を図9及び図10を参照して説明する。まず、バックアップ対象データA’のブロックデータD1が既にストレージノード10Bつまり記憶装置に記憶されていないかといった重複判定を行う。このとき、アクセスノード1AにSCCインデックスB2が読み込まれていないか調べ、この場合にはSCCインデックスB2が読み込まれていないので、インデックスノード10Cに記憶されているグローバルブロックインデックスC1内に、新たに記憶するブロックデータD1のハッシュ値ここでは、ハッシュ値の一部が存在するか調べる。そして、データ格納制御部21は、インデックスノード10Cに記憶されているグローバルブロックインデックスC1内に、新たに記憶するブロックデータD1のハッシュ値ハッシュ値の一部が存在する場合には、そのハッシュ値ハッシュ値の一部に対応付けられたストレージノード10B特定のSCCファイルB1の領域を特定し、そのストレージノード10B内のSCCインデックスB2を参照する。このSCCインデックスB2内に記憶されているハッシュ値と、新たに記憶するブロックデータD1のハッシュ値とを比較し、一致する場合には、SCCインデックスB2を参照してSCCファイル内B1のブロックデータの格納位置を、新たに記憶するブロックデータD1として参照する。これにより、新たに記憶するブロックデータD1自体を格納することなく、重複記憶を排除することができる。これと同時に、データ格納制御部21は、上述したように参照したストレージノード10Bに記憶されているSCCインデックスB2を、アクセスノード10Aに読み出す。そして、データ格納制御部21は、バックアップ対象データA’の後続のブロックデータD2,D3については、当該ブロックデータD2,D3のハッシュ値と、アクセスノード10Aに読み出されたSCCインデックスB2内に記憶されているハッシュ値とを比較し、一致する場合には、SCCインデックスB2を参照してSCCファイル内B1のブロックデータの格納位置を、新たに記憶するブロックデータD2,D3として参照する。これにより、新たに記憶するブロックデータD2,D3自体を格納することなく重複記憶を排除することができ、さらに、高速に重複判定を行うことができる。以上のように、本発明によると、複数のストレージノード10Bを備え、かかるストレージノード間の容量バランスを良好に保つべく分散してデータを記憶できると共に、記憶対象データを分割した連続する所定量のブロックデータを特定のインデックスノード10B群スーパーノードに局所的に保存できる。このため、重複排除処理を高速化することができる。さらに、データを読み出す処理も高速化することができる。<付記>上記実施形態の一部又は全部は、以下の付記のようにも記載されうる。以下、本発明におけるストレージシステム100図11参照、プログラムを記憶した記憶媒体、データ格納方法の構成の概略を説明する。但し、本発明は、以下の構成に限定されない。付記1記憶対象データを分割した複数のブロックデータを複数の記憶装置110に分散して記憶すると共に、記憶装置110に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置110に格納する場合に、当該記憶装置110に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部101を備え、前記データ格納制御部101は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置110のうち特定の記憶装置110に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置110内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置110を識別する記憶装置識別情報と当該特定の記憶装置110に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、ストレージシステム100。付記2付記1に記載のストレージシステムであって、前記データ格納制御部は、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、ストレージシステム。付記3付記2に記載のストレージシステムであって、前記データ格納制御部は、前記特定の記憶装置から読み出した前記格納位置特定テーブルに基づいて、新たに記憶する記憶対象データを分割したブロックデータが記憶装置に既に記憶されているか否かの判定を行う、ストレージシステム。付記4付記3に記載のストレージシステムであって、前記データ格納制御部は、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データが前記特定の記憶装置から読み出した前記格納位置特定テーブル内に存在しない場合に、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、ストレージシステム。付記5付記1に記載のストレージシステムであって、複数の記憶装置に対する記憶対象データの記憶動作を制御する少なくとも1つの第一サーバと、前記複数の記憶装置を構成する複数の第二サーバと、を備え、前記データ格納制御部は、前記第二サーバから前記第一サーバに前記格納位置特定テーブルを読み出す、ストレージシステム。付記6付記5に記載のストレージシステムであって、前記記憶装置特定テーブルを記憶する複数の第三サーバを備え、前記データ格納制御部は、前記記憶装置特定テーブルを前記複数の第三サーバに分散して記憶する、ストレージシステム。付記7情報処理装置に、記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納制御部を実現させると共に、前記データ格納制御部は、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、ことを実現させるためのプログラムを記憶した記憶媒体。付記8付記7に記載のプログラムを記憶した記憶媒体であって、前記データ格納制御部は、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、プログラムを記憶した記憶媒体。付記9記憶対象データを分割した複数のブロックデータを複数の記憶装置に分散して記憶すると共に、記憶装置に既に記憶されている記憶対象データと同一のデータ内容の他の記憶対象データを記憶装置に格納する場合に、当該記憶装置に既に記憶されている記憶対象データを前記他の記憶対象データとして参照して重複記憶排除を行うデータ格納方法であって、記憶対象データを分割した当該記憶対象データ内で連続する複数のブロックデータを、前記複数の記憶装置のうち特定の記憶装置に記憶すると共に、当該ブロックデータのデータ内容に基づく特徴データと当該ブロックデータの前記特定の記憶装置内における格納位置を表す格納位置情報とを関連付けて当該特定の記憶装置内に格納位置特定テーブルとして記憶し、前記特定の記憶装置を識別する記憶装置識別情報と当該特定の記憶装置に格納された前記ブロックデータの前記特徴データとを関連付けて記憶装置特定テーブルとして記憶する、データ格納方法。付記10付記9に記載のデータ格納方法であって、新たに記憶する記憶対象データを分割したブロックデータの前記特徴データに基づいて前記記憶装置特定テーブルを参照して当該ブロックデータの前記特徴データが含まれる前記格納位置特定テーブルが記憶されている前記特定の記憶装置を特定して、当該特定の記憶装置から前記格納位置特定テーブルを読み出す、データ格納方法。"