JP2012507075A - 分散データシステムにおける構成管理 - Google Patents

Abstract

分散環境におけるデータノードの構成を管理するシステムおよび方法。構成マネージャは、マスタノードのいくつかが作動不能である場合でさえ、現在の構成情報を格納するマスタノードの信頼性のある識別を可能にするクォーラムベースの処理を使用する、１組の分散マスタノードとして実装される。マスタノードのクォーラムを達成できない場合、または、現在の構成情報の識別を妨げるいくつかの他の事象が起こる場合、構成に関連するノードの読み込み／書き込みクォーラムからのレポートを分析することにより、構成マネージャをリビルドすることが可能であり、データパーティションの自動復元を可能にする。

Description

本発明は、分散システムにおけるノードの適切な管理および構成／再構成に関する。

コンピュータ技術（例えば、マイクロプロセッサの速度、記憶容量、データ転送帯域幅、ソフトウェアの機能、等）における進歩は、種々の産業において増加するコンピュータアプリケーションに広く貢献してきた。より強力なサーバシステム（サーバのアレイとして構成されることが多い）でさえも、通常、例えば、ＷＷＷ（ワールドワイドウェブ）等の外部のリソースから生じる要求に応えるために提供される。

利用可能な電子データの量が増加するのに伴い、ユーザフレンドリかつ素早いデータの検索および読み出しを容易にする管理しやすい方法で、そのようなデータを格納することがますます重要になる。今日、一般的なアプローチは、電子データを１つまたは複数のデータベースに格納することである。典型的なデータベースは、例えば、希望する複数のデータをコンピュータプログラムが素早く検索かつ選択できるように構造化されたデータを有する情報の、組織化された集合であると見なされる。さらに、そのような環境において、フェデレーション（federation）とは、お互いに信頼を築いた、ユーザのアイデンティティ情報の共有を可能にする、組織またはサービスプロバイダのグループをいう。

ウェブサービス等の分散コンピュータモデルの出現で、サービスプロバイダ（ＳＰ）等のエンティティ間の独立性が増大する。従って、現在の傾向は、内部使用のためのアイデンティティ管理ソリューションではなく組織間相互依存のアイデンティティ情報の管理に焦点を合わせることにある。これを、フェデレーテッドアイデンティティ管理（federated identity management）と呼ぶ。一般に、フェデレーテッドアイデンティティは、ますます頻度が高まる企業境界間の個人の移動を認識する分散コンピュータ構造である。フェデレーテッドアイデンティティの実用的な適用は、同時にいくつかの異機種環境のシステムを管理することが要求される巨大な多国籍企業により示される。

そのような分散システムにおいては、ノードの適切な管理および構成／再構成について種々の課題が存在する。例えば、個々のノードは不規則に作動不能になることがあり、これは、適切な付随する事柄が整えられない時に、データ喪失の原因となり得る。同様に、複製されたデータは、システム周辺で移動させることが必要な場合が多く、これがさらに、信頼性の問題および整合性の問題を生むことがある。

また、信頼性の問題は、例えば、集中型キャッシュの作動不能によりそのようなノードの管理全体に亘って関係するデータが失われると、さらに複雑になり得る。

トランザクションデータストア内のデータは、冗長性目的または高い可用性目的などのために、多くのコンピュータまたは分散システムにおけるノードとして動作する他のデバイスに亘って複製される。しかし、分散システムが可用性についての高い保証を提供する一方で、トランザクションデータストアが管理され複製される下層の（underlying）コンピュータは、それ自体信頼できない。

分散システムは、データストアまたはその何らかのパーティション、の現在のレプリカ（複製物）を格納する１つまたは複数のデータノードの識別を可能にするため、構成情報を格納する構成マネージャにより管理される。構成マネージャは、それぞれが構成情報のコピーを維持する１組のマスタノードとして実装可能である。１組のマスタノード内のマスタノードの１つを、構成マネージャの主要マスタノードとして設計することができ、かつ、構成情報についての要求に応え、データノードの再構成を制御する。

クォーラムベース（quorum-based）の処理を使用して、主要マスタノードを識別することができ、また、構成情報を含むマスタノードが現在の構成情報を含むかどうかを判定することができる。構成マネージャを編成するいくつかのマスタノードが作動不能である場合でさえ、現在の構成情報を含むマスタノードを識別するのに十分なマスタノードが利用可能であれば、信頼できる構成情報を提供することができる。ある実施形態において、十分な数のマスタノードが、マスタノード自身に格納される情報に基づき判定される。

ある実施形態において、各マスタノードは、構成情報と併せて、構成情報が格納された時に構成マネージャを編成する１組のノードを識別する情報を格納する。新しい構成として意図される１組のノードのクォーラムがコミットできない場合、構成情報が任意のマスタノードにおいてコミットされないため、そのような組におけるノードのクォーラムが、ノードが現在の構成を含むということに合意する場合は、確実に、識別される組を現在の構成として見なすことができる。現在の構成マネージャと同じマスタノードのグループを識別する１組のマスタノードが、そのグループのクォーラムを表す時、確実に、その組を、構成マネージャを編成する現在のノードの組として判定することができる。構成マネージャを編成するマスタノードのいくつかが作動不能であっても、マスタノードのクォーラムが、現在の組の構成マネージャについての構成情報を識別する整合性のある情報を格納する限り、再構築コンポーネントが、現在の構成情報のレプリカが取得されるマスタノードを確実に識別することができる。再構築コンポーネントはまた、現在の組における主要マスタノードとして設計されるマスタノードを識別すること、かつ、主要マスタノードが利用可能であるかどうかを判定すること、ができる。主要マスタノードが作動不能になった場合、新しい主要マスタノードを設計することができ、かつ、おそらく、追加のマスタノードを、現在の構成情報を格納する１組のマスタノードの一部として設計することができる。

マスタノードのクォーラムを識別することができない、または、何らかの他の壊滅的な作動不能がある、シナリオにおいては、再構築コンポーネントは、データノードに格納される情報から構成マネージャを再構築することができる。

構成マネージャを再構築するために、主要マスタノードと同じマスタノードを全てのマスタノードが認識する方法で、ノードを主要マスタノードとして識別するプロセスにより、新しい主要マスタノードを選択することができる。ある実施形態において、このプロセスには、主要マスタノード間の通信を伴い、この通信は、ノード間の通信を容易にするデータベースシステムのコンポーネントにより管理される。

ある実施形態において、マスタノード間の通信により、マスタノードはトークンがノードからノードへ渡されるトークンリングに構成されることになり、順序付けられた位置がマスタノードに割り当てられる。新しい主要マスタノードは、位置０のマスタノードとして選択される。トークンリングを使用して、システム動作中に、トークンリング内の作動不能なノードに近接するノードが、作動不能なノードとトークンを交換できない時に近接するノードにより識別される、任意のマスタノードにおける作動不能を識別することもできる。

主要マスタノードが確立されると、構成情報を、データノードに格納される情報から再構築することができる。分散システムにおけるデータノードは、データノードを示し、主要データノードを含み、現在の構成のレプリカを格納する、１つまたは複数のマスタノード（例えば、主要マスタノード）にメッセージを提供することができる。

データノードからのメッセージは、比較されて同じ現在の構成をレポートするデータノードのクォーラムを識別する。同じグループのデータノードを現在の構成を格納するものとして識別する１組のデータノードが、そのグループのクォーラムを表す場合、その組を、確実に、現在の構成を編成する１組のデータノードとして判定することができる。メッセージを、データノードに格納されるデータセットの各パーティションに対して処理することができ、構成マネージャが、パーティションの主要ノードを含む、各パーティションの現在のレプリカを格納するノードを識別する構成情報で、リビルド（再形成）される。

上記記載は、本発明の非制限の要約であり、本発明は添付の請求項により定義される。

添付図面は、正確な縮尺で図面を描くことを意図していない。図面において、種々の図に例示される同一またはほぼ同一の各コンポーネントは同様の数字で表される。明確にする目的のため、全てのコンポーネントが全ての図面でラベル付けされるとは限らない。
本発明のある実施形態に係る再構築コンポーネントのブロック図である。 本発明のある実施形態に係る複数のノードに関連する例示のパーティションおよびリビルドを示す図である。 本発明のある実施形態に係る再構築可能な構成コンポーネントを有するシステムのブロック図である。 本発明のある実施形態に係る新しい構成を設定する方法論を示す図である。 本発明のある実施形態に係るマスタクラスタを使用して分散システムを管理するための方法のフロー図である。 本発明のある実施形態に係るデータベースのパーティションの構成情報をリビルドするための方法のフロー図である。 本発明のある実施形態の種々の態様を実装する例示の環境を示す図である。 本発明のある実施形態に係るデータ検索のために採用されるサンプルのコンピュータ環境の概略ブロック図である。

本発明者は、分散データベースシステムのコストおよび信頼性における向上が、分散データストアのための構成情報を維持する向上した構成マネージャを介して達成されることを、認識し理解している。

本発明者は、分散システムの実装に使用される下層のコンピュータ機器自体が時折作動不能になるような場合でも、分散システムが、データの高い可用性を示すことを必要とすることが多いことを、認識し理解している。このことは、分散システム上のデータノード（レプリカノードとも称する）によりパーティションに維持されるトランザクションデータに適用されるだけでなく、データストアのパーティションを、データが複製されるデータノードに関連させる、マスタノードに格納される構成情報にも適用される。

従って、本発明のある実施形態において、分散システムは、データを格納するための複数のデータノードおよび構成情報を格納するための複数のマスタノードを有する。データはパーティション内に格納することができ、各パーティションは、分散システムにおける１組のデータノードにより複製することができる。パーティションを複製するデータノードが信頼できない場合でも、トランザクションの整合性は、クォーラムベースの処理を使用して確保される。現在の構成におけるデータノードのクォーラムが、現在の構成に合意する場合、クォーラムの一部であるデータノードは、パーティションのデータの信頼できるコピーを提供することができる。

各パーティションは周期的に再構成されて、異なる組のデータノードを利用すること、またはパーティションの主要ノードを変更すること、ができる。再構成は、例えば、データノードの喪失または追加等の分散システムにおける変更に応じてなされる。

任意の時にパーティション内のクォーラムベースのデータノードの識別を容易にするために、現在の構成を確立または再構成する動作はまた、クォーラムベースの処理により実装することができる。パーティションの新しい構成が確立されると、新しい構成のデータノードは、それらがコマンドをコミット可能であるということを示す応答を新しい構成のノードのクォーラムが行うまで、起動コマンドを「コミット」しない。同様に、現在の構成が動作停止にされる場合、現在の構成のノードは、動作停止コマンドをコミット可能であるという応答を現在の構成のノードのクォーラムが行うまで、動作停止コマンドをコミットしない。このように、再構成が生じると、新しい構成を持つノードのクォーラムが生じ、古い構成を持つノードのクォーラムは生じない。

ノードを再構成するプロセスにかかわらず、構成マネージャは、データノードのパーティションの構成情報を格納することができる。加えて、構成マネージャは、１組のデータノードを選択して各パーティションを格納するプログラムを実行することができる。しかし、１組のデータノードを選択してパーティションを格納する方法が、本発明に不可欠であるわけではなく、任意の適切な機構を使用することができる。また、構成マネージャを、例示の実施形態において本明細書ではマスタノードと称される、１組のノードとして実装することもできる。

１組のマスタノードは、マスタクラスタとも称し、各パーティションのレプリカを格納するデータノード、および、各パーティションにおける主要ノードのアイデンティティ等のデータにアクセスする際に使用される他の情報、を識別する構成情報を維持する。マスタクラスタを構成する１組のマスタノードは、時々変更される。クォーラムベースの処理を使用して、マスタクラスタの現在の構成を識別することもできる。データノードと同様に、クォーラムベースの動作によって、マスタクラスタの現在の構成への変更を実行することができる。

ある実施形態において、マスタクラスタ内の構成情報は、パーティションが複製されるデータノードにパーティションをマッピングするデータベースとして格納することができる。本明細書において記載したいくつかの例示の実施形態において、そのようなデータベースは、グローバルパーティションマップ（ＧＰＭ）として記載される。ＧＰＭは、どのノードが動作しているか、どのノードが各パーティションの主要ノードなのか、各パーティションの構成バージョン、および、パーティションが複製されるノードの再構成のプロセスに、ノードが現在関与しているかどうか、等の各パーティションのステータスについての情報をさらに含むことができる。

ＧＰＭは、マスタクラスタ上に格納されるパーティションとして扱うことができる。マスタクラスタ内のノードの１つを、ＧＰＭパーティションの主要ノードとして指定することができる。マスタノードは、概して分散システムのデータノードのように、１つ１つは信頼できないものであり、時々作動不能になる。マスタノードのクォーラムが、マスタクラスタの現在の構成に合意する限り、そのクォーラム内の任意のマスタノードは、ＧＰＭに信頼できる情報を提供することができる。

しかし、ハードウェアの作動不能または他の事象が原因で、マスタクラスタのインテグリティが失われることがある。それに対応して、マスタクラスタがリビルドされてインテグリティを復元することができる。マスタクラスタのインテグリティが失われると、マスタクラスタは、分散システムのデータノードにより格納される情報からリビルドすることができ、これにはＧＰＭの再生成が含まれる。

マスタクラスタは、例えば、主要マスタノードが失われる時、または、マスタノードのクォーラムにアクセスして、ＧＰＭが利用可能である特定のマスタノードが現在のＧＰＭの正確なレプリカを含む、ということを検証することが可能でない時、などのトリガとなる事象（event）に応答してリビルドされる。ある実施形態において、任意のパーティションのレプリカは、メッセージを送るとき、ＧＰＭで照合可能なパーティションの構成バージョンを含む。ＧＰＭとメッセージで示される構成バージョンとの間の不整合はまた、マスタクラスタの再構成のトリガとなり得る。しかし、トリガとなる事象と見なされる特定の事象は、本発明に不可欠ではない。例えば、ある実施形態において、主要ノードの喪失は、必ずしもマスタクラスタをリビルドするトリガとはならない。現在の構成のマスタノードのクォーラムが利用可能な場合、たとえ主要ノードが無い場合でも、主要マスタノードを現在の構成のレプリカを含む別のノードで置き換えることができる。従って、本明細書において記載されるトリガ事象は、例示であり、異なる事象または追加の事象がリビルドのトリガとなり得ることは理解すべきである。

リビルドが開始される条件にかかわらず、リビルドは、全てのマスタノードから現在の構成情報を消去すること、およびその情報をデータノードから受け取ったメッセージに基づき再生成することを伴い得る。新しい主要マスタノードはまた、リビルドの一部として選択することができる。他のマスタノードを、マスタクラスタの新しい構成の二次マスタノードとして指定することができ、データノードからのメッセージで導かれる現在の構成情報のレプリカは、主要マスタノードおよび二次マスタノードの両方に格納可能である。

ある実施形態において、二次ノードの選択は、主要マスタノード上でプログラミングすることによりなされる。加えて、主要マスタノードは、データノードからメッセージを収集かつ処理して、現在のＧＰＭを導き出す。しかし、他の実施形態において、外部のコンポーネントは、主要ノードおよび二次ノードを指定し、メッセージをデータノードから収集する構成コントローラとして動作することができる。

主要マスタノードの選択は、二次マスタノードの選択に関するものとは異なる考察を伴う。本明細書記載の実施形態において、単一のマスタノードが主要マスタノードとして指定され、かつ、全ての他のマスタノードがそのマスタノードを主要マスタノードとして認識する、処理が採用される。ある実施形態において、そのような処理は、マスタノードをトークンリング内に構成することを伴うことができる。トークンリングにおけるマスタノードは、順序を持つことができ、その順序に基づき、マスタノードがリング周りのトークンに渡されるなどする。この順序に基づき、リング内の所定の場所にあるマスタノードを、新しい主要マスタノードとして指定することができ、マスタノードが一意的に識別される。ある実施形態において、新しい主要マスタノードは、トークン値０のマスタノードとして選択される。しかし、任意の適切な機構を使用して、トークンリング内のマスタノードを一意的に識別することができる。また、トークンリングが確立されようとされまいと、任意の他の適切なアプローチを使用して、新しいマスタクラスタにおいてマスタノードを主要マスタノードとして一意的に識別することができる。

ＧＰＭをリビルドする前に、マップに関する任意の既存のデータを、マスタクラスタの要素により削除することができる。このプロセスは、以前のマスタクラスタの全てのマスタノード、および／または、新しいクラスタを編成する全てのマスタノード、またはマスタノードの全て、からＧＰＭを削除することにより、または任意の他の適切な方法により、実行することができる。ＧＰＭをリビルドするために、分散システムにおけるノードはそれぞれ、１つまたは複数のマスタノード（例えば、主要マスタノード）に、ノードにより複製されるパーティション、パーティションの構成バージョン、およびパーティションの１組のデータノード等の情報を示すメッセージ、を提供することができ、その情報からマスタノードはＧＰＭを再構築可能である。ノードによりマスタクラスタに送られたメッセージを周期的に自動的に送ること、マスタクラスタまたは再構成コントローラとして動作する他のデバイスからの要求に応答して送ること、または、システムリセットの一部として送ること、ができる。しかし、任意の適切な機構により、ノードをトリガとしてレポートメッセージをマスタクラスタに送ることができる。ある実施形態において、メッセージは、ノードがそれぞれ有するローカルなパーティションマップを使用して、ノードにより生成される。データノードが複数のパーティションを複製する場合、ノードは上述の情報を各パーティションに提供することができる。

データノードからのメッセージは、マスタクラスタ（例えば、主要マスタノード）により受け取られ、処理されて各パーティションの構成の現在のバージョンを識別する。パーティションの構成バージョンは、データノード自体を現在の構成の一部として識別するデータノードのクォーラムが、構成バージョンに合意する場合に識別される。クォーラムが、同じパーティションの複数の構成バージョンについて達成される場合、より最新の構成バージョンがＧＰＭにおいて起動される。ある実施形態において、より最新の構成バージョンが、最高の数値表現で構成バージョンとして識別される。

ある実施形態において、ノードの再構成に関するデータ／情報（ノードは、読み込み／書き出し条件の動的クォーラムを実装する分散システムに関連する）は、再構築コンポーネントを介して再構築される。一態様において、再構築コンポーネントは、分散システム自身全体に亘る情報の部分的コピーの複製を格納することを可能にする。そして、そのような分散セグメントを採用して、整合性のある方法で中央管理システムのコンテンツを再構築することができる。従って、再構築コンポーネントは、システム上の種々の場所から、グローバルパーティションマップを含む、中央管理コンポーネントのコンテンツを再構築することが可能であり、そして、中央管理コンポーネント／構成コンポーネントを、キャッシュとして扱うことができる。さらに、中央管理コンポーネントを（例えば、システムの他の部分を高度に利用可能にするために採用されるものと同じプロトコルを採用して）プロトコルパーティショニングすることを介して、スケーラビリティを提供することができる。同様に、システムの残りの部分に対するリーダシップ選択の中央管理コンポーネントを採用することにより、フレキシビリティおよびスケールが許容される（典型的には、従来の合意に基づくリーダシップ選択のアルゴリズムを使用する場合には与えられない）。

関連する態様において、構成マネージャコンポーネントを、マスタクラスタを形成する多数のマスタ機器に複製することができる。これらのノードのそれぞれは、構成マネージャのローカルインスタンスが相互作用する再構成エージェントのそれぞれと相互作用することができる。さらに、マスタクラスタの主要再構成エージェントは、通信レイヤにより提供可能な、信頼できる合意のアルゴリズムにより選択することができ、古い構成メンバシップ設定および新しい構成メンバシップ設定がシステム構成により判定される。

従って、再構築コンポーネントは、構成マネージャコンポーネントを複製することが可能であり、従って、マスタクラスタ機器のクォーラム以外のものが失われていても、構成マネージャコンポーネントを容易に利用可能にすることができる。いうなれば、主題の手法では、ノードの分散システムの種々の部分から構成マネージャコンポーネントのコンテンツの復元が可能にされる。

関連する態様において、情報に関するパーティションを、そのパーティションのより最新の構成の一部であるレプリカから復元することが可能である。再構成のアルゴリズムの一部として、各レプリカは、何が最新のまたは最新として示される、パーティションの構成であるのかについての局所視点（local view）を格納する。構成は、レプリカの書き込みクォーラムが新しい構成を受け入れるときにアクティブになるので、主題の手法は、レプリカの書き込みクォーラムが、特定の構成を最新であるとしてレポートするその構成を識別することにより、どの構成が最新であるかを判定することができる。（ノードが時間内にロールバックされないと仮定して、この構成は典型的には、最新であることが保証されるが、これは、現在の構成が、新しい構成が起動される前に動作停止されなければならないため、そのような構成は１つのみ存在可能であるからである。現在の／古い構成の動作停止は、クォーラムを形成するその構成の能力を実効的に破壊する。）
さらなる方法論に従って、マスタクラスタにおける壊滅的な喪失が検出されると、システムは、マスタクラスタ機器（いくつかの機器は実際には稼働可能であるため）に残された任意の部分的な情報を最初に破壊することにより、構成マネージャのリビルドを開始する。続いて、方法論は、ノードのクラスタ／構成の各機器に、ノードがレプリカを保持するパーティションのそれぞれの最も現在に近い（例えば、最新の）構成を送るよう要求し、ここで、構成マネージャコンポーネントはそのようなステータスメッセージを受け取る。メッセージのそれぞれは、システム内に存在したパーティション、特定の機器におけるレプリカ、レポートを行うレプリカには既知であった他の機器におけるレプリカ、および、ステータスをレポートしなかったレポートを行う機器には既知である機器、について構成マネージャコンポーネントが学習することを可能にする。構成マネージャコンポーネントは、パーティションのレプリカが同じ最新の構成をレポートするメッセージの書き込みクォーラムを受け取った時に、パーティションを再度アクティブにすることができ、それにおいて、そのようなクォーラムは構成そのものに依存する。従って、パーティションの最新構成のレプリカの書き込みクォーラムがレポートを行い、かつ、壊滅的な喪失の間、アクティブな再構成が存在しなかった限りにおいて、システムはパーティションの自動的な回復を確実にすることができる。同様に、古い構成の読み込みクォーラムまでは再構成がアクティブであった場合、新しい構成の書き込みクォーラムに対して、典型的には、正確な復元を確実にするよう要求することができる（再構成の段階によってはより少ないレポートで十分である）。

図１は、再構築コンポーネント１０１を使用する構成マネージャ１００のブロック図を示す。再構築コンポーネント１０１は、分散システムの要素の再構成に関する情報の再構築を可能にする。そのような再構築コンポーネント１０１は、リーダエレクタ（leader elector：リーダ選択の権利を持つもの）コンポーネント１０２およびクラスタ構成コンポーネント１０３にさらに関連付けることができ、これらにより、主要な（例えば、アクティブな）構成マネージャインスタンス／コンポーネントに関連する指定／動作を容易にすることができる。一態様において、再構築コンポーネント１０１は、分散システムそのもの全体の情報の部分的コピーの複製を可能にする。そのような分散セグメント／ピースを使用して、整合性のある方法で中央管理システムのコンテンツを再構築することができる。従って、再構築コンポーネント１０１は、システム上の種々の場所から、中央管理コンポーネントのコンテンツを再構築することが可能であり、それにおいて、中央管理コンポーネント／構成コンポーネントを、キャッシュとして扱うことができる。さらに、中央管理コンポーネントを（例えば、システムの他の部分を高度に利用可能にするために採用されるものと同じプロトコルを使用して）プロトコルパーティショニングすることを介して、スケーラビリティを提供することができる。加えて、システムの残りの部分に対するリーダシップ選択の中央管理コンポーネントを使用することにより、フレキシビリティおよびスケールが許容されるが、これは典型的には、従来の合意に基づくリーダシップ選択のアルゴリズムを使用する場合には与えられない。

再構築コンポーネント１０１は任意の適切な方法で実装可能である。ある実施形態において、再構築コンポーネント１０１は、ネットワークを介してマスタノード１１０₁、１１０₂および１１０₃に連結されるコンピュータデバイス内に置くことができる。そのようなコンピュータデバイスを、コンピュータ実行可能命令でプログラミングし、コンピュータデバイスに上述のように事象を監視させることができ、事象は上述のように構成マネージャの再構築のトリガとなる。そのような事象が検出されると、再構築コンポーネント１０１はまた、再構築プロセスを制御するコマンドおよび受け取られた応答を発行することができる。

ある実施形態において、再構築コンポーネント１０１は加えて、主要ノードを制御して、少なくとも利用可能なマスタノードのサブセットが構成されて、構成マネージャ１００内に保持される構成情報の現在のバージョンが複製されること、を確立させる機能を実行することができる。しかし、そのような制御機能は、代わりにまたは加えて、任意の適切なコンポーネントにおいて実装することができる。

例示の実施形態において、再構築コンポーネント１０１が、各マスタノードから切り離されたコンポーネントとして示される。しかし、再構築コンポーネント１０１は、主要マスタノード内を含む、任意の適切なハードウェア内に実装することができることは理解すべきである。

図１は、構成マネージャ１００が複数のマスタノード全体に分散されることを示す。ここでは、３つのマスタノード１１０₁、１１０₂および１１０₃が示される。しかし、任意の適切な数のマスタノードをシステム内に採用することができ、マスタノードのいくつかまたは全てを任意の時に構成して構成マネージャを構成することができる。

例示の実施形態において、各マスタノード１１０₁、１１０₂および１１０₃が、同じハードウェアとともに実装されて示される。そのような構成は、例示を簡略化するために与えられるものであり、各マスタノードは、任意の適切なハードウェアまたはハードウェアコンポーネントと共に実装することができる。しかし、マスタノード１１０₃を例にとると、各マスタノードは、データストア１１２を含むことができ、データストア１１２は、任意の適切なコンピュータ記憶媒体内に実装され、構成情報を格納することができる。加えて、マスタノードは、再構成エージェント１１４および構成マネージャコンポーネント１１６を含むことができる。ある実施形態において、再構成エージェント１１４および構成マネージャコンポーネント１１６は、サーバ内またはマスタノードをホストする他のコンピュータデバイス内に存在するようなプロセッサ上で実行される、コンピュータ実行可能命令として実装することができる。

動作において、構成マネージャコンポーネント１１６は、構成マネージャ１００がネットワークを介して連結される分散データベース内のデータノードの構成を管理することができる。管理動作には、パーティション内のアクティブノードを追跡してパーティションを複製するアクティブなデータノードの数を確認すること、および、データノードの数が不十分である場合にデータノードを構成に追加すること、を含むことができる。加えて、構成マネージャコンポーネント１１６は、パーティションを管理することに関する他のアクションを実行することができ、これには、１つまたは複数のパーティション内のデータを取得可能なデータノード上の情報を有するデータベースにアクセスする他のコンポーネントに、情報を提供すること、が含まれる。構成マネージャコンポーネント１１６はまた、構成マネージャに関連する、従来技術において既知の他のアクション、または任意の他の適切なアクションを実行することができる。

動作において、再構成エージェント１１４は、他のマスタノード内の同様の再構成エージェントと相互作用して、マスタクラスタ内の各マスタノードが構成情報の整合性のあるレプリカを維持することを確実にすることができる。例えば、１つのノード上で情報に変更があった場合、そのノード上の再構成エージェントは、他のノード上の再構成エージェントに変更情報を配布することができる。しかし、マスタノードの機能が、示されるように２つのコンポーネント内において実装される必要があるわけではないことを認識すべきである。全ての機能は、単一のコンポーネント内または３つ以上のコンポーネント内において実装することができる。

上記で触れたように、任意の時に、マスタノードの１つを主要マスタノードとして指定することができる。主要ノードは、構成マネージャの全ての制御機能を実行し、構成マネージャに格納される構成情報に対する全ての変更を開始することができる。現在の構成の他のマスタノードは、そのような変更を受け取り、対応する変更を行って整合性のあるレプリカを維持することができる。例示の実施形態において、マスタノード１１０₂は現在の主要ノードである。

マスタノードを選択して、任意の適切な方法で主要ノードとして動作させることができる。ある実施形態において、マスタノードがネットワーク管理者により指定される。しかし、以下に図３と併せて記載するように、主要マスタノードを選択するための自動化技術を採用することもできる。

図２は、例示の態様に従って、構成マネージャを再構築可能であるシステム２００のブロック図を示す。図２に例示するように、各データノードは、データノードが割り当てられた構成についての情報を格納する。データノードが構成に割り当てられ、かつ、分散システムにより維持されている現在のデータのコピーを受け取る時、そのデータノードに格納される情報は最新のものである。各データノード内のデータは、データベースのパーティションを表すことができる。ある実施形態において、データベースは、単一のパーティションを含むことができるため、現在の構成の一部である各データノードはデータベースの完全なコピーを含む。しかし、他の実施形態において、データベースは、複数のパーティションを含むことができ、また、各データノードは、データベースのサブセットのみを格納することができる。

どの程度の量のデータベースをアクティブなノードに格納するかにかかわらず、時間と共に、ハードウェアの作動不能または他の原因により、１つまたは複数のデータノードが、複製されたデータまたは構成に対する更新を受け取らないかもしれない。従って、データノードに格納される情報自体はノードが最新であることを示すが、その情報は実際には正しくないかもしれない。従って、クォーラムベースのアプローチを、データベースの現在の構成に合意するデータノードを識別するために使用することができる。図２は、クォーラムベースの処理を使用して、分散システムの複数のノードから読み込まれる情報に基づき、現在の構成を識別することができる方法の例を提供する。しかし、この情報を、必ずしも構成マネージャ、再構築コンポーネント、または他のコンポーネントにより起動されるコマンドに応答して読み込む必要はないことは理解すべきである。ある実施形態において、この情報は、システムの再起動または他の事象に応答してデータノードから提供される。

図２に示す例において、パーティションＸのデータについて（例えば、データのセグメント／レプリカ）、構成Ｍは、データノードＤおよびデータノードＥから成り、また、さらに示されるように、データノードＤのみがそのような構成をレポートしている。同様に、構成ＮはデータノードＡ、ＢおよびＣから成り、Ａ、ＢおよびＥは、そのような構成をレポートしている。留意すべきは、本シナリオにおいてデータノードＥは、そのような構成の一部ではないため重要ではなく、しかしなお、ＡおよびＢは書き込みクォーラムを形成し（３つの内２つ）、従って構成Ｎは、実際には最新の構成を表すということである。

最新の構成バージョンの構成バージョンおよびデータノードの情報は、グローバルパーティションマップ（ＧＰＭ）として構成マネージャ内に記録されるものとして示される。この構成情報は、データノードが構成された時に構成マネージャに格納されているものとすることができる。しかし、図２に示すように、この構成情報は、データノードにより送られるメッセージから得ることができ、各データノードは、データノード上にデータが格納される各パーティションの現在の構成を示す、データノードが格納した情報を識別する。このように、データノードからのメッセージに基づき、構成情報を再度作成することができる。

図３は、１組のノードを組織化して、ノードを主要ノードとして一意的に識別することができるアプローチを示す。そのようなアプローチを使用して、主要マスタノードとして動作するマスタノードを自動的に識別することができる。

図３は、リング３１０等の分散環境の一部として複数のノードと併せて構成マネージャコンポーネント３０２を実装する、システム３００のブロック図であり、主題の手法の一態様に従ってリング３１０を再構築することができる。構成マネージャコンポーネント３０２は、動的クォーラムベースの読み込み／書き込み条件を実装することによりトランザクション的に整合性のある方法で、ノードの分散システムの要素（例えば、サーバ）を、古い構成から新しい構成に再構成することができ、動的クォーラムベースの読み込み／書き込み条件によりそのような変換中のデータの喪失を軽減する。そのようなクォーラムは、所定の数値を表すことができ、ここで、読み込みクォーラムおよび書き込みクォーラムを追加すると、構成のノードの数を超える（例えば、所与の構成の読み込みおよび書き込みクォーラムが重なる）。しかし、同様の処理を使用して、古い構成がなくても新しい構成を作成することができ、また、例えば、壊滅的作動不能により構成マネージャを再構築する必要が生じた場合に、その処理を使用することができる。

図３に示すように、一般に、第１のノードＮ₁３０１は、リング３１０内に現れると、数値空間全体をカバーするトークンを作成することが可能であり、また、これを最初のトークン作成と呼ぶことができる。続いて、トークンは、理想的にはノード（Ｎ₁〜Ｎ_m：ｍは整数）間で転送されるだけとすることができ、そのため、典型的には、いずれの時も２つのノードが重なっているトークンを有することはない。例えば、最も簡単な形式において、管理者はノードが第１のノードであるかどうかを明確に示すことができる。

トークンの最初の作成の後、そのようなトークンは、新しいノードがリングに加わる時はいつでも分割される必要があり、また、既存のノードがリングを去り、そのトークンをいくつかの他のノードに引き渡す時は、マージする必要がある。典型的には、リング３１０は、お互いに協力し合って動的かつスケーラブルなネットワークを形成する１組のノードから成るフェデレーションに関連付けられ、ここで、情報を体系的かつ効率的に普及かつ配置させることができる。さらに、フェデレーションに加わるノードは、再帰的、反対照的、遷移的、全体的な、また、ノードのアイデンティティのドメイン上で定義される、２項関係を使用してソートされたリストとして表すことができる。例えば、ソートリストの両端を連結することが可能であり、これによってリング３１０が形成される。それにより、リスト内の各ノードが自分自身をソートリストの中間にあるものと見なす。関連する態様において、リストを二重にリンクし、ノードがリストを両方向に行き来することができるようにすることが可能である。さらに、１対１のマッピング機能を、ノードアイデンティティのバリュードメインからノード自体に対して定義することができる。そのようなマッピング機能は、マッピングが厳しくない場合のバリュードメイン内のノードの希薄さ（sparseness）を担う。

そのように、フェデレーションに加わるあらゆるノードには、０と何らかの適宜に選択された上界との間（０と上界を含む）であり、その範囲が連続的である必要はない（例えば、ノードに割り当てられる数値間にギャップがあっても良い）、自然数が割り当てられる。ノードに割り当てられるそのような数値は、リング内においてノードのアイデンティティの役割を果たす。マッピング機能は、２つのノードのアイデンティティ間に位置付けられる数値を、その数値に数値的に最も近いアイデンティティを有するノードにマッピングすることにより数値空間内のギャップを担う。従って、均一に分散される数値を各ノードに割り当てることにより、リングの全てのセグメントが均一にポピュレート（追加）されることを確実にすることができる。さらに、また、以下に詳細に記載するように、サクセサ（最も近傍のノード）、プレデセサ（次に近傍のノード）、および近傍、の計算を示すノードを、モジュロ演算を使用して効率的に実行することができる。

そのような配置においては、ルーティングの整合性を、トークンの割り当てと所有権を介して達成することができる。典型的には、ノードは、メッセージが向けられる予定のＩＤ上に所有権トークンを有する場合のみ、メッセージを受け入れることが可能である。上記で説明したように、トークンは、連続的範囲のＩＤを含み、全てのトークンが所有者を持つ。遷移中のトークンは、ノードにより受け入れられるまでは存在しないと見なされる。さらに、２つのトークンの範囲は、一般に、ばらばらでなければならず、ここで、全てのトークンの範囲はばらばらであり、トークンを２つの近接するトークンに分割することが可能である。加えて、２つ以上の近接するトークンは、単一のトークンにマージさせることができ、ここで、ノードは、対応するトークン無しではメッセージを受け入れない。加えて、ノードは典型的には、少なくとも自分自身のＩＤを含むトークンを所有しなければならない。トークンを所有するノードは、ルーティング段階にあるものとし、また、ルーティングノードと呼ぶことができる。ルーティングノードは、例えば、単一のトークン、または、単一の範囲のＩＤのみを所有する。最終的には、あるＩＤのトークンは、そのＩＤに最も近接するルーティングノードにより所有される（例えば、活性プロパティ）。トークン転送は、トークンの範囲内の任意のＩＤで格納されるデータの転送と同期させるべきである。さらに正確に言うと、トークン転送は典型的には、データ転送が完了した後にのみ起こり得る。一般に、ルーティングトークンを所有するノードをルーティングノードと呼ぶことが可能である。

図３に示すようなノードをリングに組織化することに関連する上述の相互作用は、任意の適切なコンポーネントにより実行することができる。ある実施形態において、メッセージは、システムにおける利用可能なマスタノードの制御下で、送信および受信することができる。他の実施形態において、相互作用は、マスタノードをネットワーク内で相互接続するコンポーネントにより実装される相互接続ファブリックの制御下で、実行することができる。

図４Ａは、ノードのネットワークを構成する種々の段階のための関連する方法論４００を示す。このプロセスを使用して、データベースのパーティションを格納するデータノードを構成することができる。しかし、同様のプロセスを使用して、マスタノードをマスタクラスタに構成することができる。

分散システムにおけるデータの各パーティションは、１組のデータノード上に格納される。データノードの１つを、パーティションの一次レプリカとして指定することができる。パーティションの残りのデータノードは、二次レプリカとして指定することができる。再構成要求を受け取る時、一次レプリカ上の再構成エージェントは、古い構成または既存の構成の動作停止を開始し、また、さらに新しい構成を起動させることが可能である（例えば、コミットがクライアントに了解された任意のトランザクションが新しい構成により保有されること、および、コミットされていないトランザクションまたはコミットが了解されていないトランザクションをコミットまたはロールバックすることができること、を確実にする）。これには以下の４つの段階の実装を含むことができる。

フェーズ１：符号４１０におけるバロット（投票）およびキャッチアップ（巻き返し）
本フェーズの間、パーティションの一次レプリカは、パーティションの新しい構成に対するグローバルに一意的なＩＤを示す。そのようなＩＤは、古い構成および新しい構成両方のレプリカのクォーラムにより受け取られると、このレプリカのユニットに対して任意の以前に受け取られたＩＤより大きいことが保証される。示されるＩＤは、以前に観察されてきた任意のＩＤより大きいかどうかに基づき、ＩＤを受け入れるかまたは拒否する、古い構成および新しい構成の両方の全てのレプリカに送られる。従って、レプリカは、そのようなＩＤを受け入れる場合、さらに一次レプリカにその最新のトランザクションシーケンス番号を通知することができ、新しいトランザクションの受け取りを停止する。

あるいは、示されるＩＤをレプリカが拒否する場合、最初に選択すべきは、新しいより大きなＩＤと、フェーズ１の再スタートである。古い構成および新しい構成両方のレプリカのクォーラムが、示されるＩＤを受け取ると、最初に新しい構成のレプリカにキャッチアップを開始させ、トランザクションの整合性およびデータの安全性要件が再構成全体に亘って維持されるようにする。これには、個々のレプリカにおいてキャッチアップおよびトランザクションのロールバックが混在して含まれる。さらに、プロセスは、コンテンツの現在の状態に合意するレプリカのクォーラムが得られるよう保証され、かつ、Ａｔｏｍｉｃｉｔｙ（原始性）、Ｃｏｎｓｉｓｔｅｎｃｙ（整合性）、Ｉｓｏｌａｔｉｏｎ（独立性）、Ｄｕｒａｂｉｌｉｔｙ（永続性）（ＡＣＩＤ）のプロパティを再構成全体に亘って提供する。少なくとも一度新しい構成のレプリカのクォーラムがキャッチアップされると、フェーズ１を完了とすることができる。

フェーズ２：符号４２０における古い構成の動作停止
本フェーズの間、一次レプリカは古い構成の動作停止を調整する。動作停止の目的は、「Ｃ１＝Ｃ２でない限り、Ｒ１＝Ｒ２であり、かつ、Ｒ１内の各レプリカｒ１が、構成Ｃ１が最新の構成であること、かつ、Ｒ１がＣ１の書き込みクォーラムを形成すること、を要求し、また、Ｒ２内の各レプリカｒ２が、構成Ｃ２が最新の構成であること、かつ、Ｒ２がＣ２の書き込みクォーラムを形成すること、を要求する」を満たす２組のレプリカＲ１およびＲ２が存在しないことを保証することである。さらに、動作停止メッセージを、古い構成の各レプリカに送ることができる。各レプリカは、受け取った最新のバロットの提示と一致する場合に、動作停止メッセージを受け取ることができる。レプリカの読み込みクォーラムが動作停止を了解すると、本フェーズを完了とする。

フェーズ３：符号４３０における新しい構成の起動
このフェーズの間、一次レプリカは、新しい構成の起動（activation）を調整する。起動の目的は、レプリカのユニットのコンテンツに対する変更が許可される前に、構成が起動されたことを、新しい構成の書き込みクォーラムが知ることを保証することである。これにより、ノードクォーラムが失われる場合に限り、任意のコンテンツの変更が失われるということを確実にすることができる。さらに、起動メッセージを、新しい構成の各レプリカに送ることができる。これらのレプリカのそれぞれは、受け取った最新のバロットの提示と一致する場合に、起動を受け入れることができる。新しい構成のレプリカの書き込みクォーラムが起動を受け入れると、このフェーズは完了する。この時点で、新しい構成はアクティブかつ使用可能になる。

フェーズ４：符号４４０におけるコミット
この段階は、再構成をコミットするための選択的なフェーズである。なぜならフェーズ３の最後で、古い構成が動作停止になり、新しい構成が起動されているためである。しかし、これは、一次レプリカにのみ、また、全体的なシステム外の観点から、了解されているだけである。従って、そのようなコミットのフェーズは、この了解事項を、分散システム内の全ての関係するもの全体に、すなわち、古い構成および新しい構成の各レプリカに加えて構成マネージャにも、配布させる。

図４Ｂは、分散データベースシステムを管理する方法４５０のフロー図である。ステップ４５１にて、データベースの構成が構築される。具体的には、データベースは、１つまたは複数のパーティションとして組織化することができる。データベースの各パーティションは、１組の割り当てられたデータノードにより複製される。最初の構成は、手動で実行されるか、または、任意の適切な方法で自動化することができる。パーティションが再構成されるため、構成バージョンを使用して、各パーティションの現在の構成を識別することができる。

最初の構成の一部として、１組のマスタノードは、分散システム内にマスタクラスタを形成する。ステップ４５３にて、データベースシステムの構成は、マスタクラスタのマスタノードにより構成情報として記録される。ある実施形態において、構成情報は、各パーティションをそれが複製されるデータノードにマッピングする。構成情報には、どのノードが動作しているか、どのノードが各パーティションの主要ノードなのか、および、各パーティションの構成バージョン、等の各パーティションのステータスについての情報がさらに含まれる。構成情報は、例えば、グローバルパーティションマップ（ＧＰＭ）として実装することができる。

ステップ４５５にて、分散システムは、パーティションからデータにアクセスする要求を受信する。要求は、例えば、パーティションからデータを読み込む要求、または、パーティションにデータを書き込む要求、とすることができる。要求は、例えば、分散システムのデータベースへのアクセスを希望するクライアントコンピュータから受信される。

要求に応えるため、分散システムは、どのデータノードが要求に応えるデータを含むのかを判定することができる。構成マネージャは、構成情報の信頼性のあるコピーを含む場合、マスタノードにより格納される構成情報からどのデータノードが要求に応えるかを判定することができる。ステップ４５７にて、分散システムは、分散データベースの現在の構成情報を保持するような、マスタノードの同じ構成を識別するマスタノードのクォーラムが存在するかどうか、を判定する。

クォーラムが存在すると判定される場合、主要ノードは、要求される情報を提供することができる。それに従って、方法４５０はステップ４５９に進む。ステップ４５９にて、マスタノードのクォーラムにより識別されたパーティションの主要データノードが読み込まれる。ステップ４６１にて、要求するクライアントは、主要データノードからアクセスされるデータを提供される。同様に、クライアントから書き込み要求がなされると、書き込まれるべき要求されたデータが、主要データノードに提供される。

しかし、ステップ４５７にて、マスタノードのクォーラムが存在しないと判定される場合、システムは、マスタクラスタをリビルドするという判定をすることができる。ステップ４５７における処理は、代わりにまたは加えて、構成マネージャをリビルドするための、壊滅的なハードウェアの作動不能等のトリガ条件の識別を導く他の処理を含むことができる。本シナリオにおいて、処理はステップ４６３に分岐する。

ステップ４６３にて、マスタクラスタがリセットされる。リセットには、構成マネージャのリビルドの準備のため、全てのマスタノードから現在の構成情報を消去することを伴い得る。

ステップ４６５にて、主要マスタノードが選択される。ある実施形態において、現在の主要マスタノードは、動作しているならば、主要マスタノードとして指定される。他の実施形態において、マスタノードを新しい主要マスタノードとして一意的に識別するための処理が使用される。例えば、マスタノードを、図３と併せて上述したトークンリングに構成することができる。そのような実施形態において、トークンは、ノードからノードに渡され、順序付けられた位置がマスタノードに割り当てられる。新しい主要マスタノードは、位置０のマスタノードとして選択される。

ステップ４６７にて、データノードからメッセージが受信される。本実施形態において、メッセージは新しい主要マスタノードにおいて受信される。しかし、メッセージは、任意の適切なコンポーネントで受信し、かつ処理することができる。各データノードは、メッセージをデータベースの構成を示すマスタクラスタに提供することができる。例えば、データノードは、それが複製するデータベースの１つまたは複数のパーティションおよび各パーティションの構成をマスタクラスタにレポートすることができる。すなわち、データノードは、パーティションの構成バージョン、パーティションの一次レプリカの指標（indication）、パーティションの任意の二次レプリカの指標、およびパーティションのステータス、を特定することができる。ステータスは、例えば、パーティションがデータノード上でアクティブであること、または、データノードがまだ起動されていないパーティションの新しい構成の一部であること、を示すことができる。

しかし、全ての可能なデータノードがそのようなメッセージを送るわけではないことを理解すべきである。例えば、アクティブなデータノードのみ、または、ノードが少なくとも１つのパーティションの現在の構成の一部であることを示す構成情報を格納するデータノードのみ、等のデータノードのいくつかのサブセットは、そのようなメッセージを送ることができる。さらに、現在のパーティション内のデータノードのクォーラムのみが、現在の構成に対する識別されるべきメッセージを送ることを要求されることを認識すべきである。従って、ステップ４６７にてメッセージを受け取るコンポーネントは、クォーラムを識別するメッセージを受け取るまでメッセージを収集することができ、または、ある適切な期間中、全ての可能なデータノードからメッセージを受け取るために待つことなく、メッセージを収集することができる。

いくつのメッセージを受け取るかにかかわらず、処理はステップ４６９に進む。ステップ４６９にて、データノードから提供された情報に基づき構成情報がリビルドされる。リビルドの処理は、図４Ｃに示す方法４７０を参照して記載される。ある実施形態において、ステップ４６３、４６５、４６７、および４６９が、再構築コンポーネント１０１（図１）等の再構築コンポーネントにより実行される。

図４Ｃは、分散システムにおけるデータノードからの構成情報をリビルドする方法４７０のフロー図である。図４Ｃでは単一のパーティションに対する処理を示すが、方法４７０は、データノードから提供される情報を使用して、分散システム内のデータベースの各パーティションに対して実行される。このようにして、データベース全体に関する構成情報を再構築することができる。

ステップ４７１にて、メッセージが送られた時に、パーティションが再構成の最中だったかどうか、すなわち、パーティションが１組のデータノードから別のデータノードに移動中だったかどうか、が判定される。データノードにより提供されるパーティションのステータス情報を使用して、パーティションが再構成の最中であるかどうかを判定することができる。そのような処理は、例えば、再構成プロセス中の構成マネージャに対する壊滅的エラーのせいで不整合な状態にあった情報を使用して、エラーでパーティションが再構築されることを防ぐために、有用である。

ステップ４７１にて、パーティションが再構成の最中でないと判定される場合、方法４７０はステップ４７３に進み、そこで、パーティションの構成バージョンのためのデータノードの書き込みクォーラムが存在するかどうかが判定される。書き込みクォーラムの存在は、データノードによりレポートされるメッセージから判定することができる。それらのメッセージが１組のメッセージを含み、それが異なるノードから送られものであって、１組のノードが現在の構成として一貫して識別される場合、その可能な組を現在の構成とすることができる。現在の構成であると識別されるデータノードのクォーラムが、データノードは現在の構成としてアクティブであるということを示すメッセージを送る場合、その組のノードを、現在の構成を表すものとみなすことができる。ブロック４７３にて、ブロック４６７にて受け取られるメッセージを検索して、現在の構成を識別するための基準を満たす１組のメッセージを見つけることができる。

書き込みクォーラムが存在する場合、方法４７０は、ステップ４７５に進み、そこで書き込みクォーラムにより検証されるようなパーティションの現在の構成が、現在の構成情報として構成マネージャに書き込まれる。

しかし、ステップ４７３にて、書き込みクォーラムが見つからない場合、構成情報をリビルドすることができない場合がある。それ故、例外条件が識別され、これは任意の適切な方法で扱うことができる。ある実施形態において、構成情報を再構築するための図４Ｂおよび図４Ｃの処理は、自動的に実行することができる。しかし、例外処理は、手動での介入を必要とする。

ステップ４７１に戻ると、ステップ４７１にてパーティションの再構成がアクティブであると判定される場合、方法４７０はステップ４７７に進む。ステップ４７７にて、パーティションの古い構成の読み込みクォーラムおよび新しい構成の書き込みクォーラムが存在するかどうかを判定する。ある実施形態において、新しい構成の書き込みクォーラムが存在するかどうかのみがステップ４７７にてチェックされる．
適切なクォーラムが存在する場合、構成マネージャのリビルドのトリガとなる、構成マネージャの壊滅的作動不能等の事象の時に、分散データベースは整合性のある状態であったと見なすことができる。従って、ステップ４７９にて、新しい構成の書き込みクォーラムにより検証されるようなパーティションの新しい構成を有するマスタクラスタにおいて、構成情報が更新される。新しいクォーラムは、選択的に達成することができる。

ステップ４７７にて適切なクォーラムの取得に失敗すると、例外という結果とされる。例外は、例えば、分散データベースが不整合な状態にあるため、手動による介入または他の例外処理が必要であるということを示す。

本願において使用される時、用語「コンポーネント」「システム」は、ハードウェア、ハードウェアとソフトウェアの組み合わせ、ソフトウェア、または実行中のソフトウェア、のいずれかのコンピュータ関連エンティティを参照することが意図される。例えば、コンポーネントは、プロセッサ上で稼働中の処理、プロセッサ、オブジェクト、実行ファイル、実行スレッド、プログラム、および／または、コンピュータとすることができるがこれに限定されない。例として、サーバ上で稼働中のアプリケーションまたはサーバの両方をコンポーネントとすることができる。１つまたは複数のコンポーネントは、プロセスおよび／または実行スレッド内に常駐させることができ、また、コンポーネントは、１つのコンピュータにローカライズさせること、および／または、２つ以上のコンピュータ間に分散させる、ことができる。

さらに、主題の手法の全てまたは一部は、標準プログラミングおよび／または工学技術を使用して、システム、方法、装置、または、製造品として実装することが可能であり、コンピュータを制御して開示される手法を実装させるための、ソフトウェア、ファームウェア、ハードウェア、またはそれらの任意の組み合わせを製造する。例えば、コンピュータ可読媒体には、磁気記憶デバイス（例えば、ハードディスク、フロッピー（登録商標）ディスク、磁気ストリップ．．．）、光ディスク（例えば、ＣＤ、ＤＶＤ．．．）、スマートカード、およびフラッシュメモリデバイス（例えば、カード、スティック、キードライブ．．．）、を含むことができるがこれに限定されない。加えて、搬送波を採用して、電子メールの送受信に使用されるもの、または、インターネットまたはローカルエリアネットワーク（ＬＡＮ）等のネットワークへのアクセス時に使用されるもの、等のコンピュータ可読電子データを搬送することができることを理解すべきである。もちろん、当業者は認識するであろうが、請求される主題の範囲または精神から逸脱することなく、この構成に多くの修正がなされ得る。

本明細書で開示される主題の種々の態様にコンテキストを提供するために、図５および図６、また、以下の検討では、開示される主題の種々の態様を実装することができる適切な環境の簡単な、一般的記述を提供することが意図される。主題は、１つのコンピュータおよび／または複数のコンピュータ上で稼働するコンピュータプログラムのコンピュータ実行可能命令の一般的コンテキストで記載されたが、当業者は認識するであろうが、手法は、他のプログラムモジュールとの組み合わせにおいて実装することができる。一般に、プログラムモジュールには、特定のタスクを実行する、および／または、特定の抽象データ型を実装するルーチン、プログラム、コンポーネント、データ構造等が含まれる。さらに、当業者は理解するであろうが、革新的な方法を他のコンピュータシステム構成で実践することが可能であり、他のコンピュータシステム構成には、シングルプロセッサコンピュータシステムまたはマルチプロセッサコンピュータシステム、ミニコンピュータデバイス、メインフレームコンピュータ、のみならず、パーソナルコンピュータ、ハンドヘルドコンピュータデバイス（例えば、ＰＤＡ、電話、時計．．．）、マイクロプロセッサベースのまたはプログラム可能な家庭用電子機器または工業電子機器、が含まれる。例示の態様はまた、通信ネットワークを介してリンクされるリモート処理デバイスによりタスクが実行される、分散コンピュータ環境にて実践することができる。しかし、手法の態様の全てではなくともいくつかは、スタンドアロンコンピュータ上で実践することができる。分散コンピュータ環境において、プログラムモジュールを、ローカルおよびリモート両方のメモリ記憶装置に配置させることできる。

図５を参照すると、主題の手法の種々の態様を実装するための例示の環境５１０が記載され、これにはコンピュータ５１２が含まれる。コンピュータ５１２には、処理ユニット５１４、システムメモリ５１６、およびシステムバス５１８が含まれる。システムバス５１８は、システムメモリ５１６を含むがこれに限定されないシステムコンポーネントを処理ユニット５１４に連結する。処理ユニット５１４は、任意の種々の利用可能なプロセッサとすることができる。デュアルマイクロプロセッサおよび他のマルチプロセッサのアーキテクチャを処理ユニット５１４として採用することも可能である。

システムバス５１８は、メモリバスまたはメモリコントローラ、周辺機器用バスまたは外部バス、および／または、例えば、１１ビットバス、ＩＳＡ、ＭＳＡ（Micro-Channel Architecture）、ＥＩＳＡ（Extended ISA）、ＩＤＥ、ＶＬＢ（VESA Local Bus）、ＰＣＩ、ＵＳＢ、ＡＧＰ、ＰＣＭＣＩＡ、およびＳＣＳＩを含むがこれらに限定されない任意の様々な利用可能なバスアーキテクチャを使用するローカルバスを含む、いくつかのタイプのバス構造のいずれかとすることができる。

システムメモリ５１６には、揮発性メモリ５２０および不揮発性メモリ５２２が含まれる。基本入出力システム（ＢＩＯＳ）は、スタートアップ時等にコンピュータ５１２内の要素間で情報を転送する基本ルーチンを含むもので、不揮発性メモリ５２２に格納される。例えば、不揮発性メモリ５２２は、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、またはフラッシュメモリを含むことができる。揮発性メモリ５２０には、外部キャッシュメモリとして働くＲＡＭが含まれる。制限ではなく例として、ＲＡＭは、ＳＲＡＭ、ＤＲＡＭ、ＳＤＲＡＭ、ＤＤＲＳＤＲＡＭ（double data rate SDRAM）、ＥＳＤＲＡＭ（enhanced SDRAM）、ＳＬＤＲＡＭ（Synchlink DRAM）、およびＤＲＲＡＭ（direct Rambus RAM）、等の多くの形式で利用可能である。

コンピュータ５１２にはまた、着脱可能／着脱不可能、揮発性／不揮発性のコンピュータ記憶媒体が含まれる。図５は、ディスクストレージ５２４を例示し、それにおいて、そのようなディスクストレージ５２４には、磁気ディスクドライブ、フロッピー（登録商標）ディスクドライブ、テープドライブ、Ｊａｚドライブ、Ｚｉｐドライブ、ＬＳ−６０ドライブ、フラッシュメモリカード、またはメモリスティック、のようなデバイスが含まれるがこれに限定されない。加えて、ディスクストレージ５２４には、記憶媒体を別個に含むことができ、または、ＣＤ−ＲＯＭデバイス、ＣＤ−Ｒドライブ、ＣＤ−ＲＷドライブ、または、ＤＶＤ−ＲＯＭドライブ等の光ディスクドライブを含むがこれに限定されない他の記憶媒体と組み合わせて含むことができる。ディスクストレージデバイス５２４とシステムバス５１８の接続を容易にするため、インターフェース５２６等の着脱可能または着脱不可能のインターフェースが、典型的には使用される。

図５では、ユーザと適切な動作環境５１０で説明した基本コンピュータリソースとの間の仲介として動作するソフトウェアが説明されることは理解すべきである。そのようなソフトウェアには、オペレーティングシステム５２８が含まれる。オペレーティングシステム５２８は、ディスクストレージ５２４に格納可能であり、コンピュータシステム５１２のリソースを制御し割り付けるよう動作する。システムアプリケーション５３０は、システムメモリ５１６またはディスクストレージ５２４に格納されるプログラムモジュール５３２およびプログラムデータ５３４を介して、オペレーティングシステム５２８によるリソースの管理を活用する。本明細書に記載される種々のコンポーネントが、種々のオペレーティングシステムまたはオペレーティングシステムの組み合わせにより実装可能であることは理解すべきである。

ユーザは、入力デバイス５３６を介してコンピュータ５１２にコマンドまたは情報を入力する。入力デバイス５３６には、マウス等のポインティングデバイス、トラックボール、スタイラスペン、タッチパッド、キーボード、マイク、ジョイスティック、ゲームパッド、パラボラアンテナ、スキャナ、テレビチューナカード、デジタルカメラ、デジタルビデオカメラ、ウェブカメラ、などが含まれるがこれに限定されない。これらおよび他の入力デバイスは、インターフェースポート５３８を介してシステムバス５１８を通り、処理ユニット５１４に接続される。インターフェースポート５３８には、例えば、シリアルポート、パラレルポート、ゲームポート、および、ＵＳＢが含まれる。出力デバイス５４０は、入力デバイス５３６と同じタイプのポートのいくつかを使用する。従って、例えば、ＵＳＢポートを使用して、コンピュータ５１２への入力を与え、かつ、コンピュータ５１２から出力デバイス５４０に情報を出力することができる。出力アダプタ５４２は、他の出力デバイス５４０の中でも、特別なアダプタを必要とする、モニタ、スピーカおよびプリンタ等のいくつかの出力デバイス５４０が存在することを例示するために与えられる。出力アダプタ５４２には、制限ではなく例として、出力デバイス５４０とシステムバス５１８との間の接続手段を提供するビデオカードおよびサウンドカードが含まれる。他のデバイスおよび／またはデバイスのシステムが、リモートコンピュータ５４４等の、入力および出力両方の能力を提供することに留意すべきである。

コンピュータ５１２は、リモートコンピュータ５４４等の１つまたは複数のリモートコンピュータへの論理接続を使用して、ネットワーク化された環境において動作することができる。リモートコンピュータ５４４は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ワークステーション、マイクロプロセッサベースの電化製品、ピアデバイス、または他の共有ネットワークノード、等とすることができ、典型的には、コンピュータ５１２に関連して説明した要素の内の多くまたは全てを含む。簡潔にする目的で、メモリ記憶装置５４６のみが、リモートコンピュータ５４４と共に例示される。リモートコンピュータ５４４は、コンピュータ５１２に、ネットワークインターフェース５４８を介して論理的に接続され、そして、通信接続５５０を介して物理的に接続される。ネットワークインターフェース５４８には、ローカルエリアネットワーク（ＬＡＮ）およびワイドエリアネットワーク（ＷＡＮ）等の通信ネットワークが包含される。ＬＡＮ技術には、光ファイバ分散データインタフェース（ＦＤＤＩ）、銅線分散データインタフェース（ＣＤＤＩ）、イーサネット（登録商標）／ＩＥＥＥ８０２．３、トークンリング／ＩＥＥＥ８０２．５、等が含まれる。ＷＡＮ技術には、２地点間リンク、ＩＳＤＮやその変形などのような回線交換ネットワーク、パケット交換ネットワーク、および、ＤＳＬ（Digital Subscriber Lines）、が含まれるがこれに限定されない。

通信接続５５０は、ネットワークインターフェース５４８をバス５１８に接続するために採用されるハードウェア／ソフトウェアに言及する。通信接続５５０は、明確に例示するためにコンピュータ５１２内部に示されるが、コンピュータ５１２の外部とすることもできる。ネットワークインターフェース５４８への接続に必要なハードウェア／ソフトウェアには、例示の目的のみのため、通常の電話回線用のモデム、ケーブルモデムおよびＤＳＬモデム、ＩＳＤＮアダプタ、ならびにイーサネットカード、等の内部技術および外部技術が含まれる。

図６は、主題の手法の態様に係る、フェデレーションの一部としてノードを実装するために採用することができるサンプルのコンピュータ環境６００の概略ブロック図である。システム６００には、１つまたは複数のクライアント６１０が含まれる。クライアント６１０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピュータデバイス）とすることができる。システム６００にはまた、１つまたは複数のサーバ６３０が含まれる。サーバ６３０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピュータデバイス）とすることができる。サーバ６３０は、本明細書に記載されるコンポーネントを使用することにより、例えば、スレッドを収容して変換を実行することができる。クライアント６１０とサーバ６３０との間の１つの可能な通信は、２つまたはそれ以上のコンピュータプロセス間で伝送されるよう適合されたデータパケットの形式とすることができる。システム６００には、クライアント６１０とサーバ６３０との間の通信を容易にするために使用することができる通信フレームワーク６５０が含まれる。クライアント６１０は、クライアント６１０にローカルな情報を格納するために使用することができる１つまたは複数のクライアントデータストア６６０に操作可能に接続される。同様に、サーバ６３０は、サーバ６３０にローカルな情報を格納するために使用することができる１つまたは複数のサーバデータストア６４０に操作可能に接続される。

本発明の少なくとも１つの実施形態の、以上のような記載のいくつかの態様を有することで、種々の代替、修正、および改良が当業者により容易に想到されることは理解すべきである。

可能性のある変形例として、上記した例示の実施形態において、ノードのクォーラムは、ノードの大多数であるものとして選択された。ノードの大多数より多いまたは少ないクォーラムでの、他の実装が可能である。さらに、クォーラムは、ノードが作動不能またはオフラインになった時など、時と共に構成を変更できる。

追加の例として、本出願では、主要マスタノードの喪失が、構成マネージャのリビルドのトリガとなる壊滅的な作動不能と見なされるシステムが例として使用される。主要マスタノードの喪失が構成マネージャのリビルドのトリガとなることは、必要条件ではない。現在の構成情報の１つまたは複数のレプリカが、確実に識別可能であるならば、この情報に基づき、構成マネージャをリセットすることができる。

そのような代替、修正、および改良は、本開示の一部であることが意図され、かつ、本発明の精神および範囲内にあることが意図される。従って、前述の記載および図面は単なる例である。

本発明の上述の実施形態は、多数の方法の内のいずれかにより実装可能である。例えば、実施形態は、ハードウェア、ソフトウェア、またはその組み合わせを使用して実装することができる。ソフトウェアにより実装する場合、ソフトウェアコードは、単一のコンピュータに提供されるか、複数のコンピュータ間に分散されるかにかかわらず、任意の適切なプロセッサまたはプロセッサの集合上で実行できる。

さらに、コンピュータは、ラックマウント式のコンピュータ、デスクトップコンピュータ、ラップトップコンピュータ、またはタブレット型コンピュータ、等の多くの形式のいずれかにより具現化できるということを理解すべきである。加えて、コンピュータは、一般にはコンピュータとは見なされないが、ＰＤＡ、スマートフォンまたは任意の他の適切な携帯用もしくは固定の電子機器を含む、適切な処理能力を有するデバイス内に埋め込むことができる。

また、コンピュータは、１つまたは複数の入力デバイスおよび出力デバイスを有することができる。これらのデバイスを、他の物の中で使用して、ユーザインターフェースを提示することができる。ユーザインターフェースを提供するために使用できる出力デバイスの例として、視覚的表現の出力のためのプリンタまたはディスプレイ画面、および、オーディオ表現の出力のためのスピーカまたは他の音声生成デバイス、がある。ユーザインターフェースを提供するために使用できる入力デバイスの例として、キーボード、およびマウス、タッチパッド、および離散化タブレット等のポインティングデバイスがある。別の例として、コンピュータは、音声認識を介した入力情報、または他のオーディオ形式の入力情報を受け取ることができる。

そのようなコンピュータは、企業ネットワークまたはインターネット等の、ＬＡＮまたはＷＡＮを含む任意の適切な形式の１つまたは複数のネットワークにより相互接続することができる。そのようなネットワークは、任意の適切な技術に基づき、かつ、任意の適切なプロトコルに従って動作し、かつ、無線ネットワーク、有線ネットワークまたは光ファイバネットワークを含む、ことができる。

また、本明細書に概説した種々の方法またはプロセスを、様々なオペレーティングシステムまたはプラットフォームのいずれか１つを使用する、１つまたは複数のプロセッサ上で実行可能なソフトウェアとしてコード化することができる。加えて、そのようなソフトウェアは、多くの適切なプログラミング言語および／またはプログラミングツールまたはスクリプトツールのいずれかを使用して記述することができ、また、フレームワークまたは仮想マシン上で実行される実行可能な機械語コードまたは中間コードとしてコンパイルすることができる。

この点において、本発明は、コンピュータ可読媒体（または複数のコンピュータ可読媒体）（例えば、コンピュータメモリ、１つまたは複数のフロッピーディスク、コンパクトディスク、光ディスク、磁気テープ、フラッシュメモリ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）内の回路構成もしくは他の半導体デバイス、または他の有形のコンピュータ記憶媒体）として具現化することができ、これには１つまたは複数のコンピュータまたは他のプロセッサ上で実行されると、上記で検討した本発明の種々の実施形態を実装する方法を実行する、１つまたは複数のプログラムがコード化される。コンピュータ可読媒体は移動可能であるので、これに格納されるプログラムを、１つまたは複数の異なるコンピュータまたは他のプロセッサにロードして、上記で検討した本発明の種々の態様を実装させることができる。

用語「プログラム」または「ソフトウェア」は、本明細書において一般的意味で使用されて、コンピュータまたは他のプロセッサをプログラムして、上記で検討した本発明の種々の態様を実装させるために使用することができる、任意のタイプのコンピュータコードまたは１組のコンピュータ実行可能命令を参照する。加えて、本実施形態の一態様に従って、実行されると本発明の方法を実行する１つまたは複数のコンピュータプログラムは、単一のコンピュータまたはプロセッサに常駐させる必要はなく、多くの異なるコンピュータまたはプロセッサ間にモジュール方式で分散させて、本発明の種々の態様を実装させることができることは理解すべきである。

コンピュータ実行可能命令は、プログラムモジュール等の、１つまたは複数のコンピュータまたは他のデバイスにより実行される、多くの形式とすることができる。一般にプログラムモジュールには、特定のタスクを実行、または特定の抽象データ型を実装する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造等が含まれる。典型的には、プログラムモジュールの機能性は、種々の実施形態において所望の通りに組み合わせることまたは分散させることができる。

また、データ構造は、任意の適切な形式でコンピュータ可読媒体内に格納することができる。説明を簡素化するために、データ構造は、データ構造内における配置を介して関連するフィールドを持つものとして示すことができる。そのような関係は、フィールド間の関係を搬送するコンピュータ可読媒体内に、フィールドのためのストレージを配置と共に割り当てることにより、同様に達成することができる。しかし、任意の適切な機構を使用して、ポインタ、タグ、またはデータ要素間の関係を確立する他の機構を使用することなどにより、データ構造のフィールドにおける情報の関係を確立することができる。

本発明の種々の態様は、単独で、組み合わせて、または、上記に記載した実施形態において特には検討されない様々な様式で、使用することができるため、その用途において、上記の記述において記載されたまたは図面に例示されるコンポーネントの詳細および様式に限定されない。例えば、一実施形態において記載される態様は、任意の方法で、他の実施形態において記載される態様と組み合わせることができる。

また、本発明は、方法として具現化することができ、その一例が提供された。方法の一部として実行される動作は、任意の適切な方法で順序付けられる。従って、動作が例示のものとは異なる順番で実行される実施形態を構築することが可能であり、例示の実施形態においては一連の動作として示されていても、いくつかの動作を同時に実行することがあり得る。

「第１の」「第２の」「第３の」等の順序を示す用語を請求項において使用され請求の要素を修飾することは、それ自体が、任意の優先、先行、または１つの請求の要素の別の要素に対する順番もしくは方法の動作が実行される一時的な順番、を暗示することはなく、単に、特定の名前を持つ１つの請求の要素を（順序を示す用語の使用以外は）同じ名前を持つ別の要素と区別するためのラベルとして使用され、請求の要素を区別する。

また、本明細書において使用される語句表現および専門用語は、記載目的のものであり、制限するものとしてみなすべきではない。本明細書における「含む」「から成る」または「有する」「含有する」「伴う」およびその変形は、その後に列挙される項目およびその等価物のみならず追加の項目をも包含することを意味する。

Claims (15)

1. データベースのパーティションのレプリカを格納する複数のデータノードの現在の構成を定義する構成情報を取得する方法であって、
   前記方法は、
   少なくとも１つのプロセッサ（５１４）を操作して、
   複数のメッセージを受け取る動作であって、各メッセージは、前記複数のデータノードの１つのデータノードにより生成され、かつ、前記データノードが構成されるデータベースの構成のバージョンを示し、また、示される構成に従って構成され、前記データノード上に格納されるパーティションを複製する１組のデータノードを示す、動作（４６７）と、
   前記受け取られたメッセージに基づき、選択される１組のデータノードを識別する動作であって、前記選択される１組のデータノードは、前記複数のメッセージの少なくとも１つで識別される組であり、前記組内のデータノードのクォーラムがそれぞれ、同じ構成バージョンと前記選択される１組のデータノードとを示すメッセージを生成した、動作（４６９）と、
   前記構成情報の一部として、前記選択される組の各データノードがパーティションのレプリカを格納するデータノードであるというインジケーションを格納する動作（１１２）と
   を含む動作を実行するステップ
   を含むことを特徴とする方法。
2. 前記複数のメッセージが、パーティションを格納するよう構成されるデータノードの少なくとも半分からのメッセージを含み、前記クォーラムを形成するデータノードが、前記パーティションを格納する前記データノードの少なくとも半分を含む、ことを特徴とする請求項１に記載の方法。
3. それぞれのデータベースを格納する前記複数のデータノードに要求を送り、前記複数のメッセージの中から各々のメッセージを提供するステップをさらに含むことを特徴とする請求項１に記載の方法。
4. 前記格納する動作が、前記構成情報を構成マネージャ（１１６）に格納する動作を含み、前記構成マネージャがマスタクラスタ（１１０）内の複数のマスタノードを含むことを特徴とする請求項３に記載の方法。
5. 前記マスタクラスタ（１１０）内に格納される前記構成情報のインテグリティの喪失を示す事象の検出に応答して、
   前記構成情報を前記マスタクラスタ（１１０）のマスタノードから削除するステップと、
   前記複数のマスタノードの中から新しい主要マスタノード（１１０₂）としてマスタノードを選択するステップと
   をさらに含むことを特徴とする請求項４に記載の方法。
6. 第２のノードにより生成される前記複数のメッセージの中の第２のメッセージは、前記第２のノードが、第２のパーティションを持ち、前記第２のパーティションが第１の構成バージョンを有することを示し、かつ、前記第２のパーティションのデータノードを識別し、
   前記第２のパーティションのデータノードから前記複数のメッセージの中の任意のメッセージを検査するステップと、
   前記第２のパーティションのデータノードのクォーラムが存在しないことを判定するステップと
   をさらに含むことを特徴とする請求項１に記載の方法。
7. 前記構成情報内のパーティションをアクティベートするステップをさらに含むことを特徴とする請求項１に記載の方法。
8. 前記パーティションのデータノードの識別されたクォーラムが、前記パーティションの全てのデータノードを含むことを特徴とする請求項７に記載の方法。
9. 複数のパーティションを含むデータベースを格納するデータベースシステムであって、
   前記システムは、
   複数のコンピュータノード（３０１）と、
   前記複数のコンピュータノードを通信可能に相互接続するネットワークと
   を備え、
   前記複数のコンピュータノード（３０１）が、
   複数の組（３１０）として組織化される複数のデータノードであって、各組は前記複数のパーティションの１つのパーティションのレプリカを格納する前記複数のデータノードのノードを含む、データノードと、
   複数のマスタノード（１１０）であって、各マスタノードは、構成情報のレプリカを格納し、前記構成情報は、前記複数の組（３１０）のそれぞれの内のデータノードと、前記複数の組のそれぞれの内のノード上で複製される前記複数のパーティションの１つのパーティションとを識別する、マスタノードと
   を含む、ことを特徴とするシステム。
10. 前記複数のパーティションの第１のパーティションのデータノードは、それぞれ、第１のメッセージを生成するように構成され、該第１のメッセージは、前記第１のパーティションを前記ノード上で複製されるものとして識別し、前記第１のパーティションの構成バージョンを識別し、前記第１のパーティションの構成バージョンのデータノードのそれぞれを識別し、
    前記複数のマスタノード（１１０）が、再構築のトリガとなる事象に応答して方法を実行するよう構成され、前記方法が、
    前記第１のパーティションのデータノードにより生成される複数の第１のメッセージを受け取るステップと、
    前記第１のパーティションのデータノードのクォーラムを識別するステップであって、前記クォーラムを形成するデータノードが、それぞれが前記第１のパーティションの同じ構成バージョンを有するステップと、
    前記構成情報を更新して、前記第１のパーティションに対して、前記第１のパーティションの構成バージョンと前記第１のパーティションのデータノードとを示すステップと
    を含む
    ことを特徴とする請求項９に記載のシステム。
11. 前記再構成のトリガとなる事象は、前記複数のマスタノード（１１０）の間でのクォーラムの喪失であることを特徴とする請求項１０に記載のシステム。
12. 前記再構成のトリガとなる事象は、前記複数のマスタノード（１１０）の間での主要マスタノードの喪失であることを特徴とする請求項１０に記載のシステム。
13. 前記複数のマスタノード（１１０）のそれぞれが、通信リング上のトークンに割り当てられ、
    主要マスタノードの喪失の後に残った複数のマスタノード（１１０）の間の新しい主要マスタノード（１１０₂）は、所定の値に亘るトークンを有するマスタノードとして識別される
    ことを特徴とする請求項１２に記載のシステム。
14. 前記新しい主要マスタノード（１１０₂）が前記方法を実行することを特徴とする請求項１３に記載のシステム。
15. 前記複数のマスタノード（１１０）によりクォーラムを識別するステップが、
    前記データノードの１つからの第１のメッセージにより識別される第１のパーティションの構成バージョンを、１つまたは複数の他のデータノードからの第１のメッセージにより示される構成バージョンと比較するステップであって、前記１つまたは複数の他のデータノードは、前記データノードの１つからの第１のメッセージにより、前記第１のパーティションの構成バージョンのデータノードであると識別されるデータノードである、ステップをさらに含む
    ことを特徴とする請求項１０に記載のシステム。

Images