海量存储之十八–一致性和高可用专题
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位技術專家共同創作,文字、視頻、音頻交互閱讀總結
以上是生活随笔為你收集整理的海量存储之十八–一致性和高可用专题的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: python old-style inh
- 下一篇: 一个不错的CSS DIV布局,DIV高度