基于Paxos算法的分布式計(jì)算模型探究

劉春漲王麗穎靳慶庚郭瑞劉金輝摘要:文中首先介紹了一致性算法的應(yīng)用狀況,重點(diǎn)結(jié)合Paxos算法對并行計(jì)算的方法進(jìn)行了探究。分析了計(jì)算機(jī)的計(jì)算問題,進(jìn)行了問題抽象,設(shè)計(jì)了一個(gè)基于Paxos算法的分布式計(jì)算的原型系統(tǒng)。并通過仿真實(shí)驗(yàn)驗(yàn)證了方案的可行性。關(guān)鍵詞:Paxos算法;并行計(jì)算;計(jì)算方法;分布式計(jì)算:TP301.61:A:2095-1302（2016）04-00-020引言一致性在計(jì)算機(jī)以及自動(dòng)控制領(lǐng)域運(yùn)用較多。例如數(shù)據(jù)中心的同步,生產(chǎn)線上機(jī)器人所執(zhí)行的動(dòng)作協(xié)調(diào)等,一致性在該領(lǐng)域的作用可以概括為解決合作問題[1]。一致性產(chǎn)生于合作,即個(gè)體與其他個(gè)體之間的協(xié)作。計(jì)算機(jī)中,一個(gè)集群中的電腦要一起合作完成一個(gè)任務(wù),可以通過消息傳遞和共享內(nèi)存兩種方式完成。Paxos算法是一種采用消息傳遞方式實(shí)現(xiàn)一致性的算法。Paxos算法就是通過前者獲知全局消息的算法。Paxos算法的輸入是各個(gè)計(jì)算機(jī)的全局請求(即整個(gè)集群知道的消息),輸出是請求的全局執(zhí)行順序。假如各個(gè)計(jì)算機(jī)內(nèi)對各消息的解釋代碼都相同,那么,通過執(zhí)行帶編號的全局請求,各個(gè)機(jī)器就可以得到同樣的結(jié)果[2-4]。本文設(shè)計(jì)了一種基于Paxos算法的分布式計(jì)算的計(jì)算模型,并進(jìn)行了系統(tǒng)仿真設(shè)計(jì)。1相關(guān)工作1.1提升集群的CPU利用率以及計(jì)算問題的本質(zhì)定義計(jì)算的數(shù)學(xué)模型TR(A,B,C,.......,Z0),Z0代表匯總計(jì)算;A,B,C,...代表可拆解的最小計(jì)算單元(即各個(gè)計(jì)算單元之間如A,B之間不存在順序)。在單臺單處理器機(jī)器上,設(shè)最小單元的平均計(jì)算時(shí)間為w,最小計(jì)算單元數(shù)為n,匯總耗時(shí)為t。則執(zhí)行TR模型耗時(shí)cost_sig為nw+t。在多臺單處理器機(jī)器上,假設(shè)計(jì)算機(jī)數(shù)目為n,每臺機(jī)器上分配到的計(jì)算單元數(shù)為k(k<<=""<p>計(jì)算問題即計(jì)算過程以及得到結(jié)果的一系列過程,可以看成一顆多叉樹,父節(jié)點(diǎn)可由其子節(jié)點(diǎn)進(jìn)行運(yùn)算得到,其所耗掉的時(shí)間為其子節(jié)點(diǎn)數(shù)g乘上平均計(jì)算時(shí)間w。整體的計(jì)算時(shí)間由樹的深度h決定（假設(shè)通信開銷為常量c）。則一個(gè)計(jì)算程序的耗時(shí)為:。在單臺單處理器的機(jī)器上TR是線性執(zhí)行的,將其也看成一棵樹,則樹的深度為節(jié)點(diǎn)數(shù)。而在多臺單處理器上,樹的深度比前面的單臺單處理器情況來的淺,故能起到加速執(zhí)行的作用。計(jì)算問題的優(yōu)化在一定程度上可以看成是提升CPU的利用率。如何利用Paxos算法來使計(jì)算機(jī)集群的CPU資源得到充分利用,本文認(rèn)為可以遵循以下兩個(gè)原則：(1)設(shè)計(jì)出計(jì)算單元耗時(shí)大于通信開銷的算法。(2)從計(jì)算樹上進(jìn)行并行算法的調(diào)度研究。從計(jì)算樹上進(jìn)行并行算法的調(diào)度研究之前,若先建立計(jì)算樹到物理機(jī)器的映射,則較快的并行算法的設(shè)計(jì)問題可以轉(zhuǎn)化為計(jì)算單元調(diào)度使得時(shí)間代價(jià)最小的問題。進(jìn)一步將計(jì)算問題進(jìn)行抽象,抽象為計(jì)算樹的葉節(jié)點(diǎn)著色問題,即每次只能在葉節(jié)點(diǎn)著色,一次只能著色1～n(機(jī)器數(shù))個(gè)葉節(jié)點(diǎn),每次著色完畢后記錄被著色的葉節(jié)點(diǎn),當(dāng)樹的中間節(jié)點(diǎn)的葉節(jié)點(diǎn)數(shù)均被著色后,中間節(jié)點(diǎn)變?yōu)樾碌娜~節(jié)點(diǎn)。直至根節(jié)點(diǎn)時(shí),計(jì)算z0以及著色的次數(shù)k,并保證k的取值最小。假設(shè)設(shè)計(jì)得到的算法是function(),該函數(shù)記錄了第i次著色時(shí)著色的葉子節(jié)點(diǎn)以及相關(guān)細(xì)節(jié)。Paxos算法中一個(gè)決議應(yīng)對應(yīng)一次著色,故通過的決議應(yīng)當(dāng)包括被著色的葉子節(jié)點(diǎn)信息(即要執(zhí)行的計(jì)算單元）。假如不考慮單點(diǎn)故障問題,認(rèn)為所有計(jì)算機(jī)均能正常工作,我們便可以用hash方法來分配這些計(jì)算單元給集群中不同的機(jī)器。當(dāng)所有節(jié)點(diǎn)執(zhí)行完成一條協(xié)議后便可以執(zhí)行下一次著色,直至根節(jié)點(diǎn),便可輸出最終的計(jì)算結(jié)果。所以應(yīng)用Paxos算法解決并行運(yùn)算之前需要將計(jì)算單元進(jìn)行分配編號,并將編號以及計(jì)算單元的內(nèi)容發(fā)送給集群中的各個(gè)機(jī)器,這樣便可以讓計(jì)算機(jī)在通過決議后經(jīng)過哈希函數(shù)(即起到過濾掉不屬于本機(jī)器的計(jì)算單元的作用）調(diào)用相應(yīng)的計(jì)算單元進(jìn)行計(jì)算,最終實(shí)現(xiàn)并行計(jì)算任務(wù)。綜上,運(yùn)用Paxos解決并行計(jì)算問題的解題步驟如下：(1)設(shè)計(jì)出計(jì)算單元耗時(shí)大于通信開銷的算法;(2)設(shè)計(jì)解釋器來解釋各服務(wù)器所能執(zhí)行的編號以及翻譯該編號的計(jì)算流程;（3)將計(jì)算問題的各個(gè)步驟內(nèi)聚成計(jì)算單元,得到計(jì)算單元的計(jì)算樹（循環(huán)問題單獨(dú)看成一個(gè)計(jì)算單元),將這些計(jì)算單元以及編號分給各個(gè)計(jì)算服務(wù)器,執(zhí)行著色算法f;(4）從算法f中得到著色過程,將這些決議提交給Paxos算法中的client。修改Paxos算法使其能將每次著色的消息通知給所有計(jì)算機(jī)。沒有一致性這一特性的保障將使得CPU利用率降低；（5)各個(gè)計(jì)算服務(wù)器利用hash值來判斷本次決議自己所負(fù)責(zé)執(zhí)行的計(jì)算單元;(6）輸出計(jì)算的結(jié)果。1.2基于Paxos算法的分布式計(jì)算模型實(shí)驗(yàn)環(huán)境與比較方案:libpaxos,不帶線程的計(jì)算方法1,帶線程的計(jì)算方法2,實(shí)驗(yàn)組用3臺計(jì)算服務(wù)器進(jìn)行協(xié)作計(jì)算,對照組用一臺。比較實(shí)驗(yàn)組和對照組得到結(jié)果所耗時(shí)間。編程實(shí)現(xiàn)如下模型,在圖1所示的基于Paxos算法的分布式計(jì)算模型的解釋器中加入上述策略。2結(jié)語通過實(shí)驗(yàn)驗(yàn)證,本文所設(shè)計(jì)的進(jìn)行計(jì)算的原型系統(tǒng)方案是可行的。在大量多線程處理問題上實(shí)驗(yàn)組比對照組表現(xiàn)好,但在多重循環(huán)嵌套的控制結(jié)構(gòu)表現(xiàn)并不優(yōu)于對照組。參考文獻(xiàn)[1]熊永陽.分布式一致性問題研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2014.[2]LAMPORTL.ThepartimePariment[J].ACMTransactiononComputerSystems,1998,16(2):133-169.[3]LamportL.Paxosmadesimple[J].ACMSIGACTNews,2001,32(4):18-25.[4]維基百科.Paxos算