隨著數(shù)據(jù)量的上升容达，傳統(tǒng)單機(jī)架構(gòu)存在的瓶頸已不能滿(mǎn)足對(duì)性能和容量的要求裁厅，從而分布式系統(tǒng)變得越來(lái)越火熱冰沙，但另一方面， 分布式也帶來(lái)了很多相對(duì)于單機(jī)架構(gòu)不同的問(wèn)題执虹。其中一個(gè)問(wèn)題就是多節(jié)點(diǎn)的時(shí)間同步問(wèn)題：不同節(jié)點(diǎn)上的物理時(shí)鐘難以同步拓挥，導(dǎo)致無(wú)法區(qū)分在分布式系統(tǒng)中多個(gè)節(jié)點(diǎn)的事件順序。

早在1978年袋励，Lamport在《Time, Clocks and the Ordering of Events in a Distributed System》中侥啤，就提出了邏輯時(shí)鐘的概念，就是用來(lái)解決分布式系統(tǒng)中事件發(fā)生的順序問(wèn)題茬故。

事件的因果

“Time is an illusion.”愛(ài)因斯坦如是說(shuō)盖灸。

邏輯時(shí)鐘是Lamport在1978年提出的一種在分布式系統(tǒng)中對(duì)事件進(jìn)行時(shí)間戳排序的方法，在其中定義了因果關(guān)系磺芭，稱(chēng)為before赁炎。

例如，before在航班滿(mǎn)員,航班可預(yù)訂钾腺。這里“事件預(yù)訂”before“航班滿(mǎn)員”甘邀，預(yù)訂和滿(mǎn)員就形成了因果關(guān)系。

現(xiàn)實(shí)世界中垮庐，確定事件預(yù)訂發(fā)生在事件滿(mǎn)員之前，需要預(yù)訂發(fā)生在比滿(mǎn)員更早的時(shí)間坞琴。 因果關(guān)系是一個(gè)事件（因）和第二個(gè)事件（果）之間的作用關(guān)系哨查， 其中后一個(gè)事件被認(rèn)為是前一個(gè)事件的結(jié)果。 一般來(lái)說(shuō)剧辐，一個(gè)事件是很多原因綜合產(chǎn)生的結(jié)果寒亥， 而且原因都發(fā)生在較早的時(shí)間點(diǎn)邮府。

而在分布式系統(tǒng)中，有時(shí)不可能說(shuō)兩個(gè)事件中的一個(gè)首先發(fā)生溉奕。 關(guān)系“happened before”只是系統(tǒng)中事件的部分排序褂傀。

部分排序

在分布式系統(tǒng)中，事件A發(fā)生在事件B之前加勤，如果A發(fā)生在比B更早的時(shí)間仙辟，需要系統(tǒng)正確的滿(mǎn)足規(guī)范。 如果分布式系統(tǒng)以物理時(shí)間為單位鳄梅，可能存在時(shí)鐘不完全準(zhǔn)確叠国，沒(méi)辦法保持精確的物理時(shí)間的問(wèn)題。 因此戴尸，在邏輯時(shí)鐘論文里粟焊，定義了“before”關(guān)系，而不使用物理時(shí)鐘孙蒙。

“before”標(biāo)記為=>,需要滿(mǎn)足三個(gè)條件：

如果a和b是同一進(jìn)程中發(fā)生的事件项棠，且a先于b，則a->b

如果a是一個(gè)進(jìn)程中的發(fā)送消息挎峦，b是另一個(gè)進(jìn)程中接收此消息香追，那么a->b

如果a->b并且b->c，那么a->c浑测。兩個(gè)事件是并發(fā)的翅阵，如果a≠>b和b≠>a

對(duì)于任意事件a，定義a≠>a迁央。

另一種說(shuō)法是a->b意味著事件a是事件b的因掷匠。兩個(gè)事件并發(fā)說(shuō)明二者不能發(fā)生因果影響， 兩個(gè)事件相互獨(dú)立岖圈。這就意味著部分排序讹语。

這樣，在分布式系統(tǒng)中蜂科，事件的順序可以根據(jù)發(fā)送的消息來(lái)定義顽决，只考慮實(shí)際發(fā)送的消息。

邏輯時(shí)鐘

由部分排序可知导匣，問(wèn)題的關(guān)鍵點(diǎn)在于節(jié)點(diǎn)間的交互要在事件發(fā)生順序上達(dá)成一致才菠， 而不是對(duì)于時(shí)間達(dá)成一致。所以贡定，邏輯時(shí)鐘指的是分布式系統(tǒng)中用于區(qū)分時(shí)間發(fā)生順序的機(jī)制赋访。 從某種意義上來(lái)講，現(xiàn)實(shí)世界的物理時(shí)間其實(shí)是邏輯時(shí)鐘的特例。

分布式系統(tǒng)中蚓耽，按是否存在節(jié)點(diǎn)交互可分為三類(lèi)事件渠牲，節(jié)點(diǎn)內(nèi)部，發(fā)送事件步悠，接收事件签杈。

Lamport邏輯時(shí)鐘的原理如下：

每個(gè)事件對(duì)應(yīng)一個(gè)Lamport時(shí)間戳，初始值為0.

如果事件發(fā)生在節(jié)點(diǎn)內(nèi)部鼎兽，本地進(jìn)程中的時(shí)間戳加1.

如果事件是發(fā)送事件答姥，本地進(jìn)程中的時(shí)間戳加1并在消息中帶上該時(shí)間戳

如果事件屬于接收事件，本地進(jìn)程中的時(shí)間戳 = Max(本地時(shí)間戳接奈，消息中的時(shí)間戳) + 1

下面詳細(xì)說(shuō)明邏輯時(shí)鐘的原理踢涌。

單機(jī)多進(jìn)程程序可以由鎖進(jìn)行同步，因?yàn)檫@些進(jìn)程都運(yùn)行在操作系統(tǒng)上序宦， 可以由操作系統(tǒng)為它們進(jìn)行排序睁壁，操作系統(tǒng)知道所有需要同步進(jìn)程的所有信息。 但是在分布式系統(tǒng)中互捌，各個(gè)進(jìn)程運(yùn)行在各個(gè)節(jié)點(diǎn)上潘明， 那么分布式系統(tǒng)中多進(jìn)程怎么進(jìn)行同步呢？

把邏輯時(shí)鐘引入到系統(tǒng)中秕噪，由一個(gè)抽象觀點(diǎn)開(kāi)始钳降，在這個(gè)觀點(diǎn)中時(shí)鐘只是給事件分配數(shù)字的一種方式， 其中這個(gè)數(shù)字就是事件發(fā)生的時(shí)間腌巾。給每個(gè)進(jìn)程Pi分配時(shí)鐘Ci,時(shí)鐘Ci是一個(gè)函數(shù)遂填，負(fù)責(zé)分配數(shù)字， 例如為事件a分配時(shí)鐘為Ci(a)澈蝙。系統(tǒng)時(shí)間函數(shù)C為任意事件b分配時(shí)間C(b)=Cj(b),如果b是發(fā)生在進(jìn)程Pj下吓坚。 這里的時(shí)鐘是邏輯時(shí)鐘不是物理時(shí)鐘，C函數(shù)可以是與物理時(shí)鐘無(wú)關(guān)的計(jì)數(shù)器實(shí)現(xiàn)灯荧。

這里由于論文時(shí)間較早礁击，所以都是以線(xiàn)程為例，可以推廣到分布式節(jié)點(diǎn)逗载。

邏輯時(shí)鐘的定義必須基于事件發(fā)生的順序而不是物理時(shí)鐘哆窿。如果事件a發(fā)生在事件b之前， 那么a應(yīng)該發(fā)生在b的更早時(shí)間厉斟。表述如下：如果a->b挚躯，那么C(a)

logic_clock1

如圖1，這里p1,p2,p3都與q3并發(fā)擦秽，這意味著它們都和q3同一時(shí)間發(fā)生秧均，但這與時(shí)間條件相矛盾食侮， 因?yàn)閜2->p3。

對(duì)關(guān)系的定義中很容易看出目胡，如果以下兩個(gè)條件成立，則時(shí)鐘條件是滿(mǎn)足的链快。

? 條件1誉己，如果a和b都是進(jìn)程Pi中的事件，并且a->b域蜗，那么Ci(a)

? 條件2巨双，如果a是Pi發(fā)送一個(gè)消息的事件，b是Pj中接收這個(gè)消息的事件霉祸，那么Ci(a)

考慮時(shí)空?qǐng)D筑累，假設(shè)一個(gè)進(jìn)程時(shí)鐘ticks分配數(shù)字，發(fā)生在進(jìn)程事件之間丝蹭。 例如a和b是Pi的連續(xù)事件慢宗，Ci(a)=4,Ci(b)=7,時(shí)鐘心跳5,6,7發(fā)生在兩個(gè)事件之間。 這樣可以在不同進(jìn)程的所有相似的ticks之間畫(huà)一條虛線(xiàn)形成圖1空間圖奔穿，如圖2镜沽。

logic_clock1

條件1意味著同一進(jìn)程上的任意事件之間必須要虛線(xiàn)，條件2意味著圖中每個(gè)消息線(xiàn)都要跨越虛線(xiàn)贱田。 從圖中可以看出為什么這兩個(gè)條件是時(shí)鐘條件缅茉。

進(jìn)程Pi的時(shí)鐘用Ci表示，Ci(a)表示事件a的時(shí)鐘男摧。事件之間Ci的值會(huì)變化蔬墩，改變Ci本身并不構(gòu)成事件。

為了確保滿(mǎn)足時(shí)鐘條件1,2,需要遵守以下實(shí)現(xiàn)規(guī)則：

? IR1. 每個(gè)進(jìn)程Pi在兩個(gè)連續(xù)事件之間遞增Ci.

? IR2. (a)如果a是進(jìn)程Pi發(fā)送消息m的事件耗拓，則消息m包含時(shí)間戳Tm=Ci(a)

? IR2. (b)在收到消息m時(shí)拇颅，處理Pj設(shè)置Cj大于或等于現(xiàn)在Tm的值

進(jìn)行全局事件排序，可以使用滿(mǎn)足時(shí)鐘條件的時(shí)鐘系統(tǒng)在所有系統(tǒng)事件的集合上進(jìn)行總排序帆离。

能夠?qū)κ录M(jìn)行完全排序蔬蕊，對(duì)于實(shí)現(xiàn)分布式系統(tǒng)非常有用。 實(shí)現(xiàn)一個(gè)正確的邏輯時(shí)鐘系統(tǒng)就是為了獲得這樣的總排序哥谷。 考慮共享資源的進(jìn)程或節(jié)點(diǎn)固定的集合組成的系統(tǒng)岸夯，一次只能有一個(gè)進(jìn)程或者節(jié)點(diǎn)使用資源， 因此進(jìn)程必須同步自己们妥，以避免發(fā)生沖突猜扮。

論文提到解決這一問(wèn)題要滿(mǎn)足三個(gè)條件：

Ⅰ 已被授予資源的進(jìn)程必須先將其釋放，然后才能將其授予另一個(gè)進(jìn)程监婶。

Ⅱ 對(duì)資源的不同請(qǐng)求必須按請(qǐng)求的順序授予旅赢。

Ⅲ 如果每個(gè)被授予資源的進(jìn)程最終都會(huì)釋放齿桃，那么每個(gè)請(qǐng)求最終都會(huì)被接受。

為解決這些問(wèn)題煮盼，并實(shí)現(xiàn)一個(gè)滿(mǎn)足條件的時(shí)鐘系統(tǒng)短纵，滿(mǎn)足規(guī)則IR1和IR2。 定義一個(gè)=>用來(lái)給全部事件排序僵控。有了這個(gè)順序香到，找到一個(gè)解決方案就變得簡(jiǎn)單了， 它只涉及確保每個(gè)進(jìn)程或節(jié)點(diǎn)知道所有其他進(jìn)程或節(jié)點(diǎn)的操作了报破。

為了簡(jiǎn)化問(wèn)題悠就，進(jìn)行一些不是必須的假設(shè)，這些假設(shè)的引入是為了避免分散實(shí)現(xiàn)細(xì)節(jié)充易。 假設(shè)對(duì)于兩個(gè)進(jìn)程Pi和Pj梗脾，從Pi發(fā)送到Pj的消息時(shí)以相同的順序接收的。 此外盹靴，我們假設(shè)每個(gè)消息最終都被接收炸茧。并且假設(shè)一個(gè)進(jìn)程可以直接向每個(gè)其他進(jìn)程發(fā)送消息。

每個(gè)進(jìn)程都維護(hù)自己的請(qǐng)求隊(duì)列鹉究，這是任何其他進(jìn)程都看不到的宇立。 假設(shè)請(qǐng)求隊(duì)列最初包含單個(gè)消息T0:P0請(qǐng)求資源，其中P0是最初授予資源的進(jìn)程自赔， T0小于任何時(shí)鐘的初始值妈嘹。

通過(guò)五條規(guī)則定義算法，為了方便起見(jiàn)绍妨，假設(shè)每個(gè)規(guī)則定義的操作形成單個(gè)事件润脸。

要請(qǐng)求資源，進(jìn)程Pi發(fā)送消息Tm:Pi請(qǐng)求給每個(gè)其他進(jìn)程他去，并將該消息放到其請(qǐng)求隊(duì)列中毙驯， 其中Tm是消息的時(shí)間戳。

每個(gè)進(jìn)程Pj接收請(qǐng)求資源消息Tm:Pi灾测，它將其放置在請(qǐng)求隊(duì)列中爆价，并向Pi發(fā)送一個(gè)帶有時(shí)間戳的確認(rèn)消息。

為了釋放資源媳搪，進(jìn)程Pi從其請(qǐng)求隊(duì)列中刪除Tm:Pi請(qǐng)求西苑消息铭段，并且發(fā)送Pi時(shí)間戳釋放資源消息到其他進(jìn)程。

當(dāng)進(jìn)程Pj接收一個(gè)Pi釋放資源消息時(shí)秦爆，它從其請(qǐng)求隊(duì)列中刪除任一Tm:Pi請(qǐng)求資源序愚。

當(dāng)滿(mǎn)足以下兩個(gè)條件時(shí)，進(jìn)程Pi被賦予資源：(1)在其隊(duì)列中由一個(gè)Tm:Pi消息等限，它在隊(duì)列中 =>其他請(qǐng)求爸吮。(為了定義=>芬膝，我們定義一個(gè)消息，使用發(fā)送消息的事件來(lái)識(shí)別形娇。)

(2)Pi收到比Tm更晚的每一個(gè)其他進(jìn)程的消息锰霜。

可以很容易的看到算法滿(mǎn)足條件Ⅰ-Ⅲ。

舉例說(shuō)明桐早，假設(shè)有3個(gè)進(jìn)程锈遥，根據(jù)算法說(shuō)明，初始化狀態(tài)各個(gè)進(jìn)程隊(duì)列里面都是(0,0)狀態(tài)勘畔， 此時(shí)鎖屬于P0。

logic_clock3

接著P1會(huì)發(fā)送請(qǐng)求資源的消息給所有其他進(jìn)程丽惶，并且放到自己的請(qǐng)求隊(duì)列里面炫七， 根據(jù)算法，P1的時(shí)鐘計(jì)數(shù)變?yōu)?钾唬，而接受消息的P0和P2的時(shí)鐘為消息時(shí)間戳+1万哪。

logic_clock4

收到P1的請(qǐng)求之后，P0和P2要發(fā)送確認(rèn)消息給P1表示自己已經(jīng)收到了抡秆。 由于目前請(qǐng)求隊(duì)列里面第一個(gè)不是P1發(fā)出的請(qǐng)求奕巍，所以此時(shí)鎖仍屬于P0。 但是由于收到了確認(rèn)消息儒士，此時(shí)P1已經(jīng)滿(mǎn)足了獲取資源的第一個(gè)條件： P1已經(jīng)收到了其他所有進(jìn)程時(shí)間戳大于1的消息的止。

logic_clock5

假設(shè)P0此時(shí)釋放了鎖，發(fā)送釋放資源的消息給P1和P2,P1和P2收到消息后把請(qǐng)求(0,0) 從隊(duì)列中刪除着撩。

logic_clock6

當(dāng)P0釋放了資源之后诅福，P1滿(mǎn)足了獲取資源的兩個(gè)條件，它的請(qǐng)求在隊(duì)列最前面和P1 已經(jīng)收到了其他所有進(jìn)程時(shí)間戳大于1的消息拖叙。也就是此時(shí)P1獲得了鎖氓润。

總結(jié)

在邏輯時(shí)鐘的論文中描述的算法大致就像上面描述的一樣，但顯而易見(jiàn)薯鳍，這個(gè)算法并不是容錯(cuò)的咖气，只要有一個(gè)進(jìn)程掛了或者響應(yīng)很慢，都會(huì)影響到整個(gè)分布式系統(tǒng)挖滤。

但邏輯時(shí)鐘的思路就如上面描述的那樣崩溪，是整個(gè)分布式一致性算法的基石， 所有的分布式一致性算法都有邏輯時(shí)鐘的影子在內(nèi)壶辜。 邏輯時(shí)鐘定義了分布式系統(tǒng)里面的時(shí)間概念悯舟，解決了分布式系統(tǒng)中區(qū)分時(shí)間發(fā)生的時(shí)序問(wèn)題。

實(shí)際上后續(xù)產(chǎn)生的矢量時(shí)鐘砸民、全局時(shí)鐘亦或者混合時(shí)鐘抵怎，都是對(duì)邏輯時(shí)鐘的增強(qiáng)奋救， 其基礎(chǔ)都是邏輯時(shí)鐘。

以上為事件的因果和邏輯時(shí)鐘反惕，「分布式技術(shù)專(zhuān)題」是國(guó)產(chǎn)數(shù)據(jù)庫(kù)hubble團(tuán)隊(duì)精心整編尝艘，專(zhuān)題會(huì)持續(xù)更新，歡迎大家保持關(guān)注姿染。