天天看點
傳回

【分布式技術專題】帶你徹底認識Paxos算法、Zab協定和Raft協定的原理和本質

内容簡介指南

  • Paxo算法指南
  • Zab算法指南
  • Raft算法指南

Paxos算法的背景

【Paxos算法】是萊斯利·蘭伯特(Leslie Lamport)1990年提出的一種基于消息傳遞的一緻性算法，是目前公認的解決分布式一緻性問題最有效的算法之一，其解決的問題就是在分布式系統中如何就某個值（決議）達成一緻。

Paxos算法的前提

Paxos算法的前提假設是不存在拜占庭将軍問題，即：信道是安全的（信道可靠），發出的信号不會被篡改。

Paxos算法的介紹

在Paxos算法中，有三種角色：
【分布式技術專題】帶你徹底認識Paxos算法、Zab協定和Raft協定的原理和本質
  • proposer：提案Proposal提出者。
  • Acceptor：決策者，可以準許議案。
  • Learner：最終決策的學習者。
【分布式技術專題】帶你徹底認識Paxos算法、Zab協定和Raft協定的原理和本質
Paxos算法安全性前提如下：
  • 隻有被提出的value才能被標明。
  • 隻有一個value被標明。
  • 如果某個程序認為某個value被標明了，那麼這個value必須是真的被標明的那個。
Paxos算法的過程描述：
Paxos算法類似于兩階段提送出，其算法執行過程分為兩個階段。具體如下

prepare階段

  • proposer提出一個編号為N的proposal，發送給半數以上的acceptor。
  • acceptor收到編号為N的prepare請求後:
    • 如果小于它已經響應過的請求，則拒絕回複或者回複error；
    • 如果N大于該Acceptor已經響應過的所有Prepare請求的編号，那麼它就會将它已經接受過（已經經過第二階段accept的提案）的編号最大的提案（如果有的話，如果還沒有的accept提案的話傳回{pok，null，null}）作為響應回報給Proposer，同時存儲更新本地對應的提案編号，并且該Acceptor承諾不再接受任何編号小于N的提案。
    • 分為兩種情況：
      • 如果acceptor已經接受過提案，傳回接受提案的最大value；
      • 如果還沒有接受過提案，就傳回{pok，null，null})

accept階段

  • 如果proposer收到半數以上的acceptor回複的編号為N的提案的prepare響應，那麼會發送一個針對[N,V]提案的Accept請求給半數以上的Acceptor。
注意：V就是收到的響應中編号最大的提案的value。
  • 如果響應中不包含任何提案，那麼V就由Proposer自己決定，可以是任意值。
  • 如果Acceptor收到一個針對編号為N的提案的Accept請求，隻要該Acceptor沒有對編号大于N的Prepare請求做出過響應，它就接受該提案。
  • 如果N小于Acceptor以及響應的prepare請求，則拒絕，不回應或回複error（當proposer沒有收到過半的回應，那麼他會重新進入第一階段，遞增提案号，重新提出prepare請求）。
具體如下圖所示：
【分布式技術專題】帶你徹底認識Paxos算法、Zab協定和Raft協定的原理和本質

過半的acceptor都接受提案後，learner會自動感覺到，并開始學習提案。（同一個程序可以同時扮演多個角色）

Learner的學習過程

learner學習過程包含兩種場景：
  • Learner所在節點參與了提案選舉，Learner需要知道其接受(accept)的提案值是否被選中(chosen)。
  • Learner所在節點已落後于其他節點，Learner需要選擇合适的政策快速完成追趕，并重新參與到提案選舉當中。

選中通知

  • 本節點Proposer的某個提案被選中(chosen)時，通過(MsgType_PaxosLearner_ProposerSendSuccess)消息通知到各個節點。
  • 正常情況下，所有節點處于online狀态，共同參與paxos選舉。是以為了避免instance id沖突，paxos建議隻由主節點的proposer發起提案，這樣保證接受提案和習得提案編号一緻。
  • 此時，Learn習得的提案值實際上就是本節點Accept的資料，是以learner隻更新記憶體狀态即可，無需再次落盤(acceptor已落盤)。
  • 最後，如果存在follower節點，資料同步到follower(follower節點不參與paxos算法，相當于某個paxos節點的同步備)。

提案值追趕

  • 一旦節點處于落後狀态，它無法再參與到paxos提案選舉中來。這時需要由learner發起主動學習完成追趕。
  • Paxos啟動時，啟動learner定時器，定時發送learn請求到各個節點，發送請求攜帶本節點的Instance ID、Node ID資訊。各節點收到該請求後，回複資料自主完成學習過程。
【分布式技術專題】帶你徹底認識Paxos算法、Zab協定和Raft協定的原理和本質

資料各節點保持資料一緻性

【分布式技術專題】帶你徹底認識Paxos算法、Zab協定和Raft協定的原理和本質

為什麼要有兩段送出

  • 一方面，第一次預送出後可能被告知已經有觀點了，此時他不應該提出自己的觀點，而應該盡快收斂，支援最新的觀點。
  • 另一方面，進行預加鎖。

怎麼保證Proposal編号唯一

  • 假設有K台Server運作paxos算法，那麼他們初始編号為0…k-1。以後編号每次增加k，進而保證全局唯一遞增。
  • 正式提案被半數以上Acceptor接受後，就可以确定最終被接受的提案就是該觀點。
  • 兩個半數以上的集合的一定存在交集。

Paxos算法有活鎖問題存在。

介紹了Paxos的算法邏輯，但在算法運作過程中，可能還會存在一種極端情況，當有兩個proposer依次提出一系列編号遞增的議案，那麼會陷入死循環，無法完成第二階段，也就是無法標明一個提案。如下圖：

【分布式技術專題】帶你徹底認識Paxos算法、Zab協定和Raft協定的原理和本質

Paxos算法的過半依據

  • 在Paxos算法中，采用了“過半”理念，也就是少數服從多數，這使Paxos算法具有很好的容錯性。那麼為什麼采用過半就可以呢？
  • Paxos基于的過半數學原理： 我們稱大多數（過半）程序組成的集合為法定集合， 兩個法定（過半）集合必然存在非空交集，即至少有一個公共程序，稱為法定集合性質。 例如A,B,C,D,F程序組成的全集，法定集合Q1包括程序A,B,C，Q2包括程序B,C,D，那麼Q1和Q2的交集必然不在空，C就是Q1，Q2的公共程序。如果要說Paxos最根本的原理是什麼，那麼就是這個簡單性質。也就是說：兩個過半的集合必然存在交集，也就是肯定是相等的，也就是肯定達成了一緻。

  • Paxos是基于消息傳遞的具有高度容錯性的分布式一緻性算法。Paxos算法引入了過半的概念，解決了2PC，3PC的太過保守的缺點，且使算法具有了很好的容錯性，另外Paxos算法支援分布式節點角色之間的輪換，這極大避免了分布式單點的出現，是以Paxos算法既解決了無限等待問題，也解決了腦裂問題，是目前來說最優秀的分布式一緻性算法。其中，Zookeeper的ZAB算法和Raft一緻性算法都是基于Paxos的。在後邊的文章中，我會逐漸介紹優秀的分布式協調服務架構，也是極優秀的工業一緻性算法的實作Zookeeper使用和實作。

ZAB算法指南

Zookeeper 采用的 ZAB協定也是基于 Paxos 算法實作的，不過 ZAB 對 Paxos 進行了很多改進與優化，兩者的設計目标也存在差異——ZAB 協定主要用于建構一個高可用的分布式資料主備系統，而 Paxos 算法則是用于建構一個分布式的一緻性狀态機系統。

ZAB協定全稱就是ZooKeeper Atomic Broadcast protocol，是ZooKeeper用來實作一緻性的算法，分成如下3個階段：

  • fast leader election：快速選舉階段
  • recovery：恢複階段
    • Discovery；
    • Synchrozation
  • broadcasting：廣播階段

先了解一些基本概念

  • electionEpoch：每執行一次leader選舉，electionEpoch就會自增，用來标記leader選舉的輪次
  • peerEpoch：每次leader選舉完成之後，都會選舉出一個新的peerEpoch，用來标記事務請求所屬的輪次
  • zxid：事務請求的唯一标記，由leader伺服器負責進行配置設定高32位是上述的peerEpoch，低32位是請求的計數，從0開始。
  • lastprocessZxid：最後一次commit的事務請求的zxid
  • LinkedList<Proposal> committedLog、long maxCommittedLog、long minCommittedLog：ZooKeeper會儲存最近一段時間内執行的事務請求議案，個數限制預設為500個議案。committedLog就是用來儲存議案的清單，maxCommittedLog表示最大議案的zxid，minCommittedLog表示committedLog中最小議案的zxid。
  • ConcurrentMap<Long, Proposal> outstandingProposals：Leader擁有的屬性，每當提出一個議案，都會将該議案存放至outstandingProposals，一旦議案被過半認同了，就要送出該議案，則從outstandingProposals中删除該議案。
  • ConcurrentLinkedQueue<Proposal> toBeApplied：Leader擁有的屬性，每當準備送出一個議案，就會将該議案存放至該清單中，一旦議案應用到ZooKeeper的記憶體樹中了，然後就可以将該議案從toBeApplied中删除。
  • state：目前伺服器的狀态
  • recvQueue：消息接收隊列，用于存放那些從其他伺服器接收到的消息。
  • queueSendMap：消息發送隊列，用于儲存那些待發送的消息，按照SID進行分組。
  • senderWorkerMap：發送器集合，每個SenderWorker消息發送器，都對應一台遠端Zookeeper伺服器，負責消息的發送，也按照SID進行分組。
  • lastMessageSent：最近發送過的消息，為每個SID保留最近發送過的一個消息。
在ZAB協定中，服務的的狀态state有四種：
  • LOOKING：進入leader選舉狀态
  • FOLLOWING：leader選舉結束，進入follower狀态
  • LEADING：leader選舉結束，進入leader狀态
  • OBSERVING：處于觀察者狀态

協定算法的具體描述

Broadcasting過程
  1. leader針對用戶端的事務請求，創造出一個提案，zxid由leader決定，并将該提案的zxid，提案放到outstandingProposals Map中。
  2. leader向所有的follower發送該提案，如果過半的follower回複OK的話，則leader認為可以送出該議案，則将該議案從outstandingProposals中删除。
  3. 然後存放到toBeApplied中leader對該議案進行送出，會向所有的follower發送送出該議案的指令，leader自己也開始執行送出過程，會将該請求的内容應用到ZooKeeper的記憶體樹中。
  4. 然後更新lastProcessedZxid為該請求的zxid，同時将該請求的議案存放到上述committedLog，同時更新maxCommittedLog和minCommittedLog。
  5. leader回複用戶端，并将提案中ToBeApplied中删除
fast leader election過程
選舉過程關注兩個要點：剛啟動時進行leader選舉和選舉完leader後，剛啟動的server怎麼感覺到leader，投票過程有兩個比較重要的資料：
  • HashMap<Long, Vote> recvset：用于收集LOOKING、FOLLOWING、LEADING狀态下的server的投票
  • HashMap<Long, Vote> outofelection：用于收集FOLLOWING、LEADING狀态下的server的投票（說明leader選舉已經完成）

具體的過程有：

  1. 伺服器先自增electionEpoch，給自己投票：
  • 從快照日志和事務日志中加載資料，得到本機器的記憶體樹資料，以及lastProcessedZxid。投票内容為：
    • proposedLeader：server自身的myid值，初始為本機器的id
    • proposedZxid：最大事務zxid，初始為本機器的lastProcessedZxid
    • proposedEpoch:peerEpoch值，由上述的lastProcessedZxid的高32得到
    • 然後向所有的伺服器發送投票。
  1. server接收到投票通知後，進行PK。
    • 如果收到的通知中的electionEpoch比自己的大，則更新自己的electionEpoch為serverA的electionEpoch；
    • 如果、收到的通知中的electionEpoch比自己的小，則向serverA發送一個通知，将自己的投票以及electionEpoch發送給serverA，serverA收到後就會更新自己的electionEpoch。
    • 如果electionEpoch相同，PK的規則是proposedZxid，然後再是myId。
  2. 根據server的狀态來判定leader
    • 如果目前發來的投票的server的狀态是LOOKING狀态，則隻需要判斷本機器的投票是否在recvset中過半了，如果過半了則說明leader選舉就算成功了，如果目前server的id等于上述過半投票的proposedLeader,則說明自己将成為了leader，否則自己将成為了follower。
    • 如果目前發來的投票的server的狀态是FOLLOWING、LEADING狀态，則說明leader選舉過程已經完成了，則發過來的投票就是leader的資訊，這裡就需要判斷發過來的投票是否在recvset或者outofelection中過半了，同時還要檢查leader是否給自己發送過投票資訊，從投票資訊中确認該leader是不是LEADING狀态。
Recovery過程
一旦leader選舉完成，就開始進入恢複階段，就是follower要同步leader上的資料資訊。
  1. 通信初始化
leader會建立一個ServerSocket，接收follower的連接配接，leader會為每一個連接配接會用一個LearnerHandler線程來進行服務；
  1. 重新為peerEpoch選舉出一個新的peerEpoch
    • follower會向leader發送一個Leader，FOLLOWERINFO資訊，包含自己的peerEpoch資訊。
    • leader的LearnerHandler會擷取到上述peerEpoch資訊，從中選出一個最大的peerEpoch，然後加1作為新的peerEpoch。
    • 然後leader的所有LearnerHandler會向各自的follower發送一個Leader.LEADERINFO資訊，包含上述新的peerEpoch；
    • follower會使用上述peerEpoch來更新自己的peerEpoch，同時将自己的lastProcessedZxid發給leader，leader的根據這個lastProcessedZxid和leader的lastProcessedZxid之間的差異進行同步。
  2. 已經處理的事務議案的同步
    • 判斷LearnerHandler中的lastProcessedZxid是否在minCommittedLog和maxCommittedLog之間
    • LearnerHandler中的lastProcessedZxid和leader的lastProcessedZxid一緻，則說明已經保持同步了
    • 如果lastProcessedZxid在minCommittedLog和maxCommittedLog之間，從lastProcessedZxid開始到maxCommittedLog結束的這部分議案，重新發送給該LearnerHandler對應的follower，同時發送對應議案的commit指令。
上述可能存在一個問題：即lastProcessedZxid雖然在他們之間，但是并沒有找到lastProcessedZxid對應的議案，即這個zxid是leader所沒有的，此時的政策就是完全按照leader來同步，删除該follower這一部分的事務日志，然後重新發送這一部分的議案，并送出這些議案。
  • 如果lastProcessedZxid大于maxCommittedLog，則删除該follower大于部分的事務日志
  • 如果lastProcessedZxid小于minCommittedLog，則直接采用快照的方式來恢複。
  1. 未處理的事務議案的同步
    • LearnerHandler還會從leader的toBeApplied資料中将大于該LearnerHandler中的lastProcessedZxid的議案進行發送和送出（toBeApplied是已經被确認為送出的）
    • LearnerHandler還會從leader的outstandingProposals中大于該LearnerHandler中的lastProcessedZxid的議案進行發送，但是不送出（outstandingProposals是還沒被被确認為送出的）
  2. 将LearnerHandler加入到正式follower清單中
  3. LearnerHandler發送Leader.NEWLEADER以及Leader.UPTODATE指令。
    • leader開始進入心跳檢測過程，不斷向follower發送心跳指令，不斷檢是否有過半機器進行了心跳回複，如果沒有過半，則執行關閉操作，開始進入leader選舉狀态；
    • LearnerHandler向對應的follower發送Leader.UPTODATE，follower接收到之後，開始和leader進入Broadcast處理過程。

事務持久化和恢複過程

  • 事務持久化分為：broadcasting持久化和leader shutdown過程的持久化。
    • leader針對每次事務請求都會生成一個議案，然後向所有的follower發送該議案。follower收到提案後，将該議案記錄到事務日志中，每當記滿100000個（預設），則事務日志執行flush操作，同時開啟一個新的檔案來記錄事務日志
    • 同時會執行記憶體樹的快照，snapshot.[lastProcessedZxid]作為檔案名建立一個新檔案，快照内容儲存到該檔案中
    • 一旦leader過半的心跳檢測失敗，則執行shutdown方法，在該shutdown中會對事務日志進行flush操作
事務的恢複分為快照恢複和日志恢複。
  • 事務快照的恢複：會在事務快照檔案目錄下找到最近的100個快照檔案，并排序，最新的在前；對上述快照檔案依次進行恢複和驗證，一旦驗證成功則退出，否則利用下一個快照檔案進行恢複。恢複完成更新最新的lastProcessedZxid；
  • 事務日志的恢複：從事務日志檔案目錄下找到zxid大于等于上述lastProcessedZxid的事務日志，然後對上述事務日志進行周遊，應用到ZooKeeper的記憶體樹中，同時更新lastProcessedZxid，同時将上述事務日志存儲到committedLog中，并更新maxCommittedLog、minCommittedLog

Raft背景

在分布式系統中，一緻性算法至關重要。在所有一緻性算法中，Paxos 最負盛名，它由萊斯利·蘭伯特（Leslie Lamport）于 1990 年提出，是一種基于消息傳遞的一緻性算法，被認為是類似算法中最有效的。

Paxos算法雖然很有效，但複雜的原理使它實作起來非常困難，截止目前，實作 Paxos 算法的開源軟體很少，比較出名的有 Chubby、LibPaxos。

  • 由于Paxos算法過于複雜、實作困難，極大地制約了其應用，而分布式系統領域又亟需一種高效而易于實作的分布式一緻性算法，在此背景下，Raft 算法應運而生。
  • Raft是一個共識算法（consensus algorithm），所謂共識，就是多個節點對某個事情達成一緻的看法，即使是在部分節點故障、網絡延時、網絡分割的情況下。
  • 共識算法的實作一般是基于複制狀态機（Replicated state machines），何為複制狀态機：簡單來說：相同的初識狀态 + 相同的輸入 = 相同的結束狀态。
Raft 角色
一個Raft叢集包含若幹個節點，這些節點分為三種狀态：Leader、 Follower、Candidate，每種狀态負責的任務也是不一樣的。正常情況下，叢集中的節點隻存在 Leader與Follower兩種狀态。
  • leader：負責日志的同步管理，處理來自用戶端的請求，與Follower保持heartBeat的聯系；
  • follower：響應 Leader 的日志同步請求，響應Candidate的邀票請求，以及把用戶端請求到Follower的事務轉發（重定向）給Leader；
  • candidate：負責選舉投票，叢集剛啟動或者Leader當機時，狀态為Follower的節點将轉為Candidate并發起選舉，選舉勝出（獲得超過半數節點的投票）後，從Candidate轉為Leader狀态。
還有一個關鍵概念：term（任期）。以選舉（election）開始，每一次選舉term都會自增，充當了邏輯時鐘的作用。
Raft的3個子問題

為簡化邏輯和實作，Raft 将一緻性問題分解成了三個相對獨立的子問題。

  • 選舉（Leader Election）：當 Leader 當機或者叢集初創時，一個新的 Leader 需要被選舉出來；
  • 日志複制（Log Replication）：Leader 接收來自用戶端的請求并将其以日志條目的形式複制到叢集中的其它節點，并且強制要求其它節點的日志和自己保持一緻；
  • 安全性（Safety）：如果有任何的伺服器節點已經應用了一個确定的日志條目到它的狀态機中，那麼其它伺服器節點不能在同一個日志索引位置應用一個不同的指令。

選舉過程

如果follower在election timeout内沒有收到來自leader的心跳，則會主動發起選舉。
第一階段：所有節點都是 Follower。
Raft 叢集在剛啟動（或 Leader 當機）時，所有節點的狀态都是 Follower，初始 Term（任期）為 0。同時啟動選舉定時器，每個節點的選舉定時器逾時時間都在 100~500 毫秒之間且并不一緻。
【分布式技術專題】帶你徹底認識Paxos算法、Zab協定和Raft協定的原理和本質
第二階段：Follower 轉為 Candidate 并發起投票。
沒有leader後，followers狀态自動轉為candidate，并向叢集中所有節點發送投票請求并且重置選舉定時器。

投票過程有：

  • 增加節點本地的current term ，切換到candidate狀态
  • 投自己一票，并行給其他節點發送 RequestVote RPCs
  • 等待其他節點的回複，可能出現三種結果：
    • 收到majority的投票（含自己的一票），則赢得選舉，成為leader
    • 被告知别人已當選，那麼自行切換到follower
    • 一段時間内沒有收到majority投票，則保持candidate狀态，重新發出選舉
第三階段：投票政策

投票的限制條件有：

  • 在一個term内，一個節點隻允許發出一次投票；
  • 候選人知道的資訊不能比自己的少（這一部分，後面介紹log replication和safety的時候會詳細介紹）
  • first-come-first-served 先來先得
  • 如果參加選舉的節點是偶數個，raft通過randomized election timeouts來盡量避免平票情況，也要求節點的數目都是奇數個，盡量保證majority的出現。

log Replication原理

  • 當leader選舉成功後，用戶端所有的請求都交給了leader，leader排程請求的順序性和followers的狀态一緻性。
  • 在叢集中，所有的節點都可能變為leader，為了保證後續leader節點變化後依然能夠使叢集對外保持一緻，需要通過Log Replication機制來解決如下兩個問題：
  • Follower與Leader節點相同的順序依次執行每個成功提案;
  • 每個成功送出的提案必須有足夠多的成功副本，來保證後續的通路一緻
第一階段：用戶端請求送出到 Leader。

Leader 在收到client請求提案後，會将它作為日志條目（Entry）寫入本地log中。需要注意的是，此時該 Entry 的狀态是未送出（Uncommitted），Leader 并不會更新本地資料，是以它是不可讀的。

第二階段：Leader 将 Entry 發送到其它 Follower
  • Leader 與 Floolwers 之間保持着心跳聯系，随心跳 Leader 将追加的 Entry（AppendEntries）并行地發送給其它的 Follower，并讓它們複制這條日志條目，這一過程稱為複制（Replicate）。
  • 為什麼 Leader 向 Follower 發送的 Entry 是 AppendEntries，因為 Leader 與 Follower 的心跳是周期性的，而一個周期間 Leader 可能接收到多條用戶端的請求，是以，随心跳向 Followers 發送的大機率是多個 Entry，即 AppendEntries。
  • Leader 向 Followers 發送的不僅僅是追加的 Entry（AppendEntries）在發送追加日志條目的時候，Leader 會把新的日志條目緊接着之前條目的索引位置（prevLogIndex）， Leader 任期号（Term）也包含在其中。如果 Follower 在它的日志中找不到包含相同索引位置和任期号的條目，那麼它就會拒絕接收新的日志條目，因為出現這種情況說明 Follower 和 Leader 不一緻。
  • 如何解決 Leader 與 Follower 不一緻的問題，正常情況下，Leader 和 Follower 的日志保持一緻。然而，Leader 和 Follower 一系列崩潰的情況會使它們的日志處于不一緻狀态。

有三種情況：

  1. Follower落後新的leader，丢失一些在新的 Leader 中有的日志條目
  2. Follower領先新的leader，有一些 Leader 沒有的日志條目，
  3. 或者兩者都發生。丢失或者多出日志條目可能會持續多個任期。
要使 Follower 的日志與 Leader 恢複一緻，Leader 必須找到最後兩者達成一緻的地方（就是回溯，找到兩者最近的一緻點），然後删除從那個點之後的所有日志條目，發送自己的日志給 Follower。Leader 為每一個 Follower 維護一個 nextIndex，它表示下一個需要發送給 Follower 的日志條目的索引位址。當一個 Leader 剛獲得權力的時候，它初始化所有的 nextIndex 值，為自己的最後一條日志的 index 加 1。如果一個 Follower 的日志和 Leader 不一緻，那麼在下一次附加日志時一緻性檢查就會失敗。在被 Follower 拒絕之後，Leader 就會減小該 Follower 對應的 nextIndex 值并進行重試。最終 nextIndex 會在某個位置使得 Leader 和 Follower 的日志達成一緻。當這種情況發生，附加日志就會成功，這時就會把 Follower 沖突的日志條目全部删除并且加上 Leader 的日志。一旦附加日志成功，那麼 Follower 的日志就會和 Leader 保持一緻，并且在接下來的任期繼續保持一緻。
第三階段：Leader 等待 Followers 回應。

Followers 接收到 Leader 發來的複制請求後，有兩種可能的回應：

  • 寫入本地日志中，傳回 Success；
  • 一緻性檢查失敗，拒絕寫入，傳回 False，原因和解決辦法上面已做了詳細說明。
  • 當 Leader 收到大多數 Followers 的回應後，會将第一階段寫入的 Entry 标記為送出狀态（Committed），并把這條日志條目應用到它的狀态機中。
第四階段：Leader 回應用戶端。

完成前三個階段後，Leader會向用戶端回應 OK，表示寫操作成功。

第五階段，Leader 通知 Followers Entry 已送出

Leader 回應用戶端後，将随着下一個心跳通知 Followers，Followers 收到通知後也會将 Entry 标記為送出狀态。至此，Raft 叢集超過半數節點已經達到一緻狀态，可以確定強一緻性。

raft safety保證

1） election safety: 在一個term内，至多有一個leader被選舉出來。raft算法通過

一個節點某一任期内最多隻能投一票；

隻有獲得majority投票的節點才會成為leader。

2）log matching：說如果兩個節點上的某個log entry的log index相同且term相同，那麼在該index之前的所有log entry應該都是相同的。leader在某一term的任一位置隻會建立一個log entry，且log entry是append-only。

3）consistency check。leader在AppendEntries中包含最新log entry之前的一個log 的term和index，如果follower在對應的term index找不到日志，那麼就會告知leader不一緻。當出現了leader與follower不一緻的情況，leader強制follower複制自己的log。

3）leader completeness ：如果一個log entry在某個任期被送出（committed），那麼這條日志一定會出現在所有更高term的leader的日志裡面。

一個日志被複制到majority節點才算committed

一個節點得到majority的投票才能成為leader，而節點A給節點B投票的其中一個前提是，B的日志不能比A的日志舊。

4）stale leader: 落後的leader，但在網絡分割（network partition）的情況下，可能會出現兩個leader，但兩個leader所處的任期是不同的。而在raft的一些實作或者raft-like協定中，leader如果收不到majority節點的消息，那麼可以自己step down，自行轉換到follower狀态。

5）leader crash：新的節點成為Leader，為了不讓資料丢失，希望新Leader包含所有已經Commit的Entry。為了避免資料從Follower到Leader的反向流動帶來的複雜性，Raft限制新Leader一定是目前Log最新的節點，即其擁有最多最大term的Log Entry。

6）State Machine Safety

log replication限制：

zab Paxo raft 分布式協定 一緻性協定
上一篇: 程序間通信IPC-命名管道FIFO
下一篇: 站在大學的最後一道十字路口

繼續閱讀