由于在分布式系統(tǒng)中沒(méi)有絕對(duì)的全局時(shí)鐘趁耗，各個(gè)物理設(shè)備上的本地時(shí)鐘也不是準(zhǔn)確的枷踏，所以為了解決一些時(shí)序的問(wèn)題，形形色色的算法和優(yōu)化措施被提出來(lái)了肴敛。
晶振和時(shí)鐘偏移
在計(jì)算機(jī)中主要通過(guò)晶體的震蕩周期進(jìn)行計(jì)時(shí)艾君，晶體的震蕩周期決定了單機(jī)的時(shí)鐘分辨率采够。比如計(jì)算機(jī)中使用的是一個(gè)晶振12Mhz的石英，那么時(shí)鐘周期就是1/12us冰垄。計(jì)算機(jī)無(wú)法分辨更細(xì)的時(shí)間間隔了蹬癌，這對(duì)高精度要求的系統(tǒng)造成了巨大的挑戰(zhàn)。
另外，時(shí)鐘頻率也可能因?yàn)闇囟鹊韧獠恳蛩貙?dǎo)致時(shí)鐘偏移逝薪，普通的石英晶體的漂移率大約10e-6 s/s伴奥，也就是12天左右會(huì)有1s的偏差。這對(duì)微秒精度的系統(tǒng)同樣造成了困擾翼闽。比如GPS等需要精確地時(shí)間戳來(lái)定位的系統(tǒng)，時(shí)間的精度影響了定位的準(zhǔn)確性洲炊。
時(shí)間正確性
我們通過(guò)外部同步和內(nèi)部同步的方式來(lái)實(shí)現(xiàn)時(shí)鐘正確性感局。
- 外部同步: 設(shè)置同步范圍D>0, UTC時(shí)間源S，只要時(shí)鐘C與S在任意時(shí)間點(diǎn)上的歐氏距離小于D暂衡，那么就處于外部同步狀態(tài)询微。
- 內(nèi)部同步: 系統(tǒng)內(nèi)部時(shí)鐘在D范圍內(nèi)一致，也就是說(shuō)時(shí)鐘沒(méi)有過(guò)大的偏移狂巢。
時(shí)鐘正確性在不同場(chǎng)景下有不同的提法撑毛，一種提法是時(shí)鐘的漂移率始終在一個(gè)設(shè)定范圍內(nèi)。另一種較弱的提法是要求時(shí)鐘始終保證單調(diào)性唧领。比如編譯工具make會(huì)根據(jù)時(shí)間戳重新編譯文件藻雌，假如在設(shè)置一個(gè)文件的時(shí)間戳以后，把時(shí)鐘向后偏移了一段時(shí)間斩个，然后修改了文件胯杭，那么make將會(huì)錯(cuò)誤的不編譯這些文件。另一個(gè)例子是密碼學(xué)中使用時(shí)間戳防止重放攻擊受啥，如果時(shí)間向前偏移量超過(guò)了可接受閾值做个，那么就會(huì)很容易受到攻擊。
ntp同步服務(wù)
ntp(Network Time Protocol)滚局，網(wǎng)絡(luò)時(shí)間協(xié)議定義了時(shí)間服務(wù)的體系結(jié)構(gòu)以及在互聯(lián)網(wǎng)上發(fā)布時(shí)間信息的協(xié)議居暖。ntp的主要設(shè)計(jì)特色有:
- 提供一個(gè)服務(wù)，能夠讓跨互聯(lián)網(wǎng)用戶能夠跟UTC時(shí)間精確同步
- 提供一個(gè)能在漫長(zhǎng)的鏈接丟失中生存的服務(wù): 提供冗余的服務(wù)器并在服務(wù)器之間提供冗余的路徑
- 提供保護(hù)藤肢，防止對(duì)時(shí)間服務(wù)的干擾太闺。
ntp使用以下三種模式相互同步,組播、過(guò)程調(diào)用和對(duì)稱模式:
- 組播模式應(yīng)用于高速LAN上谤草，一臺(tái)或多臺(tái)服務(wù)器定期將時(shí)間廣播到LAN中的其他計(jì)算節(jié)點(diǎn)上
- 過(guò)程調(diào)用模式跟束，類似于Cristina過(guò)程:
進(jìn)程p估算到遠(yuǎn)程進(jìn)程q的延遲(比如多次使用ping獲得多個(gè)T_r，取最小值)丑孩，然后請(qǐng)求q獲得時(shí)間戳t冀宴，最后設(shè)置時(shí)間為t + T_r/2 -
對(duì)稱模式是獲得較高準(zhǔn)確精度的方法:
設(shè)服務(wù)器B時(shí)鐘是正確的時(shí)鐘，Ta1絕對(duì)時(shí)間是指服務(wù)器A本地時(shí)鐘到達(dá)Ta1是温学，正確的時(shí)間是多少略贮。這也是A需要同步的時(shí)間;
a. 服務(wù)器A在本地Ta1時(shí)間向B發(fā)送時(shí)間請(qǐng)求包
b. 服務(wù)器B在本地Tb1時(shí)間收到B發(fā)來(lái)的包，Tb1 = Ta1絕對(duì)時(shí)間 + T請(qǐng)求時(shí)延
c. 服務(wù)器B在本地Tb2=Tb1 + 1時(shí)間發(fā)送時(shí)間戳包給A
d. 服務(wù)器A在本地Ta2時(shí)間收到B回復(fù)的時(shí)間戳包，Ta2絕對(duì)時(shí)間 = Tb2 + T回復(fù)時(shí)延
那么A需要同步的時(shí)間 = Tb2 + T回復(fù)時(shí)延 = Tb2 + (Tb1 - Tb2 + Ta2 - Ta1) / 2
當(dāng)然這個(gè)算法也有個(gè)缺陷逃延，就是假設(shè)了包來(lái)回的時(shí)延相等览妖，在光纖這種半雙工物理介質(zhì)中，時(shí)延不一定相等揽祥，就會(huì)造成誤差讽膏。
邏輯時(shí)鐘與向量時(shí)鐘
邏輯時(shí)鐘是一種簡(jiǎn)單的相對(duì)計(jì)時(shí)方式，通常是一個(gè)單調(diào)增長(zhǎng)的軟件計(jì)數(shù)器拄丰。Lamport Timers利用邏輯時(shí)間維護(hù)不同進(jìn)程間事件發(fā)生的時(shí)序:
- LC1: 在進(jìn)程pi發(fā)出事件之前府树，L1+=1
- Li: Li+=1
- LC2: (a) 當(dāng)進(jìn)程pi收到消息m時(shí)，在m中附加值t=L1
(b)在接受(m, t)時(shí)料按，進(jìn)程pj 計(jì)算Lj: =max(Lj ,t)奄侠，然后再給receive(m)打上時(shí)間戳Lj+=1
Lamport時(shí)鐘可以很容易根據(jù)e->e'(同一序列中) => L(e) < L(e')，但是無(wú)法根據(jù)L(e) < L(e') 推出 e->e'载矿，
向量時(shí)鐘的提出垄潮，克服了lamport 時(shí)鐘的這個(gè)缺陷:
- VC1: 初始情況下，vi[j] = 0
- VC2: 給事件pi加時(shí)間戳之前闷盔，vi[j] += 1
- VC3: pi在他發(fā)送的每個(gè)消息中包括值t=Vi
- VC4: 當(dāng)pi接收到消息中的時(shí)間戳?xí)r弯洗，設(shè)置vi[j] = max(Vi[j], t[j]), j={0,1,..N}，這個(gè)過(guò)程稱為merge(合并)
向量時(shí)鐘就可以根據(jù)L(e) < L(e') => e->e'
