合意アルゴリズムRaftの簡単な紹介

[[417323]]

この記事は、張張が執筆したWeChatパブリックアカウント「建築改善への道」から転載したものです。この記事を転載する場合は、Road to Architecture Improvement の公開アカウントまでご連絡ください。

みなさん、こんにちは。私は公開アカウント「建築改善への道」の著者、張張です。

最近、チームメイトとコンセンサスアルゴリズム Raft について話し合ったので、以前に公開された記事を調べてレビューしました。

1. ラフトアルゴリズムの概要

サービス ノードが 1 つしかない場合、ノードのコンセンサスの問題は発生しません。複数の異なるサービス ノードがある場合、分散一貫性の問題が発生します。

Raft は分散合意を実現するためのプロトコルです。いわゆるコンセンサスとは、一部のノード障害、ネットワーク遅延、またはネットワークのセグメント化が発生した場合でも、複数のノードが特定の問題について一貫した見解に達することを意味します。

主な適用シナリオ:

• Redis センチネル リーダー選挙
• Etcdは主に共有設定とサービス検出を目的としており、一貫性を実現するためにRaftアルゴリズムを使用しています。
• 暗号通貨（ビットコイン、ブロックチェーン）のコンセンサスアルゴリズム

解決すべき主な問題は何ですか?

分散ストレージ システムは通常、複数のコピーを維持することでシステムの可用性を向上させますが、複数のコピー間でデータの一貫性を維持するコストは分散ストレージ システムの中心的な問題の 1 つです。

2. Raftアルゴリズムの実装プロセス

理解を深めるために、Raft は一貫性アルゴリズムをリーダーの選択、ログの複製、安全性などのいくつかの部分に分割し、より強力な一貫性を使用して考慮する必要がある状態を減らします。

この記事では、理解を早めるために短編小説を例として使用します。

2.1 リーダー選出

部門では新しいサービス チームを立ち上げる必要があり、現在は学生 A、B、C の 3 人がいます。

後の段階でリソースと管理ニーズを統一的に割り当てやすくするために、3 人の学生の中からグループ リーダーを選出する必要があります。

A は自分がリーダーになれると感じたので、B と C に「私に投票してください。私はリーダーになりたいのです」と言います。この時点で、A は候補者となり、事前に自分自身に投票しています。

1) BとCがリーダーになることを一度も考えたことがない場合は、「OK、あなたに投票してください」と言う→Aは3票を獲得し、リーダーに選出される

2) Bが以前にリーダーになることを考えていた場合、Bは自分に投票し、CはAに投票しました。→Aは2票（3票の半分以上）を獲得し、リーダーに選出されました。

3) BとCが自分自身に投票した場合→A、B、Cはそれぞれ自分の投票権を持ち、選挙は失敗し、新しい選挙が開始されます。

4) Bが以前からリーダーになることを考えていて、CがすでにBに投票していた場合 → Bは2票（3人の半数以上）を獲得し、リーダーに選出されました

上記の選出プロセスから、ノードはいつでも次の 3 つの状態のいずれかにあることがわかります。

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

これら 3 つの状態の遷移プロセスを次の図に示します。

選挙プロセス

ステップ1: フォロワーが候補者になる

フォロワーがリーダーの意見を聞けない場合は、候補者になることができます。

ステップ2: 候補者が票を獲得する

自分に投票し、他のノードに投票リクエストを送信します。ノードはリクエストを受信すると応答します。

ステップ3: 他のノードからの応答を待つ

候補者がノードからの投票の半分以上（自身の投票を含む）を獲得した場合、その候補者がリーダーになります。

リーダーが生成されたことを候補者に通知すると、自動的にフォロワーに切り替わります。

一定期間内に過半数の投票が得られなかった場合は、候補者としての地位は維持され、選挙が再開されます。

ステップ4: 候補者が選挙に勝利する

新しいリーダーは、他のノードが新しい選出をトリガーするのを防ぐために、すべてのノードにすぐにメッセージを送信します。

2.2 ログ同期

上記2.1のリーダー選出後、グループリーダーが選出されました。ここでは、Aがリーダーとして選出されたものとします。これで、ドッキング パーティ (クライアントと呼ばれる) から提案されたいくつかの運用タスクを実行できるようになります。

各デマンド接続はチームリーダーの承認が必要であると規定されています。従業員が操作要求を行い、リーダーはそれを受信後に記録し、グループ内の他の学生と同期します。他の学生がこの要求を確認した後でのみ、リーダーは操作を確認し、実行結果を従業員（フォロワーノード）に同期します。

ログレプリケーション

リーダー選出プロセスの後、新しいリーダー ノードが生成され、システムに対するすべての変更はリーダー ノードを通じて実装される必要があります。

ステップ1: リーダーがログエントリを追加する

システムへのすべての変更はノードのログにエントリとして追加されます

ステップ2: リーダーはAppend Entries RPCを並列に発行し、応答を待ちます。

リーダーは、半数以上のノードがエントリを書き込むまで待機し、リーダー ノードがエントリをコミットし、その後、リーダーはフォロワーにエントリが送信されたことを通知します。

ステップ3: リーダーは大多数の応答を取得し、ステートマシンにエントリを適用します。

ステート マシン: 決定論的なアプリケーションとして理解できます。いわゆる決定論とは、入力が同じである限り、どのステート マシンでも同じ出力を計算することを意味します。

ステップ4: リーダーはクライアントに返信し、フォロワーにログを適用するよう通知する

クラスターはシステムの状態について合意に達した。

ログベースの複製されたステートマシンの概略図:

申請手続きに関するいくつかの質問

Q1

クライアントがフォロワーノードへのアクセスを要求した場合はどうなりますか?

回答: フォロワー ノードは、リクエストをリーダー ノードに転送します。

Q2

リーダーとフォロワーのログが矛盾している場合はどうすればいいでしょうか?

答え：

1) リーダーは、フォロワーにログのコピーを強制することで、ログの不整合に対処します。フォロワーの不整合なログは、リーダーのログによって上書きされます。

2) フォロワーのログをリーダー自身のログと一致させるために、リーダーはフォロワーのログが一致する場所を見つけ、その場所以降のフォロワーのエントリを上書きする必要があります。

3) リーダーは後ろから前に向かって試行し、AppendEntries が失敗するたびに前のログ エントリを試行して、各フォロワーのログの一貫した位置を見つけるまで試行し、その後、その位置以降のフォロワーのエントリを 1 つずつ上書きします。

2.3 セキュリティ保証

チームの運営の安定性を確保するために、いくつかのデフォルト要件があります。

2.3.1 選挙のセキュリティ

つまり、任期中、最大で 1 人のリーダーが選出されることになります。システム内に同時に複数のリーダーが存在する場合、それはブレイン スプリットと呼ばれ、データの上書きによる損失が発生します。

チームは一度に 1 人のリーダーしか持つことができません (選挙失敗などの特別な状況を除く)。そうでない場合、複数のリーダーが同時に要求を処理して命令を出すと、チーム内のペースが不安定になりやすくなります。

Raft では、次の 2 つの点によってこのプロパティが保証されます。

1) ノードは任期中に最大 1 票しか投じることができません。

2) 多数決を獲得したノードのみがリーダーになります。

2.3.2 ログマッチングの整合性

同じチーム内の 2 人の学生が現在同じタスクを担当している場合は、以前の作業記録も一貫している必要があります。つまり、同じ初期状態 + 同じ操作 = 同じ最終状態

リーダーはクライアントのリクエストをログ エントリにカプセル化し、これらのログ エントリを他のフォロワー ノードにコピーします。全員がこれらのリクエストを順番に適用するため、最終的な状態は確実に一貫しています。

Raft ログ同期の結論:

1) 異なるログ内の 2 つのエントリが同じインデックスと用語を持つ場合、それらに格納されるコマンドは同じです。

2) 異なるログ内の 2 つのエントリが同じインデックスと用語を持つ場合、それ以前のエントリはすべてまったく同じになります。

2.3.3 リーダーデータの整合性

チームの後任リーダーは、リーダー在任中の作業記録がすべて引き継がれるため、チームの前任の作業内容を把握している必要があります。

特定の期間にログ エントリがコミットされると、このログ エントリは、すべての上位期間リーダーのログに必ず表示されます。

Raft ログ上書きルール:

1) ログは多数派ノードにコピーされたときにのみコミットされたとみなされます

2) ノードは多数決を受け取った場合にのみリーダーになることができ、ノード A がノード B に投票するための前提条件の 1 つは、B のログが A のログよりも古くないことです。

結論

すべてのアルゴリズム実装の原則は、実際の社会的な作業モデルを反映しています。複雑な一貫性アルゴリズムを実際のケースに関連付けて理解することで、半分の労力で 2 倍の結果を達成できるようになります。

この記事は、ラフト プロトコルの簡単な紹介を目的としています。さらに詳しく知りたい場合は、次の 2 つのリンクをお勧めします。

1) Raft ビジュアルテストとさまざまな言語で実装された Raft: https://raft.github.io/

2) Raft アルゴリズム - アニメーション デモ (優れた入門チュートリアル): http://thesecretlivesofdata.com/raft/