(57)【要約】【課題】本発明は、データベースに高い頻度で更新処理が行われる環境においても、参照速度が低下せず、処理負荷の増大を最小限に抑えるキャッシュメンテナンス技術を提供する。【解決手段】キャッシュメンテナンス装置１は、キャッシュエントリ更新情報を記憶する更新情報記憶部１１と、メンテナンス条件を記憶するメンテナンス条件記憶部２１と、メンテナンス条件を生成してメンテナンス条件記憶部２１に書き込むメンテナンス条件生成部３１と、メンテナンスの対象となるキャッシュエントリ１ＣＥを選択するメンテナンス対象選択部４１と、メンテナンス条件を満たすか否かを判定するメンテナンス判定部５１と、キャッシュエントリ１ＣＥをメンテナンスするキャッシュメンテナンス部６１と、を備える。【選択図】図１
2010198258.tif 000002
【特許請求の範囲】
【請求項１】
１以上のコンピュータのメモリで構成されるキャッシュにデータベースからのデータを保存する分散メモリキャッシュにおける、前記データを前記キャッシュに保存する単位となるキャッシュエントリをメンテナンスするキャッシュメンテナンス装置において、
前記キャッシュエントリをメンテナンスする条件であるメンテナンス条件を記憶するメンテナンス条件記憶部と、
前記メンテナンス条件記憶部に記憶したメンテナンス条件を参照し、前記メンテナンス条件を満たすときにメンテナンス可能と判定するメンテナンス判定部と、
前記メンテナンス判定部がメンテナンス可能と判定した場合、前記キャッシュエントリをメンテナンスするキャッシュメンテナンス部と、
を備えることを特徴とするキャッシュメンテナンス装置。
【請求項２】
前回のメンテナンス時刻、及び、前回の前記メンテナンス時刻以後に前記データが更新された回数を示す更新回数の少なくとも一方を含む更新情報を記憶する更新情報記憶部と、
予め設定された許容遅延回数及び許容遅延時間の少なくとも一方が入力され、当該入力に基づいて、前記メンテナンス条件を生成して前記メンテナンス条件記憶部に書き込むメンテナンス条件生成部と、をさらに備え、
前記メンテナンス条件生成部は、
前記許容遅延回数のみが入力された場合、前記更新回数が前記許容遅延回数を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、
前記許容遅延時間のみが入力された場合、前回の前記メンテナンス時刻から現在時刻までを示す経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、
前記許容遅延回数と前記許容遅延時間とが入力された場合、前記更新回数が前記許容遅延回数を超えたとき又は前記経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成することを特徴とする請求項１に記載のキャッシュメンテナンス装置。
【請求項３】
予め設定された許容遅延回数及び許容遅延時間の少なくとも一方が入力され、当該入力に基づいて、前記メンテナンス条件を生成して前記メンテナンス条件記憶部に書き込むメンテナンス条件生成部、をさらに備え、
前記メンテナンス条件生成部は、
前記許容遅延回数のみが入力された場合、更新回数が前記許容遅延回数を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、
前記許容遅延時間のみが入力された場合、経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、
前記許容遅延回数と前記許容遅延時間とが入力された場合、前記更新回数が前記許容遅延回数を超えたとき又は前記経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、
前記メンテナンス判定部は、
前記データベースのテーブルにおける差分データを格納した差分テーブルを参照し、当該差分テーブルのデータ件数を前記更新回数として算出すると共に、当該差分テーブルにおける最も古いデータを格納した時刻から現在時刻までを前記経過時間として算出し、算出した前記更新回数と前記経過時間とを用いて前記メンテナンス条件を満たすか判定し、
前記キャッシュメンテナンス部は、
前記差分テーブルに格納した前記差分データで前記キャッシュエントリを一括して更新すると共に、更新した前記差分データを前記差分テーブルから削除することを特徴とする請求項１に記載のキャッシュメンテナンス装置。
【請求項４】
前回のメンテナンス時刻、及び、前回の前記メンテナンス時刻以後に前記データが更新された回数を示す更新回数の少なくとも一方を含む更新情報を記憶する更新情報記憶部と、
予め設定された許容遅延回数及び許容遅延時間の少なくとも一方と、メンテナンスコストの目標負荷値とが入力され、当該入力に基づいて、前記キャッシュエントリ毎に前記メンテナンス条件を生成して前記メンテナンス条件記憶部に書き込むメンテナンス条件生成部と、
予め設定された統計期間における前記キャッシュエントリをメンテナンスした回数を示すメンテナンス回数の累積値を統計情報として算出する統計情報算出部と、をさらに備え、
前記メンテナンス条件生成部は、
前記メンテナンス回数の累積値に前記目標負荷値を乗じて削減目標値を算出し、
前記許容遅延回数のみが入力された場合、前記更新回数が前記許容遅延回数を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、式（１）で算出した削減値を前記削減目標値から減算し、
前記許容遅延時間のみが入力された場合、前回の前記メンテナンス時刻から現在時刻までを示す経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、式（２）で算出した削減値を前記削減目標値から減算し、
前記許容遅延回数と前記許容遅延時間とが入力された場合、前記更新回数が前記許容遅延回数を超えたとき又は前記経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、式（３）で算出した削減値を前記削減目標値から減算し、
前記削減目標値から前記削減値を減算した値が０以下になったときは、前記メンテナンス条件の生成を終了することを特徴とする請求項１に記載のキャッシュメンテナンス装置。
Ａ＝Ｍｉ×（Ｎ−１）／Ｎ・・・式（１）
Ａ＝Ｍｉ×（１−Ｔ／Ｓ）・・・式（２）
Ａ＝ＭＩＮ［｛Ｍｉ×（Ｎ−１）／Ｎ｝，{Ｍｉ×（１−Ｔ／Ｓ）}］・・・式（３）
但し、式（１）〜式（３）において、Ａは削減値、Ｍｉはメンテナンス回数の累積値、Ｎは許容遅延回数、Ｔは許容遅延時間、及び、Ｓは統計期間である。
【請求項５】
前記メンテナンス条件生成部は、前記メンテナンス条件を生成しておらず、かつ、前記メンテナンス回数の累積値が最大となる前記キャッシュエントリについて、前記メンテナンス条件を生成することを特徴とする請求項４に記載のキャッシュメンテナンス装置。
【請求項６】
前記統計情報算出部は、前記統計情報として、前記統計期間における前記キャッシュエントリが参照された参照回数の累積値を算出し、
前記メンテナンス条件生成部は、前記メンテナンス条件を生成しておらず、かつ、前記参照回数の累積値が最小となる前記キャッシュエントリについて、前記メンテナンス条件を生成することを特徴とする請求項４に記載のキャッシュメンテナンス装置。
【請求項７】
前回のメンテナンス時刻、及び、前回の前記メンテナンス時刻以後に前記データが更新された回数を示す更新回数の少なくとも一方を含む更新情報を記憶する更新情報記憶部と、
予め設定された許容遅延回数及び許容遅延時間の少なくとも一方が入力され、当該入力に基づいて、前記メンテナンス条件を生成して前記メンテナンス条件記憶部に書き込むメンテナンス条件生成部と、
前記データベースの負荷を示す負荷値を測定するデータベース負荷測定部と、をさらに備え、
前記メンテナンス条件生成部は、
前記許容遅延回数のみが入力された場合、前記更新回数が前記許容遅延回数を超え、かつ、前記負荷値が予め設定された負荷条件を満たすときに前記メンテナンス可能となる前記メンテナンス条件を生成し、
前記許容遅延時間のみが入力された場合、前回の前記メンテナンス時刻から現在時刻までを示す経過時間が前記許容遅延時間を超え、かつ、前記負荷値が前記負荷条件を満たすときに前記メンテナンス可能となる前記メンテナンス条件を生成し、
前記許容遅延回数と前記許容遅延時間とが入力された場合、前記更新回数が前記許容遅延回数を超え又は前記経過時間が前記許容遅延時間を超え、かつ、前記負荷値が前記負荷条件を満たすときに前記メンテナンス可能となる前記メンテナンス条件を生成することを特徴とする請求項１に記載のキャッシュメンテナンス装置。
【請求項８】
１以上のコンピュータのメモリで構成されるキャッシュにデータベースからのデータを保存する分散メモリキャッシュにおける、前記データを前記キャッシュに保存する単位となるキャッシュエントリをメンテナンスするキャッシュメンテナンス方法において、
前記キャッシュエントリをメンテナンスする条件であるメンテナンス条件を参照し、前記メンテナンス条件を満たすときにメンテナンス可能と判定するメンテナンス判定ステップと、
前記メンテナンス判定ステップでメンテナンス可能と判定した場合、前記キャッシュエントリをメンテナンスするキャッシュメンテナンスステップと、
を備えることを特徴とするキャッシュメンテナンス方法。
【請求項９】
コンピュータを、請求項１から請求項７の何れか一項に記載のキャッシュメンテナンス装置を構成する各手段として機能させるためのキャッシュメンテナンスプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、１以上のコンピュータのメモリで構成されるキャッシュにデータベースからのデータを保存する分散メモリキャッシュにおける、キャッシュエントリをメンテナンスするキャッシュメンテナンス技術に関する。
【背景技術】
【０００２】
今日、インターネットの爆発的な普及に伴い、多くのサービスがインターネットを通じて提供されている。インターネットを通じて提供されるサービスとしては、例えば、オンラインショッピング、オンラインバンキング、ソーシャルネットワーキングサービス（ＳＮＳ）があげられる。これらのサービスを提供するシステムは、殆どの場合、ユーザのアカウント情報や商品情報、ユーザによる投稿記事等のデータを保管するデータベース（ＤＢ）と、アプリケーションとで構成される。このアプリケーションは、サービスに合わせてデータベースに問い合わせ（クエリ）を発行し、データベースから返却されるデータを用いて、ユーザに提示する結果を作成する。
【０００３】
これらのシステムでは、ユーザの増加等の原因によりデータベースヘのアクセス数が大きく増加した場合、データベースの帯域幅やＣＰＵ資源を使い果たし、パフォーマンスの低下やサーバダウンが発生することがある。また、これらのシステムでは、アクセス数が増加しない場合でも、データベースへの問い合わせが複雑な場合、問い合わせの結果を返却するのに長い時間がかかってしまう。
【０００４】
そこで、上記のデータベースの処理負荷や参照性能の問題を解決する手法として、データベースとは別に、高速なアクセスが可能な記憶領域（キャッシュ）にこのデータベースヘの問い合わせ結果を利用して作られたデータを格納することが行われている。このキャッシュを利用するシステムは、例えば、データベースには永続性とクエリの処理とに優れたリレーショナルデータベースシステム（ＲＤＢＭＳ）、及び、キャッシュには応答性とスケーラビリティとに優れた分散メモリキャッシュで構成できる。
【０００５】
ここで、キャッシュからデータを取得する場合、アプリケーションは、必要なデータがキャッシュ上に存在するか否かを確認する。キャッシュ上に当該データが存在しなかった場合、データベースからデータを取得するのと同時に、キャッシュにユーザからのリクエストを関連付けたデータを格納する。以降、同一のデータが必要になった場合、アプリケーションは、キャッシュからこのデータを読み出して利用する。これによって、データベースにアクセスする必要がなくなるため、キャッシュを用いたシステムでは、高速にデータを参照可能とする他、データベースヘのアクセス数を低減してデータベースの負荷を軽減することができる。
【０００６】
一方、キャッシュを利用する場合、データベースに更新処理（登録、更新、削除）が発生すると，キャッシュに保存されたデータとデータベースに格納されたデータとに不整合が発生する可能性がある。例えば、データベースで更新されたデータをキャッシュで参照する場合、キャッシュに保存されたデータは更新されていないため、アプリケーションは、更新前の古いデータを参照してしまう。
【０００７】
従来から、この問題を解決するために、データベースに対して更新が行われた際、キャッシュの一貫性(cache consistency)を保つためのキャッシュメンテナンス技術が提案されている。
【０００８】
この技術としては、キャッシュを無効化(invalidation)するものが提案されている（例えば、非特許文献１参照）。この非特許文献１に記載の無効化方式では、データベースに対してキャッシュに不整合が発生するような更新が行われた場合、データベースがキャッシュに対して無効化メッセージを送信して、キャッシュで不整合が発生するデータを無効化し、キャッシュに保存された更新前のデータが参照されてしまうことを防止する。
【０００９】
また、この無効化後に、データベースに再度問い合わせを行うことでキャッシュに保存された全データを入れ替えて最新に保つ、再問い合わせ方式も提案されている（例えば、非特許文献２及び非特許文献５参照）。
【００１０】
また、キャッシュに保存されたデータが再利用可能であるような環境において、再問い合わせ方式によってキャッシュに保存された全データを入れ替えるのではなく、更新された差分のみを計算してこの差分をキャッシュに反映し、既にキャッシュに保存されているデータを生して最新に保つ、差分更新方式も提案されている（例えば、非特許文献３及び非特許文献４参照）。
【００１１】
＜従来のキャッシュメンテナンス技術：第１例＞
ここで、図２４を参照し、従来のキャッシュメンテナンス技術の第１例を説明する。図２４に示すように、キャッシュメンテナンスシステム９００は、キャッシュメンテナンス装置９Ａと、データベース９Ｂと、キャッシュ９Ｃとを備える。ここで、キャッシュメンテナンスシステム９００は、インターネット等のネットワークＮを介して、キャッシュメンテナンス装置９Ａと、データベース９Ｂと、キャッシュ９Ｃとを接続している。
【００１２】
キャッシュメンテナンス装置９Ａは、キャッシュ９Ｃに保存されたデータに不整合が発生した場合、無効化方式又は再問い合わせ方式によって、キャッシュ９Ｃのメンテナンスを行うものである。このキャッシュメンテナンス装置９Ａは、メンテナンス対象選択部９１と、キャッシュメンテナンス部９２とを備える。
【００１３】
データベース９Ｂは、キャッシュ９Ｃの対象となるデータを格納するリレーショナルデータベース等の一般的なデータベースである。このデータベース９Ｂは、アプリケーションの種類に応じて、様々なデータを格納する。
【００１４】
キャッシュ９Ｃは、１以上のコンピュータのメモリで構成された分散メモリキャッシュである。なお、キャッシュ９Ｃを構成する各コンピュータの図示は、省略した。
【００１５】
以下、キャッシュ９Ｃのメンテナンスについて詳細に説明する。メンテナンス対象選択部９１は、データベース９Ｂに対して更新処理が行われた際、その更新の内容に基づいて、データベースの更新処理の影響を受けメンテナンスが必要となる、キャッシュ９Ｃのキャッシュエントリ（不図示）を選択するものである。ここで、メンテナンス対象選択部９１は、例えば、データベース９Ｂに対する更新問い合わせの一部又は全部を元に、メンテナンス対象を検索可能とするマッピングテーブルを用意する方法を用いる。また、メンテナンス対象選択部９１は、例えば、データベース９Ｂに対する更新問い合わせの一部又は全部を入力として、メンテナンス対象を検索するため問い合わせ文を予め用意する方法を用いる。さらに、メンテナンス対象選択部９１は、更新処理のあったテーブルを元に作られたキャッシュエントリを全てメンテナンス対象とする方法を用いても良く、前記した非特許文献３に記載の技術を用いても良い。
【００１６】
キャッシュメンテナンス部９２は、メンテナンス対象選択部９１が選択したメンテナンス対象のキャッシュエントリを無効化するための無効化メッセージを送信するものである。また、キャッシュメンテナンス部９２は、再問い合わせ方式を採用する場合、無効化メッセージの送信後、データベース９Ｂに対して、このキャッシュエントリのデータを取得するための問い合わせを発行し、その問い合わせ結果をキャッシュ２Ｃに格納する。このようにして、キャッシュメンテナンスシステム９００は、キャッシュのメンテナンスを行う。なお、無効化方式及び再問い合わせ方式の詳細については、前記した非特許文献１，２，３，５に記載されている。
【００１７】
＜従来のキャッシュメンテナンス技術：第２例＞
さらに、図２５を参照し、従来のキャッシュメンテナンス技術の第２例を説明する（適宜図２４参照）。図２５においては、キャッシュメンテナンス装置９Ａは、キャッシュ９Ｃに保存されたデータに不整合が発生した場合、差分更新方式によって、キャッシュ９Ｃのメンテナンスを行う。
【００１８】
図２５に示すように、データベース９Ｂは、「ｍｅｓｓａｇｅ」というテーブル９Ｔ１と「ｆｏｌｌｏｗｅｒ」というテーブル９Ｔ２とを格納する。また、キャッシュ９Ｃは、テーブル９Ｔ１とテーブル９Ｔ２とを結合（ＪＯＩＮ）した結果である「ｔｉｍｅｌｉｎｅ」というキャッシュエントリ９ＣＥを保存する。
【００１９】
ここで、テーブル９Ｔ１に新たなレコード（図２５におけるｉｄ＝６）が登録（ＩＮＳＥＲＴ）された場合、このレコードに基づいて、差分データを求めるための問い合わせ９Ｑを行う。その結果、求められた差分データ９Ｄを、ｋｅｙに基づいて、キャッシュエントリ９ＣＥを更新する。このように、従来の差分更新方式では、データベース９Ｂに対して更新処理が発生する都度、このキャッシュ更新処理を行う必要がある。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】Greg Barish，Katia obraczka，“World Wide Web Caching: Trends and techniques"，IEEE Communications Magazine 2000.5
【非特許文献２】James Gwertzman，Margo Seltzer,“World Wide Web Cache Consistency"，USENIX technical Conference，1996
【非特許文献３】Ashish Gupta，lnderpal Singh Mumick，“Maintenance of Materialized Views:Problems,techniques,and Applications",IEEE Data Engineering Bulletin， 1995
【非特許文献４】Jingren Zhou，Per・Ake Larson，Hicham G. Elmongui,‘Lazy maintenance of materialized views",VLDB Conference,2007
【非特許文献５】Cal Henderson，「スケーラブルWebサイト」，オライリー・ジャパン，2006
【発明の概要】
【発明が解決しようとする課題】
【００２１】
しかし、前記した無効化方式では、データベースに高い頻度で更新処理が発生した場合、キャッシュの無効化が多発するため、キャッシュヒット率が大きく低下してしまい、キャッシュの効果（参照速度の向上及び処理負荷の低減）が十分に得られないという問題がある。
【００２２】
また、前記した再問い合わせ方式及び差分更新方式では、データベースに高い頻度で更新処理が発生した場合、キャッシュメンテナンス時に毎回データベースヘの問い合わせが発生するため、データベースヘの問い合わせが多発し、データベースの処理負荷が増大し、パフォーマンスの低下やサーバダウンに繋がる。
【００２３】
そこで、本発明は、データベースに高い頻度で更新処理が行われる環境においても、参照速度が低下せず、処理負荷の増大を最小限に抑えるキャッシュメンテナンス技術を提供することを目的とする。
【課題を解決するための手段】
【００２４】
前記した課題を解決するため、本願第１発明に係るキャッシュメンテナンス装置は、１以上のコンピュータのメモリで構成されるキャッシュにデータベースからのデータを保存する分散メモリキャッシュにおける、前記データを前記キャッシュに保存する単位となるキャッシュエントリをメンテナンスするキャッシュメンテナンス装置において、前記キャッシュエントリをメンテナンスする条件であるメンテナンス条件を記憶するメンテナンス条件記憶部と、前記メンテナンス条件記憶部に記憶したメンテナンス条件を参照し、前記メンテナンス条件を満たすときにメンテナンス可能と判定するメンテナンス判定部と、前記メンテナンス判定部がメンテナンス可能と判定した場合、前記キャッシュエントリをメンテナンスするキャッシュメンテナンス部と、を備えることを特徴とする。
【００２５】
かかる構成によれば、キャッシュメンテナンス装置は、データベースの更新処理によってキャッシュエントリとデータベースのデータとの間に不整合が発生したとき、常にキャッシュエントリのメンテナンスを行うのではなく、所定のメンテナンス条件を満たす場合にのみ、キャッシュエントリのメンテナンスを行うこととした。これによって、キャッシュメンテナンス装置は、データベースに高い頻度で更新処理が行われる環境においても、参照速度が低下せず、処理負荷の増大を最小限に抑えることができる。
【００２６】
なお、分散メモリキャッシュとは、１以上のコンピュータのメモリを連携して巨大な論理メモリ（キャッシュ）として扱う技術であり、ｋｅｙとｖａｌｕｅとのペアによる単純なアクセスのみを提供する代わりに、ハッシュ分散による高いスケーラビリティを有することを特徴とする。
【００２７】
なお、キャッシュエントリとは、データベースからのデータをキャッシュに保存する単位となるものであり、例えば、ｋｅｙと対応付けてデータベースへの問い合わせ結果をキャッシュに保存したものである。
【００２８】
なお、メンテナンスとは、データベースの更新処理によって、このデータとこのデータに対応するキャッシュエントリとの間に不整合が発生した際、無効化方式、再問い合わせ方式又は差分更新方式を用いてこのキャッシュエントリを無効化又はこのデータを整合した状態にすることである。
【００２９】
なお、無効化方式とは、データベースの更新処理によって、このデータとこのデータに対応するキャッシュエントリとの間に不整合が発生した際、そのキャッシュエントリを無効化し、不整合なデータがキャッシュエントリから読み出されるのを防ぐ方式である。
【００３０】
なお、再問い合わせ方式とは、データベースの更新処理によって、このデータとこのデータに対応するキャッシュエントリとの間に不整合が発生した際、そのキャッシュエントリに対応する問い合わせをデータベースに対して行い，その問い合わせ結果をキャッシュエントリに上書きすことで、キャッシュエントリとデータとを整合した状態にする方式である。
【００３１】
また、本願第２発明に係るキャッシュメンテナンス装置は、前回のメンテナンス時刻、及び、前回の前記メンテナンス時刻以後に前記データが更新された回数を示す更新回数の少なくとも一方を含む更新情報を記憶する更新情報記憶部と、予め設定された許容遅延回数及び許容遅延時間の少なくとも一方が入力され、当該入力に基づいて、前記メンテナンス条件を生成して前記メンテナンス条件記憶部に書き込むメンテナンス条件生成部と、をさらに備え、前記メンテナンス条件生成部は、前記許容遅延回数のみが入力された場合、前記更新回数が前記許容遅延回数を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、前記許容遅延時間のみが入力された場合、前回の前記メンテナンス時刻から現在時刻までを示す経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、前記許容遅延回数と前記許容遅延時間とが入力された場合、前記更新回数が前記許容遅延回数を超えたとき又は前記経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成することを特徴とする。
【００３２】
かかる構成によれば、キャッシュメンテナンス装置は、メンテナンス条件を満たす場合にのみキャッシュエントリのメンテナンスを行い、メンテナンスの頻度を制御することとした。これによって、キャッシュメンテナンス装置は、無効化方式を採用したときは、メンテナンスによってキャッシュエントリが無効化される頻度が低減するので、キャッシュヒット率が大幅に向上する。また、キャッシュメンテナンス装置は、再問い合わせ方式を採用したときは、メンテナンス条件の判定の処理負荷がメンテナンスの頻度を少なくして削減できるメンテナンスコストよりも十分に小さいため、メンテナンスコストを大幅に削減できる。
【００３３】
なお、更新回数（メンテナンスカウント）とは、キャッシュエントリ毎に、前回のメンテナンス時刻以後にデータが更新された回数を示すものである。
【００３４】
なお、許容遅延回数とは、データベースの更新処理によって、このデータとこのデータに対応するキャッシュエントリとの間で、許容遅延回数で指定した回数の不整合が発生したときに、１回のメンテナンスを行うことを示す数値である。
【００３５】
なお、許容遅延時間とは、データベースの更新処理によって、このデータとこのデータに対応するキャッシュエントリとの間に不整合が発生した際、前回のメンテナンス時刻から許容遅延時間以上経過したキャッシュエントリをメンテナンスすることを示す時間である。
【００３６】
なお、メンテナンスコストとは、データベースサーバにおいて、メンテナンスに伴って費やされるＣＰＵ時間等の演算処理量である。
【００３７】
また、本願第３発明に係るキャッシュメンテナンス装置は、予め設定された許容遅延回数及び許容遅延時間の少なくとも一方が入力され、当該入力に基づいて、前記メンテナンス条件を生成して前記メンテナンス条件記憶部に書き込むメンテナンス条件生成部、をさらに備え、前記メンテナンス条件生成部は、前記許容遅延回数のみが入力された場合、更新回数が前記許容遅延回数を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、前記許容遅延時間のみが入力された場合、経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、前記許容遅延回数と前記許容遅延時間とが入力された場合、前記更新回数が前記許容遅延回数を超えたとき又は前記経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、前記メンテナンス判定部は、前記データベースのテーブルにおける差分データを格納した差分テーブルを参照し、当該差分テーブルのデータ件数を前記更新回数として算出すると共に、当該差分テーブルにおける最も古いデータを格納した時刻から現在時刻までを前記経過時間として算出し、算出した前記更新回数と前記経過時間とを用いて前記メンテナンス条件を満たすか判定し、前記キャッシュメンテナンス部は、前記差分テーブルに格納した前記差分データで前記キャッシュエントリを一括して更新すると共に、更新した前記差分データを前記差分テーブルから削除することを特徴とする。
【００３８】
かかる構成によれば、キャッシュメンテナンス装置は、メンテナンス条件を満たす場合にのみ差分データでキャッシュエントリを更新し、メンテナンスの頻度を制御することとした。これによって、キャッシュメンテナンス装置は、差分更新方式を採用したときは、メンテナンスによって逐次差分データをキャッシュエントリに更新する場合に比べて、問い合わせ処理及び通信処理のオーバーヘッドが大幅に少ないため、メンテナンスコストを大幅に削減できる。
【００３９】
なお、差分更新方式とは、データベースの更新処理によって、このデータとこのデータに対応するキャッシュエントリとの間に不整合が発生した際、そのキャッシュエントリを整合した状態に更新するために必要な差分データを算出し，そのキャッシュエントリにこの差分データを反映させることで、キャッシュエントリとデータとを整合した状態にする方式である。
【００４０】
また、本願第４発明に係るキャッシュメンテナンス装置は、前回のメンテナンス時刻、及び、前回の前記メンテナンス時刻以後に前記データが更新された回数を示す更新回数の少なくとも一方を含む更新情報を記憶する更新情報記憶部と、予め設定された許容遅延回数及び許容遅延時間の少なくとも一方と、メンテナンスコストの目標負荷値とが入力され、当該入力に基づいて、前記キャッシュエントリ毎に前記メンテナンス条件を生成して前記メンテナンス条件記憶部に書き込むメンテナンス条件生成部と、予め設定された統計期間における前記キャッシュエントリをメンテナンスした回数を示すメンテナンス回数の累積値を統計情報として算出する統計情報算出部と、をさらに備え、前記メンテナンス条件生成部は、前記メンテナンス回数の累積値に前記目標負荷値を乗じて削減目標値を算出し、前記許容遅延回数のみが入力された場合、前記更新回数が前記許容遅延回数を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、式（１）で算出した削減値を前記削減目標値から減算し、前記許容遅延時間のみが入力された場合、前回の前記メンテナンス時刻から現在時刻までを示す経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、式（２）で算出した削減値を前記削減目標値から減算し、前記許容遅延回数と前記許容遅延時間とが入力された場合、前記更新回数が前記許容遅延回数を超えたとき又は前記経過時間が前記許容遅延時間を超えたときに前記メンテナンス可能となる前記メンテナンス条件を生成し、式（３）で算出した削減値を前記削減目標値から減算し、前記削減目標値から前記削減値を減算した値が０以下になったときは、前記メンテナンス条件の生成を終了することを特徴とする。
Ａ＝Ｍｉ×（Ｎ−１）／Ｎ・・・式（１）
Ａ＝Ｍｉ×（１−Ｔ／Ｓ）・・・式（２）
Ａ＝ＭＩＮ［｛Ｍｉ×（Ｎ−１）／Ｎ｝，{Ｍｉ×（１−Ｔ／Ｓ）}］・・・式（３）
但し、式（１）〜式（３）において、Ａは削減値、Ｍｉはメンテナンス回数の累積値、Ｎは許容遅延回数、Ｔは許容遅延時間、及び、Ｓは統計期間である。
【００４１】
かかる構成によれば、キャッシュメンテナンス装置は、メンテナンス条件を満たす場合にのみキャッシュエントリのメンテナンスを行い、メンテナンスの頻度を制御することとした。これによって、キャッシュメンテナンス装置は、無効化方式を採用したときは、メンテナンスによってキャッシュエントリが無効化される頻度が低減するので、キャッシュヒット率が大幅に向上する。また、キャッシュメンテナンス装置は、再問い合わせ方式を採用したときは、メンテナンス条件の判定の処理負荷がメンテナンスの頻度を少なくして削減できるメンテナンスコストよりも十分に小さいため、メンテナンスコストを大幅に削減できる。さらに、キャッシュメンテナンス装置は、目標負荷を達成した後、不要なメンテナンスを行うことがなく、処理負荷をさらに削減できる。
【００４２】
なお、目標負荷値とは、メンテナンスコストを削減する目標となる数値である。
【００４３】
また、本願第５発明に係るキャッシュメンテナンス装置は、前記メンテナンス条件生成部が、前記メンテナンス条件を生成しておらず、かつ、前記メンテナンス回数の累積値が最大となる前記キャッシュエントリについて、前記メンテナンス条件を生成することを特徴とする。
【００４４】
かかる構成によれば、キャッシュメンテナンス装置は、メンテナンス回数の累積値が大きい順にキャッシュエントリを選択し、この順にキャッシュエントリのメンテナンスを行うこととした。ここで、メンテナンスの頻度が高いキャッシュエントリ程、メンテナンスの頻度を削減による効果（例えば、無効化方式を採用したときはキャッシュヒット率の向上、再問い合わせ方式を採用したときは処理負荷の削減）が大きくなる。従って、キャッシュメンテナンス装置は、メンテナンス条件を設定してメンテナンスを行うキャッシュエントリの数を必要最小限とし、キャッシュエントリの最新性の低下を最小限に抑える。
【００４５】
なお、最新性とは、キャッシュエントリから読み出したデータが最新である比率、つまり、不整合が発生しないデータの比率である。また、キャッシュエントリから読み出したデータが最新であるとは、データベースに問い合わせ結果として得られるデータと、キャッシュエントリから読み出したデータとが一致（整合）していることである。
【００４６】
また、本願第６発明に係るキャッシュメンテナンス装置は、前記統計情報算出部が、前記統計情報として、前記統計期間における前記キャッシュエントリが参照された参照回数の累積値を算出し、前記メンテナンス条件生成部は、前記メンテナンス条件を生成しておらず、かつ、前記参照回数の累積値が最小となる前記キャッシュエントリについて、前記メンテナンス条件を生成することを特徴とする。
【００４７】
かかる構成によれば、キャッシュメンテナンス装置は、参照回数の累積値が小さい順にキャッシュエントリを選択し、この順にキャッシュエントリのメンテナンスを行うこととした。これによって、キャッシュメンテナンス装置は、メンテナンスによる悪影響が少ないキャッシュエントリから順にメンテナンスを行うことで、キャッシュエントリの最新性の低下を最小限に抑える。
【００４８】
また、本願第７発明に係るキャッシュメンテナンス装置は、前回のメンテナンス時刻、及び、前回の前記メンテナンス時刻以後に前記データが更新された回数を示す更新回数の少なくとも一方を含む更新情報を記憶する更新情報記憶部と、予め設定された許容遅延回数及び許容遅延時間の少なくとも一方が入力され、当該入力に基づいて、前記メンテナンス条件を生成して前記メンテナンス条件記憶部に書き込むメンテナンス条件生成部と、前記データベースの負荷を示す負荷値を測定するデータベース負荷測定部と、をさらに備え、前記メンテナンス条件生成部は、前記許容遅延回数のみが入力された場合、前記更新回数が前記許容遅延回数を超え、かつ、前記負荷値が予め設定された負荷条件を満たすときに前記メンテナンス可能となる前記メンテナンス条件を生成し、前記許容遅延時間のみが入力された場合、前回の前記メンテナンス時刻から現在時刻までを示す経過時間が前記許容遅延時間を超え、かつ、前記負荷値が前記負荷条件を満たすときに前記メンテナンス可能となる前記メンテナンス条件を生成し、前記許容遅延回数と前記許容遅延時間とが入力された場合、前記更新回数が前記許容遅延回数を超え又は前記経過時間が前記許容遅延時間を超え、かつ、前記負荷値が前記負荷条件を満たすときに前記メンテナンス可能となる前記メンテナンス条件を生成することを特徴とする。
【００４９】
かかる構成によれば、キャッシュメンテナンス装置は、メンテナンス条件を満たす場合にのみキャッシュエントリのメンテナンスを行い、メンテナンスの頻度を制御することとした。これによって、キャッシュメンテナンス装置は、無効化方式を採用したときは、メンテナンスによってキャッシュエントリが無効化される頻度が低減するので、キャッシュヒット率が大幅に向上する。また、キャッシュメンテナンス装置は、再問い合わせ方式を採用したときは、メンテナンス条件の判定の処理負荷がメンテナンスの頻度を少なくして削減できるメンテナンスコストよりも十分に小さいため、メンテナンスコストを大幅に削減できる。さらに、キャッシュメンテナンス装置は、負荷条件を設定することで、データベースの負荷に応じて、メンテナンスの頻度を制御することができる。これによって、キャッシュメンテナンス装置は、例えば、データベースサーバのＣＰＵ資源に余裕があるときにメンテナンスの頻度を低下させてＣＰＵ資源を節約するといった事態を防止し、データベースにパフォーマンスを十分に発揮させることができる。
【００５０】
また、本願第８発明に係るキャッシュメンテナンス方法は、１以上のコンピュータのメモリで構成されるキャッシュにデータベースからのデータを保存する分散メモリキャッシュにおける、前記データを前記キャッシュに保存する単位となるキャッシュエントリをメンテナンスするキャッシュメンテナンス方法において、前記キャッシュエントリをメンテナンスする条件であるメンテナンス条件を参照し、前記メンテナンス条件を満たすときにメンテナンス可能と判定するメンテナンス判定ステップと、前記メンテナンス判定ステップでメンテナンス可能と判定した場合、前記キャッシュエントリをメンテナンスするキャッシュメンテナンスステップと、を備えることを特徴とする。
【００５１】
かかる構成によれば、キャッシュメンテナンス方法は、データベースの更新処理によってキャッシュエントリに保存したデータとデータベースに格納したデータとの間に不整合が発生したとき、常にキャッシュエントリのメンテナンスを行うのではなく、所定のメンテナンス条件を満たす場合にのみ、キャッシュエントリのメンテナンスを行うこととした。これによって、キャッシュメンテナンス方法は、データベースに高い頻度で更新処理が行われる環境においても、参照速度が低下せず、処理負荷の増大を最小限に抑えることができる。
【００５２】
また、本願第９発明に係るキャッシュメンテナンスプログラムは、コンピュータを、本願第１発明から本願第７発明の何れかのキャッシュメンテナンス装置を構成する各手段として機能させることを特徴とする。
【００５３】
かかる構成によれば、キャッシュメンテナンスプログラムは、データベースの更新処理によってキャッシュエントリに保存したデータとデータベースに格納したデータとの間に不整合が発生したとき、常にキャッシュエントリのメンテナンスを行うのではなく、所定のメンテナンス条件を満たす場合にのみ、キャッシュエントリのメンテナンスを行うこととした。これによって、キャッシュメンテナンスプログラムは、データベースに高い頻度で更新処理が行われる環境においても、参照速度が低下せず、処理負荷の増大を最小限に抑えることができる。
【発明の効果】
【００５４】
本発明によれば、所定のメンテナンス条件を満たす場合にのみ、キャッシュエントリのメンテナンスを行うため、データベースに高い頻度で更新処理が行われる環境においても、参照速度が低下せず、処理負荷の増大を最小限に抑えることができる。
【図面の簡単な説明】
【００５５】
【図１】本発明の第１実施形態に係るキャッシュメンテナンス装置の構成を示すブロック図である。
【図２】図１の更新情報記憶部が記憶するキャッシュエントリ更新情報のデータ構造を示す図である。
【図３】図１のメンテナンス条件記憶部が記憶するメンテナンス条件のデータ構造を示す図である。
【図４】図１のキャッシュメンテナンス装置の動作を示すフローチャートである。
【図５】図４のステップＳ２の詳細を示すフローチャートである。
【図６】図５のステップＳ２３の詳細を示すフローチャートである。
【図７】本発明の第１実施形態に係るキャッシュメンテナンス装置をコンピュータで実現した例を示す図である。
【図８】本発明の第２実施形態に係るキャッシュメンテナンス装置の構成を示すブロック図である。
【図９】図８のキャッシュ差分メンテナンス部によるメンテナンスについて説明する説明図である。
【図１０】図８のキャッシュメンテナンス装置における、図４のステップＳ２の詳細を示すフローチャートである。
【図１１】図１０のステップＳ３２の詳細を示すフローチャートである。
【図１２】本発明の第３実施形態に係るキャッシュメンテナンス装置の構成を示すブロック図である。
【図１３】図１２の更新情報記憶部が記憶するキャッシュエントリ更新情報のデータ構造を示す図である。
【図１４】図１２のメンテナンス条件記憶部が記憶するメンテナンス条件のデータ構造を示す図である。
【図１５】図１２のキャッシュメンテナンス装置における、図４のステップＳ１の詳細を示すフローチャートである。
【図１６】図１５のステップＳ４０の詳細を示すフローチャートである。
【図１７】図１５のステップＳ４３の第１例を示すフローチャートである。
【図１８】図１５のステップＳ４３の第２例を示すフローチャートである。
【図１９】本発明の第４実施形態に係るキャッシュメンテナンス装置の構成を示すブロック図である。
【図２０】図１８のメンテナンス条件記憶部が記憶するメンテナンス条件のデータ構造を示す図である。
【図２１】図１８のキャッシュメンテナンス装置における、図４のステップＳ１の詳細を示すフローチャートである。
【図２２】図１８のキャッシュメンテナンス装置における、図５のステップＳ２３の詳細を示すフローチャートである。
【図２３】実施例における許容遅延回数と更新スループットの限界値との関係を示す図である。
【図２４】従来のキャッシュメンテナンス技術の第１例を説明する説明図である。
【図２５】従来のキャッシュメンテナンス技術の第２例を説明する説明図である。
【発明を実施するための形態】
【００５６】
以下、本発明の各実施形態について、適宜図面を参照しながら詳細に説明する。なお、各実施形態において、同一の機能を有する手段及び同一の構成には同一の符号を付し、説明を省略した。
【００５７】
（第１実施形態：無効化方式又は再問い合わせ方式）
［キャッシュメンテナンスシステムの概略］
図１を参照して、キャッシュメンテナンスシステム１００の概略について説明する。図１に示すように、キャッシュメンテナンスシステム１００は、キャッシュメンテナンス装置１と、データベース１Ｂと、キャッシュ１Ｃとを備える。ここで、キャッシュメンテナンスシステム１００は、インターネット等のネットワークＮを介して、キャッシュメンテナンス装置１と、データベース１Ｂと、キャッシュ１Ｃとを接続している。
【００５８】
キャッシュメンテナンス装置１は、データベース１Ｂに格納されたデータをキャッシュ１Ｃに保存する分散メモリキャッシュにおける、キャッシュエントリ１ＣＥをメンテナンスするものであり、ここでは、無効化方式又は再問い合わせ方式を行う。なお、キャッシュメンテナンス装置１の構成については、後記する。
【００５９】
データベース１Ｂは、キャッシュ１Ｃの対象となるデータを格納するリレーショナルデータベース等の一般的なデータベースである。
【００６０】
キャッシュ１Ｃは、１以上のコンピュータのメモリで構成された分散メモリキャッシュである。ここで、キャッシュ１Ｃは、１個以上のキャッシュエントリ１ＣＥ１，１ＣＥ２・・・１ＣＥｎを有することになる（但し、ｎは１以上の整数）。
【００６１】
キャッシュエントリ１ＣＥは、データベース１Ｂのデータを保存し、アプリケーションにデータを提供するものである。ここで、キャッシュエントリ１ＣＥ、データベース１Ｂに格納されたデータをそのまま保存しても良く、データベース１Ｂに格納されたデータを加工（例えば、ＷｅｂアプリケーションであればＨＴＭＬ形式に加工）して保存しても良い。
【００６２】
そして、データベース１Ｂに格納したデータとキャッシュエントリ１ＣＥに保存したデータとの間に不整合が発生した場合、キャッシュメンテナンス装置１は、後記するメンテナンス条件を満たす場合、このキャッシュエントリ１ＣＥのメンテナンスを行う。
【００６３】
［キャッシュメンテナンス装置の構成］
以下、図１を参照して、キャッシュメンテナンス装置１の構成について説明する。図１に示すように、キャッシュメンテナンス装置１は、更新情報記憶部１１と、メンテナンス条件記憶部２１と、メンテナンス条件生成部３１と、メンテナンス対象選択部４１と、メンテナンス判定部５１と、キャッシュメンテナンス部６１とを備える。
【００６４】
更新情報記憶部１１は、キャッシュエントリ更新情報（更新情報）を記憶するハードディスク等の記憶手段である。このキャッシュエントリ更新情報は、前回のメンテナンス時刻、及び、前回のメンテナンス時刻以後にデータが更新された回数を示す更新回数（メンテナンスカウント）の少なくとも一方を含むものである。ここでは、図２に示すように、キャッシュエントリ更新情報は、キャッシュエントリ１ＣＥを一意に識別するキャッシュエントリ識別子と、前回のメンテナンス時刻以後にデータが更新された回数を示す更新回数を示すメンテナンスカウントと、前回にメンテナンスが行われた時刻である前回のメンテナンス時刻とを有する。
【００６５】
図１のメンテナンス条件記憶部２１は、メンテナンス条件を記憶するハードディスク等の記憶手段である。このメンテナンス条件は、キャッシュエントリ１ＣＥをメンテナンスする条件を示すものである。
【００６６】
また、メンテナンス条件生成部３１は、予め設定された許容遅延回数及び許容遅延時間の少なくとも一方が入力され、この入力に基づいて、メンテナンス条件を生成してメンテナンス条件記憶部２１に書き込むものである。ここで、メンテナンス条件生成部３１は、設定ファイルから許容遅延回数及び許容遅延時間の少なくとも一方を読み取り、又は、図示を省略したキーボード、マウス等の入力部によって、許容遅延回数及び許容遅延時間の少なくとも一方が入力される。
【００６７】
そして、メンテナンス条件生成部３１は、メンテナンス条件を生成する。具体的には、メンテナンス条件生成部３１は、許容遅延回数のみが入力された場合、メンテナンスカウントが許容遅延回数を超えたときにメンテナンス可能となるメンテナンス条件を生成する。例えば、メンテナンス条件生成部３１は、許容遅延回数「１０回」が入力された場合、図３（ａ）に示すように、「メンテナンスカウント＞１０回」というメンテナンス条件を生成する。
【００６８】
また、メンテナンス条件生成部３１は、許容遅延時間のみが入力された場合、経過時間が許容遅延時間を超えたときにメンテナンス可能となるメンテナンス条件を生成する。例えば、メンテナンス条件生成部３１は、許容遅延時間「１０分」が入力された場合、図３（ｂ）に示すように、「経過時間＞１０分」というメンテナンス条件を生成する。なお、経過時間は、前回のメンテナンス時刻から現在時刻までの時間である。また、現在時刻として、例えば、コンピュータの内蔵時計の時刻やＮＴＰ（Network Time Protocol）で取得した時刻を用いることができる。
【００６９】
また、メンテナンス条件生成部３１は、許容遅延回数と許容遅延時間との両方が入力された場合、メンテナンスカウントが許容遅延回数を超えたとき又は経過時間が許容遅延時間を超えたときにメンテナンス可能となるメンテナンス条件を生成する。例えば、メンテナンス条件生成部３１は、許容遅延回数「２０回」と許容遅延時間「１０分」とが入力された場合、図３（ｃ）に示すように、「（メンテナンスカウント＞２０回）ＯＲ（経過時間＞１０分）」というメンテナンス条件を生成する。なお、図３（ｃ）の「ＯＲ」は、ＯＲ条件であることを示す。なお、メンテナンス条件生成部３１は、全てのキャッシュエントリ１ＣＥで共通する、１個のメンテナンス条件を生成する。
【００７０】
図１のメンテナンス対象選択部４１は、キャッシュ１Ｃの全てのキャッシュエントリ１ＣＥのうち、メンテナンスの対象となるキャッシュエントリ１ＣＥを選択するものである。ここで、メンテナンス対象選択部４１は、キャッシュエントリ１ＣＥを選択すると共に、キャッシュエントリ更新情報を更新しても良い。例えば、メンテナンス対象選択部４１は、メンテナンスカウントをインクリメントし、前回のメンテナンス時刻を現在時刻に更新する。このとき、メンテナンス対象選択部４１は、データベース１Ｂに対する更新問い合わせ（登録、更新、削除）の一部又は全部を元に、メンテナンス対象を検索可能とするマッピングテーブルを用意する方法を用いる。また、メンテナンス対象選択部４１は、例えば、データベース１Ｂに対する更新問い合わせの一部又は全部を入力として、メンテナンス対象を検索するため問い合わせ文を予め用意する方法がある。さらに、メンテナンス対象選択部４１は、更新処理のあったテーブルを元に作られたキャッシュエントリ１ＣＥを全てメンテナンス対象とする方法を用いても良く、前記した非特許文献３に記載の技術を用いても良い。
【００７１】
メンテナンス判定部５１は、メンテナンス条件記憶部２１に記憶したメンテナンス条件を参照し、メンテナンス条件を満たすときにメンテナンス可能と判定するものである。ここで、メンテナンス判定部５１は、更新情報記憶部１１に記憶したキャッシュエントリ更新情報が更新された際、メンテナンス対象選択部４１が選択したキャッシュエントリ１ＣＥに対応するメンテナンスカウントと前回のメンテナンス時刻とを、更新情報記憶部１１から読み出す。そして、メンテナンス判定部５１は、メンテナンス条件にこの読み出したメンテナンスカウント及び前回のメンテナンス時刻の少なくとも一方を代入し、メンテナンス条件を満たすか否かを判定する。
【００７２】
キャッシュメンテナンス部６１は、メンテナンス判定部５１がメンテナンス可能と判定した場合、キャッシュエントリ１ＣＥをメンテナンスするものである。ここで、無効化方式を採用した場合、キャッシュメンテナンス部６１は、メンテナンス判定部５１がメンテナンス可能と判定したら、メンテナンス対象選択部４１が選択したキャッシュエントリ１ＣＥを無効化することを示す無効化メッセージをキャッシュ１Ｃに送信する。
【００７３】
また、再問い合わせ方式を採用した場合、キャッシュメンテナンス部６１は、無効化メッセージを送信した後、データベース１Ｂにこのキャッシュエントリ１ＣＥに保存するデータを取得するための問い合わせを行う。そして、キャッシュメンテナンス部６１は、この問い合わせ結果をキャッシュ１Ｃにキャッシュエントリ１ＣＥとして保存する。なお、無効化方式及び再問い合わせ方式の詳細については、前記した非特許文献１，２，３，５に記載されている。
【００７４】
［キャッシュメンテナンス装置の動作］
＜全体動作＞
以下、図４を参照して、キャッシュメンテナンス装置１の全体動作について説明する（適宜図１参照）。まず、図４に示すように、キャッシュメンテナンス装置１は、メンテナンス条件生成部３１によって、許容遅延回数及び許容遅延時間の少なくとも一方が入力され、この入力に基づいて、メンテナンス条件を生成してメンテナンス条件記憶部２１に書き込む（ステップＳ１）。
【００７５】
ステップＳ１の処理に続いて、キャッシュメンテナンス装置１は、キャッシュエントリ１ＣＥのメンテナンスを行う（ステップＳ２）。なお、ステップＳ２の詳細は、後記する。
【００７６】
ステップＳ２の処理に続いて、キャッシュメンテナンス装置１は、メンテナンス判定部５１によって、メンテナンスを終了するか否かを判定する（ステップＳ３）。例えば、入力部にユーザからの終了命令が入力された場合、キャッシュメンテナンス装置１は、メンテナンス判定部５１によって、メンテナンスを終了すると判定する。
【００７７】
ここで、メンテナンスを終了すると判定した場合（ステップＳ３でＹｅｓ）、キャッシュメンテナンス装置１は、処理を終了する。一方、メンテナンスを終了しないと判定した場合（ステップＳ３でＮｏ）、キャッシュメンテナンス装置１は、ステップＳ２の処理に戻る。
【００７８】
＜ステップＳ２の詳細：メンテナンス＞
以下、図５を参照して、図４のステップＳ２（メンテナンス）の詳細について説明する。まず、キャッシュメンテナンス装置１は、メンテナンス対象選択部４１によって、キャッシュ１Ｃの全てのキャッシュエントリ１ＣＥのうち、メンテナンスの対象となるキャッシュエントリ１ＣＥを判定する（ステップＳ２０）。具体的には、キャッシュメンテナンス装置１は、メンテナンス対象選択部４１によって、メンテナンスが行われていない未処理キャッシュエントリ識別値のリスト（未処理リスト）を出力する。
【００７９】
ステップＳ２０の処理に続いて、キャッシュメンテナンス装置１は、メンテナンス対象選択部４１によって、ステップＳ２０で出力した未処理リストに基づいて、メンテナンスを行うキャッシュエントリ１ＣＥを任意に選択する（ステップＳ２１）。例えば、キャッシュメンテナンス装置１は、メンテナンス対象選択部４１によって、この未処理リストに含まれるキャッシュエントリ識別子をソートし、ソート順にキャッシュエントリ１ＣＥを選択する。また、例えば、キャッシュメンテナンス装置１は、メンテナンス対象選択部４１によって、この未処理リストに含まれるキャッシュエントリ１ＣＥをランダムに選択する。そして、キャッシュメンテナンス装置１は、メンテナンス対象選択部４１によって、選択したキャッシュエントリ１ＣＥを示すキャッシュエントリ識別子を出力する。
【００８０】
ステップＳ２1の処理に続いて、キャッシュメンテナンス装置１は、メンテナンス対象選択部４１によって、ステップＳ２０で出力したキャッシュエントリ識別子に対応するキャッシュエントリ１ＣＥについて、キャッシュエントリ更新情報のメンテナンスカウントを更新（インクリメント）する（ステップＳ２２）。
【００８１】
ステップＳ２２の処理に続いて、キャッシュメンテナンス装置１は、メンテナンス判定部５１によって、メンテナンス条件を評価する（ステップＳ２３）。そして、キャッシュメンテナンス装置１は、メンテナンス判定部５１によって、この評価結果に応じた真偽値を出力する。なお、ステップＳ２３の詳細は、後記する。
【００８２】
ステップＳ２３の処理に続いて、キャッシュメンテナンス装置１は、メンテナンス判定部５１によって、メンテナンス条件を満たすか否かを判定する（ステップＳ２４）。例えば、キャッシュメンテナンス装置１は、メンテナンス判定部５１によって、ステップＳ２３で出力した真偽値が「真」のとき、メンテナンス条件を満たしメンテナンス可能と判定する。また、例えば、キャッシュメンテナンス装置１は、メンテナンス判定部５１によって、ステップＳ２３で出力した真偽値が「偽」のとき、メンテナンス条件を満たさずメンテナンス不可能と判定する。
【００８３】
ここで、メンテナンス可能と判定した場合（ステップ２４でＹｅｓ）、キャッシュメンテナンス装置１は、ステップＳ２５の処理に進む。一方、メンテナンス不可能と判定した場合（ステップＳ２４でＮｏ）、キャッシュメンテナンス装置１は、ステップＳ２７の処理に進む。
【００８４】
ステップ２４の処理に続いて、キャッシュメンテナンス装置１は、キャッシュメンテナンス部６１によって、ステップＳ２０で出力したキャッシュエントリ識別子に対応するキャッシュエントリ１ＣＥのメンテナンスを行う（ステップＳ２５）。
【００８５】
ステップ２５の処理に続いて、キャッシュメンテナンス装置１は、キャッシュメンテナンス部６１によって、ステップＳ２０で出力したキャッシュエントリ識別子に対応するキャッシュエントリ１ＣＥについて、キャッシュエントリ更新情報を更新する（ステップＳ２６）。例えば、キャッシュメンテナンス装置１は、キャッシュメンテナンス部６１によって、キャッシュエントリ更新情報のメンテナンスカウントを「０」に更新（リセット）し、前回のメンテナンス時刻を現在時刻で更新する。なお、ステップＳ２６では、キャッシュエントリ更新情報として、キャッシュエントリ参照回数を記憶して利用する場合、これらの値の更新（リセット）を行っても良い。
【００８６】
ステップ２６の処理又はステップＳ２４でＮｏの後に続いて、キャッシュメンテナンス装置１は、キャッシュメンテナンス部６１によって、ステップＳ２０で出力した未処理リストに含まれる、全てのメンテナンス対象となるキャッシュエントリ１ＣＥを処理（メンテナンス）したか否かを判定する（ステップＳ２７）。
【００８７】
ここで、全てのメンテナンス対象を処理したと判定した場合（ステップＳ２７でＹｅｓ）、キャッシュメンテナンス装置１は、メンテナンスを終了する。一方、全てのメンテナンス対象を処理していないと判定した場合（ステップＳ２７でＮｏ）、キャッシュメンテナンス装置１は、ステップＳ２１の処理に戻る。
【００８８】
＜ステップＳ２３の詳細：メンテナンス条件の評価＞
以下、図６を参照して、図５のステップＳ２３（メンテナンス条件を評価）の詳細について説明する。まず、キャッシュメンテナンス装置１は、メンテナンス判定部５１によって、ステップＳ２０で出力したキャッシュエントリ識別子に対応するキャッシュエントリ１ＣＥについて、メンテナンス条件記憶部２１を参照してメンテナンス条件を取得し、更新情報記憶部１１を参照してキャッシュエントリ更新情報を取得する（ステップＳ２３１）。
【００８９】
ステップＳ２３１の処理に続いて、キャッシュメンテナンス装置１は、メンテナンス判定部５１によって、ステップＳ２３１で取得したメンテナンス条件にステップＳ２３１で取得したキャッシュエントリ更新情報を代入してメンテナンス条件を評価し、この評価結果に応じた真偽値を出力する（ステップＳ２３２）。
【００９０】
以上のように、第１実施形態に係るキャッシュメンテナンス装置１は、メンテナンス条件を満たす場合にのみ、キャッシュエントリ１ＣＥのメンテナンスを行うため、データベース１Ｂに高い頻度で更新処理が行われる環境においても、参照速度が低下せず、処理負荷の増大を最小限に抑えることができる。また、キャッシュメンテナンス装置１は、無効化方式を採用したときは、メンテナンスによってキャッシュエントリ１ＣＥが無効化される頻度が低減するので、キャッシュヒット率が大幅に向上する。さらに、キャッシュメンテナンス装置１は、再問い合わせ方式を採用したときは、メンテナンス条件の判定の処理負荷がメンテナンスの頻度を少なくして削減できるメンテナンスコストよりも十分に小さいため、メンテナンスコストを大幅に削減できる。
【００９１】
なお、キャッシュメンテナンス装置１を独立した装置として説明したが、本発明は、これに限定されない。例えば、図７に示すように、本発明は、ディスプレイ等の表示部Ｏと、キーボード、マウス等の入力部Ｉと、演算装置Ｃと、メモリ、ハードディスク等の記憶装置ＨとをシステムバスＢで接続した一般的なコンピュータで実現できる。具体的には、本発明は、このコンピュータの記憶装置Ｈを更新情報記憶部１１及びメンテナンス条件記憶部２１として協調動作させ、演算装置Ｃをメンテナンス条件生成部３１、メンテナンス対象選択部４１、メンテナンス判定部５１及びキャッシュメンテナンス部６１として協調動作させるキャッシュメンテナンスプログラムによって実現できる。このプログラムは、ネットワークＮを介して配布しても良く、ＣＤ−ＲＯＭやフラッシュメモリ等の記録媒体に書き込んで配布しても良い。この点、以後の実施形態でも同様である。
【００９２】
（第２実施形態：差分更新方式）
［キャッシュメンテナンスシステムの概略］
以下、図８を参照して、第２実施形態に係るキャッシュメンテナンスシステム２００の概略について、第１実施形態と異なる点を主に説明する。ここで、メンテナンスを行う際、不整合なキャッシュエントリ２ＣＥ内のデータを全て破棄してから再計算する再問い合わせ方式に比べ、キャッシュエントリ２ＣＥ内の一部分のみを更新する差分更新方式の方が、一般的には演算量が少なくなる。この差分更新方式は、どのようなキャッシュ２Ｃでも適用できるわけではなく、一定のデータベース環境を満たしている必要がある。キャッシュメンテナンスシステム２００は、このような差分更新方式を採用する場合の一例である。
【００９３】
データベース２Ｂは、元から格納されているテーブルＴに加えて、このテーブルＴ毎に、差分データを一時的に保存するための差分テーブルΔＴを格納するリレーショナルデータベースである。この差分テーブルΔＴは、テーブルＴに登録（ＩＮＳＥＲＴ）されたレコードのみを格納するものである。なお、図８では、差分テーブルΔＴ及びテーブルＴをそれぞれ１個示したが、差分テーブルΔＴ及びテーブルＴは、それぞれ複数であっても良い。
【００９４】
キャッシュ２Ｃは、図１のキャッシュ１Ｃと同様のものである。また、キャッシュエントリ２ＣＥは、データベース２Ｂの問い合わせ結果を保存の対象とする。
【００９５】
［キャッシュメンテナンス装置の構成］
以下、第２実施形態に係るキャッシュメンテナンス装置２の構成について、第１実施形態と異なる点を主に説明する。図８に示すように、キャッシュメンテナンス装置２は、メンテナンス条件記憶部２２と、メンテナンス条件生成部３２と、メンテナンス判定部５２と、キャッシュ差分メンテナンス部（キャッシュメンテナンス部）６２とを備える。なお、キャッシュ差分メンテナンス部６２が、請求項に記載のキャッシュメンテナンス部に相当する。
【００９６】
メンテナンス条件記憶部２２は、メンテナンス条件を記憶するハードディスク等の記憶手段である。このメンテナンス条件は、後記するメンテナンス判定部５２が、差分テーブルΔＴに格納したデータの件数や最も古いデータの時刻等の情報と比較して、テーブルＴに対応するキャッシュエントリ２ＣＥの更新を行うか否かを判定する条件式である。例えば、メンテナンス条件は、差分テーブルΔＴの差分データの件数をＡｎとすると、「Ａｎ＞１０件」のような条件となる。
【００９７】
メンテナンス条件生成部３２は、データベース２Ｂに格納されたテーブルＴ毎に、メンテナンス条件を生成してメンテナンス条件記憶部２４に書き込むものである。なお、メンテナンス条件生成部３２のメンテナンス条件の生成手法は、図１のメンテナンス条件生成部３１と同様のものであるため、説明を省略する。
【００９８】
メンテナンス判定部５２は、データベース２ＢのテーブルＴにおける差分データを格納した差分テーブルΔＴを参照し、差分テーブルΔＴのデータ件数をメンテナンスカウントとして算出するものである。また、メンテナンス判定部５２は、差分テーブルΔＴにおける最も古いデータを格納した時刻から現在時刻までを経過時間として算出する。そして、メンテナンス判定部５２は、メンテナンス条件記憶部２２に記憶したメンテナンス条件を参照し、算出した更新回数と経過時間とをメンテナンス条件に代入して、このメンテナンス条件を満たすときにメンテナンス可能と判定する。
【００９９】
キャッシュ差分メンテナンス部６２は、メンテナンス判定部５２がメンテナンス可能と判定したキャッシュエントリ２ＣＥについて、差分テーブルΔＴに格納した差分データをキャッシュエントリ２ＣＥに一括して更新（メンテナンス）するものである。そして、キャッシュ差分メンテナンス部６２は、一括して更新した差分データを差分テーブルΔＴから削除する。
【０１００】
以下、図９を参照して、キャッシュ差分メンテナンス部６２によるメンテナンスについて、具体的に説明する（適宜図８参照）。図９に示すように、データベース２Ｂは、図示を省略した「ｍｅｓｓａｇｅ」というテーブルと、「Δｍｅｓｓａｇｅ」という差分テーブルΔＴと、「ｆｏｌｌｏｗｅｒ」というテーブルＴとを格納している。この差分テーブルΔＴは、ｉｄが６〜９の４レコードが格納されている。
【０１０１】
ここで、キャッシュエントリ２ＣＥの更新（メンテナンス）を行う場合、キャッシュ差分メンテナンス部６２は、１個のキャッシュエントリ２ＣＥに複数の差分データを一括して更新するための一括差分データを求める。例えば、キャッシュ差分メンテナンス部６２は、この一括差分データを求めるために、問い合わせＱ２をデータベース２Ｂに行う。この問い合わせＱ２は、図２５の問い合わせ９Ｑと比べ、差分テーブルΔＴの全レコードを用いている点、及び、キャッシュエントリ２ＣＥのｋｅｙを用いてグループ化を行う点が異なっている。そして、キャッシュ差分メンテナンス部６２は、一括差分データを、キャッシュエントリ２ＣＥのｋｅｙに対応するグループ毎に、キャッシュエントリ２ＣＥに更新する。つまり、キャッシュ差分メンテナンス部６２は、１以上の差分データをキャッシュエントリ２ＣＥに一括更新（メンテナンス）する。
【０１０２】
［キャッシュメンテナンス装置の動作］
＜ステップＳ２の詳細：メンテナンス＞
キャッシュメンテナンス装置２は、図４と同じ全体動作を行うため、説明を省略する。以下、キャッシュメンテナンス装置２における、図４のステップＳ２の動作が異なるため、図１０を参照し、これを説明する。
【０１０３】
予め、データベース２Ｂは、このデータベース２Ｂに対する更新を蓄積、つまり、差分テーブルを生成する（ステップＳ３０）。ここで、データベース２Ｂは、このデータベース２Ｂに対する登録（ＩＮＳＥＲＴ）問い合わせが入力され、この問い合わせに記述されたレコードをテーブルＴに登録する。このとき、データベース２Ｂは、このレコードを差分テーブルΔＴにも登録する。なお、ステップＳ３０の処理は、キャッシュメンテナンス装置２の動作でないことを明確にするため、破線で図示した。
【０１０４】
ステップＳ３１及びステップＳ３２の処理は、図５のステップ２３及びＳ２４と同様のものであるため、説明を省略する。
【０１０５】
ステップ３２の処理に続いて、キャッシュメンテナンス装置２は、キャッシュ差分メンテナンス部６２によって、キャッシュエントリ２ＣＥの一括更新（メンテナンス）を行う（ステップＳ３３）。
【０１０６】
＜ステップＳ３３の詳細：キャッシュエントリの一括更新＞
以下、図１１を参照して、図１０のステップＳ３３（キャッシュエントリの一括更新）の詳細について説明する。まず、キャッシュメンテナンス装置２は、キャッシュ差分メンテナンス部６２によって、差分テーブルΔＴとテーブルＴとから、一括差分データを求める（ステップＳ３３１）。ここでは、キャッシュメンテナンス装置２は、キャッシュ差分メンテナンス部６２によって、データベース２Ｂに図９の問い合わせＱ２を行い、全てのキャッシュエントリ２ＣＥについての一括差分データを求める。
【０１０７】
ステップＳ３３１の処理に続いて、キャッシュメンテナンス装置２は、キャッシュ差分メンテナンス部６２によって、ステップＳ３３１で求めた一括差分データで１個のキャッシュエントリ２ＣＥを一括更新する（ステップＳ３３２）。そして、キャッシュメンテナンス装置２は、キャッシュ差分メンテナンス部６２によって、一括差分データを更新したキャッシュエントリ２ＣＥに対応するテーブルＴの識別子（例えば、テーブルＴの名称）と、一括更新が行われていないキャッシュエントリ２ＣＥの一括差分データである未処理一括差分データとを出力する。
【０１０８】
ステップＳ３３２の処理に続いて、キャッシュメンテナンス装置２は、キャッシュ差分メンテナンス部６２によって、一括差分データを全て処理したか否かを判定する（ステップＳ３３３）。ここでは、キャッシュメンテナンス装置２は、キャッシュ差分メンテナンス部６２によって、ステップＳ３３２で未処理一括差分データが出力されなかったとき、一括差分データを全て処理したと判定する。
【０１０９】
ここで、一括差分データを全て処理したと判定した場合（ステップＳ３３３でＹｅｓ）、キャッシュメンテナンス装置２は、ステップＳ３３４の処理に進む。一方、一括差分データを全て処理していないと判定した場合（ステップＳ３３３でＮｏ）、キャッシュメンテナンス装置２は、ステップＳ３３２の処理に戻る。
【０１１０】
ステップＳ３３３の処理に続いて、キャッシュメンテナンス装置２は、キャッシュ差分メンテナンス部６２によって、ステップＳ３３２で更新した一括差分データを差分テーブルΔＴから削除する（ステップＳ３３４）。ここでは、キャッシュメンテナンス装置２は、キャッシュ差分メンテナンス部６２によって、ステップＳ３３２で出力した識別子が示す全てのテーブルＴについて、このテーブルＴの全レコードを削除（ＤＥＬＥＴＥ）する。
【０１１１】
以上のように、第２実施形態に係るキャッシュメンテナンス装置２は、メンテナンス条件を満たす場合にのみ、キャッシュエントリ２ＣＥのメンテナンスを行うため、データベース２Ｂに高い頻度で更新処理が行われる環境においても、参照速度が低下せず、処理負荷の増大を最小限に抑えることができる。また、キャッシュメンテナンス装置２は、メンテナンス条件を満たす場合にのみ差分データでキャッシュエントリ２ＣＥを一括更新し、メンテナンスの頻度を制御することとした。これによって、キャッシュメンテナンス装置２は、差分更新方式を採用したときは、メンテナンスによって逐次差分データをキャッシュエントリ２ＣＣＥに更新する場合に比べて、問い合わせ処理及び通信処理のオーバーヘッドが大幅に少ないため、メンテナンスコストを大幅に削減できる。
【０１１２】
（第３実施形態：無効化方式又は再問い合わせ方式）
［キャッシュメンテナンス装置の構成］
以下、図１２を参照して、第３実施形態に係るキャッシュメンテナンス装置３の構成について、第１実施形態と異なる点を主に説明する。キャッシュメンテナンス装置３は、統計情報を用いて、予め設定された目標負荷を達成するまでメンテナンスを行う点が、キャッシュメンテナンス装置１と大きく相違する。
【０１１３】
このため、図１２に示すように、キャッシュメンテナンス装置３は、更新情報記憶部１３と、メンテナンス条件記憶部２３と、メンテナンス条件生成部３３と、メンテナンス対象選択部４３と、メンテナンス判定部５３と、キャッシュメンテナンス部６３と、統計情報算出部７３とを備える。
【０１１４】
更新情報記憶部１３は、キャッシュエントリ更新情報を記憶するハードディスク等の記憶手段である。ここでは、図１３に示すように、キャッシュエントリ更新情報は、キャッシュエントリ識別子と、メンテナンスカウントと、前回のメンテナンス時刻と、累積参照回数と、累積メンテナンス回数とを有する。この累積参照回数は、予め設定された統計期間におけるキャッシュエントリ３ＣＥが参照された参照回数の累積値である。また、この累積メンテナンス回数は、統計期間におけるキャッシュエントリ３ＣＥをメンテナンスした回数を示すメンテナンス回数の累積値である。つまり、キャッシュエントリ更新情報のデータ項目のうち、累積参照回数及び累積メンテナンス回数がキャッシュエントリ統計情報（統計情報）となる。なお、累積参照回数及び累積メンテナンス回数は、後記する統計情報算出部７３がキャッシュエントリ更新情報に書き込む。
【０１１５】
図１２のメンテナンス条件記憶部２３は、メンテナンス条件を記憶するハードディスク等の記憶手段である。ここでは、図１４に示すように、メンテナンス条件は、キャッシュエントリ３ＣＥ毎に生成される。
【０１１６】
図１２のメンテナンス条件生成部３３は、予め設定された許容遅延回数及び許容遅延時間の少なくとも一方と、メンテナンスコストの目標負荷値とが入力され、この入力に基づいて、キャッシュエントリ３ＣＥ毎に、メンテナンス条件を生成してメンテナンス条件記憶部２３に書き込むものである。ここで、メンテナンス条件生成部３３は、キャッシュエントリ３ＣＥ毎に、許容遅延回数及び許容遅延時間の少なくとも一方が入力される。さらに、メンテナンス条件生成部３３は、設定ファイルから目標負荷値を読み取り、又は、入力部によって目標負荷値が入力される。ここで、この目標負荷値は、例えば、０を超え、かつ、１００未満の値で入力される。
【０１１７】
そして、メンテナンス条件生成部３３は、目標負荷を達成するか、又は、全てのキャッシュエントリ３ＣＥのメンテナンス条件を生成するまで、キャッシュエントリ３ＣＥ毎にメンテナンス条件を生成する。このとき、メンテナンス条件生成部３３は、メンテナンス条件生成部３３は、メンテナンス条件を生成しておらず、かつ、メンテナンス回数の累積値が最大となるキャッシュエントリ３ＣＥを選択することが好ましい。又は、メンテナンス対象選択部４３は、メンテナンス条件生成部３３がメンテナンス条件を生成しておらず、かつ、参照回数の累積値が最小となるキャッシュエントリ３ＣＥを選択することが好ましい。なお、メンテナンス条件の生成の詳細については、後記する。
【０１１８】
メンテナンス対象選択部４３は、図１のメンテナンス対象選択部４１と同様に、キャッシュエントリ３ＣＥを選択するものである。
【０１１９】
メンテナンス判定部５３は、図１のメンテナンス判定部５１と同様に、メンテナンス対象選択部４３が選択したキャッシュエントリ３ＣＥについて、メンテナンス条件記憶部２１に記憶したメンテナンス条件を参照し、メンテナンス条件を満たすときにメンテナンス可能と判定するものである。
【０１２０】
キャッシュメンテナンス部６３は、図１のキャッシュメンテナンス部６１と同様に、メンテナンス対象選択部４３が選択したキャッシュエントリについて、メンテナンス判定部５３がメンテナンス可能と判定した場合、キャッシュエントリ３ＣＥをメンテナンスするものである。
【０１２１】
統計情報算出部７３は、予め設定された統計期間における累積参照回数と、累積メンテナンス回数とを算出するものである。ここで、統計情報算出部７３は、キャッシュメンテナンス装置３を統計期間運用して、累積参照回数及び累積メンテナンス回数を算出する。そして、統計情報算出部７３は、この累積参照回数及び累積メンテナンス回数をキャッシュエントリ更新情報として、更新情報記憶部１３に書き込む。
【０１２２】
［キャッシュメンテナンス装置の動作］
キャッシュメンテナンス装置３は、図４と同じ全体動作を行うため、説明を省略する。以下、キャッシュメンテナンス装置３における、図４のステップＳ１の動作が異なるため、図１５を参照し、これを説明する。
【０１２３】
＜ステップＳ１の詳細：メンテナンス条件の生成＞
図１５に示すように、キャッシュメンテナンス装置３は、統計情報算出部７３によって、キャッシュエントリ統計情報を取得（算出）する（ステップＳ４０）。そして、キャッシュメンテナンス装置３は、統計情報算出部７３によって、このキャッシュエントリ統計情報を更新情報記憶部１３に書き込む。なお、ステップＳ４０の詳細は、後記する。
【０１２４】
ステップＳ４０の処理に続いて、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、許容遅延回数及び許容遅延時間の少なくとも一方と、メンテナンスコストの目標負荷値とを取得（入力）する（ステップＳ４１）。
【０１２５】
ステップＳ４１の処理に続いて、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、ステップＳ４１で取得した目標負荷値に基づいて、削減目標値を算出する（ステップＳ４２）。ここで、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、キャッシュエントリ統計情報を参照して、式（４）を用いて、削減目標値を算出する。なお、式（４）では、Ｄｇは削減目標値、ΣＭｉは全てのキャッシュエントリの累積メンテナンス回数を示し、Ｇは目標負荷値を示す。
Ｄｇ＝ΣＭｉ×Ｇ／１００・・・式（４）
【０１２６】
ステップＳ４２の処理に続いて、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、メンテナンス条件を生成していないキャッシュエントリ３ＣＥから、１個のキャッシュエントリ３ＣＥを選択する（ステップＳ４３）。そして、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、選択した１個のキャッシュエントリ３ＣＥを示すキャッシュエントリ識別子を出力する。なお、ステップＳ４３の処理の詳細は、後記する。
【０１２７】
ステップＳ４３の処理に続いて、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、ステップＳ４３で出力したキャッシュエントリ識別子に対応するキャッシュエントリ３ＣＥについて、メンテナンス条件を生成すると共に、削減値を算出する（ステップＳ４４）。ここで、ステップＳ４１で許容遅延回数のみが入力された場合、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、式（１）を用いて削減値を算出し、式（５）で表されるメンテナンス条件を生成する。
Ａ＝Ｍｉ×（Ｎ−１）／Ｎ・・・式（１）
Ｍｃ＞Ｎ                ・・・式（５）
【０１２８】
また、ステップＳ４１で許容遅延時間のみが入力された場合、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、式（２）を用いて削減値を算出し、式（６）で表されるメンテナンス条件を生成する。
Ａ＝Ｍｉ×（１−Ｔ／Ｓ）・・・式（２）
Ｐｔ＞Ｔ                ・・・式（６）
【０１２９】
また、ステップＳ４１で許容遅延回数と許容遅延時間との両方が入力された場合、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、式（３）を用いて削減値を算出し、式（７）で表されるメンテナンス条件を生成する。
【０１３０】
Ａ＝ＭＩＮ［｛Ｍｉ×（Ｎ−１）／Ｎ｝，{Ｍｉ×（１−Ｔ／Ｓ）}］・・・式（３）
（Ｍｃ＞Ｎ）ＯＲ（Ｐｔ＞Ｔ）                                  ・・・式（７）
【０１３１】
但し、前記した式（１）〜式（３）において、Ａは削減値、Ｍｉはメンテナンス回数の累積値、Ｎは許容遅延回数、Ｔは許容遅延時間、及び、Ｓは統計期間である。また、前記した式（５）〜式（７）において、Ｍｃはメンテナンスカウントを示し、Ｐｔは経過時間を示し、ＯＲはＯＲ条件を示し、ＭＩＮは最小値を出力する関数である。
【０１３２】
また、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、メンテナンス条件を生成する毎に、削減目標値（Ｄｇ）から削減値（Ａ）を減算する。そして、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、減算後の削減目標値を出力する。
【０１３３】
ステップＳ４４の処理に続いて、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、目標負荷を達成したか、又は、全てのキャッシュエントリ３ＣＥのメンテナンス条件を生成した否かを判定する（ステップＳ４５）。ここで、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、ステップＳ４４で出力した減算後の削減目標値が０以下の値となった場合、目標負荷を達成したと判定する。
【０１３４】
ここで、目標負荷を達成したか、又は、全てのキャッシュエントリ３ＣＥのメンテナンス条件を生成したと判定した場合（ステップ４５でＹｅｓ）、キャッシュメンテナンス装置３は、ステップＳ４６の処理に進む。目標負荷を達成せず、かつ、全てのキャッシュエントリ３ＣＥのメンテナンス条件を生成していないと判定した場合（ステップ４５でＮｏ）、キャッシュメンテナンス装置３は、ステップＳ４３の処理に戻る。
【０１３５】
ステップＳ４５の処理に続いて、キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、メンテナンス条件を生成していないキャッシュエントリ３ＣＥが存在する場合、このキャッシュエントリ３ＣＥについて、式（８）で表されるメンテナンス条件を生成する（ステップＳ４６）。なお、式（８）は、データベース３Ｂのデータと、これに対応するキャッシュエントリ３ＣＥとの間に不整合が発生した場合、目標負荷に関係なく、常にメンテナンスを行うことを示す。
Ｍｃ＞１・・・式（８）
【０１３６】
＜ステップＳ４０の詳細：キャッシュエントリ統計情報の取得＞
以下、図１６を参照して、図１５のステップＳ４０（キャッシュエントリ統計情報の取得）の詳細について説明する。まず、キャッシュメンテナンス装置３は、統計情報算出部７３によって、設定ファイルから統計期間を読み取り、又は、入力部によって統計期間が入力される（ステップＳ４０１）。
【０１３７】
ステップＳ４０１の処理に続いて、キャッシュメンテナンス装置３は、統計情報算出部７３によって、ステップＳ４０１で入力された統計期間における、参照回数及びメンテナンス回数を算出し、キャッシュエントリ統計情報に書き込む（ステップＳ４０２）。このメンテナンス回数は、無効化方式では無効化メッセージ、再問い合わせ方式及び差分更新方式ではキャッシュエントリ３ＣＥへの書き込みリクエストの回数である。
【０１３８】
ステップＳ４０２の処理に続いて、キャッシュメンテナンス装置３は、統計情報算出部７３によって、ステップＳ４０１で入力された統計期間が終了したか否かを判定する（ステップＳ４０３）。ここで、統計期間が終了したと判定した場合（ステップ４０３でＹｅｓ）、キャッシュメンテナンス装置３は、処理を終了する。一方、統計期間が終了していないと判定した場合（ステップ４０３でＮｏ）、キャッシュメンテナンス装置３は、ステップＳ４０２の処理に戻る。
【０１３９】
＜ステップＳ４３の詳細：キャッシュエントリの選択：第１例＞
以下、図１７を参照して、図１５のステップＳ４３（キャッシュエントリの選択）の第１例について説明する。キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、メンテナンス条件を生成しておらず、かつ、メンテナンス回数の累積値が最大となるキャッシュエントリ３ＣＥを選択する（ステップＳ４３１）。
【０１４０】
これによって、キャッシュメンテナンス装置３は、メンテナンスの頻度が高いキャッシュ程、メンテナンスの頻度を削減による効果（例えば、無効化方式を採用したときはキャッシュヒット率の向上、再問い合わせ方式を採用したときは処理負荷の削減）が大きくなる。従って、キャッシュメンテナンス装置３は、メンテナンス条件を設定してメンテナンスを行うキャッシュの数を必要最小限とし、キャッシュの最新性の低下を最小限に抑える。
【０１４１】
＜ステップＳ４３の詳細：キャッシュエントリの選択：第２例＞
以下、図１８を参照して、図１５のステップＳ４３（キャッシュエントリの選択）の第２例について説明する。キャッシュメンテナンス装置３は、メンテナンス条件生成部３３によって、メンテナンス条件生成部３３がメンテナンス条件を生成しておらず、かつ、参照回数の累積値が最小となるキャッシュエントリ３ＣＥを選択する（ステップＳ４３２）。
【０１４２】
これによって、キャッシュメンテナンス装置３は、メンテナンスによる悪影響が少ないキャッシュから順にメンテナンスを行うことで、キャッシュの最新性の低下を最小限に抑える。
【０１４３】
以上のように、第３実施形態に係るキャッシュメンテナンス装置３は、メンテナンス条件を満たす場合にのみ、キャッシュエントリ３ＣＥのメンテナンスを行うため、データベース３Ｂに高い頻度で更新処理が行われる環境においても、参照速度が低下せず、処理負荷の増大を最小限に抑えることができる。また、キャッシュメンテナンス装置３は、無効化方式を採用したときは、メンテナンスによってキャッシュが無効化される頻度が低減するので、キャッシュヒット率が大幅に向上する。さらに、キャッシュメンテナンス装置３は、再問い合わせ方式を採用したときは、メンテナンス条件の判定の処理負荷がメンテナンスの頻度を少なくして削減できるメンテナンスコストよりも十分に小さいため、メンテナンスコストを大幅に削減できる。さらに、キャッシュメンテナンス装置３は、目標負荷を達成した後、不要なメンテナンスを行うことがなく、処理負荷をさらに削減できる。
【０１４４】
（第４実施形態：無効化方式又は再問い合わせ方式）
［キャッシュメンテナンス装置の構成］
以下、図１９を参照して、第４実施形態に係るキャッシュメンテナンス装置４の構成について、第１実施形態と異なる点を主に説明する。キャッシュメンテナンス装置４は、データベースの負荷情報をメンテナンス条件に反映させる点が、キャッシュメンテナンス装置１と大きく相違する。
【０１４５】
このため、図１９に示すように、キャッシュメンテナンス装置４は、更新情報記憶部１４と、メンテナンス条件記憶部２４と、メンテナンス条件生成部３４と、メンテナンス対象選択部４４と、メンテナンス判定部５４と、キャッシュメンテナンス部６４と、データベース負荷測定部８４とを備える。
【０１４６】
メンテナンス条件記憶部２４は、メンテナンス条件を記憶するハードディスク等の記憶手段である。ここでは、図２０に示すように、メンテナンス条件は、後記する負荷条件が所定の閾値を超えるといった条件が付加される。なお、設定ファイルから負荷条件を読み取り、又は、入力部によって負荷条件が入力される。
【０１４７】
図１９のメンテナンス条件生成部３４は、図１のメンテナンス条件生成部３３と同様に、メンテナンス条件を生成してメンテナンス条件記憶部２４に書き込むものである。このとき、メンテナンス条件生成部３４は、このメンテナンス条件に、後記するデータベース負荷測定部８０が測定した負荷値が負荷条件を満たすという条件を付加する。例えば、メンテナンス条件生成部３４は、メンテナンス条件が「メンテナンスカウント＞１０回」の場合、「（メンテナンスカウント＞１０回）ＡＮＤ（ＣＰＵ使用率＞９０％）」というような負荷条件をＡＮＤ条件で付加する。
【０１４８】
データベース負荷測定部８４は、データベース４Ｂの負荷を示す負荷値を測定するものである。ここで、データベース負荷測定部８４は、データベース４Ｂを有するサーバのＣＰＵ使用率、インターフェース使用率、メモリ使用率、ディスクＩ／Ｏ値等の負荷値を測定する。なお、負荷条件とは、負荷値が予め設定された閾値以上又は負荷値がこの閾値以下であるといった条件を示す。
【０１４９】
なお、更新情報記憶部１４は、メンテナンス対象選択部４４は、メンテナンス判定部５４及びキャッシュメンテナンス部６４は、図１の各手段と同様のものであるため、説明を省略する。
【０１５０】
［キャッシュメンテナンス装置の動作］
＜ステップＳ１の詳細：メンテナンス条件の生成＞
キャッシュメンテナンス装置４は、図４と同じ全体動作を行うため、説明を省略する。以下、キャッシュメンテナンス装置４における、図４のステップＳ１の動作が異なるため、図２１を参照し、これを説明する。
【０１５１】
まず、キャッシュメンテナンス装置４は、メンテナンス条件生成部３４によって、許容遅延回数及び許容遅延時間の少なくとも一方を取得（入力）する（ステップＳ５０）。また、キャッシュメンテナンス装置４は、メンテナンス条件生成部３４によって、メンテナンス条件を生成する（ステップＳ５１）。そして、キャッシュメンテナンス装置４は、メンテナンス条件生成部３４によって、メンテナンス条件に負荷条件をＡＮＤ条件で付加する（ステップＳ５２）。
【０１５２】
＜ステップＳ２３の詳細：メンテナンス条件の評価＞
以下、キャッシュメンテナンス装置４における、図５のステップＳ２３の動作が異なるため、図２１を参照し、これを説明する。まず、キャッシュメンテナンス装置４は、メンテナンス判定部５４によって、メンテナンス対象となるキャッシュエントリ４ＣＥについて、メンテナンス条件記憶部２４を参照してメンテナンス条件を取得し、更新情報記憶部１４を参照してキャッシュエントリ更新情報を取得する（ステップＳ６０）。
【０１５３】
ステップＳ６０の処理に続いて、キャッシュメンテナンス装置４は、データベース負荷測定部８４によって、負荷値を測定する（ステップＳ６１）。
【０１５４】
ステップＳ６１の処理に続いて、キャッシュメンテナンス装置４は、メンテナンス判定部５４によって、ステップＳ６０で取得したメンテナンス条件に、ステップＳ６１で取得したキャッシュエントリ更新情報とステップＳ６２で測定した負荷値とを代入してメンテナンス条件を評価し、この評価結果に応じた真偽値を出力する（ステップＳ６２）。
【０１５５】
以上のように、第４実施形態に係るキャッシュメンテナンス装置４は、メンテナンス条件を満たす場合にのみキャッシュエントリ４ＣＥのメンテナンスを行い、メンテナンスの頻度を制御することとした。これによって、キャッシュメンテナンス装置４は、無効化方式を採用したときは、メンテナンスによってキャッシュが無効化される頻度が低減するので、キャッシュヒット率が大幅に向上する。また、キャッシュメンテナンス装置４は、再問い合わせ方式を採用したときは、メンテナンス条件の判定の処理負荷がメンテナンスの頻度を少なくして削減できるメンテナンスコストよりも十分に小さいため、メンテナンスコストを大幅に削減できる。さらに、キャッシュメンテナンス装置４は、負荷条件を設定することで、データベースの負荷に応じて、メンテナンスの頻度を制御することができる。これによって、キャッシュメンテナンス装置４は、例えば、データベースサーバのＣＰＵ資源に余裕があるときにメンテナンスの頻度を低下させてＣＰＵ資源を節約するといった事態を防止し、データベース４Ｂにパフォーマンスを十分に発揮させることができる。
【０１５６】
なお、キャッシュメンテナンス装置４は、第１実施形態と同様の手法でメンテナンス条件を設定することとして説明したが、これに限定されない。キャッシュメンテナンス装置４は、第３実施形態と同様に、目標負荷を達成するまで、負荷条件が負荷されたメンテナンス条件を生成することとしても良い。この場合、キャッシュメンテナンス装置４は、メンテナンス回数が大きい順に、又は、参照回数が小さい順にメンテナンス条件を生成することとしても良い。
【実施例】
【０１５７】
以下、本発明の実施例について説明する（適宜図８，図９参照）。ここでは、図８で示したキャッシュメンテナンスシステム２００を以下の環境で実装し、このときのキャッシュメンテナンス装置２の検証結果を示して説明する。
【０１５８】
本実施では、アプリケーションサーバは、下記のサーバ１台で構成した。
ＣＰＵ          ：Ｘｅｏｎ（登録商標）  Ｘ５４７０  ３．３ＧＨｚ×１
メモリ          ：３２Ｇバイト
ハードディスク  ：１．５Ｔバイト（ＲＡＩＤ１０）
ミドルウェア    ：ｒｕｂｙ１．８．５，ＭｙＳＱＬ５．０
【０１５９】
また、本実施では、データベースサーバ２Ｂは、下記のサーバ１台で構成した。
ＣＰＵ          ：Ｘｅｏｎ（登録商標）  Ｘ５３５５  ２．６６ＧＨｚ×２
メモリ          ：１６Ｇバイト
ハードディスク  ：１．５Ｔバイト（ＲＡＩＤ１０）
ミドルウェア    ：ＭｙＳＱＬ５．０，ｌｉｂｍｅｍｃａｃｈｅｄ０．２３
【０１６０】
また、本実施では、キャッシュ２Ｃは、下記のサーバ１０台で構成した。
ＣＰＵ          ：Ｃｅｌｅｒｏｎ（登録商標）  Ｘ４３０  １．８ＧＨｚ×１
メモリ          ：２Ｇバイト
ハードディスク  ：５００Ｇバイト
ミドルウェア    ：ｍｅｍｃａｃｈｅｄ１．２．６
【０１６１】
また、本実施では、ミニブログサービスである「ｇｏｏひとこと」を対象としてクローリングを行い、ユーザ同士の友好関係の情報（「ｆｏｌｌｏｗｅｒ」テーブル）と、各ユーザが投稿したメッセージの情報（「ｍｅｓｓａｇｅ」テーブル）とを取得し、これらをサンプルデータとしてデータベース２Ｂに格納した。このサンプルデータの詳細を下記に示す。
「ｍｅｓｓａｇｅ」テーブル  ：１１２８３００件
「ｆｏｌｌｏｗｅｒ」テーブル：７０８０３件
有効ユーザ数                ：１６５９６人
対象期間                    ：２００８年５月〜１１月
【０１６２】
そして、前記したデータの一部をデータベース２Ｂに登録（ＩＮＳＥＲＴ）する問い合わせを、２分間、高負荷となるように行い、このときの更新スループットの限界値を測定した。なお、許容遅延回数を１０回に設定したものを実施例１とする。また、同一条件にて、従来技術（常時メンテナンス方式）による更新スループットの限界値も合わせて測定した。これを比較例１とする。
【０１６３】
以下に、実施例１，２及び比較例１の更新スループットの限界値を示す。なお、この更新スループットの限界値は、数値が高いほど、メンテナンスコストが小さいことを示す。
実施例１：２１３．４件／秒
比較例１：  ８９．６件／秒
【０１６４】
前記した測定結果から、比較例１での更新スループットの限界値が８９．６件／秒であるのに対し、実施例１の更新スループットの限界値は２１３．４件／秒となっており、更新スループットの限界値が向上してメンテナンスコストが低減されていることがわかる。
【０１６５】
また、キャッシュメンテナンスシステム２００において、許容遅延回数を徐々に増加させたものを実施例２として説明する。そして、実施例２における許容遅延回数と更新スループットの限界値との関係を測定し、この結果を図２３に示す。なお、図２３では、横軸が許容遅延回数であり、縦軸が更新スループットの限界値である。
【０１６６】
図２３の結果から、実施例２では、許容遅延回数を増加させる程、更新スループットの限界値が向上することがわかる。ここで、比較例１と対して、実施例２は、更新スループットの限界値が最大で２７倍となる。つまり、本発明に係るキャッシュメンテナンス装置２は、許容遅延回数を多くする程、メンテナンスコストを低減できることがわかる。
【０１６７】
なお、図２３において、許容遅延回数が１回の場合（図２３の左端）、実施例２が、比較例１と略同等の測定結果となる点について補足する。実施例２では、許容遅延回数が１回の場合、比較例１と同じ頻度でメンテナンスを行うことになるのに加え、メンテナンス判定のコストが別途発生する。このため、図２３の左端に示すように、実施例２と比較例１との測定結果が略同等になると考えられる。
【符号の説明】
【０１６８】
・    キャッシュメンテナンス装置
１Ｂ，２Ｂ，３Ｂ，４Ｂ  データベース
１Ｃ，２Ｃ，３Ｃ，４Ｃ  キャッシュ
１ＣＥ，２ＣＥ，３ＣＥ，４ＣＥ  キャッシュエントリ
１１，１３，１４  更新情報記憶部
２１，２２，２３，２４  メンテナンス条件記憶部
３１，３２，３３，３４  メンテナンス条件生成部
４１，４３，４４  メンテナンス対象選択部
５１，５２，５３，５４  メンテナンス判定部
６１，６３，６４  キャッシュメンテナンス部
６２  キャッシュ差分メンテナンス部（キャッシュメンテナンス部）
７３  統計情報算出部
８４  データベース負荷測定部
１００，２００，３００，４００  キャッシュメンテナンスシステム
【図１】
2010198258.tif 000003
【図２】
2010198258.tif 000004
【図３】
2010198258.tif 000005
【図４】
2010198258.tif 000006
【図５】
2010198258.tif 000007
【図６】
2010198258.tif 000008
【図７】
2010198258.tif 000009
【図８】
2010198258.tif 000010
【図９】
2010198258.tif 000011
【図１０】
2010198258.tif 000012
【図１１】
2010198258.tif 000013
【図１２】
2010198258.tif 000014
【図１３】
2010198258.tif 000015
【図１４】
2010198258.tif 000016
【図１５】
2010198258.tif 000017
【図１６】
2010198258.tif 000018
【図１７】
2010198258.tif 000019
【図１８】
2010198258.tif 000020
【図１９】
2010198258.tif 000021
【図２０】
2010198258.tif 000022
【図２１】
2010198258.tif 000023
【図２２】
2010198258.tif 000024
【図２３】
2010198258.tif 000025
【図２４】
2010198258.tif 000026
【図２５】
2010198258.tif 000027