(57)【要約】アレイの複数のディスクにわたってパリティを分散させる準静的分散技術。この技術によれば、ディスクのストライプ間でパリティブロックの固定パターンが維持されるようなやり方で、アレイの複数のディスクにわたってパリティが分散される（割り当てられる）。１以上のディスクをアレイに追加する場合、準静的技術は、パリティの再計算やデータブロックの移動が何も必要ないようなやり方で、パリティを再分散させる。特に、パリティ情報は実際には移動されない。この技術は、新たに追加したディスクに対する各既存のディスクのパリティブロックの一部の割り当て（又は予約）を変更するだけで足りる。
2007516524.tif 000002
【特許請求の範囲】
【請求項１】
ディスクアレイ全体にわたってパリティを分散させる方法であって、
アレイの既存のディスクに新たなディスクを追加するステップと、
各ディスクをブロックに分割し、各ストライプが各ディスクから１つのブロックを含むように、前記ブロックをストライプに編成するステップと、
データを有するブロックの再計算や移動を何も行うことなく、新たなディスク及び既存のディスクのブロック間にパリティを分散させるステップと
からなる方法。
【請求項２】
前記分散させるステップは、前記ディスクのストライプ間でパリティブロックの固定パターンが維持されるようなやり方で、前記新たなディスク及び前記既存のディスクのブロック間でパリティを分散させるステップを含む、請求項１に記載の方法。
【請求項３】
前記分散させるステップは、前記新たに追加されたディスクに対する各既存のディスクのパリティを有している１以上のブロックの割当てを変更するステップを含む、請求項１に記載の方法。
【請求項４】
前記追加するステップは、前記ストライプのパリティに影響を与えないように、前記追加されるディスクを初期化するステップを含む、請求項２に記載の方法。
【請求項５】
前記初期化するステップは、パリティの計算や書き込みをすることなく、特定ストライプ内のパリティを含むブロックを再割当てするステップを含む、請求項４に記載の方法。
【請求項６】
前記特定ストライプは前記ストライプのうちの１／Ｎからなり、該Ｎは前記アレイ内のディスク数に等しい、請求項５に記載の方法。
【請求項７】
前記再割当てするステップは、パリティを含むブロック（パリティブロック）をデータを含むブロック（データブロック）に変更するステップを含み、データブロックをパリティブロックに変更することはない、請求項５に記載の方法。
【請求項８】
前記分散させるステップは、各既存のディスクからのパリティを含むＮ個のブロック（パリティブロック）のうちの１つを前記追加されたディスクに再割当てするステップを含み、該Ｎは前記アレイ内のディスク数に等しい、請求項１に記載の方法。
【請求項９】
前記再割当てするステップは、各既存のディスクに前記アレイ内の前記パリティブロックのうちの１／Ｎを保持し続けながら、Ｎ個のパリティブロックのうちの１つを前記新たなディスクに再割当てするステップを含む、請求項８に記載の方法。
【請求項１０】
ストレージシステムの複数のディスクにわたってパリティを分散させるように構成されたシステムであって、
複数の既存のディスク及び少なくとも１つの新たなディスクを含むディスクアレイと、
前記ディスクにわたってストライプのブロックにおけるパリティを計算し、故障により失われたディスクのブロックを復元するように構成され、データブロックの再計算や移動を何も行うことなく、前記新たなディスク及び前記既存のディスクのブロック間で前記パリティを割当てるように更に構成されたストレージモジュールと
からなるシステム。
【請求項１１】
前記ディスクアレイの既知のグループサイズと前記アレイの最大グループサイズのうちのいずれか一方について計算されたパリティ割当てを記憶するように構成されたテーブルを更に含み、前記記憶されたパリティ割当ては、前記アレイにおける任意のディスク上のパリティ記憶の位置の判定に使用されるパリティ分散パターンの反復間隔を定義する、請求項１０に記載のシステム。
【請求項１２】
前記ストレージシステムは、前記ストレージシステムのＲＡＩＤシステムとして実施される、請求項１０に記載のシステム。
【請求項１３】
前記ストレージモジュールは、前記ストレージシステムの内部ディスクアレイコントローラとして実施される、請求項１０に記載のシステム。
【請求項１４】
前記ストレージモジュールは、前記ストレージシステムに外部接続されたディスクアレイ制御システムとして実施される、請求項１０に記載のシステム。
【請求項１５】
前記ディスクアレイはブロックベースのＲＡＩＤアレイである、請求項１０に記載のシステム。
【請求項１６】
システムの複数のコンテナにわたって物資を分散させる方法であって、
前記システムの既存のコンテナに新たなコンテナを追加することにより、Ｎ個のコンテナを提供するステップと、
前記物資のうちの１／Ｎを前記新たなコンテナに移動させるステップと
からなる方法。
【請求項１７】
前記システムはストレージシステムであり、前記物資はアレイのストレージデバイス上に記憶されるように構成されたデータ構造であり、前記コンテナは、前記アレイに接続されたストレージエンティティである、請求項１６に記載の方法。
【請求項１８】
前記ストレージエンティティはストレージヘッドである、請求項１７に記載の方法。
【請求項１９】
前記データ構造はｉｎｏｄｅファイルブロックである、請求項１７に記載の方法。
【請求項２０】
ディスクアレイ全体にわたってパリティを分散させる装置であって、
アレイの既存のディスクに新たなディスクを追加する手段と、
各ディスクをブロックに分割し、各ストライプが各ディスクからの１つのブロックを含むように、前記ブロックをストライプに編成するステップと、
データを含むブロックの再計算や移動を何も行うことなく、前記新たなディスク及び前記既存のディスクのブロック間でパリティを分散させる手段と
からなる装置。
【請求項２１】
ディスクアレイ全体にわたってパリティを分散させるための実行可能プログラム命令を有するコンピュータ読取可能媒体であって、前記実行可能命令が、
アレイの既存のディスクに新たなディスクを追加し、
各ディスクをブロックに分割し、各ストライプが各ディスクから１つのブロックを含むように、前記ブロックをストライプに編成し、
データを有するブロックの再計算や移動を何も行うことなく、前記新たなディスク及び前記既存のディスクのブロックでパリティを分散させるための１以上のプログラム命令を含む、コンピュータ読取可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
本発明はストレージシステムに関し、詳しくは、ストレージアレイのストレージデバイス内でパリティブロックを効率的に割り当てるシステムに関する。
【背景技術】
【０００２】
発明の背景
ストレージシステムは一般に、１以上のストレージデバイスからなり、その中に情報を入れたり、必要に応じてそこから情報を取り出したりする。ストレージシステムは、とりわけ、システムによって実施されるストレージサービスを支援する記憶処理を実施することによりシステムを機能的に編成するストレージオペレーティングシステムを有する。ストレージシステムは、限定はしないが、ネットワーク・アタッチド・ストレージ環境、ストレージ・エリア・ネットワーク、及び、クライアントコンピュータやホストコンピュータに直接取り付けられたディスクアセンブリのような種々のストレージアーキテクチャに従って実施される。ストレージデバイスとは一般に、ディスクアレイとして編成されたディスクドライブであり、その場合、「ディスク」という用語は一般に、内蔵型回転磁気媒体ストレージデバイスを言う。この文脈におけるディスクという用語は、ハードディスクドライブ（ＨＤＤ）やダイレクト・アクセス・ストレージ・デバイス（ＤＡＳＤ）と同義である。
【０００３】
ディスクアレイにおける情報の記憶は、ディスク空間の全体的論理配置を規定する、複数の物理的ディスクの集まりからなる１以上のストレージ「ボリューム」として実施されることが好ましい。ボリューム内のディスクは通常、１以上のクループに編成され、各グループは、ＲＡＩＤ(Redundant Array of Independent (or Inexpensive) Disks)として動作する。この文脈において、ＲＡＩＤグループとは、それらのディスクに関連する多数のディスク、及び、アドレス／ブロック空間として定義される。「ＲＡＩＤ」という用語及びその種々の実施形態は既知のものであり、「A Case for Redundant Arrays of Inexpensive Disks (RAID)」、D. A. Patterson、 G. A. Gibson、及び、R.H. Katz著、Proceedings of the International Conference on Management of Data (SIGMOD)、１９９８年６月、に開示されている。
【０００４】
ストレージシステムのストレージオペレーティングシステムは、情報をディレクトリ、ファイル、及び、ブロックの階層構造としてディスク上に論理編成するためのファイルシステムを実施する場合がある。例えば、「ディスク上」の各ファイルは、そのファイルの実際のデータのような情報を記憶するように構成されたデータ構造、すなわちディスクブロックのセットとして実施される場合がある。ストレージオペレーティングシステムは、書き込み処理や読み出し処理に従ってディスクに対する情報の記憶や読み出しを管理するＲＡＩＤシステムを更に実施する場合がある。例えばディスク番号空間においてディスク上に記憶される情報と、例えばボリュームブロック番号空間においてファイルシステムによって編成される情報との間には通常、一対一のマッピングが存在する。
【０００５】
ファイルシステムの一般的タイプは、「定位置書き込み型」ファイルシステムであり、その一例は、従来のバークレイ・ファースト・ファイルシステムである。定位置書き込み型ファイルシステムでは、ディスク上のデータブロックのようなデータ構造の位置が一般に固定されている。データブロックに対する変更は「定位置」で行われる。ファイルの更新によってそのファイルのデータ量が増大する場合、更なるデータブロックが割り当てられる。ファイルシステムの他のタイプは、ディスク上のデータを上書きしないWrite-anywhereファイルシステムである。ディスク上のデータブロックをディスクからストレージシステムのメモリに取り出し（読み出し）、新たなデータで「汚す」と、そのデータブロックは、ディスク上の新たな場所に記憶され（書き込まれ）、それによって書き込み性能が最適化される。Write-anywhereファイルシステムは、ディスク上にデータが実質的に連続的に配置されるような最適レイアウトを最初に想定している。この最適ディスクレイアウトによって、効率的なアクセス処理が可能となり、特に、ディスクに対するシーケンシャル読み出し処理の場合に効率的なアクセス処理が可能になる。ストレージオペレーティングシステム上で動作するWrite-anywhereファイルシステムの一例は、カリフォルニア州サニーベイルにあるネットワーク・アプライアンス・インコーポレイテッドから市販されているWrite Anywhere File Layout(「WAFL」)である。
【０００６】
大抵のＲＡＩＤ実施形態は、ＲＡＩＤグループ内の所与の数の物理的ディスクにわたってデータを「ストライプ」状に冗長書き込みし、そのストライプ状のデータに関する冗長情報を適宜記憶することにより、データ記憶の信頼性／完全性を向上させている。例えば、パリティ情報のような冗長情報によれば、ディスク故障時のデータ損失からの復元が可能になる。パリティ値は、種々のデータを有する複数の同様のディスクにわたる特定ワードサイズのデータ（通常は１ビット）の合計（通常はモジューロ２で）として計算され、その結果が、別の同様のディスクに記憶される。つまり、パリティは、各ディスク上の対応する部分にある複数のビットからなる１ビット幅のベクトルに基づいて計算される場合がある。１ビット幅ベクトルに基づいて計算される場合、計算された合計とその補数は、いずれもパリティとして使用することができる。それらはそれぞれ、偶数パリティ及び奇数パリティと呼ばれる。１ビットベクトルに基づく加算及び減算は、いずれも排他的論理和（ＸＯＲ）論理演算と等価である。そして、そのデータは、いずれか１つのディスクの損失、又は、いずれか１つのディスク上のいずれかの部分の損失に対する保護を提供する。パリティを記憶しているディスクが失われた場合、そのパリティはデータから復元することができる。データディスクのうちの１つが失われた場合、そのデータは、残ったディスクの内容を加算し、その結果を記憶されたパリティから減算することによって復元することができる。
【０００７】
一般に、ディスクは複数のパリティグループに分割され、各パリティグループは１以上のデータディスク及び１つのパリティディスクから構成される。パリティセットは、複数のデータブロックと１つのパリティブロックからなるブロックのセットであり、パリティブロックは、全てのデータブロックのＸＯＲをとったものに等しい。パリティグループはディスクのセットであり、その中から１以上のパリティセットが選択される。ディスク空間は複数のストライプに分割され、各ストライプは各ディスクから１つのブロックを含む。ストライプのブロックは通常、パリティグループにおける各ディスク上の同じ位置にある。ストライプ内で、１つのブロックを除く全てのブロック（「データブロック」）はデータを保持する一方、１つのブロック（「パリティブロック」）は全てのデータのＸＯＲをとることによって算出されたパリティを保持する。
【０００８】
本明細書に記載するように、「エンコーディング」という用語は、データブロックの所定のサブセットにわたる冗長性値の計算を意味し、「デコーディング」という用語は、データブロックのサブセット及び冗長性値を使用した冗長性計算と同じプロセスによるデータブロックやパリティブロックの復元を意味する。パリティグループ内の一台のディスクが故障した場合、そのディスクの内容は、残りのデータブロックの内容を全て加算し、その結果をパリティブロックから減算することによって、１以上の予備ディスク上にデコード（復元）することができる。１ビットフィールドにおける２の補数の加算と減算はいずれも、ＸＯＲ演算と等価であるため、復元は、生き残った全てのデータブロックとパリティブロックのＸＯＲを計算することからなる。同様に、パリティディスクが失われた場合、そのパリティディスクは、生き残ったデータから同じ方法で再計算することができる。
【０００９】
パリティブロックを全て１つのディスクに記憶し、全部がパリティ情報の（すなわち、パリティ情報だけしか持たない）単一のディスクを構成する場合、ＲＡＩＤ４レベル実施形態が形成される。ＲＡＩＤ４実施形態は、パリティ情報の位置を各ＲＡＩＤグループにおいて固定しているので、事実上、先進的ＲＡＩＤ（すなわち、ストライピングやミラーリングを超える）の最も単純な形である。特に、ＲＡＩＤ４実施形態によれば、ディスクを一台追加するだけで、一台のディスク故障からの保護を提供でき、データディスクを１台づつＲＡＩＤグループに追加することも簡単である。
【００１０】
各ストリップにおいてパリティブロックが異なるディスクに、回転パターンで保持される場合、その実施形態はＲＡＩＤ５である。大抵の市販の実施形態は、先進的なＲＡＩＤ技術を使用し、パリティ情報を分散させるＲＡＩＤ５レベル実施形態を使用している。ＲＡＩＤ５実施形態を選択する動機は、多くの静的ファイルシステムにとって、ＲＡＩＤ４実施形態の使用は、処理能力を制限することがあるからである。そうした静的ファイルシステムは、ディスクアレイ上の多数のストライプにわたって書き込みデータを分散させる性質があり、その結果、パリティディスクは書き込まれた各ストライプを探すことになる。ただし、WAFLファイルシステムのようなWrite-anywhereファイルシステムは、書き込みデータを少数の隣接ストライプ上に集中させるので、そのような問題がない。
【００１１】
Write-anywhereファイルシステムにおいてＲＡＩＤ４レベル実施形態を使用することは、パフォーマンスを維持しつつ、容量をインクリメンタルに増加させることが可能な１つの望ましい方法である。しかしながら、「目に見えない」不利な面も幾らかある。第１に、ＲＡＩＤグループ内のディスクが全て、ＲＡＩＤ５実施形態における読み出しトラフィックのサービスに利用可能である場合、ディスクの１つ（パリティディスク）は、ＲＡＩＤ４実施形態におけるそのようなトラフィックに参加しない。ＲＡＩＤグループサイズが大きい場合、その影響は取るに足らないものであるが、例えば利用可能なディスク数が限られるとか、ディスクが大きくなるほど復元時間が長くなるといった理由から、そうしたＲＡＩＤグループサイズは小さくなってきている。ディスクのサイズが大きくなるほど、より小さなＲＡＩＤグループ構成が魅力的になる。ただし、その結果、ＲＡＩＤ４構成における読み出し処理を提供するのに使用できないディスクの割合は増大する。従って、ＲＡＩＤ４レベル実施形態の使用は、一秒あたりの読み出し処理の大きなロスにつながる場合がある。第２に、１つのボリュームに新たなディスクを追加した場合、Write anywhereファイルシステムは、ほとんどの書き込みトラフィックを、空き空間のほとんどが位置しているその新たなディスクに差し向ける傾向がある。
【００１２】
ＲＡＩＤシステムは一般に、ディスクアレイのＲＡＩＤ５レベル実施形態に割り当てられたデータを把握している。その目的のために、ＲＡＩＤシステムは、計算しやすく、非データ（パリティ）ブロックであることを効率的に識別可能な固定パターンでパリティブロックを予約している。しかしながら、ＲＡＩＤ５レベル実施形態のＲＡＩＤグループに新たなディスクを個々に追加するためには一般に、アレイの各ストライプにおける古いディスクと新しいディスクの間でパリティ情報を移動させ、その固定パターンを維持しなければならない。パリティ情報の移動には通常、古いディスクと新しいディスクを「一斉捜索」し、パリティブロックとデータブロックの両方が新たな分布に従っていることを確認するための複雑な（そしてコストのかかる）パリティブロック再分配スキームが必要とされる。このパリティ再分配スキームは更に、ストライプごとに、どのブロックがデータを保持しているかを識別し、割り当てられるデータブロックが多すぎず、パリティ情報のために十分な空間があることを確認しなければならない。こうしたスキームの複雑さやコストにより、大抵のＲＡＩＤ５実施形態は、ＲＡＩＤグループにディスクを個々に追加することをあきらめ、代わりに、固定ＲＡＩＤグループサイズ（通常は４〜８ディスク範囲）を使用している。そして、ディスク容量は一度に完全なＲＡＩＤグループまで増大した。しかしながら、小さなＲＡＩＤグループの使用は、高いパリティオーバヘッドとも解釈でき、より大きなＲＡＩＤグループの使用は、容量をインクリメンタルに増加させるためのコストが高くなることを意味する。
【００１３】
したがって、ストレージシステムにおいて、システムの複数のディスクにわたってパリティを均一に、又は、ほぼ均一に分散させるとともに、ディスクを一台づつ追加する能力を維持することが可能な分散システムを提供することが望まれている。
【００１４】
また、比較的な小さな（ＲＡＩＤグループ）構成において、ストレージシステムのWrite anywhereファイルシステムを比較的良好なパフォーマンスで動作させることが可能な分散システムを提供することも望まれている。
【発明の開示】
【課題を解決するための手段】
【００１５】
発明の概要
本発明は、アレイの複数のディスクにわたってパリティを分散させる準静的分散技術を提供することにより、従来の欠点を克服する。本技術の例示的実施形態によれば、ディスクのストライプ間でパリティブロックの固定パターンが維持されるようなやり方で、アレイの複数のディスクにわたってパリティが分散される（割り当てられる）。アレイに１以上のディスクを追加する場合、この準静的技術は、パリティの再計算や、データブロックの移動を何も必要としない方法で、パリティを再分配する。特に、パリティ情報は実際には移動されない。本技術は、新たに追加されたディスクに対する各既存のディスクのパリティブロックの一部の割り当てを変更するだけで足りる。例えば第１の既存のディスク上のパリティが記憶された既存のブロックは、パリティをそのまま記憶し続けることができる。あるいは、新たに追加されたディスク上のブロックは、ストライプのパリティを記憶するように割り当てられ、それによって、第１のディスク上の既存のパリティブロックは、ファイルシステムデータを記憶するために「解放」される。
【００１６】
有利なことに、準静的分散によれば、アレイにディスクを追加するときに、（ストライプにおいて）パリティを保持しているブロックを変更することができる。ストライプの複数のブロック間で再割当てが行われ、パリティのバランスを再びとることにより、書き込み処理の際に、圧倒的多数のパリティを有するディスクが「熱く」なること、すなわち、他のディスクよりも激しく使用されることを回避する。この新規な分散技術は、単一ディスク故障訂正に適用されるものであるが、二重（又はそれ以上の）ディスク損失保護に適用されるように拡張することも可能である。更に、この準静的分散技術は、１以上のディスクを一度にボリュームに追加する能力を維持しつつ、ディスク境界構成におけるパフォーマンスを向上させる可能性も有する。
【００１７】
本発明の上記の利点及び他の利点は、添付の図面と併せて下記の説明を読むと分かりやすいであろう。図中、同じ参照符号は、同一の要素、又は、機能的に類似の要素を示している。
【発明を実施するための最良の形態】
【００１８】
例示的実施形態の詳細な説明
図１は、本発明と共に使用するのに都合がよいストレージシステム１００を示す略ブロック図である。図示の実施形態において、ストレージシステム１００は、システムバス１２５によって相互接続されたプロセッサ１２２、メモリ１２４、及び、ストレージアダプタ１２８を含む。メモリ１２４は、本発明に関連するソフトウェアプログラムコードやデータ構造を記憶するための、プロセッサやアダプタによってアドレス指定可能な記憶場所を有する。また、プロセッサ及びアダプタは、ソフトウェアコードを実行し、データ構造を操作するように構成された処理要素、及び／又は、論理回路を含む。当業者には明らかなように、本明細書に記載する本発明に関連するプログラム命令の記憶や実行には、種々のコンピュータ読取可能媒体を含めて、他の処理手段や他の記憶手段を使用することも可能である。
【００１９】
ストレージオペレーティングシステム１５０は、通常その一部がメモリに常駐し、処理要素によって実行され、とりわけ、ストレージシステムによって実行されるストレージオペレーションを実行することによりファイルシステム１００を機能的に編成する。ストレージオペレーティングシステムは、情報をディレクトリ、ファイル、及び、ブロックの階層構造としてアレイのディスク上に論理編成するための上位モジュールを実行する。また、ストレージオペレーティングシステム１５０は、書き込み処理及び読み出し処理に従ってディスクに対する情報の記憶及び読み出しを管理するストレージモジュールも実行する。なお、上位モジュール及びストレージモジュールは、ソフトウェアで実施しても、ハードウェアで実施しても、ファームウェアで実施しても、それらの組み合わせで実施してもよい。
【００２０】
具体的には、上位モジュールは、ファイルシステム１６０、又は、ディスクアレイの記憶空間の割り当てを行い、アレイ上のデータのレイアウトを管理するデータベースのような他のモジュールからなる。また、ストレージモジュールは、冗長記憶アルゴリズムを使用して冗長（例えば、パリティ）情報を計算したり、ディスク故障からの復旧を行うように構成されたディスクアレイ制御システム、又は、ＲＡＩＤシステム１７０からなる。ディスクアレイ制御システム（「ディスクアレイコントローラ」）又はＲＡＩＤシステムは、アレイ上に固定データが置かれるのに応じて、代数的及びアルゴリズム的な計算を使用して、その冗長情報の計算を更に行う場合がある。なお、「ＲＡＩＤシステム」という用語は、「ディスクアレイ制御システム」や「ディスクアレイコントローラ」と同義であり、従って、「ＲＡＩＤシステム」という用語の使用は、既知のＲＡＩＤ技術のうちの１つを使用することを意味しているのではない。むしろ、本発明のＲＡＩＤシステムは、本発明による準静的パリティ分散技術を使用する。本明細書に記載されるように、ファイルシステム又はデータベースは、アレイ上にデータが置かれる場所に関する判定を行い、その判定結果をＲＡＩＤシステムに転送する。
【００２１】
図示の実施形態において、ストレージオペレーティングシステムは、カリフォルニア州サニーベイルにあるネットワーク・アプライアンス・インコーポレイテッドから市販されているNetApp Data ONTAPオペレーティングシステムであることが好ましく、このオペレーティングシステムは、例えば４キロバイト（ｋＢ）のＷＡＦＬブロックを使用したブロックベースのディスク上フォーマット表現を有するWrite Anywhere File Layout(WAFL)ファイルシステムを実施する。ただし、当然ながら、例えば定位置書き込み型ファイルシステムのような任意の適当なストレージオペレーティングシステムを、本明細書に記載する本発明の原理に従って使用するように拡張してもよいものと考えられる。従って、「ＷＡＦＬ」という用語を使用した場合でも、それは、本発明の教示に適合する任意のストレージオペレーティングシステムを含むものとして広く解釈しなければならない。
【００２２】
本明細書で使用されるように、「ストレージオペレーティングシステム」という用語は一般に、ストレージシステムにおけるストレージ機能を実施するためのコンピュータ実行可能コードを意味し、例えばファイルセマンティックを管理し、ファイルサーバの場合、ファイルシステムセマンティックを実施し、データアクセスを管理するコンピュータ実行可能コードを意味する。その意味で、ＯＮＴＡＰソフトウェアは、マイクロカーネルとして実施され、ＷＡＦＬファイルシステムセマンティックを実施し、データアクセスを管理するためのＷＡＦＬ層を含むそのようなストレージオペレーティングシステムの一例である。ストレージオペレーティングシステムは、ＵＮＩＸやＷｉｎｄｏｗｓ(R)  ＮＴのような汎用オペレーティングシステム上で動作するアプリケーションプログラムとして実施することができ、また、本明細書に記載するストレージアプリケーションで使用するために構成された設定可能な機能を有する汎用オペレーティングシステムとして実施することもできる。
【００２３】
ストレージアダプタ１２８は、ストレージシステム１００上で実行されるストレージオペレーティングシステム１５０と協働し、ユーザ（又は、クライアント）から要求された情報にアクセスする。情報は、ビデオテープ、光学、ＤＶＤ、磁気テープ、バブルメモリ、電気的ランダムアクセスメモリ、微小電気機械、及び、データとパリティ情報を含む情報を記憶するように構成された任意の他の同様の媒体といった、任意のタイプの書き込み可能な記憶装置媒体の付属アレイに記憶される場合がある。ただし、本明細書において例示するように、情報は、ＨＤＤ、及び／又は、ＤＡＳＤのような、アレイ２００のディスク上に記憶することが好ましい。ストレージアダプタは、従来の高性能ファイバチャネル・シリアルリンク・トポロジのようなＩ／Ｏ相互接続構成を介してディスクに接続された入出力（Ｉ／Ｏ）インタフェース回路を含む。
【００２４】
アレイ２００上での情報の記憶は、全体を１３０で示す物理的ストレージディスクの集まりから構成された、ディスク空間の全体的論理配置を規定する１以上のストレージ「ボリューム」（例えば、ＶＯＬ１−２  １４０）として実施されることが好ましい。各ボリュームは一般に、必須ではないが、独自のファイルシステムに関連する。ボリューム／ファイルシステム内のディスクは通常、１以上のグループとして編成され、各グループはＲＡＩＤグループに似ている。大抵のＲＡＩＤ実施形態は、ＲＡＩＤグループ内の所与の数の物理的ディスクにわたってデータを「ストライプ」状に冗長書き込みし、そのストライプ状のデータに関するパリティ情報を適宜記憶することにより、データ記憶の信頼性／完全性を向上させている。
【００２５】
具体的には、各ボリューム１４０は物理的ディスクのアレイから構成され、物理的ディスクは複数のブロックに分割され、ブロックはストライプに編成されている。ディスクは、グループ１３２、１３４及び１３６として編成される。それらのグループはＲＡＩＤグループに似ているが、各グループの中では、本明細書に記載する準静的分散技術が使用される。各グループにおける各ストライプは、そのグループに要求される故障許容度に応じて、１以上のパリティブロックを有する。各ストライプにおいてパリティが記憶されるブロック（複数の場合もあり）の選択は、ＲＡＩＤ構成によって決まるのではなく、従来のＲＡＩＤ４アレイやＲＡＩＤ５アレイにおけるようなものであることが望ましい。
【００２６】
本発明は、アレイの複数のディスクにわたってパリティを分散させる準静的分散技術に関する。本発明の技術は、とりわけ、本明細書に記載するように複数のディスクにわたってストライプごとにパリティを計算し、パリティをそれらのストライプ間に分散させ、故障により失われたディスクを復元するＲＡＩＤシステム１７０によって実施されることが好ましい。準静的分散技術は、ファイルシステム１６０の関与を必要としないので、ストレージシステム１００の内部や外部に接続されることがある例えばＲＡＩＤコントローラとして実施されるＲＡＩＤコードに配備するのにも適している。
【００２７】
この技術によれば、ディスクのストライプ間におけるパリティブロックの固定パターンが維持されるようなやり方で、パリティがアレイの複数のディスクにわたって分散される（割り当てられる）。アレイに１以上のディスクを追加する場合、準静的技術は、パリティの再計算や、データブロックの移動を何も必要としないようなやり方で、パリティを再分散させる。特に、パリティ情報は実際には移動されない。この技術は、新たに追加したディスクに対する各既存のディスクのパリティブロックの一部の割り当て（又は、予約）を単に変更するだけで足りる。例えば、第１の既存のディスク上のパリティが記憶された既存のブロックはパリティをそのまま記憶し続けることができる。あるいは、新たに追加されたディスク上のブロックは、ストライプのパリティを記憶するように割り当てられ、それによって、第１のディスク上の既存のパリティブロックは、ファイルシステムデータを記憶するために「解放」される。なお、ファイルシステムへの参照が、データベースのような他の上位モジュールによって生成されたデータの邪魔になることはない。
【００２８】
アレイ２００の複数のディスクにわたってデータが密集して割り当てられるものと仮定した場合、ストレージオペレーティングシステム１５０は、それらのディスクにわたってパリティを固定パターンで均一に割り当てることを選択する場合がある。しかしながら、アレイに１以上のディスクを追加した場合、その固定パターンは変化する。これに応じて、準静的分散技術は、ディスクのストライプ間のパリティブロックの固定パターンが維持されるようなやり方で、パリティを再分散させる（再割り当てする）。なお、新たに追加される各ディスクは、ストライプの固定パリティに影響を与えることがないように、例えば、ゼロのような所定の固定値に初期化される。また、パリティ値が既知（所定の値）である限り、その固定パリティは偶数であってもよいし、奇数であってもよい。本明細書における下記の説明は、偶数パリティに関するものである。また、新たに追加されるディスクを初期化することにより、パリティの計算や書き込みを必要とせずに、一部のストライプ（例えば、ストライプのうちの１／Ｎ、ただしＮはディスク数）におけるパリティブロックをその新たなディスクに再割り当てすることができる。
【００２９】
本発明によれば、再割当てアルゴリズムは、常にパリティブロックをデータブロックに変更するだけであり、データブロックをパリティブロックに変更することは絶対にない。例えば、新たな第Ｎのディスクをグループ１３２〜１３６に追加することに応じて、ファイルシステム１６０は、各既存のディスクのあらゆる第Ｎのパリティブロックをその新たなディスクに再割り当てすることができる。新たなディスクは空きブロックとパリティブロックしか有していないので、そのような再割り当ては、再計算やデータの移動を何も必要としない。そのため、既存のパリティブロックをデータの使用に再割当てすることは可能であるが、その逆は出来ない。この再割当て（構築）アルゴリズムは、各グループサイズについて一意に決まるパリティのパターンを形成し、そのグループ内の全てのディスク間にパリティを均一に分散させる。
【００３０】
図２は、本発明の準静的分散技術によるパリティ割り当てを例示するためのディスクアレイ２００を示すブロック図である。アレイ２００は最初に１つのディスク２０２を含み、そのディスクが冗長（パリティ）情報を記憶していることが望ましく、したがって、そのディスク上の各ブロックがパリティ（Ｐ）情報を記憶しているものと仮定する。アレイを拡張するために第２のブロック２０４を追加する場合、パリティブロックは２つのディスク間に分散される場合がある。同様に、その後、その拡張されたアレイに第３のディスク２０６及び第４のディスク２０８を追加する場合、パリティブロックはそれらのディスク間で分散される場合がある。アレイ２００にディスクを追加する際に、ファイルシステムデータが記憶されているブロックにパリティが記憶されることはない。準静的分散技術は、パリティブロックの再割当てだけを目的としたものであり、それによって、データに使用されるブロックが解放される。換言すれば、この技術は、データブロックの再割当ては絶対に行わない。この点が、従来のＲＡＩＤ５レベル実施形態の拡張とは対照的である。
【００３１】
各既存のディスクからＮ個のパリティブロックのうちの１つを新たなディスクに再割り当てする本発明の技術の構築アルゴリズムによれば、パリティは複数のディスクにわたって分散される。ここで、Ｎは、拡張されたアレイにおけるディスク数に等しい。概して、Ｎ個のパリティブロックのうちの１つが新たなディスクに再割当てされ、各既存のディスクは、拡張されたアレイにおけるパリティブロックのうちのちょうど１／Ｎを保持し続ける。２ディスクアレイの場合、第１のディスク２０２上の１つ置きのパリティブロックが、第２のディスク２０４へ移動される。拡張されたアレイ２００に第３のディスク２０６を追加し、それによって３ディスクアレイを形成する場合、第１のディスク２０２上の２つ置きの残りのパリティブロック、並びに、第２のディスク２０４上の２つ置きのパリティブロックが、第３のディスク２０６へ移動される。そのアレイに第４のディスク２０８を追加し、４ディスクアレイを形成する場合、各ディスク（ディスク１〜３）上の残りの３つ置きのパリティブロックが、第４のディスク２０８へ移動される。この再割当ての結果、各ディスク上のパリティの量は実質的に同じになる。また、アレイの複数のディスクにわたってストライプごとに、パリティブロックの位置が、予測可能な決定的パターンで変更される。
【００３２】
図３は、本発明の準静的分散技術の一実施形態による、アレイのディスク間でパリティを分散させるための一連のステップを示すフロー図である。ここで、上記のように、新たな第Ｎのディスクをアレイのグループ１３２〜１３６に追加すると、４個に１つのパリティブロックがその新たなディスクに割り当てられる。ただし、Ｎは、アレイ内のディスク数に等しい。上記のように、ディスク間でパリティ情報を実際に移動させる必要はない。本発明の準静的分散技術は、新たに追加されたディスク上の各パリティブロックの割り当て（又は、予約）を単に変更することを想定している。
【００３３】
シーケンスはステップ３００から始まり、ステップ３０２へ進み、そこで、アレイ内のＮ個のディスクのグループに新たなディスクを追加する。ステップ３０４では、その新たなディスクを初期化（例えば、ゼロ化）し、各ストライプ上のブロックのパリティが影響を受けないことを確認する。ストライプ内には、データを保持していないブロックであって、パリティを記憶できる可能性を有するブロック（すなわち、未割り当てのデータブロック）が複数存在する。ストライプは、少なくとも１つの未割り当てブロック（これはパリティブロック）と、１以上の空のデータブロックとを含むであろう。全てのブロックが例えば、偶数パリティに貢献し、その結果、パリティロック（複数の場合もあり）と空のデータブロックは全て等価になる。ファイルシステム（ファイルシステムが無い場合は、上位モジュール）は、データをストライプに書き込むための書き込み要求に応答して、ストライプ内においてどのディスクが空きブロックを保持しているかを判定する。ステップ３０６において、ファイルシステム１６０は、冗長記憶アルゴリズムによる要求に従って、適宜、パリティを記憶するための空きブロックを出来る限り多く確保する。例えば、第１の既存のディスク上のパリティが記憶された既存のブロックは、パリティをそのまま記憶し続けることができる。あるいは、新たに追加されたディスク上のブロックは、ストライプのパリティを記憶するように割り当てられ、それによって、第１のディスク上の既存のパリティブロックは、ファイルシステムデータを記憶するために「解放」される。
【００３４】
２以上のディスク故障に対する保護を提供するパリティアルゴリズムは、それがストライプ内の任意の２（以上）のブロックにパリティを記憶できるものである限り、どのようなアルゴリズムであっても、準静的分散技術とともに使用することができる。本発明と共に使用するのに都合がよい二重故障訂正アルゴリズムの一例は、「Uniform and Symmetric Double Failure Correcting Technique for Protecting against Two Disk Failures in a Disk Array」と題するPeter F. Corbett他による米国特許出願第（112056-0141）号に記載されている一様で対称な行−対角（ＳＲＤ）パリティである。ただし、本発明の技術は、このパリティアルゴリズムの一様性又は対称性に依存するものではなく、その利点を利用している。準静的分散技術とともに二重故障訂正アルゴリズムを使用した場合、ファイルシステムは、パリティを記憶するために、２つの未割り当てのデータブロックを予約する。パリティブロックの位置が確定的に分かっているので、一様でない二重（又はそれ以上）故障訂正アルゴリズムを使用することもできる。ただし、そのようなアルゴリズムの使用した場合、アレイにディスクを追加したときにパリティを再計算する必要がないという利点は犠牲になる。
【００３５】
他の技術は、データブロックがアレイの任意のブロックに書き込まれるような一様でないアルゴリズムを使用することである。ただし、それらは一般に、冗長情報の記憶に使用することが望ましい。複数故障訂正アルゴリズムは任意の失われたディスクの内容を復元することができるので、たとえそれらが失われたデータブロックの復元を通常目的とする技術を使用して構築されたとしても、残りのブロックを使用して冗長情報を記憶することができる。この方法において一様でないアルゴリズムを使用した場合、ＳＲＤのような一様で対称なアルゴリズムを使用した場合に比べて、実施形態は非常に複雑になる場合がある。
【００３６】
ステップ３０８において、ファイルシステムの書き込みアロケータ１６５は、ストライプ内のディスクに記憶するための書き込みデータを編成する。ステップ３１０において、ファイルシステムは、ファイルシステムによって発行される書き込み要求メッセージにより、予約ブロック（複数の場合もあり）の指示をＲＡＩＤシステム（ストレージモジュール）に提供する。ステップ３１２において、ＲＡＩＤシステムは、ディスクに記憶するためのパリティ情報（及び、書き込みデータ）をディスクドライバシステムに提供する。特に、ステップ３１４において、パリティはディスクのブロック間に分散され、パリティブロックのうちの１／Ｎが各ディスクに記憶され、それによって、アレイのディスク全体にわたってデータのバランスが保証される。また、アレイのストライプ間において、パリティブロックの位置が、複雑ではあるが計算の簡単な予測可能なパターンで「移動」される。そして、シーケンスはステップ３１６で終了する。
【００３７】
１ストライプあたり２つの冗長ブロックを有する二重故障訂正アレイにおいて冗長ブロックまたはパリティブロックのバランスのとれた準静的分散を実現することが可能な他の技術として、単一故障訂正準静的アレイにおける各１つのディスクを二重故障訂正アレイにおける一対のディスクで置き換えるという技術がある。ここで、ディスクの各対の役割は、単一故障訂正アレイにおける１つのディスクに対応する。単一故障訂正アレイにおいて使用されるものと同数の行を使用してバランスが維持されるが、この技術は、アレイに追加できるディスクの数が２の倍数に制限される。
【００３８】
更に他の技術として、パリティブロックで完全に満たされた２つの初期（「古い」）ディスクから開始し、第３のディスクを追加し、２つの初期ディスクのそれぞれから２つ置きにパリティブロックを新たなディスクに移動させることにより、バランスの取れた、又は、ほぼバランスのとれたアレイを構築するものがある。この技術は、各ディスク上の空間の三分の二を占めるように、パリティブロックの三分の一を各ディスクに分散させる。古いディスクからのパリティブロックを再割り当てする場合、新たなディスク上のそのブロックが既にパリティとして指定されていることが判明する場合がある。その場合、古いディスクから次の使用可能なパリティブロックを新たなディスクに割り当てる。その場合、そのパリティブロックは、新たなディスクがまだパリティを有していない次の行であって、古いディスクがパリティを有している行に割り当てられる。
【００３９】
後者の技術は、１ストライプあたり２つの冗長（例えば、パリティ）ブロックを有し、アレイ全体にわたってバランスのとれた、又は、ほぼバランスのとれた冗長ブロックを有する、任意数のディスクに対するパリティ割り当ての確定的セットを構築するように更に外挿することができる。同様に、１ストライプあたり３以上の数の冗長ブロックがある場合、同じ技術を使用して、１つのディスクあたりの冗長ブロックの数がバランスのとれたものに、又は、ほぼバランスのとれたものになるようなやり方で、任意サイズのもっと大きなアレイにおける冗長ブロックの配置を決定することもできる。さらに、この技術によれば、１つのディスクあたりの冗長ブロックの数をバランスのとれたものに、又は、ほぼバランスのとれたものに維持しつつ、データブロックをパリティブロックに変更することなく、任意数のディスクを追加することが可能になる。
【００４０】
データブロックとパリティブロックの両方の分布が、バランスのとれた状態、又は、ほぼバランスのとれた状態に維持されるため、データブロックを冗長ブロックに全く変更することなく、アレイをインクリメンタルに拡張できるという性質を維持しつつ、任意サイズのアレイにおけるデータブロックや冗長ブロックのようなブロックの役割を判定するための他の同様の技術を開発することも可能である。これらの技術はいずれも、特定サイズのアレイ内の特定数の行に関する割り当てを記憶するメモリに、データ構造（例えば、テーブル）を記憶、又は、生成することによって実施することができる。また、特定限界までの任意のアレイサイズに対する冗長ブロックの可能な割り当てを全て１つのテーブルに記憶することも可能である。ここで、例えば、このテーブルは、各行についてビットマップを記憶するものであってもよく、その場合、Ｎ未満の１つ又は（それ以上）の最も大きな番号のビットセットが選択される。ただし、Ｎはアレイ内のディスク数である。データブロックを冗長（パリティ）ブロックに変更する必要のない拡張を可能にしつつ、データブロックと冗長ブロックの分散バランスを維持する、テーブルを利用したパリティ割り当てはいずれも、１行あたりの冗長ブロックの数（すなわち、アレイが許容する故障の数）とは無関係に、本発明によって考慮される。
【００４１】
準静的分散技術のためのパリティ割り当ては、ディスクアレイの既知のサイズのグループ１３２〜１３６について計算してもよいし、アレイの最大グループサイズについて計算してもよく、上記のように、計算されたパリティ割り当ては、テーブルに記憶することができる。記憶された割り当て、及び、特にパターンの反復間隔によって定義されるパリティ分散パターンを使用すると、与えられたグループサイズ、及び、ストライプに対し、アレイ内の任意のディスク上のパリティ記憶の位置を判定することができる。つまり、このパターンを使用すると、各ストライプにおいてパリティに使用されるブロックや、異なるパターンを複数のストライプに使用できることを示すことができる。
【００４２】
図４は、準静的分散技術による、種々のグループサイズに対する反復間隔を示すパリティ割り当てテーブル４００を示す図である。このパリティ分散パターンは、アレイのグループサイズによって決まる反復間隔で繰り返される。Ｋ個のストライプごとにサイズＮのグループが繰り返される場合、サイズ（Ｎ＋１）のグループが、Ｋと（Ｎ＋１）のどちらでも割れる最小数で繰り返されることになる。ただし、テーブルの内容は、ディスク数に等しい数であるＮによって決まる数（繰り返し間隔）まで繰り返されてはいない。例えば、２ディスクアレイ（すなわち、グループサイズが２）の場合、パリティ分散パターンは、２ストライプごとに繰り返される。第３のディスクを追加した（グループサイズが３の）場合、パリティパターンは６個のストライプごとに繰り返される。第４のディスクを追加した（グループサイズが４の）場合、パリティパターンは１２個のストライプごとに繰り返される。テーブル４００から、グループサイズが５である場合、パリティパターンは６０個のストライプごとに繰り返されることが分かるであろう。
【００４３】
グループサイズの関数のような反復間隔は、最大Ｎまでの独特な素数の集合に従って決定される。ただし、Ｎはディスク数に等しい数である。反復間隔（表４００のエントリ数に等しい）はＮの階乗よりも小さく、実際には、Ｎ以下の全ての素数の積に等しい。各素数は、積の結果がＮ以下になるような最大の累乗まで上げられる。１とＮの間にある数の幾つかは素数である。当然ながら、反復間隔を大きくすれば、テーブルも大きくなる。例えば、Ｎ＝１０の場合、テーブルサイズは、２＾３×３＾２×５＾１×７＾１＝８×９×５×７＝２５２０になる。同様にＮ＝３２の場合、テーブルサイズは、２＾５×３＾３×５＾２×７＾１×１１＾１×１３＾１×１７＾１×１９＾１×２３＾１×２９＾１×３１＾１＝３２×２７×２５×７×１１×１３×１７×１９×２３×２９×３１≒１４４×１０＾１２になる。
【００４４】
次に、パターンのテーブルサイズと、バランスの精度との間のトレードオフを行う。テーブルは、適当なポイントで終了することができ、その特定の反復間隔でグループサイズを使用することができる。以後、たとえグループサイズよりも多くのディスクが存在する場合でも、この技術は、そのパターンを反復し続け、それでも、例えば５０パーセント以内のアレイにわたるデータのほぼ一様なバランスを実現する。上記のように、例えばグループサイズ１０は、２５２０個のストライプごとに反復されるパリティ分散パターンに変換される。このサイズ（すなわち、２５２０エントリ）のテーブルは、メモリ１２４において比較的小型であり、始動時に適当なソフトウェアコードを使用して比較的迅速に計算することができる。これに対し、グループサイズ３２（すなわち、１４４×１０＾１２エントリ）の場合のテーブルは大きすぎてメモリに記憶することができない。
【００４５】
２５２０エントリのテーブルは、任意の適当な数のディスクと共に使用すると、良好なデータバランスが得られる。ただし、このサイズのテーブルが唯一の選択肢ではなく、他のサイズのテーブルを使用することも可能である。１０までのＮ個のディスクの場合、２５２０エントリのパターンは完璧なバランスを有する。Ｎが１０よりも大きい場合、パターンは反復されないが、このパターンは良好なデータバランスを提供する。換言すれば、１７ディスクグループの場合のパリティ割り当てテーブルは割と大きい（１つのパターンあたり５ビットとして７．７ＭＢ）が、それでも、そのテーブルの一部だけを使用すれば良好なパリティバランスを達成することができる。例えば、このパターンを２５２０のところで切断すると、最大１０ディスクまでの全てのグループサイズについては完璧なバランスが得られ、それより大きなグループに対しては１％未満のインバランスが得られ、一方、Ｎ＝１１の場合は、テーブルサイズを２５２０×４ビット＝１２６０バイトに制限し、Ｎ＝１７〜３２の場合は、５×２５２０ビット＝１５７５バイトに制限する。
【００４６】
パリティ割り当てテーブル４００は、Ｎの特定の値に対するパリティのビット位置を示す１つの番号としてエンコードすることができる。このテーブルは、単一又は二重（又はそれ以上）ディスク故障保護を提供する単一又は二重（又はそれ以上）のパリティブロックの位置を示す１つ又は２つ（又はそれ以上）のビットセットを備えた、ビットベクトルとして符号化してもよい。また、このテーブルは、（何らかの限界以下の全てのディスクアレイサイズについて）各ストライプにおいてどのディスクがパリティを有する可能性があるかを示す単一のテーブルとしてエンコードしてもよい。次に、上位３２−Ｎビットをマスクし、最上位の残りの１つ又は２つ（又はそれ以上）のビットを選択することにより、Ｎの特定の値に対し、どのディスクが実際にパリティを有するかの判定が行われる。
【００４７】
要するに、準静的分散は、アレイ全体にわたって１つのディスクあたりのデータブロック数が概ね一定になるように維持しようとし、それによって、アレイの全てのディスクにわたって読み出し負荷を「分散」させるものである。したがって、この技術によれば、アレイ内のいずれか１つのディスクのスループットが原因で生じるアレイ内の「ボトルネック」を全て無くすことができ、同時に、書き込み処理の際のホットスポット（複数の場合もあり）のようなパリティディスク（複数の場合もあり）をなくすことができる。ＳＲＤパリティのような対称なアルゴリズムや、行−対角（ＲＤ）パリティのような対称な故障訂正アルゴリズムを使用して、一般的技術を適用することができる。ＲＤパリティ技術については、２００１年１２月２８日に出願されたPeter F. Corbett他による「Row-Diagonal Parity Technique for Enabling Efficient Recovery from Failures in a Storage Array」と題する米国特許出願第１０／０３５，６０７号に記載されている。
【００４８】
ＲＤパリティのような一様でないアルゴリズムを使用する場合、非対称パリティアルゴリズムにおけるディスクの一般的役割に関して、データブロックと冗長ブロックのどちらかを何らかの特定のブロックに記憶する際のディスクの役割は無視されるかもしれない。二重故障訂正アルゴリズムはいずれも、アレイの任意の２つのディスクが失われた場合に、失われた「データ」を構築することができるため、データを記憶する役割が割り当てられた行内の全てのブロックの内容、及び、２つの冗長ブロックの内容は、二重故障訂正アルゴリズムを使用して計算される。このアルゴリズムは、行内のディスクの位置に応じて様々に使用される。各行に２つの冗長ブロックを記憶した後、アレイは２つのディスク故障を許容することができ、何らかの特定ストライプにおける失われたブロックの役割に関係なく、失われたデータ又は冗長ブロックを復元することができる。
【００４９】
あるいは、ディスクの役割が確定的に定義されるので、アレイ内の２以上のディスクに冗長情報を記憶することが可能なアルゴリズムであれば、いかなるアルゴリズムを使用してもよい。そうしたアルゴリズムを使用すると、パリティブロックを移動させるときにパリティの再計算が必要になる場合もあるが、データブロックが何も移動されないという本発明の利点は維持される。ＳＲＤは、新たに追加されたディスク（複数の場合もあり）にパリティブロック（複数の場合もあり）を割り当てるときに、パリティブロックを再計算する必要がないという更に別の利点も有している。
【００５０】
本明細書に記載した分散技術は、少数のディスクしか有していないが、それらのディスクから利用可能な一秒あたりの読み出し処理（ｏｐｓ）を全て利用することが望ましいシステムにとって、特に有用である。小さなアレイほど、そのパフォーマンスは、ディスクから達成可能なｏｐｓ（ディスク限界）によって制限される。しかしながら、ディスクを大きくした大きなアレイの場合、その復元時間が原因で、１つのグループ１３２〜１３６あたりのディスク数は減少する傾向にある。その結果、冗長性オーバヘッド（冗長性を増加させるために使用される１グループ内のディスクの割合）は増加する。従って、それらの冗長ディスクにおける利用可能な読み出しｏｐｓの利点を得ることが望ましい。分散技術のもう１つの利点は、復元、及び／又は、復旧が「盲目的に」（すなわち、ディスクの役割を知らずに）実施できることである。
【００５１】
準静的分散は、少数の大きなディスクとともに使用すると有利な場合がある。なぜなら、この技術はアレイ全体にわたるデータのバランスをとるからである。比較的大きなディスクは妥当な容量を得るために必要とされるが、それは、小さなグループが使用され、復元時間が制限されることを意味する。１４ディスク構成で、２つのグループと１つの予備を使用した場合、ディスクの２０％を越える部分は、データの記憶や読み出しに利用することができない。８つのディスクを使用する構成であれば、状況は更に悪化する。
【００５２】
上記のように、準静的分散技術によれば、ディスクアレイの分散パリティ実施形態に一台づつディスクを追加することが可能になる。ＲＡＩＤ５レベル実施形態よりも優れている本発明の分散技術の利点は、グループ全体をアレイに追加したり、やっかいなＲＡＩＤ５再構成を実施することなく、アレイの簡単な拡張が可能である点にある。この準静的分散技術は、単一故障誤り訂正や二重故障誤り訂正と組み合わせて使用してもよい。また、この技術によれば、同じグループ１３２〜１３６内で複数のディスクサイズを使用することも可能になる。
【００５３】
ディスク全体にわたってパリティを分散させる準静的分散技術の例示的実施形態について図示説明してきたが、本発明の思想及び範囲内において、種々の変更及び改変を施すことが可能であると考えられる。例えば、本明細書に記載した分散技術は、ブロックベースのＲＡＩＤアレイに適用することで、例えば、ＲＡＩＤグループへのディスクの簡単な追加が可能となる。ブロックベースのＲＡＩＤアレイは一般に、どのブロックにファイルシステムデータを記憶すべきことを依頼したかを把握していない。むしろ、アレイは、全てのブロックが、ファイルシステムデータを記憶するパリティブロックとしてまだ指定されていないことを確認しなければならない。従って、ブロックベースのＲＡＩＤアレイは通常、パリティに使用されるブロックを予め割り当てておく。所与のアレイにおいて、そのように事前割り当てされるブロックは固定されている。普通は、システムが各パリティブロックを把握しなくてよいように、何らかの所定のアルゴリズムにおいてこれが行われる。
【００５４】
本発明によれば、ＲＡＩＤシステムは、準静的分散技術を使用して、既存のディスクにおける一部のブロックのパリティ指定を新たなディスクに移動させることができる。また、ＲＡＩＤシステムは、既存のディスクにおける論理ユニット番号（ＬＵＮ）ブロックオフセットが変化していないことを確認しなければならない。そして、その新たな空間は全てのディスクにわたって分散される。この非線形マッピングは通常、ブロックベースのアレイにおいては望ましくない。なぜなら、ファイルシステムがそれを補償できないからである。ただし、大きな塊（例えば少なくとも１トラックサイズ）においてパリティブロックが連続的に割り当てられるならば、この影響は緩和することができる。
【００５５】
当業者には分かるように、本明細書に記載する本発明の技術は、ストレージシステム１００として実施される（又はそれを含む）スタンドアロンコンピュータ及びその一部を含めて、どのようなタイプの特殊目的（例えば、ファイルサーバ、ファイラー、又は、マルチプロトコル・ストレージ・アプライアンス）のコンピュータにも、汎用コンピュータにも適用することができる。本発明と共に使用するのに都合がよいマルチプロトコル・ストレージ・アプライアンスの一例は、２００２年８月８日に出願された「Multi-Protocol Storage Appliance that provides Integrated Support for File and Block Access Protocols」と題する米国特許出願第１０／２１５，９１７号に記載されている。また、本発明の教示は、限定はしないが、ネットワーク・アタッチド・ストレージ環境、ストレージ・エリア・ネットワーク、及び、クライアントコンピュータ又はホストコンピュータに直接取り付けられたディスクアセンブリのような種々のストレージシステムアーキテクチャに適合させることができる。従って、「ストレージシステム」という用語は、そのような構成の他、ストレージ機能を実施するように構成され、他の装置又はシステムに関連する任意のサブシステムをも含むものとして広く解釈しなければならない。
【００５６】
上記の説明は本発明の特定の実施形態に関するものである。しかしながら、当然ながら、それらの利点の一部又は全部を維持したまま、記載した実施形態に対して他の変更または改変を施すことも可能である。例えば、準静的分散技術は、例えばディスクのような永久記憶装置や、例えばシステムのメモリのような非永久的記憶装置の分散に関わる他の用途にも一般化することが可能である。概して、この技術は、システムに更にコンテナを追加する際に、コンテナの何らかのセットにわたって何らかの物資を再分配するような用途にも適用することができる。例えば、この準静的技術は、複数のコンテナにわたってユニットが均一に分散されたユニットとコンテナを有するシステムであって、何らかの番号の次元に沿ってコンテナに対するユニットの割り当てのバランスのとれた比率を維持することが望ましいシステムにも適用することができる。システムに新たなコンテナを追加する場合、本技術を使用すれば、全体的バランス及び局部的バランスが維持されるようなやり方で、既存のユニットの一部を新たなコンテナに転送することができる。
【００５７】
具体的には、準静的技術は、ストレージ「ヘッド」のような複数のストレージエンティティに接続されたアレイの、ディスクのような永久記憶装置間における、ｉｎｏｄｅファイルブロックのようなデータ構造の分散に使用することができる。なお、「ヘッド」とは、ディスクを除く、ストレージシステムの全ての部分として定義される。そのような用途の一例には、１以上の新たに追加されたストレージヘッドを含む複数（Ｎ）のストレージヘッドにわたって既存のｉｎｏｄｅファイルブロックを分散させなければならないものがある。ここで、本発明の準静的分散技術は、何らかの既存のｉｎｏｄｅファイルブロックのうちの１／Ｎだけを新たに追加されたストレージヘッドに移動させるのに使用される場合がある。
【００５８】
当然ながら、本発明の教示は、コンピュータ上で実行されるプログラム命令を含むコンピュータ読取可能媒体を含むソフトウェアでも、ハードウェアでも、ファームウェアでも、それらの組み合わせでも実施することが可能であると考えられる。従って、この説明は単なる例として解釈すべきものであり、本発明の範囲を制限するものとして解釈してはならない。従って、添付の特許請求の範囲の目的は、そのような変更や改変も、本発明の思想及び範囲内に収めることにある。
【図面の簡単な説明】
【００５９】
【図１】本発明と共に使用するのに都合がよいストレージシステムの略ブロック図である。
【図２】本発明の準静的分散技術によるパリティ割り当てを例示するディスクアレイの略ブロック図である。
【図３】準静的分散技術の例示的実施形態に従ってアレイのディスク間でパリティを分散させる一連のステップを示すフロー図である。
【図４】準静的分散技術による種々のグループサイズについて反復間隔を示すパリティ割り当てテーブルを示す図である。
【図１】
2007516524.tif 000003
【図２】
2007516524.tif 000004
【図３】
2007516524.tif 000005
【図４】
2007516524.tif 000006
【国際調査報告】
2007516524.tif 000007
2007516524.tif 000008
2007516524.tif 000009