大話分布式系統(tǒng)理論基礎(chǔ)

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

2、 crawling around on the circuit board, or to the engineer who designed it, its 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ù)

3、據(jù)庫事務(wù)提交(commit transaction)、Leader選舉、序列號生成等都會遇到一致性問題。這個(gè)問題在我們的日常生活中也很常見，比如牌友怎么商定幾點(diǎn)在哪打幾圈麻將：賭圣，1990假設(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é)束，不會無休止地進(jìn)行下去有人可能會說，決定什么時(shí)候在哪搓搓麻將，4個(gè)人商量一下就ok，這不很簡單嗎？但就這樣看似簡單的事情，分布式系統(tǒng)實(shí)現(xiàn)起來并不輕松，

4、因?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ī)，不會恢復(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é)果會怎樣：還能不能一起愉快地玩耍.我

5、們把以上所列的問題稱為系統(tǒng)模型(system model)，討論分布式系統(tǒng)理論和工程實(shí)踐的時(shí)候，必先劃定模型。例如有以下兩種模型：異步環(huán)境(asynchronous)下，節(jié)點(diǎn)宕機(jī)(fail-stop)異步環(huán)境(asynchronous)下，節(jié)點(diǎn)宕機(jī)恢復(fù)(fail-recover)、網(wǎng)絡(luò)分化(network partition)2比1多了節(jié)點(diǎn)恢復(fù)、網(wǎng)絡(luò)分化的考量，因而對這兩種模型的理論研究和工程解決方案必定是不同的，在還沒有明晰所要解決的問題前談解決方案都是一本正經(jīng)地耍流氓。一致性還具備兩個(gè)屬性，一個(gè)是強(qiáng)一致(safety)，它要求所有節(jié)點(diǎn)狀態(tài)一致、共進(jìn)退；一個(gè)是可用(liveness)，它要求

6、分布式系統(tǒng)24*7無間斷對外服務(wù)。FLP定理(FLP impossibility)34已經(jīng)證明在一個(gè)收窄的模型中(異步環(huán)境并只存在節(jié)點(diǎn)宕機(jī))，不能同時(shí)滿足 safety 和 liveness。FLP定理是分布式系統(tǒng)理論中的基礎(chǔ)理論，正如物理學(xué)中的能量守恒定律徹底否定了永動機(jī)的存在，F(xiàn)LP定理否定了同時(shí)滿足safety 和 liveness 的一致性協(xié)議的存在。怦然心動 (Flipped)，2010工程實(shí)踐上根據(jù)具體的業(yè)務(wù)場景，或保證強(qiáng)一致(safety)，或在節(jié)點(diǎn)宕機(jī)、網(wǎng)絡(luò)分化的時(shí)候保證可用(liveness)。2PC、3PC是相對簡單的解決一致性問題的協(xié)議，下面我們就來了解2PC和3PC。2

7、PC2PC(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)：2PC, phase one在階段1中，coordinator發(fā)起一個(gè)提議，分別問詢各participant是否接受。2PC, phase two在階段2中，coordinator根據(jù)participant的反饋，提交或中止事務(wù)，如果participant全部

8、同意則提交，只要有一個(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ī)

9、一定時(shí)間后，watchdog接替原coordinator工作，通過問詢(query) 各participant的狀態(tài)，決定階段2是提交還是中止。這也要求coordinator/participant 記錄(logging)歷史狀態(tài)，以備coordinator宕機(jī)后watchdog對participant查詢、coordinator宕機(jī)恢復(fù)后重新找回狀態(tài)。從coordinator接收到一次事務(wù)請求、發(fā)起提議到事務(wù)完成，經(jīng)過2PC協(xié)議后增加了2次RTT(propose+commit)，帶來的時(shí)延(latency)增加相對較少。3PC3PC(three phase commit)即三階段提交67，既

10、然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就會進(jìn)入既不能回滾、又不能強(qiáng)制commit的阻塞狀態(tài)，直到participant宕機(jī)恢復(fù)。這引出兩個(gè)疑問：能不能去掉阻塞，使系統(tǒng)可以在commit/abort前回滾(rollback)到?jīng)Q議發(fā)起前的初始狀態(tài)當(dāng)次決議中，participant間能不能相互知道對方的狀態(tài)，又或者participant間

11、根本不依賴對方的狀態(tài)相比2PC，3PC增加了一個(gè)準(zhǔn)備提交(prepare to commit)階段來解決以上問題：圖片截取自wikipediacoordinator接收完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)

12、用在3PC。Participant如果在不同階段宕機(jī)，我們來看看3PC如何應(yīng)對：階段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的贊成反饋(不然也不會進(jìn)入到階段2)，coordinator進(jìn)行commit；watchdog可以通過問詢其他participant獲得這些信息，過程同理；宕機(jī)的participan

13、t恢復(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)的可用性，對一些現(xiàn)實(shí)業(yè)務(wù)場景是非常值得的。小結(jié)以

14、上介紹了分布式系統(tǒng)理論中的部分基礎(chǔ)知識，闡述了一致性(consensus)的定義和實(shí)現(xiàn)一致性所要面臨的問題，最后討論在異步網(wǎng)絡(luò)(asynchronous)、節(jié)點(diǎn)宕機(jī)恢復(fù)(fail-recover)模型下2PC、3PC怎么解決一致性問題。閱讀前人對分布式系統(tǒng)的各項(xiàng)理論研究，其中有嚴(yán)謹(jǐn)?shù)赝评?、證明，有一種數(shù)學(xué)的美；觀現(xiàn)實(shí)中的分布式系統(tǒng)實(shí)現(xiàn)，是綜合各種因素下妥協(xié)的結(jié)果。1Solved Problems, Unsolved Problems and Problems in Concurrency,Leslie Lamport, 19832The Byzantine Generals Problem,L

15、eslie Lamport,Robert Shostak and Marshall Pease, 19823Impossibility of Distributed Consensus with One Faulty Process,Fischer, Lynch and Patterson, 19854FLP Impossibility的證明,Daniel Wu, 20155Consensus Protocols: Two-Phase Commit,Henry Robinson, 20086Consensus Protocols: Three-phase Commit,Henry Robins

16、on, 20087Three-phase commit protocol,Wikipedia分布式系統(tǒng)理論基礎(chǔ) - CAP引言CAP是分布式系統(tǒng)、特別是分布式存儲領(lǐng)域中被討論最多的理論，“什么是CAP定理？”在Quora 分布式系統(tǒng)分類下排名 FAQ 的 No.1。CAP在程序員中也有較廣的普及，它不僅僅是“C、A、P不能同時(shí)滿足，最多只能3選2”，以下嘗試綜合各方觀點(diǎn)，從發(fā)展歷史、工程實(shí)踐等角度講述CAP理論。希望大家透過本文對CAP理論有更多地了解和認(rèn)識。CAP定理CAP由Eric Brewer在2000年P(guān)ODC會議上提出12，是Eric Brewer在Inktomi3期間研發(fā)搜索引擎、

17、分布式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)對一個(gè)寫操作返回成功，那么之后的讀請求都必須讀到這個(gè)新數(shù)據(jù)；如果返回失敗

18、，那么所有讀操作都不能讀到這個(gè)數(shù)據(jù)，對調(diào)用者而言數(shù)據(jù)具有強(qiáng)一致性(strong consistency) (又叫原子性 atomic、線性一致性 linearizable consistency)5服務(wù)可用性(availability)：所有讀寫請求在一定時(shí)間內(nèi)得到響應(yīng)，可終止、不會一直等待分區(qū)容錯(cuò)性(partition-tolerance)：在網(wǎng)絡(luò)分區(qū)的情況下，被分隔的節(jié)點(diǎn)仍能正常對外服務(wù)在某時(shí)刻如果滿足AP，分隔的節(jié)點(diǎn)同時(shí)對外服務(wù)但不能相互通信，將導(dǎo)致狀態(tài)不一致，即不能滿足C；如果滿足CP，網(wǎng)絡(luò)分區(qū)的情況下為達(dá)成C，請求只能一直等待，即不滿足A；如果要滿足CA，在一定時(shí)間內(nèi)要達(dá)到節(jié)點(diǎn)狀態(tài)一

19、致，要求不能出現(xiàn)網(wǎng)絡(luò)分區(qū)，則不能滿足P。C、A、P三者最多只能滿足其中兩個(gè)，和FLP定理一樣，CAP定理也指示了一個(gè)不可達(dá)的結(jié)果(impossibility result)。CAP的工程啟示CAP理論提出7、8年后，NoSql圈將CAP理論當(dāng)作對抗傳統(tǒng)關(guān)系型數(shù)據(jù)庫的依據(jù)、闡明自己放寬對數(shù)據(jù)一致性(consistency)要求的正確性6，隨后引起了大范圍關(guān)于CAP理論的討論。CAP理論看似給我們出了一道3選2的選擇題，但在工程實(shí)踐中存在很多現(xiàn)實(shí)限制條件，需要我們做更多地考量與權(quán)衡，避免進(jìn)入CAP認(rèn)識誤區(qū)7。1、關(guān)于 P 的理解Partition字面意思是網(wǎng)絡(luò)分區(qū)，即因網(wǎng)絡(luò)因素將系統(tǒng)分隔為多個(gè)單獨(dú)

20、的部分，有人可能會說，網(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)的包也將丟失，這種情況同樣符合定義?，F(xiàn)實(shí)情況下我們面對的是一個(gè)不可靠的網(wǎng)絡(luò)、有一定概率宕機(jī)的設(shè)備，這兩個(gè)因素都會導(dǎo)致P

21、artition，因而分布式系統(tǒng)實(shí)現(xiàn)中 P 是一個(gè)必須項(xiàng)，而不是可選項(xiàng)910。對于分布式系統(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的選

22、擇題不就變成數(shù)據(jù)一致性(consistency)、服務(wù)可用性(availability)2選1？工程實(shí)踐中一致性有不同程度，可用性也有不同等級，在保證分區(qū)容錯(cuò)性的前提下，放寬約束后可以兼顧一致性和可用性，兩者不是非此即彼12。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 consiste

23、ncy)14：放寬對時(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、跳出CAPCAP理論對實(shí)現(xiàn)分布式系統(tǒng)具有指導(dǎo)意義，但CAP理論并沒有涵蓋分布式

24、工程實(shí)踐中的所有重要因素。例如延時(shí)(latency)，它是衡量系統(tǒng)可用性、與用戶體驗(yàn)直接相關(guān)的一項(xiàng)重要指標(biāo)16。CAP理論中的可用性要求操作能終止、不無休止地進(jìn)行，除此之外，我們還關(guān)心到底需要多長時(shí)間能結(jié)束操作，這就是延時(shí)，它值得我們設(shè)計(jì)、實(shí)現(xiàn)分布式系統(tǒng)時(shí)單列出來考慮。延時(shí)與數(shù)據(jù)一致性也是一對“冤家”，如果要達(dá)到強(qiáng)一致性、多個(gè)副本數(shù)據(jù)一致，必然增加延時(shí)。加上延時(shí)的考量，我們得到一個(gè)CAP理論的修改版本PACELC17：如果出現(xiàn)P(網(wǎng)絡(luò)分區(qū))，如何在A(服務(wù)可用性)、C(數(shù)據(jù)一致性)之間選擇；否則，如何在L(延時(shí))、C(數(shù)據(jù)一致性)之間選擇。小結(jié)以上介紹了CAP理論的源起和發(fā)展，介紹了CAP理論

25、給分布式系統(tǒng)工程實(shí)踐帶來的啟示。CAP理論對分布式系統(tǒng)實(shí)現(xiàn)有非常重大的影響，我們可以根據(jù)自身的業(yè)務(wù)特點(diǎn)，在數(shù)據(jù)一致性和服務(wù)可用性之間作出傾向性地選擇。通過放松約束條件，我們可以實(shí)現(xiàn)在不同時(shí)間點(diǎn)滿足CAP(此CAP非CAP定理中的CAP，如C替換為最終一致性)181920。有非常非常多文章討論和研究CAP理論，希望這篇對你認(rèn)識和了解CAP理論有幫助。1Harvest, Yield, and Scalable Tolerant Systems,Armando Fox , Eric Brewer, 19992Towards Robust Distributed Systems, Eric Brewe

26、r, 20003Inktomis wild ride - A personal view of the Internet bubble,Eric Brewer, 20044Brewers Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web,Seth Gilbert, Nancy Lynch, 20025Linearizability: A Correctness Condition for Concurrent Objects, Maurice P. Herlihy,Jeannette

27、M. Wing, 19906Brewers CAP Theorem - The kool aid Amazon and Ebay have been drinking,Julian Browne, 20097CAP Theorem between Claims and Misunderstandings: What is to be Sacrificed?,Balla Wade Diack,Samba Ndiaye,Yahya Slimani, 20138Errors in Database Systems, Eventual Consistency, and the CAP Theorem,

28、Michael Stonebraker, 20109CAP Confusion: Problems with partition tolerance,Henry Robinson, 201010You Cant Sacrifice Partition Tolerance,Coda Hale, 201011Perspectives on the CAP Theorem,Seth Gilbert, Nancy Lynch, 201212CAP Twelve Years Later: How the Rules Have Changed,Eric Brewer, 201213How to Make

29、a Multiprocessor Computer That Correctly Executes Multiprocess Programs,Lamport Leslie, 197914Eventual Consistent Databases: State of the Art,Mawahib Elbushra , Jan Lindstrm, 201415Eventually Consistent,Werner Vogels, 200816Speed Matters for Google Web Search,Jake Brutlag, 200917Consistency Tradeoff

30、s in Modern Distributed Database System Design,Daniel J. Abadi, 201218A CAP Solution (Proving Brewer Wrong),Guys blog,200819How to beat the CAP theorem, nathanmarz, 201120The CAP FAQ,Henry Robinson分布式系統(tǒng)理論基礎(chǔ) - 時(shí)間、時(shí)鐘和事件順序十六號 四月十六號。一九六零年四月十六號下午三點(diǎn)之前的一分鐘你和我在一起，因?yàn)槟阄視涀∵@一分鐘。從現(xiàn)在開始我們就是一分鐘的朋友，這是事實(shí)，你改變不了，因?yàn)橐呀?jīng)過

31、去了。我明天會再來。 阿飛正傳現(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í)鐘可能有人會問，為什么分布式系統(tǒng)不使用物理時(shí)鐘(physical clock)記錄事件？每個(gè)事件對應(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時(shí)間同步節(jié)點(diǎn)間也存在毫秒級

32、別的偏差12。因而分布式系統(tǒng)需要有另外的方法記錄事件順序關(guān)系，這就是邏輯時(shí)鐘(logical clock)。Lamport timestampsLeslie Lamport在1978年提出邏輯時(shí)鐘的概念，并描述了一種邏輯時(shí)鐘的表示方法，這個(gè)方法被稱為Lamport時(shí)間戳(Lamport timestamps)3。分布式系統(tǒng)中按是否存在節(jié)點(diǎn)交互可分為三類事件，一類發(fā)生于節(jié)點(diǎn)內(nèi)部，二是發(fā)送事件，三是接收事件。Lamport時(shí)間戳原理如下：圖1: Lamport timestamps space time (圖片來源: wikipedia)每個(gè)事件對應(yīng)一個(gè)Lamport時(shí)間戳，初始值為0如果事件在節(jié)

33、點(diǎn)內(nèi)發(fā)生，時(shí)間戳加1如果事件屬于發(fā)送事件，時(shí)間戳加1并在消息中帶上該時(shí)間戳如果事件屬于接收事件，時(shí)間戳 = Max(本地時(shí)間戳，消息中的時(shí)間戳) + 1假設(shè)有事件a、b，C(a)、C(b)分別表示事件a、b對應(yīng)的Lamport時(shí)間戳，如果C(a) b，例如圖1中有 C1 - B1。通過該定義，事件集中Lamport時(shí)間戳不等的事件可進(jìn)行比較，我們獲得事件的偏序關(guān)系(partial order)。如果C(a) = C(b)，那a、b事件的順序又是怎樣的？假設(shè)a、b分別在節(jié)點(diǎn)P、Q上發(fā)生，Pi、Qj分別表示我們給P、Q的編號，如果C(a) = C(b) 并且Pi b。假如我們對圖1的A、B、C分別

34、編號Ai= 1、Bj= 2、Ck= 3，因 C(B4) = C(C3) 并且 Bj C3。通過以上定義，我們可以對所有事件排序、獲得事件的全序關(guān)系(total order)。上圖例子，我們可以從C1到A4進(jìn)行排序。Vector clockLamport時(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)不但記

35、錄本節(jié)點(diǎn)的Lamport時(shí)間戳，同時(shí)也記錄了其他節(jié)點(diǎn)的Lamport時(shí)間戳56。Vector clock的原理與Lamport時(shí)間戳類似，使用圖例如下：圖2: Vector clock space time (圖片來源: wikipedia)假設(shè)有事件a、b分別在節(jié)點(diǎn)P、Q上發(fā)生，Vector clock分別為Ta、Tb，如果 TbQ TaQ 并且 TbP = TaP，則a發(fā)生于b之前，記作 a - b。到目前為止還和Lamport時(shí)間戳差別不大，那Vector clock怎么判別同時(shí)發(fā)生關(guān)系呢？如果TbQ TaQ 并且 TbP TaP，則認(rèn)為a、b同時(shí)發(fā)生，記作 a b。例如圖2中節(jié)點(diǎn)B上的

36、第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í)踐中有很重要的引申應(yīng)用，最常見的應(yīng)用是發(fā)現(xiàn)數(shù)據(jù)沖突(detect conflict)。分布式系統(tǒng)中數(shù)據(jù)一般存在多個(gè)副本(replication)，多個(gè)副本可能被同時(shí)更新，這會引起副本間數(shù)據(jù)不一致7，Version vector的實(shí)現(xiàn)與Vector clock非常類似8，目的用于發(fā)現(xiàn)數(shù)據(jù)沖突9。下面通過一個(gè)例子說明Version vector

37、的用法10：圖3: Version vectorclient端寫入數(shù)據(jù)，該請求被Sx處理并創(chuàng)建相應(yīng)的vector (Sx, 1)，記為數(shù)據(jù)D1第2次請求也被Sx處理，數(shù)據(jù)修改為D2，vector修改為(Sx, 2)第3、第4次請求分別被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ù)沖突并寫入D5Vector clock只用于發(fā)現(xiàn)數(shù)據(jù)沖突，不能解決數(shù)據(jù)沖突。如何解決數(shù)據(jù)沖突因場景而異，具體方法有以最后更新為準(zhǔn)(l