(57)【特許請求の範囲】
【請求項１】
キャッシュに記憶されているオブジェクトを前記キャッシュから削除する方法を実行するコンピュータ実行可能命令が記録されているコンピュータ読取可能な記録媒体であって、前記方法は、
前記オブジェクトと関連付けられているポリシーであって前記オブジェクトのそれぞれに対して重みを決定するための少なくとも２つの要素を識別するポリシーを取得するステップであって、前記ポリシーは、それぞれが１つの待ち行列と対応する複数のポリシーの中から取得される、ステップと、
前記オブジェクトのそれぞれに対し、前記少なくとも２つの要素のそれぞれと関連付けられた値と前記オブジェクトの絶対的古さとを加算することによって計算される重みを決定するステップであって、オブジェクトの絶対的古さとは、ある基準となる時点から当該オブジェクトが最後にアクセスされた時点までに経過した時間の長さを意味する、ステップと、
前記ポリシーに対応する待ち行列にアクセスするステップと、
前記待ち行列の中のそれぞれのオブジェクトに対するランクを、前記重みに基づいて決定するステップと、
前記待ち行列において、削除すべきオブジェクトを当該オブジェクトのランクに基づいて選択するステップと、
前記キャッシュにおけるオブジェクトの位置を識別し、更に、複数の待ち行列のそれぞれにおけるオブジェクトと関連付けられたリンクを識別するメタデータであって、前記選択された削除すべきオブジェクトと関連付けられたリンクを識別するメタデータにアクセスするステップと、
前記メタデータによって識別されたリンクに基づいて、前記複数の待ち行列すべてから前記削除すべきオブジェクトを削除するステップと、
前記キャッシュから、前記複数の待ち行列すべてから削除されたオブジェクトに対応するオブジェクトを削除するステップと、
を更に含むことを特徴とするコンピュータ読取可能な記録媒体。
【請求項２】
請求項１記載のコンピュータ読取可能な記録媒体において、前記ポリシーはそれぞれの要素について調整を指定することを特徴とするコンピュータ読取可能な記録媒体。
【請求項３】
請求項１記載のコンピュータ読取可能な記録媒体において、前記ポリシーはいくつかのコンピュータに適用可能なグループポリシーであることを特徴とするコンピュータ読取可能な記録媒体。
【請求項４】
請求項１記載のコンピュータ読取可能な記録媒体において、前記ポリシーはＸＭＬ文書を介して定義されることを特徴とするコンピュータ読取可能な記録媒体。
【請求項５】
請求項１記載のコンピュータ読取可能な記録媒体において、前記ポリシーはユーザインターフェースを介して定義されることを特徴とするコンピュータ読取可能な記録媒体。
【請求項６】
請求項１記載のコンピュータ読取可能な記録媒体において、前記オブジェクトを選択するステップはリンクリスト内の複数のリンクから１つのリンクを識別するステップを含み、前記複数のリンクはそれぞれが前記キャッシュに格納されたオブジェクトに関連付けられており、前記識別されたリンクは最も低い重要性を有することを特徴とするコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はキャッシュに格納されたオブジェクトを管理するためのシステムおよび方法に関し、より詳細には、本発明はキャッシュ内に格納されたオブジェクトを管理および立ち退かせるためのシステムおよび方法を対象とする。
【背景技術】
【０００２】
分散ネットワーク（たとえばインターネット）は、非常に一般的なものである。分散ネットワークには、１つまたは複数のクライアントコンピュータと１つまたは複数のサーバコンピュータがある。サーバコンピュータは、クライアントコンピュータにとって関心のあるコンテンツを格納する。コンテンツには、ハイパーテキストマークアップ言語（ＨＴＭＬ／ＨｙｐｅｒＴｅｘｔＭａｒｋｕｐ Ｌａｎｇｕａｇｅ）ページ、イメージファイル、ワードプロセッシングファイル、および他のオブジェクトが含まれる。このコンテンツを取得するために、クライアントコンピュータは（たとえばリンクを介して）サーバコンピュータに要求を送信する。この要求は、サーバコンピュータ上にある所望のオブジェクトを指定するものである。サーバコンピュータが応答し、オブジェクトがクライアントコンピュータにダウンロードされる。
【０００３】
サーバコンピュータとクライアントコンピュータとの間のより高速なやりとり（interaction）を容易にするために、オブジェクトがダウンロードされた後でそのオブジェクトをキャッシュする、クライアント側キャッシング（ＣＳＣ：client-side caching）技法が開発されてきた。たとえば、クライアント側キャッシングが利用できる場合、クライアントコンピュータは最初にそのキャッシュをチェックして、指定されたオブジェクトのコピーが、以前のダウンロードからすでにキャッシュに格納されているかどうかを判別する。オブジェクトがすでにキャッシュに格納されている場合、クライアントコンピュータはオブジェクトを再度ダウンロードするのではなく、キャッシュ済みのオブジェクトを使用することができる。したがってクライアントコンピュータは、コンテンツの一部をダウンロードする必要がないため、時間の節約になる。その結果、サーバコンピュータとクライアントコンピュータの間のやりとりがより高速になる。
【０００４】
クライアント側キャッシングにより、サーバコンピュータとクライアントコンピュータとの間の通信の高速化に加えて、オブジェクトへのオフラインアクセスも可能になる。たとえば、クライアント側キャッシングが永続的キャッシュを実行している場合、クライアントコンピュータがサーバコンピュータに接続されていないときであっても、ユーザは、キャッシュされたオブジェクトをクライアントコンピュータ上で用いることができる。永続的キャッシュに格納可能なオブジェクトの数は、キャッシュサイズに依存する。典型的には、キャッシュはディスクスペースのうちの一定の割合であるか、または固定サイズとすることができる。キャッシュがいっぱいになると、新たなオブジェクトにキャッシュスペースを提供するために、キャッシュ内に格納されたオブジェクトの一部が削除（つまり、立ち退か）される。
【０００５】
現在は、オブジェクトは、最後にアクセスされた時刻に基づいて削除がなされる。つまり、最後にアクセスがなされたのが現時点から見て最も近いオブジェクトはキャッシュ内に保持され、最後にアクセスされてから最も時間が経過しているオブジェクトが削除される。十分なキャッシュスペースが確保できるまで、オブジェクトの削除は続けられる。一部の実施例では、ユーザは、１つのオブジェクトが常にキャッシュ内に残るように要求することが可能であり、これは通常「ピニング（pinning）」と称される。これらの「ピニングされた」オブジェクトは、キャッシュから削除されない。場合によっては、「ピニングされた」オブジェクトは、キャッシュとは別に、ユーザスペースなどに格納することができる。
【０００６】
本発明以前に、オブジェクトを管理するため、およびオブジェクトをキャッシュから立ち退かせるための、より高度な方法を、当業者が見つけることはなかった。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、キャッシュ内に格納されたオブジェクトを管理および立ち退かせるためのシステムおよび方法を対象とするものである。
【課題を解決するための手段】
【０００８】
本発明は、キャッシュの中にあるオブジェクトの削除に関し、各オブジェクトについて算出された重みに基づいてどのオブジェクトを削除するのかを決定する機構を提供する。この重みは、ファイルサイズ、ファイルタイプ、プライマリ・ユーザ、最終アクセス時刻などを含む少なくとも２つの要素と、それぞれの要素の相対的な重要性とによって、決定される。各オブジェクトの重みは、自律的に決定されるか、及び／又は、トリガイベントの時点で決定される。要素と要素の相対的な重要性とは、１又は複数のコンピュータに適用可能なポリシーから取得できる。
【０００９】
要素がポリシー内に指定されている場合、クライアントコンピュータは適切な立ち退き挙動について個々に構成する必要がない。大企業では、このポリシー主導の立ち退き機構は管理オーバヘッドをそれほど必要としないため、結果として大幅な節約になる。
【発明を実施するための最良の形態】
【００１０】
本発明は、キャッシュに格納されたオブジェクトを管理するためのシステムおよび方法を対象とするものである。本発明は、どのオブジェクトを立ち退かせるかを決定するための機構を提供する。この機構は、キャッシュ内に格納された各オブジェクトについて算出される重みに基づいて、この決定を行う。重みは、ファイルサイズ、ファイルタイプ、プライマリ・ユーザ、最終アクセス時間などの、多くの要素の影響を受ける。各オブジェクトに関する重みは、自律的に決定する、かつ／または、オブジェクトの更新などのトリガイベント時に決定することができる。さらにこの要素は、ポリシーから取得することができる。
【００１１】
以下の説明は２つの部分に分けられる。説明の第１の部分は、本発明が動作可能な例示的コンピューティング環境を示すものである。説明の第２の部分は、本発明の一実施例を示すものである。
【００１２】
例示的コンピューティング環境
図１は、本発明の例示的実施で使用可能なコンピューティングデバイスの一例を示す図である。図１を参照すると、非常に基本的な構成において、コンピューティングデバイス１００は通常、少なくとも１つの処理ユニット１０２およびシステムメモリ１０４を含む。コンピューティングデバイス１００の正確な構成およびタイプに応じて、システムメモリ１０４は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭ、フラッシュメモリなど）、またはこの２つの何らかの組合せとすることができる。システムメモリ１０４は、通常、オペレーティングシステム１０５、１つまたは複数のプログラムモジュール１０６を含み、プログラムデータ１０７を含むこともある。プログラムモジュール１０６の例には、ブラウザアプリケーション、財務管理アプリケーション、ワードプロセッサなどが含まれる。この基本的な構成は、図１では、破線１０８内の構成要素によって示されている。
【００１３】
コンピューティングデバイス１００は、追加の特徴または機能を有することができる。たとえば、コンピューティングデバイス１００は、たとえば磁気ディスク、光ディスク、またはテープなどの、追加のデータストレージデバイス（取外し可能および／または取外し不能）を含むこともできる。こうした追加のストレージは、図１では、取外し可能ストレージ１０９および取外し不能ストレージ１１０によって示されている。コンピュータストレージ媒体は、コンピュータ読取り可能命令、データ構造、プログラムモジュール、または他のデータなどの、情報を記憶するための任意の方法または技術で実施された、揮発性および不揮発性、取外し可能および取外し不能の媒体を含むことができる。システムメモリ１０４、取外し可能ストレージ１０９および取外し不能ストレージ１１０は、すべてコンピュータストレージ媒体の例である。コンピュータストレージ媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、または他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、または他の磁気ストレージデバイス、あるいは、所望の情報を格納するために使用可能であり、コンピューティングデバイス１００によってアクセス可能な、任意の他の媒体を含むが、これらに限定されるものではない。任意のこうしたコンピュータストレージ媒体は、デバイス１００の一部とすることができる。コンピューティングデバイス１００は、キーボード、マウス、ペン、音声入力デバイス、タッチ入力デバイスなどの、入力デバイス１１２も含むことができる。ディスプレイ、スピーカ、プリンタなどの、出力デバイス１１４も含むことができる。これらのデバイスは当分野ではよく知られているため、本明細書で詳細に論じる必要はない。
【００１４】
コンピューティングデバイス１００は、デバイス１００がネットワークを介するなどして他のコンピューティングデバイス１１８と通信できるようにする、通信接続１１６を含むこともできる。通信接続１１６は、通信媒体の一例である。通信媒体は通常、搬送波または他の移送機構などの変調データ信号内に、コンピュータ読取り可能命令、データ構造、プログラムモジュール、または他のデータを具現化することができ、任意の情報送達媒体を含む。「変調データ信号」という用語は、信号に情報を符号化するように、その特徴のうちの１つまたは複数を設定または変更した信号を意味する。例を挙げると、通信媒体には、有線ネットワークまたは直接有線接続などの有線媒体、ならびに、音波、ＲＦ、赤外線、および他の無線媒体などの無線媒体が含まれるが、これらに限定されるものではない。本明細書で使用されるコンピュータ可読媒体という用語には、ストレージ媒体および通信媒体の両方が含まれる。
【００１５】
例示的実施
図２は、本発明の実施が具体化可能な、分散ネットワーキング環境２００の概略を示す機能ブロック図である。図２に示されるように、サーバコンピュータ（以下サーバ２０２と呼ぶ）およびクライアントコンピュータ２２０などの、２つまたはそれ以上のコンピュータが、ネットワーク２０５を介して接続される。サーバ２０２およびクライアントコンピュータ２２０は、図１に関して上記で説明したようなコンピューティングデバイスであってよい。コンピュータは会社環境内で接続することが可能であり、ネットワーク２０５はローカルエリアネットワークまたはワイドエリアネットワークとすることができる。同様に、コンピュータは、インターネットなどのワイドエリアネットワークを介して任意に接続することができる。
【００１６】
サーバ２０２は、ネットワーク２０５に接続された他のコンピューティングデバイスがリソースを使用できるように構成された、コンピューティングデバイスである。サーバ２０２は、ハイパーテキストマークアップ言語（ＨＴＭＬ）文書などのインターネット関連リソースを処理するための、Ｗｅｂ処理ソフトウェアを含むことができる。サーバ２０２は、これらのリソース（すなわちコンテンツ２１０）を格納するためのストレージを含む。サーバ２０２は、他のコンピューティングデバイス（たとえばクライアントコンピュータ２２０）がネットワーク２０５を介してコンテンツ２１０を使用できるようにする。
【００１７】
クライアントコンピュータ２２０は、ローカルに実行されているアプリケーションを実行するように、ならびにネットワーク２０５を介して他のコンピュータに接続するように構成された、コンピューティングデバイスである。図に示されるように、クライアントコンピュータ２２０はキャッシュ２２８を含む。キャッシュは、ＲＡＭ、ハードディスク、または他のコンピュータ可読媒体に、物理的に配置することができる。キャッシュ２２８は一時キャッシュ２３０を含むものであり、ユーザスペース２３２を含むことができる。ユーザスペースは一時キャッシュの一部であるか、または別の場所にあってもよい。一時キャッシュ２３０は、サーバ２０２からダウンロードされた永続的なコンテンツ用である。ユーザスペース２３２も、サーバ２０２からダウンロードされた永続的なコンテンツ用である。しかし、一時キャッシュ２３０とは対照的に、通常、ユーザスペース２３２内のコンテンツが立ち退きプロセスを受けることはない。むしろ、ユーザスペース２３２内に格納されたコンテンツは「ピニング」され、これは使用可能なままであって、立ち退かされることがないことを意味する。したがってユーザスペース２３２は、追加のコンテンツを収容するようになることができる。
【００１８】
クライアントコンピュータ２２０は、ネットワーク２０５を介して他のコンピュータとやりとりするための他のアプリケーションを含む。こうしたアプリケーションの１つがインターネットブラウジングソフトウェアなどのホストソフトウェア２２２（以下、ブラウザ２２２と呼ぶ）である。ブラウザ２２２は、キャッシュマネージャ２２４と通信する。キャッシュマネージャ２２４は、ブラウザ２２２がサーバコンピュータ２０２からダウンロードするコンテンツをキャッシュに入れるように構成されている。手短に言えば、キャッシュマネージャ２２４は、立ち退きポリシー２２６にアクセスする。立ち退きポリシーは、ローカルポリシー、グループポリシー、またはその他であってよい。立ち退きポリシー２２６は、拡張可能マークアップ言語（ＸＭＬ）、ユーザインターフェース（ＵＩ）、テキストなど、いくつかのフォーマットが可能である。立ち退きポリシー２２６を作成する方法の一例については、図３との関係で後述する。立ち退きポリシー２２６は、オブジェクトに重みを割り当てる方法を決定するための要素を特定する。立ち退きポリシー２２６に含まれる要素の数は、任意である。要素の例としては、最終アクセス時刻、ファイルタイプ、アクセスしたユーザの数、ソースサーバの宛先、特定ディレクトリ、ファイルサイズ、権利者名、権利者がプライマリ・ユーザであるかどうか、ダウンロードのコスト、更新間隔、ユーザによって設定された優先順位などが含まれる。ただし、これらに限定されることはない。
【００１９】
手短に言えば、クライアントコンピュータ２２０のユーザは、任意の従来型の態様でサーバ２０２に接続することができる。サーバ２０２は、コンテンツ２１０としてサーバコンピュータ２０２上にあるファイル（すなわちオブジェクト）を使用可能にするウェブページまたは何らかの他のリソースを提示する。サーバ２０２は、ユーザによるリンクなどの選択に応答して、下位にある（underlying）オブジェクトにナビゲートする。ある実施例では、キャッシュマネージャは、オブジェクトが既にキャッシュ２２８に格納されているかどうか、または、オブジェクトをサーバ２０２からクライアントコンピュータ２２０にダウンロードする必要があるかどうか、を判別する役割を担っている。オブジェクトをクライアントコンピュータにダウンロードすることが必要な場合には、キャッシュマネージャ２２４は、オブジェクトを永続させるのに十分なスペースがキャッシュ２２８にあるかどうかを判別する役割を担う。十分なスペースがない場合、キャッシュマネージャ２２４は本発明に従って立ち退きプロセスを実行する。十分なスペースがある場合、キャッシュマネージャ２２４は一時キャッシュ２３０内にオブジェクトをキャッシュし、本発明に従ってオブジェクトに重みを適用する。図６および７は、それぞれ、重みを適用するため、およびオブジェクトを立ち退かせるための、例示的なフロー図を示すものである。
【００２０】
図３は、本発明の一実施例に従った、立ち退きポリシーを指定するためのキャッシュマネージャソフトウェアによって提示可能なスクリーン画面の一例を示す図である。当業者であれば、テキストエディタ、ＸＭＬなどの、立ち退きポリシーの作成に、様々な実施が使用可能であることを理解されよう。図３に示された実施例には、基準ボックス３０２を含むディスプレイ３００が含まれる。基準ボックス３０２は、オブジェクトに重みを割り当てる際に考慮の対象とされる、１つまたは複数の要素（たとえば要素３１０〜３１６）を識別する。要素３１０〜３１６はそれぞれ、関連付けられた調整ボックス（たとえばサイズ調整３２０）を有する。調整ボックスは、基準がどのように重みに影響を与えるかを指定するものである。たとえば、図３では、サイズ要素３１０が選択されている。したがってサイズ調整ボックス３２０が示されている。サイズ調整ボックスには、ファイルサイズのリスト（たとえば０から１０Ｋ）および関連付けられた調整が表示される。たとえば、評価されているオブジェクトが１５Ｋバイトの場合、重みは調整されない。しかし、オブジェクトが１０Ｍバイトを超える場合、重みは調整される。要素および調整に基づいてオブジェクトの重みを算出するための一実施形態は図７に示されており、それに関連して説明される。図示されていないが、他の要素（要素３１２〜３１６）はそれぞれ関連付けられた調整ボックスを有し、ユーザまたはシステム管理者はこれを使用して基準に関する調整を設定できることを、当業者であれば理解されよう。
【００２１】
図３は、ポリシーを指定するための一実施形態を示す図であるが、当業者であれば、本発明を逸脱することなく他の技法も使用可能であることを理解されよう。たとえば、ＸＭＬ文書を使用してポリシーを記述することができる。いったん定義されたポリシーは、グループ用であるか、またはローカルコンピュータ用とすることができる。ポリシーがグループ用である場合、システム管理者は、指定されたポリシーをグループ内のそれぞれのコンピュータに使用することができる。立ち退き機構を定義するためにグループポリシーを使用すると、管理を均一かつ容易にすることができる。
【００２２】
図４は、重みに基づいてキャッシュされたオブジェクトを管理するための一実施形態を示す図である。この実施形態では、重み付けされた優先順位待ち行列４００が、２重リンクリストとして実施される。各リンク（すなわち４２０〜４２６）は、順方向ポインタ（たとえばＦ．ＰＴＲ４３０）および逆方向ポインタ（たとえばＢ．ＰＴＲ４３２）を含む。順方向ポインタ４３０は次のリンクを参照し、逆方向ポインタ４３２は前のリンクを参照する。さらに、各リンク４２０〜４２６はキャッシュポインタ（たとえばＣＡＣＨＥＰＴＲ４３４）を含む。キャッシュポインタ４３４はキャッシュに格納されたオブジェクトを参照する。ツリー４０２は、キャッシュに格納されたオブジェクトの構造をグラフィカルに示すものである。各オブジェクトはオブジェクト名４０８（たとえばＦｉｌｅ１−１）によって識別され、さらにパス４０６（たとえば、「＼＼Ｓｅｒｖｅｒ１＼Ｓｈａｒｅ１」）によって識別される。次にキャッシュポインタ４３４は、パス４０６およびオブジェクト名４０８によるなどして、オブジェクトを一意に識別する。
【００２３】
本発明による重み付けされた優先順位待ち行列４００内のリンク４２０〜４２６は、それぞれが、重み（たとえば、重み４３６）をさらに含む。重みは、ポリシーにおいて特定された様々な要素に基づいて割り当てられる。次に優先順位待ち行列４００内のリンク４２０〜４２６は、重みに基づいてランクが付けられる。たとえば、リンク４２０〜４２６は、最高の重みから最低の重みまで、ランクを付けることができる。以下で説明するように、重みに基づいてランクを付けることにより、キャッシュマネージャは、優先順位の低いオブジェクトを必要に応じてキャッシュから効率的に削除できる。
【００２４】
図５には、別の実施例が図解されている。この実施例では、キャッシュの中にあるオブジェクトが重みに基づいて管理される。この実施例では、たとえば優先順位待ち行列５００〜５０６のような重みが付けられた優先順位（＝優先度付き）待ち行列が複数個存在する。優先度付き待ち行列５００〜５０６は、それぞれが、キャッシュに記憶されているオブジェクトを当該キャッシュから削除するための異なる理由を表している。たとえば、ある１つの待ち行列ではスペースを解放するという観点からオブジェクトの優先度が決められているのに対し、別の待ち行列ではセンシティブな情報を一掃（purge）するという観点からオブジェクトの優先度が決められている、といった具合である。それぞれの待ち行列には、異なるポリシーが関連付けられていて、オブジェクトに対して異なる重みを割り当てる。このようにして、それぞれの待ち行列は、関連付けられている削除ポリシーにおいて指定される要素に基づいて、リンクにランクを付けている。
【００２５】
更に別の例では、それぞれの待ち行列におけるそれぞれのリンクが、メタデータ４５０を参照する。メタデータ４５０は、キャッシュ内の各オブジェクトに関するメタデータオブジェクト（たとえば、メタデータオブジェクト４５２）を含む。ある実施例では、各キャッシュエントリについて、１つのメタデータオブジェクトが存在する。メタデータオブジェクト４５２は、キャッシュの中の実際のオブジェクトを参照するキャッシュポインタ（ｃａｃｈｅＰｔｒ）と、待ち行列５００〜５０６のそれぞれに対する待ち行列ポインタとを含む。以下で詳細に説明するように、メタデータオブジェクト４５２によると、どの待ち行列からでもオブジェクトを見つけることができ、見つけたオブジェクトをすべての待ち行列から簡単に除去することができる。たとえば、図解されているように、各待ち行列は、メタデータオブジェクト４５４を指すリンクを有する。したがって、待ち行列５０４が削除プロセスを実行している場合、そのプロセスは削除すべきメタデータオブジェクト４５４を識別することができる。すると、このメタデータオブジェクト４５４を用いて、他の待ち行列におけるランク／位置とは関係なく、他の待ち行列において、除去する必要のあるリンクを容易に識別することができる。
【００２６】
図６は、本発明の一実施形態に従ってキャッシュ内のオブジェクトを管理するプロセス６００を図解する論理フローである。プロセス６００は、オブジェクトがアクセスされたとき、何らかのユーザ選択の際にトリガされたとき、あるいは何らかの所定のイベントでトリガされたときなど、その都度自律的に実行することができる。さらに、プロセス６００は、ポリシーが変更されたときに実行されることがある。プロセス６００はブロック６０１で開始され、特定の待ち行列に対して、重み付けプロセスが何らかの態様で起動される。処理はブロック６０２で続行される。
【００２７】
ブロック６０２では、特定待ち行列に関連付けられた立ち退きポリシーが取得される。立ち退きポリシーは、ローカルポリシーまたはグループポリシーとすることができる。立ち退きポリシーに関するフォーマットは、ＸＭＬ文書、テキストファイル、バイナリファイルなどのいくつかの形式のうちの１つを取ることが可能である。一般に、立ち退きポリシーは、オブジェクトに重みを割り当てるときに考慮の対象とすべき要素を指定するものである。プロセスはブロック６０４で続行される。
【００２８】
ブロック６０４では、ポリシー内の基準のうちの１つが取得される。図３に示すように、各ポリシーは、いくつかの要素に基づいてオブジェクトの重みを算出することができる。さらに、各基準はオブジェクトの調整を指定することになる。処理はブロック６０６で続行される。
【００２９】
ブロック６０６では、基準の値が決定される。一実施形態では、基準の調整を適用することによって値が決定される。再度図３を参照すると、たとえばファイルが１５ＭＢの場合、サイズ基準の調整は１年である。プロセスは意思決定ブロック６０８で続行される。
【００３０】
意思決定ブロック６０８では、ポリシーが他の基準を含むかどうかが決定される。他の基準がある場合、処理はブロック６０４にループバックして、前述のように新しい基準について続行する。ポリシー内のそれぞれの基準について値が決定されると、処理はブロック６１０に進む。
【００３１】
ブロック６１０では、オブジェクトに関して重みが計算される。計算される重みは、基準に対して決定されたそれぞれの値に基づく。ある実施例では、オブジェクトの絶対的古さ（たとえば、１９７０年１月１日から経過した時間の長さ（単位は秒））とそれぞれの値とを加算することによって重みが計算される。したがって、オブジェクトが時刻Ｔにおいてアクセスされたと想定すると、重みは、時刻Ｔからの経過時間と、サイズの調整値と、権利者の調整値と、それ以外の調整値との合計に等しい。したがって、きょうアクセスがなされたかなり大規模なファイルが、１ヶ月前にアクセスがなされたずっと小さなファイルと同じ重みを有することもある。プロセスはブロック６１２で続行される。
【００３２】
ブロック６１２では、算出された重みを使って待ち行列が更新される。他の実施形態では、メタデータを更新することも可能である。たとえば、オブジェクトが新しいオブジェクトの場合、待ち行列内に新しいリンクを作成し、新しいメタデータオブジェクトを作成することができる。処理は意思決定ブロック６１４で続行される。
【００３３】
意思決定ブロック６１４では、更新する必要のある他の待ち行列があるかどうかが決定される。各待ち行列はそれ自体の最適なキャッシュ立ち退き目的に関してオブジェクトを分類するため、各待ち行列はそれ自体の重みを算出し、それをオブジェクトに割り当てる。したがって、一般に、複数の待ち行列があるとき各待ち行列が更新される。しかし、一定の環境では、１つの待ち行列のみを更新することができる。たとえば、ポリシーが変更され、１つの待ち行列のみに影響を与えた場合、その待ち行列内のオブジェクトのみが更新される。したがって、意思決定ブロック６１４では、他の待ち行列がないと処理は終了する。そうでない場合、処理はブロック６１６で続行される。
【００３４】
ブロック６１６では、処理用の他の待ち行列が識別される。次に処理はブロック６０２にループバックして、上記のように続行される。このオブジェクトに関するメタデータオブジェクトがすでに存在するため、ブロック６１２では、メタデータオブジェクト内の待ち行列ポインタが、現在処理されている待ち行列内のリンクを参照するように更新される。
【００３５】
重み付けプロセス６００が完了すると、更新が必要な各待ち行列は、オブジェクトに関する新しい重みで更新されていることになる。当業者であれば、ポリシーが変更されると、キャッシュ内の各オブジェクトについてブロック６０４〜６１２内の処理が実行されることを理解されよう。これでキャッシュマネージャは、図７に関連して以下で説明するように任意の待ち行列に基づいて、どのオブジェクトを立ち退かせるかを容易に決定することができる。
【００３６】
図７は、本発明の一実施形態に従って、割り当てられた重みに基づいてキャッシュからオブジェクトを立ち退かせるためのプロセスを示す論理フロー図である。プロセス７００はブロック７０１で開始され、キャッシュマネージャは、何らかのオブジェクトがキャッシュから立ち退く必要があることを決定する。プロセスはブロック７０２で続行される。
【００３７】
ブロック７０２では、オブジェクトが立ち退く必要のある理由に基づいてポリシーが取得される。前述のように、スペース考慮事項、センシティブな情報、および再度アクセスされる可能性に基づいてオブジェクトに重み付けするポリシーがあってよい。処理はブロック７０３で続行される。
【００３８】
ブロック７０３では、キャッシュマネージャは、ポリシーに割り当てられた優先順位待ち行列にアクセスする。通常、追加のオブジェクトに使用可能なスペースを作るなどの特定の目的で、プロセス７００に入る。したがって、キャッシュマネージャは、どの待ち行列がこの目的に基づいてオブジェクトを立ち退かせる責務を負っているのか（たとえばポリシー）を認識し、その待ち行列にアクセスする。処理はブロック７０４で続行される。
【００３９】
ブロック７０４では、キャッシュマネージャは、対応する待ち行列の中での位置（つまり「ランキング」）に基づいて、待ち行列の中にあるオブジェクトを選択する。たとえば、重要性によってランク付けされた２重にリンクされたリストを使用して対応する待ち行列が実施される一実施形態では、キャッシュマネージャは、重要性の最も低いオブジェクトを最初に選択する。処理はブロック７０６で続行される。
【００４０】
ブロック７０６では、選択されたオブジェクトが、すべての待ち行列から除去される。オブジェクトがある１つの待ち行列から削除される場合には、キャッシュに格納されているオブジェクトに関して他のすべての待ち行列を最新の状態に維持するため、他の待ち行列においても当該オブジェクトを削除しなければならない。そうしなければ、他の待ち行列には、存在しないオブジェクトへの参照を含むことになってしまう。メタデータを実装している実施例では、すべての待ち行列から当該オブジェクトを削除するのは、比較的簡単な作業である。当該オブジェクトと関連するメタデータオブジェクトの中のそれぞれの待ち行列ポインタを用いて、関連付けられた待ち行列の中のオブジェクトが参照される。その後、待ち行列から当該リンクが除去される。処理はブロック７０８で続行される。
【００４１】
ブロック７０８では、キャッシュ内のオブジェクトが除去される。これには、キャッシュからのオブジェクトの削除、オブジェクトが削除されたことを示すフラグの設定、などが含まれる場合がある。処理はブロック７１０で続行される。
【００４２】
意思決定ブロック７１０では、他のオブジェクトを立ち退かせる必要があるかどうかが決定される。たとえば、十分なスペースが利用できない場合、処理は他のオブジェクトを立ち退かせるために、ブロック７０４〜７０８をループバックする。同様に、センシティブな情報のしきい値上限が依然として存在する場合、処理は他のオブジェクトを立ち退かせるために、ブロック７０４〜７０８をループバックすることができる。立ち退かせる必要のあるオブジェクトがなくなると、処理は終了する。
【００４３】
したがって、前述のように、本発明は、キャッシュ内の他のオブジェクトと比較した相対的な重要性に基づいてオブジェクトの効率的な立ち退きを可能にする、オブジェクトを管理するための方法を提供するものである。これによりキャッシュマネージャは、ポリシーによって定義されたオブジェクトの重要性に対して、そのキャッシュを効率的に利用することができる。
【００４４】
上記の指定、例、およびデータは、本発明の構成を製造および使用するための完全な記述を提供するものである。本発明の多くの実施形態が本発明の要旨および範囲を逸脱することなく実行可能であるため、本発明は、添付の特許請求の範囲内にあるものである。
【図面の簡単な説明】
【００４５】
【図１】本発明の例示的実施で使用可能なコンピューティングデバイスの一例を示す図である。
【図２】本発明の実施が具体化可能な、分散ネットワーキング環境の概略を示す機能ブロック図である。
【図３】本発明の一実施に従った、立ち退きポリシーを指定するためのキャッシュマネージャソフトウェアによって提示可能なスクリーン画面の一例を示す図である。
【図４】重みに基づいてキャッシュ済みオブジェクトを管理するための一実施形態を示すグラフ図である。
【図５】重みに基づいてキャッシュ済みオブジェクトを管理するための他の実施形態を示すグラフ図である。
【図６】本発明の一実施形態に従ってキャッシュ内のオブジェクトを管理するためのプロセスを示す論理フロー図である。
【図７】本発明の一実施形態に従ってキャッシュからオブジェクトを立ち退かせるためのプロセスを示す論理フロー図である。
【符号の説明】
【００４６】
１００ コンピューティングデバイス
１０２ 処理ユニット
１０４ システムメモリ
１０５ オペレーティングシステム
１０６ プログラムモジュール
１０７ プログラムデータ
１０９ 取外し可能ストレージ
１１０ 取外し不能ストレージ
１１２ 入力デバイス
１１４ 出力デバイス
１１６ 通信接続
１１８ 他のコンピューティングデバイス
２０２ ネットワーキング環境
２０２ サーバ
２０５ ネットワーク
２１０ コンテンツ
２２０ クライアントコンピュータ
２２２ Ｗｅｂホスト
２２４ キャッシュマネージャ
２２６ ポリシー
２２８ キャッシュ
２３０ 一時キャッシュ
２３２ ユーザスペース
３０２ 基準
３１０ サイズ
３１２ アクセス元
３１４ ファイルタイプ
３１６ 感度
３２０ 重み調整
４００ 重み付けされた優先順位待ち行列
４０２ ツリー
４０６ パス
４０８ オブジェクト名
４２０，４２２，４２４，４２６ リンク
４３０ 順方向ポインタ
４３２ 逆方向ポインタ
４３４ キャッシュポインタ
４３６ 重み
４５０ メタデータ
４５２ メタデータオブジェクト
４５４ 待ち行列１ポインタ
５００，５０２，５０４，５０６ 優先順位待ち行列
【図１】
0004263672.tif 000002
【図２】
0004263672.tif 000003
【図３】
0004263672.tif 000004
【図４】
0004263672.tif 000005
【図５】
0004263672.tif 000006
【図６】
0004263672.tif 000007
【図７】
0004263672.tif 000008