JP2005339198A - キャッシュヒット率推定装置、キャッシュヒット率推定方法、プログラム及び記録媒体 - Google Patents

Abstract

【課題】キャッシュ装置のキャッシュヒット率を解析的に精度良く求める。
【解決手段】 要求元装置からアクセスされたアクセス対象データをキャッシュするキャッシュ装置のキャッシュヒット率を推定するキャッシュヒット率推定装置であって、それぞれのアクセス対象データに対するアクセス要求について計測された平均到着頻度を取得するアクセス要求到着頻度取得部と、それぞれのアクセス対象データに対するアクセス要求の平均到着頻度に基づいて、当該アクセス対象データに対するアクセス要求の到着時間間隔の確率密度関数であるアクセス要求到着確率密度関数を生成するアクセス要求到着確率密度関数生成部と、複数のアクセス対象データのアクセス要求到着確率密度関数に基づいて、それぞれのアクセス対象データのキャッシュヒット率の推定関数を生成するキャッシュヒット率推定関数生成部とを備えるキャッシュヒット率推定装置を提供する。
【選択図】図２

Description

本発明は、キャッシュヒット率推定装置、キャッシュヒット率推定方法、プログラム及び記録媒体に関する。特に本発明は、キャッシュミス時のアクセスコストが異なる複数のアクセス対象データのそれぞれについてのキャッシュヒット率を推定するキャッシュヒット率推定装置、キャッシュヒット率推定方法、プログラム及び記録媒体に関する。

近年、Ｗｅｂアプリケーション等を実行するサーバ装置は、例えばＨＴＴＰサーバ、Ｗｅｂコンテナ、ＥＪＢコンテナ、及びデータベースサーバ等の各コンポーネント毎にアクセスされたデータをキャッシュし、負荷の軽減及び応答時間の低減を図っている。このようなキャッシュを用いるアプリケーションの処理性能は、アクセス対象データのキャッシュヒット率、キャッシュヒット時の応答時間、及び、キャッシュミス時のアクセス処理時間により定まる。しかしながら、従来においては、キャッシュの各設定パラメータがキャッシュヒット率に与える影響が定量的に明らかでなく、これらのパラメータをヒューリスティックに設定していた。

また従来、ＬＲＵ（Least Recently Used）方式によるキャッシュのヒット率を推定する方法として、非特許文献１から４が提案されている。
非特許文献１は、アクセス要求を受けた際に、キャッシュする対象となる各アイテムがＬＲＵリストのn番目に存在する確率を、以下の式（１）により求める。ここで、C^Nは全てのアイテムについての参照コスト（アクセス要求を受けた際のアクセス対象アイテムのリスト内における位置）、q_rはアイテムr（r=1,2, …, N）がアクセスされる確率である。

式（１）を用いれば、k個のアイテムをキャッシュするＬＲＵキャッシュのヒット率は、P[CN≦k]により求めることができる。

非特許文献２及び非特許文献３は、アイテム毎の参照コストC_r ^Nの確率母関数を以下の式（２）により求める。

非特許文献４は、アイテム数N及びキャッシュサイズkが無限大に近づく時の漸近的な近似式として以下の式（３−１）及び（３−２）を示す。式（３−１）はアイテムの参照確率分布が多項式で減少していく場合（Heavy Tail）の近似式、式（３−２）は参照確率分布が指数的に減少していく場合（Light Tail）の近似式である。さらにN, kが比較的小さな値であっても、この近似式の精度が高いことを実験により検証している。

P.J. Burville and J. F. C. Kingman, "On a model for strage and search.", Journal of Applied Probability, 10: p.697-701, １９７３年 P. Flajolet, D. Gardy, and L. Thimonier, "Birthday paradox, coupon collector, caching algorithms and self-organizing search.", Discrete Applied mathematics, 39: p.207-229, １９９２年 J. A. Fill and L. Holst, "On the distribution search cost for the move-to-front rule.", Random Structures and algorithms, 8(3): p.179-186, １９９６年 P. R. Jelenkovic, "Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities.", Annals of Applied Probability, 9(2): p.430-464, １９９９年.

キャッシュの設定パラメータをヒューリスティックに設定する場合、アプリケーションの実行環境に応じた最適値を求めるのが困難である。すなわち例えば、設定パラメータの最適値を求めるためには、情報システムの構築時等において、設定パラメータを変えながら性能測定を繰り返して最適な設定パラメータを求める方法が考えられるが、作業の負担が大きく動的に変化するアプリケーション実行環境に対応することができない。

そこで本発明は、キャッシュの性能をより高めるため、アプリケーション実行中に計測した各種の統計情報に基づいてより適切な設定パラメータを算出し、キャッシュに設定するキャッシュシステムを提案する。より具体的には、各種の統計情報に基づいてアクセス処理の性能を推定する推定関数を生成し、アクセス処理性能の推定値を高める設定パラメータを求めてキャッシュに設定する。

ここで、Ｗｅｂアプリケーション等を実行するサーバ装置においては、キャッシュする対象となるデータは、各種のサーバアプリケーションが出力するデータであり、アクセス対象データによってキャッシュミス時のアクセスコストが異なる。したがって、アクセス処理性能を精度良く推定するためには、アクセス対象データ毎のキャッシュヒット率を求める必要がある。

非特許文献１においては、アイテムの数が増加すると、式（１）におけるアイテムの組み合わせAの数が爆発的に増加するため、アクセス処理性能の評価を効率良く行うことが困難である。

また非特許文献２及び３においても、アイテムの数が増加すると数値的に計算困難となるため、式（２）を用いてアクセス処理性能の評価を行うことは困難である。

また非特許文献４においては、アイテム毎のヒット率については考慮されていない。しかし、本発明の対象となるアプリケーション実行環境においては、アクセス対象データ毎のキャッシュヒット率が要求されるため、式（３）を用いてアクセス処理性能の評価を行うことは困難である。

そこで本発明は、上記の課題を解決することのできるキャッシュヒット率推定装置、キャッシュヒット率推定方法、プログラム及び記録媒体を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。

本発明の第１の形態によると、要求元装置からアクセスされたアクセス対象データをキャッシュするキャッシュ装置のキャッシュヒット率を推定するキャッシュヒット率推定装置であって、複数の前記アクセス対象データの少なくとも１つは、キャッシュミス時のアクセスコストが他の前記アクセス対象データと異なるものであり、それぞれの前記アクセス対象データに対するアクセス要求について計測された平均到着頻度を取得するアクセス要求到着頻度取得部と、それぞれのアクセス対象データに対するアクセス要求の平均到着頻度に基づいて、当該アクセス対象データに対するアクセス要求の到着時間間隔の確率密度関数であるアクセス要求到着確率密度関数を生成するアクセス要求到着確率密度関数生成部と、前記複数のアクセス対象データの前記アクセス要求到着確率密度関数に基づいて、それぞれの前記アクセス対象データのキャッシュヒット率の推定関数を生成するキャッシュヒット率推定関数生成部とを備えるキャッシュヒット率推定装置と、当該キャッシュヒット率推定装置に関するキャッシュヒット率推定方法、プログラム、及び記録媒体とを提供する。

なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。

本発明によれば、キャッシュ装置のキャッシュヒット率を解析的に精度良く求めることができる。そして、解析結果に基づいてキャッシュ装置の設定パラメータを最適化することにより、アクセス処理性能を高めることができる。

以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。

図１は、本実施形態に係る情報システム１０の構成を示す。情報システム１０は、１又は複数の要求元装置１００と、１又は複数のサーバ装置１１０と、キャッシュシステム１２０とを備える。
要求元装置１００は、アクセス要求をサーバ装置１１０に対して送信することにより、アクセスする対象となるアクセス対象データの送信を要求する。そして、要求元装置１００は、サーバ装置１１０からアクセス対象データを受信する。本実施形態に係る要求元装置１００は、例えばクライアント端末であり、ＨＴＴＰやＳＯＡＰ等に基づくアクセス要求をサーバ装置１１０に対して送信する。これに代えて要求元装置１００は、例えばキャッシュメモリを介してメモリをアクセスするＣＰＵ等であってもよい。

サーバ装置１１０は、キャッシュシステム１２０を介して要求元装置１００からのアクセス要求を受信し、アクセス要求に対応する処理を行って、アクセス対象データを生成する。そしてサーバ装置１１０は、アクセス対象データを、キャッシュシステム１２０を介して要求元装置１００へ返信する。本実施形態に係るサーバ装置１１０は、例えばＷｅｂアプリケーションサーバであり、アクセス要求に対応するサーブレットやＪＳＰ等のサーバプログラムを実行して、当該アクセス要求に対応するアクセス対象データを生成する。これに代えてサーバ装置１１０は、例えばＣＰＵ等の要求元装置１００からのアクセス要求を受けて記憶領域をアクセスするメモリシステムやＩ／Ｏシステム等であってもよい。また、複数のサーバ装置１１０のそれぞれは、複数のentity Beansを分割した一部のentity Beansが割り当てられたEJBコンテナを処理するＪＶＭ（Java Virtual Machine）等であってもよい。

キャッシュシステム１２０は、キャッシュ装置１３０と、キャッシュ最適化装置１４０とを有する。キャッシュ装置１３０は、要求元装置１００からアクセスされ、サーバ装置１１０により返信されたアクセス対象データをキャッシュ記憶領域１３５にキャッシュする。そして、キャッシュしたアクセス対象データをアクセスするアクセス要求を受けた場合に、キャッシュしたアクセス対象データをキャッシュ記憶領域１３５から要求元装置１００へ返信する。本実施形態において、キャッシュ装置１３０は、最大K個のアクセス対象データをＬＲＵ方式によりキャッシュする。

キャッシュ最適化装置１４０は、本発明に係るキャッシュヒット率推定装置の一例であり、情報システム１０による処理の実行中に、１又は複数の要求元装置１００からサーバ装置１１０に対するアクセス要求の到着頻度や、キャッシュされたアクセス対象データの無効化頻度等の計測値を取得する。次に、キャッシュ最適化装置１４０は、これらの計測値に基づいて、キャッシュ装置１３０のキャッシュヒット率を推定し、キャッシュヒット率の推定関数に基づいてキャッシュ装置１３０によるアクセス処理性能の推定関数を生成する。そして、アクセス処理性能の推定値をより高める設定パラメータを算出し、キャッシュ装置１３０に設定する。このようにキャッシュ最適化装置１４０は、実環境に基づいてキャッシュ装置１３０のアクセス処理性能をモデル化し、当該モデルを用いて最適な設定パラメータをキャッシュ装置１３０に設定することにより、実環境に応じてキャッシュ装置１３０のアクセス処理性能を高めることができる。

以上において、１又は複数のサーバ装置１１０は、アクセス要求を受信すると、当該アクセス要求に対応するサーバプログラムをある処理時間実行して、アクセス対象データを生成する。ここで、アクセス要求を受信してからアクセス対象データを生成するまでの処理時間は、アクセス要求に対応するサーバプログラムの相違や、サーバ装置１１０を実現するコンピュータの相違等の要因により異なる。そこで、本実施形態に係るキャッシュ最適化装置１４０は、複数のアクセス対象データの少なくとも１つについて、キャッシュミス時のサーバ装置１１０の処理時間を示すアクセスコストが、他のアクセス対象データと異なる場合において、キャッシュ装置１３０のアクセス処理性能を最適化することを目的とする。

図２は、本実施形態に係るキャッシュ最適化装置１４０の構成を示す。キャッシュ最適化装置１４０は、パラメータ設定部２００と、グループ対応統計情報取得部２１０と、アクセス要求到着頻度取得部２１５と、無効化要求到着頻度取得部２２０と、アクセス要求到着確率密度関数生成部２２５と、無効化要求到着確率密度関数生成部２３０と、次アクセスヒット時間分布関数生成部２３５と、キャッシュ有効時間分布関数生成部２４０と、キャッシュヒット率推定関数生成部２４５と、アクセス処理性能推定関数生成部２５０と、パラメータ変更部２５５とを備える。

パラメータ設定部２００は、キャッシュの設定パラメータの初期値をキャッシュ装置１３０に設定する。ここで、パラメータ設定部２００が設定する設定パラメータは、要求元装置１００からのアクセス要求に対するアクセス処理性能を変化させるパラメータである。

グループ対応統計情報取得部２１０は、アクセス要求及び／又はアクセス応答についてキャッシュ装置１３０により計測された統計情報をキャッシュ装置１３０から取得する。本実施形態において、キャッシュ装置１３０にキャッシュされる各アクセス対象データは、アクセスコスト等に基づいて分類した複数のグループのいずれかに属する。一例として、アクセス要求に応じてサーバ装置１１０により生成されるアクセス対象データは、当該アクセス対象データを生成するサーバプログラム毎、すなわち例えばサーブレット、コマンド、又はＷｅｂサービスの種類毎にグループ化される。この場合、異なるサーバプログラムに対する複数のアクセス要求に対して生成される複数のアクセス対象データは、異なるグループに属する。一方、同一のサーバプログラムへ入力パラメータが異なる複数のアクセス要求が送信された場合に生成される複数のアクセス対象データは、同一のグループに属する。後者の具体的な例としては、ユーザＩＤの異なる複数の使用者が、同一のサーバプログラムに対してアクセスする場合等が挙げられる。
本実施形態において、グループ対応統計情報取得部２１０は、アクセス要求及びアクセス対象データのグループ毎に、キャッシュ装置１３０により計測された統計情報を取得する。

アクセス要求到着頻度取得部２１５は、グループ対応統計情報取得部２１０により取得された統計情報に基づいて、それぞれのアクセス対象データに対するアクセス要求について計測された平均到着頻度λ_iを取得する。無効化要求到着頻度取得部２２０は、グループ対応統計情報取得部２１０により取得された統計情報、及び平均到着頻度λ_iに基づいて、それぞれのアクセス対象データに対する無効化要求について計測された平均到着頻度μ_iを取得する。

アクセス要求到着確率密度関数生成部２２５は、それぞれのアクセス対象データに対するアクセス要求の平均到着頻度λ_iに基づいて、当該アクセス対象データに対するアクセス要求の到着時間間隔の確率密度関数であるアクセス要求到着確率密度関数f_i ^R(t)を生成する。無効化要求到着確率密度関数生成部２３０は、それぞれのアクセス対象データに対する無効化要求の平均到着頻度μ_iに基づいて、当該アクセス対象データに対する無効化要求の到着時間間隔の確率密度関数である無効化要求到着確率密度関数f_i ^I(t)を生成する。

次アクセスヒット時間分布関数生成部２３５は、それぞれのアクセス対象データについて、アクセス要求到着確率密度関数f_i ^R(t)及び無効化要求到着確率密度関数f_i ^I(t)に基づいて、次アクセスヒット時間分布関数F_i(t)を生成する。本実施形態において、次アクセスヒット時間分布関数は、当該アクセス対象データへのアクセス要求を受信した後、当該アクセス対象データがキャッシュから無効化される前に当該アクセス対象データに対する次のアクセス要求を受信する確率の時間分布関数である。

キャッシュ有効時間分布関数生成部２４０は、それぞれのアクセス対象データについて、アクセス要求到着確率密度関数f_i ^R(t)及び無効化要求到着確率密度関数f_i ^I(t)に基づいて、キャッシュ有効時間分布関数G_i(t)を生成する。本実施形態において、キャッシュ有効時間分布関数G_i(t)は、予め定められた時点、すなわち例えば任意の時点を基準とし、当該アクセス対象データに対する少なくとも１つのアクセス要求を受信し、かつ、当該アクセス対象データがキャッシュから無効化されていない確率の時間分布関数である。

キャッシュヒット率推定関数生成部２４５は、複数のアクセス対象データのアクセス要求到着確率密度関数f_i ^R(t)に基づいて、それぞれのアクセス対象データのキャッシュヒット率の推定関数h_iを生成する。より具体的には、本実施形態に係るキャッシュヒット率推定関数生成部２４５は、それぞれのアクセス対象データについて、アクセス要求到着確率密度関数f_i ^R(t)に基づく複数のアクセス対象データのキャッシュ有効時間分布関数G_i(t)と、当該アクセス対象データに対する次アクセスヒット時間分布関数F_i(t)とに基づいて、当該アクセス対象データのキャッシュヒット率推定関数h_iを生成する。

アクセス処理性能推定関数生成部２５０は、それぞれのアクセス対象データのキャッシュヒット率推定関数h_i、キャッシュヒット時のアクセスコストC_i ^R、及びキャッシュミス時のアクセスコストC_i ^Cに基づいて、アクセス処理性能の推定関数Cを生成する。パラメータ変更部２５５は、キャッシュ装置１３０に設定された設定パラメータを、アクセス処理性能推定関数Cによるアクセス処理性能の推定値をより高める設定パラメータに変更する。

図３は、本実施形態に係るグループ対応統計情報取得部２１０の構成を示す。グループ対応統計情報取得部２１０は、アクセス対象データの各グループi（i=1,2, …, M）の統計情報として、グループ対応アクセス要求回数requestFromClients_i、グループ対応キャッシュヒット回数hitsInMemory_i、グループ対応エントリ数entries_i、及びグループ対応無効化回数explicitInvalidation_iをキャッシュ装置１３０から取得する。requestFromClients_iは、１又は複数の要求元装置１００からグループiのアクセス対象データに対するアクセス要求を受信した回数の計測値である。hitsInMemory_iは、アクセス要求に対して、グループiのアクセス対象データがキャッシュヒットした回数の計測値である。entries_iは、グループiに属する全てのアクセス対象データのうち、キャッシュ装置１３０がキャッシュしているアクセス対象データの個数の計測値である。explicitInvalidation_iは、グループiのアクセス対象データをキャッシュから無効化した回数の計測値である。なお、requestFromClients_i、hitsInMemory_i及びexplicitInvalidation_iは、単位時間当たりのカウント値であってよく、entries_iは、単位時間当たりの平均値又は単位時間毎のサンプル値であってよい。グループ対応統計情報取得部２１０は、グループ対応キャッシュヒット率取得部３００と、グループ対応エントリ数取得部３１０と、アクセス対象データ数算出部３２０と、グループ対応無効化数取得部３３０とを有し、これらの計測値に基づいて、アクセス対象データ毎の統計値を取得する。

グループ対応キャッシュヒット率取得部３００は、以下の式（４）に示すように、それぞれのグループについて、グループ対応キャッシュヒット回数hitsInMemory_i及びグループ対応アクセス要求回数requestFromClients_iに基づいて、当該グループに属する全てのアクセス対象データについて計測された平均キャッシュヒット率H_iを取得する。

ここで、同一グループに属する各アクセス対象データが同一のアクセス特性を有することを前提とすれば、同一グループに属する複数のアクセス対象データについては、同一の頻度でアクセスされる。このため、グループiの全アクセス対象データのキャッシュヒット率をH_iと見なすことができる。

グループ対応エントリ数取得部３１０は、それぞれのグループについて、グループ対応エントリ数entries_iの計測値を取得する。アクセス対象データ数算出部３２０は、それぞれのグループについて、当該グループのグループ対応エントリ数entries_i及び当該グループの平均キャッシュヒット率H_iに基づいて、当該グループに属するアクセス対象データの数γ_iの推定値を算出する。ここで、同一グループに属する複数のアクセス対象データは、同一の頻度でアクセスされることから、アクセス対象データ数算出部３２０は、以下の式（５）に示すように、グループ対応エントリ数entries_iを平均キャッシュヒット率H_iで割ることにより、各グループに属するアクセス対象データの数γ_iの推定値を算出することができる。

グループ対応無効化数取得部３３０は、それぞれのグループについて、グループ対応無効化回数explicitInvalidation_iの計測値を取得する。本実施形態に係るキャッシュ装置１３０は、アクセス対象データに変更が生じた場合に、当該アクセス対象データをキャッシュから無効化して、再度サーバ装置１１０により生成させる。そこでキャッシュ装置１３０は、アクセス対象データに変更が生じた場合に、要求元装置１００又はサーバ装置１１０から無効化要求を受けて、当該アクセス対象データを無効化する。グループ対応無効化数取得部３３０は、無効化要求によりアクセス対象データが無効化された回数を、グループ毎に計測する。

以上に示したグループ対応統計情報取得部２１０によれば、アクセス対象データを適切にグループ化しておくことにより、グループ毎の統計情報に基づいて、個々のアクセス対象データについての統計情報を近似的に求めることができる。このため、キャッシュ装置１３０は、グループ化した複数のアクセス対象データについての統計情報を計測することができ、個々のアクセス対象データの到着頻度が低い場合においても適切な統計値を得ることができる。

図４は、本実施形態に係るキャッシュ最適化装置１４０の動作フローを示す。
まず、パラメータ設定部２００は、キャッシュの設定パラメータの初期値をキャッシュ装置１３０に設定する（ステップＳ４００）。この初期値は、情報システム１０の管理者等により予め定められてよい。情報システム１０は、この設定に基づいて、アプリケーション処理を行う。本実施形態におけるキャッシュの設定パラメータは、一例として、それぞれのアクセス対象データをキャッシュするか否かをグループ毎に指定するパラメータである。

次に、グループ対応統計情報取得部２１０は、アクセス要求及び／又はアクセス応答についてキャッシュ装置１３０により計測された統計情報をキャッシュ装置１３０から取得する（Ｓ４１０）。そして、取得したグループ対応アクセス要求回数requestFromClients_i及びアクセス対象データ数算出部３２０により算出したアクセス対象データ数γ_iをアクセス要求到着頻度取得部２１５に供給する。また、取得したグループ対応キャッシュヒット回数hitsInMemory_i及びグループ対応無効化回数explicitInvalidation_iを無効化要求到着頻度取得部２２０に供給する。

次に、アクセス要求到着頻度取得部２１５は、グループ対応統計情報取得部２１０により取得された統計情報に基づいて、それぞれのアクセス対象データに対するアクセス要求についての平均到着頻度λ_iの計測値を取得する（Ｓ４２０）。本実施形態において、アクセス要求到着頻度取得部２１５は、以下の式（６）に示すように、それぞれのグループについて、グループ対応アクセス要求回数requestFromClients_iを当該グループのアクセス対象データ数γ_iで割ることにより、各アクセス対象データに対するアクセス要求の平均到着頻度λ_iを取得する。ここで、グループ対応アクセス要求回数requestFromClients_iは、当該グループに属する全アクセス対象データについて計測された単位時間当たりのアクセス要求数、すなわち、アクセス要求の平均到着頻度である。

次に、無効化要求到着頻度取得部２２０は、グループ対応統計情報取得部２１０により取得された統計情報に基づいて、それぞれのアクセス対象データに対する無効化要求の平均到着頻度μ_iの計測値を取得する（Ｓ４３０）。本実施形態において、無効化要求到着頻度取得部２２０は、以下の式（７）に示すように、それぞれのグループについて、アクセス要求到着頻度取得部２１５により取得されたアクセス要求の平均到着頻度λ_iと、グループ対応統計情報取得部２１０により取得されたグループ対応無効化回数explicitInvalidation_i、及びグループ対応キャッシュヒット回数hitsInMemory_iとに基づいて、各アクセス対象データに対する無効化要求の平均到着頻度μ_iを取得する。

次に、アクセス要求到着確率密度関数生成部２２５は、それぞれのアクセス対象データに対するアクセス要求の平均到着頻度λ_iに基づいて、当該アクセス対象データに対するアクセス要求到着確率密度関数f_i ^R(t)を生成する（Ｓ４４０）。次に、無効化要求到着確率密度関数生成部２３０は、それぞれのアクセス対象データに対する無効化要求の平均到着頻度μ_iに基づいて、当該アクセス対象データに対するアクセス要求到着確率密度関数f_i ^I(t)を生成する（Ｓ４５０）。

次に、次アクセスヒット時間分布関数生成部２３５は、それぞれのアクセス対象データについて、アクセス要求到着確率密度関数f_i ^R(t)及び無効化要求到着確率密度関数f_i ^I(t)に基づいて、次アクセスヒット時間分布関数F_i(t)を生成する（Ｓ４５２）。より具体的には、次アクセスヒット時間分布関数生成部２３５は、次の（ａ）から（ｄ）に示す手順により次アクセスヒット時間分布関数F_i(t)を生成する。

（ａ）当該アクセス対象データへの無効化要求を受信した後、次に当該アクセス対象データへの無効化要求を受信するまでの時間分布関数F_i ^I(t)を、無効化要求到着確率密度関数f_i ^I(t)に基づいて生成（式（８））

（ｂ）任意の時点を基準として、次の無効化要求が到着するまでの時間（前方待ち時間）又は最後に無効化要求が到着してからの経過時間（後方経過時間）の時間分布関数G_i ^I(t)を、無効化要求到着確率密度関数f_i ^I(t)及び時間分布関数F_i ^I(t)に基づいて生成（式（９））

（ｃ）任意の時点を基準として、ある時刻tまでに無効化要求が到着していない確率α_i(t)を、時間分布関数G_i ^I(t)に基づいて生成（式（１０））

（ｄ）確率α_i(t)及びアクセス要求到着確率密度関数f_i ^R(t)に基づいて、次アクセスヒット時間分布関数F_i(t)を生成（式（１１））

以上において、次アクセスヒット時間分布関数生成部２３５は、それぞれのアクセス対象データをキャッシュするか否かを設定する設定パラメータを入力とする次アクセスヒット時間分布関数F_i(t)を生成する。すなわち例えば、次アクセスヒット時間分布関数生成部２３５は、グループiのアクセス対象データをキャッシュしない場合に、グループiのアクセス要求到着確率密度関数f_i ^R(t)及び無効化要求到着確率密度関数f_i ^I(t)を"0"として上記の計算を行う次アクセスヒット時間分布関数F_i(t)を生成する。

次に、キャッシュ有効時間分布関数生成部２４０は、それぞれのアクセス対象データについて、アクセス要求到着確率密度関数f_i ^R(t)及び無効化要求到着確率密度関数f_i ^I(t)に基づいて、キャッシュ有効時間分布関数G_i(t)を生成する（Ｓ４５４）。より具体的には、キャッシュ有効時間分布関数生成部２４０は、次の（ａ）から（ｂ）に示す手順によりキャッシュ有効時間分布関数G_i(t)を生成する。

（ａ）当該アクセス対象データへのアクセス要求を受信した後、次に当該アクセス対象データへのアクセス要求を受信するまでの時間分布関数F_i ^R(t)を、アクセス要求到着確率密度関数f_i ^R(t)に基づいて生成（式（１２））

（ｂ）次アクセスヒット時間分布関数生成部２３５が生成した確率α_i(t)と、時間分布関数F_i ^R(t)及びアクセス要求到着確率密度関数f_i ^R(t)に基づいて、キャッシュ有効時間分布関数G_i(t)を生成
キャッシュ有効時間分布関数G_i(t)は、時刻0からtの間にアクセス要求が到着し、アクセス要求の到着後時刻tまでに無効化要求が到着していない確率であるから、以下の式（１３）により求めることができる。

以上において、キャッシュ有効時間分布関数生成部２４０は、それぞれのアクセス対象データをキャッシュするか否かを設定する設定パラメータを入力とするキャッシュ有効時間分布関数G_i(t)を生成する。すなわち例えば、キャッシュ有効時間分布関数生成部２４０は、グループiのアクセス対象データをキャッシュしない場合に、グループiのアクセス要求到着確率密度関数f_i ^R(t)及び無効化要求到着確率密度関数f_i ^I(t)を"0"として上記の計算を行うキャッシュ有効時間分布関数G_i(t)を生成する。

次に、キャッシュヒット率推定関数生成部２４５は、それぞれのグループに属するアクセス対象データについて、複数のアクセス対象データのキャッシュ有効時間分布関数G_i(t)と、当該アクセス対象データに対する次アクセスヒット時間分布関数F_i(t)とに基づいて、当該アクセス対象データのキャッシュヒット率推定関数h_iを生成する（Ｓ４６０）。ここで、次アクセスヒット時間分布関数F_i(t)及びキャッシュ有効時間分布関数G_i(t)は設定パラメータを入力とする関数であるから、キャッシュヒット率推定関数生成部２４５は、当該設定パラメータを入力とするキャッシュヒット率推定関数h_iを生成することができる。

次に、アクセス処理性能推定関数生成部２５０は、それぞれのアクセス対象データのキャッシュヒット率推定関数h_i、キャッシュヒット時のアクセスコストC_i ^R、及びキャッシュミス時のアクセスコストC_i ^Cに基づいて、アクセス処理性能の推定関数Cを生成する（Ｓ４７０）。より具体的には、アクセス処理性能推定関数生成部２５０は、グループ対応統計情報取得部２１０及びアクセス要求到着頻度取得部２１５により算出されたグループiのアクセス対象データ数γ_i及びアクセス要求の平均到着頻度λ_iと、アクセス対象データのキャッシュヒット率推定関数h_iと、キャッシュヒット時及びミス時のアクセスコストC_i ^R及びC_i ^Cとに基づいて、以下の式（１４）によりアクセス処理性能の推定関数Cを生成する。

ここで、キャッシュヒット率推定関数h_iは設定パラメータを入力とする関数であるから、アクセス処理性能推定関数生成部２５０は、当該設定パラメータを入力とするアクセス処理性能推定関数Cを生成することができる。

次に、パラメータ変更部２５５は、キャッシュ装置１３０に設定された設定パラメータを、アクセス処理性能推定関数によるアクセス処理性能の推定値をより高める設定パラメータに変更する（Ｓ４８０）。本実施形態に係るパラメータ変更部２５５は、以下の（ａ）から（ｄ）に示す近傍探索法によりアクセス処理性能の推定値を高める設定パラメータを求め、キャッシュ装置１３０に設定する。

（ａ）現在の設定パラメータについてのアクセス処理性能の推定値を算出する。
（ｂ）最適パラメータを空集合に初期化する。
（ｃ）最適パラメータにおける各グループの設定パラメータについて、当該グループに属するアクセス対象データをキャッシュする場合及びキャッシュしない場合のアクセス処理性能の推定値を算出する。そして、当該アクセス対象データをキャッシュする場合に、キャッシュしない場合と比較してアクセス処理性能の推定値がより高くなることを条件として、当該グループに属するアクセス対象データをキャッシュする設定パラメータを最適パラメータに追加する。一方、当該アクセス対象データをキャッシュする場合に、キャッシュしない場合と比較してアクセス処理性能の推定値がより高くならないこと条件として、当該グループに属するアクセス対象データをキャッシュしない設定パラメータを最適パラメータに追加する。
（ｄ）全てのグループについて（ｃ）を行った結果得られた最適パラメータによるアクセス処理性能の推定値が、現在の設定パラメータについてのアクセス処理性能の推定値より高い場合に、最適パラメータをキャッシュ装置１３０に設定する。

なお、以上に示した（ｃ）の処理に代えて、パラメータ変更部２５５は、以下に示す処理を行ってもよい。
（ｃ’）現在の設定パラメータにおける各グループの設定パラメータについて、当該グループに属するアクセス対象データをキャッシュする設定となっている場合に、当該アクセス対象データをキャッシュしない場合のアクセス処理性能の推定値を算出する。そして、当該アクセス対象データをキャッシュしない場合に、最適パラメータと比較してアクセス処理性能の推定値が高くなることを条件として、現在の設定パラメータにおいて当該グループに属するアクセス対象データをキャッシュしないように変更した設定パラメータを最適パラメータとする。
一方、当該グループに属するアクセス対象データをキャッシュしない設定となっている場合に、当該アクセス対象データをキャッシュする場合のアクセス処理性能の推定値を算出する。そして、当該アクセス対象データをキャッシュする場合に、最適パラメータと比較してアクセス処理性能の推定値が高くなることを条件として、現在の設定パラメータにおいて当該グループに属するアクセス対象データをキャッシュする変更した設定パラメータを最適パラメータとする。

キャッシュ最適化装置１４０は、以上のＳ４１０からＳ４８０に示した処理を、例えば定期的に繰り返し行うことにより、キャッシュ装置１３０の設定パラメータを最適値に保つ（Ｓ４９０）。

以上の処理により、パラメータ変更部２５５は、アクセス対象データをキャッシュする場合に、キャッシュしない場合と比較してアクセス処理性能の推定値がより高くなることを条件として、当該アクセス対象データをキャッシュすることを指定する設定パラメータをキャッシュ装置１３０に設定することができる。そして、パラメータ変更部２５５は、アクセス処理性能推定関数Cに基づいて、全てのグループについてキャッシュ有無を指定する最適パラメータを予め求めてから、キャッシュ装置１３０に設定することができる。この結果、キャッシュ最適化装置１４０は、各グループについてキャッシュ有無を試行する場合と比較して、より効率良くキャッシュ装置１３０のアクセス処理性能を最適化することができる。

なお、キャッシュ装置１３０が、アクセス対象データをタイムアウト時に無効化する方式を採る場合、式（１１）及び式（１３）に示した次アクセスヒット時間分布関数F_i(t)及びキャッシュ有効時間分布関数G_i(t)に代えて、以下に示す時間分布関数を用いることもできる。

この方式においては、キャッシュ装置１３０は、キャッシュしているアクセス対象データに対して無効化要求を受信した場合、又は、当該アクセス対象データをキャッシュしてから当該アクセス対象データに対してアクセス要求を受けることなく予め定められたタイムアウト時間τ_iが経過した場合に、当該アクセス対象データをキャッシュから無効化する。このため、アクセス要求が到着してからタイムアウト時間τ_iの経過後は、次アクセスヒット時間分布関数F_i(t)及びキャッシュ有効時間分布関数G_i(t)が一定となる。そこで、次アクセスヒット時間分布関数生成部２３５及びキャッシュ有効時間分布関数生成部２４０は、予め定められたタイムアウト時間τ_iの経過前及び経過後の各区間について、異なる計算式を用いた次アクセスヒット時間分布関数F_i(t)及びキャッシュ有効時間分布関数G_i(t)を生成する（式（１５）及び式（１６））。

また、以上において、アクセス要求到着確率密度関数f_i ^R(t)及び無効化要求到着確率密度関数f_i ^I(t)が指数分布でない場合、式（１１）及び（１３）、又は式（１５）及び（１６）に示した積分関数を求めるのが困難となる場合がある。この場合において、次アクセスヒット時間分布関数生成部２３５及びキャッシュ有効時間分布関数生成部２４０は、線分で近似したアクセス要求到着確率密度関数f_i ^R(t)及び無効化要求到着確率密度関数f_i ^I(t)に基づいて、次アクセスヒット時間分布関数F_i(t)及びキャッシュ有効時間分布関数G_i(t)を生成してもよい。

図５は、本実施形態に係るキャッシュヒット率推定関数生成部２４５の構成を示す。キャッシュヒット率推定関数生成部２４５は、エントリ数期待値関数生成部５００と、キャッシュ充填時間算出部５１０と、次アクセスヒット率推定関数生成部５２０とを有する。

エントリ数期待値関数生成部５００は、複数のアクセス対象データのキャッシュ有効時間分布関数G_i(t)に基づいて、エントリ数期待値関数G(t)を生成する。エントリ数期待値関数G(t)とは、無効化されることなくキャッシュされているアクセス対象データの数の期待値を求める関数である。ここで、キャッシュ有効時間分布関数G_i(t)は、グループiに属する１つのアクセス対象データに関して、当該アクセス対象データへのアクセス要求を受信した時点を基準とし、時刻tまでにアクセス要求が到着し、かつ、時刻tまでに無効化されていない確率である。したがって、エントリ数期待値関数生成部５００は、キャッシュ有効時間分布関数G_i(t)にグループiに属するアクセス対象データの数γ_iを乗じて、無効化されることなくキャッシュされているグループiのアクセス対象データの数の期待値を求めることができる。そして、エントリ数期待値関数生成部５００は、式（１７）に示すように、この期待値を全てのグループについて合計することにより、エントリ数期待値関数G(t)を求めることができる。

キャッシュ充填時間算出部５１０は、エントリ数期待値関数G(t)に基づいて、予め定められた時点を基準として、K個のアクセス対象データがキャッシュされるまでのキャッシュ充填時間T_fillの期待値を算出する。より具体的には、キャッシュ充填時間算出部５１０は、エントリ数期待値関数G(t)の値がキャッシュサイズKとなるまでの時間の期待値を以下の式（１８）により算出し、キャッシュ充填時間T_fillの期待値とする。

次アクセスヒット率推定関数生成部５２０は、それぞれのアクセス対象データについて、当該アクセス対象データに対するアクセス要求を受信してからキャッシュ充填時間T_fillの期待値により定められる時間の経過までに当該アクセス対象データに対する次のアクセス要求を受信する確率の関数を、次アクセスヒット時間分布関数F_i(t)に基づいて算出し、当該アクセス対象データのキャッシュヒット率推定関数h_iとする。より具体的には、次アクセスヒット率推定関数生成部５２０は、キャッシュ充填時間T_fillが経過するまでに、注目するアクセス対象データへのアクセス要求が到着し、当該アクセス対象データが無効化されていない確率を、以下の式（１９）により算出し、キャッシュヒット率推定関数h_iとする。

以上に示したキャッシュ最適化装置１４０によれば、ＬＲＵ方式のキャッシュ装置１３０について、キャッシュミス時のアクセスコストがグループ間で異なる場合においても、各グループに属するアクセス対象データのキャッシュヒット率の推定値を解析的に求めることができる。そして、キャッシュ最適化装置１４０は、各グループについてのキャッシュヒット率に基づいて、アクセス処理性能の推定関数を精度良く求めることができる。この結果キャッシュ最適化装置１４０は、アクセス処理性能推定関数を用いて最適な設定パラメータを精度良く求めることができ、効率良くキャッシュ装置１３０のアクセス処理性能を高めることができる。

なお、アクセス対象データのタイムアウトを考慮した場合、時刻T_fillにおいてキャッシュされているアクセス対象データの数がK個であっても、時刻T_fill以前にK個を超えるアクセス対象データがキャッシュされた後タイムアウトにより無効化されたケースが考えられる。このようなケースにおいては、アクセス対象データがリプレースされるため、キャッシュミスとなる。したがって、キャッシュ最適化装置１４０は、上記の式（１７）から（１９）を満たすキャッシュヒット率推定関数h_iを、キャッシュヒット率の上界を与える近似式として用いる。

また、アクセス対象データのタイムアウトを考慮した場合、次アクセスヒット時間分布関数F_i(t)及びキャッシュ有効時間分布関数G_i(t)は、時刻τ_iで不連続となる。そこで、エントリ数期待値関数生成部５００は、各アクセス対象データをタイムアウト時間τ_iの値でソートし、複数のタイムアウト時間τ_iで区切られた各区間毎に、当該区間におけるキャッシュ充填時間T_fillの期待値を算出してもよい。

図６は、本実施形態の第１変形例に係るキャッシュ最適化装置１４０によるアクセス処理性能最適化方法の一例を示す。本変形例において、キャッシュ装置１３０は、それぞれのアクセス対象データ６００を、キャッシュ装置１３０のキャッシュ記憶領域１３５を分割した複数のキャッシュ分割領域６１０のうち、当該アクセス対象データに対応して予め定められたキャッシュ分割領域６１０にキャッシュする。

図６（ａ）はアクセス対象データ６００の配置変更によるアクセス処理性能最適化を示す。図６（ａ）において、キャッシュ装置１３０は、それぞれのアクセス対象データ６００を、設定パラメータにより定められた、当該アクセス対象データに対応するキャッシュ分割領域６１０にキャッシュする。そして、キャッシュ最適化装置１４０は、設定パラメータを変更して、それぞれのアクセス対象データ６００を、いずれのキャッシュ分割領域６１０にキャッシュするかを最適化することにより、キャッシュ装置１３０のアクセス処理性能を高める。

より具体的には、まずパラメータ設定部２００は、それぞれのアクセス対象データ６００を、いずれのキャッシュ分割領域６１０にキャッシュするかを設定パラメータの初期値によりキャッシュ装置１３０に設定する。ここでパラメータ設定部２００は、少なくとも１つのアクセス対象データ６００を、キャッシュしないことを設定してもよい。

次に、キャッシュヒット率推定関数生成部２４５及びアクセス処理性能推定関数生成部２５０は、それぞれのアクセス対象データ６００をいずれのキャッシュ分割領域６１０にキャッシュするか、又は、キャッシュしないかの対応を指定する組み合わせを入力とするキャッシュヒット率推定関数h_i及びアクセス処理性能推定関数Cを生成する。例えば、キャッシュヒット率推定関数生成部２４５及びアクセス処理性能推定関数生成部２５０は、キャッシュ分割領域６１０毎に、当該キャッシュ分割領域６１０にキャッシュされる各アクセス対象データについてのヒット率推定関数及びアクセス処理性能推定関数を生成し、キャッシュ分割領域６１０毎のアクセス処理性能推定関数を合計することにより、キャッシュ装置１３０のアクセス処理性能推定関数Cを生成する。

そして、パラメータ変更部２５５は、それぞれのアクセス対象データ６００をいずれのキャッシュ分割領域６１０にキャッシュするか、又は、キャッシュしないかの対応を第１の組み合わせとした場合に、第２の組み合わせとした場合と比較してアクセス処理性能の推定値がより高くなることを条件として、当該対応を第１の組み合わせとする設定パラメータをキャッシュ装置１３０に設定する。より具体的には、パラメータ変更部２５５は、図４のＳ４８０に関連して示した近傍探索法と同様にして、それぞれのアクセス対象データ６００をいずれのキャッシュ分割領域６１０にキャッシュするか、又は、キャッシュしないかの対応の最適パラメータを探索し、キャッシュ装置１３０に設定する。

図６（ｂ）はキャッシュ分割領域６１０のサイズ変更によるアクセス処理性能最適化を示す。図６（ｂ）において、キャッシュ最適化装置１４０は、設定パラメータを変更して、予めアクセス対象データ６００の割り当てが定められた複数のキャッシュ分割領域６１０のそれぞれについて、キャッシュ記憶領域１３５に対する当該キャッシュ分割領域６１０の割合を最適化することにより、キャッシュ装置１３０のアクセス処理性能を高める。

より具体的には、キャッシュヒット率推定関数生成部２４５及びアクセス処理性能推定関数生成部２５０は、キャッシュ記憶領域１３５に対する複数のキャッシュ分割領域６１０の割合の組み合わせを入力とするキャッシュヒット率推定関数h_i及び前記アクセス処理性能推定関数Cを生成する。例えばキャッシュヒット率推定関数生成部２４５及びアクセス処理性能推定関数生成部２５０は、キャッシュ分割領域６１０毎に、キャッシュできるアクセス対象データの個数Kを入力とする、当該キャッシュ分割領域６１０にキャッシュされる各アクセス対象データについてのヒット率推定関数及びアクセス処理性能推定関数を生成する。そして、キャッシュ分割領域６１０毎のアクセス処理性能推定関数を合計することにより、キャッシュ装置１３０のアクセス処理性能推定関数Cを生成する。

そして、パラメータ変更部２５５は、複数のキャッシュ分割領域６１０の割合の組み合わせを第１の組み合わせとした場合に、第２の組み合わせとした場合と比較してアクセス処理性能の推定値がより高くなることを条件として、複数のキャッシュ分割領域６１０の割合の組み合わせを第１の組み合わせとする設定パラメータをキャッシュ装置１３０に設定する。より具体的には、パラメータ変更部２５５は、最急勾配法を用いてアクセス処理性能の推定値を最大とするキャッシュ分割領域６１０の割合の組み合わせを求め、キャッシュ装置１３０に設定する。

以上に示した第１変形例に係るキャッシュ最適化装置１４０によれば、各アクセス対象データ６００を複数のキャッシュ分割領域６１０に割り当てる場合において、アクセス対象データ６００の割り当て及び／又は各キャッシュ分割領域６１０のサイズを最適化することができる。

図７は、本実施形態の第２変形例に係るキャッシュ装置１３０の構成を示す。本変形例に係るキャッシュ装置１３０は，優先度付のＬＲＵキャッシュ方式を採用する。キャッシュ装置１３０は、キャッシュ記憶領域１３５と、アクセス要求処理部７００と、ＬＲＵリスト管理部７１０と、エントリ移動部７３０と、ＬＲＵシフト部７４０と、統計情報計測部７５０とを備える。

アクセス要求処理部７００は、要求元装置１００からのアクセス要求を処理する。より具体的には、アクセス要求処理部７００は、アクセス要求に対応するアクセス対象データ６００がキャッシュ記憶領域１３５にキャッシュされているか否かを、ＬＲＵリスト管理部７１０により管理される情報に基づいて判定する。そして、アクセス要求処理部７００は、当該アクセス対象データ６００がキャッシュされている場合に、当該アクセス対象データ６００をキャッシュ記憶領域１３５から読み出して要求元装置１００へ返信する。一方、アクセス要求処理部７００は、当該アクセス対象データ６００がキャッシュされていない場合に、アクセス要求をサーバ装置１１０へ転送する。そしてアクセス要求処理部７００は、サーバ装置１１０から返信されたアクセス対象データ６００を要求元装置１００へ返信すると共にキャッシュ記憶領域１３５に登録する。

ＬＲＵリスト管理部７１０は、キャッシュ記憶領域１３５に記憶された複数のアクセス対象データ６００を管理する。本変形例において、それぞれのアクセス対象データ６００には、当該アクセス対象データ６００をキャッシュする優先度が定められる。このため、ＬＲＵリスト管理部７１０は、キャッシュされたアクセス対象データ６００をＬＲＵ方式により管理する、優先度毎に設けられた複数のＬＲＵリスト７１５を有する。各ＬＲＵリスト７１５は、キャッシュ記憶領域１３５に記憶されたアクセス対象データ６００を特定する１又は複数のポインタ７２０をリスト構造により管理する。

エントリ移動部７３０は、アクセス要求を受けたアクセス対象データ６００を、当該アクセス対象データ６００の優先度に対応するＬＲＵリスト７１５の先頭に移動する。これにより、エントリ移動部７３０は、各アクセス対象データ６００の優先度を反映させたＬＲＵキャッシュを実現することができる。

ＬＲＵシフト部７４０は、優先度が最も低いＬＲＵリスト７１５が空となった場合に、複数のＬＲＵリスト７１５のそれぞれに登録されたアクセス対象データ６００を、より優先度が低いＬＲＵリスト７１５に登録し直すシフト処理を行う。すなわち例えば、ＬＲＵリスト管理部７１０が第１から第３ＬＲＵリスト７１５を有し、第１ＬＲＵリスト７１５の優先度が最も低い場合において、ＬＲＵシフト部７４０は、第１ＬＲＵリスト７１５が空となったことを条件として、第２ＬＲＵリスト７１５に登録されたアクセス対象データ６００を第１ＬＲＵリスト７１５に登録し直し、第３ＬＲＵリスト７１５に登録されたアクセス対象データ６００を第２ＬＲＵリスト７１５に登録し直す。

統計情報計測部７５０は、例えばグループ対応アクセス要求回数requestFromClients_i、グループ対応キャッシュヒット回数hitsInMemory_i、グループ対応エントリ数entries_i、及びグループ対応無効化回数explicitInvalidation_i等の、アクセス要求及び／又はアクセス応答についての統計情報を計測し、キャッシュ最適化装置１４０内のグループ対応統計情報取得部２１０へ供給する。

以上に示したキャッシュ装置１３０によれば、より優先度が高いアクセス対象データ６００の方が、より優先度が高いＬＲＵリスト７１５に登録される。このため、キャッシュ装置１３０は、各アクセス対象データ６００を、優先度にほぼ比例した期間の間キャッシュ記憶領域１３５に滞在させることができる。

図８は、本実施形態の第２変形例に係るキャッシュヒット率推定関数生成部２４５の構成を示す。本変形例に係るキャッシュヒット率推定関数生成部２４５は、図７に示したキャッシュ装置１３０について各アクセス対象データのキャッシュヒット率推定関数h_iを生成することができる。図７に示したキャッシュ装置１３０においては、各ＬＲＵリスト７１５に対してシフト処理が行われる度に、不連続に状態が変化する。このため、本変形例に係るキャッシュヒット率推定関数生成部２４５は、定期的にＬＲＵリスト７１５がシフト処理が行われるものとして優先度付ＬＲＵキャッシュをモデル化する。

キャッシュヒット率推定関数生成部２４５は、エントリ数期待値関数生成部８００と、シフト周期算出部８１０と、リプレース時間算出部８２０と、次アクセスヒット率推定関数生成部８３０と、次アクセスヒット率平均化部８４０とを有する。エントリ数期待値関数生成部８００は、複数のアクセス対象データのキャッシュ有効時間分布関数G_i(t)に基づいて、エントリ数期待値関数H(t)を生成する。ここで、エントリ数期待値関数H(t)は、直前のシフト処理を基準として、時刻tにおける、複数のＬＲＵリスト７１５に登録されたアクセス対象データの合計数の期待値を求める関数である。より具体的には、エントリ数期待値関数生成部８００は、グループ毎のキャッシュ有効時間分布関数G_i(t)と、グループ毎のアクセス対象データの数γ_iと、グループ毎のアクセス対象データの優先度φ_iとに基づいて、以下の式（２０）によりエントリ数期待値関数H(t)を生成する。

式（２０）においては、各アクセス対象データは、その優先度φ_iの回数分シフトが起きなければキャッシュから掃き出されないことを反映し、キャッシュ有効時間分布関数への入力をφ_i・tとしている。

シフト周期算出部８１０は、エントリ数期待値関数H(t)に基づいて、シフト処理の周期の期待値Trを算出する。より具体的には、シフト周期算出部８１０は、エントリ数期待値関数H(t)の値がキャッシュサイズKとなるまでの時間の期待値を、以下の式（２１）により算出し、シフト処理の周期の期待値Trとする。

リプレース時間算出部８２０は、シフト処理の周期を複数に等分（例えばL等分）した各時点において、アクセス対象データへのアクセス要求を受けてから当該アクセス対象データが他のアクセス対象データに置換されるまでのリプレース時間の期待値G(t,l)を算出する。より具体的には、キャッシュ装置１３０においては、注目するアクセス対象データより優先度が高い他のアクセス対象データがキャッシュされていくことにより、当該アクセス対象データがリプレースされる。ここで、当該アクセス対象データは、シフト処理が行われる度に優先度が低下する結果、当該アクセス対象データのリプレースに寄与する他のアクセス対象データの数が増加していく。これらを反映し、リプレース時間算出部８２０は、グループiについてのキャッシュ有効時間分布関数G_i(t)及び優先度φ_iと、グループiに属するアクセス対象データの数γ_iと、シフト処理の周期の期待値Trとに基づいて、以下の式（２２）によりリプレース時間の期待値G(t,l)を算出する。

次アクセスヒット率推定関数生成部８３０は、それぞれのアクセス対象データについて、次アクセスヒット時間分布関数F_i(t)及びリプレース時間G(t,l)に基づいて、次アクセスヒット率推定関数h_i,lを生成する。ここで、次アクセスヒット率推定関数h_i,lは、シフト処理の周期をL等分した各時点において当該アクセス対象データに対するアクセス要求を受信してからリプレース時間の期待値により定められる時間Trの経過までに、当該アクセス対象データに対する次のアクセス要求を受信する確率である。より具体的には、次アクセスヒット率推定関数生成部８３０は、図５に示したキャッシュ充填時間算出部５１０及び次アクセスヒット率推定関数生成部５２０と同様にして、以下の式（２３）により次アクセスヒット率推定関数h_i,lを生成する。

次アクセスヒット率平均化部８４０は、それぞれのアクセス対象データについて、シフト処理の周期を複数に等分した複数の時点のそれぞれにおいて当該アクセス対象データに対するアクセス要求を受信した場合の次アクセスヒット率推定関数h_i,lを全ての時点について平均し、当該アクセス対象データのキャッシュヒット率推定関数h_iとする。すなわち、次アクセスヒット率平均化部８４０は、以下の式（２４）によりキャッシュヒット率推定関数h_iを生成する。

本変形例に係るキャッシュ最適化装置１４０によれば、パラメータ変更部２５５は、図４のＳ４８０に関して説明した近傍探索法と同様にして、各グループのアクセス対象データをキャッシュする優先度φ_iについて、アクセス処理性能の推定値を高める設定パラメータを求め、キャッシュ装置１３０に設定する。すなわち、キャッシュヒット率推定関数生成部２４５及びアクセス処理性能推定関数生成部２５０は、それぞれの前記アクセス対象データをキャッシュする優先度を入力とするキャッシュヒット率推定関数h_i及びアクセス処理性能推定関数Cを生成する。そして、パラメータ変更部２５５は、あるアクセス対象データをキャッシュする優先度を第１の優先度とした場合に、第２の優先度とした場合と比較してアクセス処理性能の推定値がより高くなることを条件として、当該アクセス対象データをキャッシュする優先度を第１の優先度とする設定パラメータをキャッシュ装置１３０に設定する。これにより、キャッシュ最適化装置１４０は、優先度付のＬＲＵキャッシュ方式を採用するキャッシュ装置１３０について、各アクセス対象データをキャッシュする優先度の設定パラメータを最適化することができる。

図９は、本実施形態に係る第３変形例に係るキャッシュ最適化装置１４０の構成を示す。図９において図２と同一符号を付した部材は、図２と同様の機能及び構成を備えるため、以下相違点を除き説明を省略する。

本変形例に係るキャッシュ最適化装置１４０は、複数のキャッシュ装置１３０に対する各アクセス対象データの割り当てを更に最適化する。これを実現するために、キャッシュ最適化装置１４０は、図２に示したキャッシュ最適化装置１４０に加え、統合時関数生成部９２０、グループ統合部９３０、分割時関数生成部９４０、及びグループ分割部９５０を備える。

統合時関数生成部９２０及びグループ統合部９３０は、複数のキャッシュ装置１３０における同一アクセス特性のグループを統合して、一のキャッシュ装置１３０におけるグループとする処理を行う。すなわち例えば、第１のキャッシュ装置１３０として機能する第１のＪＶＭと、第２のキャッシュ装置１３０として機能する第２のＪＶＭとが稼動している場合において、第１のＪＶＭのアクセス処理を、第２のＪＶＭに担当させるようにアクセス処理の割り当てを変更する。

統合時関数生成部９２０は、複数のキャッシュ装置１３０におけるそれぞれのグループを、一のキャッシュ装置１３０における対応するグループに統合した場合におけるアクセス処理性能推定関数Cを生成する。ここで、複数のグループを統合する場合、アクセス要求の総量γ_iλ_i及び無効化要求の総量γ_iμ_iは変化しない。一方、同一アクセス特性のグループを統合するため、当該グループに属するアクセス対象データの総数γ_iが変化する場合と、各アクセス対象データに対するアクセス要求及び無効化要求の平均到着頻度λ_i及びμ_iが変化する場合が有り得る。

アクセス対象データの総数γ_iが変化する場合の一例としては、複数のキャッシュ装置１３０が、異なる利用者に対して同一のサービスを提供している場合が挙げられる。このような場合には、アクセス処理を統合すると、各利用者についてのアクセス要求及び無効化要求の平均到着頻度は変化しないが、アクセス対象データの総数γ_iは統合前のアクセス対象データの数の合計となる。そこで統合時関数生成部９２０は、このケースにおいては、統合後のアクセス要求及び無効化要求の平均到着頻度λ_i及びμ_iを統合前の各キャッシュ装置１３０における平均到着頻度と同一とする一方、統合後のアクセス対象データの数γ_iを、統合前の各キャッシュ装置１３０におけるアクセス対象データの数の合計とするようグループ対応統計情報取得部２１０に指示する。この指示を受けると、グループ対応統計情報取得部２１０はアクセス対象データの数を変更し、アクセス要求到着頻度取得部２１５、無効化要求到着頻度取得部２２０、アクセス要求到着確率密度関数生成部２２５、無効化要求到着確率密度関数生成部２３０、次アクセスヒット時間分布関数生成部２３５、キャッシュ有効時間分布関数生成部２４０、キャッシュヒット率推定関数生成部２４５、及びアクセス処理性能推定関数生成部２５０は統合後のアクセス処理性能推定関数Cを生成する。

各アクセス対象データに対するアクセス要求及び無効化要求の平均到着頻度λ_i及びμ_iが変化する場合の一例としては、複数のキャッシュ装置１３０が、利用者からのアクセス処理に対してサービスを分散処理により提供している場合が挙げられる。このような場合には、アクセス処理を統合すると、アクセス対象データの数は変化しないが、各利用者についてのアクセス要求及び無効化要求の平均到着頻度λ_i及びμ_iは統合前の値の合計となる。そこで統合時関数生成部９２０は、このケースにおいては、統合後のアクセス要求及び無効化要求の平均到着頻度λ_i及びμ_iを、統合前の各キャッシュ装置１３０におけるアクセス要求及び無効化要求の平均到着頻度の合計とするようアクセス要求到着頻度取得部２１５及び無効化要求到着頻度取得部２２０に指示する。この指示を受けると、アクセス要求到着頻度取得部２１５及び無効化要求到着頻度取得部２２０はアクセス要求及び無効化要求の平均到着頻度を変更し、アクセス要求到着確率密度関数生成部２２５、無効化要求到着確率密度関数生成部２３０、次アクセスヒット時間分布関数生成部２３５、キャッシュ有効時間分布関数生成部２４０、キャッシュヒット率推定関数生成部２４５、及びアクセス処理性能推定関数生成部２５０は統合後のアクセス処理性能推定関数Cを生成する。

そして、統合時関数生成部９２０は、上記の指示により変更されたパラメータに基づいてアクセス処理性能推定関数生成部２５０により生成されたアクセス処理性能推定関数Cを取得することにより、統合後におけるアクセス処理性能推定関数C'を生成する。

グループ統合部９３０は、コンピュータ９００により生成されたアクセス処理性能推定関数C'によるアクセス処理性能の推定値が、複数のキャッシュ装置１３０のアクセス処理性能の推定値の合計より高い場合に、複数のキャッシュ装置１３０におけるそれぞれのグループを、一のキャッシュ装置１３０における対応するグループに統合する。すなわちグループ統合部９３０は、パラメータ変更部２５５を介してグループの統合をキャッシュ装置１３０に指示する。

分割時関数生成部９４０及びグループ分割部９５０は、一のキャッシュ装置１３０におけるグループを、複数のキャッシュ装置１３０に分割する処理を行う。すなわち例えば、第１のＪＶＭのアクセス処理を、新たに起動した第２のＪＶＭに一部分担させるようにアクセス処理の割り当てを変更する。

分割時関数生成部９４０は、一のキャッシュ装置１３０におけるそれぞれのグループを、複数のキャッシュ装置１３０における対応するグループに分割した場合における複数のキャッシュ装置１３０のそれぞれのアクセス処理性能推定関数を生成する。このようにグループを分割した場合においても、アクセス要求の総量γ_iλ_i及び無効化要求の総量γ_iμ_iは変化しない。一方、グループを統合する場合と同様に、各グループに属するアクセス対象データの数が変化する場合と、各アクセス対象データに対するアクセス要求及び無効化要求の平均到着頻度が変化する場合が有り得る。

アクセス対象データの数を変化させる場合、分割時関数生成部９４０は、分割後の各キャッシュ装置１３０における分割対象グループのアクセス対象データの数の合計値を、分割前のキャッシュ装置１３０における当該グループのアクセス対象データ数とするようにグループ対応統計情報取得部２１０に指示し、分割後の各キャッシュ装置１３０におけるアクセス対象データの数を変更する。この指示を受けると、グループ対応統計情報取得部２１０は、例えば分割前のキャッシュ装置１３０におけるアクセス対象データ数を、分割後のキャッシュ装置１３０の数で割る等の処理を行なって、分割後の各キャッシュ装置１３０におけるアクセス対象データの数を算出する。そして、アクセス要求到着頻度取得部２１５、無効化要求到着頻度取得部２２０、アクセス要求到着確率密度関数生成部２２５、無効化要求到着確率密度関数生成部２３０、次アクセスヒット時間分布関数生成部２３５、キャッシュ有効時間分布関数生成部２４０、キャッシュヒット率推定関数生成部２４５、及びアクセス処理性能推定関数生成部２５０は分割後の各キャッシュ装置１３０におけるアクセス処理性能推定関数を生成する。

一方、アクセス要求及び無効化要求の平均到着頻度を変化させる場合、分割時関数生成部９４０は、分割後の各キャッシュ装置１３０における平均到着頻度の合計値を、分割前のキャッシュ装置１３０における当該グループの平均到着頻度とするようアクセス要求到着頻度取得部２１５及び無効化要求到着頻度取得部２２０に指示し、分割後の各キャッシュ装置１３０における平均到着頻度を変更する。この指示を受けると、アクセス要求到着頻度取得部２１５及び無効化要求到着頻度取得部２２０は、例えば分割前のキャッシュ装置１３０における平均到着頻度を、分割後のキャッシュ装置１３０の数で割る等の処理を行なって、分割後の各キャッシュ装置１３０における平均到着頻度を算出する。そして、アクセス要求到着頻度取得部２１５、無効化要求到着頻度取得部２２０、アクセス要求到着確率密度関数生成部２２５、無効化要求到着確率密度関数生成部２３０、次アクセスヒット時間分布関数生成部２３５、キャッシュ有効時間分布関数生成部２４０、キャッシュヒット率推定関数生成部２４５、及びアクセス処理性能推定関数生成部２５０は分割後の各キャッシュ装置１３０におけるアクセス処理性能推定関数を生成する。

そして、分割時関数生成部９４０は、上記の指示により変更されたパラメータに基づいてアクセス処理性能推定関数生成部２５０により生成された各キャッシュ装置１３０のアクセス処理性能推定関数を取得することにより、分割後における各キャッシュ装置１３０のアクセス処理性能推定関数を生成する。

グループ分割部９５０は、分割時関数生成部９４０により生成されたアクセス処理性能推定関数によるアクセス処理性能の推定値の合計が、分割前の一のキャッシュ装置１３０のアクセス処理性能の推定値より高い場合に、一のキャッシュ装置１３０におけるそれぞれのグループを、複数のキャッシュ装置１３０における対応するグループに分割する。すなわち、グループ分割部９５０は、パラメータ変更部２５５を介してグループの分割をキャッシュ装置１３０に指示する。

以上に示したグループ統合部９３０及びグループ分割部９５０によれば、複数のグループを１つのグループに統合し、又は、１つのグループを複数に分割することにより、キャッシュ装置１３０の数をより好適に変化させることができる。更に、グループ統合部９３０及びグループ分割部９５０は、次のようにして協調動作することにより、複数のキャッシュ装置１３０の割り当てを初期状態に戻して割り当て直すことができる。
まず、グループ統合部９３０は、複数のキャッシュ装置１３０におけるそれぞれのグループを、一のキャッシュ装置１３０における対応するグループに統合する。次に、グループ分割部９５０は、一のキャッシュ装置１３０に統合されたグループを複数のキャッシュ装置１３０に分割した場合のアクセス処理性能の推定値を、異なる数のキャッシュ装置１３０に分割する場合のそれぞれについて求める。そして、グループ分割部９５０は、一のキャッシュ装置１３０に統合されたグループを、アクセス処理性能の推定値が最も高くなる数のキャッシュ装置１３０に分割する。

以上に示したキャッシュ最適化装置１４０によれば、複数のキャッシュ装置１３０を用いることができる場合において、グループの統合・分割により最適な数のキャッシュ装置１３０を用いてアクセス処理を行わせることができる。これによりキャッシュ最適化装置１４０は、アクセス要求の到着頻度に基づいてアプリケーションサーバを稼動させるＪＶＭの数を動的に変更し、ＳＬＡ（Service Level Agreement）を保証することができる。

図１０は、本実施形態に係るコンピュータ９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ９００は、ホスト・コントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、グラフィック・コントローラ１０７５、及び表示装置１０８０を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホスト・コントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＲＯＭ１０１０、フレキシブルディスク・ドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。

ホスト・コントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィック・コントローラ１０７５とを接続する。ＣＰＵ１０００は、ＲＯＭ１０１０及びＲＡＭ１０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィック・コントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。

入出力コントローラ１０８４は、ホスト・コントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、ＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ１０４０は、コンピュータ９００内のＣＰＵ１０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からプログラム又はデータを読み取り、ＲＡＭ１０２０を介してハードディスクドライブ１０４０に提供する。

また、入出力コントローラ１０８４には、ＲＯＭ１０１０と、フレキシブルディスク・ドライブ１０５０、及び入出力チップ１０７０の比較的低速な入出力装置とが接続される。ＲＯＭ１０１０は、コンピュータ９００が起動時に実行するブート・プログラムや、コンピュータ９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ１０５０は、フレキシブルディスク１０９０からプログラム又はデータを読み取り、ＲＡＭ１０２０を介してハードディスクドライブ１０４０に提供する。入出力チップ１０７０は、フレキシブルディスク・ドライブ１０５０や、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を接続する。

ＲＡＭ１０２０を介してハードディスクドライブ１０４０に提供されるプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ１０２０を介してコンピュータ９００内のハードディスクドライブ１０４０にインストールされ、ＣＰＵ１０００において実行される。

コンピュータ９００にインストールされ、コンピュータ９００をキャッシュ最適化装置１４０として機能させるプログラムは、パラメータ設定モジュールと、グループ対応統計情報取得モジュールと、アクセス要求到着頻度取得モジュールと、無効化要求到着頻度取得モジュールと、アクセス要求到着確率密度関数生成モジュールと、無効化要求到着確率密度関数生成モジュールと、次アクセスヒット時間分布関数生成モジュールと、キャッシュ有効時間分布関数生成モジュールと、キャッシュヒット率推定関数生成モジュールと、アクセス処理性能推定関数生成モジュールと、パラメータ変更モジュールと、統合時関数生成モジュールと、グループ統合モジュールと、分割時関数生成モジュールと、グループ分割モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ１０００等に働きかけて、コンピュータ９００を、パラメータ設定部２００と、グループ対応統計情報取得部２１０と、アクセス要求到着頻度取得部２１５と、無効化要求到着頻度取得部２２０と、アクセス要求到着確率密度関数生成部２２５と、無効化要求到着確率密度関数生成部２３０と、次アクセスヒット時間分布関数生成部２３５と、キャッシュ有効時間分布関数生成部２４０と、キャッシュヒット率推定関数生成部２４５と、アクセス処理性能推定関数生成部２５０と、パラメータ変更部２５５と、統合時関数生成部９２０と、グループ統合部９３０と、分割時関数生成部９４０と、グループ分割部９５０としてそれぞれ機能させる。

グループ対応統計情報取得モジュールは、グループ対応キャッシュヒット率取得モジュールと、グループ対応エントリ数取得モジュールと、アクセス対象で−多数算出モジュールと、グループ対応無効化数取得モジュールとを有する。これらのプログラム又はモジュールは、ＣＰＵ１０００等に働きかけて、コンピュータ９００を、グループ対応キャッシュヒット率取得部３００と、グループ対応エントリ数取得部３１０と、アクセス対象データ数算出部３２０と、グループ対応無効化数取得部３３０としてそれぞれ機能させる。

キャッシュヒット率推定関数生成モジュールは、エントリ数期待値関数生成モジュール、キャッシュ充填時間算出モジュール、及び次アクセスヒット率推定関数生成モジュール、又は、エントリ数期待値関数生成モジュール、シフト周期算出モジュール、リプレース時間算出モジュール、次アクセスヒット率推定関数生成モジュール、及び次アクセスヒット率平均化モジュールを有する。これらのプログラム又はモジュールは、ＣＰＵ１０００等に働きかけて、コンピュータ９００を、エントリ数期待値関数生成部５００、キャッシュ充填時間算出部５１０、次アクセスヒット率推定関数生成部５２０、エントリ数期待値関数生成部８００、シフト周期算出部８１０、リプレース時間算出部８２０、次アクセスヒット率推定関数生成部８３０、及び次アクセスヒット率平均化部８４０としてそれぞれ機能させる。

以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ９００に提供してもよい。

以上に示したキャッシュ最適化装置１４０によれば、人手による最適設定が困難であったＷｅｂアプリケーションに関するキャッシュの構成及びポリシーの設定を効率良く行うことができる。また、本実施形態に係るキャッシュ最適化装置１４０によれば、ＬＲＵキャッシュ又は優先度付ＬＲＵキャッシュを備える各種のキャッシュ装置１３０について、キャッシュヒット率の近似値を算出することができ、算出したキャッシュヒット率に基づいて最適な設定パラメータを効率良く設定することができる。

以下に、本実施形態において示した式（１９）又は式（２４）によるキャッシュヒット率の推定値と、イベント駆動型シミュレーションにより求めたキャッシュヒット率との比較結果を示す。この比較においては、２５０個のアクセス対象データをそれぞれ有する４つのグループからなるキャッシュモデルを用いて、キャッシュサイズKを100から1000まで100単位で変化させながら、アクセス要求のみ受ける場合、アクセス要求及び無効化要求を受ける場合、更にタイムアウトにより無効化される場合、及び、更に優先度を考慮する場合のそれぞれについて評価を行った。この結果、式（１９）又は式（２４）によるキャッシュヒット率の推定値とイベント駆動型シミュレーションによるキャッシュヒット率の差は最大で0.016であった。このことから、本実施形態に係るキャッシュ最適化装置１４０は、キャッシュヒット率を、イベント駆動型シミュレーションと同等の精度で関数計算により高速に求めることができると言える。

以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。

例えば、キャッシュ装置１３０が、アクセス対象データの更新時にキャッシュを更新する方式を採る場合、式（１４）に示したアクセス処理性能推定関数に代えて、式（２５）に示したアクセス処理性能推定関数を用いてもよい。

式（２５）においては、アクセス対象データ更新の平均頻度をμ_i、更新処理のコストをC_i ^μとし、キャッシュヒット率h_iはアクセス要求及び更新要求の合計値とする。

本発明の実施形態に係る情報システム１０の構成を示す。 本発明の実施形態に係るキャッシュ最適化装置１４０の構成を示す。 本発明の実施形態に係るグループ対応統計情報取得部２１０の構成を示す。 本発明の実施形態に係るキャッシュ最適化装置１４０の動作フローを示す。 本発明の実施形態に係るキャッシュヒット率推定関数生成部２４５の構成を示す。 本発明の実施形態の第１変形例に係るキャッシュ最適化装置１４０によるアクセス処理性能最適化方法を示す。図６（ａ）はアクセス対象データ６００の配置変更によるアクセス処理性能最適化を、図６（ｂ）はキャッシュ分割領域６１０のサイズ変更によるアクセス処理性能最適化を示す。 本発明の実施形態の第２変形例に係るキャッシュ装置１３０の構成を示す。 本発明の実施形態の第２変形例に係るキャッシュヒット率推定関数生成部２４５の構成を示す。 本発明の実施形態に係る第３変形例に係るキャッシュ最適化装置１４０の構成を示す。 本発明の実施形態に係るコンピュータ９００のハードウェア構成の一例を示す。

符号の説明

１０ 情報システム
１００ 要求元装置
１１０ サーバ装置
１２０ キャッシュシステム
１３０ キャッシュ装置
１３５ キャッシュ記憶領域
１４０ キャッシュ最適化装置
２００ パラメータ設定部
２１０ グループ対応統計情報取得部
２１５ アクセス要求到着頻度取得部
２２０ 無効化要求到着頻度取得部
２２５ アクセス要求到着確率密度関数生成部
２３０ 無効化要求到着確率密度関数生成部
２３５ 次アクセスヒット時間分布関数生成部
２４０ キャッシュ有効時間分布関数生成部
２４５ キャッシュヒット率推定関数生成部
２５０ アクセス処理性能推定関数生成部
２５５ パラメータ変更部
３００ グループ対応キャッシュヒット率取得部
３１０ グループ対応エントリ数取得部
３２０ アクセス対象データ数算出部
３３０ グループ対応無効化数取得部
５００ エントリ数期待値関数生成部
５１０ キャッシュ充填時間算出部
５２０ 次アクセスヒット率推定関数生成部
６００ アクセス対象データ
６１０ キャッシュ分割領域
７００ アクセス要求処理部
７１０ ＬＲＵリスト管理部
７１５ ＬＲＵリスト
７２０ ポインタ
７３０ エントリ移動部
７４０ ＬＲＵシフト部
７５０ 統計情報計測部
８００ エントリ数期待値関数生成部
８１０ シフト周期算出部
８２０ リプレース時間算出部
８３０ 次アクセスヒット率推定関数生成部
８４０ 次アクセスヒット率平均化部
９２０ 統合時関数生成部
９３０ グループ統合部
９４０ 分割時関数生成部
９５０ グループ分割部
９００ コンピュータ
１０００ ＣＰＵ
１０１０ ＲＯＭ
１０２０ ＲＡＭ
１０３０ 通信インターフェイス
１０４０ ハードディスクドライブ
１０５０ フレキシブルディスク・ドライブ
１０６０ ＣＤ−ＲＯＭドライブ
１０７０ 入出力チップ
１０７５ グラフィック・コントローラ
１０８０ 表示装置
１０８２ ホスト・コントローラ
１０８４ 入出力コントローラ
１０９０ フレキシブルディスク
１０９５ ＣＤ−ＲＯＭ

Claims (18)

1. 要求元装置からアクセスされたアクセス対象データをキャッシュするキャッシュ装置のキャッシュヒット率を推定するキャッシュヒット率推定装置であって、
   複数の前記アクセス対象データの少なくとも１つは、キャッシュミス時のアクセスコストが他の前記アクセス対象データと異なるものであり、
   それぞれの前記アクセス対象データに対するアクセス要求について計測された平均到着頻度を取得するアクセス要求到着頻度取得部と、
   それぞれのアクセス対象データに対するアクセス要求の平均到着頻度に基づいて、当該アクセス対象データに対するアクセス要求の到着時間間隔の確率密度関数であるアクセス要求到着確率密度関数を生成するアクセス要求到着確率密度関数生成部と、
   前記複数のアクセス対象データの前記アクセス要求到着確率密度関数に基づいて、それぞれの前記アクセス対象データのキャッシュヒット率の推定関数を生成するキャッシュヒット率推定関数生成部と
   を備えるキャッシュヒット率推定装置。
2. 前記要求元装置からのアクセス要求に対するアクセス処理性能を変化させる設定パラメータを前記キャッシュ装置に設定するパラメータ設定部と、
   それぞれの前記アクセス対象データの前記キャッシュヒット率推定関数及び前記キャッシュミス時のアクセスコストに基づいて、前記アクセス処理性能の推定関数を生成するアクセス処理性能推定関数生成部と、
   前記キャッシュ装置に設定された前記設定パラメータを、前記アクセス処理性能推定関数による前記アクセス処理性能の推定値をより高める前記設定パラメータに変更するパラメータ変更部と
   を更に備える請求項１記載のキャッシュヒット率推定装置。
3. 前記キャッシュヒット率推定関数生成部及び前記アクセス処理性能推定関数生成部は、それぞれの前記アクセス対象データをキャッシュするか否かを設定する設定パラメータを入力とする前記キャッシュヒット率推定関数及び前記アクセス処理性能推定関数を生成し、
   前記パラメータ変更部は、一の前記アクセス対象データをキャッシュする場合に、キャッシュしない場合と比較して前記アクセス処理性能の推定値がより高くなることを条件として、前記一のアクセス対象データをキャッシュすることを指定する前記設定パラメータを前記キャッシュ装置に設定する
   請求項２記載のキャッシュヒット率推定装置。
4. 前記キャッシュヒット率推定関数生成部及び前記アクセス処理性能推定関数生成部は、それぞれの前記アクセス対象データをキャッシュする優先度を入力とする前記キャッシュヒット率推定関数及び前記アクセス処理性能推定関数を生成し、
   前記パラメータ変更部は、一の前記アクセス対象データをキャッシュする優先度を第１の優先度とした場合に、第２の優先度とした場合と比較して前記アクセス処理性能の推定値がより高くなることを条件として、前記一のアクセス対象データをキャッシュする優先度を前記第１の優先度とする前記設定パラメータを前記キャッシュ装置に設定する
   請求項２記載のキャッシュヒット率推定装置。
5. 前記キャッシュ装置は、前記複数のアクセス対象データのそれぞれを、当該キャッシュ装置のキャッシュ記憶領域を分割した複数のキャッシュ分割領域のうち、当該アクセス対象データに対応する予め定められたキャッシュ分割領域にキャッシュし、
   前記キャッシュヒット率推定関数生成部及び前記アクセス処理性能推定関数生成部は、前記キャッシュ記憶領域に対する前記複数のキャッシュ分割領域の割合の組み合わせを入力とする前記キャッシュヒット率推定関数及び前記アクセス処理性能推定関数を生成し、
   前記パラメータ変更部は、前記複数のキャッシュ分割領域の割合の組み合わせを第１の組み合わせとした場合に、第２の組み合わせとした場合と比較して前記アクセス処理性能の推定値がより高くなることを条件として、前記複数のキャッシュ分割領域の割合の組み合わせを第１の組み合わせとする前記設定パラメータを前記キャッシュ装置に設定する
   請求項２記載のキャッシュヒット率推定装置。
6. 前記キャッシュ装置は、それぞれの前記アクセス対象データを、当該キャッシュ装置のキャッシュ記憶領域を分割した複数のキャッシュ分割領域のうち、当該アクセス対象データに対応する予め定められたキャッシュ分割領域にキャッシュし、
   前記キャッシュヒット率推定関数生成部及び前記アクセス処理性能推定関数生成部は、それぞれの前記アクセス対象データをいずれの前記キャッシュ分割領域にキャッシュするかの対応を指定する組み合わせを入力とする前記キャッシュヒット率推定関数及び前記アクセス処理性能推定関数を生成し、
   前記パラメータ変更部は、前記対応を第１の組み合わせとした場合に、第２の組み合わせとした場合と比較して前記アクセス処理性能の推定値がより高くなることを条件として、前記対応を第１の組み合わせとする前記設定パラメータを前記キャッシュ装置に設定する
   請求項２記載のキャッシュヒット率推定装置。
7. それぞれの前記アクセス対象データについて、前記アクセス要求到着確率密度関数に基づいて、当該アクセス対象データへの前記アクセス要求を受信した後、当該アクセス対象データがキャッシュから無効化される前に当該アクセス対象データに対する次の前記アクセス要求を受信する確率の時間分布である次アクセスヒット時間分布関数を生成する次アクセスヒット時間分布関数生成部と、
   それぞれの前記アクセス対象データについて、前記アクセス要求到着確率密度関数に基づいて、予め定められた時点を基準とし、当該アクセス対象データに対する少なくとも１つの前記アクセス要求を受信し、かつ、当該アクセス対象データがキャッシュから無効化されていない確率の時間分布であるキャッシュ有効時間分布関数を生成するキャッシュ有効時間分布関数生成部を更に備え、
   前記キャッシュヒット率推定関数生成部は、それぞれの前記アクセス対象データについて、前記複数のアクセス対象データの前記キャッシュ有効時間分布関数と、当該アクセス対象データに対する前記次アクセスヒット時間分布関数とに基づいて、当該アクセス対象データの前記キャッシュヒット率推定関数を生成する
   請求項２記載のキャッシュヒット率推定装置。
8. それぞれの前記アクセス対象データについて、当該アクセス対象データに対する無効化要求の平均到着頻度に基づいて、無効化要求の到着時間間隔の確率密度関数である無効化要求到着確率密度関数を生成する無効化要求到着確率密度関数生成部を更に備え、
   前記次アクセスヒット時間分布関数生成部及び前記キャッシュ有効時間分布関数生成部は、前記無効化要求到着確率密度関数に更に基づいて、前記次アクセスヒット時間分布関数及び前記キャッシュ有効時間分布関数を生成する
   請求項７記載のキャッシュヒット率推定装置。
9. 前記キャッシュ装置は、キャッシュしている前記アクセス対象データに対して無効化要求を受信した場合、又は、当該アクセス対象データをキャッシュしてから当該アクセス対象データに対して前記アクセス要求を受けることなく予め定められた時間が経過した場合に当該アクセス対象データをキャッシュから無効化し、
   前記次アクセスヒット時間分布関数生成部及び前記キャッシュ有効時間分布関数生成部は、前記予め定められた時間の経過前及び経過後の各区間について前記次アクセスヒット時間分布関数及び前記キャッシュ有効時間分布関数を生成する
   請求項８記載のキャッシュヒット率推定装置。
10. 前記キャッシュ装置は、最大Ｋ個の前記アクセス対象データをＬＲＵ（Least Recently Used）方式によりキャッシュし、
    前記キャッシュヒット率推定関数生成部は、
    前記複数のアクセス対象データの前記キャッシュ有効時間分布関数に基づいて、無効化されることなくキャッシュされている前記アクセス対象データの数の期待値を求めるエントリ数期待値関数を生成するエントリ数期待値関数生成部と、
    前記エントリ数期待値関数に基づいて、予め定められた時点を基準として、Ｋ個の前記アクセス対象データがキャッシュされるまでのキャッシュ充填時間の期待値を算出するキャッシュ充填時間算出部と、
    それぞれの前記アクセス対象データについて、当該アクセス対象データに対するアクセス要求を受信してから前記キャッシュ充填時間の期待値により定められる時間の経過までに当該アクセス対象データに対する次のアクセス要求を受信する確率の関数を前記次アクセスヒット時間分布関数に基づいて算出し、当該アクセス対象データの前記キャッシュヒット率推定関数とする次アクセスヒット率推定関数生成部と
    を有する
    請求項７記載のキャッシュヒット率推定装置。
11. それぞれの前記アクセス対象データには、当該アクセス対象データをキャッシュする優先度が定められており、
    前記キャッシュ装置は、
    キャッシュされた前記アクセス対象データをＬＲＵ方式により管理する、優先度毎に設けられた複数のＬＲＵリストと、
    アクセス要求を受けた前記アクセス対象データを、当該アクセス対象データの優先度に対応する前記ＬＲＵリストの先頭に移動するエントリ移動部と、
    優先度が最も低い前記ＬＲＵリストが空である場合に、前記複数のＬＲＵリストのそれぞれに登録された前記アクセス対象データを、より優先度が低い前記ＬＲＵリストに登録し直すシフト処理を行うＬＲＵリストシフト部と
    を備え、
    前記キャッシュヒット率推定関数生成部は、
    前記複数のアクセス対象データの前記キャッシュ有効時間分布関数に基づいて、前記複数のＬＲＵリストに登録された前記アクセス対象データの合計数の期待値を求めるエントリ数期待値関数を生成するエントリ数期待値関数生成部と、
    前記エントリ数期待値関数に基づいて、前記シフト処理の周期の期待値を算出するシフト周期算出部と、
    前記シフト処理の周期を複数に等分した各時点において前記アクセス対象データへのアクセス要求を受けてから当該アクセス対象データが他の前記アクセス対象データに置換されるまでのリプレース時間の期待値を算出するリプレース時間算出部と、
    それぞれの前記アクセス対象データについて、前記シフト処理の周期を複数に等分した各時点において当該アクセス対象データに対するアクセス要求を受信してから前記リプレース時間の期待値により定められる時間の経過までに当該アクセス対象データに対する次のアクセス要求を受信する確率を算出する次アクセスヒット率推定関数を、前記次アクセスヒット時間分布関数及び前記リプレース時間に基づいて生成する次アクセスヒット率推定関数生成部と、
    それぞれの前記アクセス対象データについて、前記シフト処理の周期を複数に等分した前記複数の時点のそれぞれにおいて当該アクセス対象データに対するアクセス要求を受信した場合の前記次アクセスヒット率推定関数を全ての前記時点について平均し、当該アクセス対象データの前記キャッシュヒット率推定関数とする次アクセスヒット率平均化部と
    を有する
    請求項７記載のキャッシュヒット率推定装置。
12. 前記アクセス対象データは、前記アクセス要求を受信したサーバ装置上で当該アクセス要求に対応するサーバプログラムを、前記アクセスコストにより指定される処理時間実行することにより生成され、
    前記キャッシュ装置は、前記サーバ装置により生成された前記アクセス対象データをキャッシュするキャッシュ記憶領域を備える
    請求項２記載のキャッシュヒット率推定装置。
13. それぞれの前記アクセス対象データは、複数のグループのいずれかに属し、
    それぞれの前記グループについて、当該グループに属する全ての前記アクセス対象データについて計測された平均キャッシュヒット率を取得するグループ対応キャッシュヒット率取得部と、
    それぞれの前記グループについて、当該グループに属する全ての前記アクセス対象データのうちキャッシュしている前記アクセス対象データの個数であるグループ対応エントリ数の計測値を取得するグループ対応エントリ数取得部と、
    それぞれの前記グループについて、当該グループの前記グループ対応エントリ数を当該グループの前記平均キャッシュヒット率で割ることにより、当該グループに属する前記アクセス対象データの数の推定値を算出するアクセス対象データ数算出部と
    を備え、
    前記アクセス要求到着頻度取得部は、それぞれの前記グループについて、当該グループに属する全アクセス対象データについて計測された前記アクセス要求の平均到着頻度を当該グループに属する前記アクセス対象データの数の推定値で割ることにより、当該アクセス対象データの平均到着頻度を取得し、
    前記キャッシュヒット率推定関数生成部は、それぞれの前記グループに属する前記アクセス対象データの前記キャッシュヒット率推定関数を、当該グループに属する前記アクセス対象データの数の推定値に更に基づいて生成する
    請求項２記載のキャッシュヒット率推定装置。
14. 複数の前記キャッシュ装置におけるそれぞれの前記グループを、一の前記キャッシュ装置における対応する前記グループに統合した場合における前記アクセス処理性能推定関数を生成する統合時関数生成部と、
    前記統合時関数生成部により生成された前記アクセス処理性能推定関数による前記アクセス処理性能の推定値が、前記複数のキャッシュ装置の前記アクセス処理性能の推定値の合計より高い場合に、前記複数のキャッシュ装置におけるそれぞれの前記グループを、前記一のキャッシュ装置における対応する前記グループに統合するグループ統合部と
    を更に備える
    請求項１３記載のキャッシュヒット率推定装置。
15. 一の前記キャッシュ装置におけるそれぞれの前記グループを、複数の前記キャッシュ装置における対応する前記グループに分割した場合における前記複数のキャッシュ装置のそれぞれの前記アクセス処理性能推定関数を生成する分割時関数生成部と、
    前記分割時関数生成部により生成された前記アクセス処理性能推定関数による前記アクセス処理性能の推定値の合計が、前記一のキャッシュ装置の前記アクセス処理性能の推定値より高い場合に、前記一の前記キャッシュ装置におけるそれぞれの前記グループを、複数の前記キャッシュ装置における対応する前記グループに分割するグループ分割部と
    を更に備える
    請求項１３記載のキャッシュヒット率推定装置。
16. 要求元装置からアクセスされたアクセス対象データをキャッシュするキャッシュ装置のキャッシュヒット率をコンピュータにより推定するキャッシュヒット率推定方法であって、
    複数の前記アクセス対象データの少なくとも１つは、キャッシュミス時のアクセスコストが他の前記アクセス対象データと異なるものであり、
    それぞれの前記アクセス対象データに対するアクセス要求について計測された平均到着頻度を取得するアクセス要求到着頻度取得段階と、
    それぞれのアクセス対象データに対するアクセス要求の平均到着頻度に基づいて、当該アクセス対象データに対するアクセス要求の到着時間間隔の確率密度関数であるアクセス要求到着確率密度関数を生成するアクセス要求到着確率密度関数生成段階と、
    前記複数のアクセス対象データの前記アクセス要求到着確率密度関数に基づいて、それぞれの前記アクセス対象データのキャッシュヒット率の推定関数を生成するキャッシュヒット率推定関数生成段階と
    を備えるキャッシュヒット率推定方法。
17. 要求元装置からアクセスされたアクセス対象データをキャッシュするキャッシュ装置のキャッシュヒット率を推定するキャッシュヒット率推定装置用のプログラムであって、
    複数の前記アクセス対象データの少なくとも１つは、キャッシュミス時のアクセスコストが他の前記アクセス対象データと異なるものであり、
    当該プログラムは、前記キャッシュヒット率推定装置を、
    それぞれの前記アクセス対象データに対するアクセス要求について計測された平均到着頻度を取得するアクセス要求到着頻度取得部と、
    それぞれのアクセス対象データに対するアクセス要求の平均到着頻度に基づいて、当該アクセス対象データに対するアクセス要求の到着時間間隔の確率密度関数であるアクセス要求到着確率密度関数を生成するアクセス要求到着確率密度関数生成部と、
    前記複数のアクセス対象データの前記アクセス要求到着確率密度関数に基づいて、それぞれの前記アクセス対象データのキャッシュヒット率の推定関数を生成するキャッシュヒット率推定関数生成部と
    して機能させるプログラム。
18. 請求項１７に記載のプログラムを記録した、コンピュータにより読み取り可能な記録媒体。

Images