Paxos算法

水深无声 2023-09-26 23:03 114阅读 0赞

### Paxos算法 ###

*  一致性
 *  Paxos算法中的角色
 *  主要流程（两大阶段）
 *   *  prepare阶段
     *   *  prepare(N)请求
         *  promise(n, value)返回
     *  accept阶段
     *   *  accept(N, value)请求
         *  accepted(N)返回
         *  达成共识
 *  案例分析
 *   *  案例1
     *  案例2
 *  算法流程
 *  缺点及相关优化措施
 *   *  死锁
     *  效率低
     *  实现困难

# 一致性 #

一致性就是数据保持一致，在分布式系统中，可以理解为多个节点中数据的值是一致的。

1.  **弱一致性**  
    1）最终一致性  
    2）DNS（典型例子，在DNS服务器中添加一条域名绑定，立即去访问是访问不到的。等待1-2分钟再去访问便是可以访问的。）
2.  **强一致性**

1.  数据时刻保持一致  
    2）Paxos  
    3）Raft

# Paxos算法中的角色 #

**Proposer**：向集群**提出议案** 在发生冲突的时候起到冲突调节作用。

**Acceptor**：**对提议进行投票** 只有在达到**多数派**时提议才会最终被接受。

**Learner**：提议接受者，对集群一致性没什么影响 单纯的**记录人员**。

Proposal：proposer提出的议案或建议 **编号n和内容value**。

一个进程可以充当不同的角色  
![在这里插入图片描述][bad9e0def1704d70a36c7ce203235239.png]  
**算法最终目标**：每个Proposer、Acceptor、Learner都认为同一个Proposal的value被选中。

# 主要流程（两大阶段） #

## prepare阶段 ##

### prepare(N)请求 ###

proposer提出一个proposal，编号为N（编号应该是递增的，大于等于之前所有已经提出的编号），向所有的Acceptor广播。

**注意这里只发送编号没有内容。**

### promise(n, value)返回 ###

如果N大于该acceptor此前接收的所有提案编号就接收（并承诺不再接收比N小的提议）否则拒绝 如果该acceptor**存在已经同意的提案**就返回这个提案的编号和内容则返回空值表示接收即可。

## accept阶段 ##

### accept(N, value)请求 ###

proposer收到多数派（多于一半的acceptor返回的promise）如果存在编号大的议案返回就进行更新value，否则返回本次议案的value。**注：收到议案的n与提出的编号N无关**

### accepted(N)返回 ###

如果在此期间没有任何编号大于N的提案，就接受提案内容否则就拒绝。

### 达成共识 ###

当proposer收到超过半数的acceptor的返回值后，达成共识。

# 案例分析 #

## 案例1 ##

![在这里插入图片描述][46b56f508d7e42d1a4f3de15743ac531.png]  
参谋2发生prepare请求，三个军队收到之后，因为他们之前都已经同意了事件1，所以都给参谋2返回了编号1进攻时间1。

这里应该还有一个流程，参谋2在收到了多数派之后，它还需要发送一个accept请求。这个请求是编号2进攻时间1。

## 案例2 ##

![在这里插入图片描述][580fb95544f5451e9b7974965a6d09ff.png]  
将军2在收到编号2之后表示不再接受编号小于2的命令，因此返回Rejected 编号2，因此这次的提议就失败了。

在传递编号2进攻时间2的时候，因为之前都是返回空值，所以直接指定进攻时间2。成功传到将军2和将军3时，他们都没有任何新的编号，因此都选择了接受。这时候就达成了一致。因为满足多数派。

在参谋1发送编号3后，将军1返回编号1进攻时间1，将军2返回编号2进攻时间2，因此参谋1选取编号2，因为编号2的编号更大。选取编号2进攻时间2。然后返回编号3进攻时间2。

因为将军1和将军2没有比编号3更大的议案，因此选择接受，然后返回成功。这时整个系统就达成了共识。

# 算法流程 #

![在这里插入图片描述][293b242a3453442c8b0941055310ff74.png]

# 缺点及相关优化措施 #

## 死锁 ##

当某一proposer提交的proposal被拒绝时，可能是因为acceptor承诺返回了更大编号的proposal，因此proposer提高编号继续提交。

如果2个proposer都发现自己的编号过低而提出更高编号的proposal，会导致死循环（交替提高编号），这种情况也称为活锁。

解决方案：二进制指数退避算法。

## 效率低 ##

每个完整流程的提议都需要经过两大轮请求返回。

Multi-paxos先选出Leader后续每次仅需一轮。

## 实现困难 ##

这也是当前共识算法普遍存在的问题。

**参考资料**：[十五分钟带你了解Paxos算法][Paxos]

[bad9e0def1704d70a36c7ce203235239.png]: https://img-blog.csdnimg.cn/bad9e0def1704d70a36c7ce203235239.png
[46b56f508d7e42d1a4f3de15743ac531.png]: https://img-blog.csdnimg.cn/46b56f508d7e42d1a4f3de15743ac531.png
[580fb95544f5451e9b7974965a6d09ff.png]: https://img-blog.csdnimg.cn/580fb95544f5451e9b7974965a6d09ff.png
[293b242a3453442c8b0941055310ff74.png]: https://img-blog.csdnimg.cn/293b242a3453442c8b0941055310ff74.png
[Paxos]: https://www.bilibili.com/video/BV1kA411G7cK/?spm_id_from=333.880.my_history.page.click&vd_source=a1af903e57688df870625021f7f3a7eb