|
1、Paxos算法的應(yīng)用 Paxos算法及變種算法在分布式系統(tǒng)中應(yīng)用廣泛。 基于Paxos算法的變種有：ZAB、Raft 例如： · Zookeeper 中的ZAB協(xié)議也是Paxos算法的變種。Zookeeper通過(guò)ZAB協(xié)議實(shí)現(xiàn)數(shù)據(jù)一致性，以提供數(shù)據(jù)一致性。 · Nutanix 中通過(guò)Paxos算法實(shí)施元數(shù)據(jù)在各節(jié)點(diǎn)的強(qiáng)一致性。 2、什么是Paxos算法 Paxos算法解決的問(wèn)題是在一個(gè)可能發(fā)生消息可能會(huì)延遲、丟失、重復(fù)的分布式系統(tǒng)中如何就某個(gè)值達(dá)成一致，保證不論發(fā)生以上任何異常，都不會(huì)破壞決議的一致性。 這 個(gè)“值”可能是一個(gè)數(shù)據(jù)的某，也可能是一條LOG等；根據(jù)不同的應(yīng)用環(huán)境這個(gè)“值”也不同。 一個(gè)典型的場(chǎng)景是，在一個(gè)分布式數(shù)據(jù)庫(kù)系統(tǒng)中，如果各節(jié)點(diǎn)的初始狀態(tài)一致，每個(gè)節(jié)點(diǎn)都執(zhí)行相同的操作序列，那么他們最后能得到一個(gè)一致的狀態(tài)。為保證每個(gè)節(jié)點(diǎn)執(zhí)行相同的命令序列，需要在每一條指令上執(zhí)行一個(gè)“一致性算法”以保證每個(gè)節(jié)點(diǎn)看到的指令一致。 3、Paxos算法的原理 例如：公司商定年會(huì)舉辦的地點(diǎn)，每個(gè)人都可以提出建議。在現(xiàn)實(shí)環(huán)境中我們可以在一個(gè)會(huì)議室共同討論或在微信群中討論（基于內(nèi)存共享方式）；但在基于消息傳遞的分布式環(huán)境中每個(gè)人只能通過(guò)手機(jī)短信與其它人通過(guò)。如何在這種會(huì)延遲、丟失的環(huán)境中確定一個(gè)年會(huì)舉辦地點(diǎn)； Paxos算法是這樣解決這個(gè)問(wèn)題： 1、每個(gè)人都可以提出建議、同意建議、接受建議 2、少數(shù)服從多數(shù)。只要建議被多數(shù)人同意即可確定該建議。 于是確定以下討論方式： 1、只有被提出來(lái)的建議才能被大家同意。 2、最終只能確定一個(gè)建議 3、如果某個(gè)人認(rèn)為大家同意了某 個(gè)建議，那么這個(gè)建議必須真的是被大家同意的 算法推論： 情況一：如果只有一個(gè)人提出建議怎么辦？ 如果只有一個(gè)建議被提出來(lái)那么大家必須同這個(gè)建議，因?yàn)槿绻煌膺@個(gè)建議就無(wú)法確定一個(gè)年會(huì)舉辦地點(diǎn)。 所以得出這樣的結(jié)論： P1:每一個(gè)人必須同意他收到的第一個(gè)建議 基于這樣的結(jié)論會(huì)出現(xiàn)以下問(wèn)題：  張三給王五發(fā)短信說(shuō)：我建議去上海舉辦年會(huì)！ 王五給李四發(fā)短信說(shuō)：我建議去廣州舉辦年會(huì)！ 李四給張三發(fā)短信說(shuō)：我建議去北京舉辦年會(huì)！ 根據(jù)P1：每個(gè)人必須同意他收到的第一個(gè)建議，那么張三、李四、王五最終獲得的信息是不一致的。 所以再次規(guī)定：一個(gè)提議必須被大多數(shù)人同意才能生效。 那么說(shuō)明一個(gè)人可以同時(shí)同意多個(gè)建議，如果一個(gè)人可以同時(shí)同意多個(gè)建議最終可能出現(xiàn)拜占庭將軍問(wèn)題導(dǎo)致最終結(jié)果不一致。（例如：張三同意到北京舉辦也同意到廣州舉辦，那么李四將獲得2票一票自己的，一票張三的。他會(huì)認(rèn)為自己獲得多數(shù)人支持所以就確定最終是到北京舉辦，同理王五也會(huì)同時(shí)獲得2票，也認(rèn)為大家最終決定到廣州舉辦）； 所以要避免出現(xiàn)這種問(wèn)題，某個(gè)人只要同意的多個(gè)提議中的內(nèi)容相同（公司舉辦的地址）就不會(huì)出現(xiàn)這種問(wèn)題。  最終協(xié)商結(jié)果是有2票是到同一個(gè)地方，這樣就可以確認(rèn)最終舉辦地！ 那么就會(huì)引出 這樣的一個(gè)結(jié)論： P2:一旦同意某個(gè)建議，那么之后同意的建議中提議公司舉辦年會(huì)的地址必須一致。 問(wèn)題出來(lái)了：如何確定什么是“之前”，什么 是“之后” 所以必須為提議分配一個(gè)編號(hào)，在提議之間建立一個(gè)全序關(guān)系。 情況二： 當(dāng)張三、李四、王五三個(gè)人確定最終到鄭州舉辦年會(huì)后。趙六、孫七2人由于手機(jī)沒(méi)電，沒(méi)收到通知，當(dāng)他們2人開(kāi)機(jī)后趙六給孫七發(fā)短信提議到海南舉辦，這個(gè)提議是孫七開(kāi)機(jī)后第一次收到的提議，根據(jù)P1原則，他必須同意他接收到的第一個(gè)提議，所以孫七同意到海南舉行年會(huì)。但這樣就會(huì)導(dǎo)致孫七與張三、李四、王五他們確定的舉辦地點(diǎn)不一致。  為了避免出現(xiàn)以上問(wèn)題。對(duì)P2進(jìn)行具體說(shuō)明： P2a:一旦一個(gè)提議被大家同意，那么之后的人再次同意的提議中的公司舉辦年會(huì)的地址必須一致。 也就是說(shuō)，孫七在開(kāi)機(jī)后同意的第一個(gè)提議必須是“到鄭州舉辦”才不會(huì)出現(xiàn)信息不一致的現(xiàn)象。但孫七開(kāi)機(jī)后必須得接受第一個(gè)提議（P1原則），并且無(wú)法干涉提議中的內(nèi)容（公司舉辦年會(huì)的地址）。所以最好的辦法通過(guò)某種方式讓趙六的提議中的內(nèi)容與張三、李四同意的地址相同（到鄭州舉行）。這樣孫七同意的第一個(gè)提議就是“到鄭州舉辦” 我們?cè)俅螌?duì)P2a進(jìn)行修改： P2b:一旦一個(gè)提議被大家同意，那么之后的人再次提議，提議中的公司舉辦年會(huì)的地址必須跟之前其它人解決的地址一致。 如何讓剛開(kāi)機(jī)的趙六提議的內(nèi)容必須與張三、李四、王五討論出來(lái)的一致（到鄭州舉行）？ 我們繼續(xù)對(duì)P2b進(jìn)行強(qiáng)化修改： P2c:如果有一個(gè)編號(hào)為N的提議具有V(提議的內(nèi)容)，那么存在一個(gè)多數(shù)派，要么他們中所有人都沒(méi)有同意編號(hào)小于N的任何提議，要么他們已經(jīng)同意的所有編號(hào)小于N的提案中編號(hào)最大的那個(gè)提案具有V。 要滿足P2c的要求，提議人在提議之前，首先要和多數(shù)人通信并獲得他們進(jìn)行的最后一次同意的提議。之后根據(jù)反饋的信息決定這次提議的內(nèi)容，形成提議開(kāi)始投票！ 所以整個(gè)投票決議分兩個(gè)階段： 1、準(zhǔn)備階段 1、提議人選擇一個(gè)編號(hào)N，并將準(zhǔn)備信息發(fā)送給多數(shù)人。 2、如果收信人收到準(zhǔn)備消息后，如果提議的編號(hào)大于它已經(jīng)回復(fù)的所有準(zhǔn)備信息。那么收信人將自己上次接受的提議內(nèi)容回復(fù)給提議人，并承諾不再回復(fù)小于N的提議。 2、同意階段 1、當(dāng)一個(gè)提議人收到多數(shù)人反饋的信息后，就進(jìn)入同意階段。它要向反饋給它信息的人再次發(fā)送一個(gè)請(qǐng)同意該提議的請(qǐng)求。包含編號(hào)N和根據(jù)P2C決定的提議內(nèi)容（如果回復(fù)中沒(méi)有反饋他們已經(jīng)接受過(guò)的提議內(nèi)容，則可以自由決定提議內(nèi)容） 2、在不違背向其它人承諾的前提下，收到該提議請(qǐng)求后立即同意該請(qǐng)求。 舉例說(shuō)明一下： 假設(shè)：只有User1、User2、User3 三個(gè)人決定1 1等于幾！ 1、準(zhǔn)備階段  1、User1 提案編號(hào)為1 并發(fā)送給User2和User3。 因User2 和User3 根據(jù)P2c它們并沒(méi)有接受過(guò)小于編號(hào)為1的提案。所以它們可以接受該提議，并反饋給User1 不再接受小于編號(hào)1的提案。這時(shí)User1收到多數(shù)人的回復(fù)，將進(jìn)入第2階段。（如果收到的回復(fù)并不能形成多數(shù)人，那么將再次進(jìn)入階段1） 2、User2 提案編號(hào)為2 ；并發(fā)送給User1和User3。 因User1第一次收到提案，并且根據(jù)P2C它并沒(méi)有同意過(guò)小于編號(hào)為2的提議，所以它可以接受該提議。User3由于接受過(guò)User1編號(hào)為1的提案，但User2的提案編號(hào)2>1所以User3也可以同意User2的提議，并反饋不再接受小于2的提議。User2也收到多數(shù)人的回復(fù)，將進(jìn)行第2階段。 3、User3提案編號(hào)為3 ；并發(fā)送給user1 和user2 . 因user1收到user3編號(hào)為3的提案>user2編號(hào)為2的提案，所以接受user3的提案。 因user2收到User3編號(hào)為3的提案>user1 編號(hào)為1的提案，所以接受user3的提案。 至些user3也收到多數(shù)人回復(fù)，將進(jìn)行第2階段。 階段2： 1、user1 發(fā)送編號(hào)為1的提議，提議內(nèi)容為：1 1=1；并發(fā)送給user2和User3 。 由于user2已經(jīng)聲明不再接受小于3的提案，所以拒絕user1的提案。 由于User3已經(jīng)聲明不再接受小于2的提案，所以同樣拒絕User1的提案。 User1提議被多數(shù)人拒絕，再次進(jìn)入階段1. 2、user2 發(fā)送編號(hào)為2的提議，提議內(nèi)容為：1 1=2；并發(fā)送給User1和User3 由于User1已經(jīng)聲明不再接受小于3的提案，所以拒絕user2的提議。 由于User3已經(jīng)聲明不再接受小于2的提案，該提案編號(hào)=2所以u(píng)ser3同意User2的提議。 但User2并沒(méi)有獲得多數(shù)人的同意，所以同樣進(jìn)行階段1. 3、User3 發(fā)送編號(hào)為3的提議，提議內(nèi)容為：1 1=3；并發(fā)送給User1和User2; 由于user1聲明不再接受小于3的提案，所以同意User3的提議。 由于 user2聲明不再接受小于3的提案，所以同意User3的提議。 至此最終User3可以獲得多數(shù)人的同意。 Paxos算法圖解：  在實(shí)現(xiàn)環(huán)境中會(huì)通過(guò)一次提議，選擇一個(gè)Leader。后續(xù)所有的提議都只能由Leader提出 4、課后思考 為什么Zookeeper節(jié)點(diǎn)通常配置為3、5、7奇數(shù)節(jié)點(diǎn)？ |
|
|
來(lái)自： liang1234_ > 《分布式算法》
