(57)【要約】記憶装置ネットワーク上のデータへのアクセスを共有する複数のアクセス・ノードは、ディレクトリ編成キャッシュ所有権スキームを実現する。グローバル・コーディネータとして指定された1つのノードが、アクセス・ノードによる入出力動作に関する情報を記憶するディレクトリ（例えば、テーブルまたは他のデータ構造）を維持する。入出力動作が識別データ上で実行されるとき、他のノードは、要求をグローバル・コーディネータへ送る。ディレクトリ内のそのデータの所有権は最初の要求ノードへ与えられる。ディレクトリ項目が使用されないか、休止している場合、所有権は他のノードへ移転してもよい。分散ディレクトリ編成キャッシュ・コヒーレンスは、リモート・データへの局所化された（キャッシュされた）アクセスを許可することによって、地理的に離れたアクセス・ノード間の帯域幅要件を低減することができる。2008506195.tif 000003
2008506195.tif 000002
【特許請求の範囲】
【請求項１】
ページ所有権項目のディレクトリを維持することによって、トラフィック・スケーラビリティを維持するように、データ記憶装置ネットワークへのアクセスを共有するデータ・アクセス・ノード間で送られるメッセージの数を低減する方法であって、項目の所有権が、最初に、項目内のページへのアクセスを要求する最初のアクセス・ノードへ付与され、項目の所有権が、ノード間で送られる同期メッセージの数を低減するように、より多くの頻度で項目内のページへアクセスするノードへ自動的に移転する方法。
【請求項２】
データ記憶装置ネットワーク内のデータへのアクセスを共有する地理的に離れたアクセス・ノード間の帯域幅を低減する方法であって、以下の段階を含む方法：
アクセス・ノードに対してローカルにデータをキャッシュし、そのノードについてそのデータへの局所化されたキャッシュ・アクセスを提供する段階；および
ディレクトリ編成所有権スキームを使用して、アクセス・ノード間でキャッシュ・データについてデータ・コヒーレンスを維持する段階。
【請求項３】
データ記憶装置ネットワークにおいて、データ・アクセス・ノードの分散された集合の中でキャッシュ間のキャッシュ・コヒーレンスを提供する方法であって、以下の段階を含む方法：
データ記憶装置ネットワークへのアクセスを共有する複数のアクセス・ノードの少なくとも1つにディレクトリを維持し、該ディレクトリが複数のアクセス・ノードによってアクセスされるデータに関する情報を記憶する段階；
最初のデータ・アクセス・ノードで、ホスト・システムからのデータ・アクセス要求を受け取り、該データ・アクセス要求が、処理されるべきデータを識別する段階；
最初のアクセス・ノードが、識別されたデータをキャッシュ内に記憶しているかどうかを決定する段階；および、記憶していない場合、
ディレクトリを使用して、複数のアクセス・ノード内の他のノードが、識別されたデータのコピーをキャッシュ内に記憶しているかどうかを決定する段階；および、
ノードが、識別されたデータのコピーをキャッシュ内に記憶している場合、要求しているノードが、識別されたデータを記憶装置からアクセスする必要がないようにするための、識別されたデータを共有する共有要求、またはそのノードのキャッシュ内に記憶されたデータのコピーを無効にする無効要求、の1つをそのノードに送る段階。
【請求項４】
データ・アクセス要求がデータ読み出し要求であり、ノードが、識別されたデータのコピーをキャッシュ内に記憶していない場合、さらに以下の段階を含む、請求項3記載の方法：
識別されたデータを記憶装置から検索する段階；および
要求しているノードを、識別されたデータの所有者として識別する新しい項目をディレクトリの中に作成する段階。
【請求項５】
データ・アクセス要求が書き込み要求であり、ノードが、識別されたデータのコピーをキャッシュ内に記憶していない場合、さらに以下の段階を含む、請求項3記載の方法：
要求しているノードのキャッシュへ書き込まれるデータをコミットする段階。
【請求項６】
データ・アクセス要求が書き込み要求であり、1つまたは複数の他のノードが、識別されたデータのコピーをキャッシュ内に記憶している場合、識別されたデータのコピーをキャッシュ内に記憶している他のノードへ無効要求を送る段階をさらに含む、請求項3記載の方法。
【請求項７】
データ・アクセス要求が更新要求であり、要求しているノードが、識別されたデータのコピーをキャッシュ内に記憶している場合、および、ここで1つまたは複数の他のノードが、識別されたデータのコピーをキャッシュ内に記憶している場合、識別されたデータのコピーをキャッシュ内に記憶している他のノードへ無効要求を送る段階をさらに含む、請求項3記載の方法。
【請求項８】
データ・アクセス要求が更新要求であり、要求しているノードが、識別されたデータのコピーをキャッシュ内に記憶していない場合、および、ここで1つまたは複数の他のノードが、識別されたデータのコピーをキャッシュ内に記憶している場合、さらに以下の段階を含む、請求項3記載の方法：
最後にデータを書き込んだノードへ共有無効要求を送る段階；および
識別されたデータのコピーをキャッシュ内に記憶している他のノードへ無効要求を送る段階。
【請求項９】
以下の段階をさらに含む、請求項3記載の方法：
他のノードが、データ・アクセス要求によって識別されたデータの上にディレクトリロックを有するかどうかを決定する段階；
ノードがデータの上にディレクトリロックを有さない場合、識別されたデータの上のディレクトリロックを最初のアクセス・ノードへ付与する段階；および
ノードがデータの上にディレクトリロックを有する場合、ロックを最初のアクセス・ノードへ付与する前に、ロックが解放されるのを待機する段階。
【請求項１０】
所有されないディレクトリ項目が、対応するデータ・ページにアクセスする最初のアクセス・ノードに対してローカルに置かれ、最初のアクセス・ノードがディレクトリ項目の所有権を与えられる、請求項3記載の方法。
【請求項１１】
データ・アクセス要求が、データのページ、データのサブページ、またはデータの複数ページの1つを識別する、請求項3記載の方法。
【請求項１２】
データ・アクセス要求が、データ読み出し要求、データ書き込み要求、およびデータ更新要求の1つである、請求項3記載の方法。
【請求項１３】
トラフィック・スケーラビリティを維持するように、データ記憶装置ネットワークへのアクセスを共有するデータ・アクセス・ノード間で送られるメッセージの数を低減する方法であって、以下の段階を含む方法：
複数のデータ・アクセス・ノードによってアクセスされるデータに関する情報を記憶するディレクトリを維持し、該ディレクトリがデータ記憶装置ネットワーク内のデータの1つまたは複数のページを表す項目を含む段階；
最初のデータ・アクセス・ノードで、ホスト・システムからのデータ・アクセス要求を受け取り、該データ・アクセス要求が、処理されるべきデータを識別する段階；
グローバルディレクトリコーディネータを使用して、ノードが、識別されたデータについてディレクトリ項目の所有権を有するかどうかを決定する段階；
ノードがディレクトリ項目の所有権を有さない場合、識別されたデータについてディレクトリ項目の所有権を最初のアクセス・ノードへ付与する段階；および
ノードが項目の所有権を有する場合、そのノードを最初のノードに識別する段階。
【請求項１４】
アクセス・ノードの1つが、グローバルディレクトリコーディネータとして指定され、ここでグローバル・コーディネータがディレクトリ項目の所有権を付与する、請求項13記載の方法。
【請求項１５】
データ・アクセス要求が、データ読み出し要求、データ書き込み要求、およびデータ更新要求の1つであり、ここでデータ・アクセス要求が、データのページ、データのサブページ、またはデータの複数ページの1つを識別する、請求項13記載の方法。
【請求項１６】
最初のアクセス・ノードがディレクトリをメモリ内のテーブルとして維持し、ここで決定することが、ディレクトリテーブル内でルックアップを実行することを含む、請求項13記載の方法。
【請求項１７】
項目が現在使用されていない場合、ディレクトリ項目の所有権を現在の所有者から最初のアクセス・ノードへ移転する段階をさらに含む、請求項13記載の方法。
【請求項１８】
データ記憶装置ネットワークへのアクセスを共有する複数のデータ・アクセス・ノード間でキャッシュ・コヒーレンスを維持するシステムであって、
データを記憶する記憶装置システムと、
ノードの1つが複数のデータ・アクセス・ノードによってアクセスされるデータに関する情報を記憶するディレクトリ（ディレクトリノード）を維持するように構成され、該ディレクトリがデータ記憶装置ネットワーク内のデータの1つまたは複数のページを表す項目を含む、記憶装置システム内のデータにアクセスするように構成された複数のアクセス・ノードとを含み、
ここで処理されるべきデータを識別するデータ・アクセス要求をホストから受け取ると、最初のアクセス・ノードが要求をディレクトリノードへ送り、ディレクトリノードが、識別されたデータについてディレクトリ項目の所有権をノードが有するかどうかを決定し、ノードがディレクトリ項目の所有権を有さない場合、ディレクトリノードが、識別されたデータについてディレクトリ項目の所有権を最初のアクセス・ノードへ付与し、ノードが項目の所有権を有する場合、ディレクトリノードが、そのノードを最初のアクセス・ノードに識別する、システム。
【請求項１９】
第2のアクセス・ノードが所有権を要求し、ディレクトリ項目が使用されていない場合、識別されたデータについてディレクトリ項目の所有権が第2のアクセス・ノードへ変更される、請求項18記載の方法。
【請求項２０】
1つまたは複数のアクセス・ノードが、他のノードから地理的に離れている、請求項18記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、データ記憶装置ネットワーク上で1つまたは複数のデータ記憶装置アクセス・ノードを横切ってデータを共有することに関し、さらに具体的には、データ記憶装置アクセス・ノードの分散ネットワークを横切ってディレクトリ編成キャッシュ・コヒーレンスを提供するシステムおよび方法に関する。
【０００２】
関連出願の相互参照
本出願は、2004年7月7日に出願された米国仮出願第60/586,364号の恩典を主張する。この仮出願は、参照として全体が本明細書に組み入れられる。
【背景技術】
【０００３】
発明の背景
現在の記憶装置ネットワーク、および特に、地理的にリモートのアクセス・ノードおよび記憶装置リソースを含む記憶装置ネットワークにおいて、リソースおよびアクセス・ノード間の帯域幅を維持または低減することが高度に望ましい。したがって、さらに、ホスト・デバイスによって要求されたページへのアクセス速度を多少改善するため、データ・アクセスを局所化することが望ましい。アクセス・ノードでページをキャッシュすることは局所化を提供するが、キャッシュされたデータは、同じデータをキャッシュしているかもしれない他のアクセス・ノードでの修正に関して、コヒーレントに維持されなければならない。しかし、現在の記憶装置ネットワーク・アクセス解決法は、記憶装置ネットワーク・アクセス・ノードでページをローカルにキャッシュする実用的コヒーレンス・メカニズムを提供しない。
【０００４】
したがって、上記および他の問題点を克服する効率的なデータ局所化およびキャッシュ・コヒーレンス・システムおよび方法を提供することが望ましい。そのようなシステムおよび方法は、さらに、記憶装置ネットワーク・アクセス・ノード間で、低減された帯域幅の使用またはメッセージング要件を提供すべきである。
【発明の開示】
【０００５】
発明の簡単な概要
本発明は、データ記憶装置アクセス・ノードの分散ネットワークを横切ってディレクトリ編成キャッシュ・コヒーレンスを実現するシステムおよび方法を提供する。
【０００６】
本発明によれば、記憶装置ネットワークでデータへのアクセスを共有する複数のアクセス・ノードは、ディレクトリ編成キャッシュ所有権スキームを実行する。グローバル・コーディネータとして指定された1つのノードが、アクセス・ノードによる入出力動作に関する情報を記憶したディレクトリ（例えば、テーブルまたは他のデータ構造）を維持する。他のノードは、識別データ上で入出力動作を実行しようとするとき、要求をグローバル・コーディネータへ送る。ディレクトリ内のそのデータの所有権は、最初の要求ノードへ与えられる。ディレクトリの項目が使用されないか休止していれば、所有権は他のノードへ移転してよい。本発明によれば、分散ディレクトリ編成キャッシュ・コヒーレンスは、リモート・データへの局所化された（キャッシュされた）アクセスを可能にすることによって、地理的に離れたアクセス・ノード間の帯域幅要件を低減することができる。
【０００７】
本発明の1つの局面によれば、トラフィック・スケーラビリティを維持するように、データ記憶装置ネットワークへのアクセスを共有するデータ・アクセス・ノード間で送られるメッセージの数を低減する方法が提供される。本方法は、典型的には、ページ所有権項目のディレクトリを維持することを含む。その場合、項目の所有権は、当初に、項目内のページへのアクセスを要求する最初のアクセス・ノードへ付与され、項目の所有権は高い頻度で項目内のページにアクセスしているノードへ自動的に移転し、ノード間で送られる同期メッセージの数が低減される。
【０００８】
本発明の他の局面によれば、データ記憶装置ネットワーク内でデータへのアクセスを共有する地理的に離れたアクセス・ノード間で帯域幅を低減する方法が提供される。本方法は、典型的には、アクセス・ノードについてローカルにデータをキャッシュし、そのノードのためにそのデータへの局所化されたキャッシュ・アクセスを提供し、ディレクトリ編成所有権スキームを使用してアクセス・ノード間でキャッシュ・データについてデータ・コヒーレンスを維持することを含む。
【０００９】
本発明のさらに他の局面によれば、データ記憶装置ネットワーク内でデータ・アクセス・ノードの分散された集合におけるキャッシュ間のキャッシュ・コヒーレンスを提供する方法は、典型的には、データ記憶装置ネットワークへのアクセスを共有する複数のアクセス・ノードの少なくとも1つの中にディレクトリを維持すること、複数のアクセス・ノードによってアクセスされるデータに関する情報をディレクトリが記憶すること、最初のデータ・アクセス・ノードでホスト・システムからのデータ・アクセス要求を受け取ること、処理されるべきデータをデータ・アクセス要求が識別することを含む。本方法は、さらに、典型的には、最初のアクセス・ノードが、識別されたデータをキャッシュに記憶されているかどうかを決定すること、記憶されていない場合、ディレクトリを使用して、複数のアクセス・ノードの中の他のノードが、識別されたデータのコピーをキャッシュに記憶されているかどうかを決定すること、或るノードが、識別されたデータのコピーをキャッシュに記憶されていれば、識別されたデータを共有するための共有要求の1つをそのノードへ送って、要求しているノードが記憶装置から識別データにアクセスする必要がないようにするか、そのノードのキャッシュに記憶されたデータのコピーを無効にするための無効要求を送ることを含む。
【００１０】
本発明の更なる局面によれば、データ記憶装置ネットワークへのアクセスを共有するデータ・アクセス・ノード間で送られるメッセージの数を低減して、トラフィック・スケーラビリティを維持する方法が提供される。本方法は、典型的には、複数のデータ・アクセス・ノードによってアクセスされるデータに関する情報を記憶するディレクトリを維持すること、データ記憶装置ネットワーク内のデータの1つまたは複数のページを表す項目をディレクトリが含むこと、最初のデータ・アクセス・ノードでホスト・システムからのデータ・アクセス要求を受け取ること、処理されるべきデータをデータ・アクセス要求が識別することを含む。本方法は、さらに、典型的には、グローバルディレクトリコーディネータを使用して、識別されたデータについてディレクトリ項目の所有権を或るノードが有するかどうかを決定すること、ディレクトリ項目の所有権を有するノードが存在しない場合、識別されたデータについてディレクトリ項目の所有権を最初のアクセス・ノードへ付与すること、或るノードが項目の所有権を有する場合、そのノードを最初のノードに識別することを含む。このようにして、最初のノードは、識別されたノードと通信して、入出力要求を処理することができる。
【００１１】
更なる局面によれば、データ記憶装置ネットワークへのアクセスを共有する複数のデータ・アクセス・ノード間のキャッシュ・コヒーレンスを維持するシステムが提供される。システムは、典型的には、データを記憶する記憶装置システム、およびホスト要求に応答して記憶装置システム内のデータにアクセスするように構成された複数のアクセス・ノードを含む。ノードの1つは、典型的には、複数のデータ・アクセス・ノードによってアクセスされるデータに関する情報を記憶するディレクトリ（ディレクトリノード）を維持するように構成される。ディレクトリは、データ記憶装置ネットワーク内のデータの1つまたは複数のページを表す項目を含む。動作において、処理されるべきデータを識別するデータ・アクセス要求をホストから受け取ると、最初のアクセス・ノードは要求をディレクトリノードへ送る。ディレクトリノードは、識別されたデータについてディレクトリ項目の所有権をノードが有するかどうかを決定し、ディレクトリ項目の所有権を有するノードが存在しない場合、ディレクトリノードは、識別されたデータについてディレクトリ項目の所有権を最初のアクセス・ノードへ付与し、或るノードが項目の所有権を有する場合、ディレクトリノードはそのノードを最初のアクセス・ノードに識別する。
【００１２】
図面および特許請求の範囲を含む明細書の残りの部分を参照すると、本発明の他の特徴および利点を理解できるであろう。本発明の更なる特徴および利点、ならびに本発明の様々な態様の構造および動作は、添付の図面に関して下記で詳細に説明される。図面において、同様の符番は同一または機能的に類似した要素を示す。
【００１３】
発明の詳細な説明
1つの態様によれば、ディレクトリマネージャ・モジュールまたはDMGが提供される。DMGは、データ・アクセス・ノードの分散された集合を横切って、共有されたデータについてキャッシュ・コヒーレンス・メカニズムを提供する責任を有する。共有されるデータ・ボリュームからデータをキャッシュしているノードの集合は、共有グループと呼ばれる。一般的に、DMGモジュールは、ノード内のプロセッサまたは他の知能モジュール（例えば、ASIC）上で実行しているソフトウェアを含む。DMGモジュールは、単一のノードの中で実現されるか、複数の相互に通信するノードを横切って分散される。或る局面において、アクセス・ノードは、コントローラ・デバイスまたはブレードとして具体化される。コントローラ・デバイスまたはブレードは、記憶装置ネットワーク、例えば、記憶装置エリア・ネットワーク（SAN）へ通信可能に結合される。これは、記憶装置ネットワーク上に記憶されたデータへのアクセスを可能にする。しかし、アクセス・ノードは、知能ファブリック・スイッチまたは他のネットワーク・デバイス、例えば、ハブ・アダプタとしても具体化可能であることが分かるであろう。局所意識ディレクトリ移行（LCDM）をデータベースへ適用することができるから、DMG機能を有するアクセス・ノードとして動作するように、任意のネットワーク計算ノードを構成することができる（例えば、ネットワーク接続を有するデスクトップ・コンピュータ上で、DMGを実行することができる）。参照として全体が組み入れられる米国特許第6,148,414号は、本発明の局面の実現が特に有用であるコントローラ・デバイスおよびノードを開示している。
【００１４】
図1は、本発明に従った基本ネットワーク構成を示す。図示されるように、複数のネットワーク・クライアント101〜10Nは、複数のアクセス・ノード・デバイス201〜20N（アクセス・ノード）と通信可能に結合される。アクセス・ノードの各々は、プロセッサ・コンポーネント22、例えば、マイクロプロセッサまたは他の知能モジュール、キャッシュ24（例えば、RAMキャッシュ）および/または他のローカル記憶装置、通信ポート（図示されず）およびDMGモジュール26のインスタンスを含む。（一般的に、「N」は、本明細書において、無限の複数を示すために使用され、1つのコンポーネントを参照するときの数「N」は、異なるコンポーネントの数「N」と必ずしも等しくない。例えば、クライアント10の数は図1のアクセス・ノード20の数と等しくないが、等しくてもよい）。各々のクライアント10は、好ましくは、ローカル・ネットワーク接続15を介して1つまたは複数のノード20へ通信可能に結合されるが、クライアントは、特定の応用およびノード20に対する地理的ロケーションに要求される任意の数の接続スキームを介して、ノード20と通信可能に結合されてよい。接続スキームには、例えば、直接有線または無線接続、インターネット接続、任意のローカル・エリア・ネットワーク（LAN）型接続、任意のメトロポリタン・エリア・ネットワーク（MAN）接続、任意の広域ネットワーク（WAN）型接続、VLAN、任意のプロプラエタリ・ネットワーク接続などが含まれる。各々のノード20は、さらに、典型的には、1つまたは複数のAMFを含むか、それらと通信可能に結合され、ネットワーク50、例えば、記憶装置エリア・ネットワーク（SAN）、LAN、WAN、MANなどを介して、1つまたは複数の記憶装置リソース40と通信可能に結合される。記憶装置リソース40の各々は、1つまたは複数のディスク・ドライブを含む。ノード20は、ローカル・ネットワーク接続を介して1つまたは複数の記憶装置リソースへ結合されることが好ましい。ノード20は、相互に物理的に接近して位置するか、1つまたは複数のノードが他のノードからリモートに、例えば、地理的リモートに位置してよい。アクセス・ノード20は、さらに、ネットワーク50および/または他の通信ネットワークまたはメディアを介して、例えば、PCIバスまたはバックボーンまたはファイバーチャネル・ネットワークを介して、またはネットワーク15を介して、他のノードと相互に通信することができる。
【００１５】
本発明によれば、分散キャッシュ・コヒーレンスは、リモート・データへの局所化された（キャッシュされた）アクセスを可能にすることによって地理的に離れたアクセス・ノード間で帯域幅要件を低減するために重要である。1つの局面によれば、データをキャッシュできなければ、データ・アクセスを局所化できないが、リモートのアクセス・ノードでの修正に関してデータをコヒーレントに保持できなければ、データをキャッシュすることは安全でない。DMGの任意の態様はキャッシュ・コヒーレンスの正確度要件を満足させるが、多くの実現方法の高いオーバヘッドは、局所化されたキャッシュ・アクセスの利点を上回る。下記で説明される本発明のLCDM態様は、十分に低いオーバヘッドで、局所化されたキャッシュ・アクセスを実用的で有利にすることを証明した。
【００１６】
DMG内の基本コヒーレンス単位はページ（記憶装置の論理ブロック）であるが、DMGはサブページおよびマルチページでの動作を可能にする。ディレクトリは、ディレクトリ項目の集合であり、各々の項目は特定のページについて分散共有知識を符号化している。同時キャッシュ動作がページ上でアクティブであるとき、ディレクトリ項目は分散リソースへのアクセスをロックおよび同期する。ディレクトリ情報は、影響を受けるノード間で送られるポイントツーポイント・メッセージを介して最新に維持される。DMGキャッシュ・コヒーレンス・メッセージング対話は、リモート・キャッシュからのページを共有できるようにし（例えば、読み出し要求がローカル・キャッシュでミスになったとき）、リモートにキャッシュされたコピーを無効にすることができる（例えば、書き込み要求が前のコピーに取って代わるとき）。
【００１７】
ディレクトリ配置スキームの態様および局所データ・アクセスの利用方法は、下記のセクション1.1で説明される。セクション1.2はメッセージング対話を紹介し、さらに進んでセクション1.3では、1つの態様に従って、どのようにディレクトリでロッキングを利用して同時ページ・アクセスを管理するかを説明する。最後に、セクション1.4は、1つの態様に従って、どのようにロケーション認識ページ共有を使用して地理的に分散したキャッシュ・コヒーレンスのパフォーマンスを改善するかを説明する。
【００１８】
1.1  ディレクトリの配置
1つの局面によれば、キャッシュ・コヒーレンスを調整するため、DMGは、全てのアクティブ・ページに関する情報を追跡する項目を有するディレクトリを維持する。アクティブ・ページは、関連づけられた共有グループ内で少なくとも1つのキャッシュの中に発見されるページである。ディレクトリ項目は、どのノードが、関連づけられたページのコピーを有するかを追跡し、分散ロックを維持してページへの同時アクセスを防ぎ、待ち行列を維持して、ノードがロックを待機している間、動作を直列化する。
【００１９】
1.1.1  専用ディレクトリサーバ
1つの態様によれば、非常に簡単なディレクトリ配置スキームが使用される。そのスキームでは、全体のディレクトリが、共有グループに参加する最初のノードに置かれる。しかし、そのようなディレクトリスキームは、共有グループのサイズに対してスケール良好ではない。一般的に、ディレクトリ配置スキームのパフォーマンスを決定する場合、2つの競争する利益が関係する。所与のページのディレクトリ項目を含むノードのDMG動作は、不必要なメッセージ送信を避けるように最適化可能であり、それによってノード間帯域幅が保存され、動作待ち時間が改善される。しかし、ページのディレクトリノードは、共有グループ内の他のノードからの全ての関連メッセージ・トラフィックを処理しなければならない。
【００２０】
1.1.2  線条分割ディレクトリ配置
他の態様によれば、ディレクトリ項目は、各々の共有グループ内のノードを横切ってラウンドロビン方式で線条に分割される。DMGは、多くの場合、マルチページ動作を処理しなければならないので、線条サイズを十分大きくして、動作の頻繁な分割を回避すべきである。そのような線条分割は容易に実現することができ、最小のパフォーマンス・オーバヘッドを有するが、2つの問題点が、より良好な解決法の発見を望ましくするかもしれない。それらの2つの問題点は、次のとおりである。
1.線条分割は、共有グループ内のノードの全てがデータ・ボリュームの全体に分散されたページをアクティブに共有しているときにのみ機能する。ノードが非アクティブであるか、ノードがページを共有するだけで、ページのディレクトリ項目がリモート・ノード上に存在するならば、パフォーマンスは悪影響を受ける。線条分割ディレクトリ配置が所与の作業負荷へ適合化する方法は存在しない。
2.1つの局面において、線条分割はノードを横切るモジュラス関数を使用して実現されるので、ノードが共有グループに入るか出るならば、ディレクトリ項目を再分散する迅速かつ容易な方法はない。全てのキャッシュを無効にし、最初からディレクトリを作ることが1つの選択肢である。
【００２１】
1.1.3  局所意識ディレクトリ移行
本発明の1つの態様によれば、DMGは、適応ディレクトリ配置スキームである局所意識ディレクトリ移行またはLCDMを実現する。線条分割ディレクトリ配置の態様におけるように、LCDMの態様において、ディレクトリ項目は複数ページのチャンクへ分割される。しかし、それらのチャンクの配置または所有権は事前に設定されず、永久的でもない。その代わりに、ディレクトリチャンクの所有権は、それらのページを最も頻繁に使用しているノードへ移行する。局所データ・アクセスを利用して入出力パフォーマンスを改善することに加えて、LCDMは、ノード障害（または、共有グループに付加されるノード）からの迅速な回復を有利に助ける。なぜなら、ディレクトリチャンクを再分散する必要はないからである。1つの態様において、ディレクトリチャンクの所有権は、チャンク内のページにアクセスする最初のノードへ付与される。
【００２２】
1つの態様において、ノードの全てがそれらのキャッシュからチャンク内の全てのページを駆逐した後、ディレクトリチャンクが空であるときにのみ、所有権の持ち主が変わる。共有グループ内の1つのノードがグローバルディレクトリチャンクコーディネータ（「グローバル・コーディネータ」）として指定される。このノードは、ディレクトリ項目の所有権を付与し、ルックアップ・テーブルまたは他の類似のデータ構造を記憶する。これらのルックアップ・テーブルまたは他の類似のデータ構造は、共有グループ内の各々のアクティブ・ページの所有権を識別する。共有グループ内の他のノードは、ルックアップ・テーブルのローカル部分ミラーを維持するが、時にはグローバル・コーディネータを参照する必要がある。グローバル・コーディネータ自身も、ディレクトリ項目の所有者であるか、所有者になってよい。図2は、ディレクトリ所有権の変さらに関連したシナリオを要約する。これは下記で詳細に探究される。
A.ローカル・ノードが、ディレクトリチャンクの所有者が誰であるかを既に知っているとき、入出力動作の前に、所有者を識別または確認する簡単なテーブル・ルックアップが実行される。
B.ローカル・ノードがディレクトリチャンクに最初にアクセスする場合、ローカル・ノードはDIRQUERY＿REQメッセージをグローバル・コーディネータ・ノードへ送る。他のノードがチャンクの所有権を既に主張していれば、コーディネータは、チャンクの所有者の地位を含むDIRQUERY＿REPLYメッセージで要求者に応答する。次に、要求者はチャンクを所有するアクセス・ノードと通信し、入出力動作を完了する。
C.前のシナリオで、グローバル・コーディネータのルックアップが、問題のディレクトリチャンクを所有しているノードは存在しないことを示すならば、グローバル・コーディネータは、要求者の地位を含むと共に所有権を付与するDIRQUERY＿REPLYメッセージで要求者に応答する。地位は、ノードが共有グループに参加した順序を識別する指標である。グローバル・コーディネータのルックアップ・テーブルの中に項目が作られ、他のノードと同期される。
D.チャンク所有者が、もはやディレクトリ項目を有さないとき、それは所有権放棄のRELINQ＿REQメッセージをグローバル・コーディネータへ送る。DMGノードがチャンク所有権を放棄した後、新しい要求が元のチャンク所有者へ到着すれば、元のチャンク所有者はDIROWNER＿NACKメッセージで要求者へ応答する。これによって、要求者はグローバル・コーディネータへ再質問を行う。放棄の後に、グローバル・コーディネータへ質問した最初のノードが、チャンクの所有権を付与される。
【００２３】
他の態様では、ディレクトリチャンクが空でないときでも、ノード間におけるチャンク所有権の移行を可能にすることによって、LCDMを向上することができる。これによって、入出力アクセス・パターンを綿密に見守ることができ、メッセージング要件を最小にすることによって、DMGのパフォーマンスを改善することができる。しかし、この最適化は、一般的に、次のような或る一定の要件を有する。
1.ディレクトリチャンクの所有権は、チャンクの全体が休止しているときにのみ安全に移動可能である。アクティブなコヒーレンス・トラフィックまたはロックされたページが存在すれば、移動は実行不可能である。
2.空でないチャンクの移動は、新しいチャンク所有者への共有情報の輸送を含む。これは、半自動的に行われなければならず、したがって新しいコヒーレンス要求は、移動の途中で開始されない。
3.チャンク所有権の移転コストはゼロではないから、移転をいつ有効にするかを決定するために使用される発見的方法が非常に重要である。特に、キャッシュの作業負荷について、先行知識が制限されている場合にそうである。
4.ディレクトリチャンク移転の調整は、3つまでのノードを含むことができる。即ち、現在のチャンク所有者、グローバル・コーディネータ、および新しいチャンク所有者である。これは、半自動的移転の仕事を一層困難にする。
【００２４】
1.2  DMGにおける標準入出力パス
1つの態様によれば、データ・アクセス要求、例えば、読み出し要求、書き込み要求、および更新要求について、メッセージ対話がDMGの中で提供される。メッセージ配置を詳細に示すため、シーケンス対話が使用される（図3〜図5を参照）。各々の図において、DMGで処理されなければならない条件の範囲を説明するため、多様なシナリオが探査される。これらの図は、クライアント・キャッシュを含むノード、適切なディレクトリ項目を所有するノード（ディレクトリノード）、および問題のページのコピーを有する全ての他のノードを区別する。多くの場合、注意すべき重要なこととして、これらの実体は同じノードに共存する。各々の役割共有の組み合わせは新しい最適化を導入し、次のように処理される：
単一メンバー共有グループ：単一メンバー共有グループにおいて、ディレクトリは暗黙にのみ存在する。なぜなら、ディレクトリについて追跡すべき所有者情報は存在しないからである。クライアント・キャッシュからの要求は、処理するには平凡で、即時に答えることができる。
クライアント・キャッシュおよびディレクトリの共存：ディレクトリが、DMG要求を行っているノードに対してローカルであるとき、それは2つのメッセージ送信、即ち、開始時における要求および終了時における返答の必要性を除去する。
ディレクトリおよびページ所有者の共存：ディレクトリノードがページ所有者でもあるとき、それはローカルで共有を処理するか、要求を無効にすることができ、余分のメッセージの必要性を除く。
【００２５】
1.2.1  DMGの読み出し
図3は、読み出しがキャッシュの中でミスとなり、他のノードからのページを共有しようと試みてDMGへ達するときに看取される多様なメッセージ・シーケンスの例を詳細に示す。次の点は、図2における各々のシナリオの詳細な説明を提供する。
A.ディレクトリが、要求されたページについて項目を含まないとき、ディレクトリノードは新しい項目を作成し、要求者を唯一のページ所有者としてマークし、SHARE＿NACKメッセージで返答する。これによって、要求者はAMF（「配列管理機能」）へ進み、ディスクからページ・データのコピーを取得するようになる。一般的に、また米国特許第6,148,414号で詳細に説明されるように、AMFは、関連づけられたホスト・システムのために、記憶装置リソース、例えば、ディスクへのアクセスを提供する。例えば、ホストがリソース上で動作を実行するようにAMFへ要求するとき、AMFは、動作されるべきリソースを含む冗長グループの他のAMF共有対照と同期し、リソース上のロックを取得する。AMFは、典型的には、ミスが起こったキャッシュと同じノードに存在するが、リモートのAMFが使用されてよい。
B.ディレクトリのルックアップが、ページのリモート・コピーを発見するならば、DMGは、キャッシュされたコピーを記憶するノード（「共有者」）へSHARE＿REQメッセージを送る。共有者は、要求されたページをSHARE＿ACKメッセージの中でクライアント・ノードへ直接送り、ディレクトリノードを迂回する。データが送られた通信層から共有者が確認を受け取ると、共有者はREAD＿DONEメッセージをディレクトリノードへ送り、待機動作が始まるようにする。
C.前のシナリオで、共有者がページを非同期的に駆逐した後に（下記のセクション1.2.4を参照）、SHARE＿REQメッセージが共有者に到着すれば、共有者はSHARE＿NACKメッセージでディレクトリノードへ返答する。他の潜在的共有者が存在すれば、ディレクトリノードは後続のSHARE＿REQメッセージを送り、通常のように続ける。そうでなければ、他のノードがページを有さない場合、ディレクトリノードはSHARE＿NACKメッセージで要求者に返答する。
D.共有者が、そのSHARE＿ACKメッセージを要求者へ送った後に、しかしREAD＿DONEメッセージをディレクトリノードへ送ることができる前に消滅するならば、ディレクトリノードは、要求者がデータを獲得しなかったと仮定する。次に、ディレクトリノードはREAD＿FAILEDメッセージを要求者へ送り、読み出しが失敗したかもしれないことを表示する。読み出しが成功したのであれば、要求者はREAD＿FAILED＿NACKメッセージでディレクトリノードへ応答する。失敗した場合、ディレクトリノードは、要求者がデータを受け取ったか否かを知る必要があり、それによって、ディレクトリノードは更なる読み出し要求を適正に処理することができる。なぜなら、ディレクトリノードは回復を始める前にシステムを休止状態にして終了するからである。
E.前の例で、共有者が、SHARE＿ACKメッセージを要求者へ送ることができる前に消滅するならば、要求者はDMGの終局的READ＿FAILEDメッセージに対してREAD＿FAILED＿ACKメッセージで応答する。
【００２６】
1.2.2  DMGの書き込み
書き込み要求が要求ノードからDMGへ達するときのメッセージ・シーケンスは図4で示され、下記で説明される。
A.ディレクトリが、要求されたページについて項目を含まないか、要求者がページの唯一の所有者であることを表示する項目を発見するならば、ディレクトリノードは、WRITE＿REPLYメッセージで要求者へ即時に応答する。返答を受け取ると、要求者のキャッシュは、準備を完了すると直ちに、新しく書き込まれるデータのキャッシュへのコミットを許可される。
B.他のノードがキャッシュの中にページのコピーを有することを、問題のページのディレクトリ項目が示すならば、ディレクトリノードはそれら他のノードの各々へINVAL＿REQメッセージを送る。一度全てのINVAL＿REPLYメッセージがディレクトリノードへ戻されると、ディレクトリノードは上記のように要求者へ返答する。
【００２７】
1.2.3  DMGの更新
読み出しと同じように、多数のメッセージング・シナリオが、更新（即ち、サブページ書き込み）要求に応答するDMGの中で可能である。図5は、更新要求のメッセージ・シーケンスの例を示す。これはさらに下記で詳細に説明される。
A.UPDATE＿REQメッセージがディレクトリノードに到着したとき、ページについてディレクトリ項目が存在しないか、要求者がページの唯一の所有者であるならば、UPDATE＿NACKメッセージが即時に返却される。要求者が既にページのコピーを有するか、いかなるノードにもページのコピーが存在しないとき、UPDATE＿NACKメッセージが常にディレクトリの応答である。ノードがページのキャッシュされたコピーを有さない場合、要求者はAMFからページ・データを読み出す。一度要求者のキャッシュがそのサブページ書き込みを完了すると、要求者はUPDATE＿DONEメッセージでDMGへ応答する。
B.ページのコピーを所有する要求者に加えて、キャッシュの中にページを有する少なくとも1つのノードが存在することを、ディレクトリ項目が示すならば、ディレクトリノードはUPINV＿REQメッセージを他のページ所有者の各々へ送る。一度これらのノードの各々がページの自分のコピーを無効にし、UPINV＿REPLYメッセージでディレクトリノードへ応答すると、ディレクトリノードは、上記のようにUPDATE＿NACKメッセージを要求者へ送ることによって続ける。
C.要求者がそのキャッシュの中にページのコピーをもたず、ディレクトリ項目が、少なくとも1つの他のノードがページのコピーを有することを示すならば、ディレクトリノードは、ページを最後に書き込んだノードへSHINV＿REQメッセージを送り、コピーを保持する他のノードへUPINV＿REQメッセージを送る。SHINV＿REQメッセージを送られたノードは、SHINV＿REPLYメッセージの中でページのコピーをディレクトリノードへ転送することによってページのコピーを共有し、一度その送信が成功裏に完了すると、ローカル・コピーを無効にする。一度全ての返答がディレクトリによって受け取られると、ディレクトリノードは、共有無効標的ノードからのデータと一緒にUPDATE＿ACKメッセージを要求者へ送る。
D.前のシナリオで、共有無効標的ノードが、ディレクトリノードからSHINV＿REQメッセージを受け取る前にページのコピーを同期的に駆逐したのであれば、標的ノードはSHINV＿NACKメッセージで応答する。ディレクトリノードは、ページのコピーと一緒に無効要求を全ての他のノードへ既に送っているから、この時点では、ページのキャッシュされたコピーは存在しないであろう。ディレクトリノードは、UPDATE＿NACKメッセージで要求者へ応答する以外に選択肢をもたず（到着する全ての無効返答を待機した後で）、要求者はAMFからページを読み出すことになる。これは素晴らしいことである。なぜなら、ページのコピーを駆逐したノードは、最初にそのコピーをAMFへ一気に送り出すことが必要であったからである。ディレクトリは常に最後の書き手を追跡して、データの完全性を確保する。
E.SHINV＿REQメッセージを送った後、ディレクトリノードが、そのメッセージの共有無効標的が消滅したことに気付くならば、ディレクトリノードは他のノードからの無効返答を待機し、UPDATE＿FAILEDメッセージを要求者へ送ることによって要求を失敗させる。
【００２８】
1.2.4  DMGの駆逐
1つの局面によれば、不必要なメッセージ待ち時間を避けるため、ノード・キャッシュがページを駆逐するとき、それは単純に非同期EVICT＿REQメッセージをDMGへ送って駆逐を通知する。通知は非同期的であるから、キャッシュはページを駆逐した後に、ページへの要求を受け取るかもしれないが、それらの要求は、上記で詳説した入出力メッセージ・シナリオによって処理される。
【００２９】
1.3  DMGのロッキング
DMGの責任の1つは、ページ・データへの複数の同時変更を防止することである。DMGは、複数の読み手が同時にページにアクセスすることを許可する。しかし、複数の書き手は、書き込み要求がディレクトリノードへ到着した順序に直列化される。例えば、FIFO待ち行列またはバッファの中に置かれる。1つの局面によれば、システムのノード上のキャッシュも、ページ・フレームを保存および操作するため、或る直列化またはロッキングを必要とするかもしれない。ノードは、同じページについて同時にキャッシュおよびDMGのロックを保持する必要があるかもしれないので、システムは、好ましくは、デッドロック処理メカニズムを含む。1つの態様によれば、キャッシュ・ロックはDMGロックに従属する。これは、所与のページについてローカルに保持されたキャッシュ・ロックが、そのページ上のDMG動作が受け取られるならば、解放されなければならないことを意味する。
【００３０】
読み出し要求がディレクトリノードに到着したとき、ページを待機している動作が存在しないこと、およびゼロ以上の読み手が現在アクティブであることをディレクトリ項目が表示する場合、読み出しは即時の進行を許可される。対照的に、書き込みまたは更新要求がディレクトリノードに到着したとき、ページ上でいかなる活動も存在しない場合にのみ、それらの要求は進行することができる。他の状況においては、ディレクトリへの新しい要求は、先行する動作の完了によって活性化されるまでディレクトリ項目の中で待ち行列に入れられる。マルチページ動作については、DMGは、クライアント・ノードへ返答して関連動作の進行を許可する前に、動作についてのロックの全てを増加順序で収集する。DMGがこれらの制約を無視し、順序から外れてマルチページ動作の分割部分についてクライアント・ノードへ応答するならば、デッドロックが起こり得る。
【００３１】
1つの局面によれば、同じページへの複数の同時書き込みの場合に無益な努力を避けるDMG内の1つの最適化は、書き込みの進行を許可する前にロック待機待ち行列をチェックすることを含む。待ち行列の先頭にある書き込みの直後に、任意のノードからの1つまたは複数の書き込みが続くならば、DMGは早期の書き込みを優先的に無効にし、最後の書き込みの即時の進行を許可することができる。同時の書き込みが普通のケースであるとは予期されないので、この最適化の実現は重要でない。
【００３２】
1.4  ロケーションの認識
1つの態様によれば、DMGは、共有グループ内のノードの物理的または論理的接近度に基づいて、そのページ共有戦略を最適化する。1つの局面において、各々のノードのサイトIDが各々の共有グループ内のノードの全てによって記録される。ディレクトリノードが読み出し要求を受け取るとき、ディレクトリノードは最初に読み手と同じ（または物理的に接近した）サイト内のノードがページを有するかどうかを調べる。そうであれば、それは共有要求を最も近いノードへ送る。他の局面では、第2の選択肢として、ディレクトリノード自身によって共有が行われ（ディレクトリノードがキャッシュ内にページを有すると仮定する）、共有要求メッセージの送信を節約する。ディレクトリノードが、キャッシュされた要求ページを有さないならば、任意の他のノードを選択することができる。この場合、サイト間の相対的距離（即ち、ノードが相互に関して近いか、または遠いか）は考慮されない。更新の場合、この同じアルゴリズムがページ共有へも適用される。
【００３３】
LCDMを含むDMGの局面を実現する命令を含むコードは、コンピュータ読み取り可能メディア、例えば、CD、DVD、ROM、RAMなどに記憶可能であるか、データ・アクセス・ノード・デバイスとの間でネットワーク接続を介して送信可能であることを理解すべきである。
【００３４】
本発明は、例を使用し、特定の態様に関して説明されたが、本発明は、開示された態様に限定されないことを理解すべきである。反対に、当業者に明らかな様々な修正および類似の配列をカバーすることが意図される。したがって、添付の特許請求の範囲は、全てのそのような修正および類似の配列を包含するように最も広い解釈と一致すべきである。
【図面の簡単な説明】
【００３５】
【図１】本発明に従った基本ネットワーク構成の例を示す。
【図２】ディレクトリ所有権の変さらに関連するシナリオの例を示す。
【図３】読み出しがキャッシュでミスとなり、他のノードからのページを共有しようと試みてDMGへ達するときに看取される様々なメッセージ・シーケンスの例を示す。
【図４】書き込み要求が、要求しているノードからDMGへ達するときのメッセージ・シーケンスの例を示す。
【図５】更新要求についてのメッセージ・シーケンスの例を示す。
【図１】
2008506195.tif 000004
【図２】
2008506195.tif 000005
【図３】
2008506195.tif 000006
【図４】
2008506195.tif 000007
【図５】
2008506195.tif 000008