一致性協(xié)議

一致性協(xié)議

基于CAP理論逝撬,在分布式系統(tǒng)設(shè)計(jì)過(guò)程中嫡锌,系統(tǒng)的可用性和數(shù)據(jù)一致性需要我們反復(fù)的去權(quán)衡巾陕,于是就產(chǎn)生了很多經(jīng)典的數(shù)據(jù)一致性協(xié)議,比如2PC菠剩、3PC, PAXOS等易猫。

2PC協(xié)議

2PC是Two Phase Commit的縮寫(xiě),即兩階段提交具壮。所謂的兩個(gè)階段是指:第一階段:準(zhǔn)備階段(投票階段)和第二階段:提交階段(執(zhí)行階段)准颓。在分布式系統(tǒng)中,每個(gè)節(jié)點(diǎn)雖然可以知曉自己的操作時(shí)成功或者失敗棺妓,卻無(wú)法知道其他節(jié)點(diǎn)的操作的成功或失敗攘已。當(dāng)一個(gè)事務(wù)跨越多個(gè)節(jié)點(diǎn)時(shí),為了保持事務(wù)的ACID特性怜跑,需要引入一個(gè)作為協(xié)調(diào)者的組件來(lái)統(tǒng)一掌控所有節(jié)點(diǎn)(稱作參與者)的操作結(jié)果并最終指示這些節(jié)點(diǎn)是否要把操作結(jié)果進(jìn)行真正的提交(比如將更新后的數(shù)據(jù)寫(xiě)入磁盤(pán)等等)样勃。因此,二階段提交的算法思路可以概括為:參與者將操作成敗通知協(xié)調(diào)者妆艘,再由協(xié)調(diào)者根據(jù)所有參與者的反饋情報(bào)決定各參與者是否要提交操作還是中止操作彤灶。

協(xié)議說(shuō)明

階段一:提交事務(wù)請(qǐng)求
  1. 事務(wù)詢問(wèn)
    協(xié)調(diào)者向所有的參與者發(fā)送事務(wù)內(nèi)容,詢問(wèn)是否可以執(zhí)行事務(wù)提交操作批旺,并開(kāi)始等待各個(gè)響應(yīng)者的反饋幌陕。
  2. 執(zhí)行事務(wù)
    各參與者執(zhí)行事務(wù)操作,并將Undo和Redo信息記入事務(wù)日志中汽煮。
  3. 執(zhí)行事務(wù)
    各參與者向協(xié)調(diào)者反饋事務(wù)詢問(wèn)的響應(yīng)
    如果參與者成功執(zhí)行了事務(wù)操作搏熄,那么就反饋給協(xié)調(diào)者Yes響應(yīng)棚唆,表示事務(wù)可以執(zhí)行;如果參與者沒(méi)有成功執(zhí)行事務(wù)心例,那么就反饋給協(xié)調(diào)者No響應(yīng)宵凌,表示事務(wù)不可以執(zhí)行。
階段二:執(zhí)行事務(wù)提交

在階段二中止后,協(xié)調(diào)者會(huì)根據(jù)階段一中各參與者的反饋情況來(lái)決定最終是否可以進(jìn)行事務(wù)的提交瞎惫,主要包含以下兩種可能:

執(zhí)行事務(wù)提交
假如協(xié)調(diào)者從所有的參與者得到的反饋全是Yes,那么協(xié)調(diào)者就會(huì)執(zhí)行事務(wù)提交操作译株。

  1. 發(fā)送提交請(qǐng)求
    協(xié)調(diào)者向所有的參與者發(fā)出Commit請(qǐng)求瓜喇。
  2. 事務(wù)提交
    參與者收到協(xié)調(diào)者的Commit請(qǐng)求后,會(huì)正式的執(zhí)行事務(wù)提交操作歉糜,并在完成之后釋放執(zhí)行事務(wù)期間占有的相關(guān)資源乘寒。
  3. 反饋事務(wù)提交結(jié)果
    參與者在完成事務(wù)提交之后,向協(xié)調(diào)者發(fā)送Ack確認(rèn)消息匪补。
  4. 完成事務(wù)
    協(xié)調(diào)者接收到所有參與者反饋的Ack消息后伞辛,完成事務(wù)。
screenshot

執(zhí)行事務(wù)提交
假如任何一個(gè)參與者向協(xié)調(diào)者反饋了No響應(yīng)夯缺,或者在等待超時(shí)之后蚤氏,協(xié)調(diào)者尚無(wú)收到所有參與者的反饋?lái)憫?yīng),那么協(xié)調(diào)者就會(huì)中斷事務(wù)喳逛。

  1. 發(fā)送回滾請(qǐng)求
    協(xié)調(diào)者向所有的參與者發(fā)出Rollback請(qǐng)求瞧捌。
  2. 事務(wù)回滾
    參與者收到協(xié)調(diào)者的Rollback請(qǐng)求后,會(huì)利用在階段一中記錄的Undo信息來(lái)執(zhí)行事務(wù)的回滾操作润文,并在回滾之后釋放占有的相關(guān)的資源會(huì)正式的執(zhí)行事務(wù)提交操作姐呐,并在完成之后釋放執(zhí)行事務(wù)期間占有的相關(guān)資源。
  3. 反饋事務(wù)回滾結(jié)果
    參與者在完成事務(wù)回滾之后典蝌,向協(xié)調(diào)者發(fā)送Ack確認(rèn)消息曙砂。
  4. 中斷事務(wù)
    協(xié)調(diào)者接收到所有參與者反饋的Ack消息后,完成事務(wù)中斷骏掀。
screenshot

2PC優(yōu)缺點(diǎn)

優(yōu)點(diǎn)就不用說(shuō)了鸠澈,原理簡(jiǎn)單,實(shí)現(xiàn)起來(lái)比較容易截驮;缺點(diǎn)還是需要詳細(xì)介紹下的笑陈,主要包含以下幾點(diǎn):

  1. 同步阻塞問(wèn)題。執(zhí)行過(guò)程中葵袭,所有參與節(jié)點(diǎn)都是事務(wù)阻塞型的涵妥。當(dāng)參與者占有公共資源時(shí),其他第三方節(jié)點(diǎn)訪問(wèn)公共資源不得不處于阻塞狀態(tài)坡锡。
  2. 單點(diǎn)故障蓬网。由于協(xié)調(diào)者的重要性窒所,一旦協(xié)調(diào)者發(fā)生故障。參與者會(huì)一直阻塞下去帆锋。尤其在第二階段吵取,協(xié)調(diào)者發(fā)生故障,那么所有的參與者還都處于鎖定事務(wù)資源的狀態(tài)中锯厢,而無(wú)法繼續(xù)完成事務(wù)操作皮官。(如果是協(xié)調(diào)者掛掉,可以重新選舉一個(gè)協(xié)調(diào)者实辑,但是無(wú)法解決因?yàn)閰f(xié)調(diào)者宕機(jī)導(dǎo)致的參與者處于阻塞狀態(tài)的問(wèn)題)
  3. 數(shù)據(jù)不一致臣疑。在二階段提交的階段二中,當(dāng)協(xié)調(diào)者向參與者發(fā)送commit請(qǐng)求之后徙菠,發(fā)生了局部網(wǎng)絡(luò)異常或者在發(fā)送commit請(qǐng)求過(guò)程中協(xié)調(diào)者發(fā)生了故障郁岩,這回導(dǎo)致只有一部分參與者接受到了commit請(qǐng)求婿奔。而在這部分參與者接到commit請(qǐng)求之后就會(huì)執(zhí)行commit操作。但是其他部分未接到commit請(qǐng)求的機(jī)器則無(wú)法執(zhí)行事務(wù)提交问慎。于是整個(gè)分布式系統(tǒng)便出現(xiàn)了數(shù)據(jù)部一致性的現(xiàn)象萍摊。
  4. 二階段無(wú)法解決的問(wèn)題:協(xié)調(diào)者再發(fā)出commit消息之后宕機(jī),而唯一接收到這條消息的參與者同時(shí)也宕機(jī)了如叼。那么即使協(xié)調(diào)者通過(guò)選舉協(xié)議產(chǎn)生了新的協(xié)調(diào)者冰木,這條事務(wù)的狀態(tài)也是不確定的,沒(méi)人知道事務(wù)是否被已經(jīng)提交笼恰。

3PC協(xié)議

三階段提交(Three-phase commit)踊沸,也叫三階段提交協(xié)議(Three-phase commit protocol),是二階段提交(2PC)的改進(jìn)版本社证。與兩階段提交不同的是逼龟,三階段提交有兩個(gè)改動(dòng)點(diǎn):

  1. 引入超時(shí)機(jī)制。同時(shí)在協(xié)調(diào)者和參與者中都引入超時(shí)機(jī)制追葡。
  2. 在第一階段和第二階段中插入一個(gè)準(zhǔn)備階段腺律。保證了在最后提交階段之前各參與節(jié)點(diǎn)的狀態(tài)是一致的。

也就是說(shuō)宜肉,除了引入超時(shí)機(jī)制之外匀钧,3PC把2PC的準(zhǔn)備階段再次一分為二,這樣三階段提交就有CanCommit谬返、PreCommit之斯、DoCommit三個(gè)階段。


screenshot
階段一:CanCommit階段

3PC的CanCommit階段其實(shí)和2PC的準(zhǔn)備階段很像朱浴。協(xié)調(diào)者向參與者發(fā)送commit請(qǐng)求吊圾,參與者如果可以提交就返回Yes響應(yīng)达椰,否則返回No響應(yīng)。

  1. 事務(wù)詢問(wèn) 協(xié)調(diào)者向參與者發(fā)送CanCommit請(qǐng)求项乒。詢問(wèn)是否可以執(zhí)行事務(wù)提交操作啰劲。然后開(kāi)始等待參與者的響應(yīng)。
  2. 響應(yīng)反饋 參與者接到CanCommit請(qǐng)求之后檀何,正常情況下蝇裤,如果其自身認(rèn)為可以順利執(zhí)行事務(wù),則返回Yes響應(yīng)频鉴,并進(jìn)入預(yù)備狀態(tài)栓辜。否則反饋No
階段二:PreCommit階段

協(xié)調(diào)者根據(jù)參與者的反應(yīng)情況來(lái)決定是否可以記性事務(wù)的PreCommit操作。根據(jù)響應(yīng)情況垛孔,有以下兩種可能:
假如協(xié)調(diào)者從所有的參與者獲得的反饋都是Yes響應(yīng)藕甩,那么就會(huì)執(zhí)行事務(wù)的預(yù)執(zhí)行。

  1. 發(fā)送預(yù)提交請(qǐng)求 協(xié)調(diào)者向參與者發(fā)送PreCommit請(qǐng)求周荐,并進(jìn)入Prepared階段狭莱。
  2. 事務(wù)預(yù)提交 參與者接收到PreCommit請(qǐng)求后,會(huì)執(zhí)行事務(wù)操作概作,并將undo和redo信息記錄到事務(wù)日志中腋妙。
  3. 響應(yīng)反饋 如果參與者成功的執(zhí)行了事務(wù)操作,則返回ACK響應(yīng)讯榕,同時(shí)開(kāi)始等待最終指令骤素。

假如有任何一個(gè)參與者向協(xié)調(diào)者發(fā)送了No響應(yīng),或者等待超時(shí)之后愚屁,協(xié)調(diào)者都沒(méi)有接到參與者的響應(yīng)济竹,那么就執(zhí)行事務(wù)的中斷。

  1. 發(fā)送中斷請(qǐng)求 協(xié)調(diào)者向所有參與者發(fā)送abort請(qǐng)求霎槐。
  2. 中斷事務(wù) 參與者收到來(lái)自協(xié)調(diào)者的abort請(qǐng)求之后(或超時(shí)之后规辱,仍未收到協(xié)調(diào)者的請(qǐng)求),執(zhí)行事務(wù)的中斷栽燕。
階段三:doCommit階段

該階段進(jìn)行真正的事務(wù)提交罕袋,也可以分為以下兩種情況。
執(zhí)行提交

  1. 發(fā)送提交請(qǐng)求 協(xié)調(diào)接收到參與者發(fā)送的ACK響應(yīng)碍岔,那么他將從預(yù)提交狀態(tài)進(jìn)入到提交狀態(tài)浴讯。并向所有參與者發(fā)送doCommit請(qǐng)求。
  2. 事務(wù)提交 參與者接收到doCommit請(qǐng)求之后蔼啦,執(zhí)行正式的事務(wù)提交榆纽。并在完成事務(wù)提交之后釋放所有事務(wù)資源。
  3. 響應(yīng)反饋 事務(wù)提交完之后,向協(xié)調(diào)者發(fā)送Ack響應(yīng)奈籽。
  4. 完成事務(wù) 協(xié)調(diào)者接收到所有參與者的ack響應(yīng)之后饥侵,完成事務(wù)。

中斷事務(wù)
協(xié)調(diào)者沒(méi)有接收到參與者發(fā)送的ACK響應(yīng)(可能是接受者發(fā)送的不是ACK響應(yīng)衣屏,也可能響應(yīng)超時(shí))躏升,那么就會(huì)執(zhí)行中斷事務(wù)。

  1. 發(fā)送中斷請(qǐng)求 協(xié)調(diào)者向所有參與者發(fā)送abort請(qǐng)求
  2. 事務(wù)回滾 參與者接收到abort請(qǐng)求之后狼忱,利用其在階段二記錄的undo信息來(lái)執(zhí)行事務(wù)的回滾操作膨疏,并在完成回滾之后釋放所有的事務(wù)資源。
  3. 反饋結(jié)果 參與者完成事務(wù)回滾之后钻弄,向協(xié)調(diào)者發(fā)送ACK消息
  4. 中斷事務(wù) 協(xié)調(diào)者接收到參與者反饋的ACK消息之后佃却,執(zhí)行事務(wù)的中斷。

在doCommit階段窘俺,如果參與者無(wú)法及時(shí)接收到來(lái)自協(xié)調(diào)者的doCommit或者rebort請(qǐng)求時(shí)饲帅,會(huì)在等待超時(shí)之后,會(huì)繼續(xù)進(jìn)行事務(wù)的提交瘤泪。(其實(shí)這個(gè)應(yīng)該是基于概率來(lái)決定的洒闸,當(dāng)進(jìn)入第三階段時(shí),說(shuō)明參與者在第二階段已經(jīng)收到了PreCommit請(qǐng)求均芽,那么協(xié)調(diào)者產(chǎn)生PreCommit請(qǐng)求的前提條件是他在第二階段開(kāi)始之前,收到所有參與者的CanCommit響應(yīng)都是Yes单鹿。(一旦參與者收到了PreCommit掀宋,意味他知道大家其實(shí)都同意修改了)所以,一句話概括就是仲锄,當(dāng)進(jìn)入第三階段時(shí)劲妙,由于網(wǎng)絡(luò)超時(shí)等原因,雖然參與者沒(méi)有收到commit或者abort響應(yīng)儒喊,但是他有理由相信:成功提交的幾率很大镣奋。

3PC優(yōu)缺點(diǎn)

相比較于2PC協(xié)議,三階段提交最大的優(yōu)點(diǎn)就是降低了參與者的阻塞范圍怀愧,并且能后在出現(xiàn)單點(diǎn)故障后繼續(xù)達(dá)成一致侨颈,但是也引入了新的問(wèn)題,例如在參與者接收到preCommit消息后芯义,如果出現(xiàn)網(wǎng)絡(luò)分區(qū)哈垢,此時(shí)協(xié)調(diào)者所在的節(jié)點(diǎn)和參與者無(wú)法進(jìn)行正常的網(wǎng)絡(luò)通信,在這種情況下扛拨,該參與者依然會(huì)進(jìn)行事務(wù)的提交耘分,最終造成數(shù)據(jù)的不一致問(wèn)題。

關(guān)于PAXOS協(xié)議,感覺(jué)還是理解的不太透測(cè)求泰,后續(xù)的文章在介紹吧央渣。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市渴频,隨后出現(xiàn)的幾起案子芽丹,更是在濱河造成了極大的恐慌,老刑警劉巖枉氮,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件志衍,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡聊替,警方通過(guò)查閱死者的電腦和手機(jī)楼肪,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)惹悄,“玉大人春叫,你說(shuō)我怎么就攤上這事∑郏” “怎么了暂殖?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)当纱。 經(jīng)常有香客問(wèn)我呛每,道長(zhǎng),這世上最難降的妖魔是什么坡氯? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任晨横,我火速辦了婚禮,結(jié)果婚禮上箫柳,老公的妹妹穿的比我還像新娘手形。我一直安慰自己,他們只是感情好悯恍,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布库糠。 她就那樣靜靜地躺著,像睡著了一般涮毫。 火紅的嫁衣襯著肌膚如雪瞬欧。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,713評(píng)論 1 312
  • 那天罢防,我揣著相機(jī)與錄音黍判,去河邊找鬼。 笑死篙梢,一個(gè)胖子當(dāng)著我的面吹牛顷帖,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼贬墩,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼榴嗅!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起陶舞,我...
    開(kāi)封第一講書(shū)人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤嗽测,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后肿孵,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體唠粥,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年停做,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了晤愧。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡蛉腌,死狀恐怖官份,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情烙丛,我是刑警寧澤舅巷,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站河咽,受9級(jí)特大地震影響钠右,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜忘蟹,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一飒房、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧寒瓦,春花似錦、人聲如沸坪仇。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)椅文。三九已至喂很,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間皆刺,已是汗流浹背少辣。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留羡蛾,地道東北人漓帅。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親忙干。 傳聞我的和親對(duì)象是個(gè)殘疾皇子器予,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容