系列文章
<a href="https://my.oschina.net/pingpangkuangmo/blog/776714">raft算法賞析</a>
<a href="https://my.oschina.net/pingpangkuangmo/blog/778927">zookeeper的一緻性算法賞析</a>
<a href="https://my.oschina.net/pingpangkuangmo/blog/782702">raft對比zab協定</a>
本篇文章想總結下raft和zab在處理一些一緻性問題上的做法，詳見之前對這2個算法的描述
上述分别是針對如下算法實作的讨論：
zab的實作zookeeper，由于zookeeper裡面的很多實作細節并沒有在zab裡展現（zab裡面隻是一個大概，沒有像raft那麼具體），是以這裡讨論的都是zookeeper的實作
一緻性算法在實作狀态機這種應用時，有哪些常見的問題：
1 leader選舉
1.1 一般的leader選舉過程
1.2 leader選舉的效率
1.3 加入一個已經完成選舉的叢集
1.4 leader選舉的觸發
2 上一輪次的leader
2.1 上一輪次的leader的殘留的資料怎麼處理？
2.2 怎麼阻止之前的leader假死的問題
3 請求處理流程
3.1 請求處理的一般流程
3.2 日志的連續性問題
3.3 如何保證順序
3.3.1 正常同步過程的順序
3.3.2 異常過程的順序
3.4 請求處理流程的異常
4 分區的處理
下面分别來看看raft和zookeeper怎麼來解決的
為什麼要進行leader選舉？
在實作一緻性的方案，可以像base-paxos那樣不需要leader選舉，這種方案達成一件事情的一緻性還好，面對多件事情的一緻性就比較複雜了，是以通過選舉出一個leader來簡化實作的複雜性。
更多的有2個要素：
1.1.1 選舉輪次
1.1.2 leader包含更多的日志
1.1.1 選舉投票可能會多次輪番上演，為了區分，是以需要定義你的投票是屬于哪個輪次的。
raft定義了term來表示選舉輪次
zookeeper定義了electionepoch來表示
他們都需要在某個輪次内達成過半投票來結束選舉過程
1.1.2 投票pk的過程，更多的是日志越新越多者獲勝
在選舉leader的時候，通常都希望
選舉出來的leader至少包含之前全部已送出的日志
自然想到包含的日志越新越大那就越好。
通常都是比較最後一個日志記錄，如何來定義最後一個日志記錄？
有2種選擇，一種就是所有日志中的最後一個日志，另一種就是所有已送出中的最後一個日志。目前raft和zookeeper都是采用前一種方式。日志的越新越大表示：輪次新的優先，然後才是同一輪次下日志記錄大的優先
raft：term大的優先，然後entry的index大的優先
zookeeper：peerepoch大的優先，然後zxid大的優先
但是有一個問題就是：通過上述的日志越新越大的比較方式能達到我們的上述希望嗎？
特殊情況下是不能的，這個特殊情況詳細見上述給出raft算法賞析的這一部分
這個案例就是這種比較方式會選舉出來的leader可能并不包含已經送出的日志，而raft的做法則是對于日志的送出多加一個限制條件，即不能直接送出之前term的已過半的entry，即把這一部分的日志限制成未送出的日志，進而來實作上述的希望。
zookeeper呢？會不會出現這種情況？又是如何處理的？
zookeeper是不會出現這種情況的，因為zookeeper在每次leader選舉完成之後，都會進行資料之間的同步糾正，是以每一個輪次，大家都日志内容都是統一的
而raft在leader選舉完成之後沒有這個同步過程，而是靠之後的appendentries rpc請求的一緻性檢查來實作糾正過程，則就會出現上述案例中隔了幾個輪次還不統一的現象
raft中的每個server在某個term輪次内隻能投一次票，哪個candidate先請求投票誰就可能先獲得投票，這樣就可能造成split vote，即各個candidate都沒有收到過半的投票，raft通過candidate設定不同的逾時時間，來快速解決這個問題，使得先逾時的candidate（在其他人還未逾時時）優先請求來獲得過半投票
zookeeper中的每個server，在某個electionepoch輪次内，可以投多次票，隻要遇到更大的票就更新，然後分發新的投票給所有人。這種情況下不存在split vote現象，同時有利于選出含有更新更多的日志的server，但是選舉時間理論上相對raft要花費的多。
1.3.1 怎麼發現已完成選舉的leader？
1.3.2 加入過程是否阻塞整個請求？
一個server啟動後（該server本來就屬于該叢集的成員配置之一，是以這裡不是新加機器），如何加入一個已經選舉完成的叢集
raft：比較簡單，該server啟動後，會收到leader的appendentries rpc,這時就會從rpc中擷取leader資訊，識别到leader，即使該leader是一個老的leader，之後新leader仍然會發送appendentries rpc,這時就會接收到新的leader了（因為新leader的term比老leader的term大，是以會更新leader）
zookeeper：該server啟動後，會向所有的server發送投票通知，這時候就會收到處于looking、following狀态的server的投票（這種狀态下的投票指向的leader），則該server放棄自己的投票，判斷上述投票是否過半，過半則可以确認該投票的内容就是新的leader。
這個其實還要看對日志的設計是否是連續的
如果是連續的，則leader中隻需要儲存每個follower上一次的同步位置，這樣在同步的時候就會自動将之前欠缺的資料補上，不會阻塞整個請求過程
如果不是連續的，則在确認follower和leader目前資料的差異的時候，是需要擷取leader目前資料的讀鎖，禁止這個期間對資料的修改。差異确定完成之後，釋放讀鎖，允許leader資料被修改，每一個修改記錄都要被儲存起來，最後一一應用到新加入的follower中。
觸發一般有如下2個時機
server剛開始啟動的時候，觸發leader選舉
leader選舉完成之後，檢測到逾時觸發，誰來檢測？
raft：目前隻是follower在檢測。follower有一個選舉時間，在該時間内如果未收到leader的心跳資訊，則follower轉變成candidate，自增term發起新一輪的投票，leader遇到新的term則自動轉變成follower的狀态
zookeeper：leader和follower都有各自的檢測逾時方式，leader是檢測是否過半follower心跳回複了，follower檢測leader是否發送心跳了。一旦leader檢測失敗，則leader進入looking狀态，其他follower過一段時間因收不到leader心跳也會進入looking狀态，進而出發新的leader選舉。一旦follower檢測失敗了，則該follower進入looking狀态，此時leader和其他follower仍然保持良好，則該follower仍然是去學習上述leader的投票，而不是觸發新一輪的leader選舉
首先看下上一輪次的leader在挂或者失去leader位置之前，會有哪些資料？
已過半複制的日志
未過半複制的日志
一個日志是否被過半複制，是否被送出，這些資訊是由leader才能知曉的，那麼下一個leader該如何來判定這些日志呢？
下面分别來看看raft和zookeeper的處理政策：
raft：對于之前term的過半或未過半複制的日志采取的是保守的政策，全部判定為未送出，隻有當目前term的日志過半了，才會順便将之前term的日志進行送出
zookeeper：采取激進的政策，對于所有過半還是未過半的日志都判定為送出，都将其應用到狀态機中
raft的保守政策更多是因為raft在leader選舉完成之後，沒有同步更新過程來保持和leader一緻（在可以對外處理請求之前的這一同步過程）。而zookeeper是有該過程的
這其實就和實作有密切的關系了。
raft的copycat實作為：每個follower開通一個複制資料的rpc接口，誰都可以連接配接并調用該接口，是以raft需要來阻止上一輪次的leader的調用。每一輪次都會有對應的輪次号，用來進行區分，raft的輪次号就是term，一旦舊leader對follower發送請求，follower會發現目前請求term小于自己的term，則直接忽略掉該請求，自然就解決了舊leader的幹擾問題
zookeeper：一旦server進入leader選舉狀态則該follower會關閉與leader之間的連接配接，是以舊leader就無法發送複制資料的請求到新的follower了，也就無法造成幹擾了
這個過程對比raft和zookeeper基本上是一緻的，大緻過程都是過半複制
先來看下raft：
client連接配接follower或者leader，如果連接配接的是follower則，follower會把client的請求(寫請求，讀請求則自身就可以直接處理)轉發到leader
leader接收到client的請求，将該請求轉換成entry，寫入到自己的日志中，得到在日志中的index，會将該entry發送給所有的follower(實際上是批量的entries)
follower接收到leader的appendentries rpc請求之後，會将leader傳過來的批量entries寫入到檔案中（通常并沒有立即重新整理到磁盤），然後向leader回複ok
leader收到過半的ok回複之後，就認為可以送出了，然後應用到leader自己的狀态機中，leader更新commitindex，應用完畢後回複用戶端
在下一次leader發給follower的心跳中，會将leader的commitindex傳遞給follower，follower發現commitindex更新了則也将commitindex之前的日志都進行送出和應用到狀态機中
再來看看zookeeper：
leader接收到client的請求，将該請求轉換成一個議案，寫入到自己的日志中，會将該議案發送給所有的follower(這裡隻是單個發送)
follower接收到leader的議案請求之後，會将該議案寫入到檔案中（通常并沒有立即重新整理到磁盤），然後向leader回複ok
leader收到過半的ok回複之後，就認為可以送出了，leader會向所有的follower發送一個送出上述議案的請求，同時leader自己也會送出該議案，應用到自己的狀态機中，完畢後回複用戶端
follower在接收到leader傳過來的送出議案請求之後，對該議案進行送出，應用到狀态機中
在需要保證順序性的前提下，在利用一緻性算法實作狀态機的時候，到底是實作連續性日志好呢還是實作非連續性日志好呢？
如果是連續性日志，則leader在分發給各個follower的時候，隻需要記錄每個follower目前已經同步的index即可，如raft
如果是非連續性日志，如zookeeper，則leader需要為每個follower單獨儲存一個隊列，用于存放所有的改動，如zookeeper，一旦是隊列就引入了一個問題即順序性問題，即follower在和leader進行同步的時候，需要阻塞leader處理寫請求，先将follower和leader之間的差異資料先放入隊列，完成之後，解除阻塞，允許leader處理寫請求，即允許往該隊列中放入新的寫請求，進而來保證順序性
還有在複制和送出的時候：
連續性日志可以批量進行
非連續性日志則隻能一個一個來複制和送出
其他有待後續補充
具體順序是什麼？
這個就是先到達leader的請求，先被應用到狀态機。這就需要看正常運作過程、異常出現過程都是怎麼來保證順序的
raft對請求先轉換成entry，複制時，也是按照leader中log的順序複制給follower的，對entry的送出是按index進行順序送出的，是可以保證順序的
zookeeper在送出議案的時候也是按順序寫入各個follower對應在leader中的隊列，然後follower必然是按照順序來接收到議案的，對于議案的過半送出也都是一個個來進行的
3.3.2 異常過程的順序保證
如follower挂掉又重新開機的過程：
raft：重新開機之後，由于leader的appendentries rpc調用，識别到leader，leader仍然會按照leader的log進行順序複制，也不用關心在複制期間新的添加的日志，在下一次同步中自動會同步
zookeeper：重新開機之後，需要和目前leader資料之間進行差異的确定，同時期間又有新的請求到來，是以需要暫時擷取leader資料的讀鎖，禁止此期間的資料更改，先将差異的資料先放入隊列，差異确定完畢之後，還需要将leader中已送出的議案和未送出的議案也全部放入隊列，即zookeeper的如下2個集合資料
concurrentmap outstandingproposals
concurrentlinkedqueue tobeapplied
然後再釋放讀鎖，允許leader進行處理寫資料的請求，該請求自然就添加在了上述隊列的後面，進而保證了隊列中的資料是有序的，進而保證發給follower的資料是有序的，follower也是一個個進行确認的，是以對于leader的回複也是有序的
如果是leader挂了之後，重新選舉出leader，會不會有亂序的問題？
raft：raft對于之前term的entry被過半複制暫不送出，隻有當本term的資料送出了才能将之前term的資料一起送出，也是能保證順序的
zookeeper:zookeeper每次leader選舉之後都會進行資料同步，不會有亂序問題
一旦leader發給follower的資料出現逾時等異常
raft：會不斷重試，并且接口是幂等的
zookeeper：follower會斷開與leader之間的連接配接，重新加入該叢集，加入邏輯前面已經說了
目前zookeeper和raft都是過半即可，是以對于分區是容忍的。如5台機器，分區發生後分成2部分，一部分3台，另一部分2台，這2部分之間無法互相通信
其中，含有3台的那部分，仍然可以湊成一個過半，仍然可以對外提供服務，但是它不允許有server再挂了，一旦再挂一台則就全部不可用了。
含有2台的那部分，則無法提供服務，即隻要連接配接的是這2台機器，都無法執行相關請求。
是以zookeeper和raft在一旦分區發生的情況下是是犧牲了高可用來保證一緻性，即cap理論中的cp。但是在沒有分區發生的情況下既能保證高可用又能保證一緻性，是以更想說的是所謂的cap二者取其一，并不是說該系統一直保持ca或者cp或者ap，而是一個會變化的過程。在沒有分區出現的情況下，既可以保證c又可以保證a，在分區出現的情況下，那就需要從c和a中選擇一樣。zookeeper和raft則都是選擇了c。
歡迎關注微信公衆号：乒乓狂魔