詳細な分析: 典型的なトランザクション処理の問題と分散システムのモデル

[[282654]]

すべての企業はデータ サービスの高可用性を望んでいますが、データの高可用性を実現するには、冗長データを複数のコピーで書き込む必要があります。複数のコピーを書き込む問題は一貫性の問題を引き起こし、一貫性の問題はパフォーマンスの問題を引き起こし、解決できない悪循環につながります。ここでのいわゆるデータ一貫性とは、複数のユーザーが同時にデータベースにアクセスしようとしたときに、そのトランザクションで同時に同じデータを使用すると、更新の損失、依存関係の不確実性、分析の不一致、ファントム読み取りの 4 つの状況が発生する可能性があることを意味します。この記事では、分散データの一貫性を処理するためのさまざまな技術モデルを体系的に紹介します。

以下は著者の原文です。

生産ラインでサーバーを使用してデータ サービスを提供する場合、次の 2 つの問題が発生することがよくあります。

• 単一サーバーのパフォーマンスでは、すべてのネットワーク要求を処理するのに十分な容量を提供するのに不十分です。
• サーバーのダウンタイムによりサービスが利用できなくなったり、データが失われたりすることを心配します。

これらの問題に直面したため、パフォーマンスの問題を共有し、単一点障害の問題を解決するために、サーバーを拡張し、マシンを追加する必要がありました。通常、当社はデータ サービスを次の 2 つの方法で拡張します。

• データ パーティショニング: データをブロックに分割し、異なるサーバーに配置することです (uid % 16、一貫性のあるハッシュなど)。
• データミラーリング: すべてのサーバー上のデータを同期し、差別のないデータ サービスを提供します。

最初の解決策ではデータ損失の問題を解決できません。単一のサーバーに問題が発生すると、一部のデータが失われます。したがって、データ サービスの高可用性は、2 番目の方法、つまりデータの冗長ストレージを通じてのみ実現できます (業界では一般的に、Hadoop や Dynamo などのバックアップの最も安全な数は 3 であると考えられています)。ただし、マシンが追加されるほど、データは複雑になり、特にサーバー間のトランザクション処理、つまりサーバー間のデータの一貫性が損なわれます。これは難しい質問ですね！最も典型的な使用例、「アカウント A がアカウント B に資金を送金する」を使用して説明しましょう。 RDBMS トランザクションに精通している人は、アカウント A からアカウント B に資金を送金するには 6 つの操作が必要であることを知っています。

• アカウント A の残高を読み取ります。
• アカウントAで減算演算を実行します。
• 結果をアカウント A に書き戻します。
• アカウント B の残高を読み取ります。
• アカウント B に対して追加操作を実行します。
• 結果をアカウント B に書き戻します。

データの一貫性を保つには、これら 6 つのことはすべて正常に完了するか、いずれも成功しないかのいずれかである必要があります。さらに、この操作中は、アカウント A と B への他のアクセスをロックする必要があります。いわゆるロックとは、他の読み取りおよび書き込み操作を除外することを意味します。そうしないと、ダーティ データの問題が発生します。これは取引です。ただし、複数のマシンを追加すると、この問題は複雑になります。

1. データ パーティション スキームの場合: アカウント A とアカウント B のデータが同じサーバー上にない場合はどうなるでしょうか?マシン間のトランザクション処理が必要です。つまり、A のお金の引き落としは成功したが、B のお金の追加が失敗した場合、A の操作をロールバックする必要があります。異なるマシンに実装するのはより複雑になります。

2. データ ミラーリング ソリューションでは、アカウント A とアカウント B 間の送金は 1 台のマシンで完了できますが、アカウント A とアカウント B のコピーを持つマシンが複数あることを忘れないでください。アカウント A (B と C) に送金する 2 つの同時操作があり、これら 2 つの操作が 2 つの異なるサーバーで発生した場合はどうなるでしょうか。つまり、データミラーリングでは、異なるサーバー上の同じデータに対する書き込み操作の一貫性を確保し、データが競合しないようにするにはどうすればよいでしょうか。

同時に、パフォーマンス要因も考慮する必要があります。パフォーマンスを考慮しなければ、トランザクションを完了することは難しくありません。システムを少し遅くするだけで済みます。パフォーマンスを考慮するだけでなく、可用性も考慮する必要があります。つまり、マシンがなくなった場合でも、データは失われず、他のマシンによってサービスが引き続き提供されるということです。したがって、次のような状況に焦点を当てる必要があります。

• 災害復旧: データ損失なし、ノードフェイルオーバー
• データの一貫性: トランザクション処理
• パフォーマンス: スループット、応答時間

前述したように、データ損失を防ぐ唯一の方法は、データの冗長性を確保することです。データがパーティション分割されている場合でも、各パーティションでデータ冗長化処理を実行する必要があります。これはデータの複製です。特定のノード上のデータが失われた場合、レプリカから読み取ることができます。データ複製は、分散システムがデータ損失の異常を解決する唯一の手段です。したがって、この記事では、データ冗長性がある場合のデータの一貫性とパフォーマンスの問題についてのみ説明します。簡単に言えば:

• データの可用性を高めるには、データのコピーを複数書き込む必要があります。
• 複数のコピーを書き込むと、データの一貫性の問題が発生します。
• データの一貫性の問題はパフォーマンスの問題につながる可能性がある

これはソフトウェア開発であり、1 つの問題を抑制しながら別の問題を生み出すようなものです。

一貫性モデル

データの一貫性に関しては、3 つの単純なタイプがあります (もちろん、細かく分けると、シーケンシャル一貫性、FIFO 一貫性、セッション一貫性、シングル読み取り一貫性、シングル書き込み一貫性など、多くの一貫性モデルがありますが、この記事の簡潔さと読みやすさのために、次の 3 つについてのみ説明します)。

1. 弱い一貫性: 新しい値を書き込むと、読み取り操作でデータのコピー上でその値を読み取れるかどうかが変わります。たとえば、一部のキャッシュ システム、オンライン ゲームの他のプレイヤーのデータはあなたとはまったく関係ありません。VOIP や Baidu 検索エンジンなどのシステムも同様です。

2. 結果的一貫性: 新しい値を書き込むと、読み取り可能ではなくなる可能性がありますが、一定の時間枠が経過すると読み取り可能になることが保証されます。たとえば、DNS、電子メール、Amazon S3、Google 検索エンジンなどのシステムです。

3. 強力な一貫性: 新しいデータが書き込まれると、いつでもどのレプリカでも新しい値を読み取ることができます。たとえば、ファイル システム、RDBMS、Azure テーブルはすべて強力な一貫性を備えています。

これら 3 つの一貫性モデルから、Weak と Become は一般に非同期的に冗長であるのに対し、Strong は一般に同期的に冗長であることがわかります。非同期は通常、パフォーマンスが向上することを意味しますが、状態制御がより複雑になることも意味します。同期は単純さを意味しますが、パフォーマンスの低下も意味します。最も単純なものから最も複雑なものまで、テクニックを段階的に説明しましょう。

マスタースレーブ

1 つ目はマスター スレーブ構造です。この構造では、スレーブは通常、マスターのバックアップになります。このようなシステムは、一般的に次のように設計されます。

• マスターは読み取り要求と書き込み要求の両方を担当します。
• 書き込み要求がマスターに書き込まれた後、マスターによってスレーブに同期されます。

マスターからスレーブにデータを同期するには、非同期または同期の方法を使用できます。マスターを使用してデータをプッシュしたり、スレーブを使用してデータをプルしたりできます。一般的に言えば、スレーブは定期的にデータをプルするため、最終的な一貫性が保たれます。この設計の問題点は、プル サイクル中にマスターに障害が発生すると、このタイム スライス内のデータが失われることです。データを失いたくない場合は、スレーブは読み取り専用モードでのみ動作し、マスターが回復するまで待機します。

もちろん、データ損失が許容される場合は、スレーブがすぐにマスターを置き換えることができます (コンピューティングのみを担当するノードの場合、データの一貫性とデータ損失の問題はなく、マスター スレーブ アプローチによって単一ポイントの問題を解決できます)。もちろん、マスター スレーブも強力な一貫性を持つことができます。たとえば、マスターに書き込む場合、マスターは最初にバックアップし、成功した後にスレーブに書き込む必要があります。両方が成功すると成功が返され、プロセス全体が同期されます。スレーブへの書き込みに失敗した場合、2 つの方法があります。 1 つは、スレーブを使用不可としてマークし、エラーを報告してサービスを継続することです (スレーブが回復した後にマスターのデータを同期します。スレーブは複数存在する可能性があるため、1 つ少なくなりますが、前述のように 3 つのコピーを書き込むのと同じように、バックアップは残ります)。もう 1 つは、スレーブ自体をロールバックして書き込み失敗を返すことです。 (注: 一般的に、スレーブは最初に書き込まれません。マスターへの書き込みが失敗した場合、スレーブをロールバックする必要があるためです。スレーブのロールバックが失敗した場合、データを手動で修正する必要があります。) マスターとスレーブを高度に一貫性のあるものにする必要がある場合、それがいかに複雑であるかがわかります。

マスターマスター

マスター-マスター (マルチマスターとも呼ばれます) は、システム内に 2 つ以上のマスターがあり、各マスターが読み取り/書き込みサービスを提供することを意味します。このモデルは、マスタースレーブモデルの拡張バージョンです。データ同期は通常、マスター間で非同期的に完了するため、最終的には一貫性が保たれます。マスター-マスターの利点は、1 つのマスターに障害が発生した場合でも、他のマスターが読み取りおよび書き込みサービスを引き続き提供できることです。これはマスタースレーブと同じです。データが他のマスターに複製されない場合、データは失われます。多くのデータベースはマスター-マスター レプリケーション メカニズムをサポートしています。

さらに、複数のマスターが同じデータを変更すると、このモデルの悪夢が発生します。データ間の競合をマージする必要があり、これは非常に困難です。 Dynamo の Vector Clock (データのバージョン番号と修飾子の記録) の設計を見ると、この問題はそれほど単純ではなく、Dynamo はデータ競合の問題をユーザー自身に任せていることがわかります。 SVN ソース コードの競合と同様に、同じコード行の競合は開発者自身によってのみ処理できます。 (Dynamo の Vector Clock については、この記事の後半で説明します)

2/3 フェーズコミット

このプロトコルの略称は 2PC とも呼ばれ、中国語で 2 フェーズ コミットを意味します。分散システムでは、各ノードは自身の操作が成功したか失敗したかを知ることができますが、他のノードの操作が成功したか失敗したかを知ることはできません。トランザクションが複数のノードにまたがる場合、トランザクションの ACID 特性を維持するために、すべてのノード (参加者と呼ばれる) の操作結果を均一に制御し、最終的にこれらのノードに操作結果を実際にコミットするかどうか (更新されたデータをディスクに書き込むなど) を指示するコーディネーター コンポーネントを導入する必要があります。 2 フェーズ コミット アルゴリズムは次のとおりです。

フェーズ1:

• コーディネーターは、すべての参加ノードにコミット操作を実行できるかどうかを尋ねます。
• 各参加者は、リソースのロック、リソースの予約、UNDO/REDO ログの書き込みなど、トランザクション実行の準備を開始します。
• 参加者はコーディネータに応答し、トランザクションの準備が成功した場合は「送信可能」と応答し、そうでない場合は「送信を拒否」と応答します。

フェーズ2:

• すべての参加者が「送信してよい」と応答した場合、コーディネーターはすべての参加者に「正式な送信」コマンドを送信します。参加者は正式な提出を完了し、すべてのリソースを解放した後、「完了」と応答します。コーディネーターは各ノードから「完了した」応答を収集し、グローバル トランザクションを終了します。
• 参加者の 1 人が「コミットを拒否」と応答した場合、コーディネーターはすべての参加者に「ロールバック操作」を送信し、すべてのリソースを解放してから、「ロールバックが完了しました」と応答します。コーディネーターは各ノードから「ロールバック」応答を収集した後、グローバル トランザクションをキャンセルします。

ご覧のとおり、2PC は単純に第 1 段階で投票を行い、第 2 段階で決定を行うアルゴリズムです。 2PC は強力な一貫性アルゴリズムであることもわかります。前述のマスター/スレーブの強力な一貫性戦略は、2PC と多少似ていますが、2PC の方がより保守的 (最初に試行してから送信) である点が異なります。 2PC の方が頻繁に使用されます。一部のシステム設計では、一連の呼び出しが A -> B -> C -> D のように連続して接続されます。各ステップでは、リソースが割り当てられたり、データが書き換えられたりします。たとえば、B2C オンライン ショッピングの注文操作では、一連のプロセスをバックグラウンドで完了する必要があります。段階的にやると問題が起こります。特定のステップを完了できない場合は、それまでに割り当てられたリソースをすべて元に戻して回復する必要があります。そのため、操作はより複雑になります。現在、多くの処理プロセス (ワークフロー) は 2PC アルゴリズムを利用し、try -> confirm プロセスを使用してプロセス全体が正常に完了することを確認します。よくある例を挙げると、西洋の教会で結婚式を挙げるときには、必ずこのような場面があります。

1. 牧師は新郎新婦に別々に尋ねました。「生、病、老い、死に関わらず、…する意志がありますか…」

2. 新郎新婦が両方とも「はい」と答えると（生涯のリソースをロックします）、牧師は次のように言います。「私はあなたに宣言します...（取引の提出）

これは典型的な 2 フェーズ コミット トランザクションです。さらに、いくつかの問題が見られます。A) その 1 つは同期ブロッキング操作であり、これは必然的にパフォーマンスに大きな影響を与えます。 B) もう一つの大きな問題はタイムアウトです。例えば、

1. 最初のフェーズで、参加者がクエリ要求を受信しないか、参加者の応答がコーディネータに届かない場合。次に、コーディネーターがタイムアウトを処理する必要があります。タイムアウトが発生すると、失敗とみなされるか、再試行されます。

2. 一部の参加者が第 2 段階で正式な送信が送信された後それを受信しなかった場合、または参加者の送信/ロールバック後の確認情報が返されなかった場合、参加者の応答がタイムアウトしたら、再試行するか、参加者を問題のあるノードとしてマークしてクラスター全体から削除し、サービス ノードのデータの一貫性を確保します。

3. 最悪のシナリオは、第 2 フェーズで参加者がコーディネータからコミット/フォールバック指示を受信しない場合、「不明ステータス」フェーズになり、何をすべきか分からなくなることです。たとえば、参加者全員が第 1 フェーズで応答を完了し (すべて「はい」、すべて「いいえ」、一部が「はい」、一部が「いいえ」など)、この時点でコーディネーターが死亡したとします。そうすると、すべてのノードは何をすべきか分からなくなります (他の参加者に尋ねても機能しません)。一貫性を保つために、コーディネータを待つか、最初のフェーズで yes/no コマンドを再送信します。

2 フェーズ コミットの最大の問題は項目 3 です。第 1 フェーズが完了した後、参加者が第 2 フェーズで決定を受け取らないと、データ ノードは「混乱」状態になり、トランザクション全体がブロックされます。つまり、トランザクションの完了にはコーディネーターが非常に重要であり、コーディネーターの可用性が鍵となります。そこで、3 フェーズ コミットを導入します。 Wikipedia での 3 フェーズ コミットの説明は次のとおりです。2 フェーズ コミットの最初のフェーズを、クエリとリソースのロックの 2 つのフェーズに分割します。最後に、実際に送信します。 3 段階の提出の概略図は次のとおりです。

3 フェーズ コミットの中心的な概念は、要求時にリソースがロックされず、全員が同意するまでリソースがロックされないことです。

理論的には、第 1 フェーズのすべてのノードが成功を返した場合、送信が成功する確率が非常に高いと考えられます。これにより、参加者コホートのステータスが不明になる可能性が低くなります。言い換えれば、参加者が PreCommit を受け取ると、全員が実際に変更に同意していることが分かることになります。これはとても重要です。 3PC の状態遷移図を見てみましょう: (図の点線に注意してください。F、T は Failuer または Timeout で、ステータスは q - Query、a - Abort、w - Wait、p - PreCommit、c - Commit を意味します)

実際、3 フェーズ コミットは非常に複雑なものであり、実装が非常に難しく、いくつかの問題もあります。

これを見ると、たくさんの疑問が湧いてくると思います。 2PC/3PC のさまざまな障害シナリオについて考えているはずです。タイムアウトは対処が非常に難しいものであることがわかります。なぜなら、インターネットでのタイムアウトでは途方に暮れてしまうことが多く、相手がタイムアウトしたかどうかもわからないからです。つまり、タイムアウトにより、正常なステート マシンが装飾品になってしまいます。

ネットワーク サービスには、1) 成功、2) 失敗、3) タイムアウトの 3 つの状態があります。 3 番目は、特に状態を維持する必要がある場合には、間違いなく悪夢です。

二人の将軍の問題

二人の将軍問題は思考実験です。それぞれ将軍が率いる 2 つの軍隊があり、要塞化された都市を攻撃する準備をしています。両軍は市街地の近くに駐屯し、丘を占領した。二つの山は谷で隔てられており、二人の将軍が連絡を取る唯一の方法は、谷の両側にそれぞれ使者を送り届けることだった。残念なことに、谷は都市の防衛軍によって占領されており、谷を通って送られた使者は逮捕される可能性がありました。 2 人の将軍は都市を攻撃することには同意していたものの、それぞれが丘の頂上を占領するまで攻撃のタイミングについては合意していなかったことに注意してください。成功するには、両方の将軍が同時に軍隊を都市に攻撃させなければなりません。したがって、攻撃する時間を決定し、その時間に攻撃することに合意するために、お互いに通信する必要があります。もし将軍が一人だけ攻撃したら、それは壊滅的な失敗となるだろう。思考実験では、将軍がこれをどのように実行するかを検討します。この件に関して、いくつか考えを述べます。

1. 最初の将軍が「午前9時に攻撃を開始しましょう」というメッセージを送信します。しかし、使者が送られた後、最初の将軍には彼が谷を通り抜けたかどうかは分かりませんでした。少しでも不確実性があれば、第一将軍は攻撃を躊躇するだろう。なぜなら、第二将軍が同時に攻撃に失敗した場合には、都市の守備隊が彼の軍隊の攻撃を撃退し、その結果彼の軍隊は壊滅することになるからだ。

2. これを知った第 2 将軍は、「メッセージを受け取りました。9 時に攻撃します」という確認メッセージを送信する必要があります。しかし、確認メッセージを持ったメッセンジャーが捕まったらどうなるでしょうか?そのため、2 番目の将軍は確認メッセージが届くかどうか躊躇するでしょう。

3. したがって、最初の将軍に「確認を受け取りました」という別の確認メッセージを送信するよう依頼する必要があるようです。しかし、もし伝令が捕まったらどうなるでしょうか?

4. この場合、2 番目の将軍が「確認の受信を確認する」メッセージを送信する必要がありますか?

そのため、確認メッセージを何度送信しても、2 人の将軍が使者が敵に捕らえられていないことを十分に確信できない状況にすぐに発展することがわかります。

この問題には解決策はありません。 2 人の将軍の問題とその解決不可能な証明は、1975 年に EA Akkoyunlu、K. Ekanadham、RV Huber によって「ネットワーク通信設計におけるいくつかの制限とトレードオフ」という論文で初めて発表されました。この論文の 73 ページで、2 つのギャング間の通信を説明する段落で説明されています。 1978 年、ジム・グレイの著書『データベース オペレーティング システム ノート』(465 ページ以降) で、このパラドックスは「2 人の将軍のパラドックス」と名付けられました。この参考文献は、2 人の将軍問題の定義と解決不可能性の証明の出典として広く引用されています。

この実験は、信頼性の低い接続を介して通信することでアクションを調整しようとする際の落とし穴と設計上の課題を示すことを目的としていました。

エンジニアリングの観点から見ると、2 人の将軍の問題に対する実際的なアプローチは、通信チャネルの信頼性の低さに耐えられる方式を使用し、信頼性の低さを排除するのではなく、信頼性の低さを許容できるレベルまで下げることです。たとえば、最初の将軍は 100 人の使者を配置し、全員が捕らえられる可能性は低いと予想します。この場合、2 番目の将軍が攻撃するか、ニュースを受け取るかに関係なく、1 番目の将軍が攻撃します。あるいは、最初の将軍がメッセージのストリームを送信し、2 番目の将軍が各メッセージの確認応答を送信して、各メッセージが受信された場合に両方の将軍の気分が良くなるようにすることもできます。しかし、証拠から判断すると、どちらも攻撃が調整可能かどうか確信が持てなかった。片方からの攻撃だけを確実に防ぐアルゴリズム (例: 4 つ以上のメッセージを受信した後の攻撃) は利用できません。さらに、最初の将軍は、各メッセージに番号を付けることもできます。つまり、これは 1 番、2 番、... と番号 n まで付けます。この方法により、副将軍は通信チャネルの信頼性を把握し、最後のメッセージが確実に受信されるように適切な数のメッセージを送り返すことができます。チャネルが信頼できる場合は、必要なメッセージは 1 つだけであり、残りのメッセージはあまり役に立ちません。最後のメッセージと最初のメッセージが失われる確率は同じです。

2 人の将軍問題は、より複雑なビザンチン将軍問題に拡張することができます。背景ストーリーは次のとおりです。ビザンチウムは現在のトルコのイスタンブールに位置し、東ローマ帝国の首都でした。当時のビザンチン・ローマ帝国は広大だったため、防衛上の理由から各軍は遠く離れており、将軍たちは伝言を伝達するために使者に頼るしかありませんでした。戦争中、ビザンチン軍の将軍は全員、敵陣を攻撃する前に勝利の可能性があるかどうかを判断するために全員一致の合意に達しなければなりませんでした。しかし、軍隊には、意思決定プロセスを妨害したり影響を与えたりする裏切り者や敵のスパイがいる可能性があります。この時点で、メンバーの 1 人が反乱を企てていることがわかっている場合、残りの忠実な将軍たちは、裏切り者の影響を受けずに、どのようにして全員一致の合意に達することができるでしょうか。これはビザンチン将軍問題です。

PAXOSアルゴリズム

Wikipedia にはさまざまな Paxos アルゴリズムの説明が非常に詳しく載っているので、ぜひご覧ください。

Paxos アルゴリズムが解決する問題は、上記の例外が発生する可能性がある分散システムで、どのような例外が発生しても解決の一貫性が損なわれないようにしながら、特定の値について合意に達する方法です。典型的なシナリオとしては、分散データベース システムでは、各ノードの初期状態が一貫しており、各ノードが同じ一連の操作を実行すると、最終的に一貫した状態が得られます。各ノードが同じコマンドシーケンスを実行するようにするには、各命令に対して「一貫性アルゴリズム」を実行して、各ノードが認識する命令が一貫していることを確認する必要があります。一般的なコンセンサス アルゴリズムは多くのシナリオに適用でき、分散コンピューティングにおける重要な問題です。一貫性アルゴリズムの研究は 1980 年代から止まることなく続いています。

注: Paxos アルゴリズムは、1990 年に Leslie Lamport (LaTeX の「La」、現在は Microsoft Research 所属) によって提案されたメッセージ パッシングに基づくコンセンサス アルゴリズムです。このアルゴリズムは理解しにくいため、当初は注目を集めませんでしたが、Lamport は 8 年後の 1998 年に ACM Transactions on Computer Systems で再公開しました。それでも、Paxos アルゴリズムは真剣に受け止められませんでした。 2001年、ランポート氏は自分のユーモアのセンスが同業者に受け入れられないと感じ、より受け入れやすい形でそれを言い直した。 Lamport は Paxos アルゴリズムを特に好んでいることがわかります。近年の Paxos アルゴリズムの広範な使用は、分散コンセンサス アルゴリズムにおけるその重要な位置を証明しています。 2006 年に、Google は「クラウド」の概念を初めて示した 3 つの論文を発表しました。 Chubby Lock サービスは、Chubby Cell の一貫性アルゴリズムとして Paxos を使用しており、それ以来 Paxos の人気は急上昇しました。 (ランポート氏自身がブログで、このアルゴリズムを公開するのに 9 年かかったことを説明しています)

注: Amazon の AWS では、すべてのクラウド サービスは Paxos アルゴリズムを使用する ALF (Async Lock Framework) フレームワークに基づいて実装されています。アマゾンにいた頃、社内共有ビデオを見ました。設計者は社内のプリンシパルトークで、ZooKeeper の方法を参考にしたが、ZooKeeper よりも読みやすい別の方法でアルゴリズムを実装したと述べました。

簡単に言えば、Paxos の目的は、クラスター全体のノードが値の変更について合意に達するようにすることです。 Paxos アルゴリズムは基本的に民主的な選挙アルゴリズムであり、多数決の決定がクラスター全体の統一された決定になります。どのノードも特定のデータの変更を提案できます。提案が承認されるかどうかは、クラスター内の半数以上のノードが同意するかどうかによって決まります (そのため、Paxos アルゴリズムではクラスター内のノード数が奇数である必要があります)。

このアルゴリズムには 2 つのステージがあります (A、B、C の 3 つのノードがあると仮定)。

フェーズ1: 準備

A は、変更要求 Prepare Request をすべてのノード A、B、C に送信します。Paxos アルゴリズムにはシーケンス番号があることに注意してください (これは、継続的に増加し、一意である提案番号と考えることができます。つまり、A と B は同じ提案番号を持つことはできません)。この解決番号は変更要求とともに送信されます。 「準備フェーズ」のどのノードも、現在の提案数よりも実際に小さいリクエストを拒否します。したがって、ノード A がすべてのノードに変更要求を申請する場合、提案番号を含める必要があります。提案が新しいほど、提案番号が大きくなります。

受信ノードが受信した提案番号 n が他のノードから送信された提案番号より大きい場合、このノードは Yes (このノードで承認された最新の提案番号) で応答し、コミットメントのために他の提案を受け入れないことを保証します。 <>

最適化: 上記の準備プロセス中に、いずれかのノードがより高い番号の提案があることを発見した場合、提案者に通知して提案を中断するよう通知する必要があります。

フェーズ2: 受け入れフェーズ

提案者 A が半数以上のノードから Yes を受け取った場合、提案者 A はすべての結果に対して Accept Request (提案番号 n を使用) を発行します。半分以下であれば失敗を返します。

ノードが Accept 要求を受信すると、受信した結果の n が最大であれば、この値を変更します。より大きな提案番号があることがわかった場合、ノードはそれを変更することを拒否します。

これは「2 フェーズ コミット」の最適化であることがわかります。実際、2PC/3PC はどちらも分散一貫性アルゴリズムの欠陥バージョンです。 Google Chubby の作者である Mike Burrows 氏は、世界には一貫性アルゴリズムが 1 つだけ存在し、それが Paxos であり、他のアルゴリズムは欠陥製品であると述べています。

また、異なるノードでの同じ値の変更提案については、受信側で順序が逆になっても問題がないこともわかります。

いくつかの例については、Wikipedia 中国語版の「Paxos の例」セクションを参照してください。ここでは詳細には触れません。 Paxos アルゴリズムのいくつかの異常な例を自分で推測することができます。基本的に、半分以上のノードが稼働している限り、問題は発生しないことがわかります。

さらに少し付け加えると、Lamport が 1998 年に Paxos アルゴリズムを発表して以来、Paxos に対するさまざまな改良が止まることなく続けられてきましたが、最も重要なのは 2005 年に発表された Fast Paxos です。改良にかかわらず、メッセージのレイテンシとパフォーマンスおよびスループットの間のさまざまなトレードオフを行うことに重点が置かれています。概念的に両者を簡単に区別するために、前者は Classic Paxos と呼ばれ、改良された後者は Fast Paxos と呼ばれます。

要約する

次の画像は、Google App Engine の共同創設者である Ryan Barrett 氏が 2009 年の Google I/O で行ったスピーチからの抜粋です。

前述したように、データの可用性を高めたい場合は、冗長データのコピーを複数書き込む必要があります。複数のコピーを書き込む問題は一貫性の問題を引き起こし、一貫性の問題はパフォーマンスの問題を引き起こします。上の図から、基本的にすべてのアイテムを緑色にすることはできないことがわかります。これは有名な CAP 理論、つまり一貫性、可用性、分断耐性です。 2つ持っていてもいいですよ。

NWR モデル

最後に、Amazon Dynamo の NWR モデルについて触れておきます。この NWR モデルでは、ユーザーに CAP を選択する権利が与えられ、ユーザーは 2 つの CAP を選択できます。

いわゆるNWRモデル。 N は N 個のバックアップを表し、W は成功と見なされるために少なくとも W 個のコピーを書き込む必要があることを表し、R は少なくとも R 個のバックアップを読み取ることを表します。設定中は、W+R>N が必要です。 W+R > N なので、R > NW です。これはどういう意味ですか？つまり、書き込みが成功するようにするには、読み取られるコピーの数が、バックアップの合計数から倍数を引いた差よりも大きくなければなりません。

つまり、読むたびに少なくとも最新バージョンを読むことになります。こうすることで、古いデータが読み取られなくなります。書き込み性の高い環境が必要な場合は、W = 1、N = 3 の場合は R = 3 と設定できます。このとき、いずれかのノードが正常に書き込まれれば成功とみなされますが、読み取りの場合はすべてのノードからデータを読み取る必要があります。高い読み取り効率が必要な場合は、W=NR=1 を設定できます。現時点では、いずれかのノードの読み取りが成功すると成功とみなされますが、書き込みの場合は、3 つのノードすべてが成功しないと成功とみなされません。

NWR モデルの一部の設定では、明らかに Paxos のような強力な一貫性がないため、ダーティ データの問題が発生します。したがって、各読み取りおよび書き込み操作は同じノード上で行われない可能性があり、一部のノード上のデータは最新バージョンではない可能性がありますが、最新の操作が実行されています。

そこで、Amazon Dynamo ではデータバージョンの設計を導入しました。つまり、読み取ったデータのバージョンが v1 の場合、計算が完了した後にデータをバックフィルしようとしたときに、データのバージョン番号が v2 に更新されていることがわかった場合、サーバーは拒否します。バージョン管理は「楽観的ロック」のようなものです。

ただし、分散モデルと NWR モデルの場合、バージョンには悪夢、つまりバージョン競合の問題が発生することもあります。たとえば、N=3、W=1 に設定します。ノード A で値が受け入れられ、バージョンが v1 -> v2 に変更されたが、ノード B にまだ同期されていない場合 (非同期、W は 1 で、1 つのコピーの書き込みは成功したと見なされる)、ノード B のバージョンはまだ v1 のままです。このとき、ノード B は書き込み要求を受信します。論理的にはそれを拒否する必要がありますが、一方で、他のノードが v2 に更新されたことを認識していません。一方、W=1 なので拒否できず、1 つのコピーを書き込むことは成功します。その結果、重大なバージョンの競合が発生しました。

Amazon の Dynamo はバージョン競合の問題を巧みに回避します。バージョン競合の問題はユーザーが処理することになります。

そこで、Dynamo は Vector Clock (ベクトル クロック?!) デザインを導入しました。この設計により、各ノードは独自のバージョン情報を記録できます。つまり、同じデータに対して、1) 誰が更新したか、2) バージョン番号は何か、という 2 つのことを記録する必要があります。

次に、一連の操作を見てみましょう。

書き込み要求はノード A によって初めて処理されます。ノードAはバージョン情報（A、1）を追加します。この時点でのデータをD1(A, 1)として記録します。その後、同じキーに対する別の要求が A によって処理されるため、D2(A, 2) が存在します。このとき、D2 は D1 をカバーできるため、競合は発生しません。

ここで、D2 がすべてのノード (B と C) に伝播したと仮定します。 B と C が受信したデータはクライアントによって生成されたものではなく、他のクライアントによってコピーされたものなので、新しいバージョン情報は生成されません。したがって、BとCが保持するデータは依然としてD2（A、2）です。したがって、A、B、C のデータとバージョン番号は同じです。

ノード B への新しい書き込み要求がある場合、ノード B はデータ D3 (A, 2; B, 1) を生成します。これは、データ D のグローバル バージョン番号が 3 であり、A が 2 回更新され、B が 1 回更新されたことを意味します。これはいわゆるログのコード版ではないでしょうか？ D3 が C に伝播されず、別の要求が C によって処理される場合、C ノード上のデータは D4 (A, 2; C, 1) になります。

D3 が C に伝播されず、別の要求が C によって処理される場合、C ノード上のデータは D4 (A, 2; C, 1) になります。

さて、ここに最もエキサイティングなことがあります。この時点で読み取りリクエストが届く場合、w = 1 then r = n = 3であるため、Rは3つのノードすべてから読み取ることを覚えておく必要があります。この時点で、彼は3つのバージョンを読みます。

ノードA：D2（A、2）

ノードB：d3（a、2; b、1）;ノードC：D4（A、2; C、1）

ノードC：D4（A、2; C、1）

6。この時点で、D2はすでに古いバージョン（D3/D4に既に含まれている）であり、破棄できると判断できます。

7.ただし、D3とD4は明らかなバージョンの競合です。したがって、バージョンの競合を処理するのは発信者次第です。ソースコードバージョン管理のように。

明らかに、上記のダイナモ構成では、キャップ内のAとPを使用します。