(57)【特許請求の範囲】
【請求項１】
分散コンピューティング環境において、プロセッサ・グループのグループ・リーダに障害が発生した場合に、前記プロセッサ・グループの他のプロセッサのいずれかにより新しいグループ・リーダを決定するシステムであって、
前記プロセッサ・グループの各プロセッサは、前記プロセッサ・グループに加入しているプロセッサを識別させると共に、前記プロセッサ・グループに加入を要求するプロセッサがある場合に前記加入の要求を受け取ったグループ・リーダから送られる更新の通知により前記加入を要求するプロセッサがリストの終わりに追加されて更新されるメンバシップ・リストと、
前記グループ・リーダに障害が発生した場合、前記メンバシップ・リストから次のプロセッサを、障害の発生したグループ・リーダの代わりに前記プロセッサ・グループの新しいグループ・リーダとして選択する手段とを含むシステム。
【請求項２】
前記選択する手段が、前記メンバシップ・リストから次のアクティブ・プロセッサを選択する手段を含むことを特徴とする、請求項１に記載のシステム。
【請求項３】
前記プロセッサ・グループに前記新しいグループ・リーダを通知する手段をさらに含む、請求項１に記載のシステム。
【請求項４】
前記システムは、ネーム・サーバを含み、前記ネーム・サーバは、前記加入を要求したプロセッサに対してグループ・リーダを通知する、請求項１に記載のシステム。
【請求項５】
前記プロセッサ・グループに属する少なくとも一つのプロセッサが含む前記選択する手段は、前記プロセッサにある前記メンバシップ・リストから前記新しいグループ・リーダを選択し、前記プロセッサ・グループの少なくとも一つのプロセッサがネーム・サーバに前記新しいグループ・リーダを通知することを特徴とする、請求項１に記載のシステム。
【請求項６】
前記ネーム・サーバによって前記プロセッサ・グループに前記新しいグループ・リーダを通知する手段をさらに含む、請求項５に記載のシステム。
【請求項７】
前記新しいグループ・リーダは、前記新しいグループ・リーダとして選択される前に、前記プロセッサ・グループに加入するプロセッサに対して、前記新しいグループ・リーダが選択される前に送られたメッセージを受け取る手段をさらに含む、請求項１に記載のシステム。
【請求項８】
前記新しいグループ・リーダによって、前記プロセッサ・グループのプロセッサが逸したメッセージを提供する手段をさらに含む、請求項７に記載のシステム。
【請求項９】
前記新しいグループ・リーダに要求を送る手段をさらに含む、請求項１に記載のシステム。
【請求項１０】
分散コンピューティング環境において、プロセッサ・グループのグループ・リーダに障害が発生した場合に、前記プロセッサ・グループの他のプロセッサのいずれかにより新しいグループ・リーダを決定する方法であって、
前記プロセッサ・グループの各プロセッサは、前記プロセッサ・グループに加入しているプロセッサを識別させると共に、前記プロセッサ・グループに加入を要求するプロセッサがある場合に前記加入の要求を受け取ったグループ・リーダから送られる更新の通知により前記加入を要求するプロセッサがリストの終わりに追加されて更新されるメンバシップ・リストをメモリに記憶させ、
前記グループ・リーダに障害が発生した場合に、前記メンバシップ・リスト内の加入順に従い次のプロセッサを、前記複数のプロセッサのうちの少なくとも１つが前記メンバシップ・リストから選択するステップと、
前記複数のプロセッサのうちの少なくとも１つが、前記次のプロセッサを前記プロセッサ・グループの新しいグループ・リーダとして認識するステップとを含む方法。
【請求項１１】
前記複数のプロセッサのうちの少なくとも１つが選択するステップは、前記メンバシップ・リストから次のアクティブ・プロセッサを選択するステップを含むことを特徴とする、請求項１０に記載の方法。
【請求項１２】
新しいグループ・リーダを認識した、前記複数のプロセッサのうちの少なくとも１つが、前記プロセッサ・グループに加入している他の少なくとも１つのプロセッサに、前記新しいグループ・リーダを通知するステップをさらに含む、請求項１０に記載の方法。
【請求項１３】
前記少なくとも１つのプロセッサが、前記分散コンピューティング環境に含まれるネーム・サーバに、前記新しいグループ・リーダを前記メンバシップ・リストから選択させるために、前記新しいグループ・リーダの選択を前記ネーム・サーバに要求するステップをさらに含む、請求項１０に記載の方法。
【請求項１４】
前記選択するステップは、前記プロセッサ・グループに加入しているプロセッサが、前記プロセッサ内にある前記メンバシップ・リストから新しいグループ・リーダを選択するステップを含み、前記分散コンピューティング環境に含まれるネーム・サーバに前記新しいグループ・リーダを通知するステップをさらに含むことを特徴とする、請求項１０に記載の方法。
【請求項１５】
前記ネーム・サーバが前記プロセッサ・グループに加入しているプロセッサの少なくとも１つに前記新しいグループ・リーダを通知するステップをさらに含む、請求項１４に記載の方法。
【請求項１６】
前記新しいグループ・リーダは、当該グループ・リーダとして選択される前に、前記プロセッサ・グループに加入するプロセッサに対して、前記新しいグループ・リーダが選択される前に送られたメッセージを受け取るステップをさらに含む、請求項１０に記載の方法。
【請求項１７】
前記新しいグループ・リーダが前記プロセッサ・グループのいずれかのプロセッサが逸したメッセージを提供するステップをさらに含む、請求項１６に記載の方法。
【請求項１８】
前記新しいグループ・リーダに、前記少なくとも１つのプロセッサが要求を送るステップをさらに含む、請求項１０に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般には分散コンピューティング環境に関し、具体的には分散コンピューティング環境内で実行されるプロセッサのグループのリーダの障害から回復する機構に係わる。
【０００２】
【従来の技術】
典型的なコンピューティング・システムには、いくつかのプロセッサが定義された事前定義済み構成がある。アクティブ・プロセッサは処理するアプリケーションを受け取り、システム構成に従ってアプリケーションを実行する。
【０００３】
【発明が解決しようとする課題】
しかし、プロセッサが、プロセッサのグループによって関連性のあるプロセスが実行されるプロセッサ・グループのメンバになれるようにする機構が必要である。すなわち、アクションをグループ単位で行うことができるようにする機構が必要である。さらに、各プロセッサ・グループにリーダを設け、グループ・リーダを使用してその特定のグループのイベントの管理と調整を行う機構が存在する必要がある。特に、現行グループ・リーダに障害が発生した場合に新しいグループ・リーダを決定するために使用することができる機構の存在が必要である。
【０００４】
【課題を解決するための手段】
分散コンピューティング環境におけるプロセッサ・グループのグループ・リーダの障害の回復機構を設けることによって、従来技術の欠点が克服され、追加の利点が得られる。プロセッサ・グループにプロセッサが加入した順に順序づけられたメンバシップ・リストから新しいグループ・リーダを選択する。新しいグループ・リーダは、メンバシップ・リスト内で、障害が発生したグループ・リーダの後の次のプロセッサである。
【０００５】
本発明の一実施例では、プロセッサ・グループには新しいグループ・リーダが通知される。本発明の他の実施例では、新しいグループ・リーダはネーム・サーバから入手され、ネーム・サーバはメンバシップ・リストから新しいグループ・リーダを選択する。
【０００６】
本発明のグループ・リーダ回復機構は、現行グループ・リーダに障害が発生した場合に新しいグループ・リーダを決定する柔軟性のある技法を備える。この技法によって、グループのメンバは新しいグループ・リーダを知ることができ、グループの制御と管理をそのグループ・リーダに依存することができる。
【０００７】
本発明の技法によってその他の特徴および利点も得られる。本明細書では本発明の他の実施例および実施形態についても詳述し、特許請求の範囲の一部と見なされる。
【０００８】
【発明の実施の形態】
一実施例では、可用性の高いマルチコンピュータ・アプリケーションを実現するために、本発明の技法を分散コンピューティング環境で使用する。可用性の高いアプリケーションは、障害発生後に実行を継続することができる。すなわち、そのアプリケーションはフォールトトレラントであり、ユーザ・データの保全性が確保される。
【０００９】
可用性の高いシステムでは、分散コンピューティング環境内の処理ノードで稼働しているサブシステム（たとえばプロセス・グループ）に加えられる変更の調整、管理、および監視を行えることが重要である。本発明の原理によると、前記の機能を実施する機構が設けられる。このような機構の一例を本明細書では「グループ・サービス」と呼ぶ。
【００１０】
「グループ・サービス」は、分散コンピューティング環境の１つまたは複数のプロセッサ上で稼働しているサブシステムに加えられる変更の調整、管理、および監視を行う機能を提供する、システム規模のフォールトトレラントな可用性の高いサービスである。グループ・サービスは、本発明の技法により、フォールトトレラント・サブシステムの設計および実施のためと、複数システムの整合性のある回復を実現するための、統合されたフレームワークを提供する。グループ・サービスは、少数の中核概念に基づく単純なプログラミング・モデルを提供する。本発明の原理によると、これらの概念には、各プロセス・グループと共にアプリケーション固有の情報を維持する、クラスタ規模のプロセス・グループ・メンバシップおよび同期サービスが含まれる。
【００１１】
前述のように、一実施例では、本発明の機構は「グループ・サービス」機構に含まれる。しかし、本発明の機構は他の様々な機構内で、または様々な機構と共に使用することができ、したがって「グループ・サービス」は一例に過ぎない。本発明の技法を組み込むための「グループ・サービス」という用語の使用は、便宜のために過ぎない。
【００１２】
一実施形態では、本発明の機構は図１に示す一例のような分散コンピューティング環境に組み込んで使用される。一実施例では、分散コンピューティング環境１００は、たとえば、複数のＬＡＮゲート１０４を介して互いに結合された複数のフレーム１０２を含む。フレーム１０２とＬＡＮゲート１０４について以下に詳述する。
【００１３】
一実施例では、分散コンピューティング環境１００は、各フレームが複数の処理ノード１０６を備える８個のフレームを含む。一例では、各フレームは１６個の処理ノード（プロセッサとも呼ぶ）を含む。各処理ノードは、たとえば、ＵＮＩＸベースのオペレーティング・システムであるＡＩＸを実行するＲＩＳＣ／６０００コンピュータである。フレーム内の各処理ノードは、たとえば内部ＬＡＮ接続を介してフレームの他の処理ノードに結合されている。さらに、各フレームはＬＡＮゲート１０４を介して他のフレームに結合されている。
【００１４】
たとえば、各ＬＡＮゲート１０４には、ＲＩＳＣ／６０００コンピュータ、ＬＡＮへの任意のコンピュータ・ネットワーク接続、またはネットワーク・ルータが含まれる。しかし、これらは例に過ぎない。当業者なら、他のタイプのＬＡＮゲートがあり、フレームを互いに結合するために他の機構も使用することができることがわかるであろう。
【００１５】
上記に加えて、図１の分散コンピューティング環境も一例に過ぎない。８個より多い数または少ない数のフレームや、１フレーム当たり１６個より多い数または少ない数のノードを備えることも可能である。さらに、処理ノードはＡＩＸをを稼働させるＲＩＳＣ／６０００コンピュータでなくてもよい。処理ノードのうちの一部または全部が異なるタイプのコンピュータや異なるオペレーティング・システムを備えることもできる。これらの変形形態はすべて本願発明の一部と見なす。
【００１６】
一実施形態では、本発明の機構を組み込んだ「グループ・サービス」サブシステムは、分散コンピューティング環境１００の複数の処理ノードにわたって分散している。具体的には、一実施例では処理ノード１０６のうちの１つまたは複数のノード内に「グループ・サービス」デーモン２００（図２）を配置する。この「グループ・サービス」デーモンをまとめて「グループ・サービス」と呼ぶ。
【００１７】
グループ・サービスは、たとえばプロセス・グループの複数のプロセス間の通信と同期化を容易にし、たとえば分散回復同期機構の提供など多様な状況で使用することができる。「グループ・サービス」の機能を使用したいプロセス２０２（図２）は「グループ・サービス」デーモン２００に結合される。具体的には、そのプロセスは、「グループ・サービス」に付随するコード（たとえばライブラリ・コード）のうちの少なくとも一部をプロセス自体のコードにリンクさせることによって「グループ・サービス」に結合される。本発明の原理によると、このリンクによってプロセスは、以下に詳述するように本発明の機構を使用することができる。
【００１８】
一実施形態では、プロセスはアプリケーション・プログラミング・インタフェース２０４を介して本発明の機構を使用する。具体的には、アプリケーション・プログラミング・インタフェースは、一例では「グループ・サービス」に含まれている本発明の機構を使用するためのインタフェースを、プロセスに提供する。一実施例では、「グループ・サービス」２００は内部層３０２（図３）と外部層３０４を含み、それぞれの層について以下に詳述する。
【００１９】
本発明の原理によると、内部層３０２は限定された１組の機能を外部層３０４に提供する。内部層の限定された１組の機能を使用して、より豊富で広範囲の１組の機能を構築することができ、それを外部層で実施し、アプリケーション・プログラミング・インタフェースを介してプロセスにエクスポートする。「グループ・サービス」の内部層（メタグループ層とも呼ぶ）は「グループ・サービス」デーモンに関係し、デーモンに結合されたプロセス（すなわちクライアント・プロセス）には関係しない。すなわち、内部層はデーモンを含むプロセッサに労力を集中させる。一実施例では、１つの処理ノード上には１つの「グループ・サービス」デーモンしかない。しかし、分散コンピュータ環境内の処理ノードのうちのサブセットまたは全部が「グループ・サービス」デーモンを含むことができる。
【００２０】
「グループ・サービス」の内部層は、プロセッサ・グループごとに機能を実行する。ネットワーク内には複数のプロセッサ・グループが存在することができる。各プロセッサ・グループ（メタグループとも呼ぶ）は、その上で実行される「グループ・サービス」を持つ１つまたは複数のプロセッサを含む。特定のグループのプロセッサは、関連性のあるプロセスを実行するという点で関連している。（一実施例では、関連性のあるプロセスは共通の機能を実現する。）たとえば、図４を参照すると、処理ノード１と処理ノード２のそれぞれがプロセスＸを実行しているため、プロセッサ・グループＸ（４００）はこの２つのノードを含むが、処理ノード３は含まない。したがって、処理ノード１および２はプロセッサ・グループＸのメンバである。処理ノードは任意の数のプロセッサ・グループのメンバとなることもいずれのプロセッサ・グループのメンバにもならないこともでき、プロセッサ・グループは１つまたは複数のメンバを共通して持つことができる。
【００２１】
プロセッサ・グループのメンバになるためには、プロセッサはそのグループのメンバとなるように要求する必要がある。本発明の原理によると、特定のグループに関連するプロセス（たとえばプロセスＸ）が対応するプロセス・グループ（たとえばプロセス・グループＸ）に加わることを要求し、プロセッサがその対応するプロセス・グループを認識していない場合に、プロセッサはその特定のプロセッサ・グループ（たとえばプロセッサ・グループＸ）のメンバとなるように要求する。特定のプロセス・グループに加入する要求を扱うプロセッサ上のグループ・サービス・デーモンは、そのプロセス・グループを認識していないため、対応するプロセッサ・グループのメンバではないことを把握する。したがって、プロセッサはメンバになるように要求し、それによってプロセスがそのプロセス・グループのメンバになることができるようにする。（プロセッサ・グループのメンバになる１つの技法については以下で詳述する。）
【００２２】
内部層３０２（図３）は、プロセッサ・グループごとにいくつかの機能を実行する。これらの機能には、たとえばグループ・リーダの維持、挿入、マルチキャスト、離脱、および障害などが含まれ、それぞれについては以下で詳述する。
【００２３】
本発明の原理によると、ネットワークの各プロセッサについてグループ・リーダを選択する。一実施例では、グループ・リーダは特定のグループへの加入を要求する最初のプロセッサである。本明細書で述べるように、グループ・リーダはそのグループ・リーダのプロセッサ・グループに関連づけられた活動を制御する役割を果たす。たとえば、処理ノードであるノード２（図４）がプロセッサ・グループへの加入を要求する最初のノードである場合、処理ノード２がグループ・リーダであり、プロセッサ・グループＸの活動を管理する役割を果たす。処理ノード２は複数のプロセッサ・グループのグループ・リーダとなることができる。
【００２４】
たとえばプロセッサがグループからの離脱を要求したり、プロセッサが障害を起こしたり、プロセッサ上のグループ・サービス・デーモンに障害が発生したりした場合など、何らかの理由でグループ・リーダがプロセッサ・グループから外される場合、グループ・リーダの回復が行われる。具体的には、ステップ５００ａ「新しいグループ・リーダを選択する」（図５）で、新しいグループ・リーダが選択される。
【００２５】
一実施例では、新しいグループ・リーダを選択するために、グループに加入したプロセッサ順に順序づけられたプロセッサ・グループのメンバシップ・リストがグループの１つまたは複数のプロセッサによって走査され、リスト内の次のプロセッサを探し出す（ステップ５０２「メンバシップ・リスト内の次のメンバを入手する」）。その後、リストから入手したプロセッサについてアクティブかどうかを判断する（照会５０４「メンバはアクティブか」）。一実施例では、これは分散コンピューティング環境の処理ノードにわたって分散された他のサブシステムが判断する。このサブシステムは少なくともメンバシップ・リスト内のノードに信号を送り、特定のノードから応答がなければ、そのノードが非アクティブであるとみなす。
【００２６】
選択されたプロセッサがアクティブでない場合、再びアクティブ・メンバが見つかるまでメンバシップ・リストが走査される。リストからアクティブ・プロセッサを入手すると、そのプロセッサがそのプロセッサ・グループの新しいグループ・リーダになる（ステップ５０６「選択されたメンバが新しいグループ・リーダである」）。
【００２７】
たとえば、３つの処理ノードが以下の順序でプロセッサ・グループＸに加入しているものとする。
プロセッサ２、プロセッサ１、およびプロセッサ３
したがって、プロセッサ２が最初のグループ・リーダである（図７参照）。しばらくしてプロセッサ２がプロセッサ・グループＸから離脱し、したがって新しいグループ・リーダが必要になる。プロセッサ・グループＸのメンバシップ・リストによると、プロセッサ１が次のグループ・リーダである。しかし、プロセッサ１が非アクティブの場合は、プロセッサ３が新しいグループ・リーダに選ばれることになる（図８参照）。
【００２８】
本発明の原理によると、一実施例ではメンバシップ・リストはプロセッサ・グループの各処理ノードのメモリに記憶される。したがって、上記の例では、プロセッサ１、プロセッサ２、およびプロセッサ３はすべてメンバシップ・リストのコピーを保持することになる。具体的には、グループに加入しようとする各プロセッサは現行グループ・リーダからメンバシップ・リストのコピーを受け取る。他の実施例では、グループに加入しようとする各プロセッサは現行グループ・リーダ以外のグループの別のメンバからメンバシップ・リストを受け取る。
【００２９】
図５に戻って参照すると、本発明の一実施例では、新しいグループ・リーダが選択されると、その新しいグループ・リーダは新しいグループ・サーバであることをネーム・サーバに通知する（ステップ５０８「ネーム・サーバに通知する」）。一例では、ネーム・サーバ７００（図９）はネーム・サーバとして指定された分散コンピューティング環境内の処理ノードの１つである。ネーム・サーバは、たとえばネットワークのすべてのプロセッサ・グループのリストやすべてのプロセッサ・グループのグループ・リーダのリストを含む特定の情報を記憶する中央記憶場所の役割を果たす。この情報は、ネーム・サーバ処理ノードのメモリに記憶される。ネーム・サーバは、プロセッサ・グループ内の処理ノードでもプロセッサ・グループとは独立した処理ノードでもよい。
【００３０】
一実施例では、ネーム・サーバ７００には、新しいグループ・リーダのグループ・サービス・デーモンからネーム・サーバに送られるメッセージによってグループ・リーダの変更が通知される。その後、ネーム・サーバはたとえばアトミック・マルチキャストを使用してグループの他のプロセッサに新しいグループ・リーダを通知する（ステップ５１０「グループの他のメンバに通知する」（図５））。（マルチキャストはブロードキャストと類似した機能であるが、マルチキャストではメッセージはシステムのすべてのプロセッサに送られるのではなく、選択されたグループに宛てて送られる。一実施例では、マルチキャストは、メッセージと宛先として意図された受信先のリストとを受け取り、たとえばユーザ・データグラム・プロトコル（ＵＤＰ）または伝送制御プロトコル（ＴＣＰ）を使用して、意図された各受信先に２点間メッセージ送信を行うソフトウェアを設けることによって行うことができる。他の実施例では、メッセージと意図された受信先のリストは、イーサネットなどの基礎ハードウェア通信機構に渡され、その基礎ハードウェア通信機構がマルチキャスト機能を提供することになる。）
【００３１】
本発明の他の実施例では、新しいグループ・リーダ以外のグループのメンバが、ネーム・サーバに新しいグループ・リーダの識別情報を通知する。他の実施例では、プロセッサ・グループ内の各プロセッサがメンバシップ・リストを持っており、新しいグループ・リーダを自分で判断しているため、グループのプロセッサに対して新しいグループ・リーダは明示的には通知されない。
【００３２】
本発明の他の実施例では、新しいグループ・リーダが必要な場合、ネーム・サーバに新しいグループ・リーダの識別情報を求める要求がネーム・サーバに対して送られる（ステップ５００ｂ「ネーム・サーバに新しいグループ・リーダを要求する」（図６））。この実施例では、ネーム・サーバにもメンバシップ・リスがあり、ネーム・サーバは上述と同じステップをたどって新しいグループ・リーダを判断する（ステップ５０２、５０４、および５０６）。新しいグループ・リーダが判断されると、ネーム・サーバはプロセッサ・グループの他のプロセッサに新しいグループ・リーダを通知する（ステップ５１０「グループの他のメンバに通知する」）。
【００３３】
内部層またはメタグループ層によって実施されるグループ・リーダ維持機能に加えて、挿入機能も実施される。挿入機能は、グループ・サービス・デーモン（すなわちグループ・サービス・デーモンを実行するプロセッサ）が特定のプロセッサ・グループに加わりたい場合に使用される。前述のように、プロセッサは、プロセッサで実行されているプロセスがプロセス・グループに加わりたい場合で、プロセッサがそのプロセス・グループを認識していない場合に、特定のプロセッサ・グループに加わることを要求する。
【００３４】
他の実施例では、プロセッサ・グループのメンバになるために、グループに加入したいプロセッサはまずそのプロセッサ・グループのグループ・リーダがどれであるかを判断する（ステップ８００「グループ・リーダを判断する」（図１０））。一実施例では、ネーム・サーバ７００にプロセッサ・グループの名前を送り、ネーム・サーバにそのグループのグループ・リーダの識別情報を要求することによってグループ・リーダが判断される。
【００３５】
要求側プロセッサが（グループに対する最初の要求であるため）グループ・リーダであるとネーム・サーバが応答した場合（照会８０１）、その要求側プロセッサがプロセッサ・グループを形成する（ステップ８０３「グループを形成する」）。具体的には、その特定のプロセッサ・グループのメンバシップ・リストを作成し、そのリストには要求側プロセッサが入れられる。
【００３６】
プロセッサがグループ・リーダでない場合は、ネーム・サーバからその識別情報を入手したグループ・リーダにメッセージを使用して挿入要求を送る（ステップ８０２「グループ・リーダに挿入要求を送る」）。グループ・リーダは要求側プロセッサをプロセッサ・グループに加える（ステップ８０４「グループ・リーダがプロセッサをプロセッサ・グループに挿入する」）。具体的には、一実施例では、グループ・リーダのグループ・サービス・デーモンがそのメンバシップ・リストを更新し、マルチキャストを使用してプロセッサ・グループの他の各グループ・サービス・デーモンに、そのプロセッサにあるメンバシップ・リストに加入プロセッサを追加することを通知する。具体的には、一例として、グループ・リーダは他のデーモンにマルチキャストを使用して更新を通知し、デーモンはその更新に対して肯定応答し、次にグループ・リーダがもう一度マルチキャストを使用して変更のコミットを送出する。（他の実施例では、この通知はアトミック・マルチキャストを使用して行うことができる。）一実施例では、メンバシップ・リストはグループへの加入順に維持されるため、加入プロセッサはリストの終わりに追加される。
【００３７】
本発明の原理によると、プロセッサ・グループのメンバであるプロセッサはグループを離脱することを要求することができる。挿入要求と同様に、離脱要求もたとえばメッセージを使用してグループ・リーダに転送される（ステップ９００「グループ・リーダに離脱要求を送る」（図１１））。その後、グループ・リーダは、たとえばそのメンバシップ・リストからそのプロセッサを削除し、プロセッサ・グループのすべてのメンバにそのそれぞれのメンバシップ・リストからもそのプロセッサを除去することを通知することによって、そのプロセッサをグループから除去する（ステップ９０２「グループ・リーダがプロセッサをグループから削除する」）。さらに、離脱するプロセッサがグループ・リーダである場合、前述のようにグループ・リーダ回復が行われる。
【００３８】
以上に加えて、プロセッサが障害を起こした場合、またはプロセッサ上で実行されているグループ・サービス・デーモンが障害を起こした場合、そのプロセッサはプロセッサ・グループから除去される。一実施例では、グループ・サービス・デーモンが障害を起こした場合、プロセッサが障害を起こしたとみなされる。一実施例では、障害を起こしたプロセッサは、プロセッサ障害を検出する、分散コンピューティング環境内で稼働しているサブシステムによって検出される。障害がある場合、一実施例では、そのプロセッサはグループ・リーダによって除去される。具体的には、グループ・リーダはそのメンバシップ・リストからそのプロセッサを削除し、前述のように、他のメンバ・プロセッサにそれを行うことを通知する。
【００３９】
グループ・サービスの内部層によって実施されるもう一つの機能として、マルチキャスト機能がある。本発明の原理によると、プロセッサ・グループのメンバはグループの他のメンバにメッセージをマルチキャストすることができる。このマルチキャストには、片方向マルチキャストのほか、肯定応答マルチキャストを含めることができる。
【００４０】
一実施例では、グループの１つのメンバからグループの他のメンバにメッセージをマルチキャストするために、メッセージ送信メンバがグループのグループ・リーダにメッセージを送り、グループ・リーダがそのメッセージを他のメンバにマルチキャストする。
【００４１】
本発明の原理によると、メッセージを送信する前に、グループ・リーダはメッセージに順序番号を割り当てる。割り当てられた順序番号は数字順に維持される。したがって、プロセッサ・グループのメンバ（すなわちグループ・サービス）が順序が乱れた順序番号を持つメッセージを受け取った場合、そのメンバはメッセージを逸したことがわかる。たとえば、処理ノードがメッセージ４３と４５を受け取った場合、そのノードはメッセージ４４を逸したことになる。
【００４２】
本発明の原理によると、プロセッサ・グループ内のすべてのノードが同じメッセージを受け取っているため、処理ノードは逸したメッセージをプロセッサ・グループ内のいずれかの処理ノードから取り出すことができる。しかし、一実施例では、情報を逸した処理ノードはそれをグループ・リーダに要求する。しかし、メッセージを逸したのがグループ・リーダである場合、グループ・リーダはそれをプロセッサ・グループ内の他のいずれかの処理ノードに要求することができる。これが可能なのは、プロセッサ・グループのすべての処理ノードにわたって重要データが回復可能な方式で複製されるためである。本発明によると、回復に必要なデータを持続記憶装置に記憶する必要はない。本発明の技法によって、回復データを記憶するための持続安定ハードウェア・ベース記憶装置が不要になる。
【００４３】
たとえば、グループ・リーダが障害を起こした場合、前述のように新しいグループ・リーダが選択される。グループ・リーダは、グループの処理ノードと通信することによってすべてのメッセージを確実に入手するようにする。一実施例では、グループ・リーダがすべてのメッセージを入手していることを確認すると、グループの他のすべての処理ノードもそれらのメッセージを確実に入手するようにする。したがって、本発明の技法によって、障害を起こした処理ノード、障害を起こしたプロセス、またはリンクを、安定記憶装置を必要とせずに回復することができる。
【００４４】
本発明の原理によると、各プロセッサ・グループはメッセージのそのグループ自体の順序づけられたセットを維持する。したがって、１つのプロセッサ・グループのメッセージが他のプロセッサ・グループのメッセージと重なったり衝突したりすることはない。プロセッサ・グループは、その順序づけられたメッセージと共に、互いに独立している。したがって、１つのプロセッサ・グループが４３、４４、および４５というメッセージの順序づけられたセットを受け取ることができると同時に、他のプロセッサ・グループは１、２、３というメッセージの独立して順序づけられたセットを受け取ることができる。これによって、ネットワークのすべてのプロセッサ間で全対全通信を行う必要がなくなる。
【００４５】
本発明の一実施例では、各処理ノードはメッセージを他のノードに供給する場合やグループ・リーダになる場合に備えて、受信するメッセージを一定時間保持する。メッセージはグループのすべてのプロセッサがそのメッセージを受信するまで保管される。メッセージをすべてのプロセッサが受信すると、そのメッセージは廃棄することができる。
【００４６】
一実施例では、すべてのノードがメッセージを受信したことを処理ノードに通知するのはグループ・リーダである。具体的には、一実施例では、処理ノードはグループ・リーダにメッセージを送るときにそのノードが最後に見たメッセージ（すなわち正しい順序の最後のメッセージ）の識別標識を組み込む。グループ・リーダはこの情報を収集し、処理ノードにメッセージを送るときに、メッセージにすべてのノードが見た最後のメッセージの順序番号を組み込む。その後、処理ノードは閲覧済みの標識が付けられたメッセージを削除することができる。
【００４７】
本発明の原理によると、マルチキャスト・ストリームを特定の時点で休止させてすべてのプロセッサ・グループ・メンバがすべてのメッセージを受信済みになるようにする。たとえば、一定期間マルチキャストがなかったときや、ある数のＮｏＡｃｋＲｅｑｕｉｒｅｄ（すなわち肯定応答不要）マルチキャストが送られた後に、ストリームを休止させる。一実施例では、マルチキャスト・ストリームを休止させる場合、グループ・リーダがＳＹＮＣマルチキャストを送出し、それに対してすべてのプロセッサ・グループ・メンバが肯定応答する。プロセッサ・グループ・メンバはそのようなメッセージを受け取ると、そのＳＹＮＣメッセージの順序番号に基づいて、すべてのメッセージを受け取っていること（または受け取る必要があること）を知る。メンバがいずれかのメッセージを逸した場合は、メッセージを入手してから肯定応答する。グループ・リーダはこのマルチキャストに対する肯定応答をすべて受け取ると、すべてのプロセッサ・グループ・メンバがすべてのメッセージを受け取ったことを知り、したがってマルチキャスト・ストリームが同期化され休止される。
【００４８】
本発明の他の実施例では、特定のＳＹＮＣマルチキャストは不要である。その代わり、以下の技法のいずれか１つを使用してマルチキャスト・ストリームを休止させることができる。一例として、肯定応答を必要とするマルチキャストをグループ・リーダからプロセッサに送ることができる。プロセッサは、肯定応答を必要とするマルチキャストを受け取ると、グループ・リーダに肯定応答を送る。肯定応答には、肯定応答するマルチキャストの順序番号が含まれている。プロセッサはこの順序番号を使用して、逸したメッセージがないかどうかを判断する。逸したメッセージがある場合、プロセッサはたとえば、グループ・リーダにその逸したメッセージを要求する。グループ・リーダがＡＣＫを必要とするメッセージをグループのすべてのプロセッサに送り、肯定応答をすべて受け取ると、グループ・リーダはストリームが休止されていることを把握する。非グループ・リーダ・プロセッサはグループ・リーダに依存してすべてのメッセージを遅滞なく確実に受信するので、マルチキャストを逸していることがないようにするためにグループ・リーダに対する定期的な肯定応答やＰＩＮＧを行う必要がない。
【００４９】
他の実施例として、ＮｏＡｃｋＲｅｑｕｉｒｅｄマルチキャストを使用する状況で、グループ・リーダはＮｏＡｃｋＲｅｑｕｉｒｅｄマルチキャストの１つをＡｃｋＲｅｑｕｉｒｅｄマルチキャストに変えることができ、したがってそれを前述のようにｓｙｎｃとして使用する。したがって、明示的なＳＹＮＣメッセージは不要である。
【００５０】
上記に加えて、他の実施例では、非グループ・リーダ・プロセッサがグループ・リーダのアクションを先取りすることができ、それによってＮｏＡｃｋＲｅｑｕｉｒｅｄメッセージの数が窓サイズに達した場合（すなわち、一実施例ではたとえば５など所定の数に達した場合）、または最大遊休時間に達した場合、非グループ・リーダ・プロセッサはグループ・リーダにＡＣＫを送ることができる。ＡＣＫによって、各プロセッサが受信した最高順序番号のマルチキャストがグループ・リーダに供給される。すべての非グループ・リーダ・プロセッサがこれを行った場合、グループ・リーダはＮｏＡｃｋＲｅｑｕｉｒｅｄマルチキャストをＡｃｋＲｅｑｕｉｒｅｄマルチキャストに変える必要はない。したがって、グループはすべての肯定応答を待つことによって停滞させられることがない。
【００５１】
本発明の上記の機能のサポートは、グループ・サービス（すなわちプロセス）のユーザには透過である。この機能を実施するためのプロセスによる明示的アクションは不要である。さらに、このサポートはグループ・サービスの内部層でも外部層でも使用可能である。
【００５２】
図３に戻って参照すると、外部層３０４は、ユーザ（すなわちクライアント・プロセス）にとってわかりやすいアプリケーション・プログラミング・インタフェースのより豊富な機構のセットを実現する。
【００５３】
一実施例では、これらの機構にはアトミック・マルチキャスト、２フェーズ・コミット、バリヤ同期、プロセス・グループ・メンバシップ、プロセッサ・グループ・メンバシップ、およびプロセス・グループ状態値が含まれ、それぞれについては以下で説明する。これらの機構およびその他の機構は、本発明の原理に従って、アプリケーション・プログラミング・インタフェースによって、わかりやすい単一の統一フレームワークに統一される。具体的には、（他の機構に加えて）通信機構と同期機構が単一のプロトコルに統一されている。
【００５４】
本発明の原理によると、この単一の統一フレームワークは、本明細書で説明するようにプロセス・グループのメンバに提供される。プロセス・グループは、分散コンピューティング環境の１つまたは複数の処理ノード上で実行される１つまたは複数の関連性のあるプロセスを含む。たとえば、図１２を参照すると、プロセス・グループＸ（１０００）は、プロセッサ１上で実行されるプロセスＸとプロセッサ２上で実行される２つのプロセスＸを含む。プロセスが特定のプロセス・グループのメンバになる方式について、以下で詳述する。
【００５５】
プロセス・グループは、提供者と加入者を含む少なくとも２つのタイプのメンバを有することができる。提供者は投票権などの特定の特権を持つメンバ・プロセスであり、加入者にはそのような特権はない。加入者は単にプロセス・グループの進行状況を監視することができるに過ぎず、グループに関与することはできない。たとえば、加入者はグループのメンバシップとグループの状態値を監視することができるが、投票することはできない。他の実施例では、異なる権利を持つ他のタイプのメンバを設けることができる。
【００５６】
本発明の原理によると、以下で図１３を参照しながら説明するようにアプリケーション・プログラミング・インタフェースを実現する。
【００５７】
図１３を参照すると、一実施例では、最初にプロセス・グループの提供者がグループにプロトコルを提案する（この実施例では加入者はプロトコルを提案することはできない）（ステップ１１００「プロセス・グループのメンバがグループにプロトコルを提案する」）。具体的には、一実施例ではプロトコルを提案するＡＰＩ呼出しを行う。一実施例では、プロトコルはプロセスによって、そのプロセスを実行するプロセッサ上のグループ・サービス・デーモンの外部層に渡される。次に、そのグループ・サービス・デーモンはそのプロトコルをメッセージを使用してグループのグループ・リーダに渡す。グループ・リーダはマルチキャストを使用して、関連性のあるプロセッサ・グループのすべてのプロセッサにそのプロトコルを通知する。（デーモンの内部層がこのマルチキャストを管理している。）次にそれらのプロセッサが外部層を介してプロセス・グループの適切なメンバに、提案されたプロトコルを通知する（ステップ１１０２「プロセス・グループ・メンバにプロトコルを通知する」）。
【００５８】
同時に複数の提供者がプロトコルを提案した場合、稼働させるプロトコルをグループ・リーダが以下のようにして選択する。一実施例では、プロトコルは障害のためのプロトコルが最初、加入プロトコルが２番目、他のすべてのプロトコル（たとえば後述する離脱、追放、更新状態値の要求およびグループ・メッセージの供給）が先着順というように優先順位がつけられる。したがって、障害のためにメンバを除去する要求が、加入要求および離脱要求と同時に提案された場合、除去要求が先に選択される。次に加入要求が選択され、その後で離脱要求が選択される。
【００５９】
障害による除去要求が複数ある場合、それらの要求はすべて加入要求より先に選択される。グループ・リーダは除去要求をグループ・リーダが見た順に選択する（後述するバッチ処理が可能な場合を除く）。同様に、複数の加入要求がある場合は、それらの要求は同様にして他のどの要求よりも先に選択される。
【００６０】
一実施例では、その他の複数の要求がある場合、グループ・リーダが最初に受け取った要求が選択され、その他の要求は廃棄される。グループ・リーダはそれらの廃棄された要求の提供者に要求が廃棄されたことを通知し、その後で、提供者は希望する場合にはその要求を再提出することができる。本発明の他の実施例では、これらの他の要求は受信順に待ち行列化することができ、廃棄せずに選択することができる。
【００６１】
プロトコルを選択した後、そのプロトコルについて投票を行うかどうかを決定する（照会１１０４「投票するか？」）。一実施例では、プロトコルを提案するプロセスは最初の提案時に、投票を行うべきかどうかを指示する。投票が指示されていない場合、プロトコルは単にアトミック・マルチキャストに過ぎず、そのプロトコルは完了する（ステップ１１０６「終了」）。
【００６２】
投票を行う場合は、プロセス・グループの各提供者がプロトコルについて投票する（ステップ１１０８「投票権のあるプロセス・グループ・メンバが投票する」）。具体的には、本発明の原理によると、投票によって各提供者はグループを満足させるのに必要なローカル・アクションを行うことができ、グループにそれらのアクションの結果を通知することができる。これは、先に進む前にすべての提供者が特定の地点に達しているようにすることによって、バリヤ同期プリミティブとして機能する。
【００６３】
本発明の一実施例では、各提供者は投票値を投ずることによって投票し、投票値にはたとえば以下のものが含まれる。
（ａ）ＡＰＰＲＯＶＥ（承認）は、提供者が、すべての提供者がこのバリヤに達したらプロトコルを完了させ、提案されたすべての変更を受け入れたいということを示す。
（ｂ）ＣＯＮＴＩＮＵＥ（継続）は、提供者が、もう１回投票ステップによってプロトコルを継続し、提案された変更を保留にしておきたいとうことを示す。（ｃ）ＲＥＪＥＣＴ（拒否）は、提供者が、すべての提供者がこのバリヤに達したらこのプロトコルを終了させ、拒否することができる提案された変更を拒否したいということを示す。
【００６４】
本発明の原理によると、プロセス・グループの各提供者はその投票をプロセスと同じプロセッサ上で実行されているグループ・サービス・デーモンに転送する。グループ・サービス・デーモンは受け取った投票値を、そのプロセス・グループに関連づけられたメタグループのグループ・リーダに転送する。たとえば、プロセス・グループＸの投票値はプロセッサ・グループＸのグループ・リーダに転送される。グループ・リーダは投票値に基づいてそのプロトコルをどのように進めるかを決定する。次にグループ・リーダは投票の結果を該当するプロセッサ・グループの各プロセッサ（すなわちそれらのプロセッサ上のグループ・サービス・デーモン）にマルチキャストし、グループ・サービス・デーモンが提供者にその結果値を通知する。たとえば、グループ・リーダはプロセッサ・グループＸのグループ・サービス・デーモンに通知し、そのグループ・サービス・デーモンが結果をプロセス・グループＸの提供者に送る。
【００６５】
提供者の１つがＣＯＮＴＩＮＵＥを投票し、提供者のいずれもＲＥＪＥＣＴを投票しなかった場合（照会１１１０「投票を続けるか？」）、プロトコルはもう１つの投票ステップに進む（ステップ１１０８）。すなわち提供者は動的な数の同期フェーズを使用してバリヤ同期を行う。具体的には、本発明の原理によると、プロトコルが持つことができる投票ステップ（または同期フェーズまたは同期点）の数は動的である。投票メンバが希望する任意のステップ数とすることができる。プロトコルは、いずかの提供者がプロトコルの継続を望む限り続行することができる。したがって、一実施例では、投票によって投票ステップ数が動的に制御される。しかし、他の実施例では、動的投票ステップ数はプロトコルの開始中に設定することができる。その場合でも、プロトコルが初期設定されるたびに変更可能であるため動的である。
【００６６】
提供者がもう１つ投票ステップを続けないことに投票した場合、プロトコルは２フェーズ・コミットである。投票完了後（２フェーズ投票または多フェーズ投票の場合）、投票結果がメンバに送られる。具体的には、プロセス・グループのいずれか１つの提供者がＲＥＪＥＣＴを投票した場合、プロトコルは終了し、提案された変更は拒否される。各提供者に対してマルチキャストを使用して、プロトコルが拒否されたことが通知される（ステップ１１１２「メンバにプロトコルの完了を通知する」）。一方、すべての提供者がＡＰＰＲＯＶＥに投票した場合、プロトコルは完了して提案されたすべての変更が受け入れられる。提供者にはマルチキャストを使用して受け入れられたプロトコルが通知される（ステップ１１１２「メンバにプロトコルの完了を通知する」）。
【００６７】
本発明の原理によると、上述のプロトコルはプロセス・グループ・メンバシップおよびプロセス・グループ状態値とも統合される。具体的には、本発明の機構を使用して、プロセス・グループのメンバシップ変更の管理と監視を行う。グループのメンバシップに加えられる変更は、前述のプロトコルを介して提案される。さらに、本発明の機構はグループ状態値の変更も媒介し、少なくとも１つのプロセス・グループ・メンバが残っている限り、グループ値の整合性と信頼性が維持されるように保証する。
【００６８】
プロセス・グループのグループ状態値はプロセス・グループの同期された黒板の役割を果たす。一実施例では、グループ状態値は提供者が制御するアプリケーション固有の値である。グループ状態値は、グループ・サービスによって各プロセスのために維持されるグループ状態データの一部である。グループ状態データには、グループ状態値のほか、そのグループの提供者メンバシップ・リストが含まれる。各提供者は、提供者識別子によって識別され、このリストは、グループ・サービスによって、最も古い提供者（グループに加わっている最初の提供者）がリストの先頭になり、最も若い提供者が最後になるように順序づけられる。
【００６９】
グループ状態値の変更は、グループ・メンバ（すなわち提供者）によって前述のプロトコルを介して提案される。一実施例では、グループ状態値の内容はグループ・サービスによって解釈されない。グループ状態値の意味は、グループ・メンバによって付与される。本発明の機構によって、すべてのプロセス・グループ・メンバが、グループ状態値に加えられる同じ順序の変更を見るように保証され、すべてのプロセス・グループ・メンバがその更新を見るように保証される。
【００７０】
したがって、前述のように、本発明のアプリケーション・プログラミング・インタフェースは、たとえばアトミック・マルチキャスト、２フェーズ・コミット、バリヤ同期、グループ・メンバシップ、およびグループ状態値など複数の機構を含む単一の統一されたプロトコルを提供する。グループ・メンバシップとグループ状態値のためのプロトコルの使い方について以下に詳述する。
【００７１】
前述の投票機構を本発明の原理により使用して、プロセス・グループのメンバシップの変更を提案する。たとえば、プロセスがプロセス・グループＸなどの特定のプロセス・グループに加入したい場合、そのプロセスは加入呼出しを発行する（ステップ１２００「加入要求を出す」（図１４））。一実施例では、この呼出しはメッセージとしてローカル通信経路（たとえばＵＮＩＸドメイン・ソケット）で要求側プロセスを実行しているプロセッサ上のグループ・サービス・デーモンに送られる。グループ・サービス・デーモンはネーム・サーバに要求側プロセスが加入したいプロセス・グループのグループ・リーダの名前を問い合わせるメッセージをネーム・サーバに送る（ステップ１２０２「グループ・リーダを判断する」）。
【００７２】
この要求がその特定のプロセス・グループへの最初の加入要求である場合、ネーム・サーバはグループ・サービス・デーモンにそれがグループ・リーダであることを通知する（照会１２０４「最初の加入要求か？」）。したがって、前述のようにプロセッサはプロセッサ・グループを作成し、プロセスをプロセス・グループに加える（ステップ１２１０「プロセスを追加する」）。具体的には、プロセスはそのプロセス・グループのメンバシップ・リストに追加される。このメンバシップ・リストはグループ・サービスによってたとえば順序づけられたリストとして維持される。一実施例では、リストは加入順に順序づけられる。最初に加入したプロセスがリストの最初になり、以下同様である。
【００７３】
本発明の原理によると、プロセス・グループに最初に加入するプロセスによってそのグループの属性のセットが識別される。これらの属性はプロセスによって送られる加入呼出しに引数として組み込まれる。これらの属性には、たとえば、固有識別子であるグループ名や、グループが様々なプロトコルをどのように管理したいかをグループ・サービスに対して定義する事前指定情報が含まれる。たとえば、この属性にはプロセス・グループが、後述するバッチ要求を受け入れるかどうかを示す標識を含めることができる。さらに、他の実施例では、属性には、たとえば各提供者におけるプログラミングのソフトウェア・レベルを表すクライアントのバージョン番号を含めることができる。これによって、すべてのグループ・メンバが同じレベルになるように保証することができる。上記の属性は単に一例に過ぎない。特許請求の発明の精神から逸脱することなく、追加の属性または異なる属性を含めることができる。
【００７４】
照会１２０４「最初の加入要求か？」に戻って、これが最初の加入要求ではない場合、その加入要求はネーム・サーバによって指定されたグループ・リーダにメッセージを介して送られる（ステップ１２１４「グループ・リーダに加入要求を送る」）。グループ・リーダは事前スクリーニング・テストを行う（ステップ１２１６「事前スクリーン」）。具体的には、グループ・リーダは要求側プロセスによって指定された属性がグループの最初のプロセスによって設定された属性と同じかどうかを判断する。同じでない場合、加入要求は拒否される。
【００７５】
しかし、事前スクリーニング・テストに合格した場合は、プロセス・グループの提供者に対してたとえばグループ・リーダからのマルチキャストを介してその要求が通知され、提供者はそのプロセスをグループに加えることを許可するかどうかについて投票する（ステップ１２２０「投票する」）。投票は前述のようにして行われる。提供者は、そのプロトコルを継続することを票決してこの加入について再び投票するか、または加入を拒否または承認することを票決することができる。提供者の１つがＲＥＪＥＣＴを投票した場合、その加入は終了させられ、プロセスはグループに加えられない（照会１２２２「成功か？」）。しかし、すべての提供者がＡＰＰＲＯＶＥに投票した場合、プロセスはグループに加えられる（ステップ１２２４「プロセスを追加する」）。具体的には、プロセスはグループのメンバシップ・リストの最後に追加される。プロトコルが完了すると、グループのメンバにその結果が通知される。具体的には、一実施例ではプロセスが追加され場合はすべてのメンバ（提供者と加入者を含む）に通知されるが、プロトコルが拒否された場合は提供者のみに通知される。他の実施例では、適切とみなされる場合には他のタイプのメンバにも通知することができる。
【００７６】
前述のように提供者は加入要求を使用してプロセス・グループに加入する。提供者には投票権などの特定の利便が与えられる。プロセスもプロセス・グループに加入することができるが、（加入呼出しとは異なる）ＡＰＩ加入呼出しを発行することによって加入する。加入者は特定のプロセス・グループを監視することができるが、グループに関与することはできない。
【００７７】
加入呼出しが発行されると、そのプロセッサ上のグループ・サービスに転送され、そのグループ・サービス・デーモンがその呼出しを追跡する。グループ・サービス・デーモンがそのプロセッサ・グループに属していない場合は、前述のようにそのグループに挿入されることになる。一実施例では、この加入者に関する投票はなく、提供者および他の加入者を含むグループの他のメンバはその加入者を認識しない。加入者はまだ作成されていないプロセス・グループに加入することはできない。
【００７８】
グループ・メンバシップは、グループを離脱したりグループから除去されるグループ・メンバによって変更されることもある。一実施例では、グループを離脱したいグループ・メンバは前述のようにしてグループ・リーダに離脱要求を送る（ステップ１３００「離脱要求を出す」（図１５））。グループ・リーダは提供者にマルチキャストを送り、提案された変更について投票するように提供者に要求する（ステップ１３０２「投票する」）。この投票は前述のようにして行われ、すべての提供者がＡＰＰＲＯＶＥに投票した場合（照会１３０４）、そのプロセス・グループのメンバシップ・リストからプロセスが除去され（ステップ１３０６「プロセスを除去する」）、すべてのグループ・メンバにその変更が通知される。しかし、提供者の１つがＲＥＪＥＣＴを投票した場合、プロセスはそのプロセス・グループの一員として留まり、プロトコルが終了し、提供者にプロトコルの拒否が通知される。提供者のいずれもＲＥＪＥＣＴを投票せず、提供者のいずれか１つがＣＯＮＴＩＮＵＥを投票した場合は、当然、そのプロトコルの投票がもう１回継続される。
【００７９】
グループのメンバは、グループの他のプロセスによって提案された追放プロトコルの承認によってグループから追放された場合、またはそのグループ・メンバが障害を起こしたりそのメンバを実行しているプロセッサが障害を起こした場合、グループを非自発的に離脱することがある。追放の行われ方は、メンバがグループの離脱を要求する場合について前述したのと同じであるが、要求が離脱を希望するプロセスによって出されるのではなく、グループから他のプロセスを除去したいプロセスによって要求が行われる点が異なる。
【００８０】
同様に、一実施例ではプロセスが障害を起こした場合またはプロセスを実行しているプロセッサが障害を起こした場合、そのプロセスを除去する技法は、離脱を要求するプロセスを除去するために使用する技法と同様である。ただし、そのプロセスが離脱を要求するのではなく、以下で説明するようにグループ・サービスによって要求が出される。
【００８１】
プロセスが障害を起こした場合、一実施例では障害を起こしたプロセスのプロセッサ上で稼働しているグループ・サービス・デーモンによってその障害がグループ・リーダに通知される。グループ・サービス・デーモンは、プロセスに関連づけられた（当業者には周知の）ストリーム・ソケットが障害を起こしたことを検出すると、プロセスが障害を起こしたと判断する。そうすると、グループ・リーダは除去を開始する。
【００８２】
プロセッサ障害の場合、グループ・リーダはその障害を検出し、除去要求を出す。障害を起こしたのがグループ・リーダである場合、要求が出される前に、本明細書に記載の通りグループ・リーダ回復が行われる。一実施例では、グループ・リーダには、ネットワークの処理ノード全体にわたって分散されたサブシステムによってプロセッサ障害が通知される。このサブシステムは、すべての処理ノードに信号を送出し、その信号に特定のノードが肯定応答しない場合、そのノードはダウンした（または障害を起こした）とみさなれる。次にこの情報がグループ・サービスにブロードキャストされる。
【００８３】
前述のようにプロセスがグループに加わりたい場合、またはグループ・メンバがグループを離脱したいかまたはグループから除去される場合、グループ・リーダは各グループ提供者に提案された変更を通知し、それによって提供者はその変更について投票することができるようになる。本発明の原理によると、これらの提案されたメンバシップ変更は、グループ提供者に１つずつ（すなわち、１つのプロトコルについて１つの提案グループ・メンバシップ変更）またはバッチ（すなわち、１つのプロトコルについて複数の提案グループ・メンバシップ変更）で提示する。バッチ要求の場合、グループ・リーダは一例として、所定の時間のあいだ要求を収集してから、グループ提供者に１つまたは複数のバッチ要求を提示する。具体的には、その時間中に収集されたすべての加入要求を含む１つのバッチ要求が送られ、収集されたすべての離脱要求または除去要求を含む別のバッチ要求が送られる。一実施例では、１つのバッチ要求にはすべて加入またはすべて離脱（および除去）のみを含めることができ、その両方を組み合わせて含めることはできない。これは１つの例にすぎない。他の実施例では、両方のタイプの要求を組み合わせることができる。
【００８４】
バッチ要求がグループ提供者に転送されると、グループ提供者はそのバッチ要求全体をひとまとまりとして投票する。したがって、バッチ全体が受け入れられるか、継続されるか、または拒否される。
【００８５】
本発明の原理によると、各プロセス・グループは要求をバッチ処理することを許可するかどうかを決めることができる。さらに、各プロセス・グループはあるタイプの要求をバッチ処理することができるようにし、他のタイプの要求をできないようにするかどうかを決定することができる。たとえば、ネットワークで実行されているプロセス・グループがいくつかあるとする。プロセス・グループＷはすべてのタイプの要求についてバッチ要求を受け取ると決定し、プロセス・グループＸはそれとは独立してすべての要求を逐次に受け取ると決定することができる。さらに、プロセス・グループＹは加入要求のみのバッチ要求を許し、プロセス・グループＺは離脱または除去要求のバッチ要求のみを許すことができる。したがって、本発明の機構は要求の提示の仕方と投票の仕方に柔軟性がある。
【００８６】
このシステムは柔軟性があるが、グループ・メンバシップの整合性と信頼性を保証するために本発明の一実施例で定めたいくつかの規則がある。これらの規則には一例として以下のものが含まれる。
１．どのグループ・メンバもそのグループに加わる以前に、障害を起こすことやグループを離脱することが明らかにされてははならない。
２．どのグループ・メンバもその初期障害が処理済みになる前に、再びグループに加入することが明らかにされてはならない。
３．グループが加入要求を持っており、しかも障害状態の定着メンバを持っている場合、障害を起こしたすべてのメンバを（１つまたは複数の障害プロトコルを使用して）処理してからでなければどの加入要求も満たすことができない。
４．加入を要求している提供者を含むすべての非障害グループ提供者が同じ順序のプロトコルとメンバシップ・リストを見る。
【００８７】
以上、本発明の投票プロトコルをどのように使用してグループ・メンバシップを管理するかを詳述した。しかし、本発明の原理によると投票プロトコルはグループ状態値の提案にも使用することができる。具体的には、投票フェーズ中に、提供者またはプロセス・グループは、投票値の提供に加えてグループの状態値の変更を提案することができる。これによって、グループ提供者がグループ情報を他のグループ・メンバに信頼性と整合性をもたせて反映させることができる。一実施例では、グループ状態値（およびメッセージ、更新された投票値など本明細書に記載されているその他の情報）が、様々な引数の提示を可能にする投票インタフェースを介して投票値と共に提供される。
【００８８】
たとえば、メンバがグループに加わったりグループから離脱したりする場合、グループは前述のように複数ステップ・プロトコルを使用して駆動される。各投票ステップ中に、グループ・メンバはローカル・アクションを行って新しいメンバのための準備をしたり、障害を起こしたメンバの損失を回復したりする。これらのローカル・アクションの結果に基づいて、たとえば、１つまたは複数の提供者がグループ状態値の修正を決定することができる。一実施例では、グループ状態値は「アクティブ」になって、処理グループがサービス要求を受入れ可能であることを示したり、「非アクティブ」になって、プロセス・グループがたとえばそのグループが十分なメンバを持っていないために停止していることを示したり、「中断」になって、プロセス・グループは要求を受け入れるが、一時的に要求を処理していないことを示したりすることができる。
【００８９】
グループ・サービスは、グループ状態値の更新が調整されるように保証して、グループ提供者が同じ整合性ある値を見られるようにする。プロトコルがＡＰＰＲＯＶＥＤの場合、最新の更新済み提案グループ状態値が新しいグループ状態値である。プロトコルがＲＥＪＥＣＴＥＤの場合、グループの状態値は拒否されたプロトコルが実行を開始する前の状態のままである。
【００９０】
本発明の原理によると、投票プロトコルを使用してグループ・メンバにメッセージをマルチキャストすることができる。たとえば、投票値を送るほかに、提供者はプロセス・グループの他のすべてのメンバに転送するメッセージを組み込むことができる。グループ状態値とは異なり、このメッセージは持続性がない。グループ・メンバに示された後は、グループ・サービスはそのメッセージを追跡しない。しかし、グループ・サービスはすべての非障害グループ提供者に配布されるように保証する。
【００９１】
メッセージはグループ提供者が、たとえばプロトコル中に投票内の他の応答では伝えることができない重要な情報を転送するために使用することができる。たとえば、提供者の投票値に反映することができない情報を提供したり、持続性を持たせる必要がない情報を提供するために使用することができる。一実施例では、メッセージによってグループ・メンバに特定の機能が実行されることを通知することができる。
【００９２】
本発明の一実施例によると、プロセス・グループの各提供者はプロトコルの投票フェーズで投票することが求められる。すべての提供者が投票するまで、プロトコルは完了しないままである。したがって、１つまたは複数の提供者が投票を送っていないという状況を処理するために、本発明の原理によると、投票プロトコルに１つの機構を設ける。具体的には、この投票機構は以下で詳述する省略時の投票値を組み込む。
【００９３】
たとえば、本明細書に記載のように、プロトコルの実行中に提供者に障害が発生した場合や、提供者が実行しているプロセッサが障害を起こした場合や、提供者が無応答になった場合に省略時の投票値を使用する。省略時の投票値によってプロトコルとプロセス・グループの処理の進行をはかどらせることができる。プロセス・グループは、グループがたとえばその属性によって最初に形成されるときにそのグループの省略時の投票値を初期設定する。一実施例では、省略時の投票地はＡＰＰＲＯＶＥまたはＲＥＪＥＣＴとすることができる。各投票フェーズ中に、グループ内の変化する条件を反映するように省略時の投票値を変更することができる。
【００９４】
プロトコル中にプロセスに障害が発生した状況では、前述のようにグループ・サービスがそれを判断し、したがってプロトコルのどの投票フェーズであっても、グループ・リーダが、障害を起こしたプロセスのためにグループの現行省略時投票値を受け渡しすることになる。同様に、メンバ提供者を実行しているプロセッサが障害を起こしたとグループ・サービスが判断した場合も、グループ・リーダは再度、省略時投票値を受け渡しする。
【００９５】
しかし、プロセッサまたはプロセスが使用可能であるが無応答の場合も、省略時の投票値を使用することができる。一実施例では、プロセスは、当該プロトコルのためにプロセス・グループによって設定された制限時間内に投票に応答しない場合に無応答とみなされる。（各プロセス・グループの各プロトコルがそれ独自の制限時間を持つことができる。）プロセスが無応答の場合、プロセス・グループに割り当てられた省略時の投票値がグループ・リーダによってその特定のプロセスのために使用される。一実施例では、制限時間を設けないことも可能である。そのような状況では、グループ・サービスは提供者が最終的に応答するかまたは提供者が障害を起こすまで待つことになる。
【００９６】
一実施例では、省略時の投票値を使用する場合、提供者にそれが通知される。
【００９７】
本発明の原理によると、提供者はプロトコル内のどの１つまたは複数の投票ステップでも省略時の投票値を動的に更新することができる。これによって、プロトコルの進行とともに障害を処理する柔軟性が与えられる。提案された省略時値はプロセスの投票値と共に受け渡しされる。新しい省略時投票値は、後の投票ステップで別の省略時投票値が提案されない限り、プロトコルの残りの期間中有効であり続ける。特定の投票ステップで複数の省略時投票値が提案された場合、一実施例では、グループ・サービス（すなわちグループ・リーダ）は最初に応答したプロセスによって受け渡しされた値を選択する。プロトコルが完了すると、プロセス・グループの省略時投票値はそのグループのために最初に設定された値に戻る。
【００９８】
省略時投票値は他のあらゆる投票値と同じように扱われる。しかし、一実施例では省略時投票値は、たとえばメッセージ、グループ状態値、新たに提案された更新省略時投票値など、投票のための他の情報を含むことができない。
【００９９】
図１３を参照しながら前述したように、前記のすべての提案プロトコルは１フェーズ・プロトコルとして提案することができる。１フェーズ・プロトコルでは、プロトコルが１つのマルチキャストで提案され、受け入れられる。したがって、票決をとる必要がない。
【０１００】
以上、可用性の高いマルチコンピュータ・アプリケーションを確実に実現する機構について詳述した。一例として、本発明の機構を使用してフォールトトレラントの高可用性システムを実現することができる。本発明の機構は、システム内で実行されているプロセス・グループの状態に加えられる変更の調整、管理、および監視を行う汎用機能を提供するので有利である。
【０１０１】
本発明の原理によると、プロセッサ・グループ内のおよびプロセス・グループ内のメンバシップを動的に更新することができる。いずれの場合も、プロセッサまたはプロセスをグループへの追加またはグループからの除去を要求することができる。本発明の機構によって、これらの変更が整合性と信頼性のある仕方で行われるようになる。
【０１０２】
さらに、本発明の原理によると、メッセージを１つまたは複数の特定のプロセッサ・グループに送ることができるようにし、すべてのプロセッサ・グループにメッセージを送らなくても済むようにする機構が提供される。各プロセッサ・グループは、それ自体のメッセージのセットの監視と管理を行うことができ、１つまたは複数のメッセージを逸していないかどうかを判断することができる。メッセージを逸している場合、そのメッセージはグループの他のメンバから取り出すことができる。これらのメッセージのために安定記憶装置を維持する必要がない。各メンバがこれらのメッセージを持っており、したがって逸したメッセージを他のメンバに供給することができる。これは、ハードウェアの費用が低減されるので有利である。
【０１０３】
さらに、本発明の原理によると、障害を起こしたグループ・リーダから回復する機構が提供される。これらの機構によって、新しいグループ・リーダが容易かつ効率的に選択されるようになる。
【０１０４】
また、本発明の機構は、プロセスのためにいくつかのプロトコルを単一の統合フレームワークに統一するアプリケーション・プログラミング・インタフェースも提供する。一例として、この統合アプリケーション・プログラミング・インタフェースは、プロセス・グループのメンバ間で通信する機能と、プロセス・グループのプロセスを同期させる機能を備える。さらに、この同じインタフェースは、プロセス・グループのメンバシップ変更とグループ状態値の変更を扱う機能も備える。
【０１０５】
このアプリケーション・プログラミング・インタフェースは、グループ・サービスがプロセスの応答性を監視することができるようにする機構も備える。これは、コンピュータ・ネットワーク通信で使用されるＰＩＮＧ機構と同様にして行うことができる。
【０１０６】
以上に加えて、本発明の機構は動的バリヤ同期技法を提供する。本発明の原理によると、任意の１つのプロトコルに含まれる同期フェーズの数は可変であり、メンバがそのプロトコルに投票することによって決定することができる。
【０１０７】
本発明の機構は、本発明の機構を提供し支援するコンピュータ可読プログラム・コード手段が含まれたコンピュータ使用可能媒体を含む、１つまたは複数のコンピュータ・プログラム製品に組み込むことができる。これらの製品はコンピュータ・システムの一部として組み込むことも別途に販売することもできる。
【０１０８】
本明細書に図示する流れ図は例に過ぎない。本発明の精神から逸脱することなく、これらの図または図に図示されているステップには多くの様々な変形が考えられる。たとえば、それらのステップを異なる順序で行ったり、ステップを追加、削除、または修正したりすることができる。これらの変形はすべて特許請求の範囲の発明の一部とみなされる。
【０１０９】
本明細書では好ましい実施例を図示し、詳述したが、当業者には、本発明の精神から逸脱することなく様々な修正、追加、代替策などを行うことができることが明であろう。したがって、それらは特許請求の範囲に記載の本発明の範囲内に入るものとみなされる。
【０１１０】
まとめとして、本発明の構成に関して以下の事項を開示する。
【０１１１】
（１）分散コンピューティング環境におけるプロセッサ・グループのグループ・リーダに発生した障害から回復するシステムであって、
前記プロセッサ・グループのプロセッサの加入順に順序づけられたメンバシップ・リストと、
前記プロセッサ・グループの新しいグループ・リーダとして前記メンバシップ・リストから次のプロセッサを選択する手段とを含むシステム。
（２）前記選択する手段が、前記メンバシップ・リストから次のアクティブ・プロセッサを選択する手段を含むことを特徴とする、上記（１）に記載のシステム。
（３）前記プロセッサ・グループに前記新しいグループ・リーダを通知する手段をさらに含む、上記（１）に記載のシステム。
（４）前記メンバシップ・リストから前記新しいグループ・リーダを選択するようにプログラム可能なネーム・サーバをさらに含む、上記（１）に記載のシステム。
（５）前記メンバシップ・リストが前記プロセッサ・グループの各プロセッサにあることを特徴とする、上記（１）に記載のシステム。
（６）前記選択する手段が、前記プロセッサ・グループによって前記プロセッサにある前記メンバシップ・リストから前記新しいグループ・リーダを選択する手段を含み、ネーム・サーバに前記新しいグループ・リーダを通知する手段をさらに含むことを特徴とする、上記（５）に記載のシステム。
（７）前記ネーム・サーバによって前記プロセッサ・グループに前記新しいグループ・リーダを通知する手段をさらに含む、上記（６）に記載のシステム。
（８）前記新しいグループ・リーダによって、前記新しいグループ・リーダが前記新しいグループ・リーダとして選択される前に、前記プロセッサ・グループに以前に送られたメッセージを受け取る手段をさらに含む、上記（１）に記載のシステム。
（９）前記新しいグループ・リーダによって、前記プロセッサ・グループのプロセッサが逸したメッセージを提供する手段をさらに含む、上記（８）に記載のシステム。
（１０）前記新しいグループ・リーダに要求を送る手段をさらに含む、上記（１）に記載のシステム。
【図面の簡単な説明】
【図１】本発明の原理を組み込んだ分散コンピューティング環境の一例を示す図である。
【図２】本発明の原理による、図１の分散コンピューティング環境のいくつかの処理ノードの拡大図の一例を示す図である。
【図３】本発明の原理による、「グループ・サービス」機能の構成要素の一例を示す図である。
【図４】本発明の原理による、プロセッサ・グループの一例を示す図である。
【図５】本発明の原理による、図４のプロセッサ・グループの障害を起こしたグループ・リーダの回復に関連する論理の一例を示す図である。
【図６】本発明の原理による、図４のプロセッサ・グループの障害を起こしたグループ・リーダの回復に関連する論理の他の一例を示す図である。
【図７】本発明の原理による、グループ・リーダの一例を示す図である。
【図８】本発明の原理による、現行グループ・リーダが障害を起こした場合に新しいグループ・リーダを選択する技法を示す図である。
【図９】本発明の原理による、グループ・リーダから情報を受け取るネーム・サーバの一例を示す図である。
【図１０】本発明の原理による、プロセッサ・グループへのプロセッサの追加に関連する論理の一例を示す図である。
【図１１】本発明の原理による、プロセッサ・グループからのプロセッサの離脱に関連する論理の一例を示す図である。
【図１２】本発明の原理による、プロセス・グループの一実施例を示す図である。
【図１３】本発明の原理による、プロセス・グループのプロトコルの処理に関連する論理の一例を示す図である。
【図１４】本発明の原理による、プロセス・グループへの加入を要求するプロセスに関連する論理の一例を示す図である。
【図１５】本発明の原理による、グループからの離脱を要求するプロセス・グループのメンバに関連する論理の一例を示す図である。
【符号の説明】
１００  分散コンピューティング環境
１０２  フレーム
１０４  ＬＡＮゲート
１０６  処理ノード
２００  グループ・サービス・デーモン
２０２  プロセス
２０４  アプリケーション・プログラミング・インタフェース
３０２  内部層
３０４  外部層
４００  プロセッサ・グループ
７００  ネーム・サーバ
【図１】
0003589378.tif 000002
【図２】
0003589378.tif 000003
【図３】
0003589378.tif 000004
【図４】
0003589378.tif 000005
【図５】
0003589378.tif 000006
【図６】
0003589378.tif 000007
【図７】
0003589378.tif 000008
【図８】
0003589378.tif 000009
【図９】
0003589378.tif 000010
【図１０】
0003589378.tif 000011
【図１１】
0003589378.tif 000012
【図１２】
0003589378.tif 000013
【図１３】
0003589378.tif 000014
【図１４】
0003589378.tif 000015
【図１５】
0003589378.tif 000016