(57)【要約】【課題】　価値ベースのキャッシング・システム及び方法を提供する。【解決手段】　本発明の価値ベース・キャッシュ方法は、キャッシュを種々の価値ベース・パーティションに区分することを含む。キャッシュに記憶されるべきデータが評価され、その評価されたデータが個々の価値ベース・パーティションにキャッシングされる。その後、キャッシュ・エントリが価値ベース・パーティションから排出される。更に、キャッシング及び排出は、評価ステップに従って管理される。これに関連して、キャッシング及び排出管理ステップは、他のキャッシュされたデータに関して高い価値を有するデータに対して高いキャッシュ応答性を保証する。【選択図】　図４
2004078944.tif 000002
【特許請求の範囲】
【請求項１】
　キャッシュを複数の異なる価値ベース・パーティションに区分するステップと、
　前記キャッシュに記憶されるべきデータを評価し、評価されたデータを前記価値ベース・パーティションの各々にキャッシングするステップと、
　前記価値ベース・パーティションからキャッシュ・エントリを排出するステップと、
　他の評価されたデータに関して高い価値を持つデータに対して高いキャッシュ応答性を保証するように前記評価に従ってキャッシング及び排出を管理するステップと、
　を含む、価値ベース・キャッシュ方法。
【請求項２】
　前記管理するステップは、
　前記価値ベース・パーティションの少なくとも１つに保証されたパーティション・サイズを割り当てるステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションとは異なる価値を有するデータを求めるキャッシュ・リクエストを受け入れるように、他の価値ベース・パーティションを変化させるステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションに同様の価値を有するデータのみをキャッシングするステップと、
　を含む、請求項１に記載の方法。
【請求項３】
　前記管理するステップは、
　前記キャッシュにおけるエントリに種々のキャッシュ・エージング・プロセスを割り当てるステップと、
　対応するエージング・プロセスに従って特定の価値のキャッシュ・エントリを排出するステップと、
　を含み、同様の価値の各キャッシュ・エントリが前記種々のキャッシュ・エージング・プロセスのうちの特定のエージング・プロセスを共用し、前記エージング・プロセスが前記キャッシュにおける他のデータよりも高い価値を有するデータに対して漸進的に長い排出インターバルを与える、請求項１に記載の方法。
【請求項４】
　前記管理するステップは、
　保証されたパーティション・サイズを前記価値ベース・パーティションの少なくとも１つに割り当てるステップと、
　種々のキャッシュ・エージング・プロセスを前記キャッシュにおけるエントリに割り当てるステップであって、同様の価値の各キャッシュ・エントリが前記種々のキャッシュ・エージング・プロセスのうちの特定のエージング・プロセスを共用し、前記キャッシュ・エージング・プロセスが前記キャッシュにおける他のデータよりも高い価値を有するデータに対して漸進的に長い排出インターバルを与える、ステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションに同様の価値のデータをキャッシングするステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティション内の空きスペースに異種の価値のデータをキャッシングするステップと、
　特定の価値のキャッシュ・エントリを対応するエージング・プロセスに従って排出するステップと、
　同様の価値のデータをキャッシングすべき空きスペースが前記保証されたサイズを有する価値ベース・パーティションに存在しない場合、前記保証されたパーティション・サイズを有する価値ベース・パーティションに記憶されていたキャッシュ・エントリを排出するステップと、
　とを含む、請求項１に記載の方法。
【請求項５】
　価値ベース・キャッシングを行うコンピュータ・プログラムを記憶した機械可読記憶媒体であって、前記コンピュータ・プログラムが、
　キャッシュを複数の異なる価値ベース・パーティションに区分するステップと、
　前記キャッシュに記憶されるべきデータを評価し、評価されたデータを前記価値ベース・パーティションの各々にキャッシングするステップと、
　前記価値ベース・パーティションからキャッシュ・エントリを排出するステップと、
　他の評価されたデータに関して高い価値を持つデータに対して高いキャッシュ応答性を保証するように、前記評価に従ってキャッシング及び排出を管理するステップと、
　を機械に実行させるための命令のセットを含む、機械可読記憶媒体。
【請求項６】
　前記管理するステップは、
　前記価値ベース・パーティションの少なくとも１つに保証されたパーティション・サイズを割り当てるステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションとは異なる価値を有するデータを求めるキャッシュ・リクエストを受け入れるように、他の価値ベース・パーティションを変化させるステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションに同様の価値を有するデータのみをキャッシングするステップと、
　を含む、請求項５に記載の機械可読記憶媒体。
【請求項７】
　前記管理するステップは、
　前記キャッシュにおけるエントリに種々のキャッシュ・エージング・プロセスを割り当てるステップと、
　対応するエージング・プロセスに従って特定の価値のキャッシュ・エントリを排出するステップと、
　を含み、同様の価値の各キャッシュ・エントリが前記種々のキャッシュ・エージング・プロセスのうちの特定のエージング・プロセスを共用し、前記エージング・プロセスが前記キャッシュにおける他のデータよりも高い価値を有するデータに対して漸進的に長い排出インターバルを与える、請求項５に記載の機械可読記憶媒体。
【請求項８】
　前記管理するステップは、
　保証されたパーティション・サイズを前記価値ベース・パーティションの少なくとも１つに割り当てるステップと、
　種々のキャッシュ・エージング・プロセスを前記キャッシュにおけるエントリに割り当てるステップであって、同様の価値の各キャッシュ・エントリが前記種々のキャッシュ・エージング・プロセスのうちの特定のエージング・プロセスを共用し、前記キャッシュ・エージング・プロセスが前記キャッシュにおける他のデータよりも高い価値を有するデータに対して漸進的に長い排出インターバルを与える、ステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションに同様の価値のデータをキャッシングするステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティション内の空きスペースに異種の価値のデータをキャッシングするステップと、
　特定の価値のキャッシュ・エントリを対応するエージング・プロセスに従って排出するステップと、
　同様の価値のデータをキャッシングすべき空きスペースが前記保証されたサイズを有する価値ベース・パーティションに存在しない場合、前記保証されたパーティション・サイズを有する価値ベース・パーティションに記憶されていたキャッシュ・エントリを排出するステップと、
　とを含む、請求項５に記載の機械可読記憶媒体。
【請求項９】
　キャッシュ・マネージャと、
　前記キャッシュ・マネージャによって制御される少なくとも１つのキャッシュ・エージェントと、
　を含み、
　前記キャッシュ・マネージャが価値メトリックを前記少なくとも１つのキャッシュ・エージェントに通信し、前記少なくとも１つのキャッシュ・エージェントの各々がデータをキャッシングし、前記データ及びキャッシュ・エントリの測定された価値並びに前記キャッシュ・マネージャによって与えられた前記価値メトリックに従ってキャッシュ・エントリを排出する、価値ベース・キャッシング・システム。
【請求項１０】
　更に、種々のメディア・タイプで配置され、前記少なくとも１つのキャッシュ・エージェントの少なくとも１つによって制御される複数のキャッシュ・サブエージェントを含み、
　前記価値メトリックが前記種々のメディア・タイプに関するアクセス品質を指定し、前記キャッシュ・エージェントが、キャッシュ・リクエストを処理するために個々のキャッシュ・サブエージェントを割り当てる、請求項９に記載の価値ベース・キャッシング・システム。
【請求項１１】
　前記複数のキャッシュ・サブエージェント及び該キャッシュ・サブエージェントを制御する少なくとも１つのキャッシュ・エージェントがストレージ・エリア・ネットワーク（ＳＡＮ）に配置される、請求項１０に記載の価値ベース・キャッシング・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は、キャッシュ管理に関し、特に、キャッシュ・システムにおける差異化サービス（differentiated service）に関する。
【背景技術】
【０００２】
　現代のグローバル・ネットワークは、複数のネットワーク・テクノロジ、サーバ・プラットフォーム、クライアント機能、及びアプリケーション要件を複雑に織り交ぜたものと見なすことができる。大多数のネットワーク・テクノロジは、デバイス・リクエストを無差別に処理する。即ち、リクエスタの識別情報又はリクエストのタイプに関係なく、各デバイス・リクエストが同等の優先順位でもって処理され得る。しかし、極く最新のネットワーク指向コンピューティング・デバイスは、インターネットを介したネットワーク・トラフィックの指数関数的増加を考慮して、「ポリシー・ベースのサービス差異化モデル（policy based service differentiation model）」と呼ばれていたものに基づいて可変レベルのコンピューティング・サービスを提供し始めている。
【０００３】
　ポリシー・ベースのサービス差異化モデルでは、種々のリクエスタから発せられた種々のコンテンツ又はサービスを求めるリクエストが、管理に関連して定義されたポリシーに依存する種々のレベルの扱いを受けるという点で、コンピューティング・デバイスは多くのレベルのサービスを提供し得る。それに関して、サービス品質（ＱｏＳ）という用語は、特定のコンテンツ、サービス、又は特定のリクエスタに対して最小限負うべき応答性に関する保証レベルを指定する。ポリシー・ベースのサービス差異化モデルは、幾つかの要素の論理的結果である。第１に、私設及び公衆の両ネットワークを介してリクエストを発生するコンピューティング・アプリケーションの数及び種類が最近の１０年で劇的に増加した。しかし、これらのアプリケーションの各々は種々のサービス要件を有する。
【０００４】
　第２に、種々のレベルのセキュリティ及びＱｏＳを有する種々のサービスの提供を可能にするテクノロジ及びプロトコルが広く入手可能になった。更に、これら種々の特定のサービスに対するアクセスは、これら特定のサービスがネットワーク帯域幅、メモリ、及び処理サイクルのような重要なコンピューティング・リソースを消費することがあり得るので、規制されなければならない。結局、業務方針或いは組織の目標は、コンピュータ処理に対するすべてのリクエストを同様に扱うのではなく、種々のリクエストの間で差別化するとき、最も良好にかなえられる。
【０００５】
　デバイス・リクエストは、ネットワークを通して、最終的には、ファイル・システムに流れるので、ストレージ・システムがデータ・アクセスの終端ポイントを提供する。更に詳しく云えば、ネットワークにおいて発生したすべてのデータ・リクエストに応答して、ディスク媒体のようなファイル記憶デバイスが、そのリクエストされたデータを究極的に且つ物理的に検索する。従って、ネットワークのすべてのレベルにおけるデータ・キャッシュ・システムが、最終的にファイル記憶装置から物理的に検索され得るデータを複製する。しかし、ネットワークの他の要素と同様に、大量のリクエストがある環境では、ファイル記憶装置アクセスに起因する応答時間がかなりのコストを全体的な応答時間に付加し得る。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
　今日の企業は、或るカストマ及びデータがネットワーク上の他のカストマ及びデータより高いレベルのサービスを受けるように、種々のカストマ及び種々のデータに差異化サービスを効率的に提供する代償としてかなりの利益を受けることが可能である。即ち、企業が、価値あるものと考えられるカストマの期待されたサービス・レベルを満たす場合、その企業はそのカストマを確保することができる。逆に、企業が価値あるものと考えられるカストマの期待されたサービス・レベルを満たすことができない場合、その企業はカストマを失うことがあり得る。従って、応答時間が不安定である競争相手のシステムからカストマが単に「ワン・クリック」離れたところにいると見なされるほどに、差異化サービスは電子商取引の重要な構成要素となり得る。更に、現在のところ、ストレージ・システムが特定のレベルの差異化サービスを提供する場合に、ストレージ・システムは、そのストレージ・システムのオペレータが受けるべき利益に基づいて、キャッシュ内に記憶されたデータの価値を反映するための手段を持っていない。
【課題を解決するための手段】
【０００７】
　本発明は、価値ベース(value-based)のキャッシュ・システム及び方法に関する。価値ベース・キャッシュ方法は、キャッシュを種々の価値ベース・パーティションに区分することを含む。キャッシュに記憶されるべきデータは評価され、その評価されたデータは個々の価値ベース・パーティションにキャッシングされる。その後、キャッシュ・エントリは、その価値ベース・パーティションから排出される。最後に、キャッシング及び排出は、評価ステップに従って管理される。これに関して、キャッシング及び排出を管理するステップは、他の評価されたデータより高い価値を有するデータに対し、より高いキャッシュ応答性を保証し得る。
【０００８】
　本発明の１つの局面では、管理ステップは、保証されたパーティション・サイズを少なくとも１つの価値ベース・パーティションに割り当てるステップと、その保証されたパーティション・サイズを有する価値ベース・パーティションとは異なる価値を有するデータを求めるキャッシュ・リクエストに適応するように、他の価値ベース・パーティションが変化することを可能にするステップと、保証されたパーティション・サイズを有する価値ベース・パーティションにおいて同等の価値のデータのみをキャッシングするステップとを含み得る。本発明の別の局面では、管理ステップは、種々のキャッシュ・エージング・プロセスをキャッシュにおけるエントリに割り当てるステップを含み得る。同等の価値の各キャッシュ・エントリは、種々のキャッシュ・エージング・プロセスのうちの特定の１つを共用することができる。エージング・プロセスは、キャッシュにおける他のデータよりも高い価値を持ったデータに対して漸進的に長い排出インターバルを提供し得る。従って、特定の価値を持ったキャッシュ・エントリは、それに対応するエージング・プロセスに従って排出可能である。
【０００９】
　最後に、本発明の更に別の局面では、管理ステップは、保証されたパーティション・サイズを価値ベース・パーティションのうちの少なくとも１つに割り当てるステップと、種々のキャッシュ・エージング・プロセスをキャッシュにおけるエントリに更に割り当てるステップとを含み得る。同等の価値の各キャッシュ・エントリは、種々のキャッシュ・エージング・プロセスのうちの特定のプロセスを共用し得る。これらのエージング・プロセスは、キャッシュにおける他のデータよりも高い価値を有するデータに対して漸進的に長い排出インターバルを提供できる。
【００１０】
　同等の価値のデータは、保証されたパーティション・サイズを有する価値ベース・パーティションにキャッシングされ得る。同様に、本質的に異なる価値のデータが、保証されたパーティション・サイズを有する価値ベース・パーティションにおける空きスペースにキャッシングされ得る。更に、特定の価値のキャッシュ・エントリが、対応するエージング・プロセスに従って排出され得る。更に、保証されたパーティション・サイズを有する価値ベース・パーティションにおける同等の価値のデータのキャッシングに適応し得る空きスペースがその保証されたパーティション・サイズを有する価値ベース・パーティションに全く存在しない場合、その保証されたパーティション・サイズを有する価値ベース・パーティションにおける空きスペースに予め記憶されていたキャッシュ・エントリが排出され得る。
【発明を実施するための最良の形態】
【００１１】
　本発明は、価値ベースのキャッシング・プロセス及びシステムである。価値ベース・キャッシュでは、種々のデータ又はカストマの価値に対応した種々の価値ベース分類に従って、キャッシュが区分可能である。説明を簡単にするために、以下の記載では、３つの分類、即ち、金、銀、及び銅が示される。本発明が如何なる特定の分類法にも限定されないことは勿論であり、差異化されたサービス・レベルを種々のカストマ又は種々のデータに提供するために、如何なる他の分類法でも十分であることは勿論である。いずれの場合も、各パーティションに対するキャッシュ置換ポリシーは、そこに記憶されたデータの価値に従って変わり得る。
【００１２】
　詳しく云えば、キャッシュ置換ポリシーは、キャッシュ・データがより低い価値の他のパーティションにおける他のキャッシュ・データよりも高い価値のデータである場合、そのキャッシュ・データに対してより高い相対的キャッシュ占有権を与えることが可能である。この方法では、より高い価値のキャッシュ・データの場合、そのキャッシュ・データが、他の同様に評価されたデータのキャッシングを満足させるために、キャッシュ・パーティションから排出される前に、そのキャッシュ・データに対するリクエストがそのキャッシュ・データによって満足されるということは大いにあり得ることである。ここでは、３つの例示的キャッシュ置換ポリシーが示される。即ち、それらは、指定された価値のキャッシュ・データに対して或る量の記憶スペースを保証する置換ポリシー、より高い価値の高価値キャッシュ・データに対してより遅い老齢化ないしエージングを保証するＬＲＵ置換ポリシー、及びＬＲＵ置換ポリシーの特徴とスペース保証置換ポリシーの特徴とを組み合わせたポリシーである。
【００１３】
　図１は、本発明の価値ベース・スペース管理プロトコルに従って管理される、価値で区分されたキャッシュ（以下、価値区分キャッシュという）の概略図である。価値区分キャッシュでは、キャッシュ・スペース１８０Ａ全体が、種々の価値を有するキャッシュ・データに対して区分可能である。例えば、先ず、高価値の金のデータは金パーティション１３０Ａにキャッシング可能であり、次に低価値の銀のデータは銀パーティション１２０Ａにキャッシング可能であり、最後に、更に低価値の銅のデータは銅パーティション１１０Ａにキャッシング可能である。パーティション１１０Ａ、１２０Ａ、１３０Ａの各々は、等しいサイズ及び割り振りのものであるように示されているが、任意の初期構成を取ることができ、パーティション１１０Ａ、１２０Ａ、１３０Ａを、最初に連続的な記憶域及び等しいサイズを持つように構成する必要はない。
【００１４】
　重要なことは、図１における価値ベース・スペース管理プロトコルでは、スペース保証１７０Ａが強化されることである。それによって、金パーティション１３０Ａのようなキャッシュ・パーティションが、パーティション１６０Ａとして示された最小サイズを保証される。即ち、銅パーティション１４０Ａ及び銀パーティション１５０Ａのキャッシュ置換アクティビティに関係なく、金パーティション１６０Ａのサイズは一定のままである。それは、金パーティション１３０Ａにおけるキャッシュ・スペースが未使用のままであって、他のパーティション１１０Ａ、１２０Ａにおけるかなりのキャッシング・アクティビティがキャッシュ排出という結果を生じる場合でも言えることである。従って、図１に示されるように、銅の評価のデータに関するキャッシング・アクティビティが、その結果として銅パーティション１１０Ａの初期割り振りを越えて更に必要なキャッシング・スペースを生じた場合、拡張した銅パーティション１４０Ａが銀パーティション１５０Ａを犠牲にして提供され得るが、金パーティション１６０Ａのサイズは一定のままである。
【００１５】
　重要なことは、当業者には明らかであるように、金パーティション１６０Ａの未使用部分は、更なる金の評価のデータが金パーティション１６０Ａにキャッシングされるとき、金パーティション１６０Ａに予めキャッシングされていた既存の金の評価のデータが時期尚早の排出を被らない可能性を高くするように働くことである。その結果、金パーティション１６０Ａにおける未排出のキャッシュ・データに対するその後のリクエストは、そのリクエストされた金の評価のデータを非キャッシュ記憶装置から検索することを必要とせずに、キャッシュから満たされ得る。このように、金の評価のデータは、銅び銀の評価のデータの価値を越える相対的価値を認められたので、有利な扱いを受ける。
【００１６】
　図１に示されたスペース管理置換プロトコルは、スペース保証１７０Ａが金の評価のデータ又は金の評価のカストマに対する適切なデータ検索の応答性を与えるのに必要なレベルをはるかに超える場合には、非効率的である。従って、スペース保証１７０Ａが最適レベルの応答性を与えるように選択的に構成可能であるのが望ましい。本発明の構成によれば、動的ＬＲＵキャッシュ置換ポリシーが最適レベルの応答性を漸近的に与え、低評価のデータに対して図１のスペース保証１７０Ａのレベルを超え得る公正さを与える。
【００１７】
　図２は、本発明の価値ベースＬＲＵプロトコルに従って管理される価値区分キャッシュの概略図である。価値ベースＬＲＵプロトコルでは、キャッシュ・エントリのエージング時間はそれらの価値によって異なり、最も価値の高いキャッシュ・エントリは価値の低いキャッシュ・エントリよりもゆっくりとエージングする。例えば、先ず、キャッシュ・スペース１８０Ｂ全体が銅、銀、及び金のパーティション１１０Ｂ、１２０Ｂ、１３０Ｂに区分される。各キャッシング・インターバルでは、銅、銀、及び金のパーティション１１０Ｂ、１２０Ｂ、１３０Ｂの各々における個々のキャッシュ・エントリは異なったペースで期限切れになる。
【００１８】
　詳しく云えば、銅パーティション１１０Ｂにおけるキャッシュ・エントリは、式Ｔexpiration＝ｘ（但し、ｘは第１タイム・インターバルである） によって指定された第１ＬＲＵエージング・プロセス１８５Ｂに従って期限切れになるが、銀パーティション１２０Ｂにおけるキャッシュ・エントリは、式Ｔ’expiration =Ｔexpiration＋ｙ（但し、ｙは別のタイム・インターバルである） によって指定された更にゆっくりした第２ＬＲＵエージング・プロセス１９０Ｂに従って期限切れになる。最後に、金パーティション１３０Ｂにおけるキャッシュ・エントリは、式Ｔ”expiration＝Ｔ’expiration＋ｚ（但し、ｚは更に別のタイム・インターバルである） によって指定された更にゆっくりしたＬＲＵエージング・プロセス１９５Ｂに従って期限切れになる。従って、当業者には明らかなように、金パーティション１３０Ｂにおけるキャッシュ・エントリは、銀パーティション１２０Ｂにおけるキャッシュ・エントリよりも長く残存するであろうし、銀パーティション１２０Ｂにおけるキャッシュ・エントリは、銅パーティション１１０Ｂにおけるキャッシュ・エントリよりも長く残存するであろう。
【００１９】
　重要なことは、本発明のＬＲＵキャッシュ排出プロトコルでは、銀パーティション１２０Ｂにキャッシングされたデータに対するリクエストが少なく、金パーティション１３０Ｂにキャッシングされたデータに対するリクエストが更に少ない場合、キャッシング・インターバルに続いて、銅パーティション１４０Ｂがゆっくりとサイズを拡張して、銀パーティション１５０Ｂ及び金パーティション１６０Ｂを浸食するであろうと考えられることである。同様に、銀パーティションが、最終的には、サイズを拡張して、金パーティション１６０Ｂを浸食するであろう。従って、金パーティション１６０Ｂがいつも同じサイズのままでいることは期待し得ないが、金パーティション１６０Ｂの収縮は、単にエージング変数ｘ、ｙ、ｚを変化させることによって漸近的に減衰させられ、金パーティション１６０Ｂにキャッシングされた金の評価のデータに対して拡張した応答性を与える。
【００２０】
　本発明の明らかな利点は、上記のスペース管理プロトコル及びＬＲＵプロトコルが結合されて単一のキャッシュ置換ポリシーになり得ることである。それに関して、図３は、本発明の価値ベースのスペース管理及びＬＲＵの結合プロトコルに従って管理される価値区分キャッシュの概略図である。この結合プロトコルでは、キャッシュ・スペース１８０Ｃが前と同様に銅、銀、及び金のパーティション１１０Ｃ、１２０Ｃ、１３０Ｃに区分される。スペース管理プロトコルにおけるように、一定のパーティション・サイズ１７０Ｃが金パーティション１３０Ｃに対して設定される。更に、個別の漸進的に従属したエージング・プロセス１８５Ｃ、１９０Ｃ、１９５Ｃが銅、銀、及び金のパーティション１１０Ｃ、１２０Ｃ、１３０Ｃの各々と関連付けられる。
【００２１】
　エージング・プロセス１８５Ｃ、１９０Ｃ、１９５Ｃに従ってキャッシュ排出が決定されるキャッシング・インターバルの間に、銅、銀、及び金のパーティション１１０Ｃ、１２０Ｃ、１３０Ｃの各々において、キャッシュ空所が生じる。金及び銀の評価のデータに対するリクエストよりも多くの銅の評価のデータに対するリクエストが処理されることが期待できる場合、たとえ金パーティション１５０Ｃ又は銀パーティション１６０Ｃの空きスペースだけが使用可能であっても、銅の評価のデータはその空きスペースにキャッシングされる。例えば、図示のように、銀の評価のデータは、金パーティション１６０Ｃと関連した空きスペース１７５Ｃにキャッシングされる。
【００２２】
　しかし、図２のＬＲＵプロトコルとは違って、図３の結合プロトコルでは、金パーティション１６０Ｃは保証された一定のパーティション・サイズのものであるが、金パーティション１６０Ｃにおける不使用部分の使用を可能にすることは、金パーティション１６０Ｃの残りの部分が金の評価のデータを収容し得る限り、問題ない。しかし、金パーティション１６０Ｃにスペースが残っていない場合、空きスペース１７５Ｃに記憶されていた銅又は銀の評価のデータは、固定サイズ１７０Ｃのものであることを保証されていた金パーティション１６０Ｃにおける金の評価のデータのキャッシングに適応させるために、直ちに排出され得る。
【００２３】
　図４は、図１乃至図３に示された価値ベースＬＲＵプロトコル及び価値ベース・スペース管理プロトコルの一方又は両方に従って価値ベース・キャッシングを行うためのプロセスを示すフローチャートである。ブロック２１０において開始し、どのデータを生成又は検索すべきかを示すリクエストが受け取られる。ブロック２２０では、その生成又は検索プロセスに着手する前に、キャッシュは、以前にキャッシングされたデータによってそのリクエストを満たすことができるかどうかを決定するために検査される。判断ブロック２３０において、データがキャッシュに見つかった場合、ブロック２９５において、その見つかったデータによりリクエストが処理され、プロセスはブロック２１０に戻る。
【００２４】
　判断ブロック２３０において、以前にキャッシングされたデータによってそのリクエストが満たされ得ない場合、ブロック２４０において、そのリクエストは、必要な生成又は検索プロセスに着手することによってサービスされ得る。例えば、データが固定記憶装置から検索される。あるいは、データを生成するという結果をもたらすロジックが実行され得る。いずれの場合も、データの価値がブロック２５０において決定される。特に、その価値は、他のデータに関して評価され得る。例えば、リクエスタのアイデンティティがデータの特定の価値をもたらすことがある。また、データ提供者のアイデンティティがデータの特定の価値をもたらすことがある。更に、データのタイプそのものが特定の価値をもたらすことがある。
【００２５】
　如何なる場合も、データの価値に基づいて、キャッシュにおける適切なパーティションを識別することができ、判断ブロック２６０において、対応するキャッシュ・パーティションに空きあるかどうかが決定される。空きがあれば、ブロック２９０において、データが対応するパーティション内にキャッシングされ、プロセスはブロック２１０に戻る。空きがなければ、ブロック２７０において、そのデータの価値とは異なる価値と関連した他のパーティションに空きがあるかどうかが更に判断される。空きがあれば、ブロック２９０において、必要な場合に、そのデータが、選択されたパーティションに対応した価値を有するデータのためにあとで排出されるであろうということを承知の上で、その選択された別のパーティション内にキャッシングされる。最後に、別のパーティションに空きがなければ、ブロック２８０において、対応するパーティションにおけるキャッシュ・エントリが排出され、ブロック２９０において、そのデータが対応するパーティション内にキャッシングされる。
【００２６】
　図５は、１つ又は複数のキャッシュ・エージェントが１つ又は複数の物理的なキャッシング・プラットフォームにおいて図４の価値ベース・キャッシング・プロセスを管理するという価値ベース・キャッシュのブロック図である。それに関連して、本発明の価値ベース・キャッシュは、単一の物理的プラットフォーム３１０に配置されたキャッシュ・マネージャ３２０及び１つ又は複数のキャッシュ・エージェント３２５を含み得る。キャッシュ・マネージャ３２０は、キャッシング環境に関連して価値メトリック（ｖａｌｕｅ　ｍｅｔｒｉｃｓ）３０５を受け取り、それを解釈する。価値メトリックは、コンフィギュレーション・ファイルを通して静的に、又は管理アプリケーションを通して動的に受け取り可能である。いずれの場合も、キャッシュ・マネージャ３２０は、適切なパーティション・タイプ及びサイズ、並びにエージング・プロセスを指定し得る。
【００２７】
　キャッシュ・エージェント３２５は、キャッシュ・リクエスト３１５に応答することによってキャッシュ自体におけるデータのキャッシングを制御する。具体的に云えば、キャッシュ・エージェント３２５は、キャッシュに記憶されたデータでもってリクエスト３１５に応えることができる。更に、キャッシュ・エージェント３２５は、キャッシュ・マネージャ３２０によって指定された価値メトリックに従って、適切なキャッシュ・パーティションにおけるデータのキャッシング、及びキャッシュ・マネージャ３２０によって指定された価値メトリックに従ってキャッシュ・エントリの排出も共に制御し得る。特に、最小限、単一のキャッシュ・マネージャ３２０が単一のキャッシュ・エージェント３２５を制御し得る。別の実施例では、単一のキャッシュ・マネージャ３２０が、コンピュータ通信ネットワークに分散した他のキャッシュ・エージェント３３０を制御し得る。重要なことは、キャッシュ・マネージャ３２０が、キャッシュ・マネージャ３２０により制御される個々のキャッシュ・エージェント３２５、３３０に種々の価値メトリックを適用し得ることである。
【００２８】
　本発明の１つの重要な局面では、キャッシュ価値メトリックが異なった物理キャッシュ・スペースに相関し得るアクセス品質（ＱｏＡ）ベース・キャッシュ・クラスタ３４０が提供される。それに関連して、図６は、１つのキャッシュ・エージェントがキャッシュ・クラスタ又はストレージ・サブシステムにおける１つ又は複数のキャッシュ・サブエージェントにわたって価値ベース・キャッシングを管理する価値ベース・キャッシング・システムのブロック図である。図６では、メモリ３５０に配置されたキャッシュ・エージェント３５５に対するキャッシュ価値メトリックを指定し得るキャッシュ・マネージャ３７０が設けられる。通信可能にリンクされたサブエージェント３６０は、特定のキャッシュ・スペースにおいて動作可能であり、キャッシュ・マネージャに提供されたキャッシュ・メトリック３３５に基づいて、キャッシュ・エージェント３５５から受け取ったキャッシュ・リクエスト３４５を処理する。特に、図５の場合のように、キャッシュ・エージェント３５５は、コンピュータ通信ネットワークに分散した他のキャッシュ・サブエージェント３６５を制御し得る。
【００２９】
　特に、キャッシュ・メトリック３３５は、待ち時間、総合スループット、及び局所性のようなキャッシュ・スペースのメディア・タイプに関連したメトリックを含み得る。キャッシュ・サブエ−ジェント３６０、３６５は特定のキャッシュ・スペースにおいて動作するので、特定のキャッシュ価値メトリックに対するＱｏＡは、特殊なメディア・タイプに相関し得る。データ、リクエスタ、又はネットワークから取り出されたユーザ定義の価値は、特定のメディア・タイプに対するポリシーにより直接的に又は間接的にマップ可能である。例えば、価値の降順にリストされるとき、高速メモリ、低速メモリ、ローカル・データベース・アクセス、及びリモート・データベース・アクセスのようなメディア分類が定義可能である。
【００３０】
　当業者には明らかなように、ＱｏＡベース・キャッシュ・クラスタは、外部的には単一のキャッシュ・エンジンのように見えるが、価値が変化するデータに対するキャッシュの応答性は、キャッシュ・メディア・タイプに従って制御可能である。従って、ＱｏＡベース・キャッシュ・クラスタは、ストレージ・エリア・ネットワーク（ＳＡＮ）のような最新のストレージ・テクノロジに拡張可能である。その場合、ＳＡＮは、ユーザの価値に基づいて記憶メディアの分類を提供し、キャッシュ・マネージャ３７０、適切なキャッシュ・エージェント３５５、及び関連のサブエージェント３６０、３６５の制御の下に動作する。
【００３１】
　本発明は、１つのコンピュータ・システムにおける集中型態様で、又は種々の素子が幾つかの相互接続されたコンピュータ・システムにわたって配置される分散型態様で、ハードウェア、ソフトウェア、又はファームウェアにおいて実現可能である。本明細書で開示された機能の遂行には、本明細書で開示された方法を実行するべく適応した任意の種類のコンピュータ・システム、その他の装置が適している。代表的な集中型の実施態様は、本明細書で開示された方法を実行するようにコンピュータ・システムを制御するコンピュータ・プログラムを持った汎用コンピュータ・システムを含み得る。
【００３２】
　ここで、コンピュータ・プログラム又はアプリケーションは、情報処理能力を有するシステムに、直接に、又は（ａ）別の言語、コード、若しくは表記法への変換、及び（ｂ）異なる媒体での再生、の一方若しくは両方の後に、特定の機能を遂行させることを意図した命令のセットを任意の言語、コード、又は表記法で任意に表現したものを意味する。重要なことは、本発明が、本発明の精神又は本質的な属性から逸脱することなく、他の特定な形態で実施可能であり、従って、本発明の範囲を表すものとして、本願の明細書ではなく、特許請求の範囲を参照すべきである。
【００３３】
　まとめとして、本発明の構成に関して以下の事項を開示する。
【００３４】
（１）キャッシュを複数の異なる価値ベース・パーティションに区分するステップと、
　前記キャッシュに記憶されるべきデータを評価し、評価されたデータを前記価値ベース・パーティションの各々にキャッシングするステップと、
　前記価値ベース・パーティションからキャッシュ・エントリを排出するステップと、
　他の評価されたデータに関して高い価値を持つデータに対して高いキャッシュ応答性を保証するように前記評価に従ってキャッシング及び排出を管理するステップと、
　を含む、価値ベース・キャッシュ方法。
（２）前記管理するステップは、
　前記価値ベース・パーティションの少なくとも１つに保証されたパーティション・サイズを割り当てるステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションとは異なる価値を有するデータを求めるキャッシュ・リクエストを受け入れるように、他の価値ベース・パーティションを変化させるステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションに同様の価値を有するデータのみをキャッシングするステップと、
　を含む、（１）に記載の方法。
（３）前記管理するステップは、
　前記キャッシュにおけるエントリに種々のキャッシュ・エージング・プロセスを割り当てるステップと、
　対応するエージング・プロセスに従って特定の価値のキャッシュ・エントリを排出するステップと、
　を含み、同様の価値の各キャッシュ・エントリが前記種々のキャッシュ・エージング・プロセスのうちの特定のエージング・プロセスを共用し、前記エージング・プロセスが前記キャッシュにおける他のデータよりも高い価値を有するデータに対して漸進的に長い排出インターバルを与える、（１）に記載の方法。
（４）前記管理するステップは、
　保証されたパーティション・サイズを前記価値ベース・パーティションの少なくとも１つに割り当てるステップと、
　種々のキャッシュ・エージング・プロセスを前記キャッシュにおけるエントリに割り当てるステップであって、同様の価値の各キャッシュ・エントリが前記種々のキャッシュ・エージング・プロセスのうちの特定のエージング・プロセスを共用し、前記キャッシュ・エージング・プロセスが前記キャッシュにおける他のデータよりも高い価値を有するデータに対して漸進的に長い排出インターバルを与える、ステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションに同様の価値のデータをキャッシングするステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティション内の空きスペースに異種の価値のデータをキャッシングするステップと、
　特定の価値のキャッシュ・エントリを対応するエージング・プロセスに従って排出するステップと、
　同様の価値のデータをキャッシングすべき空きスペースが前記保証されたサイズを有する価値ベース・パーティションに存在しない場合、前記保証されたパーティション・サイズを有する価値ベース・パーティションに記憶されていたキャッシュ・エントリを排出するステップと、
　とを含む、（１）に記載の方法。
（５）価値ベース・キャッシングを行うコンピュータ・プログラムを記憶した機械可読記憶媒体であって、前記コンピュータ・プログラムが、
　キャッシュを複数の異なる価値ベース・パーティションに区分するステップと、
　前記キャッシュに記憶されるべきデータを評価し、評価されたデータを前記価値ベース・パーティションの各々にキャッシングするステップと、
　前記価値ベース・パーティションからキャッシュ・エントリを排出するステップと、
　他の評価されたデータに関して高い価値を持つデータに対して高いキャッシュ応答性を保証するように、前記評価に従ってキャッシング及び排出を管理するステップと、
　を機械に実行させるための命令のセットを含む、機械可読記憶媒体。
（６）前記管理するステップは、
　前記価値ベース・パーティションの少なくとも１つに保証されたパーティション・サイズを割り当てるステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションとは異なる価値を有するデータを求めるキャッシュ・リクエストを受け入れるように、他の価値ベース・パーティションを変化させるステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションに同様の価値を有するデータのみをキャッシングするステップと、
　を含む、（５）に記載の機械可読記憶媒体。
（７）前記管理するステップは、
　前記キャッシュにおけるエントリに種々のキャッシュ・エージング・プロセスを割り当てるステップと、
　対応するエージング・プロセスに従って特定の価値のキャッシュ・エントリを排出するステップと、
　を含み、同様の価値の各キャッシュ・エントリが前記種々のキャッシュ・エージング・プロセスのうちの特定のエージング・プロセスを共用し、前記エージング・プロセスが前記キャッシュにおける他のデータよりも高い価値を有するデータに対して漸進的に長い排出インターバルを与える、（５）に記載の機械可読記憶媒体。
（８）前記管理するステップは、
　保証されたパーティション・サイズを前記価値ベース・パーティションの少なくとも１つに割り当てるステップと、
　種々のキャッシュ・エージング・プロセスを前記キャッシュにおけるエントリに割り当てるステップであって、同様の価値の各キャッシュ・エントリが前記種々のキャッシュ・エージング・プロセスのうちの特定のエージング・プロセスを共用し、前記キャッシュ・エージング・プロセスが前記キャッシュにおける他のデータよりも高い価値を有するデータに対して漸進的に長い排出インターバルを与える、ステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティションに同様の価値のデータをキャッシングするステップと、
　前記保証されたパーティション・サイズを有する価値ベース・パーティション内の空きスペースに異種の価値のデータをキャッシングするステップと、
　特定の価値のキャッシュ・エントリを対応するエージング・プロセスに従って排出するステップと、
　同様の価値のデータをキャッシングすべき空きスペースが前記保証されたサイズを有する価値ベース・パーティションに存在しない場合、前記保証されたパーティション・サイズを有する価値ベース・パーティションに記憶されていたキャッシュ・エントリを排出するステップと、
　とを含む、（５）に記載の機械可読記憶媒体。
（９）キャッシュ・マネージャと、
　前記キャッシュ・マネージャによって制御される少なくとも１つのキャッシュ・エージェントと、
　を含み、
　前記キャッシュ・マネージャが価値メトリックを前記少なくとも１つのキャッシュ・エージェントに通信し、前記少なくとも１つのキャッシュ・エージェントの各々がデータをキャッシングし、前記データ及びキャッシュ・エントリの測定された価値並びに前記キャッシュ・マネージャによって与えられた前記価値メトリックに従ってキャッシュ・エントリを排出する、価値ベース・キャッシング・システム。
（１０）更に、種々のメディア・タイプで配置され、前記少なくとも１つのキャッシュ・エージェントの少なくとも１つによって制御される複数のキャッシュ・サブエージェントを含み、
　前記価値メトリックが前記種々のメディア・タイプに関するアクセス品質を指定し、前記キャッシュ・エージェントが、キャッシュ・リクエストを処理するために個々のキャッシュ・サブエージェントを割り当てる、（９）に記載の価値ベース・キャッシング・システム。
（１１）前記複数のキャッシュ・サブエージェント及び該キャッシュ・サブエージェントを制御する少なくとも１つのキャッシュ・エージェントがストレージ・エリア・ネットワーク（ＳＡＮ）に配置される、（１０）に記載の価値ベース・キャッシング・システム。
【図面の簡単な説明】
【００３５】
【図１】本発明の価値ベース・スペース管理プロトコルに従って管理される価値区分キャッシュの概略図である。
【図２】本発明の価値ベースＬＲＵプロトコルに従って管理される価値区分キャッシュの概略図である。
【図３】本発明の価値ベース・スペース管理プロトコル及び価値ベースＬＲＵプロトコルを結合したプロトコルに従って管理される価値区分キャッシュの概略図である。
【図４】図１乃至図３に示された価値ベースＬＲＵプロトコル及び価値ベース・スペース管理プロトコルの一方又は両方に従って価値ベース・キャッシングを行うためのプロセスを示すフロー・チャートである。
【図５】１つ又は複数のキャッシュ・エージェントが１つ又は複数の物理的キャッシング・プラットフォームにおいて図４の価値ベース・キャッシング・プロセスを管理する価値ベース・キャッシング・システムのブロック図である。
【図６】キャッシュ・エージェントがキャッシュ・クラスタ又はストレージ・サブシステムにおいて１つ又は複数のキャッシュ・サブエージェントにまたがって価値ベース・キャッシングを管理する価値ベース・キャッシング・システムのブロック図である。
【図１】
2004078944.tif 000003
【図２】
2004078944.tif 000004
【図３】
2004078944.tif 000005
【図４】
2004078944.tif 000006
【図５】
2004078944.tif 000007
【図６】
2004078944.tif 000008