問題タブ [paxos]

Paxosのようなコンセンサス アルゴリズムは、2 人の将軍が「安全に合意するアルゴリズムを設計することは不可能」であることを証明したとき、どのようにして「安全性 (不一致からの自由) を保証する」のでしょうか?

2 台のサーバーで (1) 確実に番号を交換する (つまり、両方のサーバーが確実に番号を受信したことを両方のサーバーが認識する) か、(2) 両方のサーバーが交換が失敗したことを認識し、そうでないことを認識する最も単純なケースを考えると、状態を変更すると、(2 人の将軍のように) メッセージの失敗は常に矛盾を残す方法で発生する可能性があるように思われます (つまり、一方のサーバーは他方が交換を終了したと考えているが、そうではありませんでした)。

では、Paxos (またはその他のもの) はどのようにして「矛盾からの自由」を本当に保証しているのでしょうか? 簡単な言葉での説明はありますか？2 つのサーバーが保証された交換を行う、または失敗時に交換を完全に放棄することを示す最も単純な疑似コードは何ですか?

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

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

chubby では、db に書き込む各ログのプロセスは paxos プロセスの 1 つのインスタンスであり、このインスタンスには多くのプロポーザーが存在する可能性があるため、マスター選択プロセスが存在します。なぜ多くの提案者がいるのですか？

私がChubbyについて理解しているように、いつでも5台のChubbyサーバーがあります。1 つはマスターで、クォーラムへの書き込みの調整を処理し、他の 4 つのサーバーは読み取り専用で、マスターへの書き込みの転送処理を行います。書き込みは Paxos を使用して一貫性を維持します。

マスターと 4 つのレプリカに違いがある理由を誰かが説明してくれませんか。Chubby がマルチマスターではないのはなぜですか? この質問は Zookeeper にも当てはまります。

I read this post on Paxos paxos value choice but still I am not clear. Assume we run the Paxos for first time and Proposer sends the Prepare and the Acceptors reply with (null, null) since they have not learned any value and so Proposer agrees upon its own value and sends it to the acceptors which they accept. The thing which is confusing me is when a Proposer has received the Promise-acks and needs to send an Accept message:

If any Acceptors had previously accepted any proposal, then they'll have sent their values to the Proposer, who now must set the value of its proposal to the value associated with the highest proposal number reported by the Acceptors. (from Wikipedia)

これが理解できません。「アクセプターによって報告された最大の提案番号に関連付けられた値」を選択することの意味は何ですか? 誰かがこれを例で説明できますか?

私は分散システムが初めてで、「単純な Paxos」について読んでいます。それは多くのおしゃべりを生み出し、パフォーマンスへの影響について考えています。

いくつかの小さなクラスターが異なる場所に配置された、グローバルに分散されたデータベースを構築しているとしましょう。サイト間の通信量を最小限に抑えることが重要と思われます。

1. コンセンサスを使用するために絶対に必要な決定は何ですか? 私が確かに考えた唯一のことは、ネットワークからノード (またはノードのセット?) を追加または削除するかどうかを決定することでした。これは、ベクトル クロックが機能するために必要なようです。もう 1 つ確信が持てなかったのは、同じ場所への書き込みの順序を決定することでしたが、これは Paxos を介して選出されたリーダーによって行われるべきでしょうか?

2. システム内のすべてのノードが一緒に決定を行うことは避けたほうがよいでしょう。各ローカル クラスタのいくつかのノードがクロス クラスタの決定に参加し、すべてのローカル ノードがローカル Paxos を使用して通信し、クロスサイトの質問に対するローカルの回答を決定できますか? ネットワークが飽和していないと仮定すると、待ち時間は同じになりますが、サイト間のネットワーク トラフィックははるかに軽くなります。

3. データベースのテーブルを行に沿って分割し、行の各サブセットをノードのサブセットに割り当てることができるとします。システム内のすべてのマシンで Paxos を使用してデータの各サブセットを含むノードのセットを選択し、そのデータのサブセットを扱うすべての操作に対してそれらのノード間でのみ Paxos を実行するのは正常ですか?

そしてキャッチオール: これに対処するために人々が行っている他のデザイン関連またはアルゴリズムの最適化はありますか?

背景:

Lamport の論文Paxos Made SimpleのImplementing a State Machineという名前のセクション 3 では、Multi-Paxos が説明されています。Multi-Paxos は Google Paxos Made Liveで使用されます。( Multi-Paxos はApache ZooKeeperで使用されます)。Multi-Paxos では、ギャップが発生する可能性があります。

一般に、リーダーは先にコマンドを取得できると仮定します。つまり、コマンド 1 からコマンドが選択された後、コマンドを通じてコマンドαを提案できます。コマンドまでのギャップが発生する可能性があります。i + 1i + αiα - 1

ここで、次のシナリオを検討してください。

システム全体がマスタースレーブアーキテクチャを使用しています。マスターだけがクライアント コマンドを提供します。マスターとスレーブは、Multi-Paxos を介して一連のコマンドについて合意に達します。マスターは Multi-Paxos インスタンスのリーダーです。ここで、マスターとその 2 つのスレーブが次の図に示す状態 (コマンドが選択されている) であると仮定します。

.

マスター状態には複数のギャップがあることに注意してください。非同期性のため、2 つのスレーブは遅れます。この時点で、マスターは失敗します。

問題：

1. マスターの障害を (たとえば、ハートビート メカニズムによって) 検出した後、スレーブは何をすべきか?

2. 特に旧マスターとのズレや不足しているコマンドをどう扱うか。

ザブについての更新:

@sbridges が指摘したように、ZooKeeperは Paxosの代わりにZabを使用します。引用すると、

Zab は主に、ステート マシンの複製用ではなく、ZooKeeper などのプライマリ バックアップ (マスター スレーブ) システム向けに設計されています。

Zab は上記の私の問題と密接に関係しているようです。Zab の簡単な概要論文によると、Zab プロトコルは 2 つのモードで構成されています。リカバリとブロードキャストです。回復モードでは、コミットされたメッセージを決して忘れないことと、スキップされたメッセージを手放すことの2 つの特定の保証が行われます。ザブについての私の混乱は次のとおりです。

3. リカバリ モードでは、Zab もギャップの問題に悩まされますか? もしそうなら、ザブは何をしますか？

私は最近、Paxos について多くの調査を行ってきましたが、常に疑問に思っていたことの 1 つは、答えが見当たらないということです。

Paxos には増加する提案番号が含まれています (また、読んでいる論文の著者によっては、別のラウンド番号もある可能性があります)。そしてもちろん、リーダーになる予定の 2 人が決闘に巻き込まれ、悪循環の中でお互いが相手を追い越そうとすることもあります。しかし、私はビザンチンの P2P 環境で作業しているので、提案番号を非常に高く設定しようとする提案者についてどうすればよいかを考える必要があります。たとえば、最大 32 ビットまたは 64 ビット ワードです。

言語に依存せず、プラットフォームに依存しない Paxos ベースのプロトコルは、提案番号および/またはラウンド番号の整数の最大値をどのように処理する必要がありますか? 特に意図的/悪意のあるケースでは、オーバーフローを 0 に戻すモジュラー演算アプローチが少し魅力的ではありませんか?