paxos算法的研究与改进

《paxos算法的研究与改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Paxos算法的研究与改进　　摘要：Paxos算法是分布式系统中解决一致性问题的最重要的算法，但该算法在活性和性能两个方面存在不足。文章通过对Paxos算法及其现有优化算法的研究和对比，提出了一种基于超时机制的Paxos改进算法TB-Paxos（Timeout-basedPaxos）。TB-Paxos通过对Proposer在重新发起prepare请求前加入随机等待时间能有效地避免算法出现活锁，以及在Proposer添加固定的等待时间、减少必要的Acceptor数量以及添加额外消息能有效地提升算法的执行效率。　　关键词：一致性算法；Paxos；超时机制；TB-Paxos

2、　　1概述　　一致性??题是分布式系统中最重要的问题之一，最典型的应用是容错处理，比如在原子广播和状态机复制中都需要一个步骤让所有节点让一个值达成一致。一致性问题的难点在于异步网络中的容错处理，需要保证在部分节点出现故障时整个系统能继续正确运行。一致性算法需要满足安全性和活性两个需求[1]，安全性指算法不会使系统进入不一致状态，活性指算法在有限时间内进入下一个状态。基于消息传递的Paxos算法是最重要的一致性算法之一，算法的安全性已经得到证明，即使在部分机器节点出错的情况下也能保证算法的正确性，但是仍然算法本身存在活性和消息延迟等问题[2]。本文针对Paxos算法的不

3、足，通过引入超时机制以及其它辅助策略对Paxos进行了改进，使Paxos可以在不引入Leader的情况下，保证算法的活性和提高算法的性能。　　2Paxos算法　　Paxos算法通过复制日志解决一致性问题。日志内容是形如（id，v）组成的序列，其中id和v分别代表Paxos实例编号和客户端请求，Paxos算法保证所有复制日志中id对应的v相同。Paxos算法中包括Proposer，Acceptor和Learner三种角色，每个角色对应节点上的一个进程，每个节点可同时拥有多个角色。单个Paxos实例的执行过程如下[1]：　　（1）Prepare阶段：Proposer选择一

4、个提案编号n，然后向所有Accepter发送编号为n的prepare请求。当Acceptor收到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号。那么它保证不会再通过任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在，不存在则为空）作为响应。　　（2）Accept阶段：如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n，值为v的提案的accept请求给Acceptors的一个多数派，其中v是收到的响应中编号最大的提案的值，如果响应中不包含提案

5、，那么它就是任意值。如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未响应编号大于n的prepare请求，它就可以通过这个提案。　　（3）Learn阶段：在Proposer收到来自半数以上的accept请求的回复时，它将v记录到日志里，然后发送Success消息给每个Acceptor。所有的Acceptor收到Success消息后，将v记录到它的日志里。　　从算法可知，Prepare阶段中如果两个Proposer持续地产生一系列的提案，最终不会有提案被选定，引起活锁；另一方面，完成一个Paxos实例需要3次通信延迟，所以算法执行效率不高。针对P

6、axos算法的缺陷，现有的算法改进或实现主要是通过引入Leader机制[4]来解决活性问题，并且可以将3次通信延迟减少为2次，但会出现单点问题[5]。其余的改进多通过减少算法执行中通信节点的数量[2]和减少通信延迟次数[3]对算法进行优化，以及利用计算机工程技术提高算法的执行效率[6]。　　3TB-Paxos算法　　3.1优化策略　　为了解决活性问题，为Paxos算法的必要过程设置一个计时器，利用超时机制来衡量这个过程是成功或者失败，对某个流程选择性地重复执行来保证这个流程正确执行。另外，可以利用随机超时时间保证算法有效地避免出现活锁。具体的优化策略如下：　　（1）为

7、Proposer等待prepare请求和accept请求回复的过程增加一个时钟，超过设置的时钟Proposer就认为该请求失败。当时钟设置为无穷大时，即为原生Paxos算法。具体时钟的大小可以根据具体的网络环境和服务器处理能力进行设置，初始时可以设置一个略大的值，然后根据算法具体执行流程所花费的时间，来设置一个合理大小的时钟。　　（2）当提案被拒绝时，Proposer需要重新提交prepare请求，如果频繁的提交可能会引起活锁，但是可以等待一个范围内的随机时间再提交prepare请求就可以有效地减小出现活锁的概率。　　（3）在Acceptor接收到一