基于分布式同步时钟的paxos算法改进

王丽颖 王红 刘春涨

【摘要】 本文分析了出现数据一致方面的问题，对解决数据一致性的paxos算法中存在的主要问题进行了阐述，重点对一个accept与accepted过程只能通过一个议案问题和通过议案的时间受议案的长度影响问题进行了研究。在paxos算法的基础上，利用proposor提交多个议案编号，结合议案被服务器集群过半存储的前提，对算法进行了改进。测试结果表明了算法的正确性和合理性。

【关键词】 paxos算法 一次提交多个议案 过半存储

一、引言

数据一致性问题是分布式领域的经典问题，同时也是难点问题[1]。以服务器为中心的服务模型下，单点故障会导致服务器无法对外提供服务，因此需要引入多台服务器。这样将会带来数据一致性问题，因此必须有一个副本控制协议来实现数据的一致性。[2]本文的分布式存储系统由成百上千个设备组成，若一次只能提交一条议案，引入逻辑时钟同步是一个巨大的开销。本文提出的一次提交多个议案编号的方案可以降低该开销。一次提交多个议案编号的设计中假若议案编号的议案缺失，会使得系统卡在此编号上，使得服务器无法运行下一条议案。因此得设计一个方法保证议案在被批准前时刻存在。

服务器的服务能力受其自身网络的硬件条件的制约。单台服务器所能对外提供的服务能力是有限路数的，很多是受带宽、网卡处理能力的影响，这是典型的单点问题。当单台服务器达到服务能力的上限时，则采用用多台服务器来对外提供更强的服务能力。此时需要解决数据的一致性问题。

单点问题的解决方案大多是采用备份以及多服务器，多服务器意味着多中心的出现，多个中心如何保证数据一致性，以及对外提供更快速的服务是需首要解决的问题。尤其是互联网时代中的各种交易平台（如果多中心没有一致会使得业务收到影响），达成一致性所用的时间将会影响用户体验和平台的性能。因而，设计合理的响应时间的一致性算法对实际的应用来说是有意义的。

本文提出了基于全局逻辑时钟同步分布式系统一致全局状态的一种方法。本文设计了一个一致性算法并进行了系统仿真。

二、相关工作

2.1全局时钟

分布式系统中，全局时钟需要能对发生在系统中的事件进行排序。一个时钟要能用于刻画事件发生先后顺序，且对于因果序其要满足的条件：对于任意事件a，b：如果a->b，那么Cfunction（a） < Cfunction （b）。Cfunction定义为一个函数——为进程中的任意事件a分配编号Cfunction （a）。即：

IR1.每个进程Pi在任意连续的两个事件之间会增加Ci的值。

IR2.（a）如果事件a代表了进程Pi发送消息m的事件，那么消息m包含的时间戳Tm=Ci（a）.

（b）在收到消息m后，进程Pj会设置Cj的值使得它大于等于它的当前值并大于Tm。[3]

2.2 Paxos算法

Paxos算法分为两步骤：通过一个决议的过程分为两个阶段[4，5，6]（若是fastpaxos则首先，是leader选举；其次是通过一个决议[7]）：1.准备阶段（prepear，promise），2.批准阶段（accept，accepted）。随着运行paxos算法的机器数的增多算法达到一致性的时间会延长。还可得知机器数少，达到一致性的时间更短。Paxos算法通过一条议案的转态转移如下图所示：

2.3改进的算法

改进的算法转态转移图如下：

我们约定：

1.一个客户端要执行与全局相关的事件e的时，需要向时钟系统申请一个编号，之后才能执行。来保证e的操作能被其他客户端收到。

2.定义事件系统为；存储、记录以及执行全局相关的所有事件的执行顺序的系统。事件系统是按照时钟进行事件推演的。即，将事件系统的推演定义为：整个系统执行操作的顺序是按照给定的逻辑时钟编号进行执行的，即各个节点先执行C（event1）为1的event1，在执行C（event2）为2的event2

3. 进程内，进程pi只有执行完一条指令，才能提出下一条指令的时钟申请。

基于paxos算法的分布式时钟能够用来为系统运行提供一个时序。各个节点向该时钟系统申请执行议案，且严格的按照paxos时钟的时序来执行。

单个的授时中心是不可靠的，因此需要多个授时中心，但是多个授时中心的时钟又是难以保证时时刻刻一致只能在一定的精度范围内的保持一致。故为了完成在多节点的情况下能授给任何节点相同的时钟，可以在这些分布式授时中心上运行一致性算法paxos来为事件系统的执行提供时钟协作信号。从而使得事务系统中发生在各个节点中进程的事件都可以被注册唯一的编号，即C（event）是唯一的，只要其是经过我们的时钟系统提出了申请。

如何标记议案使得其在全局中是唯一。是一个较易做到的。例如使用自身的IP和PORT可以区别出本机和本机的其他进程，给议案一个标记step使其在本进程内同其他的议案相区别开，同时使带step的议案单调递增的被本进程执行。

本文对这种标记议案使其在全局中唯一的标记定义为ID。

2.4一次提交多个议案的算法的正确性说明

上述算法设计进程内：任意连续的两个事件之间会增加Ci的值。.进程间：（a）如果事件a代表了进程Pi发送消息m的事件，那么消息m包含的时间戳Tm=Ci（a）.（b）在收到消息m后，时钟系统会设置Cj的值使得它大于等于它的当前值并大于Tm。

在时钟系统中的learner中会使得编号单调递增。

2.5仿真实验设计与实现

实验环境

操作系统：ubuntu 15.04

处理器：Xeon E5-2620 ，

主频：2.00GHz，

内存：32GB的服务器 虚拟12台机器（每台1G）。

编程技术和工具：Linux C、C++。

时钟系统源码：libpaxos（开源的），（也可以用SB_ paxos）。

三、结束语

经实验验证，采用本文所述策略使得在有大量请求时效率会高于原paxos算法。关于paxos算法，若通过设置不同的paxos组可实现不同范围内的同步。可以通过修改配置文件来构建更大范围的应用。所以，下一阶段工作是进行利用改进后的paxos算法构建应用软件的研究。

参 考 文 献

[1]周婧，王意洁，阮炜，等. 面向海量数据的数据一致性研究[J].计算机科学，2006，33（4）：137-140.

[2]谈华芳，孙丽丽，侯紫峰.一种多副本一致性控制方法[J].计算机工程.2006（11）

[3]LAMPORT L.Time，clocks and the ordering of events in a distributed system[J]Commun ACM （CACM）， 1978， 21（7）：558-565

[4]许子灿，吴荣泉.基于消息传递的Paxos算法研究[J].计算机工程，2011，37（21）：287-290.

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

[6] LAMPORT L.The partime Pariment[M]. ACM Transaction on Computer Systems，1998，16（2）：133-169.

[7]LAMPORT L. Fast paxos[J].Distributed Computing，2006，2（19）：79-103.