分散データを再構築するためのシステム
他のファイル共有の一部または全てと組み合わせた場合以外では、各ファイル共有のデータが、それ自体では利用可能性がより低い、または認識可能性が低い、または完全に利用不可能である、または完全に認識不可能であるように、格納されるオリジナルデータファイルが、ある形式の情報分散アルゴリズムを使用して、多数のファイル「スライス」またはサブセットに分散される、デジタルデータファイルのストレージシステムを開示する。これらのファイル共有は、分散されたストレージグリッド内において分散されたファイル共有［ボリューム］として、別々のデジタルデータストレージデバイスに格納される。転送される際に分散されたファイル共有が破損した場合、分散されたストレージグリッド内のプロセスは、再構築リスト［６６］で再生成する必要のある分散されたデータ共有を指定する。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の参照）
本願は、２００５年９月３０日出願の共願の同時係属出願米国出願第１１／２４１，５５５号の一部継続出願である。
【０００２】
（発明の背景）
（１．発明の分野）
本発明は、情報分散アルゴリズムを使用してデータを格納するための分散データファイルストレージシステムおよび方法に関し、より詳細には、分散データを再構築するためのシステムおよび方法に関する。情報分散グリッドにおいて、分散データ（オリジナルの組のデータおよび／または符号化されたデータの複数のサブセット）を、１つ以上の位置の、複数のデータストレージデバイス上に格納することにより、その他のデジタルデータストレージデバイスからの分散データと組み合わされる場合以外では、各ストレージデバイス上の分散データは、認識不可能かつ利用不可能である。分散データが、常に完全に動作可能ではない情報分散グリッド上に転送または格納される状況に対処するために、本発明は、リソースの利用停止（ｏｕｔａｇｅ）による分散データの再構築だけでなく、情報分散グリッドにおける一時的または永続的なリソースの利用停止のいずれかに対処するための能力を提供する。
【背景技術】
【０００３】
（２．先行技術の記載）
データの格納のために、様々なデータストレージシステムが公知である。通常、こうしたデータストレージシステムは、例えば、単一のデータ領域（すなわち、単一のデジタルデータストレージデバイス）上に、特定のデータセットに関連付けられた全てのデータ（特定のユーザの全データ、特定のソフトウェアアプリケーションに関連付けられた全データ、または特定のファイル内の全データ等）を格納する。クリティカルなデータは、まず、冗長デジタルデータストレージデバイスに格納される。従って、あるデジタルデータストレージデバイスに障害が存在する場合、他のデジタルデータストレージデバイス上でデータの完全なコピーが利用可能である。冗長デジタルデータストレージデバイスを有するこうしたシステムの例は、本明細書に参照として援用される、特許文献１、特許文献２、および特許文献３に開示されている。こうした冗長デジタルデータストレージシステムは比較的信頼性が高いが、こうしたシステムには他の問題が存在する。第１に、こうしたシステムは、デジタルデータストレージのコストを、実質的に２倍以上に増加させてしまう。第２に、こうした冗長デジタルデータストレージシステムの全データを１つの場所に保管することにより、データを、不正（ｕｎａｕｔｈｏｒｉｚｅｄ）アクセスに対して脆弱にしてしまう。
【０００４】
セキュリティおよび結果としてデータストレージシステムの信頼性を向上させるために、性能の向上または容量制限に関する理由のためだけではなく、本明細書に参照として援用される特許文献４に記載されているように、２つ以上のストレージデバイス（ハードドライブ、または磁気テープあるいはいわゆる「メモリスティック」等のリムーバル媒体等）に、データが格納され得る。例えば、使用頻度の少ない過去のデータは磁気テープに格納され得る一方で、データベースの最近のデータはハードドライブに格納され得る。別の例は、単一のハードドライブ上に格納するにはサイズが大きすぎる単一のファイルからのデータを、２つのハードドライブへの格納することである。これらの場合の各々において、各データストレージデバイスに格納されるデータサブセットがオリジナルデータ全てを含むわけではないが、一部の利用可能な情報を提供するために使用され得るデータの概して連続的な部分は含んでいる。例えば、格納されるオリジナルデータが、以下の文の文字列であるとする。
Ｔｈｅ ｑｕｉｃｋ ｂｒｏｗｎ ｆｏｘ ｊｕｍｐｅｄ ｏｖｅｒ ｔｈｅ ｌａｚｙ ｄｏｇ．
そのデータは２つの異なるデータストレージデバイスに格納され、これらのデバイスの一方または両方が利用可能な情報を含むことになる。例えば、その４５文字の文字列のうちの最初の２０文字が１つのデータストレージデバイスに格納された場合、残りの２５文字は第２のデータストレージデバイスに格納され、センテンスは以下：
Ｔｈｅ ｑｕｉｃｋ ｆｏｘ ｊｕｍｐｅｄ（第１のストレージデバイスに格納）
ｏｖｅｒ ｔｈｅ ｌａｚｙ ｂｒｏｗｎ ｄｏｇ．（第２のストレージデバイスに格納）
のように格納される。
【０００５】
それぞれの場合において、各デバイスに格納されるデータはオリジナルデータの完全なコピーではないが、各デバイスに格納されるデータサブセットの各々はいくつかの利用可能な情報を提供する。
【０００６】
典型的には、ハードドライブ等のデバイス上のデータストレージの実際のビットパターンは、ハードドライブセクタまたはメモリセグメント等の、ファイルタイプ、ファイルシステムおよびストレージ構造を表すための追加の値で構築される。特定のファイルシステムおよび特定のストレージ構造を使用する、特定のファイルタイプのデータを構築するために使用される技術がよく知られており、これらの技術に精通した個人が物理的媒体におけるビットパターンからソースデータを識別することが可能である。
【０００７】
格納されたデータを認証ユーザのみに利用可能にすることを確実に行うために、多くの場合、ＤＥＳ、ＡＥＳまたはその他のいくつかの公知の暗号化技術の１つを使用して、暗号化形式でデータが格納される。これらの暗号化技術は、理想的には認証ユーザまたは認証プロセスにのみ知られている数学キーを必要とするある符号化形式で、データを格納する。こうした暗号化技術を「解読」するのは困難であるが、解読されている暗号化技術の場合は、こうしたデータストレージシステム上のデータを不正アクセスに対して脆弱にすることがわかっている。
【０００８】
暗号化を使用してデータを安全にするだけでなく、情報分散アルゴリズムを使用してデータストレージのセキュリティを向上させるいくつかの方法が開発されており、例えば、本明細書に参照として援用される、特許文献５および特許文献６に開示されている。こうした情報分散アルゴリズムは、オリジナルデータを複数のデータサブセットに「スライス（ｓｌｉｃｅ）」し、異なるストレージノード（すなわち、異なるデジタルデータストレージデバイス）へこれらのサブセットに分散させるために使用される。オリジナルデータセットを、そのオリジナルデータが全く含まれていない複数のデータセットに分散させるために、情報分散アルゴリズムも使用できる。個別には、各データサブセットまたはスライスはオリジナルデータを再生成するための十分な情報を含んでいないが、閾値数の（すなわち、オリジナルサブセットの数より少ない）サブセットが利用可能である場合、全てのオリジナルデータを正確に生成することができる。
【０００９】
データストレージシステムにおけるこうした情報分散アルゴリズムの利用は、様々な業界紙にも記載されている。例えば、非特許文献１による、「Ｈｏｗ ｔｏ Ｓｈａｒｅ ａ Ｓｅｃｒｅｔ」は、多項式補間に基づいて、暗号鍵等の秘密を共有するスキームについて記載している。別の業界紙、すなわち、非特許文献２の「Ｅｆｆｉｃｉｅｎｔ Ｄｉｓｐｅｒｓａｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ ｆｏｒ Ｓｅｃｕｒｉｔｙ，Ｌｏａｄ Ｂａｌａｎｃｉｎｇ，ａｎｄ Ｆａｕｌｔ Ｔｏｌｅｒａｎｃｅ」も、情報分散アルゴリズムを使用した情報分散の方法について記載している。
【特許文献１】米国特許第５，８９０，１５６号明細書
【特許文献２】米国特許第６，０５８，４５４号明細書
【特許文献３】米国特許第６，４１８，５３９号明細書
【特許文献４】米国特許第６，１２８，２７７号明細書
【特許文献５】米国特許第６，８２６，７１１号明細書
【特許文献６】米国特許出願公開第２００５／０１４４３８２号明細書
【非特許文献１】Ａ．Ｓｈａｍｉｒ，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ，Ｖｏｌ．２２，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ，１９７９
【非特許文献２】Ｍ． Ｒａｂｉｎ、Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｍａｃｈｉｎｅｒｙ，Ｖｏｌ．３６，Ｎｏ．２，Ａｐｒｉｌ １９８９，３３５―３４８ページ
【発明の開示】
【発明が解決しようとする課題】
【００１０】
残念ながら、こうした方法および他の公知の情報分散方法は、計算処理能力的に負担が大きいため、企業、消費者および他の組織で今日広く使用されているタイプのコンピュータで使用している一般的な大容量データストレージにとって、実用的でない。このため、計算処理能力的に負担の大きいアルゴリズムを使用する必要のないデータを、確実かつ安全に保護できるデータストレージシステムが求められている。
【課題を解決するための手段】
【００１１】
（発明の概要）
つまり、本発明は、その他のファイル共有のいくつかまたは全てと組み合わせた場合を除き、各ファイル共有のデータが、それ自体では利用可能性がより低い、または認識可能性が低い、または完全に利用不可能である、または完全に認識不可能であるように、格納されるオリジナルデータファイルが、ある形式の情報分散アルゴリズムを使用して、多数のファイル「スライス」またはサブセットに分散される、デジタルデータファイルのストレージシステムに関する。こうしたファイル共有は、プライバシーおよびセキュリティを向上させるために、個別のデジタルデータストレージデバイスに格納される。分散されたファイル共有は、分散されたストレージ位置のグリッド上に転送または格納されるため、様々なグリッドリソースは、動作不可能になり得るか、または最適基準未満で動作し得る。分散したファイル共有が利用不可能な分散ストレージグリッドリソースに書き込まれるように指定される場合、グリッドクライアントは再構築リスト（Ｒｅｂｕｉｌｄ Ｌｉｓｔ）上にその時点で書き込まれ得ない分散データ共有を指定する。さらに、既に分散データを格納しているグリッドリソースが利用不可能になると、分散ストレージグリッド内のプロセスは、再構築リストで再生成する必要があるその分散データ共有を指定する。他の時点において、個別プロセスは再構築リストのセットを読み込み、対応する分散データを生成し、利用可能なグリッドリソース上にそのデータを格納する。
【発明を実施するための最良の形態】
【００１２】
本発明のこれらの利点および他の利点は、添付の図面および明細書を参照すると、容易に明らかとなる。
【００１３】
（詳細な説明）
本発明は、データストレージシステムに関する。オリジナルデータのセキュリティを保護するために、オリジナルデータは、多数のデータ「スライス」またはサブセットに分かれている。本発明は、データファイルをファイルスライスまたはファイル「共有（ｓｈａｒｅ）」に分けるまたは分散するために使用することもできる。各スライスのデータ容量は、他のデータサブセットのいくつかまたは全てと結合させない限り、それ自体では、利用可能性がより低い、または認識可能性がより低い、または、完全に利用不可能である、または完全に認識不可能である。特に、本発明によるシステムは、オリジナルデータをデータサブセットに「スライス」し、符号化されたデータサブセットを生成するために、データサブセット上で符号化アルゴリズムを使用する。各データサブセットおよびその対応する符号化されたサブセットを、通信ネットワーク上で別々に転送し、ストレージノードのアレイの別々のストレージノードに格納してもよい。オリジナルデータを再生成するために、データサブセットおよび符号化されたサブセットは、各ストレージノードおよび各通信チャンネルの利用可能性および性能によって、いくつかのまたは全てのストレージノードまたは通信チャンネルから取得される。一連の復号アルゴリズムを取得されたデータおよび符号化されたデータに適用することによって、オリジナルデータが再生成される。
【００１４】
情報分散方法に基づく他の公知のデータストレージシステムによる場合と同様に、１つ以上のデータサブセットへの不正アクセスは、ソースデータについての分量の不十分な、または利用不可能な情報しか提供しない。
【００１５】
本発明を理解するため、ファイルまたはファイルのシステムを構成可能なＮ個の文字ｄ０，ｄ１，．．．，ｄＮの文字列を想定する。典型的なコンピュータファイルシステムはギガバイトのデータを含むことがあり、このことは、Ｎが数兆個の文字を含むことを意味する。以下の例では、データ文字列の長さＮがストレージノードの数ｎと等しい、かなり短い文字列を想定する。より大きなデータ文字列を格納するためには、こうした方法を何度も適用可能である。これらの方法はまた、コンピュータファイルまたは全ファイルシステムを格納するために、繰り返し適用され得る。
【００１６】
この例では、文字列がＯ Ｌ Ｉ Ｖ Ｅ Ｒという文字を含み、文字列には以下のようなＡＳＣＩＩ文字コードを含むことを仮定する。
ｄ０＝Ｏ＝７９
ｄ１＝Ｌ＝７６
ｄ２＝Ｉ＝７３
ｄ３＝Ｖ＝８６
ｄ４＝Ｅ＝６９
ｄ５＝Ｒ＝８２
文字列は、それぞれｎ個の文字であるセグメントに分割され、ここで、ｎは所望の計算効率のレベルを維持しながら所望の信頼性およびセキュリティ特性を提供するように選択される（典型的には、ｎは１００未満となるように選択される）。一実施形態において、その結果データの各サブセットが、例えば、オリジナルデータの４分の１未満を含み、結果として、各データサブセットの認識可能性が低下するように、ｎは４よりも大きくなるように選択され得る。
【００１７】
別の実施形態において、以下のように、第１のオリジナルデータセットが６個の異なるデータサブセットに分けられるように、ｎを６になるように選択する。
Ａ＝ｄ０、Ｂ＝ｄ１、Ｃ＝ｄ２、Ｄ＝ｄ３、Ｅ＝ｄ４、Ｆ＝ｄ５
例えば、オリジナルデータが、Ｏ Ｌ Ｉ Ｖ Ｅ Ｒというテキストの文字のＡＳＣＩＩ値の開始文字列である場合、データサブセットの値は以下のリストのようになる。
Ａ＝７９
Ｂ＝７６
Ｃ＝７３
Ｄ＝８６
Ｅ＝６９
Ｆ＝８２
この実施形態において、符号化されたデータの値は、オリジナルデータセット内の他のデータ値のサブセットからのデータ値を加算することで生成される。例えば、符号化された値は、以下のデータ値を加算することで生成できる。
ｃ［ｘ］＝ｄ［ｎ＿ｍｏｄ（ｘ＋ｌ）］＋ｄ［ｎ＿ｍｏｄ（ｘ＋２）］＋ｄ［ｎ＿ｍｏｄ（ｘ＋４）］
この式において、
ｃ［ｘ］は、符号化されたデータ値のセグメントアレイにおけるｘ番目の符号化されたデータ値である
ｄ［ｘ＋ｌ］は、データ値のアレイにおけるｘよりも大きい位置１における値である
ｄ［ｘ＋２］は、データ値のアレイにおけるｘよりも大きい位置２における値である
ｄ［ｘ＋４］は、データ値のアレイにおけるｘよりも大きい位置４における値である
ｎ＿ｍｏｄ（）は、数空間０からｎ―１においてモジュロ演算を実行する関数である
この式を使用して、以下の符号化された値を生成する。
ｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥ、ｃＦ
ここで、ｃＡは、例えば、Ｂ＋Ｃ＋Ｅと等しく、データ値Ａと共に通信および／または格納される符号化された値を表す。
【００１８】
例えば、オリジナルデータがＯ Ｌ Ｉ Ｖ Ｅ Ｒというテキストの文字のＡＳＣＩＩ値の開始文字列である場合、符号化されたデータサブセットの値は、以下のようになる。
ｃＡ＝２１８
ｃＢ＝２４１
ｃＣ＝２３４
ｃＤ＝２２７
ｃＥ＝２３４
ｃＦ＝２４１
本発明に従って、例示的なデータＡＢＣＤＥＦから成るオリジナルデータセット２０は、例えば、６個のデータサブセットＡ、Ｂ、Ｃ、Ｄ、ＥおよびＦにスライスされる。データサブセットＡ、Ｂ、Ｃ、Ｄ、ＥおよびＦも、以下で説明するように符号化されており、符号化されたデータサブセットｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥおよびｃＦを形成する。データサブセットＡ、Ｂ、Ｃ、Ｄ、ＥおよびＦならびに符号化されたデータサブセットｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥおよびｃＦは、例えば、図１に示されているように、複数のスライス２２、２４、２６、２８、３０および３２に形成される。各スライス２２、２４、２６、２８、３０および３２は、異なるデータ値Ａ、Ｂ、Ｃ、Ｄ、ＥおよびＦならびに異なる符号化されたサブセットｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥおよびｃＦを含む。スライス２２、２４、２６、２８、３０および３２は、インターネット等の通信ネットワークを介し、一連のデータ転送の形でシリーズに転送し、異なるデジタルデータストレージデバイスまたはストレージノード３４、３６、３８、４０、４２および４４に、それぞれ格納されてもよい。
【００１９】
オリジナルデータを取得するために（またはデータが転送されたばかりで格納されていない場合にはこれを受信するために）、データを、図２に示すように再構成可能である。各ストレージノード３４、３６、３８、４０、４２および４４からのデータ値は、インターネット等の通信ネットワークを通じて、受信先のコンピュータ（図示せず）に転送される。図２に示すように、受信先のコンピュータは、そのそれぞれが異なるデータ値Ａ、Ｂ、Ｃ、Ｄ、ＥおよびＦならびに異なる符号化された値ｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥおよびｃＦを含む、スライス２２、２４、２６、２８、３０および３２を受信する。
【００２０】
ストレージノード３４、３６、３８、４０、４２および４４または通信接続の利用停止または性能遅延等の様々な理由のために、時間データを再生成するたびに、必ずしも全てのデータスライス２２、２４、２６、２８、３０および３２が利用可能となるわけではない。図３は、データスライス２２、２４、２６、２８、３０および３２の１つ、例えば、データ値Ａを含むデータスライス２２および符号化された値ｃＡが利用不可能である場合に、本発明がオリジナルデータセットを再生成する条件を示す。この場合、オリジナルデータ値Ａは、以下のようにして求められる。
Ａ＝ｃＣ−Ｄ−Ｅ
ここで、ｃＣは符号化された値であり、ＤおよびＥは、スライス２６、２８および３０から利用可能なオリジナルデータ値であり、これらはそれぞれ、ノード３８、４０および４２から利用可能であると仮定する。この場合、不明なデータ値は、既知の符号化された値から既知のデータ値を減算することにより、符号化された値を生成するためにデータ値の一部を加算する符号化の式を逆にすることで、求められる。
【００２１】
例えば、オリジナルデータがＯ Ｌ Ｉ Ｖ Ｅ Ｒというテキストの文字のＡＳＣＩＩ値の開始文字列である場合、Ａのデータ値は、以下のようにして求められる。
Ａ＝２３４−８６−６９
従って、Ａ＝７９となり、これは、文字ＯのＡＳＣＩＩ値である。
【００２２】
他の場合において、オリジナルデータ値を求めるにはより詳細な復号式が必要となる。例えば、図４は、オリジナルデータ値Ａ、ＢおよびＥを含む６個のノードのうちの３個、３４、３６および４２、およびその対応する符号化された値ｃＡ、ｃＢおよびｃＥが利用不可能である、条件を示す。図４のこうした不明なデータ値Ａ、ＢおよびＥおよび対応物は、以下の式シーケンスを使用して再構築できる。
１．Ｂ＝（ｃＤ−Ｆ＋ｃＦ−ｃＣ）／２
２．Ｅ＝ｃＤ−Ｆ−Ｂ
３．Ａ＝ｃＦ−Ｂ−Ｄ
こうした式は、特定の式を実行する場合に、各式で必要とされるデータ値が利用可能になるよう、リストされた順で実行する。
【００２３】
例えば、オリジナルデータが、Ｏ Ｌ Ｉ Ｖ Ｅ Ｒというテキストの文字のＡＳＣＩＩ値の開始文字列である場合、Ｂ、ＥおよびＡのデータ値は、以下のようにして求められる。
１．Ｂ＝（２２７−８２＋２４１−２３４）／２
Ｂ＝７６
２．Ｅ＝２２７−８２−７６
Ｅ＝６９
３．Ａ＝２４１−７６−８６
Ａ＝７９
ｎ＝６であり、およびスライス２２、２４、２６、２８、３０および３２のうちの３つまでが、再生成の際に利用不可能である場合に、オリジナル全データＡＢＣＤＥＦの再生成のための方法を一般化するために、図５は、不明なデータを再生成する方法を決定するために利用可能なテーブルを含む。
【００２４】
このテーブルは、６個のストレージノードのうち１、２または３が利用不可能である、または利用不可能であると考えられるのに十分なほど遅く行われる、４０の異なる利用停止シナリオを示す。図５の表において、行の「Ｘ」は、そのノードからのデータおよび符号化された値が利用不可能であることを示す。「タイプ」の列は、ノードの空間パターンタイプが利用不可能であることを示す。「オフセット」の値は各利用停止シナリオを示す。オフセットは特定の利用停止シナリオおよびそのタイプの第１の利用停止シナリオの空間位置の差であるということを示す。
【００２５】
データ値は、アレイｄ［ｘ］によって示すことが可能であり、ここで、ｘは、データ値が格納されたノード番号である。符号化された値は、アレイｃ［ｘ］で表すことができる。
【００２６】
ｎ＝６である場合に１つのノードがストレージアレイにおいて利用不可能である、利用停止シナリオにおける不明なデータを再構成するには、以下の式を利用可能である。
ｄ［０＋ｏｆｆｓｅｔ］＝ｃ３ｄ（２，３，４，ｏｆｆｓｅｔ）
ここで、ｃ３ｄ（）は、以下のような擬似コンピュータソフトウェアコードの関数である。
【００２７】
【化１】
ここで、ｎ＿ｍｏｄ（）は、以前に定義された関数である。
【００２８】
ｎ＝６である場合に２つのノードがストレージアレイにおいて利用不可能である、利用停止シナリオにおける不明なデータを再構成するために、図６の表の以下の式を利用可能である。図６において、「利用停止タイプ番号」は、図５の対応する利用停止「タイプ」を示す。図６の「復号演算」は、復号演算が実行される順序を示す。図６の「復号化されたデータ」の列は、各不明なデータ値を生成する特定の復号演算を示す。
【００２９】
ｎ＝６である場合に３つのノードがストレージアレイにおいて利用不可能である、利用停止シナリオにおける不明なデータを再構成するために、図７の表の式を利用可能である。図７において、利用停止タイプ＝３の場合の第１の復号のための復号式の構造は、ｎ＝６である場合の他の復号式とは異なる構造であることに留意されたい。
【００３０】
グリッドからのデータを読み込む場合に全てのストレージノード５７が利用可能な訳ではないという状況に加えて、図８に示すように、全てのストレージノード５７が、分散ストレージグリッド４９へ書き込む際に利用可能であるわけではない場合がある。図８に示す例において、それぞれ参照番号３６および４０で識別される、ストレージノード１および３は、グリッドクライアント６４がグリッドへ書き込み中は利用不可能であると仮定される。こうした状況において、グリッドクライアント６４は、ストレージノード１および３にデータを格納するために他のストレージノード５７を選択してもよく、または、クライアント６４は、図９のステップ１に示すように、ストレージグリッド上の他のノードに格納される、リビルダリスト６６または重複するリビルダリストのセットに書き込んでもよい。概して、リビルダリスト６６は、不明なデータスライスを上記のように再生成できるように、不明なデータスライスをリスト表示する。ストレージノード１および３が動作していないこの例において、グリッドクライアント６４はグリッド上の他のストレージノード５７上にノード１および３に直接指定されたスライスを格納しないが、その代わりに、グリッドクライアント６４は、図１０に示すように、データスライスをリビルダリスト６６に追加する。
【００３１】
非動作のストレージノード１および３が後で再び動作可能になると、再構築エージェント６７と呼ばれるストレージグリッド上のプロセスを使用して、図９のステップ２、３および４に示されているように、不明なデータスライスを再構築することができる。上記の例を用いて、再構築エージェント６７はまず、ステップ２において、図１０の情報を読み込む。こうして、再構築エージェント６７は、まずは不明なスライスのデータ値を生成し、次に不明なスライスのそれぞれにおいて符号化された値を生成することによって、データスライスを再生成する。
【００３２】
この例で不明なデータ値を作成するために、再構築エージェント６７は、図５のテーブルを使用して、ノード１および３を有する６個のノードグリッドの利用停止タイプは、オフセット１を有する利用停止タイプ２であると決定する。この例において、再構築エージェント６７は、以下のような、図６の６個のノードグリッドのタイプ２利用停止の式を使用する。
【００３３】
【表１】
ＯＬＩＶＥＲという単語のオリジナルデータのＡＳＣＩＩ値と共に例のデータを使用すると、以下の式によって、不明な第１のデータ値が求められる。
ｄ１＝Ｃ０−ｄ２−ｄ４（第１の復号式）
図８のステップ３に示されるように、再構築エージェントはグリッド上のストレージノード５７から必要なデータスライスを取得し、次に、以下に示すように、第１の不明なスライスデータを再生成する。
Ｂ＝ｃＡ−Ｃ−Ｅ
Ｂ＝２１８−７３−６９
Ｂ＝７６
７６というＡＳＣＩＩ値は、ストレージノート１のオリジナルデータである文字「Ｌ」に相当する。第２の不明なオリジナルデータ値は、次のように求められる。
ｄ３＝ｃ２−ｄ４−ｄ０（第２の復号式）
ステップ３に示すように、図８において、再構築エージェントはグリッド上のストレージノード５７から必要なデータスライスを取得し、次に、以下に示すように、第２の不明なスライスデータを再生成する。
Ｄ＝ＣＣ−Ｅ−Ａ
Ｄ＝２３４−６９−７９
Ｄ＝８６
８６というＡＳＣＩＩ値は、ストレージノード３のオリジナルデータである文字「Ｖ」に相当する。
【００３４】
ストレージノード１および３の符号化されたデータ値の再生成は、オリジナルの符号化式を再び適用することで実行可能である。
ｃ［ｘ］＝ｄ［ｎ＿ｍｏｄ（ｘ＋ｌ）］＋ｄ［ｎ＿ｍｏｄ（ｘ＋２）］＋ｄ［ｎ＿ｍｏｄ（ｘ＋４）］
次に例の符号化されたデータ値を再生成すると、以下のようになる。
ｃＢ＝Ｃ＋Ｄ＋Ｆ
ｃＢ＝７３＋８６＋８２
ｃＢ＝２４１
ｃＤ＝Ｅ＋Ｆ＋Ｂ
ｃＤ＝６９＋８２＋７６
ｃＤ＝２２７
すると、図９のステップ４に示されているように、ＢおよびｃＢで成るデータスライスをストレージノード１に書き込むことが可能になり、ＤおよびｃＤで成るデータスライスをストレージノード３に書き込むことが可能になる。スライスを再構築するこの方法は、グリッドクライアントがグリッドに新規データを書き込んでいるためにストレージリソースが一時的に利用不可能である場合に、分散データを再構築するために利用可能である。
【００３５】
図１１は、ストレージリソースが永久に破損しているおよび新規リソースによって置換される場合に、スライスをどのように再構築できるかを示す。このシナリオにおいて、永久に失われたストレージリソースによって以前に保持されたデータスライスは、新規の、置換ストレージリソース上で再生成される。ステップ１において、グリッド管理者６８（自動プロセスまたは判断を下す人員にしてもよい）は、図１１のストレージノード５７によって示されるストレージリソースは永久に利用不可能であると決定する。グリッド管理者６８は、次に、以下の例示的な情報によって、ストレージノード５７内の置換データ領域を指定する：Ｖｏｌｕｍｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒ、Ｖｏｌｕｍｅ＿Ｌｏｃａｔｉｏｎ。この例において、Ｖｏｌｕｍｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒは、データスライスが以前に格納され、今は利用不可能であるデータ領域番号である。Ｖｏｌｕｍｅ＿Ｌｏｃａｔｉｏｎは、新規ストレージノード５７のネットワーク位置である。この例において、Ｖｏｌｕｍｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒは、番号７６５４によって示され、ネットワーク位置は１２３．１２３．１２３．１２３の形式のインターネットＩＰアドレスによって示すことができる。グリッド管理者６８は、再構築リストメーカ７０という分散ストレージグリッド上で実行されているプロセスへ、この情報を提供する。
【００３６】
図１１のステップ２に示されているように、再構築リストメーカ７０は、次に、以下に述べる、グリッドディレクタ５８という分散ストレージグリッド上のプロセスからボリューム、ユーザおよびファイル情報を得る。ボリュームは、ハードドライブ、サーバまたは複数の位置におけるサーバのグループで構成することのできるグリッド上のデータストレージプロセスである。ユーザは、特定のグリッドクライアント６４の名称である。この例において、ファイルは、グリッド上に分散しているオリジナルデータファイルの識別子である。以下でより詳細に説明するように、グリッドディレクタ５８は、グリッド上のボリューム、ユーザおよびファイル情報を追跡するプロセスである。再構築リストメーカ７０は、再構築予定のボリューム７６５４に関連付けられたユーザについての情報を提供するようグリッドディレクタ５８にリクエストし、図１２に示すようにグリッドディレクタ５８が返る。
【００３７】
図１２は、３人のユーザが、再構築予定のボリューム７６５４上にデータを有することを示す。こうしたユーザは、識別番号１２３４５６７、１２３４５６８および１２３４５６９を有する。再構築リストメーカ７０はさらに、グリッドディレクタ５８から、３人の影響を受けるユーザへとファイルを関連付けるテーブルをリクエストする。グリッドディレクタ５８は、図１３に示されるもののようにテーブルを返す。図１３は、再構築されるボリューム上にデータを格納するユーザに、６個のファイルが関連付けられていることを示す。
【００３８】
再構築リストメーカ７０は次に、再構築予定のデータ領域またはボリュームの喪失による影響を受けるこうしたファイルに関連付けられる、全スライスのリストを生成する。そのファイルから生成されるスライスセットに対応するダッシュおよび数を追加することにより、Ｆｉｌｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒを、対応するＳｌｉｃｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒに変換することができる。この例において、６個のノード分散ストレージグリッド上の各ファイルについて、再構築予定のボリュームの損失によって影響を受ける可能性があるファイルの全てのスライスを示すために、Ｓｌｉｃｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒｓの図１４に示すようなリストが生成される。
【００３９】
まず、図１４に示されるＳｌｉｃｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒの最初の６桁は、そのスライスを生成するのに使用されるＦｉｌｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒに相当する。Ｓｌｉｃｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒの最後の桁は、そのストライプまたはファイルスライスのセット内で識別される特定のスライスに相当する。
【００４０】
次に、図１１のステップ３に示されているように、再構築リストメーカ７０は、これらのユーザに関連付けられたグリッド上に現在格納されている全てのスライスのリストを生成するために、再構築予定のボリュームに関連付けられたユーザに関連付けられたグリッド上の全ストレージノード５７にクエリを実行する。
【００４１】
図１１のステップ３に示すように、再構築リストメーカ７０は、次に、再構築予定のボリュームによって影響を受けるユーザに関連付けられたグリッド上に格納される全スライスを決定するために、グリッド上の各ストレージノード５７にクエリを実行する。各ストレージノード５７は、図１５に示される形式のテーブルを、再構築リストメーカに返す。
【００４２】
再構築リストメーカ７０は、再構築予定のボリュームによって影響を受けるユーザに関連付けられたグリッド上に現在格納される全てのＳｌｉｃｅ＿Ｉｄｅｎｔｉｆｌｃａｔｉｏｎ＿Ｎｕｍｂｅｒｓを収集する。こうして、図１３に示される再構築予定のボリュームによって影響を受ける各ファイルに関連付けられた図１４に示される各スライスについて、再構築リストメーカ７０は、図１５に示すグリッド上に現在格納されているスライスのテーブルの１つにそのＳｌｉｃｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒが表示されるかどうかを決定することによって、そのスライスがグリッド上に現在格納されているかどうかを決定する。
【００４３】
グリッド上に現在格納されていない各スライスについて、再構築リストメーカ７０は、図１１のステップ５に図示されているように、リビルダリスト６６へのエントリまたはリビルダリストのセットを追加する。図１１のステップ５、６、７および８を完了するためのプロセスは、次に、図９のステップ１、２、３、および４に以前に記載されているプロセスと同様に実行される。
【００４４】
こうしたタイプのデータ再構築方法は、全てのオリジナルデータを完全に復元している間に、ストレージグリッドが受容可能な様々な回数のストレージノード利用停止を有する様々な数のストレージノードを有する、信頼性のあるストレージグリッドを生成するために、ソフトウェア開発分野の当業者によって利用可能である
（情報分散ストレージシステムのメタデータ管理システム）
本発明の重要な態様に従って、例えば、図１〜図８に関して上述されているように、グリッドを形成する共通の通信ネットワークに結合されるいくつかのストレージノードに分散および格納される情報の分散およびストレージを管理するために、メタデータ管理システムを使用する。情報分散システムの信頼性を向上させるために、グリッド上のトランザクションのメタデータ属性は、分散データの個別のデータ領域に格納される。
【００４５】
上述のように、情報分散システムは、オリジナルデータをデータサブセットに「スライス」し、符号化されたデータサブセットを生成するために、データサブセット上で符号化アルゴリズムを使用する。オリジナルデータを再生成するために、データサブセットおよび符号化されたサブセットを、各ストレージノードおよび各通信チャンネルの利用可能性および性能に応じて、ストレージノードまたは通信チャンネルのいくつかのまたは全てから取得する。情報分散方法に基づく他の公知のデータストレージシステムと同様に、１つ以上のデータサブセットへの不正アクセスは、ソースデータについての量の不十分なまたは利用不可能な情報しか提供しない。例えば、図１に図示されているように、各スライス２２、２４、２６、２８、３０および３２は、異なるデータ値Ａ、Ｂ、Ｃ、Ｄ、ＥおよびＦならびに異なる「符号化されたサブセット」（符号化されたサブセットはアルゴリズムによって生成され、オリジナルサブセットの一部を使用して復元が完了すると、復元できるようデータスライスと共に格納される）ｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥおよびｃＦを含む。スライス２２、２４、２６、２８、３０および３２は、インターネット等の通信ネットワーク上を、異なるデジタルデータストレージデバイスまたはストレージノード３４、３６、３８、４０、４２および４４に、連続しておよびそれぞれ格納された一連のデータ転送で、転送してもよい。各データサブセットおよびその対応する符号化されたサブセットを、通信ネットワーク上を個別に転送し、ストレージノードのアレイにおける個別のストレージノードに格納してもよい。
【００４６】
「ファイルストライプ」とは、特定のファイルに対応する一組のデータおよび／または符号化されたサブセットである。各ファイルストライプは、利用可能なストレージリソースまたはストレージノードとして、全体のグリッド内において、データストレージデバイスまたはストレージノード５７の異なるセット上に格納してもよく、または、ストレージノードは、異なるファイルとして経時的に変化し、グリッド上に格納してもよい。
【００４７】
「データ領域」は、特定のクライアント６４のデータを含むストレージグリッド４９の一部である。グリッドクライアントは、２つ以上のデータも利用してもよい。図１１のデータ領域テーブル１０６は、特定のクライアントに関連付けられた全データ領域を示す。典型的には、特定のグリッドクライアントは、データセキュリティおよびプライバシーを提供するために、他のグリッドクライアントのデータ領域を表示することはできない。
【００４８】
図１６は、概して参照番号４９で識別される、ストレージグリッドの異なるコンポーネントを示す。グリッド４９は、インターネット等の通信ネットワークに接続された他のグリッドクライアント（グループまたは個別の「ストレージノード５７」）に関連付けられた他のストレージノード５６と同様に、特定のグリッドクライアント６４に関連付けられたストレージノード５４を含む。グリッド４９はさらに、クライアントバックアップを管理するためのアプリケーションおよびデータ領域およびその関連付けられた収集に関する復元を含む。
【００４９】
概して、「ディレクタ」とは、グリッド４９上で実行するアプリケーションをいう。ディレクタは、以下のような様々な目的を果たす。
１．ユーザクライアントログインの中央化されているがコピー可能なポイントを提供する。ディレクタは、ユーザログイン情報を格納するグリッドアプリケーションにすぎない。
２．自律的に格納されたファイルのユーザごとのリストを提供する。全てのユーザクライアントは、１つおよび１つのみのディレクタと対話することによって、各ユーザの、グリッド上に格納されたファイルの全リストを獲得することができる。このファイルリストメタデータは、１つのプライマリディレクタにおいて、いくつかのバックアップディレクタへとコピーされる。
３．どのサイトがユーザスライスを含むかを追跡する。
４．他のノード特性についてのマネージャ認証証明書。
【００５０】
グリッド上のアプリケーションはメタデータ管理システムを形成し、プライマリディレクタ５８、セカンダリディレクタ６０および他のディレクタ６２を含む。各データ領域は必ず、任意の時点において、１つのおよび１つのみのプライマリディレクタ５８に関連付けられる。グリッドクライアント６４が任意のデータ領域演算（保存／取得）を試行する度に、グリッドクライアント６４は、そのデータ領域に関連付けられたプライマリディレクタ５８と共にその演算を調整する必要がある。他の事柄のうち、プライマリディレクタ５８は、各データ領域への限定されたロックを管理する。各プライマリディレクタ５８は、少なくとも１つ以上のセカンダリディレクタ６０を有する。システムの信頼性を高めるために、任意のデータ領域メタデータ更新（特に、ロックの更新）は、データ領域のプライマリディレクタ５８によって同期的にコピーされ、リクエストしているグリッドクライアント６４に認知状態を返す前に、そのセカンダリまたはバックアップディレクタ６０の全てへとコピーされる。さらに、信頼性の向上のために、グリッド上の他の全てのディレクタ６２も、メタデータ更新のコピーを同期的に受信してもよい。こうした構成において、全てのデータ領域メタデータが、グリッド４９全体にわたって、効率的にコピーされる。
【００５１】
本明細書において使用されている場合、プライマリディレクタ５８およびその関連付けられたセカンダリディレクタ６０は、さらに、関連付けられたディレクタ６０と呼ばれることもある。セカンダリディレクタ６０は、グリッドクライアント６４データ領域更新の動作中にプライマリディレクタ５８が障害を発生した場合に任意の認識されたメタデータ管理更新が失われないようにしている。セカンダリディレクタ６０の数およびグリッド４９のメタデータアクセス性能の間にはトレードオフが存在する。概して、セカンダリディレクタ６０の数が増えると、メタデータ更新の信頼性は高くなるが、メタデータ更新の応答時間は遅くなる。
【００５２】
関連付けられたディレクタ６６および他のディレクタ６２は、どのスライスが各ストレージノード５７に格納されているかを追跡しないが、各グリッドクライアント６４に関連付けられたストレージノード５７を追跡する。特定のノードが各クライアントで認識されると、各グリッドクライアント６４に関連付けられたスライスを決定するために、様々なストレージノード５７にコンタクトを取ることが必要である。
【００５３】
プライマリディレクタ５８が大部分のグリッドメタデータを制御しており、ストレージノード５７は以下の役割を果たしている。
１．ユーザのスライスを格納する。ストレージノード５７は、クライアントのマシンのユーザのファイルシステム構造を反映したファイルシステムのユーザスライスを格納する。
２．データベースにおけるストレージノード５７上のユーザごとのファイルのリストを格納する。ストレージノード５７は、スライスハッシュ化したシグナチャ（例：ＭＤ５ｓ）等の最小メタデータ属性を、データベースにおける各スライスの「行」に関連付ける。
【００５４】
グリッドは、一意のストレージボリュームシリアルナンバー（ボリュームＩＤ）によって各ストレージノード５７を識別し、このため、複数のサーバに分散している場合でも、ストレージボリュームを識別できる。オリジナルデータを再生成するために、データサブセットおよび符号化されたサブセットを、各ストレージノード５７および各通信チャンネルの利用可能性および性能に応じて、ストレージノード５７または通信チャンネルのいくつかのまたは全てから取得する。各プライマリディレクタ５８は、グリッド４９上の全てのストレージノード５７、つまり、各サイトにおいて利用可能な全ノードのリストを保持する。
【００５５】
以下は、バックアップ／復元プロセス中に使用される主なメタデータ属性のリストである。
【００５６】
【表２】
【００５７】
【表３】
図１７は、クライアントがストレージシステムと対話する場合の出来事のデータの流れおよび最上層の図を示す。図１８は、プロセスのユーザ情報を追跡するために使用される主なメタデータテーブルについて説明する。
【００５８】
図１７を参照すると、まずステップ７０において、グリッドクライアント６４は、グリッドにおいてサーバで実行されているディレクタアプリケーションへのログインで開始される。ログインが成功すると、ディレクタアプリケーションは、ステップ７２において、グリッドクライアント６４へ、ＤａｔａｓｐａｃｅＤｉｒｅｃｔｏｒＭａｐ９２（図１８）を返す。ディレクタアプリケーションは、ＤａｔａｓｐａｃｅＩＤを決定するために、グリッドクライアントのＡｃｃｏｕｎｔＩＤを参照するルックアップテーブル、ＡｃｃｏｕｎｔＤａｔａｓｐａｃｅＭａｐ９３を含む。次に、ＤａｔａｓｐａｃｅＤｉｒｅｃｔｏｒＭａｐ９２からグリッドクライアントのプライマリディレクタ（つまり、ＤｉｒｅｃｔｏｒＡｐｐＩＤ）を決定するためにＤａｔａｓｐａｃｅＩＤを使用する。
【００５９】
グリッドクライアント６４がそのプライマリディレクタ５８を認識すると、グリッドクライアント６４はＤａｔａｓｐａｃｅＶｏｌｕｍｅＭａｐ９４（図１８）をリクエストし、グリッドクライアント６４に関連付けられたストレージノード（つまり、ＶｏｌｕｍｅｌＤ）を決定するためにデータ領域ＩＤを使用できる。プライマリディレクタ５８は、トランザクションテーブル１０４（図１８）のグリッドクライアント６４のために、ＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔＩＤを設定する。ＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔＩＤは、各トランザクション（つまり、グリッドクライアント６４の各実行インスタンスまたはセッション）に一意である。特に、ＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔテーブル９６の一意のトランザクションＩＤを生成するために、ＤａｔａｓｐａｃｅＤｉｒｅｃｔｏｒＭａｐ９２からのデータ領域ＩＤを使用する。グリッド４９を有するグリッドクライアントの各セッションにおいて、それぞれのグリッドクライアント別に、全てのトランザクションを追跡するために、トランザクションＩＤはＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔＩＤと共にトランザクションテーブル１０４に格納される。
【００６０】
「ＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔｌｄ」のメタデータ属性は、クライアントが２つ以上のアクティブなトランザクション（関連されていない）と関連を持つことができるＴｒａｎｓａｃｔｉｏｎＩＤとは異なる属性であるが、常に、１つのみの「トランザクションコンテクストＩｄ」が、クライアントの１つの実行インスタンスに関連付けられる。こうしたメタデータ属性によって、異なるグリッドクライアントによる同時トランザクションの管理が可能になる。
【００６１】
上述のように、プライマリディレクタ５８は、各グリッドクライアント６４に関連付けられているストレージノード５７のリストを維持する。このリストは、ストレージノード（つまり、ＤａｔａｓｐａｃｅＩＤ）のＩＤおよびグリッドクライアント６４のＩＤ（つまり、ＩＤ）を維持するＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔテーブル９６として維持される。プライマリディレクタ５８は、プライマリディレクタ５８と通信するために、グリッドクライアント６４によって使用される「アプリケーション」メタデータ（つまり、Ａｐｐｌｉｃａｔｉｏｎｓテーブル１０４）を含む。トランザクションのタイプ（ＡｐｐＴｙｐｅＩＤ）を記録するためにＡｐｐｌｉｃａｔｉｏｎｓテーブル６４を使用し、例えば、トランザクション（つまり、ＳｉｔｅＩＤ）に関連付けられたデータスライスおよびストレージノード５７を追加または削除する。
【００６２】
任意のデータ転送が開始される前に、グリッドクライアント６４は、例えば、その生成日および修正日と共に、ファイルの名前およびサイズ等の、意図したトランザクションに関してプライマリディレクタ５８を有するメタデータを保管する。メタデータは、さらに、Ｔｒａｎｓａｃｔｉｏｎ Ｄａｔａｓｏｕｃｅｓテーブル９８に示される様々なフィールド等の他のメタデータ属性も含む。（図１８）トランザクションが完了するまでトランザクションを追跡するために、トランザクションデータソースメタデータテーブル９８を使用する。
【００６３】
上記の情報をグリッドクライアント６４およびプライマリディレクタ５８間で交換後、グリッドクライアント６４は、ファイルスライスの転送準備のために、ステップ７４において、ストレージノードに接続する。任意の情報を交換する前に、グリッドクライアント６４は、トランザクションデータソーステーブル９８においてデータフィールドを埋めるために、ステップ７６において、そのデータソーステーブル１００にメタデータを登録する。
【００６４】
次にステップ７８において、グリッドクライアント６４上で実行されるアプリケーションによって上述されるように、データスライスおよび符号化されたサブセットが生成される。データの任意のデータスクランブル、圧縮および／または暗号化は、データがスライスに分散される前または後に実行されるようにしてもよい。次に、データスライスは、ステップ８０においてストレージノード５７にアップロードされる。
【００６５】
アップロードが開始されると、グリッドクライアント６４は、ファイルメタデータ（つまり、ＤａｔａＳｏｕｒｃｅｓテーブル１００）を更新するために、トランザクションメタデータ（つまり、トランザクションデータソーステーブル９８からのデータ）を使用する。アップロードが完了すると、トランザクションデータソーステーブル９８からのデータソース情報がデータソーステーブル１００に移動し、ステップ８４、８６および８８において、トランザクションデータソーステーブル９８から削除される。このプロセスは本質的に「微小」なものであり、つまり、任意のインスタンスにおいてトランザクションに障害が起こった場合、変更は記録されない。データソーステーブル１００は、ユーザのファイルセットの完全性を保持するために改訂番号を含む。
【００６６】
図１９Ａおよび図１９Ｂに図示されている簡単な例は、メタデータ管理システム５０の動作を示す。この例は、クライアントはグリッド４９の「Ｍｙｆｉｌｅ．ｔｘｔ」という名前のファイルを保存したいと仮定する。
【００６７】
ステップ１：グリッドクライアントは、グリッド４９で実行されているディレクタアプリケーションに接続する。ディレクタアプリケーションはこのグリッドクライアント６４のプライマリディレクタ５８でないため、ディレクタアプリケーションは、グリッドクライアントを認証して、ＤａｔａｓｐａｃｅＤｉｒｅｃｔｏｒＭａｐ９２を返す。基本的に、ディレクタは、そのＤａｔａｓｐａｃｅＩＤを検索して対応するＤｉｒｅｃｔｏｒＡｐｐＩＤ（このクライアントのプライマリディレクタ）を返すために、ＡｃｃｏｕｎｔＩＤを使用する。
【００６８】
ステップ２：グリッドクライアント６４がＤａｔａｓｐａｃｅＤｉｒｅｃｔｏｒＭａｐ９２を得ると、ディレクタがそのプライマリディレクタであることが認識される。すると、グリッドクライアント６４はこのディレクタアプリケーションに接続し、プライマリディレクタは、グリッドクライアントセッションに一意の、上記で説明したＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔＩＤを生成する。プライマリディレクタ５８はさらに、グリッドクライアント６４を、そのＤａｔａｓｐａｃｅＶｏｌｕｍｅＭａｐ９４（つまり、グリッドクライアント６４が接続する必要のあるストレージノード５７の数）に送る。グリッドクライアント６４は、ファイルメタデータをディレクタ（つまり、トランザクションデータソーステーブルにおいて必要なフィールド）に送信する。
【００６９】
ステップ３：クライアントで実行中のアプリケーションによって、「Ｍｙｆｉｌｅ．ｔｘｔ」のデータスライスおよび符号化されたサブセットは、上記のストレージアルゴリズムを用いて生成される。次に、グリッドクライアント６４は、ＤａｔａｓｐａｃｅＶｏｌｕｍｅＭａｐ９４について、グリッド４９上の様々なストレージノード５７に接続する。次に、グリッドクライアントがそのデータおよび符号化されたサブセットを、グリッド４９上の様々なストレージノード５７に送信する。
【００７０】
ステップ４：グリッドクライアント６４が、様々なストレージノード５７上のそのファイルスライスを保存して終了すると、グリッドクライアント６４は、ＴｒａｎｓａｃｔｉｏｎＤａｔａｓｏｕｒｃｅｓテーブル９８からのこのトランザクションを削除し、これをデータソーステーブル１００に追加するよう、プライマリディレクタアプリケーション５８に通知する。システムは、グリッドクライアント６４がデータソーステーブル１００上にない任意のファイルを取得することができないように構成される。このため、データソーステーブル１００上にファイルメタデータを追加することで、ファイル保存／バックアップの動作が完了する。
【００７１】
上述の内容から明らかであるように、プライマリディレクタ５８は、トランザクションが開始または終了する時間を決定するアプリケーションである。トランザクションはプライマリディレクタ５８がストレージノード５７のメタデータをグリッドクライアント６４に送信する前に開始され、データソーステーブル１００上のデータソースについての情報の書き込み後に終了する。この構成により、完全性が保証される。このように、プライマリディレクタ５８がトランザクションに完了したと報告する場合、そのトランザクションを表示する任意のアプリケーションは、全ての他のストレージノードがトランザクションのために適正に更新されていることを認識する。この「アトミックトランザクション（Ａｔｏｍｉｃ Ｔｒａｎｓａｃｔｉｏｎ）」の概念は、ストレージシステムの完全性を維持するために重要である。例えば、更新トランザクション全体が完了していない場合、および異なるストレージノードの全てが適切に「同期されている」訳ではない場合、少なくとも、動作中のグリッドクライアント６４のデータ領域テーブル１００についてストレージシステムは混乱状態になっている。そうでない場合、トランザクションが任意の理由で中断された（例：バックアッププロセス中にクライアントのＰＣの電源をオフにした）ために不完全な状態となっている場合、システムの全体的なデータ保全性はかなり迅速に悪化する。
【００７２】
本発明の多くの修正例および変形例が、上記の教示に照らして可能であることが明らかである。このように、添付の特許請求の範囲内において上記の詳細な説明以外にも、本発明を実行可能であることが理解されよう。
【００７３】
特許請求の内容および米国の特許証によって保証されることが望ましい内容は、特許請求の範囲のとおりである。
【図面の簡単な説明】
【００７４】
【図１】図１は、本発明に従う、６個のストレージノードを有する例示的なデータストレージシステムのブロック図であり、オリジナルデータファイルがどのようにファイル共有に分散され、符号化され、個別のデジタルデータストレージデバイスまたはノードに転送されるかを示す。
【図２】図２は、図１と類似しているが、オリジナルデータセットを生成するために例示的な６個の全ノードからのデータサブセットがどのように取得および復号されるかを示している。
【図３】図３は、図２と類似しているが、６個のデジタルデータストレージデバイスのうちの１つの障害の状態を示している。
【図４】図４は、図３と類似しているが、６個のデジタルデータストレージデバイスのうちの３個の障害の状態を示している。
【図５】図５は、例示的な６個のデジタルデータストレージデバイスに格納されているデータを再生成するために利用可能な、本発明に従う例示的なテーブルである。
【図６】図６は、２個のノードの利用停止の状態のために、例示的な６個のノードのストレージデータストレージシステムの復号式をリスト表示する例示的なテーブルである。
【図７】図７は、図６と類似しているが、３個のノードの利用停止の状態について示している。
【図８】図８は、図２と類似しているが、データをストレージグリッドに書き込み中の、６個のデジタルデータストレージデバイスのうちの１個の障害の状態について示している。
【図９】図９は、新しいデータのストレージグリッドへの書き込み中にストレージリソースが利用不可能である場合にデータを再構築する、例示的なデータ再構築システムのブロック図である。
【図１０】図１０は、再構築リストテーブルのエントリをリスト表示する、例示的なテーブルである。
【図１１】図１１は、ストレージリソースが置換された場合にデータを再構築する、例示的なデータ再構築システムのブロック図である。
【図１２】図１２は、ボリューム識別番号およびユーザ識別番号のマッピングテーブルにおけるエントリをリスト表示する例示的なテーブルである。
【図１３】図１３は、ユーザ識別番号およびファイル識別番号マッピングテーブルのエントリをリスト表示する例示的なテーブルである。
【図１４】図１４は、特定のファイルに関連付けられたスライス識別番号のテーブルのエントリをリスト表示する例示的なテーブルである。
【図１５】図１５は、ユーザ識別番号およびスライス識別番号マッピングテーブルのエントリをリスト表示する例示的なテーブルである。
【図１６】図１６は、本発明に従う、情報分散ストレージシステムと共に使用するメタデータ管理システムの様々な機能要素を示す、本発明に従う例示的な図である。
【図１７】図１７は、分散データストレージグリッド上に格納されているデータのメタデータを保守するためのプロセスを示す例示的なフローチャートである。
【図１８】図１８は、ユーザトランザクションおよびユーザファイルセットルックアップ時に使用される必須のメタデータコンポーネントを示す。
【図１９Ａ】図１９Ａおよび図１９Ｂは、システムの動作を示す。
【図１９Ｂ】図１９Ａおよび図１９Ｂは、システムの動作を示す。
【技術分野】
【０００１】
（関連出願の参照）
本願は、２００５年９月３０日出願の共願の同時係属出願米国出願第１１／２４１，５５５号の一部継続出願である。
【０００２】
（発明の背景）
（１．発明の分野）
本発明は、情報分散アルゴリズムを使用してデータを格納するための分散データファイルストレージシステムおよび方法に関し、より詳細には、分散データを再構築するためのシステムおよび方法に関する。情報分散グリッドにおいて、分散データ（オリジナルの組のデータおよび／または符号化されたデータの複数のサブセット）を、１つ以上の位置の、複数のデータストレージデバイス上に格納することにより、その他のデジタルデータストレージデバイスからの分散データと組み合わされる場合以外では、各ストレージデバイス上の分散データは、認識不可能かつ利用不可能である。分散データが、常に完全に動作可能ではない情報分散グリッド上に転送または格納される状況に対処するために、本発明は、リソースの利用停止（ｏｕｔａｇｅ）による分散データの再構築だけでなく、情報分散グリッドにおける一時的または永続的なリソースの利用停止のいずれかに対処するための能力を提供する。
【背景技術】
【０００３】
（２．先行技術の記載）
データの格納のために、様々なデータストレージシステムが公知である。通常、こうしたデータストレージシステムは、例えば、単一のデータ領域（すなわち、単一のデジタルデータストレージデバイス）上に、特定のデータセットに関連付けられた全てのデータ（特定のユーザの全データ、特定のソフトウェアアプリケーションに関連付けられた全データ、または特定のファイル内の全データ等）を格納する。クリティカルなデータは、まず、冗長デジタルデータストレージデバイスに格納される。従って、あるデジタルデータストレージデバイスに障害が存在する場合、他のデジタルデータストレージデバイス上でデータの完全なコピーが利用可能である。冗長デジタルデータストレージデバイスを有するこうしたシステムの例は、本明細書に参照として援用される、特許文献１、特許文献２、および特許文献３に開示されている。こうした冗長デジタルデータストレージシステムは比較的信頼性が高いが、こうしたシステムには他の問題が存在する。第１に、こうしたシステムは、デジタルデータストレージのコストを、実質的に２倍以上に増加させてしまう。第２に、こうした冗長デジタルデータストレージシステムの全データを１つの場所に保管することにより、データを、不正（ｕｎａｕｔｈｏｒｉｚｅｄ）アクセスに対して脆弱にしてしまう。
【０００４】
セキュリティおよび結果としてデータストレージシステムの信頼性を向上させるために、性能の向上または容量制限に関する理由のためだけではなく、本明細書に参照として援用される特許文献４に記載されているように、２つ以上のストレージデバイス（ハードドライブ、または磁気テープあるいはいわゆる「メモリスティック」等のリムーバル媒体等）に、データが格納され得る。例えば、使用頻度の少ない過去のデータは磁気テープに格納され得る一方で、データベースの最近のデータはハードドライブに格納され得る。別の例は、単一のハードドライブ上に格納するにはサイズが大きすぎる単一のファイルからのデータを、２つのハードドライブへの格納することである。これらの場合の各々において、各データストレージデバイスに格納されるデータサブセットがオリジナルデータ全てを含むわけではないが、一部の利用可能な情報を提供するために使用され得るデータの概して連続的な部分は含んでいる。例えば、格納されるオリジナルデータが、以下の文の文字列であるとする。
Ｔｈｅ ｑｕｉｃｋ ｂｒｏｗｎ ｆｏｘ ｊｕｍｐｅｄ ｏｖｅｒ ｔｈｅ ｌａｚｙ ｄｏｇ．
そのデータは２つの異なるデータストレージデバイスに格納され、これらのデバイスの一方または両方が利用可能な情報を含むことになる。例えば、その４５文字の文字列のうちの最初の２０文字が１つのデータストレージデバイスに格納された場合、残りの２５文字は第２のデータストレージデバイスに格納され、センテンスは以下：
Ｔｈｅ ｑｕｉｃｋ ｆｏｘ ｊｕｍｐｅｄ（第１のストレージデバイスに格納）
ｏｖｅｒ ｔｈｅ ｌａｚｙ ｂｒｏｗｎ ｄｏｇ．（第２のストレージデバイスに格納）
のように格納される。
【０００５】
それぞれの場合において、各デバイスに格納されるデータはオリジナルデータの完全なコピーではないが、各デバイスに格納されるデータサブセットの各々はいくつかの利用可能な情報を提供する。
【０００６】
典型的には、ハードドライブ等のデバイス上のデータストレージの実際のビットパターンは、ハードドライブセクタまたはメモリセグメント等の、ファイルタイプ、ファイルシステムおよびストレージ構造を表すための追加の値で構築される。特定のファイルシステムおよび特定のストレージ構造を使用する、特定のファイルタイプのデータを構築するために使用される技術がよく知られており、これらの技術に精通した個人が物理的媒体におけるビットパターンからソースデータを識別することが可能である。
【０００７】
格納されたデータを認証ユーザのみに利用可能にすることを確実に行うために、多くの場合、ＤＥＳ、ＡＥＳまたはその他のいくつかの公知の暗号化技術の１つを使用して、暗号化形式でデータが格納される。これらの暗号化技術は、理想的には認証ユーザまたは認証プロセスにのみ知られている数学キーを必要とするある符号化形式で、データを格納する。こうした暗号化技術を「解読」するのは困難であるが、解読されている暗号化技術の場合は、こうしたデータストレージシステム上のデータを不正アクセスに対して脆弱にすることがわかっている。
【０００８】
暗号化を使用してデータを安全にするだけでなく、情報分散アルゴリズムを使用してデータストレージのセキュリティを向上させるいくつかの方法が開発されており、例えば、本明細書に参照として援用される、特許文献５および特許文献６に開示されている。こうした情報分散アルゴリズムは、オリジナルデータを複数のデータサブセットに「スライス（ｓｌｉｃｅ）」し、異なるストレージノード（すなわち、異なるデジタルデータストレージデバイス）へこれらのサブセットに分散させるために使用される。オリジナルデータセットを、そのオリジナルデータが全く含まれていない複数のデータセットに分散させるために、情報分散アルゴリズムも使用できる。個別には、各データサブセットまたはスライスはオリジナルデータを再生成するための十分な情報を含んでいないが、閾値数の（すなわち、オリジナルサブセットの数より少ない）サブセットが利用可能である場合、全てのオリジナルデータを正確に生成することができる。
【０００９】
データストレージシステムにおけるこうした情報分散アルゴリズムの利用は、様々な業界紙にも記載されている。例えば、非特許文献１による、「Ｈｏｗ ｔｏ Ｓｈａｒｅ ａ Ｓｅｃｒｅｔ」は、多項式補間に基づいて、暗号鍵等の秘密を共有するスキームについて記載している。別の業界紙、すなわち、非特許文献２の「Ｅｆｆｉｃｉｅｎｔ Ｄｉｓｐｅｒｓａｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ ｆｏｒ Ｓｅｃｕｒｉｔｙ，Ｌｏａｄ Ｂａｌａｎｃｉｎｇ，ａｎｄ Ｆａｕｌｔ Ｔｏｌｅｒａｎｃｅ」も、情報分散アルゴリズムを使用した情報分散の方法について記載している。
【特許文献１】米国特許第５，８９０，１５６号明細書
【特許文献２】米国特許第６，０５８，４５４号明細書
【特許文献３】米国特許第６，４１８，５３９号明細書
【特許文献４】米国特許第６，１２８，２７７号明細書
【特許文献５】米国特許第６，８２６，７１１号明細書
【特許文献６】米国特許出願公開第２００５／０１４４３８２号明細書
【非特許文献１】Ａ．Ｓｈａｍｉｒ，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ，Ｖｏｌ．２２，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ，１９７９
【非特許文献２】Ｍ． Ｒａｂｉｎ、Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｍａｃｈｉｎｅｒｙ，Ｖｏｌ．３６，Ｎｏ．２，Ａｐｒｉｌ １９８９，３３５―３４８ページ
【発明の開示】
【発明が解決しようとする課題】
【００１０】
残念ながら、こうした方法および他の公知の情報分散方法は、計算処理能力的に負担が大きいため、企業、消費者および他の組織で今日広く使用されているタイプのコンピュータで使用している一般的な大容量データストレージにとって、実用的でない。このため、計算処理能力的に負担の大きいアルゴリズムを使用する必要のないデータを、確実かつ安全に保護できるデータストレージシステムが求められている。
【課題を解決するための手段】
【００１１】
（発明の概要）
つまり、本発明は、その他のファイル共有のいくつかまたは全てと組み合わせた場合を除き、各ファイル共有のデータが、それ自体では利用可能性がより低い、または認識可能性が低い、または完全に利用不可能である、または完全に認識不可能であるように、格納されるオリジナルデータファイルが、ある形式の情報分散アルゴリズムを使用して、多数のファイル「スライス」またはサブセットに分散される、デジタルデータファイルのストレージシステムに関する。こうしたファイル共有は、プライバシーおよびセキュリティを向上させるために、個別のデジタルデータストレージデバイスに格納される。分散されたファイル共有は、分散されたストレージ位置のグリッド上に転送または格納されるため、様々なグリッドリソースは、動作不可能になり得るか、または最適基準未満で動作し得る。分散したファイル共有が利用不可能な分散ストレージグリッドリソースに書き込まれるように指定される場合、グリッドクライアントは再構築リスト（Ｒｅｂｕｉｌｄ Ｌｉｓｔ）上にその時点で書き込まれ得ない分散データ共有を指定する。さらに、既に分散データを格納しているグリッドリソースが利用不可能になると、分散ストレージグリッド内のプロセスは、再構築リストで再生成する必要があるその分散データ共有を指定する。他の時点において、個別プロセスは再構築リストのセットを読み込み、対応する分散データを生成し、利用可能なグリッドリソース上にそのデータを格納する。
【発明を実施するための最良の形態】
【００１２】
本発明のこれらの利点および他の利点は、添付の図面および明細書を参照すると、容易に明らかとなる。
【００１３】
（詳細な説明）
本発明は、データストレージシステムに関する。オリジナルデータのセキュリティを保護するために、オリジナルデータは、多数のデータ「スライス」またはサブセットに分かれている。本発明は、データファイルをファイルスライスまたはファイル「共有（ｓｈａｒｅ）」に分けるまたは分散するために使用することもできる。各スライスのデータ容量は、他のデータサブセットのいくつかまたは全てと結合させない限り、それ自体では、利用可能性がより低い、または認識可能性がより低い、または、完全に利用不可能である、または完全に認識不可能である。特に、本発明によるシステムは、オリジナルデータをデータサブセットに「スライス」し、符号化されたデータサブセットを生成するために、データサブセット上で符号化アルゴリズムを使用する。各データサブセットおよびその対応する符号化されたサブセットを、通信ネットワーク上で別々に転送し、ストレージノードのアレイの別々のストレージノードに格納してもよい。オリジナルデータを再生成するために、データサブセットおよび符号化されたサブセットは、各ストレージノードおよび各通信チャンネルの利用可能性および性能によって、いくつかのまたは全てのストレージノードまたは通信チャンネルから取得される。一連の復号アルゴリズムを取得されたデータおよび符号化されたデータに適用することによって、オリジナルデータが再生成される。
【００１４】
情報分散方法に基づく他の公知のデータストレージシステムによる場合と同様に、１つ以上のデータサブセットへの不正アクセスは、ソースデータについての分量の不十分な、または利用不可能な情報しか提供しない。
【００１５】
本発明を理解するため、ファイルまたはファイルのシステムを構成可能なＮ個の文字ｄ０，ｄ１，．．．，ｄＮの文字列を想定する。典型的なコンピュータファイルシステムはギガバイトのデータを含むことがあり、このことは、Ｎが数兆個の文字を含むことを意味する。以下の例では、データ文字列の長さＮがストレージノードの数ｎと等しい、かなり短い文字列を想定する。より大きなデータ文字列を格納するためには、こうした方法を何度も適用可能である。これらの方法はまた、コンピュータファイルまたは全ファイルシステムを格納するために、繰り返し適用され得る。
【００１６】
この例では、文字列がＯ Ｌ Ｉ Ｖ Ｅ Ｒという文字を含み、文字列には以下のようなＡＳＣＩＩ文字コードを含むことを仮定する。
ｄ０＝Ｏ＝７９
ｄ１＝Ｌ＝７６
ｄ２＝Ｉ＝７３
ｄ３＝Ｖ＝８６
ｄ４＝Ｅ＝６９
ｄ５＝Ｒ＝８２
文字列は、それぞれｎ個の文字であるセグメントに分割され、ここで、ｎは所望の計算効率のレベルを維持しながら所望の信頼性およびセキュリティ特性を提供するように選択される（典型的には、ｎは１００未満となるように選択される）。一実施形態において、その結果データの各サブセットが、例えば、オリジナルデータの４分の１未満を含み、結果として、各データサブセットの認識可能性が低下するように、ｎは４よりも大きくなるように選択され得る。
【００１７】
別の実施形態において、以下のように、第１のオリジナルデータセットが６個の異なるデータサブセットに分けられるように、ｎを６になるように選択する。
Ａ＝ｄ０、Ｂ＝ｄ１、Ｃ＝ｄ２、Ｄ＝ｄ３、Ｅ＝ｄ４、Ｆ＝ｄ５
例えば、オリジナルデータが、Ｏ Ｌ Ｉ Ｖ Ｅ Ｒというテキストの文字のＡＳＣＩＩ値の開始文字列である場合、データサブセットの値は以下のリストのようになる。
Ａ＝７９
Ｂ＝７６
Ｃ＝７３
Ｄ＝８６
Ｅ＝６９
Ｆ＝８２
この実施形態において、符号化されたデータの値は、オリジナルデータセット内の他のデータ値のサブセットからのデータ値を加算することで生成される。例えば、符号化された値は、以下のデータ値を加算することで生成できる。
ｃ［ｘ］＝ｄ［ｎ＿ｍｏｄ（ｘ＋ｌ）］＋ｄ［ｎ＿ｍｏｄ（ｘ＋２）］＋ｄ［ｎ＿ｍｏｄ（ｘ＋４）］
この式において、
ｃ［ｘ］は、符号化されたデータ値のセグメントアレイにおけるｘ番目の符号化されたデータ値である
ｄ［ｘ＋ｌ］は、データ値のアレイにおけるｘよりも大きい位置１における値である
ｄ［ｘ＋２］は、データ値のアレイにおけるｘよりも大きい位置２における値である
ｄ［ｘ＋４］は、データ値のアレイにおけるｘよりも大きい位置４における値である
ｎ＿ｍｏｄ（）は、数空間０からｎ―１においてモジュロ演算を実行する関数である
この式を使用して、以下の符号化された値を生成する。
ｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥ、ｃＦ
ここで、ｃＡは、例えば、Ｂ＋Ｃ＋Ｅと等しく、データ値Ａと共に通信および／または格納される符号化された値を表す。
【００１８】
例えば、オリジナルデータがＯ Ｌ Ｉ Ｖ Ｅ Ｒというテキストの文字のＡＳＣＩＩ値の開始文字列である場合、符号化されたデータサブセットの値は、以下のようになる。
ｃＡ＝２１８
ｃＢ＝２４１
ｃＣ＝２３４
ｃＤ＝２２７
ｃＥ＝２３４
ｃＦ＝２４１
本発明に従って、例示的なデータＡＢＣＤＥＦから成るオリジナルデータセット２０は、例えば、６個のデータサブセットＡ、Ｂ、Ｃ、Ｄ、ＥおよびＦにスライスされる。データサブセットＡ、Ｂ、Ｃ、Ｄ、ＥおよびＦも、以下で説明するように符号化されており、符号化されたデータサブセットｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥおよびｃＦを形成する。データサブセットＡ、Ｂ、Ｃ、Ｄ、ＥおよびＦならびに符号化されたデータサブセットｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥおよびｃＦは、例えば、図１に示されているように、複数のスライス２２、２４、２６、２８、３０および３２に形成される。各スライス２２、２４、２６、２８、３０および３２は、異なるデータ値Ａ、Ｂ、Ｃ、Ｄ、ＥおよびＦならびに異なる符号化されたサブセットｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥおよびｃＦを含む。スライス２２、２４、２６、２８、３０および３２は、インターネット等の通信ネットワークを介し、一連のデータ転送の形でシリーズに転送し、異なるデジタルデータストレージデバイスまたはストレージノード３４、３６、３８、４０、４２および４４に、それぞれ格納されてもよい。
【００１９】
オリジナルデータを取得するために（またはデータが転送されたばかりで格納されていない場合にはこれを受信するために）、データを、図２に示すように再構成可能である。各ストレージノード３４、３６、３８、４０、４２および４４からのデータ値は、インターネット等の通信ネットワークを通じて、受信先のコンピュータ（図示せず）に転送される。図２に示すように、受信先のコンピュータは、そのそれぞれが異なるデータ値Ａ、Ｂ、Ｃ、Ｄ、ＥおよびＦならびに異なる符号化された値ｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥおよびｃＦを含む、スライス２２、２４、２６、２８、３０および３２を受信する。
【００２０】
ストレージノード３４、３６、３８、４０、４２および４４または通信接続の利用停止または性能遅延等の様々な理由のために、時間データを再生成するたびに、必ずしも全てのデータスライス２２、２４、２６、２８、３０および３２が利用可能となるわけではない。図３は、データスライス２２、２４、２６、２８、３０および３２の１つ、例えば、データ値Ａを含むデータスライス２２および符号化された値ｃＡが利用不可能である場合に、本発明がオリジナルデータセットを再生成する条件を示す。この場合、オリジナルデータ値Ａは、以下のようにして求められる。
Ａ＝ｃＣ−Ｄ−Ｅ
ここで、ｃＣは符号化された値であり、ＤおよびＥは、スライス２６、２８および３０から利用可能なオリジナルデータ値であり、これらはそれぞれ、ノード３８、４０および４２から利用可能であると仮定する。この場合、不明なデータ値は、既知の符号化された値から既知のデータ値を減算することにより、符号化された値を生成するためにデータ値の一部を加算する符号化の式を逆にすることで、求められる。
【００２１】
例えば、オリジナルデータがＯ Ｌ Ｉ Ｖ Ｅ Ｒというテキストの文字のＡＳＣＩＩ値の開始文字列である場合、Ａのデータ値は、以下のようにして求められる。
Ａ＝２３４−８６−６９
従って、Ａ＝７９となり、これは、文字ＯのＡＳＣＩＩ値である。
【００２２】
他の場合において、オリジナルデータ値を求めるにはより詳細な復号式が必要となる。例えば、図４は、オリジナルデータ値Ａ、ＢおよびＥを含む６個のノードのうちの３個、３４、３６および４２、およびその対応する符号化された値ｃＡ、ｃＢおよびｃＥが利用不可能である、条件を示す。図４のこうした不明なデータ値Ａ、ＢおよびＥおよび対応物は、以下の式シーケンスを使用して再構築できる。
１．Ｂ＝（ｃＤ−Ｆ＋ｃＦ−ｃＣ）／２
２．Ｅ＝ｃＤ−Ｆ−Ｂ
３．Ａ＝ｃＦ−Ｂ−Ｄ
こうした式は、特定の式を実行する場合に、各式で必要とされるデータ値が利用可能になるよう、リストされた順で実行する。
【００２３】
例えば、オリジナルデータが、Ｏ Ｌ Ｉ Ｖ Ｅ Ｒというテキストの文字のＡＳＣＩＩ値の開始文字列である場合、Ｂ、ＥおよびＡのデータ値は、以下のようにして求められる。
１．Ｂ＝（２２７−８２＋２４１−２３４）／２
Ｂ＝７６
２．Ｅ＝２２７−８２−７６
Ｅ＝６９
３．Ａ＝２４１−７６−８６
Ａ＝７９
ｎ＝６であり、およびスライス２２、２４、２６、２８、３０および３２のうちの３つまでが、再生成の際に利用不可能である場合に、オリジナル全データＡＢＣＤＥＦの再生成のための方法を一般化するために、図５は、不明なデータを再生成する方法を決定するために利用可能なテーブルを含む。
【００２４】
このテーブルは、６個のストレージノードのうち１、２または３が利用不可能である、または利用不可能であると考えられるのに十分なほど遅く行われる、４０の異なる利用停止シナリオを示す。図５の表において、行の「Ｘ」は、そのノードからのデータおよび符号化された値が利用不可能であることを示す。「タイプ」の列は、ノードの空間パターンタイプが利用不可能であることを示す。「オフセット」の値は各利用停止シナリオを示す。オフセットは特定の利用停止シナリオおよびそのタイプの第１の利用停止シナリオの空間位置の差であるということを示す。
【００２５】
データ値は、アレイｄ［ｘ］によって示すことが可能であり、ここで、ｘは、データ値が格納されたノード番号である。符号化された値は、アレイｃ［ｘ］で表すことができる。
【００２６】
ｎ＝６である場合に１つのノードがストレージアレイにおいて利用不可能である、利用停止シナリオにおける不明なデータを再構成するには、以下の式を利用可能である。
ｄ［０＋ｏｆｆｓｅｔ］＝ｃ３ｄ（２，３，４，ｏｆｆｓｅｔ）
ここで、ｃ３ｄ（）は、以下のような擬似コンピュータソフトウェアコードの関数である。
【００２７】
【化１】
ここで、ｎ＿ｍｏｄ（）は、以前に定義された関数である。
【００２８】
ｎ＝６である場合に２つのノードがストレージアレイにおいて利用不可能である、利用停止シナリオにおける不明なデータを再構成するために、図６の表の以下の式を利用可能である。図６において、「利用停止タイプ番号」は、図５の対応する利用停止「タイプ」を示す。図６の「復号演算」は、復号演算が実行される順序を示す。図６の「復号化されたデータ」の列は、各不明なデータ値を生成する特定の復号演算を示す。
【００２９】
ｎ＝６である場合に３つのノードがストレージアレイにおいて利用不可能である、利用停止シナリオにおける不明なデータを再構成するために、図７の表の式を利用可能である。図７において、利用停止タイプ＝３の場合の第１の復号のための復号式の構造は、ｎ＝６である場合の他の復号式とは異なる構造であることに留意されたい。
【００３０】
グリッドからのデータを読み込む場合に全てのストレージノード５７が利用可能な訳ではないという状況に加えて、図８に示すように、全てのストレージノード５７が、分散ストレージグリッド４９へ書き込む際に利用可能であるわけではない場合がある。図８に示す例において、それぞれ参照番号３６および４０で識別される、ストレージノード１および３は、グリッドクライアント６４がグリッドへ書き込み中は利用不可能であると仮定される。こうした状況において、グリッドクライアント６４は、ストレージノード１および３にデータを格納するために他のストレージノード５７を選択してもよく、または、クライアント６４は、図９のステップ１に示すように、ストレージグリッド上の他のノードに格納される、リビルダリスト６６または重複するリビルダリストのセットに書き込んでもよい。概して、リビルダリスト６６は、不明なデータスライスを上記のように再生成できるように、不明なデータスライスをリスト表示する。ストレージノード１および３が動作していないこの例において、グリッドクライアント６４はグリッド上の他のストレージノード５７上にノード１および３に直接指定されたスライスを格納しないが、その代わりに、グリッドクライアント６４は、図１０に示すように、データスライスをリビルダリスト６６に追加する。
【００３１】
非動作のストレージノード１および３が後で再び動作可能になると、再構築エージェント６７と呼ばれるストレージグリッド上のプロセスを使用して、図９のステップ２、３および４に示されているように、不明なデータスライスを再構築することができる。上記の例を用いて、再構築エージェント６７はまず、ステップ２において、図１０の情報を読み込む。こうして、再構築エージェント６７は、まずは不明なスライスのデータ値を生成し、次に不明なスライスのそれぞれにおいて符号化された値を生成することによって、データスライスを再生成する。
【００３２】
この例で不明なデータ値を作成するために、再構築エージェント６７は、図５のテーブルを使用して、ノード１および３を有する６個のノードグリッドの利用停止タイプは、オフセット１を有する利用停止タイプ２であると決定する。この例において、再構築エージェント６７は、以下のような、図６の６個のノードグリッドのタイプ２利用停止の式を使用する。
【００３３】
【表１】
ＯＬＩＶＥＲという単語のオリジナルデータのＡＳＣＩＩ値と共に例のデータを使用すると、以下の式によって、不明な第１のデータ値が求められる。
ｄ１＝Ｃ０−ｄ２−ｄ４（第１の復号式）
図８のステップ３に示されるように、再構築エージェントはグリッド上のストレージノード５７から必要なデータスライスを取得し、次に、以下に示すように、第１の不明なスライスデータを再生成する。
Ｂ＝ｃＡ−Ｃ−Ｅ
Ｂ＝２１８−７３−６９
Ｂ＝７６
７６というＡＳＣＩＩ値は、ストレージノート１のオリジナルデータである文字「Ｌ」に相当する。第２の不明なオリジナルデータ値は、次のように求められる。
ｄ３＝ｃ２−ｄ４−ｄ０（第２の復号式）
ステップ３に示すように、図８において、再構築エージェントはグリッド上のストレージノード５７から必要なデータスライスを取得し、次に、以下に示すように、第２の不明なスライスデータを再生成する。
Ｄ＝ＣＣ−Ｅ−Ａ
Ｄ＝２３４−６９−７９
Ｄ＝８６
８６というＡＳＣＩＩ値は、ストレージノード３のオリジナルデータである文字「Ｖ」に相当する。
【００３４】
ストレージノード１および３の符号化されたデータ値の再生成は、オリジナルの符号化式を再び適用することで実行可能である。
ｃ［ｘ］＝ｄ［ｎ＿ｍｏｄ（ｘ＋ｌ）］＋ｄ［ｎ＿ｍｏｄ（ｘ＋２）］＋ｄ［ｎ＿ｍｏｄ（ｘ＋４）］
次に例の符号化されたデータ値を再生成すると、以下のようになる。
ｃＢ＝Ｃ＋Ｄ＋Ｆ
ｃＢ＝７３＋８６＋８２
ｃＢ＝２４１
ｃＤ＝Ｅ＋Ｆ＋Ｂ
ｃＤ＝６９＋８２＋７６
ｃＤ＝２２７
すると、図９のステップ４に示されているように、ＢおよびｃＢで成るデータスライスをストレージノード１に書き込むことが可能になり、ＤおよびｃＤで成るデータスライスをストレージノード３に書き込むことが可能になる。スライスを再構築するこの方法は、グリッドクライアントがグリッドに新規データを書き込んでいるためにストレージリソースが一時的に利用不可能である場合に、分散データを再構築するために利用可能である。
【００３５】
図１１は、ストレージリソースが永久に破損しているおよび新規リソースによって置換される場合に、スライスをどのように再構築できるかを示す。このシナリオにおいて、永久に失われたストレージリソースによって以前に保持されたデータスライスは、新規の、置換ストレージリソース上で再生成される。ステップ１において、グリッド管理者６８（自動プロセスまたは判断を下す人員にしてもよい）は、図１１のストレージノード５７によって示されるストレージリソースは永久に利用不可能であると決定する。グリッド管理者６８は、次に、以下の例示的な情報によって、ストレージノード５７内の置換データ領域を指定する：Ｖｏｌｕｍｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒ、Ｖｏｌｕｍｅ＿Ｌｏｃａｔｉｏｎ。この例において、Ｖｏｌｕｍｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒは、データスライスが以前に格納され、今は利用不可能であるデータ領域番号である。Ｖｏｌｕｍｅ＿Ｌｏｃａｔｉｏｎは、新規ストレージノード５７のネットワーク位置である。この例において、Ｖｏｌｕｍｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒは、番号７６５４によって示され、ネットワーク位置は１２３．１２３．１２３．１２３の形式のインターネットＩＰアドレスによって示すことができる。グリッド管理者６８は、再構築リストメーカ７０という分散ストレージグリッド上で実行されているプロセスへ、この情報を提供する。
【００３６】
図１１のステップ２に示されているように、再構築リストメーカ７０は、次に、以下に述べる、グリッドディレクタ５８という分散ストレージグリッド上のプロセスからボリューム、ユーザおよびファイル情報を得る。ボリュームは、ハードドライブ、サーバまたは複数の位置におけるサーバのグループで構成することのできるグリッド上のデータストレージプロセスである。ユーザは、特定のグリッドクライアント６４の名称である。この例において、ファイルは、グリッド上に分散しているオリジナルデータファイルの識別子である。以下でより詳細に説明するように、グリッドディレクタ５８は、グリッド上のボリューム、ユーザおよびファイル情報を追跡するプロセスである。再構築リストメーカ７０は、再構築予定のボリューム７６５４に関連付けられたユーザについての情報を提供するようグリッドディレクタ５８にリクエストし、図１２に示すようにグリッドディレクタ５８が返る。
【００３７】
図１２は、３人のユーザが、再構築予定のボリューム７６５４上にデータを有することを示す。こうしたユーザは、識別番号１２３４５６７、１２３４５６８および１２３４５６９を有する。再構築リストメーカ７０はさらに、グリッドディレクタ５８から、３人の影響を受けるユーザへとファイルを関連付けるテーブルをリクエストする。グリッドディレクタ５８は、図１３に示されるもののようにテーブルを返す。図１３は、再構築されるボリューム上にデータを格納するユーザに、６個のファイルが関連付けられていることを示す。
【００３８】
再構築リストメーカ７０は次に、再構築予定のデータ領域またはボリュームの喪失による影響を受けるこうしたファイルに関連付けられる、全スライスのリストを生成する。そのファイルから生成されるスライスセットに対応するダッシュおよび数を追加することにより、Ｆｉｌｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒを、対応するＳｌｉｃｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒに変換することができる。この例において、６個のノード分散ストレージグリッド上の各ファイルについて、再構築予定のボリュームの損失によって影響を受ける可能性があるファイルの全てのスライスを示すために、Ｓｌｉｃｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒｓの図１４に示すようなリストが生成される。
【００３９】
まず、図１４に示されるＳｌｉｃｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒの最初の６桁は、そのスライスを生成するのに使用されるＦｉｌｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒに相当する。Ｓｌｉｃｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒの最後の桁は、そのストライプまたはファイルスライスのセット内で識別される特定のスライスに相当する。
【００４０】
次に、図１１のステップ３に示されているように、再構築リストメーカ７０は、これらのユーザに関連付けられたグリッド上に現在格納されている全てのスライスのリストを生成するために、再構築予定のボリュームに関連付けられたユーザに関連付けられたグリッド上の全ストレージノード５７にクエリを実行する。
【００４１】
図１１のステップ３に示すように、再構築リストメーカ７０は、次に、再構築予定のボリュームによって影響を受けるユーザに関連付けられたグリッド上に格納される全スライスを決定するために、グリッド上の各ストレージノード５７にクエリを実行する。各ストレージノード５７は、図１５に示される形式のテーブルを、再構築リストメーカに返す。
【００４２】
再構築リストメーカ７０は、再構築予定のボリュームによって影響を受けるユーザに関連付けられたグリッド上に現在格納される全てのＳｌｉｃｅ＿Ｉｄｅｎｔｉｆｌｃａｔｉｏｎ＿Ｎｕｍｂｅｒｓを収集する。こうして、図１３に示される再構築予定のボリュームによって影響を受ける各ファイルに関連付けられた図１４に示される各スライスについて、再構築リストメーカ７０は、図１５に示すグリッド上に現在格納されているスライスのテーブルの１つにそのＳｌｉｃｅ＿Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ＿Ｎｕｍｂｅｒが表示されるかどうかを決定することによって、そのスライスがグリッド上に現在格納されているかどうかを決定する。
【００４３】
グリッド上に現在格納されていない各スライスについて、再構築リストメーカ７０は、図１１のステップ５に図示されているように、リビルダリスト６６へのエントリまたはリビルダリストのセットを追加する。図１１のステップ５、６、７および８を完了するためのプロセスは、次に、図９のステップ１、２、３、および４に以前に記載されているプロセスと同様に実行される。
【００４４】
こうしたタイプのデータ再構築方法は、全てのオリジナルデータを完全に復元している間に、ストレージグリッドが受容可能な様々な回数のストレージノード利用停止を有する様々な数のストレージノードを有する、信頼性のあるストレージグリッドを生成するために、ソフトウェア開発分野の当業者によって利用可能である
（情報分散ストレージシステムのメタデータ管理システム）
本発明の重要な態様に従って、例えば、図１〜図８に関して上述されているように、グリッドを形成する共通の通信ネットワークに結合されるいくつかのストレージノードに分散および格納される情報の分散およびストレージを管理するために、メタデータ管理システムを使用する。情報分散システムの信頼性を向上させるために、グリッド上のトランザクションのメタデータ属性は、分散データの個別のデータ領域に格納される。
【００４５】
上述のように、情報分散システムは、オリジナルデータをデータサブセットに「スライス」し、符号化されたデータサブセットを生成するために、データサブセット上で符号化アルゴリズムを使用する。オリジナルデータを再生成するために、データサブセットおよび符号化されたサブセットを、各ストレージノードおよび各通信チャンネルの利用可能性および性能に応じて、ストレージノードまたは通信チャンネルのいくつかのまたは全てから取得する。情報分散方法に基づく他の公知のデータストレージシステムと同様に、１つ以上のデータサブセットへの不正アクセスは、ソースデータについての量の不十分なまたは利用不可能な情報しか提供しない。例えば、図１に図示されているように、各スライス２２、２４、２６、２８、３０および３２は、異なるデータ値Ａ、Ｂ、Ｃ、Ｄ、ＥおよびＦならびに異なる「符号化されたサブセット」（符号化されたサブセットはアルゴリズムによって生成され、オリジナルサブセットの一部を使用して復元が完了すると、復元できるようデータスライスと共に格納される）ｃＡ、ｃＢ、ｃＣ、ｃＤ、ｃＥおよびｃＦを含む。スライス２２、２４、２６、２８、３０および３２は、インターネット等の通信ネットワーク上を、異なるデジタルデータストレージデバイスまたはストレージノード３４、３６、３８、４０、４２および４４に、連続しておよびそれぞれ格納された一連のデータ転送で、転送してもよい。各データサブセットおよびその対応する符号化されたサブセットを、通信ネットワーク上を個別に転送し、ストレージノードのアレイにおける個別のストレージノードに格納してもよい。
【００４６】
「ファイルストライプ」とは、特定のファイルに対応する一組のデータおよび／または符号化されたサブセットである。各ファイルストライプは、利用可能なストレージリソースまたはストレージノードとして、全体のグリッド内において、データストレージデバイスまたはストレージノード５７の異なるセット上に格納してもよく、または、ストレージノードは、異なるファイルとして経時的に変化し、グリッド上に格納してもよい。
【００４７】
「データ領域」は、特定のクライアント６４のデータを含むストレージグリッド４９の一部である。グリッドクライアントは、２つ以上のデータも利用してもよい。図１１のデータ領域テーブル１０６は、特定のクライアントに関連付けられた全データ領域を示す。典型的には、特定のグリッドクライアントは、データセキュリティおよびプライバシーを提供するために、他のグリッドクライアントのデータ領域を表示することはできない。
【００４８】
図１６は、概して参照番号４９で識別される、ストレージグリッドの異なるコンポーネントを示す。グリッド４９は、インターネット等の通信ネットワークに接続された他のグリッドクライアント（グループまたは個別の「ストレージノード５７」）に関連付けられた他のストレージノード５６と同様に、特定のグリッドクライアント６４に関連付けられたストレージノード５４を含む。グリッド４９はさらに、クライアントバックアップを管理するためのアプリケーションおよびデータ領域およびその関連付けられた収集に関する復元を含む。
【００４９】
概して、「ディレクタ」とは、グリッド４９上で実行するアプリケーションをいう。ディレクタは、以下のような様々な目的を果たす。
１．ユーザクライアントログインの中央化されているがコピー可能なポイントを提供する。ディレクタは、ユーザログイン情報を格納するグリッドアプリケーションにすぎない。
２．自律的に格納されたファイルのユーザごとのリストを提供する。全てのユーザクライアントは、１つおよび１つのみのディレクタと対話することによって、各ユーザの、グリッド上に格納されたファイルの全リストを獲得することができる。このファイルリストメタデータは、１つのプライマリディレクタにおいて、いくつかのバックアップディレクタへとコピーされる。
３．どのサイトがユーザスライスを含むかを追跡する。
４．他のノード特性についてのマネージャ認証証明書。
【００５０】
グリッド上のアプリケーションはメタデータ管理システムを形成し、プライマリディレクタ５８、セカンダリディレクタ６０および他のディレクタ６２を含む。各データ領域は必ず、任意の時点において、１つのおよび１つのみのプライマリディレクタ５８に関連付けられる。グリッドクライアント６４が任意のデータ領域演算（保存／取得）を試行する度に、グリッドクライアント６４は、そのデータ領域に関連付けられたプライマリディレクタ５８と共にその演算を調整する必要がある。他の事柄のうち、プライマリディレクタ５８は、各データ領域への限定されたロックを管理する。各プライマリディレクタ５８は、少なくとも１つ以上のセカンダリディレクタ６０を有する。システムの信頼性を高めるために、任意のデータ領域メタデータ更新（特に、ロックの更新）は、データ領域のプライマリディレクタ５８によって同期的にコピーされ、リクエストしているグリッドクライアント６４に認知状態を返す前に、そのセカンダリまたはバックアップディレクタ６０の全てへとコピーされる。さらに、信頼性の向上のために、グリッド上の他の全てのディレクタ６２も、メタデータ更新のコピーを同期的に受信してもよい。こうした構成において、全てのデータ領域メタデータが、グリッド４９全体にわたって、効率的にコピーされる。
【００５１】
本明細書において使用されている場合、プライマリディレクタ５８およびその関連付けられたセカンダリディレクタ６０は、さらに、関連付けられたディレクタ６０と呼ばれることもある。セカンダリディレクタ６０は、グリッドクライアント６４データ領域更新の動作中にプライマリディレクタ５８が障害を発生した場合に任意の認識されたメタデータ管理更新が失われないようにしている。セカンダリディレクタ６０の数およびグリッド４９のメタデータアクセス性能の間にはトレードオフが存在する。概して、セカンダリディレクタ６０の数が増えると、メタデータ更新の信頼性は高くなるが、メタデータ更新の応答時間は遅くなる。
【００５２】
関連付けられたディレクタ６６および他のディレクタ６２は、どのスライスが各ストレージノード５７に格納されているかを追跡しないが、各グリッドクライアント６４に関連付けられたストレージノード５７を追跡する。特定のノードが各クライアントで認識されると、各グリッドクライアント６４に関連付けられたスライスを決定するために、様々なストレージノード５７にコンタクトを取ることが必要である。
【００５３】
プライマリディレクタ５８が大部分のグリッドメタデータを制御しており、ストレージノード５７は以下の役割を果たしている。
１．ユーザのスライスを格納する。ストレージノード５７は、クライアントのマシンのユーザのファイルシステム構造を反映したファイルシステムのユーザスライスを格納する。
２．データベースにおけるストレージノード５７上のユーザごとのファイルのリストを格納する。ストレージノード５７は、スライスハッシュ化したシグナチャ（例：ＭＤ５ｓ）等の最小メタデータ属性を、データベースにおける各スライスの「行」に関連付ける。
【００５４】
グリッドは、一意のストレージボリュームシリアルナンバー（ボリュームＩＤ）によって各ストレージノード５７を識別し、このため、複数のサーバに分散している場合でも、ストレージボリュームを識別できる。オリジナルデータを再生成するために、データサブセットおよび符号化されたサブセットを、各ストレージノード５７および各通信チャンネルの利用可能性および性能に応じて、ストレージノード５７または通信チャンネルのいくつかのまたは全てから取得する。各プライマリディレクタ５８は、グリッド４９上の全てのストレージノード５７、つまり、各サイトにおいて利用可能な全ノードのリストを保持する。
【００５５】
以下は、バックアップ／復元プロセス中に使用される主なメタデータ属性のリストである。
【００５６】
【表２】
【００５７】
【表３】
図１７は、クライアントがストレージシステムと対話する場合の出来事のデータの流れおよび最上層の図を示す。図１８は、プロセスのユーザ情報を追跡するために使用される主なメタデータテーブルについて説明する。
【００５８】
図１７を参照すると、まずステップ７０において、グリッドクライアント６４は、グリッドにおいてサーバで実行されているディレクタアプリケーションへのログインで開始される。ログインが成功すると、ディレクタアプリケーションは、ステップ７２において、グリッドクライアント６４へ、ＤａｔａｓｐａｃｅＤｉｒｅｃｔｏｒＭａｐ９２（図１８）を返す。ディレクタアプリケーションは、ＤａｔａｓｐａｃｅＩＤを決定するために、グリッドクライアントのＡｃｃｏｕｎｔＩＤを参照するルックアップテーブル、ＡｃｃｏｕｎｔＤａｔａｓｐａｃｅＭａｐ９３を含む。次に、ＤａｔａｓｐａｃｅＤｉｒｅｃｔｏｒＭａｐ９２からグリッドクライアントのプライマリディレクタ（つまり、ＤｉｒｅｃｔｏｒＡｐｐＩＤ）を決定するためにＤａｔａｓｐａｃｅＩＤを使用する。
【００５９】
グリッドクライアント６４がそのプライマリディレクタ５８を認識すると、グリッドクライアント６４はＤａｔａｓｐａｃｅＶｏｌｕｍｅＭａｐ９４（図１８）をリクエストし、グリッドクライアント６４に関連付けられたストレージノード（つまり、ＶｏｌｕｍｅｌＤ）を決定するためにデータ領域ＩＤを使用できる。プライマリディレクタ５８は、トランザクションテーブル１０４（図１８）のグリッドクライアント６４のために、ＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔＩＤを設定する。ＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔＩＤは、各トランザクション（つまり、グリッドクライアント６４の各実行インスタンスまたはセッション）に一意である。特に、ＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔテーブル９６の一意のトランザクションＩＤを生成するために、ＤａｔａｓｐａｃｅＤｉｒｅｃｔｏｒＭａｐ９２からのデータ領域ＩＤを使用する。グリッド４９を有するグリッドクライアントの各セッションにおいて、それぞれのグリッドクライアント別に、全てのトランザクションを追跡するために、トランザクションＩＤはＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔＩＤと共にトランザクションテーブル１０４に格納される。
【００６０】
「ＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔｌｄ」のメタデータ属性は、クライアントが２つ以上のアクティブなトランザクション（関連されていない）と関連を持つことができるＴｒａｎｓａｃｔｉｏｎＩＤとは異なる属性であるが、常に、１つのみの「トランザクションコンテクストＩｄ」が、クライアントの１つの実行インスタンスに関連付けられる。こうしたメタデータ属性によって、異なるグリッドクライアントによる同時トランザクションの管理が可能になる。
【００６１】
上述のように、プライマリディレクタ５８は、各グリッドクライアント６４に関連付けられているストレージノード５７のリストを維持する。このリストは、ストレージノード（つまり、ＤａｔａｓｐａｃｅＩＤ）のＩＤおよびグリッドクライアント６４のＩＤ（つまり、ＩＤ）を維持するＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔテーブル９６として維持される。プライマリディレクタ５８は、プライマリディレクタ５８と通信するために、グリッドクライアント６４によって使用される「アプリケーション」メタデータ（つまり、Ａｐｐｌｉｃａｔｉｏｎｓテーブル１０４）を含む。トランザクションのタイプ（ＡｐｐＴｙｐｅＩＤ）を記録するためにＡｐｐｌｉｃａｔｉｏｎｓテーブル６４を使用し、例えば、トランザクション（つまり、ＳｉｔｅＩＤ）に関連付けられたデータスライスおよびストレージノード５７を追加または削除する。
【００６２】
任意のデータ転送が開始される前に、グリッドクライアント６４は、例えば、その生成日および修正日と共に、ファイルの名前およびサイズ等の、意図したトランザクションに関してプライマリディレクタ５８を有するメタデータを保管する。メタデータは、さらに、Ｔｒａｎｓａｃｔｉｏｎ Ｄａｔａｓｏｕｃｅｓテーブル９８に示される様々なフィールド等の他のメタデータ属性も含む。（図１８）トランザクションが完了するまでトランザクションを追跡するために、トランザクションデータソースメタデータテーブル９８を使用する。
【００６３】
上記の情報をグリッドクライアント６４およびプライマリディレクタ５８間で交換後、グリッドクライアント６４は、ファイルスライスの転送準備のために、ステップ７４において、ストレージノードに接続する。任意の情報を交換する前に、グリッドクライアント６４は、トランザクションデータソーステーブル９８においてデータフィールドを埋めるために、ステップ７６において、そのデータソーステーブル１００にメタデータを登録する。
【００６４】
次にステップ７８において、グリッドクライアント６４上で実行されるアプリケーションによって上述されるように、データスライスおよび符号化されたサブセットが生成される。データの任意のデータスクランブル、圧縮および／または暗号化は、データがスライスに分散される前または後に実行されるようにしてもよい。次に、データスライスは、ステップ８０においてストレージノード５７にアップロードされる。
【００６５】
アップロードが開始されると、グリッドクライアント６４は、ファイルメタデータ（つまり、ＤａｔａＳｏｕｒｃｅｓテーブル１００）を更新するために、トランザクションメタデータ（つまり、トランザクションデータソーステーブル９８からのデータ）を使用する。アップロードが完了すると、トランザクションデータソーステーブル９８からのデータソース情報がデータソーステーブル１００に移動し、ステップ８４、８６および８８において、トランザクションデータソーステーブル９８から削除される。このプロセスは本質的に「微小」なものであり、つまり、任意のインスタンスにおいてトランザクションに障害が起こった場合、変更は記録されない。データソーステーブル１００は、ユーザのファイルセットの完全性を保持するために改訂番号を含む。
【００６６】
図１９Ａおよび図１９Ｂに図示されている簡単な例は、メタデータ管理システム５０の動作を示す。この例は、クライアントはグリッド４９の「Ｍｙｆｉｌｅ．ｔｘｔ」という名前のファイルを保存したいと仮定する。
【００６７】
ステップ１：グリッドクライアントは、グリッド４９で実行されているディレクタアプリケーションに接続する。ディレクタアプリケーションはこのグリッドクライアント６４のプライマリディレクタ５８でないため、ディレクタアプリケーションは、グリッドクライアントを認証して、ＤａｔａｓｐａｃｅＤｉｒｅｃｔｏｒＭａｐ９２を返す。基本的に、ディレクタは、そのＤａｔａｓｐａｃｅＩＤを検索して対応するＤｉｒｅｃｔｏｒＡｐｐＩＤ（このクライアントのプライマリディレクタ）を返すために、ＡｃｃｏｕｎｔＩＤを使用する。
【００６８】
ステップ２：グリッドクライアント６４がＤａｔａｓｐａｃｅＤｉｒｅｃｔｏｒＭａｐ９２を得ると、ディレクタがそのプライマリディレクタであることが認識される。すると、グリッドクライアント６４はこのディレクタアプリケーションに接続し、プライマリディレクタは、グリッドクライアントセッションに一意の、上記で説明したＴｒａｎｓａｃｔｉｏｎＣｏｎｔｅｘｔＩＤを生成する。プライマリディレクタ５８はさらに、グリッドクライアント６４を、そのＤａｔａｓｐａｃｅＶｏｌｕｍｅＭａｐ９４（つまり、グリッドクライアント６４が接続する必要のあるストレージノード５７の数）に送る。グリッドクライアント６４は、ファイルメタデータをディレクタ（つまり、トランザクションデータソーステーブルにおいて必要なフィールド）に送信する。
【００６９】
ステップ３：クライアントで実行中のアプリケーションによって、「Ｍｙｆｉｌｅ．ｔｘｔ」のデータスライスおよび符号化されたサブセットは、上記のストレージアルゴリズムを用いて生成される。次に、グリッドクライアント６４は、ＤａｔａｓｐａｃｅＶｏｌｕｍｅＭａｐ９４について、グリッド４９上の様々なストレージノード５７に接続する。次に、グリッドクライアントがそのデータおよび符号化されたサブセットを、グリッド４９上の様々なストレージノード５７に送信する。
【００７０】
ステップ４：グリッドクライアント６４が、様々なストレージノード５７上のそのファイルスライスを保存して終了すると、グリッドクライアント６４は、ＴｒａｎｓａｃｔｉｏｎＤａｔａｓｏｕｒｃｅｓテーブル９８からのこのトランザクションを削除し、これをデータソーステーブル１００に追加するよう、プライマリディレクタアプリケーション５８に通知する。システムは、グリッドクライアント６４がデータソーステーブル１００上にない任意のファイルを取得することができないように構成される。このため、データソーステーブル１００上にファイルメタデータを追加することで、ファイル保存／バックアップの動作が完了する。
【００７１】
上述の内容から明らかであるように、プライマリディレクタ５８は、トランザクションが開始または終了する時間を決定するアプリケーションである。トランザクションはプライマリディレクタ５８がストレージノード５７のメタデータをグリッドクライアント６４に送信する前に開始され、データソーステーブル１００上のデータソースについての情報の書き込み後に終了する。この構成により、完全性が保証される。このように、プライマリディレクタ５８がトランザクションに完了したと報告する場合、そのトランザクションを表示する任意のアプリケーションは、全ての他のストレージノードがトランザクションのために適正に更新されていることを認識する。この「アトミックトランザクション（Ａｔｏｍｉｃ Ｔｒａｎｓａｃｔｉｏｎ）」の概念は、ストレージシステムの完全性を維持するために重要である。例えば、更新トランザクション全体が完了していない場合、および異なるストレージノードの全てが適切に「同期されている」訳ではない場合、少なくとも、動作中のグリッドクライアント６４のデータ領域テーブル１００についてストレージシステムは混乱状態になっている。そうでない場合、トランザクションが任意の理由で中断された（例：バックアッププロセス中にクライアントのＰＣの電源をオフにした）ために不完全な状態となっている場合、システムの全体的なデータ保全性はかなり迅速に悪化する。
【００７２】
本発明の多くの修正例および変形例が、上記の教示に照らして可能であることが明らかである。このように、添付の特許請求の範囲内において上記の詳細な説明以外にも、本発明を実行可能であることが理解されよう。
【００７３】
特許請求の内容および米国の特許証によって保証されることが望ましい内容は、特許請求の範囲のとおりである。
【図面の簡単な説明】
【００７４】
【図１】図１は、本発明に従う、６個のストレージノードを有する例示的なデータストレージシステムのブロック図であり、オリジナルデータファイルがどのようにファイル共有に分散され、符号化され、個別のデジタルデータストレージデバイスまたはノードに転送されるかを示す。
【図２】図２は、図１と類似しているが、オリジナルデータセットを生成するために例示的な６個の全ノードからのデータサブセットがどのように取得および復号されるかを示している。
【図３】図３は、図２と類似しているが、６個のデジタルデータストレージデバイスのうちの１つの障害の状態を示している。
【図４】図４は、図３と類似しているが、６個のデジタルデータストレージデバイスのうちの３個の障害の状態を示している。
【図５】図５は、例示的な６個のデジタルデータストレージデバイスに格納されているデータを再生成するために利用可能な、本発明に従う例示的なテーブルである。
【図６】図６は、２個のノードの利用停止の状態のために、例示的な６個のノードのストレージデータストレージシステムの復号式をリスト表示する例示的なテーブルである。
【図７】図７は、図６と類似しているが、３個のノードの利用停止の状態について示している。
【図８】図８は、図２と類似しているが、データをストレージグリッドに書き込み中の、６個のデジタルデータストレージデバイスのうちの１個の障害の状態について示している。
【図９】図９は、新しいデータのストレージグリッドへの書き込み中にストレージリソースが利用不可能である場合にデータを再構築する、例示的なデータ再構築システムのブロック図である。
【図１０】図１０は、再構築リストテーブルのエントリをリスト表示する、例示的なテーブルである。
【図１１】図１１は、ストレージリソースが置換された場合にデータを再構築する、例示的なデータ再構築システムのブロック図である。
【図１２】図１２は、ボリューム識別番号およびユーザ識別番号のマッピングテーブルにおけるエントリをリスト表示する例示的なテーブルである。
【図１３】図１３は、ユーザ識別番号およびファイル識別番号マッピングテーブルのエントリをリスト表示する例示的なテーブルである。
【図１４】図１４は、特定のファイルに関連付けられたスライス識別番号のテーブルのエントリをリスト表示する例示的なテーブルである。
【図１５】図１５は、ユーザ識別番号およびスライス識別番号マッピングテーブルのエントリをリスト表示する例示的なテーブルである。
【図１６】図１６は、本発明に従う、情報分散ストレージシステムと共に使用するメタデータ管理システムの様々な機能要素を示す、本発明に従う例示的な図である。
【図１７】図１７は、分散データストレージグリッド上に格納されているデータのメタデータを保守するためのプロセスを示す例示的なフローチャートである。
【図１８】図１８は、ユーザトランザクションおよびユーザファイルセットルックアップ時に使用される必須のメタデータコンポーネントを示す。
【図１９Ａ】図１９Ａおよび図１９Ｂは、システムの動作を示す。
【図１９Ｂ】図１９Ａおよび図１９Ｂは、システムの動作を示す。
【特許請求の範囲】
【請求項１】
Ｎ個の文字の文字列を格納する方法であって、該方法は、
（ａ）ｎ個のデータスライスにＮ個の文字の文字列をセグメント化するステップと、
（ｂ）該ｎ個のデータスライスのそれぞれを、該データスライスの符号化された値と共に、異なるストレージノードへ格納するステップと、
（ｃ）１つ以上のストレージノードが利用不可能である場合には、該データスライスを再生成するステップと
を包含する、方法。
【請求項１】
Ｎ個の文字の文字列を格納する方法であって、該方法は、
（ａ）ｎ個のデータスライスにＮ個の文字の文字列をセグメント化するステップと、
（ｂ）該ｎ個のデータスライスのそれぞれを、該データスライスの符号化された値と共に、異なるストレージノードへ格納するステップと、
（ｃ）１つ以上のストレージノードが利用不可能である場合には、該データスライスを再生成するステップと
を包含する、方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９Ａ】
【図１９Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９Ａ】
【図１９Ｂ】
【公表番号】特表２００９−５３３７５９（Ｐ２００９−５３３７５９Ａ）
【公表日】平成２１年９月１７日（２００９．９．１７）
【国際特許分類】
【出願番号】特願２００９−５０５３７４（Ｐ２００９−５０５３７４）
【出願日】平成１９年３月２２日（２００７．３．２２）
【国際出願番号】ＰＣＴ／ＵＳ２００７／００７１２０
【国際公開番号】ＷＯ２００７／１２０４２９
【国際公開日】平成１９年１０月２５日（２００７．１０．２５）
【出願人】（５０８２６３０４０）クレーバーセーフ， インコーポレイテッド (1)
【Ｆターム（参考）】
【公表日】平成２１年９月１７日（２００９．９．１７）
【国際特許分類】
【出願日】平成１９年３月２２日（２００７．３．２２）
【国際出願番号】ＰＣＴ／ＵＳ２００７／００７１２０
【国際公開番号】ＷＯ２００７／１２０４２９
【国際公開日】平成１９年１０月２５日（２００７．１０．２５）
【出願人】（５０８２６３０４０）クレーバーセーフ， インコーポレイテッド (1)
【Ｆターム（参考）】
[ Back to top ]