(57)【要約】【課題】Split-Brain Syndromeを防止しつつ、特権ノード決定を行う際に、特権ノードが決まらないような状態をできるだけ起こらないようにする。【解決手段】分散システム１００は、クラスタ１０の外部に外部サーバ２を備え、外部サーバ２は、クラスタ１０が分断された各サブクラスタの特権ノード候補から各サブクラスタのメンバ数の情報を集約し、最もメンバ数の多いサブクラスタ、または、メンバ数が最多かつ等しいサブクラスタが複数存在する場合には特定のロジックに基づいて選出した一つのサブクラスタの特権ノード候補に特権ノード昇格の了承を、それ以外の特権ノード候補に否決を通知する。各サブクラスタの特権ノード候補は、外部サーバ２から了承の通知を受けた場合、特権ノードに昇格してクラスタ１０を構築し、外部サーバ２から否決の通知を受けた場合、当該サブクラスタを解体する。【選択図】図７
2015215754.tif 000002
【特許請求の範囲】
【請求項１】
Paxosアルゴリズムを含む多数決分散合意形成アルゴリズムを適用して、クラスタを構成する複数のノードの中からノードを管理する特権を持つ特権ノードを選出するクラスタシステムであって、
前記特権ノードを管理する外部サーバを前記クラスタの外部に備え、
前記外部サーバは、
前記クラスタが分断された各サブクラスタの特権ノード候補から各サブクラスタのメンバ数の情報を集約し、最もメンバ数の多いサブクラスタ、または、メンバ数が最多かつ等しいサブクラスタが複数存在する場合には特定のロジックに基づいて選出した一つのサブクラスタの特権ノード候補に特権ノード昇格の了承を、それ以外の特権ノード候補に否決を通知する管理部を備え、
前記サブクラスタの特権ノード候補は、
前記外部サーバから了承の通知を受けた場合、特権ノードに昇格してクラスタを構築し、
前記外部サーバから否決の通知を受けた場合、当該サブクラスタを解体する
ことを特徴とするクラスタシステム。
【請求項２】
前記サブクラスタの特権ノード候補は、
前記外部サーバから了承または否決の応答がなく、かつ当該サブクラスタのメンバ数が過半数を満たす場合、前記多数決分散合意形成アルゴリズムを適用して、特権ノードとして自律的にクラスタを構築することを特徴とする請求項１に記載のクラスタシステム。
【請求項３】
前記サブクラスタの特権ノード候補は、
前記外部サーバから了承または否決の応答がなく、かつ当該サブクラスタのメンバ数が過半数を満たさない場合、所定タイムアウト期間経過後に自律的に当該サブクラスタを解体することを特徴とする請求項１または請求項２に記載のクラスタシステム。
【請求項４】
前記クラスタの特権ノードは、自身が特権ノードであることを示す特権ノード情報およびクラスタメンバ数を、定期的およびクラスタのメンバ数が変化した時に前記外部サーバへ報告することを特徴とする請求項１ないし請求項３のいずれか一項に記載のクラスタシステム。
【請求項５】
前記サブクラスタの特権ノード候補は、
当該サブクラスタのメンバ数が、自身が特権ノード候補であることを示す特権ノード候補情報およびサブクラスタメンバ数を含む特権ノード昇格要求を前記外部サーバへ発行することを特徴とする請求項１ないし請求項４のいずれか一項に記載のクラスタシステム。
【請求項６】
前記外部サーバは、
通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計が前記クラスタの総メンバ数の半数に満たない場合、通信可能な特権ノード候補に対し一律に否決を通知することを特徴とする請求項２ に記載のクラスタシステム。
【請求項７】
前記外部サーバは、
通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計が前記クラスタの総メンバ数の半数に満たない場合、保守者端末に特権ノード候補の通知を行うとともに、当該保守者端末から当該特権ノード候補の了承または否決の判断通知を受け、当該判断通知に従って、特権ノード候補に対し了承または否決を通知することを特徴とする請求項２に記載のクラスタシステム。
【請求項８】
Paxosアルゴリズムを含む多数決分散合意形成アルゴリズムを適用して、クラスタを構成する複数のノードの中からノードを管理する特権を持つ特権ノードを選出するクラスタシステムのSplit-Brain Syndrome発生防止方法であって、
前記特権ノードを管理する外部サーバを前記クラスタの外部に備え、
前記外部サーバは、
前記クラスタが分断された各サブクラスタの特権ノード候補から各サブクラスタのメンバ数の情報を集約するステップと、
最もメンバ数の多いサブクラスタ、または、メンバ数が最多かつ等しいサブクラスタが複数存在する場合には特定のロジックに基づいて選出した一つのサブクラスタの特権ノード候補に特権ノード昇格の了承を、それ以外の特権ノード候補に否決を通知するステップと、を実行し、
前記サブクラスタの特権ノード候補は、
前記外部サーバから了承の通知を受けた場合、特権ノードに昇格してクラスタを構築するステップと、
前記外部サーバから否決の通知を受けた場合、当該サブクラスタを解体するステップと、
を実行することを特徴とするクラスタシステムのSplit-Brain Syndrome発生防止方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散システムにおいて、経路障害等に起因して発生するSplit-Brain Syndromeを防止するクラスタシステムおよびSplit-Brain Syndrome発生防止方法に関する。
【背景技術】
【０００２】
近年、クラウドコンピューティングの隆盛に伴い、多量なデータの処理や管理を効率的に行うことが求められている。そこで、複数のサーバを協調動作させることにより効率的な処理を実現する、分散処理技術が発展している。
分散処理を行う際に、分散システム（以降、クラスタと称す）を構成するサーバ（以降、ノードと呼ぶ）間で協調動作を行う場合がある。例えば、高可用性の求められるシステムにおいては、あるノードに障害が発生した場合にも他のノードで処理を継続できるように複製データを他のノードで保持する（データ冗長化）といった協調動作を行う例が挙げられる。このような協調動作を実施するためには、クラスタを構成するノードの情報（ＩＰアドレス等）をクラスタに参加している全てのノードで把握している必要が生じる。
【０００３】
そこで、クラスタを構成するノードの中から１台を、ノードを管理する特権を持つノード（以降、特権ノードと称す）として選出するノード管理方法が挙げられる。ここで、全ノードは、事前に特権ノードを選出するための同一の規則を知っており、特権ノードに障害が生じた際には残りのノードのうち１台が特権を引き継ぐこととする。このようにクラスタ内に閉じてノード管理を行うことで、特権ノードが単一障害点（ＳＰＯＦ：Single Point of Failure）となることはない。なお、ノード障害発生時には、特権ノード（特権ノードの障害時には次に特権ノードとなるノード）へと通知され、管理されているノードの情報が更新され、残りの全ノードに通知されるものとする。
【０００４】
クラスタシステムにおいて、経路障害等によりクラスタシステムを構成するノード間の通信が切断され、ＮＷ（ネットワーク）分断が発生する可能性がある。ＮＷ分断が発生すると、クラスタが複数のサブクラスタに分離し、かつそれぞれが動作を継続するSplit-Brain Syndromeが発生する可能性がある。
【０００５】
図１６は、Split-Brain Syndromeの発生例およびSplit-Brain Syndromeの解消例を示す図である。
図１６（ａ）に示すように、クラスタを構成するサーバ群であるノードＡ〜Ｅを相互接続して１台のサーバのように動作させるクラスタシステムにおいて、ノードＡ，ＢとノードＣ〜Ｅとを繋ぐ経路が、経路故障したとする。図１６（ｂ）では、ノードＡ，ＢとノードＣ〜Ｅとを繋ぐ経路に、経路故障したことを示す×印が付されている。また、クラスタのノードＡに当該クラスタの特権ノードであることを示す王冠印が付されている。図１６（ｂ）の場合、経路故障によってクラスタを構成するノードＡ，ＢとノードＣ〜Ｅとに分断され、ノードＡ，ＢからはノードＣ〜Ｅが故障したように見え、またノードＣ〜ＥからはノードＡ，Ｂが故障したように見える。
【０００６】
クラスタシステムには、障害が発生した場合もクラスタを動的に再構成してサービスを維持する対障害機構が備わっている。図１６（ｂ）の符号aに示すように、双方のサブクラスタ毎に特権ノード（ここではノードＡとノードＣ）が選出され、サブクラスタがそれぞれ動作を継続するSplit-Brain Syndromeが発生する。図１６（ｂ）では、一方のサブクラスタのノードＡに当該クラスタの特権ノードであることを示す王冠印が付され、他方のサブクラスタのノードＣに当該クラスタの特権ノードであることを示す王冠印が付されている。このような状況がSplit-Brain Syndrome発生の一例である。
【０００７】
Split-Brain Syndromeが発生すると、データの一貫性の破綻やサービスの停止等の問題を招く可能性がある。例えば、クラスタ外からのサービスへのアクセスが不能な状態に陥ったり、複数のノードのデータベースへの書き込みが競合し、データベースを破壊したり一貫性を喪失するなど、さまざまな致命的現象を引き起こす可能性がある。
【０００８】
一方、複数のデータ管理装置の中からマスタ（特権ノード）を１台選定する手法、または、データ管理装置の保持するデータの状態を同じに揃える手法として、分散調停プロトコルがある。分散調停プロトコルとして、例えば、データベースやファイルシステムに用いられるPaxosアルゴリズムが知られている（非特許文献１参照）。
また、非特許文献２には、所定のリース期間であるMaster Leaseについて記載されている。
【０００９】
ＮＷ分断が発生してクラスタが複数のサブクラスタに分割された際、Paxosアルゴリズム等を利用し、元のクラスタの過半数を満たすサブクラスタの特権ノード候補を特権ノードとしてクラスタを構築する。
【００１０】
図１６（ｃ）の符号aに示すように、Paxosアルゴリズムでは、元のクラスタのメンバ数の半数以下の場合は、解体する。図１６（ｃ）の符号ｂに示すように、元のクラスタのメンバ数の過半数を満たす場合は、クラスタを構築する。
このように、Paxosアルゴリズムは、過半数のメンバが残存するサブクラスタを残して他を解体することで、Split-Brain Syndromeを解消する。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Lamport, L. “The part-time parliament,” ACM Transactions on Computer Systems 16, 2 (1998), pp.133-169.
【非特許文献２】Gray, C., Cheriton, D. “Leases: An efficient fault-tolerant mechanism for distributed file cache consistency,” In Proceedings of the 12th ACM Symposium on Operating Systems Principles (1989), pp. 202-210.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、Paxosアルゴリズムを利用したSplit-Brain Syndrome検出・解消方法は、下記の課題があった。
図１７および図１８は、Paxosアルゴリズムを利用したSplit-Brain Syndrome検出・解消方法の課題を説明する図である。
【００１３】
（課題１）
図１７（ａ）に示すように、クラスタを構成するノードＡ〜Ｆを管理する特権ノード（ここではノードＡ）が、クラスタ毎に１台存在している。図１７（ｂ）に示すように、ノードＡ〜ＣとノードＤ〜Ｆとを繋ぐ経路が、経路故障したとする。ノードＡ〜ＣとノードＤ〜Ｆとを繋ぐ経路に、経路故障したことを示す×印が付されている。また、クラスタのノードＡとノードＤとに当該クラスタの特権ノード候補であることを示す王冠印が付されている。
【００１４】
図１７（ｂ）の符号ａに示すように、ＮＷ分断によりクラスタが２つのサブクラスタに分割され、なおかつ、２つのサブクラスタのメンバ数が同数（元のクラスタの半数）であった場合を想定する。
【００１５】
この場合、Paxosアルゴリズムでは、元のクラスタのメンバ数の半数以下の場合に該当し、図１７（ｃ）の符号ａに示すように、元のクラスタのメンバ数の半数より多いサブクラスタが存在しないためすべて解体する。すなわち、ＮＷ分断によりクラスタが２つのサブクラスタに分割され、なおかつ、２つのサブクラスタのメンバ数が同数（元のクラスタの半数）であった場合、運用可能なクラスタ数の確保が可能であるにも関わらず、クラスタ全体が解体される。
【００１６】
（課題２）
図１８（ａ）に示すように、クラスタを構成するノードＡ〜Ｅを管理する特権ノード（ここではノードＡ）が、クラスタ毎に１台存在している。図１８（ｂ）の符号ａに示すように、ノードＡ，ＢとノードＣ〜Ｅとを繋ぐ経路とノードＣとノードＡ，Ｂ，Ｄ，Ｅとを繋ぐ経路とが、分断（複数分断）したとする。複数分断した経路には、経路故障したことを示す×印が付されている。また、クラスタのノードＡとノードＣとノードＤとに当該クラスタの特権ノード候補であることを示す王冠印が付されている。
【００１７】
図１８（ｂ）の符号ａに示すように、ＮＷ分断が複数発生してクラスタが複数に分割され、なおかつ、元のクラスタの過半数が残存するサブクラスタが存在しない場合を想定する。
【００１８】
この場合、Paxosアルゴリズムでは、元のクラスタのメンバ数の半数以下の場合に該当し、図１８（ｃ）の符号ａに示すように、元のクラスタのメンバ数の半数より多いサブクラスタが存在しないためすべて解体する。すなわち、ＮＷ分断が複数発生してクラスタが複数に分割され、なおかつ、元のクラスタの過半数が残存するサブクラスタが存在しない場合、クラスタ全体が解体され、サービスの部分的な継続を行うことができない。
このように、Paxosアルゴリズムを利用したSplit-Brain Syndrome検出・解消方法では、分断されたサブクラスタのメンバ数が同数（元のクラスタの半数）の場合や元のクラスタのメンバ数の半数より多いサブクラスタが存在しない場合は、特権ノードを決めることができず、クラスタ全体が解体される。
【００１９】
このような背景を鑑みて本発明がなされたのであり、本発明は、Split-Brain Syndromeを防止しつつ、特権ノード決定を行う際に、特権ノードが決まらないような状態をできるだけ起こらないようにすることができるクラスタシステムおよびSplit-Brain Syndrome発生防止方法を提供することを課題とする。
【課題を解決するための手段】
【００２０】
前記した課題を解決するため、請求項１に記載の発明は、Paxosアルゴリズムを含む多数決分散合意形成アルゴリズムを適用して、クラスタを構成する複数のノードの中からノードを管理する特権を持つ特権ノードを選出するクラスタシステムであって、前記特権ノードを管理する外部サーバを前記クラスタの外部に備え、前記外部サーバは、前記クラスタが分断された各サブクラスタの特権ノード候補から各サブクラスタのメンバ数の情報を集約し、最もメンバ数の多いサブクラスタ、または、メンバ数が最多かつ等しいサブクラスタが複数存在する場合には特定のロジックに基づいて選出した一つのサブクラスタの特権ノード候補に特権ノード昇格の了承を、それ以外の特権ノード候補に否決を通知する管理部を備え、前記サブクラスタの特権ノード候補は、前記外部サーバから了承の通知を受けた場合、特権ノードに昇格してクラスタを構築し、前記外部サーバから否決の通知を受けた場合、当該サブクラスタを解体することを特徴とする。
【００２１】
また、請求項８に記載の発明は、Paxosアルゴリズムを含む多数決分散合意形成アルゴリズムを適用して、クラスタを構成する複数のノードの中からノードを管理する特権を持つ特権ノードを選出するクラスタシステムのSplit-Brain Syndrome発生防止方法であって、前記特権ノードを管理する外部サーバを前記クラスタの外部に備え、前記外部サーバは、前記クラスタが分断された各サブクラスタの特権ノード候補から各サブクラスタのメンバ数の情報を集約するステップと、最もメンバ数の多いサブクラスタ、または、メンバ数が最多かつ等しいサブクラスタが複数存在する場合には特定のロジックに基づいて選出した一つのサブクラスタの特権ノード候補に特権ノード昇格の了承を、それ以外の特権ノード候補に否決を通知するステップと、を実行し、前記サブクラスタの特権ノード候補は、前記外部サーバから了承の通知を受けた場合、特権ノードに昇格してクラスタを構築するステップと、前記外部サーバから否決の通知を受けた場合、当該サブクラスタを解体するステップと、を実行することを特徴とするクラスタシステムのSplit-Brain Syndrome発生防止方法とした。
【００２２】
このようにすることで、Split-Brain Syndromeを防止しつつ、特権ノード決定を行う際に、特権ノードが決まらないような状態をできるだけ起こらないようにすることができる。例えば、ＮＷ分断が複数発生してクラスタが複数に分割され、なおかつ、元のクラスタの過半数が残存するサブクラスタが存在しない場合、Paxosアルゴリズムでは、クラスタ全体が解体されてしまうが、本発明によれば、過半数を満たすサブクラスタが存在しない場合にも、クラスタの全体の解体を防ぎ、運用を継続することができる。
【００２３】
また、請求項２に記載の発明は、前記サブクラスタの特権ノード候補が、前記外部サーバから了承または否決の応答がなく、かつ当該サブクラスタのメンバ数が過半数を満たす場合、前記多数決分散合意形成アルゴリズムを適用して、特権ノードとして自律的にクラスタを構築することを特徴とする。
【００２４】
このような構成によれば、何らかの障害が原因で外部サーバから「了承／否決」の応答がないとき、サブクラスタのメンバ数が過半数を満たす場合は、外部サーバからの応答を待たずに、Paxosアルゴリズムを含む多数決分散合意形成アルゴリズムを利用して特権ノードが自律的にクラスタを構築することができる。
【００２５】
また、請求項３に記載の発明は、前記サブクラスタの特権ノード候補が、前記外部サーバから了承または否決の応答がなく、かつ当該サブクラスタのメンバ数が過半数を満たさない場合、所定タイムアウト期間経過後に自律的に当該サブクラスタを解体することを特徴とする。
【００２６】
このような構成によれば、何らかの障害が原因で外部サーバから「了承／否決」の応答がなく、サブクラスタのメンバ数が過半数を満たさない場合は外部サーバからの応答タイムアウトで自律的にサブクラスタを解体することができる。よって、他にメンバ数が過半数を満たすサブクラスタが存在するときに、Split-Brain Syndromeを防止できる。
【００２７】
また、請求項４に記載の発明は、前記クラスタの特権ノードが、自身が特権ノードであることを示す特権ノード情報およびクラスタメンバ数を、定期的およびクラスタのメンバ数が変化した時に前記外部サーバへ報告することを特徴とする。
【００２８】
このような構成によれば、外部サーバは、定期的報告を受けて分断前のクラスタ全体のメンバ数を把握し、クラスタのメンバ数が変化した時の報告を受けて現状のクラスタ状態（特権ノード情報、クラスタメンバ数）を把握することができる。
【００２９】
また、請求項５に記載の発明は、前記サブクラスタの特権ノード候補が、当該サブクラスタのメンバ数が、自身が特権ノード候補であることを示す特権ノード候補情報およびサブクラスタメンバ数を含む特権ノード昇格要求を前記外部サーバへ発行することを特徴とする。
【００３０】
このような構成によれば、外部サーバは、特権ノード候補であるノードとそのサブクラスタのサブクラスタメンバ数とを把握することができる。
【００３１】
また、請求項６に記載の発明は、前記外部サーバが、通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計が前記クラスタの総メンバ数の半数に満たない場合、通信可能な特権ノード候補に対し一律に否決を通知することを特徴とする。
【００３２】
このような構成によれば、外部サーバと通信可能な特権ノード候補に対し一律「否決」を通知することで、外部サーバから検知できないところで過半数を満たすサブクラスタが存在し、請求項２に従って自律的に特権ノードが選出される場合にもSplit-Brain Syndromeを確実に防止することができる。
【００３３】
また、請求項７に記載の発明は、前記外部サーバが、通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計が前記クラスタの総メンバ数の半数に満たない場合、保守者端末に特権ノード候補の通知を行うとともに、当該保守者端末から当該特権ノード候補の了承または否決の判断通知を受け、当該判断通知に従って、特権ノード候補に対し了承または否決を通知することを特徴とする。
【００３４】
このような構成によれば、通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計がクラスタの総メンバ数の半数に満たない場合、通信可能な特権ノード候補に対し一律「否決」を通知する場合に比べ、Split-Brain Syndromeを防止しつつ、より適切な運用を継続することができる。
【発明の効果】
【００３５】
本発明によれば、Split-Brain Syndromeを防止しつつ、特権ノード決定を行う際に、特権ノードが決まらないような状態をできるだけ起こらないようにすることができる。
【図面の簡単な説明】
【００３６】
【図１】本実施形態に係る分散システムの構成例を示す図である。
【図２】本実施形態に係るクラスタを構成するノードの機能例を示す図である。
【図３】本実施形態に係るクラスタを構成するノードのノード管理テーブルの一例を示す図である。
【図４】本実施形態に係るクラスタを構成するノードの死活監視テーブルの設定例を示す図である。
【図５】本実施形態に係る外部サーバの機能例を示す図である。
【図６】本実施形態に係るクラスタを含む分散システムの動作を示す図である。
【図７】本実施形態に係るクラスタを含む分散システムの動作を示す図である。
【図８】本実施形態に係るクラスタを含む分散システムの外部サーバに障害が発生した場合の動作を示す図である。
【図９】本実施形態に係るクラスタシステムのクラスタの一部と外部サーバとの間に障害が発生した場合の動作を示す図である。
【図１０】本実施形態に係るクラスタシステムのクラスタの一部と外部サーバとの間に障害が発生した場合の動作を示す図である。
【図１１】本実施形態に係るクラスタシステムの外部サーバを利用したSplit-Brain Syndrome発生防止方法の手順を説明する図である。
【図１２】本実施形態に係るクラスタシステムの特権ノード／特権ノード候補の管理処理を示すフローチャートである。
【図１３】本実施形態に係るクラスタシステムの外部サーバの特権ノード選定機能のメイン処理を示すフローチャートである。
【図１４】本実施形態に係るクラスタシステムの外部サーバの特権ノード選定機能のタイマ処理を示すフローチャートである。
【図１５】本実施形態に係るクラスタシステムの特権ノード選出の流れを説明するシーケンス図である。
【図１６】クラスタシステムのSplit-Brain Syndromeの発生例およびSplit-Brain Syndromeの解消例を示す図である。
【図１７】クラスタシステムのPaxosアルゴリズムを利用したSplit-Brain Syndrome発生防止方法の課題を説明する図である。
【図１８】クラスタシステムのPaxosアルゴリズムを利用したSplit-Brain Syndrome発生防止方法の課題を説明する図である。
【発明を実施するための形態】
【００３７】
以下、図面を参照して本発明を実施するための形態（以下、「本実施形態」という）におけるクラスタシステム等について説明する。
【００３８】
（実施形態）
[分散システムの構成]
図１は、本実施形態に係るクラスタを含む分散システムの構成例を示す図である。
図１に示すように、分散システム１００（クラスタシステム）は、クラスタ１０を構成する複数のノード１と、クラスタ１０の外部に設けられ、特権ノードを管理する外部サーバ２と、ネットワーク２０と、各クライアント３０とを含んで構成される。
【００３９】
ノード１は、クラスタ１０を構成する、コンピュータ等の物理装置である。また、ノード１は、仮想マシン等の論理装置であってもよい。なお、図１では、ノード１は、物理サーバイメージで表している。ノード１は、クライアント３０から送信されるメッセージを受信して処理を実行し、クライアント３０に応答情報（サービス情報）を返信することによって、サービスを提供する機能を有する。
外部サーバ２は、特権ノードを決定するクラスタ１０の外部の管理サーバである。
【００４０】
クラスタ１０を構成するノード１が連携して動作を行うために、ノード１間で一貫性が必要とされるデータ（管理情報）に基づいて、各ノード１は、データの処理および保持を行っている。例えば、一貫性が必要とされるデータ（管理情報）には、クラスタ１０を構成するノード１群の情報等がある。具体的には、一貫性が必要とされるデータ（管理情報）には、各ノード１のノード識別子が記憶されるノード管理テーブル（後記）や、死活を監視（alive monitoring）する対象のノードをリストアップした死活監視テーブル（後記）がある。
【００４１】
クライアント３０は、ユーザがネットワークサービスを享受するために、サービスへのメッセージ（入力情報等）をクラスタ１０に送信したり、クラスタ１０から当該メッセージに対応する応報情報（サービス情報）を受信して表示したりする機能を有する。クライアント３０は、不図示の入出力部、制御部、記憶部等を持っている。
クライアント３０からのメッセージは、ネットワーク２０を介してクラスタ１０を構成する何れかのノード１に送信される。各ノード１は、メッセージ処理を行い、クライアント３０にサービスを提供する。
【００４２】
なお、クライアント３０からノード１へ直接メッセージを送信せず、クライアント３０とノード１の間にロードバランサ等を設置してメッセージをノード１に振り分けてもよい。このロードバランサ（不図示）は、クライアント３０から送信されるメッセージを、単純なラウンドロビン法等により振り分ける機能を有する。
【００４３】
[ノード]
次に、ノード１の機能例について、図２を用いて説明する（適宜、図１参照）。
図２は、ノード１の機能例を示す図である。
図２に示すように、ノード１は、処理部１１、記憶部１２および通信部１３を備える。
処理部１１は、図示しないＣＰＵ（Central Processing Unit）およびメインメモリで構成され、記憶部１２に記憶されているプログラムをメインメモリに展開して、ノード管理部１１１、メッセージ処理部１１２、死活監視部１１３、特権ノード選出部１１４、およびクラスタ離脱指示部１１５を機能として実現する。
【００４４】
記憶部１２は、メモリやハードディスク等で構成され、ノード管理テーブル（ノード管理情報）１２１、死活監視テーブル（死活監視情報）１２２およびデータ記憶部１２３を有する。データ記憶部１２３は、ノード１が管理するデータ等、およびPaxosアルゴリズムの提案番号ｂ，提案内容Ｖを記憶する（詳細は後記）。
通信部１３は、メッセージや応答情報を送受信するための通信インタフェースである。
【００４５】
<ノード管理部１１１>
ノード管理部１１１は、クラスタ１０へのノード１の追加や離脱が発生した際に、クラスタ１０を構成するノード１の情報を更新し、ノード管理テーブル１２１として管理する。ここで、「ノードの情報の更新」とは、自身が特権ノードの場合には、死活監視部１１３から通知されるノード１の障害情報（後述）や追加ノード１からのノード参加情報等に基づき、ノード管理テーブル１２１（図３参照）を更新し、その情報を残りの全ノード１に配信することを指す。また、自身が特権ノード以外のノード１の場合には、特権ノードから配信されるノード１の更新情報をノード管理テーブル１２１に反映することを指す。
ノード情報には、各ノード１の少なくともクラスタ１０を構成するノード１を一意に識別するもの（例えば、クラスタ１０を構成するノード１が同一サブネット内であればＩＰ（Internet Protocol）アドレス）と必要に応じて付属情報（例えば、クラスタ参加時刻等）が含まれる。
【００４６】
<ノード管理テーブル１２１>
次に、ノード管理テーブル１２１の一例について、図３を用いて説明する（適宜、図２参照）。
図３は、ノード管理テーブル１２１の一例を示す図である。
ノード管理テーブル１２１は、記憶部１２に記憶され、ＩＰアドレス（ノード識別子）１３１および必要に応じて付属情報としてクラスタ参加時刻１３２を関連付けて記憶している。
【００４７】
ＩＰアドレス１３１は、ノード１を識別するように付与されるものであって、例えばコンシステントハッシュ（Consistent Hashing）法の管理（振り分け）手法で用いるＩＤ空間のＩＤまたは仮想ＩＤと一意に対応しているものであってもよい。
クラスタ参加時刻１３２は、ノード１のクラスタ参加時刻を記憶する。
【００４８】
<メッセージ処理部１１２>
図２に戻って、メッセージ処理部１１２は、受信したメッセージの処理を実行し処理結果をクライアントに返すことにより、サービスを提供する。この時、上述の例で示したように他のノード１に複製データを配置するようなシステムでは、ノード管理テーブル１２１を参照して事前に設定された規則（例えば、ノード管理テーブル１２１の自身の下の行のノード）に基づき複製先を特定し、データの複製を配置するような協調動作を行うこともある。
【００４９】
<死活監視部１１３>
死活監視部１１３は、死活監視テーブル１２２を参照して、指定されたノード（例えば、自身の次の行のノード）と常に死活監視信号のやり取りを行い、クラスタ１０を構成するノード１の障害を検出する。ノード１の障害を検出した場合、死活監視部１１３は、自身が特権ノードの場合はノード管理部１１１に、自身が特権ノード以外の場合には特権ノードに通知を行う。死活監視部１１３は、クラスタ１０を構成するノード１の追加や離脱があった場合、ノード管理テーブル１２１の更新に同期して死活監視テーブル１２２を更新する。
【００５０】
<特権ノード選出部１１４>
特権ノード選出部１１４は、アルゴリズムが完結するまでの一連の流れでのみ１つの提案で合意が取れることを保証する多数決プロトコルであるPaxosアルゴリズムを適用して、特権ノードを選出する。
【００５１】
特権ノード選出部１１４は、死活監視部１１３と連動して、すなわち、死活監視部１１３からのトリガにより連動して起動する。特権ノード選出部１１４は、死活監視部１１３によりあるメンバ（ノード）に障害が発生していることが分かったらその段階で動作を開始することになる。特権ノード選出部１１４は、ノード管理テーブル１２１を更新するために、一回Paxosアルゴリズムを実行することにより、死活監視部１１３により発見（検出）された情報と連動させる。なお、特権ノード選出部１１４は、死活監視部１１３と連動して動くものであればよく、死活監視部１１３に含まれる構成でもよい。Paxosアルゴリズムを用いた特権ノード選出部１１４の具体的な処理については後記する。
【００５２】
≪特権ノード≫
ここで、特権ノードについて説明する。
特権ノードは、所定の規則に則り、一意に決定される。具体的には、特権ノードは、ノード管理テーブル１２１または死活監視テーブル１２２内の一番上の行のノードから順に、若しくはクラスタ参加時刻が最も古いノードから順にといった規則に従い、一意に決定される。同様に、次に特権ノードとなるノード候補についても、上記所定の規則に則り、一意に決定される。
【００５３】
例えば、特権ノードに障害が発生した際には、テーブル内の二行目のノード、または、クラスタ参加時刻が二番目に古いノード、というように次の候補が新しい特権ノードとなる権利を持つ。全メンバ（ノード）は、同一の死活監視テーブル１２２やノード管理テーブル１２１を持つため、次の特権メンバ候補は一意に特定することができる。
【００５４】
<死活監視テーブル１２２>
次に、死活監視テーブル１２２の設定例について、図４を用いて説明する。
図４は、死活監視テーブル１２２の設定例を示す図である。
死活監視テーブル１２２は、１台の物理装置を単位として作成され、監視対象のノードをリストアップしたものである。死活監視テーブル１２２は、監視対象のノードのＩＰアドレスを記憶している。
死活監視テーブル１２２は、論理装置単位でノードが構成されるパターンを考慮して、物理メンバ単位に少なくとも１回選択されるようにする。すなわち、物理メンバ単位に少なくとも１回は選択されることで、死活監視がされていないメンバ（ノード）は存在しないようにしている。
【００５５】
また、死活監視テーブル１２２は、クラスタ１０（図１参照）を構成するノード１の追加や離脱があった場合、ノード管理テーブル１２１と同期的に更新されるものとする。ここで、例えば、ノード管理テーブル１２１には登録されているが死活監視テーブル１２２には登録されていないメンバ（ノード）があると、当該ノードは監視されないことになる。この状態を避けるため、ノード等の変更によりノード管理テーブル１２１が更新されると、必ず死活監視テーブル１２２についても更新されるように同期を取っている。
【００５６】
なお、ノード管理テーブル１２１と死活監視テーブル１２２とは、異なるものを用いてもよい場合がある。例えば、１台のサーバに対して仮想的にいくつものＩＤがあるような場合には、同じノードに対して複数のノードから監視を行うことになるので、この場合には物理ノードだけを抜き出したような死活監視テーブル１２２を用意しておくことが好ましい。
【００５７】
<クラスタ離脱指示部１１５>
クラスタ離脱指示部１１５は、特権ノード選出部１１４によるPaxosアルゴリズムを用いた特権ノード選出処理において、２回連続で提案がRejectされた場合、または過半数から応答を集められなかった場合、Split-Brain Syndromeが発生したと判定する。
クラスタ離脱指示部１１５は、２回連続で自身が特権ノードである旨の提案がRejectされた場合、または過半数から応答を集められなかった場合、自身の所属するクラスタ１０の全ノードに対し、クラスタ１０からの離脱指示を行い、クラスタ１０からの離脱指示を受け取ったノードは当該クラスタ１０から離脱することで、Split-Brain Syndromeを解消させる。なお、上記において、分断した他方のクラスタには指示が届かないため、あくまでも分断した一クラスタに対する離脱指示である。
【００５８】
また、クラスタ離脱指示部１１５は、Split-Brain Syndromeの発生を検出した場合、Split-brain Syndromeが発生したことを示す警報情報をアラームとして出力するものでもよい。この警報情報により、Split-Brain Syndromeの発生を管理者に気付かせることができる。
【００５９】
[外部サーバ]
次に、外部サーバ２の機能例について、図５を用いて説明する。
図５は、外部サーバ２の機能例を示す図である。
図５に示すように、外部サーバ２は、管理部２１、記憶部２２および通信部２３を備える。
管理部２１は、図示しないＣＰＵおよびメインメモリで構成され、記憶部２２に記憶されているプログラムをメインメモリに展開して、各サブクラスタの特権ノード候補／特権ノードを管理する。管理部２１は、分断されたサブクラスタのメンバ数が過半数に満たないという、限られた場面において、サブクラスタのメンバ数の最も多いサブクラスタの特権ノード候補を、特権ノードにさせるものである。
【００６０】
管理部２１は、クラスタ１０（図１参照）が分断された各サブクラスタの特権ノード候補から各サブクラスタのメンバ数の情報を集約し、記憶部２２に格納する。管理部２１は、この集計結果に基づいて、最もメンバ数の多いサブクラスタ、または、メンバ数が最多かつ等しいサブクラスタが複数存在する場合には特定のロジックに基づいて選出した一つのサブクラスタの特権ノード候補に特権ノード昇格の「了承」を通信部２３により通知し、それ以外の特権ノード候補に「否決」を通知する。
【００６１】
管理部２１は、外部サーバ２と通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計がクラスタ１０の総メンバ数の半数に満たない場合、外部サーバ２と通信可能な特権ノード候補に対し一律に「否決」を通信部２３により通知する。
【００６２】
管理部２１は、外部サーバ２と通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計がクラスタ１０の総メンバ数の半数に満たない場合、通信部２３を介して保守者に特権ノード候補の通知を行うとともに、当該保守者から当該特権ノード候補の「了承／否決」の判断通知を受ける。
【００６３】
記憶部２２は、メモリやハードディスク等で構成され、各サブクラスタの特権ノード候補から各サブクラスタのメンバ数の情報の集約結果を記憶する。また、記憶部２２は、各サブクラスタの特権ノード候補から報告されたクラスタ状態（特権ノード情報、クラスタメンバ数）、および特権ノード候補から発行された特権ノード昇格要求（特権ノード候補情報、サブクラスタメンバ数）を記憶する。
通信部２３は、各サブクラスタの特権ノード候補／特権ノードとの間で報告や応答情報を送受信するための通信インタフェースである。
【００６４】
以下、上述のように構成されたクラスタシステムの動作について説明する。
（原理説明）
本発明は、サブクラスタのメンバ数が過半数に満たないという、限られた場面において、クラスタの外部に設置した外部サーバが、サブクラスタのメンバ数の最も多いサブクラスタの特権ノード候補を特権ノードとして「了承」し、他のサブクラスタの特権ノード候補を「否決」して当該サブクラスタを解体させるものである。また、本発明は、外部サーバを利用したSplit-Brain Syndrome発生防止方法である。
【００６５】
本発明は、自律的にクラスタを構築できるというPaxosアルゴリズムの長所は最大限に活かしつつ、Paxosアルゴリズムではクラスタ解体となるところは外部サーバの助けをかりることで、クラスタの全体の解体を防ぎ、運用を継続する仕組みを提供するものである。
以下、その特徴について記述する。
【００６６】
（１）Paxosアルゴリズム等の多数決分散合意形成アルゴリズムを利用することで、クラスタ内部で自律的にSplit-Brain Syndromeを検出・解消するクラスタシステムである。
（２）クラスタの特権ノードを管理する外部サーバ２をクラスタ外部に設ける。外部サーバ２は、各サブクラスタの特権ノード候補から各サブクラスタのメンバ数の情報を集約する。
（３）外部サーバ２は、当該集約の結果、最もメンバ数の多いサブクラスタ、もしくは、メンバ数が最多かつ等しいサブクラスタが複数存在する場合には特定のロジックに基づいて選出した一つのサブクラスタの特権ノード候補に特権ノード昇格の「了承」を、それ以外の特権ノード候補に「否決」を通知する。
（４）了承の通知を受けた特権ノード候補が特権ノードに昇格する。これにより、過半数を満たすサブクラスタが存在しない場合にも、クラスタの全体の解体を防ぎ、運用を継続することができる。
【００６７】
[外部サーバ２を利用したSplit-Brain Syndrome検出方法の基本動作]
まず、外部サーバ２を利用したSplit-Brain Syndrome検出方法の基本動作について説明する。
分散システム１００は、クラスタ１０を構成するノード１を管理する特権ノードが、クラスタ毎に１台存在するクラスタシステムを前提とする。
分散システム１００は、Paxosアルゴリズムを含む多数決分散合意形成アルゴリズムを適用して、クラスタ１０を構成する複数のノードの中からノードを管理する特権を持つ特権ノードを選出する。
本実施形態では、クラスタごとに１台、特権ノード（代表ノード）を存在させ、いずれかのノードの離脱を契機に特権ノードを再選出するPaxosアルゴリズム（非特許文献１参照）を導入する。
【００６８】
（動作例１）
図６は、本実施形態に係るクラスタを含む分散システムの動作を示す図である。図１７の（課題１）に対応する動作例である。
図６のケースは、クラスタ１０（メンバ総数：１２）にＮＷ分断が発生してクラスタ１０が２つのサブクラスタ（サブクラスタＡ（メンバ総数：６）とサブクラスタＢ（メンバ総数：６））に分割された場合である。なお、クラスタ１０を構成するノード１は「○（白丸）」で表され、また後記するように特権ノード候補は「◎（二重丸）」で表されている。
【００６９】
このような場合、従来のPaxosアルゴリズム等の多数決分散合意形成アルゴリズムでは、ＮＷ分断により分割されたサブクラスタＡ（メンバ総数：６）とサブクラスタＢ（メンバ総数：６）のメンバ数が同数（元のクラスタの半数）であるので、運用可能なクラスタ数の確保が可能であるにも関わらず、クラスタ全体が解体されていた。
【００７０】
本実施形態では、クラスタの特権ノードを管理する外部サーバ２をクラスタ外部に設ける。外部サーバ２は、各サブクラスタＡ，Ｂの特権ノード候補「１」，「２」（◎（二重丸））から各サブクラスタＡ，Ｂのメンバ数の情報の報告を受信し、各サブクラスタＡ，Ｂのメンバ数の情報を集約する。外部サーバ２は、最もメンバ数の多いサブクラスタ、もしくは、メンバ数が最多かつ等しいサブクラスタが複数存在する場合には特定のロジックに基づいて選出した一つのサブクラスタ（この場合、サブクラスタＡ）の特権ノード候補「１」（◎（二重丸））に特権ノード昇格の「了承」を、それ以外（この場合、サブクラスタＢ）の特権ノード候補「２」（◎（二重丸））に「否決」を通知する。なお、特定のロジックは、どのようなものでもよく、例えばノードＩＤの新しいものを選ぶ態様でもよい。
【００７１】
また、外部サーバ２は、図６の符号ａに示すように、メンバ数が最多かつ等しいサブクラスタが複数存在する場合にも、特定のロジックに基づいて特権ノード候補の中から特権ノードを一つに選定する。
「了承」の通知を受けたサブクラスタＡの特権ノード候補「１」（◎（二重丸））が特権ノードに昇格することで、過半数を満たすサブクラスタが存在しない場合にも、クラスタの全体の解体を防ぎ、運用を継続することができる。
【００７２】
（動作例２）
図７は、本実施形態に係るクラスタを含む分散システムの動作を示す図である。図１８の（課題２）に対応する動作例である。
図７のケースは、クラスタ１０（メンバ総数：１２）にＮＷ分断が発生してクラスタ１０が３つのサブクラスタ（サブクラスタＡ（メンバ総数：３）とサブクラスタＢ（メンバ総数：５）とサブクラスタＣ（メンバ総数：４））に分割され、いずれのサブクラスタも元のクラスタの過半数となっていない場合である。
【００７３】
このような場合、従来のPaxosアルゴリズム等の多数決分散合意形成アルゴリズムでは、ＮＷ分断が複数発生してクラスタが複数に分割され、なおかつ、元のクラスタの過半数が残存するサブクラスタが存在しない、すなわち元のクラスタのメンバ数の半数より多いサブクラスタが存在しないので、すべて解体されていた。
【００７４】
本実施形態では、ＮＷ分断が発生した場合、各サブクラスタＡ，Ｂ，Ｃの特権ノード候補「１」〜「３」（◎（二重丸））は、外部サーバ２に対して自分のサブクラスタのメンバ数を報告する。外部サーバ２は、各サブクラスタＡ，Ｂ，Ｃの特権ノード候補「１」〜「３」（◎（二重丸））から各サブクラスタＡ，Ｂ，Ｃのメンバ数の情報の報告を受信し、各サブクラスタＡ，Ｂ，Ｃのメンバ数の情報を集約する。外部サーバ２は、最もメンバ数の多いサブクラスタ、もしくは、メンバ数が最多かつ等しいサブクラスタが複数存在する場合には特定のロジックに基づいて選出した一つのサブクラスタ（この場合、サブクラスタＢ）の特権ノード候補「２」（◎（二重丸））に特権ノード昇格の「了承」を、それ以外（この場合、サブクラスタＡ，Ｃ）の特権ノード候補「１」，「３」（◎（二重丸））に「否決」を通知する。
【００７５】
このように、外部サーバ２は、図７の符号ａに示すように、外部サーバ２は、最もメンバ数の多いサブクラスタの特権ノード候補に対して「了承」、その他の特権ノード候補に対して「否決」を応答する。
【００７６】
「了承」の通知を受けたサブクラスタＢの特権ノード候補「２」（◎（二重丸））が特権ノードに昇格し、クラスタを構築するとともに、「否決」の通知を受けたサブクラスタＡ，Ｃの特権ノード候補「１」，「３」（◎（二重丸））はクラスタを解体する。これにより、ＮＷ分断が複数発生してクラスタが複数に分割され、なおかつ、元のクラスタの過半数が残存するサブクラスタが存在しない場合にも、クラスタの全体の解体を防ぎ、運用を継続することができる。
【００７７】
[外部サーバ２に障害が発生した場合の動作]
次に、外部サーバ２に障害が発生した場合の動作について説明する。
図８は、本実施形態に係るクラスタを含む分散システムの外部サーバ２に障害が発生した場合の動作を示す図である。
本実施形態では、何らかの障害が原因で外部サーバ２から「了承／否決」の応答がないとき、サブクラスタのメンバ数が過半数を満たす場合は外部サーバ２からの応答を待たずに特権ノードが自律的にクラスタを構築し、かつ、サブクラスタのメンバ数が過半数を満たさない場合は外部サーバ２からの応答タイムアウトで自律的にサブクラスタを解体する。
【００７８】
図８のケースでは、クラスタ１０（メンバ総数：１２）にＮＷ分断が発生してクラスタ１０が３つのサブクラスタ（サブクラスタＡ（メンバ総数：３）とサブクラスタＢ（メンバ総数：７）とサブクラスタＣ（メンバ総数：２））に分割された場合を想定する。この場合、図８の破線矢印に示すように、各サブクラスタＡ，Ｂ，Ｃの特権ノード候補「１」〜「３」（◎（二重丸））は、外部サーバ２に対して、各サブクラスタＡ，Ｂ，Ｃのメンバ数の情報の報告を送信する。しかしながら、外部サーバ２に障害が発生している場合、外部サーバ２は、各サブクラスタＡ，Ｂ，Ｃのメンバ数の情報を集約できない、または該当する特権ノード候補（◎（二重丸））に特権ノード昇格の「了承」を、それ以外の特権ノード候補（◎（二重丸））に「否決」を通知することができない。
【００７９】
図８のケースでは、サブクラスタＢの特権ノード候補「２」（◎（二重丸））については、Paxosアルゴリズム（非特許文献１参照）によって、過半数を満たすサブクラスタの特権ノード候補は自律的に特権ノードへ昇格する。しかし、サブクラスタＡ，Ｃの特権ノード候補「１」，「３」（◎（二重丸））ついても、外部サーバ２に対して特権ノードへの昇格要求を発行して、外部サーバ２からの特権ノード昇格の「了承」または「否決」の応答を待っている。ここでは、外部サーバ２に障害が発生（外部サーバ２自体の障害または通信経路の障害のいずれも含む）していると想定しているので、サブクラスタＡ，Ｃの特権ノード候補「１」，「３」（◎（二重丸））に外部サーバ２から「了承／否決」の応答が通知されることはない。
【００８０】
そこで、図８の符号ａに示すように、各サブクラスタＡ，Ｂ，Ｃの特権ノード候補「１」〜「３」（◎（二重丸））は、外部サーバ２に対して昇格要求送信後、タイマを起動し、外部サーバ２から「否決」の応答がない場合、過半数を満たさないサブクラスタの特権ノード候補「１」，「３」（◎（二重丸））は、前記タイマの応答タイムアウトでクラスタを解体する。
また、図８の符号ｂに示すように、外部サーバ２から「了承」の応答がない場合でも、過半数を満たすサブクラスタの特権ノード候補「２」（◎（二重丸））は、前記タイマの応答タイムアウトで特権ノードへ昇格する。
【００８１】
このように、外部サーバ２に対して昇格要求送信後、タイマを起動し、外部サーバ２から了承／否決の応答がないときであっても、サブクラスタのメンバ数が過半数を満たす場合は外部サーバ２からの応答を待たずに特権ノードが自律的にクラスタを構築し、かつ、サブクラスタのメンバ数が過半数を満たさない場合は外部サーバ２からの応答タイムアウトで自律的にサブクラスタを解体する。
【００８２】
[クラスタの一部と外部サーバ２との間に障害が発生した場合の動作（その１）]
次に、クラスタの一部と外部サーバ２との間に障害が発生した場合の動作について説明する。
図９は、本実施形態に係るクラスタシステムのクラスタの一部と外部サーバ２との間に障害が発生した場合の動作を示す図である。
本実施形態では、クラスタの一部と外部サーバ２との間に部分的な障害が発生したとき、外部サーバ２と通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計がクラスタの総メンバ数の半数に満たない場合、外部サーバ２から検知できないところで特権ノードが選出される可能性を考慮し、外部サーバ２は通信可能な特権ノード候補に対し一律「否決」を通知する。以下、具体的に説明する。
【００８３】
図９のケースでは、クラスタ１０（メンバ総数：１２）にＮＷ分断が発生してクラスタ１０が３つのサブクラスタ（サブクラスタＡ（メンバ総数：３）とサブクラスタＢ（メンバ総数：７）とサブクラスタＣ（メンバ総数：２））に分割された場合を想定する。この場合、図９の破線および実線矢印に示すように、クラスタの一部（ここではサブクラスタＢ，Ｃ）と外部サーバ２に障害が発生している場合、クラスタの一部（ここではサブクラスタＢ，Ｃ）は外部サーバ２に対してサブクラスタＢ，Ｃのメンバ数の情報の報告を送信することができない。この場合の外部サーバ２と通信可能な全特権ノード候補は、サブクラスタＡの特権ノード候補「１」（◎（二重丸））（メンバ数：３）である。したがって、外部サーバ２は、各サブクラスタＢ，Ｃのメンバ数の情報を集約できない、または該当する特権ノード候補（◎（二重丸））に特権ノード昇格の「了承」を、それ以外の特権ノード候補（◎（二重丸））に「否決」を通知することができない。
【００８４】
図９の符号ａに示すように、外部サーバ２は、自身からクラスタメンバの半数以上の状態が見えない（サブクラスタＡの特権ノード候補「１」（◎（二重丸））（メンバ数：３）のみが見えている）状態である。
【００８５】
一方、図９の符号ｂに示すように、特権ノード候補「２」（◎（二重丸））は、過半数を満たすため、Paxosアルゴリズム等の多数決分散合意形成アルゴリズムによって、外部サーバ２からの応答がなくても特権ノードに自律的に昇格してクラスタを構築する。
【００８６】
したがって、図９のケースでは、特権ノード候補「２」（◎（二重丸））は、外部サーバ２からの応答がなくても特権ノードに昇格してクラスタを構築する一方、外部サーバ２から見えるクラスタは、サブクラスタＡの特権ノード候補「１」（◎（二重丸））（メンバ数：３）のみである。外部サーバ２が、このサブクラスタＡの特権ノード候補「１」（◎（二重丸））に特権ノード昇格の「了承」を通知してしまうと、サブクラスタＡ，Ｂがそれぞれ動作を継続するSplit-Brain Syndromeが発生するおそれがある。このような不具合は、クラスタの一部と外部サーバ２との間に障害が発生した場合に起こり得る。
【００８７】
そこで、図９の符号ａに示すように、外部サーバ２は、自身からクラスタメンバの半数以上の状態が見えない場合、一律「否決」を通知する。すなわち、外部サーバ２は、外部サーバ２と通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計がクラスタの総メンバ数の半数に満たない場合、直ちに「否決」を通知する。
【００８８】
このように、クラスタの一部と外部サーバ２との間に部分的な障害が発生したとき、外部サーバ２と通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計がクラスタの総メンバ数の半数に満たない場合、外部サーバ２から検知できないところで特権ノードが選出される可能性を考慮し、外部サーバ２は通信可能な特権ノード候補に対し一律「否決」を通知する。これにより、クラスタの一部と外部サーバ２との間に障害が発生した場合であってもSplit-Brain Syndromeを防止することができる。
【００８９】
[クラスタの一部と外部サーバ２との間に障害が発生した場合の動作（その２）]
次に、クラスタの一部と外部サーバ２との間に障害が発生した場合の動作について説明する。
図１０は、本実施形態に係るクラスタシステムのクラスタの一部と外部サーバ２との間に障害が発生した場合の動作を示す図である。
本実施形態では、クラスタの一部と外部サーバ２との間に部分的な障害が発生したとき、外部サーバ２と通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計がクラスタの総メンバ数の半数に満たない場合、外部サーバ２から検知できないところで特権ノードが選出される可能性を考慮し、外部サーバ２は保守者（保守者端末）に特権ノード候補の通知を行い、「了承／否決」の判断を保守者が行う。
【００９０】
図１０のケースでは、図９のケースと同様に、クラスタ１０（メンバ総数：１２）にＮＷ分断が発生してクラスタ１０が３つのサブクラスタ（サブクラスタＡ（メンバ総数：３）とサブクラスタＢ（メンバ総数：７）とサブクラスタＣ（メンバ総数：２））に分割された場合を想定する。この場合、図１０の破線および実線矢印に示すように、クラスタの一部（ここではサブクラスタＢ，Ｃ）と外部サーバ２に障害が発生している場合、クラスタの一部（ここではサブクラスタＢ，Ｃ）は外部サーバ２に対してサブクラスタＢ，Ｃのメンバ数の情報の報告を送信することができない。また、外部サーバ２は、各サブクラスタＢ，Ｃのメンバ数の情報を集約できない、または該当する特権ノード候補（◎（二重丸））に特権ノード昇格の「了承」を、それ以外の特権ノード候補（◎（二重丸））に「否決」を通知することができない。
【００９１】
そこで、図１０の符号ａに示すように、外部サーバ２は、自身からクラスタメンバの半数以上の状態が見えないため、保守者（保守者端末）へ特権ノード候補の通知を行い、保守者が特権ノードを判断する。前記図９の場合は、外部サーバ２は、自身からクラスタメンバの半数以上の状態が見えないため、一律「否決」を通知していたが、図１０の場合は、外部サーバ２は、外部サーバ２は保守者（保守者端末）に特権ノード候補の通知を行い、保守者（保守者端末）から「否決／可決」の判断を受けて、該当特権ノード候補「１」（◎（二重丸））に「了承／否決」を通知する。
また、図１０の符号ｂに示すように、特権ノード候補「２」（◎（二重丸））は、過半数を満たすため、外部サーバ２からの応答がなくても特権ノードに昇格する。
【００９２】
このように、クラスタの一部と外部サーバ２との間に部分的な障害が発生したとき、外部サーバ２と通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計がクラスタの総メンバ数の半数に満たない場合、外部サーバ２から検知できないところで特権ノードが選出される可能性を考慮し、外部サーバ２は保守者（保守者端末）に最適な特権ノード候補の通知を行い、「了承／否決」の判断を保守者（保守者端末）が介在して行う。
【００９３】
これにより、クラスタの一部と外部サーバ２との間に障害が発生した場合であってもSplit-Brain Syndromeを防止することができる。また、図９のように一律「否決」を通知する場合に比べ、より適切な運用を継続することができる。例えば、図１０のケースにおいて、サブクラスタＢ（メンバ総数：１２）がさらに２つに分断（クラスタ１０が４つに分断）されたような場合、図９の例では、一律「否決」により、全てのサブクラスタが解体されるが、「了承／否決」の判断を保守者（保守者端末）が介在して行うことで、分断されたサブクラスタＢのうち一部のサブクラスタについては、クラスタを構築させることが可能となる。
【００９４】
[外部サーバ２を利用したSplit-Brain Syndrome発生防止方法の手順]
次に、外部サーバ２を利用したSplit-Brain Syndrome発生防止方法の手順について説明する。
図１１は、本実施形態に係るクラスタシステムの外部サーバ２を利用したSplit-Brain Syndrome発生防止方法の手順を説明する図である。図１１（ａ）は特権ノード候補の選定（手順１）、図１１（ｂ）は外部サーバ２への報告および回答（手順２，３）、図１１（ｃ）はクラスタの構築・解体（手順４）を示す。
【００９５】
（手順１）：特権ノード候補の選定（図１１（ａ）参照）
手順１では、クラスタの分断された箇所（サブクラスタ）毎に特権ノード候補を選定する。
図１１（ａ）に示すように、クラスタ１０（メンバ総数：１３）にＮＷ分断が発生してクラスタ１０が３つのサブクラスタ（サブクラスタＡ（メンバ総数：６）とサブクラスタＢ（メンバ総数：３）とサブクラスタＣ（メンバ総数：４））に分割されている。この場合、各サブクラスタＡ，Ｂ，Ｃ毎に特権ノード候補「１」〜「３」（◎（二重丸））を選定する。
【００９６】
（手順２）：外部サーバ２への報告（図１１（ｂ）参照）
手順２では、特権ノード候補は、下記手順（２−Ａ）または手順（２−Ｂ）を実行する。
【００９７】
（２−Ａ）  サブクラスタのメンバ数が、分断前のクラスタ全体のメンバ数の過半数を満たす場合、特権ノード（注：「特権ノード候補」ではない。）としてクラスタ状態（特権ノード情報、クラスタメンバ数）を外部サーバ２へ報告する。なお、図１１は、この（２−Ａ）のケースには該当しない。
【００９８】
（２−Ｂ）  図１１（ｂ）に示すように、サブクラスタのメンバ数が、分断前のクラスタ全体のメンバ数の半数以下の場合、特権ノード候補として、特権ノード昇格要求（特権ノード候補情報、サブクラスタメンバ数）を外部サーバ２へ発行（報告）する。図１１（ｂ）の場合、サブクラスタＡ，Ｂ，Ｃのメンバ数が、分断前のクラスタ全体のメンバ数の半数以下であるので、特権ノード候補（◎（二重丸））として、特権ノード昇格要求（特権ノード候補情報、サブクラスタメンバ数）を外部サーバ２へ発行する。
【００９９】
（手順３）：外部サーバ２からの回答（図１１（ｂ）参照）
手順３では、上記手順（２−Ａ）の「報告」がある場合とない場合、さらにこの「報告」がない場合でメンバ数に応じて、外部サーバ２は、以下の各手順のいずれかを実行する。
【０１００】
（３−Ａ）  外部サーバ２は、上記手順（２−Ａ）の「報告」がある場合、それ以外の特権ノード候補からの昇格要求に対し「否決」を通知する。
【０１０１】
（３−Ｂ）  外部サーバ２は、上記手順（２−Ａ）の「報告」がなく、かつ、クラスタメンバの半数以上の状態が外部サーバ２からタイムアウト期間（Ｔ２）中に見える場合、特権ノード昇格要求を集約し、サブクラスタメンバ数の最も多いサブクラスタの特権ノード候補に対し「了承」を、それ以外の特権ノード候補に対し「否決」を通知する。メンバ数が最多かつ同数のサブクラスタが存在する場合にも所定ロジックに基づき、一つの特権ノード候補のみに「了承」を通知する。図１１（ｂ）の場合、外部サーバ２は、サブクラスタメンバ数の最も多いサブクラスタＡの特権ノード候補「１」（◎（二重丸））に対し「了承」を、それ以外の特権ノード候補「２」，「３」（◎（二重丸））に対し「否決」を通知する。なお、上記タイムアウト期間（Ｔ２）とは、外部サーバ２が、サブクラスタの特権ノード候補からの報告を待つ一定期間である。
【０１０２】
（３−Ｃ）  外部サーバ２は、上記手順（２−Ａ）の「報告」がなく、かつ、クラスタメンバの半数以上の状態が外部サーバ２からタイムアウト期間（Ｔ２）中に見えない場合、下記手順（３−Ｃ−１）または手順（３−Ｃ−２）を実行する。手順（３−Ｃ−１）では、外部サーバ２は、外部サーバ２から見えるすべての特権ノード候補に対し「否決」を通知する（図９参照）。手順（３−Ｃ−２）では、外部サーバ２は、保守者（保守者端末）に通知し、保守者介在で「了承／否決」を通知する（図１０参照）。
【０１０３】
（手順４）：クラスタの構築・解体（図１１（ｃ）参照）
手順４では、特権ノード候補は、下記手順（４−Ａ）、手順（４−Ｂ）または手順（４−Ｃ）を実行する。
【０１０４】
（４−Ａ）  特権ノード候補は、外部サーバ２から「了承」通知を受信した場合、図１１（ｃ）の○印に示すように、サブクラスタＡの特権ノード候補１を特権ノード「★（星印）」に昇格し、クラスタを構築する。
【０１０５】
（４−Ｂ）  特権ノード候補は、外部サーバ２から「否決」通知を受信した場合、図１１（ｃ）の×印に示すように、クラスタ（ここではサブクラスタＢ，Ｃ）を解体する。
【０１０６】
（４−Ｃ）  特権ノード候補は、外部サーバ２から、一定期間（タイムアウトＴ１）通知がない場合、図１１（ｃ）の×印に示すように、クラスタを解体する。
【０１０７】
次に、特権ノード／特権ノード候補および外部サーバ２の管理処理について説明する。まず、特権ノード／特権ノード候補の管理処理について述べる。
【０１０８】
[特権ノード／特権ノード候補の管理処理]
図１２は、本実施形態に係るクラスタシステムの特権ノード／特権ノード候補の管理処理を示すフローチャートであり、図１１（ｃ）の（手順４）に対応する。
本フローは、メンバ数変動をイベント（契機）にスタートする。ステップＳ１１において、特権ノード選出部１１４は、特権ノード候補の認識しているクラスタメンバ数（メンバ数ｍ）を集約する。このクラスタメンバ数（メンバ数ｍ）の集約は、後記図１５のPaxosアルゴリズム（非特許文献１参照）の第一フェーズ（Prepare phase）において、応答を返信してきたAcceptor（受理ノード）の数を集計することにより行う。
【０１０９】
ステップＳ１２において、特権ノード選出部１１４は、特権ノード候補の認識しているメンバ数ｍがＮＷ分断前のクラスタの全メンバ数Ｎ／２より大きい（ｍ＞Ｎ／２）か否かを判別する。
ｍ＞Ｎ／２の場合、ステップＳ１３で特権ノード選出部１１４は、特権ノードへ昇格し、クラスタを構築し、クラスタの特権ノードは、クラスタ状態（特権ノード情報、クラスタメンバ数）を定期的およびクラスタのメンバ数が変化した時に外部サーバ２へ報告して本フローを終了する。
ｍ≦Ｎ／２の場合、ステップＳ１４で特権ノード選出部１１４は、特権ノード候補として、特権ノード昇格要求（特権ノード候補情報、クラスタメンバ数）を外部サーバ２へ送信（発行）する。
【０１１０】
次いで、ステップＳ１５で特権ノード選出部１１４は、外部サーバ２から通知があるか否かを判別する。
上記ステップＳ１５で外部サーバ２から「了承」を受信した場合、ステップＳ１３に進む。上記したように、ステップＳ１３で特権ノード選出部１１４は、特権ノードへ昇格し、クラスタを構築し、クラスタ状態（特権ノード情報、クラスタメンバ数）を外部サーバ２へ報告する。
上記ステップＳ１５で外部サーバ２から「否決」を受信した場合、または外部サーバ２からの返答がない（タイムアウトＴ１）場合、ステップＳ１６で特権ノード選出部１１４は、クラスタを解体して本フローを終了する。
【０１１１】
[外部サーバ２の管理処理]
次に、外部サーバ２の管理処理について説明する。
外部サーバ２は、「通常機能」と「特権ノード選定機能」とを有し、「特権ノード選定機能」はさらに<メイン処理>（後記図１３参照）と、<タイマ処理>（後記図１４参照）とを実行する。
【０１１２】
（通常機能）
外部サーバ２は、「通常機能」において、現在のクラスタの全メンバ数を把握（特権ノードへ周期確認）する。また、現在の特権ノードを把握（特権ノードへ周期確認）する。
【０１１３】
（特権ノード選定機能）
外部サーバ２は、特権ノード候補からの特権ノード昇格要求（特権ノード候補情報、クラスタメンバ数）を受け付ける。
外部サーバ２は、上記要求受付後、自身が保持する特定のタイマ満了（タイムアウト期間Ｔ２の満了）まで、回答を待ち合わせるとともに、保持している直近の特権ノードの状態を確認する。
【０１１４】
外部サーバ２は、上記期間に全特権ノード候補から受け付けた内容（クラスタメンバ数）と、外部サーバ２で保持している直近の特権ノードの状態（クラスタメンバ数）の集約を行う。
【０１１５】
ここで、外部サーバ２で保持している直近のクラスタの全体メンバ数をＮとする。また、各特権ノード候補（現在の特権ノードを含む）から報告されたメンバ数をｍ０，ｍ１，ｍ２，ｍ３，…とする。なお、報告されるメンバ数の個数は、高々、分断後のサブクラスタ数である。また、全特権ノード候補（現在の特権ノードを含む）から報告されたメンバ数の合計Ｍは、Ｍ＝ｍ０＋ｍ１＋ｍ２＋ｍ３＋…である。
【０１１６】
外部サーバ２は、Ｍ＞Ｎ／２の場合、最大のクラスタメンバ数を有する特権ノード候補へ「了承」を、他特権ノード候補へ「否決」を通知する。
外部サーバ２は、Ｍ≦Ｎ／２の場合、全特権ノード候補へ「否決」を通知する。または、外部サーバ２は、Ｍ≦Ｎ／２の場合、保守者（保守者端末）に通知する。
【０１１７】
図１３は、本実施形態に係るクラスタシステムの外部サーバ２の特権ノード選定機能のメイン処理を示すフローチャートであり、図１１（ｂ）の（手順２，３）に対応する。
本フローは、特権ノード昇格要求（メンバ数ｍ０）受信をイベント（契機）にスタートする。ステップＳ２１において、管理部２１は、特権ノード昇格要求（メンバ数ｍ０）が外部サーバ２で保持している直近のクラスタの全体メンバ数Ｎ／２より大きい（ｍ０＞Ｎ／２）か否かを判別する。
【０１１８】
ｍ０＞Ｎ／２の場合、ステップＳ２２で管理部２１は、最大のクラスタメンバ数を有する特権ノード候補へ「了承」を、他特権ノード候補へ「否決」を通知して本フローを終了する。
ｍ０≦Ｎ／２の場合、ステップＳ２３で管理部２１は、メンバ数ｍ０を全特権ノード候補（現在の特権ノードを含む）から報告されたメンバ数の合計Ｍとする（ｍ０→Ｍ）。
ステップＳ２４では、管理部２１は、タイムアウト期間Ｔ２を計時するタイマを起動する。
【０１１９】
ステップＳ２５において、管理部２１は、特権ノード昇格要求（メンバ数ｍｎ）を受信する。ここで、ｎはサブクラスタの識別番号である。サブクラスタの識別番号ｎと分断後のサブクラスタ数は、「０≦ｎ≦分断後のサブクラスタ数」と表記できる。例えば、クラスタが３つに分断された場合、０≦ｎ≦２になる。
ステップＳ２６において、管理部２１は、特権ノード昇格要求（メンバ数ｍｎ）が外部サーバ２で保持している直近のクラスタの全体メンバ数Ｎ／２より大きい（ｍｎ＞Ｎ／２）か否かを判別する。
【０１２０】
ｍｎ＞Ｎ／２の場合、上記ステップＳ２２に進む。ステップＳ２２では、最大のクラスタメンバ数を有する特権ノード候補へ「了承」を、他特権ノード候補へ「否決」を通知して本フローを終了する。
ｍｎ≦Ｎ／２の場合、ステップＳ２７で管理部２１は、メンバ数の合計Ｍ＋メンバ数ｍｎを、全特権ノード候補（現在の特権ノードを含む）から報告されたメンバ数の合計Ｍとする（Ｍ←Ｍ＋ｍｎ）。
【０１２１】
ステップＳ２８において、管理部２１は、外部サーバ２で保持している直近のクラスタの全体メンバ数Ｎが全特権ノード候補（現在の特権ノードを含む）から報告されたメンバ数の合計Ｍより小さい（Ｍ＜Ｎ）か否かを判別する。
【０１２２】
Ｍ＜Ｎの場合、上記ステップＳ２５に戻る。
Ｍ≧Ｎの場合、ステップＳ２９において、管理部２１は、最大のクラスタメンバ数を有する特権ノード候補へ「了承」を、他特権ノード候補へ「否決」を通知して本フローを終了する。
【０１２３】
図１４は、本実施形態に係るクラスタシステムの外部サーバ２の特権ノード選定機能のタイマ処理を示すフローチャートである。図１４のタイマ処理フローは、図１３のメイン処理において、前記タイマが起動してタイムアウト期間Ｔ２のタイムアウト値を計時（タイムアウト発生）を契機に実行される。
【０１２４】
本フローは、タイムアウト検出をイベント（契機）にスタートする。ステップＳ３１において、管理部２１は、全特権ノード候補（現在の特権ノードを含む）から報告されたメンバ数の合計Ｍが外部サーバ２で保持している直近のクラスタの全体メンバ数Ｎ／２より大きい（Ｍ＞Ｎ／２）か否かを判別する。
【０１２５】
Ｍ＞Ｎ／２の場合、ステップＳ３２において、管理部２１は、最も多いメンバ数を有する特権ノード候補へ「了承」を、他特権ノード候補へ「否決」を通知して本フローを終了する。なお、このステップＳ３２は、前記図７の動作に対応している。
【０１２６】
Ｍ≦Ｎ／２の場合、ステップＳ３３において、管理部２１は、外部サーバ２から検知できないところで特権ノードが選出される可能性を考慮し、外部サーバ２は通信可能な特権ノード候補に対し一律「否決」を通知して本フローを終了する（前記図９の動作に対応）。または、管理部２１は、保守者（保守者端末）に最適な特権ノード候補の通知を行う（前記図１０の動作に対応）。この場合、「了承／否決」の判断を保守者（保守者端末）が介在して行うことになる。
【０１２７】
次に、外部サーバ２を利用したSplit-Brain Syndroｍe検出方式について説明する。
[Split-brain Syndromeの発生]
前記図１６に示すように、経路障害等で１つのクラスタが複数のクラスタに分断されると、各クラスタ内で他方のクラスタのノードからの死活監視信号の応答がなくなる。そして、特権ノードの存在しない（特権ノードと分断された）クラスタでは新たな特権ノードが選出され、双方のクラスタで特権ノードがノード管理テーブル１２１の更新を行うことでSplit-Brain Syndrineとなる場合が考えられる。
【０１２８】
[Paxosアルゴリズム]
一般的に、Paxosアルゴリズム（非特許文献１参照）とは、分散環境において、信頼性の低いプロセスの集合（本実施形態における複数ノードの集合で構成されるクラスタ）が１つの値に関する合意をとるためのアルゴリズムである。Paxosアルゴリズムは、同時に半数までの障害発生の場合であれば、分散システムを解体させず、分散システムを構成するノード数を変動させる。また各ノードの処理時間が保証できない場合でも、分散システム内で必ず１つの提案で合意が取れるまたは何も合意されない、ということを保証することが可能である。
【０１２９】
[本実施形態の動作説明]
本実施形態について、より詳細に説明する。本方式によれば、分散システム１００（図１参照）において、経路障害等に起因して発生するSplit-brain Syndromeの発生の可能性を検出することができる。なお、以下の一連の処理は、死活監視部１１３（図２参照。以下同様）に連動する特権ノード選出部１１４、およびクラスタ離脱指示部１１５により実現される。
【０１３０】
本実施形態では、特権ノードとして障害発生ノードをノード管理テーブル１２１から削除する処理を実行する前に、本方式を利用して特権ノードとして動作する（すなわち、ノード管理テーブル１２１の更新を行う）権利を持つことをクラスタ内で合意することとする。特権ノードの合意とノード管理テーブル１２１の更新は大きく分けて３つのフェーズで実行される。
【０１３１】
<第一フェーズ（Prepare phase）>
第一フェーズ（Prepare phase）は、提案内容を提案できる提案者を選定する。
第一フェーズ（Prepare phase）では、Paxosアルゴリズム（非特許文献１参照）に準拠するように、特権ノードあるいは特権ノード候補のノード（以降、Proposer（提案者：提案ノード）と呼ぶ）は、ノード１（後記図１５参照）の離脱を通知された場合、残りのノード１（以降、Acceptor（受理ノード）と呼ぶ）に対して、提案番号付きのPrepareリクエストを送信する（後記図１５のステップＳ１参照）。上記残りのノードとは、ノード管理テーブル１２１に存在する全ノードであり、仮にあるノード１の離脱通知を受けたことによるノード管理テーブル１２１の更新の場合でもそのノード１を含むものである。
【０１３２】
Acceptorは、受理している最大の提案番号より大きな提案番号のPrepareリクエストを受けた場合、その大きな提案番号より小さな提案番号は拒否することを約束し、Promise応答を返す（後記図１５のステップＳ２参照）。例えば、あるノード（Acceptor「Ａ」）がいままでに受理していた最大の提案番号が「５」番だった場合、それより大きな提案番号（例えば「１０」番）がくればそれより大きな提案番号を受けているので受理する。以降、「９」番以下の提案番号の提案を受けても受理しない。因みに、他のノードは、Acceptor「Ａ」が提案番号「１０」番を受理したことをAcceptor「Ａ」からのPromise応答を受けて知っているので、Acceptor「Ａ」に対し提案番号「１０」番より小さい提案番号の提案を送信することはない。
【０１３３】
Acceptorは、小さな提案番号のPrepareリクエストを受けた場合は、Reject応答を返す（後記図１５のステップＳ２参照）。Acceptorは、Prepareリクエストを受けた時点で他の小さな提案番号ｂを持つ提案を受理し、かつPaxosアルゴリズムの一連の流れが完結していない場合、その提案番号ｂと提案内容ＶをPromise応答と共に返す。なお、第一フェーズでは、提案番号ｂのみをPromise応答と共に返すAcceptorもあり得る（提案を受けているかどうかで処理が分岐する）。
【０１３４】
例えば、上記の例の場合において、あるAcceptor「Ａ」から提案番号「５」番を最大の提案番号として受理して、他のノードにPromise応答を返しているとする。ここで、別のメンバ（Acceptor「Ｂ」）から提案番号「８」番のPrepareリクエストを受けた場合、Acceptor「Ｂ」は、Acceptor「Ａ」からの提案番号「５」番より大きい提案番号「８」番であるため受理する。受理はするものの、Acceptor「Ｂ」は、既に受理している提案番号「５」番と提案内容ＶをPromise応答と共に返すようにする。なお、第一フェーズでは、提案は行わず、提案番号の予約をするのみとなる。
なお、一連の流れが完結していない場合とは、提案を受けている途中、すなわち以下に説明する第三フェーズ（Commit phase）に移行していない状態をいう。
【０１３５】
Proposerは、過半数のAcceptorからPromise応答を受信した場合、次のフェーズ（第二フェーズ）に進む。Proposerは、一定時間待って過半数からのPromise応答を集めることができない（タイムアウト内に過半数からのPromise応答を集めることができない）場合、再度Prepareから開始する。
【０１３６】
ProposerがPaxosアルゴリズムの一連の流れが完結する前に連続して提案できる回数を２回とする。２回連続で過半数からのPromise応答を集めることができない場合、次のフェーズ（第二フェーズ）に進む。つまり、Proposerが、過半数のノードからPromise応答が返っていなくても次のフェーズ（第二フェーズ）に移行する（後記図１５のステップＳ３参照）。
【０１３７】
なお、離脱したノードが、復活する場合には、障害等が取り除かれた後に、新規ノードとして設定されることを前提とする。このため、離脱したノードが、不完全な状態で復活することはない。
また、一般的に、Paxosアルゴリズムでは、新たなPaxosアルゴリズムの実行にあたり、提案しようとするノードが前回完結したPaxosアルゴリズムのProposerであった場合には、第一フェーズを省略し、後記する第二および第三フェーズのみを実行することが認められている。
【０１３８】
<第二フェーズ（Vote phase）>
第二フェーズ（Vote phase）は、提案者が提案内容を提案するフェーズである。
第二フェーズ（Vote phase）では、Paxosアルゴリズム（非特許文献１参照）に準拠するように、Proposerは、過半数のAcceptorからPromise応答を受信した時点でAcceptリクエストをAcceptorに送信する（後記図１５のステップＳ４参照）。Acceptリクエストには、提案番号ｂと提案内容Ｖが含まれ、提案番号ｂは第一フェーズで利用した提案番号ｂを採用する。つまり、第二フェーズにおける提案番号ｂは、自身が第一フェーズ（Prepare phase）で提案してPromise応答を受けた提案番号である。他のAcceptorから見れば、その約束した提案番号ｂから提案が来たので第二フェーズでAcceptリクエストを受けることになる。提案内容Ｖは、第一フェーズのPromise応答内で提案番号ｂと提案内容Ｖを受理していた場合には、その中から最も大きな提案番号ｂを持つ提案を、受理していない場合は任意の内容を採用する。ここでは、提案内容Ｖとは、あるノードが特権ノードとして、ノードの離脱に伴うノード管理テーブル１２１の更新を行うという提案である。
【０１３９】
ところで、Paxosアルゴリズム（非特許文献１参照）では、Proposerは、必ず一番大きな提案番号ｂを付された提案内容Ｖを提案しなければならない。すなわち、Paxosアルゴリズム（非特許文献１参照）では、Proposerは、同時に複数出現する可能性がある。このため、複数のProposerから同時にAcceptリクエストを受けることがあり、このような場合のため、Paxosアルゴリズム（非特許文献１参照）では、Proposerは、複数の提案の中から、自身の提案でなくても一番大きい提案番号ｂの提案を選ばなくてはならない。そのため、Proposerは、提案番号ｂと提案内容Ｖが含まれるAcceptリクエストをAcceptorに送信するようにしている。
【０１４０】
本実施形態において、Acceptorは、提案番号ｂが第一フェーズで受理している提案番号ｂ以上の値を持つAcceptリクエストを受けた場合、その提案を受理し特権ノードあるいは特権ノード候補のノード（Paxosアルゴリズム（非特許文献１参照）ではLearnerと呼び、本方式ではProposerのノードがLearnerとしての役割を兼任している）にＡＣＫを返す。Acceptorは、提案番号ｂが第一フェーズで受理している提案番号ｂ未満の値を持つAcceptリクエストを受けた場合、Reject応答を返す（後記図１５のステップＳ５参照）。
【０１４１】
Learner（ここではProposer）は、過半数のAcceptorからＡＣＫを受信した場合、外部サーバ２にＡＣＫを受けたAcceptorの数を報告し（後記図１５のステップＳ６参照）、次のフェーズ（第三フェーズ）に進む。
一定時間待って過半数のAcceptorからのＡＣＫを集めることができない（タイムアウト内に過半数からのＡＣＫを集めることができない）場合、外部サーバ２にＡＣＫを受けたAcceptorの数を報告し、外部サーバ２からの了承をもって次のフェーズ（第三フェーズ）に進む。外部サーバ２から否決された場合もしくは一定時間待っても外部サーバ２からの応答が無かった場合、自サブクラスタを解体する。
【０１４２】
ここで、Proposerが、過半数のノードからＡＣＫを受信した場合、第三フェーズ（Commit phase）に移行する（後記図１５のステップＳ７参照）。
【０１４３】
<第三フェーズ（Commit phase）>
第三フェーズ（Commit phase）は、更新情報（Commit）を通知する。
第三フェーズ（Commit phase）では、Learnerは、過半数のAcceptorからＡＣＫを受信した場合、もしくは外部サーバ２から了承された場合、特権ノードとしてのノード管理テーブル１２１（ＩＤ表）を更新する権利を得ることとなる。そして、ノード管理テーブル１２１を更新して離脱したノードを除くAcceptorに対し、更新したノード管理テーブル１２１または更新したノードの情報を配信する。ノード管理テーブル１２１（ＩＤ表）をそのまま送信すると配信負荷が大きくなるため、ノード管理テーブル１２１の送信に代えて、更新したノードの情報（差分情報）を配信するようにしてもよい。
Acceptorは、ノード管理テーブル１２１（ＩＤ表）の更新情報を受信した場合、ＡＣＫを返す。
【０１４４】
[特権ノード選出の流れ]
以上で述べた特権ノード選出の流れについて、図１５を参照して説明する。
図１５は、本実施形態に係るクラスタシステムの特権ノード選出の流れを説明するシーケンス図である。
まず、特権ノードあるいは特権ノード候補のノード１（「Proposer」）は、ノードの離脱を通知された場合、ノード管理テーブル１２１（図２参照）に存在する全ノード１（「Acceptor」）に対して、提案番号付きのPrepareリクエストを送信する（ステップＳ１）。
【０１４５】
Acceptorは、受理している最大の提案番号ｂ以上の提案番号ｂのPrepareリクエストを受けた場合、その提案番号ｂ未満の提案番号ｂは拒否することを約束し、その提案番号ｂと提案内容ＶをPromise応答と共に返す（ステップＳ２）。なお、上述したように、提案内容ＶをPromise応答と共に返すケースには、既に第二フェーズまで実行している別提案を受けていた場合がある。また、Acceptorは、受理している最大の提案番号ｂより小さな提案番号ｂのPrepareリクエストを受けた場合は、Reject応答を返す（ステップＳ２）。
以上は第一フェーズ（Prepare phase）における処理である。
【０１４６】
次に、Proposerは、過半数のAcceptorからPromise応答を受信した場合、第二フェーズ（Vote phase）に移行する。Proposerは、過半数のノードからPromise応答が返っていなくても次のフェーズ（第二フェーズ）に移行する（ステップＳ３）。
Proposerは、過半数のAcceptorからPromise応答を受信した時点でAcceptリクエストをAcceptorに送信する（ステップＳ４）。Acceptリクエストには、提案番号ｂと提案内容Ｖが含まれ、提案番号ｂは第一フェーズで利用した番号を採用する（Paxosアルゴリズム（非特許文献１参照）に準拠）。なお、提案内容Ｖは、第一フェーズのPromise応答内で提案番号ｂと提案内容Ｖを受理していた場合には、その中から最も大きな提案番号ｂを持つ提案を、受理していない場合は任意の内容を採用する。
【０１４７】
Acceptorは、提案番号ｂが第一フェーズで受理している提案番号ｂ以上の値を持つAcceptリクエストを受けた場合、その提案を受理し特権ノードあるいは特権ノード候補のノード（Proposer、ここではLearner）にＡＣＫを返す（ステップＳ５）。Acceptorは、提案番号ｂが第一フェーズで受理している提案番号ｂ未満の値を持つAcceptリクエストを受けた場合、Reject応答を返す。
【０１４８】
Proposerは、外部サーバ２に対してＡＣＫを受けたAcceptor数を報告する（ステップＳ６）。
外部サーバ２は、最大のAcceptor数を報告した特権ノード／特権ノード候補へ「了承」を通知し、それ以外へ「否決」を通知する（ステップＳ７，Ｓ７ａ）。
ここではProposerは、Learnerとして既に動作中である（ステップＳ８）。
【０１４９】
Proposerは、過半数のAcceptorからＡＣＫが返っている場合、または外部サーバ２から了承された場合、次フェーズ（第三フェーズ）に移行する（ステップＳ９）。
【０１５０】
次に、Proposer（Learner）は、過半数のAcceptorからＡＣＫを受信した時点で提案が合意に至ったことを認識する。すなわち、この段階で特権ノードとしてのノード管理テーブル１２１を更新する権利を得ることとなる。そして、ノード管理テーブル１２１（ＩＤ表）を更新して離脱したノードを除くAcceptorに更新したノード管理テーブル１２１（ＩＤ表）または更新したノードの情報を配信する（ステップＳ１０）。
Acceptorは、ノード管理テーブル１２１（ＩＤ表）の更新情報を受信した場合、ＡＣＫを返す（図示省略）。
【０１５１】
上記の処理により、同時に複数の特権ノードがノード管理テーブル１２１（ＩＤ表）を更新することを防ぐことが可能である。すなわち、経路障害等が発生し複数のクラスタに分断した場合に、互いにノード離脱処理を行い複数クラスタのまま処理が継続することはない。
【０１５２】
以上説明したように、本実施形態の分散システム１００は、クラスタ１０の外部に外部サーバ２を備え、外部サーバ２は、クラスタ１０が分断された各サブクラスタの特権ノード候補から各サブクラスタのメンバ数の情報を集約し、最もメンバ数の多いサブクラスタ、または、メンバ数が最多かつ等しいサブクラスタが複数存在する場合には特定のロジックに基づいて選出した一つのサブクラスタの特権ノード候補に特権ノード昇格の了承を、それ以外の特権ノード候補に否決を通知する。各サブクラスタの特権ノード候補は、外部サーバ２から了承の通知を受けた場合、特権ノードに昇格してクラスタ１０を構築し、外部サーバ２から否決の通知を受けた場合、当該サブクラスタを解体する。
【０１５３】
この構成により、Split-Brain Syndromeを防止しつつ、特権ノード決定を行う際に、特権ノードが決まらないような状態をできるだけ起こらないようにすることができる。例えば、ＮＷ分断が複数発生してクラスタが複数に分割され、なおかつ、元のクラスタの過半数が残存するサブクラスタが存在しない場合、Paxosアルゴリズムでは、クラスタ全体が解体されてしまうが、本実施形態によれば、過半数を満たすサブクラスタが存在しない場合にも、クラスタの全体の解体を防ぎ、運用を継続することができる。
【０１５４】
したがって、ＮＷ分断によりクラスタが２つのサブクラスタに分割され、なおかつ、２つのサブクラスタのメンバ数が同数であった場合でも、外部サーバ２からの了承をもって一方のサブクラスタを残し、Split-Brain Syndroｍeが発生していない状態で運用を継続できる。前記図１７の（課題１）を解決することができる。
【０１５５】
また、ＮＷ分断が複数発生してクラスタが複数に分割され、なおかつ、元のクラスタの過半数が残存するサブクラスタが存在しない場合でも、外部サーバ２からの了承をもって一つのサブクラスタを残し、Split-Brain Syndroｍeが発生していない状態で運用を継続できる。前記図１８の（課題２）を解決することができる。
【０１５６】
．
また、本実施形態では、サブクラスタの特権ノード候補は、外部サーバ２から了承または否決の応答がなく、かつ当該サブクラスタのメンバ数が過半数を満たす場合、Paxosアルゴリズムを含む多数決分散合意形成アルゴリズムを適用して、特権ノードとして自律的にクラスタ１０を構築する。これにより、何らかの障害が原因で外部サーバから「了承／否決」の応答がないとき、サブクラスタのメンバ数が過半数を満たす場合は、外部サーバからの応答を待たずに、Paxosアルゴリズムを含む多数決分散合意形成アルゴリズムを利用して特権ノードが自律的にクラスタを構築することができる。
【０１５７】
また、本実施形態では、サブクラスタの特権ノード候補は、外部サーバ２から了承または否決の応答がなく、かつ当該サブクラスタのメンバ数が過半数を満たさない場合、所定タイムアウト期間経過後に自律的に当該サブクラスタを解体する。これにより、何らかの障害が原因で外部サーバから了承／否決の応答がないとき、サブクラスタのメンバ数が過半数を満たさない場合は外部サーバからの応答タイムアウトで自律的にサブクラスタを解体することができる。
【０１５８】
また、本実施形態では、クラスタの特権ノードは、自身が特権ノードであることを示す特権ノード情報およびクラスタメンバ数を、定期的およびクラスタのメンバ数が変化した時に外部サーバ２へ報告する。これにより、外部サーバ２は、定期的報告を受けて分断前のクラスタ全体のメンバ数を把握し、クラスタのメンバ数が変化した時の報告を受けて現状のクラスタ状態（特権ノード情報、クラスタメンバ数）を把握することができる。
【０１５９】
また、本実施形態では、サブクラスタの特権ノード候補は、サブクラスタのメンバ数が、分断前のクラスタ全体のメンバ数の半数以下の場合、自身が特権ノード候補であることを示す特権ノード候補情報およびサブクラスタメンバ数を含む特権ノード昇格要求を外部サーバ２へ発行する。これにより、外部サーバ２は、特権ノード候補であるノードとそのサブクラスタのサブクラスタメンバ数とを把握することができる。
【０１６０】
また、本実施形態では、外部サーバ２は、通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計がクラスタ１０の総メンバ数の半数に満たない場合、通信可能な特権ノード候補に対し一律に否決を通知することで、外部サーバ２と通信可能な特権ノード候補に対し一律「否決」を通知する。これにより、外部サーバ２から検知できないところで過半数を満たすサブクラスタが存在し、多数決分散合意形成アルゴリズムに従って自律的に特権ノードが選出される場合にもSplit-Brain Syndromeを確実に防止することができる。
【０１６１】
また、本実施形態では、外部サーバ２は、通信可能な全特権ノード候補から報告されたサブクラスタのメンバ数の合計がクラスタ１０の総メンバ数の半数に満たない場合、保守者（保守者端末）に特権ノード候補の通知を行うとともに、当該保守者から当該特権ノード候補の了承または否決の判断通知を受け、当該判断通知に従って、特権ノード候補に対し了承または否決を通知する。これにより、一律「否決」を通知する場合に比べ、Split-Brain Syndromeを防止しつつ、より適切な運用を継続することができる。
【符号の説明】
【０１６２】
１  ノード
２  外部サーバ
１０，１０Ａ，１０Ｂ  クラスタ
１１  処理部
１２，２２  記憶部
１３，２３  通信部
２０  ネットワーク
２１  管理部
３０  クライアント
１００  分散システム（クラスタシステム）
１１１  ノード管理部
１１２  メッセージ処理部
１１３  死活監視部
１１４  特権ノード選出部
１１５  クラスタ離脱指示部
１２１  ノード管理テーブル（ノード管理情報）（ＩＤ表）
１２２  死活監視テーブル（死活監視情報）
ｂ  提案番号
Ｖ  提案内容
【図１】
2015215754.tif 000003
【図２】
2015215754.tif 000004
【図３】
2015215754.tif 000005
【図４】
2015215754.tif 000006
【図５】
2015215754.tif 000007
【図６】
2015215754.tif 000008
【図７】
2015215754.tif 000009
【図８】
2015215754.tif 000010
【図９】
2015215754.tif 000011
【図１０】
2015215754.tif 000012
【図１１】
2015215754.tif 000013
【図１２】
2015215754.tif 000014
【図１３】
2015215754.tif 000015
【図１４】
2015215754.tif 000016
【図１５】
2015215754.tif 000017
【図１６】
2015215754.tif 000018
【図１７】
2015215754.tif 000019
【図１８】
2015215754.tif 000020