フェデレーションインフラストラクチャ内の一貫性
【課題】ノード責任が不適当にオーバーラップしないことを保証するためのセーフティ機構とメッセージが1つのターゲットに繰り返して送信される場合にそのメッセージが受け入れられることを保証するためのライブネス機構を提供する。
【解決手段】プライマリノードは、プライマリノードおよび他のセカンダリノードを含むノードの複製セット内から選ばれたことが判定され、クライアントデータアクセス要求を受け入れ、処理し、各クライアントデータアクセス要求にクライアントデータアクセス要求が受信された順序で状態を変化させる線形化された処理順序を含むデータシーケンス番号を割り当て、すべての対応するデータシーケンス番号を含む変化するクライアントデータアクセス要求をセカンダリノードに送信し、閾値個数のセカンダリノードから、クライアントデータアクセス要求の受信を示す肯定応答を受信し、アクセス要求を変化させるデータをコミットする。
【解決手段】プライマリノードは、プライマリノードおよび他のセカンダリノードを含むノードの複製セット内から選ばれたことが判定され、クライアントデータアクセス要求を受け入れ、処理し、各クライアントデータアクセス要求にクライアントデータアクセス要求が受信された順序で状態を変化させる線形化された処理順序を含むデータシーケンス番号を割り当て、すべての対応するデータシーケンス番号を含む変化するクライアントデータアクセス要求をセカンダリノードに送信し、閾値個数のセカンダリノードから、クライアントデータアクセス要求の受信を示す肯定応答を受信し、アクセス要求を変化させるデータをコミットする。
Notice: Undefined index: DEJ in /mnt/www/gzt_disp.php on line 298
【特許請求の範囲】
【請求項1】
両方向ルーティング用に構成されたノードのリングのフェデレーションインフラストラクチャ内で、フェデレーションインフラストラクチャ内で維持される複製セット内でデータアクセストランザクションを実行する方法であって、
プライマリノードがノードの複製セット内の複数のノードの中から選ばれたことを判定する行為であって、前記プライマリノードは、クライアントデータアクセス要求を受け入れ、処理するように構成され、前記複製セットは、前記プライマリノードおよび1つまたは複数のセカンダリノードを含む、行為と、
前記プライマリノードが、1つまたは複数のクライアントデータアクセス要求を受信する行為であって、各データアクセス要求は、前記複製セット内で少なくとも前記プライマリノード上でアクセスされるデータの少なくとも一部を示す、行為と、
前記プライマリノードが、前記クライアントデータアクセス要求が受信される順序で状態を変化させる前記クライアントデータアクセス要求のそれぞれにデータシーケンス番号を割り当てる行為であって、前記データシーケンス番号は、前記複製セット内の前記ノードのそれぞれによって従われる線形化された処理順序を含む、行為と、
前記プライマリノードが、任意の対応するデータシーケンス番号を含む前記クライアントデータアクセス要求のうちの少なくとも1つを前記セカンダリノードのうちの少なくとも1つに送信する行為と、
前記プライマリノードが、少なくとも閾値個数のセカンダリノードから、前記クライアントデータアクセス要求の受信を示す肯定応答を受信する行為と、
前記プライマリノードが、前記データアクセス要求をコミットする行為であって、前記コミットは、前記クライアントデータアクセス要求に従ってデータにアクセスすることを含む、行為と
を含むことを特徴とする方法。
【請求項2】
前記プライマリノードは、前記データアクセス要求を単一フェーズでコミットすることを特徴とする請求項1に記載の方法。
【請求項3】
ノードの前記複製セット内の複数のノードの間からプライマリノードを選ぶ行為をさらに含むことを特徴とする請求項1に記載の方法。
【請求項4】
許容可能な同時障害の最大個数に基づいて、前記複製セットのメンバになるセカンダリノードの個数を判定する行為をさらに含むことを特徴とする請求項1に記載の方法。
【請求項5】
前記肯定応答は、前記クライアントデータアクセス要求の受入または拒否のうちの少なくとも1つを示すことを特徴とする請求項1に記載の方法。
【請求項6】
前記閾値個数のセカンダリノードは、クォーラムを表すことを特徴とする請求項1に記載の方法。
【請求項7】
プライマリになるはずのノードが、前記プライマリになるはずのノードが知らないすべてのトランザクションを判定するために前記クォーラムのセカンダリノードに要求を送信する行為をさらに含むことを特徴とする請求項6に記載の方法。
【請求項8】
前記クォーラムの各メンバが、少なくとも、LSNによって順序付けられる各メンバのデータアクセスキューに前記クライアントデータアクセス要求を挿入したことの表示を前記クォーラムの各メンバから受信することをさらに含むことを特徴とする請求項6に記載の方法。
【請求項9】
データの一部は、LSN、CSN、DSN、プライマリノードアイデンティティ、およびセカンダリノードアイデンティティのうちの少なくとも1つを含む、前記複製セット自体に関する制御情報のセットを含むことを特徴とする請求項1に記載の方法。
【請求項10】
前記データアクセス要求を単一フェーズでコミットすることは、前記セカンダリノードのいずれかに関してコミットクエリを送信することおよび受信することを伴わずに前記データにアクセスすることを含むことを特徴とする請求項1に記載の方法。
【請求項11】
前記クライアントデータアクセス要求を第2複製セットに送信する行為をさらに含み、前記第2複製セットは、前記プライマリノードの近傍とは異なる近傍内にあることを特徴とする請求項1に記載の方法。
【請求項12】
前記複製セットは、前記クライアントデータアクセス要求の第1部分を処理することを要求され、前記第2複製セットは、前記データアクセス要求の第2の異なる部分を処理することを要求されることを特徴とする請求項11に記載の方法。
【請求項13】
前記クライアントデータアクセス要求の前記第1部分に対応する前記複製セットからの応答を受信する行為と、
前記データアクセス要求の前記第2の異なる部分に対応する前記第2複製セットからの応答を受信する行為と、
前記応答を組み合わせる行為と、
前記組み合わされた応答に基づいて、最新のデータアクセス応答を生成する行為と
をさらに含むことを特徴とする請求項12に記載の方法。
【請求項14】
両方向ルーティング用に構成されたノードのリングのフェデレーションインフラストラクチャ内で、フェデレーションインフラストラクチャ内の複製セットからデータにアクセスするシステムであって、
前記リング上の複数のノードの近傍を確立するように構成された近傍確立モジュールであって、前記近傍は、少なくとも直接に隣接する先行ノードおよび直接に隣接する後続ノードを含む、近傍確立モジュールと、
前記確立された近傍の外の参加するノードが、ノードの前記リング内の前記確立された近傍に参加する意図を示したことを判定するように構成された意図判定モジュールと、
前記複数のノード内の各ノードが前記近傍内のid空間の一部のid空間オーナーシップをとるように、前記確立された近傍内の一貫性を維持するように構成された一貫性維持モジュールと、
前記複数のノード内の前記ノードの1つが、プライマリノードによって向けられるクライアントデータアクセス要求に応答するように構成されたノードの複製セットにまたがる責任を有する前記プライマリノードになるために選ばれたことを判定するように構成された選出判定モジュールと、
1つまたは複数のクライアントデータアクセス要求を受信するように構成された要求受信モジュールであって、各データアクセス要求は、前記複製セット内の前記ノードのうちの少なくとも1つでアクセスされるデータの少なくとも一部を示す、要求受信モジュールと、
前記クライアントデータアクセス要求内で示されるデータにアクセスするように構成されたデータアクセスモジュールと
を含むことを特徴とするシステム。
【請求項15】
前記データアクセスモジュールは、クライアントデータ書き込み要求に従ってデータを書き込むように構成されることを特徴とする請求項14に記載のシステム。
【請求項16】
前記プライマリノードは、セカンダリノードに、前記クライアントデータ書き込み要求内で示される前記データを前記セカンダリノードによって管理されるデータストアに書き込むように指示することを特徴とする請求項15に記載のシステム。
【請求項17】
前記プライマリノードは、前記書き込み要求を1つまたは複数のセカンダリノードに2フェーズで複製することを特徴とする請求項15に記載のシステム。
【請求項18】
前記データアクセスモジュールは、クライアントデータ読み取り要求に従ってデータを読み取るように構成されることを特徴とする請求項14に記載のシステム。
【請求項19】
前記クライアントデータ読み取り要求は、セカンダリノードによって直接に処理されることを特徴とする請求項18に記載のシステム。
【請求項20】
プライマリの前記確立された近傍は、そのプライマリの複製セットのセカンダリノードのセットであることを特徴とする請求項14に記載のシステム。
【請求項21】
両方向ルーティング用に構成されたノードのリングのフェデレーションインフラストラクチャ内で、フェデレーションインフラストラクチャ内の一貫した複製セットを確立し、維持する方法であって、
ノードのリング内の複数のノードの中から複製セットを確立する行為であって、前記複製セットは、メンバとしてプライマリノードおよび1つまたは複数のセカンダリノードを含む、行為と、
前記複製セットメンバのうちの少なくとも1つに影響する複製セット構成イベントオカレンスを示す表示を受信する行為と、
前記受信された表示に基づいて、前記複製セットが再構成されなければならないことを判定する行為であって、前記再構成は、前記複製セット構成イベントオカレンスに基づいて、前記複製セットからの既存セカンダリノードの除去、前記複製セットへの新しいセカンダリノードの追加、新しいプライマリへの突然の推移、および新しいプライマリへの滑らかな推移のうちの少なくとも1つを含む、行為と、
前記複製セット構成イベントに対応する前記再構成に従って前記複製セットを再構成する行為と
を含むことを特徴とする方法。
【請求項22】
前記複製セット構成イベントは、前記複製セット内のノード障害、前記複製セットからのノード離脱、およびノードが前記複製セットに参加することのうちの少なくとも1つを含むことを特徴とする請求項21に記載の方法。
【請求項23】
前記複製セットノードのうちの1つまたは複数によって制御されるデータストレージの一部を維持する行為をさらに含むことを特徴とする請求項21に記載の方法。
【請求項24】
前記プライマリノードがクライアントデータアクセス要求を受信する行為であって、前記クライアントデータアクセス要求は、ノードの複製セット内の少なくとも1つのノードでアクセスされる情報の表示を含む、行為と、
前記プライマリノードが前記受信されたクライアントデータアクセス要求内で示される情報の少なくとも一部にアクセスするのに失敗したことを検出する行為と、
前記プライマリノードに格納された情報が前記クライアントデータアクセス要求に応答してアクセスされるのを防ぐように、前記プライマリノードが前記複製セットからそれ自体を除去する行為と
をさらに含むことを特徴とする請求項23に記載の方法。
【請求項25】
構成状態情報に基づいて、進行中の1つまたは複数の複製セット再構成を検出する行為をさらに含むことを特徴とする請求項21に記載の方法。
【請求項26】
前記複製セットの新しいプライマリノードを選ぶ行為をさらに含むことを特徴とする請求項21に記載の方法。
【請求項1】
両方向ルーティング用に構成されたノードのリングのフェデレーションインフラストラクチャ内で、フェデレーションインフラストラクチャ内で維持される複製セット内でデータアクセストランザクションを実行する方法であって、
プライマリノードがノードの複製セット内の複数のノードの中から選ばれたことを判定する行為であって、前記プライマリノードは、クライアントデータアクセス要求を受け入れ、処理するように構成され、前記複製セットは、前記プライマリノードおよび1つまたは複数のセカンダリノードを含む、行為と、
前記プライマリノードが、1つまたは複数のクライアントデータアクセス要求を受信する行為であって、各データアクセス要求は、前記複製セット内で少なくとも前記プライマリノード上でアクセスされるデータの少なくとも一部を示す、行為と、
前記プライマリノードが、前記クライアントデータアクセス要求が受信される順序で状態を変化させる前記クライアントデータアクセス要求のそれぞれにデータシーケンス番号を割り当てる行為であって、前記データシーケンス番号は、前記複製セット内の前記ノードのそれぞれによって従われる線形化された処理順序を含む、行為と、
前記プライマリノードが、任意の対応するデータシーケンス番号を含む前記クライアントデータアクセス要求のうちの少なくとも1つを前記セカンダリノードのうちの少なくとも1つに送信する行為と、
前記プライマリノードが、少なくとも閾値個数のセカンダリノードから、前記クライアントデータアクセス要求の受信を示す肯定応答を受信する行為と、
前記プライマリノードが、前記データアクセス要求をコミットする行為であって、前記コミットは、前記クライアントデータアクセス要求に従ってデータにアクセスすることを含む、行為と
を含むことを特徴とする方法。
【請求項2】
前記プライマリノードは、前記データアクセス要求を単一フェーズでコミットすることを特徴とする請求項1に記載の方法。
【請求項3】
ノードの前記複製セット内の複数のノードの間からプライマリノードを選ぶ行為をさらに含むことを特徴とする請求項1に記載の方法。
【請求項4】
許容可能な同時障害の最大個数に基づいて、前記複製セットのメンバになるセカンダリノードの個数を判定する行為をさらに含むことを特徴とする請求項1に記載の方法。
【請求項5】
前記肯定応答は、前記クライアントデータアクセス要求の受入または拒否のうちの少なくとも1つを示すことを特徴とする請求項1に記載の方法。
【請求項6】
前記閾値個数のセカンダリノードは、クォーラムを表すことを特徴とする請求項1に記載の方法。
【請求項7】
プライマリになるはずのノードが、前記プライマリになるはずのノードが知らないすべてのトランザクションを判定するために前記クォーラムのセカンダリノードに要求を送信する行為をさらに含むことを特徴とする請求項6に記載の方法。
【請求項8】
前記クォーラムの各メンバが、少なくとも、LSNによって順序付けられる各メンバのデータアクセスキューに前記クライアントデータアクセス要求を挿入したことの表示を前記クォーラムの各メンバから受信することをさらに含むことを特徴とする請求項6に記載の方法。
【請求項9】
データの一部は、LSN、CSN、DSN、プライマリノードアイデンティティ、およびセカンダリノードアイデンティティのうちの少なくとも1つを含む、前記複製セット自体に関する制御情報のセットを含むことを特徴とする請求項1に記載の方法。
【請求項10】
前記データアクセス要求を単一フェーズでコミットすることは、前記セカンダリノードのいずれかに関してコミットクエリを送信することおよび受信することを伴わずに前記データにアクセスすることを含むことを特徴とする請求項1に記載の方法。
【請求項11】
前記クライアントデータアクセス要求を第2複製セットに送信する行為をさらに含み、前記第2複製セットは、前記プライマリノードの近傍とは異なる近傍内にあることを特徴とする請求項1に記載の方法。
【請求項12】
前記複製セットは、前記クライアントデータアクセス要求の第1部分を処理することを要求され、前記第2複製セットは、前記データアクセス要求の第2の異なる部分を処理することを要求されることを特徴とする請求項11に記載の方法。
【請求項13】
前記クライアントデータアクセス要求の前記第1部分に対応する前記複製セットからの応答を受信する行為と、
前記データアクセス要求の前記第2の異なる部分に対応する前記第2複製セットからの応答を受信する行為と、
前記応答を組み合わせる行為と、
前記組み合わされた応答に基づいて、最新のデータアクセス応答を生成する行為と
をさらに含むことを特徴とする請求項12に記載の方法。
【請求項14】
両方向ルーティング用に構成されたノードのリングのフェデレーションインフラストラクチャ内で、フェデレーションインフラストラクチャ内の複製セットからデータにアクセスするシステムであって、
前記リング上の複数のノードの近傍を確立するように構成された近傍確立モジュールであって、前記近傍は、少なくとも直接に隣接する先行ノードおよび直接に隣接する後続ノードを含む、近傍確立モジュールと、
前記確立された近傍の外の参加するノードが、ノードの前記リング内の前記確立された近傍に参加する意図を示したことを判定するように構成された意図判定モジュールと、
前記複数のノード内の各ノードが前記近傍内のid空間の一部のid空間オーナーシップをとるように、前記確立された近傍内の一貫性を維持するように構成された一貫性維持モジュールと、
前記複数のノード内の前記ノードの1つが、プライマリノードによって向けられるクライアントデータアクセス要求に応答するように構成されたノードの複製セットにまたがる責任を有する前記プライマリノードになるために選ばれたことを判定するように構成された選出判定モジュールと、
1つまたは複数のクライアントデータアクセス要求を受信するように構成された要求受信モジュールであって、各データアクセス要求は、前記複製セット内の前記ノードのうちの少なくとも1つでアクセスされるデータの少なくとも一部を示す、要求受信モジュールと、
前記クライアントデータアクセス要求内で示されるデータにアクセスするように構成されたデータアクセスモジュールと
を含むことを特徴とするシステム。
【請求項15】
前記データアクセスモジュールは、クライアントデータ書き込み要求に従ってデータを書き込むように構成されることを特徴とする請求項14に記載のシステム。
【請求項16】
前記プライマリノードは、セカンダリノードに、前記クライアントデータ書き込み要求内で示される前記データを前記セカンダリノードによって管理されるデータストアに書き込むように指示することを特徴とする請求項15に記載のシステム。
【請求項17】
前記プライマリノードは、前記書き込み要求を1つまたは複数のセカンダリノードに2フェーズで複製することを特徴とする請求項15に記載のシステム。
【請求項18】
前記データアクセスモジュールは、クライアントデータ読み取り要求に従ってデータを読み取るように構成されることを特徴とする請求項14に記載のシステム。
【請求項19】
前記クライアントデータ読み取り要求は、セカンダリノードによって直接に処理されることを特徴とする請求項18に記載のシステム。
【請求項20】
プライマリの前記確立された近傍は、そのプライマリの複製セットのセカンダリノードのセットであることを特徴とする請求項14に記載のシステム。
【請求項21】
両方向ルーティング用に構成されたノードのリングのフェデレーションインフラストラクチャ内で、フェデレーションインフラストラクチャ内の一貫した複製セットを確立し、維持する方法であって、
ノードのリング内の複数のノードの中から複製セットを確立する行為であって、前記複製セットは、メンバとしてプライマリノードおよび1つまたは複数のセカンダリノードを含む、行為と、
前記複製セットメンバのうちの少なくとも1つに影響する複製セット構成イベントオカレンスを示す表示を受信する行為と、
前記受信された表示に基づいて、前記複製セットが再構成されなければならないことを判定する行為であって、前記再構成は、前記複製セット構成イベントオカレンスに基づいて、前記複製セットからの既存セカンダリノードの除去、前記複製セットへの新しいセカンダリノードの追加、新しいプライマリへの突然の推移、および新しいプライマリへの滑らかな推移のうちの少なくとも1つを含む、行為と、
前記複製セット構成イベントに対応する前記再構成に従って前記複製セットを再構成する行為と
を含むことを特徴とする方法。
【請求項22】
前記複製セット構成イベントは、前記複製セット内のノード障害、前記複製セットからのノード離脱、およびノードが前記複製セットに参加することのうちの少なくとも1つを含むことを特徴とする請求項21に記載の方法。
【請求項23】
前記複製セットノードのうちの1つまたは複数によって制御されるデータストレージの一部を維持する行為をさらに含むことを特徴とする請求項21に記載の方法。
【請求項24】
前記プライマリノードがクライアントデータアクセス要求を受信する行為であって、前記クライアントデータアクセス要求は、ノードの複製セット内の少なくとも1つのノードでアクセスされる情報の表示を含む、行為と、
前記プライマリノードが前記受信されたクライアントデータアクセス要求内で示される情報の少なくとも一部にアクセスするのに失敗したことを検出する行為と、
前記プライマリノードに格納された情報が前記クライアントデータアクセス要求に応答してアクセスされるのを防ぐように、前記プライマリノードが前記複製セットからそれ自体を除去する行為と
をさらに含むことを特徴とする請求項23に記載の方法。
【請求項25】
構成状態情報に基づいて、進行中の1つまたは複数の複製セット再構成を検出する行為をさらに含むことを特徴とする請求項21に記載の方法。
【請求項26】
前記複製セットの新しいプライマリノードを選ぶ行為をさらに含むことを特徴とする請求項21に記載の方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12A】
【図12B】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19A】
【図19B】
【図19C】
【図20】
【図21】
【図22A】
【図22B】
【図23A】
【図23B】
【図23C】
【図23D】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29】
【図30】
【図31】
【図32】
【図33】
【図34】
【図35】
【図36】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12A】
【図12B】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19A】
【図19B】
【図19C】
【図20】
【図21】
【図22A】
【図22B】
【図23A】
【図23B】
【図23C】
【図23D】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29】
【図30】
【図31】
【図32】
【図33】
【図34】
【図35】
【図36】
【公開番号】特開2013−102527(P2013−102527A)
【公開日】平成25年5月23日(2013.5.23)
【国際特許分類】
【出願番号】特願2013−13645(P2013−13645)
【出願日】平成25年1月28日(2013.1.28)
【分割の表示】特願2009−536478(P2009−536478)の分割
【原出願日】平成19年11月8日(2007.11.8)
【出願人】(500046438)マイクロソフト コーポレーション (3,165)
【Fターム(参考)】
【公開日】平成25年5月23日(2013.5.23)
【国際特許分類】
【出願日】平成25年1月28日(2013.1.28)
【分割の表示】特願2009−536478(P2009−536478)の分割
【原出願日】平成19年11月8日(2007.11.8)
【出願人】(500046438)マイクロソフト コーポレーション (3,165)
【Fターム(参考)】
[ Back to top ]