前言
Paxos 算法如同我們標題大圖：世界上只有一種一致性算法哭靖，就是 Paxos。出自一位 google 大神之口。
同時希坚，Paxos 也是出名的晦澀難懂，推理過程極其復雜陵且。樓主在嘗試理解 Paxos 算法的過程中歷經(jīng)挫折裁僧。
今天，樓主不會講推理過程慕购，因為就算是嘗試使用大白話來講聊疲，也非常的難懂。當然更不會講數(shù)學公式沪悲。
而是從一個普通 Java 程序員的角度來理解 Paxos 算法获洲。
1. 什么是 Paxos 算法
Paxos 算法由圖靈獎獲得者 Leslie Lamport 于 1990 年提出的一種基于消息傳遞且具有高度容錯的特性的一致性算法。
來看看大師的樣貌：
標準的程序員殿如。贡珊。。涉馁。
Paxos 有點類似我們之前說的 2PC门岔，3PC，但是解決了他們倆的各種硬傷烤送。該算法在很多大廠都得到了工程實踐寒随，比如阿里的 OceanBase 的分布式數(shù)據(jù)庫，底層就是使用的 paxos 算法胯努。再比如 Google 的 chubby 分布式鎖也是用的這個算法牢裳。可見該算法在分布式系統(tǒng)中的地位叶沛，甚至于蒲讯，paxos 就是分布式一致性的代名詞。
2. Paxos 解決了什么問題
那么它解決了什么問題呢灰署？
答：解決了一致性問題判帮。
什么是 consensus （一致性）問題？
在一個分布式系統(tǒng)中溉箕，有一組的 process晦墙，每個 process 都可以提出一個 value，consensus 算法就是用來從這些 values 里選定一個最終 value肴茄。如果沒有 value 被提出來晌畅，那么就沒有 value 被選中；如果有1個 value 被選中寡痰，那么所有的 process 都應該被通知到抗楔。
我們假設一種情況棋凳，在一個集群環(huán)境中，要求所有機器上的狀態(tài)是一致的连躏，其中有2臺機器想修改某個狀態(tài)剩岳，機器 A 想把狀態(tài)改為 A，機器 B 想把狀態(tài)改為 B入热，那么到底聽誰的呢拍棕？
有人說，可以像 2PC勺良，3PC 一樣引入一個協(xié)調(diào)者绰播，誰先到，聽誰的尚困。
但是如果幅垮，協(xié)調(diào)者宕機了呢？
所以需要對協(xié)調(diào)者也做備份尾组，也要做集群。這時候示弓，問題來了讳侨，這么多協(xié)調(diào)者，聽誰的呢奏属？
Paxos 算法就是為了解決這個問題而生的？缈纭！囱皿！ 牛不勇婴？
下面，樓主會嘗試用自己的語言配合圖嘱腥，來解釋使用 Paxos 算法來解決這樣一個類似問題的過程耕渴。如果解釋的不好，還請見諒齿兔。但樓主不會去寫任何的算法推導過程橱脸，如果各位想看，文末有 Paxos 論文鏈接分苇，和很多大牛寫的推導過程添诉。
開始吧！
3. Paxos 例子說明
樓主這個例子來自中文維基百科医寿，但樓主為了形象化栏赴，輔以圖片解釋，但愿不會讓人更迷糊靖秩。
例子：
在 Paxos 島上须眷，有A1, A2, A3, A4, A5 5位議員竖瘾，就稅率問題進行決議。我們假設幾個場景來解釋：
場景 1.
假設 A1 說：稅率應該是 10%柒爸。而此時只有他一個人提這個建議准浴。如下圖：
很完美，沒有任何人和他競爭提案捎稚，他的這個提案毫無阻撓的通過了乐横。A2 - A5 都會回應他：我們收到了你的提案，等待最終的批準今野。而 A1 在收到 2 份回復后葡公，就可以發(fā)布最終的決議：稅率定位 10%，不用再討論了条霜。
這里有個注意的地方就是：為什么收到了 2 份回復就可以確定提案了呢萝嘁？
答：因為包括他自己，就達到 3 個人了链瓦，少數(shù)服從多數(shù)茄螃。
如果各位聽說過鴿籠原理/抽屜原理，就明白個大概了拆内。有人說旋圆，鴿籠原理/抽屜原理就是 Paxos 的核心思想。
場景 2：
現(xiàn)在我們假設在 A1 提出 10% 稅率提案的同時, A5 決定將稅率定為 20%麸恍，如果這個提案要通過侍從送到其他議員的案頭灵巧，A1 的草案將由 4 位侍從送到 A2-A5 那里。但是侍從不靠譜（代表分布式環(huán)境不靠譜）抹沪，負責 A2 和 A3 的侍從順利送達刻肄，而負責 A4 和 A5 的侍從則開溜了！
而 A5 的草案則送到了 A4 和 A3 的手中融欧。
現(xiàn)在敏弃，A1 ，A2蹬癌，A3 收到了 A1 的提案权她，A3，A4逝薪， A5 收到 A5 的提案隅要，按照 Paxos 的協(xié)議，A1董济，A2步清，A4，A5 4個侍從將接受他們的提案，侍從拿著回復：我已收到你的提案廓啊，等待最終批準 回到提案者那里欢搜。
而 A3 的行為將決定批準哪一個。
當 A3 同時收到了 A1 和 A5 的請求谴轮，該如何抉擇呢炒瘟？不同的抉擇將會導致不同的結果。
有 3 種情況第步，我們分析一下：
場景2：情況一
假設 A1 的提案先送到 A3 那里疮装，并且 A3 接受了該提案并回復了侍從。這樣粘都，A1 加上 A2 加上 A3廓推，構成了多數(shù)派，成功確定了稅率為 10%翩隧。 而 A5 的侍從由于路上喝酒喝多了樊展，晚到了一天，等他到了堆生，稅率已經(jīng)確定了专缠，A3 回復 A5：兄弟，你來的太晚了淑仆，稅率已經(jīng)定好了藤肢，不用折騰了，聽 A1 的吧糯景。
如下圖：
場景2：情況二
依然假設 A1 的提案先送到 A3 處，但是這次 A5 的侍從不是放假了省骂，只是中途耽擱了一會蟀淮。這次, A3 依然會將"接受"回復給 A1 .但是在決議成型之前它又收到了 A5 的提案。這時協(xié)議根據(jù) A5 的身份地位有兩種處理方式钞澳，但結果相同怠惶。
- 當 A5 地位很高，例如 CEO轧粟，就回復 A5：
我已收到您的提案策治，等待最終批準，但是您之前有人提出將稅率定為10%,請明察兰吟。 - 當 A5 沒地位通惫，普通碼農(nóng)一個，直接不回復混蔼。等待 A1 廣播：
稅率定為 10% 啦Ｂ囊浮！！
如下圖：
場景2：情況三
在這個情況中遵湖，我們將看見悔政，根據(jù)提案的時間及提案者的權勢決定是否應答是有意義的。在這里延旧，時間和提案者的權勢就構成了給提案編號的依據(jù)谋国。這樣的編號符合"任何兩個提案之間構成偏序"的要求。
A1 和 A5 同樣提出上述提案迁沫，這時 A1 可以正常聯(lián)系 A2 和 A3芦瘾，A5 也可以正常聯(lián)系這兩個人。這次 A2 先收到 A1 的提案; A3 則先收到 A5 的提案弯洗。而 A5 更有地位旅急。
在這種情況下，已經(jīng)回答 A1 的 A2 發(fā)現(xiàn)有比 A1 更有權勢的 A5 提出了稅率 20% 的新提案牡整，于是回復A5說：我已收到您的提案藐吮，等待最終批準。
而回復 A5 的 A3 發(fā)現(xiàn)新的提案者A1是個小人物逃贝，沒地位不予應答谣辞。
此時，A5 得到了 A2沐扳，A3 的回復泥从，于是 A5 說：稅率定為 20%，別再討論了沪摄。
那 A4 呢躯嫉？ A4 由于睡過頭了，迷迷糊糊的說：現(xiàn)有的稅率是什么? 如果沒有決定杨拐，則建議將其定為 15%.
這個時候祈餐，其他的議員就告訴他：哥們，已經(jīng)定為 20% 了哄陶，別折騰了帆阳。洗洗繼續(xù)睡吧。
整個過程如下圖：
4. 總結
從上面的例子可以看出：這個 Paxos 協(xié)議/算法 就是少數(shù)服從多數(shù)屋吨，標準的 鴿籠原理/抽屜原理蜒谤，同時，還會根據(jù)議員的身份來判斷是否需要應答至扰，這個身份其實就是一個編號鳍徽，是為了防止出現(xiàn)活性導致死循環(huán)。
注意：這一切都是在沒有 拜占庭將軍 問題的基礎上建立的敢课，即消息不會被篡改（因為分布式大多在局域網(wǎng)中）旬盯。
Paxos 的目標：保證最終有一個提案會被選定，當提案被選定后，其他議員最終也能獲取到被選定的提案胖翰。
Paxos 協(xié)議用來解決的問題可以用一句話來簡化： 將所有節(jié)點都寫入同一個值接剩，且被寫入后不再更改。
引用
如何淺顯易懂地解說 Paxos 的算法萨咳？
圖解 Paxos 一致性協(xié)議
分布式系列文章——Paxos算法原理與推導
Paxos算法 維基百科懊缺，自由的百科全書
Paxos Made Simple【翻譯】
The Part-Time Parliament(Paxos算法中文翻譯)
