分散ストレージシステムにおける Raft と Paxos のアプリケーションの違い

この記事の目的:

私は現在、Codeship の Galera から MariaDB Galera Cluster/Percona XtrDB Cluster のマルチマスター クラスター テクノロジー、そして今日の GR に至るまで、Group Replication (略して GR) のコードを読んでいます。分散ストレージ システム、特に分散 RDBMS は、将来のトレンドとなることは間違いありません。最も基本的かつ困難な問題の 1 つは一貫性の問題であり、これはすでに今日の分散システムが直面しなければならない問題です。アトミックブロードキャストからViewstamped Replication/Paxos/Raftまで...分散一貫性に関する理論論文や工学技術を多数読み、良いと思った資料を翻訳してまとめました。

[[232150]]

基本的な概念:

ログ: redolog や binlog などのストレージシステムの操作記録を表します。

メッセージ: 分散システムにおけるサーバー間のやり取りの単位

任期: クリントン大統領、ブッシュ・ジュニア大統領などの異なる任期など、任期の数。

インデックス: 用語内の通し番号。通常は連続して増加する。

スロット: ログシーケンス内の各ログエントリのグローバル位置

実際、一貫性アルゴリズムの核となる考え方は非常にシンプルで、次のようにシンプルに（現実的に）理解することができます。

1. グループの人々 (クラスター内のサーバー) が問題について議論していますが、統一された結論に達することができません。

2. 長い時間が経って、皆が疲れてきて、尊敬できるリーダー（リーダー）が必要だと気づき、リーダーのアドバイスに耳を傾けました。

3. その後、各陣営は国民を納得させることができる候補者（リーダー候補）を指名します。

4. 候補者に投票を呼び掛ける時間（タイムアウト）を 5 分与え、その後他の人に投票してもらいます（選挙）。選挙が公正かつ公平であると仮定しましょう。

5. 最後に、リーダーが選出されます。一部の人々がまだ不満を抱いているにもかかわらず、少数派は多数派（多数派派閥）に従う。

6. 今後はリーダーが提案を行い、大多数の同意が得られたら提案を掲載します。一度発表した結論は変更できない（恥ずかしいことはできない）誰も異論を唱えない（少数の人が異論を唱えても我慢するしかない）

7. リーダーが長期間在職している場合、権力と金銭の交換が行われるのは避けられません。現時点では、彼は反汚職運動に巻き込まれている可能性がある（リーダーは不在）。しかし、人生は続いていかなければならず、新しいリーダーを選出する必要があり、それは過去の歴史を繰り返すことになる...;もちろん、権力と金銭の取引により職務を解かれることのない指導者もいる。調和するものもあれば、倒されるものもあり…とにかく解雇される。ワールドカップに出られないから、首脳陣は大きなプレッシャーにさらされているから、外国人コーチに交代しても大丈夫！

8. どうしてそんなことが可能なのでしょうか?以前の指導者が残した混乱をどうしたらいいのでしょうか?ラフトという名の若者はこう言った。「まず自分の尻をきれいにしろ。さもないと、この混乱を引き継げない。チームを絶対的に支配したいんだ！」そこでラフトは正式に就任する前に、一団の人たちを集めて古い帳簿を整理し、それを公開し、その後就任して自分の時代を始めたのです。

9. 公務員は儲かる仕事です。ラフトのような若者は傲慢に見えても、誰も彼に注意を払わないことがあります...そのため、待ちきれない古参の人たちが最初にリーダーの地位に就きます。前任者が残した汚点については、就任後に大騒ぎするだけだ！はい、この古いドライバーは Paxos です...

10. パクソス兄弟は業界では評判が良くないようです。悲しいことに、昔から人々の心をつなぎとめるために習慣が使われてきました。これらの古いドライバーは多くの魔法の武器を持っており、数分でどのように行動すべきかを教えることができます。そのため、多くの学派がパクソスを研究しています。

1. 背景

一貫性は、分散型の強力な一貫性のあるストレージ システムなどのフォールト トレラント サービスを提供する上で重要な要素です。非ブロッキング アトミック ブロードキャスト、Paxos、Raft は、3 つの一般的な一貫性アルゴリズムです。 Paxos は学術界で広く研究されており、Raft はエンジニアの間で非常に人気があります。

学者たちは Paxos を好んでいますが、Raft も非常に人気があります。エンジニアはいくつかの論文を読むことで Raft アルゴリズムを理解し、Raft アルゴリズムを実装していくつかの実用的なエンジニアリング問題を解決することができます。アルゴリズムの実装プロセスでは、通信インタラクションの数、メッセージの数、リソース占有率などを考慮し、これらの要素を総合的に評価しながら、良好なシステムパフォーマンスを確保する必要があります。同時に、アルゴリズムの実装では、アルゴリズム理論とエンジニアリングの実践の間で頻繁に発生するいくつかの問題も考慮する必要があります。

これらの障害を克服するために、Diego Ongaro 氏と John Ousterhout 氏は、Paxos よりも理解しやすく、エンジニアリングが優れているように設計された Raft と呼ばれる新しいコンセンサス アルゴリズムを公開しました。 Raft アルゴリズムは複雑な分散システムに新鮮な感覚をもたらしますが、そのアイデアのほとんどは本質的に Paxos アルゴリズムと同じです。たとえば、参加者が問題について合意に達することができるように、独自のリーダーが選出されます。

この記事では、Paxos と Raft の類似点と相違点を簡単に紹介します。まず、一貫性アルゴリズムとは何かについて説明します。次に、一貫性アルゴリズムをインスタンス化してデータ複製ソリューションを構築する方法を紹介します。最後に、リーダーの選出方法と一貫性アルゴリズムのセキュリティとアクティビティについて紹介します。

この記事の目的は、Paxos と Raft について詳細に議論することではなく (Paxos アルゴリズムの一部はまだ完全には理解されていません)、両方について簡単に紹介することだけであることに注意してください。これら 2 つのアルゴリズムの詳細について詳しく知りたい場合は、参考文献 1/2/3/4 をお読みください。

2. 分散一貫性

2.1 分散システムの特徴

安全性と活性は分散システムの 2 つの基本的な特性です。安全性と活性はシステムの正確性にとって必要かつ十分な条件だからです。安全性とは、導出プロセスが正しいことを意味します。たとえ予期せぬ事態が起こったとしても、そのような事故は決して起こらず、最終的には正しい結果が得られます。アクティビティとは、結果が最終的に得られ、何らかの行き詰まりによりシステムが結果を推論し続けることができなくなることがないことを意味します（限られた時間内に結果が得られます）。定義から、次のように理解できます。

安全

• 提案された値のみ選択できます（提案されていない値は選択されません）
• 選択される値は1つだけです
• 値が実際に選択されるまで、その値は他のサーバーによって学習されません。

アクティブ

• 最終的には提案された値のいくつかを選択する必要があります
• 選択された値は、最終的には他のサーバーによって学習されます。

2.2 解決に至る

コンセンサス アルゴリズムでは、複数のサーバー間で特定の問題について合意に達することが目標です。ライブネスは、複数のサーバーが最終的に特定の問題について合意に達し、デッドロック状態にならないという事実に反映されます。安全性は、2 つのサーバーの解像度が異なることはないという事実に反映されています。

残念ながら、サーバーのパフォーマンスが他のサーバーよりも低くなったり、クラッシュしたり、コンセンサス アルゴリズム ロジックの処理が停止したりする場合があります。メッセージが遅延したり、順序が乱れたり、失われたりする可能性があります。これらすべての要因により、コンセンサス アルゴリズムの実装が非常に複雑になり、安定した時間内に正しい解決を保証することが困難になります。分散システムがいつ「安定した」状態に到達するかを正確に知ることはできませんが、最終的には「安定した」状態に到達することはわかっています。

解決には 2 つのコミュニケーションが含まれます。

リーダー –(1)–> サーバー –(2)–> リーダー:

リーダーは、すべての参加者に合意を得るための提案を送信し、提案を受信した各参加者は、提案を受け入れたことを示す ACK をリーダーに返信します。リーダーが多数派から ACK を受け取った後、全員が提案について合意に達します。

上記の分析では、2 つのメッセージを無視していることに注目してください。1 つ目は、イニシエーターからリーダーへのメッセージ (合意に達する意図を送信) であり、2 つ目は、提案について合意に達したことを通知するためにリーダーからすべての参加者に送信されるメッセージです。 2 番目のメッセージは、次の 2 つの方法で回避できます。

サーバーは受け入れられたメッセージを他のすべてのサーバーに送信できます。

リーダーは次回、合意したメッセージ番号で別の提案を送信できます。

2.3 ログレプリケーション

レプリケーションを実現するために、通常、一貫性アルゴリズムの複数のインスタンスが開始され、各インスタンスはレプリケーション ログ内のログ エントリに対応し、レプリケーション ログは通常、ディスクに永続化されます。リーダーは、コンセンサス アルゴリズムの複数のインスタンスを並行して実行して、さまざまなログ エントリでコンセンサスに達することができるため、パフォーマンスが向上します。ただし、並列処理の度合いはハードウェア、ネットワーク、およびアプリケーション自体によって異なります。

各リーダーは自身の任期に対してのみ責任を負います。リーダーが変わると、対応する用語番号も増加します。

2.4 リーダー選出

Paxos アルゴリズムまたは Raft アルゴリズムに関係なく、最終的にはリーダーが生成されます。他のすべての通常のサーバーは、一貫性の達成を調整するためにリーダーを信頼します。任期中、リーダーは 1 人だけです。現在の任期のリーダーが利用できない場合は、新しいリーダーの選出がトリガーされ、新しいリーダーの任期番号は現在の任期番号 (Term) よりも大きくなります。

Raft では、サーバー (リーダー候補) は、正式にリーダーになる前に大多数のサーバーから応答を得ることを期待して、他のサーバーに「選挙要求」を送信します。多数派サーバーから応答が受信されない場合、または別のサーバーがリーダーになったことがサーバーに通知された場合、現在のサーバーはタイムアウト後に新しい選出プロセスを開始します。任期中、どのサーバーも 1 人のリーダー候補にのみ投票できます。

Paxos では、リーダーの生成方法が明確に定義されていません。簡単にするために、通常はサーバー ID (整数) などに基づくレベルベースの優先順位が使用されます。したがって、すべての通常サーバーの中で、最高または最低のランクを持つサーバーが常にリーダーになります。これはシンプルで直感的な解決策ですが、2 つの項間の間隔を分割する必要もあります。

新しい用語 = 古い用語 + N (クラスター内のサーバーの数)

Raft は選挙プロセスにいくつかの制限を課します。つまり、最も新しいサーバーだけがリーダーとして選出されます。基本的に、このメカニズムにより、リーダーは前の期間に合意されたすべてのログを保持し、リーダーはグローバルに合意されたログから保持していないログを学習する必要がなくなります。したがって、サーバーがリーダーになると、他のサーバーに一貫性の提案を開始するなどの外部サービスをすぐに提供できるようになります。

Raft とは異なり、Paxos では任意のサーバーをリーダーとして選出できます。したがって、Paxos では、サーバーがリーダーになると、外部にサービスを提供する前に、まず他のサーバーから以前の任期中に合意されたログを学習する必要があります。この柔軟性がさらなる複雑さをもたらすことは明らかです。

上の図に示すように、Raft では Server1 と Server2 のみがリーダーとして選出されます。 Paxos では、すべてのサーバーをリーダーとして選出できます。

2.5 セキュリティ

分散システムの非同期的な性質により、サーバーは時々障害を起こし、いつでも新しい選挙ラウンドをトリガーする可能性があります。これは、クラスター全体のサーバーが、ある瞬間に一時的に異なる期間になる可能性があるが、最終的には同じ期間に入ることを意味します。

いつでも、サーバーが古い用語からメッセージを受信した場合、送信者はリーダーであるか、リーダーになろうとしている古い用語のサーバーであることを意味します。この場合、受信側サーバーはメッセージを拒否し、送信側サーバーに通知する必要があります。

サーバーが現在の期間よりも大きい期間番号を受信した場合、新しいリーダーが生成されたことを意味します。受信者は新しいリーダーの「提案」の受信を開始する必要があります。

どちらのアルゴリズムも、古いリーダーがすでに合意に達している決議を上書きすることは明らかに安全ではないため、厳密に回避する必要があることに注意する必要があります。これは Raft と Paxos の主な違いの 1 つです。この時点で、Raft アルゴリズムの相対的な単純さと直接性がわかります。

前述したように、Raft はリーダー選出にいくつかの制限を課します。最新のコンセンサス解決を持つサーバーのみがリーダーとして選出されます。

Raft は、異なるサーバーの最後のログ レコードのインデックスと用語を比較して、最新の解決があるかどうかを判断します。 2 つのログの Term が異なる場合は、Term が大きい方が勝ちます。 2 つのログに同じ用語がある場合、インデックスが大きい方が優先されます。

リーダーは、複製されたログが最終的に収集されることを確認するだけで済みます。これは、次の制限を追加することで実現されます。特定のスロットでは、インデックス「n-1」の提案について合意に達するまで、インデックス「n」の提案を受け入れません。

リーダーは、現在のログに前のログのターム番号を含め、受信サーバーは前のログと一致するログ要求のみを受信します (同じターム内のインデックス番号は連続しています)。それ以外の場合は、リーダーに、まだ存在しない独自のログを送信するように要求し、これを「n-2」、「n-3」などと続けます。

Paxos では、どのサーバーもリーダーになる可能性があるため、すでに到達した解決が上書きされるのを防ぐタスクは比較的複雑です。新しいリーダーは、外部にサービスを提供する前に、まず他のサーバーがどの解決をすでに処理したかを確認する必要があります。

Paxos アルゴリズムでは、新しいリーダーが選出されるときに、実行する必要がある「準備」フェーズがあります。 「準備」メッセージには、新しい用語番号 Term とスロット番号「n」が含まれます。ここで、「n」は以前に合意された解決番号を表します。他のサーバーは、スロット番号「n」より大きいメッセージで応答します。これは、新しいリーダーがこれらのスロットに提案できる値を制限するために使用されます。

2.6 アクティビティ

クラスター内のサーバーの大多数が存続する限り、クラスターは通常のサービスを提供することが保証されます（選挙と合意形成のプロセスは正常に進行します）[9]。前述のように、Raft と Paxos には実際に提案を担当するリーダーが存在するため、デッドロックは発生しません。

3. 結論

上記の分析を通じて、Raft と Paxos の類似点と相違点がわかります。主な違いは、リーダーの選出と安全保障の保証にあります。 Raft では、最新のデータを持つサーバーのみがリーダーになることができますが、Paxos にはこの制限はありません。これが Paxos の柔軟性ですが、もちろんこの柔軟性によってさらなる複雑さも生じます。

Raft でも Paxos でも、すべてのリクエストが Leader を通過するため、Leader がシステムのボトルネックになりやすいことに注意してください。リーダーを持つクラスターでは、メッセージ処理の時間計算量は O(N) ですが、リーダーを持たないクラスターでは、メッセージ処理の時間計算量は O(1) です。

Mencius など、複数のリーダーをサポートする Paxos ベースのプロトコルはすでにいくつか存在します。 Egalitarian Paxos や Generalized Paxos など、Paxos に基づいた、順序付けられた競合のない並列プロトコルもいくつかあります。 Raft プロトコルに基づいたこのような最適化が実現されることを期待しています。

参考文献:

01 – シンプルなPaxos

02 – 理解しやすいコンセンサスアルゴリズムを求めて

03 – パクソスの解体

04 – パクソス島へのもう一つの訪問

05 – 部分的な同期がある場合の合意

06 – クラッシュリカバリモデルにおける障害検出とコンセンサス

07 – バッチ処理とパイプライン処理による高スループットのための Paxos のチューニング

08 – 信頼性とセキュリティに優れた分散プログラミング入門

09 – 非同期コンセンサスの下限

10 – Mencius: WAN 向けの効率的な複製ステートマシンの構築

11 – 平等な議会では合意形成が進む

12 – 一般化されたコンセンサスとパクソス