(57)【要約】  一般に、本発明の実施形態は、データを書き込む要求を受け取ること、要求に応答して、データを書き込むようＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置を選択すること、第１のＲＡＩＤグリッド位置に対応する持続性ストレージにおいて第１の物理アドレスを決定すること、データと、ＲＡＩＤグリッドについての第１のグリッドジオメトリおよびＲＡＩＤグリッド内のページについての第１のストライプメンバーシップを含む第１の帯域外（ＯＯＢ）とを含む第１のページを生成すること、ならびに、第１の物理アドレスに対応する持続性ストレージにおける第１の物理的位置に第１のページを書き込むことによってデータを格納することに関する。
2015535120.tif 000002
【特許請求の範囲】
【請求項１】
データを格納するための方法であって、
データを書き込む要求を受け取ることと、
前記要求に応答して、前記データを書き込むようＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置を選択することと、
前記第１のＲＡＩＤグリッド位置に対応する持続性ストレージにおいて第１の物理アドレスを決定することと、
前記データおよび第１の帯域外（ＯＯＢ）を含む第１のページを生成することとを含み、前記第１のＯＯＢは、ＲＡＩＤグリッドについての第１のグリッドジオメトリと、前記ＲＡＩＤグリッド内の前記ページについての第１のストライプメンバーシップとを含み、前記方法はさらに、
前記第１の物理アドレスに対応する持続性ストレージにおける第１の物理的位置に前記第１のページを書き込むことを含む、方法。
【請求項２】
前記データを使用して前記ＲＡＩＤグリッドのパリティ値を計算することと、
前記パリティ値を書き込むよう前記ＲＡＩＤグリッドにおける第２のＲＡＩＤグリッド位置を選択することと、
前記パリティ値および第２のＯＯＢを含む第２のページを生成することとをさらに含み、前記第２のＯＯＢは、第２のグリッドジオメトリおよび第２のストライプメンバーシップを含み、前記方法はさらに、
前記第２のＲＡＩＤグリッド位置に対応する持続性ストレージにおける第２の物理アドレスを決定することと、
前記第２の物理アドレスに対応する持続性ストレージにおける第２の物理的位置に前記第２のページを書き込むこととを含む、請求項１に記載の方法。
【請求項３】
前記ＲＡＩＤグリッドはパリティロウを含み、前記第２のＲＡＩＤグリッド位置は前記パリティロウに存在する、請求項２に記載の方法。
【請求項４】
前記データを書き込む要求を受け取ることの前に、
前記ＲＡＩＤグリッド内における複数の可能性のある位置の各々において不良な物理的位置の数を分析することと、
前記複数の可能性のある位置のうちの１つを前記パリティロウの位置として選択することとをさらに含み、前記複数の可能性のある位置の選択された前記１つは、他の複数の可能性のある位置に対して最小の数の不良な物理的位置を含む、請求項３に記載の方法。
【請求項５】
前記第１のストライプメンバーシップは、第１の次元についてのストライプメンバーシップと、前記ＲＡＩＤグリッドにおける第２の次元についてのストライプメンバーシップとを含み、前記第２のストライプメンバーシップは、前記第１の次元についての前記ストライプメンバーシップを含む、請求項２に記載の方法。
【請求項６】
前記第１のページは、前記ＲＡＩＤグリッドにおける第１のロウに存在し、前記第１のストライプメンバーシップは、前記第１のロウに対応する持続性ストレージにおけるどの物理的位置が不良かを示す、請求項５に記載の方法。
【請求項７】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドにおけるパリティ位置を含み、前記第２のグリッドジオメトリは、前記ＲＡＩＤグリッドにおける前記パリティ位置を含む、請求項２に記載の方法。
【請求項８】
前記パリティ値は、Ｐパリティ値、Ｑパリティ値およびインターセクションパリティ値からなる群から選択される少なくとも１つを含む、請求項２に記載の方法。
【請求項９】
前記第１のストライプメンバーシップはビットマップである、請求項１に記載の方法。
【請求項１０】
前記ＯＯＢはさらにグリッドマップを含み、前記グリッドマップは、前記ＲＡＩＤグリッドの第１の次元に対応する第１の独立した障害ドメイン（ＩＦＤ）と、前記ＲＡＩＤグリッドの第２の次元に対応する第２のＩＦＤとを識別する、請求項１に記載の方法。
【請求項１１】
前記第１のＩＦＤはストレージモジュールであり、前記第２のＩＦＤはチャンネルである、請求項１０に記載の方法。
【請求項１２】
前記持続性ストレージにおける前記第１の物理的位置が、少なくとも部分的に前記第１のＩＦＤおよび前記第２のＩＦＤを使用して特定される、請求項１０に記載の方法。
【請求項１３】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドにおける基準ＲＡＩＤグリッド位置に対する前記ＲＡＩＤグリッドにおける前記第１のページの相対位置を特定するセルフフィールドを含む、請求項１に記載の方法。
【請求項１４】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドの第１の次元の第１のサイズと前記ＲＡＩＤグリッドの第２の次元の第２のサイズとを特定するラストフィールドを含む、請求項１に記載の方法。
【請求項１５】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドの第１の次元における第１の数のパリティ値を特定するｎパリティフィールドを含む、請求項１に記載の方法。
【請求項１６】
前記ｎパリティフィールドはさらに、前記ＲＡＩＤグリッドの第２の次元において第２の数のパリティ値を特定する、請求項１５に記載の方法。
【請求項１７】
前記第１のＯＯＢは、前記ＯＯＢのフォーマットに対応するバージョンフィールドを含む、請求項１に記載の方法。
【請求項１８】
前記第１のＯＯＢは、前記第１のＯＯＢにおけるすべてのデータを使用して計算されるチェックサムを含む、請求項１に記載の方法。
【請求項１９】
データを再構築するための方法であって、
第１のデータについて要求を受け取ることと、
前記データを含む前記第１のページを得ることとを含み、前記第１のページは、持続性ストレージにおける第１の物理的位置から得られ、前記第１の物理的位置は、第１の物理アドレスと、ＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置とに関連付けられ、前記方法はさらに、
前記第１のページは、破損および未取得からなる群から選択されるものであることを決定を行うことを含み、前記方法はさらに、
前記決定に基づいて、
前記ＲＡＩＤグリッドにおける前記第１のＲＡＩＤグリッド位置の隣接ＲＡＩＤグリッド位置を識別することを含み、前記ＲＡＩＤグリッドはロウを含み、前記第１のＲＡＩＤグリッド位置および前記隣接グリッド位置は前記ロウに存在し、前記方法はさらに、
前記隣接ＲＡＩＤグリッド位置から第２のページを得ることと、
前記第２のページから帯域外（ＯＯＢ）データを得ることとを含み、前記ＯＯＢは、前記ＲＡＩＤグリッドについてのグリッドマップと、前記ＲＡＩＤグリッドについてのグリッドジオメトリと、前記ＲＡＩＤグリッド内の前記第２のページについてのストライプメンバーシップとを含み、前記方法はさらに、
前記グリッドジオメトリおよび前記ストライプメンバーシップを使用して、データページを含む前記ロウ内でＲＡＩＤグリッド位置を識別することと、
前記グリッドマップおよび前記グリッドジオメトリを使用して前記ロウ内の前記データページを得ることと、
前記グリッドジオメトリおよび前記ストライプメンバーシップを使用して、パリティ値を含む前記ロウにおけるＲＡＩＤグリッド位置を識別することと、
前記グリッドマップおよび前記グリッドジオメトリを使用して前記ロウ内の前記パリティ値を得ることと、
再構築されたページを得るよう、前記データページおよび前記パリティ値を使用して前記第１のページを再構築することと、
構築された前記ページから前記データを得ることと、
再構築された前記データをクライアントに提供することとを含む、方法。
【請求項２０】
前記グリッドマップは、前記ＲＡＩＤグリッドの第１の次元に対応する第１の独立した障害ドメイン（ＩＦＤ）と、前記ＲＡＩＤグリッドの第２の次元に対応する第２のＩＦＤとを識別し、
前記ストライプメンバーシップは、前記ロウに対応する持続性ストレージにおけるどの物理的位置が不良であるかを示し、
前記グリッドジオメトリは、前記ロウにおけるパリティ位置と、前記ＲＡＩＤグリッドにおける基準ページに対する前記ＲＡＩＤグリッドにおける前記第２のページの相対位置を特定するセルフフィールドとを含む、請求項１９に記載の方法。
【発明の詳細な説明】
【背景技術】
【０００１】
背景
ストレージシステムにおけるデータの潜在的な損失に対して保護するために、複製スキームを実施することがしばしば有利である。現在の複製スキームは、ストレージシステム内のデータを読み出すことができなくなる前に、限られた量のエラーに耐えることができるだけである。
【発明の概要】
【課題を解決するための手段】
【０００２】
概要
一般に、１つの局面において、本発明はデータを格納するための方法に関する。当該方法は、データを書き込む要求を受け取ることと、要求に応答して、データを書き込むようＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置を選択することと、第１のＲＡＩＤグリッド位置に対応する持続性ストレージにおいて第１の物理アドレスを決定することと、データおよび第１の帯域外（ＯＯＢ）を含む第１のページを生成することとを含み、第１のＯＯＢは、ＲＡＩＤグリッドについての第１のグリッドジオメトリと、ＲＡＩＤグリッド内のページについての第１のストライプメンバーシップとを含み、上記方法はさらに、第１の物理アドレスに対応する持続性ストレージにおける第１の物理的位置に第１のページを書き込むことを含む。
【０００３】
一般に、１つの局面において、本発明は、データを再構築するための方法に関する。当該方法は、第１のデータについて要求を受け取ることと、データを含む第１のページを得ることとを含み、第１のページは、持続性ストレージにおける第１の物理的位置から得られ、第１の物理的位置は、第１の物理アドレスと、ＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置とに関連付けられ、上記方法はさらに、第１のページは、破損および未取得からなる群から選択されるものであることを決定を行うことを含み、上記方法はさらに、決定に基づいて、ＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置の隣接ＲＡＩＤグリッド位置を識別することを含み、ＲＡＩＤグリッドはロウを含み、第１のＲＡＩＤグリッド位置および隣接グリッド位置はロウに存在し、上記方法はさらに、隣接ＲＡＩＤグリッド位置から第２のページを得ることと、第２のページから帯域外（ＯＯＢ）データを得ることとを含み、ＯＯＢは、ＲＡＩＤグリッドについてのグリッドマップと、ＲＡＩＤグリッドについてのグリッドジオメトリと、ＲＡＩＤグリッド内の第２のページについてのストライプメンバーシップとを含み、上記方法はさらに、グリッドジオメトリおよびストライプメンバーシップを使用して、データページを含むロウ内でＲＡＩＤグリッド位置を識別することと、グリッドマップおよびグリッドジオメトリを使用してロウ内のデータページを得ることと、グリッドジオメトリおよびストライプメンバーシップを使用して、パリティ値を含むロウにおけるＲＡＩＤグリッド位置を識別することと、グリッドマップおよびグリッドジオメトリを使用してロウ内のパリティ値を得ることと、再構築されたページを得るよう、データページおよびパリティ値を使用して第１のページを再構築することと、構築されたページからデータを得ることと、再構築されたデータをクライアントに提供することとを含む。
【０００４】
本発明の他の局面は、以下の記載および添付の請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【０００５】
【図１】本発明の一実施形態に従ったシステムを示す図である。
【図２】本発明の一実施形態に従ったＲＡＩＤグリッドを示す図である。
【図３】本発明の一実施形態に従ったＲＡＩＤキューブおよびＲＡＩＤキューブのさまざまな図を示す図である。
【図４Ａ】本発明の１つ以上の実施形態に従った、ＲＡＩＤキューブの例を示す図である。
【図４Ｂ】本発明の１つ以上の実施形態に従った、ＲＡＩＤキューブの例を示す図である。
【図４Ｃ】本発明の１つ以上の実施形態に従った、ＲＡＩＤキューブの例を示す図である。
【図４Ｄ】本発明の１つ以上の実施形態に従った、ＲＡＩＤキューブの例を示す図である。
【図５】Ａ〜Ｃは、本発明の１つ以上の実施形態に従ったページを示す図である。
【図６】本発明の一実施形態に従ったデータ構造を示す図である。
【図７Ａ】本発明の一実施形態に従ったフローチャートを示す図である。
【図７Ｂ】本発明の一実施形態に従ったフローチャートを示す図である。
【図７Ｃ】本発明の一実施形態に従ったフローチャートを示す図である。
【図７Ｄ】本発明の一実施形態に従ったフローチャートを示す図である。
【図８Ａ】本発明の１つ以上の実施形態に従った例を示す図である。
【図８Ｂ】本発明の１つ以上の実施形態に従った例を示す図である。
【図８Ｃ】本発明の１つ以上の実施形態に従った例を示す図である。
【図９Ａ】本発明の１つ以上の実施形態に従ったフローチャートを示す図である。
【図９Ｂ】本発明の１つ以上の実施形態に従ったフローチャートを示す図である。
【図１０Ａ】本発明の１つ以上の実施形態に従った例を示す図である。
【図１０Ｂ】本発明の１つ以上の実施形態に従った例を示す図である。
【図１０Ｃ】本発明の１つ以上の実施形態に従った例を示す図である。
【図１０Ｄ】本発明の１つ以上の実施形態に従った例を示す図である。
【図１１Ａ】本発明の１つ以上の実施形態に従った例を示す図である。
【図１１Ｂ】本発明の１つ以上の実施形態に従った例を示す図である。
【図１１Ｃ】本発明の１つ以上の実施形態に従った例を示す図である。
【図１１Ｄ】本発明の１つ以上の実施形態に従った例を示す図である。
【発明を実施するための形態】
【０００６】
詳細な説明
ここで、本発明の特定の実施形態を添付の図面を参照して詳細に記載する。本発明の実施形態の以下の詳細な説明において、本発明のより完全な理解を提供するために多くの特定の詳細が記載される。しかしながら、本発明がこれらの特定の詳細がなくても実施されてもよいことは当業者には明らかであろう。他の例では、説明を不必要に複雑にすることを回避するよう周知の機構は詳細に記載されない。
【０００７】
図１〜図１１Ｄの以下の説明では、本発明のさまざまな実施形態において図に関して記載される任意の構成要素は、任意の他の図に関して記載された同様の名称を有する１つ以上の構成要素と同等であり得る。簡潔さのために、これらの構成要素の説明は、各図に関して繰り返されない。したがって、各図の構成要素の各実施形態は、参照により援用され、同様の名称を有する１つ以上の構成要素を有する他のすべての図内に随意に存在すると想定される。さらに、本発明のさまざまな実施形態に従うと、ある図の構成要素の如何なる記載も、任意の他の図中の対応する同様の名称を有する構成要素に関して記載された実施形態に加えて、当該実施形態に関連して、または当該実施形態の代わりに実施されてもよい随意の実施形態として解釈されるべきである。
【０００８】
一般に、本発明の実施形態は、多次元ＲＡＩＤスキームを使用してデータを複製するための方法およびシステムに関する。より具体的には、本発明の実施形態は、２Ｄ  ＲＡＩＤスキームおよび３Ｄ  ＲＡＩＤスキームを実施するための方法およびシステムを提供する。さらに、本発明の実施形態は、ＲＡＩＤグリッド内の各ページに帯域外（out-of-band（ＯＯＢ））データを格納することと、当該ＯＯＢを使用してＲＡＩＤグリッド内でページを再構築することとに関する。さらに、本発明の実施形態は、パリティ値を格納するべきＲＡＩＤグリッドにおける位置を選択することに関し、このような選択は、存在する物理的な格納位置が不良であるかどうか（またはそうでなければ書き込むことができないかどうか）に部分的に基づく。
【０００９】
２Ｄ  ＲＡＩＤスキームを使用すると、所与のＲＡＩＤストライプにおいて２つより多いエラーが存在する場合、このようなＲＡＩＤスキームを実施するＲＡＩＤグリッド内に格納されたデータが回復され得る。同様に、３Ｄ  ＲＡＩＤスキームを使用すると、所与のＲＡＩＤストライプにおいて２つより多いエラーが存在する場合、このようなＲＡＩＤスキームを実施するＲＡＩＤキューブ内に格納されたデータが回復され得る。さらに、本発明のさまざまな実施形態において、１つより多い独立した障害ドメイン（independent fault domain（ＩＦＤ））に故障がある場合、すべてのデータが回復され得る。
【００１０】
本発明の１つ以上の実施形態において、ＩＦＤは、所与の位置のデータがアクセス不能になる故障モードに対応する。各ＩＦＤは、ストレージアレイにおける故障の独立したモードに対応する。たとえば、（いくつかの実施形態においてフラッシュメモリとも称され得る）（複数のＮＡＮＤダイを含む）ストレージモジュールの一部であるＮＡＮＤフラッシュにデータが格納される場合、ＩＦＤは、（ｉ）ストレージモジュール、（ｉｉ）チャンネル（すなわち、ＮＡＮＤフラッシュにデータを書き込む、ストレージモジュールにおけるフラッシュコントローラ（図示せず）によって使用されるチャンネル）、および（ｉｉｉ）ＮＡＮＤダイであり得る。
【００１１】
この発明の目的のために、本願明細書において使用される「ＲＡＩＤ」という用語は、「独立ディスク冗長アレイ（Redundant Array of Independent Disks)」を指す。「ＲＡＩＤ」は独立したディスクの任意のアレイを指しているが、本発明の実施形態は、本発明の実現例に基づいて、ＲＡＩＤグリッド位置（たとえば図２参照）が１つ以上の持続性ストレージデバイスに亘って分散され得る任意のタイプの持続性ストレージデバイスを使用して実施されてもよい（たとえば図１および図６参照）。
【００１２】
本発明の１つ以上の実施形態において、ＲＡＩＤグリッド内における各ページにＯＯＢを格納することによって、ＲＡＩＤグリッド内のページは、他の外部のデータ構造に依存する代わりに、ＲＡＩＤグリッド内に格納されたデータを使用して再構築されることが可能になる。特に、所与のページにおけるＯＯＢは、当該所与のページが位置するストライプにおけるページの再構築を可能にするのに十分な情報を含む。さらに、ＯＯＢのさまざまな部分は、ＲＡＩＤグリッドにおけるすべてのページにわたって複製され、したがって、ＯＯＢ情報は、付加的な外部のデータ構造を必要とすることなく、ＲＡＩＤグリッドの有意な部分の再構築を可能にするよう使用され得る。ＯＯＢは、それが記述するユーザデータ（以下に規定される）と同じ位置に配置されるので、ＲＡＩＤグリッド内におけるページの再構築は、ＲＡＩＤコントローラ以外のプロセッサに容易にオフロードされ得る。
【００１３】
図１は、本発明の一実施形態に従ったシステムを示す。図１に示されるように、このシステムは、１つ以上のクライアント（１００Ａ，１００Ｍ）と、ＲＡＩＤコントローラ（１０４）と、メモリ（１０６）と、ＦＰＧＡ（１０２）（随意に存在してもよい）と、ストレージアレイ（１０８）とを含む。
【００１４】
本発明の一実施形態において、クライアント（１００Ａ，１００Ｍ）は、読出要求または書込要求をＲＡＩＤコントローラ（１０４）に発行する機能を含む任意のシステムまたはシステム上で実行するプロセスである。本発明の一実施形態において、クライアント（１００Ａ，１００Ｍ）は各々、プロセッサ（図示せず）と、メモリ（図示せず）と、持続性ストレージ（図示せず）とを含んでもよい。本発明の一実施形態において、ＲＡＩＤコントローラ（１０４）は、多次元ＲＡＩＤスキームに一致する態様でストレージアレイにデータを書き込むこと（図７Ａ〜図７Ｄ参照）と、多次元ＲＡＩＤスキームに一致する態様でストレージアレイからデータを読み出すこと（データを再構成することを含む）（図９Ａ〜図９Ｂ参照）とを含む多次元ＲＡＩＤスキームを実施するように構成される。本発明の一実施形態において、ＲＡＩＤコントローラ（１０４）は、本発明の１つ以上の実施形態を実施するよう命令を実行するように構成されるプロセッサを含む。当該命令は、ＲＡＩＤコントローラ（１０４）内に位置するかまたはＲＡＩＤコントローラ（１０４）に動作可能に接続される一時的でないコンピュータ読取可能媒体（図示せず）上に格納される。代替的には、ＲＡＩＤコントローラ（１０４）は、ハードウェアを使用して実施されてもよい。当業者であれば、ＲＡＩＤコントローラ（１０４）がソフトウェアおよび／またはハードウェアの任意の組合せを使用して実施されてもよいことを理解するであろう。
【００１５】
本発明の一実施形態では、ＲＡＩＤコントローラ（１０４）は、メモリ（１０６）に動作可能に接続される。メモリ（１０６）は、任意の揮発性メモリまたは不揮発性メモリであってもよい。当該揮発性メモリは、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、シンクロナスＤＲＡＭ、ＳＤＲ  ＳＤＲＡＭおよびＤＤＲ  ＳＤＲＡＭを含むが、これらに限定されない。本発明の一実施形態において、メモリ（１０６）は、（パリティデータを含む）さまざまなデータがストレージアレイに格納される前にこのようなデータを一時的に格納するように構成される。
【００１６】
本発明の一実施形態において、ＦＰＧＡ（１０２）（存在する場合）は、ストレージアレイ（１０８）にデータを格納するためにＰおよび／もしくはＱパリティ値を計算する機能、ならびに／または多次元ＲＡＩＤスキームを使用して格納された破損データまたは消失データを回復するのに必要なさまざまな計算を行なう機能を含む。発明の一実施形態において、ＦＰＧＡは、ＯＯＢを使用して、破損データの回復を行なう機能を含み得る。ＲＡＩＤコントローラ（１０４）は、本発明の１つ以上の実施形態に従って、さまざまなデータの処理をオフロードするようＦＰＧＡ（１０２）を使用し得る。
【００１７】
本発明の一実施形態において、ストレージアレイ（１０８）は、多くの個々の持続性ストレージデバイスを含む。当該持続性ストレージデバイスは、磁気メモリデバイス、光学メモリデバイス、ソリッドステートメモリデバイス、相変化メモリデバイス、任意の他の好適なタイプの持続メモリデバイス、またはその任意の組合せを含むがこれらに限定されない。本発明の一実施形態において、各ストレージアレイ（１０８）は、多くのストレージモジュールを含み得、各ストレージモジュールは、ソリッドステートメモリおよびストレージモジュールコントローラを含む。このような実施形態において、ストレージモジュールコントローラは、ＲＡＩＤコントローラからページを受け取るとともにソリッドステートメモリにおいて対応する物理的位置にページを書き込む機能を含む。さらに、ストレージモジュールコントローラは、ページがソリッドステートメモリに書き込まれる前に、各ページについて誤り訂正符号（error-correcting code（ＥＣＣ））を生成する機能を含み得る。さらに、ストレージモジュールコントローラは、図９Ａ〜図９Ｂに従ってページを再構築する機能を含み得る。
【００１８】
図１はＦＰＧＡを示しているが、当業者であれば、本発明はＦＰＧＡがなくても実施され得るということを理解するであろう。さらに当業者であれば、本発明から逸脱することなく、ＦＰＧＡの代わりに他の構成要素が使用されてもよいことを理解するであろう。たとえば本発明は、ＡＳＩＣ、グラフィックスプロセッシングユニット（ＧＰＵ）、汎用プロセッサ、ストレージアレイにデータを格納する目的のためにＰおよび／もしくはＱパリティ値を計算することができならびに／または多次元ＲＡＩＤスキームを使用して格納された破損データを回復するのに必要なさまざまな計算を行うことができる任意の他のハードウェアデバイス、ストレージアレイ（１０８）にデータを格納するためにＰおよび／もしくはＱパリティ情報を計算しならびに／または多次元ＲＡＩＤスキームを使用して格納された破損データを回復するのに必要なさまざまな計算を行なうよう構成されるハードウェア、ファームウェアおよび／もしくはソフトウェアの組み合わせを含む任意のデバイス、またはその任意の組合せを使用して実施されてもよい。
【００１９】
図２は、本発明の一実施形態に従ったＲＡＩＤグリッドを示す。本発明の一実施形態において、ＲＡＩＤコントローラが２Ｄ  ＲＡＩＤスキームまたは３Ｄ  ＲＡＩＤスキームを実施する場合（図３を参照）、ＲＡＩＤコントローラはＲＡＩＤグリッド（２００）にデータを格納する。図２は、本発明の１つ以上の実施形態に従ったＲＡＩＤグリッドの概念部分を示す。ＲＡＩＤグリッド（２００）は、多くのＲＡＩＤグリッド位置を含んでおり、各ＲＡＩＤグリッド位置は、ストレージアレイにおけるユニークな物理アドレスに最終的に書き込まれる。ＲＡＩＤグリッド（２００）は、（ｉ）クライアントから受け取られるデータ（すなわち、クライアントがストレージアレイに書き込むようにＲＡＩＤコントローラに指示したデータ）を格納するＲＡＩＤグリッド位置を含むデータグリッド（２０２）と、（ｉｉ）（以下に記載される）ロウでのＲＡＩＤグリッド位置におけるデータを用いて計算されるＰパリティ値に格納するＲＡＩＤグリッド位置を含むロウＰパリティグループ（２０４）と、（ｉｉｉ）（以下に記載される）ロウでのＲＡＩＤグリッド位置におけるデータを用いて計算されるＱパリティ値に格納するＲＡＩＤグリッド位置を含むロウＱパリティグループ（２０６）と、（ｉｖ）（以下に記載される）カラムでのＲＡＩＤグリッド位置におけるデータを用いて計算されるＰパリティ値に格納するＲＡＩＤグリッド位置を含むカラムＰパリティグループ（２０８）と、（ｖ）（以下に記載される）カラムでのＲＡＩＤグリッド位置におけるデータを用いて計算されるＱパリティ値に格納するＲＡＩＤグリッド位置を含むカラムＱパリティグループ（２１０）と、（ｖｉ）（ａ）ロウＰパリティグループ（２０４）におけるＲＡＩＤグリッド位置からのデータ、（ｂ）ロウＱパリティグループ（２０６）におけるＲＡＩＤグリッド位置からのデータ、（ｃ）カラムＰパリティグループ（２０８）におけるＲＡＩＤグリッド位置からのデータ、および（ｄ）カラムＱパリティグループ（２１０）におけるＲＡＩＤグリッド位置からのデータ（以下に記載）、を使用して計算されるパリティ値を含むインターセクションパリティグループ（２１２）とを含む。
【００２０】
ロウ（２１４）を参照して、本発明の一実施形態において、ロウ（２１４）においてＰｒ２として示されるＲＡＩＤグリッド位置に格納されるデータは、データを含むロウ（２１４）中のすべてのＲＡＩＤグリッド位置にＰパリティ関数を適用することによって計算される（たとえばＰｒ２＝ｆＰ（Ｄ１，Ｄ２，Ｄ３，Ｄ４）。同様に、本発明の一実施形態において、ロウ（２１４）中のＱｒ２として示されるＲＡＩＤグリッド位置に格納されるデータは、データを含むロウ（２１４）中のすべてのＲＡＩＤグリッド位置にＱパリティ関数を適用することにより計算される（たとえばＱｒ２＝ｆＱ（Ｄ１，Ｄ２，Ｄ３，Ｄ４）。
【００２１】
カラム（２１６）を参照して、本発明の一実施形態において、カラム（２１６）におけるＰｃ６として示されるＲＡＩＤグリッド位置に格納されるデータは、データを含むカラム（２１６）中のすべてのＲＡＩＤグリッド位置にＰパリティ関数を適用することにより計算される（たとえばＰＣ６＝ｆＰ（Ｄ５，Ｄ２，Ｄ６，Ｄ７）。同様に、本発明の一実施形態において、カラム（２１６）におけるＱＣ６によって示されるＲＡＩＤグリッド位置に格納されるデータは、データを含むカラム（２１６）中のすべてのＲＡＩＤグリッド位置にＱパリティ関数を適用することにより計算される（たとえばＱＣ６＝ｆＱ（Ｄ５，Ｄ２，Ｄ６，Ｄ７）。
【００２２】
インターセクションパリティグループ（２１２）を参照して、本発明の一実施形態において、Ｉｒ１として示されるＲＡＩＤグリッド位置に格納されるデータは、ロウＰパリティグループ（２０４）中のすべてのＲＡＩＤグリッド位置にＰパリティ関数を適用することによってか、またはカラムＰパリティグループ（２０８）中のすべてのＲＡＩＤグリッド位置にＰパリティ関数を適用することによって計算され得る。たとえば、Ｉｒ１＝ｆＰ（Ｐｒ１，Ｐｒ２，Ｐｒ３，Ｐｒ４）またはＩｒ１＝ｆＰ（Ｐｃ５，Ｐｃ６，Ｐｃ７，Ｐｃ８）である。
【００２３】
本発明の一実施形態において、Ｉｒ２として示されるＲＡＩＤグリッド位置に格納されたデータは、ロウＱパリティグループ（２０４）中のすべてのＲＡＩＤグリッド位置にＰパリティ関数を適用することによって、またはカラムＰパリティグループ（２０８）中のすべてのＲＡＩＤグリッド位置にＱパリティ関数を適用することによって計算され得る。たとえば、Ｉｒ２＝ｆＰ（Ｑｒ１，Ｑｒ２，Ｑｒ３，Ｑｒ４）またはＩｒ２＝ｆＱ（Ｐｃ５，Ｐｃ６，Ｐｃ７，Ｐｃ８）である。
【００２４】
本発明の一実施形態において、Ｉｒ３として示されるＲＡＩＤグリッド位置に格納されたデータは、カラムＰパリティグループ（２１０）中のすべてのＲＡＩＤグリッド位置にＰパリティ関数を適用することによってか、またはロウＰパリティグループ（２０４）中のすべてのＲＡＩＤグリッド位置にＱパリティ関数を適用することによって計算され得る。たとえば、Ｉｒ３＝ｆＰ（Ｑｃ５，Ｑｃ６，Ｑｃ７，Ｑｃ８）またはＩｒ３＝ｆＱ（Ｐｃ１，Ｐｃ２，Ｐｃ３，Ｐｃ４）である。
【００２５】
本発明の一実施形態において、Ｉｒ４として表示されるＲＡＩＤグリッド位置に格納されたデータは、カラムＱパリティグループ（２１０）中のすべてのＲＡＩＤグリッド位置にＱパリティ関数を適用することによってか、またはロウＱパリティグループ（２０６）中のすべてのＲＡＩＤグリッド位置にＱパリティ関数を適用することによって計算され得る。たとえば、Ｉｒ４＝ｆＱ（Ｑｃ１，Ｑｃ２，Ｑｃ３，Ｑｃ４）またはＩｒ４＝ｆＱ（Ｑｃ５，Ｑｃ６，Ｑｃ７，Ｑｃ８）である。
【００２６】
本発明の一実施形態において、パリティグループのすべてについての値を計算するために使用されるＰおよびＱパリティ関数は、ＲＡＩＤ６を実施するために使用される任意のＰおよびＱパリティ関数に対応し得る。
【００２７】
上で論じたように、図２に示されるＲＡＩＤグリッド（２００）は、ＲＡＩＤグリッドの概念的なレイアウトを示す。しかしながら、個々のＲＡＩＤグリッド位置がストレージアレイに書き込まれると、さまざまなＲＡＩＤグリッド位置の相対位置は、ロウおよび／またはカラムに亘って変動し得る。たとえば、ロウ（２１４）を参照して、ロウ（２１４）の内におけるＲＡＩＤグリッド位置がストレージアレイに書き込まれる場合、データ（「Ｄ」で示される）を含むＲＡＩＤグリッド位置と、パリティデータを含むＲＡＩＤグリッド位置（すなわち「Ｐｒ」および「Ｑｒ」として示されるＲＡＩＤグリッド位置）との相対位置は、＜Ｄ１，Ｄ２  Ｐｒ２，Ｄ３  Ｑｒ２，Ｄ４＞、＜Ｐｒ２，Ｑｒ２，Ｄ１，Ｄ２，Ｄ３，Ｄ４＞、またはロウ（２１４）における任意の他の構成であり得る。同様に、カラム（２１６）を参照して、データ（「Ｄ」で示される）を含むＲＡＩＤグリッド位置と、パリティデータを含むＲＡＩＤグリッド位置（すなわち「Ｐｃ」および「Ｑｃ」として示されるＲＡＩＤグリッド位置）との相対位置は、＜Ｄ５，Ｄ２，Ｄ６，Ｐｃ６，Ｄ６，Ｑｃ６＞、＜Ｐｃ６，Ｄ５，Ｄ２，Ｑｃ６，Ｄ６，Ｄ７＞、またはカラム（２１６）内における任意の他の構成であり得る。
【００２８】
本発明の一実施形態において、（ｉ）ロウＰパリティグループ、（ｉｉ）ロウＱパリティグループ、（ｉｉｉ）カラムＰパリティグループ、および（ｉｖ）カラムＱパリティグループの各々の位置は、図７Ａに示される方法に従って決定される。このような実施形態において、インターセクションパリティグループの位置は、前述のパリティグループの位置に基づいて決定される（図８Ａ参照）。
【００２９】
図２の議論を継続して、ＲＡＩＤコントローラ（またはシステムにおける別のエンティティ）は、ストレージアレイにおけるどの物理アドレスにＲＡＩＤグリッド位置の各々が書き込まれるかを決定し得る。この決定は、クライアントから特定のＲＡＩＤグリッドについて（「Ｄ」として示される）データのいずれかを受け取る前になされ得る。代替的には、この決定は、ストレージアレイにＲＡＩＤグリッド位置を書き込む前になされ得る。
【００３０】
当業者であれば、図２は６×６であるＲＡＩＤグリッドを示すが、ＲＡＩＤグリッドは、本発明から逸脱することがなければ任意の他の次元を使用して実施されてもよいということを理解するであろう。
【００３１】
本発明の一実施形態において、Ｐパリティ値は、リードソロモンシンドロームであり、したがって、Ｐパリティ関数は、リードソロモンシンドロームを生成し得る任意の関数に対応し得る。本発明の一実施形態では、Ｐパリティ関数はＸＯＲ関数である。
【００３２】
本発明の一実施形態において、Ｑパリティ値はリードソロモンシンドロームであり、したがって、Ｑパリティ関数は、リードソロモンシンドロームを生成し得る任意の関数に対応し得る。本発明の一実施形態では、Ｑパリティ値はリードソロモン符号である。本発明の一実施形態において、Ｑ＝ｇ０・Ｄ０＋ｇ１・Ｄ１＋ｇ２・Ｄ２＋．．．＋ｇｎ−１・Ｄｎ−１であり、式中、Ｑは、図２に関して規定されたＱパリティ値のうちのいずれか１つに対応し、ｇはフィールドのジェネレータであり、Ｄの値は（データグリッドからの値および／またはＰもしくはＱパリティ値の両方を含む１つ以上のロウまたはカラムからの値を含み得る）データに対応する。
【００３３】
当業者であれば、図２におけるＲＡＩＤグリッドは各ロウおよびカラムごとにＰおよびＱパリティを含むが、本発明の実施形態は、本発明から逸脱することがなければ、より多いまたはより少ないパリティ値を使用して実施され得るということを理解するであろう。たとえば、各ロウおよびカラムはＰパリティ値のみを含んでもよい。別の例では、各ロウおよびカラムは３つのパリティ値を含んでもよい。上記の例は、本発明を限定するようには意図されない。本発明の一実施形態において、本発明の実現例において使用されるパリティ値の数に関わらず、パリティ値の各々はリードソロモンシンドロームである。
【００３４】
図３は、本発明の一実施形態に従った、ＲＡＩＤキューブおよびＲＡＩＤキューブのさまざまな図を示す。図３に示されるように、ＲＡＩＤキューブ（３００）は、ＲＡＩＤグリッド（３０２）の概念的なスタックに対応する。上で論じたように、ＲＡＩＤコントローラ（またはシステムにおける別のエンティティ）は、ＲＡＩＤグリッド位置の各々についてデータを格納するべきストレージアレイ内の物理アドレスを選択する。本発明の一実施形態において、物理アドレスの選択は、それに対してＲＡＩＤグリッド（またはＲＡＩＤキューブ）が保護するよう設計されるＩＦＤに従って決定され得る。換言すると、物理アドレスは、１つ以上のＩＦＤにおける障害から保護する態様で選択され得る。たとえば、図３に示されるように、所与のＲＡＩＤグリッド（３０２，３０４）についての各ＲＡＩＤグリッド位置（図示せず）は、ＩＦＤ１およびＩＦＤ２からの値のユニークな対を使用して選択されるがＩＦＤ３については同じ値を有する、ストレージアレイ（図示せず）における物理アドレスに書き込まれる（または物理アドレスに書き込まれることになる）。たとえば、（複数のＮＡＮＤダイを含む）ストレージモジュールの一部であるストレージアレイ中のデータがＮＡＮＤフラッシュに格納される場合、ＩＦＤは、（ｉ）ＩＦＤ１＝ストレージモジュール、（ｉｉ）ＩＦＤ１＝チャンネル、および（ｉｉｉ）ＩＦＤ３＝ＮＡＮＤダイ、であり得る。したがって、所与のＲＡＩＤグリッドにおいて、各ＲＡＩＤグリッド位置におけるデータがストレージモジュール（ＩＦＤ１）およびチャンネル（ＩＦＤ２）のユニークな組合せに書き込まれるが、（ストレージモジュールの各々上の）同じＮＡＮＤダイに書き込まれる。当業者であれば、本発明が上記の３つの独立した障害ドメインに限定されないことを理解するであろう。さらに、当業者であれば、本発明がＮＡＮＤフラッシュを含むストレージアレイに限定されないことを理解するであろう。
【００３５】
図３を引き続き参照して、上で論じたように、ＲＡＩＤキューブ（３００）はＲＡＩＤグリッドの概念的なスタックである。より具体的には、本発明の一実施形態において、ＲＡＩＤキューブ（３００）は、（ｉ）２つ以上のＲＡＩＤグリッド（３０４，３０６，３０８，３１０）（図２参照）を含むデータ部分（３１６）と、ＰパリティＲＡＩＤグリッド（３１２）およびＱパリティＲＡＩＤグリッド（３１４）を含むパリティ部分（３１８）とを含み得る。
【００３６】
本発明の一実施形態において、データ部分（３１６）中のＲＡＩＤグリッド（３０４，３０６，３０８，３１０）は、ＲＡＩＤグリッド内のデータ（パリティデータを含む）のみを使用してＲＡＩＤグリッド内のデータが回復されることを可能にするパリティデータ（図２参照）を含む。本発明の一実施形態において、ＲＡＩＤキューブは、（データ部分（３１６）およびパリティ部分（３１８）の両方における）他のＲＡＩＤグリッドからのデータ（パリティデータを含む）を用いて、所与のＲＡＩＤグリッド（３０４，３０６，３０８，３１０）における所与のＲＡＩＤグリッド位置についてのデータが回復され得るように構成される。本発明の一実施形態では、ＲＡＩＤキューブのパリティ部分（３１８）は、このような回復メカニズムを可能にする。
【００３７】
本発明の一実施形態において、ＰパリティＲＡＩＤグリッド（３１２）は、存在するＲＡＩＤグリッド（３０４，３０６，３０８，３１０）と同じ次元である。データ部分（３１６）中のＲＡＩＤグリッドからのデータ（パリティデータを含む）にＰパリティ関数（たとえばＸＯＲ関数）を適用することによって、ＰパリティＲＡＩＤグリッド内のすべてのＲＡＩＤグリッド位置におけるデータが計算される（図４Ａ〜図４Ｄ参照）。同様に、ＱパリティＲＡＩＤグリッド（３１４）は、存在するＲＡＩＤグリッド（３０４，３０６，３０８，３１０）と同じ次元である。データ部分（３１６）中のＲＡＩＤグリッドからのデータ（パリティデータを含む）にＱパリティ関数を適用することによって、ＱパリティＲＡＩＤグリッド内のすべてのＲＡＩＤグリッド位置におけるデータが計算される（図４Ａ〜図４Ｄ参照）。
【００３８】
図４Ａ〜図４Ｄは、本発明の１つ以上の実施形態に従った、ＲＡＩＤキューブをポピュレートする（投入する）例を示す。この例は、本発明の範囲を限定するようには意図されない。
【００３９】
図４Ｄに示されるＲＡＩＤキューブを考えると、当該ＲＡＩＤキューブは、ＲＡＩＤグリッドＡ（４００）と、ＲＡＩＤグリッドＢ（４０２）と、ＲＡＩＤグリッドＣ（４０４）と、ＰパリティＲＡＩＤグリッド（４０６）と、ＱパリティＲＡＩＤグリッド（４０８）とを含む。さらに、ＲＡＩＤキューブにおける各ＲＡＩＤグリッド（４００，４０２，４０４，４０６，４０８）は、ＩＦＤ１およびＩＦＤ２に亘って書き込まれるが一定の値のＩＦＤ３を有するＲＡＩＤグリッド位置を含む。したがって、本発明の一実施形態において、ＲＡＩＤグリッドにおけるＲＡＩＤグリッド位置（「ターゲットＲＡＩＤグリッド位置」）の値は、（ｉ）ターゲットＲＡＩＤグリッド位置が位置するロウまたはカラムにおけるＲＡＩＤグリッド位置の値のみか、（ｉｉ）ターゲットＲＡＩＤグリッド位置が位置するＲＡＩＤグリッド内の任意のＲＡＩＤグリッド位置の値か、または（ｉｉｉ）ターゲットＲＡＩＤグリッド位置が位置するＲＡＩＤキューブ内の任意のＲＡＩＤグリッド位置の値を使用して回復され得る。換言すると、本発明の一実施形態においては、ターゲットＲＡＩＤグリッド位置が位置するロウおよびカラムの各々において２つより多いエラーが存在する場合、ＲＡＩＤグリッドおよび／またはＲＡＩＤキューブ内におけるデータおよびパリティ値の構成によってターゲットＲＡＩＤグリッド位置における値が回復されることが可能になる。
【００４０】
図４Ａを参照して、図４Ａは、ＲＡＩＤキューブのデータ部分を構成する３つのＲＡＩＤグリッド（４００，４０２，４０４）を含む。ＲＡＩＤグリッド（４００，４０２，４０４）の各々におけるＲＡＩＤグリッド位置の各々は、ＲＡＩＤグリッド位置におけるデータが書き込まれるストレージアレイにおける位置を規定する３タプルを含む。この例において、３タプルにおける要素は、＜ＩＦＤ１，ＩＦＤ２，ＩＦＤ３＞というＩＦＤに対応する。この３タプルは、ストレージアレイにおける位置がどのようにさまざまなＩＦＤに亘って選択されるかを示す。特に、ＲＡＩＤグリッドＡにおけるＲＡＩＤグリッド位置の各々は、ＩＦＤ１およびＩＦＤ２のユニークな組合せを含むがＩＦＤ３については同じ値を含む。たとえば、ＩＦＤ１がストレージモジュールである場合、ＩＦＤ２はチャンネルであり、ＩＦＤ３はＮＡＮＤダイであり、３タプル＜４，２，１＞は、特定のＲＡＩＤグリッド位置におけるデータが、チャンネル２を使用して、ストレージモジュール４中のＮＡＮＤダイ１における物理アドレスに書き込まれることになるということを示す。同様に、３タプル＜２，３，１＞は、特定のＲＡＩＤグリッド位置におけるデータが、チャンネル３を使用して、ストレージモジュール２中のＮＡＮＤ１における物理アドレスに書き込まれることになるということを示す。
【００４１】
ＲＡＩＤグリッドＢ（４０２）およびＲＡＩＤグリッドＣ（４０４）は、ＲＡＩＤグリッドＡ（４００）と同様の態様で構成される。しかしながら、ＲＡＩＤグリッドＢ（４０２）におけるＲＡＩＤグリッド位置についての３タプル中のＩＦＤ３についての値は、ＲＡＩＤグリッドＡ（４００）についてのＲＡＩＤグリッド位置についての３タプル中のＩＦＤ３の値と異なる。さらに、ＲＡＩＤグリッドＣ（４０４）についてのＲＡＩＤグリッド位置についての３タプル中のＩＦＤ３についての値は、ＲＡＩＤグリッドＡ（４００）およびＲＡＩＤグリッドＢ（４０２）についてのＲＡＩＤグリッド位置についての３タプル中のＩＦＤ３の値と異なる。
【００４２】
図４Ｂを参照して、ＰパリティＲＡＩＤグリッド（４０６）におけるＲＡＩＤグリッド位置の各々中のデータは、ＲＡＩＤグリッドＡ（４００）、ＲＡＩＤグリッドＢ（４０２）およびＲＡＩＤグリッドＣ（４０４）と同様の態様で構成される。さらに上述したように、ＰパリティＲＡＩＤグリッド（４０６）におけるＲＡＩＤグリッド位置の各々中のデータの値は、ＲＡＩＤキューブ（すなわちＲＡＩＤグリッドＡ（４００）、ＲＡＩＤグリッドＢ（４０２）、ＲＡＩＤグリッドＣ（４０４））におけるデータグリッド各々中の１つのＲＡＩＤグリッド位置からのデータを使用して計算される。たとえば、ＰパリティＲＡＩＤグリッド（４０６）におけるＲＡＩＤグリッド位置＜１，１，４＞のデータの値は、Ｐパリティ関数（たとえばＸＯＲ関数）を、（ｉ）ＲＡＩＤグリッドＡ（４００）＜１，１，１＞からのデータ、（ｉｉ）ＲＡＩＤグリッドＢ（４０２）＜１，１，２＞からのデータ、および（ｉｉｉ）ＲＡＩＤグリッドＣ（４０４）＜１，１，３＞からのデータ、といったＲＡＩＤグリッド位置からのデータに適用することにより決定される。ＰパリティＲＡＩＤグリッド（４０６）における他のＲＡＩＤグリッド位置中のデータついての値は、同様の態様で計算される。
【００４３】
図４Ｃを参照して、ＱパリティＲＡＩＤグリッド（４０８）におけるＲＡＩＤグリッド位置の各々中のデータは、ＲＡＩＤグリッドＡ（４００）、ＲＡＩＤグリッドＢ（４０２）およびＲＡＩＤグリッドＣ（４０４）と同様の態様で構成される。さらに上述したように、ＱパリティＲＡＩＤグリッド（４０８）におけるＲＡＩＤグリッド位置の各々中のデータの値は、ＲＡＩＤキューブ（すなわちＲＡＩＤグリッドＡ（４００）、ＲＡＩＤグリッドＢ（４０２）、ＲＡＩＤグリッドＣ（４０４））におけるデータグリッド各々中の１つのＲＡＩＤグリッド位置からのデータを使用して計算される。たとえば、ＱパリティＲＡＩＤグリッド（４０８）におけるＲＡＩＤグリッド位置＜１，１，５＞でのデータの値は、（上述したように）Ｑパリティ関数を、（ｉ）ＲＡＩＤグリッドＡ（４００）＜１，１，１＞からのデータ、（ｉｉ）ＲＡＩＤグリッドＢ（４０２）＜１，１，２＞からのデータ、および（ｉｉｉ）ＲＡＩＤグリッドＣ（４０４）＜１，１，３＞からのデータ、といったＲＡＩＤグリッド位置からのデータに適用することにより決定される。ＱパリティＲＡＩＤグリッド（４０８）における他のＲＡＩＤグリッド位置中のデータついての値は、同様の態様で計算される。
【００４４】
図５Ａ〜図５Ｃは、本発明の１つ以上の実施形態に従ったページを示す。本発明の一実施形態において、ＲＡＩＤグリッドにおける各ＲＡＩＤ位置（図２、図３、および図４Ａ〜図４Ｄ参照）は、ページ（５００）を格納するように構成される。図５Ａを参照して、ページ（５００）は、ユーザデータ（５０２）と、帯域外（ＯＯＢ）データ（５０４）と、誤り訂正符号（ＥＣＣ）（５０６）とを含む。本発明の一実施形態において、ユーザデータ（５０２）は、クライアントから受け取られた任意のデータと、クライアントから受け取られたデータから直接的にまたは間接的に導出される任意のデータとに対応する。たとえば、ユーザデータは、（ｉ）クライアントから受け取られたデータから直接的に導出されるＰおよびＱパリティ値と、（ｉｉ）前述のＰおよび／またはＱパリティ値から導出されるインターセクションパリティ値（図２の２１２参照）とを含み得る。
【００４５】
本発明の一実施形態において、ＯＯＢ（５０４）は、ＲＡＩＤグリッド（すなわちＯＯＢを含むページが格納されるＲＡＩＤグリッド）に関する情報と、ＯＯＢ（５０４）を含むページ（５００）に関する情報とを提供するデータに対応する。ＯＯＢ（５０４）に関する付加的な詳細は図５Ｂに記載される。
【００４６】
本発明の一実施形態において、ＥＣＣ（５０６）は、ユーザデータ（５０２）およびＯＯＢ（５０４）の組合せのために生成される。したがって、ＥＣＣ（５０６）は、ユーザデータ（５０２）およびＯＯＢ（５０４）におけるエラーを識別し、潜在的に修正するために使用され得る。本発明の一実施形態において、本発明から逸脱することがなければ、ＥＣＣは任意のタイプの誤り訂正符号を使用して計算されてもよい。使用されるＥＣＣのタイプに依存して、ＥＣＣは単に、エラーを検出可能であるが、必ずしもユーザデータおよびＯＯＢ（５０４）におけるエラーを修正しなくてもよい。
【００４７】
図５Ｂは、本発明の１つ以上の実施形態に従ったページ（５００）についてのＯＯＢ（５０４）を示す。図５Ｂに示されるように、ＯＯＢ（５０４）は、（ｉ）バージョン（５０８）フィールドと、（ｉｉ）グリッドマップ（５１０）と、（ｉｉｉ）グリッドジオメトリ（５１２）と、（ｉｖ）ストライプメンバーシップ（ＳＭ）（５１４）と、（ｖ）チェックサム（５１６）とを含む。これらのコンポーネントの各々は以下に記載される。
【００４８】
本発明の一実施形態において、バージョン（５０８）フィールドは、ＯＯＢについてのＯＯＢフォーマットのバージョンを特定する。本発明の一実施形態において、このバージョン（５０８）フィールドは、ページを再構築するためにＯＯＢを使用するエンティティ（図９Ａ〜図９Ｂ参照）がＯＯＢにおける各データが何を指すかを理解することを確実にするように含まれる。本発明の一実施形態において、バージョン（５０８）フィールドは整数を使用して表わされる。
【００４９】
本発明の一実施形態において、グリッドマップ（５１０）は、ページ（５００）が位置するＲＡＩＤグリッドにおける各次元に関連付けられる独立した障害ドメインを特定する。たとえば、第１のＩＦＤがストレージモジュールであって第２のＩＦＤがチャンネルである場合、グリッドマップ（５１０）はこの情報をビットマップへとエンコードする。
【００５０】
本発明の一実施形態において、グリッドジオメトリ（５１２）は、ＲＡＩＤグリッドのジオメトリに関する情報と、ＲＡＩＤグリッドにおけるページ（５００）の位置とを特定する。グリッドジオメトリ（５１２）に関する付加的な詳細は、図５Ｃに記載される。
【００５１】
本発明の一実施形態において、ＳＭ（５１４）は、ページ（５００）が含まれる各次元についてビットマップを含む。したがって、ページ（５００）がＲＡＩＤグリッドに含まれている場合、ＳＭは２つのビットマップ、すなわち、各次元につき１つ、を含む。さらに、ページ（５００）がＲＡＩＤキューブに含まれている場合、ＳＭは３つのビットマップ、すなわち、各次元につき１つ、を含む。ＳＭにおける各ビットマップは、その次元についてストライプ内において不良な物理的位置を識別する。より具体的には、ＲＡＩＤグリッドにおける各ＲＡＩＤグリッド位置は持続性ストレージにおける物理的位置に関連付けられる。（たとえば持続性ストレージの作製における物理的な欠陥により）ページを特定の物理的位置に書き込むことができない場合、この物理的位置は不良な物理的位置として指定される。本発明の一実施形態において、不良な物理的位置は「０」で指定され、ストライプにおける他のすべての物理的位置は「１」で指定される。本発明から逸脱することがなければ、他のビットマップエンコードスキームが使用されてもよい。
【００５２】
本発明の一実施形態において、チェックサム（５１６）は、ＯＯＢにおける他のすべてのデータ（たとえばバージョンフィールド、グリッドマップ、グリッドジオメトリおよびＳＭ）のチェックサムに対応し、ＯＯＢにおけるデータの完全性を保証するように使用される。本発明の一実施形態において、チェックサムは、本発明から逸脱することがなければ、任意の適切なチェックサム関数（たとえばＳＨＡ−１、ＭＤ５、ＳＨＡ−２５６）を使用して計算されてもよい。
【００５３】
図５Ｃを参照して、グリッドジオメトリ（５１２）は、（ｉ）セルフ（５１８）フィールドと、（ｉｉ）ラスト（５２０）フィールドと、（ｉｉｉ）ｎパリティ（５２２）フィールドと、（ｉｖ）１つ以上のパリティ位置（５２４，５２６）とを含む。これらのコンポーネントの各々は以下に記載される。
【００５４】
本発明の一実施形態において、セルフ（５１８）フィールドは、ＲＡＩＤグリッド内におけるページ（５００）の位置を含む。本発明の一実施形態において、当該位置はタプルとして表わされ、このタプルにおける各エントリは所与のＩＦＤにおける位置に対応する（図８Ｂのセルフを参照）。本発明の一実施形態において、セルフ（５１８）フィールドにおける位置は相対位置である。相対位置は、ＲＡＩＤグリッドにおける基準ＲＡＩＤグリッド位置に対して特定される。本発明の一実施形態において、基準ＲＡＩＤグリッド位置はＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置である（図８Ａの８１４を参照）。
【００５５】
本発明の一実施形態において、ラスト（５２０）フィールドは、ＲＡＩＤグリッドの最後のカラムおよびロウ番号を特定する。たとえば、図８Ａを参照して、ＲＡＩＤグリッド（８００）は６×６グリッドであり、したがって、（番号付けが０にて開始するので）ラスト（５２０）フィールドは＜５，５＞を特定する。
【００５６】
本発明の一実施形態において、ｎパリティ（５２２）フィールドは、ＲＡＩＤグリッドの各次元においてパリティ値の数を特定する。たとえば、ＰパリティおよびＱパリティが所与の次元において計算されると、ｎパリティ（５２２）フィールドは、その次元について「２」を含むことになる。
【００５７】
本発明の一実施形態において、グリッドジオメトリは、各次元における各タイプのパリティについて１つのパリティ位置（５２４，５２６）を含む。たとえば、ＲＡＩＤグリッドが両方の次元においてＰおよびＱパリティを含む場合、グリッドジオメトリは、Ｐパリティロウグループ、Ｑパリティロウグループ、ＰパリティカラムグループおよびＱパリティカラムグループのパリティ位置を含む。本発明の一実施形態において、パリティ位置は、各次元（たとえばロウおよびカラム）に基づき、各パリティタイプ上で特定される（たとえば図８ＢのＰ，Ｑ参照）。
【００５８】
本発明の一実施形態において、バージョン（５０８）、グリッドマップ（５１０）、ラスト（５２０）フィールド、ｎパリティ（５２２）フィールドおよびパリティ位置（５２４，５２６）は、ＲＡＩＤグリッド内における各ページ（５００）において同じである。本発明の一実施形態において、この複製は、ストライプにおけるすべての読み取り可能なグリッド位置がストライプ内の任意のグリッド位置の回復を可能にする必要なすべての情報を有することを保証する。
【００５９】
当業者であれば、図５Ａ〜図５Ｃは、２Ｄ  ＲＡＩＤスキームにおけるページについてのＯＯＢを記載する（たとえばＲＡＩＤグリッド）が、本発明から逸脱することがなければ、ＯＯＢ（５０４）は、ｎ次元のＲＡＩＤスキームについての情報を含んでもよいということを理解するであろう。さらに、当業者であれば、本発明の実施形態は、本発明から逸脱することなければ、（たとえばＰ、ＱおよびＲパリティを使用する）より多いパリティ値または（たとえばＰパリティを使用する）より少ないパリティ値を用いて実現されてもよいということを認識するであろう。
【００６０】
図５Ａ〜図５Ｃは、ページに格納されるさまざまなタイプのデータを示すが、本発明の実施形態は、本発明から逸脱することがなければ、付加的な（または異なる）データおよび／またはデータの異なる順序を含むページを用いて実現されてもよい。さらに、ＯＯＢ内のさまざまなフィールドにおける値は、本発明から逸脱することがなければ、任意のエンコーディングスキームを使用してエンコードされてもよい。
【００６１】
図６は、本発明の一実施形態に従ったデータ構造を示す。本発明の一実施形態において、ＲＡＩＤコントローラは、多次元ＲＡＩＤスキームを実施するよう１つ以上のデータ構造を含む。
【００６２】
本発明の一実施形態において、ＲＡＩＤコントローラは、クライアントによって提供されるデータとストレージアレイにおけるこのようなデータの物理アドレスとの間のマッピングをトラッキングするデータ構造を含む。本発明の一実施形態において、ＲＡＩＤコントローラは、クライアントのパースペクティブからデータを識別するたとえば＜オブジェクト，オフセット＞（６００）といった論理アドレスと、ストレージアレイ内のデータの位置を識別する物理アドレス（６０２）との間のマッピングを使用して、上記の情報をトラッキングする。本発明の一実施形態において、当該マッピングは、ハッシュ関数（たとえばＭＤ５，ＳＨＡ１）を＜オブジェクト，オフセット＞に適用することによって導出されるハッシュ値と対応する物理アドレス（６０２）との間であり得る。当業者であれば、本発明から逸脱することがなければ、如何なる形態の論理アドレスも使用されてもよいということを理解するであろう。
【００６３】
本発明の一実施形態において、ＲＡＩＤコントローラは、各ＲＡＩＤグリッド位置（６０４）（図２参照）がどのようにストレージアレイにおける特定の物理アドレス（６０２）にマッピングされるかをトラッキングするデータ構造を含む。
【００６４】
本発明の一実施形態において、ＲＡＩＤコントローラは、（ＲＡＩＤコントローラが３Ｄ  ＲＡＩＤスキームを実施していると仮定して）どのＲＡＩＤグリッド（データ部分およびパリティ部分におけるＲＡＩＤグリッドを含む）（６０８）がどのＲＡＩＤキューブ（６０６）に関連付けられるかと、さらにどのＲＡＩＤグリッド位置（６０４）が各ＲＡＩＤグリッド（６０８）に関連付けられるかとをトラッキングするデータ構造を含む。
【００６５】
本発明の一実施形態において、ＲＡＩＤコントローラは、各ＲＡＩＤグリッド位置（６０４）の状態（６１０）をトラッキングするデータ構造を含む。本発明の一実施形態において、ＲＡＩＤグリッド位置の状態（６１０）は、充填（ページがＲＡＩＤグリッド位置に書き込まれたことを示す）または空（何もＲＡＩＤグリッド位置に書き込まれていないことを示す）としてセットされ得る。本発明の一実施形態において、ＲＡＩＤコントローラはまた、ＲＡＩＤコントローラがＲＡＩＤグリッド位置に書き込むべきデータを識別した場合、ＲＡＩＤグリッド位置の状態を充填にセットし得る（図７Ｂのステップ７２０を参照）。ＲＡＩＤグリッドが最初に作成される場合（図７Ａ参照）、ＲＡＩＤコントローラは最初に、各ＲＡＩＤグリッド位置の状態を空にセットし得る。
【００６６】
本発明の一実施形態において、ＲＡＩＤコントローラは、ＲＡＩＤグリッドジオメトリをトラッキングするデータ構造を含む。本発明の一実施形態において、ＲＡＩＤグリッドジオメトリは、ＲＡＩＤグリッドのサイズと、ＲＡＩＤグリッドの各次元に関連付けられるＩＦＤとを含んでもよいがこれらに限定されない。このデータ構造（または別のデータ構造）はさらに、ＲＡＩＤキューブのサイズと、ＲＡＩＤキューブの各次元に関連付けられるＩＦＤとをトラッキングし得る。
【００６７】
本発明の一実施形態において、ＲＡＩＤコントローラは、各ＲＡＩＤグリッド内の各ロウおよび／またはカラム内において、（インターセクションパリティグループ内のパリティ値を含む（図２を参照））各ＰおよびＱパリティ値の位置をトラッキングするデータ構造を含む。
【００６８】
本発明の一実施形態において、ＲＡＩＤコントローラは、ＲＡＩＤキューブのデータ部分中のどのＲＡＩＤグリッド位置が、ＰパリティＲＡＩＤグリッドおよびＱパリティＲＡＩＤグリッド中のＰおよびＱパリティ値の各々を計算するよう使用されるかをそれぞれトラッキングするデータ構造を含み得る。
【００６９】
図７Ａ〜図７Ｄは、本発明の１つ以上の実施形態に従ったフローチャートを示す。より具体的には、図７Ａ〜図７Ｄは、本発明の１つ以上の実施形態に従った、ストレージアレイにデータを格納するための方法を示す。フローチャートにおけるさまざまなステップが順次、提示および記載されるが、当業者であれば、ステップのうちのいくつかまたはすべてが異なる順番で実行されてもよいこと、ステップのうちのいくつかまたはすべてが組み合わせられてもよくまたは省略されてもよいこと、およびステップのうちのいくつかまたはすべてが並列に実行されてもよいことを理解するであろう。本発明の一実施形態において、図７Ａ〜図７Ｄに示される方法は並列で行なわれてもよい。
【００７０】
図７Ａを参照して、図７Ａは、本発明の１つ以上の実施形態に従った、ＲＡＩＤグリッドをセットアップしてＲＡＩＤグリッド内のパリティロウおよびカラムの位置を選択するための方法を示す。
【００７１】
ステップ７００では、ＲＡＩＤグリッドについての独立した障害ドメイン（ＩＦＤ）が得られる。本発明の一実施形態において、ＩＦＤは、物理アドレスを構成する要素から選択される。たとえば、物理アドレスは、＜ストレージモジュール（ＦＭ），チャンネル（ＣＨ），チップイネーブル（ＣＥ），ＬＵＮ，プレーン，ブロック，ページ，バイト＞といったタプルを使用して表わされ得る。この例において、ＩＦＤは、ＦＭ、ＣＨ、ＣＥおよび／またはＬＵＮであり得る。
【００７２】
ステップ７０２では、ＲＡＩＤグリッドにおける各次元のサイズが得られる。本発明の一実施形態において、各次元のサイズは、各次元にわたって格納されるページの数を特定する。たとえば、図２において、ＲＡＩＤグリッド（２００）における各次元のサイズは６である。当業者であれば、各次元のサイズが同じである必要がないことを認識するであろう。
【００７３】
ステップ７０４では、ＲＡＩＤグリッドへの包含のために、ＩＦＤとＲＡＩＤグリッドにおける各次元のサイズとに基づき持続性ストレージにおける物理的位置が選択される。たとえば、ＲＡＩＤグリッドが４×４である場合、ＲＡＩＤグリッドについて、１６個の物理的位置が選択（別の態様では識別）される必要がある。さらに、各物理的位置が＜ＦＭ，ＣＨ，ＣＥ，ＬＵＮ，プレーン，ブロック，ページ，バイト＞といったタプルによって規定されるとともにＩＦＤがＦＭおよびＣＨである場合、ＲＡＩＤグリッドについての物理的位置が表１に示される。
【００７４】
【表１】
2015535120.tif 000003
【００７５】
表１を参照して、物理的位置番号１に対応する物理アドレスは、ＲＡＩＤグリッドにおける第１の物理的位置に対応する。残りの物理アドレスにおけるすべての要素は、ＩＦＤに対応する要素、すなわちＦＭおよびＣＨを除いて同一である。表１に示されるように、２つのＩＦＤに及ぶ物理アドレスを得るために、これらの要素の値がインクリメントされる。特に、各次元のサイズが４であるので、ＦＭの値はＦＭからＦＭ＋３まで変化し、ＣＨの値はＣＨからＣＨ＋３まで変化する。上記の例は、物理アドレスにおけるさまざまな要素が整数を使用してインクリメントされているのを示しているが、本発明から逸脱することがなければ、これらの要素は他の値を使用してインクリメントされてもよい。当業者であれば、所与のストライプにおけるグリッド位置についての物理アドレスは（たとえば表１に示されるように）順次である必要がなく、むしろ、本発明を実現する１つ以上のプロセスは、物理アドレスが外部データを参照することなく決定され得るように、なんらかの決定メカニズムを使用して物理アドレスを確認することができることを必要とするだけであるということを理解するであろう。
【００７６】
図７Ａを引き続き参照して、ステップ７０６では、各次元におけるパリティ値の数が決定される。たとえば、各次元が１つ、２つまたは３つのパリティ値を有するかどうかに関して決定がなされる。当業者であれば、本発明が１次元につき３つのパリティ値に限定されないことを理解するであろう。さらに、当業者であれば、パリティ値の数は各次元について同じである必要がないということを理解するであろう。
【００７７】
ステップ７０８では、ＩＦＤが選択される。ステップ７１０では、ＩＦＤにおける物理的位置のすべての他のロウまたはカラムに対して不良物理的位置の数が最小である（ステップ７０８で選択された）ＩＦＤに沿った物理的位置のロウまたはカラムが識別される。ステップ７１２では、ステップ７１０において識別されたロウ／カラムは、ＲＡＩＤグリッドにパリティ値を格納するように選択される（図８Ａ参照）。
【００７８】
ステップ７１４では、パリティ値を格納するべき付加的なロウ／カラムがＩＦＤに必要かどうかに関して決定がなされる。より具体的には、ＩＦＤが（ステップ７０６で特定されたように）ロウ／カラムにつき１つより多いパリティ値を必要とする場合、プロセスはステップ７１０に進み、そうでなければ、プロセスはステップ７１６に進む。ステップ７１６では、（ステップ７０６で特定されたように）ＲＡＩＤグリッドにおける他のＩＦＤにパリティ値を格納する任意のロウ／カラムが必要かどうかに関して決定がなされる。パリティ値を格納すべきロウ／カラムが他のＩＦＤのために必要な場合、プロセスはステップ７０８に進み、そうでなければプロセスは終了する。この段階で、ＲＡＩＤグリッドは、ページでポピュレートされる（投入される）準備ができている（図５Ａ〜図５Ｃ参照）。
【００７９】
図７Ｂを参照して、ステップ７１８において、データを書き込む要求がクライアントから受け取られる。本発明の一実施形態において、要求は、クライアントのパースペクティブからデータを識別する＜オブジェクト，オフセット＞（すなわち論理アドレス）を含む。ステップ７２０において、ＲＡＩＤコントローラは、当該要求に応答して、ＲＡＩＤコントローラメモリにおける位置にデータを書き込む。
【００８０】
ステップ７２２において、ＲＡＩＤコントローラは、データ構造の１つ以上を更新する（図６参照）。より具体的には、本発明の一実施形態において、ＲＡＩＤコントローラは、（ｉ）クライアントから受け取られたデータを書き込むべきストレージアレイにおける物理的位置に対応する物理アドレスを選択し、（ｉｉ）データについての＜オブジェクト，オフセット＞と選択された物理アドレスとの間のマッピングを作成し得る。
【００８１】
本発明の一実施形態において、図７Ｃは、本発明の１つ以上の実施形態に従った、ストレージアレイにＲＡＩＤグリッドを書き込むための方法を示す。図７Ｃを参照して、ステップ７２４において、所与のＲＡＩＤグリッド（たとえば図２における２０２）内のデータグリッドが充填されているかどうかについて決定がなされる。本発明の一実施形態において、この決定は、図６に関して記載されたデータ構造の１つ以上を使用してなされる。所与のＲＡＩＤグリッド内のデータグリッドが充填されている場合、当該プロセスはステップ７２６に進み、そうでなければプロセスは終了する。
【００８２】
ステップ７２６において、Ｐパリティが、データグリッドにおけるＲＡＩＤグリッド位置からの適切な値を使用してロウＰパリティグループ（たとえば図２における２０４）中の各ＲＡＩＤグリッド位置について計算される。ステップ７２８において、Ｑパリティが、データグリッドにおけるＲＡＩＤグリッド位置からの適切な値を使用してロウＱパリティグループ（たとえば図２における２０６）中の各ＲＡＩＤグリッド位置について計算される。ステップ７３０において、Ｐパリティが、データグリッドにおけるＲＡＩＤグリッド位置からの適切な値を使用してカラムＰパリティグループ（たとえば図２における２０８）中の各ＲＡＩＤグリッド位置について計算される。ステップ７３２において、Ｑパリティが、データグリッドにおけるＲＡＩＤグリッド位置からの適切な値を使用してカラムＱパリティグループ（たとえば図２における２１０）中の各ＲＡＩＤグリッド位置について計算される。
【００８３】
ステップ７３４において、インターセクションパリティグループ（たとえば図２における２１２）中のすべてのＲＡＩＤグリッド位置についてのパリティ値が、ロウＰパリティグループ（たとえば図２における２０４）、ロウＱパリティグループ（たとえば図２における２０６）、カラムＰパリティグループ（たとえば図２における２０８）、およびカラムＱパリティグループ（たとえば図２における２１０）の１つ以上において、ＲＡＩＤグリッド位置からの適切な値を使用して計算される。
【００８４】
ステップ７３６では、持続性ストレージに書き込まれるべき各ページについてのＯＯＢが得られ、（図５Ａにおいて規定されるような）ユーザデータに添付される。本発明の一実施形態において、ＯＯＢについての情報は、ＲＡＩＤコントローラによって取得され、そうでなければ提供される。すべてのＯＯＢデータ（チェックサムを除く）がひとたび得られると、ＯＯＢデータを使用してチェックサムが計算され、ＯＯＢに加えられる（図５Ｂ参照）。この段階では、（ユーザデータおよびＯＯＢを含む）ページは、持続性ストレージにおいて特定された物理アドレスに書き込まれる準備ができている。
【００８５】
ステップ７３８では、当該ページについてＥＣＣが計算される。ＥＣＣは、入力としてユーザデータおよびＯＯＢを使用して計算される。本発明の一実施形態において、ＥＣＣはＲＡＩＤコントローラによって計算され、ページに添付される（図５Ａ参照）。代替的には、ページ（ＥＣＣを除く）は、ストレージモジュールコントローラへ送信され得る。ページ（ＥＣＣを除く）の受け取りの際、ストレージモジュールコントローラは、ＥＣＣを計算し、（ＥＣＣとともに）ページを持続性ストレージに書き込む前にページにＥＣＣを添付する。
【００８６】
ステップ７４０において、ＲＡＩＤグリッドについての各ＲＡＩＤグリッド位置に関連付けられるページ（ＥＣＣを含む）は、ストレージアレイにおいて適切な物理アドレスに書き込まれる。本発明の一実施形態において、ＲＡＩＤグリッド位置の各々についてページを書き込むべき物理アドレスは、図６に関して記載されたデータ構造の１つ以上から得られる。ステップ７４２において、図６に関して記載された１つ以上のデータ構造は、ＲＡＩＤグリッドがストレージアレイに書き込まれたことを反映するよう更新される。
【００８７】
本発明の一実施形態において、ＲＡＩＤコントローラが３Ｄ  ＲＡＩＤスキームを実施している場合、ＲＡＩＤコントローラは、図７Ｄに示される方法を行なってもよい。図７Ｄを参照して、ステップ７４４において、ＲＡＩＤキューブのデータ部分が充填されているかどうかに関して決定がなされる。ＲＡＩＤキューブのデータ部分が充填されていれば、プロセスはステップ７４６に進み、そうでなければプロセスは終了する。本発明の一実施形態において、この決定は、図６に関して記載されたデータ構造の１つ以上を使用してなされる。
【００８８】
ステップ７４６において、ＰパリティＲＡＩＤグリッド中の各ＲＡＩＤグリッド位置についてのＰパリティ値（たとえば図３における３１２）が計算される。本発明の一実施形態において、ＲＡＩＤグリッド位置の各々についてのパリティ値が、ＲＡＩＤキューブのデータ部分（たとえば図４Ｂ参照）におけるＲＡＩＤグリッドの各々から得られる１つの値を使用して計算される。
【００８９】
ステップ７４８において、ＱパリティＲＡＩＤグリッド（たとえば図３における３１４）における各ＲＡＩＤグリッド位置についてのＱパリティ値が計算される。本発明の一実施形態において、ＲＡＩＤグリッド位置の各々についてのパリティ値が、ＲＡＩＤキューブのデータ部分（たとえば図４Ｃ）におけるＲＡＩＤグリッドの各々から得られる１つの値を使用して計算される。
【００９０】
ステップ７５０では、持続性ストレージに書き込まれるべき各ページについてのＯＯＢが得られ、（図５Ａにおいて規定されるような）ユーザデータに添付される。本発明の一実施形態において、ＯＯＢについての情報は、ＲＡＩＤコントローラによって取得され、そうでなければ提供される。すべてのＯＯＢデータ（チェックサムを除く）がひとたび得られると、ＯＯＢデータを使用してチェックサムが計算され、ＯＯＢに加えられる（図５Ｂ参照）。この段階では、（ユーザデータおよびＯＯＢを含む）ページは、持続性ストレージにおいて特定された物理アドレスに書き込まれる準備ができている。
【００９１】
ステップ７５２では、当該ページについてＥＣＣが計算される。ＥＣＣは、入力としてユーザデータおよびＯＯＢを使用して計算される。本発明の一実施形態において、ＥＣＣはＲＡＩＤコントローラによって計算され、ページに添付される（図５Ａ参照）。代替的には、ページ（ＥＣＣを除く）は、ストレージモジュールコントローラへ送信され得る。ページ（ＥＣＣを除く）の受け取りの際、ストレージモジュールコントローラは、ＥＣＣを計算し、（ＥＣＣとともに）ページを持続性ストレージに書き込む前にページにＥＣＣを添付し得る。
【００９２】
ステップ７５４において、パリティＲＡＩＤグリッド（たとえばＰパリティＲＡＩＤグリッドおよびＱパリティＲＡＩＤグリッド）における各ＲＡＩＤグリッド位置に関連付けられるページ（ＥＣＣを含む）は、ストレージアレイにおいて適切な物理アドレスに書き込まれる。本発明の一実施形態において、ＲＡＩＤグリッド位置の各々についてページを書き込むべき物理アドレスは、図６に関して記載されたデータ構造の１つ以上から得られる。ステップ７５６において、図６に関して記載された１つ以上のデータ構造は、ＲＡＩＤキューブがストレージアレイに書き込まれたことを反映するよう更新される。
【００９３】
図８Ａ〜図８Ｃは、本発明の１つ以上の実施形態に従った例示的なＲＡＩＤグリッドを示す。この例は、本発明の範囲を限定するようには意図されない。
【００９４】
図８Ａを参照して、図８ＡはＲＡＩＤグリッド（８００）を含む。ＲＡＩＤグリッド（８００）は、各次元において２つのパリティ値を有する６×６グリッドである。クライアントからのデータを含むＲＡＩＤグリッド位置は「Ｄ」で示され、パリティ値を含むＲＡＩＤグリッド位置はＰ、ＱまたはＩとして示され、不良物理的位置に関連付けられるＲＡＩＤグリッド位置は黒く塗りつぶした正方形として示される。
【００９５】
この例の目的のために、物理的位置（８１４）は基準ＲＡＩＤグリッド位置であるとする。したがって、基準ＲＡＩＤグリッド位置の位置は＜０，０＞である。最後に、この例の目的のために、ＩＦＤはフラッシュメモリ（ＦＭ）およびチャンネル（ＣＨ）である。
【００９６】
当該例を参照して、ロウ（８１６）および（８１８）が（図７Ａに示される方法を使用して）パリティロウとして選択され、カラム（８１２）および（８２０）がパリティカラムとして選択される。より具体的には、ＲＡＩＤグリッド（８００）は６つのロウを含み、そのうちの３つは如何なる不良物理的位置も含んでいない。したがって、ＩＦＤ１にわたってパリティ値を格納するために、前述の３つのロウのうちいずれか２つが選択され得る。同様に、ＲＡＩＤグリッド（８００）は６つのカラムを含み、そのうちの３つは如何なる不良物理的位置も含んでいない。したがって、ＩＦＤ２にわたってパリティ値を格納するために、前述の３つのカラムのうちいずれか２つが選択され得る。インターセクションパリティグループに対応するＲＡＩＤグリッド位置は、パリティ値が格納されるさまざまなロウおよびカラムの交点に位置する。
【００９７】
上記の情報に基づいて、ＲＡＩＤグリッド位置（８０４）および（８０８）に格納されたページについてのＯＯＢは、図８Ｂおよび図８Ｃに示される情報を含む。図８Ｂを参照して、図８Ｂは、ＲＡＩＤグリッド位置（８０２）に格納されるページについてのＯＯＢ（８２２）を示す。具体的には、ＯＯＢのバージョンは１であり、これはＯＯＢフォーマット番号１を示す。さらに、グリッドマップは１１を示し、これはＦＭおよびＣＨが２つのＩＦＤであることを示すエンコードされたビットマップに対応する。グリッドジオメトリに関して、（ｉ）セルフフィールドは、ＲＡＩＤグリッド位置（８０２）に格納されるページがＲＡＩＤグリッド（８００）のカラム１，ロウ０に存在することを示す＜１，０＞を含み、（ｉｉ）ラストフィールドは、ＲＡＩＤグリッドが６×６（各次元における番号付けが０にてスタートする）であることを示す＜５，５＞を特定し、（ｉｉｉ）ｎパリティフィールドは、各次元が２つのパリティ値を含むことを示す＜２，２＞を特定し、（ｉｖ）（パリティ位置フィールドのうちの１つである）Ｐフィールドは、ロウＰパリティグループがＲＡＩＤグリッドの第３のカラム（８１２）に存在するとともにカラムＰパリティグループがＲＡＩＤグリッドの第３のロウ（８１６）に存在することを示す＜２，２＞を特定し、（ｖ）（パリティ位置フィールドのうちの１つである）Ｑフィールドは、ロウＱパリティグループがＲＡＩＤグリッドの第５のロウ（８２０）に存在するとともにカラムＱパリティグループがＲＡＩＤグリッドの第６のロウ（８１８）に存在することを示す＜４，５＞を特定する。最後に、ＲＡＩＤグリッド位置（８０２）におけるページについてのストライプメンバーシップは＜０１１１１１，１１１１１１＞であり、これは、ＲＡＩＤグリッド位置（８１４）に対応する物理的位置が不良であることを示す０を有するロウ（８０６）およびカラム（８０４）に沿ったストライプメンバーシップを含む。
【００９８】
図８Ｃは、ＲＡＩＤグリッド位置（８０８）に格納されたページについてのＯＯＢ（８２４）を示す。具体的には、ＯＯＢのバージョンは１であり、これはＯＯＢフォーマット番号１を示す。さらに、グリッドマップは１１を示しており、これは、ＦＭおよびＣＨが２つのＩＦＤであることを示すエンコードされたビットマップに対応する。グリッドジオメトリに関して、（ｉ）セルフフィールドは、ＲＡＩＤグリッド位置（８０８）に格納されるページがＲＡＩＤグリッド（８００）のカラム２，ロウ４に存在することを示す＜２，４＞を含み、（ｉｉ）ラストフィールドは、ＲＡＩＤグリッドが６×６（番号が０にて開始する）であることを示す＜５，５＞を特定し、（ｉｉｉ）ｎパリティフィールドは、各次元が２つのパリティ値を含むことを示す＜２，２＞を特定し、（ｉｖ）（パリティ位置フィールドのうちの１つである）Ｐフィールドは、ロウＰパリティグループがＲＡＩＤグリッドの第３のカラム（８１２）に存在するとともにカラムＰパリティグループがＲＡＩＤグリッドの第３のロウ（８１６）に存在することを示す＜２，２＞を特定し、（ｖ）（パリティ位置フィールドのうちの１つである）Ｑフィールドは、ロウＱパリティグループがＲＡＩＤグリッドの第５のロウ（８２０）に存在するとともにカラムＱパリティグループがＲＡＩＤグリッドの第６のロウ（８１８）に存在することを示す＜４，５＞を特定する。最後に、ＲＡＩＤグリッド位置（８０８）におけるページについてのストライプメンバーシップは、＜０１１１１０，１１１１１１＞であり、これは、ロウ（８１０）の両端でのＲＡＩＤグリッド位置に対応する物理的位置が不良であることを示す０を有するロウ（８１０）およびカラム（８１２）に沿ったストライプメンバーシップを含む。
【００９９】
図９Ａ〜図９Ｂは、本発明の１つ以上の実施形態に従ったフローチャートを示す。より具体的には、図９Ａ〜図９Ｂは、本発明の１つ以上の実施形態に従った、ストレージアレイからデータを取得するための方法を示す。
【０１００】
フローチャートにおけるさまざまなステップが順次、提示および記載されるが、当業者であれば、ステップのうちのいくつかまたはすべてが異なる順番で実行されてもよいこと、ステップのうちのいくつかまたはすべてが組み合わせられてもよくまたは省略されてもよいこと、およびステップのうちのいくつかまたはすべてが並列に実行されてもよいことを理解するであろう。
【０１０１】
ステップ９００では、ページはＲＡＩＤグリッド位置から得られる。本発明の一実施形態では、ページはクライアントからの要求に応答して取得される。本発明の一実施形態において、要求は、＜オブジェクト，オフセット＞を特定し得、ＲＡＩＤコントローラは、図６に関して記載されたデータ構造の１つ以上を使用して、要求されたページが格納されるストレージアレイにおいてＲＡＩＤグリッド位置に対応する物理アドレスを決定し得る。ＲＡＩＤコントローラはその後、要求されたデータを含むページをストレージアレイから取得し得る。
【０１０２】
ステップ９０２では、ステップ９００において得られたページにおけるＥＣＣが、ページが修正不可能なエラーを含むことを示すかどうかに関して決定がなされる。上で論じたように、ＥＣＣは、ページにおけるエラーを検出およびある場合においては修正するように用いられ得る。本発明の一実施形態において、ＲＡＩＤコントローラまたはストレージモジュールコントローラ（存在する場合）は、ＥＣＣを使用して、ページが修正不可能なエラーを含むかどうか決定し得る。ページが修正不可能なエラーを含んでいる場合、プロセスはステップ９０６に進み、そうでなければ、プロセスはステップ９０４に進む。ステップ９０４では、ユーザデータがページから抽出され、クライアントに提供される。
【０１０３】
この段階では、ステップ９００で得られたページは破損しているので、ページを再構築する試みがなされる。詳細には、プロセスはステップ９０６に進む。ステップ９０６では、隣接ＲＡＩＤグリッド位置が識別される。本発明の一実施形態において、隣接ＲＡＩＤグリッド位置は、ステップ９００で得られたページからのＲＡＩＤグリッド位置と同じロウまたはカラムに存在するＲＡＩＤグリッドにおけるＩＦＤのうちの１つに沿ったＲＡＩＤグリッド位置に対応する。本発明の一実施形態において、ＲＡＩＤコントローラは隣接ＲＡＩＤグリッド位置を決定する。
【０１０４】
ステップ９０８では、隣接ＲＡＩＤグリッド位置に格納されたページは、ストレージアレイから得られる。
【０１０５】
ステップ９１０では、ステップ９０８において得られたページにおけるＥＣＣが、ページが修正不可能なエラーを含むことを示すかどうかに関して決定がなされる。上で論じたように、ＥＣＣは、ページにおけるエラーを検出およびある場合においては修正するように用いられ得る。本発明の一実施形態において、ＲＡＩＤコントローラまたはストレージモジュールコントローラ（存在する場合）は、ＥＣＣを使用して、ページが修正不可能なエラーを含むかどうか決定し得る。ページが修正不可能なエラーを含んでいる場合、プロセスはステップ９０６に進み、そうでなければ、プロセスはステップ９１２に進む。
【０１０６】
ステップ９１２では、ＯＯＢが破損しているどうかに関して決定がなされる。より具体的には、ＯＯＢはステップ９０８で得られたページから抽出される。ＯＯＢについてのチェックサムがその後、ＯＯＢから抽出される。チェックサム関数が、ＯＯＢにおける残存データに適用されて、計算されたチェックサムが生成される。この計算されたチェックサムは、抽出されたチェックサムと比較される。２つのチェックサムが一致する場合、ＯＯＢは破損しておらず、プロセスはステップ９１４に進み、そうでなければ、プロセスはステップ９０６に進む。
【０１０７】
ステップ９１４では、ストライプメンバーシップ、グリッドマップおよびグリッドジオメトリがＯＯＢから得られる。
【０１０８】
ステップ９１６では、回復次元が識別される。たとえば、隣接ＲＡＩＤグリッド位置がステップ９００において使用されたＲＡＩＤグリッド位置と同じロウにある場合、回復次元はロウに沿って存在する。
【０１０９】
ステップ９１８では、データページ（すなわちパリティデータを含まないページ）がストレージアレイから得られる。より具体的には、（ステップ９１６で決定された）回復次元についてのストライプメンバーシップビットマップが、回復次元におけるどのＲＡＩＤグリッド位置が不良でないページを含むかを識別するために使用される。さらに、グリッドジオメトリにおけるパリティ位置は、ＲＡＩＤグリッド位置のどれがパリティ値を含むかと、ＲＡＩＤグリッド位置のどれがクライアントからのデータを含むかとを決定するために使用される。前述の情報に基づいて、回復次元におけるデータページの相対位置が決定され得る。データページ、グリッドマップ、ＯＯＢのセルフフィールドにおける情報、および隣接ＲＡＩＤグリッド位置の物理アドレスの各々の相対位置を使用して、データページを含むＲＡＩＤグリッド位置の各々についての物理アドレスが決定され得る。物理アドレスがひとたび既知となれば、対応するデータページが得られる。回復次元が、（ストライプメンバーシップによって特定されるように）不良な物理的位置を含む場合、不良な物理ページからページを得る試みはなされない。
【０１１０】
随意であるが、ステップ９２０において、１つ以上のパリティページ（すなわち回復次元においてパリティ値（たとえばＰパリティ値またはＱパリティ値）を含むページ）が得られる。パリティページは、ステップ９１８におけるデータページに関して記載されたのと同様の態様で得られ得る。本発明の一実施形態において、隣接ＲＡＩＤグリッド位置がパリティページを含む場合、ステップ９２０は必要ではない場合がある。
【０１１１】
ステップ９２２では、要求されたページ（すなわちステップ９００で得られたページ）の回復が、先のステップで得られたデータページおよびパリティページ使用して試みられる。当業者であれば、ページが不良な物理的位置から得られないので、そのようなページは要求されたページの回復に必要ではないということを理解するであろう。
【０１１２】
ステップ９２４において、ステップ９２２における再構築の試みが成功したかどうかに関して決定がなされる。本発明の一実施形態では、ＲＡＩＤコントローラは、再構築の試みが成功したかどうか判断するための任意の公知の方法（たとえばチェックサム）を実施し得る。ステップ９２２における再構築の試みが成功した場合、プロセスはステップ９０４に進み、そうでなければ、プロセスはステップ９２６に進む。
【０１１３】
ステップ９２６では、ＲＡＩＤコントローラは、ＲＡＩＤグリッドの他のロウおよび／またはカラムにおけるＲＡＩＤグリッド位置を用いて、上述したのと同じプロセスを使用して、ページを再構築することを試みる。ステップ９２８において、ステップ９２６における再構築の試みが成功したかどうかに関して決定がなされる。本発明の一実施形態では、ＲＡＩＤコントローラは、再構築の試みが成功したかどうか判断するための任意の公知の方法（たとえばチェックサム）を実施し得る。ステップ９２６における再構築の試みが成功した場合、プロセスはステップ９０４に進み、そうでなければ、プロセスはステップ９３０に進む。
【０１１４】
ステップ９３０において、ＲＡＩＤコントローラは、ＲＡＩＤキューブにおける他のＲＡＩＤグリッドを用いて、上述と同じプロセスを使用してページを再構築することを試みる。ステップ９３２において、ステップ９３０における再構築の試みが成功したかどうかに関して決定がなされる。本発明の一実施形態では、ＲＡＩＤコントローラは、再構築の試みが成功したかどうか判断するための任意の公知の方法（たとえばチェックサム）を実施し得る。ステップ９３２における再構築の試みが成功した場合、プロセスはステップ９０４に進み、そうでなければ、プロセスはステップ９３４に進む。ステップ９３４において、ＲＡＩＤコントローラは、要求されたデータがストレージアレイからＲＡＩＤコントローラによって抽出され得ないということを示すエラーをクライアントに返す。
【０１１５】
当業者であれば、ＲＡＩＤキューブにおける他のＲＡＩＤグリッドを使用してデータを再構築することは、ＲＡＩＤコントローラが３Ｄ  ＲＡＩＤスキームを実施している場合のみ行われるということを理解するであろう。
【０１１６】
図１０Ａ〜図１０Ｄは、本発明の１つ以上の実施形態に従った例を示す。この例は、本発明の範囲を限定するようには意図されない。
【０１１７】
図１０Ａを参照して、ストレージアレイがＲＡＩＤグリッド（１０００）を含み、かつ、クライアントがＲＡＩＤグリッド位置（１００２）に格納されるページに位置するデータ（ＤＴ）を要求するシナリオを検討する。クライアントの要求に応答して、ＲＡＩＤコントローラ（図示せず）は、ＲＡＩＤグリッド位置（１００２）に格納されたページを得て、その後、ページにおけるＥＣＣを使用して、ページが破損していることを決定する。
【０１１８】
この段階では、ＲＡＩＤコントローラは、ＲＡＩＤグリッド位置（１００２）に格納されたページを再構築することを試みる。上で論じたように、ＲＡＩＤグリッドコントローラは隣接ＲＡＩＤグリッド位置を選択する。この例において、ＲＡＩＤグリッドコントローラはロウ（１００６）またはカラム（１００４）から隣接ＲＡＩＤグリッド位置を選択し得る。図１０Ｂに示されるように、ＲＡＩＤグリッドコントローラは隣接ＲＡＩＤグリッド位置としてＲＡＩＤグリッド位置（１００８）を選択する。
【０１１９】
その後、ＲＡＩＤコントローラは、ＲＡＩＤグリッド位置（１００８）にてページを得て、ＲＡＩＤグリッド位置（１００４）でのページが破損していないことを（たとえば、ページとともに格納されるＥＣＣを使用して）決定し、その後、ＲＡＩＤグリッド位置（１００４）に位置するページからＯＯＢを抽出する。図１０Ｃは、ＲＡＩＤグリッド位置（１００４）において得られたページについてのＯＯＢを示す。
【０１２０】
グリッドマップを使用して、ＲＡＩＤコントローラは、ＩＦＤ１がＦＭであり、ＩＦＤ２がＣＨであると決定する。さらに、ＲＡＩＤコントローラは、回復次元が（ＩＦＤ１に対応する）ロウ（図１０Ａにおける１００６）に沿っていることを決定する。ＩＦＤ１に沿ったストライプメンバーシップは、回復次元において不良な物理的位置が存在しないことを示す。さらに、Ｐフィールドは、ロウ（１００６）についてのＰパリティ値が当該ロウにおいて位置２に位置することを示し、Ｑフィールドは、ロウ（１００６）についてのＱパリティ値が当該ロウにおいて位置４に位置することを示す。セルフフィールドと共に上記の情報を使用して、ＲＡＩＤグリッドコントローラは、データページ（すなわちパリティ値を含まないページ）が位置０、１および６に位置することを決定する。図１０Ｄを参照して、前述の位置は、ＲＡＩＤグリッド位置（１０１０）、ＲＡＩＤグリッド位置（１０１２）およびＲＡＩＤグリッド位置（１０１４）にそれぞれ対応する。
【０１２１】
ＲＡＩＤグリッド位置（１００８）についての物理アドレスが＜ＦＭ，ＣＨ，ＣＥ，ＬＵＮ，プレーン，ブロック，ページ，バイト＞であると仮定すると、ＲＡＩＤコントローラは、表２に示されるようにデータページを含むＲＡＩＤグリッド位置についての物理アドレスを決定する。
【０１２２】
【表２】
2015535120.tif 000004
【０１２３】
その後、ＲＡＩＤコントローラは、前述のアドレスを使用してデータページを得る。セルフフィールドおよびＱパリティフィールドを使用して、ＲＡＩＤコントローラは、ＲＡＩＤグリッド位置（１００８）から得られたページがロウ（１００６）についてのＱパリティ値を含むと決定する。この段階で、ＲＡＩＤグリッド位置（１０１０）から得られたユーザデータ、ＲＡＩＤグリッド位置（１０１２）、およびＲＡＩＤグリッド位置（１０１４）と、Ｑパリティ値とは、ＲＡＩＤグリッド位置（１００２）にてページを再構築するために使用され得る。
【０１２４】
図１１Ａ〜図１１Ｄは、本発明の１つ以上の実施形態に従った例を示す。この例は、本発明の範囲を限定するようには意図されない。図１１Ａ〜図１１Ｄは、クライアントによって要求されたページを最終的に再構築する、ＲＡＩＤグリッドにおけるさまざまなページの反復的な再構築を示す例を含む。図１１Ａ〜図１１Ｄは、本発明の反復的な再構築の局面に焦点を置くが、当業者であれば、データページおよびパリティ値を得て反復的な再構築を促進することは、少なくとも図９Ａにおけるステップ９１６〜９２２に従って行なわれ得るということを理解するであろう。
【０１２５】
図１１Ａを参照して、クライアントがＲＡＩＤグリッド位置（１１００）からのデータを要求したシナリオを検討する。しかしながら、ＲＡＩＤグリッド位置（１１００）からのデータは（シェーディングによって示されるように）破損している。ＲＡＩＤコントローラはまず、ロウ（１１０４）および／またはカラム（１１０２）におけるＲＡＩＤグリッド位置からのデータを用いてＲＡＩＤグリッド位置（１１００）中のデータを再構築することを（図９Ａにおけるステップ９００〜９２４によって）試みる。しかしながら、ロウ（１１０４）およびカラム（１１０２）の各々が、破損データを含む３つのＲＡＩＤグリッド位置を含んでいるので、ＲＡＩＤグリッド位置（１１００）におけるデータは、ロウ（１１０４）および／またはカラム（１１０２）からのデータのみを使用して回復され得ない。一般に、ｎデータページおよびｍパリティページを含むＲＡＩＤストライプは、ｍの破損または消失ページまで回復し得る。我々の例では、２つのパリティページＰおよびＱにより、各ストライプは２つまでのエラーを回復し得る。
【０１２６】
図１１Ｂを参照して、ＲＡＩＤコントローラは、ＲＡＩＤグリッドにおける他のＲＡＩＤグリッド位置からのデータを使用して、ＲＡＩＤグリッド位置（１１００）におけるデータを再構築することを（図９Ｂのステップ９２８によって）試みる。この例において、ＲＡＩＤコントローラは、ロウ（１１０６）におけるすべての破損データを再構築する。図１１Ｃを参照して、ロウ（１１０６）における破損したデータの再構築に基づき、ＲＡＩＤコントローラは、カラム（１１０８）におけるすべての破損データを再構築することができる。最後に、図１１Ｄを参照して、カラム（１１０８）における破損データの再構築に基づき、ＲＡＩＤコントローラは、ロウ（１１１０）における他の非破損データを使用して、ＲＡＩＤグリッド位置（１１００）におけるデータを再構築することができる。
【０１２７】
図１１Ａ〜図１１Ｄに示されていないが、ＲＡＩＤグリッドにおけるデータのみを使用してＲＡＩＤグリッド位置（１１００）におけるデータが構築され得なかった場合、ＲＡＩＤコントローラが３Ｄ  ＲＡＩＤスキームを実施していれば、ＲＡＩＤコントローラは、ＲＡＩＤキューブ（図示せず）内の他のＲＡＩＤグリッドにおけるデータを用いて、ＲＡＩＤグリッド位置（１１００）におけるデータを再構築することを（図９Ｂにおけるステップ９３２によって）試みる。
【０１２８】
当業者であれば、ＩＦＤに沿ってストレージアレイにデータを格納することおよび／またはＮＡＮＤフラッシュにデータを格納することに関して本発明のさまざまな例が記載されているが、本発明の実施形態は、本発明から逸脱することがなければ、任意の多次元ディスクアレイ上で実施されてもよいということを理解するであろう。たとえば、ＲＡＩＤグリッドにおける各ＲＡＩＤグリッド位置についてのデータが別個のディスク上に格納される２次元アレイのストレージデバイス（磁気、光学、ソリッドステート、または任意の他のタイプのストレージデバイス）を使用して本発明の１つ以上の実施形態が実施され得る。
【０１２９】
さらに、本発明の一実施形態において、ＲＡＩＤコントローラが、３次元アレイのディスクを使用して３Ｄ  ＲＡＩＤスキームを実施している場合、ＲＡＩＤコントローラは、＜ディスクｘ，ディスクｙ，ディスクｚ，論理ブロックアドレス（ＬＢＡ）ａ＞（ｘ、ｙおよびｚはディスクアレイの次元）といったｎタプルを使用してＲＡＩＤグリッド位置の各々についてのデータを格納し得る。
【０１３０】
２次元のディスクアレイを使用する本発明の実施形態を実現するための上記の例は、本発明の範囲を限定するようには意図されない。
【０１３１】
当業者であれば、本発明は２Ｄ  ＲＡＩＤスキームおよび３Ｄ  ＲＡＩＤスキームに関して記載されているが、本発明の実施形態は任意の多次元のＲＡＩＤスキームまで拡張されてもよいということを理解するであろう。
【０１３２】
本発明の１つ以上の実施形態は、当該システムにおける１つ以上のプロセッサによって実行される命令を使用して実施されてもよい。さらに、このような命令は、１つ以上の一時的でないコンピュータ読取可能媒体上に格納されるコンピュータ読取可能命令に対応してもよい。
【０１３３】
本発明を限られた数の実施形態に関して記載したが、この開示の利益を有する当業者であれば、本願明細書において開示される本発明の範囲から逸脱しない他の実施形態が作り出され得るということを理解するであろう。したがって、本発明の範囲は、添付の請求の範囲によってのみ限定されるべきである。
【図１】
2015535120.tif 000005
【図２】
2015535120.tif 000006
【図３】
2015535120.tif 000007
【図４Ａ】
2015535120.tif 000008
【図４Ｂ】
2015535120.tif 000009
【図４Ｃ】
2015535120.tif 000010
【図４Ｄ】
2015535120.tif 000011
【図５】
2015535120.tif 000012
【図６】
2015535120.tif 000013
【図７Ａ】
2015535120.tif 000014
【図７Ｂ】
2015535120.tif 000015
【図７Ｃ】
2015535120.tif 000016
【図７Ｄ】
2015535120.tif 000017
【図８Ａ】
2015535120.tif 000018
【図８Ｂ】
2015535120.tif 000019
【図８Ｃ】
2015535120.tif 000020
【図９Ａ】
2015535120.tif 000021
【図９Ｂ】
2015535120.tif 000022
【図１０Ａ】
2015535120.tif 000023
【図１０Ｂ】
2015535120.tif 000024
【図１０Ｃ】
2015535120.tif 000025
【図１０Ｄ】
2015535120.tif 000026
【図１１Ａ】
2015535120.tif 000027
【図１１Ｂ】
2015535120.tif 000028
【図１１Ｃ】
2015535120.tif 000029
【図１１Ｄ】
2015535120.tif 000030
【手続補正書】
【提出日】平成26年4月24日(2014.4.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データを格納するための方法であって、
データを書き込む要求を受け取ることと、
前記要求に応答して、前記データを書き込むようＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置を選択することと、
前記第１のＲＡＩＤグリッド位置に対応する持続性ストレージにおいて第１の物理アドレスを決定することと、
前記データおよび第１の帯域外（ＯＯＢ）データを含む第１のページを生成することとを含み、前記第１のＯＯＢデータは、ＲＡＩＤグリッドについての第１のグリッドジオメトリと、前記ＲＡＩＤグリッド内の前記ページについての第１のストライプメンバーシップとを含み、前記方法はさらに、
前記第１の物理アドレスに対応する持続性ストレージにおける第１の物理的位置に前記第１のページを書き込むことを含む、方法。
【請求項２】
前記データを使用して前記ＲＡＩＤグリッドのパリティ値を計算することと、
前記パリティ値を書き込むよう前記ＲＡＩＤグリッドにおける第２のＲＡＩＤグリッド位置を選択することと、
前記パリティ値および第２のＯＯＢデータを含む第２のページを生成することとをさらに含み、前記第２のＯＯＢデータは、第２のグリッドジオメトリおよび第２のストライプメンバーシップを含み、前記方法はさらに、
前記第２のＲＡＩＤグリッド位置に対応する持続性ストレージにおける第２の物理アドレスを決定することと、
前記第２の物理アドレスに対応する持続性ストレージにおける第２の物理的位置に前記第２のページを書き込むこととを含む、請求項１に記載の方法。
【請求項３】
前記ＲＡＩＤグリッドはパリティロウを含み、前記第２のＲＡＩＤグリッド位置は前記パリティロウに存在する、請求項２に記載の方法。
【請求項４】
前記データを書き込む要求を受け取ることの前に、
前記ＲＡＩＤグリッド内における複数の可能性のある位置の各々において不良な物理的位置の数を分析することと、
前記複数の可能性のある位置のうちの１つを前記パリティロウの位置として選択することとをさらに含み、前記複数の可能性のある位置の選択された前記１つは、他の複数の可能性のある位置に対して最小の数の不良な物理的位置を含む、請求項３に記載の方法。
【請求項５】
前記第１のストライプメンバーシップは、第１の次元についてのストライプメンバーシップと、前記ＲＡＩＤグリッドにおける第２の次元についてのストライプメンバーシップとを含み、前記第２のストライプメンバーシップは、前記第１の次元についての前記ストライプメンバーシップを含む、請求項２に記載の方法。
【請求項６】
前記第１のページは、前記ＲＡＩＤグリッドにおける第１のロウに存在し、前記第１のストライプメンバーシップは、前記第１のロウに対応する持続性ストレージにおけるどの物理的位置が不良かを示す、請求項５に記載の方法。
【請求項７】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドにおけるパリティ位置を含み、前記第２のグリッドジオメトリは、前記ＲＡＩＤグリッドにおける前記パリティ位置を含む、請求項２に記載の方法。
【請求項８】
前記パリティ値は、Ｐパリティ値、Ｑパリティ値およびインターセクションパリティ値からなる群から選択される少なくとも１つを含む、請求項２に記載の方法。
【請求項９】
前記第１のストライプメンバーシップはビットマップである、請求項１に記載の方法。
【請求項１０】
前記第１のＯＯＢデータはさらにグリッドマップを含み、前記グリッドマップは、前記ＲＡＩＤグリッドの第１の次元に対応する第１の独立した障害ドメイン（ＩＦＤ）と、前記ＲＡＩＤグリッドの第２の次元に対応する第２のＩＦＤとを識別する、請求項１に記載の方法。
【請求項１１】
前記第１のＩＦＤはストレージモジュールであり、前記第２のＩＦＤはチャンネルである、請求項１０に記載の方法。
【請求項１２】
前記持続性ストレージにおける前記第１の物理的位置が、少なくとも部分的に前記第１のＩＦＤおよび前記第２のＩＦＤを使用して特定される、請求項１０に記載の方法。
【請求項１３】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドにおける基準ＲＡＩＤグリッド位置に対する前記ＲＡＩＤグリッドにおける前記第１のページの相対位置を特定するセルフフィールドを含む、請求項１に記載の方法。
【請求項１４】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドの第１の次元の第１のサイズと前記ＲＡＩＤグリッドの第２の次元の第２のサイズとを特定するラストフィールドを含む、請求項１に記載の方法。
【請求項１５】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドの第１の次元における第１の数のパリティ値を特定するｎパリティフィールドを含む、請求項１に記載の方法。
【請求項１６】
前記ｎパリティフィールドはさらに、前記ＲＡＩＤグリッドの第２の次元において第２の数のパリティ値を特定する、請求項１５に記載の方法。
【請求項１７】
前記第１のＯＯＢデータは、前記第１のＯＯＢデータのフォーマットに対応するバージョンフィールドを含む、請求項１に記載の方法。
【請求項１８】
前記第１のＯＯＢデータは、前記第１のＯＯＢデータにおけるすべてのデータを使用して計算されるチェックサムを含む、請求項１に記載の方法。
【請求項１９】
データを再構築するための方法であって、
第１のデータについて要求を受け取ることと、
前記データを含む前記第１のページを得ることとを含み、前記第１のページは、持続性ストレージにおける第１の物理的位置から得られ、前記第１の物理的位置は、第１の物理アドレスと、ＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置とに関連付けられ、前記方法はさらに、
前記第１のページは、破損および未取得からなる群から選択されるものであることを決定を行うことを含み、前記方法はさらに、
前記決定に基づいて、
前記ＲＡＩＤグリッドにおける前記第１のＲＡＩＤグリッド位置の隣接ＲＡＩＤグリッド位置を識別することを含み、前記ＲＡＩＤグリッドはロウを含み、前記第１のＲＡＩＤグリッド位置および前記隣接グリッド位置は前記ロウに存在し、前記方法はさらに、
前記隣接ＲＡＩＤグリッド位置から第２のページを得ることと、
前記第２のページから帯域外（ＯＯＢ）データを得ることとを含み、前記ＯＯＢデータは、前記ＲＡＩＤグリッドについてのグリッドマップと、前記ＲＡＩＤグリッドについてのグリッドジオメトリと、前記ＲＡＩＤグリッド内の前記第２のページについてのストライプメンバーシップとを含み、前記方法はさらに、
前記グリッドジオメトリおよび前記ストライプメンバーシップを使用して、データページを含む前記ロウ内でＲＡＩＤグリッド位置を識別することと、
前記グリッドマップおよび前記グリッドジオメトリを使用して前記ロウ内の前記データページを得ることと、
前記グリッドジオメトリおよび前記ストライプメンバーシップを使用して、パリティ値を含む前記ロウにおけるＲＡＩＤグリッド位置を識別することと、
前記グリッドマップおよび前記グリッドジオメトリを使用して前記ロウ内の前記パリティ値を得ることと、
再構築されたページを得るよう、前記データページおよび前記パリティ値を使用して前記第１のページを再構築することと、
構築された前記ページから前記データを得ることと、
再構築された前記データをクライアントに提供することとを含む、方法。
【請求項２０】
前記グリッドマップは、前記ＲＡＩＤグリッドの第１の次元に対応する第１の独立した障害ドメイン（ＩＦＤ）と、前記ＲＡＩＤグリッドの第２の次元に対応する第２のＩＦＤとを識別し、
前記ストライプメンバーシップは、前記ロウに対応する持続性ストレージにおけるどの物理的位置が不良であるかを示し、
前記グリッドジオメトリは、前記ロウにおけるパリティ位置と、前記ＲＡＩＤグリッドにおける基準ページに対する前記ＲＡＩＤグリッドにおける前記第２のページの相対位置を特定するセルフフィールドとを含む、請求項１９に記載の方法。
【手続補正書】
【提出日】平成27年7月10日(2015.7.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データを格納するための方法であって、
データを書き込む要求を受け取ることと、
前記要求に応答して、前記データを書き込むようＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置を選択することと、
前記第１のＲＡＩＤグリッド位置に対応する持続性ストレージにおいて第１の物理アドレスを決定することと、
前記データおよび第１の帯域外（ＯＯＢ）を含む第１のページを生成することとを含み、前記第１のＯＯＢは、ＲＡＩＤグリッドについての第１のグリッドジオメトリと、前記ＲＡＩＤグリッド内の前記ページについての第１のストライプメンバーシップとを含み、前記方法はさらに、
前記第１の物理アドレスに対応する持続性ストレージにおける第１の物理的位置に前記第１のページを書き込むことを含む、方法。
【請求項２】
前記データを使用して前記ＲＡＩＤグリッドのパリティ値を計算することと、
前記パリティ値を書き込むよう前記ＲＡＩＤグリッドにおける第２のＲＡＩＤグリッド位置を選択することと、
前記パリティ値および第２のＯＯＢを含む第２のページを生成することとをさらに含み、前記第２のＯＯＢは、第２のグリッドジオメトリおよび第２のストライプメンバーシップを含み、前記方法はさらに、
前記第２のＲＡＩＤグリッド位置に対応する持続性ストレージにおける第２の物理アドレスを決定することと、
前記第２の物理アドレスに対応する持続性ストレージにおける第２の物理的位置に前記第２のページを書き込むこととを含む、請求項１に記載の方法。
【請求項３】
前記ＲＡＩＤグリッドはパリティロウを含み、前記第２のＲＡＩＤグリッド位置は前記パリティロウに存在する、請求項２に記載の方法。
【請求項４】
前記データを書き込む要求を受け取ることの前に、
前記ＲＡＩＤグリッド内における複数の可能性のある位置の各々において不良な物理的位置の数を分析することと、
前記複数の可能性のある位置のうちの１つを前記パリティロウの位置として選択することとをさらに含み、前記複数の可能性のある位置の選択された前記１つは、他の複数の可能性のある位置に対して最小の数の不良な物理的位置を含む、請求項３に記載の方法。
【請求項５】
前記第１のストライプメンバーシップは、第１の次元についてのストライプメンバーシップと、前記ＲＡＩＤグリッドにおける第２の次元についてのストライプメンバーシップとを含み、前記第２のストライプメンバーシップは、前記第１の次元についての前記ストライプメンバーシップを含む、請求項２に記載の方法。
【請求項６】
前記第１のページは、前記ＲＡＩＤグリッドにおける第１のロウに存在し、前記第１のストライプメンバーシップは、前記第１のロウに対応する持続性ストレージにおけるどの物理的位置が不良かを示す、請求項５に記載の方法。
【請求項７】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドにおけるパリティ位置を含み、前記第２のグリッドジオメトリは、前記ＲＡＩＤグリッドにおける前記パリティ位置を含む、請求項２に記載の方法。
【請求項８】
前記パリティ値は、Ｐパリティ値、Ｑパリティ値およびインターセクションパリティ値からなる群から選択される少なくとも１つを含む、請求項２に記載の方法。
【請求項９】
前記第１のストライプメンバーシップはビットマップである、請求項１に記載の方法。
【請求項１０】
前記ＯＯＢはさらにグリッドマップを含み、前記グリッドマップは、前記ＲＡＩＤグリッドの第１の次元に対応する第１の独立した障害ドメイン（ＩＦＤ）と、前記ＲＡＩＤグリッドの第２の次元に対応する第２のＩＦＤとを識別する、請求項１に記載の方法。
【請求項１１】
前記第１のＩＦＤはストレージモジュールであり、前記第２のＩＦＤはチャンネルである、請求項１０に記載の方法。
【請求項１２】
前記持続性ストレージにおける前記第１の物理的位置が、少なくとも部分的に前記第１のＩＦＤおよび前記第２のＩＦＤを使用して特定される、請求項１０に記載の方法。
【請求項１３】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドにおける基準ＲＡＩＤグリッド位置に対する前記ＲＡＩＤグリッドにおける前記第１のページの相対位置を特定するセルフフィールドを含む、請求項１に記載の方法。
【請求項１４】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドの第１の次元の第１のサイズと前記ＲＡＩＤグリッドの第２の次元の第２のサイズとを特定するラストフィールドを含む、請求項１に記載の方法。
【請求項１５】
前記第１のグリッドジオメトリは、前記ＲＡＩＤグリッドの第１の次元における第１の数のパリティ値を特定するｎパリティフィールドを含む、請求項１に記載の方法。
【請求項１６】
前記ｎパリティフィールドはさらに、前記ＲＡＩＤグリッドの第２の次元において第２の数のパリティ値を特定する、請求項１５に記載の方法。
【請求項１７】
前記第１のＯＯＢは、前記ＯＯＢのフォーマットに対応するバージョンフィールドを含む、請求項１に記載の方法。
【請求項１８】
前記第１のＯＯＢは、前記第１のＯＯＢにおけるすべてのデータを使用して計算されるチェックサムを含む、請求項１に記載の方法。
【請求項１９】
データを再構築するための方法であって、
第１のデータについて要求を受け取ることと、
前記データを含む前記第１のページを得ることとを含み、前記第１のページは、持続性ストレージにおける第１の物理的位置から得られ、前記第１の物理的位置は、第１の物理アドレスと、ＲＡＩＤグリッドにおける第１のＲＡＩＤグリッド位置とに関連付けられ、前記方法はさらに、
前記第１のページは、破損および未取得からなる群から選択されるものであることを決定を行うことを含み、前記方法はさらに、
前記決定に基づいて、
前記ＲＡＩＤグリッドにおける前記第１のＲＡＩＤグリッド位置の隣接ＲＡＩＤグリッド位置を識別することを含み、前記ＲＡＩＤグリッドはロウを含み、前記第１のＲＡＩＤグリッド位置および前記隣接グリッド位置は前記ロウに存在し、前記方法はさらに、
前記隣接ＲＡＩＤグリッド位置から第２のページを得ることと、
前記第２のページから帯域外（ＯＯＢ）データを得ることとを含み、前記ＯＯＢは、前記ＲＡＩＤグリッドについてのグリッドマップと、前記ＲＡＩＤグリッドについてのグリッドジオメトリと、前記ＲＡＩＤグリッド内の前記第２のページについてのストライプメンバーシップとを含み、前記方法はさらに、
前記グリッドジオメトリおよび前記ストライプメンバーシップを使用して、データページを含む前記ロウ内でＲＡＩＤグリッド位置を識別することと、
前記グリッドマップおよび前記グリッドジオメトリを使用して前記ロウ内の前記データページを得ることと、
前記グリッドジオメトリおよび前記ストライプメンバーシップを使用して、パリティ値を含む前記ロウにおけるＲＡＩＤグリッド位置を識別することと、
前記グリッドマップおよび前記グリッドジオメトリを使用して前記ロウ内の前記パリティ値を得ることと、
再構築されたページを得るよう、前記データページおよび前記パリティ値を使用して前記第１のページを再構築することと、
構築された前記ページから前記データを得ることと、
再構築された前記データをクライアントに提供することとを含む、方法。
【請求項２０】
前記グリッドマップは、前記ＲＡＩＤグリッドの第１の次元に対応する第１の独立した障害ドメイン（ＩＦＤ）と、前記ＲＡＩＤグリッドの第２の次元に対応する第２のＩＦＤとを識別し、
前記ストライプメンバーシップは、前記ロウに対応する持続性ストレージにおけるどの物理的位置が不良であるかを示し、
前記グリッドジオメトリは、前記ロウにおけるパリティ位置と、前記ＲＡＩＤグリッドにおける基準ページに対する前記ＲＡＩＤグリッドにおける前記第２のページの相対位置を特定するセルフフィールドとを含む、請求項１９に記載の方法。
【国際調査報告】
2015535120.tif 000031
2015535120.tif 000032
2015535120.tif 000033