リーダーが二人いた

一言でいうと

ネットワークが分断されると、同じ瞬間にリーダーが2人になることがあります。Raftが防ぐのは、その状態ではなく、 同じ任期にリーダーが2人いる状態で、少数派側のリーダーは、何も確定できないまま、自分の記録が捨てられることを、後から知ることになります。

なぜ必要なのか

分散システムの事故は、たいてい障害そのものではなく、不完全な情報から来ます。切り離されたリーダーは、自分が切り離されたことを知りません。彼が知っているのは「最近、応答が来ない」だけで、それは相手が落ちているときと区別できません。ところが、Raftのリーダーには、自分から退く仕組みがありません。より大きな任期を見るまでは、自分がリーダーだと信じ続けます。

そのため、彼は引き続きリーダーのように振る舞います。クライアントの値を受け取り、自分のログに書き込み、成功を返します。同じ瞬間に反対側では、過半数が集まって、より高い任期の新しいリーダーを選びます。このとき、リーダーは本当に2人です。これを防ぐ方法がないということが、このアルゴリズムの出発点で、その代わりに防ぐのは、2人のリーダーが同じ位置に異なる値を確定することです。

どう動くのか

少数派側のリーダーは、過半数の確認を得られません。自分のログにエントリを書き込むことはできても、コミット番号は上がりません。そのため、そのエントリは「記録されたが確定されていない」状態のまま残ります。

분할 중                        임기  로그                  커밋
  옛 리더 (혼자)                 1   alpha, ghost           1
  새 리더 + 팔로워 (둘)          2   alpha, real            2

このコードブロックの韓国語コメントは、分断中の状態を表す表で、列は順に任期、ログ、コミットを意味し、上の行は(1台だけの)古いリーダー、下の行は新しいリーダーと(2台の)フォロワーを意味します。

2つのエントリが同じ位置番号のインデックス2を巡って争うというのが要点です。1つの位置には1つしか残れず、どちらが残るかはすでに決まっています。過半数の確認を得たほうです。

回復は静かに起きます。接続が戻ると、古いリーダーは任期2のハートビートを見て、自分の任期を 2に上げ、フォロワーに退きます。その後、新しいリーダーが「あなたのログのインデックス1が任期1なら、その後ろに realを付けなさい」と言い、古いリーダーのインデックス2は、任期が食い違うので切り落とされます。 ghostは消えます。何の警告も出ません。

ここで、選挙の制限がなぜ必要なのかがはっきりします。もし、回復の直後に古いリーダーが先にタイムアウトして候補になり、ログの長さだけで票を得られるなら、すでにコミットされたrealをghostで上書きできてしまいます。最後のエントリの任期を先に見るというルールが、その道を塞ぎます。

なぜこのような設計を受け入れるのかも、併せて見る価値があります。少数派側が書き込みを受け付けられなくするのは、可用性を捨てる選択です。分断された両側がどちらも書き込みを受け付けるようにすれば、サービスは動き続けますが、回復するときに、2つの系統の記録を人が統合しなければなりません。Raftを使うシステムは、その逆を選びます。少数派側は止まり、その代わり、回復が自動で終わります。メタデータのように「間違った値より、ない値のほうがましな」場面では、こちらが正解です。

そのため、このコースのタイトルが意味するところも、「バグを発見した」ではありません。リーダーが2人になる瞬間は正常な動作で、その瞬間にも確定された値は1つだけだというのが、このアルゴリズムの約束です。事故が起きる場所は、アルゴリズムの中ではなく、その外、つまり少数派側のリーダーが返した成功のレスポンスを、クライアントが確定と読んでしまう地点です。

現場での姿

運用では、この事件は「書き込みが成功したと言うのに、値がない」という形でやってきます。クライアントは少数派側のリーダーから成功を受け取り、数秒後に取得すると、その値がありません。ログにはエラーがありません。何も失敗していないからです。

実際の実装は、この窓を狭めようと努力します。リーダーがハートビートに対する過半数の応答を一定時間受け取れなければ、自分から退く方式(リースベース)が代表的です。etcdのドキュメントは、一時的な分断でクォーラムを失っても、ネットワークが戻ると自動的に安全に再開するが、恒久的なクォーラムの喪失は致命的だと書いています(etcd FAQ)。同じドキュメントに、 3ノードの過半数は2で耐えられる故障は1台、5ノードはそれぞれ3と2という表があります。

偶数台を使うなというアドバイスも、ここから出てきます。4ノードの過半数は3なので、耐えられる故障は 1台で3ノードと同じなのに、故障しうる機械だけが1つ増えます。etcdのドキュメントは、クラスターを 7台以下にするよう勧め、Google Chubbyが5台を提案していることも併せて書いています。

もう1つ覚えておくべきことは、「分断」がケーブルが切れることだけを意味しないという点です。ファイアウォールのルール 1つ、セキュリティグループの変更1つ、片方向だけが塞がる非対称な経路、長く停止したガベージコレクション。すべて同じ形で現れます。ノードは生きていて、プロセスも正常なのに、メッセージだけが届きません。片方だけが塞がる場合が特にたちが悪いものです。ハートビートは出ていくのに応答が戻ってこないと、リーダーは自分が話していると信じ、フォロワーは何も聞こえないまま、選挙を開きます。そのため、このラボも線を切りません。メッセージを拒否するだけで十分です。

次のラボですること

3つのノードのうち、リーダーを残りから切り離して、また戻します。Podにはファイアウォールをかける権限がないので、線を切る代わりに、互いのメッセージを拒否するスイッチを自分で作ります。2人のリーダーが同時に存在する瞬間を記録し、両側に値を1つずつ書いた後、回復したときにどちらが消えるのかを、自分の目で確認します。