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

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

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

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

4、采取動(dòng)作，超時(shí)不做任何動(dòng)作 waiting until P sends (event; parameters), timeout=T on timeout； if no timeout occurred Successful response actions 64.1 基本知識(shí)3.超時(shí)處理器等待響應(yīng)T秒 若處理器在等待開(kāi)始后T秒內(nèi)沒(mé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.非即時(shí)通信 A和B同時(shí)向?qū)Ψ胶霸?他們都認(rèn)為是自己先喊話

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

6、是 即使可忽略其他影響，也不可能指望不同的機(jī)器會(huì)同時(shí)做出某些反應(yīng)。因?yàn)楝F(xiàn)代計(jì)算機(jī)是一個(gè)很復(fù)雜的系統(tǒng)：CPU競(jìng)爭(zhēng)、中斷、頁(yè)錯(cuò)誤等，執(zhí)行時(shí)間無(wú)法預(yù)料。結(jié)論：不可能在同一時(shí)刻觀察一個(gè)分布式系統(tǒng)的全局狀態(tài) 必須找到某種可以依賴的性質(zhì)：時(shí)間回溯因果相關(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é)點(diǎn)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é)點(diǎn)次序和消息傳遞次序的傳遞閉包：規(guī)則1：若e1pe2，則e1He2規(guī)則2：若e1me2，則e1He2規(guī)則3：若e1He2，且e2He3，則e1He3 e1He3表示存在1個(gè)事件因果鏈，使e1發(fā)生e3在之前 Note: H是一種偏序關(guān)系，即 存在e和e，二者之間無(wú)這種關(guān)系并發(fā)事件：若兩事件不能由H定序 在集合 X 上的二元關(guān)系 R 的傳遞閉包是包含 R 的 X 上的最小的傳遞關(guān)系。 124.2 因果關(guān)系Happens-before關(guān)系（H）規(guī)則1表述的是同一處理器上兩個(gè)事件

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

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

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

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

12、進(jìn)的Lamport時(shí)戳 事件標(biāo)號(hào)：時(shí)戳.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算法特點(diǎn)：分布、容錯(cuò)、系統(tǒng)開(kāi)銷小Lamport算法的迷人之處在于：任何進(jìn)程在發(fā)送消息前，先將自己的本地計(jì)數(shù)器累加1；接收進(jìn)程總是計(jì)算自己的本地計(jì)數(shù)器和接受到計(jì)數(shù)器中較大值加上1的結(jié)果timeP1P2P3e1e2e4e3e7e5e8e61.22.23.23.12.11.14.31.3204.2.2 向量時(shí)間戳Lamport時(shí)戳缺點(diǎn) 若e1He2，則 e1.TS e2.TS

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

14、發(fā) 現(xiàn)O已在P2上，故不知錯(cuò)在哪？P1P2P3M1On P2Where is O?遷移O到P2I dont knowM2Where is O?M3Error!224.2.2 向量時(shí)間戳錯(cuò)誤原因：違反因果序 P3請(qǐng)求O是發(fā)生在從P1遷移到P2之后，但該請(qǐng)求被處理是在遷移達(dá)到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é)點(diǎn)P上m2在m1之前被接收 例如，在上例中有： M1CM3，但 r(M3

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

16、在P2上，有6個(gè)事件須在e之前 在P3上，有4個(gè)事件須在e之前 在P4上，有2個(gè)事件須在e之前P1P2P31P4325431215416423132e254.2.2 向量時(shí)間戳向量時(shí)戳的意義在因果關(guān)系上，e1.VT V e2.VT表示e2發(fā)生在 e1及e1前所有的事件之后。更精確的說(shuō)，向量時(shí)鐘的次序?yàn)椋?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 向量時(shí)戳算法 my_VT：每個(gè)節(jié)點(diǎn)有局部的向量時(shí)戳 e.VT：每個(gè)事件有向量時(shí)戳 m.VT：每個(gè)msg有向量時(shí)戳 節(jié)點(diǎn)執(zhí)行一個(gè)事件時(shí)

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

18、74.2.2 向量時(shí)間戳算法性質(zhì) 1）若eH e，則e.VTVT e.VT 算法確保對(duì)于每個(gè)事件滿足： 若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均無(wú)路徑 2）e3在因果序上先于e1 即：e3.VTV e1.VT e1的前驅(qū)事件見(jiàn)方框P1P2P31000P433002300541344001300120001003500140000103642014201200132001100130012e2e3e1294.2.2 向量時(shí)戳因果序檢

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

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

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