今天的文章來聊聊向量時(shí)鐘，在前文介紹分布式系統(tǒng)一致性的時(shí)候，曾經(jīng)介紹過，在弱一致性模型當(dāng)中會有一個(gè)因果性的問題。向量時(shí)鐘算法正是設(shè)計(jì)出來解決因果關(guān)系問題的。
我們來回顧一下因果問題，在實(shí)際日常的網(wǎng)頁行為當(dāng)中，部分行為存在因果關(guān)系。比方說知乎里面回答問題，顯然得先有一個(gè)同學(xué)提出問題，然后才能有各路大V謝邀解答問題。但是由于是分布式系統(tǒng)，有可能問題和回答并不是存放在同一臺機(jī)器，導(dǎo)致有可能它們更新的順序不一致，所以就有可能會出現(xiàn)用戶在訪問知乎的時(shí)候，發(fā)現(xiàn)自己關(guān)注的大V回答了某個(gè)問題，但是點(diǎn)進(jìn)去問題卻是空的。這種幽靈情況不是靈異事件，只是單純的分布式系統(tǒng)設(shè)計(jì)沒過關(guān)，沒有考慮因果問題。
有的同學(xué)可以會說，這個(gè)不難啊，我們加入時(shí)間戳啊。時(shí)間戳的確可以解決一部分問題，但是并不能解決所有問題。有了時(shí)間戳之后，我們可以獲得事件發(fā)生的時(shí)間，但是仍然不知道不同的數(shù)據(jù)之間的因果關(guān)系。由于分布式系統(tǒng)存在延遲，也不能簡單地通過時(shí)間戳來做過濾或者篩選。不過，雖然單純的時(shí)間戳不行，但已經(jīng)非常接近了。
我們?nèi)粘Ｉ町?dāng)中用事件發(fā)生的時(shí)間來反應(yīng)事物發(fā)生的順序，我們說的先后順序，其實(shí)是以客觀上的時(shí)間作為參考系參考得到的結(jié)果。問題來了，我們能不能找到或者構(gòu)造出其他的參考系來反應(yīng)事物發(fā)生的順序呢？
當(dāng)然是可以的，不然也沒有這篇文章了，這就是大名鼎鼎的邏輯時(shí)鐘算法。多說一句，邏輯時(shí)鐘算法和許多其他分布式算法一樣，同樣源于大神Lamport的發(fā)明。
邏輯時(shí)鐘
我們還用之前的例子來思考一下，一個(gè)人在知乎提交了問題，另一個(gè)人回答了問題，這是兩個(gè)事件。我們第一反應(yīng)自然是通過兩個(gè)事件發(fā)生的時(shí)間來反應(yīng)因果順序，但我們仔細(xì)分析一下這個(gè)場景。后面那個(gè)人既然能回答問題，說明他一定是看到了問題。也就是說回答問題和看到問題之間發(fā)生了交互，所以很自然地可以想到，我們是不是可以用兩個(gè)系統(tǒng)或者是兩個(gè)事件之間有沒有發(fā)生過信息交互來反應(yīng)因果順序呢？
于是基于這個(gè)思想，Lamport大神提出了邏輯時(shí)鐘的概念。邏輯時(shí)鐘概念的核心就是剛才我們說的，兩個(gè)事件之間建立因果關(guān)系的前提是，兩個(gè)事件之間發(fā)生過信息傳遞。
我們梳理一下可能發(fā)生的事件的種類，可以分成三種。第一種是發(fā)生在某個(gè)節(jié)點(diǎn)內(nèi)部，也就是說沒有和其他任何節(jié)點(diǎn)發(fā)生聯(lián)系。第二種是發(fā)送事件，是事件的發(fā)送方。第三種是接收事件，和第二種對應(yīng)，是事件的接收方。明確了這三點(diǎn)之后，我們就可以用時(shí)間戳來表示這三種情況了。首先，我們假設(shè)每個(gè)節(jié)點(diǎn)內(nèi)部都會維護(hù)一個(gè)時(shí)間戳，記錄當(dāng)下節(jié)點(diǎn)的狀態(tài)。
針對上面說是三種時(shí)序關(guān)系呢，我們設(shè)定三種策略。
首先是內(nèi)部事件，對于節(jié)點(diǎn)內(nèi)部發(fā)生事件呢，很簡單，我們只需要將它的時(shí)間戳增大1，表示發(fā)生過了某件事情。
其次是發(fā)送事件，節(jié)點(diǎn)內(nèi)部的時(shí)間戳自增1，并且在發(fā)送消息當(dāng)中加上這個(gè)時(shí)間戳。
最后是接收事件，由于會額外接收到一個(gè)時(shí)間戳，所以我們需要利用這個(gè)時(shí)間戳來更新節(jié)點(diǎn)內(nèi)部的時(shí)間戳。更新的方法也很簡單，假設(shè)節(jié)點(diǎn)內(nèi)部的時(shí)間戳是t，跟著消息傳遞而來的時(shí)間戳是t', 那么: t_new = max(t + 1, t') 。
我們分析一下上面這個(gè)關(guān)系，假設(shè)當(dāng)下有事件A和B，如果事件A是事件B發(fā)生的前提。那么顯然事件A的時(shí)間戳小于事件B。如果反過來，事件A的時(shí)間戳小于B，能說明事件A是事件B的前提嗎？并不能，所以時(shí)間戳較小是因果關(guān)系的必要條件，但不是充分條件。
由于會存在多個(gè)節(jié)點(diǎn)或者進(jìn)程時(shí)間戳相等的情況，所以我們把進(jìn)程id也作為比較的銀子。我們用C表示一個(gè)事件的時(shí)間戳，P表示事件的進(jìn)程pid。如果事件A排在事件B前面，只有兩種可能：
- C(A) < C(B)
- C(A) = C(B) and P(A) < P(B)
我們來看一個(gè)例子：
上圖當(dāng)中有A、B和C三個(gè)進(jìn)程，其中P(A) < P(B) < P(C)。圖中每一個(gè)箭頭都代表傳遞的消息。
我們根據(jù)重新定義的時(shí)序關(guān)系，可以得到這些點(diǎn)的先后順序是：
C1⇒B1⇒B2⇒A1⇒B3⇒A2⇒C2⇒B4⇒C3⇒A3⇒B5⇒C4⇒C5⇒A4
如果仔細(xì)觀察這條鏈的話會發(fā)現(xiàn)它并不能真實(shí)反映事件發(fā)生的順序，會存在不公平的情況。但至少因果關(guān)系可以保證。
以上這個(gè)算法被稱為是邏輯時(shí)鐘算法，它相當(dāng)于重新定義了一個(gè)邏輯上的時(shí)間來代替真實(shí)物理世界的時(shí)間。由于它是Lamport大神提出的，所以也被稱為是Lamport邏輯時(shí)鐘算法。
向量時(shí)鐘
在上面的文章當(dāng)中我們也分析了，邏輯時(shí)鐘算法有一個(gè)問題是雖然保證了因果順序，但也犧牲了公平。比如上圖當(dāng)中B3和A2發(fā)生在同一時(shí)間，但是B3排在A2的前面。也就是說我們通過比較 C(A) 和 C(B)無法得出真實(shí)的發(fā)生順序。
為了解決這個(gè)問題，大神們在Lamport的邏輯時(shí)鐘上做了改進(jìn)，提出了向量時(shí)鐘算法。
向量時(shí)鐘和邏輯時(shí)鐘的原理幾乎一樣，只不過對于每個(gè)節(jié)點(diǎn)或者進(jìn)程而言，它維護(hù)的不再是一個(gè)單個(gè)的時(shí)間戳，而是一個(gè)時(shí)間戳構(gòu)成的向量。向量的維度就等于進(jìn)程的數(shù)量，也就是說每個(gè)進(jìn)程不止記錄自己的時(shí)間戳，而且還會記錄其他進(jìn)程的時(shí)間戳，這些時(shí)間戳組合在一起，就構(gòu)成了一個(gè)時(shí)間向量。
在事件的處理上，向量時(shí)鐘算法和邏輯時(shí)鐘基本一致。
- 在進(jìn)程i發(fā)生事件（接收、發(fā)送或者是內(nèi)部事件）的時(shí)候，，這時(shí)候C是一個(gè)時(shí)間戳向量，i是進(jìn)程i的下標(biāo)。
- 當(dāng)進(jìn)程i發(fā)送消息的時(shí)候，會將消息和自己的時(shí)鐘向量一同發(fā)出。
- 當(dāng)進(jìn)程i收到進(jìn)程j發(fā)送來的消息時(shí)，會根據(jù)一起發(fā)送來的時(shí)鐘向量更新自己的時(shí)鐘向量：
同樣，由于單個(gè)時(shí)間戳換成了向量時(shí)鐘，所以我們判斷因果順序的方式也需要變化。在向量時(shí)鐘算法當(dāng)中，我們定義如果事件A在事件B之前，那么需要滿足兩個(gè)條件：
- 對于所有的下標(biāo)K，都有
- 存在下標(biāo)，使得
也就是說至少需要一個(gè)維度存在嚴(yán)格小于，其他維度全部小于等于，才可以看做是因果關(guān)系。原因也很簡單，因?yàn)槿绻嬖谙鬟f，那么至少有一個(gè)維度會帶來增加。如果兩個(gè)事件的向量時(shí)鐘相等，說明兩者是沒有發(fā)生過信息傳遞的，自然也就不符合我們定義的因果關(guān)系。
我們回顧一下之前的例子，將節(jié)點(diǎn)改寫成向量時(shí)鐘之后，得到的結(jié)果如下圖：
將邏輯時(shí)鐘優(yōu)化成向量時(shí)鐘之后，就可以嚴(yán)格判斷因果關(guān)系了。如果兩個(gè)節(jié)點(diǎn)的時(shí)鐘向量沒有大小關(guān)系，那么可以說明這兩個(gè)事件之間沒有聯(lián)系。
實(shí)際應(yīng)用
和我們之前介紹的一樣，向量時(shí)鐘算法主要用在分布式系統(tǒng)的因果關(guān)系的檢測上。而因果關(guān)系之所以需要檢測，往往是因?yàn)槲覀兠媾R多個(gè)副本同時(shí)更新，我們需要檢測這些副本的沖突。
我們來一起看一個(gè)例子，這個(gè)例子是亞馬遜的Dynamo系統(tǒng)， 它是一個(gè)KV的存儲系統(tǒng)，類似于redis，可以簡單理解成緩存。為了高可用，Dynamo保證即使在出現(xiàn)網(wǎng)絡(luò)分區(qū)或者機(jī)器宕機(jī)的時(shí)候，仍然可讀可寫。但是這會導(dǎo)致一個(gè)問題，當(dāng)網(wǎng)絡(luò)分區(qū)恢復(fù)之后，多個(gè)副本的數(shù)據(jù)可能會出現(xiàn)不一致的情況，這個(gè)時(shí)候我們就需要通過向量時(shí)鐘算法來檢測沖突了。
假設(shè)一開始的時(shí)候客戶端W創(chuàng)建了一個(gè)記錄X，這個(gè)記錄是由機(jī)器 Sx 來負(fù)責(zé)的。那么則形成了數(shù)據(jù) D1
和它對應(yīng)的向量時(shí)鐘 [Sx, 1]。
之后，客戶端繼續(xù)更新記錄X，同樣由機(jī)器 Sx 執(zhí)行，形成了新數(shù)據(jù) D2，它的向量時(shí)鐘變成 [Sx, 2]，它和 D1 存在因果關(guān)系。所以我們可以知道 D2 是最新的數(shù)據(jù)。
再之后，客戶端繼續(xù)更新X，這次由 Sy 執(zhí)行，產(chǎn)生了D3，同樣，可以知道操作結(jié)束之后它的向量時(shí)鐘為 [Sx, 2], [Sy, 1]。
與此同時(shí)，另一個(gè)客戶端讀入了 D2 之后，在機(jī)器 Sz 上更新產(chǎn)生了 D4 ，此時(shí)的向量時(shí)鐘是 [Sx, 2], [Sz, 1]。
我們來分析一下，如果這時(shí)候有客戶端同時(shí)讀到 D2 和 D3 ，那么通過向量時(shí)鐘可以判斷出來，D3 是最新的數(shù)據(jù)。如果同時(shí)讀到 D3 和 D4 ，由于這兩者的向量時(shí)鐘并沒有因果關(guān)系，所以無法判斷誰是最新的數(shù)據(jù)，這就產(chǎn)生了沖突。
但是必須要說明的是，向量時(shí)鐘算法只能檢測沖突，并不能解決沖突，沖突需要客戶端自己解決。如果客戶端判斷，決定應(yīng)該以 Sx 的節(jié)點(diǎn)為準(zhǔn)，那么最后的數(shù)據(jù)就會變成 D5 ，此時(shí)的向量時(shí)鐘為[Sx, 3], [Sy, 1], [Sz, 1]。
除了知乎之外，其實(shí)還有很多場景下的一致性問題都需要考慮因果關(guān)系。因此向量時(shí)鐘算法在分布式領(lǐng)域可以說是鼎鼎大名，使用非常廣泛。在剛聽到這個(gè)名字的時(shí)候，往往會覺得它非常晦澀難懂，但實(shí)際深入了解之后，會發(fā)現(xiàn)其實(shí)并不困難，反而非常有趣，這也算是學(xué)習(xí)的樂趣之一吧。
今天的文章就到這里，如果覺得有所收獲，請順手點(diǎn)關(guān)注或轉(zhuǎn)發(fā)個(gè)吧，你們的支持是我最大的動力。
