CAPとPaxosコンセンサスアルゴリズムについての簡単な説明

CAPとは

CAP理論についてはすでに多くの背景情報が語られているので、ここでは詳しくは触れません。どのように理解するかについてお話ししましょう。

次の 3 つの用語をわかりやすい言葉で説明してください。

一貫性

ノードに書き込んだばかりの場合、別のノードから読み取られるデータは、古いデータではなく、書き込まれたばかりのデータである必要があります。

可用性

ノードを要求した場合、ノードは応答できる必要があります。ノードがダウンしている場合、可用性の問題はありません。

パーティション耐性

ネットワーク パーティションを許容するかどうか、つまり、ノードが他のノードと通信できないようにするかどうか。

CAP は、最大で 2 つの条件が同時に満たされることしか保証できないことを意味します。

その理由を見てみましょう。

[[314890]]

図に示すように、パーティション許容値を満たす場合、点線は 2 つのノードがパーティション分割されていることを示します。

• 一貫性の要件を満たしたい場合は、別のノードにリクエストする操作を一時的に停止し、クライアント障害またはタイムアウトの結果を返すことしかできません。この状況は、ユーザーの操作を一時的に妨げるよりも、ユーザーの資金の正確性を確保することの方が重要であるため、データ一貫性の要件が非常に高い銀行カウンターなどの状況でよく発生します。
• 可用性を満たす場合、ネットワークが分離されているため一貫性は実現できません。このような状況は、データの一貫性はそれほど要求されないが可用性に対する要件が高いニュースなどのインターネット業界でよく発生します。結局のところ、ユーザーにとっては、タイムリーなニュースが見られないことよりも、ニュースをまったく読めないことの方がはるかに重要です。

誰もが自由に組み合わせることができ、最終的には 3 つの条件を同時に満たすことはできないことが証明されます。実際、ほとんどの場合、一貫性と可用性の間でトレードオフを行っているだけです。

一貫性 = コンセンサス?

一貫性は業界では過剰に使用されており、一貫性について議論するときに、相手が話している一貫性が自分の一貫性と同じであるかどうかを実際に確認することができないほどです。

一貫性：一貫性、コンセンサス：コラボレーション、これら 2 つの概念は非常に混同されやすいものです。

分散システムでよく話題になる一貫性とは、線形一貫性、因果一貫性、結果一貫性など、同じデータの複数のコピーのデータ一貫性を指します。これらはすべて、コピー問題における一貫性を説明するために使用されます。コンセンサスは異なります。簡単に言えば、コンセンサスの問題は、複数のノードが特定のアルゴリズムを通じて同じ状態に到達するプロセスです。私の意見では、一貫性は結果を重視し、コンセンサスはプロセスを重視します。

[[314891]]

コンセンサス？ステートマシン？

[[314892]]

ケン・トンプソン

コンセンサスには、より洗練された名前があります。

ステートマシンの複製に基づくコンセンサスアルゴリズム

では、ステートマシンとは何でしょうか?

ステートマシンは有限状態オートマトン（Finite State Automaton）の略で、現実のものの動作ルールを抽象化した数学モデルです。

下の写真を見てください。ドアには開いている状態と閉じている状態の 2 つの状態があります。したがって、私の意見では、状態は静的なシーンであり、遷移は動的な変化をもたらします。

同様に、ノードの現在のデータが X で、現在 add+1 の操作ログがある場合、現在の状態は X+1 です。状態 (X) があり、変更 (操作ログ) があり、これがステート マシンです。

分散コンセンサスとは、簡単に言えば、1 つ以上のノードが状態を提案した後、システム内のすべてのノードが状態について合意に達するプロセス全体です。

合意はプロセスであり、全会一致は結果です。

コンセンサスモデル

マスタースレーブ同期:

MySQL などの業界で一般的なデータベースのマスター スレーブ レプリケーションは、次の 3 つの段階に分かれていることは周知の事実です。

• マスターが書き込み要求を受け入れる
• マスターはログをスレーブにコピーします
• マスターはすべてのスレーブが戻るまで待機します。

マスター スレーブ同期モデルには致命的な問題があることがわかります。1 つのノードに障害が発生すると、マスターがブロックされ、クラスター全体が使用できなくなります。一貫性は保証されますが、可用性は大幅に低下します。

過半数：

各書き込みは N/2 ノードより大きく、各読み取りも N/2 ノードから読み取られることが保証されます。多数決モデルは、パフォーマンスがわずかに低下することを除けば、複数のノードの一貫性の問題を完璧に解決するように見えます。ただし、次の図に示すように、同時実行状況では必ずしもそうとは限りません。

並行環境では、各ノードの操作ログの書き込み順序が一貫していることが保証されないため、最終的な一貫性は保証されません。図に示すように、それらはすべて3つのノードに向けられています。

inc5 と set0 は 2 つの操作ですが、順序が異なるため、最終状態はそれぞれ 0 と 5 になります。そのため、各操作ログに番号を付ける仕組みを導入する必要があります。この番号は、各ノードが間違いを起こさないように、小さい番号から大きい番号へと生成されます。 (ネットワークのサブパケット化と再編成について考えたことはありますか?) さて、ここで再び重要な質問が出てきます。この番号付けをどのように調整するかということです。これは、鶏が先か卵が先かという質問のようです。

パクソス

Paxos モデルは、分散コンセンサス問題のより一般的な形式を探求しようとします。

Latex の発明者である Lesile Lamport が Paxos アルゴリズムを提案しました。彼はパクソスという架空のギリシャの都市国家を創設した。この島は議会制民主主義の政治モデルに従って法律を制定していたが、誰もこの問題に時間とエネルギーを費やそうとはしなかった。したがって、国会議員、議長、メモを配るウェイターのいずれも、必要なときにそこにいることを約束することはできず、また、決議を承認したりメッセージを届けたりする時間を約束することもできません。 Paxos は理解するのが難しすぎたため、Lamport は同僚が彼のユーモアのセンスを理解できないと感じ、後にアルゴリズムの説明の簡易版である「Paxos Made Simple」を再出版しました。

コンセンサスアルゴリズムは全体として2つの段階に分かれています。図に示すように、最初の段階は提案、2番目の段階は決定です。

分散システムでフォールト トレランスを実現するには、コンセンサス モデルが必要です。ノードがコンセンサスに達するには、ノード間のアルゴリズムだけでなく、クライアントの動作も必要です。たとえば、レプリカ システムがマルチ Paxos を使用してすべてのレプリカ サーバー上のログ シーケンス番号を同期している場合でも、クライアントがリーダー以外のノードからデータを書き込むことが許可されている場合、レプリカ システム全体の整合性は依然として強く保たれません。

さて、ハイライトは、Paxos の詳細な紹介です。

役割の紹介:

クライアント: システムの外部ロール、リクエストのイニシエーター。人々と同じように。

プロポーザー: クライアントの要求を受け入れ、クラスターに提案します。そして紛争が起こった場合には紛争調停の役割を果たします。彼は国会議員のように国民を代表して法案を提案します。

承認者: 提案の投票者および受信者。提案は、定足数 (Quorum、つまり過半数) が満たされた場合にのみ最終的に承認されます。例えば議会など。

学習者: 提案のアクセプタ、バックアップ、バックアップは、クラスターの一貫性に影響を与えません。リコーダーみたいに。

手順と段階:

1. フェーズ1a: 準備

提案者は、以前に提案した提案番号よりも大きい番号 N の提案を提案し、受け入れ者の定足数 (過半数) にその提案を受け入れるように要求します。

2. フェーズ1b: 約束

N が、このアクセプターによって以前に受け入れられた提案番号より大きい場合は、それを受け入れます。それ以外の場合は、それを拒否します。

3. フェーズ2a: 承認

過半数に達した場合、提案者は提案番号と前のステップの内容を含む承認リクエストを発行します。

4.フェーズ2b: 承認

このアクセプターは、この期間中に N より大きい提案を受信しなかった場合は提案の内容を受け入れ、そうでない場合は無視します。

上で述べたように、同期番号付けは非常に重要な問題です。緑色のボックスは、実際に同期番号付けのプロセスを示しています。この番号を通じて、各操作ログの順序を知ることができます。簡単に言うと、最初の段階は数値を取得することであり、2 番目の段階はログを書き込むことです。 Paxos は、時間とパフォーマンスを犠牲にして、2 ラウンドのインタラクションを通じて一貫性を実現していることがわかります。

ここで、いくつかのノードがダウンしているシナリオを考えてみましょう。

受け入れ者の大多数が合意に達したため、最初のフェーズでは目標を達成することができ、最終的にすべてが成功しました。

プロポーザーがダウンしているシナリオを考えてみましょう。

それは問題ではありません。最初の提案者は失敗しましたが、次の提案者はより大きな提案番号を使用したため、次の提案者は最終的に成功し、可用性と一貫性は依然として保証されました。

潜在的な問題: ライブロック

Paxos はライブロック問題に悩まされています。図に示すように、最初の提案者が第 1 段階でリクエストを送信すると、第 2 段階で後続のリクエストを送信する前に、2 番目の提案者も第 1 段階でリクエストを送信します。これが際限なく続き、アクセプターが常にシーケンス番号を決定するプロセスに留まると、誰も成功しません。この問題は実際には非常に簡単に解決できます。シーケンス番号が新しい提案者によって更新されたことが判明した場合、複数の提案者間の競合の問題を回避するために、ランダムな待機タイムアウトが導入されます。

マルチパクソス

Paxos の問題: 実装が困難、効率が低い (RPC が 2 ラウンド)、ライブロック。

そこで、Multi Paxos が導入されました。Multi Paxos では、唯一の提案者であるリーダーが導入され、すべてのリクエストはこのリーダーを経由する必要があります。

提案番号を管理するノードは 1 つだけなので、提案番号に関する最初の議論は省略されます。

次に、文字をさらに単純化します。

サーバーの左側にあるものが Proposer であり、他の 2 つとそれ自体が Acceptor として機能します。これにより、実際のシステムに似たものになります。 Raft プロトコルと ZAB プロトコルは、実際には基本的にこれと同じです。 2 つのプロトコルの唯一の違いは、ハートビートの方向が異なることです。

ラフトとZAB

Raft および ZAB プロトコルは、Multi Paxos を 3 つのサブ問題に分割します。

• リーダー選挙
• ログレプリケーション
• 安全性

リーダー選出プロセス中に、役割も再定義されます。

• リーダー
• フォロワー
• 候補者

このアニメーション化された Web サイトでは、リーダー選出とログ複製のプロセスを鮮明に示します。ここでは詳細には触れません。

さらに、公式ラフトウェブサイトでは、模擬選挙プロセスを独自に運営することができます。

要約する

今日はCAP、Raft、ZABについて、さまざまな用語を交えてお話ししました。モデルがどのように変化しても、私たちの目標は常に1つだけです。

フォールトトレランスの分散アーキテクチャの下で、システム全体の可用性と一貫性を最大限に確保する方法。最も理想的なモデルはもちろん Paxos ですが、理論と実装の間にはまだギャップがあるため、Raft と ZAB が生まれました。リーダーは 1 人だけですが、リーダーが失敗しても再選できるようにします。このようにして、集中化と分散化の間で妥協点が生まれます。