(57)【特許請求の範囲】
【請求項１】
ファイルを保存し提供するサーバーとファイルを利用する端末を結ぶネットワーク上に配置され、前記端末からリクエストされたファイルがファイル格納手段にキャッシュされていれば、そのファイルをリクエスト元へ送出し、キャッシュされてなければファイルをサーバーから獲得し、リクエスト元へ送出すると同時にファイル格納手段にキャッシュする、ネットワークキャッシュ装置において、
前記ファイル格納手段にファイルをキャッシュする際に所定の確率に基づき前記ファイルにマークする手段と、
各ファイルごとに優先度を決める優先度決定手段と、
各ファイルごとに、前記優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶するファイル管理手段と、
前記端末からリクエストされたファイルが前記ファイル格納手段にない場合、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するためのスペースがあれば、前記サーバーから獲得したファイルを前記ファイル格納手段に格納し、前記ファイル格納手段に前記サーバーから獲得したファイルを格納するためのスペースがない場合は、前記ファイル管理手段に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、それでも必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイル集合の中から最終参照時刻が古い順にファイルを削除した上で、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するキャッシュ制御手段と
を具備することを特徴とするネットワークキャッシュ装置。
【請求項２】
サーバに保存されているファイルをネットワークを介して利用する端末に具備され、前記端末からリクエストされたファイルがファイル格納手段にキャッシュされていれば、そのファイルをリクエスト元へ送出し、キャッシュされてなければファイルをサーバーから獲得し、リクエスト元へ送出すると同時にファイル格納手段にキャッシュする、ネットワークキャッシュ装置において、
前記ファイル格納手段にファイルをキャッシュする際に所定の確率に基づき前記ファイルにマークする手段と、
各ファイルごとに優先度を決める優先度決定手段と、
各ファイルごとに、前記優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶するファイル管理手段と、
前記端末からリクエストされたファイルが前記ファイル格納手段にない場合、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するためのスペースがあれば、前記サーバーから獲得したファイルを前記ファイル格納手段に格納し、前記ファイル格納手段に前記サーバーから獲得したファイルを格納するためのスペースがない場合は、前記ファイル管理手段に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、それでも必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイル集合の中から最終参照時刻が古い順にファイルを削除した上で、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するキャッシュ制御手段と
を具備することを特徴とするネットワークキャッシュ装置。
【請求項３】
前記ファイル管理手段に記憶されるファイルの優先度がファイルのサイズの逆数であることを特徴とする請求項１または２に記載のネットワークキャッシュ装置。
【請求項４】
ファイルを保存し提供するサーバーとファイルを利用する端末を結ぶネットワーク上に配置され、前記端末からリクエストされたファイルがファイル格納手段にキャッシュされていれば、そのファイルをリクエスト元へ送出し、キャッシュされてなければファイルをサーバーから獲得し、リクエスト元へ送出するのと同時にファイル格納手段にキャッシュする、ネットワークキャッシュ制御方法において、
前記ファイル格納手段にファイルをキャッシュする際に所定の確率に基づき前記ファイルにマークする工程と、
各ファイルごとに優先度を決める優先度決定工程と、
各ファイルごとに、前記優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶するファイル管理工程と、
前記端末からリクエストされたファイルが前記ファイル格納手段にない場合、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するためのスペースがあれば、前記サーバーから獲得したファイルを前記ファイル格納手段に格納し、前記ファイル格納手段に前記サーバーから獲得したファイルを格納するためのスペースがない場合は、前記ファイル管理手段に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、さらに必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイル集合の中から最終参照時刻が古い順にファイルを削除し、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するキャッシュ制御工程と
を具備することを特徴とするネットワークキャッシュ制御方法。
【請求項５】
サーバに保存されているファイルをネットワークを介して利用する端末に具備され、前記端末からリクエストされたファイルがファイル格納手段にキャッシュされていれば、そのファイルをリクエスト元へ送出し、キャッシュされてなければファイルをサーバーから獲得し、リクエスト元へ送出すると同時にファイル格納手段にキャッシュする、ネットワークキャッシュ制御方法において、
前記ファイル格納手段にファイルをキャッシュする際に所定の確率に基づき前記ファイルにマークする工程と、
各ファイルごとに優先度を決める優先度決定工程と、
各ファイルごとに、前記優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶するファイル管理工程と、
前記端末からリクエストされたファイルが前記ファイル格納手段にない場合、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するためのスペースがあれば、前記サーバーから獲得したファイルを前記ファイル格納手段に格納し、前記ファイル格納手段に前記サーバーから獲得したファイルを格納するためのスペースがない場合は、前記ファイル管理手段に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、さらに必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイル集合の中から最終参照時刻が古い順にファイルを削除し、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するキャッシュ制御工程と
を具備することを特徴とするネットワークキャッシュ制御方法。
【請求項６】
前記ファイル管理手段に記憶されるファイルの優先度がファイルのサイズの逆数であることを特徴とする請求項４または５に記載のネットワークキャッシュ制御方法。
【請求項７】
コンピュータに、
ファイルを保存し提供するサーバーとファイルを利用する端末を結ぶネットワーク上に配置され、前記端末からリクエストされたファイルがファイル格納手段にキャッシュされていれば、そのファイルをリクエスト元へ送出し、キャッシュされてなければファイルをサーバーから獲得し、リクエスト元へ送出すると同時にファイル格納手段にキャッシュする手順を実行させるためのプログラムを記録したコンピュータに読み取り可能な記録媒体であって、
前記ファイル格納手段にファイルをキャッシュする際に所定の確率に基づき前記ファイルにマークするマーク手順と、
各ファイルごとに優先度を決める優先度決定手順と、
各ファイルごとに、前記優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶するファイル管理手順と、
前記端末からリクエストされたファイルが前記ファイル格納手段にない場合、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するためのスペースがあれば、前記サーバーから獲得したファイルを前記ファイル格納手段に格納し、前記ファイル格納手段に前記サーバーから獲得したファイルを格納するためのスペースがない場合は、前記ファイル管理手段に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、さらに必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイル集合の中から最終参照時刻が古い順にファイルを削除し、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するキャッシュ制御手順と
をコンピュータに実行させるためのプログラムを記録したコンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ファイルを保管し提供するサーバーとファイルを利用する端末をつなぐネットワーク上に配置されるファイルキャッシュまたは前記端末に具備されるネットワークキャッシュ装置およびネットワークキャッシュ制御方法および記録媒体に関する。
【０００２】
【従来の技術】
従来、ネットワーク内に配置するキャッシュまたはネットワークに接続されたクライアント端末に具備されたキャッシュにおいて、新しくサーバーから送信されてきたファイルをキャッシュする際に、キャッシュ内に十分なスペースがない場合、最後に参照された日付の古いファイルから削除する方法（下記に記載）がとられており、以前にキャッシュされたファイル中のどのファイルから削除するかを判断する手段が重要であった。
【０００３】
この際、リクエスト（参照）されたファイルが、ファイル格納部にキャッシュされていないため、ネットワークを通じてサーバから前記ファイルを収得する場合をフォルトと呼ぶことにすると、フォルトするデータ量（フォルトしたファイルのサイズの和）を極力少なくするためには、参照頻度の高いファイルをキャッシュに残し、参照頻度の低いファイルを削除するようなキャッシュ制御方法が望ましい。
【０００４】
また、前記キャッシュの制御方法として、最も参照時刻の古いページから順に削除するＬＲＵ（Least Recently Used）と呼ばれる方法が一般的である。これは、もともと仮想記憶システムにおけるページング方法として考案されたものである。一般に、プログラムは、最近アクセスしたページにアクセスしやすいという局所参照性を持っている。前記ＬＲＵ方式は、この局所参照性を利用することにより、参照頻度の低いファイルを削除している。また、端末で起動される、ＷＷＷ（World Wide Web）のブラウザなどのアプリケーションから出される、ファイルへのリクエストもこの局所参照性をもっているため、前記ＬＲＵ方式はネットワークにおけるキャッシングでも有効であると考えられている。
【０００５】
さらに、参照時刻だけでなくサイズに着目した場合、ＷＷＷ（World  Wide Web）のトラフィックの場合のように、小さいファイルの方が頻繁にアクセスされる傾向がある場合がある。このような場合、前記ＬＲＵ方式よりも、大きいファイルから優先して削除する方式（ここではＳｉｚｅ方式とする）が、ＬＲＵ方式よりもさらに有効である（参考文献：S. Williams and M. Abrams and C. R. Strandridge and G. Abdulla and E. A. Fox, "Removal Policies in Network Caches for World-Wide-Web Documents", Proceedings of SIGCOMM, ACM, 1996）。これは、前記ＬＲＵ方式が、一度キャッシュに入ったファイルは、それがめったに参照されないものであっても、参照時刻がキャッシュの中で最も古くなるまで、削除されないのに対し、前記Ｓｉｚｅ方式は、キャッシュされているファイルの中でもっとも大きければ、即座に削除されるためである。また、画像ファイルやテキストファイルなどファイルの属性に参照頻度が予測できる場合は、参照頻度が高い属性を持つファイルに対して高い優先度を与え、前記Ｓｉｚｅ方式と同様な効果が得られる。
【０００６】
【発明が解決しようとする課題】
しかし、上記のようにリクエストされるファイルのサイズや属性の分布を仮定したキャッシュ制御方式では、参照頻度の履歴を考慮にいれていないため、何かの影響でその仮定が崩れた場合や、仮定があてはまらなかった場合に、極端にフォルトするデータ量が多くなる場合がある。例えば、Ｓｉｚｅ方式を採用していた場合、キャッシュされているどのファイルよりも大きいファイルへのリクエストが連続した場合、キャッシュに入ったばかりのファイルがすぐ削除されるため、フォルトしたデータ量が極端に大きくなるという問題があった。
【０００７】
また、特開平７−１８２２２０号公報は、キャッシュされるファイルを、優先度の低い順にファイルを削除する第１のグループと、ＬＲＵ方式でファイルを削除する第２のグループにわける方法をとっている。そして、新しいオブジェクトをキャッシュするために、すでにキャッシュされているファイルを削除する際には、二つのグループから一つを適宜選択して、削除する。しかし、グループの選択の仕方によっては、フォルト量が極端に多くなるという問題がある。
【０００８】
また、特開平１１−６５９２７号公報は、キャッシュ制御方式の異なる複数のストレージを持つ方法である。しかし、これは独立した複数のキャッシュをもっているため、あらかじめファイル毎に最適なキャッシュ制御方式を選択しなければならない、という問題がある。
【０００９】
また、特開平１１−２１９３１７号公報は、アクセスコストをパラメータとする評価関数で算出された値が大きいファイルから順に削除する方法である。また、この関数を、f(i,c)=c-1/(i+1)（ただし、ｉはアクセス順序、cはアクセスコスト）と与えることが示されている。この発明では、ファイルごとにアクセスコストが定義されていることを仮定しており、端末からのリクエストを処理する過程で生ずるアクセスコストの総和を少なくすることを目的としている。フォルトするデータ量をアクセスコストと考えると、cをファイルサイズと考えればよい。これにより、参照時刻が古くなるほど、f(i,c)の値が小さくなるので、削除されやすくなるが、アクセスコストcの値の分布によっては、ＬＲＵ方式より極端にフォルト量が多くなることがある。
【００１０】
また、ＩＢＭの方式（C. Aggarwal, J. Wolf, P. Yu, "On Caching Policies for Web Objects", IBM Research Report RC20619）では、サイズ×（現在時刻−最終参照時刻）を各ファイルのコストと定義し、コストが大きいファイルから順に削除する。この方法を用いることにより、最終参照時刻が古くなれば削除されやすくなるので、最悪の場合でもＬＲＵ方式に比べて性能が際限なく悪くなることはない。しかし、サイズと（現在時刻−最終参照時刻）の積によってファイルのコストが表されるため、サイズの大きさや分布に、フォルト量が大きく依存するという問題点がある。
【００１１】
これに対し、特願２０００−１４５３９９号では、ネットワークキャッシュ装置は、端末から出されたリクエストの時系列を、リクエストされた相異なるファイル
のサイズの合計がファイル格納部の容量を越えない最長の部分列に分割するとともに、各部分列におけるキャッシュフォルト回数を、ファイルごとに記憶しておくフォルト数管理テーブルと、
ファイル格納部にキャッシュしたファイルごとに優先度を決める機能と、フォルト数管理テーブルに記憶されているファイルのフォルト数が所定の数に達したものにマークする機能を持ち、該キャッシュされたファイルごとに、該優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶する、ファイル管理テーブルと、
端末からリクエストされたファイルがファイル格納部にない場合、該サーバーから獲得したファイルを該ファイル格納部に格納するためのスペースがあれば、該サーバーから獲得したファイルを該ファイル格納部に格納し、該ファイル格納部に該サーバーから獲得したファイルを格納するためのスペースがない場合は、該端末からリクエストされたファイルを格納するスペースをつくるために、該ファイル管理テーブルに記憶された情報をもとに、優先度の低い順にファイルを選択し、マークされていないファイルであれば削除し、マークされているファイルであれば、それ以後は、該マークされているファイルも含めた残りのファイルの中から最終参照時刻が古い順に該ファイル格納部からファイルを削除した上で、該サーバーから獲得したファイルをファイル格納部に格納するキャッシュ制御部を有することにより実現している。
【００１２】
この方式では、フォルトするデータ量の最悪値を保証するために、リクエストされた各ファイルのフォルト数を記憶するテーブルを設ける必要がある。このため、必要な記憶容量が多く、前記テーブル管理するための操作が必要であるという問題があった。
【００１３】
本発明の目的は、あるアクセスパターンを仮定したときに特に有効なキャッシュ制御方式を、ＬＲＵ方式と組み合わせることにより、仮定したアクセスパターンに対しては、ＬＲＵ方式よりもさらにキャッシュのヒット率が高く、仮定したアクセスパターン以外に対しても、フォルトするデータ量の期待値の最悪値が保証されるキャッシュ制御方式を用い、かつ、少ない記憶量と少ない手順で実現するネットワークキャッシュ装置およびネットワークキャッシュ制御方法を提供することである。
【００１４】
【課題を解決するための手段】
上記目的を達成するために、この発明のネットワークキャッシュ装置およびネットワークキャッシュ制御方法および記録媒体は、ファイルを保存し提供するサーバーとファイルを利用する端末を結ぶネットワーク上に配置され、前記端末からリクエストされたファイルがファイル格納手段にキャッシュされていれば、そのファイルをリクエスト元へ送出し、キャッシュされてなければファイルをサーバーから獲得し、リクエスト元へ送出すると同時にファイル格納手段にキャッシュする、ネットワークキャッシュ装置において、前記ファイル格納手段にファイルをキャッシュする際に所定の確率に基づき前記ファイルにマークする手段と、各ファイルごとに優先度を決める優先度決定手段と、各ファイルごとに、前記優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶するファイル管理手段と、前記端末からリクエストされたファイルが前記ファイル格納手段にない場合、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するためのスペースがあれば、前記サーバーから獲得したファイルを前記ファイル格納手段に格納し、前記ファイル格納手段に前記サーバーから獲得したファイルを格納するためのスペースがない場合は、前記ファイル管理手段に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、それでも必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイル集合の中から最終参照時刻が古い順にファイルを削除した上で、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するキャッシュ制御手段とを具備することを特徴とする。
【００１５】
また、サーバに保存されているファイルをネットワークを介して利用する端末に具備され、前記端末からリクエストされたファイルがファイル格納手段にキャッシュされていれば、そのファイルをリクエスト元へ送出し、キャッシュされてなければファイルをサーバーから獲得し、リクエスト元へ送出すると同時にファイル格納手段にキャッシュする、ネットワークキャッシュ装置において、前記ファイル格納手段にファイルをキャッシュする際に所定の確率に基づき前記ファイルにマークする手段と、各ファイルごとに優先度を決める優先度決定手段と、各ファイルごとに、前記優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶するファイル管理手段と、前記端末からリクエストされたファイルが前記ファイル格納手段にない場合、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するためのスペースがあれば、前記サーバーから獲得したファイルを前記ファイル格納手段に格納し、前記ファイル格納手段に前記サーバーから獲得したファイルを格納するためのスペースがない場合は、前記ファイル管理手段に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、それでも必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイル集合の中から最終参照時刻が古い順にファイルを削除した上で、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するキャッシュ制御手段とを具備することを特徴とする。
【００１６】
また、前記ファイル管理手段に記憶されるファイルの優先度がファイルのサイズの逆数であることを特徴とするネットワークキャッシュ装置である。
【００１７】
また、ファイルを保存し提供するサーバーとファイルを利用する端末を結ぶネットワーク上に配置され、前記端末からリクエストされたファイルがファイル格納手段にキャッシュされていれば、そのファイルをリクエスト元へ送出し、キャッシュされてなければファイルをサーバーから獲得し、リクエスト元へ送出するのと同時にファイル格納手段にキャッシュする、ネットワークキャッシュ制御方法において、前記ファイル格納手段にファイルをキャッシュする際に所定の確率に基づき前記ファイルにマークする工程と、各ファイルごとに優先度を決める優先度決定工程と、各ファイルごとに、前記優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶するファイル管理工程と、前記端末からリクエストされたファイルが前記ファイル格納手段にない場合、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するためのスペースがあれば、前記サーバーから獲得したファイルを前記ファイル格納手段に格納し、前記ファイル格納手段に前記サーバーから獲得したファイルを格納するためのスペースがない場合は、前記ファイル管理手段に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、さらに必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイル集合の中から最終参照時刻が古い順にファイルを削除し、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するキャッシュ制御工程とを具備することを特徴とする。
【００１８】
また、サーバに保存されているファイルをネットワークを介して利用する端末に具備され、前記端末からリクエストされたファイルがファイル格納手段にキャッシュされていれば、そのファイルをリクエスト元へ送出し、キャッシュされてなければファイルをサーバーから獲得し、リクエスト元へ送出すると同時にファイル格納手段にキャッシュする、ネットワークキャッシュ制御方法において、前記ファイル格納手段にファイルをキャッシュする際に所定の確率に基づき前記ファイルにマークする工程と、各ファイルごとに優先度を決める優先度決定工程と、各ファイルごとに、前記優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶するファイル管理工程と、前記端末からリクエストされたファイルが前記ファイル格納手段にない場合、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するためのスペースがあれば、前記サーバーから獲得したファイルを前記ファイル格納手段に格納し、前記ファイル格納手段に前記サーバーから獲得したファイルを格納するためのスペースがない場合は、前記ファイル管理手段に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、さらに必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイル集合の中から最終参照時刻が古い順にファイルを削除し、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するキャッシュ制御工程とを具備する。
【００１９】
また、前記ファイル管理手段に記憶されるファイルの優先度がファイルのサイズの逆数であることを特徴とするネットワークキャッシュ制御方法である。
【００２０】
また、コンピュータに、ファイルを保存し提供するサーバーとファイルを利用する端末を結ぶネットワーク上に配置され、前記端末からリクエストされたファイルがファイル格納手段にキャッシュされていれば、そのファイルをリクエスト元へ送出し、キャッシュされてなければファイルをサーバーから獲得し、リクエスト元へ送出すると同時にファイル格納手段にキャッシュする手順を実行させるためのプログラムを記録したコンピュータに読み取り可能な記録媒体であって、前記ファイル格納手段にファイルをキャッシュする際に所定の確率に基づき前記ファイルにマークするマーク手順と、各ファイルごとに優先度を決める優先度決定手順と、各ファイルごとに、前記優先度と最終参照時刻に加え、マークされているかマークされていないかを区別する記号を記憶するファイル管理手順と、前記端末からリクエストされたファイルが前記ファイル格納手段にない場合、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するためのスペースがあれば、前記サーバーから獲得したファイルを前記ファイル格納手段に格納し、前記ファイル格納手段に前記サーバーから獲得したファイルを格納するためのスペースがない場合は、前記ファイル管理手段に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、さらに必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイル集合の中から最終参照時刻が古い順にファイルを削除し、前記サーバーから獲得したファイルを前記ファイル格納手段に格納するキャッシュ制御手順とをコンピュータに実行させるためのプログラムを記録したコンピュータに読み取り可能な記録媒体である。
【００２１】
【発明の実施の形態】
本発明の実施の形態を以下に図面を用いて説明する。
【００２２】
図１に示すように、ネットワークキャッシュ装置３と端末５とサーバー６は、ネットワーク７で互いに接続されている。前記ネットワークキャッシュ装置３は、ファイル格納手段４とファイル管理手段（以下、ファイル管理テーブル）１とキャッシュ制御手段２を具備している。前記ファイル管理テーブル１は、キャッシュされたファイルのファイル名、ファイルサイズ、優先度、最終参照時刻、マークの有無、とを１エントリとして記憶するファイル管理テーブルである。このファイル管理テーブルの実施形態を図５に示した。ファイル管理テーブルに記憶されるファイルのマークの有無は、例えば、そのファイルがファイル管理テーブルに挿入されるときに所定の確率に基づいて決定される。最終参照時刻は、参照される度に更新される。優先度は、予めサーバー等によって決められたものでもよいし、ファイルのサイズや属性をもとにファイル管理テーブルが決めたものであっても良い。ファイル管理テーブルは、ファイル格納手段に実際に格納されているファイルのリストである。したがって、ファイル管理テーブルへのエントリの挿入・削除は、ファイル格納手段へのファイルの挿入・削除と連係して行なわれる。
【００２３】
次に、前記キャッシュ制御手段２について説明する。このキャッシュ制御手段２は、前記ファイル管理テーブル１を用いて、ファイル格納手段４に対するファイルの挿入・削除を管理するキャッシュ制御手段２である。端末からリクエストされたファイルがファイル格納手段４にない場合、このファイルをファイル格納手段４に格納するためのスペースがあれば、このファイル格納手段４に格納する。一方、必要なスペースがない場合は、前記ファイル管理テーブル１に記憶された情報をもとに、マークされていないファイルの中から、優先度の低い順に任意の数のファイルを削除し、それでも必要なスペースが空かない場合は、必要なスペースが空くまで、残りのファイルの中から最終参照時刻が古い順に前記ファイル格納手段４からファイルを削除することにより、ファイルを格納するための空きスペースをつくる。その上で、サーバーから獲得したファイルを前記ファイル格納手段４に格納する。この実施形態では、新たにファイルをファイル格納手段４に格納するためのスペースがない場合に、キャッシュ制御手段２は、
１．ファイル管理テーブル１に記憶された情報をもとに、優先度が最も低いファイルを選択し、
２．マークされていないファイルであれば削除した後、１．に戻り、
３．マークされているファイルであれば、そのファイルも含めた残りのファイルの中から最終参照時刻が古い順にファイル格納手段からファイルを削除し、
４．サーバーから獲得したファイルをファイル格納手段に格納する。
【００２４】
という処理を行なう。この場合のフローを、図４に示した。また、この実施形態では、ファイルの優先度は、ファイルのサイズの逆数である１／（ファイルのサイズ）で表され、ファイル格納手段４の容量は、例えば１０であるものとする。また、以下では、説明を簡潔にするため、ファイル管理テーブル１とファイル格納手段４を区別しないものとする。また、前記ファイル管理テーブル１に実際に記憶されるのは、ファイルのエントリであるが、混乱の恐れがない限り、ファイルとエントリを区別しないものとする。
【００２５】
まず、図２に示したファイルがリクエストされるものとする。また、図３は、２行目に示す系列に従って、ファイルがリクエストされたときの、ファイル管理テーブルの内容を示している。シーケンス番号は、説明の便宜上つけたものである。
【００２６】
最初、キャッシュは空なので、（シーケンス番号）３番目までのリクエストは全てフォルトし、３つのファイルは、全て、ファイル格納手段４に格納される。
【００２７】
次に、４番目のリクエストはファイルＢに対するリクエストであるが、ファイルＢはキャッシュされていないので、まずファイルＢをファイル管理テーブル１に挿入しなければならない。しかし、ファイルＢを挿入するとファイル管理テーブル１内のファイルサイズの合計はファイル格納手段４の容量、１０、を越えるので、ファイルＡ、Ｃ、Ｄのうち最も優先度が低いＡを削除し、ファイルＢのエントリを加える。この際、所定の確率に従ってファイルＢにマークするが、ここではマークされなかったものとする。
【００２８】
さらに、５番目、６番目のリクエストについても、４番目と同様の手順で処理される。ここでも新たにファイル管理テーブル１に記憶されたファイルはマークされなかったものとする。
【００２９】
次に７番目のリクエストで、ファイルＢへのリクエストがフォルトするが、ファイルＢをファイル管理テーブルに挿入するとき、マーク（＊）されたものとする。
【００３０】
続いて８番目のリクエストで、ファイルＡへのリクエストがフォルトするので、ファイルＡのエントリをファイル管理テーブル１に加えるために、他のエントリを削除しなければならない。優先度が低い順では、Ｂが削除されることになるが、Ｂにはマーク（＊）がついているので、ＬＲＵ方式に従って削除する。このＬＲＵ方式順では、Ｄが最も参照時刻が古いので、削除される。ここでも、ファイル管理テーブルにＡのエントリを作るときに、マーク（＊）されたものとする。
【００３１】
次に９番目のリクエストは、ファイル管理テーブル１内にあるファイルＢに対するものなのでヒットする（キャッシュから読み出すことができる）。
【００３２】
さらに１０番目のリクエストでは、ファイルＤへのリクエストがフォルトするので、ファイルＤのエントリをファイル管理テーブル１に加えるために、他のエントリを削除しなければならない。優先度が低い順では、Ｂが削除されることになるが、Ｂには、マーク（＊）がついているので、同様にＬＲＵ方式順により、Ｅ、Ａの順で２つのファイルが削除される。ここでは、ファイルＤにはマーク（＊）されなかったものとする。
【００３３】
そして１１番目のリクエストでは、フォルトがおこるが、ファイルＣを挿入するスペースがあるので、どのファイルも削除されない。
【００３４】
次に１２番目のリクエストでは、ＬＲＵ方式に従ってファイルＢが削除され、ファイルＡが挿入される。ここでは、ファイルＡにはマークされなかったものとする。
【００３５】
そして１３番目のリクエストはキャッシュにヒットするので、キャッシュから読み出す。
【００３６】
次に１４番目のリクエストでは、ファイル管理テーブル１内のどのファイルにもマークがついていないので、優先度の低い順にＡが削除される。
【００３７】
次に本発明の実施形態を用いた場合のフォルトしうるデータ量の上限値「最悪値」について説明する。
【００３８】
はじめに、前記ネットワーク上の端末から出されたファイルのリクエストの時系列を先頭から分割してできる連続部分列であって、リクエストされた相異なるファイルのサイズの合計が、前記ファイル格納手段４の容量を越えない最長の部分列をフェーズと呼ぶことにする。従って、各フェーズ内では、リクエストされる相異なるファイルのサイズの合計は、常にファイル格納手段４の容量以下である。また、前記フェーズは、ファイル格納手段４の容量とリクエストの時系列のみに依存し、キャッシュ制御手段２の内容に対しては独立である。また、図３において、リクエスト列を区切る二重線は、隣接するフェーズの区切りを表している。
【００３９】
任意のフェーズにおいてマーク（＊）されたファイルが、前記フェーズが終了するまでに、ＬＲＵ方式によって削除されることはない。理由は以下の通りである。
【００４０】
前記任意のフェーズに対して、例えば、前記フェーズ処理中にマークされたファイルＱが、ファイルＰをファイル格納手段４へ入れるときに、ＬＲＵ方式によって前記フェーズ処理中に削除されたとすると、ファイルＰ、ファイルＱ及びファイルＱよりも最終参照時刻が新しいファイルはすべて、前記フェーズでリクエストされたことになる。よって、これらのファイルサイズの和は、ファイル格納手段４の容量以下となる。このことは、ファイルＱが削除されることに矛盾することになり、よって、前記フェーズ処理中に、ファイルＱが削除されることはない。
【００４１】
したがって、任意のフェーズにおいてマークされた各ファイルは、前記フェーズが終了するまでに、優先度が低い順位においても、ＬＲＵ方式においても削除されることはない。つまり、任意のフェーズにおける各ファイルのフォルト回数は、前記フェーズにおいて前記ファイルがマークされる以前にフォルトする回数に等しいことになる。以下に詳しく説明する。
【００４２】
まず、ファイルを任意のフェーズにおいて確率１／Ｎでマークするものとすると、前記フェーズにおいて、前記ファイルが、ｘ回目のフォルトでマークされる確率は、
【００４３】
【数１】
0003694226.tif 000002
【００４４】
である。したがって、前記フェーズ処理中に、前記ファイルがマークされる以前に起こるフォルト数の期待値は、高々、
【００４５】
【数２】
0003694226.tif 000003
である。
【００４６】
よって、各フェーズでフォルトする回数の期待値は、そのフェーズ内でリクエストされる各ファイルにつき高々Ｎ回である。したがって、フォルトしたデータ容量（フォルト量）は、ファイル格納手段４の容量の高々Ｎ倍である。つまり、Ｎを増やすほど優先度が低い順に削除される可能性は高くなるが、各フェーズでのフォルト量の期待値の最悪値も大きくなる。
【００４７】
一方、ＬＲＵ方式のみを用いた場合は、任意のフェーズにおいて、同一のファイルに対するリクエストがフォルトする回数は高々１回であり、フォルト量は、高々、ファイル格納手段の容量である。
【００４８】
これは、以下の理由による。
【００４９】
任意のフェーズにおいて、前記フェーズでフォルトしてファイル格納手段４に入れられたファイルＱが、ファイルＰをファイル格納手段へ入れるときに、ＬＲＵ方式によって、前記フェーズ処理中に削除されたとする。ファイルＰ、ファイルＱ及び、ファイルＱよりも最終参照時刻が新しいファイルはすべて、前記フェーズでリクエストされたことになる。よって、これらのファイルサイズの和は、ファイル格納手段４の容量以下である。これは、ファイルＱが削除されることに矛盾することとなり、したがって、前記フェーズを処理する間は、ファイルＱは削除されない。
【００５０】
このことから、ＬＲＵ方式を用いた場合に起こり得るフォルト回数およびフォルト量の最悪値にくらべて、本発明の実施形態を用いた場合に起こり得るフォルト回数およびフォルト量の期待値の最悪値は、高々Ｎ倍で抑えられる。従って、Ｎの値は優先度が重要であれば値を大きく、最悪ケースにおけるフォルト量の期待値が重要であれば値を低く、ユーザの用途に応じて設定すればよい。
【００５１】
また、この実施形態では、キャッシュ制御手段２は、新たにファイルを格納するためのスペースが十分にない場合は、
１．ファイル管理テーブルに記憶された情報をもとに、優先度が最も低いファイルを選択し、
２．マークされていないファイルであれば削除した後、１．に戻り、
３．マークされているファイルであれば、そのファイルも含めた残りのファイルの中から最終参照時刻が古い順にファイル格納手段からファイルを削除する。
【００５２】
という処理をすることにより、ファイルを格納するための空きスペースを作っている。
【００５３】
しかし、次のように一般化されたキャッシュ制御手段（まず、マークされていないファイルの中から優先度の低い順にファイルを任意の数だけ削除し、それでも空きスペースが不十分な場合は、必要なスペースが空くまで、残りのファイルの中からＬＲＵ方式順でファイルを削除する）に対しても、上述と同様の理由により、ＬＲＵ方式を用いた場合に起こり得るフォルト回数およびフォルト量の最悪値にくらべて、本発明の実施形態を用いた場合に起こり得るフォルト回数およびフォルト量の期待値の最悪値は、高々Ｎ倍で抑えられる。
【００５４】
【発明の効果】
以上述べたように本発明によれば、あるアクセスパターンを仮定したときに特に有効なキャッシュ制御方式をＬＲＵ方式と組み合わせることにより、仮定したアクセスパターンに対しては、ＬＲＵ方式よりもさらにキャッシュヒット率が高く、仮定したアクセスパターン以外に対しても、フォルトするデータ量の期待値が保証され、かつ、少ない記憶容量と少ない手順で実現可能なキャッシュ制御を用いたネットワークキャッシュ装置およびネットワークキャッシュ制御方法および記録媒体を提供することが出来る。
【図面の簡単な説明】
【図１】  本発明の実施形態に係る構成を説明する図。
【図２】  本発明に係るファイルの実施形態を示す図。
【図３】  本発明の実施形態に係るファイルの要求列に対するファイル管理テーブルの状態遷移を示す図。
【図４】  本発明の実施形態に係るファイル管理テーブル及びキャッシュ制御手段の動作を示すフローを示す図。
【図５】  本発明に係るファイル管理テーブルの実施形態を示す図。
【符号の説明】
１…ファイル管理テーブル
２…キャッシュ制御手段
３…ネットワークキャッシュ装置
４…ファイル格納手段
５…端末
６…サーバー
７…ネットワーク
【図１】
0003694226.tif 000004
【図２】
0003694226.tif 000005
【図３】
0003694226.tif 000006
【図４】
0003694226.tif 000007
【図５】
0003694226.tif 000008