在程序中，我們經(jīng)常需要知道事件序列，在單體應(yīng)用中，事件序列是較為簡(jiǎn)單的，最簡(jiǎn)單的辦法就是用時(shí)間戳，但在分布式系統(tǒng)中，事件序列是很困難的，Leslie Lamport大神在論文 Time, Clocks, and the Ordering of Events in a Distributed System 討論了在分布式系統(tǒng)中時(shí)間、時(shí)鐘和事件序列的問題。
【1】分布式系統(tǒng)中物理時(shí)鐘存在的問題
邏輯時(shí)鐘是相對(duì)物理時(shí)鐘這個(gè)概念的，為什么要提出邏輯時(shí)鐘，因?yàn)槲锢頃r(shí)鐘在分布式系統(tǒng)中存在一系列問題。在一臺(tái)機(jī)器上的多個(gè)進(jìn)程可以從一個(gè)物理時(shí)鐘中獲取時(shí)間戳，不管這個(gè)物理時(shí)鐘是否準(zhǔn)確，只要是從一個(gè)物理時(shí)鐘獲取時(shí)間戳，我們都能獲得多個(gè)事件的相對(duì)時(shí)間順序。但是在分布式系統(tǒng)中，我們無(wú)法從一個(gè)物理時(shí)鐘獲取時(shí)間戳，只能從各自機(jī)器上物理時(shí)鐘獲取時(shí)間戳，而各臺(tái)機(jī)器的物理時(shí)鐘是很難完全同步的，即使有NTP，精度也是有限的。所以在分布式系統(tǒng)中，是不能通過物理時(shí)鐘決定事件序列的。
物理時(shí)鐘在分布式系統(tǒng)中也不是毫無(wú)用處，至少它一定程度上可以判斷在一臺(tái)機(jī)器上的事件順序，同時(shí)分布式系統(tǒng)中還是有必要讓不同機(jī)器上的物理時(shí)鐘在一定精度內(nèi)同步時(shí)間的，只是不作為決定事件序列的方法。
【2】偏序（Partial Ordering）
事件序列有兩種：偏序事件序列和全序事件序列。所謂的偏序指的是只能為系統(tǒng)中的部分事件定義先后順序。這里的部分其實(shí)是有因果關(guān)系的事件。在論文 Time, Clocks, and the Ordering of Events in a Distributed System 中，偏序是由“hAppened before”引出的，我們先看一下"happened before"（表示為“ -> ”）的定義：
Definition. The relation " -> "on the set of events of a system is the smallest relation satisfying the following three conditions:
(1) If a and b are events in the same process, and a comes before b , then a->b .
(2) If a is the sending of a message by one process and b is the receipt of the same message by another process, then a->b .
(3) If a->b and b->c then a->c .
在分布式系統(tǒng)中，只有兩個(gè)發(fā)生關(guān)聯(lián)的事件（有因果關(guān)系），我們才會(huì)去關(guān)心兩者的先來后到關(guān)系。對(duì)于并發(fā)事件，他們兩個(gè)誰(shuí)先發(fā)生，誰(shuí)后發(fā)生，其實(shí)我們并不關(guān)心。偏序就是用來定義兩個(gè)因果事件的發(fā)生次序，即‘happens before’。而對(duì)于并發(fā)事件（沒有因果關(guān)系），并不能決定其先后，所以說這種‘happens before’的關(guān)系，是一種偏序關(guān)系。
If two entities do not exchange any messages, then they probably do not need to share a common clock; events occurring on those entities are termed as concurrent events.”
【3】邏輯時(shí)鐘
論文原文中有這樣一句： We begin with an abstract point of view in which a clock is just a way of assigning a number to an event, where the number is thought of as the time at which the event occurred. 這句話的意思是，可以把時(shí)間進(jìn)行抽象，把時(shí)間值看成是事件發(fā)生順序的一個(gè)序列號(hào)，這個(gè)值可以 <20190515,20190516,20190517> ，也可以是 <1,2,3> 。后面就有了邏輯時(shí)鐘的概念。定義如下：
we define a clock Ci for each process Pi to be a function which assigns a number Ci(a) to any event a in that process.
Clock Condition. For any events a,b : if a->b then C(a) < C(b) .
C1. If a and b are events in process Pi , and a comes before b , then Ci(a) < Ci(b) .
C2. If a is the sending of a message by process Pi and b is the receipt of that message by process Pi , then Ci(a) < Ci(b) .
具體的，根據(jù)上面的定義條件，我們做如下實(shí)現(xiàn)規(guī)則：
- 每個(gè)事件對(duì)應(yīng)一個(gè)Lamport時(shí)間戳，初始值為0
- 如果事件在節(jié)點(diǎn)內(nèi)發(fā)生，本地進(jìn)程中的時(shí)間戳加1
- 如果事件屬于發(fā)送事件，本地進(jìn)程中的時(shí)間戳加1并在消息中帶上該時(shí)間戳
- 如果事件屬于接收事件，本地進(jìn)程中的時(shí)間戳 = Max(本地時(shí)間戳，消息中的時(shí)間戳) + 1
根據(jù)上面的定義，我們知道 a->b ， C(a)<C(b) ，但如果 C(a)=C(b) ，那么 a,b 是什么順序呢？它們肯定不是因果關(guān)系，所以它們之間的先后其實(shí)并不會(huì)影響結(jié)果，我們這里只需要給出一種確定的方式來定義它們之間的先后就能得到全序關(guān)系。
一種可行的方式是利用給進(jìn)程編號(hào)，利用進(jìn)程編號(hào)的大小來排序。假設(shè) a、b 分別在節(jié)點(diǎn) P、Q上發(fā)生， Pi、Qj 分別表示我們給 P、Q 的編號(hào)，如果 C(a)=C(b) 并且 Pi<Qj ，同樣定義為 a發(fā)生在 b 之前，記作 a⇒b （全序關(guān)系）。假如我們上圖的 A、B、C 分別編號(hào) Ai=1、Bj=2、Ck=3 ，因 C(B4)=C(C3) 并且 Bj<Ck ，則 B4⇒C3 。
通過以上定義，我們可以對(duì)所有事件排序，獲得事件的全序關(guān)系(total order)。上圖例子，我們可以進(jìn)行排序： C1⇒B1⇒B2⇒A1⇒B3⇒A2⇒C2⇒B4⇒C3⇒A3⇒B5⇒C4⇒C5⇒A4 。觀察上面的全序關(guān)系你可以發(fā)現(xiàn)，從時(shí)間軸來看 B5 是早于 A3 發(fā)生的，但是在全序關(guān)系里面我們根據(jù)上面的定義給出的卻是 A3 早于 B5 ，這是因?yàn)長(zhǎng)amport邏輯時(shí)鐘只保證因果關(guān)系（偏序）的正確性，不保證絕對(duì)時(shí)序的正確性。
【4】嘗試用邏輯時(shí)鐘解決分布式鎖的問題
單機(jī)多進(jìn)程程序可由鎖進(jìn)行同步，那是因?yàn)檫@些進(jìn)程都運(yùn)行在操作系統(tǒng)上，有center為它們的請(qǐng)求排序，這個(gè)center知道所有需要進(jìn)行同步的進(jìn)程的所有信息。但是在分布式系統(tǒng)中，各個(gè)進(jìn)程運(yùn)行在各自的主機(jī)上，沒有一個(gè)center的概念，那分布式系統(tǒng)中多進(jìn)程該怎么進(jìn)行同步呢？或者說分布式鎖該怎么實(shí)現(xiàn)呢？論文中提出了解決這一問題的算法要滿足下面三個(gè)條件：
(I) A process which has been granted the resource must release it before it can be granted to another process.
(II) Different requests for the resource must be granted in the order in which they are made.
(III) If every process which is granted the resource eventually releases it, then every request is eventually granted. 為了簡(jiǎn)化問題，我們做如下假設(shè)：
- 任何兩個(gè)進(jìn)程 Pi ， Pj 它們之間接收到的消息的順序與發(fā)送消息的順序一致，并且每個(gè)消息一定能夠被接收到。
- 每個(gè)進(jìn)程都維護(hù)一個(gè)不被其他進(jìn)程所知的請(qǐng)求隊(duì)列。并且請(qǐng)求隊(duì)列初始化為包含一個(gè) T0:P0請(qǐng)求， P0 用于該共享資源， T0 是初始值小于任何時(shí)鐘值
算法如下：
- To request the resource, process Pi sends the message Tm:Pi requests resource to every other process, and puts that message on its request queue, where Tm is the timestamp of the message.（請(qǐng)求資源，發(fā)送請(qǐng)求給其他進(jìn)程，在自己的請(qǐng)求隊(duì)列中添加該請(qǐng)求）
- When process Pj receives the message Tm:Pi requests resource, it places it on its request queue and sends a (timestamped) acknowledgment message to Pi .（收到其他進(jìn)程的請(qǐng)求，放到請(qǐng)求隊(duì)列中，回應(yīng)發(fā)起請(qǐng)求的進(jìn)程）
- To release the resource, process Pi removes any Tm:Pi requests resource message from its request queue and sends a (timestamped) Pi releases resource message to every other process.（釋放資源，從請(qǐng)求隊(duì)列中移除該資源請(qǐng)求，發(fā)送給其他進(jìn)程，告訴它們我釋放了該資源）
- When process Pj receives a Pi releases resource message, it removes any Tm:Pi requests resource message from its request queue.（收到其他進(jìn)程釋放資源的消息，從請(qǐng)求隊(duì)列中移除該資源請(qǐng)求）
- Process Pi granted the resource when the following two conditions are satisfied: (i) There is a Tm:Pi requests resource message in its request queue which is ordered before any other request in its queue by the relation ⇒ . (ii) Pi has received a message from every other process timestamped later than Tm . （判斷自己是否可以獲得該資源，有兩個(gè)條件：其一，按全序排序后， Tm:Pi 請(qǐng)求在請(qǐng)求隊(duì)列的最前面；其二，自己 Pi 已經(jīng)收到了所有其他進(jìn)程的時(shí)戳大于 Tm 的消息）
下面我們舉個(gè)例子說明上面的算法過程： 初始狀態(tài)為 P0 擁有資源，請(qǐng)求隊(duì)列中為 0:0 ( T0:P0 的簡(jiǎn)寫)，而后 P1 請(qǐng)求資源，將 1:1 添加到請(qǐng)求隊(duì)列中，此時(shí) P0 讓占有資源， P1 還無(wú)法獲取資源，等到 P0 釋放資源后， 0:0 從請(qǐng)求隊(duì)列中移除（下圖中沒有畫出），此時(shí)請(qǐng)求隊(duì)列中 1:1 的請(qǐng)求在最前面，同時(shí) P1 收到了其他兩個(gè)進(jìn)程的大于 1 的回應(yīng)消息，滿足了占有資源的條件，此時(shí) P1 占有資源。
其實(shí)關(guān)鍵思想很簡(jiǎn)單，既然分布式系統(tǒng)中沒有“center”的概念，那我請(qǐng)求共享資源時(shí)我就讓其他所有進(jìn)程都知道我要請(qǐng)求該資源，擁有資源的進(jìn)程釋放資源時(shí)也告訴所有進(jìn)程，我要釋放該資源，想請(qǐng)求該資源的你們可以按序（邏輯時(shí)鐘的作用，這里再次說明一下，并不能保證在絕對(duì)物理時(shí)間上請(qǐng)求的排序）請(qǐng)求了。這樣每個(gè)進(jìn)程都知道其他進(jìn)程的狀態(tài)，就相當(dāng)于有個(gè)“center”。
對(duì)于分布式鎖問題，多個(gè)請(qǐng)求不一定是一定按照絕對(duì)物理時(shí)鐘排序才可以，只要我們有這樣一個(gè)算法，這個(gè)算法可以保證多個(gè)進(jìn)程的請(qǐng)求按照這個(gè)算法總能得到同一個(gè)排序，就可以了，按照絕對(duì)物理時(shí)鐘排序只是其中一個(gè)可行的算法。
到這里是否就萬(wàn)事大吉了呢，其實(shí)并沒有，這個(gè)實(shí)現(xiàn)是很脆弱的，它要求所有進(jìn)程都非常可靠，一旦一個(gè)進(jìn)程掛了或出現(xiàn)網(wǎng)絡(luò)分區(qū)的情況，是無(wú)法工作的，同時(shí)我們提出的網(wǎng)絡(luò)要求也非常嚴(yán)格，要求發(fā)出的消息一定被接收到，這個(gè)在實(shí)用的系統(tǒng)中是很難做到的。所以這是一個(gè)理想狀況下的算法實(shí)現(xiàn)，并不是一個(gè)可以工業(yè)級(jí)應(yīng)用的算法實(shí)現(xiàn)。但它仍然是非常有意義的，給了我們關(guān)于分布式系統(tǒng)中解決一致性、共識(shí)算法等思想啟迪。
