JP5298393B2 - 並列リードソロモンｒａｉｄ（ｒｓ−ｒａｉｄ）アーキテクチャ、デバイス、および方法 - Google Patents

Description

本出願は、２００７年１１月２１日に出願された米国仮出願第６０／９８９，６７０号「Ｐａｒａｌｌｅｌ ＲＡＩＤ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｆｏｒ ＲＡＩＤ６ ａｎｄ Ｒｅｅｄ−Ｓｏｌｏｍｏｎ Ｃｏｄｅ」の利益を主張し、参照によりその全体が本明細書に組込まれる全ての引用された参考文献を含む。

ＲＡＩＤ（ｒｅｄｕｎｄａｎｔ ａｒｒａｙ ｏｆ ｉｎｅｘｐｅｎｓｉｖｅ ｄｉｓｋｓ）アーキテクチャは、ハードディスクなどのデータ記憶ユニットのグループを使用して、耐故障性を有するデータ記憶装置を提供する。ＲＡＩＤアーキテクチャは、誤りおよびディスク故障から情報を保護するために、前方誤り訂正（ｆｏｒｗａｒｄ ｅｒｒｏｒ ｃｏｒｒｅｃｔｉｏｎ）（ＦＥＣ）コードおよび予備のデータ記憶ユニットを使用する。情報シンボルは、ビット、バイト、またはワードであってよい。情報シンボルは、符合化されて、データおよびチェックサムまたはパリティシンボルを含むコードシンボルを形成しうる。組織的な前方誤り訂正コードの場合、情報シンボルは、コードシンボルのデータシンボル部分において明示的に表されうる。

リードソロモンコードは、チェックサムシンボルの数に等しい記憶ユニットの故障の数を許容するために、ＲＡＩＤアーキテクチャ（ＲＳ−ＲＡＩＤ）で使用されうる。たとえば、データ用に２０の記憶ユニットを、チェックサム用に４つの記憶ユニットを割当てる４重誤り訂正ＲＳ−ＲＡＩＤアーキテクチャは、４つを含む４つまでの記憶デバイスにおける故障を許容しうる。

ＲＳ−ＲＡＩＤアーキテクチャは、通常、データ記憶ユニットに書込まれるデータシンボルを保護するために単一のＲＡＩＤコントローラを使用する。単一のＲＡＩＤコントローラが使用されて、チェックサム、符号化、および復号化計算を実施するとき、ＲＡＩＤアーキテクチャのスループットまたはデータ記憶量および取出し速度は、ＲＡＩＤでなくかつ耐故障性を有さないデータ記憶アーキテクチャと比べて低減される可能性がある。

したがって、高スループットで耐故障性を有する分散型のデータ記憶アーキテクチャが望ましい場合がある。

高性能記憶アーキテクチャでは、複数のＲＡＩＤコントローラは、通信ファブリックと呼ぶ通信経路の共通集合を通じて互いに通信してもよい。通信ファブリックは、ＲＡＩＤコントローラと所与のＲＡＩＤコントローラに割当てられた記憶デバイスとの間の通信経路と比較して高いレーテンシを有する可能性がある。レーテンシの高い通信ファブリックは、ＲＡＩＤコントローラ間のデータ、メッセージ、構成などのトラフィックが、耐故障性を有する分散データ記憶装置のタスクに整合しなければ、ＲＡＩＤデータ記憶アーキテクチャのスループットを減少させる可能性がある。通信ファブリックと割当てられたデータ記憶デバイスの集合との間に介在してもよい、それぞれのＲＡＩＤコントローラは、データ記憶アーキテクチャのノードと呼ばれてもよい。ＲＡＩＤコントローラおよび割当てられたデータ記憶デバイスは、データ記憶クラスタと呼ばれてもよい。

リードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）ＲＡＩＤ（ＲＳ−ＲＡＩＤ）アーキテクチャは、冗長なデータ記憶デバイスを含むことによって、ハードディスクなどの記憶デバイスに書込まれ、また、記憶デバイスから読出される情報シンボルを保護しうる。ｍのチェックサムデバイスを使用するＲＳ−ＲＡＩＤアーキテクチャは、データ記憶デバイスのｍ程度の同時故障を許容しうる。ｍのチェックサムシンボルはｃ_１，ｃ_２、…、ｃ_ｍで示されてもよい。ＲＳ−ＲＡＩＤアーキテクチャはまた、ｄ_１，ｄ_２、…、ｄ_ｎで示す情報保持またはデータシンボル用の数ｎのデータ記憶デバイスを含みうる。

チェックサムおよびデータ記憶デバイスは、データおよびチェックサムシンボルを、ビット、バイト、ワードなどとして記憶してもよい。リードソロモン（ＲＳ）コードなどのあるタイプの前方誤り訂正コード（ｆｏｒｗａｒｄ ｅｒｒｏｒ ｃｏｒｒｅｃｔｉｏｎ ｃｏｄｅｓ）（ＦＥＣ）は、通常、バイトを使用することが留意されてもよい。たとえば、ＲＳコードは、２５５のバイトブロック内の２３３のデータバイトと３２のチェックサムバイトに２３３の情報バイトを符合化するブロックなどのバイトブロックに作用しうる。

ＲＳ−ＲＡＩＤアーキテクチャは、対応するデータ記憶デバイスＤ_１、Ｄ_２、…、Ｄ_ｎによって保持されるデータシンボルｄ_１，ｄ_２、…、ｄ_ｎを使用して、ｉ番目のチェックサムデバイスＣ_ｉに記憶されるチェックサムシンボルｃ_ｉを計算しうる。ＲＳ−ＲＡＩＤアーキテクチャは、Ｄ_１、Ｄ_２、…、Ｄ_ｎ、Ｃ_１、Ｃ_２、…、Ｃ_ｍの記憶デバイスのうちの任意のｍ以下の記憶デバイスが故障する場合、故障したデバイスのうちの任意のデバイスのコンテンツが、損なわれていないまたは故障していないデバイスから再構築されうるように各ｃ_ｉ（１≦ｉ≦ｍ）を確定しうる。ＲＳ−ＲＡＩＤアーキテクチャは、ファンデルモンデ行列の特性により耐故障性を有する演算を提供することができ、ファンデルモンデ行列は、チェックサムシンボルを計算し維持し、記憶デバイスから読出したデータおよびチェックサムシンボルから情報を回復するのに使用される。ＲＳ−ＲＡＩＤコントローラは、記憶デバイスが故障しても、添加されるかまたは拡大されたファンデルモンデ行列と単位行列の（ｎ×ｎ）部分の逆行列を計算することによって、記憶デバイスにおけるデータおよび／またはチェックサムシンボルを回復しうる。

チェックサムシンボルを生成するために、ＲＳ−ＲＡＩＤアーキテクチャは、データシンボルを、ファンデルモンデ行列の要素で重み付けし、式１によって線形関数Ｆ_ｉを使用して重み付けされたデータシンボルを合計しうる。関数Ｆ_ｉは、ファンデルモンデ行列の要素のｉ番目の行から得られうるため、Ｆ_ｉ＝［ｆ_ｉ，１；ｆ_ｉ，２；…；ｆ_ｉ，ｎ］^Ｔである。

換言すれば、データおよびチェックサムシンボルが、それぞれ、（ｎ×１）次元および（ｍ×１）次元ベクトルＤ＝［ｄ_１，ｄ_２、…、ｄ_ｎ］^ＴおよびＣ＝［ｃ_１、ｃ_２、…、ｃ_ｍ］^Ｔとして表され、また、関数Ｆ_ｉが行列Ｆの行として表される場合、ＲＳ−ＲＡＩＤアーキテクチャは、チェックサムシンボルを式２ａによって符合化しうる。
Ｃ＝ＦＤ （式２ａ）
式２ａは、

に等しい。

有利に設計されたＲＳ−ＲＡＩＤ ＦＥＣコードの場合、Ｆ行列は、要素：ｆ_ｉ，ｊ＝ｊ^ｉ−１を有する（ｍ×ｎ）ファンデルモンデ行列でありうる。式中、インデックスｉ＝１、２、…、ｍおよびｊ＝１、２、…、ｎは、それぞれ、ファンデルモンデ行列の行および列に対応し、代数演算は、ガロア体の特性を使用して実施される。たとえば、（３×４）ファンデルモンデ行列は、

として書かれうる。

誤りを含む可能性があるコードワードまたはコードシンボルから（ｎ×１）情報ベクトル

を回復するために、並列ＲＳ−ＲＡＩＤアーキテクチャは、ファンデルモンデ行列およびＩで示す添加された（（ｎ−ｍ）×（ｎ−ｍ））単位行列を含む拡大されるかまたは分割された行列Ａの逆行列を求め、Ａの逆行列に、作動可能な記憶ユニットから読出されるデータおよびチェックサムシンボルの集合ＤおよびＣをそれぞれ右から乗算し(ｐｏｓｔ−ｍｕｌｔｉｐｌｙ)うる。記号的には、回復される情報ベクトル

は、

から得られうる。式中、拡大行列は

であり、

は、拡大されたデータおよびチェックサムシンボルベクトルである。表記Ｉｎｖ（Ａ）は、正則な（ｎ×ｎ）正方行列を形成するＡの行の部分集合の逆行列などのＡに基づく逆行列をもたらし、また、以下で述べるように、

で示す列行列Ｅのｎの行の、対応する選択されるかまたは選抜された集合に共形的である関数であると理解されてもよい。Ａ行列の逆行列を求めるプロセスは、Ａの行の選択された集合の反転とみなされてもよく、選択は、作動可能なデータ記憶デバイスのリストおよび行列にベクトルを掛ける計算における共形性についての要件によって確定される。（（ｎ＋ｍ）×ｎ）拡大行列Ａのｎの行の全ての部分集合は、Ｆがファンデルモンデ行列であるため反転可能であることが留意されてもよい。

拡張形態では、式

は、

として表されうる。式中、共形性は、行列Ａの選択された部分を反転する前に、ＥおよびＡの対応する行を選択することによって実施される。

換言すれば、ＲＳ−ＲＡＩＤアーキテクチャの各記憶デバイスは、拡大行列Ａの行および列ベクトルＥ＝［ｄ_１、ｄ_２、…、ｄ_ｎ、ｃ_１、ｃ_２、…、ｃ_ｍ］^Ｔの対応する要素によって表されうる。ｍの冗長記憶デバイス中のいずれの冗長記憶デバイスも故障しない場合、回復される情報シンボルは、Ａのｎの行の任意の部分集合およびＥのｎの対応する要素を選択することによって確定されて、データ回復行列として記述されてもよい正方行列Ａ'および対応するデータ記憶ユニットから読出されるデータのベクトル

が形成されうる。換言すれば、Ｉｎｖ（Ａ）＝（Ａ'）^−１であり、また、

である。たとえば、４＋２ＲＳ−ＲＡＩＤアーキテクチャの場合、回復されるかまたは復号化されるデータ

は、

によって、拡大されたファンデルモンデ行列の最初の４つの行および記憶デバイスアレイから読出されたデータおよびチェックサムの最初の４つのエンティティから抽出された回復されるデータシンボルのベクトルでありうる。

たとえば、第３の、第５の、または、第３と第５の両方のデータ記憶デバイスが故障する場合、

は、以下の通りに、作動可能なデバイスに対応する４つの行を選択することによって、Ｅ'から回復されうる。

式中、２重末梢線は記憶デバイスの故障を示し、１重末梢線は、逆行列を形成し、その後の計算を実施するための記憶デバイスの選択解除を示しうる。逆行列は、ガウス消去法または別の方法によって計算されてもよい。

の値が得られると、回復されるかまたは推定される任意のチェックサムベクトル

が、

を使用して、データベクトル

に基づいて計算されてもよい。

並列ＲＳ−ＲＡＩＤデータ記憶アーキテクチャは、各クラスタ内のデータおよびチェックサムを、全てのクラスタに転送されるかまたは配信される中間または部分和に集計しうる。中間データシンボル、中間チェックサムシンボル、データ記憶デバイスのクラスタへの割当てに関するクラスタ構成情報、およびデータ記憶デバイスの作動に関する状態などの使用は、並列ＲＳ−ＲＡＩＤ分散データ記憶アーキテクチャのスケーラビリティおよびスループットを向上させながら、誤り訂正計算についての計算負荷およびレーテンシを低減しうる。

本開示は、同じ数字が同じ要素を表す添付図面を参照することになる。

並列ＲＳ−ＲＡＩＤ（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ ｒｅｄｕｎｄａｎｔ ａｒｒａｙ ｏｆ ｉｎｅｘｐｅｎｓｉｖｅ ｄｉｓｋ）の例を示す図である。 構成行列の例を示す図である。 ＲＡＩＤコントローラの例を示す図である。 チェックサムプログラムの例のフローチャートである。 チェックサム更新プログラムの例のフローチャートである。 データプログラムの例のフローチャートである。

図１は、データ記憶のための並列ＲＳ−ＲＡＩＤアーキテクチャ１００の例である。並列ＲＳ−ＲＡＩＤアーキテクチャ１００は、通信ファブリック１２００、ＲＡＩＤコントローラ１１１１〜１１１３、および記憶デバイス１００１〜１０１２を含みうる。記憶デバイス１００１〜１００４、１００５〜１００８、および１００９〜１０１２は、それぞれ、ＲＡＩＤコントローラ１１１１〜１１１３に結合されうる。換言すれば、記憶デバイス１００１〜１０１２の部分集合またはクラスタは、それぞれの対応するＲＡＩＤコントローラ１１１１〜１１１３に結合しうる。各ＲＡＩＤコントローラ１１１１〜１１１３に結合しうる記憶デバイスの数は、等しくても、等しくなくてもよく、また、耐故障性を改善する、スループットを改善するなどのために、記憶デバイスのＲＡＩＤコントローラに対する構成またはマッピングは動的に変わってもよい。たとえば、記憶デバイス１００１〜１０１２のＲＡＩＤコントローラ１１１１〜１１１３に対する割当ては、構成行列または同様のデータ構造によって確定されてもよい。

図２は、変数「ｔ」を含みうる構成行列２００の例を示し、変数「ｔ」は、ＲＡＩＤコントローラの数のインデックスまたはカウンタである。たとえば、構成行列２００の行２０６は、ＲＡＩＤコントローラインデックス番号「ｔ」と、ＲＡＩＤコントローラ１１１１〜１１１３などのそれぞれのＲＡＩＤコントローラとの間のマッピング関数Ｑ（ｔ）を示す。行２０２はＲＡＩＤ記憶デバイス開始インデックスＱＳ（ｔ）を示し、行２０４はＲＡＩＤ記憶デバイス終了インデックスＱＥ（ｔ）を示す。たとえば、ＱＳ（２）＝１００５であり、ＱＥ（２）＝１００８である。デバイス番号のオフセットが、関数Ｊ（）によって供給されてもよいため、Ｊ（ＱＳ（２））＝５であり、これは、たとえば、５番目の記憶デバイスが第２の記憶デバイスクラスタで開始することを示しうることが留意されてもよい。構成行列２００は、記憶デバイスを対応するＲＡＩＤコントローラにマッピングしうる。換言すれば、構成行列２００は、記憶デバイスのどの部分集合またはクラスタが、所与のＲＡＩＤコントローラに割当てられるかを確定するかまたは制御しうる。計算のために、構成行列２００は、以下で述べるように、コードワードを符合化するかまたは復号化しうる重み付き部分和の始まりと終わりを確定しうる、チェックサムおよびデータを更新するかまたは維持しうるなどを行いうる。

通信ファブリック１２００は、ＲＡＩＤコントローラ１１１１〜１１１３間で、また、並列ＲＳ−ＲＡＩＤアーキテクチャ１００と外部デバイスとの間で入力および出力（Ｉ／Ｏ）デジタル信号を結合しうる。たとえば、通信ファブリック１２００は、ＲＡＩＤコントローラ１１１１〜１１１３間で、データシンボル、チェックサムシンボル、中間データおよびチェックサムシンボルなどのようなデジタル信号を結合しうる。通信ファブリック１２００は、並列バス構造、直列データリンク、光バックプレーンなどを使用してもよい。通信ファブリック１２００は、外部通信用に１つのタイプのバス、リンク、またはバックプレーン構造を、ＲＡＩＤコントローラ１１１１〜１１１３間の通信用に別のタイプを使用してもよい。

ＲＡＩＤコントローラ１１１１〜１１１３は、構成行列２００などの構成行列または他のデータ構造によって与えられた、割当てられた記憶デバイスの部分集合またはクラスタ内の各記憶デバイスについてデータチェックサムシンボルを計算しうる。ＲＡＩＤコントローラ１１１１〜１１１３は、誤り訂正コード計算の部分和を集計するかまたは蓄積し、集計されたデータおよびパリティ計算結果を、通信ファブリック１２００を通じて、並列ＲＳ−ＲＡＩＤアーキテクチャ１００内の他のＲＡＩＤコントローラに報告しうる。データおよびチェックサムシンボルについての部分和計算の詳細が、特定のＲＡＩＤコントローラを参照して述べられてもよいが、対応する計算は、ＲＡＩＤコントローラ１１１１などの、並列ＲＳ−ＲＡＩＤアーキテクチャ１００内の任意のＲＡＩＤコントローラによって実施されてもよい。

図３は、通信ファブリックインタフェース１１１１ａ、ＲＡＩＤコントロールユニット１１１１ｂ、中間和デバイス１１１１ｃ、記憶デバイスインタフェース１１１１ｇ、および記憶デバイス故障センスユニット１１１１ｈを含みうるＲＡＩＤコントローラ１１１１の例を示す。通信ファブリックインタフェース１１１１ａは、通信ファブリック１２００などの通信ファブリックへのまた通信ファブリックからの信号を、中間和デバイス１１１１ｃおよびＲＡＩＤコントロールユニット１１１１ｂに結合しうる。ＲＡＩＤコントロールユニット１１１１ｂは、中間和デバイス１１１１ｃ、記憶デバイスインタフェース１１１１ｇ、および記憶デバイス故障センスユニット１１１１ｈに結合しうる。記憶デバイスインタフェース１１１１ｇは、ＲＡＩＤコントロールユニット１１１１ｂ、中間和デバイス１１１１ｃ、および記憶デバイス故障センスユニット１１１１ｈに結合しうる。ＲＡＩＤコントローラ１１１１は、先に述べたように、通信ファブリック１２００へまた通信ファブリック１２００から結合し、記憶デバイスインタフェース１１１１ｇを介して記憶デバイス１００１〜１００４などの記憶デバイスへまた記憶デバイスから結合しうる。

中間和デバイス１１１１ｃは、中間和計算器１１１１ｄ、再計算器１１１１ｅ、および計算コントロール１１１１ｆを含みうる。中間和計算器１１１１ｄは、通信ファブリックインタフェース１１１１ａ、記憶デバイスインタフェース１１１１ｇ、再計算器１１１１ｅ、および計算コントロール１１１１ｆに結合しうる。再計算器１１１１ｅは、通信ファブリックインタフェース１１１１ａ、中間和計算器１１１１ｄ、計算コントロール１１１１ｆ、および記憶デバイスインタフェース１１１１ｇに結合しうる。計算コントロール１１１１ｆは、中間和計算器１１１１ｄ、再計算器１１１１ｅ、および記憶デバイスインタフェース１１１１ｇに結合しうる。

通信ファブリックインタフェース１１１１ａは、並列ＲＳ−ＲＡＩＤアーキテクチャ１００と外部デバイスとの間で情報シンボルを転送し、通信ファブリック１２００とＲＡＩＤコントローラ１１１１の要素との間で、情報シンボル、情報シンボルの所定部分、データシンボル、中間チェックサムシンボルなどのチェックサムシンボル、コントロール信号、クロック信号などを結合しうる。通信ファブリックインタフェース１１１１ａは、情報シンボルをビットからバイト、ワード、または他のシンボルにリフォーマットしうる、信号を多重化し逆多重化しうる、データ転送を同期化しうる、ラインドライバおよび受信機によって信号をバッファリングしうるなどを行いうる。換言すれば、通信ファブリックインタフェース１１１１ａは、デジタルバスなどの通信ファブリックを通じて送信するためにデジタル信号を調節しうる、データ転送をバッファリングしうるなどを行いうる。

ＲＡＩＤコントロールユニット１１１１ｂは、通信ファブリックインタフェース１１１１ａおよび記憶デバイスから信号を受信しうる、情報シンボルの部分集合からデータシンボルを選択しうる、記憶デバイスにわたってデータおよびチェックサムシンボルをストライピングしうる、前方誤り訂正コード（ｆｏｒｗａｒｄ−ｅｒｒｏｒ ｃｏｒｒｅｃｔｉｏｎ ｃｏｄｅ）（ＦＥＣｃｏｄｅ）によって中間和デバイス１１１１ｃの作動を制御しうるなどを行いうる。たとえば、情報シンボルの部分集合は、データシンボルによって表され、かつ、ＲＡＩＤコントローラ１１１１によって制御される作動可能なデータ記憶デバイスに記憶される情報シンボルでありうる。中間和デバイス１１１１ｃは、記憶デバイス故障センスユニット１１１１ｈから状態情報を得ることができるＲＡＩＤコントロールユニット１１１１ｂから作動可能な記憶デバイスの数に関する状態情報を受信してもよい。

記憶デバイス故障センスユニット１１１１ｈは、ＲＡＩＤコントローラ１１１１に結合する任意の記憶デバイスの作動に関する状態を確定し、作動可能な記憶デバイスのリストを確定しうる。換言すれば、記憶デバイス故障センスユニット１１１１ｈは、所与の記憶デバイスが、データおよびチェックサムの確実な記憶に適さなくなったかどうかを判定しうる。記憶デバイス故障センスユニット１１１１ｈは、信頼性のある作動について記憶デバイスを試験しうる、所与の記憶デバイスがオンラインであるかどうかを判定しうる、所与の記憶デバイスからの応答が、所定のタイムアウト間隔内に受信されない場合、ユニットオフラインを宣言しうる、信号品質メトリックが、記憶デバイスから読出されたデータについて閾品質より小さいかどうかを判定しうる、作動可能な記憶デバイスを挙げうるなどを行いうる。記憶デバイス故障センスユニット１１１１ｈは、こうした試験の結果を記録し、ＲＡＩＤコントロールユニット１１１１ｂなどのＲＡＩＤコントローラ１１１１の要素のために、作動可能な記憶デバイスのリストを配信しうる。

中間和計算器１１１１ｄは、中間的でローカルで部分的な和を計算することができ、この和内に、チェックサムおよびデータについての誤り訂正コード計算が、式８および式１３に関してそれぞれ述べたように分解されうる。中間的なまたは部分的な和は、ＲＡＩＤコントローラ１１１１に報告するクラスタ内の作動可能な記憶デバイスから読出されるシンボルの重み付き和であってよい。たとえば、記憶デバイスのクラスタおよびこうした部分和の合計の対応する制限は、構成行列２００などの構成行列または他のデータ構造から確定されてもよい。中間和計算器１１１１ｄは、ＲＡＩＤコントローラ１１１２またはＲＡＩＤコントローラ１１１３などの他のＲＡＩＤコントローラから対応する部分和を受信した後、データおよびチェックサムシンボルを計算しうる。

再計算器１１１１ｅは、ＲＡＩＤコントローラ１１１１に直接結合する記憶デバイスからのデータに基づいて中間的なローカルのチェックサムを、また、通信ファブリックインタフェース１１１１ａを通して転送される他のＲＡＩＤコントローラからのローカルでない中間チェックサムを再計算しうる。換言すれば、データまたはチェックサムシンボルの変化が、ＲＡＩＤコントローラ１１１１に直接結合するローカルの記憶デバイスにおいて起こるか、または、通信ファブリック１２００を通じてＲＡＩＤコントローラ１１１１に送信される中間チェックサムによって起こると、再計算器１１１１ｅは、中間和計算器１１１１ｄからの結果を相応して修正しうる。

計算コントロール１１１１ｆは、中間チェックサム計算結果または再計算されたチェックサムが、ＦＥＣのために使用されるべきかどうかを判定するために、中間和計算器１１１１ｄと再計算器１１１１ｅの両方を制御しうる。ＲＡＩＤコントロール１１１１ｂは、中間和計算器１１１１ｄの結果と再計算器１１１１ｅの結果のいずれが計算されるかを判定するために、直接にまたは通信ファブリックインタフェース１１１１ａを通して計算コントロール１１１１ｆに合図し(signal)うる。ＲＡＩＤコントロール１１１１ｂは、記憶デバイス故障センスユニット１１１１ｈから、データ記憶デバイスに関する作動に関する状態などの状態情報を得ることができる。

並列ＲＡＩＤコントローラ１１１１〜１１１３は、

によって、チェックサムを計算し記憶しうる。式中、インデックスｔは、１からＲＡＩＤコントローラの数ｒまでの範囲にあることができ、ｃ_ｉ，ｔは、ｔ番目のインデックスについてのｉ番目の中間チェックサムである。たとえば、ｒは、並列ＲＡＩＤアーキテクチャ１００の場合、３に等しい。構成行列２００に関して述べたように、ＱＳ（ｔ）およびＱＥ（ｔ）は、開始および終了記憶デバイスをＲＡＩＤコントローラにマッピングし、それぞれの中間チェックサムｃ_ｉ，ｊを生成する部分和の合計の制限を確定しうる。関数Ｊ（・）は、たとえば、Ｊ（１００２）＝２であるように、オフセットを減算しうる。

ＲＡＩＤコントローラ１１１１などのｔ番目のＲＳ−ＲＡＩＤコントローラは、

によって、中間チェックサムｃ_ｉ，ｔを計算しうる。

中間チェックサムｃ_ｉ，ｔの使用は、通信ファブリック１２００上のデータトラフィックを低減することができ、並列ＲＳ−ＲＡＩＤアーキテクチャ１００のスループットを増加させることができる。たとえば、８＋４ＲＳ−ＲＡＩＤアーキテクチャでは、単一の主要なＲＡＩＤコントローラが、記憶デバイスの全てを制御し、チェックサムを計算する場合、８つのデータシンボルが、通信ファブリックを通じて転送されうる。対照的に、８＋４並列ＲＳ−ＲＡＩＤアーキテクチャからの中間チェックサム計算器結果を使用して、２つの中間チェックサムシンボルだけが、通信ファブリックを通じて転送される必要がある可能性がある。

中間チェックサムおよび全チェックサムを計算することに加えて、並列ＲＳ−ＲＡＩＤアーキテクチャ１００は、データシンボルが変化すると、チェックサムシンボルを修正するかまたは維持しうる。たとえば、データシンボルが、ｄ_ｊからｄ'_ｊに変化すると、チェックサムは、
ｃ'_ｉ＝ｃ_ｉ＋ｆ_ｉ，ｊ（ｄ'_ｊ−ｄ_ｊ） 式９
によって、再計算されうる。式９の計算を実施するとき、ＲＡＩＤコントローラ１１１１は、データ差（ｄ'_ｊ−ｄ_ｊ）を計算し、ファンデルモンデ要素ｆ_ｉ，ｊ、すなわち、

によって、データ差に重み付けしうる。

個々の並列ＲＡＩＤコントローラ１１１１〜１１１３は、一時的な成分ｃ'_ｉ，ｔをＲＡＩＤコントローラ１１１１〜１１１３の他のコントローラに送出しうる。

ＲＳ−ＲＡＩＤコントローラ１１１１〜１１１３は、

によって、それぞれの割当てられた記憶デバイスを更新しうる。

記憶デバイスが故障する、たとえば、記憶デバイス故障センスユニット１１１１ｈがハードディスククラッシュを検出すると、拡大行列の逆行列Ｉｎｖ（Ａ）が、並列ＲＡＩＤコントローラ１１１１〜１１１３によって修正されて、残りのまたは作動可能なデータ記憶デバイスに対応する逆行列Ｉｎｖ（Ａ'）が形成される。行列Ｉｎｖ（Ａ'）は、記憶デバイスのさらなる故障が起こらない限り、静的データ構造である可能性がある。別の記憶デバイスが故障すると、Ｉｎｖ（Ａ'）が一回計算され、その後、ＲＡＩＤコントローラ１１１１〜１１１３などの全ての作動可能なＲＡＩＤコントローラにブロードキャストされうる。より多くの記憶デバイスが後で故障する場合、新しい逆行列Ｉｎｖ（Ａ''）が、再計算され、全てのＲＡＩＤコントローラにブロードキャストされてもよい。

並列ＲＳ−ＲＡＩＤアーキテクチャ１００は、記憶デバイスが故障しても、各ＲＡＩＤコントローラにおいてローカルで計算される中間和または部分和を使用して、データシンボルを回復しうる。回復されるデータ

は、

から回復される可能性がある。式中、Ｉｎｖ（Ａ'）の要素は、ａ_ｉ，ｊ（１≦ｉ≦ｎおよび１≦ｊ≦ｎ）で示されてもよい。対応するデータおよびチェックサムシンボルＥ'＝［ｅ_１、ｅ_２、…、ｅ_ｎ］^Ｔの要素は、作動可能でかつ選択されたデータ記憶デバイスから読出されうる。並列ＲＳ−ＲＡＩＤアーキテクチャ１００は、Ｅの行ならびに添加された単位行列とファンデルモンデ行列の対応する部分集合を選択するかまたは選抜して、それぞれ、Ｅ'およびＩｎｖ（Ａ'）が形成されうる。換言すれば、並列ＲＳ−ＲＡＩＤアーキテクチャ１００は、データ回復計算を、

によって、部分和または中間データシンボルの集合に分解しうる。式中、ｅ_ｊは、ｔ番目のＲＳ−ＲＡＩＤコントローラの制御下にある全てのデータまたはチェックサムシンボルの集合であると理解される。

他の並列ＲＳ−ＲＡＩＤコントローラから、中間データシンボルなどのメッセージを受信すると、個々のＲＡＩＤコントローラは、最初に中間データシンボル

を計算し、次に、

によって、回復されるデータ

を計算しうる。

図４Ａは、データ記憶用の並列ＲＳ−ＲＡＩＤアーキテクチャのためのチェックサムプログラムフローチャート４００Ａの例を示す。プログラムフローチャート４００Ａは、プログラムステップＳ４１０で開始し、並列ＲＳ−ＲＡＩＤアーキテクチャの構成行列が読出されうるプログラムステップＳ４２０に進みうる。たとえば、構成行列は、図２に関して述べた構成行列などの、所与のＲＡＩＤコントローラに関連する記憶デバイスについての開始デバイス番号と終了デバイス番号を指定しうる。各ＲＡＩＤコントローラは、構成行列のローカルなコピーを記憶しうる、構成行列を他のＲＡＩＤコントローラと調和させうる、構成行列を、高レベルのＲＡＩＤデバイスまたはネットワークコントローラから受信しうるなどを行いうることが理解されてもよい。

プログラムステップＳ４２０から、プログラムフローは、プログラムステップＳ４２５に進むことができ、プログラムステップＳ４２５にて、プログラムは、外部デバイスから、記憶される情報保持データシンボルを読出すことができる。たとえば、プログラムは、通信ファブリックを通じて受信される２Ｋビットのデータブロックの集合をフラッシュドライブから受信しうる。

プログラムステップＳ４２５から、プログラムは、中間チェックサムが計算されうるプログラムステップＳ４３０に進むことができる。たとえば、中間チェックサムまたはデータおよびパリティ計算は、式８およびガロア体の特性を使用した、データワードの線形結合から計算されうる。プログラムステップＳ４３０は、中間チェックサムを計算し、１）所与のＲＡＩＤコントローラにコードワードシンボルの所定部分を供給する個々の作動可能な記憶ユニットからの記憶されたコードワードシンボルを使用して中間チェックサムを更新するかまたは維持し、２）通信ファブリックを通じて所与のＲＡＩＤコントローラと通信する他のＲＡＩＤコントローラからの中間チェックサムを集計しうる。換言すれば、ローカルな部分集合データ記憶ユニットからの低レーテンシのデータおよびパリティビット、バイト、またはワードは、他のデータ記憶ユニットからの、ｃ_ｉ，ｔの形態の、高レーテンシの、蓄積されるかまたは部分的に合計されたデータおよびパリティと結合されうる。その後、プログラムは、プログラムステップＳ４６０に進む。

ステップＳ４６０にて、プログラムは、中間チェックサムを異なるＲＳ−ＲＡＩＤコントローラに配信しうる。たとえば、Ｑ（ｔ）＝ｔである場合、プログラムステップＳ４６０は、第１のＲＡＩＤコントローラからの第１の中間チェックサムｃ_１，１を第２および第３のＲＡＩＤコントローラに配信しうる。

プログラムステップＳ４６０から、プログラムフローは、プログラムステップＳ４７０に進むことができ、プログラムステップＳ４７０にて、プログラムは、他のＲＡＩＤコントローラから中間チェックサムを受信しうる。プログラムステップＳ４７０から、プログラムはプログラムステップＳ４８０に進みうる。中間チェックサムの集合によって、各ＲＡＩＤコントローラが、式８によって完全なチェックサムｃ_ｉを計算し、その後の誤り訂正および検出計算についてｃ_ｉを記憶することが可能になる。たとえば、プログラムは、第２および第３の中間チェックサムｃ_ｉ，２およびｃ_ｉ，３を受信することができ、第２および第３の中間チェックサムｃ_ｉ，２およびｃ_ｉ，３は、ローカルに計算された第１のチェックサムｃ_ｉ，１と共に、ｃ_１を計算するためのチェックサムの十分な集合を形成しうる。

プログラムステップＳ４８０から、プログラムフローは、プログラムステップＳ４９０に進むことができ、プログラムステップＳ４９０にて、プログラムは、プログラムを実行するＲＡＩＤコントローラに割当てられるデータおよび完全なチェックサムシンボルを記憶しうる。たとえば、プログラムは、ディスクのアレイにわたってデータおよびチェックサムシンボルをストライピングしうる。プログラムステップＳ４９０から、プログラムフローは、プログラム実行が停止しうるプログラムステップＳ４９５に進みうる。

図４Ｂは、データ記憶用の並列ＲＳ−ＲＡＩＤアーキテクチャのためのチェックサム更新プログラムフローチャート４００Ｂの例を示す。プログラムフローチャート４００Ｂは、ステップＳ４４０で開始し、ステップＳ４４２に進む。

ステップＳ４４２にて、並列ＲＳ−ＲＡＩＤアーキテクチャは、データの変化を受信する可能性がある。たとえば、記憶デバイスは、古いデータシンボルを置換するために新しいデータシンボルを受信してもよい。その後、プログラムフローはステップＳ４４４に進みうる。

ステップＳ４４４にて、記憶デバイスに結合するＲＡＩＤコントローラは、式１０によって、一時的な成分を計算しうる。ＲＡＩＤコントローラは、新しいデータシンボルと古いデータシンボルとのデータ差を得、ファンデルモンデ行列要素によってデータ差に重み付けしてもよい。その後、プログラムフローはステップＳ４４６に進みうる。

ステップＳ４４６にて、一時的な成分は、他のＲＡＩＤコントローラに伝達されうる。ある実施形態では、通信ファブリックは、種々のＲＡＩＤコントローラを結合してもよい。通信ファブリックは、データ変化に対応する一時的な成分を、チェックサムを記憶する記憶デバイスを制御するＲＡＩＤコントローラに伝達しうる。その後、プログラムフローはステップＳ４４８に進みうる。

ステップＳ４４８にて、チェックサムを記憶する記憶デバイスを制御するＲＡＩＤコントローラは、たとえば、式１１によって、受信した一時的な成分に基づいてチェックサムを更新してもよい。その後、プログラムフローはステップＳ４５０に進み、停止しうる。

図５は、データ記憶用の並列ＲＳ−ＲＡＩＤアーキテクチャのためのデータプログラムフローチャート５００の例を示す。プログラムフローチャート５００は、ステップＳ５１０で開始し、ステップＳ５２０に進むことができ、ステップＳ５２０にて、並列ＲＳ−ＲＡＩＤアーキテクチャの構成行列が、図４Ａに関して説明したように読出されうる。プログラムステップＳ５２０から、プログラムフローは、プログラムステップＳ５２５に進むことができ、プログラムステップＳ５２５にて、データおよびチェックサムシンボルが、記憶デバイスから読出されうる。たとえば、８つのデータおよび４つのチェックサムシンボルは、１２の記憶デバイスから読出されうる。この例では、少なくとも８つのデータまたはチェックサムシンボルが、作動可能な記憶デバイスから読出されうる。

プログラムステップＳ４２５から、プログラムフローは、プログラムステップＳ５３０に進むことができ、プログラムステップＳ５３０にて、プログラムは、中間データシンボルを計算しうる。たとえば、プログラムは、式１３によって、中間データシンボルを計算しうる。式１３で使用される重み係数ａ_ｉ，ｊは、予め計算され、ＲＡＩＤコントローラに配信されるか、または、プログラムステップＳ５２０において構成行列を読出した後などに、必要に応じて再計算されてもよいことが理解されてもよい。プログラムステップＳ５３０から、プログラムフローは、プログラムステップＳ５４０に進むことができ、プログラムステップＳ５４０にて、プログラムは、中間データシンボルを並列ＲＡＩＤコントローラに配信しうる。

プログラムステップＳ５４０から、プログラムフローは、プログラムステップＳ５５０に進むことができ、プログラムステップＳ５５０にて、プログラムは、並列ＲＡＩＤコントローラから中間データシンボルを受信しうる。プログラムステップＳ５５０から、プログラムフローは、プログラムステップＳ５６０に進むことができ、プログラムステップＳ５６０にて、プログラムは、ローカルなＲＡＩＤコントローラと並列ＲＡＩＤコントローラの両方から来た中間データシンボルから、回復されるデータシンボルを計算しうる。換言すれば、プログラムは、式１４によって、中間データシンボルを合計しうる。プログラムステップＳ５６０から、プログラムフローは、プログラム実行が停止しうるプログラムステップＳ５７０に進むことができる。

本発明は、本発明の特定の例示的な実施形態に関連して述べられたが、多くの代替、修正、および変形が当業者に明らかになることが明らかである。したがって、本明細書で述べる本発明の実施形態は、制限的でなく、例証的であることを意図される。本発明の精神および範囲から逸脱することなく行われてもよい変更が存在する。

Claims (26)

1. 分散データ記憶デバイスであって、
   複数の並列データ記憶クラスタであって、
   複数のデータシンボルを記憶する複数のデータ記憶デバイス、および、
   前記複数のデータ記憶デバイスのそれぞれに結合し、前記複数のデータシンボルからローカルな中間チェックサムを計算し、前記ローカルな中間チェックサムを含む複数の中間チェックサムに基づいて前記複数のデータシンボルのチェックサムを計算するよう構成されたＲＡＩＤコントローラを含む、複数の並列データ記憶クラスタと、
   前記複数の並列データ記憶クラスタのそれぞれに結合し、前記複数の中間チェックサムを前記複数の並列データ記憶クラスタに配信する通信ファブリックとを備える分散データ記憶デバイス。
2. 前記ＲＡＩＤコントローラは、前記複数のデータシンボルの重み付き和に基づいて前記ローカルな中間チェックサムを計算する、請求項１に記載の分散データ記憶デバイス。
3. 前記複数の並列データ記憶クラスタの複数のＲＡＩＤコントローラの少なくとも１つは、他の並列データ記憶クラスタから前記中間チェックサムを受信し、前記複数の並列なデータ記憶クラスタの複数のデータ記憶デバイスのうちの１つに記憶するためのチェックサムを、前記受信した中間チェックサムと、前記ローカルな中間チェックサムとに基づいて生成する、請求項１又は２に記載の分散データ記憶デバイス。
4. 前記ＲＡＩＤコントローラは、前記チェックサムをデータ記憶デバイスに記憶するようさらに構成される請求項１から３のいずれか１項に記載の分散データ記憶デバイス。
5. 前記通信ファブリックは、前記複数のデータシンボルを含む複数の情報シンボルを前記複数の並列データ記憶クラスタに配信するようさらに構成される請求項１から４のいずれか１項に記載の分散データ記憶デバイス。
6. 前記ＲＡＩＤコントローラは、前記複数の情報シンボルのサブセットから前記複数のデータシンボルを選択するＲＡＩＤコントロールユニットをさらに備える請求項５に記載の分散データ記憶デバイス。
7. 前記ＲＡＩＤコントロールユニットは、前記複数のデータ記憶デバイスから作動可能なデータ記憶デバイスのリストを確定する記憶デバイス故障センスユニットをさらに備える請求項６に記載の分散データ記憶デバイス。
8. 前記ＲＡＩＤコントロールユニットは、作動可能なデータ記憶デバイスの前記リストに基づいてデータ回復行列を計算するようさらに構成される請求項７に記載の分散データ記憶デバイス。
9. 前記通信ファブリックは、作動可能なデータ記憶デバイスの前記リストが変化すると、前記データ回復行列を前記複数の並列データ記憶クラスタに配信するようさらに構成される請求項８に記載の分散データ記憶デバイス。
10. 前記ＲＡＩＤコントローラは、作動可能なデータ記憶デバイスのリストに基づいて前記中間チェックサムを計算するよう構成された中間和デバイスをさらに備える請求項６に記載の分散データ記憶デバイス。
11. 前記中間和デバイスは、データシンボルが変化すると、前記ローカルな中間チェクサムを更新するよう構成された再計算器をさらに備える請求項１０に記載の分散データ記憶デバイス。
12. 前記ＲＡＩＤコントロールユニットは、前記データ回復行列を計算するために、添加された単位行列とファンデルモンデ行列の逆行列を求めるようさらに構成される請求項８に記載の分散データ記憶デバイス。
13. 中間和デバイスは、前記データ回復行列に基づく中間データシンボル、ならびに、前記記憶デバイスから読出されるリードデータシンボルおよびリードチェックサムシンボルの少なくとも一方のベクトルを計算するようさらに構成される請求項１２に記載の分散データ記憶デバイス。
14. 前記ＲＡＩＤコントロールユニットは、前記添加された単位行列とファンデルモンデ行列の行の集合ならびに作動可能なデータ記憶デバイスの前記リストに基づくベクトルを選択し、前記データ回復行列を形成するために前記行の集合の逆行列を求めるようさらに構成される請求項１２に記載の分散データ記憶デバイス。
15. 前記ＲＡＩＤコントローラは、中間和デバイスに中間データシンボルを計算させるメッセージを前記複数の並列データ記憶クラスタに送出するようさらに構成される請求項１４に記載の分散データ記憶デバイス。
16. 前記通信ファブリックは、前記中間データシンボルを前記複数の並列データ記憶クラスタのそれぞれに配信するようさらに構成される請求項１５に記載の分散データ記憶デバイス。
17. 前記ＲＡＩＤコントローラは、複数の中間データシンボルから、回復されるデータシンボルを計算するようさらに構成される請求項１６に記載の分散データ記憶デバイス。
18. 前記ローカルな中間チェックサムは、前記ＲＡＩＤコントローラに割当てられた前記複数のデータ記憶デバイスに対応する前記複数のデータシンボルの部分集合の部分和(partial sum)である請求項１から１７のいずれか１項に記載の分散データ記憶デバイス。
19. 前記中間データシンボルは、前記ＲＡＩＤコントローラに割当てられた前記データ記憶デバイスに対応する前記データシンボルの部分集合および前記リードチェックサムシンボルの部分和である請求項１３に記載の分散データ記憶デバイス。
20. データ記憶方法であって、
    複数のデータ記憶デバイスを複数の並列データ記憶クラスタに割当てること、
    前記複数の並列データ記憶クラスタのそれぞれに複数のデータシンボルを記憶すること、
    前記複数の並列データ記憶クラスタのそれぞれに含まれる複数のＲＡＩＤコントローラのそれぞれが、前記複数のデータシンボルの重み付き和から中間チェックサムを計算すること、
    前記複数のＲＡＩＤコントローラの少なくとも１つが、前記複数のＲＡＩＤコントローラの他のＲＡＩＤコントローラのそれぞれから前記中間チェックサムを受信すること、
    前記複数のＲＡＩＤコントローラの少なくとも１つが、計算した前記中間チェックサムおよび前記他のＲＡＩＤコントローラのそれぞれから受信した前記中間チェックサムに基づいて前記複数のデータシンボルのチェックサムを計算すること、および、
    前記複数のデータ記憶デバイスの少なくとも１つに前記チェックサムを記憶することを含むデータ記憶方法。
21. 情報シンボルの部分集合から前記複数のデータシンボルを選択すること、および、
    通信ファブリックを使用して、前記複数の並列データ記憶クラスタに前記選択されたデータシンボルを配信することをさらに含む請求項２０に記載のデータ記憶方法。
22. 前記複数の並列データ記憶クラスタのそれぞれの中の作動可能なデータ記憶デバイスの集合を検知することをさらに含む請求項２１に記載のデータ記憶方法。
23. 作動可能なデータ記憶デバイスの前記集合に基づくデータ回復行列を、前記複数の並列データ記憶クラスタのそれぞれに配信することをさらに含む請求項２２に記載のデータ記憶方法。
24. 前記データ回復行列に基づく中間データシンボルならびに前記記憶デバイスから読出されるリードデータシンボルおよびリードチェックサムシンボルの少なくとも一方のベクトルを計算することをさらに含む請求項２３に記載のデータ記憶方法。
25. 前記中間データシンボルを前記複数の並列データ記憶クラスタのそれぞれに配信すること、および、
    前記中間データシンボルの和から、回復されるデータシンボルを計算することをさらに含む請求項２４に記載のデータ記憶方法。
26. 分散データアーキテクチャにおける誤り訂正のための方法であって、
    複数のデータ記憶デバイスを複数の並列データ記憶クラスタに割当てる構成行列を読出すこと、
    複数のデータシンボルを前記複数の並列データ記憶クラスタに記憶すること、
    前記複数の並列データ記憶クラスタのそれぞれに含まれる複数のＲＡＩＤコントローラのそれぞれが、前記割当てられたデータ記憶デバイスに記憶された前記複数のデータシンボルから中間チェックサムを計算することであって、それにより、少なくとも１つの中間チェックサムがそれぞれのデータ記憶クラスタについて計算される、計算すること、
    前記複数のＲＡＩＤコントローラの少なくとも１つが、前記複数のＲＡＩＤコントローラの他のＲＡＩＤコントローラのそれぞれから前記中間チェックサムを受信すること、
    チェックサムを形成するために、前記複数のＲＡＩＤコントローラの少なくとも１つが、計算した前記中間チェックサムおよび前記他のＲＡＩＤコントローラのそれぞれから受信した前記中間チェックサムを合計すること、および、
    前記チェックサムを少なくとも１つのデータ記憶デバイスに記憶する方法。

Images