比較zab、paxos和raft的算法的異同

### Zab 與 Paxos

聯系

（1）兩者建構的系統都有一個 Leader 角色，Leader 程序負責協調多個 Follower 程序的運作（MultiPaxos不在此列）

（2）Leader 程序都會等待超過半數的 Follower 程序做出正确的回報後，才會将一個提案進行送出（都是基于quorum 機制）

（3）在 Zab 協定中每個 Proposal 中都包含一個 epoch 值，用來代表目前的 Leader 周期；在 Paxos 算法中，同樣存在這樣一個辨別（Ballot）

差別

（1）兩者的初衷或者說設計目标不一樣

Paxos 算法用于建構一個分布式的一緻性狀态機系統；

Zab 算法用于建構一個高可用的分布式資料主備系統。

（2）流程上有差別

Paxos 算法，選舉出一個新的 Leader 程序需要進行兩個階段。

第一個階段是讀階段，這個階段中，這個新的主程序會通過和所有其他程序進行通信的方式收集上一個主程序提出的提案，并将它們送出。

第二個階段是寫階段，這個階段中，目前主程序 Leader 開始提出它自己的提案。

Zab 算法存在三個階段：發現階段、同步階段、廣播階段，其中發現階段等同于 Paxos 的讀階段，廣播階段等同于 Paxos 的寫階段。

同步階段是 Zab 算法新添加的，在同步階段，新的 Leader 會确儲存在過半的 Follower 已經送出了之前 Leader 周期中的所有事務 Proposal。

同步階段的引入，能夠有效地保證 Leader 在新的周期提出事物 Proposal 之前，所有的程序都已經完成了對之前所有事務的送出。

### Zab 與 Raft

相同點

（1）都使用 timeout 來重新選擇 leader

（2）采用 quorum 來确定整個系統的一緻性（也就是對某一個值的認可），這個 quorum 一般實作是叢集中半數以上的伺服器，zookeeper 裡還提供了帶權重的 quorum 實作

（3）都由 leader 來發起寫操作

（4）都采用心跳檢測存活性

（5）zookeeper 的 zab 實作裡選主要求選出來的主擁有 quorum 裡最新的曆史，而 raft 的 follower 的選主投票根據 term 的大小+日志完成度來選擇投票給誰，這點上來看是比較類似的

（6）日志和狀态機

Zab 和 Raft 都是同時存在 log（還有快照技術）和狀态機（記憶體樹）的存儲結構。

日志是以 log 和快照的形式持久化到磁盤，儲存的是資料寫的完整過程，為重新開機加載曆史資料提供了便利，避免了伺服器當機造成的資料丢失。

狀态機（記憶體樹）把資料加載到記憶體中，避免了查詢操作時磁盤讀取，讀取的是資料的最終值，進而提升讀取的性能。

不同點

（1）zab 用的是 epoch 和 count 的組合來唯一表示一個值, 而 raft 用的是 term 和 index

（2）raft 協定資料隻有單向地從 leader 到 follower（成為 leader 的條件之一就是擁有最新的 log），而 zab 的 zookeeper 實作中 ，一個 prospective leader 需要将自己的 log 更新為 quorum 裡面最新的 log，然後才好在 synchronization 階段将 quorum 裡的其他機器的 log 都同步到一緻

（3）請求的處理方式不同

ZK 叢集中的 client 和任意一個 Node 建立 TCP 的長連接配接，完成所有的互動動作，而 Raft 第一次随機的擷取到一個節點，然後找到 Leader 後，後續直接和 leader 互動（存疑）。

ZK 中的讀請求，直接由連接配接的 Node 處理，不需要和 leader 彙報，也就是 Consul 中的 stale 模式。這種模式可能導緻讀取到的資料是過時的，但是可以保證一定是半數節點之前确認過的資料。

為了避免 Follower 的資料過時，ZK 有 sync()方法，可以保證讀取到最新的資料。可以調用 sync()之後，再查詢，確定所有的資料一緻後再傳回結果。

角色 ZK 引入了 Observer 的角色來提升性能，既可以大幅提升讀取的性能，也可以不影響寫的速度和選舉的速度，同時一定程度上增加了容錯的能力。

（4）選主投票的差別

ZK 叢集之間投票消息是單向、網狀的，類似于廣播，比如 A 廣播 A 投票給自己，廣播出去，然後 B 接收到 A 的這個消息之後，會 PK A 的資料，如果 B 更适合當 leader（資料更新或者 myid 更大），B 會歸檔 A 的這個投票，但是不會更新自己的資料，也不會廣播任何消息。除非發現 A 的資料比 B 目前存儲的資料更适合當 leader，就更新自己的資料，且廣播自己的最新的投票消息。

而 Raft 叢集之間的所有消息都是雙向的，發起一個 RPC，會有個回複結果。比如 A 向 B 發起投票，B 要麼回報投票成功，要麼回報投票不成功。

ZK 叢集中，一個節點在一個 epoch 下是可以發起多次投票的，當節點發現有比之前更新的資料更适合的 leader 時，就會廣播自己的最新投票消息，結合 recvset 這個 Set 的結構，來更新某個節點最新的投票結果。而 Raft 的 follower 在一個 term 裡隻能投票一次。

ZK 叢集中，因為引入了 myid 的概念，系統傾向讓資料最新和 myid 最大的節點當 leader。是以即使有半數節點都投票給同一個 Node 當 leader，這個 Node 也不一定能成為 leader，需要等待 200ms，看是不是有更适合的 leader 産生。但是在 Raft 系統中，隻要某個 candidate 發現自己投票過半了，就一定能成為 leader。

ZK 叢集中，每一輪的選舉一定會選出一個 leader，因為每個節點允許多次投票，而且會廣播自己的最新投票結果。而 Raft 系統可能涉及選票瓜分，需要重新發起一輪選舉才能選出 leader，是通過選舉逾時時間的随機來降低選票瓜分的機率。是以 ZK 的選舉理論上一般需要花費更多的時間，但是隻需要一輪。Raft 每一輪選舉的時間是大緻固定的，但是不一定一輪就能選出 leader。

ZK 叢集中，成為公認的 leader 條件更苛刻，raft 模式下，隻要新 leader 發一個指令為空的 Log 出來，大家就會認同這個節點為 leader，但是在 ZK 叢集中，追随 leader 的 2 種條件都很苛刻：

要麼 recvset 中半數節點的選舉 following 投票給 A，才會認可 A 為自己的 leader

要麼 outofelection 中半數節點都認可 A 為 leader，自己才會認可 A 為自己的 leader

（5）事務操作的差別

Raft 系統中的事務消息是通過雙向的 RPC 來完成的，而 Zab 中，則是單向的，一來一回兩個消息來完成的。明顯 Zab 的性能更好，不需要浪費 leader 一個線程去等待 follower 完成業務操作。

Zab 中 leader 發送一個 Proposal 消息給 follower，發送完成。當 follower 完成 proposal 過程時，再發送一個消息 ACK 到 leader，發送完成。leader 統計 ACK 數量過半時，觸發廣播 commit。