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

刘春涨　王丽颖　靳庆庚　郭瑞　刘金辉

摘 要：文中首先介绍了一致性算法的应用状况，重点结合Paxos算法对并行计算的方法进行了探究。分析了计算机的计算问题，进行了问题抽象，设计了一个基于Paxos算法的分布式计算的原型系统。并通过仿真实验验证了方案的可行性。

关键词：Paxos算法；并行计算；计算方法；分布式计算

中图分类号：TP301.61 文献标识码：A 文章编号：2095-1302（2016）04-00-02

0 引 言

一致性在计算机以及自动控制领域运用较多。例如数据中心的同步，生产线上机器人所执行的动作协调等，一致性在该领域的作用可以概括为解决合作问题[1]。一致性产生于合作，即个体与其他个体之间的协作。计算机中，一个集群中的电脑要一起合作完成一个任务，可以通过消息传递和共享内存两种方式完成。Paxos算法是一种采用消息传递方式实现一致性的算法。

Paxos算法就是通过前者获知全局消息的算法。Paxos算法的输入是各个计算机的全局请求（即整个集群知道的消息），输出是请求的全局执行顺序。假如各个计算机内对各消息的解释代码都相同，那么，通过执行带编号的全局请求，各个机器就可以得到同样的结果[2-4]。

本文设计了一种基于Paxos算法的分布式计算的计算模型，并进行了系统仿真设计。

1 相关工作

1.1 提升集群的CPU利用率以及计算问题的本质

定义计算的数学模型TR（A，B，C，.......，Z0），Z0代表汇总计算；A，B，C，...代表可拆解的最小计算单元（即各个计算单元之间如A，B之间不存在顺序）。

在单台单处理器机器上，设最小单元的平均计算时间为w，最小计算单元数为n，汇总耗时为t。则执行TR模型耗时cost_sig为nw+t。

在多台单处理器机器上，假设计算机数目为n，每台机器上分配到的计算单元数为k（k<

计算问题即计算过程以及得到结果的一系列过程，可以看成一颗多叉树，父节点可由其子节点进行运算得到，其所耗掉的时间为其子节点数g乘上平均计算时间w。整体的计算时间由树的深度h决定（假设通信开销为常量c）。则一个计算程序的耗时为：。在单台单处理器的机器上TR是线性执行的，将其也看成一棵树，则树的深度为节点数。而在多台单处理器上，树的深度比前面的单台单处理器情况来的浅，故能起到加速执行的作用。

计算问题的优化在一定程度上可以看成是提升CPU的利用率。如何利用Paxos算法来使计算机集群的CPU资源得到充分利用，本文认为可以遵循以下两个原则：

（1）设计出计算单元耗时大于通信开销的算法。

（2）从计算树上进行并行算法的调度研究。

从计算树上进行并行算法的调度研究之前，若先建立计算树到物理机器的映射，则较快的并行算法的设计问题可以转化为计算单元调度使得时间代价最小的问题。

进一步将计算问题进行抽象，抽象为计算树的叶节点着色问题，即每次只能在叶节点着色，一次只能着色1～n（机器数）个叶节点，每次着色完毕后记录被着色的叶节点，当树的中间节点的叶节点数均被着色后，中间节点变为新的叶节点。直至根节点时，计算z0以及着色的次数k，并保证k的取值最小。

假设设计得到的算法是function（），该函数记录了第i次着色时着色的叶子节点以及相关细节。

Paxos算法中一个决议应对应一次着色，故通过的决议应当包括被着色的叶子节点信息（即要执行的计算单元）。假如不考虑单点故障问题，认为所有计算机均能正常工作，我们便可以用hash方法来分配这些计算单元给集群中不同的机器。当所有节点执行完成一条协议后便可以执行下一次着色，直至根节点，便可输出最终的计算结果。所以应用Paxos算法解决并行运算之前需要将计算单元进行分配编号，并将编号以及计算单元的内容发送给集群中的各个机器，这样便可以让计算机在通过决议后经过哈希函数（即起到过滤掉不属于本机器的计算单元的作用）调用相应的计算单元进行计算，最终实现并行计算任务。

综上，运用Paxos解决并行计算问题的解题步骤如下：

（1）设计出计算单元耗时大于通信开销的算法；

（2）设计解释器来解释各服务器所能执行的编号以及翻译该编号的计算流程；

（3）将计算问题的各个步骤内聚成计算单元，得到计算单元的计算树（循环问题单独看成一个计算单元），将这些计算单元以及编号分给各个计算服务器，执行着色算法f；

（4）从算法f中得到着色过程，将这些决议提交给Paxos算法中的client。修改Paxos算法使其能将每次着色的消息通知给所有计算机。没有一致性这一特性的保障将使得CPU利用率降低；

（5）各个计算服务器利用hash值来判断本次决议自己所负责执行的计算单元；

（6）输出计算的结果。

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

实验环境与比较方案：libpaxos，不带线程的计算方法1，带线程的计算方法2，实验组用3台计算服务器进行协作计算，对照组用一台。比较实验组和对照组得到结果所耗时间。

编程实现如下模型，在图1所示的基于Paxos算法的分布式计算模型的解释器中加入上述策略。

2 结 语

通过实验验证，本文所设计的进行计算的原型系统方案是可行的。在大量多线程处理问题上实验组比对照组表现好，但在多重循环嵌套的控制结构表现并不优于对照组。

参考文献

[1]熊永阳.分布式一致性问题研究[D].哈尔滨：哈尔滨工业大学，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