轉載聲明
本系列文章轉自某技術大佬的部落格
https://www.cnblogs.com/bangerlee/該系列文章是我在網上能夠找到的最全面的分布式理論介紹文章了，一直沒看到有人整理這個系列文章，是以這次我就來做技術好文的搬運工，給整合了一把，覺得寫得好的朋友不妨去這位大佬的部落格上打賞一把。
分布式系統理論 - 從放棄到入門
随承載使用者數量的增加和容災的需要，越來越多網際網路背景系統從單機模式切換到分布式叢集。回顧自己畢業五年來的工作内容，同樣有這樣的轉變。
畢業頭兩年負責維護運作在刀片機上的業務，在機房裡拔插單闆的日子是我逝去的青春。裝置之間通過VCS組成冷備，但即使有雙機軟體保護，當機、網絡丢包等問題發生時業務仍會受影響。這樣的系統架構下為保證SLA，有時候需要深入
Linux系統核心或硬體層面分析機器重新開機的原因。
接下來負責維護承載在分布式叢集上的業務，相比前面的工作，這個階段主要關注點不是單節點的異常，更多是系統整體的穩定和健壯。面對紛繁複雜的系統，剛開始的時候有這樣的感覺：
龐大複雜的分布式系統前，應該從哪方面入手提升對其的認識和了解、提升專業性？網上可以找到很多分布式系統相關的論文和資料，但歸納起來要表達的主要意思是什麼？
結合自己這幾年的工作經驗，總結分布式系統的核心就是解決一個問題：不同節點間如何達成共識。
看似簡單的問題因網絡丢包、節點當機恢複等場景變得複雜，由此才衍生出很多概念、協定和理論。為探究共識問題最大能解決的程度，于是有FLP、CAP邊界理論；為在特定條件和範圍内解決該問題，于是有一緻性協定Paxos、Raft、Zab和Viewstamped Replication；為建構這些協定，于是有多數派、Leader選舉、租約、邏輯時鐘等概念和方法。
2016年我閱讀了分布式系統領域一些代表性的論文和博文，圍繞“不同節點如何達成共識”這個問題，加入自己的認識和了解後有下面7篇小結：
[一緻性、2PC和3PC](http://www.cnblogs.com/bangerlee/p/5268485.html)
[選舉、多數派和租約](http://www.cnblogs.com/bangerlee/p/5767845.html)
[時間、時鐘和事件順序](http://www.cnblogs.com/bangerlee/p/5448766.html)
[CAP](http://www.cnblogs.com/bangerlee/p/5328888.html)
[Paxos](http://www.cnblogs.com/bangerlee/p/5655754.html)
[Raft、Zab](http://www.cnblogs.com/bangerlee/p/5991417.html)
[Paxos變種和優化](http://www.cnblogs.com/bangerlee/p/6189646.html)
構思和寫作技術類文章是一個辛苦的過程，一方面要閱讀很多資料并轉化成自己的了解、找到盡量不拾人牙慧的立意和角度，一方面要絞盡腦汁組織語言讓預期的讀者能夠容易了解。
但它也是一個有趣的過程，把知識捋一遍後原本一些模糊的概念變得清晰，寫作過程中想到的一些有意思的内容我也會将它穿插到文章裡，有時候會被自己想到的一些小機靈逗樂 :)
希望這幾篇整理能為系統性地介紹分布式理論中文資料添一塊磚、加一片瓦。
分布式系統理論基礎 - 一緻性、2PC和3PC
引言
狹義的分布式系統指由網絡連接配接的計算機系統，每個節點獨立地承擔計算或存儲任務，節點間通過網絡協同工作。廣義的分布式系統是一個相對的概念，正如
Leslie Lamport所說[1]：
What is a distributed systeme. Distribution is in the eye of the beholder.
To the user sitting at the keyboard, his IBM personal computer is a nondistributed system.
To a flea crawling around on the circuit board, or to the engineer who designed it, it's very much a distributed system.
一緻性是分布式理論中的根本性問題，近半個世紀以來，科學家們圍繞着一緻性問題提出了很多理論模型，依據這些理論模型，業界也出現了很多工程實踐投影。下面我們從一緻性問題、特定條件下解決一緻性問題的兩種方法(2PC、3PC)入門，了解最基礎的分布式系統理論。
一緻性(consensus)
何為一緻性問題？簡單而言，一緻性問題就是互相獨立的節點之間如何達成一項決議的問題。分布式系統中，進行資料庫事務送出(commit transaction)、Leader選舉、序列号生成等都會遇到一緻性問題。這個問題在我們的日常生活中也很常見，比如牌友怎麼商定幾點在哪打幾圈麻将：
《賭聖》，1990
假設一個具有N個節點的分布式系統，當其滿足以下條件時，我們說這個系統滿足一緻性：
- 全認同(agreement): 所有N個節點都認同一個結果
- 值合法(validity): 該結果必須由N個節點中的節點提出
- 可結束(termination): 決議過程在一定時間内結束，不會無休止地進行下去
有人可能會說，決定什麼時候在哪搓搓麻将，4個人商量一下就ok，這不很簡單嗎？
但就這樣看似簡單的事情，分布式系統實作起來并不輕松，因為它面臨着這些問題：
- 消息傳遞異步無序(asynchronous): 現實網絡不是一個可靠的信道，存在消息延時、丢失，節點間消息傳遞做不到同步有序(synchronous)
- 節點當機(fail-stop): 節點持續當機，不會恢複
- 節點當機恢複(fail-recover): 節點當機一段時間後恢複，在分布式系統中最常見
- 網絡分化(network partition): 網絡鍊路出現問題，将N個節點隔離成多個部分
- 拜占庭将軍問題(byzantine failure)[2]: 節點或當機或邏輯失敗，甚至不按套路出牌抛出幹擾決議的資訊
假設現實場景中也存在這樣的問題，我們看看結果會怎樣：
; "複制代碼")
我: 老王，今晚7點老地方，搓夠48圈不見不散！
……
（第二天淩晨3點） 隔壁老王: 沒問題！ // 消息延遲 我: ……
我: 小張，今晚7點老地方，搓夠48圈不見不散！
小張: No ……
（兩小時後……）
小張: No problem！ // 當機節點恢複
我: 老李頭，今晚7點老地方，搓夠48圈不見不散！
老李: 必須的，大保健走起！ // 拜占庭将軍 （這是要打麻将呢？還是要大保健？還是一邊打麻将一邊大保健……）
還能不能一起愉快地玩耍...
我們把以上所列的問題稱為系統模型(system model)，讨論分布式系統理論和工程實踐的時候，必先劃定模型。例如有以下兩種模型：
- 異步環境(asynchronous)下，節點當機(fail-stop)
- 異步環境(asynchronous)下，節點當機恢複(fail-recover)、網絡分化(network partition)
2比1多了節點恢複、網絡分化的考量，因而對這兩種模型的理論研究和工程解決方案必定是不同的，在還沒有明晰所要解決的問題前談解決方案都是一本正經地耍流氓。
一緻性還具備兩個屬性，一個是強一緻(safety)，它要求所有節點狀态一緻、共進退；一個是可用(liveness)，它要求分布式系統24*7無間斷對外服務。FLP定理(FLP impossibility)3 已經證明在一個收窄的模型中(異步環境并隻存在節點當機)，不能同時滿足 safety 和 liveness。
FLP定理是分布式系統理論中的基礎理論，正如實體學中的能量守恒定律徹底否定了永動機的存在，FLP定理否定了同時滿足safety 和 liveness 的一緻性協定的存在。
《怦然心動 (Flipped)》，2010
工程實踐上根據具體的業務場景，或保證強一緻(safety)，或在節點當機、網絡分化的時候保證可用(liveness)。2PC、3PC是相對簡單的解決一緻性問題的協定，下面我們就來了解2PC和3PC。
2PC
2PC(tow phase commit)兩階段送出[5]顧名思義它分成兩個階段，先由一方進行提議(propose)并收集其他節點的回報(vote)，再根據回報決定送出(commit)或中止(abort)事務。我們将提議的節點稱為協調者(coordinator)，其他參與決議節點稱為參與者(participants, 或cohorts)：
2PC, phase one
在階段1中，coordinator發起一個提議，分别問詢各participant是否接受。
2PC, phase two
在階段2中，coordinator根據participant的回報，送出或中止事務，如果participant全部同意則送出，隻要有一個participant不同意就中止。
在異步環境(asynchronous)并且沒有節點當機(fail-stop)的模型下，2PC可以滿足全認同、值合法、可結束，是解決一緻性問題的一種協定。但如果再加上節點當機(fail-recover)的考慮，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)增加相對較少。
3PC
3PC(three phase commit)即三階段送出6，既然2PC可以在異步網絡+節點當機恢複的模型下實作一緻性，那還需要3PC做什麼，3PC是什麼鬼？
在2PC中一個participant的狀态隻有它自己和coordinator知曉，假如coordinator提議後自身當機，在watchdog啟用前一個participant又當機，其他participant就會進入既不能復原、又不能強制commit的阻塞狀态，直到participant當機恢複。這引出兩個疑問：
- 能不能去掉阻塞，使系統可以在commit/abort前復原(rollback)到決議發起前的初始狀态
- 當次決議中，participant間能不能互相知道對方的狀态，又或者participant間根本不依賴對方的狀态
相比2PC，3PC增加了一個準備送出(prepare to commit)階段來解決以上問題：
圖檔截取自wikipedia
coordinator接收完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該次事務
因為有了準備送出(prepare to commit)階段，3PC的事務處理延時也增加了1個RTT，變為3個RTT(propose+precommit+commit)，但是它防止participant當機後整個系統進入阻塞态，增強了系統的可用性，對一些現實業務場景是非常值得的。
小結
以上介紹了分布式系統理論中的部分基礎知識，闡述了一緻性(consensus)的定義和實作一緻性所要面臨的問題，最後讨論在異步網絡(asynchronous)、節點當機恢複(fail-recover)模型下2PC、3PC怎麼解決一緻性問題。
閱讀前人對分布式系統的各項理論研究，其中有嚴謹地推理、證明，有一種數學的美；觀現實中的分布式系統實作，是綜合各種因素下妥協的結果。
分布式系統理論基礎 - 選舉、多數派和租約
選舉(election)是分布式系統實踐中常見的問題，通過打破節點間的對等關系，選得的leader(或叫master、coordinator)有助于實作事務原子性、提升決議效率。 多數派(quorum)的思路幫助我們在網絡分化的情況下達成決議一緻性，在leader選舉的場景下幫助我們選出唯一leader。租約(lease)在一定期限内給予節點特定權利，也可以用于實作leader選舉。
下面我們就來學習分布式系統理論中的選舉、多數派和租約。
選舉(electioin)
一緻性問題(consistency)是獨立的節點間如何達成決議的問題，選出大家都認可的leader本質上也是一緻性問題，因而如何應對當機恢複、網絡分化等在leader選舉中也需要考量。
Bully算法[1]是最常見的選舉算法，其要求每個節點對應一個序号，序号最高的節點為leader。leader當機後次高序号的節點被重選為leader，過程如下：
(a). 節點4發現leader不可達，向序号比自己高的節點發起重新選舉，重新選舉消息中帶上自己的序号
(b)(c). 節點5、6接收到重選資訊後進行序号比較，發現自身的序号更大，向節點4傳回OK消息并各自向更高序号節點發起重新選舉
(d). 節點5收到節點6的OK消息，而節點6經過逾時時間後收不到更高序号節點的OK消息，則認為自己是leader
(e). 節點6把自己成為leader的資訊廣播到所有節點
回顧
《分布式系統理論基礎 - 一緻性、2PC和3PC》就可以看到，Bully算法中有2PC的身影，都具有提議(propose)和收集回報(vote)的過程。
在一緻性算法
Paxos、ZAB[2]、Raft[3]中，為提升決議效率均有節點充當leader的角色。ZAB、Raft中描述了具體的leader選舉實作，與Bully算法類似ZAB中使用zxid辨別節點，具有最大zxid的節點表示其所具備的事務(transaction)最新、被選為leader。
多數派(quorum)
在網絡分化的場景下以上Bully算法會遇到一個問題，被分隔的節點都認為自己具有最大的序号、将産生多個leader，這時候就需要引入多數派(quorum)[4]。多數派的思路在分布式系統中很常見，其確定網絡分化情況下決議唯一。
多數派的原理說起來很簡單，假如節點總數為2f+1，則一項決議得到多于 f 節點贊成則獲得通過。leader選舉中，網絡分化場景下隻有具備多數派節點的部分才可能選出leader，這避免了多leader的産生。
多數派的思路還被應用于副本(replica)管理，根據業務實際讀寫比例調整寫副本數Vw、讀副本數Vr，用以在可靠性和性能方面取得平衡[5]。
租約(lease)
選舉中很重要的一個問題，以上尚未提到：怎麼判斷leader不可用、什麼時候應該發起重新選舉？最先可能想到會通過心跳(heart beat)判别leader狀态是否正常，但在網絡擁塞或瞬斷的情況下，這容易導緻出現雙主。
租約(lease)是解決該問題的常用方法，其最初提出時用于解決分布式緩存一緻性問題[6]，後面在分布式鎖[7]等很多方面都有應用。
租約的原理同樣不複雜，中心思想是每次租約時長内隻有一個節點獲得租約、到期後必須重新頒發租約。假設我們有租約頒發節點Z，節點0、1和2競選leader，租約過程如下：
(a). 節點0、1、2在Z上注冊自己，Z根據一定的規則(例如先到先得)頒發租約給節點，該租約同時對應一個有效時長；這裡假設節點0獲得租約、成為leader
(b). leader當機時，隻有租約到期(timeout)後才重新發起選舉，這裡節點1獲得租約、成為leader
租約機制確定了一個時刻最多隻有一個leader，避免隻使用心跳機制産生雙主的問題。在實踐應用中，zookeeper、ectd可用于租約頒發。
在分布式系統理論和實踐中，常見leader、quorum和lease的身影。分布式系統内不一定事事協商、事事民主，leader的存在有助于提升決議效率。
本文以leader選舉作為例子引入和講述quorum、lease，當然quorum和lease是兩種思想，并不限于leader選舉應用。
最後提一個有趣的問題與大家思考，leader選舉的本質是一緻性問題，Paxos、Raft和ZAB等解決一緻性問題的協定和算法本身又需要或依賴于leader，怎麼了解這個看似“蛋生雞、雞生蛋”的問題？[8]
分布式系統理論基礎 - 時間、時鐘和事件順序
十六号…… 四月十六号。一九六零年四月十六号下午三點之前的一分鐘你和我在一起，因為你我會記住這一分鐘。從現在開始我們就是一分鐘的朋友，這是事實，你改變不了，因為已經過去了。我明天會再來。
—— 《阿飛正傳》
現實生活中時間是很重要的概念，時間可以記錄事情發生的時刻、比較事情發生的先後順序。分布式系統的一些場景也需要記錄和比較不同節點間事件發生的順序，但不同于日常生活使用實體時鐘記錄時間，分布式系統使用邏輯時鐘記錄事件順序關系，下面我們來看分布式系統中幾種常見的邏輯時鐘。
實體時鐘 vs 邏輯時鐘
可能有人會問，為什麼分布式系統不使用實體時鐘(physical clock)記錄事件？每個事件對應打上一個時間戳，當需要比較順序的時候比較相應時間戳就好了。
這是因為現實生活中實體時間有統一的标準，而分布式系統中每個節點記錄的時間并不一樣，即使設定了
NTP時間同步節點間也存在毫秒級别的偏差1。因而分布式系統需要有另外的方法記錄事件順序關系，這就是邏輯時鐘(logical clock)。
Lamport timestamps
Leslie Lamport在1978年提出邏輯時鐘的概念，并描述了一種邏輯時鐘的表示方法，這個方法被稱為Lamport時間戳(Lamport timestamps)[3]。
分布式系統中按是否存在節點互動可分為三類事件，一類發生于節點内部，二是發送事件，三是接收事件。Lamport時間戳原理如下：
圖1: Lamport timestamps space time (圖檔來源: wikipedia)
- 每個事件對應一個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 j，同樣定義為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)[4]。例如圖1中事件B4和事件C3沒有因果關系，屬于同時發生事件，但Lamport時間戳定義兩者有先後順序。
Vector clock是在Lamport時間戳基礎上演進的另一種邏輯時鐘方法，它通過vector結構不但記錄本節點的Lamport時間戳，同時也記錄了其他節點的Lamport時間戳5。Vector clock的原理與Lamport時間戳類似，使用圖例如下：
圖2: Vector clock space time (_圖檔來源: wikipedia)_
假設有事件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)，多個副本可能被同時更新，這會引起副本間資料不一緻[7]，Version vector的實作與Vector clock非常類似[8]，目的用于發現資料沖突[9]。下面通過一個例子說明Version vector的用法[10]：
圖3: 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決議事先避免資料沖突的情況發生[11]。
由于記錄了所有資料在所有節點上的邏輯時鐘資訊，Vector clock和Version vector在實際應用中可能面臨的一個問題是vector過大，用于資料管理的中繼資料(meta data)甚至大于資料本身[12]。
解決該問題的方法是使用server id取代client id建立vector (因為server的數量相對client穩定)，或設定最大的size、如果超過該size值則淘汰最舊的vector資訊10。
以上介紹了分布式系統裡邏輯時鐘的表示方法，通過Lamport timestamps可以建立事件的全序關系，通過Vector clock可以比較任意兩個事件的順序關系并且能表示無因果關系的事件，将Vector clock的方法用于發現資料版本沖突，于是有了Version vector。
分布式系統理論基礎 - CAP
CAP是分布式系統、特别是分布式存儲領域中被讨論最多的理論，“
什麼是CAP定理？”在Quora 分布式系統分類下排名 FAQ 的 No.1。CAP在程式員中也有較廣的普及，它不僅僅是“C、A、P不能同時滿足，最多隻能3選2”，以下嘗試綜合各方觀點，從發展曆史、工程實踐等角度講述CAP理論。希望大家透過本文對CAP理論有更多地了解和認識。
CAP定理
CAP由
Eric Brewer)在2000年PODC會議上提出1，是Eric Brewer在Inktomi[3]期間研發搜尋引擎、分布式web緩存時得出的關于資料一緻性(consistency)、服務可用性(availability)、分區容錯性(partition-tolerance)的猜想：
It is impossible for a web service to provide the three following guarantees : Consistency, Availability and Partition-tolerance.
該猜想在提出兩年後被證明成立[4]，成為我們熟知的CAP定理：
- 資料一緻性(consistency)：如果系統對一個寫操作傳回成功，那麼之後的讀請求都必須讀到這個新資料；如果傳回失敗，那麼所有讀操作都不能讀到這個資料，對調用者而言資料具有強一緻性(strong consistency) (又叫原子性 atomic、線性一緻性 linearizable consistency)[5]
- 服務可用性(availability)：所有讀寫請求在一定時間内得到響應，可終止、不會一直等待
- 分區容錯性(partition-tolerance)：在網絡分區的情況下，被分隔的節點仍能正常對外服務
在某時刻如果滿足AP，分隔的節點同時對外服務但不能互相通信，将導緻狀态不一緻，即不能滿足C；如果滿足CP，網絡分區的情況下為達成C，請求隻能一直等待，即不滿足A；如果要滿足CA，在一定時間内要達到節點狀态一緻，要求不能出現網絡分區，則不能滿足P。
C、A、P三者最多隻能滿足其中兩個，和FLP定理一樣，CAP定理也訓示了一個不可達的結果(impossibility result)。
CAP的工程啟示
CAP理論提出7、8年後，NoSql圈将CAP理論當作對抗傳統關系型資料庫的依據、闡明自己放寬對資料一緻性(consistency)要求的正确性[6]，随後引起了大範圍關于CAP理論的讨論。
CAP理論看似給我們出了一道3選2的選擇題，但在工程實踐中存在很多現實限制條件，需要我們做更多地考量與權衡，避免進入CAP認識誤區[7]。
1、關于 P 的了解
Partition字面意思是網絡分區，即因網絡因素将系統分隔為多個單獨的部分，有人可能會說，網絡分區的情況發生機率非常小啊，是不是不用考慮P，保證CA就好[8]。要了解P，我們看回CAP證明[4]中P的定義：
In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another.
網絡分區的情況符合該定義，網絡丢包的情況也符合以上定義，另外節點當機，其他節點發往當機節點的包也将丢失，這種情況同樣符合定義。現實情況下我們面對的是一個不可靠的網絡、有一定機率當機的裝置，這兩個因素都會導緻Partition，因而分布式系統實作中 P 是一個必須項，而不是可選項9。
對于分布式系統工程實踐，CAP理論更合适的描述是：在滿足分區容錯的前提下，沒有算法能同時滿足資料一緻性和服務可用性[11]：
In a network subject to communication failures, it is impossible for any web service to implement an atomic read/write shared memory that guarantees a response to every request.
2、CA非0/1的選擇
P 是必選項，那3選2的選擇題不就變成資料一緻性(consistency)、服務可用性(availability) 2選1？工程實踐中一緻性有不同程度，可用性也有不同等級，在保證分區容錯性的前提下，放寬限制後可以兼顧一緻性和可用性，兩者不是非此即彼[12]。
CAP定理證明中的一緻性指強一緻性，強一緻性要求多節點組成的被調要能像單節點一樣運作、操作具備原子性，資料在時間、時序上都有要求。如果放寬這些要求，還有其他一緻性類型：
- 序列一緻性(sequential consistency)[13]：不要求時序一緻，A操作先于B操作，在B操作後如果所有調用端讀操作得到A操作的結果，滿足序列一緻性
- 最終一緻性(eventual consistency)[14]：放寬對時間的要求，在被調完成操作響應後的某個時間點，被調多個節點的資料最終達成一緻
可用性在CAP定理裡指所有讀寫操作必須要能終止，實際應用中從主調、被調兩個不同的視角，可用性具有不同的含義。當P(網絡分區)出現時，主調可以隻支援讀操作，通過犧牲部分可用性達成資料一緻。
工程實踐中，較常見的做法是通過異步拷貝副本(asynchronous replication)、quorum/NRW，實作在調用端看來資料強一緻、被調端最終一緻，在調用端看來服務可用、被調端允許部分節點不可用(或被網絡分隔)的效果[15]。
3、跳出CAP
CAP理論對實作分布式系統具有指導意義，但CAP理論并沒有涵蓋分布式工程實踐中的所有重要因素。
例如延時(latency)，它是衡量系統可用性、與使用者體驗直接相關的一項重要名額[16]。CAP理論中的可用性要求操作能終止、不無休止地進行，除此之外，我們還關心到底需要多長時間能結束操作，這就是延時，它值得我們設計、實作分布式系統時單列出來考慮。
延時與資料一緻性也是一對“冤家”，如果要達到強一緻性、多個副本資料一緻，必然增加延時。加上延時的考量，我們得到一個CAP理論的修改版本PACELC[17]：如果出現P(網絡分區)，如何在A(服務可用性)、C(資料一緻性)之間選擇；否則，如何在L(延時)、C(資料一緻性)之間選擇。
以上介紹了CAP理論的源起和發展，介紹了CAP理論給分布式系統工程實踐帶來的啟示。
CAP理論對分布式系統實作有非常重大的影響，我們可以根據自身的業務特點，在資料一緻性和服務可用性之間作出傾向性地選擇。通過放松限制條件，我們可以實作在不同時間點滿足CAP(此CAP非CAP定理中的CAP，如C替換為最終一緻性)18[20]。
有非常非常多文章讨論和研究CAP理論，希望這篇對你認識和了解CAP理論有幫助。
分布式系統理論進階 - Paxos
一文介紹了一緻性、達成一緻性需要面臨的各種問題以及2PC、3PC模型，Paxos協定在節點當機恢複、消息無序或丢失、網絡分化的場景下能保證決議的一緻性，是被讨論最廣泛的一緻性協定。
Paxos協定同時又以其“艱深晦澀”著稱，下面結合
Paxos Made Simple、
The Part-Time Parliament兩篇論文，嘗試通過Paxos推演、學習和了解Paxos協定。
Basic Paxos
何為一緻性問題？簡單而言，一緻性問題是在節點當機、消息無序等場景可能出現的情況下，互相獨立的節點之間如何達成決議的問題，作為解決一緻性問題的協定，Paxos的核心是節點間如何确定并隻确定一個值(value)。
也許你會疑惑隻确定一個值能起什麼作用，在Paxos協定裡确定并隻确定一個值是确定多值的基礎，如何确定多值将在第二部分Multi Paxos中介紹，這部分我們聚焦在“Paxos如何确定并隻确定一個值”這一問題上。
和2PC類似，Paxos先把節點分成兩類，發起提議(proposal)的一方為proposer，參與決議的一方為acceptor。假如隻有一個proposer發起提議，并且節點不當機、消息不丢包，那麼acceptor做到以下這點就可以确定一個值：
P1. 一個acceptor接受它收到的第一項提議 當然上面要求的前提條件有些嚴苛，節點不能當機、消息不能丢包，還隻能由一個proposer發起提議。我們嘗試放寬條件，假設多個proposer可以同時發起提議，又怎樣才能做到确定并隻确定一個值呢？
首先proposer和acceptor需要滿足以下兩個條件：
1. proposer發起的每項提議分别用一個ID辨別，提議的組成是以變為(ID, value)
2. acceptor可以接受(accept)不止一項提議，當多數(quorum) acceptor接受一項提議時該提議被确定(chosen)
(注: 注意以上“接受”和“确定”的差別）
我們約定後面發起的提議的ID比前面提議的ID大，并假設可以有多項提議被确定，為做到确定并隻确定一個值acceptor要做到以下這點：
P2. 如果一項值為v的提議被确定，那麼後續隻确定值為v的提議 (注: 乍看這個條件不太好了解，謹記目标是“确定并隻确定一個值”)
由于一項提議被确定(chosen)前必須先被多數派acceptor接受(accepted)，為實作P2，實質上acceptor需要做到：
P2a. 如果一項值為v的提議被确定，那麼acceptor後續隻接受值為v的提議 滿足P2a則P2成立 (P2a => P2)。
目前在多個proposer可以同時發起提議的情況下，滿足P1、P2a即能做到确定并隻确定一個值。如果再加上節點當機恢複、消息丢包的考量呢？
假設acceptor c 當機一段時間後恢複，c 當機期間其他acceptor已經确定了一項值為v的決議但c 因為當機并不知曉；c 恢複後如果有proposer馬上發起一項值不是v的提議，由于條件P1，c 會接受該提議，這與P2a沖突。為了避免這樣的情況出現，進一步地我們對proposer作限制：
P2b. 如果一項值為v的提議被确定，那麼proposer後續隻發起值為v的提議 滿足P2b則P2a成立 (P2b => P2a => P2)。
P2b限制的是提議被确定(chosen)後proposer的行為，我們更關心提議被确定前proposer應該怎麼做：
P2c. 對于提議(n,v)，acceptor的多數派S中，如果存在acceptor最近一次(即ID值最大)接受的提議的值為v'，那麼要求v = v'；否則v可為任意值 滿足P2c則P2b成立 (P2c => P2b => P2a => P2)。
條件P2c是Basic Paxos的核心，光看P2c的描述可能會覺得一頭霧水，我們通過
中的例子加深了解：
假設有A~E 5個acceptor，- 表示acceptor因當機等原因缺席當次決議，x 表示acceptor不接受提議，o 表示接受提議；多數派acceptor接受提議後提議被确定，以上表格對應的決議過程如下：
- ID為2的提議最早提出，根據P2c其提議值可為任意值，這裡假設為a
- acceptor A/B/C/E 在之前的決議中沒有接受(accept)任何提議，因而ID為5的提議的值也可以為任意值，這裡假設為b
- acceptor B/D/E，其中D曾接受ID為2的提議，根據P2c，該輪ID為14的提議的值必須與ID為2的提議的值相同，為a
- acceptor A/C/D，其中D曾接受ID為2的提議、C曾接受ID為5的提議，相比之下ID 5較ID 2大，根據P2c，該輪ID為27的提議的值必須與ID為5的提議的值相同，為b；該輪決議被多數派acceptor接受，是以該輪決議得以确定
- acceptor B/C/D，3個acceptor之前都接受過提議，相比之下C、D曾接受的ID 27的ID号最大，該輪ID為29的提議的值必須與ID為27的提議的值相同，為b
以上提到的各項限制條件可以歸納為3點，如果proposer/acceptor滿足下面3點，那麼在少數節點當機、網絡分化隔離的情況下，在“确定并隻确定一個值”這件事情上可以保證一緻性(consistency)：
- B1(ß): ß中每一輪決議都有唯一的ID辨別
- B2(ß): 如果決議B被acceptor多數派接受，則确定決議B
- B3(ß): 對于ß中的任意提議B(n,v)，acceptor的多數派中如果存在acceptor最近一次(即ID值最大)接受的提議的值為v'，那麼要求v = v'；否則v可為任意值
(注: 希臘字母ß表示多輪決議的集合，字母B表示一輪決議)
另外為保證P2c，我們對acceptor作兩個要求：
1. 記錄曾接受的ID最大的提議，因proposer需要問詢該資訊以決定提議值
2. 在回應提議ID為n的proposer自己曾接受過ID最大的提議時，acceptor同時保證(promise)不再接受ID小于n的提議
至此，proposer/acceptor完成一輪決議可歸納為prepare和accept兩個階段。prepare階段proposer發起提議問詢提議值、acceptor回應問詢并進行promise；accept階段完成決議，圖示如下：
還有一個問題需要考量，假如proposer A發起ID為n的提議，在提議未完成前proposer B又發起ID為n+1的提議，在n+1提議未完成前proposer C又發起ID為n+2的提議…… 如此acceptor不能完成決議、形成活鎖(livelock)，雖然這不影響一緻性，但我們一般不想讓這樣的情況發生。解決的方法是從proposer中選出一個leader，提議統一由leader發起。
最後我們再引入一個新的角色：learner，learner依附于acceptor，用于習得已确定的決議。以上決議過程都隻要求acceptor多數派參與，而我們希望盡量所有acceptor的狀态一緻。如果部分acceptor因當機等原因未知曉已确定決議，當機恢複後可經本機learner采用pull的方式從其他acceptor習得。
Multi Paxos
通過以上步驟分布式系統已經能确定一個值，“隻确定一個值有什麼用？這可解決不了我面臨的問題。” 你心中可能有這樣的疑問。
其實不斷地進行“确定一個值”的過程、再為每個過程編上序号，就能得到具有全序關系(total order)的系列值，進而能應用在資料庫副本存儲等很多場景。我們把單次“确定一個值”的過程稱為執行個體(instance)，它由proposer/acceptor/learner組成，下圖說明了A/B/C三機上的執行個體：
不同序号的執行個體之間互相不影響，A/B/C三機輸入相同、過程實質等同于執行相同序列的狀态機(state machine)指令 ，因而将得到一緻的結果。
proposer leader在Multi Paxos中還有助于提升性能，常态下統一由leader發起提議，可節省prepare步驟(leader不用問詢acceptor曾接受過的ID最大的提議、隻有leader提議也不需要acceptor進行promise)直至發生leader當機、重新選主。
以上介紹了Paxos的推演過程、如何在Basic Paxos的基礎上通過狀态機建構Multi Paxos。Paxos協定比較“艱深晦澀”，但多讀幾遍論文一般能了解其内涵，更難的是如何将Paxos真正應用到工程實踐。
微信背景開發同學實作并開源了一套基于Paxos協定的多機狀态拷貝類庫
PhxPaxos，PhxPaxos用于将單機服務擴充到多機，其經過線上系統驗證并在一緻性保證、性能等方面作了很多考量。
分布式系統理論進階 - Raft、Zab
《分布式系統理論進階 - Paxos》介紹了一緻性協定Paxos，今天我們來學習另外兩個常見的一緻性協定——Raft和Zab。通過與Paxos對比，了解Raft和Zab的核心思想、加深對一緻性協定的認識。
Raft
Paxos偏向于理論、對如何應用到工程實踐提及較少。了解的難度加上現實的骨感，在生産環境中基于Paxos實作一個正确的分布式系統非常難[1]：
There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. In order to build a real-world system, an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions. The cumulative effort will be substantial and the final system will be based on an unproven protocol.
Raft2在2013年提出，提出的時間雖然不長，但已經有很多系統基于Raft實作。相比Paxos，Raft的買點就是更利于了解、更易于實行。
為達到更容易了解和實行的目的，Raft将問題分解和具體化：Leader統一處理變更操作請求，一緻性協定的作用具化為保證節點間記錄檔副本(log replication)一緻，以term作為邏輯時鐘(logical clock)保證時序，節點運作相同狀态機(state machine)[4]得到一緻結果。Raft協定具體過程如下：
- Client發起請求，每一條請求包含操作指令
- 請求交由Leader處理，Leader将操作指令(entry)追加(append)至記錄檔，緊接着對Follower發起AppendEntries請求、嘗試讓記錄檔副本在Follower落地
- 如果Follower多數派(quorum)同意AppendEntries請求，Leader進行commit操作、把指令交由狀态機處理
- 狀态機處理完成後将結果傳回給Client
指令通過log index(指令id)和term number保證時序，正常情況下Leader、Follower狀态機按相同順序執行指令，得出相同結果、狀态一緻。
當機、網絡分化等情況可引起Leader重新選舉(每次選舉産生新Leader的同時，産生新的term)、Leader/Follower間狀态不一緻。Raft中Leader為自己和所有Follower各維護一個nextIndex值，其表示Leader緊接下來要處理的指令id以及将要發給Follower的指令id，LnextIndex不等于FnextIndex時代表Leader記錄檔和Follower記錄檔存在不一緻，這時将從Follower記錄檔中最初不一緻的地方開始，由Leader記錄檔覆寫Follower，直到LnextIndex、FnextIndex相等。
Paxos中Leader的存在是為了提升決議效率，Leader的有無和數目并不影響決議一緻性，Raft要求具備唯一Leader，并把一緻性問題具體化為保持日志副本的一緻性，以此實作相較Paxos而言更容易了解、更容易實作的目标。
Zab
Zab5的全稱是Zookeeper atomic broadcast protocol，是Zookeeper内部用到的一緻性協定。相比Paxos，Zab最大的特點是保證強一緻性(strong consistency，或叫線性一緻性linearizable consistency)。
和Raft一樣，Zab要求唯一Leader參與決議，Zab可以分解成discovery、sync、broadcast三個階段：
- discovery: 選舉産生PL(prospective leader)，PL收集Follower epoch(cepoch)，根據Follower的回報PL産生newepoch(每次選舉産生新Leader的同時産生新epoch，類似Raft的term)
- sync: PL補齊相比Follower多數派缺失的狀态、之後各Follower再補齊相比PL缺失的狀态，PL和Follower完成狀态同步後PL變為正式Leader(established leader)
- broadcast: Leader處理Client的寫操作，并将狀态變更廣播至Follower，Follower多數派通過之後Leader發起将狀态變更落地(deliver/commit)
Leader和Follower之間通過心跳判别健康狀态，正常情況下Zab處在broadcast階段，出現Leader當機、網絡隔離等異常情況時Zab重新回到discovery階段。
了解完Zab的基本原理，我們再來看Zab怎樣保證強一緻性，Zab通過限制事務先後順序達到強一緻性，先廣播的事務先commit、FIFO，Zab稱之為primary order(以下簡稱PO)。實作PO的核心是zxid。
Zab中每個事務對應一個zxid，它由兩部分組成：，e即Leader選舉時生成的epoch，c表示當次epoch内事務的編号、依次遞增。假設有兩個事務的zxid分别是z、z'，當滿足 z.e < z'.e 或者 z.e = z'.e && z.c < z'.c 時，定義z先于z'發生(z < z')。
為實作PO，Zab對Follower、Leader有以下限制：
- 有事務z和z'，如果Leader先廣播z，則Follower需保證先commit z對應的事務
- 有事務z和z'，z由Leader p廣播，z'由Leader q廣播，Leader p先于Leader q，則Follower需保證先commit z對應的事務
- 有事務z和z'，z由Leader p廣播，z'由Leader q廣播，Leader p先于Leader q，如果Follower已經commit z，則q需保證已commit z才能廣播z'
第1、2點保證事務FIFO，第3點保證Leader上具備所有已commit的事務。
相比Paxos，Zab限制了事務順序、适用于有強一緻性需求的場景。
Paxos、Raft、Zab再比較
除Paxos、Raft和Zab外，Viewstamped Replication(簡稱VR)7也是讨論比較多的一緻性協定。這些協定包含很多共同的内容(Leader、quorum、state machine等)，因而我們不禁要問：Paxos、Raft、Zab和VR等分布式一緻性協定差別到底在哪，還是根本就是一回事？[9]
Paxos、Raft、Zab和VR都是解決一緻性問題的協定，Paxos協定原文傾向于理論，Raft、Zab、VR傾向于實踐，一緻性保證程度等的不同也導緻這些協定間存在差異。下圖幫助我們了解這些協定的相似點和差別[10]：
相比Raft、Zab、VR，Paxos更純粹、更接近一緻性問題本源，盡管Paxos傾向理論，但不代表Paxos不能應用于工程。基于Paxos的工程實踐，須考慮具體需求場景(如一緻性要達到什麼程度)，再在Paxos原始語意上進行包裝。
以上介紹分布式一緻性協定Raft、Zab的核心思想，分析Raft、Zab與Paxos的異同。實作分布式系統時，先從具體需求和場景考慮，Raft、Zab、VR、Paxos等協定沒有絕對地好與不好，隻是适不适合。
分布式系統理論進階 - Paxos變種和優化
中我們了解了Basic Paxos、Multi Paxos的基本原理，但如果想把Paxos應用于工程實踐，了解基本原理還不夠。
有很多基于Paxos的優化，在保證一緻性協定正确(safety)的前提下，減少Paxos決議通信步驟、避免單點故障、實作節點負載均衡，進而降低延遲時間、增加吞吐量、提升可用性，下面我們就來了解這些Paxos變種。
首先我們來回顧一下Multi Paxos，Multi Paxos在Basic Paxos的基礎上确定一系列值，其決議過程如下：
phase1a: leader送出提議給acceptor
phase1b: acceptor傳回最近一次接受的提議(即曾接受的最大的提議ID和對應的value)，未接受過提議則傳回空
phase2a: leader收集acceptor的應答，分兩種情況處理
phase2a.1: 如果應答内容都為空，則自由選擇一個提議value
phase2a.2: 如果應答内容不為空，則選擇應答裡面ID最大的提議的value
phase2b: acceptor将決議同步給learner
Multi Paxos中leader用于避免活鎖，但leader的存在會帶來其他問題，一是如何選舉和保持唯一leader(雖然無leader或多leader不影響一緻性，但影響決議程序progress)，二是充當leader的節點會承擔更多壓力，如何均衡節點的負載。Mencius[1]提出節點輪流擔任leader，以達到均衡負載的目的；租約(lease)可以幫助實作唯一leader，但leader故障情況下可導緻服務短期不可用。
Fast Paxos
在Multi Paxos中，proposer -> leader -> acceptor -> learner，從提議到完成決議共經過3次通信，能不能減少通信步驟？
對Multi Paxos phase2a，如果可以自由提議value，則可以讓proposer直接發起提議、leader退出通信過程，變為proposer -> acceptor -> learner，這就是Fast Paxos[2]的由來。
Multi Paxos裡提議都由leader提出，因而不存在一次決議出現多個value，Fast Paxos裡由proposer直接提議，一次決議裡可能有多個proposer提議、出現多個value，即出現提議沖突(collision)。leader起到初始化決議程序(progress)和解決沖突的作用，當沖突發生時leader重新參與決議過程、回退到3次通信步驟。
Paxos自身隐含的一個特性也可以達到減少通信步驟的目标，如果acceptor上一次确定(chosen)的提議來自proposerA，則當次決議proposerA可以直接提議減少一次通信步驟。如果想實作這樣的效果，需要在proposer、acceptor記錄上一次決議确定(chosen)的曆史，用以在提議前知道哪個proposer的提議上一次被确定、當次決議能不能節省一次通信步驟。
EPaxos
除了從減少通信步驟的角度提高Paxos決議效率外，還有其他方面可以降低Paxos決議時延，比如Generalized Paxos[3]提出不沖突的提議(例如對不同key的寫請求)可以同時決議、以降低Paxos時延。
更進一步地，EPaxos[4](Egalitarian Paxos)提出一種既支援不沖突提議同時送出降低延遲時間、還均衡各節點負載、同時将通信步驟減少到最少的Paxos優化方法。
為達到這些目标，EPaxos的實作有幾個要點。一是EPaxos中沒有全局的leader，而是每一次提議發起提議的proposer作為當次提議的leader(command leader)；二是不互相影響(interfere)的提議可以同時送出；三是跳過prepare，直接進入accept階段。EPaxos決議的過程如下：
左側展示了互不影響的兩個update請求的決議過程，右側展示了互相影響的兩個update請求的決議。Multi Paxos、Mencius、EPaxos時延和吞吐量對比：
為判斷決議是否互相影響，實作EPaxos得記錄決議之間的依賴關系。
以上介紹了幾個基于Paxos的變種，Mencius中節點輪流做leader、均衡節點負載，Fast Paxos減少一次通信步驟，Generalized Paxos允許互不影響的決議同時進行，EPaxos無全局leader、各節點平等分擔負載。
優化無止境，對Paxos也一樣，應用在不同場景和不同範圍的Paxos變種和優化将繼續不斷出現。