(57)【特許請求の範囲】
【請求項１】
コンピュータ実行可能命令がエンコードされたコンピュータ読取り可能記録媒体であって、前記コンピュータ実行可能命令は、ネットワーク内のコンピュータの少なくとも１つのプロセッサ上で実行されると、ネットワーク内のノードの第１のセットおよび第２のセットと通信し、前記ノードの第１のセットによって実装された分散データベースを前記ノードの第２のセットによって実装された分散データベースに再構成する再構成動作を行う方法であって、前記ノードの第１のセットは、ノードの現在アクティブなセットであり、前記ノードの第２のセットは、ノードの現在アクティブではないセットであり、前記ノードの第１のセットは、前記ノードの第１のセット内のノードの数を指定する第１の定数値と関連付けられ、前記ノードの第２のセットは、前記ノードの第２のセット内のノードの数を指定する第２の定数値と関連付けられている、方法を実行し、前記方法は、
前記ノードの第１のセットがノードの現在アクティブなセットであることをやめることを合図する非アクティブ化メッセージを前記ノードの第１のセットに送信することと、
少なくとも前記ノードの第１のセットのサブセット内の各ノードから、前記非アクティブ化メッセージに対する応答であって、前記非アクティブ化メッセージの受諾または拒否の表示を含む応答、を受信することと、
前記非アクティブ化メッセージの受諾の表示を含む受信された応答の数が、少なくとも前記ノードの第１のセットと関連付けられた前記第１の定数値であるかどうかを判定することと、
前記非アクティブ化メッセージの受諾の表示を含む受信された応答の数が、少なくとも前記ノードの第１のセットと関連付けられた前記第１の定数値である時に、前記ノードの第２のセットがノードの現在アクティブなセットになることを合図するアクティブ化メッセージを前記ノードの第２のセットに送信することと、
少なくとも前記ノードの第２のセットのサブセット内の各ノードから、前記アクティブ化メッセージに対する応答であって、前記アクティブ化メッセージの受諾または拒否の表示を含む応答、を受信することと、
前記アクティブ化メッセージの受諾の表示を含む受信された応答の数が、少なくとも前記ノードの第２のセットと関連付けられた前記第２の定数値であるかどうかを判定することと、
前記アクティブ化メッセージの受諾の表示を含む受信された応答の数が、少なくとも前記ノードの第２のセットと関連付けられた前記第２の定数値である時に、前記ノードの第１のセットの識別子および前記ノードの第２のセットの識別子を含む構成コミットメッセージを、前記ノードの第１のセットおよび前記ノードの第２のセットに送信することと
を備えることを特徴とするコンピュータ読取り可能記録媒体。
【請求項２】
前記方法は、
少なくとも前記ノードの第１のセットのサブセット内の各ノードから、前記非アクティブ化メッセージに対する応答を受信した後に、
前記非アクティブ化メッセージに対する受信された応答が、前記非アクティブ化メッセージの拒否の表示を含むかどうかを判定することと、
前記非アクティブ化メッセージに対する受信された応答が、前記非アクティブ化メッセージの拒否の表示を含むと判定される時に、前記再構成動作を再開始することと
をさらに備えることを特徴とする請求項１に記載のコンピュータ読取り可能記録媒体。
【請求項３】
前記方法は、
少なくとも前記ノードの第２のセットのサブセット内の各ノードから、前記アクティブ化メッセージに対する応答を受信した後に、
前記アクティブ化メッセージに対する受信された応答が、前記アクティブ化メッセージの拒否の表示を含むかどうかを判定することと、
前記アクティブ化メッセージに対する受信された応答が、前記アクティブ化メッセージの拒否の表示を含むと判定される時に、前記再構成動作を再開始することと
をさらに備えることを特徴とする請求項１に記載のコンピュータ読取り可能記録媒体。
【請求項４】
前記ネットワークは、構成マネージャをさらに備え、
前記ノードの第２のセットは、主ノードを備え、
前記方法は、前記コンピュータ読取り可能記録媒体上にエンコードされた前記コンピュータ実行可能命令が、前記主ノード上の少なくとも１つのプロセッサ上で実行される時に、前記構成マネージャから構成要求を受信することに応答して実行されることを特徴とする請求項１に記載のコンピュータ読取り可能記録媒体。
【請求項５】
前記方法が、
前記ノードの第１のセットの識別子および前記ノードの第２のセットの識別子を含む前記構成コミットメッセージを、前記構成マネージャに送信すること
を備える方法であること
を特徴とする請求項４に記載のコンピュータ読取り可能記録媒体。
【請求項６】
ネットワーク内のノードの第１のセット上で複製されたデータパーティションを前記ネットワーク内のノードの第２のセット上で複製されたデータパーティションに再構成する再構成動作を行う方法であって、前記ノードの第１のセットは、ノードの現在アクティブなセットであり、前記ノードの第２のセットは、ノードの現在アクティブではないセットであり、前記ノードの第１のセットは、前記ノードの第１のセット内のノードの数を指定する第１の定数値と関連付けられ、前記ノードの第２のセットは、前記ノードの第２のセット内のノードの数を指定する第２の定数値と関連付けられ、前記方法は、前記ネットワーク内のノード上の少なくとも１つのプロセッサを動作させ、
前記ノードの第１のセットがノードの現在アクティブなセットであることをやめることを合図する非アクティブ化メッセージを前記ノードの第１のセットに送信することと、
少なくとも前記ノードの第１のセットのサブセット内の各ノードからの、前記非アクティブ化メッセージに対する応答であって、前記ノードの第１のセット内のノードから受信する各応答が前記非アクティブ化メッセージの受諾または拒否の表示を含む応答、を受信することと、
前記非アクティブ化メッセージの受諾の表示を含む受信された応答の数が、少なくとも前記ノードの第１のセットと関連付けられた前記第１の定数値であるかどうかを判定することと、
前記非アクティブ化メッセージの受諾の表示を含む受信された応答の数が、少なくとも前記ノードの第１のセットと関連付けられた前記第１の定数値である時に、前記ノードの第２のセットがノードの現在アクティブなセットになることを合図するアクティブ化メッセージを前記ノードの第２のセットに送信することと、
少なくとも前記ノードの第２のセットのサブセット内の各ノードからの、前記アクティブ化メッセージに対する応答であって、前記ノードの第２のセット内のノードから受信する各応答が前記アクティブ化メッセージの受諾または拒否の表示を包む応答、を受信することと、
前記アクティブ化メッセージの受諾の表示を含む受信された応答の数が、少なくとも前記ノードの第２のセットと関連付けられた前記第２の定数値であるかどうかを判定することと、
前記アクティブ化メッセージの受諾の表示を含む受信された応答の数が、少なくとも前記ノードの第２のセットと関連付けられた前記第２の定数値である時に、前記再構成動作を完了することと
を実行することを特徴とする方法。
【請求項７】
少なくとも前記ノードの第１のセットのサブセット内の各ノードから、前記非アクティブ化メッセージに対する応答を受信した後に、
前記非アクティブ化メッセージに対する受信された応答が、前記非アクティブ化メッセージの拒否の表示を含むかどうかを判定することと、
前記非アクティブ化メッセージに対する受信された応答が、前記非アクティブ化メッセージの拒否の表示を含むと判定される時に、前記再構成動作を再開始することと
をさらに備えることを特徴とする請求項６に記載の方法。
【請求項８】
少なくとも前記ノードの第２のセットのサブセット内の各ノードから、前記アクティブ化メッセージに対する応答を受信した後に、
前記アクティブ化メッセージに対する受信された応答が、前記アクティブ化メッセージの拒否の表示を含むかどうかを判定することと、
前記アクティブ化メッセージに対する受信された応答が、前記アクティブ化メッセージの拒否の表示を含むと判定される時に、前記再構成動作を再開始することと
をさらに備えることを特徴とする請求項７に記載の方法。
【請求項９】
前記ノードの第１のセットおよび前記ノードの第２のセット内の各セットが読み出し定数および書き込み定数と関連付けられ、
前記セットと関連付けられた読み出し定数および前記セットと関連付けられた書き込み定数のそれぞれは、セット内のノードの数を指定し、
前記セットと関連付けられた読み出し定数および前記セットと関連付けられた書き込み定数の総和が、セット内のノードの総数よりも大きく、
前記ノードの第１のセットと関連付けられた第１の定数値は、前記ノードの第１のセットと関連付けられた読み出し定数の値を含み、
前記ノードの第２のセットと関連付けられた第１の定数値は、前記ノードの第２のセットと関連付けられた書き込み定数の値を含む、
ことを特徴とする請求項６に記載の方法。
【請求項１０】
前記ノードの第１のセットは、バージョン識別子と関連付けられたセットであり、
前記方法は、
前記非アクティブ化メッセージを前記ノードの第１のセットに送信する前に、
前記ノードの第２のセットと関連付けられたバージョン識別子であって、前記ノードの第１のセットと関連付けられたバージョン識別子よりも大きい値を有するバージョン識別子、を選択することと、
前記ノードの第１のセットおよび前記ノードの第２のセットに、前記ノードの第２のセットと関連付けられた前記バージョン識別子を含む再構成提案を送信することと、
少なくとも前記ノードの第１のセットのサブセット内の各ノード、および、少なくとも前記ノードの第２のセットのサブセット内の各ノード、からの前記再構成提案に対する応答であって、前記ノードから受信された各応答が前記再構成提案の受諾または拒否の表示を含む応答、を受信することと、
前記再構成提案に対する受信された応答が前記再構成提案の拒否の表示を含むかどうかを判定することと、
受信された応答が前記再構成提案の拒否の表示を含むと判定される時に、
前記ノードの第２のセットと関連付けられた新しいバージョン識別子であって、前記再構成提案の拒否の表示を含む前記受信された応答に含まれるバージョン識別子よりも大きな値を有するバージョン識別子、を選択することと、
前記ノードの第１のセットおよび前記ノードの第２のセットに、前記ノードの第２のセットと関連付けられた前記新しいバージョン識別子を含む再構成提案を送信することと、
前記再構成提案の受諾の表示を含む前記ノードの第１のセットから受信された応答の第１の数が、少なくとも前記ノードの第１のセットと関連付けられた前記読み出し定数の値であるかどうかを判定することと、
前記再構成提案の受諾の表示を含む前記ノードの第２のセットから受信された応答の第２の数が、少なくとも前記ノードの第２のセットと関連付けられた前記書き込み定数の値であるかどうかを判定することと、
前記第１の数が少なくとも前記ノードの第１のセットと関連付けられた前記読み出し定数の値である、および、前記第２の数が少なくとも前記ノードの第２のセットと関連付けられた前記書き込み定数の値である、と判定されない時、前記再構成動作をサスペンドすることと
をさらに備えることを特徴とする請求項９に記載の方法。
【請求項１１】
前記データパーティションは、複数のトランザクションを格納するデータパーティションであり、
前記方法は、
前記第１の数が少なくとも前記ノードの第１のセットと関連付けられた前記読み出し定数の値である、および、前記第２の数が少なくとも前記ノードの第２のセットと関連付けられた前記書き込み定数の値であると判定された後に、
前記ノードの第２のセット内の各ノードに、更新された複製が少なくとも前記ノードの第１のセットのサブセット上でコミットされるものとして格納されていた各トランザクションを含み、前記ノードの第１のセットのサブセットのサイズが前記ノードの第１のセットと関連付けられた前記書き込み定数の値となるように、当該ノード上に格納されたデータパーティションの複製を更新することを命令することと、
前記データパーティションの複製を更新した前記ノードの第２のセットの数が、少なくとも前記ノードの第２のセットと関連付けられた前記書き込み定数の値であるかどうかを判定することと、
前記データパーティションの複製を更新した前記ノードの第２のセットの数が、少なくとも前記ノードの第２のセットの前記書き込み定数の値であると判定されない時、前記再構成動作をサスペンドすることと
をさらに備えることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記ノードの第２のセットは、主ノードを備え、
前記ネットワーク内のノード上の少なくとも１つのプロセッサを動作させることは、前記主ノード上の少なくとも１つのプロセッサを動作させることを備えることを特徴とする請求項６に記載の方法。
【請求項１３】
前記ネットワークは、構成マネージャをさらに備え、
前記主ノード上の少なくとも１つのプロセッサによって行われる動作は、前記構成マネージャから再構成要求を受信することに応答して行われる動作であること
を特徴とする請求項１２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散ストレージシステムにおける定数ベースのトランザクショナルに一貫性のあるメンバシップ管理に関する。
【背景技術】
【０００２】
コンピュータ技術の進歩（例えば、マイクロプロセッサの処理速度、メモリ容量、データ転送帯域幅、ソフトウェアの機能性等）は、さまざまな産業においてコンピュータ利用を増大させるのに広く貢献してきた。これまで以上に強力なサーバシステムは、しばしばサーバの配列として構成され、通常、例えば、ワールドワイドウェブ等の外部ソースに由来する要求を処理するために提供されている。
【０００３】
使用可能な電子データ量が増えるにつれて、そのようなデータを、ユーザフレンドリですばやくデータを探索および検索することを容易にする管理しやすい方法で格納することがより重要になる。今日、通常の手法は、電子データを１または複数のデータベースに格納することである。典型的なデータベースを、構造化されたデータを有する組織化された情報の集まりと呼ぶことができ、例えば、コンピュータプログラムが所望する個々のデータをすばやく探索して選択することができるようする。さらに、そのような環境において、フェデレーション(federation)は、お互いの間で信頼を築いていて、それらの間でユーザアイデンティティ情報を共有するのを可能にする組織またはサービスプロバイダのグループを指す。
【０００４】
ウェブサービス等の分散コンピューティングモデルの出現によって、サービスプロバイダ（ＳＰ）等のエンティティ間で相互依存性が増大している。それによって、現在の傾向は、内部使用のアイデンティティ管理ソリューションよりはむしろ、組織間および相互依存のアイデンティティ情報の管理に重点が置かれている。そのことをフェデレート型アイデンティティ管理と呼ぶことができる。一般的に、フェデレート型アイデンティティは、分散コンピューティングの構成概念であり、個々のアイデンティティが頻度を増大して企業の境界間を移動するのを認識する。フェデレート型アイデンティティの実用化は、いくつかの異種システムを同時に管理するように要求される大手多国籍企業に代表される。
【０００５】
このような分散システムにおいて、ノードの正しい管理および構成／再構成を行うにはさまざまな困難がある。例えば、個々のノードは、ランダムに失敗する可能性があり、それによって、適応するコンテンジェンシーが実行されない時にデータ損失を引き起こす可能性がある。同様に、複製されたデータは、しばしばシステムをあちこち移動するように要求されるので、信頼性の問題および一貫性の問題がさらに生じる可能性がある。
【０００６】
さらに、そのようなノード全体の管理に関連するデータが、例えば、集中型のキャッシュの失敗に起因する損失に影響される場合、信頼性の問題がさらに複雑になる可能性がある。
【発明の概要】
【０００７】
トランザクショナルデータストア内のデータを、冗長性または高い可用性を目的とする等、分散システム内のノードとして作用する多数のコンピュータまたは他のデバイスを通じて複製できる。しかしながら、分散システムが可用性の高い保証を提供できても、トランザクショナルデータストアが複製される下層のコンピュータ自体が信用できないことがあるので、分散システム内のノードを通じてトランザクショナルデータストアのトランザクションの一貫性を維持することは難しい。
【０００８】
ノードのセットの各ノード上で複製するように構成されたトランザクショナルデータストアを、異なるノードのセットの各ノード上で複製するように再構成できる。
【０００９】
部分的に定数を用いたトランザクショナルに一貫性のある方法で、現在の構成から新しい構成への再構成を行うことができる。現在および新しい構成のそれぞれを少なくとも１つの定数と関連付けることができ、その定数を構成内のノード数より少ないまたは等しくすることができる。動作が行われる構成内のノードの定数がその動作の承認を表示する場合のみ再構成動作が行われるように、再構成動作を選択的に行うことができる。
【００１０】
再構成プロセスは、新しい構成用の固有のバージョン識別子を選択すること、新しい構成内のノード上で複製されたトランザクショナルデータストアを更新して一貫性のある状態にすること、古い構成を非アクティブ化すること、および現在の構成をアクティブ化すること、を含むいくつかのステップを伴うことができる。構成内のノードの定数から受諾(acceptance)またはコミット(committal)を取得することを伴う再構成プロセスで、あるステップからその続のステップに進むことを要求することによって、その構成を通じて一貫性のレベルをなおも保証しながら、再構成プロセスが構成内のノードの失敗を回復できるようにすることが可能である。
【００１１】
前述は、添付の特許請求の範囲によって定義される発明の概要に限定されるものではない。
【００１２】
前述およびそれに関連する目的を達成するために、特許請求の範囲の主題の特定の図示された態様が、以下の説明および添付図面に関連して本明細書で説明される。これらの態様は、実施できるさまざまな方法を示すものであり、そのすべては、特許請求の範囲の主題の範囲内であることを意図とする。他の利点および新規な特徴は、図面とともに考慮される場合、以下の詳細な説明から明らかにすることができる。
【図面の簡単な説明】
【００１３】
添付図面は、一定の縮尺で描かれることを意図としない。図中、さまざまな図で図示された同一またはほぼ同一の各コンポーネントは、同種の数字によって表される。明確さを目的とするため、すべてのコンポーネントがすべての図で標示されているとは限らない。図は以下の通りである。
【図１】対象のイノベーションの特定の態様に従う、復元コンポーネントのブロック図である。
【図２】対象のイノベーションの特定の態様に従う、複数のノードと関連付けられた例示的なパーティショニングおよび再構築を示す図である。
【図３】対象のイノベーションの態様に従う、復元することができる構成コンポーネントを有するシステムのブロック図である。
【図４Ａ】対象のイノベーションの態様に従う、新しい構成を設定する方法を示す図である。
【図４Ｂ】再構成プロセスを実施できるネットワークのブロック図である。
【図４Ｃ】再構成プロセスのフローチャートである。
【図５】対象のイノベーションのさまざまな態様を実装するための例示的な環境を示す図である。
【図６】対象のイノベーションの態様に従う、データの検索に用いることができるサンプルコンピューティング環境の略ブロック図である。
【発明を実施するための形態】
【００１４】
対象のイノベーションのさまざまな態様について、添付図面を参照してこれから説明する。図中、同種の数字は、全体を通じて同種または一致する要素を指す。しかしながら、図およびそれに関連する詳細な説明は、特許請求の範囲の主題を開示される特定の形態に限定することを意図としないことを理解されたい。むしろ、その意図とするところは、特許請求の範囲の主題の精神および範囲内において、すべての変更、等価および代替を網羅することである。
【００１５】
発明者は、多数のコンピュータを通じてデータを複製できる分散コンピューティングシステムの出現によって、トランザクショナルに一貫性のある方法で複製されたデータを再構成する機構が必要であることを認識している。発明者は、分散システムを実装するのに使用される原コンピュータ自体が時々クラッシュすることがあっても、このような分散システムが頻繁にデータの高い可用性を提供する必要があることをさらに認識している。データベースの一部等のトランザクショナルデータをノードのセットを通じて複製でき、そのノード自体が信用できなくてもノードのセットを通じて複製されたデータに対してトランザクションの一貫性を維持する必要がある可能性があるので、そのセットにノードを付加または削除する必要があることがある。
【００１６】
それによって、本発明のすべての実施形態において、各ノードがトランザクショナルデータストアの複製を包含できるノードのセットを含む現在の構成を、異なるノードのセットを含む新しい構成にする再構成要求に応答して再構成でき、その間すべての複製されたトランザクショナルデータストアを通じてトランザクションの一貫性を維持することができる。
【００１７】
トランザクションの一貫性は、定数を用いた再構成プロセスの間中も維持され、そこで、古い構成および新しい構成のそれぞれを少なくとも１つの定数と関連付けることができる。その構成に対する再構成動作は、その構成内のノードの定数が動作の承認を表示するかどうかに基づいて選択的に処理されうる。再構成プロセスは、新しい構成用の固有のバージョン識別子を選択すること、新しい構成内のノード上で複製されたトランザクショナルデータストアを更新して一貫性のある状態にすること、古い構成を非アクティブ化すること、および現在の構成をアクティブ化すること、を含むいくつかのステップを伴うことができる。構成内のノードの定数から受諾(acceptance)またはコミット(committal)を取得することを要求する再構成プロセスで、あるステップからその続のステップに進むのを確実に行うことによって、その構成を通じて一貫性のレベルをなおも保証しながら、再構成プロセスが構成内のノードの失敗を回復できるようにする。
【００１８】
さらに、システムの他の態様は、復元コンポーネントを経由してノード（それらのノードは、読み出し／書き込み条件の動的定数を実装する分散システムと関連付けられる）の再構成に関連するデータ／情報を復元することに関連する。ある態様において、復元コンポーネントは、その分散システム自体を通じて情報の部分的コピーの複製を格納することを可能にする。このような分散型セグメントを用いて、一貫性のある方法で集中管理システムのコンテンツを復元することができる。それによって、復元コンポーネントは、集中管理コンポーネント／構成コンポーネントをキャッシュとして取り扱うことができるシステム上のさまざまな場所から集中管理コンポーネントのコンテンツを復元することができる。さらに、集中管理コンポーネントを分けるプロトコルを経由して拡張性を提供することができる（例えば、システムの他の部分の可用性を高くするのに用いられるのと同じプロトコルを用いる）。同様に、リーダーシップ選択(leadership election)のための集中管理コンポーネントを残りのシステムに用いることによって、柔軟性および拡張性が可能になる（典型的には、従来のコンセンサスベースのリーダーシップ選択のアルゴリズムを使用する場合には提供できない）。
【００１９】
図１に、分散システムのメンバの再構成に関連する情報の復元を可能にする、復元コンポーネント１０１を用いるシステム１００のブロック図を図示する。復元コンポーネント１０１は、リーダー選択コンポーネント(leader elector component)１０２と、主（例えば、アクティブな）構成マネージャインスタンス／コンポーネントと関連付けられた指定／動作を容易にすることができるクラスタ構成コンポーネント１０３とをさらに関連付けることができる。
【００２０】
図２に、例示的な態様に従って、定数ベースの手法を使用して構成マネージャコンポーネントを復元するシステム２００のブロック図を図示する。
【００２１】
図３に、主題のイノベーションの態様に従って、復元することができるリング３１０等の、分散環境の一部とする複数のノードとともに、構成マネージャコンポーネント３０２を実装するシステム３００のブロック図を図示する。構成マネージャコンポーネント３０２は、この変換中にデータ損失を軽減する、動的定数ベースの読み出し／書き込み条件を実装することによるトランザクショナルに一貫性のある方法で、古い構成から新しい構成を形成するノードの分散システム（例えば、サーバ）のメンバを再構成することができる。このような定数は、読み出し定数および書き込み定数の付加が構成のノード数を超える（例えば、所定の読み出しおよび書き込み定数が重複する）既定の数を表すことができる。
【００２２】
図４に、対象のイノベーションの態様にさらに従って復元することができるノードのネットワークを構成するさまざまなステージに関連する方法４００を図示する。再構成要求を受信すると、主複製の再構成エージェント(Reconfiguration Agent)は、古いまたは既存の構成の非アクティブ化を開始して、新しい構成のアクティブ化をさらに供給することができる（例えば、コミット(commit)がクライアントに肯定応答されたあらゆるトランザクションは、新しい構成によって格納されることを確保し、まだコミットされていないまたはコミットが肯定応答されていないトランザクションは、コミットまたはロールバックのどちらかが行われることを確保する）。このようなことは、４つのステージの実装を含むことができる。
【００２３】
（フェーズ１：４０２におけるバロットおよびキャッチアップ）
このフェーズ中、主複製は、新しい構成についてのグローバルな固有のＩＤを提案する。グローバルな固有のＩＤは、各連続構成を増加させることを意図とする。古い構成と新しい構成の両方の複製の定数によって受諾されると、このようなＩＤは、このパーティションに対して以前に受諾されたいかなるＩＤよりも大きく保証される。提案されたＩＤは、古い構成と新しい構成の両方の中にあるすべての複製に送信され、各構成は、それらが以前に観察したいかなるＩＤよりも保証が大きいかどうかに基づいてそのＩＤを受諾または拒否する。それによって、複製がこのようなＩＤを受諾する場合、その複製はさらに、主複製にその最新のトランザクションシーケンス番号を通知して、新しいトランザクションの受諾を停止する。
【００２４】
あるいは、複製が提案されたＩＤを拒否する場合、主複製は、新しくてより保証が大きいＩＤを選んでフェーズ１を再開始する。ひとたび古い構成と新しい構成の両方からの複製の定数が、提案されたＩＤを受諾したら、主複製が、新しい構成内の複製にキャッチアップを開始するように指示することによって、その再構成を通じてトランザクションの一貫性およびデータの安全要件は維持できるようになる。このようなことは、個々の複製に対するキャッチアップとトランザクションのロールバックとの混合を伴いうる。さらに、そのプロセスは、複製の定数がコンテンツの現在の状態に一致することが保証されて、その再構成を通じて、原子性(Atomicity)、一貫性(Consistency)、独立性(Isolation)、永続性(Durability)（ＡＣＩＤ）プロパティを提供する。ひとたび新しい構成内の複製の少なくとも１つの定数がキャッチアップされたら、フェーズ１を完了することができる。
【００２５】
（フェーズ２：４０４における古い構成の非アクティブ化）
このフェーズ中、主複製は、古い構成の非アクティブ化を調整する。非アクティブ化の目的は、Ｒ１≠Ｒ２となるようなＲ１とＲ２の複製の２セットを見つけるのを不可能にすることを保証することであり、Ｃ１＝Ｃ２でない限り、Ｒ１内の各複製ｒ１は構成Ｃ１が最新の構成であることを主張して、Ｒ１はＣ１の少なくとも書き込み定数を形成し、Ｒ２内の各複製ｒ２は構成Ｃ２が最新の構成であることを主張して、Ｒ２はＣ２の少なくとも書き込み定数を形成する。さらに、非アクティブ化メッセージを、古い構成内の各複製に送信することができる。それぞれの複製は、各複製が受諾した最新のバロット（ballot）提案に一致する場合、その非アクティブ化を受諾することができる。このフェーズは、複製の読み出し定数がその非アクティブ化に肯定応答する時に完了する。
【００２６】
（フェーズ３：４０６における新しい構成のアクティブ化）
このフェーズ中、主複製は、新しい構成のアクティブ化を調整する。アクティブ化の目的は、新しい構成の書き込み定数が、複製ユニットのコンテンツに対する変更が許可される前に構成がアクティブ化されていることを知ることを保証することである。そうすることで、ノードの定数が無効(lost)であればいかなるコンテンツの変更も無効(lost)にすることができることを確保することができる。アクティブ化メッセージをさらに、新しい構成内の各複製に送信することができる。それぞれのこれらの複製は、各複製が受諾した最新のバロット提案に一致する場合、そのアクティブ化を受諾することができる。このフェーズは、新しい構成内の複製の書き込み定数がアクティブ化を受諾した時に完了する。この時点で、その新しい構成は、アクティブで使用可能になる。
【００２７】
（フェーズ４：４０８におけるコミット）
フェーズ３の終りまでに古い構成が非アクティブ化されていて、新しい構成がアクティブ化されているので、このステージは、再構成をコミットするための選択的なフェーズである。その上、このステージは、グローバルな外部システム全体から主複製のみに知られる。それによって、このコミットフェーズは、この情報(knowledge)を分散システム内の関心があるすべてのパーティ(parties)中に分散する、つまり古い構成および新しい構成内の各複製に分散する。フェーズ４が実装されるかどうかにかかわらず、構成マネージャ(Configuration Manager)に、フェーズ３の完了後のどの時点でも再構成の完了を通知することができる。
【００２８】
図４Ｂおよび４Ｃは、上記の図４Ａで説明された再構成プロセスをより詳細に提供する。図４Ｂは、再構成プロセスを実施できる例示的なネットワーク４２０である。ネットワーク４２０は、図１−３と関連して上記で論じた構成マネージャコンポーネントと同様にできる構成マネージャ４２１を含む、適応する任意のコンピュータ通信媒体上で通信（例えば、無線または有線通信等）を行う複数のノードを含む。ネットワーク４２０も、現在の（すなわち「古い」）構成４２８内のノード４２２、ノード４２４およびノード４２６の第１のセットを含み、新しい構成４４８内のノード４４２、ノード４４４およびノード４４６の第２のセットを含む。ノードの第１のセットおよびノードの第２のセットは、お互いに対して適応する任意の関係を持つことができる。例えば、ノードの第１のセットおよびノードの第２のセットは、共通した１または複数のノードを持つことができ、それらのセットが、それぞれにノードの同じセットを備えることができる、またはノードの２セットを完全にバラバラにすることができる。構成マネージャ４２１を含む複数のノードである、ノード４２２．．．４２６およびノード４４２．．．４４６は、ハードウェアとソフトウェアとの適応する任意の組み合わせを含む、適応する任意の方法で実装できる。例えば、構成マネージャ４２１およびノード４４２．．．４４６は、それぞれ、適応する任意のコンピュータアーキテクチャを使用したデスクトップコンピュータまたはサーバコンピュータにすることができ、マイクロソフト社によって開発されたさまざまなウィンドウズ（登録商標）オペレーティングシステム等の、オペレーティングシステムを含むことができる。ある実施形態において、１または複数のノード、例えば、構成マネージャ４２１を、ロードバランシングまたは冗長性の目的等の、コヒーレントなユニットとして動作するように構成された複数のコンピュータ上で実装できる。
【００２９】
各ノードは、分散データの複製を包むストレージ媒体を包含するまたはそれに接続されることができる。ノード４２２、４２４および４２６のそれぞれは、複製４３２、４３４および４３６として図示された分散データの複製をそれぞれに含む。分散データは、分散ストレージシステムのコンポーネントにすることができる。例えば、ノード４２２、４２４および４２６上で複製された分散データは、データベース内のデータパーティション等の分散データベースの一部にすることができる。適応する任意の分散データベースを使用できる。ある実施形態において、マイクロソフト社によって開発されたさまざまなＳＱＬサーバ（登録商標）データベースを使用できる。上記で論じたように、複製４３２、４３４および４３６のそれぞれは、複数のトランザクションを格納できる。
【００３０】
再構成動作は、データが格納される方法で変更できる。図４Ｂで図示した現在の構成４２８のように、ノードの第１のセット上で複製されるよりはむしろ、再構成の後、現在の情報は、図４Ｂで図示した新しい構成４４８のように、ノードの第２のセット上で複製されるであろう。従って、少なくともその再構成プロセスが終わるまでに、新しい構成４２８内のノード４４２、４４４および４４６も、それぞれ、複製４５２、４５４および４５６をそれぞれに包含することができる。再構成プロセスは、新しい構成４４８内のノードが複製されるデータパーティションの複製を最初に包含しない場合、または新しい構成４４８内のノード上の複製が古くなっている場合等で、現在の構成４２８から新しい構成４４８へとデータの実移動を行うことを伴うことができる。しかしながら、ある実施形態またはあるシナリオにおいて、新しい構成内のノードは、再構成プロセスが主に、古い構成の非アクティブ化および新しい構成のアクティブ化を伴う場合、すでに最新のデータパーティションの複製を包含することができる。
【００３１】
ある実施形態において、再構成プロセスは、構成マネージャ４２１によって開始される。構成マネージャ４２１は、いくつかの理由で再構成を開始できる。例えば、再構成は、ノードまたは複製の失敗、ノードまたは複製のリカバリ、複製の再生、または他の管理動作を含む、さまざまなイベントをトリガーとすることができる。再構成プロセスを、ネットワーク内の適応する任意のノード上で実行できる。ある実施形態において、構成マネージャ４２１は、主に再構成プロセスを実装する責任を負うことができる一方、他の実施形態において、構成マネージャ４２１は、ネットワーク内の別のノードに再構成要求を発行し、次にその要求に応答して再構成プロセスを実行できる。ある実施形態において、新しい構成内のあるノードは、図４Ｂで「主再構成エージェント」ノード４４２として図示した「主ノード」として指定され、構成マネージャ４２８からの再構成要求に応答して再構成プロセスを実行する責任を負うことができる。再構成プロセスを実装することは、主ノード４４２および現在の構成４２８と新しい構成４４８の両方の中にある他のノードとやりとりする再構成メッセージ４５８および４５９等の、メッセージを送信することを伴うことができる。
【００３２】
図４Ｃに、再構成動作において定数ベースの処理を使用することができる複数の方法を図示する。図４Ｃに、分散データベースを再構成する一部として、古い構成を非アクティブ化することおよび新しい構成をアクティブ化すること等の再構成動作が行われることを図示する。これらの再構成動作のそれぞれを伴うノードの定数が、その再構成動作が行われることを表示するメッセージの受諾を表示しない場合、その再構成動作は進まない。反対に、再構成メッセージまたはコマンドに応答して再構成動作を伴う適切なノードの定数が受諾を表示する時、その再構成動作は進むことができる。
【００３３】
図４Ｃに図示したように、再構成プロセスは、データパーティションを現在の（すなわち「古い」）ノード構成から新しいノード構成に移動することを伴うことができる。論考において、図４Ｃで図示したプロセスは、新しい構成内の主ノード上で実装されると仮定されて、構成マネージャからの再構成要求の受信に応答して開始すると仮定されることに従っているが、図４Ｃのプロセスを、ネットワーク内の適応する任意のノード上で実装でき、適応する任意のイベント、トリガー(stimulus)、または条件に基づいて開始できる。
【００３４】
ある実施形態において、データパーティションの各構成をバージョン識別子と関連付けることによって、データパーティションの新しい構成が異なるバージョン番号と関連付けられるようにできる。バージョン識別子を実装するために適応する任意のスキームを選択できる一方で、ある実施形態において、データパーティションの新しい構成用のバージョン識別子も、以前にまたは現在そのデータパーティションと関連付けられたバージョン識別子用のその他の値よりも高位にしなければならない。従って、新しい構成用のバージョン識別子は、古い構成と関連付けられたバージョン識別子よりも高位にしなければならない。新しい構成と関連付けられたバージョン識別子を、そのデータパーティションの失敗した再構成と関連付けられたバージョン識別子を含む、そのデータパーティション用のその他の構成と関連付けられた任意のバージョン識別子よりも高位にするために意図する場合もある。しかし、他の実施形態において、他の機構を使用して、現在のバージョン識別子を確定できる。
【００３５】
ブロック４６０において、主ノードは、新しい構成と関連付けられたバージョン識別子用の新しい値を判定できる。ある実施形態において、主ノードは、古い構成と関連付けられたバージョン番号よりも高位の値を選択できる。主ノードは、次に、新しいバージョン識別子用のこの提案された値を包含するメッセージを、新しい構成と古い構成の両方のノードに送信できる。主ノードは、次に、ノードが新しい構成用にその提案されたバージョン識別子を受諾したことを表示する、少なくとも１つの新しい構成内のノードの定数および古い構成内のノードの定数からの応答を受信するまで待つことができる。
【００３６】
ある実施形態において、古い構成および新しい構成と関連付けられた定数は同じになるまたはその構成内のノードと同じ割合にできる。しかしながら、古い構成および新しい構成と関連付けられた定数が同じになるまたは同じ方法で判定されることが要件ではない。ある実施形態において、主ノードは、古い構成内のノードの読み出し定数が受諾されるのを待つ、および新しい構成内のノードの書き込み定数が受諾されるのを待つことができる。
【００３７】
ある実施形態において、再構成プロセスは、古い構成内のノードの読み出し定数および新しい構成内のノードの書き込み定数が提案されたバージョン識別子を受諾するまで進むことができない（即ち、サスペンドされる）。さらに、ある実施形態において、古い構成内のノードの読み出し定数および新しい構成内のノードの書き込み定数が新しく提案されたバージョン識別子を受諾した後でさえも、主ノードは、なおも所定の時間期間待つことができ、または他のイベントを待つことができ、複製が応答するのを遅くさせ、提案されたバージョン識別子を拒否する可能性もある。
【００３８】
ブロック４６２において、主ノードは、次に、新しい構成か、古い構成のどちらかにおいて、ノードが提案を拒否したことを表示する任意のノードからの応答を受信したかどうかをチェックできる。ノードは、いくつかの理由で提案されたバージョン識別子を拒否できる。例えば、ノードは、提案されたバージョン識別子よりも高位であるデータパーティションと関連付けられたバージョン識別子を以前に見つけた場合、ノードはその提案を拒否できる。そうである場合、拒否するノードは、そのバージョン識別子を以前に見つけたことを拒否応答で主ノードに送信できる。
【００３９】
プロセスは、次に、ブロック４６４に進むことができ、そこでプロセスが稼動しているノードが、なおも新しい構成用の主ノードであるかどうかを判定できる。ある実施形態において、いくつかの理由で、新しい構成用の主ノードは、構成マネージャからのコマンドに応答して行うことができる変更を行うことができる。再構成プロセスが稼動しているノードがブロック４６４において、そのノードはもはや主ノードではないと判定する場合、そのノードはブロック４６６において再構成プロセスを停止できる。図４Ｃの再構成プロセスは、この時点で終了される。
【００４０】
その他では、ブロック４６４において、再構成プロセスが稼動しているノードがなおも主ノードであると判定する場合、主ノードは、ブロック４６０に戻ることによって再構成プロセスを再開始できる。次に、上記で論じたプロセスを繰り返すことができ、今度は、新しい構成用に、新しく提案されたバージョン識別子を選択する。新しく提案されたバージョン識別子は、以前の提案に応答して送信した拒否メッセージに含まれたバージョン識別子を含む、その構成の以前に見つけたいかなるバージョン識別子よりも高位である。
【００４１】
その他では、主ノードがブロック４６２において、どのノードも提案を拒否しなかったと判定した場合、ブロック４６８において、主ノードは、古い構成内で複製された最新のデータを用いて新しい構成のノード内で複製されたデータを更新できる。これを、適応する任意の方法で行うことができる。ある実施形態において、この動作を２つのステップで行うことができる。最初に、主ノードが古い構成からの複製の最新のコピーを包含しない場合、主ノードは、最新データを用いて古い構成内のノードからのデータパーティションのそのローカル複製を更新（または「キャッチアップ」）できる。ある実施形態において、最新データを用いた古い構成内のノードは、ステップ４６０で論じたように、バージョン識別子を受諾した古い構成内のノードの中から選択される。ノードが最新データを包含すると判定することを、適応する任意の方法で行うことができる。ある実施形態において、それを、複製に格納された最新のトランザクションと関連付けられた識別子をチェックすることによって行うことができる。
【００４２】
ひとたび、主ノードが複製の最新コピーを有すると、ある実施形態において、主ノードは、次に、データパーティション上のユーザトランザクションを不能にでき、新しい構成内の他のノードにそれらの複製を更新するように命令できる。主ノードは、次に、新しい構成内のノードの書き込み定数が更新されるのを待つことができる。
【００４３】
ある実施形態において、複製を更新することは、その複製を更新して、古い構成内の複製の書き込み定数によってコミットされた少なくともすべてのトランザクションを格納することを伴うことができる。ある実施形態において、新しい構成内のノードの書き込み定数上の複製を更新して、トランザクションの一貫性のあるセットを格納できる。従って、新しい構成内の特定の複製が、古い構成内のノードの書き込み定数によってコミットされたトランザクションよりも後のトランザクションを包含する場合、複製を更新することは、トランザクションのロールバックも含むことができる。このような状態は、ユーザトランザクションがコミットされる前にそのトランザクションが停止されたことによって、そのトランザクションが古い構成内のノードの書き込み定数を満たさずに格納された場合に起こり得る。ある実施形態において、新しい構成内の複製の書き込み定数がトランザクションの一貫性のあるセットを格納するために更新されるまで再構成プロセスは進むことができない（即ち、サスペンドされる）。
【００４４】
ひとたび新しい構成内のノードの書き込み定数がキャッチアップされたら、再構成プロセスは、再構成メッセージを古い構成および／または新しい構成のノードに送信すること、およびそのメッセージを受諾するために与えられた構成内のノードの定数を待つことを伴うことができる。再構成メッセージは、例えば、アクティブ化メッセージまたは非アクティブ化メッセージを含むことができる。例えば、図４Ｃのブロック４７０において図示された例において、主ノードは、次に、非アクティブ化メッセージを古い構成内のノードに送信できる。非アクティブ化メッセージは、提案された新しい構成を備えることができ、その構成は、提案された新しい構成内のノードの識別子を含むことができる。古い構成内のノードが非アクティブ化メッセージを受諾する場合、その現在のアクティブな構成の状態を「非アクティブ化(Deactivated)」になるように変更でき、提案された新しい構成を、適応するコンピュータストレージ内の、ハードディスク等のノード上で格納できる。
【００４５】
古い構成内の各ノードも、ノードが非アクティブ化メッセージを受諾または拒否するかどうかを表示する応答を主ノードに返信するように構成できる。主ノードは、次に、古い構成内のノードからの、それらのノードが非アクティブ化メッセージを受諾したことを表示する応答の読み出し定数を待つことができる。
【００４６】
次に、ブロック４７２において、主ノードは、古い構成内の少なくとも１つのノードからの非アクティブ化メッセージに対する応答に、そのノードが非アクティブ化メッセージを拒否したことを表示させるかどうかを判定できる。いずれかのノードが非アクティブ化メッセージを拒否した場合、再構成プロセスは、ブロック４６４に進むことができ、その時点で再構成プロセスは、上記で論じたように、再開するか、停止するかのどちらかを行う。
【００４７】
その他では、ブロック４７２において、古い構成内のどのノードも非アクティブ化メッセージを受信しなかったと判定した場合、ひとたび古い構成内のノードの読み出し定数が、ブロック４７４において、再構成メッセージを受諾したことを表示したら、主ノードは、新しい構成のアクティブ化を開始できる。これは、アクティブ化メッセージを新しい構成内の他のすべてのノードに送信することによって行うことができる。新しい構成内の他のノードのそれぞれは、ノードがアクティブ化メッセージを受諾または拒否したかどうかを表示する応答を主ノードに送信するように構成されうる。ノードがアクティブ化メッセージを受諾する場合、そのノードは、適切に、自身の状態を「アクティブ化された」状態に更新できる。ある実施形態において、古い構成と新しい構成の両方の部分であるノードがすでに（例えば、アクティブ化メッセージを受諾した後）提案された構成として新しい構成の状態をローカルに格納した場合もあり、その場合、ブロック４７４において、格納された状態を「提案された状態」から「アクティブ化された状態」に更新できる。主ノードは、次に、新しい構成内のノードからの、それらのノードがアクティブ化メッセージを受諾したことを表示する応答の書き込み定数を待つことができる。
【００４８】
次に、ブロック４７６において、主ノードは、新しい構成内の少なくとも１つのノードからのアクティブ化メッセージに対する応答に、そのノードがアクティブ化メッセージを拒否したことを表示させるかどうかを判定できる。いずれかのノードがアクティブ化メッセージを拒否した場合、再構成プロセスは、ブロック４６４に進むことができ、その時点で再構成プロセスは、上記で論じたように、再開するか、停止するかのどちらかを行う。
【００４９】
しかしながら、新しい構成内のノードの書き込み定数がアクティブ化メッセージを受諾して、どのノードもそのアクティブ化メッセージを拒否しなかった場合、主ノードは、その構成上でトランザクションを再度可能にでき、構成マネージャ４２１等の構成マネージャに新しい構成がコミットされた状態を通知することもできる。プロセスは、ブロック４７８に進むこともでき、その時点で主ノードは、新しい構成をコミットできる。この選択的な動作は、古い構成と新しい構成の両方を含む構成コミットメッセージをネットワーク内のすべてのノードに送信して、データパーティションの複製を新しい構成に適応させることを伴うことができる。このステップは、選択的にすることができる。なぜならば、ある実施形態において、新しい構成は、アクティブになって、新しい構成内のノードの書き込み定数がアクティブ化メッセージを受諾したらすぐに完了することができるからである。この時点で、新しい構成は完全にアクティブ化されて使用可能にされるので、図４のプロセスを終了できる。
【００５０】
この適用で使用されたように、用語「コンポーネント」、「システム」は、コンピュータに関連したエンティティである、ハードウェア、ハードウェアとソフトウェアの組み合わせ、ソフトウェア、または実行中のソフトウェアのいずれかを指すことを意図する。例えば、コンポーネントは、プロセッサで稼動するプロセス、プロセッサ、オブジェクト、実行可能ファイル、実行スレッド、プログラム、および／またはコンピュータとすることができるが、これらに限らない。実例として、サーバ上で稼動するアプリケーションとそのサーバの両方をコンポーネントとすることができる。１または複数のコンポーネントは、プロセスおよび／または実行スレッド内に常駐することができ、コンポーネントを、１つのコンピュータ上にローカライズするおよび／または２または３以上のコンポーネント間で分散することができる。
【００５１】
さらに、対象のイノベーションのすべてまたは一部を、システム、方法、装置、または工業製品として実装することができ、ソフトウェア、ファームウェア、ハードウェア、またはそれらの任意の組み合わせを生産するための標準のプログラミングおよび／またはエンジニアリング技術を使用してコンピュータを制御して、開示されたイノベーションを実装できる。例えば、コンピュータ可読媒体は、磁気ストレージデバイス（例えば、ハードディスク、フロッピー（登録商標）ディスク、磁気帯）、光ディスク（例えば、コンパクトディスク（ＣＤ）、デジタル多用途ディスク（ＤＶＤ））、スマートカード、およびフラッシュメモリデバイス（例えば、カード、スティック、キードライブ）を含むことができるが、これに限らない。さらに、搬送波を用いて、電子メールの送受信またはインターネットまたはローカルエリアネットワーク（ＬＡＮ）等のネットワークにアクセスするのに使用されるようなコンピュータ可読の電子データを伝達することができることを認識されたい。もちろん、当業者は、特許請求の範囲の対象の範囲または精神から逸脱せずに、この構成に対して多数の変更を行うことができることを理解するであろう。
【００５２】
コンテキストを開示された発明の対象のさまざまな態様に提供するために、以下の考察とともに図５および図６では、開示された発明の対象のさまざまな態様を実装できる適応する環境の簡潔な概要を提供することを意図とする。発明の対象を、１つのコンピュータおよび／または複数のコンピュータ上で稼動するコンピュータプログラムのコンピュータ実行可能命令の一般的なコンテキストで上述してきたが、当業者は、本イノベーションは他のプログラムモジュールとの組み合わせにおいても実装できることを認識するであろう。一般的に、プログラムモジュールは、ルーチン、プログラム、コンポーネント、データ構造等を含み、それらは特定のタスクを実行するおよび／または特定の抽象データ型を実装する。さらに、革新的な方法は、パーソナルコンピュータ、ハンドヘルドコンピューティングデバイス（例えば、ＰＤＡ（Personal Digital Assistant）、電話機、時計）、マイクロプロセッサベースまたはプログラム可能な消費者または工業用電化製品等に加え、単一のプロセッサまたはマルチプロセッサコンピュータシステム、ミニコンピューティングデバイス、メインフレームコンピュータを含む、他のコンピュータシステム構成を用いて実施することができることを当業者は認識するであろう。図示した態様も、通信ネットワークでリンクされたリモート処理デバイスによってタスクが行われる分散コンピューティング環境で実施できる。しかしながら、本イノベーションのすべての態様ではないにしても一部を、スタンドアロンコンピュータ上で実施することができる。分散コンピューティング環境において、プログラムモジュールをローカルメモリストレージデバイスとリモートメモリストレージデバイスの両方に配置できる。
【００５３】
図５を参照して、対象のイノベーションのさまざまな態様を実装するために、コンピュータ５１２を含む例示的な環境５１０について説明する。コンピュータ５１２は、処理ユニット５１４、システムメモリ５１６、およびシステムバス５１８を含む。システムバス５１８は、システムメモリ５１６を含むシステムコンポーネントを処理ユニット５１４に接続するが、これに限らない。処理ユニット５１４は、さまざまに使用可能なプロセッサのいずれにもすることができる。デュアルマイクロプロセッサおよび他のマルチプロセッサのアーキテクチャも処理ユニット５１４として用いることができる。
【００５４】
システムバス５１８は、メモリバスまたはメモリコントローラ、周辺バスまたは外部バス、および／またはさまざまに利用可能なバスアーキテクチャを任意に使用するローカルバスを含む数種類のバス構造（複数可）のいずれにもすることができ、それらのバスアーキテクチャは、ＩＩビットバス、ＩＳＡ（Industrial Standard Architecture）、ＭＣＡ（Micro-Channel Architecture）、ＥＩＳＡ（Extended ISA）、ＩＤＥ（Intelligent Drive Electronics）、ＶＬＢ（VESA Local Bus）、ＰＣＩ（Peripheral Component Interconnect）、ＵＳＢ（Universal Serial Bus）、ＡＧＰ（Advanced Graphics Port）、ＰＣＭＣＩＡ（Personal Computer Memory Card International Association bus）、およびＳＣＳＩ（Small Computer Systems Interface）を含むが、これに限らない。
【００５５】
システムメモリ５１６は、揮発性メモリ５２０および不揮発性メモリ５２２を含む。起動時等の、コンピュータ５１２内で情報を要素間で転送する基本ルーチンを包含する基本入出力システム（ＢＩＯＳ）は、不揮発性メモリ５２２に格納される。例えば、不揮発性メモリ５２２は、リードオンリーメモリ（ＲＯＭ）、プログラム可能なＲＯＭ（ＰＲＯＭ）、電子的にプログラム可能なＲＯＭ（ＥＰＲＯＭ）、電子的に消去可能なＲＯＭ（ＥＥＰＲＯＭ）、またはフラッシュメモリを含むことができる。揮発性メモリ５２０は、外部キャッシュメモリとして作用するランダムアクセスメモリ（ＲＡＭ）を含む。ＲＡＭは、同期ＲＡＭ（ＳＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、同期ＤＲＡＭ（ＳＤＲＡＭ）、二重データレートＳＤＲＡＭ（ＤＤＲ  ＳＤＲＡＭ）、拡張ＳＤＲＡＭ（ＥＳＤＲＡＭ）、同期リンクＤＲＡＭ（ＳＬＤＲＡＭ）、およびダイレクトラムバスＲＡＭ（ＤＲＲＡＭ）等の多数の形態に使用可能であるが、実例としてであり、これらに限らない。
【００５６】
コンピュータ５１２は、リムーバブル／ノンリムーバブル、揮発性／不揮発性コンピュータストレージ媒体も含む。図５に、ディスクストレージ５２４を図示するが、このようなディスクストレージ５２４は、磁気ディスクドライブ、フロッピーディスクドライブ、テープドライブ、ジャズドライブ、ジップドライブ、ＬＳ−６０ドライブ、フラッシュメモリカード、またはメモリスティックのようなデバイスを含むが、これに限らない。さらに、ディスクストレージ５２４は、ストレージ媒体を個別にして含むか、またはコンパクトディスクＲＯＭデバイス（ＣＤ−ＲＯＭ）、書き込み可能なＣＤドライブ（ＣＤ−Ｒ−Ｄｒｉｖｅ）、書き換え可能なＣＤドライブ（ＣＤ−ＲＷ−Ｄｒｉｖｅ）またはデジタル多用途ディスクＲＯＭドライブ（ＤＶＤ−ＲＯＭ）等の光学ディスクドライブを含む他のストレージ媒体との組み合わせにおいて含むことができるが、これらに限らない。ディスクストレージデバイス５２４がシステムバス５１８へ接続するのを容易にするために、インタフェース５２６等のリムーバブルまたはノンリムーバブルなインタフェースが典型的には使用される。
【００５７】
図５は、適応するオペレーティング環境５１０で説明されるユーザと基本コンピュータリソースとの間の中間として作用するソフトウェアを説明していることが認識されよう。このようなソフトウェアは、オペレーティングシステム５２８を含む。ディスクストレージ５２４上に格納することができるオペレーティングシステム５２８は、コンピュータシステム５１２のリソースを制御して割り付けるために作用する。システムアプリケーション５３０は、システムメモリ５１６か、ディスクストレージ５２４のどちらかに格納されるプログラムモジュール５３２およびプログラムデータ５３４を介したオペレーティングシステム５２８によってリソースの管理を利用する。さまざまなオペレーティングシステムまたはオペレーティングシステムの組み合わせを用いて本明細書で説明したさまざまなコンポーネントを実装することができることが認識されよう。
【００５８】
ユーザは、入力デバイス（複数可）５３６を介してコマンドまたは情報をコンピュータ５１２に入力する。入力デバイス５３６は、マウス、トラックボール、タッチペン、タッチパッド、キーボード、マイクロフォン、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナ、ＴＶチューナーカード、デジタルカメラ、デジタルビデオカメラ、ウェブカメラ等のポインティングデバイスを含むが、これに限らない。これらと他の入力デバイスは、インタフェースポート（複数可）５３８経由のシステムバス５１８を介して処理ユニット５１４に接続する。インタフェースポート（複数可）５３８は、例えば、シリアルポート、パラレルポート、ゲームポート、およびユニバーサルシリアルバス（ＵＳＢ）を含む。出力デバイス（複数可）５４０は、入力デバイス（複数可）５３６と同じ種類のポートのいくつかを使用する。従って、例えば、ＵＳＢポートを使用してコンピュータ５１２に入力を提供して、コンピュータ５１２から出力デバイス５４０に情報を出力できる。出力アダプタ５４２は、専用アダプタを必要とする出力デバイス５４０の中でもとりわけ、モニタ、スピーカ、およびプリンタのようないくつかの出力デバイス５４０があることを図示するために提供される。出力アダプタ５４２は、出力デバイス５４０とシステムバス５１８との間の接続手段を提供するビデオおよび音声カードを含むが、実例としてであり、これらに限らない。他のデバイスおよび／またはデバイスのシステムは、リモートコンピュータ（複数可）５４４等の入力能力と出力能力の両方を提供することに留意されたい。
【００５９】
コンピュータ５１２は、リモートコンピュータ（複数可）５４４等の１または複数のリモートコンピュータへの論理接続を使用してネットワーク環境において動作することができる。リモートコンピュータ（複数可）５４４は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ワークステーション、マイクロプロセッサベースの電化製品、ピアデバイスまたは他の共通ネットワークのノード等にすることができ、典型的には、コンピュータ５１２に関連して説明した要素の多数またはすべてを含む。簡潔にするために、メモリストレージデバイス５４６のみが、リモートコンピュータ（複数可）５４４とともに図示されている。リモートコンピュータ（複数可）５４４は、ネットワークインタフェース５４８を介してコンピュータ５１２に論理的に接続されて、次に、通信接続５５０を経由して物理的に接続される。ネットワークインタフェース５４８は、ローカルエリアネットワーク（ＬＡＮ）およびワイドエリアネットワーク（ＷＡＮ）等の通信ネットワークを網羅する。ＬＡＮ技術は、光ファイバー分散データインタフェース（ＦＤＤＩ）、銅分散データインタフェース（ＣＤＤＩ）、イーサネット／ＩＥＥＥ８０２．３、トークンリング／ＩＥＥＥ８０２．５等を含む。ＷＡＮ技術は、ポイントツーポイントリンク、統合サービスデジタルネットワーク（ＩＳＤＮ）およびその変形等の回路交換ネットワーク、パケット交換ネットワーク、およびデジタル加入者回線（ＤＳＩ）を含むが、これに限らない。
【００６０】
通信接続（複数可）５５０は、ネットワークインタフェース５４８をバス５１８に接続するのに用いられるハードウェア／ソフトウェアを指す。通信接続５５０がコンピュータ５１２内部で図解して示されているが、それをコンピュータ５１２の外部接続にすることもできる。ネットワークインタフェース５４８の接続に必要なハードウェア／ソフトウェアは、単なる例示を目的として、通常の電話のグレードのモデム、ケーブルモデムおよびＤＳＬモデムを含むモデム、ＩＳＤＮアダプタ、およびイーサネットカード等の内部および外部技術を含む。
【００６１】
図６は、対象のイノベーションの態様に従って、フェデレーションの一部としてノードを実装するために用いることができるサンプルコンピューティング環境６００の略ブロック図である。システム６００は、１または複数のクライアント（複数可）６１０を含む。クライアント（複数可）６１０は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティングデバイス）にすることができる。システム６００は１または複数のサーバ（複数可）６３０も含む。サーバ（複数可）６３０も、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティングデバイス）にすることができる。サーバ６３０は、スレッドを収容(house)して、例えば、本明細書で説明したコンポーネントを用いることによってトランザクションを行うことができる。クライアント６１０とサーバ６３０との間で可能な１つの通信を、２または３以上のコンピュータプロセス間で送信されるのに適用されるデータパケットの形式にすることができる。システム６００は、クライアント（複数可）６１０とサーバ（複数可）６３０との間の通信を容易にするのに用いることができる通信フレームワーク６５０を含む。クライアント（複数可）６１０は、情報をクライアント（複数可）６１０にローカルに格納するのに用いることができる１または複数のクライアントデータストア（複数可）６６０に動作可能なように接続される。同様に、サーバ（複数可）６３０は、情報をサーバ６３０にローカルに格納するのに用いることができる１または複数のサーバデータストア（複数可）６４０に動作可能なように接続される。
【００６２】
この発明の少なくとも１つの実施形態のうちのいくつかの態様をこのように説明したので、当然ながら、さまざまな代替、変更、および改良が当業者に容易には思いつくであろう。可能な変形の例として、上述した例示的な実施形態において、ノードの定数はそのノードの最大数になるように選択された。ノードの最大数よりも大きいか、少ないかのどちらかになる定数を用いて他の実装も可能である。さらに、定数は、ノード障害またはオフラインとなる構成に対して時間を変更することができる。
【００６３】
このような代替、変更、および改良は、この開示の一部であることを意図として、発明の精神および範囲内であることを意図とする。したがって、前述の説明および図面は単なる実例である。
【００６４】
上述した本発明の実施形態をあらゆる方法で実装することができる。例えば、ハードウェア、ソフトウェアまたはそれらの組み合わせを使用して実施形態を実装できる。ソフトウェアにて実装する場合、単一のコンピュータで提供される、または複数のコンピュータ内に分散されるにかかわらず、適応する任意のプロセッサまたはプロセッサ群上でソフトウェアコードを実行することができる。
【００６５】
さらに、コンピュータを、ラックマウント型コンピュータ、デスクトップコンピュータ、ラップトップコンピュータ、またはタブレットコンピュータ等のいくつかの形態のいずれかに実施できることを認識されたい。さらに、コンピュータを、一般的にはコンピュータと見なされないが、適応する処理能力を有するデバイスに組み込むことができ、そのデバイスは、パーソナルデジタルアシスタント（ＰＤＡ）、スマートフォンまたは適応するその他の移動式または固定式電子デバイスを含む。
【００６６】
また、コンピュータは、１または複数の入出力デバイスを有することができる。これらのデバイスは、とりわけユーザインタフェースを提供するのに使用することができる。ユーザインタフェースを提供するのに使用することができる出力デバイスの例は、プリンタまたは視覚表示出力用のディスプレイスクリーンおよび可聴表示出力用のスピーカまたは他の音を発生させるデバイスを含む。ユーザインタフェースに使用することができる入力デバイスの例は、キーボード、およびマウス、タッチパッド、およびデジタルタブレット等のポインティングデバイスを含む。別の例として、コンピュータは、音声認識を介してまたは可聴なフォーマットで入力情報を受信できる。
【００６７】
このようなコンピュータは、企業ネットワークまたはインターネット等のローカルエリアネットワークまたはワイドエリアネットワークとして含む、適応する任意の形式の１または複数のネットワークによって相互接続される。このようなネットワークは、適応する任意の技術に基づくことができ、適応する任意のプロトコルに従って動作でき、無線ネットワーク、有線ネットワークまたは光ファイバーネットワークを含むことができる。
【００６８】
また、本明細書で概要を説明したさまざまな方法またはプロセスは、さまざまなオペレーティングシステムまたはプラットフォームのうちのいずれかに用いる１または複数のプロセッサ上で実行可能なソフトウェアとしてコード化される。さらに、このようなソフトウェアを、いくつかの適応するプログラミング言語および/またはプログラミングまたはスクリプティングのツールのいずれかを使用して書き込むことができ、フレームワークまたは仮想マシン上で実行される実行可能なマシン語コードまたは中間コードとしてコンパイルすることもできる。
【００６９】
この点において、本発明を、１または複数のプログラムを用いてエンコードされる１つのコンピュータ可読媒体（または複数のコンピュータ可読媒体）（例えば、コンピュータメモリ、１または複数のフロッピーディスク、コンパクトディスク、光ディスク、磁気テープ、フラッシュメモリ、ＦＰＧＡ(Field Programmable Gate Arrays)または他の半導体デバイス内の回路構成、または他の有形のコンピュータストレージ媒体）として実施することができ、そのプログラムが１または複数のコンピュータまたは他のプロセッサ上で実行される場合、上記で論じた発明のさまざまな実施形態を実装する方法を行う。１つまたは複数のコンピュータ可読媒体を可搬型(transportable)にすることができることによって、それらの上に格納された１つまたは複数のプログラムを１または複数の異なるコンピュータまたは他のプロセッサ上にロードして、上述した本発明のさまざまな態様を実施できるようにする。
【００７０】
用語「プログラム」または「ソフトウェア」は、本明細書では、コンピュータまたは他のプロセッサをプログラムして、上記で論じたような本発明のさまざまな態様を実装するのに用いることができるコンピュータコードまたはコンピュータ実行可能命令のセットの任意の種類を指す一般的な意味で使用される。さらに、この実施形態の１つの態様に従って、実行された時に本発明の方法を行う１または複数のコンピュータプログラムは、単一のコンピュータまたはプロセッサ上に常駐する必要がないが、いくつかの異なるコンピュータまたはプロセッサの中のモジュラー方式で分散して、本発明のさまざまな態様を実装できることを認識されたい。
【００７１】
コンピュータ実行可能命令を、１または複数のコンピュータまたは他のデバイスによって実行されるプログラムモジュール等の多数の形態にすることができる。一般的に、プログラムモジュールは、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含み、特定のタスクを実行するまたは特定の抽象データ型を実装する。典型的には、プログラムモジュールの機能性を、組み合わせるまたはさまざまな実施形態に要望通りに分散できる。
【００７２】
また、データ構造を適応する任意の形態でコンピュータ可読媒体に格納できる。説明を簡潔にするために、データ構造をデータ構造内の場所に関連するフィールドを有するように示すことができる。このような関係は、同様に、フィールド間の関係を伝達するコンピュータ可読媒体の場所にフィールド用のストレージを割り当てることによって達成できる。しかしながら、適応する任意の構造を使用して、ポインタ、タグまたはデータ要素間の関係を確立する他の構造の使用を含むデータ構造のフィールド内の情報間の関係を確立できる。
【００７３】
本発明のさまざまな態様を、単独で、組み合わせにおいて、または前述した実施形態で特に論じていないさまざまな配置に使用できるので、前述の説明または図示されたコンポーネントの詳細および配置にその適用を限定されない。例えば、一実施形態で説明した態様を、他の実施形態で説明した態様を用いた任意の方法で組み合わせることができる。
【００７４】
また、本発明を、例示が提供された方法として実施できる。その方法の一部として行われた作用を適応する任意の方法で順序付けることができる。それによって、実施形態を、作用が図示されたものとは異なる順序で行われるものを構築でき、図示された実施形態の連続的作用として示されていても、ある作用を同時に行うことを含むことができる。
【００７５】
特許請求の範囲において「第１の」、「第２の」、「第３の」等の普通の用語を使用して請求の要素を変更すること自体は、優先、先行、または方法の作用が行われる別のまたは一時的な順序に勝る１つの請求の要素の順序を暗示しないが、単に、特定の名前を有するある請求の要素を同じ名前を有する別の要素と区別して（普通の用語の使用がなければ）、請求の要素を区別するラベルとして使用される。
【００７６】
また、本明細書で使用された表現および用語は、説明を目的とし、限定するものとして見なすべきではない。本明細書の「含む(including)」、「備える(comprising)」、または「有する(having)」、「包含する(containing)」、「伴う(involving)」およびそれらの変形は、付加的な項目とともにその後に記載される項目およびそれらの等価物を網羅することを意図とする。
【図１】
0005580831.tif 000002
【図２】
0005580831.tif 000003
【図３】
0005580831.tif 000004
【図４Ａ】
0005580831.tif 000005
【図４Ｂ】
0005580831.tif 000006
【図４Ｃ】
0005580831.tif 000007
【図５】
0005580831.tif 000008
【図６】
0005580831.tif 000009