基于Paxos算法的分布式計算模型探究

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

摘 要：文中首先介紹了一致性算法的應用狀況，重點結合Paxos算法對并行計算的方法進行了探究。分析了計算機的計算問題，進行了問題抽象，設計了一個基于Paxos算法的分布式計算的原型系統(tǒng)。并通過仿真實驗驗證了方案的可行性。

關鍵詞：Paxos算法；并行計算；計算方法；分布式計算

中圖分類號：TP301.61 文獻標識碼：A 文章編號：2095-1302（2016）04-00-02

0 引 言

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

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

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

1 相關工作

1.1 提升集群的CPU利用率以及計算問題的本質

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

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

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

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

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

（1）設計出計算單元耗時大于通信開銷的算法。

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

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

進一步將計算問題進行抽象，抽象為計算樹的葉節(jié)點著色問題，即每次只能在葉節(jié)點著色，一次只能著色1～n（機器數(shù)）個葉節(jié)點，每次著色完畢后記錄被著色的葉節(jié)點，當樹的中間節(jié)點的葉節(jié)點數(shù)均被著色后，中間節(jié)點變?yōu)樾碌娜~節(jié)點。直至根節(jié)點時，計算z0以及著色的次數(shù)k，并保證k的取值最小。

假設設計得到的算法是function（），該函數(shù)記錄了第i次著色時著色的葉子節(jié)點以及相關細節(jié)。

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

綜上，運用Paxos解決并行計算問題的解題步驟如下：

（1）設計出計算單元耗時大于通信開銷的算法；

（2）設計解釋器來解釋各服務器所能執(zhí)行的編號以及翻譯該編號的計算流程；

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

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

（5）各個計算服務器利用hash值來判斷本次決議自己所負責執(zhí)行的計算單元；

（6）輸出計算的結果。

1.2 基于Paxos算法的分布式計算模型

實驗環(huán)境與比較方案：libpaxos，不帶線程的計算方法1，帶線程的計算方法2，實驗組用3臺計算服務器進行協(xié)作計算，對照組用一臺。比較實驗組和對照組得到結果所耗時間。

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

2 結 語

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

參考文獻

[1]熊永陽.分布式一致性問題研究[D].哈爾濱：哈爾濱工業(yè)大學，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