前言
Paxos 算法如同我們標(biāo)題大圖：世界上只有一種一致性算法，就是 Paxos。出自一位 google 大神之口。
同時，Paxos 也是出名的晦澀難懂，推理過程極其復(fù)雜。樓主在嘗試?yán)斫?Paxos 算法的過程中歷經(jīng)挫折。
今天，樓主不會講推理過程，因?yàn)榫退闶菄L試使用大白話來講，也非常的難懂。當(dāng)然更不會講數(shù)學(xué)公式。
而是從一個普通 Java 程序員的角度來理解 Paxos 算法。
1. 什么是 Paxos 算法
Paxos 算法由圖靈獎獲得者 Leslie Lamport 于 1990 年提出的一種基于消息傳遞且具有高度容錯的特性的一致性算法。
來看看大師的樣貌：
標(biāo)準(zhǔn)的程序員。。。。
Paxos 有點(diǎn)類似我們之前說的 2PC，3PC，但是解決了他們倆的各種硬傷。該算法在很多大廠都得到了工程實(shí)踐，比如阿里的 OceanBase 的分布式數(shù)據(jù)庫，底層就是使用的 paxos 算法。再比如 Google 的 chubby 分布式鎖也是用的這個算法?？梢娫撍惴ㄔ诜植际较到y(tǒng)中的地位，甚至于，paxos 就是分布式一致性的代名詞。
2. Paxos 解決了什么問題
那么它解決了什么問題呢？
答：解決了一致性問題。
什么是 consensus （一致性）問題？
在一個分布式系統(tǒng)中，有一組的 process，每個 process 都可以提出一個 value，consensus 算法就是用來從這些 values 里選定一個最終 value。如果沒有 value 被提出來，那么就沒有 value 被選中；如果有1個 value 被選中，那么所有的 process 都應(yīng)該被通知到。
我們假設(shè)一種情況，在一個集群環(huán)境中，要求所有機(jī)器上的狀態(tài)是一致的，其中有2臺機(jī)器想修改某個狀態(tài)，機(jī)器 A 想把狀態(tài)改為 A，機(jī)器 B 想把狀態(tài)改為 B，那么到底聽誰的呢？
有人說，可以像 2PC，3PC 一樣引入一個協(xié)調(diào)者，誰先到，聽誰的。
但是如果，協(xié)調(diào)者宕機(jī)了呢？
所以需要對協(xié)調(diào)者也做備份，也要做集群。這時候，問題來了，這么多協(xié)調(diào)者，聽誰的呢？
Paxos 算法就是為了解決這個問題而生的?。?！ 牛不？
下面，樓主會嘗試用自己的語言配合圖，來解釋使用 Paxos 算法來解決這樣一個類似問題的過程。如果解釋的不好，還請見諒。但樓主不會去寫任何的算法推導(dǎo)過程，如果各位想看，文末有 Paxos 論文鏈接，和很多大牛寫的推導(dǎo)過程。
開始吧！
3. Paxos 例子說明
樓主這個例子來自中文維基百科，但樓主為了形象化，輔以圖片解釋，但愿不會讓人更迷糊。
例子：
在 Paxos 島上，有A1, A2, A3, A4, A5 5位議員，就稅率問題進(jìn)行決議。我們假設(shè)幾個場景來解釋：
場景 1.
假設(shè) A1 說：稅率應(yīng)該是 10%。而此時只有他一個人提這個建議。如下圖：
很完美，沒有任何人和他競爭提案，他的這個提案毫無阻撓的通過了。A2 - A5 都會回應(yīng)他：我們收到了你的提案，等待最終的批準(zhǔn)。而 A1 在收到 2 份回復(fù)后，就可以發(fā)布最終的決議：稅率定位 10%，不用再討論了。
這里有個注意的地方就是：為什么收到了 2 份回復(fù)就可以確定提案了呢？
答：因?yàn)榘ㄋ约?，就達(dá)到 3 個人了，少數(shù)服從多數(shù)。
如果各位聽說過鴿籠原理/抽屜原理，就明白個大概了。有人說，鴿籠原理/抽屜原理就是 Paxos 的核心思想。
場景 2：
現(xiàn)在我們假設(shè)在 A1 提出 10% 稅率提案的同時, A5 決定將稅率定為 20%，如果這個提案要通過侍從送到其他議員的案頭，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個侍從將接受他們的提案，侍從拿著回復(fù)：我已收到你的提案，等待最終批準(zhǔn) 回到提案者那里。
而 A3 的行為將決定批準(zhǔn)哪一個。
當(dāng) A3 同時收到了 A1 和 A5 的請求，該如何抉擇呢？不同的抉擇將會導(dǎo)致不同的結(jié)果。
有 3 種情況，我們分析一下：
場景2：情況一
假設(shè) A1 的提案先送到 A3 那里，并且 A3 接受了該提案并回復(fù)了侍從。這樣，A1 加上 A2 加上 A3，構(gòu)成了多數(shù)派，成功確定了稅率為 10%。 而 A5 的侍從由于路上喝酒喝多了，晚到了一天，等他到了，稅率已經(jīng)確定了，A3 回復(fù) A5：兄弟，你來的太晚了，稅率已經(jīng)定好了，不用折騰了，聽 A1 的吧。
如下圖：
場景2：情況二
依然假設(shè) A1 的提案先送到 A3 處，但是這次 A5 的侍從不是放假了，只是中途耽擱了一會。這次, A3 依然會將"接受"回復(fù)給 A1 .但是在決議成型之前它又收到了 A5 的提案。這時協(xié)議根據(jù) A5 的身份地位有兩種處理方式，但結(jié)果相同。
- 當(dāng) A5 地位很高，例如 CEO，就回復(fù) A5：
我已收到您的提案，等待最終批準(zhǔn)，但是您之前有人提出將稅率定為10%,請明察。 - 當(dāng) A5 沒地位，普通碼農(nóng)一個，直接不回復(fù)。等待 A1 廣播：
稅率定為 10% 啦?。?！
如下圖：
場景2：情況三
在這個情況中，我們將看見，根據(jù)提案的時間及提案者的權(quán)勢決定是否應(yīng)答是有意義的。在這里，時間和提案者的權(quán)勢就構(gòu)成了給提案編號的依據(jù)。這樣的編號符合"任何兩個提案之間構(gòu)成偏序"的要求。
A1 和 A5 同樣提出上述提案，這時 A1 可以正常聯(lián)系 A2 和 A3，A5 也可以正常聯(lián)系這兩個人。這次 A2 先收到 A1 的提案; A3 則先收到 A5 的提案。而 A5 更有地位。
在這種情況下，已經(jīng)回答 A1 的 A2 發(fā)現(xiàn)有比 A1 更有權(quán)勢的 A5 提出了稅率 20% 的新提案，于是回復(fù)A5說：我已收到您的提案，等待最終批準(zhǔn)。
而回復(fù) A5 的 A3 發(fā)現(xiàn)新的提案者A1是個小人物，沒地位不予應(yīng)答。
此時，A5 得到了 A2，A3 的回復(fù)，于是 A5 說：稅率定為 20%，別再討論了。
那 A4 呢？ A4 由于睡過頭了，迷迷糊糊的說：現(xiàn)有的稅率是什么? 如果沒有決定，則建議將其定為 15%.
這個時候，其他的議員就告訴他：哥們，已經(jīng)定為 20% 了，別折騰了。洗洗繼續(xù)睡吧。
整個過程如下圖：
4. 總結(jié)
從上面的例子可以看出：這個 Paxos 協(xié)議/算法 就是少數(shù)服從多數(shù)，標(biāo)準(zhǔn)的 鴿籠原理/抽屜原理，同時，還會根據(jù)議員的身份來判斷是否需要應(yīng)答，這個身份其實(shí)就是一個編號，是為了防止出現(xiàn)活性導(dǎo)致死循環(huán)。
注意：這一切都是在沒有 拜占庭將軍 問題的基礎(chǔ)上建立的，即消息不會被篡改（因?yàn)榉植际酱蠖嘣诰钟蚓W(wǎng)中）。
Paxos 的目標(biāo)：保證最終有一個提案會被選定，當(dāng)提案被選定后，其他議員最終也能獲取到被選定的提案。
Paxos 協(xié)議用來解決的問題可以用一句話來簡化： 將所有節(jié)點(diǎn)都寫入同一個值，且被寫入后不再更改。
引用
如何淺顯易懂地解說 Paxos 的算法？
圖解 Paxos 一致性協(xié)議
分布式系列文章——Paxos算法原理與推導(dǎo)
Paxos算法 維基百科，自由的百科全書
Paxos Made Simple【翻譯】
The Part-Time Parliament(Paxos算法中文翻譯)
