web分布式系統(tǒng)怎么理解-創(chuàng)新互聯(lián)

本篇內(nèi)容介紹了“web分布式系統(tǒng)怎么理解”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

十余年的昔陽網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。全網(wǎng)整合營銷推廣的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整昔陽建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)公司從事“昔陽網(wǎng)站設(shè)計(jì)”,“昔陽網(wǎng)站推廣”以來，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

分布式系統(tǒng)理論基礎(chǔ) - 一致性、2PC和3PC

引言

狹義的分布式系統(tǒng)指由網(wǎng)絡(luò)連接的計(jì)算機(jī)系統(tǒng)，每個(gè)節(jié)點(diǎn)獨(dú)立地承擔(dān)計(jì)算或存儲(chǔ)任務(wù)，節(jié)點(diǎn)間通過網(wǎng)絡(luò)協(xié)同工作。廣義的分布式系統(tǒng)是一個(gè)相對(duì)的概念，正如 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.

一致性是分布式理論中的根本性問題，近半個(gè)世紀(jì)以來，科學(xué)家們圍繞著一致性問題提出了很多理論模型，依據(jù)這些理論模型，業(yè)界也出現(xiàn)了很多工程實(shí)踐投影。下面我們從一致性問題、特定條件下解決一致性問題的兩種方法(2PC、3PC)入門，了解最基礎(chǔ)的分布式系統(tǒng)理論。

一致性(consensus)

何為一致性問題？簡單而言，一致性問題就是相互獨(dú)立的節(jié)點(diǎn)之間如何達(dá)成一項(xiàng)決議的問題。分布式系統(tǒng)中，進(jìn)行數(shù)據(jù)庫事務(wù)提交(commit transaction)、Leader選舉、序列號(hào)生成等都會(huì)遇到一致性問題。這個(gè)問題在我們的日常生活中也很常見，比如牌友怎么商定幾點(diǎn)在哪打幾圈：

web分布式系統(tǒng)怎么理解

假設(shè)一個(gè)具有N個(gè)節(jié)點(diǎn)的分布式系統(tǒng)，當(dāng)其滿足以下條件時(shí)，我們說這個(gè)系統(tǒng)滿足一致性：

全認(rèn)同(agreement): 所有N個(gè)節(jié)點(diǎn)都認(rèn)同一個(gè)結(jié)果
值合法(validity): 該結(jié)果必須由N個(gè)節(jié)點(diǎn)中的節(jié)點(diǎn)提出
可結(jié)束(termination): 決議過程在一定時(shí)間內(nèi)結(jié)束，不會(huì)無休止地進(jìn)行下去

有人可能會(huì)說，決定什么時(shí)候在哪搓搓，4個(gè)人商量一下就ok，這不很簡單嗎？

但就這樣看似簡單的事情，分布式系統(tǒng)實(shí)現(xiàn)起來并不輕松，因?yàn)樗媾R著這些問題：

消息傳遞異步無序(asynchronous): 現(xiàn)實(shí)網(wǎng)絡(luò)不是一個(gè)可靠的信道，存在消息延時(shí)、丟失，節(jié)點(diǎn)間消息傳遞做不到同步有序(synchronous)
節(jié)點(diǎn)宕機(jī)(fail-stop): 節(jié)點(diǎn)持續(xù)宕機(jī)，不會(huì)恢復(fù)
節(jié)點(diǎn)宕機(jī)恢復(fù)(fail-recover): 節(jié)點(diǎn)宕機(jī)一段時(shí)間后恢復(fù)，在分布式系統(tǒng)中最常見
網(wǎng)絡(luò)分化(network partition): 網(wǎng)絡(luò)鏈路出現(xiàn)問題，將N個(gè)節(jié)點(diǎn)隔離成多個(gè)部分
拜占庭將軍問題(byzantine failure)^[2]: 節(jié)點(diǎn)或宕機(jī)或邏輯失敗，甚至不按套路出牌拋出干擾決議的信息

假設(shè)現(xiàn)實(shí)場景中也存在這樣的問題，我們看看結(jié)果會(huì)怎樣：

我: 老王，今晚7點(diǎn)老地方，搓夠48圈不見不散！
……
（第二天凌晨3點(diǎn)） 隔壁老王: 沒問題！ // 消息延遲
我: ……
----------------------------------------------
我: 小張，今晚7點(diǎn)老地方，搓夠48圈不見不散！
小張: No …… 
（兩小時(shí)后……）
小張: No problem！ // 宕機(jī)節(jié)點(diǎn)恢復(fù)
我: ……
-----------------------------------------------
我: 老李頭，今晚7點(diǎn)老地方，搓夠48圈不見不散！
還能不能一起愉快地玩耍...![](/upload/otherpic10/116770-20160313010025194-2394933.png)
我們把以上所列的問題稱為系統(tǒng)模型(system model)，討論分布式系統(tǒng)理論和工程實(shí)踐的時(shí)候，必先劃定模型。例如有以下兩種模型：
1.  異步環(huán)境(asynchronous)下，節(jié)點(diǎn)宕機(jī)(fail-stop)
2.  異步環(huán)境(asynchronous)下，節(jié)點(diǎn)宕機(jī)恢復(fù)(fail-recover)、網(wǎng)絡(luò)分化(network partition)
2比1多了節(jié)點(diǎn)恢復(fù)、網(wǎng)絡(luò)分化的考量，因而對(duì)這兩種模型的理論研究和工程解決方案必定是不同的，在還沒有明晰所要解決的問題前談解決方案都是一本正經(jīng)地耍流氓。
一致性還具備兩個(gè)屬性，一個(gè)是強(qiáng)一致(safety)，它要求所有節(jié)點(diǎn)狀態(tài)一致、共進(jìn)退；一個(gè)是可用(liveness)，它要求分布式系統(tǒng)24*7無間斷對(duì)外服務(wù)。FLP定理(FLP impossibility)[3][4] 已經(jīng)證明在一個(gè)收窄的模型中(異步環(huán)境并只存在節(jié)點(diǎn)宕機(jī))，不能同時(shí)滿足 safety 和 liveness。
FLP定理是分布式系統(tǒng)理論中的基礎(chǔ)理論，正如物理學(xué)中的能量守恒定律徹底否定了永動(dòng)機(jī)的存在，F(xiàn)LP定理否定了同時(shí)滿足safety 和 liveness 的一致性協(xié)議的存在。
![](/upload/otherpic10/116770-20160314181639599-564845788.jpg)
_《怦然心動(dòng) (Flipped)》，2010_ 
工程實(shí)踐上根據(jù)具體的業(yè)務(wù)場景，或保證強(qiáng)一致(safety)，或在節(jié)點(diǎn)宕機(jī)、網(wǎng)絡(luò)分化的時(shí)候保證可用(liveness)。2PC、3PC是相對(duì)簡單的解決一致性問題的協(xié)議，下面我們就來了解2PC和3PC。
**2PC**
2PC(tow phase commit)兩階段提交[5]顧名思義它分成兩個(gè)階段，先由一方進(jìn)行提議(propose)并收集其他節(jié)點(diǎn)的反饋(vote)，再根據(jù)反饋決定提交(commit)或中止(abort)事務(wù)。我們將提議的節(jié)點(diǎn)稱為協(xié)調(diào)者(coordinator)，其他參與決議節(jié)點(diǎn)稱為參與者(participants, 或cohorts)：
![](/upload/otherpic10/116770-20160313203429600-179395429.png)
_2PC, phase two_
在階段2中，coordinator根據(jù)participant的反饋，提交或中止事務(wù)，如果participant全部同意則提交，只要有一個(gè)participant不同意就中止。
在異步環(huán)境(asynchronous)并且沒有節(jié)點(diǎn)宕機(jī)(fail-stop)的模型下，2PC可以滿足全認(rèn)同、值合法、可結(jié)束，是解決一致性問題的一種協(xié)議。但如果再加上節(jié)點(diǎn)宕機(jī)(fail-recover)的考慮，2PC是否還能解決一致性問題呢？
coordinator如果在發(fā)起提議后宕機(jī)，那么participant將進(jìn)入阻塞(block)狀態(tài)、一直等待coordinator回應(yīng)以完成該次決議。這時(shí)需要另一角色把系統(tǒng)從不可結(jié)束的狀態(tài)中帶出來，我們把新增的這一角色叫協(xié)調(diào)者備份(coordinator watchdog)。coordinator宕機(jī)一定時(shí)間后，watchdog接替原coordinator工作，通過問詢(query) 各participant的狀態(tài)，決定階段2是提交還是中止。這也要求 coordinator/participant 記錄(logging)歷史狀態(tài)，以備coordinator宕機(jī)后watchdog對(duì)participant查詢、coordinator宕機(jī)恢復(fù)后重新找回狀態(tài)。
從coordinator接收到一次事務(wù)請(qǐng)求、發(fā)起提議到事務(wù)完成，經(jīng)過2PC協(xié)議后增加了2次RTT(propose+commit)，帶來的時(shí)延(latency)增加相對(duì)較少。
**3PC**
3PC(three phase commit)即三階段提交[6][7]，既然2PC可以在異步網(wǎng)絡(luò)+節(jié)點(diǎn)宕機(jī)恢復(fù)的模型下實(shí)現(xiàn)一致性，那還需要3PC做什么，3PC是什么鬼？
在2PC中一個(gè)participant的狀態(tài)只有它自己和coordinator知曉，假如coordinator提議后自身宕機(jī)，在watchdog啟用前一個(gè)participant又宕機(jī)，其他participant就會(huì)進(jìn)入既不能回滾、又不能強(qiáng)制commit的阻塞狀態(tài)，直到participant宕機(jī)恢復(fù)。這引出兩個(gè)疑問：
1.  能不能去掉阻塞，使系統(tǒng)可以在commit/abort前回滾(rollback)到?jīng)Q議發(fā)起前的初始狀態(tài)
2.  當(dāng)次決議中，participant間能不能相互知道對(duì)方的狀態(tài)，又或者participant間根本不依賴對(duì)方的狀態(tài)
相比2PC，3PC增加了一個(gè)準(zhǔn)備提交(prepare to commit)階段來解決以上問題：
![](/upload/otherpic10/116770-20160314002734304-489496391.png)
_圖片截取自wikipedia_
coordinator接收完participant的反饋(vote)之后，進(jìn)入階段2，給各個(gè)participant發(fā)送準(zhǔn)備提交(prepare to commit)指令。participant接到準(zhǔn)備提交指令后可以鎖資源，但要求相關(guān)操作必須可回滾。coordinator接收完確認(rèn)(ACK)后進(jìn)入階段3、進(jìn)行commit/abort，3PC的階段3與2PC的階段2無異。協(xié)調(diào)者備份(coordinator watchdog)、狀態(tài)記錄(logging)同樣應(yīng)用在3PC。
participant如果在不同階段宕機(jī)，我們來看看3PC如何應(yīng)對(duì)：
*   **階段1**: coordinator或watchdog未收到宕機(jī)participant的vote，直接中止事務(wù)；宕機(jī)的participant恢復(fù)后，讀取logging發(fā)現(xiàn)未發(fā)出贊成vote，自行中止該次事務(wù)
*   **階段2**: coordinator未收到宕機(jī)participant的precommit ACK，但因?yàn)橹耙呀?jīng)收到了宕機(jī)participant的贊成反饋(不然也不會(huì)進(jìn)入到階段2)，coordinator進(jìn)行commit；watchdog可以通過問詢其他participant獲得這些信息，過程同理；宕機(jī)的participant恢復(fù)后發(fā)現(xiàn)收到precommit或已經(jīng)發(fā)出贊成vote，則自行commit該次事務(wù)
*   **階段3**: 即便coordinator或watchdog未收到宕機(jī)participant的commit ACK，也結(jié)束該次事務(wù)；宕機(jī)的participant恢復(fù)后發(fā)現(xiàn)收到commit或者precommit，也將自行commit該次事務(wù)
因?yàn)橛辛藴?zhǔn)備提交(prepare to commit)階段，3PC的事務(wù)處理延時(shí)也增加了1個(gè)RTT，變?yōu)?個(gè)RTT(propose+precommit+commit)，但是它防止participant宕機(jī)后整個(gè)系統(tǒng)進(jìn)入阻塞態(tài)，增強(qiáng)了系統(tǒng)的可用性，對(duì)一些現(xiàn)實(shí)業(yè)務(wù)場景是非常值得的。
**小結(jié)**
以上介紹了分布式系統(tǒng)理論中的部分基礎(chǔ)知識(shí)，闡述了一致性(consensus)的定義和實(shí)現(xiàn)一致性所要面臨的問題，最后討論在異步網(wǎng)絡(luò)(asynchronous)、節(jié)點(diǎn)宕機(jī)恢復(fù)(fail-recover)模型下2PC、3PC怎么解決一致性問題。
閱讀前人對(duì)分布式系統(tǒng)的各項(xiàng)理論研究，其中有嚴(yán)謹(jǐn)?shù)赝评?、證明，有一種數(shù)學(xué)的美；觀現(xiàn)實(shí)中的分布式系統(tǒng)實(shí)現(xiàn)，是綜合各種因素下妥協(xié)的結(jié)果。
## 分布式系統(tǒng)理論基礎(chǔ) - 選舉、多數(shù)派和租約
選舉(election)是分布式系統(tǒng)實(shí)踐中常見的問題，通過打破節(jié)點(diǎn)間的對(duì)等關(guān)系，選得的leader(或叫master、coordinator)有助于實(shí)現(xiàn)事務(wù)原子性、提升決議效率。 多數(shù)派(quorum)的思路幫助我們?cè)诰W(wǎng)絡(luò)分化的情況下達(dá)成決議一致性，在leader選舉的場景下幫助我們選出唯一leader。租約(lease)在一定期限內(nèi)給予節(jié)點(diǎn)特定權(quán)利，也可以用于實(shí)現(xiàn)leader選舉。
下面我們就來學(xué)習(xí)分布式系統(tǒng)理論中的選舉、多數(shù)派和租約。
**選舉(electioin)**
一致性問題(consistency)是獨(dú)立的節(jié)點(diǎn)間如何達(dá)成決議的問題，選出大家都認(rèn)可的leader本質(zhì)上也是一致性問題，因而如何應(yīng)對(duì)宕機(jī)恢復(fù)、網(wǎng)絡(luò)分化等在leader選舉中也需要考量。
Bully算法[1]是最常見的選舉算法，其要求每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)序號(hào)，序號(hào)最高的節(jié)點(diǎn)為leader。leader宕機(jī)后次高序號(hào)的節(jié)點(diǎn)被重選為leader，過程如下：
![](/upload/otherpic10/116770-20160814110211906-1201598126.png)
(a). 節(jié)點(diǎn)4發(fā)現(xiàn)leader不可達(dá)，向序號(hào)比自己高的節(jié)點(diǎn)發(fā)起重新選舉，重新選舉消息中帶上自己的序號(hào)
(b)(c). 節(jié)點(diǎn)5、6接收到重選信息后進(jìn)行序號(hào)比較，發(fā)現(xiàn)自身的序號(hào)更大，向節(jié)點(diǎn)4返回OK消息并各自向更高序號(hào)節(jié)點(diǎn)發(fā)起重新選舉
(d). 節(jié)點(diǎn)5收到節(jié)點(diǎn)6的OK消息，而節(jié)點(diǎn)6經(jīng)過超時(shí)時(shí)間后收不到更高序號(hào)節(jié)點(diǎn)的OK消息，則認(rèn)為自己是leader
(e). 節(jié)點(diǎn)6把自己成為leader的信息廣播到所有節(jié)點(diǎn)
回顧[《分布式系統(tǒng)理論基礎(chǔ) - 一致性、2PC和3PC》](http://www.cnblogs.com/bangerlee/p/5268485.html)就可以看到，Bully算法中有2PC的身影，都具有提議(propose)和收集反饋(vote)的過程。
在一致性算法[Paxos](http://www.cnblogs.com/bangerlee/p/5655754.html)、ZAB[2]、Raft[3]中，為提升決議效率均有節(jié)點(diǎn)充當(dāng)leader的角色。ZAB、Raft中描述了具體的leader選舉實(shí)現(xiàn)，與Bully算法類似ZAB中使用zxid標(biāo)識(shí)節(jié)點(diǎn)，具有大zxid的節(jié)點(diǎn)表示其所具備的事務(wù)(transaction)最新、被選為leader。
**多數(shù)派(quorum)**
在網(wǎng)絡(luò)分化的場景下以上Bully算法會(huì)遇到一個(gè)問題，被分隔的節(jié)點(diǎn)都認(rèn)為自己具有大的序號(hào)、將產(chǎn)生多個(gè)leader，這時(shí)候就需要引入多數(shù)派(quorum)[4]。多數(shù)派的思路在分布式系統(tǒng)中很常見，其確保網(wǎng)絡(luò)分化情況下決議唯一。
多數(shù)派的原理說起來很簡單，假如節(jié)點(diǎn)總數(shù)為2f+1，則一項(xiàng)決議得到多于 f 節(jié)點(diǎn)贊成則獲得通過。leader選舉中，網(wǎng)絡(luò)分化場景下只有具備多數(shù)派節(jié)點(diǎn)的部分才可能選出leader，這避免了多l(xiāng)eader的產(chǎn)生。
![](/upload/otherpic10/116770-20160814195846250-9979865.png)
多數(shù)派的思路還被應(yīng)用于副本(replica)管理，根據(jù)業(yè)務(wù)實(shí)際讀寫比例調(diào)整寫副本數(shù)Vw、讀副本數(shù)Vr，用以在可靠性和性能方面取得平衡[5]。
**租約(lease)**
選舉中很重要的一個(gè)問題，以上尚未提到：怎么判斷l(xiāng)eader不可用、什么時(shí)候應(yīng)該發(fā)起重新選舉？最先可能想到會(huì)通過心跳(heart beat)判別leader狀態(tài)是否正常，但在網(wǎng)絡(luò)擁塞或瞬斷的情況下，這容易導(dǎo)致出現(xiàn)雙主。
租約(lease)是解決該問題的常用方法，其最初提出時(shí)用于解決分布式緩存一致性問題[6]，后面在分布式鎖[7]等很多方面都有應(yīng)用。
![](/upload/otherpic10/116770-20160821195833933-818514275.png) 
租約的原理同樣不復(fù)雜，中心思想是每次租約時(shí)長內(nèi)只有一個(gè)節(jié)點(diǎn)獲得租約、到期后必須重新頒發(fā)租約。假設(shè)我們有租約頒發(fā)節(jié)點(diǎn)Z，節(jié)點(diǎn)0、1和2競選leader，租約過程如下：
(a). 節(jié)點(diǎn)0、1、2在Z上注冊(cè)自己，Z根據(jù)一定的規(guī)則(例如先到先得)頒發(fā)租約給節(jié)點(diǎn)，該租約同時(shí)對(duì)應(yīng)一個(gè)有效時(shí)長；這里假設(shè)節(jié)點(diǎn)0獲得租約、成為leader
(b). leader宕機(jī)時(shí)，只有租約到期(timeout)后才重新發(fā)起選舉，這里節(jié)點(diǎn)1獲得租約、成為leader
租約機(jī)制確保了一個(gè)時(shí)刻最多只有一個(gè)leader，避免只使用心跳機(jī)制產(chǎn)生雙主的問題。在實(shí)踐應(yīng)用中，zookeeper、ectd可用于租約頒發(fā)。
**小結(jié)**
在分布式系統(tǒng)理論和實(shí)踐中，常見leader、quorum和lease的身影。分布式系統(tǒng)內(nèi)不一定事事協(xié)商、事事民主，leader的存在有助于提升決議效率。
本文以leader選舉作為例子引入和講述quorum、lease，當(dāng)然quorum和lease是兩種思想，并不限于leader選舉應(yīng)用。
最后提一個(gè)有趣的問題與大家思考，leader選舉的本質(zhì)是一致性問題，Paxos、Raft和ZAB等解決一致性問題的協(xié)議和算法本身又需要或依賴于leader，怎么理解這個(gè)看似“蛋生雞、雞生蛋”的問題？[8]## 分布式系統(tǒng)理論基礎(chǔ) - 時(shí)間、時(shí)鐘和事件順序
> 十六號(hào)…… 四月十六號(hào)。一九六零年四月十六號(hào)下午三點(diǎn)之前的一分鐘你和我在一起，因?yàn)槟阄視?huì)記住這一分鐘。從現(xiàn)在開始我們就是一分鐘的朋友，這是事實(shí)，你改變不了，因?yàn)橐呀?jīng)過去了。我明天會(huì)再來。
> 
>     —— 《阿飛正傳》
現(xiàn)實(shí)生活中時(shí)間是很重要的概念，時(shí)間可以記錄事情發(fā)生的時(shí)刻、比較事情發(fā)生的先后順序。分布式系統(tǒng)的一些場景也需要記錄和比較不同節(jié)點(diǎn)間事件發(fā)生的順序，但不同于日常生活使用物理時(shí)鐘記錄時(shí)間，分布式系統(tǒng)使用邏輯時(shí)鐘記錄事件順序關(guān)系，下面我們來看分布式系統(tǒng)中幾種常見的邏輯時(shí)鐘。
**物理時(shí)鐘 vs 邏輯時(shí)鐘**
可能有人會(huì)問，為什么分布式系統(tǒng)不使用物理時(shí)鐘(physical clock)記錄事件？每個(gè)事件對(duì)應(yīng)打上一個(gè)時(shí)間戳，當(dāng)需要比較順序的時(shí)候比較相應(yīng)時(shí)間戳就好了。
這是因?yàn)楝F(xiàn)實(shí)生活中物理時(shí)間有統(tǒng)一的標(biāo)準(zhǔn)，而分布式系統(tǒng)中每個(gè)節(jié)點(diǎn)記錄的時(shí)間并不一樣，即使設(shè)置了 [NTP](http://www.zhihu.com/question/24960940) 時(shí)間同步節(jié)點(diǎn)間也存在毫秒級(jí)別的偏差[1][2]。因而分布式系統(tǒng)需要有另外的方法記錄事件順序關(guān)系，這就是邏輯時(shí)鐘(logical clock)。
![](/upload/otherpic10/116770-20160501174922566-1686627384.png)
_圖1: Lamport timestamps space time (圖片來源: wikipedia)_
1.  每個(gè)事件對(duì)應(yīng)一個(gè)Lamport時(shí)間戳，初始值為0
2.  如果事件在節(jié)點(diǎn)內(nèi)發(fā)生，時(shí)間戳加1
3.  如果事件屬于發(fā)送事件，時(shí)間戳加1并在消息中帶上該時(shí)間戳
4.  如果事件屬于接收事件，時(shí)間戳 = Max(本地時(shí)間戳，消息中的時(shí)間戳) + 1
假設(shè)有事件a、b，C(a)、C(b)分別表示事件a、b對(duì)應(yīng)的Lamport時(shí)間戳，如果C(a) < C(b)，則有a發(fā)生在b之前(happened before)，記作 a -> b，例如圖1中有 C1 -> B1。通過該定義，事件集中Lamport時(shí)間戳不等的事件可進(jìn)行比較，我們獲得事件的[偏序關(guān)系](https://en.wikipedia.org/wiki/Partially_ordered_set#Formal_definition)(partial order)。
如果C(a) = C(b)，那a、b事件的順序又是怎樣的？假設(shè)a、b分別在節(jié)點(diǎn)P、Q上發(fā)生，Pi、Qj分別表示我們給P、Q的編號(hào)，如果 C(a) = C(b) 并且 Pi j，同樣定義為a發(fā)生在b之前，記作 a => b。假如我們對(duì)圖1的A、B、C分別編號(hào)Ai = 1、Bj = 2、Ck = 3，因 C(B4) = C(C3) 并且 Bj < Ck，則 B4 => C3。
通過以上定義，我們可以對(duì)所有事件排序、獲得事件的[全序關(guān)系](https://en.wikipedia.org/wiki/Total_order)(total order)。上圖例子，我們可以從C1到A4進(jìn)行排序。
**Vector clock**
Lamport時(shí)間戳幫助我們得到事件順序關(guān)系，但還有一種順序關(guān)系不能用Lamport時(shí)間戳很好地表示出來，那就是同時(shí)發(fā)生關(guān)系(concurrent)[4]。例如圖1中事件B4和事件C3沒有因果關(guān)系，屬于同時(shí)發(fā)生事件，但Lamport時(shí)間戳定義兩者有先后順序。
Vector clock是在Lamport時(shí)間戳基礎(chǔ)上演進(jìn)的另一種邏輯時(shí)鐘方法，它通過vector結(jié)構(gòu)不但記錄本節(jié)點(diǎn)的Lamport時(shí)間戳，同時(shí)也記錄了其他節(jié)點(diǎn)的Lamport時(shí)間戳[5][6]。Vector clock的原理與Lamport時(shí)間戳類似，使用圖例如下：
![](/upload/otherpic10/116770-20160502134654404-1109556515.png)
_圖2: Vector clock space time (_圖片來源: wikipedia)__
假設(shè)有事件a、b分別在節(jié)點(diǎn)P、Q上發(fā)生，Vector clock分別為Ta、Tb，如果 Tb[Q] > Ta[Q] 并且 Tb[P] >= Ta[P]，則a發(fā)生于b之前，記作 a -> b。到目前為止還和Lamport時(shí)間戳差別不大，那Vector clock怎么判別同時(shí)發(fā)生關(guān)系呢？
如果 Tb[Q] > Ta[Q] 并且 Tb[P] < Ta[P]，則認(rèn)為a、b同時(shí)發(fā)生，記作 a 
 b。例如圖2中節(jié)點(diǎn)B上的第4個(gè)事件 (A:2，B:4，C:1) 與節(jié)點(diǎn)C上的第2個(gè)事件 (B:3，C:2) 沒有因果關(guān)系、屬于同時(shí)發(fā)生事件。
**Version vector**
基于Vector clock我們可以獲得任意兩個(gè)事件的順序關(guān)系，結(jié)果或?yàn)橄群箜樞蚧驗(yàn)橥瑫r(shí)發(fā)生，識(shí)別事件順序在工程實(shí)踐中有很重要的引申應(yīng)用，最常見的應(yīng)用是發(fā)現(xiàn)數(shù)據(jù)沖突(detect conflict)。
分布式系統(tǒng)中數(shù)據(jù)一般存在多個(gè)副本(replication)，多個(gè)副本可能被同時(shí)更新，這會(huì)引起副本間數(shù)據(jù)不一致[7]，Version vector的實(shí)現(xiàn)與Vector clock非常類似[8]，目的用于發(fā)現(xiàn)數(shù)據(jù)沖突[9]。下面通過一個(gè)例子說明Version vector的用法[10]：
![](/upload/otherpic10/116770-20160502183034013-800335383.png)
_圖3: Version vector_
*   client端寫入數(shù)據(jù)，該請(qǐng)求被Sx處理并創(chuàng)建相應(yīng)的vector ([Sx, 1])，記為數(shù)據(jù)D1
*   第2次請(qǐng)求也被Sx處理，數(shù)據(jù)修改為D2，vector修改為([Sx, 2])
*   第3、第4次請(qǐng)求分別被Sy、Sz處理，client端先讀取到D2，然后D3、D4被寫入Sy、Sz*   第5次更新時(shí)client端讀取到D2、D3和D4 3個(gè)數(shù)據(jù)版本，通過類似Vector clock判斷同時(shí)發(fā)生關(guān)系的方法可判斷D3、D4存在數(shù)據(jù)沖突，最終通過一定方法解決數(shù)據(jù)沖突并寫入D5
Vector clock只用于發(fā)現(xiàn)數(shù)據(jù)沖突，不能解決數(shù)據(jù)沖突。如何解決數(shù)據(jù)沖突因場景而異，具體方法有以最后更新為準(zhǔn)(last write win)，或?qū)_突的數(shù)據(jù)交給client由client端決定如何處理，或通過quorum決議事先避免數(shù)據(jù)沖突的情況發(fā)生[11]。
由于記錄了所有數(shù)據(jù)在所有節(jié)點(diǎn)上的邏輯時(shí)鐘信息，Vector clock和Version vector在實(shí)際應(yīng)用中可能面臨的一個(gè)問題是vector過大，用于數(shù)據(jù)管理的元數(shù)據(jù)(meta data)甚至大于數(shù)據(jù)本身[12]。
解決該問題的方法是使用server id取代client id創(chuàng)建vector (因?yàn)閟erver的數(shù)量相對(duì)client穩(wěn)定)，或設(shè)定大的size、如果超過該size值則淘汰最舊的vector信息[10][13]。
**小結(jié)**
以上介紹了分布式系統(tǒng)里邏輯時(shí)鐘的表示方法，通過Lamport timestamps可以建立事件的全序關(guān)系，通過Vector clock可以比較任意兩個(gè)事件的順序關(guān)系并且能表示無因果關(guān)系的事件，將Vector clock的方法用于發(fā)現(xiàn)數(shù)據(jù)版本沖突，于是有了Version vector。
## 分布式系統(tǒng)理論基礎(chǔ) - CAP
**引言**
CAP是分布式系統(tǒng)、特別是分布式存儲(chǔ)領(lǐng)域中被討論最多的理論，“[什么是CAP定理？](https://www.quora.com/What-Is-CAP-Theorem-1)”在Quora 分布式系統(tǒng)分類下排名 FAQ 的 No.1。CAP在程序員中也有較廣的普及，它不僅僅是“C、A、P不能同時(shí)滿足，最多只能3選2”，以下嘗試綜合各方觀點(diǎn)，從發(fā)展歷史、工程實(shí)踐等角度講述CAP理論。希望大家透過本文對(duì)CAP理論有更多地了解和認(rèn)識(shí)。
**CAP定理**
CAP由[Eric Brewer](https://en.wikipedia.org/wiki/Eric_Brewer_(scientist))在2000年P(guān)ODC會(huì)議上提出[1][2]，是Eric Brewer在Inktomi[3]期間研發(fā)搜索引擎、分布式web緩存時(shí)得出的關(guān)于數(shù)據(jù)一致性(consistency)、服務(wù)可用性(availability)、分區(qū)容錯(cuò)性(partition-tolerance)的猜想：
> It is impossible for a web service to provide the three following guarantees : Consistency, Availability and Partition-tolerance.
該猜想在提出兩年后被證明成立[4]，成為我們熟知的CAP定理：
*   **數(shù)據(jù)一致性**(consistency)：如果系統(tǒng)對(duì)一個(gè)寫操作返回成功，那么之后的讀請(qǐng)求都必須讀到這個(gè)新數(shù)據(jù)；如果返回失敗，那么所有讀操作都不能讀到這個(gè)數(shù)據(jù)，對(duì)調(diào)用者而言數(shù)據(jù)具有強(qiáng)一致性(strong consistency) (又叫原子性 atomic、線性一致性 linearizable consistency)[5]*   **服務(wù)可用性**(availability)：所有讀寫請(qǐng)求在一定時(shí)間內(nèi)得到響應(yīng)，可終止、不會(huì)一直等待
*   **分區(qū)容錯(cuò)性**(partition-tolerance)：在網(wǎng)絡(luò)分區(qū)的情況下，被分隔的節(jié)點(diǎn)仍能正常對(duì)外服務(wù)
在某時(shí)刻如果滿足AP，分隔的節(jié)點(diǎn)同時(shí)對(duì)外服務(wù)但不能相互通信，將導(dǎo)致狀態(tài)不一致，即不能滿足C；如果滿足CP，網(wǎng)絡(luò)分區(qū)的情況下為達(dá)成C，請(qǐng)求只能一直等待，即不滿足A；如果要滿足CA，在一定時(shí)間內(nèi)要達(dá)到節(jié)點(diǎn)狀態(tài)一致，要求不能出現(xiàn)網(wǎng)絡(luò)分區(qū)，則不能滿足P。
C、A、P三者最多只能滿足其中兩個(gè)，和FLP定理一樣，CAP定理也指示了一個(gè)不可達(dá)的結(jié)果(impossibility result)。
![](/upload/otherpic10/116770-20160329205542613-1908405713.jpg)
**CAP的工程啟示**
CAP理論提出7、8年后，NoSql圈將CAP理論當(dāng)作對(duì)抗傳統(tǒng)關(guān)系型數(shù)據(jù)庫的依據(jù)、闡明自己放寬對(duì)數(shù)據(jù)一致性(consistency)要求的正確性[6]，隨后引起了大范圍關(guān)于CAP理論的討論。
CAP理論看似給我們出了一道3選2的選擇題，但在工程實(shí)踐中存在很多現(xiàn)實(shí)限制條件，需要我們做更多地考量與權(quán)衡，避免進(jìn)入CAP認(rèn)識(shí)誤區(qū)[7]。
**1、關(guān)于 P 的理解**
Partition字面意思是網(wǎng)絡(luò)分區(qū)，即因網(wǎng)絡(luò)因素將系統(tǒng)分隔為多個(gè)單獨(dú)的部分，有人可能會(huì)說，網(wǎng)絡(luò)分區(qū)的情況發(fā)生概率非常小啊，是不是不用考慮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.
網(wǎng)絡(luò)分區(qū)的情況符合該定義，網(wǎng)絡(luò)丟包的情況也符合以上定義，另外節(jié)點(diǎn)宕機(jī)，其他節(jié)點(diǎn)發(fā)往宕機(jī)節(jié)點(diǎn)的包也將丟失，這種情況同樣符合定義。現(xiàn)實(shí)情況下我們面對(duì)的是一個(gè)不可靠的網(wǎng)絡(luò)、有一定概率宕機(jī)的設(shè)備，這兩個(gè)因素都會(huì)導(dǎo)致Partition，因而分布式系統(tǒng)實(shí)現(xiàn)中 P 是一個(gè)必須項(xiàng)，而不是可選項(xiàng)[9][10]。
對(duì)于分布式系統(tǒng)工程實(shí)踐，CAP理論更合適的描述是：在滿足分區(qū)容錯(cuò)的前提下，沒有算法能同時(shí)滿足數(shù)據(jù)一致性和服務(wù)可用性[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 是必選項(xiàng)，那3選2的選擇題不就變成數(shù)據(jù)一致性(consistency)、服務(wù)可用性(availability) 2選1？工程實(shí)踐中一致性有不同程度，可用性也有不同等級(jí)，在保證分區(qū)容錯(cuò)性的前提下，放寬約束后可以兼顧一致性和可用性，兩者不是非此即彼[12]。
![](/upload/otherpic10/116770-20160401221124957-2025686892.jpg)
CAP定理證明中的一致性指強(qiáng)一致性，強(qiáng)一致性要求多節(jié)點(diǎn)組成的被調(diào)要能像單節(jié)點(diǎn)一樣運(yùn)作、操作具備原子性，數(shù)據(jù)在時(shí)間、時(shí)序上都有要求。如果放寬這些要求，還有其他一致性類型：
*   序列一致性(sequential consistency)[13]：不要求時(shí)序一致，A操作先于B操作，在B操作后如果所有調(diào)用端讀操作得到A操作的結(jié)果，滿足序列一致性
*   最終一致性(eventual consistency)[14]：放寬對(duì)時(shí)間的要求，在被調(diào)完成操作響應(yīng)后的某個(gè)時(shí)間點(diǎn)，被調(diào)多個(gè)節(jié)點(diǎn)的數(shù)據(jù)最終達(dá)成一致
可用性在CAP定理里指所有讀寫操作必須要能終止，實(shí)際應(yīng)用中從主調(diào)、被調(diào)兩個(gè)不同的視角，可用性具有不同的含義。當(dāng)P(網(wǎng)絡(luò)分區(qū))出現(xiàn)時(shí)，主調(diào)可以只支持讀操作，通過犧牲部分可用性達(dá)成數(shù)據(jù)一致。
工程實(shí)踐中，較常見的做法是通過異步拷貝副本(asynchronous replication)、quorum/NRW，實(shí)現(xiàn)在調(diào)用端看來數(shù)據(jù)強(qiáng)一致、被調(diào)端最終一致，在調(diào)用端看來服務(wù)可用、被調(diào)端允許部分節(jié)點(diǎn)不可用(或被網(wǎng)絡(luò)分隔)的效果[15]。
**3、跳出CAP**
CAP理論對(duì)實(shí)現(xiàn)分布式系統(tǒng)具有指導(dǎo)意義，但CAP理論并沒有涵蓋分布式工程實(shí)踐中的所有重要因素。
例如延時(shí)(latency)，它是衡量系統(tǒng)可用性、與用戶體驗(yàn)直接相關(guān)的一項(xiàng)重要指標(biāo)[16]。CAP理論中的可用性要求操作能終止、不無休止地進(jìn)行，除此之外，我們還關(guān)心到底需要多長時(shí)間能結(jié)束操作，這就是延時(shí)，它值得我們?cè)O(shè)計(jì)、實(shí)現(xiàn)分布式系統(tǒng)時(shí)單列出來考慮。
延時(shí)與數(shù)據(jù)一致性也是一對(duì)“冤家”，如果要達(dá)到強(qiáng)一致性、多個(gè)副本數(shù)據(jù)一致，必然增加延時(shí)。加上延時(shí)的考量，我們得到一個(gè)CAP理論的修改版本PACELC[17]：如果出現(xiàn)P(網(wǎng)絡(luò)分區(qū))，如何在A(服務(wù)可用性)、C(數(shù)據(jù)一致性)之間選擇；否則，如何在L(延時(shí))、C(數(shù)據(jù)一致性)之間選擇。
**小結(jié)**
以上介紹了CAP理論的源起和發(fā)展，介紹了CAP理論給分布式系統(tǒng)工程實(shí)踐帶來的啟示。
CAP理論對(duì)分布式系統(tǒng)實(shí)現(xiàn)有非常重大的影響，我們可以根據(jù)自身的業(yè)務(wù)特點(diǎn)，在數(shù)據(jù)一致性和服務(wù)可用性之間作出傾向性地選擇。通過放松約束條件，我們可以實(shí)現(xiàn)在不同時(shí)間點(diǎn)滿足CAP(此CAP非CAP定理中的CAP，如C替換為最終一致性)[18][19][20]。
有非常非常多文章討論和研究CAP理論，希望這篇對(duì)你認(rèn)識(shí)和了解CAP理論有幫助。
## 分布式系統(tǒng)理論進(jìn)階 - Paxos
**引言**
[《分布式系統(tǒng)理論基礎(chǔ) - 一致性、2PC和3PC》](http://www.cnblogs.com/bangerlee/p/5268485.html)一文介紹了一致性、達(dá)成一致性需要面臨的各種問題以及2PC、3PC模型，Paxos協(xié)議在節(jié)點(diǎn)宕機(jī)恢復(fù)、消息無序或丟失、網(wǎng)絡(luò)分化的場景下能保證決議的一致性，是被討論最廣泛的一致性協(xié)議。
Paxos協(xié)議同時(shí)又以其“艱深晦澀”著稱，下面結(jié)合 [Paxos Made Simple](http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf)、[The Part-Time Parliament](http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf) 兩篇論文，嘗試通過Paxos推演、學(xué)習(xí)和了解Paxos協(xié)議。
**Basic Paxos**
何為一致性問題？簡單而言，一致性問題是在節(jié)點(diǎn)宕機(jī)、消息無序等場景可能出現(xiàn)的情況下，相互獨(dú)立的節(jié)點(diǎn)之間如何達(dá)成決議的問題，作為解決一致性問題的協(xié)議，Paxos的核心是節(jié)點(diǎn)間如何確定并只確定一個(gè)值(value)。
也許你會(huì)疑惑只確定一個(gè)值能起什么作用，在Paxos協(xié)議里確定并只確定一個(gè)值是確定多值的基礎(chǔ)，如何確定多值將在第二部分Multi Paxos中介紹，這部分我們聚焦在“Paxos如何確定并只確定一個(gè)值”這一問題上。
![](/upload/otherpic10/116770-20160711232543717-973749854.gif)
和2PC類似，Paxos先把節(jié)點(diǎn)分成兩類，發(fā)起提議(proposal)的一方為proposer，參與決議的一方為acceptor。假如只有一個(gè)proposer發(fā)起提議，并且節(jié)點(diǎn)不宕機(jī)、消息不丟包，那么acceptor做到以下這點(diǎn)就可以確定一個(gè)值：**P1**. 一個(gè)acceptor接受它收到的第一項(xiàng)提議當(dāng)然上面要求的前提條件有些嚴(yán)苛，節(jié)點(diǎn)不能宕機(jī)、消息不能丟包，還只能由一個(gè)proposer發(fā)起提議。我們嘗試放寬條件，假設(shè)多個(gè)proposer可以同時(shí)發(fā)起提議，又怎樣才能做到確定并只確定一個(gè)值呢？首先proposer和acceptor需要滿足以下兩個(gè)條件：1. proposer發(fā)起的每項(xiàng)提議分別用一個(gè)ID標(biāo)識(shí)，提議的組成因此變?yōu)?ID, value)acceptor可以接受(accept)不止一項(xiàng)提議，當(dāng)多數(shù)(quorum) acceptor接受一項(xiàng)提議時(shí)該提議被確定(chosen)(注: 注意以上“接受”和“確定”的區(qū)別）我們約定后面發(fā)起的提議的ID比前面提議的ID大，并假設(shè)可以有多項(xiàng)提議被確定，為做到確定并只確定一個(gè)值acceptor要做到以下這點(diǎn)：**P2**. 如果一項(xiàng)值為v的提議被確定，那么后續(xù)只確定值為v的提議(注: 乍看這個(gè)條件不太好理解，謹(jǐn)記目標(biāo)是“確定并只確定一個(gè)值”)由于一項(xiàng)提議被確定(chosen)前必須先被多數(shù)派acceptor接受(accepted)，為實(shí)現(xiàn)P2，實(shí)質(zhì)上acceptor需要做到：**P2a**. 如果一項(xiàng)值為v的提議被確定，那么acceptor后續(xù)只接受值為v的提議滿足P2a則P2成立 (P2a => P2)。目前在多個(gè)proposer可以同時(shí)發(fā)起提議的情況下，滿足P1、P2a即能做到確定并只確定一個(gè)值。如果再加上節(jié)點(diǎn)宕機(jī)恢復(fù)、消息丟包的考量呢？假設(shè)acceptor c 宕機(jī)一段時(shí)間后恢復(fù)，c 宕機(jī)期間其他acceptor已經(jīng)確定了一項(xiàng)值為v的決議但c 因?yàn)殄礄C(jī)并不知曉；c 恢復(fù)后如果有proposer馬上發(fā)起一項(xiàng)值不是v的提議，由于條件P1，c 會(huì)接受該提議，這與P2a矛盾。為了避免這樣的情況出現(xiàn)，進(jìn)一步地我們對(duì)proposer作約束：**P2b**. 如果一項(xiàng)值為v的提議被確定，那么proposer后續(xù)只發(fā)起值為v的提議滿足P2b則P2a成立 (P2b => P2a => P2)。P2b約束的是提議被確定(chosen)后proposer的行為，我們更關(guān)心提議被確定前proposer應(yīng)該怎么做：**P2c**. 對(duì)于提議(n,v)，acceptor的多數(shù)派S中，如果存在acceptor最近一次(即ID值大)接受的提議的值為v'，那么要求v = v'；否則v可為任意值滿足P2c則P2b成立 (P2c => P2b => P2a => P2)。條件P2c是Basic Paxos的核心，光看P2c的描述可能會(huì)覺得一頭霧水，我們通過 
The Part-Time Parliament 中的例子加深理解：假設(shè)有A~E 5個(gè)acceptor，- 表示acceptor因宕機(jī)等原因缺席當(dāng)次決議，x 表示acceptor不接受提議，o 表示接受提議；多數(shù)派acceptor接受提議后提議被確定，以上表格對(duì)應(yīng)的決議過程如下：ID為2的提議最早提出，根據(jù)P2c其提議值可為任意值，這里假設(shè)為aacceptor A/B/C/E 在之前的決議中沒有接受(accept)任何提議，因而ID為5的提議的值也可以為任意值，這里假設(shè)為bacceptor B/D/E，其中D曾接受ID為2的提議，根據(jù)P2c，該輪ID為14的提議的值必須與ID為2的提議的值相同，為aacceptor A/C/D，其中D曾接受ID為2的提議、C曾接受ID為5的提議，相比之下ID 5較ID 2大，根據(jù)P2c，該輪ID為27的提議的值必須與ID為5的提議的值相同，為b；該輪決議被多數(shù)派acceptor接受，因此該輪決議得以確定acceptor B/C/D，3個(gè)acceptor之前都接受過提議，相比之下C、D曾接受的ID 27的ID號(hào)大，該輪ID為29的提議的值必須與ID為27的提議的值相同，為b以上提到的各項(xiàng)約束條件可以歸納為3點(diǎn)，如果proposer/acceptor滿足下面3點(diǎn)，那么在少數(shù)節(jié)點(diǎn)宕機(jī)、網(wǎng)絡(luò)分化隔離的情況下，在“確定并只確定一個(gè)值”這件事情上可以保證一致性(consistency)：B1(?): ?中每一輪決議都有唯一的ID標(biāo)識(shí)B2(?): 如果決議B被acceptor多數(shù)派接受，則確定決議BB3(?): 對(duì)于?中的任意提議B(n,v)，acceptor的多數(shù)派中如果存在acceptor最近一次(即ID值大)接受的提議的值為v’，那么要求v = v’；否則v可為任意值(注: 希臘字母?表示多輪決議的集合，字母B表示一輪決議)另外為保證P2c，我們對(duì)acceptor作兩個(gè)要求：1. 記錄曾接受的ID大的提議，因proposer需要問詢?cè)撔畔⒁詻Q定提議值2. 在回應(yīng)提議ID為n的proposer自己曾接受過ID大的提議時(shí)，acceptor同時(shí)保證(promise)不再接受ID小于n的提議至此，proposer/acceptor完成一輪決議可歸納為prepare和accept兩個(gè)階段。prepare階段proposer發(fā)起提議問詢提議值、acceptor回應(yīng)問詢并進(jìn)行promise；accept階段完成決議，圖示如下：還有一個(gè)問題需要考量，假如proposer A發(fā)起ID為n的提議，在提議未完成前proposer B又發(fā)起ID為n+1的提議，在n+1提議未完成前proposer C又發(fā)起ID為n+2的提議…… 如此acceptor不能完成決議、形成活鎖(livelock)，雖然這不影響一致性，但我們一般不想讓這樣的情況發(fā)生。解決的方法是從proposer中選出一個(gè)leader，提議統(tǒng)一由leader發(fā)起。最后我們?cè)僖胍粋€(gè)新的角色：learner，learner依附于acceptor，用于習(xí)得已確定的決議。以上決議過程都只要求acceptor多數(shù)派參與，而我們希望盡量所有acceptor的狀態(tài)一致。如果部分acceptor因宕機(jī)等原因未知曉已確定決議，宕機(jī)恢復(fù)后可經(jīng)本機(jī)learner采用pull的方式從其他acceptor習(xí)得。Multi Paxos通過以上步驟分布式系統(tǒng)已經(jīng)能確定一個(gè)值，“只確定一個(gè)值有什么用？這可解決不了我面臨的問題?！?nbsp;你心中可能有這樣的疑問。其實(shí)不斷地進(jìn)行“確定一個(gè)值”的過程、再為每個(gè)過程編上序號(hào)，就能得到具有全序關(guān)系(total order)的系列值，進(jìn)而能應(yīng)用在數(shù)據(jù)庫副本存儲(chǔ)等很多場景。我們把單次“確定一個(gè)值”的過程稱為實(shí)例(instance)，它由proposer/acceptor/learner組成，下圖說明了A/B/C三機(jī)上的實(shí)例：不同序號(hào)的實(shí)例之間互相不影響，A/B/C三機(jī)輸入相同、過程實(shí)質(zhì)等同于執(zhí)行相同序列的狀態(tài)機(jī)(state machine)指令 ，因而將得到一致的結(jié)果。proposer leader在Multi Paxos中還有助于提升性能，常態(tài)下統(tǒng)一由leader發(fā)起提議，可節(jié)省prepare步驟(leader不用問詢acceptor曾接受過的ID大的提議、只有l(wèi)eader提議也不需要acceptor進(jìn)行promise)直至發(fā)生leader宕機(jī)、重新選主。小結(jié)以上介紹了Paxos的推演過程、如何在Basic Paxos的基礎(chǔ)上通過狀態(tài)機(jī)構(gòu)建Multi Paxos。Paxos協(xié)議比較“艱深晦澀”，但多讀幾遍論文一般能理解其內(nèi)涵，更難的是如何將Paxos真正應(yīng)用到工程實(shí)踐。微信后臺(tái)開發(fā)同學(xué)實(shí)現(xiàn)并開源了一套基于Paxos協(xié)議的多機(jī)狀態(tài)拷貝類庫
PhxPaxos，PhxPaxos用于將單機(jī)服務(wù)擴(kuò)展到多機(jī)，其經(jīng)過線上系統(tǒng)驗(yàn)證并在一致性保證、性能等方面作了很多考量。分布式系統(tǒng)理論進(jìn)階 - Raft、Zab引言《分布式系統(tǒng)理論進(jìn)階 - Paxos》介紹了一致性協(xié)議Paxos，今天我們來學(xué)習(xí)另外兩個(gè)常見的一致性協(xié)議——Raft和Zab。通過與Paxos對(duì)比，了解Raft和Zab的核心思想、加深對(duì)一致性協(xié)議的認(rèn)識(shí)。RaftPaxos偏向于理論、對(duì)如何應(yīng)用到工程實(shí)踐提及較少。理解的難度加上現(xiàn)實(shí)的骨感，在生產(chǎn)環(huán)境中基于Paxos實(shí)現(xiàn)一個(gè)正確的分布式系統(tǒng)非常難[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.Raft[2][3]在2013年提出，提出的時(shí)間雖然不長，但已經(jīng)有很多系統(tǒng)基于Raft實(shí)現(xiàn)。相比Paxos，Raft的買點(diǎn)就是更利于理解、更易于實(shí)行。為達(dá)到更容易理解和實(shí)行的目的，Raft將問題分解和具體化：Leader統(tǒng)一處理變更操作請(qǐng)求，一致性協(xié)議的作用具化為保證節(jié)點(diǎn)間操作日志副本(log replication)一致，以term作為邏輯時(shí)鐘(logical clock)保證時(shí)序，節(jié)點(diǎn)運(yùn)行相同狀態(tài)機(jī)(state machine)[4]得到一致結(jié)果。Raft協(xié)議具體過程如下：Client發(fā)起請(qǐng)求，每一條請(qǐng)求包含操作指令請(qǐng)求交由Leader處理，Leader將操作指令(entry)追加(append)至操作日志，緊接著對(duì)Follower發(fā)起AppendEntries請(qǐng)求、嘗試讓操作日志副本在Follower落地如果Follower多數(shù)派(quorum)同意AppendEntries請(qǐng)求，Leader進(jìn)行commit操作、把指令交由狀態(tài)機(jī)處理狀態(tài)機(jī)處理完成后將結(jié)果返回給Client指令通過log index(指令id)和term number保證時(shí)序，正常情況下Leader、Follower狀態(tài)機(jī)按相同順序執(zhí)行指令，得出相同結(jié)果、狀態(tài)一致。宕機(jī)、網(wǎng)絡(luò)分化等情況可引起Leader重新選舉(每次選舉產(chǎn)生新Leader的同時(shí)，產(chǎn)生新的term)、Leader/Follower間狀態(tài)不一致。Raft中Leader為自己和所有Follower各維護(hù)一個(gè)nextIndex值，其表示Leader緊接下來要處理的指令id以及將要發(fā)給Follower的指令id，LnextIndex不等于FnextIndex時(shí)代表Leader操作日志和Follower操作日志存在不一致，這時(shí)將從Follower操作日志中最初不一致的地方開始，由Leader操作日志覆蓋Follower，直到LnextIndex、FnextIndex相等。Paxos中Leader的存在是為了提升決議效率，Leader的有無和數(shù)目并不影響決議一致性，Raft要求具備唯一Leader，并把一致性問題具體化為保持日志副本的一致性，以此實(shí)現(xiàn)相較Paxos而言更容易理解、更容易實(shí)現(xiàn)的目標(biāo)。ZabZab[5][6]的全稱是Zookeeper atomic broadcast protocol，是Zookeeper內(nèi)部用到的一致性協(xié)議。相比Paxos，Zab大的特點(diǎn)是保證強(qiáng)一致性(strong consistency，或叫線性一致性linearizable consistency)。和Raft一樣，Zab要求唯一Leader參與決議，Zab可以分解成discovery、sync、broadcast三個(gè)階段：discovery: 選舉產(chǎn)生PL(prospective leader)，PL收集Follower epoch(cepoch)，根據(jù)Follower的反饋PL產(chǎn)生newepoch(每次選舉產(chǎn)生新Leader的同時(shí)產(chǎn)生新epoch，類似Raft的term)sync: PL補(bǔ)齊相比Follower多數(shù)派缺失的狀態(tài)、之后各Follower再補(bǔ)齊相比PL缺失的狀態(tài)，PL和Follower完成狀態(tài)同步后PL變?yōu)檎絃eader(established leader)broadcast: Leader處理Client的寫操作，并將狀態(tài)變更廣播至Follower，F(xiàn)ollower多數(shù)派通過之后Leader發(fā)起將狀態(tài)變更落地(deliver/commit)Leader和Follower之間通過心跳判別健康狀態(tài)，正常情況下Zab處在broadcast階段，出現(xiàn)Leader宕機(jī)、網(wǎng)絡(luò)隔離等異常情況時(shí)Zab重新回到discovery階段。了解完Zab的基本原理，我們?cè)賮砜碯ab怎樣保證強(qiáng)一致性，Zab通過約束事務(wù)先后順序達(dá)到強(qiáng)一致性，先廣播的事務(wù)先commit、FIFO，Zab稱之為primary order(以下簡稱PO)。實(shí)現(xiàn)PO的核心是zxid。Zab中每個(gè)事務(wù)對(duì)應(yīng)一個(gè)zxid，它由兩部分組成：，e即Leader選舉時(shí)生成的epoch，c表示當(dāng)次epoch內(nèi)事務(wù)的編號(hào)、依次遞增。假設(shè)有兩個(gè)事務(wù)的zxid分別是z、z’，當(dāng)滿足 z.e < z’.e 或者 z.e = z’.e && z.c < z’.c 時(shí)，定義z先于z’發(fā)生(z < z’)。為實(shí)現(xiàn)PO，Zab對(duì)Follower、Leader有以下約束：有事務(wù)z和z’，如果Leader先廣播z，則Follower需保證先commit z對(duì)應(yīng)的事務(wù)有事務(wù)z和z’，z由Leader p廣播，z’由Leader q廣播，Leader p先于Leader q，則Follower需保證先commit z對(duì)應(yīng)的事務(wù)有事務(wù)z和z’，z由Leader p廣播，z’由Leader q廣播，Leader p先于Leader q，如果Follower已經(jīng)commit z，則q需保證已commit z才能廣播z’第1、2點(diǎn)保證事務(wù)FIFO，第3點(diǎn)保證Leader上具備所有已commit的事務(wù)。相比Paxos，Zab約束了事務(wù)順序、適用于有強(qiáng)一致性需求的場景。Paxos、Raft、Zab再比較除Paxos、Raft和Zab外，Viewstamped Replication(簡稱VR)[7][8]也是討論比較多的一致性協(xié)議。這些協(xié)議包含很多共同的內(nèi)容(Leader、quorum、state machine等)，因而我們不禁要問：Paxos、Raft、Zab和VR等分布式一致性協(xié)議區(qū)別到底在哪，還是根本就是一回事？[9]Paxos、Raft、Zab和VR都是解決一致性問題的協(xié)議，Paxos協(xié)議原文傾向于理論，Raft、Zab、VR傾向于實(shí)踐，一致性保證程度等的不同也導(dǎo)致這些協(xié)議間存在差異。下圖幫助我們理解這些協(xié)議的相似點(diǎn)和區(qū)別[10]：相比Raft、Zab、VR，Paxos更純粹、更接近一致性問題本源，盡管Paxos傾向理論，但不代表Paxos不能應(yīng)用于工程?；赑axos的工程實(shí)踐，須考慮具體需求場景(如一致性要達(dá)到什么程度)，再在Paxos原始語意上進(jìn)行包裝。小結(jié)以上介紹分布式一致性協(xié)議Raft、Zab的核心思想，分析Raft、Zab與Paxos的異同。實(shí)現(xiàn)分布式系統(tǒng)時(shí)，先從具體需求和場景考慮，Raft、Zab、VR、Paxos等協(xié)議沒有絕對(duì)地好與不好，只是適不適合。分布式系統(tǒng)理論進(jìn)階 - Paxos變種和優(yōu)化引言《分布式系統(tǒng)理論進(jìn)階 - Paxos》中我們了解了Basic Paxos、Multi Paxos的基本原理，但如果想把Paxos應(yīng)用于工程實(shí)踐，了解基本原理還不夠。有很多基于Paxos的優(yōu)化，在保證一致性協(xié)議正確(safety)的前提下，減少Paxos決議通信步驟、避免單點(diǎn)故障、實(shí)現(xiàn)節(jié)點(diǎn)負(fù)載均衡，從而降低時(shí)延、增加吞吐量、提升可用性，下面我們就來了解這些Paxos變種。Multi Paxos首先我們來回顧一下Multi Paxos，Multi Paxos在Basic Paxos的基礎(chǔ)上確定一系列值，其決議過程如下：phase1a: leader提交提議給acceptorphase1b: acceptor返回最近一次接受的提議(即曾接受的大的提議ID和對(duì)應(yīng)的value)，未接受過提議則返回空phase2a: leader收集acceptor的應(yīng)答，分兩種情況處理　　phase2a.1: 如果應(yīng)答內(nèi)容都為空，則自由選擇一個(gè)提議value　　phase2a.2: 如果應(yīng)答內(nèi)容不為空，則選擇應(yīng)答里面ID大的提議的valuephase2b: acceptor將決議同步給learnerMulti Paxos中l(wèi)eader用于避免活鎖，但leader的存在會(huì)帶來其他問題，一是如何選舉和保持唯一leader(雖然無leader或多l(xiāng)eader不影響一致性，但影響決議進(jìn)程progress)，二是充當(dāng)leader的節(jié)點(diǎn)會(huì)承擔(dān)更多壓力，如何均衡節(jié)點(diǎn)的負(fù)載。Mencius[1]提出節(jié)點(diǎn)輪流擔(dān)任leader，以達(dá)到均衡負(fù)載的目的；租約(lease)可以幫助實(shí)現(xiàn)唯一leader，但leader故障情況下可導(dǎo)致服務(wù)短期不可用。Fast Paxos在Multi Paxos中，proposer -> leader -> acceptor -> learner，從提議到完成決議共經(jīng)過3次通信，能不能減少通信步驟？對(duì)Multi Paxos phase2a，如果可以自由提議value，則可以讓proposer直接發(fā)起提議、leader退出通信過程，變?yōu)閜roposer -> acceptor -> learner，這就是Fast Paxos[2]的由來。Multi Paxos里提議都由leader提出，因而不存在一次決議出現(xiàn)多個(gè)value，F(xiàn)ast Paxos里由proposer直接提議，一次決議里可能有多個(gè)proposer提議、出現(xiàn)多個(gè)value，即出現(xiàn)提議沖突(collision)。leader起到初始化決議進(jìn)程(progress)和解決沖突的作用，當(dāng)沖突發(fā)生時(shí)leader重新參與決議過程、回退到3次通信步驟。Paxos自身隱含的一個(gè)特性也可以達(dá)到減少通信步驟的目標(biāo)，如果acceptor上一次確定(chosen)的提議來自proposerA，則當(dāng)次決議proposerA可以直接提議減少一次通信步驟。如果想實(shí)現(xiàn)這樣的效果，需要在proposer、acceptor記錄上一次決議確定(chosen)的歷史，用以在提議前知道哪個(gè)proposer的提議上一次被確定、當(dāng)次決議能不能節(jié)省一次通信步驟。EPaxos除了從減少通信步驟的角度提高Paxos決議效率外，還有其他方面可以降低Paxos決議時(shí)延，比如Generalized Paxos[3]提出不沖突的提議(例如對(duì)不同key的寫請(qǐng)求)可以同時(shí)決議、以降低Paxos時(shí)延。更進(jìn)一步地，EPaxos[4](Egalitarian Paxos)提出一種既支持不沖突提議同時(shí)提交降低時(shí)延、還均衡各節(jié)點(diǎn)負(fù)載、同時(shí)將通信步驟減少到最少的Paxos優(yōu)化方法。為達(dá)到這些目標(biāo)，EPaxos的實(shí)現(xiàn)有幾個(gè)要點(diǎn)。一是EPaxos中沒有全局的leader，而是每一次提議發(fā)起提議的proposer作為當(dāng)次提議的leader(command leader)；二是不相互影響(interfere)的提議可以同時(shí)提交；三是跳過prepare，直接進(jìn)入accept階段。EPaxos決議的過程如下：左側(cè)展示了互不影響的兩個(gè)update請(qǐng)求的決議過程，右側(cè)展示了相互影響的兩個(gè)update請(qǐng)求的決議。Multi Paxos、Mencius、EPaxos時(shí)延和吞吐量對(duì)比：為判斷決議是否相互影響，實(shí)現(xiàn)EPaxos得記錄決議之間的依賴關(guān)系。小結(jié)以上介紹了幾個(gè)基于Paxos的變種，Mencius中節(jié)點(diǎn)輪流做leader、均衡節(jié)點(diǎn)負(fù)載，F(xiàn)ast Paxos減少一次通信步驟，Generalized Paxos允許互不影響的決議同時(shí)進(jìn)行，EPaxos無全局leader、各節(jié)點(diǎn)平等分擔(dān)負(fù)載。優(yōu)化無止境，對(duì)Paxos也一樣，應(yīng)用在不同場景和不同范圍的Paxos變種和優(yōu)化將繼續(xù)不斷出現(xiàn)。

“web分布式系統(tǒng)怎么理解”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！

網(wǎng)頁標(biāo)題：web分布式系統(tǒng)怎么理解-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://muchs.cn/article16/dspodg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、網(wǎng)站收錄、手機(jī)網(wǎng)站建設(shè)、搜索引擎優(yōu)化、企業(yè)網(wǎng)站制作、網(wǎng)站改版

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

web分布式系統(tǒng)怎么理解-創(chuàng)新互聯(lián)

分布式系統(tǒng)理論基礎(chǔ) - 一致性、2PC和3PC

分布式系統(tǒng)理論基礎(chǔ) - 一致性、2PC和3PC