受け取ることと確定することは違う

一言でいうと

リーダーが値を受け取って自分のログに書き込んだという事実は、何も保証しません。過半数が同じ位置に同じエントリを持ち、そのエントリがリーダーの現在の任期のものであって初めて「コミット」になり、そのときになってようやく、クライアントに成功と伝えられます。

なぜ必要なのか

選挙が終わると、書き込みを受け付ける場所が1つに決まります。では、その1つが受け取った値を、残りにどう広めるのか。単純に「送って忘れる」にすると、リーダーが値を受け取った直後に落ちたとき、その値はどこにもありません。逆に、「全員が受け取るまで待つ」にすると、1台だけが遅くても全体が止まります。合意が選ぶのは、その間にある過半数です。

過半数を選ぶ理由は、性能ではなく安全性です。2つの過半数は必ず重なるので、あるエントリが過半数に届いていれば、次のリーダーになりうる候補のうち、少なくとも1つはそのエントリを持っています。ここに条件をもう1つ加えると、つまり、候補のログが投票者のものと同じくらい新しいときだけ票を与えるという条件を加えると、そのエントリを持つノードだけがリーダーになれるようになります。そのため、コミットされたエントリは、どんな未来のリーダーにも残ります。

どう動くのか

ログは追記するだけのリストで、エントリごとにそのときの任期が一緒に付きます。その任期が、 2つのログを比較する唯一の根拠です。

index :   1        2        3        4
term  :   1        1        2        3
value : "a"      "b"      "c"      "d"

リーダーは、フォロワーにエントリを送るとき、「あなたのログのインデックス2が任期1なら、その後ろにこれらを付けなさい」と言います。フォロワーは、その直前の位置だけを確認します。全体を比較しない理由は、 ログの一致性のためです。同じ位置に同じ任期のエントリがあれば、その前はすべて同じだという性質が、ルールから導かれます。直前の位置が食い違っていれば、フォロワーは拒否し、リーダーは1つ後ろに下がってもう一度尋ねます。合う地点を見つけたら、そこから自分のもので埋めます。

コミットは、リーダーが数えます。各フォロワーがどこまで受け取ったかを数えて、過半数が持っている最も高い位置をコミット番号にします。ここに、ほとんど必ず見落とされる但し書きが付きます。

리더는 자기 임기의 항목이 과반에 닿았을 때만 커밋 번호를 올린다.
앞 임기의 항목은 그 자체로는 과반에 닿아도 커밋하지 않는다.

このコードブロックの韓国語コメントは、リーダーは自分の任期のエントリが過半数に届いたときだけコミット番号を上げ、前の任期のエントリは、それ自体では過半数に届いてもコミットしない、という意味です。

この但し書きがないと、こんなことが起きます。前の任期のエントリが過半数に複製されてコミットしたのに、そのリーダーが落ちて、そのエントリを持っていない別のノードが(より高い任期のエントリを持っているために)リーダーになると、その位置を別のエントリで上書きします。すでに確定したと伝えた値が消えてしまうのです。論文はこのケースを図8で説明し、解決策として、上の但し書きを入れています。新しいリーダーが自分の任期のエントリを 1つでもコミットした瞬間に、その前のものも一緒に安全になります。

リーダーがフォロワーごとに別々に持っている値が、もう1つあります。「このフォロワーに次にどこから送るか」です。リーダーが新しく選ばれると、この値を自分のログの末尾に楽観的に設定しておき、拒否されるたびに1つずつ減らします。ほとんどのフォロワーは、1–2回で合う地点を見つけるので、この楽観は普段はただです。その代わり、長く離れていたノードでは巻き戻しが長くなり、それがスナップショットが必要になる理由になります。

現場での姿

この区別は、クライアントが受け取るレスポンスの意味を変えます。etcdの書き込みが成功を返したなら、その値は過半数に届いていて、そのため、リーダーがその直後に落ちても生き残ります。逆に、レスポンスが timeoutだったなら、その書き込みは成功したかもしれないし、失敗したかもしれません。過半数に届いた後にレスポンスだけが失われた可能性があるからです。そのため、分散ストアを使うコードは、リトライを冪等にしなければなりません。etcdのドキュメントが、トランザクションとリビジョンを前面に出す理由が、ここにあります (etcd — なぜetcdなのか)。

キャッチアップも、毎日見る場面です。フォロワーが1つ再起動すると、リーダーが送る位置番号を 1つずつ後ろに戻しながら、合う地点を探します。ログが長いと、この巻き戻しに時間がかかり、そのため実際の実装は、スナップショットを併用します。etcdは、ログが一定数溜まると圧縮しますが、その値を決める--snapshot-countのデフォルト値は、v3.2で10,000から100,000に変わりました (etcdのメンテナンスのドキュメント)。

3番目によく見るのが、「遅いフォロワー1台」です。過半数さえあればコミットが進むので、遅い1台はサービスを止めません。そのため目立たず、ある日、別の1台が再起動するときに初めて表面化します。その瞬間に、過半数を作れる健康なノードが1つだけになるからです。複製の遅延は、障害ではなく余裕分の消費として読まなければなりません。

次のラボですること

ログのルールを4つ、自分で書きます。追記、ログの一致性の確認、食い違う位置から切り落とすこと、そしてコミット番号の計算です。最後の2つのステップでは、3つのノードに値を書いて、コミットが広がるのを確認し、フォロワーを1つ落として復活させて、空のログからキャッチアップする過程を、自分で確認します。