(57)【要約】【課題】効率の高いデータ照合のための装置および方法を提供する。【解決手段】非連続項目を記憶する仮想データ空間（１４０）と連続項目の第１のデータ・アレイ（１４２）とを備えるメモリ空間（１２２）内にデータ構造を形成し、データ・アレイ（１４２）の少なくとも第１の連続項目はスキップ・リスト（１４４）を指し、データ・アレイ（１４２）の少なくとも第２の連続項目は第２のデータ・アレイ（１４６）を指し、データ・アレイ（１４２）の少なくとも第３の連続項目（１４８）は仮想データ空間（１４０）内の選ばれた非連続項目を指すようにする。【選択図】図５
2009015840.tif 000002
【特許請求の範囲】
【請求項１】
メモリ空間内にデータ構造を含む機器であって、非連続項目を記憶する仮想データ空間として特徴付けられる第１の部分と、連続項目の第１のデータ・アレイとして特徴付けられる第２の部分とを含み、前記データ・アレイの少なくとも第１の連続項目はスキップ・リストを指し、前記データ・アレイの少なくとも第２の連続項目は第２のデータ・アレイを指し、少なくとも第３の連続項目は前記第１の部分内の選ばれた非連続項目を指す、メモリ空間内にデータ構造を含む機器。
【請求項２】
前記スキップ・リストのキーは前記第１の連続項目から得られ、また前記スキップ・リストの関連するノードは前記仮想データ空間の前記非連続項目の選ばれた１つを指す、請求項1記載のメモリ空間内にデータ構造を含む機器。
【請求項３】
前記第２の連続項目は前記第２のデータ・アレイへの直接ルックアップ索引を与え、また前記索引での関連する値は前記仮想データ空間の前記非連続項目の選ばれた１つを指す、請求項1記載のメモリ空間内にデータ構造を含む機器。
【請求項４】
前記スキップ・リストおよび前記第２のデータ・アレイの各出力はそれぞれ、前記仮想データ空間の前記非連続項目の選ばれた１つを識別するポインタと、前記非連続項目の前記選ばれた１つに関連するメモリの範囲のコピー・グレインを識別するオフセット値とを備える、請求項1記載のメモリ空間内にデータ構造を含む機器。
【請求項５】
前記仮想データ空間および第１のデータ・アレイは共に同じ最大数の前記各項目を収容する、請求項1記載のメモリ空間内にデータ構造を含む機器。
【請求項６】
前記仮想データ空間の前記非連続項目はそれぞれ、記憶空間内の選ばれた範囲のデータの固有のアドレスを識別する高信頼記憶ユニット記述子（ＲＳＵＤ）を含む、請求項1記載のメモリ空間内にデータ構造を含む機器。
【請求項７】
前記仮想データ空間内にＲＳＵＤが存在することを、前記関連する選ばれた範囲のデータのスナップショット・コピーが生成されたことの表示として用いる、請求項６記載のメモリ空間内にデータ構造を含む機器。
【請求項８】
前記データ構造は中間レベル・マップ（ＭＬＭ）として特徴付けられ、また前記第１のデータ・アレイの前記連続項目には、トップ・レベル・マップ（ＴＬＭ）に入力値を与えることによりアクセスする、請求項1記載のメモリ空間内にデータ構造を含む機器。
【請求項９】
前記メモリ空間はハードディスク・ドライブのアレイを含む記憶要素の一部を形成する、請求項1記載のメモリ空間内にデータ構造を含む機器。
【請求項１０】
記憶要素を含む機器であって、プロセッサと、キャッシュ・メモリと、データ記憶装置のアレイとを備え、前記記憶要素は更に、非連続項目を記憶する仮想データ空間として特徴付けられる第１の部分と連続項目の第１のデータ・アレイとして特徴付けられる第２の部分とを備える関連するメモリ空間内のデータ構造を備え、前記データ・アレイの少なくとも第１の連続項目はスキップ・リストを指し、前記データ・アレイの少なくとも第２の連続項目は第２のデータ・アレイを指し、少なくとも第３の連続項目は前記第１の部分内の選ばれた非連続項目を指す、記憶要素を含む機器。
【請求項１１】
前記仮想データ空間の前記非連続項目はデータ記憶装置のアレイの関連する範囲のアドレスを識別する、請求項1０記載の記憶要素を含む機器。
【請求項１２】
前記データ構造は中間レベル・マップとして特徴付けられ、また前記記憶要素は更に前記データ記憶装置のアレイに関連する仮想ブロック・アドレス（ＶＢＡ）に応じて前記第１のデータ・アレイに索引を付ける前記関連するメモリ空間内のトップ・レベル・マップを含む、請求項1０記載の記憶要素を含む機器。
【請求項１３】
前記スキップ・リストおよび前記第２のデータ・アレイは仮想記憶空間の前記非連続項目のそれぞれへのポインタを与える、請求項1２記載の記憶要素を含む機器。
【請求項１４】
前記仮想データ空間の前記非連続項目はそれぞれ、前記アレイ内の選ばれた範囲のデータの固有のアドレスを識別する高信頼記憶ユニット記述子（ＲＳＵＤ）を含む、請求項1０記載の記憶要素を含む機器。
【請求項１５】
前記仮想データ空間内にＲＳＵＤが存在することは前記関連する選ばれた範囲のデータのスナップショット・コピーが生成されたことを示す、請求項請求項1４記載の記憶要素を含む機器。
【請求項１６】
方法であって、
非連続項目を記憶する仮想データ空間として特徴付けられる第１の部分と連続項目の第１のデータ・アレイとして特徴付けられる第２の部分とを備えるメモリ空間内にデータ構造を形成し、前記データ・アレイの少なくとも第１の連続項目はスキップ・リストを指し、前記データ・アレイの少なくとも第２の連続項目は第２のデータ・アレイを指し、少なくとも第３の連続項目は前記第１の部分内の選ばれた非連続項目を指し、
前記データ構造にアクセスして、選ばれた値が関連する範囲の値の中にあるかどうかを、対応する非連続項目が前記仮想データ空間内にあるかどうかに関して決定する、
方法。
【請求項１７】
前記アクセスするステップは、前記第１の連続項目から前記スキップ・リストのキーを得、前記キーを用いて前記スキップ・リストを探索して対応するノードを識別し、前記ノードでの値を用いて前記仮想データ空間の前記非連続項目の選ばれた１つを指すことを含む、請求項１６記載の方法。
【請求項１８】
前記アクセスするステップは、前記第２の連続項目を用いて前記第２のデータ・アレイに索引を付けてポインタ値を出力し、前記ポインタ値を用いて前記仮想データ空間の前記非連続項目の対応する1つを識別することを含む、請求項１６記載の方法。
【請求項１９】
前記仮想データ空間の前記非連続項目はそれぞれ、記憶空間内の選ばれた範囲のデータのユニークなアドレスを識別する高信頼記憶ユニット記述子（ＲＳＵＤ）を含み、また前記仮想データ空間内にＲＳＵＤが存在することを、前記関連する選ばれた範囲のデータのスナップショット・コピーが生成されたことの表示として用いる、請求項１６記載の機器。
【請求項２０】
前記形成するステップのメモリ空間はハードディスク・ドライブのアレイを含む記憶要素の一部を有する、請求項１６記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に効率の高いデータ照会のための機器および方法に関するものである。
【背景技術】
【０００２】
データ記憶装置はユーザ・データを記憶し、また読み出すために種々のアプリケーションに用いられている。データは内部記憶媒体（データ変換器のアレイによりアクセスされる１個以上の回転ディスクなど）に記憶されることが多い。これらの変換器は、トラックが定義されている媒体の種々の領域まで移動して入出力動作を行う。
【０００３】
記憶装置をグループ化して記憶アレイにすることにより統合された物理的記憶空間を形成して、冗長性、拡張性、および高いデータ処理速度を支援することができる。多くの場合、かかるアレイにはコントローラからアクセスし、コントローラはローカル・エリア・ネットワーク（ＬＡＮ）やインターネットなどのネットワーク構造（ファブリック）を介してホスト装置と通信する。多数の装置から仮想記憶空間を形成して、単一の仮想論理ユニット番号（ＬＵＮ）をネットワークに提示することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の種々の実施の形態は概して、効率の高いデータ照会のための装置および方法に導入されることを目的とする。
【課題を解決するための手段】
【０００５】
種々の実施の形態において、第１の部分が非連続項目を記憶する仮想データ空間として特徴付けられまた第２の部分が連続項目の第１のデータ・アレイとして特徴付けられるデータ構造を、記憶空間内に形成する。データ・アレイの少なくとも第１の連続項目はスキップ・リストを指し、データ・アレイの少なくとも第２の連続項目は第２のデータ・アレイを指し、少なくとも第３の連続項目は第１の部分内の選ばれた非連続項目を指す。
【発明の効果】
【０００６】
本発明によれば、効率の高いデータ照会を行う装置および方法を提供することができる。
【実施例】
【０００７】
図１は本発明の種々の実施の形態に係るデータ記憶装置の一例を示す。この装置は、ユーザ・データを記憶しまたホスト装置との間で転送するタイプのハードディスク・ドライブとして特徴付けられるが、これに限定されるものではない。
【０００８】
装置１００はベース・デッキ１０２と上部カバー１０４とで形成するハウジングを含む。スピンドル・モータ１０６は多数の記憶媒体１０８を回転方向１０９に回転させる。媒体１０８には、媒体に近接して配置されてヘッド・ディスク・インターフェース（ＨＤＩ）を形成する、対応するデータ変換器（ヘッド）１１０のアレイによりアクセスする。
【０００９】
ヘッド・スタック組立体（「ＨＳＡ」または「アクチュエータ」）を１１２で示す。ボイス・コイル・モータ（ＶＣＭ）１１４に電流を流すとアクチュエータ１１２は回転する。ＶＣＭ１１４は媒体表面上に定義されたトラック（図示せず）に変換器１１０を位置合わせして、データを記憶しまたは読み出す。可撓性の回路組立体１１６は、アクチュエータ１１２と、外部に設けられるプリント回路板（ＰＣＢ）１１８上の装置制御電子回路との間に電気通信経路を形成する。
【００１０】
或る実施の形態では、装置１００は図２に示すような多重装置知的記憶要素（ＩＳＥ）１２０内に組み込まれる。ＩＳＥ１２０は、データ記憶アレイ１２２を形成する複数のかかる装置１００を含む。ＩＳＥ１２０は更に、少なくとも１個のプログラム可能な知的記憶プロセッサ（ＩＳＰ）１２４と、関連するキャッシュ・メモリ１２６とを備える。アレイ１２２は大きな結合メモリ空間を形成し、データはこのメモリ空間にわたってストライピングされる（例えば選ばれたＲＡＩＤ（独立ディスクの冗長アレイ）構成内などに）。ＩＳＰ１２４はアレイ・コントローラとして動作し、アレイへのまたはアレイからのデータの転送を指示する。
【００１１】
ＩＳＥ１２０はコンピュータ・ネットワーク（すなわち、ファブリック１２８）を介して、ホスト装置１３０などの任意の数のホスト装置と通信する。ファブリックはインターネットやローカル・エリア・ネットワーク（ＬＡＮ）などを含む任意の適当な形をとってよい。ホスト装置１３０は個別のパーソナル・コンピュータ（ＰＣ）や遠隔ファイル・サーバなどでよい。必要に応じて、１個以上のＩＳＥ１２０を結合して仮想記憶空間を形成してよい。
【００１２】
好ましい実施の形態では、図２のＩＳＥ１２０内の装置１００はそれぞれ、約４テラバイト（ＴＢ）（４ｘ１０12バイト）の容量を有するものとして特徴付けられる。全部で１２８個のかかる装置（すなわち、全容量は約５１２ＴＢ）が考えられる。各装置１００を１／８の容量セグメントに分割してブックを形成する。１２８個の装置の中で、全部で１２８個のかかるブックを０％の予備で形成してよい。ブックを１６ＭＢのデータの集合に分割し、これを高信頼記憶ユニット（ＲＳＵ）と呼ぶ。
【００１３】
各ブック内のＲＳＵは個別の行番号により識別する。高信頼記憶ユニット記述子（ＲＳＵＤ）はこれに従ってアレイ内の各ＲＳＵを効率的に記述する。３２ビット（４バイト）のＲＳＵＤのフォーマットの一例を表１に示す。
【表１】
2009015840.tif 000003
【００１４】
好ましくはアレイ１２２内のデータ容量を、最大６４個のオリジナル論理ユニット番号（ＬＵＮ）を形成するように配列する。1個のオリジナルＬＵＮ当たり最大３個のスナップショットＬＵＮを設けてスナップショット（すなわち「前のバージョン」の）データを記憶する。これにより、ＩＳＥ１２０内に全部で最大２５６個のＬＵＮが形成される。スナップショットＬＵＮは好ましくはスナップショット・データ・コンテナ（ＳＤＣ）として配列する。
【００１５】
ご存知のように、スナップショット・データは一般に、通常のシステムの使用中にデータを変える前に、そのデータの前のバージョンを保存するためにコピーしたデータを含む。任意の数のスナップショット方式を用いてよい。例えば、スナップショットは通常の時間ベースで取ってもよいし、また事象発生ベースで取ってもよい（例えば、現在のデータに新たな書込み動作または削除動作を行う前に）。したがって、アレイ内に記憶されているデータのスナップショット状態を効率的に確認できることが望ましい。
【００１６】
記憶システムを設計するときにシステム設計者が決定しなければならないことの１つは、スナップショット動作でデータをコピーするときの「コピー・グレイン」のサイズ（すなわち、増分サイズ（境界））を選ぶことである。１２８Ｋなどの比較的小さなコピー・グレイン（ただしこれに制限されない）は、或る環境（ＲＡＩＤ−１など）や、システムが非常にランダムな負荷に曝される場合に有利であろう。なぜなら、一般にホストが記憶システムにアクセスする度にコピーするデータが少なくてすむからである。
【００１７】
しかし、小さなコピー・グレインを用いると、スナップショット状態を追跡するのに必要な処理オーバーヘッドが非常に大きくなることがある。例えば、個々のコピー・グレインの状態を示すために追加の状態ビット（例えば、参照ビットやゼロ・ビットなど）が必要なことがある。特に２ＭＢなどの大きなストライプ・サイズを用いるときにそうである。また、ＲＡＩＤ−５やＲＡＩＤ−６などの高いＲＡＩＤレベルは、一般に５１２ＫＢという大きなコピー・グレインを用いるようフォーマットされる。
【００１８】
また、或るタイプの負荷のスナップショット・コピーを処理するときに、データ記憶装置容量の使用効率が悪くなることがある。広い拡散を持つ比較的大きな転送（例えば、６４ＫＢから１２８ＫＢ）や小さなクラスタを持つ小さな転送（例えば、６４ＫＢから１２８ＫＢ）のランダムな入出力負荷は、５１２ＫＢの均一なコピー・グレインを用いることにより効率的に処理することができる。
【００１９】
それにもかかわらず、かかる転送において割り当てられるグレインは、多くの場合、１２８（１６ＭＢ）につき１つしかコピーグレインとして占めていない。メモリ使用の観点からすると、これによる効率は１％未満（１／１２８＜１％）である。更に、スナップショット・データを処理するには、コピー・グレイン毎に２個（ＲＡＩＤ−１）、５個（ＲＡＩＤ−５）、または６個（ＲＡＩＤ−６）の１２８ＫＢのデータ・ブロックのランダムな書込みを行うが必要である。
【００２０】
このため、ＩＳＥ記憶空間に関する状態情報（スナップショット情報など）を非常に効率的に処理するための新しいデータ配置を提供する。図３はこの配置を示すもので、トップ・レベル・マップ（ＴＬＭ）１３２、中間レベル・マップ（ＭＬＭ）１３４、およびグレイン・レベル・マップ（ＧＬＭ）１３６を含む。制限するものではないが、これらの構造はそれぞれ２ＫＢのメモリ空間を占め、これによりローカル・メモリ（例えば、図２のキャッシュ・メモリ１２６）とディスク・メモリ（例えば、図１の媒体１１０）の間の転送を必要に応じて効率的に行うことができると考えられる。
【００２１】
後で説明するが、好ましくは構造１３２、１３４、および１３６は、個別のグレインのスナップショット・コピーに関する照会をシステムが効率的に処理できるように配置する。この実施の形態の例では、スナップショット・コピーのグレイン・サイズは１２８ＫＢという小さなサイズである。ただしこれは例であって、制限するものではない。一般に、構造１３２、１３４、および１３６に連続的にアクセスして、所定のデータの集合について特定のスナップショット・コピーが存在するかどうか決定する。或るマップ構造内に一致するものが見つかった場合はスナップショット・コピーがすでに作られているので、システムはその通常の処理に進むことができる。データが存在しない場合は、システムは必要な割当ておよびコピー操作を行うことになる。
【００２２】
更に好ましくは、構造１３２、１３４、および１３６はスナップショット項目を蓄積する。これにより、全ストライプに相当するデータ（例えば、２ＭＢ）を蓄積した後にはデータの書込みを効率的に行うことができる。この構造はＩＳＰ１２４で処理するようになっているが、必要に応じて他の方法を用いてよい。
【００２３】
各ＴＬＭ１３２は一般に、ある範囲の仮想空間で直接データ・ルックアップを行うことができるフラット・マップ（すなわち、データ・アレイ）として特徴付けられる。好ましくは、２５６個のＬＵＮはそれぞれ対応するＴＬＭ１３２（全部で２５６個のＴＬＭ）を備える。これにより、各ＴＬＭは全記憶空間の約２ＴＢをマップする。
【００２４】
図４に示すように、関連するＴＬＭ１３２に３２ビットの特定のＶＢＡ（仮想ブロック・アドレス）値を供給する。この例では、この特定のアドレスに関してスナップショット・コピーが生成されているかどうか決定するためにＶＢＡを与える。より一般的に、ここでの動作はこの特定の３２ビット範囲内の値に関して或るデータが存在するかどうかを照会することを含むと考えてよい。
【００２５】
図のＴＬＭ１３２は全部で５１２項目を有する。シフト・ブロック１３８は好ましくは３２ビット入力のＶＢＡの値を２３ビット右にシフトして、最上位９ビットをＴＬＭの索引付けに用いる。５１２（２9）項目の中の関連する項目はいわゆる「ＭＬＭルックアップ値」を作成し、これを関連するＭＬＭ１３４に出力する。一般に、ＭＬＭ１３４はＳＤＣ（スナップショット・データ・コンテナ）内のデータを編成するのに用いられる。
【００２６】
各ＭＬＭ１３４は全記憶空間の４ＧＢをカバーし、第１の部分１４０および第２の部分１４２を含む。第１の部分１４０は仮想空間として特徴付けられ、最大２５６個の４バイトのＲＳＵＤを収容することができる。これらのＲＳＵＤはＴＬＭ１３２が参照するＳＤＣの４ＧＢのグレインの占められた部分を１６ＭＢのグレインでマップする。ＲＳＵＤの新しい項目を第１の部分１４０に追加することについては後で詳細に説明するが、ここでは、ＲＳＵＤは非連続の順番でよいと認識される。なぜなら、新しいＲＳＵＤはオリジナルＬＵＮへの入出力操作に応じて追加され、これはランダムな負荷に応じてよいからである。
【００２７】
４ＧＢスパンのＭＬＭは全部で３２，７６８個の１２８ＫＢグレインをカバーする。或るＲＳＵＤ項目が存在するということは、関連する１６ＭＢのＲＳＵＤスパン内のグレインの少なくとも１つまたは全てがコピーされたことを示す。
ＭＬＭ１３４の第２の部分１４２は、好ましくは最大２５６項目（ポインタ）を持つフラット・データ・アレイを含む。このデータ・アレイにより、ＴＬＭ１３２から供給されたルックアップ値から直接ルックアップを行うことが容易になる。第２の部分１４２内の各ポインタは１６ＭＢをカバーし、３つの異なる構造の１つを参照する。
【００２８】
好ましくは、ポインタ内の「セグメント化された」フラグ（０ｘ８０００００００）がセットされている場合は、その項目は、スキップ・リストとして配列された特定のセグメント化されたグレイン・レベル・マップ（ＳＧＬＭ）１４４を指す。セグメント化されたフラグがセットされていない場合は、その項目は特定のフラット・グレイン・レベル・マップ（ＦＧＬＭ）１４６を指す。これらの個別の構造にアクセスすることにより第１の部分１４０内の特定のＲＳＵＤを指す出力を作り、４ＧＢの空間内の３２，７６８個の１２８ＫＢグレインのどれがコピーされたかを識別するオフセット情報を与える。
【００２９】
各ＦＧＬＭ１４６は直接ルックアップが可能なフラット・データ・アレイとして配列され、ＭＬＭ１３４内の１２８ＭＢのマッピング境界で始まる８個の連続する項目により参照される１２８ＭＢをカバーする。参考までに、一組のＳＧＬＭ１４２の使用容量が、それがカバーする範囲に関する或るしきい値（満杯の１/４（例えば、全部で１２８ＭＢの揃った領域の中の３２ＭＢ）など）に達すると、ＳＧＬＭ１４２はＦＧＬＭ１４４に変換される。これは、一般にここでは単一のＦＧＬＭの方が一層効率的なマップ構造であろうという観察に基づいている。
【００３０】
または、ＭＬＭ１３４の第２の部分１４２内の各項目はＭＬＭ１３４の第１の部分１４０に索引を付けてよい。これが行われるのは、いわゆる間接ＲＳＵポインタ（ＩＲＰ）フラグ１４８（０ｘ４０００００００）がセットされている場合である。この場合はＭＬＭ項目の下位８ビットがＭＬＭ１３４内のＲＳＵＤアレイに索引を付け、これによりその中のＲＳＵＤを見つけることができる。ＲＳＵＤは１６ＭＢのコピー・グレインをマップする。すなわち、好ましくはＩＲＰフラグは、１６ＭＢスパンのＲＳＵＤにある１２８ＫＢのコピー・グレインのうち１２８個全てがコピーされたことを示す。
【００３１】
ここで分かるように、特定の４ＧＢのグレインのスナップショットを管理することは、次の自由な１２８ＫＢのグレインを見つける問題（システムのリブート後など）のためにやや困難なことがある。好ましくはこれに対処するため、ＲＳＵＤアレイが、割当てられた最後のＲＳＵ（最初の全てゼロの項目）を示して開始オフセット（ＳＧＬＭで用いられる）を与えるように、ＭＬＭ１３４の第１の部分１４０をフォーマットする。しかし、用いられた最後のオフセットを決定するには全てのＧＬＭ構造を走査する必要がある。１個以上のＩＲＰ項目では、最後のＲＳＵＤはＧＬＭの集合内に索引を有しないことがある。なぜなら、これはＩＲＰを介して参照するからである。しかし、これは走査中に決定することができる。
【００３２】
ＳＧＬＭ１４４のフォーマットは比較的明確なスキップ・リストである。当業者が認識するように、スキップ・リストは連結リストの１つの形式であって、リスト内の各項目（すなわち、ノード）はランダムな数の特別の正方向ポインタを有する。かかるリストの探索は２進トリーの探索に似ているが２進トリーに比べて維持のためのコストが非常に低い。
【００３３】
一般に、スキップ・リストは各ノード内のキー・フィールドを比較した結果に基づく順序に維持される。この比較は随意に選ばれ、昇順または降順、数または英数字、などでよい。新しいノードをリスト内に挿入するときは、一般に正方向ポインタの数を実質的にランダムにノードに割り当てるという方法を用いる。各ノードに関連する特別の正方向ポインタの数をノード・レベルと呼ぶ。
【００３４】
図４はスキップ・リストの一般化された構造を１５０で示す。その構造は、索引入力１５２、リスト・ヘッド１５４、ノードの母集団１５６（その最初の３つを一般にＡ，Ｂ，Ｃで示す）、およびヌル・ポインタ・ブロック１５８を含む。０からＮまでの正方向ポインタ（ＦＰ）を一般的に線１６０で表す。上に述べたように、索引１５２はＭＬＭ１３４から供給する。
【００３５】
各ノード１５６はそのノードの個別のキーによりアクセスする値（オフセット）である。各ノード１５６に関連する正方向ポインタ１６０の数は、リスト１５０に挿入するときに実質的にランダムに割り当てる。各ノードの特別の正方向ポインタの数をそのノードのノード・レベルと呼ぶ。
【００３６】
好ましくは、正方向ポインタ１６０の数はリストのサイズに関連して選ぶ。表２は、Ｎ個のノードの１つがｘ以上のレベルを有する多数の種々のノード・レベルのそれぞれにおけるノードの代表的な分布を示す。
【表２】
2009015840.tif 000004
【００３７】
ＬＺ（リーディング・ゼロ）列の値は一般に、関連するレベルの各ノードをアドレス指定することのできる索引値ビットの数に対応する（例えば、２ビットはレベル１内の４個のノードのアドレス指定が可能であり、４ビットはレベル２内の１６個のノードのアドレス指定が可能である、など）。表１は３０ビットの索引を用いて最大１，０７３，７４１，８２４（０ｘ４０００００００）個のポテンシャル・ノードのプールを与えることが分かる。
【００３８】
表２から分かるように、一般に４個のノードの中の１個は「０」より高いレベルを有する。すなわち、ノードの全母集団の２５％は１つ以上の特別の正方向ポインタを有する。逆に、４個のノードの中の３個（７５％）は一般に「０」のレベルを有する（特別の正方向ポインタはない）。同様に１６個のノードの中の３個は一般に「１」のレベルを有し、６４個のノードの中の３個は「２」のレベルを有する、などである。
【００３９】
リストが非常に大きくかつポインタの最大数が限られる場合は、一般にリストの探索に平均して最大レベルで約ｎ／２回の比較が必要である。ただし、ｎはそのレベルのノードの数である。例えば、ノードの数が１６，３８４個に限られかつ最大レベルが５である場合は、平均してレベル５に１６個のノード（１０２４個の中の１個）がある。したがって探索毎に、レベル４での比較に落とす前に一般に平均して８回の比較が必要であり、レベル４から０で平均２回の比較が必要である。
【００４０】
スキップ・リスト１５０の探索には一般にリスト・ヘッド１５４を用いる。リスト・ヘッド１５４は支援する最大レベルまでの正方向ポインタ１６０を識別する。ヌル・ポインタ１５８には特殊な値を用いてよい。ヌル・ポインタ１５８はリストの終わりより先を指すと解釈される。索引からレベルを得るので、ヌル・ポインタ値が「０」の場合はリストはやや不均衡になる。これは、「０」という索引は最大レベルの特定のノードを別のやり方で参照するからである。
【００４１】
ノードの総数は、索引フィールド内のビット数が表すことのできる最大数である２の累乗の半分より小さくなるように選ぶのが好ましいと考えられる。こうすることの利点は、最高のビット集合を持つ任意の値でヌル・ポインタを表すことができることである。例えば、１６ビットを用いて索引を記憶しかつ最大３２，７６８（索引範囲は０ｘ００００−０ｘ７ＦＦＦ）個のノードがあるとすると、０ｘ８０００と０ｘＦＦＦＦの間の任意の値をヌル・ポインタとして用いることができる。
【００４２】
ＳＧＬＭ１４４の好ましいメモリ構造を図７に示す。図７のＳＧＬＭ１４４は、アドレスを得たレベルと１バイトのポインタを持つ４レベルのスキップ・リストである。ＳＧＬＭ１４４は最大２５５個のキー／オフセット対を保持するよう形成される。
【００４３】
シフト・ブロック１６２で示すように、キーは好ましくは元の３２ビットのＶＢＡ入力値（図４参照）から下位（最下位）２３ビットを取り、８ビット右にシフトすることにより得られる。キー空間は好ましくは８ＧＢをカバーするので、４ＧＢのグレイン内の全てのキーは固有であることが分かる。図７から決定されるオフセットは、ＭＬＭ１３４の第１の部分１４０の仮想空間内の特定のＲＳＵＤを指す１６ビット（２バイト）のポインタを含む。
【００４４】
ＭＬＭ１３４のデータ・アレイ１４２（図５）内の複数の項目は同じＳＧＬＭ１４４を指すことができる。実際のところ、ＭＬＭ内の１つ以外の全ての項目（すなわち、２５６個の中の２５５個）は単一のＳＧＬＭを参照することができる。ＳＧＬＭ１４４はまばらに割当てられた（すなわち、比較的広く分離された）非近接値の情報を記憶するのに特に有用である。
【００４５】
好ましくは、新しいＳＧＬＭ構造を初期化するのにテンプレートを用いる。新しいＳＧＬＭはメモリの新しいセグメントにテンプレートをコピーすることにより作る。所定のＳＧＬＭ１４４内に記憶されている最高のオフセットを用いれば、所定のＭＬＭ内の次の自由な１２８ＫＢのグレインを簡単に見つけることができる。好ましくは、レベル２および３で探索するときは全部で３つのキャッシュ・ラインだけを参照する。新しい１２８ＫＢのグレインを追加する（新しいスナップショット・コピーが生成される）と、ＳＧＬＭを更新するだけでなく、その結果ＭＬＭ１３４も更新または作成し、さらにその結果ＴＬＭ１３２も更新する。
【００４６】
或る選ばれたＦＧＬＭ１４６を図８に概して示す。上に述べたように、各ＦＧＬＭは１２８ＭＢの空間内の８個の１６ＭＢの順次の項目をカバーするデータ・アレイである。ＭＬＭ１３４のデータ・アレイ１４２（図５）内で識別された項目を直接ルックアップとして用いて、ＦＧＬＭ１４６（図８）からポインタ値を出力する。前と同様に、ＦＧＬＭ１４６により出力されたポインタ値はＭＬＭ１３４の仮想空間１４０内の特定のＲＳＵＤ項目を指し、また１６ＭＢのスパンの特定のＲＳＵＤ項目内の特定の１２８ＫＢのグレインを指す。
【００４７】
ＭＬＭ自身に関連するオーバーヘッドをしばらく無視すると、６４ＧＢの容量を１ＭＢのＦＧＬＭ構造でマップし、また１６ＧＢの容量を１ＭＢのＳＧＬＭ構造でマップすることができると考えられる。各ＭＬＭ１３４は、最大２５６個のＳＧＬＭ１４４、最大３２個のＦＧＬＭ１４６、および最大２５６個のＩＲＰ（すなわち、仮想空間１４０のポインタ）を指すことができる。
【００４８】
全記憶容量の２５％がオリジナルでありかつフラット・マップされると仮定すると、１２８ＫＢのコピー・グレインで１９２ＭＢのデータ構造をマップに用いることができる。このマッピングの１００％がＳＧＬＭ構造を用いた場合は最大３ＴＢの容量をマップすることになるが、このマッピングの１００％がＦＧＬＭ構造を用いた場合は最大１２ＴＢの容量をマップすることになる。ほとんどの場合はこれらの構造を混合して用いると考えられる。すなわち、ＭＬＭデータ・アレイ内の少なくとも１項目はＳＧＬＭ１４４を指し、少なくとも１項目はＦＧＬＭ１４６を指し、少なくとも１項目は仮想空間１４０内のＲＳＵＤを指す。
【００４９】
種々のＴＬＭ、ＭＬＭ、およびＧＬＭ構造を背景の動作モードで用いて、ＲＡＩＤ−５またはＲＡＩＤ−６を含む任意の数の環境で、スナップショット・データを比較的小さなグレイン・サイズ（例えば、１２８ＫＢ）で効率的に追跡することができると考えられる。一般に、データの特定の部分をＩＳＥ記憶空間に書き込むデータ入出力操作に応じて、この処理の一部は、データのこの特定の部分のスナップショット・コピーがすでに存在するかどうかを決定することであると考えられる。存在する場合は、新しいものを作る理由はない。
【００５０】
したがって、入出力操作に関連するその特定の部分の関連するＶＢＡを該当するＴＬＭ構造（図４）に供給する。この入力は関連するＭＬＭルックアップ値を作成し、ＭＬＭルックアップ値は該当するＭＬＭ１３４のデータ・アレイ（図５の下部１４２）に索引を付ける。上に述べたように、出力項目は、ＭＬＭ仮想空間（図５の上部１４０）内の特定の項目か、スキップ・リストＳＧＬＭ１４４（図７）か、または第２のフラット・データ・アレイＦＧＬＭ１４６（図８）を指す。
【００５１】
第１の場合は、ＭＬＭ仮想空間内のその特定の項目が有効なＲＳＵＤの場合は、このＲＳＵＤはそのスナップショット・コピーの位置を識別する。同様に、第２および第３の場合は、関連するＳＧＬＭまたはＦＧＬＭの探索が正常に終わるとＭＬＭ仮想空間内の項目へのポインタを作成し、有効なＲＳＵＤが記憶されている場合はやはりスナップショット・コピーの位置を識別する。
【００５２】
他方で、仮想空間へのポインタがヌル値を与える場合、またはＳＧＬＭ／ＦＧＬＭ探索の結果何も見つからない場合は、この関連するデータのスナップショット・コピーは実際に存在しないと結論することができる。したがって、適当な空間を割り当て、スナップショット・コピーを作成して該当するメモリ位置（図２のキャッシュ・メモリ１２６など）に置き、新しいＲＳＵＤをＭＬＭ仮想空間（上部１４０）に追加し、対応するポインタの集合をＭＬＭデータ・アレイ（下部１４２）内に配置する。必要に応じて、項目をＳＧＬＭまたはＦＧＬＭに更に追加する。
【００５３】
最初は、ＭＬＭ１４０は空で（「次のオフセット」を示すヌル値は別として）、ＭＬＭデータ・アレイ内の全ての項目はヌル値を指すと考える。スナップショットが蓄積されるに従って、関連する値が１個以上のＳＧＬＭ（まばらにある場合）またはＦＧＬＭ（近接する場合）内に置かれる。上に述べたテンプレート・プロセスにより新しいＳＧＬＭを生成してよく、またノード数が増えるに従ってＳＧＬＭをＦＧＬＭに変換してよい。最終的に、全ＭＬＭ仮想空間が２５６個の項目で満たされ、データが媒体にストライプされると考える。
【００５４】
ここに述べた非常に効率的な小さな割当ておよびコピー・グレインの１つの利点はスナップショット・データを連続的に書き込むことができることである。しかし１つの限界は、ＶＢＡがＲＳＵの仮想空間内の予想位置に揃わないときは、コピー・グレインはデータの書込みを必要とすることである。この予想位置は、実際には上に述べたオフセットである。より詳しく述べると、オフセットは４ＧＢのグレインの始まりに関係し、１２８ＫＢのセグメントのアレイへの索引を表す。特定のＲＳＵでは、オフセットを１バイト（または７ビットでもよい）に減らして、ＲＳＵ内の１２８個のＲＡＩＤストライプ（１６ＭＢのＲＳＵ）のどれを参照しているかを示すことができる。
【００５５】
上に述べたように、完全なストライプに相当するデータを蓄積するまでは最後のストライプの書込みを避けるのが好ましい。ストライプを満たすデータを蓄積する前にシャットダウンが起こる可能性があることを除けば、これは一般に問題なく処理することができる。電源のシャットダウンに対する１つの対策はストライプを満たすのに十分なデータを単にコピーすることである。この方法の欠点は、実はそうではないのに、或るデータ集合が親データにおいて更新されたと他の状態情報が示す（１２８ＫＢのグレインで）ことがあることである。これは大きな問題ではなさそうである。なぜなら、グレイン・サイズが大きいときは、どのデータが書き込まれたかどうかを知ることは必ずしもできないからである。
【００５６】
上に述べた種々の例示の実施の形態は、データ記憶装置において小さなグレイン・スナップショット・コピーを用いる環境でデータ構造を用いることに向けてのものであったが、これは制限するものではないことは明らかである。むしろ、ここに示した種々のＴＬＭ、ＭＬＭ、およびＧＬＭ構造を用いて任意の数の異なるタイプのデータを処理することができる。これには、一般のデータ照会、インターネット・ウェブ資源の探索エンジンなどが制限なしに含まれる。
【００５７】
理解されるように、本発明の種々の実施の形態の多くの特徴および利点を、本発明の種々の実施の形態の構造および機能の詳細と共に上に説明したが、この詳細な説明は単なる例であって、詳細について、特に本発明の原理内の各部の構造および配置に関して、添付のクレームに示す用語の広い一般的意味が示す範囲において、変更を行ってよいものとする。
【産業上の利用可能性】
【００５８】
データ記憶装置を含む種々の情報処理装置もしくはシステムに利用できるであろう。
【図面の簡単な説明】
【００５９】
【図１】データ記憶装置の一例を示す
【図２】図１の装置を組み込んだネットワーク・システムを示す。
【図３】トップ・レベル・マップ（ＴＬＭ）、中間レベル・マップ（ＭＬＭ）、およびグレイン・レベル・マップ（ＧＬＭ）を含む図２のシステムのメモリ内のデータ構造を一般的に示す。
【図４】図３のＴＬＭを詳細に示す。
【図５】図３のＭＬＭを詳細に示す。
【図６】一般化されたスキップ・リストのフォーマットを示す。
【図７】図６に係るスキップ・リストとして配置されたセグメント化されたグレイン・レベル・マップ（ＳＧＬＭ）を示す。
【図８】直接ルックアップ・データ・アレイとしてのフラット・グレイン・レベル・マップ（ＦＧＬＭ）を示す。
【符号の説明】
【００６０】
１００  データ記憶装置
１０２  ベース・デッキ
１０４  カバー
１０６  スピンドル・モータ
１０８  記憶媒体
１０９  回転方向
１１０  変換器
１１２  アクチュエータ
１１４  ボイス・コイル・モータ
１１６  回路組立体
１１８  プリント回路板
１２０  ＩＳＥ
１２２  メモリ空間（データ記憶アレイ）
１２４  ＩＳＰ
１２６  キャッシュ・メモリ
１２８  ファブリック
１３０  ホスト
１３２  ＴＬＭ
１３４  ＭＬＭ
１３６  ＧＬＭ
１３８，１６２  シフト・ブロック
１４０  仮想データ空間
１４２  第１のデータ・アレイ
１４４  スキップ・リスト
１４６  第２のデータ・アレイ
１４８  間接ＲＳＵＤポインタ
１５２  索引入力
１５４  リスト・ヘッド
１５６  母集団
１５８  ヌル・ポインタ・ブロック
１６０  正方向ポインタ
【図１】
2009015840.tif 000005
【図２】
2009015840.tif 000006
【図３】
2009015840.tif 000007
【図４】
2009015840.tif 000008
【図５】
2009015840.tif 000009
【図６】
2009015840.tif 000010
【図７】
2009015840.tif 000011
【図８】
2009015840.tif 000012
【外国語明細書】
2009015840000001.pdf