Zookeeper中Paxos算法的介紹

本篇內(nèi)容主要講解“Zookeeper中Paxos算法的介紹”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Zookeeper中Paxos算法的介紹”吧!

算法簡(jiǎn)介

Paxos 算法是萊斯利·蘭伯特(Leslie Lamport)1990 年提出的一種基于消息傳遞的、具有高 容錯(cuò)性的一致性算法。Google Chubby 的作者 Mike Burrows 說(shuō)過(guò)，世上只有一種一致性算法， 那就是 Paxos，所有其他一致性算法都是 Paxos 算法的不完整版。Paxos 算法是一種公認(rèn)的晦 澀難懂的算法，并且工程實(shí)現(xiàn)上也具有很大難度。較有名的 Paxos 工程實(shí)現(xiàn)有 Google Chubby、 ZAB、微信的 PhxPaxos 等

Paxos 算法是用于解決什么問(wèn)題的呢? Paxos 算法要解決的問(wèn)題是，在分布式系統(tǒng)中如何 就某個(gè)決議達(dá)成一致。

Paxos與拜占庭將軍問(wèn)題

拜占庭將軍問(wèn)題是由 Paxos 算法作者萊斯利·蘭伯特提出的點(diǎn)對(duì)點(diǎn)通信中的基本問(wèn)題。該 問(wèn)題要說(shuō)明的含義是，<font color='red'>在不可靠信道上試圖通過(guò)消息傳遞的方式達(dá)到一致性是不可能的</font>。所 以，Paxos 算法的前提是<font color='red'>不存在拜占庭將軍問(wèn)題</font>，即信道是安全的、可靠的，集群節(jié)點(diǎn)間傳 遞的消息是不會(huì)被篡改的。

一般情況下，分布式系統(tǒng)中各個(gè)節(jié)點(diǎn)間采用兩種通訊模型:共享內(nèi)存(Shared Memory)、消息傳遞(Messages Passing)。而 Paxos 是基于消息傳遞通訊模型的。

算法描述

三種角色

在 Paxos 算法中有三種角色，分別具有三種不同的行為。但很多時(shí)候，一個(gè)進(jìn)程可能同 時(shí)充當(dāng)著多種角色。

• Proposer:提案者，提出提案（Proposal）；

• Acceptor:表決者；

• Learner:學(xué)習(xí)者(同步者，即Proposer決議形成，將所有形成的決議發(fā)送給Learners)

Paxos算法一致性

Paxos 算法的一致性主要體現(xiàn)在以下幾點(diǎn):

• 每個(gè)提案者在提出提案時(shí)都會(huì)首先獲取到一個(gè)具有全局唯一性的、遞增的提案編號(hào)N，即在整個(gè)集群中是唯一的編號(hào) N，然后將該編號(hào)賦予其要提出的提案。

• 每個(gè)表決者在accept某提案后，會(huì)將該提案的編號(hào)N記錄在本地，這樣每個(gè)表決者中保存的已經(jīng)被 accept 的提案中會(huì)存在一個(gè)編號(hào)最大的提案，其編號(hào)假設(shè)為 maxN。每個(gè)表決者僅會(huì) accept 編號(hào)大于自己本地 maxN 的提案。

• 在眾多提案中最終只能有一個(gè)提案被選定。

• 一旦一個(gè)提案被選定，則其它服務(wù)器會(huì)主動(dòng)同步(Learn)該提案到本地。

• 沒(méi)有提案被提出則不會(huì)有提案被選定。

Paxos算法流程

Paxos 算法的執(zhí)行過(guò)程劃分為兩個(gè)階段:準(zhǔn)備階段 prepare 與接受階段 accept。Ps:Learn階段之前決議已經(jīng)形成。

由于Paxos算法是晦澀難懂的，這里我將以自己的理解來(lái)做整個(gè)描述，雖然可能在嚴(yán)謹(jǐn)性上會(huì)差強(qiáng)人意，但是可讀性會(huì)提高，希望可以給大家更輕松的閱讀體驗(yàn)。

A、Prepare階段

1. 提案者(Proposer)準(zhǔn)備提交一個(gè)編號(hào)為 N 的提議，于是其首先向所有表決者(Acceptor)發(fā) 送 prepare(N)請(qǐng)求，用于試探集群是否支持該編號(hào)的提議。 如果這里不好理解我們可以試圖理解為提議者拿著鈔票去賄賂“表決者（Accept）”

2. 每個(gè)表決者（Acceptor）都保存者當(dāng)前賄賂自己的最大金額數(shù)，即（maxN），當(dāng)每個(gè)表決者接收到賄賂自己的提議時(shí)，會(huì)比較賄賂金額與maxN的值。有以下幾種情況：

1. 若 N 小于 maxN，則說(shuō)明該提議已過(guò)時(shí)（錢(qián)少不接受），當(dāng)前表決者采取不回應(yīng)或回應(yīng) Error 的方 式來(lái)拒絕該 prepare 請(qǐng)求；

2. 若 N 大于 maxN，則說(shuō)明該提議是可以接受的（畢竟誰(shuí)給的錢(qián)多聽(tīng)誰(shuí)的），當(dāng)前表決者會(huì)首先將該 N（當(dāng)前賄賂金額） 記錄下來(lái)， 并將其曾經(jīng)已經(jīng) accept 的編號(hào)最大的提案 Proposal(myid,maxN,value)反饋給提案者， 以向提案者展示自己支持的提案意愿。其中第一個(gè)參數(shù) myid 表示表決者 Acceptor 的標(biāo)識(shí) id，第二個(gè)參數(shù)表示其曾接受的提案的最大編號(hào) maxN（前任領(lǐng)導(dǎo)賄賂的金額），第三個(gè)參數(shù)表示該 提案的真正內(nèi)容 value（前任領(lǐng)導(dǎo)提議的內(nèi)容）。當(dāng)然，若當(dāng)前表決者還未曾 accept 過(guò)任何提議，則會(huì)將 Proposal(myid,null,null)反饋給提案者。

3. 在 prepare 階段 N 不可能等于 maxN。這是由 N 的生成機(jī)制決定的。要獲得 N 的值， 其必定會(huì)在原來(lái)數(shù)值的基礎(chǔ)上采用同步鎖方式增一。

這里需要說(shuō)明下，為什么在表決者（Acceptor）判斷賄賂金額大于當(dāng)前保存的最大金額時(shí)會(huì)將前任已經(jīng)保存的金額和提案內(nèi)容返回給提案者，這是因?yàn)樘岚刚撸≒roposer），在收到表決者的答復(fù)后，需要判斷誰(shuí)是最有錢(qián)的提案者，便推舉它為領(lǐng)袖 (修改自己的提案)。

B、Accept階段

1. 當(dāng)提案者(Proposer)發(fā)出 prepare(N)后，若收到了超過(guò)半數(shù)的表決者(Accepter)的反饋， 那么該提案者就會(huì)將其真正的提案 Proposal(myid,N,value)發(fā)送給所有的表決者。

2. 當(dāng)表決者(Acceptor)接收到提案者發(fā)送的 Proposal(myid,N,value)提案后，會(huì)再次拿出自己 曾經(jīng) accept 過(guò)的提議中的最大編號(hào) maxN，或曾經(jīng)記錄下的 prepare 的最大編號(hào)，讓 N 與它們進(jìn)行比較，若 N 大于等于這兩個(gè)編號(hào)，則當(dāng)前表決者 accept 該提案，并反饋給 提案者。若 N 小于這兩個(gè)編號(hào)，則表決者采取不回應(yīng)或回應(yīng) Error 的方式來(lái)拒絕該提議。

3. 若提案者沒(méi)有接收到超過(guò)半數(shù)的表決者的 accept 反饋（中間有別人以更多的金額賄賂了它），則有兩種可能的結(jié)果產(chǎn)生。一 是放棄該提案，不再提出；二是重新進(jìn)入 prepare 階段，遞增提案號(hào)，重新提出 prepare 請(qǐng)求。

4. 若提案者接收到的反饋數(shù)量超過(guò)了半數(shù)，則其會(huì)向外廣播兩類信息：

1. 向曾 accept 其提案的表決者發(fā)送“可執(zhí)行數(shù)據(jù)同步信號(hào)”，即讓它們執(zhí)行其曾接收到的提案；

2. 向未曾向其發(fā)送 accept 反饋的表決者發(fā)送“提案 + 可執(zhí)行數(shù)據(jù)同步信號(hào)”，即讓 它們接受到該提案后馬上執(zhí)行。

上述的過(guò)程中，如果某一個(gè)提議收到了大多數(shù)的表決者（Acceptor）的響應(yīng)后（提案者（Proposal）中的N必須大于當(dāng)前maxN才會(huì)響應(yīng)），則提案通過(guò)，向所有表決者以及l(fā)eaner發(fā)送同步數(shù)據(jù)，達(dá)成數(shù)據(jù)一致性。

當(dāng)然上面只是簡(jiǎn)單的描述，真是的算法場(chǎng)景更復(fù)雜，所有提議者，決策者身份信息都是交叉的，如果提議者、接受者的數(shù)量是4個(gè),5個(gè)。。。但是你按照上面的思路進(jìn)行推演，最終會(huì)發(fā)現(xiàn)最終是唯一一個(gè)提議獲取多數(shù)票而勝出，從而其他提議者和決策者同步此提議。

活鎖問(wèn)題

上面的流程可能會(huì)引發(fā)活鎖問(wèn)題，那么什么是活鎖呢？

活鎖指的是任務(wù)或者執(zhí)行者沒(méi)有被阻塞，由于某些條件沒(méi)有滿足，導(dǎo)致一直重復(fù)嘗試—失敗—嘗試—失敗的過(guò)程。處于活鎖的實(shí)體是在不斷的改變狀態(tài)，活鎖有可能自行解開(kāi)。

那么上面的行為是怎么會(huì)引發(fā)活鎖呢？接下來(lái)我們一起來(lái)分析下：

在整個(gè)選舉過(guò)程中，每個(gè)人誰(shuí)先來(lái)誰(shuí)后到，“接受者”什么時(shí)間能夠接到“提議者”的信息，是完全不可控的；

假設(shè)，第一個(gè)提案者A（Proposal）已經(jīng)成功過(guò)了prepare階段，準(zhǔn)備向Acceptors廣播發(fā)送Accept時(shí)，有一個(gè)更有錢(qián)土豪提案者B也向決議者（Acceptors）廣播了prepare請(qǐng)求并在A的accept請(qǐng)求到之前發(fā)送給了決議者，這時(shí)毫無(wú)疑問(wèn)，決議者會(huì)接收該請(qǐng)求，并記錄在冊(cè)。這時(shí)候，A的accept請(qǐng)求姍姍來(lái)遲，決議者對(duì)比此proposal的賄賂金額已經(jīng)小于當(dāng)前記錄的prepare最大編號(hào)，因此不響應(yīng)給提議者A，則提議者A收到的響應(yīng)為過(guò)半，此提案廢棄。這時(shí)它又用大于Proposer A的賄賂金額重新發(fā)起 preapre廣播請(qǐng)求，這時(shí)提議者B的accept請(qǐng)求還沒(méi)有到達(dá)決議者（Acceptors），因此Acceptor也接受了該prepare請(qǐng)求，將其記錄在案，在之后提議者B發(fā)出的accept請(qǐng)求到達(dá)，決議者發(fā)現(xiàn)賄賂金額已經(jīng)小于當(dāng)前prepare的最大賄賂金額，因此拒絕響應(yīng)，這樣就會(huì)形成活鎖問(wèn)題。

總結(jié)

本篇文章故事講到這里就基本上結(jié)束了，下面我們來(lái)總結(jié)一下，其實(shí)Paxos算法主要包括兩個(gè)階段：

1. prepare階段，這個(gè)階段主要是準(zhǔn)備一個(gè)編號(hào)為N的提案，首先向所有決議者（Acceptor）發(fā)送prepare請(qǐng)求，用于試探是否支持該編號(hào)的提議。

2. accept階段，當(dāng)一階段提議收到了超過(guò)半數(shù)的響應(yīng)，則開(kāi)始正式下發(fā)提案內(nèi)容proposal，如果過(guò)半則提案提交成功，廣播給所有l(wèi)earner。

到此，相信大家對(duì)“Zookeeper中Paxos算法的介紹”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！