raft 博士論文の抄訳

以下は、Diego Ongaro による、Consensus: Bridging Theory and Practice の kanda.motohiro@gmail.com による抄訳です。Creative Commons Attribution-4.0 International License https://creativecommons.org/licenses/by/4.0/ の元で配布します。スナップショットとクイズに興味があるので読みました。全部訳す気は、無いです。USENIX 版の raft 論文抄訳もあります。

This is a Japanese translation by kanda.motohiro@gmail.com of the portions of the paper Consensus: Bridging Theory and Practice by Diego Ongaro.This translation is distributed under Creative Commons Attribution-4.0 International License https://creativecommons.org/licenses/by/4.0/

５章

ログコンパクション

Raft のログは、通常の運用中に、それがより多くのクライアント要求を受け付けるにつれて大きくなります。大きくなるとそれはより場所を取りますし、リプレイにより時間がかかるようになります。ログをコンパクトにするなんらかの方法がないとこれは最終的に可用性の問題を起こします。サーバーはディスク容量がなくなるか、開始に時間がかかり過ぎるようになります。なので、全ての現実システムには何らかの形のログコンパクションが必要です。

ログコンパクションの一般的概念は、ログにある多くの情報は時間が経つと不要になり、捨てることができるということです。例えば、ｘを２に設定する操作は、その後の操作がｘを３にすれば不要です。ログエントリがコミットされ、状態マシンに適用されたら、その現在状態に達するために使われた中間の状態と操作はもういりません。なので、コンパクトして捨てられます。

コアRaft アルゴリズムやメンバーシップ変更と違って、異なるシステムは、ログコンパクションについては、異なる要求を持ちます。ログコンパクションへの、一つのサイズで全部に使えるソリューションは、いくつかの理由により存在しません。まず、異なるシステムは単純さと性能へのトレードオフを異なる度合いで選ぶでしょう。次に、状態マシンはログコンパクションに緊密に関連しなければならず、状態マシンは大きさと、それがディスクか揮発メモリのどちらをベースとするかの点で、大きく異なるからです。

この章の目的は、ログコンパクションのいろいろなアプローチを議論することです。それぞれのアプローチで、ログコンパクションのほとんどの責任は、状態マシンに課せられます。それは状態をディスクに書いて、状態をコンパクションする役目を果たします。状態マシンはこれを、異なる方法で達成できます。それらはこの章で説明され、図５．１でまとめられています。

・メモリベースの状態マシンでスナップショットを取るのは、概念的には最も単純なアプローチです。スナップショットを取るときは、現在のシステム状態全体が、ステーブル記憶域のスナップショットに書かれます。そしてその時点までの全てのログが捨てられます。スナップショットは、Chubby[11, 15] と ZooKeeper[38] で使われており、私たちは LogCabin でスナップショットを実装しました。スナップショットはこの章で最も深く述べられているアプローチで、５．１節にあります。

・ディスクベースの状態マシンでは、システム状態の最新のコピーが、通常の操作の一部として、ディスク上に維持されています。なので、 Raft ログは、状態マシンがライトをディスクに反映したらすぐに捨てることができます。そしてスナップショットを取ることは、一貫したディスクイメージを他のサーバに送るためにだけ使われます。（５．２節）

・５．３節は、ログクリーニングや、ログ構造マージ木のような、インクリメンタルなログコンパクションアプローチを述べます。このアプローチは効率的にディスクに書き、資源を時間に渡って均等に使います。

・最後に、５．４節は、スナップショットを直接ログ内に格納することで必要な機構を最小化するログコンパクションアプローチを議論します。実装はより簡単ですが、このアプローチはとても小さい状態マシンにだけ有効です。

現在 LogCabin はメモリベースのスナップショットアプローチだけを実装します(それはメモリベースの状態マシンを持ちます)。

コンパクションのいろいろなアプローチはいくつかのコアとなる概念を共用します。一つめに、コンパクションの決定をリーダーに集中させるのではなく、それぞれのサーバは自分のログのコミットされたプレフィクスを独立にコンパクトします。これは、リーダーがフォロワーに、それらが既に自分のログに持っているデータを転送しなくてもよくします。それはまた、モジュール性を助けます。ログコンパクションのほとんどの複雑さは状態マシンの中に含まれており、Raft 自身とはあまりかかわりません。これはシステム全体の複雑さを最小に保つ助けになります。Raft の複雑さはログの複雑さと掛け算になるのでなく、足し算になります。５.4節では、コンパクションの責任をリーダーに集中化する別のアプローチを詳しく議論します(そして、とても小さい状態マシンにとっては、リーダーベースのアプローチの方が良いかもしれません)。

二つめに、状態マシンと Raft の間の基本的な関り合いは、ログのプレフィクスの責任を、Raft から状態マシンに移すことを含みます。エントリを適用した後、状態マシンは遅かれ早かれいずれは、それらのエントリを現在のシステム状態を回復できる方法でディスクに反映します。それが終わったら、それは Raft にログの対応するプレフィクスを捨てるように言います。Raft がそのログプレフィクスへの責任を放棄する前に、Raft はそのログプレフィクスを記述する自分自身の状態のいくらかをセーブしなくてはいけません。具体的には、Raft は自分が捨てた最後のエントリのインデックスとタームを保持します。これは、状態マシンの状態の後に、ログの残りを位置づけ、AppendEntries の一貫性チェックが引き続きうまくはたらくようにします（それは、ログ中の最初のエントリの一つ前のエントリのインデックスとタームを必要とします）。Raft はまた、捨てられたログプレフィックスの中から、最新のクラスタ構成を保持します。クラスタメンバーシップの変更をサポートするためです。

三つめに、いったん、Raft がログのプレフィックスを捨てたら、状態マシンは二つの新しい責任を負います。もしサーバが再開始したら、状態マシンは、それがRaft ログから何らかのエントリを適用できる前に、捨てられたログエントリに対応する状態をディスクからロードする必要があります。さらに、状態マシンは状態の一貫したイメージを作る必要があるかもしれません。それを遅いフォロワー（ログが、リーダーのよりもずっと遅れている）に送ることができるためです。ログエントリがクラスタの全てのメンバーに「完全に複製される」までコンパクションを遅らせるのは妥当ではありません。過半数に満たない遅いフォロワーがクラスタを完全に可用であることから遠ざけるのはあってはいけないことですし、新しいサーバはいつでもクラスタに追加されることがあります。なので、遅いフォロワーあるいは新しいサーバはそれらの初期状態をネットワーク経由で受け取る必要があることがあります。Raft はこれを、AppendEntries で必要となる次のエントリが既にリーダーのログから捨てられている時に検出します。この場合、状態マシンは状態の一貫したイメージを提供しなくてはいけません。リーダーはそれをフォロワーに送ります。

５．１メモリベースの状態マシンをスナップショットする

最初のスナップショットアプローチは状態マシンのデータ構造がメモリに維持されるときに適用できます。これは、データセットが数ギガバイトから数十ギガバイトの大きさの状態マシンにとって合理的な選択です。その場合、操作は素早く終わることができます。データをディスクからフェッチする必要は全くありませんから。また、プログラムも簡単です。豊富なデータ構造を使うことができ、全ての操作は終わるまで走ることができます（I/O によってブロックすることなく）。

図５．２は、状態マシンがメモリに維持されるときに、Raft でスナップショットを行うための基本的概念を示します。それぞれのサーバは独立にスナップショットを取ります。それは、自分のログの、コミット済みエントリだけをカバーします。スナップショットのほとんどの仕事は、状態マシンの現在状態をシリアライズすることに関わります。そしてこれは特定の状態マシンの実装に固有なことです。例えば、LogCabin の状態マシンは、木をその主要なデータ構造として使います。それはこの木を pre-order depth-first トラバーサルを使ってシリアライズします（これは、スナップショットを適用するときに、親ノードが、その子よりも先に作成されるようにです）。状態マシンは、クライアントに linearize 可能性を提供するために自分が維持する情報もシリアライズする必要があります（６章を参照）。

状態マシンがスナップショットを書くのを完了したら、ログはトランケートできます。Raft は最初に自分が再開始の時に必要な状態を格納します。それは、そのスナップショットに含まれる最後のエントリのインデックスとターム、そしてそのインデックスの時の最新のクラスタ構成です。次に Raft はログの先頭からそのインデックスのところまでを捨てます。以前のスナップショットも全て捨てることができます。もう役に立ちませんから。

先に紹介したように、リーダーは時には、自分の状態を、遅いフォロワーと、クラスタに参加しつつある新しいサーバに送る必要があることがあります。スナップショットに関して言えば、この状態は単純に最新のスナップショットです。リーダーはこれを、図5.3に示す InstallSnapshot という新しいRPCを使って転送します。フォロワーがこのRPCでスナップショットを受けたら、それは自分の既存のログエントリをどうするか決めなくてはいけません。普通はそのスナップショットはフォロワーのログには無い新しい情報を含むでしょう。この場合、フォロワーは自分のログを全部捨てます。それは全てスナップショットによって置き換わり、そのスナップショットと矛盾するコミットされていないエントリを含んでいるかもしれません。

もし、その代わりに、フォロワーが自分のログのプレフィックスを記述するスナップショットを受けたら、（再送のため、あるいは、誤りによって）そのスナップショットがカバーするログエントリは削除されます。しかし、そのスナップショットに続くエントリはまだ有効で、保持されなくてはいけません。

この節の残りは、メモリーベースの状態マシンをスナップショットする時の、二次的な問題を議論します。

• ５．１．１節は通常処理と並行してスナップショットを生成するにはどうするかを議論します。クライアントへのその影響を最小化するためです。

•５．１．２節はいつスナップショットを取るかを議論します。スペースの使用量とスナップショットのオーバーヘッドをバランスします。そして、

•５．１．３節はスナップショットを実装するときに現れる問題を議論します。

InstallSnapshot RPC

スナップショットのチャンクをフォロワーに送るためにリーダーによって呼ばれます。

リーダーは常にチャンクを順番に送ります。

引数：

結果：

term

currentTerm。リーダーが自分を更新するため

受信者の実装：

１．もし term < currentTerm ならすぐに応答します。

２．最初のチャンク(オフセットゼロ)なら新しいスナップショットファイルを作ります。

３．スナップショットファイルの指定されたオフセットにデータを書きます。

４．応答します。done が偽なら、次のチャンクを待ちます。

５．lastIndex が最新のスナップショットのものよりも大きいなら、スナップショットファイルと Raft 状態を待避します。既存の、あるいは部分的なスナップショットを全て捨てます。

６．もし既存のログエントリが lastIndex と lastTerm と同じインデックスとタームを持っているなら、 lastIndex までのログを(なお、後に続くエントリはそのままとします)捨てて応答します。

７．ログ全体を捨てます。

８．スナップショットの内容を使って状態マシンをリセットします。(そして lastConfig をクラスタ構成としてロードします)

図５．３．１

リーダーは、InstallSnapshot RPC を呼んで、遅いフォロワーにスナップショットを送ります。リーダーがスナップショットを送るのは、リーダーがフォロワーに AppendEntries を使ってログエントリを複製するために必要な次のエントリを既に破棄してしまった時だけに限ります。リーダーは転送のためにスナップショットをチャンクに切ります。他にも利点はありますが、これはフォロワーがチャンクごとに生きているしるしを得ることができ、選出タイマーをリセットできる利点があります。チャンクはそれぞれ順番に送られます。これはファイルをディスクに書くことを単純にします。この RPC は、再開始の時に Raft がスナップショットをロードするために必要な状態を含みます。それは、このスナップショットがカバーする最後のエントリのインデックスとターム、そしてその時点の最新の構成です。

５．１．１並行にスナップショットする

スナップショットを作るには、状態をシリアライズすることと、ディスクに書くことの両方において、長時間かかります。例えば、10GB のメモリをコピーするのは、今日のサーバで約一秒かかります。それをシリアライズするのは、通常、ずっと長くかかります。ソリッドステートディスクでも、一秒で500MBくらいしか書けません。なので、スナップショットをシリアライズすることと、書くことの両方は、可用性のギャップを避けるために、通常の操作と並行しなければいけません。

幸運にも、コピーオンライトテクニックは、書かれている途中のスナップショットに影響することなく、新しい更新を適用することを許します。これには二つのアプローチがあります。

・これをサポートするために、状態マシンはイミュータブル(functional) データ構造を使って作ります。状態マシンコマンドは状態をその場で変更しないので、スナップショット作業は、以前のどこかの状態への参照を維持でき、それをスナップショットに一貫性があるように書くことができます。

・別の案は、オペレーティングシステムのコピーオンライトサポートを使うことです（プログラミング環境がそれを許すなら）。例えば、Linux では、インメモリの状態マシンは、 fork を使って、そのサーバのアドレス空間全体のコピーを作ることができます。そして、子プロセスは、状態マシンの状態を書き出して終了することができます。その間ずっと、親プロセスは要求を処理できます。LogCabin 実装は今は、このアプローチを使います。

サーバは、並行してスナップショットを取るために余分のメモリを必要とします。それは、予定され、管理されるべきです。状態マシンがスナップショットファイルにストリーミング

ーーここから

ーーここまで

５．２ディスクベースの状態マシンをスナップショットする

この節は、ディスクを記録の主な場所とする大きな状態マシン（数十あるいは数百ギガバイト）のためのスナップショットアプローチを議論します。これらの状態マシンは、クラッシュの時に、常にディスクに状態のコピーを用意しているという点で異なるふるまいをします。Raft ログからそれぞれのエントリを適用することは、オンディスクの状態を更新し、実質的に新しいスナップショットに至ります。なので、いったんあるエントリが適用されたら、それはRaft ログから捨てられます。（状態マシンはライトをメモリにバッファすることもできます。より良いディスク効率を得られるかもしれないからです。それらがディスクに書かれたら、対応するエントリはRaftログから捨てることができます。）

ディスクベースの状態マシンの主な問題は、ディスク上で状態を変更することが悪い性能につながるかもしれないことです。ライトをバッファリングしないなら、全ての適用されるコマンドごとに、一度以上のランダムディスクライトが必要です。それはシステム全体のライトスループットを制限します（そしてライトバッファリングはあまり役に立たないでしょう）。５．３節は、ログコンパクションのインクリメンタルアプローチを議論します。それは、ディスクに、より効率的に、大きく、シーケンシャルにライトします。

ディスクベースの状態マシンは、遅いフォロワーに送るために、ディスクの一貫したスナップショットを提供することができなくてはいけません。スナップショットは常にディスクにありますが、それは常に変更されています。なので、それを転送するための十分に長い期間、一貫したスナップショットを保つためには、コピーオンライトテクニックが必要です。幸運にも、ディスク形式は、ほとんど常に、論理的ブロックに分割されていますから、状態マシンにコピーオンライトを実装するのは直裁的のはずです。ディスクベースの状態マシンはまた、スナップショットのためにオペレーティングシステムのサポートに頼ることもできます。例えば、Linux の LVM（論理ボリュームマネージャ）はディスクパーティション全体のスナップショットを作るために使うことができます[70] 。また、最近のファイルシステムには、個別のディレクトリのスナップショットができるものがあります[19]。

ディスクイメージのスナップショットをコピーするのは長時間かかることがあります。そして、ディスクへの変更が蓄積するにつれて、スナップショットを保つために必要な余分なディスク使用量は増えます。私達はディスクベースのスナップショットは実装していませんが、ディスクベースの状態マシンはこのほとんどのオーバーヘッドを、以下のアルゴリズムを使ってディスク内容を転送することによって避けることができると推測します：

１．ディスクブロックごとに、それが最後に変更された時刻を追跡します。

２．通常の運用を続けながら、ディスク内容全部を、フォロワーにブロックごとに転送します。この処理の間、リーダーでは余分なディスク領域は使われません。ブロックは並行して変更されているので、これはフォロワーにおいては一貫しないディスクイメージになることが多いでしょう。それぞれのブロックをリーダーから転送する時に、その最後に変更された時刻を記録します。

３．ディスク内容のコピーオンライトスナップショットを取ります。これが取れたら、リーダーはそのディスク内容の一貫したコピーを持ちます。しかし、クライアント操作を続けるためにディスクが変更されると追加のディスク領域が使われます。

４．ステップ2でディスクブロックを最初lに転送した時と、ステップ3でスナップショットを取った時との間で変更されたディスクブロックだけを再送します。

運が良ければ、ステップ3で一貫したスナップショットが作られる時までには、そのほとんどのブロックは既に転送が終わっているでしょう。その場合、ステップ4の転送は素早くできるでしょう。ステップ4の間にスナップショットをリーダーにおいて保持するために使われる追加のディスク容量は少ないでしょう。そして、ステップ4で変更されたブロックを再送するために使われる追加のネットワークバンド幅も少ないでしょう。

５．３インクリメンタルクリーニングアプローチ

のようなインクリメンタルなコンパクションへxのアプローチも可能です。それはスナップショットよりも複雑ですが、インクリメンタルアプローチはいくつかの望ましい機能を持ちます。

・それは一度にデータの一部だけを操作します。なので、コンパクションの負荷を時間にわたって均等に分散します。

・それは、通常運用の時も、コンパクションの間も、ディスクに効率的に書きます。どちらの場合でも、大きくシーケンシャルなライトを使います。また、インクリメンタルアプローチは、最もリクレイム可能な領域を持つディスクの部分を選択的にコンパクトします。このためそれは、メモリベースの状態マシンのスナップショット(これは全てのスナップショットでディスク全体を書き直します)と比べて、ディスクに書くデータが少ないです。

・それは、ディスクの領域をその場で変更しないので、一貫した状態のスナップショットを転送するのがとても簡単です。

ーーここから

ーーここまで

５．３．１ログクリーニングの基本

ログクリーニングは、ログ構造ファイルシステム[97] の文脈で導入され、最近、RAMCloud [98] のようなインメモリストレージシステムに対して、提案されてきました。原理的には、ログクリーニングは任意の型のデータ構造に対して使うことができますが、ものによっては他と比べて、効率的に実装するのがより困難なことがあります。

ログクリーニングはログを、システムの状態を記録する場所として維持します。そのレイアウトはシーケンシャルライトに最適化され、リード操作はほぼランダムアクセスに変えられます。なので、読むべきデータ要素を位置付けるためにインデックスが必要です。

ログクリーニングでは、ログはセグメントと呼ばれる連続した領域に分割されます。ログクリーナーのそれぞれのパスは三ステップのアルゴリズムを使ってログをコンパクトします。

それはまず、無効なエントリの大きな割合を蓄積した、クリーンするべきセグメントを選びます。

次に、ライブエントリ(現在のシステム状態に関わっているもの)を、これらのセグメントからログの先頭に複写します。

最後に、それらのセグメントのストレージ領域を解放して、新しいセグメントに使えるようにします。

通常の操作への影響を最小化するために、この処理は並行して行なうことができます[98]。

ライブエントリをログの先頭に複写したことによって、そのエントリはリプレイのための順序を乱すことになります。エントリには、追加の情報(例えばバージョン番号)を含めることで、ログが適用されるときに正しい順序を再作成できます。

どのセグメントをクリーニングのために選択するかというポリシーは性能に大きな影響があります。以前の研究は、ライブエントリが使っている領域の大きさだけでなく、それらのエントリがどのくらい長くライブでとどまると思われるかまでを考慮に入れたコスト・利益ポリシーを提案しました[97, 98]。

あるエントリがライブであるかを決めるのは、状態マシンの責任です。例えば、キーバリューストアにおいて、あるキーに特定の値を設定するログエントリは、そのキーが存在して現在その値に設定されていればライブです。キーを削除するログエントリがライブであるかを決めるのはもっと微妙です。それは、そのキーに設定をする何らかの以前のエントリがログに存在する限りライブです。RAMCloud は、削除コマンド(墓石と呼ばれます)を必要に応じて残します [98]。しかし、別のアプローチは、定期的に現在の状態に存在するキーのサマリーを書き出すことです。そうすれば、リストにないキーに関する全てのログエントリはライブではありません。キーバリューストアは、とても単純な例です。他の状態マシンは可能であり、でも不幸なことに、ライブであることを決めることはそれぞれ異なります。

５．３．２ログ構造マージ木の基本

ログ構造マージ木、Log-structured merge tree (LSM tree)は、最初に O’Neil [84] によって説明され、後に、BigTable [17] によって、分散システムでよく知られるようになりました。それは、Apache Cassandra [1] や HyperDex [27] のようなシステムで使われ、LevelDB [62] とそのフォーク (例えば、RocksDB [96] and HyperLevelDB [39]) のようなライブラリとして使用可能です。

LSM 木は木のようなデータ構造で、順序づいたキーと値の対を格納します。高いレベルでは、それはディスクを、ログクリーニングアプローチと似たように使います。それは大きなシーケンシャルな歩調で書き込み、ディスク上のデータをその場で変更することはありません。しかし、ログに全ての状態を維持するのでなく、LSM 木はその状態をより良いランダムアクセスのために再構成します。

典型的な LSM 木は最近書かれたキーをディスク上の小さいログに維持します。そのログが一定の大きさに達したら、それはキーによってソートされて、ランと呼ばれるファイルにソートされた順序で書かれます。ランは、決してその場で変更されません。しかし、コンパクション処理が定期的に複数のランを一緒にマージして、新しいランを作り、古いものを捨てます。このマージはマージソートに似ています。あるキーが複数の入力ランに含まれる時は、最新のバージョンだけが残されます。このため、生成されたランはよりコンパクトです。LevelDB で使われるコンパクション戦略を、図５．１にまとめました。それは効率のため、ランを年齢によって区別します（ログクリーニングと同様に）。

ーーここから

ーーここまで

６章

クライアント相互作用

６．４リードオンリーの問い合わせをより効率的に処理する

リードオンリーのクライアントコマンドは、複製された状態マシンに問い合わせるだけで、変更はしません。なので、これらの問い合わせは Raft ログをバイパスできないかと問うのは自然です。ログの目的は、サーバの状態マシンに変更を同じ順序で複製することですから。ログをバイパスすると魅力的な性能利点が得られます。リードオンリーの問い合わせは多くのアプリケーションで一般的であり、エントリを追加するのに必要な同期のディスクライトは時間がかかります。

しかし、追加の注意をしないでログをバイパスすることは、リードオンリーの問い合わせに古い結果を返すことになるかもしれません。例えば、リーダーはクラスタの残りから分断されており、クラスタの残りは新しいリーダーを選出して、Raft ログに新しいエントリをコミットしてしまったかもしれません。もし、分断されたリーダーが他のサーバに問い合わせることなくリードオンリーの問い合わせに応答したら、それは古い結果を返します。それは linearize 可能ではありません。linearize 可能性は、リードの結果が、リードが開始された後のいつかのシステムの状態を反映することを要求します。それぞれのリードは少なくても、最新のコミットされたライトの結果を返さなくてはいけません。(stale 古いリードを許すシステムは、serialize 可能性を提供するだけです。それは、一貫性のより弱い形です。)古いリードが原因の問題は、既に二つのサードパーティ Raft 実装において見つかっています[45]。なのでこの問題は十分な注意が必要です。

幸運にも、リードオンリーの問い合わせの時に、Raft ログをバイパスして、しかも、linearize 可能性を保つことは可能です。そのためには、リーダーは以下のステップを行います。

１．もしリーダーがまだ、自分の現在タームのエントリをコミット済みとマークしていない時は、それが終わるまで待ちます。Leader Completeness 属性は、リーダーが全てのコミット済みエントリを持つことを保証します。しかし、自分のタームの開始時には、リーダーはどのエントリがそうであるか知ることはできません。それを知るためには、リーダーは自分のタームからのエントリを一つ、コミットする必要があります。Raft は、それぞれのリーダーが自分のタームの初めに、ブランクの no-op エントリをログにコミットすることでそれを実現します。この no-op エントリがコミットされたらすぐに、リーダーのコミットインデックスはこのタームの間、他のどのサーバよりも大きくなります。

２．リーダーは自分の現在コミットインデックスをローカル変数 readIndex に退避します。これは、問い合わせが対象とする状態のバージョンの最低値として使われます。

３．リーダーは、自分が、未知のより新しいリーダーによって取って代わられていないことを確認する必要があります。それは新しいハートビートのラウンドを発行して、クラスタの過半数からの認可を待ちます。この認可がいったん受信されたら、リーダーは、自分がハートビートを送った時には、より大きいタームに属するリーダーは存在したはずがないことを知ります。このため、その readIndex はその時、クラスタのどのサーバが見たより大きいコミットインデックスです。

４．リーダーは、自分の状態マシンが少なくても、readIndex まで進むのを待ちます。これは、linearize 可能性を満足するために、十分、最新です。

５．最後にリーダーは問い合わせを自分の状態マシンに対して発行し、結果をクライアントに応答します。

このアプローチは、同期のディスクライトをしないので、リードオンリーの問い合わせを新しいエントリとしてログにコミットするよりも、より効率的です。さらに効率を上げるために、リーダーは自分のリーダーシップを確認するコストを緩和できます。リーダーは、一つのハートビートのラウンドを使って、蓄積した任意の数のリードオンリーの問い合わせを処理できます。

フォロワーも、リードオンリーの問い合わせの処理をオフロードする助けができます。これはシステムのリードスループットを改善するでしょうし、リーダーから負荷を取り除いて、リーダーがより多くの読み書きの要求を処理できるようにするでしょう。しかし、このリードは、追加の注意をしないと、古いデータを返す危険があります。例えば、分断されたフォロワーは、長い間、リーダーから新しいログエントリを何も受け取らないかもしれません。あるいは、フォロワーがリーダーからハートビートを受けたとしても、そのリーダー自身が、

それをまだ知らないのかもしれません。リードを安全に提供するには、フォロワーはリーダーに、現在の

を聞くだけの要求を発行することができます(リーダーは前記ステップの1から3を実行するでしょう)。そしてフォロワーは自分自身の状態マシンにステップ4と5を

ーーここから

ーーここまで

付録 A

利用者の学習資料

A.1 Raft クイズ

訳注。答えは、まとめて、問題の最後に置きました。点数のつけ方は、略しました。

１．以下の図はそれぞれ、Raft サーバのログの、あり得るかもしれない構成を示します。(ログエントリの内容は示されず、そのインデックスとタームだけを示します。)それぞれのログを一つづつ考えて、そのログ構成が正しい Raft 実装で起き得るか答えなさい。答えが「いいえ」なら、なぜか説明しなさい。

(a)

(b)

(c)

(d)

２．以下の図は５サーバのクラスタのログの状態を示します。状態マシンに安全に適用できるのはどのログエントリですか？あなたの答えを説明しなさい。

３．以下の図を考えなさい。これは、６サーバのクラスタで、ターム７のための新しいリーダーがちょうど選出された直後のログです。図にあるそれぞれのフォロワーについて、示されるログの構成は、正しく機能している Raft システムで起き得るか答えなさい。もしそうなら、それがどのように起きるかを説明しなさい。そうでないなら、なぜそれが起きないか説明しなさい。

４．ハードウェアあるいはソフトウェアのエラーが、リーダーが特定のフォロワーのために格納している nextIndex の値をこわしたとします。これは、システムの安全性を脅かしますか？簡単にあなたの答えを説明しなさい。

５．あなたは Raft を実装して、同じデータセンタにある全てのサーバに配備したとします。次に、あなたはそのシステムを世界中に広がっている異なるデータセンタにあるサーバに配備するとします。単一データセンタバージョンの Raft に比べて、ワイドエリアバージョンは変更をする必要が何かありますか？なぜ？

６．それぞれのフォロワーはディスクに三つの情報を格納します。自分の現在ターム、自分の最新の投票、そして自分がアクセプトした全てのログエントリ。

(a)フォロワーがクラッシュして、それが再開始した時に、その最新の投票が失われていたとします。このフォロワーがクラスタに再参加するのは安全ですか（アルゴリズムの変更は無いとします）？あなたの答えを説明しなさい。

(b)さて、フォロワーのログがクラッシュの間にトランケートされ、最後にあるエントリをいくつか失ったとします。このフォロワーがクラスタに再参加するのは安全ですか？あなたの答えを説明しなさい。

７．ビデオで述べたように、リーダーは、他のサーバがそれがクラッシュしたと判断して新しいリーダーを選出した後でも動作を続けることがあり得ます。新しいリーダーはクラスタの過半数に接触して、それらのタームを更新するでしょう。そのため、古いリーダーはこれらのサーバのどれかと通信したなら、すぐにステップダウンするはずです。しかし、その一方で、それはリーダーとして動作し、まだ新しいリーダーによって接触されていないフォロワーに要求を発行することができます。さらに、クライアントは古いリーダーに要求を送り続けるかもしれません。古いリーダーは、選出が終わった後にそれが受け取る新しいログエントリをけっしてコミットできないことはわかります。それをするためには、古いリーダーは選出に加わった過半数のサーバのどれか一つ以上に必ず接触しなくてはいけないだろうからです。しかし、古いリーダーが、選出が始まる前に受け取った古いログエントリのコミットを完了させる AppendEntries RPC を実行して成功させることができますか？そうならば、それがどのように起きることができるか説明しなさい。そして、これが Raft プロトコルに問題を起こすかどうかを議論しなさい。これが起きることができないならば、なぜだか説明しなさい。

８．構成変更の間、もし現在のリーダーが Cnew に含まれないなら、それは Cnew のためのログエントリがコミットされたらステップダウンします。しかしこれは、リーダーが、自分がリードしているクラスタの部分ではない期間があることを意味します（リーダーに格納されている現在構成エントリは Cnew です。それはそのリーダーを含みません）。プロトコルを変更して、リーダーはそれが自分のログに Cnew を格納したらすぐにステップダウンするようにしたとします。もし Cnew がそのリーダーを含まないなら、このアプローチの結果起きうる最悪なことは何ですか？

raft クイズの答え

１．

(a)

いいえ。タームはログ中で単調増加します。

具体的には、エントリ（４，２）を作ったリーダーは、現在ターム＞＝３の時のリーダーから（３，３）だけを受け取りました。なので、その現在タームも＞＝３のはずです。そうするとそれは（４，２）を作ることはできません。

(b)

はい。

(c)

はい。

(d)

いいえ。ログはホールを持つことはできません。

具体的には、リーダーは自分のログに追加だけをします。そして、フォロワーでの AppendEntries の一貫性チェックは決してホールとマッチしません。

２．エントリ（１，１）と（２，２）は安全に適用できます。

もしエントリがクォーラムに格納されていないなら、それは安全に適用できません。これは、このマイノリティが障害になるかもしれず、他のサーバ（それがマジョリティを構成します）はそのエントリを知らないまま続行できるからです。

なので、エントリ（１，１）（２，１）（３，２）（４，２）（５，２）だけを考えれば良いです。

私達はどれがリーダーに選出される可能性があるかを見つけて、それがこれらのエントリを削除することができるかを考えなければいけません。

サーバ２はリーダーに選出されることができます。そのログは S3,S4 そして S5 以上に完全だからです。するとそれはサーバにエントリ（３，２）（４，２）そして（５，２）を削除させることができます。なので、これらのエントリは安全に適用できません。

そうなると、（１，１）と（２，１）が、安全に適用できる可能性があるものとして残ります。

サーバ３と４はリーダーに選出されることができません。ログが十分に完全でないからです。サーバ５はリーダーに選出されることができます。

訳注。サーバ１と２が落ちていれば、S3、S4、S5 で過半数が取れます。S5 のログは三つの中では一番長いからです。

しかしそれは（１，１）と（２，１）を含んでいます。

なので、エントリ（１，１）と（２，１）は安全に適用できます。

３．

(a)

いいえ。

エントリ（５，３）は一意にログプレフィックスを識別します（AppendEntries 一貫性チェックにより）。しかし、このフォロワーはエントリ（５，３）とその前にリーダーと異なるログプレフィックスを持ちます。

(b)

いいえ。エントリ（６，５）が一致していて、その前が異なります。訳注。前項と同じ。

(c)

はい。クラスタの他のサーバについて多くは言えません。このサーバはターム６でリーダーであり、開始した時のログが（１，１）（２，１）であり、自分のログにたくさんエントリを書き、私達の今のターム７のリーダーと通信しなかったのかもしれません。これは、エントリ（３，３）（４，３）（５，３）そして（６，５）はターム５ではコミットされなかったことを前提とします。それはあり得ます。

(d)

いいえ。タームはログ中で単調増加します。具体的には、エントリ（５，２）を作ったリーダーは、現在タームが＞＝３の時のリーダーからは（４，３）を受け取ったはずで、その現在タームも＞＝３でしょう。なので、（５，２）を作ることはできません。

(e)

はい。例えば、(e) はターム１のリーダーで、エントリ（１，１）と（２，１）をコミットし、そして他のサーバから分離されましたが、クライアントの要求を処理し続けました。

４．

いいえ。

もし nextIndex が小さすぎる時は、リーダーは余分な AppendEntries 要求を送ります。それらはフォロワーのログでは、影響を与えません（それらは一貫性チェックを通りますが、フォロワーのログのどれとも矛盾しませんし、そのフォロワーがまだ持っていないエントリをフォロワーに提供することはありません）。そして、成功の応答はリーダーに、nextIndex を加算するべきだと指示します。

もし nextIndex が大きすぎる時も、リーダーは余分な AppendEntries 要求を送ります。これらに対して一貫性チェックは失敗します。その結果、フォロワーはその要求を拒否し、リーダーは nextIndex を減算してリトライすることになります。

いずれの場合も、これは安全なふるまいで、どちらの場合も致命的な状態は変更されません。

５．

選出タイムアウトを大きくする必要があるでしょう。予期されるブロードキャスト時間はより大きいでしょう。そして、選出タイムアウトはブロードキャスト時間よりずっと大きいべきです。候補者がタイムアウトを繰り返す前に選出を完了する機会を得るためです。アルゴリズムの残りは何も変更はいりません。それはタイミングに依存しないからです。

６．

(a)

いいえ。これは、サーバが、同じターム内に二回投票することを許します。それはタームに複数のリーダーを許すことになります。それは単純に全てをこわします。

例えば、３つのサーバがいて、

S1はS1とS2の投票を得て、ターム２のリーダーになります。

S2が再開始して、自分がターム２で投票したことを忘れます。

S3はS2とS3の投票を得て、ターム２の２つめのリーダーになります。

すると、S1とS3はターム２の中で、同じインデックスとタームを持ちますが異なる値を持つ別々のエントリをコミットすることができます。

(b)

いいえ。これは、コミット済みエントリがクォーラムに格納されないことを許します。それは何か他のエントリが同じインデックスに対してコミットされることを許すことになります。

例えば、３つのサーバがいて、

S1はターム２のリーダーになって、インデックス＝１，ターム＝２，値＝Xを、自分とS2に加えます。

S1はその committedIndex を１にして、クライアントに、Xがコミットされたと言って戻ります。

S2が再開始して、自分のログからエントリを失います。

S3（空のログを持ち）がターム３のリーダーになります。その空のログは、S2と同じくらい完全だからです。

S3はインデックス＝１，ターム＝３，値＝Yを、自分とS2に加えます。

S3はその committedIndex を１にして、クライアントに、Yがコミットされたと言って戻ります。

７．

はい。これは、新しいリーダーも、そのコミットされるエントリを持っている時にしか起きません。このため、問題ではありません。

以下は、５サーバでこれが起きる例です。

S1は空のログを持ち、S1, S2, そしてS3 の投票を得てターム２のリーダーになります。

S1は、インデックス=1,ターム=2,値=X を、自分とS2 に追加を完了します。

S2は、インデックス=1,ターム=2,値=X を、自分のログに持ち、S2, S4, そしてS5 の投票を得てターム３のリーダーになります。

S1は、インデックス=1,ターム=2,値=X を、S3 に追加を完了します。

この時点で、S1は、もう現在のリーダーではないのに、インデックス=1,ターム=2,値=X を、コミットできました。

このふるまいは安全です。新しいリーダーは必ず、同様にそのエントリを含まなくてはなりません。なのでそれは、永遠に永続化されます。

そのエントリは、新しいリーダーＬに投票したどれかのサーバSに格納されているはずです。そしてそれは、Sがその新しいリーダーに投票したよりも前に S に格納されなくてはいけません。ログ完全性チェックは、Sは以下の条件の時にだけ Lに投票できるとします。

L.lastLogTerm > S.lastLogTerm or

(L.lastLogTerm == S.lastLogTerm and L.lastLogIndex ≥ S.lastLogIndex)

もし L が S の後の最初のリーダーなら、二つ目の場合であるはずです。そのため、LはSが持つ全てのエントリを含まなくてはいけません。それには私たちが気にしているものも入っています。

もし L' がSの後の二つ目のリーダーなら、それがSより大きいラストタームを持つのはそれがLからエントリを受け取った時だけです。しかし、Lは自分自身のエントリをL' に複製する前に、L' に、私たちが気にしているエントリを複製しているはずです。なので、これも安全です。

そしてこの議論は、全ての未来のリーダーに対して、帰納的に正しいです。

８.

アルゴリズムの解釈によって、二つの、正しい答えが可能です。

答え1は、いったんサーバが現在の構成に属さなくなったら、もう候補者にならないという実装を前提とします。問題は、C old に属する他のサーバがリーダーに選出され、自分のログに C new を追加し、そして直ちにステップダウンすることがあり得ることです。

さらに悪いことに、これは C old に属する過半数のサーバの数だけ繰り返すことがあります。それ以上は繰り返しません。なぜならば、過半数の C old が C new をいったん格納したら、このエントリを持たない C old のサーバはログ完全性チェックのために選出されることはできないからです。(C old,new のために必要な C old の過半数は、もうこのサーバへの自分の投票を与えません)

この後、 C new に属するサーバが選出されなくてはいけません。そしてクラスタは続行します。なので、最悪の場合は、最大、約 | C old | /2 の余分な選出と選出タイムアウトをしなければいけないというだけのことです。

答え2は、サーバは現在の構成に属さなくなってもまだ、候補者になることができるというナイーブな実装を前提とします。この場合、起きうる最悪のことは、リーダーがステップダウンしてすぐにまた選出されることです(そのログはまだ完全です)。そしてまたステップダウンして、永遠に繰り返します。

A.2 Paxos クイズ

１．以下の図はそれぞれ、Multi-Paxos サーバのログの、あり得るかもしれない構成を示します。(ログエントリの中の数字は、その acceptedProposal 値です)それぞれのログを一つづつ考えて、そのログ構成が正しい Multi-Paxos 実装で起き得るか答えなさい。

訳注。無限大は、値が選択された(acceptedValue is know to be chosen)ことを示します。

２． Base Paxos において、クラスタは５つのサーバを持ち、そのうち３つがプロポーザル５．１を値X でアクセプトしたとします。いったんこれが起きた後、そのクラスタの他のいずれかのサーバが異なる値Yをアクセプトできますか？あなたの答えを説明しなさい。

３．サーバが、Multi-Paxos において、たった今、リーダーとしてふるまうと決めたとします。現在リーダーとして活動しているサーバは他にはいません。さらに、そのサーバはある期間、リーダーであり続け、ログエントリのために多くのコマンドを選択するようにして、その間、他のサーバはどれも、リーダーとしてふるまう試みをしなかったとします。

a)この期間に、このサーバが発行しなくてはいけない Prepare RPC のラウンドの最小値はいくつですか？あなたの答えを説明しなさい。出来る限り、正確に答えなさい。

b)この期間に、このサーバが発行しなくてはいけない Prepare RPC のラウンドの最大値はいくつですか？

４．アクセプタは、プロポーザが提供した、firstUnchosenIndex を使ってエントリを選択済みとマークするときに、それはまず、マークするエントリのプロポーザル番号をチェックしなくてはいけません。このチェックをしなかったとします。システムが誤動作することのあるシナリオを説明しなさい。

５．プロポーザル番号の二つの部分（ラウンド番号と、一意のサーバID)が入れ替わって、サーバIDが高位ビットにあるとします。

a)これは、Paxos の安全性を脅かしますか？

b)これは、Paxos のlivenessを脅かしますか？

６．あるプロポーザが初期値 v1 を使って Basic Paxos プロトコルを実行したとします。しかしそれは、プロトコル実行の途中あるいは後の、不明な地点でクラッシュしました。そのプロポーザが再開始して、以前使ったのと同じプロポーズ番号を使い、ただし異なる初期値 v2 を使って最初からプロトコルを実行したとします。これは安全ですか？

７．成功した Accept RPC では、アクセプタは、自分の minProposal を、n （Accept RPC 内のプロポーザル番号）に設定します。これが実際に minProposal の値を変更する（つまり、minProposal がまだ n に等しくない）シナリオを説明しなさい。このコードが無いときに、システムが誤動作するシナリオを説明しなさい。

８．Multi-Paxos での構成変更を考えなさい。古い構成はサーバ１，２，３からなり、新しい構成はサーバ３，４，５からなります。新しい構成は、ログ内のエントリNで選択され、エントリNからN＋α（含む）も選択されたとします。この時点で、古いサーバ１と２は、それらが新しい構成の一部でないためにシャットダウンしたとします。これがシステムに与える可能性のある問題を説明しなさい。

Paxos クイズの答え

１．

はい。

２．

はい。もし、S1, S2, そして S3 が（５．１，X)をアクセプトしたとします。他のサーバはそれでも、Y が無効なプロポーザル番号を持てばそれをアクセプトできます。

例えば、S4 が３．４をプリペアして、値を何も見つけませんでした。次にS1は５．１を、S1, S2, S3 でだけプリペアできます。次に S1 はS1, S2, S3 でだけ、アクセプトを完了できます。そして、S4はまだ、（３．４，Y)で、S4とS5においてアクセプトを完了できます。

訳注。しかし、S4 が S3にアクセプトを送ると、より大きいプロポーザル番号５が返ってくるので、過半数を得ることはできずに、やり直しになります。

３．

Prepare RPC 応答の過半数が、ただちに、noMoreAccepted=true を返せば、Prepare のラウンドの最小値は、１です。

最大値は、リーダーにおいて選択されていないスロットで、どれかのアクセプタが何らかのプロポーザルをアクセプトしたことのあるスロット一つにつき、Prepare RPC のラウンド一回です。これは、リーダーが、自分が選択していないスロットの一つにプリペアを発行するたびに、リーダーが、既に何らかの値をアクセプトしたアクセプタを見つける場合に起きます。するとリーダーはこのスロットにはその値を採用する必要があり、次のスロットの処理を続けます。

４．

略

図A.2からA.5 利用者の学習で使われた Paxos 概要

Paxos 概要

Diego Ongaro and John Ousterhout

March 6, 2013

この文書は、Basic Paxos (single-decree) コンセンサスプロトコルと、Multi-Paxos の簡単な概要です。これは、Paxos を Raft コンセンサスアルゴリズムと比べるための利用者学習の一部として作成された一時間のビデオ講義に付属するものとして作られました。Multi-Paxos は講義では正確には説明されませんでした。ここでの私たちの目的は、Leslie Lamport の “The Part-Time Parliament” でのオリジナルな Paxos の説明に近い、わりと完全な仕様を提供することです。ここで説明されているバージョンの Multi-Paxos は、実装されたことも、正しさを証明されたこともありません。

1 基本

• プロポーザル番号 (n) = (ラウンド番号, server ID)

• T: リーダー選出アルゴリズムで使われる固定のタイムアウト値

• α: Multi-Paxos での並行性の限界

1.1 リーダー選出アルゴリズム

• T ミリ秒ごとに、空のハートビートメッセージを他の全てのサーバに送ります。

• サーバは、より大きいIDを持つサーバから、最近 2T ミリ秒以内にハートビートメッセージを受け取らなかったら、リーダーとしてふるまいます。

2 Basic Paxos (Single-decree)

2.1 サーバごとの永続的状態

• minProposal: このサーバが受け付けるだろう最小のプロポーザル番号。あるいはそれが一度も Prepare 要求を受けていないなら、０．

• acceptedProposal: このサーバが受け付けた最近のプロポーザル番号。あるいはそれが一度も受け付けていないなら、０．

• acceptedValue: このサーバが受け付けた最近のプロポーザルにある値。あるいはそれが一度も受け付けていないなら、null。

• maxRound: このサーバが見た最大のラウンド番号。

2.2 メッセージ

2.2.1 Prepare (Phase 1)

要求フィールド:

• n: 新しいプロポーザル番号

Prepare 要求を受けた時, もし n >= minProposal なら、アクセプタは minProposal を n にします。応答は、将来、n より小さいプロポーザル番号を持つ Accept メッセージを拒否する約束を設定します。

応答フィールド:

• acceptedProposal: アクセプタの acceptedProposal

• acceptedValue: アクセプタの acceptedValue

2.2.2 Accept (Phase 2)

要求フィールド:

• n: Prepare で使われたのと同じプロポーザル番号

• v: 値。Prepare 応答にある最大の番号を持つ値。あるいは、無い場合は、クライアント要求からの値。

Accept 要求を受けた時、もし n >= minProposal なら:

• Set acceptedProposal = n

• Set acceptedValue = v

• Set minProposal = n

応答フィールド:

• n: アクセプタの minProposal

2.3 プロポーザアルゴリズム: write(inputValue)->chosenValue

1. n を新しいプロポーザル番号とします (maxRound を加算して永続化します).

2. Prepare(n) 要求を全てのアクセプタにブロードキャストします。

3. アクセプタの過半数から Prepare 応答(reply.acceptedProposal, reply.acceptedValue) を受けた時:

• v を以下のように設定します: もしそれら応答の最大の reply.acceptedProposal がゼロでない時、それに対応する reply.acceptedValue を使います。そうでないなら、inputValue を使います。

4. Accept(n, v) 要求をブロードキャストします。

5. Accept 応答(reply.n)を受けた時:

• もし reply.n > n なら, maxRound を n に設定して、ステップ１に戻ってやり直します。

6. アクセプタの過半数から n の Accept 応答を受けるまで待ちます。

7. v を戻します。

3 Multi-Paxos

3.1 アクセプタごとの永続状態

アクセプタはそれぞれ以下を格納します:

• lastLogIndex: このサーバがプロポーザルをアクセプトした最大のエントリ

• minProposal: このサーバが任意のエントリに対してアクセプトするであろう最小のプロポーザル番号。それが一度も Prepare 要求を受けていないなら、０．これは、グローバルに全てのエントリに適用されます。

アクセプタはそれぞれ、ログも格納します。それぞれのログエントリ i ∈ [1, lastLogIndex] は以下のフィールドを持ちます:

• acceptedProposal[i]: このサーバがこのエントリに対してアクセプトした最後のプロポーザル番号。あるいはそれが一度も受け付けていないなら、０．または、acceptedValue[i] が選択されたことがわかっているなら ∞。

• acceptedValue[i]: このサーバがこのエントリに対してアクセプトした最近のプロポーザルにある値。あるいはそれが一度も受け付けていないなら、null。

firstUnchosenIndex を、acceptedProposal[i] < ∞ である最小のログインデックス i > 0 と定義します。

3.2 プロポーザごとの永続状態

• maxRound: プロポーザが見た最大のラウンド番号。

3.3 プロポーザごとのソフト (揮発)状態

（私はここで、プロポーザとアクセプタにあまり強い分離をしていません。プロポーザは、時には、アクセプタの状態を読み書きどちらもすることを許します。）

• nextIndex: クライアント要求に対して使う、次のエントリのインデックス

• prepared: 真は、 Prepare 要求を投げる必要がないことを意味します。（過半数のアクセプタは Prepare 要求に対して、 noMoreAccepted true を返しました）初期値は、偽です。

3.4 メッセージ

3.4.1 Prepare (Phase 1)

要求フィールド:

• n: 新しいプロポーザル番号

• index: プロポーザが情報を求めているログエントリ

Prepare 要求を受けた時、もし n >= minProposal なら、アクセプタは minProposal を request.n に設定します。

応答は、request.n より小さいプロポーザル番号を持つ Accept 要求（任意のログエントリに対して）を拒否する約束を設定します。

応答フィールド:

• acceptedProposal: アクセプタの acceptedProposal[index]

• acceptedValue: アクセプタの acceptedValue[index]

• noMoreAccepted: このアクセプタが index より大きいインデックスを持つログエントリに対して一度も値をアクセプトしていないなら真に設定されます。

3.4.2 Accept (Phase 2)

要求フィールド:

• n: 最新の Prepare で使われたのと同じプロポーザル番号

• index: ログエントリを指定します

• v: Prepare 応答にある最大の番号を持つ値、あるいは、あるいは、無い場合は、クライアント要求からの値。

• firstUnchosenIndex: 送信者の firstUnchosenIndex

Accept 要求を受けた時、もし n >= minProposal なら:

• Set acceptedProposal[index] = n

• Set acceptedValue[index] = v

• Set minProposal = n

全ての index < request.firstUnchosenIndex に対して、もし acceptedProposal[index] = n なら、 acceptedProposal[index] を ∞ に設定します。

応答フィールド:

• n: アクセプタの minProposal

• firstUnchosenIndex: アクセプタの firstUnchosenIndex.

3.4.3 Success (Phase 3)

要求フィールド:

• index: ログエントリを指定します

• v: そのエントリインデックスに対して選ばれた値

Success 要求を受けたら、acceptedValue[index] を v にして、acceptedProposal[index] = ∞ にします。

応答フィールド:

• firstUnchosenIndex: アクセプタの firstUnchosenIndex.

送信者が応答を受けた時、もし reply.f irstUnchosenIndex < firstUnchosenIndex なら送信者は Success(index = reply.firstUnchosenIndex, value = acceptedValue[reply.f irstUnchosenIndex]) を送ります。

3.5 プロポーザアルゴリズム: write(inputValue) -> bool

1. リーダーでないか、リーダー初期化が終わっていなければ、偽を返します。

2. もし prepared が真なら:

(a) index = nextIndex にして, nextIndex を加算します。

(b) step 6 に行きます。

3. index = firstUnchosenIndex and nextIndex = index + 1 にします。

4. n を新しいプロポーザル番号とします (maxRound を加算して、永続化します)。

5. Prepare(n, index) 要求を全てのアクセプタにブロードキャストします。

6. Prepare 応答 (reply.acceptedProposal, reply.acceptedValue, reply.noMoreAccepted)

を過半数のアクセプタから受けたら:

• v を以下の通り設定します: もし応答の最大の reply.acceptedProposal がゼロでないなら、それに対応する reply.acceptedValue を使います。そうでないなら、inputValue を使います。

• もし過半数の全てのアクセプタが reply.noMoreAccepted を返したら、prepared = 真にします。

7. Accept(index, n, v) 要求を全てのアクセプタにブロードキャストします。

8. Accept 応答 (reply.n, reply.firstUnchosenIndex) を受けたら:

• もし reply.n > n なら、maxRound を reply.n に設定します。prepared = 偽にします。step 1 に行きます。

• もし reply.firstUnchosenIndex <= lastLogIndex かつ、

acceptedProposal[reply.firstUnchosenIndex] = ∞ なら,

Success(index = reply.firstUnchosenIndex, value = acceptedValue[reply.firstUnchosenIndex])

を送ります。

9. n の Accept 応答を過半数のアクセプタから受けたら:

• acceptedProposal[index] = ∞ かつ acceptedValue[index] = v にします。

10. もし v == inputValue なら, 真を返します。

11. step 2 に行きます。

4 再構成

• Configuration は、サーバのIDとアドレスのリストで、特別のログエントリとして格納されます。

• エントリ i を選ぶための Configuration は、ログ中の、エントリ i − α 以下の最近の configuration で決まります。

• α は並行性を制限します: エントリ i が選ばれるまでは、エントリ i + α は選べません。

以上

Page updated

Google Sites

Report abuse