- ブラウザURL入力
- DNS名前→IP
- ルータ経路選択
- ロードバランサ振り分け
- Nginx受け口
- アプリ処理
- DB保存今ここ
前回、過半数が揃わないと書けないことを見ました。今回は「その過半数を集めるのに何が要るか」を見ます。
まず結論
複数台で同じ値を決めるには、リーダーが過半数へ問い合わせて返事を待つ1往復が必ず乗ります。ただし待つのは過半数までで、遅い少数派は待ちません。
そして「返事が来ない相手が死んだのか遅いだけか」は区別できません。そのぶんを時間で埋めるのがタイムアウトで、待ち時間が実測に現れます。
3台構成の etcd で、リーダーを止めてから新リーダーが選ばれるまでの時間は、止め方(正常終了 / 強制終了)で変わるでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
決めるには、聞いて、返事をもらうしかない
前回、過半数が揃わないと書き込みが止まることを見ました。その過半数はどう集まるのでしょうか。
誰か一人が代表になり、全員に送り、過半数から返事をもらう。 離れた機械の状態は、通信して確かめる以外に知りようがありません。
Raft はまずリーダーを1人決め、次にそのリーダーが書き込みを配ります。拡張版 Raft 論文 §5.3 は、いつ確定したと言えるかをこう定義しています。
A log entry is committed once the leader that created the entry has replicated it on a majority of the servers
全台ではなく過半数です。同じ論文の §2 は共通ケースをこう書きます。
In the common case, a command can complete as soon as a majority of the cluster has responded to a single round of remote procedure calls; a minority of slow servers need not impact overall system performance
「合意は遅い」と雑にまとめるのは正しくありません。1往復ぶんの遅延は必ず乗る。しかし全員を待つわけではない。 コストは最速の過半数が返るまでの時間であって、最も遅いノードの時間ではありません。
- ・「過半数に複製した」がコミットの定義(拡張版論文 §5.3)
選挙が起きる瞬間を、ログで見る
リーダーが落ちると、残りが新しいリーダーを選びます。実測(etcd 3.5.17、3ノード、同一ホストの Docker、--heartbeat-interval 100 --election-timeout 1000)での raft ログです。
a525040065197eaa became candidate at term 4a525040065197eaa received MsgVoteResp from a525040065197eaa at term 4a525040065197eaa [logterm: 3, index: 15] sent MsgVote request to a2b2fbc7877af89 at term 4raft.node: a525040065197eaa lost leader a2b2fbc7877af89 at term 4a525040065197eaa received MsgVoteResp from a2b2fbc7877af89 at term 4a525040065197eaa has received 2 MsgVoteResp votes and 0 vote rejectionsa525040065197eaa became leader at term 4
自分に1票を入れ、他ノードへ投票依頼を送り、返事が1つ返り、合計2票で3台の過半数に達し、リーダーになる。 往復が3行に見えています。
そして term 4 という数字。拡張版 Raft 論文 §5.1 はこう書いています。
Terms act as a logical clock [14] in Raft
この [14] は Lamport 1978 です。 本コースで「壁時計を諦めて論理時計に置き換える」と見た考え方が、Raft では term という単調増加する整数として入っています。実測でも term が 3 → 4 → 5 → 6 と増えました。
Raft で「書き込みがコミットされた」と言えるのは、どの時点ですか。
返事が来ない相手を、どう扱うか
ここで壁に当たります。返事が来ないとき、相手が死んだのか、遅いだけなのかは区別できません。
これを扱ったのが FLP の不可能性(Fischer-Lynch-Paterson 1985)です。ただし流布している「非同期では合意は不可能」という要約は不正確なので、慎重に読みます。
そのうえで同じ論文の Theorem 2 は、条件を足せば決まることを示しています。逐語は provided no processes die during its execution and a strict majority of the processes are alive initially。前回の過半数が不可能性の論文の中に出てきます。
前提のうち決定的なのは「タイムアウトが使えない」です。Raft も etcd もタイムアウトを使うので、FLP の前提の外にいます。 これが「実装はタイミングの仮定を置く」の中身です。拡張版 Raft 論文 §5.6 は、その仮定を不等式として挙げ、
broadcastTime ≪ electionTimeout ≪ MTBF
同じ節で時間との関係を二段構えで述べています。
safety must not depend on timing ... However, availability (the ability of the system to respond to clients in a timely manner) must inevitably depend on timing
ログが矛盾することはない。しかし進まなくなることはある。 「Raft は時計に依存しない」と一文で書くと誤りです。なお、この不等式を置くことを部分同期と呼ぶのは本教材側の用語付けで、論文はその語を使っていません。論文は FLP にも言及していません。
区別できないぶんが、1秒として現れる
「死んだのか遅いのか区別できない」は抽象論ではなく、待ち時間として実測に出ます。 同じ3ノードの etcd で、リーダーの止め方だけを変えて各3回測りました。
止め方 1回目 2回目 3回目SIGTERM(正常終了) 89 ms 108 ms 129 msSIGKILL(強制終了) 1150 ms 1531 ms 1571 ms
一桁違います。 SIGTERM では etcd が終了処理をしてから落ちるので、残りは待たずに選挙を始められます。SIGKILL では何も告げずに消えるため、残りは election timeout の 1000ms が切れるまで「まだ生きているかもしれない」と待つしかありません。強制終了のログにだけ became pre-candidate が現れるのも、その待ちの表れです。拡張版 Raft 論文 §5.6 の記述とも噛み合います。
When the leader crashes, the system will be unavailable for roughly the election timeout
なお合意のコストはネットワークだけではありません。etcd 公式 FAQ は This is intentional; disk latency is part of leader liveness. と、ディスクの遅さが生存判定に効くことを明言しています。
FLP の不可能性が否定しているのは、次のうちどれですか。
Raft のリーダー故障検出
リーダーからの連絡が途切れたとき、落ちたのか遅いだけなのかを残りは区別できません。election timeout ぶん待って選挙を始めます。実測では、告げずに消えた場合だけ1秒級の待ちが出ました。
止め方 相手の状態の告知 確定までSIGTERM あり 89-129 msSIGKILL なし 1150-1571 ms
TCP の再送(第23週)
送ったセグメントにACKが返らないとき、失われたのか経路が混んで遅れているだけなのかを送信側は区別できません。再送タイマが切れるまで待って送り直します。
原因 送信側が見るもの 取る行動失われた ACKが来ない タイマ満了で再送遅れている ACKが来ない タイマ満了で再送
リーダーの故障検出とTCPの再送。層も目的も違いますが、共通する構造は何でしょうか。
「観測できるもの」と「区別したい原因」が何個あるかを、両方で数えてみてください。
この章のまとめ
- 合意には必ず1往復ぶんの遅延が乗る。ただし待つのは過半数までで、遅い少数派は待たない(拡張版 Raft 論文 §2・§5.3)。
- Raft の term は論理時計。拡張版論文 §5.1 が Lamport 1978 を引いている。
- FLP が潰すのは停止性であって安全性ではない。しかも「決まらない実行が存在する」。論文自身が実務で解けないとは言っていないと明記し、Theorem 2 は厳密な過半数が生きていれば決まることを示している。
- FLP はタイムアウトが使えない前提の定理。Raft も etcd もタイムアウトを使うので、その前提の外にいる。
- Raft の時間との関係は二段構え。安全性は時間に依存しない / 可用性は必ず依存する(拡張版論文 §5.6)。
- 区別できないぶんは待ち時間として現れる。実測では止め方だけで 89-129 ms と 1150-1571 ms の差。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
「Raft は時計に依存しないので、時刻がずれても影響がない」という説明の問題点はどこですか。
用語集(5語)
- コミット(Raft)
- そのエントリを作ったリーダーが過半数に複製し終えた状態。全台への複製は条件ではない(拡張版論文 §5.3)。
- term(任期)
- Raft の単調増加する番号。拡張版論文 §5.1 は「Terms act as a logical clock [14] in Raft」と書き、[14] は Lamport 1978。
- election timeout
- 連絡が途切れてから選挙を始めるまでの待ち時間。本教材の実測では 1000ms。拡張版論文が例に挙げる 150–300ms は etcd の既定値ではない。
- FLP 不可能性
- 完全な非同期モデルで1台の停止故障があると、決まらないまま終わらない実行が存在するという定理(Fischer-Lynch-Paterson 1985)。潰れるのは停止性であって安全性ではない。
- broadcastTime ≪ electionTimeout ≪ MTBF
- 拡張版 Raft 論文 §5.6 が安定したリーダーを保つ条件として挙げる不等式。左からRPC往復の平均、選挙の待ち、平均故障間隔。