フェーズ 1a で、プロポーザーはアクセプターへのプロポーザルに選択しようとしている値を含めますか?
プロポーザーは、フェーズ 2a まで、選択しようとしている値を送信する必要はありません。以前の質問に対する私の回答も参照してください。
フェーズ 1b では、アクセプターは以前に受け入れた値があればそれを返すことになっています。値の寿命は？IOW、いつ承認されたと見なされ、いつ上書き/削除されますか?
別の別の質問に対する私の答えから、 「受け入れないことを約束していない限り、受け入れ者はすべての値を受け入れる必要があります。」つまり、最後に送信した応答の round-id 以上の round-id を持つ任意の値を受け入れる必要があります。
他の値を受け入れなければならない理由は、提案者が (フェーズ 1 の結果として)別の値を選択する必要があること、または既に選択されていることを発見する可能性があるためです。次に、この値をすべてのアクセプターにブロードキャストします。この不一致は、複数の提案者がいる場合、および/またはネットワークの分割中に発生する可能性があります。
コメントに答えるために更新します。
アクセプターが値を受け入れると、別の値を受け入れるまでその値を保持します。（これに加えて、値の丸めを保存します）。
フェーズ 1b では、Acceptorは常にその値を送信し、Proposer が実際に選択された値を分類できるようにします。現在の値を決して忘れません。これまで。
アクセプターから約束を受け取った後、提案者はシステムの素晴らしいビューを持っています。(注: 必ずしも完全または最新のビューではありません。)
異なる提案者との何らかの競合のために、異なるアクセプターが異なる値を受け入れた可能性があります。そのため、プロポーザーはラウンド ID が最も高い値を選択し、その値をすべてのアクセプターに送信します。これが、アクセプターの値を変更できる理由です。
コメントの懸念は、これが Paxos を壊すことです。そうではありません。
しかし、例に入る前に、1a、1b、2a、2b ではなく名前付きのフェーズとメッセージを使用して Paxos について考える方がはるかに簡単であることを強調しておきます。私は通常、これらのフェーズを準備フェーズと受け入れフェーズと呼んでいます。メッセージ 1a は Prepare、1b は Promise、2a は Accept、2b は Accepted です。
さて、人々がよく与える、そして彼らが Paxos を壊すと考える仮説的な例を取り上げましょう。3 つのアクセプター A1、A2、および A3 があるとします。A1 と A2 はどちらもラウンド 1 で値 ABC を受け入れ、A3 はラウンド 2 で XYZ を選択しました (つまり、別の提案者から)。A1 と A2 が過半数を占めており、ABC が「選択」されていることがわかります。
この架空の例を続けると、提案者は Prepare(3) を送信し、A2 と A3 から応答を受け取ります。つまり、Promise(ABC @ 1) と Promise(XYZ @ 2) です。Proposer は、XYZ が最高のラウンドを持っていることを認識し、それを Accept フェーズで送信して、他のホストの ABC を上書きします。そしてヴィオラ、パクソスは壊れてるよね？
いいえ。問題は開始状態にあり、これは不可能です。その理由をお見せしましょう。
まず、Paxos が正しく動作するための鍵となるいくつかの命題:
命題 A : A1 と A2 の値が ABC @ 1 になるには、提案者は Accept(ABC @ 1) を送信している必要があります。
命題 B : A3 が XYZ @ 2 という値を持つためには、提案者は Accept(XYZ @ 2) を送信している必要があります。
そして今、証拠：
ケース 1 : A1 と A2 は既に値 ABC @ 1 を持っています。命題 B により、A3 が値 XYZ @ 2 を持つためには、アクセプターからPromise の過半数を受け取っている必要があります。値 ABC は多数のアクセプターにあるため、そのうちの少なくとも 1 つが Promise(ABC @ 1) を送信している必要があります。1 が最高のラウンド ID であるため、提案者は値 ABC を選択し、Accept(ABC @ 2) を送信する必要があります。しかし、そうではなく、Accept(XYZ @ 2) を送信しました。矛盾。
ケース 2 : A3 はすでに XYZ @ 2 の値を持っています。プロポーザーは、アクセプターからプロミスの過半数を受け取っている必要があります。同様に、命題 B によって、A3 もそれを持つためには、約束の過半数を受け取っていなければなりません。つまり、セット {A1, A2} には、Promised を 2 回行った少なくとも 1 つのアクセプターが存在する必要があります。
ケース 2a : アクセプタは最初に Promise(1) を送信し、次に Promise(2) を送信しました。次に、Accept(ABC @ 1) というメッセージを受信したとき、2 より前の値は受け入れないと約束しているので、拒否したに違いありません。しかし、ABC @ 1 という値を持っているため、拒否しませんでした。
ケース 2b : アクセプターが最初に Promise(2) を送信しました。その後、Prepare(1) というメッセージを受信したとき、より高いラウンドを約束していたので、それを拒否したに違いありません。しかし、命題 A によって Promise(1) を送信したため、明らかにそうではありませんでした。矛盾。
わお！
これがお役に立てば幸いです。
更新 2 : これは Paxos の疑似 Python 実装です。
from itertools import count
from concurrent import futures
class Acceptor():
def __init__(self):
self.acceptedValue = None
self.acceptedRound = None
self.promisedRound = None
def onPrepare(self, message):
if self.promisedRound > message.round:
send(message.source, new Nack())
self.promisedRound = message.round
response = new Promise(round=self.acceptedRound, value=self.acceptedValue)
send(message.source, response)
def onAccept(self, message):
if self.promisedRound > message.round:
send(message.source, new Nack())
self.acceptedValue = message.value
self.acceptedRound = message.round
send(message.source, new Accepted())
class Proposer():
def __init__(self, selfId, quorum):
self.quorum = quorum
self.id = selfId
# get a unique starting round,
# assumes acceptors and proposers are on same hosts
self.initialRound = sorted(quorum).index(selfId)
def propose(self, value):
"Propose a value to be chosen; returns actual value chosen"
# round is always unique to a proposer
# count(start, step) returns an infinite sequence
for round in count(self.initialRound, len(self.quorum))
promises = self.prepare(round)
if not promises: continue
# interpret the prepare phase results, may be None
selectedValue = max(promises, key=lambda p: p.round or -1)
accepted = self.accept(round, selectedValue or value)
if accepted: return value
def prepare(self, round):
"Drive the Prepare phase. returns the promises from the acceptors or None"
message = new Prepare(round, source=self.id)
responses = []
for acceptor in self.quorum:
responses.append(send(acceptor, message)))
# wait for the results
promises = []
for response in futures.as_completed(responses):
if response.exception(): continue # message died
message = response.result()
if not isinstance(message, Promise):
# A nack message; abort the round. We may have got a majority,
# but this speeds up the case when we didn't.
return None
promises.append(message)
if (len(promises) > len(self.quorum) / 2:
return promises
# No majority of responses
return None
def accept(self, round, value):
"Drive the Accept phase. returns True iff the value was accepted"
message = new Accept(round, value)
responses = []
for acceptor in self.quorum:
responses.append(send(acceptor, message)
# wait for the results
accepts = 0
for response in futures.as_completed(responses):
if response.exception(): continue # message died
message = response.result()
if not isinstance(message, Accepted):
# A nack message; abort the round. We may have got a majority,
# but this speeds up the case when we didn't.
return False
accepts = accepts + 1
if accepts > len(self.quorum) / 2:
return True
# No majority of responses
return False
更新 3コメントからさらに質問に答える。
…前回のラウンドで送信されたプロポーザーと同じ値の場合、プロポーザーにそれを無視してもらいます (そうしないと、デッド ループになってしまいますよね?)
(値を「無視する」ということは、ループを早期に終了することを意味すると想定しています。)
まず、プロポーザーがアクセプターの過半数から値が選択されたという確認を受け取ると、ループが終了することに注意してください。そのため、プロポーザーが後続の準備フェーズを実行していることに気付いた場合、別のプロポーザーと競合しているか、何らかのネットワーク パーティションが発生していることを確認できます。次に、 1 つのアクセプターしか値を受け入れていない場合でも、準備フェーズが値を返すことに注意してください(値が過半数によって受け入れられていない可能性があることを意味します)。
準備フェーズの結果が値になり、それが前のラウンドで見たのと同じ値である場合、いくつかの理由から受け入れフェーズを続行する必要があります。
- 提案者がループを早期に終了した場合、他の提案者が失敗した可能性があります。これにより、値が選択されない場合があります。
- ループを早期に終了した場合、他の提案者が同じアルゴリズムに従ってループを終了したことは合理的です。この場合も、値が選択されない可能性があります。
- 値が実際に選択された場合、すべてのノードが値を受け取っていないか (ネットワーク パーティションが原因)、または別の値を持っている可能性があります (他の提案者との戦いが原因です)。したがって、耐久性のために値をノードにプッシュすることをお勧めします。
一方、Paxos は、2 つ以上の提案者の間で競合が発生し、運が悪いと、無限ループに陥る可能性があります。(これはあらゆるコンセンサス アルゴリズムに当てはまり、コンセンサス アルゴリズムが実際に発見される前に、Liskov らによって証明されました。) したがって、理論は述べていますが、実際のシステムでは回避するのは簡単です。次の各ラウンドで、ランダムな量の一時停止を行います。他の提案者にレースに勝つチャンスを与える時間。確かに、無限ループが発生する可能性はまだありますが、宇宙の存続期間中に発生する可能性はほとんどありません。
引数をサポートするための参照はありますか?
私は主に私自身の学習と経験から話します。私は、Paxos を中心に構築されたシステムを開発および保守するチームに所属しています。私はまた、このテーマについて広範な研究を行ってきました。
このテーマに関するいくつかの優れた論文を次に示します。
更新 4質問の更新に回答します。
通常、paxos ワークフローでは、アクセプターは常に以前に受け入れられた値を手元に持っている必要があります。また、準備リクエストに応答すると、promise レスポンスで値が返されます。また、提案者は、値が前回のラウンドで提案された値と同じかどうかを確認する必要があります。そうでない場合、プロポーザーは、アクセプターによって返された値を使用して受け入れ要求を送信します。
さて、ここまで。しかし、提案者はラウンド間で状態を保持する必要はありません。その理由はすぐにわかります。
[同じ値] である場合、提案者は、現在のラウンドで送信することを意図した値で Accept 要求を送信します。
アクセプターから何らかの値が返された場合、ラウンド ID が最大のものをAccept フェーズで使用する必要があります。アクセプターから値が返されない場合は、任意の値を使用できます。私の論理では、これがクライアントがプロポーザーに渡した値になることを示唆しています。
これをPaxos Made Simple (pg 6)と比較してください。
...ここで、v は応答の中で最も番号の大きい提案の値、または応答が提案を報告しなかった場合は任意の値です。
(論文間で用語を切り替えるのはちょっと難しいです。ここでランポートは番号付き提案という用語を使用し、他の場所ではラウンド IDという用語を使用します。まったく同じものがあります。)
プロポーザーが準備フェーズを実行し、アクセプター間でこの状態を確認するとします。
A1 A2 A3
promise: 3 ? 4
value@round: x@3 ? y@4
実際の状態はどこですか
A1 A2 A3
promise: 3 4 4
value@round: x@3 y@4 y@4
ここで、前のラウンドを値 y で実行したとします。この時点で任意の値を選択できる場合は、次の状態を強制できます。
A1 A2 A3
value@round: z@5 z@5 z@5
これは、選択された値を上書きし、コンセンサスの一貫性プロパティに違反します (つまり、多くても 1 つの値を選択できます。 )。
この種の動作が必要な場合は、コンセンサス プロトコルをそのまま使用することはできません。ABDやその他のラウンドベースの registerなどのプロトコルを使用できます。または、Paxosはステート マシンで遷移を選択するものと考えることができます。つまり、変数を変更するたびに、新しい Paxos アルゴリズムを実行して遷移を選択します。これが私のシステムが行うことです (そして、最も実用的な Paxos システムと言えます)。
ABD およびラウンドベースのレジスタは Paxos と同様に動作しますが、上記の一貫性プロパティを保証する必要がないため (一度選択すると常に選択される)、少し単純です。しかし、Paxos ベースのステート マシンでは、変数に対する CAS 操作が可能です。