(57)【要約】  本発明は、一般に、分散型データ記憶システムに関する。特に、本発明は、データ・ブロックのクラスタ化と、記憶方法および関連する修復方法に関する所要記憶スペースおよびデバイス間通信コストの点で分散型データ記憶システムを効率化するデータ・ブロックのランダム線形結合の使用とを含む、分散型データ記憶システムにおいてデータを記憶する方法に関する。
2015519648.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク中で相互接続された複数の記憶デバイスを含む分散型データ記憶システムにデータ・ファイルを記憶する方法であって、前記分散型データ記憶システムに記憶する前記データ・ファイルごとに実行される、以下のステップ、すなわち
前記データ・ファイルをｋ個のデータ・ブロックに分割し、前記ｋ個のデータ・ブロックのランダム線形結合によって前記ｋ個のデータ・ブロックから少なくともｎ個の符号化データ・ブロックを作成するステップと、
前記ファイルの前記少なくともｎ個の符号化データ・ブロックを、同じ記憶デバイス・クラスタに含まれている前記少なくともｎ個の記憶デバイスにわたって拡散させることによって、前記少なくともｎ個の符号化データ・ブロックを記憶するステップであり、各クラスタが、異なる記憶デバイスのセットを含み、前記ファイルの前記少なくともｎ個の符号化データ・ブロックが、各記憶デバイス・クラスタが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶し、且つ１つの記憶デバイス・クラスタの前記記憶デバイスのそれぞれが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶するように、１つの記憶デバイス・クラスタの前記少なくともｎ個の記憶デバイスにわたって分散されるステップと、を含む、前記方法。
【請求項２】
請求項１に記載の方法に従ってデータが記憶され、記憶されたファイルがｋ個のデータ・ブロックに分割される分散型データ記憶システムにおいて故障した記憶デバイスを修復する方法であって、以下のステップ、すなわち
前記故障した記憶デバイスが属している記憶デバイス・クラスタに置換記憶デバイスを追加するステップと、
前記置換記憶デバイスが、前記記憶デバイス・クラスタ内のｋ＋１個の残りの記憶デバイスのうちの何れかから、前記ｋ＋１個の記憶デバイスのそれぞれが記憶している２つの異なるファイルＸおよびＹの２つの符号化データ・ブロックから生成されるｋ＋１個の新たなランダム線形結合を受け取るステップと、
代数演算を使用して、受け取った前記新たなランダム線形結合をそれらの間で結合して、ファイルＸのみに関係するものが１つとファイルＹのみに関係するものが１つの２つのブロックが得られる２つの線形結合を得るステップと、
前記２つの線形結合を前記置換記憶デバイスに記憶するステップと、を含む、前記方法。
【請求項３】
前記分散型データ・システムに復帰する故障した記憶デバイスを前記記憶デバイス・クラスタに再統合するステップを含む、請求項２に記載の方法。
【請求項４】
ネットワーク中で相互接続された複数の記憶デバイスを含む分散型データ記憶システムにおいてデータ・ファイルの記憶を管理するデバイス（７００）であって、以下の手段、すなわち
前記データ・ファイルをｋ個のデータ・ブロックに分割し、前記ｋ個のデータ・ブロックのランダム線形結合によって前記ｋ個のデータ・ブロックから少なくともｎ個の符号化データ・ブロックを作成するデータ・スプリッタ（７０１）と、
前記ファイルの前記少なくともｎ個の符号化データ・ブロックを同じ記憶デバイス・クラスタに含まれる前記少なくともｎ個の記憶デバイスにわたって拡散させることによって、前記少なくともｎ個の符号化データ・ブロックを記憶する記憶配分器（７０２）であり、各クラスタが、異なる記憶デバイスのセットを含み、前記ファイルの前記少なくともｎ個の符号化データ・ブロックを、各記憶デバイス・クラスタが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶し、且つ１つの記憶デバイス・クラスタの前記記憶デバイスのそれぞれが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶するように、１つの記憶デバイス・クラスタの前記少なくともｎ個の記憶デバイスにわたって分散させる記憶配分器（７０２）と、を備える、前記デバイス（７００）。
【請求項５】
請求項１に記載の方法に従ってデータが記憶され、記憶されたファイルがｋ個のデータ・ブロックに分割される分散型データ記憶システムにおいて故障した記憶デバイスの修復を管理するデバイス（７１０）であって、以下の手段、すなわち
前記故障した記憶デバイスが属している記憶デバイス・クラスタに置換記憶デバイスを追加する置換器（７１１）と、
前記記憶デバイス・クラスタ内のｋ＋１個の残りの記憶デバイスのうちの何れかから前記置換記憶デバイスに、前記ｋ＋１個の記憶デバイスのそれぞれが記憶している２つの異なるファイルＸおよびＹの２つの符号化データ・ブロックから生成されたｋ＋１個の新たなランダム線形結合を分配する配分器（７１２）と、
代数演算を用いて前記新たなランダム線形結合をそれらの間で結合して、Ｘのみに関係するものが１つとＹのみに関係するものが１つの２つのブロックが得られる２つの線形結合を得る結合器（７１６）と、
前記２つの線形結合を前記置換記憶デバイスに記憶するデータ書込み器（７１７）と、を備える、前記デバイス（７１０）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、分散型データ記憶システムに関する。特に、本発明は、データ可用性が高いことと、ネットワーク記憶デバイス間のデータの交換に必要な帯域幅の点、およびデータ項目を記憶するために必要なネットワーク記憶デバイスの数の点でネットワークおよびデータ記憶リソースへの影響が小さいこととを兼ね備えた、分散型データ記憶システムにおいてデータを記憶する方法に関する。本発明は、また、このような分散型データ記憶システムにおいて故障した記憶デバイスを修復する方法、および本発明を実施するデバイスにも関する。
【背景技術】
【０００２】
映像および画像を扱うデバイスなど、大量のデータを扱うデバイスの導入が急速に広がっており、直接記憶のために、またはバックアップ記憶の一部として、大量のデータを高い信頼性で記憶することが必要とされている。ネットワーク接続性を備えるデバイスが増えるにつれて、ネットワーク接続されたデバイス（「記憶デバイス」）へのデータの分散型記憶は、費用対効果の高い解決策であると考えられるようになっている。インターネットなど、非管理ネットワーク上に展開することができるこのような分散型データ記憶システムでは、同じデータ項目を複数のネットワーク接続デバイスにコピーして、データ可用性とデータ喪失耐性とを保証する方法が開発されている。これは、データ・レプリケーションまたは冗長性追加と呼ばれる。冗長性は、広い意味で解釈する必要があり、単なるデータの複製だけでなく、消去符号または再生符号などのコード化技術を使用することも含む（耐障害性のために符号化データが記憶デバイスに配置される）。デバイスの障害によって永久にデータが失われる危険性、または一時的にデバイスが利用不能になることによって一時的にデータが失われる危険性に対処するためには、冗長性が高いことが望ましい。しかし、通信および必要な記憶サイズ（いわゆるレプリケーション・コスト）の点でコストを低下させるためには、むしろ冗長性が低いことが望ましい。
【０００３】
従って、冗長性は、信頼性の低い構成要素に基づいて信頼性の高いサービスを提供しなければならない実際のいかなるシステムでも、重要な特徴である。記憶システムは、不可避のディスクの利用不能性および障害をマスクするために冗長性を利用するサービスの代表例である。上述のように、この冗長性は、基本的なレプリケーションまたはコード化技術を用いて実現することができる。消去符号は、基本的なレプリケーションよりはるかに高い効率を実現することができるが、現行のシステムでは完全には導入されていない。消去符号を使用する際の大きな懸念は、符号化／復号動作によって複雑さが増すことを除けば、故障した記憶デバイスの保守によるものである。実際に、記憶デバイスが故障すると、データの耐久性を保証するためには、その記憶デバイスが記憶していた様々なファイルの全てのブロックを置換しなければならない。これは、喪失したブロックごとに、新たなブロックを１つだけ再生するために、そのブロックの出所であるファイル全体をダウンロードして復号しなければならないということである。基本的なデータ・レプリケーションと比較したときのこの帯域幅および復号動作のオーバヘッドにより、障害つまり修復が例外的なものでなく一般的なものであるシステムにおいて消去符号を使用することは、かなり制限される。それでも、ネットワーク・コード化を使用すれば、保守プロセス中に必要となる帯域幅を大幅に減少させることができる。こうして、符号化されているファイルの保守に対処するように特に設計され、消去符号の既知の欠点を軽減しながら消去符号の効率性を利用する、新たな分散型記憶システムが登場する下地ができた。
【０００４】
高いレベルのデータ可用性を実現する、可用性要件とレプリケーション・コストを併せて考慮した分散型データ記憶手段が必要とされている。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、従来技術の欠点のいくつかを改善することを目的とする。
【課題を解決するための手段】
【０００６】
分散型データ記憶システムにおけるデータ記憶を最適化するために、本発明は、ネットワーク中で相互接続された複数の記憶デバイスを含む分散型データ記憶システムにデータを記憶する方法であって、前記分散型データ記憶システムに記憶するデータ・ファイルごとに実行される、
前記データ・ファイルをｋ個のデータ・ブロックに分割し、前記ｋ個のデータ・ブロックのランダム線形結合によって前記ｋ個のデータ・ブロックから少なくともｎ個の符号化データ・ブロックを作成するステップと、
前記ファイルの前記少なくともｎ個の符号化データ・ブロックを、同じ記憶デバイス・クラスタに含まれている前記少なくともｎ個の記憶デバイスにわたって拡散させることによって、前記少なくともｎ個の符号化データ・ブロックを記憶するステップであり、各クラスタが、異なる記憶デバイスのセットを含み、前記ファイルの前記少なくともｎ個の符号化データ・ブロックが、各記憶デバイス・クラスタが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶し、且つ１つの記憶デバイス・クラスタの記憶デバイスのそれぞれが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶するように、１つの記憶デバイス・クラスタの前記少なくともｎ個の記憶デバイスにわたって分散されるステップと、を含む方法を提案する。
【０００７】
本発明は、また、本発明の記憶方法に従ってデータが記憶され、記憶されたファイルがｋ個のデータ・ブロックに分割される分散型データ記憶システムにおいて故障した記憶デバイスを修復する方法であって、
前記故障した記憶デバイスが属している記憶デバイス・クラスタに置換記憶デバイスを追加するステップと、
前記置換記憶デバイスが、前記記憶デバイス・クラスタ内のｋ＋１個の残りの記憶デバイスのうちの何れかから、前記ｋ＋１個の記憶デバイスのそれぞれが記憶している２つの異なるファイルＸおよびＹの２つの符号化データ・ブロックから生成されるｋ＋１個の新たなランダム線形結合を受け取るステップと、
代数演算を使用して、受け取った前記新たなランダム線形結合をそれらの間で結合して、ファイルＸのみに関係するものが１つとファイルＹのみに関係するものが１つの２つのブロックが得られる２つの線形結合を得るステップと、
前記２つの線形結合を前記置換記憶デバイスに記憶するステップと、を含む方法も含む。
【０００８】
この修復方法の変形実施形態によれば、この修復方法は、前記分散型データ・システムに復帰する故障した記憶デバイスを前記記憶デバイス・クラスタに再統合するステップを含む。
【０００９】
本発明は、また、ネットワーク中で相互接続された複数の記憶デバイスを含む分散型データ記憶システムでデータ・ファイルの記憶を管理するデバイスであって、前記データ・ファイルをｋ個のデータ・ブロックに分割し、前記ｋ個のデータ・ブロックのランダム線形結合によって前記ｋ個のデータ・ブロックから少なくともｎ個の符号化データ・ブロックを作成するデータ・スプリッタを備え、前記ファイルの前記少なくともｎ個の符号化データ・ブロックを同じ記憶デバイス・クラスタに含まれる前記少なくともｎ個の記憶デバイスにわたって拡散させることによって、前記少なくともｎ個の符号化データ・ブロックを記憶する記憶配分器であり、各クラスタが、異なる記憶デバイスのセットを含み、前記ファイルの前記少なくともｎ個の符号化データ・ブロックを、各記憶デバイス・クラスタが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶し、且つ１つの記憶デバイス・クラスタの記憶デバイスのそれぞれが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶するように、１つの記憶デバイス・クラスタの前記少なくともｎ個の記憶デバイスにわたって分散させる記憶配分器をさらに備えるデバイスも含む。
【００１０】
本発明は、また、本発明の記憶方法に従ってデータが記憶される分散型データ記憶システムにおいて故障した記憶デバイスの修復を管理するデバイスにも関する。この修復を管理するデバイスは、前記故障した記憶デバイスが属している記憶デバイス・クラスタに置換記憶デバイスを追加する置換器と、前記記憶デバイス・クラスタ内のｋ＋１個の残りの記憶デバイスのうちの何れかから前記置換記憶デバイスに、前記ｋ＋１個の記憶デバイスのそれぞれが記憶している２つの異なるファイルＸおよびＹの２つの符号化データ・ブロックから生成されたｋ＋１個の新たなランダム線形結合を分配する配分器と、代数演算を用いて前記新たなランダム線形結合をそれらの間で結合して、Ｘのみに関係するものが１つとＹのみに関係するものが１つの２つのブロックが得られる２つの線形結合を得る結合器と、前記２つの線形結合を前記置換記憶デバイスに記憶するデータ書込み器とを備える。
【００１１】
本発明のさらなる利点は、本発明の具体的な非制限的な実施形態の説明から、明らかになるであろう。
【００１２】
実施形態について、以下の図面を参照して説明する。
【図面の簡単な説明】
【００１３】
【図１】本発明の記憶方法の具体的な詳細を示す図である。
【図２】本発明の記憶方法によるデータのクラスタ化の例を示す図である。
【図３】記憶デバイスの障害の修復プロセスを示す図である。
【図４】本発明を実施することができるデバイスを示す図である。
【図５】本発明の方法の特定の実施形態を実施するアルゴリズムを示す図である。
【図６ａ】ネットワーク中で相互接続された複数の記憶デバイスを含む分散型データ・システムにおけるデータ・ファイルの記憶を管理するデバイスを示す図である。
【図６ｂ】本発明の記憶方法に従ってデータが記憶される分散型データ記憶システムにおける故障した記憶デバイスの修復を管理するデバイスを示す図である。
【発明を実施するための形態】
【００１４】
上述のように、消去符号は、データ記憶システムの基本的なレプリケーションよりはるかに高い効率を実現することができることが分かっている。それでも実際には、このような記憶システムへの消去符号の適用は、その明白な利点にもかかわらず普及していない。消去符号が比較的適用されていない理由の１つは、現況技術のコード化方法では、ブロックを挿入または修復する必要が生じるたびに新たな記憶デバイスが発見される可能性があると考えている、すなわち、無制限の記憶デバイスのリソースが存在すると仮定しているからである。さらに、記憶デバイスの可用性も、考慮されていない。この２つの前提条件が、現在の分散型データ記憶システムに消去符号を単純に適用することの実際上の障壁となり、これらの重要な問題の答えとなる設計の選択を行わなければならないときに混乱を生じている。これらの欠点を解消するために、本発明は、分散型データ記憶システムの冗長性を構成するデータ・ブロックのホスティングを担当する記憶デバイスのクラスタ化を提案し、さらに、消去符号を使用および展開する実際上の手段を提案する。次いで、本発明は、単純なレプリケーション方式およびコード化方式の両方と比較して優位に性能を向上させることを可能にする。本発明によるクラスタ化によって、個々のファイル・レベルではなく記憶デバイス・レベル（すなわち多数のファイルの多数のブロックを含む記憶デバイス）で保守を行うことが可能になり、消去符号を適用することによって、効率的なデータ・レプリケーションが可能になり、それにより、複数の修復を利用し、分散型データ記憶システムの性能向上を改善することができる。
【００１５】
消去符号の効率は、最大距離分離（ＭＤＳ）符号を使用するときに最大となり、いわゆる「最適」となる。これは、所与の記憶オーバヘッドに対して、ＭＤＳ符号が、データ可用性という点では可能な限り最高の効率を与えるということである。ＭＤＳ符号は、喪失したデータを再構築するのに、ｎ個の冗長性ブロック（＝符号化データ・ブロック）のうちのｋ個からなる任意のサブセットで十分であるような符号である。これは、Ｍバイトのファイルを再構築するためには、正確にＭバイトをダウンロードする必要があるということである。リード・ソロモン（ＲＳ）は、ＭＤＳ符号の旧来の例である。ランダム性によって、ＭＤＳ符号を構築する柔軟な方法が得られる。
【００１６】
本発明は、ネットワーク中で相互接続された複数の記憶デバイスを含む分散型データ記憶システムにデータ・ファイルを記憶する特定の方法を提案する。この方法は、分散型データ記憶システムに記憶するデータ・ファイルごとに実行される、以下のステップを含む。
データ・ファイルをｋ個のデータ・ブロックに分割し、これらのｋ個のデータ・ブロックのランダム線形結合によってこれらのｋ個のブロックからｎ個の符号化データ・ブロックを作成するステップ。
このファイルのこれらのｎ個の符号化データ・ブロックを、同じ記憶デバイス・クラスタに含まれているｎ個の記憶デバイスにわたって拡散するステップ。各クラスタは、異なる記憶デバイスのセットを含み、このファイルのこれらのｎ個の符号化データ・ブロックは、各記憶デバイス・クラスタが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶し、且つ１つの記憶デバイス・クラスタの記憶デバイスのそれぞれが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶するように、１つの記憶デバイス・クラスタのｎ個の記憶デバイスにわたって分散される。
【００１７】
図１は、１つのファイルがｋ＝２個のデータ・ブロックに分割される本発明の記憶方法の具体例、ならびにそれに関連するｎ＝４個の符号化データ・ブロックを生成する線形結合方法を示す図である。これは、次のように行われる。すなわち、各ファイルＸ（１０）を、同じ大きさのｋ個のデータ・ブロック（１２、１３）にチャンク化し、次いで、これらのｋ個のブロックのランダム線形結合としてｎ個の符号化データ・ブロックＸｊ（１５、１６、１７、１８）を作成する。次いで、分散型記憶システムの各記憶デバイスｊが、これらのｋ個のデータ・ブロックのランダム線形結合である符号化データ・ブロックＸｊを記憶する。関連するランダム係数α（例えばブロック１５では２および７）は、体Ｆｑで一様にランダムに選択される。すなわち、Ｆｑは、ｑ個の要素を有する「有限体」の意味である。有限体を利用することは、誤り訂正符号を実施するのに必要であり、当業者には既知である。簡単に言うと、有限体とは、離散数のセットなど１組の数のセットであるが、離算数で一般に既知であるように異なる加算と乗算の規則を有するセットである。
【００１８】
ｎ個の符号化データ・ブロックＸｊ（１５〜１８）を記憶するだけでなく、関連するランダム係数αも記憶する必要がある。ランダム係数の大きさはブロックＸｊの大きさと比較して無視できるので、これらの係数を記憶するために必要な記憶スペースも、無視することができる。一般に、本明細書で（ランダム）線形結合という表現を用いるときには、関連する係数も含む。
【００１９】
実際の例として、ファイルＸ（１０）がＭ＝１ギガバイトの大きさを有する場合を考える。パラメータｋ（ファイル・チャンクの数）およびｎ（ｋ個のファイル・チャンクのランダム線形結合の数）は、例えばｋ＝２、およびｎ＝４など、符号の実施が存在するように選択される。関連するランダム係数αは、１からｑの範囲の離散数を生成するようにパラメータ化された従来技術の乱数発生器で生成することができる。
【００２０】
ｎ／ｋは、分散型記憶システムの設計者が希望する冗長性レベルに応じて選択される。例えば、ｋ＝２、およびｎ＝４の符号では、発明者等は、ｎ／ｋ＝２とし、従って、１Ｇｂのファイルを記憶するためには、システムは２Ｇｂの記憶スペースを必要とする。さらに、ｎ／ｋは、システムが許容することができる障害の数（故障した記憶デバイスの数）を表す。ｋ＝２、ｎ＝４とした例では、ｋ＝２個の符号化データ・ブロックが残っている限り、元のファイルを回復することができる。従って、導入する冗長性の量と、分散型記憶システムの障害許容度との間の兼ね合いがある。
【００２１】
このようにして分散型記憶システムに記憶されたファイルの再構築は、次のように行われる。数学的には、ｋ個のデータ・ブロックからランダム線形結合によってこのようにして作成されたｎ個の符号化データ・ブロックＸｊはそれぞれ、これらのｋ個のデータ・ブロックが及んでいるサブスペースのランダム・ベクトルとして表すことができる。従って、ファイルＸの再構築には、このサブスペース中でｋ個の独立したベクトルを得れば十分である。この独立性要件は、関連するランダム係数αがそれ以前にファイルＸの記憶中に上述の乱数発生器によって生成されているので、満たされる。実際には、１次独立であるｋ個のベクトルの全てのファミリが、反転させることができる正則行列を形成するので、ファイルＸは、非常に高い確率（すなわち１に近い確率）で再構築することができる。あるいは、より正式には、Ｄを、Ｆｑｎに属するｎ個の冗長ブロックＸｊ、換言すればｎ個のランダム・ベクトルが及んでいるサブスペースの次元を表すランダムな変数とすると、次のように表すことができる。
【数１】
2015519648.tif 000003
【００２２】
この数式は、ｍ個のランダム・ベクトルが及んでいるサブスペースの次元が正確にｎであり、これらのｎ個のベクトルのファミリが１次独立である確率を与えるものである。この確率は、通常は２８または２１６である実際の体の大きさを使用するときには、全てのｎに対して１に非常に近いことが分かっている。上述のように、体の大きさは、有限体Ｆｑの要素の数である。値２８または２１６は、有限体の１つの要素はそれぞれ１バイトまたは２バイト（８ビットまたは１６ビット）に相当するので、実際の値である。例えば、体の大きさが２１６で、ｎ＝１６である（これらは伝統的な実際値である）場合には、正確にｎ＝１６個の記憶デバイスに接触するときには、ファイルＸを再構築することができる確率は、０．９９９９８５である。このように、ランダムな（ＭＤＳ）符号は、データを最適に符号化する柔軟な方法を提供する。これらの符号は、固定された符号化行列を使用し、従ってレートｋ／ｎが固定されている、すなわち冗長性システムが一定数を超える数の冗長な独立したブロックを作成することができない、伝統的な消去符号とは異なる。実際に、本発明で提案するランダム符号を使用するときには、単にファイルＸのｋ個のブロックＸｊの新たなランダム結合を作成するだけで、冗長ブロックＸｊを必要なだけ生成することができるので、レートの概念は消滅する。この性質により、ランダム符号は、噴水符号（ｆｏｕｎｔａｉｎ  ｃｏｄｅ）とも呼ばれるレート・レス符号となる。このレート・レスの性質により、以下でさらに述べるように、誤って「喪失」とされた記憶デバイスの再統合が可能になるので、これらの符号は、分散型記憶システムの状況に非常に適している。
【００２３】
上述の喪失したデータの修復を容易且つ効率的にする（上述のパラメータｋ、ｎの）ＭＤＳ消去符号の使用に関連して、本発明は、複数のファイルに属する喪失データの同時修復を活用する特定のデータ・クラスタ化方法を利用することを提案する。クラスタの大きさは、符号の種類によって決まる。さらに厳密には、ＭＤＳ符号がｋ個のブロックからｎ個の符号化データ・ブロックを生成している場合には、クラスタの大きさは、正確にｎになるものとする。本発明の記憶方法によるこのようなクラスタ化の例を、図２に示す。全ての記憶デバイスからなる集合を、複数の互いに素なクラスタに分割する。従って、各記憶デバイスは、１つのクラスタのみに属する。次いで、このように編成された分散型記憶システムに記憶する各ファイルを、特定のクラスタに記憶する。クラスタは、異なるファイルからのデータを含む。記憶デバイスは、異なるファイルからのデータを含む。さらに、記憶デバイスは、そのクラスタに記憶される全てのファイルからの１つのデータ・ブロックを含む。図２は、これらのファイルのｋ個のブロックのランダム線形結合であるｎ＝３個の符号化データ・ブロックＸｊをそれぞれ含む６個のファイルＸ１からＸ６の場合の例を与える図である。２つの記憶クラスタは、それぞれ３つの記憶デバイスのセットを含み、第１のクラスタ１（２０）は、記憶デバイス１、２、および３（２００、２０１、および２０２）を含み、第２のクラスタ２（２１）は、３つの記憶デバイス４、５、および６（２１０、２１１、および２１２）を含む。ファイルＸ１の３つ（ｎ＝３）の符号化データ・ブロックＸｊは、クラスタ１（２０）に記憶される。具体的には、第１のブロック（２０００）は、記憶デバイス１（２００）に記憶され、第２のブロック（２０１０）は、記憶デバイス２（２０１）に記憶され、第３のブロック（２０２０）は、記憶デバイス３（２０２）に記憶される。ファイルＸ２の３つの符号化データ・ブロックＸｊは、クラスタ２（２１）に記憶される。具体的には、第１のブロック２１００は、記憶デバイス４（２１０）に記憶され、第２のブロック２１１０は、記憶デバイス５（２１１）に記憶され、第３のブロック２１２０は、記憶デバイス６（２１２）に記憶される。同様に、クラスタ１は、ファイルＸ３の符号化データ・ブロックＸｊ（２００１、２０１１、２０２１）、およびファイルＸ５の符号化データ・ブロックＸｊ（２００２、２０１２、２０２２）も、記憶デバイス１、２、および３（それぞれ２００、２０１、および２０２）に記憶する。同様に、クラスタ２は、ファイルＸ４の符号化データ・ブロックＸｊ（２１０１、２１１１、および２１２１）、およびファイルＸ６の符号化データ・ブロックＸｊ（２１０２、２１１２、および２１２２）も、記憶デバイス４、５、および６（それぞれ２１０、２１１、および２１２）に記憶する。これらのファイルは、選択されたロード・バランシング・ポリシーに従って、到着順に記憶される（例えばファイルＸ１がクラスタ１に、ファイルＸ２がクラスタ２に、ファイルＸ３がクラスタ１に、など）。
【００２４】
これらのファイルを管理するためには、各ファイルをクラスタにマッピングする指標と、各記憶デバイスをクラスタにマッピングする指標の、２つの指標を維持すれば十分である。本発明の特定の実施形態によれば、記憶デバイスは、それぞれのＩＰ（インターネット・プロトコル）アドレスによって識別することができる。
【００２５】
本発明のデータ・ブロック配置ストラテジは、分散型記憶システムに記憶されたファイルの数によく対応する単純なファイル管理を示しながら、以下でさらに説明するように、このようなシステムの保守プロセスを直接提供する。なお、クラスタがどのように構成されているか、およびクラスタがどのように様々なファイルで充填されるかは、一様サンプリングと同様に任意のポリシーに従って、または特定のプロトコルを使用して、決定することができることに留意されたい。実際に、現況技術では、例えばロード・バランシングに焦点を当てたものや可用性に焦点を当てたものなど、様々な配置ストラテジが存在する。
【００２６】
配置ストラテジおよび保守（修復）プロセスは、通常は独立して設計される２つのビルディング・ブロックと考えられる。
【００２７】
本発明では、配置ストラテジは、以下でさらに説明するように、保守プロセスを直接提供する。分散型データ記憶システムは、その商業的な実施規模の大きさのために、システムの障害が起きやすい。通常、分散型データ記憶システムは、インターネット加入者からこのサービスへのデータを記憶する役割を果たし、ハードディスク・ドライブを備える何千もの記憶デバイスを利用する。従って、これらの障害によって生じるデータ喪失を修復するために、信頼性の高い保守機構が必要である。そのためには、システムは、記憶デバイスをモニタリングする必要があり、従来は、修復を実行しなければならないかどうかを判断するタイムアウト式のトリガ機構を使用している。本発明のクラスタ化方法の第１の実用的な点は、記憶デバイスのクラスタが管理しやすく、また、自身をモニタリングして必要に応じて自身を再生する（すなわちデータ喪失を修復する）自律型クラスタを作成することにより、完全に非集中的な方法でモニタリングを実施することができる点である。これは、故障した記憶デバイスを修復するためには、故障した記憶デバイスと置換する記憶デバイスが、故障した記憶デバイスが記憶していた各冗長ブロックに関連する全てのファイルにアクセスする必要があり、その際、接触すべき記憶デバイスは任意の位置に位置している可能性があるので、置換記憶デバイスは、修復を行う前にまずそれらの位置を問い合わせる必要がある、現行の記憶システムとは対照的である。こうしたことは、所与のクラスタで配置が構造化されているので、本発明では行われない。
【００２８】
この従来技術に従って、記憶デバイスの十分に大きなセットへのデータの一様なランダム配置を用いる場合によくあるように記憶した各ファイルへのアクセスを独立した事象とみなす場合には、そのセット内の全ての記憶デバイスに接触することに成功する確率は、様々なファイルの冗長ブロックが同じ記憶デバイスのセットに記憶されていない場合には、ブロック数とともに低下する。これは、各ホスト記憶デバイスが実際には特定の確率で利用可能であり、アクセス対象のこのようなホスト記憶デバイスの数が増加すると、所与の時点で全ての必要なブロックにアクセスすることができる確率が低下することによるものである。上述した従来技術の解決策とは対照的に、本発明のクラスタ型配置方法を使用すると、置換記憶デバイスにとって極めて重要なブロックに協働してホスティングするように記憶デバイスがグループ化されるので、修復が成功する確率は、故障した記憶デバイスに記憶されるブロックの数に依存しなくなる。さらに、置換記憶デバイスが接続する必要がある記憶デバイスの数は、故障した記憶デバイスに記憶されていたブロックの数に依存しない。その代わりに、この数は、システム・オペレータによって予め定義される固定されたクラスタの大きさに依存するので、置換記憶デバイスが保守する必要がある接続の数が減少する。
【００２９】
この記憶方法の具体的な効率性は、以下でさらに述べる、故障した記憶デバイスの修復を示す図３を援用することで最もよく説明される。
【００３０】
図３を用いて説明する本発明の方法とは対照的に、従来技術の修復プロセスは、従来の消去符号を使用するときには、次のようになる。所与のファイルの１つのデータ・ブロックを修復するためには、置換記憶デバイスは、（未符号化のプレーン・データの）ファイルを再生するために、十分に冗長な消去符号符号化ブロックをダウンロードして、それらを復号しなければならない。この動作が行われたら、置換記憶デバイスは、そのファイルを再符号化して、喪失した冗長データ・ブロックを再生することができるが、喪失したブロックごとに、再符号化を繰り返さなければならない。この従来技術の方法には、これらの種類の符号を使用することによって生じる以下の欠点がある。
１．１つのブロックを修復するために、すなわち１つのファイルの小さな一部分を修復するために、置換記憶デバイスは、そのファイルのブロックを記憶しているその他の記憶デバイスに記憶されている全てのブロックをダウンロードしなければならない。これは、通信コストがかかり、またこの第１のステップが完了しないうちは第２のステップ（後述）に取り掛かることができないので、時間もかかる。
２．第１のステップが完了した後で、置換記憶デバイスは、未符号化のプレーン・データ・ファイルを再生することができるようにダウンロードしたブロックを判読しなければならない。これは、計算負荷が高い動作であり、大きなファイルではさらに計算負荷は高くなる。
３．次いで、符号化アルゴリズムを使用して、再生したプレーン・データ・ファイルから喪失したブロックを符号化することによって、喪失したブロックを再作成しなければならない。
【００３１】
この従来技術の方法とは対照的に、本発明の記憶方法のクラスタ型配置ストラテジおよびランダム符号の使用により、修復プロセスにおいて重要な利点が得られる。既に示したように、従来技術の修復方法によれば、同じファイルの複数のブロックを、それらの間で結合する。本発明の方法によれば、ファイル・レベルではなくシステム・レベルでネットワーク・コード化を使用する。すなわち、本発明の修復方法は、複数のファイルのデータ・ブロックを結合することを含み、これにより、修復中に記憶デバイス間で交換されるメッセージの数が大幅に減少する。記憶デバイスによって記憶される符号化データ・ブロックＸｊは、代数演算を実行することができる単なる代数要素である。
【００３２】
修復プロセスの終了時に得られるのは、故障した記憶デバイスの修復である。本発明の状況では、故障した記憶デバイスの修復とは、故障した記憶デバイスが符号化データ・ブロックＸｊを記憶していた各ファイルのランダム・ベクトルの作成である。任意のランダム・ベクトルは、冗長な、または符号化された、データ・ブロックである。従って、故障した記憶デバイスの修復プロセスで必要な動作は、故障した記憶デバイスに記憶されていたデータそのものを置換することではなく、故障した記憶デバイスによって喪失した量のデータを再生することである。この選択により、記憶デバイスの再統合と呼ばれるものに関するさらなる利点が得られることについて、以下でさらに述べる。
【００３３】
図３は、本発明のデータを記憶する方法を使用する分散型データ記憶システムに基づく、本発明による故障した記憶デバイスの修復を示す図である。ここで、クラスタ（３００００）は、最初に、４つの記憶デバイス（３０、３１、３２、３３）を含む。各記憶デバイスは、２つのファイル、ファイルＸおよびファイルＹのランダム符号ブロックＸｊを記憶している。両方のファイルＸおよびＹについて、ｋ＝２である（すなわち、ファイルＸおよびＹは、ｋ＝２個のブロックにチャンク化される）。第１の記憶デバイス（３０）は、ランダム符号ブロック（＝符号化データ・ブロック）３００および３０１を記憶する。第２の記憶デバイス（３１）は、ランダム符号ブロック３１０および３１１を記憶する。第３の記憶デバイス（３２）は、ランダム符号ブロック３２０および３２１を記憶する。第４の記憶デバイス（３３）は、ランダム符号ブロック３３０および３３１を記憶する。第４の記憶デバイス（３３）が故障して、修復しなければならないものと仮定する。これは、次のように行われる。
１．第５の置換記憶デバイス（３９）を、クラスタ（３００００）に追加する。この置換記憶デバイスは、クラスタ内のｋ＋１個の残りの記憶デバイスから、各記憶デバイスに記憶されているランダム符号から生成されたランダム符号の新たなランダム線形結合（および関連する係数α）を受け取る。これは、枠３４から３６および矢印３０００から３００５で示してある。
２．その結果得られた生成された新たなランダム線形結合を、ファクタＸおよびＹがそれぞれ消去された２つの線形結合が残るように、それらの間で結合する。すなわち、一方の線形結合はＸのみと関係し、もう一方の線形結合はＹのみと関係する。この除去は、例えば従来の「ガウス消去」代数演算を用いて、これらの結合の係数を慎重に選択することによって行われる。
３．残りの２つの線形結合を、置換記憶デバイス３９に記憶する。これは、矢印３０１２および３０１３で示してある。
【００３４】
これで、修復動作は完了し、システムは再び安定した動作状態になっていると考えられる。
【００３５】
ほとんどの分散型記憶システムでは、記憶デバイスが故障した記憶デバイスであると宣言する判断は、タイムアウトを用いて行われる。重要なことは、これが、エラーが起こりやすい不確実な判断であることである。実際に、記憶デバイスは、誤ってタイムアウトする可能性があり、修復が行われた後で予期せずに再接続する可能性がある。もちろん、タイムアウトが長くなるほど、エラーの数は少なくなる。しかし、長いタイムアウトを使用すると、記憶システムの反応性が低下し、そのため障害バーストが起こったときに修繕不能なデータ喪失が生じる恐れがあるので、危険である。再統合という概念は、誤ってタイムアウトしている記憶デバイスを再統合することである。再統合は、消去符号を使用するときには対処されていない。再統合を実施しない場合には、誤って故障しているとみなされた記憶デバイスの修復は不要であり、従って、追加の障害の許容に寄与することができないので、資源の無駄となる。これは、修復された記憶デバイスが、他の記憶デバイスから独立した冗長性を含んでおらず、従って追加の冗長性の利点をもたらさないことから生じる。
【００３６】
本発明の特定の有利な実施形態は、誤って故障とされた記憶デバイス、すなわち例えば接続タイムアウトが検出されたときに分散型データ記憶装置によって故障しているとみなされたがシステムに再接続するデバイスの再統合を含む。本発明で、このような再統合が可能であるのは、このような再統合が、単にさらなる冗長データをクラスタに追加するだけであり、誤って故障とされた記憶デバイスの修復は、一見すると不要であるように見えるが、クラスタの冗長性を高めることになるので、次に同じクラスタの任意の記憶デバイスが故障したときに、修復を実行する必要がなくなるからである。これは、本発明によるクラスタ化方式とともに、ランダム符号の性質から得られるものである。従って、再統合により、分散型データ記憶システムのリソースの利用効率が高まる。
【００３７】
この記憶デバイス再統合の概念を利用した、本発明の様々な変形実施形態も可能である。
【００３８】
第１の変形実施形態によれば、クラスタのサイズを、正確にｎ個の記憶デバイスに維持する。記憶デバイスが故障した場合には、本発明の故障した記憶デバイスを修復する方法に従って、その記憶デバイスを、符号化データ・ブロックを備える置換記憶デバイスで置換する。故障した記憶デバイスが復帰した場合（すなわちそのデバイスは一時的に利用不能になっていただけ）には、そのデバイスは、クラスタの記憶デバイスのうちの１つとしてクラスタに再統合されるのではなく、必要に応じてこのクラスタの置換デバイスとして、または変形形態では別のクラスタの置換デバイスとして使用することができる記憶デバイスのプールにフリー・デバイスとして統合される。
【００３９】
第２の変形実施形態によれば、修復された、すなわち別の置換記憶デバイスで置換され、クラスタに復帰する故障したデバイスは、クラスタに再統合される。これは、そのクラスタが、それまではｎ個の記憶デバイスを有していたが、特定の期間（すなわち次の障害まで）にわたってｎ＋１個の記憶デバイスのレベルに維持されることを意味する。２通りの場合が当てはまる。すなわち、故障したデバイスが一時的に存在しない間に、ｎ個のノードでデータの変更が行われず、既にクラスタに含まれているｎ個の記憶ノードにノードを単純に追加することができる場合。これに対して、データが変更された場合には、故障したノードを、そのクラスタの残りのｎ個のノードと同期させる必要がある。この同期は、故障したノードの完全な修復に必要な動作を必要とするわけではなく、単に図１を援用して上述したように、そのデバイスが存在しない間にクラスタに記憶された新たなファイルのそれぞれの１つのブロックの新たなランダム線形結合を生成し、生成した新たなランダム線形結合を故障した記憶デバイスに記憶すればよい。もちろん、クラスタがｎ＋１個の記憶デバイスのレベルのままである場合には、クラスタに追加される任意の新たなファイルを、クラスタのｎ＋１個のノードにわたって拡散させなければならない。これは、デバイス障害が存在しない限り続く。次のデバイス障害の後で、クラスタのサイズは、再びｎに減少する。
【００４０】
上述のように、変形実施形態によれば、ｎ個の記憶デバイスを含む代わりに、クラスタは、ｎ＋１個、またはｎ＋２個、またはｎ＋１０個、またはｎ＋ｍ個の記憶デバイスを含むことができる（ｍは任意の整数）。これによって本発明のデータを記憶する方法が変化することはなく、また修復方法が変化することもなく、記憶方法では、ｋ個のデータ・ブロックに分割されたファイルから、ｎ個ではなくｎ＋ｍ個の符号化データ・ブロックが作成され、クラスタに含まれているｎ＋ｍ個の記憶デバイスにわたって拡散されることを考慮しているだけでよい。１つのクラスタ内にｎ個を超える記憶デバイスを有すると、クラスタの冗長性が高まるという利点があるが、データ記憶のオーバヘッドも大きくなる。
【００４１】
図４は、本発明によるデータ項目を記憶する方法を実施する分散型記憶システムにおいて記憶デバイスとして使用することができるデバイスを示す図である。デバイス４００は、記憶デバイスの管理デバイスの役割を果たす汎用デバイスとすることができる。このデバイスは、ディジタル・データ／アドレス・バス４１４によって相互接続された、以下の構成要素を含む。
処理ユニット４１１（または中央処理装置（ＣＰＵ））。
不揮発性メモリＮＶＭ４１０。
揮発性メモリＶＭ４２０。
デバイス４００の構成要素間の動作同期用、およびタイミング用の参照クロック信号を供給するクロック４１２。
デバイス４００を、接続４１５を介してネットワーク中に接続された他のデバイスと相互接続するためのネットワーク・インタフェース４１３。
【００４２】
なお、メモリ４１０および４２０の説明で用いる「レジスタ」という用語は、これらのメモリのそれぞれにおいて、いくつかの２値データを記憶することができる小容量メモリ領域と、実行可能なプログラムまたはデータ・セット全体を記憶することができる大容量メモリ領域とを指すことに留意されたい。
【００４３】
処理ユニット４１１は、マイクロプロセッサ、カスタム・チップ、および専用（マイクロ）制御装置などとして実装することができる。不揮発性メモリＮＶＭ４１０は、ハード・ディスク、不揮発性ランダム・アクセス・メモリ、およびＥＰＲＯＭ（消去可能プログラマブルＲＯＭ）など、任意の形態の不揮発性メモリとして実装することができる。
【００４４】
不揮発性メモリＮＶＭ４１０は、特に、本発明による正確な修復方法を格納する実行可能なプログラムを表すプログラムを保持するレジスタ４１０１と、永続パラメータを含むレジスタ４１０２とを含む。電源が投入されると、処理ユニット４１１は、ＮＶＭレジスタ４１０１に含まれる命令をロードし、それらをＶＭレジスタ４２０１にコピーし、それらを実行する。
【００４５】
ＶＭメモリ４２０は、特に、
ＮＶＭレジスタ４１０１のプログラム「ｐｒｏｇ」のコピーを含むレジスタ４２０１と、
データ記憶装置４２０２と、を含む。
【００４６】
デバイス４００などのデバイスは、本発明のデータ項目を記憶する方法を実施するのに適しており、このデバイスは、
データ・ファイルをｋ個のデータ・ブロックに分割し（ＣＰＵ４１１、ＶＭレジスタ４２０２）、これらのｋ個のデータ・ブロックのランダム線形結合によってこれらのｋ個のブロックからｎ個の符号化データ・ブロックを作成する手段と、
このファイルのこれらのｎ個の符号化データ・ブロックを、同じ記憶デバイス・クラスタに含まれているｎ個の記憶デバイスにわたって拡散する手段（ＣＰＵ４１１、ネットワーク・インタフェース４１３）と、を備え、各クラスタは、異なる記憶デバイスのセットを含み、このファイルのこれらのｎ個の符号化データ・ブロックは、各記憶デバイス・クラスタが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶し、且つ１つの記憶デバイス・クラスタの記憶デバイスのそれぞれが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶するように、１つの記憶デバイス・クラスタのｎ個の記憶デバイスにわたって分散される。
【００４７】
変形実施形態によれば、本発明は、例えば専用構成要素として（例えばＡＳＩＣ（特定用途向け集積回路）、ＦＰＧＡ（フィールド・プログラマブル・ゲート・アレイ）、もしくはＶＬＳＩ（超大規模集積回路）として）またはデバイスに一体化された別個の電子構成要素として、完全にハードウェアで実装される、あるいはハードウェアとソフトウェアの混成形態で実装される。
【００４８】
図５ａは、本発明による分散型データ記憶システムでデータ・ファイルを記憶する方法を流れ図の形態で示す図である。
【００４９】
第１のステップ５００で、この方法を初期化する。この初期化は、この方法の適用に必要な変数およびメモリ・スペースの初期化を含む。ステップ５０１で、記憶するファイルをｋ個のデータ・ブロックに分割し、これらのｋ個のデータ・ブロックのランダム線形結合によって、これらのｋ個のデータ・ブロックからｎ個の符号化データ・ブロックを作成する。ステップ５０２で、このファイルのｎ個のデータ・ブロックを、同じ記憶デバイス・クラスタに含まれている分散型データ記憶システムの記憶デバイスにわたって拡散させる。分散型データ記憶システムの各クラスタは、異なる記憶デバイスのセットを含む。このファイルのｎ個の符号化データ・ブロックは、同じ記憶デバイス・クラスタにわたって分散し（またはこれまでに用いていた表現を用いれば、拡散し）、各記憶デバイス・クラスタが２つ以上のファイルからの符号化データ・ブロックを記憶し、且つ１つの記憶デバイス・クラスタの記憶デバイスのそれぞれが、少なくとも２つのファイルからの符号化データを記憶するようになる（図２およびその説明も参照されたい）。ステップ５０３で、この方法が行われる。
【００５０】
本発明による分散型データ記憶システムにおけるこれらのステップの実行は、このシステム内のデバイスが様々な方法で行うことができる。
【００５１】
例えば、ステップ５０１は、管理デバイスによって、すなわち分散型データ記憶システムを管理する管理デバイスまたは特定のクラスタを管理する管理デバイスによって実行される。このような管理デバイスは、特定のデバイスでなく、管理デバイスの役割も果たす記憶デバイスなどの任意のデバイスであってもよい。
【００５２】
図５ｂは、本発明の記憶方法に従ってファイルがｋ個のデータ・ブロックに分割され、データが記憶される分散型データ記憶システムにおいて故障した記憶デバイスを修復する方法を流れ図の形態で示す図である。
【００５３】
第１のステップ６００で、この方法を初期化する。この初期化は、この方法の適用に必要な変数およびメモリ・スペースの初期化を含む。ステップ６０１で、故障した記憶デバイスが属している記憶デバイス・クラスタに置換記憶デバイスを追加する。次いで、ステップ６０２で、置換記憶デバイスが、その記憶デバイス・クラスタ内のｋ＋１個の残りの記憶デバイスの全てから、ランダム線形結合を受け取る。これらの結合は、２つの異なるファイルＸおよびＹの２つの符号化データ・ブロックから生成される（なお、本発明によるデータを記憶する方法では、各記憶デバイスが、少なくとも２つの異なるファイルの符号化データ・ブロックを記憶することに留意されたい）。次いで、ステップ６０３で、これらの受け取った新たなランダム線形結合を、ファイルＸのみに関係するものが１つとファイルＹのみに関係するものが１つの２つの線形結合が得られるように、それらの間で結合する。最後から２番目のステップ６０４で、これらの２つの結合を置換デバイスに記憶し、修復を行う（ステップ６０５）。
【００５４】
この修復方法は、所望のレベルのデータ冗長性が所定レベル未満に低下したことを検出したことによってトリガすることができる。
【００５５】
図６ａは、ネットワーク中で相互接続された複数の記憶デバイスを含む分散型データ・システムでデータ・ファイルの記憶を管理するデバイス７００を示す図である。デバイス７００は、記憶管理デバイスとも呼ぶ。この記憶管理デバイスは、ネットワークに接続するためのネットワーク接続７０５に対するネットワーク・インタフェース７０３を備える。記憶管理デバイス７００は、さらに、データ・ファイルをｋ個のデータ・ブロックに分割し、これらのｋ個のデータ・ブロックのランダム線形結合によってこれらのｋ個のデータ・ブロックから少なくともｎ個の符号化データ・ブロックを作成するデータ・スプリッタ７０１を備える。記憶管理デバイス７００は、さらに、このファイルの少なくともｎ個の符号化データ・ブロックを同じ記憶デバイス・クラスタに含まれる少なくともｎ個の記憶デバイスにわたって拡散させることによって、少なくともｎ個の符号化データ・ブロックを記憶する記憶配分器７０２を備える。各クラスタは、異なる記憶デバイスのセットを含み、このファイルの少なくともｎ個の符号化データ・ブロックは、各記憶デバイス・クラスタが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶し、且つ１つの記憶デバイス・クラスタの記憶デバイスのそれぞれが、少なくとも２つの異なるファイルからの符号化データ・ブロックを記憶するように、１つの記憶デバイス・クラスタの少なくともｎ個の記憶デバイスにわたって分散される。データ・スプリッタ７０１と、記憶配分器７０２と、ネットワーク・インタフェース７０３とは、記憶管理デバイス７００内の通信バスを介して相互接続される。
【００５６】
特定の実施形態によれば、記憶管理デバイスは、それ自体が、分散型データ・システムの記憶デバイスのうちの１つである。
【００５７】
図６ｂは、本発明の記憶方法に従ってデータが記憶され、記憶されたファイルがｋ個のデータ・ブロックに分割される分散型データ記憶システムにおいて故障した記憶デバイスの修復を管理するデバイス７１０を示す図である。このデバイス７１０は、修復管理デバイスとも呼ぶ。修復管理デバイス７１０は、接続７１５を介して分散型データ記憶システム内のデバイスに接続するためのネットワーク・インタフェース７１３と、故障した記憶デバイスが属している記憶デバイス・クラスタに置換記憶デバイスを追加する置換器７１１と、記憶デバイス・クラスタ内のｋ＋１個の残りの記憶デバイスのうちの何れかから置換記憶デバイスに、ｋ＋１個の記憶デバイスのそれぞれが記憶している２つの異なるファイルＸおよびＹの２つの符号化データ・ブロックから生成されたｋ＋１個の新たなランダム線形結合を分配する配分器７１２とを備える。修復管理デバイス７１０は、さらに、代数演算を用いて新たなランダム線形結合をそれらの間で結合して、Ｘのみに関係するものが１つとＹのみに関係するものが１つの２つのブロックが得られる２つの線形結合を得る、結合器７１６を備える。最後に、修復管理デバイスは、これらの２つの線形結合を置換記憶デバイスに記憶するデータ書込み器７１７を備える。ネットワーク・インタフェース７１３と、配分器７１２と、置換器７１１と、結合器７１６と、データ書込み器７１７とは、内部通信バス７１４を介して相互接続される。
【００５８】
特定の実施形態によれば、記憶修復管理デバイスは、それ自体が、分散型データ・システムの記憶デバイスのうちの１つである。
【図１】
2015519648.tif 000004
【図２】
2015519648.tif 000005
【図３】
2015519648.tif 000006
【図４】
2015519648.tif 000007
【図５ａ】
2015519648.tif 000008
【図５ｂ】
2015519648.tif 000009
【図６ａ】
2015519648.tif 000010
【図６ｂ】
2015519648.tif 000011
【国際調査報告】
2015519648.tif 000012
2015519648.tif 000013
2015519648.tif 000014