(57)【特許請求の範囲】
【請求項１】
待ち行列に対する複数のメッセージを大規模トランザクションデータ構造内に格納するステップであって、前記大規模トランザクションデータ構造は、前記待ち行列に対する待ち行列データ構造とは別であるステップ；
前記メッセージと関係付けられる大規模トランザクションをコミットするステップ；および、
連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すステップ；を含み、
前記大規模トランザクションをコミットするステップは、前記待ち行列データ構造内の間接メッセージ内に、前記大規模トランザクションデータ構造へのポインタを格納するステップを含む、
方法。
【請求項２】
連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すステップは、前記大規模トランザクションデータ構造から前記メッセージの少なくとも幾つかを読み出すステップを含む、請求項１の方法。
【請求項３】
連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すステップは、前記待ち行列データ構造から前記メッセージの少なくとも幾つかを読み出すステップを含む、請求項１の方法。
【請求項４】
前記待ち行列データ構造は不揮発性メモリ内に格納される、請求項１の方法。
【請求項５】
前記大規模トランザクションデータ構造から第３データ構造へ前記メッセージを移動するステップ；および、
前記待ち行列データ構造内に、前記第３データ構造を指すポインタを格納するステップ；を更に含む、請求項１の方法。
【請求項６】
連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すステップは、前記第３データ構造から前記メッセージの少なくとも幾つかを読み出すステップを含む、請求項５の方法。
【請求項７】
コンピュータ可読媒体上に格納されるソフトウエアであって：
待ち行列に対する複数のメッセージを大規模トランザクションデータ構造内に格納するステップであって、前記大規模トランザクションデータ構造は、前記待ち行列に対する待ち行列データ構造とは別であるステップ；
前記メッセージと関係付けられる大規模トランザクションをコミットするステップ；および、
連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すステップ；をコンピューターシステムに実行させるための命令を含み、
前記大規模トランザクションをコミットするステップは、前記待ち行列データ構造内の間接メッセージ内に、前記大規模トランザクションデータ構造へのポインタを格納するステップを含む、
ソフトウエア。
【請求項８】
待ち行列に対する複数のメッセージを大規模トランザクションデータ構造内に格納するための手段であって、前記大規模トランザクションデータ構造は、前記待ち行列に対する待ち行列データ構造とは別である手段；
前記メッセージと関係付けられる大規模トランザクションをコミットするための手段；および、
連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すための手段；を含み、
前記大規模トランザクションをコミットすることは、前記待ち行列データ構造内の間接メッセージ内に、前記大規模トランザクションデータ構造へのポインタを格納することを含む、
システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッセージ待ち行列の管理に関する。
【背景技術】
【０００２】
メッセージ待ち行列を用いて、アクセスエンティティ（例えば、サーバ、オペレーティングシステム、ソフトウエアモジュール等）がメッセージを交換するための非同期通信プロトコルを提供することができる。メッセージ待ち行列上に置かれたメッセージは、受信者（例えば、メッセージ待ち行列の契約者）がそのメッセージを取り出すまで、待ち行列データ構造内に格納される。
【０００３】
メッセージ待ち行列システムは、システム欠陥が起きてもメッセージが失われない（または、どの失われたメッセージも復元できる）のを保証する「永続性」を提供できる。永続性を達成する一方法は、揮発性メモリに格納されるメッセージを、例えば、入ってくるメッセージまたはデータのバイトを所与の数だけ受信した後、不揮発性メモリと同期させることである。
【発明の開示】
【課題を解決するための手段】
【０００４】
一般的な態様では、本発明は、複数の待ち行列へデータを書き込むための方法、ならびに対応するソフトウエアおよびシステムを特徴とし、データのそれぞれの部分は、待ち行列の内の対応する一つへ書き込まれる。本方法は、二つ以上の待ち行列を同時にロックする必要なく、データの対応する部分を書き込むための空間が、それぞれの待ち行列内で利用できるかどうかを判定し、利用できる場合は、待ち行列内にその空間を予約するステップを含む。本方法は、待ち行列の内の対応する一つへそれぞれのデータ部分を書き込むステップを含む。
【０００５】
本態様は、下記の特徴の内の一つ以上を含むことができる。
【０００６】
それぞれのデータ部分を待ち行列の内の対応する一つへ書き込むステップは、待ち行列内の全ての空間を予約したステップの後に行われる。
【０００７】
本方法は、データ部分を対応する待ち行列へ書き込むステップの後、その待ち行列内に書き込まれたデータ部分に対する空間の予約を解放するステップを更に含む。
【０００８】
空間がそれぞれの待ち行列内で利用できるかどうかを判定し、利用できる場合、空間を予約するステップが、多数の待ち行列のそれぞれに対して：待ち行列をロックするステップ；空間が待ち行列内で利用できるかどうかを判定するステップ；利用できる場合、空間を予約するステップ；および待ち行列のロックを外すステップ；を含む。
【０００９】
待ち行列の内の対応する一つへ書き込まれたデータ部分のそれぞれは、レコードを含む。
【００１０】
本方法は、ジャーナルレコードを書き込んでから、何れかの待ち行列へレコードを書き込むステップを更に含む。
【００１１】
本方法は、待ち行列のそれぞれを不揮発性メモリと同期してから、ジャーナルレコードを書き込むステップを更に含む。
【００１２】
本方法は、レコードの内の一つ以外の他のデータを待ち行列の内の第１のものに書き込む前に、空間が第１待ち行列内に予約されていれば、第１待ち行列をロックし、その一方で、他のデータのために第１待ち行列内の追加の空間が利用可能かどうかを判定してから、他のデータを第１待ち行列へ書き込むステップを更に含む。
【００１３】
本方法は、レコードの内の一つ以外の他のデータを待ち行列の内の第１のものに書き込む前に、空間が第１待ち行列内にまだ予約されていなければ、第１待ち行列を必ずしもロックする必要なく、第１待ち行列へデータを書き込むステップを更に含む。
【００１４】
それぞれの待ち行列内で、データの対応する部分を書き込むための空間が利用できるかどうかを判定するステップは、待ち行列との何らかの未解決トランザクションに対するコミットレコードを書き込むために十分な空間が、それぞれの待ち行列内で利用できる、ということを確実にするステップを含む。
【００１５】
本方法は、待ち行列との何らかの未解決トランザクションに対するコミットレコードを書き込むために十分な空間が、待ち行列の少なくとも一つに予約されないと判定した後、対応するコミットレコードを複数の待ち行列のそれぞれへ書き込むのを中断するステップを含む。
【００１６】
待ち行列内に空間を予約するステップは、それぞれの待ち行列に対応するカウンタをインクリメントするステップを含む。
【００１７】
別の一般的な態様では、本発明は、待ち行列に対する第２データ構造とは別の第１データ構造内に、待ち行列に対する複数のメッセージを格納するステップ；メッセージと関係付けられるトランザクションをコミットするステップ；および連続メモリ場所から少なくとも幾つかのメッセージを読み出すステップを含む方法、ならびに対応するソフトウエアおよびシステムを特徴とする。
【００１８】
本態様は、一つ以上の下記特徴を含むことができる。
【００１９】
本方法は、第１データ構造を指すポインタを第２データ構造内に格納するステップを更に含む。
【００２０】
連続メモリ場所から少なくとも幾つかのメッセージを読み出すステップは、第１データ構造から少なくとも幾つかのメッセージを読み出すステップを含む。
【００２１】
トランザクションをコミットするステップは、第１データ構造から第２データ構造へメッセージを移動するステップを含む。
【００２２】
連続メモリ場所から少なくとも幾つかのメッセージを読み出すステップは、第２データ構造から少なくとも幾つかのメッセージを読み出すステップを含む。
【００２３】
第１データ構造は揮発性メモリ内に格納され、第２データ構造は不揮発性メモリ内に格納される。
【００２４】
本方法は、メッセージを第１データ構造から第３データ構造へ移動するステップ；および第３データ構造を指すポインタを第２データ構造内に格納するステップを更に含む。
【００２５】
連続メモリ場所から少なくとも幾つかのメッセージを読み出すステップは、第３データ構造から少なくとも幾つかのメッセージを読み出すステップを含む。
【００２６】
本発明の態様は、下記利点の内の一つ以上を含むことができる。
【００２７】
複合コミット動作が、複数の待ち行列のそれぞれへのレコードの書き込み成功を、二つ以上の待ち行列の同時ロックを必要とせずに保証するので、演算リソースの利用率が増加する。大規模書き込みトランザクションにおいて別のデータ構造へメッセージを書き込むと、他のメッセージを読み出す場合に、大規模書き込みトランザクションのレコードをスキャンする必要がなくなる。書き込みトランザクションにおいて別のデータ構造または書き込みバッファへメッセージを書き込んでから、それらを待ち行列へ追加すると、書き込みトランザクションにおいてそれらのメッセージとインターリーブされる他のメッセージの数が減少し、入力／出力（Ｉ／Ｏ）の効率が向上する。
【００２８】
本発明の他の特徴および利点は、下記説明、およびクレームにより明らかになる。
【図面の簡単な説明】
【００２９】
【図１Ａ】待ち行列システムの図である。
【図１Ｂ】待ち行列データ構造の図である。
【図２Ａ】書き込みバッファおよび待ち行列データ構造の図である。
【図２Ｂ】書き込みバッファおよび待ち行列データ構造の図である。
【図２Ｃ】書き込みバッファおよび待ち行列データ構造の図である。
【図２Ｄ】書き込みバッファおよび待ち行列データ構造の図である。
【図２Ｅ】書き込みバッファおよび待ち行列データ構造の図である。
【図３Ａ】書き込みバッファおよび二つの待ち行列データ構造の図である。
【図３Ｂ】書き込みバッファおよび二つの待ち行列データ構造の図である。
【図４】待ち行列データ構造および対応する読み出しデータ構造の図である。
【図５】待ち行列データ構造および大規模トランザクションデータ構造の図である。
【図６】複合コミット動作の一部である待ち行列データ構造の図である。
【図７】複合コミット動作のフロー図である。
【図８Ａ】オープン動作のフロー図である。
【図８Ｂ】複合コミット動作および関係する書き込み動作それぞれのフロー図である。
【図８Ｃ】複合コミット動作および関係する書き込み動作それぞれのフロー図である。
【図９Ａ】複合コミット動作および関係する書き込み動作それぞれのフロー図である。
【図９Ｂ】複合コミット動作および関係する書き込み動作それぞれのフロー図である。
【発明を実施するための形態】
【００３０】
１  概観
図１Ａは、一セットの信頼済みアクセスエンティティ１０２Ａ〜１０２Ｍそれぞれが、待ち行列マネージャ１０６と直接相互作用するための待ち行列トランザクションモジュール１０４を備える待ち行列システム１００を示す。待ち行列システム１００は、一セットの未信頼アクセスエンティティ１０８Ａ〜１０８Ｎをも含み、それぞれのエンティティは、リモート手順呼出し（ＲＰＣ）マネージャ１１２を通じて待ち行列マネージャ１０６と相互作用するための、リモート待ち行列トランザクションモジュール１１０を含む。
【００３１】
待ち行列システム１００は、一つ以上のメッセージ待ち行列を通じて、アクセスエンティティ間でメッセージを渡すためのメカニズムを提供する。アクセスエンティティは、モジュールが待ち行列システム１００と相互作用するためのインターフェースを提供する。例えば、分散演算システム内の「発行者」演算モジュールは、処理されたデータ要素を含むメッセージを、一つ以上の「契約者」演算モジュールへ渡すことができる。
【００３２】
待ち行列マネージャ１０６は、一セットのメッセージ待ち行列に対するメモリ格納を管理する入力／出力（Ｉ／Ｏ）マネージャ１１４と相互作用し、そのメッセージ待ち行列は、対応する待ち行列データ構造QUEUE_A〜QUEUE_Pを有し、この待ち行列データ構造はそれぞれ、揮発性メモリ格納１１８（半導体ランダムアクセスメモリ（ＲＡＭ）等）内の格納空間（例えば、一セットのディスクページ）を割り当てられ、揮発性メモリ格納は、データの読み出しおよび書き込みについて比較的高速のアクセスを提供する一時的作業の格納である。Ｉ／Ｏマネージャ１１４は、揮発性メモリ格納よりデータの永続性が比較的高い恒久的格納であり、読み出しおよび書き込みのアクセスが比較的低速な不揮発性メモリ格納１１６（磁気ディスクシステム等）も管理する。オプションとして、全ての待ち行列に対するＩ／Ｏを扱う単一Ｉ／Ｏマネージャがあり、または待ち行列のサブセットに対するＩ／Ｏをそれぞれが扱う並列に実行されるマルチＩ／Ｏマネージャがある。
【００３３】
待ち行列データ構造は、配布中のデータメッセージを含む「メッセージレコード」（単に「メッセージ」とも称する）、および待ち行列システム１００が待ち行列を管理するのに用いる情報を含む「制御レコード」を含むレコードを格納する。図１Ｂは、メッセージヘッダ１３０およびメッセージデータ１３２をそれぞれが含む一連のメッセージレコードを含む例示の待ち行列データ構造QUEUE_Mを示す。待ち行列は、オプションで、メッセージヘッダ１３０を伴うメッセージデータを格納でき、または代替として、外部に格納したメッセージデータ１３６のアドレスを規定するメッセージヘッダ１３０を伴うポインタ１３４を格納できる。後述の「大規模トランザクション間接技法」では、レコードは、メッセージシーケンスを格納する大規模トランザクションデータ構造１２２を指すポインタ１３８をオプションで含むことができる。
【００３４】
待ち行列システム１００は、発行者−契約者データ配布モデルを含む各種のデータ配布モデルをサポートする。待ち行列に対して「発行者」として作用するアクセスエンティティ（信頼済みまたは未信頼のエンティティ）は、「書き込みトランザクション」内の待ち行列（トピックとも称する）へ一つ以上のメッセージを追加することができる。待ち行列に対して「契約者」として働くアクセスエンティティ（信頼済みまたは未信頼のエンティティ）は、「読み出しトランザクション」内の待ち行列から一つ以上のメッセージを読み出すことができる。複数の発行者が、同一待ち行列へメッセージを追加することができ、複数の契約者が、同一待ち行列から同一メッセージを読み出すことができる。待ち行列マネージャ１０６は、待ち行列に対する全ての契約者がメッセージを読み出した後、その待ち行列からメッセージを削除する。代替として、ポイント対ポイントのデータ配布モデルでは、多数のアクセスエンティティが待ち行列へメッセージを追加できるが、それぞれのメッセージは単一のアクセスエンティティにより待ち行列から読み出される。「複合トランザクション」は、詳細に後述するように、二つ以上の待ち行列との相互作用を含む。
【００３５】
本明細書で説明する書き込みトランザクション、読み出しトランザクションおよび複合トランザクションは、原子性（Atomicity）、整合性（Consistency）、分離性（Isolation）、および永続性（Durability）の頭字からなる「ＡＣＩＤ」特性の内の一つ以上と調和する方法で実行することができる。
【００３６】
書き込みトランザクションを開始するには、発行者はトランザクション識別子（ＩＤ）を待ち行列マネージャ１０６から取得し、書き込みトランザクションにおいて待ち行列へ追加すべき一つ以上のメッセージを、待ち行列マネージャ１０６へ渡す。追加されたメッセージは、それらが待ち行列へ追加された書き込みトランザクションのトランザクションＩＤと関係付けられる。待ち行列マネージャ１０６は、メッセージをＩ／Ｏマネージャ１１４へ渡して、揮発性メモリ格納１１８へ書き込み、最終的に不揮発性メモリ格納１１６へ書き込む。待ち行列マネージャ１０６およびＩ／Ｏマネージャ１１４が実行する機能の役割分担を代替することができる。
【００３７】
発行者が、書き込みトランザクションにおいて追加すべき全てのメッセージを待ち行列マネージャ１０６に提供した後、発行者は、待ち行列マネージャ１０６に書き込みトランザクションを「コミット」または「ロールバック（元に戻す）」するようリクエストできる。書き込みトランザクションをコミットするためには、待ち行列マネージャ１０６は、不揮発性メモリ内の対応する待ち行列データ構造へ「コミットレコード」を追加する。コミットレコードは、コミット済み書き込みトランザクションのメッセージ（「コミット済みメッセージ」）を契約者へ渡すことができることを示す。書き込みトランザクションをコミットする前に、関係付けられるメッセージを揮発性メモリから不揮発性メモリに確実に同期する（まだ同期されていない場合）ことにより、メッセージを永続性のあるものにする。
【００３８】
待ち行列マネージャ１０６は、ロールバックされた書き込みトランザクションにおけるメッセージを、これらのメッセージが不揮発性メモリと同期されていない場合、破棄する。メッセージが不揮発性メモリと同期されている場合、「ロールバックレコード」を適切な待ち行列データ構造へ書き込んで、そのトランザクションにおけるメッセージはコミットされず、そのメッセージは最終的に破棄することができることを示す。実装によっては、所定の時間（例えば、１時間）が経過した後、書き込みトランザクションがコミットされず、またはロールバックされない場合、待ち行列マネージャ１０６は、オプションで自動的にトランザクションをロールバックして、例えば、これらのトランザクションの蓄積が格納空間を浪費するのを防ぐことができる。
【００３９】
読み出しトランザクションを開始するには、契約者は、トランザクションＩＤを取得し、一つ以上の次の未読メッセージを待ち行列マネージャ１０６から受信する。Ｉ／Ｏマネージャ１１４は、適切な待ち行列データ構造からメッセージを取り出すステップを扱い、待ち行列マネージャ１０６は、それらを契約者へ渡す。コミット済みメッセージだけが契約者へ渡され、コミットされたメッセージはまだコミットされていないメッセージとインターリーブされ得るので、メッセージは、それらが待ち行列データ構造へ書き込まれたのと同一の順序で渡しても、同一の順序で渡さなくてもよい。待ち行列マネージャ１０６は、詳細に後述するように、「読み出しデータ構造」を蓄積することにより、待ち行列内のどのメッセージを契約者へ渡すべきかを判定する。
【００４０】
「複合トランザクション」では、アクセスエンティティは、全てのメッセージが同一トランザクションＩＤと関係付けられる二つ以上の待ち行列へ、書き込みおよび／またはそこから読み出すことができる。複合トランザクションをコミットまたはロールバックすることもできる。複合トランザクションがコミットされると、「複合コミット」動作では、その複合トランザクションにおいてメッセージを書き込まれている待ち行列のそれぞれへ、コミットレコードが追加される。これらの「待ち行列コミットレコード」は、対応するコミット済みメッセージを契約者へ渡すことができることを表すのに用いる。
【００４１】
これらの「待ち行列コミットレコード」を書き込む前に、コミットされている複合トランザクションのトランザクションＩＤを含むジャーナルデータ構造１２４へ、「ジャーナルコミットレコード」を書き込む。ジャーナルコミットレコードは、オプションで、複合トランザクションに参加しているアクセスエンティティおよび関与する待ち行列データ構造のような他の情報も含むことができる。トランザクションに書き込まれるメッセージ全てを永続的に格納するか、またはどれも永続的に格納しないか、の何れかを確実に行う（例えば、追加されたメッセージ全てを、障害が発生するとロールバックする）原子動作として、複合コミット動作を実行する。ジャーナルコミットレコードの書き込みは、複合コミット動作を完了させる原子作用である。ジャーナルコミットレコードが書き込まれた後に障害が起きて、それが待ち行列コミットレコード全てが書き込まれる前であった場合、待ち行列システム１００は、永続的に格納されたジャーナルコミットレコードに基づいて復元でき、残りの待ち行列コミットレコードを書き込む。
【００４２】
Ｉ／Ｏ効率を向上させるために、待ち行列マネージャ１０６は、オプションで、待ち行列データ構造とは別のデータ構造内に、待ち行列に対する新規メッセージを格納することにより、異なるトランザクションからのメッセージのインターリーブを減少させる技法を用いる。例えば、待ち行列システム１００は、この種のメッセージインターリーブを減少させる二つの技法を含む：後述する「書き込みバッファ技法」および「大規模トランザクション間接技法」である。
【００４３】
書き込みバッファ技法では、Ｉ／Ｏマネージャ１１４は、最初に、待ち行列に対する未コミットメッセージを、揮発性メモリ格納１１８内の書き込みバッファ１２０内に一時的に格納する。メッセージと関係付けられる書き込みトランザクションがコミットされたら、それらのメッセージを書き込みバッファ１２０から適切な待ち行列データ構造へ移動する。例えば、書き込みバッファ１２０が一杯か、または所定の時間経過後の場合は、書き込みトランザクションがコミットされる前に、メッセージを書き込みバッファ１２０から適切な待ち行列データ構造へ移動してもよい。代替として、書き込みバッファ１２０を、不揮発性メモリ格納１１６内に格納することができ、それでも同一機能の内の一部を提供できる（例えば、異なるトランザクションからのメッセージのインターリーブを減少させる）。
【００４４】
大規模トランザクション間接技法では、大規模数のメッセージ（例えば、コンピュータ環境の特性に応じて、１０，０００、１００，０００、１，０００，０００等を越える等）を含む書き込みトランザクションは、発行者により「大規模トランザクション」として識別される。待ち行列マネージャ１０６は、大規模トランザクションのメッセージを大規模トランザクションデータ構造（ＬＴＤＳ）１２２内に格納し、ＬＴＤＳ１２２を指すポインタを待ち行列データ構造内に格納する。待ち行列マネージャ１０６は、オプションで、書き込みトランザクション内に所定の数のメッセージを検出したら、書き込みトランザクションを大規模トランザクションへオンザフライで自動的に変換できる。書き込みバッファ技法と大規模トランザクション間接技法はともに、メッセージデータを連続メモリ場所内に格納する可能性を高めて、Ｉ／Ｏ効率を向上させる。
【００４５】
２  メッセージの追加および読み出し
Ｉ／Ｏマネージャ１１４は、不揮発性メモリ１１８内の順序付けられた待ち行列データ構造へメッセージを格納する場合、どの特定の書き込みトランザクションに対するメッセージも、待ち行列マネージャ１０６へ提示された順序で維持する。待ち行列データ構造内に格納されたメッセージの順序は、例えば、現在、待ち行列データ構造の一部となっているディスクページのリンクリストにより判定される。異なる書き込みトランザクションに対するメッセージは、待ち行列データ構造内でインターリーブすることができる。新規の書き込みトランザクションを、前に開始された書き込みトランザクションをコミットした後で開始する場合、新規書き込みトランザクションと関係付けられる全てのメッセージは、前の書き込みトランザクション内のメッセージ全てが待ち行列データ構造内で処理された後に行われる。
【００４６】
契約者は、読み出しトランザクションを開始し、その中で待ち行列から一つ以上のメッセージをリクエストすることができる。契約者が受信するメッセージは、一つの書き込みトランザクションから来ることも、書き込みトランザクションのサブセットから来ることも、または二つ以上の書き込みトランザクションから来ることもある。詳細に後述するように、待ち行列マネージャ１０６は、コミット済み書き込みトランザクションからメッセージを契約者へ渡す。同一の書き込みトランザクション内に書き込まれていたメッセージは、書き込みトランザクションの順序で契約者へ提供される。異なる書き込みトランザクションからのメッセージは、書き込みトランザクションがコミットされた順序で契約者へ提供される。待ち行列の異なる契約者が読み出すメッセージは、これらの契約者が同一順序で見る。
【００４７】
異なる書き込みトランザクションからのメッセージが、待ち行列データ構造内にインターリーブされるという程度にまで、読み出しトランザクションのＩ／Ｏ効率が低下することがある。例えば、待ち行列マネージャ１０６は、メッセージがコミットされたと判断するまで、メッセージを契約者へ渡さない。メッセージおよびそのメッセージと対応するコミットレコードを分離するデータが多いほど、用いられる管理リソース（例えば、メモリ、または読み出し動作）は多くなる。書き込みトランザクションと関係付けられるメッセージ（特に、書き込みトランザクションの最初のメッセージ）は、例えば、メッセージが追加されてから、関係付けられる書き込みトランザクションがコミットされるまでの間に長い時間を要する場合、その書き込みトランザクションに対するコミットレコードと遠く離れていることがある。その時間の間、メッセージは、他のメッセージ（例えば、他の書き込みトランザクションと関係付けられるメッセージ）とインターリーブされる待ち行列データ構造内に格納されることになる。更に、その書き込みトランザクション内のメッセージは、遠く離れたディスクページ上に存在することもある。読み出しトランザクションでは、待ち行列マネージャ１０６は、コミットレコードに対する待ち行列データ構造をスキャンし、その書き込みトランザクションに対するメッセージが格納されるページ全てを遡ってスワップしなければならないことになる。
【００４８】
２．１  書き込みバッファ
図２Ａ〜図２Ｅは、上記に説明した書き込みバッファ技法の例示を実行している間の、書き込みバッファ１２０および待ち行列データ構造QUEUE_Aの状態を示す。書き込みバッファ１２０は、待ち行列レコード（例えば、メッセージレコードおよび書き込みトランザクションの開始を示す「オープン」レコード）に対する一時的な格納である。書き込みバッファ１２０は、対応するトランザクションがコミットされるか、または書き込みバッファ１２０が「一杯」になるまで、レコードを保持する。待ち行列マネージャ１０６は、データの最大量、メッセージの最大数に基づいて、またはデータの量とメッセージの数の組み合わせに基づいて、書き込みバッファ１２０が一杯になる時間を判定できる。本実施例では、説明のために過ぎないが、書き込みバッファ１２０は、最大３つのメッセージを保持する。書き込みバッファ１２０は、メッセージが追加された順序を保存する順序付けデータ構造（例えば、リンクリスト）とともに実装する。書き込みバッファ１２０および待ち行列データ構造QUEUE_Aを、メッセージがリストの底部の「ヘッド」へ追加されるリストとして示す。
【００４９】
図２Ａを参照すると、待ち行列データ構造QUEUE_Aは、書き込みトランザクションＴ１の開始を示す「OPEN T1」レコード、およびトランザクションＴ２の開始を示す「OPEN T2」レコードを保持する。書き込みバッファ１２０は、ヘッダ：「T1:ADD M1」、「T2:ADD M1」、および「T1:ADD M2」を有するメッセージを保持する。各メッセージのメッセージデータも、対応するメッセージヘッダと併せて書き込みバッファ１２０内に格納する。本実施例では、書き込みトランザクションＴ１と関係付けられる二つのメッセージが、書き込みトランザクションＴ２と関係付けられるメッセージとインターリーブされる。これは、例えば、Ｔ１およびＴ２が異なる発行者により同時に書き込まれたためである。
【００５０】
図２Ｂを参照すると、待ち行列マネージャ１０６は、トランザクションＴ１（メッセージヘッダおよび関係付けられるメッセージデータを含む）に対するメッセージＭ１およびＭ２を、QUEUE_Aへ移動し、メッセージを不揮発性メモリへ同期したことを確認した後、書き込みトランザクションＴ１に対するコミット動作を実行する。コミットレコード「COMMITT1」をメッセージの後でQUEUE_Aへ書き込んで、コミット動作を完了させる。Ｔ１メッセージをQUEUE_Aへ移動した後、単一のＴ２メッセージが書き込みバッファ内に残る（Ｔ２はまだコミットされていないので）。
【００５１】
図２Ｃを参照すると、発行者が、新規書き込みトランザクションＴ３を開いて、ヘッダ「T3:ADD M1」および「T3:ADD M2」を有する二つのメッセージを待ち行列へ追加する。両者は、二つの空いているスロットを有する書き込みバッファ１２０内に格納される。次いで、待ち行列マネージャ１０６は、ヘッダ「T2:ADD M1」を有するＴ２の唯一のメッセージＭ１をQUEUE_Aへ移動した後、書き込みトランザクションＴ２に対するコミット動作を実行する。次いで、発行者は、新規の書き込みトランザクションＴ４を開いて、ヘッダ「T4:ADD M1」を有するメッセージを、最後に残っている書き込みバッファ１２０のスロット内の待ち行列へ追加する。書き込みトランザクションＴ１およびＴ２と関係付けられるメッセージは、当初インターリーブされていたが、インターリーブを解かれて、書き込みバッファ１２０からQUEUE_Aへの転送の一部として、待ち行列データ構造QUEUE_A内に連続して格納されている。
【００５２】
図２Ｄを参照して、発行者がＴ４に対する第２メッセージを追加すると、書き込みバッファ１２０が一杯なので、待ち行列マネージャ１０６は、Ｔ３と関係付けられるメッセージを書き込みバッファ１２０からQUEUE_Aへ転送する。この転送は、第２のＴ４メッセージに対して書き込みバッファ１２０内の空間を空ける。このように、書き込みトランザクション内のメッセージは、コミットされる前に書き込みバッファ１２０から転送されることもある。
【００５３】
図２Ｅを参照すると、待ち行列マネージャ１０６は、書き込みトランザクションＴ４に対するコミット動作を実行し、新規のＴ３メッセージを受信し、書き込みトランザクションＴ３に対するコミット動作を実行する。本実施例は、書き込みのバッファ処理がメッセージのインターリーブ（または一時的な断片化）を低減するが、書き込みバッファ１２０が一杯になることにより、書き込みバッファ処理を用いても何らかの一時的な断片化が依然として起きることを示す。代替として、書き込みバッファ１２０が一杯の場合、一つ以上の書き込みトランザクションを大規模トランザクションに変換して、待ち行列データ構造に一時的な断片化を起こさずに、書き込みバッファ１２０内の空間を空けることができる。
【００５４】
実装によっては、それぞれの待ち行列は自身の書き込みバッファを有する。代替として、書き込みバッファ１２０は二つ以上の待ち行列に対するメッセージを保持してもよい。一実施例では、三つの書き込みトランザクションＴ１〜Ｔ４に対するメッセージを二つの待ち行列へ追加する。図３Ａは、書き込みバッファ１２０が一杯の場合（本実施例では、書き込みバッファ１２０が１０個のメッセージを保持する）の、書き込みバッファ１２０および待ち行列データ構造QUEUE_A、QUEUE_Bの状態を示す。図３Ｂは、二つの新規メッセージ（書き込みトランザクションＴ１、Ｔ４に対する）が追加された後の、書き込みバッファ１２０および待ち行列データ構造QUEUE_A、QUEUE_Bの状態を示す。最も古いトランザクションＴ１と関係付けられるメッセージはQUEUE_Aへ転送され、新規メッセージのための書き込みバッファ１２０内の空間が空いている。
【００５５】
２．２  読み出しデータ構造
待ち行列マネージャ１０６は、待ち行列内のメッセージレコードを順次スキャンし、メッセージヘッダだけを読み出して、それぞれのメッセージがどのトランザクションと関係付けられるかを判定することにより読み出しデータ構造を蓄積する。待ち行列マネージャ１０６は、読み出しデータ構造を用いて、多数となる可能性のある書き込みトランザクションの経過を追跡する。それぞれの待ち行列に対して、待ち行列マネージャ１０６は、その待ち行列の各契約者に対する読み出しデータ構造を格納する。
【００５６】
図４は、QUEUE_Aと対応する例示の読み出しデータ構造４００を示す。本実施例では、読み出しデータ構造４００は、先入れ先出し（ＦＩＦＯ）のサブリスト４０１〜４０４の順序付けられたリストを含む。待ち行列マネージャ１０６が、新規書き込みトランザクションと対応するメッセージを見付けるたびに、新規のＦＩＦＯサブリストを、その書き込みトランザクションのトランザクションＩＤにより識別される読み出しデータ構造４００へ追加する。待ち行列マネージャ１０６は、各ＦＩＦＯサブリストへ、対応する書き込みトランザクションと関係付けられるそれぞれのメッセージを指すポインタを、スキャンされる順序で（例えば、待ち行列へ追加した順序で）追加する。
【００５７】
図４に示す待ち行列データ構造QUEUE_Aをスキャンする際には、待ち行列マネージャ１０６は、メッセージＭ１およびＭ２を指すポインタを有する、書き込みトランザクションＴ１に対する第１ＦＩＦＯサブリスト４０１を生成する。待ち行列マネージャ１０６は、メッセージがコミットされたことを確認するまで（すなわち、関係するトランザクションに対するコミットレコードをスキャンするまで）、対応する契約者へ（読み出しトランザクションへ応答して）メッセージを返すのを開始しない。Ｔ１に対するコミットレコードに到達した後、Ｔ１に対するＦＩＦＯサブリスト４０１が完成し、待ち行列マネージャ１０６は、読み出しデータ構造４００を蓄積するのを一時的に停止して、ＦＩＦＯサブリスト４０１内のポインタに基づいて次のメッセージを取り出し、契約者が新規メッセージを請求した場合、そのメッセージを契約者へ渡す。完成したＦＩＦＯサブリスト４０１内の全てのメッセージを契約者へ渡した後、待ち行列マネージャ１０６は、QUEUE_Aのスキャンを再開して、次のＦＩＦＯサブリスト４０２が完成するまで、読み出しデータ構造４００の蓄積を継続する。待ち行列マネージャは、完成したＦＩＦＯサブリストから契約者へメッセージを渡すことと、待ち行列データ構造をスキャンして読み出しデータ構造を蓄積することとを交互に行う。本実施例では、Ｔ４のコミットレコードはＴ３のコミットレコードの前に行われるので、Ｔ３に対するメッセージＭ１〜Ｍ３の前に、Ｔ４に対するメッセージＭ１およびＭ２を契約者へ渡す。代替の実施では、待ち行列マネージャは、完成したＦＩＦＯサブリスト内の全メッセージを契約者へ渡す前に、契約者へメッセージ渡すことから読み出しデータ構造の蓄積へと移行することができる。
【００５８】
それぞれのＦＩＦＯサブリストは、対応する契約者がそのＦＩＦＯサブリスト内の全メッセージを受け取るまで、または待ち行列マネージャ１０６が、対応する書き込みトランザクションはコミットされないと判定する（例えば、ロールバックレコードを読んだ後）まで、維持される。読み出しトランザクションをコミットしてから、契約者がどのメッセージを読み出したかを示すジャーナルデータ構造１２４へコミットレコードを書き込む。待ち行列マネージャ１０６が読み出しデータ構造４００の蓄積を終了した後、読み出しデータ構造４００を、同一契約者に対する同一待ち行列からの次の読み出しトランザクションのために維持する。
【００５９】
２．３  大規模トランザクション間接化
図５を参照して、待ち行列マネージャ１０６が大規模トランザクションＴ２を開くと、待ち行列マネージャ１０６は、不揮発性メモリ格納１１６内に大規模トランザクションデータ構造（ＬＴＤＳ）１２２を配置する。大規模トランザクションのメッセージが到着すると、メッセージの連続リストとしてＬＴＤＳ１２２へ直接書き込まれる。大規模トランザクションがコミットされると、待ち行列マネージャ１０６は、ＬＴＤＳ １２２を閉じ、待ち行列データ構造QUEUE_P内の間接メッセージ５００内にＬＴＤＳ １２２へのポインタを格納する。間接メッセージ５００は、大規模トランザクションＴ２のトランザクションＩＤも含む。
【００６０】
待ち行列マネージャ１０６が、QUEUE_Pに対する読み出しデータ構造を蓄積すると、Ｔ１メッセージは二回スキャンされる。一回目は、読み出しデータ構造のＦＩＦＯサブリストを指すポインタを書き込むとき、もう一回目は、契約者へ返すメッセージを読み出すときである。この二回のスキャンは、大規模トランザクションＴ２の多数のメッセージがQUEUE_P内に格納されるとしたら、非効率であろう。その代わりに、待ち行列マネージャ１０６がQUEUE_Pに対する読み出しデータ構造を蓄積していて、単一の間接メッセージ５００をスキャンする場合、待ち行列マネージャ１０６は、Ｔ２に対するＦＩＦＯサブリストを必ずしも必要とせずに、ＬＴＤＳ１２２からメッセージを契約者へ直接渡すことができる。大規模トランザクションがコミットされていると自動的に指示されるので、どの大規模トランザクションメッセージも、契約者へ渡す前にスキャンする必要はない。また、スキャンの別の機能、異なるトランザクションからのメッセージの「非インターリーブ化」が不要になる。大規模トランザクションＴ２内の全てのメッセージを返した後、待ち行列マネージャ１０６は、待ち行列データ構造へ戻る。
【００６１】
大規模トランザクションは、発行者により選択されるか、または待ち行列によりオンザフライで推定されるオプションとすることができる。
【００６２】
３  複合コミット
複合コミット動作では、待ち行列マネージャ１０６は、複数の待ち行列へ書き込む複合トランザクションの追加メッセージ全てが、確実に、永続的に格納されているようにする。複合コミット動作の一部は、これらの待ち行列へコミットレコードを書き込むステップを含む。一つ以上のアクセスエンティティが待ち行列に同時にアクセスでき、その一方で、アクセスエンティティに複合コミット動作へ干渉させずに、複合コミット動作を実行するメカニズムを提供することが有用である。
【００６３】
待ち行列マネージャ１０６は、ジャーナルデータ構造１２４へジャーナルコミットレコードを書き込むことにより、複合トランザクションのメッセージが永続的に格納されている（すなわち、不揮発性メモリと同期されている）ことを示す。続いて、待ち行列マネージャ１０６は、複合トランザクションにおいてメッセージが書き込まれている待ち行列のそれぞれに、待ち行列コミットレコードを書き込む（例えば、読み出しデータ構造を蓄積するためにコミットレコードに対して待ち行列をスキャンできるように）。待ち行列データ構造には格納空間の制約があるので、複合コミット動作に対するタイムアウト期間内に（例えば、５秒間）、コミットレコードを書き込むのに十分な残り空間を幾つかの待ち行列が持っていない可能性がある。待ち行列データ構造が複合コミット動作の開始時に利用できる空間を持っていたとしても、同時に行われる書き込み動作が、待ち行列コミットレコードが書き込まれる前にその空間を使い切ってしまうこともある。コミットレコードに対する待ち行列内の空間の不足は、メッセージがコミットされていることをジャーナルデータ構造１２４が示すにもかかわらず、契約者にそのメッセージを受信させるための対応コミットレコードが待ち行列内にないので、潜在的な問題となる。
【００６４】
複合コミット動作に対する待ち行列コミットレコード管理の一手法では、待ち行列マネージャ１０６が、コミットレコードを書き込む間、各待ち行列を同時にロックし、コミット動作中に空間が使い尽くされるのを防ぐことにより、待ち行列のそれぞれにコミットレコードのための十分な空間を利用できるのを確実にする。第２、第３の手法では、複合コミット動作を更に効率的に実行するため、待ち行列マネージャ１０６は、二つ以上の待ち行列の同時ロックを必要としないで、複数の待ち行列のそれぞれへのコミットレコードの書き込み成功を保証する方法を用いる。これら３つの各方法については詳細に後述する。
【００６５】
図６を参照すると、待ち行列データ構造QUEUE_AおよびQUEUE_Dは、トランザクションＩＤがＴ１、Ｔ２およびＴ３の複合トランザクションのメッセージならびにトランザクションＩＤがＴ４の書き込みトランザクションを含む。複合トランザクションＴ１はコミットされていて、Ｔ１のコミットレコードは、QUEUE_AおよびQUEUE_Dへ書き込まれている。トランザクションＴ２、Ｔ３およびＴ４はまだコミットされていない。複合トランザクションＴ２に対する複合コミット動作と関係付けられるQUEUE_AおよびQUEUE_Dの動作を、３つの例示の手法それぞれについて下記に説明する。
【００６６】
３．１  第１手法
図７は、コミットレコード書き込み動作７００のフロー図を示す。待ち行列マネージャ１０６は、複合トランザクション内に含まれる各待ち行列をロックする７０２。図６の実施例では、待ち行列マネージャ１０６は、QUEUE_AおよびQUEUE_Dをロックする（例えば、ロックフラグを設定することにより）。このロックは、何らかの他のプロセスが、待ち行列データ構造内の利用できる空間を占有するのを防ぐ。
【００６７】
各待ち行列をロック７０２した後、待ち行列マネージャ１０６は各待ち行列内の利用できる格納空間をチェックする７０４。図６の実施例では、待ち行列データ構造QUEUE_Aは、利用できる格納６００のブロックを有し、待ち行列データ構造QUEUE_Bは、利用できる格納６０２のブロックを有する。待ち行列マネージャ１０６は、各待ち行列内の利用できる空間量を、コミットされる複合トランザクションに対するコミットレコードを書き込むのに用いるであろう空間量と比較する。どの待ち行列も、コミットレコードに確保される利用可能な空間を十分に持たない場合、待ち行列マネージャ１０６は、複合コミット動作を中断する７０６。待ち行列マネージャ１０６は、後で複合コミット動作を試みることができ、および／または一つ以上の待ち行列に対する格納空間の更なる取得を試みることができる。
【００６８】
待ち行列が、コミットレコードに確保される格納空間を十分に持つ場合、待ち行列マネージャ１０６は、それぞれの待ち行列を同期して７０８、揮発性メモリ内に格納されるどのメッセージも不揮発性メモリへ移動したことを確認する。それぞれの待ち行列が同期されてから、待ち行列マネージャ１０６は、コミットレコードをジャーナルデータ構造１２６へ書き込む７１０。ジャーナルコミットレコードを書き込んだ後、待ち行列マネージャ１０６は、それぞれの待ち行列へコミットレコードを書き込む７１２。コミットレコードを待ち行列へ書き込んだ後、待ち行列マネージャ１０６はその待ち行列のロックを外す７１４。
【００６９】
ジャーナルコミットレコードの書き込みは、複合コミット動作を復元可能な時点を定義する原子動作である。待ち行列システム１００が、待ち行列マネージャ１０６がジャーナルコミットレコードを書き込む７１０前に、複合コミット動作中に障害を起こした場合、コミット動作を待ち行列全てに対して中断する（待ち行列の幾つかが不揮発性格納へ同期されていないかもしれず、コミットレコードがどの待ち行列にも書き込まれていないこともあるからである）。待ち行列システム１００が、待ち行列マネージャ１０６がジャーナルコミットレコードを書き込んだ７１０後、複合コミット動作中に障害を起こした場合、コミット動作を、待ち行列全てに対して完了させる（それぞれの待ち行列が不揮発性格納へ同期されていて、コミットレコードをジャーナルコミットレコードから復元できるからである）。
【００７０】
３．２  第２手法
第２手法では、待ち行列マネージャ１０６は、各待ち行列内の利用できる空間量を、コミットされる複合書き込みトランザクションおよび何らかの未解決トランザクションに対するコミットレコードを書き込むのに用いるであろう空間量と比較する（本明細書で使用しているように、「未解決トランザクション」は、複合トランザクションおよび書き込みトランザクションの両方を含む）。待ち行列データ構造QUEUE_Aは、Ｔ２および未解決トランザクションＴ３に対するコミットレコードを書き込むために予約される記憶装置６０４のブロックを含む。待ち行列データ構造QUEUE_Bは、Ｔ２および未解決トランザクションＴ３およびＴ４に対するコミットレコードを書き込むために予約される記憶装置６０６のブロックを含む。
【００７１】
図８Ａは、書き込みトランザクションの開始時に実行される「オープン動作」８００のフロー図を示す。各待ち行列QUEUE_iに対して、待ち行列マネージャ１０６は、コミットレコードが未だ書き込まれていない未解決トランザクションの数Ｔiの経過を追跡する。QUEUE_iに関する新規トランザクションを開き、およびＴiをインクリメントする前に、待ち行列マネージャ１０６は、待ち行列（単純な書き込みトランザクションについては単一の待ち行列、または複合トランザクションにおいてはメッセージが追加されているそれぞれの待ち行列）をロックし８０２、チェックして８０４、「オープンレコード」およびコミットレコードに対する空間が存在するよう確保する。待ち行列マネージャ１０６は、現在利用できる空間を次式により与えられるＤoと比較する：
Ｄo ＝ size_of（１オープンレコード）＋size_of（１コミットレコード）×（Ｔi＋１）
利用できる空間がＤo以上の場合、待ち行列マネージャ１０６は、QUEUE_iのロックを外し８０６、「オープンレコード」を書き込み８０８、未解決トランザクションの数Ｔiをインクリメントする８１０。あるいは、利用できる空間がＤo未満の場合、待ち行列マネージャ１０６は、QUEUE_iのロックを外し８１２、オープン動作８００を中断する８１４。
【００７２】
図８Ｂおよび図８Ｃは、コミットレコード書き込み動作８４０および関係する書き込み動作８５０それぞれのフロー図を示す。待ち行列マネージャ１０６（またはＩ／Ｏマネージャ１１４）は、コミット動作に対するコミットレコード書き込み動作８４０を用いるとともに、書き込み動作８５０を用いて（同時に起きる可能性がある）、待ち行列へコミットレコード以外の何らかのデータを書き込む。この手法では、コミットレコード書き込み動作８４０は、待ち行列内の利用できる空間に対するチェックを必要としない。その理由は、書き込み動作８５０が、待ち行列データ構造へ何らかのデータを書き込む前にこのチェックを含むからである。待ち行列マネージャ１０６は、詳細に後述するように、各待ち行列QUEUE_iが、その待ち行列に対するＴi個の未解決トランザクションそれぞれに対するコミットレコードのための十分な空間予約を確保する。従って、コミットレコード書き込み動作８４０を実行する際、待ち行列マネージャ１０６は、空間が各コミットレコードのために予約されたことを前提とすることができる。
【００７３】
図８Ｂを参照すると、コミットレコード書き込み動作８４０では、待ち行列マネージャ１０６は、最初に各待ち行列を同期させる８４２。各待ち行列を同期させた後、待ち行列マネージャ１０６は、ジャーナルコミットレコードを書き込む８４４。ジャーナルコミットレコードを書き込んだ後、待ち行列マネージャ１０６は各待ち行列へコミットレコードを書き込む８４６。
【００７４】
図８Ｃを参照すると、待ち行列マネージャ１０６は、待ち行列データ構造へ書き込まれるデータに対して書き込み動作８５０を用いる。待ち行列マネージャ１０６は、書き込まれるデータがコミットレコードかどうかを最初に判定する８５２。Ｙｅｓであれば、待ち行列マネージャ１０６は、コミットレコード８５４を書き込み、未解決トランザクションの数Ｔiをデクリメントする８５６。Ｎｏであれば、待ち行列マネージャ１０６は待ち行列をロックし８５８、待ち行列内で利用できる格納空間をチェックする８６０。待ち行列マネージャ１０６は、現在の利用できる空間を次式で与えられるＤWと比較する：
ＤW ＝ size_of（書き込まれるデータ）＋size_of（１コミットレコード）×Ｔi
ここで、size_of（data）は、適切な単位（例えばバイト）のdataのサイズを返す。利用できる空間がＤW以上の場合、待ち行列マネージャ１０６は、データを書き込み８６２、待ち行列のロックを外す８６４。あるいは、利用できる空間がＤW未満の場合、待ち行列マネージャ１０６は、待ち行列のロックを外し８６６、書き込み動作８５０を中断する８６８。本手法では、格納空間をチェックする間、データを書き込む待ち行列である単一の待ち行列だけがロックされる。
【００７５】
３．３  第３手法
図９Ａおよび図９Ｂは、コミットレコード書き込み動作９００および関係する書き込み動作９５０のフロー図を示す。この手法では、待ち行列マネージャ１０６は、書き込みトランザクションの開始時点で図８Ａに示す「オープン動作」８００を用いる。コミットレコード書き込み動作９００および書き込み動作９５０は、ともに待ち行列内の利用できる空間をチェックする。また、本手法では、一度には単一の待ち行列しかロックしない。各待ち行列QUEUE_iに対して、待ち行列マネージャ１０６は、未解決トランザクションの数Ｔiの経過を追跡する（オープン動作８００を用いてＴiをインクリメントする）。待ち行列マネージャ１０６は、Ｔi個の未解決トランザクションのそれぞれに対するコミットレコードのための十分な空間を、それぞれの待ち行列データ構造が予約するのを確実にする。しかし、本手法では、待ち行列マネージャ１０６は、データを待ち行列へ書き込む前に空間をチェックするために、「予約モード」状態にある待ち行列をロックするのみである。予約モードは、全ての参加している待ち行列を同時にはロックせずに、コミット動作が進行状態にあるということを示す方法を提供する。
【００７６】
図９Ａを参照すると、コミットレコード書き込み動作９００では、待ち行列マネージャ１０６は、最初に、コミットレコード書き込み動作９００に含まれる各待ち行列QUEUE_iに対して一回（ｉ＝１の場合．．．動作９００における待ち行列の数）、ループ９０２（または、等価の制御構造）を実行する。ループ９０２は、多数の複合コミット動作が同時に実行される可能性があることを考慮できる方法で、QUEUE_iに対する予約モードをＯＮにする。本実施例では、ループ９０２は、QUEUE_iに対する予約モードカウンタＲiをインクリメントする９０４。予約モードカウンタは、QUEUE_iが予約モード状態にない初期値、例えば、Ｒi＝０、で開始する。Ｒi＞０の場合、QUEUE_iは予約モード状態にある。これにより、待ち行列の予約モード状態が、その待ち行列が予約モードとなった回数に対応するようになる。
【００７７】
予約モードカウンタをインクリメントした後、ループ９０２内で、待ち行列マネージャ１０６はQUEUE_iをロックし９０６、QUEUE_i内で利用できる格納空間をチェックする９０８。待ち行列マネージャ１０６は、現在の利用できる空間を、次式により与えられるＤCと比較する：
ＤC ＝ size_of（１コミットレコード）×Ｔi
利用できる空間がＤC以上の場合、待ち行列マネージャ１０６は、QUEUE_iのロックを外し９１０、継続する。あるいは、利用できる空間がＤC未満の場合、待ち行列マネージャ１０６は、QUEUE_iのロックを外し９１２、コミットレコード書き込み動作９００を中断する９１４。
【００７８】
ループ９０２の後、待ち行列マネージャ１０６は、各待ち行列を同期する９１６。各待ち行列を同期した後、待ち行列マネージャ１０６は、ジャーナルコミットレコードを書き込む９１８。ジャーナルコミットレコードを書き込んだ後、待ち行列マネージャ１０６は、コミットレコードを各待ち行列へ書き込む９２０。コミットレコードを待ち行列へ書き込んだ後、待ち行列マネージャ１０６は、その待ち行列に対する予約モードカウンタをデクリメントする９２２。
【００７９】
図９Ｂを参照すると、待ち行列マネージャ１０６は、待ち行列データ構造へ書き込まれるデータに対する書き込み動作９５０を用いる。待ち行列マネージャ１０６は、最初に、書き込まれるデータがコミットレコードであるかどうかを判定する９５２。Ｙｅｓであれば、待ち行列マネージャ１０６は、コミットレコード９５４を書き込み、未解決トランザクションの数Ｔiをデクリメントする９５６。Ｎｏであれば、待ち行列マネージャ１０６は、待ち行列が予約モード状態かどうかを判定する９５８（例えば、Ｒi＞０かどうかを判定することにより）。待ち行列が予約モード状態にない場合、待ち行列マネージャ１０６は、データを書き込む９６０。待ち行列が予約モード状態の場合、待ち行列マネージャ１０６は待ち行列をロックし９６２、待ち行列内で利用できる格納空間をチェックする９６４。待ち行列マネージャ１０６は、現在の利用できる空間を第２手法について上記で定義したＤWと比較する。利用できる空間がＤW以上の場合、待ち行列マネージャ１０６は、データを書き込み９６６、待ち行列のロックを外す９６８。あるいは、利用できる空間がＤW未満の場合、待ち行列マネージャ１０６は、待ち行列のロックを外し９７０、書き込み動作９５０を中断する９７２。
【００８０】
３．４  他の手法
二つ以上の待ち行列を同時ロックせずに、多数の待ち行列のそれぞれへの、コミットレコードの書き込み成功を保証するコミット動作を管理するための他の手法が可能である。例えば、第３の手法の変形形態では、全ての未解決トランザクションのカウントＴiを用いる代わりに、待ち行列マネージャ１０６は、ＤCおよび／またはＤWの計算に対して予約モードＲi状態の待ち行列の数を用いる。手法によっては、ジャーナルコミットレコードを書き込む前に、待ち行列コミットレコードに対する空間が不足しているためにコミット動作が失敗しても許容される。
【００８１】
４  実装
本明細書で説明した待ち行列管理機能をコンピュータ上で実行するためにソフトウエアを用いて実装することができる。例えば、ソフトウエアは、一台以上のプログラム済みまたはプログラム可能なコンピューターシステム（分散型、クライアント／サーバ型、またはグリッド型等の各種アーキテクチャから構成できる）上で実行される一つ以上のコンピュータープログラム内の手順を形成する。それぞれのコンピューターシステムは、少なくとも一つのプロセッサ、少なくとも一つのデータ格納システム（揮発性メモリおよび不揮発性メモリおよび／または記憶素子を含む）、少なくとも一つの入力装置またはポート、および少なくとも一つの出力装置またはポートを含む。ソフトウエアは、例えば、計算グラフの設計および構成と関連する他のサービスを提供する、規模の大きなプログラムの内の一つ以上のモジュールを形成してもよい。本明細書で説明するデータ構造を、コンピュータ可読媒体内に格納したデータ構造、またはデータ収納庫内に格納したデータモデルへ準拠する他の体系化したデータ、として実装することができる。
【００８２】
本ソフトウエアは、汎用または専用のプログラム可能なコンピュータにより読み込むことができるＣＤ−ＲＯＭのような媒体上で提供するか、またはネットワークを介してソフトウエアが実行される場所であるコンピュータへ配布する（伝搬信号で符号化される）ことができる。機能全てを専用コンピュータ上で、またはコプロセッサ等の専用ハードウエアを用いて、実行することができる。本ソフトウエアは、ソフトウエアにより規定される異なる計算部分を異なるコンピュータで実行する分散型で実装できる。このようなコンピュータープログラムはそれぞれ、格納媒体または汎用もしくは専用のプログラム可能なコンピュータに可読の装置（例えば、固体メモリもしくは媒体、または磁気もしくは光学媒体）に格納するか、ダウンロードして、格納媒体または格納装置をコンピューターシステムが読み出す際に、本明細書で説明した手順を実行するようにコンピュータを構成し、動作させるのが好ましい。本発明のシステムは、コンピュータープログラムで構成されたコンピュータ可読格納媒体として実装し、そのように構成される格納媒体が、コンピューターシステムを規定の方法、所定の方法で動作させて、本明細書で説明した機能を実行させると考えることもできる。
【００８３】
理解すべきは、上記説明が説明を意図していて本発明の範囲を限定する意図はなく、本発明の範囲は、付帯のクレーム範囲により定義されるということである。例えば、上記説明の機能ステップの幾つかは、全体の処理に実質的に影響を与えることなく異なる順序で実行してもよい。他の実施の形態は以下のクレームの範囲内にある。
【図１Ａ】
0005657599.tif 000002
【図１Ｂ】
0005657599.tif 000003
【図２Ａ】
0005657599.tif 000004
【図２Ｂ】
0005657599.tif 000005
【図２Ｃ】
0005657599.tif 000006
【図２Ｄ】
0005657599.tif 000007
【図２Ｅ】
0005657599.tif 000008
【図３Ａ】
0005657599.tif 000009
【図３Ｂ】
0005657599.tif 000010
【図４】
0005657599.tif 000011
【図５】
0005657599.tif 000012
【図６】
0005657599.tif 000013
【図７】
0005657599.tif 000014
【図８Ａ】
0005657599.tif 000015
【図８Ｂ】
0005657599.tif 000016
【図８Ｃ】
0005657599.tif 000017
【図９Ａ】
0005657599.tif 000018
【図９Ｂ】
0005657599.tif 000019