問題タブ [paxos]

操作ログをレプリケーションに同期することで、paxos を使用してレプリケーションの同期を維持できることを読みました。

私の理解では、各 paxos インスタンスは操作でログ ID を定義します

理想的には、ログは各ノードでこのようになるため、データの一貫性を保つために、ログ ID の順序で操作ログを適用します。

1. 消去 ....
2. 追加 ...
3. 削除する ...

私の理解では、ログ ID は 1 つずつ増加しないため、ログは次のようになります。

1.削除 ....

3.追加...

5.削除...

私の質問は、paxos インスタンス中に 1 つのノードがダウンした場合、実際にどのように機能するかということだと思います。

このノードでは 1 つのログ エントリが失われるため、このノードは回復後にエントリが失われたことをどのように認識しますか?

ウィキによると

https://en.wikipedia.org/wiki/Paxos_(computer_science)#Multi-Paxos

複数の paxos は、ログ ID が常にギャップなく増加するようにするために実装されているようです。

そうは言っても、私の理解では、各レプリケートは、最新の変更が適用されていることを確認するために、定期的にいくつかと対話する必要があります。

Paxos を使用して、サイズが約 50MB で、個々のノードで常に変更されているファイルのノード間のコンセンサスを維持しようとしています。実用性の問題に直面しています。要件：

1. 数百のノード間で 50MB 以上のファイルを同期
2. このファイルに変更を加えます。これはどのノードからでも行うことができ、互いに直接競合する可能性は低く、せいぜい数秒でネットワーク全体に伝播されます。
3. ネットワークに参加する新しいノードは、Paxos メッセージに従って、数分 (1 時間未満) 以内にファイル全体を構築できます。

私が直面している問題は、目標 2 と 3 の両方を達成する方法がないように見えることです。

これまでに検討したオプションは次のとおりです。

• ラウンドごとにファイル全体を同期する — 完全に非現実的で、Paxos ラウンドには数分かかります
• ファイルへの変更のみを同期 — 目標 1 と 2 には妥当ですが、新しいノードはすべての状態単位が変更された後にのみファイル全体を同期できるため、目標 3 を破ります。
• ラウンドごとに変更とファイルのランダムな部分を同期します — Paxos がこれを許可するかどうかはわかりません。ノードは自分自身に対して変更を検証することができ (新しい変更を許可する)、ファイルのランダムな部分をそれらのバージョンのその部分に対して検証することができますが、これは実用的ですか?

私は 3 番目のオプションが最適だと考えていますが、Paxos がこれを許可するかどうかはわかりません。アイデアは、各ラウンドで交換されるデータをおそらく 1500 バイトに制限し、その 1500 バイトを主にファイルへの変更で埋めることです。ほとんどのラウンドでは、ファイルは変更されず、何かが変更されたラウンドは 100 バイト未満の変更された状態である可能性が高いため、他の 1400 バイトはファイルの一部で満たされる可能性があり、これにより新しいノードを構築できます。時間をかけてファイル全体をアップします。これは実用的ですか？この問題はすでに解決されていますか?

MIT 6.824 クラスを学んでいて、paxos について質問があります。プロポーザーが準備をアクセプターに送信すると、アクセプターは準備OKをnとvで返します。アクセプターが n と v を返す必要があるのはなぜですか?

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

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

質問:

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

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

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

最近私は を学んPaxosでいますが、今まではそれがどのように機能するかについての基本的な理解をすでに持っています。しかし、Paxos がパケット損失と新しいノードの参加をどのように処理するかを説明できる人はいますか? 簡単な例が提供されている場合は、より良いかもしれません。

Cassandra 2.0.12 (DataStax Community エディション) を実行する 9 ノードのクラスターがありました。このクラスターを拡張する必要があったため、DataStax に従ってさらに 3 つのノードを追加しました。

私たちのアプリケーションは Light Weight Transaction 機能を利用しており、新しいノードが JOINING 状態 (古いノードからデータがストリーミングされている) である間、LWT を含むほとんどのアプリケーション呼び出しが次のエラーで失敗することがわかりました。

com.datastax.driver.core.exceptions.UnavailableException: 一貫性 SERIAL でクエリに使用できる十分なレプリカがありません (6 つが必要ですが、5 つしか有効ではありません)

よくわかりません

1. レプリケーション ファクターが 3 のときに、エラー メッセージに 6 ノードが必要であると表示されるのはなぜですか。これは、現在新しいノードによって所有されている範囲の古いノードから新しいノードにデータがストリーミングされている間、PAXOS では古いノードと新しいノードの両方が必要になることを意味しますか?さまざまなPAXOSステージに関与していますか？

2. 私の理解では、新しいノードがクラスターに参加している間、古いノードは引き続きすべてのクライアント要求を取得しますが (新しいノードが現在所有しているトークン範囲に対して)、古いノードはすべての書き込み要求を新しいノードに転送し、読み取り要求を引き続き処理します。 . CAS操作はREADとWRITEの両方を意味するため、LWTとPaxosでどのように機能しますか。これが、CAS (IF NOT EXISTS) 操作を実行するときに 6 ノードの応答が必要な理由である可能性があります。その場合でも、ほとんどの CAS 操作が失敗するのはなぜですか? 新しいノードが参加している間に LWT にバグの可能性がありますか、それとも新しいノードが非常にビジーで応答していないという事実ですか。私の場合、新しいノードが JOINING 状態にある間、常に非常にビジーではなかったと確信していますが、LWT 呼び出しは、JOINING 状態にある間はほぼ常に失敗していました。

3 つの新しいノードのうち 2 つがクラスターに参加するとすぐに、エラーの数が大幅に減少し、3 番目のノードも参加するとすぐに確認できました (最初のノードが参加するのに約 5 時間かかり、その後 10 ～ 20 分で他のノードが続きました)。すべてのエラーがなくなり、アプリケーションは正常に戻りました。

誰かがこの動作と、実際に「本番環境」をアップグレードするときにこれらのエラーを回避するために何ができるかを説明してもらえますか (上記のテストはテスト環境で行われました)。

下の図は、基本的な Paxos のメッセージ フローです。フェーズ 2a で、リーダーはその提案 1 の値 Vn を選択し、Accept!(1,Vn) をすべてのアクセプターに送信します。私の質問は、これら 3 つのメッセージのうち 2 つが失われた場合はどうなるかということです。Accept!(1,Vn) を受け取るのは Acceptor 1 (多数派ではない) だけです。Acceptor 1 はこの要求を受け入れますか? そして、すべての学習者にブロードキャストしますか? この値は選択されていますか?

いくつかのマシンをエラスティック クラスターに投入し、その中で何らかのコンセンサス アルゴリズムを実行したいとします (Paxos など)。彼らがネットワークの初期サイズ、たとえば 8 台のマシンを知っているとします。

したがって、彼らはコンセンサス アルゴリズムを実行し、定足数は 5 です。

ここで、次のケースを検討してください。

1. CPU が少なすぎることがわかり、クラスター サイズを半分の 4 台のマシンに減らしました。
2. パーティション分割があり、各分割には 4 台のマシンが割り当てられます。

クォーラムを取得するために現在のクラスター サイズを使用すると、パーティションが分割される可能性があります。基礎となるクラスターの場合、状況 (1) と (2) はまったく同じに見えます。ただし、固定数を使用すると、クラスターをスケールダウンできません (スケールアップすると、パーティションによる不整合が発生します)。

スケーリング時にすべてのマシンにクラスターのサイズを通知する 3 つ目の方法がありますが、たとえば、スケールアップの直前にパーティションが発生し、そのパーティションが新しいサイズを受け取らず、十分なクォーラムを持っていない可能性があります。古いサイズを使用したコンセンサス。

Paxos (およびその他の安全なコンセンサス アルゴリズム) は、柔軟な環境では使用できませんか?

Spanner: Google の Globally-Distributed Databaseのセクション 2.1 には、次のように書かれています。

レプリケーションをサポートするために、各スパンサーバーは各タブレットの上に単一の Paxos ステート マシンを実装します。(初期の Spanner 化身は、タブレットごとに複数の Paxos ステート マシンをサポートしていたため、より柔軟なレプリケーション構成が可能でした。その設計の複雑さにより、私たちはそれを放棄しました。)

Paxos ステート マシンは、一貫して複製されるマッピングのバッグを実装するために使用されます。

この単一の Paxos ステート マシンは、「Paxos Made Simple」で言及されている Paxos ステート マシンと似ていますか?

新しいリーダーが失われたすべてのデータを学習する方法を選択したときのことを知りたいです。Spanner での Paxos グループの詳細な実装について説明できる人はいますか?