3.2　邏輯時(shí)鐘

在不使用物理時(shí)間的情況下，參考文獻(xiàn)[178]提出了一個(gè)happened-before模型，并采用邏輯時(shí)鐘定義事件之間相關(guān)順序的算法，解決了分布式系統(tǒng)中事件之間的排序問(wèn)題，但是這里的序是偏序關(guān)系（偏序關(guān)系可反映部分事件之間的因果關(guān)系），而不是全序關(guān)系。Lamport Logical Clocks（邏輯時(shí)鐘，LC）算法定義的偏序關(guān)系能夠正確地排列出具有因果關(guān)系的事件的次序（但是不能保證并發(fā)事件的真實(shí)順序），這使得分布式系統(tǒng)在邏輯上不會(huì)發(fā)生因果倒置的錯(cuò)誤。

然后，參考文獻(xiàn)[178]基于偏序又引入物理時(shí)間戳，給分布式系統(tǒng)中所有事件排定了全序。

3.2.1　因果（happened-before）模型

happened-before模型定義了兩個(gè)事件，這兩個(gè)事件如果符合下面3個(gè)關(guān)系中的一個(gè)，則說(shuō)明事件之間的時(shí)間就存在happened-before關(guān)系，即表明事件之間存在happened-before關(guān)系，也即表明若事件之間的因果關(guān)系是確定的則其發(fā)生的時(shí)間關(guān)系是確定的。

• 事件a和事件b在同一個(gè)進(jìn)程中發(fā)生：如果事件a在事件b之前發(fā)生，則事件a先于事件b，這時(shí)可表示為if a -> b then Ci(a) < Ci(b)，其中i表示同一個(gè)進(jìn)程；C[1]表示與事件的函數(shù)關(guān)系，通常用時(shí)間（時(shí)間表達(dá)的順序關(guān)系）映射此函數(shù)關(guān)系。
• 事件a和事件b在不同進(jìn)程中發(fā)生：如果事件a為數(shù)據(jù)在進(jìn)程P1上被發(fā)出，而事件b為數(shù)據(jù)在進(jìn)程P2上被接收，則事件a先于事件b，這時(shí)可表示為if a -> b then Ci(a) < Cj(b)，i、j表示不同進(jìn)程。
• 事件之間的傳遞關(guān)系：如果由Ci(a) < Cj(b)、Cj(b) < Ck(c)，可得到Ci(a) < Ck(c)，則說(shuō)明事件發(fā)生的順序滿足傳遞性。

其他任何不滿足上述關(guān)系的事件，都被稱為并發(fā)事件。

但是，如果由Ci(a) < Cj(b)并不能得到a -> b（前者是后者的必要不充分條件），即如果由時(shí)間戳大小，尚不能確定事件a和b兩者間是否具有可能的因果關(guān)系，則說(shuō)明存在“識(shí)別因果關(guān)系存在困難”。而happened-before模型表達(dá)的是“根據(jù)事件發(fā)生的真實(shí)情況生成因果關(guān)系是可行的”。請(qǐng)注意：這里強(qiáng)調(diào)了“生成（產(chǎn)生）”和“識(shí)別（讀取）”之間的差異。

Lamport根據(jù)該偏序關(guān)系提出了Lamport Logical Clocks算法，該算法最先拋棄將物理時(shí)鐘作為時(shí)間戳，提出將邏輯時(shí)鐘作為時(shí)間戳。

3.2.2　邏輯時(shí)鐘的實(shí)現(xiàn)

參考文獻(xiàn)[178]給出的Lamport Logical Clocks算法的內(nèi)容如下。

每個(gè)進(jìn)程Pi維護(hù)一個(gè)本地計(jì)數(shù)器Ci，Ci相當(dāng)于邏輯時(shí)鐘，并按照以下的規(guī)則更新Ci：

• 單進(jìn)程時(shí)鐘處理規(guī)則：每次執(zhí)行一個(gè)事件（如通過(guò)網(wǎng)絡(luò)發(fā)送消息，或者將消息交給應(yīng)用層，還可包括其他的一些內(nèi)部事件）之前，將Ci加1。
• 多進(jìn)程間時(shí)鐘處理規(guī)則：
• • 當(dāng)Pi發(fā)送消息m給Pj的時(shí)候，在消息m上附著上Ci。
  • 當(dāng)接收進(jìn)程Pj接收到Pi發(fā)送的消息時(shí)，更新自己的Cj=max{Cj, Ci}+1。

3.2.3　邏輯時(shí)鐘的缺點(diǎn)

1.1.1節(jié)給出了一個(gè)典型的日志問(wèn)題，這個(gè)問(wèn)題可以延伸為如下問(wèn)題。

那海藍(lán)藍(lán)、那天藍(lán)藍(lán)兩人分別要在某電子商務(wù)網(wǎng)站上買書(shū)。假設(shè)該電子商務(wù)網(wǎng)站的后臺(tái)架構(gòu)為：

1）前端代理服務(wù)器，負(fù)責(zé)接收用戶購(gòu)書(shū)請(qǐng)求。因?yàn)榫W(wǎng)站的用戶很多，所以有很多前端代理服務(wù)器。

2）購(gòu)書(shū)服務(wù)器負(fù)責(zé)存儲(chǔ)、管理相關(guān)圖書(shū)的數(shù)據(jù)。

假設(shè)該電子商務(wù)網(wǎng)站的后臺(tái)情況為：

1）那海藍(lán)藍(lán)的購(gòu)書(shū)請(qǐng)求發(fā)給前端代理服務(wù)器A，之后那天藍(lán)藍(lán)的購(gòu)書(shū)請(qǐng)求發(fā)給前端代理服務(wù)器B。兩個(gè)人要購(gòu)買同一本圖書(shū)，但被購(gòu)買的圖書(shū)只剩一本。

2）前端代理服務(wù)器A的物理時(shí)間是10，前端代理服務(wù)器B的物理時(shí)間是5。

3）因?yàn)槟翘焖{(lán)藍(lán)的購(gòu)書(shū)時(shí)間5早于那海藍(lán)藍(lán)的購(gòu)書(shū)時(shí)間10，所以購(gòu)書(shū)服務(wù)器支持了那天藍(lán)藍(lán)的購(gòu)書(shū)請(qǐng)求。

4）但實(shí)際情況是，那海藍(lán)藍(lán)購(gòu)書(shū)請(qǐng)求先發(fā)出卻沒(méi)有買到書(shū)，這似乎不公正。

Lamport Logical Clocks算法有其缺陷：事件a和事件b實(shí)際發(fā)生的順序不能僅通過(guò)比較Ci(a)和Cj(b)來(lái)決定。該算法不能很好地處理向外部傳遞的信息（如怎么從分布式系統(tǒng)之外，即從用戶的角度使看到的數(shù)據(jù)滿足線性一致性。Spanner系統(tǒng)結(jié)合分布的原子鐘、GPS、一些事務(wù)處理規(guī)則，共同構(gòu)成物理時(shí)間，并通過(guò)Truetime機(jī)制對(duì)事務(wù)的提交進(jìn)行全序排序）。

從系統(tǒng)之外看，基于邏輯時(shí)鐘定義出的全序關(guān)系（下節(jié)討論全序關(guān)系）與實(shí)際物理時(shí)間上發(fā)生的順序，在分布式系統(tǒng)下會(huì)存在不一致的情況。例如：事務(wù)T1與事務(wù)T2在邏輯時(shí)鐘這個(gè)軸上，事務(wù)T1因先提交并獲得一個(gè)邏輯時(shí)間戳值，故邏輯上先發(fā)生，事務(wù)T2后提交故邏輯上后發(fā)生。但是，在物理時(shí)間上，事務(wù)T2的提交可能先發(fā)生，事務(wù)T1的提交后發(fā)生；這樣邏輯時(shí)鐘和物理時(shí)鐘不能對(duì)應(yīng)，從系統(tǒng)之外看就會(huì)發(fā)現(xiàn)存在不一致的問(wèn)題。如何解決這個(gè)問(wèn)題呢？3.3節(jié)將討論的Vector Clocks（向量時(shí)鐘）算法、3.4節(jié)將討論的HLC（Hybird Logic Clocks，混合邏輯時(shí)鐘）算法，就是用于解決這個(gè)問(wèn)題的，同時(shí)也是對(duì)Lamport Logical Clocks算法進(jìn)行的改進(jìn)。

3.2.4　物理時(shí)鐘與同步問(wèn)題

參考文獻(xiàn)[178]還定義了物理時(shí)鐘和全序關(guān)系，即通過(guò)引入物理時(shí)鐘來(lái)排定事件之間的全序關(guān)系（只是這個(gè)全序關(guān)系定義的有些簡(jiǎn)單隨意[2]了），然后通過(guò)全序解決同步問(wèn)題[3]（換言之，偏序關(guān)系在分布式系統(tǒng)中是無(wú)法充分表達(dá)事件之間的正確順序的）。

所謂的同步問(wèn)題，是指在分布式系統(tǒng)下必須要確認(rèn)任何事件之間的發(fā)生順序，即全序關(guān)系。事件的全序關(guān)系是分布式系統(tǒng)中必須明確的，明確后才不至于出現(xiàn)“邏輯錯(cuò)誤”。

換言之，參考文獻(xiàn)[178]的核心在于：通過(guò)定義happened-before模型確定偏序關(guān)系，從而為定義全序關(guān)系做好鋪墊。然后通過(guò)引入物理時(shí)間戳定義全序關(guān)系，目的是解決分布式系統(tǒng)下事件間的全序問(wèn)題，避免分布式系統(tǒng)出現(xiàn)邏輯錯(cuò)誤。

---

[1]參考文獻(xiàn)[178]中的原文為：we define a clock Ci for each process Pi to be a function which assigns a number Ci(a) to any event a in that process. The entire system of clocks is represented by the function C which assigns to any event b the number C(b), where C(b) = Cj(b) if b is an event in process Pj.

[2]筆者認(rèn)為，該算法定義的總排序是比較隨意的。

[3]參考文獻(xiàn)[178]給出的原文為：We described an algorithm for extending that partial ordering to a somewhat arbitrary total ordering, and showed how this total ordering can be used to solve a simple synchronization problem.（我們描述了一種將偏序擴(kuò)展到任意的全序的算法，并展示了如何用這個(gè)全序來(lái)解決一個(gè)簡(jiǎn)單的同步問(wèn)題。）