(57)【要約】【課題】  実稼動状態のＷｅｂサーバ１０のＷｅｂアプリケーションに係るセッション・データ・キャッシュ１２についてのヒット率を、オーバヘッドの増大を回避しつつ精確に推定する。【解決手段】  Ｗｅｂサーバ１０のカウンタより、所定Ｗｅｂアプリケーションに係るセッション・データ・キャッシュ１２に対して、退出確率ｐｌ，思考時間の平均値μ及び分散σ2，ヒット率ｒを算出する。時間的に近接する複数個のセッション・データ読出しから成る群の先頭の読出しについて、ｐｌα、μα、及びσ2αと、各群のセッション・データ読出しの個数の平均値αとを定義する。計算式設定手段２１は、αを変数とする不動点計算法の計算式であってｐｌ，μ，σ2，ｒ，ｐｌα，μα，σ2αを含む計算式ｆ（α）＝αを設定する。真値探索手段２２は、計算式ｆ（α）＝αに基づき不動点計算法によりαのほぼ真値を探索する。推定手段２３は、探索したαに基づきｒαを推定する。【選択図】      図４
2005149184.tif 000002
【特許請求の範囲】
【請求項１】
Ｗｅｂサーバが、各Ｗｅｂアプリケーションごとに所定サイズのセッション・データ・キャッシュを設定し、セッション・データ・キャッシュのセッション・データに対するキャッシュ・ヒットかキャッシュ・ミスかに応じて該セッション・データをそれぞれ前記セッション・データ・キャッシュ及び永続ストアから読出し、読出しデータに係る属性値について参照又は更新を行い、
１セッション当たりのセッション・データの読出し回数についての平均値の逆数としての退出確率をｐｌと定義し、同一セッション内の時間軸方向に相互に隣接するセッション・データ読出し間の時間間隔を思考時間と呼んで、思考時間の平均値及び分散をそれぞれμ及びσ2と定義し、並びにセッション・データ読出しに対するキャッシュ・ヒット率をｒと定義し、
該Ｗｅｂサーバは、ｐｌ，μ，σ2，ｒを算出可能とする所定の計数情報を計数する１個以上のカウンタを実装し、
同一セッション内の１個のＷｅｂページ送信リクエストに対応する１個以上のセッション・データ読出しをセッション・データ読出し群と呼び、またセッション・データ読出し群の中で先頭のセッション・データ読出しを群先頭読出しと呼ぶことにし、群先頭読出しのみについての前記セッション・データ・キャッシュにおけるヒット率ｒαを推定するヒット率推定装置において、
群先頭読出しのみについて、退出確率ｐｌα、思考時間の平均値μα、及び思考時間の分散σ2αを定義し、セッション・データ読出し群に含まれるセッション・データ読出しの個数の平均値をαと定義し、αを変数とする不動点計算法の計算式であってｐｌ，μ，σ2，ｒ，ｐｌα，μα，σ2αを含む計算式ｆ（α）＝α（ただし、左辺のαは元値を代入するα、右辺のαは左辺の計算により算出された新規値としてのα）を設定する計算式設定手段、
前記計算式ｆ（α）＝αに基づき不動点計算法によりαのほぼ真値を探索する真値探索手段、及び
探索したαに基づきｒαを推定する推定手段、
を有していることを特徴とするヒット率推定装置。
【請求項２】
前記計算式設定手段の設定する計算式ｆ（α）＝αは、ｐｌ，μ，σ2をαの元値に基づきｐｌα，μα，σ2αへ変換する第１の計算式、ｐｌα，μα，σ2αに基づき先頭呼出しのみについてのヒット率ｒαを求める第２の計算式、ｒαと観測したｒとの関係からαの新規値を計算する第３の計算式を基礎としており、
前記真値探索手段は、
αの元値入力に伴い第１の計算式に基づく計算を実施する第１の計算手段、
前記第１の計算手段からのｐｌα，μα，σ2αの入力に伴い第２の計算式に基づく計算を実施する第２の計算手段、
前記第２の計算手段からのｒαの入力に伴い第３の計算式に基づく計算を実施する第３の計算手段、
αの新規値がαのほぼ真値であると認めるか否かを判定する判定手段、
判定結果が「正」であれば、αの新規値を前記真値探索手段の出力とする出力生成手段、及び
判定結果が「否」であれば、αの新規値をαの元値として前記第１の計算手段へ付与する元値付与手段、
を有していることを特徴とする請求項１記載のヒット率推定装置。
【請求項３】
前記判定手段は、αの元値と新規値との差の絶対値が所定値未満であるとき及び所定値以上であるとき、それぞれ「正」及び「否」と判定することを特徴とする請求項２記載のヒット率推定装置。
【請求項４】
前記第１の計算手段は、αの最初の元値は予め決められた初期値とすることにし、
前記第２の計算手段は、前記Ｗｅｂサーバのセッション・データ・キャッシュの仕組みをシミュレーションしてαの新規値を求めるシミュレーション手段を含むことを特徴とする請求項２記載のヒット率推定装置。
【請求項５】
前記Ｗｅｂサーバは、ユーザが該Ｗｅｂサーバに訪れる時間間隔についての時間間隔用確率分布と、ユーザが、Ｗｅｂサーバに対して明示的なログ・アウトを通知して来る確率ＰIとを算出可能とする計数情報を計数する１個以上のカウンタを実装し、
前記シミュレーション手段は、
前記時間間隔用確率分布に基づいてトリガを発生するトリガ手段、
トリガに基づき模擬セッションを開始し各模擬セッションはμα，σ2αに基づく確率分布と、ｐｌαと、ＰIとに基づいてセッション・データ読出しを模擬するユーザ模擬手段、
前記ユーザ模擬手段におけるセッション・データ読出しについてのキャッシュ・ヒットを観測する観測手段、及び
前記観測手段の観測に基づきシミュレーション期間のｒαを出力する観測ヒット率出力手段、
を含むことを特徴とする請求項４記載のヒット率推定装置。
【請求項６】
前記ユーザ模擬手段は、各セッションにおいてセッション・データ読出しする回数をマルコフ・モデルで定義するものであることを特徴とする請求項５記載のヒット率推定装置。
【請求項７】
Ｗｅｂサーバが、各Ｗｅｂアプリケーションごとに所定サイズのセッション・データ・キャッシュを設定し、セッション・データ・キャッシュのセッション・データに対するキャッシュ・ヒットかキャッシュ・ミスかに応じて該セッション・データをそれぞれ前記セッション・データ・キャッシュ及び永続ストアから読出し、読出しデータに係る属性値について参照又は更新を行い、
１セッション当たりのセッション・データの読出し回数についての平均値の逆数としての退出確率をｐｌと定義し、同一セッション内の時間軸方向に相互に隣接するセッション・データ読出し間の時間間隔を思考時間と呼んで、思考時間の平均値及び分散をそれぞれμ及びσ2と定義し、並びにセッション・データ読出しに対するキャッシュ・ヒット率をｒと定義し、
該Ｗｅｂサーバは、ｐｌ，μ，σ2，ｒを算出可能とする所定の計数情報を計数する１個以上のカウンタを実装し、
同一セッション内の１個のＷｅｂページ送信リクエストに対応する１個以上のセッション・データ読出しをセッション・データ読出し群と呼び、またセッション・データ読出し群の中で先頭のセッション・データ読出しを群先頭読出しと呼ぶことにし、群先頭読出しのみについての前記セッション・データ・キャッシュにおけるヒット率ｒαを推定するヒット率推定方法において、
群先頭読出しのみについて、退出確率ｐｌα、思考時間の平均値μα、及び思考時間の分散σ2αを定義し、セッション・データ読出し群に含まれるセッション・データ読出しの個数の平均値をαと定義し、αを変数とする不動点計算法の計算式であってｐｌ，μ，σ2，ｒ，ｐｌα，μα，σ2αを含む計算式ｆ（α）＝α（ただし、左辺のαは元値を代入するα、右辺のαは左辺の計算により算出された新規値としてのα）を設定する第１のステップ、
前記計算式ｆ（α）＝αに基づき不動点計算法によりαのほぼ真値を探索する第２のステップ、及び
探索したαに基づきｒαを推定する第３のステップ、
を有していることを特徴とするヒット率推定方法。
【請求項８】
前記第１のステップにおいて設定する計算式ｆ（α）＝αは、ｐｌ，μ，σ2をαの元値に基づきｐｌα，μα，σ2αへ変換する第１の計算式、ｐｌα，μα，σ2αに基づき先頭呼出しのみについてのヒット率ｒαを求める第２の計算式、ｒαと観測したｒとの関係からαの新規値を計算する第３の計算式を基礎としており、
前記第２のステップは、
αの元値入力に伴い第１の計算式に基づく計算を実施する第１のサブステップ、
前記第１のサブステップからのｐｌα，μα，σ2αの入力に伴い第２の計算式に基づく計算を実施する第２のサブステップ、
前記第２のサブステップからのｒαの入力に伴い第３の計算式に基づく計算を実施する第３のサブステップ、
αの新規値がαのほぼ真値であると認めるか否かを判定する第４のサブステップ、
判定結果が「正」であれば、αの新規値を前記第２のステップの出力とする第５のサブステップ、及び
判定結果が「否」であれば、αの新規値をαの元値として前記第１のサブステップへ付与する第６のサブステップ、
を有していることを特徴とする請求項７記載のヒット率推定方法。
【請求項９】
前記第４のサブステップでは、αの元値と新規値との差の絶対値が所定値未満であるとき及び所定値以上であるとき、それぞれ「正」及び「否」と判定することを特徴とする請求項８記載のヒット率推定方法。
【請求項１０】
前記第１のサブステップでは、αの最初の元値は予め決められた初期値とすることにし、
前記第２のサブステップは、前記Ｗｅｂサーバのセッション・データ・キャッシュの仕組みをシミュレーションしてαの新規値を算出するシミュレーション・ステップを含むことを特徴とする請求項８記載のヒット率推定方法。
【請求項１１】
前記Ｗｅｂサーバは、ユーザが該Ｗｅｂサーバに訪れる時間間隔についての時間間隔用確率分布と、ユーザが、Ｗｅｂサーバに対して明示的なログ・アウトを通知して来る確率ＰIとを算出可能とする計数情報を計数する１個以上のカウンタを実装し、
前記シミュレーション・ステップは、
時間間隔用確率分布に基づいてトリガを発生するサブステップ、
トリガに基づき模擬セッションを開始し各模擬セッションはμα，σ2αに基づく確率分布と、ｐｌαと、ＰIとに基づいてセッション・データ読出しを模擬するサブステップ、
セッション・データ読出しの模擬におけるセッション・データ読出しについてのキャッシュ・ヒットを観測した結果に基づきシミュレーション期間のｒαを出力するサブステップ、
を含むことを特徴とする請求項１０記載のヒット率推定方法。
【請求項１２】
セッション・データ読出しの模擬に係るサブステップでは、各セッションにおいてセッション・データ読出しする回数をマルコフ・モデルで定義するものであることを特徴とする請求項１１記載のヒット率推定方法。
【請求項１３】
請求項７〜１２のいずれかに記載のヒット率推定方法の各ステップをコンピュータに実行させるためのヒット率推定プログラム。
【請求項１４】
請求項１３記載のヒット率推定プログラムをコンピュータに読取り自在に記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュを装備するＷｅｂサーバにおいてクライアントからのＷｅｂページ送信リクエストに対するキャッシュのヒット率に係る情報を推定するヒット率推定装置、ヒット率推定方法、ヒット率推定プログラム及び記録媒体に係り、詳しくはＷｅｂサーバを稼動させたままかつオーバヘッドを抑制しつつＷｅｂページ送信リクエストに対するキャッシュのヒット率に係る情報を推定するヒット率推定装置、ヒット率推定方法、ヒット率推定プログラム及び記録媒体に関するものである。
【背景技術】
【０００２】
ＩＢＭ社のＷｅｂサーバ（Websphere Application Server。以下、「ＩＢＭ社Ｗｅｂサーバ」という。」）では、ＨＴＴＰセッションのデータに永続性を持たせるために、データベース、JMS( Java Message Service )サーバを外部記憶装置と定義して利用し、Ｗｅｂアプリケーションごとに用意されたセッション・データ・キャッシュを通してセッション・データの読出しを行っている。サーバの性能を向上させるためには各Ｗｅｂアプリケーションに対するセッション・データ・キャッシュのサイズを適切な大きさに設定することが必要であるが、Ｗｅｂアプリケーションに対するＨＴＴＰリクエストの到着パターンにより最適なサイズは異なる。そこで、ＩＢＭ社Ｗｅｂサーバが保持している性能に関する統計量（PMI Data Counter）を利用して、キャッシュ・サイズを変更した場合のキャッシュ・ヒット率を推定し、適切なキャッシュ・サイズを求めたい。しかし、ＨＴＴＰセッション・データの参照又は更新のパターンには局所性があり、ＰＭＩ( Performance Measurement infrastructue )データ・カウンタ（PMI Data Counter）の統計量をそのまま利用したのでは実際のヒット率を過小評価することになり、正しい評価ができないことが問題であった。
【０００３】
キャッシュのヒット率を評価する方法の研究の歴史は長く、解析的な手法からシミュレーションによる手法まで多くの方法が存在する。入力の到着パターンに関しても、独立な確率に従って生起するものから依存関係にある分布を示すものなど局所性を扱ったものも多数存在する。しかしながら、実システムのヒット率を評価するにあたっては詳細なデータを取得して事後的に分析している。サーバ・システムのように、実稼動中に詳細なデータを取得することがオーバヘッドになり現実的に不可能な場合には、これらの方法を適用することは難しい。
【０００４】
特許文献１の装置は、サーバのキャッシュではなく、ＣＰＵと主記憶装置との間に介在するキャッシュに関する。特許文献１のコンピュータでは、ジョブ実行時にアプリケーションがヒット率を知ることができるようにし、アプリケーション自らが、ヒット率を最大となるように、キャッシュの方式選択（ダイレクト・マップ／セット・アソシアティブ）及びキャッシュ・ライン・サイズを設定できるようにしている。
【０００５】
特許文献２の装置は、サーバのキャッシュにおいて、出現数に係る経験式ｆ（ｘ）が所定の特徴パラメータを含み、キャッシュの全サイズの内で実際に使用されているサイズ及びセッション・データのエントリ数を所定時間間隔で記録して、その記録に基づき出現順位ｘと該ｘに対応する出現数ｆ（ｘ）の値を求め、求めたｆ（ｘ）の値に基づいて所定の特徴パラメータを検出し、特徴パラメータからキャッシュ・ヒット率及びエントリ数Ｓを推定し、さらに、推定したキャッシュ・ヒット率及びＳに基づき適切なキャッシュ・サイズを算出している。
【０００６】
特許文献３の装置は、サーバのキャッシュではなく、ＣＰＵと主記憶装置との間に介在するキャッシュに関する。特許文献３の装置では、アプリケーションの実行中、キャッシュのブロック・サイズを仮想的に変化させて、ヒット数を算出し、該ヒット数に基づきデータ転送のサイズを決定することにし、キャッシュのヒット率を改善している。
【０００７】
特許文献４の装置は、サーバのキャッシュではなく、ＣＰＵと主記憶装置との間に介在するキャッシュに関する。特許文献４は、キャッシュ・ヒット率を考慮して、評価対象のプログラムの総実行クロック数を求めることを開示する。
【特許文献１】特開平５−２２５０６０号公報
【特許文献２】特開２０００−１５５７１３公報
【特許文献３】特開２０００−２５０８０９公報
【特許文献４】特開平１０−１３３９０２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ＩＢＭ社Ｗｅｂサーバでは、クラスター構成の場合に１つのサーバがダウンしても、そのサーバが処理していたセッションを他のサーバが肩代わりできるように、ＨＴＴＰセッションのデータに永続性を持たせている。そのための外部記憶装置と定義して、データベース、ＪＭＳサーバ等を利用し、各サーバではＷｅｂアプリケーションごとに用意されたセッション・データ・キャッシュを通してセッション・データの参照、更新を行っている。
【０００９】
なお、セッション・データには属性と値とのペアの集合が入っている（例えば、ユーザＩＤとその値）。参照とはその属性値の参照で、更新とはその属性値の更新のことである。しかし、セッション・データそのものはそれらの属性の集合の入れ物であるから、参照と更新のどちらにしても、まずはセッション・データそのものを取り出してこなければならないので、キャッシュにとっては同じことになる。すなわち、getSession()というメソッドでセッション・データを取り出すのであるが、そのときにキャッシュにヒットするかどうかが問題であって、取り出した後のセッション・データの内容を参照するか更新するかはキャッシュには関係してこない。
【００１０】
サーバの性能を向上させるためにはキャッシュ・サイズを適切な大きさに設定することが必要であるが、Ｗｅｂアプリケーションに対するＨＴＴＰリクエストの到着パターンにより最適なサイズは異なるため、アプリケーションの構造だけでなく運用時のアクセス・パターンに基づいて最適なサイズを決定しなければならない。
【００１１】
詳細なアクセス・パターンのログがあれば、その特徴を解析して、キャッシュ・サイズを変更した場合のキャッシュ・ヒット率等の性能指標を求めることは、シミュレーションを利用すれば比較的容易であるが、運用時に詳細なログをとることは大きなオーバヘッドとなり事実上不可能である。一方で、ＩＢＭ社Ｗｅｂサーバには運用時の性能指標のデータ収集機能と定義してPMIがあり、比較的少ない（標準設定で２％程度）オーバヘッドで各種の統計量（PMI Data Counter）を保持している。このＰＭＩデータ・カウンタからキャッシュ・ヒット率が正確に評価可能であれば、運用時のアクセス・パターンを反映評価が可能となる。
【００１２】
PMIのセッションに関する統計量には、セッション・データの読出しの回数、時間間隔の平均、分散が含まれている。しかし、セッション・データの読出しは１つのＨＴＴＰリクエストに対して１度だけ起こるわけではなく、サーブレット（Servlet）が他のサーブレットやJSPを呼び出す場合には複数回のセッション・データ読出しが起こる可能性があり、それらの時間間隔は非常に短い。したがって、測定される時間間隔には大きな偏りがあり、PMIが保持している平均値及び分散をそのまま利用したのでは正しい評価を得ることは難しい。さらに特定のＨＴＴＰリクエストに注目しても読出し回数はデータに依存しており、サーブレットやJSPを解析してもセッション・データの読出し回数が実行時にしか分からない場合もある。
【００１３】
したがって、ＰＭＩデータ・カウンタのような比較的オーバヘッドの少ない統計量を用いて、セッション・データに関するキャッシュ・ヒット率等の性能指標をできるだけ正確に評価することが課題である。
【００１４】
特許文献１，３の装置はヒット率又はヒット数を検出するが、そのヒット率又はヒット数は、全部のセッション・データ読出しに対するヒット率であり、１個のＨＴＴＰリクエストに対して複数個のセッション・データ読出しが生じる場合に、最初のセッション・データ読出しについてのみのヒット率を、オーバヘッドを抑制しつつ、検出することはできない。
【００１５】
特許文献２の装置は、適切なキャッシュ・サイズを算出するものであるが、出現数に係る経験式を必須と定義しており、各Ｗｅｂページ送信リクエストに対する最初のセッション・データ読出しのみについてのヒット率を、オーバヘッドを抑制して、検出する場合への適用は困難である。
【００１６】
特許文献４は、キャッシュ・ヒット率について言及するものの、各ＨＴＴＰリクエストに対する最初のセッション・データ読出しのみについてのヒット率をいかに検出するかについては一切関知していない。
【００１７】
本発明の目的は、実稼動状態のＷｅｂサーバにおいて所定Ｗｅｂアプリケーションに係るキャッシュについてのヒット率に係る情報を、オーバヘッドの増大を回避しつつ、精確に推定するヒット率推定装置、ヒット率推定方法、ヒット率推定プログラム及び記録媒体を提供することである。
【課題を解決するための手段】
【００１８】
本発明のヒット率推定装置によれば、Ｗｅｂサーバが、各Ｗｅｂアプリケーションごとに所定サイズのセッション・データ・キャッシュを設定し、セッション・データ・キャッシュのセッション・データに対するキャッシュ・ヒットかキャッシュ・ミスかに応じて該セッション・データをそれぞれセッション・データ・キャッシュ及び永続ストアから読出し、読出しデータに係る属性値について参照又は更新を行う。１セッション当たりのセッション・データの読出し回数についての平均値の逆数としての退出確率をｐｌと定義し、同一セッション内の時間軸方向に相互に隣接するセッション・データ読出し間の時間間隔を思考時間と呼んで、思考時間の平均値及び分散をそれぞれμ及びσ2と定義し、並びにセッション・データ読出しに対するキャッシュ・ヒット率をｒと定義する。該Ｗｅｂサーバは、ｐｌ，μ，σ2，ｒを算出可能とする所定の計数情報を計数する１個以上のカウンタを実装している。同一セッション内の１個のＷｅｂページ送信リクエストに対応する１個以上のセッション・データ読出しをセッション・データ読出し群と呼び、またセッション・データ読出し群の中で先頭のセッション・データ読出しを群先頭読出しと呼ぶことにする。該ヒット率推定装置は、群先頭読出しのみについてのキャッシュにおけるヒット率ｒαを推定する。該ヒット率推定装置は次のものを有している。
群先頭読出しのみについて、退出確率ｐｌα、思考時間の平均値μα、及び思考時間の分散σ2αを定義し、セッション・データ読出し群に含まれるセッション・データ読出しの個数の平均値をαと定義し、αを変数とする不動点計算法の計算式であってｐｌ，μ，σ2，ｒ，ｐｌα，μα，σ2αを含む計算式ｆ（α）＝α（ただし、左辺のαは元値を代入するα、右辺のαは左辺の計算により算出された新規値としてのα）を設定する計算式設定手段、
計算式ｆ（α）＝αに基づき不動点計算法によりαのほぼ真値を探索する真値探索手段、及び
探索したαに基づきｒαを推定する推定手段。
【００１９】
本発明のヒット率推定方法によれば、Ｗｅｂサーバが、各Ｗｅｂアプリケーションごとに所定サイズのセッション・データ・キャッシュを設定し、セッション・データ・キャッシュのセッション・データに対するキャッシュ・ヒットかキャッシュ・ミスかに応じて該セッション・データをそれぞれセッション・データ・キャッシュ及び永続ストアから読出し、読出しデータに係る属性値について参照又は更新を行う。１セッション当たりのセッション・データの読出し回数についての平均値の逆数としての退出確率をｐｌと定義し、同一セッション内の時間軸方向に相互に隣接するセッション・データ読出し間の時間間隔を思考時間と呼んで、思考時間の平均値及び分散をそれぞれμ及びσ2と定義し、並びにセッション・データ読出しに対するキャッシュ・ヒット率をｒと定義する。該Ｗｅｂサーバは、ｐｌ，μ，σ2，ｒを算出可能とする所定の計数情報を計数する１個以上のカウンタを実装している。同一セッション内の１個のＷｅｂページ送信リクエストに対応する１個以上のセッション・データ読出しをセッション・データ読出し群と呼び、またセッション・データ読出し群の中で先頭のセッション・データ読出しを群先頭読出しと呼ぶことにする。該ヒット率推定方法では、群先頭読出しのみについてのキャッシュにおけるヒット率ｒαを推定する。そして、該ヒット率推定方法は次のステップを有している。
群先頭読出しのみについて、退出確率ｐｌα、思考時間の平均値μα、及び思考時間の分散σ2αを定義し、セッション・データ読出し群に含まれるセッション・データ読出しの個数の平均値をαと定義し、αを変数とする不動点計算法の計算式であってｐｌ，μ，σ2，ｒ，ｐｌα，μα，σ2αを含む計算式ｆ（α）＝α（ただし、左辺のαは元値を代入するα、右辺のαは左辺の計算により算出された新規値としてのα）を設定する第１のステップ、
計算式ｆ（α）＝αに基づき不動点計算法によりαのほぼ真値を探索する第２のステップ、及び
探索したαに基づきｒαを推定する第３のステップ。
【００２０】
本発明のヒット率推定プログラムは、前述のヒット率推定方法及び後述の実施の形態に係るヒット率推定方法の各ステップをコンピュータに実行させる。又は、本発明のヒット率推定プログラムは、前述のヒット率推定装置及び後述の実施の形態に係るヒット率推定装置の各手段としてコンピュータを機能させるものであってもよい。本発明の記録媒体は、かかるプログラムをコンピュータ読み取り可能に記録したものである。
【発明の効果】
【００２１】
本発明によれば、群先頭読出しについてのみのヒット率を導入し、ｐｌ，μ，σ2，ｒ，ｐｌα，μα，σ2αから計算式ｆ（α）＝α（ただし、左辺のαは元値を代入するα、右辺のαは左辺の計算により算出された新規値としてのα）を用いて、αを不動点計算法により求める。これにより、Ｗｅｂアプリケーションに対する精確なヒット率及び適切なキャッシュ・サイズを検出可能となる。そして、群先頭読出しに係るヒット率を計測するカウンタを設置することなく、全部のセッション・データ読出しに対するヒット率を算出可能とするカウンタを用いるので、オーバヘッドを小さくすることができる。
【発明を実施するための最良の形態】
【００２２】
図１はネットワークで接続されている所定Ｗｅｂサーバ１０と複数のクライアント１１，１１，・・・との関係を示す図である。このＷｅｂサーバ１０は、Ｗｅｂアプリケーションごとに所定サイズで割当てられているセッション・データ・キャッシュ１２を内部に装備するとともに、また、データベースやＪＭＳサーバ等から成る永続ストア１３を外部記憶装置と定義して有している。Ｗｅｂサーバ１０は、インターネット１５を介して複数のクライアント１１，１１，・・・からＷｅｂページ送信リクエストとしてのＨＴＴＰリクエストを受け付け、受け付けたＨＴＴＰリクエストに対応するＷｅｂページ表示用ファイルとしてのＨＴＭＬファイルを、ＨＴＴＰリクエストを発行したクライアント１１，１１，・・・へ送信するようになっている。Ｗｅｂサーバ１０は、ＨＴＭＬファイルの作成に必要とするセッション・データを、原則的にはセッション・データ・キャッシュ１２から読出し、キャッシュ・ミスのときのみ永続ストア１３から読出すようにしている。永続ストア１３は、インターネット１５を介してＷｅｂサーバ１０へ接続されていてもよい。
【００２３】
ＨＴＴＰセッション・データの読出しの局所性は、サーブレットが他のサーブレットやJSPを呼び出したり、JSPが他のJSPの出力を取り込んだりすることで、１度のＨＴＴＰリクエストの中で何度もセッション・データ読出しを行うことにより生じる。一方、ＰＭＩデータ・カウンタはこれらを独立のセッション・データ読出しと定義してモニターして、統計量を計算している。そこで、この局所性（１つのＨＴＴＰリクエストに対していくつの参照又は更新が続けて呼び出されるか）を表現するパラメータ（locality factor。後述の局所性因子α）を導入し、ＰＭＩデータ・カウンタ（PMI Data Counter）の統計量を適切に変換することにより、正しいキャッシュのヒット率を求める。また、局所性因子（locality factor）は実行時にしか分からない場合があるので、ＰＭＩデータ・カウンタから求めた現状のヒット率を利用して、局所性因子を周知の不動点計算方法で推定する。なお、不動点計算方法とは、ｆ（ｘ）＝ｘ（ただし、左辺のｘは元値を代入するｘ、右辺のｘは左辺の計算により算出された新規値としてのｘ）を定義して、ｘの近似値を求める計算法のことである。
【００２４】
図２は１回のセッションにおけるセッション・データ読出し命令（＝セッション・データ読出しの実行）の時間分布を示している。セッション・データ読出しの分布には局所性がある。１個のセッション中、１個のＷｅｂページ送信リクエストとしての１個のＨＴＴＰリクエストに対して１個以上のセッション・データ読出しが発行され、同一のＨＴＴＰリクエストに対応する複数個のセッション・データ読出しは時間間隔が短く、時間的な密なセッション・データ読出し同士はセッション・データ読出し群Ｇ１，Ｇ２，Ｇ３，・・・を構成する。図２では、各セッション・データ読出し群において、１番目のセッション・データ読出しはＯ1で、また、２番目以降のセッション・データ読出しはＯ2で示している。図２の例では、各セッション・データ読出し群Ｇ１，Ｇ２，Ｇ３，Ｇ４におけるαg（＝Ｏ1の個数＋Ｏ2の個数）は、それぞれ３，４，３，２となっている。
【００２５】
セッション・データへの参照又は更新のパターン（＝セッション・データ読出し命令のパターン＝セッション・データ読出し実行のパターン）に見かけられる局所性は、ＨＴＴＰリクエストの到着する時間間隔の中に非常に短い時間間隔が複数回続くという特徴を持っている。このようなセッション・データ読出しパターンでは、ほぼ同時に発行されるセッション・データ読出しの列の中で２番目以降のセッション・データ読出しＯ2に関してはセッション・データ・キャッシュ１２に必ずセッション・データがあると考えてよいので、これらのヒット率は１００％とみなせる。そこで、これら２番目以降のセッション・データ読出しＯ2を一時的に無視して、セッション・データ読出しパターンと定義して１番目のセッション・データ読出しＯ1のみを対象とすれば、時間間隔の分布にあった極端な偏りはかなり減らすことができる。キャッシュの交換アルゴリズム（Replacement Algorithm）が参照頻度を利用している場合(Least Frequently Used (LFU)最小頻度参照ページ追い出し)はこの限りではないが、現実にＩＢＭ社Ｗｅｂサーバでは、単純なLeast Recently Used (LRU：最旧参照ページ追い出し)方式を使っているので、２番目以降を無視しても、１番目のセッション・データ読出しＯ1のヒット率が変わることはない。
【００２６】
αgの平均値をαと定義する。PMIでは２番目以降のセッション・データ読出しＯ2も含んだ統計量を保持しているが、１番目のセッション・データ読出しＯ1のみを対象と定義した解析を行うためには、局所性因子に応じて統計量を変換する必要がある。１番目のセッション・データ読出しＯ1の時間間隔は１人のユーザのＨＴＴＰリクエストの時間間隔と同じであるからそれを思考時間（think time）と呼ぶことにし、また、そのユーザがＷｅｂアプリケーションを１回のセッション内に訪れる平均訪問回数の逆数を退出確率（leave probability）とすると、局所性因子αを導入することにより、以下のようなパラメータ変換Ｆαが必要である。なお、ｐｌ，μ，σ2は、１セッション内の全セッション・データ読出しについての退出確率、思考時間の平均値及び分散であり、ｐｌα，μα，σ2αは、１セッション内の先頭セッション・データ読出しについてのみの退出確率、思考時間の平均値及び分散である。
μα＝α・μ・・・（１）
σ2α＝α・（σ2＋μ2）−μ2α・・・（２）
ｐｌα＝α・ｐｌ・・・（３）
【００２７】
このパラメータ変換Ｆαを施した新しいパラメータにより求められる１番目のセッション・データ読出しＯ1のキャッシュ・ヒット率ｒαと、すべてのセッション・データ読出しＯ1，Ｏ2を考慮した場合のキャッシュ・ヒット率ｒとには、次の関係がある。
１−ｒα＝α・（１−ｒ）・・・（４）
【００２８】
この関係から一時的に無視した２番目以降のセッション・データ読出しＯ2も含んだキャッシュ・ヒット率ｒを計算することができる。図３はパラメータ変換Ｆαによるｒαと観測によるｒとが関係式により規定されることを示す説明図である。図３の説明図と不動点計算法との関係を説明すると、ここで、不動点計算で求めるのはαであるから、αの関数と定義して新しいαを計算する手順を考える。左上から右回りにｒαを求める関数をsimulation( Ｆα(μ，σ2，ｐｌ))とする。これと観測値のｒから上述（４）の関係式を利用して新しいαとしてのα’を求めると、図３の（５）式となる。左辺をαの関数だとみなせば、正しいαを求めるには、不動点計算法の式ｆ(α)＝αとなるような計算をすればいいことになる。
【００２９】
図３から、局所性因子が既知である場合には、局所性因子により任意のキャッシュ・サイズに対するヒット率を評価することが可能になる。しかし、局所性因子が実行時にしか決まらない場合もあり、その場合にはなんらかの方法で局所性因子を推定できれば適用範囲を広げることができる。
【００３０】
ＰＭＩデータ・カウンタから現状でのヒット率を知ることができるので、このことを利用して局所性因子を推定することができる。適当な局所性因子αの初期値（例えば１）からｒαを計算し、上図の関係を用いて、ｒαとｒからαの新規値を求める。この手順を以下の手順１と定義して示す。手順１では、αの値が収束するまで繰り返し、局所性因子αを推定する。
【００３１】
（手順１）
10:Set α, αnew = 1 // start from 1.0
11:Do {
12:  α = αnew
13:  Simulation → rα
14:  αnew = (1 - rα)/(1 - ractual)
15:} while ( | α - αnew | > ε )
【００３２】
図４はヒット率推定装置２０の機能ブロック図である。Ｗｅｂサーバ１０は、各Ｗｅｂアプリケーションごとに所定サイズのセッション・データ・キャッシュを設定し、セッション・データ・キャッシュのセッション・データに対するキャッシュ・ヒットかキャッシュ・ミスかに応じて該セッション・データをそれぞれセッション・データ・キャッシュ及び永続ストア１３から読出し、読出しデータに係る属性値について参照又は更新を行う。ここで、１セッション当たりのセッション・データの読出し回数についての平均値の逆数としての退出確率をｐｌと定義し、同一セッション内の時間軸方向に相互に隣接するセッション・データ読出し間の時間間隔を思考時間と呼んで、思考時間の平均値及び分散をそれぞれμ及びσ2と定義し、並びにセッション・データ読出しに対するキャッシュ・ヒット率をｒと定義する。該Ｗｅｂサーバ１０は、ｐｌ，μ，σ2，ｒを算出可能とする所定の計数情報を計数する１個以上のカウンタを実装する。同一セッション内の１個のＷｅｂページ送信リクエストに対応する１個以上のセッション・データ読出しをセッション・データ読出し群と呼び、またセッション・データ読出し群の中で先頭のセッション・データ読出しを群先頭読出しと呼ぶことにする。ヒット率推定装置２０は、群先頭読出しのみについてのセッション・データ・キャッシュ１２におけるヒット率ｒαを推定する。ヒット率推定装置２０は、計算式設定手段２１、真値探索手段２２、及び推定手段２３を有している。群先頭読出しのみについて、退出確率ｐｌα、思考時間の平均値μα、及び思考時間の分散σ2αを定義し、セッション・データ読出し群に含まれるセッション・データ読出しの個数の平均値をαとする。計算式設定手段２１は、αを変数とする不動点計算法の計算式であってｐｌ，μ，σ2，ｒ，ｐｌα，μα，σ2αを含む計算式ｆ（α）＝α（ただし、左辺のαは元値を代入するα、右辺のαは左辺の計算により算出された新規値としてのα）を設定する。真値探索手段２２は、計算式ｆ（α）＝αに基づき不動点計算法によりαのほぼ真値を探索する。推定手段２３は、探索したαに基づきｒαを推定する。
【００３３】
群先頭呼出しのみについてのみのキャッシュ・ヒットを直接観測するためのカウンタを実装することは、オーバヘッドを増大させるのに対し、このヒット率推定装置２０は、全部のセッション・データ読出しに係るｐｌ，μ，σ2，ｒを得るためのカウンタを実装するのみであるので、オーバヘッドの増大は抑制される。また、局所性因子αの導入、及びｐｌ，μ，σ2，ｒ，ｐｌα，μα，σ2αを含む不動点計算用計算式ｆ（α）＝αを用いてのαの探索により、適切なｒαを推定することが可能になる。結果、ＷｅｂサーバにおけるＷｅｂアプリケーションに係るセッション・データ・キャッシュ１２について、その適切なサイズを求めることができる。
【００３４】
ヒット率推定装置２０を任意に具体化した態様について、図５及び図６を参照しつつ、説明する。以下の個々の具体的構成は、任意の組み合わせで図４のヒット率推定装置２０に付加可能になっている。
【００３５】
図５は真値探索手段２２の詳細な機能ブロック図である。計算式設定手段２１の設定する計算式ｆ（α）＝αは、ｐｌ，μ，σ2をαの元値に基づきｐｌα，μα，σ2αへ変換する第１の計算式、ｐｌα，μα，σ2αに基づき先頭呼出しのみについてのヒット率ｒαを求める第２の計算式、ｒαと観測したｒとの関係からαの新規値を計算する第３の計算式を基礎と定義している。真値探索手段２２は、第１の計算手段２８、第２の計算手段２９、第３の計算手段３０、判定手段３１、出力生成手段３２、及び元値付与手段３３を有している。第１の計算手段２８は、αの元値入力に伴い第１の計算式に基づく計算を実施する。第２の計算手段２９は、第１の計算手段２８からのｐｌα，μα，σ2αの入力に伴い第２の計算式に基づく計算を実施する。第３の計算手段３０は、第２の計算手段２９からのｒαの入力に伴い第３の計算式に基づく計算を実施する。判定手段３１は、αの新規値がαのほぼ真値であると認めるか否かを判定する。出力生成手段３２は、判定結果が「正」であれば、αの新規値を真値探索手段２２の出力とする。元値付与手段３３は、判定結果が「否」であれば、αの新規値をαの元値として第１の計算手段２８へ付与する。
【００３６】
判定手段３１は、αの元値と新規値との差の絶対値が所定値未満であるとき及び所定値以上であるとき、それぞれ「正」及び「否」と判定する。
【００３７】
第１の計算手段２８は、αの最初の元値は予め決められた初期値とすることにしている。第２の計算手段２９は、Ｗｅｂサーバ１０のセッション・データ・キャッシュの仕組みをシミュレーションして、αの新規値を求めるシミュレーション手段３７（図６）を含む。
【００３８】
図６はシミュレーション手段３７の詳細な機能ブロック図である。Ｗｅｂサーバ１０は、ユーザがＷｅｂサーバ１０に訪れる時間間隔についての確率分布（例えば正規分布のＮ（μ，σ2））、ユーザが、Ｗｅｂサーバ１０に対して明示的なログ・アウトを通知して来る確率ＰIとを算出可能とする計数情報を計数する１個以上のカウンタを実装している。シミュレーション手段３７は、トリガ手段３８、ユーザ模擬手段３９、観測手段４０、及び観測ヒット率出力手段４１を有している。トリガ手段３８は、時間間隔用確率分布に基づいてトリガを発生する。ユーザ模擬手段３９は、トリガに基づき模擬セッションを開始し各模擬セッションはμα，σ2αに基づく確率分布と、ｐｌαと、ＰIとに基づいてセッション・データ読出しを模擬する。観測手段４０は、ユーザ模擬手段におけるセッション・データ読出しについてのキャッシュ・ヒットを観測する。観測ヒット率出力手段４１は、観測手段４０の観測に基づきシミュレーション期間のｒαを出力する。
【００３９】
ユーザ模擬手段３９は、各セッションにおいてセッション・データ読出しする回数をマルコフ・モデルで定義するものである。
【００４０】
図７はヒット率推定方法のフローチャートである。Ｓ４５では、群先頭読出しのみについて、退出確率ｐｌα、思考時間の平均値μα、及び思考時間の分散σ2αを定義し、セッション・データ読出し群に含まれるセッション・データ読出しの個数の平均値をαと定義し、αを変数とする不動点計算法の計算式であってｐｌ，μ，σ2，ｒ，ｐｌα，μα，σ2αを含む計算式ｆ（α）＝α（ただし、左辺のαは元値を代入するα、右辺のαは左辺の計算により算出された新規値としてのα）を設定する。Ｓ４６では、計算式ｆ（α）＝αに基づき不動点計算法によりαのほぼ真値を探索する。Ｓ４７では、探索したαに基づきｒαを推定する。
【００４１】
図７に係るヒット率推定方法の具体的態様を以下に説明する。以下の各具体的態様は、任意の組み合わせで付加するものであり、本発明を限定するものではない。
【００４２】
図８は図７の不動点計算法による探索ステップＳ４６の詳細図である。図７のＳ４５において設定する計算式ｆ（α）＝αは、ｐｌ，μ，σ2をαの元値に基づきｐｌα，μα，σ2αへ変換する第１の計算式、ｐｌα，μα，σ2αに基づき先頭呼出しのみについてのヒット率ｒαを求める第２の計算式、ｒαと観測したｒとの関係からαの新規値を計算する第３の計算式を基礎と定義している。図８において、Ｓ４６はＳ５２〜Ｓ５７を有している。Ｓ５２では、αの元値入力に伴い第１の計算式に基づく計算を実施する。Ｓ５３では、Ｓ５２からのｐｌα，μα，σ2αの入力に伴い第２の計算式に基づく計算を実施する。Ｓ５４では、Ｓ５３からのｒαの入力に伴い第３の計算式に基づく計算を実施する。Ｓ５５では、αの新規値がαのほぼ真値であると認めるか否かを判定する。判定結果が「正」であれば、Ｓ５６において、αの新規値をＳ４６の出力とする。また、Ｓ５５の判定結果が「否」であれば、Ｓ５７において、αの新規値をαの元値としてから、Ｓ５２へ戻る。
【００４３】
Ｓ５５は、αの元値と新規値との差の絶対値が所定値未満であるとき及び所定値以上であるとき、それぞれ「正」及び「否」と判定する。
【００４４】
Ｓ５２は、αの最初の元値は予め決められた初期値とすることにする。Ｓ５３は、Ｗｅｂサーバ１０のセッション・データ・キャッシュの仕組みをシミュレーションしてαの新規値を算出するシミュレーション・ステップ（図９〜図１１）を含む。
【００４５】
Ｗｅｂサーバは、ユーザが該Ｗｅｂサーバに訪れる時間間隔についての時間間隔用確率分布と、ユーザが、Ｗｅｂサーバに対して明示的なログ・アウトを通知して来る確率ＰIとを算出可能とする計数情報を計数する１個以上のカウンタを実装する。図９〜図１１はシミュレーション・ステップの具体的なフローチャートである。シミュレーション・ステップは例えばそれぞれ図９〜図１１に対応する３個のルーチンに分解される。図９及び図１１のフローチャートに係るルーチンは例えば時間割り込みにより実行される。図１０のフローチャートに係るルーチンは例えば図１０所定のトリガの発生に伴って実行される割り込みルーチンである。
【００４６】
図９において、Ｓ６１，Ｓ６２では、時間間隔用確率分布（例えば正規分布Ｎ（μ，σ2））に基づいてトリガを発生する。すなわち、Ｓ６１において、時間間隔用確率分布に基づき、トリガ発生時刻になったか否かを判定し、判定結果が「正」であれば、Ｓ６２において、トリガを発生する。このトリガは、図１０のルーチンの実行を引き起こす。
【００４７】
図１０のルーチンは、各模擬セッションごとに実行されるものであり、１個のシミュレーション全体では該シミュレーションにおけるセッション数だけ実行されることになる。該ルーチンでは、トリガに基づき模擬セッションを開始し、各模擬セッションはμα，σ2αに基づく確率分布と、ｐｌαと、ＰIとに基づいてセッション・データ読出しを模擬する。すなわち、Ｓ６５では、トリガに基づき模擬セッションを開始する。各模擬セッションはμα，σ2αに基づく確率分布と、ｐｌαと、ＰIとに基づいてセッション・データ読出しを模擬することとし、Ｓ６６では、該当の模擬セッションにおけるセッション・データ読出しを模擬する。Ｓ６７では、該当の模擬セッションを終了するか否かを判定する。
【００４８】
図１１のルーチンでは、セッション・データ読出しの模擬（Ｓ６５〜Ｓ６７）におけるセッション・データ読出しについてのキャッシュ・ヒットを観測した結果に基づきシミュレーション期間のｒαを出力する。すなわち、Ｓ７０では、例えば、シミュレーション時間が所定値に達したかや模擬セッションの実行回数が所定値に達したか等に基づき、今回のシミュレーションを終了するか否かを判定する。該判定結果が「正」であるときは、Ｓ７１において、ｒαを出力する。
【００４９】
セッション・データ読出しの模擬に係るＳ６６では、各セッションにおいてセッション・データ読出しする回数をマルコフ・モデルで定義するものである。
【００５０】
本発明は、ハードウェア、ソフトウェア、又はそれらの組み合わせと定義して実現可能である。ハードウェアとソフトウェアの組み合わせによる実行において、所定のプログラムを有するコンピュータ・システムにおける実行が典型的な例と定義して挙げられる。かかる場合、該所定プログラムが該コンピュータ・システムにロードされ実行されることにより、該プログラムは、コンピュータ・システムを制御し、本発明に係る処理を実行させる。このプログラムは、任意の言語・コード・表記によって表現可能な命令群から構成される。そのような命令群は、システムが特定の機能を直接、又は１．他の言語・コード・表記への変換、２．他の媒体への複製、のいずれか一方もしくは双方が行われた後に、実行することを可能にするものである。もちろん、本発明は、そのようなプログラム自体のみならず、プログラムを捕捉した媒体もその範囲に含むものである。本発明の機能を実行するためのプログラムは、フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ、ハード・ディスク装置、ＲＯＭ、ＭＲＡＭ、ＲＡＭ等の任意のコンピュータ読み取り可能な捕捉媒体に格納することができる。かかるプログラムは、捕捉媒体への格納のために、通信回線で接続する他のコンピュータ・システムからダウンロードしたり、他の捕捉媒体から複製したりすることができる。また、かかるプログラムは、圧縮し、又は複数に分割して、単一又は複数の捕捉媒体に格納することもできる。
【００５１】
図１２はプログラムを実行するためのハードウェア構成図である。前述したヒット率推定方法の各ステップ（サブステップを含む。）をコンピュータに実行させるためのヒット率推定プログラムは、例えば、図１２に記載したハードウェアを使用して、実行される。あるいは、前述したヒット率推定装置２０の各手段としてコンピュータを機能させるためのプログラムは、例えば図１２に記載したハードウェアを使用して、実行される。図１２において、システム・バス８０には、ＣＰＵ８１、主記憶装置８２及び入出力制御装置８３が接続される。前述した手段又はステップは、コード化されたプログラムと定義して実行可能となっている。入出力制御装置８３には、ハード・ディスク・インターフェース等が含まれ、ＣＰＵ８１が実行する各種プログラムはハード・ディスク装置等にストアされている。プログラムは、ＣＰＵ８１において実行されるのに先立ち、主記憶装置８２にストアされる。ＣＰＵ８１は、主記憶装置８２の命令行を順次、読出して、該プログラムを実行する。  
【実施例１】
【００５２】
図１３はキャッシュ構成アドバイザ（Cache Configuration Advisor）プロジェクトで、ＩＢＭ社Ｗｅｂサーバのセッション・キャッシュの大きさを最適化する目的に使用するために実装したヒット率推定装置９０の機能ブロック図である。このヒット率推定装置９０では、セッション・データ読出しパターンと実際のキャッシュの振る舞いをモデル化し、シミュレーションにより与えられたキャッシュ・サイズにおけるヒット率を求める機能を核と定義している。図１３に示すように３つのコンポーネント９１〜９３から構成され、コンポーネント９１，９２がセッション・データ読出しパターンをモデル化する部分で、コンポーネント９３がキャッシュの振る舞いをモデル化する部分である。コンポーネント９１，９２のパラメータを決定するためにPMIのデータを使用する。
【００５３】
トリガ発生器９１（Trigger）: 新しいユーザが訪れる時間間隔（triggerRate）を確率分布で定義している。確率分布と定義して例えば指数分布（μ1，σ1）を使用する。トリガ発生器９１において、１回のシミュレーションにおける最大イベントは１００，０００を想定している。
【００５４】
ユーザ・モデル（User Model）９２: １人のユーザがセッション・データを参照する回数（Ｗｅｂページを閲覧する回数と考えてもよい。）の逆数としての退出確率（leaveProb）を簡単なマルコフ・モデルで、参照の時間間隔としての思考時間（thinkTime）を確率分布（例えば正規分布（μ2，σ2）を使用する）で定義している。また、Ｗｅｂサイトを去るときに、セッション・データを陽に無効化する（ログアウト（logout）に相当する）確率（invalidateProb）も与える。なお、無効化する確率は、条件付確率で、ユーザがＷｅｂサイトを去る場合に陽にログ・アウトをする割合を表しており、無効化する集合は立ち去る集合に完全に包含されている。また、陽に無効化するとは、ログ・アウトのリンク（もしあれば）を押すことである。銀行のオンラインなどのログ・イン（log in）する必要があるアプリケーションの場合にはログ・アウトのリンクがあるが、一般にはログ・アウトのリンクはないのでほとんどの場合は陽に無効化することなくユーザは別のＷｅｂページへ行ってしまう。ユーザ・モデルにおいて、退出確率Ｐは０．１を、また、無効化確率ＰIは０．５を、それぞれ想定している。
【００５５】
ＬＲＵキャッシュ（LRU Cache）９３: LRUをreplacement algorithmとするセッションデータのキャッシュをモデル化している。ＬＲＵキャッシュにおいて、キャッシュ・サイズは５００を、また、タイム・アウトは１，８００秒をそれぞれ想定している。なお、ＬＲＵキャッシュ及び後述の図１４〜図１８において、キャッシュ・サイズの単位は個数である。アプリケーション・サーバはJava（登録商標）で実装されており、キャッシュするデータもJavaのオブジェクトである。Javaではメモリーの領域を明示的に管理することはできないので、最大で何個のオブジェクトをキャッシュするかを指定するだけになる。もちろん１個の１個のオブジェクトの大きさは決まっていないので、消費するメモリーの総量は不定である。ＬＲＵキャッシュからｒαの推定値が出力される。
【００５６】
ＩＢＭ社ＷｅｂサーバVer. 5.0以降ではセッションに関するＰＭＩデータ・カウンタと定義して以下のような統計量を利用することができる。平均値を与えるデータ・カウンタ（Data Counter）では内部的に、測定個数、総和、２乗総和、最大値、最小値を保持しているので、分散を得ることも可能である。”：”の左側がデータ・カウンタ名、右側が計数データをそれぞれ意味する。
【００５７】
Ａ．データ・カウンタ名：計数データ
createdSessions：作成されたセッションの数
invalidatedSessions：無効になったセッションの数
sessionLifeTime：セッションの平均存続時間
activeSessions：同時にアクティブなセッションの数。 ＩＢＭ社Ｗｅｂサーバが、セッションを使用する要求を現在処理している場合、そのセッションはアクティブである。
liveSession：同時にメモリーのキャッシュに入れられるセッションの数。
NoRoomForNewSession：メモリー内で AllowOverflow=false が指定されているセッションに対してのみ適用されます。最大セッション・カウント数を超えるため、新規セッションの要求を処理できない回数。
cacheDiscards：キャッシュから強制的に除去されたセッション・オブジェクトの数 (LRU アルゴリズムは、古いエントリーを除去して、新規セッションとキャッシュ・ミス用にスペースを確保します)。持続セッションにのみ適用可能。
externalReadTime：永続ストアからのセッション・データの読み取りにかかる時間 (ミリ秒)。複数行セッションの場合、メトリックは属性用で、単一行セッションの場合、メトリックはセッション全体用になる。持続セッションにのみ適用可能。 JMS 永続ストアを使用する場合、ユーザーは、複製されているデータを直列化するかどうか選択できる。ユーザーがデータを直列化しないよう選択した場合、カウンターは使用できなくなる。
externalReadSize：永続ストアから読み取られるセッション・データのサイズ。 (直列化された) 持続セッションにのみ適用可能。上述の externalReadTime と同様。
externalWriteTime：永続ストアからのセッション・データの書き込みにかかる時間 (ミリ秒)。(直列化された) 持続セッションにのみ適用可能。上述の externalReadTime と同様。
externalWriteSize：永続ストアに書き込まれるセッション・データのサイズ。(直列化された) 持続セッションにのみ適用可能。上述の externalReadTime と同様。
affinityBreaks：別の Web アプリケーションから最後にアクセスされたセッションで受信された要求の数。これは、フェイルオーバ処理または壊れたプラグイン構成を示している可能性がある。
serializableSessObjSize：メモリー内のセッションの (直列化可能属性の) サイズ (バイト)。少なくとも 1 つの直列化可能な属性オブジェクトが入ったカウント・セッション・オブジェクトのみ。 1 つのセッションに直列化可能属性とそうでない属性が含まれている場合がある点に注意してください。サイズ (バイト) はセッション・レベルのものです。
timeSinceLastActivated：直前のアクセス時刻と現在のアクセス時刻のタイム・スタンプの時間差 (ミリ秒)。セッション・タイムアウトは含まれない。
invalidatedViaTimeout：おそらくセッション・タイムアウトが原因で、CountStatistic が存在していないセッションの要求の数。
attemptToActivateNotExistentSession：おそらくセッション・タイムアウトが原因で、もはや存在していないセッションの要求の数。このカウンターを使用すると、タイムアウトが短すぎるかどうかを判断するのに役立つ。
【００５８】
上記ＰＭＩデータ・カウンタの中から選択したものを用いて次の量を利用する。以降ではデータ・カウンタの名前の後に、Rate, Mean, Var, Countを付記することで、それぞれ増加率、平均、分散、測定回数を表現するものとする。
【００５９】
Ｂ．選択するＰＭＩデータ・カウンタ（利用する量）
・createdSessions (rate of increase)
・invalidatedSessions (rate of increase)
・sessionLifeTime (mean and variance)
・externalReadTime (count and mean)
・externalWriteTime (count and mean)
・timeSinceLastActivated (count , mean and variance)
・invalidatedViaTimeout (rate of increase)
【００６０】
また、アプリケーション・サーバ（Application Server）についての次の構成パラメータ（Configuration parameters）も取得可能である。
Ｃ．構成パラメータ
・maxInMemorySessionCount: セッション・キャッシュのサイズ
・sessionTimeout: 最後に参照されてから無効化されるまでの時間
・ writeInterval:  外部記憶への非同期更新を行う時間間隔
【００６１】
上記Ａ．、Ｂ．及びＣ．の数値を基にして次のＤ．では、以下に示す計算式（下段）により各種の統計量（上段）を計算することができる。
Ｄ．統計量及び計算式
・hitRatio: ヒット率
1-externalReadTimeCount/timeSinceLastActivatedCount
・invalidateRate: 陽に無効化される頻度
invalidatedSessionsRate - invalidatedViaTimeoutRate
・timeoutRate: タイムアウトにより無効化される頻度
invalidatedViaTimeoutRate
・totalRate: 上記２つをまとめた無効化される頻度
invalidatedSessionsRate
・userLifetime: ユーザがＷｅｂサイトを訪れている総時間
( sessionLifeTimeMean*totalRate - timeoutInterval*timeoutRate ) / totalRate
・userLifetimeVar: userLifetimeの分散
((sessionLifeTimeVar+sessionLifeTimeMean*sessionLifetimeMean)*totalRate - 2*timeoutInterval*sessionLifeTimeMean*timeoutRate -timeoutInterval*timeoutInterval*timeoutRate) / totalRate
・userLifetimeSD: userLifetimeの標準偏差
sqrt(userLifetimeVar)
・activeUser: Ｗｅｂサイトをある時間に訪れている平均ユーザ数
userLifetime*createdSessionsRate
・activeUserSD: 上記ユーザ数の分散
userLifetimeSD*createdSessionsRate
・averageVisit: １人のユーザがＷｅｂページを閲覧する平均回数
userLifetime/timeSinceLastActivatedMean
【００６２】
上記Ｄ．の主要な統計量を使って、シミュレーション用のモデルを以下のように求める。
Ｅ．シミュレーション用モデルに使用する数学量及び計算式
・triggerRate: 新しいセッションが始まる（新しいユーザが到着する）時間間隔の平均
1/createdSessionsRate
・leaveProb: ユーザがＷｅｂサイトを去る確率
1/averageVisit
・invalidateProb: ユーザがＷｅｂサイトを去るときに陽にセッションの無効化を行う確率
invalidateRate/totalRate
・userThinkTime: ユーザがＷｅｂページを移動する時間間隔の平均
timeSinceLastActivatedMean
・userThinkTimeVar: 上記時間間隔の分散
timeSinceLastActivatedVar
【００６３】
モデルの定義から分かるように、このモデルではユーザがＷｅｂページを参照する行為とセッション・データを参照又は更新する行為が同一視されている。したがって、セッション・データへの参照又は更新が局所的にかたまって起きることは想定されていないので、シミュレーションにより推定されるヒット率と実際のヒット率との間には大きな開きがある。
【００６４】
Trade3というベンチマーク用のアプリケーションを用いてセッション・キャッシュのヒット率を測定する２種類の実験（図１４及び図１５は第１の実験（テスト・ケース１）、図１６及び図１７は第２の実験（テスト・ケース２）に関する。）を行い、同時にTivoli Performance Monitorにより１０秒毎のＰＭＩデータ・カウンタの値を取得し、その値からシミュレーションによりヒット率を求めた。図１１及び図１３の表にはPMIの測定値から計算したモデルのパラメータを、図１５及び図１７にはシミュレーションにより推定したヒット率（折れ線）と実測値（●印）とのグラフを示す。実線、破線及び一点鎖線はヒット率をそれぞれ１．０，  ２．０，  ３．０にしてシミュレーションしたときのヒット率を表す。図１５では、●は、接近して重なって見え難くなっているが、キャッシュ・サイズ＝３００，４００，５００において、それぞれ２個（図１４の各キャッシュ・サイズの行数に対応する個数）ずつ存在する。シミュレーションでは局所性因子（Locality factor）を何種類（α＝１．０，  ２．０，  ３．０）か用いてヒット率を評価している。α＝１．０である場合がセッション・データ読出しパターンの局所性を考慮せずにPMIの統計量から評価したヒット率に相当する。図１５及び図１７のグラフから分かるように、局所性を考慮しない場合には実測値と推定値に大きな開きが出てしまう。したがって、本発明のように、局所性を考慮して、ヒット率を考えることが有意義であることが理解できる。
【００６５】
次に、実測されたヒット率ｒから局所性因子を推定する手法の検証を行った。上記実験で得られたヒット率とシミュレーションによるヒット率を用いて、局所性因子の推定した結果が図１８の表である。αと一緒に、推定されたαを用いて思考時間と退出確率の変換後を値も示している。実験の条件から、正しい値は、思考時間の平均が１０秒、分散（ＳＤ）が５．７４、退出確率が６％であり、比較のために最後の行に示した。また、図１８中にテスト・ケース名の後に※が付記されているテスト・ケースは、推定の繰り返しが収束せずに局所性因子の許容範囲を超えて停止したものである。
【００６６】
測定されたヒット率が高いところでは、局所性因子を変化させてもシミュレーションによるヒット率があまり変化しないので測定誤差、モデルの誤差が大きい場合には推定が難しいが、ヒット率が小さい場合には局所性因子をかなり正しく推定していると言える。
【００６７】
本発明はＩＢＭ社Ｗｅｂサーバに実装されているデータ取得機能であるPMIを基にしてキャッシュ・サイズを変更した場合のキャッシュのヒット率を推定する方法である。PMIは稼動中のサーバから各種の統計量を取得するために、比較的オーバヘッドが小さく抑えられる範囲で有益な情報を集めている。これらの情報だけから正確なヒット率の評価が可能になれば、アクセス・パターンに変化があっても、実稼動中のサーバへのアクセス・パターンをオンラインでモニターしながら最適なキャッシュ・サイズを随時求めることが可能になり、ＨＴＴＰセッションに関するシステム構成の動的で適応的な最適化が可能になる。
【図面の簡単な説明】
【００６８】
【図１】ネットワークで接続されている所定Ｗｅｂサーバと複数のクライアントとの関係を示す図である。
【図２】１回のセッションにおけるセッション・データ読出しの時間分布を示す図である。
【図３】パラメータ変換と観測によるヒット率とが関係式により規定されることを示す説明図である。
【図４】ヒット率推定装置の機能ブロック図である。
【図５】真値探索手段の詳細な機能ブロック図である。
【図６】シミュレーション手段の詳細な機能ブロック図である。
【図７】ヒット率推定方法のフローチャートである。
【図８】図７の不動点計算法による探索ステップの詳細図である。
【図９】シミュレーション・ステップの具体的な第１のフローチャート部分である。
【図１０】シミュレーション・ステップの具体的な第２のフローチャート部分である。
【図１１】シミュレーション・ステップの具体的な第３のフローチャート部分である。
【図１２】プログラムを実行するためのハードウェア構成図である。
【図１３】キャッシュ構成アドバイザ・プロジェクトで、ＩＢＭ社Ｗｅｂサーバのセッション・キャッシュの大きさを最適化する目的に使用するために実装したヒット率推定装置の機能ブロック図である。
【図１４】第１の実験においてＰＭＩの測定値から計算したモデルのパラメータを示す表である。
【図１５】第１の実験におけるヒット率実測値と第１の実験のデータに基づくシミュレーションにより推定したヒット率との関係を示すグラフである。
【図１６】第２の実験においてＰＭＩの測定値から計算したモデルのパラメータを示す表である。
【図１７】第２の実験におけるヒット率実測値と第２の実験のデータに基づくシミュレーションにより推定したヒット率との関係を示すグラフである。
【図１８】第１及び第２の実験におけるヒット率実測値から推定した局所性因子を示す表である。
【符号の説明】
【００６９】
１０：Ｗｅｂサーバ、１２：セッション・データ・キャッシュ、１３：永続ストア、１９：カウンタ、２０：ヒット率推定装置、２１：計算式設定手段、２２：真値探索手段、２３：推定手段、２８：第１の計算手段、２９：第２の計算手段、３０：第３の計算手段、３１：判定手段、３２：出力生成手段、３３：元値付与手段、３７：シミュレーション手段、３８：トリガ手段、３９：ユーザ模擬手段、４０：観測手段、４１：観測ヒット率出力手段。
【図１】
2005149184.tif 000003
【図２】
2005149184.tif 000004
【図３】
2005149184.tif 000005
【図４】
2005149184.tif 000006
【図５】
2005149184.tif 000007
【図６】
2005149184.tif 000008
【図７】
2005149184.tif 000009
【図８】
2005149184.tif 000010
【図９】
2005149184.tif 000011
【図１０】
2005149184.tif 000012
【図１１】
2005149184.tif 000013
【図１２】
2005149184.tif 000014
【図１３】
2005149184.tif 000015
【図１４】
2005149184.tif 000016
【図１５】
2005149184.tif 000017
【図１６】
2005149184.tif 000018
【図１７】
2005149184.tif 000019
【図１８】
2005149184.tif 000020