Raft 論文抄訳

以下は、Diego Ongaro 他による、In Search of an Understandable Consensus Algorithm 、USENIX ATC ’14 で発表、 の kanda.motohiro@gmail.com による抄訳です。Open access が、翻訳を公開する権利を許すのか、実は知らない。Raft 博士論文の抄訳も参照。そちらは、Creative Commons です。

This is a Japanese translation by kanda.motohiro@gmail.com of the portions of the paper "In Search of an Understandable Consensus Algorithm" by Diego Ongaro et al., presented at USENIX ATC ’14.

In Search of an Understandable

Consensus Algorithm

Diego Ongaro and John Ousterhout, Stanford University

https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro

This paper is included in the Proceedings of USENIX ATC ’14:

2014 USENIX Annual Technical Conference.

June 19–20, 2014 • Philadelphia, PA

978-1-931971-10-2

Open access to the Proceedings of

USENIX ATC ’14: 2014 USENIX Annual Technical

Conference is sponsored by USENIX.

In Search of an Understandable Consensus Algorithm

Diego Ongaro and John Ousterhout

Stanford University

概要

Raft は、複製されたログを管理するためのコンセンサスアルゴリズムです。それは、(multi-)Paxos に等しい結果を生成し、Paxos と同じくらい効率的です。しかし、その構造は Paxos とは違います。これにより Raft は、Paxos に比べてより理解可能となり、現実システムを作る上でのより良い基礎を提供します。理解可能性を高めるために、Raft は、リーダー選出、ログ複製、そして安全性などのコンセンサスの鍵となる要素を分離します。そして、考える必要のある状態数を減らすために、より強いコヒーレンシーを強制します。利用者からの結果は、Raft はPaxos よりも、学生にとって学ぶのがより簡単であることを示します。Raft はまた、クラスタメンバーシップを変えるための新しい機構を含みます。それは、安全性を保証するために、オーバーラップする過半数を使います。

１．はじめに

コンセンサスアルゴリズムは、マシンの集まりが、コヒーレントなグループとして動作し、そのメンバーのどれかが障害になっても動作し続けることを可能とします。このため、それは高信頼な巨大スケールのソフトウェアシステムを開発する上で鍵となる役割を果たします。Paxos [13, 14] はこの数十年にわたって、コンセンサスアルゴリズムの議論を独占してきました。コンセンサスのほとんどの実装は Paxos をベースとしているか、あるいはそれに影響されています。そして、Paxos はコンセンサスを生徒に教えるのに使われる主なビークルとなりました。

不幸にも、Paxos はとても理解がむつかしいです。それをよりアプローチ可能としようという試みはたくさんありますが。さらに、そのアーキテクチャは、現実的システムをサポートするためには複雑な変更を必要とします。その結果、システム開発者も生徒も、Paxos と格闘することになります。

私達自身も、Paxos と格闘した後、システム開発と教育のためにより優れた基礎を提供することのできる新しいコンセンサスアルゴリズムを見つけることに着手しました。私達のアプローチは、その主なゴールが、理解可能性であるという点で特別です。現実システムのためのコンセンサスアルゴリズムを定義して、それをPaxos よりもずっと学ぶのが簡単な方法で説明できるでしょうか？さらに、私達はそのアルゴリズムがシステム開発者にとって必須である直感の開発を容易とすることも求めました。アルゴリズムがうまく働くことは大切ですが、なぜそれが働くのかが自明であることも大切です。

この研究の結果は、Raft と呼ばれるコンセンサスアルゴリズムです。Raft を設計する中で私達は、理解可能性を高めるための独特の技術を使いました。それは、分割（Raft はリーダー選出、ログ複製、そして安全性を分離します）と状態空間を減らすこと（Paxos に比べ、Raft は非決定性の割合を減らし、サーバがお互いに矛盾した状態になる可能性を減らしています）です。二つの大学で４３人の利用者を使った実験では、Raft は Paxos に比べて大いに理解が簡単であることを示しました。両方のアルゴリズムを読んだ後、３３人の学生は、Raft に関する質問に、Paxos に関する質問よりも良く答えることができました。

Raft は多くの点で、既存のコンセンサスアルゴリズムに似ています（最も顕著には、Oki and Liskov’s Viewstamped Replication [27, 20]）。しかし、いくつかの新規な機能もあります。

・強いリーダー：Raft は他のコンセンサスアルゴリズムよりも強い形式のリーダーシップを使います。例えば、ログエントリはリーダーから他のサーバにだけ流れます。これは複製されたログの管理を単純にし、Raft を理解しやすくします。

・リーダー選出：Raft はリーダーを選ぶのに、乱数化されたタイマーを使います。これは、全てのコンセンサスアルゴリズムが既に必要とするハートビートに、小さな機構を追加するだけです。その一方、競合を単純で迅速に解決します。

・メンバーシップ変更：Raft は、クラスタ内のサーバのセットを変えるために、新しい joint consensus アプローチを使います。そこでは、遷移の間、二つの異なる構成の過半数はオーバーラップします。これによってクラスタは、構成変更の間も通常の運用を続けられます。

私達は Raft が、教育目的と実装のための基礎の両方において、Paxos や他のコンセンサスアルゴリズムよりも優れていると信じます。それは他のアルゴリズムよりもより単純で、より理解可能です。それは現実システムの要求を満足するのに十分なほど完全に記述されています。それはいくつかのオープンソース実装を持ち、いくつかの会社で使われています。その安全性の属性は形式的に記述され、証明されています。そしてその効率は他のアルゴリズムに並ぶものです。

２．複製された状態マシン

３．Paxos の何が悪いのか？

４．理解可能性をめざす設計

５．Raft コンセンサスアルゴリズム

Raft は、２節で述べた形式の複製されたログを管理するためのアルゴリズムです。図２は、アルゴリズムを、レファレンスのための凝縮された形式で概説します。そして図３はアルゴリズムの鍵となる属性を列挙します。これらの図の中の要素は、この節の残りを通して、一つづつ説明します。

Raft は最初に明らかなリーダーを選出し、次にそのリーダーに複製されたログを管理するための完全な責任を与えることによってコンセンサスを実装します。リーダーはクライアントからログエントリを受け付け、それらを他のサーバに複製し、そしてログエントリをサーバの状態マシンに適用することが安全である時を伝えます。一つのリーダーを持つことは、複製されたログの管理を簡単にします。例えば、リーダーは新しいエントリをログのどこに置くかを他のサーバに接触することなく決めることができます。データは、リーダーから他のサーバという、単純な形式で流れます。リーダーは落ちたり、他のサーバから切断されることがあります。その場合、新しいリーダーが選出されます。

リーダーアプローチを取ることで、Raft はコンセンサス問題を、三つの比較的独立した副次問題に分解します。今後の節でそれらを議論します。

・リーダー選出：既存のリーダーが落ちたら、新しいリーダーを選ぶ必要があります。（５．２節）

・ログ複製：リーダーはログエントリをクライアントから受け付け、それらをクラスタ内に複製する必要があります。自分自身のログと、他のログが一致するように強制します。（５．３節）

・安全性：Raft の鍵となる安全性の属性は、図３の State Machine Safety 属性です。もしもあるサーバが特定のログエントリを自分の状態マシンに適用したならば、いかなる他のサーバもその同じログインデックスにはそれと異なるコマンドを適用することはできません。５．４節は、Raft がどのようにこの属性を満足させるかを述べます。解決策は、５．２節で述べた選出機構に新たな制約をもたらします。

コンセンサスアルゴリズムを提示した後、この節は可用性の問題と、システムでのタイミングの役割を議論します。

５．１ Raft の基本

Raft クラスタはいくつかのサーバを含みます。５つが、典型的です。その場合、システムは２つが落ちても耐えられます。いかなる時も、それぞれのサーバは以下の三つの状態のどれかにあります。リーダー、フォロワー、そして候補者です。正常な運用では、一つのリーダーだけが存在し、残りの全てのサーバはフォロワーです。フォロワーは受動的です。自分では何も要求を出さず、単純に、リーダーと候補者からの要求に答えます。リーダーは全てのクライアント要求を処理します。（もしクライアントがフォロワーに接触したら、フォロワーはそれをリーダーに転送します。）３つめの状態である候補者は、５．２節で述べる、新しいリーダーを選出するときに使われます。図４はこれらの状態とその遷移を示します。遷移は、以下で議論します。

図５に示すように、Raft は、時間を任意の長さのタームに分割します。タームは連続する整数で数えられます。それぞれのタームは選出で始まります。一つ以上の候補者が、５．２節に述べるように、リーダーになろうと試みます。候補者が選出に勝ったら、それはそのタームの残りの間、リーダーとして機能します。場合によっては、選出の結果、投票が分かれることがあります。この場合は、タームはリーダーなしに終わり、じきに新しいターム（新しい選出を伴い）が始まります。Raft はあるタームには最大一つのリーダーがいることを保証します。

異なるサーバは、ターム間の遷移を異なる時間に観測するかもしれません。また、サーバが選出を観測しなかったり、ターム全体を見ないこともあります。タームは Raft において、logical clock [12] としてはたらきます。それはサーバが、無効なリーダーのような、古い情報を検出するのを助けます。それぞれのサーバは、現在ターム番号を格納します。それは、時とともに単調増加します。現在タームは、サーバたちが通信するときに常に交換されます。もしあるサーバの現在タームが他のより小さい時は、それは自分の現在タームをより大きい方に更新します。もし候補者かリーダーが自分のタームが古いことを見つけたら、それは直ちに、フォロワー状態に戻ります。もしサーバが無効なターム番号を持つ要求を受信したら、それはその要求を捨てます。

Raft サーバは、遠隔手続き呼び出し remote procedure call (RPC) を使って通信します。コンセンサスアルゴリズムは二つのタイプの RPC しか必要としません。候補者は、選出の間、RequestVote RPC を発行します（５．２節）。そして、リーダーはログエントリを複製し、ある種のハートビートを提供するために、AppendEntries RPC を発行します（５．３節）。サーバは、応答を適当な時間内に受け取らない場合は、RPC をリトライします。そして、最高性能のために、RPC を並行して発行します。

５．２ リーダー選出

Raft は、リーダー選出をトリガーするために、ハートビート機構を使います。サーバが開始した時、それはフォロワーとして始まります。サーバは、それが有効な RPC をリーダーあるいは候補者から受け取る間ずっと、フォロワー状態にとどまります。リーダーは定期的なハートビート（ログエントリを持たない AppendEntries RPC）を全てのフォロワーに対して送り、自分の権威を維持します。

もし、フォロワーが、選出タイムアウトと呼ばれる時間内に、通信を受けない時は、有効なリーダーがいないと推測して、新しいリーダーを選ぶための選出を始めます。

選出を始めるため、フォロワーは自分の現在タームを加算し、候補者状態に遷移します。次にそれは、自分に投票し、クラスタ内の他のサーバに並行して、RequestVote RPC を発行します。候補者は、以下の三つのうちどれかが起きるまで、この状態にとどまります。(a) 自分が選出に勝つ。(b) 他のサーバが、リーダーになる。あるいは、(c) 勝者のいないまま、一定時間が過ぎる。これらの結果は以下のパラグラフで別々に議論します。

候補者は、同じタームにおいて完全なクラスタのサーバの過半数から投票を受けたら、選出に勝ちます。それぞれのサーバはあるターム内では最大一つの候補者にだけ投票します。それは、最初に来たものが最初に応答されるように行われます（注意：５．４節は、投票に追加の制約を加えます。）過半数規則は、あるターム内では最大一つの候補者だけが選出に勝つことができる（図３の Election Safety 属性）ことを保証します。候補者が選出に勝ったら、それはリーダーになります。それは他の全てのサーバにハートビートメッセージを送り、自分の権威を確立し、新しい選出を防ぎます。

投票を待っている間、候補者はリーダーを自称する他のサーバから、AppendEntries RPC を受けるかもしれません。もしそのリーダーのターム（その RPC 内に含まれます）が候補者の現在ターム以上であるならば、候補者はそのリーダーを正当であるとみなし、フォロワー状態に戻ります。もし RPC にあるタームがその候補者の現在タームよりも小さいならば、候補者はその RPC を捨て、候補者状態にとどまります。

３つめの可能な結果は、候補者が選出に勝ちも負けもしないことです。もし同時に多くのフォロワーが候補者になったならば、投票は分かれ、どの候補者も過半数を得ないでしょう。これが起きたら、それぞれの候補者はタイムアウトして、自分のタームを加算し、RequestVote RPC のラウンドをもう一度始めることで新しい選出を始めます。しかし、何か手を講じない限り、過半数に満たない投票は永遠に続くかもしれません。

Raft は、乱数化された選出タイムアウトを使って、過半数に満たない投票がまれであり、素早く解決されることを保証します。そもそも、過半数に満たない投票を防ぐために、選出タイムアウトは固定の間隔（例えば、150–300ms）からランダムに選ばれます。これはサーバ間にひろがっているので、ほとんどの場合には一つのサーバだけがタイムアウトします。それは、他のどのサーバがタイムアウトするよりも早く選出に勝ち、ハートビートを送ります。同じ機構を、過半数に満たない投票を処理するために使います。それぞれの候補者は選出の開始で、自分の乱数化された選出タイムアウトを再開始します。そして次の選出を始めるまでに、そのタイムアウトが過ぎるのを待ちます。これによって、新しい選出において、また、過半数に満たない投票が起きる可能性を減らします。８．３節は、このアプローチがリーダーを迅速に選出することを示します。

選出は、理解可能性がいかに私達の設計の選択に影響したかを示す例です。最初私達は、ランク付けシステムを使おうとしました。それぞれの候補者は一意のランクを与えられます。候補者がより高いランクの他の候補者を見つけたら、それはフォロワーに戻り、より高いランクの候補者が次の選出により簡単に勝つことができます。私達は、このアプローチが可用性の微妙な問題を起こすことに気が付きました（より低いランクのサーバは高いランクのサーバが落ちた時に、タイムアウトしてもう一度候補者になる必要があるかもしれません。しかしそれがあまりにもすぐにそうすると、リーダーを選出するための進行をリセットするかもしれません。）。私達はアルゴリズムに何度か調整をしました。しかし、調整のたびに、新しいまれな問題ケースが見つかりました。最終的に私達は、乱数化されたリトライアプローチが、最も明瞭で理解可能であると結論づけました。

５．３ ログ複製

リーダーは選出された後、クライアント要求を処理し始めます。それぞれのクライアント要求は、複製された状態マシンによって実行されるべきコマンドを持っています。リーダーはそのコマンドを自分のログに、新しいエントリとして追加し、AppendEntries RPC を他のサーバのそれぞれに並列に発行し、そのエントリを複製させます。エントリが安全に複製された（以下に説明します）後、リーダーはそのエントリを自分の状態マシンに適用して、その実行の結果をクライアントに戻します。フォロワーがクラッシュした時、実行が遅い時、あるいはネットワークパケットが失われた時、リーダーは無限に AppendEntries RPC をリトライします。（リーダーがクライアントに応答した後でも）それは、全てのフォロワーが最終的に全てのログエントリを格納するまで続きます。

ログの構造を図６に示します。それぞれのログエントリは状態マシンコマンドとともに、そのエントリがリーダーによって受信されたターム番号を格納します。ログエントリ中のそのターム番号は、ログの間の矛盾を検出し、図３のいくつかの属性を保証するために使われます。それぞれのログエントリは、ログの中でのその位置を示す整数インデックスも持ちます。

リーダーは、いつログエントリを状態マシンに適用するのが安全であるのかを決めます。そのようなエントリは、コミット済みと呼ばれます。Raft はコミット済みエントリが永続的であり、最終的には全ての使用可能な状態マシンによって実行されることを保証します。ログエントリは、そのエントリを作成したリーダーが、それを過半数のサーバに複製した時にコミットされます（例えば、図６のエントリ７）。これは同時に、そのリーダーのその前にある全てのエントリを含みます。それは、以前のリーダーが作成したエントリも含みます。５．４節は、リーダーが変わった後にこの規則を適用するときに起きる微妙な問題を議論します。また、このコミットメントの定義が安全であることを示します。リーダーはそれがコミット済みであることを知っている、最大のインデックスを追跡しています。そして、そのインデックスを将来の AppendEntries RPC （ハートビートを含みます）に含めます。そうすれば、他のサーバはいずれ気が付きます。フォロワーがあるログエントリがコミットされたことを知ったら、それはそのエントリを自分のローカルな状態マシンに適用します（ログの順序で）。

私達は、Raft のログ機構を、異なるサーバ間で高レベルのログのコヒーレンシーを維持するように設計しました。これはシステムのふるまいを単純にしてより予測可能としただけではなく、安全性を保証するための重要なコンポーネントでした。Raft は以下の属性を維持します。それは全部合わせて、図３の Log Matching 属性を構成します。

・もし異なるログの二つのエントリが同じインデックスとタームを持つなら、それらは同じコマンドを格納します。

・もし異なるログの二つのエントリが同じインデックスとタームを持つなら、その前の全てのエントリは、二つのログの間で同じです。

最初の属性は、リーダーがあるタームのあるログインデックスに対して、最大でも一つのエントリしか作らない事実と、ログエントリはログ中での自分の位置を決して変えない事実から導かれます。２つめの属性は、AppendEntries が実行する単純な一貫性チェックによって保証されます。AppendEntries RPC を送るとき、リーダーはその新しいエントリのログ中で一つ前のエントリのインデックスとタームを含めます。フォロワーが自分のログ中で同じインデックスとタームを持つエントリを見つけられない場合、それは新しいエントリを拒否します。一貫性チェックは、帰納ステップとしてはたらきます。ログの最初の空の状態は Log Matching 属性を満足します。そして、一貫性チェックは、ログが増えるときには必ず Log Matching 属性を維持します。この結果、AppendEntries が成功を返すときには必ず、リーダーはフォロワーのログが、その新しいエントリのところまで、自分自身のログと同じであることがわかります。

通常の運用の間、リーダーとフォロワーのログは一貫したままです。なので、AppendEntries の一貫性チェックは決して失敗しません。しかしリーダーのクラッシュはログを異なる状態にするかもしれません（古いリーダーは自分のログの全てのエントリを完全には複製していないかもしれません）。これらの矛盾はリーダーとフォロワーのクラッシュが続くにつれて蓄積するかもしれません。図７はフォロワー達のログが新しいリーダーのログと異なることがある状況を説明します。フォロワーはリーダーにあるエントリを持たないかもしれません。リーダーにない余分なエントリを持つかもしれません。それとも両方。ログ中で、無いエントリと余分なエントリは複数のタームにまたがるかもしれません。

Raft では、リーダーはフォロワーのログに自分自身のログを強制的に複製することによって矛盾を処理します。これは、フォロワーのログ中の競合するエントリはリーダーのログのエントリによって上書きされることを意味します。５．４節は、もうひとつの制約を組み合わせた時に、これが安全であることを示します。

フォロワーのログを自分自身のログと一貫した状態にするために、リーダーは二つのログが合意する最も新しいログエントリを見つけなくてはいけません。そしてフォロワーのログでその位置より後にある全てのエントリを削除し、そのフォロワーに、その位置より後のリーダーの全てのエントリを送ります。これらのアクションは全て、AppendEntries RPC が実行する一貫性チェックに対応して行われます。リーダーはフォロワーのそれぞれに、nextIndex を維持します。それは、リーダーがそのフォロワーに送る予定の次のログエントリのインデックスです。リーダーが最初に電源が入った時それは全ての nextIndex 値を、自分自身のログの最後のものの一つ後のインデックス（図７の１１）に初期化します。フォロワーのログがリーダーのものと矛盾している時、次の AppendEntries RPC において AppendEntries 一貫性チェックは失敗します。拒否の後、リーダーは nextIndex を減算して AppendEntries RPC をリトライします。最終的に、nextIndex はリーダーとフォロワーのログが一致する地点に達するはずです。これが起きたら、AppendEntries は成功するでしょう。その結果、フォロワーのログから競合する全てのエントリを削除し、リーダーのログからエントリを（もしあれば）追加します。AppendEntries が一度成功したら、フォロワーのログはリーダーのログと一貫しており、そのタームの終わりまでそうであり続けるでしょう。

プロトコルを最適化して、拒否される AppendEntries RPC の数を減らすことができます。詳しくは、 [29] を参照下さい。

この機構により、リーダーは電源が入った時に、ログの一貫性を回復するために何らかの特別なアクションを取る必要はありません。それは通常処理を始めるだけです。そしてログは、AppendEntries 一貫性チェックの失敗を通して自動的に収束していきます。リーダーは自分自身のログにあるエントリを決して、上書きしたり削除したりはしません（図３の、Leader Append-Only 属性）。

このログ複製機構は、２節で述べた望ましいコンセンサス属性を示します。Raft は、サーバの過半数がアップである限り、新しいログエントリを受け付け、複製し、適用することができます。通常の場合、新しいエントリは、クラスタの過半数との１ラウンドの RPC で複製できます。そして、遅いフォロワーが一ついても、性能に影響しません。

５．４ 安全性

これまでの節は、Raft がどのようにリーダーを選出し、ログエントリを複製するかを述べました。しかし、今まで述べた機構は、それぞれの状態マシンが正確に同じ順序で同じコマンドを実行することを保証するためには全く不十分です。例えば、リーダーがいくつかのログエントリをコミットする間、あるフォロワーは落ちているかもしれません。次に、それがリーダーに選出されて、それらのエントリを新しいもので上書きするかもしれません。この結果、異なる状態マシンは異なるコマンドのシーケンスを実行するかもしれません。

この節は、サーバがリーダーに選出されることができるための制約を加えることで、Raft アルゴリズムを完成させます。この制約は、どのタームのリーダーであっても、以前のタームでコミットされた全てのエントリを含むことを保証します（図３の、Leader Completeness 属性）。この選出の制約を得て、私達は、コミットメントの規則をより正確にします。最後に、私達は、Leader Completeness 属性の証明のスケッチを示して、それがどのように複製された状態マシンの正しいふるまいに導くかを示します。

５．４．１ 選出の制約

リーダーをベースとするコンセンサスアルゴリズムではどれでも、リーダーは最終的にはコミットされた全てのログエントリを格納しなくてはいけません。Viewstamped Replication [20] のようなある種のコンセンサスアルゴリズムでは、リーダーはそれが最初は、コミットされた全てのログエントリを持っていなくても選出されることがあります。これらのアルゴリズムは、失われたエントリを特定して新しいリーダーにそれらを送るための追加の機構を含みます。それは選出プロセスの間か、その後しばらくして行われます。不幸にも、これはかなりの追加の機構と複雑さをもたらします。Raft はより単純なアプローチを使い、以前のタームからのコミットされた全てのエントリは新しいリーダーが選出された瞬間から、リーダーのところに存在することを保証します。エントリをそのリーダーに転送する必要はありません。これは、ログエントリがリーダーからフォロワーへと一方向にだけ流れることを意味します。そしてリーダーは自分のログの既存のエントリを決して上書きしません。

Raft は投票プロセスを使って、候補者が、そのログがコミットされた全てのエントリを含まない限り、選出に勝てないようにします。候補者は選出されるためにはクラスタの過半数に接触する必要があります。それは、コミットされた全てのエントリはこれらサーバの少なくても一つには存在するはずであることを意味します。もし候補者のログがその過半数の他のログよりも少なくてもより、アップツーデートであるならば（「アップツーデート」の定義は、以下で正確にします。）それはコミットされた全てのエントリを持っているはずです。RequestVote RPC はこの制約を実装します。この RPC は候補者のログに関する情報を含み、投票者はもし自分のログが候補者のそれよりもよりアップツーデートであるならば、投票を拒否します。

Raft は、二つの、ログのどちらがよりアップツーデートであるかを、ログの最後のエントリのインデックスとタームを比べて決めます。もしログが異なるタームを持つ最後のエントリを持てば、より新しいタームを持つ方のログがよりアップツーデートです。もしログが同じタームで終わるならば、より長い方のログがよりアップツーデートです。

５．４．１ 以前のタームのエントリをコミットする

５．３節で述べたように、リーダーは自分の現在タームのエントリは、それがサーバの過半数に格納されたならばコミット済みとわかります。もしリーダーがエントリをコミットする前にクラッシュしたら、未来のリーダーはそのエントリの複製を終わらせようと試みます。しかし、リーダーは以前のタームのエントリがサーバの過半数に格納されたからと言って、直ちにコミット済みと結論できません。図８は、古いログエントリがサーバの過半数に格納されていても、未来のリーダーによって上書きれることがある状況を示します。

図８にあるような問題を除くために、Raft は、以前のタームのログエントリを、複製を数えることによってコミットすることは決してありません。複製を数えることでコミットできるのは、そのリーダーの現在タームのログエントリだけです。このように現在タームのエントリがコミットされたら、Log Matching 属性のために、それ以前の全てのエントリは間接的にコミットされます。リーダーが、より古いログエントリがコミット済みであると安全に結論できる状況はいくつかありますが（例えば、そのエントリが全てのサーバに格納されていれば）、Raft は簡単のため、より保守的なアプローチを取ります。

Raft はこの余分な複雑さを、コミットメント規則に引き受けます。リーダーが以前のタームからのログエントリを複製する場合、ログエントリはそれらのオリジナルのターム番号を保持するからです。他のコンセンサスアルゴリズムでは、もし新しいリーダーが以前の「ターム」からエントリを複製する時は、自分の新しい「ターム番号」を使ってそうしなければいけません。Raft のアプローチは、ログエントリについて推測するのをより簡単にします。それらは、時間に渡り、複数のログに渡り、同じターム番号を維持するからです。それに、Raft の新しいリーダーは、他のアルゴリズムに比べて、以前のタームからのログエントリをより少なく送ります（他のアルゴリズムはログエントリをコミットする前に、番号を付け替えるために冗長なログエントリを送らなくてはいけません。）。

５．４．３ 安全性の議論

完全な Raft アルゴリズムを得たので、私達は、Leader Completeness 属性が満たされることをより正確に議論できます（この議論は、安全性の証明をベースとします。８．２節を参照下さい。）。Leader Completeness 属性が満たされないと仮定しましょう。そして、矛盾を示します。ターム T (leader T )のリーダーが自分のタームのログエントリをコミットしたとします。しかしそのログエントリはある未来のタームのリーダーによっては格納されませんでした。そのタームのリーダー (leader U ) がそのエントリを格納しなかった最小のターム  U > T  を考えましょう。

１．leader U の選出の時、コミット済みエントリは leader U のログには存在しなかったはずです（リーダーはエントリを削除したり上書きしたりはしません）。

２．leader T はクラスタの過半数にそのエントリを複製しました。そして、leader U はクラスタの過半数から投票をもらいました。このため、図９が示すように、少なくても一つのサーバ（“the voter”）は leader T からのエントリをアクセプトし、かつ、leader U に投票したはずです。この voter が矛盾に導く鍵です。

３．voter は leader U に投票する前に、leader T からのコミット済みエントリをアクセプトしたはずです。そうでなければ、それは leader T からの AppendEntries 要求を拒否したはずです（その現在タームは T よりも大きいはずですから）。

訳注。leader U に投票した後、leader T からのログはアクセプトできません。Uのタームにいるから古い T のタームのRPCは捨てます。

４．voter はそれでも、それが leader U に投票した時には、エントリを格納していました。なぜならば、全ての途中に入ったリーダーはそのエントリを持っており（仮定により）、リーダーは決してエントリを削除せず、フォロワーはリーダーと競合した時にだけエントリを削除するからです。

５．voter は、leader U に投票しました。なので、leader U のログは voter と同じくらいアップツーデートであったはずです。これは、二つの矛盾のどちらかを導きます。

６．まず、voter と、leader U の最後のログタームが同じだったとしましょう。すると、leader U のログは voter のログ以上の長さがあったはずです。なので、そのログは voter のログの全ての、エントリを含みます。これは矛盾です。なぜならば、voter はコミット済みエントリを含み、仮定により leader U はそれを持たないからです。

７．そうでないとすると、leader U の最後のログタームは voter のそれよりも大きかったはずです。さらに、それは T より大きいです。voter の最後のログタームは T 以上ですから（それはターム T のコミット済みログエントリを持ちます）leader U の最後のログエントリを作った以前のリーダーは自分のログにそのコミット済みエントリを持っていたはずです（仮定により。それが U の定義です。）すると、Log Matching 属性により、leader U のログもコミット済みエントリを含まなければならず、これは矛盾です。

８．これで矛盾の説明を終わります。なので、T より大きいタームの全てのリーダーはターム T でコミットされたターム T からの全てのエントリを含まなければいけません。

９．Log Matching 属性により、未来のリーダーも、図8(d) のインデックス２のように、間接的にコミットされたエントリを含むことが保証されます。

Leader Completeness 属性が与えられたならば、図３の State Machine Safety 属性と、全ての状態マシンが同じログエントリを同じ順序で適用することを証明するのは容易です（[29] を参照）。

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

今まで私達は、リーダーの障害に集中してきました。リーダーのクラッシュに比べて、フォロワーと候補者のクラッシュはずっと扱いが単純です。どちらも同じ方法で処理できます。もしフォロワーか候補者がクラッシュしたら、それに送られる将来の RequestVote と AppendEntries RPC は失敗します。Raft は無限にリトライすることでこれらの障害に対処します。もしクラッシュしたサーバが再開始したら、その RPC は成功するでしょう。もしサーバが、RPC を完了したけど応答を送る前にクラッシュしたら、それは再開始した後、同じ RPC を受けます。Raft の RPC はべき等なので、これは問題を起こしません。例えば、もしフォロワーが自分のログに既にあるログエントリを含む AppendEntries 要求を受けたら、それは新しい要求の中でそれらのエントリを無視します。

５．６ タイミングと可用性

６．クラスタメンバーシップ変更

訳注。この USENIX 版の論文で提案されている、C old,new というジョイントコンセンサスを使う方法は、Raft 博士論文の方では、「複雑な割に、実用的でない」と否定されています。代わりに、サーバの増減は一度に一つだけ、にする方法が提案されています。

７．クライアントとログ圧縮

８．実装と評価

９．関連する研究

１０．結論

１１．謝辞

参考文献

訳注。これは、図２です。 Google site に置く都合で、レイアウトは原文とは違います。この図が全部わかれば、Raft 合格です。

状態

 全てのサーバにおける永続的状態：（RPC に応答する前に、ステーブル記憶域上で更新されます）

 全てのサーバにおける揮発的状態：

リーダーにおける揮発的状態：（選出の後、再初期化されます）

受信者の実装：

1. もし term < currentTerm ならば、偽を返します(§5.1)

2. もし votedFor が null もしくは candidateId であり、 候補者のログが、受信者のログと同じくらいアップツーデートならば、投票を与えます (§5.2, §5.4)

サーバの規則

全てのサーバ：

• もし commitIndex > lastApplied:  lastApplied を加算し、log[lastApplied] を状態マシンに適用します (§5.3)

• もし RPC 要求あるいは応答に含まれる T > currentTerm:

currentTerm = T に設定して、フォロワーになります (§5.1)

フォロワー(§5.2):

• 候補者とリーダーからの RPC に応えます

• もし、現在のリーダーからの AppendEntries RPC を受信するか、あるいは、候補者に投票を与えることなく、選出タイムアウトが過ぎたならば：

候補者になります

候補者 (§5.2):

• 候補者になったら選出を始めます

    • currentTerm を加算します

    • 自分に投票します

    • 選出タイマーをリセットします

    • 全ての他のサーバに RequestVote RPC を送ります

• 過半数のサーバから投票を得たら：リーダーになります

• 新しいリーダーからの AppendEntries RPC を受けたら：フォロワーになります

• 選出タイムアウトが過ぎたら：新しい選出を始めます

リーダー：

• 選出されたら：最初の空の AppendEntries RPC （ハートビート）をそれぞれのサーバに送ります。アイドル期間の間繰り返して、選出タイムアウトを避けます。(§5.2)

• クライアントからコマンドを受けたら：エントリをローカルなログに追加します。エントリが状態マシンに適用された後、応答します (§5.3)

• もしあるフォロワーに対して、最後のログのインデックス  ≥ nextIndex[そのフォロワー] ならば：nextIndex から始まるログエントリを持つ AppendEntries RPC を送ります

    • 成功したら： そのフォロワーに対する nextIndex and matchIndex を更新します(§5.3)

    • ログの矛盾のために AppendEntries が失敗したら： nextIndex を減算してリトライします (§5.3)

• 以下の条件を満たす N があれば、commitIndex = N に設定します

N > commitIndex,

過半数の matchIndex[i] ≥ N,

log[N].term == currentTerm

(§5.3, §5.4).

訳注。これが、過半数の複製を作ることに成功して、リーダーの状態マシンにログが適用され、クライアントにコマンド応答を返すことのできる契機です。

図２：Raft コンセンサスアルゴリズムの凝縮されたまとめ（メンバーシップ変更とログ圧縮を除く）。右下の箱のサーバのふるまいは、独立して、繰り返しトリガーされる規則のセットとして記述されています。§5.2 のような節の番号はその特定の機能を議論しているところを示します。形式的仕様[28]は、このアルゴリズムをより正確に記述します。

Election Safety: あるターム内では、最大でも一つのリーダーしか選出されることができません。 §5.2

Leader Append-Only: リーダーは自分のログ内で、決してエントリを上書きしたり削除したりしません。それは新しいエントリを追加するだけです。 §5.3

Log Matching: もし二つのログが同じインデックスとタームを持つエントリを含むならば、そのログは、そのインデックスまでの全てのエントリが等しいです。 §5.3

Leader Completeness: もしあるログエントリがあるタームでコミットされたら、そのエントリは、全てのより大きい番号を持つタームにおいて、その時のリーダーのログ中に存在するでしょう。 §5.4

State Machine Safety: もしあるサーバがあるインデックス位置にあるログエントリを自分の状態マシンに適用したならば、他のどのサーバも、異なるログエントリをその同じインデックスに適用することは決してありえません。§5.4.3

図３：Raft はこれらの属性が常に正しいことを保証します。示された節の番号は、それらの属性を議論しているところを示します。

以下、私による、問いと答え

問い：自分がリーダーであることは、ディスクに覚えてなくてもいいのですか。

答え：はい。リーダーが落ちて上がり直した時にするべきことは特にありません。ハートビートが聞こえなければ、立候補するだけです。かつて自分がリーダーであったことは関係ありません。むしろ、落ちていた間にあなたはログエントリをミスしているので、投票に負ける可能性が高いです。

問い：リーダーは、何をどこまでやったか、つまり、インデックスとそれぞれのサーバとの交渉進捗をディスクに覚えてなくてもいいのですか。

答え：はい。同じ情報は、フォロワーの log[] 永続的状態にあります。AppendEntries RPC の拒否とリトライによって、フォロワーとリーダーの状態は同期します。

問い： log[] 以外の永続状態はリーダー選出が起きないと更新されません。これは、Raft プロトコル処理のためのディスクフォースは通常運転時は無いということですか。素晴らしい。

答え：はい。

問い：リーダーが、どこまでコミットしたかをディスクに覚えなくてもいい理由がわかりません。古典的な二相コミットの苦労はなんだったのですか。

答え：コミットしていないログエントリは、クライアントにライト完了を返してないので、捨てることができます。リーダーにあるログエントリが大切かどうかは、それをたくさんのフォロワーが持っているかでわかります。

問い：過半数を得る前にリーダーが落ちたら、そのコマンドは、クラスタ全体で無かったことになりますよね。

答え：いいえ。リーダーはログに書いたとします。

複製を書いてない人が新しいリーダーになったら、AppendEntries RPC の拒否とリトライによって、そのコマンドのログエントリは全てのサーバで消えます。

書いた人、元のリーダーも含む、が新しいリーダーになったら、同じ RPC によってログエントリはクラスタ全体に拡散します。

クライアントには応答を返してないので、どっちになっても、仕様です。

問い：ログ複製以外のコンセンサスにも使えますか？

問い：なぜ、Paxos と違って、一つのラウンドトリップで済むのですか？

答え１：プロポーザの提案は、最強であることが既に合意されているから。

答え２：Multi-Paxos は、リーダーが決まっていて、アクセプトの一つのラウンドトリップで済みます。

答え３：フォロワーは AppendEntries RPC を受けて、応えて、リーダーが過半数を得て、次のハートビートに、増えた leaderCommit  が入ってくるので、フォロワーは初めて、コミットつまり、状態マシンに新しい値を反映できる。二つのラウンドトリップと言える。

問い：古典的な二相コミットは Raft に乗りますか？

問い：クライアントからのライトは必ずリーダーが処理しなくてはいけないというのは、負荷集中を招く、プロトコルの欠点ではないですか。

問い：フォロワーが積極的にリーダー権限を奪うしかけは無いのですか。

私の答え：あるフォロワーが、ハートビートが聞こえないふりをして、立候補します。その間に、元のリーダーがクライアントからの新しい要求を受けていないなら、ログの長さは候補者と変わらないので、先に言ったもの勝ちで、候補者は新しいリーダーになれます。

答え：Raft 論文の方に書いてありました。3.10 Leadership transfer extension

TimeoutNow というメッセージを、リーダーが投げると、受けたフォロワーは即座に立候補します。etcd 実装では、TransferLeader メッセージと呼ばれます。

問い：クライアントは、リーダー以外のサーバから読むことはできますか。

リーダーが過半数のサーバからの AppendEntries RPC 応答を得たら状態マシンに新しい値を反映することができるということは、古い値を持っているサーバに行ったクライアントはどうなりますか。

答え：古い値を読むのは仕様です。それは複製とレイヤーが違う、トランザクションの話です。古典的な二相ロックならば、アプリケーションは更新を始める前にトランザクションを開始し、対象のレコードをロックして、他のトランザクションから見えなくします。トランザクションのコミットはアンロックを伴うので、更新後の値が見えるようになります。

古い値を持っているサーバはアンロックをしてないので、

＃ あれ、Raft とどうつながるの？

更新を開始した後は古い値はどこのサーバからも読めなくなります。

Raft クイズもやってみましょう。

以下の Ousterhout 先生のビデオ、おすすめです。一時間ほどで、英語もとても聞き取りやすいです。

https://www.youtube.com/watch?v=JEpsBg0AO6o

https://www.youtube.com/watch?v=YbZ3zDzDnrw

以上