【誤訳訂正書】
【提出日】平成20年10月27日(2008.10.27)
【誤訳訂正１】
【訂正対象書類名】明細書
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【書類名】明細書
【発明の名称】データベースシステムにおけるバーチャルメモリマッピングとトランザクションマネージメントのポインターリロケーション最適化方法及び装置
【特許請求の範囲】
【請求項１】  データベースシステムのキャッシュ内のデータを区画する方法であって、前記キャッシュ内のポインターが、パーシステントなアドレスポインタからトランスレートされたバーチャルアドレスポインターであり、
ａ）リロケーション最適化行列を提供するステップであって、該行列は該行列内の位置を指定する複数のフィンガーと、前記キャッシュ内のキャッシュデータと対応する複数のエントリーとを有するステップと、
ｂ）前記行列を前記フィンガーを有する複数のセクションに区画するステップであって、第一セクションはクライアントのアプリケーションによる現在のトランザクションにて使用されているデータのためのエントリーを含むためのものであり、第二セクションは、ポインターを更新することなく前記クライアントのアプリケーションによって使用可能なエントリーを含むためのものであり、第三セクションは、ポインターを更新することなく前記クライアントのアプリケーションによって使用することができないエントリーを含むためのものであるステップと、
ｃ）前記キャッシュ内のデータ及び未だ前記キャッシュ内には存在しないデータに対するアクセスのために、前記クライアントのアプリケーションからのリクエストを斡旋するステップと、
ｄ）未だ前記キャッシュ内には存在しないデータを前記キャッシュ内へ組み入れ、前記行列内に組み入れられた前記データを反映するようにするステップと、ポインター情報を更新するために前記行列内のポインターをトランスレートするステップと、
ｅ）前記クライアントのアプリケーションから要求されることがなくなったデータを前記キャッシュ内から取り除き、前記行列内の該取り除かれたデータを反映するようにポインター情報を更新するために、ポインターをトランスレートするステップと、
ｆ）前記行列内の第三セクション内の前記エントリーと対応するデータへのアクセスを提供する際にポインターを更新し、それによって前記行列の前記第一及び第二セクションに対応する前記キャッシュ内のデータへの迅速なアクセスを提供するステップと、
を含んでいることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する分野】
本願発明はコンピュータシステムに関し、特にはパーシステントデータ（persistent data）を有した複数のキャッシュ(cache)を有したバーチャルメモリマッピングを使用したデータベースシステムのポインターマネージメントに関する。
【０００２】
関連出願の解説
本願は１９９９年３月２５日出願の米国仮特許願第６０/１２６１０３号の優先権を主張する。
【０００３】
【従来の技術】
オブジェクト（object-oriented）型データベースシステム並びに多数の相互関連オブジェクトを有した他のシステムにおいては、ポインター(pointer)とも呼称されるインターオブジェクトリファレンス(inter-object reference)は保存されたオブジェクトにアクセスを提供する複雑な構造を提供する。オブジェクト型データベースにアクセスする際にアプリケーションプログラムは、データベースの関連行列とデータベースを通過するダイレクトトラバーサルを使用してオブジェクト間の複雑な接続を利用してオブジェクトにアクセスして更新し、各オブジェクトがアクセスされるときに計算を実行することに時間を費やす。
【０００４】
オブジェクト型データベースの典型的な適用領域はコンピュータ利用デザイン、製造、エンジニアリング、ソフトウェア開発、電子パブリケーション、マルチメディアオフィースオートメーション、及び地理的インフォメーションシステムである。これらアプリケーション環境はオブジェクト型データベースシステムが迅速であることを要求する。
【０００５】
典型的なオブジェクト型データベースシステムはサーバーを介してオブジェクト型データベースに接続された多数のワークステーションや他のタイプのクライエントコンピュータを有している。各クライエントコンピュータは自身のキャッシュメモリを有しており、クライエントアプリケーションプログラムが要求するデータが配置される。
【０００６】
全てのオブジェクト型データベースシステムはオブジェクトを識別する方法を有している。現在、システムによっては“オブジェクトアイデンティファイヤー”（ＯＩＤ）を使用する。これはレフェレンスをオブジェクトに具現化する。システムによってはポインターを使用する。“デレフェレンス処理”と呼ばれるオペレーションはポインターをオブジェクトにまで従い、オブジェクトをリクエストするアプリケーションに利用可能にすることでオブジェクトを発見する。
【０００７】
データベースのデータへのアクセスはクライエントシステムのキャッシュメモリにデータをコピーすることが関与する。現行システムによってはキャッシュデータはトランザクションの完了後にしばしば放棄される。なぜなら、キャッシュデータをレフェレンスするポインターは時代遅れだからである。キャッシュデータの放棄はデータの整合性を確実にするが、クライエントとサーバーコンピュータとの間のコミュニケーションを増加させる。またキャッシュの使用を促すローカリティ(locality)の原理を利用させない。しかし、キャッシュのパーシステントなデータは、データとデータをレフェレンスするポインターとをデータベースと整合状態に保つ方法を必要とする。
【０００８】
パーシステントなデータのキャッシュ処理を、デレフェレンスオペレーションが高速で行えるような形態にするために、データレフェレンスポインターを更新する方法を有することが望ましい。
【０００９】
本願発明の１目的は、オブジェクト型データベースシステムにおいてデータをパーシステントにキャッシュ処理する方法と装置の提供である。
【００１０】
本願発明の別目的はキャッシュ処理されたデータのための最良ポインターリロケーションを有する方法と装置の提供である。
【００１１】
本願発明の別目的はオブジェクト型データベースシステムのためのバーチャルメモリマッピングアーキテクチャにおける最良ポインターリロケーションのための方法と装置の提供である。
【００１２】
【発明が解決しようとする課題】
パーシステントキャッシュ処理データのためのポインターリロケーション最良化の問題は、データベースシステムにおけるバーチャルメモリマッピングとトランザクションマネージメントのポインターリロケーション最良化のための本願発明の方法と装置により解消される。
【００１３】
【課題を解決するための手段】
データを保存する少なくとも１つの永久保存手段と少なくとも１つのデータベースと、物理的アドレスでアドレスされたローカルにデータを保存する少なくとも１つのキャッシュメモリと、キャッシュメモリ内のデータをアクセスするためにバーチャルアドレスを利用してデータをリクエストする手段と、バーチャルアドレスを物理的アドレスにマッピングする手段と、トランザクションの終了後にキャッシュデータを維持する手段とを含んだ処理ユニットとを有したオブジェクト型データベースシステムのためのバーチャルメモリマッピングとトランザクションマネージメントのための装置と方法とが提供される。典型的には、このシステムは複数のクライエントコンピュータを有している。それぞれはネットワークで接続されたキャッシュメモリを有しており、各永久保存手段はサーバーコンピュータを有している。１つのコンピュータがクライエントコンピュータとサーバーコンピュータとして作用することができる。クライエントアプリケーションに効率的なデレフェレンスオペレーションを提供するためにこの装置はポインターをキャッシュデータにリロケートすることで作動する。装置はさらにリロケーションされたポインターをキャッシュに維持されたデータに対して連続的トランザクションに維持することで作動する。ポインターリロケーション維持オペレーションの頻度を最低にまで減少させることで装置はその最良利益を達成する。
【００１４】
リロケーションオペレーションは３つのカテゴリーに分割できる。すなわち、インバウンドリロケーションと、フォーワードリロケーションと、アウトバウンドリロケーションとである。インバウンドリロケーションには外部フォーマットからクライエントアプリケーションで使用できるフォーマットとステートへのページのポインターの翻訳が関与する。インバウンドリロケーションはクライエントキャッシュに入るデータベースのリロケーションの発生ごとに発生する。フォーワードリロケーションはインバウンドリロケーションまたは前のフォーワードリロケーションによって創出されたステートからのページのポインターの翻訳が関与する。これはクライエントアプリケーションによって、現行的に利用できるステートには直ちに使用できない。特定のページのフォーワードリロケーションは、ページがまずキャッシュに入る最初のトランザクションではなく、ページが読み取り、または改正されるトランザクションの発生ごとにせいぜい１回発生する。アウトバウンドリロケーションはクライエントアプリケーションによって使用が可能な形態から外部フォームへの翻訳が関与する。特定ページのアウトバウンドリロケーションは連続的なトランザクションの終了部で発生する。ここではページは変更されている。あるいは、変更ページはキャッシュから他の手段で取り戻されなければならない。本願発明の利点はクライエントアプリケーションにより使用されるアドレスのマネージメントにより、連続的トランザクションに必要なフォーワードリロケーションの数を減少させることである。
【００１５】
本願発明は以下の解説からさらに理解されよう。
【本発明の実施の態様】
好適実施例の詳細な説明
図１から４は代表的なベーシックコンピュータシステムを表す。ここで本願発明のバーチャルメモリマッピング方法と装置のためのポインターリロケーション最良化が実践できる。
【００１６】
図１は複数のクライエントコンピュータ４０、クライエントとサーバーコンピュータ４２及びサーバーコンピュータ４４がコンピュータネットワーク４６またはコンピュータバス等の他のコンピュータ通信通路で接続されているシステムを図示している。クライエントコンピュータ４０はユーザによって使用され、種々なアプリケーションソフトを実行する。サーバーコンピュータ４４はデータベースで維持されるデータの永久レポジトリとして作用する。一般的に、どのクライエントコンピュータ４０でもサーバーコンピュータ４４に保存されたデータにアクセスできる。コンピュータ４２によってはクライエントコンピュータ及びサーバーコンピュータとして作用する。このようなコンピュータ４２は自身が保存するデータにアクセスでき、他のサーバーコンピータ４４のデータにもアクセスできる。他のクライエントコンピュータ４０もクライエントとサーバーのコンピュータ４２のデータにアクセスできる。本願発明のデータベース方法と装置は、少なくとも１つのクライエントとサーバーコンピュータ４２または少なくとも１つづつのクライエントコンピュータ４０とサーバーコンピュータ４４をそれぞれコンピュータネットワークまたは通信通路４６で接続したシステムで使用できる。説明を簡単にするため、クライエントコンピュータ４０または、クライエントコンピュータとして作用するコンピュータ４２を“クライエント”と呼称し、サーバーコンピュータ４４またはサーバーとして作用するコンピュータ４２を“サーバー”と呼称する。
【００１７】
図２は単純化された本発明システムの詳細図である。サーバーコンピュータ４４はディスクまたは他の大量保存媒体５２に接続されたＣＰＵ５０を含んでいる。これはデータベース用データの永久レポジトリである。ＣＰＵ５０はデータをディスク５２とネットワーク４６との間で移動させる。クライエントコンピュータ４０はデータをネットワーク４６とそのキャッシュメモリ５６との間で移動させるＣＰＵ５４を有している。ＣＰＵ５４はキャッシュ５６の物理的アドレスにマップされたバーチャルアドレススペースをコントロールする。クライエントコンピュータ４０で作動するアプリケーションはキャッシュメモリ５６内のデータの読み取り、書き込み、創出及び削除によってデータベースのデータを操作するであろう。クライエント４０は、キャッシュメモリ５６のデータの全ての操作を行い、標準分散データベースシステムでのようにサーバーコンピュータ４４に保存されたデータに対してコンピュータネットワーク４６でトラザクションは行わない。トランザクションがキャッシュメモリ５６のデータに対してクライエントコンピュータ４０で完了すると、このトランザクションの結果はネットワーク４６を介してサーバーコンピュータ４４の永久レポジトリ、すなわちディスク５２に伝達される。クライエントコンピュータ４０とサーバーコンピュータ４４の間の相互作用の方法は通信ネットワーク上のサーバーコンピュータ４４とクライエントコンピュータ４０の数には無関係であり同じである。
【００１８】
図３は組み合わされたクライエントとサーバーコンピュータ４２の特殊なケースを図示する。このようなコンピュータは図２のクライエントコンピュータ４０またはサーバーコンピュータ４４のいずれかとして使用できる。このようなコンピュータは典型的なサーバーコンピュータ４４、及び典型的なクライエントコンピュータ４０として図２に関連して説明したモードで作用することができる。
【００１９】
クライエントとサーバーコンピュータ４２はキャッシュメモリと永久データレポジトリ５２の間で相互作用もＣＰＵ６０を介して扱う。この相互作用はサーバーコンピュータＣＰＵ５０、クライエントコンピュータＣＰＵ５４及び通信ネットワーク４６の組み合わせ５８（図２）の相互作用と類似している。クライエントとサーバーコンピュータ４２のキャッシュメモリ５６は典型的なクライエントコンピュータ４０のキャッシュメモリ５６と同様に機能する。
【００２０】
図４はバーチャルメモリマッピングデータベース（ＶＭＭＤＢ）のモジュール性と相互作用を図示する。クライエントコンピュータ４０またはクライエントとサーバーコンピュータ４２のＶＭＭＤＢ６６はそのオペレーションシステム６８により提供されるサービスを利用する。一方、ＶＭＭＤＢ６６はアプリケーションプログラム６４で使用されるサービスを供給する。サーバーコンピュータ４４でＶＭＭＤＢ６６はオペレーションシステム６８と相互作用し、クライエントコンピュータからのリードリクエストとライトリクエストを扱い、データページのオーナーシップをモニターする。
【００２１】
図５は少なくとも１つのデータベース７０へのデータ５２の永久レポジトリの分割を図示する。各データベース７０は少なくとも１つのセグメント７４に分割される。各セグメント７４は少なくとも１つのクラスター７３に分割される。各クラスター７３は多数のページ７２を含んでいる。これらページはクラスター７３の最初からページ数７１によりアドレスできる。各ページはページの最初からオフセットによりアドレスされる多数のアドレス可能なロケーション（個々のバイト）を含んでいる。これらアドレス可能なロケーションはクラスターの最初からオフセットでアドレスされているとも考えられる。そこで、このオフセットはページ内のアドレス可能なロケーション数をページ数に掛け算し、ページ内でオフセットを足し算することで計算される。すなわち、データベース内の各アドレス可能なロケーションは次のようにアドレスを有している：［データベース、セグメント、クラスター、オフセット］。アドレス可能なロケーション７２の配列はデータベースアドレスに対応する値またはポインターを含むことができる。ポインターは同一データベースの現行ページまたは他のページあるいは他のデータベースの他のページ内にポイント処理できる。クライエントアプリケーションがデータベースにアクセスすると、ＶＭＭＤＢはクライエントアプリケーションがアクセスする必要があるデータベースのページにクライエントのバーチャルアドレススペースからバーチャルアドレスを指定する。
【００２２】
図６はパーシステントリロケーションマップ（ＰＲＭ）１４０と、関連データベースページ１４４のポインター１４２内へのＰＲＭ１４０のインデックス処理を図示する。各ページはメタデータ構造と呼ばれる関連構造を有している。ページとメタデータ構造はページがアクセスされたときには常にサーバーとクライエントとの間で共に通信される。サーバーはメタデータ構造とページとの組み合わせを維持する。メタデータ構造はＰＲＭと以下で解説する様々なタッグを含んでいる。ＰＲＭとタッグはページのポインターのロケーションと翻訳とを解説する。ＰＲＭ１４０は複数のエントリー（ＰＭＲＥ）１４６，１４８を有しており、それぞれデータベースのページ内にインデックス処理する。データベースページのポインター１４２は４バイト値（８バイト値も同様に表すことが可能）である。ポインター１４２は２つのフィールドに分割される。インデックスフィールド１５０とローオフセットフィールド１５２である。インデックスフィールド１５０は同じＰＲＭＥを有したページに次のポインターをインデックスするフィールドである。ローオフセットフィールド１５２の機能はＩＰＲＭＥでリクエスト処理された可能なアドレス可能ロケーション区別することである。これはターゲットクラスター内にて４メガバイトをアドレスできる。ローオフセットフィールドはＰＲＭＥのハイオフセットフィールドに加えられ、ターゲットクラスター内で使用する１つのオフセットを提供する。
【００２３】
各ＰＲＭＳ１４６、１４８はフラッグフィールド１５４、ハイオフセットフィールド１５６、ナンバーフィールド１５８、インデックスフィールド１６０を有している。フラッグは、新データベースインデックスフラッグ、新セグメントＩＤフラッグ、新クラスターＩＤフラッグ、及び新マッピング細分性フラッグである。これらフラッグはどのフィールドがＰＲＭＥのヘッドワードに続くかを示す。ヘッドワードのみを有するショートエントリーＰＲＭＥ１４６はナンバーフィールド１５８の内容と等しいターゲットクラスターＩＤとなる。このナンバーフィールド１５８は、ＰＲＭを構成するＰＲＭＥの配列の以前のＰＲＭＥのターゲットクラスターＩＤ、または、前のＰＲＭＥが存在しないときに現在アクセスされているページのクラスターＩＤに加えられる。長いエントリーＰＲＭＥ１４８はヘッドワードと、続くフィールドを有している。これらの追加フィールドはデータベースフィールド１６２、セグメントＩＤフィールド１６４、クラスターＩＤフィールド１６６、及びマッピング細分性フィールド１６８である。これら追加フィールドはＰＲＭＥヘッドワードのナンバーフィールド１５８と共にターゲットデータベース、セグメント、クラスターまたはマッピング細分性がその配列内の以前のＰＲＭＥのものとどのように異なるのかを示す（以前のＰＲＭＥが存在しなければ現行のページとの相違）。これら追加フィールドのそれぞれは、ＰＲＭＥヘッドワードの対応するフラッグが示すときのみ存在する。ＰＲＭエントリーがソーティングされ、類似ＰＲＭＥが並んでいるかぎり、長いエントリーの代わりに短いエントリーが使用できる。ＰＲＭＥヘッドワード内のヘッドポインターインデックス１６０から開始し、ポインターのインデックスフィールド１５０を通過するリストの各ポインターはターゲットデータベース、セグメント、クラスター、及びＰＲＭＥのマッピング細分性を対象にし、ＰＲＭＥヘッドワードのハイオフセットフィールド１５６と各ポインターのローオフセットフィールド１５２を連続的に組み合わせることで計算される。細分性フィールド１６８のマッピングの目的は６４ｋバイトのユニット、たとえば、１ｘ６４ｋ、２ｘ６４ｋ等々のユニットのターゲットによって必要とされるアドレススペースの倍数を示すことである。
【００２４】
図７はデータベースのクラスターを図示している。データベース７０の各クラスターはページに分割される。各ページはページの内容を説明するデータを含んだメタデータの構造とそれを関連付けており、ページの各オブジェクトのタイプを特定するタッグリストを含んでいる。オブジェクトはページでのみ発見される。よってアプリケーションプログラムはページと直接アクセスするのみであり、メタデータとはアクセスしない。ベタデータはＶＭＭＤＢによってのみ使用される内部データ構造を維持する。各クラスターは少なくとも１ページ８０に分割される。ページ８０のサイズはコンピュータハードウェアにより決定済であり、典型的には４０９６、８１９２、または１６３８４バイトである。この場合、４０９６バイトページを想定している。さらに大きなページは複数の４０９６バイトページにサブ分割できる。クラスター７６内では典型的には３タイプの保存オブジェクトが存在する：シングルオブジェクト８２、オブジェクトのベクトル８４及びフリースペース８６である。オブジェクトはポインターを示すことができる値を含むことができる。フリースペース８６は特殊可変サイズオブジェクトとして理解できる。４タイプ以上のオブジェクトが使用可能であるが、図示の３つは代表例であり、本願発明の実行には充分である。ページ全体あるいはページにオーバーラップする各オブジェクトに対して、タッグがページに関連する対応メタデータ構造に配置される。タッグの配列はタッグ表９４と呼ばれる。シングルオブジェクト８２は対応するオブジェクトタッグ８８を有している。オブジェクト８４のベクトルは対応するベクトルタッグ９０を有するであろう。最後に、フリースペースオブジェクト８６は対応するフリースペースタッグ９２を有するであろう。
【００２５】
図８Ａから８Ｃは図７の各タッグの詳細を示す。オブジェクトタッグ８８（図８Ａ）はタッグがシングルオブジェクトのためであることを示すフラッグフィールド１００とタイプコードフィールド１０２とを有している。タイプコードはオブジェクトの特別な特性を説明し、多様なシングルオブジェクトを有することを可能にする。各タイプは自身の特徴を有する。タイプコードは図９と図１０でさらに詳細に解説する。ベクトルタッグ９０（図８Ｂ）はタッグがベクトルに対するものであることを示すフラッグタッグ１０４と、タイプコード１０２に類似したタイプコード１０６と、ベクトルの長さを示すレングスフィールド１０８とを有している。最後に、フリースペースタッグ９２（図８Ｃ）はタッグがフリースペース用であることを示すフラッグフィールド１１０と、フリースペースの長さを示すレングスフィールド１１２を有している。
【００２６】
本願発明の好適実施例ではシングルオブジェクトタッグ８８は２バイト長である。ベクトルタッグ９０は６バイト長であり、追加４バイトはベクトルにその数の要素を含んでいる。フリースペースタッグ９２は２バイト長である。本願発明の実行に使用されるオブジェクトタイプとタッグの数は使用されるデータベースの種類と実行される操作のタイプに依存し、前述の例には限定されない。
【００２７】
図７に示すタッグテーブル９４はリロケーションが必要なデータベースアドレスを含んだページ内のロケーションの発見に使用される。タッグテーブルは各ページの内容がオブジェクトのエンドツーエンド配列を含んでいるという原理に基づいている。これはクラスターの前及び/又は次のページにオーバーラップするかも知れず、各オブジェクトは知られた数のタイプの１つである。この例では、３タイプが存在する：（１）シンプルオブジェクト、（２）オブジェクトのベクトル一次元配列）及び（３）フリースペースである。タッグテーブルはページ上のオブジェクトの配列に直接対応するタッグの配列を含んだデータ構造とも言える。ページの最初のオブジェクトが前のページにオーバーラップすれば、ページのメタデータのフィールドはオブジェクトのヘッドからページのヘッドまでのバイトによる距離を示すように使用される。
【００２８】
図９に示すデータベースの一部である“スキーマ”と呼ばれるデータ構造はタイプ解説のセットを含んでいる。データベースの特定のオブジェクトタイプごとに１つ用意されている。スキーマはタイプコード１０２と１０６（図８Ａから図８Ｃ）でインデックスされる。タイプ解説はオブジェクトのサイズと、そのオブジェクトのポインター値のロケーションを示す。スキーマはデータベース内の自身のクラスター内に配分される。スキーマ１２０は対応するデータベースに含まれる各々異なるオブジェクトタイプ（タイプコードで示す）に対してタイプ解説１２２を含んでいる。各タイプ解説１２２は１つのオブジェクトタイプを説明し、ユニークタイプコード値がそれぞれに割り当てられている。オブジェクトタッグからのタイプコード値１０２、１０６が与えられると、ＶＭＭＤＢはタイプコードを使用してそのオブジェクトタイプに対応するタイプ解説１２２に対してスキーマ１２０内にインデックスすることができる。
【００２９】
ページのメタデータはタッグテーブル９４とスキーマ１２０（タイプ解説１２２を含む）を介してページ内の全てのポインターを追尾する。メタデータはパーシステントリロケーションマップでパーシステントアドレススペースのページ特定配分をも追尾する。
【００３０】
図１０はタイプ解説１２２の内容を図示する。タイプ解説１２２はタイプコードフィールド１２４でインデックスされており、そのタイプのオブジェクトのサイズを含むサイズフィールド１２８と、ポインターを含むそのタイプのオブジェクト内のどのロケーションがポインターを含むかを示すフィールドセット１２８を含む。これらフィールド１２８はＶＭＭＤＢにより解釈され、オブジェクト内でポインターのロケーションを発見するインストラクション１３０のセットである。それらは普通はハードウェアＣＰＵが直接理解する機械インストラクションではない。
【００３１】
これらインストラクションの２種類が存在する：１つはポインターがオブジェクトタイプ内の特定オフセットに存在することを示し、他はバーチャルファンクションテーブル（ＶＴＢＬ）ポインターがオブジェクトタイプの特定オフセットで発見されることを示す。（ＶＴＢＬポインターはＣ++言語の実行の一部であり、単にＶＭＭＤＢがリロケーションを実行する特定タイプのポインターである。ＶＴＢＬはアプリケーションがバーチャルファンクションのコールに使用するファンクションポインターのテーブルをポイントする。）
【００３２】
図１１はタイプ解説１２２からのインストラクション１３０（図１０）のフォーマットである。それぞれのインストラクションはこのポインターがＶＴＢＬポインターであるか、リロケーションすべきポインターであるかを示すフィールド１３２を有している。フィールド１３４はポインターが存在するオブジェクトの開始部からのオフセットを示す。
【００３３】
図１２はクライエントコンピュータ４０のキャッシュメモリ５６の構造と、キャッシュメモリステータスをモニターするためのクライエントコンピュータＣＰＵ５４により使用されるキャッシュディレクトリと呼ばれる構造を図示する。クライエントキャッシュメモリ５６はクライエントディスクの典型的には物理的キャッシュファイル内のページフレーム１７０のセットを含んでいる。またはクライエントディスクの作動システムのスワップファイルの一部内に存在するページフレーム１７０のセットを含んでいる。各ページフレーム１７０はフリーであるか、データベースのページを有している。クライエントコンピュータはキャッシュディレクトリを維持する。これはどのページフレーム１７０がデータベースページを含み、どのページがフリーであるのかモニターする。２つのフレームで同じページを保持するものはない。データベースのページ、例えばページ“５”、クラスター“ｎ”、セグメント“４”、データベース“/Ａ/Ｂ/Ｃ”を与えられると、ＶＭＭＤＢはキャッシュディレクトリ１８０を使用してページ（ページの物理的ロケーション）を保持するページフレーム１７０を効率的に決定し、またはそのページがキャッシュには存在しないことを決定する。この目的で、キャッシュディレクトリ１８０はフレームフィールド１７２を含む。これはページフレームの番号と、クラスターＩＤ、セグメントＩＤ、及びデータベースインデックスによりフレーム内のページを特定するコンテンツフィールド１７４とを含む。ページがキャッシュになければそのためのエントリーはない。
【００３４】
キャッシュディレクトリ１８０の各ページフレーム１７０はそれと関連する４ステート値を有している。最初の２つはエンキャッシュされたステート１７６とロックされたステート１７８を示す。エンキャッシュされたステートは“リード用エンキャッシュ（ＥＲ）”あるいは“ライト用エンキャッシュ（ＥＷ）”できる。ロックされたステートは“アンロック（Ｕ）”、“リード用ロック（ＬＲ）”、または“ライト用ロック（ＬＷ）”できる。ページのステートがＥＷＬＲであることはそれがライトのためにエンキャッシュされており、リードのためにロックされていることを意味する。ページがＥＲのステートであることは、リードのためにエンキャッシュされており、アンロックされていることを意味する。キャッシュディレクトリエントリの他の２つのフラッグは“実行時ダウングレード”１８２及び“実行時エビクト”と呼ばれる。これらフィールドの目的はオペレーションのフローチャートに関して後述する。
【００３５】
図１３はオーナーシップテーブルを示す。サーバー４４はどのクライエント４０がデータベースからページのコピーを有しているか、そのページはそのクライエントによりリードのため、またはライトのためにエンキャッシュされているかの追尾を行う。サーバーはオーナーシップテーブルでデータベースの使用をモニターする。オーナーシップテーブル１９０は３フィールドを含んだエントリー１９２を含んでいる。コンテンツフィールド１９４はページ数、クラスター番号、セグメント番号及びデータベースネームを示す。オーナーフィールド１９６は現在どのクライエントがそのページを使用しているか示す。オーナーフィールドは好適にはクライエントネームのアレイである。ステータスフィールド１９８はページがリードまたはライトのためにクライエントでエンキャッシュされているかどうかを示す。１つの値のみの保存でよい。なぜなら、全てのクライエントはリードのためにエンキャッシュされたページを有するか、１つのクライエントがライトのためにエンキャッシュされたページを有するからである。
【００３６】
キャッシュディレクトリ１８０とオーナーシップテーブル１９０の組み合わせはキャッシュコヒーレンシーを維持する。クライエントプロセスは、ページを有するページフレームがクライエントによるライトのためにロックされているなら、ページの内容を修正することができるだけである。ページフレームはライトのためにエンキャッシュされているならライトのためにロックできるだけである。このステータスの確認とロッキングはクライエントでキャッシュディレクトリを使用して実行される。クライエントがライトのためにエンキャッシュされたページフレームを有していれば、他のクライエントコンピュータはそのキャッシュに同じページを有することができない。多くのクライエントがリードのためにエンキャッシュされたページのコピーを有することは可能であるが、一時に１クライエントのみがライトのためにエンキャッシュされたページのコピーを有することができる。エンキャッシュされたステータスの確認はオーナーシップテーブルを使用してサーバーにより実行される。クライエントコンピュータでトランザクションが進行していなければ、そのキャッシュの全ページフレームはアンロックされる。トランザクションがクライエントで進行中であれば、ロックされたページはアンロックできない。ライトのためにロックされたページはリードのためにロックできない。すなわち、ページはリードからライトにロックまたはアップグレードできるが、トランザクション中はアンロックもダウンロードもできない。ロックはトランザクションが関与するときにリリースされる。このルールはデータベース用の標準２フェーズロッキングルールに対応する。
【００３７】
この２フェーズロッキングの形態の利点は、サーバーコンピュータではなくクライエントコンピュータでロックのモニターをする点にある。さらに、データはサーバーではなくてクライエントでキャッシュされ、使用される。ロッキング情報のサーバーへの送付のオーバーヘッドは低減される。よって、データはサーバーへのエクストラコールなしで２トランザクション以上に使用できる。すなわち、このキャッシュ戦略はトランザクションのクライエント内でページを維持することを可能にする。以下で解説するページアドレス方法の追加はクライエントに残るページのアクセスを高速にする。これが本願発明の主たる利点である。それでも２フェーズロックの標準特徴は、全てのデータが利用可能になるまでのライトロックの妨害及びデッドロックを妨害する“時間切れ”またはデッドロックを検出する他のスキームの提供を含んで使用可能である。
【００３８】
ページがクライエントキャッシュメモリ５６に入れられた後、そのページの全てのポインターのターゲットは図１４に示すようにクライエントコンピュータＣＰＵのバーチャルアドレススペース２００内にロケーションを割り当てられなければならない。そしてポインターは、そのデータがバーチャルメモリにマップされ、クライエントアプリケーションで使用される前に翻訳されなければならない。このプロセスはインバウンドリロケーションと呼ばれる。この割り当てはバーチャルアドレスマップ（ＶＡＭ）と呼ばれる現行のアドレスバインディングセット２１０を使用して、どのデータベース、セグメント、クラスター、オフセット及びレングスがクライエントのバーチャルアドレススペースの特定部分に割り当てられたかを示すエントリー２１２で管理される。インバウンドリロケーション中のポインターの翻訳は、ポインターのターゲットに対して１つが存在するなら存在するバーチャルアドレスマップエントリー（ＶＡＭＥ）の使用を必要とする。または、ターゲットの新ＶＡＭＥの構築とそのＶＡＭへのそのＶＡＭＥの組み込みを必要とする。翻訳はさらに、まだであれば、クライエントのバーチャルアドレススペースの領域が、そのＶＡＭＥに予約されて割り当てられることも要求する。最後にポインターの翻訳は、ポインターのローオフセットフィールドとＰＲＭＥナンバーフィールド、ハイオフセット及び/又はオフセットフィールドからクラスター内のＶＡＭＥのオフセットを差し引いたものに等しいバーチャルアドレススペースの割り当てられた領域のトップからのオフセットとして計算されたポインターのためのバーチャルアドレスのポインター内へライトできる。
【００３９】
バウンドまたは割り当てられたＤＳＣＯハンドルとも呼ばれるバーチャルアドレスマップエントリー（ＶＡＭＥ）２１２はパーシステントリロケーションマップ１４０（図６）のエントリー１４６、１４８に類似している。バーチャルアドレスマップ２１０はバーチャルアドレススペース２００の領域を示す。これはデータベース領域が割り当てられたところである。一方、パーシステントリロケーションマップ１４０はデータベースアドレススペースの領域を示す。各ＶＡＭエントリー２１２はデータベース２１４を含む。これは領域が存在し、その領域がロケーションされるそのデータベースのセグメントを示すセグメントフィールド２１６を示すデータベースを示す。さらに、そのデータベースのセグメントのクラスターを示すクラスターフィールド２１７と、その領域が始まるクラスターの開始部からアドレス可能がユニット（バイト）でのオフセットまたは距離を示すオフセットフィールド２１８が含まれる。その領域の長さを示すサイズフィールド２２０が存在する。サイズフィールド２２０はＰＲＭＥのマッピング細分性フィールドと同じである。その領域の最初のアドレス可能なロケーションに割当てられたバーチャルアドレスを示すアドレスフィールド２２２も存在する。
【００４０】
キャッシュ内のデータページにアクセスためのアプリケーションでは、データをバーチャルメモリーにマッピング処理する必要がある。図１５には、クライエントコンピュータによるマッピング処理の後での、（クライエントディスク上の別のファイルとして、あるいは、クライエントのスワップファイルの一部として一般的に実行される）キャッシュ５６に対するバーチャルアドレススペース２００の関係が概略的に図示されている。バーチャルメモリーマップ２２４は、ほとんどのコンピュータシステムにおける標準方法で、クライエントコンピュータのオペレーションシステム６８により作成される。そのバーチャルメモリーマップには、バーチャルアドレスがマッピングされるキャッシュファイルアドレスが示されている。バーチャルメモリーマップは、普通、各ベージのバーチャルアドレス２２５、レングス２２６、対応するキャッシュファイルリロケーション２２８、リードとライト保護ステート２２７をそのページに含む各ページのエントリーを有する。
【００４１】
図１６Ａ−１６Ｃは、キャッシュディレクトリー、バーチャルアドレスマップ、オペレーションシステムのバーチャルメモリーマップの相互関係を示す。キャッシュディレクトリ１８０（図１２）は、キャッシュメモリー５６内でデータベースページが発見されるキャッシュファイルアドレス（ページフレーム）を示している。バーチャルアドレスマップ２１０（図１４）は、データベースページが割当てられるバーチャルアドレス、つまり、アプリケーションで利用する場合にマッピング処理されるバーチャルアドレスを示している。バーチャルメモリーマップ２２４（図１５）は、キャッシュディレクトリ１８０とバーチャルアドレスマップ２１０からＶＭＭＤＢによって与えられた情報からオペレーションシステムが作成したものである。ＶＭＭＤＢは、オペレーションシステムに、バーチャルメモリー内にデータベースページをマッピングするように指示し、それにキャッシュファイルアドレスを与える。それはキャッシュディレクトリー１８０からのもので、データベースページを含んでいる。さらにバーチャルアドレスも与えられる。それはバーチャルアドレスマップ２１０からのものである。
【００４２】
データベースページを、バーチャルメモリーにマッピングするより前にキャッシュにまず送るときには、そのページのポインターはＰＲＭエントリーへのスレッドポインターとして外部表示内に存在する。ページをバーチャルメモリーにマッピングするとき、それらポインターは、そのデータがアプリーケーションで使用される前に、その外部様式から対応するバーチャルアドレスへと翻訳しなければならない。“インバウンドリロケーション”とも呼ばれるこの翻訳操作は、図１７に概略的に図示されている。
【００４３】
ページの外部フォーマットを構成するスレッドポインターとそのページのＰＲＭの組み合わせにより、ページの各ポインターのターゲットデータベース、セグメント、クラスター及びオフセットがエンコードされる。データベース、セグメント、クラスター及びオフセットは、それから正しいバーチャルアドレス２３２が得られるバーチャルアドレスリロケーションマップ２１０内の対応エントリーを検索するため利用できる。
【００４４】
図１８は、前記のインバウンドリロケーションの詳細を示す。ページのＰＲＭ内のＰＲＭＥは連続的に処理され、１つが存在するなら、前のＰＲＭＥのターゲットに対応して各ＰＲＭＥにそのターゲットをコンパクトにエンコードさせる。図６に戻ると、各シーケンスＰＲＭＥでは、ＰＲＭＥのターゲットの４メガバイト範囲は、そのナンバーフィールド１５８、ハイオフセットフィールド１５６、ヘッドワードに続く４つの追加フィールドのうちいずれかから演算することで得られる。これらの追加フィールドとは、データベースインデックスフィールド１６２、セグメントIDフィールド１６４、クラスターIDフィールド１６６、マッピング細分性フィールド１６８である。この演算プロセスは以下のように実行される。ＰＲＭＥにデータベースインデックスフィールドが備わっていれば、そのターゲットデータベースは、ページのソースデータベースに含まれるテーブルを使用して、このインデックスの翻訳により決定される。ＰＲＭＥにデータベースインデックスフィールドが備わっていなければ、そのＰＥＭＥのターゲットデータベースは、このページのために以前に処理されたＰＲＭＥのターゲットデータベースが存在すれば、それと同じであるか、そのページ自体のソースデータベースである。ＰＲＭＥにセグメントＩＤフィールドが備わっていれば、ターゲットセグメントはそのＩＤによって示される。ＰＲＭＥにセグメントＩＤフィールドが無く、データベースインデックスフィールドが備わっていれば、そのターゲットセグメントは、セグメントＩＤとしてナンバーフィールド１５８の値を使用することで示される。ＰＲＭＥが、データベースインデックスフィールドもセグメントＩＤフィールドも備えていなければ、そのターゲットセグメントは、そのページの以前に処理されたＰＲＭＥのターゲットデータベースが存在すれば、それと同じであるか、該ページ自体のソースセグメントである。ＰＲＭＥにクラスターＩＤフィールドが備わっていれば、ターゲットクラスターはそのＩＤによって示される。ＰＲＭＥにクラスターＩＤがなく、データベースインデックスフィールドか、セグメントＩＤフィールドの一方、またはその両方が備わっていれば、そのターゲットクラスターは、クラスターＩＤとしてナンバーフィールド１５８の値を使用することで示される。ＰＲＭＥが、データベースインデックス、セグメントIDあるいはクラスターIDフィールドの何れも備えていなければ、そのクラスターIDは、ナンバーフィールド１５８の値を、そのページの以前に処理されたＰＲＭＥのクラスターＩＤが存在すればその値に加えるか、あるいは、そのページ自体のソースクラスターのＩＤに加えることで算出される。ＰＲＭＥのマッピング細分性フィールドが存在する場合は、それはターゲットデータベース、セグメント及びクラスターによってそれまで示されてきたターゲット領域へのアドレススペースの割当てのために連続していることが必要なアドレススペースの量を示す。ＰＲＭＥのマッピング細分性フィールドが存在しないで、データベースインデックスフィールドか、セグメントＩＤフィールドが存在する場合は、そのターゲットのマッピング細分性は６４キロバイトのデフォルト値に設定される。も��、マッピング細分性フィールド、データベースインデックスフィールドあるいはセグメントＩＤフィールドのいずれも存在しなければ、そのターゲットのマッピング細分性は、そのページの以前に処理されたＰＲＭＥが存在すればその値か、６３キロバイトのデフォルト値である。翻訳処理によって、これまでにターゲット領域のターゲットデータベース、セグメント、クラスター及びマッピング細分性が作成された。
【００４５】
上記のＰＲＭＥの翻訳処理後に、ＰＲＭＥのヘッドポインターインデックスフィールド１６０は、そのターゲットをエンコードするために、ローオフセットフィールド１５２との組み合わせでＰＲＭＥを使用するページの第１ポインターを検索するようトラバース処理される。後続のポインターは、図６に示すように、インデックスフィールド１５０を介してリンクされる。ＰＲＭＥのヘッドポインターインデックスフィールド１６０から到達可能な全てのポインターは、同じターゲットデータベース、セグメント及びクラスターを共有する。それらは上述のＰＲＭＥ翻訳処理により提供された値である。これらのポインターの実際のターゲットは、ターゲットクラスター内のオフセットによってのみ異なるであろう。このような各ポインターのオフセット値は、ＰＲＭＥのハイオフセットフィールド１５６を、各ポインターのローオフセットフィールド１５２と組み合わせることで算出される。
【００４６】
前記のデータベース、セグメント及びオフセットは次に、対応するバーチャルアドレスマップエントリー（ＶＡＭＥ）２１２（または割当てＤＳＣＯハンドルとも称される）を検索するために使用される。この対応ＶＡＭＥは、ターゲットオフセットが、オフセットフィールド２１８のＰ値以上であって、そのオフセットＰとそのエントリーのレングスフィールド２２０のＱ値の合計未満のものとなる。（ターゲットオフセット<Ｐ+Ｑ）。前記ポインターのターゲットのバーチャルアドレスは、Ｐ−ターゲットオフセット値の差値をＲ（ＶＡＭＥの第１仮想アドレス）に加算して算定できる。アウトバウンドリロケーション中に、ポインターのバーチャルアドレスを外部フォーマットへ翻訳するには、これとは逆の工程を実行する。
【００４７】
データのページをデータベースから取り出し、キャッシュへ格納する場合、このページはインバウンドリロケーションされる。つまり、そのページ内のポインターは、その外部フォーマットからバーチャルアドレスへ翻訳される。データのページをサーバへ返送するプロセスは、アウトバウンドリロケーションと呼ばれる。この情報がアドレススペース作成に利用できなくなった後のキャッシュ内に残っているデータページのポインター情報を更新するプロセスはフォワードリロケーションと呼ばれる。
【００４８】
図１９には、本発明のリロケーション最適化方法で使用するデータ構造であるリロケーション最適化行列（リロプト行列）が図示してある。ここでいうリロケーション最適化とは、フォワードリロケーションの頻度を減らす操作をいう。キャッシュデータの保全は、リロプト行列を使って実行できる。リロプト行列により、アドレススペース作成が一般的には単独のトランザクションであるが、トランザクションの一部あるいは連続するトランザクション群であり得るような、連続アドレススペース作成におけるＰＳＲ内のバーチャルアドレススペースが管理およびインデックス処理される。
【００４９】
図２３には、パーシステントリロケーションへのポインターの全ターゲットを取り囲み、キャッシュ内のページがアプリケーションにアクセス可能であるＰＳＲ（パーシステント記憶領域）セクションを含むヒープとスタックのプロセスアドレススペースを示す。クライエントアプリケーションがデータベースにアクセスすると、クライエントアプリケーションは、バーチャルアドレススペースのＰＳＲ部内からバーチャルアドレスを、アプリケーションがアクセスする必要があるページに割当てる。このバーチャルアドレスの割当ては、アクセスする特定のページの領域、および、特定ページがポイントするページを有する領域についてのみ実行される。バーチャルアドレスの割当てはデータベースへアクセスする各クライエント内に制限されるので、クライエントは自身のバーチャルアドレス割当てを有する。標準的なＰＳＲの大きさは１２８メガバイトであるが、アプリケーションに応じて変更しても構わない。各セッションは１個のＰＳＲを有する。
【００５０】
アドレススペース作成の期間は、クライエントアプリケーションで管理下におかれ、クライエントアプリケーション要件により決定され、リード及び/又はＰＳＲ内のポインターセットは、演算における特異点に達するまで変更してはならない。それら特異点は、クライエントアプリケーションで指示される場合、アドレススペース作成の範囲を決める。
【００５１】
１セッションにつき１リロプト行列が提供される。システムの各クライエントにつき１セッションが与えられる（ただし、１つのアプリケーションプロセスに、複数のクライエント、つまり、複数のセッションを含むことができる）ので、クライエントとセッションの用語は、リロプト行列の説明においては相互交換しても使える。
【００５２】
前記の本発明のこの実施例では、リロプト行列を、必要に応じてオブジェクトを行列のどこにでも挿入や除去ができるよう、ダブルリンクリストとして実行する。行列の一方の端はヘッドであり、他方の端はテイルである。リロプト行列を図示した図面では、右側がヘッド側である。行列の要素の順序は、リロプト機構の機能のため、ヘッドに近いほうを最近利用（ＭＲＵ）要素とし、テイルに近いほうを最遠利用（ＬＲＵ）要素として説明することもできる。リロプト行列を説明するのに使うことができる別の非公式だが便利な順序として、ここで使用する新しいとか古いという用語は確立された年代順序を意味するものではないが、ヘッドに近いほうを新しい要素とし、テイルに近いほうを古い要素とみなすことも可能である。リロプト行列内のオブジェクトには、それぞれ下記に詳細に説明するような、フィンガー、データベースセグメントクラスターオフセット（ＤＳＣＯ）、ハンドル、ページハンドル及び変位アドレスバインドセット（ＤＡＢＳ）が含まれる。
【００５３】
フィンガーは、リロケーション最適化法の機能に対して重要なリロプト行列での位置を指定する要素である。基本的なリロケーション最適化法では、さまざまなフィンガーである挿入フィンガー、スキャンフィンガー、移動フィンガー、削除フィンガー、およびモジュラスフィンガーがある。高度なリロケーション最適化法では、複数の挿入フィンガーでもよい。
【００５４】
基本的なリロケーション最適化法では、挿入フィンガーは行列の“最新”端とも呼ばれる行列のヘッドに固定される。この挿入フィンガーは、ページやＤＳＣＯハンドルが行列に挿入される場所である行列の唯一のポイントを示す。
【００５５】
挿入フィンガーの左にあるフィンガーはスキャンフィンガーである。スキャンフィンガーは、定義上挿入フィンガーよりも古く、移動フィンガーや削除フィンガーよりも新しい。スキャンフィンガーと挿入フィンガーは行列のセグメントに境界を設け、その中でページハンドルは、すべてのポインターが有効で、かつ、それ以上のプロセスを必要とすることなく、現行のアドレススペース生成期間有効であり続けると保証されるページに対応している。スキャンフィンガーの位置は、新アドレススペース生成が開始されるまで、リロプト行列列内に固定され、そのポイントで、スキャンフィンガーはリロプト行列のヘッドに移動する。それは挿入フィンガーよりもほんの少々古い。スキャンフィンガーは生成番号が現行の生成であり、スキャンフラッグが設定されている最も古いページハンドルよりもほんの少々古い。生成番号とスキャンフラッグについては後述する。
【００５６】
フォワードリロケーションの目的は、クライエントアプリケーションに、一連のアドレススペース生成時に、任意時ＰＳＲにフィットできる分を越えた大量のパーシステントデータにアクセスさせることである。システムによっては、フォワードリロケーションはアウバウンドリロケーションとインバウンドリロケーションとの組み合わせで置き換えられる。しかしこの置き換えは、本発明に関しては重要ではない。なぜならフォワードリロケーションでも、アウトバウンドとインバウンドのリロケーションの組み合わせでも同様に機能する。同じ作業を行うのにアウトバウンドとインバウンドリロケーションの組み合わせのコストの半分以下のコストで済むため、フォワードリロケーションが好ましい方法である。
【００５７】
本発明の第一の目的は、クライエントアプリケーションに透明である方法で、フォワードリロケーション（あるいは前述のような同様の機能を実行する代用物）の頻度を減らすことである。これにより、クライエントアプリケーションとＶＭＭＤＢの組み合わされたシステムの性能全体を向上させる。この組み合わせシステムが、本発明が適応されない場合にフォワードリロケーションを必要としないという利益を実現した場合は常に、このシステムはリロケーション最適化あるいはリロプトの恩恵を受けたとされる。
【００５８】
リロプト行列は、本発明における構造であって、その目的は、アドレススペースのバインディングをこれらバインディングが一番最近に使用されたもの（ＭＲＵ）が行列のヘッドに最も近くなるようにする等、使用の最近性によって大まかに順番付けられるように整理することにある。
ＰＳＲ内における全ての利用可能なバーチャルアドレススペースがバインディングによって占められた場合、現時点のアドレススペースの生成において使用されていない以前の（ＬＲＵ）バインディングは転置が可能であり、よってこれらが占めていたバーチャルアドレススペースを利用できるようにする。以前のバインディングの転置を優先させ、新しいバインディングが利用できるようにスペースを作るために必要に応じてのみこのような転置を行うことによって、ほとんどのクライエントアプリケーションにとって典型的である一時的なローカリティプロパティと本発明とを組み合わせた場合に、そのクライエントアプリケーションによって次回使用された場合にクライエントキャッシュのページに無効であるポインターが含まれているという状態の頻度を低減させることが可能となる。このようなページのみがフォワードリロケーションを必要とするため、フォワードリロケーションの頻度が低減される。
【００５９】
前述のように、リロプト行列においてはアドレススペースのバインディングを整理する。これらバインディングは、行列内においてＤＳＣＯハンドルと称されるオブジェクトによって表されるものであり、ＤＳＣＯとはデータベース、セグメント、クラスターおよびオフセットの略である。ＤＳＣＯハンドルは、バーチャルアドレスマップにおけるエントリーでもある。各ＤＳＣＯハンドルは、クラスターが６４キロバイトのデフォルトマッピング細分性のみを必要とする場合にデータベース、セグメント、クラスター、オフセットあるいはサイズによって指定されるパーシステントな領域を静的に引用する。第２の類似したＤＳＣＯハンドルは６４キロバイト以上のマッピング細分性を有するクラスターである。この場合、本発明の機能にとっては必須ではない簡素化のための実施上の決定事項としてこれらクラスターのマッピング細分性とサイズとは一致する。特に明記しない限り本文においてＤＳＣＯハンドルについて述べる場合にはいずれかの種類について述べているものとする。ＤＳＣＯハンドルはデータベース、セグメント、クラスターおよびオフセットのために別個のフィールドを備えるものではない。むしろクラスターハンドルである唯一のフィールドを含むものであって、このようなクラスターハンドルとは特定のデータベースにおける特定のセグメント内の特定のクラスターである。したがって同一のクラスターであるＤＳＣＯハンドルは同一のクラスターハンドルを共有するものであり得る（このことはＤＳＣＯハンドルのサイズを低減する実施上の決定であって、本発明の機能に対して必須ではない）。またＤＳＣＯハンドルは、ゼロであってもＰＳＲ内におけるバーチャルアドレスの値であってもよいバーチャルアドレスフィールドを含む。このフィールドがゼロである場合、ＤＳＣＯハンドルは割り当てられていない、あるいはバウンドされていないと称される状態にある。このフィールドがゼロでない場合、このＤＳＣＯハンドルは割り当てられている、あるいはバウンドされていると称される状態にあり、バウンドされているＤＳＣＯハンドルはさらにＶＡＭＥとも称される。このフィールドに含まれるアドレスから開始され、このサイズフィールドの値と等しいバイトの数だけ連続するバーチャルアドレススペース領域は、パーシステントな領域内におけるターゲット並びにこのパーシステントな領域内におけるパーシステントなデータを構成するページに関する両方のポインターによって使用されるべく予約されているとみ考えられる。このバーチャルアドレススペース領域は、ＤＳＣＯハンドルに対して割り当てられている、あるいはバウンドされているとも称される。ＤＳＣＯハンドルが割り当てられるが、これに対して割り当てられているバーチャルアドレススペース領域は他のいかなるＤＳＣＯハンドルに対しても割り当てられない。バウンドされているＤＳＣＯハンドルは、ＰＳＲ内におけるプロセスアドレススペースの連続する領域とパーシステントなアドレススペースの同等サイズを有する連続する領域との間の双方向的なマッピングである。転置フィンガーと挿入フィンガーとの間における全てのＤＳＣＯハンドルのサイズの合計は、ＰＳＲのサイズによって限定されている。
【００６０】
バウンドされたＤＳＣＯハンドルのみがＶＭＭＤＢシステムによって管理されており、バーチャルアドレスによってインデックスされるバーチャルアドレスマップ上にてエントリーとして現れる。クライエント内において現存する全てのＤＳＣＯハンドルが、データベース、セグメント、クラスターおよびオフセットにてインデックスされる、ＤＳＣＯマップと称される別のテーブルにおいてエントリーとして現れる。このＤＳＣＯマップは、ポインターのターゲットとされるデータベース、セグメント、クラスターおよびオフセットが識別できる程度にまでにＰＲＭＥとポインターの組み合わせとの翻訳が完成したとき、主にインバウンドリロケーションによって使用される。インバウンドリロケーションにおいてＤＳＣＯマップが使用されることに関しては後に詳述する。
【００６１】
クライエント内において現存する全てのＤＳＣＯハンドルは、バウンドされているものであろうとなかろうと、リロプト行列内における要素である。
【００６２】
ＤＳＣＯハンドルに加えて、リロプト行列はページハンドルと称される要素を含む。クライエントキャッシュに現存し、アウトバウンドリロケーションよりも最近にインバウンドリロケーションが行われた全てのページに対して個別のページハンドルが存在する。リロプト行列内におけるＤＳＣＯハンドルに関連したページハンドルの配置は、ページハンドルが常にリロプト行列内で対応するページに含まれるポインターによって参照されるパーシステントな領域に対応するＤＳＣＯハンドル、およびページハンドルによって表されるページが所属するパーシステントな領域に対応するＤＳＣＯハンドルよりも古い位置に存在しなければならないとしている定理に従う。この定理の目的は、各ページがリロプト行列をページハンドルの位置に関連する２つの領域に分割することを可能にすることにある。ページハンドルよりも古い領域は、クライエントアプリケーションによってページが有効にアクセスできるようにバウンドされねばならないＤＳＣＯハンドルを含まない。ページハンドルよりも若い領域は、クライエントアプリケーション（およびその他多数）によって、ページに有効にアクセスできるようにバウンドされねばならない全てのＤＳＣＯハンドルを含む。この分割によってバーチャルアドレススペースを利用可能にする目的のためにバウンドされたＤＳＣＯハンドルを転置することによって、転置されるＤＳＣＯハンドルよりもより古い位置のページハンドルによって表されるページの有効性に影響を与えるだけであることが保証される。
【００６３】
リロプト行列においてはその他の要素も存在している。このような集合的にはフィンガーと称される要素の一分類は、リロプト行列のセグメントの範囲を定めるために用いられる。本発明の基本的な方法においては、各リロプト行列に対してこのようなフィンガーが５つ存在する。
【００６４】
第１のフィンガーは、挿入フィンガーと称される。これは常にリロプト行列のヘッドに固定されているため、ヘッドと同義である。本発明の発展例においては、複数の挿入フィンガーが存在し得るが、１つ以外は行列のヘッドには固定されていない。このような発展例は後に詳述する。
【００６５】
第２のフィンガーは、スキャンフィンガーと称される。スキャンフィンガーと挿入フィンガーとの間の行列のセクションはスキャンセクションである。アドレススペース生成の開始時にはスキャンフィンガーを挿入フィンガーの隣接する古い位置に移動させることによってこのスキャンセクションは空状態にされる。アドレススペース生成中に、このスキャンセクションには要素が加えられる。スキャンセクション内における要素の有効性は、アドレススペース生成期間中はその方法によって保存される、すなわちスキャンセクション内のＤＳＣＯハンドルは転置されず、よってスキャンセクション内のページハンドルに対応するページに含まれる全てのポインターはアドレススペース生成中は有効であり続ける。
【００６６】
第３のフィンガーは転置フィンガーと称される。この転置フィンガーは常にスキャンフィンガーよりも古い位置に存在する。転置フィンガーとスキャンフィンガーとの間の行列のセクションは非スキャンセクションである。
【００６７】
第４のフィンガーは削除フィンガーと称される。これは常にリロプト行列のテールに固定されるため、テールと同義である。削除フィンガーと転置フィンガーとの間のセクションは転置セクションである。全ての非バウンドＤＳＣＯハンドルは転置セクション内である。全ての現在では無効であるポインターを含むページを表す全てのページハンドルもまた、この転置セクションである。クライエントキャッシュ内にある間は、再びクライエントアプリケーションによって使用され得るためにフォワードリロケーションを必要とする無効ポインターを含むのはこれらのページのみであることに注意されたい。
【００６８】
データベースアプリケーションを開始する際に、すなわち時間ｔ０において、削除、転置、スキャンおよび挿入フィンガーのすべてが行列内において隣接して配置され、図２０において図示されるようにリロプト行列にはその他の要素が存在しない。
【００６９】
第５のフィンガーは、モジュラスフィンガーと称される。その他のフィンガーとは違ってこのモジュラスフィンガーは、行列のセクションの範囲を定めるために用いられるものではない。これはアドレススペース生成数の演算において整数のオーバーフローをオフセットするための技術として用いられるものである。モジュラスフィンガーの機能は、この方法のその他の機能とは別個であるため、後に詳述する。
【００７０】
リロプト行列において存在する最後の分類の要素は転置されたアドレスバインディングのセットである、それぞれの転置されたアドレスバインディングセット（ＤＡＢＳ）は、現在のアドレスバインディングセットと同様の構造を有するバーチャルアドレスからＤＳＣＯハンドルへのマップである。各クライエントに対して複数のＤＡＢＳが存在でき、その最初のものはＤＳＣＯハンドルの第１転置において生成される。ＤＡＢＳの機能は、ＤＳＣＯハンドルの以前のバインディングからバーチャルアドレスへの情報の経路を追尾することにある。これらＤＡＢＳはフォワードリロケーションにおいて用いられる。各ＤＡＢＳは、存在するならリロプト行列の次の若いＤＡＢＳに対するリンクをも有するものである。
【００７１】
その操作中、クライエントアプリケーションは一連のトランザクションを発行する。クライエントアプリケーションはまた、デフォルトによってトランザクションに正確に対応するものであっても、クライエントアプリケーションのさらに精密な制御を行うことによって個々のあるいは一連のトランザクションの一部分に対応するものであってもよい一連のアドレススペース生成をも発行する。トランザクション中、クライエントアプリケーションはパーシステントデータのページに対してＶＭＭＤＢのクライエントコンポーネントに対してリクエストを発行する。要求されたページが既にクライエントキャッシュに存在する場合、ＶＭＭＤＢのクライエントコンポーネントは、そのページがさらなる翻訳（フォワードリロケーション）を必要とするか否かを判断し、必要であればそのような翻訳を行い、その後ＶＭＭＤＢはそのページをＰＳＲにマッピングし、所望されるアクセスのために保護し、対応するページハンドルとキャッシュディレクトリエントリーとの状態を更新することによってクライエントアプリケーションにそのページをアクセスさせる。要求されたページが既にクライエントキャッシュになければ、ＶＭＭＤＢのクライエントコンポーネントはサーバコンポーネントに対してリクエストを発行する。ページに対する要求をサーバコンポーネントに発行すると、多くの場合同時に同じパーシステントデータに対してトランザクションを行う他のクライエントに対する項目をロック問題が関与する。このような問題は標準的な二相式ロッキングデータベースモデルにおける問題と同等であると理解されるため、ここでは考察しない。サーバがクライエントの要求に応答すると、そのページはクライエントのキャッシュ内に配置され、それに対するページハンドルとキャッシュディレクトリエントリーが生成されて、適性に初期化され、そのページはインバウンドリロケーション処理され、その後ＶＭＭＤＢはそれをＰＳＲにマッピングして所望されるアクセスに対して適宜保護することによってクライエントアプリケーションがそのページを利用できるようにする。したがってインバウンドおよびフォワードリロケーションのいずれもがクライエントアプリケーションのパーシステントデータのページに対するアクセス要求によって誘発される。フォワードリロケーションがクライエントキャッシュに既に存在するページに対して行われるものであるのに対して、インバウンドリロケーションは常に現在そこに存在しない場合にクライエントのキャッシュにページが導入される場合に行われるという点であう。
【００７２】
図２１はページの最初のインバウンドリロケーションに続く典型的なリロプト行列を示している。インバウンドリロケーション中に、ページＰ１に対応するページハンドルが挿入フィンガーより古いリロプト行列に置かれ、そのページのＰＲＭが前述のページに含まれるポインターに沿って処理される。
【００７３】
このプロセスにより翻訳されるターゲットを有するそれぞれのポインターにおいて、そのターゲットはＤＳＣＯマップで調べられる。この調査では３つの結果が可能である。すなわち、そのターゲットを取り囲む領域についてバウンドＤＳＣＯハンドルがあるか、そのターゲットを取り囲む領域について非バウンドＤＳＣＯハンドルがあるか、あるいは、そのターゲットを取り囲む領域についてのＤＳＣＯハンドルがない場合である。そのターゲットを取り囲む領域についてバウンドＤＳＣＯハンドルがある場合、バウンドされたバーチャルアドレスは、ポインターのターゲットオフセットとＤＳＣＯハンドルの領域オフセットとの間の差異に加えられるとき、そのポインターについてのバーチャルアドレス翻訳値を作り出す。この値はそのポインターの外部形態に上書きされる。そのターゲットを取り囲む領域について非バウンドＤＳＣＯハンドルがある場合、そのポインター翻訳は進行することができる前にまずバウンドされなければならない。非バウンドＤＳＣＯハンドルをバウンドするプロセスは以下で詳細に説明する。一旦そのＤＳＣＯハンドルがバウンドすると、そのバウンドＤＳＣＯハンドルに対して行ったように、ポインター翻訳処理が継続する。
【００７４】
そのターゲットを取り囲む領域のＤＳＣＯハンドルがない場合、ＤＳＣＯハンドルが作成され、バーチャルアドレスマップの中に置かれ、バウンドされ、バウンドＤＳＣＯハンドルに対して行ったように、そのポインター翻訳処理が再び継続する。３つすべての場合で、ＤＳＣＯハンドルはその後、挿入フィンガーよりもちょっと古いリロプト行列の中に置かれるが、それが作成されなければ、リロプト行列の中のその以前の位置からまずそれを取り出す。ページ上のすべてのポインターが翻訳されるまで、インバウンドリロケーションはこのように進む。図２１の実施例では、リロプト行列にこのように加えられたＤＳＣＯハンドルは、ＤＳＣＯ１、ＤＳＣＯ２、ＤＳＣＯ３およびＤＳＣＯ４となる。インバウンドリロケーションはその後に、そのページに対応するページハンドルの状態を使用中ならびにスキャンされている状態に設定し、その後、適切な保護を備えた適切なアドレスでＰＳＲの中にそのページをマップし、そのページをクライエントアプリケーションに対してアクセス可能にし、そしてそのクライエントアプリケーションにコントロールを戻す。
【００７５】
図２２は、図２０と図２１の例の続きであり、第２ページＰ２が持ち込まれ、またそのページがＤＳＣＯ２によりカバーされる範囲にある場合、また、ＤＳＣＯ１と新たなＤＳＣＯハンドルであるＤＳＣＯ５−（その他の４つのＤＳＣＯハンドルに関して行われたように、作成され、割り当てられ、そしてＤＳＣＯマップとＣＡＢＳの中に置かれる）によりカバーされたターゲットを有するポインターを含み、そのページがインバウンドリロケーションを行い、挿入フィンガーに挿入され、そしてその後にＤＳＣＯ１、ＤＳＣＯ５、およびＤＳＣＯ２がその挿入フィンガーに挿入される場合に何が起こるのかを図示する。
【００７６】
ページハンドルの状態には、“使用中ならびにスキャン中”、“使用中だが非スキャン中”、“非使用中”、そして“非使用中で転置”がある。最初の２つの状態の両方ともでみられる“使用中”という指定は、現行アドレススペース生成時にクライエントアプリケーションにアクセス可能であるページのページハンドルに対応している。“スキャン中”という指定は、リロプト行列のスキャンセクションの中にあるページハンドルに対応している。“転置”という指定は、リロプト行列の転置セクションの中にあるページハンドルに対応している。なお、スキャンページハンドルはすべて使用中であり、転置ページハンドルはすべて非使用中である。“使用中で非スキャン”および“非使用中”状態は、リロプト行列の非スキャンセクション中にあるページハンドルに対応している。
【００７７】
クライエントアプリケーションによりページに対するリクエストが進められると、ページハンドルは個別に使用中にされる。そのクライエントアプリケーションが現行アドレススペース生成が終了したことを指示するときには、ページハンドルは全部まとめて使用から取り外される。
【００７８】
前に述べたように、図２４の継続実施例の中で図示されているように、挿入フィンガーよりもちょっと古い位置にスキャンフィンガーを移動することにより現行アドレススペース生成は終了する。スキャンフィンガーをこのように移動させるだけでは、ページハンドルが非使用中の状態に変わることはない。数多くのページハンドルを同時に非使用中にするプロセスをスピードアップするためには、本発明は、各ページハンドルにおけるアドレススペース生成フィールドと一緒にクライエントの単一グローバル現行アドレススペース生成カウンタを使用する。クライエントグローバルカウンタとフィールドの両方とも３２ビット幅である。グローバルカウンタは、１〜２32−１の範囲にある値をとり、一方、フィードは０〜２32−１という範囲にある値をとる。現行アドレススペース生成がいつ終了しても、グローバルカウンタは増分され、またそれが０にオーバーフローする場合は、即座に１にセットされる。ページハンドルが“使用中でスキャン中”あるいは“使用中で非スキャン中”の状態のいずれかにされている場合は、そのページハンドルのアドレススペース生成フィールドはそのグローバル現行アドレススペース生成数の値にセットされる。このように、ページハンドルのアドレススペース生成フィールドの値がグローバル現行アドレススペース生成カウンタの値と等しい場合は、そのページハンドルは使用中と指定される。フィールドの値がグローバルカウンタの値と等しくない場合、そのページハンドルは、リロプト行列のなかのその位置により、“非使用中”あるいは“転置”状態のいずれかである。このように、アドレススペース生成の終了時にはグローバルカウンタを増分するという単一動作により、各ページハンドルが順次訪問されることは要求されずにそのアドレススペース生成時に使用中であったすべてのページハンドルの状態は有効に変化する。
【００７９】
このプロセスは、グローバルカウンタが前の値よりも小さい値にセットされる場合には整数オーバーフローのためにエラーが発生しやすくなる。ここで可能性のあるエラーとは、この低値をそのフィールドの値として有し、何らかの以前のアドレススペース生成時にセットされたページハンドルが存在し、しかも、そのページハンドルが使用中であるということを意味するように、そのフィールドが現在グローバルカウンタに等しいと解釈することは間違いである。これが、２32−１生成よりも小さい数から０までの範囲にある使用中状態の中に入れられていなかったすべてのページハンドルのアドレススペース生成フィールドをセットすることで、このエラーしやすい状態の発生を防ぐことは、本発明のモジュラスフィンガーの機能である。このモジュラスフィンガーは、アドレススペース生成毎にリロプト行列の中にある１つの構成要素を移動して（古い位置から新しい位置へ）、それがヘッドを通過すると、テールにループバックすることによりこのタスクを達成する。本発明は、この移動をアドレススペース生成の終了時に実施するが、いつでもそれを実施して構わない。モジュラスフィンガーにより移動通過されられるその構成要素がページハンドルであって、そのアドレススペース生成フィールドがグローバル現行アドレススペース生成カウンタに現在は等しくない場合、フィールドは０にセットされる。それはグローバルカウンタの値が少なくとも１に常に維持されているため、整数オーバーフローには無関係に、グローバルカウンタとは等しくはない値となる。このプロセスが正確であるのは、リロプト行列には２32−１構成要素よりも少ない数の構成要素しかないという制限に基づいている。この制限はメモリ消費のコンピュータハードウエアの制限により間接的に課せられており、そのため、本発明により直接課せられる必要はない。
【００８０】
非バウンドＤＳＣＯをバウンド状態にするため、この方法は、どの他のＤＳＣＯハンドルにもバインドされていないＤＳＣＯハンドルのサイズフィールドと等しいかそれより大きなサイズのバーチャルアドレス領域を見つけなければならない。バーチャルアドレスマップはそのような領域が存在するかどうかを決定するように質問できる。もし適当な領域が存在し、その領域がリクエストされたサイズであれば、ＤＳＣＯハンドルにバウンドされている。適した領域が存在し、サイズがリクエストされたものより大きければ、リクエストされたサイズが等しいサイズの領域の一部はＤＳＣＯハンドルにバウンド状態であり、残りは非バウンド状態である。もし、適当な領域が存在しなければ、現在のアドレススペース発生で使用されているページハンドルで必要とされない他のバウンドＤＳＣＯハンドルを非バインドすることで創出できる。本願発明は転置フィンガーを使用して他のバウンドＤＳＣＯハンドルを見つけ、次の転置手法でそれらを非バウンド状態とする。転置フィンガーよりも若い要素が調べられる。その要素がＤＳＣＯハンドルであれば、バウンドＤＳＣＯハンドルにバウンドに間違いない。なぜなら、全ての非バウンドＤＳＣＯハンドルは転置フィンガーの古い側への転置セクションに存在するからである。このように発見されたＤＳＣＯハンドルは非バウンドであり、バーチャルアドレスフィールドは０にセットされ、バーチャルアドレスマップの対応エントリーは変性されてＤＳＣＯハンドルに前にバウンドされたバーチャルアドレス領域がフリーであることを示す。ＤＳＣＯハンドルを参照するエントリーは最も若いＤＡＢＳハンドルに加えられる。それは、ＤＳＣＯハンドルに前にバウンドされたバーチャルアドレス領域のアドレスによりインデックス可能な方法で行われ、バーチャルアドレス領域の開始が決定される。ＤＳＣＯハンドルは転置フィンガーの古い側に配置される。もし、その１側部またはｒ両側部に存在しえるフリー領域と合体したとき、この方法でフリーとなったバーチャルアドレススペース領域のサイズがスペースに対するリクエストを満たすに充分であれば、領域がバーチャルアドレスマップを質問して見つけられると、前述のようにリクエストは充足される。もし合体したフリー領域が充分に大きくなければ、転置手法は次の要素を検査する。
【００８１】
この転置手法で検査された要素がスキャンフィンガーであれば、全ての残ったバウンドＤＳＣＯハンドルはスキャンセクション内でのみ存在しなければならない。全てのそのようなバウンドＤＳＣＯハンドルは現在のアドレススペース生成時だけ現行バウンド状態を維持しなければならないので、他のＤＳＣＯハンドルによって消費されるフリーバーチャルアドレススペースを提供するように非バウンド状態となるものはない。このような場合に、クライエントはバーチャルアドレススペースを消費し、この状態はクライエントアプリケーションに信号される。クライエントアプリケーションは現行のアドレススペース生成を終了させるように選択させ、継続させたり、現行のトランザクションを中断させてリクエストされたページを終了させることができる。
【００８２】
もし転置手法により検査される要素がページハンドルであれば、このページハンドルは“使用中で非スキャン状態”か“非使用中”でなければならない。なぜなら転置状態の全てのページハンドルは行列の転置フィンガーの古い側にあるからである。また、“使用中でスキャン中”状態はスキャンフィンガーよりも新しく、転置手法では到達できない。もし、検査されるページハンドルが“非使用”状態であれば、転置フィンガーよりも古く、そのヘッドＤＡＢＳフィールドが現行のもっとも新しいＤＡＢＳを参照するようにセットされ、転置状態となるようにセットされる。もし、ページハンドルが“使用中で非スキャン”状態であれば、さらなる処理が必要で、ページハンドルを転置手法から外して、バウンドＤＳＣＯハンドルを発見するように処理は継続できる。このプロセスはスキャニングである。スキャニングはリロケーションと類似しており、ページのメタデータのオブジェクトタッグで全ポインターを発見するようにページでオブジェクトを通して反復するように使用される。リロケーションとは異なり、ポインター値はスキャニングで変化しない。その代わりに、バーチャルアドレスマップにインデックスするのに使用され、ポインターのターゲットに対応するバウンドＤＳＣＯハンドルを発見する。まず、ページハンドル自身が行列のヘッドに移動される。次にスキャニング中にページの各ポインターはバーチャルアドレスマップへのインデックスに使用され、対応するバウンドＤＳＣＯハンドルを発見する。発見された各ＤＳＣＯハンドルは行列のヘッドに移動される。ページがメンバーである領域に対応するＤＳＣＯハンドルも同様に移動される。スキャニングはページハンドルを転置手法から外し、ページハンドルによって必要とされる全ＤＳＣＯハンドルがページハンドルよりも若いという定理を維持する。明らかに移動された全ＤＳＣＯハンドルは現在のアドレススペース生成時に転置により到達しないが、他のバウンドＤＳＣＯハンドルは行列の非スキャンセクションで存在しえる。転置手法は、転置フィンガーよりも直前の若い要素を検査することでその検索を開始する。
【００８３】
もし転置手法で検査される要素がＤＡＢＳであれば、全ての古いＤＡＢＳは転置セクションでのみ存在できるため、それは最も若いＤＡＢＳであるに違いない。このＤＡＢＳは転置フィンガーよりもほんの少々古くなるように移動する。新しい空ＤＡＢＳが創出され、転置対象のページハンドルよりもほんの少々古いスキャンされたセクションの位置でリロプト行列に配置される。転置ＤＡＢＳの次の若いフィールドが新ＤＡＢＳに指向するようにセットされ、その新ＤＡＢＳが最も若くなる。これは新ＤＡＢＳが創出されるか、リロプト行列内で移動される唯一の場合である。ゆえにこの手順自体が唯一のＤＡＢＳが置換フィンガーよりも若いことを保証する。
【００８４】
クライエントアプリケーションによるページのためのリクエストがＶＭＭＤＢのクライエントコンポーネントによってどのように扱われるかの説明に戻る。もしリクエストされたページがクライエントキャッシュ内に既に存在するならば、そのページハンドルは存在し、“非使用”状態であるか転地状態である。ページハンドルは使用状態ではあり得ない。なぜなら、クライエントアプリケーションはそのページをリクエストすることはなく、その現状でそのページを使用するだけである。もしページハンドルが“非使用”状態であれば、それはリロプト行列の非スキャンセクション内に存在するに違いない。リロプト行列の位置不変性はこのページのポインターによって必要とされる全ＤＳＣＯハンドルがページよりも若い位置であり、バウンドを必要とすることを保証する。さらに、以前のアドレススペース発生でページ上のポインターの翻訳を提供するためにそれらが最後に使用されて以来、これらＤＳＣＯハンドルは非バウンド状態となることはできなかったからである。なぜなら、ＤＳＣＯハンドルを解く唯一のプロセスは転置プロセスであり、この転置プロセスはまずページハンドル自体を転置したものとしてマークしただろうからである。本発明はこのページの状態を“非使用”から“使用中であるが非スキャン”状態にポインターあるいはマップを審査あるいは翻訳せずに変更する。キャッシュのページの一部をさらなる翻訳連続的アドレススペース発生に使用させる本発明のこの能力は、他の方法に勝る主要な利点である。本発明はさらに、さらに最近に使用されたページとそれより古く使用されたものとの比較で行列内の若い位置のＤＳＣＯハンドルを、ほとんどのクライエントアプリケーションの時間位置特性と共に保持する組織的効果の相互作用により、キャッシュ内のページのこの部分を実質部分とさせる。
【００８５】
クライエントアプリケーションによりリクエストされているページのページハンドルが転置状態であるなら、そのページの一部または全部のポインターは、バーチャルアドレスマップに表出されるバーチャルアドレススペースバインディングの現行セットに関して無効化されるであろう。インバウンドリロケーションとスキャニング同様にフォワードリロケーションはページのメタデータ内のオブジェクトタッグを使用し、ページ内でポインターを配置する。インバウンドリロケーションやスキャニングとは異なり、それらポインターのターゲットはＰＲＭ（インバウンドリロケーションによってのみ使用）からの翻訳あるいはバーチャルアドレスマップ内へのインデックス処理では見つけられない。その代わり、フォワードリロケーションは転置ページ上のポインターの翻訳にＤＡＢＳを使用する。図２５はリロプト行列を示す。ＤＡＢＳの鎖はそのようなページハンドルのヘッドＤＡＢＳポインターと共に開始する。ページで遭遇するそれぞれのポインターに対して、ポインターの値はページハンドルのヘッドＤＡＢＳフィールドにより言及されるＤＡＢＳ内にインデックス処理される。もしＤＡＢＳ内にエントリーが見つかれば、そのエントリーが言及するＤＳＣＯハンドルは３状態の１つでありえる。ＤＳＣＯハンドルは、偶発的ではあるが可能な結果であるが、そのエントリーがＤＡＢＳに加えられる直前にバウンドされた先の同一バーチャルアドレス領域にバウンドが可能である。この場合、ＤＳＣＯハンドルは、転置処理が必要であるかも知れない前述の処理を使用してバウンドされなければならない。ポインターの値は新規にバウンドされたバーチャルアドレススペース領域の開始アドレス、並びにポインターの旧値とＤＡＢＳエントリーに記録された旧バーチャルアドレススペース領域の開始との間の相違にセットされる。ＤＳＣＯハンドルはバウンド状態でもよいが、ＤＡＢＳエントリーで記録されたものとは異なるバーチャルアドレス領域にバウンドされなければならない。この場合、ポインターの値はバウンド領域の開始アドレス、並びにポインターの旧値と、ＤＡＢＳエントリーで記録された旧バーチャルアドレススペース領域の開始との相違にセットされる。全部の場合に、見つけられたＤＳＣＯハンドルは行列のヘッドに移動される。
【００８６】
もしＤＡＢＳがポインターのための適当なエントリーを有していないなら、調べたばかりのＤＡＢＳの次のＤＡＢＳフィールドによって到達された鎖内の次のＤＡＢＳが次にクエリーされる。この処理はＤＳＣＯハンドルが見つかるまで、あるいはＤＡＢＳ鎖の端に到達するまで反復される。もしＤＳＣＯハンドルが見つかれば、それは前述したように処理される。もしＤＡＢＳ鎖の端にＤＳＣＯハンドルを見つけることなく到達すれば、ページハンドルが転置されたときから対応するＤＳＣＯハンドルは転置されてはならない。よって、ページハンドルが置換されたときバウンドされていたのと同じバーチャルアドレススペース領域にまだバウンドされたままである。この場合、ポインターは有効であり、翻訳を必要としない。ＤＳＣＯハンドルはフォワードリロケーション内で異なる場合によって見つけられる他の場合と同様に行列のヘッドまで移動し、位置不変性を保存する。
【００８７】
そのページ上の全ポインターがフォワードリロケーションによって処理された後に、ページハンドルは“使用中及びスキャン”状態にセットされ、ページは適したアドレスにそれをマッピングし、リクエストに適した方法で保護することによりクライエントアプリケーションにアクセス可能になる。
【００８８】
“使用中であるが非スキャン”状態にあるページの修正は特に本発明により扱われる。ページをクライエントアプリケーションで書き込み可能とする前に、移動処理中にページが検査された場合と同様にページはスキャン処理される。このスキャン処理は、現行アドレススペース発生期間の現行バインディングを維持しなければならないバウンドＤＳＣＯハンドルの偶然の脱バインディングを防止するのに必要である。
【００８９】
トランザクションの端部ではないアドレススペース発生の端部でキャッシュの書き込み可能なページは移動フィンガーよりも少々若い位置にページハンドルを移動させる。これは書き込み可能なページが書き込み可能になって以来、新規または異なるポインター値を得たかも知れず、アドレススペース発生中にこれらポインター値のバウンドＤＳＣＯハンドルがそのポジションでページハンドルよりも若いとは限らないという理由により行われる。移動したフィンガーよりも次に若いポジションは、現在バウンド状態であるＤＳＣＯハンドル全てよりも古いことが保証され、ポジション不変条件を満たす。アドレススペース発生中に書き込み可能ページはポジション不変条件を守らなかったかも知れない。全ページは書き込み可能になる前にスキャンセクションに存在するため、移動プロセスが必要なＤＳＣＯハンドルを移動させることで問題を発生させることはまだできない。このことは不変性に対する許容範囲の例外あるいは不変性はスキャンセクションの外部だけで適用できるように書き直しができると考えることが可能である。
【００９０】
説明がまだなされていないタイプのアウトバウンドリロケーションは、変更を含むページのコピーが安全な保管のためにサーバーに戻されなければならないときに常に発生する。この条件は典型的には。トランザクション中に変更されたページのためにトランザクションが実行されるときに生じる。この条件はまた、キャッシュ内でクライエントアプリケーションにより必要とされる、あるいはクライエントアプリケーションが取り戻しを明確にリクエストしたという理由によって、他のページのスペースを創出するために変更ページがトランザクション中にキャッシュから取り戻されたときにも発生する。アウトバウンドリロケーションは他の全形態のリロケーション同様にページのメタデータに記録された対象物タグを使用して実行される。アウトバウンドリロケーションの目的はページのための新ＰＲＭ構築することであり（旧ＰＲＭはインバウンドリロケーションで使用された後に廃棄される）、ページ上のポインターを外部形態に翻訳することである。アウトバウンドリロケーションは４種の異なる状態のいずれかでページハンドルを有したページに対して実行できる。移動した状態のページハンドルを備えたページに対して、アウトバウンドリロケーションはフォワードリロケーションと全く同様にＤＡＲＢチェーンを使用する。アウトバウンドリロケーションで非バウンドＤＳＣＯハンドルはバウンド状態である必要がなく、ＤＳＣＯハンドルはキーの先端に移動する必要がない。ページハンドルを“非使用中”または“使用中でスキャン中”の状態に備えたページに対しては、必要な全部のＤＳＣＯハンドルはポインター値でバーチャルアドレスマップをインデックス処理することで発見できる。なぜなら、全部のそのようなハンドルはバウンド状態でなければならないからである。これらＤＳＣＯハンドルはキーの先頭にまで移動していない。“使用中であるが未スキャン”状態であるページに対しては、全ＤＳＣＯハンドルはポインター値でバーチャルアドレスマップをインデックス処理することで発見できる。しかし、これらＤＳＣＯハンドルはキーの先頭に移動し、そのようなページのアウトバウンドリロケーションにスキャン状態のようにＤＳＣＯハンドルのポジションに同一効果を与えなければならない。ポインターがアウトバウンドリロケーション中に遭遇し、対応するＤＳＣＯハンドルが上述の方法の１つで発見されるたびに、“サンプル”ＰＲＭＥがポインターのために創出され、アウトバウンドリロケーションのために“サンプル”ＰＲＭＥに挿入される。このサンプルＰＲＭＥは図６のＰＲＭＥフィールド１４８の全てを含む。もし同一フィールドを備えたサンプルＰＲＭＥがサンプルＰＲＭＥに既に存在していれば、それが代用として使用される。通常のＰＲＭＥとは違い、サンプルＰＲＭＥは後尾インデックスフィールドをも含む。新サンプルＰＲＭＥが使用されると、先頭インデックスと後尾インデックスの両方は翻訳最中の現行ポインターに言及するようにセットされる。もし存在するサンプルＰＲＭＥが使用されると、ＰＲＭＥの後尾インデックスフィールドにより言及されたポインターのインデックスフィールドは翻訳最中の現行ポインターに言及するようにセットされる。両方の場合に、ＤＳＣＯハンドルにバウンドされている領域の開始バーチャルアドレスは現行ポインターから差し引かれ、ＤＳＣＯハンドルのオフセットがポインターに加算され、現行ポインターのインデックスフィールド１５０は０にセットされる。サンプルＰＲＭＥの後尾インデックスフィールドを使用する効果は、適した順序で先頭インデックスフィールドから開始して、ポインターの必要な縫合リストを作成することである。
【００９１】
ポインターが上述のようにアウトバウンドリロケーションによって翻訳されると、サンプルＰＲＭはデータベース、セグメント及びクラスターに選別される。選別された配列は順番に審査され、配列内において先行ＰＲＭＥで過剰となったフィールドを排除することでページの新規でコンパクトなＰＲＭが造りだされる。続いてＰＲＭはページのメタデータ内に置かれ、サーバーにページ（またはページのコピー）と共に送られる（ページがトランザクションコミットのためにアウトバウンドリロケーションされているだけなら、クライエントはキャッシュのコピーを維持する）。
【００９２】
削除フィンガーの機能はガベージ回収機構と同じである。クライエントアプリケーションは、リロプトキューにより管理されている要素のメモリーオーバーヘッドは、使用中のページの有効性を保存するのに必要でない限り、特定の閾値を超えるべきではない。リロプトキューのエレメントの創出時にメモリー消費がモニターされる。メモリー消費が設定閾値に到達すると、本発明は削除フィンガーの隣のエレメント（古いエレメントがないため、削除フィンガーより若い）を検査する。もしこのエレメントがＤＳＣＯハンドルまたはＤＡＢＳであればそのエレメントは削除される。もしそのエレメントがページハンドルであれば、対応ページはキャッシュから取り戻され、ページハンドルは削除される。もしそのエレメントが移動フィンガーであれば、いくらかの他のエレメントが削除フィンガーの隣に現れるまで移動プロセスが実行される。もし移動フィンガーがスキャンされたフィンガーの隣に既に存在すれば、移動プロセスが実行されず、削除プロセスは継続できない。もし、移動プロセスの実行で削除フィンガーの隣に現れる移動フィンガー以外のエレメントが出現すれば、削除プロセスがそのエレメントに対して実行可能である。削除プロセスは、リロプトキューエレメントにより消費されたメモリー量が設定閾値以下に降下するか、削除、移動およびスキャンフィンガー全てがリロプトキューに隣接して表れるまで継続する。
【００９３】
アドレススペース発生の終結はグローバルアドレススペース発生カウンターを増加させ（前述のようにオーバーフローの是正による）、脱マッピングまたは保護によって全ページをクライエントアプリケーションにアクセス不能にする。読み取り可能なページは読み取れないようになり、書き込み可能なページは書き込めないようになる。しかし、アドレスバインディングはタッチされない。すなわち、バーチャルアドレスマップは全バウンドＤＳＣＯハンドル同様に変更されない。
【００９４】
本発明の改良形態はネストアドレススペース発生の特徴を加える。これらネストアドレススペース発生はクライエントアプリケーションで開始および停止する。ネストアドレススペース発生の目的はクライエントアプリケーションに、外部アドレススペース発生中に仕事がさらなるアドレススペースを消費するかも知れないことを明記させることである。これは仕事が終了すれば不要なものである。このような仕事は任意にネストできるので、本発明の改良形態はアドレススペース発生の対応する任意ネストを可能にする。次の外側アドレススペース発生が効果を有しているときにネストアドレススペース発生が終了すると、ネスト発生中に加えられたバインディングは将来のバインディングで使用するために必要に応じて交換できる。
【００９５】
基本形態と改良形態との間の最大の相違は、改良形態が複数の挿入フィンガーを有しており、１つだけが行列の先頭に固定されていることである。また、挿入フィンガーは移動フィンガーの若い方にいつでも現れることができる。スキャンフィンガーの若い方の挿入フィンガーは活性であると考えられ、スキャンフィンガーの古いほうの挿入フィンガーは不活性であると考えられる。挿入フィンガーのフラッグは活性/不活性状態をモニターする。それは新挿入フィンガーに対して当初は活性であり、対応するネストアドレススペース発生が終了すると不活性になる。改良形態にはグローバルアドレススペース発生カウンターは存在しない。アドレススペース発生フィールドの代わりに、各ページハンドルは挿入フィンガーを参照する挿入フィンガーフィールドを有するか、何も有しない。ページハンドルの“使用中”指定は挿入フィンガーフィールドの検査によって決定される。フィールドが存在しなければ、ページハンドルは使用中ではない。フィールドが無状態でなく、参照された挿入フィンガーが現行のものであればページハンドルは使用中である。その後、ページハンドルは最内側の活性ネストアドレススペース発生のため、挿入フィンガーフィールドを挿入フィンガーに言及するようにセットすることで使用される。モジュラスフィンガーは改良形態には不要である。
【００９６】
ページハンドルの移動で挿入フィンガーフィールドは存在しないアドレススペース発生フィールドをセットする代わりに無にセットされる。移動プロセスが挿入フィンガーと遭遇すると、挿入フィンガーは削除される。よって、リロプト行列内の挿入フィンガー数はバウンドされることなく増加することはない。不活性挿入フィンガーの早めの削除は基準計数プロセスによって可能である。
【００９７】
ネストまたは外側のアドレススペース発生が終了すると、スキャンフィンガーは終了するアドレススペース発生に対応する挿入フィンガーよりも少々若い位置に移動する。ネストまたは外側のアドレススペース発生が開始すると、新スキャンフィンガーが創出され、スキャンフィンガーより若い隣の位置でリロプト行列に挿入される。挿入フィンガーはこのネストレベルを示すフィールドを有している。これは、新挿入フィンガーが創出されたとき最内側ネスト活性挿入フィンガーのネストレベルよりも大きい。最外側のレベルを０とする。よって、連続的なネストアドレススペース発生は連続的な高ネストレベルを備えた連続的な古い挿入フィンガーに対応するであろう。活性挿入フィンガー間のリロプトキーのセクションはマルチスキャンセクションと呼称される。挿入よりも若い活性挿入フィンガーはセクションのオーナーであると考えられる。
【００９８】
挿入フィンガーフィールドもＤＳＣＯハンドルに追加される。このフィールドは、ＤＳＣＯハンドルを移動させる操作中にＤＳＣＯハンドルが移動する先である挿入フィンガーにセットされる。
【００９９】
ページまたはＤＳＣＯハンドルのネストレベルを挿入フィンガーフィールドの検査で決定させる。フィールドが無状態であれば、あるいは不活性挿入フィンガーに言及していれば、ネストフィンガーレベルは正の無限であると考えられる。さもないと、ネストレベルは基準活性挿入フィンガーのものであると考えられる。ページまたはＤＳＣＯハンドルのネストレベルは新不変性（ページまたはＤＳＣＯハンドルは、現在のネストレベルよりも高いネストレベルを受領する領域には決して移動しない）の保証に使用される。よって、リロケーションまたはスキャニングの最中に、ＤＳＣＯハンドルを移動させるとき、現在のＤＳＣＯハンドルのリロケーションレベルは移動前に検査され、ＤＳＣＯハンドルは移動前に検査され、ＤＳＣＯハンドルは移動先の挿入フィンガーがＤＳＣＯハンドルのネストレベル以下のレベルを有するなら、ＤＳＣＯハンドルは移動されるだけである。
【０１００】
トランザクションの最中には常に１つの最内側アドレススペース発生が存在する。これがどの挿入フィンガーであるかにもよるが、対応する１つの最内側活性挿入フィンガーはアドレススペース発生が開始または終了するときに変化する。１つのグローバル可変は現行の最内側活性挿入フィンガーをモニターする。ページハンドルと基本バージョンのＤＳＣＯハンドルの動作は是正され、動作が常にこの挿入フィンガーよりも少々古い位置でリロプト行列への挿入が得られ、ページまたはＤＳＣＯハンドルの挿入フィンガーはこの挿入フィンガーに言及するようにセットされる。
【０１０１】
アドレススペースが終了すると、対応する挿入フィンガーの状態は活性にセットされ、スキャンフィンガーは隣の若い位置に移動される。アドレススペース発生は最内側から最外側の順番に終了しなければならず、スキャンフィンガーは活性挿入フィンガーよりも若い位置に移動することはない。アドレススペース発生が終了すると、対応挿入フィンガーとそのスキャンセクションの内容はスキャンフィンガーのこの移動によって非スキャンセクションの要素になる。よって、これら要素はずれ易く、活性挿入フィンガーのスキャンセクションにまだ存在する要素よりも早くずれ易い。このずれ易さはクライエントアプリケーションに可視であるネスト現象を提供する。
【０１０２】
上記の実施例は、単に本発明の要旨を示したに過ぎないものである。本発明の要旨に沿った変更は当業者にとって可能であり、それらも本発明の範囲内のものである。
【０１０３】
【図面の簡単な説明】
図１は本願発明が利用される典型的な分散データベースシステムのブロック図である。
図２は図１のシステムの一部の詳細なブロック図であり、サーバーコンピュータとクライエントコンピュータでの別々のデータレポジトリを有している。
図３はシステムの一部のさらに詳細なブロック図であり、１つのコンピュータにデータとクライエントの永久レポジトリを有している。
図４は本願発明のシステムがコンピュータの他のプロセスと相互作用する様子を示す。
図５はデータの永久レポジトリの図であり、データベース、セグメント、クラスター、及びページへの分割を図示している。
図６はパーシステントリロケーションマップと関連データベースページとの図である。
図７はさらに詳細なメモリ図であり、データベースに保存されたクラスターのデータ構造を示している。
図８Ａから８Ｃは３つの異なるオブジェクトタッグのデータ構造を示す図である。
図９はスキーマのためのデータ構造を示す図である。
図１０は図９のスキーマへのタイプエントリーのデータ構造を示す図である。
図１１はタイプデスクリプションディクショナリエントリーのインストラクション用データ構造の図である。
図１２はクライエントキャッシュのモニターのためのクライエントコンピュータのデータ構造の図である。
図１３はデータベースページのオーナーシップステータスをモニターするためのサーバーコンピュータのデータ構造の図である。
図１４はデータベースセグメントに対するバーチャルアドレススペースの指定を示す図である。
図１５はバーチャルメモリ（キャッシュのバーチャルアドレスの物理的アドレス）へのマッピングデータを示す図である。
図１６Ａ図１６Ｃはキャッシュディレクトリと、バーチャルメモリマップと、バーチャルアドレスマップとの間の関係を示す図である。
図１７はバーチャルアドレスへのレジスタンスアドレスのリロケーション方法を示す図である。
図１８はバーチャルアドレスへのパーシステントアドレスのマッピングの詳細図である。
図１９は本願発明の原理に従った第１リロプト行列(relopt queue)である。
図２０は本願発明の原理に従ったｔ0での第２リロプト行列である。
図２１はデータの第１ページのインバウンドリロケーション後の図２０のリロプト行列である。
図２２はデータの第２ページのインバウンドリロケーション後の図２１のリロプト行列である。
図２３は本願発明の原理に従ったＰＳＲスペースの図である。
図２４はトランザクション後の図２２のリロプト行列である。
図２５は本願発明の原理に従ったキュー要素間の鎖ＤＡＢＳ構造を有した第３リロプト行列である。