http://aliapp.blog.51cto.com/blog/8192229/1325794上一篇

我們已經在上面的分析中，我們已經看到observer模型在多機場景下的問題，所以，paxos模型的目標就是解決這個問題，他解決這個問題的方法就是quorum模型。

我的目標是讓大家能弄明白，掌握這些復雜的概念，所以我也會將以前我在淘寶java中間件團隊內分享時候，大家經常犯的一些錯誤，也寫到【】里面，盡可能讓大家少走彎路，如果有什么感想，疑問，后面可以留言。

PS廣告插播:淘寶java中間件團隊，你值得擁有:)

—-PAXOS——

好，我們回顧一下上下文，我們在上篇文章中談到，當機器變得更多的時候Observer不能只有一個。必須有更多個Observer，但Observer多了，到底聽誰的又成了問題。你一言我一語，大家都覺得自己是老大，誰也不服誰。咋辦捏？

這時候就得有人站出來，說：那我們少數服從多數吧！制定一套策略，在各種情況下都能夠選出一個決議不就行了！

這其實就是paxos協議的核心想法之一，我們來看一下他是怎么做到的。在這里，我不想去做那個繁瑣的證明過程，那個過程如果你感興趣，可以去看paxosmadesimple這篇文章，有中文，這里給出http://blog.csdn.net/sparkliang/article/details/5740882，數星星同學也翻譯過。可以直接google.

我在這里只說結論，因為結論更容易理解一些。

我們假定有A,B,C,D,E五臺機器。kv系統需要put一個數據[key=Whisper->val=3306]到我們這5臺機器上，要保證只要反饋為真，任意兩臺機器掛掉都不會丟失數據，并且可以保證高可用。怎么做：

1.首先,客戶端隨機選擇一個節點，進行寫入提交，這里我們隨機選擇了C這個節點，這時候C節點就是這次提議的發起人【也叫proposer，在老的2pc協議里也叫做coodinator】，當C收到這個提議的時候，C首先要做的事情是根據當前節點的最新全局globalid，做一次自增操作，我們假定，在當時全局id,GlobalID是0,所以，這個議案就被對應了一個編號，1—>[key=Whisper->val=3306]。

【【這里有兩個我們經常犯的錯誤，下面做一個解說：

1.globalid問題，在老的論文里，Lamport沒有描述這個自增id是怎么生成的，所以大家的第一個疑問一般是問id怎么生成，從我目前能夠看到的所有實現里面，基本上就是選擇哪一臺機器，就是以那臺機器當前所保持的全局id(snapshot，可能不是全局來看的最高值，但沒關系，只要是自己這臺機器的最高值就行了)，然后做一下自增就行了。我們后面會看到協議如何保證非全局最高值的globalID提議會被拒絕以至于不能夠形成決議。

2.globalid—>[key=Whisper->val=3306].這也是個會讓人困惑的問題，在原文中，他被表示為一個key-value的形式，比如proposal[0->value]。這會讓人自然的聯想到與數據庫的kv相對應，key是0，value是value。然后就會困惑，這個數據是怎么和數據庫對應起來的呢？這是我當時的困惑，現在也把他列在這里。其實很簡單，這里的globalid對應value.globalid只是對paxos協議有意義，對于數據庫，其實只需要關心value里面的數據即可，也即將globalid—>[key=Whisper->val=3306]里面的value:[key=Whisper->val=3306]作為數據庫構建映射時所需要的redoLog就行了，globalid的作用只是告訴你這些數據的順序是按照globalid來排列的，其他無意義。】】

我們回到文中，我們已經將這個新的議案標記了從C這臺機器看起來最大的globalid:1—>[key=Whisper->val=3306]。然后，他會嘗試將這個信息發送給其余的A,B,D,E這幾臺機器。

我們來看這些機器的操作流程。在這個過程中，Paxos將A,B,D,E叫做accepter【老的協議里沒有區分，管這些都叫做參與者，cohorts】，他們的行為模式如下：

如果A,B,D,E這幾臺機器的globalID小于C給出的決議的GID(1—>[key=Whisper->val=3306])，那么就告訴C，這個決議被批準了。而如果A,B,D,E這幾臺機器的GlobalID大于或等于C給出決議的GID.那么就告知C這個決議不能夠被批準。

我們假定A,B兩臺機器當時的Max(GID)是0，而D,E的Max(GID)是1.那么，A,B兩臺機器會反饋給C說協議被接受，這時候我們算算，C的議案有幾票了？A+B+!C!，一定要算自己哦:)。所以，這個議案有三票，5臺機器的半數是3.超過法定人數，于是決議就被同意了。

我們保持這個上下文，來看看D,E這邊的情況。首先，要思考的問題是，為什么D,E的Max(GID)是1呢？

其實很簡單，D可能在C發起決議的同時，也發起了一個決議，我們假定這個決議是由D發起的，決議是1—>[key=taobao->val=1234]。既然D,E的Max(GID)是1，那么意味著E已經告知D,它同意了他的決議，但D馬上會發現，A,B,C里面的任意一個都返回了D不同意。他的議案只拿到兩票，沒有通過，它雖然有點不爽，但也是沒辦法的事情啊。。

這時候C的決議已經被多數派接受，所以他需要告知所有人，我的議案1—>[key=Whisper->val=3306]已經被接受，你們去學習吧。

這時候還有一個問題是需要被考慮的，如果在C已經得知決議已經達到法定人數，在告知所有人接受之前，C掛了，應該怎么辦呢？

我之所以沒有將這個放到開始的描述里，主要原因是覺得這是個獨立因素，不應該影響議案被接受時候的清晰度。

為了解決這個問題，需要要求所有的accepter在接受某個人提出的議案之后，額外的記錄一個信息：當前accepter接受了哪個提議者的議案。

為什么要記錄這個？很簡單，我們看一下上面出現這個情況時候的判斷標準。

A機器:角色-accepter。批準的議案1—>[key=Whisper->val=3306]。提議人：C

B機器:角色-accepter。批準的議案1—>[key=Whisper->val=3306]。提議人：C

C機器:角色-proposer。掛了。。不知道他的情況。

D機器:角色-accepter。批準的議案1—>[key=taobao->val=1234]。提議人：自己

E機器:角色-proposer。“提議的”議案1—>[key=taobao->val=1234]。提議人：D。

因為有了提議人這個記錄，所以在超時后很容易可以判斷，議案1—>[key=Whisper->val=3306]是取得了多數派的議案，因為雖然D,E兩臺機器也是可以達成一致的議案的。但因為有個人本身是提議者，所以可以算出這個議案是少數派。

就可以知道哪一個議案應該是被接受的了。

在這之后，提議者還需要做一件事，就是告知D,E，被決定的決議已經是什么了。即可。

這個過程在文章中叫Learn.D,E被稱為Learner.

別看寫的簡單，這個過程也是變數最大的過程，有不少方法可以減少網絡傳輸的量，不過不在這里討論了。

下面，我們討論一下我們在2pc/3pc中面臨的問題，在paxos里面是怎么被解決的。

2pc最主要的問題是腦裂，死等。兩個問題。

對于腦裂，paxos給出的解決方案是，少數服從多數，決議發給所有人，盡一切努力送達，總有一個決議會得到多數派肯定，所以，不在糾結于某一臺機器的反饋，網絡無響應？沒有就沒有吧，其他人有反饋就行了。

所以，如果出現了機房隔離的情況，比如A,B,C在機房1，D,E在機房2，機房1和機房2物理隔離了，那么你會發現，D,E永遠也不可能提出能夠得到多數派同意的提案。

所以，少數派的利益被犧牲了。。換來了多數派的可用性。我們分析過，這是唯一能夠既保證數據的一致性，又盡可能提高可用性的唯一方法。

而對于死等問題，解決的方法也是一樣的，對于某一臺機器的無響應，完全不用去管，其他機器有相應就行了，只要能拿到多數，就不怕一小撮別有用心的反對派的反攻倒算~。

———————————paxos就是這樣一個協議———-

休息一下

—————————————————————————————-

那么Paxos有沒有什么值得改進的地方？有的，很簡單，你會發現，如果在一個決議提議的過程中，其他決議會被否決，否決本身意味著更多的網絡io，意味著更多的沖突，這些沖突都是需要額外的開銷的，代價很大很大。

為了解決類似的問題，所以才會有zookeeper對paxos協議的改進。zk的協議叫zab協議，你可以說zab協議不是paxos,但又可以說是paxos.但將paxos和zab協議之間做直接的等同關系，無疑是【錯誤】的。

其實，這也是在我們的現實生活中經常能夠發現的，如果每個議案都要經過議會的討論和表決，那么這個國家的決策無疑是低效的，怎么解決這個問題呢？弄個總統就行了。zab協議就是本著這個思路來改進paxos協議的。

———paxos改進—-zab協議討論—————–

zab協議把整個過程分為兩個部分，第一個部分叫選總統，第二個部分叫進行決議。

選總統的過程比較特殊，這種模式，相對的給人感覺思路來源于lamport的面包房算法，這個我們后面講。，選擇的主要依據是：

1.如果有gid最大的機器，那么他是主機。

2.如果好幾臺主機的gid相同，那么按照序號選擇最小的那個。

所以，在開始的時候，給A,B,C,D,E進行編號，0,1,2,3,4。第一輪的時候，因為大家的Max(gid)都是0，所以自然而然按照第二個規則，選擇A作為主機。

然后，所有人都知道A是主機以后，無論誰收到的請求，都直接轉發給A,由A機器去做后續的分發，這個分發的過程，我們叫進行決議。

進行決議的規則就簡單很多了，對其他機器進行3pc提交，但與3pc不同的是，因為是群發議案給所有其他機器，所以一個機器無反饋對大局是沒有影響的，只有當在一段時間以后，超過半數沒有反饋，才是有問題的時候，這時候要做的事情是，重新選擇總統。

具體過程是，A會將決議precommit給B,C,D,E。然后等待，當B,C,D,E里面的任意兩個返回收到后，就可以進行doCommit().否則進行doAbort().

為什么要任意兩個？原因其實也是一樣的，為了防止腦裂，原則上只能大于半數，不能少于半數，因為一旦決議成立的投票數少于半數，那么就存在另立中央的可能，兩個總統可不是鬧著玩的。

定兩個，就能夠保證，任意“兩臺”機器掛掉，數據不丟:)，能夠做到quorum。。

然后是我的個人評述，寫zab協議的人否認自己的協議是paxos.變種其實我也是有些認同的。不過，他們是針對一個問題的兩種解決方法：

因為他們解決的問題的領域相同

解決網絡傳輸無響應這個問題的方法也一樣：也即不在乎一城一池的得失，盡一切努力傳遞給其他人，然后用少數服從多數的方式，要求網絡隔離或自己掛掉的機器，在恢復可用以后，從其他主機那里學習和領會先進經驗。

并且也都使用了quorum方式來防止腦裂的情況。

核心思路是類似的，但解決問題的方法完全是兩套。paxos在其他公司的實現里面也對paxos進行了這樣，那樣的改進。不過核心思路都是這個。

我們對paxos協議的講解，就到這里。

也留下一個問題，zab協議，如果我們用在google全球數據庫spanner上，會不會有什么問題呢？請大家思考哈

后記，抱歉，這篇文章一個圖都沒有。。我已經盡可能用簡單的方式來描述paxos和他的變種協議了（當然有一個作為了問題）。如果有哪個地方不明白，也還請在后面留言吧。友情提示這篇文章不適于跳躍性閱讀，想要理解，必須從第一行開始讀到最后。。。。

google的工程師說，所有的一致性協議都是paxos的特例，我表示不置可否吧。。。。下一篇我們要討論另外一系的實現，gossip模型的實現。我個人感覺：把gossip歸類到paxos模型，似乎也不是很合適。gossip協議的兩個主要的實現方式，是dynamo和cassandra.我們在下一篇里面進行討論

http://aliapp.blog.51cto.com/blog/8192229/1325790下一篇

轉載于:https://blog.51cto.com/aliapp/1325791

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的海量存储之十八–一致性和高可用专题的全部內容，希望文章能夠幫你解決所遇到的問題。

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