第5章分布式系統(tǒng)的同步

分布式系統(tǒng)同步算法分布式系統(tǒng)進(jìn)程同步邏輯時鐘Lamport算法物理時鐘Cristian算法Berkeley算法同步基本含義同步是指兩個或兩個以上隨時間變化的量在變化過程中保持一定的相對關(guān)系。當(dāng)兩個設(shè)備一起工作并對時間有精確要求的時候，就需要在它們之間進(jìn)行同步。同步是基于在兩個設(shè)備之間規(guī)定一個共同的時間參考。數(shù)據(jù)庫同步的含義就是讓兩個或多個數(shù)據(jù)庫內(nèi)容保持一致，或者按需要部分保持一致。文件同步的含義就是讓兩個或多個文件夾里的文件保持一致，或者按需要部分保持一致。網(wǎng)絡(luò)通信編程中常提到的“同步”，則主要指某函數(shù)的執(zhí)行方式，即函數(shù)調(diào)用者需等待函數(shù)執(zhí)行完成后才能進(jìn)到下一步?！巴酵ㄐ拧钡耐ㄐ烹p方必須先建立同步，即雙方的時鐘要調(diào)整到同一個頻率。收發(fā)雙方不停地發(fā)送和接收連續(xù)的同步比特流。5.1分布式系統(tǒng)時鐘同步在分布式系統(tǒng)中：進(jìn)程之間的通信：采用消息傳遞(Message-passing)進(jìn)行通信。與進(jìn)程通信密切相關(guān)的問題：進(jìn)程之間的協(xié)作和同步。

5.1分布式系統(tǒng)時鐘同步分布式系統(tǒng)中的同步比單機(jī)系統(tǒng)中的同步要復(fù)雜的多,這是由分布式算法決定的:

1.相關(guān)的信息是分布在多個機(jī)器上的。

2.進(jìn)程根據(jù)局部信息來作出決定。

3.對系統(tǒng)中任一個機(jī)器的失敗應(yīng)能容錯。

4.不存在公共時鐘或其它全局時間源。

5.1分布式系統(tǒng)時鐘同步由一個機(jī)器收集所有的信息進(jìn)行處理是不可能的。在分布式系統(tǒng)中必將造成某一個進(jìn)程負(fù)擔(dān)過重。分布式系統(tǒng)應(yīng)該比單機(jī)系統(tǒng)更可靠。如果一個機(jī)器崩潰了,其余的機(jī)器應(yīng)能繼續(xù)工作,而不至于使系統(tǒng)癱瘓。在單機(jī)系統(tǒng)中,時間是確定的。如果一個進(jìn)程想要知道時間,則它可以調(diào)用一個系統(tǒng)調(diào)用由內(nèi)核告訴它當(dāng)前的時間值。如果一個進(jìn)程先得到時間值而另一個進(jìn)程后得到時間值,那么,先得到的時間值一定比后得到的時間值小。在分布式系統(tǒng)中,所有機(jī)器要在時間上達(dá)到一致是非常困難的。5.1分布式系統(tǒng)時鐘同步在分布式系統(tǒng)中缺乏全局時間產(chǎn)生不良影響的例子：Unix中make程序的調(diào)用問題。假設(shè)實(shí)現(xiàn)程序編輯功能的進(jìn)程與實(shí)現(xiàn)程序編譯功能的進(jìn)程在不同的兩臺計(jì)算機(jī)上運(yùn)行。Make程序的功能：自動完成對源文件的編譯Make工具最主要也是最基本的功能就是通過makefile文件來描述源程序之間的相互關(guān)系并自動維護(hù)編譯工作通常,一個大程序分成多個源文件。這樣,對其中某一個文件的修改只需要對被修改的這個文件進(jìn)行重編譯,而無須對所有的源文件進(jìn)行編譯。當(dāng)調(diào)用make程序時，Make程序根據(jù)所有源文件和對應(yīng)目標(biāo)文件的修改時間來決定是否對某個源文件重新編譯。如果源文件input.c的修改時間為5155且對應(yīng)目標(biāo)文件input.o的修改時間為5151,那么,make程序知道input.c已被修改。input.c必須被重新編譯。如果output.c的修改時間為5144且對應(yīng)目標(biāo)文件output.o的修改時間為5145,則不需要對output.c進(jìn)行重新編譯。Make程序在考察完所有源文件和其對應(yīng)目標(biāo)文件的修改時間后決定那些文件需要重新編譯并調(diào)用編譯器對其進(jìn)行編譯。5.1分布式系統(tǒng)時鐘同步在分布式環(huán)境中,由于時間不同步造成程序不能正常運(yùn)行：假定output.o的修改時間為5144,output.c被修改并被賦予的時間為5143,原因是output.c所在機(jī)器上的時鐘要比output.o所在機(jī)器上的時鐘慢。make程序不調(diào)用編譯器進(jìn)行編譯。結(jié)果,最終可執(zhí)行二進(jìn)制程序?qū)⒑杏尚吕显次募傻哪繕?biāo)文件，導(dǎo)致該可執(zhí)行程序無法運(yùn)行而程序員卻不知道原因而一直尋找程序代碼的錯誤。結(jié)論：在分布式系統(tǒng)中，時鐘同步是非常重要的，也是必不可少的。

時鐘同步問題例：makefile誤差時間output.o：cc–Coutput.c5.1分布式系統(tǒng)時鐘同步5.1.1邏輯時鐘同步算法

在分布式系統(tǒng)中，n臺計(jì)算機(jī)上的時鐘值都不相同。因此,需要一種方法將所有機(jī)器上的時鐘進(jìn)行同步。

Lamport在1978年指出時鐘同步是可能的并提出了一個邏輯時鐘同步算法。在1990年,Lamport擴(kuò)展了他的工作。Lamport指出時鐘的同步不是絕對的。如果兩個進(jìn)程并不交互,則它們的時鐘就無須同步。

邏輯時鐘同步算法系統(tǒng)中的進(jìn)程不需要在事件發(fā)生的確切時間上達(dá)成一致而只需要在事件發(fā)生的先后順序上達(dá)成一致即可。在make例子中,make只需要知道input.c是否比input.o生成的早即可,而無須知道input.c和input.o確切的生成時間。在許多應(yīng)用中,只要所有機(jī)器都認(rèn)可某一時間就足夠了,而這個時間無須與收音機(jī)每小時廣播的時間相同例如,盡管現(xiàn)在真正的時間是10:05,但只要所有機(jī)器都認(rèn)為現(xiàn)在是10:00,我們說系統(tǒng)的時鐘是同步的。我們把這種并不一定是真正時間但所有機(jī)器都一致認(rèn)可的時鐘稱之為邏輯時鐘。5.1分布式系統(tǒng)時鐘同步5.1.1邏輯時鐘同步算法如果我們增加一個條件:所有的時鐘不僅一致而且與實(shí)際時間之間的誤差不超過某個值。那么,這種時鐘我們稱之為物理時鐘。為了將邏輯時鐘進(jìn)行同步,Lamport定義了一種稱之為在之前發(fā)生的關(guān)系。表達(dá)式a→b讀做”a在b之前發(fā)生”。它表示所有的進(jìn)程都認(rèn)為事件a先發(fā)生,而事件b后發(fā)生。a→b存在于下列兩種情況:

1.如果a和b都是同一個進(jìn)程中的兩個事件且a在b之前發(fā)生,則a→b為真。

2.如果a是一個進(jìn)程發(fā)送一個消息的事件且b是另一個進(jìn)程接收該消息的事件,則a→b為真。

5.1分布式系統(tǒng)時鐘同步5.1.1邏輯時鐘同步算法在之前發(fā)送是一個傳遞關(guān)系,如果a→b且b→c,則a→c。如果兩個事件x和y分別發(fā)生在兩個不同的進(jìn)程內(nèi)且x和y不是同一個消息的發(fā)送和接收事件,則x→y不為真,y→x亦不為真。我們將這兩個事件稱之為是并發(fā)事件。度量時間的方法：對于每一個事件a,我們給a分配一個所有進(jìn)程都認(rèn)可的時間值C(a)。這種時間值必須具有一個特性:如果a→b,則C(a)<C(b)。時鐘時間C是一直向前走的(即增加)，不會向后退(即減少)。時間的修改只能增加而不能減少。

Lamport邏輯時鐘同步算法算法基本思想在圖5-1（a）中有三個進(jìn)程。每一個進(jìn)程都運(yùn)行在不同的機(jī)器上且每一個機(jī)器都有一個自己的時鐘以各自的速度走時。當(dāng)進(jìn)程0中的時鐘滴答6次時，進(jìn)程1滴答8次，而進(jìn)程3滴答10次。在時間為6時,進(jìn)程0發(fā)送了一個消息A給進(jìn)程1。進(jìn)程1在時間為16時收到了消息。如果消息中含有消息開始發(fā)送的時間值6,則進(jìn)程1認(rèn)為該消息的傳輸花費(fèi)了10次滴答。同理,消息B從進(jìn)程1傳輸?shù)竭M(jìn)程2花費(fèi)了16次滴答。但是,由進(jìn)程2發(fā)給進(jìn)程1的消息C在發(fā)送時的時間值為60而在接收時的時間值為56。這樣,消息C的傳輸時間為負(fù)值。

Lamport算法時間慢快慢快5.1分布式系統(tǒng)時鐘同步5.1.1邏輯時鐘同步算法Lamport解決這個問題的算法：每一個消息都含有一個發(fā)送者時鐘的發(fā)送時間,當(dāng)消息到達(dá)時,接收者將自己時鐘的接收時間與發(fā)送時間相比較。如果接收時間小于等于發(fā)送時間,則接收者的時鐘被修改成發(fā)送時間加1。如果接收時間大于發(fā)送時間,則不改變接收者的時鐘。因此,消息C到達(dá)進(jìn)程1的時間改為61,消息D到達(dá)進(jìn)程0的時間改為70(見圖5-1(b))。Lamport算法還必須滿足一個要求：任意兩個事件的時間之差至少為1。如果一個進(jìn)程連續(xù)發(fā)送或接收兩個消息,則這兩個消息的時間之差也至少為1。我們對不同進(jìn)程內(nèi)兩個同時發(fā)生的事件是這樣賦時間值的:5.1分布式系統(tǒng)時鐘同步5.1.1邏輯時鐘同步算法事件發(fā)生的時間值與該事件所屬進(jìn)程的進(jìn)程號連接起來,中間用’.’加以分隔。例如,進(jìn)程1和進(jìn)程2中兩個事件恰好同時在時間為40時發(fā)生。進(jìn)程1中的事件發(fā)生時間為40.1而進(jìn)程2中的事件發(fā)生時間為40.2。由此我們可以對系統(tǒng)中所有事件按如下方法賦時間值:1.在同一進(jìn)程中,如果事件a在事件b之前發(fā)生,則

C(a)<C(b)。

2.如果a和b分別是一個消息的發(fā)送和接收事件,則

C(a)<C(b)。

3.對所有事件a和b,C(a)≠C(b)。

5.1分布式系統(tǒng)時鐘同步5.1.2物理時鐘同步算法如果某臺機(jī)器有一個WWW接收器接收標(biāo)準(zhǔn)時間,那么,時鐘同步算法的目的就是讓所有機(jī)器的時鐘與該機(jī)器的時鐘進(jìn)行同步。如果沒有一臺機(jī)器具有WWW接收器且每一臺機(jī)器都有自己的時鐘,那么,時鐘同步算法的目的就是使得所有機(jī)器的時鐘盡可能地一致。假定每一個機(jī)器都有一個每秒中斷H次的定時器。定時器中斷一次,中斷處理程序就將軟件時鐘加1。該軟件時鐘保存滴答(即中斷)次數(shù)。我們定義這個軟件時鐘的值為C。

5.1分布式系統(tǒng)時鐘同步5.1.2物理時鐘同步算法當(dāng)UTC(一種標(biāo)準(zhǔn)的時間源)時間為t,則機(jī)器p上時鐘值為Cp(t)。在理想情況下,對于所有的p和t,Cp(t)=t。換句話說,dC/dt=1。實(shí)際的定時器不可能每一秒精確地滴答H次。一個具有H=60的定時器應(yīng)該每小時周期地滴答516,000次。但世界上最先進(jìn)定時器芯片的相對誤差是10-5。這就意味著一個機(jī)器時鐘每小時的滴答值在515,998至516,005范圍內(nèi)。更確切地說,如果存在某個常數(shù)ρ使得：

1-ρ≤dC/dt≤1+ρ

則該定時器的誤差在允許的范圍之內(nèi)。常數(shù)ρ由廠商設(shè)定。有時也稱之為最大漂移率。當(dāng)dC/dt>1時,時鐘太快。當(dāng)dC/dt<1時,時鐘太慢。只有dC/dt=1時,時鐘不快不慢。

Christian算法5.1.2基本思想一臺機(jī)器設(shè)為時間服務(wù)器(帶有衛(wèi)星接收器)其他的每一臺機(jī)器周期性地向時間服務(wù)器發(fā)送請求消息以獲得當(dāng)前標(biāo)準(zhǔn)時間。時間服務(wù)器在短時間內(nèi)將包含當(dāng)前時間的消息發(fā)送給請求時間機(jī)器。發(fā)送機(jī)器收到此消息后，將機(jī)器時鐘調(diào)到與時間服務(wù)器一致的標(biāo)準(zhǔn)時間。Christian’s算法--逐步調(diào)整法時間服務(wù)器，可接受WWV的UTC時間(CoordinatedUniversalTime國際協(xié)調(diào)時間)每隔δ/5ρ校準(zhǔn)時間（允許誤差δ

，存在誤差ρ

）兩個問題：時間決不能倒退,延遲假設(shè)：每秒產(chǎn)生100次中斷，每次中斷將時間加10毫秒若調(diào)慢時鐘，中斷服務(wù)程序每次只加9毫秒；若加快時鐘，則加11毫秒。傳播時間Christian算法存在問題當(dāng)發(fā)送消息機(jī)器時間比標(biāo)準(zhǔn)時間快時，發(fā)送消息的機(jī)器時間需往后調(diào)，應(yīng)當(dāng)避免。解決方法：改變定時器每秒中斷次數(shù)服務(wù)器的回答消息具有一定的延遲。Berkeley算法–主動式方法時間監(jiān)控器定期查詢其他機(jī)器時間計(jì)算出平均值通知其他機(jī)器調(diào)整時間平均值算法–非集中式方法將時間劃分成固定長度的再