(57)【要約】【課題】ストレージ・ユニットのアナモルフィック・アレイと共に使用される時にＥＣＣの最小ハミング距離を強化し、これによってアレイの有効最小距離を増やす技法を提供すること。【解決手段】ｍ個のストレージ・ユニットのアレイのエラー許容範囲が、「ドッジング」と称する技法を使用することによって増やされる。複数のｋ個のストライプが、ストレージ・ユニットのアレイにまたがって保管され、各ストライプは、最小ハミング距離ｄ＝ｒ＋１を有する対称コードに対応するｎ＋ｒ個の要素を有する。ストライプの各めいめいの要素が、異なるストレージ・ユニットに保管される。ドナー・ストライプの最小距離とレシピエント・ストライプの最小距離の間の差が２以上の時に、要素が選択される。選択された要素は、レシピエント・ストライプの要素を有しないストレージ・ユニットに保管される。その後、レシピエント・ストライプの失われた要素が、選択された要素上で再作成される。【選択図】図２【特許請求の範囲】
【請求項１】
ｍ個のストレージ・ユニットのアレイのエラー許容範囲を増やす方法であって、ｍ個のストレージ・ユニットの前記アレイにまたがってｋ個のストライプを保管するステップであって、各ストライプが複数の要素を有し、各ストライプが最小ハミング距離ｄを有する消去または誤り訂正コードを形成し、ストライプの各めいめいの要素が、異なるストレージ・ユニットに保管される、ステップと；ドナー・ストライプの最小距離とレシピエント・ストライプの最小距離との間の差が２以上の時に前記ドナー・ストライプ内の要素を選択するステップであって、前記選択された要素が、前記レシピエント・ストライプの要素を有しないストレージ・ユニットに保管される、ステップと；前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成するステップとを含む方法。
【請求項２】
前記レシピエント・ストライプの前記最小ハミング距離が、前記ドナー・ストライプ内の前記要素を選択する前記ステップの前にｄ≧２である、請求項１に記載の方法。
【請求項３】
前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成する前記ステップの前に、前記選択された要素が寄贈されたことを前記ドナー・ストライプを保管する前記ストレージ・ユニットに示すステップをさらに含む、請求項１に記載の方法。
【請求項４】
ｍ個のストレージ・ユニットの前記アレイが、アナモルフィック・アレイであり、各ストライプが、ｎ＋ｒ個の要素を含み、ｎが、ベース・アレイのデータ要素の個数であり、ｒが、ベース・アレイの冗長要素の個数であり、ｍ＞ｎ＋ｒ、ｊｍ＝ｋ（ｎ＋ｒ）であり、ｊおよびｋが整数である、請求項１に記載の方法。
【請求項５】
前記ドナー・ストライプが、さらに、前記アレイに対する最小限の性能影響に基づいて選択される、請求項１に記載の方法。
【請求項６】
前記アレイの改善された性能に基づいてレシピエント情報を選択するステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記消去または誤り訂正コードが、パリティ・コード；Ｗｉｎｏｇｒａｄコード；対称コード；リード−ソロモン・コード；ＥＶＥＮＯＤＤコード；またはＥＶＥＮＯＤＤコードの派生物のうちの１つである、請求項１に記載の方法。
【請求項８】
前記選択された要素上で前記レシピエント・ストライプから失われた要素を再作成する前記ステップ中に前記ドナー・ストライプ内の要素が故障した時に、前記方法が、さらに、前記選択された要素上で前記レシピエント・ストライプから失われた要素を再作成する前記ステップを打ち切るステップと；第２ドナー・ストライプの最小距離と第２レシピエント・ストライプの最小距離との間の差が２以上である時に前記複数のストライプから前記第２ドナー・ストライプを選択するステップと；前記第２ドナー・ストライプ内でドナー要素を選択するステップと；前記第２ドナー・ストライプ内の前記選択された要素上で前記レシピエント・ストライプから失われたレシピエント情報の少なくとも一部を再作成するステップとを含む、請求項１に記載の方法。
【請求項９】
予備要素が使用可能になった時に、前記予備要素を選択されたストレージ・ユニットに割り当てるステップをさらに含む、請求項１に記載の方法。
【請求項１０】
故障の選択されたパターンに脆弱なｍ個のストレージ・ユニットのアレイの故障許容範囲を増やす方法であって、ｍ個のストレージ・ユニットの前記アレイにまたがってｋ個のストライプを保管するステップであって、各ストライプが、複数の要素を有し、各ストライプが、最小ハミング距離ｄを有する消去または誤り訂正コードを形成し、ストライプの各めいめいの要素が、異なるストレージ・ユニットに保管される、ステップと；要素故障の後に、レシピエント要素を選択するステップと；前記アレイの故障許容範囲が再作成動作の後に増えるように、ドナー・ストライプ内の要素を選択するステップと；前記ドナー・ストライプの前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成するステップとを含む方法。
【請求項１１】
ｍ個のストレージ・ユニットのアレイであって、ｋ個のストライプがｍ個のストレージ・ユニットの前記アレイにまたがって保管され、各ストライプが複数の要素を有し、各ストライプが最小ハミング距離ｄを有する消去または誤り訂正コードを形成し、ストライプの各めいめいの要素が、異なるストレージ・ユニットに保管される、ｍ個のストレージ・ユニットのアレイと；ドナー・ストライプの最小距離とレシピエント・ストライプの最小距離との間の差が２以上の時に前記ドナー・ストライプ内の要素を選択するシステム・アレイ・コントローラであって、前記選択された要素が、前記レシピエント・ストライプの要素を有しないストレージ・ユニットに保管される、システム・アレイ・コントローラとを有し；前記システム・アレイ・コントローラが、前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成するデータ・ストレージ・システム。
【請求項１２】
前記レシピエント・ストライプの前記最小ハミング距離が、前記システム・アレイ・コントローラが前記ドナー・ストライプ内の前記要素を選択する前にｄ≧２である、請求項１１に記載のデータ・ストレージ・システム。
【請求項１３】
前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成する前に、前記システム・アレイ・コントローラが、前記選択された要素が寄贈されたことを前記ドナー・ストライプを保管する前記ストレージ・ユニットに示す、請求項１１に記載のデータ・ストレージ・システム。
【請求項１４】
ｍ個のストレージ・ユニットの前記アレイが、アナモルフィック・アレイであり、各ストライプが、ｎ＋ｒ個の要素を含み、ｎが、ベース・アレイのデータ要素の個数であり、ｒが、ベース・アレイの冗長要素の個数であり、ｍ＞ｎ＋ｒ、ｊｍ＝ｋ（ｎ＋ｒ）であり、ｊおよびｋが整数である、請求項１１に記載のデータ・ストレージ・システム。
【請求項１５】
前記システム・アレイ・コントローラが、前記アレイに対する最小限の性能影響にさらに基づいて前記ドナー・ストライプを選択する、請求項１１に記載のデータ・ストレージ・システム。
【請求項１６】
前記システム・アレイ・コントローラが、前記アレイの改善された性能に基づいてレシピエント情報を選択する、請求項１１に記載のデータ・ストレージ・システム。
【請求項１７】
前記システム・アレイ・コントローラが前記選択された要素上で前記レシピエント・ストライプからレシピエント情報の少なくとも一部を再作成している時に前記ドナー・ストライプ内の要素が故障した時に、前記システム・アレイ・コントローラが、前記選択された要素上で前記レシピエント・ストライプから前記レシピエント情報を再作成するのを打ち切り、第２ドナー・ストライプの最小距離と第２レシピエント・ストライプの最小距離との間の差が２以上である時に前記複数のストライプから前記第２ドナー・ストライプを選択し、前記第２ドナー・ストライプ内でドナー要素を選択し、前記第２ドナー・ストライプ内の前記選択された要素上で前記レシピエント・ストライプから失われたレシピエント情報の少なくとも一部を再作成する、請求項１１に記載のデータ・ストレージ・システム。
【請求項１８】
予備要素が使用可能になった時に、前記システム・アレイ・コントローラが、前記予備要素を選択されたストレージ・ユニットに割り当てる、請求項１１に記載のデータ・ストレージ・システム。
【請求項１９】
ｍ個のストレージ・ユニットのアレイであって、ｋ個のストライプが、ｍ個のストレージ・ユニットの前記アレイにまたがって保管され、各ストライプが、複数の要素を有し、各ストライプが、最小ハミング距離ｄを有する消去または誤り訂正コードを形成し、ストライプの各めいめいの要素が、異なるストレージ・ユニットに保管される、ｍ個のストレージ・ユニットのアレイと；要素故障の後にレシピエント・ストライプを選択し、前記アレイの故障許容範囲が再作成動作の後に増えるように、ドナー・ストライプ内の要素を選択するシステム・アレイ・コントローラであって、前記システム・アレイ・コントローラが、前記ドナー・ストライプの前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成する、システム・アレイ・コントローラとを含むデータ・ストレージ・システム。
【請求項２０】
前記レシピエント・ストライプの最小ハミング距離が、前記システム・アレイ・コントローラが前記ドナー・ストライプ内の要素を選択する前にｄ≧２である、請求項１９に記載のデータ・ストレージ・システム。
【請求項２１】
前記アレイの最小ハミング距離が、前記ドナー・ストライプの前記選択された要素上での前記レシピエント・ストライプの前記失われた要素の再作成の完了時に増える、請求項１９に記載のデータ・ストレージ・システム。
【請求項２２】
ストレージ・ユニットの複数のアレイであって、各アレイが、ｍ個のストレージ・ユニットを有し、ｋ個のストライプが、ｍ個のストレージ・ユニットの各めいめいのアレイにまたがって保管され、各ストライプが、複数の要素を有し、各ストライプが、最小ハミング距離ｄ＝ｎ＋１を有する消去または誤り訂正コードを形成し、ストライプの各めいめいの要素が、前記アレイ内の異なるストレージ・ユニットに保管される、ストレージ・ユニットの複数のアレイと；
ドナー・ストライプの最小距離とレシピエント・ストライプの最小距離との間の差が２以上の時に前記ドナー・ストライプ内の要素を選択するシステム・アレイ・コントローラであって、前記選択された要素が、前記レシピエント・ストライプの要素を有しないストレージ・ユニットに保管され、前記システム・アレイ・コントローラが、前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成する、システム・アレイ・コントローラとを有するデータ・ストレージ・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージ・システムに関する。具体的に言うと、本発明は、アレイに保管されたデータの消失なしでアレイが許容できるストレージ・ユニット故障の数を増やすためにストレージ・ユニットのアレイを構成する方法に関する。
【背景技術】
【０００２】
次の定義が、本明細書で使用され、制限ではなく例示のために提供される。
【０００３】
「要素」は、ストレージ・ユニット上のデータのブロックである。
【０００４】
「ベース・アレイ」は、ＥＣＣ用のアレイ・ユニットを含む要素の組である。
【０００５】
「アレイ」は、１つまたは複数のベース・アレイを保持するストレージ・ユニットの組である。
【０００６】
「ストライプ」は、アレイ内のベース・アレイである。
【０００７】
ｎは、ベース・アレイのデータ・ユニットの個数である。
【０００８】
ｒは、ベース・アレイの冗長ユニットの個数である。
【０００９】
ｍは、アレイのストレージ・ユニットの個数である。
【００１０】
ｄは、ベース・アレイの最小ハミング距離である。
【００１１】
Ｄは、アレイの最小ハミング距離である。
【００１２】
従来のアレイでは、アレイ内のストレージ・ユニットの個数が、ベース・アレイ内のデータ・ユニットの個数とベース・アレイ内の冗長ユニットの個数の合計と等しい。すなわちｍ＝ｎ＋ｒである。ほとんどの従来のストレージ・アレイは、パリティなどのＭＤＳ（マキシマム・ディスタンス・セパレーション）コードまたは故障を許容するためのミラーリング技法を使用する。ＭＤＳコードを有するベース・アレイの最小ハミング距離は、１とベース・アレイ内の冗長ユニットの個数の合計と等しい（すなわち、ｄ＝１＋ｒである）。ミラー構成について、ベース・アレイ内の冗長ユニットの個数は、ベース・アレイ内のデータ・ユニットの個数と等しく（ｒ＝ｎ＝１）、最小ハミング距離はｄ＝２である。
【００１３】
ｍ個のストレージ・ユニットにわたってアナモルフィックに（anamorphically）アレイを符号化することが可能であり、ｍは、アレイ内のデータ・ユニットの個数ｎとアレイ内の冗長ユニットの個数ｒの合計より大きい、すなわち、ｍ＞ｎ＋ｒである。文献では、性能のためにパリティ・ブロックを配置するにアナモルフィック符号化が使用される時に、そのような符号化を、通常は「クラスタリングされていないパリティ（de-clusteringparity）」と称する。本明細書で使用される時に、そのような符号化方式を、アナモルフィック符号化と称する。というのは、これによって、その符号化方式がアレイの新しいプロパティを提供できることがより正確に識別されるからである。
【００１４】
アナモルフィズムは、アレイ内のベース・アレイの組を選択的に配置することによって達成することができる。たとえば、４要素コードを使用する図３に示された例示的なアレイ２００を検討されたい。アレイ２００に、列の形で示された６つのストレージ・ユニットＤ１〜Ｄ６が含まれる。アレイ２００について、ｍ＝６である。アレイ２００に、ｎ個のデータ・ユニットとｒ個の冗長ユニットからそれぞれが形成される複数のベース・アレイも含まれる。すなわち、ベース・アレイごとに、ｎ＋ｒ＝４である。めいめいのベース・アレイは、図３ではストライプ１として順次番号を付けられて、アレイ２００の４要素コードがストレージ・ユニットＤ１〜Ｄ６にまたがって分散することが示されている。各ストライプに４つのブロックがあり、各ストライプは、独立のベース・アレイとして働く。したがって、アレイの最小距離は、めいめいのストライプのすべての最小ハミング距離の最小値すなわち、Ｄ＝ｍｉｎ（ｄｉ）であり、ｄｉは、ストライプｉの最小距離である。
【００１５】
構成された時に、アナモルフィック・アレイ２００は、ｎ個のストレージ・ユニットの組から正確にｒ個のユニットではなく、データの消失なしにｍ個のストレージ・ユニットの組の少なくともｒ個のストレージ・ユニットの消失を許容することができる。したがって、ｒ＝２であり使用されるコードがＭＤＳの場合に、どの２つのストレージ・ユニットでも、データの消失なしで故障することができる。このストライプは、その要素のうちのいずれか３つが失われた場合に故障する。しかし、アナモルフィック・アレイ２００によって許容できる３ユニット故障のある組合せがある。たとえば、ストレージ・ユニットＤ１、Ｄ３、およびＤ５のそれぞれが故障した場合に、ストライプ１の２つの要素、ストライプ２の２つの要素、およびストライプ３の２つの要素が失われるが、どのストライプも、３つの要素を失ってはいない。したがって、アナモルフィック・アレイ２００は、過剰仕様であり、有利に活用することができる。
【特許文献１】US Patent Application Serial No.10/619,649
【特許文献２】US Patent Application Serial No.10/619,633
【特許文献３】US Patent Application Serial No.10/619,648
【特許文献４】US Patent Application Serial No.10/600,593
【発明の開示】
【発明が解決しようとする課題】
【００１６】
必要なものは、ストレージ・ユニットのアナモルフィック・アレイと共に使用される時にＥＣＣの最小ハミング距離を強化し、これによってアレイの有効最小距離を増やす技法である。
【課題を解決するための手段】
【００１７】
本発明は、ストレージ・ユニットのアナモルフィック・アレイと共に使用されるＥＣＣの最小ハミング距離を強化し、これによってアレイの最小距離を増やす技法を提供する。
【００１８】
本発明の利益は、ｋ個のストライプがｍ個のストレージ・ユニットのアレイにまたがって保管されるｍ個のストレージ・ユニットのアナモルフィック・アレイのエラー許容範囲を増やす方法およびシステムである第１の実施形態によって提供される。各ストライプは、最小ハミング距離ｄ＝ｒ＋１を有する対称コードに対応するｎ＋ｒ個の要素を有し、ｎは、ｍ個のストレージ・ユニットのアレイのベース・アレイのデータ・ストレージ・ユニットの個数であり、ｒは、このベース・アレイの冗長ユニットの個数である。さらに、ｎ＝ｒ、ｎ≧２、ｍ＞ｎ＋ｒ、ｊｍ＝ｋ（ｎ＋ｒ）であり、ｊおよびｋは整数である。あるストライプの各めいめいの要素は、異なるストレージ・ユニットに保管される。ドナー・ストライプ（donor stripe）の最小距離とレシピエント・ストライプ（recipient stripe）の最小距離の間の差が２以上である時に、要素が選択される。選択された要素は、レシピエント・ストライプの要素を有しないストレージ・ユニットで再作成される。失われた要素を再作成する前に、ドナー・ストライプを保管したストレージ・ユニットは、選択された要素が寄贈（donate）され、その結果、データが、ドナー・ストライプの一部として選択された要素から読み取られず、書き込まれなくなることを知らされる。次に、レシピエント・ストライプの失われた要素が、選択された要素で再作成される。本発明によれば、レシピエント・ストライプの最小ハミング距離は、ドナー・ストライプの要素が選択される前に、ｄ≧１である。ドナー・ストライプの選択された要素を、さらに、アレイに対する最小の性能影響に基づいて選択することができる。さらに、レシピエント情報が、アレイの改善された性能に基づいて選択される。ストレージ・システムのアレイに、パリティ・コード、Ｗｉｎｏｇｒａｄコード、対称コード、リード−ソロモン・コード、ＥＶＥＮＯＤＤコード、またはＥＶＥＮＯＤＤコードの派生物（derivative）など、消去または誤り訂正コードに基づく冗長性が含まれる。代替案では、アレイに、複数の消去または誤り訂正コードの結果に基づく冗長性が含まれ、消去または誤り訂正コードの少なくとも１つが、パリティ・コード、Ｗｉｎｏｇｒａｄコード、対称コード、リード−ソロモン・コード、ＥＶＥＮＯＤＤコード、またはＥＶＥＮＯＤＤコードの派生物である。
【００１９】
ドナー・ストライプの要素が、選択された要素でレシピエント・ストライプからレシピエント情報の少なくとも一部を再作成するステップ中に故障した時に、選択された要素でレシピエント・ストライプからレシピエント情報の少なくとも一部を再作成するステップが打ち切られる。第２ドナー・ストライプの最小距離と第２レシピエント・ストライプの最初距離の間の差が２以上である時に、第２ドナー・ストライプが、複数のストライプから選択される。ドナー要素が、第２ドナー・ストライプ内で選択される。レシピエント・ストライプから失われたレシピエント情報の少なくとも一部が、第２ドナー・ストライプ内の選択された要素で再作成される。予備要素が使用可能になった時に、予備要素が、選択されたストレージ・ユニットに割り当てられる。
【００２０】
本発明の第２の実施形態は、故障の選択されたパターンに脆弱であるｍ個のストレージ・ユニットのアレイの故障許容範囲を増やす方法およびシステムを提供する。本発明のこの実施形態によれば、ｋ個のストライプが、ｍ個のストレージ・ユニットのアレイにまたがって保管される。ｍ個のストレージ・ユニットのアレイは、アナモルフィック・アレイである。各ストライプは、ｎ＋ｒ個の要素を有し、ｎは、ベース・アレイのデータ要素の個数であり、ｒは、ベース・アレイの冗長要素の個数であり、ｍ＞ｎ＋ｒ、ｊｍ＝ｋ（ｎ＋ｒ）であり、ｊおよびｋは整数である。各ストライプは、複数の要素を有し、各ストライプは、最小ハミング距離ｄを有する消去または誤り訂正コードを形成する。あるストライプの各めいめいの要素は、異なるストレージ・ユニットに保管される。要素故障の後に、レシピエント要素が選択される。アレイの故障許容範囲が再作成動作の後に増えるように、ドナー・ストライプ内の要素が選択される。レシピエント・ストライプの失われた要素が、ドナー・ストライプの要素で再作成される。レシピエント・ストライプの最小ハミング距離は、要素がドナー・ストライプで選択される前に、ｄ≧２である。さらに、アレイの最小ハミング距離は、ドナー・ストライプの選択された要素でのレシピエント・ストライプの再作成の完了時に増える。レシピエント要素を、アレイの故障パターンに基づいて選択することができる。さらに、ドナー要素を、所定のターゲット・パターンに基づいて選択することができる。ドナー・ストライプを保管するストレージ・ユニットは、レシピエント・ストライプの失われた要素が選択された要素で再作成される前に、選択された要素が寄贈されたことを知らされる。ストレージ・ユニットのアレイに、パリティ・コード、Ｗｉｎｏｇｒａｄコード、対称コード、リード−ソロモン・コード、ＥＶＥＮＯＤＤコード、またはＥＶＥＮＯＤＤコードの派生物など、消去または誤り訂正コードに基づく冗長性が含まれる。代替案では、ストレージ・ユニットのアレイに、複数の消去または誤り訂正コードの結果に基づく冗長性が含まれ、消去または誤り訂正コードの少なくとも１つが、パリティ・コード、Ｗｉｎｏｇｒａｄコード、対称コード、リード−ソロモン・コード、ＥＶＥＮＯＤＤコード、またはＥＶＥＮＯＤＤコードの派生物である。
【００２１】
本発明の第３の実施形態は、各アレイがｍ個のストレージ・ユニットを含み、ｋ個のストライプがｍ個のストレージ・ユニットの各めいめいのアレイにまたがって保管される、ストレージ・ユニットの複数のアレイを有するストレージ・システムのエラー許容範囲を増やす方法およびシステムを提供する。各ストライプは、最小ハミング距離ｄを有する対称コードに対応するｎ＋ｒ個の要素を有し、ｎは、ｍ個のストレージ・ユニットのアレイのベース・アレイのデータ要素の個数であり、ｒは、ベース・アレイの冗長要素の個数である。さらに、ｎ＝ｒ、ｎ≧２、ｍ＞ｎ＋ｒ、ｊｍ＝ｋ（ｎ＋ｒ）であり、ｊおよびｋは整数である。あるストライプの各めいめいの要素は、アレイの異なるストレージ・ユニットに保管される。ドナー・ストライプの最小距離とレシピエント・ストライプの最小距離の間の差が２以上である時に、要素がドナー・ストライプ内で選択される。選択された要素は、レシピエント・ストライプの要素を有しないストレージ・ユニットに保管される。ドナー・ストライプは、レシピエント・ストライプのアレイと異なるアレイに保管することができる。その代わりに、ドナー・ストライプを、レシピエント・ストライプと同一のアレイに保管することができる。失われた要素を再作成する前に、ドナー・ストライプを保管したストレージ・ユニットは、選択された要素が寄贈され、その結果、データが、ドナー・ストライプの一部として選択された要素から読み取られず、書き込まれなくなることを知らされる。次に、レシピエント・ストライプの失われた要素が、選択された要素で再作成される。本発明によれば、レシピエント・ストライプの最小ハミング距離は、ドナー・ストライプの要素が選択される前に、ｄ≧２である。ドナー・ストライプの選択された要素を、さらに、ドナー・ストライプに対する最小の性能影響に基づいて、またはストレージ・システムに対する最小の性能影響に基づいて選択することができる。さらに、レシピエント情報が、レシピエント・ストライプの改善された性能に基づいて、またはストレージ・システムの改善された性能に基づいて選択される。ストレージ・システムのアレイに、パリティ・コード、Ｗｉｎｏｇｒａｄコード、対称コード、リード−ソロモン・コード、ＥＶＥＮＯＤＤコード、またはＥＶＥＮＯＤＤコードの派生物など、消去または誤り訂正コードに基づく冗長性が含まれる。代替案では、アレイに、複数の消去または誤り訂正コードの結果に基づく冗長性が含まれ、消去または誤り訂正コードの少なくとも１つが、パリティ・コード、Ｗｉｎｏｇｒａｄコード、対称コード、リード−ソロモン・コード、ＥＶＥＮＯＤＤコード、またはＥＶＥＮＯＤＤコードの派生物である。
【００２２】
本発明を、制限ではなく例として添付図面に示すが、添付図面では、同一の符号が同一の要素を指す。
【発明を実施するための最良の形態】
【００２３】
本願は、US Patent Application Serial No.10/619,649 (Attorney Docket No. ARC92003015US1), entitled “Automatic ParityExchange”、US Patent Application Serial No. 10/619,633 (entitled “Multi-pathData Retrieval From Redundant Array”、およびUS Patent Application Serial No.10/619,648 (entitled “RAID 3 + 3”に関する。本願は、同時係属であり本願と同一の譲受人に譲渡されたUS PatentApplication Serial No. 10/600,593 (Attorney Docket No. YOR9-2003-0069US1)にも関する。
【００２４】
パリティ・コード、Ｗｉｎｏｇｒａｄコード、対称コード、リード−ソロモン・コード、ＥＶＥＮＯＤＤコード、またはＥＶＥＮＯＤＤコードの派生物などの消去または誤り訂正コード（ＥＣＣ）によって許容できるアレイの故障の最小個数は、少なくとも、ＥＣＣの最小ハミング距離ｄから１を引いた数すなわちｄ−１である。本発明は、本明細書で「ドッジング（ｄｏｄｇｉｎｇ）」動作と称する、ＥＣＣのハミング距離より大きい「有効距離」を提供する動作を利用することによって、ＥＣＣの最小ハミング距離を拡張する。したがって、故障がデバイス故障またはハード故障のどちらであるかにかかわりなく、アレイが許容できる故障の個数は、ＥＣＣによって提供される最小距離を超えて増やされる。本明細書で使用する用語「有効距離」および「有効最小距離」は、１に、本発明による１つまたは複数のドッジング動作を利用するアレイが許容できる故障の個数を加えた数を指す。
【００２５】
次では、ドッジング動作は、アレイ内のストライプがレシピエント・ストライプへの要素の寄贈のために選択され、レシピエント情報が寄贈された要素上で再作成され、これによってアレイの最小距離が増やされる処理である。ドッジング動作は、距離ｄｉ≧ｄｊ＋２である時にストライプの対（ｉ，ｊ）に対して実行することができる。ドッジング動作の後に、ドナー・ストライプは、距離が１つだけ減る。対照的に、レシピエント・ストライプは、距離が１つだけ増える。ドッジング動作を、最小アレイ距離であるすべてのストライプに対して実行できる時に、総合的な最小アレイ距離が増える。ドッジング動作は、アレイの構成に応じて、さまざまな距離で行うことができる。
【００２６】
図１に、共通のアレイ・コントローラ１０１に接続された２つのストレージ・アレイ１０２および１０３を含む、全般的に１００として示された例示的なストレージ・システムを示す。ストレージ・アレイ１０２および１０３は、複数のストレージ・ユニット１０４を含み、インターフェース１０５を介してアレイ・コントローラ１０１と通信する。アレイ・コントローラ１０１は、インターフェース１０６を介して他のコントローラおよびホスト・システムと通信する。そのような構成は、アレイ・コントローラが複数のストレージ・アレイと通信することを可能にする。
【００２７】
図２に、異なるアレイ・コントローラ１５２および１５１にそれぞれ接続された２つのストレージ・アレイ１５３および１５４を含む、全般的に１５０として示された例示的なストレージ・システムを示す。ストレージ・アレイ１５３は、インターフェース１５７を介してアレイ・コントローラ１５２と通信し、ストレージ・アレイ１５４は、インターフェース１５６を介してアレイ・コントローラ１５１と通信する。アレイ・コントローラ１５１および１５２は、それぞれ、インターフェース１５８および１５９を介して他のアレイ・コントローラおよびストレージ・システムと通信する。図２には、アレイ・コントローラ１５１および１５２が互いに通信できるようにする通信接続１６０も示されている。
【００２８】
図１および２に示されたアレイ・コントローラは、ハードウェア・コントローラまたはソフトウェア・コントローラとして設計することができる。用語コントローラは、本明細書では、一般に、上で説明した構成のいずれかを指すのに使用される。
【００２９】
多数のアナモルフィック・アレイが、ドッジングから利益を得ることができる。アナモルフィック・アレイがドッジング動作から利益を得る能力は、アレイの故障組合せの検査によって検証することができる。たとえば、図４に、９つのストレージ・ユニットＤ１〜Ｄ９を有する例示的なアナモルフィック・アレイ３００を示す。この例では、アレイ３００が、（３＋３）対称コードを使用し、このコードは、ｎ＝３、ｒ＝３、およびｄ＝４のＭＤＳである。アレイ３００は、ストライプ内の６つの要素からの３つの故障した要素を訂正できる３つの冗長要素を含むように配置される。それぞれ１、２、および３として示された３つの独自のストライプが、アレイ３００内に配置されている。３つのストレージユニット故障のどれであっても、１つのストライプの３つを超える要素に影響しない。したがって、アレイ３００は、最小距離Ｄ＝４を有する。
【００３０】
本発明によるドッジング動作を実行して、アレイ３００の有効最小距離を増やすことができることを示すために、考慮を必要とする３ストレージユニット故障の３つの配置だけがある。第１の３ストレージユニット故障配置を、図５に示すが、ここで、ブロック内の×はストレージユニット故障を示す。この特定の故障配置では、各ストライプの２つのブロックが故障している。その結果、各ストライプは、最小距離ｄ＝２を有し、したがって、アレイ３００は、最小距離Ｄ＝２を有する。したがって、アレイ３００は、図５に示されているように、可能なデータ消失なしに、もう１つのストレージユニット故障を許容することができる。
【００３１】
第２の３ストレージユニット故障配置を図６に示すが、ここで、ブロック内の×はストレージユニット故障を示す。第２の３ストレージユニット故障配置では、ストライプ１が、３つの要素を失っており、ストライプ２が、２つの要素を失っており、ストライプ３が、１つの要素を失っている。したがって、ストライプ１は、最小距離ｄ＝１を有し、データ消失なしでこれ以上のストレージユニット故障を許容することができない。ストライプ２は、最小距離ｄ＝２を有し、ストライプ３は、最小距離ｄ＝３を有する。その結果、アレイ３００は、最小距離Ｄ＝１を有する。
【００３２】
ドッジング動作は、第２の３ストレージユニット故障配置について、ストライプ３の故障していない要素の１つで周知の形でストライプ１の失われた要素の１つの内容を再作成することによって実行することができる。図７に、ドッジング動作を実行した後の図６のアレイを示す。図７では、再作成されたデータに下線を付けた。ここで、ユニットＤ９のストライプ３の要素が、ストライプ１に寄贈されている。ドッジング動作の後に、すべてのストライプが、最小距離ｄ＝２を有し、したがって、アレイ３００は、最小距離Ｄ＝２を有する。ドッジング動作の後のアレイの構成は、データを失わずにもう１つの故障を許容することができる。
【００３３】
第３の３ストレージユニット故障配置を図７に示すが、ここで、ブロック内の×はストレージユニット故障を示す。第３の３ストレージユニット故障配置では、ストライプ１および２が、それぞれ３つの要素を失っており、最小距離ｄ＝１を有する。しかし、ストライプ３は、要素を失っておらず、その結果、最小距離ｄ＝４を有する。ストライプ１および２（ｄ＝１）のそれぞれからの１つの失われた要素の内容を周知の形でストライプ３（ｄ＝４）の異なる要素で再作成することによって、第３の３ストレージユニット故障配置についてドッジング動作を実行することができる。たとえば、ストレージ・ユニットＤ１の要素１の内容を、ディスクＤ９の要素３で再作成することができ、ディスクＤ１の要素２の内容を、ディスクＤ４の要素３で再作成することができる。
【００３４】
図９に、ドッジング動作を実行した後の図８のアレイを示す。図９では、再作成されたデータに下線を付けた。その結果は、やはり、すべてのストライプが最小距離ｄ＝２を有し、その結果、アレイ３００が最小距離Ｄ＝２を有することである。ドッジング動作の後に、どのストレージ・ユニットにも同一ストライプからの２つの要素が含まれないことが重要である。すなわち、ストレージ・ユニットＤ４に保管されたストライプ３の要素のどれもが、ストライプ１の失われた要素の再作成のために選択されていない。というのは、ストレージ・ユニットＤ４のそれぞれに、既にストライプ１の要素が含まれるからである。同様に、ストレージ・ユニットＤ７に保管されたストライプ３の要素のどれもが、ストライプ２の失われた要素の再作成のために選択されていない。
【００３５】
したがって、ドッジングは、３つのストレージユニット故障の後に、図４のアレイ３００の最小距離をＤ＝１からＤ＝２に復元する技法を提供する。さらに、アレイ３００の有効最小距離は、アレイ３００のシステムがまだ距離ｄ＝４を有するコードの書込性能を有する場合であっても、ｄ＝４からｄ＝５に増えている。
【００３６】
有効距離が増える（３＋３）コードに関する最小のアナモルフィック・アレイは、９ストレージ・ユニットのアレイである。９ストレージ・ユニットより大きいすべてのアレイも、（３＋３）コードが使用される時に、増えた有効距離というプロパティを有する。（３＋３）コードの８ストレージ・ユニットのアレイは、増えた有効距離というプロパティを有しない。１２個のストレージ・ユニットに対して利用される（４＋４）コードも、増えた有効距離というプロパティを有する。しかし、ドッジング動作は、最小アレイ距離がｄ＝２の時に行われなければならない。その結果、ドッジング動作中のさらなるストレージユニット故障を許容することができる。
【００３７】
本発明の実施形態によれば、ドッジング動作は、アレイ内、別々のアレイの間、または、アレイと予備プールの間で実行することができ、後者を、本明細書で外部ドッジング動作と称する。予備プールに対して実行されるドッジング動作が可能ではあるが、通常は、予備で完全な再作成動作を実行し、予備プールが使い果たされた時に限ってドッジング動作を実行することがよりよい。これは、ドッジング動作が、寄贈されたストレージ・ユニット上で故障したストレージ・ユニットから一部の要素だけを再作成するが、予備作成（ｓｐａｒｉｎｇ）動作が、予備ストレージ・ユニット上で故障したストレージからすべての要素を再作成するからである。
【００３８】
外部ドッジング動作は、参照によって本明細書に組み込まれている同時係属のUSPatent Application Serial No.10/619,649に開示されたものなどのパリティ交換動作と異なる。すなわち、ドッジング動作は、ストライプを基礎として実行されるが、パリティ交換動作は、ストレージ・ユニットを基礎として実行される。
【００３９】
本発明による外部（アレイ対アレイ）ドッジング動作によって提供される利益を示すために、図１０に示された例示的なアレイ９００を検討されたい。アレイ９００は、８つのストレージ・ユニットＤ１〜Ｄ８を含み、（３＋３）対称コードを使用する。アレイ９００に、符号１〜４によって示された４つのストライプも含まれる。各ストライプは、６つの要素を有し、距離ｄ＝４を有する。前に述べたように、アレイ９００など、（３＋３）コードを使用する８ストレージ・ユニットのアレイの内部のドッジング動作は、アレイの有効最小ハミング距離を増やさない。というのは、残りの故障していないストライプが、複数のユニット故障によって影響を受けるストライプの個数を補償するのには少なすぎるからである。
【００４０】
対照的に、図１１に示された、３つの８ストレージユニット・アレイ１００１を含む例示的なアレイ・システム１０００を検討されたい。具体的に言うと、アレイ１００１に、ストレージ・ユニットＤ１〜Ｄ８が含まれ、アレイ１００２に、ストレージ・ユニットＤ９〜Ｄ１６が含まれ、アレイ１００３に、ストレージ・ユニットＤ１７〜Ｄ２４が含まれる。各めいめいのアレイ１００１〜１００３に、アレイ内に配置された４つのストライプも含まれる。たとえば、アレイ１００１に、ストライプ１〜４が含まれ、アレイ１００２に、ストライプ５〜８が含まれ、アレイ１００３に、ストライプ９〜１２が含まれる。
【００４１】
いずれか３つのストレージユニット故障の後に、同時係属のUS PatentApplication Serial No.10/619,649に開示されたものなどのパリティ交換動作を使用して、各アレイ１００１〜１００３が１つの故障したストレージ・ユニットを有することを保証すると仮定する。パリティ交換動作の結果は、たとえば、ストレージ・ユニットのブロック内に×を有して示されているストレージ・ユニットＤ１、Ｄ９、およびＤ１７によって示されている。さらに、第４のストレージユニット故障が、パリティ交換動作の後に発生したと仮定する。第４のストレージユニット故障は、たとえば、ストレージ・ユニットＤ２のブロック内に×を有して示されている、アレイ１００１内のストレージ・ユニットＤ２によって示されている。第４のストレージユニット故障の後に、アレイ１００１、１００２、および１００３のそれぞれは、距離Ｄ＝（２，３，３）を有する。ストレージ・ユニットＤ２以外の別のストレージ・ユニットが、第４のストレージユニット故障として故障する可能性があり、下で説明する手順に似た手順が、ストレージ・システムの有効距離を増やすために実行されることを理解されたい。
【００４２】
アレイ１００１内のストライプ１、２、および３は、現在、距離ｄ＝２のみを有する。アレイ１００１の内部のドッジング動作は、アレイ１００の最小距離を２から３に増やすために少なくとも３つの距離ｄ＝４を有する要素が必要なので、失敗する。アレイ１００１内のストライプ４だけが、距離ｄ＝４を有する。それでも、アレイの間の外部ドッジング動作によって、アレイ１００２および１００３の最小距離を変更せずに、アレイ１００１の最小距離を２から３に増やすことが可能になる。これを達成するために、ストライプ１〜３のそれぞれの欠けている要素の１つの内容を、周知の形で、アレイ１００１のストライプ４、アレイ１００２のストライプ８、およびアレイ１００３のストライプ１２など、まだ距離ｄ＝４を有する他のストライプの要素に再作成する。
【００４３】
図１２に、本発明による外部ドッジング動作を実行した後の図１１のアレイ・システム１０００を示す。図１２では、再作成されたデータに下線を付けた。具体的に言うと、ストライプ３の要素が、ストレージ・ユニットＤ３内のストライプ４での再作成のために選択される。ストライプ２の要素が、ストレージ・ユニットＤ１０内のストライプ８での再作成のために選択される。最後に、ストライプ１の要素が、ストレージ・ユニットＤ１７内のストライプ１２での再作成のために選択される。
【００４４】
要素がドナー・ストライプ内で選択された時に、選択された要素を含むストレージ・ユニットは、レシピエント・ストライプの要素を含むことができない。たとえば、ストレージ・ユニットＤ７およびＤ８の両方にストライプ１の要素が含まれないので、ストレージ・ユニットＤ７またはストレージ・ユニットＤ８のいずれかに含まれるストライプ４の要素を、ストライプ１からの故障した要素の再作成に選択することができる。同様に、ストレージ・ユニットＤ５およびＤ６の両方にストライプ２の要素が含まれないので、ストレージ・ユニットＤ５またはストレージ・ユニットＤ６のいずれかに含まれるストライプ４の要素を、ストライプ２からの故障した要素の再作成に選択することができる。最後に、ストレージ・ユニットＤ３およびＤ４の両方にストライプ３の要素が含まれないので、ストレージ・ユニットＤ３またはストレージ・ユニットＤ４のいずれかに含まれるストライプ４の要素を、ストライプ３からの故障した要素の再作成に選択することができる。この例において、ストレージ・ユニットＤ３に含まれるストライプ４の要素が、ストライプ３の要素の再作成のためのドナー要素に選択されると仮定する。
【００４５】
ｄ＝４を有するストライプ８の要素のいずれか１つを、それぞれがｄ＝２を有する残りのストライプのいずれか１つの故障した要素の再作成のために選択することができ、ｄ＝４を有するストライプ１２の要素のいずれか１つを、それぞれがｄ＝２を有する最後の残りのストライプの故障した要素の再作成のために選択することができる。この例示的な例において、ストレージ・ユニットＤ１１に含まれるストライプ８の要素が、ストライプ２の要素の再作成のためのドナー要素に選択され、ストレージ・ユニットＤ１９に含まれるストライプ１２の要素が、ストライプ１の要素の再作成のためのドナー要素に選択されると仮定する。ドッジング動作の前のこの例示的な例のドッジング選択のそれぞれについて、ドナー・ストライプは、距離ｄ＝４を有し、レシピエント・ストライプ（すなわち、ストライプ１〜３）は、距離ｄ＝２を有する。
【００４６】
この外部ドッジング動作の正味の結果は、アレイ・システム１０００が、４つの故障の後に最小距離Ｄ＝３を有することである。対照的に、同時係属のUS Patent Application Serial No.10/619,649に開示されたものなどのパリティ交換動作だけを使用することによって、最小距離は２だけを有する。その結果、外部ドッジング動作が、アレイ・システム１０００について利用される時に、アレイ・システム１０００がｄ＝２の最小距離を有するためには、４つの故障が必要である。これは、６つのユニットの４つのアレイとして配置され、各アレイが同時係属のUSPatent Application Serial No.10/619,649に開示されたものなどのパリティ交換動作だけを使用する、２４ユニットのアレイ・システムと同一の結果である。したがって、パリティ交換動作と組み合わされたドッジング動作は、システム信頼性がアレイ構成と独立になることをもたらす。
【００４７】
パリティ交換動作と組み合わされた一般化されたドッジング動作の処理を、各さらなるストレージ・ユニット故障と共に継続することができる。上で説明したように、故障した要素が、残っている要素で再作成され、各アレイの最小距離が、最大化される。図１０および１１の例示的な２４ユニットのアレイ・システムでは、システムのすべてのアレイについてｄ＝２の最小距離に、８つのストレージユニット故障が必要である。各アレイの最小距離がｄ＝２になったならば、もはや、システムの有効距離を増やすためにパリティ交換動作またはドッジング動作を実行することは不可能である。その結果、２つのさらなる故障が、データ消失をもたらす可能性がある。
【００４８】
経時的に、一般化されたドッジング動作は、もはや所与のアレイに局所的でないストライプをもたらす。したがって、ドナー・ストライプの選択を、ドナー要素の選択として実現することができる。
【００４９】
保守を介するなど、予備ユニットが使用可能になったならば、その予備ユニットを、故障したユニットのいずれかを交換するために割り当てることができる。最小の最小距離を有するストライプの要素を、予備ユニット上で再作成することが好ましい。図１３の例を検討されたい。アレイ１２００は、１０個のストレージ・ユニットＤ１〜Ｄ１０を含み、（３＋３）対称コードを使用する。アレイ１２００に、符号１〜５によって示された、５つのストライプも含まれる。各ストライプは、６つの要素を有し、距離ｄ＝４を有する。３つのストレージ・ユニットＤ１、Ｄ２、およびＤ４が、故障したものとして示され、ストライプ１の要素が、ユニットＤ１０のストライプ５の要素上でドッジング動作を介して再作成されており、ストライプ４の要素が、ユニットＤ８のストライプ５の第２の要素上でドッジング動作を介して再作成されている。この時点で、ストライプ１、２、４、および５のすべてが、距離ｄ＝２を有し、ストライプ３が、距離ｄ＝３を有する。その後、予備がアレイ１２００から使用可能にされた場合に、距離ｄ＝２のストライプからの情報を、その予備で再作成しなければならない。予備で再作成される要素は、ストライプ内に現在存在しない要素の組から選択されなければならない。たとえば、ユニットＤ２のストライプ１の要素が、ユニットＤ１０上で再作成され、ユニットＤ１からのストライプ４の要素が、ユニットＤ８上で再作成されたと仮定する。予備で再作成される要素に、ストライプ１および４の再作成される要素を含めることはできない。再作成される要素を選択したならば、情報が、周知の形で予備上で再作成される。
【００５０】
ドナー要素選択の主判断基準は、ドナー・ストライプ信頼性に対する最も少ない影響を有するドナー要素を選択することに基づく。副判断基準は、最も高価な冗長性計算を有する要素など、性能に対する最小の影響を有するストレージ要素を選択することに基づく。図１３の例では、主に、ストライプ５が最大の距離を有し、第２に、Ｄ８およびＤ１０が最も高価なパリティ計算を有するので、ストライプ５の要素が選択された。Ｄ９は、既にストライプ４の要素を含むので、ストライプ４の要素の再作成のために選択することができない。再作成される情報の選択の主判断基準は、信頼性の最大の向上をもたらす情報セットに基づく。副判断基準は、再作成動作の後に最善のアレイ性能をもたらす情報セットを選択することである。図１３の例では、ストライプ１および４の要素が、主に残りの距離に基づき、第２に選択された要素の再作成がドッジング動作の後に性能を最大にするので、再作成のために選択された。
【００５１】
一般化されたドッジングには、さらに重要な効果がある。図１０および１１の例で、一般化されたドッジング動作は、レシピエント・ストライプが距離ｄ＝２の時にアレイの間で実行されたが、内部ドッジング動作は、レシピエント・ストライプが距離ｄ＝１の時に９ユニット・アレイで実行された（図７および８）。したがって、外部ドッジング動作中のデータ消失のために、外部ドッジング動作に用いられるストライプ内で２つの故障が必要である。
【００５２】
ドナー・ストライプからレシピエント・ストライプへの寄贈は、ストレージ・システムがあるストライプから別のストライプに要素を割り当てることができることを必要とする。ドナー・ストライプおよびレシピエント・ストライプが、図１に示されているように共通のアレイ・コントローラ１０１に接続されている時には、コントローラ１０１が、この動作を内部で実行することができる。ドナー・ストライプおよびレシピエント・ストライプが、図２に示されているように別々のコントローラ１５１および１５２に接続されている時には、コントローラ１５１および１５２が、情報を交換する。たとえば、コントローラは、ＪＢＯＤ（Just a Bunch of Disks）アレイ構成の形のように、通信接続１６０を介して個々のドライブを公表することができる。その代わりに、コントローラが、用いられるストレージ・ユニットの位置から読み取られ、書き込まれるデータに関する情報を交換することができる。
【００５３】
ドッジングの技法を、アナモルフィック・アレイについて説明した。ドッジングは、最小距離ｄ＝３以上を有するアレイ・タイプと共に使用することができる。ただし、一般化されたドッジングは、対称アレイと共に最もよく働く。
【００５４】
ドッジングは、ストレージ・システムの最小距離を単純に増やすことを超えて使用することができる。多数の他の要因を、ドッジングを実行するかどうかの判定ならびにドナーおよびレシピエントの選択の判定に含めることができる。たとえば、不均一である時のコンポーネントの個々の故障確率、データ消失につながる故障の組合せ、およびシステム性能に対する影響のすべてを考慮することができる。その場合に、システムの最小距離を、ドッジングの後に変更されないままにすることができる。
【００５５】
本発明を、ＨＤＤストレージ・ユニットから形成されるストレージ・アレイに関して説明したが、本発明は、ランダム・アクセス・メモリ（ＲＡＭ）ストレージ・デバイス（揮発性と不揮発性の両方）、光ストレージ・デバイス、およびテープ・ストレージ・デバイスなどの他のメモリ・デバイスのアレイから形成されるストレージ・システムに適用可能である。さらに、本発明は、network attached storageから作られたアレイなど、仮想化されたストレージ・システムに適する。さらに、本発明は、冗長コンポーネントをコンポーネントの特定のサブセットに関連付ける状態情報があり、その状態情報を寄贈動作を使用して転送できるすべての冗長システムに適用可能である。
【００５６】
前述の発明は、理解を明瞭にするために詳細に説明されたが、添付請求項の範囲内である変更および修正を実践できることは明白である。したがって、本実施形態は、例示的であって制限的でないものと考えられなければならず、本発明は、本明細書で与えられた詳細に制限されるのではなく、添付請求項の範囲および同等物の中で変更することができる。
【図面の簡単な説明】
【００５７】
【図１】共通のストレージ・コントローラに接続された複数のアレイを有するストレージ・システムの通常の構成を示す図である。
【図２】別々のストレージ・コントローラに接続された複数のアレイを有するストレージ・システムの通常の構成を示す図である。
【図３】６つのストレージ・ユニットを有する例示的なアナモルフィック・アレイを示す図である。
【図４】本発明の実施形態によるドッジング動作の利益を示す、９つのストレージ・ユニットを有する例示的なアナモルフィック・アレイを示す図である。
【図５】図４に示されたアナモルフィック・アレイの第１の３ストレージユニット故障配置を示す図である。
【図６】図４に示されたアナモルフィック・アレイの第２の３ストレージユニット故障配置を示す図である。
【図７】本発明の実施形態によるドッジング動作を実行した後の図６のアレイを示す図である。
【図８】図４に示されたアナモルフィック・アレイの第３の３ストレージユニット故障配置を示す図である。
【図９】本発明の実施形態によるドッジング動作を実行した後の図８のアレイを示す図である。
【図１０】（３＋３）対称コードを使用する、８つのストレージ・ユニットを有する例示的なアレイを示す図である。
【図１１】３つの８ストレージユニット・アレイを有するシステムを示す図である。
【図１２】本発明の実施形態による外部ドッジング動作を実行した後の図１１のアレイ・システムを示す図である。
【図１３】ドッジング動作の組の後の３つの故障したストレージ・ユニットを有する１０ストレージ・ユニット・アレイを示す図である。
【符号の説明】
【００５８】
１００  ストレージ・システム
１０１  アレイ・コントローラ
１０２、１０３  ストレージ・アレイ
１０４  ストレージ・ユニット
１０５、１０６  インターフェース
１５０  ストレージ・システム
１５１、１５２  アレイ・コントローラ
１５３、１５４  ストレージ・アレイ
１５６、１５７、１５８、１５９  インターフェース
１６０  通信接続
２００  アレイ
３００  アナモルフィック・アレイ
９００  アレイ
１０００  アレイ・システム
１００１、１００２、１００３  アレイ
１２００  アレイ
【図１】
2007529061.tif 000002
【図２】
2007529061.tif 000003
【図３】
2007529061.tif 000004
【図４】
2007529061.tif 000005
【図５】
2007529061.tif 000006
【図６】
2007529061.tif 000007
【図７】
2007529061.tif 000008
【図８】
2007529061.tif 000009
【図９】
2007529061.tif 000010
【図１０】
2007529061.tif 000011
【図１１】
2007529061.tif 000012
【図１２】
2007529061.tif 000013
【図１３】
2007529061.tif 000014
2007529061.tif 000015
2007529061.tif 000016
2007529061.tif 000017
2007529061.tif 000018
2007529061.tif 000019
2007529061.tif 000020
2007529061.tif 000021
2007529061.tif 000022
2007529061.tif 000023
2007529061.tif 000024
2007529061.tif 000025
2007529061.tif 000026
【手続補正書】
【提出日】平成19年7月3日(2007.7.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ｍ個のストレージ・ユニットのアレイのエラー許容範囲を増やす方法であって、ｍ個のストレージ・ユニットの前記アレイにまたがってｋ個のストライプを保管するステップであって、各ストライプが複数の要素を有し、各ストライプが最小ハミング距離ｄを有する消去または誤り訂正コードを形成し、ストライプの各めいめいの要素が、異なるストレージ・ユニットに保管される、ステップと；ドナー・ストライプの最小距離とレシピエント・ストライプの最小距離との間の差が２以上の時に前記ドナー・ストライプ内の要素を選択するステップであって、前記選択された要素が、前記レシピエント・ストライプの要素を有しないストレージ・ユニットに保管される、ステップと；前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成するステップとを含む方法。
【請求項２】
前記消去または誤り訂正コードが、パリティ・コード；Ｗｉｎｏｇｒａｄコード；対称コード；リード−ソロモン・コード；ＥＶＥＮＯＤＤコード；またはＥＶＥＮＯＤＤコードの派生物のうちの１つである、請求項１に記載の方法。
【請求項３】
故障の選択されたパターンに脆弱なｍ個のストレージ・ユニットのアレイの故障許容範囲を増やす方法であって、ｍ個のストレージ・ユニットの前記アレイにまたがってｋ個のストライプを保管するステップであって、各ストライプが、複数の要素を有し、各ストライプが、最小ハミング距離ｄを有する消去または誤り訂正コードを形成し、ストライプの各めいめいの要素が、異なるストレージ・ユニットに保管される、ステップと；要素故障の後に、レシピエント要素を選択するステップと；前記アレイの故障許容範囲が再作成動作の後に増えるように、ドナー・ストライプ内の要素を選択するステップと；前記ドナー・ストライプの前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成するステップとを含む方法。
【請求項４】
ｍ個のストレージ・ユニットのアレイであって、ｋ個のストライプがｍ個のストレージ・ユニットの前記アレイにまたがって保管され、各ストライプが複数の要素を有し、各ストライプが最小ハミング距離ｄを有する消去または誤り訂正コードを形成し、ストライプの各めいめいの要素が、異なるストレージ・ユニットに保管される、ｍ個のストレージ・ユニットのアレイと；ドナー・ストライプの最小距離とレシピエント・ストライプの最小距離との間の差が２以上の時に前記ドナー・ストライプ内の要素を選択するシステム・アレイ・コントローラであって、前記選択された要素が、前記レシピエント・ストライプの要素を有しないストレージ・ユニットに保管される、システム・アレイ・コントローラとを有し；前記システム・アレイ・コントローラが、前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成するデータ・ストレージ・システム。
【請求項５】
前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成する前に、前記システム・アレイ・コントローラが、前記選択された要素が寄贈されたことを前記ドナー・ストライプを保管する前記ストレージ・ユニットに示す、請求項４に記載のデータ・ストレージ・システム。
【請求項６】
ｍ個のストレージ・ユニットの前記アレイが、アナモルフィック・アレイであり、各ストライプが、ｎ＋ｒ個の要素を含み、ｎが、ベース・アレイのデータ要素の個数であり、ｒが、ベース・アレイの冗長要素の個数であり、ｍ＞ｎ＋ｒ、ｊｍ＝ｋ（ｎ＋ｒ）であり、ｊおよびｋが整数である、請求項４に記載のデータ・ストレージ・システム。
【請求項７】
前記システム・アレイ・コントローラが、前記アレイに対する最小限の性能影響にさらに基づいて前記ドナー・ストライプを選択する、請求項４に記載のデータ・ストレージ・システム。
【請求項８】
前記システム・アレイ・コントローラが、前記アレイの改善された性能に基づいてレシピエント情報を選択する、請求項４に記載のデータ・ストレージ・システム。
【請求項９】
前記システム・アレイ・コントローラが前記選択された要素上で前記レシピエント・ストライプからレシピエント情報の少なくとも一部を再作成している時に前記ドナー・ストライプ内の要素が故障した時に、前記システム・アレイ・コントローラが、前記選択された要素上で前記レシピエント・ストライプから前記レシピエント情報を再作成するのを打ち切り、第２ドナー・ストライプの最小距離と第２レシピエント・ストライプの最小距離との間の差が２以上である時に前記複数のストライプから前記第２ドナー・ストライプを選択し、前記第２ドナー・ストライプ内でドナー要素を選択し、前記第２ドナー・ストライプ内の前記選択された要素上で前記レシピエント・ストライプから失われたレシピエント情報の少なくとも一部を再作成する、請求項４に記載のデータ・ストレージ・システム。
【請求項１０】
予備要素が使用可能になった時に、前記システム・アレイ・コントローラが、前記予備要素を選択されたストレージ・ユニットに割り当てる、請求項４に記載のデータ・ストレージ・システム。
【請求項１１】
ｍ個のストレージ・ユニットのアレイであって、ｋ個のストライプが、ｍ個のストレージ・ユニットの前記アレイにまたがって保管され、各ストライプが、複数の要素を有し、各ストライプが、最小ハミング距離ｄを有する消去または誤り訂正コードを形成し、ストライプの各めいめいの要素が、異なるストレージ・ユニットに保管される、ｍ個のストレージ・ユニットのアレイと；要素故障の後にレシピエント・ストライプを選択し、前記アレイの故障許容範囲が再作成動作の後に増えるように、ドナー・ストライプ内の要素を選択するシステム・アレイ・コントローラであって、前記システム・アレイ・コントローラが、前記ドナー・ストライプの前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成する、システム・アレイ・コントローラとを含むデータ・ストレージ・システム。
【請求項１２】
前記レシピエント・ストライプの最小ハミング距離が、前記システム・アレイ・コントローラが前記ドナー・ストライプ内の要素を選択する前にｄ≧２である、請求項４または１１に記載のデータ・ストレージ・システム。
【請求項１３】
前記アレイの最小ハミング距離が、前記ドナー・ストライプの前記選択された要素上での前記レシピエント・ストライプの前記失われた要素の再作成の完了時に増える、請求項１１に記載のデータ・ストレージ・システム。
【請求項１４】
ストレージ・ユニットの複数のアレイであって、各アレイが、ｍ個のストレージ・ユニットを有し、ｋ個のストライプが、ｍ個のストレージ・ユニットの各めいめいのアレイにまたがって保管され、各ストライプが、複数の要素を有し、各ストライプが、最小ハミング距離ｄ＝ｎ＋１を有する消去または誤り訂正コードを形成し、ストライプの各めいめいの要素が、前記アレイ内の異なるストレージ・ユニットに保管される、ストレージ・ユニットの複数のアレイと；
ドナー・ストライプの最小距離とレシピエント・ストライプの最小距離との間の差が２以上の時に前記ドナー・ストライプ内の要素を選択するシステム・アレイ・コントローラであって、前記選択された要素が、前記レシピエント・ストライプの要素を有しないストレージ・ユニットに保管され、前記システム・アレイ・コントローラが、前記選択された要素上で前記レシピエント・ストライプの失われた要素を再作成する、システム・アレイ・コントローラとを有するデータ・ストレージ・システム。
【国際調査報告】
2007529061.tif 000027
2007529061.tif 000028
2007529061.tif 000029