如何使用Paxos算法

如何使用Paxos算法，針對這個問題，這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

        先說 Paxos，它是一個基于消息傳遞的一致性算法，Leslie Lamport 在 1990 年提出，近 幾年被廣泛應(yīng)用于分布式計算中，Google 的 Chubby，Apache 的 Zookeeper 都是基于它的理 論來實現(xiàn)的，Paxos 還被認(rèn)為是到目前為止唯一的分布式一致性算法，其它的算法都是 Paxos 的改進(jìn)或簡化。有個問題要提一下，Paxos 有一個前提:沒有拜占庭將軍問題。就是說 Paxos 只有在一個可信的計算環(huán)境中才能成立，這個環(huán)境是不會被入侵所破壞的。 

        關(guān)于 Paxos 的具體描述可以在 Wiki 中找到:http://zh.wikipedia.org/zh-cn/Paxos 算法。網(wǎng) 上關(guān)于 Paxos 分析的文章也很多。這里希望用最簡單的方式加以描述并建立起 Paxos 和 ZK Server 的對應(yīng)關(guān)系。 

        Paxos 描述了這樣一個場景，有一個叫做 Paxos 的小島(Island)上面住了一批居民，島上 面所有的事情由一些特殊的人決定，他們叫做議員(Senator)。議員的總數(shù)(Senator Count)是確 定的，不能更改。島上每次環(huán)境事務(wù)的變更都需要通過一個提議(Proposal)，每個提議都有一 個編號(PID)，這個編號是一直增長的，不能倒退。每個提議都需要超過半數(shù)((Senator Count)/2 +1)的議員同意才能生效。每個議員只會同意大于當(dāng)前編號的提議，包括已生效的和未生效 的。如果議員收到小于等于當(dāng)前編號的提議，他會拒絕，并告知對方:你的提議已經(jīng)有人提 過了。這里的當(dāng)前編號是每個議員在自己記事本上面記錄的編號，他不斷更新這個編號。整 個議會不能保證所有議員記事本上的編號總是相同的?，F(xiàn)在議會有一個目標(biāo):保證所有的議 員對于提議都能達(dá)成一致的看法。 

        好，現(xiàn)在議會開始運作，所有議員一開始記事本上面記錄的編號都是 0。有一個議員發(fā) 了一個提議:將電費設(shè)定為 1 元/度。他首先看了一下記事本，嗯，當(dāng)前提議編號是 0，那么 我的這個提議的編號就是 1，于是他給所有議員發(fā)消息:1 號提議，設(shè)定電費 1 元/度。其他 議員收到消息以后查了一下記事本，哦，當(dāng)前提議編號是 0，這個提議可接受，于是他記錄 下這個提議并回復(fù):我接受你的 1 號提議，同時他在記事本上記錄:當(dāng)前提議編號為 1。發(fā) 起提議的議員收到了超過半數(shù)的回復(fù)，立即給所有人發(fā)通知:1 號提議生效!收到的議員會 修改他的記事本，將 1 好提議由記錄改成正式的法令，當(dāng)有人問他電費為多少時，他會查看 法令并告訴對方:1 元/度。 

        現(xiàn)在看沖突的解決:假設(shè)總共有三個議員 S1-S3，S1 和 S2 同時發(fā)起了一個提議:1 號提 議，設(shè)定電費。S1 想設(shè)為 1 元/度, S2 想設(shè)為 2 元/度。結(jié)果 S3 先收到了 S1 的提議，于是他 做了和前面同樣的操作。緊接著他又收到了 S2 的提議，結(jié)果他一查記事本，咦，這個提議 的編號小于等于我的當(dāng)前編號 1，于是他拒絕了這個提議:對不起，這個提議先前提過了。 于是 S2 的提議被拒絕，S1 正式發(fā)布了提議: 1 號提議生效。S2 向 S1 或者 S3 打聽并更新了 1 號法令的內(nèi)容，然后他可以選擇繼續(xù)發(fā)起 2 號提議。 

        好，Paxos 的精華就這么多內(nèi)容。現(xiàn)在讓我們來對號入座，看看在 ZK Server 里面 Paxos 是如何得以貫徹實施的。 

        小島(Island)——ZK Server Cluster 

        議員(Senator)——ZK Server 

        提議(Proposal)——ZNode Change(Create/Delete/SetData...)

        提議編號(PID)——Zxid(ZooKeeper Transaction Id) 

        正式法令——所有 ZNode 及其數(shù)據(jù) 

        貌似關(guān)鍵的概念都能一一對應(yīng)上，但是等一下，Paxos 島上的議員應(yīng)該是人人平等的吧， 而 ZK Server 好像有一個 Leader 的概念。沒錯，其實 Leader 的概念也應(yīng)該屬于 Paxos 范疇的。 如果議員人人平等，在某種情況下會由于提議的沖突而產(chǎn)生一個“活鎖”(所謂活鎖我的理解 是大家都沒有死，都在動，但是一直解決不了沖突問題)。Paxos 的作者 Lamport 在他的文 章”The Part-Time Parliament“中闡述了這個問題并給出了解決方案——在所有議員中設(shè)立一 個總統(tǒng)，只有總統(tǒng)有權(quán)發(fā)出提議，如果議員有自己的提議，必須發(fā)給總統(tǒng)并由總統(tǒng)來提出。 好，我們又多了一個角色:總統(tǒng)。 

        總統(tǒng)——ZK Server Leader

        又一個問題產(chǎn)生了，總統(tǒng)怎么選出來的?

        現(xiàn)在我們假設(shè)總統(tǒng)已經(jīng)選好了，下面看看 ZK Server 是怎么實施的。 

        情況一: 

        屁民甲(Client)到某個議員(ZK Server)那里詢問(Get)某條法令的情況(ZNode 的數(shù)據(jù))，議員 毫不猶豫的拿出他的記事本(local storage)，查閱法令并告訴他結(jié)果，同時聲明:我的數(shù)據(jù)不 一定是最新的。你想要最新的數(shù)據(jù)?沒問題，等著，等我找總統(tǒng) Sync 一下再告訴你。 

        情況二: 

        屁民乙(Client)到某個議員(ZK Server)那里要求政府歸還欠他的一萬元錢，議員讓他在辦 公室等著，自己將問題反映給了總統(tǒng)，總統(tǒng)詢問所有議員的意見，多數(shù)議員表示欠屁民的錢 一定要還，于是總統(tǒng)發(fā)表聲明，從國庫中拿出一萬元還債，國庫總資產(chǎn)由 100 萬變成 99 萬。 屁民乙拿到錢回去了(Client 函數(shù)返回)。 

        情況三: 

        總統(tǒng)突然掛了，議員接二連三的發(fā)現(xiàn)聯(lián)系不上總統(tǒng)，于是各自發(fā)表聲明，推選新的總統(tǒng)， 總統(tǒng)大選期間政府停業(yè)，拒絕屁民的請求。 

關(guān)于如何使用Paxos算法問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。