
阿裡妹導讀:
“幽靈複現”的問題本質屬于分布式系統的“第三态”問題,即在網絡系統裡面,對于一個請求都有三種傳回結果:成功,失敗,逾時未知。對于超>時未知,服務端對請求指令的處理結果可以是成功或者失敗,但必須是兩者中之一,不能出現前後不一緻情況。
1、“幽靈複現”問題
我們知道,目前業界有很多分布式一緻性複制協定,比如Paxos,Raft,Zab及Paxos的變種協定,被廣泛用于實作高可用的資料一緻性。Paxos組通常有3或5個互為備援的節點組成,它允許在少數派節點發生停機故障的情況下,依然能繼續提供服務,并且保證資料一緻性。作為一種優化,協定一般會在節點之間選舉出一個Leader專門負責發起Proposal,Leader的存在,避免了常态下并行提議的幹擾,這對于提高Proposal處理的效率有很大提升。
但是考慮在一些極端異常,比如網絡隔離,機器故障等情況下,Leader可能會經過多次切換和資料恢複,使用Paxos協定處理日志的備份與恢複時,可以保證确認形成多數派的日志不丢失,但是無法避免一種被稱為“幽靈複現”的現象。考慮下面一種情況:
如上表所示,在第一輪中,A成為指定Leader,發出1-10的日志,不過後面的6-10沒有形成多數派,随機當機。随後,第二輪中,B成為指定Leader,繼續發出6-20的日志(B沒有看到有6-10日志的存在),這次,6以及20兩條日志形成了多數派。随機再次發生切換,A回來了,從多數派拿到的最大LogId為20,是以決定補空洞,事實上,這次很大可能性是要從6開始,一直驗證到20。我們逐個看下會發生什麼:
- 針對Index 6的日志,A重新走一輪basic paxos就會發現更大proposeid形成決議的6,進而放棄本地的日志6,接受已經多數派認可的日志;
- 針對Index 7到Index 10,因為多數派沒有形成有效落盤,是以A随機以本地日志發起提議并形成多數派;
- 針對Index 11到Index 19,因為均沒有形成有效落盤資料,是以,以noop形成補空洞;
- 針對Index 20,這個最簡單,接受已經多數派認可的日志;
在上面的四類情況分析中,1,3,4的問題不大。主要在場景2,相當于在第二輪并不存在的7~10,然後在第三列又重新出現了。按照Oceanbase的說法,在資料庫日志同步場景的情況,這個問題是不可接受的,一個簡單的例子就是轉賬場景,使用者轉賬時如果傳回結果逾時,那麼往往會查詢一下轉賬是否成功,來決定是否重試一下。如果第一次查詢轉賬結果時,發現未生效而重試,而轉賬事務日志作為幽靈複現日志重新出現的話,就造成了使用者重複轉賬。
2、基于 Multi-Paxos 解決“幽靈複現”問題
為了處理“幽靈複現”問題,基于Multi-Paxos實作的一緻性系統,可以在每條日志内容儲存一個epochID,指定Proposer在生成這條日志時以目前的ProposalID作為epochID。按logID順序回放日志時,因為leader在開始服務之前一定會寫一條StartWorking日志,是以如果出現epochID相對前一條日志變小的情況,說明這是一條“幽靈複現”日志,要忽略掉這條日志(說明一下,我認這裡順序是先補空洞,然後寫StartWorkingID,然後提供服務)。
以上個例子來說明,在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應該是要沿襲自己作為Leader看到的上上一輪StartWorkingID(當然,ProposeID還是要維持在3的),或者因為是noop日志,可以特殊化處理,即這部分日志不參與epochID的大小比較。然後index 20日志也會被重新确認。最後,在index 21寫入StartWorking日志,并且被大多數确認後,A作為leader開始接收請求。
3、基于Raft解決“幽靈複現”問題
3.1 關于Raft日志恢複
首先,我們聊一下Raft的日志恢複,在 Raft 中,每次選舉出來的Leader一定包含已經Committed的資料(抽屜原理,選舉出來的Leader是多數中資料最新的,一定包含已經在多數節點上Commit的資料),新的Leader将會覆寫其他節點上不一緻的資料。雖然新選舉出來的Leader一定包括上一個Term的Leader已經Committed的Log Entry,但是可能也包含上一個Term的Leader未Committed的Log Entry。這部分Log Entry需要轉變為Committed,相對比較麻煩,需要考慮Leader多次切換且未完成Log Recovery,需要保證最終提案是一緻的,确定的,不然就會産生所謂的幽靈複現問題。
是以,Raft中增加了一個限制:對于之前Term的未Committed資料,修複到多數節點,且在新的Term下至少有一條新的Log Entry被複制或修複到多數節點之後,才能認為之前未Committed的Log Entry轉為Committed。
為了将上一個Term未Committed的Log Entry轉為Committed,Raft 的解決方案如下:
Raft算法要求Leader當選後立即追加一條Noop的特殊内部日志,并立即同步到其它節點,實作前面未Committed日志全部隐式送出。
進而保證了兩個事情:
- 通過最大Commit原則保證不會丢資料,即是保證所有的已經Committed的Log Entry不會丢;
- 保證不會讀到未Committed的資料,因為隻有Noop被大多數節點同意并送出了之後(這樣可以連帶往期日志一起同步),服務才會對外正常工作;Noop日志本身也是一個分界線,Noop之前的Log Entry被送出,之後的Log Entry将會被丢棄。
3.2 Raft解決“幽靈複現”問題
針對第一小節的場景,Raft中是不會出現第三輪A當選leader的情況,首先對于選舉,候選人對比的是最後一條日志的任期号(lastLogTerm)和日志的長度(lastLogIndex)。B、C的lastLogTerm(t2)和lastLogIndex(20)都比A的lastLogTerm(t1)和lastLogIndex(10)大,是以leader隻能出現在B、C之内。假設C成為leader後,Leader運作過程中會進行副本的修複,對于A來說,就是從log index為6的位置開始,C将會把自己的index為6及以後的log entry複制給A,是以A原來的index 6-10的日志删除,并保持與C一緻。最後C會向follower發送noop的log entry,如果被大多數都接收送出後,才開始正常工作,是以不會出現index 7-10能讀到值的情況。
這裡考慮另一個更通用的幽靈複現場景。考慮存在以下日志場景:
1)Round 1,A節點為leader,Log entry 5,6内容還沒有commit,A節點發生當機。這個時候client 是查詢不到 Log entry 5,6裡面的内容。
2)Round 2,B成為Leader, B中Log entry 3, 4内容複制到C中, 并且在B為主的期間内沒有寫入任何内容。
3)Round 3,A 恢複并且B、C發生重新開機,A又重新選為leader, 那麼Log entry 5, 6内容又被複制到B和C中,這個時候client再查詢就查詢到Log entry 5, 6 裡面的内容了。
Raft裡面加入了新Leader 必須寫入一條目前Term的Log Entry 就可以解決這個問題, 其實和MultiPaxos提到的寫入一個StartWorking 日志是一樣的做法, 當B成為Leader後,會寫入一個Term 3的noop日志,這裡解決了上面所說的兩個問題:
Term 3的noop日志commit前,B的index 3,4的日志内容一定會先複制到C中,實作了最大commit原則,保證不會丢資料,已經 commit 的 log entry 不會丢。
就算A節點恢複過來, 由于A的lastLogTerm比B和C都小,也無法成了Leader, 那麼A中未完成的commit隻是會被drop,是以後續的讀也就不會讀到Log Entry 5,6裡面的内容。
**4、基于Zab解決“幽靈複現”問題
**
4.1 關于Zab的日志恢複
Zab在工作時分為原子廣播和崩潰恢複兩個階段,原子廣播工作過程也可以類比raft送出一次事務的過程。
崩潰恢複又可以細分為Leader選舉和資料同步兩個階段。
早期的Zab協定選舉出來的Leader滿足下面的條件:
a) 新選舉的Leader節點含有本輪次所有競選者最大的zxid,也可以簡單認為Leader擁有最新資料。該保證最大程度確定Leader具有最新資料。
b) 競選Leader過程中進行比較的zxid,是基于每個競選者已經commited的資料生成。
zxid是64位高32位是epoch編号,每經過一次Leader選舉産生一個新的leader,新的leader會将epoch号+1,低32位是消息計數器,每接收到一條消息這個值+1,新leader選舉後這個值重置為0。這樣設計的好處在于老的leader挂了以後重新開機,它不會被選舉為leader,是以此時它的zxid肯定小于目前新的leader。當老的leader作為follower接入新的leader後,新的leader會讓它将所有的擁有舊的epoch号的未被commit的proposal清除。
選舉出leader後,進入日志恢複階段,會根據每個Follower節點發送過來各自的zxid,決定給每個Follower發送哪些資料,讓Follower去追平資料,進而滿足最大commit原則,保證已commit的資料都會複制給Follower,每個Follower追平資料後均會給Leader進行ACK,當Leader收到過半Follower的ACK後,此時Leader開始工作,整個zab協定也就可以進入原子廣播階段。
4.2 Zab解決“幽靈複現”問題
對于第 1 節的場景,根據ZAB的選舉階段的機制保證,每次選舉後epoch均會+1,并作為下一輪次zxid的最高32位。是以,假設Round 1階段,A,B,C的EpochId是1,那麼接下來的在Round 2階段,EpochId為2,所有基于這個Epoch産生的zxid一定大于A上所有的zxid。于是,在Round 3,由于B, C的zxid均大于A,是以A是不會被選為Leader的。A作為Follower加入後,其上的資料會被新Leader上的資料覆寫掉。可見,對于情況一,zab是可以避免的。
對于 3.2 節的場景,在Round 2,B選為leader後,并未産生任何事務。在Round 3選舉,由于A,B,C的最新日志沒變,是以A的最後一條日志zxid比B和C的大,是以A會選為leader,A将資料複制給B,C後,就會出現”幽靈複現“現象的。
為了解決“幽靈複現”問題,最新Zab協定中,每次leader選舉完成後,都會儲存一個本地檔案,用來記錄目前EpochId(記為CurrentEpoch),在選舉時,會先讀取CurrentEpoch并加入到選票中,發送給其他候選人,候選人如果發現CurrentEpoch比自己的小,就會忽略此選票,如果發現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、 進一步探讨
在阿裡雲的女娲一緻性系統裡面,做法也是類似于Raft與Zab,確定能夠制造幽靈複現的角色無法在新的一輪選舉為leader,進而避免幽靈日志再次出現。從服務端來看“幽靈複現”問題,就是在failover情況下,新的leader不清楚目前的committed index,也就是分不清log entry是committed狀态還是未committed狀态,是以需要通過一定的日志恢複手段,保證已經送出的日志不會被丢掉(最大 commit 原則),并且通過一個分界線(如MultiPaxos的StartWorking,Raft的noop,Zab的CurrentEpoch)來決定日志将會被commit還是被drop,進而避免模糊不一的狀态。“幽靈複現”的問題本質屬于分布式系統的“第三态”問題,即在網絡系統裡面, 對于一個請求都有三種傳回結果:成功,失敗,逾時未知。對于逾時未知,服務端對請求指令的處理結果可以是成功或者失敗,但必須是兩者中之一,不能出現前後不一緻情況。在用戶端中,請求收到逾時,那麼用戶端是不知道目前底層是處于什麼狀況的,成功或失敗都不清楚,是以一般用戶端的做法是重試,那麼底層apply的業務邏輯需要保證幂等性,不然重試會導緻資料不一緻。
參考文章:
- In Search of an Understandable Consensus Algorithm - Diego Ongaro and John Ousterhout https://raft.github.io/raft.pdf?spm=ata.13261165.0.0.337d6f55qtohyc&file=raft.pdf
- Paxos Made Simple – Leslie Lamport https://lamport.azurewebsites.net/pubs/paxos-simple.pdf?spm=ata.13261165.0.0.337d6f55qtohyc&file=paxos-simple.pdf
- Oceanbase列傳 – 郁白 http://oceanbase.org.cn/?spm=ata.13261165.0.0.337d6f55qtohyc&p=111
- 關于Paxos "幽靈複現"問題看法 – 陳宗志 https://zhuanlan.zhihu.com/p/40175038?spm=ata.13261165.0.0.337d6f55qtohyc
- zookeeper原了解析 https://www.cnblogs.com/wxd0108/p/6251729.html?spm=ata.13261165.0.0.337d6f55qtohyc