(57)【要約】【課題】  ロックのオーバヘッドなしに更新される集中キャッシュを提供すること。【解決手段】  更新は、途中で割り込むことができない点で「アトミック」である。アプリケーションは、参照テーブルを介してデータにアクセスして、常に自由に集中キャッシュ内のデータを読み込む。アプリケーションは直接キャッシュを更新せず、その代わりに更新要求をサービスルーチンに送る。キャッシュを更新するために、サービスルーチンは、２つの段階で進行する。第１の段階で、サービスルーチンは、参照テーブルを更新することなしに、新しいデータを準備し、それらをキャッシュに追加する。第１段階の間、キャッシュにアクセスするアプリケーションは、参照テーブルがまだ更新されていないため、新しいデータを「見る」ことができない。第１段階が完了した後で、サービスルーチンは、更新プロセスの第２段階、すなわち参照テーブルの自動更新を実行する。この２段階更新プロセスは、キャッシュを常に一貫した状態にしておく。【選択図】  図１ｂ
2007184009.tif 000002
【特許請求の範囲】
【請求項１】
コンピューティングデバイスのユーザがキャッシュサービスルーチンのパラメータを変更する方法であって、
前記キャッシュサービスルーチンが既存の集中キャッシュから選択されたデータ要素を新たな集中キャッシュに設置するときに前記キャッシュサービスルーチンによって用いられるヒューリスティックを表示するステップであって、前記選択は少なくとも部分的には前記ヒューリスティックに基づく、ステップと、
前記ユーザから新たなヒューリスティックの指示を受け取るステップと、
前記新たなヒューリスティックを表示するステップと、
前記新たなヒューリスティックを前記キャッシュサービスルーチンにアクセス可能とするステップと、
を含むことを特徴とする方法。
【請求項２】
請求項１記載の方法において、前記新たなヒューリスティックは、最も最近用いられたもの、最も頻繁に用いられたもの及びラウンドロビンから選択されることを特徴とする方法。
【請求項３】
請求項１記載の方法において、
前記既存の集中キャッシュの現行のサイズを表示するステップと、
前記既存の集中キャッシュの最大許容サイズを表示するステップと、
前記ユーザから新たな最大許容サイズの指示を受け取るステップと、
前記新たな最大許容サイズを表示するステップと、
前記新たな最大許容サイズを前記キャッシュサービスルーチンにアクセス可能とするステップと、
を更に含むことを特徴とする方法。
【請求項４】
請求項１記載の方法において、前記既存の集中キャッシュの使用統計を表示するステップを更に備えていることを特徴とする方法。
【請求項５】
コンピューティングデバイスのユーザが、キャッシュサービスルーチンのパラメータを変更するための方法であって、
前記キャッシュサービスルーチンが既存の集中キャッシュから選択されたデータ要素を新たな集中キャッシュに設置するときに前記キャッシュサービスルーチンによって用いられるヒューリスティックを表示するステップであって、前記選択は少なくとも部分的には前記ヒューリスティックに基づく、ステップと、
前記ユーザから新たなヒューリスティックの指示を受け取るステップと、
前記新たなヒューリスティックを表示するステップと、
前記新たなヒューリスティックを前記キャッシュサービスルーチンにアクセス可能とするステップと、
を含む方法を実行する命令を含むコンピュータ読取可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にコンピュータメモリ記憶技術に関し、より詳細には、キャッシュメモリに関する。
【背景技術】
【０００２】
コンピュータアプリケーションによって必要とされる一部のデータは、作成またはアクセスするのにコストがかかる。このコストには、データを計算するためのコンピュータ資源、およびネットワークを介してデータにアクセスするための（帯域幅および時間を含む）移送コストが含まれる。コンピューティングデバイスは、資源を費やしてこれらのデータを作成し、またはこれらのデータにアクセスした後、しばしばそのデータを「キャッシュ」メモリ内に記憶することになる。これにより、コンピューティングデバイスが再びデータを必要とする場合には、コストをかけずにキャッシュからアクセスすることができる。
【０００３】
キャッシュは、最初の（ｏｒｉｇｉｎａｌ）アプリケーションに対して、または最初のコンピューティングデバイスのローカルに置くことができ、あるいはいくつかのアプリケーションおよびデバイスの間で共有することができる。後者のタイプのキャッシュは、しばしば「中央」キャッシュ（ｃｅｎｔｒａｌｃａｃｈｅ）と呼ばれる。他のアプリケーションと集中キャッシュを共有する一方、各アプリケーションがそれ自体で使用するローカルキャッシュをサポートするような環境がある。集中キャッシュは、複数のアプリケーションにとって有用なデータを記憶するために最適化され、一方、ローカルキャッシュは、各アプリケーション特有のデータについてキャッシュする利点がある。
【０００４】
集中キャッシュ内のデータを管理することは容易ではない。集中キャッシュからデータを読み込もうとする複数のアプリケーションが問題となることはまれであるが、少なくとも１つのアプリケーションがデータをキャッシュに追加しようとするとき同様にまれとは言うことはできない。１つのアプリケーションがキャッシュに書き込むのと同時に、他のアプリケーションが集中キャッシュから読み込むことを認められた場合、読取り側は古い、または誤ったデータを得る可能性がある。このアクセス調整は、複数のアプリケーションがデータをキャッシュに追加しようとするときより問題となる。
【０００５】
このアクセス調整問題を改善するための一般的な手法は、「キャッシュロック」と呼ばれる。あるアプリケーションがキャッシュの内容を、追加、削除、または修正することによって変更したいと望むときはいつでも、「ロック」データ構造への単独のアクセスを要求する。ロックを有している間、書込み側アプリケーションはキャッシュを修正することができ、他のアプリケーションは、書込み側がロックを有する限りキャッシュにアクセスすることができない。したがって、読取り側は、古い、または誤ったデータを得ることがない。２つのアプリケーションが共にキャッシュを修正したいと望む場合には、その一方は、他方がロックを放棄するまで待たなければならない。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ロックは、集中キャッシュへのアクセスを調整する際に大いに有用となり得る。しかし、あるアプリケーションがキャッシュを修正したいと望むときはいつでも、アプリケーシ
ョンすべてロックによりアクセスが遅延することは明らかである。アプリケーションがこの遅延に容易に耐えられるような集中キャッシュもあるが、他のキャッシュの場合、これが本当の厄介者となる可能性がある。たとえば、フォントグリフキャッシュを考えてみる。コンピュータ画面上で表示される文字は、「グリフ」と呼ばれる個々の要素で構成されている。これらのグリフのいくつかが著しい量のデータを含み、グリフのいくつかが、その生成時に著しいコンピュータ資源を消費すると、これらは集中キャッシュの理想的な対象となる。しかし、新しいグリフがフォントグリフキャッシュに追加される間、それをロックすることは、コンピュータの画面に書き込むアプリケーション内で顕著な遅延を引き起こす可能性がある。
【０００７】
集中キャッシュにとって使用することができるメモリ資源が限られていると、別のキャッシュ管理の問題が生ずる。データをキャッシュに追加しようとする複数のアプリケーションは、互いに独立して動作する。したがって、これらのどのアプリケーションも、動作環境を全体的に改善するためにどのデータを集中キャッシュに追加すべきかについて「グローバル」な視野を持っていない。集中キャッシュが非常に大きくなって、さらなる追加を可能にするために、より小さいサイズで再構成されるときも同じ問題が生ずる。１つのアプリケーションも、どのデータを集中キャッシュ内で保持すべきか、また、今後のキャッシュの増大に対応してメモリを解放するため、どのデータを除去するのが最善か判断することができない。
【０００８】
本発明は、このような問題に鑑みて、ロックの遅延オーバヘッドなしに更新することができ、キャッシュ内のデータの重要度についてグローバルな視野を有する集中キャッシュを提供することを目的とする。
【課題を解決するための手段】
【０００９】
「アトミックな」（ａｔｏｍｉｃ）更新により、ロックの遅延オーバヘッドを被ることなくアクセス調整の利益を得ることができる。キャッシュ更新は、途中で割り込まれないように設計されている点で「アトミック」である。これらにより、アプリケーションによってアクセスされたとき常に最新かつ一貫性のあるキャッシュが提供される。
【００１０】
アプリケーションは、参照テーブルを介してデータにアクセスし、常に自由に集中キャッシュ内のデータを読み込む。しかし、アプリケーションは直接キャッシュを更新せず、その代わりに更新要求をサービスルーチンに送る。キャッシュを更新するために、キャッシュサービスルーチンは、２つの段階で進められる。第１の段階で、キャッシュサービスルーチンは、参照テーブルを更新することなしに新しいデータを準備してそれらをキャッシュに追加する。この第１段階は一定の時間がかかる可能性があるが、キャッシュがロックされていないため、キャッシュはアプリケーションにとって完全にアクセス可能な状態にある。第１段階において、キャッシュにアクセスするアプリケーションは、参照テーブルがまだ更新されていないので、新しいデータを「覗く」ことができない。キャッシュデータが完全に準備されてキャッシュ内にロードされた後になって始めて、キャッシュサービスルーチンは、更新プロセスの第２段階、すなわち参照テーブルの更新を実行する。この更新は、ポインタを１つだけ変更するステップからなり、キャッシュをロックすることなしに自動的に実行される。したがって、この２段階更新プロセスは、キャッシュをロックすることを必要とせず、アクセスするアプリケーションに対してキャッシュを常に有効な状態にしておく。更新はすべて、１つのキャッシュサービスルーチンによって実行されるため、複数のキャッシュ書込み側の間で調整するためにロックする必要はない。
【００１１】
キャッシュサービスルーチンは、キャッシュ内のデータがどのように使用されるかについての統計値を収集する。キャッシュが非常に大きくなったとき、キャッシュサービスルーチンは、これらの統計値を使用して、どのデータを新しいキャッシュ内にコピーすべき
か判断する。新たなキャッシュは、同様に２段階で自動的に作成される。第１段階において、キャッシュサービスルーチンは新たなキャッシュを作成し、古いキャッシュから選択されたデータを配置する。アプリケーションは、まだ新たなキャッシュについて認識していない。新たなキャッシュの使用の準備ができたとき、キャッシュサービスルーチンは、古いキャッシュのヘッダ内に新たなキャッシュへの参照を追加する。次いで、第２段階で、アトミックな別の処理を使用して、キャッシュサービスルーチンは古いキャッシュを「廃止」とマークする。アプリケーションは、古いキャッシュが廃止とマークされていることに気付くと、新たなキャッシュへの参照を追って、新たなキャッシュのみ使用を開始する。キャッシュ内の更新におけるのと同様に、キャッシュ全体を置き換えるためのこの機構を実行することにより、アプリケーションは常に一貫性のあるキャッシュを見ことができる。
【００１２】
アプリケーションは、廃止フラグに気付いて新たなキャッシュに切り替えるまで、廃止されたキャッシュを引き続き使用することができる。アプリケーションすべてが切り替えられた後で、廃止されたキャッシュは自動的に削除される。
【００１３】
実施形態には、キャッシュ内の参照テーブルが、キャッシュ内の別のロケーションに関連して、キャッシュ内に記憶されたデータのロケーションを特定するオフセットからなるものがある。これは、キャッシュをファイルとして記憶することができ、コンピューティングデバイスがキャッシュの再ブートを行った後に、直ちに再使用することができる点で有利である。
【００１４】
集中キャッシュは、１つのコンピューティングデバイスによって提供され（ｈｏｓｔ）、そのコンピューティングデバイス上のアプリケーションによって使用することができ、または他のコンピューティングデバイス上のアプリケーションによって使用することができる。各アプリケーションはまた、集中キャッシュと共に使用するために、それ自体のローカルキャッシュを有することができる。ローカルキャッシュが集中キャッシュと同じデータ構造を有する場合には、どちらのキャッシュにも同じキャッシュアクセスコードを使用することができる。
【００１５】
キャッシュサービスルーチンは、キャッシュを置き換える際どのデータを維持するかを判断するために、キャッシュ使用に関し収集する統計にヒューリスティックを適用する。実施形態には、ユーザインターフェースを用意してヒューリスティックを変更することを可能にし、またはキャッシュの動作を監視することを可能にするものがある。
【００１６】
添付の特許請求の範囲は、詳細に本発明の特徴を記載しているが、本発明は、添付の図面と共に挙げられた以下の詳細な説明から、その目的および利点と共に最もよく理解することができる。
【発明を実施するための最良の形態】
【００１７】
図面においては同じ参照符号が同じ要素を指しており、本発明は、適切なコンピューティング環境内で実施されるものとして示されている。以下の説明は、本発明の諸実施形態に基づいており、代替実施形態に関して本明細書で明示的に述べられていないとしても、それにより本発明を限定的に捉えてはならない。
【００１８】
以下の説明では、別段の表示がない限り、本発明について、１つまたは複数のコンピューティングデバイスによって実行される動作、および操作を記号で表したものを参照して述べる。そのような動作および操作は、「コンピュータによって実行される」と記述されることがあり、コンピューティングデバイスの処理装置によって、構造化された形態でデータを表す電気信号が操作されることを含むことを理解されたい。この操作は、データを
変換し、またはコンピューティングデバイスのメモリシステム内のロケーションでデータを維持し、当業者にはよく理解できる方法で、デバイスの動作を再構成し、または他の方法で変更する。データが維持されるデータ構造は、データの形式によって定義された特定の特性を有するメモリの物理ロケーションである。しかし、本発明について前述の文脈で述べると、当業者なら、以下で述べる様々な動作および操作をハードウェアで実施することもできることを理解できるので、限定はされないものとする。
【００１９】
本発明は、アトミックに更新される集中キャッシュメモリを提供する。この集中キャッシュは、キャッシュを提供するコンピューティングデバイス上で動作するアプリケーションによって排他的に使用することができ、あるいは図１ａのように、いくつかのコンピューティングデバイス上のアプリケーションによって集中キャッシュを使用することができる。図１ａでは、コンピューティングデバイスＡ１０２、Ｂ １０４、およびラップトップ１０６の３つが、キャッシュ型データ共有環境１００内にある。集中キャッシュ（図示せず）は、コンピューティングデバイスＡ１０２上に常駐し、ＬＡＮ１０８を介してアプリケーションにとってアクセス可能である。キャッシュ要求を送るためには、標準的な通信プロトコルが存在しており、共有環境１００内のコンピューティングデバイスの間で応答する。
【００２０】
図では、インターネット１１０への接続は、遠隔コンピューティングデバイスであってもキャッシュ型データ共有環境１００に加わることができることを示す。実際には、そのような遠隔デバイスが集中キャッシュにアクセスするために必要とされる通信時間の増大は、データへの高速アクセスを提供するというキャッシュの目的に反する。したがって、ほとんどの集中キャッシュの使用状況においては、接近して配置されたコンピューティングデバイスが１つだけ、または多くとも数個必要とされるだけである。
【００２１】
図１ｂは、図１ａのキャッシュ型データ共有環境１００の例示的な一実施形態の構造の詳細を表す。アプリケーションＡ１１２は、コンピューティングデバイスＡ １０２上で動作している。アプリケーションＡ １１２を構成するルーチンの中に、ローカル／集中キャッシュ探索ルーチン１１４がある。アプリケーションＡ１１２がキャッシュ内に常駐している可能性のあるデータを必要とするとき、ルーチン１１４は、現行のローカルキャッシュ１１６内で、または現行の集中キャッシュ１１８内でデータを探索する。ローカルキャッシュ１１６は、アプリケーションＡ１１２の一部であり、その管理下にある。集中キャッシュ１１８はアプリケーションＡ１１２の一部でないが、アプリケーションＡ １１２にとって、また他のアプリケーションにとってアクセス可能である。
【００２２】
集中キャッシュ探索ルーチン１１４が、ローカルキャッシュ１１６内または集中キャッシュ１１８内で要求されたデータを見つけた場合には、そのデータをアプリケーションＡ１１２に返す。見つからなかった場合には、データは他で探索され、または作成される。データが見つかった、または作成された後に、キャッシュ探索ルーチン１１４は、ローカルキャッシュ更新ルーチン１２０を呼び出して、そのデータをローカルキャッシュ１１６に追加することを要求する。データを集中キャッシュ１１８に追加するための要求が集中キャッシュサービスルーチン１２４にも送られる。
【００２３】
データが追加されると、ローカルキャッシュと集中キャッシュは共に増大する。これらが増大し過ぎると新しいキャッシュが作成され、以前キャッシュされたデータの一部が配置される。どのデータを新しいキャッシュに持ち越すか選択するために、いくつかの方法が適用される。たとえば、最も最近使用されたデータが選択され、または最も使用頻度の高いデータが選択される。図１ｂは、現行のローカルキャッシュ１１６と共に以前のローカルキャッシュ１２２を示す。
【００２４】
新しい集中キャッシュを作成するとき、集中キャッシュを使用するアプリケーションの混乱を防止するように注意する必要がある。新しい集中キャッシュ１１８の準備ができると、より古い集中キャッシュ１２６は「廃止」とマークされ、より新しいキャッシュが使用可能であることがアプリケーションに警告される。しかし、これらのアプリケーションは直ちに新しいキャッシュ１１８に切り替える必要はなく、しばらくの間、引き続きより古い集中キャッシュ１２６にアクセスすることを選択することができる。それ以上アプリケーションがより古い集中キャッシュ１２６にアクセスしなくなった後で、そのキャッシュは削除される。
【００２５】
アプリケーションＢ１２８は、キャッシュ型データ共有環境１００内において別のコンピューティングデバイス上で動作する。このアプリケーションは、ローカルキャッシュを備えていないように示されているが、集中キャッシュ探索ルーチン１３０を有する。このルーチンは、より古い集中キャッシュ１２６に依然としてアクセスしており、このキャッシュが廃止とマークされていることにまだ気付いていない。キャッシュ探索ルーチン１３０は、データを集中キャッシュに追加することを要求することができるが、集中キャッシュサービスルーチン１２４は、そのデータを廃止されたキャッシュ１２６ではなく、現行の集中キャッシュ１１８に追加することになる。
【００２６】
図１ａのコンピューティングデバイス１０２、１０４、１０６は、いずれのアーキテクチャのものとすることもできる。図２は、本発明をサポートする例示的なコンピュータシステムを一般的に示すブロック図である。図２のコンピュータシステムは、好適な環境の一例にすぎず、本発明の使用または機能の範囲についてどのような制限をも示唆しないものとする。コンピューティングデバイス１０２は、図２に示されている構成要素のいずれか１つまたは組合せに関して、どのような依存性も要件も有すると解釈すべきでない。本発明は、多数の他の汎用または専用コンピューティングシステム環境または構成と共に動作可能である。本発明と共に使用するのに適している周知のコンピューティングシステム、環境、および構成の例には、これに限られないが、パーソナルコンピュータ、サーバ、ハンドヘルドデバイスまたはラップトップデバイス、タブレットデバイス、マルチプロセッサシステム、マイクロプロセッサをベースとするシステム、セットトップボックス、プログラム可能な家電、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境などが含まれる。コンピューティングデバイス１０２は、その最も基本的な構成では、一般に少なくとも１つの処理装置２００およびメモリ２０２を含む。メモリ２０２は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭまたはフラッシュメモリなど）、またはその２つの何らかの組合せとすることができる。この最も基本的な構成が、図２に破線２０４によって示されている。コンピューティングデバイス１０２は、追加の特徴および機能を有することができる。たとえば、コンピューティングデバイス１０２は、それだけには限らないが、磁気ディスクおよび光ディスクならびにテープを含む追加記憶装置（取外し式および固定式）を含むことができる。そのような追加記憶装置は、図２に取り外し可能な記憶装置２０６および固定式記憶装置２０８によって示されている。コンピュータ記憶媒体には、コンピュータ読取可能命令、データ構造、プログラムモジュール、または他のデータなど、情報を記憶するための任意の方法または技術で実施される揮発性と不揮発性、取外し式と固定式の媒体が共に含まれる。メモリ２０２、取り外し可能な記憶装置２０６、および固定式記憶装置２０８は、すべてコンピュータ記憶媒体の例である。コンピュータ記憶媒体には、それだけには限らないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、他の光記憶、磁気カセット、磁気テープ、磁気ディスク記憶、または他の磁気記憶デバイス、および、所望の情報を記憶するために使用することができ、デバイス１０２によってアクセスすることができる他の任意の媒体が含まれる。任意のそのようなコンピュータ記憶媒体をデバイス１０２の一部とすることができる。デバイス１０２はまた、他のデバイスと通信することがで
きる通信チャネル２１０を含むことができる。通信チャネル２１０は、通信媒体の例である。通信媒体は、一般に、コンピュータ読取可能命令、データ構造、プログラムモジュール、または他のデータを、搬送波または他の移送機構など変調データ信号に統合し、任意の情報送達媒体を含む。「変調データ信号」という用語は、情報を信号に符号化するようにその特性の１つまたは複数が設定された、または変化した信号を意味する。限定ではなく例を挙げると、通信媒体は、有線ネットワークまたは直接配線接続など有線媒体と、音響、ＲＦ、赤外線および他の無線媒体など無線媒体とを含む。本明細書では、「コンピュータ読取可能な媒体」という用語は、記憶媒体と通信媒体を共に含む。コンピューティングデバイス１０２はまた、キーボード、マウス、ペン、音声入力デバイス、タブレット、タッチ入力デバイスなど、入力デバイス２１２を有することができる。ディスプレイ（タッチ入力デバイスと一体化することができる）、スピーカ、プリンタなど、出力デバイス２１４をも含むことができる。これらのデバイスはすべて、当技術分野で周知であり、ここで詳細に論じる必要はない。
【００２７】
図３ａから３ｄは、図１ｂのローカル／集中キャッシュ探索ルーチン１１４のための例示的な方法を示すフローチャートである。このフローチャートは多くの任意の選択肢を含むが、これらはキャッシュ探索ルーチン１１４のあらゆる実施形態に含まれなければならないわけではない。
【００２８】
図３ａのステップ３００においてフローチャートが始まる前に、アプリケーションＡ１１２が注目するデータにアクセスするように、キャッシュ探索ルーチン１１４は要求される。ステップ３００において、キャッシュ探索ルーチン１１４は、集中キャッシュがアクセス可能かどうか検査することから開始される。どの集中キャッシュもアクセス可能でない場合、キャッシュ探索ルーチン１１４は図３ｄのステップ３２６に進み、ローカルキャッシュ内で注目されるデータを捜す。その環境によっては、他の実施形態におけるキャッシュ探索ルーチン１１４は、集中キャッシュにアクセスする前にローカルキャッシュにアクセスしようとする。
【００２９】
ステップ３０２において、集中キャッシュがアクセス可能である場合、キャッシュ探索ルーチン１１４は検査を行って、その集中キャッシュが「廃止」とマークされているかどうか確かめる。このステップと以下のステップ３０４は任意に選択することができることに留意されたい。すなわち、キャッシュ探索ルーチン１１４は、廃止されたキャッシュを継続して使用することができる。しかし、流れを維持するために、キャッシュ探索ルーチン１１４は、アクセス中の集中キャッシュの状態を定期的に検査し、ひとたび古いキャッシュが廃止されていることに気付いた場合、その古いキャッシュを解放すべきである。
【００３０】
集中キャッシュが廃止とマークされる前に、集中キャッシュサービスルーチン１２４は、新しい集中キャッシュを作成する（図５ａおよび５ｂのステップ５１２から５１８参照）。したがって、ステップ３０４において、キャッシュ探索ルーチン１１４は、廃止された集中キャッシュのヘッダ内の、現行の集中キャッシュを指す参照に従う。要求の到達と実際の処理との間に著しい遅延があるため、遅延中に複数のキャッシュが廃止とマークされる可能性がある。その場合には、廃止されていないキャッシュに達するまで、ステップ３０２および３０４が繰り返される。
【００３１】
ステップ３０６において、キャッシュ探索ルーチン１１４は、集中キャッシュにアクセスし、注目されるデータを含むかどうか確かめる。ステップ３０６の詳細は、集中キャッシュがどのような構造になっているかによって多様に変わる可能性がある。図３ａから３ｃに示されているステップ３０６は、一定の考えうる実施形態を示しているものであり、図４ａおよび４ｂに示されている例示のキャッシュデータ構造と共に参照する。
【００３２】
図４ａは、ステップ３０６に示されている手順と共に使用可能な集中キャッシュ４００の構造を示す。固定サイズヘッダ４０２は廃止フラグを含み、このフラグが設定されている場合、より新しい集中キャッシュ４００が参照される。次に、参照の固定サイズテーブル４０４が含まれる。参照のテーブル４０４内の各エントリは、データ要素記憶領域４０６内のデータ要素への参照（図４ｂの４１０参照）か、そのエントリがデータ要素を指していないことを示す特別な値（たとえば、ＮＵＬＬ）のどちらかである。実施形態によっては、これらの参照は、整数オフセットとして与えられるものがある。これにより、集中キャッシュ４００をファイルとしてディスク上に記憶することが可能となり、ホストコンピューティングデバイス１０２を再起動させた後に回復させることが可能になる。
【００３３】
実際のキャッシュデータは、個々のデータ要素４１０として記憶される。これらのデータ要素に割り振られた空間４０６は、必要に応じて、予約空間（ｕｎｃｏｍｍｉｔｅｄｓｐａｃｅ）４０８の領域内に拡大する。予約空間４０８が使い果たされると、キャッシュサービスルーチン１２４が新しい集中キャッシュ４００を作成する。
【００３４】
ステップ３０６に示されている特定の実施形態は、ステップ３０８において、注目されるデータをハッシュすることによって開始される。次いで、このハッシュは、ステップ３１０において、集中キャッシュ４００内にある参照のテーブル４０４へのインデックスとして使用される。参照のテーブル４０４内で選択されたエントリが、図３ｂのステップ３１２において検査される。そのエントリがどのデータ要素も指していない場合には、注目されるデータは集中キャッシュ４００にはない（ステップ３１４）。次いで、キャッシュ探索ルーチン１１４は、図３ｄのステップ３２６に進み、集中キャッシュ４００以外の所で注目されるデータを捜す。
【００３５】
一方、参照のテーブル４０４内の選択されたエントリがデータ要素を指している場合には、そのデータ要素が注目されるデータを含んでいることも含んでいないこともある。その理由は、異なるデータ値が同じ値にハッシュされ、参照のテーブル４０４内で同じエントリを選択する可能性があるからである。
【００３６】
図４ｂの例示的なデータ要素構造４１０を参照されたい。各データ要素４１０は、同じハッシュ値を有する別のデータ要素４１０か、そのエントリが別のデータ要素４１０を指していないことを示す特別な値（たとえば、ＮＵＬＬ）のどちらかを指す参照４１２から始まる。参照のテーブル４０４内のエントリの場合と同様に、この参照は、整数オフセットとして与えられる。参照４１２の次に、このデータ要素４１０内に含まれているデータを一意に識別するデータ識別子フィールド４１４が続く。最後に、データ自体を含むフィールド４１６が続く。このフィールド４１６のサイズと構造は、記憶されたデータの性質に特有である。実施形態によっては、データ要素４１０が、そのサイズ自身、またはそれと同等である要素特有（ｅｌｅｍｅｎｔ−ｓｐｅｃｉｆｉｃ）データフィールド４１６の終端の位置を示すフィールドを含むものがある。他の実施形態においては、集中キャッシュ４００のヘッダ４０２内のフィールドが、割り当てられたデータ記憶領域４０６の終端を示している。いかなる場合でも、これらの長さフィールドは、（以下で論じる図５ｄのステップ５３４において）別のデータ要素４１０をキャッシュ４００に追加することができる場所を示すために使用される。
【００３７】
データ要素４１０の例示的な構造を念頭に置いて、図３ｂのステップ３１６に戻る。ステップ３１６においてデータ要素４１０のハッシュは、注目されるデータのハッシュに一致する。データ要素４１０が注目されるデータを含むかどうか確かめるために、データ要素４１０のデータ識別子フィールド４１４が注目されるデータと比較される。それらが一致した場合には探索を完了する。注目されるデータは、ステップ３１８において取り出され、アプリケーションＡ１１２に渡される。これにより、図３ａから３ｄのキャッシュ探
索ルーチン１１４が問題なく終了する。
【００３８】
一方、ステップ３１６の比較により、このデータ要素４１０が注目されるデータを含まないことが明らかになった場合、キャッシュ探索ルーチン１１４は、図３ｃのステップ３２０に進む。ステップ３２０において、データ要素４１０の参照フィールド４１２が調べられる。このフィールドが別のデータ要素４１０を指していないとき、集中キャッシュ４００は、注目されるデータを含まない（ステップ３２２）。キャッシュ探索ルーチン１１４は、図３ｄのステップ３２６に進み、別の場所で注目されるデータを探索する。
【００３９】
ステップ３２０において、データ要素４１０の参照フィールド４１２が他のデータ要素を指している場合、その他のデータ要素が調べられ、注目されるデータを含むかどうか確かめられる。ステップ３２４は、このプロセスを表す。すなわち、注目されるデータが見つかり、取り出されるまで（ステップ３１８）、または注目されるデータを見つけることなしにチェインの最後に達するまで（ステップ３２２）、ステップ３１６から３２２を繰り返すことによってデータ要素４１０のチェインに従う。
【００４０】
集中キャッシュ４００が注目されるデータを含まない場合、図３ｄのステップ３２６において、キャッシュ探索ルーチン１１４は、アプリケーションＡ１１２に対してローカルなキャッシュ１１６を探索することができる。実施形態によっては、ステップ３２６の細部がステップ３０６の細部そのままのものがある。これによりキャッシュ探索コードを再使用することが可能となる。いずれの場合でも、ローカルキャッシュ１１６が注目されるデータを含んでいるときは、それらのデータがステップ３３２において取り出される。注目されるデータを含んでおらず、注目されるデータを探索すべき他のキャッシュがないと想定されるときは、ステップ３２８においてそれらのデータが生成される。次いで、ステップ３３０において、これらのデータをローカルキャッシュ１１６に追加して、今後のアクセスを容易にすることができる。作成されたデータを集中キャッシュ４００に追加するための要求は、ステップ３３４において行うことができる。
【００４１】
図３ａから３ｄは、集中キャッシュ４００から、または別の場所からキャッシュ探索ルーチン１１４がどのように注目されるデータを取り出すかを示す。図５ａから５ｄは、キャッシュ４００の別の態様、すなわち、キャッシュ４００にデータを追加し、現在のキャッシュが満杯になったとき新しい集中キャッシュを作成するキャッシュサービスルーチン１２４を示す。キャッシュサービスルーチン１２４は、キャッシュ４００にデータを追加する唯一のルーチンであることから、複数の書込み側アプリケーションの間で衝突を防止するため、キャッシュ４００をロックする必要はない。また、キャッシュサービスルーチン１２４は、書込み要求のすべてが流通するため、キャッシュ使用について統計を収集し、キャッシュ４００にデータを追加するための特定の要求の重要度について「グローバル」な視野を形成することができので、新しいキャッシュが作成されたとき、どのデータを持ち越すべきか判断することができる。ここで、図５ａから５ｄの手順は例示的なものにすぎない。なお、この手順は、図４ａおよび４ｂにおいて導入された集中キャッシュデータ構造を使用する。
【００４２】
キャッシュサービスルーチン１２４は、集中キャッシュ４００にデータを追加するための要求を受け取ると、図５ａのステップ５００において始まる。この要求は、キャッシュ探索ルーチン１１４が図３ｄのステップ３３４を実行したとき発せられている場合がある。
【００４３】
実施形態によっては、ステップ５０２において、キャッシュサービスルーチン１２４が受け取った要求に関する、また他の要求に関する統計を収集するものがある。ステップ５０４において、キャッシュサービスルーチン１２４は、この要求に従うかどうか判断する
。実施形態によっては、単に要求のすべてに従うものがある一方、収集済み統計を参考にして、注目されるデータが集中キャッシュ４００に追加される「価値がある」かどうか判断するものもある。実施形態によっては、注目されるデータのサイズが、キャッシュ４００内の予約空間４０８と比較して大きすぎる場合は要求を拒否する。注目されるデータは、（おそらくは、図３ａから３ｃのステップ３０６を実行することによって）キャッシュ４００内のデータと比較され、注目されるデータがすでに存在する場合は要求が拒否される。これが発生する可能性があるのは、ステップ５００において受け取られた要求が待ち行列に入ったことにより、要求が到達したときと、（図５ｂから５ｄのステップ５２２において）注目されるデータがキャッシュ４００に追加されたときとの間に著しい遅延が存在する可能性があるからである。遅延の間、要求しているキャッシュ探索ルーチン１１４、または別のルーチンは、キャッシュ４００に再アクセスし、注目されるデータを見つけられず、要求を提出する可能性がある。後者の要求が処理されるときまでに、より早い要求に応じて、キャッシュ４００に注目されるデータがすでに追加されている。いずれの場合も、ステップ５０６において、要求に従わないと判断された場合には、キャッシュサービスルーチン１２４は、ステップ５０８において他の要求を待つ。
【００４４】
要求に従うと判断された場合、ステップ５１０において、キャッシュサービスルーチン１２４は、新たな集中キャッシュ４００が必要とされているかどうか判断する。たとえば、注目されるデータがキャッシュ４００内の予約空間４０８内に合わないときには、図５ａおよび５ｂのステップ５１２から５２０において新たなキャッシュ４００が作成される。新しいキャッシュ４００はまた、参照のテーブル４０４が満杯になりつつあるとき、またはキャッシュ４００が、暫時使用されていない非常に多数のデータ要素４１０を有するときに作成することができる。新しいキャッシュ４００が必要とされないときには、キャッシュサービスルーチン１２４は、図５ｂのステップ５２２において注目されるデータを追加する処理に直接移行する。
【００４５】
新しい集中キャッシュ４００が必要とされる場合には、ステップ５１２において空のシェルが作成される。キャッシュは、データへの高速アクセスが可能なように一般にＲＡＭ内に記憶される。いくつかのオペレーティングシステムにおいては、ＲＡＭのある領域をファイルシステムによってマッピングすることが可能である。これは、後述するある利点を有する。
【００４６】
図５ｂのステップ５１４において、キャッシュサービスルーチン１２４は、既存のキャッシュから選択されたデータ要素４１０を新しく作成されたキャッシュ４００に配置する。データ要素４１０を選択するいくつかの方法が可能である。キャッシュサービスルーチン１２４は、データ要素４１０がどのように使用されているかに関して統計を収集することができる。次いで、最近使用された要素、または最もしばしば使用された要素が選択される。実施形態によっては、乱数の要素を選択時に使用するものがある。いずれの場合も、データ要素４１０は、選択されれば、新しい集中キャッシュ４００のデータ記憶領域４０６内にコピーされ、新しいキャッシュ４００の参照のテーブル４０４に配置される。ステップ５１４は、実行するのに一定の時間を要する可能性があるが、ステップ中、古いキャッシュは常にアクセス可能であることに留意されたい。
【００４７】
古いキャッシュのヘッダ４０２内に、ステップ５１６において新しいキャッシュ４００への参照が書き込まれ、ステップ５１８においてフラグが設定され、古いキャッシュを「廃止」とマークする。これで、新しいキャッシュ４００を使用する準備ができる。キャッシュ探索ルーチン１１４は、古いキャッシュ内で廃止フラグを見たとき、新しいキャッシュ４００への参照に従う（図３ａのステップ３０２および３０４参照）。
【００４８】
キャッシュサービスルーチン１２４は、ステップ５２０において、廃止されたキャッシ
ュを参照するアプリケーションがなくなったとき直ちに、すなわち、アプリケーションのすべてが、廃止されたキャッシュへのその参照を解放したとき直ちに、廃止されたキャッシュをオペレーティングシステムが自動的に削除することを要求する。
【００４９】
新しいキャッシュ４００が生成されたばかりか否かにかかわらず、ステップ５２２において注目されるデータが現行のキャッシュ４００に追加される。図５ｂから５ｄのステップ５２２は、図３ａから３ｃのステップ３０６内において探索されたデータ構造自体を生成するので、ステップ３０６の有する複雑さをそのまま有する。図中に示されるステップ３０６および５２２についての詳細は、一定の実施形態についてのみの例示ではあるが、ほとんどの実施形態において、これらのステップは互いに生き写し（ｍｉｒｒｏｒ）になる。
【００５０】
特定の実施形態においてステップ５２２は、（図３ａのステップ３０８を写した）ステップ５２４において注目されるデータをハッシュすることで開始される。ステップ５２６において、（ステップ３１０を写しているので）ハッシュが使用され、キャッシュ４００の参照のテーブル４０４内のエントリを選択する。ステップ５２８において、選択されたエントリがまだデータ要素４１０を指していない場合には、図５ｄのステップ５３４において、キャッシュ４００のデータ記憶領域４０６内でデータ要素４１０が作成される。次いで、この新しいデータ要素に注目されるデータが配置される。この配置ステップが実行されている間、キャッシュ４００にアクセスするキャッシュ探索ルーチン１１４は、新しいデータを見ておらず、したがって、これらと同じデータを追加するために追加要求をする可能性があることに留意されたい。配置ステップ５３４が完了し、新しいデータ要素４１０の準備ができた後に、キャッシュサービスルーチン１２４は、新しいデータ要素４１０を指すように、参照のテーブル４０４内の選択されたポインタをアトミックに更新する（ステップ５３６）。この参照の書込みは、コンピュータ命令１つ分を占有するだけであり、その結果、本来的に割込み不能である。したがって、この動作中その内部一貫性を保持するためにキャッシュ４００をロックする必要がない。
【００５１】
ステップ５２８に戻ると、参照のテーブル４０４内の選択されたエントリがすでにデータ要素４１０を指している場合には、ステップ５３０において、データ要素４１０の参照フィールド４１２が調べられる。ステップ５３２において、終了するまで参照のチェインに従う（これは、図３ｂおよび３ｃのステップ３１６から３２４における同じ参照チェインの下方への探索をそのまま写している）。チェインの終端が見つかった後に、キャッシュサービスルーチンは、上述のステップ５３４に進み、ここで新しいデータ要素４１０が割り振られ、注目されるデータが格納（ｆｉｌｌｅｄ）される。この状況で、ステップ５３６により、チェインの終端にあった既存のデータ要素４１０内に、新しいデータ要素４１０への参照が自動的に追加され、したがって、参照のチェインがさらに「リンク」１つ分だけ延びる。
【００５２】
以上の通り、新しいデータ要素４１０を既存の集中キャッシュ４００に追加し、あるいは新しい集中キャッシュ４００を生成するとしても、キャッシュサービスルーチン１２４は２段階で処理が進められる。まず、データが準備され、時間のかかる作業のすべてが行われる。この段階の間、集中キャッシュ４００に対する変更は、キャッシュ探索ルーチン１１４から見えない。したがって、その内部一貫性を保存するために集中キャッシュ４００をロックする必要がない。また、キャッシュサービスルーチン１２４が高い優先順位で動作する必要がない。第２段階では、単一のポインタが新しいデータ要素４１０または新しい集中キャッシュ４００に書き込まれる。単一のポインタを書き込むのは本来割込み不能であるので、やはり、この段階の間、集中キャッシュ４００をロックする必要はない。第２段階が完了すると、新しいデータまたは新しいキャッシュが、キャッシュ探索ルーチン１１４にとってアクセス可能になる。
【００５３】
図６は、キャッシュサービスルーチン１２４の動作を監視し構成するための方法を示すフローチャートである。ステップ６００において、集中キャッシュの最大サイズおよび現行のサイズが表示される。図５ｂのステップ５１４において新しい集中キャッシュに配置するとき、既存の集中キャッシュからデータ要素を選択するために使用されたヒューリスティックが、ステップ６０２において示される。ステップ５０４において、集中キャッシュにデータを追加するための要求に従うかどうか判断するために使用されたヒューリスティックが、ステップ６０４において示される。このヒューリスティックを単に「常に従う」とすることができたことを想起されたい。ステップ６０６において、キャッシュ使用について収集された様々な統計が示される。管理者は、これらの統計を解析し、集中キャッシュが最適動作していないと判断することができる。管理者は、ステップ６０８において、何らかの変更を入力し、これがステップ６１０において反映される。図６は、単にユーザインターフェースの特色を提供するものであって、本技術分野で周知の多種多様なキャッシュ解析ツールを十分に示すものではないことが理解される。
【００５４】
本発明の原理を適用することができる多数の可能な実施形態に鑑みて、本明細書で図面に関連して述べられている実施形態は、例示的なものにすぎず、本発明の範囲を制限すると考えるべきでないことを理解されたい。たとえば、例示されている実施形態、特にデータ構造とそれらに基づく手順は、本発明の精神から逸脱することなしに構成および詳細を修正することができることを当業者なら理解するであろう。本発明について、ソフトウェアモジュールまたは構成要素によって述べられているが、それらをハードウェア構成要素によって等価に置き換えることができることを当業者なら理解するであろう。したがって、本明細書に述べられている発明は、そのような実施形態すべてを、特許請求の範囲とその均等物の範囲内に入れることができると企図している。
【図面の簡単な説明】
【００５５】
【図１ａ】ローカルエリアネットワーク（ＬＡＮ）を介してキャッシュデータを共有する３つのコンピューティングデバイスを示すブロック図である。
【図１ｂ】図１ａのコンピューティングデバイスの間で共有された集中キャッシュメモリを示すブロック図である。
【図２】本発明をサポートする例示的なコンピュータシステムを一般的に示す概略図である。
【図３ａ】本発明による、集中キャッシュからデータにアクセスしようと試みるアプリケーションプログラムのための例示的な方法を示すフローチャートである。
【図３ｂ】本発明による、集中キャッシュからデータにアクセスしようと試みるアプリケーションプログラムのための例示的な方法を示すフローチャートである。
【図３ｃ】本発明による、集中キャッシュからデータにアクセスしようと試みるアプリケーションプログラムのための例示的な方法を示すフローチャートである。
【図３ｄ】本発明による、集中キャッシュからデータにアクセスしようと試みるアプリケーションプログラムのための例示的な方法を示すフローチャートである。
【図４ａ】本発明による、集中キャッシュ用の例示的なデータ構造を示す概略図である。
【図４ｂ】集中キャッシュ内のデータ要素用の例示的なデータ構造を示す概略図である。
【図５ａ】本発明による、集中キャッシュを維持するルーチンのための例示的な方法のフローチャートである。
【図５ｂ】本発明による、集中キャッシュを維持するルーチンのための例示的な方法のフローチャートである。
【図５ｃ】本発明による、集中キャッシュを維持するルーチンのための例示的な方法のフローチャートである。
【図５ｄ】本発明による、集中キャッシュを維持するルーチンのための例示的な方法のフローチャートである。
【図６】集中キャッシュサービスルーチンを構成するための例示的な方法のフローチャートである。
【符号の説明】
【００５６】
１００キャッシュ型データ共有環境
１０２コンピューティングデバイスＡ
１０４コンピューティングデバイスＢ
１０６ラップトップ
１０８ＬＡＮ
１１０インターネット
１１２アプリケーションＡ
１１４ローカル／集中キャッシュ探索ルーチン
１１６現行のローカルキャッシュ
１１８現行の集中キャッシュ
１２０ローカルキャッシュ更新ルーチン
１２２以前のローカルキャッシュ
１２４集中キャッシュサービスルーチン
１２６より古い集中キャッシュ
１２８アプリケーションＢ
１３０集中キャッシュ探索ルーチン
２００処理装置
２０２メモリ
２０６取り外し可能な記憶装置
２０８固定式記憶装置
２１０通信チャネル
２１２入力デバイス
２１４出力デバイス
４００集中キャッシュ
４０２固定サイズヘッダ
４０４参照の固定サイズテーブル
４０６データ要素記憶領域
４０８予約空間
４１０データ要素
４１２参照フィールド
４１４データ識別子フィールド
４１６データフィールド
【図１ａ】
2007184009.tif 000003
【図１ｂ】
2007184009.tif 000004
【図２】
2007184009.tif 000005
【図３ａ】
2007184009.tif 000006
【図３ｂ】
2007184009.tif 000007
【図３ｃ】
2007184009.tif 000008
【図３ｄ】
2007184009.tif 000009
【図４ａ】
2007184009.tif 000010
【図４ｂ】
2007184009.tif 000011
【図５ａ】
2007184009.tif 000012
【図５ｂ】
2007184009.tif 000013
【図５ｃ】
2007184009.tif 000014
【図５ｄ】
2007184009.tif 000015
【図６】
2007184009.tif 000016