溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“Zookeeper中Paxos算法的介紹”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Zookeeper中Paxos算法的介紹”吧!
Paxos 算法是萊斯利·蘭伯特(Leslie Lamport)1990 年提出的一種基于消息傳遞的、具有高 容錯性的一致性算法。Google Chubby 的作者 Mike Burrows 說過，世上只有一種一致性算法， 那就是 Paxos，所有其他一致性算法都是 Paxos 算法的不完整版。Paxos 算法是一種公認的晦 澀難懂的算法，并且工程實現上也具有很大難度。較有名的 Paxos 工程實現有 Google Chubby、 ZAB、微信的 PhxPaxos 等
Paxos 算法是用于解決什么問題的呢? Paxos 算法要解決的問題是，在分布式系統中如何 就某個決議達成一致。
拜占庭將軍問題是由 Paxos 算法作者萊斯利·蘭伯特提出的點對點通信中的基本問題。該 問題要說明的含義是，<font color='red'>在不可靠信道上試圖通過消息傳遞的方式達到一致性是不可能的</font>。所 以，Paxos 算法的前提是<font color='red'>不存在拜占庭將軍問題</font>，即信道是安全的、可靠的，集群節點間傳 遞的消息是不會被篡改的。
一般情況下，分布式系統中各個節點間采用兩種通訊模型:共享內存(Shared Memory)、消息傳遞(Messages Passing)。而 Paxos 是基于消息傳遞通訊模型的。
在 Paxos 算法中有三種角色，分別具有三種不同的行為。但很多時候，一個進程可能同 時充當著多種角色。
Proposer:提案者，提出提案（Proposal）；
Acceptor:表決者；
Learner:學習者(同步者，即Proposer決議形成，將所有形成的決議發送給Learners)
Paxos 算法的一致性主要體現在以下幾點:
每個提案者在提出提案時都會首先獲取到一個具有全局唯一性的、遞增的提案編號N，即在整個集群中是唯一的編號 N，然后將該編號賦予其要提出的提案。
每個表決者在accept某提案后，會將該提案的編號N記錄在本地，這樣每個表決者中保存的已經被 accept 的提案中會存在一個編號最大的提案，其編號假設為 maxN。每個表決者僅會 accept 編號大于自己本地 maxN 的提案。
在眾多提案中最終只能有一個提案被選定。
一旦一個提案被選定，則其它服務器會主動同步(Learn)該提案到本地。
沒有提案被提出則不會有提案被選定。
Paxos 算法的執行過程劃分為兩個階段:準備階段 prepare 與接受階段 accept。Ps:Learn階段之前決議已經形成。
由于Paxos算法是晦澀難懂的，這里我將以自己的理解來做整個描述，雖然可能在嚴謹性上會差強人意，但是可讀性會提高，希望可以給大家更輕松的閱讀體驗。
提案者(Proposer)準備提交一個編號為 N 的提議，于是其首先向所有表決者(Acceptor)發 送 prepare(N)請求，用于試探集群是否支持該編號的提議。 如果這里不好理解我們可以試圖理解為提議者拿著鈔票去賄賂“表決者（Accept）”
每個表決者（Acceptor）都保存者當前賄賂自己的最大金額數，即（maxN），當每個表決者接收到賄賂自己的提議時，會比較賄賂金額與maxN的值。有以下幾種情況：
若 N 小于 maxN，則說明該提議已過時（錢少不接受），當前表決者采取不回應或回應 Error 的方 式來拒絕該 prepare 請求；
若 N 大于 maxN，則說明該提議是可以接受的（畢竟誰給的錢多聽誰的），當前表決者會首先將該 N（當前賄賂金額） 記錄下來， 并將其曾經已經 accept 的編號最大的提案 Proposal(myid,maxN,value)反饋給提案者， 以向提案者展示自己支持的提案意愿。其中第一個參數 myid 表示表決者 Acceptor 的標識 id，第二個參數表示其曾接受的提案的最大編號 maxN（前任領導賄賂的金額），第三個參數表示該 提案的真正內容 value（前任領導提議的內容）。當然，若當前表決者還未曾 accept 過任何提議，則會將 Proposal(myid,null,null)反饋給提案者。
在 prepare 階段 N 不可能等于 maxN。這是由 N 的生成機制決定的。要獲得 N 的值， 其必定會在原來數值的基礎上采用同步鎖方式增一。
這里需要說明下，為什么在表決者（Acceptor）判斷賄賂金額大于當前保存的最大金額時會將前任已經保存的金額和提案內容返回給提案者，這是因為提案者（Proposer），在收到表決者的答復后，需要判斷誰是最有錢的提案者，便推舉它為領袖 (修改自己的提案)。
當提案者(Proposer)發出 prepare(N)后，若收到了超過半數的表決者(Accepter)的反饋， 那么該提案者就會將其真正的提案 Proposal(myid,N,value)發送給所有的表決者。
當表決者(Acceptor)接收到提案者發送的 Proposal(myid,N,value)提案后，會再次拿出自己 曾經 accept 過的提議中的最大編號 maxN，或曾經記錄下的 prepare 的最大編號，讓 N 與它們進行比較，若 N 大于等于這兩個編號，則當前表決者 accept 該提案，并反饋給 提案者。若 N 小于這兩個編號，則表決者采取不回應或回應 Error 的方式來拒絕該提議。
若提案者沒有接收到超過半數的表決者的 accept 反饋（中間有別人以更多的金額賄賂了它），則有兩種可能的結果產生。一 是放棄該提案，不再提出；二是重新進入 prepare 階段，遞增提案號，重新提出 prepare 請求。
若提案者接收到的反饋數量超過了半數，則其會向外廣播兩類信息：
向曾 accept 其提案的表決者發送“可執行數據同步信號”，即讓它們執行其曾接收到的提案；
向未曾向其發送 accept 反饋的表決者發送“提案 + 可執行數據同步信號”，即讓 它們接受到該提案后馬上執行。
上述的過程中，如果某一個提議收到了大多數的表決者（Acceptor）的響應后（提案者（Proposal）中的N必須大于當前maxN才會響應），則提案通過，向所有表決者以及leaner發送同步數據，達成數據一致性。
當然上面只是簡單的描述，真是的算法場景更復雜，所有提議者，決策者身份信息都是交叉的，如果提議者、接受者的數量是4個,5個。。。但是你按照上面的思路進行推演，最終會發現最終是唯一一個提議獲取多數票而勝出，從而其他提議者和決策者同步此提議。
上面的流程可能會引發活鎖問題，那么什么是活鎖呢？
活鎖指的是任務或者執行者沒有被阻塞，由于某些條件沒有滿足，導致一直重復嘗試—失敗—嘗試—失敗的過程。處于活鎖的實體是在不斷的改變狀態，活鎖有可能自行解開。
那么上面的行為是怎么會引發活鎖呢？接下來我們一起來分析下：
在整個選舉過程中，每個人誰先來誰后到，“接受者”什么時間能夠接到“提議者”的信息，是完全不可控的；
假設，第一個提案者A（Proposal）已經成功過了prepare階段，準備向Acceptors廣播發送Accept時，有一個更有錢土豪提案者B也向決議者（Acceptors）廣播了prepare請求并在A的accept請求到之前發送給了決議者，這時毫無疑問，決議者會接收該請求，并記錄在冊。這時候，A的accept請求姍姍來遲，決議者對比此proposal的賄賂金額已經小于當前記錄的prepare最大編號，因此不響應給提議者A，則提議者A收到的響應為過半，此提案廢棄。這時它又用大于Proposer A的賄賂金額重新發起 preapre廣播請求，這時提議者B的accept請求還沒有到達決議者（Acceptors），因此Acceptor也接受了該prepare請求，將其記錄在案，在之后提議者B發出的accept請求到達，決議者發現賄賂金額已經小于當前prepare的最大賄賂金額，因此拒絕響應，這樣就會形成活鎖問題。
本篇文章故事講到這里就基本上結束了，下面我們來總結一下，其實Paxos算法主要包括兩個階段：
prepare階段，這個階段主要是準備一個編號為N的提案，首先向所有決議者（Acceptor）發送prepare請求，用于試探是否支持該編號的提議。
accept階段，當一階段提議收到了超過半數的響應，則開始正式下發提案內容proposal，如果過半則提案提交成功，廣播給所有learner。
到此，相信大家對“Zookeeper中Paxos算法的介紹”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
