杨革+徐虹

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

关键词：一致性算法；Paxos；超时机制；TB-Paxos

1 概述

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

2 Paxos算法

Paxos算法通过复制日志解决一致性问题。日志内容是形如（id，v）组成的序列，其中id和v分别代表Paxos实例编号和客户端请求，Paxos算法保证所有复制日志中id对应的v相同。Paxos算法中包括Proposer，Acceptor和Learner三种角色，每个角色对应节点上的一个进程，每个节点可同时拥有多个角色。单个Paxos实例的执行过程如下[1]：

（1）Prepare阶段：Proposer选择一个提案编号n，然后向所有Accepter发送编号为n的prepare请求。当Acceptor收到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号。那么它保证不会再通过任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在，不存在则为空）作为响应。

（2）Accept阶段：如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n，值为v的提案的accept请求给Acceptors的一个多数派，其中v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未响应编号大于n的prepare请求，它就可以通过这个提案。

（3）Learn阶段：在Proposer收到来自半数以上的accept请求的回复时，它将v记录到日志里，然后发送Success消息给每个Acceptor。所有的Acceptor收到Success消息后，将v记录到它的日志里。

从算法可知，Prepare阶段中如果两个Proposer持续地产生一系列的提案，最终不会有提案被选定，引起活锁；另一方面，完成一个Paxos实例需要3次通信延迟，所以算法执行效率不高。针对Paxos算法的缺陷，现有的算法改进或实现主要是通过引入Leader机制[4]来解决活性问题，并且可以将3次通信延迟减少为2次，但会出现单点问题[5]。其余的改进多通过减少算法执行中通信节点的数量[2]和减少通信延迟次数[3]对算法进行优化，以及利用计算机工程技术提高算法的执行效率[6]。

3 TB-Paxos算法

3.1 优化策略

为了解决活性问题，为Paxos算法的必要过程设置一个计时器，利用超时机制来衡量这个过程是成功或者失败，对某个流程选择性地重复执行来保证这个流程正确执行。另外，可以利用随机超时时间保证算法有效地避免出现活锁。具体的优化策略如下：

（1）为Proposer等待prepare请求和accept请求回复的过程增加一个时钟，超过设置的时钟Proposer就认为该请求失败。当时钟设置为无穷大时，即为原生Paxos算法。具体时钟的大小可以根据具体的网络环境和服务器处理能力进行设置，初始时可以设置一个略大的值，然后根据算法具体执行流程所花费的时间，来设置一个合理大小的时钟。

（2）当提案被拒绝时，Proposer需要重新提交prepare请求，如果频繁的提交可能会引起活锁，但是可以等待一个范围内的随机时间再提交prepare请求就可以有效地减小出现活锁的概率。

（3）在Acceptor接收到一个新的prepare请求时，可以给最近收到的prepare请求回复一条Nack消息，通知该编号的协议不会被通过。如果某个Proposer收到超过半数的Acceptor的Nack消息，则可以断定该提案一定会失败，可以提前结束这个流程。

（4）使用缺少失败恢复机制的Cheap Paxos的策略[2]，可以减少Proposer发送prepare请求和accept消息的数量。由于系统环境的不确定性，可以根据具体环境决定接收Acceptor集合的大小，并且每个阶段Acceptor的数量可以不一致。

3.2 TB-Paxos算法过程

优化算法过程和Paxos算法相似，只需在相应的阶段和角色中添加优化策略。Paxos算法的执行过程，以下给出优化算法的流程图（如图1），其中lastTried为上次请求编号，nextBal为上次同意投票的编号、preVote为上次投票的值。

在Proposer重新发起请求之前，可以根据是否收到alert消息判断是否需要设置一个随机等待时间避免活锁。如果需要则等待随机时间后才发起请求；否则直接发起请求。图中的虚线框的内容表示可以根据需要选择是否添加到算法中，收到Nack消息可以按照算法改进策略（3）进行处理；Acceptor如果收到一个编号比其它prepare请求编号小，可发送reject消息（内容为请求编号）告知Proposer需要提交更大编号的请求才能被通过，以减少该Proposer请求失败的次数。流程图中未涉及相应阶段Acceptor集合的选择，具体参考算法改进策略（4）。

3.3 性能分析

本文提出的前三条优化策略可以有效地解决Paxos算法的活性问题，可以提高算法的可靠性，保证算法快速完成；第四条优化策略从消息数量方面对Paxos算法进行了优化，在稳定的系统环境中，可以有效的提升算法的执行效率。假设Paxos集群拥有2F+1个节点，如果在Prepare阶段和Accept阶段分别选用M，N（M，N>F+1）个Acceptor，则可以减少2（2F+1-M-N）个消息传输和处理。然而在网络不稳定的系统环境中减少消息传输可能不会带来明显的效果，反而导致算法不斷重新执行。

4 结束语

数据一致性是分布式系统中的难点问题，Paxos算法是一致性问题的主要解决方案。本文提出的TB-Paxos算法在不破坏系统节点对称性的前提下，能有效地解决Paxos算法的活性问题，并且通过减少消息通信数量的方式可以提高算法性能。Paxos算法除了本文提及的活性问题，还有很多问题需要解决（如日志复制、读写请求的区分等），未来的工作主要包括如何优化Paxos算法流程以及结合计算机相关技术方面来提高算法的可靠性和性能。

参考文献

[1]L Lamport. Paxos Made Simple [J]. ACM Sigact News， 32（4）： 18-25， 2001.

[2]L Lamport， Massa Mike. Cheap Paxos [J]. Proceedings of the International Conference， 2004.

[3]L Lamport. Fast Paxos [J]. Distributed Computing， 19（2）， 2005.

[4]D Ongaro. In Search of an Understandable Consensus Algorithm [J]. Stanford University. 2013.

[5]I Moraru. There Is More Consensus in Egalitarian Parliaments [J]. In Proc. of SOSP， 2013.

[6]J Li. Just Say NO to Paxos Overhead： Replacing Consensus with Network Ordering [J]. In 11th USENIX Symposium on OSDI.，2016.

作者简介：杨革（1992-），男，四川达州，硕士研究生，主要研究方向：嵌入式工程。