LogPosition::is_newer_or_equal_than の定義ミスによって生じる無限ループについて

[yuezato]

Leaderがいつまで経っても決まらずに、無限ループとなりサービス不能となるバグがあるのでそれについて述べる。

is_newer_or_equal_than とは?

中身（定義）は次節で述べるとして、どこで使われていて、直感的な意味は何かをまず述べる。

Common::handle_message

raftlog/src/node_state/common/mod.rs

Lines 300 to 304 in 05c3d32

	/// 受信メッセージに対する共通的な処理を実行する.
	pub fn handle_message(&mut self, message: Message) -> HandleMessageResult<IO> {
	if self.local_node.role == Role::Leader
	&& !self.config().is_known_node(&message.header().sender)
	{

が（テストコードを除くと）唯一使用されている箇所である。特に次の箇所である:

raftlog/src/node_state/common/mod.rs

Lines 325 to 330 in 05c3d32

	let next_state = if let Message::RequestVoteCall(m) = message {
	if m.log_tail.is_newer_or_equal_than(self.history.tail()) {
	// 送信者(候補者)のログは十分に新しいので、その人を支持する
	let candidate = m.header.sender.clone();
	self.transit_to_follower(candidate, Some(m.header))
	} else {

これは raft論文 https://raft.github.io/raft.pdf の Figure2 RequestVote RPCの

If votedFor is null or candidateId, and candidate’s log is at least as up-to-date as receiver’s log, grant vote

に対応しているだろう。ここで up-to-date というのは論文の5.4.1節で定義されている全順序である。詳しくは下の方で述べる。

一言で言うなれば、is_newer_or_equal_than は leader node を決定する上で鍵となる述語である。
これは、上で抜粋したコードで行っている計算からも明らかである（下は無理やり日本語にしたもの）:

325行目

RequestVoteを他のノード X から受け取った時に

326行目

相手のlogの最新情報が、自分のlogの最新情報と同じかそれ以上に新しい（すなわち、least as up-to-date）ならば

328--329行目

Xに投票して、自分自身はfollowerになる

現在の定義

現在のraftlogでは、LogPosition上の順序 is_newer_or_equal_than が以下のように定義されている:

raftlog/src/log/mod.rs

Lines 272 to 274 in 05c3d32

	pub fn is_newer_or_equal_than(&self, other: LogPosition) -> bool {
	self.prev_term >= other.prev_term && self.index >= other.index
	}

Note: LogPosition は term と index の組:

raftlog/src/log/mod.rs

Lines 233 to 241 in 05c3d32

	/// ログの特定位置を識別するためのデータ構造.
	#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, Hash)]
	pub struct LogPosition {
	/// 一つ前のインデックスのエントリの`Term`.
	pub prev_term: Term,
	/// この位置のインデックス.
	pub index: LogIndex,
	}

現在の順序は、 (termL, indexL) ≽ (termR, indexR) が成立するのは直積順序が成立する時、すなわち

(termL, indexL) ≽ (termR, indexR) iff termL >= termR  AND  indexL >= indexR

を要求している。

期待される定義

is_newer_or_equal_than は、raft論文 https://raft.github.io/raft.pdf の 5.4.1 節 の最後にあるパラグラフ:

Raft determines which of two logs is more up-to-date by comparing the index and term of the last entries in the logs. If the logs have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up-to-date.

に対応していると考えられる。このパラグラフが要求しているのは辞書式順序

(termL, indexL) ≽ (termR, indexR) iff  termL > termR   OR    (termL = termR AND indexL >= indexR)

２つの定義の違いと、それによる問題点

• 現在採用している直積順序は全順序ではない（全順序２つからなる直積順序は一般に半順序）
• 一方で論文の辞書式順序は全順序（全順序２つからなる辞書式順序は一般に全順序）

全順序でない順序をLeaderの裁定基準に採用する場合には、優劣を決定できないために計算が次のステージ/Termに持ち越され、次のステージ/Termでも結局判断出来ず、これが繰り返されいつまでも決定できないということが起きうる。

実際に、無限ループとなりLeaderがいつまでも決定できずクラスタが使用不能になる例について
上里の再現用ブランチを確認されたい。

修正方法 と 気になる点

修正方法については、論文の定義に直すだけで良い。

一方で、全順序とならないことを承知の上で、現在の定義を採用した可能性がある:

raftlog/src/log/mod.rs

Lines 265 to 266 in 05c3d32

	/// // `a`の方がインデックスは大きいが、`b`の方が`Term`は大きい
	/// // => 順序が確定できない

USENIXに公開されているバージョン https://www.usenix.org/node/184041. から
up-to-date の定義は変わらず辞書式順序のままなので、
辞書式順序版になにかミスがあることを見越して異なる定義を採用した可能性がある。

あるが、この辞書式順序はRaftアルゴリズムの根幹を支える直観と密接に関係していることと、
多少粘った程度では「辞書式順序で問題がある＝論文の安全性をひっくり返す」ようなことは示せていないので、
論文の定義に戻したい。

[sile]

詳細にありがとうございます。

実装当時の詳細はうろ覚えなので、適切なことを即答はできないのですが「期待される定義」に記載されている以下の定義に単純に書き換えてしまって大丈夫なのかどうかは、若干気になっています。

(termL, indexL) ≽ (termR, indexR) iff  termL > termR   OR    (termL = termR AND indexL >= indexR)

理由としては、Raftのアルゴリズム的にtermはいろいろな理由で大きな値になることがあり、その場合にtermだけみて次のリーダを決めてしまうと、不整合が発生するのではないかと思いました。
（e.g., 既にリーダが確立している状態で、特定のノードがネットワーク的に孤立した場合、その孤立ノードは新選挙の開始とタイムアウトを繰り返して無限にtermがインクリメントされる。その後ネットワークが復帰した場合にtermの大小だけをいmると、その孤立ノードが勝ってしまう）

ちょっと、issueの内容を完全に把握している訳ではないのと、Raftの論文もうろ覚えなので、時間がある時にでも再確認してみます 🙇
（ただ、そのための十分な時間がいつ取れるかは不明なので、あくまでも参考程度の意見と考えて貰えると助かります）

[yuezato]

コメントありがとうございます。

Ohtaさんのコメントは至極真っ当で、明らかにしておかなければならない点だと思います。

まず、定義中の

(termL, indexL) ≽ (termR, indexR) iff  termL > termR   OR    (termL = termR AND indexL >= indexR)

の termL 及び termR は、

• logをLogPositionのなす列として見た時の、logに含まれている 最終エントリ のtermであり
• Nodeが抱えているcurrentTermではない

というところが注意を要する点だと思います。up-to-date順序はlog上の全順序で、currentTermの値とは独立しています。

いま急いで付け足さなければならないのは次の点です（具体例は以降で見ます）:

• 論文のnodeの定義通り、currentTerm だけが巨大な（leaderとしてqualifiedではないlogを持つ）node NからのVoteCallを、健全なleaderが受け取ると、followerになってしまう;
• しかし一方で、currentTerm だけが巨大でlogがqualifiedでないNは、論文のup-to-date順序によって leader になることはない。

これは、Ohtaさんが気にしている（であろう）

qualifiedなlogを持たないTermだけが巨大なnodeがleaderになると、
データ上大幅な巻き戻りが生じて、例えばcommitted entryが消去されてしまう

といった状況が辞書式順序でも起こらないということを保証しています。

---

上記「currentTermだけが大きいnodeはleaderになれない」を確認するために、次のようなconfigurationを考えたいです:

A: { currentTerm = 2, log = (Term 1, Index 1) (Term 1, Index 2) (Term 2, Index 3) (Term 2, Index 4) ... (Term 2, Index 100) }

B: { currentTerm = 10000, log = (Term 1, Index 1) }

話を簡単にするために、Index 99がcommittedだとします。

これは

• ノードAがTerm2のリーダーを勝ち取ってからは、今現在まで平穏に計算が続いていて、ログの長さは100まで伸びている
• ノードBはTerm1の早い段階でネットワーク的に孤立した

という状況を反映しています。

さて、この状態で B がネットワークに復帰して、VoteCallをbroadcastする場合を考えます。

• まずAがBからVoteCallを受け取った場合ですが
  • BのcurrentTerm = 10000 > Aのそれ = 2 なので、Aは一旦、followerに戻ってしまいます（これは Figure2の Rule for Servers -> All Servers から）
  • ただし、自分=(Term 2, Index 100) ≽ VoteCall主=(Term 1, Index 1) なので B には 投票しません 。
• A以外のノードがBからVoteCallを受け取った場合ですが
  • Aとまともに通信できていた場合にはlast entryのtermは 2 であるはずなので Bには 投票しません 。

結局のところ

1. いま、index 99まではcommittedだとしているので、Bが過半票を得ることはないです。
2. よって、タイムアウトを契機として、例えばAあたりが currentTerm = 10001 として再びVoteCallを行って（他のNodeとの票のsplitはあるかもしれませんが）再びleaderになる

ということになります。

参考になっていれば幸いです。

[sile]

ありがとうございます。後でまたちゃんと確認させて貰います 🙇

[yuezato]

スパッと納得に通じるとそれに越したことはないのですが、そうでない場合は
「そうは言ってもこの辺とかこの辺が釈然としないんだよな〜」とか
「こうしたらどうなるんだ」という様な素朴なコメントも頂けると、
多角的にRaftの論文そのものが検証でき大変助かるのでお願いします 🙏

[sile]

この件、全く確認できていないですが、十月には少し時間ができる予定なので、そこで対応しようと思っています（既に一ヶ月放置してしまっていますが、一応情報共有）。

[yuezato]

ありがとうございます。
このissueに動きがなかったのは、Ohtaさんの反応待ちというよりも、こちらが時間を取れず、それで止まっていました。

現状のコードだと極端な場合に困るので、論文の順序の定義を採用したいという話なのですが、
その時に気になるのは

• これまでの順序の定義を前提に書かれている箇所は、順序の定義を差し替えるだけだと問題になるかもしれないので、そこを明らかにしたい
  • とはいえ、自分では現在の順序の定義を前提にしている箇所はコード中にはないと思っています
• パフォーマンスの話

あたりだと思うのですが、他になにかありそうでしょうか。

[sile]

上記以外で気になる点は特にないですね。
（自分のモチベーションとしては「ちゃんと理解しておきたい」というのが一番大きいので、そもそも変更すること自体はそこまで気になってはいなかったりもします）

[yuezato]

「ちゃんと理解しておきたい」というのが一番大きい

どれだけ頷いても頷き足りないほど同意です。

ひとまず上のdescriptionは
超具体的なレベル---直積順序だと問題になるケースがあり、辞書式順序だとその問題は少なくとも解消できる---の
理解の一助になると嬉しいです。

一方でより深いレベルの話については……　これは相当難しいと思っています。
それはそれで何とかしたいと心底思っているのですが、
少なくともこのissueのscopeは遥かに超えていると思っていて、
ですので、今回は一応の限られた範囲での解決を、ひとまず目指していると思ってもらえると幸いです 🙇

[sile]

だいぶ遅くなってしまいましたが、改めてissue/実装/論文を確認させて貰いました。

結論から言えば「@yuezatoさんが提案されている内容に修正して問題なさそう（というかそちらの方が確かに論文通りになっていて良さそう）」ということになります。

最初にコメントを書いていた時に、↓の点を失念していたのが混乱の原因でした...。

- logをLogPositionのなす列として見た時の、logに含まれている 最終エントリ のtermであり
- Nodeが抱えているcurrentTermではない

詳細な説明をありがとうございました 🙏