前言

前面Quorum System (上)、(下)，討論了針對replica server的讀寫，我們可以參數化各種W/R數量，來改變系統的Consistency與Availability程度。

以下用此圖做總整理

而我們說系統可以為了提高Availability，選擇W+W<=N來使系統 Always Writable。
但是這種情況下會發生一件事，那就是可能出現兩個concurrent writes，
例如: client1拿到兩個locks寫入r1,r2; client2拿到兩個locks寫入w3,w4。

這會有什麼問題呢？如果client1與client2都是要改同一筆data，則該data可能會有不同的update歷史順序，導致最終資料不一致。

比方說一個replica(上)先接收到了processA的指令再收到processB的指令，
與另一個replica(下)相反。
則要解決衝突的方法，最簡單的就是擁有一個上帝視角的全局觀察來決定就竟是processA先發起指令，還是processB。前面在W+W>=N時，似乎有提到timestamp來比較順序，所以read的時候可以知道哪個是最新的。

而這種想法就是 Versioning。

所以時間似乎就是最好的上帝視角，因為世界各地的時間應該是同步的。用時間做Versioning一定可以唯一且一定存在順序，而processA,processB傳遞指令訊息時都使用timestamp就可以在replica1, replica2解決順序問題。
但真的是這樣嗎?

電腦時鐘的限制

我們以為時間是固定的且一致的，但是其實電腦裡的時間會因為執行速度不一樣而有不一點點偏差。
而這件事情如果是單機系統不會有太大的影響。然而如果到了分散式系統，電腦之間會彼此溝通，而我們又希望用全局時間來解決寫入衝突的問題，那影響就大了。

我們來看以下例子:

假設時間快慢: P3 > P2 > P1
每當P3走10秒=>P2走8秒=>P1走6秒

1. 則當P1在他自己認為的6秒鍾時傳遞訊息並標記timestamp=6給P2，P2在他自認為的16秒鐘時收到訊息，因此P2自己計算傳輸時間是16-6=10秒鐘
2. 但是反過來，當P3在自己認為的60秒傳遞訊息，P2在自己認為的56秒收到，此時P2觀察訊息傳輸時間居然在自己的未來，這就不合理了。

以上的現象我們稱為 非同步網路 中的 時間飄移。

Lamport Logical Clock

而 Lamport 針對上述問題提出了一個很簡單直觀的想法。

1. 每個Node都初始Logical Clock為 timestamp=0
2. 如果此事件在本地Node發生 timestamp+1
3. 如果事件屬於傳遞訊息的事件，先將 timestamp+1，並在消息中夾帶該 timestamp
4. 如果事件屬於接收訊息的事件，則 timestamp = Max(本地Logical Clock時間, 消息中的timestamp)+1

簡單說，針對事件我們綁定timestamp，
而傳遞該事件的資料時，我們在訊息裡夾帶timestamp，而每個Node收到該事件與資料時，使用的不是自己的time去定timestamp，而是比較自己的time與事件夾帶的timestamp去選大的。
也就是當收到的訊息夾帶的時間比我的大時(上述4)，我就將自己的時間改為那個時間(圖b)，而該事件與資料夾帶的timestamp就一定會是遞增，而不會出現剛剛P2時間倒退的現象。

Causality 與 Happen-Before

回到前面的問題，我們先暫時將問題簡化！

我們最簡單的第一個願望就是希望在分散式系統中找出事件的先後順序，也就是Causality(因果關係)，更直白說就是 Happen-Before。

舉一個在分散式系統最常見的例子，訊息的接收，我們希望能夠定義出這兩個事件在物理上的順序。

When a message m is sent, send(m) occurs before receive(m)

既然是找出事件的順序，也就是Order，我們這邊複習一下離散數學的幾種Order xD

1. Total order: 在一個集合中(set)每兩個事件一定可以比較，也因此一定存在唯一一個順序。
   例如: UserA register -> UserA login -> order -> buy

2. Partial order: 在一個集合中不一定存在唯一一個順序，也就是有些事件是不能比較的。
   例如: UserA register與UserB register，並不真的存在事件的因果關係

3. Causality Order: 是Partial order的一種，但是如果系統中有傳收訊息的發生，這是是我們可以排序的
   例如: register UserB -> greet to UserB 這是可以知道順序，因為你要可以向UserB招手，UserB一定有註冊在系統中。

而 Lamport Logical Clock 就是希望幫我們定義出 Causality Order。

"Potential" Causality

我們定義 "Happen-Before" 的關係為 "->"，則

1. 存在process pi: 發生event e，接著傳遞該event e'，則e->e' (先發生event才能傳遞該event)
2. 存在 message m: send(m)->receive(m)
3. 如果 e->e' 且 e'->e''，則e->e'' (遞移律)
4. 如果搭配剛剛定義的 timestamp 規則，則 e → e’ ⇒ L(e) < L(e’) 一個事件先後順序可以從Logical Time大小看出。

Partial order: 有些事件我們無法比較先後順序
Concurrent events: 因為我們無法比較先後順序，因此當e-!>f, f-!>e則 f || e。

例子

有三個process p1,p2,p3。

1. p1發生event，L(a)=0+1=1
2. p1將event傳遞給p2，L(b)=L(a)+1=2，且L( c)=Max(p2=0, L(b))+1=L(b)+1=3
3. ...
   透過這樣的定義我們可以將事件利用Logical Clock找出順序。

限制

一樣剛剛的例子，有一個地方有點小問題啊。
p3默默地發生了一個event e且L(e)=1，而且其實這個event跟p2接收到訊息的event c沒有任何因果前後關係，理論上應該可以視為concurrent的。
但是因為Logical Clock規則，導致L(e) < L( c)，而被視為e發生在c前面。因此我們仍然無法找出 Total Order，頂多只有Causality Order，而這仍然是不夠的！

總結

雖然Lamport Logical Clock，似乎可以在非同步網路造成時間飄移的分散式系統中，幫我們定出因果關係順序，而不用受每台電腦時間不一困擾。

但是對於因果順序的事件，與某個process隨機發生的事件，套用Lamport Logical Clock會發生順序問題。

因此接下來我們將了解如何用 Vector Clock 來解決這個問題。

喔對，Lamport 大家可能沒印象他是誰，會出現在這裡應該是分散式系統裡的大大。
但是其實如果你曾經用latex來寫你的畢業論文，你就應該感謝他。
因為，他就是發明latex的人！

Note:
這下你知道為什麼很多分散式系統或是平台例如: OpenStack
在安裝前，必須在每個節點安裝一個叫做 NTP 的服務了吧。目的也就是希望能夠引用外部來源的時間來同步每一個節點的時間。
NTP我們在這裡先不做討論。