Ordering

現(xiàn)實(shí)生活中時(shí)間可以記錄事情發(fā)生的時(shí)刻、比較事情發(fā)生的先后順序。

分布式系統(tǒng)的一些場景也需要記錄和比較不同節(jié)點(diǎn)間事件發(fā)生的順序。如數(shù)據(jù)寫入先后順序，事件發(fā)生的先后順序等等。

關(guān)系

復(fù)習(xí)下離散數(shù)學(xué)中關(guān)系：

假設(shè)A是一個(gè)集合 {1,2,3,4} ；R是集合A上的關(guān)系，例如{<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,4>,<2,4>,<3,4>}

• 自反性：任取一個(gè)A中的元素x，如果都有在R中，那么R是自反的。
  • <1,1>,<2,2>,<3,3>,<4,4>
• 對稱性：任取一個(gè)A中的元素x,y，如果 在關(guān)系R上,那么 也在關(guān)系R上，那么R是對稱的。
• 反對稱性：任取一個(gè)A中的元素x,y(x!=y)，如果 在關(guān)系R上,那么 不在關(guān)系R上，那么R是反對稱的。
  • 對于 <1,2>，有 <2,1> 不在R中；對于<2,4> 有<4,2>不在R中；對于<3,4> 有<4,3> 不在 R中，滿足。
• 傳遞性：任取一個(gè)A中的元素x,y,z，如果, 在關(guān)系R上，那么 也在關(guān)系R上，那么R是對稱的。
  • <1,1><1,2>在R中，并且<1,2>在R中；<1,1><1,4>在R中，并且<1,4>在R中；<2,2><2,4>在R中，并且<2,4>在R中；<3,3><3,4>在R中，并且<3,4>在R中；等等其他，滿足。
• 完全性（全關(guān)系）：包含了自反性；對集合A中所有，都有關(guān)系x到y(tǒng)或y到x；
  • R中并沒有<1, 3>，所以不滿足完全性

偏序The Partial Ordering

集合內(nèi)只有部分元素之間是可以比較的。

偏序關(guān)系的定義（R為A上的偏序關(guān)系）：設(shè)R是集合A上的一個(gè)二元關(guān)系，若R滿足：

• 反對稱性：對任意x,y∈A，若xRy，且yRx，則x=y；
• 傳遞性：對任意x, y,z∈A，若xRy，且yRz，則xRz
• 自反性：對任意x∈A，有xRx；

一個(gè)partitial ordering關(guān)系滿足的條件是自反的，反對稱的和可傳遞的，因此在partitial ordering中，可能有兩個(gè)元素之間是不相關(guān)的。

全序The Total Ordering

集合內(nèi)只有部分元素之間是可以比較的。

比如：比如復(fù)數(shù)集中并不是所有的數(shù)都可以比較大小，那么“大小”就是復(fù)數(shù)集的一個(gè)偏序關(guān)系。

全序關(guān)系的定義：

• 反對稱性：對任意x,y∈A，若xRy，且yRx，則x=y；
• 傳遞性：對任意x, y,z∈A，若xRy，且yRz，則xRz
• 完全性(total relation全關(guān)系)：對任意x,y∈A，由xRy或yRx （包括了自反性）

完全性本身也包括了自反性，所以全序關(guān)系是偏序關(guān)系。

所以偏序中滿足完全性就是全序了。

一個(gè)total ordering關(guān)系滿足的條件是反對稱的，可傳遞的和完全性，因此在total ordering中，兩個(gè)元素一定是有關(guān)系的，要么是a<>b或b<>a。

happens before

在分布式系統(tǒng)中，一個(gè)進(jìn)程包含一系列的事件，對于同一進(jìn)程內(nèi)的事件，如果a happens before b，那么a發(fā)生在b之前。并且，假定收或發(fā)消息都是一個(gè)事件。

happens before的定義如下(用->表示)

• 如果a和b在同一進(jìn)程中，并且a發(fā)生在b之前，那么a->b
• 如果a是一個(gè)進(jìn)程發(fā)消息的事件，b是另一個(gè)進(jìn)程接收這條消息的事件，則a->b
• 如果a->b且b->c，那么a->c。
• 如果同時(shí)不滿足a->b，且b->a，那么說a和b是并發(fā)的concurrent

[圖來自Time, Clocks, and the Ordering of Events in a Distributed System]

以一個(gè)例子來說明happens before關(guān)系，如上圖，垂直線上代表一個(gè)進(jìn)程，從下往上，時(shí)間依次增加，水平的距離代表空間的隔離。原點(diǎn)代表一個(gè)事件，而曲線代表一條消息。

從圖中很容易地看出，如果一個(gè)事件a，能通過進(jìn)程的線和消息線，到達(dá)b，那么a->b。

在圖中，p3和q4是并行的事件，因?yàn)椋挥械搅藀4才能確定q4的發(fā)生，而q3也只能確定p1發(fā)生。

clock時(shí)鐘

物理時(shí)鐘

晶振和時(shí)鐘偏移

計(jì)算機(jī)有固定頻率晶體的震蕩次數(shù)，晶體的振蕩周期決定了單機(jī)的時(shí)鐘精度。

時(shí)鐘頻率也可能因?yàn)闇囟鹊韧獠恳蛩貙?dǎo)致時(shí)鐘偏移，普通的石英晶體的漂移大10 ^-6^ 。 原子鐘的漂移約為 10^-13^ ，所以原子鐘精度遠(yuǎn)遠(yuǎn)高于石英晶體。

分布式下帶來的問題

不同機(jī)器上的物理時(shí)鐘難以同步，導(dǎo)致無法區(qū)分在分布式系統(tǒng)中多個(gè)節(jié)點(diǎn)的事件時(shí)序。即使設(shè)置了 NTP 時(shí)間同步節(jié)點(diǎn)間也存在毫秒級別的偏差，因而分布式系統(tǒng)需要有另外的方法記錄事件順序關(guān)系。

1978年Lamport在《Time, Clocks and the Ordering of Events in a Distributed System》中提出了邏輯時(shí)鐘的概念，來解決分布式系統(tǒng)中區(qū)分事件發(fā)生的時(shí)序問題。

邏輯時(shí)鐘Logical clocks

邏輯時(shí)鐘指的是分布式系統(tǒng)中用于區(qū)分事件的發(fā)生順序的時(shí)間機(jī)制。 從某種意義上講，現(xiàn)實(shí)世界中的物理時(shí)間其實(shí)是邏輯時(shí)鐘的特例。

Logical Clock解決的問題是找到一種方法，給分布式系統(tǒng)中所有時(shí)間定一個(gè)序，這個(gè)序能夠正確地排列出具有因果關(guān)系的事件（注意，是不能保證并發(fā)事件的真實(shí)順序的），使得分布式系統(tǒng)在邏輯上不會(huì)發(fā)生因果倒置的錯(cuò)誤。因果一致性

Lamport timestamps

論文

Time, Clocks, and the Ordering of Events in a Distributed System

Lamport timestamps

Leslie Lamport 在1978年提出邏輯時(shí)鐘的概念，并描述了一種邏輯時(shí)鐘的表示方法，這個(gè)方法被稱為Lamport時(shí)間戳(Lamport timestamps)。

分布式系統(tǒng)中按是否存在節(jié)點(diǎn)交互可分為三類事件:

• 發(fā)生在節(jié)點(diǎn)內(nèi)部
• 發(fā)送事件
• 接收事件

時(shí)鐘的定義如下

• 對于一個(gè)進(jìn)程i，Ci(a)表示進(jìn)程i中事件a的發(fā)生時(shí)間
• 對于整個(gè)系統(tǒng)來講，對于任意的事件b，其發(fā)生時(shí)間為C(b)，當(dāng)b為進(jìn)程j的事件時(shí)，則C(b) = Cj(b)為了使得事件按照正確的排序，需要使得如果事件a發(fā)生在事件b之前，那么a發(fā)生的時(shí)間要小于b，如下

for any events a, b

 if a->b then C(a) < C(b)

根據(jù)關(guān)系->的定義，我們可以得出

• 如果a和b都是進(jìn)程i中的事件，且a發(fā)生在b之前，那么Ci(a) < Ci(b)
• 如果事件a發(fā)送消息給事件b，a屬于進(jìn)程i，b屬于進(jìn)程j，那么Ci(a) < Cj(b)

為了讓系統(tǒng)滿足上述條件，在實(shí)現(xiàn)中，需要滿足以下原則

• 對于每個(gè)進(jìn)程，相鄰的事件的時(shí)鐘要增加1
• (a) 如果事件a是進(jìn)程i發(fā)送消息m的事件，發(fā)送時(shí)帶時(shí)間戳Tm = Ci(a)，(b)事件b是進(jìn)程j接受消息m的事件，那么事件b的取值為max(進(jìn)程b的當(dāng)前時(shí)鐘，Tm+1)

假設(shè)有事件a、b，C(a)、C(b)分別表示事件a、b對應(yīng)的Lamport時(shí)間戳，如果a->b,則C(a) < C(b)，a發(fā)生在b之前(happened before)。

所以Lamport timestamps原理如下：

• 每個(gè)事件對應(yīng)一個(gè)Lamport時(shí)間戳，初始值為0
• 如果事件在節(jié)點(diǎn)內(nèi)發(fā)生，時(shí)間戳加1
• 如果事件屬于發(fā)送事件，時(shí)間戳加1并在消息中帶上該時(shí)間戳
• 如果事件屬于接收事件，時(shí)間戳 = Max(本地時(shí)間戳，消息中的時(shí)間戳) + 1

通過該定義，事件集中Lamport時(shí)間戳不等的事件可進(jìn)行比較，我們獲得事件的偏序關(guān)系(partial order)。

上圖更形象的解釋了事件之間的關(guān)系。

以B4事件為基準(zhǔn)：

• B4左邊深灰色的區(qū)域的事件，都發(fā)生在B4前，和B4具有因果關(guān)系，這些事件屬于與B4因果關(guān)系中的因(cause)
• B4右邊的深紅色區(qū)域的事件，都發(fā)生在B4后，和B4具有因果關(guān)系，這些事件屬于與B4因果關(guān)系中的果(effect)
• B4上下的白色區(qū)域是跟B4無關(guān)的事件，可以認(rèn)為是并發(fā)關(guān)系(concurrent)
• 在淺灰色和淺紅色區(qū)域中的事件，C2、A3兩個(gè)事件與B4是并行關(guān)系，根據(jù)Lamport timestamps的定義，將他們判定為與B4具前后關(guān)系。（所以Lamport timestamps并不能嚴(yán)格的表示并行關(guān)系）

Lamport timestamps與偏序關(guān)系

Lamport timestamps只保證因果關(guān)系（偏序）的正確性，不保證絕對時(shí)序的正確性。

Lamport logical clock

由于Lamport timestamps只能得到偏序關(guān)系，如果要得到全序關(guān)系，就需要給Ci(a) = Cj(b)的事件定一個(gè)先后順序。

total order的事件關(guān)系=>定義如下：

如果事件a發(fā)生在進(jìn)程Pi，事件b發(fā)生在進(jìn)程Pj，那么當(dāng)滿足下列兩者條件之一時(shí)，a=>b

• Ci(a) < Cj(b)
• Ci(a) = Cj(b) 且 Pi < Pj

根據(jù)以上條件，對于任意的兩個(gè)事件，都能判斷出它們之間的關(guān)系，因此是total ordering的。

當(dāng)Lamport timestamp一致時(shí)，通過義Pi < Pj來定義順序，確保分布式場景下各個(gè)進(jìn)程間發(fā)生的事件的全序定義。至于Pj < Pj：可采用不同的方式，Lamport Logical Clock提到的 arbitrary total ordering。

vector clock

Lamport timestamp得到的是全序關(guān)系，但無法嚴(yán)格表示對于沒有因果關(guān)系、存在同時(shí)發(fā)生關(guān)系(concurrent)的事件。

Vector clock是在Lamport timestamp基礎(chǔ)上改進(jìn)的一種邏輯時(shí)鐘方法，它構(gòu)不但記錄本節(jié)點(diǎn)的Lamport timestamp，同時(shí)也記錄了其他節(jié)點(diǎn)的Lamport timestamp。

原理如下:

• 本地vector clock的clock數(shù)組中每一個(gè)邏輯時(shí)間(clock)對應(yīng)一個(gè)進(jìn)程的clock
• 初始化vector clock中每一個(gè)邏輯時(shí)間為0；
• 每一次處理內(nèi)完內(nèi)部事件，將vector clock中自己的邏輯時(shí)間戳+1；
• 每發(fā)送一個(gè)消息的時(shí)候，將vector clock中自己的邏輯時(shí)間+1，且將其和消息一起發(fā)送出去
• 每接收到一個(gè)消息的時(shí)候，需要將本地的vector clock中自己的邏輯時(shí)間戳+1，且將自己vector clock中的邏輯時(shí)間和消息中攜帶的進(jìn)行比較，取最大的更新本地vector clock中的邏輯時(shí)間。

圖來源于wikipedia

vector clock判定并發(fā)關(guān)系：

• 事件i、事件j對應(yīng)的vector clock中，每一個(gè)進(jìn)程Pk的邏輯時(shí)間戳都滿足Vi[Pk]
• vector clock中，存在P1、P2，使得Vi[P1]Vj[P2]，我們稱事件i和事件j是并發(fā)關(guān)系(沒有因果關(guān)系)；

和之前l(fā)amport timestamp的一樣，以B4事件為基準(zhǔn)(vector clock為[A:2,B:4,C:1])，根據(jù)vector clock的判定，可以判斷出

• 灰色區(qū)域的事件happens before B4事件，B4事件happens before紅色區(qū)域的事件
• 白色區(qū)域與B4事件沒有因果關(guān)系。

特性：

• vector clock不需要在節(jié)點(diǎn)之間同步時(shí)鐘，不需要在所有節(jié)點(diǎn)上維護(hù)一段數(shù)據(jù)的版本數(shù)；
• 缺點(diǎn)是時(shí)鐘值的大小隨著節(jié)點(diǎn)增多和時(shí)間不斷增長

version vector

分布式系統(tǒng)多個(gè)副本被同時(shí)更新時(shí)，會(huì)導(dǎo)致副本之間數(shù)據(jù)的不一致。version vector用于來發(fā)現(xiàn)這些不一致的沖突。

version vector只能發(fā)現(xiàn)沖突，無法解決沖突；當(dāng)然也可以通過再添加一個(gè)維度信息timestamp，發(fā)生沖突時(shí)進(jìn)行比較，但是又回到了物理時(shí)鐘不同步的問題。

下圖展示了數(shù)據(jù)由不同副本處理后導(dǎo)致的不同版本沖突。

D5時(shí)發(fā)現(xiàn)了數(shù)據(jù)的沖突，這時(shí)會(huì)將不同版本數(shù)據(jù)都存儲下來，一般由客戶端來解決沖突。

version vector與vector clock的差異

• vector clocks 使用 receive和send 方法來更新clock,而version vector使用sync方法來更新。
• vector clocks是給事件定序的，確定事件的因果關(guān)系；而version vector是確定同一個(gè)數(shù)據(jù)不同版本的因果關(guān)系。

分布式與時(shí)鐘

分布式系統(tǒng)中，每個(gè)節(jié)點(diǎn)的物理時(shí)鐘是不同步的，都有一定的差異。

這樣就帶來了一些分布式系統(tǒng)實(shí)現(xiàn)的難題，如基于MVCC實(shí)現(xiàn)的事務(wù)，基于MVCC實(shí)現(xiàn)事務(wù)會(huì)要求版本之間能判斷先后順序，只有確定先后才知道應(yīng)該用哪一個(gè)版本的數(shù)據(jù)，確定先后順序就涉及到時(shí)間，而不同機(jī)器之間的本地時(shí)鐘是無法保證一致的，所以這就需要確保時(shí)鐘的同步。

而通常解決方案有兩種：

• 中心化的時(shí)鐘方案，如Timestamp oracle(TSO)
• 無中心化的時(shí)鐘方案，如google True Time，Hybrid Logic Time

Timestamp oracle

如果我們整個(gè)系統(tǒng)不復(fù)雜，而且沒有跨全球的需求，這時(shí)用一臺中心授時(shí)服務(wù)就可以了。

如TiDB使用的就是TSO方案，tipb作為一個(gè)TSO集群，來提供授時(shí)服務(wù)。

使用TSO的好處在于因?yàn)橹挥幸粋€(gè)中心授時(shí)，所以我們一定能確定所有時(shí)間的時(shí)間，但TSO需要關(guān)注幾個(gè)問題：

• 網(wǎng)絡(luò)延時(shí)：因?yàn)樗械氖录夹枰獜腡SO獲取時(shí)間，所以TSO只適合小集群部署，不能是那種全球級別的數(shù)據(jù)庫
• 性能：每個(gè)事件都需要從TSO獲取時(shí)間，所以TSO需要非常高的性能
• 容錯(cuò)：TSO是一個(gè)單點(diǎn)，需要考慮節(jié)點(diǎn)的failover

True Time

由于節(jié)點(diǎn)間NTP是有偏差的，且可能出現(xiàn)時(shí)間回退的情況，所以NTP無法準(zhǔn)確的判定事件的全序關(guān)系。在Google Spanner里面，通過引入True Time來解決了分布式時(shí)間問題。

True Time實(shí)現(xiàn)

Spanner通過使用GPS + 原子鐘atomic clock來對集群的機(jī)器時(shí)間進(jìn)行校對，保證了集群機(jī)器的時(shí)間戳差距不會(huì)超過一個(gè)上限值(ε)。

用兩種技術(shù)來處理，是因?yàn)閷?dǎo)致這兩種技術(shù)的失敗的原因是不同的。

• GPS會(huì)有一個(gè)天線，電波干擾會(huì)導(dǎo)致其失靈。原子鐘很穩(wěn)定。
• 當(dāng)GPS失靈的時(shí)候，原子鐘仍然能保證在相當(dāng)長的時(shí)間內(nèi)，不會(huì)出現(xiàn)偏差。

API

• TT.now() : 返回一個(gè)當(dāng)前時(shí)間，其位于范圍區(qū)間[earliest,latest]
• TT.after(t) : 當(dāng)前時(shí)間是否在t之后
• TT.before(t) : 當(dāng)前時(shí)間是否在t之前

雖然spanner引入了TrueTime可以得到全球范圍的時(shí)序一致性，但由于TrueTime返回的時(shí)間仍然有一定的偏差，如果要給兩個(gè)事件定序，就需要等待2個(gè)偏差的時(shí)間間隔，來確保其先后順序。

• 事件a：[Tai, Taj], Taj-Tai=ε
• 事件b：[Tbi, Tbj], Tbj-Tbi=ε
• 所以要確定b>a, 那么就要確保Tbi > Taj, 就需要在事件b進(jìn)行等待，以確保：事件b時(shí)間 - 事件a時(shí)間 > 2ε

Hybrid logical clock

HLC

Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases

TrueTime 需要硬件的支持，所以有一定的成本，而HLC無需硬件支持也能解決分布式下時(shí)間問題。

HLC同時(shí)使用了物理時(shí)鐘和邏輯時(shí)鐘（physical clock + logical clock），能夠保證單點(diǎn)的時(shí)間發(fā)生器是單調(diào)遞增的，同時(shí)能夠盡量控制不同節(jié)點(diǎn)之間的時(shí)鐘偏差在規(guī)定的偏差范圍內(nèi)。

判斷兩個(gè)事件的先后順序：先判斷物理時(shí)間，再判斷邏輯時(shí)間。

HLC的算法

l.j維護(hù)的是節(jié)點(diǎn)j當(dāng)前已知的最大的物理時(shí)間(wall time)，c.j則是當(dāng)前的邏輯時(shí)間。

// 在節(jié)點(diǎn)j上面：初始化: l.j = 0，c.j = 0。
initially l.j :=0; c.j := 0


// 本地事件或者發(fā)送消息時(shí)，
// 如果本地時(shí)鐘pt大于當(dāng)前的混合邏輯時(shí)鐘的l，
// 則將l更新成本地時(shí)鐘，將c清零。
// 否則，l保持不變，將c加1。
Send or local event
{
    l'.j := l.j;
    l.j := max(l'.j, pt.j);    // 本地物理時(shí)間pt
    if (l.j = l'.j) then 
        c.j := c.j+1
    else 
        c.j := 0;
    Timestamp with l.j, c.j
}


// 收到消息時(shí)
// l在 當(dāng)前的邏輯時(shí)鐘的l、機(jī)器的本地時(shí)鐘pt、收到消息里面帶的l，三者中取最大的。
// 如果l部分是更新為本地時(shí)鐘了，則將c清零。否則，c取較大的那個(gè)l對應(yīng)到的c加1。
Receive event of message m
{
    l'.j := l.j;
    l.j := max(l'.j, l.m, pt.j);
    if (l.j = l'.j = l.m) then 
        c.j := max(c.j, c.m) + 1
    elseif (l.j=l'.j) then 
        c.j := c.j + 1
    elseif (l.j=l.m) then 
        c.j := c.m + 1
    else 
        c.j := 0
    Timestamp with l.j, c.j
}

特性

HLC算法保證了HLC時(shí)間有如下特性：

• 事件e發(fā)生在事件f之前，那么事件e的HLC時(shí)間一定小于事件f的HLC時(shí)間：(l.e, c.e) < (l.f, c.f)
• 本地WallTime大于等于本地物理時(shí)間(l.e ≥ pt.e)：HLC時(shí)間總是不斷遞增，不會(huì)隨著物理時(shí)間發(fā)生回退。
• 對事件e，l.e是事件e能感知的到的最大物理時(shí)間值：如果l.e > pt.e，那么一定存在著一個(gè)發(fā)生在e之前的事件g，有pt.g=l.e。簡單來說是如果出現(xiàn)l.e > pt.e肯定是因?yàn)橛幸粋€(gè)HLC時(shí)間更大的的節(jié)點(diǎn)把當(dāng)前節(jié)點(diǎn)的HLC時(shí)間往后推了。
• WallTime和物理時(shí)鐘的偏差是有界的(ε ≥ |pt.e - l.e| )：因?yàn)楣?jié)點(diǎn)之間通過NTP服務(wù)校時(shí)，那么節(jié)點(diǎn)之間的物理時(shí)鐘偏差一定小于某個(gè)值ε。那么對于任一事件b和e，如果b hb e，那么事件b的物理時(shí)間pt.b一定滿足pt.e + ε ≥ pt.b。結(jié)合特性3存在一個(gè)事件g滿足，l.e = pt.g。那么 pt.e + ε ≥ l.e=pt.g > pt.e。

開源實(shí)現(xiàn)

CockroachDB采用基于NTP時(shí)鐘同步的HLC去中心化方案。

時(shí)鐘同步

所有節(jié)點(diǎn)間的RPC消息都會(huì)把時(shí)間戳帶入到消息中，接收到消息的節(jié)點(diǎn)會(huì)通過消息中的時(shí)間戳更新自己的時(shí)間, 從而達(dá)到節(jié)點(diǎn)間時(shí)間同步的效果。

代碼分析

HLC定義

// Timestamp represents a state of the hybrid logical clock.
type Timestamp struct {
    // Holds a wall time, typically a unix epoch time
    // expressed in nanoseconds.
    WallTime int64 `protobuf:"varint,1,opt,name=wall_time,json=wallTime" json:"wall_time"`
    // The logical component captures causality for events whose wall
    // times are equal. It is effectively bounded by (maximum clock
    // skew)/(minimal ns between events) and nearly impossible to
    // overflow.
    Logical int32 `protobuf:"varint,2,opt,name=logical" json:"logical"`
}

• WallTime：本地已知物理時(shí)鐘
• Logical：邏輯時(shí)鐘
• Timestamp：HLC，單調(diào)遞增

獲取物理時(shí)鐘

// PhysicalNow returns the local wall time. It corresponds to the physicalClock
// provided at instantiation. For a timestamp value, use Now() instead.
func (c *Clock) PhysicalNow() int64 {
    c.mu.Lock()
    defer c.mu.Unlock()
    return c.getPhysicalClockLocked()
}


// getPhysicalClockLocked returns the current physical clock and checks for
// time jumps.
func (c *Clock) getPhysicalClockLocked() int64 {
    // physicalClock 就是 UnixNano
    newTime := c.physicalClock()


    if c.mu.lastPhysicalTime != 0 {
        interval := c.mu.lastPhysicalTime - newTime
        // 檢查時(shí)鐘是否回退
        if interval > int64(c.maxOffset/10) {
            c.mu.monotonicityErrorsCount++
            log.Warningf(context.TODO(), "backward time jump detected (%f seconds)", float64(-interval)/1e9)
        }
    }


    c.mu.lastPhysicalTime = newTime
    return newTime
}




// UnixNano returns the local machine's physical nanosecond
// unix epoch timestamp as a convenience to create a HLC via
// c := hlc.NewClock(hlc.UnixNano, ...).
func UnixNano() int64 {
    return timeutil.Now().UnixNano()
}

獲取當(dāng)前HLC時(shí)鐘

// Now returns a timestamp associated with an event from
// the local machine that may be sent to other members
// of the distributed network. This is the counterpart
// of Update, which is passed a timestamp received from
// another member of the distributed network.
func (c *Clock) Now() Timestamp {
    c.mu.Lock()
    defer c.mu.Unlock()
    if physicalClock := c.getPhysicalClockLocked(); c.mu.timestamp.WallTime >= physicalClock {
        // The wall time is ahead, so the logical clock ticks.
        c.mu.timestamp.Logical++
    } else {
        // Use the physical clock, and reset the logical one.
        c.mu.timestamp.WallTime = physicalClock
        c.mu.timestamp.Logical = 0
    }
    return c.mu.timestamp
}

• 如果當(dāng)前物理時(shí)鐘小于WallTime，則將邏輯時(shí)鐘+1
• 如果當(dāng)前物理時(shí)鐘大于WallTime，則更新WallTime為當(dāng)前物理時(shí)鐘，且將邏輯時(shí)鐘設(shè)置為0

節(jié)點(diǎn)時(shí)鐘同步

節(jié)點(diǎn)之間通過在RPC請求中攜帶HLC時(shí)間來進(jìn)行時(shí)鐘同步。

// sendSingleRange gathers and rearranges the replicas, and makes an RPC call.
func (ds *DistSender) sendSingleRange(
    ctx context.Context, ba roachpb.BatchRequest, desc *roachpb.RangeDescriptor,
) (*roachpb.BatchResponse, *roachpb.Error) {
    ......

    br, err := ds.sendRPC(ctx, desc.RangeID, replicas, ba)
    if err != nil {
        log.ErrEvent(ctx, err.Error())
        return nil, roachpb.NewError(err)
    }


    // If the reply contains a timestamp, update the local HLC with it.
    if br.Error != nil && br.Error.Now != (hlc.Timestamp{}) {
        ds.clock.Update(br.Error.Now)
    } else if br.Now != (hlc.Timestamp{}) {
        ds.clock.Update(br.Now)
    }

    ......
}




// Update takes a hybrid timestamp, usually originating from
// an event received from another member of a distributed
// system. The clock is updated and the hybrid timestamp
// associated to the receipt of the event returned.
// An error may only occur if offset checking is active and
// the remote timestamp was rejected due to clock offset,
// in which case the timestamp of the clock will not have been
// altered.
// To timestamp events of local origin, use Now instead.
func (c *Clock) Update(rt Timestamp) Timestamp {
    c.mu.Lock()
    defer c.mu.Unlock()

    // 如果本地物理時(shí)間pt
    physicalClock := c.getPhysicalClockLocked()


    // 大于本地WallTime且大于rt.WallTime：
    //      更新本地WallTime=pt，且logical=0
    if physicalClock > c.mu.timestamp.WallTime && physicalClock > rt.WallTime {
        // Our physical clock is ahead of both wall times. It is used
        // as the new wall time and the logical clock is reset.
        c.mu.timestamp.WallTime = physicalClock
        c.mu.timestamp.Logical = 0
        return c.mu.timestamp
    }


    // In the remaining cases, our physical clock plays no role
    // as it is behind the local or remote wall times. Instead,
    // the logical clock comes into play.

    // 如果rt.WallTime > 本地WallTime：
    //   檢查rt.WallTime與pt是否大于時(shí)鐘偏差；
    //   本地WallTime=rt.WallTime，logical++
    if rt.WallTime > c.mu.timestamp.WallTime {
        offset := time.Duration(rt.WallTime-physicalClock) * time.Nanosecond
        if c.maxOffset > 0 && offset > c.maxOffset {
            log.Warningf(context.TODO(), "remote wall time is too far ahead (%s) to be trustworthy - updating anyway", offset)
        }
        // The remote clock is ahead of ours, and we update
        // our own logical clock with theirs.
        c.mu.timestamp.WallTime = rt.WallTime
        c.mu.timestamp.Logical = rt.Logical + 1
    } else if c.mu.timestamp.WallTime > rt.WallTime {
       // 如果本地WallTime>rt.WallTime：logical++
        // Our wall time is larger, so it remains but we tick
        // the logical clock.
        c.mu.timestamp.Logical++
    } else {
        // Both wall times are equal, and the larger logical
        // clock is used for the update.
        if rt.Logical > c.mu.timestamp.Logical {
            c.mu.timestamp.Logical = rt.Logical
        }
        c.mu.timestamp.Logical++
    }
    return c.mu.timestamp
}