(57)【要約】  本発明は、複数の協働するコンピュータ（ホストと呼ばれる）のクラスタの中に共通のメンバーシップを確立し維持するためのソフトウェアベース通信アーキテクチャおよび関連ソフトウェア方法を備える。本発明は、もっとも近いネイバー、および、一次または多次元のアレイに論理的に組織されるクラスタコンピュータの間の重なり合いハートビート接続の使用を組み込む。ハートビート接続のこの配列は、２つの主要な利点を有する。第１に、ホストはメンバーシップを分割せずに別のホストの故障を即座に検出しそれからリカバリすることができるため、ホスト故障後にクラスタメンバーシップを高度に利用可能に保つ。第２に、特定のハートビート接続を維持するためのホスト当たりの計算およびメッセージ通過オーバーヘッドは固定され且つ基礎となる物理的なネットワークは拡張することができるため、クラスタメンバーシップが大きな数（たとえば、何百）のコンピュータへ拡張することを可能にする。このメンバーシップアーキテクチャは、負荷のバランスをとる目的で隣接しているホストによって作業負荷への変化がクラスタ風に作られ伝播される分散アプリケーション（分割されたデータベース等）によく適している。
2007538306.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク内の複数のホストを接続するシステムであって、
ａ）各ホストがハートビートリンクによって、該各ホストが隣接しているネイバーホストへ接続される、前記複数のホストの間のリンクの第１のチェーンと、
ｂ）各ホストがハートビートリンクによって前記隣接しているネイバーホストに隣接しているホストへ接続される、前記複数のホストの間のハートビートリンクの第２のチェーンと、
を具備するシステム。
【請求項２】
前記複数のホストの１つのホストの故障が、
ａ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに接続させ、
ｂ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに隣接しているネイバーホストに接続させ、
ｃ）前記故障したホストの第２の隣接しているネイバーホストを、ハートビートによって、前記故障したホストの第１の隣接しているネイバーホストの第２の隣接しているネイバーに接続させ、
ｄ）これによって、元々のネットワークの凝集性を維持するのに必要なリンクを確立する、
請求項１に記載のシステム。
【請求項３】
前記複数のホストの間のハートビートリンクの前記第２のチェーンは、ホストを、２つのハートビートリンクされたホストの間の少なくとも２つの介在ホストに接続する、請求項１に記載のシステム。
【請求項４】
前記複数のホストの１つのホストの故障が、
ａ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに接続させ、
ｂ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの少なくとも第２の隣接しているネイバーホストに隣接しているネイバーホストに接続させ、
ｃ）前記故障したホストの少なくとも第２の隣接しているネイバーホストを、ハートビートによって前記故障したホストの第１の隣接しているネイバーホストの少なくとも第２の隣接しているネイバーに接続させ、
ｄ）これによって、元々のネットワークの凝集性を維持するのに必要なリンクを確立する、
請求項３に記載のシステム。
【請求項５】
ネットワークされたコンピュータクラスタ内の複数のホストを接続する方法であって、
ａ）各ホストが、ハートビートによって、該各ホストが隣接しているネイバーホストへ接続されるように、前記複数のホストの間にリンクの第１のチェーンを確立し、
ｂ）各ホストが、ハートビートリンクによって、前記隣接しているネイバーホストに隣接しているホストへ接続されるように、前記複数のホストの間にリンクの第２のチェーンを確立する、
方法。
【請求項６】
前記複数のホストの１つのホストの故障が、
ａ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに接続させ、
ｂ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに隣接しているネイバーホストに接続させ、
ｃ）前記故障したホストの第２の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第１の隣接しているネイバーホストに隣接しているネイバーホストに接続させる、
請求項５に記載の方法。
【請求項７】
ハートビートリンクの前記第２のチェーンが、２つのハートビートリンクされたホストの間の少なくとも２つの介在ホストを備えたホストに接続される、請求項５に記載のネットワークされたコンピュータクラスタ内の複数のホストを接続する方法。
【請求項８】
前記複数のホストの１つのホストの故障が、
ａ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに接続させ、
ｂ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに隣接しているネイバーホストに接続させ、
ｃ）前記故障したホストの第２の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第１の隣接しているネイバーホストに隣接しているネイバーホストに接続させる、
請求項５に記載の方法。
【請求項９】
前記複数のホストの１つのホストの故障が、
ａ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに接続させ、
ｂ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに少なくとも隣接しているネイバーホストに接続させ、
ｃ）前記故障したホストの第２の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第１の隣接しているネイバーホストに少なくとも隣接しているネイバーホストに接続させる、
請求項７に記載の方法。
【請求項１０】
最小の帯域幅を使用しながら、ネットワークされたコンピュータのクラスタ内の複数のホストの接続のコヒーレンスを維持する手段であって、
ａ）各ホストが、ハートビートリンクによって、該各ホストが隣接しているネイバーホストへ接続されるように、前記複数のホストの間にリンクの第１のチェーンを確立する手段と、
ｂ）各ホストが、ハートビートリンクによって、前記隣接しているネイバーホストに隣接しているホストへ接続されるように、前記複数のホストの間にハートビートリンクの第２のチェーンを確立する手段と、
を具備する手段。
【請求項１１】
前記ネットワークのコヒーレンスは前記複数のホストの１つのホストが故障している間維持され、
前記コヒーレンスの機能は、
ａ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに接続する手段と、
ｂ）前記故障したホストの第１の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第２の隣接しているネイバーホストに隣接しているネイバーホストに接続させる手段と、
ｃ）前記故障したホストの第２の隣接しているネイバーホストを、ハートビートリンクによって、前記故障したホストの第１の隣接しているネイバーホストに隣接しているネイバーホストに接続させる手段と、
を含み、
ｄ）これによって、残りのネットワークされたホストの相互接続が維持される、
請求項１０に記載の手段。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の協働するコンピュータの中で共通のメンバーシップを確立し維持するためのソフトウェアベース通信アーキテクチャおよび関連したソフトウェア方法を含む。
【背景技術】
【０００２】
メンバーシップは、ここではホストと呼ばれるコンピュータのセットを意味し、これは、クラスタと呼ばれる協働するグループのメンバーである（コンピュータは、１つまたはそれ以上のＣＰＵと、メモリと、ディスク記憶装置と、ネットワーク接続と、から構成される一般的な計算システムである）。各ホストは、メンバーシップリストと呼ばれるリストを維持し、これは、クラスタセットとも呼ばれるクラスタ内のホストのセットのこのホストのビューを列挙し、これは、他のホストがグループに結合したかまたは離脱したことを検出したときに、リストを修正する。ホストは、故障したかまたは他のホストとの通信を中止した後に、自主的にグループを離脱するかまたは無意識に離脱する。様々なクラスタホストのメンバーシップリストは、クラスタセット変化の通知がホスト内に伝播するときに、一時的に異なってもよい。
【０００３】
クラスタセットの変化が発生するときには、メンバーシップリストがすべてのクラスタホストで同一の内容に即座に収束するように、すべてのホストはそのメンバーシップリストを即座に更新する必要がある。クラスタメンバーシップのこの特性は、コヒーレンスと呼ばれ、クラスタがその作用を緊密に調整することを可能にし、たとえば、クラスタメンバーの中で共有作業負荷を分割し分散し、クラスタセットの変化が発生した後に必要に応じて作業を再分散する。共有作業負荷の例は、並列探索またはソートの目的でルックアップキーに基づいて、クラスタセットにわたって分割されるデータベーステーブルである。少なくとも、ホストがいずれかの単一ホストの故障を即座に検出し、そのメンバーシップリストを更新してそのコヒーレンスを再確立し、それによって共有作業負荷を再分割するのを可能にすることが必要である。即座のリカバリは、作業負荷を処理する際に崩壊を最小限にする。ホストが複数の同時ホスト故障を検出しリカバリすることができることもまた望ましい。作業負荷の有用な処理を維持するようにホストの故障を即座に検出しそれからリカバリするクラスタメンバーシップが、高度に利用可能であるといわれる。
【０００４】
高度に利用可能なクラスタは、様々な技術を使用して故障に対する耐性を増加する。たとえば、確実な通信プロトコルおよび冗長ネットワークハードウェア（たとえば、アダプタ、スイッチおよびルータ）は、通信故障の可能性を減少し、冗長記憶コンポーネント（たとえば、ＲＡＩＤドライブ）は、記憶故障の確率を減少する。しかし、ホストの故障は発生することがあり、リカバリを開始することができ有用な処理を再開することができるように、即座に検出されなければならない。ホストの故障を検出するためのよく知られた技術は、他のホストの存在および健全性を決定するために、ホストの間で、ハートビート接続と呼ばれる周期的なメッセージの交換を使用することである。クラスタホストは、ホストの間で共有されるコンピュータネットワークを使用して、周期的に（たとえば、１秒に１回）ハートビートメッセージを送り且つ受け取る。たとえば、図１は、ハートビート接続（ここでは、ハートビートリンクとも呼ばれる）上でハートビートメッセージを交換する２つのホストを示す。ハートビートメッセージの間の期間を最小限にすることは、ホストが故障をより即座に検出しクラスタメンバーシップをよりコヒーレントに保つことを可能にする。しかし、ハートビート接続は、ネットワークおよびコンピュータのオーバーヘッドを加え、より短いハートビート期間はより大きなオーバーヘッドを有する。
【０００５】
高度に利用可能なクラスタメンバーシップを構築する際の重要な挑戦は、クラスタセットが変化した後にメンバーシップのコヒーレンスを最大限にしながら、メンバーシップリストが効率的に増大することを可能にし大きな数（すなわち、何百）のホストをサポートすることである。この特性を有するクラスタメンバーシップは、拡張可能であると言われる。クラスタメンバーシップを拡張可能にするために、ハートビート接続に関連したオーバーヘッドが増大するのは、ホストの数よりも遅いことが非常に望ましい。加えて、拡張への障害、たとえば、完全に共有された固定帯域ネットワーク媒体は、回避するべきである。例として、各ホストが他のすべてのメンバーとハートビート接続を有するクラスタメンバーシップは、ホストによって交換される周期的なハートビートメッセージの数が二次関数で（すなわち、ホストの数の二乗に比例して）増大するため、効率的には拡張しない。
【０００６】
小さなクラスタ（一般的に、２〜４のホスト）でクラスタメンバーシップを確立するための一般的な方法は、クラスタの各ホストが、他のすべてのホストとハートビート接続を有することである。たとえば、図２は、４つのホストおよび６つのハートビートリンクを備えたクラスタセットを示す。ホストは、クラスタセットに変化が発生するときには必ず検出することができる。上記に注記されたように、このやり方でメンバーシップを維持するために各ホストに必要なオーバーヘッドは、クラスタセットのサイズとともに非線形的に増大する。このオーバーヘッドを減少するために、ハートビートメッセージは、他のすべてのホストへブロードキャストされるかまたはマルチキャストされてもよい。この場合、メッセージトラフィックは、ホストの数とともに線形的に増大する。しかし、このアプローチは、コンピュータネットワークがマルチキャスト用に効率的なハードウェアサポートを提供することを必要とし、マルチキャストをサポートするために共有ネットワークスイッチを使用することは、スイッチの帯域幅が固定されるため、障害になりうる。マルチキャストの使用を回避するために、すべてのハートビート接続は、スポークを車輪上に車軸に対して取り付けるのと同様に、クラスタ内の単一の「マスター」ホストに接続することができる。この配列は、残念ながら、マスターホストを故障の単一点にしクラスタ全体の障害になる。したがって、これらの通信アーキテクチャは固有の限界を有し、大きなクラスタセットサイズを取り扱うために拡張するのを阻止する。
【０００７】
これらの問題を回避するために、大きなクラスタメンバーシップ（たとえば、何百のホストを備えた）は、そのメンバーシップが上述のようなやり方で維持されてもよい多くの個別ホストまたは小さなクラスタ（サブクラスタと呼ばれる）を緩く集めることによって、形成されることが多い。オーバーヘッドを最小限にするために、これらの大きな「ピアツーピア」メンバーシップは、サブクラスタの間の周期的なハートビート接続を維持しない。結果として、グローバルクラスタメンバーシップを分割することができ、且つ／または、クラスタセットの変化が発生するときにメンバーシップリストは長期間発散してもよい。クラスタメンバーシップを維持するこの方法は、共有作業負荷を分割する際にすべてのクラスタメンバーの作用を緊密に調整するほど、十分にコヒーレントではない。本発明が修正しようとしているのは、大きなクラスタメンバーシップ用に先行技術が試みるこの制限である。
【０００８】
ここに記載された本発明を、コンピュータの間の通信用の物理的なネットワークの設計における先行技術の試みから分別することが重要である。並列スーパーコンピュータの設計等の先行技術の試みにおいて、もっとも近いネイバーおよびマルチホップ相互接続を含む物理的なポイントツーポイントコンピュータ相互接続ネットワークが提案されているかまたは実行されている。たとえば、図３の相互接続ネットワークは、もっとも近いネイバーおよびホストの間のマルチホップ物理的通信リンクを示す。これらのコンピュータネットワークは、大きな数の相互接続されたコンピュータをサポートするためにネットワークハードウェアの効率的な構築を可能にするように考案されている。しかし、これらのネットワークは、物理的な通信媒体を厳密に表し、意図されたふるまいを実行するソフトウェアアーキテクチャまたはメッセージ通信パターンを特定しない。対照的に、本発明は、拡張可能で高度に利用可能なクラスタメンバーシップを構築するために、ホストの故障を検出しそれからリカバリする目的で、コンピュータの間のハートビート接続を構築するためのソフトウェアアーキテクチャを記載する。ハートビート接続は、不特定の基礎をなす物理的なネットワーク、たとえばいくつか例を挙げると、図３に示されたようなネットワーク、共有イーサネット（登録商標）スイッチ、クロスバーネットワーク、メッシュバックプレーン等上で通信する。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、ネットワーク内の複数のコンピュータ（ホストと呼ばれる）を接続するシステムに関する。
【課題を解決するための手段】
【００１０】
これらのホストは、周期的なメッセージ交換（ハートビートリンクと呼ばれる）に携わり、隣接するホストの健全性を決定し、それによって、通信ホストのリスト（クラスタメンバーシップと呼ばれる）を確立し維持する。本発明は、例として線状配列に、隣接している（もっとも近いネイバー）ホストを一緒に接続するハートビートリンクの第１のセットと、隣接している（もっとも近いネイバー）ホストに隣接している他のホストへホストを接続するハートビートリンク（重なり合いハートビートリンクと呼ばれる）の第２のセットと、を使用する。言い換えると、各重なり合いハートビートリンクは、隣接している（もっとも近いネイバー）ホストを飛び越して、隣接している（もっとも近いネイバー）ホストの他方の側のホストに接続する。ホストが故障したときには、隣接しているハートビートリンクが、故障したホストの第１の隣接しているネイバーが故障したホストを検出して、（ａ）もっとも近いネイバーとして故障したホストの第２の隣接しているネイバーと、および、（ｂ）第２の隣接しているネイバーの隣接しているネイバーとも、ハートビートリンクを確立するのを可能にし、それによって、故障したホストを飛び越し、すべての故障していないホストを一緒に、連続したチェーンに接続するハートビートリンクのセットの一体性を維持する。故障したホストの第２の隣接しているネイバーはまた、そのもっとも近いネイバーとして故障したホストの第１の隣接しているネイバーとの、および、故障したホストの第１の隣接しているネイバーの隣接しているネイバーとの、ハートビートリンクを確立する。これは、ホストの故障前に存在した単一ホップおよび複数ホップの（重なり合い）ハートビートリンクのシステムを再確立する。第１のハートビートリンクはまた、上記に説明したように隣接しているホストを接続してもよく、次いで、第２のハートビートリンクを使用して複数の隣接しているホストを飛び越し、それによって、それらの間の複数の介在ホストを有するホストを接続する。ネットワークの各次元内で隣接しているハートビートリンクおよび重なり合いハートビートリンクの両方を使用してホストを接続する一次のまたは多次元のホストネットワーク構造は、本発明の範囲内である。
【発明を実施するための最良の形態】
【００１１】
このセクションは、まず本発明の好適な実施の形態を説明し、次にその論理的根拠および利点を述べる。
「説明」
本発明は、ホストを、もっとも近いネイバーおよびホストの間の重なり合いハートビート接続の両方を備えた単一のまたは多次元のアレイに論理的に組織することによって、拡張可能で高度に利用可能性なメンバーシップを構築する。重なり合いハートビート接続は、アレイの２つ以上の（ネイバー）ホストに及ぶ接続として規定される。たとえば、２ホップ接続は、３ホストに及び、１つの中間ホストを通過する。一般に、Ｍホップ重なり合い接続は、Ｍ＋１ホストに及ぶ。本発明のもっとも簡単な実施の形態は、一次元の２ホップアレイであり、これは、もっとも近いネイバーおよび２ホップハートビート接続の両方を使用する。例として、図４は、ホスト０からホスト４とラベルされた５つのホストの一次元の２ホップアレイを示し、ホストのすべてが共有ネットワークスイッチを使用して通信する。各ホストは、その直前のものに対する１つのハートビート接続（ハートビートリンクとも呼ばれる）と、その直後のものに対する別のハートビート接続と、を有する。たとえば、ホスト２はリンクＢを使用してその直前のものすなわちホスト１に接続し、リンクＣを使用してその直後のものすなわちホスト３に接続する。さらに、ホスト２は、リンクＱを使用して次の前のものすなわちホスト０にハートビート接続を有し、ホスト２は、リンクＳを使用して次の後のものすなわちホスト４に別のハートビート接続を有する。他の実施の形態において、ホストは、Ｎ次元メッシュに配列されることができ（Ｎ次元の負荷分散用に負荷バランスを最適化するため）、その場合、各ホストは、もっとも近いネイバーおよびアレイの各次元の重なり合い接続を有する。たとえば、図５は、二次元の２ホップアレイを示す。代替の実施の形態もまた、Ｍホップ接続を使用することができる。ただし、Ｍは３以上であり、（複数の隣接するホスト故障の場合には、耐故障性を改良するために）Ｍの異なる値用に複数のＭホップ接続を組み込むこともできる。これらの実施の形態は、本発明の範囲内に含まれる。ここに記載されたソフトウェア方法は、ハートビート接続の一次元２ホップアレイをどのように構築するかを説明する。本発明はまた、三次元でホストを接続する能力も含み、隣接しているホストは、すべてターゲットホストの隣でありそれを囲む。
「論理的根拠および利点」
重なり合いハートビート接続の使用は、クラスタメンバーシップを分割せずにクラスタ内で隣接するホストの故障をホストが直接且つ即座に検出しそれからリカバリするのを可能にする。これは、ホスト故障の存在時にクラスタメンバーシップが高度に利用可能のままであることを可能にする。たとえば、図６は、ホスト２およびその関連ハートビート接続リンクＢ、Ｃ、ＱおよびＳの故障を示す。この例において、ホスト１およびホスト３は、故障したハートビート接続を使用してホスト２の故障を検出し、重なり合いハートビート接続、リンクＲを使用して互いにクラスタメンバーシップを維持し、これが今や、ホスト１とホスト３との間の非重なり合いハートビート接続として作用する。重なり合い接続、リンクＲの存在は、ホスト２の故障によってクラスタメンバーシップが分割されるのを防止する。ホスト１およびホスト３は、そのメンバーシップリストを更新して故障したホスト２を取り外し、ホスト２の故障をその隣接するホスト、すなわちホスト０およびホスト４へ知らせる。図７に示されるように、残っているホスト（０、１、３および４）は、新しい重なり合いハートビート接続ＴおよびＵを形成して、ホスト２の故障後のクラスタのリカバリを完了する。
【００１２】
先行技術の試みとは異なり、本発明は、ハートビート接続を使用して高度に利用可能なクラスタメンバーシップを可能にし、大きな数（たとえば、何百）のホストへ効率的に拡張する。各ホストは固定した数のハートビート接続を有するため、クラスタメンバーシップを維持するのに必要なオーバーヘッドは、クラスタセットが増大するときに増加しない。図４に述べられた実施の形態において、各ホストは、通常操作下で４つ以下のハートビート接続、および、ホストがクラスタに結合するときに１つの追加ハートビート接続、を有する。クラスタホストは、追加のメンバーシップ変更メッセージを隣接するホストに送ることによって、メンバーシップの変更（すなわち、新しく結合した、離れた、および、故障したホストのリスト）を離れたホストへ知らせる。たとえば、図７は、隣接するホストが故障した後にメンバーシップ変更メッセージを送っているホスト１を示す。これらのメッセージは、単一のホストの故障または単一のネットワーク接続の故障のためにクラスタメンバーシップが絶対に分割されることはないことを、２ホップ重なり合いハートビート接続が確実にするため、確実にすべてのホストへ伝播する。周期的に送られるハートビートメッセージとは異なり、メンバーシップ変更メッセージは、メンバーシップの変化が発生した後に送られるだけであり、これは、拡張に影響を与えないわずかなオーバーヘッドを加える。クラスタメンバーシップのグローバルコヒーレンスを再確立するために必要な時間は、クラスタセットのサイズとともに増加するが（メンバーシップ変更メッセージをすべてのホストへ伝播する待ち時間のために）、ハートビート接続でネイバーの間のローカルコヒーレンスを再確立するために必要な時間は、固定され且つ非常に短く、クラスタを拡張することによって影響されない。クラスタメンバーシップを維持するためのこの方法は、アプリケーション（分散分割データベース等）によく適しており、負荷分散変化は、隣接するホストによって増分的に作ることができ、クラスタ内のより離れたホストへ伝播される。
【００１３】
本発明はまた、クラスタセットのサイズが増大するにつれてネットワークの帯域幅を拡張することができるように、ホストが複数のネットワークスイッチを使用するのを可能にする。これは、ネットワークの帯域幅が、クラスタメンバーシップ用の拡張性に対する障害にならないことを確実にする。図８は、２つのネットワークスイッチを備えた図８の例の実施の形態を示す。この例において、ホスト１、２および３は、両方のネットワークスイッチに接続するために２つのハードウェアネットワークインタフェースを必要とする。１つのスイッチ上のホストの数がそのスイッチの帯域幅能力に近づくときには必ず、ネットワークスイッチを加えることができる。ホストは、ハートビート接続する他のホストへ直接接続（たとえば、スイッチを通して）を有する必要があるだけである。したがって、これらのホストが接続されるすべてのスイッチへ、ネットワークインタフェースを有さなければならない。図５に示された一次元２ホップの実施の形態では、各ホストは、最大２のネットワークインタフェースを必要とする。
「本発明の１つの実施の形態用のソフトウェア方法」
下記のソフトウェア方法は、隣接するホストが、線形的に相互接続されるハートビート接続を有し且つ各ホストが次の前のものに対して１つの重なり合いハートビート接続を有し次の後のもの（これらのホストが存在する場合）に対して重なり合いハートビート接続を有する本発明の一次元２ホップの実施の形態に適用される。５つのホストを備えたこの実施の形態の例は、図４に示される。下記の用語を使用して、ソフトウェア方法の説明を簡略化する。ホストの線状配列において、ホストの直後のものは、そのＳ０と表示され、その次の後のものはＳ１と表示される。同様に、ホストの直前のものは、そのＰ０と表示され、その次の前のものはＰ１と表示される。これらのリンク表示の例は、図９に示される。この図において、ホスト３はホスト２のＳ０であり、ホスト４はＳ１、ホスト１はＰ０、ホスト０はＰ１である。Ｐ１、Ｐ０、Ｓ０およびＳ１ネイバー用のホスト識別のホストのリストは、そのネイバーリストと呼ばれる。複数のＭホップハートビート接続を備えた多次元の実施の形態用にソフトウェア方法を構築することが可能であり、これらの方法は、本発明の範囲内である。
【００１４】
記載されたソフトウェア方法は、分散ソフトウェア方法であり、すなわち、メッセージを交換してその作用を調整する複数のホストにわたってアルゴリズムが分散される。機能を実施する完全なソフトウェア方法は、したがって、複数のフローチャートによって表され、その各々が特定のホスト上で実行される。ソフトウェア方法は、単一の送り手から単一の受け手へのメッセージの順序を保存する確実なトランスポートプロトコルを使用して送られることを想定する。また、ソフトウェア方法は、２つのホストの間のハートビート接続を構築し維持する詳細は記述しない。ハートビート接続を構築するための技術は、よく理解されている。いずれかのホストによってまたは両方のホストによって同時にハートビート接続を開始することができることが想定される。
【００１５】
本発明は、ホストが既存のクラスタに結合し且つ離脱するのを可能にする下記のソフトウェア方法を組み込む。これらのソフトウェア方法は、共通のロックおよび同期機構を必要とするため、重なり合い機能を有することに注意されたい。本発明はまた、クラスタがホストの故障を検出しこれからリカバリするのを可能にするソフトウェア方法もまた組み込む。
「ホストがクラスタに結合するためのアルゴリズム」
クラスタに結合しクラスタセットの一部になることを望むホストは、候補ホストと呼ばれる。これは、初期に通信するクラスタセットのメンバーであるホストを識別する。このホストは、メンターホストと呼ばれ、管理ポリシーによって選択される。候補ホストがクラスタに結合した後に、これは、メンターホストの直後のホストになる。たとえば、図１０は、ホスト５が図３に示されたクラスタに結合したクラスタを示す。この例では、ホスト５は候補ホストであり、ホスト２はメンターホストである。ホスト５がクラスタに結合した後に、新しいハートビート接続Ｖ、Ｗ、ＸおよびＹが形成され、ハートビート接続ＲおよびＳが終了している。
【００１６】
クラスタに結合するために、候補ホストは、図１１に示されたソフトウェア方法を実行する。候補ホストは、まず、メンターホストへメンバーシップリクエストメッセージを送り、メンターホストのネイバーリスト（すなわち、ホストはそのＳ１、Ｓ０、Ｐ０およびＰ１ネイバー用のホスト識別子）を含むメンバーシップリプライメッセージを待つことによって、そのメンターホストのＳ１、Ｓ０およびＰ０を決定する。これは次いで、メンターホストのＳ１とのハートビート接続を開始し、これは、候補のＳ１Ｃと示され、ロックリクエストメッセージをＳ１Ｃへ送る（ハートビート接続を構築し維持するためにホストによって使用される方法は、ここでは説明されない）。このロックリクエストメッセージを使用して、他の候補ホストが同時にクラスタに結合するかまたは離脱することを試みている場合に、候補ホストにＳ１Ｃの専用権を与える。ホストＳ１Ｃから、Ｓ１Ｃがうまくロックされたことを示すロックリプライメッセージを受け取った後に、候補ホストは、次に、メンターホストのＳ０とのハートビート接続を開始し、これは、候補のＳ０Ｃと示され、Ｓ０Ｃへロックリクエストメッセージを送る。Ｓ０Ｃからロックリプライメッセージを受け取った後に、候補ホストは、メンターホストとこのプロセスを繰り返し、最後に、メンターホストのＰ０と行い、それぞれ、候補のＰ０ＣおよびＰ１Ｃと示される。ロックリクエストは、複数のホストが同時にクラスタに結合し且つ／または離脱するときにデッドロックを防止するために、常に同一の順序（すなわち、このソフトウェア方法では、Ｓ１Ｃ、Ｓ０Ｃ、Ｐ０ＣおよびＰ１Ｃ）で開始される。場合によっては、これら４つのネイバーホストのすべてが存在するわけではないことに注意されたい。たとえば、ホスト０は、図１０の例では、前のホストがない。
【００１７】
候補ホストがすべてのネイバーホストからロックリプライメッセージを受け取った後に、これらのホストに結合開始メッセージを送り、候補ホストへの新しいハートビート接続によって置き換えられるべき既存のハートビート接続をやめるように合図する。たとえば、図１０では、ホスト５がクラスタに結合してホスト５へハートビート接続（リンクＷ）を形成するときには、ホスト３は、ホスト１への重なり合いハートビート接続（リンクＲ）をやめる。特定のリンク変更は下記の通りである。候補ホストのＳ１ＣがそのＰ１接続をやめ、Ｓ０ＣがそのＰ１接続をやめ、Ｐ０ＣがそのＳ１接続をやめ、Ｐ１ＣがそのＳ１接続をやめる。候補ホストがすべてのネイバーホスト（図６の例では、Ｓ１Ｃ、Ｓ０Ｃ、Ｐ０ＣおよびＰ１Ｃ）から結合終了メッセージを受け取った後に、これらのネイバーホストへロック解放メッセージを送る。候補ホストは今やクラスタに結合している。
【００１８】
候補ホストがクラスタに結合するときに、それが通信する既存のホストは、図１２に示されたソフトウェア方法を実行する。第１に、メンターホストは、候補ホストからメンバーシップリクエストメッセージを受け取り、そのＳ１、Ｓ０、Ｐ０およびＰ１ネイバー用のホスト識別子を備えたメンバーシップリプライメッセージを送る（このステップはメンターホストによってのみ実行されるため、図１２には示されない）。ホストはまず、候補ホストから新しいハートビート接続を受け取りそれを受け入れる。候補ホストからロックリクエストメッセージを受け取るホストは、別の候補によってまたはクラスタを離脱している隣接するホストによってまたはクラスタを離脱する準備をしているホスト自体によって、ホストが既にロックされているか否かをチェックする。ロックが使用されている場合には、候補のロックリクエストは待機状態にされ、リプライは送られない。そうでなければ、ホストは、候補のためにロックされ、ロックリプライメッセージが候補へ送られる。ホストが候補から結合開始メッセージを受け取ったときには、今や候補のハートビート接続によって置き換えられるべき別のホストへのハートビート接続をやめる（やめるべきハートビート接続は、候補のソフトウェア方法の説明において上記に特記される）。ホストは次いで、結合終了メッセージを候補ホストへ送る。ホストが候補ホストからロック解放メッセージを受け取ったときには、そのロックをクリアし、ホストがロックされた間に別のロックリクエストが待機状態であったか否かをチェックする。そうである場合には、待機状態のロックリクエストが待機解除され、それが新しいロックリクエストであるかのように扱われる。そうでなければ、結合ソフトウェアは完了する。待機解除されたロックリクエストが新しい結合ロックリクエストである場合には、ソフトウェア方法は、制御をそのエントリーポイントＪＲへ移す。そうでなければ、待機解除されたロックリクエストが新しい離れた離脱リクエストである場合には、ソフトウェア方法は、制御を、図１５に示される異なるソフトウェア方法へ、エントリーポイントＬＲで移す。そうでなければ、待機解除されたロックリクエストは、新しいローカル離脱リクエストでなければならず、ソフトウェア方法は、制御を、図１３に示される異なるソフトウェア方法へ、エントリーポイントＬＬで移す。
「ホストがクラスタを離脱するためのアルゴリズム」
既存のクラスタを離脱することを望むクラスタは、離脱ホストと呼ばれる。このホストは、図１３に示されたソフトウェア方法を実行する。まず、そのＳ１ホストへロックリクエストメッセージを送り、このホストからロックリプライメッセージを待つ。次に、そのＳ０ホストへロックリクエストメッセージを送り、このホストからロックリプライメッセージを待つ。離脱ホストは次いで、そのローカルホストロックを設定するように試みる。ロックが既に使用されている場合には、離脱ホストは待機状態にされ、ソフトウェア方法は、図１３に示されるように、ロックリクエストがエントリーポイントＬＬで要求に応えることができるまで、実行を一時停止する。次に、そのＰ０ホストへロックリクエストメッセージを送り、このホストからロックリプライメッセージを待ち、最後に、離脱ホストは、そのＰ１ホストへロックリクエストメッセージを送り、このホストからロックリプライメッセージを待つ。ロックリクエストは、複数のホストが同時にクラスタに結合し且つ／または離脱するときにデッドロックを防止するために、常に同一の順序（すなわち、このソフトウェア方法では、Ｓ１、Ｓ０、ローカルホスト、Ｐ０およびＰ１）で開始される。場合によっては、これら４つのネイバーホストのすべてが存在するわけではないことに注意されたい。
【００１９】
離脱ホストがすべてのネイバーホストからロックリプライメッセージを受け取った後に、これらのホストへ、そのＳ１、Ｓ０、Ｐ０およびＰ１識別子を含む離脱開始メッセージを送り、離脱ホストのハートビート接続と置き換えるべき別のホストへの新しいハートビート接続を加えるように合図する。たとえば、図１４は、クラスタを離脱する（先に、図１０の例では結合していた）ホスト５を示す。この例では、ホスト１はホスト３へ重なり合いハートビート接続（リンクＲ）を形成し、離脱するホスト５へのハートビート接続（リンクＸ）をやめる。同様に、ホスト４はホスト２へ重なり合いハートビート接続（リンクＳ）を形成し、ホスト５へのハートビート接続（リンクＹ）をやめる。特定のリンク変更は下記の通りである。離脱ホストのＳ１が、離脱ホストのＰ０へ新しいＰ１接続を構築し、その既存のＰ１接続をやめる。Ｓ０が、離脱ホストのＰ１へ新しいＰ１接続を構築し、そのＰ０接続をやめる。Ｐ０が、離脱ホストのＳ１へ新しいＳ１接続を構築し、そのＳ０接続をやめる。最後に、Ｐ１が、離脱ホストのＳ０へ新しいＳ１接続を構築し、そのＳ１接続をやめる。離脱ホストがすべてのネイバーホスト（Ｓ１、Ｓ０、Ｐ０およびＰ１）から離脱終了メッセージを受け取った後に、これらのネイバーホストへロック解放メッセージを送り、それらへのハートビート接続をやめる（図１４では、リンクＶ、Ｗ、ＸおよびＹ）。離脱ホストは今やクラスタを離脱している。離脱ホストがロックリクエストを待機状態にしている場合には、既存のホストへロックリクエストを再提出するように要請する特別なロックリプライメッセージをリクエストするものへ送ることに注意されたい。
【００２０】
離脱ホストがクラスタを離脱するときには、これが通信する既存のホストは、図１５に示されたソフトウェア方法を実行する。ホストはまず、離脱ホストからロックリクエストメッセージを受け取り、候補ホストによってまたはクラスタを離脱している隣接するホストによってまたはクラスタを離脱する準備をしているホスト自体によって、ホストが既にロックされているか否かをチェックする。ロックが使用されている場合には、離脱ホストのロックリクエストは待機状態にされ、リプライは送られない。そうでなければ、ホストは、離脱ホストのためにロックされ、ロックリプライメッセージが離脱ホストへ送られる。ホストが離脱ホストから離脱開始メッセージを受け取ったときには、今や離脱ホストのハートビート接続と置き換えるべき別のホストへのハートビート接続を構築する（形成されるべきハートビート接続は、離脱ホストのソフトウェア方法の説明において上記に特記される）。ホストは次いで、離脱終了メッセージを候補ホストへ送る。ホストが離脱ホストからロック解放メッセージを受け取ったときには、そのロックをクリアし、離脱ホストへのハートビート接続をやめる。次いで、ホストがロックされた間に別のロックリクエストが待機状態であったか否かをチェックする。そうである場合には、待機状態のロックリクエストが待機解除され、それが新しいロックリクエストであるかのように扱われる。そうでなければ、離脱ソフトウェア方法は完了する。待機解除されたロックリクエストが新しい結合ロックリクエストである場合には、ソフトウェア方法は、制御を、図１２に示される異なるソフトウェア方法へ、エントリーポイントＪＲで移す。そうでなければ、待機解除されたロックリクエストが新しい離れた離脱リクエストである場合には、ソフトウェア方法は、制御をエントリーポイントＬＲへ移す。そうでなければ、待機解除されたロックリクエストは、新しいローカル離脱リクエストでなければならず、ソフトウェア方法は、制御を、図１３に示される異なるソフトウェア方法へ、エントリーポイントＬＬで移す。
「クラスタホストが故障したホストからリカバリするためのアルゴリズム」
ホストが故障しているときには、これの隣接するホストは、そのハートビート接続を使用して故障を検出する。これらのホストは、２ホップ接続を復帰し故障したホストを排除する新しい重なり合いハートビート接続を構築することによって、リカバリしなければならない。たとえば、図１６は、ホスト２およびその関連ハートビート接続（リンクＢ、Ｃ、ＱおよびＲ）が故障したクラスタを示す。ホスト０はホスト３へハートビート接続を構築しなければならず（図のリンクＸ）、ホスト４はホスト１へハートビート接続を構築しなければならない（リンクＹ）。リンクＲは、その役割を、重なり合いハートビート接続から、ホスト１と３との間のもっとも近いネイバー接続へ、変えることに注意されたい。
【００２１】
ホスト故障からリカバリする（ここではヒーリングとも呼ばれる）ためのソフトウェア方法は、故障したホストの４つのネイバー（すなわち、そのＰ１、Ｐ０、Ｓ０またはＳ１）のいずれか１つによって実行するように設計することができる。下記のソフトウェア方法は、もっとも近いネイバーＰ０が存在する場合にはそれからリカバリを開始する。このホストは、イニシエーターと呼ばれる。ソフトウェア方法は、Ｐ０が存在しない場合には（すなわち、故障したホストがアレイのもっとも左側のホストである場合には）、Ｓ０から開始するように対称的に実行することができる。このソフトウェア方法において、故障したホストからＰ０（またはＳ０）の反対側のもっとも近いネイバーであるホストは、Ｐ０（またはＳ０）の外側ネイバーと呼ばれる。たとえば、図１６では、ホスト０はホスト１の外側ネイバーであり、ホスト４はホスト３の外側ネイバーである。また、ホストから反対側にある故障したホストのもっとも近いネイバーであるホストは、ここでは、反対ネイバーと呼ばれ、反対ネイバーの外側ネイバーは、反対外側ネイバーと呼ばれる。たとえば、図１６では、ホスト３はホスト０およびホスト１の反対ネイバーであり、ホスト１はホスト２およびホスト３の反対ネイバーであり、同様に、ホスト４はホスト１の反対外側ネイバーであり、ホスト０はホスト３の反対外側ネイバーである。
【００２２】
図１７は、ヒーリングを開始するためのソフトウェア方法を示す。イニシエーターは、通常は、故障したホストのＰ０であり、まずヒーリング更新メッセージを、その外側ネイバーが存在する場合にはそのネイバーへ送る。イニシエーターが反対側ネイバーを有する場合には、ネイバーリストを含むヒーリングリクエストメッセージを、ネイバーに送る。そうでなければ、ソフトウェア方法は終了する。次いで、イニシエーターは、その反対ネイバーからヒーリングリプライメッセージを待つ。このメッセージは、ネイバーホストの反対ネイバーのリストを含み、イニシエーターは、このリストを使用して、反対外側ネイバーが存在する場合にはそれへ重なり合いハートビート接続を構築する。図１６の例において、イニシエーターホスト１は、その反対外側ネイバーホスト４へ重なり合いハートビート接続（リンクＹ）を構築する。最後に、イニシエーターは、新しいネイバーからヒーリング完了メッセージを待ち、ソフトウェア方法は終了する。
【００２３】
図１８は、イニシエーターの外側ネイバーによっておよびその反対外側ネイバーによっても、これらのホストが存在する場合に、実行されるソフトウェア方法を示す。外側ネイバーがヒーリング更新メッセージを受け取った後に、メッセージ内のネイバーリストをチェックし、反対ネイバーが存在するか否かを決定する。このホストが存在する場合には、外側ネイバーは、反対ネイバーへ新しい重なり合いハートビート接続を構築し、ヒーリング完了メッセージを送る。これは、外側ネイバーのソフトウェア方法を終了する。図１６の例において、外側ネイバーホスト０および４は、それぞれ、その反対ネイバーホスト３および１へ重なり合いハートビート接続（リンクＸおよびＹ）を構築する。
【００２４】
図１９は、ヒーリングリクエストメッセージを受け取ったときにイニシエーターの反対ネイバーによって実行されるソフトウェア方法を示す。このホストは、ヒーリングリプライメッセージをイニシエーターへ送り返し、このメッセージは、ネイバーホストの反対ネイバーのリストを含む。イニシエーターはこのリストを使用して、その反対外側ネイバーへハートビート接続を構築するか否かを決定する（イニシエーターのソフトウェア方法について上述したように）。反対ネイバーが外側ネイバーを有する場合には、このホストへヒーリング更新メッセージを送る。反対ネイバーは次に、イニシエーターから受け取ったネイバーリストを見て、反対外側ネイバーを有するか否かを決定する。このホストが存在する場合には、反対ネイバーは、反対外側ネイバーへ新しい重なり合いハートビート接続を構築し、このホストからヒーリング完了メッセージを待つ。図１６の例において、外側ネイバーホスト３は、その反対外側ネイバーホスト０へ重なり合いハートビート接続（リンクＸ）を構築する。
【００２５】
図１７〜１９に示されたソフトウェア方法は、ヒーリング完了メッセージの到着順序が、それぞれ反対ネイバーまたはイニシエーターでヒーリングリクエストメッセージまたはヒーリングリプライメッセージの到着に対して不確定であるため発生する「レース」状態を有する。これらのソフトウェア方法の実施はこのレース状態を取り扱わなければならないが、これは、ソフトウェア方法に記載されたロジックを変更しない。
【００２６】
本発明は、その特定の実施の形態を述べるように説明されているが、本発明は、それに限定されない。詳細における変更が本発明の精神および範囲内で行われてもよく、上記精神および範囲は、広く解釈されるべきものであり、ここに添付の特許請求の範囲の特徴による以外、限定されない。
「関連出願へのクロスリファレンス」
本出願は、本発明者によって２００４年３月１０日に出願された仮特許出願第６０／５５１，８３７号の利益を主張する。
【図面の簡単な説明】
【００２７】
【図１】ハートビート接続を備えた２つのクラスタホストを示す。
【図２】すべてのホスト対の間でハートビートリンクを備えた４つのクラスタホストの例である。
【図３】重なり合う物理的通信リンクを備えた従来技術の５つのホストクラスタの例である。
【図４】共有物理的ネットワークスイッチを使用することによって重なり合う論理的なハートビート接続を備えた５つのホストクラスタを示す。
【図５】１６のクラスタホストを備えたハートビート接続の二次元２ホップアレイの例を示す。
【図６】故障したホストおよびその関連した故障したハートビート接続リンクの例を示す。
【図７】図面に示されたホスト２が故障した後のクラスタのリカバリの例である。
【図８】重なり合いハートビート接続リンクを備えたクラスタに複数のネットワークスイッチを使用する例であり、ホスト１、２および３は複数のネットワークインタフェースを使用する。
【図９】ホスト２の直前および直後のホスト表示を示すクラスタの例を示す。
【図１０】クラスタを結合する候補の例である。
【図１１】クラスタを結合する候補ホストのソフトウェア方法を示すフローチャートである。
【図１２】候補の結合リクエストを受け入れるクラスタホストのソフトウェア方法を示すフローチャートである。
【図１３】クラスタを離脱する離脱ホストのソフトウェア方法を示すフローチャートである。
【図１４】クラスタを離脱するホストの例を示す。
【図１５】離脱ホストの離脱リクエストを受け入れるクラスタホストのソフトウェア方法のフローチャートである。
【図１６】故障したホストからリカバリするクラスタの例を示す。
【図１７】ホスト故障後のクラスタのヒーリングを開始するネイバーホストのソフトウェア方法のフローチャートである。
【図１８】ホスト故障後のクラスタのヒーリングを完了する外側ネイバーホストのソフトウェア方法を示すフローチャートである。
【図１９】ホスト故障後のクラスタのヒーリングを完了する反対ネイバーホストのソフトウェア方法を示す。
【図１】
2007538306.tif 000003
【図２】
2007538306.tif 000004
【図３】
2007538306.tif 000005
【図４】
2007538306.tif 000006
【図５】
2007538306.tif 000007
【図６】
2007538306.tif 000008
【図７】
2007538306.tif 000009
【図８】
2007538306.tif 000010
【図９】
2007538306.tif 000011
【図１０】
2007538306.tif 000012
【図１１】
2007538306.tif 000013
【図１２】
2007538306.tif 000014
【図１３】
2007538306.tif 000015
【図１４】
2007538306.tif 000016
【図１５】
2007538306.tif 000017
【図１６】
2007538306.tif 000018
【図１７】
2007538306.tif 000019
【図１８】
2007538306.tif 000020
【図１９】
2007538306.tif 000021