本系列文章主要介紹計算機系統(tǒng)中時鐘的處理。主要內(nèi)容包含NTP，Lamport邏輯時鐘，向量時鐘，TrueTime等。本文是第五篇，介紹混合邏輯時鐘(Hybrid Logical Clocks)。
計算機的時鐘（一）：NTP協(xié)議
計算機的時鐘（二）：Lamport邏輯時鐘
計算機的時鐘（三）：向量時鐘
計算機的時鐘（四）：TrueTime
在本系列前面的文章中我們介紹了計算機處理時鐘的兩種方式，一種是物理時鐘，包括NTP協(xié)議和TrueTime都屬于物理時鐘，另一種是邏輯時鐘，包括Lamport邏輯時鐘和向量時鐘。這兩種時鐘有各自的優(yōu)缺點。物理時鐘的優(yōu)點在于直觀，就是真實世界的時間，使用方便，缺點在于無法做到絕對精確，成本相對高一些。邏輯時鐘的優(yōu)點在于可以做到精確的因果關(guān)系，缺點在于節(jié)點之間需要通信，而且使用上不如物理時鐘直觀。
本文介紹的混合邏輯時鐘(HLC)將物理時鐘和邏輯時鐘結(jié)合起來，我們來看看它是怎么一回事。

HLC介紹

HLC由Sandeep Kulkarni, Murat Demirbas, Deepak Madeppa, Bharadwaj Avva, and Marcelo Leone在2014年的論文《Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases》中提出。目的是為了填補理論（邏輯時鐘）和實際（物理時鐘）之間的差距，支持因果關(guān)系，同時又有物理時鐘的直觀特點。

給分布式系統(tǒng)中每個事件分配一個HLC，比如e事件的HLC記作 l.e，HLC保證能夠滿足以下四個性質(zhì)：

1. 如果 e 事件發(fā)生在 f 事件之前（e happened before f），那么 l.e 一定小于 l.f，也就是滿足因果關(guān)系。
2. l.e 可以存儲在一個整數(shù)中，不會隨著分布式系統(tǒng)中節(jié)點數(shù)的增加而增加。（這點和向量時鐘不一樣，向量時鐘會隨著節(jié)點數(shù)的增加而增加）
3. l.e 的值不會無限增長。（這點和Lamport邏輯時鐘不一樣，Lamport邏輯時鐘會無限增長）
4. l.e 的值和 e 事件發(fā)生的物理時鐘值接近，| l.e - pt.e |的值會小于一定的范圍。

第一版算法

回顧之前介紹過的Lamport邏輯時鐘算法：
記事件 j 的邏輯時鐘為 l.j

初始化：l.j = 0
發(fā)送消息事件或者本地事件：l.j = l.j + 1
接收m消息事件：l.j = max(l.j, l.m) + 1

如果想在算法中引入物理時鐘，最簡單的做法是每次修改邏輯時鐘的時候，比較邏輯時鐘和物理時鐘的大小，取最大的值。
記事件 j 發(fā)生時的物理時鐘值為 pt.j，算法變成了：

初始化：l.j = 0
發(fā)送消息事件或者本地事件：l.j = max(l.j + 1, pt.j)
接收m消息事件：l.j = max(l.j + 1, l.m + 1, pt.j)

從算法中可以很容易地看出滿足上面說的HLC性質(zhì)1和2。然而算法不滿足性質(zhì)3和性質(zhì)4。舉個例子：

圖一

分布式系統(tǒng)中有4個節(jié)點，每個矩形中左邊的數(shù)字是本節(jié)點的物理時鐘 pt，右邊是本節(jié)點的邏輯時鐘 l。消息從節(jié)點0依次到節(jié)點1，節(jié)點2，節(jié)點3，再到節(jié)點1。到了節(jié)點1的時候，從圖中可以看到物理時鐘和邏輯時鐘的差距 |l - pt| 是13。如果整個系統(tǒng)中事件發(fā)生的頻率比較高，可以想象到，物理時鐘和邏輯時鐘的差距會越來越大。這違反了性質(zhì)3和性質(zhì)4。
為什么會發(fā)生這個問題？原因是雖然在Lamport邏輯時鐘的基礎(chǔ)上引入了物理時鐘，但是我們卻不知道這個值究竟是物理時鐘增長導(dǎo)致的還是邏輯時鐘增長導(dǎo)致的。這樣即使物理時鐘的增長追趕上了邏輯時鐘的增長，我們也沒辦法重置邏輯時鐘部分的值。
第一版算法涼涼。

第二版算法

為了解決這個問題，很自然地想到把物理時鐘和邏輯時鐘分開來表示。我們把HLC分成兩部分 l.j 和 c.j。l.j 表示事件 j 發(fā)生時所感知到的最大物理時鐘值，c.j 是事件 j 的邏輯時鐘部分，當(dāng)幾個事件在同一個物理時鐘值內(nèi)發(fā)生時，c 用于記錄事件之間的因果關(guān)系。pt 依然表示本地NTP協(xié)議的物理時鐘值。新的算法如下：

初始化：l.j = 0; c.j = 0
發(fā)送消息事件或者本地事件：
  if pt.j <= l.j then c.j = c.j + 1
  else c.j = 0; l.j = pt.j
接收m消息事件：
  if l.j == m.j == pt.j then c.j = max(c.j, c.m) + 1
  else if pt.j <= l.j and l.m <= l.j then c.j = c.j + 1
  else if pt.j <= l.m and l.j <= l.m then c.j = c.m + 1; l.j = l.m
  else c.j = 0; l.j = pt.j

新算法執(zhí)行的過程中，本地時鐘的值通過NTP協(xié)議更新，HLC的值并不會修改本地時鐘的值。由于分離了物理時鐘和邏輯時鐘，新的事件發(fā)生時，如果物理時鐘部分的值沒增長，就只增加邏輯時鐘部分的值。如果本地的物理時鐘趕上了HLC的物理時鐘部分的值 l.j，就可以重置邏輯時鐘部分的值 c.j，并把 l.j 更新為新的本地物理時鐘。這樣就可以解決第一版算法中HLC無限增長的問題，也滿足了性質(zhì)3和性質(zhì)4的要求。具體數(shù)學(xué)證明過程參考論文。
對于任何一個事件 j，pt.j <= l.j，也即HLC的物理時鐘部分的值一定大于等于本地NTP的時鐘值。假設(shè)整個分布式系統(tǒng)中，NTP協(xié)議的時鐘誤差值為 ε。新算法中，對于任何一個事件 j，| l.j - pt.j | <= ε，也就是HLC物理部分的值和本地物理時鐘值的差距不會超過 ε。根據(jù)前文計算機的時鐘（一）：NTP協(xié)議的介紹，這個誤差值在局域網(wǎng)內(nèi)大概1毫秒內(nèi)，廣域網(wǎng)可能達到100毫秒或更大。
使用新算法來分析第一版算法中的例子：

圖二

HLC的異常處理

如果某個節(jié)點的NTP物理時鐘值出現(xiàn)了異常，比如變成一個極大的值，其他節(jié)點收到這個故障節(jié)點的消息，會導(dǎo)致其他節(jié)點的HLC值出現(xiàn)問題。為了阻止故障的擴散，可以設(shè)置HLC物理部分偏差的上限，如果收到的消息物理部分值的偏差超過上限，忽略這條消息，同時發(fā)送告警等待人工處理。

HLC的性能數(shù)據(jù)

論文中給出了HLC的性能測試數(shù)據(jù)。

圖三

圖四

HLC應(yīng)用

HLC可以用于分布式數(shù)據(jù)庫一致性快照讀的處理中。很多系統(tǒng)中都使用了HLC，比如HBase和CockRoachDB。

圖五

比如，我們要獲取 t = 10 這個時間點的數(shù)據(jù)快照，也即HLC為(l = 10, c = 0)，拿這個HLC值去每個節(jié)點查找，可以得出上圖中黑色的粗線，這條線對應(yīng)的數(shù)據(jù)就是系統(tǒng)在 t = 10 的數(shù)據(jù)快照。
CockRoachDB在分布式事務(wù)中使用了HLC。根據(jù)HLC的性質(zhì)4，| l.e - pt.e |的值會小于一定的范圍 MaxOffset，CockRoachDB默認這個值為500毫秒，pt.e + MaxOffset一定是系統(tǒng)中最大的物理時間。啟動事務(wù)時會獲取本地的HLC值 hlc.e，并且確定一個區(qū)間 [ hlc.e, hlc.e + MaxOffset ]，然后發(fā)往其他節(jié)點執(zhí)行快照讀，如果節(jié)點上某個數(shù)據(jù)的HLC值為 hlc.g，分三種情況考慮：

1. 如果 hlc.e + MaxOffset < hlc.g，即處于區(qū)間的右邊，那么e事件肯定發(fā)生在g事件之前，不能讀取這個數(shù)據(jù)。
2. 如果 hlc.e < hlc.g <= hlc.e + MaxOffs，即處于區(qū)間之中，由于物理時鐘的不確定性，不能分辨出e事件和g事件的先后關(guān)系。這個時候需要重啟事務(wù)，獲取一個更大的hlc，相當(dāng)于等待這個不確定的時間過去，推遲事務(wù)的執(zhí)行。
3. 如果 hlc.g < hlc.e，那么g事件肯定發(fā)生在e之前，這時可以讀取這個數(shù)據(jù)。（對于這點我有點疑問，由于不確定時間的存在，物理時間可能快，也可能慢，這個區(qū)間應(yīng)該是[ hlc.e - MaxOffset, hlc.e + MaxOffset ]，為什么這里hlc.g < hlc.e就認為g在e前面？）

總結(jié)

整個系列一直在物理時鐘和邏輯時鐘之間打轉(zhuǎn)。先介紹了最直觀的NTP協(xié)議，由于NTP協(xié)議的不可靠性，引入了邏輯時鐘，包括Lamport邏輯時鐘和向量時鐘，但是邏輯時鐘只能確保因果關(guān)系，并且需要消息的傳遞，由此又引入了更精確的物理時鐘TrueTime，最后是把物理時鐘和邏輯時鐘結(jié)合起來的混合邏輯時鐘。

參考

Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases
CockroachDB分布式事務(wù)解密