zookeeper的paxos演算法

Ⅰ Raft 演算法（詳細版）

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

Paxos 演算法雖然很有效，但復雜的原理使它實現起來非常困難，截止目前，實現 Paxos 演算法的開源軟體很少，比較出名的有 Chubby、LibPaxos。此外，Zookeeper 採用的 ZAB（Zookeeper Atomic Broadcast）協議也是基於 Paxos 演算法實現的，不過 ZAB 對 Paxos 進行了很多改進與優化，兩者的設計目標也存在差異——ZAB 協議主要用於構建一個高可用的分布式數據主備系統，而 Paxos 演算法則是用於構建一個分布式的一致性狀態機系統。

由於 Paxos 演算法過於復雜、實現困難，極大地制約了其應用，而分布式系統領域又亟需一種高效而易於實現的分布式一致性演算法，在此背景下，Raft 演算法應運而生。

Raft 演算法在斯坦福 Diego Ongaro 和 John Ousterhout 於 2013 年發表的《In Search of an Understandable Consensus Algorithm》中提出。相較於 Paxos，Raft 通過邏輯分離使其更容易理解和實現，目前，已經有十多種語言的 Raft 演算法實現框架，較為出名的有 etcd、Consul 。

根據官方文檔解釋，一個 Raft 集群包含若干節點，Raft 把這些節點分為三種狀態：Leader、 Follower、Candidate，每種狀態負責的任務也是不一樣的。正常情況下，集群中的節點只存在 Leader 與 Follower 兩種狀態。

• Leader（領導者） ：負責日誌的同步管理，處理來自客戶端的請求，與Follower保持heartBeat的聯系；

• Follower（追隨者） ：響應 Leader 的日誌同步請求，響應Candidate的邀票請求，以及把客戶端請求到Follower的事務轉發（重定向）給Leader；

• Candidate（候選者） ：負責選舉投票，集群剛啟動或者Leader宕機時，狀態為Follower的節點將轉為Candidate並發起選舉，選舉勝出（獲得超過半數節點的投票）後，從Candidate轉為Leader狀態。

通常，Raft 集群中只有一個 Leader，其它節點都是 Follower。Follower 都是被動的，不會發送任何請求，只是簡單地響應來自 Leader 或者 Candidate 的請求。Leader 負責處理所有的客戶端請求（如果一個客戶端和 Follower 聯系，那麼 Follower 會把請求重定向給 Leader）。

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

• 選舉（Leader Election） ：當 Leader 宕機或者集群初創時，一個新的 Leader 需要被選舉出來；

• 日誌復制（Log Replication） ：Leader 接收來自客戶端的請求並將其以日誌條目的形式復制到集群中的其它節點，並且強制要求其它節點的日誌和自己保持一致；

• 安全性（Safety） ：如果有任何的伺服器節點已經應用了一個確定的日誌條目到它的狀態機中，那麼其它伺服器節點不能在同一個日誌索引位置應用一個不同的指令。

根據 Raft 協議，一個應用 Raft 協議的集群在剛啟動時，所有節點的狀態都是 Follower。由於沒有 Leader，Followers 無法與 Leader 保持心跳（Heart Beat），因此，Followers 會認為 Leader 已經下線，進而轉為 Candidate 狀態。然後，Candidate 將向集群中其它節點請求投票，同意自己升級為 Leader。如果 Candidate 收到超過半數節點的投票（N/2 + 1），它將獲勝成為 Leader。

第一階段：所有節點都是 Follower。

上面提到，一個應用 Raft 協議的集群在剛啟動（或 Leader 宕機）時，所有節點的狀態都是 Follower，初始 Term（任期）為 0。同時啟動選舉定時器，每個節點的選舉定時器超時時間都在 100~500 毫秒之間且並不一致（避免同時發起選舉）。

第二階段：Follower 轉為 Candidate 並發起投票。

沒有 Leader，Followers 無法與 Leader 保持心跳（Heart Beat），節點啟動後在一個選舉定時器周期內未收到心跳和投票請求，則狀態轉為候選者 Candidate 狀態，且 Term 自增，並向集群中所有節點發送投票請求並且重置選舉定時器。

注意，由於每個節點的選舉定時器超時時間都在 100-500 毫秒之間，且彼此不一樣，以避免所有 Follower 同時轉為 Candidate 並同時發起投票請求。換言之，最先轉為 Candidate 並發起投票請求的節點將具有成為 Leader 的「先發優勢」。

第三階段：投票策略。

節點收到投票請求後會根據以下情況決定是否接受投票請求（每個 follower 剛成為 Candidate 的時候會將票投給自己）：

請求節點的 Term 大於自己的 Term，且自己尚未投票給其它節點，則接受請求，把票投給它；

請求節點的 Term 小於自己的 Term，且自己尚未投票，則拒絕請求，將票投給自己。

第四階段：Candidate 轉為 Leader。

一輪選舉過後，正常情況下，會有一個 Candidate 收到超過半數節點（N/2 + 1）的投票，它將勝出並升級為 Leader。然後定時發送心跳給其它的節點，其它節點會轉為 Follower 並與 Leader 保持同步，到此，本輪選舉結束。

注意：有可能一輪選舉中，沒有 Candidate 收到超過半數節點投票，那麼將進行下一輪選舉。

在一個 Raft 集群中，只有 Leader 節點能夠處理客戶端的請求（如果客戶端的請求發到了 Follower，Follower 將會把請求重定向到 Leader） ，客戶端的每一個請求都包含一條被復制狀態機執行的指令。Leader 把這條指令作為一條新的日誌條目（Entry）附加到日誌中去，然後並行得將附加條目發送給 Followers，讓它們復制這條日誌條目。

當這條日誌條目被 Followers 安全復制，Leader 會將這條日誌條目應用到它的狀態機中，然後把執行的結果返回給客戶端。如果 Follower 崩潰或者運行緩慢，再或者網路丟包，Leader 會不斷得重復嘗試附加日誌條目（盡管已經回復了客戶端）直到所有的 Follower 都最終存儲了所有的日誌條目，確保強一致性。

第一階段：客戶端請求提交到 Leader。

如下圖所示，Leader 收到客戶端的請求，比如存儲數據 5。Leader 在收到請求後，會將它作為日誌條目（Entry）寫入本地日誌中。需要注意的是，此時該 Entry 的狀態是未提交（Uncommitted），Leader 並不會更新本地數據，因此它是不可讀的。

第二階段：Leader 將 Entry 發送到其它 Follower

Leader 與 Followers 之間保持著心跳聯系，隨心跳 Leader 將追加的 Entry（AppendEntries）並行地發送給其它的 Follower，並讓它們復制這條日誌條目，這一過程稱為復制（Replicate）。

有幾點需要注意：

1. 為什麼 Leader 向 Follower 發送的 Entry 是 AppendEntries 呢？

因為 Leader 與 Follower 的心跳是周期性的，而一個周期間 Leader 可能接收到多條客戶端的請求，因此，隨心跳向 Followers 發送的大概率是多個 Entry，即 AppendEntries。當然，在本例中，我們假設只有一條請求，自然也就是一個Entry了。

2. Leader 向 Followers 發送的不僅僅是追加的 Entry（AppendEntries）。

在發送追加日誌條目的時候，Leader 會把新的日誌條目緊接著之前條目的索引位置（prevLogIndex）， Leader 任期號（Term）也包含在其中。如果 Follower 在它的日誌中找不到包含相同索引位置和任期號的條目，那麼它就會拒絕接收新的日誌條目，因為出現這種情況說明 Follower 和 Leader 不一致。

3. 如何解決 Leader 與 Follower 不一致的問題？

在正常情況下，Leader 和 Follower 的日誌保持一致，所以追加日誌的一致性檢查從來不會失敗。然而，Leader 和 Follower 一系列崩潰的情況會使它們的日誌處於不一致狀態。Follower可能會丟失一些在新的 Leader 中有的日誌條目，它也可能擁有一些 Leader 沒有的日誌條目，或者兩者都發生。丟失或者多出日誌條目可能會持續多個任期。

要使 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，原因和解決辦法上面已做了詳細說明。

需要注意的是，此時該 Entry 的狀態也是未提交（Uncommitted）。完成上述步驟後，Followers 會向 Leader 發出 Success 的回應，當 Leader 收到大多數 Followers 的回應後，會將第一階段寫入的 Entry 標記為提交狀態（Committed），並把這條日誌條目應用到它的狀態機中。

第四階段：Leader 回應客戶端。

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

第五階段，Leader 通知 Followers Entry 已提交

Leader 回應客戶端後，將隨著下一個心跳通知 Followers，Followers 收到通知後也會將 Entry 標記為提交狀態。至此，Raft 集群超過半數節點已經達到一致狀態，可以確保強一致性。

需要注意的是，由於網路、性能、故障等各種原因導致「反應慢」、「不一致」等問題的節點，最終也會與 Leader 達成一致。

前面描述了 Raft 演算法是如何選舉 Leader 和復制日誌的。然而，到目前為止描述的機制並不能充分地保證每一個狀態機會按照相同的順序執行相同的指令。例如，一個 Follower 可能處於不可用狀態，同時 Leader 已經提交了若乾的日誌條目；然後這個 Follower 恢復（尚未與 Leader 達成一致）而 Leader 故障；如果該 Follower 被選舉為 Leader 並且覆蓋這些日誌條目，就會出現問題，即不同的狀態機執行不同的指令序列。

鑒於此，在 Leader 選舉的時候需增加一些限制來完善 Raft 演算法。這些限制可保證任何的 Leader 對於給定的任期號（Term），都擁有之前任期的所有被提交的日誌條目（所謂 Leader 的完整特性）。關於這一選舉時的限制，下文將詳細說明。

在所有基於 Leader 機制的一致性演算法中，Leader 都必須存儲所有已經提交的日誌條目。為了保障這一點，Raft 使用了一種簡單而有效的方法，以保證所有之前的任期號中已經提交的日誌條目在選舉的時候都會出現在新的 Leader 中。換言之，日誌條目的傳送是單向的，只從 Leader 傳給 Follower，並且 Leader 從不會覆蓋自身本地日誌中已經存在的條目。

Raft 使用投票的方式來阻止一個 Candidate 贏得選舉，除非這個 Candidate 包含了所有已經提交的日誌條目。Candidate 為了贏得選舉必須聯系集群中的大部分節點。這意味著每一個已經提交的日誌條目肯定存在於至少一個伺服器節點上。如果 Candidate 的日誌至少和大多數的伺服器節點一樣新（這個新的定義會在下面討論），那麼它一定持有了所有已經提交的日誌條目（多數派的思想）。投票請求的限制中請求中包含了 Candidate 的日誌信息，然後投票人會拒絕那些日誌沒有自己新的投票請求。

Raft 通過比較兩份日誌中最後一條日誌條目的索引值和任期號，確定誰的日誌比較新。如果兩份日誌最後條目的任期號不同，那麼任期號大的日誌更加新。如果兩份日誌最後的條目任期號相同，那麼日誌比較長的那個就更加新。

如同 4.1 節介紹的那樣，Leader 知道一條當前任期內的日誌記錄是可以被提交的，只要它被復制到了大多數的 Follower 上（多數派的思想）。如果一個 Leader 在提交日誌條目之前崩潰了，繼任的 Leader 會繼續嘗試復制這條日誌記錄。然而，一個 Leader 並不能斷定被保存到大多數 Follower 上的一個之前任期里的日誌條目 就一定已經提交了。這很明顯，從日誌復制的過程可以看出。

鑒於上述情況，Raft 演算法不會通過計算副本數目的方式去提交一個之前任期內的日誌條目。只有 Leader 當前任期里的日誌條目通過計算副本數目可以被提交；一旦當前任期的日誌條目以這種方式被提交，那麼由於日誌匹配特性，之前的日誌條目也都會被間接的提交。在某些情況下，Leader 可以安全地知道一個老的日誌條目是否已經被提交（只需判斷該條目是否存儲到所有節點上），但是 Raft 為了簡化問題使用了一種更加保守的方法。

當 Leader 復制之前任期里的日誌時，Raft 會為所有日誌保留原始的任期號，這在提交規則上產生了額外的復雜性。但是，這種策略更加容易辨別出日誌，即使隨著時間和日誌的變化，日誌仍維護著同一個任期編號。此外，該策略使得新 Leader 只需要發送較少日誌條目。

raft 的讀寫都在 leader 節點中進行，它保證了讀的都是最新的值，它是符合強一致性的（線性一致性），raft 除了這個還在【客戶端交互】那塊也做了一些保證，詳情可以參考論文。但是 zookeeper 不同，zookeeper 寫在 leader，讀可以在 follower 進行，可能會讀到了舊值，它不符合強一致性（只考慮寫一致性，不考慮讀一致性），但是 zookeeper 去 follower 讀可以有效提升讀取的效率。

對比於 zab、raft，我們發現他們選舉、setData 都是需要過半機制才行，所以他們針對網路分區的處理方法都是一樣的。

一個集群的節點經過網路分區後，如一共有 A、B、C、D、E 5個節點，如果 A 是 leader，網路分區為 A、B、C 和 D、E，在A、B、C分區還是能正常提供服務的，而在 D、E 分區因為不能得到大多數成員確認（雖然分區了，但是因為配置的原因他們還是能知道所有的成員數量，比如 zk 集群啟動前需要配置所有成員地址，raft 也一樣），是不能進行選舉的，所以保證只會有一個 leader。

如果分區為 A、B 和 C、D、E ，A、B 分區雖然 A 還是 leader，但是卻不能提供事務服務（setData），C、D、E 分區能重新選出 leader，還是能正常向外提供服務。

1）我們所說的日誌（log）與狀態機（state machine）不是一回事，日誌指還沒有提交到狀態機中的數據。
2）新 leader 永遠不會通過計算副本數量提交舊日誌，他只能復制舊日誌都其他 follower 上，對於舊日誌的提交，只能是新 leader 接收新的寫請求寫新日誌，順帶著把舊日誌提交了。

Ⅱ 常見分布式集群選舉機制總結

1，Zookeeper -- paxos

2，kafka -- zookeeper上創建節點

3，redis -- 哨兵模式

4，Eureka -- 相互復制

我們探討這幾個集群的選舉機制，其實就是探討它們的高可用性。如果集群中的某些節點掛了，如何保證可用性？這個問題是分布式系統面臨的三大問題之一。

Zookeeper的leader選舉機制，是這四種集群中最復雜的選舉機制，同時也是這四種集群中最接近paxos演算法的實現。相比於Zookeeper的選舉機制，kafka集群、redis集群、Eureka集群的選舉機制簡單了許多。

Zookeeper的leader選舉是Zookeeper實現數據一致性的關鍵，同時也存在一些問題。認清Zookeeper的優點與缺陷，對於我們使用好它還是很有必要的。

Zookeeper的選舉機制有2個觸發條件：集群啟動階段和集群運行階段leader掛機。這2種場景下選舉的流程基本一致，我們以集群運行階段leader掛機為例來進行說明。leader掛機以後，重新選舉leader，選舉的流程如下：

1，Zookeeper集群中的follower檢測到leader掛機，然後把自己的狀態置為LOOKING，開始進行leader選舉。

2，每台伺服器選舉自己為leader，然後把自己的選票通過廣播通知其他伺服器。

3，每台伺服器接收來自其他伺服器的選票，並進行合法性校驗，主要有兩點校驗，選舉輪次校驗和伺服器的狀態的校驗。

4，處理選票。每台伺服器都會將自己的選票與其他伺服器的選票進行PK，PK的規則如下：

第一個規則：首先進行ZXID的PK，大者獲勝。

第二條規則：如果ZXID相等，則進行myid的PK，大者獲勝。

經過PK以後，如果當前伺服器PK失敗，則會把自己的選票重新投給勝者，然後把更新後的選票通過廣播通知其他伺服器。

5，統計選票。根據超過半數的原則，每台伺服器都會統計leader的選票，如果超過半數，則結束選舉。

6，更新伺服器狀態。follower把自己的狀態更新為FOLLOWING，leader把自己的狀態更新為LEADING。

OK，這就是Zookeeper的leader選舉機制。經過若干輪選舉以後，Zookeeper集群繼續對外提供服務。由於選票PK首先比較的是ZXID，所以Zookeeper能夠保證leader的數據是最新的。

kafka集群是如何保證高可用性的呢？

kafka通過Zookeeper管理集群配置、選舉leader、consumer group發生變化時進行rebalance。

那麼我要問了，kafka是如何選舉leader的呢？

概括來說，Kafka選舉leader的過程是這樣的：kafka的所有broker，在Zookeeper的/controller路徑下創建臨時節點，成功創建的那個broker就會成為leader，其他的broker就會成為follower。

當leader掛機時，臨時節點會被刪除，這是其他節點通過Zookeeper的watch機制，會監聽到leader的變化，然後所有的follower會再次進行leader選舉。

kafka的選舉其實就是創建臨時節點，這和Zookeeper分布式鎖的實現原理基本相同。

redis主從切換和redis集群的理解。

要注意，主從切換默認只有一個master，但是對於多個master的集群，沒有主從切換的說法。

redis沒有類似Zookeeper的選舉機制。redis的master掛掉以後，redis集群是通過主從切換來保證高可用性的。

redis主從切換有2種方式：手動切換和自動切換。

這里我們討論自動切換，redis主從自動切換需要哨兵模式的支持，哨兵模式簡單來說就是：監控master和slave，在master出現故障的時候，自動將slave切換成master，master恢復以後，作為新master的slave對外提供服務。

准確的來說，Eureka集群中的各節點之間不存在主從關系。Eureka集群中的節點的關系是對等的，其他3種集群則都存在主從關系，這是Eureka集群的一個特色。

Eureka集群的各個server之間通過相互注冊的方式來實現集群的高可用性。數據同步的方式是增量備份，這樣可以保證每個server都是最新最全的數據。從而保證集群的高可用性。這樣即使某個server掛了，集群還可以對外提供服務。

Eureka有一個配置項：eureka.client.fetch-register，是否從Eureka server獲取注冊信息。如果我們是Eureka集群，那麼該項配置為true。這樣Eureka server直接就可以相互注冊。

OK，這篇文章只是對4種集群的選舉機制進行了一個概括性的介紹，具體細節還是很復雜的。之前有文章重點分析過Zookeeper的leader選舉，後續還會另起文章分析其他幾種集群的選舉機制，到時候我們再進行更深入的講解。

Ⅲ Zookeeper 理論基礎

ZooKeeper 由雅虎研究院開發，後來捐贈給了 Apache。ZooKeeper 是一個開源的分布式應用程序協調伺服器，其為分布式系統提供一致性服務。其一致性是通過基於 Paxos 演算法的ZAB 協議完成的。其主要功能包括：配置維護、域名服務、分布式同步、集群管理等。
zookeeper 的官網： http://zookeeper.apache.org

zk 是如何保證分布式系統的一致性的呢？是因為 zk 具有以下幾方面的特點：

對於zk 理論的學習，最重要也是最難的知識點就是 Paxos 演算法。所以我們首先學習 Paxos演算法。

Paxos 演算法是萊斯利·蘭伯特(Leslie Lamport)1990 年提出的一種基於消息傳遞的、具有高容錯性的一致性演算法。Google Chubby 的作者 Mike Burrows 說過，世上只有一種一致性演算法， 那就是 Paxos，所有其他一致性演算法都是 Paxos 演算法的不完整版。Paxos 演算法是一種公認的晦澀難懂的演算法，並且工程實現上也具有很大難度。較有名的 Paxos 工程實現有Google Chubby、ZAB、微信的 PhxPaxos 等。
Paxos 演算法是用於解決什麼問題的呢？Paxos 演算法要解決的問題是，在分布式系統中如何就某個決議達成一致。

拜占庭將軍問題是由 Paxos 演算法作者萊斯利·蘭伯特提出的點對點通信中的基本問題。該問題要說明的含義是，在不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的。所以，Paxos 演算法的前提是不存在拜占庭將軍問題，即信道是安全的、可靠的，集群節點間傳遞的消息是不會被篡改的。

一般情況下，分布式系統中各個節點間採用兩種通訊模型：共享內存（Shared Memory）、消息傳遞（Messages Passing）。而 Paxos 是基於消息傳遞通訊模型的。

在 Paxos 演算法中有三種角色，分別具有三種不同的行為。但很多時候，一個進程可能同時充當著多種角色。

Paxos 演算法的一致性主要體現在以下幾點：

Paxos 對於提案的提交演算法有兩種方案，2PC 與 3PC。

它們的區別主要就在於 accept 階段中是否包含 commit 功能。具體看下面的描述。

Paxos 演算法的 3PC 執行過程劃分為三個階段：准備階段 prepare、接受階段 accept，與提交階段 commit。

若提案者接收到的反饋數量超過了半數，則其會向外廣播兩類信息：

2PC 與 3PC 的區別是，在提案者接收到超過半數的表決者對於 parepare 階段的反饋後，其會向所有表決者發送真正的提案 proposal。當表決者接受到 proposal 後就直接將其同步到了本地，不用再等待 commit 消息了。

那麼，為什麼不直接使用 2PC，而要使用 3PC 呢？是因為 2PC 中存在著較多的弊端（這里就不再展開來說了）。所以很多 Paxos 工業實現使用的都是 3PC 提交。但 2PC 提交的效率要高於 3PC 提交，所以在保證不出問題的情況下，是可以使用 2PC 提交的。

前面所述的Paxos 演算法在實際工程應用過程中，根據不同的實際需求存在諸多不便之處， 所以也就出現了很多對於基本 Paxos 演算法的優化演算法，以對 Paxos 演算法進行改進，例如，Multi Paxos、Fast Paxos、EPaxos。

例如，Paxos 演算法存在「活鎖問題」，Fast Paxos 演算法對 Paxos 演算法進行了改進：只允許一個進程提交提案，即該進程具有對 N 的唯一操作權。該方式解決了「活鎖」問題。

ZAB ，Zookeeper Atomic Broadcast，zk 原子消息廣播協議，是專為 ZooKeeper 設計的一種支持崩潰恢復的原子廣播協議，在 Zookeeper 中，主要依賴 ZAB 協議來實現分布式數據一致性。

Zookeeper 使用一個單一主進程來接收並處理客戶端的所有事務請求，即寫請求。當伺服器數據的狀態發生變更後，集群採用 ZAB 原子廣播協議，以事務提案 Proposal 的形式廣播到所有的副本進程上。ZAB 協議能夠保證一個全局的變更序列，即可以為每一個事務分配一個全局的遞增編號 xid。

當 Zookeeper 客戶端連接到 Zookeeper 集群的一個節點後，若客戶端提交的是讀請求， 那麼當前節點就直接根據自己保存的數據對其進行響應；如果是寫請求且當前節點不是Leader，那麼節點就會將該寫請求轉發給 Leader，Leader 會以提案的方式廣播該寫操作，只要有超過半數節點同意該寫操作，則該寫操作請求就會被提交。然後 Leader 會再次廣播給所有訂閱者，即 Learner，通知它們同步數據。

ZAB 協議是 Paxos 演算法的一種工業實現演算法。但兩者的設計目標不太一樣。ZAB 協議主要用於構建一個高可用的分布式數據主從系統，即 Follower 是 Leader 的從機，Leader 掛了， 馬上就可以選舉出一個新的 Leader，但平時它們都對外提供服務。而 Fast Paxos 演算法則是用於構建一個分布式一致性狀態機系統，確保系統中各個節點的狀態都是一致的。

另外，ZAB 還使用 Google 的 Chubby 演算法作為分布式鎖的實現，而 Google 的 Chubby 也是 Paxos 演算法的應用。

zk 集群對於事務請求的處理是 Fast Paxos 演算法的體現，即只允許 Leader 提出提案。其屬於 3PC 提交。

但 Leader 選舉是 Paxos 演算法的體現，因為 Leader 宕機後，所有 Follower 均可提交提案， 它們在最初都是「我選我」。其屬於 2PC 提交。

為了避免 Zookeeper 的單點問題，zk 也是以集群的形式出現的。zk 集群中的角色主要有以下三類：

Learner：學習者，同步者。
Learner = Follower + Observer
QuorumPeer = Participant = Leader + Follower

在 ZAB 中有三個很重要的數據：

ZAB 協議中對zkServer 的狀態描述有三種模式。這三種模式並沒有十分明顯的界線，它們相互交織在一起。

zk 集群中的每一台主機，在不同的階段會處於不同的狀態。每一台主機具有四種狀態。

在集群啟動過程中，或 Leader 宕機後，集群就進入了恢復模式。恢復模式中最重要的階段就是 Leader 選舉。

A、serverId
這是zk 集群中伺服器的唯一標識，也稱為 sid，其實質就是 zk 中配置的 myid。例如， 有三個 zk 伺服器，那麼編號分別是 1,2,3。
B、 邏輯時鍾
邏輯時鍾，Logicalclock，是一個整型數，該概念在選舉時稱為 logicalclock，而在選舉結束後稱為epoch。即 epoch 與 logicalclock 是同一個值，在不同情況下的不同名稱。

在集群啟動過程中的 Leader 選舉過程（演算法）與 Leader 斷連後的 Leader 選舉過程稍微有一些區別，基本相同。

A、集群啟動中的 Leader 選舉

對於 Server1 而言，它的投票是(1, 0)，接收 Server2 的投票為(2, 0)。其首先會比較兩者的 ZXID，均為 0，再比較 myid，此時 Server2 的 myid 最大，於是 Server1 更新自己的投票為(2, 0)，然後重新投票。對於 Server2 而言，其無須更新自己的投票，只是再次向集群中所有主機發出上一次投票信息即可。
(4) 統計投票。每次投票後，伺服器都會統計投票信息，判斷是否已經有過半機器接受到相同的投票信息。對於 Server1、Server2 而言，都統計出集群中已經有兩台主機接受了(2, 0)的投票信息，此時便認為已經選出了新的 Leader，即 Server2。
(5) 改變伺服器狀態。一旦確定了 Leader，每個伺服器就會更新自己的狀態，如果是Follower，那麼就變更為 FOLLOWING，如果是 Leader，就變更為 LEADING。
(6) 添加主機。在新的 Leader 選舉出來後 Server3 啟動，其想發出新一輪的選舉。但由於當前集群中各個主機的狀態並不是 LOOKING，而是各司其職的正常服務，所以其只能是以Follower 的身份加入到集群中。

B、 宕機後的 Leader 選舉
在 Zookeeper 運行期間，Leader 與非 Leader 伺服器各司其職，即便當有非 Leader 伺服器宕機或新加入時也不會影響 Leader。但是若 Leader 伺服器掛了，那麼整個集群將暫停對外服務，進入新一輪的 Leader 選舉，其過程和啟動時期的 Leader 選舉過程基本一致。

前面我們說過，恢復模式具有兩個階段：Leader 選舉與初始化同步。當完成 Leader 選舉後，此時的 Leader 還是一個准 Leader，其要經過初始化同步後才能變為真正的 Leader。

具體過程如下：

當集群中的 Learner 完成了初始化狀態同步，那麼整個 zk 集群就進入到了正常工作模式了。
如果集群中的 Learner 節點收到客戶端的事務請求，那麼這些 Learner 會將請求轉發給Leader 伺服器。然後再執行如下的具體過程：

Observer 數量並不是越多越好，一般與 Follower 數量相同。因為 Observer 數量的增多雖不會增加事務操作壓力，但其需要從 Leader 同步數據，Observer 同步數據的時間是小於等於 Follower 同步數據的時間的。當 Follower 同步數據完成，Leader 的 Observer 列表中的Observer 主機將結束同步。那些完成同步的 Observer 將會進入到另一個對外提供服務的列表。那麼，那些沒有同步了數據無法提供服務的 Observer 主機就形成了資源浪費。
所以，對於事務操作發生頻繁的系統，不建議使用過多的 Observer。

Leader 中保存的 Observer 列表其實有兩個：
all：包含所有 Observer。
service：已經完成了從 Leader 同步數據的任務。service <= all。其是動態的。

Leader 中保存的 Follower 列表其實也有兩個：
all：要求其中必須有過半的 Follower 向Leader 反饋ACK
service：

當集群正在啟動過程中，或 Leader 崩潰後，集群就進入了恢復模式。對於要恢復的數據狀態需要遵循三個原則。

若集群中 Leader 收到的 Follower 心跳數量沒有過半，此時 Leader 會自認為自己與集群的連接已經出現了問題，其會主動修改自己的狀態為 LOOKING，去查找新的 Leader。
而其它 Server 由於有過半的主機認為已經丟失了 Leader，所以它們會發起新的 Leader選舉，選出一個新的 Leader。

正常情況下，當 Leader 收到超過半數 Follower 的 ACKs 後，就向各個 Follower 廣播COMMIT 消息，批准各個Server 執行該寫操作事務。當各個Server 在接收到Leader 的COMMIT 消息後就會在本地執行該寫操作，然後會向客戶端響應寫操作成功。
但是如果在非全部 Follower 收到 COMMIT 消息之前 Leader 就掛了，這將導致一種後果：部分 Server 已經執行了該事務，而部分 Server 尚未收到 COMMIT 消息，所以其並沒有執行該事務。當新的 Leader 被選舉出，集群經過恢復模式後需要保證所有 Server 上都執行了那些已經被部分 Server 執行過的事務。

當在 Leader 新事務已經通過，其已經將該事務更新到了本地，但所有 Follower 還都沒有收到 COMMIT 之前，Leader 宕機了，此時，所有 Follower 根本就不知道該 Proposal 的存在。當新的 Leader 選舉出來，整個集群進入正常服務狀態後，之前掛了的 Leader 主機重新啟動並注冊成為了 Follower。若那個別人根本不知道的 Proposal 還保留在那個主機，那麼其數據就會比其它主機多出了內容，導致整個系統狀態的不一致。所以，該 Proposa 應該被丟棄。類似這樣應該被丟棄的事務，是不能再次出現在集群中的，應該被清除。

前面我們說過，無論是寫操作投票，還是 Leader 選舉投票，都必須過半才能通過，也就是說若出現超過半數的主機宕機，則投票永遠無法通過。基於該理論，由 5 台主機構成的集群，最多隻允許 2 台宕機。而由 6 台構成的集群，其最多也只允許 2 台宕機。即，6 台與5 台的容災能力是相同的。基於此容災能力的原因，建議使用奇數台主機構成集群，以避免資源浪費。
但從系統吞吐量上說，6 台主機的性能一定是高於 5 台的。所以使用 6 台主機並不是資源浪費。

對於一個高可用的系統，除了要設置多台主機部署為一個集群避免單點問題外，還需要考慮將集群部署在多個機房、多個樓宇。對於多個機房、樓宇中集群也是不能隨意部署的， 下面就多個機房的部署進行分析。
在多機房部署設計中，要充分考慮「過半原則」，也就是說，盡量要確保 zk 集群中有過半的機器能夠正常運行。

在生產環境下，三機房部署是最常見的、容災性最好的部署方案。三機房部署中要求每個機房中的主機數量必須少於集群總數的一半。

zk 官方沒有給出較好的雙機房部署的容災方案。只能是讓其中一個機房佔有超過半數的主機，使其做為主機房，而另一機房少於半數。當然，若主機房出現問題，則整個集群會癱瘓。

CAP 定理又稱 CAP 原則，指的是在一個分布式系統中，Consistency（一致性）、Availability（可用性）、Partition tolerance（分區容錯性），三者不可兼得。

對於分布式系統，網路環境相對是不可控的，出現網路分區是不可避免的，因此系統必須具備分區容錯性。但其並不能同時保證一致性與可用性。CAP 原則對於一個分布式系統來說，只可能滿足兩項，即要麼 CP，要麼 AP。

BASE 是Basically Available（基本可用）、Soft state（軟狀態）和 Eventually consistent（最終一致性）三個短語的簡寫。

BASE 理論的核心思想是：即使無法做到實時一致性，但每個系統都可以根據自身的業務特點，採用適當的方式來使系統達到最終一致性。

基本可用是指分布式系統在出現不可預知故障的時候，允許損失部分可用性。
損失響應時間：
損失功能：

軟狀態，是指允許系統數據存在的中間狀態，並認為該中間狀態的存在不會影響系統的整體可用性，即允許系統主機間進行數據同步的過程存在一定延時。軟狀態，其實就是一種灰度狀態，過渡狀態。

最終一致性強調的是系統中所有的數據副本，在經過一段時間的同步後，最終能夠達到一個一致的狀態。因此，最終一致性的本質是需要系統保證最終數據能夠達到一致，而不需要實時保證系統數據的一致性。

從達到一致性的時間角度來劃分，可以分為：

單從客戶端訪問到的內容角度來劃分，可以分為：

zk 遵循的是 CP 原則，即保證了一致性，但犧牲了可用性。體現在哪裡呢？

當 Leader 宕機後，zk 集群會馬上進行新的 Leader 的選舉。但選舉時長一般在 200 毫秒內，最長不超過 60 秒，整個選舉期間 zk 集群是不接受客戶端的讀寫操作的，即 zk 集群是處於癱瘓狀態的。所以，其不滿足可用性。

這里說的zk可能會引發腦裂，是指的在多機房部署中，若出現了網路連接問題，形成多個分區，則可能會出現腦裂問題，可能會導致數據不一致。
（1）情況一

（2）情況二

（5）情況五

Ⅳ Zookpeer是什麼在系統中如何起作用

Zookeeper分布式服務框架是Apache Hadoop的一個子項目，它主要是用來解決分布式應用中經常遇到的一些數據管理問題。如：統一命名服務、狀態同步服務、集群管理、分布式應用配置項的管理等。

我們先看看它都提供了哪些功能，然後再看看使用它的這些功能能做點什麼。

簡單的說，zookeeper=文件系統+通知機制。

Zookeeper維護一個類似文件系統的數據結構：

每個子目錄項如 NameService 都被稱作為 znode，和文件系統一樣，我們能夠自由的增加、刪除znode，在一個znode下增加、刪除子znode，唯一的不同在於znode是可以存儲數據的。

客戶端注冊監聽它關心的目錄節點，當目錄節點發生變化（數據改變、被刪除、子目錄節點增加刪除）時，zookeeper會通知客戶端。

這個似乎最簡單，在zookeeper的文件系統里創建一個目錄，即有唯一的path。在我們使用tborg無法確定上遊程序的部署機器時即可與下遊程序約定好path，通過path即能互相探索發現，不見不散了。

程序總是需要配置的，如果程序分散部署在多台機器上，要逐個改變配置就變得困難。
可以把這些配置全部放到zookeeper上去，保存在 Zookeeper 的某個目錄節點中，然後所有相關應用程序對這個目錄節點進行監聽，一旦配置信息發生變化，每個應用程序就會收到 Zookeeper 的通知，然後從 Zookeeper 獲取新的配置信息應用到系統中就好。

集群管理無在乎兩點：是否有機器退出和加入、選舉master。

對於第一點，所有機器約定在父目錄GroupMembers下創建臨時目錄節點，然後監聽父目錄節點的子節點變化消息。一旦有機器掛掉，該機器與 zookeeper的連接斷開，其所創建的臨時目錄節點被刪除，所有其他機器都收到通知：某個兄弟目錄被刪除，於是，所有人都知道：它下船了。當然又會有新機器加入，也是類似：所有機器收到通知---新兄弟目錄加入，highcount又有了，有人上船了。

對於第二點，我們假設機器創建臨時順序編號目錄節點，每次選取編號最小的機器作為master就好。

有了zookeeper的一致性文件系統，鎖的問題變得容易。鎖服務可以分為兩類，一個是保持獨占，另一個是控制時序。

對於第一類，我們將zookeeper上的一個znode看作是一把鎖，通過createznode的方式來實現。所有客戶端都去創建 /distribute_lock 節點，最終成功創建的那個客戶端也即擁有了這把鎖。廁所有言：來也沖沖，去也沖沖，用完刪除掉自己創建的distribute_lock 節點就釋放出鎖。

對於第二類， /distribute_lock 已經預先存在，所有客戶端在它下面創建臨時順序編號目錄節點，和選master一樣，編號最小的獲得鎖，用完刪除，依次方便。

兩種類型的隊列：

1、 同步隊列，當一個隊列的成員都聚齊時，這個隊列才可用，否則一直等待所有成員到達。

2、隊列按照 FIFO 方式進行入隊和出隊操作。

第一類，在約定目錄下創建臨時目錄節點，監聽節點數目是否是我們要求的數目。

第二類，和分布式鎖服務中的控制時序場景基本原理一致，入列有編號，出列按編號。

Zookeeper中的角色主要有以下三類：

系統模型如圖所示：

Zookeeper的核心是原子廣播，這個機制保證了各個Server之間的同步。實現這個機制的協議叫做Zab協議。Zab協議有兩種模式，它們分 別是恢復模式（選主）和廣播模式（同步）。當服務啟動或者在領導者崩潰後，Zab就進入了恢復模式，當領導者被選舉出來，且大多數Server完成了和 leader的狀態同步以後，恢復模式就結束了。狀態同步保證了leader和Server具有相同的系統狀態。

為了保證事務的順序一致性，zookeeper採用了遞增的事務id號（zxid）來標識事務。所有的提議（proposal）都在被提出的時候加上 了zxid。實現中zxid是一個64位的數字，它高32位是epoch用來標識leader關系是否改變，每次一個leader被選出來，它都會有一個 新的epoch，標識當前屬於那個leader的統治時期。低32位用於遞增計數。

每個Server在工作過程中有三種狀態：

當leader崩潰或者leader失去大多數的follower，這時候zk進入恢復模式，恢復模式需要重新選舉出一個新的leader，讓所有的 Server都恢復到一個正確的狀態。Zk的選舉演算法有兩種：一種是基於basic paxos實現的，另外一種是基於fast paxos演算法實現的。系統默認的選舉演算法為fast paxos。先介紹basic paxos流程：

通過流程分析我們可以得出：要使Leader獲得多數Server的支持，則Server總數必須是奇數2n+1，且存活的Server的數目不得少於n+1.

選完leader以後，zk就進入狀態同步過程。

Leader主要有三個功能：

PING消息是指Learner的心跳信息；REQUEST消息是Follower發送的提議信息，包括寫請求及同步請求；ACK消息是 Follower的對提議的回復，超過半數的Follower通過，則commit該提議；REVALIDATE消息是用來延長SESSION有效時間。
Leader的工作流程簡圖如下所示，在實際實現中，流程要比下圖復雜得多，啟動了三個線程來實現功能。

Follower主要有四個功能：

Follower的消息循環處理如下幾種來自Leader的消息：

Follower的工作流程簡圖如下所示，在實際實現中，Follower是通過5個線程來實現功能的。

https://blog.csdn.net/xinguan1267/article/details/38422149
https://blog.csdn.net/gs80140/article/details/51496925
https://www.2cto.com/kf/201708/668587.html
https://blog.csdn.net/milhua/article/details/78931672

P.S. 這篇文章是本人對網路上關於ZK的文章閱讀之後整理所得，作為入門級的了解。個人覺得看了上面的內容就能基本了解Zookeeper的作用了，後面在結合實際項目使用加深自己的了解。

end