Basic - Paxos

目录

这是 Paxos 两部曲中的第一篇，附上两部曲连接

• Basic-Paxos —— 朴素 Paxos
• Muti-Paxos 与 Fast-Paxos

导言

Paxos 是 Lamport 提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法，在 2006 年 Google 将其运用于 Chubby 锁服务器上后便受到了巨大的关注。

1998 年，Lamport 在其发表的论文 《The Part-Time Parliament》中虚构了一个古希腊诚邦，并通过寓言的方式讲解了如何在城邦中形成一个确定性的提案。论文提出后，许多人表示难以理解，于是 Lamport 在 2001 年又发表了第二篇论文 《Paxos made simple》。

在 Wiki 中对于 Paxos 算法的解说比较难以理解。而在观看完 知行学社 关于该算法的介绍之后，茅塞顿开。

该视频就 Paxos 在解决什么问题以及如何解决问题给出了通俗的解释，同时提出了一个工程问题，并通过不断优化来最终引出 Paxos 算法。

因此本文章最开始会采用视频中的说法来介绍该算法的实现过程，而最后回到 wiki 中的说明。

学习资料

• 论文：paxos_made_simple.pdf (stanford.edu)
• 翻译：《Paxos Made Simple》翻译 - 姚灯灯! - 博客园 (cnblogs.com)
• 视频：知行学社 —— paxos 和分布式系统_哔哩哔哩_bilibili

Paxos 在解决什么问题

Paxos 算法是用来确定一个不可变量的取值的 。

分布式中的通讯存在两张模型：共享内存和消息传递。基于消息传递的分布式系统不可避免的会出现以下问题：

• 节点宕机
• 消息延迟，重复，丢失（这里暂时不考虑消息被篡改）

作为共识算法，其主要目的为在可能会出现以上问题的分布式系统中各个节点就某个值达成共识 。

例如在分布式系统中，可以设置一个叫 var 的变量。我们需要实现以下功能：

• 在该值被确定前，可以就该值的取值提出设置请求
• 在该值被确定后，后续都可以获取到该值，即使分布式系统中部分节点宕机。

提出问题

视频中提出了一个工程问题，提出解决方案并不断优化，最终引出 Paxos 算法。

消息流: Fast-Paxos ，无冲突

这里的 API 接口为 ：Acceptor::propose(var, V) => <ok, f> or <error, null>

要求：

2. 可以容忍任意 Proposer 故障
3. 可以容忍半数以下的 Acceptor 故障

方案一

假设系统只有一个 Acceptor，则只需要解决 Proposer 的并发调用。这里可以采用一种互斥锁的方式解决。

该方案的 Acceptor::propose 过程分为两个阶段：

1. Prepare

   首先调用 Acceptor::prepare 获取 Acceptor 的锁和当前 var 的值 f，如果发现锁被占用，则停止 propose 操作。否则进入阶段二

2. Accept

   • 如果 f 为 null，则调用 Acceptor::accept(var, v)，将 Acceptor 的 var 值设置为 v 。
   • 否则，则调用 Acceptor::release() 释放锁

该方案会出现死锁的问题，当 Proposer 调用 Acceptor::prepare 获取锁后宕机，则会一直占用锁，整个系统将不可用。因此不能容忍 Proposer 故障 ，需要改进。

方案二

为了解决方案一的死锁问题，我们引入一个可抢占锁机制：

Proposer 向 Acceptor 申请访问权时指定编号 epoch，获得访问权之后才能向 acceptor 提交取值。

对于 Acceptor ，采用 喜新厌旧 原则，其需要记录自己授权的最大的编号 last_epoch，对于任何请求，如果其附带的 epoch 小于 last_epoch ，则不接受其请求，返回 <error> (或直接不返回都可)。

这里抽象出一个 提案 = [value, accept_epoch]

即变量 var 除了具有值信息，还存有设置其值的 epoch 值。

对于 Proposer 来说，采用 后者认同前者 原则：

• 在肯定旧的 epoch 没有形成确定性取值时，新的 epoch 会提交自己的 value
• 一旦旧的 epoch 形成了确定性取值，则新的 epoch 会认同此取值。

该方案的 Acceptor::propose 过程同样分为两个阶段：

1. Prepare

   选取当前时间戳作为 epoch，通过 Acceptor::prepare 获取访问权，与当前 var 的取值，如果不能获取则直接停止。

2. Accept

   • 如果 var 的取值为空，则调用 Acceptor::accept(var, prepared_epoch, V) 将数据 V 提交，因为存在并发，因此这里可能会失败，失败后可直接返回失败，或回到阶段一再次尝试。
   • 如果 var 的取值不为空，则说明已经有确定性取值，因此不调用任何 acceptor 的接口，直接将 var 作为获取到的值返回 。

在该方案中，只要 Acceptor 不宕机，则该系统一定能成功运行，包括某些极端情况 （例如 两个 Proposer 同时经过阶段一后同时执行阶段二），同时 因为 只有一个 Acceptor，所有异步请求在进入 Acceptor 后都会变为 串行请求 。

但该方案的前提 只有一个 Acceptor 决定了该方案中 Acceptor 存在单点故障。

方案三

方案三在方案二的基础上引入多个 Acceptor，实际上该方案已经很接近 Paxos 的实现模式。

Acceptor 的实现保持不变，仍然采用 喜新厌旧 的 原则 。

同时因为引入了多个 Acceptor，因此不定值的确定需要引入新的原则。也就是 Paxos 中的半数以上确定原则，即：

一旦某 epoch 的取值 f 被半数以上的 acceptor 接受，则认为该值已经确定为 f 。

这里的半数是法定半数，为所有节点数量的半数，不是当前正常工作的设备的半数，即宕机的节点也要被计算在内。

该方案的 Acceptor::propose 过程同样分为两个阶段：

在该过程中，var 除了具有值信息，同时储存了其修改请求对应的 epoch 值，在阶段一中返回的 var 值就带有其 epoch 信息。

1. Prepare

   选定时间戳作为 epoch，调用所有 acceptor 中的 Acceptor::prepare 获取访问权，同时也会得到一组取值。如果能不能获取半数以上 Acceptor 的访问权，则直接停止。否则进入第二阶段。

2. Accept

   • 如果获取到的 var 取值都为空，则调用 所有Acceptor::accept(var, prepared_epoch, V) 将数据 V 提交，如果能收到半数以上 Acceptor 成功，则返回成功，否则返回失败。这里失败后会重新进行阶段一 。
   • 如果获取到的 var 取值不为空，则认同 最大 accepted_epoch 对应的 f，调用所有 Acceptor::accept(var, prepared_epoch, f) 将 f 作为新值提交修改，同时如果能收到半数以上 Acceptor 成功，则返回成功，否则返回失败。

Liveness 问题

方案三中，如果初始状态 var 没有取值，而两个 profoser 交替进行阶段一和阶段二，每次都将对方的访问权抢占，则可能会导致活锁。

称为 Paxos 算法的 Liveness 问题。

该问题 Paxos 算法并没有规定，因此我们在使用该算法时需要自行解决该问题。

目前对于该问题，一般是限定 Proposer 为一个解决。当然在真正的工程中，为了防止 Proposer 单点故障，一般采用投票选举的方式选出 Proposer，在 之后 zab 或 raft 协议中会提及。

总结

1. 不可变变量包括两个信息，其取值，与其接受对应的 epoch
2. Acceptor 采用 喜新厌旧 原则，只接受 epoch 大的请求
3. Profoser 采用 后者认同前者 原则 与 半数以上接受 原则
4. 在实际应用中，为了避免活锁问题，一般需要确保只有一个 Profoser，而该算法本身没有确定该方面，因此在具体的协议中一般会另外规定选举的算法。

官方定义

在 wiki 中给出了 Paxos 算法论文中给出的过程。

wiki 中从数学上给出了其可用性的证明，这里直接跳过不做分析。

首先将议员的角色分为 proposers，acceptors，和 learners（允许身兼数职）。proposers 提出提案，提案信息包括提案编号和提议的 value；acceptor 收到提案后可以接受（accept）提案，若提案获得多数派（majority）的 acceptors 的接受，则称该提案被批准（chosen）；learners 只能“学习”被批准的提案。划分角色后，就可以更精确的定义问题：

1. 决议（value）只有在被 proposers 提出后才能被批准（未经批准的决议称为“提案（proposal）”）；
2. 在一次 Paxos 算法的执行实例中，只批准（chosen）一个 value；
3. learners 只能获得被批准（chosen）的 value。

决议的提出与批准

通过一个决议分为两个阶段：

1. Prepare
   1. Proposer 选择一个提案编号 n 并将 Prepare 请求发送给 Acceptors 中的一个多数派 （即至少要发给半数以上的 Acceptor ）
   2. Acceptor 收到 Prepare 消息后，如果提案的编号大于已经接受的所有 Prepare 消息的编号，则将自己上次接受的提案回复给 Proposer，并承诺不再回复小于 n 的提案
   3. 当 Proposer 收到了半数以上 Acceptor 对 Prepare 的回复，则进入第二阶段。
2. Accept
   1. Proposer 选择一个值，该值为阶段一中收到的提案中提案编号最大的提案中的取值，如果不存在这样的取值，则 Poposer 可自行指定。并与阶段一中确定的提案编号 n 组成一个提案，向阶段一中有回复的 Acceptor 发送 Accept 请求，其中包含这个新生成的提案。
   2. 在不违背自己向其他 Proposer 承诺的前提下，Acceptor 收到 Accept 请求后即接受该提案，将其储存。

这个过程在任何时候中断都可以保证正确性。例如如果一个 Proposer 发现已经有其他 Proposers 提出了编号更高的提案，则有必要中断这个过程。因此为了优化，在上述Prepare 过程中，如果一个 Acceptor 发现存在一个更高编号的提案，则需要通知 Proposer，提醒其中断这次提案。

Leaners 学习

一个显而易见的方法是当 Acceptors 通过一个提案时，将这个消息发送给所有 Learners 。但是这个方法会导致消息量过大。

由于假设没有 Byzantine failures（拜占庭问题），Learners可以通过别的 Learners 获取已经通过的决议。因此 Acceptors 只需将批准的消息发送给指定的某一个 Learner ，其他 Learners 向它询问已经通过的决议。这个方法降低了消息量，但是指定 Learner 失效将引起系统失效。

因此 Acceptors 需要将 accept 消息发送给 Learners 的一个子集，然后由这些 Learners 去通知所有 Learners。

但是由于消息传递的不确定性，可能会没有任何 Learner 获得了决议批准的消息。当 Learners 需要了解决议通过情况时，可以让一个 proposer 重新进行一次提案。注意一个Learner 可能兼任 proposer 。