Logical Clock

這里首先簡單回顧下分布式系統(tǒng)以及分布式計算概念和特性。

什么是分布式系統(tǒng)？

image.png

假設多個系統(tǒng)分布在多臺機器上，多臺機器組成一個分布式系統(tǒng)。
官方介紹：簡單來說就是一群獨立計算機集合共同對外提供服務，但是對于系統(tǒng)的用戶來說，就像是一臺計算機在提供服務一樣。
特點：
1.multiple machine services as one
2.one request cross multiple machine
3.each machine can talk to anyone

什么是分布式計算？

最直觀的解釋：將一個計算任務由管理節(jié)點拆分多個子計算任務分布在多機器組成的系統(tǒng)中，最后再將子計算結(jié)果進行匯總返回。
特點：
1.follow the master-slave mode possibly
2.master split and control job in term of sub tasks
3.subTask run on the slave
4.slave or sub task can communicate with each other
5.msg flow in subTask

如何決定分布式系統(tǒng)中事件的先后順序？

在分布式系統(tǒng)中有一個特點是不同的機器或者不同的進程之間都會有相互傳遞信息的特點，那么由于物理時鐘漂移以及網(wǎng)絡延遲等問題，通過物理時鐘來定義事件的先后順序其實是一件不現(xiàn)實的事情。

我們來看一件簡單的例子，假設微信朋友圈的數(shù)據(jù)中心在a,b,c三個城市，a城市的李雷同學分享一條消息，該消息從a數(shù)據(jù)中心分別擴散到b，c數(shù)據(jù)中心，b城市的韓梅梅收到以后進行來評論，隨后評論以消息的形式同樣被擴散到c城市，由于網(wǎng)絡延遲等問題，c城市的小明同學首先收到的是b城市韓梅梅的評論消息，其次才是a城市的李雷的原始分享。那么最終c城市的小明觀察到的時間順序就是評論->分享，而不是正確的分享->評論。

因此對于分布式系統(tǒng)來說如何解決事件的先后順序就變成了如何在分布式系統(tǒng)構(gòu)建一種全局因果一致性。

分布式邏輯時鐘

• 總體來說， 邏輯時鐘嘗試用「通過進程間創(chuàng)造通信以添加因果關系」的方式來對分布式中的事件順序做描述。

觀察下面圖8中的兩個圖：

• 紅色的點表示自發(fā)性事件。 黑色的表示『觀察到其他進程事件』而發(fā)生的事件。
• 橫向黑色實線代表物理時鐘。
• 帶箭頭的線表示進程中一個事件發(fā)生時，向另外一個進程傳播這個事件。

我們試著從每個進程的視角，依次對圖S1S1和S2S2進行推導一下，會發(fā)現(xiàn)， 其實兩個圖所描述的事件順序，在進程的相對視角中，是一樣的。

img

圖8 - 示例： S1S1和S2S2雖然在物理時序上不一樣，但是在各個進程的視角上推導出來卻是一樣的

我們的邏輯時序應該越接近物理時序越好，然而兩個圖對時序的刻畫， 出現(xiàn)了歧義（比如無法確定 a3a3 和 b2b2 的順序）。 根本上是沒有做充分的消息傳遞來添加因果關系。

首先我們需要明確一點： 邏輯時鐘并不度量時間本身，僅區(qū)分事件發(fā)生的前后順序。

Lamport的時鐘算法：

1. 每個進程 PiPi 內(nèi)維護本地一個計數(shù)器 CiCi ，初始為00.
2. 每次執(zhí)行一個事件，計數(shù)器 CiCi 自增 （假設自增量為11）.
3. 進程 PiPi 發(fā)消息給進程 PjPj 時，需要在消息上附帶自己的計數(shù)器 CiCi.
4. 當進程 PjPj 接收到消息時，更新自己的計數(shù)器 Cj=Max(Ci,Cj)+1Cj=Max(Ci,Cj)+1

下面的圖10是這個算法的示意圖，可以推算最后的時鐘計數(shù)器的值：Ci=3Ci=3, Cj=5Cj=5

img

圖10 - Lamport時鐘算法

下面，將證明：如果 a→ba→b，那么一定有 Ca<CbCa<Cb。

1. 假設 aa 和 bb 發(fā)生在同一個進程內(nèi)，顯然 Ca<CbCa<Cb.

2. 假設 aa 和 bb 分別處在不同的進程內(nèi)，如 PaPa 和 PbPb，
   根據(jù)事件先后的定義，必然存在一個不早于 aa 且 不晚于 bb 的由 PaPa 到 PbPb 的通信 （否則 a∥ba∥b ，矛盾）。

   那么假設兩個進程在 aa 和 bb 之間最近一次通信是由 PaPa 向 PbPb 發(fā)送了消息 a→ba→b： 易得 a→c→d→ba→c→d→b (其中可能 a=ca=c 或者 d=bd=b) 。根據(jù)算法定義，得：

   1. Ca≤CcCa≤Cc (進程內(nèi)計數(shù)器自增).
   2. Cd≤CbCd≤Cb (進程內(nèi)計數(shù)器自增).
   3. Cc<CdCc<Cd (進程間通信，觀察者事件已經(jīng)嚴格大于發(fā)生者事件的計數(shù)器)。

   那么，最終推導出 Ca<CbCa<Cb（嚴格小于）。

   img

   圖11 - 事件 aa 和 bb 在不同進程的情況下，中間一定有消息傳遞，否則兩個事件并發(fā)

以上，得證 a→b?Ca<Cba→b?Ca<Cb。

但是，如果我們已知 Ca<CbCa<Cb 的話，是否可以推導出 a→ba→b 呢？

悲哀的是，不能。 下面的圖12是個反例：

img

圖12 - lamport時鐘無法反向推導事件順序的反例： 紅色 aa 和藍色 bb 是并發(fā)的

這樣，我們反證了 Ca<Cb?a→bCa<Cb?a→b。

我們無法推導出 Ca<Cb?a→bCa<Cb?a→b 的原因，在于 aa 可能和 bb 并發(fā)。

但是， 如果 Ca<CbCa<Cb，一定不會有 b→ab→a 的關系存在。

Lamport的邏輯時鐘算法構(gòu)建了一個全序(total ordering)時鐘來描述事件順序， 但是我們知道「happened before」是一個偏序關系， 用全序關系的一維計數(shù)器來描述「happened before」的話， 就會導致無法等價化描述的結(jié)果， lamport時鐘的缺陷在于：如果兩個事件并不相關，那么這個時鐘給出的大小關系則沒有意義， 這個缺陷其實恰好就是全序和偏序的不同點而已。

所以，要準確描述事件順序，我們終究要尋求偏序方法。

于是，我們繼續(xù)探討向量時鐘。

邏輯時鐘的不足

• 現(xiàn)實中，無法構(gòu)建精確的全局時鐘來描述事件順序。
• 受狹義相對論的啟發(fā)，我們用因果關系來描述事件順序。
• 因果關系是一種偏序關系。
• Lamport時鐘構(gòu)造的計數(shù)器之間的大小關系是一種全序關系，無法準確刻畫事件順序的偏序關系。
• 向量時鐘是一種對lamport時鐘的延伸，以偏序關系準確刻畫了事件的因果順序。

此外，向量時鐘給我一種感想，對每個分布式節(jié)點來說：

1. 我把我的視角分享給其他節(jié)點。
2. 我對齊我看到的其他節(jié)點的視角。

本質(zhì)上，是在做 視角對齊。

參考