(57)【特許請求の範囲】
【請求項１】
データを記憶するための方法をプロセッサに行なわせるための命令を記録した、コンピュータ読取可能な記録媒体であって、前記方法は、前記プロセッサが、
データを永続性記憶装置に書込む要求をクライアントから受信することと、
前記要求に基づいて、前記データのための記憶モードを判断することとを備え、前記データのための前記記憶モードはミラードモードであり、さらに前記プロセッサが、
前記記憶モードに基づいて独立装置冗長アレイ（ＲＡＩＤ）グリッド内の場所であるＲＡＩＤグリッド場所を選択して、選択されたＲＡＩＤグリッド場所に前記データを書込むことと、
前記データをメモリに書込むこととを備え、前記データは前記メモリに一時的に記憶され、さらに前記プロセッサが、
ＲＡＩＤグリッドとＲＡＩＤグリッド場所とを関連付けたデータ構造を更新して、前記ＲＡＩＤグリッド場所にデータが書き込まれていると示すことと、
前記データ構造を用いて、前記ＲＡＩＤグリッド中の、データを格納するためのグリッドであるデータグリッド内のすべての場所にデータが格納されているか否かを判断することとを備え、
前記データが書込まれる前記ＲＡＩＤグリッド場所は前記データグリッド中にあり、さらに
前記データグリッドにデータが書き込まれているという判断に基づいて、
前記データを用いて前記ＲＡＩＤグリッドのパリティ値を算出することと、
前記データ構造を用いて、前記ＲＡＩＤグリッド場所に対応する前記永続性記憶装置中の第１の物理アドレスを決定することと、
前記データ構造を用いて、前記ＲＡＩＤグリッド場所に対応する前記永続性記憶装置中の第２の物理アドレスを決定することと、
前記第１の物理アドレスに対応する前記永続性記憶装置中の第１の物理的場所に前記データを書込むことと、
前記第２の物理アドレスに対応する前記永続性記憶装置中の第２の物理的場所に前記データを書込むことと、
データグリッドに関連付けられる前記パリティ値を前記永続性記憶装置に書込むことと、を備える、コンピュータ読取可能な記録媒体。
【請求項２】
前記方法はさらに、前記プロセッサが、
第２のデータを書込む第２の要求を前記クライアントから受信することと、
前記第２の要求に基づいて、前記第２のデータのための第２の記憶モードを判断することとを備え、前記第２のデータのための前記記憶モードは非ミラードモードであり、さらに前記プロセッサが、
前記第２の記憶モードに基づいて前記ＲＡＩＤグリッド中の第２のＲＡＩＤグリッド場所を選択して前記データを書込むことと、
前記第２のデータを前記メモリに書込むこととを備え、前記第２のデータは前記メモリに一時的に記憶され、さらに
前記データ構造を更新して、前記第２のＲＡＩＤグリッド場所が部分的にデータが格納されていると示すことと、
第３のデータを書込む第３の要求を前記クライアントから受信することと、
前記データ構造に基づいて、前記第３のデータのための第３の記憶モードを判断することとを備え、前記第３のデータのための前記第３の記憶モードは前記非ミラードモードであり、
前記第３の記憶モードに基づいて、前記ＲＡＩＤグリッド中の前記第２のＲＡＩＤグリッド場所を選択して、選択された第２のＲＡＩＤグリッド場所に、前記第３の記憶モードを用いて前記データを書込むことと、
前記第３のデータを前記メモリに書込むこととを備え、前記第３のデータは前記メモリに一時的に記憶され、さらに前記プロセッサが、
前記データ構造を更新して、前記第２のＲＡＩＤグリッド場所にデータが格納されていると示すことと、
前記データグリッド内のすべての場所にデータが書き込まれているという前記判断に基づいて、
前記第２のＲＡＩＤグリッド場所に対応する前記永続性記憶装置中の第３の物理アドレスを決定することと、
前記第２のＲＡＩＤグリッド場所に対応する前記永続性記憶装置中の第４の物理アドレスを決定することと、
前記第３の物理アドレスに対応する前記永続性記憶装置中の第３の物理的場所に前記第２のデータを書込むことと、
前記第４の物理アドレスに対応する前記永続性記憶装置中の第４の物理的場所に前記第３のデータを書込むことと、を備える、請求項１に記載のコンピュータ読取可能な記録媒体。
【請求項３】
前記ＲＡＩＤグリッド場所は仮想ストライプに関連付けられ、前記仮想ストライプは第１の物理ストライプおよび第２の物理ストライプに関連付けられ、前記第１の物理的場所は前記第１の物理ストライプの一部であり、前記第２の物理的場所は前記第２の物理ストライプの一部であり、前記第２のＲＡＩＤグリッド場所は第２の仮想ストライプに関連付けられ、前記第２の仮想ストライプは第３の物理ストライプおよび第４の物理ストライプに関連付けられ、前記第３の物理的場所は前記第３の物理ストライプの一部であり、前記第３の物理ストライプ中に記憶される前記パリティ値は、前記第４の物理ストライプ中に記憶される前記パリティ値とは異なる、請求項２に記載のコンピュータ読取可能な記録媒体。
【請求項４】
前記ＲＡＩＤグリッド場所は仮想ストライプに関連付けられ、前記仮想ストライプは第１の物理ストライプおよび第２の物理ストライプに関連付けられ、前記第１の物理的場所は前記第１の物理ストライプの一部であり、前記第２の物理的場所は前記第２の物理ストライプの一部である、請求項１に記載のコンピュータ読取可能な記録媒体。
【請求項５】
前記ＲＡＩＤグリッド場所は仮想ストライプおよび第２の仮想ストライプに関連付けられる、請求項１に記載のコンピュータ読取可能な記録媒体。
【請求項６】
前記第１の物理ストライプ中に記憶される前記パリティ値は、前記第２の物理ストライプ中に記憶される前記パリティ値に等しい、請求項４に記載のコンピュータ読取可能な記録媒体。
【請求項７】
前記第１の物理的場所は、記憶モジュール、チャネル、およびチップを備えるｎタプルを用いて特定され、前記第２の物理的場所は、前記記憶モジュール、前記チャネル、および第２のチップを用いて特定される、請求項１に記載のコンピュータ読取可能な記録媒体。
【請求項８】
前記データは、前記データを前記第２の物理的場所に書込む前に、永続性記憶装置中の前記第１の物理的場所に書込まれる、請求項１に記載のコンピュータ読取可能な記録媒体。
【請求項９】
前記永続性記憶装置は複数の記憶モジュールを備え、前記複数の記憶モジュールの各々は固体メモリを備える、請求項８に記載のコンピュータ読取可能な記録媒体。
【請求項１０】
前記パリティ値は、Ｐパリティ値、Ｑパリティ値、および交差パリティ値からなる群から選択される少なくとも１つを備える、請求項１に記載のコンピュータ読取可能な記録媒体。
【請求項１１】
前記ＲＡＩＤグリッドは、行Ｑパリティ群、行Ｐパリティ群、列Ｑパリティ群、列Ｐパリティ群、および交差パリティ群を備え、前記パリティ値の各々は、前記行Ｑパリティ群、前記行Ｐパリティ群、前記列Ｑパリティ群、前記列Ｐパリティ群、および前記交差パリティ群からなる群から選択される１つに関連付けられる、請求項１に記載のコンピュータ読取可能な記録媒体。
【請求項１２】
前記交差パリティ群に関連付けられる前記パリティ値は、前記行Ｑパリティ群、前記行Ｐパリティ群、前記列Ｑパリティ群、および前記列Ｐパリティ群からなる群から選択される少なくとも１つの前記パリティ値を用いて算出される、請求項１１に記載のコンピュータ読取可能な記録媒体。
【請求項１３】
再構築データを得るための方法をプロセッサに行なわせるための命令を記録した、コンピュータ読取可能な記録媒体であって、前記方法は、前記プロセッサが、
データに対する第１の要求をクライアントから受信することと、
前記第１の要求に基づいて、前記データに関連付けられる独立装置冗長アレイ（ＲＡＩＤ）グリッド中の場所であるグリッド場所を同定することとを備え、前記グリッド場所は第１の物理的場所および第２の物理的場所に関連付けられ、さらに前記プロセッサが、
前記第１の要求に基づいて、前記グリッド場所のための記憶モードがミラードモードであるという第１の判断を行なうことと、
前記第１の判断に基づいて、前記第１の物理的場所にデータが格納されているという第２の判断を行なうことと、
前記第２の判断に基づいて、前記データに対する第２の要求を前記第２の物理的場所に発行することと、
前記第２の要求に応答して、前記データを前記第２の物理的場所から受信することとを備え、
前記グリッド場所は仮想ストライプに関連付けられ、
前記仮想ストライプは第１の物理ストライプおよび第２の物理ストライプに関連付けられ、
前記第１の物理的場所は前記第１の物理ストライプの一部であり、前記第２の物理的場所は前記第２の物理ストライプの一部である、コンピュータ読取可能な記録媒体。
【請求項１４】
前記方法は、前記プロセッサが、
前記第２の物理的場所から得られた前記データが破損しているという第３の判断を、前記データのチェックに基づいて行なうことと、
前記第３の判断に基づいて、前記データに対する第３の要求を前記第１の物理的場所に発行することとをさらに備える、請求項１３に記載のコンピュータ読取可能な記録媒体。
【請求項１５】
前記方法はさらに、前記プロセッサが、
前記第２の物理的場所から得られた前記データが破損しているという第４の判断を前記データのチェックに基づいて行なうことと、
前記第４の判断に基づいて、前記第１の物理ストライプおよび前記第２の物理ストライプからなる群から選択される少なくとも１つを用いて前記データの再構築を試みることとを備える、請求項１４に記載のコンピュータ読取可能な記録媒体。
【請求項１６】
前記方法はさらに、前記プロセッサが、
前記第２の物理的場所から得られた前記データが破損しているという第４の判断を、前記データのチェックに基づいて行なうことと、
前記第４の判断に基づいて、前記第１の物理ストライプを用いて前記データの再構築を試みることとを備える、請求項１４に記載のコンピュータ読取可能な記録媒体。
【請求項１７】
前記方法はさらに、前記プロセッサが、
前記第１の物理ストライプを用いて前記データを再構築する試みが失敗したという第５の判断を行なうことと、
前記第５の判断に基づいて、前記第２の物理ストライプを用いて前記データの再構築を試みることとを備える、請求項１６に記載のコンピュータ読取可能な記録媒体。
【請求項１８】
前記第１の物理的場所は永続性記憶装置中の第１のチップ上にあり、前記第２の物理的場所は前記永続性記憶装置中の第２のチップ上にあり、前記第１のチップおよび前記第２のチップは入／出力（Ｉ／Ｏ）動作を並列に行うことができる請求項１３に記載のコンピュータ読取可能な記録媒体。
【請求項１９】
前記Ｉ／Ｏ動作は、読出動作、書込動作、および消去動作からなる群から選択される少なくとも１つを備える、請求項１８に記載のコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
背景
記憶システム中のデータの潜在的な損失に対する保護のために、複製方式を実現することがしばしば有利である。現在の複製方式では、記憶システム内のデータを読出せなくなる前に被る誤りの量を限定することしかできない。
【発明の概要】
【課題を解決するための手段】
【０００２】
要約
一般的に、１つの局面では、発明は、プロセッサによって実行されると方法を実行する命令を備える非一時的コンピュータ読出可能媒体に関し、データを記憶するための方法は、データを書込む要求を受信することと、データのための記憶モードを判断することとを備え、データのための記憶モードはミラードモードであり、さらに、記憶モードに基づいて独立装置冗長アレイ（ＲＡＩＤ）グリッド中のＲＡＩＤグリッドを選択してデータを書込むことと、データをメモリに書込むこととを備え、データはメモリに一時的に記憶され、さらに、データ構造を更新してＲＡＩＤグリッド場所が埋まっていると示すことと、ＲＡＩＤグリッド場所が埋まっているか否かをデータ構造を用いて判断することとを備え、ＲＡＩＤグリッド場所はデータグリッド中にあり、さらに、データグリッドが埋まっているいう判断に基づいて、データを用いてＲＡＩＤグリッドのパリティ値を算出することと、ＲＡＩＤグリッド場所に対応する永続性記憶装置中の第１の物理アドレスを判断することと、ＲＡＩＤグリッド場所に対応する永続性記憶装置中の第２の物理アドレスを判断することと、第１の物理アドレスに対応する永続性記憶装置中の第１の物理的場所にデータを書込むことと、第２の物理アドレスに対応する永続性記憶装置中の第２の物理的場所にデータを書込むことと、データグリッドに関連付けられるパリティ値を永続性記憶装置に書込むこととを備える。
【０００３】
一般的に、１つの局面では、発明は、プロセッサによって実行されると方法を実行する命令を備える非一時的コンピュータ読出媒体に関し、再構築データを得るための方法は、データに対する第１の要求を受信することと、データに関連付けられる独立装置冗長アレイ（ＲＡＩＤ）中のグリッド場所を同定することとを備え、グリッド場所は第１の物理的場所および第２の物理的場所に関連付けられ、さらに、グリッド場所のための記憶モードがミラードモードであるという第１の判断を行なうことと、第１の判断に基づいて、第１の物理的場所が塞がっているという第２の判断を行なうことと、第２の判断に基づいて、データに対する第２の要求を第２の物理的場所に発行することと、第２の要求に応答して、第２の物理的場所からデータを受信することとを備え、グリッド場所は仮想ストライプに関連付けられ、仮想ストライプは第１の物理ストライプおよび第２の物理ストライプに関連付けられ、第１の物理的場所は第１の物理ストライプの一部であり、第２の物理的場所は第２の物理ストライプの一部である。
【０００４】
発明の他の局面は以下の説明および添付の請求項から明らかになるであろう。
【図面の簡単な説明】
【０００５】
【図１】発明の１つの実施形態に従うシステムを示す図である。
【図２Ａ】発明の１つの実施形態に従うＲＡＩＤグリッドを示す図である。
【図２Ｂ】発明の１つの実施形態に従う仮想ストライプおよび物理ストライプを示す図である。
【図２Ｃ】発明の１つの実施形態に従う記憶モジュールを示す図である。
【図３Ａ】発明の１つの実施形態に従うＲＡＩＤキューブおよびＲＡＩＤキューブのさまざまな表示を示す図である。
【図３Ｂ】発明の１つの実施形態に従う例示的なＲＡＩＤキューブおよびＲＡＩＤグリッドを示す図である。
【図３Ｃ】発明の１つの実施形態に従う例示的なＲＡＩＤキューブおよびＲＡＩＤグリッドを示す図である。
【図４Ａ】発明の１つの実施形態に従うデータ構造を示す図である。
【図４Ｂ】発明の１つの実施形態に従うデータ構造を示す図である。
【図５Ａ】発明の１つの実施形態に従うフローチャートである。
【図５Ｂ】発明の１つの実施形態に従うフローチャートである。
【図５Ｃ】発明の１つの実施形態に従うフローチャートである。
【図６Ａ】発明の１つ以上の実施形態に従う例を示す図である。
【図６Ｂ】発明の１つ以上の実施形態に従う例を示す図である。
【図６Ｃ】発明の１つ以上の実施形態に従う例を示す図である。
【図７Ａ】発明の１つ以上の実施形態に従うフローチャートである。
【図７Ｂ】発明の１つ以上の実施形態に従うフローチャートである。
【図８Ａ】発明の１つ以上の実施形態に従う例を示す図である。
【図８Ｂ】発明の１つ以上の実施形態に従う例を示す図である。
【図８Ｃ】発明の１つ以上の実施形態に従う例を示す図である。
【図８Ｄ】発明の１つ以上の実施形態に従う例を示す図である。
【図８Ｅ】発明の１つ以上の実施形態に従う例を示す図である。
【発明を実施するための形態】
【０００６】
詳細な説明
添付の図を参照して、発明の具体的な実施形態をここで詳細に説明する。発明の実施形態の以下の詳細な説明では、発明のより徹底した理解を与えるために数多くの具体的な詳細を述べる。しかしながら、当業者には、これらの具体的な詳細なしに発明を実践してもよいことが明らかであろう。他の事例では、不要に説明を複雑にするのを回避するために周知の特徴を詳細に説明していない。
【０００７】
図１から図８Ｅの以下の説明では、発明のさまざまな実施形態中の、図に関して説明される任意の構成要素は、任意の他の図に関して説明される１つ以上の同じ名称の構成要素と均等であることがある。簡略さのため、各図に関してこれらの構成要素の説明を繰返さない。このように、各図の構成要素のありとあらゆる実施形態が引用により援用され、１つ以上の同じ名称の構成要素を有するあらゆる他の図内にオプションで存在すると想定される。加えて、発明のさまざまな実施形態に従うと、図の構成要素の任意の説明は、任意の他の図中の対応の同じ名称の構成要素に関して説明される実施形態に加えて、それに関連して、またはその代わりに実現されてもよいオプションの実施形態として解釈されるべきである。
【０００８】
一般的に、発明の実施形態は、グリッド場所レベルでミラーリングを実現する多次元ＲＡＩＤ方式を用いてデータを複製するための方法およびシステムに関する。より具体的には、発明の実施形態は、各々がグリッド場所レベルでミラーリングを実現する２Ｄ  ＲＡＩＤ方式および３Ｄ  ＲＡＩＤ方式を実現するための方法およびシステムを提供する。
【０００９】
２Ｄ  ＲＡＩＤ方式を用いると、そのようなＲＡＩＤ方式を実現するＲＡＩＤグリッド内に記憶されるデータは、所与のＲＡＩＤストライプ中に２つよりも多くの誤りが存在すると回復され得る。同様に、３Ｄ  ＲＡＩＤ方式を用いると、そのようなＲＡＩＤ方式を実現するＲＡＩＤキューブ内に記憶されるデータは、所与のＲＡＩＤストライプ中に２つよりも多くの誤りが存在すると回復され得る。発明のさまざまな実施形態では、１つよりも多くの独立障害ドメイン（ＩＦＤ）中に不具合が存在すると、すべてのデータを回復することができる。さらに、グリッド場所レベルでのミラーリングを可能化することにより、発明の実施形態は、永続性記憶装置からデータにアクセスすることに関する潜在的な待ち時間の問題を軽減しながら、付加的なレベルの複製／冗長を提供する。
【００１０】
発明の１つ以上の実施形態では、ＩＦＤは、所与の場所にあるデータがアクセス不可能になってしまう結果を招く不具合モードに対応する。各々のＩＦＤは記憶アレイ中の不具合の独立したモードに対応する。たとえば、ＮＡＮＤフラッシュが（複数のＮＡＮＤダイを含む）記憶モジュールの一部であるＮＡＮＤフラッシュにデータが記憶される場合、ＩＦＤは、（ｉ）記憶モジュール、（ii）チャネル（すなわち、記憶モジュール中の記憶モジュールコントローラ（図示せず）が用いてデータをＮＡＮＤフラッシュに書込むチャネル）、および（iii）ＮＡＮＤフラッシュダイであり得る。
【００１１】
この発明の目的のため、本明細書中で用いるような「ＲＡＩＤ」という用語は、「独立装置冗長アレイ」を指す。これに応じて、発明の実施形態は、発明の実現例（たとえば図２Ｂ−図４Ｂを参照）に基づいて１つ以上の永続性記憶装置装置にわたってＲＡＩＤグリッド場所（たとえば図２Ａを参照）が分散され得る任意の種類の永続性記憶装置装置を用いて実現されることがある。
【００１２】
図１は、発明の１つの実施形態に従うシステムを示す。図１に示されるように、システムは、１つ以上のクライアント（１００Ａ，１００Ｍ）と、ＲＡＩＤコントローラ（１０４）と、メモリ（１０６）と、オプションでＦＰＧＡ（１０２）と、記憶アレイ（１０８）とを含む。
【００１３】
発明の１つの実施形態では、クライアント（１００Ａ，１００Ｍ）は、読出要求または書込要求をＲＡＩＤコントローラ（１０４）に発行する機能を含むシステム上で実行する任意のシステムまたはプロセスである。発明の１つの実施形態では、クライアント（１００Ａ，１００Ｍ）は各々、プロセッサ（図示せず）、メモリ（図示せず）、および永続性記憶装置（図示せず）を含んでもよい。発明の１つの実施形態では、ＲＡＩＤコントローラ（１０４）は、多次元ＲＡＩＤ方式と整合する態様でデータを記憶アレイに書込むこと（図５Ａ−図５Ｃを参照）と、多次元ＲＡＩＤ方式と整合する態様で記憶アレイから（再構築データを含む）データを読出すこと（図７Ａ−図７Ｂを参照）とを含む多次元ＲＡＩＤ方式を実現するように構成される。発明の１つの実施形態では、ＲＡＩＤコントローラ（１０４）は、発明の１つ以上の実施形態を実現する命令を実行するように構成されるプロセッサを含み、命令は、ＲＡＩＤコントローラ（１０４）内に位置するかまたはこれに動作するように接続される非一時的コンピュータ読出可能媒体（図示せず）上に記憶される。これに代えて、ＲＡＩＤコントローラ（１０４）は、ハードウェアを用いて実現されてもよい。当業者は、ソフトウェアおよび／またはハードウェアの任意の組合せを用いてＲＡＩＤコントローラ（１０４）を実現してもよいことを認めるであろう。
【００１４】
発明の１つの実施形態では、ＲＡＩＤコントローラ（１０４）はメモリ（１０６）に動作するように接続される。メモリ（１０６）は、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、同期ＤＲＡＭ、ＳＤＲ  ＳＤＲＡＭ、およびＤＤＲ  ＳＤＲＡＭを含むがこれらに限定されない任意の揮発性メモリであってもよい。発明の１つの実施形態では、メモリ（１０６）は、（パリティデータを含む）さまざまなデータが記憶アレイに記憶される前に、そのようなデータを一時的に記憶するように構成される。
【００１５】
発明の１つの実施形態では、ＦＰＧＡ（１０２）（存在する場合）は、記憶アレイ（１０８）中にデータを記憶する目的でＰおよび／もしくはＱパリティ情報を算出する機能、ならびに／または多次元ＲＡＩＤ方式を用いて記憶される破損データを回復するのに必要なさまざまな算出を行なう機能を含む。ＲＡＩＤコントローラ（１０４）は、発明の１つ以上の実施形態に従って、ＦＰＧＡ（１０２）を用いてさまざまなデータの処理の負荷を軽減してもよい。発明の１つの実施形態では、記憶アレイ（１０８）は、磁気メモリ装置、光学メモリ装置、固体メモリ装置、相変化メモリ装置、任意の他の好適な種類の永久メモリ装置、またはその任意の組合せを含むがそれらに限定されない多数の個別の永続性記憶装置装置を含む。他に特に示されなければ、以上言及した装置の各々は、この説明を通じて包括的に記憶モジュールと称されることがある。
【００１６】
当業者は、図１がＦＰＧＡを示す一方で、ＦＰＧＡなしに発明を実現してもよいことを認めるであろう。さらに、当業者は、発明から逸脱することなく、ＦＰＧＡの代わりに他の構成要素を用いてもよいことを認めるであろう。たとえば、発明は、ＡＳＩＣ、グラフィック処理ユニット（ＧＰＵ）、汎用プロセッサ、記憶アレイ中にデータを記憶する目的のためにＰおよび／もしくはＱパリティ情報を算出する、ならびに／もしくは多次元ＲＡＩＤ方式を用いて記憶される破損データを回復するのに必要なさまざまな算出を行なうことができる任意の他のハードウェア装置、記憶アレイ（１０８）中にデータを記憶する目的のためにＰおよび／もしくはＱパリティ情報を算出する、ならびに／または多次元ＲＡＩＤ方式を用いて記憶される破損データを回復するのに必要なさまざまな算出を行なうように構成されるハードウェア、ファームウェア、ならびに／もしくはソフトウェアの組合せを含む任意の装置、またはその任意の組合せを用いて実現されてもよい。
【００１７】
図２Ａは、発明の１つの実施形態に従うＲＡＩＤグリッドを示す。発明の１つの実施形態では、ＲＡＩＤコントローラが２Ｄ  ＲＡＩＤ方式または３Ｄ  ＲＡＩＤ方式（図３Ａを参照）を実現すれば、ＲＡＩＤコントローラはＲＡＩＤグリッド（２００）中にデータを記憶する。図２Ａは、発明の１つ以上の実施形態に従うＲＡＩＤグリッドの概念的部分を示す。ＲＡＩＤグリッド（２００）は多数のＲＡＩＤグリッド場所を含み、各々のＲＡＩＤグリッド場所に関連付けられるデータは究極的に、記憶アレイ中の２つ（以上）の一意な物理的場所に書込まれる（図２Ｂを参照）。ＲＡＩＤグリッド（２００）は、（ｉ）クライアントから受信したデータ（すなわち、クライアントがＲＡＩＤコントローラに記憶アレイに書込むことを指示したデータ）を記憶するＲＡＩＤグリッド場所を含むデータグリッド（２０２）と、（ii）行の次元に沿った仮想ストライプ中のＲＡＩＤグリッド場所中のデータを用いて算出されるＰパリティ値を記憶するＲＡＩＤグリッド場所を含む行Ｐパリティ群（２０４）（図２Ａ、２１４、および図６Ａ、６０２を参照）と、（iii）行の次元に沿った仮想ストライプ中のＲＡＩＤグリッド場所中のデータを用いて算出されるＱパリティ値を記憶するＲＡＩＤグリッド場所を含む行Ｑパリティ群（２０６）（図２Ａ、２１４、および図６Ａ、６０２を参照）と、（iv）列の次元に沿った仮想ストライプ中のＲＡＩＤグリッド場所中のデータを用いて算出されるＰパリティ値を記憶するＲＡＩＤグリッド場所を含む列Ｐパリティ群（２０８）（図２Ａ、２１４、および図６Ａ、６０４を参照）と、（ｖ）列の次元に沿った仮想ストライプ中のＲＡＩＤグリッド場所中のデータを用いて算出されるＱパリティ値を記憶するＲＡＩＤグリッド場所を含む列Ｑパリティ群（２１０）（図２Ａ、２１４、および図６Ａ、６０２を参照）と、（vi）（ａ）行Ｐパリティ群（２０４）中のＲＡＩＤグリッド場所からのデータ、（ｂ）行Ｑパリティ群（２０６）中のＲＡＩＤグリッド場所からのデータ、（ｃ）列Ｐパリティ群（２０８）中のＲＡＩＤグリッド場所からのデータ、および（ｄ）（以下に記載される）列Ｑパリティ群（２１０）中のＲＡＩＤグリッド場所からのデータを用いて算出されるパリティ値を含む交差パリティ群（２１２）とを含む。
【００１８】
行（２１４）を参照して、発明の１つの実施形態では、行（２１４）中のＰr2と表記されるＲＡＩＤグリッド場所に記憶されるデータは、データ（たとえば、Ｐr2＝ｆP（Ｄ1，Ｄ2，Ｄ3，Ｄ4）を含む行（２１４）中のすべてのＲＡＩＤグリッド場所にＰパリティ関数を適用することによって算出される。同様に、発明の１つの実施形態では、行（２１４）中のＱr2と表記されるＲＡＩＤグリッド場所に記憶されるデータは、データ（たとえば、Ｑr2＝ｆQ（Ｄ1，Ｄ2，Ｄ3，Ｄ4）を含む行（２１４）中のすべてのＲＡＩＤグリッド場所にＱパリティ関数を適用することによって算出される。
【００１９】
列（２１６）を参照して、発明の１つの実施形態では、列（２１６）中のＰc6と表記されるＲＡＩＤグリッド場所に記憶されるデータは、データ（たとえばＰc6＝ｆP（Ｄ5，Ｄ2，Ｄ6，Ｄ7）を含む列（２１６）中のすべてのＲＡＩＤグリッド場所にＰパリティ関数を適用することによって算出される。同様に、発明の１つの実施形態では、列（２１６）中のＱc6によって表記されるＲＡＩＤグリッド場所に記憶されるデータは、データ（たとえば、Ｑc6＝ｆQ（Ｄ5，Ｄ2，Ｄ6，Ｄ7）を含む列（２１６）中のすべてのＲＡＩＤグリッド場所にＱパリティ関数を適用することによって算出される。
【００２０】
交差パリティ群（２１２）を参照して、発明の１つの実施形態では、Ｉr1と表記されるＲＡＩＤグリッド場所に記憶されるデータは、行Ｐパリティ群（２０４）中のすべてのＲＡＩＤグリッド場所にＰパリティ関数を適用することによって、または列Ｐパリティ群（２０８）中のすべてのＲＡＩＤグリッド場所にＰパリティ関数を適用することによって算出され得る。たとえば、Ｉr1＝ｆP（Ｐr1，Ｐr2，Ｐr3，Ｐr4）またはＩr1＝ｆP（Ｐc5，Ｐc6，Ｐc7，Ｐc8）である。
【００２１】
発明の１つの実施形態では、Ｉr2と表記されるＲＡＩＤグリッド場所に記憶されるデータは、行Ｑパリティ群（２０４）中のすべてのＲＡＩＤグリッド場所にＰパリティ関数を適用することによって、または列Ｐパリティ群（２０８）中のすべてのＲＡＩＤグリッド場所にＱパリティ関数を適用することによって算出され得る。たとえば、Ｉr2＝ｆP（Ｑr1，Ｑr2，Ｑr3，Ｑr4）またはＩr2＝ｆQ（Ｐc5，Ｐc6，Ｐc7，Ｐc8）である。
【００２２】
発明の１つの実施形態では、Ｉr3と表記されるＲＡＩＤグリッド場所に記憶されるデータは、列Ｑパリティ群（２１０）中のすべてのＲＡＩＤグリッド場所にＰパリティ関数を適用することによって、または行Ｐパリティ群（２０４）中のすべてのＲＡＩＤグリッド場所にＱパリティ関数を適用することによって算出され得る。たとえば、Ｉr3＝ｆP（Ｑc5，Ｑc6，Ｑc7，Ｑc8）またはＩr3＝ｆQ（Ｐc1，Ｐc2，Ｐc3，Ｐc4）である。
【００２３】
発明の１つの実施形態では、Ｉr4と表記されるＲＡＩＤグリッド場所に記憶されるデータは、列Ｑパリティ群（２１０）中のすべてのＲＡＩＤグリッド場所にＱパリティ関数を適用することによって、または行Ｑパリティ群（２０６）中のすべてのＲＡＩＤグリッド場所にＱパリティ関数を適用することによって算出され得る。たとえば、Ｉr4＝ｆQ（Ｑc1，Ｑc2，Ｑc3，Ｑc4）またはＩr4＝ｆQ（Ｑc5，Ｑc6，Ｑc7，Ｑc8）である。
【００２４】
発明の１つの実施形態では、パリティ群のすべての値を算出するのに用いられるＰおよびＱパリティ関数は、ＲＡＩＤ６を実現するのに用いられる任意のＰおよびＱパリティ関数に対応してもよい。
【００２５】
以上で論じたように、図２Ａに示されるＲＡＩＤグリッド（２００）は、ＲＡＩＤグリッドの概念的レイアウトを表わす。しかしながら、さまざまなＲＡＩＤグリッド場所の相対的な場所は、行およびまたは列にわたって異なることがある。たとえば、行（２１４）を参照して、（「Ｄ」で表記される）データを含むＲＡＩＤグリッド場所およびパリティデータを含むＲＡＩＤグリッド場所（すなわち、「Ｐr」および「Ｑr」と表記されるＲＡＩＤグリッド場所）の相対的な場所は、＜Ｄ1，Ｄ2，Ｐr2，Ｄ3，Ｑr2，Ｄ4＞，＜Ｐr2，Ｑr2，Ｄ1，Ｄ2，Ｄ3，Ｄ4＞または行（２１４）内の任意の他の配置であってもよい。同様に、列（２１６）を参照して、（「Ｄ」で表記される）データを含むＲＡＩＤグリッド場所およびパリティデータを含むＲＡＩＤグリッド場所（すなわち、「Ｐc」および「Ｑc」と表記されるＲＡＩＤグリッド場所）の相対的な場所は、＜Ｄ5，Ｄ2，Ｄ6，Ｐc6，Ｄ6，Ｑc6＞，＜Ｐc6，Ｄ5，Ｄ2，Ｑc6，Ｄ6，Ｄ7＞または列（２１６）内の任意の他の配置であってもよい。
【００２６】
ＲＡＩＤコントローラ（またはシステム中の別のエンティティ）は、記憶アレイ中のどの物理アドレスにＲＡＩＤグリッド場所の各々が書込まれるかを判断してもよい。この判断は、特定のＲＡＩＤグリッドについての（「Ｄ」と表記される）データの任意のものをクライアントから受信する前に行なわれてもよい。これに代えて、判断は、ＲＡＩＤグリッド場所中のデータを記憶アレイに書込む前に行なわれてもよい。
【００２７】
当業者は、図２Ａが６×６であるＲＡＩＤグリッドを示す一方で、発明から逸脱することなく、任意の他の次元を用いてＲＡＩＤグリッドを実現してもよいことを認めるであろう。
【００２８】
発明の１つの実施形態では、Ｐパリティ値はリードソロモンシンドロームであり、そのため、Ｐパリティ関数はリードソロモンシンドロームを生成することができる任意の関数に対応してもよい。発明の１つの実施形態では、Ｐパリティ関数はＸＯＲ関数である。
【００２９】
発明の１つの実施形態では、Ｑパリティ値はリードソロモンシンドロームであり、そのため、Ｑパリティ関数はリードソロモンシンドロームを生成することができる任意の関数に対応してもよい。発明の１つの実施形態では、Ｑパリティ値はリードソロモン符号である。発明の１つの実施形態では、Ｑ＝ｇ0・Ｄ0＋ｇ1・Ｄ1＋ｇ2・Ｄ2＋…ｇn-1・Ｄn-1であり、式中、Ｑは図２Ａに関して規定されるＱパリティ値の任意の１つであり、ｇはフィールドの生成元であり、Ｄの値は（データグリッドからの値、および／またはＰもしくはＱパリティ値を含む１つ以上の行もしくは列からの値の両方を含み得る）データに対応する。
【００３０】
当業者は、図２Ａ中のＲＡＩＤグリッドが各行および列毎にＰおよびＱパリティを含む一方で、発明から逸脱することなく、発明の実施形態を、より多くのまたはより少ないパリティ値を用いて実現してもよいことを認めるであろう。たとえば、各行および列はＰパリティ値しか含まなくてもよい。別の例では、各行および列は３つのパリティ値を含んでもよい。以上言及した例は発明を限定することを意図しない。発明の１つの実施形態では、発明の実現例で用いられるパリティ値の数に係わらず、パリティ値の各々がリードソロモンシンドロームである。
【００３１】
図２Ｂは発明の１つの実施形態に従う仮想ストライプおよび物理ストライプを示す。発明の１つの実施形態では、各々のＲＡＩＤグリッド場所（たとえば２２２）は、永続性記憶装置中の２つの物理的場所（２１８，２２０）に関連付けられる。この説明の目的のため、２つの物理的場所は、物理的場所左（ＰＬL）および物理的場所右（ＰＬR）と称されることがある。以上で言及した標識は発明を説明する目的のためにのみ含まれるが、発明を限定することを意図しない。
【００３２】
以上言及した物理的場所（ＰＬL（２１８），ＰＬR（２２０））の各々は、永続性記憶装置中の区別される物理的場所に対応する。発明の１つの実施形態では、物理的場所は同じ記憶モジュール上であるが記憶モジュール中の（同じＮＡＮＤダイ上の）異なるＮＡＮＤチップ上にあってもよい。これに代えて、物理的場所の各々は別個の記憶モジュール上に位置してもよい。
【００３３】
図２Ｂに戻って、図２Ａに示されるＲＡＩＤグリッド中の各行および列は仮想ストライプと称されることがある。たとえば、図２Ｂに示されるように、１つの仮想ストライプは行（２１４）であり、行（２１４）は（Ｄ1，Ｄ2，Ｄ3，Ｐr2，Ｑr2，Ｄ4と表記される）ＲＡＩＤグリッド場所からなる。以上で論じたように、ＲＡＩＤグリッド場所の各々は永続性記憶装置中の２つの物理的場所に関連付けられる。このことから、各々の仮想ストライプは物理ストライプ左（ＰＳＬ）および物理ストライプ右（ＰＳＲ）と表記される２つの物理ストライプ（２１４Ｌ，２１４Ｒ）に関連付けられることになる。以上言及した標識は発明を説明する目的のためにのみ含まれるが、発明を限定することを意図しない。ＰＳＬ（２１４Ｌ）は、行（２１４）についてのＲＡＩＤグリッド場所に関連付けられるすべてのＰＬLを含み、ＰＳＲ（２１４Ｒ）は、行（２１４）についてのＲＡＩＤグリッド場所に関連付けられるすべてのＰＬRを含む。以下に論じるように、ＰＳＬおよびＰＳＲの各々中のパリティ値は、ＰＳＬおよびＰＳＲ中のデータ値を用いて算出される。仮想ストライプがミラードモードで動作している場合、所与の仮想ストライプについてのＰＳＬおよびＰＳＲ中のパリティ値は同一である。これに代えて、仮想ストライプが非ミラードモードで動作していれば、所与の仮想ストライプについてのＰＳＬおよびＰＳＲ中のパリティ値は異なることがある。
【００３４】
図２Ｂを参照して、ＰＬ5Lの値は、ＰＳＬ中の（パリティ値に対する）データを含むＰＬLにＰパリティ関数を適用することによって定められる（たとえば、ＰＬ5L＝ｆP（ＰＬ1L，ＰＬ2L，ＰＬ3L，ＰＬ4L）。同様に、ＰＬ6Lの値は、ＰＳＬ中の（パリティ値に対する）データを含むＰＬLにＱパリティ関数を適用することによって定められる（たとえば、ＰＬ6L＝ｆQ（ＰＬ1L，ＰＬ2L，ＰＬ3L，ＰＬ4L）。所与のＰＳＬおよびＰＳＲ中のデータ値およびパリティ値の場所は、対応の仮想ストライプ中のデータ値およびパリティ値の場所に対応する。たとえば、図２Ｂでは、仮想ストライプ（２１４）Ｐパリティ値はＲＡＩＤグリッド場所Ｐ2Rに関連付けられる。これに応じて、ＰＬ5LおよびＰＬ5RはＰパリティ値を含む。
【００３５】
図２Ｃは発明の１つの実施形態に従う記憶モジュールを示す。図２Ｃに示されるように、所与のＲＡＩＤグリッド場所に関連付けられる値（データまたはパリティ）は、同じ記憶モジュール（２２４）ではあるが記憶モジュール中の異なるチップ（２２６，２２８）に書込まれてもよい。発明の１つの実施形態では、記憶モジュール中の物理的場所に対応する物理アドレスは、ｎタプル：＜記憶モジュール、チャネル、チップ、平面、ブロック、ページ、バイト＞を用いて表わされることがある。そのような実施形態では、図２Ｃを参照して、ＰＬLおよびＰＬRの物理的場所が以下の物理アドレスに関連付けられることがある：ＰＬL：＜記憶モジュール、チャネル、チップ０、平面、ブロック、ページ、バイト＞およびＰＬR：＜記憶モジュール、チャネル、チップ１、平面、ブロック、ページ、バイト＞。当業者は、発明から逸脱することなく、記憶モジュール中の物理アドレスを他のｎタプルを用いて表わしてもよいことを認めるであろう。
【００３６】
図３Ａは、発明の１つの実施形態に従うＲＡＩＤキューブおよびＲＡＩＤキューブのさまざまな表示を示す。図３Ａに示されるように、ＲＡＩＤキューブ（３００）は、ＲＡＩＤグリッドの概念的積層体に対応する（明瞭性のため、ＲＡＩＤグリッド（３０４）のみをＲＡＩＤキューブ（３００）内に示す）。以上論じたように、ＲＡＩＤコントローラ（またはシステム中の別のエンティティ）は、ＲＡＩＤグリッド場所の各々毎にデータを記憶すべき記憶アレイ内の物理アドレスを選択する。発明の１つの実施形態では、物理アドレスの選択は、ＲＡＩＤグリッド（またはＲＡＩＤキューブ）がそれに対して保護するように設計されるＩＦＤに従って判断されてもよい。換言すると、物理アドレスは１つ以上のＩＦＤ中の不具合に対して保護する態様で選択されてもよい。たとえば、図３Ａに示されるように、所与のＲＡＩＤグリッド（３０４）についての各々のＲＡＩＤグリッド場所（図示せず）は、ＩＦＤ１およびＩＦＤ２からの一意な対の値を用いて選択されるが、ＩＦＤ３については同じ値を有する記憶アレイ（図示せず）中の物理アドレスに書込まれる（または物理アドレスに書込まれるであろう）。たとえば、記憶アレイ中のデータが、ＮＡＮＤフラッシュが（複数のＮＡＮＤダイを含む）記憶モジュールの一部であるＮＡＮＤフラッシュに記憶される場合、ＩＦＤは、（ｉ）ＩＦＤ１＝記憶モジュール、（ii）ＩＦＤ２＝チャネル、および（iii）ＩＦＤ３＝ＮＡＮＤダイであってもよい。これに応じて、所与のＲＡＩＤグリッドにおいては、各々のＲＡＩＤグリッド場所におけるデータが記憶モジュール（ＩＦＤ１）とチャネル（ＩＦＤ２）との一意な組合せに書込まれるが、（記憶モジュールの各々上の）同じＮＡＮＤダイに書込まれる。当業者は、発明が上述の３つの独立障害ドメインに限定されないことを認めるであろう。さらに、当業者は、発明がＮＡＮＤフラッシュを含む記憶アレイに限定されないことを認めるであろう。
【００３７】
図３Ａを続けて参照して、以上論じたように、ＲＡＩＤキューブ（３００）はＲＡＩＤグリッドの概念的積層体である。より具体的には、発明の１つの実施形態では、ＲＡＩＤキューブ（３００）は、（ｉ）２つ以上のＲＡＩＤグリッド（３０４，３０６，３０８）を含むデータ部分（３１４）（図２Ａを参照）と、ＰパリティＲＡＩＤグリッド（３１０）およびＱパリティＲＡＩＤグリッド（３１２）を含むパリティ部分（３１６）とを含んでもよい。
【００３８】
発明の１つの実施形態では、データ部分（３１４）中のＲＡＩＤグリッド（３０４，３０６，３０８）は、ＲＡＩＤグリッド内の（パリティデータを含む）データのみを用いてＲＡＩＤグリッド内のデータを回復できるようにするパリティデータ（図２Ａを参照）を含む。発明の１つの実施形態では、ＲＡＩＤキューブは、所与のＲＡＩＤグリッド（３０４，３０６，３０８）中の所与のＲＡＩＤグリッド場所についてのデータが、（データ部分（３１４）およびパリティ部分（３１６）の両方の中の）他のＲＡＩＤグリッドからの（パリティデータを含む）データを用いて回復され得るように配置される。発明の１つの実施形態では、ＲＡＩＤキューブのパリティ部分（３１６）はそのような回復メカニズムを可能化する。
【００３９】
発明の１つの実施形態では、ＰパリティＲＡＩＤグリッド（３１０）は、下にあるＲＡＩＤグリッド（３０４，３０６，３０８）と同次元であり、ＰパリティＲＡＩＤグリッド内のあらゆるＲＡＩＤグリッド場所におけるデータはデータ部分（３１６）中のＲＡＩＤグリッドからの（パリティデータを含む）データにＰパリティ関数（たとえばＸＯＲ関数）を適用することによって算出される（図３Ｂ−図３Ｃを参照）。同様に、ＱパリティＲＡＩＤグリッド（３１６）は、下にあるＲＡＩＤグリッド（３０４，３０６，３０８）と同次元であり、ＱパリティＲＡＩＤグリッド内のあらゆるＲＡＩＤグリッド場所におけるデータは、データ部分（３１６）中のＲＡＩＤグリッドからの（パリティデータを含む）データにＱパリティ関数を適用することによって算出される（図３Ｂ−図３Ｃを参照）。
【００４０】
図３Ｂ−図３Ｃは、発明の１つ以上の実施形態に従うＲＡＩＤキューブに入力する例を示す。例は、発明の範囲を限定することを意図しない。
【００４１】
ＲＡＩＤグリッド１（３０４）、ＲＡＩＤグリッド２（３０６）、ＲＡＩＤグリッド３（３０８）、ＰパリティＲＡＩＤグリッド（３１０）、およびＱパリティＲＡＩＤグリッド（３１２）を含む、図３Ａに描かれるＲＡＩＤキューブを考える。さらに、ＲＡＩＤキューブ中の各々のＲＡＩＤグリッド（３０４，３０６，３０８）は、ＩＦＤ１およびＩＦＤ２にわたって書込まれるが、ＩＦＤ３の一定の値を有するＲＡＩＤグリッド場所を含む。これに応じて、発明の１つの実施形態では、ＲＡＩＤグリッド中のＲＡＩＤグリッド場所（「目標ＲＡＩＤグリッド場所」）の値は、（ｉ）目標ＲＡＩＤグリッド場所が位置する行または列中のＲＡＩＤグリッド場所の値のみを用いて、（ii）目標ＲＡＩＤグリッド場所が位置するＲＡＩＤグリッド内の任意のＲＡＩＤグリッド場所の値を用いて、または（iii）目標ＲＡＩＤグリッド場所が位置するＲＡＩＤキューブ内の任意のＲＡＩＤグリッド場所の値を用いて、回復されてもよい。換言すると、発明の１つの実施形態では、ＲＡＩＤグリッドおよび／またはＲＡＩＤキューブ内のデータ値およびパリティ値の配置は、目標ＲＡＩＤグリッド場所が位置する行および列の各々に２つよりも多くの誤りが存在する場合に、目標ＲＡＩＤグリッド場所中の値が回復されるようにする。
【００４２】
図３Ｂを参照して、図３Ｂは、ＲＡＩＤキューブ（３００）のデータ部分（３１４）を構成する３つのＲＡＩＤグリッド（３０４，３０６，３０８）を含む。ＲＡＩＤグリッド（３０４，３０６，３０８）の各々中のＲＡＩＤグリッド場所の各々は、ＲＡＩＤグリッド場所のデータが書込まれる記憶アレイ中の物理的場所を規定する３タプルを含む。この例では、３タプル中の要素は、＜ＩＦＤ１、ＩＦＤ２、ＩＦＤ３＞のようなＩＦＤに対応する。３タプルは、記憶アレイ中の物理的場所がどのようにさまざまなＩＦＤにわたって選択されるかを図示する。特に、ＲＡＩＤグリッド１中のＲＡＩＤグリッド場所の各々は、ＩＦＤ１とＩＦＤ２との一意な組合せを含むが、ＩＦＤ３については同じ値を含む。たとえば，ＩＦＤ１が記憶モジュールであり、ＩＦＤ２がチャネルであり、かつＩＦＤ３がＮＡＮＤダイであれば、３タプル＜４，２，１＞は、特定のＲＡＩＤグリッド場所中のデータがチャネル２を用いて記憶モジュール４中のＮＡＮＤダイ１中の物理的場所に対応する物理アドレスに書込まれることを示す。同様に、３タプル＜２，３，１＞は、特定のＲＡＩＤグリッド場所中のデータがチャネル３を用いて記憶モジュール２中のＮＡＮＤ１中の物理的場所に対応する物理アドレスに書込まれることを示す。
【００４３】
ＲＡＩＤグリッド２（３０６）およびＲＡＩＤグリッド３（３０８）は、ＲＡＩＤグリッド１（３０４）と同様の態様で配置される。しかしながら、ＲＡＩＤグリッド２（３０６）中のＲＡＩＤグリッド場所についての３タプル中のＩＦＤ３の値は、ＲＡＩＤグリッド１（３０４）についてのＲＡＩＤグリッド場所についての３タプル中のＩＦＤ３の値とは異なっている。さらに、ＲＡＩＤグリッド３（３０８）についてのＲＡＩＤグリッド場所についての３タプル中のＩＦＤ３の値は、ＲＡＩＤグリッド１（３０４）およびＲＡＩＤグリッド２（３０６）についてのＲＡＩＤグリッド場所についての３タプル中のＩＦＤ３の値とは異なっている。
【００４４】
図３Ｃを参照して、ＰパリティＲＡＩＤグリッド（３１０）中のＲＡＩＤグリッド場所の各々の中のデータは、ＲＡＩＤグリッド１（３０４）、ＲＡＩＤグリッド２（３０６）、およびＲＡＩＤグリッド３（３０８）と同様の態様で配置される。さらに、上述のように、ＰパリティＲＡＩＤグリッド（３１０）中のＲＡＩＤグリッド場所の各々の中のデータの値は、ＲＡＩＤキューブ中のデータグリッドの各々（すなわち、ＲＡＩＤグリッド１（３０４）、ＲＡＩＤグリッド２（３０６）、およびＲＡＩＤグリッド３（３０８））の中の１つのＲＡＩＤグリッド場所からのデータを用いて算出される。たとえば、ＰパリティＲＡＩＤグリッド（３１０）中のＲＡＩＤグリッド場所＜１，１，４＞におけるデータの値は、以下のＲＡＩＤグリッド場所からのデータにＰパリティ関数（たとえばＸＯＲ関数）を適用することによって定められる：（ｉ）ＲＡＩＤグリッド１（３０４）からのデータ＜１，１，１＞、（ii）ＲＡＩＤグリッド２（３０６）からのデータ＜１，１，２＞、および（iii）ＲＡＩＤグリッド３（３０８）からのデータ＜１，１，３＞。ＰパリティＲＡＩＤグリッド（３１０）中の他のＲＡＩＤグリッド場所におけるデータの値が同様の態様で算出される。
【００４５】
さらに、ＱパリティＲＡＩＤグリッド（３１２）中のＲＡＩＤグリッド場所の各々の中のデータは、ＲＡＩＤグリッド１（３０４）、ＲＡＩＤグリッド２（３０６）、およびＲＡＩＤグリッド３（３０８）と同様の態様で配置される。さらに、上述のように、ＱパリティＲＡＩＤグリッド（３１２）中のＲＡＩＤグリッド場所の各々の中のデータの値は、ＲＡＩＤキューブ中のデータグリッドの各々（すなわち、ＲＡＩＤグリッド１（３０４）、ＲＡＩＤグリッド２（３０６）、およびＲＡＩＤグリッド３（３０８））の中の１つのＲＡＩＤグリッド場所からのデータを用いて算出される。たとえば、ＱパリティＲＡＩＤグリッド（３１２）中のＲＡＩＤグリッド場所＜１，１，５＞におけるデータの値は、以下のＲＡＩＤグリッド場所からのデータに（上述のような）Ｑパリティ関数を適用することによって定められる：（ｉ）ＲＡＩＤグリッド１（３０４）からのデータ＜１，１，１＞、（ii）ＲＡＩＤグリッド２（３０６）からのデータ＜１，１，２＞、および（iii）ＲＡＩＤグリッド３（３０８）からのデータ＜１，１，３＞。ＱパリティＲＡＩＤグリッド（３１２）中の他のＲＡＩＤグリッド場所中のデータの値が同様の態様で算出される。
【００４６】
図４Ａ−図４Ｂは、発明の１つ以上の実施形態に従うシステム中のさまざまな構成要素同士の間の関係を示す。発明の１つの実施形態では、ＲＡＩＤコントローラは、図４Ａ−図４Ｂに示される関係に追従する１つ以上のデータ構造を含む。ＲＡＩＤコントローラは、発明から逸脱することなく、以下の関係のうち１つ以上に追従してもよい。換言すると、ＲＡＩＤコントローラは、図４Ａ−図４Ｂに示される関係のすべてに追従せずに発明を実現してもよい。
【００４７】
発明の１つの実施形態では、各々のＲＡＩＤキューブ（４００）は、２つ以上のＲＡＩＤグリッド（４０２Ａ，４０２Ｎ）に関連付けられる。ＲＡＩＤコントローラがＲＡＩＤグリッドを実現しない場合は、ＲＡＩＤキューブとＲＡＩＤグリッドとの間の関係に追従しない。
【００４８】
各々のＲＡＩＤグリッド（４０２）は、（ＲＡＩＤグリッド場所とも称される）２つ以上のグリッド場所（４０４Ａ，４０４Ｎ）に関連付けられる。各々のＲＡＩＤグリッドに関連付けられるグリッド場所の数は、ＲＡＩＤグリッドの実現例に基づいて異なることがある。
【００４９】
図２Ｂに示されるように、各々のグリッド場所（４０４）は少なくとも２つの物理的場所（４０６Ａ，４０６Ｂ）に関連付けられる。グリッド場所に関連付けられる２つの物理的場所が存在する場合、物理的場所は、物理的場所左（４０６Ａ）および物理的場所右（４０６Ｂ）と称されることがある。発明の１つの実施形態では、特定のＲＡＩＤグリッドに関連付けられるすべてのグリッド場所は同じ数の物理的場所に関連付けられる。しかしながら、ＲＡＩＤコントローラによって実現される他のＲＡＩＤグリッドに関連付けられるグリッド場所が、異なる数の物理的場所に関連付けられてもよい。
【００５０】
以上で論じたように、各々のＲＡＩＤグリッド（４０２）は、仮想ストライプ（４０８）の各々がＲＡＩＤグリッド（４０２）に関連付けられるグリッド場所の組（４０４Ａ，４０４Ｎ）から構成される１つ以上の仮想ストライプ（４０８Ａ，４０８Ｎ）（図２Ｂを参照）に関連付けられる。所与のグリッド場所（４０４Ａ，４０４Ｎ）は、複数の仮想ストライプ（４０８）に関連付けられてもよい。
【００５１】
たとえば図２Ｂに示されるように、各々の仮想ストライプ（４０８）は、少なくとも２つの物理ストライプ（４０１Ａ，４１０Ｂ）に関連付けられる。仮想ストライプに関連付けられる物理ストライプが２つ存在する場合、物理ストライプは、物理ストライプ左（４１０Ａ）および物理ストライプ右（４１０Ｂ）と称されることがある。発明の１つの実施形態では、特定のＲＡＩＤグリッドに関連付けられるすべての仮想ストライプは同じ数の物理ストライプに関連付けられる。しかしながら、ＲＡＩＤコントローラによって実現される他のＲＡＩＤグリッドに関連付けられる仮想ストライプが、異なる数の物理ストライプに関連付けられてもよい。
【００５２】
各々の仮想ストライプ（４０８）は記憶モード（４１２）に関連付けられる。記憶モードはミラードモードまたは非ミラードモードであってもよい。ミラードモードでは、仮想ストライプに関連付けられる物理ストライプは、（パリティデータを含む）同じデータを含む。非ミラードモードでは、仮想ストライプに関連付けられる物理ストライプは、（パリティデータを含む）異なるデータを含んでもよい。発明の１つの実施形態では、所与のＲＡＩＤグリッドは、ミラードモードの仮想ストライプおよび非ミラードモードの仮想ストライプを含んでもよい。発明の代替的な実施形態では、記憶モードは、仮想ストライプ毎とは対照的に、グリッド場所毎に特定されてもよい。そのような実施形態では、所与の仮想ストライプは、ミラードモードおよび非ミラードモードの両方を実現するグリッド場所を含んでもよい。
【００５３】
各々の物理的場所は状態（４１４）に関連付けられる。状態（４１４）は、（データ（またはパリティデータ）が物理的場所に書込まれたことを表わす）埋まっているまたは（データ（またはパリティデータ）が場所に書込まれていないことを表わす）空に設定されてもよい。物理的場所の状態は、ＲＡＩＤコントローラがＲＡＩＤコントローラ中のデータを同定して物理的場所に書込めば（たとえば図５Ａ、ステップ５１６を参照）、埋まっているに設定されてもよい。ＲＡＩＤコントローラは各々の物理的場所の状態を空に初期化してもよい。
【００５４】
各々の物理的場所（４０６）は、永続性記憶装置内の物理的場所を規定する物理アドレス（４１６）に関連付けられる。物理アドレスは、ｎタプル＜記憶モジュール、チャネル、チップ、平面、ブロック、ページ、バイト＞を用いて特定されてもよい。発明から逸脱することなく、物理アドレスを表わすのに他のｎタプルを用いてもよい。さらに、発明から逸脱することなく、他の形態の物理アドレスを用いてもよい。
【００５５】
各々の物理アドレス（４０６）は、クライアントの観点からデータを同定する、たとえば＜オブジェクト、オフセット＞（４００）などの論理アドレス（４１８）にも関連付けられる。発明から逸脱することなく、任意の形態の論理アドレスを用いてもよい。ＲＡＩＤコントローラは、特定の論理アドレスを特定の物理アドレスに翻訳するか、またはそれ以外のやり方で関連付けるためのメカニズムを提供してもよい。
【００５６】
図４Ａ−図４Ｂには示さないが、ＲＡＩＤコントローラは、ＲＡＩＤグリッドジオメトリについての情報も維持してもよい。ＲＡＩＤグリッドジオメトリは、ＲＡＩＤグリッドの大きさ、ＲＡＩＤグリッドの各次元に関連付けられるＩＦＤ、ＲＡＩＤキューブの大きさ、ＲＡＩＤキューブの各次元に関連付けられるＩＦＤ、ならびに各々のＲＡＩＤグリッド内の各行および／または列内の（交差パリティ群内のパリティ値を含む（図２Ａを参照））各々のＰパリティ値およびＱパリティ値の場所を含んでもよいが、それらに限定されない。
【００５７】
図５Ａ−図５Ｃは、発明の１つ以上の実施形態に従うフローチャートを示す。より具体的には、図５Ａ−図５Ｃは、発明の１つ以上の実施形態に従う記憶アレイ中にデータを記憶するための方法を示す。フローチャート中のさまざまなステップを順に提示して説明するが、当業者は、ステップのうちいくつかまたはすべてを異なる順序で実行してもよく、組合せてもまたは省略してもよく、かつステップのうちいくつかまたはすべてを並列に実行してもよいことを認めるであろう。発明の１つの実施形態では、図５Ａ、図５Ｂ、および図５Ｃに示される方法を並列に行なってもよい。
【００５８】
図５Ａを参照して、ステップ５００で、データを書込む要求をクライアントから受信する。発明の１つの実施形態では、要求は、クライアントが記憶アレイに書込むことを要求しているデータの論理アドレスを含む。ステップ５０２で、記憶モード（たとえばミラードまたは非ミラード）が判断される。発明の１つの実施形態では、記憶モードは、クライアントからの要求中の情報に基づいて、または別個の要求の中でもしくは別の通信メカニズムによってクライアントに通信される情報に基づいて判断される。発明の他の実施形態では、記憶モードはＲＡＩＤコントローラ（またはシステム中の別のプロセスもしくは構成要素）によって判断される。そのような実施形態では、ＲＡＩＤコントローラ（またはシステム中の別のプロセスもしくは構成要素）は、たとえば、ポリシー設定、書込要求を発行したクライアントについての情報、ＱｏＳ保証、および／またはデータについての情報（たとえば、大きさ、種類など）に基づいて記憶モードを判断する。
【００５９】
ステップ５０４で、ステップ５０２で判断した記憶モードを実現する利用可能なグリッド場所があるか否かについての判断がなされる。発明の１つの実施形態では、ステップ５０４での判断は、たとえば、図４Ａ−図４Ｂに記載されるような情報を記憶するデータ構造を用いて、現在活性のＲＡＩＤグリッド（すなわち、図２Ａ中のデータグリッド部分２０２が埋まっていないＲＡＩＤグリッド）中の利用可能なグリッド場所を探索することに係る。利用可能なグリッド場所が存在すればグリッド場所が同定され、プロセスはステップ５１２に進む。そうでない場合、プロセスはステップ５０６に進む。
【００６０】
ステップ５０６で、新たなＲＡＩＤグリッドが割当てられる。ステップ５０８で、新たなＲＡＩＤグリッドから仮想ストライプが選択される。ステップ５１０で、選択された仮想ストライプのための記憶モードは、ステップ５０２で判断された記憶モードに対応する記憶モードを有する。
【００６１】
ステップ５１２で、グリッド場所が選択される。発明の１つの実施形態では、グリッド場所は、ステップ５０４で同定されたグリッド場所から、またはステップ５０８で選択された新たな仮想ストライプ中のグリッド場所から選択される。
【００６２】
発明の１つの実施形態では、仮想ストライプ毎の代わりにグリッド場所毎に記憶モードが判断されれば、ステップ５０８および５１０を、仮想ストライプとは対照的に特定のグリッド場所で行ってもよい。
【００６３】
図５Ａを続けて参照して、ステップ５１４で、グリッド場所に関連付けられる物理的場所を判断する。発明の１つの実施形態では、同定される物理的場所の数はステップ５０２で判断される記憶モードに依存する。たとえば、記憶モードが非ミラードであれば、グリッド場所に関連付けられる物理的場所が１つだけ同定される。これに代えて、記憶モードがミラードであれば、グリッド場所に関連付けられる少なくとも２つの物理的場所が同定される。
【００６４】
ステップ５１６で、ＲＡＩＤコントローラは、データ構造のうち１つ以上を更新して、データが物理的場所に書込まれるべきであることを反映させる（図４Ａ−図４Ｂを参照）。図５Ａに示されるステップは、データが記憶アレイに書込まれるたびに予め形成されてもよい。
【００６５】
図５Ｂを参照して、図５Ｂは、発明の１つ以上の実施形態に従ってＲＡＩＤグリッドを記憶アレイに書込むための方法を示す。図５Ｂを参照して、ステップ５２０で、所与のＲＡＩＤグリッド（たとえば図２Ａ中の２０２）内のデータグリッドが埋まっているか否かについての判断がなされる。発明の１つの実施形態では、データグリッドは、データグリッド中のグリッド場所に関連付けられるすべての物理的場所のすべての状態が埋まっているに設定されている場合に、「埋まっている」である。発明の１つの実施形態では、この判断は、図４Ａおよび図４Ｂに関して説明されるデータ構造のうち１つ以上を用いてなされる。所与のＲＡＩＤグリッド内のデータグリッドが埋まっていれば、プロセスはステップ５２２に進む。そうでない場合はプロセスは終了する。
【００６６】
ステップ５２２で、対応の物理的場所からの適切な値を用いて（たとえば、以上で論じた図２Ｂを参照）、行Ｐパリティ群（たとえば図２Ａ中の２０４）中のＲＡＩＤグリッド場所に対応する各物理的場所毎にＰパリティが算出される。ステップ５２４で、対応の物理的場所からの適切な値を用いて（たとえば以上で論じた図２Ｂを参照）、行Ｑパリティ群（たとえば図２Ａ中の２０６）中のＲＡＩＤグリッド場所に対応する各物理的場所毎にＱパリティが算出される。ステップ５２６で、対応の物理的場所からの適切な値を用いて（たとえば以上で論じた図２Ｂを参照）、列Ｐパリティ群（たとえば図２Ａ中の２０８）中のＲＡＩＤグリッド場所に対応する各物理的場所毎にＰパリティが算出される。ステップ５２８で、対応の物理的場所からの適切な値を用いて（たとえば以上で論じた図２Ｂを参照）列Ｑパリティ群（たとえば図２Ａ中の２１０）中のＲＡＩＤグリッド場所に対応する各物理的場所毎にＱパリティが算出される。
【００６７】
ステップ５３０で、行Ｐパリティ群（たとえば図２Ａ中の２０４）、行Ｑパリティ群（たとえば図２Ａ中の２０６）、行Ｑパリティ群（たとえば図２Ａ中の２０６）、および列Ｑパリティ群（たとえば図２Ａ中の２１０）のうち１つ以上の中のＲＡＩＤグリッド場所に対応する物理的場所からの適切な値を用いて、交差パリティ群（たとえば図２Ａ中の２１２）中のＲＡＩＤグリッド場所に対応する各物理的場所毎のパリティ値が算出される。
【００６８】
ステップ５３２で、ＲＡＩＤグリッドについてのＲＡＩＤグリッド場所に対応する各物理的場所に関連付けられるデータが記憶アレイ中の適切な物理アドレスに書込まれる。発明の１つの実施形態では、（パリティデータを含む）データが２段階で記憶アレイに書込まれる。第１の段階では、ＲＡＩＤグリッド中のグリッド場所の左側部分に関連付けられる各物理的場所に関連付けられるデータまたはパリティデータが適切な記憶モジュールに並列に書込まれる。第２の段階では、ＲＡＩＤグリッド中のグリッド場所の右側部分に関連付けられる各物理的場所に関連付けられるデータまたはパリティデータが適切な記憶モジュールに並列に書込まれる。２段階の書込の例を以下図６Ａ−図６Ｃに説明する。発明の１つの実施形態では、ＲＡＩＤグリッド場所の各々毎にデータを書込むべき物理アドレスが、図４Ａ−図４Ｂに関して説明されるデータ構造のうち１つ以上から得られる。ステップ５３４で、図４Ａ−図４Ｂに関して説明される１つ以上のデータ構造が更新されて、ＲＡＩＤグリッドが記憶アレイに書込まれたことを反映させる。
【００６９】
以上の実施形態はＲＡＩＤグリッドについての（パリティデータを含む）すべてのデータを並列に書込むことを記載するが、発明から逸脱することなく、（パリティデータを含む）データの書込を段階的に行なってもよい。たとえば、（パリティデータを除く）データを記憶アレイに並列に書込んでもよい一方で、パリティデータを後で記憶アレイに書込んでもよい。発明から逸脱することなく、他のやり方で書込を段階的に行なってもよい。
【００７０】
発明の１つの実施形態では、ＲＡＩＤコントローラが３Ｄ  ＲＡＩＤ方式を実現していれば、ＲＡＩＤコントローラは図５Ｃに示される方法を行なってもよい。図５Ｃを参照して、ステップ５３６で、ＲＡＩＤキューブのデータ部分が埋まっているか否かについての判断を行なう。発明の１つの実施形態では、ＲＡＩＤキューブのデータ部分中のグリッド場所に対応するすべての物理的場所の状態が埋まっているに設定されている場合に、ＲＡＩＤキューブのデータ部分は埋まっている。ＲＡＩＤキューブのデータ部分が埋まっているであれば、プロセスはステップ５３８に進む。そうでない場合、プロセスは終了する。発明の１つの実施形態では、この判断は、図４Ａ−図４Ｂに関して説明したデータ構造のうち１つ以上を用いて行なわれる。
【００７１】
ステップ５３８で、ＰパリティＲＡＩＤグリッド（たとえば図３Ａ中の３１０）中のＲＡＩＤグリッド場所に対応する各物理的場所毎のＰパリティ値が算出される。発明の１つの実施形態では、ＲＡＩＤキューブのデータ部分（たとえば図３Ａ中の３１４）中のＲＡＩＤグリッドの各々から得られた１つの値を用いて、ＲＡＩＤグリッド場所の各々毎の値が算出される。
【００７２】
ステップ５４０で、ＱパリティＲＡＩＤグリッド（たとえば図３Ａ中の３１２）中のＲＡＩＤグリッド場所に対応する各物理的場所毎のＱパリティ値が算出される。発明の１つの実施形態では、ＲＡＩＤキューブのデータ部分（たとえば図３Ａ中の３１４）中のＲＡＩＤグリッドの各々から得られた１つの値を用いて、ＲＡＩＤグリッド場所の各々毎の値が算出される。
【００７３】
ステップ５４２で、パリティＲＡＩＤグリッド（たとえば、ＰパリティＲＡＩＤグリッドおよびＱパリティＲＡＩＤグリッド）中のＲＡＩＤグリッド場所に対応する各物理的場所に関連付けられるデータが記憶アレイ中の適切な物理アドレスに書込まれる。発明の１つの実施形態では、ＲＡＩＤグリッド場所の各々毎にデータを書込むべき物理アドレスは、図４Ａ−図４Ｂに関して説明したデータ構造のうち１つ以上から得られる。ステップ５４４で、図４Ａ−図４Ｂに関して説明した１つ以上のデータ構造が更新されて、ＲＡＩＤキューブが記憶アレイに書込まれたことを反映させる。
【００７４】
図６Ａ−図６Ｃは、発明の１つ以上の実施形態に従う例を示す。例は、発明の範囲を限定することを意図しない。
【００７５】
図６Ａを参照して、３６個のグリッド場所（ＧＬ）を含むＲＡＩＤグリッド（６００）を示す。さらに、以上言及したＧＬに対応する物理的場所は、図６Ａに示されるように記憶モジュールおよびチャネルにわたって分散される。データの４つの部分（Ｄ1A−Ｄ4A）が書込まれて仮想ストライプ（６０２）中のＧＬ1，ＧＬ2，ＧＬ3，ＧＬ4に対応する物理的に書込まれるシナリオを考える。さらに、この例の目的のため、仮想ストライプがミラードモードを実現しており、かつＧＬ5がＰパリティ値を含み、ＧＬ6が仮想ストライプ（６０２）についてのＱパリティ値を含むと仮定する。以下の表は、仮想ストライプがミラードモードを実現している場合に仮想ストライプ（６０２）を用いて対応の物理的場所の各々の中に記憶されるデータを要約する。
【００７６】
【表１】
0005968562.tif 000002
【００７７】
データ（Ｄ1A−Ｄ4AおよびＤ1B−Ｄ4B）の８つの部分が書込まれて仮想ストライプ（６０２）中のＧＬ1，ＧＬ2，ＧＬ3，ＧＬ4に対応する物理的場所に書込まれる代替的なシナリオを考える。さらに、この例の目的のため、仮想ストライプが非ミラードモードを実現しており、かつＧＬ5がＰパリティ値を含み、ＧＬ6が仮想ストライプ（６０２）のＱパリティ値を含むと仮定する。以下の表は、仮想ストライプが非ミラードモードを実現している場合に仮想ストライプ（６０２）を用いて対応の物理的場所の各々の中に記憶されるデータを要約する。
【００７８】
【表２】
0005968562.tif 000003
【００７９】
図６Ａを参照して、仮想ストライプ（６０４）は、仮想ストライプ（６０２）に関して上述されたのと同じ態様で埋められてもよい。
【００８０】
発明の１つの実施形態では、ＲＡＩＤグリッド中の各々の物理的場所がクライアントからのデータまたはパリティデータ（すなわちＰまたはＱパリティデータ）に一旦関連付けられると、ＲＡＩＤグリッドは、記憶モジュールに書込まれる準備ができる。書込プロセスは２段階に分割される。第１の段階では、グリッド場所の左側部分に関連付けられる各物理的場所に関連付けられるデータまたはパリティデータが記憶アレイ中の適切な場所に並列に書込まれる。第２の段階では、グリッド場所の右側部分に関連付けられる各物理的場所に関連付けられるデータまたはパリティデータが記憶アレイ中の適切な場所に並列に書込まれる。
【００８１】
以下は、ミラードモードに従って（Ｄと表記される）データを記憶アレイに書込む例である。この例では、（上述のような）データ（Ｄ1A−Ｄ4A）が記憶アレイに書込まれると仮定する。（仮想ストライプ（６０２）を含む）ＲＡＩＤグリッドが記憶アレイに書込まれる準備ができると、ＲＡＩＤコントローラ（図示せず）は、書込プロセスの段階１で３６個の書込コマンドを並列に発行する。具体的に、所与の記憶モジュールに対する各書込コマンドが記憶モジュール上の異なるチップを標的としている各記憶モジュールに６つの書込コマンドが発行される。表３は、書込プロセスの段階１の間に発行される仮想ストライプ（６０２）の「左側部分」に対応する書込コマンドのサブセットを示す。
【００８２】
【表３】
0005968562.tif 000004
【００８３】
書込プロセスの段階１の後に、ＲＡＩＤコントローラは、書込プロセスの段階２で３６個の書込コマンドを並列に発行する。具体的に、所与の記憶モジュールに対する各々の書込コマンドが記憶モジュール上の異なるチップを標的としている各記憶モジュールに６つの書込コマンドが発行される。表４は、書込プロセスの段階２の間に発行される仮想ストライプ（６０２）の「右側部分」に対応する書込コマンドのサブセットを示す。
【００８４】
【表４】
0005968562.tif 000005
【００８５】
図６Ｂは、以上で言及した書込段階の各々の間に、フラッシュモジュールの各々の中のどのチップが活性に書込んでいる（Ｗ）かまたは読出要求（Ｒ）を供給するのに利用可能であるかを示す。図６Ｃは、表３および表４中のコマンドが発行された後の記憶モジュール中の１２個のチップの状態を示す。
【００８６】
図７Ａ−図７Ｂは、発明の１つ以上の実施形態に従うフローチャートを示す。より具体的には、図７Ａ−図７Ｂは、発明の１つ以上の実施形態に従って記憶アレイからデータを得るための方法を示す。フローチャート中のさまざまなステップを順に提示しかつ説明するが、当業者は、ステップのうちいくつかまたはすべてを異なる順序で行っても、これらを組合せてももしくは省略してもよく、かつステップのいくつかまたはすべてを並列に実行してもよいことを認めるであろう。発明の１つの実施形態では、図７Ａおよび図７Ｂに示される方法を並列に行ってもよい。
【００８７】
ステップ７００で、永続性記憶装置からデータを得る要求が受信される。発明の１つの実施形態では、要求は、クライアントが発行する読出要求であってもよい。発明の１つの実施形態では、要求は、データに関連付けられる論理アドレスを特定してもよい。
【００８８】
ステップ７０２で、要求されたデータに関連付けられる物理アドレスを得る。発明の１つの実施形態では、以上言及した物理アドレスは、図４Ａ−図４Ｂに関して上述されたデータ構造を用いて判断されてもよい。
【００８９】
ステップ７０４で、データがミラーリングされているか否かについての判断がなされる。発明の１つの実施形態では、この判断は、（ｉ）物理アドレスが関連付けられているグリッド場所を判断すること、（ii）グリッド場所が関連付けられている仮想ストライプを判断すること、および（iii）（ii）で同定された仮想ストライプに関連付けられる記憶モードを判断すること、を含んでもよい。記憶モードがグリッドレベル毎に設定されていれば、ステップ７０４での判断は、（ｉ）物理アドレスが関連付けられるグリッド場所を判断すること、および（ii）（ｉ）で同定されたグリッド場所に関連付けられる記憶モードを判断すること、によって行なわれてもよい。仮想記憶がミラードモードを実現している場合、データがミラーリングされて、プロセスはステップ７０６に進む。そうでない場合、プロセスはステップ７０８に進む。
【００９０】
データがミラーリングされると、少なくとも２つの異なる物理的場所からデータを得てもよい。そのような場合、ステップ７０６で、データが位置する物理的場所のいずれかが塞がっていない（すなわち、データが位置するチップが書込または消去要求を供給していない）か否かについての判断がなされる。データが位置する物理的場所のいずれかが塞がっていなければ、プロセスはステップ７１０に進む。そうでない場合、プロセスはステップ７０８に進む。
【００９１】
ステップ７０８で、ステップ７０２で得られた物理アドレスを用いて、読出要求が永続性記憶装置に発行される。ステップ７１０で、塞がっていない物理的場所に対応する（ステップ７０２で得られた）物理アドレスを用いて読出要求が永続性記憶装置に発行される。ステップ７１２で、要求中の物理アドレスに対応する物理的場所から（ステップ７０８または７１０を介して）データを得る。
【００９２】
図７Ｂを参照して、ステップ７１４で、ステップ７１２で得られたデータが破損しているか否かについての判断がなされる。発明の１つの実施形態では、ＲＡＩＤコントローラは、データが破損しているか否かを判断するための任意の公知の方法（たとえばチェックサム）を実現してもよい。データが破損していなければ、プロセスはステップ７１６に進む。そうでない場合、プロセスはステップ７１８に進む。ステップ７１６で、データがクライアントに戻され、プロセスが終了する。発明の別の実施形態では、−たとえば永続性記憶装置が破損しているかまたはプラグを抜かれているためにデータを得ることができない場合、または読出コマンドが機能しない場合に、プロセスはステップ７１８に進んでもよい。
【００９３】
ステップ７１８で、ＲＡＩＤコントローラは、どのＲＡＩＤグリッドからデータが得られたかを判断する。ステップ７２０で、ＲＡＩＤコントローラは、利用可能であれば、データのミラーリングされたコピーを用いて（図２Ａを参照）、ならびに／またはデータを含んだ物理的場所が位置する行および／もしくは列内の他のＲＡＩＤグリッド場所に対応する物理的場所を用いて、データの再構築を試みる。
【００９４】
ステップ７２２で、ステップ７２０での再構築の試みが成功したか否かについての判断がなされる。発明の１つの実施形態では、ＲＡＩＤコントローラは、再構築の試みが成功したか否かを判断するのに任意の公知の方法（たとえばチェックサム）を実現してもよい。ステップ７２２での再構築の試みが成功すれば、プロセスはステップ７２４に進む。そうでない場合、プロセスはステップ７２７に進む。ステップ７２４で、再構築されたデータがクライアントに戻され、プロセスは終了する。
【００９５】
ステップ７２６で、ＲＡＩＤグリッドの他の行および／または列中の他のＲＡＩＤグリッド場所に対応する物理的場所を用いて、ＲＡＩＤコントローラはデータの再構築を試みる。ステップ７２７で、ステップ７２６での再構築の試みが成功したか否かについての判断がなされる。発明の１つの実施形態では、ＲＡＩＤコントローラは、再構築の試みが成功したか否かを判断するのに任意の公知の方法（たとえばチェックサム）を実現してもよい。ステップ７２６での再構築の試みが成功すれば、プロセスはステップ７２４に進む。そうでない場合、プロセスはステップ７３０に進む。
【００９６】
ステップ７３０で、ＲＡＩＤコントローラは、ＲＡＩＤキューブ中の他のＲＡＩＤグリッドに対応する物理的場所を用いてデータの再構築を試みる。ステップ７３２で、ステップ７３０での再構築の試みが成功したか否かについての判断がなされる。発明の１つの実施形態では、ＲＡＩＤコントローラは、再構築の試みが成功したか否かを判断するのに任意の公知の方法（たとえばチェックサム）を実現してもよい。ステップ７３０での再構築の試みが成功すれば、プロセスはステップ７３４に進む。そうでない場合、プロセスはステップ７３６に進む。ステップ７３４で、再構築されたデータがクライアントに戻され、プロセスが終了する。ステップ７３６で、ＲＡＩＤコントローラはクライアントにエラーを返し、これは、要求されたデータがＲＡＩＤコントローラによって記憶アレイから取出せないことを示す。
【００９７】
当業者は、ＲＡＩＤコントローラが３Ｄ  ＲＡＩＤ方式を実現している場合にのみ、ＲＡＩＤキューブ中の他のＲＡＩＤグリッドを用いたデータの再構築が発生することを認めるであろう。
【００９８】
図８Ａ−図８Ｅは、発明の１つ以上の実施形態に従う例を示す。例は、発明の範囲を限定することを意図しない。図８Ａを参照して、システムがグリッド場所の組（たとえば２Ａを参照）を含むＲＡＩＤグリッド（８００）を含むシナリオを考える。さらに、グリッド場所（図示せず）は、すべてミラードモードを実現する仮想ストライプの組（図示せず）に関連付けられる。最後に、図８Ａに示されるように、グリッド場所（図示せず）の各々は２つの物理的場所（たとえば２Ｂを参照）に関連付けられる。その結果、ＲＡＩＤグリッド（８００）は、２組の物理的場所−物理的場所左（８００Ｌ）および物理的場所右（８００Ｒ）、に関連付けられる。
【００９９】
図８Ｂを参照して、クライアントが、物理的場所左（８００Ｌ）中のＰＬL1および物理的場所右（８００Ｒ）中のＰＬR1に位置するデータを要求したシナリオを考える。しかしながら、ＰＬL1およびＰＬR1中のデータは、（陰で表記されるように）破損している。ＲＡＩＤコントローラはまず、行（８０４）および／または列（８０２）中の物理的場所からのデータを用いて、（図７Ｂ中のステップ７２０に従って）ＰＬL1中のデータの再構築を試みる。しかしながら、行（８０４）および列（８０２）は各々、破損したデータを含む３つの物理的場所を含むので、ＰＬL1中のデータを、行（８０４）および／または列（８０２）からのデータのみを用いて回復することができない。
【０１００】
図８Ｃを参照して、ＲＡＩＤコントローラは、物理的場所左（８００Ｌ）中の他の物理的場所からのデータを用いて（図７Ｂ中のステップ７２６に従って）ＰＬL1中のデータの再構築を試みる。この例では、究極的にＰＬL1を再構築するのに用いることができる物理的場所左（８００Ｌ）中の行または列が存在しない。しかしながら、ＲＡＩＤコントローラは、物理的場所左（８００Ｌ）中の行（８０６）中の残余の物理的場所中のデータと組合せて物理的場所右（８００Ｒ）中のＰＬR2（図８Ｂを参照）からのデータを用いて、行（８０６）中のすべての破損したデータを再構築することができる。図８Ｄを参照して、行（８０６）中の破損したデータの再構築に基づいて、ＲＡＩＤコントローラは、列（８０８）中のすべての破損したデータを再構築することができる。最後に、図８Ｅを参照して、列（８０８）中の破損したデータの再構築に基づいて、ＲＡＩＤコントローラは、行（８１０）中の他の破損していないデータを用いてＰＬL1中のデータを再構築することができる。発明の１つの実施形態では、図８Ｂ−図８Ｅ中に示されるようなさまざまな破損したデータの再構築は、図７Ｂ中のステップ７２０および７２６の一部として行なわれる。
【０１０１】
図８Ａ−図８Ｅ中に示されないが、ＲＡＩＤグリッド中のデータのみを用いてＰＬL1中のデータを再構築することができない場合、ＲＡＩＤコントローラは、ＲＡＩＤコントローラが３Ｄ  ＲＡＩＤ方式を実現していれば、ＲＡＩＤキューブ（図示せず）内の他のＲＡＩＤグリッド中のデータを用いて、（図７Ｂ中のステップ７３００に従って）ＰＬL1中のデータの再構築を試みるであろう。
【０１０２】
ＩＦＤに沿った記憶アレイにデータを記憶することおよび／またはＮＡＮＤフラッシュ中にデータを記憶することに関して発明のさまざまな例を説明したが、発明から逸脱することなく、発明の実施形態を任意の多次元記憶装置上で実現してもよいことを当業者は認めるであろう。たとえば、発明の１つ以上の実施形態は、ＲＡＩＤグリッド中の各々のＲＡＩＤグリッド場所毎のデータが別個の記憶装置に記憶される、記憶装置（磁気的、光学的、固体、または任意の他の種類の記憶装置）の二次元アレイを用いて実現されてもよい。
【０１０３】
さらに、発明の１つの実施形態では、ＲＡＩＤコントローラが記憶装置の二次元アレイを用いて３Ｄ  ＲＡＩＤ方式を実現している場合、ＲＡＩＤコントローラは、ｎタプル＜記憶装置ｘ、記憶装置ｙ、論理ブロックアドレス（ＬＢＡ）ｚ＞を用いてＲＡＩＤグリッド場所の各々毎にデータを記憶してもよい。なお、ｘおよびｙは記憶装置のアレイの次元である。さらに、所与のＲＡＩＤグリッドについて、ＬＢＡは、単一のＲＡＩＤグリッドについての各々のＲＡＩＤグリッド場所毎に一定である。しかしながら、ＬＢＡはＲＡＩＤキューブ中のＲＡＩＤグリッドにわたって異なる。
【０１０４】
二次元の記憶装置アレイを用いて発明の実施形態を実現するための以上の例は、発明の範囲を限定することを意図しない。
【０１０５】
２Ｄ  ＲＡＩＤ方式および３Ｄ  ＲＡＩＤ方式に関して発明を説明したが、発明の実施形態を任意の多次元ＲＡＩＤ方式に拡張してもよいことを当業者は認めるであろう。
【０１０６】
発明の１つ以上の実施形態は、システム中の１つ以上のプロセッサによって実行される命令を用いて実現されてもよい。さらに、そのような命令は、１つ以上の非一時的コンピュータ読出可能媒体上に記憶されるコンピュータ読出可能命令に対応してもよい。
【０１０７】
限られた数の実施形態に関して発明を説明したが、この開示の利益を得る当業者は、本明細書中に開示されるような発明の範囲から逸脱しない他の実施形態を企図することができることを認めるであろう。これに応じて、発明の範囲は添付の請求項によってのみ限定されるべきである。
【図１】
0005968562.tif 000006
【図２Ａ】
0005968562.tif 000007
【図２Ｂ】
0005968562.tif 000008
【図２Ｃ】
0005968562.tif 000009
【図３Ａ】
0005968562.tif 000010
【図３Ｂ】
0005968562.tif 000011
【図３Ｃ】
0005968562.tif 000012
【図４Ａ】
0005968562.tif 000013
【図４Ｂ】
0005968562.tif 000014
【図５Ａ】
0005968562.tif 000015
【図５Ｂ】
0005968562.tif 000016
【図５Ｃ】
0005968562.tif 000017
【図６Ａ】
0005968562.tif 000018
【図６Ｂ】
0005968562.tif 000019
【図６Ｃ】
0005968562.tif 000020
【図７Ａ】
0005968562.tif 000021
【図７Ｂ】
0005968562.tif 000022
【図８Ａ】
0005968562.tif 000023
【図８Ｂ】
0005968562.tif 000024
【図８Ｃ】
0005968562.tif 000025
【図８Ｄ】
0005968562.tif 000026
【図８Ｅ】
0005968562.tif 000027