Raftは複数serverのreplicated logを同じ順序で確定するためのconsensus algorithmです。leader processが動いているだけでは安全に変更を確定できず、cluster quorumとの通信が必要です。Raft論文は選挙・複製・commit規則を説明し、etcd用語集はquorumをcluster状態変更に必要なactive member数と定義します。

quorumにはleaderも数える

member数Nのquorumはfloor(N/2)+1です。3台なら2台、5台なら3台です。leaderもmemberの一台として数えます。3台構成でleaderとfollower一台が同じlog entryを持てば、2/3のmajorityに達します。「leader以外のfollowerの過半数」が必要なわけではありません。

この計算はmajorityを維持したまま応答できないmember数も示します。3台では1台、5台では2台までです。quorumがない側では新leaderを選出したり変更を安全にcommitしたりできません。minority partitionに以前のleader processが残っても、それだけでwrite権限は得られません。

election termとreplicationを区別する

termは選挙を区切る論理的なepochです。candidateが投票を求め、majorityを得るとleaderになります。leaderはAppendEntriesでfollowerへlogを複製します。followerはtermとlog整合性の規則で受信内容を判断し、選挙ではより新しいlogを持つcandidateが優先されるよう制約します。

障害調査ではleader名だけでなく、current term、通信可能なmember数、leaderがどこまで複製したかを確認します。follower一台が遅くてもmajorityと接続できれば進められますが、majorityを失うと安全なcommitは止まります。

commit判断ではcurrent termが重要

leaderは過去termのentryがmajorityに複製されたという理由だけで、そのentryを直接commitできません。Raft論文はcurrent termのentryがmajorityに複製されたときにcommitを進める規則を示します。そのentryがcommitされれば、log-matching propertyにより先行entryも間接的にcommitされます。

これは以前のleaderが複製したものの確定できなかったentryを新leaderが上書きし得る状況を安全に扱います。「半数を超えるnodeに存在する」と「clientに確定値として返せる」は同じではありません。replica数だけでwrite成功を推測しないでください。

network partition時の期待

3台のclusterでAが最初のleaderだったとします。AがBとCの両方との通信を失うと、Aは少数側に分かれ、接続を保つBとCが2/3のmajorityになります。BとCは新leaderを選出し、現在のtermのlog entryをmajorityへ複製してcommitできます。Aのprocessは自分をleaderだと思い続ける場合がありますが、quorumがないため新しいentryを安全にcommitできません。通信が戻ると、Aはより高いtermに従い、競合する未commit logはRaftのlog matching規則で整合します。

導入前にはprocess数だけでなく、failure domain、network partition、再起動時のmembership設定も確認します。Raftはconsensus規則であり、application retry、idempotency、backup、disaster recoveryの代わりにはなりません。

参考資料