第3章時間和全局狀態(tài)第3章時間和全局狀態(tài)第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)同步物理時鐘邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介簡介如何計時？如何同步時鐘？沒有物理時鐘能否確定事件的順序？簡介如何計時？簡介時間的重要性需要精確度量——審計電子商務(wù)某些算法依賴于時鐘同步——數(shù)據(jù)一致性維護(hù)、make計算全局狀態(tài)——事件排序時間的復(fù)雜性節(jié)點具有獨立的物理時鐘精確同步物理時鐘非常困難全局狀態(tài)的捕獲依賴于邏輯時鐘邏輯時鐘與物理時鐘無必然聯(lián)系簡介時間的重要性時鐘、事件和進(jìn)程狀態(tài)時間分類天文學(xué)時間

-太陽日：兩次連續(xù)的太陽中天之間的時間間隔

-太陽秒：1/86400個太陽日國際原子時間(TAI)-基于銫原子跳躍周期

-秒：9192631770次跳躍周期通用協(xié)調(diào)時間(UTC)-基于原子時間

-采用潤秒，與天文時間保持一致時鐘、事件和進(jìn)程狀態(tài)時間分類第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)同步物理時鐘邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介時鐘、事件和進(jìn)程狀態(tài)假設(shè)每個進(jìn)程在單處理器上執(zhí)行處理器之間不共享內(nèi)存進(jìn)程之間通過消息進(jìn)行通信進(jìn)程狀態(tài)所有變量的值相關(guān)的本地操作系統(tǒng)環(huán)境中的對象的值事件定義：一個通信動作或進(jìn)程狀態(tài)轉(zhuǎn)換動作進(jìn)程歷史：時鐘、事件和進(jìn)程狀態(tài)假設(shè)時鐘、事件和進(jìn)程狀態(tài)計算機(jī)時鐘晶體具有固定震蕩頻率硬件時鐘：軟件時鐘：時鐘漂移頻率不同時鐘頻率隨溫度變化而有所差別時鐘偏移不可避免Infact,theeffectofclockskewisthemainreasonwhyclockoffsetskeepdriftingaway.Novelclockphaseoffset……IEEETransactionsonCommnunications,Vol55,No.4,2007.4時鐘、事件和進(jìn)程狀態(tài)計算機(jī)時鐘第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)同步物理時鐘邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介同步物理時鐘外部同步采用權(quán)威的外部時間源時鐘Ci在范圍D內(nèi)是準(zhǔn)確的內(nèi)部同步無外部權(quán)威時間源,系統(tǒng)內(nèi)時鐘同步時鐘Ci在范圍D內(nèi)是準(zhǔn)確的關(guān)系

若P在范圍D內(nèi)外部同步,則P在范圍2D內(nèi)內(nèi)部同步同步物理時鐘外部同步同步物理時鐘Cristian方法(適用于只有一臺機(jī)器有WWV接收器)應(yīng)用條件

-存在時間服務(wù)器，可與外部時間源同步

-消息往返時間與系統(tǒng)所要求的精度相比足夠短協(xié)議

-進(jìn)程p根據(jù)消息mr，mt計算消息往返時間Tround-根據(jù)服務(wù)器在mt中放置的時間t設(shè)置時鐘為：t+Tround/2mtp時間服務(wù)器Smr同步物理時鐘Cristian方法(適用于只有一臺機(jī)器有WWV同步物理時鐘Berkeley算法（沒有WWV接收器）主機(jī)周期輪詢從屬機(jī)時間主機(jī)通過消息往返時間估算從屬機(jī)的時間

與Cristian方法類似主機(jī)計算容錯平均值主機(jī)發(fā)送每個從屬機(jī)的調(diào)整量同步物理時鐘Berkeley算法（沒有WWV接收器）同步物理時鐘網(wǎng)絡(luò)時間協(xié)議(NTP)設(shè)計目標(biāo)

-可外部同步使得跨Internet的用戶能精確地與UTC同步

-高可靠性可處理連接丟失，采用冗余服務(wù)器、路徑等

-擴(kuò)展性好大量用戶可經(jīng)常同步，以抵消漂移率的影響

-安全性強(qiáng)防止惡意或偶然的干擾同步物理時鐘網(wǎng)絡(luò)時間協(xié)議(NTP)同步物理時鐘協(xié)議結(jié)構(gòu)

-層次結(jié)構(gòu)

-主服務(wù)器直接與外部UTC同步

-同步子網(wǎng)可重新配置123233

同步子網(wǎng)結(jié)構(gòu)示例同步物理時鐘協(xié)議結(jié)構(gòu)123233第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)物理時鐘同步邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介邏輯時間和邏輯時鐘邏輯時間的引入分布式系統(tǒng)中的物理時鐘無法完美同步

-消息傳輸延時的不確定性事件排序是眾多分布式算法的基石

-互斥算法

-死鎖檢測算法缺乏全局時鐘

-后發(fā)生的事件有可能賦予較早的時間標(biāo)記邏輯時間和邏輯時鐘邏輯時間的引入邏輯時間和邏輯時鐘邏輯時鐘眾多應(yīng)用只要求所有節(jié)點具有相同時間，該時間不一定與實際時間相同Lamport(1978)指出：不進(jìn)行交互的兩個進(jìn)程之間不需要時鐘同步對于不需要交互的兩個進(jìn)程而言，即使沒有時鐘同步，也無法察覺，更不會產(chǎn)生問題。所有的進(jìn)程需要在時間的發(fā)生順序上達(dá)成一致

如make程序邏輯時間和邏輯時鐘邏輯時鐘邏輯時間和邏輯時鐘事件排序“系統(tǒng)i中的事件a發(fā)生在系統(tǒng)j中的事件b之前”是不準(zhǔn)確的

-事件發(fā)生和觀察之間存在時延

-不同系統(tǒng)中的時鐘存在偏差時間戳(Lamport1978)

-用于分布式系統(tǒng)中的事件排序

-與物理時鐘無關(guān)

-實用高效，應(yīng)用廣泛邏輯時間和邏輯時鐘事件排序邏輯時間和邏輯時鐘兩個基本事實

-同一進(jìn)程中的兩個事件存在關(guān)系“i”-任一消息的發(fā)送事件發(fā)生在該消息的接收事件之前“發(fā)生在先(happens-before)”關(guān)系定義

-若存在進(jìn)程pi滿足eie’，則ee’-對于任一消息m，存在send(m)recv(m)-若事件滿足ee’

和e’e’’

，則ee’’并發(fā)關(guān)系定義

XY與YX均不成立，則稱事件X、Y是并發(fā)的，表示為X||Y邏輯時間和邏輯時鐘兩個基本事實邏輯時間和邏輯時鐘事件排序示例

-bc，cd和df成立

-bf與ef均成立

-事件b和e無法比較，即b||ep1p2p3abcdefm1m2物理時間邏輯時間和邏輯時鐘事件排序示例p1p2p3abcdefm1m邏輯時間和邏輯時鐘Lamport時鐘機(jī)制

-進(jìn)程維護(hù)一個單調(diào)遞增的軟件計數(shù)器，充當(dāng)邏輯時鐘

-用邏輯時鐘為事件添加時間戳

-按事件的時間戳大小為時間排序邏輯時鐘修改規(guī)則

-進(jìn)程pi發(fā)出事件前，邏輯時鐘Li:=Li+1-進(jìn)程pi發(fā)送消息m時，在m中添加時間戳t=Li-進(jìn)程pj在接收(m,t)時，更新Li:=max(Lj,t)+1，給s事件recv(m)添加時間戳后發(fā)送給應(yīng)用程序邏輯時間和邏輯時鐘Lamport時鐘abcdefm1m2213451p1p2p3物理時間邏輯時間和邏輯時鐘Lamport時鐘示例(一)

abL(a)<L(b)

L(e)<L(b)beabcdefm1m2213451p1p2p3物理邏輯時間和邏邏輯時間和邏輯時鐘(a)三個不同速率的時鐘(b)Lamport算法校正時鐘Lamport時鐘示例(二)邏輯時間和邏輯時鐘(a)三個不同速邏輯時間和邏輯時鐘Lamport時鐘練習(xí)假設(shè)系統(tǒng)中只存在消息發(fā)送和接收事件，如下圖所示，請給出事件a-g的邏輯時鐘。邏輯時鐘

0邏輯時間和邏輯時鐘Lamport時鐘練習(xí)邏輯時鐘0邏輯時間和邏輯時鐘Lamport時鐘練習(xí)答案邏輯時鐘：0144328657579邏輯時間和邏輯時鐘Lamport時鐘練習(xí)答案邏輯時鐘：014邏輯時間和邏輯時鐘不同進(jìn)程產(chǎn)生的消息可能具有相同數(shù)值的Lamport時間戳物理時間邏輯時間和邏輯時鐘不同進(jìn)程產(chǎn)生的消息可能具有相同數(shù)值的Lam邏輯時間和邏輯時鐘基于Lamport時間戳的事件排序---總結(jié)算法不依賴于事件發(fā)生的真實時間與真實物理時間中事件的發(fā)生順序可能不一致

基于Lamport時間戳的排序中，在時刻(2,1)發(fā)生的事件發(fā)生比在時刻（2，2）發(fā)生的事件要早，然而在真實物理時間中可能恰好相反。邏輯時間和邏輯時鐘基于Lamport時間戳的事件排序---總邏輯時間和邏輯時鐘Lamport時鐘不具備性質(zhì)：若L(A)<L(B)則AB沒有捕獲事件的因果關(guān)系

節(jié)點B發(fā)布一篇文章并傳送給節(jié)點A和C。節(jié)點A就此發(fā)表評論并傳送給節(jié)點B和C。araarr我們無法準(zhǔn)確確定r的先后關(guān)系：C(a)<C(r)ara是節(jié)點A發(fā)布的文章r是節(jié)點B對文章a的評論

邏輯時間和邏輯時鐘Lamport時鐘不具備性質(zhì)：若L(A)全序邏輯時鐘引入進(jìn)程標(biāo)示符創(chuàng)建事件的全序關(guān)系若e、e’分別為進(jìn)程pi、pj中發(fā)生的事件，則其全局邏輯時間戳分別為(Ti,i)、(Tj,j)。ee’Ti<Tj||Ti=Tj&&i<j系統(tǒng)中各個事件Lamport時間戳均不相同全序邏輯時鐘引入進(jìn)程標(biāo)示符創(chuàng)建事件的全序關(guān)系向量時鐘克服Lamport時鐘的缺點：若L(e)<L(e’)不能推出則ee’。每個進(jìn)程維護(hù)它自己的向量時鐘ViVC1:初始情況下，Vi[j]=0,i,j=1,2,...N.VC2:在pi給事件加時間戳之前，設(shè)置Vi[i]=Vi[i]+1。VC3:pi在它發(fā)送的每個消息中包括t＝Vi。VC4：當(dāng)pi接收到消息中的時間戳t時，設(shè)置Vi[j]=max(Vi[j],t[j]),j=1,2,...,N。向量時鐘克服Lamport時鐘的缺點：若L(e)<L(e向量時鐘向量時鐘

Host1Host2Host3Host40,0,0,0VectorlogicalclockMessage(vectortimestamp)PhysicalTime0,0,0,00,0,0,00,0,0,0(1,0,0,0)1,0,0,01,1,0,02,0,0,02,0,1,0(2,0,0,0)2,0,2,02,0,2,1(2,0,2,0)1,2,0,02,2,3,0(1,2,0,0)4,0,2,24,2,4,2(4,0,2,2)2,0,2,23,0,2,2(2,0,2,2)2,0,2,34,2,5,3(2,0,2,3)n,m,p,q向量時鐘Host1Host2Host3Host40,0,第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)同步物理時鐘邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介全局狀態(tài)觀察全局狀態(tài)的必要性分布式無用單元的收集

-基于對象的引用計數(shù)

-必須考慮信道和進(jìn)程的狀態(tài)分布式死鎖檢測

觀察系統(tǒng)中的“等待”關(guān)系圖中是否存在循環(huán)p1消息無用對象對象引用p2等待等待p1p2全局狀態(tài)觀察全局狀態(tài)的必要性p1消息無用對象p2等待等待p1分布式終止檢測與進(jìn)程的狀態(tài)有關(guān)——“主動”或“被動”分布式調(diào)試需要收集同一時刻系統(tǒng)中分布式變量的數(shù)值全局狀態(tài)激活被動的p1p2被動的分布式終止檢測全局狀態(tài)激活被動的p1p2被動的全局狀態(tài)全局狀態(tài)和一致割集觀察進(jìn)程集的狀態(tài)——全局狀態(tài)非常困難根源：缺乏全局時間進(jìn)程的歷史

hi=<ei0,ei1,ei2

…>進(jìn)程歷史的有限前綴

hik=<ei0,ei1,…,eik>全局歷史——單個進(jìn)程歷史的并集

H=h1

h2

…

hN全局狀態(tài)全局狀態(tài)和一致割集全局狀態(tài)進(jìn)程狀態(tài)

sik:進(jìn)程pi在第k個事件發(fā)生之前的狀態(tài)全局狀態(tài)——單個進(jìn)程狀態(tài)的集合

S=(s1,s2,…sN)割集——系統(tǒng)全局歷史的子集

C=<h1c1,h2c2…h(huán)3c3>割集的一致性割集C是一致的:對于所有事件eC,f

e

f

C全局狀態(tài)進(jìn)程狀態(tài)全局狀態(tài)割集示例m1m2p1p2物理時間e10一致的割集不一致的割集e11e12e13e20e21e22全局狀態(tài)割集示例m1m2p1p2物理時間e10一致的割集不一全局狀態(tài)一致的全局狀態(tài)——對應(yīng)于一致割集的狀態(tài)

S0

S1

S2

…走向(run)-全局歷史中所有事件的全序

-與每個本地歷史順序一致

-不是所有的走向都經(jīng)歷一致的全局狀態(tài)線性化走向

-所有的線性化走向只經(jīng)歷一致的全局狀態(tài)

-若存在一個經(jīng)過S和S’的線性化走向，則狀態(tài)S’是從S可達(dá)全局狀態(tài)一致的全局狀態(tài)——對應(yīng)于一致割集的狀態(tài)全局狀態(tài)Chandy和Lamport的“快照”算法目的捕獲一致的全局狀態(tài)假設(shè)

-進(jìn)程和通道均不會出現(xiàn)故障

-單向通道，提供FIFO順序的消息傳遞

-進(jìn)程之間存在全連通關(guān)系

-任一進(jìn)程可在任一時間開始全局拍照

-拍照時，進(jìn)程可繼續(xù)執(zhí)行，并發(fā)送和接收消息全局狀態(tài)Chandy和Lamport的“快照”算法全局狀態(tài)算法基本思想

-接入通道+外出通道

-進(jìn)程狀態(tài)+通道狀態(tài)

-標(biāo)記消息

標(biāo)記接收規(guī)則：強(qiáng)制進(jìn)程在記錄下自己的狀態(tài)之后但在它們發(fā)送其他消息前發(fā)送一個標(biāo)記。

標(biāo)記發(fā)送規(guī)則：強(qiáng)制沒有記錄狀態(tài)的進(jìn)程去記錄狀態(tài)全局狀態(tài)算法基本思想全局狀態(tài)算法偽碼(一)進(jìn)程pi的標(biāo)記接收規(guī)則

pi接收通道c上的標(biāo)記消息：

if(pi還沒有記錄它的狀態(tài))pi記錄它的進(jìn)程狀態(tài)；將c的狀態(tài)記成空集；開始記錄從其他接入通道上到達(dá)的消息

elsepi把c的狀態(tài)記錄到從保留它的狀態(tài)以來它在c上接收到的消息集合中

endif全局狀態(tài)算法偽碼(一)全局狀態(tài)算法偽碼(二)

進(jìn)程pi的標(biāo)記發(fā)送規(guī)則在pi記錄了它的狀態(tài)之后，對每個外出通道c:(在pi從c上發(fā)送任何其他消息前)pi在c上發(fā)送一個消息標(biāo)記全局狀態(tài)算法偽碼(二)全局狀態(tài)算法示例

-兩個進(jìn)程p1、p2進(jìn)行交易，每件10$

-初始狀態(tài)進(jìn)程p2已經(jīng)收到5件商品的定單，它將馬上分發(fā)給p1

p1p2c2c1帳戶窗口部件$1000(none)帳戶窗口部件$502000全局狀態(tài)算法示例p1p2c2c1帳戶窗口$1000(none全局狀態(tài)最后狀態(tài)：P1:<$1000,0>;p2:<$50,1995>;

c1:<(fivewidgets)>;c2:<>p1(空)<$1000,0>1.全局狀態(tài)S0p1p1p1c2c1(空)2.全局狀態(tài)S1<$900,0><$900,0><$900,5><$50,1995><$50,1995><$50,2000><$50,2000>3.全局狀態(tài)S24.全局狀態(tài)S3p2p2p2p2c2c2c2c1c1c1(定單10，$100)，M(空)(空)(定單10，$100)，M(五個窗口部件)M=標(biāo)記信息)(定單10，$100)全局狀態(tài)最后狀態(tài)：P1:<$1000,0>;p2:全局狀態(tài)算法終止

-假設(shè)：一個進(jìn)程已經(jīng)收到了一個標(biāo)記信息，在有限的時間內(nèi)記錄了它的狀態(tài)，并在有限的時間里通過每個外出通道發(fā)送了標(biāo)記信息．

-若存在一條從進(jìn)程pi到進(jìn)程pj的信道和進(jìn)程的路徑，那么pi記錄它的狀態(tài)之后的有限時間內(nèi)pj將記錄它的狀態(tài)．

-進(jìn)程和通道圖是強(qiáng)連接的，因此在一些進(jìn)程記錄它的狀態(tài)之后的有限時間內(nèi)，所有進(jìn)程將記錄它們的狀態(tài)和節(jié)入通道的狀態(tài)。全局狀態(tài)算法終止全局狀態(tài)算法一致性

ei、ej分別為進(jìn)程pi、pj中的事件，且eiej則我們有:若ejCei

C，其中C為一個割集。即如果ej在pj記錄它的狀態(tài)之前發(fā)生，那么ei必須在pi記錄它的狀態(tài)之前發(fā)生.證明思路如下：

-i=j時，顯然成立

-i≠j時，反證法全局狀態(tài)算法一致性第3章時間和全局狀態(tài)簡介時鐘、事件和進(jìn)程狀態(tài)物理時鐘同步邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介分布式調(diào)試目的對系統(tǒng)實際執(zhí)行中的暫態(tài)作出判斷例子安全條件檢查

xi為進(jìn)程pi的變量(i=1,2,…)，安全條件為|xi-xj|≤控制系統(tǒng)所有閥門在某些時間是否全部處于開啟狀態(tài)分布式調(diào)試目的分布式調(diào)試方法監(jiān)控器進(jìn)程收集進(jìn)程狀態(tài)信息全局狀態(tài)謂詞的判斷

-可能的：存在一個一致的全局狀態(tài)S，H的一個線性化走向經(jīng)歷了這個全局狀態(tài)S，而且該S使得(s)為True。

-明確的：對于H的所有線性化走向L，存在L經(jīng)歷的一個一致的全局狀態(tài)S，而且該S使得(s)為True。分布式調(diào)試方法分布式調(diào)試觀察一致的全局狀態(tài)進(jìn)程的狀態(tài)信息附有向量時鐘值全局狀態(tài)的一致性判斷——CGS條件設(shè)S=(s1,s2,…,sN)是從監(jiān)控器進(jìn)程接收到的狀態(tài)信息中得出的全局狀態(tài)，V(si)是從pi接收到的狀態(tài)si的向量時間戳，則S是一致的全局狀態(tài)當(dāng)且僅當(dāng)：

V(si)[i]>=V(sj)[i]

(i,j=1,2,…,N)

即若一個進(jìn)程的狀態(tài)依賴于另一個進(jìn)程的狀態(tài)，則全局狀態(tài)也包含了它所以來的狀態(tài)。分布式調(diào)試觀察一致的全局狀態(tài)分布式調(diào)試全局狀態(tài)示例m1m2p1p2物理時間

CutC1(1,0)(2,0)(4,3)(2,1)(2,2)(2,3)(3,0)x1=1x1=100x1=105x2=100x2=95x2=90x1=90CutC2分布式調(diào)試全局狀態(tài)示例m1m2p1p2物理時間CutC1Sij=在進(jìn)程１發(fā)生事件i以及在進(jìn)程２發(fā)生事件j之后的全局狀態(tài)S00S10S20S21S30S31S32S22S23S33S43層次01234567分布式調(diào)試一致全局狀態(tài)網(wǎng)格Sij=在進(jìn)程１發(fā)生事件i以及在進(jìn)程２S00S10S20S2分布式調(diào)試判定可能的

從初始狀態(tài)考試，遍歷可達(dá)狀態(tài)的網(wǎng)格。L:=0;States:={(s01,s02,…,s0N)};while(對所有可能的S∈States，(s)=False)L:=L+1;Reachable:={S’:H中從一些S∈States可到達(dá)的狀態(tài)∧level(S’)=L};States:=Reachable;endwhile輸出“可能的”;分布式調(diào)試判定可能的

?

–層次012345FFFFTFF=((s)=False);T=((s)=True)分布式調(diào)試值判定示例

在第５層的狀態(tài)為True＝》明確的在第５層的狀態(tài)為False＝》可能的?–層次012345FFFFTFF=((s)=分布式調(diào)試異步系統(tǒng)

開銷很大，需要作O(kＮ)次比較。

同步系統(tǒng)物理時鐘：|Ci(t)－Cj(t)|<D，即在范圍D內(nèi)同步。同步系統(tǒng)中的算法改進(jìn)消息中同時攜帶物理時間戳和向量時間戳測試條件

V(si)[i]≧V(si)[i]，且si和sj能在同一時間發(fā)生分布式調(diào)試異步系統(tǒng)第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)物理時鐘同步邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介小結(jié)時鐘偏移和時鐘漂移物理時鐘同步Cristian方法Berkeley方法網(wǎng)絡(luò)時間協(xié)議邏輯時間發(fā)生在先關(guān)系Lamport時間戳向量時鐘小結(jié)時鐘偏移和時鐘漂移小結(jié)全局狀態(tài)一致割集，一致全局狀態(tài)“快照”算法分布式調(diào)試狀態(tài)收集判定可能的和明確的小結(jié)全局狀態(tài)作業(yè)11.411.14Databases-R-UsrunsaclusterofthreeserversA,B,andC,whichcommunicatewithoneanother.Youaretoldthatthecurrentclockskewsbetweenserverpairsareasfollows:A-B:3ms;B-C:1ms;C-A:-4ms.Further,youaretoldthatcorrectnessinthedatabaserequiresthatnotwoserverclocksbemorethan30msapart.Ifeachoftheservershasanabsoluteclockdriftof2msperminute,howmanyminimum(i.e.,worst-case)minutescantheclustergowithoutrunningasynchronizationalgorithmamongitsservers?作業(yè)11.4作業(yè)a,b,andcareeventsandnotwoeventsbelongtothesameprocess.Proveordisprove(givecounter-example)thefollowing: (a)aisconcurrentwithbandbisbeforecimpliesthataisbeforec. (b)aisconcurrentwithbandbisconcurrentwithcimpliesthataisconcurrentwithc.作業(yè)a,b,andcareeventsandn第3章時間和全局狀態(tài)第3章時間和全局狀態(tài)第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)同步物理時鐘邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介簡介如何計時？如何同步時鐘？沒有物理時鐘能否確定事件的順序？簡介如何計時？簡介時間的重要性需要精確度量——審計電子商務(wù)某些算法依賴于時鐘同步——數(shù)據(jù)一致性維護(hù)、make計算全局狀態(tài)——事件排序時間的復(fù)雜性節(jié)點具有獨立的物理時鐘精確同步物理時鐘非常困難全局狀態(tài)的捕獲依賴于邏輯時鐘邏輯時鐘與物理時鐘無必然聯(lián)系簡介時間的重要性時鐘、事件和進(jìn)程狀態(tài)時間分類天文學(xué)時間

-太陽日：兩次連續(xù)的太陽中天之間的時間間隔

-太陽秒：1/86400個太陽日國際原子時間(TAI)-基于銫原子跳躍周期

-秒：9192631770次跳躍周期通用協(xié)調(diào)時間(UTC)-基于原子時間

-采用潤秒，與天文時間保持一致時鐘、事件和進(jìn)程狀態(tài)時間分類第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)同步物理時鐘邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介時鐘、事件和進(jìn)程狀態(tài)假設(shè)每個進(jìn)程在單處理器上執(zhí)行處理器之間不共享內(nèi)存進(jìn)程之間通過消息進(jìn)行通信進(jìn)程狀態(tài)所有變量的值相關(guān)的本地操作系統(tǒng)環(huán)境中的對象的值事件定義：一個通信動作或進(jìn)程狀態(tài)轉(zhuǎn)換動作進(jìn)程歷史：時鐘、事件和進(jìn)程狀態(tài)假設(shè)時鐘、事件和進(jìn)程狀態(tài)計算機(jī)時鐘晶體具有固定震蕩頻率硬件時鐘：軟件時鐘：時鐘漂移頻率不同時鐘頻率隨溫度變化而有所差別時鐘偏移不可避免Infact,theeffectofclockskewisthemainreasonwhyclockoffsetskeepdriftingaway.Novelclockphaseoffset……IEEETransactionsonCommnunications,Vol55,No.4,2007.4時鐘、事件和進(jìn)程狀態(tài)計算機(jī)時鐘第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)同步物理時鐘邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介同步物理時鐘外部同步采用權(quán)威的外部時間源時鐘Ci在范圍D內(nèi)是準(zhǔn)確的內(nèi)部同步無外部權(quán)威時間源,系統(tǒng)內(nèi)時鐘同步時鐘Ci在范圍D內(nèi)是準(zhǔn)確的關(guān)系

若P在范圍D內(nèi)外部同步,則P在范圍2D內(nèi)內(nèi)部同步同步物理時鐘外部同步同步物理時鐘Cristian方法(適用于只有一臺機(jī)器有WWV接收器)應(yīng)用條件

-存在時間服務(wù)器，可與外部時間源同步

-消息往返時間與系統(tǒng)所要求的精度相比足夠短協(xié)議

-進(jìn)程p根據(jù)消息mr，mt計算消息往返時間Tround-根據(jù)服務(wù)器在mt中放置的時間t設(shè)置時鐘為：t+Tround/2mtp時間服務(wù)器Smr同步物理時鐘Cristian方法(適用于只有一臺機(jī)器有WWV同步物理時鐘Berkeley算法（沒有WWV接收器）主機(jī)周期輪詢從屬機(jī)時間主機(jī)通過消息往返時間估算從屬機(jī)的時間

與Cristian方法類似主機(jī)計算容錯平均值主機(jī)發(fā)送每個從屬機(jī)的調(diào)整量同步物理時鐘Berkeley算法（沒有WWV接收器）同步物理時鐘網(wǎng)絡(luò)時間協(xié)議(NTP)設(shè)計目標(biāo)

-可外部同步使得跨Internet的用戶能精確地與UTC同步

-高可靠性可處理連接丟失，采用冗余服務(wù)器、路徑等

-擴(kuò)展性好大量用戶可經(jīng)常同步，以抵消漂移率的影響

-安全性強(qiáng)防止惡意或偶然的干擾同步物理時鐘網(wǎng)絡(luò)時間協(xié)議(NTP)同步物理時鐘協(xié)議結(jié)構(gòu)

-層次結(jié)構(gòu)

-主服務(wù)器直接與外部UTC同步

-同步子網(wǎng)可重新配置123233

同步子網(wǎng)結(jié)構(gòu)示例同步物理時鐘協(xié)議結(jié)構(gòu)123233第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)物理時鐘同步邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介邏輯時間和邏輯時鐘邏輯時間的引入分布式系統(tǒng)中的物理時鐘無法完美同步

-消息傳輸延時的不確定性事件排序是眾多分布式算法的基石

-互斥算法

-死鎖檢測算法缺乏全局時鐘

-后發(fā)生的事件有可能賦予較早的時間標(biāo)記邏輯時間和邏輯時鐘邏輯時間的引入邏輯時間和邏輯時鐘邏輯時鐘眾多應(yīng)用只要求所有節(jié)點具有相同時間，該時間不一定與實際時間相同Lamport(1978)指出：不進(jìn)行交互的兩個進(jìn)程之間不需要時鐘同步對于不需要交互的兩個進(jìn)程而言，即使沒有時鐘同步，也無法察覺，更不會產(chǎn)生問題。所有的進(jìn)程需要在時間的發(fā)生順序上達(dá)成一致

如make程序邏輯時間和邏輯時鐘邏輯時鐘邏輯時間和邏輯時鐘事件排序“系統(tǒng)i中的事件a發(fā)生在系統(tǒng)j中的事件b之前”是不準(zhǔn)確的

-事件發(fā)生和觀察之間存在時延

-不同系統(tǒng)中的時鐘存在偏差時間戳(Lamport1978)

-用于分布式系統(tǒng)中的事件排序

-與物理時鐘無關(guān)

-實用高效，應(yīng)用廣泛邏輯時間和邏輯時鐘事件排序邏輯時間和邏輯時鐘兩個基本事實

-同一進(jìn)程中的兩個事件存在關(guān)系“i”-任一消息的發(fā)送事件發(fā)生在該消息的接收事件之前“發(fā)生在先(happens-before)”關(guān)系定義

-若存在進(jìn)程pi滿足eie’，則ee’-對于任一消息m，存在send(m)recv(m)-若事件滿足ee’

和e’e’’

，則ee’’并發(fā)關(guān)系定義

XY與YX均不成立，則稱事件X、Y是并發(fā)的，表示為X||Y邏輯時間和邏輯時鐘兩個基本事實邏輯時間和邏輯時鐘事件排序示例

-bc，cd和df成立

-bf與ef均成立

-事件b和e無法比較，即b||ep1p2p3abcdefm1m2物理時間邏輯時間和邏輯時鐘事件排序示例p1p2p3abcdefm1m邏輯時間和邏輯時鐘Lamport時鐘機(jī)制

-進(jìn)程維護(hù)一個單調(diào)遞增的軟件計數(shù)器，充當(dāng)邏輯時鐘

-用邏輯時鐘為事件添加時間戳

-按事件的時間戳大小為時間排序邏輯時鐘修改規(guī)則

-進(jìn)程pi發(fā)出事件前，邏輯時鐘Li:=Li+1-進(jìn)程pi發(fā)送消息m時，在m中添加時間戳t=Li-進(jìn)程pj在接收(m,t)時，更新Li:=max(Lj,t)+1，給s事件recv(m)添加時間戳后發(fā)送給應(yīng)用程序邏輯時間和邏輯時鐘Lamport時鐘abcdefm1m2213451p1p2p3物理時間邏輯時間和邏輯時鐘Lamport時鐘示例(一)

abL(a)<L(b)

L(e)<L(b)beabcdefm1m2213451p1p2p3物理邏輯時間和邏邏輯時間和邏輯時鐘(a)三個不同速率的時鐘(b)Lamport算法校正時鐘Lamport時鐘示例(二)邏輯時間和邏輯時鐘(a)三個不同速邏輯時間和邏輯時鐘Lamport時鐘練習(xí)假設(shè)系統(tǒng)中只存在消息發(fā)送和接收事件，如下圖所示，請給出事件a-g的邏輯時鐘。邏輯時鐘

0邏輯時間和邏輯時鐘Lamport時鐘練習(xí)邏輯時鐘0邏輯時間和邏輯時鐘Lamport時鐘練習(xí)答案邏輯時鐘：0144328657579邏輯時間和邏輯時鐘Lamport時鐘練習(xí)答案邏輯時鐘：014邏輯時間和邏輯時鐘不同進(jìn)程產(chǎn)生的消息可能具有相同數(shù)值的Lamport時間戳物理時間邏輯時間和邏輯時鐘不同進(jìn)程產(chǎn)生的消息可能具有相同數(shù)值的Lam邏輯時間和邏輯時鐘基于Lamport時間戳的事件排序---總結(jié)算法不依賴于事件發(fā)生的真實時間與真實物理時間中事件的發(fā)生順序可能不一致

基于Lamport時間戳的排序中，在時刻(2,1)發(fā)生的事件發(fā)生比在時刻（2，2）發(fā)生的事件要早，然而在真實物理時間中可能恰好相反。邏輯時間和邏輯時鐘基于Lamport時間戳的事件排序---總邏輯時間和邏輯時鐘Lamport時鐘不具備性質(zhì)：若L(A)<L(B)則AB沒有捕獲事件的因果關(guān)系

節(jié)點B發(fā)布一篇文章并傳送給節(jié)點A和C。節(jié)點A就此發(fā)表評論并傳送給節(jié)點B和C。araarr我們無法準(zhǔn)確確定r的先后關(guān)系：C(a)<C(r)ara是節(jié)點A發(fā)布的文章r是節(jié)點B對文章a的評論

邏輯時間和邏輯時鐘Lamport時鐘不具備性質(zhì)：若L(A)全序邏輯時鐘引入進(jìn)程標(biāo)示符創(chuàng)建事件的全序關(guān)系若e、e’分別為進(jìn)程pi、pj中發(fā)生的事件，則其全局邏輯時間戳分別為(Ti,i)、(Tj,j)。ee’Ti<Tj||Ti=Tj&&i<j系統(tǒng)中各個事件Lamport時間戳均不相同全序邏輯時鐘引入進(jìn)程標(biāo)示符創(chuàng)建事件的全序關(guān)系向量時鐘克服Lamport時鐘的缺點：若L(e)<L(e’)不能推出則ee’。每個進(jìn)程維護(hù)它自己的向量時鐘ViVC1:初始情況下，Vi[j]=0,i,j=1,2,...N.VC2:在pi給事件加時間戳之前，設(shè)置Vi[i]=Vi[i]+1。VC3:pi在它發(fā)送的每個消息中包括t＝Vi。VC4：當(dāng)pi接收到消息中的時間戳t時，設(shè)置Vi[j]=max(Vi[j],t[j]),j=1,2,...,N。向量時鐘克服Lamport時鐘的缺點：若L(e)<L(e向量時鐘向量時鐘

Host1Host2Host3Host40,0,0,0VectorlogicalclockMessage(vectortimestamp)PhysicalTime0,0,0,00,0,0,00,0,0,0(1,0,0,0)1,0,0,01,1,0,02,0,0,02,0,1,0(2,0,0,0)2,0,2,02,0,2,1(2,0,2,0)1,2,0,02,2,3,0(1,2,0,0)4,0,2,24,2,4,2(4,0,2,2)2,0,2,23,0,2,2(2,0,2,2)2,0,2,34,2,5,3(2,0,2,3)n,m,p,q向量時鐘Host1Host2Host3Host40,0,第3章時間和全局狀態(tài)簡介

時鐘、事件和進(jìn)程狀態(tài)同步物理時鐘邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介全局狀態(tài)觀察全局狀態(tài)的必要性分布式無用單元的收集

-基于對象的引用計數(shù)

-必須考慮信道和進(jìn)程的狀態(tài)分布式死鎖檢測

觀察系統(tǒng)中的“等待”關(guān)系圖中是否存在循環(huán)p1消息無用對象對象引用p2等待等待p1p2全局狀態(tài)觀察全局狀態(tài)的必要性p1消息無用對象p2等待等待p1分布式終止檢測與進(jìn)程的狀態(tài)有關(guān)——“主動”或“被動”分布式調(diào)試需要收集同一時刻系統(tǒng)中分布式變量的數(shù)值全局狀態(tài)激活被動的p1p2被動的分布式終止檢測全局狀態(tài)激活被動的p1p2被動的全局狀態(tài)全局狀態(tài)和一致割集觀察進(jìn)程集的狀態(tài)——全局狀態(tài)非常困難根源：缺乏全局時間進(jìn)程的歷史

hi=<ei0,ei1,ei2

…>進(jìn)程歷史的有限前綴

hik=<ei0,ei1,…,eik>全局歷史——單個進(jìn)程歷史的并集

H=h1

h2

…

hN全局狀態(tài)全局狀態(tài)和一致割集全局狀態(tài)進(jìn)程狀態(tài)

sik:進(jìn)程pi在第k個事件發(fā)生之前的狀態(tài)全局狀態(tài)——單個進(jìn)程狀態(tài)的集合

S=(s1,s2,…sN)割集——系統(tǒng)全局歷史的子集

C=<h1c1,h2c2…h(huán)3c3>割集的一致性割集C是一致的:對于所有事件eC,f

e

f

C全局狀態(tài)進(jìn)程狀態(tài)全局狀態(tài)割集示例m1m2p1p2物理時間e10一致的割集不一致的割集e11e12e13e20e21e22全局狀態(tài)割集示例m1m2p1p2物理時間e10一致的割集不一全局狀態(tài)一致的全局狀態(tài)——對應(yīng)于一致割集的狀態(tài)

S0

S1

S2

…走向(run)-全局歷史中所有事件的全序

-與每個本地歷史順序一致

-不是所有的走向都經(jīng)歷一致的全局狀態(tài)線性化走向

-所有的線性化走向只經(jīng)歷一致的全局狀態(tài)

-若存在一個經(jīng)過S和S’的線性化走向，則狀態(tài)S’是從S可達(dá)全局狀態(tài)一致的全局狀態(tài)——對應(yīng)于一致割集的狀態(tài)全局狀態(tài)Chandy和Lamport的“快照”算法目的捕獲一致的全局狀態(tài)假設(shè)

-進(jìn)程和通道均不會出現(xiàn)故障

-單向通道，提供FIFO順序的消息傳遞

-進(jìn)程之間存在全連通關(guān)系

-任一進(jìn)程可在任一時間開始全局拍照

-拍照時，進(jìn)程可繼續(xù)執(zhí)行，并發(fā)送和接收消息全局狀態(tài)Chandy和Lamport的“快照”算法全局狀態(tài)算法基本思想

-接入通道+外出通道

-進(jìn)程狀態(tài)+通道狀態(tài)

-標(biāo)記消息

標(biāo)記接收規(guī)則：強(qiáng)制進(jìn)程在記錄下自己的狀態(tài)之后但在它們發(fā)送其他消息前發(fā)送一個標(biāo)記。

標(biāo)記發(fā)送規(guī)則：強(qiáng)制沒有記錄狀態(tài)的進(jìn)程去記錄狀態(tài)全局狀態(tài)算法基本思想全局狀態(tài)算法偽碼(一)進(jìn)程pi的標(biāo)記接收規(guī)則

pi接收通道c上的標(biāo)記消息：

if(pi還沒有記錄它的狀態(tài))pi記錄它的進(jìn)程狀態(tài)；將c的狀態(tài)記成空集；開始記錄從其他接入通道上到達(dá)的消息

elsepi把c的狀態(tài)記錄到從保留它的狀態(tài)以來它在c上接收到的消息集合中

endif全局狀態(tài)算法偽碼(一)全局狀態(tài)算法偽碼(二)

進(jìn)程pi的標(biāo)記發(fā)送規(guī)則在pi記錄了它的狀態(tài)之后，對每個外出通道c:(在pi從c上發(fā)送任何其他消息前)pi在c上發(fā)送一個消息標(biāo)記全局狀態(tài)算法偽碼(二)全局狀態(tài)算法示例

-兩個進(jìn)程p1、p2進(jìn)行交易，每件10$

-初始狀態(tài)進(jìn)程p2已經(jīng)收到5件商品的定單，它將馬上分發(fā)給p1

p1p2c2c1帳戶窗口部件$1000(none)帳戶窗口部件$502000全局狀態(tài)算法示例p1p2c2c1帳戶窗口$1000(none全局狀態(tài)最后狀態(tài)：P1:<$1000,0>;p2:<$50,1995>;

c1:<(fivewidgets)>;c2:<>p1(空)<$1000,0>1.全局狀態(tài)S0p1p1p1c2c1(空)2.全局狀態(tài)S1<$900,0><$900,0><$900,5><$50,1995><$50,1995><$50,2000><$50,2000>3.全局狀態(tài)S24.全局狀態(tài)S3p2p2p2p2c2c2c2c1c1c1(定單10，$100)，M(空)(空)(定單10，$100)，M(五個窗口部件)M=標(biāo)記信息)(定單10，$100)全局狀態(tài)最后狀態(tài)：P1:<$1000,0>;p2:全局狀態(tài)算法終止

-假設(shè)：一個進(jìn)程已經(jīng)收到了一個標(biāo)記信息，在有限的時間內(nèi)記錄了它的狀態(tài)，并在有限的時間里通過每個外出通道發(fā)送了標(biāo)記信息．

-若存在一條從進(jìn)程pi到進(jìn)程pj的信道和進(jìn)程的路徑，那么pi記錄它的狀態(tài)之后的有限時間內(nèi)pj將記錄它的狀態(tài)．

-進(jìn)程和通道圖是強(qiáng)連接的，因此在一些進(jìn)程記錄它的狀態(tài)之后的有限時間內(nèi)，所有進(jìn)程將記錄它們的狀態(tài)和節(jié)入通道的狀態(tài)。全局狀態(tài)算法終止全局狀態(tài)算法一致性

ei、ej分別為進(jìn)程pi、pj中的事件，且eiej則我們有:若ejCei

C，其中C為一個割集。即如果ej在pj記錄它的狀態(tài)之前發(fā)生，那么ei必須在pi記錄它的狀態(tài)之前發(fā)生.證明思路如下：

-i=j時，顯然成立

-i≠j時，反證法全局狀態(tài)算法一致性第3章時間和全局狀態(tài)簡介時鐘、事件和進(jìn)程狀態(tài)物理時鐘同步邏輯時間和邏輯時鐘全局狀態(tài)分布式調(diào)試小結(jié)第3章時間和全局狀態(tài)簡介分布式調(diào)試目的對系統(tǒng)實際執(zhí)行中的暫態(tài)作出判斷例子安全條件檢查

xi為進(jìn)程pi的變量(i=1,2,…)，安全條件為|xi-xj|≤控制系統(tǒng)所有閥門在某些時間是否全部處于開啟狀態(tài)分布式調(diào)試目的分布式調(diào)試方法監(jiān)控器進(jìn)程收集進(jìn)程狀態(tài)信息全局狀態(tài)謂詞的判斷

-可能的：存在一個一致的全局狀態(tài)S，H的一個線性化走向經(jīng)歷了這個全局狀態(tài)S，而且該S使得(s)為True。

-明確的：對于H的所有線性化走向L，存在L經(jīng)歷的一個一致的全局狀態(tài)S，而且該S使得(s)為True。分布式調(diào)試方法分布式調(diào)試觀察一致的全局狀態(tài)進(jìn)程的狀態(tài)信息附有向量時鐘值全局狀態(tài)的一致性判斷——CGS條件設(shè)S=(s1,s2,…,sN)是從監(jiān)控器進(jìn)程接收到的狀態(tài)信息中得出的全局狀態(tài)，V(si)是從