你一定要了解的分布式協定

分布式一緻性協定

目前業界主流的分布式一緻性協定主要有如下幾種：

• totem協定（簡單即有效）
• totem協定，全稱是The Totem Single-Ring Ordering and Membership Protocol，是一個基于令牌環的分布式一緻性算法。corosync基于totem協定實作。
• paxos協定（二階段送出）
• raft協定（二階段送出，基于paxos協定完善和改進）
• Raft協定就是Paxos的衍生，etcd基于raft協定實作。
• zab協定（二階段送出）
• ZAB協定是為分布式協調服務Zookeeper專門設計的一種支援崩潰恢複和原子廣播協定。

totem協定

totem協定，全稱是The Totem Single-Ring Ordering and Membership Protocol，是一個基于令牌環的分布式一緻性算法。一個令牌在叢集節點之間傳遞，拿到令牌的節點才能夠發消息，消息通過UDP廣播發送。是以，totem隻适合在區域網路裡的小叢集使用，這種情況下，這個算法性能還算高的。從CAP來說，totem具有強一緻性，但幾乎沒有分區容錯性，在網絡出現分區時，totem會腦裂，當網絡恢複時，會造成消息丢失。

在多個節點組成的叢集中，totem實作讓一個節點發送消息，其它所有節點都能全部收到，并且有序的送出給上層應用。

說起totem協定，最簡單的形象就是，他将多個節點組成一個令牌環。多個節點手拉手形成一個圈，大家依次的傳遞token。隻有擷取到token的節點才有發送消息的權利。簡單有效的解決了在分布式系統中各個節點的同步問題，因為隻有一個節點會在一個時刻發送消息，不會出現沖突。當然，如果有節點發生意外時，令牌環就會斷掉，此時大家不能夠通信，而是重新組建出一個新的令牌環。

totem的節點有四個狀态，也是組建叢集的4個階段。

Gather階段： 這個階段用于每個節點向外界廣播自己的存在并收集其它節點的存在

Commit階段： 這個階段會産生一個代表節點，該節點向其它所有節點收集資訊，并将收集的資訊傳遞給其它所有節點，用于後續階段

Recovery階段： 這個階段用于新舊叢集交替時，舊叢集成員用新叢集傳遞舊叢集的消息，使舊叢集成員達到所有節點消息全部有序送出到上層

Operational階段： 這個階段是叢集組建完成正常工作的狀态，這個狀态一個節點發送的消息其它節點都會全部有序送出給上層

通信方式。當叢集有節點要發起通信時，需要等待token。當拿到token後，先廣播這次需要發送的資料，然後傳遞token來确認所有人都接收到消息。如果确認成功，釋放token。節點的加入和退出。當叢集中有節點加入時，加入的節點廣播一個加入資訊，所有人都開始廣播自己的資訊，當所有人都獲得同伴資訊，開始由id最小的人送出一個token，交由所有節點确認。如果都确認後，則節點正式加入，開始正常運作。當叢集有節點退出時，由于令牌環斷鍊，觸發token逾時，則同樣開始廣播資訊，然後由最小id送出token，經過确認後恢複正常。

raft協定

Paxos 算法的描述偏學術化，缺失了很多細節，無法直接應用于工程領域。實際工程應用中的分布式算法大多是 Paxos 的變種，Raft協定就是Paxos的簡化。

RAFT算法分為兩個階段：Leader選舉，日志複制。也有三種角色，分别為：

Leader（上司者）：負責發送要進行共識的資料，如果用戶端發送的資料不是發送到Leader而是其他角色，其他角色會進行轉發至Leader。

Follower（追随者）：參與共識的角色

Candidate（候選者）：如果Follower沒有收到Leader的心跳響應超過150——300ms，會進行Leader選舉

正常運作的情況下，會有一個Leader，其他全為Follower，Follower隻會響應Leader和Candidate的請求，而用戶端的請求則全部由Leader處理，即使有用戶端請求了一個Follower也會将請求重定向到Leader。Candidate代表候選人，出現在選舉Leader階段，選舉成功後Candidate将會成為新的Leader。

Raft 将一緻性問題分解為 3 個獨立的子問題：

Leader 選舉Election：Leader 程序失效後能夠自動選舉出一個新的 Leader

日志複制Replication：Leader 保證其他節點的日志與其保持一緻

狀态安全Safety：Leader 保證狀态機執行指令的順序與内容完全一緻

leader選舉所有節點初始狀态為Follower狀态，此時沒有Leader，肯定會與Leader的心跳逾時（一般150——300ms，随機的，這樣就是想誰先發出競選，誰當選leader），此時Candidate就會發出leader競選給其他節點（大家快選我啊，leader挂掉了）；其他節點收到競選請求，會響應同意，當一個Candidate收到大多數（n/2 + 1）節點的回複，就成為leader。然後與Candidate保持心跳連接配接。Raft有個Term（任期）的概念，隻有在發生Leader選舉階段，term+1，表示新的leader産生，挂掉的節點，或者挂掉的leader重新開機後，會發現自己的term小于最新的，此時就會切換到日志複制，去同步之前丢失的消息。如果同時有多個Candidate發出競選，并且都沒有獲得大多數投票，會一直進行競選，直到選出leader日志複制leader收到用戶端或者其他節點轉發過來需要共識的值，會跟随心跳一起廣播給其他節點，進行寫入其他節點寫入後響應成功給leader，當leader收到大多數的follower響應的成功，發出commit指令其他節點收到commit後，進行事務送出，響應成功為leader，leader收到大多數的commit成功，Raft完成

ZAB協定

Zookeeper是一個為分布式應用提供高效且可靠的分布式協調服務。在解決分布式一緻性方面，Zookeeper并沒有使用Paxos，而是采用了ZAB協定。

ZAB協定基本與Raft相同，都是Multi Paxos的衍生。ZAB與Raft在一些名詞的叫法上有差別：如ZAB将某一個Leader的周期稱為epoch，而Raft則稱之為term。在實作上也有些許不同：Raft為了保證日志連續性，心跳方向為Leader至Follower，ZAB則相反。

消息廣播模式

ZAB協定的消息廣播過程使用的是一個原子廣播協定，類似一個2PC二階段送出過程。

Leader将用戶端的request轉化成一個Proposal（提議）；

Leader為每一個Follower準備了一個FIFO隊列，并把Proposal發送到隊列上；

Leader若收到follower的半數以上ACK回報；

Leader向所有的follower發送commit。

崩潰恢複

ZAB 定義了 2 個原則：

ZAB 協定確定那些已經在 Leader 送出的事務最終會被所有伺服器送出。

ZAB 協定確定丢棄那些隻在 Leader 提出/複制，但沒有送出的事務。

是以，ZAB 設計了下面這樣一個選舉算法：能夠確定送出已經被 Leader 送出的事務，同時丢棄已經被跳過的事務。針對這個要求，如果讓 Leader 選舉算法能夠保證新選舉出來的 Leader 伺服器擁有叢集中所有機器編号（即 ZXID最大）的事務，那麼就能夠保證這個新選舉出來的 Leader 一定具有所有已經送出的提案。

reference

1. https://blog.csdn.net/zancijun1666/article/details/83512038
2. https://blog.csdn.net/cloudresearch/article/details/23127985
3. https://blog.csdn.net/TJtulong/article/details/106510970
4. https://blog.csdn.net/TJtulong/article/details/106510970