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

摘 要：文中首先介紹了一致性算法的應(yīng)用狀況，重點(diǎn)結(jié)合Paxos算法對(duì)并行計(jì)算的方法進(jìn)行了探究。分析了計(jì)算機(jī)的計(jì)算問(wèn)題，進(jìn)行了問(wèn)題抽象，設(shè)計(jì)了一個(gè)基于Paxos算法的分布式計(jì)算的原型系統(tǒng)。并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了方案的可行性。

關(guān)鍵詞：Paxos算法；并行計(jì)算；計(jì)算方法；分布式計(jì)算

中圖分類號(hào)：TP301.61 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2016）04-00-02

0 引 言

一致性在計(jì)算機(jī)以及自動(dòng)控制領(lǐng)域運(yùn)用較多。例如數(shù)據(jù)中心的同步，生產(chǎn)線上機(jī)器人所執(zhí)行的動(dòng)作協(xié)調(diào)等，一致性在該領(lǐng)域的作用可以概括為解決合作問(wèn)題[1]。一致性產(chǎn)生于合作，即個(gè)體與其他個(gè)體之間的協(xié)作。計(jì)算機(jī)中，一個(gè)集群中的電腦要一起合作完成一個(gè)任務(wù)，可以通過(guò)消息傳遞和共享內(nèi)存兩種方式完成。Paxos算法是一種采用消息傳遞方式實(shí)現(xiàn)一致性的算法。

Paxos算法就是通過(guò)前者獲知全局消息的算法。Paxos算法的輸入是各個(gè)計(jì)算機(jī)的全局請(qǐng)求（即整個(gè)集群知道的消息），輸出是請(qǐng)求的全局執(zhí)行順序。假如各個(gè)計(jì)算機(jī)內(nèi)對(duì)各消息的解釋代碼都相同，那么，通過(guò)執(zhí)行帶編號(hào)的全局請(qǐng)求，各個(gè)機(jī)器就可以得到同樣的結(jié)果[2-4]。

本文設(shè)計(jì)了一種基于Paxos算法的分布式計(jì)算的計(jì)算模型，并進(jìn)行了系統(tǒng)仿真設(shè)計(jì)。

1 相關(guān)工作

1.1 提升集群的CPU利用率以及計(jì)算問(wèn)題的本質(zhì)

定義計(jì)算的數(shù)學(xué)模型TR（A，B，C，.......，Z0），Z0代表匯總計(jì)算；A，B，C，...代表可拆解的最小計(jì)算單元（即各個(gè)計(jì)算單元之間如A，B之間不存在順序）。

在單臺(tái)單處理器機(jī)器上，設(shè)最小單元的平均計(jì)算時(shí)間為w，最小計(jì)算單元數(shù)為n，匯總耗時(shí)為t。則執(zhí)行TR模型耗時(shí)cost_sig為nw+t。

在多臺(tái)單處理器機(jī)器上，假設(shè)計(jì)算機(jī)數(shù)目為n，每臺(tái)機(jī)器上分配到的計(jì)算單元數(shù)為k（k<

計(jì)算問(wèn)題即計(jì)算過(guò)程以及得到結(jié)果的一系列過(guò)程，可以看成一顆多叉樹(shù)，父節(jié)點(diǎn)可由其子節(jié)點(diǎn)進(jìn)行運(yùn)算得到，其所耗掉的時(shí)間為其子節(jié)點(diǎn)數(shù)g乘上平均計(jì)算時(shí)間w。整體的計(jì)算時(shí)間由樹(shù)的深度h決定（假設(shè)通信開(kāi)銷為常量c）。則一個(gè)計(jì)算程序的耗時(shí)為：。在單臺(tái)單處理器的機(jī)器上TR是線性執(zhí)行的，將其也看成一棵樹(shù)，則樹(shù)的深度為節(jié)點(diǎn)數(shù)。而在多臺(tái)單處理器上，樹(shù)的深度比前面的單臺(tái)單處理器情況來(lái)的淺，故能起到加速執(zhí)行的作用。

計(jì)算問(wèn)題的優(yōu)化在一定程度上可以看成是提升CPU的利用率。如何利用Paxos算法來(lái)使計(jì)算機(jī)集群的CPU資源得到充分利用，本文認(rèn)為可以遵循以下兩個(gè)原則：

（1）設(shè)計(jì)出計(jì)算單元耗時(shí)大于通信開(kāi)銷的算法。

（2）從計(jì)算樹(shù)上進(jìn)行并行算法的調(diào)度研究。

從計(jì)算樹(shù)上進(jìn)行并行算法的調(diào)度研究之前，若先建立計(jì)算樹(shù)到物理機(jī)器的映射，則較快的并行算法的設(shè)計(jì)問(wèn)題可以轉(zhuǎn)化為計(jì)算單元調(diào)度使得時(shí)間代價(jià)最小的問(wèn)題。

進(jìn)一步將計(jì)算問(wèn)題進(jìn)行抽象，抽象為計(jì)算樹(shù)的葉節(jié)點(diǎn)著色問(wèn)題，即每次只能在葉節(jié)點(diǎn)著色，一次只能著色1～n（機(jī)器數(shù)）個(gè)葉節(jié)點(diǎn)，每次著色完畢后記錄被著色的葉節(jié)點(diǎn)，當(dāng)樹(shù)的中間節(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)對(duì)應(yīng)一次著色，故通過(guò)的決議應(yīng)當(dāng)包括被著色的葉子節(jié)點(diǎn)信息（即要執(zhí)行的計(jì)算單元）。假如不考慮單點(diǎn)故障問(wèn)題，認(rèn)為所有計(jì)算機(jī)均能正常工作，我們便可以用hash方法來(lái)分配這些計(jì)算單元給集群中不同的機(jī)器。當(dāng)所有節(jié)點(diǎn)執(zhí)行完成一條協(xié)議后便可以執(zhí)行下一次著色，直至根節(jié)點(diǎn)，便可輸出最終的計(jì)算結(jié)果。所以應(yīng)用Paxos算法解決并行運(yùn)算之前需要將計(jì)算單元進(jìn)行分配編號(hào)，并將編號(hào)以及計(jì)算單元的內(nèi)容發(fā)送給集群中的各個(gè)機(jī)器，這樣便可以讓計(jì)算機(jī)在通過(guò)決議后經(jīng)過(guò)哈希函數(shù)（即起到過(guò)濾掉不屬于本機(jī)器的計(jì)算單元的作用）調(diào)用相應(yīng)的計(jì)算單元進(jìn)行計(jì)算，最終實(shí)現(xiàn)并行計(jì)算任務(wù)。

綜上，運(yùn)用Paxos解決并行計(jì)算問(wèn)題的解題步驟如下：

（1）設(shè)計(jì)出計(jì)算單元耗時(shí)大于通信開(kāi)銷的算法；

（2）設(shè)計(jì)解釋器來(lái)解釋各服務(wù)器所能執(zhí)行的編號(hào)以及翻譯該編號(hào)的計(jì)算流程；

（3）將計(jì)算問(wèn)題的各個(gè)步驟內(nèi)聚成計(jì)算單元，得到計(jì)算單元的計(jì)算樹(shù)（循環(huán)問(wèn)題單獨(dú)看成一個(gè)計(jì)算單元），將這些計(jì)算單元以及編號(hào)分給各個(gè)計(jì)算服務(wù)器，執(zhí)行著色算法f；

（4）從算法f中得到著色過(guò)程，將這些決議提交給Paxos算法中的client。修改Paxos算法使其能將每次著色的消息通知給所有計(jì)算機(jī)。沒(méi)有一致性這一特性的保障將使得CPU利用率降低；

（5）各個(gè)計(jì)算服務(wù)器利用hash值來(lái)判斷本次決議自己所負(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臺(tái)計(jì)算服務(wù)器進(jìn)行協(xié)作計(jì)算，對(duì)照組用一臺(tái)。比較實(shí)驗(yàn)組和對(duì)照組得到結(jié)果所耗時(shí)間。

編程實(shí)現(xiàn)如下模型，在圖1所示的基于Paxos算法的分布式計(jì)算模型的解釋器中加入上述策略。

2 結(jié) 語(yǔ)

通過(guò)實(shí)驗(yàn)驗(yàn)證，本文所設(shè)計(jì)的進(jìn)行計(jì)算的原型系統(tǒng)方案是可行的。在大量多線程處理問(wèn)題上實(shí)驗(yàn)組比對(duì)照組表現(xiàn)好，但在多重循環(huán)嵌套的控制結(jié)構(gòu)表現(xiàn)并不優(yōu)于對(duì)照組。

參考文獻(xiàn)

[1]熊永陽(yáng).分布式一致性問(wèn)題研究[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