(57)【要約】【課題】仮想記憶のスパース割当てのための２レベルマップ構造を提供する。【解決手段】仮想記憶空間にアクセスするための装置および方法を提供する。空間は、複数の記憶素子にわたって配列され、スキップリストは、選択された記憶素子から、仮想記憶空間の仮想ブロックアドレスの複数の非重複範囲の各々を個々のノードとしてマップするために使用される。【選択図】図３
2009015838.tif 000002
【特許請求の範囲】
【請求項１】
記憶素子を仮想記憶空間に配列するステップと、前記仮想記憶空間の仮想ブロックアドレス（ＶＢＡ）の複数の非重複範囲の各々を個々のノードとしてマップするためにスキップリストを使用するステップ、を含む方法。
【請求項２】
請求項１に記載の方法であって、前記使用するステップのＶＢＡの前記複数の非重複範囲は、前記記憶素子のデータ記憶装置のアレイ内の仮想アドレスであることを特徴とする、前記方法。
【請求項３】
請求項２に記載の方法であって、前記データ記憶装置の前記アレイは、ハードディスクドライブのアレイを含み、前記記憶素子はさらに、プロセッサおよびライトバックキャッシュメモリを含むことを特徴とする、前記方法。
【請求項４】
請求項１に記載の方法であって、さらに、キー値を提供するためにトップレベルマップをインデックスすることと、前記スキップリストにアクセスするために前記キー値を使用することを含むことを特徴とする、前記方法。
【請求項５】
請求項４に記載の方法であって、前記トップレベルマップの複数のエントリは、同じスキップリストをインデックスすることを特徴とする、前記方法。
【請求項６】
請求項１に記載の方法であって、前記使用するステップの前記スキップリストは、スキップリストヘッド、偶数長リンクエントリ（ＥＬＬＥ）のテーブル、奇数長リンクレベルエントリ（ＯＬＬＥ）のテーブル、短リンクエントリ（ＳＬＥ）のテーブル、およびフリーリストヘッドを有するセグメント化されたボトムレベルマップ（ＳＢＬＭ）として特徴付けられることを特徴とする、前記方法。
【請求項７】
請求項１に記載の方法であって、前記使用するステップの前記スキップリストは、セグメント化されたボトムレベルマップ（ＳＢＬＭ）として特徴付けられ、前記方法はさらに、前記ＳＢＬＭを、直接ルックアップアレイを含むフラットボトムレベルマップ（ＢＬＭ）に変換するステップを含み、前記フラットＢＬＭは、メモリにおいて前記ＳＢＬＭと同じ全体サイズを有することを特徴とする、前記方法。
【請求項８】
請求項１に記載の方法であって、前記配列するステップは、各々ハードディスクドライブのアレイを含む複数の記憶素子にわたる前記仮想記憶空間を形成するステップと、該記憶素子の各々に対して、そこに前記仮想記憶空間の非隣接範囲をマップするために、少なくとも１つのスキップリストを生成するステップを含むことを特徴とする、前記方法。
【請求項９】
仮想記憶空間に配列されたデータ記憶装置のアレイを含む記憶素子と、
前記仮想記憶空間の仮想ブロックアドレス（ＶＢＡ）の複数の非重複範囲の各々を個々のノードとしてマップするスキップリストとして特徴付けられる、前記記憶素子のメモリに格納されたデータ構造、
を含む、装置。
【請求項１０】
請求項９に記載の装置であって、前記データ記憶装置のアレイは、個々のハードディスクドライブのアレイを含むことを特徴とする、前記装置。
【請求項１１】
請求項１０に記載の装置であって、前記記憶素子はさらに、プロセッサおよびライトバックキャッシュメモリを含み、前記プロセッサは、該個々のハードディスクドライブの少なくともいくつかにわたってストライプされたデータのセグメントを識別するために、前記スキップリストを探索することを特徴とする、前記装置。
【請求項１２】
請求項９に記載の装置であって、前記データ構造はさらに、トップレベルマップ（ＴＬＭ）を含み、該トップレベルマップは、インデックスされると、前記スキップリストにアクセスするために使用されるキー値を提供することを特徴とする、前記装置。
【請求項１３】
請求項１２に記載の装置であって、前記ＴＬＭの複数のエントリは、同じスキップリストをインデックスすることを特徴とする、前記装置。
【請求項１４】
請求項９に記載の装置であって、前記スキップリストは、スキップリストヘッド、偶数長リンクエントリ（ＥＬＬＥ）のテーブル、奇数長リンクレベルエントリ（ＯＬＬＥ）のテーブル、短リンクエントリ（ＳＬＥ）のテーブル、およびフリーリストヘッドを有するセグメント化されたボトムレベルマップ（ＳＢＬＭ）として特徴付けられることを特徴とする、前記装置。
【請求項１５】
請求項９に記載の装置であって、前記スキップリストは、セグメント化されたボトムレベルマップ（ＳＢＬＭ）として特徴付けられ、前記記憶素子はさらに、前記ＳＢＬＭを、直接ルックアップアレイを含むフラットボトムレベルマップ（ＢＬＭ）に変換するよう構成されたプロセッサを含み、前記フラットＢＬＭは、メモリにおいて前記ＳＢＬＭと同じ全体サイズを有することを特徴とする、前記装置。
【請求項１６】
請求項９に記載の装置であって、さらに、前記仮想記憶空間がそこにわたって形成される複数の記憶素子を含み、前記複数の記憶素子の各々は、ハードディスクドライブのアレイを含み、前記複数の記憶素子の各々は、そこに前記仮想記憶空間の非隣接範囲をマップするために、少なくとも１つのスキップリストを関連するメモリに格納することを特徴とする、前記装置。
【請求項１７】
プロセッサと、メモリと、仮想記憶空間に配列されたデータ記憶装置のアレイを含む記憶素子と、
ノードのスキップリストとして特徴付けられる、該メモリにおける第１のデータ構造と、各ノードは、前記仮想記憶空間の仮想ブロックアドレス（ＶＢＡ）の非重複範囲の第１のセットに対応し、
前記仮想記憶空間に対する入力ＶＢＡ値に応答して、前記スキップリストに対するキー値を出力するデータアレイとして特徴付けられる、該メモリにおける第２のデータ構造、
を含む、装置。
【請求項１８】
請求項１７に記載の装置であって、前記第１のデータ構造の前記スキップリストは、第１のスキップリストとして特徴付けられ、前記装置はさらに、該メモリにおいて、前記第１のセットとは異なる、ＶＢＡの非重複範囲の第２のセットに各々対応するノードの第２のスキップリストとして特徴付けられる、第３のデータ構造を含むことを特徴とする、前記装置。
【請求項１９】
請求項１７に記載の装置であって、前記プロセッサは、前記データ記憶装置のアレイに関するデータ入出力操作のためのホストコマンドに応答して、前記第２のデータ構造にアクセスすることを特徴とする、前記装置。
【請求項２０】
請求項１７に記載の装置であって、前記プロセッサは、前記第１のデータ構造の前記スキップリストを、前記第２のデータ構造からの出力からの直接ルックアップを容易にするデータアレイとして特徴付けられる、該メモリにおける第３のデータ構造に変換することを特徴とする、前記装置。
【発明の詳細な説明】
【背景技術】
【０００１】
（技術背景）
データ記憶装置は、ユーザデータを格納および検索するために、様々なアプリケーションにおいて使用されている。データはしばしば、入出力操作を実行するために媒体の異なる半径範囲に動かされるデータトランスジューサのアレイによってアクセスされる、そこに定義されているトラックを有する、１つあるいは複数の回転可能ディスクのような、内部記憶媒体に格納される。
【０００２】
記憶装置は、冗長性、スケーラビリティ、および改良されたデータスループット速度をサポートするよう統合された物理的メモリ記憶空間を提供するために、記憶アレイにグループ化することができる。このようなアレイはしばしばコントローラによってアクセスされ、コントローラは今度は、ローカルエリアネットワーク（ＬＡＮ）、インターネット、等の構造を通して、ホスト装置と通信することができる。仮想記憶空間は、複数の装置から形成し、ネットワークに単一の仮想論理装置番号（ＬＵＮ）を提示することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
（要約）
本発明の多様な実施例は、一般に、仮想記憶空間にアクセスするための装置および方法に関する。
【課題を解決するための手段】
【０００４】
好ましい実施例によると、仮想記憶空間は、複数の記憶素子にわたって配列され、スキップリストは、選択された記憶素子から、仮想記憶空間の仮想ブロックアドレスの複数の非重複範囲の各々を個々のノードとしてマップするために使用される。
【実施例１】
【０００５】
図１は、本発明の多様な実施例による、例示的データ記憶装置を示している。装置は、ホスト装置にユーザデータを格納および転送するよう構成されている型のハードディスクドライブとして特徴付けられるが、このような型に限定されるものではない。
【０００６】
装置１００は、ベースデック１０２およびトップカバー１０４から形成されるハウジングを含む。スピンドルモータ１０６は、複数の記憶媒体１０８を回転方向１０９に回転させる。媒体１０８は、媒体に隣接して置かれヘッド・ディスクインタフェース（ＨＤＩ）を形成するデータトランスジューサ（ヘッド）１１０の対応するアレイによってアクセスされる。
【０００７】
ヘッド・スタックアセンブリ（“ＨＳＡ”即ち“アクチュエータ”）が１１２に示されている。アクチュエータ１１２は、ボイスコイルモータ（ＶＣＭ）１１４に電流が流されると回転する。ＶＣＭ１１４は、データをそこに格納するため、あるいはそこからデータを検索するために、媒体表面上に定義されたトラック（図示されていない）にトランスジューサ１１０を整列させる。フレックス回路アセンブリ１１６は、アクチュエータ１１２と、端に置かれたプリント回路基板（ＰＣＢ）１１８上の装置制御電子機器との間の電気的通信経路を提供する。
【０００８】
いくつかの実施例において、装置１００は、図２に示されるように、複数装置知的記憶素子（ｍｕｌｔｉ−ｄｅｖｉｃｅ  ｉｎｔｅｌｌｉｇｅｎｔ  ｓｔｏｒａｇｅ  ｅｌｅｍｅｎｔ：ＩＳＥ）１２０に組み込まれる。ＩＳＥ１２０は、データ記憶アレイ１２２に配列された、例えば４０個の装置の、複数のこのような装置１００を含む。ＩＳＥ１２０はさらに、少なくとも１つのプログラマブル知的記憶プロセッサ（ｐｒｏｇｒａｍｍａｂｌｅ  ｉｎｔｅｌｌｉｇｅｎｔ  ｓｔｏｒａｇｅ  ｐｒｏｃｅｓｓｏｒ：ＩＳＰ）１２４、および関連するキャッシュメモリ１２６を含む。アレイ１２２は、被選択ＲＡＩＤ（独立ディスクの冗長アレイ）構成におけるように、データがそれにわたってストライプされる、大規模な組み合わされたメモリ空間を形成する。ＩＳＰ１２４は、アレイにおよびアレイからデータを転送するよう指示するためのアレイコントローラとして動作する。
【０００９】
ＩＳＥ１２０は、コンピュータネットワーク、あるいは機構１２８を通して、任意の数の、例えばホスト装置１３０のような、ホスト装置と通信する。機構は、インターネット、ローカルエリアネットワーク（ＬＡＮ）、等を含む、任意の適当な形式を取ることができる。ホスト装置１３０は、個々のパーソナルコンピュータ（ＰＣ）、遠隔ファイルサーバ、等であってもよい。１つあるいは複数のＩＳＥ１２０を、必要に応じて、仮想記憶空間を形成するために組み合わせることができる。
【００１０】
新規のマップ構造が、仮想記憶空間へのアクセスを容易にするために使用される。図３に示されるように、これらの構造は、トップレベルマップ（ＴＬＭ）１３４およびボトムレベルマップ（ＢＬＭ）１３６を含むことが望ましい。特定の入出力要求に関連する、選択されたＶＢＡアドレスあるいはアドレスの範囲が、その範囲と関連するＢＬＭエントリを探し出すために、ＴＬＭに初期に提供されていることが望ましい。ＢＬＭは今度は、要求が、空間内の適切なロケーションに向けられるように、物理アドレスを識別するよう動作する。複数のＴＬＭエントリが、同じＢＬＭエントリを指すことができる。
【００１１】
ＴＬＭ１３４は、各インデックスが特定のＢＬＭエントリを指す、ＢＬＭインデックスのフラットテーブル（アレイ）として配列されることが望ましい。理解されるように、フラットテーブルにおける全てのアドレスは、直接ルックアップを有する。ＢＬＭエントリは今度は、記憶素子のための全ての仮想記憶を提供する単一のプールから、最も可用性の低いスキームを使用して、割り当てられている。ＴＬＭエントリのサイズは、ＢＬＭエントリのサイズと一致するように選択され、そうすることにより、ルックアップおよび割当ての双方における柔軟性がさらに向上する。この構造は、格納されたデータの実際の量が、使用可能な記憶域の量と比較して相対的に少ない、スパース割当て状況において特に有用である。
【００１２】
多様な実施例により、ＢＬＭエントリは、図４によって説明されるように、それぞれ独立したスキップリストとして特徴付けられることが望ましい。理解されるように、スキップリストは、リストにおける各項目あるいはノードが、余分な正方向ポインタの乱数を有する、リンクされたリストの１形式である。このようなリストを探索することは、２進法ツリーを探索することの性能に近く、一方、２進法ツリーと比較して、保守に関しては非常にコストが低い。
【００１３】
一般に、スキップリストは、各ノード内のキーフィールドの比較に基づき順番に保持されている。比較は任意に選択され、昇順あるいは降順、数字あるいはアルファベット−数字、等であってもよい。新しいノードをリストに挿入する場合、実質的に無作為に、正方向ポインタの数をノードに割り当てる方法が、一般的に使用される。各ノードに関連する余分な正方向ポインタの数は、ノードレベルと呼ばれる。
【００１４】
スキップリストのための一般化されたアーキテクチャは、図４における１４０において説明され、インデックス入力１４２、リストヘッド１４４、ノード１４６の母集団（これらの最初の３つは一般に、Ａ、Ｂ、Ｃと示されている）、および、ヌルポインタブロック１４８を含むよう示されている。０からＮの正方向ポインタ（ＦＰ）は一般に、ライン１５０によって表されている。インデックス１４２は、上記のように、ＴＬＭ１３４から供給される。
【００１５】
各ノード１４６は、そのノードに対するキーとして機能する、仮想空間内のＶＢＡアドレスの非重複範囲と関連付けられることが望ましい。各ノード１４６と関連する正方向ポインタ１５０の数は、リスト１４０への挿入の際に、実質的に無作為に割り当てられる。各ノードに対する余分な正方向ポインタの数は、そのノードに対するノードレベルと呼ばれる。
【００１６】
正方向ポインタ１５０の数は、リストのサイズと関連して選択される。表１は、Ｎノードの１つはｘ以上のレベルを有する、複数の多様なノードレベルの各々におけるノードの代表的な分布を示している。
【表１】
2009015838.tif 000003
【００１７】
ＬＺ（先行ゼロ）列における値は、一般に、関連するレベルにおいて各ノードをアドレス指定することができるインデックス値ビットの数に対応する（例えば、２ビットは、レベル１において４つのノードをアドレス指定することができ、４ビットは、レベル２において１６個のノードをアドレス指定することができ、以下同様である）。表１は、３０ビットのインデックスを使用すると、１，０７３，７４１，８２４（０ｘ４０００００００）の可能性のあるノードの最高のプールを提供することがわかる。
【００１８】
表１から、一般に、４つのノード中１つは“０”より大きいレベルを持つ、つまり、ノードの全母集団の２５％が１つあるいは複数の余分な正方向ポインタを持つことがわかる。反対に、４つのノード中３つ（７５％）は、一般に、レベル“０”を持つ（余分な正方向ポインタが無い）。同様に、１６個のノード中３つは、一般に、レベル“１”を持ち、６４個のノード中３つは、レベル“２”を持ち、以下同様である。
【００１９】
リストが非常に大きく、ポインタの最大数が限られている場合、リストの探索は、一般に、最高レベルにおいて、平均約ｎ／２比較を必要とする。ここでｎは、そのレベルにおけるノードの数である。例えば、ノードの数が１６，３８４個に限られていて、最高レベルが５の場合、ここにおける平均は、レベル５において１６個のノードとなる（１０２４個中１つ）。全ての探索は、このように一般に、平均して、レベル４における比較に至る前に８比較を必要とし、レベル４から０においては平均２比較を必要とする。
【００２０】
スキップリスト１４０を探索することは、一般に、リストヘッド１４４を使用することを含み、リストヘッド１４４は、サポートされる最高レベルまで正方向ポインタ１５０を識別する。ヌルポインタ１４８として特別の値を使用することができ、それは、リストの端を越えて指していると解釈される。インデックスからレベルを得ることは、ヌルポインタ値“０”が、リストを少しアンバランスにすることを意味する。このことは、インデックス“０”は、そうでなければ、最高レベルにおける特定のノードを参照するからである。
【００２１】
ノードの全数は、インデックスフィールドにおけるビットの数によって表すことができる２の最大べきの半分より少なくなるよう選択されることが望ましいと考えられる。このことにより、有利に、ヌルポインタを、最高のビットセットを有する任意の値によって表すことができる。例えば、インデックスと最高３２，７６８個のノード（インデックス範囲は０ｘ００００−０ｘ７ＦＦＦ）を格納するために１６ビットを使用すると、０ｘ８０００と０ｘＦＦＦＦの間の任意の値をヌルポインタとして使用することができる。  
【００２２】
好ましい実施例によると、ＢＬＭ１３６（ここでは、セグメント化されたＢＬＭ、あるいはＳＢＬＭ１４０と呼ばれる）における各独立したスキップリストは、ＴＬＭ１３４における複数のエントリからアドレス指定される空間から、低レベルエントリの個定数までマップする。ノード１４６は、選択されたＩＳＥ１２０と関連する仮想空間１３２内におけるＶＢＡ値の非重複範囲である。
【００２３】
より具体的には、図５に示されるように、特定のＳＢＬＭ１４０の各ノード１４６は、図５におけるＶＢＡ範囲０−Ｎのような、仮想ブロックアドレスの複数の非重複範囲の各々を、個々のノードとしてマップする。これらの範囲は、図２におけるＩＳＥ１２０のような、選択された記憶素子の仮想記憶空間から取られることが望ましい。
【００２４】
ＴＬＭ１３４の四分円（４分の１）内の任意の数のＴＬＭエントリは、その４分の１における範囲は重複しないので、所定のＢＬＭスキップリストを指すことができる。バイトインデックスは、スキップリストにアクセスするために使用されるキー値として使用され、各ノード１４６の実際のＶＢＡ範囲は、希望どおりの大きさとし、調整することができる。
【００２５】
各ＳＢＬＭ１４０は、６つのテーブルと３つの追加フィールドとして組織されることが望ましい。最初の３つのテーブルは、リンクエントリを格納する。１つのテーブルは、“偶数長リンクエントリ”（ＥＬＬＥ）構造のアレイを保持する。もう１つのテーブルは、“奇数長リンクエントリ”（ＯＬＬＥ）構造のアレイを保持する。第３のテーブルは、“短いリンクエントリ”（ＳＬＥ）構造のアレイを保持する。“長いリンクエントリ”（ＬＬＥ）は、４つの１バイトのリンク値から成る。“短いリンクエントリ”（ＳＬＥ）は、２つの１バイトのリンク値から成る。
【００２６】
ＳＢＬＭにおける次の２つのテーブルは、データ記述子データを保持する。１つは、ここではリライアブル記憶ユニット記述子（ＲＳＵＤ）と呼ばれる行アドレス値のための、４バイトのエントリを格納する。ＲＳＵＤは、任意の適当な形式を取ることができ、ＩＳＥ１２０（図２）内の関連するデータセグメント（リライアブル記憶ユニット）のために、ブックＩＤ、行ＩＤ、ＲＡＩＤレベル、等に関する情報を提供することが望ましい。参考のために、例示的３２ビットＲＳＵＤ形式を表２によって説明する。
【表２】
2009015838.tif 000004
【００２７】
表２の例示的ＲＳＵＤは、ＩＳＥアレイ（図２）における装置１００を８分の１の容量のセグメントに分割し、これらのセグメントからブックを形成することに基づいている。関連するアレイ内に１２８個の装置１００があれば、最高１２８のブックを予備０％で使用することができるであろう。従って、ブックＩＤ値は、７ビット（２7＝１２８）である。各装置１００が２ＴＢ（テラバイト、あるいは１０12バイト）の容量および８ＭＢのＲＳＵサイズを有すると仮定すると、そのＲＳＵに対する関連する行番号を特定するために、１８ビットが必要となる。
【００２８】
例示的ＳＢＬＭ構造の説明を続けると、そこにおける次のテーブルは、データに対するスナップショット状態のような状態情報を提供するために使用される、いわゆるＺビット値を保持するための２バイトのエントリを提供する（Ｚは“ゼロ化が必要である”ことを示す）。最後のテーブルは、“キーテーブル”（ＫＴ）と呼ばれ、２バイトのＶＢＡインデックス値を保持する。ＶＢＡインデックスは、ＶＢＡ全体の１６ビットを占める。ＶＢＡインデックスは、８ＭＢの仮想空間（１６Ｋセクタ）を参照するので、下位１４ビットは関係ない。ＶＢＡの上位２ビットは、ＴＬＭにおいて参照される４分の１から由来する。従って、ＳＢＬＭは、一般に、ＴＬＭの異なる４分の１におけるエントリ間で共有されない。
【００２９】
ＶＢＡインデックスは、ＳＢＬＭ１４０において実現されているスキップリストの探索に関する“キー”である。上記のように、各ＳＢＬＭは、アドレス由来のレベルおよび１バイトの相対的インデックスポインタを有するバランスのとれたスキップリストを実現する。スキップリストは、４つのレベルと最高２０１のエントリをサポートする。アドレス関連テーブル構造（ＡＲＴＳ）を使用すると、キーは、ポインタ値をインデックスとして使用することによって、キーテーブルに置かれる。ＲＳＵＤテーブルおよびＺビットテーブルは、エントリがキーに基づき見つけられると、同様に参照される。
【００３０】
上記のＳＢＬＭ１４０構造は、表３に例示されている。この構造は、合計２０１のエントリ（ノード）を収容する。
【表３】
2009015838.tif 000005
【００３１】
ＳＢＬＭは、“フリーリスト”が全てのＥＬＬＥ、ＯＬＬＥ、およびＳＬＥ構造を含むテンプレートによって初期化され、ノードが０から３のランダムなレベルで選ばれるように、エントリの“擬似ランダム”分布に等しい順番でリンクされる。ノードのレベルは、ＦＦＳ命令を使用して最初のビットセットを決定することによって、インデックスから得られる。インデックスは、０ｘ０１と０ｘＣ９の間で変化するので、このことにより、１と７の間の値が生成される。この数字は、０と３の間の値を生成するために右に１つシフトされ、そしてレベルを生成するために３から減算される。
【００３２】
全てのテーブルは、エントリインデックスにエントリのサイズを掛け、ベースを加算することによって、アクセスされる。リンクする目的のみのために、レベルが１より大きくインデックスが奇数であるかどうかを知るために、特別な検査を行ってもよい。その場合、ＯＬＬＥテーブルベースが、ＥＬＬＥテーブルベースの代わりに使用される。これらのファクタによって生成されたリストは、２０２と２５５およびその間のインデックスを有するエントリは存在しないので（表２のＳＢＬＭ１４０は、ノードの合計が２０１に限定されていることが望ましいので）、レベル０のエントリが期待されるより少ないかもしれないけれども（１９２の代わりに１３７）、名目上はバランスが取れている。
【００３３】
ＳＢＬＭ１４０は、ＴＬＭ１３４から参照される。一般に、任意の数のＳＢＬＭエントリは、ＴＬＭ１３４の同じ４分の１における任意の数のエントリから参照されてもよい。このことは、同じ４分の１からのエントリに対するキー空間において、重複がないからである。所定のキーが、ＴＬＭにおける適切なエントリによって指し示されるＳＢＬＭにおいて見つからない場合、それは、ＶＢＡアクセスに関してまだフラットであり、１つのエントリが、それが利用可能であれば、そのＳＢＬＭに挿入される。利用可能なものがない場合、ＳＢＬＭは、２ＧＢ境界に関する最適な分割ラインを見つけることに基づき、エントリの半分にできるだけ近づくことによって、分割される。このように、ＢＬＭ１３６内のＳＢＬＭ１４０の合計数は、仮想空間の利用レベルに関連して調整される。
【００３４】
特定のＳＢＬＭ１４０が単一のエントリのみを提供しているので、分割が可能でない場合、ＳＢＬＭは、“フラット”ＢＬＭ、つまり、ＲＳＵＤ値に対する直接ルックアップを提供するアドレスアレイ、に変換されることが望ましい。フラットＢＬＭは、ＳＢＬＭと同じだけのメモリを占有するが、２５６エントリまでを収容する。表２のＳＢＬＭは、従って、フラットＢＬＭの約５分の４効率的である（２０１／２５６＝７８．５１６％）。
【００３５】
この時点において、フラットＢＬＭ構造と比較して、ＳＢＬＭの有用性を簡単に説明することが役に立つであろう。この分野における技術者は、最初から気がつかれたであろうが、同じ量のメモリ空間に対して、ＳＢＬＭは、フラットＢＬＭと比較してより少ないエントリを保持し、スキップリスト探索を処理するために、追加的な処理資源を必要とする。
【００３６】
それにも関わらず、ＳＢＬＭは、メモリ管理の観点からすると望ましい場合がある。例えば、スパース割当ての場合、マップするためにいくつかのフラットＢＬＭを要求したかもしれないエントリは、単一のＳＢＬＭ構造に累積することができ、単一のリストから相対的に効率的な方法で探索することができる。
【００３７】
フラットＢＬＭへの次の変換は、ＳＢＬＭを、ＶＢＡアドレスインデックス（ＴＬＭエントリからの直接ルックアップのため）および関連するＲＳＵＤをルックアップデータ値として有する、単純なテーブル構造に置き換えることを含むことが望ましい。
【００３８】
ヌルエントリがＴＬＭにおいて見つかった場合、その近隣（同じ４分の１を含む）にあるいくつかの数の占有されたエントリが考慮されなければならない。空きパーセンテージが計算されなければならない。最も近いＳＢＬＭがおよそ５０％満杯より少ない場合、それは使用されるべきである。そうでなければ、空き容量および“近さ”の何らかの組合せに基づき１つを選択する何らかのアルゴリズムが、使用するＳＢＬＭを選択するために呼び出されるべきである。１つも見つけられなかった場合、新しいＳＢＬＭが割当てられ、ＳＢＬＭテンプレートにコピーすることにより初期化されるべきである。
【００３９】
提案されたＳＢＬＭデータ構造において、いわゆるＲビットは、これは、スナップショットＬＵＮを識別するものであるが（Ｒは“親における参照”を示す）、適切なキーを有するエントリのインデックスを使用してアクセスされる。Ｒビットは、Ｚビット細分性（例えば、５１２ＫＢ）と一致しない、コピーのためのグレインサイズ（例えば、１２８ＫＢ)かどうか問題を提示することができる。一方、ＺビットおよびＲビットの細分性が同じであった場合、より多くのデータをコピーする必要があるかもしれないが、Ｒビットの分離した使用は排除することができ、１つのＣビット（状態ビット）のみを使用することができる。元のＬＵＮに対して、Ｃビットは、データが一度は書き込まれたかどうかを示す。スナップショットＬＵＮに対して、Ｃビットは、ＬＵＮが実際にデータを保持しているかどうかを示す。書き込まれていないデータからコピーする必要がある場合、何のデータもコピーされるべきではなく、Ｃビットはクリアされるべきである。従って、単一のＣビットを使用することの不利益は、一般に、書き込まれていないデータがスナップショットにコピーされた後に、特定のデータセットが書き込まれていないデータかどうか決定することができないということである。
【００４０】
それにも関わらず、ＲビットおよびＺビットの双方を有することからＣビットのみを有することに変えることを検討する理由は、容量を保持するためにＲＡＩＤ−５あるいはＲＡＩＤ−６のいずれかを使用すると、スナップショットが形成される可能性が高いからである。効率的なＲＡＩＤ−６スキームを使用すると、コピーグレインは当然５１２ＫＢに選択されてもよく、これは、Ｚビットの細分性である。
【００４１】
ＳＢＬＭ１４０に対する代替的構造を、ここで簡単に説明する。この代替的構造は、例えば（しかしこれに限定されるものではなく）、２ＭＢのＲＡＩＤ−１ストライプサイズおよびＩＳＥ１２０における１２８個までの記憶装置１００を使用するスキームにおいて、有用である。
【００４２】
相対的に小さいコピーグレインサイズ、例えば１２８ＫＢ、を使用する利点の１つは、高度にランダムな負荷シナリオの下で、ＲＡＩＤ−１データをコピーすることのオーバヘッドを減少させることである。それにも関わらず、このようなより小さいグレインサイズは、一般に、１２８ＫＢグレインサイズをサポートするために必要なビットの数に関して、オーバヘッド要求を増大させることがある。ＲＡＩＤ−１データをコピーするための入出力要求に関して、５１２ＫＢ対１２８ＫＢのコピーグレインは、ストライプサイズが２ＭＢであるときの（あるいは１ＭＢであっても）、１２８ＫＢのストライプサイズに対するほどやっかいではないことがわかる。より大きいストライプサイズにおいて、まだ２つの入出力要求がある。性能データは、転送サイズを１２８ＫＢから５１２ＫＢに４倍にしたときに、ＩＯＰＳが半分未満に削減されることを提示している。
【００４３】
従って、ストライプサイズが２ＭＢに調整された場合、データセット（リライアブル記憶ユニット、あるいはＲＳＵＤにより識別されるＲＳＵ）は、サイズが８ＭＢから１６ＭＢに、２倍となることが望ましい。Ｒビットは、コピーグレインが５１２ＫＢに設定されているので（ＲＡＩＤ−５およびＲＡＩＤ−６もサポートする）、不必要である。
【００４４】
ＲＳＵサイズが１６ＭＢで、ＲＳＵＤにおける同じ数の“行ビット”を保存する場合（上で提案されたように）、各４ＴＢにおける１２８個のドライブをここで、ＲＳＵＤに関してサポートすることができる。ＴＬＭは、最高２ＴＢをマッピングしているときに、４ＫＢから２ＫＢに縮小し、フラットＢＬＭはここで２ＧＢの代わりに４ＧＢをマップすることができる。しかし、ＳＢＬＭにおけるエントリ（ノード）の数は、より大きなコピーグレインサイズに対する追加的ビットオーバヘッドのために、２０１から１６７に減少される。この代替的ＳＢＬＭ構造のための好ましい組織を、表４に説明する。
【表４】
2009015838.tif 000006
【００４５】
この第２のＳＢＬＭ構造は、フラットＢＬＭ構造の約２／３しか効率的ではないが（１６７／２５６＝６５．２３４％）、この第２の構造は、約２．６ＧＢの容量までマップすることができる。容量の２５％が“フラット”にマップされていると仮定すると、ＳＢＬＭエントリの１９２ＭＢが残ることになる。このことにより、仮想空間の２５０ＴＢを、セグメント化されたマッピングを使用してマップすることができ、仮想空間の１２８ＴＢを、フラットマッピングを使用してマップすることができる。全ての記憶装置がＲＡＩＤレベル０（２ＭＢのストライプサイズを有する）である想定される最悪の場合でも、容量の３７８ＴＢは、パートナーメモリの２５６ＭＢおよび媒体容量の２５６ＭＢを使用してマップすることができる。
【００４６】
本発明の多様な実施例の多くの特徴および利点を、本発明の多様な実施例の構造および機能の詳細と共に、上記説明において記述してきたが、この詳細な説明は例示のみであり、詳細、特に構造および部分の配列に関して、付随する請求項が表される用語の広い一般的な意味によって示される最大の範囲まで、本発明の趣旨内において変更が可能であることを理解されたい。
【図面の簡単な説明】
【００４７】
【図１】図１は、例示的データ記憶装置を示す図である。
【図２】図２は、図１の装置を組み込んだネットワークシステムを示す図である。
【図３】図３は、図２の仮想空間と関連して使用されるトップレベルマップ（ＴＬＭ）およびボトムレベルマップ（ＢＬＭ）構造のそれぞれを一般的に示す図である。
【図４】図４は、図３のＢＬＭの好ましい配列を、スキップリストとして一般的に示す図である。
【図５】図５は、図２の選択されたＩＳＥ上の非隣接ＶＢＡ範囲を相応して示す図である。
【符号の説明】
【００４８】
１００  装置
１０２  ベースデック
１０４  トップカバー
１０６  スピンドルモータ
１０８  記憶媒体
１０９  回転方向
１１０  データトランスジューサ
１１２  ヘッド・スタックアセンブリ
１１４  ボイスコイルモータ
１１６  フレックス回路アセンブリ
１１８  プリント回路板
１２０  知的記憶素子（ＩＳＥ）
１２２  データ記憶アレイ
１２４  知的記憶プロセッサ（ＩＳＰ）
１２６  キャッシュメモリ
１２８  機構
１３０  ホスト装置
１３４  トップレベルマップ（ＴＬＭ）
１３６  ボトムレベルマップ（ＢＬＭ）
１４０  アーキテクチャ
１４２  インデックス入力
１４４  リストヘッド
１４６  ノード
１４８  ヌルポインタブロック
１５０  ライン
【図１】
2009015838.tif 000007
【図２】
2009015838.tif 000008
【図３】
2009015838.tif 000009
【図４】
2009015838.tif 000010
【図５】
2009015838.tif 000011