JPH10510651A - 最適化された同期化プロシージャ - Google Patents

Abstract

(57)【要約】 本発明は、データ処理システム（１００）においてトランザクションを同期化するための方法を開示する。トランザクションは、そのトランザクションに参加する複数のエージェント（１２０−１５０）及びそのトランザクションをコーディネートするための１つのコーディネータ（１１０）に影響を与える。エージェントは、それらエージェントの少なくとも１つのセット（１３０、１４０）をコーディネートする少なくともミドルマン（１２０）を含む。コミットするために使用可能であるか又は使用不能であるかを表す意思表示が各エージェント（１２０−１５０）からコーディネータ（１１０）に送られる（５１０）。コーディネータは、すべての意思表示が受信される時、コミット又はバックアウトの判断を決定する（５２０）。障害のためにその判断がミドルマン（１２０）において得られない場合、コミットするために使用可能なセットにおけるエージェント（１３０、１４０）の各々にミドルマン（１２０）から「未知」判断メッセージが送られる（５４０）。「未知」判断メッセージは使用可能なエージェント（１３０、１４０）の各々の再同期化を停止する。ミドルマン（１２０）が再同期化の責任を持つ場合、その判断がミドルマン（１２０）において得られる時、再同期化メッセージがその使用可能なエージェント（１３０、１４０）の各々に送られる（５６０）。ミドルマン（１２０）が再同期化の責任を持たない場合、「既知」判断メッセージがミドルマン（１２０）からその使用可能なエージェント（１３０、１４０）の各々に送られる（５７０）。「既知」判断メッセージの受信は使用可能なエージェント（１３０、１４０）の各々の再同期化を始動する（５８０）。

Description

【発明の詳細な説明】 最適化された同期化プロシージャ 技術分野 本発明はデータ処理システムにおけるトランザクションの同期化に関するもの であり、更に詳しく云えば、トランザクションに参加する複数のエージェント及 びそのトランザクションをコーディネートするための１つのコーディネータを含 むデータ処理システムにおいてそのトランザクションの同期化を行うための方法 に関するものである。それらのエージェントは、それらのうちの少なくとも１つ のエージェントのセットをコーディネートする少なくとも１つのミドルマン（ｍ ｉｄｄｌｅｍａｎ）を含む。その方法は、コミットするために使用可能か又は使 用不能かを表す意思表示（ｖｏｔｅ）をそれらのエージェントの各々からコーデ ィネータに送るステップ、及びすべての意思表示が受信された時、コーディネー タによるコミット又はバックアウトの判断を決定するステップを含む。 背景技術 データ処理システムでは、システム資源に対するアクセス及び更新は、一般に 、個別のトランザクション（又は、作業単位）の実行によって行われる。トラン ザクションは、変更 がすべて成功する或いは全く成功しないというような、システム資源に関する一 連のコーデイネートされたオペレーションである。これらのオペレーションは、 一般に、トランザクション処理システムにおける記憶装置に保持されたデータに 対して行われる変更である。システム資源は、データベース、データ・テーブル 、ファイル、データ・レコード等を含む。トランザクションが全体として成就さ れるか或いは全く成就されないというこの特性は、原子性（ａｔｏｍｉｃｉｔｙ ）としても知られている。 この方法では、資源は相互に不整合にならないようにされる。更新オペレーシ ョンのセットの１つが失敗する場合、他のオペレーションも成功しないであろう 。そこで、作業単位は、必ずしも中間点すべてにおける整合性を保存することな く、整合状態の資源を他の整合状態に変換する。 トランザクションの原子的性質は、コミット・プロシージャと一般に呼ばれて いるトランザクション同期化プロシージャによって維持される。資源変更がトラ ンザクション実行の範囲内で同期化される整合性の論理的ポイントは、コミット ・ポイント又は同期点と呼ばれる。アプリケーションは、同期ポイントを宣言す ることによって、或いはそのアプリケーションが終了することによって作業単位 を終了する。 トランザクションの原子性は、そのトランザクションの終了時に同期ポイント が宣言されるまで、そのトランザクションの範囲内で行われた資源更新が未確定 のまま（コミットさ れないで）保持されることによって得られる。トランザクションが成功する場合 、そのトランザクションの結果は恒久的なものにされる（コミットされる）。そ のトランザクションが失敗する場合、その不成功のトランザクションの影響はす べて除去（バックアウト）される。即ち、資源更新は、成功裏に終了した時だけ その更新を行ったアプリケーション以外のアプリケーションにとっても恒久的に 且つ可視的にされる。各作業単位の期間の間、すべての更新された資源は、更な る更新アクセスを防ぐためにロックされなければならない。それとは対照的に、 トランザクションがバックアウト（ロールバック）される時、資源は、そのトラ ンザクションが開始する前に存在した整合状態に回復される。 商業的に入手可能な多くの種々なトランザクション処理システムが存在する。 オンライン・トランザクション処理システムの一例は、ＩＢＭ社（インターナシ ョナル・ビジネス・マシーンズ・コーポレーション）によって開発されたＣＩＣ Ｓシステムである（ＩＢＭ及びＣＩＣＳは、インターナショナル・ビジネス・マ シーンズ・コーポレーションの商標である）。 トランザクション・オペレーションが実行される単一ノードを含む、或いはそ のようなオペレーションが如何なるトランザクション中でも１つのノードでしか 実行されないようにするトランザクション・データ処理システムでは、単一フェ ーズの同期化オペレーションによって原子性は強化される。 この点に関しては、トランザクションが終了する時、そのノードは、単一フェー ズにおいて、変更を恒久的にすることをコミットするか或いはバックアウトする 。 多数のノードを包含する分散システムでは、１つのトランザクションがそのよ うなノードのうちの複数のものに対して変更を行わせることがある。そのような システムでは、そのトランザクションに関与したすべてのノードがそれの結果に 同意する場合にだけ原子性を保証することができる。簡単な例は、１つの口座か ら異なる銀行における他の口座に現金振込を行うための金融アプリケーションで あり、クリティカルな資源に対する２つの基本的なオペレーション（一方の口座 における貸方及び他方の口座における借方）に関連するものである。これらのオ ペレーションの両方が成功するか或いは何れも成功しないことを保証することが 重要である。 分散システムは、一般に、原子性を保証するために、２フェーズ・コミット・ プロトコルと呼ばれるトランザクション同期化プロシージャを使用する。この点 に関しては、トランザクションが実行ノードにおいて成功裏に終了し、しかも、 すべてのノード資源マネージャ（又は、エージェント）がそのトランザクション に関与したオペレーションをコミットすることをリクエストされるものと仮定す る。そのプロトコルの第１フェーズ（準備フェーズ）では、すべての関連のエー ジェントがコミットする準備をするようにリクエストされる。それに応答して、 それらエージェントは、個々に、それらの オペレーションをコミットすべきか或いはバックアウトすべきかをローカルの状 態に基づいて判断する。これらの判断は、意思表示がカウントされる場所である コーディネータと呼ばれる同期化ロケーションに伝送される。第２フェーズ（コ ミット・フェーズ）では、すべてのエージェントがコミットするように意思表示 する場合、コミットを望むリクエストが発生され、それに応答してすべてのエー ジェントがそれらのオペレーションをコミットする。一方、何れのエージェント もそれらのオペレーションをバックアウトするように意思表示する場合、すべて のエージェントがそれらのオペレーションをバックアウトするように命令される 。大量のトランザクションを持った大型のシステムでは、その２フェーズ・コミ ット・プロセスはツリー状にエージェントを構成してもよく、その場合、エージ ェントのサブセットの１つが、そのサブセットの意思表示をコーディネートする ための及びメイン・コーディネータに結合された意思表示を送るためのミドルマ ンとして作用する。 分散システムは、システムの障害、即ち、通信障害又はノード障害から十分に 回復可能であるように編成される。通信障害及び遠隔のノードにおける障害は、 一般に、１つ又は複数のノードへのメッセージの停止によって明らかになる。そ の障害によって影響される各ノードは、種々の機構によってそれを検出すること ができる。例えば、その機構は、作業単位が事前設定の最大時間よりも長い間ア クティブであった時、 それを検出するそのノードにおけるタイマを含む。ノード障害は、一般に、その ノードの再始動を要求するソフトウエア障害又はそのノード上で走るトランザク ションの優先使用に関連したデッドロックによるものである。 システム障害は、その作業単位に関連したノードの再同期化を必要とする回復 プロシージャによって管理される。ノード障害は、一般に、その結果として揮発 性記憶装置における情報の喪失を生じるので、作業単位に関連した如何なるノー ドも、２フェーズ・コミット・プロトコル時にメッセージの伝送と同期して不揮 発性記憶装置に状態変化（チェックポイント）を書き込まなければならない。こ れらのチェックポイント・データ（又は、ログ・メッセージ）は、そのプロトコ ルが進行する時に安定した記憶媒体に書き込まれ、ノードの障害の場合に同じプ ロトコルが整合状態から再始動されることを可能にする。これは再同期化として 知られている。 米国特許第５,３１１,７７３号は、開始アプリケーションが他のタスクを進行 させることを可能にしながら、コミット・プロシージャを障害後に非同期的に再 同期化する方法を開示している。しかし、それは、分散作業単位に関与する複数 のパートナ・ノードへのコミュニケーションの中断という問題を処理するもので はない。 インターナショナル・ビジネス・マシーンズ・コーポレーションによって開発 されたＩＢＭシステム・ネットワーク・アーキテクチャ、即ち、ＩＢＭ ＳＮＡ ＬＵ６.２同期点アー キテクチャは、２つ又はそれ以上の保護された資源相互間のコミットをコーディ ネートするものとして知られている。そのＬＵ６.２アーキテクチャは、資源コ ーディネーション、同期点ロギング、及び回復に責任のある同期点マネージャ（ ＳＰＭ）をサポートする。このアーキテクチャにおいて使用される通信プロトコ ルの説明は、「ＬＵ６.２のためのＳＮＡピア・プロトコル（SNA Peer Protocol s for LU6.2）」（文献番号ＳＣ３１−６８６８−１、ＩＢＭ社）に見ることが できる。 ネットワークにまたがる２フェーズ・コミットのための既知のプロトコルによ る問題は、作業単位のコーディネータとの接触が失われた場合に対してそれらが 十分に対応しないことである。そのような場合、その結果がどのようなものであ るかを分散作業単位の他方のパートナに直ちに知らせることができない。その判 断は、コーディネータとの接触が行われた後でわかるだけである。 接触が失われた場合、接触が再び行われるまで、パートナを永久に待ち続けさ せることが可能である。それらのパートナの各々は資源ロックを保つことができ 、アプリケーション・コード及びユーザを長い時間待たせておくことが可能であ る。そこで、ロック、アプリケーション、及びエンド・ユーザ・スタリーンを解 放するために、オペレータ・アクションが必要である。 この問題に対する既知の解決方法は、パートナとのコミュ ニケーションを中断すること及びすべてのパートナ相互間の時限再試行ループに 入ることである。この従来技術の方法に伴う幾つかの欠点がある。再試行ループ は非常に非効率的であり、特に、それらを発生する多くのエージェントが存在す るか或いはそれらが頻繁に行われる場合に非効率的である。更に、コミュニケー ションの中断によりオペレーション上の問題が生じことがある。 再試行ループのタイミング次第で作業単位の結果の導出における遅れが生じ、 それは資源更新処理の同時性におけるかなりの低下を生じさせる（特に、多くの 資源が関与する場合）。ノードの再始動時には、システムを過負荷にする多くの 再同期化タスクが存在することがある。多くのコミュニケートするノードが同時 に再始動される場合、デッドロックが生じることもある。 発明の開示 従来技術の上記欠点は、本発明によるミドルマンを使用するシステムにおいて 克服される。従って、本発明は、前述のようなデータ処理システムにおけるトラ ンザクションの同期化のための方法を提供する。その方法は、障害のためにミド ルマンにおいて判断が得られない場合、コミットのために使用可能な一組のエー ジェントの各々にそのミドルマンから「未知（Ｎｏｔ Ｋｎｏｗｎ）」判断メッ セージを送るステップ（その「未知」判断メッセージは、ミドルマンにおいて判 断が得られる場合、前記使用可能なエージェントの各々の再同期化を停止させる ）と、前記ミドルマンが再同期化の責任を持つ場合、前記ミドルマンからその使 用可能なエージェントの各々に再同期化メッセージを送るステップ、又は前記ミ ドルマンが再同期化の責任を持たない場合、前記ミドルマンからその使用可能な エージェントの各々に「既知（Ｋｎｏｗｎ）」判断メッセージを送るステップ（ その「既知」判断メッセージはその使用可能なエージェントの各々の再同期化を 始動する）とを含むことを特徴とする。 従って、パートナは何が問題であるかを詳しく知らされるので、適当なアクシ ョンを取ることができる。更に、そのセッションは解放されず、従って、パフォ ーマンスを改善し、オペレータ・インターラクションを減少させる。 この提案された解決方法は如何なる既存のプロトコルに対する変更も必要なく 、しかも、それは既存のシステムに容易に組み込み可能であり、比較的簡単な実 施を可能にする。その解決方法は、上記引用の文献「ＬＵ６.２のためのＳＮＡ ピア・プロトコル」においてＬＵタイプ６.２用のＳＮＡによって定義された「 仮定異常終了、仮定零、及び最終エージェント最適化（Presumed Abort，Presum ed Nothing and Last Agent Optimisation）」プロトコルで使用される。 本発明の更なる利点は、高いトランザクション速度をサポートする分散システ ムの管理をそれが実用的な期間において単純化することである。 次に、添付図面を参照して本発明の実施例を詳細に説明することにする。 図面の簡単な説明 第１図は、本発明を実施し得るデータ処理システムの概略図である。 第２図は、その分野で知られた２フェーズ・コミット・プロトコルの特定のケ ースを示す。 第３図は、本発明の特定の実施例におけるメッセージ・フローの概要図である 。 第４ａ図及び第４ｂ図は、システムの再始動に続く種々のメッセージ・コミュ ニケーション・フローを示す。 第５図は、本発明の特定の実施例に従ったプロトコルのルールを説明する概略 的フローチャートである。 第６図は、メッセージの間のレース状態を示す図である。 発明を実施するための最良の形態 図面、特に、第１図を参照すると、本発明を実施するために利用し得るデータ 処理システムの概略図が示される。汎用アーキテクチャ１００は、５つのノード より成る分散データ処理システムを示す。アプリケーション・ノード１１０には 、例えば、ＩＢＭ社から得られるＣＩＣＳのようなトランザクション・ベースの アプリケーション・プログラムを実行するＩＢＭ Ｅｎｔｅｒｐｒｉｓｅ Ｓｙ ｓｔｅｍ／９０００、 即ち、ＥＳ／９０００のようなメインフレーム・コンピュータがある（Ｅｎｔｅ ｒｐｒｉｓｅ Ｓｙｓｔｅｍ／９０００及びＥＳ／９０００は、インターナショ ナル・ビジネス・マシーンズ・コーポレーションの商標である）。ノード１１０ は、揮発性メモリ（即ち、ＲＡＭ）１１２、及び２フェーズ・コミット（ＰＣ） プロトコルに関する情報を記憶するために使用される不揮発性メモリ１１４、一 般には、ダイレクト・アクセス記憶装置（即ち、ＤＡＳＤ）を含む。その不揮発 性メモリ１１４に記憶された情報は恒久的である。即ち、それは、ノード障害の 場合に喪失されるが、そのノードが再始動された後にはアクセス可能である。対 照的に、揮発性メモリ１１２に記憶された情報はノード障害の場合に喪失される 。アプリケーション・ノード１１０は複数のローカル資源をアクセスし、例えば 、データベース管理システムによってデータベース（即ち、ＤＢ）１１６をアク セスし、及びダイレクト・アクセス記憶装置１１４上の複数のファイルをアクセ スする。アプリケーション・ノード１１０は、データ通信機構によって同様の構 成のノード１２０、１３０、１４０、及び１５０とコミュニケートすることを可 能にされる。アプリケーション・ノード１１０において実行されるトランザクシ ョン・ベースのアプリケーション・プログラムは、例えば、６.２アーキテクチ ャ拡張機能において実施される対等通信プロトコルによって、システム・ネット ワーク・アーキテクチャ（ＳＮＡ）のような標準的なシステム・インターフェー スを 介して他のノードにおける資源をアクセスすることを可能にされる。ノード１２ ０はミドルマンとして作用し、アプリケーション・ノード１１０がノード１３０ 及び１４０における資源をアクセスすることを可能にする。 次に、第２図を参照すると、その分野で知られた２フェーズ・コミット・プロ トコルの特定のケースが示される。そのプロトコルの２つのフェーズは、システ ムがそれらの作業をバックアウトするために又はコミットするためにアクション を取る準備をする時の意思表示フェーズ、及び判断がブロードキャストされる時 のコミット・フェーズである。最終的な判断は、コーディネータとして知られた それらのノードの１つによって行われる。 第２図は、ミドルマン２１０を介してコーディネータ２０５とコミュニケート するエージェント２１５を示す。作業単位はノード２０５−２１０間及びノード ２１０−２１５間に２つの会話を確立することによって管理される。第１ノード 及び第２ノードの間の各会話は、２つのノード相互間のコミュニケーション・セ ッションの設定を必要とする。同期点プロトコル中にセッションが失敗する場合 、各ノードはメッセージを再伝送するために又はメッセージの再伝送を要請する ために他のノードと接触しようとするので、各ノード相互間の２つのセッション が同時に使用可能である。そこで、その作業単位の一部としての資源に対する変 更がユーザ・プロセスによって遂行される。ユーザ・データは、ユーザ・データ ・メッセージを介してその作業単位に関連のノード相互間で交換される。その作 業単位及び関連の２フェーズ・コミット同期化時に、各ノードは状態変更に関す る情報をそれの揮発性メモリに記憶する。チェックポイントにおいて、この状態 変更情報は、ノードが障害から回復することを可能にするように不揮発性メモリ に対して更に強制される。 ノードは、同期点が期限であることを所定の計画に従って決定し、そしてその プロトコルが開始されなければならないことをそれらノードの１つが同期点マネ ージャに信号するまで、データ・メッセージを交換する。コーディネータ２０５ は、ミドルマン２１０に準備メッセージ２２０を送ることによって２フェーズ・ コミット同期化を始動する。ミドルマン２１０はノード２０５との会話ではエー ジェントとして作用し、ノード２１５との会話ではコーデイネータとして作用す る。従って、ミドルマン２１０は準備メッセージ２２５をエージェント２１５に 送る。 ローカルの状態に基づいて、エージェント２１５は、それのオペレーションを コミットするか或いはバックアウトするかを決定する。図示の例では、エージェ ント２１５はコミットすることを決定し、意思表示「イエス」メッセージ２３０ をミドルマン２１０に送る。エージェント２１５がその作業単位の結果について それのパートナからの連絡を待っている間、それは「未確定」状態にある。ミド ルマン２１０（ノード２１５に対するコーディネータとして作用する）はコミッ トすることを決定し、意思表示「イエス」メッセージ２３５をコーディネータ２ ０５に送り、それ自身は「未確定」になる。 コミュニケーションが何れかのステージで中断される場合、プロトコルは再同 期化フェーズに入る。再同期化時に接触を再確立する責任は、そのプロトコルに おいて定義されたようにコミュニケーション・パートナの一方（又は、時には両 方）に依存する。第２図に示された例では、コーディネータとのコミュニケーシ ョンは、判断２４０がミドルマン２１０において受信される前に失われる。そこ で、ミドルマン２１０は、それがエージェント２１５からの再同期化に応答して 、コーディネータ２０５に対するそれ自身のコミュニケーションが再確立される まで、エージェント２１５とのコミュニケーションを中断し続ける。 次に、第３図を参照すると、本発明の特定の実施例におけるメッセージ・フロ ー・コミュニケーションの概要図が示される。第３図は、コーディネータ２０５ 、ミドルマン２１０、及びエージェント２１５を有するシステムを特徴とする。 コーディネータとの接触が失われたこと或いはそれが再確立されたことをコミュ ニケートするためのフローが定義される。図示の例では、ノード２０５−２１０ 間又はノード２１０−２１５間の２つの会話が設定され、しかる後、作業単位の 一部としての資源に対する変更が、ノード相互間で交換されるユーザ・データ・ メッセージを通してユーザ・プロセスによ って遂行される。状態変更が各ノードにおいてそれの揮発性メモリに記憶され、 更に、ノードが障害から回復することを可能にするように不揮発性記憶装置に対 してチェックポイントが強制される。 コーディネータ２０５は、ミドルマン２１０に準備メッセージ２２０を送るこ とによって２フェーズ・コミットを始動する。一方、ミドルマン２１０は、ノー ド２０５との会話に対するエージェントとして及びノード２１５との会話に対す るコーディネータとして作用して準備メッセージ２２５をエージェント２１５に 送る。 エージェント２１５が作業単位をコミットすることを決定する場合、それは意 思表示「イエス」メッセージ２３０をミドルマン２１０に送り、「未確定」にな る。一方、ミドルマン２１０は（ノード２１５に対するコーディネータとして作 用して）コミットすることを決定し、意思表示「イエス」メッセージ２３５をコ ーディネータ２０５に送り、「未確定」になる。 意思表示「イエス」メッセージ２３５がコーディネータ２０５に送られた後且 つ判断３３０がミドルマン２１０において受信される前の２フェーズ・コミット 同期化中、コミュニケーションは失われる。エージェント２１５とのコミュニケ ーションを中断する代わりに、ミドルマン２１０は「未知」判断メッセージ（De cision Not Known）３１０をエージェント２１５に送り、判断が得られないとい う事実をコミュニケ ートする。そこで、ミドルマン２１０は、コーディネータ２０５とのコミュニケ ーションが回復されるまで待機する。この「未知」メッセージは、判断が知らさ れるまで、エージェント２１５に再同期化を抑止させる。一方、それは、作業単 位において修正された如何なる資源に関するロックも保持し続けなければならな い。従って、エージェント２１５は、なにが問題であるか及び何故それが待機し ているのかを詳しく知らされる。更に、そのセッションは解放されず、従って、 パフォーマンスは改善され、オペレータ・インターラクションを減少する。 コーディネータ２０５とミドルマン２１０との間のコミュニケーションが回復 される時、ミドルマン２１０は再同期化メッセージ３２０をコーディネータ２０ ５に送り、しかる後、作業単位に関する判断メッセージ３３０を受信する。その 判断はミドルマン２１０において得られるので、ミドルマン２１０は「既知」判 断メッセージ（Decision Known）３４０をエージェント２１５送り、その判断が 得られたこと（判断そのものではないけれども）をコミュニケートする。そこで 、エージェント２１５は、再同期化シーケンスを始動して再同期化メッセージ３ ５０をミドルマン２１０に送り、判断メッセージ３６０をミドルマン２１０から 受け取る。この提案された解決方法は如何なる既存のプロトコルに対しても変更 を必要とせず、しかも、それは既存のシステムに容易に組み込み可能であり、比 較的簡単な実施方法を可能にすることに注 意して欲しい。 その分野で知られたコミュニケーション・プロトコルでは、情報は、そのプロ トコルの進行及び行われる判断をレコードするために不揮発性記憶媒体に固定化 される。システム障害の場合、この情報はシステムの状態を回復させるために使 用される。本発明の実施例によれば、その解決方法と関連したメッセージ（「未 知」判断）に関する情報は不揮発性媒体上にレコードされないことが望ましい。 情報を固定化するための既存のルールがそのような最適化によって複雑にされる ので、これは望ましい特徴である。 第４ａ図は、システムの再始動に続く第１のメッセージ・コミュニケーション ・フローを示す。それは、その再始動前に存在した状態を回復するために使用さ れる。図示の例では、ミドルマン２１０は、「未知」判断メッセージ３１０をエ ージェント２１５に送った後に障害を生じた。ミドルマン２１０はその「未知」 判断メッセージに関するチェックポイント情報を不揮発性記憶装置に強制しない ので、ミドルマン２１０の障害はその結果としてこの情報の喪失を生じる。ミド ルマン２１０の再始動に続いて、再始動メッセージ４１０がエージェント２１５ に送られる。エージェント２１５が「未知」判断メッセージ３１０を前に受信し ていたために再同期化を抑止していた場合、それは、再同期化メッセージ４２０ をミドルマン２１０に送ることによってそれを試みる。その判断がミドルマン２ １０において依然として未知である場合、新 たな「未知」判断メッセージ４３０が送られ、その障害前に存在した関係が再確 立される。 第４ｂ図は、同じシステムの別の再始動に続く第２のメッセージ・コミュニケ ーション・フローを示す。図示の例では、エージェント２１５は、ミドルマン２ １０から「未知」判断メッセージ３１０を受信した後に障害を生じた。エージェ ント２１５はその「未知」判断メッセージに関連したチェックポイント情報を不 揮発性記憶装置に強制しないので、そのエージェント２１５の障害もプロトコル に関する揮発性情報を喪失させる。この場合、「未知」判断メッセージ３１０の 受信という知識は喪失される。この情報は、ミドルマン２１０との再同期化を試 みることによって、エージェント２１５の再始動に続いて回復される。その場合 、再同期化メッセージ４４０がエージェント２１５によってミドルマン２１０に 送られる。その判断がミドルマン２１０において依然として未知である場合、新 たな「未知」判断メッセージ４５０がエージェント２１５に送られるであろう。 これは、障害前に存在した状況を再確立する。 次に、一般的なケースを参照すると、２つのコミュニケーション・ノードのう ちの１つ又は両方が障害に続いて再同期化を始動する責任を持つことがある。そ れらのうちのどちらに責任があるかは、それら２つのノードの間の一致したプロ トコル、そのシステムが障害を生じる前に到達した位置、及びそれらのパートナ のうちの責任のある一方を助けることが できるコーディネータによって行われた判断に依存する。本発明は、ＬＵタイプ ６.２のためのＳＮＡによって定義された「仮定異常終了、仮定零、及び最終エ ージェント最適化」プロトコルにおいて動作可能である。しかし、それが２フェ ーズ・コミットのための種々のプロトコルにおいて使用可能であることは、当業 者には明らかであろう。 第５図には、本発明の特定の実施例に従ってプロトコルのルールを説明した概 略的フローチャートが示される。ブロック５１０を参照すると、そのシステムに おけるすべての関連するエージェントがコミットする準備をするようにリクエス トされる。それに応答して、エージェントは、それらのオペレーションをコミッ トすべきか或いはバックアウトすべきかを、ローカル状態に基づいて個々に判断 する。そこで、それらの判断がコーディネータにコミュニケートされる。即ち、 それらエージェントの各々は意思表示を送って、作業単位をコミットするために それが使用可能であること（意思表示「イエス」）又は利用不能であること（意 思表示「ノー」）を表す。 ブロック５２０において、エージェントから受信された意思表示に基づいた判 断がコーディネータによって行われる。すべてのエージェントがコミットすると いう意思表示をする場合、コミットするためのリクエストが発生される。一方、 何れのエージェントもそれのオペレーションをバックアウトするという意思表示 をする場合、すべてのエージェントが、 それらのオペレーションをバックアウトするように命令される。 しかる後、ブロック５３０において、最終判断がコーディネータによってすべ ての関連エージェントにブロードキャストされる。 次に、ブロック５４０を参照すると、提案された解決方法のルールは、意思表 示「イエス」メッセージに対する応答が「未知」判断メッセージであることを必 要とする。これは、その判断がミドルマンにおいて得られる前にそのコーディネ ータとのコミュニケーションが失われる時に生じる。 「未知」判断メッセージが送られ、その後、その判断が使用可能になった時、 プロセスはブロック５５０に進む。 ミドルマンが既存のプロトコルにおける再同期化の責任を有する場合、制御フ ローはブロック５５０に進み、そこでは、再同期化メッセージがパートナに送ら れる。 ミドルマンが再同期化の責任を持たない場合、ブロック５７０において、「既 知」判断メッセージがパートナに送られる。 「既知」判断メッセージの受信時に、ブロック５８０に示されるように、エー ジェントは、再同期化メッセージを送ることによって再同期化を始動する。 ノードが障害を生じて揮発性情報を失う場合、それはその事実をそれのパート ナにコミュニケートしなければならない。又、それは、既存のプロトコルに関し て、未決の作業単位に 対して再同期化を試みなければならない。再始動メッセージを受信した時、「未 知」判断メッセージによって抑止された未決の再同期化が再試行される。再同期 化メッセージに対する応答は、その判断が未だ得られない場合、「未知」判断と なり得る。本発明は不揮発性媒体に情報を固定化するための既存のプロトコルに おける変更を必要としないということは注目すべきことである。すべての情報が 揮発性記憶装置に保持され、そしてそのシステムが再始動される場合にリフレッ シュされる。従って、この解決方法は比較的簡単な実施を可能にする。 第６図を参照すると、メッセージ相互間のレース状態が示される。ケース（ａ ）では、「未知」判断メッセージ６１０と「既知」判断メッセージ６２０との間 のレース状態が示される。明らかに、後者は前者の前に送られることはないが、 それらのメッセージは非論理的順序でレシーバに到達し得る。「未知」判断メッ セージ６１０は送られるが、直ちには受信されない。しかる後、「既知」判断メ ッセージ６２０が送られる。第６図に示されたケース（ａ）では、この「既知」 判断メッセージ６２０は「未知」判断メッセージ６１０よりも速く伝播し、その 結果、それは早く送られた「未知」判断メッセージ６１０よりも前に受信される 。「既知」判断メッセージ６２０の受信の後、「未知」判断メッセージ６１０が 受信される。その受信側は、「未知」判断メッセージ６１０が順序どおりでなく 現れる場合、そのメッセージを無視できな ければならない。ケース（ｂ）では、「未知」判断メッセージ６３０と再同期化 メッセージ６４０との間の同様な状態が示される。 その分野で知られたプロトコルでは、再同期化の処理はコミュニケーション・ セッションの中断を生じさせることがある。その中断において、受動的なパート ナは、それが責任を有し且つ厳格な再試行ループを防ぐためにその中断の開始前 の待機期間が要求される場合、その処理を再試行しなければならない。この期間 はミドルマンによって制御され、多少は任意の長さのもの、一般的には、再試行 の頻度と究極的な再同期化の時機との間の妥協的なものである。この処理のブロ ッキングが起こり得るということは、再同期化タスクが並列に実行可能でなけれ ばならないことを意味する。ノードの再始動時には、それを過負荷にし得る多く のそのようなタスクが存在することがある。数多くのコミュニケートするノード が同時に再始動される場合、デッドロックが生じ得る。本発明は、再同期化にお いてブロッキングが生じ得ないことを保証する。一連の実行によって再同期化を 順次に処理することが可能である。

【手続補正書】 【提出日】１９９８年１月１２日 【補正内容】 請求の範囲 １．トランザクションに参加する複数のエージェント（１２０−１５０）及び前 記トランザクションをコーディネートするためのコーディネータ（１１０）を含 むデータ処理システム（１００）において前記トランザクションの同期化を行う ための方法にして、前記エージェント（１２０−１５０）は前記エージェント（ １２０−１５０）のうちの少なくとも１つのセット（１３０、１４０）をコーデ ィネートする少なくとも１つのミドルマン（１２０）を含み、 コミットするために使用可能であるか又は使用不能であるかを表す意思表示を 前記エージェント（１２０−１５０）の各々から前記コーディネータ（１１０） に送るステップ（５１０）と、 前記意思表示がすべて受信された時、前記コーディネータ（１１０）によるコ ミット又はバックアウトの判断を決定するステップ（５２０）と、 を含み、 障害のために前記判断が前記ミドルマン（１２０）において得られない場合、 前記ミドルマン（１２０）からコミットするために使用可能な前記セットにおけ るエージェント（１３０、１４０）の各々に「未知」判断メッセージを送るステ ップ（５４０）であって、前記「未知」判断メッセージは通 常障害に応答して発生される前記使用可能なエージェント（１３０、１４０）及 び前記ミドルマン（１２０）との間の再同期化メッセージを禁止することを含む ステップ、及び 前記判断が前記ミドルマン（１２０）において得られる場合（５５０）、前記 使用可能なエージェント及び前記ミドルマン（１２０）の間の再同期化メッセー ジを可能にするステップ（５６０、５７０、５８０） を含むことを特徴とする方法。 ２．前記可能にするステップは、前記判断が前記ミドルマン（１２０）において 得られる場合（５５０）、前記ミドルマン（１２０）が再同期化の責任を持つ場 合には前記ミドルマン（１２０）から前記使用可能なエージェント（１３０、１ ４０）の各々に再同期化メッセージを送るステップ（５６０）、又は、前記ミド ルマン（１２０）が再同期化の責任を持たない場合には前記ミドルマン（１２０ ）から前記使用可能なエージェント（１３０、１４０）の各々に「既知」判断メ ッセージを送るステップ（５７０）を含み、前記「既知」判断メッセージは前記 使用可能なエージェント（１３０、１４０）のうちの少なくとも１つに再同期化 メッセージ（３５０）を前記ミドルマンへ送らせることを特徴とする請求の範囲 第１項に記載の方法。 ３．「既知」判断メッセージ（６２０）を受信した後、前記使用可能なエージェ ント（１３０、１４０）の１つによって受信された如何なる「未知」判断メッセ ージ（６１０）も無 視するステップを更に含むことを特徴とする請求の範囲第２項に記載の方法。 ４．再同期化メッセージ（６４０）を受信した後、前記使用可能なエージェント （１３０、１４０）の１つによって受信された如何なる「未知」判断メッセージ （６３０）も無視するステップを更に含むことを特徴とする請求の範囲第１項乃 至第３項のいずれかに記載の方法。 ５．前記「未知」判断メッセージに関連した情報は前記エージェント（１２０− １５０）の各々における揮発性メモリにおいてのみ記憶されることを特徴とする 請求の範囲第１項乃至第４項のいずれかに記載の方法。 ６．前記ミドルマン（２１０）の障害からの再始動の後、前記ミドルマン（２１ ０）から前記使用可能なエージェント（２１５）の各々に「再始動済み」メッセ ージ（４１０）を送るステップと、 前記使用可能なエージェント（２１５）の各々から前記ミドルマン（２１０） に更なる再同期化メッセージ（４２０）を送るステップと、 前記判断が前記ミドルマン（２１０）において未だ得られない場合、前記ミド ルマン（２１０）から前記使用可能なエージェント（２１５）の各々に更なる「 未知」判断メッセージ（４３０）送るステップと、 を更に含むことを特徴とする請求の範囲第５項に記載の方法。 ７．トランザクションが同期化される分散データ処理システムにして、 前記トランザクションに参加する複数のエージェント（１２０−１５０）であ って、前記エージェント（１２０−１５０）のうちの少なくとも１つのセット（ １３０、１４０）をコーディネートする少なくとも１つのミドルマン（１２０） を含む複数のエージェントと、 前記トランザクションをコーディネートための１つのコーディネータ（１１０ ）と を含み、 前記コーディネータ（１１０）は コミットするために使用可能であるか又は使用不能であるかを表す意思表示を 前記エージェント（１２０−１５０）の各々から前記コーディネータ（１１０） に送るための手段（５１０）と、 前記意思表示がすべて受信された時、前記コーディネータ（１１０）によるコ ミット又はバックアウトの判断を決定するための手段（５２０）と、 を含む分散データ処理システムにおいて、 障害のために前記判断が前記ミドルマン（１２０）において得られない場合、 前記ミドルマン（１２０）からコミットするために使用可能な前記セットにおけ るエージェント（１３０、１４０）の各々に「未知」判断メッセージを送るため の手段（５４０）であって、前記「未知」判断メッセージは 通常障害に応答して発生される前記使用可能なエージェント（１３０、１４０） 及び前記ミドルマン（１２０）との間の再同期化メッセージを禁止することを含 む手段、及び 前記判断が前記ミドルマン（１２０）において得られる（５５０）ことに応答 して、前記使用可能なエージェント及び前記ミドルマン（１２０）の間の再同期 化メッセージを可能にするための手段（５６０、５７０、５８０） を含むことを特徴とする分散データ処理システム。 ８．前記再同期化メッセージを可能にするための手段は、 前記ミドルマン（１２０）が再同期化の責任を持つかどうかの表示を行うため の手段と、 前記ミドルマン（１２０）が再同期化の貴任を持つことを表す表示に応答して 、前記判断が前記ミドルマン（１２０）において得られる時（５５０）、前記使 用可能なエージェント（１３０、１４０）の各々に再同期化メッセージを送るた めの手段（５６０）と、 前記ミドルマン（１２０）が再同期化の責任を持たないことを表す表示に応答 して、前記使用可能なエージェント（１３０、１４０）の各々に「既知」判断メ ッセージを送るための手段（５７０）であって、前記「既知」判断メッセージは 前記使用可能なエージェント（１３０、１４０）のうちの少なくとも１つに再同 期化メッセージ（３５０）を前記ミドルマンへ送らせることを含む手段と、 を含むことを特徴とする請求の範囲第７項に記載のシステ ム。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ノーミントン、グライン イギリス国ハンプシャー、ウインチェスタ ー、コレイ・クロス 18 (72)発明者 ツイマー、デニス・ジャック イギリス国ハンプシャー、チャンドラー ズ・フォード、クイーンズ・ロード 17 (72)発明者 ラプトン、ピータ、ジェイムス イギリス国ハンプシャー、チャンドラー ズ・フォード、バッデズレイ・ロード 38 【要約の続き】 々の再同期化を停止する。ミドルマン（１２０）が再同 期化の責任を持つ場合、その判断がミドルマン（１２ ０）において得られる時、再同期化メッセージがその使 用可能なエージェント（１３０、１４０）の各々に送ら れる（５６０）。ミドルマン（１２０）が再同期化の責 任を持たない場合、「既知」判断メッセージがミドルマ ン（１２０）からその使用可能なエージェント（１３ ０、１４０）の各々に送られる（５７０）。「既知」判 断メッセージの受信は使用可能なエージェント（１３ ０、１４０）の各々の再同期化を始動する（５８０）。

Claims (1)

1. 【特許請求の範囲】 １．トランザクションに参加する複数のエージェント（１２０−１５０）及び前 記トランザクションをコーディネートするためのコーディネータ（１１０）を含 むデータ処理システム（１００）において前記トランザクションの同期化を行う ための方法にして、前記エージェント（１２０−１５０）は前記エージェント（ １２０−１５０）のうちの少なくとも１つのセット（１３０、１４０）をコーデ ィネートする少なくとも１つのミドルマン（１２０）を含み、 コミットするために使用可能であるか又は使用不能であるかを表す意思表示を 前記エージェント（１２０−１５０）の各々から前記コーディネータ（１１０） に送るステップ（５１０）と、 前記意思表示がすべて受信された時、前記コーディネータ（１１０）によるコ ミット又はバックアウトの判断を決定するステップ（５２０）と、 を含み、 障害のために前記判断が前記ミドルマン（１２０）において得られない場合、 前記ミドルマン（１２０）からコミットするために使用可能な前記セットにおけ るエージェント（１３０、１４０）の各々に「未知」判断メッセージを送るステ ップ（５４０）であって、前記「未知」判断メッセージは使用可能なエージェン ト（１３０、１４０）の各々の再同期化 を停止させることを含むステップ、及び 前記判断が前記ミドルマン（１２０）において得られる場合（５５０）、前記 ミドルマン（１２０）が再同期化の責任を持つ場合には前記ミドルマン（１２０ ）から前記使用可能なエージェント（１３０、１４０）の各々に再同期化メッセ ージを送るステップ（５６０）、又は、前記ミドルマン（１２０）が再同期化の 責任を持たない場合には前記ミドルマン（１２０）から前記使用可能なエージェ ント（１３０、１４０）の各々に「既知」判断メッセージを送るステップ（５７ ０）であって、前記「既知」判断メッセージは前記使用可能なエージェント（１ ３０、１４０）の各々の再同期化（５８０）を始動することを含むステップ を含むことを特徴とする方法。 ２．「既知」判断メッセージ（６２０）を受信した後、前記使用可能なエージェ ント（１３０、１４０）の１つによって受信された如何なる「未知」判断メッセ ージ（６１０）も無視するステップを更に含むことを特徴とする請求の範囲第１ 項に記載の方法。 ３．再同期化メッセージ（６４０）を受信した後、前記使用可能なエージェント （１３０、１４０）の１つによって受信された如何なる「未知」判断メッセージ （６３０）も無視するステップを更に含むことを特徴とする請求の範囲第１項又 は第２項に記載の方法。 ４．前記「未知」判断メッセージに関連した情報は前記エー ジェント（１２０−１５０）の各々における揮発性メモリにおいてのみ記憶され ることを特徴とする請求の範囲第１項乃至第３項の１つに記載の方法。 ５．前記ミドルマン（２１０）の障害からの再始動の後、前記ミドルマン（２１ ０）から前記使用可能なエージェント（２１５）の各々に「再始動済み」メッセ ージ（４１０）を送るステップと、 前記使用可能なエージェント（２１５）の各々から前記ミドルマン（２１０） に更なる再同期化メッセージ（４２０）を送るステップと、 前記判断が前記ミドルマン（２１０）において未だ得られない場合、前記ミド ルマン（２１０）から前記使用可能なエージェント（２１５）の各々に更なる「 未知」判断メッセージ（４３０）送るステップと、 を更に含むことを特徴とする請求の範囲第４項に記載の方法。 ６．トランザクションが同期化される分散データ処理システムにして、 前記トランザクションに参加する複数のエージェント（１２０−１５０）であ って、前記エージェント（１２０−１５０）のうちの少なくとも１つのセット（ １３０、１４０）をコーディネートする少なくとも１つのミドルマン（１２０） を含む複数のエージェントと、 前記トランザクションをコーディネートための１つのコー ディネータ（１１０）と を含み、 前記コーディネータ（１１０）は コミットするために使用可能であるか又は使用不能であるかを表す意思表示を 前記エージェント（１２０−１５０）の各々から前記コーディネータ（１１０） に送るための手段（５１０）と、 前記意思表示がすべて受信された時、前記コーディネータ（１１０）によるコ ミット又はバックアウトの判断を決定するための手段（５２０）と、 を含む分散データ処理システムにおいて、 障害のために前記判断が前記ミドルマン（１２０）において得られない場合、 前記ミドルマン（１２０）からコミットするために使用可能な前記セットにおけ るエージェント（１３０、１４０）の各々に「未知」判断メッセージを送るため の手段（５４０）であって、前記「未知」判断メッセージは使用可能なエージェ ント（１３０、１４０）の各々の再同期化を停止させることを含む手段と、 前記ミドルマン（１２０）が再同期化の責任を持つかどうかの表示を行うため の手段と、 前記ミドルマン（１２０）が再同期化の責任を持つことを表す表示に応答して 、前記判断が前記ミドルマン（１２０）において得られる時（５５０）、前記使 用可能なエージェント（１３０、１４０）の各々に再同期化メッセージを送るた めの手段（５６０）と、 前記ミドルマン（１２０）が再同期化の責任を持たないことを表す表示に応答 して、前記使用可能なエージェント（１３０、１４０）の各々に「既知」判断メ ッセージを送るための手段（５７０）であって、前記「既知」判断メッセージは 前記使用可能なエージェント（１３０、１４０）の各々の再同期化（５８０）を 始動することを含む手段と、 を含むことを特徴とする分散データ処理システム。