時間同步演算法的應用非常廣泛。
譬如在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在處理請求的時候時間可以忽略。基於以上假設,改演算法可以改進如下:
從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。