[[397422]]

發(fā)現(xiàn)之前寫的 Raft 文章并沒有分析過 Figure 8 的問題，而這張圖比較容易讓人產(chǎn)生歧義，群里討論過不止一次。在這里談?wù)勎业睦斫狻?/p>

Figure 8 用來說明為什么 Leader 不能提交之前任期的日志，只能通過提交自己任期的日志，從而間接提交之前任期的日志。

先按錯誤的情況，也就是 Leader 可以提交之前任期的日志。那么上述的流程：

• (a) S1 是任期 2 的 Leader(仔細(xì)看，有個黑框)，日志已經(jīng)復(fù)制到了 S2。
• (b) S1 宕機(jī)，S5 獲得 S3、S4 和 S5 的選票成為 Leader，然后寫了一條日志 index=2 & term=3。
• (c) S5 剛寫完就宕機(jī)了，S1 重新當(dāng)選 Leader，currentTerm = 4，此刻還沒有新的請求進(jìn)來，S1 將 index=2 & term = 2 的日志復(fù)制到了 S3，多數(shù)派達(dá)成，S1 提交了這個日志(注意，term=2 不是當(dāng)前任期的日志，我們在討論錯誤的情況)。然后請求進(jìn)來，剛寫了本地 index=3 & term=4 的日志，S1 就故障了。
• (d) 這時候 S5 可以通過來自 S2、S3、S4 和自己的投票，重新成為 Leader(currentTerm>=5)，并將 index=2 && term=3 的日志復(fù)制到其他所有節(jié)點并提交，此時 index=2 的日志提交了兩次!一次 term=2，一次term=3，這是絕對不允許發(fā)生的，已經(jīng)提交的日志不能夠被覆蓋!
• (e) 這里的情況是，S1 在宕機(jī)之前將自己 term=4 的日志復(fù)制到了大多數(shù)機(jī)器上，這樣 S5 就不可能選舉成功。這是 S1 不發(fā)生故障，正確復(fù)制的情況。

這里主要通過 (c) 和 (d) 來說明問題所在。其實這張圖用 Raft 大論文的圖會比較好理解。(d) 和 (e) 分別對應(yīng) term=4 有沒有復(fù)制到多數(shù)派的情況。

所以，我們要增加提交的約束，不讓 (d) 這種情況發(fā)生。這個約束就是，Leader 只能提交自己任期的日志。

我們再來看看，加了約束后會變成什么樣?前面 (a) 和 (b) 沒有任何改變，我們從 (c) 開始。

• (c) 還是將 index=2 & term=2 復(fù)制到大多數(shù)，由于 currentTerm = 4，所以不能提交這條日志。如果 S1 將 term = 4 的日志復(fù)制到多數(shù)派，那么 Leader 就可以提交日志，index=2 & term=2 也會間接一起提交，其實這就是 (e) 的情況，1-2-4 都被提交。
• (d) 的情況我覺得是理解問題的關(guān)鍵。如果 S1 只將 term=4 寫入自己的日志，然后宕機(jī)了;S5 選舉成功成為 Leader，然后將 index=2 & term=3 的日志復(fù)制到所有節(jié)點，現(xiàn)在 index=2 是沒有提交過的，S5 能提交 index=2 & term=3 的日志嗎?

答案是不能。因為 S5 在 S1(term=4) 選舉出來后 currentTerm 至少是 5，也可能是 6、7、8……我們假設(shè)就是 5，但這條日志 term = 3，Leader 不能提交之前任期的日志，所以這條日志是不能提交的。只有等到新的請求進(jìn)來，超過半數(shù)節(jié)點復(fù)制了 1-3-5 后，term=3 的日志才能跟著 term=5 的一起提交。

雖然加了這個約束不會重復(fù)提交了，但如果一直沒新的請求進(jìn)來，index=2 & term=3 豈不是就一直不能提交?那這里不就阻塞了嗎?如果這里是 kv 數(shù)據(jù)庫，問題就很明顯了。假設(shè) (c) 或 (d) 中 index=2 那條日志里的 Command 是 Set("k", "1")，S5 當(dāng)選 Leader 后，客戶端來查詢 Get("k")，Leader 查到日志有記錄但又不能回復(fù) 1 給客戶端(因為按照約束這條日志未提交)，線性一致性要求不能返回陳舊的數(shù)據(jù)，Leader 迫切地需要知道這條日志到底能不能提交。

所以 raft 論文提到了引入 no-op 日志來解決這個問題。這個在 etcd 中有實現(xiàn)。

引入 no-op 日志

no-op 日志即只有 index 和 term 信息，command 信息為空。也是要寫到磁盤存儲的。

具體流程是在 Leader 剛選舉成功的時候，立即追加一條 no-op 日志，并立即復(fù)制到其它節(jié)點，no-op 日志一經(jīng)提交，Leader 前面那些未提交的日志全部間接提交，問題就解決了。像上面的 kv 數(shù)據(jù)庫，有了 no-op 日志之后，Leader 就能快速響應(yīng)客戶端查詢了。

本質(zhì)上，no-op 日志使 Leader 隱式地快速提交之前任期未提交的日志，確認(rèn)當(dāng)前 commitIndex，這樣系統(tǒng)才會快速對外正常工作。

另外說一句，6.824 的實驗不需要實現(xiàn) no-op 日志。

這個問題之前阿里巴巴團(tuán)隊稱之為“幽靈復(fù)現(xiàn)”，參見《如何解決分布式系統(tǒng)中的“幽靈復(fù)現(xiàn)”?》，里面討論了 Paxos、Raft 和 Zab 的解決方案。

本文轉(zhuǎn)載自微信公眾號「多顆糖」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系多顆糖公眾號。