阅读笔记（八）共识算法Paxos

约定不等于承诺〃 2023-07-02 03:22 14阅读 0赞

### 一. 前言 ###

本文接前文[2PC][], [3PC][]，继续介绍最常用的共识算法之一：Paxos。在今天的很多分布式系统，如谷歌的Chubby， 雅虎的Zookeeper之中，都可以见到其身影。相对于2PC和3PC，Paxos在遇到网络分区的情况时会表现出更好的容错性，不论是对于彻底宕机的节点（fail - stop），还是暂时宕机之后可以恢复的节点（fail - recover），均可以保证最终一致性。

### 二. 算法模型 ###

Paxos算法中，网络节点分为了三类：提出者（Proposers），接受者（Acceptors），学习者（Learners）。每个节点可以充当多个角色，同时必须知道大多数或全部的接受者。另外，节点需要记录他们收到的信息，不可以遗忘。一次Paxos过程的目标是达成一个一致性，如果有新的共识需要达成，则需要一个新的Paxos过程。

*  提出者（Proposer）顾名思义，是整个过程的发起人。提出者会首先发送一个序列号n给所有的接受者，如果收到回复则发送数据，如果没有则考虑自增序列号再次尝试发送。
 *  接受者（Acceptors）在收到一个序列号n之后会比对自身曾经收到的最大序列号，如果n比较大则会回复Promise消息，等待接收提出者的值。当收到值得时候则发送确认，并向学习者发送该共识消息
 *  学习者（Learners）主要是没有参与Paxos共识过程的节点，在收到接受者给出的共识消息时直接接收采用

如下图所示为一个Paxos的整体过程。左侧为n值为最大序列时顺利的完成共识算法的过程，右侧是n值较小时需要自增的过程图。

![基本paxos过程][paxos]

### 三. 算法容错性 ###

Paxos过程可能会遇到如下图所示的问题：如果有两个提出者均提出各自的共识，可能会导致类似于TCP中拥塞控制的不断自增序列的问题。提出者1提出了序列5，而提出者2提出了6，这导致1的提交过程无法顺利完成，因此只好继续自增。而这又会导致2的继续自增。如此循环。对于此类问题较好的解法是采取类似TCP的指数退避，从而给出间隔让某一个提出者先完成共识。

![paxos 出现问题][paxos 1]

### 四. 总结 ###

本文简单介绍了Paxos的整个过程，中间也许有一些遗漏，可以参考下面的文献资料进行学习。学习的话建议先看论文《Paxos Made Simple》，即该算法提出者自己写的一篇较易于理解的论文，之后可以看一看博客https://www.the-paper-trail.org/post/2009-02-03-consensus-protocols-paxos/以及油管视频The Paxos Algorithm。后续深入的论文包括工程实践的《Paxos Made Live - An Engineering Perspective》以及算法讨论的《The Part-Time Parliament》。

### 五. 参考文献 ###

【1】https://www.the-paper-trail.org/post/2009-02-03-consensus-protocols-paxos/  
【2】Paxos Made Simple  
【3】Paxos Made Live - An Engineering Perspective  
【4】The Part-Time Parliament  
【5】The Paxos Algorithm (https://www.youtube.com/watch?v=d7nAGI\_NZPk&t=4s)

[2PC]: https://blog.csdn.net/u013354486/article/details/103934854
[3PC]: https://blog.csdn.net/u013354486/article/details/104081996
[paxos]: https://img-blog.csdnimg.cn/2020012616373393.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70
[paxos 1]: https://img-blog.csdnimg.cn/20200126164113761.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70