ラフト（アルゴリズム）

ラフト

Raft コンセンサス アルゴリズムのマスコット。
クラス	コンセンサスアルゴリズム

Raft は、Paxosファミリーのアルゴリズムの代替として設計されたコンセンサスアルゴリズムです。ロジックの分離によって Paxos よりも理解しやすいように設計されましたが、正式に安全性が証明されており、いくつかの追加機能も提供しています。^{[1] Raft は、コンピューティング システムのクラスター}全体に状態マシンを分散する一般的な方法を提供し、クラスター内の各ノードが同じ一連の状態遷移に同意することを保証します。Go、C++、Java、Scalaで完全な仕様の実装を備えた、多数のオープンソースの参照実装があります。[ ^2]信頼性、複製、冗長性、耐障害性にちなんで名付けられました。^[3]

Raftはビザンチンフォールトトレラント（BFT）アルゴリズムではありません。ノードは選出されたリーダーを信頼します。^[1]

Raft は選出されたリーダーを介して合意形成を図る。Raft クラスタ内のサーバはリーダーまたはフォロワーのいずれかであり、選出の場合（リーダーが利用できない）には候補になることができる。リーダーはフォロワーへのログの複製を担当する。定期的にハートビート メッセージを送信して、フォロワーに自身の存在を知らせる。各フォロワーにはタイムアウト（通常 150 ～ 300 ミリ秒）があり、その時間内にリーダーからのハートビートを待つ。ハートビートを受信するとタイムアウトはリセットされる。ハートビートを受信しない場合、フォロワーはステータスを候補に変更し、リーダー選出を開始する。^{[1] [4]}

Raft は、リーダー アプローチによるコンセンサスを実装します。クラスターには、クラスターの他のサーバーでのログ レプリケーションの管理に全面的に責任を負う、選出されたリーダーが 1 人だけ存在します。つまり、リーダーは、他のサーバーに相談することなく、新しいエントリの配置と、リーダーと他のサーバー間のデータ フローの確立を決定できます。リーダーは、障害が発生するか切断されるまでリードし、その場合は、生き残ったサーバーが新しいリーダーを選出します。

Raft では、コンセンサス問題は、以下にリストされている 2 つの比較的独立したサブ問題に分解されます。

既存のリーダーが失敗した場合、またはアルゴリズムが初期化された場合は、新しいリーダーを選出する必要があります。

この場合、クラスターで新しいタームが始まります。タームとは、サーバー上で新しいリーダーを選出する必要がある任意の期間です。各タームはリーダー選出から始まります。選出が正常に完了した場合 (つまり、単一のリーダーが選出された場合)、タームは新しいリーダーによって編成された通常の操作を継続します。選出が失敗した場合、新しいタームが始まり、新しい選出が行われます。

リーダー選挙は候補サーバーによって開始されます。サーバーは、選挙タイムアウトと呼ばれる期間内にリーダーからの通信を受信しない場合、候補になり、現職のリーダーはもういないとみなされます。サーバーは、任期カウンターを増やし、自分自身を新しいリーダーとして投票し、他のすべてのサーバーに投票を要求するメッセージを送信することで選挙を開始します。サーバーは、先着順で、任期ごとに 1 回のみ投票します。候補者が、現在の任期よりも大きい任期番号を持つ別のサーバーからメッセージを受信した場合、候補者の選挙は敗北し、候補者はフォロワーに変わり、リーダーを正当なものとして認識します。候補者が過半数の票を獲得した場合、その候補者が新しいリーダーになります。どちらも起こらなかった場合 (たとえば、投票が分裂したため)、新しい任期が始まり、新しい選挙が始まります。^[1]

Raft は、分割投票の問題が迅速に解決されるように、ランダムな選挙タイムアウトを使用します。これにより、サーバーが同時に候補になることがないため、分割投票の可能性が減ります。1 つのサーバーがタイムアウトし、選挙に勝ち、リーダーになり、フォロワーが候補になる前に他のサーバーにハートビート メッセージを送信します。^[1]

リーダーはログのレプリケーションを担当します。リーダーはクライアントのリクエストを受け入れます。各クライアント リクエストは、クラスター内のレプリケートされたステート マシンによって実行されるコマンドで構成されます。各リクエストは、リーダーのログに新しいエントリとして追加された後、AppendEntries メッセージとしてフォロワーに転送されます。フォロワーが利用できない場合は、リーダーは、ログ エントリが最終的にすべてのフォロワーによって保存されるまで、AppendEntries メッセージを無期限に再試行します。

リーダーは、エントリが複製されたという確認をフォロワーの半数以上から受け取ると、そのエントリをローカル ステート マシンに適用し、要求がコミットされたとみなされます。^{[1] [4]}このイベントは、リーダーのログにある以前のエントリもすべてコミットします。フォロワーは、ログ エントリがコミットされたことを知ると、そのエントリをローカル ステート マシンに適用します。これにより、クラスター全体のすべてのサーバー間でログの一貫性が確保され、ログ マッチングの安全ルールが遵守されます。

リーダーがクラッシュした場合、ログは不整合のままになり、古いリーダーからのログの一部がクラスター全体に完全に複製されないことがあります。新しいリーダーは、フォロワーに自身のログを強制的に複製させることで不整合に対処します。これを行うには、リーダーはフォロワーごとに自身のログとフォロワーのログを比較し、一致する最後のエントリを見つけ、フォロワーのログでこの重要なエントリの後のエントリをすべて削除して、自身のログ エントリに置き換えます。このメカニズムにより、障害が発生する可能性のあるクラスターでログの整合性が回復されます。

Raft は、以下の各安全特性を保証します。

• 選挙の安全性:任期中に選出されるリーダーは最大で 1 人です。
• リーダー追加のみ:リーダーはログに新しいエントリを追加することしかできません (エントリを上書きしたり削除したりすることはできません)。
• ログのマッチング: 2 つのログに同じインデックスと用語を持つエントリが含まれている場合、指定されたインデックスまでのすべてのエントリにおいてログは同一です。
• リーダーの完全性:ログ エントリが特定の期間内にコミットされた場合、そのエントリはこの期間以降のリーダーのログに存在します。
• ステート マシンの安全性:サーバーが特定のログ エントリをステート マシンに適用した場合、他のサーバーは同じログに対して異なるコマンドを適用することはできません。

最初の 4 つのルールは、前のセクションで説明したアルゴリズムの詳細によって保証されます。ステート マシンの安全性は、選出プロセスの制限によって保証されます。

このルールは、単純な制限によって保証されます。つまり、ログにコミットされたすべてのエントリが含まれていなければ、候補は選出に勝つことができません。選出されるには、候補はクラスターの過半数とコンタクトする必要があり、ログをコミットするためのルールを考えると、コミットされたすべてのエントリは、候補がコンタクトするサーバーの少なくとも 1 つに存在することになります。

Raft は、ログ内の最後のエントリのインデックス用語を比較して、2 つのログ (2 つの異なるサーバーによって保持される) のどちらがより新しいかを判断します。ログの最後のエントリが異なる用語を持つ場合、後の用語を持つログの方が新しいです。ログが同じ用語で終わる場合、長い方のログの方が新しいです。

Raft では、候補者から投票者へのリクエストには、候補者のログに関する情報が含まれます。投票者自身のログが候補者のログよりも新しい場合、投票者は候補者への投票を拒否します。この実装により、ステート マシンの安全性ルールが保証されます。

フォロワーがクラッシュすると、他のサーバーから送信されたAppendEntriesおよび投票リクエストは失敗します。このような失敗は、ダウンしたフォロワーへの接続を無期限に試行するサーバーによって処理されます。フォロワーが再起動すると、保留中のリクエストが完了します。障害が発生する前にリクエストがすでに考慮されている場合、再起動したフォロワーはそれを無視します。

Raft では、クラスターの完全な可用性を確保するために、安定したリーダーを選出して長期間維持するためにタイミングが重要です。アルゴリズムの タイミング要件を尊重することで安定性が確保されます。

放送時間 << 選挙タイムアウト << MTBF

• ブロードキャスト時間は、サーバーがクラスター内のすべてのサーバーにリクエストを送信し、応答を受信するのにかかる平均時間です。これは、使用されるインフラストラクチャに依存します。
• MTBF (平均故障間隔) は、サーバーの故障間隔の平均です。また、インフラストラクチャにも関連しています。
• electionTimeout は、リーダー選出セクションで説明されているものと同じです。これはプログラマが選択する必要があります。

これらの値の一般的な数値は、 broadcastTimeでは 0.5 ミリ秒から 20 ミリ秒です。これは、プログラマーがelectionTimeout を10 ミリ秒から 500 ミリ秒の間に設定することを意味します。単一のサーバー障害が発生するまでに数週間から数か月かかる場合があるため、これらの値は安定したクラスターには十分であることを意味します。

• CockroachDBはレプリケーション層でRaftを使用しています。^[5]
• EtcdはRaftを使用して高可用性の複製ログを管理します^[6]
• HazelcastはRaftを使用して、分散データ構造のための強力な一貫性レイヤーであるCPサブシステムを提供します。^[7]
• MongoDB はレプリケーション セットで Raft のバリアントを使用します。
• Neo4jは一貫性と安全性を確保するためにRaftを使用しています。^[8]
• RabbitMQはRaftを使用して耐久性のある複製FIFOキューを実装します。^[9]
• ScyllaDBはメタデータ（スキーマとトポロジの変更）にRaftを使用する^[10]
• Splunk Enterpriseはサーチヘッドクラスタ（SHC）でRaftを使用しています^[11]
• TiDBはストレージエンジンTiKVでRaftを使用します。^[12]
• YugabyteDBはDocDBレプリケーションにRaftを使用しています^[13]
• ClickHouseはZooKeeperのようなサービスの社内実装にRaftを使用している^[14]
• Redpandaはデータ複製にRaftコンセンサスアルゴリズムを使用している^[15]
• Apache Kafka Raft（KRaft）はメタデータ管理にRaftを使用します。^[16]
• NATSメッセージングは​​、 Jetstreamクラスタ管理とデータ複製にRaftコンセンサスアルゴリズムを使用しています^[17]
• Camundaはデータ複製にRaftコンセンサスアルゴリズムを使用している^[18]

• 公式サイト