"明細書に記載の発明。本発明の概要本発明の第1の実施形態において、データ損失なしに複数の格納デバイスのうちの一つの損失からの回復を可能にするために、該複数の格納デバイスにデータを格納する方法が提供される。該方法は、故障許容を提供するために、少なくとも一つの冗長スキームを使用して、該複数の格納デバイスの上にデータを格納することと、第1の格納デバイスの損失の際に、データの故障許容を復元するために、一つ以上の残りの該格納デバイスを自動的に再構成することとを含む。本発明の第2の実施形態において、複数の格納デバイスと、該複数の格納デバイスに動作可能なように結合された格納マネジャーとを備える格納システムが提供される。該格納マネジャーは、故障許容を提供するために、少なくとも一つの冗長スキームを使用して、該複数の格納デバイスの上にデータを格納し、データの故障許容を復元するために、一つ以上の残りの該格納デバイスを自動的に再構成する。関連する実施形態において、ミラリング、パリティを用いたストライピング、RAID6、二重パリティ、対角線パリティ、低密度パリティチェックコード、およびターボコードのうちの少なくとも一つを使用して、データが上記複数の格納デバイスに格納され得る。該格納デバイスは、4つ以上の格納デバイスにわたる第1のストライピングパターンを3つ以上の残りの格納デバイスにわたる第2のストライピングパターンに変換すること;3つの格納デバイスにわたるストライピングパターンを2つの残りの格納デバイスにわたるミラリングパターンに変換すること;2つの格納デバイスにわたるミラリングパターンを単一の格納デバイスの上のミラリングパターンに変換すること;格納デバイスの第1のペアにわたるミラリングパターンを格納デバイスの第2のペアにわたるミラリングパターンに変換すること;または一つの格納デバイスの上のミラリングパターンを別の格納デバイスの上のミラリングパターンに変換することによって、再構成され得る。自動的な再構成を可能にするために、十分な量の利用可能な格納スペースが、上記複数の格納デバイスにわたって維持され得る。このことは、たとえば、多数のあり得る故障状態の各々についての再構成シナリオを決定することと、上記自動的な再構成を可能にするために、各格納デバイスの上で必要とされる格納スペースの総量を決定することとによって、なされ得る。上記必要とされる格納スペースの総量を決定することは、データの冗長格納のために各ドライブの上で必要とされるスペースの量を決定することと、必要とされるスペアワーキングスペース領域の量を決定することとを含み得る。自動的な再構成を可能にするためには不十分な量の利用可能な格納スペースがある場合には、追加の格納が必要とされることを示すために信号が生成され得るたとえば、インジケータの状態を変化させることによって。複数の格納スロットを有する格納システムにおいて、どのスロットに追加の格納が配置されるべきかについて決定がなされ得、その場合には信号がスロットを示し得る。本発明は、例えば、以下を提供する。項目1データ損失なしに複数の格納デバイスのうちの一つの損失からの回復を可能にするために、該複数の格納デバイスにデータを格納する方法であって、該方法は、故障許容を提供するために、少なくとも一つの冗長スキームを使用して、該複数の格納デバイスの上にデータを格納することと、第1の格納デバイスの損失の際に、データの故障許容を復元するために、一つ以上の残りの該格納デバイスを自動的に再構成することとを包含する、方法。項目2上記データを格納することが、ミラリング、パリティを用いたストライピング、RAID6、二重パリティ、対角線パリティ、低密度パリティチェックコード、およびターボコードのうちの少なくとも一つを使用してデータを格納することを含む、項目1に記載の方法。項目3上記データを格納することが、第1の冗長スキームを使用して格納デバイスの第1の配置の上にデータを格納することを含み、上記一つ以上の残りの格納デバイスを自動的に再構成することが、a格納デバイスの同じ配置の上の第2の冗長スキームと、b格納デバイスの異なる配置の上の第2の冗長スキームと、c格納デバイスの異なる配置の上の同じ冗長スキームとのうちの一つを使用して自動的にデータを再構成することを包含する、項目1に記載の方法。項目4上記一つ以上の残りの格納デバイスを自動的に再構成することが、4つ以上の格納デバイスにわたる第1のストライピングパターンを、3つ以上の残りの格納デバイスにわたる第2のストライピングパターンに変換することを包含する、項目3に記載の方法。項目5上記一つ以上の残りの格納デバイスを自動的に再構成することが、3つの格納デバイスにわたるストライピングパターンを、2つの残りの格納デバイスにわたるミラリングパターンに変換することを包含する、項目3に記載の方法。項目6上記一つ以上の残りの格納デバイスを再構成することが、2つの格納デバイスにわたるミラリングパターンを、単一の格納デバイスの上のミラリングパターンに変換することを包含する、項目3に記載の方法。項目7上記一つ以上の残りの格納デバイスを再構成することが、格納デバイスの第1のペアにわたるミラリングパターンを、格納デバイスの第2のペアにわたるミラリングパターンに変換することを包含する、項目3に記載の方法。項目8上記一つ以上の残りの格納デバイスを自動的に再構成することが、一つの格納デバイスの上のミラリングパターンを、別の格納デバイスの上のミラリングパターンに変換することを包含する、項目3に記載の方法。項目9上記自動的な再構成を可能にするために、上記複数の格納デバイスにわたって十分な量の利用可能な格納スペースを維持することをさらに包含する、項目1に記載の方法。項目10上記十分な量の利用可能な格納スペースを維持することが、多数のあり得る故障状態の各々についての再構成シナリオを決定することと、上記自動的な再構成を可能にするために、各格納デバイスの上で必要とされる格納スペースの総量を決定することとを包含する、項目9に記載の方法。項目11上記必要とされる格納スペースの総量を決定することが、データの冗長格納のために各ドライブの上で必要とされるスペースの量を決定することと、必要とされるスペアワーキングスペース領域の量を決定することとを包含する、項目10に記載の方法。項目12上記複数の格納デバイスが上記自動的な再構成を可能にするための適切な量の利用可能な格納スペースを含むかどうかを決定することと、該複数の格納デバイスが不適切な量の利用可能な格納スペースを含む場合に、追加の格納が必要とされることを示すために信号を生成することとを包含する、項目9に記載の方法。項目13上記信号を生成することが、インジケータの状態を変化させることを包含する、項目12に記載の方法。項目14上記複数の格納デバイスが、複数のスロットを有するアレイにインストールされ、上記信号を生成することが、該アレイのどのスロットに追加の格納容量が配置されるべきかを決定し、該スロットを示すことを包含する、項目12に記載の方法。項目15格納システムであって、複数の格納デバイスと、該複数の格納デバイスに動作可能なように結合された格納マネジャーとを備え、該格納マネジャーは、故障許容を提供するために、少なくとも一つの冗長スキームを使用して、該複数の格納デバイスの上にデータを格納し、第1の格納デバイスの損失の際に、データの故障許容を復元するために、一つ以上の残りの該格納デバイスを自動的に再構成する、格納システム。項目16ミラリング、パリティを用いたストライピング、RAID6、二重パリティ、対角線パリティ、低密度パリティチェックコード、およびターボコードのうちの少なくとも一つを使用して、データが上記複数のデバイスの上に格納される、項目15に記載の格納システム。項目17データが、第1の冗長スキームを使用して格納デバイスの第1の配置の上に格納され、上記格納マネジャーが、a格納デバイスの同じ配置の上の第2の冗長スキームと、b格納デバイスの異なる配置の上の第2の冗長スキームと、c格納デバイスの異なる配置の上の同じ冗長スキームとのうちの一つを使用して自動的にデータを再構成する、項目15に記載の格納システム。項目18上記格納マネジャーが、4つ以上の格納デバイスにわたる第1のストライピングパターンを、3つ以上の残りの格納デバイスにわたる第2のストライピングパターンに自動的に変換する、項目17に記載の格納システム。項目19上記格納マネジャーが、3つの格納デバイスにわたるストライピングパターンを、2つの残りの格納デバイスにわたるミラリングパターンに自動的に変換する、項目17に記載の格納システム。項目20上記格納マネジャーが、2つの格納デバイスにわたるミラリングパターンを、単一の格納デバイスの上のミラリングパターンに自動的に変換する、項目17に記載の格納システム。項目21上記格納マネジャーが、格納デバイスの第1のペアにわたるミラリングパターンを、格納デバイスの第2のペアにわたるミラリングパターンに自動的に変換する、項目17に記載の格納システム。項目22上記格納マネジャーが、一つの格納デバイスの上のミラリングパターンを、別の格納デバイスの上のミラリングパターンに自動的に変換する、項目17に記載の格納システム。項目23上記格納マネジャーが、上記自動再構成を可能にするために、上記複数の格納デバイスにわたって、十分な量の利用可能な格納スペースを維持する、項目15に記載の格納システム。項目24上記格納マネジャーが、多数のあり得る故障状態の各々についての再構成シナリオを決定し、上記自動的な再構成を可能にするために、各格納デバイスの上で必要とされる格納スペースの総量を決定する、項目23に記載の格納システム。項目25上記格納マネジャーが、データの冗長格納のために各ドライブの上で必要とされるスペースの量を決定し、必要とされるスペアワーキングスペース領域の量を決定する、項目24に記載の格納システム。項目26上記格納マネジャーが、上記複数の格納デバイスが上記自動的な再構成を可能にするための適切な量の利用可能な格納スペースを含むかどうかを決定し、該複数の格納デバイスが不適切な量の利用可能な格納スペースを含む場合に、追加の格納が必要とされることを示す信号を生成する、項目23に記載の格納システム。項目27上記格納マネジャーが、上記信号を生成するためにインジケータの状態を変化させる、項目26に記載の格納システム。項目28上記複数の格納デバイスが、複数のスロットにインストールされ、上記格納マネジャーが、該アレイにおけるどのスロットに追加の格納容量が配置されるべきかを決定し、該スロットを示す、項目26に記載の格納システム。本発明の前述の特徴は、添付の図面を参照して、以下の詳細な説明を参照することによって容易に理解される。具体的な実施形態の詳細な説明定義。本明細書および添付の特許請求の範囲において使用されるように、文脈上特別な断りがない限り、以下の用語は指示された意味を有する。オブジェクトのチャンクは、オブジェクトの抽象スライスであり、使用される物理的格納とは無関係に作られ、一般的にオブジェクトの隣接バイトの固定数である。データ格納のための故障許容パターンは、データが一つ以上の格納デバイスにわたって冗長に分散される事項particularであり、なかでも、ミラリングたとえばRAID1に類似した方法で、ストライピングたとえばRAID5に類似した方法で、RAID6、二重パリティ、対角線パリティ、低密度パリティチェックLowDensityParityCheckコード、ターボコード、または他の冗長スキーム、または冗長スキームの組み合わせであり得る。所定のチャンクのハッシュ数は、該所定のチャンクが任意の他のチャンクのハッシュ数とは一般的に異なるハッシュ数を生成するときに、該他のチャンクが該所定のチャンクと同一のデータコンテンツを有するときを除いて、一意である。すなわち、2つのチャンクは、それらのコンテンツが同一でないときはいつでも、異なるハッシュ数を一般的に有する。以下に詳細に説明されるように、一意という用語は、この文脈において、同一でないチャンクに対して共通ハッシュ数をたまに生成するハッシュ関数から生成されるハッシュ数をカバーするように使用される。なぜなら、ハッシュ関数は、異なるチャンクについて異なる数を生成することにおいて、一般的に完全ではないからである。領域は、格納媒体の上の隣接する物理ブロックのセットであるたとえばハードドライブ。ゾーンは、2つ以上の領域からなる。ゾーンを構成する領域は、一般的に隣接することが要求されない。以下に説明される例示的な実施形態において、ゾーンは、1GBのデータまたは制御情報と等価なものを格納する。クラスタは、ゾーンの中の単位サイズであり、圧縮以下に説明されるの単位を表す。以下に説明される例示的な実施形態において、クラスタは、4KBすなわち8つの512バイトセクタであり、本質的にチャンクと同じである。冗長セットは、データのセットに冗長性を提供するセクタ/クラスタのセットである。領域をバックアップすることは、一つの領域のコンテンツを別の領域にコピーすることを含む。格納デバイスの第1のペアおよび第2のペアは、共通格納デバイスを含み得る。第1の複数のおよび第2の複数の格納デバイスは、一つ以上の共通格納デバイスを含み得る。格納デバイスの第1の配置および第2の配置または異なる配置は、一つ以上の共通格納デバイスを含み得る。図1は、本発明の実施形態の図示であり、オブジェクト、この例においてはファイルが、格納のために一連のチャンクに分解される。最初に、ファイル11が格納ソフトウェアに渡され、そこでオブジェクト12として指定され、一意のオブジェクト識別番号、この場合は007が割当てられる。新しいエントリ131は、オブジェクトテーブル13の中に作られ、この新しいオブジェクトの割当てを表す。オブジェクトは、今度はデータ121、122および123のチャンクに分解され、それらはオブジェクトの固定長セグメントである。各チャンクは、ハッシングアルゴリズムを通過させられ、ハッシングアルゴリズムはチャンクについて一意のハッシュ数を返す。このアルゴリズムは、リトライされたチャンクが格納されたチャンクと同一であることを保証するために、検索されたチャンクと、もともとのハッシュと比較された結果とに、後で適用され得る。各チャンクのハッシュ数は、後で完全なオブジェクトがチャンクの収集によって検索され得るように、オブジェクト132のエントリ行においてオブジェクトテーブル13の中に格納される。図1においてさらに、チャンクハッシュは、今度はチャンクテーブル14の中の既存のエントリと比較される。既存のエントリ141と一致する任意のハッシュは、すでに格納されているので、行動はとられないすなわち、データは再び格納されず、オブジェクトの自動的圧縮につながる。新しいハッシュチャンクテーブル14の中に対応するエントリがないハッシュは、チャンクテーブル141の中に入力される。チャンクにおけるデータは、次に、故障許容格納のために最も効率的な方法で、利用可能な格納デバイス151、152および153の上に格納される。このアプローチは、チャンクデータが、たとえば、一つまたは2つのデバイスからなる格納システムの上にミラリングされた方法で、または3つ以上の格納デバイスを用いてシステムの上でパリティストライピングされた方法で格納されることにつながり得る。このデータは、物理的位置1511、1521および1531において格納デバイスの上に格納され、チャンクのすべての物理的部分が後で場所を突き止められ検索され得るように、これらの位置および位置の番号は、チャンクテーブルの列143および142に格納される。図2は、より多くの格納デバイスstorageの追加の結果として、チャンクのための故障許容格納のパターンがどのように動的に変化され得るかという同じ実施形態を示す。特に、図2は、追加の格納デバイスがシステム全体にひとたび追加されると、格納デバイスの上に物理的に格納されたチャンクが、新しいパターンにおいてどのようにレイアウトされ得るかを示す。図2aにおいて、格納システムは2つの格納デバイス221および222を備え、チャンクデータは、位置2211および2221において2つの格納デバイスの上に物理的にミラリングされ、故障許容を提供する。図2bにおいて、第3の格納デバイス223が追加され、チャンクをパリティストライピングした方法で格納することが可能になり、これは、ミラリングされたパターンよりも格納効率が良いパターンである。チャンクは、3つの物理的位置2311、2321および2331において、この新しいパターンにレイアウトされ、利用可能な格納デバイスにとる割合がはるかに低い。チャンクテーブル21はアップデートされて、新しいレイアウトが3つの位置212にすることと、新しいチャンクの物理的位置2311、2321および2331が213に記録されていることをも示す。図3は、本発明の実施形態による、完成されたmature格納システムを示し、ある期間にわたって機能していた。これは、可変格納容量を有する格納デバイスの上で、チャンクが、時間を経てどのように物理的に格納され得るかを図示する。この図は、40GB格納デバイス31と、80GB格納デバイス32と、120GB格納デバイス33とからなる格納システムを示す。最初に、チャンクは、40GB格納デバイス31が満杯になるまで、故障許容ストライプパターン34で格納される。次に、格納スペースの欠如のために、新しいデータは、80GB格納デバイス32および120GB格納デバイス33の上の利用可能なスペースの上に、ミラリングされたパターン36で格納される。80GB格納デバイス32がひとたび満杯になると、次に、新しいデータは単一のディスク故障許容パターン37でレイアウトされる。たとえ格納デバイスがデータ格納のための単一のプールを備えていても、チャンクにおいて格納されたようなデータそのものは、種々の別個のパターンで格納されている。図4は、本発明の別の実施形態を図示し、非効率的な格納デバイスの使用と、故障許容の低いレベルとを警告するために、インジケータ状態が使用される。図4aにおいて、すべての3つの格納デバイス41、42および45は使用されていないスペースを有しており、効率的で故障許容の方法でデータが格納されていることを示すために、インジケータライト44は緑色である。図4bにおいて、40GB格納デバイス41は満杯になったので、新しいデータは、ミラリングされた冗長パターン46で、使用されていない残りのスペースを用いて2つの格納デバイス42および43の上のみに格納され得る。データは完全に冗長ではあるが、効率的に格納されていないことを示すために、インジケータライト44は琥珀色に変わった。図4cにおいて、120GB格納デバイス43のみが使用されていない残りのスペースを有しているので、すべての新しいデータは、この一つのデバイス43の上でミラリングされたパターンのみで格納され得る。故障許容はよりロバストrobustでなくなり、システムはスペースが非常に足りなくなっているので、より多くの格納デバイスの追加が必要であることを示すために、インジケータライト44は赤色に変わる。一つの代替的な実施形態において、アレイにおけるそれぞれのドライブ/スロットに、たとえば3色たとえば緑色、黄色、赤色の形で、インジケータが提供される。一つの特定の実施形態において、ライトは、光る効果でディスクキャリアの前面全体を照らすように使用される。ライトは、システムの全体的な状態のみならず、もしあればどのドライブ/スロットが注意を必要としているかを示すように制御される。それぞれの3色ライトは、少なくとも4つの状態に置かれ得、具体的には、オフ、緑色、黄色、赤色である。スロットが空であり、システムが十分な格納デバイスと冗長性をもって作動しているために、スロットにドライブがインストールされる必要がない場合には、特定のスロットのためのライトは、オフ状態に置かれ得る。特定のスロットのためのライトは、対応するドライブが十分であり、置き換えられる必要がない場合には、緑色状態に置かれ得る。特定のスロットのためのライトは、対応するドライブをより大きなドライブに置き換えることが推奨されるようにシステム操作が低下する場合には、黄色の状態に置かれ得る。特定のスロットのためのライトは、対応するドライブをインストールまたは置き換えなければならない場合には、赤色の状態に置かれ得る。必要または要求に応じて、たとえば、オンとオフとの状態の間でライトをフラッシュさせることによって、または2つの異なる色の間でライトをフラッシュさせるたとえば、ドライブが置き換えられた後に、データの再レイアウトが進行中であるときに、赤色と緑色との間でフラッシュさせることによって、追加の状態が示され得る。例示的な実施形態のさらなる詳細が、以下に説明される。もちろん、システム状態とドライブ/スロット状態との両方を示すために、他の指示技術が使用され得る。たとえば、システム状態と、必要な場合には、注意を必要とするスロット番号とを示すために、LCDディスプレイが使用され得る。さらに、他の種類のインジケータたとえば、スロットインジケータまたは各スロット用のライトとともに、システムのための単一の状態インジケータたとえば緑色/黄色/赤色が使用され得る。図5は、図1~3に関連して上述されたような、本発明の実施形態に従ったデータの格納、検索および再レイアウトにおいて使用される機能モジュールのブロック図である。通信のための入口点および出口点は、オブジェクトの格納または検索のためにオブジェクトをシステムに渡すオブジェクトインタフェース511と、格納システムを一つの大きな格納デバイスであるように見せるブロックインタフェース512と、格納システムをWindows登録商標ファイルシステムであるように見せるCIFSインタフェース513とである。これらのインタフェースがデータの格納を要求するとき、データはチャンクパーサChunkParser52に渡され、チャンクパーサは、データのチャンクへの分解を実行し、オブジェクトテーブル512への最初のエントリを生成する図1に関連して上述されたように。これらのチャンクは、次にハッシュコード生成器53に渡され、ハッシュコード生成器は各チャンクについて関連するハッシュコードを生成し、それらをオブジェクトテーブルに入力するので、各オブジェクトに関連するチャンクは512で列挙される図1に関連して上述されたように。チャンクハッシュ数は、チャンクテーブル531におけるエントリと比較される。一致が見出された場合には、新しいチャンクは、格納システムにすでに格納されたチャンクと同一であるので、捨てられる。チャンクが新しい場合には、そのための新しいエントリがチャンクテーブル531の中に作成され、ハッシュされたチャンクは物理的格納マネジャー54に渡される。物理的格納マネジャーは、利用可能な格納デバイス571、572および573の上で可能な最も効率的なパターンでチャンクを格納して、チャンクのコンテンツが後で512で検索され得るように図1に関連して上述されたように、チャンクの物理的格納がどこで発生したかを示すために、チャンクテーブル531の中に対応するエントリを作成する。オブジェクトインタフェース511、ブロックインタフェース512、またはCIFSインタフェース513による、図5におけるデータの検索は、検索マネジャー56に対するリクエストによって実行され、検索マネジャーは、どのチャンクがオブジェクトを含むかを決定するためにオブジェクトテーブル521を調べ、次にこれらのチャンクを物理的格納マネジャー54から要求する。物理的格納マネジャー54は、要求されたチャンクがどこに格納されているかを決定するためにチャンクテーブル531を調べ、次にそれらを検索し、完了したデータオブジェクトを検索マネジャー56に返し、検索マネジャーは、要求しているインタフェースにデータを返す。図5には、故障許容マネジャーFTL55も含まれ、チャンクが可能な最も効率的な方法で格納されているかどうかを決定するために、絶えずチャンクテーブルをスキャンする。格納デバイス571、572および573が追加されたり取り外されたりすると、これらは変化し得る。チャンクが可能な最も効率的な方法で格納されていない場合には、FTLは、物理的格納マネジャー54に、チャンクについて新しいレイアウトパターンを作成し、チャンクテーブル531をアップデートするように、要求する。このようにして、すべてのデータは、アレイを含む格納デバイスの数について可能な最も効率的な方法で格納されたままでいる図2および3に関連して上述されたように。以下は、本発明の例示的な実施形態のさらなる詳細を提供する。データレイアウトスキーム-ゾーンなかでも、ゾーンは、ディスクの上に格納されている実際のデータから、冗長性とディスク再レイアウトとを隠す効果を有する。ゾーンは、ゾーンのユーザに影響することなく、追加のレイアウト方法が追加および変更されることを可能にする。格納アレイは、ゾーンと呼ばれる仮想セクションにおけるディスクの上で、データをレイアウトする。ゾーンは、所定および固定の量たとえば1Gバイトのデータを格納する。ゾーンは、単一のディスクの上に存在し得るか、あるいは一つ以上のドライブにわたってまたがり得る。ゾーンの物理的レイアウトは、そのゾーンについて指定された形で冗長性を提供する。図6は、2つ以上のドライブを含むアレイにおいてミラリングが使用される例を示す。図7は、データを格納するために異なるレイアウトスキームを使用するいくつかの例示的なゾーンを示す。図は、ゾーンが1GBのデータを格納することを想定する。以下の点に留意されたい。i複数のドライブにまたがるゾーンは、セットにわたるドライブの中に同じオフセットを必ずしも使用しない。ii単一ドライブミラリングは、1Gのデータを格納するために2Gの格納デバイスを必要とする。iii二重ドライブミラリングは、1Gのデータを格納するために2Gの格納デバイスを必要とする。iv3つのドライブストライピングは、1Gのデータを格納するために1.5Gの格納デバイスを必要とする。v4つのドライブストライピングは、1Gのデータを格納するために1.33Gの格納デバイスを必要とする。viゾーンA、ゾーンBなどは、任意のゾーン名である。実際のインプリメンテーションにおいて、それぞれのゾーンは一意の数によって識別され得る。vii図によって暗示されるものの、ゾーンは必ずしもディスクの上で隣接しない後で領域を参照。viiiミラリングが2つのドライブに制約される技術的理由はない。たとえば、3ドライブシステムにおいて、データの一つのコピーが一つのドライブの上に格納され得、ミラリングされたデータの半分が他の2つのドライブのそれぞれの上に格納され得る。同様に、データは3つのドライブにわたってミラリングされ得、データの半分が2つのドライブのそれぞれの上にミラリングされ、ミラリングの半分が他の2つのドライブの上にミラリングされる。データレイアウトスキーム-領域各ディスクは、均等なサイズの領域に分割される。領域のサイズはゾーンよりもはるかに小さく、ゾーンは一つ以上のディスクからの一つ以上の領域から構築される。ディスクスペースの効率的な使用のために、領域のサイズは一般的に、異なるゾーンサイズと、アレイによってサポートされる異なる数のディスクとの共通因子である。例示的な実施形態において、領域はゾーンの1/12のデータサイズである。以下の表は、本発明の例示的な実施形態に従って、種々のレイアウトについての、領域/ゾーンの数と、領域/ディスクの数とを列挙する。個々の領域は、使用済み、使用されていない、または不良としてマークされ得る。ゾーンが作成されるときには、適切なディスクから使用されていない領域のセットが、テーブルにおいて選択されログをとられる。これらの領域は、任意の順序であり得、ディスクの上で隣接する必要はない。データがゾーンに書き込まれるかまたはゾーンから読み取られるときには、アクセスは適切な領域にリダイレクトされる。なかでも、このことは、データの再レイアウトが柔軟かつ効率的な方法で生ずることを可能にする。時間を経て、異なるサイズのゾーンは、おそらく断片化を発生させ、小さすぎて完全なゾーンを保持できない多くのディスクエリアを残す。適切な領域サイズを使用することによって、断片化によって残されたすべてのギャップは、サイズにおいて少なくとも一つの領域になり、ディスク全体を断片化解消de-fragmentする必要なしに、これらの小さなギャップの容易な再使用を可能にする。データレイアウトスキーム-再レイアウトインプリメンテーションを容易にするために、固定シーケンスの拡張および縮小が強化され得る。たとえば、2つのドライブが急に追加される場合には、第2のドライブを組み込むために第2の拡張が実行される前に、あたかも一つのドライブが追加されたかのように、ゾーンの拡張が中間の拡張を経由し得る。代替的には、複数のドライブを含む拡張および縮小は、中間のステップなしに、アトミックにatomically処理され得る。任意の再レイアウトが生じる前に、必要とされるスペースが利用可能でなければならない。このことは、不必要な再レイアウトが生じないことを確実にするために、再レイアウトを始める前に計算されるべきである。レイアウトスキーム-ドライブ拡張以下は、本発明の例示的な実施形態に従って、単一ドライブミラリングから二重ドライブミラリングに拡張する一般的なプロセスを説明する。i単一ドライブミラリングが、データAとミラリングBとを有すると想定する。iiゾーンをCへと拡張するために、ドライブの上に12の領域を割当てる。iiiミラリングBを領域セットCにコピーする。ivすでにコピーされたデータへのいかなる書き込みも、Cにおける適切な場所にミラリングされなければならない。vコピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、BへのポインタをCへのポインタに置き換える。viBを構成する領域を、使用されていないとしてマークする。以下は、本発明の例示的な実施形態に従って二重ドライブミラリングからパリティを用いた三重ドライブストライピングへと拡張する、一般的なプロセスを説明する。i一つのドライブがデータAを有し、第2のドライブがミラリングBを有すると想定する。iiパリティ情報Cのために、第3のドライブの上に6つの領域を割当てる。iiiAの第1の6領域と、Bの第2の6領域とを使用して、パリティ情報を計算する。ivCにパリティ情報を置く。vすでに処理されたデータになされたいかなる書き込みも、Cにおける適切な場所にパリティされなければならない。viコピーが完了したら、新しいレイアウトタイプのポイントテーブルを用いて、ゾーンテーブルを、Aの第1の半分と、Bの第2の半分と、Cとにアップデートする。viiAの第2の半分とBの第1の半分とを、使用されていないとしてマークする。以下は、本発明の例示的な実施形態に従って三重ドライブストライピングからパリティを用いた四重ドライブストライピングに拡張する、一般的なプロセスを説明する。i一つのドライブがデータAを有し、第2のドライブがデータBを有し、第3のドライブがパリティPを有すると想定する。iiストライピングデータCのために、第4のドライブの上に4つの領域を割当てる。iiiAの最後の2領域を、Cの最初の2領域にコピーする。ivBの最初の2領域を、Cの最後の2領域にコピーする。vパリティドライブDの上に4つの領域を割当てる。viAの最初の4領域と、Cと、Bの最後の4領域とを使用して、パリティ情報を計算する。viiパリティ情報をDに置く。viiiすでに処理されたデータへのいかなる書き込みも、Dにおける適切な場所にパリティされなければならない。ix新しいレイアウトタイプとポイントテーブルとを用いて、ゾーンテーブルを、Aの第1の4領域と、Cと、Bの第2の4領域と、Dとにアップデートする。xAの最後の2領域と、Bの最初の2領域を、使用されていないとしてマークする。データレイアウトスキーム-ドライブ縮小ドライブ縮小は、ディスクが取り外されるかまたは故障するときに発生する。そのような場合には、アレイは、可能であればすべてのゾーンを冗長状態に戻すために、データを縮小する。ドライブ縮小は、拡張よりもやや複雑である。なぜなら、より多くの選択がなされるべきだからである。しかし、レイアウト方法の間の移行は、拡張と同様の方法で生じるが、逆の順序である。再生されるべきデータの量を最小限に保つことは、冗長性が可能な限り迅速に達成されることを可能にする。ドライブ縮小は、すべてのゾーンが再レイアウトされるまで、スペースが利用可能である間に、一般的に一度に1ゾーン先行する。一般的に言って、取り外されたかまたは故障したディスクの上に存在するデータのみが再構築される。どのように縮小するかの選択以下の表は、本発明の例示的な実施形態に従って、再レイアウトされる必要のある各ゾーンについての決定ツリーを説明する:以下は、本発明の例示的な実施形態に従って、二重ドライブミラリングから単一ドライブミラリングに縮小する一般的なプロセスを説明する。i単一ドライブミラリングが、データAと欠いているミラリングBとを有するか、またはその逆であると仮定する。iiAをCとして含むドライブの上に12の領域を割当てる。iiiデータAを領域セットCにコピーする。ivすでにコピーされたデータへのいかなる書き込みも、Cにおける適切な場所にミラリングされなければならない。vコピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、BへのポインタをCへのポインタに置き換える。以下は、本発明の例示的な実施形態に従って、三重ドライブストライピングから二重ドライブミラリングに縮小する一般的なプロセスを説明するパリティを欠いている。iストライピングは、異なるドライブの上のデータブロックA、BおよびCからなると想定する。パリティCが欠けている。iiAをゾーンの第1の半分を含むものとして定義し、Bをゾーンの第2の半分を含むものとして定義する。iiiAドライブの上に6つの領域Dを割当て、Bドライブの上に6つの領域Eを割当てる。ivAをEにコピーする。vBをDにコピーする。すでにコピーされたデータへのいかなる書き込みも、DおよびEにおける適切な場所にミラリングされなければならない。viiコピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、A/DおよびE/Bへのポインタを設定する。以下は、本発明の例示的な実施形態に従って、三重ドライブストライピングから二重ドライブミラリングに縮小する一般的なプロセスを説明するデータを欠いている。iストライピングは、異なるドライブの上のデータブロックA、BおよびCからなると想定する。データCが欠けている。iiAをゾーンの第1の半分を含むものとして定義し、Cをゾーンの第2の半分を含むものとして定義する。iiiAドライブの上に6つの領域Dを割当て、Bドライブの上に12の領域Eを割当てる。ivAをEの第1の半分にコピーする。vAおよびBから、欠けているデータを再構築する。データをDに書き込む。viDをEの第2の半分にコピーする。viiすでにコピーされたデータへのいかなる書き込みも、DおよびEにおける適切な場所にミラリングされなければならない。viiiコピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、A/DおよびEへのポインタを設定する。ixB領域を、使用されていないとしてマークする。以下は、本発明の例示的な実施形態に従って、四重ドライブストライピングから三重ドライブストライピングに縮小する一般的なプロセスを説明するパリティを欠いている。iストライピングは、異なるドライブの上のデータブロックA、B、CおよびDからなると仮定する。パリティDが欠けている。iiAをゾーンの第1の3分の1を含むものとして定義し、Bを第2の3分の1を含むものとして定義し、Cを第3の3分の1を含むものとして定義する。iiiAドライブの上に2領域Gを割当て、Cドライブの上に2領域Eを割当て、Bドライブの上に6領域Fを割当てる。ivBの第1の半分をGにコピーする。vBの第2の半分をEにコピーする。viA/GおよびE/Cからパリティを構築し、Fに書き込む。viiすでにコピーされたデータへのいかなる書き込みも、G、EおよびFにおける適切な場所にミラリングされなければならない。viiiコピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、A/G、E/C、およびFへのポインタを設定する。ixB領域を、使用されていないとしてマークする。以下は、本発明の例示的な実施形態に従って、四重のドライブストライピングから三重のドライブストライピングに縮小する一般的なプロセスを説明する最初の1/3を欠いている。iストライピングは、異なるドライブの上のデータブロックA、B、CおよびDからなると想定する。データAが欠けている。iiAをゾーンの第1の3分の1を含むものとして定義し、Bを第2の3分の1を含むものとして定義し、Cを第3の3分の1を含むものとして定義し、Dをパリティを含むものとして定義する。iiiBドライブの上に4領域Eを割当て、Cドライブの上に2領域Fを割当て、Dドライブの上に6領域Gを割当てる。ivBの第2の半分をFにコピーする。vB、CおよびDから、欠けているデータを構築し、Eに書き込む。viE/Bの第1の半分と、F/Cとから新しいパリティを構築し、Gに書き込む。viiすでにコピーされたデータへのいかなる書き込みも、B、E、FおよびGにおける適切な場所にミラリングされなければならない。viiiコピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、E/Bの第1の半分、F/C、およびGへのポインタを設定する。ixBの第2の半分およびDの領域を、使用されていないとしてマークする。以下は、本発明の例示的な実施形態に従って、四重のドライブストライピングから三重のドライブストライピングに縮小する一般的なプロセスを説明する第2の1/3を欠いている。iストライピングは、異なるドライブの上のデータブロックA、B、CおよびDからなると想定する。データBが欠けている。iiAをゾーンの第1の3分の1を含むものとして定義し、Bを第2の3分の1を含むものとして定義し、Cを第3の3分の1を含むものとして定義し、Dをパリティを含むものとして定義する。iiiAドライブの上に2領域Eを割当て、Cドライブの上に2領域Fを割当て、Dドライブの上に6領域Gを割当てる。ivAの第1の半分、Cの第1の半分、およびDの第1の半分から、欠けているデータを構築し、Eに書き込む。vAの第2の半分、Cの第2の半分、およびDの第2の半分から、欠けているデータを構築し、Fに書き込む。viA/EおよびF/Cから新しいパリティを構築し、Gに書き込む。viiすでにコピーされたデータへのいかなる書き込みも、E、FおよびGにおける適切な場所にミラリングされなければならない。viiiコピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、E、FおよびGへのポインタを設定する。ixD領域を、使用されていないとしてマークする。以下は、本発明の例示的な実施形態に従って、四重のドライブストライピングから三重のドライブストライピングへの縮小の一般的なプロセスを説明する第3の1/3を欠いている。iストライピングは、異なるドライブの上のデータブロックA、B、CおよびDからなると想定する。データCが欠けている。iiAをゾーンの第1の3分の1を含むものとして定義し、Bを第2の3分の1を含むものとして定義し、Cを第3の3分の1を含むものとして定義し、Dをパリティを含むものとして定義する。iiiAドライブの上に2領域Eを割当て、Bドライブの上に4領域Fを割当て、Dドライブの上に6領域Gを割当てる。ivBの第1の半分をEにコピーする。vA、BおよびDから、欠けているデータを構築し、Fに書き込む。viA/Eと、B/Fの第2の半分とから新しいパリティを構築し、Gに書き込む。viiすでにコピーされたデータへのいかなる書き込みも、E、FおよびGにおける適切な場所にミラリングされなければならない。viiiコピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、A/E、B/Fの第2の半分、およびGへのポインタを設定する。ixBの第1の半分およびDを、使用されていないとしてマークする。たとえば、図3を再び参照して、ドライブ0またはドライブ1のいずれかが失われた場合には、ドライブ2の上に十分な利用可能なスペースがあるという条件で、二重ドライブミラリングゾーンBはドライブ2の上で再構築され得る。同様に、ドライブ0~2のいずれかが失われた場合には、ドライブ3の上に十分な利用可能なスペースがあるという条件で、ドライブストライピングゾーンCは、ドライブ3を利用して再構築され得る。データレイアウトスキーム-ゾーン再構築ゾーン再構築は、ドライブが取り外されて、理想的なゾーン再レイアウトのために残りのドライブの上に十分なスペースがあるとき、あるいはドライブがより大きなサイズの新しいドライブと置き換えられたときに、生じる。以下は、本発明の例示的な実施形態に従って、二重ドライブミラリングの再構築の一般的なプロセスを説明する。i単一ドライブミラリングが、データAと欠けているミラリングBとを有すると想定する。iiAを含むドライブ以外のドライブの上に12の領域Cを割当てる。iiiデータAをCにコピーする。ivすでにコピーされたデータへのいかなる書き込みも、Cにおける適切な場所にミラリングされなければならない。vコピーが完了したら、ゾーンテーブルをアップデートし、BへのポインタをCへのポインタにアップデートする。以下は、本発明の例示的な実施形態に従って、三重ドライブストライピングの再構築の一般的なプロセスを説明する。i一つのドライブがデータAを有し、第2のドライブがデータBを有し、第3のドライブがパリティPを有すると想定する。Bが欠けている。どの断片が欠けているかは問題ではなく、必要とされる行動はすべての場合において同じであることに留意されたい。iiAおよびPを含むドライブ以外のドライブの上に、6つの領域Dを割当てる。iiiAおよびPから、欠けているデータを構築する。データをDに書き込む。ivすでに処理されたデータへのいかなる書き込みも、Dにおける適切な場所にパリティされなければならない。vBへのポインタをDへのポインタに置き換えることによって、ゾーンテーブルをアップデートする。この例示的な実施形態において、取り外されたドライブが別のドライブと置き換えられる場合に、4ドライブ再構築のみが生じる。再構築は、新しいドライブの上に6つの領域を割当てることと、他の3つの領域セットから、欠けているデータを再構築することとからなる。データレイアウトスキーム-一時的に欠けるドライブの問題ドライブが取り外されて、再レイアウトのための余地がないときには、古いドライブが再び取り付けられるか、またはドライブが新しいドライブと置き換えられるまで、アレイは劣化したモードで作動し続ける。新しいドライブが取り付けられる場合には、ドライブセットが再構築されるべきである。この場合には、データが再レイアウトされる。古いディスクがアレイの中に戻して置かれる場合には、それはもはや現在のディスクセットの一部ではなく、新しいディスクとしてみなされる。しかし、新しいディスクがアレイに置かれるのではなく、古いディスクが戻される場合には、古いディスクは、たとえ古いメンバであろうとも、やはりディスクセットのメンバであるとして認識される。この場合には、すでに再レイアウトされた任意のゾーンが新しい構成を保ち、古いディスクの上の領域は解放される。再レイアウトされていない任意のゾーンは、やはり古いディスクの適切な領域をポインティングする。しかし、劣化したゾーンに何らかの書き込みが実行され得た場合には、これらのゾーンはリフレッシュされる必要がある。生じたすべての書き込みのログをとるのではなく、変更された劣化領域はマークされ得る。このようにして、ディスクが置き換えられるときには、変更された領域のみがリフレッシュされる必要がある。さらに、書き込まれたゾーンは、再レイアウトのための優先リストにさらに置かれ得る。このことは、ディスクが置き換えられた場合に、リフレッシュされる必要がある領域の数を低減し得る。タイムアウトも使用され得、その時点の後で、ディスクはたとえ置き換えられても消去されるwiped。しかし、このタイムアウトは非常に大きくあり得、場合によると数分ではなく数時間である。データレイアウトスキーム-データ保全性上述のように、標準的なRAIDシステムの一つの問題は、ディスクアレイのまれにしか使用されないエリアの上で、ディスク表面の破損が生じる可能性があることである。別のドライブが故障する場合には、破損が生じたことを決定することは必ずしも可能ではない。そのような場合には、RAIDアレイが故障したドライブを再構築するときに、破損したデータが伝播され保存され得る。上述のハッシュメカニズムは、RAIDのもとで利用可能なメカニズムにわたってデータ破損検出の追加のメカニズムを提供する。他の場合に述べられるように、チャンクが格納されるときに、そのチャンクについて、ハッシュ値が計算され格納される。チャンクが読み出されるときはいつでも、検索されたチャンクについてのハッシュ値が計算され得、格納されたハッシュ値と比較され得る。ハッシュ値が一致しない場合には破損したチャンクを示し、チャンクデータは冗長データから回復され得る。ディスクの上のデータ破損が生じ得る時間窓timewindowを最小化するために、破損したデータを可能な限り速やかに発見し修正するように、ディスクの定期的なスキャンが実行される。それは、オプションとして、アレイからの読み出しにおいてチェックが実行されることをも可能にする。データレイアウトスキーム-ボリュームスパースボリュームsparsevolumeにおいて、アレイにおけるディスクの上で利用可能な格納スペースの量に関わりなく、アレイは固定サイズたとえばMテラバイトであることをつねに求める。アレイはSバイトの実際の格納スペースを含み、ここでS<=Mであり、データは、Mテラバイトのスペースの中の位置L1、L2、L3などに格納されるように要求され得ると仮定する。要求された位置Ln>Sである場合には、Lnのためのデータは、位置Pn<Sに格納されなければならない。このことは、図8に示されるように、Lnに基づいてインデックスPnに対するルックアップテーブルを含むことによって管理される。この特徴は、Windows登録商標、Linux登録商標およびApple登録商標のオペレーティングシステムなどの、ボリューム拡張をサポートしないオペレーティングシステムとともに、アレイが作動することを可能にする。さらに、アレイは、複数のスパースボリュームを提供し得、そのすべては同一の物理格納を共有する。それぞれのスパースボリュームは、専用のルックアップテーブルを有するが、データ格納のために同一の物理スペースを共有する。ドライブスロットインジケータ上述のように、格納アレイは一つ以上のドライブスロットからなる。それぞれのドライブスロットは、空であり得るか、またはハードディスクドライブを含み得る。それぞれのドライブスロットは、4つの状態を示す能力のある専用インジケータを有する。すなわち、オフ、OK、劣化、および故障である。状態は、一般的に以下のように解釈される:この例示的な実施形態において、赤色/琥珀色/緑色の発光ダイオードLEDがインジケータとして使用される。LEDは、一般的に以下のように解釈される:図9は、本発明の例示的な実施形態に従った、利用可能な格納スペースを有し、故障許容方法において作動する、例示的なアレイを示す。スロットB、CおよびDには、格納デバイスが配置され、追加のデータを冗長に格納するために利用可能な十分な格納スペースがある。スロットB、CおよびDのインジケータは緑色でありこれらの格納デバイスが正しく作動しており、アレイデータが冗長であり、アレイが利用可能なディスクスペースを有することを示す、スロットAのインジケータはオフである格納デバイスをスロットAに配置する必要がないことを示す。図10は、本発明の例示的な実施形態に従った、冗長データ格納を維持するために十分なスペースを有せず、より多くのスペースが追加されなければならない、例示的なアレイを示す。スロットB、CおよびDには、格納デバイスが配置される。スロットCおよびDにおける格納デバイスは満杯である。スロットB、CおよびDのインジケータは緑色でありこれらの格納デバイスが正しく作動していることを示す、スロットAのインジケータは赤色であるアレイが、冗長データ格納を維持するための十分なスペースを有せず、スロットAに格納デバイスが配置されるべきであることを示す。図11は、本発明の例示的な実施形態に従った、故障の場合に冗長データを維持することができなくあり得る、例示的なアレイを示す。スロットA、B、CおよびDには、格納デバイスが配置される。スロットCおよびDにおける格納デバイスは満杯である。スロットA、BおよびCのインジケータは緑色でありアレイが正しく作動していることを示す、スロットDのインジケータは琥珀色であるスロットDにおける格納デバイスが、より大きな格納容量を有する格納デバイスに置き換えられるべきであることを示す。図12は、本発明の例示的な実施形態に従った、格納デバイスが故障した例示的なアレイを示す。スロットB、CおよびDには、格納デバイスが配置される。スロットCにおける格納デバイスが故障した。スロットBおよびDのインジケータは緑色でありこれらが正しく作動していることを示す、スロットCのインジケータは赤色でありスロットCにおける格納デバイスが置き換えられるべきであることを示す、スロットAのインジケータはオフである格納デバイスがスロットAに配置される必要がないことを示す。以下は、本発明の例示的な実施形態のためのソフトウェア設計の説明である。ソフトウェア設計は、6つのソフトウェアレイヤに基づき、ソフトウェアレイヤは、ディスクに物理的にアクセスすることから、ホストコンピューティングシステムと通信することまでの、論理アーキテクチャにわたる。この例示的な実施形態において、ファイルシステムは、Windows登録商標、Linux登録商標またはApple登録商標などのホストサーバに常駐し、USBデバイスまたはiSCSIデバイスとして格納アレイにアクセスする。ホストインタフェースを介して到着する物理的ディスクリクエストは、ホストリクエストマネジャーHostRequestManagerHRMによって処理される。ホストI/Oインタフェースは、ホストに対するホストUSBまたはiSCSIインタフェースのプレゼンテーションを調整しcoordinate、HRMとインタフェースする。HRMは、ホストI/Oインタフェースからのデータ読み出し/書き込みリクエストを調整し、読み出しおよび書き込みリクエストをタスク指名し、これらのリクエストが完了したときに、これらのリクエストのホストへの回収retiringを調整する。格納アレイの何よりも重要な目的は、ひとたびデータがシステムによって受け入れられると、システムが現在格納する冗長性の最大量を利用して、データが確実な方法で格納されることを保証することである。アレイが物理的構成を変化させると、データは冗長性を維持するさらに場合によると最大化するために再編成される。さらに、使用される格納量を低減するために、単純なハッシュに基づいた圧縮が使用される。最も基本的なレイヤは、データを異なるディスクに格納するディスクドライバからなる。ディスクは、USBインタフェースを介して通り抜けたtunneledATAなどの種々のインタフェースを介して接続され得る。ディスクの上のセクタは、領域、ゾーン、およびクラスタに編成され、それぞれが異なる論理的役割を有する。領域は、ディスクの上の隣接する物理ブロックのセットを表す。4ドライブシステムにおいて、それぞれの領域は、サイズが1/12GBであり、冗長性の最小単位を表す。領域の中のセクタが物理的に損傷していることがわかった場合は、領域全体が放棄される。ゾーンは、冗長性の単位を表す。ゾーンは、適切な量の冗長性を提供するために、場合により異なるディスクの上の、多数の領域からなる。ゾーンは、1GBのデータ容量を提供するが、冗長性を提供するためにより多くの領域を要求し得る。冗長性のない1GBは、1セットの12領域1GBを要求する;1GBのミラリングされたゾーンは、2セットの1GB領域24領域を要求する;1GBの3ディスクストライピングされたゾーンは、3セットの0.5GB領域18領域を要求する。異なるゾーンは、異なる冗長特性を有する。クラスタは、圧縮の基本単位を表し、ゾーンの中の単位サイズである。クラスタのサイズは現在4KB、すなわち8×512バイトセクタである。ディスクの上の多くのクラスタは、おそらく同じデータを含む。クラスタアクセステーブルCATは、ハッシュ関数を介してクラスタの利用を追跡するために使用される。CATは、論理ホストアドレスと、ゾーンにおける適切なクラスタの位置との間の変換をする。ディスクに書き込むときに、データがディスクの上にすでに存在するかどうかを知るためにハッシュ関数が使用される。そうである場合には、CATテーブルにおける適切なエントリが、既存のクラスタを示すように設定される。CATテーブルは、自らのゾーンの中に常駐する。CATテーブルがゾーンのサイズを超える場合には、追加のゾーンが使用され、CATのその部分のゾーンに論理アドレスをマッピングするために、テーブルが使用される。代替的には、ゾーンはCATテーブルを含むように事前に割当てられる。ホスト書き込み待ち時間を低減し、データ信頼性を保証するために、ジャーナルマネジャーが、ディスクまたはNVRAMのいずれかに対するすべての書き込みリクエストを記録する。システムが再起動される場合には、ジャーナルエントリは再起動に際してコミットされる。ディスクは出入りし得、領域は、破損を有することがわかった場合には、使わなくretireされ得る。これらの状況のいずれにおいても、レイアウトマネジャーは、冗長タイプを変更するために、またはゾーンの領域的な構成を変化させるために領域が破損した場合に、ゾーンの中の領域を再編成することが可能である。格納アレイは、物理的ディスクスペースの変化するレベルによって支援されて、仮想ディスクアレイを提供し、それはブロックレベルのインタフェースを提供するので、いつクラスタがファイルシステムによってもはや使われなくなるかは、明らかではない。結果として、使用されるクラスタスペースは、拡張し続ける。ガーベッジコレクタホストまたはファームウェアのいずれかに位置するは、どのクラスタが解放されたかを決定するためにファイルシステムを分析し、それらをハッシュテーブルから取り除く。以下の表は、本発明の例示的な実施形態に従った6つのソフトウェアレイヤを示す:図13は、異なるソフトウェアレイヤと、それらが互いにどのように関連するかを表す、モジュール階層を示す。ソフトウェアレイヤリングは、明瞭なAPIおよび記述を提供するために、好ましくはリジッドである。ガーベッジコレクタGarbageCollectorは、ホストファイルシステムによってもはや使われないクラスタを解放する。たとえば、ファイルが削除されるときに、そのファイルを含むために使用されたクラスタは、好ましくは解放される。ジャーナルマネジャーJournalManagerは、書き込みの実行記録journalingの形を提供するので、電源異常または他のエラー状態の場合において、保留中の書き込みは失われない。レイアウトマネジャーLayoutManagerは、ゾーンの領域に対するゾーンのランタイム再レイアウトを提供する。このことは、ディスクの挿入/取り外しまたは故障の結果として生じ得る。クラスタマネジャーClusterManagerは、データゾーンのセットの中にクラスタを割当てる。ディスク利用デーモンDiskUtilizationDaemonは、使用されていないディスクスペースを定期的にチェックする。ロックテーブルLockTableは、書き込み衝突発行collisionissuesの後で、読み出しを処理する。ホストリクエストマネジャーHostRequestManagerは、ホストおよびガーベッジコレクタからの読み出し/書き込みリクエストを処理する。書き込みはジャーナルマネジャーに渡されるが、読み出しはクラスタアクセステーブルCAT管理レイヤを介して処理される。上述のように、代表的なファイルシステムにおいて、ある量のデータが一般的に事実上反復される。ディスクスペース利用を低減させるために、このデータの複数のコピーはディスクに書き込まれない。代わりに、一つのインスタンスが書き込まれ、同じデータのすべての他のインスタンスが、この一つのインスタンスに対して参照される。この例示的な実施形態において、システムはつねにデータのクラスタの上で作動したとえば8つの物理的セクタ、これはハッシュされる単位である。SHA1アルゴリズムは、160ビットハッシュを生成するために使用される。このことは、良好な独特さuniquenessを含む多数の利益を有し、多数のプロセッサにおいてオンチップでサポートされる。すべての160ビットがハッシュ記録に格納されるが、最下位の16ビットのみがハッシュテーブルへのインデックスとして使用される。最も低い16ビットと一致する他のインスタンスは、リンクされたリストを介して連鎖される。この例示的な実施形態において、一度に一つの読み出し/書き込み操作のみが生じ得る。性能の目的のために、クラスタをディスクに書き込むときにハッシュ分析が生じることは許されない。代わりに、ハッシュ分析は、ハッシュマネジャーによるバックグラウンド活動として生じる。書き込みリクエストは、ジャーナルの書き込みキューから読み込まれ、完了に向けて処理される。データの一貫性を保証するために、書き込み操作がクラスタの上ですでに活動状態である場合には、書き込みは遅らせなければならない。他のクラスタの上の操作は、妨げられずに進行し得る。クラスタ全体が書き込まれない限りは、書き込まれるデータは、クラスタに格納された既存のデータと併合される必要がある。論理セクタアドレスLSAに基づいて、クラスタのCATエントリが位置づけられる。ハッシュキー、ゾーン、およびクラスタオフセット情報は、この記録から獲得され、次に、ハッシュテーブルを検索して一致を見出すために使用され得る。これがクラスタである。正しいハッシュエントリのルックアップの速度を改善するために、一度はSHA1ダイジェストを介して、次にゾーン/クラスタオフセットによって、ハッシュテーブルを二重にハッシュすることは十分に必要であり得る。ハッシュ記録がすでに使用されている場合には、参照カウントが減少させられる。参照カウントが現在ゼロであり、かつハッシュエントリによって参照されるスナップショットがない場合には、ハッシュエントリおよびクラスタは、それぞれのフリーリストに解放し返され得る。もともとのクラスタデータは、これでクラスタのアップデートセクションと併合させられ、データは再ハッシュされる。新しいクラスタはフリーリストから除去され、併合されたデータはクラスタに書き込まれ、新しいエントリはハッシュテーブルに追加され、CATテーブルにおけるエントリは新しいクラスタを指し示すようにアップデートされる。ハッシュテーブルをアップデートする結果として、エントリも内部キューに追加されて、バックグラウンドタスクによって処理される。このタスクは、新たに追加されたクラスタおよびハッシュエントリと、ハッシュテーブル行アドレスに一致する他のハッシュエントリとを比較し、これらが重複している場合には記録を結合し、必要に応じてハッシュエントリおよびCATテーブルエントリを解放する。これは、この活動によって書き込み待ち時間に負荷がかけられないことを保証する。この処理の間に故障たとえば電力の損失が生じる場合には、種々のテーブルが削除され得、結果としてデータの損失になる。テーブルは、最終コミットがアトミックであるか、あるいはジャーナルエントリが完全に完了しなかった場合には再実行され得るような方法で、管理されるべきである。以下は、書き込み論理の疑似コードである。読み出しリクエストもまた、一度に一つのクラスタセクタではなくで処理される。読み出しリクエストは、上記に概説されたハッシュ関連の処理を経ない。代わりに、ホスト論理セクタアドレスが、CATを参照するために使用され、ゾーン番号とゾーンの中へのクラスタオフセットとを獲得する。読み出しリクエストは、CATキャッシュにおけるCATテーブルエントリをルックアップすべきであり、書き込み進行中のビットが設定されることにおいて遅延されなければならない。他の読み出し/書き込みは、妨げられずに進行し得る。データ保全性のチェックを改善するために、クラスタは、読み出されるときにハッシュされ、そのハッシュは、ハッシュ記録に格納されたSHA1ハッシュ値と比較される。このことは、ハッシュテーブルの中への検索キーとして、ハッシュ、ゾーン、およびクラスタを使用することを必要とする。クラスタは、可能な限り少ないゾーンを使用するように割当てられる。なぜなら、ゾーンは、ディスクドライブの使用に直接的に対応するからである。すべてのゾーンについて、ハードドライブアレイの上に2つ以上の領域がある。ゾーンの数を最小化することによって、物理的領域の数が最小化され、したがってハードドライブアレイの上のスペースの消費が低減される。クラスタマネジャーは、データゾーンのセットからクラスタを割当てる。ゾーンにおける使用されていないクラスタを把握するために、リンクされたリストが使用される。しかし、使用されていないクラスタの情報は、ディスクの上にビットマップゾーンあたり32KBとして格納される。リンクされたリストは、ビットマップから動的に構築される。最初に、使用されていないクラスタの一定の数のリンクされたリストが、メモリの中で作成される。クラスタが割当てられると、リストは縮小する。所定の最低点において、使用されていないクラスタを表す新しいリンクされたリストのノードは、ディスクの上のビットマップから抽出される。このようにして、ビットマップは、割当て用に使用されていないクラスタを見出すために分析される必要はない。この例示的な実施形態において、ハッシュテーブルは64Kの記録ハッシュのより下位の16ビットによって索引をつけられるであり、以下のフォーマットを有する:オールゼロallzeroのクラスタは、かなり一般的であり得るので、たとえば決して削除され得ないように、オールゼロの場合は特別な場合として扱われ得るしたがってカウントをラッピングwrappingすることは問題ではあり得ない。複数のハッシュが同一の最下位ハッシュを有するとき、あるいは2つのハッシュエントリが異なるデータクラスタを指し示すときには、使用されていないハッシュ記録のリンクされたリストが使用される。いずれの場合においても、使用されていないハッシュ記録は、リストから取られ、pNextHashポインタを介してリンクされる。ハッシュマネジャーは、ハッシュテーブルに追加されたエントリを整頓し、ディスクの上の同一のクラスタを結合する。新しいハッシュ記録がハッシュテーブルに追加されると、メッセージがハッシュマネジャーに通知される。これは、ハッシュマネジャーによって自動的に行われる。バックグラウンド活動として、ハッシュマネジャーはキューの上のエントリを処理する。ハッシュマネジャーは、完全なfullハッシュ値が既存のハッシュ記録と一致するかどうかを知るために、完全なハッシュ値を比較する。そうする場合には、ハッシュマネジャーは、完成したcompleteクラスタデータも比較する。クラスタが一致する場合には、新しいハッシュ記録は使用されていないキューに捨て戻され得、ハッシュ記録カウントは増加させられ、重複するクラスタはクラスタの使用されていないキューに戻される。ハッシュマネジャーは、記録を結合するときに、スナップショットビットを前に伝播させるように注意しなければならない。クラスタアクセステーブルCATは、間接的なポインタを含む。ポインタは、ゾーンの中のデータクラスタ0が最初のデータクラスタであるを指し示す。一つのCATエントリは、単一のデータクラスタ暫定的にサイズが4KBを参照する。多くの反復データがあるときには、ディスク使用要件を低減するために、CATがハッシングとともに使用される。単一のCATは、格納の隣接ブロックをつねに表す。CATは、非データゾーンの中に含まれる。それぞれのCATエントリは48ビットである。以下の表は、それぞれのエントリがどのようにレイアウトされるかを示すそれぞれのデータゾーンが1GBのデータを含むと想定する:CATは64ビットの中に収まることが望ましいが、これは必要不可欠ではない。2TBアレイのためのCATテーブルは、現在、サイズが4GBまでである。それぞれのCATエントリは、データとゾーンの数とを含むゾーンを指し示す。図14は、ゾーンにおけるデータクラスタにアクセスするために、CATがどのように使用されるかを示す。冗長データは、CATにおける2つ以上のエントリによって参照される。2つの論理クラスタが同じデータを含むので、それらのCATエントリは、同じ物理的クラスタに指し示される。ハッシュキーエントリは、クラスタ全体の160ビットSHA1ハッシュ値の16ビット抽出を含む。このエントリは、書き込み操作の間にハッシュテーブルをアップデートするために使用される。16TBのデータを参照するCATにおけるそれぞれのエントリにおいて、十分なビットがある。しかし、すべてのデータクラスタが互いに異なる場合にはコンテンツに関して、2TBのデータを参照するために、ちょうど3ゾーン相当以上のCATエントリが必要とされるそれぞれのゾーンは、サイズが1GBであり、したがって1GBサイズのCATエントリを格納し得る。6バイトCATエントリを想定すると、178956970CATエントリ/ゾーンであり、すなわち、それぞれのクラスタが4Kである場合には、テーブルは約682GB/ゾーンを参照する。ホスト論理セクタ変換テーブルは、ホスト論理セクタアドレスをゾーン番号に変換するために使用される。ホスト論理セクタアドレスに対応するCATの部分は、このゾーンに常駐する。それぞれのCATエントリは、4096バイトのクラスタサイズを表すことに留意されたい。これは8つの512バイトセクタである。以下は、ホスト論理セクタ変換テーブルの表現を示す:ゾーンは、CAT全体を保持するように事前に割当てられ得る。代替的に、CATに対してより多くのエントリが要求されるときには、ゾーンがCATに対して割当てられ得る。CATは、2TB仮想ディスクをホストセクタアドレススペースにマッピングするので、ホストによるハードディスクのパーティショニングまたはフォーマッティングの間に、おそらくCATの大部分が参照される。このことを理由として、ゾーンは事前に割当てられ得る。CATは大きな1GB/ゾーンのテーブルである。使用されるクラスタのワーキングセットは、この大きなテーブルからのスパースセットsparsesetである。性能の理由のために、活動状態のエントリは、ディスクからおそらく時間的につねに読み込むのではなく、プロセッサメモリにおいてキャッシュされ得る。キャッシュを配置するために、少なくとも2つのオプションがあり、CATからの個々のエントリ、またはCATからの全体のクラスタである。進行中の書き込みは、CATキャッシュテーブルと結合されるので、すべての未処理の書き込みがキャッシュの中に留まることを保証する必要がある。したがって、キャッシュは、少なくとも、未処理の書き込みリクエストの最大数と同じくらい大きい必要がある。キャッシュにおけるエントリは、クラスタサイズすなわち4Kである。クラスタの上で作動中の進行中の書き込みがあるかどうかを知る必要がある。この指示は、クラスタについてのキャッシュエントリにおけるフラグとして格納され得る。以下の表は、CATキャッシュエントリのフォーマットを示す:キャッシュエントリにおける進行中のフラグは、2つの意味を有する。第一に、書き込みが進行中であり、クラスタの上のいかなる書き込みまたは追加の書き込みも、書き込みが完了するまでは延期されなければならない、ということを示す。第二に、キャッシュにおけるこのエントリは、ビットが設定される間はフラッシュflushされてはならない。このことは、部分的にはビットの状態を保護するためであり、このクラスタが現在使用されているという事実を反映させるためでもある。さらに、このことは、キャッシュのサイズが、少なくとも、未処理の書き込み操作の数と同じくらい大きくなければならないことを意味する。進行中の書き込みのインジケータをクラスタについてのキャッシュエントリに格納することの一つの利点は、現在操作中であるという事実を反映し、別のテーブルを有することを不要にし、追加のハッシュベースのルックアップ、またはこのビットもチェックするためのテーブルウォークtablewalkを不要にすることである。キャッシュは、書き込み遅延write-delayedキャッシュであり得る。より早く書き込ませることは有益であり得るが、書き込み操作が完了したときにキャッシュエントリをディスクに書き戻すのみでよい。ハッシュされ得る未処理の書き込みエントリの数を増加させるために、ハッシュ関数または他のメカニズムが使用され得る。代替のアプローチは、CATのクラスタ全体をキャッシュすることであるすなわちエントリのうちの4Kエントリ。このことは、アクセスの良好な空間的局所性がある場合に、一般的に性能を改善し得る。CATエントリは48ビット幅なので、注意が払われる必要があり、キャッシュにおけるエントリの全体の数はない。以下の表は、クラスタされたCATキャッシュエントリの例を示す:テーブルサイズは、40969964192バイトであり得る。250エントリのキャッシュサイズを有する必要があると想定すると、キャッシュは約1MBを占め得る。論理CATエントリアドレスの適切なマスキングによらずに、最初および最後のエントリが不完全であるかどうかを計算することは可能である。キャッシュするルックアップルーチンは、エントリのローディングの前にこれを行うべきであり、必要とされるCATクラスタをロードするべきである。ホストがセクタまたはクラスタ読み出しリクエストを送信するときに、論理セクタアドレスを介して送信する。論理セクタアドレスは、ホストによって要求される実際のデータを含むゾーンにおけるクラスタのオフセットを獲得するために、CATの中へのオフセットとして使用される。その結果は、ゾーン番号と、そのゾーンの中へのオフセットとである。その情報は、レイヤ2Layer2ソフトウェアに渡され、レイヤ2ソフトウェアは、次に、ドライブからロークラスタrawclusterを抽出する。ホストによっていまだかつて書き込まれていないクラスタを処理するために、すべてのCATエントリが、オールゼロを含むデフォルトクラスタを指し示すように初期化される。ジャーナルマネジャーは、二層の書き込み実行記録システムである。システムの目的は、書き込みリクエストがホストから受け入れられ得ることを確実にし、データが保全性を保証しながら受け入れられたことをホストに迅速に示し返すことである。さらに、システムは、任意のディスク書き込みの間のシステムリセットの場合において、ブロックレベルデータまたはシステムメタデータたとえばCATおよびハッシュテーブルエントリの破損または損失がないことを保証する必要がある。J1ジャーナルマネジャーは、すべての書き込みリクエストをホストからディスクへ可能な限り迅速にキャッシュする。ひとたび書き込みが首尾良く完了するとすなわちデータがアレイによって受け入れられると、ホストは、操作が完了したことを示すために信号を送られ得る。ジャーナルエントリは、故障から回復するときに、書き込みリクエストの回復を可能にする。ジャーナル記録は、ディスクに書き込まれるべきデータと、書き込みトランザクションに関連するメタデータとからなる。ディスク読み出し/書き込みを低減するために、書き込みに関連するデータが書き込まれて、クラスタを解放する。このことは、データを自動的にミラリングする。使用されていないクラスタは、使用されていないクラスタのリストから取られる。ひとたびデータが書き込まれると、使用されていないクラスタのリストは、ディスクに書き戻されなければならない。ジャーナル記録は、ミラリングされていないゾーンの上のジャーナルキューに対して書き込まれる。それぞれの記録は、サイズにおいてセクタであり、ジャーナル書き込みの間の故障が以前のジャーナルエントリを破損し得るリスクを低減するために、セクタ境界に位置合わせされる。ジャーナルエントリは、記録の終端において一意の増加するシーケンスカウントを含むので、キューの終端は容易に識別され得る。ジャーナル書き込み操作は、スレッドを処理するホストキューの中で同期的に生じる。ジャーナル書き込みは、ディスクに書き込まれるときに順序づけられなければならないので、任意の時間において一つのスレッドのみがジャーナルに書き込み得る。J1テーブルにおけるジャーナルエントリのアドレスは、一意の識別子として使用され得るので、J1ジャーナルエントリは、J2ジャーナルにおけるエントリと相互に関連させられ得る。ひとたびジャーナルエントリが書き込まれると、トランザクション完了通知が、ホスト完了キューに対して通知される。今や書き込み操作が実行され得る。ジャーナル書き込みが完了する前の、クラスタに対するいかなる次の読み出しも、遅延されることを保証することが重要である。以下の表は、J2ジャーナル記録のフォーマットを示す:それぞれのジャーナル記録は、セクタ境界に位置合わせされる。ジャーナル記録は、ゾーン/オフセット/サイズの組のアレイを含み得る。図15は、本発明の例示的な実施形態に従ったジャーナルテーブルアップデートを示す。具体的には、ホスト書き込みリクエストが受信されるときに、ジャーナルテーブルがアップデートされ、一つ以上のクラスタが割当てられ、データがクラスタに書き込まれる。ホストジャーナルリクエストが処理される。これらによって、クラスタは書き込まれ、ディスクにシャドウバックshadowbackされなければならないメタデータ構造たとえばCATテーブルへのアップデートももたらされる。たとえシステムリセットが生じても、これらのメタデータ構造がディスクに正しく書き戻されることを保証することが重要である。低レベルディスクI/O書き込みJ2ジャーナルは、このために使用される。ホストインタフェースジャーナルエントリを処理するために、メタデータ構造の適切な操作が決定されるべきである。メモリにおいて変化が生じるべきであり、種々のディスクブロックへの変化の記録が生成されるべきである。この記録は、ディスクの上でなされるべき実際の変化を含む。アップデートされるそれぞれのデータ構造は、J2ジャーナルマネジャーを用いて登録される。この記録は、ディスクベースのジャーナルに記録されるべきであり、識別子を用いてスタンプされるべきである。記録がJ1ジャーナルエントリと結びつけられる場合には、識別子がリンクされるべきである。ひとたび記録が格納されると、ディスクへの変更がなされ得るあるいはバックグラウンドタスクを介して行われ得る。J2ジャーナルは、論理的にレイヤ3において存在する。これは、ゾーンマネジャーを介した書き込みを含み得るメタデータアップデートを実行記録journalするために使用される。ジャーナルエントリの再生が生じるときには、ゾーンマネジャーの方法を使用する。ジャーナルそのものは、特殊な領域に格納され得る。ジャーナルエントリの短い寿命を考慮すれば、ジャーナルエントリはミラリングされない。特に構造へのアップデートがアトミックである場合には、すべてのメタデータがJ2ジャーナルを経る必要はない。領域マネジャー構造は、J2ジャーナルを使用し得ない。たとえばバックグラウンドスレッドをチェックする保全性を用いて、領域マネジャービットマップにおける不整合を検出することが可能であり得る。J2ジャーナルのための単純なアプローチは、単一の記録を含むことである。記録がディスクに対してコミットされるとすぐに、記録は再生され、ディスクの上の構造をアップデートする。複数のJ2記録を有することと、ディスクの上の記録のアップデートをコミットするバックグラウンドタスクを有することとは可能である。この場合、ジャーナルと、種々のデータ構造に関連する任意のキャッシングアルゴリズムとの間の相互作用に、周到な注意が払われる必要がある。最初のアプローチは、ジャーナルエントリがディスクに対してコミットされるとすぐに、ジャーナルエントリを実行する。原則としては、J2の複数の同時ユーザがあり得るが、J2ジャーナルは一度に一人のユーザに対してロックされ得る。たとえこの場合においても、ジャーナルエントリは、実行依頼されたらすぐにコミットされるべきである。任意のより高いレベルのジャーナル活動が生じる前に、メタデータ構造が修復されることを保証することが重要である。システム再起動の際に、J2ジャーナルが分析され、任意の記録が再生される。ジャーナルエントリがJ1ジャーナルエントリと相互に関連させられる場合には、J1エントリは、完成したものとしてマークされ、除去され得る。ひとたびすべてのJ2ジャーナルエントリが完成すると、メタデータは信頼性のある状態になり、任意の残りのJ1ジャーナルエントリが処理され得る。J2ジャーナル記録は、以下の情報を含む。操作の数各操作は以下を含む:-J1記録インジケータ-書き込むべきゾーン/データオフセット-書き込むべきデータ-データのサイズ-データクラスタの中へのオフセットジャーナル記録識別子終端マーカこのスキームは、たとえばJ2ジャーナルエントリの終端を識別するためにシーケンス番号を用いて、J2ジャーナルエントリをセクタ境界に置いて、J1ジャーナルスキームと同様に作動し得る。J1データポインタインジケータが設定される場合には、この特定の操作が、J1ジャーナル記録を指し示し得る。ホストによって供給される書き込みデータは、われわれのourジャーナルエントリにコピーされる必要はない。ジャーナル記録における操作の最大数は十分に理解されると予想されるので、操作は固定サイズとして定義されることができるべきである。低レベル書き込み操作の間におけるセクタの破損たとえば電力の損失によるものからの回復を可能にするために、J2ジャーナルは、書き込まれたセクタ全体を格納し得るので、必要な場合にはこの情報からセクタが再書き込みされ得る。代替的にまたは追加的に、書き込み操作の再生が必要とされるかどうかを決定するために、それぞれの変更されたセクタについて計算されたCRCは、J2記録に格納され得、ディスクの上のセクタからたとえばゾーンマネジャーによって計算されたCRCと比較され得る。異なるジャーナルが異なる位置に格納され得るので、ジャーナル記録を補助格納デバイスに書き込むために提供されるインタフェースレイヤがある。位置は非揮発性であるべきである。2つの候補は、ハードディスクおよびNVRAMである。J1がハードディスクに格納される場合には、J1ジャーナルのミラリングされないゾーンに格納される。J1ジャーナルは、NVRAMに格納する候補である。J2ジャーナルは、特殊な領域に格納され得るが、ディスクの上に格納されるべきであるすなわち、短い寿命を有するので冗長ではない。J2ジャーナルをディスクの上に格納する利点は、内部データ構造のアップデートの間にシステムリセットがある場合に、データ構造が一貫性のある状態に戻され得ることであるたとえユニットが長時間にわたって電源を入れられないままにされるとしても。ゾーンマネジャーZMは、より高いレベルのソフトウェアによって必要とされるゾーンを割当てる。ZMへのリクエストは以下を含む:a.ゾーンを割当てるb.ゾーンを再割当て/解放するc.L1に対してデータ読み出し/書き込みパススルーを制御するd.ゾーンにおけるクラスタの読み出し/書き込みをするクラスタのオフセットとゾーン番号とを考慮してZMは、冗長メカニズムを管理しドライブの数およびその相対的サイズの関数として、ミラリング、ストライピング、およびデータの読み出し/書き込みのための他の冗長スキームを処理する。ZMは、ゾーンを割当てる必要があるときには、2つ以上のセットの領域の割当てを要求する。たとえば、ゾーンは1GBのデータに対して割当てられ得る。このゾーンを構成する領域は、冗長データを含む1GBのデータを含むことができる。ミラリングメカニズムのために、ゾーンは、それぞれ1GBの2セットの領域からなる。別の例として、3ディスクストライピングメカニズムは、それぞれ1/2GBの3セットの領域を利用する。ZMは、ゾーンを構成する領域の各セットの位置ドライブ番号および開始領域番号を見出すために、ZR変換テーブル6を使用する。1/12GBの領域サイズを想定すると、最大24領域が必要とされる。24領域は2×1GBゾーンを構成する。したがって、ZR変換テーブルは、ドライブ/領域データを提供する24列を含む。ZMは一般的に以下のように働く:a.SDM単一ドライブミラリングの場合には、24列が使用される。ドライブ番号はすべての列において同じである。それぞれのエントリは、ゾーンを構成する物理的ドライブの上の物理的領域に対応する。最初の12エントリは、データの一つのコピーを含む領域を指し示す。最後の12エントリは、データの第2のコピーを含む領域を指し示す。b.DDM二重ドライブミラリングの場合は、最初の12エントリのドライブ番号が最後の12エントリのドライブ番号とは異なることを除いて、SDMと同じである。c.ストライピングの場合には、3つ以上の列が使用され得る。たとえば、ストライピングが3つのドライブにわたって使用される場合には、6つの領域が3つの異なるドライブから必要とされ得すなわち18エントリが使用される、最初の6エントリが同じドライブ番号を含み、次の6エントリが別のドライブ番号を含み、それに続く6エントリが第3のドライブ番号を含み、未使用のエントリはゼロにされる。以下は、ゾーン領域変換テーブルの表現を示す:読み出し/書き込みリクエストが入ってくるときに、ZMは、ゾーン番号およびそのゾーンの中へのオフセットを提供される。ZMは、そのゾーンについての冗長メカニズムを見出すためにZR変換テーブルを調べ、どのドライブ/領域が読み出し/書き込みされなければならないセクタを含むかを計算するためにオフセットを使用する。ドライブ/領域情報は、次に、実際の読み出し/書き込みを行うL1レイヤに提供される。使用Usageの列における追加の可能なエントリは、使用されていないである。使用されていないは、ゾーンが定義されているものの、現在は使用中ではないことを示す。クラスタマネジャーは、データゾーンのセットの中のクラスタを割当ておよび再割当てする。レイアウトマネジャーは、ゾーンの領域に対するゾーンのランタイム再レイアウトを提供する。このことは、ディスクの挿入/取り外しまたは故障の結果として生じ得る。レイヤ1L1ソフトウェアは、物理的なドライブおよび物理的なセクタについて知っている。なかでも、L1ソフトウェアは、ゾーンマネジャーによる使用のために、物理的ドライブから領域を割当てる。この例示的な実施形態において、それぞれの領域は、4ドライブアレイシステムについて1/12GBすなわち174763セクタのサイズを有する。より大きなドライブ最大数8、12または16を有するシステムは、異なる領域サイズを有する。SD33つのドライブにわたるストライピング;パリティがプラスされた2データを用いて1GBのデータを含むゾーンを作成するためには、3つのドライブにおいてそれぞれ6つの領域を使用することになる6×1/12=ドライブあたり1/2GB。この領域スキームの使用は、ゾーンが、たとえばミラリングからストライピングへと、移動または再構成されるときに、ディスクスペースのより良好な利用を提供することを可能にする。L1ソフトウェアは、領域のビットマップを用いて、物理的ドライブの上の利用可能なスペースを追跡する。それぞれのドライブは一つのビットマップを有する。それぞれの領域は、領域が使用されていないか、使用されているか、または不良であるかを追跡するために、ビットマップにおける2ビットによって表される。L2ソフトウェアZMは、ゾーンを作成する必要があるときには、L1レイヤから領域のセットを得る。ゾーンを構成する領域は、ディスクの中で隣接しない。L1へのリクエストは以下を含む:a.データの読み出し/書き込みをする領域のグループの中のクラスタに対してb.読み出し/書き込みを制御するテーブル、データ構造、DICなどc.領域に対して物理的スペースを割当てる1ドライブの中の実際の物理的セクタd.領域を再割当てするe.物理的ドライブの中の物理的クラスタに対してローRaw読み出し/書き込みをするf.領域から領域へデータをコピーするg.領域を不良としてマークする使用されていない領域ビットマップは大きくあり得、したがって、使用されていないエントリを見つけるための検索最悪の場合、使用されていないエントリがないは、遅くあり得る。性能を改善するために、ビットマップの一部がメモリの中に事前にロードされ得、使用されていない領域のリンクされたリストがメモリに格納され得る。活動状態のそれぞれのゾーンについてリストがある。リストの最低点に達した場合には、より多くの使用されていないエントリが、バックグランド活動としてディスクから読み出され得る。ディスクマネジャーDiskManagerは、レイヤ0において作動する。以下の表に示されるように、2つのサブレイヤがあり、具体的には、抽象化レイヤと、物理的な格納アレイと通信するデバイスドライバとである。デバイスドライバDeviceDriverレイヤはまた、いくつかのレイヤを含む。たとえば、USBドライブを使用する格納アレイのために、USB移送レイヤの一番上にATAまたはSCSIスタックがある。抽象化レイヤは、格納アレイにおいて使用されるドライブの種類から独立した、基本的な読み出し/書き込み機能を提供する。一つ以上のディスクアクセスキューが、ディスクアクセスリクエストをキューに入れるために使用され得る。ディスクアクセスレートは、われわれのシステムにおける重要な性能ボトルネックの一つである。われわれは、全般的なシステム待ち時間を低減し、性能を改善するために、ディスクインタフェースがつねに可能な限りビジーに保たれることを確実にしたい。ディスクインタフェースへのリクエストは、非同期インタフェースを有するべきであり、ディスク操作が終了したときには、コールバックハンドラが操作を完了する。一つのディスクリクエストの完了は、キューの上の次のリクエストを自動的に開始する。ドライブごとに一つのキュー、またはすべてのドライブに一つのキューがあり得る。レイヤ1は、ドライブを論理ドライブ番号として参照する。レイヤ0は、論理ドライブ番号を、物理的ドライブ参照に変換するたとえば、オープンコールの結果として、/dev/sdaまたはファイルデバイス番号。柔軟性のためにUSBを介した拡張、それぞれの論理ドライブについてキューがあるべきである。以下は、一部の例示的なオブジェクト定義およびデータフローである:以下は、物理的ディスクレイアウトの説明である。上述のように、それぞれのディスクは固定サイズの領域に分割される。この例示的な実施形態において、それぞれの領域は、4ドライブアレイシステムについて、1/12GBすなわち174763セクタのサイズを有する。より大きなドライブ最大数8、12または16を有するシステムは、異なる領域サイズを有する。最初に、領域番号0および1は、領域マネジャーによる使用のために予約され、割当てのためには使用されない。領域番号1は、領域番号0のミラリングである。所定のハードディスクについて領域マネジャーによって使用されるすべての内部データは、このハードディスクの領域番号0および1に格納される。この情報は、他のドライブと重複またはミラリングされない。領域0または1のいずれかにエラーがある場合には、データを保持するために他の領域が割当てられ得る。ディスク情報構造DiskInformationStructureは、これらの領域を指し示す。それぞれのディスクは、ディスクと、ディスクが属するディスクセットと、ディスクについてのレイアウト情報とを識別する、DISを含む。ハードディスクの上の第1のセクタは予約されている。DISは、第1のセクタの後の、第1の不良でないクラスタに格納される。DISは、1KB相当のデータの中に含まれる。DISの2つのコピーがある。DISのコピーは、DISが属するディスクの上に格納される。さらに、システムにおけるすべてのディスクは、システムにおけるディスクのすべてのDISのコピーを含む。以下の表は、DISフォーマットを示す。領域マネジャーは、領域情報構造における内部データを格納する。以下の表は、領域情報構造フォーマットを示す。ゾーン情報構造は、ゾーンマネジャーがどこにゾーンテーブルを見出し得るかに関する情報を提供する。以下は、ゾーン情報構造フォーマットを示す。高レベル情報ゾーンは、ハイレベルマネジャーによって使用されるゾーンテーブルおよび他のテーブルを含む。これらは、ミラリングを使用して保護される。以下の表は、ゾーンテーブルノードフォーマットを示す。以下は、ゾーン情報のレイアウトの説明である。ゾーンテーブルノードZonesTableNodesのリンクされたリストは、以下の方法でZISの後に置かれる。この情報は、ゾーンテーブル領域ZonesTableRegionに格納される。図16は、本発明の例示的な実施形態に従ったドライブレイアウトを示す。最初の2つの領域は、互いのコピーである。第3のオプションのゾーンテーブル領域は、ゾーンテーブルを含む。一つ以上のドライブを有するシステムにおいて、ドライブのうちの2つのみがZTRを含む。一つのドライブのみを有するシステムにおいて、2つの領域は、ZTRの2つのミラリングされたコピーを保持するために使用される。DISは、RISおよびZISの位置に関する情報を含む。RISの第1のコピーは、領域0の中にある必要はないことに留意されたいたとえば、領域0が不良セクタを含む場合には、異なる領域に位置し得る。ゾーンマネジャーは、システム起動時にゾーンテーブルをロードする必要がある。それを行うために、ゾーンマネジャーは、領域番号およびオフセットをDISから抽出する。これは、ZISの開始を指し示す。定モジュールたとえばCATマネジャーは、制御構造およびデータテーブルをゾーンに格納する。レイヤ3以上におけるモジュールについてのすべての制御構造は、ゾーン0に格納される構造から参照される。このことは、たとえば、実際のCATクラスタ割当てテーブルの位置が、ゾーン0に格納されたデータ構造から参照されることを意味する。以下の表は、ゾーン0情報テーブルフォーマットを示す。CATのリンクされたリストは、CATを含むゾーンを記述するノードのリンクされたリストである。以下の表は、CATのリンクされたリストのノードフォーマットを示す。ハッシュテーブルのリンクされたリストは、ハッシュテーブルを保持するゾーンを記述するノードのリンクされたリストである。以下の表は、ハッシュテーブルのリンクされたリストのノードフォーマットを示す。図17は、本発明の例示的な実施形態に従った、ゾーン0のレイアウトと、他のゾーンがどのように参照されるかとを示す。上述のように、冗長セットは、データのセットに対して冗長性を提供するセクタ/クラスタのセットである。領域をバックアップすることは、一つの領域のコンテンツを別の領域にコピーすることを含む。データ読み出しエラーの場合には、より低いレベルのソフトウェアディスクマネジャーまたはデバイスドライバは、最初の失敗した試みの後に、追加の2回にわたって読み出しリクエストを再試行する。失敗状態は、ゾーンマネジャーに返される。次に、ゾーンマネジャーは、冗長クラスタから読み出しによってリクエストされるデータを、ディスクアレイにおいて再構築することを試みる。冗長データは、ミラリングされたクラスタSDM、DDMについて、またはパリティを含むクラスタのセットストライピングされたインプリメンテーションについてのいずれかであり得る。次に、再構築されたデータは、ホストに返される。ZMがデータを再構築することができない場合には、読み出しエラーがホストに返される。ゾーンマネジャーは、エラー通知パケットErrorNotificationPacketをエラーマネジャーErrorManagerに送信する。図18は、本発明の例示的な実施形態に従った読み出しエラー処理を示す。データ書き込みエラーの場合には、より低いレベルのソフトウェアディスクマネジャーまたはデバイスドライバは、最初の失敗した試みの後に、追加の2回にわたって書き込みリクエストを再試行する。失敗状態はゾーンマネジャーに返される。ゾーンマネジャーは、エラー通知パケットをエラーマネジャーに送信する。このレベルにおいてデータ書き込みが実行されるときに、冗長情報もディスクに書き込まれる。結果として、一つのみのクラスタが書き込みエラーを有する限りは、次の読み出しはデータを再構築することができる。複数のディスクエラーがあり、冗長情報が読み出しまたは書き込みされ得ない場合には、少なくとも二つの可能なアプローチがある。a.書き込みエラー状態をホストに戻す。冗長セットに関連するすべての領域を、不良セクタを含まない、新たに割当てられた領域に、バックアップする。b.書き込みを遅らせる。冗長セットに関連するすべての領域を、不良セクタを含まない、新たに割当てられた領域に、バックアップする。次に、新たに割当てられた領域における適切なクラスタに書き込みを行うすべての冗長部分、たとえばパリティなどとともに。別個の書き込みキューは、遅らせられた書き込みを含むように使用され得る。アプローチaは、問題がある。なぜなら、ジャーナルの成功した書き込みの結果として、書き込み状態がすでにホストに送信されてい得るので、ホストはエラーがあったことを知り得ないからである。代替策は、読み出しの失敗を報告するが、書き込みを可能にすることである。CATにおけるビットは、特定のLBAが不良読み出しを戻すべきであることを追跡するために使用され得る。図19は、本発明の例示的な実施形態に従ったエラー処理を示す。エラーマネジャーEMは、クラスタが本当に不良であるかどうかを知るためにクラスタをチェックする。そうである場合には、領域全体が不良であると考えられる。領域のコンテンツは、同じディスクの上の新たに割当てられた領域にコピーされる。次に、現在の領域はBAD不良とマークされる。領域にコピーする間に、エラーマネジャーは、不良セクタに遭遇したときに、必要とあればデータを再構築する。図20は、本発明の例示的な実施形態に従った、エラーマネジャーによる不良領域のバックアップを示す論理フロー図である。データ読み出しエラーがあり、エラーマネジャーが所定のクラスタについてデータを再構築できない場合にはたとえば、冗長セットにわたる読み出しエラーの結果として、再構築され得ないデータの代わりに、ゼロが使用される。この場合には、不良セクタを含む他のセクタ冗長セットからのもまた、バックアップされなければならない。この場合もやはり、再構築され得ないデータの代わりにゼロが使用される。ひとたび冗長セットのコピーが行われると、EMはゾーンのこの部分に対応するクラスタへのアクセスを使用不能にする。次にEMは、新たに割当てられた領域を指し示すように、ゾーンテーブルをアップデートする。次に、クラスタへのアクセスが再び使用可能にされる。この例示的な実施形態は、8つのスナップショットをサポートするように設計されるこれは、ハッシュ/クラスタのエントリが特定のスナップショットインスタンスによって使用されるかどうかを示す1バイトの使用を可能にする。スナップショットに含まれる2つのテーブルがある。1.スナップショットあたりのCATテーブルは、論理セクタアドレスと、そのLASについてのデータを含むディスクの上のクラスタとの関係を捉えるように、存在する必要がある。究極的には、スナップショットあたりのCATは、スナップショットが取られた瞬間におけるCATのコピーでなければならない。2.ハッシュ値とデータクラスタとの間のマッピングをするシステムハッシュテーブル。ハッシュ関数は、どのスナップショットが使用されているかに関わらず同じ結果を返し、結果としてすべてのスナップショットにわたって共通である。結果として、このテーブルは、一意にクラスタが任意のスナップショットによって使用されているかどうかを理解しなければならない。ハッシュエントリを使用するスナップショットがない限りは、ハッシュクラスタエントリは、解放され得ないか、または新しいデータと置き換えられ得ない。現在のものでありなおかつ追加されつつあるスナップショットが、つねにある。ハッシュエントリが作成またはアップデートされるときに、現在のスナップショット番号をそのハッシュエントリに適用する必要がある。スナップショットが作られるときに、現在のスナップショット番号が増加させられる。任意のスナップショットによってもはや必要とされないクラスタ/ハッシュのエントリは、ハッシュテーブルをざっと読むことwalkingthroughによって解放され、リタイヤretireしたスナップショットビットセットで任意のハッシュエントリを見出し、そのビットをクリアする。スナップショットバイトがゼロである場合には、ハッシュエントリはテーブルから除去され得、クラスタは解放され得る。ハッシュツリーに追加されつつある任意の新しいエントリとの衝突を防ぐために新しいスナップショット番号は、リタイヤするスナップショット番号と同じであるから、7つのスナップショットのみが取られることが可能にされ得、最後の8番目のスナップショットはリタイヤするスナップショットである。ハッシュテーブルは、バックグラウンド活動として調べられwalked得る。スナップショットを作成するために、主たるCATがアップデートされているときはいつでも、第2のCATゾーンが書き込まれ得る。これらのアップデートはキューに入れられ得、シャドーshadowCATは別のタスクとしてアップデートされ得る。スナップショットするために、シャドーCATはスナップショットCATになる。ひとたびスナップショットが行われると、新しいスナップショットCATになる新しいゾーンにこのスナップショットテーブルをコピーするために、バックグランドプロセスが開始され得る。CATのコピーが完了するまではシャドーCATキューが処理されないように、キューが使用され得る。万一、シャドーCATをアップデートする前に故障が生じた場合にはこの場合にはキューにおけるエントリが失われ得る、アレイがオンラインにされる前に、主たるCATテーブルからの再シャドーが実行され得る。代替的に、スナップショットが必要とされるときに、最初のCATコピーがプラスされたデルタの収集がスナップショットを構成し得る。次に、バックグランドタスクが、この情報から完全なスナップショットCATを再構成し得る。このことは、スナップショットを行うためにダウンタイムをほとんどあるいはまったく必要とし得ない。一方、デルタの別のセットが、次のスナップショットのために収集され得る。上述のように、いわゆるガーベッジコレクタは、ホストファイルシステムによってもはや使用されないクラスタを解放するために使用され得るたとえばファイルが削除されるとき。一般的に言って、ガーベッジ収集は、使用されていないブロックを見出し、それらのホストLSAを計算し、LSAに基づいてそれらのCATエントリの場所を突き止めることによって働く。特定のLSAについてCATエントリがない場合には、クラスタはすでに使用されていない。しかし、CATエントリの場所が突き止められる場合には、参照カウントが増加され、カウントがゼロに当たる場合にクラスタが解放される。ガーベッジ収集の一つの問題は、ホストファイルシステムが使用しているブロックと、すでに使用され、ある時点で使用されていないとしてマークされたブロックとを区別することが難しくあり得ることである。ホストファイルシステムがブロックを書き込むときに、格納システムは、データのクラスタならびにそれを記述するCATエントリを割当てる。その時点から、たとえホストファイルシステムが次にそのブロックの使用を停止したとしても、一般的にクラスタは使用されているように見えるすなわち、クラスタは有効なCATエントリとともにまだ使用されている。たとえば、特定のホストファイルシステムは、使用されたディスクブロックを追跡するためにビットマップを使用する。最初は、ビットマップは、たとえばすべてのビットをクリアすることによって、すべてのブロックが使用されていないことを示す。ファイルシステムが使用されると、ホストファイルシステムは、使用されていないブロックビットマップを使用することによって、ブロックを割当てる。格納システムは、クラスタおよびCATエントリを以前に概略されたoutlinedものとして割当てることによって、物理的格納をこれらのファイルシステム割当てと関連づける。ホストファイルシステムが、一部のブロックを、使用されていないプールに解除するときに、使用されていないブロックビットマップにおける対応するビットをクリアする必要が単にある。格納システムの上で、このことは、ホストの使用されていないブロックビットマップの一部をたまたま含むクラスタへの書き込みとして、一般的に明らかにされ、おそらく解放された実際のクラスタに対するI/Oがないしかし、たとえば、ホストファイルシステムが一部の強化されたセキュリティーモードで実行している場合には、解放されたクラスタに対するI/Oがあり得、その場合には、長期経過のstaleクラスタコンテンツが攻撃者によって読み出され得る可能性を低減させるために、ゼロまたはランダムデータのクリプトストロングハッシュcryptostronghashをクラスタにおそらく書き込み得る。さらに、ホストファイルシステムが、新しい割当てリクエストを満たすときに以前に解放したブロックを再使用するという保証はない。したがって、ホストファイルシステムが、格納システムの観点から、新しい、すなわち以前に再使用されたブロックを割当て続ける場合には、格納システムは、使用されていないクラスタをすぐに使い果たしてしまい、圧縮によって再生され得るどんなスペースにも左右される。たとえば、ファイルシステムブロックが4kであると想定すると、ホストが、ファイルシステムブロック100~500を割当て、次に使用されていないブロック300~500を割当て、次にブロック1000~1100を割当てる場合には、合計のファイルシステム使用は300ブロックになり、それでもアレイは500クラスタを使用する。本発明の例示的な実施形態において、格納システムは、ホストファイルシステムのレイアウトにアクセスし、その使用されていないブロックビットマップを分析し、ファイルシステムによってもはや使用されていないクラスタを特定するためにその情報を使用することによって、ホストファイルシステムのディスクリソースの解放を検出し得る。格納システムが未使用のクラスタをこのように特定できるためには、格納システムは、ファイルシステムの使用されていないブロックビットマップの場所を突き止めて理解することができなければならない。したがって、格納システムは、所定のセットのファイルシステムを一般的にサポートし、格納システムは、ファイルシステムについて、使用されていないブロックビットマップの場所を突き止めて利用するのに十分なほど内部の働きを理解する。サポートされないファイルシステムについては、格納システムは、おそらくガーベッジ収集を実行することができず、したがって、過剰にコミットされることを回避するために、アレイの実際の物理的サイズの公示のみをするべきである。ファイルシステムタイプたとえば、NTFS、FAT、ReiserFS、ext3を決定するために、ファイルシステムのスーパーブロックまたは同等の構造の場所が突き止められる必要がある。スーパーブロックを見出すために、パーティションテーブルが分析されて、OSパーティションの場所を突き止める。OSパーティションの場所が突き止められると想定すると、スーパーブロックの場所を突き止める目的のために、OSパーティションが分析され、それによってファイルシステムタイプを特定する。ひとたびファイルシステムタイプがわかると、使用されていないブロックビットマップを見出すために、レイアウトが分析され得る。使用されていないブロックの検索を容易にするために、たとえば、非公式の非冗長ゾーンに格納され得る使用されていないブロックビットマップのコピーを作り、そのコピーを使用して検索を実行することによって、ホストファイルシステムビットマップの履歴データが保たれ得る。ビットマップのサイズを考慮すれば、情報は、ビットマップ全体についてではなく、一度に比較的少数のクラスタについて保たれ得る。ガーベッジ収集が実行されるときに、現在の使用されていないブロックビットマップが、クラスタごとに履歴コピーと比較され得る。割当てられた状態から使用されない状態へと移行する任意のビットマップエントリが特定され得、ごみあさりをするscavenging操作が、再使用の良い候補であるクラスタに正確に向けられることを可能にする。それぞれのビットマップクラスタが処理されると、ビットマップ操作の経過する履歴を維持するために、履歴コピーが現在のコピーと置き換えられ得る。時間が経つにつれて、使用されていないブロックビットマップのコピーは、時間的にばらばらなクラスタの寄せ集めになるが、使用されていないエントリの場所を突き止めるために、現在のコピーがつねに使用されるので、このことは何の問題も引き起こさない。特定の条件下で、たとえば、ホストファイルシステムが、使用されていないブロックビットマップを使用してディスクブロックを割当て、次にデータブロックを書き込み、次に変更されたビットマップをディスクに流し戻す場合には、使用されていないブロックビットマップに関する競争状態があり得る。そのような場合には、たとえファイルシステムがクラスタを使用中であるとしても、ガーベッジコレクタがクラスタを解放し得る。このことはファイルシステムの破損につながり得る。格納システムは、そのような条件を回避または処理するようにインプリメントされるべきである。ガーベッジ収集はかなり高価な操作であり得、軽量のごみあさりがバックエンドI/O帯域幅を消費するので、ガーベッジ収集は過剰に使用されるべきではない。ガーベッジコレクタは、軽いバックグランドの遅いごみあさりから、積極的で重量の、または高優先度でさえあるごみあさりにわたる、いくつかのモードにおいて実行することができるべきである。たとえば、ガーベッジコレクタは、スペースの30が使用されるときに、または少なくとも週に一回、軽く実行され得、スペースの50が使用されるときに、やや激しく実行され得、ディスクスペースの90以上が使用されるときに、すっかり高優先度のごみあさりで実行され得る。ガーベッジコレクタの積極性は、再利用するクラスタの目標数に限定することによって、およびおそらくそれぞれの収集実行について最大の許容できるI/Oカウントに限定することによって、制御され得る。たとえば、ガーベッジコレクタは、わずか10,000のI/Oを使用して1GBを再使用するように構成され得る。再利用リクエストを達成できなかったことは、次回に実行されるときにより積極的に操作するように、コレクタへのフィードバックとして使用され得る。ガーベッジコレクタがホストファイルシステム全体の使用されていないブロックビットマップを分析することと、おそらく可能なすべてのブロックを再使用することとの許可を、ガーベッジコレクタに与える、すべて再使用モードもあり得る。これは、アレイがほとんど完全に満杯であるときに、クラスタを再使用する最後の試みとして行われ得る。ガーベッジコレクタは、そのルールを適用するために定期的に実行され得、ごみあさり操作を実行することを決定し得るかまたはし得ない。ごみあさり操作は、別のモジュールたとえば領域マネジャーが領域を構築するためにクラスタを見出そうと努力しているときの領域マネジャーから明示的に要求されることもできるべきである。ガーベッジ収集機能は、状態インジケータメカニズムの中に結びつけられ得る。たとえば、ある時点において、格納システムは赤色状態にあり得るが、進行中のガーベッジ収集操作は赤色状態を消去するのに十分なスペースを解放し得る。関連する状態情報を示すために、追加のインジケータ状態が使用され得るたとえば、赤色インジケータは、ガーベッジ収集操作が進行中であることを示すように点滅させられ得る。図21は、本発明の例示的な実施形態に従った、格納アレイの関連するコンポーネントを示す模式的なブロック図である。なかでも、格納アレイは、シャーシ2502を含み、格納マネジャー2504はシャーシ2502を介して複数の格納デバイス25081~2508Nと通信し、格納デバイス25081~2508Nはそれぞれ複数のスロット25061~2506Nを通してシャーシに結合される。それぞれのスロット25061~2506Nは、一つ以上のインジケータ25071~2507Nと関連づけられ得る。なかでも、格納マネジャー2504は、上述の機能性をインプリメントするための種々のハードウェアおよびソフトウェアのコンポーネントを一般的に含む。ハードウェアコンポーネントは、プログラムコード、データ構造、およびデータを格納するためのメモリ、ならびにプログラムコードを実行するためのマイクロプロセッサシステムを一般的に含む。仮想ホットスペア上述のように、多くの格納システムにおいて、ホットスペア格納デバイスが作動可能状態において維持されるので、別の格納デバイスが故障した場合に迅速にオンラインにされ得る。本発明の特定の実施形態において、物理的に別個のホットスペアを維持するのではなく、複数の格納デバイスにわたる未使用の格納容量から、仮想ホットスペアが作成される。物理的なホットスペアとは異なり、この未使用の格納容量は、格納デバイスが残りの格納デバイスから回復されたデータを格納できない場合に利用可能である。仮想ホットスペア機構は、ディスク故障の際にデータが冗長に再レイアウトされ得ることを保証するために、アレイの上に十分なスペースが利用可能であることを必要とする。したがって、進行中の方法で、格納システムは、一般的に、仮想ホットスペアのインプリメンテーションのために必要とされる未使用の格納容量の量を決定したとえば、格納デバイスの数、種々の格納デバイスの容量、格納されるデータの量、およびデータが格納される方法に基づいて、仮想ホットスペアのために追加の格納容量が必要とされる場合に信号を発生するたとえば、実質的に上述のような状態およびスロットを示す緑色/黄色/赤色のライトを使用して。ゾーンが割当てられると、ディスクごとにそのゾーンを再レイアウトするためにいくつの領域が必要とされるかについての記録が保たれる。以下の表は、4つのドライブが使用される仮想ホットスペアを示す。以下の表は、3つのドライブが使用される仮想ホットスペアを示す。この例示的な実施形態において、仮想ホットスペアは、1つまたは2つのドライブのみを有するアレイの上では利用可能ではない。それぞれのゾーンと、アレイにおけるディスクの数とに関する情報に基づいて、アレイは、それぞれのあり得るディスク故障について再レイアウトのシナリオを決定し、それぞれのシナリオについてそれぞれのドライブの上で十分なスペースが利用可能であることを保証する。生成される情報は、再レイアウトエンジンおよびゾーンマネジャーにフィードバックされ得るので、データは、データ格納とホットスペア機構との間で正しくバランスを取られ得る。ホットスペア機構は、再レイアウトが生じ得るように、ゾーンレイアウトデータから計算されるものに加えて、十分なスペアワーキングスペース領域を必要とすることに留意されたい。図22は、本発明の例示的な実施形態に従った、仮想ホットスペアを管理するための例示的な論理を示す論理フロー図である。ブロック2102において、論理は、それぞれのあり得るディスク故障について再レイアウトのシナリオを決定する。ブロック2104において、論理は、最悪の事態のシナリオにおいてデータを冗長に再レイアウトするためにそれぞれのドライブの上で必要とされるスペースの量を決定する。ブロック2106において、論理は、最悪の事態のシナリオにおいてデータを冗長に再レイアウトするために必要とされるスペアワーキングスペース領域の量を決定する。ブロック2108において、論理は、最悪の事態のシナリオにおいてデータを冗長に再レイアウトすることを可能にするためにそれぞれのドライブの上で必要とされるスペースの総量を決定する基本的に、再レイアウトのために必要とされるスペースの量と、必要とされるスペアワーキングスペース領域の量との合計。ブロック2110において、論理は、格納システムが適切な大きさの利用可能な格納デバイスを含むかどうかを決定する。適切な大きさの利用可能な格納デバイスがある場合にはブロック2112におけるはい、論理反復はブロック2199において終了する。しかし、不適切な大きさの利用可能な格納装置がある場合にはブロック2112におけるいいえ、論理は、ブロック2114において、どのドライブ/スロットがアップグレードを必要とするかを決定する。次に、ブロック2116において、論理は、追加の格納スペースが必要とされるという信号を出し、どのドライブ/スロットがアップグレードを必要とするかを示す。論理反復は、ブロック2199において終了する。図23は、本発明の例示的な実施形態に従った、図22のブロック2102におけるような、それぞれのあり得るディスク故障について再レイアウトのシナリオを決定するための例示的な論理を示す論理フロー図である。ブロック2202において、論理はゾーンを割当てる。次に、ブロック2204において、論理は、ディスクごとにそのゾーンを再レイアウトするためにいくつの領域が必要とされるかを決定する。論理反復は、ブロック2299において終了する。図24は、本発明の例示的な実施形態に従った、仮想ホットスペア機能を呼び出すための例示的な論理を示す論理フロー図である。ブロック2302において、論理は、最悪の事態のシナリオの際にデータを冗長に再レイアウトすることを可能にするために利用可能な格納の十分な量を維持する。ブロック2304においてドライブの損失たとえば取り外しまたは故障を決定すると、論理は、ブロック2306において、データの故障許容を復元するために、一つ以上の残りのドライブを自動的に再構成する。論理反復は、ブロック2399において終了する。図25は、本発明の例示的な実施形態に従った、図24のブロック2306におけるような、データの故障許容を復元するために一つ以上の残りのドライブを自動的に再構成するための例示的な論理を示す論理フロー図である。ブロック2402において、論理は、4つ以上の格納デバイスにわたる第1のストライピングパターンを、3つ以上の残りの格納デバイスにわたる第2のストライピングパターンに変換し得る。ブロック2404において、論理は、3つの格納デバイスにわたるストライピングパターンを、残りの2つの格納デバイスにわたるミラリングパターンに変換し得る。もちろん、論理は、ドライブの損失の後でデータを冗長に再レイアウトするために、他の方法でパターンを変換し得る。論理反復は、ブロック2499において終了する。再び図21を参照すると、格納マネジャー2504は、上述のような仮想ホットスペア機能をインプリメントするための適切なコンポーネントおよび論理を一般的に含む。動的アップグレード格納の動的な拡大および縮小を処理するための上述の論理は、動的にアップグレード可能なシステムを提供するように延長され得る。該システムにおいて、格納デバイスは必要に応じてより大きな格納デバイスと置き換えられ得、冗長性が維持または拡張されて、なおかつより大きな格納デバイスによって提供される追加の格納スペースが、複数の格納デバイスにわたる利用可能な格納スペースのプールに含まれるように、既存のデータが格納デバイスにわたって自動的に再構成される。したがって、より小さな格納デバイスがより大きな格納デバイスに置き換えられるときに、すでに格納されたデータの冗長性を改善するため、ならびに追加のデータを格納するために、追加の格納スペースが使用され得る。より多くの格納スペースが必要とされるときはいつでも、適切な信号がユーザに提供されたとえば実質的に上述のような緑色/黄色/赤色のライトを使用して、ユーザは単に格納デバイスを取り外し得、それをより大きな格納デバイスと置き換え得る。図26は、本発明の例示的な実施形態に従った、格納デバイスをアップグレードするための例示的な論理を示す論理フロー図である。ブロック2602において、論理は、第1の格納デバイスの上のデータを、その上に格納されたデータが他の格納デバイスの上で冗長に見えるように、格納する。ブロック2604において、論理は、第1の格納デバイスが、第1の格納デバイスよりも大きな格納容量を有する置換用デバイスと置き換えられたことを検出する。ブロック2606において、論理は、第1のデバイスの上に格納されたデータを、他のデバイスの上に冗長に格納されたデータを使用して、置換用デバイスの上に自動的に複写する。ブロック2608において、論理は、新しいデータを冗長に格納するために利用可能な置換用デバイスの上に、追加の格納スペースを作る。ブロック2610において、新しいデータに冗長性を提供するために利用可能な十分な量の格納容量を有するデバイスが他にない場合には、論理は、置換用デバイスの上の追加の格納スペースの中に、新しいデータを冗長に格納し得る。ブロック2612において、少なくとも一つの他のデバイスが、新しいデータに冗長性を提供するために利用可能な十分な量の格納容量を有する場合には、論理は、複数の格納デバイスにわたって新しいデータを冗長に格納し得る。再び図21を参照すると、格納マネジャー2504は、上述のような動的アップグレード機能をインプリメントするための適切なコンポーネントおよび論理を一般的に含む。その他本発明の実施形態は、本明細書において全体が参照により援用されている、GeoffreyS.Barralの名義で2004年11月5日に出願された米国仮特許出願第60/625,495号に記述される態様で、周辺接続プロトコルを使用して、格納容量をホストコンピュータに提供するように使用され得る。ハッシュアルゴリズムは、厳密に一意のハッシュ値を生成し得ないことが留意されるべきである。したがって、ハッシュアルゴリズムが、同一でないコンテンツを有するデータの2つのチャンクに対して、同じハッシュ値を生成することが考えられる。ハッシュアルゴリズムを一般的に取り入れるハッシュ関数は、一意性を確認するメカニズムを一般的に含む。たとえば、上述のような本発明の例示的な実施形態において、一つのチャンクのハッシュ値が別のチャンクのハッシュ値と異なる場合には、これらのチャンクのコンテンツは同一でないと考えられる。しかし、一つのチャックのハッシュ値が別のチャンクのハッシュ値と同じである場合には、コンテンツが同一であるか同一でないかを決定するために、ハッシュ関数は、2つのチャンクのコンテンツを比較し得るか、または何らかの他のメカニズムを利用し得るたとえば異なるハッシュ関数。論理フロー図は、本発明の種々の局面を示すために本明細書中で使用されるものであり、本発明を任意の特定の論理フローまたは論理インプリメンテーションに限定するものと解釈されるべきではないことが留意されるべきである。記載される論理は、全般的な結果を変化させることなく、またはさもなければ本発明の真の範囲から逸脱することなく、異なる論理ブロックたとえば、プログラム、モジュール、機能、またはサブルーチンに分割され得る。全般的な結果を変化させることなく、またはさもなければ本発明の真の範囲から逸脱することなく、しばしば、時間および論路要素が、追加され得、変更され得、省略され得、異なる順序で実行され得、または異なる論理構成を使用してインプリメントされ得るたとえば、論理ゲート、ルーピング基本命令、条件付き論理、および他の論理構成。本発明は、プロセッサたとえば、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ、または汎用コンピュータとともに使用するコンピュータプログラム、プログラム可能論理デバイスとともに使用するプログラマブルロジックたとえば、フィールドプログラマブルゲートアレイFieldProgrammableGateArrayFPGA、または他のPLD、個別のコンポーネント、集積回路たとえば、特定用途向けICApplicationSpecificIntegratedCircuitASIC、またはこれらの任意の組み合わせを含む任意の他の手段を含むが決してこれらに限定されない多くの異なる形で具体化され得る。本明細書中にこれまで記載された機能性のすべてまたは一部をインプリメントするコンピュータプログラム論理は、ソースコードの形態、コンピュータ実行可能な形態、および種々の中間的な形態たとえば、アセンブラ、コンパイラ、リンカ、またはロケータを含むが決してそれらに限定されない、種々の形において具体化され得る。ソースコードは、種々のオペレーティングシステムまたはオペレーティング環境とともに使用する、種々のプログラミング言語たとえば、オブジェクトコード、アセンブリ言語、またはFortran、C、C、JAVA登録商標、またはHTMLのいずれかにおいてインプリメントされる一連のコンピュータプログラム命令を含み得る。ソースコードは、種々のデータ構造および通信メッセージを定義および使用し得る。ソースコードはコンピュータ実行可能な形態たとえば、インタプリタを介してであり得、あるいはソースコードはコンピュータ実行可能な形態に変換され得るたとえば、翻訳プログラムtranslator、アセンブラ、またはコンパイラを介して。コンピュータプログラムは、半導体メモリデバイスたとえば、RAM、ROM、PROM、EEPROM、またはフラッシュプログラム可能RAM、磁気メモリデバイスたとえばディスケットまたは固定ディスク、光メモリデバイスたとえば、CD-ROM、PCカードたとえば、PCMCIAカード、または他のメモリデバイスなどの有形の格納媒体において、永久的または一時的に、任意の形態たとえば、ソースコードの形態、コンピュータ実行可能な形態、または中間的な形態で固定され得る。コンピュータプログラムは、アナログテクノロジー、デジタルテクノロジー、光学テクノロジー、ワイヤレステクノロジーたとえば、Bluetooth、ネットワーキングテクノロジー、およびインターネットワーキングテクノロジーを含むが決してそれらに限定されない、種々の通信テクノロジーのいずれかを使用してコンピュータに送信可能な信号における任意の形態に固定され得る。コンピュータプログラムは、付随する印刷文書または電子文書とともに取り外し可能な格納媒体たとえば、シュリンクラップソフトウェアとして任意の形態で配布され得るか、コンピュータシステムたとえば、システムROMまたは固定ディスクの上に事前ロードされ得るか、または通信システムたとえば、インターネットまたはワールドワイドウェブを介してサーバまたは電子掲示板から配信され得る。本明細書中にこれまで記載された機能性のすべてまたは一部をインプリメントするハードウェア論理プログラム可能論理デバイスとともに使用するプログラマブルロジックを含むは、従来のマニュアル方法を使用して設計され得るか、あるいは計算機援用設計ComputerAidedDesignCAD、ハードウェア記述言語たとえば、VHDLまたはAHDL、またはPLDプログラミング言語たとえば、PALASM、ABEL、またはCUPLなどの種々のツールを使用して、設計、キャプチャ、シミュレーション、または電子的文書化をされ得る。プログラマブルロジックは、半導体メモリデバイスたとえば、RAM、ROM、PROM、EEPROM、またはフラッシュプログラム可能RAM、磁気メモリデバイスたとえば、ディスケットまたは固定ディスク、光メモリデバイスたとえば、CD-ROM、または他のメモリデバイスなどの、有形の格納媒体において、永久的または一時的に固定され得る。プログラマブルロジックは、アナログテクノロジー、デジタルテクノロジー、光学テクノロジー、ワイヤレステクノロジーたとえば、Bluetooth、ネットワーキングテクノロジー、およびインターネットワーキングテクノロジーを含むが決してそれらに限定されない、種々の通信テクノロジーのいずれかを使用してコンピュータに送信可能な信号に固定され得る。プログラマブルロジックは、付随する印刷文書または電子文書とともに取り外し可能な格納媒体たとえば、シュリンクラップshrinkwrappedソフトウェアとして配布され得るか、コンピュータシステムたとえば、システムROMまたは固定ディスクの上に事前ロードされ得るか、または通信システムたとえば、インターネットまたはワールドワイドウェブを介してサーバまたは電子掲示板から配信され得る。本出願は、以下の米国特許出願に関連し、それらは本明細書と同じ日付で出願され、参照によりそれらの全体が本明細書に援用されている:DynamicallyExpandableandContractibleFault-TolerantStorageSystemPermittingVariouslySizedStorageDevicesandMethodというタイトルの、代理人整理番号2950/103;DynamicallyUpgradeableFault-TolerantStorageSystemPermittingVariouslySizedStorageDevicesandMethodというタイトルの、代理人整理番号2950/104;およびStorageSystemConditionIndicatorandMethodというタイトルの、代理人整理番号2950/107。本発明は、本発明の真の範囲から逸脱することなく、他の特定の形において具体化され得る。記載された実施形態は、あらゆる点で、説明的なものとしてのみ考えられ、限定的なものとしては考えられない。"