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