Paxos 有點(diǎn)類似我們之前說(shuō)的 2PC葵姥，3PC紊浩，但是解決了他們倆的各種硬傷。該算法在很多大廠都得到了工程實(shí)踐酌呆，比如阿里的 OceanBase 的分布式數(shù)據(jù)庫(kù)衡载，底層就是使用的 paxos 算法。再比如 Google 的 chubby 分布式鎖也是用的這個(gè)算法隙袁√涤椋可見該算法在分布式系統(tǒng)中的地位，甚至于菩收，paxos 就是分布式一致性的代名詞梨睁。
Paxos 角色
在paxos算法中，分為4種角色：
- Proposer ：信使
- Acceptor：決策者
- Client：產(chǎn)生議題者
- Learner：最終決策學(xué)習(xí)者
不過(guò)為了方便理解娜饵，我們將Proposer摘取出來(lái)作為算法的主角坡贺，其他三者為配角。
Paxos 舉例說(shuō)明
在 Paxos 島上，有A1, A2, A3, A4, A5 5位議員拴念，就稅率問(wèn)題進(jìn)行決議，決議結(jié)果由少數(shù)服從多數(shù)來(lái)決定褐缠。
我們假設(shè)幾個(gè)場(chǎng)景來(lái)解釋：
場(chǎng)景 1.
（暫且不考慮信使政鼠，即不考慮分布式網(wǎng)絡(luò)問(wèn)題）
A1 說(shuō)：稅率應(yīng)該是 10%。而此時(shí)只有他一個(gè)人提這個(gè)建議队魏。如下圖：
很完美公般，沒(méi)有任何人和他競(jìng)爭(zhēng)提案，他的這個(gè)提案毫無(wú)阻撓的通過(guò)了胡桨。A2 - A5 都會(huì)回應(yīng)他：我們收到了你的提案官帘，等待最終的批準(zhǔn)。而 A1 在收到 2 份回復(fù)后（加上A1自己昧谊，表決結(jié)果過(guò)半）刽虹，就可以發(fā)布最終的決議：稅率定位 10%，不用再討論了呢诬。
場(chǎng)景 2.
現(xiàn)在我們假設(shè)在 A1 提出 10% 稅率提案的同時(shí), A5 決定將稅率定為 20%涌哲，如果這個(gè)提案要通過(guò)侍從送到其他議員的案頭，A1 的草案將由 4 位侍從送到 A2-A5 那里尚镰。但是侍從不靠譜（代表分布式環(huán)境不靠譜）阀圾，負(fù)責(zé) A2 和 A3 的侍從順利送達(dá)，而負(fù)責(zé) A4 和 A5 的侍從則開溜了狗唉！而 A5 的草案則送到了 A4 和 A3 的手中初烘。
現(xiàn)在，A1 分俯，A2肾筐，A3 收到了 A1 的提案，A3澳迫，A4局齿， A5 收到 A5 的提案，按照 Paxos 的協(xié)議橄登，A1抓歼，A2，A4拢锹，A5 4個(gè)侍從將接受他們的提案谣妻，侍從拿著回復(fù)：我已收到你的提案，等待最終批準(zhǔn) 回到提案者那里卒稳。
而 A3 的行為將決定批準(zhǔn)哪一個(gè)蹋半。當(dāng) A3 同時(shí)收到了 A1 和 A5 的請(qǐng)求，該如何抉擇呢充坑？不同的抉擇將會(huì)導(dǎo)致不同的結(jié)果减江。
場(chǎng)景 2. 抉擇1.
假設(shè) A1 的提案先送到 A3 那里染突，并且 A3 接受了該提案并回復(fù)了侍從。這樣辈灼，A1 加上 A2 加上 A3份企，構(gòu)成了多數(shù)派，成功確定了稅率為 10%巡莹。 而 A5 的侍從由于路上喝酒喝多了司志，晚到了一天，等他到了降宅，稅率已經(jīng)確定了（決策已經(jīng)成型）骂远，A3 回復(fù) A5：兄弟，你來(lái)的太晚了腰根，稅率已經(jīng)定好了激才，不用折騰了，聽 A1 的吧唠雕。
場(chǎng)景 2. 抉擇2.
依然假設(shè) A1 的提案先送到 A3 處贸营，但是這次 A5 的侍從不是放假了，只是中途耽擱了一會(huì)岩睁。這次, A3 依然會(huì)將"接受"回復(fù)給 A1 .但是在決議成型之前它又收到了 A5 的提案钞脂。這時(shí)協(xié)議根據(jù) A5 的身份地位有兩種處理方式。
- 當(dāng) A5 地位很高捕儒，例如 CEO冰啃，就回復(fù) A5：我已收到您的提案，等待最終批準(zhǔn)刘莹，但是您之前有人提出將稅率定為10%,請(qǐng)明察阎毅。
- 當(dāng) A5 沒(méi)地位，普通碼農(nóng)一個(gè)点弯，直接不回復(fù)扇调。等待 A1 廣播：稅率定為 10% 啦！抢肛！
場(chǎng)景 2. 抉擇3.
在這個(gè)情況中狼钮，我們將看見，根據(jù)提案的時(shí)間及提案者的權(quán)勢(shì)決定是否應(yīng)答是有意義的捡絮。在這里熬芜，時(shí)間和提案者的權(quán)勢(shì)就構(gòu)成了給提案編號(hào)的依據(jù)。這樣的編號(hào)符合"任何兩個(gè)提案之間構(gòu)成偏序"的要求福稳。
A1 和 A5 同樣提出上述提案涎拉，這時(shí) A1 可以正常聯(lián)系 A2 和 A3，A5 也可以正常聯(lián)系這兩個(gè)人。這次 A2 先收到 A1 的提案; A3 則先收到 A5 的提案鼓拧。而 A5 更有地位半火。
在這種情況下，已經(jīng)回答 A1 的 A2 發(fā)現(xiàn)有比 A1 更有權(quán)勢(shì)的 A5 提出了稅率 20% 的新提案季俩，于是回復(fù)A5說(shuō)：我已收到您的提案慈缔，等待最終批準(zhǔn)。
而回復(fù) A5 的 A3 發(fā)現(xiàn)新的提案者A1是個(gè)小人物种玛，沒(méi)地位不予應(yīng)答。
此時(shí)瓤檐，A5 得到了 A2赂韵，A3 的回復(fù)，于是 A5 說(shuō)：稅率定為 20%挠蛉，別再討論了祭示。
那 A4 呢？ A4 由于睡過(guò)頭了(決議已經(jīng)成型)谴古，迷迷糊糊的說(shuō)：現(xiàn)有的稅率是什么? 如果沒(méi)有決定质涛，則建議將其定為 15%.
這個(gè)時(shí)候，其他的議員就告訴他：哥們掰担，已經(jīng)定為 20% 了汇陆，別折騰了。洗洗繼續(xù)睡吧带饱。
整個(gè)過(guò)程如下圖：
總結(jié)
我們可以看到Paxos算法就是少數(shù)服從多數(shù)毡代，同時(shí)，還會(huì)根據(jù)議員的身份和提案的時(shí)間來(lái)判斷是否需要應(yīng)答勺疼，這個(gè)身份其實(shí)就是一個(gè)編號(hào)教寂，是為了防止出現(xiàn)活性導(dǎo)致死循環(huán)。
Paxos 的目標(biāo)：保證最終有一個(gè)提案會(huì)被選定执庐，當(dāng)提案被選定后酪耕，其他議員最終也能獲取到被選定的提案。
Paxos 協(xié)議用來(lái)解決的問(wèn)題可以用一句話來(lái)簡(jiǎn)化： 將所有節(jié)點(diǎn)都寫入同一個(gè)值轨淌，且被寫入后不再更改迂烁。
注意：這一切都是在沒(méi)有 拜占庭將軍 問(wèn)題的基礎(chǔ)上建立的，即消息不會(huì)被篡改（因?yàn)榉植际酱蠖嘣诰钟蚓W(wǎng)中）猿诸。
