DDIA 對(duì) Raft 的這種極端場(chǎng)景的描述,要如何理解?
本文選自我在知乎的回答。
《設(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)題了嗎?
可以了!