分布式-分布式理论
應用發展
單體應用架構
在企業發展的初期，一般公司的網站流量都比較小，只需要一個應用，將所有的功能代碼打包成一個服務，部署到服務器上就能支撐公司的業務。這樣也能夠減少開發、部署和維護的成本。
這種架構特點有其優點：
架構簡單，項目開發和維護成本低。所有項目模塊部署到一起，對于小型項目來說，維護方便。
垂直應用架構
垂直應用架構，就是將原來一個項目應用進行拆分，將其拆分為互不想干的幾個應用，以此來提升系統的整體性能。
這種架構的優點：
- 系統進行了拆分，可根據不同系統的訪問情況，有針對性的進行優化。
- 能夠實現應用的水平擴展。
- 各系統能夠分擔整體訪問的流量，解決了并發問題。
- 一個系統發生了故障，不應用其他系統的運行情況，提高了整體的容錯率。?
?這種架構的缺點：
- 拆分后的各系統之間相對比較獨立，無法進行互相調用。
- 各系統難免存在重疊的業務，會存在重復開發的業務，后期維護比較困難。
分布式架構
? ? ? ?我們將系統演變為垂直應用架構之后，當垂直應用越來越多，重復編寫的業務代碼就會越來越多。此時，我們需要將重復的代碼抽象出來，形成統一的服務供其他系統或者業務模塊來進行調用。此時，系統就會演變為分布式架構。
? ? ? ?在分布式架構中，我們會將系統整體拆分為服務層和表現層。服務層封裝了具體的業務邏輯供表現層調用，表現層則負責處理與頁面的交互操作。
這種架構的優點：
- 將重復的業務代碼抽象出來，形成公共的訪問服務，提高了代碼的復用性。
- 可以有針對性的對系統和服務進行性能優化，以提升整體的訪問性能。
這種架構的缺點：?
- 系統之間的耦合度變高，調用關系變得復雜，難以維護。
SOA架構
? ? ? 在分布式架構下，當部署的服務越來越多，重復的代碼就會越來越多，對于容量的評估，小服務資源的浪費等問題比較嚴重。此時，我們就需要增加一個統一的調度中心來對集群進行實時管理。此時，系統就會演變為SOA（面向服務）的架構。
這種架構的優點：?
- 使用注冊中心解決了各個服務之間的服務依賴和調用關系的自動注冊與發現。
這種架構的缺點：
- 各服務之間存在依賴關系，如果某個服務出現故障可能會造成服務的雪崩（關于穿透、擊穿和雪崩的問題。
- 服務之間的依賴與調用關系復雜，測試部署的困難比較大。
微服務架構
? ? ? 隨著業務的發展，我們在SOA架構的基礎上進一步擴展，將其徹底拆分為微服務架構。在微服務架構下，我們將一個大的項目拆分為一個個小的可以獨立部署的微服務，每個微服務都有自己的數據庫。
這種架構的優點：
- 服務徹底拆分，各服務獨立打包、獨立部署和獨立升級
- 每個微服務負責的業務比較清晰，利于后期擴展和維護。
- 微服務之間可以采用REST和RPC協議進行通信。
這種架構的缺點：
- 開發的成本比較高。涉及到各服務的容錯性問題。涉及到數據的一致性問題。涉及到分布式事務問題
分布式理論
分布式理論(一) - CAP定理
CAP的定義
Consistency (一致性)：
“all nodes see the same data at the same time”,即更新操作成功并返回客戶端后，所有節點在同一時間的數據完全一致，這就是分布式的一致性。一致性的問題在并發系統中不可避免，對于客戶端來說，一致性指的是并發訪問時更新過的數據如何獲取的問題。從服務端來看，則是更新如何復制分布到整個系統，以保證數據最終一致。
Availability (可用性):
可用性指“Reads and writes always succeed”，即服務一直可用，而且是正常響應時間。好的可用性主要是指系統能夠很好的為用戶服務，不出現用戶操作失敗或者訪問超時等用戶體驗不好的情況。
Partition Tolerance (分區容錯性):
即分布式系統在遇到某節點或網絡分區故障的時候，仍然能夠對外提供滿足一致性或可用性的服務。
分區容錯性要求能夠使應用雖然是一個分布式系統，而看上去卻好像是在一個可以運轉正常的整體。比如現在的分布式系統中有某一個或者幾個機器宕掉了，其他剩下的機器還能夠正常運轉滿足系統需求，對于用戶而言并沒有什么體驗上的影響。
CA?- 單點集群，滿足一致性，可用性的系統，通常在可擴展性上不太強大。
CP- 滿足一致性，分區容忍必的系統，通常性能不是特別高。
AP?- 滿足可用性，分區容忍性的系統，通常可能對一致性要求低一些。
?CAP定理的證明
現在我們就來證明一下，為什么不能同時滿足三個特性？
? ? ? ?假設有兩臺服務器，一臺放著應用A和數據庫V，一臺放著應用B和數據庫V，他們之間的網絡可以互通，也就相當于分布式系統的兩個部分。
? ? ? ?在滿足一致性的時候，兩臺服務器 N1和N2，一開始兩臺服務器的數據是一樣的，DB0=DB0。在滿足可用性的時候，用戶不管是請求N1或者N2，都會得到立即響應。在滿足分區容錯性的情況下，N1和N2有任何一方宕機，或者網絡不通的時候，都不會影響N1和N2彼此之間的正常運作。?
? ? ? 當用戶通過N1中的A應用請求數據更新到服務器DB0后，這時N1中的服務器DB0變為DB1，通過分布式系統的數據同步更新操作，N2服務器中的數據庫V0也更新為了DB1，這時，用戶通過B向數據庫發起請求得到的數據就是即時更新后的數據DB1。?
? ? 上面是正常運作的情況，但分布式系統中，最大的問題就是網絡傳輸問題，現在假設一種極端情況，N1和N2之間的網絡斷開了，但我們仍要支持這種網絡異常，也就是滿足分區容錯性，那么這樣能不能同時滿足一致性和可用性呢？
? ? 假設N1和N2之間通信的時候網絡突然出現故障，有用戶向N1發送數據更新請求，那N1中的數據DB0將被更新為DB1，由于網絡是斷開的，N2中的數據庫仍舊是DB0；
? ? ?如果這個時候，有用戶向N2發送數據讀取請求，由于數據還沒有進行同步，應用程序沒辦法立即給用戶返回最新的數據DB1，怎么辦呢？有二種選擇，第一，犧牲數據一致性，響應舊的數據DB0給用戶；第二，犧牲可用性，阻塞等待，直到網絡連接恢復，數據更新操作完成之后，再給用戶響應最新的數據DB1。?
? ? 上面的過程比較簡單，但也說明了要滿足分區容錯性的分布式系統，只能在一致性和可用性兩者中，選擇其中一個。也就是說分布式系統不可能同時滿足三個特性。這就需要我們在搭建系統時進行取舍了，那么，怎么取舍才是更好的策略呢?
取舍策略
CAP三個特性只能滿足其中兩個，那么取舍的策略就共有三種：
CA without P：如果不要求P（不允許分區），則C（強一致性）和A（可用性）是可以保證的。但放棄P的同時也就意味著放棄了系統的擴展性，也就是分布式節點受限，沒辦法部署子節點，這是違背分布式系統設計的初衷的。
CP without A：如果不要求A（可用），相當于每個請求都需要在服務器之間保持強一致，而P（分區）會導致同步時間無限延長(也就是等待數據同步完才能正常訪問服務)，一旦發生網絡故障或者消息丟失等情況，就要犧牲用戶的體驗，等待所有數據全部一致了之后再讓用戶訪問系統。設計成CP的系統其實不少，最典型的就是分布式數據庫，如Redis、HBase等。對于這些分布式數據庫來說，數據的一致性是最基本的要求，因為如果連這個標準都達不到，那么直接采用關系型數據庫就好，沒必要再浪費資源來部署分布式數據庫。
?AP wihtout C：要高可用并允許分區，則需放棄一致性。一旦分區發生，節點之間可能會失去聯系，為了高可用，每個節點只能用本地數據提供服務，而這樣會導致全局數據的不一致性。典型的應用就如某米的搶購手機場景，可能前幾秒你瀏覽商品的時候頁面提示是有庫存的，當你選擇完商品準備下單的時候，系統提示你下單失敗，商品已售完。這其實就是先在?A（可用性）方面保證系統可以正常的服務，然后在數據的一致性方面做了些犧牲，雖然多少會影響一些用戶體驗，但也不至于造成用戶購物流程的嚴重阻塞。
分布式理論(二) - BASE理論
BASE 思想中的 BA（Basically Available）基本可用
是鼓勵通過預先的架構設計或者前期規劃，盡量在分布式的系統中，把以前可能影響全平臺的嚴重問題，變成只會影響平臺中的一部分數據或者功能的非嚴重問題。
在了解BASE理論的時候先說說 2PC（兩階段提交）方案
2PC（兩階段提交）方案，這個方案本身能保證在數據庫切分的情況下，原來的事務依然保留著自身的 ACID 性質。即:
Atomicity（原子性），不管事務里執行多少命令，對外它們都是一體的，要么都執行，要么都不執行。
Consistency（一致性），正因為事務里要么做要么都不做，所以數據庫的狀態變化只能由事務變更后，才會叫一致性狀態。
Isolation（隔離性），事務里做的事兒事務外面誰也看不到，就跟個盒子把數據罩起來一樣，到底中間怎么變化的，事務外面的觀察不到。
Durability（持久性），事務確認成功了，那這狀態就永久不變了。
但也正因為這 4 個特性，2PC才有一定的問題
- 首先，數據庫拆分了，那么根據事務的原子性，事務自身必須是一體的，那么事務涉及到的不同的數據庫就必須都訪問一遍，而這本身就意味著很高的通信成本。
再加上，為了保持一致性，事務失敗后，還必須恢復各個數據庫原來的狀態，這就必須讓已經成功執行過本地事務的數據庫全部回滾。
而稍微懂點數據庫的人都知道，這個成本有多大。
- 數據庫的拆分會造成整個平臺的可用性下降。?
- coordinator如果在發起提議后宕機，那么participant將進入阻塞(block)狀態、一直等待coordinator回應以完成該次決議。這時需要另一角色把系統從不可結束的狀態中帶出來，我們把新增的這一角色叫協調者備份(coordinator watchdog)。coordinator宕機一定時間后，watchdog接替原coordinator工作，通過問詢(query) 各participant的狀態，決定階段2是提交還是中止。這也要求?coordinator/participant 記錄(logging)歷史狀態，以備coordinator宕機后watchdog對participant查詢、coordinator宕機恢復后重新找回狀態。
- 從coordinator接收到一次事務請求、發起提議到事務完成，經過2PC協議后增加了2次RTT(propose+commit)，帶來的時延(latency)增加相對較少。 ?
假設我現在有一臺數據庫，它的可用性是 99.9%。如果因為分庫，數據庫從一臺變成兩臺，那么平臺的可用性就會變成：
平臺的可用性 = 99.9% * 99.9% = 99.8%
從 99.9% 變成了 99.8%，這意味著可用性下降了 0.1%，每個月的不可用時間會增加 43 分鐘之多。
一邊是硬件升級已經到頂，單機數據庫也優化到了極限，再不做數據庫拆分，平臺可能隨時癱瘓。一邊是沒有好的策略，可能拆分數據庫后，每個月都有宕機的風險，同時性能也可能會出現劇烈的下降。
?由于上面的問題，我們在聊聊 BASE理論
用廣告平臺舉例
從業務上，要求廣告的訪問數據都要保證及時入庫不能丟，因為丟了就可能造成計費的損失，而這些損失全是錢。所以，每當用戶點擊廣告或者廣告展示出來的時候，為了保證不丟失，這些數據都是實時入庫的。
又根據業務需求，當廣告流量入庫時，還需要往廣告預算表和媒體流水表里同時根據這筆流量進行記賬，以供后續財務計算。
如果完全不考慮事務，則拆分庫后，操作可能會是這個樣子。
?
這三個操作可能會并行發往不同的數據庫執行。由于三個操作之間沒有事務的約束，所以，一個操作出問題了，另外的操作并不會受到影響。
而這卻也引發了另外一個問題，數據狀態不一致。
如果在上面的業務中，插入廣告流量表的操作失敗了，但其余兩張表插入成功了，業務就會面臨一個很尷尬的情況：他們算出的財務報表沒有依據。財務流水中找不到產生了這筆流水的依據。
而這種不一致的狀態由于已經被持久化到了數據庫中，就會導致這種不一致的狀態永久存在了數據庫中。這業務能接受嗎？但凡有點職業精神的程序員能接受嗎？
要有折中的辦法！！！
現在再回過頭來看看 2PC 的問題。假設 2PC 的實現是一步步執行的（當然，不管是一步一步還是異步并發，他們總是要確保大家要么一起成功要么一起失敗的。
所以，即使并發操作，也不會節省多少性能，因為短板在執行最慢的那條語句上。如果執行我們上面的事務需要幾步呢？
假如現在要執行事務 A：
協調器發出事務 A 中的第一條語句 Insert into 流量表
協調器等待結果
協調器發出事務 A 中的第二條語句 Insert into 預算表
協調器等待結果
協調器發出事務 A 中的第三條語句 Insert into 流水表
協調器等待結果
如果中間有失敗的，協調器還需要做額外的操作：
協調器告訴事務 A 中第一條語句做回滾操作
協調器等待結果
協調器告訴事務 A 中第二條語句做回滾操作
協調器等待結果
協調器告訴事務 A 中第三條語句做回滾操作
協調器等待結果
這簡直是讓人窒息的操作步驟了。如果有一種方法既能節省步驟又能節省事務執行時間該有多好啊。
嗯……我只能說當時的自己實在是長得丑卻想的美。
世上尚不存在這種方法的。但是，世上還存在另外的解決此類事情的方式：
異步處理，時間分攤
我們分析下關于插入廣告流量這塊兒的業務。你會發現一個神奇的現象，即廣告流量表中的數據才是核心，而預算表和流水表統統都是廣告流量表中數據的一種緩存而已。
如果，嗯，我是說如果有這么一種辦法，即我們先把廣告流量數據插入數據庫，成功以后，再把以廣告流量數據作為根基的附屬操作（這里是插入預算表和流水表）放到一個地方持久化。然后，我們再從那個存放附屬操作的地方把操作信息取出來，專門對這些操作信息進行處理。
而這種處理方式可能會非常靈活，要么可以對這些操作信息進行批量處理，要么可以對他們異步的在后臺處理。處理這些操作信息成功以后，再把以前持久化好的操作信息給刪除。
整個方法實施下來，相當于把應該在 A 時刻在前臺阻塞著花 3 秒處理業務的操作，變成了在 A 時刻前臺花 1 秒，然后在 B 時刻后臺花 2 秒處理業務的操作，這不也可以變相的達到我們想節省步驟和事務執行時間的目標了嗎？
這真的是一個好的思路啊，還記得當時的自己想到這個思路的時候，忍不住在內心大喊了起來：“那個存附屬操作信息的地方就是 MQ 啊。用 MQ，MQ 就能做這件事情。”
那么就一起來看下 MQ 是如何幫我解決這個大難題的吧，針對上面的廣告流量詳情的業務，我們用了 MQ 之后會有如下的步驟：
執行 Insert into 流量表語句
等待結果
發消息到 MQ 里，內容為 Insert into 預算表
等待 MQ 持久化成功
發消息到 MQ 里，內容為 Insert into 流水表
等待 MQ 持久化成功
如果發給 MQ 消息失敗：
可以降級寫到本地日志中
OK那么這改進后的方法是怎么提升性能的呢？
-
首先，我們發給 MQ 的消息可以批量發送；
-
其次，發給 MQ 并持久化消息要比數據庫執行一次事務快了一個數量級；
-
最后，失敗后，回滾操作成本降低了不止一個數量級。
這個方法本質上，在應用層其實就執行了一條語句而已，剩下的完全可以根據業務需求的不同，選擇處理 MQ 中的消息的方式。比如，處理消息既可以異步慢慢處理，也可以推遲一段時間后處理，更可以凌晨定時處理。
可以看到，使用 MQ 方案后，對廣告流量這個業務需求而言，其實，出現了一個中間狀態：廣告流量表有數據，但是以這條數據為基準的預算表和流水表暫時還沒有數據。
中間這個狀態此時是不滿足業務需求的。而這種狀態，在 BASE 理論中就被稱為：
軟狀態（Soft state）
至于廣告流量表當時沒有及時插入到預算表和流水表中的數據呢，它們最終也將會隨著后續對 MQ 消息的處理而被補充完整的。
而對于這種當時不符合業務需求的軟狀態，通過一些后續內部的自動化操作把數據狀態補充完整從而最終滿足業務需求的情況，在 BASE 理論中就被稱為了：
最終一致性（Eventually consistent）
由此，我通過不斷利用 BASE 理論中的軟狀態和最終一致性的思路，最終補上了平臺數據庫切分需要的最后一塊拼圖——平臺性能大提升。
再重復一次，BASE 理論本質上只是一種架構思想，它告訴人們世界上還存在著這么一些事情：
能通過巧妙地設計，通過局部輕微的損失減少全局嚴重的損失；
能通過一些解耦、異步、推遲執行、批量執行等技巧，構造出一種中間狀態，從而提高系統的整體性能；
平臺是為業務服務的，業務的核心是數據狀態，而數據狀態無論中間變成什么樣，最終還要恢復到它應該處于的正確狀態。
?3PC
3PC(three phase commit)即三階段提交，既然2PC可以在異步網絡+節點宕機恢復的模型下實現一致性，那還需要3PC做什么？
在2PC中一個participant的狀態只有它自己和coordinator知曉，假如coordinator提議后自身宕機，在watchdog啟用前一個participant又宕機，其他participant就會進入既不能回滾、又不能強制commit的阻塞狀態，直到participant宕機恢復。這引出兩個疑問：
能不能去掉阻塞，使系統可以在commit/abort前回滾(rollback)到決議發起前的初始狀態 當次決議中，participant間能不能相互知道對方的狀態，又或者participant間根本不依賴對方的狀態
圖片截取自wikipediacoordinator 接收完participant的反饋(vote)之后，進入階段2，給各個participant發送準備提交(prepare to commit)指令。participant接到準備提交指令后可以鎖資源，但要求相關操作必須可回滾。coordinator接收完確認(ACK)后進入階段3、進行commit/abort，3PC的階段3與2PC的階段2無異。協調者備份(coordinator watchdog)、狀態記錄(logging)同樣應用在3PC。 ? participant如果在不同階段宕機，我們來看看3PC如何應對：
- 階段1:?coordinator或watchdog未收到宕機participant的vote，直接中止事務；宕機的participant恢復后，讀取logging發現未發出贊成vote，自行中止該次事務
- 階段2:?coordinator未收到宕機participant的precommit ACK，但因為之前已經收到了宕機participant的贊成反饋(不然也不會進入到階段2)，coordinator進行commit；watchdog可以通過問詢其他participant獲得這些信息，過程同理；宕機的participant恢復后發現收到precommit或已經發出贊成vote，則自行commit該次事務
- 階段3: 即便coordinator或watchdog未收到宕機participant的commit ACK，也結束該次事務；宕機的participant恢復后發現收到commit或者precommit，也將自行commit該次事務
物理時鐘 vs 邏輯時鐘?
? ? ? 現實生活中時間是很重要的概念，時間可以記錄事情發生的時刻、比較事情發生的先后順序。分布式系統的一些場景也需要記錄和比較不同節點間事件發生的順序，但不同于日常生活使用物理時鐘記錄時間，分布式系統使用邏輯時鐘記錄事件順序關系，下面我們來看分布式系統中幾種常見的邏輯時鐘。
? ? ?可能有人會問，為什么分布式系統不使用物理時鐘(physical clock)記錄事件？每個事件對應打上一個時間戳，當需要比較順序的時候比較相應時間戳就好了。??
? ? ?這是因為現實生活中物理時間有統一的標準，而分布式系統中每個節點記錄的時間并不一樣，即使設置了 NTP 時間同步節點間也存在毫秒級別的偏差。因而分布式系統需要有另外的方法記錄事件順序關系，這就是邏輯時鐘(logical clock)。
Lamport timestamps
Leslie Lamport 在1978年提出邏輯時鐘的概念，并描述了一種邏輯時鐘的表示方法，這個方法被稱為Lamport時間戳(Lamport timestamps)。
分布式系統中按是否存在節點交互可分為三類事件，一類發生于節點內部，二是發送事件，三是接收事件。Lamport時間戳原理如下：
每個事件對應一個Lamport時間戳，初始值為0 如果事件在節點內發生，時間戳加1 如果事件屬于發送事件，時間戳加1并在消息中帶上該時間戳 如果事件屬于接收事件，時間戳 = Max(本地時間戳，消息中的時間戳) + 1
假設有事件a、b，C(a)、C(b)分別表示事件a、b對應的Lamport時間戳，如果C(a) < C(b)，則有a發生在b之前(happened before)，記作 a -> b，例如圖1中有 C1 -> B1。通過該定義，事件集中Lamport時間戳不等的事件可進行比較，我們獲得事件的偏序關系(partial order)。
如果C(a) = C(b)，那a、b事件的順序又是怎樣的？假設a、b分別在節點P、Q上發生，Pi、Qj分別表示我們給P、Q的編號，如果 C(a) = C(b) 并且 Pi < Qj，同樣定義為a發生在b之前，記作 a => b。假如我們對圖1的A、B、C分別編號Ai = 1、Bj = 2、Ck = 3，因 C(B4) = C(C3) 并且 Bj < Ck，則 B4 => C3。
通過以上定義，我們可以對所有事件排序、獲得事件的全序關系(total order)。上圖例子，我們可以從C1到A4進行排序。
Vector clock
Lamport時間戳幫助我們得到事件順序關系，但還有一種順序關系不能用Lamport時間戳很好地表示出來，那就是同時發生關系(concurrent)。例如圖1中事件B4和事件C3沒有因果關系，屬于同時發生事件，但Lamport時間戳定義兩者有先后順序。
Vector clock是在Lamport時間戳基礎上演進的另一種邏輯時鐘方法，它通過vector結構不但記錄本節點的Lamport時間戳，同時也記錄了其他節點的Lamport時間戳。Vector clock的原理與Lamport時間戳類似，使用圖例如下：
假設有事件a、b分別在節點P、Q上發生，Vector clock分別為Ta、Tb，如果 Tb[Q] > Ta[Q] 并且 Tb[P] >= Ta[P]，則a發生于b之前，記作 a -> b。到目前為止還和Lamport時間戳差別不大，那Vector clock怎么判別同時發生關系呢？
如果 Tb[Q] > Ta[Q] 并且 Tb[P] < Ta[P]，則認為a、b同時發生，記作 a <-> b。例如圖2中節點B上的第4個事件 (A:2，B:4，C:1) 與節點C上的第2個事件 (B:3，C:2) 沒有因果關系、屬于同時發生事件。
Version vector
基于Vector clock我們可以獲得任意兩個事件的順序關系，結果或為先后順序或為同時發生，識別事件順序在工程實踐中有很重要的引申應用，最常見的應用是發現數據沖突(detect conflict)。
分布式系統中數據一般存在多個副本(replication)，多個副本可能被同時更新，這會引起副本間數據不一致，Version vector的實現與Vector clock非常類似[8]，目的用于發現數據沖突。下面通過一個例子說明Version vector的用法：
- client端寫入數據，該請求被Sx處理并創建相應的vector ([Sx, 1])，記為數據D1
- 第2次請求也被Sx處理，數據修改為D2，vector修改為([Sx, 2])
- 第3、第4次請求分別被Sy、Sz處理，client端先讀取到D2，然后D3、D4被寫入Sy、Sz
- 第5次更新時client端讀取到D2、D3和D4 3個數據版本，通過類似Vector clock判斷同時發生關系的方法可判斷D3、D4存在數據沖突，最終通過一定方法解決數據沖突并寫入D5
Vector clock只用于發現數據沖突，不能解決數據沖突。如何解決數據沖突因場景而異，具體方法有以最后更新為準(last write win)，或將沖突的數據交給client由client端決定如何處理，或通過quorum決議事先避免數據沖突的情況發生。
由于記錄了所有數據在所有節點上的邏輯時鐘信息，Vector clock和Version vector在實際應用中可能面臨的一個問題是vector過大，用于數據管理的元數據(meta data)甚至大于數據本身。
解決該問題的方法是使用server id取代client id創建vector (因為server的數量相對client穩定)，或設定最大的size、如果超過該size值則淘汰最舊的vector信息。
以上介紹了分布式系統里邏輯時鐘的表示方法，通過Lamport timestamps可以建立事件的全序關系，通過Vector clock可以比較任意兩個事件的順序關系并且能表示無因果關系的事件，將Vector clock的方法用于發現數據版本沖突，于是有了Version vector。
Paxos協議?
算法過程
少數服從多數
首先要認識到，這是一個分布式系統下的共識算法，要解決的問題，簡化一點，就是一堆機器，每一臺都可能會收到客戶端的一條消息，那需要將自己收到的消息，告訴其他的機器，讓所有分布式系統中的機器，達到最終的一致，這就是達到共識。
Paxos采取了一個我們非常熟悉的達成共識的方法：少數服從多數。只要有超過一半的機器認可某一個消息，那么最終就所有機器都接受這條消息并將它作為本次的結論。而競選失敗的少數派消息，就會被拒絕，并由第一個從客戶端處接收到該消息的機器，向客戶端發送失敗結果，由客戶端進行重試，去嘗試在下一輪競選中勝出。
少數服從多數，說來簡單，如果是一群人的話，大家碰個頭一起舉手表決就好了。但是放到一個分布式系統中就變復雜了。機器之間怎么傳遞提議，怎么表決，怎么統計多數，網絡傳輸需要時間，在表決過程中，其他機器收到了新的消息怎么辦，都需要一整套機制來解決。
下面就來逐步講解Paxos的過程，但在講解過程之前，先說Paxos中最常見的兩種角色：
Proposer：提案者。也就是在選舉中提出提案的人，放到分布式系統里，就是接收到客戶端寫操作的人。一切行為都由Proposer提出提案開始，Paxos會將提案想要進行的操作，抽象為一個“value”，去在多臺機器中傳遞，最后被所有機器接受。
Acceptor：批準者。Acceptor從含義上來說就是除了當前Proposer以外的其他機器，他們之間完全平等和獨立，Proposer需要爭取超過半數（N/2+1）的Acceptor批準后，其提案才能通過，它倡導的“value”操作才能被所有機器所接受。
除了以上兩種角色，實際上Paxos還會提到Learner，即學習者這個角色，該角色是在達成決議時，對結論的學習者，也即是從其他節點“學習”最終提案內容，比較簡單。需要注意，這些角色只是在不同時間下，邏輯上的劃分，實際上任何一臺機器都可以充當這三個角色之一。
一個簡單的提案
先描述最簡單的情況，假設現在有四臺機器，其中一臺收到了來自客戶端的寫操作請求，需要同步給其他機器。
此時這臺收到請求的機器，我們稱它為Proposer，因為它將要開始將收到的請求，作為一個提案，提給其他的機器。這里為了方便，我們假設這個請求是要將一個地址設置為“深圳”，那么如下圖所示：
此時，其他的Acceptor都閑著呢，也沒其他人找，所以當它們收到Proposer的提案時，就直接投票了，說可以可以，我是空的，贊成提案（同意提議）：
?
到這里，就還是一個簡單的同步的故事，但需要注意的是，這里Proposer實際上是經歷了兩步的。?
在這個簡單的提案過程中，Proposer其實也經歷了兩個階段：
Prepare階段：Proposer告訴所有其他機器，我這里有一個提案（操作），想要你們投投票支持一下，想聽聽大家的意見。Acceptor看自己是NULL，也就是目前還沒有接受過其他的提案，就說我肯定支持。
Accept階段：Proposer收到其他機器的回復，說他們都是空的，也就是都可以支持接受Proposer的提案（操作），于是正式通知大家這個提案被集體通過了，可以生效了，操作就會被同步到所有機器正式生效。
兩個提案并發進行
現在考慮一個更復雜的場景，因為我們處于一個分布式的場景，每臺機器都可能會收到請求，那如果有兩臺機器同時收到了兩個客戶端的不同請求，該怎么處理呢？大家聽誰的呢？最后的共識以誰的為準呢？如下圖所示：
在這種情況下，由于網絡傳輸的時間問題，兩個Proposer的提案到達各個機器，是會存在先后順序的。假設Proposer 1的提案先達到了Acceptor 1和 Acceptor 2，而Proposer 2的提案先達到了Acceptor 3，其達到Acceptor 1和Acceptor 2時，由于機器已經投票給Proposer 1了，所以Proposer 2的提案遭到拒絕，Proposer 1達到Acceptor 3的時候同樣被拒。
Acceptor們迷了，Proposer們也迷了，到底應該接受誰？此時，還是遵循自由民主的法則——少數服從多數。
Proposer 1發現超過半數的Acceptor都接受了自己，所以放心大膽地發起要求，讓所有Acceptor都按照自己的值來操作。而Proposer 2發現只有不到半數的Acceptor支持自己，而有超過半數是支持Proposer 1的值的，因此只能拒絕Client 2，并將自己也改為Proposer 1的操作：
?
到此為止，看起來沒有問題，但是，這是因為恰好Acceptor的數量是單數，可以選出“大多數”，但是因為同時成為Proposer的機器數量是不確定的，因此是無法保證Acceptor的數量一定是單數的，如下面這種情況就無法選出“大多數”了：
?
這時，兩個Proposer有可能總是先搶到一個Acceptor的支持，然后在另一個Acceptor處折戟沉沙，算法就一直循環死鎖下去了。為了解決這種情況，Paxos給提案加了一個編號。
之前我們Proposer的提案都是只有操作內容的，現在我們給他加一個編號，即：
Proposer 1的提案為：[n1，v1]
Proposer 2的提案為：[n2，v2]
假設Proposer 1接到Clint 1的消息稍微早一點，那么它的編號就是1，Proposer 2的編號就是2，那么他們的提案實際就是：
Proposer 1的提案為：[1，{ Set Addr =“深圳”}]
Proposer 2的提案為：[2，{ Set Addr =“北京”}]
此時，Paxos加上一條規則：
Acceptor如果還沒有正式通過提案（即還沒有Accept使操作生效），就可以接受編號更大的Prepare請求。
所以，回到上面的困境
當Proposer 1想要向Acceptor 2尋求支持時，Acceptor 2一看你的編號（1）比我已經支持的編號（2）要小，拒絕拒絕。此時Proposer 1由于沒有得到過半數的支持，會重新尋求支持。
而當Proposer 2想要向Acceptor 1尋求支持時，Acceptor 1一看你的編號（2）比我已經支持的編號（1）要大，好的你是老大我聽你的。此時Proposer 2已經得到了超過半數的支持，可以進入正式生效的Accept階段了。
這里需要補充一下，Proposer 1這里支持提案失敗，他是怎么讓自己也接受Proposer 2的提案的呢？
所以這里的后續會發生的事情是：
Proposer 2發現得到了過半數的支持，開始向所有Acceptor發送Accept請求。
所有Acceptor接收到Accept請求后，按照之前Prepare時收到的信息與承諾，去生效Proposer 2的提案內容（即Set Addr=“北京”的操作）。
Proposer 1之前已經收到了所有Acceptor的回復，發現沒有得到過半數的支持，直接回復Client 1請求失敗，并變成一個Acceptor（或者說Learner），接受Proposer 2的Accept請求。
Proposer 1之前已經收到了所有Acceptor的回復，發現沒有得到過半數的支持，直接回復Client 1請求失敗，并變成一個Acceptor（或者說Learner），接受Proposer 2的Accept請求。
這里再想多一點，考慮另一種場景：假設Proposer 2的Accept請求先達到了Acceptor 2，然后Proposer 1向Acceptor 2發送的Prepare請求才到達 Acceptor 2，會發生什么呢？
最直觀的處理是，Acceptor 2直接拒絕，然后Proposer 1走上面的流程，但Paxos為了效率，又增加了另一條規則：
如果一個Prepare請求，到達Acceptor時，發現該Acceptor已經接受生效了另一個提案，那么它除了回復提案被拒絕外，還會帶上Acceptor已經通過的編號最大的那個提案的內容回到Proposer。Proposer收到帶內容的拒絕后，需要修改自己的提案為返回的內容。
此時會發生的事情就變成了：
此時Acceptor 2除了會拒絕它的請求，還會告訴Proposer 1，說我已經通過并生效了另一個編號為2的提案，內容是Set Addr=“北京”。
然后Proposer 1查看回復時，發現已經有Acceptor生效提案了，于是就修改自己的提案，也改為Set Addr=“北京”，并告知Client 1你的請求失敗了。
接著Proposer 1開始充當Proposer 2的小幫手，幫他一起傳播 Proposer 2的提案，加快達成共識的過程。
PS：這里需要注意， 編號是需要保證全局唯一的，而且是全局遞增的 ，否則在比較編號大小的時候就會出現問題，怎么保證編號唯一且遞增有很多方法，比如都向一個統一的編號生成器請求新編號；又比如每個機器的編號用機器ID拼接一個數字，該數字按一個比總機器數更大的數字間隔遞增。
一些異常情況
上面的規則是不是就能保證整個算法解決所有問題了呢？恐怕不是，這里再看看一些異常情況。
異常情況一：假設現在有三個Proposer同時收到客戶端的請求，那么他們會生成全局唯一的不同編號，帶著各自接收到的請求提案，去尋求Acceptor的支持。但假設他們都分別爭取到了一個Acceptor的支持，此時由于Prepare階段只會接受編號更大的提案，所以正常情況下只有Proposer 3的提案會得到所有Acceptor的支持。但假設這時候Proposer 3機器掛了，無法進行下一步的Accept了，怎么辦呢？那么所有Acceptor就會陷入持續的等待，而其他的Proposer也會一直重試然后一直失敗。
為了解決這個問題，Paxos決定，允許Proposer在提案遭到過半數的拒絕時，更新自己的提案編號，用新的更大的提案編號，去發起新的Prepare請求。
那么此時Proposer 1和Proposer 2就會更新自己的編號，從【1】與【2】，改為比如【4】和【5】，重新嘗試提案。這時即使Proposer 3機器掛了，沒有完成Accept，Acceptor也會由于接收到了編號更大的提案，從而覆蓋掉Proposer 3的提案，進入新的投票支持階段。
異常情況二：雖然更新編號是解決了上面的問題，但卻又引入了活鎖的問題。由于可以更新編號，那么有概率出現這種情況，即每個Proposer都在被拒絕時，增大自己的編號，然后每個Proposer在新的編號下又爭取到了小于半數的Acceptor，都無法進入Accept，又重新加大編號發起提案，一直這樣往復循環，就成了活鎖（和死鎖的區別是，他們的狀態一直在變化，嘗試解鎖，但還是被鎖住了）。
要解決活鎖的問題，有幾種常見的方法：
當Proposer接收到回復，發現支持它的Acceptor小于半數時，可以不立即更新編號重試，而是隨機延遲一小段時間，來錯開彼此的沖突。
可以設置一個Proposer的Leader，全部由它來進行提案，這即使共識算法的常見套路，選擇一個Leader。這需要進行Leader的選舉，以及解決存活性檢查以及換屆的問題。實際上就已經演變成Multi-Paxos了。
異常情況三：由于在提案時，Proposer都是根據是否得到超過半數的Acceptor的支持，來作為是否進入Accept階段的依據，那如果在算法進行中新增或下線了機器呢？如果此時一些Proposer知道機器數變了，一些Proposer不知道，那么大家對半數的判斷就會不一致，導致算法出錯。
因此在實際運行中，機器節點數的變動，也需要作為一條要達成共識的請求提案，通過Paxos算法本身，傳達到所有機器節點上。
為了使Paxos運行得更穩定，不需要時刻擔心是否有節點數變化，可以固定一個周期，要求只有在達到固定周期時才允許變更節點數，比如只有在經過十次客戶端請求的提案與接受后，才處理一次機器節點數變化的提案。
那如果這個間隔設置地相對過久，導致現在想要修改節點數時，一直要苦等提案數，怎么辦呢？畢竟有時候機器壞了是等不了的。那么可以支持主動填充空的提案數，來讓節點變更的提案盡早生效。
Paxos協議的兩階段
抽象和完善一下這個過程，就是：
Prepare準備階段：
在該階段，Proposer會嘗試告訴所有的其他機器，我現在有一個提案（操作），請告訴我你們是否支持（是否能接受）。其他機器會看看自己是否已經支持其他提案了（是否接受過其他操作請求），并回復給Proposer（如果曾經接受過其他值，就告訴Proposer接受過什么值/操作）；
Acceptor如果已經支持了編號N的提案，那么不會再支持編號小于N的提案，但可以支持編號更大的提案；
Acceptor如果生效了編號為N的提案，那么不會再接受編號小于N的提案，且會在回復時告知當前已生效的提案編號與內容。
Accept提交階段：
在該階段，Proposer根據上一階段接收到的回復，來決定行為；
如果上一階段超過半數的機器回復說接受提案，那么Proposer就正式通知所有機器去生效這個操作；
如果上一階段超過半數的機器回復說他們已經先接受了其他編號更大的提案，那么Proposer會更新一個更大的編號去重試（隨機延時）；
如果上一階段的機器回復說他們已經生效了其他編號的提案，那么Proposer就也只能接受這個其他人的提案，并告知所有機器直接接受這個新的提案；
如果上一階段都沒收到半數的機器回復，那么提案取消；
PS：接受其他提案，以及提案取消的情況下，Proposer就要直接告訴客戶端該次請求失敗了，等待客戶端重試即可。
這里可以看到，超過半數以上的機器是個很重要的決定結果走向的條件。至此，已經描述完了針對一次達成共識的過程，這被稱為Basic-Paxos。
那如果有多個值需要達成共識呢？
Multi-Paxos
如果有多個值要不斷地去針對一次次請求達成共識，使用Basic-Paxos也是可以的，無非就是一遍遍地執行算法取得共識并生效嘛，但在分布式系統下，容易由于多次的通信協程造成響應過慢的問題，何況還有活鎖問題存在。因此Lamport給出的解法是：
先選擇一個Leader來擔當Proposer的角色，取消多Proposer，只有一個Leader來提交提案，這樣就沒有了競爭（也沒有了活鎖）。同時，由于無需協商判斷，有了Leader后就可以取消Prepare階段，兩階段變一階段，提高效率。
對于每一次要確定的值/操作，使用唯一的一個標識來區分，保證其單調遞增即可。
對于選擇Leader的過程，簡單的做法很多，復雜的也只需要進行一次Basic-Paxos即可。選出Leader后，直到Leader掛掉或者到期，都可以保持由它來進行簡化的Paxos協議。
如果有多個機器節點都由于某些問題自認為自己是Leader，從而都提交了提案，也沒關系，可以令其退化成Basic-Paxos，也可以在發現后再次選擇Leader即可。
其他共識算法?ZAB&Raft
這里也順便對比一下另外兩種常見的共識算法：ZAB和Raft。
（一）ZAB
ZAB全稱是Zookeeper Atomic Broadcast，也就是Zookeeper的原子廣播，顧名思義是用于Zookeeper的。
ZAB理解起來很簡單，在協議中有兩種角色：
Leader節點：有任期的領導節點，負責作為與客戶端的連接點接受讀寫操作，然后將其廣播到其他節點去。
Follower節點：主要是跟隨領導節點的廣播消息進行同步，并關注領導節點的健康狀態，好隨時取而代之。
既然有Leader節點，就必然有Leader的選舉過程，ZAB的選舉，會先看各個節點所記錄的消息的時間戳（數據ID），時間戳（數據ID）越大，節點上的數據越新，就會優先被投票，如果數據ID比較不出來，就再看事先定義的節點的優先級（節點ID）。當大家根據上述優先級投票，超過半數去支持一個節點時，該節點就成為Leader節點了。
通過心跳算法可以共同檢查Leader節點的健康度，如果出現問題（比如機器下線、網絡分區、延遲過高等），就會考慮重新選舉。
可以看出，這種選舉方式相對Paxos是比較方便高效的，而且選出Leader節點后，就可以直接通過Leader節點接受消息進行廣播，而不需要進行兩階段提交。
其實ZAB就很像選出了Leader的Multi-Paxos，兩者的差異主要在選Leader的流程上。
（二）Raft
Raft的應用比Paxos要多，有人認為Raft是Multi-Paxos的改進，因為Raft的作者也曾研究過Paxos。既然Paxos是前輩，為什么應用的反而要少呢？這是因為Basic-Paxos相對比較耗時，而Multi-Paxos，作者并沒有給出具體的實現細節，這雖然給了開發者發揮的空間，但同樣可能會在實現的過程中由于開發者不同的實現方式帶來不同的問題，對于一個分布式共識算法，誰也不知道潛在的問題會不會就影響到一致性了。而Raft算法給出了大量實現細節，簡單說就是，實現起來更不容易出錯。
Raft協議同樣是需要選舉出Leader的，從這里也能看到，共識算法大都會走向選舉出一個Leader的方向，來提升效率和穩定性。不同之處可能只在于選舉的方式，以及消息同步的方式。
Raft的選舉，會在上一任Leader失去聯系時發起，每個Follower便有機會成為Candidate，參與選舉。之所以說有機會，是因為每個Follower都會先等一會，看是否有其他候選人過來拉票，避免人人都跑去湊熱鬧參與選舉浪費通信，這個等待的時間是在一個范圍內隨機的。
候選者參與選舉時會產生一個term概念，每個候選者會先投自己一票，然后帶著自己的term和自己的日志信息（代表著數據的新舊）去拉票，其他的Follower先看候選者的term是否大于等于當前自己的term，再看其日志信息是否比自己新，如果都滿足就會投票。候選者收到超過半數的投票的話，就會成為新的Leader了。
在這個過程中投票的Follower也會更新自己的term為自己投票的候選者的term，這樣就可以拒絕低于它的term的候選者了。而候選者如果被拒絕，也會回去更新自己的term以獲得支持。
選出Leader后，Leader會把自己的日志發給大家做同步，以保持大家和自己的日志是一樣的，然后就進行后續的接收客戶端請求的環節。
可以看到Raft和Multi-Paxos也都要選舉出一個Leader節點來，不同之處在于，Raft選舉的Leader節點上的日志信息是最新最全的，這一方面可以不丟失日志信息的順序，另一方面也可以讓選舉過程簡化（日志信息的順序總是好比較的），而Multi-Paxos選Leader的過程偏隨機，就是看誰先拉攏更多節點的支持并快速落定，這一方面會使其日志不連續，另一方面也會使得其實現變得復雜和相對不可控。
但實際上不連續也不完全是缺點，它也可以提高寫入的并發性能，所以雖然Raft實現相對更簡單，但微信的PaxosStore還是選擇了Paxos，甚至它都沒有選擇Multi-Paxos，而是Basic-Paxos，就是為了進一步避免單點依賴和切換Leader時的拒絕服務，來提高可用性。
可以看到，共識算法基本都需要解決兩個基本問題：
如何提出一個需要達成共識的提案（選舉Leader、隨機投票...）
如何讓多個節點對提案達成共識（廣播、復制、投票...）
在這兩個問題的處理方案上選擇不同，就會導致性能、可用性等指標的不同，所以其實，兵器各有利弊，還是要看使用場景和使用的人。
Ralt算法動畫演示地址
Raft
參考資料：
- 當年，我的架構師之路差點完蛋，幸虧了它——BASE理論
總結
- 上一篇： iOS多线程加锁
- 下一篇： 服务器远程端口是什么？远程端口怎么设置？