目錄
1、Zab協定
2、raft協定
3、gossip
分布式資料一緻性簡單點了解就是在多個節點中同一時間視圖時資料值是一緻的。大體上可以将這些算法分為強一緻性與弱一緻性。
- 強一緻性
zab協定（zk基于該協定實作了主備模式的系統架構，不保證線性一緻性）
raft協定（該協定是實作etcd高可靠的基礎，大名鼎鼎的k8s就使用了etcd儲存叢集中所有的網絡配制和對象的狀态資訊）
paxos
- 弱一緻性
gossip協定（這個應用在redis cluster中）
下面對上述算法進行簡要的介紹。
1、Zab協定
Zab 協定的全稱是 ZooKeeper 原子廣播協定（ZooKeeper Atomic Broadcast Protocol），目前Zookeeper基于該協定作為共識算法實作了主備模式的系統架構，并以此保證其叢集中各個副本資料之間的一緻性。Zab協定的原理大緻分為選舉(Leader election)、發現(discovery)、同步（synchronization）與廣播（broadcast），但在zk的具體實作中，隻有三個階段：leader選舉階段，資料恢複階段和廣播階段，将發現和同步兩部分合并成為資料恢複階段了。
在zk中，所有的寫請求都是由leader伺服器協調處理，如果寫請求連接配接到follower節點，則會向leader轉發請求，leader收到請求後，基于類似的2PC 當過半數節點寫入成功，leader會再次向叢集廣播commit消息并送出。如果是讀請求，則直接從目前節點中讀取資料。
zk中的節點類型有
- LOOKING：進入 Leader 選舉狀态；
- LEADING：某個節點成為 leader 并負責協調事務 ；
- FOLLOWING：目前節點是 Follower，服從 Leader 節點的指令并參與共識；
- OBSERVING：Observer 節點是隻讀節點，用于增加叢集的隻讀事務性能，不參與共識與選舉
消息廣播
主要是針對于寫請求，當任意節點收到寫請求時，最終都會轉發給leader節點。leader節點對生成對應的事務提案，并生成zxid（zxid是一個64位數字，高32位表示目前leader的epoch【類似于raft的term，即任期】，低32位是一個單增的電腦【每個epoch從0開始計數】），然後将提案廣播給其他節點，其他節點收到請求以事務日志形式寫入本地磁盤成功後回報ack響應。當收到超過半數的ack響應後，則回複用戶端寫入成功，并向叢集發送commit消息，送出事務。當各節點收到commit後，會完成事務的送出，資料寫到資料副本中。
在實際中，leader會收到多個寫請求，為了統計每個寫請求來自于follower的ack回報數，在leader伺服器中會為每個follower維護一個消息隊列，然後将需要廣播的提案依次放入到隊列中，并基于FIFO的規則 發送消息。leader隻需要統計每個zxid對應的提案超過半數有ack回報就行，無需等待全部的follower節點。
崩潰恢複
崩潰恢複即是包含有兩個階段：一是leader選舉，另一個是資料恢複階段。為了保證叢集的資料強一緻性，zab協定需要通過以下兩個特性來保證：
- 已經在leader伺服器上送出的事務最終被所有伺服器送出
這個特性很容易保證，畢竟zab協定中隻要超過半數節點寫入資料并ack響應，leader才會回複client寫操作成功。
- 丢棄隻在leader上提出但沒有被送出的事務
（1）如果leader在第一階段崩潰了，如廣播提案時崩潰，或者等待半數follower的ack響應期間崩潰。 這一階段其實沒有向用戶端回複寫入成功，以及向叢集發送commit。是以從用戶端角度來說沒有收到leader節點的寫操作成功響應，這種事務是失敗的。從follower角度來說，由于沒有收到commit指令，是以沒有任何一個follower節點送出資料
（2）在第二階段發送commit後回複用戶端寫入成功前崩潰，這個過程稍微複雜一點。我猜想是通過逾時機制以及用戶端業務保證，這個後期再驗證一下（要求rpc請求實作幂等性即可，也即實作内部的去重機制） 。
leaer選舉階段
在leader選舉階段，叢集中的伺服器的節點狀态都是LOOKING，每個節點向叢集中的其他節點發送消息（包含epoch,zxid）。在選舉初始階段，每個節點都會将自己作為投票對象，并向叢集廣播投票資訊。為了達成選舉一緻性，避免無休止的選舉，zab總體保證擁有最新資料的伺服器當選leader。具體規則如下：
- 比較epoch，取其大者作為新的選舉伺服器，如相同進入2
- 比較zxid，取其大者作為新的選舉伺服器，如果相等進入3
- 比較伺服器的myid(每一個節點都擁有一個唯一辨別 ID
myid
myid
一旦某個節點擁有半數以上的投票，則會切換成leader，其他節點自動變為follower。
資料恢複階段
當leader選舉成功後，follower與leader建立長連接配接，并進行資料同步。當資料恢複階段結束後，zk叢集才能正式對外提供事務服務，也就是進入了上文所說的消息廣播階段。
操作順序性保證
zab協定是基于主備模式的原子廣播協定，最終實作了操作的順序性。在zab協定中，所有副本的資料都是以主節點為準，主節點采用2PC送出，向follower節點同步資料。如果leader節點發生故障，則資料（日志）最完備的節點當選為leader。其次，zab實作了FIFO隊列，保證消息處理的順序性。總之，zab協定實作了一切以leader為準的專政模式和嚴格的FIFO順序送出日志來保證操作的有順序性的。
從上面的描述，對zab協定總結幾點：
- zab實作的是最終一緻性。即當寫請求過半節點成功後，是不能保證每次都實時的讀到最新資料，但能保證在一定的時間範圍内，用戶端最終能夠從服務端上讀取到最新的資料狀态。
- zab采用的快速上司者選舉（fast leader election）,與raft采取的『一張選票，先到先得』算法相比，需要的通訊消息數要多一點，選舉也稍微慢一些
另外，zab協定目前與zk是強耦合的。
一緻性保證
預設情況下，ZooKeeper并不提供線性一緻性，也即全局一緻的資料視圖。如果需要線性一緻性，可以通過執行Zookeeper#sync()方法。對于讀請求，每一個zk伺服器都會對外提供服務，每一個伺服器都有一層本地緩存，這也是zk高效的原因之一。zk可以通過線性增加follower節點均衡讀壓力（但是節點過多，會影響寫入的性能，畢竟寫請求需要同步到更多的節點）。zk中，與讀不同，寫入請求是滿足線性一緻性的。
2、raft協定
raft對應的論文參考：In Search of an Understandable Consensus Algorithm(https://raft.github.io/raft.pdf)。它是一種基于leader選舉的算法，用于保證分布式資料的一緻性，它是實作etcd高可靠的基礎。在raft協定中，節點的類型有leader, follower, candidate。
伺服器的狀态
時間被劃分為term
在etcd的實作中，節點類型有相應的增加，如preCandidate， learner。
叢集啟動時，所有的節點都是follower狀态，随後會進入leader選舉階段。當follower節點的選舉計時逾時後仍然沒有leader節點，會先切換為preCandidate身份，然後發送preVote預投票詢問其他節點是否願意參與選舉争取他們的投票，如果有超過法定人數的節點響應并表示參與新一輪選舉，則該節點會切換到candidate身份，并發起新一輪的選舉。與前面的zab協定不同的是，節點類型多了一個預投票機制，通過preVote機制可以阻止失聯節點（與現有的leader節點心跳逾時）頻繁的重新整理term值，防止該節點重新加入叢集時以更大的term值取代leader，進而影響leader節點的頻繁切換（這種情況多發生于節點在不同的網絡分區中）。
learner是etch3.4引入的新節點類型，處于該類型的節點沒有vote 權限，不算入Quorum。主要是解決以下問題：
- 新節點加入叢集時，需要花費大量的時間同步日志，這可能導緻叢集無法處理新的文法
以上需要說明的有：
- 在一個term内，同一個節點最多能給一個candidate投票.原則是『一張選票，先到先服務』
- 選取心跳的發送是從leader(candidate)發送給follower
- 選舉的timeout是随機的，最先從timeout中恢複發起投票的一方向還在timeout中的其他方請求投票，避免在沒有選舉合适的leader的case下無限重複選舉
狀态複制
一般通過使用複制日志來實作複制狀态機。與zab協定一樣，leader建立的日志entry已經複制到大多數的伺服器上，這個entry就稱為已送出。
為了消除上圖描述的問題，
Raft基于leader目前term的日志entry才通過計算數目來進行送出。
下面介紹一下raft與zab的差別：
- zab是主備模式的系統架構:所有的資料都以leader為準備，raft是狀态機系統：僅同步事務指令
- 選主方式：raft比較last_log_index以及last_log_term保證選出的leader已經擁有最完整的資料，zab僅通過節點辨別選主，是以需要之後的recovery過程，不過實作中zab也采用了類似于raft的選主方式
- 資料恢複方向：raft，leader擁有最完備的資料，它僅從leader單向到follower補齊log；而zab是雙向的，leader需要從follower接收資料生成初始日志
- leader選舉效率：raft更高
腦殘問題
- 對于寫請求，當存在多個leader時，原先的leader獨自在一個區，向其送出的資料得不到Quorum數量的支援永遠也送出不成功。向新的leader資料可以送出成功，網絡恢複後，舊的leader發現叢集中有更新的term存在而自動降級為follower并從新的leader處同步資料達成叢集資料的一緻。
- 對于讀請求，在etch-raft通過一種稱為readIndex的機制來實作線性一緻讀，基本原理：leader節點在處理讀請求時，先确定自身leader的地位（過半節點認為自己是leader），然後讀取資料。（這裡有個疑問：讀請求也與寫請求一樣是重量級，能否有更優化的方案呢？——實際中，在發送心跳時會順帶上最近一個readIndex的ID,如果心跳等到多數派确認，則該ID對應的readIndex請求也得到确認，當然該請求之前的readIndex也變相被确認）
是以，理論上可以這樣了解:在etcd中不存在腦殘問題。
一緻性保證
raft可以保證線性一緻性讀，有以下幾種政策：
- 讀取也走raft log, 讓讀取的請求也走一遍raft流程，raft日志是全局嚴格有序的，讀寫也必然是有序的，是以當處理到讀取的日志的時候，能夠保證之前的寫入請求都已經處理完成并sync狀态機，
- read index：發送心跳時順帶上最近一個readIndex的id
- lease Read:一般follower會在election timeout逾時後才會認為leader挂掉，并發起一次新的選舉。這裡需要考慮伺服器的時間
3、gossip
它是一個無中心的基于流行病傳播方式的節點或者程序之間資訊交換的協定，簡單點就是ping-pong進行廣播。
關于腦裂及解決方案會持續更新
references:
[1]https://github.com/aCoder2013/blog/issues/36