(57)【特許請求の範囲】
【請求項１】
少なくとも１つの遠隔サーバに向けられたデータベース照会にローカル・サーバが応じるための方法であって、
前記ローカル・サーバが、前記遠隔サーバの従前のデータベース照会の結果を動的に前記ローカル・サーバの共有テーブルにキャッシュする段階であって、前記共有テーブルが包含関係チェック可能照会に応じて受け取られた結果を保管するものである段階と、
前記ローカル・サーバが、新しいデータベース照会に応じる際に前記共有テーブルにキャッシュされた結果を用いる段階と、
従前の照会結果のデータ整合性を確保する段階であって、
前記遠隔サーバが、前記遠隔サーバの基本テーブルに適用された更新、削除、及び挿入を含むリフレッシュ・メッセージを、前記更新、削除及び挿入のトランザクションにおける最大のタイムスタンプと共に前記ローカル・サーバに送る段階、
前記ローカル・サーバが、前記リフレッシュ・メッセージを受信するたびに、前記更新、削除、及び挿入を前記共有テーブルに適用する段階、
前記ローカル・サーバが、前記遠隔サーバから受信した最後のリフレッシュ・メッセージのタイムスタンプを、前記遠隔サーバで実行された新しい照会への応答と共に前記遠隔サーバから戻された前記新しい照会のタイムスタンプと比較する段階、及び
前記ローカル・サーバが、前記新しい照会のタイムスタンプが前記最後のリフレッシュ・メッセージのタイムスタンプを超える場合に、前記新しい照会への応答を前記共有テーブルに挿入すると共に、前記遠隔サーバから待機中のリフレッシュ・メッセージを引き出す段階
を含む前記確保する段階と、
を含む方法。
【請求項２】
前記キャッシュする段階が、単一のデータベース・テーブル上の単純照会及び上位Ｎ個の照会の結果を前記共有テーブルに挿入する段階を含み、前記単純照会が前記基本テーブルの行及び列のサブセットを照会結果とする照会であり、
前記ローカル・サーバが、複合照会の結果を、照会結果ごとに１つずつ別個のテーブルに格納する段階を更に含む、請求項１に記載の方法。
【請求項３】
前記別個のテーブルが完全一致リポジトリを形成し、
新しい照会が複合照会の場合に、前記ローカル・サーバが、前記完全一致リポジトリにおいて前記新しい照会への応答を検索する段階と、
前記新しい照会が複合照会でない場合に、前記ローカル・サーバが、前記共有テーブルにおいて前記新しい照会への応答を検索する段階と、
を更に含む、請求項２に記載の方法。
【請求項４】
前記共有テーブルにおいて前記新しい照会への応答を検索する段階が、
前記新しい照会の結果が、前記共有テーブルに格納された照会結果の和集合に含まれるかどうかを判断する段階と、
前記和集合に含まれる場合に、前記新しい照会において記載されるテーブルの名前を前記共有テーブルの名前に置き換える段階と、
前記新しい照会が上位Ｎ個の照会である場合に、前記共有テーブルから受信した行数を数え、前記行数が、照会要求元のアプリケーションによって要求される行数を超えない場合に、前記新しい照会を修正し、修正した照会を前記遠隔サーバに送信し、前記遠隔サーバから受信した結果を前記共有テーブルに格納し、前記修正した照会の述部を前記共有テーブルの索引に付加し、前記アプリケーションによって要求された結果を前記アプリケーションに戻す段階と、
を含む、請求項３に記載の方法。
【請求項５】
前記完全一致リポジトリにおいて前記新しい照会への応答を検索する段階が、
前記新しい照会のＳＯＬ文字列が前記完全一致リポジトリ内に見出された場合に、前記ＳＱＬ文字列に対応する照会結果を前記完全一致リポジトリから照会要求元のアプリケーションに戻す段階と、
前記新しい照会の前記ＳＱＬ文字列が前記完全一致リポジトリ内に見出されない場合に、前記新しい照会を前記遠隔サーバに送信する段階と、
前記遠隔サーバから受信した照会結果を前記完全一致リポジトリに挿入する段階と、
前記完全一致リポジトリに挿入した照会結果を前記新しい照会の前記ＳＱＬ文字列と関連付ける段階と、
を含む、請求項３に記載の方法。
【請求項６】
前記ローカル・サーバが、前記共有テーブルからデータを追い出すために、
前記共有テーブルに新しい列を付加する段階と、
前記新しい列内のエントリを偽に設定する段階と、
前記共有テーブル内で維持すべき照会を特定する段階と、
前記維持すべき照会を再実行して、前記新しい列内の対応するエントリを真に設定する段階と、
前記新しい列のエントリが依然として偽である前記共有テーブル内の行を削除する段階と、
を更に含む、請求項１乃至５のいずれかに記載の方法。
【請求項７】
少なくとも１つの遠隔サーバに向けられたデータベース照会にローカル・サーバが応じるためのシステムであって、
前記遠隔サーバの従前のデータベース照会の結果を動的に前記ローカル・サーバの共有テーブルにキャッシュする手段であって、前記共有テーブルが包含関係チェック可能照会に応じて受け取られた結果を保管するものである手段と、
前記ローカル・サーバによって新しいデータベース照会に応じる際に前記共有テーブルにキャッシュされた結果を用いる手段と、
従前の照会結果のデータ整合性を確保する手段であって、
前記遠隔サーバの基本テーブルに適用された更新、削除、及び挿入を含むリフレッシュ・メッセージを、前記更新、削除及び挿入のトランザクションにおける最大のタイムスタンプと共に前記遠隔サーバから前記ローカル・サーバに送る手段、
前記リフレッシュ・メッセージを受信するたびに、前記更新、削除、及び挿入を前記共有テーブルに適用する手段、
前記遠隔サーバから受信した最後のリフレッシュ・メッセージのタイムスタンプを、前記遠隔サーバで実行された新しい照会への応答と共に前記遠隔サーバから戻された前記新しい照会のタイムスタンプと比較する手段、及び
前記新しい照会のタイムスタンプが前記最後のリフレッシュ・メッセージのタイムスタンプを超える場合に、前記新しい照会への応答を前記共有テーブルに挿入すると共に、前記遠隔サーバから待機中のリフレッシュ・メッセージを引き出す手段、
を含む前記確保する手段と、
を含むシステム。
【請求項８】
少なくとも１つの遠隔サーバに向けられたデータベース照会にローカル・サーバが応じるためのプログラムであって、コンピュータに
前記遠隔サーバの従前のデータベース照会の結果を動的に前記ローカル・サーバの共有テーブルにキャッシュする手順であって、前記共有テーブルが包含関係チェック可能照会に応じて受け取られた結果を保管するものである手順と、
前記ローカル・サーバによって新しいデータベース照会に応じる際に前記共有テー部にキャッシュされた結果を用いる手順と、
従前の照会結果のデータ整合性を確保する手順であって、
前記遠隔サーバの基本テーブルに適用された更新、削除、及び挿入を含むリフレッシュ・メッセージを、前記更新、削除及び挿入のトランザクションにおける最大のタイムスタンプと共に前記遠隔サーバから前記ローカル・サーバに送る手順、
前記リフレッシュ・メッセージを受信するたびに、前記更新、削除、及び挿入を前記共有テーブルに適用する手順、
前記遠隔サーバから受信した最後のリフレッシュ・メッセージのタイムスタンプを、前記遠隔サーバで実行された新しい照会への応答と共に前記遠隔サーバから戻された前記新しい照会のタイムスタンプと比較する手順、及び
前記新しい照会のタイムスタンプが前記最後のリフレッシュ・メッセージのタイムスタンプを超える場合に、前記新しい照会への応答を前記共有テーブルに挿入すると共に、前記遠隔サーバから待機中のリフレッシュ・メッセージを引き出す手順
を含む前記確保する手順と、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、分散ネットワークにおけるデータベースのキャッシングに向けられる。
【背景技術】
【０００２】
分散ウェブ・アプリケーションの普及により、遠隔データベース・サーバに対するアプリケーション照会の頻度が増加している。こうした照会の性能を改善し、データ可用性を高めるために、こうしたアプリケーションは、ローカル・データベース・キャッシュを用いることができる。例えば、コンテンツ分散ネットワーク内のエッジ・サーバは、データ・アクセスをスピードアップし、ネットワーク・エッジにおいて動的なウェブコンテンツをより迅速に生成するために、近くのデータベース・キャッシュを用いることができる。
【０００３】
エッジ・サーバ上でデータをキャッシュするための典型的な技術は、（ｉ）ローカル・マシン上でのデータベース全体又は該データベースの明示的部分の明示的複製、或いは（ｉｉ）従前の照会応答をキャッシュすること及び前にキャッシュされた応答に対する新しい照会ステートメントの完全一致、のいずれかに依存している。複製手法において、キャッシュのコンテンツは、データベース・テーブルのどの部分をエッジ・ノード上で複製すべきかを判断しなければならない管理者によって、明示的に特定される。キャッシュ・コンテンツが、テーブル名又は「実体化ビュー」定義として特定されると、データが、起点サーバからエッジ・キャッシュにコピーされる。
【０００４】
照会応答キャッシュ手法において、アプリケーション照会の応答がキャッシュに動的に取り込まれる。キャッシュ内のデータは照会応答リストによって記述され、リスト内の各応答は、該応答を生成した照会ステートメントでタグ付けされている。次の照会が、一般的には文字列の比較によって、キャッシュされた応答に対応する照会文字列と一致する場合に限り、次の照会に対してその応答が戻される。照会応答キャッシュは、データを動的にキャッシュすることによって管理者制御に対する必要性を排除するが、データを別個の領域、すなわち照会応答ごとに１つの領域に非効率的に格納するというものである。多くの照会応答において同じ基本データを複製できるため、このことにより、大きなスペース・オーバーヘッドがもたらされる。これは、多くの場合、一般的に、基礎となるデータベースの重要な部分及び共通部分を含む照会応答が重複しているためである。さらに、キャッシュされた照会応答は、同じ照会のまさにその再実行要求に応じるためだけに用いられ、該応答に含めることができる他の照会には応じないので、この手法の性能利点が制限されたものになる。例えば、３０歳未満の全従業員の社会保障番号を見つけ出すために最初の照会が与えられる。ＳＱＬステートメントは、
ＳＥＬＥＣＴ  ｅｍｐｌｏｙｅｅ．ｓｓｎ  ＦＲＯＭ  ｅｍｐｌｏｙｅｅ  ＷＨＥＲＥ  ｅｍｐｌｏｙｅｅ．ａｇｅ＜３０
となる。
【０００５】
この照会に対する応答がキャッシュされ、キャッシュが、２５歳未満の全従業員の社会保障番号を見つけ出すために新しい照会を受け取ると仮定すると、そのＳＱＬステートンメントは、
ＳＥＬＥＣＴ  ｅｍｐｌｏｙｅｅ．ｓｓｎ  ＦＲＯＭ  ｅｍｐｌｏｙｅｅ  ＷＨＥＲＥ  ｅｍｐｌｏｙｅｅ．ａｇｅ＜２５
となる。
【０００６】
２５歳未満の全従業員は、３０歳未満でもあるので、新しい照会の応答は、第１の応答内に含まれるが、完全一致検索に基づいた照会応答キャッシュは、該キャッシュからの該照会を処理することができない。
【０００７】
手短に言えば、明示的な管理者定義のデータ・キャッシュは、手動の介入を必要とし、該管理者が、各エッジ・サーバ上の作業負荷及びリソースについての詳細な知識を有することを想定している。照会応答キャッシュは、管理者のオーバーヘッドを排除するが、有効性が限定され、スペース・オーバーヘッドが大きくなる。さらに、整合性の管理は、キャッシュされたデータの表示と起点サーバ内の基本データとの間の不一致のために複雑なものとなる。整合性の制御は、一般に、いずれかの基本テーブルが変わるときに全ての照会応答を無効にするか、又は複雑な依存グラフを維持するかのいずれかを必要とする。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
したがって、作業負荷の変更又はキャッシュが常駐するマシン上のリソース可用性の変更に従って、管理者がそのコンテンツを指定し、或いは仕様を適合させることが望ましい。キャッシュの格納オーバーヘッド及び整合性の維持が効率的であることがさらに望ましい。
【課題を解決するための手段】
【０００９】
従来技術のこれら及び他の欠点及び不利な点は、ローカル・アプリケーションによって実行される照会に基づいてデータを動的にキャッシュすることをサポートするための、コンピュータ・システム及び対応する方法によって対処される。
【００１０】
例示的なシステムは、完全なデータベースを有する遠隔サーバと、該完全なデータベースのサブセットを含み、該遠隔サーバと信号通信状態にあるエッジ・サーバ上のローカル・データベースと、該完全なデータベースからの結果をキャッシュし、ローカルで生成されたデータを受信し、該ローカル・データベースと遠隔データベースとの間のデータの整合性を保証しながら、使用可能な格納要件に基づいてキャッシュのコンテンツを調整するための、該エッジ・サーバ上の該ローカル・データベース内にある共有テーブルとを含む。
【００１１】
例示的な装置は、照会エバリュエータと、全てが該照会エバリュエータと信号通信状態にあるキャッシュ索引と、キャッシュ・リポジトリと、リソース・マネージャと、包含関係チェッカと、照会パーサと、整合性マネージャとを有するエッジ・データ・キャッシュを含む。
【００１２】
少なくとも１つの遠隔サーバに向けられたデータベース照会にローカル・サーバが応じるための、対応する例示的な対応方法が、該遠隔サーバの従前のデータベース照会の結果を動的にキャッシュし、ローカル・データベースを該ローカル・サーバと関連付け、複数のキャッシュ結果を該ローカル・データベース内の共有テーブルに格納し、該ローカル・サーバによって新しいデータベース照会に応じる際に該複数のキャッシュ結果を使用する段階を含む。
【００１３】
本開示のこれら及び他の態様、特徴及び利点は、添付の図面と併せて読まれるべきである例示的な実施形態の以下の説明から明らかになるであろう。
【００１４】
本開示の実施形態は、以下の例示的な図面によるネットワーク・エッジでのトランスペアレントなデータのキャッシュ処理を教示する。
【発明を実施するための最良の形態】
【００１５】
本開示の実施形態は、遠隔サーバに向けられたデータベース照会をローカル・マシンによって処理することを可能にする動的なデータベースのキャッシュ処理を提供するものである。キャッシュ処理は、ローカル・データベース・エンジンを利用して、部分的にではあるが意味的に整合性のある、従前の照会結果の「実体化ビュー」を維持する。アプリケーション照会のストリームに基づいて、データがキャッシュに動的に取り込まれる。照会述部上で作動する包含関係チェッカを用いて、新しい照会結果が、キャッシュされた結果の和集合内に含まれるかどうかを確定する。共通のローカル・テーブルを用いて、可能であれば重複する照会結果の間で物理的格納部を共有する。起点データベースから、挿入、削除、及び更新をローカル・データベース内のキャッシュ結果に伝えることによって、データ整合性が維持される。バックグラウンド・クリーニング・アルゴリズムが、整合性プロトコルによって伝えられる過剰な行並びにキャッシュから追い出すように印が付けられた照会に属する行を追い出すことによって、共通のローカル・テーブルのコンテンツを継続的又は周期的に整理する。この開示において、「照会応答」及び「照会結果」という用語は、互換性をもって用いられる。
【００１６】
以下の説明において、次の定義が、例示的な実施形態の原理及び／又は演算の理解の助けとなるであろう。
【００１７】
データベース・テーブルとは、リレーショナル・データベース・システムによって定義されるリレーショナル・テーブルである。
【００１８】
照会述部とは、照会結果において基本テーブル内のどの行を戻すかを選択するための基準として用いられる、照会において特定される制約（例えば、ＳＱＬステートメントのＷＨＥＲＥ節）である。
【００１９】
照会結果とは、ＳＱＬ照会によってデータベース・システムに戻される応答である。照会結果は、行と列を有するテーブルに似ている。
【００２０】
照会結果の組とは、多数の照会に対応する複数の結果の組である。
【００２１】
データ整合性とは、データベース・キャッシュ内のデータが、起点データベース内のデータに対して、所与の時間窓の範囲内で整合しているという要件である。正確には、現在時間Ｔｃにおけるキャッシュされたデータの状態が、過去の時間Ｔｐにおける起点データベース状態と整合していることを意味する。ここで、Ｔｐは、所与の最大時間窓の範囲内である。
【００２２】
照会／トランザクション・タイムスタンプとは、単調に増加し、起点サーバで実行する全ての照会及びトランザクションと関連付けられる、サーバによって生成された固有の数である。タイムスタンプは、並行操作に対してトランザクション又は照会の逐次化順序を反映する。
【００２３】
リフレッシュ・メッセージとは、起点データベース内のテーブルへの新しい変更（例えば、挿入、更新、削除ステートメント）を反映する、起点サーバによってエッジ・キャッシュに送られるメッセージである。多数のリフレッシュ・メッセージにおいて、基本テーブルへの変更をバッチ処理することができるが、該リフレッシュ・メッセージは、これらが報告する変更が生じた順序で伝えられる。
【００２４】
即時更新の可視性とは、アプリケーションによる更新がうまく完了した後に、同じアプリケーションによる次の照会が、データベースへの更新の結果を認識するという特性である。
【００２５】
単調状態遷移とは、第１の照会への応答を受信した後に、第２の照会が実行依頼されるという、アプリケーションによってキャッシュに実行依頼される２つの連続する照会が、時間と共に変化するデータベースの状態を認識する特性である。すなわち、第２の照会は、第１の照会によって認識された状態と同じか又はより新しいデータベースの状態を認識する。
【００２６】
図１に示されるように、「エッジ・データ・キャッシュ」を用いる例示的なネットワークの実施形態が、全体を参照符号１００で示される。ネットワーク１００は、より大きなアプリケーション・システムの一部とすることができる。ネットワーク１００は２つのエッジ・サーバ１０９及び１１０を含み、これらエッジ・サーバは、ウェブ要求を実行するクライアント・マシンに接続され、かつ、起点サーバ１０８にも接続されており、該起点サーバにおいて、主データベース及びウェブ・サイトがネットワーク接続１０７を介してホストされる。起点サーバ１０８は、データベース１０１と、アプリケーション・サーバ１０２と、ウェブ・サーバ１０３とを含む。エッジ・サーバ１０９、１１０の各々は、アプリケーション・サーバ１０５及びウェブ・サーバ１０６を含む。しかしながら、エッジ・サーバは、起点サイトに格納されたデータベース全体のレプリカを有するわけではない。代わりに、エッジ・サーバは、新規なエッジ・データ・キャッシュ１０４を使用する。動的コンテンツについての要求が、エッジ・サーバによって受信され、エッジ・アプリケーション・サーバ１０５の内部でホストされるアプリケーション・コンポーネントによって処理される。これらのコンポーネントは、データベース照会を発し、該データベース照会は、可能であれば、エッジ・データ・キャッシュ１０４によってインターセプトされ、ローカル・データベースにおいて処理される。ローカル・データベースによって照会を処理することができない場合には、エッジ・データ・キャッシュ１０４は、要求を起点データベース１０１に転送し、そこから結果を検索する。
【００２７】
図２を参照すると、エッジ・データ・キャッシュが、全体を参照符号２００で示される。エッジ・データ・キャッシュ２００は、主部分２０２と結合されたＪａｖａ（商標）サーブレット２０１を含む。主部分２０２は、照会パーサ２０５、包含関係チェッカ２０７、照会エバリュエータ２０４、キャッシュ索引２０６、ローカル・リポジトリ２０８、整合性マネージャ２１０及びリソース・マネージャ２０９と信号通信状態で結合されたＪＤＢＣインタフェース２０３を含む。キャッシュの機能は、以下のコンポーネントとして実装される。
【００２８】
照会パーサ２０５は、ＳＱＬ文字列を、「照会ステートメント」データ構造体、列のリストを特定する構文解析ツリー、ターゲット・テーブル、及び照会によってアクセスされる種々の節に変換する。特に、ＷＨＥＲＥ節は、ＡＮＤ−ＯＲ標準形態で格納されるブール述部に構文解析される。これが、包含関係チェッカにより、照会述部の対に等価演算及び包含関係演算を行うことを可能にする。
【００２９】
照会包含関係チェッカ２０７は、新しい照会の結果が前にキャッシュされた照会結果に含まれるかどうかを判断する。従前の照会、従前の照会の適切なサブセット、又は多数の従前の照会の和集合の適切なサブセットに対する完全一致として、包含関係をチェックすることができる。
【００３０】
キャッシュ索引２０６は、包含関係のチェックを提供する。照会述部が複雑であるか、又はキャッシュされた照会の組が長過ぎるとき、包含関係のチェックは、計算に費用がかかることになる。新しい照会が受信されると、キャッシュ索引２０６は、前にキャッシュされた照会の全てをチェックする代わりに、同じテーブル及び列上で作動する照会だけに焦点を合わせる。キャッシュ索引は、テーブル名及び列名に基づいて、キャッシュされた照会を多重レベルのハッシュ・テーブル内に構成する。
【００３１】
照会エバリュエータ２０４は、キャッシュのコア・モジュールであり、キャッシュ論理を含む。照会エバリュエータ２０４は、アクセスがヒットであるかミスであるか、ミスの際にバックエンドによって戻された結果をキャッシュ内に挿入すべきかどうかを判断する。照会エバリュエータ２０４はまた、データを前もって取得し、キャッシュ性能を改善するために、キャッシュ・ミスを起こした照会をバックエンドに送る前に、その照会を修正することもできる。
【００３２】
リソース・マネージャ２０９は、ヒット率及び応答時間についての統計値と、キャッシュ構成パラメータとを維持する。収集された統計値がそうした必要性を示す場合には、リソース・マネージャ２０９は、特定の作業負荷に適合させるように構成パラメータを変えることができる。
【００３３】
キャッシュ・リポジトリ２０８は、結果を格納する。キャッシュ・ミスの際の照会結果は、キャッシュ・エバリュエータによって判断されるローカル・データベース・テーブルに格納される。本開示の実施形態は、ハイブリッドの物理的格納ポリシーを用いる。幾つかの照会は、照会結果モデルごとに１つのテーブルを用い、他の照会は、データがバックエンドの基本テーブルの部分的に取り込まれたローカル・レプリカを通じて、物理的格納部を共有する。
【００３４】
整合性マネージャ２１０は、バックエンド・データベースから受信したリフレッシュ・メッセージに応答して、キャッシュされたデータに更新を適用する。
【００３５】
操作において、照会は、Ｊａｖａ（商標）サーブレット２０１のようなアプリケーション又はアプリケーション・コンポーネントから送出される。照会は、データベース・キャッシュ２０２によって受信される。具体的には、キャッシュ内のＪＤＢＣインタフェース・アダプタ２０３が、アプリケーションとの接続を担当する。インタフェース・アダプタは、Ｊａｖａ（商標）ＪＤＢＣ規格によって定義され、必要とされるクラスの組の実装である。次に、「照会ステートメント」が、照会エバリュエータ２０４に送られる。照会エバリュエータは、照会をローカル・サーバで実行（以下、ローカルで実行という）するか、遠隔サーバで実行（以下、リモートで実行という）するかの決定と、キャッシュ操作の制御とを担当するモジュールである。照会ステートメントを受信すると、照会エバリュエータは、照会パーサ２０５を呼び出すことによって、受信したステートメントを構文解析する。パーサは、ステートメントを４つのカテゴリの１つに分類する。ステートメントの処理は、その照会カテゴリによって決まる。
【００３６】
ここで図３を参照すると、照会ツリーが、全体を参照符号３００で示されている。照会ツリー３００は、異なる照会カテゴリを示す。キャッシュによって受信された照会３０１は、包含関係チェック可能照会３０２及び包含関係チェック不能照会３０３の２つのクラスに構成される。キャッシュされた包含関係チェック可能照会は、キャッシュされた照会の結果のサブセットをもたらす後の任意の照会に応じることができる。単一のテーブル上で作動し、又は多数のテーブルを結合させるが、ｇｒｏｕｐ−ｂｙ節も集約演算子も含まない照会が、包含関係チェック可能照会としてキャッシュされる。これらは、全体の結果すなわち単純照会３０４と、部分的結果すなわち上位Ｎ個の照会３０５の２つのカテゴリにさらに分けることができる。
【００３７】
包含関係チェック不能照会は、キャッシュすることができるが、ＳＱＬ文字列の完全一致検索を用いてマッチングが行なわれる。これらはさらに、集約照会３０６及び複合照会３０７の２つのカテゴリに分けられる。ＵＤＦ、サブ照会、又はｇｒｏｕｐ−ｂｙ節を使用する複合照会は、包含関係チェッカによっては処理されず、完全一致するものとしてキャッシュされる。選択リスト内のＭＩＮ、ＭＡＸ、及びＡＶＧなどの集約演算子を用いてデータを集約する照会も、完全一致するものとしてキャッシュされる。しかしながら、集約照会３０６は、その選択リスト内の集約演算子をドロップすることによって、包含関係チェック可能照会３０２に変換することができる。この最適化は、かなりの利点が予想される場合に、キャッシュによって行なわれる。
【００３８】
単純照会の処理は、次のように進行する。単純照会は、その結果が基本テーブルの行及び列のサブセットであるというものである。したがって、単純照会は、「ＧＲＯＵＰ  ＢＹ」節、サブ照会、又はユーザ定義機能のいずれをももたない。単純照会は、上位Ｎ個の照会ではなく、基本的な比較基本形を用いるＷＨＥＲＥ節に基づいて、単に、単一のテーブルの一部又は多数のテーブルの結合を選択するというものである。単純照会の例が下記に与えられる。
ＳＥＬＥＣＴ  ｅｍｐｌｏｙｅｅ．ｉｄ  ＦＲＯＭ  ｅｍｐｌｏｙｅｅ  ＷＨＥＲＥ  ｅｍｐｌｏｙｅｅ．ａｇｅ＜２５
【００３９】
図４に示されるように、高レベルの処理アルゴリズムが、全体を参照符号４００で示される。高レベルの処理アルゴリズム４００は、キャッシュ・ヒット又はキャッシュ・ミスの処理を提供するものである。照会を受信すると、キャッシュ索引を用いて、同じテーブル・リスト及び列のリスト上にある照会を検索する。次に、決定ブロック４１０において、包含関係チェッカを呼び出し、この照会が前にキャッシュされたこれらの照会内に含まれるかどうかを確定する。
【００４０】
キャッシュ・ヒットの場合には、機能ブロック４１２において、照会がローカル・キャッシュ上で実行され、結果が戻される。機能ブロック４１２はまた、キャッシュ・リポジトリ４１４にも照会を送信し、該キャッシュ・リポジトリ４１４から結果を受信する。キャッシュ・ミスの場合には、照会は、バックエンド・サーバに該照会を送信する前に、機能ブロック４１６及び４１８において修正される。次の最適化が行われる。第１に、ＷＨＥＲＥ文節、ｏｒｄｅｒ−ｂｙ節、及びｈａｖｉｎｇ節内に記載される列を含むように、選択リストが拡張される。この拡張の目的は、キャッシュにおいてヒットする将来の照会を実行できる可能性を最大化することである。第２に、一次キー列も選択リストに加えられる。重複する結果を有する多数の照会が同じ基本テーブルの同じ行を検索するとき、重複する行がキャッシュに挿入されるのを防止するために、一次キー列をキャッシュすることが必要とされる。バックエンドによって戻される結果は、ミスの際に常にキャッシュに挿入されるわけではない。決定ブロック４２０において高度な履歴ベースのアルゴリズムを用い、どの照会が機能ブロック４２２においてキャッシュするに値するのかを決定することができる。結果は、出力として与えられ、キャッシュ・リポジトリ４１４に送信される。
【００４１】
上位Ｎ個の照会の処理は、次のように進行する。上位Ｎ個の照会は、通常、ｏｒｄｅｒ−ｂｙ節に従ってソートされた結果の組の最初から、指定された数の行を取得する。照会包含関係及び評価アルゴリズムは、単純な全体結果の照会のものとは異なる。上位Ｎ個の照会は、Ｆｅｔｃｈ節を落とすことによって、単純照会に変換される。上述のように、包含関係は、これらの単純照会において実行される。最終ステップにおいて、Ｆｅｔｃｈ節が考慮される。基本照会（Ｆｅｔｃｈ節をもたない）はキャッシュ・ヒットであるが、Ｆｅｔｃｈ節は、該基本照会をキャッシュ・ミスにすることがあることに注目されたい。例えば、下記の２つの照会Ｑ１及びＱ２、すなわち
Ｑ１：ＳＥＬＥＣＴ  ｉｄ  ＦＲＯＭ  ｉｔｅｍ  ＷＨＥＲＥ  ｃｏｓｔ＜１５  ＯＲＤＥＲ  ＢＹ  ｃｏｓｔ  ＦＦＮＲＯ  ２０
Ｑ２：ＳＥＬＥＣＴ  ｉｄ  ＦＲＯＭ  ｉｔｅｍ  ＷＨＥＲＥ  ｃｏｓｔ＜５  ＯＲＤＥＲ  ＢＹ  ｃｏｓｔ  ＦＦＮＲＯ  ２０
を考える。
【００４２】
ＦＥＴＣＨ  ＦＩＲＳＴ  ２０  ＲＯＷＳ  ＯＮＬＹアルゴリズム（ＦＦＮＲＯ  ２０）節が、両方の照会に存在しない場合には、第２の照会の結果を、第１の照会の結果すなわちキャッシュ・ヒット内に含めることができる。しかしながら、その節が存在するときには、キャッシュ・ヒットは、単なる照会ステートメントの検査によって保証されるわけではない。したがって、上位Ｎ個の照会について包含関係チェックを処理する際の第２のステップは、キャッシュされたデータ上で局所的な実行を試みることである。十分な行が検索される場合には、照会はキャッシュ・ヒットと考えられ、他の場合には、キャッシュ・ミスと考えられる。結果の一部だけがローカル・キャッシュ内に見出されるので、このタイプのキャッシュ・ミスは、「部分的ヒット」と呼ばれる。
【００４３】
包含関係チェックがいずれのマッチング照会も見出さないか、又は結果の組が十分な行を有していない場合には、元の照会ＱＮが、修正された照会ＱＮ´に変換され、ここで、Ｆｅｔｃｈ節内のＮの値は、より大きなＮ´（Ｎ´＝Ｎ＊Ｅｘｐａｎｓｉｏｎ−Ｆａｃｔｏｒ）によって置き換えられる。例えば、実験におけるデフォルト係数値が２である場合には、要求される行数の２倍をフェッチする。要求されるアプリケーションより多くの行を検索することは、後の「部分的ヒット」照会、すなわち包含関係チェック・ステップを通過するが、要求されている行数を見出すことができない照会のイベントを減少させることを狙いとした発見的方法である。
【００４４】
集約照会の処理は、次のように進行する。集約照会は、その選択リスト内に集約演算子（例えば、ＭＡＸ、ＭＩＮ、ＡＶＧ、ＳＵＭ）を有し、他の場合には包含関係チェックが可能になる。次の照会Ｑ３：
Ｑ３：ＳＥＬＥＣＴ  ＭＡＸ（ｃｏｓｔ）  ＦＲＯＭ  ｉｔｅｍ  ＷＨＥＲＥ  ｉｄ＝１０
を考える。
【００４５】
ヒットのためのマッチングが、２つのステップで進行する。まず、ＳＱＬ文字列に基づいてＱ３の完全一致についてのチェックが行われ、結果の組の全体がアプリケーションに戻される。次に、何らの完全一致が見出されなかった場合には、集約演算子を取り除くことによって、元の照会Ｑ３が、照会Ｑ４に修正される。
Ｑ４：ＳＥＬＥＣＴ  ｃｏｓｔ  ＦＲＯＭ  ｉｔｅｍ  ＷＨＥＲＥ  ｉｄ＝１０
【００４６】
修正された照会Ｑ４について包含関係の一致が見出された場合には、元の照会Ｑ３が、ローカル・キャッシュ上で実行され、コスト（ｃｏｓｔ）をローカルで集約し、結果をアプリケーションに戻す。ミスの際には、修正された照会Ｑ４が、バックエンドで実行される。結果の組のサイズが閾値内である場合には、結果は、対応するローカル・テーブルに格納され、元の照会がローカルで実行される。このことは、異なる集約演算子を有する将来の照会をキャッシュにおいて処理することを可能にする。結果の組のサイズが大きすぎることが判明した場合には、元の照会Ｑ３がバックエンドに送信され、その結果は、新しい完全一致テーブルに格納される。このことは、全く同じ集約条件を有する何らかの将来の照会をキャッシュから処理することを可能にする。この発見的方法は、キャッシュのサイズを必要以上に増大させることなく、キャッシュ・ヒットを増大させること目的としたものである。
【００４７】
複合照会は、複合節（例えば、ユーザ定義機能又はＷＨＥＲＥ節におけるサブ照会）、或いはｇｒｏｕｐ−ｂｙ節のいずれかのために、包含関係チェックが可能ではない。ｇｒｏｕｐ−ｂｙ節は、全く同じｇｒｏｕｐ−ｂｙ節及びＷＨＥＲＥ節を有する照会によってのみ用いることができる集約データを生成する。このように、包含関係チェックを行うことは、不適切である。代わりに、こうした照会の結果は、照会のＳＱＬ文字列によって索引が付けられた別個の結果テーブルに格納される。こうした照会についての包含関係チェックは、ＳＱＬ文字列の完全一致に基づいている。このルックアップ・プロセスは、キーとしてＳＱＬ文字列を有するハッシュ・テーブルに基づいているので、非常に高速である。正確なＳＱＬ文字列がキャッシュに実行依頼される場合には、対応する結果テーブルにおいて、ローカル照会が実行され、テーブル全体を検索する（すなわち、「ＳＥＬＥＣＴ＊ＦＲＯＭ  ＬＯＣＴＡＢ」がローカルで実行される）。こうした照会は、費用がかからず、エッジ・サーバ上での処理時間が最小であることに注目されたい。
【００４８】
図５を参照すると、ローカル・リポジトリが、全体を参照符号５００で示される。ローカル・リポジトリ５００は、照会結果がどのようにローカル・キャッシュ・リポジトリ５０１に格納されるかを示す。リポジトリ５０１は、２つの区画、すなわち、一方は複合又は完全一致照会の格納のための区画５０２と、もう一方は包含関係チェック可能照会の格納のための区画５０３とに分けられる。完全一致照会は、別個のテーブルに格納され、その仕様がキャッシュされた照会のＳＱＬ文字列に一致する新しい照会に応答するためだけに用いられる。例えば、照会Ｑ５  ５０４及びＱ６  ５０５は、これらの結果が重複するかどうかに関係なく、別個のテーブルに格納される。
【００４９】
包含関係チェック可能照会は、共有テーブルに格納される。同じ基本テーブル上の照会は、同じテーブルのローカル・コピーに格納される。例えば、図は、２つの照会Ｑ７及びＱ８が同じテーブルから「ＳＥＬＥＣＴ（選択）」されると仮定する。まず、照会Ｑ７  ５０６によって検索されたタプルが、キャッシュに挿入される。次に、第２の照会Ｑ８によってフェッチされた行が、同じテーブルに挿入される５０７。Ｑ８の結果が挿入されると、既存の行が、新たにフェッチされた値で更新される。そのため、２つの異なる照会によってフェッチされた同じ行は、キャッシュ内で複写されない。全ての照会は、それらをバックエンド・サーバに送信する前に、一次キーを取得するように修正されるので、同一の行が発見される。
【００５０】
ここで、図６を参照すると、キャッシュ・テーブル構造が、全体を参照符号６００で示される。キャッシュ・テーブル構造６００は、ここでは「従業員」と呼ばれる、同じデータ・テーブル上の２つの照会の特定の例を示し、それらの結果データ構造６０１、６０２が、どのようにエッジ・データベース・キャッシュ内の同じローカル・テーブル６０３に格納されるかを示す。
【００５１】
図７には、整合性プロトコルが、全体を参照符号７００で示されている。整合性プロトコル７００は、バックエンド・サーバ部分７０２と信号通信状態にあるエッジ・サーバ部分７０１を含む。エッジ・サーバ部分７０１は、照会結果を挿入し、照会を実行するための、キャッシュ・リポジトリ７０４と信号通信状態にあるＤＢＰｒｏｘｙユニットを含む。変更ＡＰＰＬＹユニット７０５が、テーブルをリフレッシュするために、キャッシュ・リポジトリ７０４と信号通信状態にある。
【００５２】
バックエンド・サーバ部分７０２は、照会を受信し、結果を提供するためのＤＢＰｒｏｘｙユニット７０３と信号通信状態にあるＤＢＭＳユニット７０６を含む。ＤＢＭＳユニット７０６はさらに、別のキャッシュ・リポジトリ７０７と信号通信状態にあり、キャッシュ・リポジトリ７０７への書き込み、及びキャッシュ・リポジトリ７０７からの読み取りを行う。キャッシュ・リポジトリ７０７は、最後に書き込まれたデータを読み取るための、変更ＣＡＰＴＵＲＥユニット７０８と信号通信状態にある。次に、変更ＣＡＰＴＵＲＥユニット７０８は、メッセージをリフレッシュするための変更ＡＰＰＬＹ装置７０５と信号通信した状態で接続される。
【００５３】
このように、起点サーバによって伝えられる更新のストリームを利用することによって、データ整合性が確保される。従来の実体化ビュー手法は、基本データ内の変更に対するビュー定義（「データ」）を再実行することによって、キャッシュされたビューを更新するというものである。しかしながら、キャッシュする照会（「ビュー」）の数が潜在的に多数であるため、エッジ・データ・キャッシュは、より効率的な機構を必要とする。キャッシュされたデータは、データが部分的に取り込まれたバックエンド・テーブルのコピーとして維持されるため、起点において基本テーブルにコミットされた変更は、照会を再実行する必要なく、単に、「現状のままで」キャッシュされたバージョンに伝えることができる。基本テーブルへの更新、削除、及び挿入（「ＵＤＩ」）は、データが部分的に取り込まれたエッジ上のものに伝えられ、適用される。キャッシュ上で実行することになる将来の照会が、これらの新しく伝えられた変更から、何らかのマッチング・タプルを検索する。この解法は、一般的に大部分のウェブ環境の遅い速度で変化するデータを想定したものであり、キャッシュされたビューをどのように更新すべきかを判断する処理オーバーヘッドを低減させるために、潜在的に不必要なデータの伝搬をあきらめる。しかしながら、テーブルに大量の更新作業負荷がかかっている場合には、キャッシュ・リソース・マネージャが、指定期間の間だけ、ローカル・コピーを使用不可にすることができる。
【００５４】
エッジ・アプリケーションによって発せられる読み取り専用照会は、可能ならいつでもキャッシュから応じられる。更新トランザクションは、常に、最初に該更新トランザクションをローカル・キャッシュに適用することなく、実行のためにバックエンド・データベースに経路指定される。エッジ・データ・キャッシュは、大規模展開向けに設計されているので、整合性プロトコルは、可能な限り起点から疎結合されたものにしなければならない。その結果、キャッシュの整合性を確保する負担が、できる限り、リソースがより自然に拡大縮小するエッジ・キャッシュにかかるようにしなければならない。バックエンド・サーバは、周期的な更新の伝搬、別個のプロセス又はマシンに対して負担を軽減できるタスクを担当するだけにすべきである。強力な整合性保証を与えることは、キャッシュの有効性を制限し、高いコストを招くが、即時更新可視性及びデータ整合性のような幾つかの重要な整合性保証を確保できるかが、まもなく説明される。本開示は、起点において全てのＵＤＩをテーブルに捕捉し、それらを「リフレッシュ・メッセージ」内にパッケージされた状態で、エッジ・キャッシュに転送するデータ・プロパゲータに依存している。データの変更は、トランザクション識別子によってタグ付けされたエッジに伝えられ、トランザクション・コミット順にエッジ・キャッシュに適用される。起点サイトでコミットされるトランザクションの効果を反映させる、入ってくるＵＤＩのストリームが、ローカルでキャッシュされたテーブルに適用される。
【００５５】
ＵＤＩが伝えられ、タイムスタンプ順にキャッシュに適用されるので、このセクションに用いられる全てのタイムスタンプは、バックエンド・サーバ側のコミット・タイムスタンプを指し、キャッシュ内のタプル値は、起点からの最後の伝搬メッセージのタイムスタンプに対応するデータベースの状態を反映していなければならない。より正確には、伝搬メッセージのタイムスタンプは、そのメッセージ内に含まれるあらゆる更新トランザクションのうちの最大タイムスタンプである。データ整合性を確保する際の問題は、伝播メッセージ及びミスの際の照会結果の挿入によって、ローカル・テーブルを更新できることから生じる。
【００５６】
保証された整合性特性。キャッシュは、エッジ・アプリケーションについての幾つかの重要な整合性特性、すなわちデータ整合性、単調遷移、及び即時更新可視性を保証する。キャッシュは、アプリケーションにとっては、本物のバックエンド・データベースのように見える。しかしながら、キャッシュのコンテンツは、通常、バックエンド・データベースに格納されるものと同程度に最新のものではない。したがって、キャッシュは、現在の状態と異なる可能性がある状態をアプリケーションに反映するので、データベースの所与の状態を「エクスポート」するものである。データ整合性特性は、その時点におけるキャッシュによってエクスポートされたデータベースの状態が、常に、従前の時点におけるデータベースの過去の状態に対応することを要求する。エクスポートされた状態と実際の状態との間のずれも制限される。単調状態遷移特性は、キャッシュによってエクスポートされたデータベースの状態が、時間と共に変化することだけを示す。即時更新可視性の特性は、アプリケーションが更新をコミットし、後に照会を発する場合に、該照会が該更新（及び従前の更新の全て）の結果を認識することを要求する。
【００５７】
データ整合性及び単調遷移を保証すること。最初に、キャッシュが１分前のデータベース状態と一致すると仮定する。キャッシュ・ミスのため、起点で実行された新しい照会の結果（以下、ミスの結果という）がキャッシュに挿入された場合には、該キャッシュは、古いデータと新しいデータの混合物を含むことになる。データ整合性は、キャッシュされたデータが、常にデータベースの単一の過去のバージョンと一致することを要求する。照会が起点において原子的に実行されると仮定する。照会が失敗し、リモートで実行される場合には、サーバは、該照会が実行されたときに、その最後のコミット・タイムスタンプｔｑを結果と共に戻す。
【００５８】
図８を参照すると、照会処理アルゴリズムが、全体を参照符号８００で示される。照会処理アルゴリズム８００は、整合性を考慮し、照会の包含関係チェックに基づいてキャッシュ・ヒットを登録するための機能ブロック８０１を含む。機能ブロック８０１は、ヒットが生じたかどうかを判断するために、決定ブロック８０２に制御を渡す。ヒットが生じた場合には、機能ブロック８０３に制御を渡し、共有キャッシュのロック、照会のローカル実行、及び共有キャッシュのロック解除を行う。しかしながら、ブロック８０２においてヒットが生じなかった場合には、機能ブロック８０４に制御を渡し、照会をリモートで実行し、決定ブロック８０５に制御を渡す。ブロック８０５は、リモートで実行された照会がうまくいかなかったのかどうかを判断する。うまくいった場合には、戻しブロック８０６に制御が渡り、キャッシュされた結果「ｒｃ」を戻す。うまくいかなかった場合には、決定ブロック８０７に制御が渡り、結果が部分的なものでしかないのかどうかを判断する。部分的なものでしかない場合には、機能ブロック８０８に制御が渡り、キャッシュを排他的にロックし、結果を結果の組に挿入し、サーバからの付加的な情報を伝え、該キャッシュをロック解除する。機能ブロック８０８は、戻しブロック８０９に制御を渡し、結果の組「ｒｓ」を戻す。ブロック８０７の結果がノーである場合には、制御は、戻しブロック８０９に直接渡る。
【００５９】
作動において、結果の挿入は、ブロック８０７において、照会のタイムスタンプｑｕｅｒｙ＿ｔｓを、起点サーバから受信した最後の伝搬メッセージのタイムスタンプｃａｃｈｅ＿ｔｓと比較することによって開始される。照会及びキャッシュのタイムスタンプは、図では、それぞれｑｕｅｒｙ＿ｔｓ（「ｔｑ」）及びｃａｃｈｅ＿ｔｓ（「ｔｃ」）という長い名前によって、また、他の場所では、長い名前又は短い名前で呼ばれることに注意されたい。ｑｕｅｒｙ＿ｔｓがｃａｃｈｅ＿ｔｓより大きい場合には、照会は、キャッシュのものより新しい状態を見ている。この通常の場合においては、ブロック８０８において、まずミスの結果がキャッシュに挿入され、あらゆる待機中の伝搬メッセージが起点サーバから引き出され、キャッシュ全体を後の時間に合わせる。最後に、照会が索引に加えられる。しかしながら、ｃａｃｈｅ＿ｔｓがｑｕｅｒｙ＿ｔｓより大きい場合には、ミスの結果を即座に挿入することで、キャッシュされたデータを過去の値に戻すことができ、伝搬メッセージによって適用される変更を逆にし、単調性要件に失敗する。これは、まれな競合状態であるため、こうした場合には、結果の挿入を省略することができる。これは、通常、後のミスの１つが、結果の挿入に成功するまで、照会をキャッシュするのを遅らせるだけであり、キャッシュの有効性を著しく損なうものではない。ブロック８０８におけるｐｒｏｐａｇａｔｅ＿ｆｒｏｍ＿ｓｅｒｖｅｒ（）の副次的作用として、ｃａｃｈｅ＿ｔｓを増加させることができることに注目されたい。
【００６０】
ここで、図９を参照すると、結果をキャッシュに挿入するためのアルゴリズムが、全体を参照符号９００で示される。ループ・ブロック９０１が、照会結果内の各タプルについてループを実行する。ブロック９０１のためのループは、タプルがキャッシュ内にあるかどうかを判断するための決定ブロック９０２を含む。タプルがキャッシュ内にある場合には、機能ブロック９０３に制御が渡り、該タプルを更新する。タプルがキャッシュ内にない場合には、機能ブロック９０４に制御が渡り、該タプルを挿入する。このように、操作において、キャッシュへの結果の組の挿入は、次のように進行する。すなわち、結果の組をキャッシュに挿入したとき、ブロック９０３において、既存の行が新しい値で上書きされ、一方、ブロック９０４において、既存のものでない行がテーブルに挿入される。
【００６１】
図１０には、更新トランザクションを実行するためのアルゴリズムが、全体を参照符号１０００で示される。機能ブロック１００１が、結果「ｒｃ」についてのリモート照会を実行し、決定ブロック１００２に制御を渡す。照会がうまくいった場合には、ブロック１００２は、戻しブロック１００３に制御を渡し、結果「ｒｃ」を戻す。照会がうまくいかなかった場合には、ブロック１００２は、機能ブロック１００４に制御を渡し、サーバからデータを伝える。ブロック１００４は、戻しブロック１００５に制御を渡し、結果「ｒｃ」を戻す。
【００６２】
このように、即時更新可視性が保証される。エッジ・アプリケーションによってキャッシュに実行依頼された更新トランザクションは、起点データベースに経路指定される１００１。さらに、更新トランザクションが完了した後に、アプリケーションに戻す前に該更新トランザクションを起点から引き出す１００４ことによって、更新の効果を迅速にフェッチすることができる。
【００６３】
キャッシュのスペース・オーバーヘッドが、キャッシュ置換えによって調整される。スペース・オーバーヘッドを制限し、通常制限されるエッジ・リソースの使用を最適化するために、エッジ・データ・キャッシュは、データ整合性を保持しながら、キャッシュから未使用のデータを安全に追い出すバックグラウンドのガーベッジ・コレクション・プロセスに依存する。具体的には、キャッシュ置換えの目的は、制限された使用可能なスペース量に対するキャッシュの利点を最大化することである。ファイル及びメモリ・ページの従来の置換えとは対照的に、基礎となる行を多数の照会にわたって共有することができる。
【００６４】
キャッシュ置換えは、ローカル・データベースのスペース使用が高水位線（「ＨＷＭ」）値に達するときにトリガされる。次に、スペースが十分に空けられ、低水位線（「ＬＷＭ」）値より下に達するまで、置換えが始まる。置換えは、より多くの行をローカル・テーブルに挿入するためのスペース、又は新しいテーブルを作成するためのスペースがないときに、照会ミスについての要求に応じてトリガされるわけでない。置換えは、バックグラウンド・プロセスであり、照会処理及び更新操作と同時進行することが予想できる。
【００６５】
図１１を参照すると、キャッシュ・クリーニング・アルゴリズムが、全体を参照符号１１００で示される。アルゴリズム１１００は、テーブルを拡張して新しい列「ａｃｃｅｓｓｅｄＦｌａｇ」を付加するための機能ブロック１１０１を含む。ブロック１１０１は、機能ブロック１１０２に制御を渡し、ローカル・テーブル内の全ての列について「ａｃｃｅｓｓｅｄＦｌａｇ」を偽に再設定する。ブロック１１０２は、機能ブロック１１０３に制御を渡し、キャッシュ内に留まる照会の組「Ｓ」を判断する。次に、機能ブロック１１０３は、機能ブロック１１０４に制御を渡し、組「Ｓ」内の全ての照会を再実行し、いずれかの選択された行の「ａｃｃｅｓｓｅｄＦｌａｇ」を真に設定する。次に、ブロック１１０４は、機能ブロック１１０５に制御を渡し、「ａｃｃｅｓｓｅｄＦｌａｇ」が偽である全ての行を削除する。
【００６６】
キャッシュ・クリーニングのためのアルゴリズム１１００は、グループ置換えと呼ばれる。このアルゴリズムは、実装が簡単であり、ヒット、ミス、又は更新の伝搬時にオーバーヘッドを付加するものではない。ブロック１１０３において、置換えポリシーに基づいて、１組の「犠牲」照会に印が付けられ、キャッシュから削除される。「犠牲」照会だけに属する重複しない行に適正に印が付けられることを保証するために、次のステップが実行される。最初に、ブロック１１０２において、ローカル・テーブルの生成時に定義された制御列として実装されるａｃｃｅｓｓｅｄ  ｆｌａｇが、キャッシュされた全ての行と関連付けられ、偽に設定される。次に、ブロック１１０４において、非犠牲照会がバックグラウンドにおいて実行される。このバックグラウンド実行は、フォアグラウンド照会の性能に影響を及ぼさないように、長期間にわたって行われる。照会が実行されるときはいつも、制御列内の対応するエントリが、あらゆる選択された行について真に設定される。ブロック１１０５において、この命令実行段階の終わりに、制御列（ａｃｃｅｓｓｅｄ  ｆｌａｇ）が依然として偽の状態である任意の行を安全に削除することができる。ガーベッジ・コレクション・サイクルが実行を開始した後に、キャッシュ・ミス又は整合性マネージャによって挿入又は更新される行の削除を防止するために、更新されるか又はローカル・テーブルに挿入される任意の行について制御列が設定される。
【００６７】
本開示の実施形態は、ある意味では、具体的には管理しやすさ及び作業負荷又はリソースの可用性の変更に適合する能力である照会応答キャッシュの利点と、具体的には非冗長データ格納のスペース効率及び効率的な更新ベースの整合性プロトコルをサポートする能力である基本テーブル・レプリケーションの利点との両方の世界の最良のものを達成する。
【００６８】
従って、本開示の実施形態の１つの態様は、ローカル・マシンを使用し、従前の照会の結果を動的にキャッシュする際にキャッシュ・ポリシーを用いることによって、少なくとも１つの遠隔サーバ用のデータベース照会に応じることである。本開示の実施形態の別の態様は、ローカル・データベースをローカル・マシンと関連付け、該ローカル・データベースを使用して複数の照会結果を共有テーブルに格納することである。本開示の実施形態のさらに別の態様は、照会述部で作動する包含関係チェッカを用いることによって、新しい照会に応じる際に、ローカル・データベースに格納された照会結果を使用することである。包含関係チェッカは、照会述部によって定められる新しい照会が必要とするデータが、論理的に、従前の照会の述部の和集合によって記載されるキャッシュされた複数の結果内のデータの組に含まれることを保証する。
【００６９】
本開示の実施形態の別の態様は、エッジ・キャッシュに格納されたデータが、可能ならいつでも、起点データベースにおいて定義されたテーブルの「部分的レプリカ」内に構成されることである。起点サーバから受信した照会結果は、ローカル・データベースに挿入される。同じ基本テーブルに対して行われる照会の結果は、該基本テーブルのキャッシュされた同じバージョンに挿入される。本開示の実施形態のさらに別の態様は、結果が基本テーブルの行及び列の単純なサブセットでない場合に、サブ照会、集約、又はユーザ定義機能を含む照会のような複合照会の結果を、結果ごとに１つずつ、多数のテーブルとしてローカル・データベースに格納することである。
【００７０】
本開示の実施形態のさらに別の態様は、トランスペアレントであり、アプリケーションへの変更を必要としないことである。また、キャッシュ論理が、データベースの外に存在するので、バックエンド又はローカル・データベースのいずれとも両立性があり、データベース・サーバへの変更を必要としない。本開示の実施形態の別の態様は、起点において基本テーブルに生じる変更をエッジ・キャッシュに伝えることによって、また、入ってくる照会を処理する際に整合性認識アルゴリズムを用いることによって、ローカル・データベースにキャッシュされたデータの整合性が維持されることである。本開示の実施形態のさらに別の態様は、キャッシュが、整合性又は正確性を損なうことなく、ローカル・データベースから有用性が少ない照会結果を追い出すことによって、ローカル・データベースで使用されるスペース量を調整できることである。
【００７１】
本開示のこれら及び他の特徴及び利点は、当業者であれば、本明細書内の教示に基づいて容易に確認することができる。本開示の教示は、ハードウェア、ソフトウェア、ファームウェア、専用プロセッサ、又はこれらの組み合わせの種々の形態で実装できることを理解すべきである。
【００７２】
本開示の教示は、例えば、ハードウェア及びソフトウェアの組み合わせとして実装することができる。さらに、ソフトウェアは、プログラム格納ユニット上で明白に具体化されたファームウェアとして実装されることが好ましい。ソフトウェアは、何らかの適切なアーキテクチャを含むマシンによってアップロードし、実行することができる。マシンは、１つ又はそれ以上の中央処理装置（ＣＰＵ）、ランダム・アクセス・メモリ（「ＲＡＭ」）、及び入力／出力（「Ｉ／Ｏ」）インタフェースのような、ハードウェアを有するコンピュータ・プラトフォーム上に実装されることが好ましい。コンピュータ・プラトフォームはまた、オペレーティング・システム及びマイクロ命令コードを含むこともできる。ここに記載された種々のプロセス及び機能は、ハードウェアによって実行することができるマイクロ命令コードの一部、又はソフトウェアの一部、或いはそれらの任意の組み合わせのいずれかとすることができる。さらに、他の種々の周辺装置を、付加的なデータ格納ユニットのようなコンピュータ・プラットフォームに接続することもできる。
【００７３】
さらに、添付の図面に示された構成システム・コポーネント及び方法の幾つかは、ソフトウェアとして実装されることが好ましいので、該システム・コンポーネント又はプロセス機能ブロック間の実際の接続は、本開示がプログラムされる方法によって異なり得ることを理解すべきである。本明細書の教示を考慮すれば、当業者には、これら及び本開示と同様の実装又は構成を考えることができるであろう。
【００７４】
例証となる実施形態は、ここでは添付の図面と関連して説明されるが、本開示が、それらの精密な実施形態に限定されないこと、及び、当業者であれば、本開示の範囲又は精神から逸脱することなく、種々の変更及び修正をもたらし得ることを理解すべきである。そのような変更及び修正の全ては、添付の特許請求の範囲に述べられる本開示の範囲内に含まれることが意図されている。
【図面の簡単な説明】
【００７５】
【図１】起点サーバに接続された２つのエッジ・サーバの概略図を示す。
【図２】図１のエッジ・サーバのデータ・キャッシュのブロック図を示す。
【図３】図２のエッジ・サーバのデータベース・キャッシュにおける異なるクラスの照会の樹形図を示す。
【図４】図１のエッジ・サーバについての照会処理全体の流れ図を示す。
【図５】図２のデータ・キャッシュによって用いられる共通スキーマの共有格納技術の概略図を示す。
【図６】図１の起点サーバ内の同じテーブル上の２つの照会に関するデータ・テーブルの例を示す。
【図７】整合性保守プロトコルの概略図を示す。
【図８】整合性が考慮された照会処理アルゴリズムの流れ図を示す。
【図９】結果をキャッシュに挿入するためのアルゴリズムの流れ図を示す。
【図１０】更新トランザクションを実行するアルゴリズムの流れ図を示す。
【図１１】キャッシュが占めるスペースを調整するために用いられるバックグラウンド・キャッシュ・クリーニング・アルゴリズムの流れ図を示す。
【図１】
0004416663.tif 000002
【図２】
0004416663.tif 000003
【図３】
0004416663.tif 000004
【図４】
0004416663.tif 000005
【図５】
0004416663.tif 000006
【図６】
0004416663.tif 000007
【図７】
0004416663.tif 000008
【図８】
0004416663.tif 000009
【図９】
0004416663.tif 000010
【図１０】
0004416663.tif 000011
【図１１】
0004416663.tif 000012