Ordering
現(xiàn)實(shí)生活中時間可以記錄事情發(fā)生的時刻、比較事情發(fā)生的先后順序昆禽。
分布式系統(tǒng)的一些場景也需要記錄和比較不同節(jié)點(diǎn)間事件發(fā)生的順序蝗蛙。
如數(shù)據(jù)寫入先后順序，事件發(fā)生的先后順序等等醉鳖。
關(guān)系
復(fù)習(xí)下離散數(shù)學(xué)中關(guān)系：
假設(shè)A是一個集合 {1,2,3,4} 捡硅；R是集合A上的關(guān)系，例如{<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,4>,<2,4>,<3,4>}
- 自反性：任取一個A中的元素x盗棵，如果都有<x,x>在R中壮韭，那么R是自反的北发。
- <1,1>,<2,2>,<3,3>,<4,4>
- 對稱性：任取一個A中的元素x,y，如果<x,y> 在關(guān)系R上,那么<y,x> 也在關(guān)系R上喷屋，那么R是對稱的琳拨。
- 反對稱性：任取一個A中的元素x,y(x!=y)，如果<x,y> 在關(guān)系R上,那么<y,x> 不在關(guān)系R上屯曹，那么R是反對稱的狱庇。
- 對于 <1,2>，有 <2,1> 不在R中恶耽；對于<2,4> 有<4,2>不在R中密任；對于<3,4> 有<4,3> 不在 R中，滿足偷俭。
- 傳遞性：任取一個A中的元素x,y,z浪讳，如果<x,y>,<y,z> 在關(guān)系R上，那么 <x,z> 也在關(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中所有<x,y>，都有關(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上的一個二元關(guān)系，若R滿足：
- 反對稱性：對任意x,y∈A蜡豹，若xRy麸粮，且yRx，則x=y镜廉；
- 傳遞性：對任意x, y,z∈A弄诲，若xRy，且yRz娇唯，則xRz
- 自反性：對任意x∈A齐遵，有xRx寂玲；
一個partitial ordering關(guān)系滿足的條件是自反的，反對稱的和可傳遞的梗摇，因此在partitial ordering中拓哟，可能有兩個元素之間是不相關(guān)的。
全序The Total Ordering
集合內(nèi)只有部分元素之間是可以比較的留美。
比如：比如復(fù)數(shù)集中并不是所有的數(shù)都可以比較大小彰檬，那么“大小”就是復(fù)數(shù)集的一個偏序關(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)系妆毕。
所以偏序中滿足完全性就是全序了慎玖。
一個total ordering關(guān)系滿足的條件是反對稱的，可傳遞的和完全性笛粘，因此在total ordering中趁怔，兩個元素一定是有關(guān)系的，要么是a<>b或b<>a薪前。
happens before
在分布式系統(tǒng)中润努，一個進(jìn)程包含一系列的事件，對于同一進(jìn)程內(nèi)的事件示括，如果a happens before b铺浇，那么a發(fā)生在b之前。并且垛膝，假定收或發(fā)消息都是一個事件鳍侣。
happens before的定義如下(用->表示)
- 如果a和b在同一進(jìn)程中，并且a發(fā)生在b之前吼拥，那么a->b
- 如果a是一個進(jìn)程發(fā)消息的事件倚聚，b是另一個進(jìn)程接收這條消息的事件，則a->b
- 如果a->b且b->c扔罪，那么a->c。
- 如果同時不滿足a->b桶雀，且b->a矿酵，那么說a和b是并發(fā)的concurrent
[圖來自Time, Clocks, and the Ordering of Events in a Distributed System]
以一個例子來說明happens before關(guān)系唬复，如上圖，垂直線上代表一個進(jìn)程全肮，從下往上敞咧，時間依次增加，水平的距離代表空間的隔離辜腺。原點(diǎn)代表一個事件休建，而曲線代表一條消息。
從圖中很容易地看出评疗，如果一個事件a测砂，能通過進(jìn)程的線和消息線，到達(dá)b百匆，那么a->b砌些。
在圖中，p3和q4是并行的事件加匈，因?yàn)榇媪В挥械搅藀4才能確定q4的發(fā)生，而q3也只能確定p1發(fā)生雕拼。
clock時鐘
物理時鐘
晶振和時鐘偏移
計算機(jī)有固定頻率晶體的震蕩次數(shù)纵东，晶體的振蕩周期決定了單機(jī)的時鐘精度。
時鐘頻率也可能因?yàn)闇囟鹊韧獠恳蛩貙?dǎo)致時鐘偏移啥寇，普通的石英晶體的漂移大約
原子鐘的漂移約為
所以原子鐘精度遠(yuǎn)遠(yuǎn)高于石英晶體偎球。
分布式下帶來的問題
不同機(jī)器上的物理時鐘難以同步，導(dǎo)致無法區(qū)分在分布式系統(tǒng)中多個節(jié)點(diǎn)的事件時序示姿。即使設(shè)置了 NTP 時間同步節(jié)點(diǎn)間也存在毫秒級別的偏差甜橱，因而分布式系統(tǒng)需要有另外的方法記錄事件順序關(guān)系。
1978年Lamport在《Time, Clocks and the Ordering of Events in a Distributed System》中提出了邏輯時鐘的概念栈戳，來解決分布式系統(tǒng)中區(qū)分事件發(fā)生的時序問題岂傲。
邏輯時鐘Logical clocks
邏輯時鐘指的是分布式系統(tǒng)中用于區(qū)分事件的發(fā)生順序的時間機(jī)制。 從某種意義上講子檀，現(xiàn)實(shí)世界中的物理時間其實(shí)是邏輯時鐘的特例镊掖。
Logical Clock解決的問題是找到一種方法，給分布式系統(tǒng)中所有時間定一個序褂痰，這個序能夠正確地排列出具有因果關(guān)系的事件（注意亩进，是不能保證并發(fā)事件的真實(shí)順序的），使得分布式系統(tǒng)在邏輯上不會發(fā)生因果倒置的錯誤缩歪。因果一致性
Lamport timestamps
論文
Time, Clocks, and the Ordering of Events in a Distributed System
Lamport timestamps
Leslie Lamport 在1978年提出邏輯時鐘的概念归薛，并描述了一種邏輯時鐘的表示方法，這個方法被稱為Lamport時間戳(Lamport timestamps)。
分布式系統(tǒng)中按是否存在節(jié)點(diǎn)交互可分為三類事件:
- 發(fā)生在節(jié)點(diǎn)內(nèi)部
- 發(fā)送事件
- 接收事件
時鐘的定義如下
- 對于一個進(jìn)程i主籍，Ci(a)表示進(jìn)程i中事件a的發(fā)生時間
- 對于整個系統(tǒng)來講习贫，對于任意的事件b，其發(fā)生時間為C(b)千元，當(dāng)b為進(jìn)程j的事件時苫昌，則C(b) = Cj(b)
為了使得事件按照正確的排序，需要使得如果事件a發(fā)生在事件b之前幸海，那么a發(fā)生的時間要小于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)中瞻凤，需要滿足以下原則
- 對于每個進(jìn)程憨攒，相鄰的事件的時鐘要增加1
- (a) 如果事件a是進(jìn)程i發(fā)送消息m的事件，發(fā)送時帶時間戳Tm = Ci(a)阀参，(b)事件b是進(jìn)程j接受消息m的事件肝集，那么事件b的取值為max(進(jìn)程b的當(dāng)前時鐘，Tm+1)
假設(shè)有事件a蛛壳、b杏瞻，C(a)、C(b)分別表示事件a衙荐、b對應(yīng)的Lamport時間戳捞挥，如果a->b,則C(a) < C(b)，a發(fā)生在b之前(happened before)忧吟。
所以Lamport timestamps原理如下：
- 每個事件對應(yīng)一個Lamport時間戳砌函，初始值為0
- 如果事件在節(jié)點(diǎn)內(nèi)發(fā)生，時間戳加1
- 如果事件屬于發(fā)送事件溜族，時間戳加1并在消息中帶上該時間戳
- 如果事件屬于接收事件讹俊，時間戳 = Max(本地時間戳，消息中的時間戳) + 1
通過該定義煌抒，事件集中Lamport時間戳不等的事件可進(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兩個事件與B4是并行關(guān)系蛋褥，根據(jù)Lamport timestamps的定義临燃，將他們判定為與B4具前后關(guān)系。（所以Lamport timestamps并不能嚴(yán)格的表示并行關(guān)系）
Lamport timestamps與偏序關(guān)系
Lamport timestamps只保證因果關(guān)系（偏序）的正確性膜廊，不保證絕對時序的正確性淫茵。
Lamport logical clock
由于Lamport timestamps只能得到偏序關(guān)系，如果要得到全序關(guān)系铆铆，就需要給Ci(a) = Cj(b)的事件定一個先后順序丹喻。
total order的事件關(guān)系=>定義如下：
如果事件a發(fā)生在進(jìn)程Pi，事件b發(fā)生在進(jìn)程Pj谅猾，那么當(dāng)滿足下列兩者條件之一時骑冗，a=>b
- Ci(a) < Cj(b)
- Ci(a) = Cj(b) 且 Pi < Pj
根據(jù)以上條件，對于任意的兩個事件巧涧，都能判斷出它們之間的關(guān)系遥倦，因此是total ordering的。
當(dāng)Lamport timestamp一致時缩筛，通過義Pi < Pj來定義順序瞎抛，確保分布式場景下各個進(jìn)程間發(fā)生的事件的全序定義艺演。至于Pj < Pj：可采用不同的方式桐臊，Lamport Logical Clock提到的 arbitrary total ordering断凶。
vector clock
Lamport timestamp得到的是全序關(guān)系，但無法嚴(yán)格表示對于沒有因果關(guān)系肿男、存在同時發(fā)生關(guān)系(concurrent)的事件却嗡。
Vector clock是在Lamport timestamp基礎(chǔ)上改進(jìn)的一種邏輯時鐘方法，它構(gòu)不但記錄本節(jié)點(diǎn)的Lamport timestamp冠王，同時也記錄了其他節(jié)點(diǎn)的Lamport timestamp舌镶。
原理如下:
- 本地vector clock的clock數(shù)組中每一個邏輯時間(clock)對應(yīng)一個進(jìn)程的clock
- 初始化vector clock中每一個邏輯時間為0；
- 每一次處理內(nèi)完內(nèi)部事件哟楷，將vector clock中自己的邏輯時間戳+1否灾；
- 每發(fā)送一個消息的時候，將vector clock中自己的邏輯時間+1惩阶，且將其和消息一起發(fā)送出去
- 每接收到一個消息的時候扣汪，需要將本地的vector clock中自己的邏輯時間戳+1崭别，且將自己vector clock中的邏輯時間和消息中攜帶的進(jìn)行比較恐锣，取最大的更新本地vector clock中的邏輯時間舞痰。
圖來源于wikipedia
vector clock判定并發(fā)關(guān)系：
- 事件i响牛、事件j對應(yīng)的vector clock中，每一個進(jìn)程Pk的邏輯時間戳都滿足Vi[Pk]<Vj[Pk]時论衍，我們稱事件i happen before事件j；
- vector clock中炬丸，存在P1稠炬、P2，使得Vi[P1]<Vj[P1]暮屡，Vi[P2]>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)之間同步時鐘结耀，不需要在所有節(jié)點(diǎn)上維護(hù)一段數(shù)據(jù)的版本數(shù)；
- 缺點(diǎn)是時鐘值的大小隨著節(jié)點(diǎn)增多和時間不斷增長
version vector
分布式系統(tǒng)多個副本被同時更新時香伴，會導(dǎo)致副本之間數(shù)據(jù)的不一致即纲。version vector用于來發(fā)現(xiàn)這些不一致的沖突。
version vector只能發(fā)現(xiàn)沖突蜂厅，無法解決沖突膊畴；當(dāng)然也可以通過再添加一個維度信息timestamp唇跨，發(fā)生沖突時進(jìn)行比較，但是又回到了物理時鐘不同步的問題改橘。
下圖展示了數(shù)據(jù)由不同副本處理后導(dǎo)致的不同版本沖突玉控。
D5時發(fā)現(xiàn)了數(shù)據(jù)的沖突，這時會將不同版本數(shù)據(jù)都存儲下來碌识，一般由客戶端來解決沖突丸冕。
version vector與vector clock的差異
- vector clocks 使用 receive和send 方法來更新clock,而version vector使用sync方法來更新薛窥。
- vector clocks是給事件定序的诅迷，確定事件的因果關(guān)系；而version vector是確定同一個數(shù)據(jù)不同版本的因果關(guān)系趟畏。
分布式與時鐘
分布式系統(tǒng)中滩租，每個節(jié)點(diǎn)的物理時鐘是不同步的，都有一定的差異猎莲。
這樣就帶來了一些分布式系統(tǒng)實(shí)現(xiàn)的難題著洼，如基于MVCC實(shí)現(xiàn)的事務(wù)，基于MVCC實(shí)現(xiàn)事務(wù)會要求版本之間能判斷先后順序豹悬，只有確定先后才知道應(yīng)該用哪一個版本的數(shù)據(jù)液荸，確定先后順序就涉及到時間娇钱，而不同機(jī)器之間的本地時鐘是無法保證一致的，所以這就需要確保時鐘的同步。
而通常解決方案有兩種：
- 中心化的時鐘方案细疚，如Timestamp oracle(TSO)
- 無中心化的時鐘方案川梅，如google True Time，Hybrid Logic Time
Timestamp oracle
如果我們整個系統(tǒng)不復(fù)雜吧彪，而且沒有跨全球的需求姨裸，這時用一臺中心授時服務(wù)就可以了怨酝。
如TiDB使用的就是TSO方案，tipb作為一個TSO集群赡艰，來提供授時服務(wù)慷垮。
使用TSO的好處在于因?yàn)橹挥幸粋€中心授時，所以我們一定能確定所有時間的時間汤纸，但TSO需要關(guān)注幾個問題：
- 網(wǎng)絡(luò)延時：因?yàn)樗械氖录夹枰獜腡SO獲取時間惯驼，所以TSO只適合小集群部署祟牲，不能是那種全球級別的數(shù)據(jù)庫
- 性能：每個事件都需要從TSO獲取時間，所以TSO需要非常高的性能
- 容錯：TSO是一個單點(diǎn)议惰，需要考慮節(jié)點(diǎn)的failover
True Time
由于節(jié)點(diǎn)間NTP是有偏差的乡恕，且可能出現(xiàn)時間回退的情況傲宜，所以NTP無法準(zhǔn)確的判定事件的全序關(guān)系。在Google Spanner里面辆憔，通過引入True Time來解決了分布式時間問題报嵌。
True Time實(shí)現(xiàn)
Spanner通過使用GPS + 原子鐘atomic clock來對集群的機(jī)器時間進(jìn)行校對锚国，保證了集群機(jī)器的時間戳差距不會超過一個上限值(ε)。
用兩種技術(shù)來處理绘沉，是因?yàn)閷?dǎo)致這兩種技術(shù)的失敗的原因是不同的梆砸。
- GPS會有一個天線园欣，電波干擾會導(dǎo)致其失靈。原子鐘很穩(wěn)定日矫。
- 當(dāng)GPS失靈的時候哪轿，原子鐘仍然能保證在相當(dāng)長的時間內(nèi)，不會出現(xiàn)偏差杨耙。
API
- TT.now() : 返回一個當(dāng)前時間飘痛，其位于范圍區(qū)間[earliest,latest]
- TT.after(t) : 當(dāng)前時間是否在t之后
- TT.before(t) : 當(dāng)前時間是否在t之前
雖然spanner引入了TrueTime可以得到全球范圍的時序一致性宣脉，但由于TrueTime返回的時間仍然有一定的偏差，如果要給兩個事件定序竹祷，就需要等待2個偏差的時間間隔塑陵，來確保其先后順序蜡励。
- 事件a：[Tai, Taj], Taj-Tai=ε
- 事件b：[Tbi, Tbj], Tbj-Tbi=ε
- 所以要確定b>a, 那么就要確保Tbi > Taj, 就需要在事件b進(jìn)行等待巍虫，以確保：
事件b時間 - 事件a時間 > 2ε
Hybrid logical clock
HLC
Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases
TrueTime 需要硬件的支持鳍刷，所以有一定的成本输瓜，而HLC無需硬件支持也能解決分布式下時間問題。
HLC同時使用了物理時鐘和邏輯時鐘（physical clock + logical clock）搔啊，能夠保證單點(diǎn)的時間發(fā)生器是單調(diào)遞增的北戏，同時能夠盡量控制不同節(jié)點(diǎn)之間的時鐘偏差在規(guī)定的偏差范圍內(nèi)嗜愈。
判斷兩個事件的先后順序：先判斷物理時間莽龟，再判斷邏輯時間毯盈。
HLC的算法
l.j維護(hù)的是節(jié)點(diǎn)j當(dāng)前已知的最大的物理時間(wall time)病袄，c.j則是當(dāng)前的邏輯時間益缠。
// 在節(jié)點(diǎn)j上面：初始化: l.j = 0，c.j = 0捺信。
initially l.j :=0; c.j := 0
// 本地事件或者發(fā)送消息時迄靠，
// 如果本地時鐘pt大于當(dāng)前的混合邏輯時鐘的l喇辽，
// 則將l更新成本地時鐘菩咨，將c清零。
// 否則特占，l保持不變云茸，將c加1标捺。
Send or local event
{
l'.j := l.j;
l.j := max(l'.j, pt.j); // 本地物理時間pt
if (l.j = l'.j) then
c.j := c.j+1
else
c.j := 0;
Timestamp with l.j, c.j
}
// 收到消息時
// l在 當(dāng)前的邏輯時鐘的l亡容、機(jī)器的本地時鐘pt、收到消息里面帶的l茂缚，三者中取最大的。
// 如果l部分是更新為本地時鐘了帖汞，則將c清零翩蘸。否則淮逊，c取較大的那個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時間有如下特性：
- 事件e發(fā)生在事件f之前，那么事件e的HLC時間一定小于事件f的HLC時間：(l.e, c.e) < (l.f, c.f)
- 本地WallTime大于等于本地物理時間(l.e ≥ pt.e)：HLC時間總是不斷遞增舶治，不會隨著物理時間發(fā)生回退霉猛。
- 對事件e珠闰，l.e是事件e能感知的到的最大物理時間值：如果l.e > pt.e伏嗜，那么一定存在著一個發(fā)生在e之前的事件g，有pt.g=l.e裸影。簡單來說是如果出現(xiàn)l.e > pt.e肯定是因?yàn)橛幸粋€HLC時間更大的的節(jié)點(diǎn)把當(dāng)前節(jié)點(diǎn)的HLC時間往后推了轩猩。
- WallTime和物理時鐘的偏差是有界的(ε ≥ |pt.e - l.e| )：因?yàn)楣?jié)點(diǎn)之間通過NTP服務(wù)校時羞迷，那么節(jié)點(diǎn)之間的物理時鐘偏差一定小于某個值ε衔瓮。那么對于任一事件b和e抖甘，如果b hb e，那么事件b的物理時間pt.b一定滿足pt.e + ε ≥ pt.b偷办。結(jié)合特性3存在一個事件g滿足澄港，l.e = pt.g回梧。那么 pt.e + ε ≥ l.e=pt.g > pt.e。
開源實(shí)現(xiàn)
CockroachDB采用基于NTP時鐘同步的HLC去中心化方案湖苞。
時鐘同步
所有節(jié)點(diǎn)間的RPC消息都會把時間戳帶入到消息中财骨，接收到消息的節(jié)點(diǎn)會通過消息中的時間戳更新自己的時間, 從而達(dá)到節(jié)點(diǎn)間時間同步的效果隆箩。
代碼分析
參考：https://github.com/cockroachdb/cockroach/blob/v1.1.3/pkg/util/hlc/hlc.go
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：本地已知物理時鐘
- Logical：邏輯時鐘
- Timestamp：HLC摘仅，單調(diào)遞增
獲取物理時鐘
// 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
// 檢查時鐘是否回退
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時鐘
// 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)前物理時鐘小于WallTime娃属，則將邏輯時鐘+1
- 如果當(dāng)前物理時鐘大于WallTime矾端，則更新WallTime為當(dāng)前物理時鐘秩铆，且將邏輯時鐘設(shè)置為0
節(jié)點(diǎn)時鐘同步
節(jié)點(diǎn)之間通過在RPC請求中攜帶HLC時間來進(jìn)行時鐘同步灯变。
// 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()
// 如果本地物理時間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是否大于時鐘偏差凡壤；
// 本地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
}
