程序算法設(shè)計分布式2第四章

1、1第4章分布式系統(tǒng)中的計算模型2006.12.152概述分布式系統(tǒng)計算模型的復(fù)雜性系統(tǒng)由并發(fā)執(zhí)行部件構(gòu)成系統(tǒng)中無全局時鐘必須捕捉系統(tǒng)部件可能的失效對策因果關(guān)系（Causality）一致狀態(tài)（Consistent states）全局狀態(tài)34.1 基本知識協(xié)議（Protocol）協(xié)議中的控制語句 1.Send（destination, action; parameters） destination：處理器抽象。實用中是通信實體的地址： 機器名，機器的端口號(即1個socket地址) action： 控制msg，希望接收者采取的動作 parameters：參數(shù)集合 假定： msg發(fā)送是無阻塞、可靠的

2、（語義類似于TCP套接字）； 有時假定較弱的msg傳遞層（等價于UDP）。TCP與UDP的區(qū)別：基于連接與無連接對系統(tǒng)資源的要求（TCP較多，UDP少） UDP程序結(jié)構(gòu)較簡單流模式與數(shù)據(jù)報模式 TCP保證數(shù)據(jù)正確性，UDP可能丟包 TCP保證數(shù)據(jù)順序，UDP不保證44.1 基本知識2.接收msg 接收msg可推廣至接收事件，引起事件的原因是： 外部msg、超時設(shè)定、內(nèi)部中斷 事件在處理前，一般是在緩沖區(qū)(如事件隊列)中，若一處理器想處理事件，它必須執(zhí)行一個聲明處理這些事件的線程。 例如，一個節(jié)點通過執(zhí)行下述代碼等待事件A1, A2,., An waiting for A1, A2,., An

3、：/聲明 A1（Source; parameters） Code to handle A1 . A1（Source; parameters） Code to handle An 當p執(zhí)行send(q, A1; parameters)且q執(zhí)行上述代碼時，q將最終處理由p發(fā)送的msg54.1 基本知識3.超時 當懷疑遠程處理器失效時，可通過超時檢測來判定：當T秒后仍未收到P的類型為event的msg時，執(zhí)行指定的動作 waiting until P sends (event; parameters), timeout=T on timeout timeout action僅當收到一個響應(yīng)msg時才

4、采取動作，超時不做任何動作 waiting until P sends (event; parameters), timeout=T on timeout； if no timeout occurred Successful response actions 64.1 基本知識3.超時處理器等待響應(yīng)T秒 若處理器在等待開始后T秒內(nèi)沒響應(yīng)，則等待結(jié)束，協(xié)議繼續(xù) waiting up to T seconds for (event; parameters) msgs Event: 74.2 因果關(guān)系 分布式系統(tǒng)為何缺乏全局的系統(tǒng)狀態(tài)？ 1.非即時通信 A和B同時向?qū)Ψ胶霸?他們都認為是自己先喊話

5、C聽到兩人是同時喊話 結(jié)論：系統(tǒng)的全局狀態(tài)依賴于觀察點 原因： 傳播延遲 網(wǎng)絡(luò)資源的競爭 丟失msg重發(fā) ACBd1 = d284.2 因果關(guān)系2.相對性影響 假設(shè)張三和李四決定使用同步時鐘來觀察全局狀態(tài)： 他們約定下午5點在某餐館會面，張三準時到達，但李四在一個接近光速的日光系統(tǒng)中游覽。 張三在等待李四1小時后離開餐館，而李四在自己的表到達5點時準時達到餐館，但他認為張三未達到。 因為大多數(shù)計算機的實際時鐘均存在漂移，故相對速度不同，時鐘同步仍然是一個問題。 結(jié)論：使用時間來同步不是一個可靠機制。94.2 因果關(guān)系3.中斷 假設(shè)張三和李四在同一起跑線上賽跑，信號為小旗，前兩個問題可以忽略，但

6、是 即使可忽略其他影響，也不可能指望不同的機器會同時做出某些反應(yīng)。因為現(xiàn)代計算機是一個很復(fù)雜的系統(tǒng)：CPU競爭、中斷、頁錯誤等，執(zhí)行時間無法預(yù)料。結(jié)論：不可能在同一時刻觀察一個分布式系統(tǒng)的全局狀態(tài) 必須找到某種可以依賴的性質(zhì)：時間回溯因果相關(guān)104.2 因果關(guān)系假設(shè)分布式系統(tǒng)構(gòu)成： PP1, P2,., Pn：處理器集合 E：全體事件的集合 EpE, Ep表示發(fā)生在p上的所有事件次序 e1e2： 事件e1發(fā)生e2在之前（亦記：e1e2） e1I e2：事件e1發(fā)生e2在之前，I為信息源定序 有些E中事件很容易定序： 發(fā)生在同一節(jié)點p上的事件滿足全序： 若e1,e2 Ep，則 e1pe2 或 e

7、2pe1 成立e1發(fā)送消息m,e2接收m，則e1me2114.2 因果關(guān)系Happens-before關(guān)系（H） 該關(guān)系是節(jié)點次序和消息傳遞次序的傳遞閉包：規(guī)則1：若e1pe2，則e1He2規(guī)則2：若e1me2，則e1He2規(guī)則3：若e1He2，且e2He3，則e1He3 e1He3表示存在1個事件因果鏈，使e1發(fā)生e3在之前 Note: H是一種偏序關(guān)系，即 存在e和e，二者之間無這種關(guān)系并發(fā)事件：若兩事件不能由H定序 在集合 X 上的二元關(guān)系 R 的傳遞閉包是包含 R 的 X 上的最小的傳遞關(guān)系。 124.2 因果關(guān)系Happens-before關(guān)系（H）規(guī)則1表述的是同一處理器上兩個事件

8、之間的因果關(guān)系；規(guī)則2表述了不同處理器上兩個事件之間的因果關(guān)系規(guī)則3闡述了傳遞律Note: Happens-Before關(guān)系完整表述了執(zhí)行中的因果關(guān)系。如果一個執(zhí)行中的事件按照其相對順序重新進行排序，而不改變他們的happens-before關(guān)系的話，那么其結(jié)果仍是一個執(zhí)行，并且對處理器而言，該執(zhí)行與原執(zhí)行并無區(qū)別。134.2 因果關(guān)系舉例1)因事件e1,e4和e7均發(fā)生在P1上，故：e1P1e4P1e72)因e1發(fā)送1個msg到e3，故：e1me3，類似地e5me83)應(yīng)用規(guī)則1和2得： e1He4He7，e1He3，e5He84)由H的傳遞閉包性質(zhì)得： e1He85)e1和e6是并發(fā)的：e

9、1和e6之間無 路徑 P1P2P3e1e2e4e3e7e5e8e6time144.2 因果關(guān)系HDAG 有時將Happens-before關(guān)系描述為一個有向無環(huán)圖頂點集VH是事件集E：eVH 當且僅當 eE 邊集EH：若(e1，e2)EH 當且僅當e1Pe2或e1me2 P1P2P3e1e2e4e3e7e5e8e6timee1e2e4e3e7e5e8e6154.2.1 Lamport時間戳系統(tǒng)有序性的重要性 若分布式系統(tǒng)中存在全局時鐘，則系統(tǒng)中的事件均可安排為全序。例如，可以更公平地分配系統(tǒng)資源。全序?qū)κ录挠绊懞陀蒆關(guān)系確定的偏序?qū)κ录挠绊懯且恢碌娜绾瓮ㄟ^H關(guān)系確定的偏序關(guān)系來建立一個“一

10、致”的全序關(guān)系？在H的DAG上拓撲排序 On the fly：Lamport提出了動態(tài)即時地建立全序算法 164.2.1 Lamport時間戳Lamport算法的思想 每個事件e有一個附加的時戳：e.TS 每個節(jié)點有一個局部時戳：my_TS 每個msg有一個附加時間戳：m.TS 節(jié)點執(zhí)行一個事件時，將自己的時戳賦給該事件； 節(jié)點發(fā)送msg時，將自己的時戳賦給所有發(fā)送的msg。 174.2.1 Lamport時間戳Lamport算法的實現(xiàn) Initially：my_TS=0; On event e： if ( e是接收消息m ) then my_TS = max ( m.TS, my_TS );

11、 /取msg時戳和節(jié)點時戳的較大者作為新時戳 my_TS+; e.TSmy_TS; /給事件e打時戳 if ( e是發(fā)送消息m ) then m.TSmy_TS; /給消息m打時戳184.2.1 Lamport時間戳Lamport算法賦值的時戳是因果相關(guān)的 若e1He2，則 e1.TS e2.TS 若e1Pe2或e1me2，則的e2時戳大于e1的時戳 在因果事件鏈上，每一事件的時戳大于其前驅(qū)事件的時戳問題：系統(tǒng)中所有事件已為全序？ 不同的事件可能有相同的時戳（并發(fā)事件）Lamport算法改進 因為并發(fā)事件的時戳可以任意指定先后 故可用節(jié)點地址作為時戳的低位194.2.1 Lamport時間戳改

12、進的Lamport時戳 事件標號：時戳.id 事件e8為4.3: my_TS=max(m.TS,my_TS) =max(3,1)=3 按字典序得全序： 1.1, 1.2, 1.3, 2.1, 2.2, 3.1, 3.2, 4.3算法特點：分布、容錯、系統(tǒng)開銷小Lamport算法的迷人之處在于：任何進程在發(fā)送消息前，先將自己的本地計數(shù)器累加1；接收進程總是計算自己的本地計數(shù)器和接受到計數(shù)器中較大值加上1的結(jié)果timeP1P2P3e1e2e4e3e7e5e8e61.22.23.23.12.11.14.31.3204.2.2 向量時間戳Lamport時戳缺點 若e1He2，則 e1.TS e2.TS

13、；反之不然。 例如：1.32.1，但是e6e4不成立 原因：并發(fā)事件之間的次序是任意的 不能通過事件的時戳判定兩事件之間是否是因果相關(guān)判定事件間因果關(guān)系的重要性 例子：違反因果關(guān)系檢測 在一個分布式對象系統(tǒng)中，為了負載平衡，對象是可移動的，對象在處理器之間遷移是為了獲得所需的調(diào)用的進程或資源。如下圖： 214.2.2 向量時戳1)P1持有對象O，決定遷移到P2 為獲取資源，P1將O裝配在消息 M1中發(fā)送給P22)P1收到P3訪問O的請求 P1將O的新地址P2放在消息M2 中通知P33)P3在M3中請求訪問P2的O 當M3達到P2時，O不可用，故 回答一個出錯消息。問題：當debug該系統(tǒng)時，會

14、發(fā) 現(xiàn)O已在P2上，故不知錯在哪？P1P2P3M1On P2Where is O?遷移O到P2I dont knowM2Where is O?M3Error!224.2.2 向量時間戳錯誤原因：違反因果序 P3請求O是發(fā)生在從P1遷移到P2之后，但該請求被處理是在遷移達到P2之前。形式地， 設(shè)：s(m)是發(fā)送m的事件 r(m)是接收m的事件 若s(m1)H s(m2)，則稱消息m1因果關(guān)系上先于m2，記做m1C m2 若m1 C m2，但 r(m2) P r(m1)，則違反“因果關(guān)系”： 即，若m1先于m2發(fā)送，但在同一節(jié)點P上m2在m1之前被接收 例如，在上例中有： M1CM3，但 r(M3

15、) P2 r(M1)234.2.2 向量時間戳違反因果序檢測定義：若時戳VT具有比較函數(shù)V滿足： e1H e2 iff e1.VTV e2.VT 則我們能夠檢測出是否違反因果關(guān)系VT性質(zhì) 1）因H 是偏序，故V 也是偏序； 2）因為必須知道在因果關(guān)系上每一節(jié)點中哪些事件是在事 件e之前，故e.VT中必須包含系統(tǒng)中每一個其它節(jié)點的 狀態(tài)。 這兩個性質(zhì)導(dǎo)致了向量時戳VT的引入244.2.2 向量時戳向量時戳VT VT是一個整數(shù)數(shù)組： e.VTi=k表示在節(jié)點i（或 Pi）上，因果關(guān)系上e之前有k 個事件（可能包括e自己）。 e.VT=(3,6,4,2)表示因果序： 在P1上，有3個事件須在e之前

16、在P2上，有6個事件須在e之前 在P3上，有4個事件須在e之前 在P4上，有2個事件須在e之前P1P2P31P4325431215416423132e254.2.2 向量時間戳向量時戳的意義在因果關(guān)系上，e1.VT V e2.VT表示e2發(fā)生在 e1及e1前所有的事件之后。更精確的說，向量時鐘的次序為： e1.VTV e2.VT iff e1.VTi e2.VTi,i=1,2,M e1.VTV e2.VT iff e1.VT VTe2.VT且e1.VTe2.VT 向量時戳算法 my_VT：每個節(jié)點有局部的向量時戳 e.VT：每個事件有向量時戳 m.VT：每個msg有向量時戳 節(jié)點執(zhí)行一個事件時

17、，將自己的時戳賦給該事件； 節(jié)點發(fā)送msg時，將自己的時戳賦給所有發(fā)送的msg。注意V, VT以及V之間的區(qū)別：V代表因果序，而VT代表時戳比較264.2.2 向量時間戳算法實現(xiàn) Initially：my_VT=0,0; On event e： if ( e是消息m的接收者 ) then for i=1 to M do /向量時戳的每個分量只增不減 my_VT i = max( m.VTi, my_VTi ); my_VT self +; /設(shè)變量self是本節(jié)點的名字 e.VTmy_VT; /給事件e打時戳 if ( e是消息m的發(fā)送者 ) then m.VTmy_VT; /給消息m打時戳2

18、74.2.2 向量時間戳算法性質(zhì) 1）若eH e，則e.VTVT e.VT 算法確保對于每個事件滿足： 若eP e或em e ，則e.VTVT e.VT 2）若eH e，則e.VTVT e.VT pf：若e和e 因果相關(guān)，則有eH e，即e.VTe2.VT1 e1.VT2e2.VT2 e1到e2及e2到e1均無路徑 2）e3在因果序上先于e1 即：e3.VTV e1.VT e1的前驅(qū)事件見方框P1P2P31000P433002300541344001300120001003500140000103642014201200132001100130012e2e3e1294.2.2 向量時戳因果序檢

19、測 1)消息時戳間比較 在P2上，先到達的M3的時戳為 （3,0,3），后到達的M1的時戳 為（1,0,0）。但是： (1,0,0)V (3,0,3) M1在因果序上先于M3 故M1后于M3到達違反因果序 2)消息時戳和局部時戳比較 當時戳為(1,0,0) 的M1到達P2 時，P2的時戳是(3,2,3)。但： (1,0,0)V (3,2,3) M1在因果序上應(yīng)先于(3,2,3)對應(yīng)的事件P1P2P3M1On P2Where is O?遷移O到P2I dont knowM2Where is O?M3Error!100201301001302303313323333324304.2.3 因果通信如

20、何保證通信不違反因果關(guān)系？ 處理器不能選擇msg達到的次序，但能抑制過早達到的msg來修正傳遞（指提交給應(yīng)用）次序。 FIFO通信（如TCP） 由msg傳遞協(xié)議棧里的一層負責確保FIFO通信ApplicationFIFO orderingDeliver in FIFO orderMsg passingassign timestamps314.2.3 因果通信FIFO通信 源處理器給每個發(fā)送的msg順序編號，目的處理器知道自己所收到的msg應(yīng)該有何順序的編號，若目的處理器收到一個編號為x的msg但未收到較小編號的msg時，則延遲傳遞直至能夠順序傳遞為止。因果通信 因果通信與FIFO通信類似 源：

21、附上時戳 目的地：延遲錯序msgMsg 達到次序X2deliverx2X5bufferx5X1deliverx1X4bufferx4X3deliverx3x4x5324.2.3 因果通信因果通信實現(xiàn)思想抑制從P發(fā)送的消息m，直至可斷定沒有來自于其它處理器上的消息m，使m V m.在每個節(jié)點P上： earliest1.M：存儲不同節(jié)點當前能夠傳遞的消息時戳的下界 earliestk表示在P上，對節(jié)點k能夠傳遞的msg的時戳的下界 blocked1.M：阻塞隊列數(shù)組，每個分量是一個隊列Alg. Causal Msg delivery 定義時戳1k： 若使用Lamport時戳，則1k1； 若用向量時戳，則1k(0,1,0,0)，kt