(57)【特許請求の範囲】
【請求項１】
ストレージアレイにおける記憶装置の２以下の同時故障からの復旧を可能にするために、コンピュータで実施される方法であって、
前記ストレージアレイが、データを記憶するように構成されたｎ−２個のデータ記憶装置と、行パリティを記憶するように構成された１つの行パリティ記憶装置と、対角パリティを記憶するように構成された１つの対角パリティ記憶装置とを含む所定数ｎの記憶装置からなり、前記記憶装置の所定数ｎが、ｐを素数として、ｐ＋１であるものにおいて、
各記憶装置を複数のブロックに分割するステップと、
各ストライプが、各記憶装置におけるｎ−２個のブロックを含み、かつｎ−２行のブロックを含むものとなるように、前記複数のブロックを１以上のストライプに編成するステップと、
前記データ記憶装置、及び前記行パリティ記憶装置にわたる対角パリティ集合に沿って対角パリティを定義するステップであって、前記対角パリティ集合が、前記ストライプ中の前記データ記憶装置、及び前記行パリティ記憶装置におけるｎ−２行のブロックのグループ内で循環し、それによって前記ストライプ中の前記データ記憶装置、及び前記行パリティ記憶装置におけるすべてのブロックが、前記対角パリティ集合に属するものとなる、対角パリティを定義するステップと、
１つを除くすべての前記対角パリティ集合について対角パリティを計算し、前記対角パリティ記憶装置に記憶するステップと、
からなる方法。
【請求項２】
前記データ記憶装置がすべて存在するのではなく、不在のデータ記憶装置はゼロ値のデータを有するものとして扱われる、請求項１に記載の方法。
【請求項３】
前記行パリティのそれぞれの計算が、単一装置故障を許容するストライプ中の前記データ記憶装置におけるブロックの各行におけるデータブロックの冗長符号化によって実施される、請求項１又は請求項２に記載の方法。
【請求項４】
２つの記憶装置の２以下の同時故障からの復旧を可能にするように構成されたシステムであって、
データを記憶するように構成されたｎ−２個のデータ記憶装置と、行パリティを記憶するように構成された１つの行パリティ記憶装置と、対角パリティを記憶するように構成された１つの対角パリティ記憶装置とを含む所定数ｎの記憶装置を有するアレイであって、前記記憶装置の所定数ｎが、ｐを素数として、ｐ＋１である、所定数ｎの記憶装置を有するアレイと、
各記憶装置を複数のブロックに分割し、各ストライプが、各記憶装置におけるｎ−２個のブロックを含み、かつｎ−２行のブロックを含むものとなるように、前記複数のブロックを１以上のストライプに編成し、前記データ記憶装置、及び前記行パリティ記憶装置にわたる対角パリティ集合に沿って対角パリティを定義し、前記対角パリティ集合が、前記ストライプ中の前記データ記憶装置、及び前記行パリティ記憶装置におけるｎ−２行のブロックのグループ内で循環し、それによって前記ストライプ中の前記データ記憶装置、及び前記行パリティ記憶装置におけるすべてのブロックが、前記対角パリティ集合に属するものとなり、さらに、１つを除くすべての前記対角パリティ集合について対角パリティを計算し、前記対角パリティ記憶装置に記憶する行−対角（Ｒ−Ｄ）パリティ技術を実施するように構成されたデバイスストレージ層を含むストレージオペレーティングシステムと、
前記ストレージオペレーティングシステムを実行することにより前記アレイに対するストレージアクセス処理を前記Ｒ−Ｄパリティ技術に従って実施するように構成された処理要素と、
からなるシステム。
【請求項５】
前記データ記憶装置がすべて存在するのではなく、不在のデータ記憶装置はゼロ値のデータを有するものとして扱われる、請求項４に記載のシステム。
【請求項６】
前記行パリティのそれぞれの計算が、単一装置故障を許容するストライプ中の前記データ記憶装置におけるブロックの各行におけるデータブロックの冗長符号化によって実施される、請求項４又は請求項５に記載のシステム。
【請求項７】
ストレージアレイにおける２つの記憶装置の２以下の同時故障からの復旧を可能にする装置であって、
データを記憶するように構成されたｎ−２個のデータ記憶装置と、行パリティを記憶するように構成された１つの行パリティ記憶装置と、対角パリティを記憶するように構成された１つの対角パリティ記憶装置とを含む所定数ｎの記憶装置を有するアレイであって、前記記憶装置の所定数ｎが、ｐを素数として、ｐ＋１である、所定数ｎの記憶装置を有するアレイを提供する手段と、
各記憶装置を複数のブロックに分割する手段と、
各ストライプが、各記憶装置におけるｎ−２個のブロックを含み、かつｎ−２行のブロックを含むものとなるように、前記複数のブロックを１以上のストライプに編成する手段と、
前記データ記憶装置、及び前記行パリティ記憶装置にわたる対角パリティ集合に沿って対角パリティを定義する手段であって、前記対角パリティ集合が、前記ストライプ中の前記データ記憶装置、及び前記行パリティ記憶装置におけるｎ−２行のブロックのグループ内で循環し、それによって前記ストライプ中の前記データ記憶装置、及び前記行パリティ記憶装置におけるすべてのブロックが、前記対角パリティ集合に属するものとなる、対角パリティを定義する手段と、
１つを除くすべての前記対角パリティ集合について対角パリティを計算し、前記対角パリティ記憶装置に記憶する手段と
からなる装置。
【請求項８】
前記データ記憶装置がすべて存在するのではなく、不在のデータ記憶装置はゼロ値のデータを有するものとして扱われる、請求項７に記載の装置。
【請求項９】
前記行パリティのそれぞれの計算が、単一装置故障を許容するストライプ中の前記データ記憶装置におけるブロックの各行におけるデータブロックの冗長符号化によって実施される、請求項７又は請求項８に記載の装置。
【請求項１０】
記憶装置の２以下の同時故障からの復旧を可能にするように構成されたストレージアレイであって、
データを保持するように構成されたｎ−２個のデータ記憶装置と、行パリティを記憶するように構成された１つの行パリティ記憶装置と、対角パリティを記憶するように構成された１つの対角パリティ記憶装置とを含む所定数ｎの記憶装置を有するアレイであって、ｐを素数として前記所定数ｎ＝ｐ＋１である、所定数ｎの記憶装置を有するアレイを提供する手段と、
各記憶装置を複数のブロックに分割する手段と、
各ストライプが、各記憶装置におけるｎ−２個のブロックを含み、かつｎ−２行のブロックを含むものとなるように、前記複数のブロックを１以上のストライプに編成する手段と、
前記データ記憶装置、及び前記行パリティ記憶装置にわたる対角パリティ集合に沿って対角パリティを定義する手段であって、前記対角パリティ集合が、前記ストライプ中の前記データ記憶装置、及び前記行パリティ記憶装置におけるｎ−２行のブロックのグループ内で循環し、それによって前記ストライプ中の前記データ記憶装置、及び前記行パリティ記憶装置におけるすべてのブロックが、前記対角パリティ集合に属するものとなる、対角パリティを定義する手段と、
１つを除くすべての前記対角パリティ集合いついて対角パリティを計算し、前記対角パリティ記憶装置に記憶する手段と
からなるストレージアレイ。
【請求項１１】
前記データ記憶装置がすべて存在するのではなく、不在のデータ記憶装置はゼロ値のデータを有するものとして扱われるように、前記ｎ−２個のデータ記憶装置を構成する手段をさらに含む、請求項１０に記載のストレージアレイ。
【請求項１２】
単一装置故障を許容するストライプ中の前記データ記憶措置におけるブロックの各行におけるデータブロックの冗長符号化によって、前記行パリティのそれぞれを計算する手段をさらに含む、請求項１０又は請求項１１に記載のストレージアレイ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はストレージシステムのアレイに関し、詳しくは、スレージアレイ中の任意の１台の故障した記憶装置、または、任意の２台の故障した記憶装置の組み合わせを効率よく復元するための技術に関するものである。
【０００２】
【従来の技術】
ストレージシステムは通常１以上の記憶装置を含み、要求に応じてそれらの記憶装置にデータを入力したりそれらの記憶装置からデータを取得したりすることができる。ストレージシステムは、限定はしないが、ネットワークに取り付けられたストレージ環境、ストレージエリアネットワーク、及び、クライアントまたはホストコンピュータに直接取り付けられたディスクアセンブリを含む、様々なストレージアーキテクチャに従って実施される。記憶装置は典型的にはディスクドライブであり、ここで「ディスク」という用語は一般に独立型の回転式磁気媒体記憶装置を意味している。この文脈での用語「ディスク」は、ハードディスクドライブ（ＨＤＤ）やダイレクトアクセス記憶装置（ＤＡＳＤ）と同義である。
【０００３】
ストレージシステム内のディスクは通常、１以上のグループに編成され、各グループがＲＡＩＤ（Redundant Array of Independent(or Inexpensive) Disks）として運用されている。大半のＲＡＩＤ実施形態は、ＲＡＩＤグループ内の所定数の物理ディスクに「ストライプ状」にまたがるデータの冗長書き込み、及び、そのストライプ状になったデータに関する冗長情報の適切な記憶により、データ記憶の信頼性／完全性を向上させている。この冗長情報によって、記憶装置が故障したときのデータロストの復旧が可能になる。
【０００４】
ディスクアレイを運用する場合、ディスクが故障し得ることを考慮している。高性能ストレージシステムの目標は、ＭＴＴＤＬ（Mean time to data loss）を可能な限り長くすることであり、システムの推定サービス寿命よりも長くすることが好ましい。１以上のディスクが故障した場合、データがロストする可能性があり、その装置からデータを復旧させることは不可能になる。データの損失を回避する一般的な手段としては、ミラーリング、バックアップ、パリティ保護が挙げられる。ミラーリングは、ディスク等のストレージリソースの消費という観点からは、高価な解決方法である。バックアップは、バックアップが作成された後に変更されたデータを保護することができない。パリティ手段は、わずか１台のディスクドライブをシステムに追加するだけでデータの冗長符号化を提供し、単一削除（１台のディスクの損失）を許容するので、一般的である。
【０００５】
パリティ保護は、ディスク等の記憶装置上のデータの損失を防止するためにコンピュータシステムで用いられる。パリティ値は、異なるデータを有する多数の同様のディスクにわたって、あるワードサイズ（通常１ビット）のデータを足し合わせる（通常モジュロ２で）ことにより計算される。すなわち、パリティは、各々のディスク上の対応する位置にあるビットから構成される１ビット幅のベクトルに対して計算される。１ビット幅のベクトルに対して計算される場合、パリティは、合計として計算される場合と、その補数として計算される場合とがあり、これらはそれぞれ偶数パリティ、奇数パリティと呼ばれる。１ビットベクトルに対する加算および減算は、いずれも排他的論理和（ＸＯＲ）演算と同じである。そして、データは、ディスクのうちのいずれか１つの損失、またはディスクのうちのいずれか１つの任意の部分のデータの損失から保護される。パリティを記憶しているディスクが失われた場合、パリティはデータから再生成することができる。データディスクのうちの１つが失われた場合、そのデータは、残ったディスクの内容を加え合わせてその結果を記憶されているパリティから減算することにより再生成することができる。
【０００６】
通常、ディスクはパリティグループに分割され、パリティグループの各々が１以上のデータディスクと１つのパリティディスクとを含んでいる。パリティ集合は複数のデータブロックと１つのパリティブロックとを含むブロックの集合であり、ここでパリティブロックはそれらのデータブロックすべてのＸＯＲをとったものである。パリティグループは、１以上のパリティ集合を選択する元になるディスクの集合である。ディスク空間はストライプに分割され、各ストライプが各ディスクの中から１ブロックを保持している。あるストライプのブロックは通常、パリティグループ内の各ディスク上で同じ位置に存在する。ストライプ内では、１ブロックを除くすべてのブロックがデータを保持するブロック（「データブロック」）であり、１ブロックはそれらのデータ全てのＸＯＲをとることによって計算されたパリティを保持するブロック（「パリティブロック」）である。これらのパリティブロックをすべて１つのディスク上に記憶し、すべてのパリティ情報（かつパリティ情報のみ）を保持する１つのディスクを設けた場合、ＲＡＩＤ−４実施形態になる。それらのパリティブロックを各ストライプの異なるディスク内に保持する場合、たいていは循環パターンが用いられ、実施形態はＲＡＩＤ−５になる。用語「ＲＡＩＤ」及びその実施形態は広く知られており、１９９８年６月、データの管理に対する国際会議（ＳＩＧＭＯＤ）の議事録で、Ｄ．Ａ．Ｐａｔｔｅｒｓｏｎ、Ｇ．Ａ．Ｇｉｂｓｏｎ、およびＲ．Ｈ．Ｋａｔｚによる「A Case for Redundant Arrays of Inexpensive Disks(RAID)」に開示されている。
【０００７】
本明細書で用いられる場合、「符号化」という用語はデータブロックのうちの所定のサブセットにわたる冗長性値の計算を意味しているのに対して、「復号化」という用語は、データブロックのサブセット及び冗長性値を用いた冗長性計算の際のその同じプロセスによるデータブロックまたはパリティブロックの復元を意味している。パリティグループ内で１台のディスクが故障した場合、そのディスクの内容は、残ったデータブロックのすべての内容を加え合わせ、その結果をパリティブロックから減算することにより、予備ディスク上に復号（復元）することができる。１ビットフィールド上での２の補数加算及び減算はいずれもＸＯＲ演算と等しいので、この復元は、すべての生き残ったデータブロック及びパリティブロックのＸＯＲから構成される。同様に、パリティディスクが失われた場合も、パリティディスクは生き残ったデータから同じ方法で再計算することができる。
【０００８】
パリティ手段は、一般にパリティグループ内の１つの故障に対する保護を提供するものである。これらの手段は、故障が異なるパリティグループ内で発生する限りは、複数のディスク故障に対する保護を提供することも可能である。しかしながら、パリティグループ内で２台のディスクが同時に故障した場合、復元不能なデータの損失をこうむる。パリティグループ内で２台のディスクが同時の故障することはかなり一般的に起こりうるものであり、特にその原因は、ディスクの磨耗、及び、ディスクの動作に関する環境要因である。この文脈で、パリティグループ内での２台のディスクの同時の故障は「２重故障」と呼ばれる。
【０００９】
２重故障は、典型的には、１台のディスクの故障と、その最初の故障からの復旧を試みている間に生じた他のディスクの故障の結果として発生する。復旧時間または復元時間は、ストレージシステムのアクティビティのレベルに依存している。すなわち、故障したディスクを復元している間、ストレージシステムは「オンライン」のままであり、データに対するアクセス（読み出し及び／又は書き込み）の要求（クライアントまたはユーザからの）に関するサービスを提供することが可能である。ストレージシステムが要求に対するサービスの提供に忙しい場合、復元の所要時間は増加することになる。失われたデータを復元するためには生き残ったディスクのすべてを読み出す必要があるので、この復元処理時間はストレージシステムのディスクの数やサイズが増加するのに応じても増加する。また、２重故障確率は、パリティグループ内のディスク数の２乗に比例する。しかしながら、パリティグループを小さくすることは、各パリティグループが冗長データを扱うために１ディスク全体を必要とするので、費用がかかることになる。
【００１０】
ディスクの他の故障形態は、ディスク内の１ブロックまたは１セクタが読み出せなくなるというメディア読み込みエラーである。ストレージアレイにパリティが保持されていれば、その読み出し不能なデータを復元することができる。しかしながら、あるディスクがすでに故障しているときに、アレイ内の他のディスクに対して読み出しエラーが起きると、データが失われる。これが２重故障の第２の形態である。
【００１１】
従って、２重故障に対して耐性のある技術を提供することが望まれている。この技術は、より大きなパリティグループを有するより大きなディスクシステムの構成を可能にする一方、一台のディスク故障に長い時間（例えば数時間）を要した後の復元であっても、システムが２重故障に耐えることを保証する。このような技術により、ストレージシステムに対する特定の設計上の制限を緩和することができる。例えば、ストレージシステムはより低コストのディスクを使用し、かつ、それでも高いＭＴＴＤＬを維持することができるようになるであろう。低コストのディスクは高コストのディスクに比べて一般に寿命が短く、寿命までの間に故障する確率も高い。従って、ストレージシステムがパリティグループ内の２重ディスク故障に耐えることができれば、このようなディスクの使用がもっと可能になる。
【００１２】
２重故障を訂正するのに必要な冗長情報の最小量が２ユニットであることは、簡単に示すことが可能である。従って、データディスクに付加することができるパリティディスクの最小数は２台である。このことは、パリティが複数のディスクにわたって分散されているか２台の追加ディスク上に集中されているかに関係なく、事実である。
【００１３】
既知の２重故障訂正パリティ手段は、失われた（故障した）ディスクの順次復元を可能にするＥＶＥＮＯＤＤ  ＸＯＲベースの技術である。ＥＶＥＮＯＤＤパリティには、ちょうど２台のディスク分の冗長データが必要であり、これが最適である。このパリティ技術によると、すべてのディスクブロックは２つのパリティ集合に属しており、一方はすべてのデータディスクにわたって計算される一般的なＲＡＩＤ４スタイルのＸＯＲであり、他方は対角方向に隣り合ったディスクブロックの集合にわたって計算される。対角パリティ集合は、１ブロックを除きすべてのデータディスクからブロックを含む。ｎ台のデータディスクの場合、１ストライプ中にｎ−１行のブロックが存在する。各ブロックが１つの対角上に存在し、長さｎ−１ブロックのｎ個の対角が存在する。注意して欲しいのは、ＥＶＥＮＯＤＤ手段はｎが素数の場合にしか機能しない点である。ＥＶＥＮＯＤＤ技術については、１９９５年ブラウム他による「A variant of EVENODD is Failure in RAID Architecture」と題したIEEE Transactions on Computers Vol.44 No.2の論文に開示されている。１９９６年１１月２６日に発行された「Method and Means for Encoding and Rebuilding the Data Contents of up to Two Unavailable DASDs in a DASD Array using Simple Non-Recursive Diagonal and Row Parity」と題したブラウム他による米国特許第５，５７９，４７５号には、様々なＥＶＥＮＯＤＤが開示されている。上記の論文および特許はここで参照することにより完全に説明したものとして取り込まれる。
【００１４】
ＥＶＥＮＯＤＤ技術は、ｐを素数として全部でｐ＋２台のディスクを使用し、そのうちのｐ台のディスクがデータを保持し、残りの２台のディスクがパリティ情報を保持する。一方のパリティディスクは行パリティブロックを保持する。行パリティは、各データディスクの同じ位置にあるすべてのデータブロックのＸＯＲとして計算される。他方のパリティディスクは対角パリティブロックを保持する。対角パリティは、複数のデータディスク上に対角パターンに配置されたｐ−１個のデータブロックから構成される。これらのブロックは、ｐ−１行のストライプにグループ化される。これは、データブロックの行パリティ集合への割り当てには影響を与えない。しかしながら、対角は、対角内のすべてのブロックが同じブロックのストライプに入るようなパターンに構成される。これは、ほとんどの対角は、ディスクからディスクへと進む際に、ストライプ内で「循環」することを意味している。
【００１５】
具体的には、ｎ×（ｎ−１）のデータブロックのアレイの場合、対角がアレイの端部で「循環する」ならば、長さｎ−１の対角がちょうどｎ個存在する。ＥＶＥＮＯＤＤパリティ配置の復元で重要なのは、各対角パリティ集合がデータディスクのうちの１つから情報を保持していないことである。しかしながら、対角についてパリティブロックを記憶するためのブロックが存在する以外に、もう１つだけ対角が存在する。すなわち、ＥＶＥＮＯＤＤパリティ配置では、独立したパリティブロックを持たない対角パリティ集合になる。この余分な「抜けている」パリティブロックを収容するため、ＥＶＥＮＯＤＤ配置は、ある特別な対角のパリティ結果とその他の対角の各々についてのパリティブロックとのＸＯＲをとる。
【００１６】
図１は、従来のＥＶＥＮＯＤＤパリティ配置に従って構成された従来技術のディスクアレイ１００を示す略ブロック図である。各データブロックＤａｂはパリティ集合ａ及びｂに属しており、各パリティ集合のパリティブロックがＰａで表記されている。ある特別な対角（Ｘ）については、対応するパリティブロックが何も記憶されていないことに注意して欲しい。ここにＥＶＯＮＯＤＤの特徴が現れている。２つの故障からの復元を可能にするためには、各データディスクは少なくとも１つの対角パリティ集合に貢献してはならない。ｎ×（ｎ−１）のデータブロックのアレイを用いた場合、対角パリティ集合はｎ−１個のデータブロック要素を有する。上記のように、このような配置では、すべての対角パターンについてパリティブロックを記憶するための位置を持つのではない。そのため、余分な（抜けている）対角パリティブロックのパリティ（Ｘ）は、その対角パリティを他の対角パリティブロックの各々のパリティとＸＯＲをとることにより記録される。具体的には、この抜けている対角パリティ集合のパリティは対角パリティブロックＰ４〜Ｐ７の各々とＸＯＲをとられ、それらのブロックがＰ４Ｘ〜Ｐ７Ｘで表記されている。
【００１７】
２台のデータディスクの故障から復元するためには、まず、全てのパリティブロックのＸＯＲをとることにより、パリティブロックを持たない対角のパリティを再計算する。例えば、全ての行パリティの合計は全てのデータブロックの合計である。全ての対角パリティの合計は、全てのデータブロックの合計から抜けている対角パリティブロックの合計を引いたものである。従って、すべてのパリティブロックのＸＯＲは、すべてのブロックの合計（行パリティ合計）から抜けている対角を除いた全てのブロックの合計を引いたものに等しく、これがちょうど抜けている対角のパリティになる。実際には、各対角パリティブロックについて１つ、抜けている対角パリティのｎ−１個の複製がその結果に加算される。ｎが２よりも大きい素数であるからｎ−１は偶数であり、あるブロックを自分自身と偶数回ＸＯＲをとった結果はゼロブロックになる。従って、対角パリティをさらに追加しなくても、抜けているパリティが各々に加算されたそれらの対角パリティブロックの和は対角パリティブロックの合計に等しい。
【００１８】
次に、対角パリティブロックの各々からその抜けている対角パリティを減算する。２台のデータディスクが故障した後には、１ブロックしか失われていない対角パリティ集合が少なくとも２つ存在する。それらのパリティ集合の各々から失われたブロックは、一方の集合がパリティブロックを持たない対角であれば、復元することが可能である。これらのブロックが復元されると、２つの行パリティ集合について１要素を除いたすべての要素が利用可能になる。これにより、それらの行の失われた要素の復元が可能になる。この復元により、他の対角に対して、対角上で１つだけ失われたブロックを復元するのに十分な情報が提供される。行パリティ及び対角パリティを交互に利用したこの復元パターンは、すべての失われたブロックを復元し終えるまで継続される。
【００１９】
ｎが素数なので、復元の際に、すべての対角に出くわすまで、即ちすべての失われたデータブロックが復元されるまで、循環が形成されることはない。ｎが素数でなければ、状況は異なる。両方のパリティディスクが失われた場合は、データからパリティの単純な復元を実施することが可能である。データディスクと対角パリティディスクが失われた場合は、行パリティを用いてデータディスクの単純なＲＡＩＤ−４スタイルの復元を実施した後、対角パリティディスクの復元を実施する。データディスクと行パリティディスクが失われた場合は、１つの対角パリティを計算することができる。すべての対角が同じパリティを有するので、次いで各対角上の失われたブロックを計算することが可能である。
【００２０】
各データブロックが対角パリティ集合の要素であるため、２台のデータディスクが失われた場合（２重故障）、１要素しか失われていない対角パリティ集合が２つ存在する。各ディスクには、そのディスク上に現れない対角パリティ集合がある。従って、２重故障の場合、復元可能な２つの対角パリティ集合が存在する。ＥＶＥＮＯＤＤは、両方のパリティディスクの故障や、１台のデータディスクと１台のパリティディスクとの任意の組み合わせの故障からの復元も可能である。また、この技術は、任意の一台のディスク故障からの復元も可能である。
【００２１】
ＥＶＥＮＯＤＤ技術は、パリティ情報の量については最適であるが、符号化及び復号の両方に必要な計算の量については漸近的最適さにすぎない。その理由は、抜けている対角パリティを対角パリティブロックの各々に追加するために必要な余分な計算にある。つまり、１ストライプ中のｐ−１個のブロックでは、ｐ個の対角から生成されるｐ個のパリティブロックを保持するのに不十分であるからである。これを克服するため、ＥＶＥＮＯＤＤ技術では、対角のうちの１つのパリティを他の対角すべてのパリティブロックとＸＯＲをとる必要があるので、計算のオーバヘッドが増大している。
【００２２】
概して、直接のパリティブロックを持たない対角のデータブロックへの書き込み処理は、いかなる小さな書き込み処理についても、すべての対角パリティブロックを更新しなければならない。また、大きな書き込み処理については、余分な計算も必要になる。本明細書で用いる場合、「大きな書き込み」処理には、１ストライプのすべてのブロックの書き替えが含まれ、「小さな書き込み」処理には、少なくとも１データブロック及び関連するパリティの変更が含まれる。
【００２３】
発明の概要
本発明は、ストレージアレイ中の２台の記憶装置の同時故障からの効率的な復旧が可能になるように構成されたストレージアレイについて、対角パリティの計算のオーバヘッドを低減させる「行−対角」（Ｒ−Ｄ）パリティ技術を含む。このＲ−Ｄパリティ技術は、ｐを素数とし、ｎ＝ｐ＋１としたときに、行パリティディスク及び対角パリティディスクを含む数ｎのディスク等の記憶装置で使用することが好ましい。ディスクはブロックに分割され、ブロックはストライプに編成され、各ストライプがｎ−２行を含む。ストライプを形成するために選択される行のブロックは通常各ディスク上で連続しているが、これは本発明に必須ではない。対角パリティディスクは、アレイの対角パリティ集合（「対角」）に沿って計算されたパリティ情報を記憶する。ストライプ内のブロックはｎ−１個の対角に編成され、対角の各々がデータディスク及びパリティディスクの中からｎ−２個のブロックを保持し、１つの対角を除くすべての対角がそのパリティを対角パリティディスク上のブロックに記憶する。その結果、この新規のＲ−Ｄパリティ技術は、一様なストライプ深さと、任意の２台のディスク故障からの復元を可能にするのに必要な最少量である２台のディスク分に等しいパリティ情報の量を提供する。
【００２４】
本発明によると、Ｒ−Ｄパリティ技術は、アレイ内のデータディスクの各行に沿った行パリティの計算を含み、その後、対角パリティディスク上に記憶する対角パリティを計算するときには、行パリティブロックとデータブロックとを区別しない。つまり、対角パリティは、すべてのデータディスクと行パリティディスクを合わせた範囲にわたる対角に沿って計算される。さらに、１つの対角を除くすべての対角について、対角パリティディスク上にパリティが記憶される。換言すれば、対角パリティディスクは、ストライプ中の１つを除く各々の対角についてパリティブロックを保持する。また、本発明の技術は、対角のうちの１つについてパリティが記憶（または計算）されていなくても、アレイ内の任意の２つの同時ディスク故障からの復旧に必要な十分な情報を提供する。
【００２５】
有利なことに、本発明の技術は、故障の無い動作中、アレイに記憶されるパリティを計算するための計算負荷を最小限にする。また、本発明は、パリティ計算のオーバヘッドも最小限にし、所定数のデータディスクについて必要な計算も、ＥＶＥＮＯＤＤなどの従来の方法に比べて少なくなっている。本発明のＲ−Ｄパリティ技術は、失われたデータを復旧するために必要な計算の総量を最小限にすることにより、復旧を速めている。さらに、本発明は集中パリティ技術を用いて実施することもでき、その場合、行パリティブロックがすべて同じディスク上に記憶され、既存のパリティ情報を再フォーマットしたり再計算したりすることなくデータディスクをアレイに徐々に追加してゆくことができる。データディスクをアレイに追加する際の制限は、アレイ内で利用可能なディスクの最大数を前もって決めておかなければならないことだけである（重要）。この制限は、対角の利用と、それらの対角の長さがストライプの深さに応じて決まることに起因している。実際に存在するディスクの数とアレイ内のディスクの最大数との差は、ゼロ値のデータのみを保持する「仮想」ディスクで埋められる。
【００２６】
また、本発明は、行パリティ配置について、分散パリティ配置を用いて実施することも可能である。例えば本発明は、素数のディスクを有するＲＡＩＤ−５アレイに１台の対角パリティディスクを追加することにより、実施される場合がある。本発明は、行内のパリティ等の冗長性を用いて１台のディスク故障を許容する素数のディスク構成であれば、いかなる構成でも機能するであろう。そのような場合、本発明は、対角パリティ専用に１台のディスクをアレイに追加することによって実施され、元のアレイのディスク上に定義された対角にわたる通常のパリティ計算を用いて対角パリティを計算する。
【００２７】
本発明の説明は、すべての行パリティが１つのディスク上に記憶される集中パリティ実施形態に関するものである。
【００２８】
本発明の上記の利点及び更なる利点は添付の図面と共に下記の説明を参照することによりさらによく理解することができ、図面中の似たような符号は同じ要素または機能的に類似した要素を示している。
【００２９】
図２は、本発明に有利に用いられるストレージシステム２２０を含む環境２００を示す略ブロック図である。本明細書で説明する本発明の技術は、ストレージシステム２２０として実現された、あるいは、ストレージシステム２２０を含む、スタンドアロンのコンピュータやその一部を含むいかなる種類の特別な目的（例えばファイルサーバやファイラー）のコンピュータまたは汎用コンピュータにも適用することができる。さらに、本発明の教示は、これらに限定はしないが、ネットワークに取り付けられたストレージ環境、ストレージエリアネットワーク、及びクライアントまたはホストコンピュータに直接取り付けられたディスクアセンブリを含む、様々なストレージシステムアーキテクチャに適合させることができる。従って、「ストレージシステム」という用語は、ストレージ機能を実施するように構成され、他の装置またはシステムに関連付けられた任意のサブシステムに加えて、それらの構成も含むように広く解釈しなければならない。
【００３０】
例示的実施形態において、ストレージシステム２２０は、システムバス２２５によって相互接続されたプロセッサ２２２、メモリ２２４及びストレージアダプタ２２８を含む。メモリ２２４は、本発明に関するソフトウェアプログラムコード及びデータ構造を記憶するためにプロセッサ及びアダプタによってアドレス指定可能な記憶場所を含む。そして、プロセッサ及びアダプタは、そのソフトウェアコードを実行し、データ構造を操作するように構成された処理要素及び／又は論理回路を含む。ストレージオペレーティングシステム６００は通常、その一部がメモリ内に存在し、処理要素によって実行され、とりわけ、ストレージシステムによって実行される記憶処理を呼び出すことにより、システム２００の機能を構成する。当業者であれば、本明細書で説明する本発明の技術に関するプログラム命令の記憶及び実行のために、様々なコンピュータ読取可能媒体を含む他の処理手段及びメモリ手段を用いることもできることは、明らかであろう。
【００３１】
ストレージアダプタ２２８は、システム２２０上で実行されているストレージオペレーティングシステム６００と協働して、ユーザ（またはクライアント）から要求された情報にアクセスする。その情報は、データ及びパリティ情報含めて情報を記憶するように構成された、ビデオテープ、光学式ＤＶＤ、磁気テープ、バブルメモリ、電子的ランダムアクセスメモリ、マイクロ電気機械、及び、何らかの他の媒体などの任意の種類の書込可能記憶装置媒体の取り付けられたアレイ上に記憶される。しかしながら、本明細書で例示的に説明するように、この情報は、アレイ４００の、ＨＤＤ及び／又はＤＡＳＤ等のディスク２３０上に記憶することが好ましい。ストレージアダプタは、従来の高性能ファイバーチャネルシリアル接続トポロジ等のＩ／Ｏ相互接続構成を介してそれらのディスクに接続された入出力（Ｉ／Ｏ）インタフェースを含む。
【００３２】
アレイ４００上での情報の記憶は、ディスク空間の全体的な論理的配置を定義する、物理的記憶ディスク２３０の集まりを含む１以上のストレージ「ボリューム」として実施されることが好ましい。各ボリュームは通常、必須ではないが、そのボリューム自体のファイルシステムに関連している。ボリューム／ファイルシステム内のディスクは通常、１以上のグループに編成され、各グループがＲＡＩＤ（Redundant Array of Independent(or Inexpensive) Disks）として動作している。ほとんどのＲＡＩＤ実施形態は、ＲＡＩＤグループ内の所定数の物理ディスクに「ストライプ状」にまたがるデータの冗長書き込みと、そのストライプ化されたデータに関するパリティ情報の適当な記憶とによって、データ記憶の信頼性／完全性を向上させている。
【００３３】
本発明は、ディスクアレイ内の行パリティと対角パリティとを用いて２重故障のパリティ訂正復旧を提供する「行−対角」（Ｒ−Ｄ）パリティ技術を含む。本発明の技術は、ストレージオペレーティングシステム６００のディスクストレージ層（図６の符号６２４に示す）によって実施され、ストレージシステムにおけるディスク等の複数の記憶装置にわたるストライプにパリティを作成するための方法及びシステムを提供することが好ましい。アレイ中の２台のディスクは完全にパリティ専用であり、残りのディスクはデータを保持する。データディスク上のデータは、記憶のためにそれ以上符号化されないという意味で、「クリア」に記憶される。任意の１台または２台の同時ディスク故障の後、アレイの内容はデータを失うことなく完全に復元することができる。本発明は、従来の方法に比べてパリティ情報の計算量を低減させるとともに、２台のディスク故障から復旧させるための計算も低減させている。さらに本発明は、一様なストライプ深さ（各ディスクが１ストライプ当たり同数のブロックを保持する）を提供し、２台のディスク故障からの復元を可能にするために必要な最小量である２台分のディスクに等しい量のパリティ情報を提供する。
【００３４】
概して、本発明は、ｎ＝ｐ＋１、ｐが素数であるものとして、ｎ個の記憶装置を含む。これらの記憶装置は、同サイズのブロックに分割される。各装置内で、ｎ−２個のブロックが任意に選択され、すべての装置にわたるストライプを形成するようにグループ化される。入力として他の装置の中からブロックを選択することによって形成されたパリティを保持するため、ストライプ内で一台の装置が指定される。本明細書でさらに説明する単純化された作成技術の結果、この装置は対角パリティ装置と呼ばれ、この装置が保持するパリティは対角パリティと呼ばれる。各ストライプ内で、ストライプ内の対角パリティ装置以外の装置の各々の中から１ブロックが選択される。このブロックの集合は、行と呼ばれる。行内の１ブロックがその行のパリティを保持するために選択され、残りのブロックはデータを保持する。行の構築は、ストライプ内の対角パリティ装置以外にあるすべてのブロックがちょうど１行に割り当てられるまで続けられる。全部でｎ−２行になる。
【００３５】
各ストライプ内で、ストライプ内の対角パリティ装置以外のすべての装置のうち一台を除く各々の装置から１ブロックを選択し、選択されたブロックのうちの２つが同じ行に属しないという制限をさらに付ける。これは、対角パリティ集合または「対角」と呼ばれる。例えば対角は、データ装置、行パリティ装置及び対角パリティ装置に０からｎ−１までの番号を付け、各行に０からｎ−３の番号を付け、そして、装置ｉ、行ｊにあるブロックを対角（ｉ＋ｊ＋１）ｍｏｄ（ｎ−１）に割り当てることによって形成することができる。この対角の形成は、ストライプ内の対角パリティ装置上に無いブロックのすべてが対角に割り当てられるまで続け、同じ装置の中からすべてのブロックを含まない２つの対角が無いようにするという制限をさらに付ける。ｎ−１個の対角になる。ｎ−１個の対角の中からｎ−２個の対角を選択する。これらの対角内のブロックは、データを保持するものであるかパリティを保持するものであるかに関わらず、結合されて対角パリティブロックを形成する。これらのｎ−２個の対角パリティブロックは、ストライプ内の対角パリティを保持する装置上にあるストライプのｎ−２個のブロックに、任意の順序で記憶される。
【００３６】
本発明は、各ディスクの同じ位置にあるブロックを保持する行を選択し、ｎ−１行の連続したグループを選択してストライプを形成し、さらにそのストライプ内のブロックを選択して、各対角のブロックによって循環する対角パターンが形成されるようにすることにより、簡単に実施することも可能である。さらに本発明は、あるストライプのすべての行パリティブロックをそのストライプの同じ装置に記憶することにより、実施することもできる。好ましい実施形態では、本発明は、ストライプが異なっても、行パリティ装置、対角パリティ装置あるいはデータ装置として、装置の同じ用途を保つことにより実施することもできる。あるいは、本発明の他の好ましい実施形態では、ストライプが異なるごとに、行パリティ装置、対角パリティ装置あるいはデータ装置として、装置の用途を循環または変更することにより実施することもできる。
【００３７】
パリティは、一般にデータブロックの排他的論理和（ＸＯＲ）として計算され、パリティブロックを形成する。ＸＯＲ演算は、一般に各入力ブロックの同じ１ビットフィールド上で実施され、１つの対応する出力のビットを生成する。前述のように、このＸＯＲ演算は、２つの１ビットフィールドの２の補数加算または減算と同じである。また、すべての入力において、同サイズの複数ビットフィールド（例えば８，１６，３２，６４，１２８ビット）の合計として、冗長パリティ情報も計算される。例えば、このパリティの等価物は、３２ビットフィールドに対して２の補数加算を用いてデータを加算することにより計算することができ、各々３２ビットの冗長情報が生成される。あるブロックとそのブロック自体とのＸＯＲはゼロになるので、これは、あるブロックの２回の同じ入力に関するＸＯＲ演算がそのブロックの元の内容になることが信頼できないことを仮定した場合だけである。本明細書で説明する本発明の技術はＸＯＲの態様に依存しないので、１ビットよりも大きなフィールド上での加算及び減算によって実施することができる。
【００３８】
データビットの直接ＸＯＲ合計をパリティビット値として記憶するのが一般的であると言える。この方法はしばしば「偶数パリティ」と呼ばれる。あるいは、データビットのＸＯＲ合計の補数を記憶する場合もあり、これは「奇数パリティ」と呼ばれる。本明細書で開示する発明に関して、偶数パリティまたは奇数パリティの使用は指定されていない。しかしながら、このような区別が問題となる場合、本明細書で参照するアルゴリズムは、偶数パリティが用いられるものとして説明している。また、当業者であれば、本発明の教示に従って奇数パリティも使用できることは明らかであろう。
【００３９】
当業者であれば、ブロック（パリティ計算のための）が、ファイルブロック、データベースブロック、ディスクセクタ、または、他の都合のよい大きさの単位に対応する場合もあれば対応しない場合もあることは明らかであろう。パリティ計算のために用いられるブロックサイズがシステムで使用される他のブロックサイズと何らかの関係を有することは、全く必要ない。しかしながら、１以上の整数のパリティブロックが、１以上の整数のディスクセクタとして定義された単位に、ちょうど収まるようにすることが望ましい。多くの場合、いくつかのブロックはファイルシステムのブロックまたはデータベースのブロックに対応し、その大きさは典型的には４ｋ（４０９６）バイトまたはそれより大きな２の階乗バイト（例えば８ｋ、１６ｋ、３２ｋ、６４ｋ、１２８ｋ、２５６ｋ）になる。
【００４０】
本明細書で説明する例示的システムは、全ストライプ書き込み処理を実施することが好ましい。特に、通常４ｋまたは８ｋバイトである個々のファイルブロックを、パリティ計算にしか使用されないより小さなブロックに分割し、例えば４ｋバイトサイズのブロックの全ストライプをアレイのディスクに書き込みできるようにすることが好ましい。全ストライプをディスクに書き込む場合、結果をディスクに書き込む前にメモリ内ですべてのパリティ計算が実施されるため、ディスク上のパリティの計算及び更新の負荷が低減される。
【００４１】
図３は、本発明のＲ−Ｄパリティ技術を含むステップのシーケンスを例示したフロー図である。このシーケンスはステップ３００で開始し、ステップ３０２へ進み、ここで行パリティディスクを含む素数ｐのディスク等の記憶装置を用いてアレイを構成する。ステップ３０４で対角パリティディスクを追加して、アレイ全体がｐ＋１台のディスクから構成されるようにする。以下で説明するように、この対角パリティディスクは、アレイの全てのデータディスク及び行パリティディスク全体にわたる対角パリティ集合を定義することによって計算された対角パリティを記憶する。従ってこのアレイは、ｐ−１台のデータディスクと、１台の行パリティディスクと、１台の対角パリティディスクとを含む。ステップ３０６でディスクをブロックに分割し、ステップ３０８でブロックをストライプに編成して各ストライプがｎ−２行（ｎ＝ｐ＋１）のブロックを含むようにする。各ディスクをｎ−２ブロックのストライプに分割することが好ましい。ステップ３１０で、行の各データブロックのＸＯＲをとり、各データディスク上の同じ位置にあるすべてのデータブロックのＸＯＲを保持するその行の行パリティブロックに入れる。
【００４２】
次にステップ３１２で、全てのデータブロック及び行パリティブロックを対角に割り当てる。ｐ台のディスクを含むアレイの場合、これらの対角はｐ−１行のブロックのグループ内に含まれる。ちょうどｐ個の対角が存在し、各対角は、ちょうどｐ−１個のデータブロック及び／又は行パリティディスクのＸＯＲからなる１つの対角パリティブロックを含む。これらの対角はアレイの端部で循環し、ｐ個の対角集合の各々がちょうど１台のディスクだけ含まないようにする。各対角が含まないディスクは、異なるものにしなければならない。ｐ−１行の集合内で、あらゆるディスクブロックは、ｐ個の対角のうちのちょうど１つの上に存在する。表１は、０から４まで番号を付けた対角を有するｐ＝５のアレイの一実施形態を示している。表中の番号は、各ブロックが属する対角パリティ集合を示している。
【表１】
0004823468.tif 000002
【００４３】
行内の２つのブロックが同じ対角パリティ集合に属することがない限り、任意の２台のディスク故障からアレイを復元できるという特徴を変更することなく、各列の要素の位置を変更するのに応じて、列の位置を変更することが可能である。一般性を失うことなく、実質的に表１に従う方法でブロックを対角パリティ集合に割り当てることができると推定される。また、行内のブロックの要素を変更することも可能である。
【００４４】
上記のように、対角パリティ集合のパリティは対角パリティディスクに記憶される。本発明によると、Ｒ−Ｄパリティ技術は、対角パリティディスクに記憶される対角パリティを計算する際に、行パリティブロックとデータブロックとを区別しない。換言すれば、元のアレイのすべてのディスクが同等に取り扱われ、それらのうちの１つに記憶された情報は、その行パリティ集合内の他のすべてのディスクのＸＯＲ合計から復元できるようになっている。従って、対角パリティディスクは、アレイのすべてのデータディスク及び行パリティディスクにわたる対角パリティ集合に沿って計算された対角パリティを記憶する（ステップ３１４）。データディスク、行パリティディスクまたは対角パリティディスクなどのディスクの役割はストライプによって異なり、ＲＡＩＤ５スタイルの分散パリティ実施形態を可能にしている。
【００４５】
しかしながら、対角パリティディスク上には、ｐ−１行上に定義されたｐ個の対角について、すべてのパリティ情報を保持するだけの十分な空間が存在しない。具体的には、ｐ−１ブロックの対角パリティについて十分な空間しか存在しない。各データディスク及び行パリティディスクは最大でも１ブロックが１対角に属するだけであり、データであるか行パリティであるかに関わらず同じ対角の要素である２ブロックを含む行は存在しない。１ストライプ中にはちょうどｐ個の対角が存在するが、対角パリティディスク上にはｐ−１個の対角パリティブロックしか存在しない。
【００４６】
これを克服するため、対角パリティ集合のうちの１つについては、対角パリティが対角パリティディスク上に記憶されない（ステップ３１６）。すなわち、対角パリティディスクは、１ストライプ中の１つの対角を除いて各々の対角についてパリティブロックを保持する。いずれの対角パリティブロックを記憶しないかの選択は、任意である。そのパリティは記憶されないので、計算もされない。また、対角のうちの１つについてパリティが記憶されていなくても、本発明の技術は、アレイ内の任意の２台の同時ディスク故障から復旧させるのに十分なパリティ情報を提供することができる。すなわち、任意の２台のディスクが失われた場合、本発明の復元態様に従って、１ストライプの内容全体を復元することができる（ステップ３１８）。ステップ３２０で、この復元処理をすべてのストライプについて繰り返すことにより、２台の故障したディスクの内容全体を復元することができる。そしてこのシーケンスはステップ３２２で終了する。
【００４７】
ディスクを対角に割り当てる際に行パリティディスクとデータディスクとが区別されないので、対角パリティ集合からの復元を扱うときに、行パリティディスクとデータディスクとの区別は無視することができる。これを例示するため、任意の２台のデータディスク、または、任意の１台のデータディスクと行パリティディスクが失われた場合を考える。パリティ集合の中の失われたブロックは、そのパリティ集合を構成する他のすべてのブロックが利用可能である場合にのみ復元することができる。ＸＯＲパリティの巧妙さは、ブロックが最初にデータを保持していたかパリティを保持していたかに関わらず、すべてのブロックが数学的に等価であることである。例えば「＾」がＸＯＲ演算子を表すものとして、パリティ構成ａ＾ｂ＾ｃ＝ｄを考える。両辺をｄでＸＯＲをとると、ａ＾ｂ＾ｃ＾ｄ＝０になる。従って、すべてのデータディスク及び行パリティディスクは、復元の際に同じ物として扱うことができる。
【００４８】
これらのディスクの各々において、ちょうど１つの対角だけは現れない。従って、復元は、その対角の要素を含まない他のディスク上から開始することができる。２台のディスクが故障したとき、ほとんどの場合において、対角パリティデータから直ぐに復元できる２つのブロックが存在する。これは、１ブロックだけを失った対角のうちの一方がパリティの記憶されていない対角でない限り、本当である。しかしながら、大抵は１台のディスクがそのパリティ集合についてデータを失っているだけなので、直ぐに復元可能なブロックが少なくとも１つ存在する。対角パリティから１ブロックまたは２ブロックを復元すると、その時点で対角パリティ（対角パリティブロックを含まない）を用いて復元されたブロックを有する行パリティ集合に欠けているのは１ブロックだけであるから、その行またはそれらの行の他の失われたブロックは行パリティから復元することができる。これらのブロックを復元した後、同じ対角上にある１または２以上のブロックを、行ブロックとして復元することができる。
【００４９】
従って、復元は、一連の対角「移動」そして水平「移動」によって進められる。ｐが素数であるため、一連の水平移動そして対角移動は、同じ行に２回ヒットするまでストライプ内のあらゆる行を移動する。また、対角についてパリティが記憶されていないために、その対角を超えて対角移動が不可能な１つの対角が存在する。一般性を失うことなく、対角には０からｐ−１まで番号が付けられ、対角ゼロを除いてすべての対角についてパリティが計算される。従って対角ゼロに沿った対角移動は不可能である。アレイ内で所定の距離だけ離れたディスクの場合、対角ゼロで終わる復元可能な対角の固定シーケンスが常に存在する。ディスクに０からｐ−１まで番号を付け、ディスクｐ−１（行パリティディスク）がディスク０に隣接するようなディスク間の循環を考えた場合、（ｐ−１）個のシーケンスが考えられる。各シーケンスは、その距離だけ隔てたディスクの任意の対の復元に対応する。例えば、表２はｐ＝１３のときのシーケンスを例示している。
【表２】
0004823468.tif 000003
【００５０】
ディスクｋ離れた場合のシーケンスは、常に対角ｋで始まり、毎回ｊをインクリメントしてモジューロｐをとることにより継続され、ｐ  ｍｏｄ  ｐ＝０で終了することに注意して欲しい。また、ディスクｋ離れた場合のシーケンスの最初のｐ項が、ディスクｐ−ｋ離れた場合のシーケンスの最初のｐ項の逆順であることにも注意して欲しい。
【００５１】
シーケンス上の開始位置は、いずれのディスク対が故障したかに応じて決まる。先の説明に従ってディスク及び対角に番号を付けた場合、すなわち、ディスクに０からｎ−１までの番号を連続的に付け、行に０からｎ−３までの番号を連続的に付け、故障した各ディスクｊにおいて、ディスクｊのブロックｉが対角パリティ集合（ｉ＋ｊ＋１）ｍｏｄ（ｎ−１）に属している場合、抜けている対角は常に対角ｊである。従って、ｋだけ隔てたディスク対の場合、修復を開始することが可能な２つの対角は、ｊと（ｊ＋ｋ）ｍｏｄ（ｎ−１）である。ディスクｋ離れた復元シーケンスにおいて、これら２つの対角が常に隣接していることに注意して欲しい。これら２つのシーケンスでは、開始点から右へ移動することにより判定される対角のシーケンスで復元が進められ、ディスクｋ離れた場合、記号（ｊ＋ｋ）ｍｏｄ（ｎ−１）から開始され、ディスクｐ−ｋ離れた場合、ｋ＜ｐ／２として記号ｊから開始される。従って、２台のデータディスクの任意の組み合わせが故障した場合でも、１台のデータディスク及び行パリティディスクが故障した場合でも、完全に復元することが常に可能である。対角パリティディスクともう１つ他のディスクが故障した場合、故障した他のディスクがデータディスクであるか行パリティディスクであるかに関わらず、記憶された行パリティから他の故障したディスクを復元し、次いで対角パリティディスクを復元することは簡単なことである。結果として、本発明のＲ−Ｄパリティ技術によると任意の２台のディスク故障からの復旧が可能になる。
【００５２】
すべてのデータブロックがパリティの計算された対角に属するわけではないことに注意すべきである。実際、対角パリティは、データブロックのうちの（ｐ−１）／ｐと、行パリティブロックについてしか計算されない。１ブロックの更新は、そのブロックの行パリティブロックだけでなく、そのブロックの対角パリティブロックも再計算しなければならいので、コストがかかる。そして、１ブロックについて行パリティを更新する場合には、その行パリティブロックの対角パリティブロックにも変更を加えなければならない。しかし、これは、ストライプが１「ブロック」幅であって、パリティ計算にしか使用されないサブブロックから構成されたシステムでは、簡略化することが可能である。その場合、パリティ更新を計算し、それを行パリティに加算する。また、同じパリティ更新ブロックの部分は、そのストライプの対角パリティブロックの部分にも直接加算される。
【００５３】
図４は、本発明の新規のＲ−Ｄパリティ技術に従って編成されたディスクアレイ４００を示すブロック図である。ｎはアレイ内のディスク数であり、ｎ＝ｐ＋１であるものと仮定する。最初のｎ−２台のディスク（Ｄ０〜Ｄ３）はデータを保持し、ディスクｎ−１（ＲＰ）はデータディスクＤ０〜Ｄ３についての行パリティを保持し、ディスクｎ（ＤＰ）は対角パリティを保持している。この例示的実施形態では、アレイ内のディスク数ｎは６である。ディスクはブロックに分割され、ブロックはストライプにグループ化され、各ストライプがｎ−２（例えば４）行になっている。さらに、１ストライプ当たりｎ−１（例えば５）個の対角が存在する。
【００５４】
各ブロックが１対角パリティ集合に属し、各行内で各ブロックが異なる対角パリティ集合に属するように、データブロック及び行パリティブロックに番号が付けられている。Ｄa,b及びＰa,bという記述は、データ（Ｄ）ブロック及びパリティ（Ｐ）ブロックの特定の行（ａ）及び対角（ｂ）パリティ計算への寄与をそれぞれ表している。すなわち、Ｄa,bという記述は、それらのブロックが行パリティａ及び対角パリティｂの計算に使用される行または対角に属していることを意味しており、Ｐa,bは、行パリティ集合ａについてのパリティを記憶するとともに、対角パリティ集合ｂにも寄与することを意味している。例えば、Ｐ0,8＝Ｄ0,4＾Ｄ0,5＾Ｄ0,6＾Ｄ0,7である。この記述は、特定の対角についての対角パリティの計算に使用される行パリティブロックにも用いられ、例えばＰ4＝Ｄ0,4＾Ｄ3,4＾Ｄ2,4＾Ｐ1,4である。対角パリティディスク上に記憶された対角パリティブロックの各々は、アレイ内の他のディスク（行パリティディスクを含む）のうちの一台を除いて全てのディスクからの寄与を含むことに注意して欲しい。例えば、対角パリティブロックＰ4は、Ｄ０（Ｄ0,4）、Ｄ２（Ｄ3,4）、Ｄ３（2,4）及びＲＰ（Ｐ1,4）からの寄与を含むが、Ｄ１からの寄与は含まない。また、対角８（Ｐ8）についての対角パリティは、計算もされず、対角パリティディスクＤＰに記憶もされないことに注意して欲しい。
【００５５】
本発明によると、ディスクＤＰ上の対角パリティブロックは、それらのＸＯＲ計算を行なう際に行パリティブロックも含める。すなわち、ディスクＤＰに記憶された対角パリティは、データディスクの内容だけでなく、行パリティディスクの内容にも従って計算される。アレイ４００に示すように対角パリティブロックを符号化することにより、本システムは、対角パリティ（Ｐ8）が無くても、任意の２台の同時ディスク故障から復旧させることが可能である。これは、対角パリティディスクＤＰ上に記憶される対角パリティブロックの計算に、行パリティブロックが要素として含まれた結果である。これに対して従来のＥＶＥＮＯＤＤ技術は、対角パリティ集合の計算に、行パリティブロックを要素として含めていない。むしろ、従来のＥＶＥＮＯＤＤのアプローチは、対角パリティディスク上に記憶される他の対角パリティブロックの各々に、この抜けている対角パリティブロックを要素として含めている。
【００５６】
動作時には、対角パリティディスクと何らかのデータディスクとが失われた場合、まず行パリティからデータディスクを復元し（例えば従来のＲＡＩＤ−４復元技術に従って）、次いで対角パリティディスクを復元することによって、復旧を行なうことができる。同様に、２台のパリティディスクが失われた場合、まずデータディスクから行パリティディスクを復元し、次いで対角パリティディスクを復元することによって、復旧を行なうことができる。一方、任意の一対のデータディスクが失われた場合、対角パリティ集合のうちの少なくとも１つ、大抵は２つから１ブロックを直ぐに復元することができる。続いて、システムは残りの失われたデータブロックを復元することができる。注意して欲しいのは、行パリティディスクとデータディスクが失われた場合は、２台のデータディスクが失われた場合と全く同じであり、復元も同じ方法で行なうことができる点である。
【００５７】
図５は、新規のＲ−Ｄパリティ技術の復旧（復元処理）態様に必要なステップのシーケンスを示すフロー図である。このシーケンスは、ステップ５００で開始して、ステップ５０２へ進み、ここでアレイ４００の中の２台のデータディスクが故障により同時に失われたものと仮定する。故障した２台のデータディスクには任意の組み合わせがあるため、失われたデータを復元するのに行パリティを直ちに用いることはできないが、対角パリティだけは用いることができる。与えられたアレイの構造および編成（即ち、ストライプの長さとストライプの深さが等しくない）の場合、各対角は、ディスクのうちの１台からはブロックを含まない（抜けている）。そのため、２台のデータディスクが失われた場合でも、１要素しか失わない対角が２つ存在する。言い換えると、２台のディスクが失われても、それらのディスクの各々が１つの対角の要素にはなっていない。対角パリティブロックは、１つの対角を除くすべての対角についてＤＰディスク上に記憶されているので、ステップ５０４で、抜けているブロックのうちの少なくとも一方、通常２つの復元が、対角パリティを用いて開始される。
【００５８】
失われたブロックを１つ復元した後、行パリティを用いてその行にある他の失われたブロックを復元することにより、行の復元を計算することができる（ステップ５０６）。他のブロックを復元する場合、ステップ５０８で、そのブロックがパリティの記憶された対角に属しているか否かについて判定を行なう。そのブロックがパリティのある対角に属している場合、その対角上にある他のディスクから、対角パリティを用いてその対角上にある他方の失われたブロックを復元することができる（ステップ５１０）。すなわち、抜けている対角を除くすべての対角について、その対角上の１ブロックが復元できれば、他方のブロックも復元することが可能である。その後シーケンスはステップ５０６へ戻り、その行パリティ集合の他方の失われたブロックを復元する。しかしながら、ブロックがパリティの無い対角（即ち、抜けている対角）に属していた場合、ステップ５１２で、すべてのブロックを復元し終わったか否かについて判定を行なう。まだ復元し終っていない場合、シーケンスはステップ５０４へ戻り、そこで対角パリティに基づく第１の復元と、続く行パリティに基づく復元とからなるパターンを繰り返し、抜けている対角パリティ集合の計算に用いられる最後のデータブロックに達するまでそれを継続する。すべてのブロックを復元し終えると、シーケンスはステップ５１４で終了する。この抜けている対角パリティ集合は、常に復元の連鎖の最後になる。
【００５９】
具体的に、アレイ４００中の隣接するデータディスクＤ０及びＤ１が失われたものと仮定する。Ｄ０は対角パリティ集合８の要素を持たず、Ｄ１は対角パリティ集合４の要素を持たない。しかしながら、対角８についてのパリティは計算も記憶もされていないので、復元の開始点は１つしかなく、それは対角４である。他の従来の２重ディスク故障パリティ訂正手段は一般に復元用の２つの開始点を有するが、本発明の一態様によると、ただ１つの開始点しか必要なく、ただ１つしか利用できない。対角４が１要素しか失っていないので、Ｄ０上のデータブロックＤ0,4はその対角４から直ちに復元することができ、次いでパリティディスクＲＰ上のパリティブロックＰ0,8に記憶された行パリティ情報に従ってデータディスクＤ１上のデータブロックＤ0,5の復元が可能になる。
【００６０】
データブロックＤ0,5が復元されると、対角５に抜けているのは１要素だけになるので、その要素（即ち、Ｄ０上のデータブロックＤ1,5）は対角パリティを用いて復元することができる。データブロックＤ1,5が復元されると、パリティディスクＲＰ上のパリティブロックＰ1,4を用いた行パリティ復元により、Ｄ１上のＤ1,6の復元が可能になる。この復元の「対角−行」シーケンスは、抜けている対角パリティ集合の計算に用いられる最後のデータブロック（Ｄ１上のＤ3,8）に達するまで進められることに注意して欲しい。この例では、復元の連鎖は、抜けている対角パリティ集合（Ｐ8）で終了する。また、各対角について、故障したディスク間の距離（即ち、ディスク数）は、失われたデータを対角パリティ集合に沿って復元するときに通る行数に等しいことにも注意して欲しい。さらに、復元の連鎖は１つしかないが、パリティ集合８の中の１ブロックだけが失われていることにも注意して欲しい。
【００６１】
他の例として、隣接するディスクＤ１及びＤ２が失われ、これによって対角パリティ集合４及び５の各々が１要素を失った場合を仮定する。対角パリティ集合５に関する失われたデータブロック（Ｄ１上のＤ0,5）は直ちに復元することができ、同様に対角パリティ集合４に関する失われたデータブロック（Ｄ２上のＤ3,4）も直ちに復元することができる。これらの復元されたブロックの各々は、上記の「対角−行」パターンに従って行パリティ情報を用いて他のデータブロックを復元するために使用することができる。これは、失われたデータディスクの復元に用いられる２つの並行復元「スレッド」の例であることに注意して欲しい。第１のスレッドはＤ0,5、Ｄ0,6、Ｄ1,6、Ｄ1,7、Ｄ2,7、Ｄ2,8を復元するように進められ、第２のスレッドはＤ0,5及びＤ0,6を復元するように進められる。この場合も、各スレッドは抜けている対角パリティ集合で終了する。
【００６２】
次に、２台のディスクが故障したが、それらのデータディスクが隣接していない場合を仮定する。例えば、Ｄ０及びＤ２が失われた結果、対角パリティ集合８及び５が１要素だけ失った場合を仮定する。上記のように、対角パリティ集合８は復元処理の役に立たないので、復元チェーンは、対角パリティ集合５に関する失われたデータブロック（Ｄ０上のＤ1,5）から開始する。そのデータブロックの復元によって、パリティディスクＲＰ上のパリティブロックＰ1,4に記憶された行パリティ情報を用いてＤ２上のデータブロックＤ1,7の復元が可能になる。失われたデータディスクが２つに分かれているので、対角パリティ集合７に関する失われたデータブロックの復元には、アレイ中を２行下がって、Ｄ０上のＤ3,7を通る必要がある。次いで、行パリティを用いてＤ２上の失われたデータブロックＤ3,4を復元することが可能になる。この「対角−行」パターンは、モジューロｐ（「循環」」）演算に従って続けられ、次にブロックがＤ0,4が復元され、その後Ｄ0,6、Ｄ2,6が、最後にＤ2,8が復元される。
【００６３】
要するに、この復元のシーケンスは、復元される最初の対角から開始して抜けている対角パリティで終了する復元可能な順序で対角をリストすることによって表現することができる。ｋだけ離れた２台の故障したディスクｊ及びｊ＋ｋの場合、対角の一方のシーケンスは毎回ｋだけ増加させることによって復元を行なうことができ、他方のシーケンスは毎回ｋだけ減少させることにより復元を行なうことができる。その理由は、行復元がｋディスク右（または左）へ移動するので、次のｋだけ大きい（または小さい）対角もモジューロｐだけ移動するからである。ほとんどの場合、複数（少なくとも２つ）の並行復元スレッドが存在する。例外は、「抜けている」対角のブロックを含まないディスクであるＤ０と、対角パリティディスクＤＰ以外の何らかの他のディスクが失われた場合である。その場合、復元されるブロックのストリームはただ１つしか存在せず、他方の失われたディスク上の抜けている対角パリティ集合のブロックで終了する。
【００６４】
図６は、本発明に有利に用いることができるストレージオペレーティングシステム６００を示す略ブロック図である。例示的実施形態では、このストレージオペレーティングシステムは、カリフォルニア州サニーベールにあるネットワークアプライアンス社から入手可能なＮｅｔＡｐｐ  Ｄａｔａ  ＯＮＴＡＰ（登録商標）オペレーティングシステムが好ましく、Ｗｒｉｔｅ  Ａｎｙｗｈｅｒｅ  Ｆｉｌｅ  Ｌａｙｏｕｔ（ＷＡＦＬ（登録商標））ファイルシステムを実施する。本明細書で用いる場合、「ストレージオペレーティングシステム」という用語は、一般にストレージシステムにおいてストレージ機能を実施することができるコンピュータ実行可能コードを指しており、例えばファイルシステムセマンティックを実施したり、データアクセスを管理したりする。その意味で、ＯＮＴＡＰソフトウェアは、マイクロカーネルとして実施されるそのようなストレージオペレーティングシステムの一例であり、ＷＡＦＬファイルシステムセマンティック及びデータアクセスの管理を実施するためのＷＡＦＬ層を含む。また、このストレージオペレーティングシステムは、ＵＮＩＸ（登録商標）やＷｉｎｄｏｗｓＮＴ（登録商標）等の汎用オペレーティングシステム上で動作するアプリケーションプログラムとして実施することもできるし、本明細書で説明するストレージアプリケーションのために構成されたストレージ機能または設定可能な機能を有する汎用オペレーティングシステムとして実施することもできる。
【００６５】
ストレージオペレーティングシステムは、ネットワークドライバ（例えばイーサネット（登録商標）ドライバ）のメディアアクセス層６１０を含む一連のソフトウェア層からなる。このネットワークオペレーティングシステムは、インターネットプロトコル（ＩＰ）層６１２、並びに、ＩＰ層がサポートするトランスポート手段であるＴＣＰ（Transport Control Protcol）層６１４及びＵＤＰ(User Datagram Protocol）層６１６等のネットワークプロトコル層をさらに含む。ファイルシステムプロトコル層は、マルチプロトコルアクセスを提供するため、ＣＩＦＳ（Common Internet File System）プロトコル６１８、ＮＦＳ（Network File System）プロトコル６２０、及び、ＨＴＴＰ（Hypertext Transfer Protocol）プロトコル６２２をサポートしている。さらに、オペレーティングシステム６００は、ＲＡＩＤプロトコル等のディスクストレージプロトコルを実施するディスクストレージ層６２４と、ＳＣＳＩ（Small Computer Systems Interface）プロトコル等のディスクアクセスプロトコルを実施するディスクドライバ層６２６とを含む。ディスクソフトウェア層とネットワークプロトコル層／ファイルシステムプロトコル層とを橋渡しするのは、好ましくはＷＡＦＬファイルシステムを実施するＷＡＦＬ層６８０である。
【００６６】
ストレージシステムで受信したユーザ要求に対して、データストレージアクセスを実施するのに必要な上記のストレージオペレーティングシステム層を通るソフトウェア「パス」は、代替的にハードウェアで実施することもできる。すなわち、本発明の代替の実施形態では、このストレージアクセス要求データパス６５０は、ＦＰＧＡ（Field Programmable Gate Array）やＡＳＩＣ（Application Specific Integrated Cirquit）の中に実現された論理回路として実施することもできる。この種のハードウェアによる実施形態は、ユーザ要求に応答してシステム２２０によって提供されるサービスの能力を向上させることができる。さらに、本発明のさらに他の実施形態として、アダプタ２２８の処理要素は、プロセッサ２２２からストレージアクセス処理の負荷の一部または全部を低減させるように構成し、ストレージシステムによって提供されるサービスの性能を向上させることもできる。本明細書で説明する様々な処理、アーキテクチャが、ハードウェアでもファームウェアでも、あるいはソフトウェアでも実施できることは、明らかである。
【００６７】
ここまで、ストレージアレイの対角パリティを計算するためのオーバヘッドを低減させるＲ−Ｄパリティ技術の例示的実施形態を図示及び説明してきたが、本発明の思想及び範囲から外れることなく、様々な変更及び修正が可能であることは明らかである。例えば本発明は、すべてのパリティ情報が２台のディスク上に記憶されるＲＡＩＤ−４に類似した集中パリティ配置に構成するのに適しているが、ＲＡＩＤ−５に類似した分散パリティ配置や、他の分散パリティ配置にも適用することが可能である。後者の分散パリティ配置によると、異なる行の集合内で、１行当たり２ブロックのパリティが存在し、アレイ内でそれらのパリティの位置がディスクごとにシフトされる。
【００６８】
行パリティ集合及び対角パリティ集合の完全なグループを保持し、行のグループ全体がその行内のいかなる２台のディスクの損失からも復旧可能であるようにするためには、本発明は、ｐ−１行のグループが必要であることが分かっている。例示的実施形態では、このグループの行は、ディスクアレイのディスクの隣接した行である。また、アレイが集中パリティスタイルに構成され、すべてのパリティ情報が２台のディスク上に存在する場合、必ずしもすべてのデータディスクが必要なわけではないことも分かっている。２台のパリティディスクが必要であり、それらが通常少なくとも１台のデータディスクを伴う。しかしながら、必ずしもアレイ内に全部でｐ−１台のデータディスクが存在する必要はない。存在しないディスクは、全てゼロ、即ちゼロのデータを保持するディスクが存在するかのように扱われる。そのため、パリティ値に全く関与することがなく、パリティの復元や故障したディスクの復旧に用いられるアルゴリズムの邪魔にはならない。
【００６９】
アレイを構成するための特に優れた選択である、いくつかの素数が存在する。これらは２のべき乗＋１の素数であって、ディスクアクセスに用いられるブロックサイズよりも小さく、アレイ内のディスク数以上の数である。最初の素数、２のべき乗＋１は、５、１７及び２５７である。そのうち、５ではディスクアレイが最大で４台のデータディスクしか持てないので、多くの場合小さすぎるであろう。しかしながら、１７と２５７はいずれも良い選択である。その理由は、大抵のストレージシステムはディスクストレージをブロックに分割しており、１ブロックが２のべき乗の大きさ、典型的には４ｋ（４０９６）バイト、８ｋ（８１９２）バイト、あるいは同様に２の何らかのべき乗の大きさであるからである。ｐ＝１７またはｐ＝２５７にすると、対角パリティは１６行または２５６行のグループ内で計算され、アレイ内には、最大１５または２５５台のデータディスクがそれぞれ保持される。これらの選択はいずれもデータブロックを均等に分割することができ、例えば４ｋバイトの大きさのブロックを、４ｋ／１６＝２５６バイトまたは４ｋ／２５６＝１６バイトにそれぞれ分割できるので、妥当な選択である。対角パリティは、サブブロックに沿って対角を定義することにより、計算される。行パリティは、対角パリティを持たないＲＡＩＤ−４またはＲＡＩＤ−５アレイで計算するのとちょうど同じ方法で、例えば４ｋブロック全体に対してパリティを計算することにより、計算することができる。
【００７０】
各ディスクブロックは対角パリティ集合計算の目的で１６または２５６個のサブブロックに均等に分割することができるが、ソフトウェアまたはハードウェアによるこの方法の実施形態は、例示的実施形態として、４ｋ対角パリティに重なることがない１つ又は２つの連続した４ｋブロックの領域であって、各々が１以上のサブブロックからなる４ｋブロックの領域のＸＯＲが必要である。これらのデータブロックの内容のＸＯＲをとってシフトパターンで対角パリティブロックに入れ、抜けている対角パリティ集合に属する各データブロックのサブブロックを対角パリティブロックから除外する。対角パリティデータを対角パリティブロックに加算するための総計算時間は、データブロックを行パリティブロックに加算するための計算時間に匹敵する。
【００７１】
有利なことに、本発明は、例えば、すべてのパリティ情報がディスク等の２つの装置に記憶されるＲＡＩＤ−４スタイルの集中パリティフォーマットにおいて、２重ディスク故障パリティ保護を提供する。従って、本発明の技術によると、データディスクを再フォーマットしたり既存のパリティ情報を再計算したりすることなく、データディスクをディスクアレイに徐々に追加してゆくこと可能になる。本発明は、最小量の冗長ディスク空間、即ち、１アレイ当たりちょうど２台のディスクしか利用しない。また、本発明は、ＥＶＥＮＯＤＤ等の従来技術のアプローチに比べて、所与のデータディスク数について、パリティ計算のオーバヘッドも低減している。
【００７２】
上記の説明は、本発明の特定の実施形態に関して行なっている。しかしながら、説明した実施形態に対して他の様々な変更及び修正を行い、本発明の利点のうちのいくらかまたは全部を得ることも可能であることは明らかである。従って、付記した請求の範囲の目的は、かかる変更及び修正が本発明の真の思想及び範囲に入るようにすることである。
【図面の簡単な説明】
【図１】従来のＥＶＥＮＯＤＤパリティ配置に従って構成された従来技術のディスクアレイを示す略ブロック図である。
【図２】本発明に有利に用いられる、ストレージシステムを含む環境を示す略ブロック図である。
【図３】本発明の行−対角（Ｒ−Ｄ）パリティ技術を含むステップシーケンスを示すフロー図である。
【図４】新規のＲ−Ｄパリティ技術に従って攻勢されたディスクアレイを示すブロック図である。
【図５】本発明によるＲＤパリティ技術の復元処理に必要なステップのシーケンスを示すフロー図である。
【図６】本発明に有利に用いられるストレージオペレーティングシステムを示す略ブロック図である。
【図１】
0004823468.tif 000004
【図２】
0004823468.tif 000005
【図３】
0004823468.tif 000006
【図４】
0004823468.tif 000007
【図５】
0004823468.tif 000008
【図６】
0004823468.tif 000009