(57)【要約】  シンドローム生成及びデータ復旧のための方法及びシステムが説明される。このシステムは、１つ又は複数のストレージデバイスに接続されて、データの復旧用のパリティを生成するパリティ生成器を含む。このパリティ生成器は、ストレージデバイスの１つ又は複数にあるデータに基づいて第１のパリティ要素を生成する第１の比較器と、ストレージデバイスの１つ又は複数からのデータを乗算係数と乗算して積を生成する乗算器と、この乗算器に接続されて、この積に少なくとも部分的に基づき第２のパリティ要素を生成する第２の比較器と、第１のパリティ要素と第２のパリティ要素との間で選択を行うセレクタとを含む。【選択図】なし
2008525898.tif 000002
【特許請求の範囲】
【請求項１】
１つ又は複数のストレージブロックからのデータに基づいて第１のパリティ要素を生成する第１の比較器と、
前記ストレージブロックの１つ又は複数からの前記データを乗算係数と乗算して積を生成する乗算器と、
前記乗算器に接続されて、前記積に少なくとも部分的に基づき第２のパリティ要素を生成する第２の比較器と、
前記第１の比較器及び前記第２の比較器に接続されて、前記第１のパリティ要素と前記第２のパリティ要素との間で選択を行うセレクタと
を備える、装置。
【請求項２】
前記第２の比較器に接続されて、前記第２のパリティ要素に対して除算演算を行う除算器をさらに備える、請求項１に記載の装置。
【請求項３】
前記第１の比較器に接続されて、前記第１のパリティ要素を記憶する第１のバッファをさらに備える、請求項１に記載の装置。
【請求項４】
前記第２の比較器に接続されて、前記第２のパリティ要素を記憶する第２のバッファをさらに備える、請求項１に記載の装置。
【請求項５】
前記第１の比較器はＸＯＲ（排他的ＯＲ）ゲートである、請求項１に記載の装置。
【請求項６】
前記第２の比較器はＸＯＲ（排他的ＯＲ）ゲートである、請求項１に記載の装置。
【請求項７】
前記乗算器はガロア体乗算を行う、請求項１に記載の装置。
【請求項８】
前記第１の比較器は、前記ストレージブロックの１つ又は複数からのデータに基づいて、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを生成する、請求項１に記載の装置。
【請求項９】
前記第２の比較器は、前記乗算器からの出力を使用して、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを生成する、請求項８に記載の装置。
【請求項１０】
前記第１の比較器はＲＡＩＤ  Ｐシンドロームを生成し、且つ前記第２の比較器はＲＡＩＤ  Ｑシンドロームを生成する、請求項９に記載の装置。
【請求項１１】
１つ又は複数のストレージブロックからのデータを比較することに基づいて第１のパリティ要素を計算すること、
前記ストレージブロックの１つ又は複数からの前記データを乗算係数と乗算することであって、それによって、積を生成する、乗算すること、
前記積に少なくとも部分的に基づいて、第２のパリティ要素を計算すること、及び
前記第１のパリティ要素と前記第２のパリティ要素との間で選択を行うこと
を含む、方法。
【請求項１２】
前記第１のパリティ要素を計算することは、前記ストレージブロックの１つ又は複数からのデータに基づいて、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを計算することを含む、請求項１１に記載の方法。
【請求項１３】
前記第２のパリティ要素を計算することは、前記積に少なくとも部分的に基づいて、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを計算することを含む、請求項１１に記載の方法。
【請求項１４】
前記ストレージブロックの１つ又は複数からの前記データを乗算係数と乗算することは、前記ストレージブロックの１つ又は複数からの前記データをガロア体被乗数と乗算することを含む、請求項１１に記載の方法。
【請求項１５】
前記第２のパリティ要素を除数で除算することをさらに含む、請求項１１に記載の方法。
【請求項１６】
前記第１のパリティ要素を第１のバッファに記憶することをさらに含む、請求項１１に記載の方法。
【請求項１７】
前記第２のパリティ要素を第２のバッファに記憶することをさらに含む、請求項１１に記載の方法。
【請求項１８】
前記第１のパリティ要素及び前記第２のパリティ要素は並列に計算される、請求項１１に記載の方法。
【請求項１９】
データを記憶する１つ又は複数のストレージデバイスと、
前記１つ又は複数のストレージデバイスに接続されて、データの復旧用のパリティを生成するパリティ生成器であって、
前記ストレージデバイスにある１つ又は複数のデータに基づいて第１のパリティ要素を生成する第１の比較器と、
前記ストレージデバイスの１つ又は複数からのデータを乗算係数と乗算して積を生成する乗算器と、
前記乗算器に接続されて、前記積に少なくとも部分的に基づき第２のパリティ要素を生成する第２の比較器と、
前記第１の比較器及び前記第２の比較器に接続されて、前記第１のパリティ要素と前記第２のパリティ要素との間で選択を行うセレクタと
を含む、パリティ生成器と
を備える、システム。
【請求項２０】
前記第２の比較器に接続されて、前記第２のパリティ要素に対して除算演算を行う除算器をさらに備える、請求項１９に記載のシステム。
【請求項２１】
前記乗算器はガロア体乗算を行う、請求項１９に記載のシステム。
【請求項２２】
前記第１の比較器及び前記第２の比較器は並列に動作する、請求項１９に記載のシステム。
【請求項２３】
前記第１の比較器は、前記ストレージデバイスの１つ又は複数からのデータに基づいて、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを生成する、請求項１９に記載のシステム。
【請求項２４】
前記第２の比較器は、前記積に少なくとも部分的に基づいて、ＲＡＩＤ（独立ディスク冗長アレイ）シンドロームを生成する、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施の形態は、シンドローム生成及びデータ復旧に関し、より具体的には、ＰＱ  ＲＡＩＤシンドローム生成及びデータ復旧に関する。
【背景技術】
【０００２】
ファイバチャネルシステム及びギガビットイーサネットシステム等を有する大規模ストレージシステムの使用が増大するにつれて、これらのシステムは、複数のディスク故障にますます影響されやすくなっている。ディスク容量の急成長も、ディスク故障時のディスク復旧時間を長引かせている。この復旧時間が長引くことによって、障害ディスクに記憶されたユーザデータ及びパリティ情報の復元中に、ディスク故障が続いて発生する確率が増大している。加えて、長期間読み出されないままにされていたデータによって引き起こされる潜在的なセクタ故障が、データの喪失をもたらすディスク故障の後のデータ復旧を妨げるおそれがある。高いデータ完全性が必要とされるアレイにＡＴＡ（アドバンストテクノロジーアタッチメント）ディスク等の安価なディスクを使用することも、このようなディスク故障の確率を増大させている。
【０００３】
ＲＡＩＤ（独立ディスク冗長アレイ）アーキテクチャは、ディスク故障からの復旧を可能にするために開発されたものである。通常、複数のディスクからのデータのＸＯＲ（排他的ＯＲ）が、冗長ディスクに保持される。ディスク故障の場合、故障ディスクのデータは、生存ディスクのデータをＸＯＲすることによって復元される。復元されたデータは、スペアディスクに書き込まれる。しかしながら、復元が完了する前に第２のディスクが故障すると、データは喪失する。わずか１つのディスクのみの喪失を防ぐ従来のディスクアレイは、データ復旧には不十分であり、特に、大規模ストレージシステムには不十分である。
【０００４】
添付図面の図において、本発明を、限定ではなく一例として説明する。添付図面では、同様の参照符号は同様の要素を指す。
【発明を実施するための最良の形態】
【０００５】
詳細な説明
シンドローム生成及びデータ復旧のためのシステム及び方法の実施形態を説明する。以下の説明では、多数の特定の詳細を述べる。しかしながら、本発明の実施形態は、これらの特定の詳細がなくても実施できることが理解される。それ以外の場合には、既知の回路、構造、及び技法は、この説明の理解を分かりにくくしないように詳細に示されていない。
【０００６】
本明細書全体を通じて「一実施形態」に言及しているが、これは、その実施形態と共に説明する特定の特徴、構造、又は特性が、本発明の少なくとも１つの実施形態に含まれることを意味する。したがって、本明細書の全体を通じたさまざまな箇所に「一実施形態では」というフレーズが現れるが、必ずしもすべてが同じ実施形態に言及しているとは限らない。さらに、特定の特徴、構造、又は特性を、１つ又は複数の実施形態において任意の適した方法で組み合わせてもよい。
【０００７】
図１を参照すると、ブロック図は、複数のディスク故障からの復旧を可能にするシステム１００を示している。システム１００は、１０２〜１２４等のデータを記憶するための１つ又は複数のストレージブロック、及び、１３０〜１４４等のパリティ情報又はシンドローム情報を記憶するための２つ以上のストレージブロックを含む。一実施形態では、システム１００は、ＲＡＩＤ（独立ディスク冗長アレイ）システムである。一実施形態では、Ｐシンドローム及びＱシンドロームの２つのシンドロームが生成されて記憶される。Ｐシンドロームは、１つのストライプにわたってパリティを計算することにより生成される。Ｑシンドロームは、ガロア体乗算を使用することによって生成される。データ復旧のための再生方式は、ガロア体乗算及びガロア体除算の双方を使用する。
【０００８】
以下は、ｎ個のデータディスク及び２つのチェックディスクを有するストレージアレイのＰ及びＱを生成するための式である。
【０００９】
【数１】
2008525898.tif 000003
（式１）
2008525898.tif 000004
（式２）
【００１０】
Ｐは、
【００１１】
【数２】
2008525898.tif 000005
【００１２】
（ＸＯＲ）演算を使用して１つのストライプにわたり計算されたデータ（Ｄ）の単純なパリティである。Ｑは、ガロア体乗算器（ｇ）を使用した乗算（＊）を必要とする。
【００１３】
以下の式は、データブロックＤａを更新する時のＰ及びＱの生成を示している。
【００１４】
【数３】
2008525898.tif 000006
【００１５】
復旧を必要とする複数のディスク故障には４つのケースがある。ケース１では、Ｐ及びＱが故障する。このケースでは、Ｐ及びＱは、上記に示した式１及び式２を使用して再生することができる。
【００１６】
ケース２では、Ｑ及びデータディスク（Ｄａ）が故障する。このケースでは、Ｄａは、Ｐ及び残りのデータディスクを使用して式１を介し再生することができる。Ｑは、その後、式２を使用して再生することができる。
【００１７】
ケース３では、Ｐ及びデータディスク（Ｄａ）が故障する。このケースでは、Ｄａは、Ｑ、残りのデータディスク、及び以下の式を使用して再生することができる。
【００１８】
【数４】
2008525898.tif 000007
【００１９】
ここで、
【００２０】
【数５】
2008525898.tif 000008
【００２１】
Ｄａが再生された後、Ｐは式１を使用して再生することができる。
【００２２】
ケース４では、２つのデータディスク（Ｄａ及びＤｂ）が故障する。このケースでは、Ｄａ及びＤｂは、Ｐ及びＱ、残りのデータディスク、並びに以下の式を使用して再生することができる。
【００２３】
【数６】
2008525898.tif 000009
【００２４】
ここで、
【００２５】
【数７】
2008525898.tif 000010
【００２６】
以下は、上述したケースにおけるディスク故障からの復旧例である。以下の例では、データパスは、１バイト幅、すなわち８ビット幅であると仮定される。したがって、ガロア体のＧＦ（２８）が使用される。本発明は、１バイト幅よりも大きなデータパス又は１バイト幅よりも小さなデータパスについても実施することができ、より大きなガロア体又はより小さなガロア体を使用することができる。
【００２７】
以下の式は、２つの８ビット要素（ｂ及びｃ）を乗算して８ビット積（ａ）を与えるのに使用することができる。
ｂ＝［ｂ７  ｂ６  ｂ５  ｂ４  ｂ３  ｂ２  ｂ１  ｂ０］であり、ｃ＝［ｃ７  ｃ６  ｃ５  ｃ４  ｃ３  ｃ２  ｃ１  ｃ０］である。
【００２８】
【数８】
2008525898.tif 000011
【００２９】
図２は、ｇ＝００００  ００１０の場合のガロア体乗算器ｇａの値の例を提供する表２００を示している。ＧＦ（２８）の生成器の負の累乗は、以下の式を使用して計算することができる。
ｇ−ａ＝ｇ２５５−ａ
【００３０】
以下の例は、４つのデータディスク及び２つのパリティディスクを有するディスクアレイのＰパリティ及びＱパリティを生成する方法を示している。各データブロックは１データバイトを含むものと仮定する。Ｄｉを、ディスクＩに含まれるデータとする（ｉ＝０、１、２，３）。次のデータストライプ、すなわち、Ｄ０＝１０１１  ０１００、Ｄ１＝００１０  １１００、Ｄ２＝１１００  ０１１０、及びＤ３＝１１０１  ０１０１を考える。この場合、Ｐは、次のように、式１を使用して生成することができる。
【００３１】
【数９】
2008525898.tif 000012
【００３２】
Ｑは、次のように、式２を使用して生成することができる。
【００３３】
【数１０】
2008525898.tif 000013
【００３４】
図２の表から、ｇ０＝００００  ０００１、ｇ１＝００００  ００１０、ｇ２＝００００  ０１００、及びｇ３＝００００  １０００となる。
したがって、
【００３５】
【数１１】
2008525898.tif 000014
【００３６】
次の例は、上記で生成されたアレイを使用して２つのディスク故障から復旧する方法を示している。第１のケースでは、Ｐ及びＱが故障する。このケースでは、Ｐ及びＱが上記に示したような式１及び式２を使用して再生される。第２のケースでは、Ｑ及びデータディスク（Ｄａ）が故障する。このケースでは、Ｄａは、Ｐ及び残りのデータディスクを使用して式１を介し再生することができる。Ｑは、その後、式２を使用して再生することができる。第３のケースでは、Ｐ及びデータディスク（Ｄａ）が故障する。このケースでは、Ｄａは、Ｑ、残りのデータディスク、及び以下の式を使用して再生することができる。
【００３７】
【数１２】
2008525898.tif 000015
【００３８】
ここで、
【００３９】
【数１３】
2008525898.tif 000016
【００４０】
たとえば、ディスク２が故障したものと仮定する。この場合、
【００４１】
【数１４】
2008525898.tif 000017
【００４２】
図２の表を使用して、ｇ２５３＝０１００  ０１１１である。したがって、
【００４３】
【数１５】
2008525898.tif 000018
【００４４】
この時、すべてのデータブロックが利用可能であるので、Ｐは、その後、式１を使用して再生することができる。
【００４５】
第４のケースでは、２つのデータディスク（Ｄａ及びＤｂ）が故障する。このケースでは、Ｄａ及びＤｂは、Ｐ及びＱ、残りのデータディスク、並びに以下の式を使用して再生することができる。
【００４６】
【数１６】
2008525898.tif 000019
【００４７】
ここで、
【００４８】
【数１７】
2008525898.tif 000020
【００４９】
たとえば、ディスク１及び３が故障したものと仮定する。この場合、
【００５０】
【数１８】
2008525898.tif 000021
【００５１】
図２の表から、ｇ２５４＝１０００  １１１０であり、ｇ２＝００００  ０１００である。したがって、
【００５２】
【数１９】
2008525898.tif 000022
【００５３】
図３は、本発明の一実施形態によるシステム３００のブロック図である。システム３００は、乗算器３０２と、３０４及び３０６等の１つ又は複数の比較器とを含む。一実施形態では、これらの比較器の１つ又は複数はＸＯＲ（排他的ＯＲ）ゲートである。また、システム３００は、３０８及び３１０等の１つ又は複数のバッファも含んでもよい。バッファ３０８は、比較器３０６からの出力を記憶する。比較器３０６は、図１に示すストレージブロックから読み出されるデータ３２０を、バッファ３０８の出力と比較する。このように、比較器３０６は、上述したＰシンドロームを計算するために使用してもよい。Ｐシンドロームは、１つのストライプにわたるパリティである。
【００５４】
乗算器３０２は、被乗数３３０を、図１に示すストレージブロックから読み出されたデータ３２０と乗算する。一実施形態では、被乗数３３０は、図２の表２００に示すようなガロア体である。乗算器３０２の出力は、比較器３０４によって、バッファ３１０の出力と比較される。このように、ガロア体乗算を行うことができ、Ｑシンドロームを計算することができる。また乗算器３０２は、複数のディスクが故障する４つのケースに関して上述した式のさまざまな乗算演算を行うために使用してもよい。データは、被乗数３３０を１に等しく設定することによって、乗算器を通過することが可能となる。セレクタ３１２は、乗算器３０２の出力と比較器３０４の出力との間で選択を行うために使用してもよい。一実施形態では、セレクタ３１２はマルチプレクサ（ＭＵＸ）である。
【００５５】
システム３００は、複数のディスクが故障する４つのケースに関して上述した式の除算演算を行うために使用される除算器３１４も含んでもよい。たとえば、ケース４では、Ｄａの再生の計算は除算演算を有し、この除算演算は除算器３１４が行ってもよい。データは、除数３４０を１に等しく設定することによって、除算器３１４を通過することが可能となり得る。これは、除算演算を行うことが必要とされない場合に望ましい場合がある。
【００５６】
図３に示すように、システム３００は、Ｐシンドローム及びＱシンドロームの生成を並列に行う。必要とされる他の乗算演算及び除算演算も、システム３００が行うことができる。セレクタ３１６は、システムの所望の出力を選択するために使用することができる。一実施形態では、セレクタ３１６はマルチプレクサ（ＭＵＸ）である。
【００５７】
図４は、本発明の一実施形態による１つ又は複数のストレージブロックのデータの復旧を助けるパリティを生成するための方法を示している。４００において、第１のパリティ要素が、ストレージブロックの１つ又は複数からのデータを比較することに基づいて計算される。４０２において、ストレージブロックの１つ又は複数からのデータが乗算係数と乗算されて、積が生成される。４０４において、第２のパリティ要素が、この積に少なくとも部分的に基づいて計算される。４０６において、第１のパリティ要素と第２のパリティ要素との間で選択が行われる。一実施形態では、上述したように、第１のパリティ要素はＰシンドロームであり、第２のパリティ要素はＱシンドロームである。一実施形態では、第２のパリティ要素は、除算器によってさらに除算される。一実施形態では、第１のパリティ要素及び第２のパリティ要素はバッファリングされる。一実施形態では、第１のパリティ要素及び第２のパリティ要素は、並列に計算される。
【００５８】
いくつかの実施形態の観点から本発明を説明してきたが、当業者は、本発明が、説明してきた実施形態に限定されず、添付の特許請求の範囲の精神及び範囲内において変更及び改変して実施できることを認識するであろう。本説明は、したがって、限定ではなく例示としてみなされるべきである。
【図面の簡単な説明】
【００５９】
【図１】複数のディスク故障からの復旧を可能にするシステムを示すブロック図である。
【図２】ガロア体の値の例の表である。
【図３】本発明の一実施形態によるシステムを示すブロック図である。
【図４】本発明の一実施形態による方法を示すフロー図である。
【図１】
2008525898.tif 000023
【図２】
2008525898.tif 000024
【図３】
2008525898.tif 000025
【図４】
2008525898.tif 000026
【国際調査報告】
2008525898.tif 000027
2008525898.tif 000028
2008525898.tif 000029