(57)【要約】クラスタ内のノード上のキャッシュは、データ項目がキャッシュのうちのいずれかに保持され得るようにグローバルに管理される。キャッシュに記憶されたデータ項目の置換を支配する置換ポリシーが、他のノードのキャッシュの状態を含む要因に従って置換するためのバッファを選択する。いくつかのキャッシュされたデータ項目は、グローバルに共有されるものと指定され、主要キャッシュが割当てられる。主要キャッシュが別のノードであるデータ項目のコピーをバッファが維持している場合、そのバッファのデータ項目は、これが主要キャッシュであるグローバルなデータ項目またはローカルなデータ項目よりも置換が優先される。異なったノード上のバッファのキャッシュ保存値が比較されてもよい。最低のキャッシュ保存値を有するバッファが置換のために選択される。置換ポリシーは、クラスタ内の他のキャッシュが如何に構成されるかも説明する。
2004511840.tif 000002
【特許請求の範囲】
【請求項１】
各々が１つ以上のノードの組のうちのあるノード上に存在する複数個のキャッシュのバッファに記憶されるデータの置換を管理するための方法であって、前記１つ以上のノードの組の各ノードは、前記複数個のキャッシュのうちの１つ以上のキャッシュを含み、複数個のキャッシュは第１のキャッシュを含み、前記方法は、
１つ以上の要因に基づいて前記第１のキャッシュから第１のバッファを置換のために選択するステップを含み、前記第１のバッファは、第１のデータ項目を記憶するために現在使用されており、
前記１つ以上の要因は、
前記複数個のキャッシュのうち少なくとも１つの他のキャッシュの状態、または
前記複数個のキャッシュのうち前記少なくとも１つの他のキャッシュの構成、のいずれかを含み、さらに、
前記第１のバッファに記憶された前記第１のデータ項目を第２のデータ項目と置換するステップを含む、方法。
【請求項２】
前記１つ以上の要因は、前記第１のデータ項目が前記複数個のキャッシュのうち少なくとも１つの他のキャッシュに存在するか否かを含む、請求項１に記載の方法。
【請求項３】
前記方法はさらに、
前記複数個のキャッシュのうちの別の特定のキャッシュに前記第１のデータ項目を転送するステップと、
前記第１のデータ項目を特定のキャッシュに転送することに応答して、前記第１のキャッシュから除去されてもよいデータを前記第１のバッファが含むことを示すデータを生成するステップとを含み、
前記１つ以上の要因は、置換されてもよいデータを前記第１のバッファが含むことを前記データが示すことを含む、請求項１に記載の方法。
【請求項４】
データを生成するステップは、前記第１のデータ項目が、第１のキャッシュに記憶されたデータ項目の特定のサブセットに属するとき行なわれる、請求項３に記載の方法。
【請求項５】
データ項目の前記特定のサブセットは、前記第１のキャッシュに現在存在するデータ項目のうち最も頻繁にアクセスされた組を含む、請求項４に記載の方法。
【請求項６】
前記第２のデータ項目を置換する前に、前記第１のバッファは第１のキャッシュ保持値と関連付けられ、第２のバッファは第２のキャッシュ保持値と関連付けられ、第２のキャッシュは前記第２のバッファを含み、
前記１つ以上の要因は、前記第１のキャッシュ保持値が前記第２のキャッシュ保持値よりも小さいことを含む、請求項１に記載の方法。
【請求項７】
前記第１のキャッシュは第１のキャッシュマネージャによって管理され、前記第２のキャッシュは第２のキャッシュマネージャによって管理され、前記方法はさらに、
前記第１のキャッシュマネージャが、前記第２のキャッシュマネージャに代わって、第１のキャッシュに記憶された特定のデータ項目の直接転送の要求を受信するステップと、
前記第１のキャッシュマネージャが前記要求を受信することに応答して、前記第１のキャッシュマネージャが、前記第１のキャッシュ保持値および前記特定のデータ項目を前記第２のキャッシュに送信するステップとを含み、前記第１のキャッシュ保持値は、前記第１のキャッシュ内のバッファの少なくともサブセットの最低のキャッシュ保持値を示す、請求項６に記載の方法。
【請求項８】
前記第２のキャッシュマネージャが、前記第２のキャッシュ保持値が前記第１のキャッシュ保持値よりも大きいと判断することに応答して、前記第１のキャッシュが前記第２のキャッシュから送信された前記第２のデータ項目を受信するステップをさらに含み、
前記要因は、前記第２のキャッシュマネージャが、前記第２のキャッシュ保持値が前記第１のキャッシュ保持値よりも大きいと判断することに応答して、前記第１のキャッシュが前記第２のキャッシュから送信された前記第２のデータ項目を受信したことを含む、請求項６に記載の方法。
【請求項９】
最初に前記第１のキャッシュからの前記第１のデータ項目を持続的記憶装置に永続的に記憶することなしに、前記第１のデータ項目のコピーを第２のノードの第２のキャッシュに転送するステップをさらに含む、請求項１に記載の方法。
【請求項１０】
前記複数個のキャッシュは各々データベースシステムによって管理される、請求項１に記載の方法。
【請求項１１】
前記１つ以上の要因は、前記データ項目が、前記複数個のキャッシュのうちの別の特定のキャッシュから転送されるとき置換の資格ができるか否かを含む、請求項１に記載の方法。
【請求項１２】
１つ以上のノード上のデータ項目をキャッシュする方法であって、前記方法は、
１つ以上のノードの組の上の複数個のキャッシュを含むグローバルキャッシュを、前記グローバルキャッシュに任意の所与のデータ項目の特定のコピーを保持する態様で管理するステップを含み、
１つ以上のノードの前記組の各ノードは、前記複数のキャッシュのうちの１つ以上のキャッシュを含む、方法。
【請求項１３】
前記特定のコピーは、前記グローバルキャッシュに保持された複数個のデータ項目のうちの１つのコピーであり、
管理するステップは、前記複数個のデータ項目の各データ項目の１つのみのコピーを前記グローバルキャッシュに保持することにより行なわれる、請求項１２に記載の方法。
【請求項１４】
前記複数個のキャッシュは、前記特定のデータ項目のサブセットのための１つ以上の主要キャッシュを含み、
管理するステップは、前記サブセットからのデータ項目のコピーをそのデータ項目のための主要キャッシュに保持することを含むステップを含む、請求項１２に記載の方法。
【請求項１５】
前記１つ以上の主要キャッシュのうち特定の主要キャッシュが、シェアードナッシングシステムにおける特定のノードのダイナミックメモリを占有し、前記特定のノードは、特定のデータ項目が存在する静的記憶装置に直接アクセスし、前記特定のノードは、前記特定のデータ項目のための主要キャッシュである、請求項１４に記載の方法。
【請求項１６】
複数個のキャッシュは、第１のノード上に存在する第１のキャッシュを含み、管理するステップは、
１つ以上の要因に基づいて前記第１のキャッシュから第１のバッファを置換のために選択し、前記第１のバッファは第１のデータ項目を記憶するために現在使用されており、前記１つ以上の要因は、
前記複数個のキャッシュのうち少なくとも１つの他のキャッシュの状態、または
前記複数個のキャッシュのうち少なくとも１つの他のキャッシュの構成、のいずれかを含み、さらに
前記第１のバッファに記憶された前記第１のデータ項目を第２のデータ項目と置換するステップを含む、請求項１２に記載の方法。
【請求項１７】
最初に前記第１のキャッシュからの前記第１のデータ項目を持続的記憶装置に永続的に記憶することなしに、前記第１のデータ項目のコピーを第２のノードの第２のキャッシュに転送するステップをさらに含む、請求項１６に記載の方法。
【請求項１８】
前記複数個のキャッシュは各々データベースシステムによって管理される、請求項１２に記載の方法。
【請求項１９】
各々が１つ以上のノードの組のうちのあるノード上に存在する複数個のキャッシュを含むグローバルキャッシュを管理するための方法であって、前記１つ以上のノードの組の各ノードは前記複数個のキャッシュのうち１つ以上のキャッシュを含み、前記複数個のキャッシュは第１のノード上に存在する第１のキャッシュを含み、
前記方法は、
第１のデータ項目の第２のコピーが前記複数個のキャッシュのうちの第２のキャッシュにおける第２のバッファに存在することに基づいて、第１のキャッシュの第１のバッファ中の第１のデータ項目のコピーが置換の資格があることを示すデータを生成するステップと、
前記第１のバッファに記憶された前記第１のデータ項目を別のデータ項目と置換するステップとを含む、方法。
【請求項２０】
複数個のキャッシュは、第１のノード上に存在する第１のキャッシュを含み、前記方法は、
１つ以上の要因に基づいて前記第１のキャッシュから第１のバッファを置換のために選択するステップを含み、前記１つ以上の要因は、
前記第１のバッファが前記第１のデータ項目を記憶するために現在使用されている、前記複数個のキャッシュのうち前記第１のノードと異なるノード上に存在する少なくとも１つのキャッシュの状態、または
前記複数個のキャッシュのうち前記第１のノードと異なるノード上に存在する少なくとも１つのキャッシュの構成、のいずれかを含み、さらに
前記第１のバッファに記憶される前記第１のデータ項目を第２のデータ項目と置換するステップを含む、請求項１９に記載の方法。
【請求項２１】
最初に前記第１のキャッシュからの前記第１のデータ項目を持続的記憶装置に永続的に記憶することなしに、前記第１のデータ項目のコピーを第２のノードの第２のキャッシュに転送するステップをさらに含む、請求項１９に記載の方法。
【請求項２２】
前記複数個のキャッシュは各々データベースシステムによって管理される、請求項１９に記載の方法。
【発明の詳細な説明】
【０００１】
【関連出願】
この出願は、１９９８年１１月２４日に出願され、あるノードのキャッシュから別のノードのキャッシュにデータを転送するための方法および装置（Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｔｒａｎｓｆｅｒｒｉｎｇ Ｄａｔａ Ｆｒｏｍ ｔｈｅ Ｃａｃｈｅ ｏｆ Ｏｎｅ Ｎｏｄｅ ｔｏ ｔｈｅ Ｃａｃｈｅ ｏｆ Ａｎｏｔｈｅｒ Ｎｏｄｅ）と題され、発明者としてボリス・クロッツ（Ｂｏｒｉｓ Ｋｌｏｔｓ）およびロジャー・Ｊ・バンフォード（Ｒｏｇｅｒ Ｊ． Ｂａｍｆｏｒｄ）を列挙し、ここではクロッツと呼ばれる関連の米国特許出願第０９／１９９，１２０号に関連し、米国特許法第１１９条（ｅ）に基づき国内の優先権を主張し、その全開示がここに引用により援用される。
【０００２】
【発明の分野】
この発明は、キャッシュ管理に関し、より特定的には、他のノードのキャッシュに基づいてあるノードのキャッシュのデータの置換を管理することに関する。
【０００３】
【発明の背景】
クラスタは、１つ以上のＣＰＵによって共有される揮発性ダイナミックメモリデバイス（「ダイナミックメモリ」）を各々が有するノードの集合である。クラスタ中の各ノードは、配線によりそのクラスタの他のノードに接続される。典型的には、クラスタ中の各ノードは、そのクラスタの他のノードと資源を共有する。そのような資源は、たとえば、スタティックメモリデバイス（たとえばディスク記憶装置）に記憶されるページなどのデータ項目であり得る。
【０００４】
アプリケーションと称されるソフトウェアが、ノードの各々上で実行する。アプリケーションは、共有データ資源からのデータに作用する。たとえば、データシステムは、クラスタ中の各ノードで実行し、ディスク記憶装置上のデータブロックに記憶されたデータを管理し得る。
【０００５】
クラスタ中のノード上で実行するアプリケーションによって必要とされるデータ項目へのアクセスを高速化するために、データ項目のコピーがノードのキャッシュにキープされる。キャッシュは、そのデータ項目が別のソースからだとそれほど効率的に獲得できない場合に、効率的なアクセスのためにそのデータ項目のコピーを記憶するために使用される記憶媒体である。その他の、効率的にアクセスされないソースを、ここでは２次データ資源と言う。たとえば、クラスタ内のノード上で実行するデータシステムは、典型的には、ディスクに永続的にデータブロックを記憶する。しかしながら、データベースシステムは、ダイナミックメモリのキャッシュにデータブロックのコピーをロードしこれにアクセスする。同様に、パーソナルコンピュータ上で稼動するブラウザは、ネットワークを介して獲得された頻繁にアクセスされるウェブページを、ディスクファイルの形でキャッシュに記憶する。
【０００６】
ノード上のキャッシュはキャッシュマネージャによって管理される。キャッシュマネージャは、キャッシュと２次データ資源との間の入力および出力を低減する態様でキャッシュを管理しようとするソフトウェアのシステムである。典型的には、キャッシュマネージャは、最も頻繁にアクセスされるデータ項目のコピーをキャッシュにキープする。さらに、キャッシュマネージャは、アプリケーションがデータ項目に行なった修正を追跡でき、「ライトバック」、「ライトスルー」およびさまざまなロギングメカニズムを通じて、各データ項目が２次データ資源（例えばディスク記憶装置）に永続的に記憶されるように整理することができる。
【０００７】
特定のアプリケーションによって頻繁にアクセスされるデータ項目を集合的にアプリケーションのワーキングセットという。アプリケーションのワーキングセットが、アプリケーションが実行しているノード上のキャッシュに収まるには大きすぎるとき、アプリケーションはスラッシングする。スラッシングは、キャッシュ内のキャッシュされたデータ項目を２次データ資源からのデータ項目と不所望に高頻度で置換することを伴う。スラッシングは、頻繁にアクセスされるデータ項目がキャッシュ内で互いに絶えず置換するときに起こり、キャッシュミスを頻繁に発生し、そのため平均データ項目アクセス時間が劇的に増加してしまう。スラッシングが発生しアプリケーションがデータ項目を必要とするとき、アプリケーションは、２次データ資源から必要とされるデータ項目の検索を待つことにより、あまりにもしばしば遅延される。こうしてスラッシングはスループットを低減させてしまう。他方で、ワーキングセットが利用可能なダイナミックメモリに収まることができるとき、アプリケーションはスラッシングせず、システムのスループットが向上する。
【０００８】
スケーラブルクラスタとは、資源を追加して全体としてクラスタの容量を比例的に増やすことのできるクラスタである。資源は、たとえば、コンピュータ、ＣＰＵ、記憶装置、配線帯域幅、またはコンピュータごとのダイナミックメモリであってもよい。典型的には、容量は、ユーザの数、１秒あたりのウェブページヒット数、時間期間当りのトランザクション数、および／またはデータのテラバイトなどの、ビジネス成長の何らかの尺度に従って測定される。
【０００９】
容量の必要性がクラスタにおいて増すと、通常は、ＣＰＵの必要が高まり、しばしばワーキングセットが増える。追加のＣＰＵの必要性を見込んで、より多くのノードがクラスタに追加され得る。しかしながら、ワーキングセットの増大を見込むと、コンピュータをクラスタに単に追加する以上のことが必要となる。それどころか、そのクラスタ中のすべてのノードのダイナミックメモリを増やさなければならない、というのも各ノードは、ワーキングセットを記憶するのに十分なダイナミックメモリが必要であるからである。各ノードが、ワーキングセット全体を記憶するのに十分なダイナミックメモリを必要とするのは、頻繁にアクセスされるページの大部分が典型的には各ノードのキャッシュ内に複製されるからである。
【００１０】
いかなるコンピュータにとっても、追加できるダイナミックメモリの量は限られている。限界に達する前でさえも、アプリケーションによって必要とされるダイナミックメモリの総量は、クラスタ内のノードの数によって乗算されたそのワーキングセットに等しい。クラスタが大きくなると、もしワーキングセットも大きくなるのであれば、クラスタサイズにともない価格性能が落ち、クラスタは拡張しない。ワーキングセットが限界よりも大きければ、アプリケーションがスラッシングする。クラスタへのノードの追加は、クラスタのＣＰＵ能力を高め得るが、スラッシングを解消はしない。したがって、クラスタのスループットは悪くなる。
【００１１】
前述の説明に基づいて、ダイナミックメモリをクラスタ中の各ノードに追加することを必要としない、クラスタ上のスラッシングを低減するためのメカニズムを提供することが所望される。
【００１２】
【発明の概要】
クラスタ内のノード上のキャッシュを管理するためのメカニズムが記載される。キャッシュは、データ項目がノード上のいずれのキャッシュでも保持され得るように、グローバルに管理される。これは、たとえば、キャッシュのバッファに記憶されるデータ項目を置換するための置換ポリシーによって達成され得、バッファは、他のノードのキャッシュの状態を含む要因を説明する態様で置換のために選択される。いくつかのキャッシュされたデータ項目は、グローバルに共有されるものとしてされ、（静的または動的に）主要キャッシュが割当てられる。たとえば、あるバッファが、その主要キャッシュが別のノードであるデータ項目のコピーを維持しているならば、そのバッファのデータ項目は、これが主要キャッシュであるグローバルデータ項目またはローカルデータ項目よりも、置換が優先される。この発明の別の局面に従えば、異なったノード上のバッファのキャッシュ保持値が比較され、最低のキャッシュ保持値を有するバッファが置換のために選択される。この発明のさらに別の局面に従えば、置換ポリシーは、クラスタ中の他のキャッシュの構成を説明する
この発明は、添付の図面の図において制限的にではなく例として説明され、同様の参照番号は同様の要素を参照する。
【００１３】
【好ましい実施例の詳細な説明】
クラスタのノード上のキャッシュを管理するための方法および装置が記載される。以下の説明において、説明の目的で、この発明を完全に理解するために多くの具体的な詳細が述べられる。しかしながら、当業者にはこの発明がこれらの具体的な詳細なしに実施できることが明らかである。その他の場合には、この発明を不必要に不明瞭にすることを避けるために、周知の構造および装置がブロック図で示される。
【００１４】
例示のクラスタ
図１は、この発明の実施例が実現され得る例示のクラスタ１００を表わすブロック図である。クラスタ１００は、ノード１１０、１３０および１５０を含む。配線１６０がノード１１０と１３０と１５０とを接続し、そのためクラスタ１００中のいずれのノードも、データを別のコンピュータのダイナミックメモリに転送することができる。
【００１５】
ノード１１０、１３０および１５０の各々は、キャッシュおよびキャッシュマネージャを含む。具体的には、ノード１００は、キャッシュ１１４およびキャッシュマネージャ１１２を含み、ノード１３０はキャッシュ１３４およびキャッシュマネージャ１３２を含み、ノード１５０はキャッシュ１５４およびキャッシュマネージャ１５２を含む。この発明の実施例は、各々異なったノード上に存在するキャッシュを用いて例示されるが、この発明は、各々が異なったノード上に存在するキャッシュに限られるものでない。むしろ、この発明は、同じノード上に存在するキャッシュのサブセットを含むキャッシュ、またはすべてが同じノード上に存在するキャッシュで実現されてもよい。
【００１６】
キャッシュ１１４、１３４および１５４は、それぞれキャッシュマネージャ１１２、１３２および１５２によって管理され、クラスタ１００上で実行する１組のアプリケーションによってアクセスされるデータ項目を記憶する。この発明のある実施例では、アプリケーションの組はデータベースであってもよい。キャッシュマネージャ１１２、１３２および１５２の各々は、データベースシステムの管理下で実行する。キャッシュ１１４、１３４および１５４は、データベースシステムによって管理されるデータを含むデータブロックを記憶するために使用される。
【００１７】
キャッシュマネージャ１１２、１３２および１５２は集合的に「コヒーレントなクラスタキャッシュマネージャ」を形成する。コヒーレントなクラスタキャッシュマネージャは、アプリケーションが所与のキャッシュ中のデータ項目へのアクセスを要求し、かつそのデータ項目がその所与のキャッシュ内には記憶されていないか別のキャッシュに記憶されているとき、データ項目のコピーが別のキャッシュからその所与のキャッシュに直接コピーされるような態様で、キャッシュをグローバルに管理する、クラスタ上で実行するソフトウェアのシステムである。データ項目が修正された場合、修正されたデータ項目のコピーは、そのデータ項目を最初に２次データ資源に永続的に記憶することなしに、その所与のキャッシュに転送され得る。コヒーレントなキャッシュマネージャの一例は、キャッシュを管理するデータベースシステムを記載するクロッツに記載される。
【００１８】
コヒーレントなクラスタキャッシュマネージャは、クラスタ上の典型的な従来のキャッシュマネージャと異なる。従来のキャッシュマネージャは、典型的には、クラスタ中のあるノード上で動作し、そのノードが、ノード上にキャッシュされていないデータ項目を必要とするとき、それは別のノードのキャッシュからではなく２次データ資源からデータ項目のコピーを取得する。実際に、従来のキャッシュマネージャは、キャッシュが同じノードに存在していようとも異なったノードに存在していようとも、要求されたデータ項目のコピーが別のキャッシュに存在することを知らない。したがって、データ項目のコピーを取得するために、従来のマネージャは、ディスク記憶システムなどの２次データ資源にアクセスするという負担を招く。
【００１９】
ディスク記憶システムなどの２次データ資源にアクセスすることは、比較的費用の高くつく入力および出力動作を伴う。他方で、クラスタ中の別のノードのダイナミックメモリにアクセスすることは、比較的安価な動作である。したがって、別のキャッシュからデータ項目のコピーを取得することは、そのキャッシュが別のノードに存在するかどうかにかかわらず、２次データ資源からコピーを取得することよりもはるかに安く済む。
【００２０】
要求されたデータ項目を別のキャッシュからより安価に取得できることにより、頻繁にアクセスされるデータ項目の複製は、それらがクラスタ中の少なくとも１つのキャッシュに保持されている限り、スラッシングを引起すことなしにあるキャッシュから除去することができる。頻繁にアクセスされるページのコピーを２次データ資源から再検索するのではなく、コピーは、別のノードのキャッシュからはるかにより安価で再検索される。
【００２１】
スラッシングを引起すことなしにデータ項目の複製を減らすことができるので、クラスタ内のノード間でワーキングセットを割当てることが実現可能となる。ワーキングセットは、すべてのノード上に複製されるのではなくノード間で分割されるので、ワーキングセットのための付加的なダイナミックメモリは、すべてのノードのダイナミックメモリを増やすのではなく、あるノードをコンピュータに追加することによって設けることができる。したがって、効率性のために、ワーキングセットのサイズは、コンピュータのダイナミックメモリ容量によって制限されず、それにより、スケーラビリティはワーキングセットのサイズおよびクラスタ中のノードのダイナミックメモリの容量によって制限されない。
【００２２】
たとえば、４個のノードがあるクラスタ上で実行するデータベースシステムによって頻繁にアクセスされる１０００個のデータブロックがあるとする。ワーキングセットが割当てられると、頻繁にアクセスされるブロックは、ノードのキャッシュに複製される必要がない。したがって、キャッシュの各々が２５０個の頻繁にアクセスされるデータブロックを維持するようにワーキングセットが分割され得る。別のノードが追加される場合、ノードの各々は２００個のブロックを維持するようになる。ワーキングセットが分割されなければ、各ノードは１０００個のブロックを維持するのに十分なダイナミックメモリを有していなければならない。
【００２３】
データ項目の複製を低減する置換ポリシー
ここに記載される、グローバルキャッシュに記憶されるデータ項目の複製を低減するための技術は、キャッシュマネージャの置換ポリシーに組込まれる。ここで使用されるグローバルキャッシュという言葉は、たとえば、クラスタ内のノードなどの１つ以上のノードのキャッシュの組のことをいい、キャッシュの各々は、１つ以上のアプリケーションの組によってアクセスされるデータ項目を維持する。あるキャッシュマネージャによって管理される特定のキャッシュを、そのキャッシュマネージャに対してローカルなキャッシュという。置換ポリシーとは、バッファが所与のデータ項目を維持するために必要とされるとき、データ項目を既に含むバッファを選択するためにキャッシュマネージャによって遵守される規則および手続の組のことである。選択されたバッファにおけるデータ項目は所与のデータ項目と置換される。したがって、キャッシュマネージャは、比較的低いキャッシュ保持値を有するデータを含むバッファを選択する。
【００２４】
キャッシュ保持値とは、キャッシュ内のデータ項目を保持することがキャッシュの効率的な動作のためになる程度の尺度である。典型的には、最も頻繁にアクセスされるデータ項目はより大きなキャッシュ保持値を有する、なぜならキャッシュにそれらを保持することで、キャッシュと２次データソースとの間の入力および出力動作の数が多くなることを回避するからである。保持するという言葉は、特定のデータ項目が別のデータ項目、典型的にはより低いキャッシュ保持値を有するデータ項目よりも長くキャッシュ内にとどまる可能性を増す動作を実行することをいう。保持は、別のデータ項目を置換のために選択したり、または他のデータ項目に対してより低いキャッシュ保持値を単に割当てることをいってもよい。
【００２５】
種々の要因を用いてバッファのキャッシュ保持値を決定することができる。たとえば、最近に最もアクセスされたデータ項目は将来にアクセスされる可能性が最も高いので、最近に最もアクセスされたデータ項目は通常、最近最もアクセスされなかったものよりも大きなキャッシュ保持値を有する。キャッシュマネージャは、最近最もアクセスされたものから最近最もアクセスされなかったものまでバッファを順序付ける最近使用頻度リスト（ＬＲＵ）を保守し得る。最近に最もアクセスされた項目はリストの最上部にあり、最近最も使用されなかったものはリストの下部にある。したがって、ＬＲＵ内のバッファの位置は、バッファ内に維持されるデータ項目のキャッシュ保持値を示す。考慮され得る別の要因は、最近のある期間内でデータ項目がどれだけ頻繁にアクセスされるかである。ごく最近に最も頻繁にアクセスされたデータ項目はより大きいキャッシュ保持値を有する、というのもこれらのデータ項目は近い将来アクセスされる可能性が最も高いからである。ここに記載される技術に従ってキャッシュ保持値を決定するにあたって、キャッシュマネージャは、１つのローカルキャッシュのみでなくグローバルキャッシュを伴う要因も説明する置換ポリシーに従う。これらの要因の１つは、データ項目がグローバルキャッシュのキャッシュに複製されるか否かである。
【００２６】
データ項目の複製コピーの低減
図２は、クラスタのキャッシュ内のデータ項目の複製コピーを低減する置換ポリシーを少なくとも部分的に実現するために辿られ得るプロセスを表わすフローチャートである。ステップは、キャッシュマネージャによって管理されるキャッシュ内のデータ項目の要求を受信するとキャッシュマネージャによって行なわれる。ステップは、図１に示すクラスタ１００を用いて例示される。
【００２７】
図１を参照して、ステップ２１０で、キャッシュマネージャ１１２は、キャッシュ１１４に記憶されるデータ項目をキャッシュ１３４に直接転送するリクエストをキャッシュマネージャ１３２から受信する。ステップ２２０で、キャッシュマネージャ１１２は、要求されたデータ項目をキャッシュ１３４に直接転送する。
ステップ２３０で、転送されたデータ項目が、他のキャッシュでの複製の価値があるデータ項目であるか否かが判定される。一般的に、複製の価値があるデータ項目は、たとえばダイナミックメモリの使用の増大の点で、それらを複製するコストがそれらの複製を正当化するような高いキャッシュ保持値を有する。たとえば、キャッシュ１１０において最も頻繁にアクセスされたデータ項目は複製の価値があるであろう。転送されたデータ項目が複製の価値あるデータ項目であると判定された場合、図１に示すステップは終了する。さもなくば、ステップの実行はステップ２４０に続く。
【００２８】
ステップ２４０で、キャッシュマネージャ１１２は、そのデータ項目を維持するバッファを置換可能なものと確立する。バッファを置換可能であると確立することは、置換処理中に選択される資格をそれに与えることである。置換可能なバッファを確立するための種々の方法がある。たとえば、バッファは、バッファ内のフラグをセットすることにより即座に置換可能であると表示されてもよく、または置換可能なバッファのリストに追加されてもよい。
【００２９】
キャッシュマネージャ１１２が置換処理を行なうとき、それは、即座に置換可能であるものとして確立されていたバッファを選択し得る。たとえば、キャッシュマネージャ１１２によって保守されるＬＲＵでのその地位が、アクセスの新しさが比較的高いデータ項目をそのバッファが維持すると示したとしても、このバッファは選択され得る。バッファのデータ項目が別のキャッシュに転送されてしまったので即座に置換可能であると確立されたバッファを、キャッシュマネージャが置換のために選択するとき、キャッシュマネージャは、グローバルキャッシュの状態を説明する置換ポリシーに従っている。具体的には、キャッシュマネージャは、少なくとも別のキャッシュに記憶されている理由もあって、データ項目を置換する。
【００３０】
一方で、別のキャッシュ上のデータ項目のコピーの存在は、バッファをその含まれたデータの置換のために選択するために用いられ得る要因の１つにすぎない。考慮すべき他の要因は、ＬＲＵリストにおけるバッファの位置などの、既に述べたものを含む。
【００３１】
異なったキャッシュにおけるデータ項目間のキャッシュ保持値の説明
データ項目が別のキャッシュ上に複製されているか否かを説明する置換ポリシーは、クラスタ内の複数のノード上のキャッシュの状態をいかに説明し得るかの一例にすぎない。図３は、複数のノード上のキャッシュの状態を説明する別のプロセスを表わす。あるキャッシュマネージャが、別のノードのキャッシュに記憶されているデータ項目を要求するとき、このプロセスは行なわれる。
【００３２】
図３を参照して、ステップ３１０で、キャッシュマネージャ１１２は、キャッシュ１１４に記憶されるデータ項目を直接転送する要求をキャッシュマネージャ１３２から受信する。
【００３３】
ステップ３２０で、キャッシュマネージャ１１２は、要求されたデータ項目、およびキャッシュ１１４内のいずれかのバッファと関連付けられる最低のキャッシュ保持値を示すデータをキャッシュマネージャ１３２に直接転送する。最低キャッシュ保持値を有するキャッシュ１１４内のバッファは、要求されたデータ項目が存在するキャッシュ１１４内のバッファでなくてもよい。さまざまなメカニズムを用いて、バッファのキャッシュ保持値を確立することができる。たとえば、最低のキャッシュ保持値を示すデータは、前回データ項目がアクセスされたことを示すデータであってもよく、またはある時間期間内にアクセスされた頻度を特定するデータであってもよい。
【００３４】
ステップ３３０で、キャッシュマネージャ１３２は、要求されたデータ項目、および最低のキャッシュ保持値を示すデータ（「受信キャッシュ保持値」）を受信する。
【００３５】
ステップ３３５で、キャッシュマネージャ１３２は、キャッシュマネージャ１１２からキャッシュマネージャ１３２に送信された要求データ項目と置換するためにキャッシュ１３４内のバッファを選択する。
【００３６】
ステップ３４０で、キャッシュマネージャ１３２は、受信キャッシュ保持値が、置換のために選択されたバッファ内のデータ項目（「選択データ項目」）のキャッシュ保持値よりも大きいか否かを判定する。選択データ項目が、受信保持値よりも大きいキャッシュ保持値を有しているならば、制御はステップ３５０に続き、キャッシュマネージャ１３２は、選択データ項目をキャッシュマネージャ１１２に送信する。
【００３７】
一方で、受信キャッシュ保持値が選択データ項目のキャッシュ保持値よりも大きければ、ステップ３７５で、選択データ項目をキャッシュマネージャ１１２に送信することなしに、要求ノードは受信データ項目と選択データ項目を置換する。
【００３８】
ステップ３５０で、キャッシュマネージャ１３２は、選択データ項目をキャッシュマネージャ１１２に送信する。ステップ３６０で、キャッシュマネージャ１１２は選択データ項目を受信する。ステップ３７０で、キャッシュマネージャ１１２は、キャッシュ１１４内の最低のキャッシュ保持値を有するバッファ内のデータ項目を選択データ項目と置換する。次に制御はステップ３７５に進む。
【００３９】
グローバルキャッシュの構成に基づく置換ポリシー
ここに記載される技術は、クラスタ内のキャッシュのグローバルな状態を説明する置換ポリシーを組込む。しかしながら、置換ポリシーは、キャッシュのグローバルな状態以外のグローバルな構成を説明してもよい。たとえば、特定のキャッシュのための置換ポリシーは、他のキャッシュの構成に基づいてもよい。キャッシュの構成は、キャッシュの動作を支配し、キャッシュの動作中に変化しない論理および値である。一方で、キャッシュの状態は、キャッシュの動作中に変化する集合的な現在の値である。たとえば、キャッシュの状態は、キャッシュのバッファ内のデータ項目を含む。さらに、キャッシュの状態は、ＬＲＵにおけるバッファの位置、またはバッファのアクセス頻度など、キャッシュが動作すると変化する、バッファまたはバッファ内のデータ項目の属性を表わす値を含む。キャッシュの構成は、キャッシュの動作を支配するソフトウェア、およびキャッシュのサイズまたはキャッシュ内のバッファの数などの動作パラメータの値を含んでもよい。
【００４０】
以下の例は、キャッシュの置換ポリシーが他のキャッシュの構成にいかに基づき得るかを示す。データベースがクラスタ上で実行しており、１つのキャッシュがデータブロックの特定の組に対して「ホーム」であるようにクラスタのノード上のキャッシュが構成されると仮定する。データブロックの特定の組に対して「ホーム」であるキャッシュを、ここではデータブロックのその組の主要キャッシュという。キャッシュマネージャが置換するためにキャッシュ内のバッファを選択しなければならないとき、キャッシュマネージャはまず、主要キャッシュなしのデータ項目を選択する前に主要キャッシュが別のキャッシュであるデータ項目を有するバッファ、または主要キャッシュが現在のキャッシュであるデータ項目を有するバッファを選択する。キャッシュマネージャが、キャッシュマネージャによって管理されるキャッシュ内のバッファを選択するとき、これは別のキャッシュの構成がそれをそのバッファのデータ項目の主要キャッシュとしているからであるが、キャッシュマネージャは別のキャッシュの構成を説明する置換ポリシーに従っている。
【００４１】
シェアードナッシングシステムのための主要キャッシュ
データ項目の主要キャッシュに基づく置換ポリシーのさらなる例は、特定のデータ項目のための主要キャッシュが、あるデータ項目の２次データ資源に直接アクセスし得るノードのキャッシュであるグローバルキャッシュのための置換ポリシーである。このようにデータ項目のための主要キャッシュとしてキャッシュを扱うことは、特にシェアードナッシングシステムにとって有利である。したがって、シェアードナッシングシステムの記載が有用である。
【００４２】
マルチプロセッシングシステムには３つの一般的なタイプがある：シェアードエブリシング、シェアードディスクシステム、およびシェアードナッシングシステムである。シェアードエブリシングシステムにおいては、すべてのプロセッサ上のプロセスは、システム内のすべてのダイナミックメモリデバイスおよびすべてのスタティックメモリデバイスへの直接アクセスを有する。シェアードエブリシングの機能を設けるためには、さまざまなコンピュータ要素間の高度の配線が必要とされる。
【００４３】
シェアードディスクシステムにおいては、プロセッサおよびダイナミックメモリデバイスはノードにグループ化される。シェアードディスクシステムにおける各ノードは、複数プロセッサおよび複数メモリを含むシェアードエブリシングシステムをそれ自体構成し得る。すべてのプロセッサ上のプロセスは、システム内のすべてのスタティックメモリデバイスにアクセスすることができるが、特定のノードに属するプロセッサ上のプロセスのみが、特定のノード内のダイナミックメモリデバイスに直接アクセスすることができる。シェアードディスクシステムは、一般的に、シェアードエブリシングシステムよりも配線が少なくてすむ。
【００４４】
シェアードナッシングシステムにおいては、すべてのプロセッサ、ダイナミックメモリデバイスおよびスタティックメモリデバイスがノードにグループ化される。シェアードディスクシステムにおいてのようにシェアードナッシングシステムにおいては、各ノードが、シェアードエブリシングシステムまたはシェアードディスクシステムをそれ自体構成し得る。特定のノード上で実行するプロセスのみが、その特定のノード内のダイナミックメモリデバイスおよびスタティックメモリデバイスに直接アクセスすることができる。
【００４５】
シェアードナッシングシステムにおいては、データ項目が、静的記憶装置の形の二次データ資源からダイナミックメモリ中のキャッシュに転送される場合、静的記憶装置への直接アクセスを有するノードが、データ項目をノードのダイナミックメモリに読出す。別のノードの別のダイナミックメモリのキャッシュがそのデータ項目の主要キャッシュであるならば、そのデータ項目はそこに転送され、データ項目のさらなる転送が生じてしまう。これは、データ項目を維持する二次資源への直接アクセスを有するノードをそのデータ項目のための主要キャッシュとして扱うことにより回避され得る。
【００４６】
ハードウェア概要
図４は、この発明の実施例を実現するために使用され得るコンピュータシステム４００を説明するブロック図である。コンピュータシステム４００は、情報をやり取りするためのバス４０２または他の通信メカニズムと、バス４０２に結合され情報を処理するプロセッサ４０４とを含む。コンピュータシステム４００は、バス４０２に結合され、プロセッサ４０４によって実行されるべき命令および情報を記憶するための、ランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置などの主メモリ４０６も含む。主メモリ４０６は、プロセッサ４０４によって実行される命令の実行中に一時変数または他の中間情報を記憶するために使用されてもよい。コンピュータシステム４００はさらに、バス４０２に結合されプロセッサ４０４のための静的情報および命令を記憶するためのリードオンリメモリ（ＲＯＭ）４０８または他の静的記憶装置を含む。磁気ディスクまたは光ディスクなどの記憶装置４１０が設けられ、バス４０２に結合され命令および情報を記憶する。
【００４７】
コンピュータシステム４００は、コンピュータのユーザに情報を表示するための陰極線管（ＣＲＴ）などのディスプレイ４１２にバス４０２を介して結合され得る。英数字および他のキーを含む入力装置４１４がバス４０２に結合され、プロセッサ４０４に情報およびコマンド選択を交信する。ユーザ入力装置の別のタイプは、方向情報およびコマンド選択をプロセッサ４０４に交信しかつディスプレイ４１２上のカーソルの動きを制御するマウス、トラックボールまたはカーソル方向キーなどのカーソルコントロール４１６である。この入力装置は、典型的には、第１の軸（たとえばｘ）および第２の軸（たとえばｙ）の２つの軸における２つの自由度を有しており、装置が平面上の位置を特定することを可能にする。
【００４８】
この発明は、ここに記載される技術を実現するためのコンピュータシステム４００の使用に関する。この発明のある実施例に従えば、これらの技術は、プロセッサが主メモリ４０６に含まれる１つ以上の命令の１つ以上のシーケンスを実行することに応答してコンピュータシステム４００によって実現される。そのような命令は、記憶装置４１０などの別のコンピュータ読出可能媒体から主メモリ４０６に読出されてもよい。主メモリ４０６に含まれる命令のシーケンスの実行により、プロセッサ４０４はここに記載されるプロセスステップを行なう。代替の実施例では、この発明を実現するためのソフトウェア命令の代わりにまたはこれと組合せてハードワイヤードの回路構成が使用されてもよい。したがって、この発明の実施例は、ハードウェア回路構成とソフトウェアの如何なる特定の組合せにも限定されるものでない。
【００４９】
ここで使用される「コンピュータ読出可能媒体」という言葉は、命令をプロセッサ４０４に与えて実行させることに関わる任意の媒体のことをいう。そのような媒体は、不揮発性媒体、揮発性媒体および伝送媒体を含むがこれに限られるものでない多くの形をとり得る。不揮発性媒体は、たとえば、記憶装置４１０などの光ディスクまたは磁気ディスクを含む。揮発性媒体は、主メモリ４０６などのダイナミックメモリを含む。伝送媒体は、バス４０２を含む配線を含む、同軸ケーブル、銅線および光ファイバを含む。伝送媒体は、無線および赤外線データ通信の際に生成されるものなどの音波または光波の形をとってもよい。
【００５０】
コンピュータ読出可能媒体の通常の形は、たとえば、フロッピー（Ｒ）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、もしくは任意の他の磁気媒体、ＣＤ−ＲＯＭ、任意の他の光学的媒体、パンチカード、ペーパテープ、穴のパターンを有する任意の他の物理的媒体、ＲＡＭ、ＰＲＯＭ、およびＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、任意の他のメモリチップもしくはカートリッジ、以下に記載される搬送波、またはコンピュータが読出すことのできる任意の他の媒体を含む。
【００５１】
コンピュータ読出可能媒体のさまざまな形が、１つ以上の命令の１つ以上のシーケンスをプロセッサ４０４に運んで実行させることに関わり得る。たとえば、命令は最初に遠隔コンピュータの磁気ディスク上に担持されていてもよい。遠隔コンピュータは、命令をそのダイナミックメモリにロードし、モデムを用いて電話線を介して命令を送信することができる。コンピュータシステム４００にローカルなモデムが、電話線でデータを受信し、赤外線送信機を用いてデータを赤外線信号に変換することができる。赤外線検出器が、赤外線信号で運ばれたデータを受信することができ、適切な回路がデータをバス４０２に与えることができる。バス４０２は、データを主メモリ４０６に運び、プロセッサ４０４はそこから命令を取出して実行する。主メモリ４０６によって受信された命令は、任意選択で、プロセッサ４０４による実行の前または後に記憶装置４１０に記憶されてもよい。
【００５２】
コンピュータシステム４００は、バス４０２に結合される通信インターフェイス４１８も含む。通信インターフェイス４１８は、ローカルネットワーク４２２に接続されるネットワークリンク４２０に結合する双方向のデータ通信を与える。たとえば、通信インターフェイス４１８は、サービス統合デジタル網（ＩＳＤＮ）カードまたはモデムであってもよく、データ通信接続を対応の型の電話線に与える。別の例として、通信インターフェイス４１８は、ローカルエリアネットワーク（ＬＡＮ）カードであってもよく、データ通信接続を互換性あるＬＡＮに与える。ワイヤレスリンクが実現されてもよい。いずれのそのような実現化例でも、通信インターフェイス４１８は、さまざまな形の情報を表わすデジタルデータストリームを運ぶ電気、電磁または光信号を送受信する。
【００５３】
ネットワークリンク４２０は、典型的には、１つ以上のネットワークを介して他のデータ装置にデータ通信を与える。たとえば、ネットワークリンク４２０は、ローカルネットワーク４２２を介してホストコンピュータ４２４にまたはインターネットサービスプロバイダ（ＩＳＰ）４２６によって作動されるデータ機器に通信を与え得る。そして、ＩＳＰ４２６は、現在通常「インターネット」と呼ばれるワールドワイドパケットデータ通信ネットワーク４２８を介してデータ通信サービスを与える。ローカルネットワーク４２２およびインターネット４２８はどちらも、デジタルデータストリームを運ぶ電気、電磁または光信号を用いる。デジタルデータをコンピュータシステム４００へとおよびそこから運ぶ、さまざまなネットワークを介する信号およびネットワークリンク４２０で通信インターフェイス４１８を介する信号は、情報を転送する搬送波の例示の形である。
【００５４】
コンピュータシステム４００は、ネットワーク、ネットワークリンク４２０および通信インターフェイス４１８を介して、プログラムコードを含むデータを受信しメッセージを送信することができる。インターネットの例では、サーバ４３０が、インターネット４２８、ＩＳＰ４２６、ローカルネットワーク４２２および通信インターフェイス４１８を介してアプリケーションプログラムのための要求されたコードを送信し得る。この発明に従えば、あるそのようなダウンロードされたアプリケーションがここに記載される技術を実現する。
【００５５】
受信されたコードは、受信されたときにプロセッサ４０４によって実行されてもよく、および／または記憶装置４１０もしくは他の不揮発性記憶装置に記憶されて後に実行されてもよい。このように、コンピュータシステム４００は、搬送波の形でアプリケーションコードを獲得し得る。
【００５６】
前述の明細書において、この発明はその具体的な実施例に参照して記載された。しかしながら、この発明のより広範な精神および範囲から逸脱することなしにこれにさまざまな変形および変更を加え得ることは明らかである。したがって、この明細書および図面は、制限的な意味ではなく例示的に考えられるべきである。
【図面の簡単な説明】
【図１】例示のクラスタのブロック図である。
【図２】この発明の実施例に従うキャッシュを管理するための技術を実現するプロセスのフローチャートである。
【図３】この発明の実施例に従うキャッシュを管理するための技術を実現するプロセスのフローチャートである。
【図４】この発明の実施例が実現され得るコンピュータシステムのブロック図である。
【図１】
2004511840.tif 000003
【図２】
2004511840.tif 000004
【図３】
2004511840.tif 000005
【図４】
2004511840.tif 000006
【国際公開パンフレット】
2004511840.tif 000007
2004511840.tif 000008
2004511840.tif 000009
2004511840.tif 000010
2004511840.tif 000011
2004511840.tif 000012
2004511840.tif 000013
2004511840.tif 000014
2004511840.tif 000015
2004511840.tif 000016
2004511840.tif 000017
2004511840.tif 000018
2004511840.tif 000019
2004511840.tif 000020
2004511840.tif 000021
2004511840.tif 000022
2004511840.tif 000023
2004511840.tif 000024
2004511840.tif 000025
2004511840.tif 000026
2004511840.tif 000027
2004511840.tif 000028
2004511840.tif 000029
2004511840.tif 000030
【国際公開パンフレット（コレクトバージョン）】
2004511840.tif 000031
2004511840.tif 000032
【国際調査報告】
2004511840.tif 000033
2004511840.tif 000034
2004511840.tif 000035
2004511840.tif 000036
2004511840.tif 000037