共识算法——Paxos算法

故事

Lamport描述了一个名为Paxos的希腊城邦（算法得名于此），这个城邦是按照民主的议会制度来进行选举的，所有的居民进行提议和投票来选出决议。但是居民们不想花时间一直在选举上，大家都不定时地来提议、了解提议、投票、看进展等等

CAP

• C：一致性
• A：可用性
• P：分区容错性

CAP定理指 在一个分布式系统中，无法同时满足 CAP 3个特性。 在分布式系统中，分区是必须面对的问题，因此P是一定要成立的。

在满足分区容错性（P）的前提下，一个分布式系统只能满足 一致性（C）或者 可用性（A）
像zk之类的配置中心对一致性要求较高，一般都是CP

共识算法

共识算法可以理解为了实现分布式一致性协议而产生的一系列流程与规则。 共识算法大体分为两种类型：

• 拜占庭算法：伪造信息恶意响应的情况
• 非拜占庭算法：把出现故障(即不响应)但不会伪造信息的情况

Paxos

概念

Paxos：达成共识的方式-少数服从多数；也就是典型的“多数人暴政” 在Paxos中，包含三种角色：

• 提案者（Proposer）：提案者。也就是进行写操作的人
• 接受者（Acceptor）：对每个提议的值进行投票，并存储接受的值
• 学习者（Learner）：被告知投票的结果，接受达成共识的值，不参与投票的过程，存储接受数据

单个提案者

在 Paxos 算法中，使用提案表示一个提议，提案包括提案编号和提议的值。接下来，我们使用 [n, v] 表示一个提案，其中，n 是提案编号，v 是提案的值。

首先一台机器接受到了客户端写操作，设置为提案者，然后该节点提出提案给其他机器。（注意在准备阶段，请求中不需要指定提议的值，只需要包含提案编号即可。） [图片上传失败...(image-517a14-1663294562999)]

其他的接收者没有收到其他提案时，就直接投票了，赞成提案（同意提议）。

Paxos两阶段提交：

• Prepare阶段：Proposer告诉所有其他机器，我这里有一个提案（操作），想要你们投投票支持一下，想听听大家的意见。Acceptor进行响应。
• Accept阶段：Proposer收到其他机器的回复，可以支持接受Proposer的提案（操作），于是正式通知大家这个提案被集体通过了，可以生效了，操作就会被同步到所有机器正式生效。

多个提案者(Basic-Paxos)

前提：Acceptor如果还没有正式通过提案（即还没有Accept使操作生效），就可以接受编号更大的Prepare请求。 因为网络等一些问题，提案者到达接收者的顺序也不同。假设提案者1的提案先到达接受者1上；提案者2的提案先导致接受者2上。

• 接受者1发现自己可以接受提案，并承诺自己不在接受提案编号小于1的提案
• 接受者2发现自己可以接受提案，并承诺自己不在接受提案编号小于2的提案
• 此时提案者1希望得到接受者2的支持，接收者2一看提案编号比2小，就拒绝
• 而提案者2去发送提案给接受者1，接受者1一看提案比自己的编号1要大，就同意该提案
• 最终提案2得到共识
• 后续提案者1知道自己没有得到半数以上的支持，会变成一个Learner（如果后续新增机器，也会变成learner），接受 接受者2的生效提案的请求

  

已经存在通过的提案

• 接上图，编号2的提案已经生效了，但是提案者1发送了编号为1的提案给接受者2
• 此时接受者2会拒绝提案并告诉当前生效的提案
• 而后提案者1会修改自身提案，同时帮助提案者2传播提案，加快达成共识

接收者在Accept前挂了

假设有多个提案提出，此时接收者3正好是此时编号最大的提案，按照正常情况，编号为3的提案是最终会达成共识的提案。但此时接受者3在生效提案之前挂掉了，那么就会陷入一个不断重试报错的循环。 为了解决这个问题，加入如下规则：允许Proposer在提案遭到过半数的拒绝时，更新自己的提案编号，用新的更大的提案编号，去发起新的Prepare请求。

上述的问题也会引起活锁的问题；（一直被拒绝，一直更新编号）。

• 随机延时更新编号的行为，错开冲突
• 选举一个提案者为leader，只有leader才有提案的权限，相当于单个提案者的思路。

Multi-Paxos

Basic-Paxos是一次达成共识的过程，如果有多个值，那么需要多次的网络通信，和活锁问题。
因此提出Multi-Paxos的方式，此种算法也是可以应用于工业生产的共识原型。

• 选择一个leader来当选提案者（此时有且只有一个提案者，解决活锁问题），两阶段变成一阶段（取消Prepare阶段）
• 自定义leader选举方式，需解决脑裂问题。

Google Chubby组件便是使用了类Multi-Paxos的方式