邏輯時鐘算法

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

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

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

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

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

邏輯時鐘算法的可行性基于以下幾點：1） 、如果兩個進程之間不存在相互作用，它們的同步?jīng)]有意義；2） 、時鐘同步不需要絕對同步，不需要所有進程在時間上完全一致，而是它們在事件的發(fā)生順序要完全一致；3） 、只關(guān)心事件的發(fā)生順序，而不關(guān)心是否與物理時間接近。邏輯時鐘通常用時標（timestamp）表示，稱為Lamport時標，它沒有具有物理意義的單位的概念，一般情況下以正整數(shù)標識。時標只能通過節(jié)點之間進行消息交換完成，時標間完全沒有物理時鐘方面的要求。事件是進程中相對獨立的一段程序（代碼，語句序列）的一次運行，具有不可分割性和相對獨立的語義。并發(fā)與同步分析的基本單位（不可分割）。事件之間不存在包含關(guān)系。同步點：含有發(fā)送或接收動作的事件。事件間的關(guān)系：一個沒有死鎖的特定系統(tǒng)，在確定了并發(fā)進程和各進程的事件后，任何2個事件間要么是“先于發(fā)生（?）”關(guān)系，要么是“并發(fā)（II）”關(guān)系。具有并發(fā)關(guān)系的事件可以并發(fā)完成，也可以先后完成，沒有順序要求，具有發(fā)生在先關(guān)系的事件必須按該關(guān)系所規(guī)定順序先后完成。發(fā)生在先關(guān)系的定義為：1） 、如果a和b是同一個進程中的事件且a在b之前被執(zhí)行，則a-b；2） 、如果a是某個進程發(fā)送消息的事件，b是另一個進程接收該消息的事件，則a—b；3） 、如果a—b且b—c，則a—c；4） 、a—a對于任何事件a都不成立。如果事件a和b之間不存在發(fā)生在先關(guān)系，則它們是并發(fā)的。事件發(fā)生在先關(guān)系要求：1） 、單個進程執(zhí)行中所有的事件是全（偏）序的；2） 、相對的要求，可以通過調(diào)節(jié)事件的分割來滿足3） 、當消息接收方發(fā)現(xiàn)自己的（邏輯）時鐘小于收到的消息的時標時，要將自己的時鐘調(dià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標量邏輯時鐘沒有一個直接的全局的邏輯時鐘，但每個進程Pi維護一個當前邏輯時鐘LCi,它是一個非減的整數(shù)序列且初始化為init($0)；進程中的每個事件均有一個邏輯時鐘，其數(shù)值等于發(fā)生時刻所屬進程的邏輯時鐘的取值；Pi發(fā)出的每個消息m都帶有本地邏輯時鐘，可表為(m,LCi,i)；?通過這些邏輯時鐘和消息，可以維護事件間的先于發(fā)生關(guān)系。附加條件：兩個事件不可以同時發(fā)生。LCi的更新原則為“、在發(fā)生一個(外部發(fā)送或內(nèi)部)事件之前更新LCi=LCi+d；、當收到一個帶時戳的消息(m,LCj,j)時，Pi執(zhí)行更新LCi=max(LCi,LCj)+d(d>0)。在圖2中，用標量時鐘模型可以得到各事件的邏輯時鐘：pOplp2圖3、標量邏輯時鐘標量邏輯時鐘的缺點是，afb可以得到LC(a)vLC(b),但LC(a)<LC(b)卻不一定能得出a-b。上圖，b、g兩個事件不存在先于發(fā)生關(guān)系。而且標量邏輯時鐘并不能確定系統(tǒng)里的并發(fā)關(guān)系。2?3■向量時鐘對標量邏輯時鐘算法的改進是向量時鐘算法。在一個由n個并發(fā)進程構(gòu)成的系統(tǒng)中，每個事件的邏輯時鐘均由一個n維向量(n元組)構(gòu)成，其中第i維(分量)對應(yīng)于第i個進程的邏輯時鐘Vi。第i個進程在事件發(fā)生時，繼承上一事件的邏輯時鐘并將自身所對應(yīng)的分量Vi增加一個步長，任何進程Pi在發(fā)出任何信息時都要將自己當前的邏輯時鐘分

量Vi起發(fā)送出去，如果是接收事件，且發(fā)送方為j則比較自己繼承的Vj和收到的邏輯時鐘，并取其中較大者為自己的Vj。這樣，每次消息都能使接收方更新對系統(tǒng)每個進程的時鐘認識。在沒有死鎖的向量時鐘系統(tǒng)中，設(shè)：-i進程中a事件的向量時鐘為(…ai?aj…)-j進程中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為對應(yīng)的發(fā)送事件b所屬進程、j進程中b事件的向量時鐘為(?bi……)、若滿足aivbi，則存在一個因等待接收消息存在的死鎖。一致割在這一部分，介紹一個利用先于發(fā)生關(guān)系來理解分布式系統(tǒng)的例子：一致割。一致割是指處理器可以并發(fā)保留的狀態(tài)，在一個分布式系統(tǒng)中，基本上沒有可以記錄系統(tǒng)狀態(tài)瞬時快照的觀察者?？墒?，這樣一種能力在解決譬如系統(tǒng)崩潰后的恢復(fù)、檢測系統(tǒng)中是否存在死鎖及檢測計算是否已經(jīng)終止時是需要的?？梢匀〈姆椒ㄊ窍到y(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生，那么這個向量就是一致