第3章時間和全局狀態第3章時間和全局狀態簡介

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

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

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

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

-采用潤秒，與天文時間保持一致第3章時間和全局狀態簡介

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

時鐘、事件和進程狀態同步物理時鐘邏輯時間和邏輯時鐘全局狀態分布式調試小結同步物理時鐘外部同步采用權威的外部時間源時鐘Ci在范圍D內是準確的內部同步無外部權威時間源,系統內時鐘同步時鐘Ci在范圍D內是準確的關系

若P在范圍D內外部同步,則P在范圍2D內內部同步同步物理時時鐘Cristian方法(適用于只有有一臺機器器有WWV接收器)應用條件-存在時間服服務器，可可與外部時時間源同步步-消息往返時時間與系統統所要求的的精度相比比足夠短協議-進程p根據消息mr，mt計算消息往往返時間Tround-根據服務器器在mt中放置的時時間t設置時鐘為為：t+Tround/2mtp時間服務器Smr同步物理時時鐘Berkeley算法（沒有有WWV接收器）主機周期輪詢從屬機時間間主機通過消消息往返時時間估算從從屬機的時時間與Cristian方法類似主機計算容錯平均值值主機發送每每個從屬機機的調整量同步物理時時鐘網絡時間協協議(NTP)設計目標-可外部同步步使得跨Internet的用戶能精精確地與UTC同步-高可靠性可處理連接接丟失，采采用冗余服服務器、路路徑等-擴展性好大量用戶可可經常同步步，以抵消消漂移率的的影響-安全性強防止惡意或或偶然的干干擾同步物理時時鐘協議結構-層次結構-主服務器直直接與外部部UTC同步-同步子網可可重新配置置123233

同步子網結構示例第3章時間和和全局狀態態簡介時鐘、事件件和進程狀狀態物理時鐘同同步邏輯時間和和邏輯時鐘鐘全局狀態分布式調試試小結邏輯時間和和邏輯時鐘鐘邏輯時間的的引入分布式系統統中的物理理時鐘無法法完美同步步-消息傳輸延延時的不確確定性事件排序是是眾多分布布式算法的的基石-互斥算法-死鎖檢測算算法缺乏全局時時鐘-后發生的事事件有可能能賦予較早早的時間標標記邏輯時間和和邏輯時鐘鐘邏輯時鐘眾多應用只只要求所有有節點具有有相同時間，該時間不一定與實實際時間相相同Lamport(1978)指出：不進進行交互的的兩個進程程之間不需需要時鐘同同步對于不需要要交互的兩兩個進程而而言，即使使沒有時鐘鐘同步，也也無法察覺覺，更不會會產生問題題。所有的進程程需要在時時間的發生順序上達成一致如make程序邏輯時間和和邏輯時鐘鐘事件排序“系統i中的事件a發生在系統統j中的事件b之前”是不不準確的-事件發生和和觀察之間間存在時延延-不同系統中中的時鐘存存在偏差時間戳(Lamport1978)-用于分布式式系統中的的事件排序序-與物理時鐘鐘無關-實用高效，，應用廣泛泛邏輯時間和和邏輯時鐘鐘兩個基本事事實-同一進程中中的兩個事事件存在關關系“i”-任一消息的的發送事件件發生在該該消息的接接收事件之之前“發生在先先(happens-before)””關系定義-若存在進程程pi滿足eie’，則ee’-對于任一消消息m，存在send(m)recv(m)-若事件滿足足ee’和e’e’’，則ee’’并發關系定定義XY與YX均不成立，，則稱事件件X、Y是并發的，，表示為X||Y邏輯時間和和邏輯時鐘鐘事件排序示示例-bc，cd和df成立-bf與ef均成立-事件b和e無法比較，，即b||ep1p2p3abcdefm1m2物理時間邏輯時間和和邏輯時鐘鐘Lamport時鐘機制-進程維護一一個單調遞遞增的軟件件計數器，，充當邏輯輯時鐘-用邏輯時鐘鐘為事件添添加時間戳戳-按事件的時時間戳大小小為時間排排序邏輯時鐘修修改規則-進程pi發出事件前前，邏輯時時鐘Li:=Li+1-進程pi發送消息m時，在m中添加時間間戳t=Li-進程pj在接收(m,t)時，更新Li:=max(Lj,t)+1，給s事件件recv(m)添加時間戳戳后發送給給應用程序序abcdefm1m2213451p1p2p3物理時間邏輯時間和和邏輯時鐘鐘Lamport時鐘示例(一)abL(a)<L(b)L(e)<L(b)be邏輯時間和和邏輯時鐘鐘(a)三個不同速速率的時鐘鐘(b)Lamport算法校正時時鐘Lamport時鐘示例(二)邏輯時間和和邏輯時鐘鐘Lamport時鐘練習假設系統中中只存在消消息發送和和接收事件件，如下圖圖所示，請請給出事件件a-g的邏輯時鐘鐘。邏輯時鐘0邏輯時間和和邏輯時鐘鐘Lamport時鐘練習答案邏輯時鐘：：0144328657579邏輯時間間和邏輯輯時鐘不同進程產生生的消息息可能具具有相同數值值的Lamport時間戳物理時間邏輯時間間和邏輯輯時鐘基于Lamport時間戳的的事件排排序---總結算法不依依賴于事事件發生生的真實實時間與真實物物理時間間中事件件的發生生順序可可能不一一致基于Lamport時間戳的的排序中中，在時時刻(2,1)發生的事事件發生生比在時時刻（2，2）發生的事事件要早早，然而而在真實實物理時時間中可可能恰好好相反。。邏輯時間間和邏輯輯時鐘Lamport時鐘不具具備性質質：若L(A)<L(B)則AB沒有捕獲獲事件的的因果關關系節點B發布一篇篇文章并并傳送給給節點A和C。節點A就此發表表評論并并傳送給給節點B和C。araarr我們無法法準確確確定r的先后關關系：C(a)<C(r)ara是節點A發布的文文章r是節點B對文章a的評論全序邏輯輯時鐘引入進程程標示符符創建事事件的全全序關系系若e、e’分別為進進程pi、pj中發生的的事件，，則其全全局邏輯輯時間戳戳分別為為(Ti,i)、(Tj,j)。ee’Ti<Tj||Ti=Tj&&i<j系統中各各個事件件Lamport時間戳均均不相同同向量時鐘鐘克服Lamport時鐘的缺缺點：若L(e)<L(e’)不能推出出則ee’。每個進程程維護它它自己的的向量時時鐘ViVC1:初始情況況下，Vi[j]=0,i,j=1,2,...N.VC2:在pi給事件加加時間戳戳之前，，設置Vi[i]=Vi[i]+1。VC3:pi在它發送送的每個個消息中中包括t＝Vi。VC4：當pi接收到消消息中的的時間戳戳t時，設置置Vi[j]=max(Vi[j],t[j]),j=1,2,...,N。向量時鐘鐘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向量時鐘鐘第3章時間間和全局局狀態簡介時鐘、事事件和進進程狀態態同步物理理時鐘邏輯時間間和邏輯輯時鐘全局狀態態分布式調調試小結全局狀態態觀察全局局狀態的的必要性性分布式無無用單元元的收集集-基于對象象的引用用計數-必須考慮慮信道和和進程的的狀態分布式死死鎖檢測測觀察系統統中的““等待””關系圖圖中是否否存在循循環p1消息無用對象對象引用p2等待等待p1p2分布式終終止檢測測與進程的的狀態有有關——“主動”或“被動”分布式調調試需要收集集同一時時刻系統統中分布布式變量量的數值值全局狀態態激活被動的p1p2被動的全局狀態態全局狀態態和一致致割集觀察進程程集的狀狀態——全局狀態態非常困困難根源：缺缺乏全局局時間進程的歷歷史hi=<ei0,ei1,ei2…>進程歷史史的有限限前綴hik=<ei0,ei1,…,eik>全局歷史史——單個進程程歷史的的并集H=h1h2…hN全局狀態進程狀態sik:進程pi在第k個事件發生之之前的狀態全局狀態——單個進程狀態態的集合S=(s1,s2,…sN)割集——系統全局歷史史的子集C=<h1c1,h2c2…h3c3>割集的一致性性割集C是一致的:對于所有事件件eC,fefC全局狀態割集示例m1m2p1p2物理時間e10一致的割集不一致的割集e11e12e13e20e21e22全局狀態一致的全局狀狀態——對應于一致割割集的狀態S0S1S2…走向(run)-全局歷史中所所有事件的全全序-與每個本地歷歷史順序一致致-不是所有的走走向都經歷一一致的全局狀狀態線性化走向-所有的線性化化走向只經歷歷一致的全局局狀態-若存在一個經經過S和S’的線性化走向向，則狀態S’是從S可達全局狀態Chandy和Lamport的“快照”算算法目的捕獲一致的全全局狀態假設-進程和通道均均不會出現故故障-單向通道，提提供FIFO順序的消息傳傳遞-進程之間存在在全連通關系系-任一進程可在在任一時間開開始全局拍照照-拍照時，進程程可繼續執行行，并發送和和接收消息全局狀態算法基本思想想-接入通道+外出通道-進程狀態+通道狀態-標記消息標記接收規則則：強制進程在在記錄下自己己的狀態之后后但在它們發發送其他消息息前發送一個個標記。標記發送規則則：強制沒有記記錄狀態的進進程去記錄狀狀態全局狀態算法偽碼(一)進程pi的標記接收規規則pi接收通道c上的標記消息息：if(pi還沒有記錄它它的狀態)pi記錄它的進程程狀態；將c的狀態記成空空集；開始記錄從其其他接入通道道上到達的消消息elsepi把c的狀態記錄到到從保留它的的狀態以來它它在c上接收到的消消息集合中endif全局狀態算法偽碼(二)進程pi的標記發送規規則在pi記錄了它的狀狀態之后，對對每個外出通通道c:(在pi從c上發送任何其其他消息前)pi在c上發送一個消消息標記全局狀態算法示例-兩個進程p1、p2進行交易，每每件10$-初始狀態進程p2已經收到5件商品的定單單，它將馬上上分發給p1p1p2c2c1帳戶窗口部件$1000(none)帳戶窗口部件$502000全局狀態最后狀態：P1:<$1000,0>;p2:<$50,1995>;c1:<(fivewidgets)>;c2:<>p1(空)<$1000,0>1.全局狀態S0p1p1p1c2c1(空)2.全局狀態S1<$900,0><$900,0><$900,5><$50,1995><$50,1995><$50,2000><$50,2000>3.全局狀態S24.全局狀態S3p2p2p2p2c2c2c2c1c1c1(定單10，$100)，M(空)(空)(定單10，$100)，M(五個窗口部件)M=標記信息)(定單10，$100)全局局狀狀態態算法法終終止止-假設設：：一一個個進進程程已已經經收收到到了了一一個個標標記記信信息息，，在在有有限限的的時時間間內內記記錄錄了了它它的的狀狀態態，，并并在在有有限限的的時時間間里里通通過過每每個個外外出出通通道道發發送送了了標標記記信信息息．．-若存存在在一一條條從從進進程程pi到進進程程pj的信信道道和和進進程程的的路路徑徑，，那那么么pi記錄錄它它的的狀狀態態之之后后的的有有限限時時間間內內pj將記記錄錄它它的的狀狀態態．．-進程程和和通通道道圖圖是是強強連連接接的的，，因因此此在在一一些些進進程程記記錄錄它它的的狀狀態態之之后后的的有有限限時時間間內內，，所所有有進進程程將將記記錄錄它它們們的的狀狀態態和和節節入入通通道道的的狀狀態態。。全局局狀狀態態算法法一一致致性性ei、ej分別別為為進進程程pi、pj中的的事事件件，，且且eiej則我我們們有有:若ejCeiC，其其中中C為一一個個割割集集。。即即如如果果ej在pj記錄錄它它的的狀狀態態之之前前發發生生，，那那么么ei必須須在在pi記錄錄它它的的狀狀態態之之前前發發生生.證明明思思路路如如下下：：-i=j時，，顯顯然然成成立立-i≠≠j時，，反反證證法法第3章時時間間和和全全局局狀狀態態簡介介時鐘鐘、、事事件件和和進進程程狀狀態態物理理時時鐘鐘同同步步邏輯輯時時間間和和邏邏輯輯時時鐘鐘全局局狀狀態態分布布式式調調試試小結結分布布式式調調試試目的的對系系統統實實際際執執行行中中的的暫暫態態作作出出判判斷斷例子子安全全條條件件檢檢查查xi為進進程程pi的變變量量(i=1,2,…)，安安全全條條件件為為|xi-xj|≤≤控制制系系統統所有有閥閥門門在在某某些些時時間間是是否否全全部部處處于于開開啟啟狀狀態態分布布式式調調試試方法法監控控器器進進程程收集集進進程程狀狀態態信信息息全局局狀狀態態謂謂詞詞的的判判斷斷-可能能的的：存在在一一個個一一致致的的全全局局狀狀態態S，H的一一個個線線性性化化走走向向經經歷歷了了這這個個全全局局狀狀態態S，而而且且該該S使得得(s)為True。-明確確的的：對于于H的所所有有線線性性化化走走向向L，存存在在L經歷歷的的一一個個一一致致的的全全局局狀狀態態S，而而且且該該S使得得(s)為True。分布布式式調調試試觀察察一一致致的的全全局局狀狀態態進程程的的狀狀態態信信息息附附有有向向量量時時鐘鐘值值全局局狀狀態態的的一一致致性性判判斷斷———CGS條件件設S=(s1,s2,…,sN)是從從監監控控器器進進程程接接收收到到的的狀狀態態信信息息中中得得出出的的全全局局狀狀態態，，V(si)是從從pi接收收到到的的狀狀態態si的向向量量時時間間戳戳，，則則S是一一致致的的全全局局狀狀態態當當且且僅僅當當：：V(si)[i]>=V(sj)[i](i,j=1,2,……,N)即若若一一個個進進程程的的狀狀態態依依賴賴于于另另一一個個進進程程的的狀狀態態，，則則全全局局狀狀態態也也包包含含了了它它所所以以來來的的狀狀態態。。分布布式式調調試試全局局狀狀態態示示例例m1m2p1p2物理時間

CutC1(1,0)(2,0)(4,3)(2,1)(2,2)(2,3)(3,0)x1=1x1=100x1=105x2=100x2=95x2=90x1=90CutC2Sij=在進程１發生事件i以及在進程２發生事件j之后的全局狀態S00S10S20S21S30S31S32S22S23S33S43層次01234567分布布式式調調試試一致致全全局局狀狀態態網網格格分布布式式調調試試判定定可可能能的的從初初始始狀狀態態考考試試，，遍遍歷歷可可達達狀狀態態的的網網格格。。L:=0;States:={(s01,s02,……,s0N)};while(對所所有有可可能能的的S∈∈States，(s)=False)L:=L+1;Reachable:={S’’:H中從一一些S∈States可到達達的狀狀態∧∧level(S’)=L};States:=Reachable;endwhile輸出““可能能的”;

?

–層次012345FFFFTFF=((s)=False);T=((s)=True)分布式式調試試值判定定示例例在第５５層的的狀態態為True＝》明確的的在第第５層層的狀狀態為為False＝》可能的的分布式式調試試異步系系統開銷很很大，，需要要作O(kＮ)次比較較。同步系系統物理時時鐘：：|Ci(t)－Cj(t)|<D，即在在范圍圍D內同步步。同步系系統中中的算算法改改進消息中中同時時攜帶帶物理理時間間戳和和向量量時間間戳測試條條件V(si)[i]≧≧V(si)[i]，且si和sj能在同同一時時間發發生第3章時時間和和全局局狀態態簡介時鐘、、事件件和進進程狀狀態物理時時鐘同同步邏輯時時間和和邏輯輯時鐘鐘全局狀狀態分布式式調試試小結小結時鐘偏偏移和和時鐘鐘漂移移物理時時鐘同同步Cristian方法Berkeley方法網絡時時間協協議邏輯時時間發生在在先關關系Lamport時間戳戳向量時時鐘小結全局狀狀態一致割割集，，一致致全局局狀態態“快照照”算算法分布式式調試試狀態收收集判定可可能的的和明確的的作業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?作業a,b,andcareeventsandnotwoeventsbelongtothesameprocess.Proveordisprove(givecounter-example)thefollowing:(a)aisconcurrentwithbandbisbeforecimpliesthataisbeforec.(b)aisconcurrentwithbandbisconcurrentwithcimpliesthataisconcurrentwithc.9、靜夜四無鄰鄰，荒居舊業業貧。。1月-231月-23Sunday,January1,202310、雨中中黃葉葉樹，，燈下下白頭頭人。。。13:01:1513:01:1513:011/1/20231:01:15PM11、以我獨獨沈久，，愧君相相見頻。。。1月-2313:01:1513:01Jan-2301-Jan-2312、故人江海別別，幾度隔山山川。。13:01:1513:01:1513:01Sunday,January1,202313、乍乍見見翻翻疑疑夢夢，，相相悲悲各各問問年年。。。。1月月-231月月-2313:01:1513:01:15January1,202314、他鄉鄉生白白發，，舊國國見青青山。。。01一一月月20231:01:15下下午13:01:151月-2315、比不了了得就不不比，得得不到的的就不要要。。。一月231:01下午午1月-2313:01January1,202316、行動出成成果，工作作出財富。。。2023/1/113:01:1513:01:1601January202317、做前，能夠夠環視四周；；做時，你只只能或者最好好沿著以腳為為起點的射線線向前。。1:01:16下午1:01下下午13:01:161月-239、沒有有失敗敗，只只有暫暫時停停止成成功！！。1月-231月-23Sunday,January1,202310、很多事事情努力力了未必必有結果果，但是是不努力力卻什么么改變也也沒有。。。13:01:1613:01:1613:011/1/20231:01:16PM11、成功就是是日復一日日那一點點點小小努力力的積累。。。1月-2313:01:1613:01Jan-2301-Jan-2312、世間成事事，不求其其絕對圓滿滿，留一份份不足，可可得無限完完美。。13:01:1613:01:1613:01Sunday,January1,202313、不知知香積積寺，