時間同步算法與Simple Ring-based election algorithm算法分析

2019-11-17 03:52:06

字體：大中小

來源：轉載

供稿：網友

時間同步算法的應用非常廣泛。

譬如在Unix系統里面，Make命令，只是用來編譯新修改過的代碼文件。Make命令使用運行的客戶端的時鐘來決定哪個文件是被修改過的。但是，如果把代碼放到文件服務器上面，而運行make命令的主機與文件服務器的時間不同的時候，make命令就有可能工作不正常。

譬如玩dota的時候，幾個客戶端需要一個同步過的時鐘來使每個人的畫面保持一致。、再譬如PC電腦同步服務器上面的時間可以做到很高的同步精度。

時間同步算法

時間同步算法，有以下幾個解決方案：

Cristian’s algorithm算法

Cristian's Algorithm算法的應用背景，主要是在一個進程P像一個服務器S請求時間：

1.       P發送一個請求包到S請求時間。

2.       S收到P的請求包以后，在包上面加上當前S的時間，然后回發過去。

3.       P收到數據包之后，把當前時間設置為T+RTT/2。

RTT表示一個Round Trip Time，即P從發送到接受到數據包的時間。該算法假設發送數據包和接受數據包在網絡上所用的時間是一樣的。而且也假設S在處理請求的時候時間可以忽略不計?；谝陨霞僭O，改算法可以改進如下：

從P發送多個請求包到S，然后取RTT最小的做為RTT除以二加在此包包含的時間上。

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



Berkeley algorithm算法

Berkeley算法的使用環境與Cristian算法有所不同。Cristian算法是用在一個客戶端向一個服務器請求正確時間的時候。而Berkeley算法是幾個客戶端之間同步時鐘的算法。具體算法如下：

1.       首先通過Change and Robert’s Algorithm來從一個環里面選擇一個節點做為Master。

2.       一個Master使用Cristian算法來請求各個節點的時間。

3.       Master通過記錄RTT的平均值，同時剔除偏差很大的RTT來評估出每個節點的時間偏差。

4.       Master發送每個節點的時間偏差到每個節點，讓節點自行校正。

客戶端接受到了時間以后，一般來說不會把當前的時間往回調整。因為這會導致一些程序莫名奇妙的錯誤。因為在很多算法中，時間不會往回調整是一個基本假設。譬如make命令。

解決的方案有一個：讓時鐘走慢點就可以了。花費一些時間來調整到正確時間。

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

Change and Robert’s Algorithm

Change and Robert’s Algorithm算法假設每個PRocess都有一個UID，同時在一個Ring狀網絡中可以有個沒有方向的通訊信道。算法如下：

1.       首先ring中的每個節點把自個標識為non-participant。

2.       當一個process發現主機掉線了的時候，它首先把自個標識成為participant，然后發送給鄰居一個包含了自個UID的一個選主機的數據包。

3.       當數據包達到鄰居的時候，首先和自己的UID比較下，如果自己的UID比這個UID大，就把自己標識成為participant，同時修改數據包里面的UID，并且也往順時針方向發送這個數據。

4.       當一個process接到一個數據包的時候發現這個數據包里面的UID和自己的UID一樣的時候，就開始這個算法的第二階段：

5.       這個process把自己標識成為non-participant，同時發送已經選擇好了主機的信息到鄰居，并且包含UID信息。

6.       如此循環，當回到被選中成為主機的Process的時候，整個過程結束。

這是在分布式系統里面選擇一個主機的算法。當然，在特定的環境下，可以把選擇的條件變化一下，譬如選擇網絡速度最快的或者是CPU最快的作為主機。同時，這個算法還可以避免多個Process同時發現主機掉線，幾個process同時尋求主機的情況。

這個算法的偽碼可以描述如下：

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;

該算法詳細的復雜度分析，數學模型和統計表可以參考這篇論文：

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

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

上一篇：正則表達式——極速入門

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