(57)【特許請求の範囲】
【請求項１】
ストレージアレイにおける記憶装置の最大ｎ個までの同時故障からの復旧を可能にする方法であって、
データを記憶するように構成された複数ｍの第１の装置を含む、所定数の記憶装置を有する前記アレイを設けるステップであって、ｍがｐ−１であり、ｐが素数であり、行パリティが、専用の行パリティ装置に記憶され、又は前記複数ｍの第１の装置にわたって循環される、所定数の記憶装置を有するアレイを設けるステップと、
前記アレイに少なくとも３つの対角パリティクラスを記憶するように構成された少なくとも３つの第２の装置を設けるステップと、
各装置を複数のブロックに分割するステップと、
前記ブロックを、各装置におけるブロックを含むストライプに編成するステップと、
データの各行について行パリティを計算するステップと、
データ及び行パリティを記憶している前記装置から全てのブロックを対角に割当てるステップと、
前記少なくとも３つの対角パリティクラスの各対角パリティクラスについて、共通の傾斜を有する全ての対角に沿って対角パリティを計算し、計算された対角パリティを前記対角パリティクラスに関連する前記第２の装置の１つに記憶するステップであって、各傾斜とｐとのモジューロが異なる値であるステップと、
前記行パリティ及び前記対角パリティを使用して、ｎ以下の１以上の記憶装置のうちの１つの故障について再構築を実施するステップであって、ｎがｐ以下であるステップと
からなる方法。
【請求項２】
前記第１の装置は、複数のデータ装置を含み、前記データ装置は、全て存在するのではなく、パリティを計算する際に、不在のデータ装置は全て、ゼロを格納しているものとして扱われる、請求項１に記載の方法。
【請求項３】
異なるストライプ内において、パリティブロックの場所は、装置ごとにシフトされる、請求項１に記載の方法。
【請求項４】
前記ストライプは、２の累乗数のビットのサイズを有する、請求項１に記載の方法。
【請求項５】
前記複数の第２の装置は、最大ｎ−１個までの装置からなる、請求項１に記載の方法。
【請求項６】
追加の対角パリティクラスを記憶するための追加の第２の記憶装置を追加するステップであって、前記追加の対角パリティクラスを有する共通の傾斜を有する全ての対角に沿って対角パリティのみが計算される、追加の第２の記憶装置を追加するステップと、
計算された対角パリティを、前記追加の対角パリティクラスに関連する前記追加の第２の装置に記憶するステップと
さらに含む、請求項１に記載の方法。
【請求項７】
ストレージアレイにおける記憶装置の最大ｎ個までの同時故障からの復旧を可能にするシステムであって、
データを記憶するように構成された複数ｍの第１の装置を含む、所定数の記憶装置を有するように構成されたストレージアレイであって、ｍがｐ−１であり、ｐが素数であり、行パリティが、専用の行パリティ装置に記憶され、又は前記複数ｍの第１の装置にわたって循環され、各装置が複数のブロックに分割され、前記ブロックが、各装置における同数のブロックを含むストライプに編成される、ストレージアレイを含み、
前記ストレージアレイは、少なくとも３つの対角パリティクラスを記憶するように構成された少なくとも３つの第２の装置を有するようにさらに構成され、前記少なくとも３つの対角パリティクラスの各対角パリティクラスは、前記データ及び行パリティに沿った傾斜により定義され、各対角パリティクラスに関連する各傾斜とｐとのモジューロが異なる値であり、
前記対角パリティクラスの全てについて、対角パリティを計算し、記憶し、前記行パリティ及び前記対角パリティを使用して、ｎ以下の１以上の記憶装置のうちの１つの故障について再構築を実施するように構成されたデバイスストレージモジュールであって、ｎがｐ以下である、デバイスストレージモジュールを含むストレージオペレーティングシステムをさらに含む、システム。
【請求項８】
１つのストライプ中の行パリティブロックは全て、単一の装置に記憶される、請求項７に記載のシステム。
【請求項９】
前記第１の装置は、複数のデータ装置を含み、前記データ装置は、全て存在するのではなく、パリティを計算する際に、不在のデータ装置は全て、ゼロを格納しているものとして扱われる、請求項７に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
[関連出願の相互参照]
本願は、２００５年１２月１５日に出願され、２００７年４月１９日に米国出願公開第ＵＳ２００７−００８９０４５号として発行された「TRIPLE PARITY TECHNIQUE FOR ENABLING EFFICIENT RECOVERY FROM TRIPLE FAILURES IN A STORAGE ARRAY」と題するピーター・エフ・コルベットらによる米国特許出願第１１／３０４，３６９号の一部継続出願であり、当該米国特許出願は、２００１年１２月２８日に出願され、２００６年１月３１日に米国特許第６，９９３，７０１号として発行された「ROW-DIAGONAL PARITY TECHNIQUE FOR ENABLING EFFICIENT RECOVERY FROM DOUBLE FAILURES IN A STORAGE ARRAY」と題するピーター・エフ・コルベットらによる米国特許出願第１０／０３５，６０７号の一部継続出願であり、両出願の教示は、参照によって本明細書に援用される。
【０００２】
[発明の分野]
本発明は、ストレージシステムに関し、より具体的には、ストレージアレイの複数の故障した記憶装置からの復旧を可能にするために、パリティデータをエンコードする技術に関する。
【背景技術】
【０００３】
[発明の背景]
ストレージシステムは通常、１以上の記憶装置を含み、必要に応じて、その中にデータを入れることができ、又はそこからデータを取得することができる。ストレージシステムは、種々のストレージアーキテクチャに従って実施することができ、限定はしないが、例えば、ネットワーク・アタッチド・ストレージ環境、ストレージ・エリア・ネットワーク、及び、クライアントまたはホストコンピュータに直接接続されたディスクアセンブリのようなストレージアーキテクチャに従って実施される場合がある。記憶装置は通常、ディスクドライブであり、「ディスク」という用語は一般に、内蔵型の回転磁気媒体記憶装置を表す。この文脈における「ディスク」という用語は、ハードディスクドライブ（ＨＤＤ）またはダイレクト・アクセス・ストレージ・デバイス（ＤＡＳＤ）と同義である。
【０００４】
ストレージシステム内のディスクは通常、１以上のグループに編成され、各グループは、ＲＡＩＤ（Redundant Array of Independent (or Inexpensive) Disks）として運用される。大半のＲＡＩＤ実施形態は、ＲＡＩＤグループ内の所与の数の物理的ディスクにわたってデータストライプを冗長書き込みし、ストライピングされたデータに関する冗長情報を適切に記憶することによって、データ記憶の信頼性／完全性を向上させる。冗長情報によって、記憶装置が故障したときに失われたデータの復旧が可能となる。
【０００５】
ディスクアレイの動作において、ディスクが故障することが予想される。高パフォーマンスのストレージシステムの目標は、データ損失発生までの平均時間（ＭＴＴＤＬ）を可能な限り長くすることであり、好ましくは、システムの期待耐用年数よりも遥かに長くすることである。１以上のディスクが故障すると、データは失われることがあり、その結果、その装置からデータを回復することは不可能になる。データの損失を避ける一般的手段としては、ミラーリング、バックアップ、およびパリティ保護が挙げられる。ミラーリングは、ディスクのようなストレージリソースの消費の面で、高価な手段である。バックアップは、バックアップが作成された後に変更されたデータを保護しない。パリティ手段が一般的である理由は、パリティ手段によれば、１個のディスクドライブをシステムに追加するだけで、単一の消去（１つのディスクの損失）を許容するデータの冗長エンコーディングが可能となるからである。
【０００６】
パリティー保護は、コンピュータシステムにおいて、ディスクのようなストレージデバイス上のデータを損失から保護するために使用される。パリティ値は、異なるデータを保持している複数の同様のディスクにわたって、特定ワードサイズ（通常は１ビット）のデータを（通常はモジューロ２で）合計することにより計算される場合があり、その後、その結果は、別の同様のディスクに記憶される場合がある。すなわち、パリティは、各ディスク上の対応する位置にあるビットからなる１ビット幅のベクトルに基づいて計算される場合がある。１ビット幅のベクトルに基づいて計算される場合、パリティは、計算された合計、及びその補数のいずれであってもよく、それらはそれぞれ、偶数パリティ及び奇数パリティと呼ばれる。１ビットベクトルに基づく加算と減算は、いずれも排他的論理和（ＸＯＲ）演算と等価である。その後、データは、いずれか１つのディスクの損失、又はいずれか１つのディスク上のデータの任意の部分の損失から保護される。パリティを記憶しているディスクが失われた場合、そのパリティは、データから復元することができる。データディスクの１つが失われた場合、そのデータは、生き残ったデータディスクの中身を１つに加算し、その結果を記憶されたパリティから減算することによって復元することができる。
【０００７】
通常、ディスクは複数のパリティグループに分割され、各パリティグループは、１以上のデータディスク、及び１つのパリティディスクを含む。パリティセットは、複数のデータブロック、及び１つのパリティブロックを含む一組のブロックであり、パリティブロックは、全データブロックのＸＯＲである。パリティグループは、そこから１以上のパリティセットが選択される元になる一組のディスクである。ディスク空間は、各ストライプが各ディスクから１つのブロックを保持するように、複数のストライプに分割される。あるストライプのブロックは通常、パリティグループ内の各ディスク上の同じ位置にある。ストライプ内の１つを除く全てのブロックは、データを保持するブロック（「データブロック」）であり、１つのブロックは、全てのデータのＸＯＲにより計算されたパリティを保持するブロック（「パリティブロック」）である。もしパリティブロックを全て１つのディスクに記憶し、それによって全てのパリティ情報（かつ、パリティ情報のみ）を保持する単一のディスクを作成した場合、ＲＡＩＤ４実施形態が得られる。もしパリティブロックが、各ストライプにおける異なるディスク内に保持される場合、通常は回転パターンを成して保持され、実施形態はＲＡＩＤ−５となる。用語「ＲＡＩＤ」及びその種々の実施形態は、周知であり、ディー・エー・パターソン、ジー・エー・ギブソン、及びアール・エイチ・カツD.による「A Case for Redundant Arrays of Inexpensive Disks (RAID)」、１９８８年６月、データ管理に関する国際会議（ＳＩＧＭＯＤ）の議事録に開示され、その内容は、参照により本明細書に援用される。
【０００８】
本明細書において、用語 「エンコーディング」は、データブロックの所定のサブセットにわたる冗長値の計算を意味するのに対し、用語「デコーディング」は、データブロックのサブセット及び冗長値を使用したデータブロック又はパリティブロックの再構築を意味する。もしパリティグループ中の１個のディスクが故障した場合、そのディスクの中身は、残りのデータブロックの中身を全て加算し、その結果をパリティブロックから減算することによって、スペアディスク（１又は複数）上にデコード（再構築）することができる。１ビットフィールドにおける２の補数による加算と減算は、いずれもＸＯＲ演算と等価であるから、この再構築は、生き残ったデータブロック全てとパリティブロックをＸＯＲ演算することからなる。同様に、もしパリティディスクが失われた場合、それは、生き残ったデータから同じ方法で再計算することができる。
【０００９】
パリティ手段は一般に、パリティグループ内の単一のディスク故障らの保護を提供する。各故障が異なるパリティグループ内で発生する限り、これらの手段は、複数のディスク故障からの保護も提供することができる。しかし、もしパリティグループ内の２個のディスクが同時に故障した場合、復元不可能なデータの損失を被ることになる。パリティグループ内の２個のディスクの同時故障は、かなり一般的に発生し、特にディスクの「磨耗」を原因として、及びディスクの動作に関する環境要因を原因として発生する。この文脈において、パリティグループ内の２個のディスクの同時故障は、「二重故障」と呼ばれる。
【００１０】
二重故障は一般に、１個のディスクが故障した後、その最初の故障からの復旧を試みている間に他のディスクが続けて故障する結果として発生する。復旧または再構築の時間は、ストレージシステムのアクティビティのレベルに依存する。すなわち、故障したディスクの再構築の間も、ストレージシステムは「オンライン」の状態を維持し、データにアクセス（すなわち、読み出し及び／又は書き込み）する（クライアント又はユーザからの）要求に対するサービスの提供を継続することが可能である。もしストレージシステムが、要求に対するサービスの提供に忙しい場合、再構築に要する経過時間は増加する。また、この再構築処理の時間は、ストレージシステム内のディスクのサイズ及び数が増加することによっても増加する。失われたデータを再構築するためには、生き残ったディスクの全てを読み出さなければならないからである。さらに、二重ディスク故障率は、パリティグループ内のディスク数の二乗に比例する。しかし、パリティグループを小さくすることは、各パリティグループが、冗長データのために専用の１個のディスク全体を必要とするため、費用がかかる。
【００１１】
ディスクの他の故障態様は、ディスクの単一のブロック又はセクタを読み出すことができない、メディア読み取りエラーである。ストレージアレイ内にパリティが保持されていれば、かかる読み取り不能なデータを再構築することができる。ただし、１個ディスクが既に故障しているときに、アレイ中の他のディスクにメディア読み取りエラーが発生した場合、データは失われる結果となる。これが、二重故障の第２の形態である。
【００１２】
ストレージ環境によっては、データがテープまたは他の長期アーカイブシステムにバックアップされるまでの短期記憶装置として、例えばニアラインストレージシステムのような相当な数の低品質ディスクドライブを使用することが一般的である。しかしながら、アレイ内のディスク数が増えるほど、複数の故障が発生する確率は増大する。あまり高価でない記憶装置の故障発生までの平均時間（ＭＴＴＦ）は低いことから、この確率は悪化する。従って、ストレージシステムは、３重以上の故障、すなわち、ストレージアレイ内の３以上の装置の同時故障を受けることもあり得る。さらに、シリアル・アタッチド・ＳＣＳＩ（ＳＡＳ）、ファイバチャネル（ＦＣ）のような多数のストレージプロトコルが存在する結果、ディスクシェルフのアーキテクチャは益々複雑なものとなり、それに付随して、かかるシェルフが受ける故障の数は増加する結果となり、さらに、故障したディスクシェルフに接続された各ディスクへのアクセスも失われる結果となる。
【００１３】
より一般的には、効率的で、かつ、１つのパリティグループ内のｎウェイ故障、すなわち、アレイ内の最大ｎ個までの記憶装置の故障に対して使用可能な汎用消去コードが必要とされている。ｎウェイ故障からのそのような更なる保護は、規制産業、長期アーカイブストレージ、災害復旧等との適合性を確保するために必要とされる場合がある。
【００１４】
[発明の概要]
本発明は、ｎウェイディスク故障からの保護を提供するようにエンコードされたストレージアレイのパリティグループ内の最大ｎ個までの記憶装置（例えばディスク）の復旧を可能にするｎウェイパリティ保護技術を提供することによって、従来技術の欠点を克服する。このアレイは、アレイの記憶装置が故障したときに、例えば行列数学等のような連立一次方程式を解く任意の技術を使用して、アレイの中身を再構築することができるように構成される。このストレージアレイはまず、ｍ個のデータディスクを有するアレイを構成することによって作成される。ここで、ｍ＝ｐ−１であり、ｐは素数、すなわち１又はそれ自体でしか割り切れない数である。行パリティは、例えばＲＡＩＤ 4に類似した形で専用の１個の行パリティディスクに記憶される場合があり、又は、例えばＲＡＩＤ５に類似した形で複数のデータディスクにわたって記憶され、それらのデータディスクにわたって循環される場合がある。
【００１５】
次に、ｎ−１個の対角パリティディスクがアレイに追加され、全部でｎビットのパリティ、すなわち、１つの行パリティビット、及びｎ−１個の対角パリティビットが形成される。各対角パリティセット（すなわち、対角）は、その対角に含まれるアレイのデータブロック及び行パリティブロックを定義する傾斜に関連する。すなわち、アレイ全体を通じて、同じ傾斜に沿って存在するデータブロック及び行パリティブロックは全て、１つの対角に関連する。パリティグループ内の同じ傾斜を有する対角は全て、１つの対角パリティクラスとして編成される。各対角パリティクラスについて、対角パリティを記憶するために、１つの対角パリティストレージディスクが設けられる。対角パリティクラスの最大数がｐ−１に制限されている場合、所望のレベルの保護を達成するために、追加される対角パリティディスクの数は、システム管理者により設定される場合がある。換言すれば、本明細書に記載する例示的実施形態によれば、結果として得られる連立方程式を確実に解けるようにするために、対角パリティクラスの数ｎ−１は、ｐ−１を超えることはできないので、ｎ≦ｐである。各対角パリティディスクは、アレイに追加された後、複数のブロックに分割され、データディスクのブロック、及び必要に応じて対角パリティディスクのブロックは、ストライプに編成される。その後、行パリティセット（すなわち、行）のデータブロックのＸＯＲを計算することによって行パリティが計算され、計算されたパリティは、その後、行パリティディスク、又は適当なデータディスク上の行パリティブロックに記憶される。
【００１６】
その後、データブロック及び行パリティブロックは全て、ｎ−１個の対角パリティクラスの対角に割り当てられる。対角パリティクラスの１つが選択され、そのクラスの各対角、すなわち、共通の（同じ）傾斜を有する対角について、対角パリティが計算される。その後、計算された対角パリティは、適当な対角パリティディスクに記憶される。他にも対角パリティクラスがある場合、このプロセスは、他のクラスのそれぞれについて繰り返される。
【００１７】
本発明の上記およびさらなる利点は、添付の図面と共に以下の説明を参照することによってより良好に理解することができる。図中、同じ参照符号は、同一の又は機能的に類似の要素を指している。
【図面の簡単な説明】
【００１８】
【図１】本発明の例示的実施形態による、ストレージシステムを含む環境を示す略ブロック図である。
【図２】本発明の例示的実施形態による、図１のストレージシステムにおいて使用される例示的ストレージオペレーティングシステムを示す略ブロック図である。
【図３】本発明の例示的実施形態による、パリティをエンコードする手順のステップの詳細を示すフロー図である。
【図４】本発明の例示的実施形態による、パリティストライプを示すディスクアレイの略ブロック図である。
【図５】本発明の例示的実施形態による、パリティストライプを示すディスクアレイの略ブロック図である;
【図６】本発明の例示的実施形態による、１以上のディスク故障からの復旧のための手順のステップの詳細を示すフロー図である。
【発明を実施するための形態】
【００１９】
[例示的実施形態の詳細な説明]
Ａ．ストレージシステム環境
図１は、本発明の例示的実施形態によれば有利である場合があるストレージシステム１２０を含む環境１００を示す略ブロック図である。本明細書に記載する本発明の技術は、如何なるタイプの特殊な目的の（例えばファイルサーバ又はファイラーのような）コンピュータにも、汎用コンピュータにも適用することができ、例えば、ストレージシステム１２０として実施され、又はストレージシステム１２０を含むスタンドアロンのコンピュータ、又はその一部に適用される場合がある。また、本発明の教示は、種々のストレージシステムアーキテクチャに適合させることができ、限定はしないが、例えば、ネットワーク・アタッチド・ストレージ環境、ストレージ・エリア・ネットワーク、及びクライアントまたはホストコンピュータに直接取り付けられたディスクアセンブリに適合させることができる。従って、「ストレージシステム」という用語は、ストレージ機能を実施するように構成され、他の装置又はシステムに関連する任意のサブシステムに加えて、そのような構成をも含むものとして、広い意味で解釈しなければならない。
【００２０】
例示的実施形態において、ストレージシステム１２０は、システムバス１３２により相互接続されたプロセッサ１２２、メモリ１２４、ネットワークアダプタ１２５、及びストレージアダプタ１２８を含む。メモリ１２４は、本発明に関連するソフトウェアプログラムコード及びデータ構造を記憶するためにプロセッサ及びアダプタによってアドレス指定可能な種々の記憶場所を含む。さらに、プロセッサ及びアダプタは、かかるソフトウェアコードを実行しデータ構造を操作するように構成された処理要素、及び／又は論理回路を含む場合がある。ストレージオペレーティングシステム２００は通常、その種々の部分がメモリに常駐し、処理要素によって実行され、とりわけストレージシステムにより実行されるストレージオペレーションを実行することにより、システム１２０を機能的に編成する。当業者には明らかであるように、本明細書に記載する本発明の技術に関連するプログラム命令の記憶及び実行には、他の処理手段、及び、例えば種々のコンピュータ読み取り可能媒体のような、他の記憶手段を使用してもよい。
【００２１】
ネットワークアダプタ１２５は、ポイント・ツー・ポイントリンク、ワイド・エリア・ネットワーク、公衆網（インターネット）を介して実施される仮想私設ネットワーク、又は共有ローカル・エリア・ネットワークを介して、ストレージシステム１２０を１以上のクライアント１１０に接続するように構成された複数のポートを有する。従って、ネットワークアダプタ１２５は、ノードをネットワークに接続するために必要とされる機械的、電気的、及び信号回路を含む場合がある。例えば、ネットワーク１０５は、イーサネット（登録商標）ネットワーク、又はファイバチャネル（ＦＣ）ネットワークとして実施される場合がある。各クライアント１１０は、ＴＣＰ／ＩＰのような所定のプロトコルに従って、データの離散的なフレーム又はパケットを交換することにより、ネットワーク１０５を介してストレージシステム１２０と通信することができる。
【００２２】
ストレージアダプタ１２８は、システム１２０上で実行されるストレージオペレーティングシステム２００と協働し、ユーザ（またはクライアント）から要求された情報にアクセスする。情報は、例えば、ビデオテープ、光学的手段、ＤＶＤ、磁気テープ、バブルメモリ、電子ランダムアクセスメモリ、微小電気機械、フラッシュまたは他の固体媒体、及び／又は、データ及びパリティ情報のような情報を記憶するように構成された任意の他の同様の媒体のような書き込み可能な記憶装置の、任意のタイプのアタッチドアレイに記憶される。ただし、本明細書に例示的に記載したように、情報は、アレイ１４０のＨＤＤ及び／又はＤＡＳＤのようなディスク１５０に記憶される。ストレージアダプタは、従来の高性能ＦＣシリアルリンクトポロジのようなＩ／Ｏ相互接続構成を介してディスクに接続される入出力（Ｉ／Ｏ）インタフェース回路を含む。
【００２３】
アレイ１４０への情報の記憶は、好ましくは、ディスク空間の全体的論理構成を定義する、１クラスタの物理的ストレージディスク１５０を含む１以上のストレージ「ボリューム」として実施される。各ボリュームは一般に、必須ではないが、それ独自のファイルシステムに関連する。ボリューム/ファイルシステム内のディスクは通常、１以上のグループに編成され、各グループは、ＲＡＩＤ（Redundant Array of Independent or Inexpensive Disks）として運用される。大半のＲＡＩＤ実施形態は、ＲＡＩＤグループ内の所与の数の物理ディスクにわたってデータ「ストライプ」を冗長書き込みし、ストライピングされたデータに関するパリティ情報を適切に記憶することによって、データ記憶の信頼性／完全性を向上させる。
【００２４】
本発明は、ディスクアレイ内の行パリティ、及び複数の対角パリティを使用して、複数の記憶装置故障の復旧を可能にするｎウェイパリティ（ｎＰ）技術を含む。本発明の技術は、好ましくは、ストレージオペレーティングシステム２００のディスクストレージモジュール（図２に２４０で示される）により実施され、ストレージシステムにおけるディスクのような複数の記憶装置にわたってパリティをストライプ状に構築する方法及びシステムを提供する。本発明は、以前から知られている方式に比べて、必要とされるパリティ計算の量を低減しながらも、さらに複数のディスク故障からの復旧のための計算量を低減する。さらに、本発明によれば、均一なストライプ深さ（各ディスクが１ストライプあたり同数のブロックを含む）、及び、任意のｎ個のディスク故障からの復元を可能にするために必要となる最少量であるｎ個のディスク分に等しい量のパリティ情報が得られる。
【００２５】
大まかに言えば、本発明は、ｍ＋ｎ個の記憶装置を含む。ここで、ｍ＝ｐ−１であり、ｐは素数であり、ｎは復元可能な故障の数である。パリティは一般に、パリティブロックを形成するための種々のデータブロックの排他的論理和（ＸＯＲ）として計算される。ＸＯＲ演算は一般に、各入力ブロックにおける同じ１ビットフィールドに対して実施され、単一の対応する出力のビットを生成する。前述のように、ＸＯＲ演算は、２つの１ビットフィールドの２の補数加算、又は減算と等価である。冗長パリティ情報は、すべての入力における同サイズの複数ビットフィールド（例えば、８、１６、３２、６４、１２８ビット）の合計として計算される場合もある。例えば、パリティの等価物は、３２ビットフィールドにおいて２の補数加算を使用してデータを加算することにより計算され、それぞれ３２ビットの冗長情報を生成する場合がある。これは単に、あるブロックをそれ自身とＸＯＲ演算するとゼロが生成されるため、同じ入力に対する２回のＸＯＲ演算によりブロックを生成すると、そのブロックの元の内容が生成されるという事実に依存しないことを想定したケースである。
【００２６】
当業者には明らかであるように、ブロックは（パリティ計算の目的で）、ファイルブロック、データベースブロック、ディスクセクタ、又は任意の他の便利なサイズのユニットに対応していてもよいし、対応しなくてもよい。パリティ計算に使用されるブロックサイズが、システムにおいて使用される何らかの他のブロックサイズと何らかの関係を有していなければならないという要件は無い。ただし、１以上の整数個のパリティブロックが、１以上の整数個のディスクセクタとして定義された１単位の中に丁度収まるであろうことは、予想される。多くの場合、多少の数のブロックは、ファイルシステムブロック又はデータベースブロックに対応することになり、それらは通常、４ｋ（４０９６）バイトのサイズ、又は２バイトのさらに高次の累乗（例えば、８ｋ、１６ｋ、３２ｋ、６４ｋ、１２８ｋ、２５６ｋ）のサイズを有することになる。
【００２７】
本明細書に記載するシステムは、例えば、フルストライプ書き込み処理を実施する場合がある。具体的には、一般に４ｋ又は８ｋバイトである個々のファイルブロックは、パリティ計算のためにのみ使用される複数のより小さなブロックに分割され、その結果、例えば４ｋバイトサイズのブロックのフルストライプを、アレイの種々のディスクに書き込むことができる場合がある。フルストライプをディスクに書き込む場合、パリティ計算は全て、その結果をディスクに書き込む前にメモリ上で実施される場合があり、従って、ディスク上のパリティの計算及び更新の負担は軽減される場合がある。
【００２８】
Ｂ．ストレージオペレーティングシステム 
ディスクへのアクセスを容易にするために、ストレージオペレーティングシステム２００は、ディスクにより提供される記憶空間を「仮想化」する機能を提供する仮想化モジュールと協働するｗｒｉｔｅ−ａｎｙｗｈｅｒｅファイルシステムを実施する。ファイルシステムは、情報を名前付きディレクトリ及びファイルオブジェクト（以下、「ディレクトリ」及び「ファイル」）の階層構造としてディスク上に論理編成する。各「ディスク上」のファイルは、データのような情報を記憶するように構成された一組のディスクブロックとして実施されるのに対し、ディレクトリは、特殊な形式のファイルとして実施される場合があり、その中に、他のファイル及びディレクトリの名前及びそれらへのリンクが記憶される。仮想化システムによれば、ファイルシステムは、情報を名前付きｖｄｉｓｋの階層構造としてディスク上にさらに論理編成することが可能となり、それによって、ファイル及びディレクトリに対するファイルベースの（ＮＡＳ）アクセスを可能にし、同時にファイルベースのストレージプラットフォームにおけるｖｄｉｓｋへのブロックベースの（ＳＡＮ）アクセスをさらに可能にすることによって、ストレージのためのＮＡＳとＳＡＮの統合システムアプローチを提供することが可能となる。
【００２９】
例示的実施形態として、ストレージオペレーティングシステムは、好ましくは、カリフォルニア州サニーベイルにあるネットアップ，インコーポレイテッドから入手可能なＮｅｔＡｐｐ  Ｄａｔａ  ＯＮＴＡＰオペレーティングシステムであり、このオペレーティングシステムは、Ｗｒｉｔｅ  Ａｎｙｗｈｅｒｅ  Ｆｉｌｅ  Ｌａｙｏｕｔ（ＷＡＦＬ）ファイルシステムを実施する。ただし、当然ながら、ｗｒｉｔｅ  ｉｎ  ｐｌａｃｅファイルシステムを含む任意のストレージオペレーティングシステムを、本明細書に記載する本発明の原理に従って拡張して使用してもよいと考えられる。従って、「ＯＮＴＡＰ」という用語が使用された場合であっても、この用語は、本発明の教示に通常適合する任意のストレージオペレーティングシステムを指すものとして広い意味で解釈しなければならない。
【００３０】
本明細書において、「ストレージオペレーティングシステム」という用語は、一般に、データアクセスを管理するコンピュータ上で動作可能なコンピュータ実行可能コードを指し、ストレージシステムの場合、マイクロカーネルとして実施されるデータＯＮＴＡＰストレージオペレーティングシステムのように、データアクセスセマンティックを実施する場合がある。また、ストレージオペレーティングシステムは、ＵＮＩＸ又はＷｉｎｄｏｗｓ  ＸＰ（登録商標）のような汎用オペレーティングシステム、あるいは、本明細書に記載するようなストレージアプリケーションのために構成された設定可能な機能を有する汎用オペレーティングシステムの上で動作するアプリケーションプログラムとして実施されることもある。
【００３１】
さらに、当業者には理解されるように、本明細書に記載する本発明の技術は、如何なるタイプの特殊な目的の（例えばファイルサーバ又はファイラーのような）コンピュータにも、汎用コンピュータにも適用することができ、例えば、ストレージシステムとして実施され、又はストレージシステムを含むスタンドアロンのコンピュータ、又はその一部にも適用される場合がある。また、本発明の教示は、種々のストレージシステムアーキテクチャに適合させることができ、限定はしないが、例えば、ネットワーク・アタッチド・ストレージ環境、ストレージ・エリア・ネットワーク、及びクライアントまたはホストコンピュータに直接取り付けられたディスクアセンブリに適合させることができる。従って、「ストレージシステム」という用語は、ストレージ機能を実施するように構成され、他の装置又はシステムに関連する任意のサブシステムに加えて、そのような構成をも含むものとして、広い意味で解釈しなければならない。
【００３２】
図２は、本発明とともに有利に使用可能なストレージオペレーティングシステム２００を示す略ブロック図である。ストレージオペレーティングシステムは、統合ネットワークプロトコルスタックを形成するように構成された、すなわち、より一般的には、クライアントがブロックアクセスプロトコル及びファイルアクセスプロトコルを使用してマルチプロトコルストレージシステムに記憶された情報にアクセスするためのデータパスを提供するマルチプロトコルエンジンを形成するように構成された、一連のソフトウェアモジュール、及び／又はエンジンを含む。このプロトコルスタックは、ＩＰモジュール２１２、及びその支援搬送機構であるＴＣＰモジュール２１４、ユーザデータグラムプロトコル（ＵＤＰ）モジュール２１６のようなネットワークプロトコルモジュールとのインタフェースとなる種々のネットワークドライバ（例えば、ギガビットイーサネットドライバ）のメディアアクセスモジュール２１０を含む。ファイルシステムプロトコルモジュールは、マルチプロトコルファイルアクセスを可能にし、その目的のために、ＤＡＦＳプロトコル２１８、ＮＦＳプロトコル２２０、ＣＩＦＳプロトコル２２２、及びＨＴＴＰ（HyperText Transfer Protocol）プロトコル２２４をサポートする。ＶＩモジュール２２６は、ＶＩアーキテクチャを実施し、ＤＡＦＳプロトコル２１８により必要とされる、ＲＤＭＡのようなダイレクト・アクセス・トランスポート（ＤＡＴ）機能を提供する。
【００３３】
ｉＳＣＳＩドライバモジュール２２８は、ＴＣＰ／ＩＰネットワークプロトコル層を介したブロックプロトコルアクセスを可能にする一方、ＦＣドライバモジュール２３０は、ネットワークアダプタと協働し、ストレージシステムとの間で、ブロックアクセス要求及び応答を送受信する。ＦＣドライバ及びｉＳＣＳＩドライバは、ＬＵＮ（ｖｄｉｓｋ）に対するＦＣ固有の及びｉＳＣＳＩ固有のアクセス制御を可能にし、従って、マルチプロトコルストレージシステム上の単一のｖｄｉｓｋにアクセスするときに、ｉＳＣＳＩとＦＣＰのいずれか一方、あるいは、ｉＳＣＳＩとＦＣＰの両方へのｖｄｉｓｋのエキスポートを管理する。さらに、ストレージオペレーティングシステムは、ＲＡＩＤプロトコルのようなディスクストレージプロトコルを実施するＲＡＩＤシステムのようなディスクストレージモジュール２４０と、例えばＳＣＳＩプロトコルのようなディスクアクセスプロトコルを実施するディスクドライバモジュール２５０とを含む。
【００３４】
本発明の例示的実施形態において、ディスクストレージモジュール（例えば、ＲＡＩＤシステム２４０）は、新規なｎＰ技術を実施する。例えば、ＲＡＩＤシステム２４０は、書き込み処理中に後述するエンコーディング技術に従ってデータをエンコードし、さらに、記憶装置の１以上の故障の検出に応答し、後述するようにデータを再構築する。なお、代替実施形態において、新規なｎＰ技術は、ＲＡＩＤシステム２４０以外のストレージオペレーティングシステムのモジュールにより実施される場合がある。従って、新規なｎＰ技術を実施するＲＡＩＤシステム２４０の説明は、単なる例として解釈しなければならない。
【００３５】
種々のディスクソフトウェアモジュールを統合ネットワークプロトコルスタック層に橋渡しするのは、例えばｖｄｉｓｋモジュール２７０及びＳＣＳＩターゲットモジュール２６０として実施される仮想化モジュールと交信するファイルシステム２６５によって実施される仮想化システム２５５である。なお、ｖｄｉｓｋモジュール２７０、ファイルシステム２６５、及びＳＣＳＩターゲットモジュール２６０は、ソフトウェアで実施しても、ハードウェアで実施しても、ファームウェアで実施してもよく、あるいはそれらの組み合わせで実施してもよい。ｖｄｉｓｋモジュール２７０は、ファイルシステム２６５と交信し、システム管理者がマルチプロトコルストレージシステム１２０に対し発行したコマンドに応答して、管理者インタフェースによるアクセスを可能にする。基本的には、ｖｄｉｓｋモジュール２７０は、とりわけ、システム管理者によってユーザインタフェースを通じて発行された複雑な一組のｖｄｉｓｋ（ＬＵＮ）コマンドを実施することにより、ＳＡＮデプロイメントを管理する。これらのｖｄｉｓｋコマンドは、ファイルシステム２６５及びＳＣＳＩターゲットモジュール２６０に作用する原始的なファイルシステムオペレーション（「プリミティブ」）に変換され、ｖｄｉｓｋを実施する。
【００３６】
その後、ＳＣＳＩターゲットモジュール２６０は、ＬＵＮを特殊なｖｄｉｓｋファイルタイプに変換するマッピング手順を提供することにより、ディスク又はＬＵＮのエミュレーションを開始する。ＳＣＳＩターゲットモジュールは、例えば、ＦＣ及びｉＳＣＳＩドライバ２３０、２２８と、ファイルシステム２６５との間に配置され、それによってＳＡＮブロック（ＬＵＮ）空間とファイルシステム空間との間に仮想化システム２５５の変換層を提供し、ここで、ＬＵＮはｖｄｉｓｋとして表現される。ＳＡＮ仮想化をファイルシステム２６５の上に「配置」することによって、マルチプロトコルストレージシステムは、従来のシステムにより行われるアプローチを逆転させ、それによって、事実上全てのストレージアクセスプロトコルのための単一の統合されたストレージプラットフォームを提供する。
【００３７】
ファイルシステム２６５は、例えば、メッセージベースのシステムである。従って、ＳＣＳＩターゲットモジュール２６０は、ＳＣＳＩ要求を、ファイルシステムへのオペレーションを表すメッセージに置き換える。例えば、ＳＣＳＩターゲットモジュールにより生成されるメッセージは、オペレーションのタイプ（例えば、読み出し、書き込み）と共に、ファイルシステムにおいて表現されるｖｄｉｓｋオブジェクトのパス名（例えば、パス記述子）及びファイル名（例えば、特殊なファイル名）を含む場合がある。ＳＣＳＩターゲットモジュール２６０は、かかるメッセージを例えばファンクションコールのようなファイルシステム２６５に渡し、そこで、オペレーションは実施される。
【００３８】
例えば、ファイルシステム２６５は、例えば４キロバイト（ＫＢ）ブロックを使用し、ｉｎｏｄｅを使用してファイルを表現するブロックベースのオンディスク・フォーマット表現を有するＷＡＦＬファイルシステムを実施する場合がある。ＷＡＦＬファイルシステムは、自身のファイルシステムのレイアウトを表すメタデータを、ファイルを使用して記憶する。そのようなメタデータファイルとしては、とりわけ、ｉｎｏｄｅファイルが挙げられる。ファイルハンドル、すなわち、ｉｎｏｄｅ番号を含む識別子が、ディスクからのｉｎｏｄｅの読み出しに使用される。
【００３９】
動作的には、クライアント１１０からの要求は、コンピュータネットワーク１０５を介してパケットとしてストレージシステム１２０へ転送され、そこでそのパケットは、ネットワークアダプタ１２５によって受信される。ネットワークドライバは、そのパケットを処理し、そのパケットをｗｒｉｔｅ−ａｎｙｗｈｅｒｅファイルシステム２６５へ転送する前に、更なる処理を施すために、必要に応じてネットワークプロトコル・ファイルアクセスモジュールに渡す場合がある。ここで、ファイルシステムは、要求されたデータが「コア内」に、すなわちメモリ１２４内に存在しない場合、そのデータをディスク１５０から（読み出す）ロードするためのオペレーションを生成する。情報がメモリ上に無い場合、ファイルシステム２６５は、ｉｎｏｄｅ番号を使用してｉｎｏｄｅファイルの中を検索し、適当なエントリにアクセスし、論理ボリュームブロック番号（ｖｂｎ）を読み出す。次に、ファイルシステムは、その論理ｖｂｎを含むメッセージ構造をＲＡＩＤシステム２４０に渡す。論理ｖｂｎは、ディスク識別子及びディスクブロック番号（ディスク，ｄｂｎ）にマッピングされ、ディスクドライバシステム２５０の適当なドライバ（例えば、ＳＣＳＩ）へ送信される。ディスクドライバは、指定されたディスク１５０からそのｄｂｎにアクセスし、要求されたデータブロック（複数可）をストレージシステムによる処理のためにメモリにロードする。要求が完了すると、ストレージシステム（及びオペレーティングシステム）は、ネットワーク１０５を介してクライアント１１０へ応答を返す。
【００４０】
なお、ストレージシステムにおいて受信されたクライアント要求のためのデータストレージアクセスを実施するために必要な上記のストレージオペレーティングシステム層を通るソフトウェア「パス」は、代替的に、ハードウェアで実施してもよい。すなわち、本発明の代替実施形態では、ストレージアクセス要求データパスは、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）又は特定用途向け集積回路（ＡＳＩＣ）の中に実現される論理回路として実施される場合がある。この種のハードウェア実施形態によれば、クライアント１１０が発行した要求に応答してストレージシステム１２０により提供されるストレージサービスの性能が向上する。さらに、本発明の他の代替実施形態では、アダプタ１２５、１２８の処理要素は、パケット処理オペレーション、及びストレージアクセスオペレーションの負荷の全部又は一部をプロセッサ１２２からそれぞれ取り除くように構成される場合があり、それによってシステムにより提供されるストレージサービスの性能は向上する。当然ながら、本明細書に記載する種々のプロセス、アーキテクチャ、及び手順は、ハードウェアで実施しても、ファームウェアで実施しても、ソフトウェアで実施してもよい。
【００４１】
本明細書において「ストレージオペレーティングシステム」とは一般に、ストレージシステムにおいてストレージ機能を実施するために動作可能なコンピュータ実行可能コードを言い、かかるコードは、例えばデータアクセスを管理し、ファイルシステムセマンティクスを実施する場合がある。その意味で、ＯＮＴＡＰソフトウェアは、マイクロカーネルとして実施され、かつ、ＷＡＦＬファイルシステムセマンティクスを実施し、データアクセスを管理するためのＷＡＦＬ層を含む、そのようなストレージオペレーティングシステムの一例である。ストレージオペレーティングシステムは、ＵＮＩＸ又はＷｉｎｄｏｗｓ  ＸＰのような汎用オペレーティングシステム、あるいは、本明細書に記載するようなストレージアプリケーションのために構成された設定可能な機能を有する汎用オペレーティングシステムの上で動作するアプリケーションプログラムとして実施されることもある。
【００４２】
さらに、当業者には理解されるように、本明細書に記載する本発明の技術は、如何なるタイプの特殊な目的の（例えばファイルサーバ又はストレージシステムのような）コンピュータにも、汎用コンピュータにも適用することができ、例えば、ストレージシステム１２０として実施され、又はストレージシステム１２０を含むスタンドアロンのコンピュータ、又はその一部に適用される場合がある。また、本発明の教示は、種々のストレージシステムアーキテクチャに適合させることができ、限定はしないが、例えば、ネットワーク・アタッチド・ストレージ環境、ストレージ・エリア・ネットワーク、及びクライアントまたはホストコンピュータに直接取り付けられたディスクアセンブリに適合させることができる。従って、「ストレージシステム」という用語は、ストレージ機能を実施するように構成され、他の装置又はシステムに関連する任意のサブシステムに加えて、そのような構成をも含むものとして、広い意味で解釈しなければならない。
【００４３】
C．パリティエンコーディング
本発明は、ｎウェイディスク故障からの保護を提供するようにエンコードされたストレージアレイのパリティグループ内の最大ｎ個までのディスク（又は他の記憶装置）の復旧を可能にするｎウェイパリティ保護技術を提供する。このアレイは、アレイの記憶装置が故障したときに、連立一次方程式を解く任意の技術を使用して、アレイの中身を再構築することができるように構成される。このストレージアレイはまず、ｍ個のデータディスクを有するアレイを構成することによって作成される。ここで、ｍ＝ｐ−１であり、ｐは素数である。行パリティは、例えばＲＡＩＤ 4に類似した形で専用の１個の行パリティディスクに記憶される場合があり、又は、例えばＲＡＩＤ５に類似した形で複数のデータディスクにわたって記憶され、それらのデータディスクにわたって循環される場合がある。
【００４４】
次に、ｎ−１個の対角パリティディスクがアレイに追加され、全部でｎビットのパリティ、すなわち、１つの行パリティビット、及びｎ−１個の対角パリティビットが形成される。各対角パリティセット（すなわち、対角）は、その対角に含まれるアレイのデータブロック及び行パリティブロックを定義する傾斜に関連する。パリティグループ内の同じ傾斜を有する対角は全て、１つの対角パリティクラスとして編成される。各対角パリティクラスについて、対角パリティを記憶するために、１つの対角パリティストレージディスクが設けられる。対角パリティクラスの最大数がｐ−１に制限されている場合、所望のレベルの保護を達成するために、追加される対角パリティディスクの数は、システム管理者により設定される場合がある。換言すれば、本明細書に記載する例示的実施形態によれば、対角パリティクラスの数ｎ−１は、ｐ−１を超えることはできないので、ｎ≦ｐである。各対角パリティディスクは、アレイに追加された後、複数のブロックに分割され、データディスクのブロック、及び必要に応じて対角パリティディスクのブロックは、ストライプに編成される。その後、行パリティセット（すなわち、行）のデータブロックのＸＯＲを計算することによって行パリティが計算され、計算されたパリティは、その後、行パリティディスク、又は適当なデータディスク上の行パリティブロックに記憶される。
【００４５】
その後、データブロック及び行パリティブロックは全て、ｎ−１個の対角パリティクラスの対角に割り当てられる。対角パリティクラスの１つが選択され、そのクラスの各対角、すなわち、共通の（同じ）傾斜を有する対角について、対角パリティが計算される。その後、計算された対角パリティは、適当な対角パリティディスクに記憶される。他にも対角パリティクラスがある場合、このプロセスは、他のクラスのそれぞれについて繰り返される。
【００４６】
図３は、本発明の例示的実施形態による、ｎウェイパリティ技術を実施する手順３００のステップを示すフロー図である。手順３００は、ステップ３０５から開始され、ステップ３１０へ進み、そこで、アレイはまず、数ｍに等しいディスクのような記憶装置を有するように構成される。ここで、ｍ＝ｐ−１であり、ｐは素数である。ｍ個のディスクは、アレイ内のデータディスクを表す。アレイは、例えば管理者によって手作業で構成される場合もあれば、ストレージシステム１２０上で実行されるストレージオペレーティングシステムのディスクストレージモジュール２４０のようなソフトウェアエージェントによって自動的に構成される場合もある。ステップ３１５において、アレイ全体が最大ｍ＋ｎ個までのディスクから構成されるものとなるように、さらにパリティディスクが追加される。例えば、これらのディスクは、手作業で追加される場合もあれば、例えば、ディスクストレージモジュール２４０のようなソフトウェアエージェントによって追加される場合もある。この時点で、アレイは、ｐ−１個のデータディスク、すなわち、１個の行パリティディスク、及び最大ｎ−１個までの対角パリティディスクを含む。例えば、各対角パリティクラスについて、その対角パリティクラスについての対角パリティを記憶するために、対角パリティディスクが設けられる。ただし、後で詳しく説明するように、アレイを構成するときに最大限度数の対角パリティクラスを使用することは、必要とされない。本発明の教示によれば、アレイは、ｎ個の装置の故障の検出を可能とするように構成され、同時に、それらの故障した装置に格納されたデータの訂正（すなわち、再構築）を可能とするように構成される場合がある。本発明の例示的実施形態によれば、対角パリティクラスの数は、ｐ−１を超えることができないため、ｎ≦ｐである。
【００４７】
ステップ３２０において、ディスクは、例えばディスクストレージモジュール２４０によって、複数のブロックに分割され、ステップ３２５において、それらのブロックはストライプに編成される。その後、ステップ３３０において、ディスクストレージモジュール２４０は、ある行の各データブロックを、各データディスク上の同じ位置にある全てのデータブロックのＸＯＲを格納しているその行の行パリティブロックの中に排他的論理和演算（ＸＯＲ）する。これは例えば、従来のＲＡＩＤ４行パリティエンコーディングと同様の形で実施される場合がある。なお、代替実施形態では、行パリティの位置は、ＲＡＩＤ５構成のように移動される場合がある。従って、ＲＡＩＤ４エンコーディング技術の説明は、単なる例として解釈すべきである。
【００４８】
その後、ステップ３３５において、データブロックと行パリティブロックの全てが、例えばディスクストレージモジュール２４０によって、対角パリティクラスの対角に割り当てられる。上記のとおり、各対角パリティクラスについて、そのクラス内の対角の対応する対角パリティを記憶するために、独立した対角パリティ記憶装置が設けられる。なお、本発明の例示的実施形態では、種々の傾斜を有する３以上の対角パリティクラスが存在する場合がある。しかしながら、代替実施形態では、任意の正の整数（最大でｎ−１）個の対角パリティクラスが、使用される場合がある。上で援用された米国特許出願第１１／３０４，３６９号では、アレイは、例えば傾斜＋１の対角のように各対角が特定の傾斜値を有し、例えば傾斜−１の反対角のように反対角が対角とは逆の傾斜を有するように構成される場合がある。例えば、本発明は、任意の整数値の傾斜を有するようなアレイの構成を可能とし、反対角が対角とは逆の傾斜を有する必要性を無くすことによって、上で援用された米国特許出願の技術を改良するものである。上記のように、上で援用された米国特許出願は、例えば傾斜＋１の対角のように各対角が特定の傾斜値を有し、例えば傾斜−１の反対角のように反対角が対角とは逆の傾斜を有するようにアレイを構成する技術を記載している。従って、本発明によれば、例えば、管理者は、例えば対角パリティクラスの対角が傾斜＋１及び＋２を有するような三重（すなわち、ｎ＝３）パリティアレイを構成することが可能となる。
【００４９】
例えば、データブロック及び行パリティブロックのアレイの各要素は、Ａ［ｉ，ｊ］によって、それらに割当てられた位置に索引付けされる場合がある。ここで、ｉは行索引を表し、ｊは列索引を表し、Ａ［］はアレイを表す。例えば、これらの索引値の各々は、０からｐ−１の範囲とされる場合がある。
【００５０】
２次元アレイのこの表現を使用すると、傾斜ｓを有する対角の数ｘは、Ａ［（ｘ＋ｓ＊ｊ）ｍｏｄ  ｐ，ｊ］のように表すことができる。ただし、ｊ＝｛０．．．ｐ−１｝である。
【００５１】
傾斜項は、従来の幾何学的な意味で理解することができる。すなわち、上下に移動した場所の数を左右に移動した場所の数で割った比率である。例えば、傾斜＋２は、次の場所が２つの場所だけ下がり、かつ１の場所だけ右へ移動する対角を表し、傾斜−４は、次の場所が４つの場所だけ上がり、かつ１つの場所だけ右へ移動する傾斜を表す等である。例えば、ｎウェイパリティは、ディスクストレージモジュール２４０によって実施される場合がある。しかしながら、ｎウェイパリティは、他のモジュールにおいて実施されてもよいし、複数のモジュール間に分散されてもよい。
【００５２】
図４は、本発明の例示的実施形態による、例示的ストライピング構成を示す略ブロック図である。この構成は、ｐ＝７、及びｓ＝＋２の例示的なアレイに関するものである。なお、対角パリティディスクは他の対角に含まれないため、データディスク及び行パリティディスクのみが示されている。この構成に示されている番号はそれぞれ、所与の対角に割当てられた１以上のブロックを表す。従って、図４の中の０を有するブロックはそれぞれ、傾斜＋２を有する対角０上に存在する１以上のブロックを表す等である。対角には、０からｐ−１まで番号が付され、この例では、０から６までの番号が対角に付されている。図４に示されている対角はそれぞれ、同じ傾斜（すなわち、＋２）を有し、従って、単一の対角パリティ記憶装置に記憶された対角パリティを有する同じ対角パリティクラスの一部である。図４から分かるように、アレイのデータブロック及び行パリティブロックが全て、少なくとも１つの対角によってカバーされるようにするために、対角はアレイの端部において循環される。最後の行（行ｐ−１）は、所定の値、例えば０を有するものと仮定される。これは、図４において、最後の行が破線であることによって示されている。ある行に所定値を与えることにより、対角はデータブロック及び行パリティブロックの全体にわたって広がる（すなわち、カバーする）ことができ、さらに、各対角において１つの既知の値が存在することを確保することができる。その結果、解くべき連立方程式から潜在的変数が取り除かれるため、これは再構築に役立つ。図４の例示的ストライピング構成は、Ａ［（ｘ＋２＊ｊ）ｍｏｄ  ７，ｊ］によって表される場合がある。ただし、ｊは、０からｐ−１を範囲とする。
【００５３】
図５は、本発明の例示的実施形態による、例示的ストライピング構成を示す略ブロック図である。この構成は、ｐ＝７、及びｓ＝−３の例示的なアレイからなる。図４と同様に、対角パリティディスクは他の対角に含まれないため、データディスク及び行パリティディスクのみが示されている。図５の例示的ストライピング構成は、Ａ［（ｘ−３＊ｊ）ｍｏｄ  ７，ｊ］によって表される場合がある。図４及び図５の例示的ストライピング構成は、ｎ−３アレイとともに使用される場合がある。そのような例示的アレイでは、３つのパリティビットは、（ａ）行パリティ、（ｂ）図４に示されるような傾斜＋２を有する対角パリティクラス内の対角の対角パリティ、及び（ｃ）図５に示されるような傾斜−３を有する対角パリティクラス内の対角の対角パリティによって与えられる場合がある。理解されるように、そのような構成は、パリティ保護を増加させるために、（対応する追加の対角パリティ／ビットを有する）追加の対角パリティクラスを有する場合がある。しかしながら、本発明の例示的実施形態は、最大限度数の対角パリティクラスが使用されることを必要としない。本発明のさらに別の顕著な利点は、全パリティを再計算する必要なしに、追加の対角パリティクラスをアレイに追加することができることである。すなわち、アレイがまだ、最大限度数の対角パリティクラスを有するように構成されていないと仮定した場合、新たな対角パリティクラスについてのパリティを記憶するための対角パリティ記憶装置を追加することによって、新たな対角パリティ記憶装置がアレイに追加される場合がある。そのような場合、計算しなければならないパリティは、新たに追加された記憶装置に記憶すべき対角パリティのみである。その結果、管理者は、アレイが既にサービス提供状態になった後、時間を要するリソース集約的なアレイ内の全パリティの再計算を必要とすることなく、アレイの保護のレベルを増加させる機能が得られる。なお、データディスクの数は、ｐを素数として、ｍ＝ｐ−１の条件を満たさなければならないが、もっと少ない数のディスクを有するアレイを構築することも可能である。追加されるディスク、すなわち、ディスクの実際の番号とｍとの間にあるディスクは、ｍ＝ｐ−１の条件を満たすように、仮想的にゼロで満たされたディスクであってもよい。仮想的にゼロで満たされたディスクは、パリティ計算には影響を与えない。さらに、対角パリティクラスの傾斜は、それらをアレイの構築に使用される素数ｐとモジューロ演算した結果が互いに異なるものとなるような形で選択されなければならない。例えば、素数ｐ＝７の場合、傾斜１、２及び−３は、この条件を満たす。しかし、傾斜４、及び−３は、−３ｍｏｄ７＝（７−３）ｍｏｄ７＝４ｍｏｄ７であるから、この条件を満たさない。
【００５４】
図３を再度参照すると、データブロック及び行パリティブロックの全てが対角に割当てられた後、ステップ３４０において、対角パリティクラスの１つが、例えばディスクストレージモジュール２４０によって選択される。選択された対角パリティクラス内の対角に沿った対角パリティは、例えば、その対角パリティクラス内のそれらの対角に沿って全てのブロックの排他的論理和（ＸＯＲ）演算を実施することにより計算される。その後、ステップ３５０において、計算された対角パリティブロックは、選択された対角パリティクラスに関連する対角パリティディスクに記憶される。この記憶は、例えば、ディスクドライバ２５０と協働するディスクストレージモジュール２４０によって実施され、計算されたパリティをディスク１５０に記憶させる場合がある。ステップ３５５において、他の対角パリティクラスについて対角パリティを計算する必要があるか否かの判断を行う。もし、他の対角パリティクラスについて対角パリティを計算する必要がある場合、手順３００は、ステップ３４０へループバックし、他の対角パリティクラスを選択する。その後、手順３００は、ステップ３６０で完了する。手順３００の結果として、アレイは、アレイ内のｎ個の記憶装置（例えばディスク）の故障からの復旧が可能となるように構成される。その後アレイは、（例えば、エラー条件に応答して）連立一次方程式を解くための任意の技術を使用して再構築されることができる。
【００５５】
図６は、本発明の例示的実施形態による、１以上の故障した記憶装置が発生したときに再構築を実施するための例示的手順６００の種々のステップを示すフロー図である。手順６００は、ステップ６０５から開始され、ステップ６１０へ進み、そこで、例えばディスクストレージモジュール２４０によってエラー条件が検出される。エラー条件は、例えば、１以上の記憶装置の故障を含む場合がある。故障は、例えば、メディアに対する物理的損傷、接続性の喪失などに起因して発生する場合がある。エラーは、例えば、装置に対する入出力（Ｉ／Ｏ）故障、接続性の喪失の検出などの従来のエラー検出技術により検出される場合がある。その後、ステップ６１５において、ディスクストレージモジュール２４０は、故障の数がｎ以下であるか否かを判断する。もし故障の数がｎ以下である場合、故障は、本明細書に記載するｎＰ技術を使用して訂正することができる。その場合、手順は、ステップ６２０へ進み、そこで、失われたデータが再構築される。上記のように、ｎＰアレイの再構築の実施には、連立一次方程式を解くための任意の技術を使用することができる。連立一次方程式を解くための例示的技術としては、例えば、ガウス消去法、クラメールの公式、コレスキー分解、ＬＵ分解などが挙げられる。他の例示的技術は、ジェイムス・リー・ハフナー他による「Matrix Methods for Lost Data Reconstruction in Erasure Codes」、ＵＳＥＮＩＸ  ＦＡＳＴ（Conference on File and Storage Technologies）、第４回、２００５年に記載されており、この文献の内容は、参照により本明細書に援用される。データが再構築された後、次に手順６００は、ステップ６２５において完了する。
【００５６】
もしステップ６１５において、故障の数がｎよりも大きいと判断された場合、手順６００は、ステップ６３０へ分岐し、そこで、エラー条件は、復旧可能ではないものとみなされ、その後、手順は、ステップ６２５で完了する。
【００５７】
上記の説明は、本発明の特定の実施形態に関するものである。しかし、当然ながら、それらの利点の一部又は全部を維持しながら、記載した実施形態に対し、他の変形及び修正を施すことも可能である。例えば、説明は、ディスクを例として記載されているが、限定はしないが、例えば、フラッシュデバイス、及び他の個体媒体も、代替実施形態に従って使用される場合がある。従って、添付の特許請求の範囲の目的は、そうした変形や修正も、本発明の真の思想および範囲に含めることにある。
【図１】
0005518201.tif 000002
【図２】
0005518201.tif 000003
【図３】
0005518201.tif 000004
【図４】
0005518201.tif 000005
【図５】
0005518201.tif 000006
【図６】
0005518201.tif 000007