ラフト Kv

Lab2 文档翻译#

私の英語はあまり得意ではないので、翻訳ソフトを使って翻訳し、その後手動で校正して理解します。

original アドレス: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html

Introduction#

これは一連の実験の最初のもので、フォールトトレラントなキー / バリューストレージシステムを構築します。
この実験では、Raft（複製された状態機械プロトコルの一種）を実装します。次の実験では、Raft の上にキー / バリューサービスを構築します。
その後、複数のレプリカを持つ状態機械でシャーディング（キーに基づいてハッシュを使用してどのレプリカにルーティングするかを決定）を行い、パフォーマンスを向上させます。

複製（レプリケーション）は、複数のレプリケーションサーバーにその状態（すなわちデータ）の完全なコピーを保存することによってフォールトトレランスを実現します。
いくつかのサーバーが故障（クラッシュまたはネットワークの切断や揺れ）しても、レプリケーションはそれらが引き続き動作することを可能にします。課題は、故障がレプリカに異なるデータを持たせる可能性があることです。

Raft は、クライアントのリクエストをログと呼ばれるシーケンスに整理し、すべてのレプリカサーバーが同じログを見ていることを保証します。
各レプリカはログの順序に従ってクライアントのリクエストを実行し、それらをローカルのサービス状態のレプリカに適用します（クライアントからのコマンドを実行することです）。
すべての生存しているレプリカが読み取るログの内容が同じであるため、同じ順序でリクエストを実行し、したがって同じサービス状態を持ちます。
もしサーバーが故障した場合でも、その後回復した場合、Raft はそのログを最新の状態に更新する責任を負います。少なくとも過半数のサーバーが生きていて、通信を続けることができる限り、
Raft は動作し続けます。この数に達しない場合、Raft は動作を停止し、この数に達するまで再び動作を開始しません。

このラボでは、Raft を関連するメソッドを持つ GO のオブジェクトタイプとして実装し、より大きなモジュールで使用できるようにします。
一組の Raft インスタンスは RPC を介して複製されたログを維持します。あなたの Raft インスタンスは、一連の不確定番号のコマンドをサポートし、
これらはログエントリとも呼ばれます。これらのエンティティはインデックスで番号付けされます。特定のインデックスを持つログエントリはコミットされ、
この時、あなたの Raft はこのログをより大きなサービスに送信して実行する必要があります。

あなたはextended Raft paperの設計に従うべきです、
特に図 2。あなたは論文のほとんどの内容を実装し、永続的な状態を保存し、ノードの故障後に状態を読み取ることを含みます。
クラスタメンバーの変更（セクション 6）は実装しません。

このガイドが役に立つかもしれません、
また、同様にこのロックと構造に関する提案も役立ちます。
より広範な視点が必要な場合は、Paxos、Chubby、Paxos Made Live、Spanner、Zookeeper、Harp、Viewstamped Replication
およびBolosky et alを見てください。

このラボで最も挑戦的な部分は、あなたのソリューションを実装することではなく、それをデバッグすることかもしれません。この課題に対処するために、あなたは実装をデバッグしやすくする方法に時間を費やす必要があるかもしれません。
ガイダンスページや、効果的な印刷声明に関するこのブログ記事を参照できます。

私たちはまた、Raft の相互作用図を提供していますRaft 交互作用図、
これは Raft コードが上位（使用者？）とどのように相互作用するかを明らかにするのに役立ちます。

The code#

raft/raft.goにコードを追加して Raft を実装します。このファイルには、スケルトンコードと RPC を送受信する方法の例があります。
あなたの実装は以下のインターフェースをサポートしなければなりません。テスト者と（最終的に）あなたのキー / バリューサービスはこのインターフェースを使用します。詳細はraft.goのコメントにあります。

{{< block type="tip">}}
Raft インスタンスは rpc を介してのみ通信でき、labrpcパッケージを使用しなければなりません（例えば、ファイルや共有変数を使用してはいけません）。
{{< /block >}}

// create a new Raft server instance:
rf := Make(peers, me, persister, applyCh)

// start agreement on a new log entry:
rf.Start(command interface{}) (index, term, isleader)

// ask a Raft for its current term, and whether it thinks it is leader
rf.GetState() (term, isLeader)

// each time a new entry is committed to the log, each Raft peer
// should send an ApplyMsg to the service (or tester).
type ApplyMsg

Make#

Make(peers []*labrpc.ClientEnd, me int,persister *Persister, applyCh chan ApplyMsg)

Raft サーバーを作成するために使用されます。

すべての raft サーバーのポートはpeers[]に格納されています（現在のサービスを含む）、現在のサービスのポートはpeers[me]を介して取得できます。
すべてのサービスのpeers[]配列は同じ順序を持っています。
persisterはpersistent stateを保存するための場所であり、初期時に最も新しい状態を保存します。
applyChはサービスまたはテスターが Raft にメッセージを送信するためのチャネルです。Make()
は迅速に戻る必要があるため、いくつかの長時間実行されるタスクのためにgoroutinesを開始する必要があります。

Start#

Raft のサービス（例えば kv サーバー）は、次に Raft ログに追加されるコマンドについて合意を開始することを希望します。このサーバーがリーダーでない場合は
false を返します。そうでなければ、プロトコルを開始し、すぐに返します。このコマンドが Raft ログに永遠にコミットされることは保証できません、なぜならリーダーが故障したり選挙に負ける可能性があるからです。Raft
インスタンスが殺されても、この関数は優雅に戻るべきです。最初の戻り値はこのコマンドがコミットされるときに表示されるインデックスです。2 番目の戻り値は現在の任期です。このサーバーがリーダーであると考える場合、3 番目の戻り値は
true です。

Start(command interface{}) (int, int, bool)

Raft のサービス（例：k/v サーバー）は、次に Raft ログに追加されるコマンドについて合意を開始することを希望します。
現在の Raft サーバーがリーダーでない場合はfalseを返します。そうでなければ、プロトコルを開始し、すぐに返します。ログの追加が完了するのを待つ必要はありません。
したがって、このコマンドが Raft ログに必ずコミットされることは保証できません、なぜならリーダーが故障したり選挙に負ける可能性があるからです。
Raft インスタンスが kill されても、この関数は優雅に戻るべきです。

最初の戻り値はこのコマンドがコミットされるときに設定されるインデックスです。2 番目の戻り値は現在の任期です。このサーバーがリーダーであると考える場合、3 番目の戻り値はtrueです。

新しくコミットされたRaft log entityは、Make()のapplyChにApplyMsgを送信する必要があります。

2A - Leader Election#

Raft リーダー選挙とハートビート（AppendEntries RPCsにログエントリを含まない）を実装します。

2A の目標は：リーダーを選出し、故障がない場合はリーダーであり続け、古いリーダーが故障したり古いリーダーとの間でパケットが失われた場合は新しいリーダーが引き継ぐことです。

{{< block type="tip">}}
この故障はリーダーが故障することを意味しますか？つまり、リーダーが運用上の故障やネットワークの問題がない限り、永遠にリーダーであるということですか？
{{< /block >}}

要点：

go test -run 2Aを実行して実装をテストします。
論文の図 2に従い、RequestVote RPCsの送受信に主に関心を持ち、
選挙に関連するサーバーのルールおよびリーダー選挙に関連する状態を考慮します。
Raft構造体にリーダー選挙に関連する状態を追加し、各ログの情報を保存するための構造体を定義する必要があります。
RequestVote()を実装し、Raft サービスが互いに投票できるようにします。RequestVoteArgsとRequestVoteReplyの 2 つの構造体を追加します。Make()を修正し、
ハートビートメッセージをチェックするための goroutine を作成し、一定の時間内にピアからメッセージを受信しない場合は、定期的にRequestVote RPCsを送信してリーダー選挙を開始します。これにより、リーダーが存在する場合、ピアはリーダーが誰であるかを知ることができ、または自分がリーダーになることができます。
ハートビートを実装し、AppendEntries RPC構造体を定義する必要があります（すべてのパラメータが必要なわけではありませんが）。
そして、リーダーが定期的にそれを送信するようにします。AppendEntries RPCのハンドルメソッドを作成し、選挙タイムアウトをリセットします。
これにより、誰かが選出された場合、他のサーバーは再びリーダーにならないようになります。
異なるピアの選挙タイムアウトが同時に発生しないようにしてください。そうでないと、すべてのピアが自分自身に投票するだけになり、誰もリーダーにならなくなります。
テスト中、リーダーが 1 秒あたり 10 回を超える RPC リクエストを送信してはいけません。
テスト中、古いリーダーが故障した後 5 秒以内に新しいリーダーを選出する必要があります（大多数のノードが通信を続けることができる場合）。
ただし、split voteが発生した場合（パケットが失われたり候補者が同じランダムなバックオフ時間を選択した場合に発生する可能性があります）、リーダー選挙は複数回必要になる可能性があります。
したがって、十分に短い選挙タイムアウト（すなわちハートビート間隔）を設定する必要があります。たとえ複数回選挙が行われても、5 秒以内に完了する可能性があります。
論文のリーダー選挙セクションで述べられている選挙タイムアウトの範囲は 150 から 300 ミリ秒です。
リーダーが 150 ミリ秒以上の頻度でハートビートを送信する場合にのみ、上記の範囲が意味を持ちます。テスト中に 1 秒あたり 10 回のハートビートを制限するため、論文よりも大きな選挙タイムアウトを使用する必要がありますが、あまり大きくしてはいけません。そうしないと、5 秒以内に選挙を完了できなくなる可能性があります。
コードがテストに合格しない場合は、論文の図 2を再度読み直してください。リーダー選挙のすべてのロジックは図の複数の部分に分散しています。
GetState()を実装することを忘れないでください。
テスト中に Raft インスタンスをシャットダウンする場合、rf.kill()が呼び出されます。rf.killedを呼び出して、kill()が呼び出されたかどうかを確認できます。すべてのループでこれを行うことをお勧めします。そうしないと、死亡した Raft インスタンスが混乱した情報を印刷する可能性があります。
go RPCは、名前が大文字で始まる構造体フィールドのみを送信します。サブ構造体も大文字のフィールド名を持つ必要があります。

2B - log#

リーダーとフォロワーのコードを実装して新しいログを追加します。

要点：

あなたの最優先目標はTestBasicAgree2Bを通過することです。Start()の実装から始め、図 2に従ってコードを作成し、
AppendEntriesを介して新しいログを送信および受信します。最近コミットされたログを相手のapplyChに送信します。
election restrictionを実装する必要があります。
初期の Lab 2B テストで合意に達しなかった方法の 1 つは、リーダーがまだ生存していても選挙を繰り返すことです。
選挙タイマーのバグを見つけるか、選挙に勝った後にすぐにハートビートを送信しない問題を見つけてください。
あなたのコードには、特定のイベントを繰り返しチェックするループがあるかもしれません。これらのループを連続して実行しないようにしてください。そうしないと、実装が遅くなり、テストに合格できなくなります。
Go の条件変数を使用するか、各ループにtime.sleep(10 * Millisecond)を追加してください。
config.goとtest_test.goを読み、何をテストしているのかを理解してください。

コード実装思考#

コードの実装思考や遭遇した問題を大まかに記録します。

2A#

図 2 の state セクションに対応する属性を追加します。
現在の役割を表すRaftRole属性を追加します：リーダー、候補者、フォロワー。
ticker関数を実装します：
- 2 つのtime.timerをトリガーとして使用できます。
- ハートビートを長い間受信していないかどうかを判断し、選挙を開始します。
- 自分の権威を維持するためにハートビートを送信する必要があるかどうかを判断します。
このルールに注意してください：RPC のリクエストまたは応答に任期 T が含まれている場合、currentTerm は T に設定され、状態はフォロワーに切り替わります。
選挙を開始するプロセスを実装します。
- 図 2 のRules for Serversのcandidateプロセスに従って一歩ずつ実装します。
- RequestVote RPCを並行して発信し、票数が 1/2 を超えればリーダーに変わります（ハートビートをブロードキャストする必要があります）。
RequestVoteを実装します。
- 図 2 のRequestVote RPCに従って実装します。
AppendEntriesを実装します。
- フォロワーに変換し、選挙タイムアウトをリフレッシュするだけで簡単に実装できます。
すべてのノードが応答を受け取った後、選挙タイムアウトをリフレッシュします（具体的な状況に応じて判断します）。
リーダーになった後、ハートビートのタイムアウトをリフレッシュし始めます（フォロワーの選挙タイムアウトをリフレッシュするために）。

遭遇した問題：

最初のテストでwarning: Term changed even though there were no failuresが表示されます。

リーダーが存在する場合、他のフォロワーが選挙を開始したことを示しています。原因はelection timeoutとAppendEntriesのタイミングが非常に近いことだと推測しています。これにより、2 つのタイムアウトをデバッグする必要があります。私の選挙タイムアウトは 200〜350ms、ハートビートは 125ms に固定されています。

役割を変換する際にif new role == old role then returnのチェックを追加しましたが、これによりelection timeoutがリフレッシュされませんでした。

応答またはリクエスト時に、すぐに 4 条を処理する必要があります。

Raft 論文翻訳#

重要なセクションをいくつか翻訳します。

original アドレス: https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf

Abstract#

Raft は、複製ログを管理するためのコンセンサスアルゴリズムです。Paxos アルゴリズムと同じ機能と性能を提供しますが、そのアルゴリズムの構造は Paxos とは異なり、
Raft は理解しやすく、実際のシステムを構築するのが容易です。理解しやすさを高めるために、Raft はコンセンサスアルゴリズムをリーダー選挙、ログ複製、安全性などのいくつかの重要なモジュールに分割しました。
同時に、より強力な一貫性を実装することで、考慮すべき状態の数を減らします。Raft には、クラスタメンバーの動的な変更を許可するメカニズムも含まれており、重複する過半数を利用して安全性を保証します。

Introduction#

Raft アルゴリズムは、既存のコンセンサスアルゴリズムといくつかの点で類似しています（主に Oki および Liskov の Viewstamped Replication）が、以下の新機能があります：

強いリーダー：Raft は他のコンセンサスアルゴリズムよりも強力なリーダーの形式を使用します。たとえば、ログはリーダーから他のサーバーにのみ送信されます。
これにより、複製ログの管理が簡素化され、Raft は理解しやすくなります。
リーダー選挙：Raft はランダムなタイマーを使用してリーダーを選出します。この方法は、すべてのコンセンサスアルゴリズムが改善を必要とするハートビートメカニズムにわずかな改善を加えたものですが、これにより
Raft は競合を解決する際により簡単で迅速になります。
メンバー調整：Raft は、クラスタメンバーの変更に関する問題を処理するために新しい共同コンセンサスアルゴリズムを使用します。
調整プロセス中の 2 つの異なる構成の過半数のクラスタは重複しており、これによりメンバー変更時にクラスタが正常に動作し続けることができます。

Replicated State Machine#

Replicated State Machine（複製状態機械）は、分散システムでさまざまなフォールトトレランスの問題を解決するために使用されます。たとえば、GFS、HDFS、RAMCloud などの単一リーダーの大規模クラスタシステムでは、
通常、独立した複製状態機械を使用してリーダー選挙を管理し、リーダーがクラッシュした場合でも生存できるように設定情報を保存します。複製状態機械の例には Chubby や Zookeeper が含まれます。

コンセンサスアルゴリズムは、複製状態機械の背景で提案されており、この方法では、一組のサーバー上の状態機械が同じ状態の同じレプリカを計算し、いくつかのサーバーがダウンしても動作を続けることができます。

図 1 に示すように、複製状態機械は複製ログを介して実現されます。各サーバーは、一連のコマンドを含むログを保持し、その状態機械はそれらを順番に実行します。
各ログは同じ順序の同じコマンドを含んでいるため、各状態機械は同じコマンドシーケンスを実行します。状態機械は決定的であるため、各状態機械は同じ状態と同じ順序の出力を計算します。

コンセンサスアルゴリズムのタスクは、複製ログの一貫性を保証することです。サーバー上のコンセンサスモジュールは、クライアントからのコマンドを受信し、それらをログに追加し、
他のサーバー上のコンセンサスモジュールと通信して、すべてのログが最終的に同じになるようにします（同じリクエストが同じ順序で）、たとえいくつかのサービスが故障しても。
コマンドが正しく複製されると、各サービスの状態機械はログの順序に従ってそれらを処理し、結果をクライアントに返します。

したがって、これらのサービスは単一の、高度に信頼性のある状態機械のように見えます。

実際のコンセンサスアルゴリズムには以下の属性があります：

非バイザンティン（non-Byzantine）条件下での安全性（常に誤った結果を返さないこと）、ネットワーク遅延、分割、ネットワークパケットの損失、冗長性、順序の乱れを含みます。
大多数のサービスが稼働し、相互に通信でき、クライアントと通信できる限り、すべての機能を発揮できる（可用性）。したがって、5 台のサービスのクラスタは 2 台のサービスの故障に耐えられます。
サービスが停止するために故障した場合、それらは後でstable storageから状態を回復し、再びクラスタに参加する可能性があります。
ログの一貫性を保証するために時系列に依存しない：誤った時計と極端な情報遅延は、最悪の場合、可用性の問題を引き起こす可能性があります。
一般的に、コマンドの完了は、クラスタ内の大多数が単一のラウンドのリモートコールに応答することに依存し、少数の遅いサービスはシステム全体のパフォーマンスに影響を与えません。

The Raft consensus algorithm#

Raft は、前述の複製ログを管理するためのアルゴリズムです。図 2はこのアルゴリズムの簡潔な要約であり、図 3はこのアルゴリズムの重要な属性を列挙し、次にこれらの部分を個別に議論します。

Raft は、_リーダー_を選出し、そのログ複製の責任を完全に管理させることによってコンセンサスを実現します。リーダーはクライアントからのログを受け取り、それを他のサービスに複製し、いつそれらのログを安全に消費できるかを通知します。リーダーはログ複製の管理を簡素化します。たとえば、リーダーは新しいログをどこに保存するかを他のサービスに尋ねることなく自分で決定でき、データはリーダーから他のサーバーに流れます。リーダーは故障する可能性があり、他のサーバーとの接続を失うことがあります。この場合、リーダーを再選出する必要があります。

リーダーベースのアプローチに基づいて、Raft は一貫性の問題を 3 つのサブプロセスに分けて解決します：

リーダー選挙：リーダーが故障した場合（クラッシュ）に新しいリーダーを選出する必要があります。
ログ複製：リーダーはクライアントからのログを受け取り、クラスタ内の他のマシンに複製し、他のサーバーを自分と一致させることを強制します。
安全性：Raft の安全性は図 3の安全属性にあります：もし任意のサーバーがログを消費した場合、他の任意のサーバーは同じログインデックスで異なるログを消費することはできません。

Figure 2#

state：

すべてのサーバーに永続化（RPC リクエストに応答する前に、安定したストレージデバイスに更新されている）
- currentTerm: サーバーが知っている最新の任期（サーバーが最初に起動したときに 0 に初期化され、単調に増加）
- votedFor: 現在の任期内に受け取った投票の候補者 ID、投票がない場合は空
- log[]: ログエントリ、各エントリには状態機械のコマンドと、リーダーがそのエントリを受け取ったときの任期が含まれます（初期インデックスは 1）
すべてのサーバーの揮発性状態
- commitIndex: 知られているコミットされたログの最大インデックス（初期 0、単調に増加）
- lastApplied: 状態機械が実行したログの最大インデックス（初期 0、単調に増加）
リーダー上の不安定な存在（毎回再選挙の後に初期化）
- nextIndex[]: 各サーバーに対して、そのサーバーに送信される次のログエントリのインデックス（初期はリーダーの最後のログインデックス + 1）
- matchIndex[]: 各サーバーに対して、すでにそのサーバーに複製された最高のログエントリのインデックス（初期 0、単調に増加）

AppendEntries RPC

リーダーがログを複製するために呼び出し、ハートビート検出にも使用されます。

引数：
- term: リーダーの任期
- leaderId: フォロワーがリーダーを見つけるために使用（時にはクライアントがフォロワーにリクエストを送信した場合）
- prevLogIndex: 新しいログエントリの直前のログエントリのインデックス
- prevLogTerm: 新しいログエントリの直前のログエントリの任期
- entries[]: 保存する必要があるログ（空の場合はハートビート検出、効率を高めるために複数のエントリを一度に送信することがあります）
- leaderCommit: リーダーがコミットした最高のログエントリのインデックス
結果：
- term: currentTerm、リーダーが自分のtermを更新するために使用
- success: フォロワーのprevLogIndexとprevLogTermが一致する場合は true
受信者の実装：
- if term < currentTerm then return false（リーダーの任期が受信者の現在の任期より小さい場合、受信者はフォロワーまたは候補者である可能性があります）
- if log[prevLogIndex].term != prevLogTerm then return false（受信者のログに prevLogIndex および prevLogTerm と同じインデックスと任期のログエントリが見つからない場合は、偽を返します）
- if log[oldIndex].term != log[newIndex].term then remove log[oldIndex,lastIndex]（既存のログが新しいログ（リクエスト内のログエントリ）と衝突する場合（インデックスが同じで任期が異なる）、そのインデックスと以降のすべてのログを削除します）
- ログリストに存在しない新しいログを追加します。
- if leaderCommit > commitIndex then commitIndex=min(leaderCommit,log[].last.commitIndex)（リーダーの知られている最高のコミットされたログのインデックスが受信者の知られている最高のコミットされたログのインデックスより大きい場合、受信者の知られている最高のコミットされたログのインデックス commitIndex をリーダーの知られている最高のコミットされたログのインデックス leaderCommit または新しいエントリのインデックスの最小値にリセットします）

RequestVote RPC

候補者が呼び出し、投票を収集します。

引数：
- term: 候補者の任期番号
- candidateId: リクエストを発信した候補者の ID
- lastLogIndex: 候補者の最後のログのインデックス
- lastLogTerm: 候補者の最後のログに対応する任期番号
結果：
- term: 現在の任期番号、候補者が自分のtermを更新するために使用
- voteGranted: true は候補者が投票を得たことを示します
受信者の実装：
- if term < currentTerm then return false（term < currentTerm の場合は偽を返します）
- if (votedFor==null||votedFor==candidateId)&&(lastLogIndex,lastLogTerm)==log[].last then return true
  （votedFor が空であるか、candidateId と同じであり、候補者のログが自分のログと同じくらい新しい場合、その候補者に投票します）

Rules for Servers

すべてのサーバー：
- if commitIndex > lastApplied then incr lastApplied and exec log[lastApplied]（もし commitIndex >
  lastApplied なら、lastApplied をインクリメントし、log [lastApplied] を状態機械に適用します）
- if appendEntries.logs exist (log.term > currentTerm) then currentTerm = log.term and set status = follower（もし
  RPC のリクエストまたは応答に任期 T が含まれている場合、currentTerm を T に設定し、状態をフォロワーに切り替えます）
フォロワー：
- いかなるリクエストも発信せず、候補者やリーダーからのリクエストにのみ応答します。
- 選挙タイムアウト後、現在のリーダー（同じ任期）のAppendEntries RPCを受信しない場合、または候補者に投票した場合、候補者に変わります。
候補者：
- 候補者に変わった後、選挙を開始します。
  - currentTermをインクリメントします。
  - 自分に投票します。
  - 選挙タイマーをリセットします。
  - クラスタ内の他のすべてのサーバーにRequestVote RPCを送信します。
- 過半数の投票を受け取った場合、リーダーになります。
- 新しいリーダーのAppendEntries RPCを受信した場合、フォロワーになります。
- 選挙タイムアウトが発生した場合、新しい選挙を開始します。
リーダー：
- リーダーになったら、他のサーバーに空のAppendEntries RPCを送信し、アイドル時に繰り返し送信して選挙タイムアウトを防ぎます。
- クライアントからのコマンドを受信した場合：ローカルログに追加し、実行して状態機械に適用した後、クライアントに応答します。
- フォロワーに対してif last log index >= nextIndex（最後のログエントリのインデックスが nextIndex 以上の場合）：
  次のインデックス以降のすべてのログをAppendEntries RPCを介して送信します。
  - 成功した場合：そのフォロワーのnextIndexとmatchIndexを更新します。
  - ログの不一致により失敗した場合：nextIndexを減少させて再送信します。
- もし数 N が存在し、N > commitIndex、大多数のmatchIndex[i] >= N
  かつlog[N].term == currentTerm：set commitIndex = N

Figure 3#

Election Safety: 任期内にリーダーは 1 つだけ選出される。
Leader Append-Only: リーダーはログを上書きしたり削除したりせず、追加するだけです。
Log Matching: もし 2 つのログが同じインデックスと任期を持っている場合、それらは完全に同じであると見なされます。
Leader Completeness: もしログが任期内にコミットされた場合、それは必ず任期が大きいリーダーのログに存在します。
State Machine Safety: もしサーバーが特定のインデックス位置のログエントリを状態機械に適用した場合、他のすべてのサーバーは同じインデックスで異なるログを持つことはありません。

Raft の基本#

Raft クラスタは複数のサーバーを含むことができます；5 は典型的な数であり、システムは 2 回の故障に耐えることができます（2 台のサービスがダウンします）。
任意の時点で、各サービスは以下の 3 つの状態のいずれかにあります：
leader、follower、candidate。通常、ちょうど 1 つのリーダーが存在し、他のすべてのサーバーはフォロワーです。

フォロワーは受動的です：自分からリクエストを発信せず、リーダーや候補者からのリクエストにのみ応答します。
リーダーはすべてのクライアントのリクエストを処理します（クライアントがフォロワーに連絡した場合、フォロワーはリーダーにリダイレクトします）。
候補者は新しいリーダーを選出するために使用されます（図 4を参照）。

Figure 4#

図 5 に示すように、Raft は時間を任意の長さの_terms_に分割します。任期の番号は連続した整数です。各任期は_election_で始まり、1 つ以上の候補者がリーダーになろうとします。候補者が選挙に勝つと、その任期の残りの間リーダーとして機能します。

特定の状況では、選挙の結果が split vote になることがあります。この場合、任期は終了し、リーダーは存在しません。新しい任期（新たな選挙を伴う）がすぐに始まります。
Raft は、特定の任期内に最大 1 つのリーダーしか存在しないことを保証します。

Figure 5#

異なるサーバーは異なる時間に任期間の切り替えを観察する可能性があり、特定の状況では、サーバーが選挙や任期全体を観察しないこともあります。
任期は Raft 内で論理クロックとして機能し、サーバーが古い情報を検出できるようにします：古いリーダーなど。

各サーバーは現在の任期番号を保存しており、この番号は時間とともに単調に増加します。サーバーが通信するたびに、現在の任期が交換されます；
もしサーバーの現在の任期が他のサーバーより小さい場合、そのサーバーは現在の任期をより大きい値に更新します。

もし候補者またはリーダーが自分の任期が古くなったことを発見した場合、すぐにフォロワーの状態に戻ります。

もしサーバーが受信したリクエストが古い任期番号である場合、そのリクエストは拒否されます。

Raft サーバーは RPC を使用して通信し、基本的なコンセンサスアルゴリズムは 2 種類の RPC のみを必要とします。RequestVote RPCsは候補者が選挙中に発信します；
AppendEntries RPCsはリーダーが発信し、ログエントリを複製し、ハートビートメカニズムを提供します。以下の章では、サーバー間でスナップショットを転送するための 3 番目の RPC も追加されます。
サーバーがタイムリーに応答を受信できない場合、RPC を再試行し、最適なパフォーマンスを得るために RPC を並行して発信します。

リーダー選挙#

Raft はハートビートメカニズムを使用してリーダー選挙をトリガーします。サーバーが起動すると、初期状態はすべてフォロワーです。サーバーがリーダーまたは候補者からの有効な RPC を受信すると、
フォロワー状態に留まります。リーダーは定期的にすべてのフォロワーにハートビート（AppendEntries RPCs、ログエントリを含まない）を送信してその権威を維持します。
フォロワーが一定の時間内に何の通信も受信しない場合（election timeout）、それは利用可能なリーダーがいないと見なし、新しいリーダーを選出するための選挙を開始します。

選挙を開始するために、フォロワーは現在の任期を増加させ、候補者状態に切り替えます。
次に、自分に投票し、クラスタ内の他のすべてのサーバーに並行してRequestVote RPCsを発信します。
候補者は次のいずれかの状況が発生するまでこの状態に留まります：

選挙に勝った。
別のサーバーが自分のリーダーシップを確立した。
一定の時間が経過しても誰も勝たなかった。

次に、これらの結果について議論します：

選挙に勝った

もし候補者が同じ任期内にクラスタ内の大多数のサーバーから投票を得た場合、その候補者は選挙に勝ちます。
各サーバーは、特定の任期内に最大 1 名の候補者に投票し、先着順で投票します。

少数が多数に従う原則は、特定の任期内に最大 1 名の候補者が選挙に勝つことを保証します
（図 3の選挙安全性属性）。
候補者が選挙に勝つと、リーダーになります。次に、すべての他のサーバーにハートビートメッセージ（ログを含まないAppendEntries RPC）を送信し、その権威を確立し、新しい選挙を防ぎます。

別のサーバーが自分のリーダーシップを確立した

投票を待っている間、候補者は別のサーバーからのAppendEntries RPCを受信する可能性があります。自分がリーダーであると主張する場合。
このリーダーの任期（RPC に含まれる）は、候補者の現在の任期と同じかそれ以上である場合、候補者はリーダーを合法的なものとして認め、フォロワー状態に戻ります。
RPC の任期が候補者の現在の任期より小さい場合、候補者は RPC を拒否し、候補者状態に留まります。

一定の時間が経過しても誰も勝たなかった

候補者が選挙に勝たず、負けないという 3 番目の可能性があります：多くのフォロワーが同時に候補者になると、票が分割される可能性があり、
そのため、どの候補者も十分な投票を得ることができません。
この状況が発生した場合、各候補者はタイムアウトし、任期を増加させ、新しいRequestVote RPCを発信して新しい選挙を開始します。
ただし、追加の対策がない場合、split voteは無限に繰り返される可能性があります。

Raft はランダムな選挙タイムアウトを使用して、split voteが発生する可能性を低くし、迅速に解決します。
最初からsplit voteを防ぐために、選挙タイムアウトは固定の時間間隔（たとえば 150〜300ms）からランダムに選択されます。
これにより、各サーバーの選挙タイムアウトが異なるため、ほとんどの場合、1 つのサーバーだけがタイムアウトします。

もしサービスが選挙に勝った場合、他のサービスがタイムアウトする前にハートビートを送信します。split voteはこのようなメカニズムを使用して処理されます。
各候補者は選挙開始時にランダムな選挙タイムアウトをリセットし、タイムアウト後に次の選挙を開始します；
これにより、新しい選挙で再びsplit voteが発生する可能性が減ります。

選挙は、可理解性が設計のトレードオフにどのように導くかを示す例です。
最初はランクシステムを使用する予定でした：各候補者に一意のランクを割り当て、競争する候補者間で選択を行います。
候補者が別のより高いランクの候補者を発見した場合、フォロワーの状態に戻ります。これにより、より高いランクの候補者が次の選挙で勝ちやすくなります。
この方法は、可用性に関して微妙な問題を引き起こすことがわかりました（もし高いランクのサービスが故障した場合、低いランクのサーバーがタイムアウトして再び候補者になる可能性がありますが、早すぎると選挙の進行をリセットする可能性があります）。私たちはアルゴリズムを何度も調整しましたが、各調整後に新しい隅のケースが発生しました。
最終的に、ランダムな再試行の方法がより明確で理解しやすいという結論に達しました。

ログ複製#

リーダーが選出されると、クライアントのリクエストにサービスを提供し始めます。各クライアントのリクエストには、複製された状態機械が実行するコマンドが含まれています。
リーダーはそのコマンドを新しいエントリとしてログに追加し、他のすべてのサーバーに並行してAppendEntries RPCを発信してそのログを複製します。
エントリが安全に複製されると（後で説明します）、リーダーはそのログを状態機械に適用し、実行結果をクライアントに返します。
フォロワーがクラッシュしたり遅延したりする場合、またはネットワークパケットが失われた場合、リーダーは無限にAppendEntries RPCを再試行します（クライアントに応答した後でも）、
すべてのフォロワーが最終的にすべてのログエントリを保存するまで。

ログの組織方法は図 6に示されています。各ログエントリは状態機械コマンドを保存し、
リーダーがそのエントリを受け取ったときの任期番号を含みます。ログエントリ内の任期番号は、ログ間の不一致を検出するために使用され、
図 3のいくつかの属性を保証します。各ログエントリには、ログ内の位置を識別するための整数インデックスもあります。

リーダーは、ログエントリを状態機械に適用するのが安全なときを決定します。このようなエントリは_コミットされた_と呼ばれます。
Raft は、コミットされたエントリが永続化され、最終的にすべての利用可能な状態機械によって実行されることを保証します。
エントリを作成したリーダーがそのエントリを大多数のサーバーに複製すると、そのログエントリはコミットされます（たとえば、図 6 のエントリ 7）。
これにより、リーダーのログ内のすべての以前のエントリもコミットされます。
リーダーは、知っている最大のコミットインデックスを追跡し、将来のAppendEntries RPC（ハートビートを含む）でそのインデックスを含め、他のサーバーが最終的にそれを発見できるようにします。
フォロワーがログエントリがコミットされたことを知ると、そのエントリをローカル状態機械に適用します（ログの順序に従って）。

私たちが設計した Raft ログメカニズムは、異なるサーバー間のログの間で高い一貫性を維持します。これにより、システムの動作が簡素化され、予測可能性が向上し、安全性を確保する重要な要素となります。
Raft は以下の特性を維持し、これらは共同で図 3のLog Matching特性を構成します：

もし異なる 2 つのログが同じインデックスと任期を持っている場合

それらは同じコマンドを保存していると見なされます。
それらの以前のすべてのログも同じであると見なされます。

最初の属性は、リーダーが 1 つの任期内に 1 つのインデックスでのみログエントリを作成でき、ログエントリはログ内の位置を変更しないという事実に由来します。
2 番目の属性は、AppendEntries RPCが実行する単純な一貫性チェックによって保証されます。
AppendEntries RPCを送信する際、リーダーはそのログの新しいエントリの直前のエントリのインデックスと任期を含めます。
フォロワーがそのログ内に同じインデックスと任期を持つエントリを見つけられない場合、リーダーは新しいエントリを拒否します。
一貫性チェックは帰納的ステップのようなもので、ログの初期状態は確実にLog Matching属性を満たし、
ログが拡張されるたびに一貫性チェックがLog Matching属性を保持します。
したがって、AppendEntriesが成功して返されるたびに、リーダーはフォロワーのログが新しいエントリの前のリーダーのログと一致していることを知っています。

通常の動作中、リーダーとフォロワーのログは一致しているため、AppendEntriesの一貫性チェックは失敗しません。
ただし、リーダーがクラッシュすると、ログが不一致になる可能性があります（古いリーダーがそのログ内のすべてのエントリを完全に複製していない可能性があります）。
これらの不一致は、一連のリーダーとフォロワーのクラッシュの中で悪化する可能性があります。図 7 は、フォロワーのログが新しいリーダーのログと異なる可能性のある方法を示しています。

フォロワーはリーダーのエントリを失う可能性があります。
フォロワーはリーダーが持っていない追加のエントリを持つ可能性があります。
またはその両方の可能性があります。

ログ内の欠落したエントリや余分なエントリは、複数の任期にまたがる可能性があります。

Raft では、リーダーがフォロワーのログを自分のログに強制的に複製することによって、不一致の状況を処理します。これは、フォロワーのログ内の衝突エントリがリーダーのログ内のエントリによって上書きされることを意味します。次のセクションでは、これが安全であることを示します。

フォロワーのログをリーダーのログと一致させるために、リーダーは 2 つのログが一致する最新のログエントリを見つけ、そのポイント以降のフォロワーのログ内のすべてのエントリを削除し、
そのポイント以降のすべてのリーダーのエントリをフォロワーに送信する必要があります。これらの操作はすべて、AppendEntries RPCの一貫性チェックに応じて行われます。
リーダーは各フォロワーに対して nextIndex を維持し、これはリーダーがそのフォロワーに送信する次のログエントリのインデックスです。
リーダーが選出されると、すべての nextIndex の値を自分の最後のログのインデックス + 1 に初期化します（図 7 の 11）。
フォロワーのログがリーダーのログと一致しない場合、AppendEntriesの一貫性チェックは次のAppendEntries RPCで失敗します。
フォロワーが拒否した場合、リーダーは nextIndex の値を減少させ、AppendEntries RPCを再試行します。
最終的にnextIndexはリーダーとフォロワーのログが一致するポイントに達します。
この状況が発生すると、AppendEntriesは成功し、フォロワーのログ内の衝突エントリが削除され、リーダーログからエントリが追加されます（もしあれば）。
AppendEntriesが成功すると、フォロワーのログはリーダーのログと一致し、次の任期内にその状態を維持します。

必要に応じて、拒否されたAppendEntries RPCの数を減らすためにプロトコルを最適化できます。たとえば、AppendEntriesリクエストを拒否する際に、
フォロワーは衝突エントリの任期を含めることができます。それがその任期内に保存されている最初のインデックスです。
この情報を使用して、リーダーは nextIndex を減少させ、その任期内のすべての衝突エントリを回避できます；
各ログ衝突のある任期は、各ログエントリの RPC ではなく、1 つのAppendEntries RPCのみが必要です。
実際には、失敗がほとんど発生せず、多くの不一致エントリがある可能性は低いため、この最適化が必要かどうかは疑問です。

このメカニズムにより、リーダーは選出時にログの一貫性を回復するために特別な措置を講じる必要はありません。リーダーは通常通り動作を開始し、
ログは自動的にAppendEntriesの一貫性チェックの失敗に応じて収束します。
リーダーは自分のログ内のエントリを上書きしたり削除したりすることはありません（図 3のLeader Append-Only）。

理想的な Raft：

大多数のサーバーが起動すれば、Raft は新しいログエントリを受け入れ、複製し、適用できます。
新しいエントリをクラスタの大部分に単一の RPC で複製できます。
単一の遅いフォロワーはパフォーマンスに影響を与えません。

Safety#

前の章では、Raft がどのようにリーダーを選出し、ログを複製するかを説明しました。
しかし、これらのメカニズムだけでは、各状態機械が同じ順序で同じコマンドを実行することを保証するには不十分です。
たとえば、フォロワーが利用できない状態で（unavailable）、リーダーがいくつかのログをコミットし、その後リーダーとして選出され、これらのログを上書きする可能性があります；
その結果、異なる状態機械が異なるコマンドシーケンスを実行する可能性があります。

このセクションでは、どのサーバーがリーダーとして選出されるかに制限を追加することで Raft を強化します。
この制限により、リーダーは任意の特定の任期内に、以前の任期中にコミットされたすべてのログを保持することが保証されます（図 3のLeader Completeness Property）。
この選挙制限を追加することで、コミット時のルールをより正確にします。
最後に、Leader Completeness Propertyの簡単な証明を示し、正しい動作の複製状態機械をどのように導くかを説明します。

Election restriction#

リーダーベースのコンセンサスアルゴリズムでは、リーダーはコミットされたログを保存する必要があります。一部のコンセンサスアルゴリズム、たとえばViewstamped Replicationでは、
ノードはすべてのコミットされたログを含まなくてもリーダーとして選出されることができます。
これらのアルゴリズムには、失われたログを識別し、新しいリーダーに送信するための追加のメカニズムがあり、選挙中または選挙後すぐに行われます。
残念ながら、この方法はかなりの追加のメカニズムと複雑さを引き起こします。

Raft は、選挙時に新しいリーダーが以前の任期中にコミットされたすべてのログエントリを持つことを保証する、よりシンプルな方法を使用します。
これにより、これらのログエントリをリーダーに送信する必要がなくなります。これは、ログエントリの送信が一方向であり、リーダーからフォロワーにのみ行われ、
リーダーは自分のローカルログにすでに存在するエントリを上書きすることはありません。

Raft は、候補者が選挙に勝つのを防ぐために投票プロセスを使用します。候補者は、すべてのコミットされたエントリを含む必要があります。
候補者が選出されるためには、クラスタ内の大多数のノードに連絡する必要があります。これは、各コミットされたログがこれらのサービスのいずれかに少なくとも 1 つのノードに存在することを意味します。
候補者のログが大多数のログのいずれかと同じくらい新しい場合（“新しい” の定義は以下に示します）、それはすべてのコミットされたログを保持していることが保証されます。

RequestVote RPCの実装制限：RPC は候補者のログ情報を含み、もし投票者自身のログが候補者のログよりも新しい場合、
投票は拒否されます。

Raft は、最後のログのインデックスと任期を比較することで、2 つのログのどちらが新しいかを決定します。
最後のログの任期が異なる場合は、大きい方が新しいと見なされます。
ログが同じ任期を持つ場合、どちらのログが長いか（ログ配列の長さ？それともインデックスのサイズ？）が新しいと見なされます。

Committing entries from previous terms#

ログ複製で説明したように、
ログが大多数のノードに保存されると、リーダーはそのログが現在の任期内にコミットできることを知っています。
リーダーがログをコミットする前にクラッシュした場合、将来のリーダーはそのログの複製を完了しようとします。
ただし、リーダーは、前の任期のログが大多数のサーバーに保存されたときに必ずコミットされたと推測することはできません。
図 8 は、すでに大多数のノードに保存された古いログエントリが、将来のリーダーによって上書きされる可能性がある状況を示しています。

図 8 の問題を解消するために、Raft は、前の任期のログをコミットするために複製数を計算することは決してありません。
現在の任期のログエントリのみが、複製数を計算することでコミットされます；
現在の任期のログがこの方法でコミットされると、Log Matchingにより、以前のすべてのログエントリも間接的にコミットされます。
特定の状況では、リーダーが古いログがコミットされているかどうかを安全に知ることができます（たとえば、そのログがサーバーに保存されているかどうか）。
しかし、Raft は問題を簡素化するために、より保守的なアプローチを使用します。

リーダーが以前の任期のログを複製する際、Raft はすべてのログに元の任期番号を保持します。これはコミットルールに追加の複雑さをもたらします。
他のコンセンサスアルゴリズムでは、新しいリーダーが以前の任期のログを再複製する場合、現在の新しい任期番号を使用する必要があります。
Raft の方法は、時間とログの変化に伴ってログを維持するため、ログを識別しやすくなります。
さらに、他のアルゴリズムと比較して、Raft の新しいリーダーは、より少ないログエントリを送信する必要があります（他のアルゴリズムでは、コミットされる前に冗長なログエントリを送信して再番号付けする必要があります）。
ただし、これは実際にはあまり重要ではないかもしれません。なぜなら、リーダーの変更はほとんど発生しないからです。

フォロワーと候補者のクラッシュ#

フォロワーまたは候補者がクラッシュした場合、後続の RPC はすべて失敗します。
Raft の処理方法は無限に再試行し、後続のリクエストが成功するまで、これらのリクエストを再試行します。
もしノードが RPC リクエストを受信した後、まだ応答していないときにクラッシュした場合、再起動時に同じリクエストを再度受信します。
Raft の RPC はすべて冪等であるため、再試行は問題を引き起こしません