Paxos の実装に関する質問

https://stackoverflow.com/questions/5850487

27-10-2019
|

質問

で入手可能なドキュメントを使用して、クラスターシミュレーターアプリケーションに Paxos を実装しています。ウィキペディア. 。残念ながら、解釈の余地がいくつか残されており、主要な実装上の問題については多くの情報が提供されていません。それは不明確で不完全です。

クラスターが 3 つのリージョンに分割され、それぞれに 3 つのノードが含まれていると仮定します (合計 = 9 ノード)。リージョン間の通信が切断された場合はどうなりますか?どのリーダーも定足数（5）に達することはできません。

Paxosは無限ループに陥るのではないか？少なくとも定足数のノードと通信できない場合は、Paxos を開始すべきではないと思います。

フェーズ 1b では:'プロポーザル番号 N が以前のどのプロポーザルよりも大きい場合、各アクセプタは N 未満のプロポーザルを受け入れないことを約束し、 最後に受け入れられた値 のために このインスタンス 提案者へ'.

「最後に受け入れられた値」とは何ですか?提案者からの以前の提案番号ですか?この場合の「インスタンス」とは正確には何を指すのでしょうか?

フェーズ 1a では:Prepare メッセージに同意するための値が含まれていますか、それとも Accept! メッセージに延期されますか?メッセージ？それともそれは重要ですか？
フェーズ 2a:'アクセプタのいずれかがすでに値を受け入れている場合、リーダーは次のことを行う必要があります。 値を選択してください 最大提案数 N'.

ここでの価値とは何でしょうか？提案番号ですか？私はそうではないと思いますが、この表現は不明瞭です。

フェーズ 2a:「それ以外の場合、提案者は任意の値を自由に選択できます。」これはどういう意味ですか？何のための価値なのでしょうか？提案番号については?
Paxos は、N (提案番号) の値の増加に依存して機能しているようですか?これは正しいです？
ウィキペディアのエントリでは、Paxos への参加を開始する前にノードが設定する必要がある初期値については説明されていません。これらは何ですか？

追記：「Paxos」タグを作成するのに十分な評判がありません (ボランティアはいますか?)

解決

インスタンスとは何ですか?

Paxos の命名法は少し直感的ではありません。

アン実例を選択するためのアルゴリズムです 1つ価値。
あ ラウンド 提案者によるフェーズ 1 + フェーズ 2 の 1 回の試行を指します。ノードには複数のノードを含めることができます ラウンド で実例パクソスの。ラウンド ID は、すべてのノードにわたってインスタンスごとにグローバルに一意です。これは時々呼ばれます 提案番号.
ノードはいくつかの役割を担う場合があります。最も注目すべきは提案者と受諾者です。私の回答では、各ノードが両方の役割を担うと仮定します。
フェーズ 1 は準備フェーズとも呼ばれます。
- フェーズ 1a では、プロポーザーが Prepare!(roundId) メッセージをアクセプターに送信します。
- フェーズ 1b では、アクセプタは Promise!(roundId, value) または PrepareNack!() で応答します。
フェーズ 2 は受け入れフェーズとも呼ばれます。
- フェーズ 2a では、プロポーザーが Accept!(roundId, value) メッセージをアクセプターに送信します。
- フェーズ 2b では、アクセプターは Accepted!(...) または AcceptNack!() で応答します。

クラスターが 3 つのリージョンに分割され、それぞれに 3 つのノードが含まれていると仮定します (合計 = 9 ノード)。リージョン間の通信が切断された場合はどうなりますか?どのリーダーも定足数（5）に達することはできません。

Paxos では、少なくともクォーラム (この場合は 5 ノード) を取得できる必要があります。3 つのリージョンのソリューションを使用してください。3 つのリージョン間に 2 つのネットワークパーティションがあることは、非常に悪いニュースです。また、ノードのメンバーシップをあるインスタンスから次のインスタンスに変更できるバージョンの Paxos も使用しています。これは、パーティションやノードの障害に役立ちます。

Paxosは無限ループに陥るのではないか？

Paxos の単純な実装は、複数のノードが準備フェーズを飛び越える可能性があるため、終了することが保証されません。これを回避するには 2 つの方法があります。1 つは、新しい準備フェーズを開始する前にランダムなバックオフを行うことです。2 つ目は、すべてのリクエストを、提案者として機能する指定されたリーダーにルーティングすることです (リーダーは Paxos インスタンスによって選択されます)。マルチパクソも参照)

フェーズ 1b では:「プロポーザル番号 N が以前のどのプロポーザルよりも大きい場合、各 >>Acceptor は N 未満のプロポーザルを受け入れないことを約束し、>>このインスタンスに対して最後に受け入れた値を Proposer に送信します。」

「最後に受け入れられた値」とは何ですか?提案者からの以前の提案番号ですか?

ノードがプロポーザーから Accept!(roundId, value) メッセージを受信したとき そして (Prepare!(higherRoundId) メッセージのため) 値を受け入れないことは約束されておらず、値とroundId (私はこれらをroundIdと呼びます) を保存します。 acceptedValue そして acceptedRoundId）。後続の Accept!(...) メッセージにより、これらが上書きされる可能性があります。

ノードがプロポーザーから Prepare!(roundId) メッセージを受信すると、roundId を次のように格納します。 promiseRoundId = max(roundId, promiseRoundId). 。次に、 Promise!(acceptedRoundId, acceptedValue) 提案者に戻ります。注意:ノードが Accept!(...) メッセージを受信していない場合は、次のように応答します。 Promise!(null, null).

フェーズ 1a では:Prepare メッセージに同意するための値が含まれていますか、それとも Accept! メッセージに延期されますか?メッセージ？それともそれは重要ですか？

送信する必要はありません。私はしません。

フェーズ 2a:「アクセプタのいずれかがすでに値を受け入れている場合、リーダーは最大提案番号 N の値を選択する必要があります。」

ここでの価値とは何でしょうか？提案番号ですか？私はそうではないと思いますが、この表現は不明瞭です。

値は、アルゴリズムが合意に達している実際のデータです。これをこう言い換えます

承認フェーズを開始するには、提案者は準備フェーズの結果に応じて承認される値を選択する必要があります。いずれかのアクセプタが Promise(roundId, value) で応答した場合、プロポーザは最も高いroundIdに関連付けられた値を使用する必要があります。それ以外の場合、プロポーザーは Promise(null, null) のみを受け取り、アクセプターに送信する任意の値を選択できます。

注意:ここでのプロポーザル番号はroundIdと同じものです。

フェーズ 2a:「それ以外の場合、提案者は任意の値を自由に選択できます。」これはどういう意味ですか？何のための価値なのでしょうか？提案番号については?

これは、合意を得たい値です。これは通常、分散システム全体の状態変化であり、おそらくクライアント要求によってトリガーされます。

Paxos は、N (提案番号) の値の増加に依存して機能しているようですか?これは正しいです？

ウィキペディアのエントリでは、Paxos への参加を開始する前にノードが設定する必要がある初期値については説明されていません。これらは何ですか？

ラウンド ID (別名プロポーザル番号) すべき 増えていて、 しなければならない すべてのノードにわたってインスタンスごとに一意である必要があります。Paxos の論文では、これを達成するのは簡単であるため、これが可能であると仮定しています。すべてのノードで同じ結果を生成するスキームの 1 つを次に示します。

Paxos のインスタンスに M 個のノードが参加しているとします。
すべてのノードを辞書順に並べ替えます。Index[node] は、このソートされたリスト内のノードのインデックスです。
roundId = i*M + index[node] ここで、 i はこのノードが開始する i 番目のラウンドです (つまり、 i は paxos インスタンスごとにノードごとに一意であり、単調増加します)。

または、疑似コード (明らかにいくつかの主要な最適化が欠けています) では次のようになります。

define runPaxos( allNodesThisPaxosInstance, myValue ) {
    allNodesThisPaxosInstance.sort()
    offset = allNodesThisPaxosInstance.indexOf( thisNode )
    for (i = 0; true; i++) {
        roundId = offset + i * allNodesThisPaxosInstance.size()
        prepareResult = doPreparePhase( roundId )

        if (!prepareResult.shouldContinue?)
            return

        if (prepareResult.hasAnyValue?)
           chosenValue = prepareResult.valueWithHighestRoundId
        else
            chosenValue = myValue

        acceptResult = doAcceptPhase( roundId, chosenValue )

        if (!acceptResult.shouldContinue?)
            return
    }
}

他のヒント

私は次のことを見つけました資料詳細については、Paxosを説明します。それに応じてウィキペディアのエントリを更新しました。

私が見つけることができる私の質問への答えは次のとおりです。

Paxosは無限のループを入力するつもりはありませんか？

Paxosは、少なくとも一定のノードが互いに通信できる場合にのみ機能します（この場合5）。したがって、ノードが少なくともクォーラムのノードと通信できない場合、Paxosを試してはいけません。

「それが受け入れた最後の価値」とは何ですか？

これは、最後に受け入れられた提案番号と対応する値です。

この場合、「インスタンス」は正確に何を参照していますか？

アクセプターを指します。

準備メッセージに同意する価値が含まれていますか、それとも受け入れに延期されていますか？メッセージ？またはそれは重要ですか？

値は準備メッセージに含まれておらず、承認要求メッセージに任されています。

ここでの価値は何ですか？それは提案番号ですか？私は信じていませんが、このフレーズは不明です。

それ以外の場合、提案者は自由に価値を選択できます」。これは何を意味するのでしょうか？何の価値？提案番号は？

アクセプターが提案者からの提案をすでに受け入れている場合、対応する提案数と価値を返すことができます。

ウィキペディアのエントリは誤解を招くため、2番目の質問はありません。特定の提案の任意の値を選択したり、前に受け入れられた提案に対応する値から導き出すことができます。

Paxosは、動作するn（提案番号）の値の増加に依存しているようですか？これは正しいです？

はい。提案者Pは、その提案をますます番号にする必要があります。

Wikipediaのエントリでは、Paxosに参加する前にノードが設定する初期値については説明していません。これは何？

ノードは、最後に受け入れられた提案番号を維持する必要があります。最終的には、対応する値も保持する必要があります。彼らはそれを持つべきです。初めて接続する場合、特定の提案者の最初の提案番号はnull（または同等）でなければなりません。

Paxos seems to rely on an increasing value of N (proposal number) to work? Is this correct?

各提案者には安定したストレージがあります。各提案者は（安定したストレージで）発行しようとした最高の提案を覚えており、すでに使用しているよりも高い提案数でフェーズ1を開始します。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow