1?Paxos算法

1.1?基本定義

算法中的參與者主要分為三個角色，同時每個參與者又可兼領多個角色:

⑴proposer?提出提案，提案信息包括提案編號和提議的value;

⑵acceptor?收到提案后可以接受(accept)提案;

⑶learner?只能"學習"被批準的提案;

算法保重一致性的基本語義:

⑴決議(value)只有在被proposers提出后才能被批準(未經批準的決議稱為"提案(proposal)");

⑵在一次Paxos算法的執行實例中，只批準(chosen)一個value;

⑶learners只能獲得被批準(chosen)的value;

有上面的三個語義可演化為四個約束:

⑴P1:一個acceptor必須接受(accept)第一次收到的提案;

⑵P2a:一旦一個具有value?v的提案被批準(chosen)，那么之后任何acceptor?再次接受(accept)的提案必須具有value?v;

⑶P2b:一旦一個具有value?v的提案被批準(chosen)，那么以后任何?proposer?提出的提案必須具有value?v;

⑷P2c:如果一個編號為n的提案具有value?v，那么存在一個多數派，要么他們中所有人都沒有接受(accept)編號小于n的任何提案，要么他們已經接受(accpet)的所有編號小于n的提案中編號最大的那個提案具有value?v;

1.2?基本算法(basic?paxos)

算法(決議的提出與批準)主要分為兩個階段:

1.?prepare階段：?

(1).?當Porposer希望提出方案V1，首先發出prepare請求至大多數Acceptor。Prepare請求內容為序列號<SN1>;

(2).?當Acceptor接收到prepare請求<SN1>時，檢查自身上次回復過的prepare請求<SN2>

a).?如果SN2>SN1，則忽略此請求，直接結束本次批準過程;

b).?否則檢查上次批準的accept請求<SNx，Vx>，并且回復<SNx，Vx>；如果之前沒有進行過批準，則簡單回復<OK>;

2.?accept批準階段：?

(1a).?經過一段時間，收到一些Acceptor回復，回復可分為以下幾種:

a).?回復數量滿足多數派，并且所有的回復都是<OK>，則Porposer發出accept請求，請求內容為議案<SN1，V1>;

b).?回復數量滿足多數派，但有的回復為：<SN2，V2>，<SN3，V3>……則Porposer找到所有回復中超過半數的那個，假設為<SNx，Vx>，則發出accept請求，請求內容為議案<SN1，Vx>;

c).?回復數量不滿足多數派，Proposer嘗試增加序列號為SN1+，轉1繼續執行;

?????????(1b).?經過一段時間，收到一些Acceptor回復，回復可分為以下幾種:

a).?回復數量滿足多數派，則確認V1被接受;

b).?回復數量不滿足多數派，V1未被接受，Proposer增加序列號為SN1+，轉1繼續執行;

(2).?在不違背自己向其他proposer的承諾的前提下，acceptor收到accept?請求后即接受并回復這個請求。

1.3?算法優化(fast?paxos)

Paxos算法在出現競爭的情況下，其收斂速度很慢，甚至可能出現活鎖的情況，例如當有三個及三個以上的proposer在發送prepare請求后，很難有一個proposer收到半數以上的回復而不斷地執行第一階段的協議。因此，為了避免競爭，加快收斂的速度，在算法中引入了一個Leader這個角色，在正常情況下同時應該最多只能有一個參與者扮演Leader角色，而其它的參與者則扮演Acceptor的角色，同時所有的人又都扮演Learner的角色。

在這種優化算法中，只有Leader可以提出議案，從而避免了競爭使得算法能夠快速地收斂而趨于一致，此時的paxos算法在本質上就退變為兩階段提交協議。但在異常情況下，系統可能會出現多Leader的情況，但這并不會破壞算法對一致性的保證，此時多個Leader都可以提出自己的提案，優化的算法就退化成了原始的paxos算法。

一個Leader的工作流程主要有分為三個階段：

(1).學習階段?向其它的參與者學習自己不知道的數據(決議);

(2).同步階段?讓絕大多數參與者保持數據(決議)的一致性;

(3).服務階段?為客戶端服務，提議案;

1.3.1?學習階段

當一個參與者成為了Leader之后，它應該需要知道絕大多數的paxos實例，因此就會馬上啟動一個主動學習的過程。假設當前的新Leader早就知道了1-134、138和139的paxos實例，那么它會執行135-137和大于139的paxos實例的第一階段。如果只檢測到135和140的paxos實例有確定的值，那它最后就會知道1-135以及138-140的paxos實例。

1.3.2?同步階段

此時的Leader已經知道了1-135、138-140的paxos實例，那么它就會重新執行1-135的paxos實例，以保證絕大多數參與者在1-135的paxos實例上是保持一致的。至于139-140的paxos實例，它并不馬上執行138-140的paxos實例，而是等到在服務階段填充了136、137的paxos實例之后再執行。這里之所以要填充間隔，是為了避免以后的Leader總是要學習這些間隔中的paxos實例，而這些paxos實例又沒有對應的確定值。

1.3.4?服務階段

Leader將用戶的請求轉化為對應的paxos實例，當然，它可以并發的執行多個paxos實例，當這個Leader出現異常之后，就很有可能造成paxos實例出現間斷。

1.3.5?問題

(1).Leader的選舉原則

(2).Acceptor如何感知當前Leader的失敗，客戶如何知道當前的Leader

(3).當出現多Leader之后，如何kill掉多余的Leader

(4).如何動態的擴展Acceptor

2.?Zookeeper

2.1?整體架構

在Zookeeper集群中，主要分為三者角色，而每一個節點同時只能扮演一種角色，這三種角色分別是：

(1).?Leader?接受所有Follower的提案請求并統一協調發起提案的投票，負責與所有的Follower進行內部的數據交換(同步);

(2).?Follower?直接為客戶端服務并參與提案的投票，同時與Leader進行數據交換(同步);

(3).?Observer?直接為客戶端服務但并不參與提案的投票，同時也與Leader進行數據交換(同步);

2.2?QuorumPeer的基本設計

Zookeeper對于每個節點QuorumPeer的設計相當的靈活，QuorumPeer主要包括四個組件：客戶端請求接收器(ServerCnxnFactory)、數據引擎(ZKDatabase)、選舉器(Election)、核心功能組件(Leader/Follower/Observer)。其中：

(1).?ServerCnxnFactory負責維護與客戶端的連接(接收客戶端的請求并發送相應的響應);

(2).?ZKDatabase負責存儲/加載/查找數據(基于目錄樹結構的KV+操作日志+客戶端Session);

(3).?Election負責選舉集群的一個Leader節點;

(4).?Leader/Follower/Observer一個QuorumPeer節點應該完成的核心職責;

2.3?QuorumPeer工作流程

2.3.1?Leader職責

Follower確認:?等待所有的Follower連接注冊，若在規定的時間內收到合法的Follower注冊數量，則確認成功；否則，確認失敗。

2.3.2?Follower職責

2.4?選舉算法

2.4.1?LeaderElection選舉算法

選舉線程由當前Server發起選舉的線程擔任，他主要的功能對投票結果進行統計，并選出推薦的Server。選舉線程首先向所有Server發起一次詢問(包括自己)，被詢問方，根據自己當前的狀態作相應的回復，選舉線程收到回復后，驗證是否是自己發起的詢問(驗證xid?是否一致)，然后獲取對方的id(myid)，并存儲到當前詢問對象列表中，最后獲取對方提議?的

leader?相關信息(id,zxid)，并將這些?信息存儲到當次選舉的投票記錄表中，當向所有Serve?r

都詢問完以后，對統計結果進行篩選并進行統計，計算出當次詢問后獲勝的是哪一個Server，并將當前zxid最大的Server?設置為當前Server要推薦的Server(有可能是自己，也有可以是其它的Server，根據投票結果而定，但是每一個Server在第一次投票時都會投自己)，如果此時獲勝的Server獲得n/2?+?1的Server票數，設置當前推薦的leader為獲勝的Server。根據獲勝的Server相關信息設置自己的狀態。每一個Server都重復以上流程直到選舉出Leader。

初始化選票(第一張選票):?每個quorum節點一開始都投給自己;

收集選票:?使用UDP協議盡量收集所有quorum節點當前的選票(單線程/同步方式)，超時設置200ms;

統計選票:?1).每個quorum節點的票數;

?????????2).為自己產生一張新選票(zxid、myid均最大);

選舉成功:?某一個quorum節點的票數超過半數;

更新選票:?在本輪選舉失敗的情況下，當前quorum節點會從收集的選票中選取合適的選票(zxid、myid均最大)作為自己下一輪選舉的投票;

異常問題的處理

1).?選舉過程中，Server的加入

當一個Server啟動時它都會發起一次選舉，此時由選舉線程發起相關流程，那么每個?Serve?r都會獲得當前zxi?d最大的哪個Serve?r是誰，如果當次最大的Serve?r沒有獲得n/2+1?個票數，那么下一次投票時，他將向zxid最大的Server投票，重復以上流程，最后一定能選舉出一個Leader。

2).?選舉過程中，Server的退出

只要保證n/2+1個Server存活就沒有任何問題，如果少于n/2+1個Server?存活就沒辦法選出Leader。

3).?選舉過程中，Leader死亡

當選舉出Leader以后，此時每個Server應該是什么狀態(FLLOWING)都已經確定，此時由于Leader已經死亡我們就不管它，其它的Fllower按正常的流程繼續下去，當完成這個流程以后，所有的Fllower都會向Leader發送Ping消息，如果無法ping通，就改變自己的狀為(FLLOWING?==>?LOOKING)，發起新的一輪選舉。

4).?選舉完成以后，Leader死亡

處理過程同上。

5).?雙主問題

Leader的選舉是保證只產生一個公認的Leader的，而且Follower重新選舉與舊Leader恢復并退出基本上是同時發生的，當Follower無法ping同Leader是就認為Leader已經出問題開始重新選舉，Leader收到Follower的ping沒有達到半數以上則要退出Leader重新選舉。

2.4.2?FastLeaderElection選舉算法

FastLeaderElection是標準的fast?paxos的實現，它首先向所有Server提議自己要成為leader，當其它Server收到提議以后，解決?epoch?和?zxid?的沖突，并接受對方的提議，然后向對方發送接受提議完成的消息。

FastLeaderElection算法通過異步的通信方式來收集其它節點的選票，同時在分析選票時又根據投票者的當前狀態來作不同的處理，以加快Leader的選舉進程。

每個Server都一個接收線程池和一個發送線程池,?在沒有發起選舉時，這兩個線程池處于阻塞狀態，直到有消息到來時才解除阻塞并處理消息，同時每個Serve?r都有一個選舉線程(可以發起選舉的線程擔任)。

1).?主動發起選舉端(選舉線程)的處理

首先自己的?logicalclock加1，然后生成notification消息，并將消息放入發送隊列中，?系統中配置有幾個Server就生成幾條消息，保證每個Server都能收到此消息，如果當前Server?的狀態是LOOKING就一直循環檢查接收隊列是否有消息，如果有消息，根據消息中對方的狀態進行相應的處理。

2).主動發送消息端(發送線程池)的處理

將要發送的消息由Notification消息轉換成ToSend消息，然后發送對方，并等待對方的回復。

3).?被動接收消息端(接收線程池)的處理

將收到的消息轉換成Notification消息放入接收隊列中，如果對方Server的epoch小于logicalclock則向其發送一個消息(讓其更新epoch)；如果對方Server處于Looking狀態，自己則處于Following或Leading狀態，則也發送一個消息(當前Leader已產生，讓其盡快收斂)。

2.4.3?AuthFastLeaderElection選舉算法

AuthFastLeaderElection算法同FastLeaderElection算法基本一致，只是在消息中加入了認證信息，該算法在最新的Zookeeper中也建議棄用。

2.5?Zookeeper的API

名稱	同步	異步	watch	權限認證
create	√	√		√
delete	√	√		√
exist	√	√	√
getData	√	√	√	√
setData	√	√		√
getACL	√	√
setACL	√	√		√
getChildren	√	√	√	√
sync		√
multi	√			√
createSession	√
closeSession	√

2.6?Zookeeper中的請求處理流程

2.6.1?Follower節點處理用戶的讀寫請求

2.6.2?Leader節點處理寫請求

??? 值得注意的是， Follower/Leader上的讀操作時并行的，讀寫操作是串行的，當CommitRequestProcessor處理一個寫請求時，會阻塞之后所有的讀寫請求。

通信不可靠:?消息延遲、消息重復傳遞、消息丟失

總結

以上是生活随笔為你收集整理的Paxos算法与Zookeeper分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。