説明

種々のサイズの格納デバイスを許容する動的にアップグレード可能な故障許容格納システムおよび方法

動的にアップグレード可能な故障許容格納システムは、格納デバイスがより大きな格納デバイスと置き換えられることを許容する。複数の格納デバイスにわたって冗長に格納されたデータは、置換用デバイスの上に複写され、置換用デバイスの上の追加の格納スペースは、追加データを冗長に格納するために利用可能にされる。格納デバイスのセットにおいてデータを格納する方法が提供され、該セットは少なくとも2つのデバイスを有し、該方法は、データ損失なしに、該デバイスのうちの第1のデバイスを、より大きな格納容量を有する置換用デバイスと置き換えることを可能にする。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、デジタルデータ格納システムおよび方法に関連し、より具体的には、故障許容格納を提供するシステムおよび方法に関連する。
【背景技術】
【0002】
種々のRAID(Redundant Array of Independent Disks)のいずれか一つに従って、一定のパターンの冗長ディスク格納を提供することは、従来技術において公知である。一般的に、RAIDパターンを使用したディスクアレイは、経験豊かな情報技術者による管理を必要とする複雑な構造である。さらに、RAIDパターンを使用した多くのアレイ設計において、アレイにおけるディスクドライブの容量が均一でない場合には、設計は、アレイにおける最小のドライブの容量を超えるドライブの上で、いかなる容量を使用することもでき得ない。
【0003】
標準的なRAIDシステムの一つの問題は、ディスクアレイのまれにしか使用されないエリアの上で、ディスク表面の破損が生じる可能性があることである。別のドライブが故障する場合には、破損が生じたことを決定することは必ずしも可能ではない。そのような場合には、破損されたデータは、RAIDアレイが故障したドライブを再構築するときに、伝播および保存され得る。
【0004】
多くの格納システムにおいて、スペアの格納デバイスが使用可能状態で維持されるので、別の格納デバイスが故障した場合にそれが使用され得る。そのようなスペアの格納デバイスは、しばしば「ホットスペア」と呼ばれる。ホットスペアは、格納システムの通常の作動中は、データを格納するようには使用されない。活動状態の格納デバイスが故障するときには、故障した格納デバイスはホットスペアと論理的に置き換えられ、データはホットスペアの上に移動されるかまたはさもなければ再作成される。故障した格納デバイスが修復されるかまたは置き換えられる場合には、データは一般的に、(再)作動させられた格納デバイスの上に移動させられるかまたはさもなければ再作成されるので、別の故障の場合にそれが容易に使用される。ホットスペアディスクの維持は一般的に複雑であるので、熟練した管理者によって一般的に処理される。ホットスペアディスクは、追加の費用をも意味する。
【発明の開示】
【課題を解決するための手段】
【0005】
(本発明の概要)
本発明の第1の実施形態において、格納デバイスのセットにおいてデータを格納する方法が提供され、該セットは、少なくとも2つのデバイスを有し、該方法は、データ損失なしに、該デバイスのうちの第1のデバイスを、より大きな格納容量を有する置換用デバイスと置き換えることを可能にする。該方法は、該格納デバイスのセットにデータを冗長に格納することと、該デバイスのうちの第1のデバイスを置換用デバイスによって置き換える際に、該セットの少なくとも一つの他のドライブの上に冗長に格納されたデータを使用して、該第1のデバイスの上に格納されたデータを、置換用デバイスの上に複写することと、少なくとも一つの冗長スキームを使用して、追加データが冗長に格納される態様で、該置換用ドライブの上の残りの格納容量を、該追加データの格納のために利用可能にすることとを含む。
【0006】
本発明の第2の実施形態において、格納システムが提供され、該格納システムは、種々の格納容量の格納デバイスを受け入れるための複数の格納デバイススロットと、該複数の格納デバイススロットに動作可能なように結合され、それに結合された格納デバイスのセットを管理するための、格納マネジャーとを備える。該格納マネジャーは、冗長的な態様で該格納デバイスのセットの上にデータを格納し、該デバイスのうちの第1のデバイスを、より大きな格納容量を有する置換用デバイスによって置き換える際に、該セットの他のドライブの上に冗長に格納されたデータを使用して、該第1のデバイスの上に格納されたデータを該置換用デバイスの上に複写し、該格納マネジャーはさらに、少なくとも一つの冗長スキームを使用して、追加データが冗長に格納される態様で、追加された格納容量を、該追加データの格納のために利用可能にする。
【0007】
関連する実施形態において、データは、冗長スキームの混合を使用して格納され得る。冗長スキームは、ミラリング、パリティを用いたストライピング、RAID6、二重パリティ、対角線パリティ、低密度パリティチェックコード、およびターボコードを含むグループから選択され得る。上記追加データに冗長性を提供するために十分な量の利用可能な格納容量を有するデバイスが他にない場合に、該追加データは、上記置換用デバイスの上の残りの上記格納容量の中に冗長に格納され得る(たとえば、ミラリングを使用して)か、あるいは、少なくとも一つの他のデバイスが、上記追加データに冗長性を提供するために十分な量の利用可能な格納容量を有する場合に、該追加データは、上記置換用デバイスを含む複数の格納デバイスにわたって冗長に格納され得る(たとえば、ミラリング、パリティを用いたストライピング、RAID6、二重パリティ、対角線パリティ、低密度パリティチェックコード、またはターボコードを使用して)。
【0008】
他の関連する実施形態において、上記格納デバイスのセットの第1の格納容量が示され得、該格納デバイスのセットは、該第1の格納容量よりも小さい実際の格納容量を提供し、該実際の格納容量の外側の場所にデータを格納するリクエストは、該実際の格納容量の中の場所にマッピングされ得る。リクエストされた場所を実際の場所にマッピングするルックアップテーブルを維持し、該実際の場所を得るために該リクエストされた場所に従ってルックアップテーブルに索引をつけることによって、該リクエストはマッピングされ得る。
【0009】
本発明の第3の実施形態において、複数の格納デバイスと、該複数の格納デバイスに動作可能なように結合された格納マネジャーとを備える、格納システムが提供される。該格納マネジャーは、該複数の格納デバイスにデータを冗長に格納し、第1の格納デバイスがより大きな格納容量の置換用格納デバイスに置き換えられたときに、該複数の格納デバイスにわたる既存のデータを自動的に再構成することにより、冗長性を少なくとも維持しオプションとして拡張し、該置換用格納デバイスによって提供される追加の格納容量を冗長な格納に利用可能にする。
【0010】
関連する実施形態において、上記格納マネジャーは、他の格納デバイスの上に冗長に格納されたデータを使用して、上記第1のデバイスの上に格納されたデータを、上記置換用デバイスの上に複写し得る。該格納マネジャーは、該置換用格納デバイスによって提供される追加の格納容量を使用して、データを再構成することによって、データの冗長性を拡張し得る。該格納マネジャーは、第1の冗長スキームのセットを使用してデータを格納し得、該第1の冗長スキームのセットとは異なり得る第2の冗長スキームのセットを使用してデータを再構成し得る。
【発明を実施するための最良の形態】
【0011】
本発明の前述の特徴は、添付の図面を参照して、以下の詳細な説明を参照することによって容易に理解される。
【0012】
(具体的な実施形態の詳細な説明)
定義。本明細書および添付の特許請求の範囲において使用されるように、文脈上特別な断りがない限り、以下の用語は指示された意味を有する。
【0013】
オブジェクトの「チャンク」は、オブジェクトの抽象スライスであり、使用される物理的格納とは無関係に作られ、一般的にオブジェクトの隣接バイトの固定数である。
【0014】
データ格納のための故障許容「パターン」は、データが一つ以上の格納デバイスにわたって冗長に分散される事項(particular)であり、なかでも、ミラリング(たとえばRAID1に類似した方法で)、ストライピング(たとえばRAID5に類似した方法で)、RAID6、二重パリティ、対角線パリティ、低密度パリティチェック(Low Density Parity Check)コード、ターボコード、または他の冗長スキーム、または冗長スキームの組み合わせであり得る。
【0015】
所定のチャンクのハッシュ数は、該所定のチャンクが任意の他のチャンクのハッシュ数とは一般的に異なるハッシュ数を生成するときに、該他のチャンクが該所定のチャンクと同一のデータコンテンツを有するときを除いて、「一意」である。すなわち、2つのチャンクは、それらのコンテンツが同一でないときはいつでも、異なるハッシュ数を一般的に有する。以下に詳細に説明されるように、「一意」という用語は、この文脈において、同一でないチャンクに対して共通ハッシュ数をたまに生成するハッシュ関数から生成されるハッシュ数をカバーするように使用される。なぜなら、ハッシュ関数は、異なるチャンクについて異なる数を生成することにおいて、一般的に完全ではないからである。
【0016】
「領域」は、格納媒体の上の隣接する物理ブロックのセットである(たとえばハードドライブ)。
【0017】
「ゾーン」は、2つ以上の領域からなる。ゾーンを構成する領域は、一般的に隣接することが要求されない。以下に説明される例示的な実施形態において、ゾーンは、1GBのデータまたは制御情報と等価なものを格納する。
【0018】
「クラスタ」は、ゾーンの中の単位サイズであり、圧縮(以下に説明される)の単位を表す。以下に説明される例示的な実施形態において、クラスタは、4KB(すなわち8つの512バイトセクタ)であり、本質的にチャンクと同じである。
【0019】
「冗長セット」は、データのセットに冗長性を提供するセクタ/クラスタのセットである。
【0020】
「領域をバックアップすること」は、一つの領域のコンテンツを別の領域にコピーすることを含む。
【0021】
格納デバイスの「第1のペア」および「第2のペア」は、共通格納デバイスを含み得る。
【0022】
「第1の複数の」および「第2の複数の」格納デバイスは、一つ以上の共通格納デバイスを含み得る。
【0023】
格納デバイスの「第1の配置」および「第2の配置」または「異なる配置」は、一つ以上の共通格納デバイスを含み得る。
【0024】
図1は、本発明の実施形態の図示であり、オブジェクト、この例においてはファイルが、格納のために一連のチャンクに分解される。最初に、ファイル11が格納ソフトウェアに渡され、そこでオブジェクト12として指定され、一意のオブジェクト識別番号、この場合は#007が割当てられる。新しいエントリ131は、オブジェクトテーブル13の中に作られ、この新しいオブジェクトの割当てを表す。オブジェクトは、今度はデータ121、122および123の「チャンク」に分解され、それらはオブジェクトの固定長セグメントである。各チャンクは、ハッシングアルゴリズムを通過させられ、ハッシングアルゴリズムはチャンクについて一意のハッシュ数を返す。このアルゴリズムは、リトライされたチャンクが格納されたチャンクと同一であることを保証するために、検索されたチャンクと、もともとのハッシュと比較された結果とに、後で適用され得る。各チャンクのハッシュ数は、後で完全なオブジェクトがチャンクの収集によって検索され得るように、オブジェクト132のエントリ行においてオブジェクトテーブル13の中に格納される。
【0025】
図1においてさらに、チャンクハッシュは、今度はチャンクテーブル14の中の既存のエントリと比較される。既存のエントリ141と一致する任意のハッシュは、すでに格納されているので、行動はとられない(すなわち、データは再び格納されず、オブジェクトの自動的圧縮につながる)。新しいハッシュ(チャンクテーブル14の中に対応するエントリがないハッシュ)は、チャンクテーブル141の中に入力される。チャンクにおけるデータは、次に、故障許容格納のために最も効率的な方法で、利用可能な格納デバイス151、152および153の上に格納される。このアプローチは、チャンクデータが、たとえば、一つまたは2つのデバイスからなる格納システムの上にミラリングされた方法で、または3つ以上の格納デバイスを用いてシステムの上でパリティストライピングされた方法で格納されることにつながり得る。このデータは、物理的位置1511、1521および1531において格納デバイスの上に格納され、チャンクのすべての物理的部分が後で場所を突き止められ検索され得るように、これらの位置および位置の番号は、チャンクテーブルの列143および142に格納される。
【0026】
図2は、より多くの格納デバイス(storage)の追加の結果として、チャンクのための故障許容格納のパターンがどのように動的に変化され得るかという同じ実施形態を示す。特に、図2は、追加の格納デバイスがシステム全体にひとたび追加されると、格納デバイスの上に物理的に格納されたチャンクが、新しいパターンにおいてどのようにレイアウトされ得るかを示す。図2aにおいて、格納システムは2つの格納デバイス221および222を備え、チャンクデータは、位置2211および2221において2つの格納デバイスの上に物理的にミラリングされ、故障許容を提供する。図2bにおいて、第3の格納デバイス223が追加され、チャンクをパリティストライピングした方法で格納することが可能になり、これは、ミラリングされたパターンよりも格納効率が良いパターンである。チャンクは、3つの物理的位置2311、2321および2331において、この新しいパターンにレイアウトされ、利用可能な格納デバイスにとる割合がはるかに低い。チャンクテーブル21はアップデートされて、新しいレイアウトが3つの位置212にすることと、新しいチャンクの物理的位置2311、2321および2331が213に記録されていることをも示す。
【0027】
図3は、本発明の実施形態による、完成された(mature)格納システムを示し、ある期間にわたって機能していた。これは、可変格納容量を有する格納デバイスの上で、チャンクが、時間を経てどのように物理的に格納され得るかを図示する。この図は、40GB格納デバイス31と、80GB格納デバイス32と、120GB格納デバイス33とからなる格納システムを示す。最初に、チャンクは、40GB格納デバイス31が満杯になるまで、故障許容ストライプパターン34で格納される。次に、格納スペースの欠如のために、新しいデータは、80GB格納デバイス32および120GB格納デバイス33の上の利用可能なスペースの上に、ミラリングされたパターン36で格納される。80GB格納デバイス32がひとたび満杯になると、次に、新しいデータは単一のディスク故障許容パターン37でレイアウトされる。たとえ格納デバイスがデータ格納のための単一のプールを備えていても、チャンクにおいて格納されたようなデータそのものは、種々の別個のパターンで格納されている。
【0028】
図4は、本発明の別の実施形態を図示し、非効率的な格納デバイスの使用と、故障許容の低いレベルとを警告するために、インジケータ状態が使用される。図4aにおいて、すべての3つの格納デバイス41、42および45は使用されていないスペースを有しており、効率的で故障許容の方法でデータが格納されていることを示すために、インジケータライト44は緑色である。図4bにおいて、40GB格納デバイス41は満杯になったので、新しいデータは、ミラリングされた冗長パターン46で、使用されていない残りのスペースを用いて2つの格納デバイス42および43の上のみに格納され得る。データは完全に冗長ではあるが、効率的に格納されていないことを示すために、インジケータライト44は琥珀色に変わった。図4cにおいて、120GB格納デバイス43のみが使用されていない残りのスペースを有しているので、すべての新しいデータは、この一つのデバイス43の上でミラリングされたパターンのみで格納され得る。故障許容はよりロバスト(robust)でなくなり、システムはスペースが非常に足りなくなっているので、より多くの格納デバイスの追加が必要であることを示すために、インジケータライト44は赤色に変わる。
【0029】
一つの代替的な実施形態において、アレイにおけるそれぞれのドライブ/スロットに、たとえば3色(たとえば緑色、黄色、赤色)の形で、インジケータが提供される。一つの特定の実施形態において、ライトは、光る効果でディスクキャリアの前面全体を照らすように使用される。ライトは、システムの全体的な状態のみならず、(もしあれば)どのドライブ/スロットが注意を必要としているかを示すように制御される。それぞれの3色ライトは、少なくとも4つの状態に置かれ得、具体的には、オフ、緑色、黄色、赤色である。スロットが空であり、システムが十分な格納デバイスと冗長性をもって作動しているために、スロットにドライブがインストールされる必要がない場合には、特定のスロットのためのライトは、オフ状態に置かれ得る。特定のスロットのためのライトは、対応するドライブが十分であり、置き換えられる必要がない場合には、緑色状態に置かれ得る。特定のスロットのためのライトは、対応するドライブをより大きなドライブに置き換えることが推奨されるようにシステム操作が低下する場合には、黄色の状態に置かれ得る。特定のスロットのためのライトは、対応するドライブをインストールまたは置き換えなければならない場合には、赤色の状態に置かれ得る。必要または要求に応じて、たとえば、オンとオフとの状態の間でライトをフラッシュさせることによって、または2つの異なる色の間でライトをフラッシュさせる(たとえば、ドライブが置き換えられた後に、データの再レイアウトが進行中であるときに、赤色と緑色との間でフラッシュさせる)ことによって、追加の状態が示され得る。例示的な実施形態のさらなる詳細が、以下に説明される。
【0030】
もちろん、システム状態とドライブ/スロット状態との両方を示すために、他の指示技術が使用され得る。たとえば、システム状態と、必要な場合には、注意を必要とするスロット番号とを示すために、LCDディスプレイが使用され得る。さらに、他の種類のインジケータ(たとえば、スロットインジケータまたは各スロット用のライトとともに、システムのための単一の状態インジケータ(たとえば緑色/黄色/赤色))が使用され得る。
【0031】
図5は、図1〜3に関連して上述されたような、本発明の実施形態に従ったデータの格納、検索および再レイアウトにおいて使用される機能モジュールのブロック図である。通信のための入口点および出口点は、オブジェクトの格納または検索のためにオブジェクトをシステムに渡すオブジェクトインタフェース511と、格納システムを一つの大きな格納デバイスであるように見せるブロックインタフェース512と、格納システムをWindows(登録商標)ファイルシステムであるように見せるCIFSインタフェース513とである。これらのインタフェースがデータの格納を要求するとき、データはチャンクパーサ(Chunk Parser)52に渡され、チャンクパーサは、データのチャンクへの分解を実行し、オブジェクトテーブル512への最初のエントリを生成する(図1に関連して上述されたように)。これらのチャンクは、次にハッシュコード生成器53に渡され、ハッシュコード生成器は各チャンクについて関連するハッシュコードを生成し、それらをオブジェクトテーブルに入力するので、各オブジェクトに関連するチャンクは512で列挙される(図1に関連して上述されたように)。チャンクハッシュ数は、チャンクテーブル531におけるエントリと比較される。一致が見出された場合には、新しいチャンクは、格納システムにすでに格納されたチャンクと同一であるので、捨てられる。チャンクが新しい場合には、そのための新しいエントリがチャンクテーブル531の中に作成され、ハッシュされたチャンクは物理的格納マネジャー54に渡される。物理的格納マネジャーは、利用可能な格納デバイス571、572および573の上で可能な最も効率的なパターンでチャンクを格納して、チャンクのコンテンツが後で512で検索され得るように(図1に関連して上述されたように)、チャンクの物理的格納がどこで発生したかを示すために、チャンクテーブル531の中に対応するエントリを作成する。
【0032】
オブジェクトインタフェース511、ブロックインタフェース512、またはCIFSインタフェース513による、図5におけるデータの検索は、検索マネジャー56に対するリクエストによって実行され、検索マネジャーは、どのチャンクがオブジェクトを含むかを決定するためにオブジェクトテーブル521を調べ、次にこれらのチャンクを物理的格納マネジャー54から要求する。物理的格納マネジャー54は、要求されたチャンクがどこに格納されているかを決定するためにチャンクテーブル531を調べ、次にそれらを検索し、完了したデータ(オブジェクト)を検索マネジャー56に返し、検索マネジャーは、要求しているインタフェースにデータを返す。図5には、故障許容マネジャー(FTL)55も含まれ、チャンクが可能な最も効率的な方法で格納されているかどうかを決定するために、絶えずチャンクテーブルをスキャンする。(格納デバイス571、572および573が追加されたり取り外されたりすると、これらは変化し得る。)チャンクが可能な最も効率的な方法で格納されていない場合には、FTLは、物理的格納マネジャー54に、チャンクについて新しいレイアウトパターンを作成し、チャンクテーブル531をアップデートするように、要求する。このようにして、すべてのデータは、アレイを含む格納デバイスの数について可能な最も効率的な方法で格納されたままでいる(図2および3に関連して上述されたように)。
【0033】
以下は、本発明の例示的な実施形態のさらなる詳細を提供する。
【0034】
(データレイアウトスキーム−ゾーン)
なかでも、ゾーンは、ディスクの上に格納されている実際のデータから、冗長性とディスク再レイアウトとを隠す効果を有する。ゾーンは、ゾーンのユーザに影響することなく、追加のレイアウト方法が追加および変更されることを可能にする。
【0035】
格納アレイは、ゾーンと呼ばれる仮想セクションにおけるディスクの上で、データをレイアウトする。ゾーンは、所定および固定の量(たとえば1Gバイト)のデータを格納する。ゾーンは、単一のディスクの上に存在し得るか、あるいは一つ以上のドライブにわたってまたがり得る。ゾーンの物理的レイアウトは、そのゾーンについて指定された形で冗長性を提供する。
【0036】
図6は、2つ以上のドライブを含むアレイにおいてミラリングが使用される例を示す。図7は、データを格納するために異なるレイアウトスキームを使用するいくつかの例示的なゾーンを示す。図は、ゾーンが1GBのデータを格納することを想定する。以下の点に留意されたい。
i)複数のドライブにまたがるゾーンは、セットにわたるドライブの中に同じオフセットを必ずしも使用しない。
ii)単一ドライブミラリングは、1Gのデータを格納するために2Gの格納デバイスを必要とする。
iii)二重ドライブミラリングは、1Gのデータを格納するために2Gの格納デバイスを必要とする。
iv)3つのドライブストライピングは、1Gのデータを格納するために1.5Gの格納デバイスを必要とする。
v)4つのドライブストライピングは、1Gのデータを格納するために1.33Gの格納デバイスを必要とする。
vi)ゾーンA、ゾーンBなどは、任意のゾーン名である。実際のインプリメンテーションにおいて、それぞれのゾーンは一意の数によって識別され得る。
vii)図によって暗示されるものの、ゾーンは必ずしもディスクの上で隣接しない(後で領域を参照)。
viii)ミラリングが2つのドライブに制約される技術的理由はない。たとえば、3ドライブシステムにおいて、データの一つのコピーが一つのドライブの上に格納され得、ミラリングされたデータの半分が他の2つのドライブのそれぞれの上に格納され得る。同様に、データは3つのドライブにわたってミラリングされ得、データの半分が2つのドライブのそれぞれの上にミラリングされ、ミラリングの半分が他の2つのドライブの上にミラリングされる。
【0037】
(データレイアウトスキーム−領域)
各ディスクは、均等なサイズの領域に分割される。領域のサイズはゾーンよりもはるかに小さく、ゾーンは一つ以上のディスクからの一つ以上の領域から構築される。ディスクスペースの効率的な使用のために、領域のサイズは一般的に、異なるゾーンサイズと、アレイによってサポートされる異なる数のディスクとの共通因子である。例示的な実施形態において、領域はゾーンの1/12のデータサイズである。以下の表は、本発明の例示的な実施形態に従って、種々のレイアウトについての、領域/ゾーンの数と、領域/ディスクの数とを列挙する。
【0038】
【表1−1】

【0039】
【表1−2】

個々の領域は、使用済み、使用されていない、または不良としてマークされ得る。ゾーンが作成されるときには、適切なディスクから使用されていない領域のセットが、テーブルにおいて選択されログをとられる。これらの領域は、任意の順序であり得、ディスクの上で隣接する必要はない。データがゾーンに書き込まれるかまたはゾーンから読み取られるときには、アクセスは適切な領域にリダイレクトされる。なかでも、このことは、データの再レイアウトが柔軟かつ効率的な方法で生ずることを可能にする。時間を経て、異なるサイズのゾーンは、おそらく断片化を発生させ、小さすぎて完全なゾーンを保持できない多くのディスクエリアを残す。適切な領域サイズを使用することによって、断片化によって残されたすべてのギャップは、サイズにおいて少なくとも一つの領域になり、ディスク全体を断片化解消(de−fragment)する必要なしに、これらの小さなギャップの容易な再使用を可能にする。
【0040】
(データレイアウトスキーム−再レイアウト)
インプリメンテーションを容易にするために、固定シーケンスの拡張および縮小が強化され得る。たとえば、2つのドライブが急に追加される場合には、第2のドライブを組み込むために第2の拡張が実行される前に、あたかも一つのドライブが追加されたかのように、ゾーンの拡張が中間の拡張を経由し得る。代替的には、複数のドライブを含む拡張および縮小は、中間のステップなしに、アトミックに(atomically)処理され得る。
【0041】
任意の再レイアウトが生じる前に、必要とされるスペースが利用可能でなければならない。このことは、不必要な再レイアウトが生じないことを確実にするために、再レイアウトを始める前に計算されるべきである。
【0042】
(レイアウトスキーム−ドライブ拡張)
以下は、本発明の例示的な実施形態に従って、単一ドライブミラリングから二重ドライブミラリングに拡張する一般的なプロセスを説明する。
i)単一ドライブミラリングが、データ「A」とミラリング「B」とを有すると想定する。
ii)ゾーンを「C」へと拡張するために、ドライブの上に12の領域を割当てる。
iii)ミラリング「B」を領域セット「C」にコピーする。
iv)すでにコピーされたデータへのいかなる書き込みも、「C」における適切な場所にミラリングされなければならない。
v)コピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、「B」へのポインタを「C」へのポインタに置き換える。
vi)「B」を構成する領域を、使用されていないとしてマークする。
【0043】
以下は、本発明の例示的な実施形態に従って二重ドライブミラリングからパリティを用いた三重ドライブストライピングへと拡張する、一般的なプロセスを説明する。
i)一つのドライブがデータ「A」を有し、第2のドライブがミラリング「B」を有すると想定する。
ii)パリティ情報「C」のために、第3のドライブの上に6つの領域を割当てる。
iii)「A」の第1の6領域と、「B」の第2の6領域とを使用して、パリティ情報を計算する。
iv)「C」にパリティ情報を置く。
v)すでに処理されたデータになされたいかなる書き込みも、「C」における適切な場所にパリティされなければならない。
vi)コピーが完了したら、新しいレイアウトタイプのポイントテーブルを用いて、ゾーンテーブルを、「A」の第1の半分と、「B」の第2の半分と、「C」とにアップデートする。
vii)「A」の第2の半分と「B」の第1の半分とを、使用されていないとしてマークする。
【0044】
以下は、本発明の例示的な実施形態に従って三重ドライブストライピングからパリティを用いた四重ドライブストライピングに拡張する、一般的なプロセスを説明する。
i)一つのドライブがデータ「A」を有し、第2のドライブがデータ「B」を有し、第3のドライブがパリティ「P」を有すると想定する。
ii)ストライピングデータ「C」のために、第4のドライブの上に4つの領域を割当てる。
iii)「A」の最後の2領域を、「C」の最初の2領域にコピーする。
iv)「B」の最初の2領域を、「C」の最後の2領域にコピーする。
v)パリティドライブ「D」の上に4つの領域を割当てる。
vi)Aの最初の4領域と、Cと、Bの最後の4領域とを使用して、パリティ情報を計算する。
vii)パリティ情報を「D」に置く。
viii)すでに処理されたデータへのいかなる書き込みも、「D」における適切な場所にパリティされなければならない。
ix)新しいレイアウトタイプとポイントテーブルとを用いて、ゾーンテーブルを、「A」の第1の4領域と、「C」と、「B」の第2の4領域と、「D」とにアップデートする。
x)「A」の最後の2領域と、「B」の最初の2領域を、使用されていないとしてマークする。
【0045】
(データレイアウトスキーム−ドライブ縮小)
ドライブ縮小は、ディスクが取り外されるかまたは故障するときに発生する。そのような場合には、アレイは、可能であればすべてのゾーンを冗長状態に戻すために、データを縮小する。ドライブ縮小は、拡張よりもやや複雑である。なぜなら、より多くの選択がなされるべきだからである。しかし、レイアウト方法の間の移行は、拡張と同様の方法で生じるが、逆の順序である。再生されるべきデータの量を最小限に保つことは、冗長性が可能な限り迅速に達成されることを可能にする。ドライブ縮小は、すべてのゾーンが再レイアウトされるまで、スペースが利用可能である間に、一般的に一度に1ゾーン先行する。一般的に言って、取り外されたかまたは故障したディスクの上に存在するデータのみが再構築される。
【0046】
(どのように縮小するかの選択)
以下の表は、本発明の例示的な実施形態に従って、再レイアウトされる必要のある各ゾーンについての決定ツリーを説明する:
【0047】
【表2−1】

【0048】
【表2−2】

以下は、本発明の例示的な実施形態に従って、二重ドライブミラリングから単一ドライブミラリングに縮小する一般的なプロセスを説明する。
i)単一ドライブミラリングが、データ「A」と欠いているミラリング「B」とを有するか、またはその逆であると仮定する。
ii)「A」を「C」として含むドライブの上に12の領域を割当てる。
iii)データ「A」を領域セット「C」にコピーする。
iv)すでにコピーされたデータへのいかなる書き込みも、「C」における適切な場所にミラリングされなければならない。
v)コピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、「B」へのポインタを「C」へのポインタに置き換える。
【0049】
以下は、本発明の例示的な実施形態に従って、三重ドライブストライピングから二重ドライブミラリングに縮小する一般的なプロセスを説明する(パリティを欠いている)。
i)ストライピングは、異なるドライブの上のデータブロック「A」、「B」および「C」からなると想定する。パリティ「C」が欠けている。
ii)「A」をゾーンの第1の半分を含むものとして定義し、「B」をゾーンの第2の半分を含むものとして定義する。
iii)「A」ドライブの上に6つの領域「D」を割当て、「B」ドライブの上に6つの領域「E」を割当てる。
iv)「A」を「E」にコピーする。
v)「B」を「D」にコピーする。すでにコピーされたデータへのいかなる書き込みも、「D」および「E」における適切な場所にミラリングされなければならない。
vii)コピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、「A」/「D」および「E」/「B」へのポインタを設定する。
【0050】
以下は、本発明の例示的な実施形態に従って、三重ドライブストライピングから二重ドライブミラリングに縮小する一般的なプロセスを説明する(データを欠いている)。
i)ストライピングは、異なるドライブの上のデータブロック「A」、「B」および「C」からなると想定する。データ「C」が欠けている。
ii)「A」をゾーンの第1の半分を含むものとして定義し、「C」をゾーンの第2の半分を含むものとして定義する。
iii)「A」ドライブの上に6つの領域「D」を割当て、「B」ドライブの上に12の領域「E」を割当てる。
iv)「A」を「E」の第1の半分にコピーする。
v)「A」および「B」から、欠けているデータを再構築する。データを「D」に書き込む。
vi)「D」を「E」の第2の半分にコピーする。
vii)すでにコピーされたデータへのいかなる書き込みも、「D」および「E」における適切な場所にミラリングされなければならない。
viii)コピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、「A」/「D」および「E」へのポインタを設定する。
ix)「B」領域を、使用されていないとしてマークする。
【0051】
以下は、本発明の例示的な実施形態に従って、四重ドライブストライピングから三重ドライブストライピングに縮小する一般的なプロセスを説明する(パリティを欠いている)。
i)ストライピングは、異なるドライブの上のデータブロック「A」、「B」、「C」および「D」からなると仮定する。パリティ「D」が欠けている。
ii)「A」をゾーンの第1の3分の1を含むものとして定義し、「B」を第2の3分の1を含むものとして定義し、「C」を第3の3分の1を含むものとして定義する。
iii)「A」ドライブの上に2領域「G」を割当て、「C」ドライブの上に2領域「E」を割当て、「B」ドライブの上に6領域「F」を割当てる。
iv)「B」の第1の半分を「G」にコピーする。
v)「B」の第2の半分を「E」にコピーする。
vi)「A」/「G」および「E」/「C」からパリティを構築し、「F」に書き込む。
vii)すでにコピーされたデータへのいかなる書き込みも、「G」、「E」および「F」における適切な場所にミラリングされなければならない。
viii)コピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、「A」/「G」、「E」/「C」、および「F」へのポインタを設定する。
ix)「B」領域を、使用されていないとしてマークする。
【0052】
以下は、本発明の例示的な実施形態に従って、四重のドライブストライピングから三重のドライブストライピングに縮小する一般的なプロセスを説明する(最初の1/3を欠いている)。
i)ストライピングは、異なるドライブの上のデータブロック「A」、「B」、「C」および「D」からなると想定する。データ「A」が欠けている。
ii)「A」をゾーンの第1の3分の1を含むものとして定義し、「B」を第2の3分の1を含むものとして定義し、「C」を第3の3分の1を含むものとして定義し、「D」をパリティを含むものとして定義する。
iii)「B」ドライブの上に4領域「E」を割当て、「C」ドライブの上に2領域「F」を割当て、「D」ドライブの上に6領域「G」を割当てる。
iv)「B」の第2の半分を「F」にコピーする。
v)「B」、「C」および「D」から、欠けているデータを構築し、「E」に書き込む。
vi)「E」/「Bの第1の半分」と、「F」/「C」とから新しいパリティを構築し、「G」に書き込む。
vii)すでにコピーされたデータへのいかなる書き込みも、「B」、「E」、「F」および「G」における適切な場所にミラリングされなければならない。
viii)コピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、「E」/「Bの第1の半分」、「F」/「C」、および「G」へのポインタを設定する。
ix)「B」の第2の半分および「D」の領域を、使用されていないとしてマークする。
【0053】
以下は、本発明の例示的な実施形態に従って、四重のドライブストライピングから三重のドライブストライピングに縮小する一般的なプロセスを説明する(第2の1/3を欠いている)。
i)ストライピングは、異なるドライブの上のデータブロック「A」、「B」、「C」および「D」からなると想定する。データ「B」が欠けている。
ii)「A」をゾーンの第1の3分の1を含むものとして定義し、「B」を第2の3分の1を含むものとして定義し、「C」を第3の3分の1を含むものとして定義し、「D」をパリティを含むものとして定義する。
iii)「A」ドライブの上に2領域「E」を割当て、「C」ドライブの上に2領域「F」を割当て、「D」ドライブの上に6領域「G」を割当てる。
iv)「A」の第1の半分、「C」の第1の半分、および「D」の第1の半分から、欠けているデータを構築し、「E」に書き込む。
v)「A」の第2の半分、「C」の第2の半分、および「D」の第2の半分から、欠けているデータを構築し、「F」に書き込む。
vi)「A」/「E」および「F」/「C」から新しいパリティを構築し、「G」に書き込む。
vii)すでにコピーされたデータへのいかなる書き込みも、「E」、「F」および「G」における適切な場所にミラリングされなければならない。
viii)コピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、「E」、「F」および「G」へのポインタを設定する。
ix)「D」領域を、使用されていないとしてマークする。
【0054】
以下は、本発明の例示的な実施形態に従って、四重のドライブストライピングから三重のドライブストライピングへの縮小の一般的なプロセスを説明する(第3の1/3を欠いている)。
i)ストライピングは、異なるドライブの上のデータブロック「A」、「B」、「C」および「D」からなると想定する。データ「C」が欠けている。
ii)「A」をゾーンの第1の3分の1を含むものとして定義し、「B」を第2の3分の1を含むものとして定義し、「C」を第3の3分の1を含むものとして定義し、「D」をパリティを含むものとして定義する。
iii)「A」ドライブの上に2領域「E」を割当て、「B」ドライブの上に4領域「F」を割当て、「D」ドライブの上に6領域「G」を割当てる。
iv)「B」の第1の半分を「E」にコピーする。
v)「A」、「B」および「D」から、欠けているデータを構築し、「F」に書き込む。
vi)「A」/「E」と、「B」/「F」の第2の半分とから新しいパリティを構築し、「G」に書き込む。
vii)すでにコピーされたデータへのいかなる書き込みも、「E」、「F」および「G」における適切な場所にミラリングされなければならない。
viii)コピーが完了したら、新しいレイアウトタイプを用いてゾーンテーブルをアップデートし、「A」/「E」、「B」/「F」の第2の半分、および「G」へのポインタを設定する。
ix)「B」の第1の半分および「D」を、使用されていないとしてマークする。
【0055】
たとえば、図3を再び参照して、ドライブ0またはドライブ1のいずれかが失われた場合には、ドライブ2の上に十分な利用可能なスペースがあるという条件で、二重ドライブミラリング(ゾーンB)はドライブ2の上で再構築され得る。同様に、ドライブ0〜2のいずれかが失われた場合には、ドライブ3の上に十分な利用可能なスペースがあるという条件で、ドライブストライピング(ゾーンC)は、ドライブ3を利用して再構築され得る。
【0056】
(データレイアウトスキーム−ゾーン再構築)
ゾーン再構築は、ドライブが取り外されて、理想的なゾーン再レイアウトのために残りのドライブの上に十分なスペースがあるとき、あるいはドライブがより大きなサイズの新しいドライブと置き換えられたときに、生じる。
【0057】
以下は、本発明の例示的な実施形態に従って、二重ドライブミラリングの再構築の一般的なプロセスを説明する。
i)単一ドライブミラリングが、データ「A」と欠けているミラリング「B」とを有すると想定する。
ii)「A」を含むドライブ以外のドライブの上に12の領域「C」を割当てる。
iii)データ「A」を「C」にコピーする。
iv)すでにコピーされたデータへのいかなる書き込みも、「C」における適切な場所にミラリングされなければならない。
v)コピーが完了したら、ゾーンテーブルをアップデートし、「B」へのポインタを「C」へのポインタにアップデートする。
【0058】
以下は、本発明の例示的な実施形態に従って、三重ドライブストライピングの再構築の一般的なプロセスを説明する。
i)一つのドライブがデータ「A」を有し、第2のドライブがデータ「B」を有し、第3のドライブがパリティ「P」を有すると想定する。「B」が欠けている。どの断片が欠けているかは問題ではなく、必要とされる行動はすべての場合において同じであることに留意されたい。
ii)「A」および「P」を含むドライブ以外のドライブの上に、6つの領域「D」を割当てる。
iii)「A」および「P」から、欠けているデータを構築する。データを「D」に書き込む。
iv)すでに処理されたデータへのいかなる書き込みも、「D」における適切な場所にパリティされなければならない。
v)「B」へのポインタを「D」へのポインタに置き換えることによって、ゾーンテーブルをアップデートする。
【0059】
この例示的な実施形態において、取り外されたドライブが別のドライブと置き換えられる場合に、4ドライブ再構築のみが生じる。再構築は、新しいドライブの上に6つの領域を割当てることと、他の3つの領域セットから、欠けているデータを再構築することとからなる。
【0060】
(データレイアウトスキーム−一時的に欠けるドライブの問題)
ドライブが取り外されて、再レイアウトのための余地がないときには、古いドライブが再び取り付けられるか、またはドライブが新しいドライブと置き換えられるまで、アレイは劣化したモードで作動し続ける。新しいドライブが取り付けられる場合には、ドライブセットが再構築されるべきである。この場合には、データが再レイアウトされる。古いディスクがアレイの中に戻して置かれる場合には、それはもはや現在のディスクセットの一部ではなく、新しいディスクとしてみなされる。しかし、新しいディスクがアレイに置かれるのではなく、古いディスクが戻される場合には、古いディスクは、たとえ古いメンバであろうとも、やはりディスクセットのメンバであるとして認識される。この場合には、すでに再レイアウトされた任意のゾーンが新しい構成を保ち、古いディスクの上の領域は解放される。再レイアウトされていない任意のゾーンは、やはり古いディスクの適切な領域をポインティングする。しかし、劣化したゾーンに何らかの書き込みが実行され得た場合には、これらのゾーンはリフレッシュされる必要がある。生じたすべての書き込みのログをとるのではなく、変更された劣化領域はマークされ得る。このようにして、ディスクが置き換えられるときには、変更された領域のみがリフレッシュされる必要がある。
【0061】
さらに、書き込まれたゾーンは、再レイアウトのための優先リストにさらに置かれ得る。このことは、ディスクが置き換えられた場合に、リフレッシュされる必要がある領域の数を低減し得る。タイムアウトも使用され得、その時点の後で、ディスクはたとえ置き換えられても消去される(wiped)。しかし、このタイムアウトは非常に大きくあり得、場合によると数分ではなく数時間である。
【0062】
(データレイアウトスキーム−データ保全性)
上述のように、標準的なRAIDシステムの一つの問題は、ディスクアレイのまれにしか使用されないエリアの上で、ディスク表面の破損が生じる可能性があることである。別のドライブが故障する場合には、破損が生じたことを決定することは必ずしも可能ではない。そのような場合には、RAIDアレイが故障したドライブを再構築するときに、破損したデータが伝播され保存され得る。
【0063】
上述のハッシュメカニズムは、RAIDのもとで利用可能なメカニズムにわたってデータ破損検出の追加のメカニズムを提供する。他の場合に述べられるように、チャンクが格納されるときに、そのチャンクについて、ハッシュ値が計算され格納される。チャンクが読み出されるときはいつでも、検索されたチャンクについてのハッシュ値が計算され得、格納されたハッシュ値と比較され得る。ハッシュ値が一致しない場合には(破損したチャンクを示し)、チャンクデータは冗長データから回復され得る。
【0064】
ディスクの上のデータ破損が生じ得る時間窓(time window)を最小化するために、破損したデータを可能な限り速やかに発見し修正するように、ディスクの定期的なスキャンが実行される。それは、オプションとして、アレイからの読み出しにおいてチェックが実行されることをも可能にする。
【0065】
(データレイアウトスキーム−ボリューム)
スパースボリューム(sparse volume)において、アレイにおけるディスクの上で利用可能な格納スペースの量に関わりなく、アレイは固定サイズ(たとえばMテラバイト)であることをつねに求める。アレイはSバイトの実際の格納スペースを含み、ここでS<=Mであり、データは、Mテラバイトのスペースの中の位置L1、L2、L3などに格納されるように要求され得ると仮定する。要求された位置Ln>Sである場合には、Lnのためのデータは、位置Pn<Sに格納されなければならない。このことは、図8に示されるように、Lnに基づいてインデックスPnに対するルックアップテーブルを含むことによって管理される。この特徴は、Windows(登録商標)、Linux(登録商標)およびApple(登録商標)のオペレーティングシステムなどの、ボリューム拡張をサポートしないオペレーティングシステムとともに、アレイが作動することを可能にする。さらに、アレイは、複数のスパースボリュームを提供し得、そのすべては同一の物理格納を共有する。それぞれのスパースボリュームは、専用のルックアップテーブルを有するが、データ格納のために同一の物理スペースを共有する。
【0066】
(ドライブスロットインジケータ)
上述のように、格納アレイは一つ以上のドライブスロットからなる。それぞれのドライブスロットは、空であり得るか、またはハードディスクドライブを含み得る。それぞれのドライブスロットは、4つの状態を示す能力のある専用インジケータを有する。すなわち、オフ、OK、劣化、および故障である。状態は、一般的に以下のように解釈される:
【0067】
【表3】

この例示的な実施形態において、赤色/琥珀色/緑色の発光ダイオード(LED)がインジケータとして使用される。LEDは、一般的に以下のように解釈される:
【0068】
【表4】

図9は、本発明の例示的な実施形態に従った、利用可能な格納スペースを有し、故障許容方法において作動する、例示的なアレイを示す。スロットB、CおよびDには、格納デバイスが配置され、追加のデータを冗長に格納するために利用可能な十分な格納スペースがある。スロットB、CおよびDのインジケータは緑色であり(これらの格納デバイスが正しく作動しており、アレイデータが冗長であり、アレイが利用可能なディスクスペースを有することを示す)、スロットAのインジケータはオフである(格納デバイスをスロットAに配置する必要がないことを示す)。
【0069】
図10は、本発明の例示的な実施形態に従った、冗長データ格納を維持するために十分なスペースを有せず、より多くのスペースが追加されなければならない、例示的なアレイを示す。スロットB、CおよびDには、格納デバイスが配置される。スロットCおよびDにおける格納デバイスは満杯である。スロットB、CおよびDのインジケータは緑色であり(これらの格納デバイスが正しく作動していることを示す)、スロットAのインジケータは赤色である(アレイが、冗長データ格納を維持するための十分なスペースを有せず、スロットAに格納デバイスが配置されるべきであることを示す)。
【0070】
図11は、本発明の例示的な実施形態に従った、故障の場合に冗長データを維持することができなくあり得る、例示的なアレイを示す。スロットA、B、CおよびDには、格納デバイスが配置される。スロットCおよびDにおける格納デバイスは満杯である。スロットA、BおよびCのインジケータは緑色であり(アレイが正しく作動していることを示す)、スロットDのインジケータは琥珀色である(スロットDにおける格納デバイスが、より大きな格納容量を有する格納デバイスに置き換えられるべきであることを示す)。
【0071】
図12は、本発明の例示的な実施形態に従った、格納デバイスが故障した例示的なアレイを示す。スロットB、CおよびDには、格納デバイスが配置される。スロットCにおける格納デバイスが故障した。スロットBおよびDのインジケータは緑色であり(これらが正しく作動していることを示す)、スロットCのインジケータは赤色であり(スロットCにおける格納デバイスが置き換えられるべきであることを示す)、スロットAのインジケータはオフである(格納デバイスがスロットAに配置される必要がないことを示す)。
【0072】
以下は、本発明の例示的な実施形態のためのソフトウェア設計の説明である。ソフトウェア設計は、6つのソフトウェアレイヤに基づき、ソフトウェアレイヤは、ディスクに物理的にアクセスすることから、ホストコンピューティングシステムと通信することまでの、論理アーキテクチャにわたる。
【0073】
この例示的な実施形態において、ファイルシステムは、Windows(登録商標)、Linux(登録商標)またはApple(登録商標)などのホストサーバに常駐し、USBデバイスまたはiSCSIデバイスとして格納アレイにアクセスする。ホストインタフェースを介して到着する物理的ディスクリクエストは、ホストリクエストマネジャー(Host Request Manager)(HRM)によって処理される。ホストI/Oインタフェースは、ホストに対するホストUSBまたはiSCSIインタフェースのプレゼンテーションを調整し(coordinate)、HRMとインタフェースする。HRMは、ホストI/Oインタフェースからのデータ読み出し/書き込みリクエストを調整し、読み出しおよび書き込みリクエストをタスク指名し、これらのリクエストが完了したときに、これらのリクエストのホストへの回収(retiring)を調整する。
【0074】
格納アレイの何よりも重要な目的は、ひとたびデータがシステムによって受け入れられると、システムが現在格納する冗長性の最大量を利用して、データが確実な方法で格納されることを保証することである。アレイが物理的構成を変化させると、データは冗長性を維持する(さらに場合によると最大化する)ために再編成される。さらに、使用される格納量を低減するために、単純なハッシュに基づいた圧縮が使用される。
【0075】
最も基本的なレイヤは、データを異なるディスクに格納するディスクドライバからなる。ディスクは、USBインタフェースを介して通り抜けた(tunneled)ATAなどの種々のインタフェースを介して接続され得る。
【0076】
ディスクの上のセクタは、領域、ゾーン、およびクラスタに編成され、それぞれが異なる論理的役割を有する。
【0077】
領域は、ディスクの上の隣接する物理ブロックのセットを表す。4ドライブシステムにおいて、それぞれの領域は、サイズが1/12GBであり、冗長性の最小単位を表す。領域の中のセクタが物理的に損傷していることがわかった場合は、領域全体が放棄される。
【0078】
ゾーンは、冗長性の単位を表す。ゾーンは、適切な量の冗長性を提供するために、場合により異なるディスクの上の、多数の領域からなる。ゾーンは、1GBのデータ容量を提供するが、冗長性を提供するためにより多くの領域を要求し得る。冗長性のない1GBは、1セットの12領域(1GB)を要求する;1GBのミラリングされたゾーンは、2セットの1GB領域(24領域)を要求する;1GBの3ディスクストライピングされたゾーンは、3セットの0.5GB領域(18領域)を要求する。異なるゾーンは、異なる冗長特性を有する。
【0079】
クラスタは、圧縮の基本単位を表し、ゾーンの中の単位サイズである。クラスタのサイズは現在4KB、すなわち8×512バイトセクタである。ディスクの上の多くのクラスタは、おそらく同じデータを含む。クラスタアクセステーブル(CAT)は、ハッシュ関数を介してクラスタの利用を追跡するために使用される。CATは、論理ホストアドレスと、ゾーンにおける適切なクラスタの位置との間の変換をする。
【0080】
ディスクに書き込むときに、データがディスクの上にすでに存在するかどうかを知るためにハッシュ関数が使用される。そうである場合には、CATテーブルにおける適切なエントリが、既存のクラスタを示すように設定される。
【0081】
CATテーブルは、自らのゾーンの中に常駐する。CATテーブルがゾーンのサイズを超える場合には、追加のゾーンが使用され、CATのその部分のゾーンに論理アドレスをマッピングするために、テーブルが使用される。代替的には、ゾーンはCATテーブルを含むように事前に割当てられる。
【0082】
ホスト書き込み待ち時間を低減し、データ信頼性を保証するために、ジャーナルマネジャーが、(ディスクまたはNVRAMのいずれかに対する)すべての書き込みリクエストを記録する。システムが再起動される場合には、ジャーナルエントリは再起動に際してコミットされる。
【0083】
ディスクは出入りし得、領域は、破損を有することがわかった場合には、使わなく(retire)され得る。これらの状況のいずれにおいても、レイアウトマネジャーは、冗長タイプを変更するために、またはゾーンの領域的な構成を変化させるために(領域が破損した場合に)、
ゾーンの中の領域を再編成することが可能である。
【0084】
格納アレイは、物理的ディスクスペースの変化するレベルによって支援されて、仮想ディスクアレイを提供し、それはブロックレベルのインタフェースを提供するので、いつクラスタがファイルシステムによってもはや使われなくなるかは、明らかではない。結果として、使用されるクラスタスペースは、拡張し続ける。ガーベッジコレクタ(ホストまたはファームウェアのいずれかに位置する)は、どのクラスタが解放されたかを決定するためにファイルシステムを分析し、それらをハッシュテーブルから取り除く。
【0085】
以下の表は、本発明の例示的な実施形態に従った6つのソフトウェアレイヤを示す:
【0086】
【表5】

図13は、異なるソフトウェアレイヤと、それらが互いにどのように関連するかを表す、モジュール階層を示す。ソフトウェアレイヤリングは、明瞭なAPIおよび記述を提供するために、好ましくはリジッドである。
【0087】
ガーベッジコレクタ(Garbage Collector)は、ホストファイルシステムによってもはや使われないクラスタを解放する。たとえば、ファイルが削除されるときに、そのファイルを含むために使用されたクラスタは、好ましくは解放される。
【0088】
ジャーナルマネジャー(Journal Manager)は、書き込みの実行記録(journaling)の形を提供するので、電源異常または他のエラー状態の場合において、保留中の書き込みは失われない。
【0089】
レイアウトマネジャー(Layout Manager)は、ゾーンの領域に対するゾーンのランタイム再レイアウトを提供する。このことは、ディスクの挿入/取り外しまたは故障の結果として生じ得る。
【0090】
クラスタマネジャー(Cluster Manager)は、データゾーンのセットの中にクラスタを割当てる。ディスク利用デーモン(Disk Utilization Daemon)は、使用されていないディスクスペースを定期的にチェックする。
【0091】
ロックテーブル(Lock Table)は、書き込み衝突発行(collision issues)の後で、読み出しを処理する。
【0092】
ホストリクエストマネジャー(Host Request Manager)は、ホストおよびガーベッジコレクタからの読み出し/書き込みリクエストを処理する。書き込みはジャーナルマネジャーに渡されるが、読み出しはクラスタアクセステーブル(CAT)管理レイヤを介して処理される。
【0093】
上述のように、代表的なファイルシステムにおいて、ある量のデータが一般的に事実上反復される。ディスクスペース利用を低減させるために、このデータの複数のコピーはディスクに書き込まれない。代わりに、一つのインスタンスが書き込まれ、同じデータのすべての他のインスタンスが、この一つのインスタンスに対して参照される。
【0094】
この例示的な実施形態において、システムはつねにデータのクラスタの上で作動し(たとえば8つの物理的セクタ)、これはハッシュされる単位である。SHA1アルゴリズムは、160ビットハッシュを生成するために使用される。このことは、良好な独特さ(uniqueness)を含む多数の利益を有し、多数のプロセッサにおいてオンチップでサポートされる。すべての160ビットがハッシュ記録に格納されるが、最下位の16ビットのみがハッシュテーブルへのインデックスとして使用される。最も低い16ビットと一致する他のインスタンスは、リンクされたリストを介して連鎖される。
【0095】
この例示的な実施形態において、一度に一つの読み出し/書き込み操作のみが生じ得る。性能の目的のために、クラスタをディスクに書き込むときにハッシュ分析が生じることは許されない。代わりに、ハッシュ分析は、ハッシュマネジャーによるバックグラウンド活動として生じる。
【0096】
書き込みリクエストは、ジャーナルの書き込みキューから読み込まれ、完了に向けて処理される。データの一貫性を保証するために、書き込み操作がクラスタの上ですでに活動状態である場合には、書き込みは遅らせなければならない。他のクラスタの上の操作は、妨げられずに進行し得る。
【0097】
クラスタ全体が書き込まれない限りは、書き込まれるデータは、クラスタに格納された既存のデータと併合される必要がある。論理セクタアドレス(LSA)に基づいて、クラスタのCATエントリが位置づけられる。ハッシュキー、ゾーン、およびクラスタオフセット情報は、この記録から獲得され、次に、ハッシュテーブルを検索して一致を見出すために使用され得る。これがクラスタである。
【0098】
正しいハッシュエントリのルックアップの速度を改善するために、一度はSHA1ダイジェストを介して、次にゾーン/クラスタオフセットによって、ハッシュテーブルを二重にハッシュすることは十分に必要であり得る。ハッシュ記録がすでに使用されている場合には、参照カウントが減少させられる。参照カウントが現在ゼロであり、かつハッシュエントリによって参照されるスナップショットがない場合には、ハッシュエントリおよびクラスタは、それぞれのフリーリストに解放し返され得る。
【0099】
もともとのクラスタデータは、これでクラスタのアップデートセクションと併合させられ、データは再ハッシュされる。新しいクラスタはフリーリストから除去され、併合されたデータはクラスタに書き込まれ、新しいエントリはハッシュテーブルに追加され、CATテーブルにおけるエントリは新しいクラスタを指し示すようにアップデートされる。
【0100】
ハッシュテーブルをアップデートする結果として、エントリも内部キューに追加されて、バックグラウンドタスクによって処理される。このタスクは、新たに追加されたクラスタおよびハッシュエントリと、ハッシュテーブル行アドレスに一致する他のハッシュエントリとを比較し、これらが重複している場合には記録を結合し、必要に応じてハッシュエントリおよびCATテーブルエントリを解放する。これは、この活動によって書き込み待ち時間に負荷がかけられないことを保証する。この処理の間に故障(たとえば電力の損失)が生じる場合には、種々のテーブルが削除され得、結果としてデータの損失になる。テーブルは、最終コミットがアトミックであるか、あるいはジャーナルエントリが完全に完了しなかった場合には再実行され得るような方法で、管理されるべきである。
【0101】
以下は、書き込み論理の疑似コードである。
【0102】
【化1−1】

【0103】
【化1−2】

読み出しリクエストもまた、一度に一つのクラスタ(「セクタ」ではなく)で処理される。読み出しリクエストは、上記に概説されたハッシュ関連の処理を経ない。代わりに、ホスト論理セクタアドレスが、CATを参照するために使用され、ゾーン番号とゾーンの中へのクラスタオフセットとを獲得する。読み出しリクエストは、CATキャッシュにおけるCATテーブルエントリをルックアップすべきであり、書き込み進行中のビットが設定されることにおいて遅延されなければならない。他の読み出し/書き込みは、妨げられずに進行し得る。データ保全性のチェックを改善するために、クラスタは、読み出されるときにハッシュされ、そのハッシュは、ハッシュ記録に格納されたSHA1ハッシュ値と比較される。このことは、ハッシュテーブルの中への検索キーとして、ハッシュ、ゾーン、およびクラスタを使用することを必要とする。
【0104】
クラスタは、可能な限り少ないゾーンを使用するように割当てられる。なぜなら、ゾーンは、ディスクドライブの使用に直接的に対応するからである。すべてのゾーンについて、ハードドライブアレイの上に2つ以上の領域がある。ゾーンの数を最小化することによって、物理的領域の数が最小化され、したがってハードドライブアレイの上のスペースの消費が低減される。
【0105】
クラスタマネジャーは、データゾーンのセットからクラスタを割当てる。ゾーンにおける使用されていないクラスタを把握するために、リンクされたリストが使用される。しかし、使用されていないクラスタの情報は、ディスクの上にビットマップ(ゾーンあたり32KB)として格納される。リンクされたリストは、ビットマップから動的に構築される。最初に、使用されていないクラスタの一定の数のリンクされたリストが、メモリの中で作成される。クラスタが割当てられると、リストは縮小する。所定の最低点において、使用されていないクラスタを表す新しいリンクされたリストのノードは、ディスクの上のビットマップから抽出される。このようにして、ビットマップは、割当て用に使用されていないクラスタを見出すために分析される必要はない。
【0106】
この例示的な実施形態において、ハッシュテーブルは64Kの記録(ハッシュのより下位の16ビットによって索引をつけられる)であり、以下のフォーマットを有する:
【0107】
【表6−1】

【0108】
【表6−2】

オールゼロ(all zero)のクラスタは、かなり一般的であり得るので、たとえば決して削除され得ないように、オールゼロの場合は特別な場合として扱われ得る(したがってカウントをラッピング(wrapping)することは問題ではあり得ない)。
【0109】
複数のハッシュが同一の最下位ハッシュを有するとき、あるいは2つのハッシュエントリが異なるデータクラスタを指し示すときには、使用されていないハッシュ記録のリンクされたリストが使用される。いずれの場合においても、使用されていないハッシュ記録は、リストから取られ、pNextHashポインタを介してリンクされる。
【0110】
ハッシュマネジャーは、ハッシュテーブルに追加されたエントリを整頓し、ディスクの上の同一のクラスタを結合する。新しいハッシュ記録がハッシュテーブルに追加されると、メッセージがハッシュマネジャーに通知される。これは、ハッシュマネジャーによって自動的に行われる。バックグラウンド活動として、ハッシュマネジャーはキューの上のエントリを処理する。ハッシュマネジャーは、完全な(full)ハッシュ値が既存のハッシュ記録と一致するかどうかを知るために、完全なハッシュ値を比較する。そうする場合には、ハッシュマネジャーは、完成した(complete)クラスタデータも比較する。クラスタが一致する場合には、新しいハッシュ記録は使用されていないキューに捨て戻され得、ハッシュ記録カウントは増加させられ、重複するクラスタはクラスタの使用されていないキューに戻される。ハッシュマネジャーは、記録を結合するときに、スナップショットビットを前に伝播させるように注意しなければならない。
【0111】
クラスタアクセステーブル(CAT)は、間接的なポインタを含む。ポインタは、ゾーンの中のデータクラスタ(0が最初のデータクラスタである)を指し示す。一つのCATエントリは、単一のデータクラスタ(暫定的にサイズが4KB)を参照する。多くの反復データがあるときには、ディスク使用要件を低減するために、CATが(ハッシングとともに)使用される。単一のCATは、格納の隣接ブロックをつねに表す。CATは、非データゾーンの中に含まれる。それぞれのCATエントリは48ビットである。以下の表は、それぞれのエントリがどのようにレイアウトされるかを示す(それぞれのデータゾーンが1GBのデータを含むと想定する):
【0112】
【表7】

CATは64ビットの中に収まることが望ましいが、これは必要不可欠ではない。2TBアレイのためのCATテーブルは、現在、サイズが4GBまでである。それぞれのCATエントリは、データとゾーンの数とを含むゾーンを指し示す。
【0113】
図14は、ゾーンにおけるデータクラスタにアクセスするために、CATがどのように使用されるかを示す。冗長データは、CATにおける2つ以上のエントリによって参照される。2つの論理クラスタが同じデータを含むので、それらのCATエントリは、同じ物理的クラスタに指し示される。
【0114】
ハッシュキーエントリは、クラスタ全体の160ビットSHA1ハッシュ値の16ビット抽出を含む。このエントリは、書き込み操作の間にハッシュテーブルをアップデートするために使用される。
【0115】
16TBのデータを参照するCATにおけるそれぞれのエントリにおいて、十分なビットがある。しかし、すべてのデータクラスタが互いに異なる場合には(コンテンツに関して)、2TBのデータを参照するために、ちょうど3ゾーン相当以上のCATエントリが必要とされる(それぞれのゾーンは、サイズが1GBであり、したがって1GBサイズのCATエントリを格納し得る。6バイトCATエントリを想定すると、178956970CATエントリ/ゾーンであり、すなわち、それぞれのクラスタが4Kである場合には、テーブルは約682GB/ゾーンを参照する)。
【0116】
ホスト論理セクタ変換テーブルは、ホスト論理セクタアドレスをゾーン番号に変換するために使用される。ホスト論理セクタアドレスに対応するCATの部分は、このゾーンに常駐する。それぞれのCATエントリは、4096バイトのクラスタサイズを表すことに留意されたい。これは8つの512バイトセクタである。以下は、ホスト論理セクタ変換テーブルの表現を示す:
【0117】
【表8−1】

【0118】
【表8−2】

ゾーンは、CAT全体を保持するように事前に割当てられ得る。代替的に、CATに対してより多くのエントリが要求されるときには、ゾーンがCATに対して割当てられ得る。CATは、2TB仮想ディスクをホストセクタアドレススペースにマッピングするので、ホストによるハードディスクのパーティショニングまたはフォーマッティングの間に、おそらくCATの大部分が参照される。このことを理由として、ゾーンは事前に割当てられ得る。
【0119】
CATは大きな1GB/ゾーンのテーブルである。使用されるクラスタのワーキングセットは、この大きなテーブルからのスパースセット(sparse set)である。性能の理由のために、活動状態のエントリは、ディスクから(おそらく時間的に)つねに読み込むのではなく、プロセッサメモリにおいてキャッシュされ得る。キャッシュを配置するために、少なくとも2つのオプションがあり、CATからの個々のエントリ、またはCATからの全体のクラスタである。
【0120】
進行中の書き込みは、CATキャッシュテーブルと結合されるので、すべての未処理の書き込みがキャッシュの中に留まることを保証する必要がある。したがって、キャッシュは、少なくとも、未処理の書き込みリクエストの最大数と同じくらい大きい必要がある。
【0121】
キャッシュにおけるエントリは、クラスタサイズ(すなわち4K)である。クラスタの上で作動中の進行中の書き込みがあるかどうかを知る必要がある。この指示は、クラスタについてのキャッシュエントリにおけるフラグとして格納され得る。以下の表は、CATキャッシュエントリのフォーマットを示す:
【0122】
【表9】

キャッシュエントリにおける進行中のフラグは、2つの意味を有する。第一に、書き込みが進行中であり、クラスタの上のいかなる書き込み(または追加の書き込み)も、書き込みが完了するまでは延期されなければならない、ということを示す。第二に、キャッシュにおけるこのエントリは、ビットが設定される間はフラッシュ(flush)されてはならない。このことは、部分的にはビットの状態を保護するためであり、このクラスタが現在使用されているという事実を反映させるためでもある。さらに、このことは、キャッシュのサイズが、少なくとも、未処理の書き込み操作の数と同じくらい大きくなければならないことを意味する。
【0123】
進行中の書き込みのインジケータをクラスタについてのキャッシュエントリに格納することの一つの利点は、現在操作中であるという事実を反映し、別のテーブルを有することを不要にし、追加のハッシュベースのルックアップ、またはこのビットもチェックするためのテーブルウォーク(table walk)を不要にすることである。キャッシュは、書き込み遅延(write−delayed)キャッシュであり得る。より早く書き込ませることは有益であり得るが、書き込み操作が完了したときにキャッシュエントリをディスクに書き戻すのみでよい。ハッシュされ得る未処理の書き込みエントリの数を増加させるために、ハッシュ関数または他のメカニズムが使用され得る。
【0124】
代替のアプローチは、CATのクラスタ全体をキャッシュすることである(すなわちエントリのうちの4Kエントリ)。このことは、アクセスの良好な空間的局所性がある場合に、一般的に性能を改善し得る。CATエントリは48ビット幅なので、注意が払われる必要があり、キャッシュにおけるエントリの全体の数はない。以下の表は、クラスタされたCATキャッシュエントリの例を示す:
【0125】
【表10】

テーブルサイズは、4096+996(4192バイト)であり得る。250エントリのキャッシュサイズを有する必要があると想定すると、キャッシュは約1MBを占め得る。
【0126】
論理CATエントリアドレスの適切なマスキングによらずに、最初および最後のエントリが不完全であるかどうかを計算することは可能である。キャッシュするルックアップルーチンは、エントリのローディングの前にこれを行うべきであり、必要とされるCATクラスタをロードするべきである。
【0127】
ホストがセクタ(またはクラスタ)読み出しリクエストを送信するときに、論理セクタアドレスを介して送信する。論理セクタアドレスは、ホストによって要求される実際のデータを含むゾーンにおけるクラスタのオフセットを獲得するために、CATの中へのオフセットとして使用される。その結果は、ゾーン番号と、そのゾーンの中へのオフセットとである。その情報は、レイヤ2(Layer 2)ソフトウェアに渡され、レイヤ2ソフトウェアは、次に、ドライブからロークラスタ(raw cluster)を抽出する。
【0128】
ホストによっていまだかつて書き込まれていないクラスタを処理するために、すべてのCATエントリが、オールゼロを含む「デフォルト」クラスタを指し示すように初期化される。
【0129】
ジャーナルマネジャーは、二層の書き込み実行記録システムである。システムの目的は、書き込みリクエストがホストから受け入れられ得ることを確実にし、データが保全性を保証しながら受け入れられたことをホストに迅速に示し返すことである。さらに、システムは、任意のディスク書き込みの間のシステムリセットの場合において、ブロックレベルデータまたはシステムメタデータ(たとえばCATおよびハッシュテーブルエントリ)の破損または損失がないことを保証する必要がある。
【0130】
J1ジャーナルマネジャーは、すべての書き込みリクエストをホストからディスクへ可能な限り迅速にキャッシュする。ひとたび書き込みが首尾良く完了すると(すなわちデータがアレイによって受け入れられると)、ホストは、操作が完了したことを示すために信号を送られ得る。ジャーナルエントリは、故障から回復するときに、書き込みリクエストの回復を可能にする。ジャーナル記録は、ディスクに書き込まれるべきデータと、書き込みトランザクションに関連するメタデータとからなる。
【0131】
ディスク読み出し/書き込みを低減するために、書き込みに関連するデータが書き込まれて、クラスタを解放する。このことは、データを自動的にミラリングする。使用されていないクラスタは、使用されていないクラスタのリストから取られる。ひとたびデータが書き込まれると、使用されていないクラスタのリストは、ディスクに書き戻されなければならない。
【0132】
ジャーナル記録は、ミラリングされていないゾーンの上のジャーナルキューに対して書き込まれる。それぞれの記録は、サイズにおいてセクタであり、ジャーナル書き込みの間の故障が以前のジャーナルエントリを破損し得るリスクを低減するために、セクタ境界に位置合わせされる。ジャーナルエントリは、記録の終端において一意の増加するシーケンスカウントを含むので、キューの終端は容易に識別され得る。
【0133】
ジャーナル書き込み操作は、スレッドを処理するホストキューの中で同期的に生じる。ジャーナル書き込みは、ディスクに書き込まれるときに順序づけられなければならないので、任意の時間において一つのスレッドのみがジャーナルに書き込み得る。J1テーブルにおけるジャーナルエントリのアドレスは、一意の識別子として使用され得るので、J1ジャーナルエントリは、J2ジャーナルにおけるエントリと相互に関連させられ得る。ひとたびジャーナルエントリが書き込まれると、トランザクション完了通知が、ホスト完了キューに対して通知される。今や書き込み操作が実行され得る。ジャーナル書き込みが完了する前の、クラスタに対するいかなる次の読み出しも、遅延されることを保証することが重要である。
【0134】
以下の表は、J2ジャーナル記録のフォーマットを示す:
【0135】
【表11】

それぞれのジャーナル記録は、セクタ境界に位置合わせされる。ジャーナル記録は、ゾーン/オフセット/サイズの組のアレイを含み得る。
【0136】
図15は、本発明の例示的な実施形態に従ったジャーナルテーブルアップデートを示す。具体的には、ホスト書き込みリクエストが受信されるときに、ジャーナルテーブルがアップデートされ、一つ以上のクラスタが割当てられ、データがクラスタに書き込まれる。
【0137】
ホストジャーナルリクエストが処理される。これらによって、クラスタは書き込まれ、ディスクにシャドウバック(shadow back)されなければならないメタデータ構造(たとえばCATテーブル)へのアップデートももたらされる。たとえシステムリセットが生じても、これらのメタデータ構造がディスクに正しく書き戻されることを保証することが重要である。低レベルディスクI/O書き込み(J2)ジャーナルは、このために使用される。
【0138】
ホストインタフェースジャーナルエントリを処理するために、メタデータ構造の適切な操作が決定されるべきである。メモリにおいて変化が生じるべきであり、種々のディスクブロックへの変化の記録が生成されるべきである。この記録は、ディスクの上でなされるべき実際の変化を含む。アップデートされるそれぞれのデータ構造は、J2ジャーナルマネジャーを用いて登録される。この記録は、ディスクベースのジャーナルに記録されるべきであり、識別子を用いてスタンプされるべきである。記録がJ1ジャーナルエントリと結びつけられる場合には、識別子がリンクされるべきである。ひとたび記録が格納されると、ディスクへの変更がなされ得る(あるいはバックグラウンドタスクを介して行われ得る)。
【0139】
J2ジャーナルは、論理的にレイヤ3において存在する。これは、ゾーンマネジャーを介した書き込みを含み得るメタデータアップデートを実行記録(journal)するために使用される。ジャーナルエントリの再生が生じるときには、ゾーンマネジャーの方法を使用する。ジャーナルそのものは、特殊な領域に格納され得る。ジャーナルエントリの短い寿命を考慮すれば、ジャーナルエントリはミラリングされない。
【0140】
特に構造へのアップデートがアトミックである場合には、すべてのメタデータがJ2ジャーナルを経る必要はない。領域マネジャー構造は、J2ジャーナルを使用し得ない。たとえばバックグラウンドスレッドをチェックする保全性を用いて、領域マネジャービットマップにおける不整合を検出することが可能であり得る。
【0141】
J2ジャーナルのための単純なアプローチは、単一の記録を含むことである。記録がディスクに対してコミットされるとすぐに、記録は再生され、ディスクの上の構造をアップデートする。複数のJ2記録を有することと、ディスクの上の記録のアップデートをコミットするバックグラウンドタスクを有することとは可能である。この場合、ジャーナルと、種々のデータ構造に関連する任意のキャッシングアルゴリズムとの間の相互作用に、周到な注意が払われる必要がある。
【0142】
最初のアプローチは、ジャーナルエントリがディスクに対してコミットされるとすぐに、ジャーナルエントリを実行する。原則としては、J2の複数の同時ユーザがあり得るが、J2ジャーナルは一度に一人のユーザに対してロックされ得る。たとえこの場合においても、ジャーナルエントリは、実行依頼されたらすぐにコミットされるべきである。
【0143】
任意のより高いレベルのジャーナル活動が生じる前に、メタデータ構造が修復されることを保証することが重要である。システム再起動の際に、J2ジャーナルが分析され、任意の記録が再生される。ジャーナルエントリがJ1ジャーナルエントリと相互に関連させられる場合には、J1エントリは、完成したものとしてマークされ、除去され得る。ひとたびすべてのJ2ジャーナルエントリが完成すると、メタデータは信頼性のある状態になり、任意の残りのJ1ジャーナルエントリが処理され得る。
【0144】
J2ジャーナル記録は、以下の情報を含む。
・操作の数
・各操作は以下を含む:
−J1記録インジケータ
−書き込むべきゾーン/データオフセット
−書き込むべきデータ
−データのサイズ
−データクラスタの中へのオフセット
・ジャーナル記録識別子
・終端マーカ
このスキームは、たとえばJ2ジャーナルエントリの終端を識別するためにシーケンス番号を用いて、J2ジャーナルエントリをセクタ境界に置いて、J1ジャーナルスキームと同様に作動し得る。
【0145】
J1データポインタインジケータが設定される場合には、この特定の操作が、J1ジャーナル記録を指し示し得る。ホストによって供給される書き込みデータは、われわれの(our)ジャーナルエントリにコピーされる必要はない。ジャーナル記録における操作の最大数は十分に理解されると予想されるので、操作は固定サイズとして定義されることができるべきである。
【0146】
低レベル書き込み操作の間におけるセクタの破損(たとえば電力の損失によるもの)からの回復を可能にするために、J2ジャーナルは、書き込まれたセクタ全体を格納し得るので、必要な場合にはこの情報からセクタが再書き込みされ得る。代替的にまたは追加的に、書き込み操作の再生が必要とされるかどうかを決定するために、それぞれの変更されたセクタについて計算されたCRCは、J2記録に格納され得、ディスクの上のセクタから(たとえばゾーンマネジャーによって)計算されたCRCと比較され得る。
【0147】
異なるジャーナルが異なる位置に格納され得るので、ジャーナル記録を補助格納デバイスに書き込むために提供されるインタフェースレイヤがある。位置は非揮発性であるべきである。2つの候補は、ハードディスクおよびNVRAMである。J1がハードディスクに格納される場合には、J1ジャーナルのミラリングされないゾーンに格納される。J1ジャーナルは、NVRAMに格納する候補である。J2ジャーナルは、特殊な領域に格納され得るが、ディスクの上に格納されるべきである(すなわち、短い寿命を有するので冗長ではない)。J2ジャーナルをディスクの上に格納する利点は、内部データ構造のアップデートの間にシステムリセットがある場合に、データ構造が一貫性のある状態に戻され得ることである(たとえユニットが長時間にわたって電源を入れられないままにされるとしても)。
【0148】
ゾーンマネジャー(ZM)は、より高いレベルのソフトウェアによって必要とされるゾーンを割当てる。ZMへのリクエストは以下を含む:
a.ゾーンを割当てる
b.ゾーンを再割当て/解放する
c.L1に対してデータ読み出し/書き込みパススルーを制御する(?)
d.ゾーンにおけるクラスタの読み出し/書き込みをする(クラスタのオフセットとゾーン番号とを考慮して)
ZMは、冗長メカニズムを管理し(ドライブの数およびその相対的サイズの関数として)、ミラリング、ストライピング、およびデータの読み出し/書き込みのための他の冗長スキームを処理する。
【0149】
ZMは、ゾーンを割当てる必要があるときには、2つ以上のセットの領域の割当てを要求する。たとえば、ゾーンは1GBのデータに対して割当てられ得る。このゾーンを構成する領域は、冗長データを含む1GBのデータを含むことができる。ミラリングメカニズムのために、ゾーンは、それぞれ1GBの2セットの領域からなる。別の例として、3ディスクストライピングメカニズムは、それぞれ1/2GBの3セットの領域を利用する。
【0150】
ZMは、ゾーンを構成する領域の各セットの位置(ドライブ番号および開始領域番号)を見出すために、ZR変換テーブル(6)を使用する。1/12GBの領域サイズを想定すると、最大24領域が必要とされる。24領域は2×1GBゾーンを構成する。したがって、ZR変換テーブルは、ドライブ/領域データを提供する24列を含む。
【0151】
ZMは一般的に以下のように働く:
a.SDM(単一ドライブミラリング)の場合には、24列が使用される。ドライブ番号はすべての列において同じである。それぞれのエントリは、ゾーンを構成する物理的ドライブの上の物理的領域に対応する。最初の12エントリは、データの一つのコピーを含む領域を指し示す。最後の12エントリは、データの第2のコピーを含む領域を指し示す。
b.DDM(二重ドライブミラリング)の場合は、最初の12エントリのドライブ番号が最後の12エントリのドライブ番号とは異なることを除いて、SDMと同じである。
c.ストライピングの場合には、3つ以上の列が使用され得る。たとえば、ストライピングが3つのドライブにわたって使用される場合には、6つの領域が3つの異なるドライブから必要とされ得(すなわち18エントリが使用される)、最初の6エントリが同じドライブ番号を含み、次の6エントリが別のドライブ番号を含み、それに続く6エントリが第3のドライブ番号を含み、未使用のエントリはゼロにされる。
【0152】
以下は、ゾーン領域変換テーブルの表現を示す:
【0153】
【表12】

読み出し/書き込みリクエストが入ってくるときに、ZMは、ゾーン番号およびそのゾーンの中へのオフセットを提供される。ZMは、そのゾーンについての冗長メカニズムを見出すためにZR変換テーブルを調べ、どのドライブ/領域が読み出し/書き込みされなければならないセクタを含むかを計算するためにオフセットを使用する。ドライブ/領域情報は、次に、実際の読み出し/書き込みを行うL1レイヤに提供される。使用(Usage)の列における追加の可能なエントリは、「使用されていない」である。「使用されていない」は、ゾーンが定義されているものの、現在は使用中ではないことを示す。
【0154】
クラスタマネジャーは、データゾーンのセットの中のクラスタを割当ておよび再割当てする。
【0155】
レイアウトマネジャーは、ゾーンの領域に対するゾーンのランタイム再レイアウトを提供する。このことは、ディスクの挿入/取り外しまたは故障の結果として生じ得る。
【0156】
レイヤ1(L1)ソフトウェアは、物理的なドライブおよび物理的なセクタについて知っている。なかでも、L1ソフトウェアは、ゾーンマネジャーによる使用のために、物理的ドライブから領域を割当てる。この例示的な実施形態において、それぞれの領域は、4ドライブアレイシステムについて1/12GB(すなわち174763セクタ)のサイズを有する。より大きなドライブ最大数(8、12または16)を有するシステムは、異なる領域サイズを有する。
【0157】
SD3(3つのドライブにわたるストライピング;パリティがプラスされた2データ)を用いて1GBのデータを含むゾーンを作成するためには、3つのドライブにおいてそれぞれ6つの領域を使用することになる(6×1/12=ドライブあたり1/2GB)。
【0158】
この領域スキームの使用は、ゾーンが、たとえばミラリングからストライピングへと、移動または再構成されるときに、ディスクスペースのより良好な利用を提供することを可能にする。L1ソフトウェアは、領域のビットマップを用いて、物理的ドライブの上の利用可能なスペースを追跡する。それぞれのドライブは一つのビットマップを有する。それぞれの領域は、領域が使用されていないか、使用されているか、または不良であるかを追跡するために、ビットマップにおける2ビットによって表される。L2ソフトウェア(ZM)は、ゾーンを作成する必要があるときには、L1レイヤから領域のセットを得る。ゾーンを構成する領域は、ディスクの中で隣接しない。
【0159】
L1へのリクエストは以下を含む:
a.データの読み出し/書き込みをする(領域のグループの中のクラスタに対して)
b.読み出し/書き込みを制御する(テーブル、データ構造、DICなど)
c.領域に対して物理的スペースを割当てる(1ドライブの中の実際の物理的セクタ)
d.領域を再割当てする
e.物理的ドライブの中の物理的クラスタに対してロー(Raw)読み出し/書き込みをする
f.領域から領域へデータをコピーする
g.領域を不良としてマークする
使用されていない領域ビットマップは大きくあり得、したがって、使用されていないエントリを見つけるための検索(最悪の場合、使用されていないエントリがない)は、遅くあり得る。性能を改善するために、ビットマップの一部がメモリの中に事前にロードされ得、使用されていない領域のリンクされたリストがメモリに格納され得る。活動状態のそれぞれのゾーンについてリストがある。リストの最低点に達した場合には、より多くの使用されていないエントリが、バックグランド活動としてディスクから読み出され得る。
【0160】
ディスクマネジャー(Disk Manager)は、レイヤ0において作動する。以下の表に示されるように、2つのサブレイヤがあり、具体的には、抽象化レイヤと、物理的な格納アレイと通信するデバイスドライバとである。
【0161】
【表13】

デバイスドライバ(Device Driver)レイヤはまた、いくつかのレイヤを含む。たとえば、USBドライブを使用する格納アレイのために、USB移送レイヤの一番上にATAまたはSCSIスタックがある。抽象化レイヤは、格納アレイにおいて使用されるドライブの種類から独立した、基本的な読み出し/書き込み機能を提供する。
【0162】
一つ以上のディスクアクセスキューが、ディスクアクセスリクエストをキューに入れるために使用され得る。ディスクアクセスレートは、われわれのシステムにおける重要な性能ボトルネックの一つである。われわれは、全般的なシステム待ち時間を低減し、性能を改善するために、ディスクインタフェースがつねに可能な限りビジーに保たれることを確実にしたい。ディスクインタフェースへのリクエストは、非同期インタフェースを有するべきであり、ディスク操作が終了したときには、コールバックハンドラが操作を完了する。一つのディスクリクエストの完了は、キューの上の次のリクエストを自動的に開始する。ドライブごとに一つのキュー、またはすべてのドライブに一つのキューがあり得る。
【0163】
レイヤ1は、ドライブを論理ドライブ番号として参照する。レイヤ0は、論理ドライブ番号を、物理的ドライブ参照に変換する(たとえば、オープン()コールの結果として、/dev/sdaまたはファイルデバイス番号)。柔軟性のために(USBを介した拡張)、それぞれの論理ドライブについてキューがあるべきである。
【0164】
以下は、一部の例示的なオブジェクト定義およびデータフローである:
【0165】
【化2−1】

【0166】
【化2−2】

【0167】
【化2−3】

以下は、物理的ディスクレイアウトの説明である。上述のように、それぞれのディスクは固定サイズの領域に分割される。この例示的な実施形態において、それぞれの領域は、4ドライブアレイシステムについて、1/12GB(すなわち174763セクタ)のサイズを有する。より大きなドライブ最大数(8、12または16)を有するシステムは、異なる領域サイズを有する。最初に、領域番号0および1は、領域マネジャーによる使用のために予約され、割当てのためには使用されない。領域番号1は、領域番号0のミラリングである。所定のハードディスクについて領域マネジャーによって使用されるすべての内部データは、このハードディスクの領域番号0および1に格納される。この情報は、他のドライブと重複(またはミラリング)されない。領域0または1のいずれかにエラーがある場合には、データを保持するために他の領域が割当てられ得る。ディスク情報構造(Disk Information Structure)は、これらの領域を指し示す。
【0168】
それぞれのディスクは、ディスクと、ディスクが属するディスクセットと、ディスクについてのレイアウト情報とを識別する、DISを含む。ハードディスクの上の第1のセクタは予約されている。DISは、第1のセクタの後の、第1の不良でないクラスタに格納される。DISは、1KB相当のデータの中に含まれる。DISの2つのコピーがある。DISのコピーは、DISが属するディスクの上に格納される。さらに、システムにおけるすべてのディスクは、システムにおけるディスクのすべてのDISのコピーを含む。以下の表は、DISフォーマットを示す。
【0169】
【表14−1】

【0170】
【表14−2】

【0171】
【表14−3】

領域マネジャーは、領域情報構造における内部データを格納する。以下の表は、領域情報構造フォーマットを示す。
【0172】
【表15】

ゾーン情報構造は、ゾーンマネジャーがどこにゾーンテーブルを見出し得るかに関する情報を提供する。以下は、ゾーン情報構造フォーマットを示す。
【0173】
【表16−1】

【0174】
【表16−2】

高レベル情報ゾーンは、ハイレベルマネジャーによって使用されるゾーンテーブルおよび他のテーブルを含む。これらは、ミラリングを使用して保護される。
【0175】
以下の表は、ゾーンテーブルノードフォーマットを示す。
【0176】
【表17−1】

【0177】
【表17−2】

以下は、ゾーン情報のレイアウトの説明である。ゾーンテーブルノード(Zones Table Nodes)のリンクされたリストは、以下の方法でZISの後に置かれる。
【0178】
【表18】

この情報は、ゾーンテーブル領域(Zones Table Region)に格納される。
【0179】
図16は、本発明の例示的な実施形態に従ったドライブレイアウトを示す。最初の2つの領域は、互いのコピーである。第3の(オプションの)ゾーンテーブル領域は、ゾーンテーブルを含む。一つ以上のドライブを有するシステムにおいて、ドライブのうちの2つのみがZTRを含む。一つのドライブのみを有するシステムにおいて、2つの領域は、ZTRの2つの(ミラリングされた)コピーを保持するために使用される。DISは、RISおよびZISの位置に関する情報を含む。RISの第1のコピーは、領域0の中にある必要はないことに留意されたい(たとえば、領域0が不良セクタを含む場合には、異なる領域に位置し得る)。
【0180】
ゾーンマネジャーは、システム起動時にゾーンテーブルをロードする必要がある。それを行うために、ゾーンマネジャーは、領域番号およびオフセットをDISから抽出する。これは、ZISの開始を指し示す。
【0181】
定モジュール(たとえばCATマネジャー)は、制御構造およびデータテーブルをゾーンに格納する。レイヤ3以上におけるモジュールについてのすべての制御構造は、ゾーン0に格納される構造から参照される。このことは、たとえば、実際のCAT(クラスタ割当てテーブル)の位置が、ゾーン0に格納されたデータ構造から参照されることを意味する。
【0182】
以下の表は、ゾーン0情報テーブルフォーマットを示す。
【0183】
【表19】

CATのリンクされたリストは、CATを含むゾーンを記述するノードのリンクされたリストである。以下の表は、CATのリンクされたリストのノードフォーマットを示す。
【0184】
【表20−1】

【0185】
【表20−2】

ハッシュテーブルのリンクされたリストは、ハッシュテーブルを保持するゾーンを記述するノードのリンクされたリストである。以下の表は、ハッシュテーブルのリンクされたリストのノードフォーマットを示す。
【0186】
【表21】

図17は、本発明の例示的な実施形態に従った、ゾーン0のレイアウトと、他のゾーンがどのように参照されるかとを示す。
【0187】
上述のように、冗長セットは、データのセットに対して冗長性を提供するセクタ/クラスタのセットである。領域をバックアップすることは、一つの領域のコンテンツを別の領域にコピーすることを含む。
【0188】
データ読み出しエラーの場合には、より低いレベルのソフトウェア(ディスクマネジャーまたはデバイスドライバ)は、最初の失敗した試みの後に、追加の2回にわたって読み出しリクエストを再試行する。失敗状態は、ゾーンマネジャーに返される。次に、ゾーンマネジャーは、冗長クラスタから(読み出しによって)リクエストされるデータを、ディスクアレイにおいて再構築することを試みる。冗長データは、ミラリングされたクラスタ(SDM、DDMについて)、またはパリティを含むクラスタのセット(ストライピングされたインプリメンテーションについて)のいずれかであり得る。次に、再構築されたデータは、ホストに返される。ZMがデータを再構築することができない場合には、読み出しエラーがホストに返される。ゾーンマネジャーは、エラー通知パケット(Error Notification Packet)をエラーマネジャー(Error Manager)に送信する。図18は、本発明の例示的な実施形態に従った読み出しエラー処理を示す。
【0189】
データ書き込みエラーの場合には、より低いレベルのソフトウェア(ディスクマネジャーまたはデバイスドライバ)は、最初の失敗した試みの後に、追加の2回にわたって書き込みリクエストを再試行する。失敗状態はゾーンマネジャーに返される。ゾーンマネジャーは、エラー通知パケットをエラーマネジャーに送信する。
【0190】
このレベルにおいてデータ書き込みが実行されるときに、冗長情報もディスクに書き込まれる。結果として、一つのみのクラスタが書き込みエラーを有する限りは、次の読み出しはデータを再構築することができる。複数のディスクエラーがあり、冗長情報が読み出しまたは書き込みされ得ない場合には、少なくとも二つの可能なアプローチがある。
a.書き込みエラー状態をホストに戻す。冗長セットに関連するすべての領域を、不良セクタを含まない、新たに割当てられた領域に、バックアップする。
b.書き込みを遅らせる。冗長セットに関連するすべての領域を、不良セクタを含まない、新たに割当てられた領域に、バックアップする。次に、新たに割当てられた領域における適切なクラスタに書き込みを行う(すべての冗長部分、たとえばパリティなどとともに)。別個の書き込みキューは、遅らせられた書き込みを含むように使用され得る。
【0191】
アプローチ(a)は、問題がある。なぜなら、ジャーナルの成功した書き込みの結果として、書き込み状態がすでにホストに送信されてい得るので、ホストはエラーがあったことを知り得ないからである。代替策は、読み出しの失敗を報告するが、書き込みを可能にすることである。CATにおけるビットは、特定のLBAが不良読み出しを戻すべきであることを追跡するために使用され得る。
【0192】
図19は、本発明の例示的な実施形態に従ったエラー処理を示す。
【0193】
エラーマネジャー(EM)は、クラスタが本当に不良であるかどうかを知るためにクラスタをチェックする。そうである場合には、領域全体が不良であると考えられる。領域のコンテンツは、同じディスクの上の新たに割当てられた領域にコピーされる。次に、現在の領域はBAD(不良)とマークされる。領域にコピーする間に、エラーマネジャーは、不良セクタに遭遇したときに、必要とあればデータを再構築する。図20は、本発明の例示的な実施形態に従った、エラーマネジャーによる不良領域のバックアップを示す論理フロー図である。
【0194】
データ読み出しエラーがあり、エラーマネジャーが所定のクラスタについてデータを再構築できない場合には(たとえば、冗長セットにわたる読み出しエラーの結果として)、再構築され得ないデータの代わりに、ゼロが使用される。この場合には、不良セクタを含む他のセクタ(冗長セットからの)もまた、バックアップされなければならない。この場合もやはり、再構築され得ないデータの代わりにゼロが使用される。
【0195】
ひとたび冗長セットのコピーが行われると、EMはゾーンのこの部分に対応するクラスタへのアクセスを使用不能にする。次にEMは、新たに割当てられた領域を指し示すように、ゾーンテーブルをアップデートする。次に、クラスタへのアクセスが再び使用可能にされる。
【0196】
この例示的な実施形態は、8つのスナップショットをサポートするように設計される(これは、ハッシュ/クラスタのエントリが特定のスナップショットインスタンスによって使用されるかどうかを示す1バイトの使用を可能にする)。スナップショットに含まれる2つのテーブルがある。
1.スナップショットあたりのCATテーブルは、論理セクタアドレスと、そのLASについてのデータを含むディスクの上のクラスタとの関係を捉えるように、存在する必要がある。究極的には、スナップショットあたりのCATは、スナップショットが取られた瞬間におけるCATのコピーでなければならない。
2.ハッシュ値とデータクラスタとの間のマッピングをするシステムハッシュテーブル。ハッシュ関数は、どのスナップショットが使用されているかに関わらず同じ結果を返し、結果としてすべてのスナップショットにわたって共通である。結果として、このテーブルは、一意にクラスタが任意のスナップショットによって使用されているかどうかを理解しなければならない。ハッシュエントリを使用するスナップショットがない限りは、ハッシュクラスタエントリは、解放され得ないか、または新しいデータと置き換えられ得ない。
【0197】
現在のものでありなおかつ追加されつつあるスナップショットが、つねにある。ハッシュエントリが作成またはアップデートされるときに、現在のスナップショット番号をそのハッシュエントリに適用する必要がある。スナップショットが作られるときに、現在のスナップショット番号が増加させられる。
【0198】
任意のスナップショットによってもはや必要とされないクラスタ/ハッシュのエントリは、ハッシュテーブルをざっと読むこと(walking through)によって解放され、リタイヤ(retire)したスナップショットビットセットで任意のハッシュエントリを見出し、そのビットをクリアする。スナップショットバイトがゼロである場合には、ハッシュエントリはテーブルから除去され得、クラスタは解放され得る。
【0199】
ハッシュツリーに追加されつつある任意の新しいエントリとの衝突を防ぐために(新しいスナップショット番号は、リタイヤするスナップショット番号と同じであるから)、7つのスナップショットのみが取られることが可能にされ得、最後の(8番目の)スナップショットはリタイヤするスナップショットである。ハッシュテーブルは、バックグラウンド活動として調べられ(walked)得る。
【0200】
スナップショットを作成するために、主たるCATがアップデートされているときはいつでも、第2のCATゾーンが書き込まれ得る。これらのアップデートはキューに入れられ得、シャドー(shadow)CATは別のタスクとしてアップデートされ得る。スナップショットするために、シャドーCATはスナップショットCATになる。
【0201】
ひとたびスナップショットが行われると、新しいスナップショットCATになる新しいゾーンにこのスナップショットテーブルをコピーするために、バックグランドプロセスが開始され得る。CATのコピーが完了するまではシャドーCATキューが処理されないように、キューが使用され得る。万一、シャドーCATをアップデートする前に故障が生じた場合には(この場合にはキューにおけるエントリが失われ得る)、アレイがオンラインにされる前に、主たるCATテーブルからの再シャドーが実行され得る。
【0202】
代替的に、スナップショットが必要とされるときに、最初のCATコピーがプラスされた「デルタ」の収集がスナップショットを構成し得る。次に、バックグランドタスクが、この情報から完全なスナップショットCATを再構成し得る。このことは、スナップショットを行うためにダウンタイムをほとんどあるいはまったく必要とし得ない。一方、デルタの別のセットが、次のスナップショットのために収集され得る。
【0203】
上述のように、いわゆる「ガーベッジコレクタ」は、ホストファイルシステムによってもはや使用されないクラスタを解放するために使用され得る(たとえばファイルが削除されるとき)。一般的に言って、ガーベッジ収集は、使用されていないブロックを見出し、それらのホストLSAを計算し、LSAに基づいてそれらのCATエントリの場所を突き止めることによって働く。特定のLSAについてCATエントリがない場合には、クラスタはすでに使用されていない。しかし、CATエントリの場所が突き止められる場合には、参照カウントが増加され、カウントがゼロに当たる場合にクラスタが解放される。
【0204】
ガーベッジ収集の一つの問題は、ホストファイルシステムが使用しているブロックと、すでに使用され、ある時点で使用されていないとしてマークされたブロックとを区別することが難しくあり得ることである。ホストファイルシステムがブロックを書き込むときに、格納システムは、データのクラスタならびにそれを記述するCATエントリを割当てる。その時点から、たとえホストファイルシステムが次にそのブロックの使用を停止したとしても、一般的にクラスタは使用されているように見える(すなわち、クラスタは有効なCATエントリとともにまだ使用されている)。
【0205】
たとえば、特定のホストファイルシステムは、使用されたディスクブロックを追跡するためにビットマップを使用する。最初は、ビットマップは、たとえばすべてのビットをクリアすることによって、すべてのブロックが使用されていないことを示す。ファイルシステムが使用されると、ホストファイルシステムは、使用されていないブロックビットマップを使用することによって、ブロックを割当てる。格納システムは、クラスタおよびCATエントリを以前に概略された(outlined)ものとして割当てることによって、物理的格納をこれらのファイルシステム割当てと関連づける。ホストファイルシステムが、一部のブロックを、使用されていないプールに解除するときに、使用されていないブロックビットマップにおける対応するビットをクリアする必要が単にある。格納システムの上で、このことは、ホストの使用されていないブロックビットマップの一部をたまたま含むクラスタへの書き込みとして、一般的に明らかにされ、おそらく解放された実際のクラスタに対するI/Oがない(しかし、たとえば、ホストファイルシステムが一部の強化されたセキュリティーモードで実行している場合には、解放されたクラスタに対するI/Oがあり得、その場合には、長期経過の(stale)クラスタコンテンツが攻撃者によって読み出され得る可能性を低減させるために、ゼロまたはランダムデータのクリプトストロングハッシュ(crypto strong hash)をクラスタにおそらく書き込み得る)。さらに、ホストファイルシステムが、新しい割当てリクエストを満たすときに以前に解放したブロックを再使用するという保証はない。したがって、ホストファイルシステムが、格納システムの観点から、新しい、すなわち以前に再使用されたブロックを割当て続ける場合には、格納システムは、使用されていないクラスタをすぐに使い果たしてしまい、圧縮によって再生され得るどんなスペースにも左右される。たとえば、ファイルシステムブロックが4kであると想定すると、ホストが、ファイルシステムブロック100〜500を割当て、次に使用されていないブロック300〜500を割当て、次にブロック1000〜1100を割当てる場合には、合計のファイルシステム使用は300ブロックになり、それでもアレイは500クラスタを使用する。
【0206】
本発明の例示的な実施形態において、格納システムは、ホストファイルシステムのレイアウトにアクセスし、その使用されていないブロックビットマップを分析し、ファイルシステムによってもはや使用されていないクラスタを特定するためにその情報を使用することによって、ホストファイルシステムのディスクリソースの解放を検出し得る。格納システムが未使用のクラスタをこのように特定できるためには、格納システムは、ファイルシステムの使用されていないブロックビットマップの場所を突き止めて理解することができなければならない。したがって、格納システムは、所定のセットのファイルシステムを一般的にサポートし、格納システムは、ファイルシステムについて、使用されていないブロックビットマップの場所を突き止めて利用するのに十分なほど内部の働きを「理解」する。サポートされないファイルシステムについては、格納システムは、おそらくガーベッジ収集を実行することができず、したがって、過剰にコミットされることを回避するために、アレイの実際の物理的サイズの公示のみをするべきである。
【0207】
ファイルシステムタイプ(たとえば、NTFS、FAT、ReiserFS、ext3)を決定するために、ファイルシステムのスーパーブロック(または同等の構造)の場所が突き止められる必要がある。スーパーブロックを見出すために、パーティションテーブルが分析されて、OSパーティションの場所を突き止める。OSパーティションの場所が突き止められると想定すると、スーパーブロックの場所を突き止める目的のために、OSパーティションが分析され、それによってファイルシステムタイプを特定する。ひとたびファイルシステムタイプがわかると、使用されていないブロックビットマップを見出すために、レイアウトが分析され得る。
【0208】
使用されていないブロックの検索を容易にするために、たとえば、非公式の非冗長ゾーンに格納され得る使用されていないブロックビットマップのコピーを作り、そのコピーを使用して検索を実行することによって、ホストファイルシステムビットマップの履歴データが保たれ得る。ビットマップのサイズを考慮すれば、情報は、ビットマップ全体についてではなく、一度に比較的少数のクラスタについて保たれ得る。ガーベッジ収集が実行されるときに、現在の使用されていないブロックビットマップが、クラスタごとに履歴コピーと比較され得る。割当てられた状態から使用されない状態へと移行する任意のビットマップエントリが特定され得、ごみあさりをする(scavenging)操作が、再使用の良い候補であるクラスタに正確に向けられることを可能にする。それぞれのビットマップクラスタが処理されると、ビットマップ操作の経過する履歴を維持するために、履歴コピーが現在のコピーと置き換えられ得る。時間が経つにつれて、使用されていないブロックビットマップのコピーは、時間的にばらばらなクラスタの寄せ集めになるが、使用されていないエントリの場所を突き止めるために、現在のコピーがつねに使用されるので、このことは何の問題も引き起こさない。
【0209】
特定の条件下で、たとえば、ホストファイルシステムが、使用されていないブロックビットマップを使用してディスクブロックを割当て、次にデータブロックを書き込み、次に変更されたビットマップをディスクに流し戻す場合には、使用されていないブロックビットマップに関する競争状態があり得る。そのような場合には、たとえファイルシステムがクラスタを使用中であるとしても、ガーベッジコレクタがクラスタを解放し得る。このことはファイルシステムの破損につながり得る。格納システムは、そのような条件を回避または処理するようにインプリメントされるべきである。
【0210】
ガーベッジ収集はかなり高価な操作であり得、軽量のごみあさりがバックエンドI/O帯域幅を消費するので、ガーベッジ収集は過剰に使用されるべきではない。ガーベッジコレクタは、軽いバックグランドの遅いごみあさりから、積極的で重量の、または高優先度でさえあるごみあさりにわたる、いくつかのモードにおいて実行することができるべきである。たとえば、ガーベッジコレクタは、スペースの30%が使用されるときに、または少なくとも週に一回、軽く実行され得、スペースの50%が使用されるときに、やや激しく実行され得、ディスクスペースの90%以上が使用されるときに、すっかり高優先度のごみあさりで実行され得る。ガーベッジコレクタの積極性は、再利用するクラスタの目標数に限定することによって、およびおそらくそれぞれの収集実行について最大の許容できるI/Oカウントに限定することによって、制御され得る。たとえば、ガーベッジコレクタは、わずか10,000のI/Oを使用して1GBを再使用するように構成され得る。再利用リクエストを達成できなかったことは、次回に実行されるときにより積極的に操作するように、コレクタへのフィードバックとして使用され得る。ガーベッジコレクタがホストファイルシステム全体の使用されていないブロックビットマップを分析することと、おそらく可能なすべてのブロックを再使用することとの許可を、ガーベッジコレクタに与える、「すべて再使用」モードもあり得る。これは、アレイが(ほとんど)完全に満杯であるときに、クラスタを再使用する最後の試みとして行われ得る。ガーベッジコレクタは、そのルールを適用するために定期的に実行され得、ごみあさり操作を実行することを決定し得るかまたはし得ない。ごみあさり操作は、別のモジュール(たとえば領域マネジャーが領域を構築するためにクラスタを見出そうと努力しているときの領域マネジャー)から明示的に要求されることもできるべきである。
【0211】
ガーベッジ収集機能は、状態インジケータメカニズムの中に結びつけられ得る。たとえば、ある時点において、格納システムは「赤色」状態にあり得るが、進行中のガーベッジ収集操作は「赤色」状態を消去するのに十分なスペースを解放し得る。関連する状態情報を示すために、追加のインジケータ状態が使用され得る(たとえば、赤色インジケータは、ガーベッジ収集操作が進行中であることを示すように点滅させられ得る)。
【0212】
図21は、本発明の例示的な実施形態に従った、格納アレイの関連するコンポーネントを示す模式的なブロック図である。なかでも、格納アレイは、シャーシ2502を含み、格納マネジャー2504はシャーシ2502を介して複数の格納デバイス2508〜2508と通信し、格納デバイス2508〜2508はそれぞれ複数のスロット2506〜2506を通してシャーシに結合される。それぞれのスロット2506〜2506は、一つ以上のインジケータ2507〜2507と関連づけられ得る。なかでも、格納マネジャー2504は、上述の機能性をインプリメントするための種々のハードウェアおよびソフトウェアのコンポーネントを一般的に含む。ハードウェアコンポーネントは、プログラムコード、データ構造、およびデータを格納するためのメモリ、ならびにプログラムコードを実行するためのマイクロプロセッサシステムを一般的に含む。
【0213】
(仮想ホットスペア)
上述のように、多くの格納システムにおいて、ホットスペア格納デバイスが作動可能状態において維持されるので、別の格納デバイスが故障した場合に迅速にオンラインにされ得る。本発明の特定の実施形態において、物理的に別個のホットスペアを維持するのではなく、複数の格納デバイスにわたる未使用の格納容量から、仮想ホットスペアが作成される。物理的なホットスペアとは異なり、この未使用の格納容量は、格納デバイスが残りの格納デバイスから回復されたデータを格納できない場合に利用可能である。
【0214】
仮想ホットスペア機構は、ディスク故障の際にデータが冗長に再レイアウトされ得ることを保証するために、アレイの上に十分なスペースが利用可能であることを必要とする。したがって、進行中の方法で、格納システムは、一般的に、仮想ホットスペアのインプリメンテーションのために必要とされる未使用の格納容量の量を決定し(たとえば、格納デバイスの数、種々の格納デバイスの容量、格納されるデータの量、およびデータが格納される方法に基づいて)、仮想ホットスペアのために追加の格納容量が必要とされる場合に信号を発生する(たとえば、実質的に上述のような状態およびスロットを示す緑色/黄色/赤色のライトを使用して)。ゾーンが割当てられると、ディスクごとにそのゾーンを再レイアウトするためにいくつの領域が必要とされるかについての記録が保たれる。以下の表は、4つのドライブが使用される仮想ホットスペアを示す。
【0215】
【表22−1】

【0216】
【表22−2】

以下の表は、3つのドライブが使用される仮想ホットスペアを示す。
【0217】
【表23】

この例示的な実施形態において、仮想ホットスペアは、1つまたは2つのドライブのみを有するアレイの上では利用可能ではない。それぞれのゾーンと、アレイにおけるディスクの数とに関する情報に基づいて、アレイは、それぞれのあり得るディスク故障について再レイアウトのシナリオを決定し、それぞれのシナリオについてそれぞれのドライブの上で十分なスペースが利用可能であることを保証する。生成される情報は、再レイアウトエンジンおよびゾーンマネジャーにフィードバックされ得るので、データは、データ格納とホットスペア機構との間で正しくバランスを取られ得る。ホットスペア機構は、再レイアウトが生じ得るように、ゾーンレイアウトデータから計算されるものに加えて、十分なスペアワーキングスペース領域を必要とすることに留意されたい。
【0218】
図22は、本発明の例示的な実施形態に従った、仮想ホットスペアを管理するための例示的な論理を示す論理フロー図である。ブロック2102において、論理は、それぞれのあり得るディスク故障について再レイアウトのシナリオを決定する。ブロック2104において、論理は、最悪の事態のシナリオにおいてデータを冗長に再レイアウトするためにそれぞれのドライブの上で必要とされるスペースの量を決定する。ブロック2106において、論理は、最悪の事態のシナリオにおいてデータを冗長に再レイアウトするために必要とされるスペアワーキングスペース領域の量を決定する。ブロック2108において、論理は、最悪の事態のシナリオにおいてデータを冗長に再レイアウトすることを可能にするためにそれぞれのドライブの上で必要とされるスペースの総量を決定する(基本的に、再レイアウトのために必要とされるスペースの量と、必要とされるスペアワーキングスペース領域の量との合計)。ブロック2110において、論理は、格納システムが適切な大きさの利用可能な格納デバイスを含むかどうかを決定する。適切な大きさの利用可能な格納デバイスがある場合には(ブロック2112における「はい」)、論理反復はブロック2199において終了する。しかし、不適切な大きさの利用可能な格納装置がある場合には(ブロック2112における「いいえ」)、論理は、ブロック2114において、どのドライブ/スロットがアップグレードを必要とするかを決定する。次に、ブロック2116において、論理は、追加の格納スペースが必要とされるという信号を出し、どのドライブ/スロットがアップグレードを必要とするかを示す。論理反復は、ブロック2199において終了する。
【0219】
図23は、本発明の例示的な実施形態に従った、図22のブロック2102におけるような、それぞれのあり得るディスク故障について再レイアウトのシナリオを決定するための例示的な論理を示す論理フロー図である。ブロック2202において、論理はゾーンを割当てる。次に、ブロック2204において、論理は、ディスクごとにそのゾーンを再レイアウトするためにいくつの領域が必要とされるかを決定する。論理反復は、ブロック2299において終了する。
【0220】
図24は、本発明の例示的な実施形態に従った、仮想ホットスペア機能を呼び出すための例示的な論理を示す論理フロー図である。ブロック2302において、論理は、最悪の事態のシナリオの際にデータを冗長に再レイアウトすることを可能にするために利用可能な格納の十分な量を維持する。ブロック2304においてドライブの損失(たとえば取り外しまたは故障)を決定すると、論理は、ブロック2306において、データの故障許容を復元するために、一つ以上の残りのドライブを自動的に再構成する。論理反復は、ブロック2399において終了する。
【0221】
図25は、本発明の例示的な実施形態に従った、図24のブロック2306におけるような、データの故障許容を復元するために一つ以上の残りのドライブを自動的に再構成するための例示的な論理を示す論理フロー図である。ブロック2402において、論理は、4つ以上の格納デバイスにわたる第1のストライピングパターンを、3つ以上の残りの格納デバイスにわたる第2のストライピングパターンに変換し得る。ブロック2404において、論理は、3つの格納デバイスにわたるストライピングパターンを、残りの2つの格納デバイスにわたるミラリングパターンに変換し得る。もちろん、論理は、ドライブの損失の後でデータを冗長に再レイアウトするために、他の方法でパターンを変換し得る。論理反復は、ブロック2499において終了する。
【0222】
再び図21を参照すると、格納マネジャー2504は、上述のような仮想ホットスペア機能をインプリメントするための適切なコンポーネントおよび論理を一般的に含む。
【0223】
(動的アップグレード)
格納の動的な拡大および縮小を処理するための上述の論理は、動的にアップグレード可能なシステムを提供するように延長され得る。該システムにおいて、格納デバイスは必要に応じてより大きな格納デバイスと置き換えられ得、冗長性が維持または拡張されて、なおかつより大きな格納デバイスによって提供される追加の格納スペースが、複数の格納デバイスにわたる利用可能な格納スペースのプールに含まれるように、既存のデータが格納デバイスにわたって自動的に再構成される。したがって、より小さな格納デバイスがより大きな格納デバイスに置き換えられるときに、すでに格納されたデータの冗長性を改善するため、ならびに追加のデータを格納するために、追加の格納スペースが使用され得る。より多くの格納スペースが必要とされるときはいつでも、適切な信号がユーザに提供され(たとえば実質的に上述のような緑色/黄色/赤色のライトを使用して)、ユーザは単に格納デバイスを取り外し得、それをより大きな格納デバイスと置き換え得る。
【0224】
図26は、本発明の例示的な実施形態に従った、格納デバイスをアップグレードするための例示的な論理を示す論理フロー図である。ブロック2602において、論理は、第1の格納デバイスの上のデータを、その上に格納されたデータが他の格納デバイスの上で冗長に見えるように、格納する。ブロック2604において、論理は、第1の格納デバイスが、第1の格納デバイスよりも大きな格納容量を有する置換用デバイスと置き換えられたことを検出する。ブロック2606において、論理は、第1のデバイスの上に格納されたデータを、他のデバイスの上に冗長に格納されたデータを使用して、置換用デバイスの上に自動的に複写する。ブロック2608において、論理は、新しいデータを冗長に格納するために利用可能な置換用デバイスの上に、追加の格納スペースを作る。ブロック2610において、新しいデータに冗長性を提供するために利用可能な十分な量の格納容量を有するデバイスが他にない場合には、論理は、置換用デバイスの上の追加の格納スペースの中に、新しいデータを冗長に格納し得る。ブロック2612において、少なくとも一つの他のデバイスが、新しいデータに冗長性を提供するために利用可能な十分な量の格納容量を有する場合には、論理は、複数の格納デバイスにわたって新しいデータを冗長に格納し得る。
【0225】
再び図21を参照すると、格納マネジャー2504は、上述のような動的アップグレード機能をインプリメントするための適切なコンポーネントおよび論理を一般的に含む。
【0226】
(その他)
本発明の実施形態は、本明細書において全体が参照により援用されている、Geoffrey S.Barralの名義で2004年11月5日に出願された米国仮特許出願第60/625,495号に記述される態様で、周辺接続プロトコルを使用して、格納容量をホストコンピュータに提供するように使用され得る。
【0227】
ハッシュアルゴリズムは、厳密に一意のハッシュ値を生成し得ないことが留意されるべきである。したがって、ハッシュアルゴリズムが、同一でないコンテンツを有するデータの2つのチャンクに対して、同じハッシュ値を生成することが考えられる。(ハッシュアルゴリズムを一般的に取り入れる)ハッシュ関数は、一意性を確認するメカニズムを一般的に含む。たとえば、上述のような本発明の例示的な実施形態において、一つのチャンクのハッシュ値が別のチャンクのハッシュ値と異なる場合には、これらのチャンクのコンテンツは同一でないと考えられる。しかし、一つのチャックのハッシュ値が別のチャンクのハッシュ値と同じである場合には、コンテンツが同一であるか同一でないかを決定するために、ハッシュ関数は、2つのチャンクのコンテンツを比較し得るか、または何らかの他のメカニズムを利用し得る(たとえば異なるハッシュ関数)。
【0228】
論理フロー図は、本発明の種々の局面を示すために本明細書中で使用されるものであり、本発明を任意の特定の論理フローまたは論理インプリメンテーションに限定するものと解釈されるべきではないことが留意されるべきである。記載される論理は、全般的な結果を変化させることなく、またはさもなければ本発明の真の範囲から逸脱することなく、異なる論理ブロック(たとえば、プログラム、モジュール、機能、またはサブルーチン)に分割され得る。全般的な結果を変化させることなく、またはさもなければ本発明の真の範囲から逸脱することなく、しばしば、時間および論路要素が、追加され得、変更され得、省略され得、異なる順序で実行され得、または異なる論理構成を使用してインプリメントされ得る(たとえば、論理ゲート、ルーピング基本命令、条件付き論理、および他の論理構成)。
【0229】
本発明は、プロセッサ(たとえば、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ、または汎用コンピュータ)とともに使用するコンピュータプログラム、プログラム可能論理デバイスとともに使用するプログラマブルロジック(たとえば、フィールドプログラマブルゲートアレイ(Field Programmable Gate Array)(FPGA)、または他のPLD)、個別のコンポーネント、集積回路(たとえば、特定用途向けIC(Application Specific Integrated Circuit)(ASIC)、またはこれらの任意の組み合わせを含む任意の他の手段を含むが決してこれらに限定されない多くの異なる形で具体化され得る。
【0230】
本明細書中にこれまで記載された機能性のすべてまたは一部をインプリメントするコンピュータプログラム論理は、ソースコードの形態、コンピュータ実行可能な形態、および種々の中間的な形態(たとえば、アセンブラ、コンパイラ、リンカ、またはロケータ)を含むが決してそれらに限定されない、種々の形において具体化され得る。ソースコードは、種々のオペレーティングシステムまたはオペレーティング環境とともに使用する、種々のプログラミング言語(たとえば、オブジェクトコード、アセンブリ言語、またはFortran、C、C++、JAVA(登録商標)、またはHTML)のいずれかにおいてインプリメントされる一連のコンピュータプログラム命令を含み得る。ソースコードは、種々のデータ構造および通信メッセージを定義および使用し得る。ソースコードはコンピュータ実行可能な形態(たとえば、インタプリタを介して)であり得、あるいはソースコードはコンピュータ実行可能な形態に変換され得る(たとえば、翻訳プログラム(translator)、アセンブラ、またはコンパイラを介して)。
【0231】
コンピュータプログラムは、半導体メモリデバイス(たとえば、RAM、ROM、PROM、EEPROM、またはフラッシュプログラム可能RAM)、磁気メモリデバイス(たとえばディスケットまたは固定ディスク)、光メモリデバイス(たとえば、CD−ROM)、PCカード(たとえば、PCMCIAカード)、または他のメモリデバイスなどの有形の格納媒体において、永久的または一時的に、任意の形態(たとえば、ソースコードの形態、コンピュータ実行可能な形態、または中間的な形態)で固定され得る。コンピュータプログラムは、アナログテクノロジー、デジタルテクノロジー、光学テクノロジー、ワイヤレステクノロジー(たとえば、Bluetooth)、ネットワーキングテクノロジー、およびインターネットワーキングテクノロジーを含むが決してそれらに限定されない、種々の通信テクノロジーのいずれかを使用してコンピュータに送信可能な信号における任意の形態に固定され得る。コンピュータプログラムは、付随する印刷文書または電子文書とともに取り外し可能な格納媒体(たとえば、シュリンクラップソフトウェア)として任意の形態で配布され得るか、コンピュータシステム(たとえば、システムROMまたは固定ディスクの上)に事前ロードされ得るか、または通信システム(たとえば、インターネットまたはワールドワイドウェブ)を介してサーバまたは電子掲示板から配信され得る。
【0232】
本明細書中にこれまで記載された機能性のすべてまたは一部をインプリメントするハードウェア論理(プログラム可能論理デバイスとともに使用するプログラマブルロジックを含む)は、従来のマニュアル方法を使用して設計され得るか、あるいは計算機援用設計(Computer Aided Design)(CAD)、ハードウェア記述言語(たとえば、VHDLまたはAHDL)、またはPLDプログラミング言語(たとえば、PALASM、ABEL、またはCUPL)などの種々のツールを使用して、設計、キャプチャ、シミュレーション、または電子的文書化をされ得る。
【0233】
プログラマブルロジックは、半導体メモリデバイス(たとえば、RAM、ROM、PROM、EEPROM、またはフラッシュプログラム可能RAM)、磁気メモリデバイス(たとえば、ディスケットまたは固定ディスク)、光メモリデバイス(たとえば、CD−ROM)、または他のメモリデバイスなどの、有形の格納媒体において、永久的または一時的に固定され得る。プログラマブルロジックは、アナログテクノロジー、デジタルテクノロジー、光学テクノロジー、ワイヤレステクノロジー(たとえば、Bluetooth)、ネットワーキングテクノロジー、およびインターネットワーキングテクノロジーを含むが決してそれらに限定されない、種々の通信テクノロジーのいずれかを使用してコンピュータに送信可能な信号に固定され得る。プログラマブルロジックは、付随する印刷文書または電子文書とともに取り外し可能な格納媒体(たとえば、シュリンクラップ(shrink wrapped)ソフトウェア)として配布され得るか、コンピュータシステム(たとえば、システムROMまたは固定ディスクの上)に事前ロードされ得るか、または通信システム(たとえば、インターネットまたはワールドワイドウェブ)を介してサーバまたは電子掲示板から配信され得る。
【0234】
本出願は、以下の米国特許出願に関連し、それらは本明細書と同じ日付で出願され、参照によりそれらの全体が本明細書に援用されている:
「Dynamically Expandable and Contractible Fault−Tolerant Storage System Permitting Variously Sized Storage Devices and Method」というタイトルの、代理人整理番号2950/103;
「Dynamically Expandable and Contractible Fault−Tolerant Storage System With Virtual Hot Spare」というタイトルの、代理人整理番号2950/105;および
「Storage System Condition Indicator and Method」というタイトルの、代理人整理番号2950/107。
【0235】
本発明は、本発明の真の範囲から逸脱することなく、他の特定の形において具体化され得る。記載された実施形態は、あらゆる点で、説明的なものとしてのみ考えられ、限定的なものとしては考えられない。
【図面の簡単な説明】
【0236】
【図1】図1は、格納のためにオブジェクトが一連のチャンクに分析される、本発明の実施形態の図示である。
【図2a】図2aおよび図2bは、同じ実施形態において、より多くの格納デバイスの追加の結果として、チャンクのための故障許容格納のパターンがどのように動的に変化させられ得るかを図示する。
【図2b】図2aおよび図2bは、同じ実施形態において、より多くの格納デバイスの追加の結果として、チャンクのための故障許容格納のパターンがどのように動的に変化させられ得るかを図示する。
【図3】図3は、本発明のさらなる実施形態において、異なるサイズの格納デバイスを使用して構築された格納システムの上の異なる故障許容パターンにおけるチャンクの格納を図示する。
【図4a】図4a、図4bおよび図4cは、非効率な格納の使用および低レベルの故障許容を警告するためにインジケータ状態が使用される、本発明の別の実施形態を図示する。
【図4b】図4a、図4bおよび図4cは、非効率な格納の使用および低レベルの故障許容を警告するためにインジケータ状態が使用される、本発明の別の実施形態を図示する。
【図4c】図4a、図4bおよび図4cは、非効率な格納の使用および低レベルの故障許容を警告するためにインジケータ状態が使用される、本発明の別の実施形態を図示する。
【図5】図5は、本発明の実施形態に従った、データの格納、検索および再レイアウトにおいて使用される機能性モジュールのブロック図である。
【図6】図6は、2つ以上のドライブを含むアレイにおいてミラリングが使用される例を示す。
【図7】図7は、異なるレイアウトスキームを使用してデータを格納するいくつかの例示的なゾーンを示す。
【図8】図8は、スパースボリュームをインプリメントするためのルックアップテーブルを示す。
【図9】図9は、本発明の例示的な実施形態に従った、利用可能な格納スペースを有し、かつ故障許容の方法で作動する、例示的なアレイのための、状態インジケータを示す。
【図10】図10は、本発明の例示的な実施形態に従った、冗長データ格納を維持するために十分なスペースを有せず、より多くのスペースが追加されなければならない、例示的なアレイの状態インジケータを示す。
【図11】図11は、本発明の例示的な実施形態に従った、故障の際に冗長データを維持することができ得ない例示的なアレイの状態インジケータを示す。
【図12】図12は、本発明の例示的な実施形態に従った、格納デバイスが故障した例示的なアレイの状態インジケータを示す。スロットB、CおよびDに、格納デバイスが配置されている。
【図13】図13は、例示的な実施形態の異なるソフトウェアレイヤを表すモジュール階層と、それらが互いにどのように関係するかとを示す。
【図14】図14は、本発明の例示的な実施形態に従って、ゾーンにおけるデータクラスタにアクセスするためにクラスタアクセステーブルがどのように使用されるかを示す。
【図15】図15は、本発明の例示的な実施形態に従ったジャーナルテーブルアップデートを示す。
【図16】図16は、本発明の例示的な実施形態に従ったドライブレイアウトを示す。
【図17】図17は、本発明の例示的な実施形態に従った、ゾーン0のレイアウトと、他のゾーンがどのように参照されるかとを示す。
【図18】図18は、本発明の例示的な実施形態に従った読み出しエラー処理を示す。
【図19】図19は、本発明の例示的な実施形態に従った書き込みエラー処理を示す。
【図20】図20は、本発明の例示的な実施形態に従った、エラーマネジャーによる不良領域のバックアップを示す論理フロー図である。
【図21】図21は、本発明の例示的な実施形態に従った格納アレイの関連コンポーネントを示す模式的なブロック図である。
【図22】図22は、本発明の例示的な実施形態に従った、仮想ホットスペアを管理するための例示的な論理を示す論理フロー図である。
【図23】図23は、本発明の例示的な実施形態に従った、図22のブロック2102におけるような、それぞれのあり得るディスク故障について再レイアウトシナリオを決定するための例示的な論理を示す論理フロー図である。
【図24】図24は、本発明の例示的な実施形態に従った、仮想ホットスペア機能を呼び出すための例示的な論理を示す論理フロー図である。
【図25】図25は、本発明の例示的な実施形態に従った、図24のブロック2306におけるような、データの故障許容を復元する一つ以上の残りのドライブを自動的に再構成するための例示的な論理を示す論理フロー図である。
【図26】図26は、本発明の例示的な実施形態に従った、格納デバイスをアップグレードするための例示的な論理を示す論理フロー図である。

【特許請求の範囲】
【請求項1】
格納デバイスのセットにおいてデータを格納する方法であって、該セットは、少なくとも2つのデバイスを有し、該方法は、データ損失なしに、該デバイスのうちの第1のデバイスを、より大きな格納容量を有する置換用デバイスと置き換えることを可能にし、該方法は、
該格納デバイスのセットにデータを冗長に格納することと、
該デバイスのうちの第1のデバイスを置換用デバイスによって置き換える際に、該セットの少なくとも一つの他のドライブの上に冗長に格納されたデータを使用して、該第1のデバイスの上に格納されたデータを、置換用デバイスの上に複写することと、
少なくとも一つの冗長スキームを使用して、追加データが冗長に格納される態様で、該置換用ドライブの上の残りの格納容量を、該追加データの格納のために利用可能にすることと
を包含する、方法。
【請求項2】
前記格納デバイスのセットにデータを冗長に格納することが、冗長スキームの混合を使用してデータを格納することを包含する、請求項1に記載の方法。
【請求項3】
前記データ冗長スキームが、ミラリング、パリティを用いたストライピング、RAID6、二重パリティ、対角線パリティ、低密度パリティチェックコード、およびターボコードを含むグループから選択される、請求項2に記載の方法。
【請求項4】
前記追加データに冗長性を提供するために十分な量の利用可能な格納容量を有するデバイスが他にない場合に、前記置換用デバイスの上の残りの前記格納容量の中に該追加データを冗長に格納することをさらに包含する、請求項1に記載の方法。
【請求項5】
前記置換用デバイスの上の残りの前記格納容量の中に前記追加データを冗長に格納することが、ミラリングを包含する、請求項4に記載の方法。
【請求項6】
少なくとも一つの他のデバイスが、前記追加データに冗長性を提供するために十分な量の利用可能な格納容量を有する場合に、前記置換用デバイスを含む複数の格納デバイスにわたって該追加データを冗長に格納することをさらに包含する、請求項1に記載の方法。
【請求項7】
前記複数の格納デバイスにわたって前記追加データを冗長に格納することが、ミラリング、パリティを用いたストライピング、RAID6、二重パリティ、対角線パリティ、低密度パリティチェックコード、およびターボコードのうちの少なくとも一つを包含する、請求項6に記載の方法。
【請求項8】
前記格納デバイスのセットの実際の格納容量よりも大きい、該格納デバイスのセットの第1の格納容量を示すことと、
該実際の格納容量の外側の場所にデータを格納するリクエストを、該実際の格納容量の中の場所にマッピングすることと
をさらに包含する、請求項1に記載の方法。
【請求項9】
前記リクエストをマッピングすることが、
リクエストされた場所を実際の場所にマッピングするルックアップテーブルを維持することと、
該実際の場所を得るために、該リクエストされた場所に従って該ルックアップテーブルに索引をつけることと
を包含する、請求項8に記載の方法。
【請求項10】
格納システムであって、
種々の格納容量の格納デバイスを受け入れるための複数の格納デバイススロットと、
該複数の格納デバイススロットに動作可能なように結合され、それに結合された格納デバイスのセットを管理するための、格納マネジャーとを備え、
該格納マネジャーは、
冗長的な態様で該格納デバイスのセットの上にデータを格納し、
該デバイスのうちの第1のデバイスを、より大きな格納容量を有する置換用デバイスによって置き換える際に、該セットの他のドライブの上に冗長に格納されたデータを使用して、該第1のデバイスの上に格納されたデータを該置換用デバイスの上に複写し、
該格納マネジャーはさらに、少なくとも一つの冗長スキームを使用して、追加データが冗長に格納される態様で、追加された格納容量を、該追加データの格納のために利用可能にする、格納システム。
【請求項11】
前記格納マネジャーが、冗長スキームの混合を使用してデータを格納する、請求項10に記載の格納システム。
【請求項12】
前記冗長スキームが、ミラリング、パリティを用いたストライピング、RAID6、二重パリティ、対角線パリティ、低密度パリティチェックコード、およびターボコードを含むグループから選択される、請求項11に記載の格納システム。
【請求項13】
前記追加データに冗長性を提供するために十分な量の利用可能な格納容量を有するデバイスが他にない場合に、前記格納マネジャーが、前記置換用デバイスの上の残りの前記格納容量の中に該追加データを冗長に格納する、請求項10に記載の格納システム。
【請求項14】
前記格納マネジャーが、ミラリングを使用して、前記置換用デバイスの上の残りの前記格納容量の中に前記追加データを冗長に格納する、請求項13に記載の格納システム。
【請求項15】
少なくとも一つの他のデバイスが、前記追加データに冗長性を提供するために十分な量の利用可能な格納容量を有する場合に、前記格納マネジャーが、前記置換用デバイスを含む複数の格納デバイスにわたって該追加データを冗長に格納する、請求項10に記載の格納システム。
【請求項16】
前記格納マネジャーが、ミラリング、パリティを用いたストライピング、RAID6、二重パリティ、対角線パリティ、低密度パリティチェックコード、およびターボコードのうちの少なくとも一つを使用して、複数の格納デバイスにわたり前記追加データを冗長に格納する、請求項15に記載の格納システム。
【請求項17】
前記格納マネジャーが、
前記格納デバイスのセットの実際の格納容量よりも大きい、該格納デバイスのセットの第1の格納容量を示し、
該実際の格納容量の外側の場所にデータを格納するリクエストを、該実際の格納容量の中の場所にマッピングする、請求項10に記載の格納システム。
【請求項18】
リクエストされた場所を実際の場所にマッピングするために前記格納マネジャーによって維持されるルックアップテーブルをさらに備え、
該格納マネジャーが、該実際の場所を得るために、該リクエストされた場所に従って該ルックアップテーブルに索引をつける、請求項17に記載の格納システム。
【請求項19】
格納システムであって、
複数の格納デバイスと、
該複数の格納デバイスに動作可能なように結合された格納マネジャーとを備え、
該格納マネジャーは、
該複数の格納デバイスにデータを冗長に格納し、
第1の格納デバイスがより大きな格納容量の置換用格納デバイスに置き換えられたときに、該複数の格納デバイスにわたる既存のデータを自動的に再構成することにより、冗長性を少なくとも維持しオプションとして拡張し、該置換用格納デバイスによって提供される追加の格納容量を冗長な格納に利用可能にする、格納システム。
【請求項20】
前記格納マネジャーが、他の格納デバイスの上に冗長に格納されたデータを使用して、前記第1のデバイスの上に格納されたデータを、前記置換用デバイスの上に複写する、請求項19に記載の格納システム。
【請求項21】
前記格納マネジャーが、前記置換用格納デバイスによって提供される追加の格納容量を使用して、データを再構成することにより、データの冗長性を拡張する、請求項19に記載の格納システム。
【請求項22】
前記格納マネジャーが、第1の冗長スキームのセットを使用してデータを格納し、該第1の冗長スキームのセットとは異なり得る第2の冗長スキームのセットを使用してデータを再構成する、請求項20に記載の格納システム。

【図1】
image rotate

【図2a】
image rotate

【図2b】
image rotate

【図3】
image rotate

【図4a】
image rotate

【図4b】
image rotate

【図4c】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate


【公表番号】特表2008−521074(P2008−521074A)
【公表日】平成20年6月19日(2008.6.19)
【国際特許分類】
【出願番号】特願2007−540108(P2007−540108)
【出願日】平成17年11月4日(2005.11.4)
【国際出願番号】PCT/US2005/040174
【国際公開番号】WO2006/052829
【国際公開日】平成18年5月18日(2006.5.18)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Bluetooth
【出願人】(507146739)データ ロボティクス インコーポレイテッド (6)
【Fターム(参考)】