[[421736]]

本文選自我在知乎的回答。

《設(shè)計(jì)數(shù)據(jù)密集型應(yīng)用》(即 DDIA)中提到 Raft 的一個(gè)問(wèn)題，即，Raft 算法存在一種失去活性(liveness)的極端情況：如果有一條網(wǎng)絡(luò)連接不可靠，Raft 當(dāng)前領(lǐng)導(dǎo)者會(huì)不斷被迫下臺(tái)導(dǎo)致系統(tǒng)實(shí)質(zhì)上毫無(wú)進(jìn)展。

我們先來(lái)具體描述一下該問(wèn)題。

如圖所示的 4 節(jié)點(diǎn) Raft 集群，其中有一個(gè)節(jié)點(diǎn)和其他三個(gè)網(wǎng)絡(luò)不太穩(wěn)定，假設(shè)它能發(fā)送消息給別的節(jié)點(diǎn)但收不到其他節(jié)點(diǎn)的消息，那么它就會(huì)一直收不到心跳消息，然后轉(zhuǎn)為 candidate 自增任期并發(fā)起新的選舉，來(lái)自更大任期的 RequestVote 請(qǐng)求會(huì)導(dǎo)致現(xiàn)在的 Leader 下臺(tái)重新選舉。這樣一直反復(fù)，會(huì)導(dǎo)致集群無(wú)法正常工作。

Raft 大論文提到一種解決方式是加入一個(gè)新的 PreVote 階段，etcd 就這么干了，為此增加了一種新的節(jié)點(diǎn)狀態(tài)叫做 PreCandidate 狀態(tài)。

PreVote 階段作用是當(dāng)一個(gè)節(jié)點(diǎn)想要發(fā)起選舉時(shí)，首先要確認(rèn)自己確實(shí)有資格贏得投票而不是在浪費(fèi)時(shí)間，才會(huì)真的自增任期發(fā)起新的選舉。

PreVote 階段的具體流程是，在發(fā)起真正的選舉之前，先發(fā)送 PreVote 消息給所有節(jié)點(diǎn)， PreVote消息和 RequestVote 消息一樣，但節(jié)點(diǎn)不會(huì)自增自己的任期，只會(huì)增加消息中的 term 參數(shù)。

收到 PreVote 消息的節(jié)點(diǎn)同意重新選舉的條件是：

參數(shù)中的任期更大，或者任期相同但 log index 更大;

至少一次 election timeout 時(shí)間內(nèi)沒(méi)有收到領(lǐng)導(dǎo)者心跳;

只有超過(guò)半數(shù)節(jié)點(diǎn)同意 PreVote 消息，該節(jié)點(diǎn)才能真正去自增任期并發(fā)起新的選舉。

回到上述情況，網(wǎng)絡(luò)鏈路有問(wèn)題的那個(gè)節(jié)點(diǎn)在 PreVote 階段會(huì)發(fā)現(xiàn)自己無(wú)法贏得超過(guò)半數(shù)節(jié)點(diǎn)同意自己發(fā)起選舉(別的節(jié)點(diǎn)都能收到心跳)，因此不會(huì)自增任期去干擾 Leader 工作。

問(wèn)題解決了嗎?

問(wèn)題并沒(méi)有解決，只有 PreVote 階段還可能有一種極端情況會(huì)導(dǎo)致 Raft 失去活性。如圖所示：

圖中是一個(gè) 5 節(jié)點(diǎn)組成的 Raft 集群，故障發(fā)生之前 4 是 Leader?，F(xiàn)在故障發(fā)生了，5 宕機(jī)了，同時(shí) 4 只和 2 保持連接，1、2、3互相保持連接。這種情況下 1、3 收不到 Leader 的心跳，會(huì)發(fā)起 PreVote請(qǐng)求，但由于 2 能收到 Leader 節(jié)點(diǎn) 4 的心跳，所以 2 不會(huì)同意 PreVote 請(qǐng)求，因此節(jié)點(diǎn) 1、3 無(wú)法獲得多數(shù)派的 PreVote 同意。

該集群的問(wèn)題是，無(wú)法選舉出新的 Leader，但舊的 Leader 又只能 AppendEntries 到兩個(gè)節(jié)點(diǎn)(2和自己)，無(wú)法達(dá)成多數(shù)派，整個(gè)集群無(wú)法取得任何進(jìn)展，不滿足活性。

此處 Raft 協(xié)議明明可以容忍 2 個(gè)節(jié)點(diǎn)故障，但增加了 PreVote 階段后反而無(wú)法容忍僅僅 1 個(gè)節(jié)點(diǎn)故障，其實(shí)沒(méi)有 PreVote 階段的話，1 和 3 是有機(jī)會(huì)當(dāng)選 Leader 推進(jìn)整個(gè)系統(tǒng)正常工作的。

因此 Raft 還需要增加一種機(jī)制來(lái)讓 Leader 主動(dòng)下臺(tái)。

這個(gè)機(jī)制很簡(jiǎn)單：Leader 沒(méi)有收到來(lái)自多數(shù)派節(jié)點(diǎn)的 AppendEntries 響應(yīng)時(shí)就主動(dòng)下臺(tái)。這樣，圖中 1、2 和 3 都有機(jī)會(huì)當(dāng)選新的 Leader，整個(gè)集群依舊可以正常工作。

etcd 把這叫做 CheckQuorum，etcd 的 issue 中有關(guān)于此問(wèn)題的討論：https://github.com/etcd-io/etcd/issues/3866

CheckQuorum 確保了如果當(dāng)前 Leader 無(wú)法連接到多數(shù)派節(jié)點(diǎn)，它將會(huì)下臺(tái)并選舉出新的 Leader。PreVote 確保一旦 Leader 當(dāng)選，整個(gè)系統(tǒng)將是穩(wěn)定的，Leader 不會(huì)被迫下臺(tái)。

那么 PreVote + CheckQuorum 可以解決活性問(wèn)題了嗎?

可以了!