Paxos算法——科普贴（下篇，设计之美）

2019-06-20 本文已影响0人实力吃饭

接上篇：Paxos算法——科普贴（上篇，共识问题+故障是常态）

Paxos算法由图灵奖得主Leslie Lamport在《The Part-Time Parliament》一文中提出（中文译文见链接）。本文主要对Paxos算法步骤以及设计思路进行分析。

首先，需要明白Paxos算法适用于哪种环境（适用环境）以及Paxos算法设计目标，即：Paxos算法致力于提供什么样的性能（算法保证）

适用环境：非拜占庭故障下的异步系统

异步系统中，没有时间的限制。时钟以任意速度运行，网络通信所需时间不确定，节点执行操作可以花费任意长的时间。

非拜占庭故障是指，节点故障表现为对收到的消息无法进行响应，永远保持在当前状态；节点之间的消息传递是可靠的，即：消息可以不按顺序到达，可以重复发送，但不会损坏。

Paxos算法可以容忍非拜占庭故障，对于拜占庭故障，并不能很优雅地处理。

算法保证

1. Paxos算法在任何情况下均可保证安全性（Safety）。

这里安全性由两个部分组成：

（1）非平凡性（Nontriviality）：只有客户端提出的请求才能被学习；

（2）一致性（Consistency）： 同一个实例，最多只有一个客户端请求能被学习。

这里，如果节点持久存储了客户端请求，我们称节点“学习”了客户端请求。

Paxos算法中，存在一个预先确定的编号1，2，...，n，对于收到的客户端请求，分配一个特定的编号，由<编号，客户端请求>构成的二元组称为实例。Paxos通过确保每个节点收到相同的实例，节点按实例编号执行客户端请求，即可实现共识。

2. Paxos 在少数节点故障的情况下，可以提供进展保证（Progress guarantee）。

即：如果足够多的节点没有故障，并且消息在超时之前到达，对于特定编号的实例，最终可以确定对应的客户端请求，并在所有无故障节点上持久存储该实例。

Paxos算法在异步系统中，放宽了一点要求：少数节点故障，消息最终可以送达，并没有违背FLP定理（FLP定理不存在少数节点故障，消息最终可以送达这一限制）

下面，针对Paxos算法提供的算法保证，考虑Paxos的适用环境，对Paxos算法步骤进行介绍。

算法步骤

为了实现安全性保证，Paxos算法需满足非平凡性以及一致性。对于非平凡性，不难满足，Paxos只处理客户端提出的请求即可。对于一致性，是实现的难点。Paxos算法首先证明，如果满足特定约束，算法即可提供一致性和进展保证。

1.相关概念

cf：学习，确认

Paxos算法中，节点持久存储客户端请求的过程，我们称为“学习”

节点首次收到特定实例（包含<编号，客户端请求>）会进行“确认”，这里的确认并未持久存储，而是节点会记录下，收到过这一实例。Paxos算法中，在“学习”客户端请求之前，肯定会经过节点“确认”的过程。

2.特定约束

约束1：每次投票都有一个独一无二的投票编号

约束2：任意两次投票的法定人数的交集不为空，即：任意两次投票的法定人数至少有一个共同的节点。

约束3：对每次投票，如果法定人数中的节点在早期的投票中对某些实例编号（k1，k2，...，kn）的客户端请求进行了确认，并且这次投票依然需要确定这些实例编号（k1，k2，...，kn）的客户端请求，那么这些实例编号（k1，k2，...，kn）的客户端请求只能设置为法定人数中的节点在早期投票中，最晚确认的那次客户端请求。

这里，投票可以理解为执行一次Paxos算法。那么约束1要求一次Paxos算法需要有一个独一无二的编号来唯一标识。

法定人数指的是包含大多数节点（如果系统中一共有N个节点，那么大多数节点指的是最少有 $\lfloor$ N/2 $\rfloor$ +1个节点， $\lfloor$ N/2 $\rfloor$ 表示N/2的下界）的节点集合，在Paxos算法中，法定人数需要和特定节点进行消息交流。约束2要求，任意两次Paxos算法选择的法定人数至少有一个共同节点。

约束3是实现一致性的关键所在。约束3要求，对于一个实例，如果一次投票中法定人数的节点在之前的投票中对客户端请求进行了确认，那么这个实例的客户端请求必须设置为法定人数中的节点在早期投票中，最晚确认的客户端请求。那么，对于一个实例，假设在一次投票（假设编号为k）中，有一个客户端请求被学习。在紧接着的一次投票（编号为k+1）中，法定人数中的节点肯定至少存在一个节点在编号为k的投票中，对该实例进行了确定（约束2导致）。那么对于该实例，只能选择编号为k的投票中选择的客户端请求。以此类推，在之后的投票中，该实例的客户端请求只能选择编号为k的投票中选择的客户端请求，进而实现了：同一个实例，最多只有一个客户端请求能被学习。

如果大多数的节点没有故障，那么在满足约束1-3的情况下，实例被学习是有可能的。

3.算法步骤

(1) 节点p选择一个比之前所有投票都大的新的投票编号ba，将lastTried[p]设置为ba，并给某个节点集合发送NextBallot(ba，n)消息，n表示编号小于等于n的实例均已被p学习。

(2) 节点q从p处收到NextBallot(ba，n)消息并且ba要大于q收到的所有NextBallot(ba，n)消息中的ba，q将nextBal[q]设置为ba。如果q中存在小于等于n的实例未被学习，q会请求p发送这样的实例；如果q中存在大于n的实例已经被学习，会通知p；如果q中存在大于n的实例的确认，但并未学习，则给p发送LastVote(ba, v)消息，v等于q之前发送过确认的大于n的实例集合，对于每个实例来说，其中的客户端请求是最晚发送确认的客户端请求。（如果ba $\leq$ q收到的所有NextBallot(ba，n)消息中的ba，那么就忽略NextBallot(ba，n)消息）

(3) 节点p如果收到请求发送实例的信息，则发送相应实例；如果收到其他节点发送的已学习实例的通知，则学习相应实例；如果从某个大多数集合Q中的每个牧师那都收到LastVote(ba, v)（ba= lastTried[p]）消息，p会初始化一次新投票，投票编号为ba，法定人数为Q，实例集合为d，d中客户端请求的选择满足约束3。p给Q中所有牧师接着发送BeginBallot(ba, d)消息。

(4) 在节点q收到BeginBallot(ba, d)消息并且ba= nextBal[q]，q对投票编号为ba的实例进行确认，并记录下确认的实例，并且给p发送一个Voted(ba, q)消息。（如果ba $\neq$ nextBal[q]，那么就忽略BeginBallot(ba, d)消息）

(5) 如果p从Q（投票编号为ba的投票中的法定人数）中的每个节点q那都收到了Voted(ba, q)消息，并且ba = lastTried[p]，那么p将d写入分类账中并给每个节点发送Success(d)消息。

(6) 在收到Success(d)消息之后，节点持久存储d中的实例，即：学习d中的实例。

其中，步骤(1)(2)主要是为约束3的执行收集一些必要信息（例如：早期投票中，节点最晚发送确认的客户端请求）；步骤(3)根据约束3为实例选择相应的客户端请求；步骤(4)会对下一次投票收集约束3相关的信息产生影响，同时也会决定是否执行步骤(5)(6)。执行步骤(5)(6)表明实例被成功“学习”。

综上，Paxos算法步骤可以满足约束1-3，Paxos可以保证安全性，此时影响进展保证的因素是：如果不断有节点尝试进行步骤(1)，投票编号ba的值设置地越来越大，那么会阻碍下面步骤的执行（ba $\leq$ q以及ba $\neq$ nextBal[q]的情况发生）。因此，为了提供进展保证，Paxos需要选出一个特定的节点（领导者），只有该节点有权执行步骤(1),(3)。具体的选择方法，Paxos算法中并未详细描述。

Paxos算法设计精细巧妙，本身较为难懂，本文对Paxos算法进行了一个简单的描述，可能存在描述不清楚的地方，欢迎进行提问。