本系列文章主要介紹計(jì)算機(jī)系統(tǒng)中時(shí)鐘的處理翅帜。主要內(nèi)容包含NTP怜浅，Lamport邏輯時(shí)鐘，向量時(shí)鐘爽醋，TrueTime等蚁署。本文是第五篇，介紹混合邏輯時(shí)鐘(Hybrid Logical Clocks)蚂四。
計(jì)算機(jī)的時(shí)鐘（一）：NTP協(xié)議
計(jì)算機(jī)的時(shí)鐘（二）：Lamport邏輯時(shí)鐘
計(jì)算機(jī)的時(shí)鐘（三）：向量時(shí)鐘
計(jì)算機(jī)的時(shí)鐘（四）：TrueTime
在本系列前面的文章中我們介紹了計(jì)算機(jī)處理時(shí)鐘的兩種方式光戈，一種是物理時(shí)鐘哪痰，包括NTP協(xié)議和TrueTime都屬于物理時(shí)鐘，另一種是邏輯時(shí)鐘久妆，包括Lamport邏輯時(shí)鐘和向量時(shí)鐘晌杰。這兩種時(shí)鐘有各自的優(yōu)缺點(diǎn)。物理時(shí)鐘的優(yōu)點(diǎn)在于直觀筷弦，就是真實(shí)世界的時(shí)間肋演，使用方便，缺點(diǎn)在于無(wú)法做到絕對(duì)精確奸笤，成本相對(duì)高一些惋啃。邏輯時(shí)鐘的優(yōu)點(diǎn)在于可以做到精確的因果關(guān)系哼鬓，缺點(diǎn)在于節(jié)點(diǎn)之間需要通信监右，而且使用上不如物理時(shí)鐘直觀。
本文介紹的混合邏輯時(shí)鐘(HLC)將物理時(shí)鐘和邏輯時(shí)鐘結(jié)合起來(lái)异希，我們來(lái)看看它是怎么一回事健盒。

HLC介紹

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

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

1. 如果 e 事件發(fā)生在 f 事件之前（e happened before f），那么 l.e 一定小于 l.f授药，也就是滿足因果關(guān)系士嚎。
2. l.e 可以存儲(chǔ)在一個(gè)整數(shù)中，不會(huì)隨著分布式系統(tǒng)中節(jié)點(diǎn)數(shù)的增加而增加悔叽。（這點(diǎn)和向量時(shí)鐘不一樣莱衩，向量時(shí)鐘會(huì)隨著節(jié)點(diǎn)數(shù)的增加而增加）
3. l.e 的值不會(huì)無(wú)限增長(zhǎng)。（這點(diǎn)和Lamport邏輯時(shí)鐘不一樣娇澎，Lamport邏輯時(shí)鐘會(huì)無(wú)限增長(zhǎng)）
4. l.e 的值和 e 事件發(fā)生的物理時(shí)鐘值接近笨蚁，| l.e - pt.e |的值會(huì)小于一定的范圍。

第一版算法

回顧之前介紹過(guò)的Lamport邏輯時(shí)鐘算法：
記事件 j 的邏輯時(shí)鐘為 l.j

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

如果想在算法中引入物理時(shí)鐘趟庄，最簡(jiǎn)單的做法是每次修改邏輯時(shí)鐘的時(shí)候括细，比較邏輯時(shí)鐘和物理時(shí)鐘的大小，取最大的值戚啥。
記事件 j 發(fā)生時(shí)的物理時(shí)鐘值為 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)

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

圖一

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

第二版算法

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

初始化：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í)行的過(guò)程中许昨，本地時(shí)鐘的值通過(guò)NTP協(xié)議更新懂盐，HLC的值并不會(huì)修改本地時(shí)鐘的值。由于分離了物理時(shí)鐘和邏輯時(shí)鐘糕档，新的事件發(fā)生時(shí)莉恼，如果物理時(shí)鐘部分的值沒(méi)增長(zhǎng)，就只增加邏輯時(shí)鐘部分的值速那。如果本地的物理時(shí)鐘趕上了HLC的物理時(shí)鐘部分的值 l.j俐银，就可以重置邏輯時(shí)鐘部分的值 c.j，并把 l.j 更新為新的本地物理時(shí)鐘端仰。這樣就可以解決第一版算法中HLC無(wú)限增長(zhǎng)的問(wèn)題捶惜，也滿足了性質(zhì)3和性質(zhì)4的要求。具體數(shù)學(xué)證明過(guò)程參考論文荔烧。
對(duì)于任何一個(gè)事件 j吱七，pt.j <= l.j汽久，也即HLC的物理時(shí)鐘部分的值一定大于等于本地NTP的時(shí)鐘值。假設(shè)整個(gè)分布式系統(tǒng)中踊餐，NTP協(xié)議的時(shí)鐘誤差值為 ε景醇。新算法中，對(duì)于任何一個(gè)事件 j吝岭，| l.j - pt.j | <= ε三痰，也就是HLC物理部分的值和本地物理時(shí)鐘值的差距不會(huì)超過(guò) ε。根據(jù)前文計(jì)算機(jī)的時(shí)鐘（一）：NTP協(xié)議的介紹窜管，這個(gè)誤差值在局域網(wǎng)內(nèi)大概1毫秒內(nèi)散劫，廣域網(wǎng)可能達(dá)到100毫秒或更大。
使用新算法來(lái)分析第一版算法中的例子：

圖二

HLC的異常處理

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

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

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

圖三

圖四

HLC應(yīng)用

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

圖五

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

1. 如果 hlc.e + MaxOffset < hlc.g，即處于區(qū)間的右邊饥伊，那么e事件肯定發(fā)生在g事件之前象浑，不能讀取這個(gè)數(shù)據(jù)。
2. 如果 hlc.e < hlc.g <= hlc.e + MaxOffs撵渡，即處于區(qū)間之中融柬，由于物理時(shí)鐘的不確定性，不能分辨出e事件和g事件的先后關(guān)系趋距。這個(gè)時(shí)候需要重啟事務(wù)粒氧，獲取一個(gè)更大的hlc，相當(dāng)于等待這個(gè)不確定的時(shí)間過(guò)去节腐，推遲事務(wù)的執(zhí)行外盯。
3. 如果 hlc.g < hlc.e摘盆，那么g事件肯定發(fā)生在e之前，這時(shí)可以讀取這個(gè)數(shù)據(jù)饱苟。（對(duì)于這點(diǎn)我有點(diǎn)疑問(wèn)孩擂，由于不確定時(shí)間的存在，物理時(shí)間可能快箱熬，也可能慢类垦，這個(gè)區(qū)間應(yīng)該是[ hlc.e - MaxOffset, hlc.e + MaxOffset ]，為什么這里hlc.g < hlc.e就認(rèn)為g在e前面城须？）

總結(jié)

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

參考

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