[[318383]]

阿里妹導(dǎo)讀：“幽靈復(fù)現(xiàn)”的問題本質(zhì)屬于分布式系統(tǒng)的“第三態(tài)”問題，即在網(wǎng)絡(luò)系統(tǒng)里面，對于一個請求都有三種返回結(jié)果：成功，失敗，超時未知。對于超時未知，服務(wù)端對請求命令的處理結(jié)果可以是成功或者失敗，但必須是兩者中之一，不能出現(xiàn)前后不一致情況。

1、“幽靈復(fù)現(xiàn)”問題

我們知道，當(dāng)前業(yè)界有很多分布式一致性復(fù)制協(xié)議，比如Paxos，Raft，Zab及Paxos的變種協(xié)議，被廣泛用于實現(xiàn)高可用的數(shù)據(jù)一致性。Paxos組通常有3或5個互為冗余的節(jié)點組成，它允許在少數(shù)派節(jié)點發(fā)生停機故障的情況下，依然能繼續(xù)提供服務(wù)，并且保證數(shù)據(jù)一致性。作為一種優(yōu)化，協(xié)議一般會在節(jié)點之間選舉出一個Leader專門負責(zé)發(fā)起Proposal，Leader的存在，避免了常態(tài)下并行提議的干擾，這對于提高Proposal處理的效率有很大提升。

但是考慮在一些極端異常，比如網(wǎng)絡(luò)隔離，機器故障等情況下，Leader可能會經(jīng)過多次切換和數(shù)據(jù)恢復(fù)，使用Paxos協(xié)議處理日志的備份與恢復(fù)時，可以保證確認形成多數(shù)派的日志不丟失，但是無法避免一種被稱為“幽靈復(fù)現(xiàn)”的現(xiàn)象?？紤]下面一種情況：

如上表所示，在第一輪中，A成為指定Leader，發(fā)出1-10的日志，不過后面的6-10沒有形成多數(shù)派，隨機宕機。隨后，第二輪中，B成為指定Leader，繼續(xù)發(fā)出6-20的日志(B沒有看到有6-10日志的存在)，這次，6以及20兩條日志形成了多數(shù)派。隨機再次發(fā)生切換，A回來了，從多數(shù)派拿到的最大LogId為20，因此決定補空洞，事實上，這次很大可能性是要從6開始，一直驗證到20。我們逐個看下會發(fā)生什么：

1. 針對Index 6的日志，A重新走一輪basic paxos就會發(fā)現(xiàn)更大proposeid形成決議的6，從而放棄本地的日志6，接受已經(jīng)多數(shù)派認可的日志;
2. 針對Index 7到Index 10，因為多數(shù)派沒有形成有效落盤，因此A隨機以本地日志發(fā)起提議并形成多數(shù)派;
3. 針對Index 11到Index 19，因為均沒有形成有效落盤數(shù)據(jù)，因此，以noop形成補空洞;
4. 針對Index 20，這個最簡單，接受已經(jīng)多數(shù)派認可的日志;

在上面的四類情況分析中，1，3，4的問題不大。主要在場景2，相當(dāng)于在第二輪并不存在的7~10，然后在第三列又重新出現(xiàn)了。按照Oceanbase的說法，在數(shù)據(jù)庫日志同步場景的情況，這個問題是不可接受的，一個簡單的例子就是轉(zhuǎn)賬場景，用戶轉(zhuǎn)賬時如果返回結(jié)果超時，那么往往會查詢一下轉(zhuǎn)賬是否成功，來決定是否重試一下。如果第一次查詢轉(zhuǎn)賬結(jié)果時，發(fā)現(xiàn)未生效而重試，而轉(zhuǎn)賬事務(wù)日志作為幽靈復(fù)現(xiàn)日志重新出現(xiàn)的話，就造成了用戶重復(fù)轉(zhuǎn)賬。

2、基于 Multi-Paxos 解決“幽靈復(fù)現(xiàn)”問題

為了處理“幽靈復(fù)現(xiàn)”問題，基于Multi-Paxos實現(xiàn)的一致性系統(tǒng)，可以在每條日志內(nèi)容保存一個epochID，指定Proposer在生成這條日志時以當(dāng)前的ProposalID作為epochID。按logID順序回放日志時，因為leader在開始服務(wù)之前一定會寫一條StartWorking日志，所以如果出現(xiàn)epochID相對前一條日志變小的情況，說明這是一條“幽靈復(fù)現(xiàn)”日志，要忽略掉這條日志(說明一下，我認這里順序是先補空洞，然后寫StartWorkingID，然后提供服務(wù))。

以上個例子來說明，在Round 3，A作為leader啟動時，需要日志回放重確認，index 1~5 的日志不用說的，epochID為1，然后進入epochID為2階段，index 6 會確認為epochID為2的StartWorking日志，然后就是index 7~10，因為這個是epochID為1的日志，比上一條日志epochID小，會被忽略掉。而Index 11~19的日志，EpochID應(yīng)該是要沿襲自己作為Leader看到的上上一輪StartWorkingID(當(dāng)然，ProposeID還是要維持在3的)，或者因為是noop日志，可以特殊化處理，即這部分日志不參與epochID的大小比較。然后index 20日志也會被重新確認。最后，在index 21寫入StartWorking日志，并且被大多數(shù)確認后，A作為leader開始接收請求。

3、基于Raft解決“幽靈復(fù)現(xiàn)”問題

3.1 關(guān)于Raft日志恢復(fù)

首先，我們聊一下Raft的日志恢復(fù)，在 Raft 中，每次選舉出來的Leader一定包含已經(jīng)Committed的數(shù)據(jù)(抽屜原理，選舉出來的Leader是多數(shù)中數(shù)據(jù)最新的，一定包含已經(jīng)在多數(shù)節(jié)點上Commit的數(shù)據(jù))，新的Leader將會覆蓋其他節(jié)點上不一致的數(shù)據(jù)。雖然新選舉出來的Leader一定包括上一個Term的Leader已經(jīng)Committed的Log Entry，但是可能也包含上一個Term的Leader未Committed的Log Entry。這部分Log Entry需要轉(zhuǎn)變?yōu)镃ommitted，相對比較麻煩，需要考慮Leader多次切換且未完成Log Recovery，需要保證最終提案是一致的，確定的，不然就會產(chǎn)生所謂的幽靈復(fù)現(xiàn)問題。

因此，Raft中增加了一個約束：對于之前Term的未Committed數(shù)據(jù)，修復(fù)到多數(shù)節(jié)點，且在新的Term下至少有一條新的Log Entry被復(fù)制或修復(fù)到多數(shù)節(jié)點之后，才能認為之前未Committed的Log Entry轉(zhuǎn)為Committed。

為了將上一個Term未Committed的Log Entry轉(zhuǎn)為Committed，Raft 的解決方案如下：

Raft算法要求Leader當(dāng)選后立即追加一條Noop的特殊內(nèi)部日志，并立即同步到其它節(jié)點，實現(xiàn)前面未Committed日志全部隱式提交。

從而保證了兩個事情：

• 通過最大Commit原則保證不會丟數(shù)據(jù)，即是保證所有的已經(jīng)Committed的Log Entry不會丟;
• 保證不會讀到未Committed的數(shù)據(jù)，因為只有Noop被大多數(shù)節(jié)點同意并提交了之后(這樣可以連帶往期日志一起同步)，服務(wù)才會對外正常工作;Noop日志本身也是一個分界線，Noop之前的Log Entry被提交，之后的Log Entry將會被丟棄。

3.2 Raft解決“幽靈復(fù)現(xiàn)”問題

針對第一小節(jié)的場景，Raft中是不會出現(xiàn)第三輪A當(dāng)選leader的情況，首先對于選舉，候選人對比的是最后一條日志的任期號(lastLogTerm)和日志的長度(lastLogIndex)。B、C的lastLogTerm(t2)和lastLogIndex(20)都比A的lastLogTerm(t1)和lastLogIndex(10)大，因此leader只能出現(xiàn)在B、C之內(nèi)。假設(shè)C成為leader后，Leader運行過程中會進行副本的修復(fù)，對于A來說，就是從log index為6的位置開始，C將會把自己的index為6及以后的log entry復(fù)制給A，因此A原來的index 6-10的日志刪除，并保持與C一致。最后C會向follower發(fā)送noop的log entry，如果被大多數(shù)都接收提交后，才開始正常工作，因此不會出現(xiàn)index 7-10能讀到值的情況。

這里考慮另一個更通用的幽靈復(fù)現(xiàn)場景?？紤]存在以下日志場景：

1)Round 1，A節(jié)點為leader，Log entry 5，6內(nèi)容還沒有commit，A節(jié)點發(fā)生宕機。這個時候client 是查詢不到 Log entry 5，6里面的內(nèi)容。

2)Round 2，B成為Leader, B中Log entry 3, 4內(nèi)容復(fù)制到C中， 并且在B為主的期間內(nèi)沒有寫入任何內(nèi)容。

3)Round 3，A 恢復(fù)并且B、C發(fā)生重啟，A又重新選為leader, 那么Log entry 5, 6內(nèi)容又被復(fù)制到B和C中，這個時候client再查詢就查詢到Log entry 5, 6 里面的內(nèi)容了。

Raft里面加入了新Leader 必須寫入一條當(dāng)前Term的Log Entry 就可以解決這個問題, 其實和MultiPaxos提到的寫入一個StartWorking 日志是一樣的做法, 當(dāng)B成為Leader后，會寫入一個Term 3的noop日志，這里解決了上面所說的兩個問題：

• Term 3的noop日志commit前，B的index 3，4的日志內(nèi)容一定會先復(fù)制到C中，實現(xiàn)了最大commit原則，保證不會丟數(shù)據(jù)，已經(jīng) commit 的 log entry 不會丟。
• 就算A節(jié)點恢復(fù)過來, 由于A的lastLogTerm比B和C都小，也無法成了Leader, 那么A中未完成的commit只是會被drop，所以后續(xù)的讀也就不會讀到Log Entry 5，6里面的內(nèi)容。

4、基于Zab解決“幽靈復(fù)現(xiàn)”問題

4.1 關(guān)于Zab的日志恢復(fù)

Zab在工作時分為原子廣播和崩潰恢復(fù)兩個階段，原子廣播工作過程也可以類比raft提交一次事務(wù)的過程。

崩潰恢復(fù)又可以細分為Leader選舉和數(shù)據(jù)同步兩個階段。

早期的Zab協(xié)議選舉出來的Leader滿足下面的條件：

a) 新選舉的Leader節(jié)點含有本輪次所有競選者最大的zxid，也可以簡單認為Leader擁有最新數(shù)據(jù)。該保證最大程度確保Leader具有最新數(shù)據(jù)。

b) 競選Leader過程中進行比較的zxid，是基于每個競選者已經(jīng)commited的數(shù)據(jù)生成。

zxid是64位高32位是epoch編號，每經(jīng)過一次Leader選舉產(chǎn)生一個新的leader，新的leader會將epoch號+1，低32位是消息計數(shù)器，每接收到一條消息這個值+1，新leader選舉后這個值重置為0。這樣設(shè)計的好處在于老的leader掛了以后重啟，它不會被選舉為leader，因此此時它的zxid肯定小于當(dāng)前新的leader。當(dāng)老的leader作為follower接入新的leader后，新的leader會讓它將所有的擁有舊的epoch號的未被commit的proposal清除。

選舉出leader后，進入日志恢復(fù)階段，會根據(jù)每個Follower節(jié)點發(fā)送過來各自的zxid，決定給每個Follower發(fā)送哪些數(shù)據(jù)，讓Follower去追平數(shù)據(jù)，從而滿足最大commit原則，保證已commit的數(shù)據(jù)都會復(fù)制給Follower，每個Follower追平數(shù)據(jù)后均會給Leader進行ACK，當(dāng)Leader收到過半Follower的ACK后，此時Leader開始工作，整個zab協(xié)議也就可以進入原子廣播階段。

4.2 Zab解決“幽靈復(fù)現(xiàn)”問題

對于第 1 節(jié)的場景，根據(jù)ZAB的選舉階段的機制保證，每次選舉后epoch均會+1，并作為下一輪次zxid的最高32位。所以，假設(shè)Round 1階段，A,B,C的EpochId是1，那么接下來的在Round 2階段，EpochId為2，所有基于這個Epoch產(chǎn)生的zxid一定大于A上所有的zxid。于是，在Round 3，由于B, C的zxid均大于A，所以A是不會被選為Leader的。A作為Follower加入后，其上的數(shù)據(jù)會被新Leader上的數(shù)據(jù)覆蓋掉。可見，對于情況一，zab是可以避免的。

對于 3.2 節(jié)的場景，在Round 2，B選為leader后，并未產(chǎn)生任何事務(wù)。在Round 3選舉，由于A,B,C的最新日志沒變，所以A的最后一條日志zxid比B和C的大，因此A會選為leader，A將數(shù)據(jù)復(fù)制給B,C后，就會出現(xiàn)”幽靈復(fù)現(xiàn)“現(xiàn)象的。

為了解決“幽靈復(fù)現(xiàn)”問題，最新Zab協(xié)議中，每次leader選舉完成后，都會保存一個本地文件，用來記錄當(dāng)前EpochId(記為CurrentEpoch)，在選舉時，會先讀取CurrentEpoch并加入到選票中，發(fā)送給其他候選人，候選人如果發(fā)現(xiàn)CurrentEpoch比自己的小，就會忽略此選票，如果發(fā)現(xiàn)CurrentEpoch比自己的大，就會選擇此選票，如果相等則比較zxid。因此，對于此問題，Round 1中，A,B,C的CurrentEpoch為2;Round 2，A的CurrentEpoch為2，B,C的CurrentEpoch為3;Round 3，由于B,C的CurrentEpoch比A的大，所以A無法成為leader。

5、 進一步探討

在阿里云的女媧一致性系統(tǒng)里面，做法也是類似于Raft與Zab，確保能夠制造幽靈復(fù)現(xiàn)的角色無法在新的一輪選舉為leader，從而避免幽靈日志再次出現(xiàn)。從服務(wù)端來看“幽靈復(fù)現(xiàn)”問題，就是在failover情況下，新的leader不清楚當(dāng)前的committed index，也就是分不清log entry是committed狀態(tài)還是未committed狀態(tài)，所以需要通過一定的日志恢復(fù)手段，保證已經(jīng)提交的日志不會被丟掉(最大 commit 原則)，并且通過一個分界線(如MultiPaxos的StartWorking，Raft的noop，Zab的CurrentEpoch)來決定日志將會被commit還是被drop，從而避免模糊不一的狀態(tài)。“幽靈復(fù)現(xiàn)”的問題本質(zhì)屬于分布式系統(tǒng)的“第三態(tài)”問題，即在網(wǎng)絡(luò)系統(tǒng)里面, 對于一個請求都有三種返回結(jié)果：成功，失敗，超時未知。對于超時未知，服務(wù)端對請求命令的處理結(jié)果可以是成功或者失敗，但必須是兩者中之一，不能出現(xiàn)前后不一致情況。在客戶端中，請求收到超時，那么客戶端是不知道當(dāng)前底層是處于什么狀況的，成功或失敗都不清楚，所以一般客戶端的做法是重試，那么底層apply的業(yè)務(wù)邏輯需要保證冪等性，不然重試會導(dǎo)致數(shù)據(jù)不一致。