時間同步算法的應用非常廣泛。
譬如在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;
本文僅分析了Centrilized System裡面的幾個時間同步算法,對於分布式系統裡面的Network Time Protocal和Reference broadcast Synchronization算法並未做分析。以後有空研究研究NTP。