JP2558052B2

JP2558052B2 - 仮定コミット２フェーズコミットプロトコルを用いるトランザクション処理システム及びその動作方法

Info

Publication number: JP2558052B2
Application number: JP5157165A
Authority: JP
Inventors: バトラーランプソン; デイビッドビーロメット
Original assignee: Digital Equipment Corp
Current assignee: Digital Equipment Corp
Priority date: 1992-07-06
Filing date: 1993-06-28
Publication date: 1996-11-27
Anticipated expiration: 2011-11-27
Also published as: EP0578406B1; US5335343A; DE69322549D1; EP0578406A1; JPH06168169A; DE69322549T2

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は分散計算システムの
動作に関し、特に分散トランザクション処理システムの
ためのコミットプロトコルに関する。

【０００２】

【従来の技術】トランザクション処理を用いるコンピュ
ータシステムは、特定の「コミット」が実行されるま
で、データの状態が永久的な変化をしないこと或いはそ
のシステムの他のノードから見える変化をしないことを
保証するためのコミットプロトコルを使う。トランザク
ション処理において通常用いられるこれらのプロトコル
の１つは、その詳細は文献「分散トランザクションの処
理モデルのツリーのための有効なコミットプロトコル」
（Mohan & Lindsay;"Efficient Commit Protocolsfor t
he Tree of Processes Model of Distributed Transact
ions",Proc.2nd ACM SIGACT/SIGOPS Symposium on Prin
ciples of Distributed Computing,17 August 1983 ）
に詳細に記述されている、所謂「２フェーズコミット」
即ち「２ＰＣ」である。２フェーズコミットプロトコル
は、「仮定アボート」型又は「仮定コミット」型のコミ
ットプロトコルとすることができる。現在のトランザク
ション処理システムにおいては、分散トランザクション
のコミットメントを調整するために、通常、仮定コミッ
ト２フェーズコミットプロトコルではなく、仮定アボー
ト２フェーズコミットプロトコルが用いられる。しかし
ながら、コミットされたトランザクションの各サブオー
ディネイトが、アボートのアクノリッジは必要ではある
が、コミットメッセージの回答として最終のアクノリッ
ジをコーディネイタに送付する必要がないので、多くの
状態において仮定コミットプロトコルが明確な利点を有
する。仮定アボートを用いると、この最終のアクノリッ
ジは、コーディネイタからのアボートメッセージに対し
て必要ではなく、コミットメッセージに対して必要であ
る。トランザクションは、アボートするより遥かに頻繁
にコミットする。従って、仮定コミットプロトコルは、
仮定アボート変形版より遥かに頻繁にこの最終のアクノ
リッジを節約する。このため、仮定コミットプロトコル
の性能改善を実現するためには、後述のように、この現
在の仮定コミットの障害を除去することが望ましい。

【０００３】従来のワークでは、コミットコーディネイ
タに必要な機能であるという理由で、仮定コミットに代
わって仮定アボートプロトコルが選択されていた。仮定
アボートプロトコルを用いると、サブオーディネイト
（これはコホートとも呼ばれる）がコーディネイタ処理
にトランザクションの状態を問い合わせた時はいつで
も、コーディネイタがそれのレコードを持っておれば、
トランザクションがコミットされる。他方情報がない場
合は、コーディネイタ処理はトランザクションがアボー
トされることを表示する。これは、以前のクラッシュは
全てアボートしたものと仮定されるので、トランザクシ
ョンがコミットするまではコーディネイタ処理が情報を
安定化する（ディスク記憶装置に書込む）必要はなく、
これは生起したことと一致することを意味する。コーデ
ィネイタは、結局、全てのコホートが最終メッセージを
アクノリッジした時に（非強制的な）エンドトランザク
ションレコードを書込む。これにより、コーディネイタ
は、記憶していた状態のガーベジコレクションを行い、
そのガーベジコレクション情報をシステムクラッシュの
間中持続することができる。

【０００４】仮定コミットプロトコルについては、コー
ディネイタ処理が、どのトランザクションがアボートし
たかを明確に知る必要がある。伝統的にこれは、２フェ
ーズコミットプロトコルが開始される時点で、コーディ
ネイタがログに対して、そのトランザクションが成功裏
にコミットしてはいない事実を強制的に与え、それが、
プロトコル開始のためのものであるが完結は表示しない
ログレコードを持つということを意味する。これらの不
完全なプロトコルトランザクションは、アボートされた
トランザクションのリストに加えられる。更に、プロト
コル開始ログレコードは、揮発性のメモリーに保持され
るアボートリスト情報のガーベジコレクションを可能に
する。全ての期待されたアクノリッジが受信された時点
で、コーディネイタは、それ以上の質問は受信されない
ことを知る。この時、トランザクションについてのアボ
ート情報がディスカード可能になる。エンドトランザク
ションレコードはこの安定状態を示す。

【０００５】

【発明が解決しようとする課題】２フェーズコミットプ
ロトコルの開始時点における、コーディネイタによるロ
グレコードの強制は追加の消費である。この余分の書込
みの強制は、２フェーズコミットプロトコルを経て完結
する各トランザクションに対して行われる。従って、本
発明の目的は、２フェーズコミットプロトコルの仮定コ
ミット形式の利点を残しながら、この余分のログ強制を
排除することにある。

【０００６】

【課題を解決するための手段】本発明は、特許請求の範
囲に記載されたような２フェーズコミットプロトコルに
存在する。本発明の１つの実施例によれば、分散トラン
ザクション処理システムのための２フェーズコミットプ
ロトコルは、「プリペア」メッセージがサブオーディネ
イト処理に送られる前にコミット手順の最初に通常書込
まれる最初の「コミット」レコードが、強制的なログ書
込みではなく、非強制的な型であることを除いて、仮定
コミット構成を用いる。即ち、「コミット」レコードは
ログバッファ即ち揮発性メモリーに書込まれるが、ログ
バッファは直ちにディスクに直接書込まれる必要はな
く、従って、ディスクへの書込みに固有の性能の低下を
避けることができる。通信のクラッシュ又は損失に続い
て、サブオーディネイト処理から行われる質問にコーデ
ィネイタが回答するために必要な情報を提供できるよう
にするため、不確定トランザクションの組を制限する技
術が用いられる。トランザクションには、トランザクシ
ョンＩＤ（Ｔ＿ＩＤ）として識別される昇順の番号が付
与される。コミットするトランザクションのトランザク
ションＩＤが、安定的に記録されたトランザクションＩ
Ｄの最高番号から予め選択された番号までの範囲内にな
ければ、コミット動作は開始できない。即ち、トランザ
クション番号がディスク記憶装置に書込まれている（従
ってクラッシュに耐える）最近の開始「コミット」レコ
ードから極端に離れていると、この開始コミットレコー
ド（及び安定的に記録されていない他のレコード）は、
揮発性メモリーに保持されずにディスクに書込まれる。
大部分のコミットトランザクションは、このようにディ
スク書込み（強制的なログ）のための待時間なしに処理
され、従って性能が改善される。不確定トランザクショ
ン（コミットしたか、アボートしたか、又は開始するこ
とはないかが未知）の組を限定し、これによりこの組が
コーディネイタによってキャッシュ又は揮発性メモリー
に記憶され、質問に答えることが可能になり、且つシス
テムクラッシュの後で再構成することが可能になるよう
な技術が開示されている。

【０００７】

【発明の実施の形態】添付図面を用いて行われる次の例
示としての好ましい実施例の説明から、本発明の更に詳
細な理解が得られる。

【０００８】図１には、通信リンク10及び多数のノード
11、12、13、14、15等を有する分散コンピュータシステ
ムが示されている。リンク上の通信方法は、イーサネッ
ト、トークンリング、ＦＤＤＩ又は他の同様のローカル
エリアネットワーク構成であり、更に遠隔リンクに対し
てはマイクロ波又は衛星リンクを含むことができる。接
続リンク自体は、例えば光ファイバ、撚線対電線又は同
軸ケーブルのような多くの商業的に利用できる技術のい
ずれかであってもよい。リンク10の構成及びその動作の
特定の型は本発明の一部ではない。必要なことは、コン
ピュータノード間の通信リンクを確立し、分散トランザ
クション処理システムを実現するための手段である。図
２によれば、各ノード11、12等は、通常、システムバス
19によって結合されたＣＰＵ16、主メモリー17及びディ
スク記憶装置18を含む。ネットワークアダプタ20が、通
信リンク10とのインタフェースになる。このノードは、
例えば、机上型ワークステーション、又はサーバーとし
て作用するミニコンピュータ、又はディスク記憶装置の
ような共有型システムリソース、又は他のネットワーク
或いは長距離リソースへのブリッジである。ノード（サ
イト）11−15は、何十、何百又は何千とあってもよい。

【０００９】図２のノードの適当な構成の例としては、
ＣＰＵが例えば文献「コンピュータプログラム及びアー
キテクチャ：ＶＡＸ」（"Computer Programming and Ar
chitecture:The VAX", 2nd Ed., Levy and Eckhouse, D
igital Press,1989)に記載されたＶＡＸ（商標）アーキ
テクチャである。ＶＡＸアーキテクチャの１チップＣＰ
Ｕは米国特許第5,006,980 号（Sander, Uhler, Brownに
よって発明され、本発明の譲受人であるディジタルイク
ィップメントコーポレーションに譲渡された）に開示さ
れている。ＣＰＵ16はまた、欧州特許出願91401782・7
（これもディジタルイクィップメントコーポレーション
に譲渡された）に開示されている改良された６４ビット
ＲＩＳＣアーキテクチャであってもよい。これに代え
て、勿論、ＣＰＵは、例えばインテル３８６又は４８６
アーキテクチャ、又はＭＩＰＳR3000 又はR4000 ＲＩＳ
Ｃアーキテクチャ等の多くの他の型であってもよい。

【００１０】図１及び２の分散システムの実行例は、数
種の型が市販されているデータベース管理システムのよ
うな分散された用途である。分散データベースシステム
においては、トランザクション（コンシステンシ及びリ
カバリのアトミックユニット）のアクションが複数のノ
ード又はサイト11、12、13等で起きる。トランザクショ
ンは、多重データ操作及び１つのトランザクションを構
成する定義ステートメントを含むことができる。分散ト
ランザクションコミットプロトコルは、（１）トランザ
クションの全ての影響が持続するために、又は（２）リ
ンク10又はノード11、12等のうちの１つが故障してメッ
セージの損失がある場合であっても全く影響が続かない
ようにするために、必要である。コミットプロトコル
は、分散トランザクション実行の一様なコミットメント
を保証する。

【００１１】開始する全てのトランザクションが最終的
にコミットするわけではない。コミットしないトランザ
クションは所謂アボートである。多くの理由の中で、ト
ランザクションがアボートするのは、電源が断になった
場合、システムがクラッシュした場合、他のトランザク
ションとの同時実行競合が起きた場合、又はユーザー
（又はユーザーのアプリケーションプログラム）が他の
エラーを検出して明示的にアボートする場合である。

【００１２】図１及び２のシステムで実行される分散デ
ータベースシステムは、異なるノードで実行される多数
の処理を含み、各々が、トランザクションがアボートさ
れることが必要ならばそのアクションは実行されなかっ
たことにすることとして、トランザクションのアクショ
ンを暫定的に実行することができる。データは、種々の
ノード11、12等の図３のデータ記憶21のような種々の不
揮発性の位置に記憶され、このようなそれぞれのデータ
記憶装置は、コミットプロトコルの実行中のトランザク
ションに対する全ての状態の変化及びトランザクション
の変化を、データ記憶21に記録するために用いられるロ
グ22を持つ。これらのログレコードは、通常、ノードの
ディスク18のような安定な不揮発性記憶装置の一部であ
るログファイル22に連続的に書込まれる。

【００１３】ログファイル22が書込まれる時は、この書
込みは主メモリー17中のログ「バッファ」に一時的に行
われ、次に、不揮発性ディスク記憶装置18に移す。この
ように、ログは揮発性主メモリー17に対して行われ、後
にディスク記憶装置18に書込まれる。コミットプロトコ
ルが「強制ログ書込み」を用いると、そのログレコード
（及び全ての以前のレコード）が主メモリー17のログバ
ッファからディスク18の安定記憶装置の永久ログに書込
まれる。ログレコードを書込む処理は、この強制的なロ
グ書込みが完了するまでその順序で連続的に行われる訳
ではない。サイト（ノード11、12等）がクラッシュする
場合は揮発性メモリー17の内容が失われると仮定される
が、強制的なログ書込みが完了すると強制されたレコー
ドはディスク記憶装置18のログ22に存在し、クラッシュ
を切り抜ける。従って、サイトが再スタートする時に
は、ディスク18から読取ることによってこのレコードを
含むログを再生することができる。

【００１４】強制的ログ書込みがコミットプロトコルに
含まれない場合は、このレコードは非同期的に、即ち主
メモリー17のメモリーバッファにのみ書込まれ、次に若
干後の時刻、例えば、強制的ログ書込みが偶然行われる
時又はそのレコードを含むバッファが満杯の時にディス
ク18に移される。ログレコードを送る処理は、安定な記
憶装置18への書込みの完了を待たずに実行が続けられ
る。従って、メモリー17へのログ書込みの後で且つディ
スク18への書込みの前にサイトがクラッシュした場合
は、このレコードはクラッシュを切り抜けられない。こ
のように、強制的なログ書込みはかなり強力（残存が確
実である）であるが、ログを強制する処理の効率が阻害
されること、即ち、応答時間が増加することが問題であ
る。ＣＰＵ16によってメモリー17に書込むために用いら
れる時間は、多分、数ＣＰＵサイクル（例えば、数百ナ
ノ秒）であるが、ディスク18への書込み完了の確認を受
信するために必要な時間は多分、数ミリ秒であり、即ち
10,000倍大きい。従って、効率の観点から、可能な限り
強制書込みを避けることが必須である。

【００１５】本発明の新しい特徴を説明する前に、前記
の参考文献において（Mohan 及びLindsay によって）与
えられた説明を用いて、標準的な２フェーズコミットプ
ロトコル、並びに仮定アボート及び仮定コミットと呼ば
れる変形を、背景として説明する。

【００１６】コミットプロトコルはいくつかの要件を持
っている。第１に、それはトランザクションのアトム性
を保証しなければならない。トランザクションがコミッ
トされると、そのコミットは全面的に完結した状態に達
するか又は全面的に完結しない状態かいずれかである。
部分的な完結はあり得ず、従って、コミット動作の間に
サイト又は分散システムのいずれかの部分がクラッシュ
すると、システムは部分的に完結した部分の全てを削除
した状態に復旧しなければならない。第２に、システム
が、或る時間の後にコミット処理の結果を「忘れる」こ
とができなければならない。即ち、クラッシュが起きな
い場合はそのデータを必要とする可能性が時間と共に急
速に減少するので、古いデータの保持を継続しない。第
３に、効率の面から、ログ書込みとメッセージ送信のオ
ーバーヘッドを最小にすることが好ましい。第４に、シ
ステムクラッシュは稀にしか起きず、大部分の時間はコ
ミットプロトコルが故障なしに動作し、ログレコードを
再生する必要はないので、従って、効率は無故障状態に
対して最適にされるべきである。第５に、読出し専用ト
ランザクションは必要性が低いので、システムの効率を
最適にすることが可能な時はいつでもこれを利用すべき
である。

【００１７】２フェーズコミットプロトコルは、図１の
システムにおけるように、ユーザーアプリケーションに
結合されたコーディネイタと呼ばれる１つ（１つだけ）
の処理及びサブオーディネイトと呼ばれる１組の他の処
理があるような、分散トランザクション実行のモデルを
使用する。図４を参照すると、データベース管理システ
ムのようなアプリケーションプログラム24は、トランザ
クションのコミット段に到達すると、コミットコーディ
ネイタと呼ばれる処理25を呼出し、次にコーディネイタ
25が制御を行う。サブオーディネイト処理26は、図１の
ノード11−15の分離されたそれぞれで実行する処理であ
り、コーディネイタ25は、１つのノードで実行する処理
である。

【００１８】トランザクションは、トランザクションＩ
Ｄ即ちＴＩＤと呼ばれる全体において独自の名前を持
ち、更に、処理も、処理ＩＤと呼ばれる全体において独
自の名前を持つと仮定される。処理名は更に処理の位置
（ノード）を表す。通常、処理はサイトからサイトへ移
ることはない。処理は、共同して分散トランザクション
の機能を遂行する。

【００１９】図５及び６を参照すると、２フェーズコミ
ットプロトコルが、先ず、無故障条件で記載されてい
る。アプリケーション24（ユーザー）がトランザクショ
ンのコミットを必要とする点に到達すると、メッセージ
又はコマンド（「コミットトランザクション」コマン
ド）がコーディネイタ25に送られる。これは図５の番号
27で示される。コーディネイタ25は、コミットプロトコ
ルのフェーズ１を開始し、各サブオーディネイト26に並
列に「プリペア」メッセージを送信し、それぞれに対し
て、トランザクションがコミットされるように準備され
ているか否かを問い合わせる。これは番号28で示され
る。図６には、サブオーディネイト処理26の動作が示さ
れている。各サブオーディネイト26が、番号29で、プリ
ペアメッセージを受信し、各サブオーディネイトは先
ず、番号30で、トランザクションがコミットされるよう
にする意志があるか否かを決め、その意志がある場合
は、第１に番号31で「プリペア」ログレコードの強制書
込みを行い、第２に番号32で「イエス投票」メッセージ
をコーディネイタ処理25に送信する。次に番号33で各サ
ブオーディネイト26はコーディネイタ25からの「コミッ
ト」又は「アボート」のメッセージを待つ。「イエス投
票」送出処理は準備完了状態といわれる。この処理は図
７及び８に示されるような状態図によっても表される。
この図においては、コーディネイタ及びサブオーディネ
イト処理はそれぞれアイドル状態27a 又は29a を持つ。
この状態では、サブオーディネイト処理は番号31で準備
完了レコードの強制書込みを行うと準備完了状態31a に
行く。トランザクションがアボートされることを望んで
いる各サブオーディネイト26は、図６の番号34で、第１
にそのログにアボートレコードの強制書込みを行い、次
に番号35で「ノー投票」をコーディネイタ25に送信す
る。「ノー投票」は拒否権であり、このような「ノー投
票」を送信するサブオーディネイト26は、コーディネイ
タ25によってこのトランザクションがアボートされるで
あろうと理解し、従って、サブオーディネイト26は、番
号36で、このトランザクションをアボートし、そのロッ
クを解除し、その揮発性記憶装置の中のこのトランザク
ションについての情報を保持しない（このトランザクシ
ョンを「忘れる」）。図７の状態図において、番号34
で、サブオーディネイト処理はアボートレコードの強制
書込みを行ってアイドル状態を続ける。

【００２０】図５において、コーディネイタ25がサブオ
ーディネイト26から投票を受信した後、２フェーズプロ
トコルの第２フェーズが開始される。番号37で全ての
「イエス投票」を受信した場合はコーディネイタ25はコ
ミット状態に移り、番号38で、「コミット」レコードの
ログ強制を行い、全てのそのサブオーディネイト26に対
して「コミット」メッセージを送信する。番号38で、永
久記憶装置18に強制ログ書込みが完了すると、このトラ
ンザクションはコミット点を通過し、番号39で、アプリ
ケーション処理24に「完了」メッセージを送信すること
ができる。図８において、番号38で、コミットレコード
の強制ログがこの処理をコミット状態38aに移す。コミ
ット点を通過すると、図５の番号40で、そのトランザク
ションがコミットされる旨のメッセージがユーザーに送
られる。図６において、番号33で、コミットメッセージ
を受信した各サブオーディネイト26はコミット状態に移
り、番号41で、コミットレコードの強制書込みを行い、
番号42で、コーディネイタ25に「アクノリッジ」メッセ
ージを送信し、次いでそのトランザクションをコミット
（ロック解除等）し、そのトランザクションを「忘れ
る」。図７において、番号41での強制書込みにより、こ
の処理はアイドル状態29a に戻る。しかしながら１つで
も「ノー投票」があると、コーディネイタ25（図５）が
アボート状態に移る原因になり、この状態では、番号43
で、アボートレコードの強制書込みが行われ、番号44
で、準備状態にあるサブオーディネイトにのみ「アボー
ト」メッセージが送信される。図８において、番号43で
の強制書込みにより、コーディネイタ処理はアイドル状
態27a に移る。図６において、番号33で、サブオーディ
ネイト処理が「アボート」メッセージを受信すると、そ
れはアボート状態に移り、番号45で、アボートレコード
の強制書込みを行い、次いでコーディネイタ25にアクノ
リッジメッセージを送信し（番号46）、そのトランザク
ションをアボートし、それを「忘れる」（番号47）。こ
れは図７の状態図に示され、番号45でのアボートレコー
ドの強制ログにより、この処理は準備状態31a からアイ
ドル状態29a に移る。図５において、コーディネイタ処
理25は、番号48で、フェーズ２でメッセージを送信され
ていた（番号40）全てのサブオーディネイト26からアク
ノリッジメッセージを受信した後、番号49で、エンドレ
コードを書込み、そのトランザクションを「忘れ」、図
８の状態図でアイドル状態27a に戻る。

【００２１】番号42及び46において、サブオーディネイ
ト26がアクノリッジメッセージを送信するとの要件によ
り、番号48で、コーディネイタ25は、全てのサブオーデ
ィネイトが結果（コミット又はアボート）を知っている
ことを確認できる。アクノリッジメッセージが送信され
る前における、番号41又は45での各サブオーディネイト
がコミットレコード又はアボートレコードの強制書込み
を行う要件は、サブオーディネイト処理26がコーディネ
イタ25に対して、「コミット」又は「アボート」メッセ
ージをアクノリッジした後は、故障の場合でも最終結果
について質問してはならないことを意味する。一般的な
原理は、番号42及び46において、サブオーディネイト26
がアクノリッジメッセージを送ると、それにより、番号
41又は45での強制ログレコードにより、アクノリッジの
前に、このサブオーディネイトは決してコーディネイタ
25に対して、そのアクノリッジメッセージの内容につい
て質問をしないことである。この原理はトランザクショ
ンのアトム性を保証するために必要である。

【００２２】図９によれば、いずれかのサイト11−15に
おける処理によって行われたログ動作によって生成され
たログ22におけるレコード54は、例えば「プリペア」
「エンド」等のレコードの型を与えるタイプフィールド
55、レコードを書込む処理（処理ＩＤ）の識別子のため
のフィールド56、コーディネイタ処理25の識別子のため
のフィールド57、及び、サブオーディネイトによって書
込まれたプリペアレコードについて、フィールド58への
書込み者によって保持されているロックの名前、又は、
コーディネイタによって書込まれたコミット又はアボー
トレコードについて、フィールド59に書込まれたサブオ
ーディネイトの名前及びフィールド60に書込まれたトラ
ンザクションＩＤ（ＴＩＤ）を含む。別の他のログレコ
ードは同様のフィールドに他の必要な情報を有する。こ
れらのログレコードは、故障の際に実行している処理の
状態を再現するための復旧処理を可能にする。

【００２３】図５−８の古典的な２フェーズプロトコル
の実行の間、アボート又は故障がない場合は、各サブオ
ーディネイト26は２つ、即ち、番号31及び41のコミット
するトランザクションについてのプリペアレコード及び
コミットレコードの強制書込みを行い、２つのメッセー
ジ、即ち、番号32のイエス投票及び番号42のコミットア
クノリッジを送信する。この状態で、コーディネイタ処
理25は、各サブオーディネイト26に２つのメッセージ、
即ち、番号28及び40のプリペア及びコミットを送信し、
１つ、即ち、番号38での「コミット」の強制書込みを行
い、１つ、即ち、番号49での「エンド」の非強制書込み
を行う。この動作は、標準２フェーズコミットプロトコ
ルタイプについての図１０のテーブルの第１行を２つの
欄に分けて要約されている。

【００２４】次に、サイト11−15又は通信リンク10の故
障の状態における標準２フェーズコミットプロトコルを
検討する。各サイト11−15は、どのサイトが故障した時
でもいつでもエンターして故障のために起動する復旧処
理62（図４）を持つと仮定する。復旧処理62の一例が図
１１に示されている。復旧処理62は、他のサイト11−15
における他の復旧処理62からの全てのメッセージを処理
し、そのサイトの最近の故障の時にコミットプロトコル
25を実行していた全てのトランザクションを処理する。
再スタートから起動されたクラッシュからの復旧の部分
として、復旧サイトにおける復旧処理62は、番号64で、
安定な記憶装置18上のログ22を読み取り、番号65で、ク
ラッシュの時にそのコミットプロトコルを実行していた
トランザクションに関する情報を揮発性記憶装置17に蓄
積する。この揮発性記憶装置中の復旧情報リストは、そ
のサイトでそれらのコーディネイタ25を持っていたトラ
ンザクションについての、他のサイト11−15からの質問
（番号66）に回答するために使用され、且つ、そのサイ
トにコーディネイタを持っていたトランザクションにつ
いてのサブオーディネイト26を持っていた他のサイトに
対して、未請求の情報を送信するために使用される。揮
発性記憶装置17中に情報リストを持つことにより、ディ
スク記憶装置18中のログ22を参照する必要がないので、
遠隔サイトの質問（番号66）に迅速に回答することがで
きる。

【００２５】復旧処理62は番号65で集めた情報リストを
通して続けられ、そのログ22中のレコード54から、この
サイトが特定のトランザクションＩＤに対する準備状態
のサブオーディネイトであったことが見出される場合
（番号67）は、復旧処理はそのトランザクションが解決
されるべき方法を発見するため、周期的にコーディネイ
タ処理25への接触を試みる（番号67a ）。このコーディ
ネイタ処理がトランザクションを解決し、質問サイトに
最終的な結果を伝えるためにコミット又はアボートメッ
セージを送る場合（番号67b ）は、復旧処理は上記の図
６の番号33に示された、サブオーディネイトが「コミッ
ト」又は「アボート」メッセージを受信するときのシー
ケンスに入る。復旧処理が、クラッシュ時にトランザク
ションが実行されていたこと、及びコミットプロトコル
（番号27）が未だ書込まれていない（番号68）ことを見
出した場合は、復旧処理は、それがこのトランザクショ
ンＩＤのサブオーディネイト又はコーディネイタのいず
れを処理していたかを知らず又は関心を持たない。それ
は、アクションがあってもそれを「行わなず」、「行わ
ない」ログレコードを用い、番号68a で、ログに「アボ
ート」レコードを書込むことにより、そのトランザクシ
ョンをアボートし、そのトランザクションを「忘れ
る」。番号69で、復旧処理がコミット状態（ログされた
コミット、番号38）のトランザクションを発見した場合
は、それは、番号69a で、周期的に「コミット」（図５
の番号40）を、準備状態（番号41）としてリストされて
いる全てのサブオーディネイトに送ることを試み、番号
69b で、それらのアクノリッジメッセージを待つ。又
は、復旧処理が、番号70で、アボート状態（図５の番号
43）のトランザクションを発見した場合は、それは、番
号70a で、周期的に「アボート」メッセージを、準備状
態（番号44）としてリストされている全てのサブオーデ
ィネイトに送ることを試み、番号70b で、それらのアク
ノリッジメッセージを待つ。両者の場合において、全て
のアクノリッジメッセージを受信してしまうと、復旧処
理62は「エンド」レコードを書込み（番号49）、このト
ランザクションを「忘れる」。

【００２６】コーディネイタ処理25が、サブオーディネ
イトから投票（番号37）が送られるのを待つ間に、その
サブオーディネイト処理26の故障を知った場合は、この
コーディネイタは、上記の番号43、44等で定められたス
テップで、このトランザクションをアボートする。又
は、この故障が、番号48で、コーディネイタがアクノリ
ッジメッセージの受信を待っている時に知らされた場合
は、このコーディネイタは復旧処理62に制御を引き渡
す。サブオーディネイト処理26が、イエス投票を送り
（番号32）準備状態31a に入る前にコーディネイタ処理
25の故障を知った場合は、このサブオーディネイトはト
ランザクションをアボートする（ノー投票を送る一方的
なアボート、番号34）が、他方、サブオーディネイトが
準備状態31a に入った後にこの故障が起きた場合は、サ
ブオーディネイトはトランザクションの制御を復旧処理
62に引き渡す。

【００２７】復旧処理62がトランザクションＩＤについ
て準備状態のサブオーディネイトサイトから質問メッセ
ージを受信した場合は、揮発性記憶装置中の情報で調べ
る。それが、トランザクションがアボート状態又はコミ
ット状態にあるとの情報を持っている場合は、それは適
当な回答を送る。そのトランザクションについての情報
が揮発性記憶装置中に見つからない場合には、どのよう
なアクションをとるべきかとの自然な疑問が起きる。こ
のような状態が起こり得る場合を確認するための検査に
よれば、「コミット」及び「アボート」共にアクノリッ
ジされるので、この質問は、被質問者がそのトランザク
ションを「忘れる」前に、質問者が「コミット」又は
「アボート」を受信せず処理していないことを意味する
ということが分かる。このような状態は、(1) 被質問者
が「プリペア」メッセージを送出し、(2) それが全ての
投票を受信しコミット又はアボートを決める前にクラッ
シュし、且つ(3) 再スタートする際に、それがトランザ
クションをアボートし、いずれのサブオーディネイトに
ついても何も知らせない場合に起きる。再スタートする
際に、そのトランザクションについてのコミットプロト
コルログレコードは何も存在していないので、それがコ
ーディネイタなのか又はサブオーディネイトなのかを、
被質問者が知ることはできない。この事実により、情報
がない場合の質問に対する正しい回答は「アボート」メ
ッセージであり、従って「仮定アボート」と名付けられ
る。

【００２８】２フェーズコミットプロトコルの所謂「仮
定アボート」バージョンは、トランザクションについて
の情報が全くない状態で、復旧処理62が、質問するサブ
オーディネイトにアボートすることを指示するという概
念に基づいている。検査によれば、アボートする（例え
ばノー投票を受信することによって）ことを決定し、番
号43で、アボートレコードを書込んだ後、直ちにトラン
ザクションを忘れることがコーディネイタ処理25にとっ
て安全であることを示している。これは、アボートレコ
ードが（番号43でコーディネイタにより、番号34及び45
で各サブオーディネイトにより）強制される必要がない
こと、及びアボートに対してアクノリッジ（番号46）が
（サブオーディネイトによって）送られる必要がないこ
とを意味する。更に、コーディネイタ処理は、アボート
レコード54（番号43）中にサブオーディネイトの名前を
記録する必要がなく、アボートレコードの後にエンドレ
コードを書込む必要がない。更に、コーディネイタ処理
25が、サブオーディネイトに対してアボートメッセージ
（番号44）を送ろうとしている間にサブオーディネイト
の故障を知った場合は、コーディネイタは、トランザク
ションを復旧処理62に引き渡す必要はない。サブオーデ
ィネイトのサイトの復旧処理62が質問メッセージを送る
場合は、サブオーディネイトがアボートの理由を見出す
ようになっている。これらの、仮定アボートプロトコル
を生成するための、標準２フェーズコミットプロトコル
からの変更は、トランザクションのコミットに関するロ
グ書込み及びメッセージ送信についてのプロトコルの性
能を変えてはいない。図１０のテーブルの第２行目に、
仮定アボートプロトコルについての必要な動作が要約さ
れている。

【００２９】リードオンリー（部分的に又は完全に）の
トランザクションはコミットするトランザクションのダ
イナミックスを変え、プロトコルはこの事実を利用する
ために変えられる場合がある。トランザクションの或る
処理がデータベースへの書込み（更新）を全く実行せ
ず、一方他の処理が書込みを行う場合は、このトランザ
クションは部分的にリードオンリーである。データベー
スに書込む処理を全く実行しない場合は、トランザクシ
ョンは完全にリードオンリーである。

【００３０】図１２を参照すると、２フェーズコミット
プロトコルの「リードオンリー」トランザクションを考
慮するため、サブオーディネイトがプリペアメッセージ
（番号29）を受信すると、それは、先ず番号80でそのロ
グを検査して、データベースに対して更新を行ったか否
か（即ち、「未」か「再」かいずれのログレコードが書
込まれているか）を決定する。これが否の場合は番号81
でコーディネイタに「読取り」投票を送り、そのロック
を解除し、番号82で、そのトランザクションを忘れる。
この場合、このサブオーディネイトはログレコードを書
込まない。それはアイドル状態に戻るだけである。この
サブオーディネイト処理26に関する限り、そのトランザ
クションが最終的にアボートされたかコミットされたか
は無関係である。従って、コーディネイタにここで「リ
ードオンリー」として知られるこのサブオーディネイト
は、コーディネイタによって「コミット」又は「アボー
ト」メッセージを送られることは必要としない。図１０
のテーブルには、列に「リードオンリー」及び「更新」
トランザクションについて記載されている。

【００３１】図１３を参照すると、コーディネイタ処理
がリードオンリーであり、「読取り」投票のみを受取る
場合は、２フェーズプロトコルの第２フェーズは存在し
ない。番号83でコーディネイタ処理が、自身がリードオ
ンリーであることを決定し、次に番号84で、全てのサブ
オーディネイトが読取り投票を送ったことを知る。この
場合、コーディネイタは、サブオーディネイトと同様
に、トランザクションについてのログレコードを全く書
込まない。他方、コーディネイタ又はサブオーディネイ
トの１つがイエス投票を行い、ノー投票を行うものがな
い場合は、そのコーディネイタは標準２フェーズコミッ
トプロトコルにあるように振る舞う。しかし、コーディ
ネイタとしては、コミットレコード54に、（存在すれ
ば）イエス投票（これらの処理のみが準備状態にあり、
従ってコミットメッセージが送られる）を行ったサブオ
ーディネイトの識別子のみを含むだけで充分であること
に注意すべきである。コーディネイタ又はサブオーディ
ネイトの１つがノー投票を行う場合、このコーディネイ
タは図５で既に説明したように振る舞う。

【００３２】完全にリードオンリーのトランザクション
については、コーディネイタもいずれのサブオーディネ
イトもログレコードを全く書込まず、各サブオーディネ
イトに対して、それぞれのサブオーディネイトが１つの
メッセージ（読取り投票）を送り、コーディネイタが１
つのメッセージ（プリペア）を送る。この動作は図１０
のテーブルの２行目のリードオンリーの列に記載されて
いる。

【００３３】部分的にリードオンリーのトランザクショ
ンについては、コミットの場合、コーディネイタが更新
サブオーディネイトに、番号28でプリペアと番号40でコ
ミットとの２つのメッセージを送り、他のサブオーディ
ネイトには、図１３に示すように、１つのメッセージ、
プリペアを送る。少なくとも１つの更新サブオーディネ
イト処理が存在する場合は、コーディネイタは２つのレ
コードを（図５から分かるように、番号38で強制的なコ
ミットを、番号49で非強制的なエンドレコードを）書込
むが、他の場合は１レコード（番号85で強制的なコミッ
ト）のみを書込む。リードオンリーのサブオーディネイ
トは、完全にリードオンリーのトランザクションの中の
１つのように振る舞い、更新サブオーディネイトは、図
６の標準２フェーズコミットプロトコルの中のコミット
トランザクションのサブオーディネイトのように振る舞
う。この動作は図１０のテーブルの２行目に記載されて
いる。

【００３４】２フェーズコミットプロトコルに対してこ
れらの変更を行うことにより、所謂仮定アボートプロト
コルが作られる。仮定アボートの名は、情報のない場合
に、トランザクションがアボートされたと仮定され、質
問に対する復旧処理の応答がアボートメッセージである
ことに基づいている。

【００３５】仮定コミットプロトコルは仮定アボートプ
ロトコルの代替である。大部分のトランザクションはコ
ミットすることが期待されており、問題は次のようなも
のである。即ち、アボートメッセージ（標準では図６の
番号46）に対するアクノリッジメッセージを要求するこ
とによって、コミットメッセージに対するアクノリッジ
メッセージ即ちＡＣＫ（図６の番号42）を省略すること
により簡単にコミットを行うことができるか、という問
題である。簡単化の概念は、アボートがアクノリッジさ
れることが必要とされ、一方、コミットはそれを必要と
せず、更に、アボートレコードが強制され、他方、サブ
オーディネイトによるコミットレコードは強制される必
要はない、ということである。その結果は、情報がない
場合には、サブオーディネイトが質問する時に、復旧処
理はコミットメッセージで回答することである。しかし
ながら、このアプローチについては、他の状態について
も考慮する必要がある。

【００３６】コーディネイタ処理が番号28のプリペアメ
ッセージを送り、１つのサブオーディネイトが既に準備
状態に移り、そして、コーディネイタが全ての投票を集
めて番号37の決定を行うことができる前に、コーディネ
イタがクラッシュする場合を考える。このような状態で
は、コーディネイタはコミットプロトコルログレコード
（番号38）を何も書込んでいない。クラッシュしたコー
ディネイタのサイトが復旧すると、その復旧処理はこの
トランザクションをアボートし、サブオーディネイトに
ついて利用できる情報は何もないので、何の情報も出さ
ずにそれを「忘れる」。続いて、準備済のサブオーディ
ネイトのサイトの復旧処理62がコーディネイタサイトに
質問する時は、その復旧処理はコミットメッセージで応
答することになり、許容できない矛盾を引き起こすこと
になる。

【００３７】この状態から抜け出す方法は、コーディネ
イタ処理としては、サブオーディネイトの内のいずれか
が準備済の状態に入る前に、安定記憶装置にレコード54
によってサブオーディネイトの名前を安全に記録するこ
とである。このようにすれば、番号28のプリペアメッセ
ージの送出後に起きたクラッシュからの復旧の際に、コ
ーディネイタサイトがアボートする時に、再スタート処
理は、そのアボートを誰に知らせ（且つ誰からアクノリ
ッジを得）るべきかを知ることになる。これらの修正は
仮定コミットプロトコルを与える。この名称は、情報が
ない場合にはトランザクションがコミットしたものと仮
定し、従って質問に対する応答はコミットメッセージで
あるということから起こる。

【００３８】図１４を参照すると、仮定コミットプロト
コルにおいては、コーディネイタ処理は、以下の例外を
除いて仮定アボートにおけるように振る舞う。例外は、
(1)第１フェーズの開始時（即ち、プリペアメッセージ
の送出前）に、番号86で、全てのサブオーディネイトの
名前を含む収集レコード54を強制的に書込み、収集状態
に移ること、(2) 番号38及び43でコミットレコード及び
アボートレコードの両者を強制的に書込むこと、(3) 番
号46で、アボートに対してのみサブオーディネイトから
のアクノリッジを要求し、コミットに対してはこれを要
求しないこと、(4) アボートレコードの後（収集レコー
ドが書込まれた後にアボートがなされた場合）にのみ番
号49でエンドレコードを書込み、コミットレコードの後
ではこれを行わないこと、(5) アボート状態にある時に
のみ、（サブオーディネイトの故障の通知と共に）トラ
ンザクションを復旧処理62に引き渡すこと、及び(6) 完
全にリードオンリーのトランザクションの場合には、仮
定アボートにおける第１フェーズの終わりに何のレコー
ドも書込まない（図１３）が、仮定コミットにおいては
番号87でコミットレコードを書込み、次にそのトランザ
クションを「忘れる」ことである。

【００３９】図１５を参照すると、仮定コミットに対し
て、サブオーディネイトは、番号45で、ここではアボー
トレコードのみを強制的に書込み、コミットレコードは
書込まず、番号46で、アボートのみをアクノリッジし、
コミットはアクノリッジしないことを除いて、仮定アボ
ートにおけると同様に振る舞う。再スタートの際には、
復旧処理62が、番号86で特定のトランザクションについ
ての収集レコード54が書込まれ且つその後には他のレコ
ードがないことを見出した場合は、それはアボートレコ
ードを強制的に書込み、全てのサブオーディネイトに通
知し、それらからアクノリッジを受取り、エンドレコー
ドを書込み、そのトランザクションを「忘れる」。情報
がない場合は、復旧処理は質問に対してコミットメッセ
ージで答する。

【００４０】仮定コミットにおいては、完全にリードオ
ンリーのトランザクションについては、コーディネイタ
が２つのレコード（番号86での強制的な収集、及び番号
87での非強制的なコミット）を書込み、番号28で、各サ
ブオーディネイトに対して１つのメッセージ、即ちプリ
ペアを送出する。サブオーディネイトはログレコードの
書込みは行わず、それぞれ１つのサブオーディネイト
が、番号81で、１つのメッセージ、即ち読取り投票を送
信する。

【００４１】コミットする部分的にリードオンリーのト
ランザクションについては、コーディネイタは、更新サ
ブオーディネイトに２つのメッセージ（番号28でのプリ
ペア、及び番号40でのコミット）を送信し、他のサブオ
ーディネイトには１つのメッセージ（番号28でのプリペ
ア）を送信し、２つのレコード（番号86での強制的な収
集、及び番号38での強制的なコミット）を書込む。リー
ドオンリーのサブオーディネイトは完全にリードオンリ
ーのトランザクションにおけるサブオーディネイトと全
く同様に振る舞い、更新サブオーディネイトは１つのメ
ッセージ（番号32でのイエス投票）を送信し、２つのレ
コード（番号31での強制的なプリペア、及び番号88での
非強制的なコミット）を書込む。

【００４２】図１６及び１７には、仮定アボートプロト
コルについての状態図が示されている。このコーディネ
イタ処理は、アイドル状態27a から番号83及び84の経路
を通して全リードオンリー状態が検出されると、同一の
アイドル状態に戻る。ノー投票が受信されてコミットプ
ロトコルがアボートする場合は、それは番号44を含む経
路によってアイドル状態に戻る。コミットレコードの強
制的な書込みの場合は、それはコミット状態38a に移
り、次いで番号49でエンドレコードの強制的な書込みが
行われるとアイドル状態に戻る。図１７のサブオーディ
ネイト処理は、このサブオーディネイトが番号80及び81
を含む経路を経てリードオンリーであることが決定され
ると、同様に、アイドル状態29a から同一のアイドル状
態に戻る。又は、この処理が、番号35を含む経路を経て
アボートされると、それはアイドル状態に戻る。強制書
込みのプリペアレコードが番号31で書込まれると、この
処理はプリペア状態31a に移る。それは、番号41での強
制書込みコミットレコードによるか、又はアボート（非
強制的）によるか、いずれかによってアイドル状態に戻
ることができる。

【００４３】図１８及び１９には、仮定コミットプロト
コルについての状態図が示されている。コーディネイタ
処理は、先ずアイドル状態27a から、番号86での収集レ
コードの強制書込みに基づいて収集状態86a に移る。こ
れは、番号87でのコミットレコードの書込みによって全
リードオンリー状態が検出されるとアイドル状態に戻
る。ノー投票が受信された場合は、番号43で、アボート
レコードを強制的に書込んでアボート状態43a に移る。
続いてこれは、番号49で、エンドレコードを書込んでア
イドル状態に戻る。図１９の仮定コミットについてのサ
ブオーディネイト処理は、コミットレコード41に代わっ
てアボートレコードが強制的に書込まれることを除い
て、図１７の処理と同じである。

【００４４】上述の３つのコミットプロトコルの性能が
図１０のテーブルに要約されている。この３つの従来の
プロトコルは、(1) 標準２フェーズコミット、(2) 仮定
アボートを持つ２フェーズコミット、及び(3) 仮定コミ
ットを持つ２フェーズコミットである。標準２フェーズ
コミットにおいては、全てのトランザクションが完全に
更新トランザクション（非リードオンリー）であるよう
に見える。従って、期待されているように、リードオン
リーのトランザクションについて、強制書込みの或る部
分及びメッセージのオーバーヘッドが減少するので、仮
定アボートプロトコルは標準２フェーズより良い性能を
示す。更に、仮定アボートプロトコルは、完全にリード
オンリーのトランザクションの場合に、コーディネイタ
による２つのログ書込み（１つは強制的）を節約できる
ので、仮定コミットより良い性能を示す。コーディネイ
タのみが更新できる部分的にリードオンリーの場合は、
強制書込みがコーディネイタによって節約されるので、
仮定アボートプロトコルは更に良い性能を示す。両方の
状態において、仮定アボート又は仮定コミットで同一数
のメッセージが送られる必要がある。ただ１つの更新サ
ブオーディネイトを持つトランザクションの場合、仮定
アボート及び仮定コミットは、ログ書込みに関しては同
等であるが、仮定アボートは、余分のメッセージ、即ち
更新サブオーディネイトによって送られるアクノリッジ
を必要とする。１を超える更新サブオーディネイトを持
つトランザクションの場合、仮定アボート及び仮定コミ
ットの両者が、同数のレコードの書込みを必要とする
が、仮定アボートは、更新サブオーディネイトの数から
１を減じた数に等しい多数の強制書込みを持つことにな
り、一方、仮定コミットはこれらの強制書込みを持たな
いことになる。これらの強制書込みは、サブオーディネ
イトによるコミットレコードの強制に対応する。これに
加えて、仮定アボートは、更新サブオーディネイトの数
に等しい多数の余分のメッセージ、即ちアクノリッジを
送ることになる。

【００４５】特定の分散データベースに対して走ること
が期待されているトランザクションの混合に依れば、仮
定アボートと仮定コミットとの間の選択を行うことがで
きる。この選択は、システム全体を基にするのではな
く、コーディネイタによって２フェーズコミットの第１
フェーズの開始時に、トランザクションとトランザクシ
ョンとを繋ぐことを基本として行われる。この方法が採
用されると、コーディネイタは、選択されたプロトコル
（仮定コミットか仮定アボートか）の名前をプリペアメ
ッセージに含め、全ての処理が、それぞれが書込む第１
コミットプロトコルログレコードにこの名前を含む。こ
の名前は、更に再スタート処理によって送られる質問メ
ッセージに含まれ、この情報は、復旧処理において、情
報がない場合における質問に応答する時に利用される。

【００４６】本発明によれば、仮定コミットプロトコル
の修正バージョンは強制書込みを省略することによって
改善された性能を具える。この修正バージョンも、図１
０のテーブルの最下行に「仮定コミット、ログ強制な
し」として記載されている。この修正バージョンを用い
ることにより、混合トランザクション（一部リードオン
リー及び一部更新）において、強制ログのオーバーヘッ
ドを劣化せずに、仮定コミットの利点が達成される。

【００４７】非強制的仮定コミットプロトコルを用いる
場合のコーディネイタの動作を最初に説明する。この説
明は次の３つの部分：（Ａ）更新サブオーディネイトを
持つ更新トランザクション、（Ｂ）更新サブオーディネ
イトを持たない更新トランザクション、及び（Ｃ）リー
ドオンリートランザクションに分かれている。

【００４８】状態（Ａ）、即ち更新サブオーディネイト
を持つ更新トランザクションの場合は、図２０の番号27
で、コーディネイタが最初に「コミット」コマンドを受
信する。コーディネイタは続いて、図２０の番号28で、
コホートに対して、そのトランザクションをコミットで
きるか否かを質問する「プリペア」メッセージを送出す
る。この時、ログレコードは書込まれず、ログレコード
が強制されないことに注意すべきである。次に、コーデ
ィネイタは、番号90で、全てのコホートから回答を受信
するのを待つ。

【００４９】回答が適時に到着しない場合又はいずれか
のコホートが「アボート」投票をする場合には、コーデ
ィネイタは、番号91で、アボートレコード（非強制的）
を書込み、番号92で、（イエス投票をした）全てのコホ
ートに「アボート」メッセージを送る。アボートログレ
コードは（ログ上の) トランザクションを終了させるこ
とができるので、復旧処理がアクティブトランザクショ
ンのテーブルにトランザクションを保持することを必要
としない。アボートレコードは、トランザクションコホ
ートの名前を含む。全てのコホートがアボートメッセー
ジをアクノリッジすると（番号93）、コーディネイタ
は、番号94で、これを「エンド」ログレコードと共に記
録し、このトランザクションを忘れる（揮発性状態から
抜け出す）。エンドメッセージは、それ以上コホートか
らの質問が到着することはないものとして揮発性状態の
アボート情報が安全に忘れられることを記録する。

【００５０】エンドメッセージ（番号94）がログに安全
に記録される前にシステムが故障すると、復旧処理がア
ボートメッセージを再送し、アクノリッジを待たなけれ
ばならない。番号94のエンドメッセージがまだ書込まれ
ていない場合は、復旧処理は、アボートされたトランザ
クションが何時「忘れられ」てよいか、即ち何時揮発性
状態から解放されるかを知らない。これらの番号91又は
94のメッセージはいずれもログを強制されない。

【００５１】上述の方法には多数の変形が存在する。そ
の１つは、番号91の「アボート」メッセージにサブオー
ディネイトを記録しないという選択である。すると、シ
ステムが故障した場合、アボートされたトランザクショ
ンは、永久的なクラッシュに関する情報中に保持された
ものの中の１つになる。他の変形は、図２０ｂに示され
ているように、全てのサブオーディネイトからのアクノ
リッジが受信されるまでアボートメッセージを書込まな
いという選択である。このトランザクションは、（少な
くとも多くのシステムで）コミットレコードがないとア
ボートされ、これはログ書込みの節約になる。即ち、全
てのアクノリッジの後のエンドレコードの書込み（番号
94）に代えて、アボートレコードが図２０ｂの番号95で
書込まれる。これはアボートされたトランザクションに
ついての唯一のログレコードである。繰り返すと、トラ
ンザクションがアボートされた状態を記述する情報は永
久的なクラッシュに関する情報の一部になる。

【００５２】図２０の番号90で、全てのコホートが適時
に（コミットするための）「イエス」投票で回答する場
合は、番号96で、コーディネイタがコミットログレコー
ドを書込む。このログレコードは強制的であり、トラン
ザクションの耐久性を確実にする。アクノリッジメッセ
ージが期待されないので、コホートの名前は含まれな
い。更に、コホートからのアクノリッジメッセージが期
待されないので、エンドログレコードは必要ない。

【００５３】先行特許出願においては、グローバルトラ
ンザクションの順序性を保証する助けにするため、タイ
ムスタンプが用いられた。この技術を用いると、コミッ
トレコードは、そのトランザクションについてのタイム
スタンプを含むことが必要である。

【００５４】図２０ａ又は２０ｂの方法を用いる場合、
最も古いＴＩＤ（以下ではＯ＿ＴＩＤと記す）は、以前
のクラッシュ以来最も古いアクティブなトランザクショ
ンＩＤのトランザクションＩＤに関する限界である。こ
の最も古いトランザクションがコミット又はアボートす
る場合には、（非連続ＴＩＤの場合）いつでも、そのコ
ミットレコード及びアボートレコードを、最も古い現在
アクティブなトランザクションに対するレコードとして
マークすることができる。このようにして最近にマーク
したレコードが、クラッシュに関する持続情報について
のＯ＿ＴＩＤになる。

【００５５】図１０を参照すると、図２０ａ又は２０ｂ
の方法においてコミットの場合、このコーディネイタの
アクティビティのメッセージ／ログコストは、書込まれたレコード１（強制１）各Ｒ−Ｏサブオーディネイトに対するメッセージ１各更新サブオーディネイトに対するメッセージ２である。

【００５６】状態（Ｂ）、即ち更新サブオーディネイト
を持たない更新トランザクションの場合は、コーディネ
イタの動作は、更新サブオーディネイトがないことを除
いて状態（Ａ）と同じである。

【００５７】状態（Ｃ）、即ちリードオンリートランザ
クションの場合について、コーディネイタの動作を説明
する。番号90で、全てのサブオーディネイトについての
投票が受信されるまで、上述のプロトコルにおいては、
ログレコードは何も書込まれない。全てのコホートが
「リードオンリー」を投票すると、そのトランザクショ
ンはリードオンリートランザクションである。この場
合、流れは、図２０ａの番号90から経路98を経て「トラ
ンザクションを忘れる」ステップ50に向かう。ここで
は、全てのコホートがそれらのログへの書込みなしに終
了し、このトランザクションを「忘れる」。従って、コ
ーディネイタにとってどのようなログレコードも書込む
必要はない。システムが故障（クラッシュ）した場合
は、仮定コミット要求を記録するために導出される情報
は、リードオンリートランザクションがどの程度クラッ
シュに近くで終了したかによって異なる結果を示唆す
る。このトランザクションについてのＴＩＤがＯ＿ＴＩ
Ｄより大きい場合は、トランザクションはアボートされ
るべきであるように見える。Ｏ＿ＴＩＤより小さい場合
は、コミットされるべきであるように見える。しかしな
がら、質問するサブオーディネイトは存在しないので、
これは重要な問題ではない。よって記録は存在せず、こ
のトランザクションがコミットされるか又はアボートさ
れるか、いずれに見えるかは重要な問題ではない。従っ
て、この場合（図１０参照）のメッセージ／ログコスト
は、書込まれたレコード０（非強制的）各Ｒ−Ｏサブオーディネイトに対するメッセージ１である。

【００５８】問題は、アクティブプロトコルフェーズに
あり得るがそれについて安定なレコードが存在しないト
ランザクションを、このシステムが厳密に如何に扱うか
である。このトランザクションの組を限定することがで
きると、この問題は復旧処理62で扱うことができる。本
発明の実施例によれば、アクティブプロトコルフェーズ
にあるがそれについて安定なレコードが存在しないトラ
ンザクションの組を限定することができる。

【００５９】２フェーズコミットトランザクションの組
を限定するため、トランザクションの識別子（ＴＩＤ）
が単調に増加する順序で与えられると仮定する。基本的
な概念は、そのトランザクション識別子が安定に記録さ
れたトランザクション識別子（Ｓ＿ＴＩＤと記す）から
或るΔ（デルタ）の範囲内になければ、トランザクショ
ンが２フェーズコミットプロトコルを開始することを許
可しないという点にある。このようにすれば、システム
の故障の場合、Ｓ＿ＴＩＤ＋Δまでの識別子を持つトラ
ンザクションのみがアクティブであったことになる。有
効にコミットしたトランザクション（Ｃ＿ＴＩＤと記
す）は全てログに安定に記録される。アボートした可能
性のあるトランザクション（ＭＡ＿ＴＩＤと記す）は、ＭＡ＿ＴＩＤ＝｛ＴＩＤ｜ＴＩＤ＜Ｓ＿ＴＩＤ＋Δ｝−Ｃ＿ＴＩＤによって表される。即ち、有効にコミットされるべきも
のと判明しているトランザクションＩＤ（Ｃ＿ＴＩＤ）
が、Ｓ＿ＴＩＤ＋Δより小さいＴＩＤの組から差し引か
れ、その残りがＭＡ＿ＴＩＤである。このＭＡ＿ＴＩＤ
のうち幾つかのトランザクションは明確にアボートされ
た筈である（ここではＡ＿ＴＩＤと記す）。従って、不
確定なトランザクションの組（走っていたかも知れない
が全く情報がない。ここではＩ＿ＴＩＤと記す）は、Ｉ＿ＴＩＤ＝ＭＡ＿ＴＩＤ−Ａ＿ＴＩＤである。これらのＴＩＤを持つトランザクションはコミ
ットしていない。しかし、それらがアボートしたのか、
又は走らなかったのかは不明である。アボートした場合
でも、それらが２フェーズコミットプロトコルを開始し
たかどうかは不明である。従って、この組についての質
問が受信されるか否かは不明である。幾つの質問が受信
されるか、又はどのコホート（サブオーディネイト）に
よって受信されるかも不明である。しかしながら、全て
のこのような質問者は、そのトランザクションがアボー
トした旨の回答を受信するであろうことが分かる。

【００６０】Ｉ＿ＴＩＤの組のみが永久的に記録される
べきである。コホートは誰かについて、また、コホート
が幾つあるかについての情報がないと、これのガーベジ
コレクションはできない。Ｉ＿ＴＩＤの基数は通常は小
さい（例えば50-100TID 以下）。安定に記録されること
が必要な情報の量はシステムクラッシュの数に比例する
が、それ程大きくはない。安定に記録されたトランザク
ションについては、仮定コミットプロトコルに対して通
常行われるのと同様のガーベジコレクションが可能であ
る。勿論、トランザクションがコミットされた場合、
「情報なし」はコミットと仮定するので、その性質を全
て保持する必要はない。

【００６１】このように、不確定トランザクションにつ
いてのＴＩＤの組を表すこと及びその情報を安定に記録
することが必要である。Ｉ＿ＴＩＤについて選択された
表現が小さいサイズになるように選択されることが重要
である。この理由から、(i)Ｓ＿ＴＩＤの後の不確定ト
ランザクション、及び(ii)Ｓ＿ＴＩＤの前の不確定トラ
ンザクションの２部分表現が選択される。

【００６２】第１の部分、即ちＳ＿ＴＩＤの後の不確定
トランザクションは、Ｓ＿ＴＩＤとＳ＿ＴＩＤ＋Δとの
間のＴＩＤを持ち、多分実行されたであろうトランザク
ションの組であり、最良の表現は、＜Ｓ＿ＴＩＤ，Ｓ＿ＴＩＤ＋Δ＞の範囲の指定による表現である。これは、この組のこの
部分の極めて単純且つコンパクトな表現である。

【００６３】第２の部分、即ちＳ＿ＴＩＤの前の不確定
トランザクションは、コミットせず、アボートしたかも
知れず、しかしそれらのコホートについて知る情報がな
い、Ｓ＿ＴＩＤより小さいＴＩＤのトランザクションで
ある。更に、これはＴＩＤの連続した範囲ではない。Ｓ
＿ＴＩＤより小さいＴＩＤのトランザクションの或る組
はコミットし、他の組はアボートしている。

【００６４】しかしながら、下記で説明されるように決
定されるＯ＿ＴＩＤの識別子を持つ最も古いアクティブ
トランザクションが存在する。Ｏ＿ＴＩＤより古い全て
のトランザクションは、最近のクラッシュ後には既に完
了しており、それらの状態（コミット又はアボート）が
ログ中に安定に記録されている。Ｉ＿ＴＩＤのメンバー
には、このクラッシュについてＯ＿ＴＩＤより古いメン
バーはいない。従って、Ｏ＿ＴＩＤがＩ＿ＴＩＤの表現
で記録される。Ｏ＿ＴＩＤより小さいこれらのＴＩＤは
完全に知られており、正規にガーベジコレクションが可
能であるため、これらを永久的に記録することは不要で
ある。

【００６５】Ｏ＿ＴＩＤとＳ＿ＴＩＤとの間でアボート
したトランザクションは、コミットしなかったトランザ
クションである。Ｏ＿ＴＩＤの決定方法、及び、コミッ
トしなかった組を最良に表現する方法は、ＴＩＤが連続
的に与えられたか、又は非連続的に与えられたかに依存
する。

【００６６】連続的なＴＩＤの場合、コミットしなかっ
たトランザクションは確実にアボートしている。これら
のトランザクションは、最も古いアクティブトランザク
ションＯ＿ＴＩＤの名前を付けて表すのが最良であり、
どのトランザクションがそれ以後アボートしたかを厳密
に示すビットベクトル、即ち、＜Ｏ＿ＴＩＤ，アボートビットベクトル＞を記憶する。ログを検査し、コミットもせずアボートも
していない最小数を付されたＴＩＤを探し出すことによ
って、Ｏ＿ＴＩＤを見出すことができる。探し出したＴ
ＩＤがＯ＿ＴＩＤである。このことは、ＴＩＤが与えら
れている各トランザクションについてログレコードが書
込まれている（コミット又はアボート）ことが前提にな
る。

【００６７】非連続的なＴＩＤの場合、例えばタイムス
タンプの場合、そのＴＩＤには連続的な番号は付与され
ないが、やはり単調に増加している。従って、Ｓ＿ＴＩ
Ｄより小さいＴＩＤを持つ不確定のトランザクションを
表す方法は異なっている。上記と同様に、最も古いアク
ティブＴＩＤの表記としてＯ＿ＴＩＤを用いる。しかし
ながら、ＴＩＤの隙間が大きいので、ビットベクトルを
用いずに、この組はコミットされたトランザクションの
組の全数として表示され、ここではリストの形で表示さ
れる。従って、これらは、＜Ｏ＿ＴＩＤ，Ｏ＿ＴＩＤ・Ｓ＿ＴＩＤ間のコミットされたＴＩＤのリスト＞で表される。この範囲のアボートされたトランザクショ
ンの組は、まだコミットされていないと考えられるＴＩ
Ｄの組に含まれる。

【００６８】システムクラッシュを生き延びるためには
Ｏ＿ＴＩＤを識別する必要がある。このＴＩＤは、（以
前のシステムクラッシュに遡って）Ｏ＿ＴＩＤより小さ
いＴＩＤを持つ不確定のトランザクションは存在しない
ことを示す。最も古いアクティブトランザクションがコ
ミットする時は、いつでも、実際にＯ＿ＴＩＤをコミッ
トすることをコミットレコードに表示することができ
る。システムが正規に実行される間、どのトランザクシ
ョンが最も古いアクティブトランザクションであるかを
知ることができる。この情報をログに入れると、それを
システムクラッシュに対して安定にすることができる。
このように、ログは、単調に増加する一連のＯ＿ＴＩＤ
を記録することになる。クラッシュ前にログに書込まれ
た最近のＯ＿ＴＩＤは、Ｉ＿ＴＩＤを表すために用いら
れるＯ＿ＴＩＤである。この方法によれば、余分のログ
書込み／強制なしに、「コミットされたＴＩＤ」のリス
トのサイズを最小にすることができる。

【００６９】Ｉ＿ＴＩＤ情報はコミット処理及び復旧処
理によってアクセスされなければならず、この情報が永
久記憶装置18にあることが必要である。概念的には、全
てのクラッシュについてのＩ＿ＴＩＤが永久的に且つ安
定的に保持されることが必要である。Ｉ＿ＴＩＤに上記
のような表現を与えると、永久に保持されるべき情報は
比較的多くなくすることができる。クラッシュ当たりの
情報は数百バイト以下で足り、この大きさは完全に管理
できる量である。システムクラッシュが１日に１回起き
ると仮定し（これは良好に管理されているシステムとし
ては極めて高い値である）、このシステムが１週間に７
日稼働するとしても、クラッシュ関連のＩ＿ＴＩＤを１
メガバイト蓄積するのに2000日（５年以上）かかること
になる。

【００７０】最近の情報をキャッシュすることが望まし
い。Ｉ＿ＴＩＤ情報が多くなり過ぎて利用できる形で主
記憶装置17に保持することができない場合は、最近数回
のクラッシュについての情報をキャッシュしてもよい。
殆ど全てのトランザクション質問は、最近のクラッシュ
以後に完了したトランザクション又は最近のクラッシュ
の結果として中断したトランザクションに対するもので
ある。最近のものより前のクラッシュによって中断した
トランザクションに対する要求の数は極めて小さい。最
近３回（又はそれに近い数）のクラッシュを主メモリー
17に保持すれば、効率的なシステム動作にとって充分で
ある。

【００７１】最も効果的な特徴はＩ＿ＴＩＤファイルを
切り詰めることである。全く古いＴＩＤについての質問
を切り捨てることにより、Ｉ＿ＴＩＤファイルのサイズ
を制御し、小さく保つことができる。要求が切り捨てら
れるトランザクションは、「ヒューリスティックに」解
決されなければならない。即ち、それらは人間の介在を
必要とする。（多分それらを記録中で探し出すことがで
きる。）

【００７２】トランザクションコホート当たりのメッセ
ージコストの削減に関する仮定コミットプロトコルの利
点は、コミットプロトコルのスタート時に、トランザク
ションコーディネイタがログレコードの強制を行うため
のコストを不要にすることによって実現される。ユーザ
ーにとっての利益は、トランザクション処理システム
が、従来のシステムの効率を上回る効率で２フェーズコ
ミットを実行することができる点にある。

【００７３】本発明は特定の実施例について説明された
が、これらの記載は、制限的な意味に解釈されてはなら
ない。当業者にとっては、開示された実施例及び他の実
施例について多くの変形が存在することが明らかであ
る。従って、特許請求の範囲は、このような変形又は本
発明の範囲に含まれる実施例を含むものである。

【図面の簡単な説明】

【図１】本発明の実施例の方法が用いられる分散コンピ
ュータシステムを説明する図である。

【図２】図１のノードの１つの構成例を示すブロック図
である。

【図３】１つのノードで本発明のシステムが走る際のデ
ータ記憶装置のマップの一部を示す図である。

【図４】コミットプロトコルを用いるトランザクション
処理システムの実施例における種々の処理を示す図であ
る。

【図５】図４の標準２フェーズコミットプロトコルにお
けるコミットコーディネイタによって実行される処理の
論理フローチャートである。

【図６】標準２フェーズコミットプロトコルにおける図
５のコミットコーディネイタのサブオーディネイトによ
って実行される処理の論理フローチャートである。

【図７】図６のサブオーディネイト処理の状態図であ
る。

【図８】図５のコーディネイタ処理の状態図である。

【図９】メモリー又はディスク上におけるログレコード
のデータ構造の例を示す図である。

【図１０】種々の２フェーズコミットプロトコルのアク
ティビティを要約したテーブルである。

【図１１】標準２フェーズコミットプロトコルを用いる
トランザクション処理システムの１つのサイトで実行さ
れる復旧処理の論理フローチャートである。

【図１２】リードオンリートランザクションを考慮して
サブオーディネイトによって実行される処理の論理フロ
ーチャートである。

【図１３】図１２に対応しリードオンリートランザクシ
ョンを考慮してコミットコーディネイタによって実行さ
れる処理の論理フローチャートである。

【図１４】図５のコーディネイタによって実行される仮
定コミットプロトコルの論理フローチャートである。

【図１５】図６のサブオーディネイトによって実行され
る仮定コミットプロトコルの論理フローチャートであ
る。

【図１６】仮定アボートプロトコルについてのコーディ
ネイタ処理の状態図である。

【図１７】仮定アボートプロトコルについてのサブオー
ディネイト処理の状態図である。

【図１８】仮定コミットプロトコルについてのコーディ
ネイタ処理の状態図である。

【図１９】仮定コミットプロトコルについてのサブオー
ディネイト処理の状態図である。

【図２０】本発明の実施例によるコーディネイタによっ
て実行されるログ強制なしの仮定コミットプロトコルの
論理フローチャートである。

【符号の説明】

１０通信リンク１１、１２、１３、１４、１５ノード（サイト）１６ＣＰＵ１７主メモリー１８ディスク記憶装置１９システムバス２０ネットワークアダプタ２１データ記憶２２ログ２４アプリケーションプログラム２５コミットコーディネイタ２６サブオーディネイト２７ａコーディネイタのアイドル状態２９ａサブオーディネイトのアイドル状態３１ａサブオーディネイトの準備完了状態３８ａコーディネイタのコミット状態４３ａコーディネイタのアボート状態５４ログレコード５５タイプフィールド５６レコード書込み処理識別子フィールド５７コーディネイタ処理識別子フィールド５８準備済サブオーディネイト名保持フィールド５９コミット又はアボートサブオーディネイト名保持
フィールド６０トランザクション識別子フィールド６２復旧処理８６ａコーディネイタの収集状態

Claims

(57)【特許請求の範囲】

【請求項１】仮定コミット２フェーズコミットプロト
コルを用いるトランザクション処理システムの動作方法
であってトランザクションにトランザクション識別子（ＴＩＤ）
を昇順に割当てるステップ、トランザクションが、コミットする準備を済ませた時
に、コーディネイタ処理にコミットコマンドを送信し、
該コーディネイタ処理が、永久記憶装置及び揮発性メモ
リーを持つサイトで実行するステップ、ＴＩＤの１つの範囲を選択し、コミットする準備を済ま
せた前記トランザクションのＴＩＤが、ＴＩＤの前記選
択された範囲の中にあるか否かを決定するステップ、コミットする準備を済ませた前記トランザクションの前
記ＴＩＤがＴＩＤの前記選択された範囲の中にある場合
は、サブオーディネイト処理にプリペアメッセージを送
信するステップ、コミットする準備を済ませた前記トランザクションの前
記ＴＩＤがＴＩＤの前記選択された範囲の中にない場合
は、前記サブオーディネイト処理に前記プリペアメッセ
ージを送信する前に、コミットする準備を済ませた該ト
ランザクションについてのログレコードを含む揮発性の
ログレコードを前記永久記憶装置に書込み、これによ
り、該ＴＩＤをＴＩＤの選択された範囲の中に入れるス
テップを含むことを特徴とする仮定コミット２フェーズ
コミットプロトコルを用いるトランザクション処理シス
テム動作方法。
【請求項２】前記範囲が、前記永久記憶装置に既に書
込まれている以前のログレコードの最高のＴＩＤから、
選択されたＴＩＤの数だけ該最高のＴＩＤを超えたＴＩ
Ｄまでの範囲であることを特徴とする請求項１に記載の
方法。
【請求項３】結果が不確定の全てのＴＩＤのリストを
保持し、該リストが前記範囲の最高数より小さい大きさ
のＴＩＤ数を持ち、該リストが既にコミットされたか又
はアボートされた全てのＴＩＤを除外するステップを含
むことを特徴とする請求項１に記載の方法。
【請求項４】前記コーディネイタ及び各前記サブオー
ディネイトが、通信ネットワークによって相互接続され
た個々のサイトで実行するステップを含み、コミット又
はアボートされていないがそれより小さいＴＩＤは既に
コミット又はアボートされている、最小ＴＩＤ数を持つ
トランザクションのＴＩＤである最も古いＴＩＤ（Ｏ＿
ＴＩＤ）の安定なレコードを保持するステップを含み、
システムクラッシュの時刻の近くでアクティブなＴＩＤ
のレコードに、どれがアクティブであったか及びどれが
コミットされたかを記録し、このレコードを前記永久記
憶装置に保持するステップを含むことを特徴とする請求
項１に記載の方法。
【請求項５】コミットコーディネイタ及び複数のサブ
オーディネイトを含み、仮定コミット２フェーズコミッ
トプロトコルを用いるトランザクション処理システムに
おいて、前記システムで実行するトランザクションにトランザク
ション識別子（ＴＩＤ）を昇順に割当てる手段、前記システムで実行するトランザクションがコミットす
る準備を済ませた時に、永久記憶装置及び揮発性メモリ
ーを持つサイトで実行する前記コーディネイタにコミッ
トコマンドを送信する手段、ＴＩＤの１つの範囲を選択する手段、コミットする準備を済ませた前記トランザクションのＴ
ＩＤがＴＩＤの前記選択された範囲の中にあるか否かを
決定する手段、コミットする準備を済ませた前記トランザクションの前
記ＴＩＤがＴＩＤの前記選択された範囲の中にある場合
に、前記サブオーディネイトにプリペアメッセージを送
信する手段、コミットする準備を済ませた前記トランザクションの前
記ＴＩＤがＴＩＤの選択された前記範囲の中にない場合
に、前記サブオーディネイトに前記プリペアメッセージ
を送信する前に、全ての揮発性のログレコードを前記永
久記憶装置に書込み、これにより、該ＴＩＤをＴＩＤの
選択された範囲の中に入れる手段を具えることを特徴と
する仮定コミット２フェーズコミットプロトコルを用い
るトランザクション処理システム。
【請求項６】前記範囲が、前記永久記憶装置に既に書
込まれている以前のコミットレコードの最高のＴＩＤか
ら、選択されたＴＩＤの数だけ該最高のＴＩＤを超えた
ＴＩＤまでの範囲であり、結果が不確定の全てのＴＩＤ
のリストを保持し、該リストが前記範囲の最高数より小
さい大きさのＴＩＤ数を持ち、該リストがコミットされ
たか又はアボートされた全てのＴＩＤを除外することを
特徴とする請求項５に記載のシステム。
【請求項７】前記コーディネイタ及び各前記サブオー
ディネイトが、通信ネットワークによって相互接続され
た個々のサイトで実行し、コミット又はアボートされて
いないがそれより小さいＴＩＤは既にコミット又はアボ
ートされている、最小ＴＩＤ数を持つトランザクション
のＴＩＤである最も古いＴＩＤ（Ｏ＿ＴＩＤ）の安定な
レコードを保持する手段を具えることを特徴とする請求
項５に記載のシステム。