Raft アルゴリズムの原理と CMQ への応用 (パート 1)

[[202009]]

導入

Raft アルゴリズムは分散コンセンサス アルゴリズムです。 Paxos と比較すると、理解しやすく、エンジニアリングも簡単です。このアルゴリズムを完全実装し、自社開発の高信頼性メッセージミドルウェア CMQ に適用したほか、汎用 Raft アルゴリズムライブラリも開発しました。この記事では主に、Raft アルゴリズムの原理、エンジニアリング中に遭遇する問題とその解決策、およびパフォーマンスを向上させるための対策について紹介します。

1. 背景

分散システムとは、ネットワークを通じて連携して動作する独立したコンピュータのグループであり、クライアントからは単一のマシンが動作しているように見えます。インターネット時代のデータの爆発的な増加により、従来のスタンドアロン システムはパフォーマンスと可用性の面で要件を満たすことができなくなりました。分散システムは、強力なスケーラビリティ、高可用性、低コスト、高効率などの利点があり、広く使用されています。

ただし、スタンドアロン システムと比較すると、分散システムの実装ははるかに複雑です。 CAP 理論は分散システムの理論的な基礎であり、次の 3 つの要素で提案されています。

一貫性: どのクライアントも他のクライアントからの最新の更新を読み取ることができます。

可用性: システムは常に利用可能です。

パーティション耐性: 1 台のマシンに障害が発生した場合やネットワークがパーティション分割された場合でも、システムは強力な一貫性と可用性を保証できます。

分散システムは、これらの要素のうち最大 2 つしか満たすことができません。分散システムの場合、P は明らかに不可欠なので、AP と CP の間でバランスを取るしかありません。 AP システムでは強力な一貫性が犠牲になりますが、これは一部のビジネス シナリオ (財務など) では受け入れられません。CP システムはそのような要件を満たすことができます。重要な問題は、可用性がどの程度犠牲になるかです。従来のマスター/スレーブの強力な同期モードでは一貫性を確保できますが、マシンに障害が発生したり、ネットワークが分割されたりすると、システムは使用できなくなります。 Paxos や Raft などのコンセンサス アルゴリズムの導入により、この欠点は補われました。 CP を確保するという前提のもと、ほとんどのノードが正常に相互接続できればよく、システムを常に利用可能な状態に維持でき、可用性が大幅に向上します。 Paxos はより理論的なものであり、開発者が多くの詳細を自分で処理する必要があるため、多くのバリエーションがあります。それに比べて、raft は理解しやすく、エンジニアリングも容易であり、提案されて以来広く普及しています。

私たちが関心を持っているメッセージ ミドルウェアの分野では、金融決済サービスではデータの強い一貫性と高い信頼性が厳しく求められることがよくあります。強い一貫性: A が B に 100 元を送金し、システムは送金が成功したことを返します。その後、B が残高を確認すると、100 元が受け取られたことが示されるはずです。受け取られていないか、一定期間後に受け取られたことが判明した場合、そのようなシステムは強い一貫性がありません。高い信頼性: リクエストが顧客に正常に戻った場合、リクエスト結果が失われないようにする必要があります。

主流のメッセージ ミドルウェアを調査した結果、このシナリオに対処する場合、どのミドルウェアにも特定の欠点があることがわかりました。

RabbitMQ: 一貫性を確保するために、リクエストをすべてのノードで 2 回処理する必要があり、パフォーマンスは高くありません。

Kafka: Kafka は主にログやビッグデータなどの分野で使用されています。少量のデータ損失は許容できますが、高いデータ信頼性が求められるシステムには適していません。

RocketMQ: 一貫性アルゴリズムは使用されません。非同期モードで構成されている場合、データが失われる可能性があります。同期モードでは、ノード障害またはネットワークパーティションが可用性に影響します。

SQS: 最終的な一貫性のみを提供し、強力な一貫性は保証しません。

上記の分析を踏まえて、Raft をベースにした強力な一貫性と信頼性の高いメッセージ ミドルウェアである CMQ を設計、開発しました。次に、ラフト アルゴリズムの原理の詳細、メッセージの信頼性と損失の防止を保証するために CMQ でラフト アルゴリズムを適用する方法、実装プロセス中に行ったパフォーマンスの最適化について詳しく紹介します。

2. Raftアルゴリズムの基本原理

2.1 概要

ラフト アルゴリズムは、Diego Ongaro 博士が USENIX 2014 の論文「理解可能なコンセンサス アルゴリズムの探求」で初めて提案しました。このアルゴリズムは、主に選出とログ同期の 2 つの部分で構成されています。

***フェーズ選択:

• クラスターから適切なノードをリーダーとして選択します。

第 2 段階のログ同期:

• 選出されたリーダーはクライアントのリクエストを受け取り、それをラフト ログに変換します。
• リーダーはログを他のノードと同期します。ほとんどのノードが正常に書き込みを終えると、ログはコミットされます。コミットされると、ログは改ざんされなくなります。
• リーダーが失敗すると、*** フェーズに切り替わり、再選出されます。

以下は、Raft アルゴリズム全体で使用される重要な用語です。

用語: ノードの現在のサイクルは、文明の時代とみなすことができます。

votedFor: 現在の用語の投票情報。各ノードは特定の用語に対して 1 回だけ投票できます。

エントリ: インデックス、用語、および user_data を含む、raft ログの基本単位。インデックスはログ ファイル内で順番に割り当てられ、term はエントリを作成するリーダー ターム、user_data はビジネス データです。

状態: ノードの役割 (リーダー、候補、フォロワーのいずれか)。

CommitIndex: 送信されたログのインデックス。

ステート マシン: ステート マシン。 Raft と対話するビジネス モジュール。

ApplyIndex: アクションが適用されたログのインデックス。

ElectionTime: 選挙タイムアウト。

ノードは RPC を介して通信し、選出とログの同期を完了します。送信者は RPC を送信するときに独自の用語を持ちます。受信側は RPC を処理するときに次の 2 つの一般的なルールに従います。

• RPC 内の RTerm が現在の Term より大きい場合は、自身の Term = RTerm、votedFor = null に更新し、Follower になります。
• RPC 内の RTerm は現在の Term よりも小さいため、要求は拒否され、その独自の Term が応答パケットで伝送されます。

2.2 選挙

Raft アルゴリズムは、強力なリーダー モードに属します。リーダーのみがクライアント要求を処理できます。リーダーはハートビートを通じてその位置を維持します。リーダーに障害が発生したり、ネットワークに異常が発生しない限り、リーダーは変更されません。選出フェーズの目的は、クラスターから適切なリーダー ノードを選択することです。

選挙プロセス:

1. ノードの初期状態はフォロワーです。フォロワーは受動的にリクエストを受信するだけです。ElectionTime の期限が切れたときにリーダーからの AppendEntry RPC が受信されない場合、フォロワーは現在リーダーがいないと判断し、候補者になります。

2. 候補者は、クラスター内で RequestVote RPC をブロードキャストし、リーダーに立候補しようとします。メッセージを受信した後、他のノードはまず選出に同意するかどうかを決定し、結果を候補者に返します。候補が大多数のノードから同意応答を受け取った場合、その候補がリーダーになります。

3. リーダーはクライアント要求を受信し、それをエントリに変換してログ ファイルに追加し、AppendEntry RPC を通じてログ エントリを他のノードと同期します。

次の例では、選挙プロセスを詳しく説明します。

1) 初期状態: クラスターは 3 つのノードで構成され、すべてのノードは最初は Follower 状態にあります。図の四角はノードのラフト ログを表します。

2) 選挙を開始する: ノード 1 の選挙タイマーが最初に期限切れになり、候補になります。 期間は自動的に増加し、voteFor は 1 (自分自身に投票) に更新されます。 次に、RequestVote RPC がクラスター内の他のノードにブロードキャストされます。 RequestVote RPC はノードのログ情報を伝達します。

3) 選挙に応答: RequestVote RPC を受信した後、ノード 2 と 3 は、RPC ルールに従って term と voteFor (term:6、voteFor:null) を更新し、この選挙に同意するかどうかを決定します。他の人に投票した場合は、この選挙を拒否します (ここで、voteFor: null は投票しません)。RequestVote RPC のログが完全でない場合は、拒否します。それ以外の場合は、同意します (ここで、ノード 1 のログは、2 と 3 のログよりも完全です)。*** voteReply RPC を通じて投票結果に応答します。

4) 選挙完了: ノード 2 と 3 の両方がこの選挙に同意するため、いずれかのノードから voteReply RPC を受信すると、ノード 1 がリーダーになります (多数決で十分です)。

選挙タイムアウト値:

選挙中、2 つのノードの選挙タイマーが同時に期限切れになり、選挙が開始され、それぞれが投票の半分を受け取ることになり、選挙が失敗します。選挙が失敗すると、システムにリーダーがいなくなり、サービスを提供できなくなります。選挙タイマーが設定されている場合は、両方が再び同時に期限切れになる可能性があります。競合の可能性を減らすために、選出タイムアウト値にはランダムな値を採用します。さらに、選出タイムアウト値が大きすぎると、リーダーの障害後に次の選出が行われるまでに長い時間がかかる可能性があります。選出タイムアウト値は通常、300 ミリ秒から 600 ミリ秒の間のランダムな値です。

2.3 ログの同期

選出フェーズが完了すると、リーダー ノードはクライアント要求の受信を開始し、要求をエントリにカプセル化して raft ログ ファイルの末尾に追加し、エントリを他のフォロワー ノードと同期します。ほとんどのノードが正常に書き込みを完了すると、エントリはコミット済みとしてマークされます。ラフト アルゴリズムにより、コミットされたエントリが再度変更されることがなくなります。

ログ同期固有のプロセス:

1) リーダーは各ノードの NextIndex と MatchIndex を管理します。NextIndex はノードに送信されるエントリ インデックスを示し、MatchIndex はノードによって一致したエントリ インデックスを示します。同時に、各ノードは現在コミットされているエントリ インデックスを示す CommitIndex を管理します。リーダーになった後、すべてのノードの NextIndex を最後のログのインデックス + 1 に設定し、すべての MatchIndex を 0 に設定し、自身の CommitIndex を 0 に設定します。

2) リーダー ノードは、user_data を継続的にエントリに変換し、ログ ファイルの末尾に追加します。エントリには、index、term、user_data が含まれます。index はログ ファイル内で 1 から順番に割り当てられ、term はリーダーの現在の term です。

3) リーダーは、AppendEntry RPC を通じてエントリをフォロワーに同期します。 エントリを受信した後、フォロワーはエントリの前のログが一致しているかどうかを確認します。一致する場合、エントリが直接書き込まれ、成功が返されます。一致しない場合は、一致しないログが削除され、失敗が返されます。検証は、AppendEntry RPC に書き込まれるエントリの以前のエントリ情報を保持することによって実行されます。

4) フォロワーが成功を返すと、対応するノードの NextIndex と MatchIndex を更新し、後続のエントリの送信を続けます。 MatchIndex が更新された後、ほとんどのノードの MatchIndex が CommitIndex より大きい場合は、CommitIndex が更新されます。 Follower が失敗を返すと、Follower が成功を返すまでロールバック NextIndex の送信が継続されます。

5) リーダーは、各 AppendEntry RPC で現在の LeaderCommitIndex を保持します。フォロワーが正常に書き込みを行うと、フォロワー自身の CommitIndex が Min(LastLogIndex、LeaderCommitIndex) に更新されます。

同期プロセス中は、クラッシュが発生した場合にデータが失われないように、各ログ書き込みをディスクにフラッシュする必要があります。

次の例では、ログ同期の基本的なプロセスを紹介します。

1) 初期状態では、すべてのノードの Term=2、CommitIndex=2 です。次に、リーダーは y←9 の要求を受信し、それをログの末尾の Entry に書き込みます。エントリのインデックス =3、term =1 です。

2) リーダーは、AppendEntry RPC を通じて、エントリを 2 人のフォロワーに同期します。RPC には、前のエントリ情報 (インデックス = 2、用語 = 1) が含まれています。フォロワーは、それを受信した後、まず前のエントリが自分自身と一致するかどうかを確認し (ここでは一致が成功)、次にエントリを書き込んで、リーダーに成功を返します。

3) リーダーはフォロワーからの応答を受信した後、対応するノードの NextIndex と MatchIndex を更新します。この時点で、ほとんどのノードの MatchIndex は CommitIndex より大きいため、リーダーは CommitIndex=3 に更新します。

4) Leader は Follower に AppendEntry を送信し続けます。この時点では新しい Entry がないため、RPC 内のエントリ情報は空で、LeaderCommitIndex は 3 です。メッセージを受信した後、FollowerはCommitIndex=3 (Min(3,3))を更新します。

ログの競合:

ログ同期プロセス中に、ノード間でログの不整合が発生する可能性があります。たとえば、フォロワーがログを書き込む速度が遅すぎる場合や、リーダーが切り替わった結果、古いリーダーにコミットされていないダーティ データが残る場合などに、これが発生する可能性があります。 Raft アルゴリズムでは、ログの競合が発生した場合、リーダーのログが優先され、フォロワーは一致しない部分を削除します。

下の図に示すように、フォロワーノードとリーダーノードのログに矛盾があります。ノード(a)と(b)のログは不完全であり、ノード(c)、(d)、(e)、(f)のログは矛盾しています。リーダーは最初に、インデックス = 11 (最後のエントリ インデックス +1) から AppendEntry RPC を送信します。フォロワーはすべて不一致を返し、リーダーはそれを受信した後も後退し続けます。 (a) と (b) は、最初に一致するログが見つかった後、正常に同期します。(c)、(d)、(e)、(f) は、このプロセス中に不一致なログを徐々に削除し、最終的にすべてのノードのログがリーダーと一致するようになります。リーダー ノードになると、既存のログを変更または削除することはなくなり、新しいログのみが追加されます。

2.4 アルゴリズムの証明

Raft アルゴリズムの 2 つのコア プロパティは次のとおりです。

1) 提出されたログは再度変更されない。(信頼性)

2) すべてのノード上のデータは一貫しています。 （一貫性）

具体的な証明は次のとおりです。

1) リーダーの完全性: 特定のタームに送信されたログは、次の上位タームのリーダーに存在する必要があります。 （ログは失われません）

• 選出されたリーダーには、現在送信されているすべてのログが含まれている必要があります。送信されたログはほとんどのノードに存在し、選出に同意するための前提は、候補者のログが完全であるか更新されている必要があることです。コミットされたログを含まないノードは、大多数のノードから確実に投票を得ることができません (これらのノードはすべてコミットされたログを持っているため、ログが十分に完全であるという前提を満たしていません)。そのため、リーダーになることはできません。
• リーダー ノードは既存のログを変更または削除しません (アルゴリズムの制約)。

要約すると、選出もログ同期も送信されたログを破壊しないことが証明されています。

2) ステートマシンの安全性: すべてのノードのデータは最終的に一貫性を持ちます。

Leader Completeness に従って、送信されたログは再度変更されません。ビジネス ステート マシンは、エントリ内の user_data アプリケーションを 1 つずつ取り出し、最終的にすべてのノードのデータが整合されます。

2.5 クラスタ管理

Raft アルゴリズムは、エンジニアリングにおけるクラスター管理の問題を完全に考慮し、クラスターへのノードの動的な追加と障害のあるノードの削除をサポートします。ノードの追加と削除のプロセスについては、以下で詳しく説明します。

• ノードの追加

次の図に示すように、クラスターには ABC が含まれており、A がリーダーであり、現在ノード D が追加されています。

1) ダーティデータを避けるために、D ノード上のすべてのデータをクリアします。

2) リーダーは、AppendEntry RPC を通じて既存のログを D に同期し、D のデータが他のノードと同期されるようにします。

3) D のログがキャッチアップされた後、リーダー A は、クラスター情報に ABCD が含まれる構成エントリを作成します。

4) リーダーAはコンフィグエントリをBCDに同期します。フォロワーはそれを受信して​​適用します。その後、すべてのノードのクラスタ情報がABCDになり、追加が完了します。

注: ステップ 2 では、リーダーはエントリを生成するためのクライアント要求を引き続き受信しているため、D ログと A ログの差がそれほど大きくない限り、D が追いついたとみなされます。

• ノードの削除

次の図に示すように、クラスターには元々 ABCD が含まれており、A がリーダーでしたが、現在はノード D が削除されています。

1) リーダー A は、クラスタ情報 ABC を含む構成エントリを作成します。

2) A は AppendEntry RPC を介してログをノード BC に同期します。

3) ABC がログを適用すると、クラスター情報は ABC になります。A は D に AppendEntry を送信しなくなり、D はクラスターから削除されます。

4) この時点で、D のクラスター情報はまだ ABCD です。選出タイムアウトが経過すると、選出が開始されます。D の干渉を防ぐために、追加のメカニズムが導入されています。すべてのノードがリーダーの AppendEntry を正常に受信すると、他のノードから送信された選出要求を拒否します。

5) Dのデータを消去してログオフします。

2.5 ラフトアプリケーション

State Matchine を使用してビジネス モジュールを統一的に表現し、ApplyIndex を通じて適用されたログ インデックスを維持します。以下は、Raft とステート マシン間の相互作用のプロセスです。

1) クライアント要求がリーダーノードに送信されます。

2) リーダーノードの Raft モジュールはリクエストをエントリに変換し、フォロワーと同期します。

3) ほとんどのノードが正常に書き込みを行った後、Raft モジュールは CommitIndex を更新します。

4) 各ノードのステートマシンは、ApplyIndex+1 から CimmitIndex までのエントリを順に読み取り、user_data を抽出して適用し、完了後に ApplyIndex を更新します。

5) リーダー上のステートマシンは、操作が成功したことをクライアントに通知します。

6) このサイクルを繰り返します。

2.6 スナップショット管理

ノードが再起動されると、State Matchine の現在の ApplyIndex を知ることは不可能であるため (ログが適用されるたびに ApplyIndex が永続化されない限り、またそれがアトミック操作であることを保証する必要があり、コストがかかります)、State Matchine のデータをクリアし、ApplyIndex を 0 に設定して、ログを最初から適用する必要があります。これはコストがかかりすぎるため、定期的にスナップショットを作成することで解決できます。次の図に示すように:

1) エントリ 5 を適用した後、現在の状態マッチン データをエントリ情報とともにスナップショット ファイルに書き込みます。

2) ノードが再起動されると、まずスナップショット ファイルから状態マッチが復元されます。これは、エントリ 5 までのすべてのエントリを適用するのと同じですが、効率が大幅に向上します。

3) ApplyIndex を 5 に設定し、エントリ 6 からログを適用し続けます。データは再起動前のデータと一致しています。

スナップショットの利点:

• 再起動時間を短縮: スナップショット + ラフト ログを介して復元するため、最初のエントリから開始する必要はありません。
• スペースを節約: スナップショットが完了したら、スナップショット ポイントより前の Raft ログを削除できます。

2.7 異常なシナリオと解決策

Raft は強力なフォールト トレランスを備えています。ほとんどのノードが正常に接続されている限り、システムの一貫性と可用性が保証されます。次に、一般的な異常な状況とその影響および対処方法を示します。

異常な状況がシステムにほとんど影響を与えないことがわかります。リーダーの障害であっても、非常に短時間で回復できます。システムは、可用性をある程度犠牲にして、どのような状況でも常に強力な一貫性を維持します (ほとんどのノードが故障した場合、その確率は極めて低くなります)。ただし、リーダーが失敗した場合、新しいリーダーには、古いリーダーが送信していないログ、または送信したがクライアントにまだ通知していないログが含まれている可能性があります。アルゴリズムでは、リーダーになった後はログを削除できないと規定されているため、これらのログは新しいリーダーによって同期され、送信されます。ただし、接続情報が失われるため、クライアントはこの状況を知ることができません。再試行が開始されると、重複データが表示されるため、べき等性を保証する必要があります。また、ラフトのコアアルゴリズムはすべてリーダーを中心に構築されています。ネットワークが分割されると疑似リーダー問題が発生する可能性があり、この点についても特別な配慮が必要です。

ネットワークが分割されたときに疑似リーダーを生成するプロセスは次のとおりです。

上記の状況では、リーダーと 2 人のフォロワー間のネットワークは異常ですが、2 人のフォロワー間の通信は正常です。リーダーのハートビートを受信できないため、フォロワーの 1 人が選挙を開始してリーダーになります。元のリーダーは疑似リーダーになります。次に、このシナリオがシステムの一貫性に影響を与えるかどうかを分析します。

書き込み一貫性: 新しいリーダーに送信された書き込み要求は送信できますが、疑似リーダーに送信された要求は送信できません。 書き込み要求を正常に処理しているのは 1 つのリーダーだけなので、書き込み一貫性は影響を受けません。

読み取り一貫性: 読み取り要求が Raft によって同期されていない場合、クライアントの書き込み要求が新しいリーダーに送信され、正常に実行されると、読み取り要求が疑似リーダーに送信され、結果が得られるため、データの不整合が発生します。この問題には 2 つの解決策があります。

読み取り要求も Raft を通じて同期されるため、不整合の問題は発生しませんが、システム負荷が増加します。

リーダーノードは読み取り要求を受信した後、大多数のノードが再びハートビート RPC に応答するのを待機し、結果を返します。

ほとんどのノードがハートビートに応答するため、現時点では他のリーダーは存在しないことになります (ほとんどのノードは現在のリーダーとのリースを維持しており、新しいリーダーは過半数の投票を獲得する必要があります)。

2.8 まとめ

Raft アルゴリズムには、強力な一貫性、高い信頼性、高い可用性という利点があり、具体的には次のような利点があります。

強力な一貫性: すべてのノードのデータはリアルタイムで一貫していませんが、Raft アルゴリズムにより、リーダー ノードのデータが最も完全であることが保証されます。同時に、すべてのリクエストはリーダーによって処理されるため、クライアントの観点からは強力な一貫性が保たれます。

高い信頼性: Raft アルゴリズムにより、コミットされたログが変更されないことが保証されます。状態マッチングはコミットされたログのみに適用されるため、クライアントが成功したリクエストを受信した場合、データは変更されないことになります。コミットされたログはほとんどのノードに冗長的に保存されるため、ディスクの半分未満に障害が発生してもデータが失われることはありません。

高可用性: Raft アルゴリズムの原理から、選出とログ同期には大多数のノードが正常に接続されていることだけが必要であることがわかります。そのため、少数のノード障害やネットワーク異常はシステムの可用性に影響を与えません。リーダーが失敗した場合でも、選出タイムアウトが経過すると、クラスターは手動による介入なしに新しいリーダーを自動的に選出し、使用不可時間は非常に短くなります。ただし、リーダーに障害が発生すると、重複データの問題が発生し、ビジネス重複排除またはべき等性の保証が必要になります。

高性能: クライアントに成功応答を返す前にすべてのノードにデータを書き込む必要があるアルゴリズムと比較して、Raft アルゴリズムでは大多数のノードが成功するだけで済みます。少数のノードによる処理が遅くても、システム全体の動作が遅れることはありません。

オリジナルリンク: https://cloud.tencent.com/community/article/678192

[この記事は51CTOコラムニスト「テンセントクラウドテクノロジーコミュニティ」によるオリジナル記事です。転載の許可を得るには51CTOを通じて原作者に連絡してください]

この著者の他の記事を読むにはここをクリックしてください