0

提案者が選択した値に混乱しています。例を使って説明します。提案者がファイルをロックしたい場合、l1 が processor_number であり、v1 が「ファイルをロックする」の値であり、受け入れ者がそれを受け入れることを送信します。提案者がファイルのロックを解除したいので、v2 が「ファイルのロックを解除する」という値であることを送信します (l2 > l1)。その後、アクセプターは最後の値を返し、提案者はそれを選択して再度送信します。

この例では、v2 が失われていますか? または、この例の実際のプロセスは何ですか? また、これらは 2 ラウンドですか、それとも 1 ラウンドですか? ラウンドにどう対処する？

4

2 に答える 2

1

Paxos はアトミック レジスタではありません。値が Paxos によって選択されると、変更できません。

まず、ロックが有限状態マシンであることに注意してください。

          on_lock
       .-----------.
       |           |
+------+---+    +--v-----+
| UNLOCKED |    | LOCKED |<--- start
+------^---+    +--+-----+
       |           |
       `-----------'
         on_unlock

Paxos は一連の遷移を決定するために使用できます。ただし、新しい遷移はそれぞれ、新しい Paxos インスタンスで決定する必要があります。

StackOverflow に関するその他の paxos に関する質問をいくつか見てみることをお勧めします。

于 2013-03-08T22:25:03.933 に答える
0

複数の値がいつ利用できるかを理解し、値を選択した結果を確認するために、Paox を使用して実行できるロック プロトコルを記述する必要があります。

ロックは、 の形式でロック トークン値を保持するセルですL={T,P}。ここPで、 はロックを保持しているプロセス、Tはプロセスがロックを取得した時刻です。クライアントが送信するロックを取得するには、現在のロック トークンであると考えられるV={Lc,Ln}場所と、設定したい新しいロック トークンを送信します。ロックを解除するために特別なトークンを送信できます。メッセージが現在のトークンと一致する正しいことを示していない場合、新しいトークンは設定されません。このコンペア アンド スワップ (CAS) により、遅延ロック解除メッセージが誤って適用されるのを防ぎます。また、クライアントがロックを盗むことができる場合にロックをタイムアウトするように機能します。2 つのプロセスが 2 つの競合メッセージを送信し、LcLn={T',P'}NilLc{L1,L2}{L1,L3}成功できるのは1つだけです。プロセスは、ロック値である戻り値を検査することにより、操作が成功したかどうかを学習しますL。{Nil,Nil}プロセスは、開いているロックのロックを解除する「何もしない」CAS を送信することにより、ロック値を照会できます。ただし、ロックが閉じている場合は、誰がロックを所有しているかを返します。

書き込みはリーダーを通過する必要があります。ノードがリーダーではないことを認識している場合、クライアントをリーダーにリダイレクトする必要があります。ノードが誰がリーダーかわからない場合、エラーをスローし、クライアントは別のノードをランダムに選択する必要があります。ノードがリーダーであると判断した場合、ノードの大部分が新しい値を受け入れたことが確実な場合にのみ、クライアントに応答できます。これは、Paxos が過半数によって受け入れられた値がクラスターによって永続化されていることを保証するためです。ノードがリードしていた場合、受諾の過半数が聞こえず、クライアントに応答できません。他のノードから分離されている可能性があります。他のノードには、新しく選出されたリーダーがいる場合があります。これは以下にも当てはまります{Nil,Nil}クライアントに現在のロック値を伝えるために、リーダーがまだリーダーであることを確認するために過半数の受け入れを必要とするクエリ。最終的に、ノードは、新しいリーダーが存在するかどうかを確認する必要があります。そうでない場合、過半数に受け入れられた値を取得しようとしてタイムアウトになります。次に、クライアントを新しいリーダーにリダイレクトするか、クライアントにエラーを返す必要があります。

これで、リーダーのフェイルオーバー中に複数の値を考慮することができます。クライアント Aは、3 ノード クラスタV1のリーダー ノードに成功するはずの有効な CAS 更新を送信します。Xノードはそれ自体とノードおよびノー​​ドにX送信します。は独自の値を受け入れ、 からも受け入れられますが、ネットワークはメッセージを にドロップします。その後、ノードは暗くなり、しばらくメッセージの発行を停止します。死んでいるか失速している可能性がありますが、まだわかりません。それは大部分を見ていましたが、その運命を知るために別のメッセージを見るまで、今では謎のシュレディンガーの猫が死んでいるか生きているかのどちらかです. これは、Paxos がコラボレーションを使用して、次に何が起こっても一貫した正しい結果を得ることを選択した場所です。accept(N1,V1)YZYZXX,Y

リーダーからの応答が長すぎるため、しばらくするとノードZがタイムアウトします。propose(N2)自分自身と他のノードに発行し​​ます。promise(N2,V1)ノードYとそれ自体から戻りpromise(N2,empty)ます。それは過半数Y,Zを占めており、リードすることができます。ノードのみXが、値V1が過半数に受け入れられたこと、およびクライアントが CAS が成功したと通知されたかどうかを認識します。しかし、それは沈黙しています。ノードZは保守的な選択をしなければなりません。ノードが死んでいると仮定すると、Xそれは間違っている可能性があります。ノードXは生きていて、操作が成功したことをクライアントに伝えている可能性があります。ノードは、最初の値としてZリードすることにより、最後のリーダーの部分的な作業を協力して完了する必要があります。V1したがって、accept(N2,V1)3 つのノードすべてに送信されます。現在、ノードかどうかは問題ではありませんX死んでいるか生きているか、クライアントに操作が成功したかどうかを伝えていました。すべての場合において、ロック プロトコルに違反することはなく、クライアントは、エラー時に再試行すると、最終的にロックされていることがわかります。それは、どの提案やどのノードが作業をコミットしたかを見たり気にしたりしません。

于 2014-10-25T22:01:33.997 に答える