4

特にデータベーストランザクションのコンテキストで、paxos についていくつかの混乱がありました。

「paxos made simple」という論文では、第 2 段階で、提案者は、アクセプターの 1 つが以前に受け入れた最大のシーケンス番号を持つ値の 1 つを選択する必要があると述べています (そのような値が存在しない場合、提案者は自由に選択できます)。提案された元の値を選択します)。

質問:

  1. 一方では、コンセンサスを維持するためにそうしていることを理解しています。しかしその一方で、値が実際に何であるかについて混乱がありました。「以前に受け入れられた値をアクセプターに送信する必要がある」という点は何ですか?

  2. データベース トランザクションのコンテキストで、新しい値をコミットする必要がある場合はどうなるでしょうか? Paxos の新しいインスタンスを開始する必要がありますか?

  3. 上記の質問に対する答えが「はい」の場合、アクセプターはどのように状態をリセットしますか? (私の理解では、状態がリセットされない場合、提案者は、新しい値が何であれ自由にコミットするのではなく、以前に受け入れられた古い値のいずれかを送信することを余儀なくされます。)

4

4 に答える 4

2

「Paxos made simple」という論文には、さまざまな種類の paxos があります。1 つは Paxos (plain paxos、single-degree paxos、synod) で、もう 1 つは Multi-Paxos です。エンジニアの観点からすると、1 つ目は分散型ライト ワンス レジスタであり、2 つ目は分散型追記のみのログです。

答え:

  1. Paxos のコンテキストでは、実際の値はライトワンス レジスタに正常に書き込まれた値であり、アクセプターの大部分が同じラウンドの値を受け入れるときに発生します。この論文では、新しく選択された値は常に以前と同じになることが示されました（選択された場合）。したがって、実際の値を取得するには、新しいラウンドを開始し、正常に書き込まれた新しい値を返す必要があります。

    Multi-Paxos のコンテキストでは、実際の値はログに追加された最新の値です。

  2. Multi-Paxos では、ログに新しい値を追加するだけです。現在の値を読み取るために、ログを読み取り、最新バージョンを返します。低レベルの Multi-Paxos は、Paxos レジスタの配列です。新しい値を書き込むには、空きレジスタに現在の値の位置を入れてから、以前の空きレジスタをノーオペレーションで埋めます。2 つのレジスタに同じ前の値に対して 2 つの異なる次の値が含まれている場合、配列内で最も低い位置にあるレジスタを選択します。

  3. Multi-Paxos を使用することは可能であり、些細なことです。無料のレジスターで Paxos の新しいラウンドを開始するだけです。普通の Paxos はそれをカバーしていませんが、それを「拡張」して、dist の代わりに分散変数に変えることができます。登録。このアイデアと証明については、「Paxos の仕組みに関するメモ」の投稿で説明しました。

于 2015-11-07T06:46:18.457 に答える
1

あなたの質問に直接答えるのではなく、Paxos でデータベース トランザクションを実装する方法を説明しようと思います。

最初に気付くのは、ここで 2 つの「値」が問題になっていることです。1 つ目はデータベースの値で、変更されるアプリケーション レベルのデータです。2 つ目は、「コミット」/「中止」の決定です。Paxos ベースのトランザクションの場合、コンセンサス「値」は「コミット」/「中止」の決定です。

Paxos コンセンサスに関するデータベース トランザクションについて留意すべき重要な点は、Paxos は、トランザクションに関与するすべてのピアが実際にコンセンサスの決定を見ることを保証しないということです。これが必要な場合、通常はデータベースの場合と同様に、これが確実に行われるようにすることはアプリケーションに任されています。これは、一部のピアによって保存された状態が他のピアよりも遅れることがあり、Paxos の上に構築されたデータベース アプリケーションには、これを処理するための何らかのメカニズムが必要であることを意味します。これは非常に複雑になる可能性があり、すべてアプリケーション固有であるため、すべてを完全に無視し、すべてのデータベース レプリカの単純過半数がデータベース キー FOO のリビジョン 2 の値に同意することを保証することに焦点を当てます。初期設定は BAR です。

最初のステップは、FOO の新しい値を送信することです。これは BAZ であり、現在のリビジョン 1 が期待されており、Paxos Prepareメッセージと共に送信されます。データベース レプリカがこのメッセージを受信すると、最初に FOO のローカル コピーを検索し、現在のリビジョンが準備メッセージと共に含まれている予想されるリビジョンと一致するかどうかを確認します。それらが一致する場合、データベース レプリカは、 Prepareへの応答として送信されるPromiseメッセージとともに「Vote Commit」フラグをバンドルします。それらが一致しない場合は、代わりに「Vote Abort」が送信されます (リビジョン チェックは、アプリケーションが最後に値を読み取った後に値が変更された場合から保護します。

トランザクション ドライバは、関連する「Vote Commit」/「Vote Abort」値とともにPromiseメッセージのクォーラムを受信すると、「Commit」または「Abort」のいずれかを提案することを選択する必要があります。この値を選択する最初のステップは、Paxos の要件に従って、準備メッセージをチェックして、データベース レプリカント (Paxos 用語でのアクセプター) が「コミット」/「中止」の決定を既に受け入れているかどうかを確認することです。それらのいずれかがある場合、トランザクション ドライバーは、以前に受け入れられた最大の提案 ID に関連付けられた "Commit"/"Abort" 値を選択する必要があります。そうでない場合は、独自に決定する必要があります。これは、「Vote Commit」/「Vote Abort」を見ることによって行われます。秒。「Vote Commmit」の定足数が存在する場合、トランザクション ドライバは「Commit」を提案する場合があります。それ以外の場合は、「Abort」を提案する必要があります。

その時点から、「コミット」/「中止」の決定でコンセンサスに達するまで、やり取りされるのはすべて標準的な Paxos メッセージです。「コミット」が選択されていると仮定すると、データベース レプリカントは FOO に関連付けられた値とリビジョンをそれぞれ BAZ と 2 に更新します。

于 2015-11-05T17:05:15.090 に答える
0

Paxos Made Simpleの論文で説明されているように、paxos を使用してトランザクション ログのレプリケーションを行うというトピックについて、ソースコードへのリンクを含む長いブログを書きました。ここで、あなたの質問に簡単に答えます。ブログ投稿とソースコードは全体像を示しています。

一方では、コンセンサスを維持するためにそうしていることを理解しています。しかしその一方で、値が実際に何であるかについて混乱がありました。「以前に受け入れられた値をアクセプターに送信する必要がある」という点は何ですか?

値は、クライアントがクラスターで実行しようとしているコマンドです。停止中、最後のリーダーによってすべてのノードに送信されたクライアント値は、生き残った多数派の 1 つのノードにしか到達していない可能性があります。新しいリーダーはそのノードではない場合があります。新しいリーダーは、少なくとも 1 つの生き残ったノードからクライアント値を発見し、それを生き残った多数派のすべてのノードに送信します。このようにして、新しいリーダーは死んだリーダーと協力して、進行中のクライアントの作業を完了します。

データベース トランザクションのコンテキストで、新しい値をコミットする必要がある場合はどうなるでしょうか? Paxos の新しいインスタンスを開始する必要がありますか?

最後のリーダーによって選択された選択値の履歴を再構築するまで、クライアントから新しいコマンドを選択することはできません。ブログ投稿では、これについて、古いリーダーがクラッシュした後、新しいリーダーがすべてのノードを完全に最新の状態にしようとする「リーダー テイクオーバー フェーズ」として説明しています。

事実上、過半数のノードに到達した最後のリーダーが送信されたものは何でも選択されます。新しいリーダーはこの歴史を変えることはできません。テイクオーバー フェーズでは、単にノードを同期してすべてを最新の状態にします。新しいリーダーがこのフェーズを終了した場合にのみ、選択されたすべての値で完全に最新であることがわかり、新しいクライアント コマンドを処理できます (つまり、新しい作業を処理できます)。

上記の質問に対する答えが「はい」の場合、アクセプターはどのように状態をリセットしますか?

彼らはしません。選択された値と、その値が選択されたことを学習するノードとの間にはギャップがあります。データベースのコンテキストでは、選択した値を「学習」するまで、値を「コミット」(データ ストアに適用) することはできません。Paxos は、選択された値が取り消されないことを保証します。したがって、値が選択されたことを知るまで、値をコミットしないでください。ブログ投稿では、これについて詳しく説明しています。

于 2015-12-10T15:08:41.203 に答える
0

これは、raft を実装し、ZAB の論文を読んだ私の経験からです。どちらが PAXOS の 2 つの一般的な化身です。私は単純な paxos や multipaxos にはあまり興味がありません。

クライアントがクラスター内の任意のノードにコミットを送信すると、そのコミットをリーダーにリダイレクトし、リーダーはクォーラム内の各ノードにコミット メッセージを送信します。すべてのノードがコミットを確認すると、それ自体のログにコミットします。 .

于 2017-03-30T17:40:18.697 に答える