タイマーが全て同じなら誰も勝てない

一言でいうと

合意は、「誰が正しいか」を決めることではなく、「誰が話す番か」を決めることで、Raftはそれを、任期(term)と過半数の投票という2つの仕組みだけで解決します。そして、その選挙が終わるには、タイマーが互いに異なっている必要があります。

なぜ必要なのか

サーバー3台に同じ値を保存するとしましょう。クライアントが3台にそれぞれ書き込みを送ると、ネットワークの遅延のために到着順序が変わり、3台の記録がずれます。そのため、実務の答えはいつも同じです。書き込みを受け付ける場所を1つに決めて、残りはその1つに従います。問題は、「その1つ」が落ちたときです。誰が次の番なのかを誰も決めてくれない状態で、残ったサーバー同士でそれを決めなければなりません。

人が介入すればよいのではないか、という疑問が自然に出てきます。実際に長い間そうしてきましたし、今でも多くのデータベースのレプリケーションが、昇格(promotion)を人の手に委ねています。しかし、人が介入するには分単位の時間がかかり、その間、サービスは書き込みを受け付けられません。さらに悪いのは、人も間違えるということです。元のリーダーが実は生きていたのにネットワークだけが切れていたなら、昇格した瞬間に、書き込みを受け付ける場所が2つになります。

Raftの論文(Diego Ongaro、John Ousterhout)は、この問題を理解できる形で解くことを目標にしました。公式サイトは、Raftを「理解しやすいように設計された合意アルゴリズムで、耐障害性と性能の面でPaxosと同等」と紹介しています (raft.github.io)。論文の短縮版は、 2014年のUSENIX ATCで最優秀論文賞を受賞しました。

どう動くのか

Raftの時間は、任期で進みます。任期は1ずつ上がるだけの整数で、1つの任期にリーダーは最大1人です。リーダーがいなければ任期が1つ上がり、新しい選挙が開かれます。すべてのメッセージに送信側の任期が載っているので、2つのノードが出会うと、ルールは単純になります。より大きな任期を見た側が、自分の任期をその値に上げて、フォロワーに退きます。より小さな任期のリクエストは拒否しますが、自分の任期をそちらに下げることはしません。

選挙は、3行で終わります。

1. 리더 소식이 타임아웃만큼 끊기면 → 임기 +1, 후보가 되어 자기에게 한 표
2. 나머지에게 투표를 요청 → 받는 쪽은 '한 임기에 한 표' 만 준다
3. 과반을 받으면 리더. 과반은 절반 이상이 아니라 절반 초과다

このコードブロックの韓国語コメントは、順に、リーダーの知らせがタイムアウトの時間だけ途絶えたら、任期を1上げて候補になり、自分に1票を入れること、残りに投票を要求し、受け取る側は1つの任期につき1票だけ与えること、過半数を得たらリーダーになること(過半数は半分以上ではなく、半分超)を述べています。

過半数という条件が担う役割は1つです。2つの過半数は必ず重なります。5台のうち3台の集合を2つ、どう選んでも、少なくとも1台は両方に入ります。その1台が1つの任期に1票しか与えないので、同じ任期にリーダーが2人になることは起こりえません。raft.github.ioは、この性質を「サーバーのどの過半数でも生きていれば進行する。たとえば、5台のクラスターは2台が落ちても動作し続ける」と書いています。

残るのは、タイマーです。3つのノードのタイムアウトがまったく同じだと、3つが同じ瞬間に候補になり、それぞれ自分に1票ずつ与えて、互いには与えません。誰も過半数に届かないまま、任期だけが上がります。そのため、Raftはタイムアウトを一定の区間の中でランダムに選びます。先に目覚めた 1つが、残りが目覚める前に票を集めれば、選挙は1回で終わります。

ここで、1つはっきりさせておくとよいでしょう。選挙は、「どちらがより良いノードか」を選ぶことではありません。性能も、リソースも、最近の負荷も見ません。見るのは2つだけです。先に目覚めたか、そして(ログができてからは)ログが遅れていないか。この単純さが、アルゴリズムを理解できるものにする一方で、「なぜよりによってあのノードがリーダーになったのか」という質問に対する答えを、味気ないものにします。答えは、たいてい「タイマーが先に鳴ったから」です。

リーダーがすることも、思ったより少ないものです。値を受け取り、残りに伝え、生きているという合図を送り続けます。その合図がハートビート(heartbeat)で、話すことがなくても送り続けます。沈黙と死を区別する方法が、それしかないからです。フォロワーは、ハートビートが届くたびに、タイマーを最初に戻します。そのため、選挙が再び開かれる条件は、「リーダーが死んだとき」ではなく、 ハートビートがタイムアウト内に届かなかったときであり、この2つの違いが、運用の事故の大部分を説明します。

現場での姿

運用では、この話はたいてい「任期が上がり続ける」という警告として現れます。etcdのドキュメントは、リーダーが生きているのにハートビートが間に合わないと、「無用な選挙(spurious election)」が起きると書き、遅延の大きい環境では、heartbeat-intervalとelection-timeoutを調整するよう案内しています(etcd FAQ)。ディスクが遅くなって書き込みが滞ったり、GCが長く停止したりすると、ノードは正常なのにハートビートだけが遅れて、選挙が繰り返されます。その間、クラスターは書き込みを受け付けられません。

逆の方向の事故もあります。タイムアウトを長くしすぎると、本当にリーダーが落ちたとき、その分だけ長く止まってしまいます。選挙のタイムアウトは、「どれだけ早く気づくか」と「どれだけ頻繁に無駄に驚くか」の間のつまみで、どちらの方向も障害に見えます。

次のラボですること

ポートだけが異なるプロセスを3つ起動して、選挙を自分で実装します。HTTPサーバーとタイマーのような配線は用意してあり、任期の比較・投票・過半数の判定のような判断する関数だけを書きます。最後のステップでは、 3つのノードのタイムアウトを同じに合わせて、9秒間見守ります。リーダーが選ばれず、任期だけが上がるのを、自分の目で見ることになります。