邏輯時鐘算法

邏輯時鐘算法學(xué)號：101425摘要：時鐘同步是分布式系統(tǒng)的重要概念。時鐘系統(tǒng)的工作穩(wěn)定與否在很大程度上決定了分布式系統(tǒng)的運(yùn)行穩(wěn)定程度。時鐘同步在分布式系統(tǒng)的備份和錯誤恢復(fù)機(jī)制中應(yīng)用廣泛。本文分別物理時鐘和介紹邏輯時鐘的概念，并進(jìn)一步介紹幾種邏輯時鐘同步模型、時鐘因果排序及其應(yīng)用。關(guān)鍵字：邏輯時鐘；同步；一致割物理時鐘同步當(dāng)兩個設(shè)備一起工作并對時間有精確要求的時候，就需要在它們之間進(jìn)行同步。同步是基于在兩個設(shè)備之間規(guī)定一個共同的時間參考。如果這兩個設(shè)備沒有進(jìn)行同步，無論它們開始的時間多么一致，也會由于兩臺設(shè)備機(jī)械結(jié)構(gòu)的差異而產(chǎn)生時間漂移。計算機(jī)系統(tǒng)時鐘的基本元素是石英振蕩器，若干次振蕩形成一次時鐘中斷，若干次（H）中斷構(gòu)成時鐘值的一次遞增。由于時鐘芯片存在誤差，如果H=60，則每小時時鐘應(yīng)當(dāng)振蕩60X3600=216000次，但實際的振蕩次數(shù)大約在215998—216002之間。分布式系統(tǒng)中各計算機(jī)的特點(diǎn)如下：1） 、相關(guān)信息散布在多個場地上；2） 、每個進(jìn)程只能基于本地信息做決定；3） 、應(yīng)避免因單點(diǎn)故障造成整個系統(tǒng)的失?。?） 、不存在公共時鐘或精確的全局時間。當(dāng)每個機(jī)器有自己的時鐘，一個發(fā)生于另一個事件之后的事件可能被標(biāo)記上較早的時間。如圖1所示：進(jìn)疔編譯的計算機(jī)21442145 21462147根據(jù)水地対

鐘的時間創(chuàng)lEDUtputQ2143 2144 2145根據(jù)本地時

鐘的時間創(chuàng)iBoutput.c進(jìn)疔編譯的計算機(jī)21442145 21462147根據(jù)水地対

鐘的時間創(chuàng)lEDUtputQ2143 2144 2145根據(jù)本地時

鐘的時間創(chuàng)iBoutput.c圖1、異步系統(tǒng)的問題為了實現(xiàn)分布系統(tǒng)的時間同步，有幾種可行算法如下:1?1?Cristian算法:有一個時間服務(wù)器，提供標(biāo)準(zhǔn)時鐘，其它系統(tǒng)通過詢問與它同步。誤差周期內(nèi)，每個機(jī)器向服務(wù)器發(fā)出校時請求，服務(wù)器用進(jìn)行響應(yīng)，各機(jī)器根據(jù)響應(yīng)值重置自己的時鐘。這種算法有兩個不足之處。由于時鐘是不可回卷的，對于當(dāng)前時鐘值已經(jīng)大于服務(wù)器時間的機(jī)器必須動態(tài)調(diào)整自己時鐘的H值，減慢時鐘推進(jìn)的速率，逐漸地消化與標(biāo)準(zhǔn)時鐘之間的差距。另一個不足，由于請求與響應(yīng)的傳輸與處理會產(chǎn)生延遲，進(jìn)而影響時鐘的精度。因此要求詢問者要統(tǒng)計它與服務(wù)器之間的RTT,并利用它對得到的時間響應(yīng)值進(jìn)行修正。1.2.Berkeley算法：時間服務(wù)器沒有標(biāo)準(zhǔn)時鐘，它通過定期地詢問各個機(jī)器的當(dāng)前時間并從中求出平均值作為當(dāng)前的標(biāo)準(zhǔn)時間，然后再廣播給各個機(jī)器。當(dāng)前時鐘慢于新標(biāo)準(zhǔn)時間的機(jī)器重置自己的時鐘；當(dāng)前時鐘快于新標(biāo)準(zhǔn)時間的機(jī)器要調(diào)整自己的H值，以消化這個時間誤差。時間服務(wù)器的時鐘由系統(tǒng)管理員手工校正。1?3?Averaging算法：定義一個固定的同步間隔R，每經(jīng)過R時刻，所有的機(jī)器廣播自己的當(dāng)前時鐘。在經(jīng)過規(guī)定的接收間隔S之后，所有的機(jī)器根據(jù)接收到的時鐘值計算自己的當(dāng)前時鐘值。從上面幾種算法可以看到，物理時鐘同步的問題主要有兩個：1） 、是時間決不能倒退；2） 、二是不得不考慮傳輸延時。由于這兩個因素的存在，分布式系統(tǒng)的物理時間同步總是會出現(xiàn)誤差。邏輯時鐘Lamport提出了一種邏輯時鐘的概念可以比較好的解決分布式系統(tǒng)中的時間問題。邏輯時鐘的意義是在各進(jìn)程不能物理同步的情況下，確定各事件的先于發(fā)生或并發(fā)關(guān)系。2?1■邏輯時鐘概念：邏輯時鐘是（松耦合）分布式系統(tǒng)的特性，要求的是系統(tǒng)節(jié)點(diǎn)進(jìn)程之間的相對一致性。只有相關(guān)的進(jìn)程才需要有邏輯時鐘同步，同步的目的是維持事件的順序性，除時間的基本特性外，與物理時鐘之間沒有通用意義上的明確的關(guān)系。

邏輯時鐘算法的可行性基于以下幾點(diǎn)：1） 、如果兩個進(jìn)程之間不存在相互作用，它們的同步?jīng)]有意義；2） 、時鐘同步不需要絕對同步，不需要所有進(jìn)程在時間上完全一致，而是它們在事件的發(fā)生順序要完全一致；3） 、只關(guān)心事件的發(fā)生順序，而不關(guān)心是否與物理時間接近。邏輯時鐘通常用時標(biāo)（timestamp）表示，稱為Lamport時標(biāo)，它沒有具有物理意義的單位的概念，一般情況下以正整數(shù)標(biāo)識。時標(biāo)只能通過節(jié)點(diǎn)之間進(jìn)行消息交換完成，時標(biāo)間完全沒有物理時鐘方面的要求。事件是進(jìn)程中相對獨(dú)立的一段程序（代碼，語句序列）的一次運(yùn)行，具有不可分割性和相對獨(dú)立的語義。并發(fā)與同步分析的基本單位（不可分割）。事件之間不存在包含關(guān)系。同步點(diǎn)：含有發(fā)送或接收動作的事件。事件間的關(guān)系：一個沒有死鎖的特定系統(tǒng)，在確定了并發(fā)進(jìn)程和各進(jìn)程的事件后，任何2個事件間要么是“先于發(fā)生（?）”關(guān)系，要么是“并發(fā)（II）”關(guān)系。具有并發(fā)關(guān)系的事件可以并發(fā)完成，也可以先后完成，沒有順序要求，具有發(fā)生在先關(guān)系的事件必須按該關(guān)系所規(guī)定順序先后完成。發(fā)生在先關(guān)系的定義為：1） 、如果a和b是同一個進(jìn)程中的事件且a在b之前被執(zhí)行，則a-b；2） 、如果a是某個進(jìn)程發(fā)送消息的事件，b是另一個進(jìn)程接收該消息的事件，則a—b；3） 、如果a—b且b—c，則a—c；4） 、a—a對于任何事件a都不成立。如果事件a和b之間不存在發(fā)生在先關(guān)系，則它們是并發(fā)的。事件發(fā)生在先關(guān)系要求：1） 、單個進(jìn)程執(zhí)行中所有的事件是全（偏）序的；2） 、相對的要求，可以通過調(diào)節(jié)事件的分割來滿足3） 、當(dāng)消息接收方發(fā)現(xiàn)自己的（邏輯）時鐘小于收到的消息的時標(biāo)時，要將自己的時鐘調(diào)整到比收到的時標(biāo)至少大1的值，以維持偏序關(guān)系的成立。一個先與于生的示例如下：pOP1p2圖2、先于發(fā)生示例在這個圖中，可以找出的先于發(fā)生關(guān)系序列有:

a—b,c-a—d,g-—d—e—f,g—h—i—e,f—ia?e,cfi,…并行關(guān)系有hIIe,hIIb,bIIe等。22標(biāo)量邏輯時鐘沒有一個直接的全局的邏輯時鐘，但每個進(jìn)程Pi維護(hù)一個當(dāng)前邏輯時鐘LCi,它是一個非減的整數(shù)序列且初始化為init($0)；進(jìn)程中的每個事件均有一個邏輯時鐘，其數(shù)值等于發(fā)生時刻所屬進(jìn)程的邏輯時鐘的取值；Pi發(fā)出的每個消息m都帶有本地邏輯時鐘，可表為(m,LCi,i)；?通過這些邏輯時鐘和消息，可以維護(hù)事件間的先于發(fā)生關(guān)系。附加條件：兩個事件不可以同時發(fā)生。LCi的更新原則為“、在發(fā)生一個(外部發(fā)送或內(nèi)部)事件之前更新LCi=LCi+d；、當(dāng)收到一個帶時戳的消息(m,LCj,j)時，Pi執(zhí)行更新LCi=max(LCi,LCj)+d(d>0)。在圖2中，用標(biāo)量時鐘模型可以得到各事件的邏輯時鐘：pOplp2圖3、標(biāo)量邏輯時鐘標(biāo)量邏輯時鐘的缺點(diǎn)是，afb可以得到LC(a)vLC(b),但LC(a)<LC(b)卻不一定能得出a-b。上圖，b、g兩個事件不存在先于發(fā)生關(guān)系。而且標(biāo)量邏輯時鐘并不能確定系統(tǒng)里的并發(fā)關(guān)系。2?3■向量時鐘對標(biāo)量邏輯時鐘算法的改進(jìn)是向量時鐘算法。在一個由n個并發(fā)進(jìn)程構(gòu)成的系統(tǒng)中，每個事件的邏輯時鐘均由一個n維向量(n元組)構(gòu)成，其中第i維(分量)對應(yīng)于第i個進(jìn)程的邏輯時鐘Vi。第i個進(jìn)程在事件發(fā)生時，繼承上一事件的邏輯時鐘并將自身所對應(yīng)的分量Vi增加一個步長，任何進(jìn)程Pi在發(fā)出任何信息時都要將自己當(dāng)前的邏輯時鐘分

量Vi起發(fā)送出去，如果是接收事件，且發(fā)送方為j則比較自己繼承的Vj和收到的邏輯時鐘，并取其中較大者為自己的Vj。這樣，每次消息都能使接收方更新對系統(tǒng)每個進(jìn)程的時鐘認(rèn)識。在沒有死鎖的向量時鐘系統(tǒng)中，設(shè)：-i進(jìn)程中a事件的向量時鐘為(…ai?aj…)-j進(jìn)程中b事件的向量時鐘為(?bi?bj…)-若滿足aiWbi且ajWbj，則a~b,否則allb并發(fā)關(guān)系和先于發(fā)生關(guān)系僅反應(yīng)2個事件之間的關(guān)系，只有發(fā)生在先關(guān)系具有傳遞性，并發(fā)不具該特性。如果有a-b和c-b,不能判斷a和c之間的關(guān)系。pOplp2(1;OpOplp2(1;O5OJ\(2AO)c.d(0丄0) (l,2s0).(UJ)他4,1)(0,0.1)pL］卩口2)?*i(1A3)圖4、向量時鐘仍然以此系統(tǒng)為例，圖4為向量時鐘算法執(zhí)行的結(jié)果。顯然，b、g為并發(fā)關(guān)系。對于給定的時空視圖其向量時鐘的生成算法可以發(fā)現(xiàn)系統(tǒng)是否存在因等待接收消息而引起的死鎖，具體方法是：、接收a事件的向量時鐘為(?ai )，a屬i進(jìn)程，j為對應(yīng)的發(fā)送事件b所屬進(jìn)程、j進(jìn)程中b事件的向量時鐘為(?bi……)、若滿足aivbi，則存在一個因等待接收消息存在的死鎖。一致割在這一部分，介紹一個利用先于發(fā)生關(guān)系來理解分布式系統(tǒng)的例子：一致割。一致割是指處理器可以并發(fā)保留的狀態(tài)，在一個分布式系統(tǒng)中，基本上沒有可以記錄系統(tǒng)狀態(tài)瞬時快照的觀察者?？墒?，這樣一種能力在解決譬如系統(tǒng)崩潰后的恢復(fù)、檢測系統(tǒng)中是否存在死鎖及檢測計算是否已經(jīng)終止時是需要的。可以取代的方法是系統(tǒng)自身通過協(xié)作來獲取近似的瞬時信息快照。分布式系統(tǒng)里的一個割是一個n元的向量Vk,k，…k＞。使得處理器Pi的0 1 n1狀態(tài)是指第k個事件之后的狀態(tài)。

對于任意的i和j如果Pi上第k個計算事件不在Pj上第k個事件之前發(fā)i1 j生，那么這個向量就是一致