図面 (/)

技術 メッセージ待ち行列の管理

出願人 アビニシオテクノロジーエルエルシー
発明者 ミハイロフスピロバナージサンジーブスタンフィルクレイグダブリュ
出願日 2006年6月22日 (13年5ヶ月経過) 出願番号 2008-519405
公開日 2008年12月25日 (10年10ヶ月経過) 公開番号 2008-547130
状態 特許登録済
技術分野 マルチプログラミング
主要キーワード 残り空間 追加空間 規模数 システム欠陥 非同期通信プロトコル 計算グラフ トランザクションモジュール 待ち行列マネージャ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2008年12月25日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (19)

課題・解決手段

データのそれぞれの部分を待ち行列の内の対応する一つへ書き込む、複数の待ち行列へデータを書き込むための方法、ならびに対応するシステムおよびソフトウエアを説明する。本方法は、二つ以上の待ち行列を同時にロックする必要なく、データの対応する部分を書き込むために利用できる空間が、それぞれの待ち行列にあるかどうかを判定し、利用できる場合は、待ち行列内にその空間を予約するステップを含む。本方法は、待ち行列の内の対応する一つへデータのそれぞれの部分を書き込むステップを含む。

概要

背景

概要

データのそれぞれの部分を待ち行列の内の対応する一つへ書き込む、複数の待ち行列へデータを書き込むための方法、ならびに対応するシステムおよびソフトウエアを説明する。本方法は、二つ以上の待ち行列を同時にロックする必要なく、データの対応する部分を書き込むために利用できる空間が、それぞれの待ち行列にあるかどうかを判定し、利用できる場合は、待ち行列内にその空間を予約するステップを含む。本方法は、待ち行列の内の対応する一つへデータのそれぞれの部分を書き込むステップを含む。

目的

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

複数の待ち行列へデータを書き込むための方法であって、前記データのそれぞれの部分は前記待ち行列の内の対応する一つへ書き込まれ、前記方法は:二つ以上の待ち行列を同時にロックする必要なく、それぞれの待ち行列内に、前記データの対応する部分を書き込むための空間が利用できるかどうかを判定し(902)、利用できる場合は、前記待ち行列内に前記空間を予約するステップ;および、前記データのそれぞれの部分を前記待ち行列の内の対応する一つへ書き込む(920)ステップ;を含む方法。

請求項2

前記データのそれぞれの部分を前記待ち行列の内の対応する一つへ書き込むステップは、前記待ち行列内の前記空間全てを予約した後に行われる、請求項1の方法。

請求項3

前記データの一部を前記対応する待ち行列内に書き込んだ後、その待ち行列内に書き込まれた前記データの一部のための前記空間の前記予約を開放するステップを更に含む、請求項1の方法。

請求項4

それぞれの待ち行列内に前記空間が利用できるかどうかを判定し、利用できる場合は、前記空間を予約するステップは、多数の前記待ち行列のそれぞれに対して:前記待ち行列をロックするステップ;前記空間が前記待ち行列内に利用できるかどうかを判定するステップ;利用できる場合は前記空間を予約するステップ;および、前記待ち行列のロックを外すステップ;を含む、請求項1の方法。

請求項5

前記待ち行列の内の対応する一つへ書き込まれる前記データのそれぞれの部分は、レコードを含む、請求項1の方法。

請求項6

ジャーナルレコードを書き込んでから、前記待ち行列の何れかへ前記レコードを書き込むステップを更に含む、請求項5の方法。

請求項7

前記待ち行列のそれぞれを不揮発性メモリへ同期してから、前記ジャーナルレコードを書き込むステップを更に含む、請求項6の方法。

請求項8

前記待ち行列の内の第1のものへ、前記レコードの内の一つ以外の他のデータを書き込む前に、前記第1待ち行列内に空間が予約されている場合、前記他のデータに対して、前記第1待ち行列内に追加空間が利用できるかどうかを判定する間、前記第1待ち行列をロックしてから、前記他のデータを前記第1待ち行列へ書き込むステップを更に含む、請求項5の方法。

請求項9

前記待ち行列の内の第1のものへ、前記レコードの内の一つ以外の他のデータを書き込む前に、前記第1待ち行列内に空間が未だ予約されていない場合、前記第1待ち行列を必ずしもロックする必要なく、前記データを前記第1待ち行列へ書き込むステップを更に含む、請求項5の方法。

請求項10

それぞれの待ち行列内に、前記データの対応する部分を書き込むための空間が利用できるかどうかを判定するステップは、それぞれの待ち行列内に、前記待ち行列との何れかの未解決トランザクションに対するコミットレコードを書き込むのに十分な空間が利用できることを確実にするステップを含む、請求項1の方法。

請求項11

前記待ち行列の少なくとも一つに、前記待ち行列との何れかの未解決トランザクションに対するコミットレコードを書き込むのに十分な空間が予約されていないと判定した後、前記複数の待ち行列のそれぞれへ前記対応するコミットレコードを書き込むのを中断するステップを更に含む、請求項10の方法。

請求項12

前記待ち行列内に前記空間を予約するステップは、それぞれの待ち行列に対応するカウンタインクリメントするステップを含む、請求項1の方法。

請求項13

複数の待ち行列へデータを書き込むためのコンピュータ可読媒体上に格納されるソフトウエアであって、前記データのそれぞれの部分を前記待ち行列の内の対応する一つへ書き込み、前記ソフトウエアは:二つ以上の待ち行列を同時にロックする必要なく、それぞれの待ち行列内に、前記データの対応する部分を書き込むための空間が利用できるかどうかを判定し(902)、利用できる場合は、前記待ち行列内に前記空間を予約するステップ;および、前記データのそれぞれの部分を前記待ち行列の内の対応する一つへ書き込む(920)ステップ;をコンピューターシステムに実行させるための命令を含むソフトウエア。

請求項14

複数の待ち行列へデータを書き込むためのシステムであって、前記データのそれぞれの部分を前記待ち行列の内の対応する一つへ書き込み、前記システムは:二つ以上の待ち行列を同時にロックする必要なく、それぞれの待ち行列内に、前記データの対応する部分を書き込むための空間が利用できるかどうかを判定し(902)、利用できる場合は、前記待ち行列内に前記空間を予約するための手段;および、前記データのそれぞれの部分を前記待ち行列の内の対応する一つへ書き込む(920)ための手段;を含むシステム。

請求項15

待ち行列に対する複数のメッセージを第1データ構造(122)内に格納するステップであって、前記第1データ構造(122)は、前記待ち行列に対する第2データ構造とは別である;前記メッセージと関係付けられるトランザクションをコミットするステップ;および、連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すステップ;を含む方法。

請求項16

前記第2データ構造内に、前記第1データ構造を指すポインタを格納するステップを更に含む、請求項15の方法。

請求項17

連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すステップは、前記第1データ構造から前記メッセージの少なくとも幾つかを読み出すステップを含む、請求項16の方法。

請求項18

前記トランザクションをコミットするステップは、前記第1データ構造から前記第2データ構造へ前記メッセージを移動するステップを含む、請求項15の方法。

請求項19

連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すステップは、前記第2データ構造から前記メッセージの少なくとも幾つかを読み出すステップを含む、請求項18の方法。

請求項20

前記第1データ構造を揮発性メモリ内に格納し、前記第2データ構造を不揮発性メモリ内に格納する、請求項18の方法。

請求項21

前記第1データ構造から第3データ構造へ前記メッセージを移動するステップ;および、前記第2データ構造内に、前記第3データ構造を指すポインタを格納するステップ;を更に含む、請求項15の方法。

請求項22

連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すステップは、前記第3データ構造から前記メッセージの少なくとも幾つかを読み出すステップを含む、請求項21の方法。

請求項23

コンピュータ可読媒体上に格納されるソフトウエアであって:待ち行列に対する複数のメッセージを第1データ構造(122)内に格納するステップであって、前記第1データ構造(122)は、前記待ち行列に対する第2データ構造とは別である;;前記メッセージと関係付けられるトランザクションをコミットするステップ;および、連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すステップ;をコンピューターシステムに実行させるための命令を含むソフトウエア。

請求項24

待ち行列に対する複数のメッセージを第1データ構造(122)内に格納するための手段であって、前記第1データ構造(122)は、前記待ち行列に対する第2データ構造とは別である;前記メッセージと関係付けられるトランザクションをコミットするための手段;および、連続するメモリ場所から前記メッセージの少なくとも幾つかを読み出すための手段;を含むシステム。

発明の詳細な説明

0001

背景
本発明は、メッセージ待ち行列の管理に関する。

0002

メッセージ待ち行列を用いて、アクセスエンティティ(例えば、サーバオペレーティングシステムソフトウエアモジュール等)がメッセージ交換するための非同期通信プロトコルを提供することができる。メッセージ待ち行列上に置かれたメッセージは、受信者(例えば、メッセージ待ち行列の契約者)がそのメッセージを取り出すまで、待ち行列データ構造内に格納される。

0003

メッセージ待ち行列システムは、システム欠陥が起きてもメッセージが失われない(または、どの失われたメッセージも復元できる)のを保証する「永続性」を提供できる。永続性を達成する一方法は、揮発性メモリに格納されるメッセージを、例えば、入ってくるメッセージまたはデータのバイトを所与の数だけ受信した後、不揮発性メモリと同期させることである。

0004

概要
一般的な態様では、本発明は、複数の待ち行列へデータを書き込むための方法、ならびに対応するソフトウエアおよびシステムを特徴とし、データのそれぞれの部分は、待ち行列の内の対応する一つへ書き込まれる。本方法は、二つ以上の待ち行列を同時にロックする必要なく、データの対応する部分を書き込むための空間が、それぞれの待ち行列内で利用できるかどうかを判定し、利用できる場合は、待ち行列内にその空間を予約するステップを含む。本方法は、待ち行列の内の対応する一つへそれぞれのデータ部分を書き込むステップを含む。

0005

本態様は、下記の特徴の内の一つ以上を含むことができる。

0006

それぞれのデータ部分を待ち行列の内の対応する一つへ書き込むステップは、待ち行列内の全ての空間を予約したステップの後に行われる。

0007

本方法は、データ部分を対応する待ち行列へ書き込むステップの後、その待ち行列内に書き込まれたデータ部分に対する空間の予約を解放するステップを更に含む。

0008

空間がそれぞれの待ち行列内で利用できるかどうかを判定し、利用できる場合、空間を予約するステップが、多数の待ち行列のそれぞれに対して:待ち行列をロックするステップ;空間が待ち行列内で利用できるかどうかを判定するステップ;利用できる場合、空間を予約するステップ;および待ち行列のロックを外すステップ;を含む。

0009

待ち行列の内の対応する一つへ書き込まれたデータ部分のそれぞれは、レコードを含む。

0010

本方法は、ジャーナルレコードを書き込んでから、何れかの待ち行列へレコードを書き込むステップを更に含む。

0011

本方法は、待ち行列のそれぞれを不揮発性メモリと同期してから、ジャーナルレコードを書き込むステップを更に含む。

0012

本方法は、レコードの内の一つ以外の他のデータを待ち行列の内の第1のものに書き込む前に、空間が第1待ち行列内に予約されていれば、第1待ち行列をロックし、その一方で、他のデータのために第1待ち行列内の追加の空間が利用可能かどうかを判定してから、他のデータを第1待ち行列へ書き込むステップを更に含む。

0013

本方法は、レコードの内の一つ以外の他のデータを待ち行列の内の第1のものに書き込む前に、空間が第1待ち行列内にまだ予約されていなければ、第1待ち行列を必ずしもロックする必要なく、第1待ち行列へデータを書き込むステップを更に含む。

0014

それぞれの待ち行列内で、データの対応する部分を書き込むための空間が利用できるかどうかを判定するステップは、待ち行列との何らかの未解決トランザクションに対するコミットレコードを書き込むために十分な空間が、それぞれの待ち行列内で利用できる、ということを確実にするステップを含む。

0015

本方法は、待ち行列との何らかの未解決トランザクションに対するコミットレコードを書き込むために十分な空間が、待ち行列の少なくとも一つに予約されないと判定した後、対応するコミットレコードを複数の待ち行列のそれぞれへ書き込むのを中断するステップを含む。

0016

待ち行列内に空間を予約するステップは、それぞれの待ち行列に対応するカウンタインクリメントするステップを含む。

0017

別の一般的な態様では、本発明は、待ち行列に対する第2データ構造とは別の第1データ構造内に、待ち行列に対する複数のメッセージを格納するステップ;メッセージと関係付けられるトランザクションをコミットするステップ;および連続メモリ場所から少なくとも幾つかのメッセージを読み出すステップを含む方法、ならびに対応するソフトウエアおよびシステムを特徴とする。

0018

本態様は、一つ以上の下記特徴を含むことができる。

0019

本方法は、第1データ構造を指すポインタを第2データ構造内に格納するステップを更に含む。

0020

連続メモリ場所から少なくとも幾つかのメッセージを読み出すステップは、第1データ構造から少なくとも幾つかのメッセージを読み出すステップを含む。

0021

トランザクションをコミットするステップは、第1データ構造から第2データ構造へメッセージを移動するステップを含む。

0022

連続メモリ場所から少なくとも幾つかのメッセージを読み出すステップは、第2データ構造から少なくとも幾つかのメッセージを読み出すステップを含む。

0023

第1データ構造は揮発性メモリ内に格納され、第2データ構造は不揮発性メモリ内に格納される。

0024

本方法は、メッセージを第1データ構造から第3データ構造へ移動するステップ;および第3データ構造を指すポインタを第2データ構造内に格納するステップを更に含む。

0025

連続メモリ場所から少なくとも幾つかのメッセージを読み出すステップは、第3データ構造から少なくとも幾つかのメッセージを読み出すステップを含む。

0026

本発明の態様は、下記利点の内の一つ以上を含むことができる。

0027

複合コミット動作が、複数の待ち行列のそれぞれへのレコードの書き込み成功を、二つ以上の待ち行列の同時ロックを必要とせずに保証するので、演算リソース利用率が増加する。大規模書き込みトランザクションにおいて別のデータ構造へメッセージを書き込むと、他のメッセージを読み出す場合に、大規模書き込みトランザクションのレコードをスキャンする必要がなくなる。書き込みトランザクションにおいて別のデータ構造または書き込みバッファへメッセージを書き込んでから、それらを待ち行列へ追加すると、書き込みトランザクションにおいてそれらのメッセージとインターリーブされる他のメッセージの数が減少し、入力/出力(I/O)の効率が向上する。

0028

本発明の他の特徴および利点は、下記説明、およびクレームにより明らかになる。

0029

説明
概観
図1Aは、一セット信頼済みアクセスエンティティ102A〜102Mそれぞれが、待ち行列マネージャ106と直接相互作用するための待ち行列トランザクションモジュール104を備える待ち行列システム100を示す。待ち行列システム100は、一セットの未信頼アクセスエンティティ108A〜108Nをも含み、それぞれのエンティティは、リモート順呼出し(RPC)マネージャ112を通じて待ち行列マネージャ106と相互作用するための、リモート待ち行列トランザクションモジュール110を含む。

0030

待ち行列システム100は、一つ以上のメッセージ待ち行列を通じて、アクセスエンティティ間でメッセージを渡すためのメカニズムを提供する。アクセスエンティティは、モジュールが待ち行列システム100と相互作用するためのインターフェースを提供する。例えば、分散演算システム内の「発行者演算モジュールは、処理されたデータ要素を含むメッセージを、一つ以上の「契約者」演算モジュールへ渡すことができる。

0031

待ち行列マネージャ106は、一セットのメッセージ待ち行列に対するメモリ格納を管理する入力/出力(I/O)マネージャ114と相互作用し、そのメッセージ待ち行列は、対応する待ち行列データ構造QUEUE_A〜QUEUE_Pを有し、この待ち行列データ構造はそれぞれ、揮発性メモリ格納118(半導体ランダムアクセスメモリ(RAM)等)内の格納空間(例えば、一セットのディスクページ)を割り当てられ、揮発性メモリ格納は、データの読み出しおよび書き込みについて比較的高速アクセスを提供する一時的作業の格納である。I/Oマネージャ114は、揮発性メモリ格納よりデータの永続性が比較的高い恒久的格納であり、読み出しおよび書き込みのアクセスが比較的低速な不揮発性メモリ格納116(磁気ディスクシステム等)も管理する。オプションとして、全ての待ち行列に対するI/Oを扱う単一I/Oマネージャがあり、または待ち行列のサブセットに対するI/Oをそれぞれが扱う並列に実行されるマルチI/Oマネージャがある。

0032

待ち行列データ構造は、配布中のデータメッセージを含む「メッセージレコード」(単に「メッセージ」とも称する)、および待ち行列システム100が待ち行列を管理するのに用いる情報を含む「制御レコード」を含むレコードを格納する。図1Bは、メッセージヘッダ130およびメッセージデータ132をそれぞれが含む一連のメッセージレコードを含む例示の待ち行列データ構造QUEUE_Mを示す。待ち行列は、オプションで、メッセージヘッダ130を伴うメッセージデータを格納でき、または代替として、外部に格納したメッセージデータ136のアドレスを規定するメッセージヘッダ130を伴うポインタ134を格納できる。後述の「大規模トランザクション間接技法」では、レコードは、メッセージシーケンスを格納する大規模トランザクションデータ構造122を指すポインタ138をオプションで含むことができる。

0033

待ち行列システム100は、発行者−契約者データ配布モデルを含む各種のデータ配布モデルサポートする。待ち行列に対して「発行者」として作用するアクセスエンティティ(信頼済みまたは未信頼のエンティティ)は、「書き込みトランザクション」内の待ち行列(トピックとも称する)へ一つ以上のメッセージを追加することができる。待ち行列に対して「契約者」として働くアクセスエンティティ(信頼済みまたは未信頼のエンティティ)は、「読み出しトランザクション」内の待ち行列から一つ以上のメッセージを読み出すことができる。複数の発行者が、同一待ち行列へメッセージを追加することができ、複数の契約者が、同一待ち行列から同一メッセージを読み出すことができる。待ち行列マネージャ106は、待ち行列に対する全ての契約者がメッセージを読み出した後、その待ち行列からメッセージを削除する。代替として、ポイント対ポイントのデータ配布モデルでは、多数のアクセスエンティティが待ち行列へメッセージを追加できるが、それぞれのメッセージは単一のアクセスエンティティにより待ち行列から読み出される。「複合トランザクション」は、詳細に後述するように、二つ以上の待ち行列との相互作用を含む。

0034

本明細書で説明する書き込みトランザクション、読み出しトランザクションおよび複合トランザクションは、原子性(Atomicity)、整合性(Consistency)、分離性(Isolation)、および永続性(Durability)の頭字からなる「ACID」特性の内の一つ以上と調和する方法で実行することができる。

0035

書き込みトランザクションを開始するには、発行者はトランザクション識別子(ID)を待ち行列マネージャ106から取得し、書き込みトランザクションにおいて待ち行列へ追加すべき一つ以上のメッセージを、待ち行列マネージャ106へ渡す。追加されたメッセージは、それらが待ち行列へ追加された書き込みトランザクションのトランザクションIDと関係付けられる。待ち行列マネージャ106は、メッセージをI/Oマネージャ114へ渡して、揮発性メモリ格納118へ書き込み、最終的に不揮発性メモリ格納116へ書き込む。待ち行列マネージャ106およびI/Oマネージャ114が実行する機能の役割分担を代替することができる。

0036

発行者が、書き込みトランザクションにおいて追加すべき全てのメッセージを待ち行列マネージャ106に提供した後、発行者は、待ち行列マネージャ106に書き込みトランザクションを「コミット」または「ロールバック(元に戻す)」するようリクエストできる。書き込みトランザクションをコミットするためには、待ち行列マネージャ106は、不揮発性メモリ内の対応する待ち行列データ構造へ「コミットレコード」を追加する。コミットレコードは、コミット済み書き込みトランザクションのメッセージ(「コミット済みメッセージ」)を契約者へ渡すことができることを示す。書き込みトランザクションをコミットする前に、関係付けられるメッセージを揮発性メモリから不揮発性メモリに確実に同期する(まだ同期されていない場合)ことにより、メッセージを永続性のあるものにする。

0037

待ち行列マネージャ106は、ロールバックされた書き込みトランザクションにおけるメッセージを、これらのメッセージが不揮発性メモリと同期されていない場合、破棄する。メッセージが不揮発性メモリと同期されている場合、「ロールバックレコード」を適切な待ち行列データ構造へ書き込んで、そのトランザクションにおけるメッセージはコミットされず、そのメッセージは最終的に破棄することができることを示す。実装によっては、所定の時間(例えば、1時間)が経過した後、書き込みトランザクションがコミットされず、またはロールバックされない場合、待ち行列マネージャ106は、オプションで自動的にトランザクションをロールバックして、例えば、これらのトランザクションの蓄積が格納空間を浪費するのを防ぐことができる。

0038

読み出しトランザクションを開始するには、契約者は、トランザクションIDを取得し、一つ以上の次の未読メッセージを待ち行列マネージャ106から受信する。I/Oマネージャ114は、適切な待ち行列データ構造からメッセージを取り出すステップを扱い、待ち行列マネージャ106は、それらを契約者へ渡す。コミット済みメッセージだけが契約者へ渡され、コミットされたメッセージはまだコミットされていないメッセージとインターリーブされ得るので、メッセージは、それらが待ち行列データ構造へ書き込まれたのと同一の順序で渡しても、同一の順序で渡さなくてもよい。待ち行列マネージャ106は、詳細に後述するように、「読み出しデータ構造」を蓄積することにより、待ち行列内のどのメッセージを契約者へ渡すべきかを判定する。

0039

「複合トランザクション」では、アクセスエンティティは、全てのメッセージが同一トランザクションIDと関係付けられる二つ以上の待ち行列へ、書き込みおよび/またはそこから読み出すことができる。複合トランザクションをコミットまたはロールバックすることもできる。複合トランザクションがコミットされると、「複合コミット」動作では、その複合トランザクションにおいてメッセージを書き込まれている待ち行列のそれぞれへ、コミットレコードが追加される。これらの「待ち行列コミットレコード」は、対応するコミット済みメッセージを契約者へ渡すことができることを表すのに用いる。

0040

これらの「待ち行列コミットレコード」を書き込む前に、コミットされている複合トランザクションのトランザクションIDを含むジャーナルデータ構造124へ、「ジャーナルコミットレコード」を書き込む。ジャーナルコミットレコードは、オプションで、複合トランザクションに参加しているアクセスエンティティおよび関与する待ち行列データ構造のような他の情報も含むことができる。トランザクションに書き込まれるメッセージ全てを永続的に格納するか、またはどれも永続的に格納しないか、の何れかを確実に行う(例えば、追加されたメッセージ全てを、障害が発生するとロールバックする)原子動作として、複合コミット動作を実行する。ジャーナルコミットレコードの書き込みは、複合コミット動作を完了させる原子作用である。ジャーナルコミットレコードが書き込まれた後に障害が起きて、それが待ち行列コミットレコード全てが書き込まれる前であった場合、待ち行列システム100は、永続的に格納されたジャーナルコミットレコードに基づいて復元でき、残りの待ち行列コミットレコードを書き込む。

0041

I/O効率を向上させるために、待ち行列マネージャ106は、オプションで、待ち行列データ構造とは別のデータ構造内に、待ち行列に対する新規メッセージを格納することにより、異なるトランザクションからのメッセージのインターリーブを減少させる技法を用いる。例えば、待ち行列システム100は、この種のメッセージインターリーブを減少させる二つの技法を含む:後述する「書き込みバッファ技法」および「大規模トランザクション間接技法」である。

0042

書き込みバッファ技法では、I/Oマネージャ114は、最初に、待ち行列に対する未コミットメッセージを、揮発性メモリ格納118内の書き込みバッファ120内に一時的に格納する。メッセージと関係付けられる書き込みトランザクションがコミットされたら、それらのメッセージを書き込みバッファ120から適切な待ち行列データ構造へ移動する。例えば、書き込みバッファ120が一杯か、または所定の時間経過後の場合は、書き込みトランザクションがコミットされる前に、メッセージを書き込みバッファ120から適切な待ち行列データ構造へ移動してもよい。代替として、書き込みバッファ120を、不揮発性メモリ格納116内に格納することができ、それでも同一機能の内の一部を提供できる(例えば、異なるトランザクションからのメッセージのインターリーブを減少させる)。

0043

大規模トランザクション間接技法では、大規模数のメッセージ(例えば、コンピュータ環境の特性に応じて、10,000、100,000、1,000,000等を越える等)を含む書き込みトランザクションは、発行者により「大規模トランザクション」として識別される。待ち行列マネージャ106は、大規模トランザクションのメッセージを大規模トランザクションデータ構造(LTDS)122内に格納し、LTDS122を指すポインタを待ち行列データ構造内に格納する。待ち行列マネージャ106は、オプションで、書き込みトランザクション内に所定の数のメッセージを検出したら、書き込みトランザクションを大規模トランザクションへオンザフライで自動的に変換できる。書き込みバッファ技法と大規模トランザクション間接技法はともに、メッセージデータを連続メモリ場所内に格納する可能性を高めて、I/O効率を向上させる。

0044

2 メッセージの追加および読み出し
I/Oマネージャ114は、不揮発性メモリ118内の順序付けられた待ち行列データ構造へメッセージを格納する場合、どの特定の書き込みトランザクションに対するメッセージも、待ち行列マネージャ106へ提示された順序で維持する。待ち行列データ構造内に格納されたメッセージの順序は、例えば、現在、待ち行列データ構造の一部となっているディスクページのリンクリストにより判定される。異なる書き込みトランザクションに対するメッセージは、待ち行列データ構造内でインターリーブすることができる。新規の書き込みトランザクションを、前に開始された書き込みトランザクションをコミットした後で開始する場合、新規書き込みトランザクションと関係付けられる全てのメッセージは、前の書き込みトランザクション内のメッセージ全てが待ち行列データ構造内で処理された後に行われる。

0045

契約者は、読み出しトランザクションを開始し、その中で待ち行列から一つ以上のメッセージをリクエストすることができる。契約者が受信するメッセージは、一つの書き込みトランザクションから来ることも、書き込みトランザクションのサブセットから来ることも、または二つ以上の書き込みトランザクションから来ることもある。詳細に後述するように、待ち行列マネージャ106は、コミット済み書き込みトランザクションからメッセージを契約者へ渡す。同一の書き込みトランザクション内に書き込まれていたメッセージは、書き込みトランザクションの順序で契約者へ提供される。異なる書き込みトランザクションからのメッセージは、書き込みトランザクションがコミットされた順序で契約者へ提供される。待ち行列の異なる契約者が読み出すメッセージは、これらの契約者が同一順序で見る。

0046

異なる書き込みトランザクションからのメッセージが、待ち行列データ構造内にインターリーブされるという程度にまで、読み出しトランザクションのI/O効率が低下することがある。例えば、待ち行列マネージャ106は、メッセージがコミットされたと判断するまで、メッセージを契約者へ渡さない。メッセージおよびそのメッセージと対応するコミットレコードを分離するデータが多いほど、用いられる管理リソース(例えば、メモリ、または読み出し動作)は多くなる。書き込みトランザクションと関係付けられるメッセージ(特に、書き込みトランザクションの最初のメッセージ)は、例えば、メッセージが追加されてから、関係付けられる書き込みトランザクションがコミットされるまでの間に長い時間を要する場合、その書き込みトランザクションに対するコミットレコードと遠く離れていることがある。その時間の間、メッセージは、他のメッセージ(例えば、他の書き込みトランザクションと関係付けられるメッセージ)とインターリーブされる待ち行列データ構造内に格納されることになる。更に、その書き込みトランザクション内のメッセージは、遠く離れたディスクページ上に存在することもある。読み出しトランザクションでは、待ち行列マネージャ106は、コミットレコードに対する待ち行列データ構造をスキャンし、その書き込みトランザクションに対するメッセージが格納されるページ全てを遡ってスワップしなければならないことになる。

0047

2.1書き込みバッファ
図2A図2Eは、上記に説明した書き込みバッファ技法の例示を実行している間の、書き込みバッファ120および待ち行列データ構造QUEUE_Aの状態を示す。書き込みバッファ120は、待ち行列レコード(例えば、メッセージレコードおよび書き込みトランザクションの開始を示す「オープン」レコード)に対する一時的な格納である。書き込みバッファ120は、対応するトランザクションがコミットされるか、または書き込みバッファ120が「一杯」になるまで、レコードを保持する。待ち行列マネージャ106は、データの最大量、メッセージの最大数に基づいて、またはデータの量とメッセージの数の組み合わせに基づいて、書き込みバッファ120が一杯になる時間を判定できる。本実施例では、説明のために過ぎないが、書き込みバッファ120は、最大3つのメッセージを保持する。書き込みバッファ120は、メッセージが追加された順序を保存する順序付けデータ構造(例えば、リンクリスト)とともに実装する。書き込みバッファ120および待ち行列データ構造QUEUE_Aを、メッセージがリストの底部の「ヘッド」へ追加されるリストとして示す。

0048

図2Aを参照すると、待ち行列データ構造QUEUE_Aは、書き込みトランザクションT1の開始を示す「OPEN
T1」レコード、およびトランザクションT2の開始を示す「OPEN T2」レコードを保持する。書き込みバッファ120は、ヘッダ:「T1:ADDM1」、「T2:ADD
M1」、および「T1:ADD M2」を有するメッセージを保持する。各メッセージのメッセージデータも、対応するメッセージヘッダと併せて書き込みバッファ120内に格納する。本実施例では、書き込みトランザクションT1と関係付けられる二つのメッセージが、書き込みトランザクションT2と関係付けられるメッセージとインターリーブされる。これは、例えば、T1およびT2が異なる発行者により同時に書き込まれたためである。

0049

図2Bを参照すると、待ち行列マネージャ106は、トランザクションT1(メッセージヘッダおよび関係付けられるメッセージデータを含む)に対するメッセージM1およびM2を、QUEUE_Aへ移動し、メッセージを不揮発性メモリへ同期したことを確認した後、書き込みトランザクションT1に対するコミット動作を実行する。コミットレコード「COMMIT
T1」をメッセージの後でQUEUE_Aへ書き込んで、コミット動作を完了させる。T1メッセージをQUEUE_Aへ移動した後、単一のT2メッセージが書き込みバッファ内に残る(T2はまだコミットされていないので)。

0050

図2Cを参照すると、発行者が、新規書き込みトランザクションT3を開いて、ヘッダ「T3:ADDM1」および「T3:ADD M2」を有する二つのメッセージを待ち行列へ追加する。両者は、二つの空いているスロットを有する書き込みバッファ120内に格納される。次いで、待ち行列マネージャ106は、ヘッダ「T2:ADD
M1」を有するT2の唯一のメッセージM1をQUEUE_Aへ移動した後、書き込みトランザクションT2に対するコミット動作を実行する。次いで、発行者は、新規の書き込みトランザクションT4を開いて、ヘッダ「T4:ADD
M1」を有するメッセージを、最後に残っている書き込みバッファ120のスロット内の待ち行列へ追加する。書き込みトランザクションT1およびT2と関係付けられるメッセージは、当初インターリーブされていたが、インターリーブを解かれて、書き込みバッファ120からQUEUE_Aへの転送の一部として、待ち行列データ構造QUEUE_A内に連続して格納されている。

0051

図2Dを参照して、発行者がT4に対する第2メッセージを追加すると、書き込みバッファ120が一杯なので、待ち行列マネージャ106は、T3と関係付けられるメッセージを書き込みバッファ120からQUEUE_Aへ転送する。この転送は、第2のT4メッセージに対して書き込みバッファ120内の空間を空ける。このように、書き込みトランザクション内のメッセージは、コミットされる前に書き込みバッファ120から転送されることもある。

0052

図2Eを参照すると、待ち行列マネージャ106は、書き込みトランザクションT4に対するコミット動作を実行し、新規のT3メッセージを受信し、書き込みトランザクションT3に対するコミット動作を実行する。本実施例は、書き込みのバッファ処理がメッセージのインターリーブ(または一時的な断片化)を低減するが、書き込みバッファ120が一杯になることにより、書き込みバッファ処理を用いても何らかの一時的な断片化が依然として起きることを示す。代替として、書き込みバッファ120が一杯の場合、一つ以上の書き込みトランザクションを大規模トランザクションに変換して、待ち行列データ構造に一時的な断片化を起こさずに、書き込みバッファ120内の空間を空けることができる。

0053

実装によっては、それぞれの待ち行列は自身の書き込みバッファを有する。代替として、書き込みバッファ120は二つ以上の待ち行列に対するメッセージを保持してもよい。一実施例では、三つの書き込みトランザクションT1〜T4に対するメッセージを二つの待ち行列へ追加する。図3Aは、書き込みバッファ120が一杯の場合(本実施例では、書き込みバッファ120が10個のメッセージを保持する)の、書き込みバッファ120および待ち行列データ構造QUEUE_A、QUEUE_Bの状態を示す。図3Bは、二つの新規メッセージ(書き込みトランザクションT1、T4に対する)が追加された後の、書き込みバッファ120および待ち行列データ構造QUEUE_A、QUEUE_Bの状態を示す。最も古いトランザクションT1と関係付けられるメッセージはQUEUE_Aへ転送され、新規メッセージのための書き込みバッファ120内の空間が空いている。

0054

2.2読み出しデータ構造
待ち行列マネージャ106は、待ち行列内のメッセージレコードを順次スキャンし、メッセージヘッダだけを読み出して、それぞれのメッセージがどのトランザクションと関係付けられるかを判定することにより読み出しデータ構造を蓄積する。待ち行列マネージャ106は、読み出しデータ構造を用いて、多数となる可能性のある書き込みトランザクションの経過を追跡する。それぞれの待ち行列に対して、待ち行列マネージャ106は、その待ち行列の各契約者に対する読み出しデータ構造を格納する。

0055

図4は、QUEUE_Aと対応する例示の読み出しデータ構造400を示す。本実施例では、読み出しデータ構造400は、先入れ先出し(FIFO)のサブリスト401〜404の順序付けられたリストを含む。待ち行列マネージャ106が、新規書き込みトランザクションと対応するメッセージを見付けるたびに、新規のFIFOサブリストを、その書き込みトランザクションのトランザクションIDにより識別される読み出しデータ構造400へ追加する。待ち行列マネージャ106は、各FIFOサブリストへ、対応する書き込みトランザクションと関係付けられるそれぞれのメッセージを指すポインタを、スキャンされる順序で(例えば、待ち行列へ追加した順序で)追加する。

0056

図4に示す待ち行列データ構造QUEUE_Aをスキャンする際には、待ち行列マネージャ106は、メッセージM1およびM2を指すポインタを有する、書き込みトランザクションT1に対する第1FIFOサブリスト401を生成する。待ち行列マネージャ106は、メッセージがコミットされたことを確認するまで(すなわち、関係するトランザクションに対するコミットレコードをスキャンするまで)、対応する契約者へ(読み出しトランザクションへ応答して)メッセージを返すのを開始しない。T1に対するコミットレコードに到達した後、T1に対するFIFOサブリスト401が完成し、待ち行列マネージャ106は、読み出しデータ構造400を蓄積するのを一時的に停止して、FIFOサブリスト401内のポインタに基づいて次のメッセージを取り出し、契約者が新規メッセージを請求した場合、そのメッセージを契約者へ渡す。完成したFIFOサブリスト401内の全てのメッセージを契約者へ渡した後、待ち行列マネージャ106は、QUEUE_Aのスキャンを再開して、次のFIFOサブリスト402が完成するまで、読み出しデータ構造400の蓄積を継続する。待ち行列マネージャは、完成したFIFOサブリストから契約者へメッセージを渡すことと、待ち行列データ構造をスキャンして読み出しデータ構造を蓄積することとを交互に行う。本実施例では、T4のコミットレコードはT3のコミットレコードの前に行われるので、T3に対するメッセージM1〜M3の前に、T4に対するメッセージM1およびM2を契約者へ渡す。代替の実施では、待ち行列マネージャは、完成したFIFOサブリスト内の全メッセージを契約者へ渡す前に、契約者へメッセージ渡すことから読み出しデータ構造の蓄積へと移行することができる。

0057

それぞれのFIFOサブリストは、対応する契約者がそのFIFOサブリスト内の全メッセージを受け取るまで、または待ち行列マネージャ106が、対応する書き込みトランザクションはコミットされないと判定する(例えば、ロールバックレコードを読んだ後)まで、維持される。読み出しトランザクションをコミットしてから、契約者がどのメッセージを読み出したかを示すジャーナルデータ構造124へコミットレコードを書き込む。待ち行列マネージャ106が読み出しデータ構造400の蓄積を終了した後、読み出しデータ構造400を、同一契約者に対する同一待ち行列からの次の読み出しトランザクションのために維持する。

0058

2.3 大規模トランザクション間接化
図5を参照して、待ち行列マネージャ106が大規模トランザクションT2を開くと、待ち行列マネージャ106は、不揮発性メモリ格納116内に大規模トランザクションデータ構造(LTDS)122を配置する。大規模トランザクションのメッセージが到着すると、メッセージの連続リストとしてLTDS
122へ直接書き込まれる。大規模トランザクションがコミットされると、待ち行列マネージャ106は、LTDS 122を閉じ、待ち行列データ構造QUEUE_P内の間接メッセージ500内にLTDS 122へのポインタを格納する。間接メッセージ500は、大規模トランザクションT2のトランザクションIDも含む。

0059

待ち行列マネージャ106が、QUEUE_Pに対する読み出しデータ構造を蓄積すると、T1メッセージは二回スキャンされる。一回目は、読み出しデータ構造のFIFOサブリストを指すポインタを書き込むとき、もう一回目は、契約者へ返すメッセージを読み出すときである。この二回のスキャンは、大規模トランザクションT2の多数のメッセージがQUEUE_P内に格納されるとしたら、非効率であろう。その代わりに、待ち行列マネージャ106がQUEUE_Pに対する読み出しデータ構造を蓄積していて、単一の間接メッセージ500をスキャンする場合、待ち行列マネージャ106は、T2に対するFIFOサブリストを必ずしも必要とせずに、LTDS
122からメッセージを契約者へ直接渡すことができる。大規模トランザクションがコミットされていると自動的に指示されるので、どの大規模トランザクションメッセージも、契約者へ渡す前にスキャンする必要はない。また、スキャンの別の機能、異なるトランザクションからのメッセージの「非インターリーブ化」が不要になる。大規模トランザクションT2内の全てのメッセージを返した後、待ち行列マネージャ106は、待ち行列データ構造へ戻る。

0060

大規模トランザクションは、発行者により選択されるか、または待ち行列によりオンザフライで推定されるオプションとすることができる。

0061

3複合コミット
複合コミット動作では、待ち行列マネージャ106は、複数の待ち行列へ書き込む複合トランザクションの追加メッセージ全てが、確実に、永続的に格納されているようにする。複合コミット動作の一部は、これらの待ち行列へコミットレコードを書き込むステップを含む。一つ以上のアクセスエンティティが待ち行列に同時にアクセスでき、その一方で、アクセスエンティティに複合コミット動作へ干渉させずに、複合コミット動作を実行するメカニズムを提供することが有用である。

0062

待ち行列マネージャ106は、ジャーナルデータ構造124へジャーナルコミットレコードを書き込むことにより、複合トランザクションのメッセージが永続的に格納されている(すなわち、不揮発性メモリと同期されている)ことを示す。続いて、待ち行列マネージャ106は、複合トランザクションにおいてメッセージが書き込まれている待ち行列のそれぞれに、待ち行列コミットレコードを書き込む(例えば、読み出しデータ構造を蓄積するためにコミットレコードに対して待ち行列をスキャンできるように)。待ち行列データ構造には格納空間の制約があるので、複合コミット動作に対するタイムアウト期間内に(例えば、5秒間)、コミットレコードを書き込むのに十分な残り空間を幾つかの待ち行列が持っていない可能性がある。待ち行列データ構造が複合コミット動作の開始時に利用できる空間を持っていたとしても、同時に行われる書き込み動作が、待ち行列コミットレコードが書き込まれる前にその空間を使い切ってしまうこともある。コミットレコードに対する待ち行列内の空間の不足は、メッセージがコミットされていることをジャーナルデータ構造124が示すにもかかわらず、契約者にそのメッセージを受信させるための対応コミットレコードが待ち行列内にないので、潜在的な問題となる。

0063

複合コミット動作に対する待ち行列コミットレコード管理の一手法では、待ち行列マネージャ106が、コミットレコードを書き込む間、各待ち行列を同時にロックし、コミット動作中に空間が使い尽くされるのを防ぐことにより、待ち行列のそれぞれにコミットレコードのための十分な空間を利用できるのを確実にする。第2、第3の手法では、複合コミット動作を更に効率的に実行するため、待ち行列マネージャ106は、二つ以上の待ち行列の同時ロックを必要としないで、複数の待ち行列のそれぞれへのコミットレコードの書き込み成功を保証する方法を用いる。これら3つの各方法については詳細に後述する。

0064

図6を参照すると、待ち行列データ構造QUEUE_AおよびQUEUE_Dは、トランザクションIDがT1、T2およびT3の複合トランザクションのメッセージならびにトランザクションIDがT4の書き込みトランザクションを含む。複合トランザクションT1はコミットされていて、T1のコミットレコードは、QUEUE_AおよびQUEUE_Dへ書き込まれている。トランザクションT2、T3およびT4はまだコミットされていない。複合トランザクションT2に対する複合コミット動作と関係付けられるQUEUE_AおよびQUEUE_Dの動作を、3つの例示の手法それぞれについて下記に説明する。

0065

3.1 第1手法
図7は、コミットレコード書き込み動作700のフロー図を示す。待ち行列マネージャ106は、複合トランザクション内に含まれる各待ち行列をロックする702。図6の実施例では、待ち行列マネージャ106は、QUEUE_AおよびQUEUE_Dをロックする(例えば、ロックフラグを設定することにより)。このロックは、何らかの他のプロセスが、待ち行列データ構造内の利用できる空間を占有するのを防ぐ。

0066

各待ち行列をロック702した後、待ち行列マネージャ106は各待ち行列内の利用できる格納空間をチェックする704。図6の実施例では、待ち行列データ構造QUEUE_Aは、利用できる格納600のブロックを有し、待ち行列データ構造QUEUE_Bは、利用できる格納602のブロックを有する。待ち行列マネージャ106は、各待ち行列内の利用できる空間量を、コミットされる複合トランザクションに対するコミットレコードを書き込むのに用いるであろう空間量と比較する。どの待ち行列も、コミットレコードに確保される利用可能な空間を十分に持たない場合、待ち行列マネージャ106は、複合コミット動作を中断する706。待ち行列マネージャ106は、後で複合コミット動作を試みることができ、および/または一つ以上の待ち行列に対する格納空間の更なる取得を試みることができる。

0067

待ち行列が、コミットレコードに確保される格納空間を十分に持つ場合、待ち行列マネージャ106は、それぞれの待ち行列を同期して708、揮発性メモリ内に格納されるどのメッセージも不揮発性メモリへ移動したことを確認する。それぞれの待ち行列が同期されてから、待ち行列マネージャ106は、コミットレコードをジャーナルデータ構造126へ書き込む710。ジャーナルコミットレコードを書き込んだ後、待ち行列マネージャ106は、それぞれの待ち行列へコミットレコードを書き込む712。コミットレコードを待ち行列へ書き込んだ後、待ち行列マネージャ106はその待ち行列のロックを外す714。

0068

ジャーナルコミットレコードの書き込みは、複合コミット動作を復元可能な時点を定義する原子動作である。待ち行列システム100が、待ち行列マネージャ106がジャーナルコミットレコードを書き込む710前に、複合コミット動作中に障害を起こした場合、コミット動作を待ち行列全てに対して中断する(待ち行列の幾つかが不揮発性格納へ同期されていないかもしれず、コミットレコードがどの待ち行列にも書き込まれていないこともあるからである)。待ち行列システム100が、待ち行列マネージャ106がジャーナルコミットレコードを書き込んだ710後、複合コミット動作中に障害を起こした場合、コミット動作を、待ち行列全てに対して完了させる(それぞれの待ち行列が不揮発性格納へ同期されていて、コミットレコードをジャーナルコミットレコードから復元できるからである)。

0069

3.2 第2手法
第2手法では、待ち行列マネージャ106は、各待ち行列内の利用できる空間量を、コミットされる複合書き込みトランザクションおよび何らかの未解決トランザクションに対するコミットレコードを書き込むのに用いるであろう空間量と比較する(本明細書で使用しているように、「未解決トランザクション」は、複合トランザクションおよび書き込みトランザクションの両方を含む)。待ち行列データ構造QUEUE_Aは、T2および未解決トランザクションT3に対するコミットレコードを書き込むために予約される記憶装置604のブロックを含む。待ち行列データ構造QUEUE_Bは、T2および未解決トランザクションT3およびT4に対するコミットレコードを書き込むために予約される記憶装置606のブロックを含む。

0070

図8Aは、書き込みトランザクションの開始時に実行される「オープン動作」800のフロー図を示す。各待ち行列QUEUE_iに対して、待ち行列マネージャ106は、コミットレコードが未だ書き込まれていない未解決トランザクションの数Tiの経過を追跡する。QUEUE_iに関する新規トランザクションを開き、およびTiをインクリメントする前に、待ち行列マネージャ106は、待ち行列(単純な書き込みトランザクションについては単一の待ち行列、または複合トランザクションにおいてはメッセージが追加されているそれぞれの待ち行列)をロックし802、チェックして804、「オープンレコード」およびコミットレコードに対する空間が存在するよう確保する。待ち行列マネージャ106は、現在利用できる空間を次式により与えられるDoと比較する:
Do = size_of(1オープンレコード)+size_of(1コミットレコード)×(Ti+1)
利用できる空間がDo以上の場合、待ち行列マネージャ106は、QUEUE_iのロックを外し806、「オープンレコード」を書き込み808、未解決トランザクションの数Tiをインクリメントする810。あるいは、利用できる空間がDo未満の場合、待ち行列マネージャ106は、QUEUE_iのロックを外し812、オープン動作800を中断する814。

0071

図8Bおよび図8Cは、コミットレコード書き込み動作840および関係する書き込み動作850それぞれのフロー図を示す。待ち行列マネージャ106(またはI/Oマネージャ114)は、コミット動作に対するコミットレコード書き込み動作840を用いるとともに、書き込み動作850を用いて(同時に起きる可能性がある)、待ち行列へコミットレコード以外の何らかのデータを書き込む。この手法では、コミットレコード書き込み動作840は、待ち行列内の利用できる空間に対するチェックを必要としない。その理由は、書き込み動作850が、待ち行列データ構造へ何らかのデータを書き込む前にこのチェックを含むからである。待ち行列マネージャ106は、詳細に後述するように、各待ち行列QUEUE_iが、その待ち行列に対するTi個の未解決トランザクションそれぞれに対するコミットレコードのための十分な空間予約を確保する。従って、コミットレコード書き込み動作840を実行する際、待ち行列マネージャ106は、空間が各コミットレコードのために予約されたことを前提とすることができる。

0072

図8Bを参照すると、コミットレコード書き込み動作840では、待ち行列マネージャ106は、最初に各待ち行列を同期させる842。各待ち行列を同期させた後、待ち行列マネージャ106は、ジャーナルコミットレコードを書き込む844。ジャーナルコミットレコードを書き込んだ後、待ち行列マネージャ106は各待ち行列へコミットレコードを書き込む846。

0073

図8Cを参照すると、待ち行列マネージャ106は、待ち行列データ構造へ書き込まれるデータに対して書き込み動作850を用いる。待ち行列マネージャ106は、書き込まれるデータがコミットレコードかどうかを最初に判定する852。Yesであれば、待ち行列マネージャ106は、コミットレコード854を書き込み、未解決トランザクションの数Tiをデクリメントする856。Noであれば、待ち行列マネージャ106は待ち行列をロックし858、待ち行列内で利用できる格納空間をチェックする860。待ち行列マネージャ106は、現在の利用できる空間を次式で与えられるDwと比較する:
Dw = size_of(書き込まれるデータ)+size_of(1コミットレコード)×Ti
ここで、size_of(data)は、適切な単位(例えばバイト)のdataのサイズを返す。利用できる空間がDw以上の場合、待ち行列マネージャ106は、データを書き込み862、待ち行列のロックを外す864。あるいは、利用できる空間がDW未満の場合、待ち行列マネージャ106は、待ち行列のロックを外し866、書き込み動作850を中断する868。本手法では、格納空間をチェックする間、データを書き込む待ち行列である単一の待ち行列だけがロックされる。

0074

3.3 第3手法
図9Aおよび図9Bは、コミットレコード書き込み動作900および関係する書き込み動作950のフロー図を示す。この手法では、待ち行列マネージャ106は、書き込みトランザクションの開始時点図8Aに示す「オープン動作」800を用いる。コミットレコード書き込み動作900および書き込み動作950は、ともに待ち行列内の利用できる空間をチェックする。また、本手法では、一度には単一の待ち行列しかロックしない。各待ち行列QUEUE_iに対して、待ち行列マネージャ106は、未解決トランザクションの数Tiの経過を追跡する(オープン動作800を用いてTiをインクリメントする)。待ち行列マネージャ106は、Ti個の未解決トランザクションのそれぞれに対するコミットレコードのための十分な空間を、それぞれの待ち行列データ構造が予約するのを確実にする。しかし、本手法では、待ち行列マネージャ106は、データを待ち行列へ書き込む前に空間をチェックするために、「予約モード」状態にある待ち行列をロックするのみである。予約モードは、全ての参加している待ち行列を同時にはロックせずに、コミット動作が進行状態にあるということを示す方法を提供する。

0075

図9Aを参照すると、コミットレコード書き込み動作900では、待ち行列マネージャ106は、最初に、コミットレコード書き込み動作900に含まれる各待ち行列QUEUE_iに対して一回(i=1の場合...動作900における待ち行列の数)、ループ902(または、等価の制御構造)を実行する。ループ902は、多数の複合コミット動作が同時に実行される可能性があることを考慮できる方法で、QUEUE_iに対する予約モードをONにする。本実施例では、ループ902は、QUEUE_iに対する予約モードカウンタRiをインクリメントする904。予約モードカウンタは、QUEUE_iが予約モード状態にない初期値、例えば、Ri=0、で開始する。Ri>0の場合、QUEUE_iは予約モード状態にある。これにより、待ち行列の予約モード状態が、その待ち行列が予約モードとなった回数に対応するようになる。

0076

予約モードカウンタをインクリメントした後、ループ902内で、待ち行列マネージャ106はQUEUE_iをロックし906、QUEUE_i内で利用できる格納空間をチェックする908。待ち行列マネージャ106は、現在の利用できる空間を、次式により与えられるDcと比較する:
Dc = size_of(1コミットレコード)×Ti
利用できる空間がDc以上の場合、待ち行列マネージャ106は、QUEUE_iのロックを外し910、継続する。あるいは、利用できる空間がDc未満の場合、待ち行列マネージャ106は、QUEUE_iのロックを外し912、コミットレコード書き込み動作900を中断する914。

0077

ループ902の後、待ち行列マネージャ106は、各待ち行列を同期する916。各待ち行列を同期した後、待ち行列マネージャ106は、ジャーナルコミットレコードを書き込む918。ジャーナルコミットレコードを書き込んだ後、待ち行列マネージャ106は、コミットレコードを各待ち行列へ書き込む920。コミットレコードを待ち行列へ書き込んだ後、待ち行列マネージャ106は、その待ち行列に対する予約モードカウンタをデクリメントする922。

0078

図9Bを参照すると、待ち行列マネージャ106は、待ち行列データ構造へ書き込まれるデータに対する書き込み動作950を用いる。待ち行列マネージャ106は、最初に、書き込まれるデータがコミットレコードであるかどうかを判定する952。Yesであれば、待ち行列マネージャ106は、コミットレコード954を書き込み、未解決トランザクションの数Tiをデクリメントする956。Noであれば、待ち行列マネージャ106は、待ち行列が予約モード状態かどうかを判定する958(例えば、Ri>0かどうかを判定することにより)。待ち行列が予約モード状態にない場合、待ち行列マネージャ106は、データを書き込む960。待ち行列が予約モード状態の場合、待ち行列マネージャ106は待ち行列をロックし962、待ち行列内で利用できる格納空間をチェックする964。待ち行列マネージャ106は、現在の利用できる空間を第2手法について上記で定義したDwと比較する。利用できる空間がDw以上の場合、待ち行列マネージャ106は、データを書き込み966、待ち行列のロックを外す968。あるいは、利用できる空間がDW未満の場合、待ち行列マネージャ106は、待ち行列のロックを外し970、書き込み動作950を中断する972。

0079

3.4 他の手法
二つ以上の待ち行列を同時ロックせずに、多数の待ち行列のそれぞれへの、コミットレコードの書き込み成功を保証するコミット動作を管理するための他の手法が可能である。例えば、第3の手法の変形形態では、全ての未解決トランザクションのカウントTiを用いる代わりに、待ち行列マネージャ106は、Dcおよび/またはDWの計算に対して予約モードRi状態の待ち行列の数を用いる。手法によっては、ジャーナルコミットレコードを書き込む前に、待ち行列コミットレコードに対する空間が不足しているためにコミット動作が失敗しても許容される。

0080

4実装
本明細書で説明した待ち行列管理機能をコンピュータ上で実行するためにソフトウエアを用いて実装することができる。例えば、ソフトウエアは、一台以上のプログラム済みまたはプログラム可能コンピューターシステム分散型クライアントサーバ型、またはグリッド型等の各種アーキテクチャから構成できる)上で実行される一つ以上のコンピュータープログラム内の手順を形成する。それぞれのコンピューターシステムは、少なくとも一つのプロセッサ、少なくとも一つのデータ格納システム(揮発性メモリおよび不揮発性メモリおよび/または記憶素子を含む)、少なくとも一つの入力装置またはポート、および少なくとも一つの出力装置またはポートを含む。ソフトウエアは、例えば、計算グラフの設計および構成と関連する他のサービスを提供する、規模の大きなプログラムの内の一つ以上のモジュールを形成してもよい。本明細書で説明するデータ構造を、コンピュータ可読媒体内に格納したデータ構造、またはデータ収納庫内に格納したデータモデル準拠する他の体系化したデータ、として実装することができる。

0081

本ソフトウエアは、汎用または専用のプログラム可能なコンピュータにより読み込むことができるCD−ROMのような媒体上で提供するか、またはネットワークを介してソフトウエアが実行される場所であるコンピュータへ配布する(伝搬信号で符号化される)ことができる。機能全てを専用コンピュータ上で、またはコプロセッサ等の専用ハードウエアを用いて、実行することができる。本ソフトウエアは、ソフトウエアにより規定される異なる計算部分を異なるコンピュータで実行する分散型で実装できる。このようなコンピュータープログラムはそれぞれ、格納媒体または汎用もしくは専用のプログラム可能なコンピュータに可読の装置(例えば、固体メモリもしくは媒体、または磁気もしくは光学媒体)に格納するか、ダウンロードして、格納媒体または格納装置をコンピューターシステムが読み出す際に、本明細書で説明した手順を実行するようにコンピュータを構成し、動作させるのが好ましい。本発明のシステムは、コンピュータープログラムで構成されたコンピュータ可読格納媒体として実装し、そのように構成される格納媒体が、コンピューターシステムを規定の方法、所定の方法で動作させて、本明細書で説明した機能を実行させると考えることもできる。

0082

理解すべきは、上記説明が説明を意図していて本発明の範囲を限定する意図はなく、本発明の範囲は、付帯のクレーム範囲により定義されるということである。例えば、上記説明の機能ステップの幾つかは、全体の処理に実質的に影響を与えることなく異なる順序で実行してもよい。他の実施の形態は以下のクレームの範囲内にある。

図面の簡単な説明

0083

図1Aは、待ち行列システムの図である。
図1Bは、待ち行列データ構造の図である。
図2Aは、書き込みバッファおよび待ち行列データ構造の図である。
図2Bは、書き込みバッファおよび待ち行列データ構造の図である。
図2Cは、書き込みバッファおよび待ち行列データ構造の図である。
図2Dは、書き込みバッファおよび待ち行列データ構造の図である。
図2Eは、書き込みバッファおよび待ち行列データ構造の図である。
図3Aは、書き込みバッファおよび二つの待ち行列データ構造の図である。
図3Bは、書き込みバッファおよび二つの待ち行列データ構造の図である。
図4は、待ち行列データ構造および対応する読み出しデータ構造の図である。
図5は、待ち行列データ構造および大規模トランザクションデータ構造の図である。
図6は、複合コミット動作の一部である待ち行列データ構造の図である。
図7は、複合コミット動作のフロー図である。
図8Aは、オープン動作のフロー図である。
図8Bは、複合コミット動作および関係する書き込み動作それぞれのフロー図である。
図8Cは、複合コミット動作および関係する書き込み動作それぞれのフロー図である。
図9Aは、複合コミット動作および関係する書き込み動作それぞれのフロー図である。
図9Bは、複合コミット動作および関係する書き込み動作それぞれのフロー図である。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

該当するデータがありません

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

該当するデータがありません

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ