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

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

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

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

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

針對(duì)Index 6的日志，A重新走一輪basic paxos就會(huì)發(fā)現(xiàn)更大proposeid形成決議的6，從而放棄本地的日志6，接受已經(jīng)多數(shù)派認(rèn)可的日志；

針對(duì)Index 7到Index 10，因?yàn)槎鄶?shù)派沒(méi)有形成有效落盤，因此A隨機(jī)以本地日志發(fā)起提議并形成多數(shù)派；

針對(duì)Index 11到Index 19，因?yàn)榫鶝](méi)有形成有效落盤數(shù)據(jù)，因此，以noop形成補(bǔ)空洞；

針對(duì)Index 20，這個(gè)最簡(jiǎn)單，接受已經(jīng)多數(shù)派認(rèn)可的日志；

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

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

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

以上個(gè)例子來(lái)說(shuō)明，在Round 3，A作為leader啟動(dòng)時(shí)，需要日志回放重確認(rèn)，index 1~5 的日志不用說(shuō)的，epochID為1，然后進(jìn)入epochID為2階段，index 6 會(huì)確認(rèn)為epochID為2的StartWorking日志，然后就是index 7~10，因?yàn)檫@個(gè)是epochID為1的日志，比上一條日志epochID小，會(huì)被忽略掉。而Index 11~19的日志，EpochID應(yīng)該是要沿襲自己作為L(zhǎng)eader看到的上上一輪StartWorkingID（當(dāng)然，ProposeID還是要維持在3的），或者因?yàn)槭莕oop日志，可以特殊化處理，即這部分日志不參與epochID的大小比較。然后index 20日志也會(huì)被重新確認(rèn)。最后，在index 21寫入StartWorking日志，并且被大多數(shù)確認(rèn)后，A作為leader開始接收請(qǐng)求。

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

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

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

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

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

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

從而保證了兩個(gè)事情：

通過(guò)最大Commit原則保證不會(huì)丟數(shù)據(jù)，即是保證所有的已經(jīng)Committed的Log Entry不會(huì)丟；

保證不會(huì)讀到未Committed的數(shù)據(jù)，因?yàn)橹挥蠳oop被大多數(shù)節(jié)點(diǎn)同意并提交了之后（這樣可以連帶往期日志一起同步），服務(wù)才會(huì)對(duì)外正常工作；Noop日志本身也是一個(gè)分界線，Noop之前的Log Entry被提交，之后的Log Entry將會(huì)被丟棄。

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

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

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

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

2）Round 2，B成為L(zhǎng)eader， B中Log entry 3， 4內(nèi)容復(fù)制到C中， 并且在B為主的期間內(nèi)沒(méi)有寫入任何內(nèi)容。

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

Raft里面加入了新Leader 必須寫入一條當(dāng)前Term的Log Entry 就可以解決這個(gè)問(wèn)題， 其實(shí)和MultiPaxos提到的寫入一個(gè)StartWorking 日志是一樣的做法， 當(dāng)B成為L(zhǎng)eader后，會(huì)寫入一個(gè)Term 3的noop日志，這里解決了上面所說(shuō)的兩個(gè)問(wèn)題：

Term 3的noop日志commit前，B的index 3，4的日志內(nèi)容一定會(huì)先復(fù)制到C中，實(shí)現(xiàn)了最大commit原則，保證不會(huì)丟數(shù)據(jù)，已經(jīng) commit 的 log entry 不會(huì)丟。

就算A節(jié)點(diǎn)恢復(fù)過(guò)來(lái)， 由于A的lastLogTerm比B和C都小，也無(wú)法成了Leader， 那么A中未完成的commit只是會(huì)被drop，所以后續(xù)的讀也就不會(huì)讀到Log Entry 5，6里面的內(nèi)容。

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

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

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

崩潰恢復(fù)又可以細(xì)分為L(zhǎng)eader選舉和數(shù)據(jù)同步兩個(gè)階段。

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

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

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

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

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

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

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

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

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

5、 進(jìn)一步探討

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