(57)【特許請求の範囲】
【請求項１】
キャッシュサーバにおいて、リクエストの列に基づいて、仮想的なキャッシュ容量（以下、仮想キャッシュ容量と記す）を持つ仮想的なキャッシュ（以下、仮想キャッシュ）に対する性能値を算出するキャッシュサーバ性能値算出方法において、
リクエストされたオブジェクトＡが、オブジェクト名、オブジェクトサイズ、オブジェクトをキャッシュする仮想キャッシュの中で最小のレベルである下限ラベル、及び順位を記録するキャッシュテーブルに存在するかを判定し、
存在しなければ、オブジェクト名、サイズ、下限ラベル、キャッシュ置換アルゴリズムで決定される順位の組を前記キャッシュテーブルに書き込み、
存在すれば、キャッシュ置換アルゴリズムでオブジェクトの新たな順位を決定し、前記キャッシュテーブルのオブジェクトの順位を更新し、
前記オブジェクトＡの下限ラベルを読み取り、
前記下限ラベル以上のレベルの仮想キャッシュにおいては、前記オブジェクトＡがヒットしたものとして性能値を計算し、
前記下限ラベル未満のレベルの仮想キャッシュにおいては、前記オブジェクトＡがヒットしなかったものとして性能値を計算し、
前記仮想キャッシュに蓄積されているオブジェクトプログラムの中で最も順位の低いオブジェクトであるエンドオブジェクトの中で、オブジェクトＡの順位以下の最大の順位のものを、該仮想キャッシュのレベル、エンドオブジェクト、及びその順位を並べたエンドポインターテーブル上で探し、該エンドオブジェクトに対応する仮想キャッシュのレベルを設定し、
所定のレベルのすべての仮想キャッシュの各々に対して、オブジェクト追い出し処理を行い、
前記オブジェクトＡの下限ラベルを設定することを特徴とするキャッシュサーバ性能値算出方法。
【請求項２】
前記オブジェクト追い出し処理として、
リクエストされた前記オブジェクトＡを、あるレベルＫの仮想キャッシュに蓄積しようとした時、該仮想キャッシュの容量を越える場合には、該レベルＫの仮想キャッシュのエンドオブジェクトを前記エンドポインタテーブルで探し、順位の小さいものから順に、該オブジェクトＡを蓄積できる空き容量ができるまで、オブジェクトを該レベルＫの仮想キャッシュから追い出し、
追い出された残りのオブジェクトの中で順位が最も小さいものを前記エンドポインタテーブルのあるレベルＫの仮想キャッシュのエンドオブジェクトとする請求項１記載のキャッシュサーバ性能値算出方法。
【請求項３】
キャッシュサーバにおいて、リクエストの列に基づいて、仮想キャッシュ容量を持つ仮想キャッシュに対する性能値を算出するキャッシュサーバ性能値算出装置であって、
オブジェクト名、オブジェクトサイズ、オブジェクトをキャッシュする仮想キャッシュの中で最小のレベルである下限ラベル、及び順位の組とを記録するキャッシュテーブルと、
各仮想キャッシュに蓄積されているオブジェクトの中で最も順位の低いオブジェクトであるエンドオブジェクト、仮想キャッシュのレベル、及びその順位を並べたエンドポインタテーブルと、
リクエストされたオブジェクトＡが、前記キャッシュテーブルに存在するかを判定し、存在しなければ、オブジェクト名、サイズ、下限ラベル、キャッシュ置換アルゴリズムで決定される順位の組を該キャッシュテーブルに書き込み、存在すれば、キャッシュ置換アルゴリズムでオブジェクトの新たな順位を決定し、該キャッシュテーブルのオブジェクトの順位を更新するオブジェクト判定手段と、
前記オブジェクトＡの下限ラベルを読み取り、前記下限ラベル以上のレベルの仮想キャッシュにおいては、前記オブジェクトＡがヒットしたものとして性能値を計算し、前記下限ラベル未満のレベルの仮想キャッシュにおいては、前記オブジェクトＡがヒットしなかったものとして性能値を計算し、仮想キャッシュに蓄積されているオブジェクトプログラムの中で最も順位の低いオブジェクトであるエンドオブジェクトの中で、オブジェクトＡの順位以下の最大の順位のものを、該仮想キャッシュのレベル、エンドオブジェクト、及びその順位を並べたエンドポインターテーブル上で探し、該エンドオブジェクトに対応する仮想キャッシュのレベルを設定する性能値計算手段と、
所定のレベルのすべての仮想キャッシュの各々に対して、オブジェクト追い出し処理を行う追い出し手段と、
前記オブジェクトＡの下限ラベルを設定するラベル設定手段とを有することを特徴とするキャッシュサーバ性能値算出装置。
【請求項４】
前記追い出し手段は、
リクエストされた前記オブジェクトＡを、あるレベルＫの仮想キャッシュに蓄積しようとした時、該仮想キャッシュの容量を越える場合には、該レベルＫの仮想キャッシュのエンドオブジェクトを前記エンドポインタテーブルで探し、順位の小さいものから順に、該オブジェクトＡを蓄積できる空き容量ができるまで、オブジェクトを該レベルＫの仮想キャッシュから追い出し、追い出された残りのオブジェクトの中で順位が最も小さいものを該記エンドポインタテーブルのあるレベルＫの仮想キャッシュのエンドオブジェクトとする手段を有する請求項３記載のキャッシュサーバ性能値算出装置。
【請求項５】
キャッシュサーバにおいて、リクエストの列に基づいて、仮想キャッシュ容量を持つ仮想キャッシュに対する性能値を算出するキャッシュサーバ性能算出プログラムを格納した記憶媒体であって、
コンピュータに、
リクエストされたオブジェクトＡが、オブジェクト名、オブジェクトサイズ、オブジェクトをキャッシュする仮想キャッシュの中で最小のレベルである下限ラベル、及び順位を記録するキャッシュテーブルに存在するかを判定するステップと、
存在しなければ、オブジェクト名、サイズ、下限ラベル、キャッシュ置換アルゴリズムで決定される順位の組を前記キャッシュテーブルに書き込むステップと、
存在すれば、キャッシュ置換アルゴリズムでオブジェクトの新たな順位を決定し、前記キャッシュテーブルのオブジェクトの順位を更新するステップと、
前記オブジェクトＡの下限ラベルを読み取るステップと、
前記下限ラベル以上のレベル仮想キャッシュにおいては、前記オブジェクトＡがヒットしたものとして性能値を計算するステップと、
前記下限ラベル未満のレベルの仮想キャッシュにおいては、前記オブジェクトＡがヒットしなかったものとして性能値を計算するステップと、
前記仮想キャッシュに蓄積されているオブジェクトの中で最も順位の低いオブジェクトであるエンドオブジェクトの中でオブジェクトＡの順位以下の最大の順位のものを、仮想キャッシュのレベル、エンドオブジェクト、及びその順位を並べたエンドポインタテーブル上で探し、該エンドオブジェクトに対応する仮想キャッシュのレベルを設定するステップと、
所定のレベルの全ての仮想キャッシュの各々に対して、オブジェクト追い出し処理を行うステップと、
前記オブジェクトＡの下限ラベルを設定するステップと、
を実行させるプログラムを格納したことを特徴とするキャッシュサーバ性能値算出プログラムを格納した記憶媒体。
【請求項６】
前記オブジェクト追い出し処理を行うステップは、
リクエストされた前記オブジェクトＡを、あるレベルＫの仮想キャッシュに蓄積しようとした時、該仮想キャッシュの容量を越える場合には、該レベルＫの仮想キャッシュのエンドオブジェクトを前記エンドポインタテーブルで探し、順位の小さいものから順に、該オブジェクトＡを蓄積できる空き容量ができるまでオブジェクトを該レベルＫの仮想キャッシュから追い出すステップと、
追い出された残りのオブジェクトの中で順位が最も小さいものを前記エンドポインタテーブルのあるレベルＫの仮想キャッシュのエンドオブジェクトとするステップと、
を含む、請求項５記載のキャッシュサーバ性能値算出プログラムを格納した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、キャッシュサーバ性能値算出方法及び装置及びキャッシュサーバ性能値算出プログラムを格納した記憶媒体に係り、特に、実際のリクエスト列に基づいて、様々なキャッシュ容量における性能値を仮想的に求めることによって、適切なキャッシュ容量を設計するためのキャッシュサーバ性能値算出方法及び装置及びキャッシュサーバ性能値算出プログラムを格納した記憶媒体に関する。
【０００２】
【従来の技術】
キャッシュサーバは、リクエストされたオブジェクトがキャッシュ内に蓄積されている場合は、当該オブジェクトをクライアントへ転送し、キャッシュ置換アルゴリズムによって、当該オブジェクトの順位を変更する。また、リクエストされたオブジェクトがキャッシュ内に蓄積されていない場合は、当該オブジェクトをオリジンサーバから取得してキャッシュ内に蓄積し、キャッシュ置換アルゴリズムによって当該オブジェクトの順位を決定する。その際、リクエストされたオブジェクトを蓄積しようとしたとき、キャッシュ容量を越える場合は、キャッシュされたオブジェクトの中で順位の低いものから削除することによって空き容量を作り、リクエストされたオブジェクトをキャッシュ内に蓄積する。
【０００３】
このような動作を行うキャッシュサーバのキャッシュ容量の設計として、従来は、リクエストの発生間隔に何らかの確率分布を仮定した上で、規定された性能値の閾値を満たす容量を解析的に求める方法がある。
【０００４】
【発明が解決しようとする課題】
しかしながら、上記の従来の方法は、仮定する確率分布の妥当性が不明であり、確率分布のパラメータをどのように設定すべきか不明であるため、この方法によって設計された容量が実際のリクエストに対して適切か否かを判断することができない。従って、実際には少なく見積り過ぎることにより性能の劣化、もしくは、多く見積り過ぎることによるコストアップが生じうるという問題がある。
【０００５】
本発明は、上記の点に鑑みなされたもので、要求性能を満たすキャッシュ容量を決定するために、実際のリクエスト列に基づいて、複数の異なる容量における性能値を同時に算出することが可能なキャッシュサーバ性能値算出方法及び装置及びキャッシュサーバ性能値算出プログラムを格納した記憶媒体を提供することを目的とする。
【０００６】
【課題を解決するための手段】
図１は、本発明の原理を説明するための図である。
本発明（請求項１）は、キャッシュサーバにおいて、リクエストの列に基づいて、仮想キャッシュ容量を持つ仮想キャッシュに対する性能値を算出するキャッシュサーバ性能値算出方法において、
リクエストされたオブジェクトＡが、オブジェクト名、オブジェクトサイズ、オブジェクトをキャッシュする仮想キャッシュの中で最小のレベルである下限ラベル、及び順位を記録するキャッシュテーブルに存在するかを判定し（ステップ１）、
存在しなければ、オブジェクト名、サイズ、下限ラベル、キャッシュ置換アルゴリズムで決定される順位の組をキャッシュテーブルに書き込み（ステップ２）、
存在すれば、キャッシュ置換アルゴリズムでオブジェクトの新たな順位を決定し、キャッシュテーブルのオブジェクトの順位を更新し（ステップ３）、
オブジェクトＡの下限ラベルを読み取り（ステップ４）、
下限ラベル以上のレベルの仮想キャッシュにおいては、オブジェクトＡがヒットしたものとして性能値を計算し（ステップ５）、
下限ラベル未満のレベルの仮想キャッシュにおいては、オブジェクトＡがヒットしなかったものとして性能値を計算し（ステップ６）、
仮想キャッシュに蓄積されているオブジェクトの中で最も順位の低いオブジェクトであるエンドオブジェクトの中でオブジェクトＡの順位以下の最大の順位のものを、仮想キャッシュのレベル、エンドオブジェクト、及びその順位を並べたエンドポインターテーブル上で探し、該エンドオブジェクトに対応する仮想キャッシュのレベルを設定し（ステップ７）、
所定のレベルのすべての仮想キャッシュの各々に対して、オブジェクト追い出し処理を行い（ステップ８）、
オブジェクトＡの下限ラベルを設定する（ステップ９）。
【０００７】
本発明（請求項２）は、オブジェクト追い出し処理として、
リクエストされたオブジェクトＡを、あるレベルＫの仮想キャッシュに蓄積しようとした時、該仮想キャッシュの容量を越える場合には、該レベルＫの仮想キャッシュのエンドオブジェクトをエンドポインタテーブルで探し、順位の小さいものから順に、該オブジェクトＡを蓄積できる空き容量ができるまで、オブジェクトを該レベルＫの仮想キャッシュから追い出し、
追い出された残りのオブジェクトの中で順位が最も小さいものをエンドポインタテーブルのあるレベルＫの仮想キャッシュのエンドオブジェクトとする。
【０００８】
図２は、本発明の原理構成図である。
本発明（請求項３）は、キャッシュサーバにおいて、リクエストの列に基づいて、仮想キャッシュ容量を持つ仮想キャッシュに対する性能値を算出するキャッシュサーバ性能値算出装置であって、
オブジェクト名、オブジェクトサイズ、オブジェクトをキャッシュする仮想キャッシュの中で最小のレベルである下限ラベル、及び順位の組とを記録するキャッシュテーブル１３０と、
仮想キャッシュに蓄積されているオブジェクトの中で最も低い順位のオブジェクトであるエンドオブジェクト、仮想キャッシュのレベル、及びその順位を並べたエンドポインタテーブル１４０と、
リクエストされたオブジェクトＡが、キャッシュテーブル１３０に存在するかを判定し、存在しなければ、オブジェクト名、サイズ、下限ラベル、キャッシュ置換アルゴリズムで決定される順位の組をキャッシュテーブル１３０に書き込み、存在すれば、キャッシュ置換アルゴリズムでオブジェクトの新たな順位を決定し、キャッシュテーブルのオブジェクトの順位を更新するオブジェクト判定手段１１０と、
オブジェクトＡの下限ラベルを読み取り、下限ラベル以上のレベルの仮想キャッシュにおいては、オブジェクトＡがヒットしたものとして性能値を計算し、下限ラベル未満のレベルの仮想キャッシュにおいては、オブジェクトＡがヒットしなかったものとして性能値を計算し、仮想キャッシュに蓄積されているオブジェクトの中で最も順位の低いオブジェクトであるエンドオブジェクトの中でオブジェクトＡの順位以下の最大の順位のものを、エンドポインターテーブル１４０上で探し、該エンドオブジェクトに対応する仮想キャッシュのレベルを設定する性能値計算手段１２０と、
所定のレベルのすべての仮想キャッシュの各々に対して、オブジェクト追い出し処理を行う追い出し手段１５０と、
オブジェクトＡの下限ラベルを設定するラベル設定手段１６０とを有する。
【０００９】
本発明（請求項４）は、追い出し手段１５０において、
リクエストされたオブジェクトＡを、あるレベルＫの仮想キャッシュに蓄積しようとした時、該仮想キャッシュの容量を越える場合には、該レベルＫの仮想キャッシュのエンドオブジェクトをエンドポインタテーブルで探し、順位の小さいものから順に、該オブジェクトＡを蓄積できる空き容量ができるまで、オブジェクトを該レベルＫの仮想キャッシュから追い出し、追い出された残りのオブジェクトの中で順位が最も小さいものを該記エンドポインタテーブルのあるレベルＫの仮想キャッシュのエンドオブジェクトとする手段を有する。
【００１０】
本発明（請求項５）は、キャッシュサーバにおいて、リクエストの列に基づいて、仮想キャッシュ容量を持つ仮想キャッシュに対する性能値を算出するキャッシュサーバ性能算出プログラムを格納した記憶媒体であって、
コンピュータに、
リクエストされたオブジェクトＡが、オブジェクト名、オブジェクトサイズ、オブジェクトをキャッシュする仮想キャッシュの中で最小のレベルである下限ラベル、及び順位を記録するキャッシュテーブルに存在するかを判定するステップと、
存在しなければ、オブジェクト名、サイズ、下限ラベル、キャッシュ置換アルゴリズムで決定される順位の組をキャッシュテーブルに書き込むステップと、
存在すれば、キャッシュ置換アルゴリズムでオブジェクトの新たな順位を決定し、キャッシュテーブルのオブジェクトの順位を更新するステップと、
オブジェクトＡの下限ラベルを読み取るステップと、
下限ラベル以上のレベル仮想キャッシュにおいては、オブジェクトＡがヒットしたものとして性能値を計算するステップと、
下限ラベル未満のレベルの仮想キャッシュにおいては、オブジェクトＡがヒットしなかったものとして性能値を計算するステップと、
仮想キャッシュに蓄積されているオブジェクトの中で最も順位の低いオブジェクトであるエンドオブジェクトの中でオブジェクトＡの順位以下の最大の順位のものを、仮想キャッシュのレベル、エンドオブジェクト、及びその順位を並べたエンドポインタテーブル上で探し、該エンドオブジェクトに対応する仮想キャッシュのレベルを設定するステップと、
所定のレベルの全ての仮想キャッシュの各々に対して、オブジェクト追い出し処理を行うステップと、
オブジェクトＡの下限ラベルを設定するステップと、を実行させるプログラムを格納した記憶媒体である。
【００１１】
本発明（請求項６）は、オブジェクト追い出し処理を行うステップにおいて、
リクエストされた前記オブジェクトＡを、あるレベルＫの仮想キャッシュに蓄積しようとした時、該仮想キャッシュの容量を越える場合には、該レベルＫの仮想キャッシュのエンドオブジェクトをエンドポインタテーブルで探し、順位の小さいものから順に、該オブジェクトＡを蓄積できる空き容量ができるまでオブジェクトを該レベルＫの仮想キャッシュから追い出すステップと、
追い出された残りのオブジェクトの中で順位が最も小さいものをエンドポインタテーブルのあるレベルＫの仮想キャッシュのエンドオブジェクトとするステップと、
を含む。
【００１２】
上記のように、本発明では、複数の仮想キャッシュを用いることにより、複数の異なるキャッシュ容量における性能値を同時に計算することが可能となる。
次に、オブジェクトに対して下限ラベルを定義することにより、そのオブジェクトをキャッシュしていない仮想キャッシュの集合（当該オブジェクトの下限ラベルより小さいレベルを持つすべての仮想キャッシュ）が把握できる。従って、リクエストされたオブジェクトがヒットし仮想キャッシュの集合と、ヒットしなかった仮想キャッシュの集合が、下限ラベルを参照することにより、容易に分離できるため、各仮想キャッシュ毎にヒットしたかしなかったかの判定を行う必要がなく、より少ない計算で複数の異なるキャッシュ容量における性能値を計算することが可能となる。
【００１３】
また、リクエストされたオブジェクトの順位以下の順位を持つエンドオブジェクトの中で、最大の順位のものに対応する仮想キャッシュのレベルをＬB 、リクエストされたオブジェクトの下限ラベルをＬとして、ＬB からＬ−１のレベルの全ての仮想キャッシュの各々に対してのみ、オブジェクト追い出し処理を行うことによって、オブジェクト追い出し処理を必要最低限に抑えることができる。
【００１４】
更に、エンドポインタテーブルを用いることにより、各仮想キャッシュにおいて最小の順位のオブジェクトをすぐに参照することができるため、新たなオブジェクトをキャッシュする際に空き容量を作るために順位の小さいものを新たに探索する必要がなく、オブジェクトの追い出し処理を高速に行うことが可能となる。
【００１５】
このようにして、実際のリクエスト列に基づいて、複数の異なる容量における性能値を、少ない手間で同時に算出することが可能となる。
【００１６】
【発明の実施の形態】
図３は、本発明のキャッシュサーバ性能値算出装置の接続構成を示し、図４は、本発明のキャッシュサー性能値算出装置の構成を示す。
キャッシュサーバ性能値算出装置１００は、サーバ２００に接続され、当該サーバ２００からリクエスト列が入力されると、キャッシュサーバ性能値を算出し、入力されたリクエスト列に対応する性能値を出力する。
【００１７】
キャッシュサーバ性能値算出装置１００は、オブジェクト判定部１１０、性能値計算部１２０、キャッシュテーブル１３０、エンドポインタテーブル１４０から構成される。
キャッシュテーブル１３０は、オブジェクト名、当該オブジェクトサイズ、当該オブジェクトをキャッシュする仮想キャッシュの中で最小のレベル（以下、下限ラベルと記す）、及び順位の組を記録したテーブルである。
【００１８】
エンドポインタテーブル１４０は、仮想キャッシュのレベル、当該仮想キャッシュに蓄積されているオブジェクトの中で最も順位の低いもの（以下、エンドオブジェクトと記す）、及びその順位を並べたテーブルである。
オブジェクト判定部１１０は、リクエストされたオブジェクトＡがキャッシュテーブル１３０にあるか否かを判定し、存在しなければ当該オブジェクト名、サイズ、下限ラベル、キャッシュ置換アルゴリズムで決定される順位の組を、キャッシュテーブル１３０に書き込む。但し、下限ラベルは∞とする。一方、リクエストされたオブジェクトＡがキャッシュテーブル１３０に存在すれば、キャッシュ置換アルゴリズムでその新たな順位を決定し、キャッシュテーブル１３０のすべてのオブジェクトの順位を更新する。
【００１９】
性能値計算部１２０は、性能値を計算する計算部１２１と、仮想キャッシュに対してオブジェクトの追い出しを行う追い出し処理部１２２から構成される。
計算部１２１は、当該オブジェクトＡの下限ラベル（Ｌとする）を読み取る。この下限ラベルＬ以上のレベルの仮想キャッシュにおいては、オブジェクトＡがヒットしたものとして性能値を計算する。一方、この下限ラベル未満のレベルの仮想キャッシュにおいては、オブジェクトＡがヒットしなかったものとして性能値を計算する。そして、オブジェクトＡの順位以下の順位を持つオブジェクトの中で最大の順位のものをエンドポインタテーブル１４０上で探し、そのエンドオブジェクトに対応する仮想キャッシュのレベルをＬB とする。
【００２０】
追い出し処理部１２２は、ＬB からＬ−１のレベルのすべての仮想キャッシュの各々に対して、オブジェクト追い出し処理を行い、オブジェクトＡの下限ラベルをＬB とする。
図５は、本発明のキャッシュサーバ性能値算出方法の処理手順のフローチャートである。
【００２１】
ステップ１０１）  オブジェクト判定部１１０において、リクエストされたオブジェクトＡがキャッシュテーブル１３０に存在するかを判定する。存在する場合にはステップ１０２に移行し、存在しない場合にはステップ１０３に移行する。
ステップ１０２）  キャッシュ置換アルゴリズムでその新たな順位を決定し、キャッテーブル１３０のすべてのオブジェクトの順位を更新し、ステップ１０４に移行する。
【００２２】
ステップ１０３）  オブジェクトＡがキャッシュテーブル１３０に存在しない場合には、以下の内容をキャッシュテーブル１３０に書き込む。
▲１▼  当該オブジェクト名
▲２▼  サイズ
▲３▼  下限ラベル：∞
▲４▼  キャッシュ置換アルゴリズムで決定される順位
ステップ１０４）  性能値計算部１２０の計算部１２１において、当該オブジェクトＡの下限ラベルＬを読み取る。
【００２３】
・この下限ラベルＬ以上のレベルの仮想キャッシュにおいては、オブジェクトＡがヒットしたものとして性能値を計算する。
・一方、この下限ラベル未満のレベルの仮想キャッシュにおいては、オブジェクトＡがヒットしなったものとして、性能値を計算する。
ステップ１０５）  オブジェクトＡの順位以下の順位を持つエンドオブジェクトの中で最大の順位のものをエンドポインタテーブル１４０上で探し、そのエンドオブジェクトに対応する仮想キャッシュのレベルＬB とする。
【００２４】
ステップ１０６）  レベルＫを、最大の順位のものに対応する仮想キャッシュのレベルＬB とする。
ステップ１０７）  追い出し処理部１２２において、レベルＬB の仮想キャッシュに対して、オブジェクト追い出し処理（Discard ）を行う。詳細は図６で説明する。
【００２５】
ステップ１０８）  追い出された各オブジェクトの下限ラベルＫを１増加させる。
ステップ１０９）  レベルＫが下限ラベルＬとなった場合にはステップ１１０に移行し、そうでない場合にはステップ１０７に移行する。
ステップ１１０）  オブジェクトＡの下限ラベルをＬB にする。
【００２６】
ステップ１１１）  次のオブジェクトの処理に移行する。
次に、上記のステップ１０７におけるオブジェクト追い出し処理について説明する。
図６は、本発明のオブジェクト追い出し処理（Discard ）の手順のフローチャートである。
【００２７】
ステップ２０１）  性能値計算部１２０の追い出し処理部１２２は、オブジェクトＡをレベルＫの仮想キャッシュに蓄積しようとしたとき、当該仮想キャッシュ容量を越えるかを判定し、越える場合には当該処理を終了する。
ステップ２０２）  レベルＫの仮想キャッシュのエンドオブジェクトをエンドポインタテーブル１４０で探し、順位の小さいものから順に、以下の処理を行う。  ステップ２０３）  オブジェクトをレベルＫ仮想キャッシュから追い出す。
つまり、各オブジェクトの下限ラベルを１だけ増加させる。
【００２８】
ステップ２０４）  オブジェクトを蓄積できる空き容量があるかを判定し、ある場合には、ステップ２０５に移行し、ない場合にはステップ２０３に移行する。
ステップ２０５）  追い出された残りのオブジェクトの中で順位が最も小さいものをエンドポインタテーブル１４０のレベルＫ仮想キャッシュのエンドオブジェクトとする。
【００２９】
このように、キャッシュテーブル１３０として、動的ハッシュなどのデータ構造を用いることにより、オブジェクトがキャッシュテーブル１３０にあるか否かを高速に判定することができる。また、オブジェクトの順位を線形リスト構造やヒープ構造で管理することにより、順位に関する操作を高速化することができる。
【００３０】
【実施例】
以下、図面と共に本発明の実施例を説明する。
図７は、本発明の一実施例のリクエスト列の例を示し、図８は、本発明の一実施例のキャッシュテーブルの遷移を示し、図９は、本発明の一実施例のエンドポインタテーブルの遷移を示す。
【００３１】
以下、図７に示すリクエスト列の例に基づいて、キャッシュサーバ性能算出の手順を説明する。
ここで、仮想キャッシュ容量５，１０（それぞれレベル０，１）とし、性能値としてヒット率（キャッシュでヒットしたオブジェクト数÷リクエストさたオブジェクト総数）を用いるものとする。
【００３２】
また、キャッシュ置換アルゴリズムとして、ＬＲＵ(Least Recently Used）を用いることにする。これは、オブジェクトがリクエストされた際、当該オブジェクトの順位を、キャッシュされているオブジェクトの中で最大の順位＋１とするものである。
まず、時刻Ｔ1 にオブジェクトＡがリクエストされたとき、キャッシュテーブル１３０には何も載っていないので（ステップ１０１）、オブジェクト判定部１１０は、「オブジェクトＡ、サイズ２、下限ラベル∞、順位１」の組を書き込む（ステップ１０３）（図８（Ａ））。エンドポインタテーブル１４０には「レベル０、オブジェクトＡ、順位１」及び「レベル１、オブジェクトＡ、順位１」と書き込む（図９（Ａ））。
【００３３】
性能値計算部１２０の計算部１２１において、下限ラベル未満のレベルの仮想キャッシュ、つまり、レベル０およびレベル１仮想キャッシュにおいて、オブジェクトＡがヒットしなかったものとして、性能値であるヒット率を計算すると、容量５の場合（レベル０）及び容量１０の場合（レベル１）ともに０である（ステップ１０４）。
【００３４】
オブジェクトＡの順位以下の順位を持つエンドオブジェクトの中で、最大の順位のものはオブジェクトＡ自身しかなく、その仮想キャッシュのレベルは０である。従って、追い出し処理部１２２は、ＬB ＝０，Ｌ−１＝∞なので、レベル０及びレベル１仮想キャッシュに対して、オブジェクト追い出し処理を行う（ステップ１０７）。しかし、いずれも、オブジェクトＡを蓄積することで、容量を越えないので、オブジェクトをレベル０及びレベル１仮想キャッシュから追い出さない。オブジェクトＡの処理の最後にオブジェクトＡの下限ラベルを０に更新する。
【００３５】
次に、時刻Ｔ2 にオブジェクトＢがリクエストされた時、キャッシュテーブル１３０にオブジェクトＢは載っていないので（ステップ１０１）、オブジェクト判定部１１０は、「オブジェクトＢ、サイズ２、下限ラベル∞、順位２」の組をキャッシュテーブル１３０に書き込む（ステップ１０３）（図８（Ｂ））。
性能計算部１２０の計算部１２１において、下限ラベル未満のレベルの仮想キャッシュ、つまり、レベル０及びレベル１の仮想キャッシュにおいて、オブジェクトＢがヒットしなかったものとして、性能値であるヒット率を計算すると、容量５の場合（レベル０）及び容量１０の場合（レベル１）と共に０である（ステップ１０４）。
【００３６】
オブジェクトＢの順位以下の順位を持つエンドオブジェクトの中で、最大の順位のものはオブジェクトＡである。また、その仮想キャッシュのレベルは０である。従って、追い出し処理部１２２は、ＬB ＝０，Ｌ−１＝∞なので、レベル０及びレベル１仮想キャッシュに対して、オブジェクト追い出し処理を行う（ステップ１０７）。しかし、いずれもオブジェクトＢを蓄積することで容量を越えないので、オブジェクトをレベル０及びレベル１仮想キャッシュから追い出さない。オブジェクトＢの処理に最後にオブジェクトＢの下限ラベルを０に更新する（図８（Ｂ））。
【００３７】
時刻Ｔ3 にオブジェクトＣがリクエストされた時、キャッシュテーブル１３０にオブジェクトＣは載っていないので（ステップ１０１）、オブジェクト判定部１１０は、「オブジェクトＣ，サイズ４、下限ラベル∞、順位３」の組を書き込む（ステップ１０３）（図８（Ｃ））。
下限ラベル未満のレベルの仮想キャッシュ、つまり、レベル０及びレベル１仮想キャッシュにおいて、オブジェクトＣがヒットしなかったものとして、性能値計算部１２０の計算部１２１において、性能値であるヒット率を計算すると、容量５の場合（レベル０）及び容量１０の場合（レベル１）共に０である（ステップ１０４）。
【００３８】
オブジェクトＣの順位以下の順位を持つエンドオブジェクトの中で、最大の順位のものはオブジェクトＡである。その仮想キャッシュのレベルは０である。従って、ＬB ＝０，Ｌ−１＝∞なので、追い出し処理部１２２は、レベル０及びレベル１仮想キャッシュに対して、オブジェクト追い出し処理を行う（ステップ１０７）。
【００３９】
・レベル０仮想キャッシュにおいて：
オブジェクトＣを蓄積すると、オブジェクトＡ，Ｂ，Ｃのサイズの合計が２＋２＋４＝８＞５となるため、追い出し処理部１２２において、レベル０からオブジェクトを追い出す処理が必要となる。まず、レベル０仮想キャッシュのエンドオブジェクトをエンドポインタテーブル１４０で探すとオブジェクトＡである（図９（Ｂ））。追い出し処理部１２２は、オブジェクトＡを追い出し（ステップ１０７）、オブジェクトＡの下限ラベルを０から１に更新し、レベル０仮想キャッシュの残されたオブジェクトの中で最も順位が小さいオブジェクトＢを、レベル０仮想キャッシュのエンドオブジェクトとしてエンドポインタテーブル１４０を更新する（図９（Ｃ））。オブジェクトＢ，Ｃのサイズの合計が２＋４＝６＞５となるが、まだ十分な空き容量がないため、追い出し処理部１２２は、オブジェクトＢを追い出し（ステップ１０７）、オブジェクトＢの下限ラベルを０から１に更新し（ステップ１０８）、レベル０仮想キャッシュの残されたオブジェクトの中で最も順位が小さいオブジェクトＣを、レベル０仮想キャッシュのエンドオブジェクトとしてエンドポインタテーブル１４０を更新する（図９（Ｃ））。オブジェクトＣのサイズは４＜５なので、レベル０仮想キャッシュに蓄積可能であり、追い出し処理部１２２は、オブジェクトをレベル０仮想キャッシュから追い出す処理を停止する。
【００４０】
・レベル１仮想キャッシュにおいて：
オブジェクトＡ，Ｂ，Ｃのサイズの合計が２＋２＋４＝８＜１０であり、レベル１仮想キャッシュの容量を越えないので、追い出し処理部１２２は、仮想キャッシュから追い出さない。
オブジェクトＣの処理の最後に、オブジェクトＣの下限ラベルを０にする。
【００４１】
時刻Ｔ4 にオブジェクトＡがリクエストされたとき、キャッシュテーブル１３０には、オブジェクトＡが載っているので、オブジェクト判定部１１０は、キャッシュ置換アルゴリムＬＲＵで新たな順位４に更新する（図８（Ｄ））。
オブジェクトＡの下限ラベルは１なので、性能値計算部１２０の計算部１２１は、レベル０仮想キャッシュにおいて、オブジェクトＡがヒットしなかったものとして、ヒット率を計算すると０である。一方、レベル１仮想キャッシュにおいては、オブジェクトＡがヒットしたとしてヒット率を計算すると、１÷４（ヒット数÷リクエスト総数）＝２５％である。
【００４２】
オブジェクトＡの順位４以下の順位を持つエンドポインタテーブル１４０のエンドオブジェクトの中で、最大の順位のものは、順位３のオブジェクトＣであり、そのレベルは０である。従って、追い出し処理部１２２は、ＬB ＝０、Ｌ−１＝０（オブジェクトＡの下限ラベルＬは１）なので、レベル０仮想キャッシュに対してのみ、オブジェクト追い出し処理を行う。
【００４３】
・レベル０仮想キャッシュにおいて：
オブジェクトＡを蓄積すると、オブジェクトＡ，Ｃのサイズの合計が２＋４＝６＞５となるため、レベル０からオブジェクトを追い出す処理が必要となる。まず、オブジェクト判定部１１０において、レベル０仮想キャッシュのエンドオブジェクトをエンドポインタテーブル１４０で探すと、オブジェクトＣである（図９（Ｃ））。追い出し処理部１２２において、オブジェクトＣを追い出し（ステップ１０７）、オブジェクトＣの下限ラベルを０から１に更新し（ステップ１０８）、レベル０仮想キャッシュの残されたオブジェクトの中で最も順位が小さいオブジェクトＡを、レベル０仮想キャッシュのエンドオブジェクトとしてエンドポインタテーブル１４０を更新する（図９（Ｄ））。
【００４４】
オブジェクトＡのサイズは２＜５であり、レベル０仮想キャッシュの容量を越えないので、追い出し処理部１２２は、レベル０仮想キャッシュに蓄積可能であるため、オブジェクトの追い出し処理を停止する。
オブジェクトＡの処理の最後にオブジェクトＡの下限ラベルを０にする（ステップ１１０）。
【００４５】
最終的に得られたヒット率は、、容量５の場合は、０％、容量１０の場合は２５％であることが分かる。
このようにして、複数のことある容量におけるキャッシュサーバの性能値を同時に算出することができる。
また、上記の実施例では、図４の構成及び図５、図６のフローチャートに基づいて説明したが、図４の構成及び図５、図６のステップをプログラムとして構築し、キャッシュサーバ性能値算出装置として利用されるコンピュータに接続されるディスク装置や、フロッピーディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、本発明を実施する際にインストールすることにより、容易に本発明を実現できる。
【００４６】
なお、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【００４７】
【発明の効果】
上述のように、本発明によれば、実際のリクエスト列に基づいて、少ない処理で、複数の異なる容量におけるキャッシュサーバの性能値を同時に算出することができる。
【図面の簡単な説明】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明のキャッシュサーバ性能値算出装置の接続構成図である。
【図４】本発明のキャッシュサーバ性能値算出装置の構成図である。
【図５】本発明のキャッシュサーバ性能値算出方法の処理手順のフローチャートである。
【図６】本発明のオブジェクト追い出し処理（Discard ）の手順のフローチャートである。
【図７】本発明の一実施例のリクエスト列の例である。
【図８】本発明の一実施例のキャッシュテーブルの遷移を示す図である。
【図９】本発明の一実施例のエンドポインタテーブルの遷移を示す図である。
【符号の説明】
１００  キャッシュサーバ性能値算出装置
１１０  オブジェクト判定手段、オブジェクト判定部
１２０  性能値計算手段、性能値計算部
１２１  計算部
１２２  追い出し処理部
１３０  キャッシュテーブル
１４０  エンドポインタテーブル
１５０  追い出し手段
１６０  ラベル設定手段
【図１】
0003788121.tif 000002
【図２】
0003788121.tif 000003
【図３】
0003788121.tif 000004
【図４】
0003788121.tif 000005
【図５】
0003788121.tif 000006
【図６】
0003788121.tif 000007
【図７】
0003788121.tif 000008
【図８】
0003788121.tif 000009
【図９】
0003788121.tif 000010