论文部分内容阅读
共识算法在分布式计算中处于核心地位,主要解决多个计算节点如何在故障存在的情况下,就计算期间所需数值达成一致的问题。目前,Multi-Decree Paxos(Multi-Paxos)算法在共识算法领域占据主导地位,但其单领导者设计策略不仅存在单点故障的风险,也会对算法性能产生影响。针对Multi-Paxos单领导者设计缺陷,研究人员提出了许多算法变种。其中,Iulian Moraru等人在the Twenty-Fourth ACM Symposium on Operating Systems Principles(SOSP 2013)上提出的Egalitarian Paxos(EPaxos)算法具有优异的性能,得到了业内的广泛关注。EPaxos不设置领导者,所有节点均可处理客户端命令。在客户端命令无冲突的情况下,算法性能优异,但客户端命令冲突的情况会对算法性能产生影响。本文在EPaxos算法的基础上,以提升共识算法性能为目标进行研究,主要研究工作和创新点如下:(1)针对客户端命令冲突影响EPaxos延迟性能的问题,以低延迟为设计目标,将EPaxos算法和Multi-Paxos算法相结合,提出了共识算法Modified Egalitarian Paxos(MEPaxos)。首先,综合考虑节点的负载情况、网络的实时情况以及客户端命令的处理情况,提出系统平均延迟的计算方法;接着,对二阶段提交算法进行改进,提出转换算法;最后,根据系统平均延迟的计算结果,利用转换算法自动选择系统平均延迟较优的算法模式执行。理论分析与实验结果表明,MEPaxos算法下,系统延迟性能得到了提升。(2)针对客户端命令冲突影响EPaxos算法性能的问题,兼顾延迟与吞吐量性能,在EPaxos算法的基础上,引入分区处理的思想,提出了共识算法Partition Processing Egalitarian Paxos(PPEPaxos)。首先,设计并实现了实时监控系统,从各节点处获取当前客户端命令的处理情况,据此判断是否需要进行分区处理;接着,提出分区方案决策算法,对需要进行分区处理的情况,利用分区方案决策算法生成具体的分区方案;最后,通知各节点分区方案,各节点根据分区方案,对客户端命令进行分区处理。理论分析和实验结果表明,PPEPaxos算法下,系统延迟和吞吐量性能均有了提升。(3)从理论与实验两方面,对MEPaxos和PPEPaxos进行对比分析。首先,分析MEPaxos与PPEPaxos处理客户端命令的流程;接着,根据客户端命令处理流程,结合二者详细的算法步骤,从应用范围、延迟性能以及吞吐量性能三方面对MEPaxos和PPEPaxos进行理论分析对比;最后,对MEPaxos和PPEPaxos进行延迟与吞吐量实验,验证理论分析的结果。