時(shí)間同步算法與Simple Ring-based election algorithm算法分析

2019-11-17 03:52:06

字體：大中小

供稿：網(wǎng)友

時(shí)間同步算法的應(yīng)用非常廣泛。

譬如在Unix系統(tǒng)里面，Make命令，只是用來(lái)編譯新修改過(guò)的代碼文件。Make命令使用運(yùn)行的客戶端的時(shí)鐘來(lái)決定哪個(gè)文件是被修改過(guò)的。但是，如果把代碼放到文件服務(wù)器上面，而運(yùn)行make命令的主機(jī)與文件服務(wù)器的時(shí)間不同的時(shí)候，make命令就有可能工作不正常。

譬如玩dota的時(shí)候，幾個(gè)客戶端需要一個(gè)同步過(guò)的時(shí)鐘來(lái)使每個(gè)人的畫面保持一致。、再譬如PC電腦同步服務(wù)器上面的時(shí)間可以做到很高的同步精度。

時(shí)間同步算法

時(shí)間同步算法，有以下幾個(gè)解決方案：

Cristian’s algorithm算法

Cristian's Algorithm算法的應(yīng)用背景，主要是在一個(gè)進(jìn)程P像一個(gè)服務(wù)器S請(qǐng)求時(shí)間：

1.       P發(fā)送一個(gè)請(qǐng)求包到S請(qǐng)求時(shí)間。

2.       S收到P的請(qǐng)求包以后，在包上面加上當(dāng)前S的時(shí)間，然后回發(fā)過(guò)去。

3.       P收到數(shù)據(jù)包之后，把當(dāng)前時(shí)間設(shè)置為T+RTT/2。

RTT表示一個(gè)Round Trip Time，即P從發(fā)送到接受到數(shù)據(jù)包的時(shí)間。該算法假設(shè)發(fā)送數(shù)據(jù)包和接受數(shù)據(jù)包在網(wǎng)絡(luò)上所用的時(shí)間是一樣的。而且也假設(shè)S在處理請(qǐng)求的時(shí)候時(shí)間可以忽略不計(jì)。基于以上假設(shè)，改算法可以改進(jìn)如下：

從P發(fā)送多個(gè)請(qǐng)求包到S，然后取RTT最小的做為RTT除以二加在此包包含的時(shí)間上。

算法精度分析：假設(shè)min為從S到P的最短時(shí)間，T為包含在上述定義的RTT中的時(shí)間。那么，P設(shè)置時(shí)間的范圍應(yīng)該是[T+min，T+RTT-min]。這樣時(shí)間的偏差范圍就在RTT-2min以內(nèi)。改進(jìn)后的算法精度應(yīng)該為RTT/2-min。



Berkeley algorithm算法

Berkeley算法的使用環(huán)境與Cristian算法有所不同。Cristian算法是用在一個(gè)客戶端向一個(gè)服務(wù)器請(qǐng)求正確時(shí)間的時(shí)候。而Berkeley算法是幾個(gè)客戶端之間同步時(shí)鐘的算法。具體算法如下：

1.       首先通過(guò)Change and Robert’s Algorithm來(lái)從一個(gè)環(huán)里面選擇一個(gè)節(jié)點(diǎn)做為Master。

2.       一個(gè)Master使用Cristian算法來(lái)請(qǐng)求各個(gè)節(jié)點(diǎn)的時(shí)間。

3.       Master通過(guò)記錄RTT的平均值，同時(shí)剔除偏差很大的RTT來(lái)評(píng)估出每個(gè)節(jié)點(diǎn)的時(shí)間偏差。

4.       Master發(fā)送每個(gè)節(jié)點(diǎn)的時(shí)間偏差到每個(gè)節(jié)點(diǎn)，讓節(jié)點(diǎn)自行校正。

客戶端接受到了時(shí)間以后，一般來(lái)說(shuō)不會(huì)把當(dāng)前的時(shí)間往回調(diào)整。因?yàn)檫@會(huì)導(dǎo)致一些程序莫名奇妙的錯(cuò)誤。因?yàn)樵诤芏嗨惴ㄖ校瑫r(shí)間不會(huì)往回調(diào)整是一個(gè)基本假設(shè)。譬如make命令。

解決的方案有一個(gè)：讓時(shí)鐘走慢點(diǎn)就可以了。花費(fèi)一些時(shí)間來(lái)調(diào)整到正確時(shí)間。

另外，還需討論一下Change and Robert’s Algorithm這個(gè)算法。這個(gè)算法和時(shí)間同步算法一樣，是玩dota的時(shí)候需要用到的。在dota初始化的時(shí)候，需要同步各個(gè)玩家的時(shí)鐘。在掉線了之后，就要通過(guò)特定的算法來(lái)找一個(gè)新的主機(jī)：

Change and Robert’s Algorithm

Change and Robert’s Algorithm算法假設(shè)每個(gè)PRocess都有一個(gè)UID，同時(shí)在一個(gè)Ring狀網(wǎng)絡(luò)中可以有個(gè)沒(méi)有方向的通訊信道。算法如下：

1.       首先ring中的每個(gè)節(jié)點(diǎn)把自個(gè)標(biāo)識(shí)為non-participant。

2.       當(dāng)一個(gè)process發(fā)現(xiàn)主機(jī)掉線了的時(shí)候，它首先把自個(gè)標(biāo)識(shí)成為participant，然后發(fā)送給鄰居一個(gè)包含了自個(gè)UID的一個(gè)選主機(jī)的數(shù)據(jù)包。

3.       當(dāng)數(shù)據(jù)包達(dá)到鄰居的時(shí)候，首先和自己的UID比較下，如果自己的UID比這個(gè)UID大，就把自己標(biāo)識(shí)成為participant，同時(shí)修改數(shù)據(jù)包里面的UID，并且也往順時(shí)針?lè)较虬l(fā)送這個(gè)數(shù)據(jù)。

4.       當(dāng)一個(gè)process接到一個(gè)數(shù)據(jù)包的時(shí)候發(fā)現(xiàn)這個(gè)數(shù)據(jù)包里面的UID和自己的UID一樣的時(shí)候，就開始這個(gè)算法的第二階段：

5.       這個(gè)process把自己標(biāo)識(shí)成為non-participant，同時(shí)發(fā)送已經(jīng)選擇好了主機(jī)的信息到鄰居，并且包含UID信息。

6.       如此循環(huán)，當(dāng)回到被選中成為主機(jī)的Process的時(shí)候，整個(gè)過(guò)程結(jié)束。

這是在分布式系統(tǒng)里面選擇一個(gè)主機(jī)的算法。當(dāng)然，在特定的環(huán)境下，可以把選擇的條件變化一下，譬如選擇網(wǎng)絡(luò)速度最快的或者是CPU最快的作為主機(jī)。同時(shí)，這個(gè)算法還可以避免多個(gè)Process同時(shí)發(fā)現(xiàn)主機(jī)掉線，幾個(gè)process同時(shí)尋求主機(jī)的情況。

這個(gè)算法的偽碼可以描述如下：

Start : M:= i:

       Send <i> to neighbor;

Upon receiving message <j>;

       If M<j then M:=j;

                       Send <j> to neighbor;

                Elseif M=j then leader;

                Endif;

該算法詳細(xì)的復(fù)雜度分析，數(shù)學(xué)模型和統(tǒng)計(jì)表可以參考這篇論文：

http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf

本文僅分析了Centrilized System里面的幾個(gè)時(shí)間同步算法，對(duì)于分布式系統(tǒng)里面的Network Time Protocal和Reference broadcast Synchronization算法并未做分析。以后有空研究研究NTP。

上一篇：正則表達(dá)式——極速入門

下一篇：使用lucene 3.0.0 索引和檢索中文文件