(57)【要約】 【課題】  分散データ処理ネットワークでのノード「活性」状態を決定するためのシステム及び方法を提供。【解決手段】  分散ネットワーク・データ処理システムにおいてノード及び／又はアダプタ活性の決定は、第２のメッセージ・プロトコルによって補助された第１のメッセージ・プロトコルを介して実行される。第２のメッセージ・プロトコルは、第１のメッセージ・プロトコルよりも遅延、特に他のノード上で実行されるデーモンによって遭遇するメモリ阻害による遅延の影響を受けることが少ない。プロトコルの切り換えは、必要とする応答の制御された猶予期間によって達成される。このメッセージ・プロトコルの柔軟性は、ノードの追加（バース）及びノードの削除（デス）の意図的なアクティビティを制御するための機構としての使用にも適している。【選択図】  図１
2006146913.tif 000002
【特許請求の範囲】
【請求項１】
相互接続された複数のデータ処理ノードからなるネットワークにおいて、２つ以上のノードからなる第１のグループに対して新しいメンバを加えるための方法であって、
現在のところ前記第１のグループのメンバではないが前記ネットワーク内にある選択されたノードに対して、前記第１のグループのリーダ・ノードからプロクレーム・メッセージを送信するステップと、
前記プロクレーム・メッセージに対する応答を、前記第１のグループのリーダ・ノードよりも低いネットワーク・アドレスを有する他のグループのリーダ・ノードから、該他のグループのメンバシップ・リストを含む参加メッセージによって行うステップと、
前記第１のグループのリーダ・ノードが前記参加メッセージを受信した場合には、該第１のグループのリーダ・ノードから前記第１のグループのメンバ及び前記他のグループのメンバである全てのノード上で実行されるデーモン・プログラムに向けて、コミット準備メッセージを送信するステップと、
前記第１のグループのリーダ・ノードが前記全てのノード上で実行されるデーモン・プログラムから前記コミット準備メッセージに対する確認を受信した場合には、該第１のグループのリーダ・ノードから該全てのノード上で実行されるデーモン・プログラムに向けて、該全てのノードをメンバとする新しいグループのメンバーシップ・リストを含むコミット・メッセージを送信することにより、該新しいグループの編成を行うステップと、
前記第１のグループのリーダ・ノードが前記全てのノードのうち一部のノード上で実行されるデーモン・プログラムから前記コミット準備メッセージに対する確認を受信していない場合には、該第１のグループのリーダ・ノードから該一部のノード上で実行されるデーモン・プログラムに向けて、所定数の前記コミット準備メッセージを周期的に送信するステップと、
前記コミット準備メッセージの周期的な送信に続く所定の時間内に、前記第１のグループのリーダ・ノードが前記一部のノード上で実行されるデーモン・プログラムから前記コミット準備メッセージに対する確認を受信していない場合には、該第１のグループのリーダ・ノードから該一部のノード上で実行され且つ該一部のノード上で実行される前記デーモン・プログラムよりも応答の遅れが生じにくい他のプログラムに向けて、エコー要求メッセージを送信するステップと、
前記第１のグループのリーダ・ノードが前記一部のノード上で実行される前記他のプログラムから前記エコー要求メッセージに対する応答を受信した場合には、前記コミット準備メッセージに対する応答の猶予期間を設定するステップと、
を有する方法。
【請求項２】
前記他のプログラムは、前記一部のノード上で実行されるオペレーティング・システム・カーネルの一部である、請求項１記載の方法。
【請求項３】
前記一部のノードは、該一部のノード内のメモリ割り当て制約によって前記所定の時間内に応答することが妨げられる、請求項１記載の方法。
【請求項４】
前記一部のノードは、該一部のノード内のプログラム優先度制約によって前記所定の時間内に応答することが妨げられる、請求項１記載の方法。
【請求項５】
前記エコー要求メッセージに対する応答がない場合には、前記一部のノードがデス状態となっていることを、前記第１のグループのリーダ・ノードが報告するステップをさらに有する、請求項１記載の方法。
【請求項６】
前記エコー要求メッセージが送信される前に、応答なしで、前記コミット準備メッセージが少なくとも３回周期的に送信される、請求項１記載の方法。
【請求項７】
前記猶予期間の終わりに前記コミット準備メッセージに対する応答がない場合には、前記一部のノードがデス状態となっていることを、前記第１のグループのリーダ・ノードが報告するステップをさらに有する、請求項１記載の方法。
【請求項８】
前記一部のノードがデス状態となっている場合には、前記第１のグループのリーダ・ノードから前記全てのノードのうち前記一部のノードを除く残余のノード上で実行されるデーモン・プログラムに向けて、該残余のノードをメンバとする新しいグループのメンバーシップ・リストを含むコミット・メッセージを送信することにより、該新しいグループの編成を行うステップをさらに有する、請求項５又は７記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、異なる優先度及び／又は異なる特性応答制限で、異なるレベルで動作するメッセージ・プロトコルを用いることが可能な分散データ処理システムにおいて、ネットワーク・アダプタ（以下単に「アダプタ」とも称する）及び／又はノードのデス状態を決定するための方法に関連して、アダプタ及び／又はノードをグループに加えるための方法に関する。本発明の重要な利点は、デーモン阻害によって生ずる偽りの障害通知に対する優れた障害許容力である。
【背景技術】
【０００２】
アダプタ及びノード活性（liveness）の決定は、特定のアプリケーションを動作させるために一般に用いられる複数のクラスタにノードを分割することが可能である、任意の高度に利用可能な分散データ処理ネットワークの核心的事項である。高可用性サービスを提供するために、クラスタ・システムは、どのノード、ネットワーク、及びシステム内のネットワーク・アダプタが働いているかを決定することができなければならない。そのような任意のコンポーネントにおける障害は、早く検出しなければならず、結果として生ずる情報は、より高水準のソフトウェア・サブシステムに伝えられ、もし可能であるならば、回復動作がクラスタ回復マネージャ及びアプリケーション・レベル・ソフトウェアによって開始されなければならない。
【０００３】
ノード、ネットワーク、及びネットワーク・アダプタ活性の決定は、しばしば分散システムの各ノードで実行されるデーモン・プログラム（以下単に「デーモン」とも称する）の利用を介してなされる。デーモンは、分散プロトコルを実行し、システムにおいて異なるネットワーク経路を通して強制される活性メッセージを交換する。もし、そのような活性メッセージが所定の間隔内で受信されなければ、送信ノード又はネットワーク・アダプタが他のものによって作動していない（「デス」）と想定される。
【０００４】
この活性決定方法は、対応するデーモンに対してリアル・タイム制約を課す。すなわち、もしデーモンがいずれにせよ遅れるならば、このことはそのホスティング・ノードが誤ってデスとして検出されることに帰着するかもしれない（「誤りダウン」イベント）。誤りダウン・イベントは、不要で、しばしば高くつく、クラスタの動作を中断させることがある回復手順に帰着する。
【０００５】
しかし、基礎をなすオペレーティング・システムはめったにリアル・タイムとならないことから、デーモンをこれらのリアル・タイム制約に従わせることはしばしば簡単なことではない。リアル・タイム・オペレーティング・システムだけが、どんな状態下でも有限の応答時間を保証することができる。
【０００６】
システムの複数のノードのうちの一つにある負荷が、現在のメモリの量を物理的メモリが大きく上回ることを必要とするほどのものならば、重いページングが起こり始め、それは時折、殆ど進行しないプロセスに至る。活性決定デーモンに関しては、これらのページング動作は、活性メッセージの適時の送信を妨げるように作用することがある。
【０００７】
幾つかのオペレーティング・システムは、他のアプリケーションによって該システムのページを「盗まれない」ようにするプロセスを可能とする基本命令を提供するが、実際にはこの解決策は完璧ではない。すなわち、基本命令が全体のアドレス空間で働かない（例えば、基本命令が共有ライブラリと連携しない）か、又はオペレーティング・システムそのものがしばしばページ可能である。
【０００８】
メモリ枯渇の他に、プロセスの適切な進行を妨げる他の原因が知られている。すなわち、システム内での任意のプロセスの実行を阻止する高い割り込み率と、ＣＰＵ利用を独占する優先度の高いプロセスの存在である。
【０００９】
プロセス阻害によって引き起こされるそれらの「誤りダウン」を防ぐために、以下の異なるアプローチが使用される。
（１）リモート・エンティティが「ダウン」であると宣言する前に、欠落（missing）活性メッセージの数の閾値を増加させること。
（２）リアル・タイム・スケジューリング優先度及びページングを防ぐオペレーティング・システム基本命令を用いることで、可能な限りリアル・タイムでデーモンを動作させること。
（３）活性メッセージを送信するためのコードをカーネルに取り込むこと。
【００１０】
しかし、前記（１）〜（３）のアプローチは、以下のような解決すべき課題を有する。すなわち、前記（１）は、真の障害を検出するのに時間がかかるという欠点を有し、そのため（真の）障害が生じている間、クラスタによって提供されるエンド・ユーザ・サービスが長時間にわたって利用不能となる。
【００１１】
前記（２）は、部分的に効果があるのみである。オペレーティング・システムによって提供される多数のリアル・タイム基本命令の使用を必要とするのみならず、通信及びＩ／Ｏ等、知られている障害の原因を避けるように注意深く設計することも必要である。それでも、オペレーティング・システムはプロセスが常に進行することを保証することができないかもしれない。
【００１２】
前記（３）は良好な結果をもたらすが、オペレーティング・システム・カーネルにコードを導入する必要があることから、しばしば法外な開発費がかかり、移植性及び保守性を著しく損なう。このアプローチに伴う微妙な問題は、カーネルを実行できるが、ユーザ・プログラムを実行できないという状態を検出するのに不適当な「カーネル活性」を提供することしかできないということである。そのような状態下では、ノードは役に立たなくなり、該ノードがデスであると宣言することが正しい決定となろう。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明は、相互接続された複数のデータ処理ノードからなるネットワークにおいて、データ処理ノードが「デス」であるとの宣言を早まって、及び／又は誤って行うことを防ぐ基本機構を利用する。
【課題を解決するための手段】
【００１４】
本発明の基本機構によれば、相互接続された複数のデータ処理ノードからなるネットワークにおいて、ノード及び／又はそのアダプタの状態を決定するための方法が提供される。複数のノードはグループとして存在し、好ましくは特定の機能及び権限を持つ一つのグループ・リーダが設けられる（しかし、ここで注意すべき点は、グループ・リーダの存在は、本発明の最も広い範囲内において本発明の動作にとって必須なものではないことである）。周期的に、該グループ内の各ノードは、状態メッセージをそのグループ内の所定の一つのノードに対して送る。このメッセージは、ハート・ビート・メッセージと呼ばれ、くだけた言い方では、「私は生きている」メッセージとも呼ばれる。もしそれらの複数のノードが一つの環状トポロジで接続されているならば（ここでは好ましい実現体である）、各ノードはそのハート・ビート・メッセージを前記環状トポロジの下流に位置する隣接ノードに対して送信する。送信されたメッセージは、「私は生きている」（ハート・ビート）メッセージに対する応答を与える目的で、指定ノード（又は非環状トポロジの複数のノード）上で走るデーモン・プログラムに向けられる。デーモンは、所定の一つ（又は複数）のノードに対してハート・ビート・メッセージを転送することによって応答するものではない。むしろ、それ自身のハート・ビート・メッセージを、指定された一つの宛先（又は非環状トポロジのノード相互接続が用いられる場合は、指定された複数の宛先）に対して周期的に送る。しかし、好ましくはないが、ハート・ビート・メッセージを転送することは、このサービスを提供する代替方法を提供するものである。各ノードは、周期的に、ハート・ビート信号が、指定した一つの送信ノードから送られたかどうかを決定する。もし幾つかのハート・ビート信号が予想通りに受信されなければ、前記送信ノードにおけるメモリ制約の問題に起因して、該ハート・ビート信号の送信に責任あるデーモンの応答が遅れた可能性が存在する。このデーモンの応答を遅らす原因は数多くあり、該ノードで実行される他のアプリケーションがローカル・オペレーティング・システムによってより高い実行優先度を割り当てられる状態もそのような原因の一つとして含まれる。このような遅延現象は、単にメモリ制約の問題に限られているわけではない。本発明の基本機構が「有利な立場にたっている」ことを保証するために、好ましくは第２のメッセージが無条件に必須なものとなる前に、すなわち前記したように、他のアプローチがすでにノードの「デス」を宣言する前に、第２のメッセージを送信する。この第２のメッセージは、非応答ノードへ送られる。しかし、前記第２のメッセージは、デーモンには送られないで、むしろ同一のメモリ制約問題を持たないメッセージ受信ノード上で実行されるプログラムへ送られる。特に、第２のメッセージは、好ましくは優先度処理が利用可能であるオペレーティング・システム・カーネル部分に向けられる。さらに具体的には、本発明の基本機構は、Ｕｎｉｘ(R)系オペレーティング・システムで用いられるような「ピング」機能を用いる。
【００１５】
本発明の好ましい実施形態によれば、ノードをグループに加えるプロセス、又はノード「デス」を操作するプロセスもまた、この２段階のメッセージ送信機構とともに与えられる。このプロセスは、メッセージ通信での遅れ、特にローカル・メモリ制約問題で生ずる遅れが課されることなく、グループのトポロジ又は構造の変更を効率的に行うことができることを保証する。特に、本発明は、前記の「私は生きている」（I am Alive: ＩＡＡ）メッセージと同様に処理される、「コミット準備」（Prepare to Commit: ＰＴＣ）メッセージも用いる。本発明で用いた概念を使用することで、生じ得る若干の遅れを減らす効果が得られ、その一方で主な利点はその使用によってノードが早まって「デス」と宣告されることを防ぐことである。
【００１６】
したがって、本発明の目的は、ノード状態、特にノードが生きていて機能しているかどうかを反映する状態に関係する、メッセージ処理要求で使用される阻害されたデーモンの問題を避けることである。
【００１７】
本発明のさらに別の目的は、ノードが早まって「デス」であると宣告される状態で生じたオーバヘッド及びシステム処理における遅れを取り除くことである。
【００１８】
本発明のさらに別の目的は、ネットワーク・グループに対するノードの追加を処理し、また不必要な遅れなしにネットワーク・グループからのノード除去を処理することである。
【００１９】
本発明の別の目的は、リモート・ノードにあるメモリ制約の問題によって生じたメッセージ応答遅延を取り除くことである。
【００２０】
本発明のさらに別の目的は、完全なネットワーク・システム利用を確実にすることであり、また所望のノード全てによる完全なプロセス参加が欠けている状態を避けることである。
【００２１】
本発明のさらに別の目的は、ノード及び／又はそのアダプタのデスを検出し、グループ・メンバシップの適切な再構成を与える機構を提供することである。
【００２２】
最後に、ここでは限定されないが、メモリ・ページング、メモリ割り当て、又は同様の遅延によって生ずる制約条件によっては妨げられない、オペレーティング・システム・カーネル機能を利用することである。
【００２３】
本発明の種々の実施形態に合致する一連の所望の目的をここで列挙したことは、本発明の最も普遍的な実施形態、又はそのより特徴的な実施形態のいずれかで、個々に、又は集合的のいずれにおいても、それらの目的のいずれか、又は全てが必須事項として存在することを暗示又は示唆するものではない。
【００２４】
本発明として見なされる主題は、発明の詳細な説明の中で詳しく指摘し、また明細書の記述に加えて特許請求の範囲において明瞭に記載されている。しかし、本発明は、さらなる目的とその利点と共に、構造及び実施方法の両方に関して、添付図面と関連して以下の記載を参照することで、最も良く理解されるだろう。
【発明を実施するための最良の形態】
【００２５】
本発明の基本機構は、ストレス負荷のもとで、またプロセスが阻害される他の条件のもとでのデーモン阻害によって起こる、「誤りダウン」を防ぐために提供される。この基本機構は、ダウンしていると疑われるノード／アダプタへ送られるインターネット制御メッセージ・プロトコル（ＩＣＭＰ）エコー要求メッセージを使用する。そのようなメッセージに対する応答は、割り込みモードにあるカーネルによって行われるため、たとえピア・デーモンが一時的に阻害されていたとしても、該メッセージに対する応答を行うことができる。もし「デスであると疑われた」ノード又はアダプタからＩＣＭＰエコー応答の応答受信がなされると、該ノード又はアダプタのために猶予期間が設定されるので、少なくとも初めのうちは該ノード又はアダプタがデスであると宣言しない。
【００２６】
本発明の基本機構は、すでに説明した従来の３通りのアプローチを上回る利点を提供する。前記した第１のアプローチとは異なり、真のアダプタ及び／又はノード障害の検出時間は増加しない。本発明の基本機構は、前記した第２のアプローチよりも有効である。なぜなら、オペレーティング・システム・カーネルは、ユーザ・レベル・プロセスの実行を許可するよりも早く、ＩＣＭＰエコー要求メッセージに応答することができるからである。最後に、本発明の基本機構は、前記した第３のアプローチで行われるような書き込みカーネル・コードを必要とするものではない。
【００２７】
ここで提案する基本機構は、ＩＢＭのリライアブル・スケーラブル・クラスタ・テクノロジ（ＲＳＣＴ）インフラストラクチャの一部である、トポロジ・サービス・サブシステムにおけるその使用という環境下で導入される。トポロジ・サービスは、クラスタにおいて稼働している複数のノードからなるセットを決定する役割を担うことから、システムの「活性層」を提供する。
【００２８】
ハート・ビートプロトコル
本発明の基本機構をより良く説明するために、またそれがどのようにしてトポロジ・サービスで使用されるかをより良く説明するために、ここでサブシステム内のアダプタ・メンバシップ（「ハート・ビート」）プロトコルを詳述する。
【００２９】
各ネットワークのアダプタの健全性及び接続性をモニタするために、該ネットワークの全てのアダプタが「アダプタ・メンバシップ・グループ」（ＡＭＧ）を形成することを試みる。ここで、ＡＭＧは、該ネットワーク内で互いに通信することができる全てのネットワーク・アダプタが含まれるグループである。ＡＭＧ内のアダプタは、互いの「活性」をモニタする。ＡＭＧが形成されると、全てのグループ・メンバは、該ＡＭＧを一意的に識別する「ＡＭＧｉｄ」を受信する。故障したアダプタは、そのグループから追放され、パワー・アップされた新しいアダプタがグループへの参加を勧誘される。どちらの場合も、新しいＡＭＧｉｄを有する新しいＡＭＧが形成される。各ＡＭＧは、グループ・リーダ（ＧＬ）である一つのメンバを有し、さらに全てのメンバはどのノードがグループ・リーダであるかを知る。ここで注目すべき点は、一つのノードが幾つかのＡＭＧ（その複数のネットワーク・アダプタの各々に対応）に属していてもよいことである。
【００３０】
各ネットワークで活きている複数のアダプタからなるセットを決定するために、アダプタ・メンバシップ・プロトコルはネットワークの各々で実行する。このプロトコルのメッセージは、ＵＤ／ＩＰ（ユーザ・データグラム・プロトコル／インターネット・プロトコル）を用いて送信される。このプロトコルをインターネット・プロトコルと呼ぶが、この語の用法はここではいかなるインターネット接続の存在も意味するものではなく、またどんな形ではあれインターネットに対する依存性を意味するものではない。それは単に相互接続された複数のデータ処理ノードからなるネットワーク内で有用で、かつ明確に特徴づけられた通信プロトコルを示すために便宜的に使用された名前であるに過ぎない。
【００３１】
活きているアダプタは、ＡＭＧを形成し、そこでは複数のメンバが好ましくはバーチャル環状トポロジに編成される。全てのグループ・メンバが活きていることを確かめるために、各メンバは周期的に「ハート・ビート」メッセージをその「下流側の隣接メンバ」へ送信し、その「上流側の隣接メンバ」からの「ハート・ビート」メッセージをモニタする。「ハート・ビート」メッセージは、ここでは「私は生きている」（ＩＡＡ）メッセージとも呼ばれる。デス・プロトコル及び参加プロトコルは、アダプタ故障の場合、又は新しいアダプタが機能的になり始めた時、それぞれ実行される。そのようなプロトコルの目標は、メンバシップ・グループが、各時点で、互いに通信することができるネットワーク（しかし、クラスタに属するものだけ）内のアダプタの全て（及びのみ）を含むことを保証することである。
【００３２】
グループ・リーダに加えて、各グループは「クラウン・プリンス」（バックアップ・グループ・リーダ）を有する。「クラウン・プリンス」モデルの詳細については、米国特許第５，８０５，７８６号及び第５，９２６，６１９号を参照されたい。グループ・リーダは、グループ・プロトコルを調整する役割を担っている。一方、クラウン・プリンスは、グループ・リーダであるアダプタが故障した場合に該グループ・リーダに取って代わる役割を担う。グループ・リーダ及びクラウン・プリンスの選択と環内でのこれらのアダプタの位置とが、ともに所定のアダプタ優先度規則によって決定される。ここで、所定のアダプタ優先度規則は、好ましくはアダプタのＩＰアドレスとなるように選択される。このアドレスは、簡単に入手可能で、かつ一意的な識別子を提供するもので、その特徴の全てはこの規則に対して高度に適したものとなる。
【００３３】
各ネットワークにおける全ての可能なアダプタからなるリストが構成ファイルに含まれる。この構成ファイルは、開始時及び再構成時にノードの全てによって読み込まれる。
【００３４】
参加プロトコル
新しいメンバをグループに引きつけるために、各グループ内のグループ・リーダは周期的に「プロクレーム」メッセージを、現在のところ該グループには属さないがアダプタ構成にあるアダプタへ送る。このメッセージは、送信元のＩＰアドレスよりも低いＩＰアドレスを有するアダプタへ送られる。注意すべき点は、ＩＰアドレスの使用が「プロクレーム」メッセージを適切に向けるための好ましい機構である一方で、任意の他の簡便な方法もまた適用可能であることである。すなわち、唯一の要件は、グループ・リーダを有する複数のノードからなる明確に定義されたセットへの送信である。
【００３５】
「プロクレーム」メッセージは、グループ・リーダではない全てのアダプタによって無視される。より高い優先度（より高いＩＰアドレス）ノードからの「プロクレーム」メッセージを受信するグループ・リーダ・ノードは、そのグループに代わって「参加」メッセージで応答する。このメッセージは、「参加するグループ」のメンバシップ・リストを含む。
【００３６】
ノード（例えばＧＬ１）は、別のノード（例えばＧＬ２）から「参加」メッセージを受信すると、「コミット準備」メッセージを送信することにより、参加しようとするグループ内の全てのメンバに加えて今までのメンバを含む新しいグループの形成を試みる。
【００３７】
「コミット準備」メッセージを受信したノードは、「ＰＴＣ＿ＡＣＫ」（コミット準備確認）メッセージによって応答する。「ＰＴＣ＿ＡＣＫ」メッセージで応答したノードの全てが新しいグループに含まれる。グループ・リーダ（ノードＧＬ１）は、新たに形成されたグループのメンバに対して、グループ・メンバシップ・リスト全体を含んでいる「コミット」メッセージを送信する。
【００３８】
「コミット」メッセージを受信することで、新しいグループへの移行がマークされる。このメッセージを受信した後に、一つのグループ・メンバは該メンバの（たぶん新しい）下流側の隣接メンバへ「ハート・ビート」メッセージの送信を開始し、また該メンバの上流側の隣接メンバからの「ハート・ビート」メッセージのモニタリングを開始する。
【００３９】
「コミット準備」メッセージ及び「コミット」メッセージは、それらのメッセージが受信されたことを確実にするための確認を必要とする。もし、何ら確認が受信されなければ、再試行が限定された回数だけ行われる。再試行が全回数行われた後、「コミット準備」メッセージに対する応答の失敗は、対応するアダプタが新しいグループに含まれないことになる。もし、「ＰＴＣ＿ＡＣＫ」メッセージの再試行が全回数行われた後に、デーモンが「コミット」メッセージの受信に失敗すると、そのローカル・アダプタは新しいグループの形成を諦め、それ自身を単一アダプタ・グループに再初期化する。この現象は、グループ・リーダが「コミット準備」メッセージの送信と「コミット」メッセージの送信との間の短いウィンドウで失敗するという相対的にまれな事例でのみ生ずるべきである。
【００４０】
トポロジ・サービス・デーモンが初期化される場合、該デーモンはそのアダプタの各々において単一アダプタ・グループ（そのノードがグループ・リーダ）を形成する。そして、そのノードは、「プロクレーム」メッセージの送信及び受信を開始する。
【００４１】
デス・プロトコル
ノード又はアダプタは、その「上流側の隣接メンバ」（グループ・メンバの中で次に最も高いＩＰアドレスを有するグループ内のアダプタ）から到来する「ハート・ビート」メッセージをモニタする。所定の時間内に「ハート・ビート」メッセージが受信されないと、「上流側の隣接メンバ」が故障したと想定する。そして、「デス」メッセージをグループ・リーダに送信し、新しいグループの形成を要求する。
【００４２】
「デス」メッセージを受信すると、グループ・リーダは、故障として検出されたアダプタを除く現グループ内の全アダプタが含まれる新しいグループの形成を試みる。グループ・リーダは、「コミット準備」メッセージを前記新しいグループの全アダプタへ送信する。続いて、このプロトコルは、参加プロトコルに関してすでに説明したシーケンスと同じシーケンスに従う。
【００４３】
「デス」メッセージを送信した後、デーモンは「コミット準備」メッセージをまもなく受け取ることを予測する。再試行が数多く繰り返されるが、「コミット準備」メッセージが受信されなければ、グループ・リーダ・アダプタ（又はそのホスティング・ノード）がデス状態であり、また「クラウン・プリンス」アダプタもデス状態であるため、グループ・リーダシップを取ることができないと解釈される。この場合、アダプタはそれ自身を単一アダプタ・グループに再初期化するとともに「解消」メッセージを送信し、グループ・メンバ全てが同様のことを行うように促す。この機構によって、グループの全メンバがグループ・リーダとクラウン・プリンスとが同時にデス状態となったことを知ることができる。
【００４４】
基本機構
一旦、ＡＭＧが形成されると、「上流側の隣接メンバ」によって送信された周期的な「ハート・ビート」メッセージを「下流側の隣接メンバ」がモニタすることができるように、「ハート・ビート」メッセージが好ましくは環状トポロジに送信される。なお、特許請求の範囲の１つ以上の請求項において、「ハート・ビート」メッセージは「第１のメッセージ」と呼ばれている。下流側の隣接メンバは、その上流側の隣接メンバから最近に「ハート・ビート」メッセージを受信したかどうかを見るために、周期的にチェックを行う。もし、最終チェック以後に「ハート・ビート」メッセージを受信していなければ、「ハート・ビート欠落」カウンタがインクリメントされる。もし、ハート・ビート欠落カウンタが所定の閾値Ｓ（「感度」）に達すると、比較的簡単なプロトコルによってリモート・アダプタがデス状態であると見なされ、そのデス状態が報告される。
【００４５】
本発明の範囲及び精神の範囲内で、非環状形態のトポロジを用いることも可能である。任意の簡便なトポロジを使用することができる。しかし、環状トポロジが好ましい。その理由は、環状トポロジが実現する上で簡単であるということ、またノードの数を増やした時により優れたスケーラビリティを示すということである。他のトポロジは、本明細書の他の箇所に記載されているように、構造的リンクの記述がメンバ・リストの通信に伴ってグループのメンバ又は将来のグループ・メンバにも伝えられることを必要とする。このことは、一般的に望ましくない複雑化をもたらすが、それでもなお、本発明の基礎をなす基本原則から逸脱することなく可能である。
【００４６】
しかし、ハート・ビート欠落カウンタが（Ｓよりも小さい）値Ｘに達すると、モニタされているアダプタに対してＩＣＭＰ（インターネット制御メッセージ・プロトコル）エコー要求パケットが送られるように、プロトコルが変更される。もし、リモート・ノード及びアダプタが活きているならば、たとえピア・デーモンが阻害されていたとしても、宛先ＯＳカーネル、及び最も好ましくはその割り込みハンドラがＩＣＭＰ「エコー応答」メッセージによって応答する。ハート・ビート欠落カウンタの値がＸ＋１等に達すると、その手順が繰り返される。もしモニタされているアダプタからＩＣＭＰ「エコー応答」メッセージが受信されると、このことは、「モニタされているアダプタがおそらく機能してはいるが、対応するデーモンは阻害されているか又はデス状態のいずれかであるかもしれない」と解釈される。もう一方の側で何が起きているかを知る直接的な方法がないことから、猶予期間が設定される。値Ｓよりも著しく大きい値Ｓ１に達するまで、ハート・ビート欠落カウンタがＳを過ぎることを許可される。その時点で、もしモニタされているアダプタから「ハート・ビート」メッセージが受信されなければ、該アダプタが最終的にデス状態であることを宣言する。
【００４７】
もし「ハート・ビート」メッセージがカウント値ＸとＳｉとの間のある点で再び受信されると、猶予期間が不活性化され、ハート・ビート欠落カウンタはゼロにリセットされる。猶予期間の目的は、メモリ枯渇又は他の何らかの要因によって阻害されているリモート・デーモンを償うことである。もし、リモート・アダプタ又はノードが実際にデス状態であるならば、ＩＣＭＰ「エコー応答」パケットが受信されないのであり、それによって猶予期間の設定がなされない。その結果、有効な「アダプタがデス状態となるイベント」が猶予期間によって遅れるという懸念はあてはならない。そのような遅れが生ずる唯一の機会は、対応するデーモンがデス状態になるか、もしくは無期限に阻害された場合であり、そのような問題は、過剰な負荷によってデーモンが一時的に阻害されるという問題よりも、比較的まれにしか生じない。
【００４８】
Ｓｉの値は、大きな負荷状態下にあるシステムでデーモンが阻害される「最も大きい合理的期間」に相当するように選択される。
【００４９】
Ｕｎｉｘ(R)システムの異なる「フレーバ」上では、ＩＣＭＰメッセージの送受信は「生ソケット」を開くプログラムを必要とする。生ソケットの挙動は、ローカル・アダプタによって受信されたＩＣＭＰパケットの全てが、生ソケットを開く各プラグラムに与えられるようなものである。これらのパケットを処理するために、ＣＰＵリソースが著しく費やされ、その多くが送信された「エコー」メッセージとは関係ないものである。この問題を軽減するために、猶予期間を適用するかどうかを決定する間、「生ソケット」はただ開いたままに維持される。もし、到来する「ハート・ビート」が欠落していないか、又は猶予期間がすでに設定されているならば、生ソケットが閉じられる。
【００５０】
コミット準備（ＰＴＣ）メッセージの猶予期間
基本のハート・ビート機構と同様に、グループの再形成もリアルタイム制約を有する。すなわち、もし一つのノードが適時に、すなわち「コミット準備＿ＡＣＫ」メッセージを待つことをグループ・リーダが諦めるまで、「コミット準備」パケットに応答することに失敗すれば、グループ・リーダによって対応するアダプタがデス状態であると宣言される。したがって、「コミット準備」メッセージを送信しているか又は該メッセージに応答している間にデーモンが阻害される場合のために、一つの機構が必要とされる。
【００５１】
「コミット準備」メッセージに応答している間にデーモンが阻害されるノードを償うために、同様の「ピング及び猶予期間」機構が導入される。もし、グループ・リーダが全ての再試行の後にでさえ一つのアダプタからの何らかの応答を得られないならば、グループ・リーダはＩＣＭＰ（インターネット制御メッセージ・プロトコル）エコー要求メッセージを該アダプタへ送信する。もし、「エコー応答」メッセージが受信されるならば、グループ・リーダは、リモート・デーモンが阻害されていると推測し、そのための猶予期間を設定する。しかし、この機構は、単独で問題を提示する。すなわち、「コミット」メッセージを待っている間に（猶予期間については知らない）他のアダプタの全てが「タイム・アウト」し、新しいグループを諦めることがあり得るからである。この問題を打ち消すために、他のアダプタも「ピング及び猶予期間」機構をグループ・リーダに適用する。グループ・リーダがＩＣＭＰエコー要求メッセージに応答し、かつ猶予期間が切れていない限り、他のアダプタは「コミット」メッセージを待ち続ける。注目すべきことは、非グループ・リーダ・ノードによって適用される猶予期間もまた、グループ・リーダ・ノードにあるデーモンがそれ自身を阻害し始める状態を取り扱うということである。非グループ・リーダ・ノードによって適用される猶予期間は、異なるノードが異なる再試行でそれぞれの「コミット準備」メッセージを受け取る、「コミット準備」再試行を考慮に入れている。
【００５２】
「デス」メッセージを送信するデーモンについても、前記と同じ方法が用いられる。「コミット準備」メッセージが到着するにはあまりにも長い（グループ・リーダ・ノードにあるデーモンが阻害されたためと考えられる）場合に、ＩＣＭＰエコー要求メッセージがグループ・リーダに送られる。
【００５３】
（新しいプロトコル・メッセージを生成することなく）前記の諸機構が成し遂げるものは、たとえプロトコルが実行されている間に対応するデーモンが阻害されたとしても、そのアダプタを新しいＡＭＧに含める能力である。
【００５４】
以下、図面を参照して、本発明の構造、環境、及び動作を説明する。特に、図１は、本発明が使用される環境を理解する上で有用である。この環境は、ネットワーク・アダプタ１１０〜１１７（及び図示の複数の経路）によって相互接続された複数のデータ処理ノード１００〜１０３から構成される。本発明が適用される典型的なノードは、以前はＲＳ／６０００ＳＰ（スケーラブル・パラレル用）と呼ばれていたＩＢＭのｐシリーズのサーバ製品である。一般に、各ノードは、少なくとも１つの中央処理装置、共用メモリ、ローカル・メモリ・キャッシュ、及び内蔵の不揮発性記憶装置（一般にハード・ディスクＤＡＳＤユニット）との接続を含む。各ノードの典型的なオペレーティング・システムは、本発明の譲受人によって提供されるようなＡＩＸオペレーティング・システムである。各ノードは、ＡＩＸであってもなくてもよいが、それ自身のオペレーティング・システムで走ることができる。ＡＩＸは、ＵＮＩＸ(R)に類似したプログラムであり、オペレーティング・システムのカーネル（又はコア）に向けられ、かつ基本的な「あなたはそこにいますか」のようなサービスを提供するために基本的には低いレベルで動作する「ピング」等の命令に基づいたエコー要求をサポートする。明らかに、ノードに障害がある場合、又は複数のネットワーク・アダプタの一つに障害がある場合でも、通信上の問題が生ずる。
【００５５】
図２は、２つのノード・グループ（すなわち、一方のグループはノード２００〜２０２によって構成され、他方のグループはノード３００〜３０２によって構成される）が存在する場合について説明する。ノード２００及び３００は、それぞれのグループのグループ・リーダである。図２の右端に示したグループ内のグループ・リーダ＃１（ノード２００）から「プロクレーム」メッセージが送られる。このメッセージは、それ自身の現グループ内にあるノードに送られる必要はない。このメッセージは、ネットワーク内の全ての既知のノードへ送信される。しかし、そのようなメッセージは、グループ・リーダによってのみ応答されるため、図２では「プロクレーム」メッセージの送信を実線及び破線を用いて示している。グループ・リーダのみが「プロクレーム」メッセージに対して応答する。一つのグループ・リーダが既存のグループに参加を望む場合のそのような応答は、該「プロクレーム」メッセージを送信したグループ・リーダへの「参加」メッセージの送信となる（図３を参照）。グループ参加のためのプロトコルは、図４に示すように、関係する全てのノードに対して「コミット準備」（ＰＴＣ）メッセージを送信することも含んでいる。ＰＴＣメッセージに対する通常の応答は、該ＰＴＣメッセージの受信を確認するメッセージの送信、すなわち図５に示すように、同一ノードからのＰＴＣ＿ＡＣＫ信号の送信である。
【００５６】
図６は、「コミット」動作に関するさらなる送信を処理するために、グループ・リーダ２００から「メイア・ノード」２０２の「コミット同報通信」メッセージ送信を使用することについて説明するためのものである。メイア・ノードの概念は、好ましくはグループ・リーダからの通信負担の一部を軽減するために使われる。このことは、図７に具体的に示されている。図７には、メイア・ノード２０２からグループ・リーダ２００へ「コミット同報通信確認」メッセージを返信することに加えて、「コミット」メッセージの送信プロトコルも示されている。特に、「メイア」ノードは、グループ・リーダからその仕事、特に通信負担を軽減するのに有用な機構として用いられるように示されている。一般に、各サブネット上に一つの「メイア」があり、また各メイアはグループ・リーダから特定の割り当てられたメッセージをそのサブネットへ中継する役割を担う。どれに対しても出力される必要がある幾つかのメッセージに関して、グループ・リーダは各サブユニットから一つのメイア・ノードを選択し、そのようなメイアに対してメッセージをポイント・ツー・ポイントで送る。次に、各メイア・ノードは、そのメッセージを（該メッセージの種類及びグループの大きさに応じて）同報通信又はポイント・ツー・ポイントでそのサブセット上の各アダプタに送信する。グループ・リーダからメイアへ送信され、次にメイアからサブセットへ送信されるメッセージは、確認及び再試行の対象となる。もし、一つのメイア・ノードがメッセージの確認に失敗すると、グループ・リーダは該失敗したメイアのサブセット上で新しいメイアを選択してプロセスを繰り返す。いずれのものに対しても到達する必要がある全てのメッセージがメイア・ノードを中継として用いて送られはしない。例えば、「コミット準備」（ＰＴＣ）メッセージは、「グループ・リーダ・ワント・ツー・ビー」からポイント・ツー・ポイントで各及び全ての潜在的グループ・メンバに対して送られる。この種のメッセージ送信では、メイア・ノードは用いられない。
【００５７】
ノードを加えるために確立されたプロトコルの終わりで、グループ・リーダ２００は、新しいグループにあるノードの全てを新しいトポロジに編成する。図８に示すように、このトポロジは、前記した理由（特に、簡潔性及びスケーラビリティ）により、好ましくは環状トポロジである。本発明の好ましい実施形態では、新しいグループ・リーダが最も高いＩＰアドレスを持つノードとなるように選択される。しかし、プロセスが一意的な選択に帰着する限り、任意の他の簡便な機構もまたこの目的のために用いられてもよい。例えば、最も長い時間働いていたノードが選択されてもよい。また、注目すべき点は、ノードのデス状態もまた新しいグループ・トポロジの形成を招くということである。ノード及び／又はグループ付加のための新しいトポロジの構築とともに使用可能である同じ機構もまたノード・デス状態のイベントで使用可能である。しかし、ノード・デス状態の場合、環状トポロジ状況は、事実上、消滅したノードを単にバイパスするだけでよいので、新しいトポロジによって構成することが特に容易である。
【００５８】
本発明が用いる基本的な動作は、前記したハート・ビート機構である。これもまた図９〜図１１により詳細に示されている。図９は、ハート・ビート・メッセージが環状トポロジ・グループを順に回ることを示している。図１０は、ノード２０１でノード又はアダプタの障害が生ずることを示している。ハート・ビート・メッセージが周期的であり、かつ特定の時間に予測されることから、ノード３００においてその存在が欠落することが分かる。このようなことが生じた場合、ノード「デス・メッセージ」がノード３００からグループ・リーダ２００へ送信される。そして、グループ・リーダ２００は、故障したノード２０１を除く新しいグループの形成を試みることによって応答する。そうするため、図１１に示されているように、「コミット準備」（ＰＴＣ）メッセージが先のグループに残るノードの全てに送られ、これには、グループ・リーダであるノード２００に対するＰＴＣメッセージも含まれる。次に、新しいグループの形成が前記した方法で進行する。
【００５９】
図１２は、ノード＃２からのハート・ビート・メッセージをノード＃１において最初に受信する様子を模式的に示したものである。もし所定数のそのようなメッセージが受信されなければ、ＩＣＭＰエコー要求メッセージがノード＃１からノード＃２へ送信される。そのようなエコー要求メッセージは、優先度操作が利用可能であるポート及び／又はソフトウェアに向けられる。そのようなメッセージが一般に非常に単純に設計され、かつ受信側（又は送信側でも）相当量のリソース又はプロセッサ時間を必要としないことから、その優先度が提供される。そのようなメッセージは単純で、かつ該メッセージに対し可能な限り素早く応答することができる。したがって、たとえメモリ制約問題等によって、特定の予測されたメッセージがホルド・アップされても、ＩＣＰＭ要求及びＩＣＭＰエコー応答は素早く処理され、ノードのデス状態の早まった報告及び誤った報告を防止できる。実際、ノードは「一時的な病気」に罹るだけである。
【００６０】
図１３は、「短期間のノードの病気」ではなく、正真正銘のノード又はアダプタの障害が存在するイベントでのハート・ビートとメッセージとの交換を示す。特に、この方法が所定数の欠落したハート・ビート・メッセージを許容することが分かる。所定数のハート・ビート・メッセージ（好ましくは２）が欠落した場合、ＩＣＭＰエコー要求メッセージを送信するために幾つかの試みがなされる。もしそのような試みを所定の回数（好ましくは２回）行った場合、ノード＃２がデスであると宣言する。
【００６１】
図１４は、図１３と類似しているが、ノードが実際には「デス」ではなく、短期間の問題に遭遇しているだけである場合に生ずる本発明の利点を説明する。そのような場合、疑わしいノードへＩＣＭＰエコー要求メッセージが送られ、このメッセージに対する応答が送信ノード（ここではノード＃１）へ送られる。このことによって、ハート・ビート・メッセージの再設定のための猶予期間の設定を可能とする。示した例では、閾値はそのようなハート・ビート数が５から８までの範囲である。ここで、短期間の病気は、ノード＃２上のデーモンを阻害することによって、おそらくはメモリ制約問題によって生ずる。しかし、本発明が性能及び安定性の恩恵を与える他の原因もあると思われる。
【００６２】
図１５は、ハート・ビート・メッセージから「コミット準備」（ＰＴＣ）メッセージ送信への前記方法の拡張を説明する。この例では、図面を簡潔にするため、関係しているノードが３つしかない。すなわち、ノード＃１〜＃３である。シーケンスは、ノード＃１から（他のノードの全てへ）の「コミット準備」メッセージの送信によって開始する。また、このメッセージは、ＰＴＣメッセージへの応答が期待される時期を決定するための機構として「ＰＴＣ再試行タイマ」を開始させる。（デス状態のノード又はアダプタとは対照的に、阻害されたデーモンに起因する）ノード＃３からの確認メッセージの欠如によって、ノード＃３に対する第２のＰＴＣメッセージの送信が引き起こされる。ＰＴＣ再試行＃１メッセージに対する応答の欠如によって、ノード＃３に対する低いレベルのＩＣＭＰエコー要求の送信が引き起こされる。ＰＴＣメッセージに対する応答の欠如は、一時的なデーモン阻害に起因するのみであることから、ノード＃３は、依然としてエコー要求メッセージに対する応答が可能である。すなわち、ノード＃３は、ＩＣＭＰエコー応答メッセージをノード＃１に対して送信する。ノード＃１でのＩＣＭＰエコー応答メッセージの受信は、ノード＃３が一時的に阻害されただけであり、「デス」状態となったわけではないことを意味している。このことによって、ノード＃３でのデーモン阻害にもかかわらず、ＰＴＣメッセージの確認の時間を延ばすことが可能となる。この例では、ＰＴＣメッセージはノード＃２及びノード＃３に送られる。ノード＃２はＰＴＣ＿ＡＣＫ（確認）メッセージによって応答する。ノード＃３からの最初のＰＴＣメッセージに対する応答の欠如は、ノード＃３に対するＩＣＭＰエコー要求メッセージの送信を引き起こす。前記したように、このメッセージは、単純で、より直接的であり、さらにノード及びそのアダプタが活きているか、さもなければビジー状態であるイベントにおいて応答する可能性がより高い。このメッセージ交換がノード＃１とノード＃３との間で起きている間、ノード＃２は最初のＰＴＣメッセージを確認し、ノード＃１からの「コミット」メッセージを待つ。もし、ノード＃２が「コミット」メッセージを受信せず、その予定到着時間が過ぎたならば、ノード＃２は、問題があると想定して、好ましくはＩＣＭＰエコー要求メッセージをノード＃１へ送信する。図１５によれば、ノード＃２から送られたＩＣＭＰエコー要求メッセージに対する応答（すなわち、ＩＣＭＰエコー応答メッセージ）は、ノード＃２で受信されることが分かる。したがって、認識及び延長についての類似のデフォルト設定によって、コミット・メッセージを受信するための通常の最終期限が実質的に前記と同様の方法で延長される。このことは、全てのノードが最終的にコミット・メッセージを受信し、かつ応答することを保証する。
【００６３】
前記のことから、前記した目的の全てが本発明の１つ以上の実施形態において達成されることを理解すべきである。また、リモート・アダプタ及び／又はノード障害を検出するための基本機構は、その殆どの機能性について相対的に低い優先度のメッセージ送信に基づいているが、代替機構としての猶予期間と組み合わせてエコー要求メッセージを用いることで、より低い、より高い優先度のメッセージ・システムに復帰することができることも理解すべきである。特に、本発明は分散プロトコルの実行中に阻害されたデーモンを処理するための基本機構を提供することが分かる。さらに、本発明は新しいメッセージをプロトコルに導入する必要がないことも分かる。
【図面の簡単な説明】
【００６４】
【図１】本発明が適用される環境、すなわち相互接続された複数のデータ処理ノードからなるネットワーク内の環境を説明するためのブロック図である。
【図２】「プロクレーム」メッセージの送信におけるノードの範囲を説明するための信号フロー図である。
【図３】図２に類似した図であって、特に、「プロクレーム」メッセージに対する「参加」応答に関係するノードを説明するための信号フロー図である。
【図４】図２及び図３に類似した図であって、特に、新しいノードをグループに参加させることに関係するプロトコルの「コミット準備」（ＰＴＣ）メッセージの送信を説明するための信号フロー図である。
【図５】図４に類似した図であって、特に、「コミット準備」メッセージの送信に対する確認（ＰＴＣ＿ＡＣＫ）を説明するための信号フロー図である。
【図６】「コミット」同報通信メッセージに関係するノードを説明するための信号フロー図である。
【図７】図６に類似した図であって、特に、「コミット」メッセージの送信におけるノードの範囲を説明するための信号フロー図である。
【図８】複数のノードからなる新しいグループの形成に続いて現れる環状接続を説明するためのノード・トポロジ図である。
【図９】ノード・グループ内でのハート・ビート・メッセージの伝わる方向を説明するための信号フロー図である。
【図１０】図９に類似した図であって、特に、ノード・デスのイベントにおける「デス」メッセージの送信を説明するための信号フロー図である。
【図１１】図９及び図１０に類似した図であって、特に、「コミット準備」メッセージが送信されるノードの範囲を説明するための信号フロー図である。
【図１２】より低いレベル及び／又はより高い優先度エコー要求メッセージが送られる前に幾つかのハート・ビート・メッセージが欠落する概念を説明するための時系列図である。
【図１３】ノード２上のトポロジ・サービス・デーモンが一時的に阻害されている状態でのメッセージ送信を説明するためのイベント時系列図である。
【図１４】ノード２がデスとなった状態でのメッセージ送信を説明するためのイベント時系列図である。
【図１５】「コミット準備」メッセージ及びそれに対応する確認メッセージの送信を説明するためのイベント時系列図である。
【符号の説明】
【００６５】
１００、１０１、１０２、１０３    データ処理ノード
１１０、１１１、１１２、１１３、１１４、１１５、１１６、１１７  ネットワーク・アダプタ
２００  ノード（グループ・リーダ）
２０１、２０２    ノード
３００  ノード（グループ・リーダ）
３０１、３０２  ノード
【図１】
2006146913.tif 000003
【図２】
2006146913.tif 000004
【図３】
2006146913.tif 000005
【図４】
2006146913.tif 000006
【図５】
2006146913.tif 000007
【図６】
2006146913.tif 000008
【図７】
2006146913.tif 000009
【図８】
2006146913.tif 000010
【図９】
2006146913.tif 000011
【図１０】
2006146913.tif 000012
【図１１】
2006146913.tif 000013
【図１２】
2006146913.tif 000014
【図１３】
2006146913.tif 000015
【図１４】
2006146913.tif 000016
【図１５】
2006146913.tif 000017