web分布式系統(tǒng)時(shí)間、時(shí)鐘和事件順序是什么

這篇文章主要介紹“web分布式系統(tǒng)時(shí)間、時(shí)鐘和事件順序是什么”，在日常操作中，相信很多人在web分布式系統(tǒng)時(shí)間、時(shí)鐘和事件順序是什么問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”web分布式系統(tǒng)時(shí)間、時(shí)鐘和事件順序是什么”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

物理時(shí)鐘 vs 邏輯時(shí)鐘

可能有人會(huì)問(wèn)，為什么分布式系統(tǒng)不使用物理時(shí)鐘(physical clock)記錄事件？每個(gè)事件對(duì)應(yīng)打上一個(gè)時(shí)間戳，當(dāng)需要比較順序的時(shí)候比較相應(yīng)時(shí)間戳就好了。

這是因?yàn)楝F(xiàn)實(shí)生活中物理時(shí)間有統(tǒng)一的標(biāo)準(zhǔn)，而分布式系統(tǒng)中每個(gè)節(jié)點(diǎn)記錄的時(shí)間并不一樣，即使設(shè)置了 NTP 時(shí)間同步節(jié)點(diǎn)間也存在毫秒級(jí)別的偏差^[1][2]。因而分布式系統(tǒng)需要有另外的方法記錄事件順序關(guān)系，這就是邏輯時(shí)鐘(logical clock)。

Lamport timestamps

Leslie Lamport 在1978年提出邏輯時(shí)鐘的概念，并描述了一種邏輯時(shí)鐘的表示方法，這個(gè)方法被稱(chēng)為L(zhǎng)amport時(shí)間戳(Lamport timestamps)^[3]。

分布式系統(tǒng)中按是否存在節(jié)點(diǎn)交互可分為三類(lèi)事件，一類(lèi)發(fā)生于節(jié)點(diǎn)內(nèi)部，二是發(fā)送事件，三是接收事件。Lamport時(shí)間戳原理如下：

圖1: Lamport timestamps space time (圖片來(lái)源: wikipedia)

1. 每個(gè)事件對(duì)應(yīng)一個(gè)Lamport時(shí)間戳，初始值為0

2. 如果事件在節(jié)點(diǎn)內(nèi)發(fā)生，時(shí)間戳加1

3. 如果事件屬于發(fā)送事件，時(shí)間戳加1并在消息中帶上該時(shí)間戳

4. 如果事件屬于接收事件，時(shí)間戳 = Max(本地時(shí)間戳，消息中的時(shí)間戳) + 1

假設(shè)有事件a、b，C(a)、C(b)分別表示事件a、b對(duì)應(yīng)的Lamport時(shí)間戳，如果C(a) < C(b)，則有a發(fā)生在b之前(happened before)，記作 a -> b，例如圖1中有 C1 -> B1。通過(guò)該定義，事件集中Lamport時(shí)間戳不等的事件可進(jìn)行比較，我們獲得事件的 偏序關(guān)系(partial order)。

如果C(a) = C(b)，那a、b事件的順序又是怎樣的？假設(shè)a、b分別在節(jié)點(diǎn)P、Q上發(fā)生，P_i、Q_j分別表示我們給P、Q的編號(hào)，如果 C(a) = C(b) 并且 P_i j，同樣定義為a發(fā)生在b之前，記作 a => b。假如我們對(duì)圖1的A、B、C分別編號(hào)A_i = 1、B_j = 2、C_k = 3，因 C(B4) = C(C3) 并且 B_j < C_k，則 B4 => C3。

通過(guò)以上定義，我們可以對(duì)所有事件排序、獲得事件的 全序關(guān)系(total order)。上圖例子，我們可以從C1到A4進(jìn)行排序。

Vector clock

Lamport時(shí)間戳幫助我們得到事件順序關(guān)系，但還有一種順序關(guān)系不能用Lamport時(shí)間戳很好地表示出來(lái)，那就是同時(shí)發(fā)生關(guān)系(concurrent)^[4]。例如圖1中事件B4和事件C3沒(méi)有因果關(guān)系，屬于同時(shí)發(fā)生事件，但Lamport時(shí)間戳定義兩者有先后順序。

Vector clock是在Lamport時(shí)間戳基礎(chǔ)上演進(jìn)的另一種邏輯時(shí)鐘方法，它通過(guò)vector結(jié)構(gòu)不但記錄本節(jié)點(diǎn)的Lamport時(shí)間戳，同時(shí)也記錄了其他節(jié)點(diǎn)的Lamport時(shí)間戳^[5][6]。Vector clock的原理與Lamport時(shí)間戳類(lèi)似，使用圖例如下：

圖2: Vector clock space time (圖片來(lái)源: wikipedia)__

假設(shè)有事件a、b分別在節(jié)點(diǎn)P、Q上發(fā)生，Vector clock分別為T(mén)_a、T_b，如果 T_b[Q] > T_a[Q] 并且 T_b[P] >= T_a[P]，則a發(fā)生于b之前，記作 a -> b。到目前為止還和Lamport時(shí)間戳差別不大，那Vector clock怎么判別同時(shí)發(fā)生關(guān)系呢？

如果 T_b[Q] > T_a[Q] 并且 T_b[P] < T_a[P]，則認(rèn)為a、b同時(shí)發(fā)生，記作 a <-> b。例如圖2中節(jié)點(diǎn)B上的第4個(gè)事件 (A:2，B:4，C:1) 與節(jié)點(diǎn)C上的第2個(gè)事件 (B:3，C:2) 沒(méi)有因果關(guān)系、屬于同時(shí)發(fā)生事件。

Version vector

基于Vector clock我們可以獲得任意兩個(gè)事件的順序關(guān)系，結(jié)果或?yàn)橄群箜樞蚧驗(yàn)橥瑫r(shí)發(fā)生，識(shí)別事件順序在工程實(shí)踐中有很重要的引申應(yīng)用，最常見(jiàn)的應(yīng)用是發(fā)現(xiàn)數(shù)據(jù)沖突(detect conflict)。

分布式系統(tǒng)中數(shù)據(jù)一般存在多個(gè)副本(replication)，多個(gè)副本可能被同時(shí)更新，這會(huì)引起副本間數(shù)據(jù)不一致^[7]，Version vector的實(shí)現(xiàn)與Vector clock非常類(lèi)似^[8]，目的用于發(fā)現(xiàn)數(shù)據(jù)沖突^[9]。下面通過(guò)一個(gè)例子說(shuō)明Version vector的用法^[10]：

圖3: Version vector

• client端寫(xiě)入數(shù)據(jù)，該請(qǐng)求被S_x處理并創(chuàng)建相應(yīng)的vector ([S_x, 1])，記為數(shù)據(jù)D1

• 第2次請(qǐng)求也被S_x處理，數(shù)據(jù)修改為D2，vector修改為([S_x, 2])

• 第3、第4次請(qǐng)求分別被S_y、S_z處理，client端先讀取到D2，然后D3、D4被寫(xiě)入S_y、S_z

• 第5次更新時(shí)client端讀取到D2、D3和D4 3個(gè)數(shù)據(jù)版本，通過(guò)類(lèi)似Vector clock判斷同時(shí)發(fā)生關(guān)系的方法可判斷D3、D4存在數(shù)據(jù)沖突，最終通過(guò)一定方法解決數(shù)據(jù)沖突并寫(xiě)入D5

Vector clock只用于發(fā)現(xiàn)數(shù)據(jù)沖突，不能解決數(shù)據(jù)沖突。如何解決數(shù)據(jù)沖突因場(chǎng)景而異，具體方法有以最后更新為準(zhǔn)(last write win)，或?qū)_突的數(shù)據(jù)交給client由client端決定如何處理，或通過(guò)quorum決議事先避免數(shù)據(jù)沖突的情況發(fā)生^[11]。

由于記錄了所有數(shù)據(jù)在所有節(jié)點(diǎn)上的邏輯時(shí)鐘信息，Vector clock和Version vector在實(shí)際應(yīng)用中可能面臨的一個(gè)問(wèn)題是vector過(guò)大，用于數(shù)據(jù)管理的元數(shù)據(jù)(meta data)甚至大于數(shù)據(jù)本身^[12]。

解決該問(wèn)題的方法是使用server id取代client id創(chuàng)建vector (因?yàn)閟erver的數(shù)量相對(duì)client穩(wěn)定)，或設(shè)定最大的size、如果超過(guò)該size值則淘汰最舊的vector信息^[10][13]。

到此，關(guān)于“web分布式系統(tǒng)時(shí)間、時(shí)鐘和事件順序是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！