《雲數據管理》2.1邏輯時間和Lamport時鍾

本節書摘來自華章出版社《雲數據管理》一書中的第2章，第1節，作者迪衛艾肯特·阿格拉沃爾，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看

2.1.1　邏輯時間和Lamport時鍾

Lamport於1978年在他的一篇代表性論文裏提出了一個簡單的分布式係統模型[Lamport, 1978]。該模型中，進程被建模成一個全序事件的序列。事件分為本地（local）事件、發送（send）事件和接收（receive）事件。發送事件負責發送消息，該消息由相應的接收事件接收。本地事件是非通信事件，如，內存讀寫、矩陣相乘等。圖2-1展示了一個包括4個進程（p1、p2、p3和p4）的分布式係統示例。事件e2和e4在進程p1上執行，事件e1、e3和e9在進程p2執行，等等。事件e3是進程p2上的本地事件，而事件e1是一個發送事件，e2是相應的接收事件。

若兩個事件e和f滿足下列任一條件，則事件e發生在事件f之間，記作e→f：

1. 如果e和f是發生在同一進程內的兩個事件，並且e發生在f之前，那麼e→f；

2. 如果e代表了某個進程的消息發送事件send(m)，f代表另一進程中針對這同一個消息的接收事件receive(m)，那麼e→f；

3. 如果存在一個事件g，滿足e→g並且g→f，那麼e→f。

 

圖2-1　事件和消息

“發生在前”（happens-before）關係可以很好地反映任意兩個事件之間的潛在因果依賴關係。並且，如果兩個事件e和f既不存在e→f關係，也不存在f→e關係，那麼e和f是並發的。在圖2-1中，事件e4發生在事件e6之前，而事件e3與事件e2和e4都是並發的。

時間概念以及時間與事件之間的關係對很多分布式係統協議來說都是至關重要的。一般情況下，不一定需要實時時鍾或近似實時時鍾，隻要有一個時間概念能夠捕獲潛在的因果關係就足夠了。Lamport引入了一種可以捕獲事件之間的潛在因果關係的邏輯時鍾概念。邏輯時鍾為每一個事件e賦一個值clock(e)，因此，對任意兩個事件e和f，存在如下關係：

如果e→f，那麼clock(e)<clock(f)。

為了能夠實現這種邏輯時鍾，Lamport為每一個進程設置了一個時鍾計數器。該計數器在同一進程中的任意兩個事件之間都必須是遞增的，並且，每一個消息都攜帶了發送者的時鍾值。當消息到達目的地之後，本地時鍾計數器被設置為本地值的最大值，同時消息的時間戳加1。這種實現方式可以滿足上述邏輯時鍾的條件。

在圖2-2中，使用與圖2-1相同的例子，為係統中的所有事件都賦一個邏輯時間。

 

圖2-2　Lamport時鍾

因為“發生在前”關係是一個偏序，因此，多個事件可能被賦值相同的邏輯時鍾。但是，在很多協議中，為每一個事件賦一個唯一的時間值更為方便。這種情況下，為了打破這種關係，時間值可以設置為<t, p>，其中，t是本地時鍾計數器設置的邏輯時間，p是事件執行所在進程的進程標識。一般情況下，每一個進程都被賦值一個唯一的全序的進程標識，這些進程標識可以打破具有相同邏輯時間的事件之間的關係。