(57)【特許請求の範囲】
【請求項１】
１つ又は複数のストレージブロックからのデータに基づいて第１のパリティ要素を生成する第１の演算器と、
前記１つ又は複数のストレージブロックからの前記データを、前記１つ又は複数のストレージブロックの故障ケースに従って選択された乗算係数と乗算して積を生成する乗算器と、
前記積に基づき第２のパリティ要素を生成する第２の演算器と、
前記第１のパリティ要素と前記第２のパリティ要素との間で選択を行う第１のセレクタと
を備える装置。
【請求項２】
前記第２のパリティ要素に対して除算演算を行う除算器をさらに備える
請求項１に記載の装置。
【請求項３】
前記第１の演算器が生成した前記第１のパリティ要素を記憶する第１のバッファ
をさらに備える
請求項１または２に記載の装置。
【請求項４】
前記第２のパリティ要素を記憶する第２のバッファ
をさらに備える
請求項１から３のいずれかに記載の装置。
【請求項５】
前記乗算器が生成した前記積および前記第２の演算器が生成した前記第２のパリティ要素の一方を選択して出力する第２のセレクタ
をさらに備え、
前記除算器は、前記第２のセレクタの出力に対して除算演算を行い、
前記第１のセレクタは、前記除算器による除算演算で得られた値と、前記第１のパリティ要素との間で、選択を行う
請求項２に記載の装置。
【請求項６】
前記第１の演算器が生成した値を記憶する第１のバッファと、
前記除算器による除算演算で得られた値を記憶する第２のバッファと
をさらに備え、
前記第１の演算器は、前記データと、前記第１のバッファが記憶している値とに基づいて、前記第１のパリティ要素を生成し、
前記第２の演算器は、前記乗算器が生成した前記積と、前記第２のバッファが記憶している値とに基づいて、前記第２のパリティ要素を生成し、
前記第１のセレクタは、前記第１のバッファが記憶している値と前記第２のバッファが記憶している値との間で選択を行う
請求項５に記載の装置。
【請求項７】
前記乗算器は、前記データを通過させる場合に、１に設定された前記乗算係数と前記データとを乗算して前記積を生成し、
前記除算器は、前記データを通過させる場合に、前記第２のセレクタの出力を、１に設定された除数で除算する
請求項６に記載の装置。
【請求項８】
前記第１の演算器はＸＯＲ（排他的ＯＲ）ゲートである
請求項１から７のいずれかに記載の装置。
【請求項９】
前記第２の演算器はＸＯＲ（排他的ＯＲ）ゲートである
請求項１から８のいずれかに記載の装置。
【請求項１０】
前記乗算器はガロア体乗算を行う
請求項１から９のいずれかに記載の装置。
【請求項１１】
前記第１の演算器は、前記１つ又は複数のストレージブロックからのデータに基づいて、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを生成する
請求項１から１０のいずれかに記載の装置。
【請求項１２】
前記第２の演算器は、前記乗算器からの出力を使用して、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを生成する
請求項１１に記載の装置。
【請求項１３】
前記第１の演算器はＲＡＩＤ  Ｐシンドロームを生成し、且つ前記第２の演算器はＲＡＩＤ  Ｑシンドロームを生成する
請求項１２に記載の装置。
【請求項１４】
第１の演算器が、１つ又は複数のストレージブロックからのデータに基づいて第１のパリティ要素を生成する段階と、
乗算器が、前記１つ又は複数のストレージブロックからの前記データを、前記１つ又は複数のストレージブロックの故障ケースに従って選択された乗算係数と乗算して積を生成する段階と、
第２の演算器が、前記積に基づいて、第２のパリティ要素を生成する段階と、
第１のセレクタが、前記第１のパリティ要素と前記第２のパリティ要素との間で選択を行う段階と
を備える方法。
【請求項１５】
前記第１のパリティ要素を生成する段階は、前記１つ又は複数のストレージブロックからのデータに基づいて、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを生成する
請求項１４に記載の方法。
【請求項１６】
前記第２のパリティ要素を生成する段階は、前記積に基づいて、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを生成する
請求項１４または１５に記載の方法。
【請求項１７】
前記積を生成する段階は、前記データをガロア体被乗数と乗算する
請求項１４から１６のいずれかに記載の方法。
【請求項１８】
除算器が、前記第２のパリティ要素を除数で除算する段階
をさらに備える請求項１４から１７のいずれかに記載の方法。
【請求項１９】
前記第１の演算器によって生成された前記第１のパリティ要素を第１のバッファに記憶する段階
をさらに備える請求項１４から１８のいずれかに記載の方法。
【請求項２０】
前記第２のパリティ要素を第２のバッファに記憶する段階
をさらに備える請求項１４から１９のいずれかに記載の方法。
【請求項２１】
第２のセレクタが、前記乗算器によって生成された前記積および前記第２の演算器によって生成された前記第２のパリティ要素の一方を選択して出力する段階
をさらに備え、
前記除算する段階は、前記第２のセレクタの出力を除数で除算し、
前記第１のパリティ要素と前記第２のパリティ要素との間で選択を行う段階は、前記除算する段階において前記第２のパリティ要素を除数で除算して得られた値と、前記第１のパリティ要素との間で、選択を行う
請求項１８に記載の方法。
【請求項２２】
前記第１の演算器によって生成された値を第１のバッファに記憶する段階と、
前記除算器によって前記第２のセレクタの出力を除数で除算して得られた値を第２のバッファに記憶する段階と
をさらに備え、
前記第１のパリティ要素を生成する段階は、前記データと、前記第１のバッファに記憶されている値とに基づいて、前記第１のパリティ要素を生成し、
前記第２のパリティ要素を生成する段階は、前記乗算器が生成した前記積と、前記第２のバッファに記憶されている値とに基づいて、前記第２のパリティ要素を生成し、
前記第１のパリティ要素と前記第２のパリティ要素との間で選択を行う段階は、前記第１のバッファに記憶されている値と前記第２のバッファに記憶されている値との間で選択を行う
請求項２１に記載の方法。
【請求項２３】
前記積を生成する段階は、前記データを通過させる場合に、１に設定された前記乗算係数と前記データとを乗算して前記積を生成し、
前記除算する段階は、前記データを通過させる場合に、前記第２のセレクタの出力を、１に設定された除数で除算する
請求項２２に記載の方法。
【請求項２４】
前記第１のパリティ要素及び前記第２のパリティ要素は並列に計算される
請求項１４から２３のいずれかに記載の方法。
【請求項２５】
データを記憶する１つ又は複数のストレージデバイスと、
前記１つ又は複数のストレージデバイスに接続されて、データの復旧用のパリティを生成するパリティ生成器と
を備え、
前記パリティ生成器は、
前記１つ又は複数のストレージデバイスからのデータに基づいて第１のパリティ要素を生成する第１の演算器と、
前記１つ又は複数のストレージデバイスからの前記データを、前記１つ又は複数のストレージデバイスの故障ケースに従って選択された乗算係数と乗算して積を生成する乗算器と、
前記積に基づき第２のパリティ要素を生成する第２の演算器と、
前記第１のパリティ要素と前記第２のパリティ要素との間で選択を行う第１のセレクタと
を有するシステム。
【請求項２６】
前記パリティ生成器は、
前記第２のパリティ要素に対して除算演算を行う除算器
をさらに有する請求項２５に記載のシステム。
【請求項２７】
前記パリティ生成器は、
前記乗算器が生成した前記積および前記第２の演算器が生成した前記第２のパリティ要素の一方を選択して出力する第２のセレクタ
をさらに有し、
前記除算器は、前記第２のセレクタの出力に対して除算演算を行い、
前記第１のセレクタは、前記除算器による除算演算で得られた値と、前記第１のパリティ要素との間で、選択を行う
請求項２６に記載のシステム。
【請求項２８】
前記パリティ生成器は、
前記第１の演算器が生成した値を記憶する第１のバッファと、
前記除算器による除算演算で得られた値を記憶する第２のバッファと
をさらに有し、
前記第１の演算器は、前記データと、前記第１のバッファが記憶している値とに基づいて、前記第１のパリティ要素を生成し、
前記第２の演算器は、前記乗算器が生成した前記積と、前記第２のバッファが記憶している値とに基づいて、前記第２のパリティ要素を生成し、
前記第１のセレクタは、前記第１のバッファが記憶している値と前記第２のバッファが記憶している値との間で選択を行う
請求項２７に記載のシステム。
【請求項２９】
前記乗算器は、前記データを通過させる場合に、１に設定された前記乗算係数と前記データとを乗算して前記積を生成し、
前記除算器は、前記データを通過させる場合に、前記第２のセレクタの出力を、１に設定された除数で除算する、
請求項２８に記載のシステム。
【請求項３０】
前記乗算器はガロア体乗算を行う
請求項２５から２９のいずれかに記載のシステム。
【請求項３１】
前記第１の演算器及び前記第２の演算器は並列に動作する
請求項２５から３０のいずれかに記載のシステム。
【請求項３２】
前記第１の演算器は、前記データに基づいて、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを生成する
請求項２５から３１のいずれかに記載のシステム。
【請求項３３】
前記第２の演算器は、前記積に基づいて、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを生成する
請求項２５から３２のいずれかに記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施の形態は、シンドローム生成及びデータ復旧に関し、より具体的には、ＰＱ  ＲＡＩＤシンドローム生成及びデータ復旧に関する。
【背景技術】
【０００２】
ファイバチャネルシステム及びギガビットイーサネットシステム等を有する大規模ストレージシステムの使用が増大するにつれて、これらのシステムは、複数のディスク故障にますます影響されやすくなっている。ディスク容量の急成長も、ディスク故障時のディスク復旧時間を長引かせている。この復旧時間が長引くことによって、障害ディスクに記憶されたユーザデータ及びパリティ情報の復元中に、ディスク故障が続いて発生する確率が増大している。加えて、長期間読み出されないままにされていたデータによって引き起こされる潜在的なセクタ故障が、データの喪失をもたらすディスク故障の後のデータ復旧を妨げるおそれがある。高いデータ完全性が必要とされるアレイにＡＴＡ（アドバンストテクノロジーアタッチメント）ディスク等の安価なディスクを使用することも、このようなディスク故障の確率を増大させている。
【０００３】
ＲＡＩＤ（独立ディスク冗長アレイ）アーキテクチャは、ディスク故障からの復旧を可能にするために開発されたものである。通常、複数のディスクからのデータのＸＯＲ（排他的ＯＲ）が、冗長ディスクに保持される。ディスク故障の場合、故障ディスクのデータは、生存ディスクのデータをＸＯＲすることによって復元される。復元されたデータは、スペアディスクに書き込まれる。しかしながら、復元が完了する前に第２のディスクが故障すると、データは喪失する。わずか１つのディスクのみの喪失を防ぐ従来のディスクアレイは、データ復旧には不十分であり、特に、大規模ストレージシステムには不十分である。
特許文献１  米国特許第５０９９４８４号明細書
特許文献２  米国特許第５２７１０１２号明細書
特許文献３  米国特許第５４９９２５３号明細書
特許文献４  米国特許第５５７９４７５号明細書
特許文献５  米国特許第６２４７１５７号明細書
特許文献６  米国特許第６５６７８９１号明細書
特許文献７  米国特許出願公開第２００５／００５０３８４号明細書
特許文献８  米国特許出願公開第２００５／０１０８６１３号明細書
特許文献９  米国特許出願公開第２００６／０１２３２６８号明細書
非特許文献１  Park, Chan-Ik, "Efficient Placement of Parity and Data to Tolerate Two Disk Failures in Disk Array Systems," IEEE Transactions on Parallel and Distributed Systems, Nov. 1995, vol. 6, No. 11, pp. 1177-1184.
非特許文献２  Burkhard, Walter A. et al., "Disk Array Storage System Reliability," IEEE, 1993, pp. 432-441.
非特許文献３  Blaum, Mario et al., "EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures," IEEE Transactions on Computers, Feb. 1995, vol. 44, No. 2, pp. 192-202.
非特許文献４  Gibson, Garth A. et al., "Coding Techniques for Handling Failures in Large Disk Arrays," Computer Science Division, Electrical Engineering and Computer Sciences, Berkeley, CA, 1994, pp. 1-29.
非特許文献５  Patterson, David A. et al., "A Case for Redundant Arrays of Inexpensive Disks (RAID)," Computer Science Division, Department of Electrical Engineering and Computer Sciences, Berkeley, CA, 1988, pp. 109-116.
【０００４】
添付図面の図において、本発明を、限定ではなく一例として説明する。添付図面では、同様の参照符号は同様の要素を指す。
【発明を実施するための最良の形態】
【０００５】
詳細な説明
シンドローム生成及びデータ復旧のためのシステム及び方法の実施形態を説明する。以下の説明では、多数の特定の詳細を述べる。しかしながら、本発明の実施形態は、これらの特定の詳細がなくても実施できることが理解される。それ以外の場合には、既知の回路、構造、及び技法は、この説明の理解を分かりにくくしないように詳細に示されていない。
【０００６】
本明細書全体を通じて「一実施形態」に言及しているが、これは、その実施形態と共に説明する特定の特徴、構造、又は特性が、本発明の少なくとも１つの実施形態に含まれることを意味する。したがって、本明細書の全体を通じたさまざまな箇所に「一実施形態では」というフレーズが現れるが、必ずしもすべてが同じ実施形態に言及しているとは限らない。さらに、特定の特徴、構造、又は特性を、１つ又は複数の実施形態において任意の適した方法で組み合わせてもよい。
【０００７】
図１を参照すると、ブロック図は、複数のディスク故障からの復旧を可能にするシステム１００を示している。システム１００は、１０２〜１２４等のデータを記憶するための１つ又は複数のストレージブロック、及び、１３０〜１４４等のパリティ情報又はシンドローム情報を記憶するための２つ以上のストレージブロックを含む。一実施形態では、システム１００は、ＲＡＩＤ（独立ディスク冗長アレイ）システムである。一実施形態では、Ｐシンドローム及びＱシンドロームの２つのシンドロームが生成されて記憶される。Ｐシンドロームは、１つのストライプにわたってパリティを計算することにより生成される。Ｑシンドロームは、ガロア体乗算を使用することによって生成される。データ復旧のための再生方式は、ガロア体乗算及びガロア体除算の双方を使用する。
【０００８】
以下は、ｎ個のデータディスク及び２つのチェックディスクを有するストレージアレイのＰ及びＱを生成するための式である。
【０００９】
【数１】
0004664988.tif 000002
（式１）
0004664988.tif 000003
（式２）
【００１０】
Ｐは、
【００１１】
【数２】
0004664988.tif 000004
【００１２】
（ＸＯＲ）演算を使用して１つのストライプにわたり計算されたデータ（Ｄ）の単純なパリティである。Ｑは、ガロア体乗算器（ｇ）を使用した乗算（＊）を必要とする。
【００１３】
以下の式は、データブロックＤａを更新する時のＰ及びＱの生成を示している。
【００１４】
【数３】
0004664988.tif 000005
【００１５】
復旧を必要とする複数のディスク故障には４つのケースがある。ケース１では、Ｐ及びＱが故障する。このケースでは、Ｐ及びＱは、上記に示した式１及び式２を使用して再生することができる。
【００１６】
ケース２では、Ｑ及びデータディスク（Ｄａ）が故障する。このケースでは、Ｄａは、Ｐ及び残りのデータディスクを使用して式１を介し再生することができる。Ｑは、その後、式２を使用して再生することができる。
【００１７】
ケース３では、Ｐ及びデータディスク（Ｄａ）が故障する。このケースでは、Ｄａは、Ｑ、残りのデータディスク、及び以下の式を使用して再生することができる。
【００１８】
【数４】
0004664988.tif 000006
【００１９】
ここで、
【００２０】
【数５】
0004664988.tif 000007
【００２１】
Ｄａが再生された後、Ｐは式１を使用して再生することができる。
【００２２】
ケース４では、２つのデータディスク（Ｄａ及びＤｂ）が故障する。このケースでは、Ｄａ及びＤｂは、Ｐ及びＱ、残りのデータディスク、並びに以下の式を使用して再生することができる。
【００２３】
【数６】
0004664988.tif 000008
【００２４】
ここで、
【００２５】
【数７】
0004664988.tif 000009
【００２６】
以下は、上述したケースにおけるディスク故障からの復旧例である。以下の例では、データパスは、１バイト幅、すなわち８ビット幅であると仮定される。したがって、ガロア体のＧＦ（２８）が使用される。本発明は、１バイト幅よりも大きなデータパス又は１バイト幅よりも小さなデータパスについても実施することができ、より大きなガロア体又はより小さなガロア体を使用することができる。
【００２７】
以下の式は、２つの８ビット要素（ｂ及びｃ）を乗算して８ビット積（ａ）を与えるのに使用することができる。
ｂ＝［ｂ７  ｂ６  ｂ５  ｂ４  ｂ３  ｂ２  ｂ１  ｂ０］であり、ｃ＝［ｃ７  ｃ６  ｃ５  ｃ４  ｃ３  ｃ２  ｃ１  ｃ０］である。
【００２８】
【数８】
0004664988.tif 000010
【００２９】
図２は、ｇ＝００００  ００１０の場合のガロア体乗算器ｇａの値の例を提供する表２００を示している。ＧＦ（２８）の生成器の負の累乗は、以下の式を使用して計算することができる。
ｇ−ａ＝ｇ２５５−ａ
【００３０】
以下の例は、４つのデータディスク及び２つのパリティディスクを有するディスクアレイのＰパリティ及びＱパリティを生成する方法を示している。各データブロックは１データバイトを含むものと仮定する。Ｄｉを、ディスクＩに含まれるデータとする（ｉ＝０、１、２，３）。次のデータストライプ、すなわち、Ｄ０＝１０１１  ０１００、Ｄ１＝００１０  １１００、Ｄ２＝１１００  ０１１０、及びＤ３＝１１０１  ０１０１を考える。この場合、Ｐは、次のように、式１を使用して生成することができる。
【００３１】
【数９】
0004664988.tif 000011
【００３２】
Ｑは、次のように、式２を使用して生成することができる。
【００３３】
【数１０】
0004664988.tif 000012
【００３４】
図２の表から、ｇ０＝００００  ０００１、ｇ１＝００００  ００１０、ｇ２＝００００  ０１００、及びｇ３＝００００  １０００となる。
したがって、
【００３５】
【数１１】
0004664988.tif 000013
【００３６】
次の例は、上記で生成されたアレイを使用して２つのディスク故障から復旧する方法を示している。第１のケースでは、Ｐ及びＱが故障する。このケースでは、Ｐ及びＱが上記に示したような式１及び式２を使用して再生される。第２のケースでは、Ｑ及びデータディスク（Ｄａ）が故障する。このケースでは、Ｄａは、Ｐ及び残りのデータディスクを使用して式１を介し再生することができる。Ｑは、その後、式２を使用して再生することができる。第３のケースでは、Ｐ及びデータディスク（Ｄａ）が故障する。このケースでは、Ｄａは、Ｑ、残りのデータディスク、及び以下の式を使用して再生することができる。
【００３７】
【数１２】
0004664988.tif 000014
【００３８】
ここで、
【００３９】
【数１３】
0004664988.tif 000015
【００４０】
たとえば、ディスク２が故障したものと仮定する。この場合、
【００４１】
【数１４】
0004664988.tif 000016
【００４２】
図２の表を使用して、ｇ２５３＝０１００  ０１１１である。したがって、
【００４３】
【数１５】
0004664988.tif 000017
【００４４】
この時、すべてのデータブロックが利用可能であるので、Ｐは、その後、式１を使用して再生することができる。
【００４５】
第４のケースでは、２つのデータディスク（Ｄａ及びＤｂ）が故障する。このケースでは、Ｄａ及びＤｂは、Ｐ及びＱ、残りのデータディスク、並びに以下の式を使用して再生することができる。
【００４６】
【数１６】
0004664988.tif 000018
【００４７】
ここで、
【００４８】
【数１７】
0004664988.tif 000019
【００４９】
たとえば、ディスク１及び３が故障したものと仮定する。この場合、
【００５０】
【数１８】
0004664988.tif 000020
【００５１】
図２の表から、ｇ２５４＝１０００  １１１０であり、ｇ２＝００００  ０１００である。したがって、
【００５２】
【数１９】
0004664988.tif 000021
【００５３】
図３は、本発明の一実施形態によるシステム３００のブロック図である。システム３００は、乗算器３０２と、３０４及び３０６等の１つ又は複数の比較器とを含む。一実施形態では、これらの比較器の１つ又は複数はＸＯＲ（排他的ＯＲ）ゲートである。また、システム３００は、３０８及び３１０等の１つ又は複数のバッファも含んでもよい。バッファ３０８は、比較器３０６からの出力を記憶する。比較器３０６は、図１に示すストレージブロックから読み出されるデータ３２０を、バッファ３０８の出力と比較する。このように、比較器３０６は、上述したＰシンドロームを計算するために使用してもよい。Ｐシンドロームは、１つのストライプにわたるパリティである。
【００５４】
乗算器３０２は、被乗数３３０を、図１に示すストレージブロックから読み出されたデータ３２０と乗算する。一実施形態では、被乗数３３０は、図２の表２００に示すようなガロア体である。乗算器３０２の出力は、比較器３０４によって、バッファ３１０の出力と比較される。このように、ガロア体乗算を行うことができ、Ｑシンドロームを計算することができる。また乗算器３０２は、複数のディスクが故障する４つのケースに関して上述した式のさまざまな乗算演算を行うために使用してもよい。データは、被乗数３３０を１に等しく設定することによって、乗算器を通過することが可能となる。セレクタ３１２は、乗算器３０２の出力と比較器３０４の出力との間で選択を行うために使用してもよい。一実施形態では、セレクタ３１２はマルチプレクサ（ＭＵＸ）である。
【００５５】
システム３００は、複数のディスクが故障する４つのケースに関して上述した式の除算演算を行うために使用される除算器３１４も含んでもよい。たとえば、ケース４では、Ｄａの再生の計算は除算演算を有し、この除算演算は除算器３１４が行ってもよい。データは、除数３４０を１に等しく設定することによって、除算器３１４を通過することが可能となり得る。これは、除算演算を行うことが必要とされない場合に望ましい場合がある。
【００５６】
図３に示すように、システム３００は、Ｐシンドローム及びＱシンドロームの生成を並列に行う。必要とされる他の乗算演算及び除算演算も、システム３００が行うことができる。セレクタ３１６は、システムの所望の出力を選択するために使用することができる。一実施形態では、セレクタ３１６はマルチプレクサ（ＭＵＸ）である。
【００５７】
図４は、本発明の一実施形態による１つ又は複数のストレージブロックのデータの復旧を助けるパリティを生成するための方法を示している。４００において、第１のパリティ要素が、ストレージブロックの１つ又は複数からのデータを比較することに基づいて計算される。４０２において、ストレージブロックの１つ又は複数からのデータが乗算係数と乗算されて、積が生成される。４０４において、第２のパリティ要素が、この積に少なくとも部分的に基づいて計算される。４０６において、第１のパリティ要素と第２のパリティ要素との間で選択が行われる。一実施形態では、上述したように、第１のパリティ要素はＰシンドロームであり、第２のパリティ要素はＱシンドロームである。一実施形態では、第２のパリティ要素は、除算器によってさらに除算される。一実施形態では、第１のパリティ要素及び第２のパリティ要素はバッファリングされる。一実施形態では、第１のパリティ要素及び第２のパリティ要素は、並列に計算される。
【００５８】
いくつかの実施形態の観点から本発明を説明してきたが、当業者は、本発明が、説明してきた実施形態に限定されず、添付の特許請求の範囲の精神及び範囲内において変更及び改変して実施できることを認識するであろう。本説明は、したがって、限定ではなく例示としてみなされるべきである。
【図面の簡単な説明】
【００５９】
【図１】複数のディスク故障からの復旧を可能にするシステムを示すブロック図である。
【図２】ガロア体の値の例の表である。
【図３】本発明の一実施形態によるシステムを示すブロック図である。
【図４】本発明の一実施形態による方法を示すフロー図である。
【図１】
0004664988.tif 000022
【図２】
0004664988.tif 000023
【図３】
0004664988.tif 000024
【図４】
0004664988.tif 000025