劉春漲　王麗穎　靳慶庚　郭瑞　劉金輝

摘 要：文中首先介紹了一致性算法的應(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 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2016）04-00-02

0 引 言

一致性在計(jì)算機(jī)以及自動控制領(lǐng)域運(yùn)用較多。例如數(shù)據(jù)中心的同步，生產(chǎn)線上機(jī)器人所執(zhí)行的動作協(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<

計(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] LAMPORT L.The partime Pariment[J]. ACM Transaction on Computer Systems，1998，16（2）：133-169.

[3] Lamport L. Paxos made simple[J]. ACM SIGACT News，2001，32 （4）：18-25.

[4]維基百科.Paxos算法[EB/OL]. http：//zh.wikipedia.org/zh-cn/Paxos%E7%AE% 97%E6%B3%95， [2014-09-15].

[5] Bitbucket[EB/OL]. https：//bitbucket.org/sciascid/libpaxos.git