分布式---Paxos算法

缺乏、安全感 2021-11-29 08:00 293阅读 0赞

## 5.Paxos ##

Paxos算法解决的问题是**一个分布式系统如何就某个值（决议）达成一致**。一个典型的场景就是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。Paxos算法就是一种**基于消息传递模型的一致性算法**。

主要有三类节点：

*  **提议者**（Proposer）:提议一个值；
 *  **接受者**（Acceptor）:对每个提议进行投票；
 *  **告知者**（Learner）：被告知投票的结果，不参与投票。

![1652742-20190705175033153-952247898.png][]

### 执行过程 ###

规定一个提议包含两个字段：**\[n,v\]**，其中**n为序号**（具有唯一性），**v为提议值**。

#### 1.Prepare阶段 ####

下图演示了两个proposer和三个acceptor的系中运行该算法的初始过程，**每个proposer都会向所有的acceptor发送prepare请求**。

![1652742-20190705175101682-2091784006.png][]

当acceptor接受到一个prepare请求，包含的提议为\[n1,v1\]，并且之前还未接受过prepare请求，那么**发送一个prepare响应**，设置当前接受到的提议为\[n1,v1\]，并且**保证以后不会接受序号小于n1的提议**。

如下图，Acceptor X 在收到 \[n=2, v=8\] 的 Prepare 请求时，由于之前没有接收过提议，因此就发送一个 \[no previous\] 的 Prepare 响应，设置当前接收到的提议为 \[n=2, v=8\]，并且**保证以后不会再接受序号小于 2 的提议**。其它的 Acceptor 类似。

![1652742-20190705175131250-720418786.png][]

如果acceptor接收到一个prepare请求，包含的提议为\[n2,v2\],并且之前已经接收到提议\[n1,v1\]。如果n1>n2，那么就该丢弃该提议请求；否则，发送prepare响应，该prepare响应包含之前已经接收过的提议\[n1,v1\]，设置当前接收到的提议为\[n2,v2\]，并且保证以后不会再接收序号小于n2的提议。

如下图，Acceptor Z 收到 Proposer A 发来的 \[n=2, v=8\] 的 Prepare 请求，由于之前已经接收过 \[n=4, v=5\] 的提议，并且 n > 2，因此就抛弃该提议请求；Acceptor X 收到 Proposer B 发来的 \[n=4, v=5\] 的 Prepare 请求，因为之前接收到的提议为 \[n=2, v=8\]，并且 2 <= 4，因此就发送 \[n=2, v=8\] 的 Prepare 响应，设置当前接收到的提议为 \[n=4, v=5\]，并且保证以后不会再接受序号小于 4 的提议。Acceptor Y 类似。

![1652742-20190705175214562-2074984674.png][]

#### 2.Accept阶段 ####

当一个**Proposer接收超过一半acceptor的prepare响应时**，就可以发送accept请求。

proposerA接收到两个prepare响应之后，就发送\[n=2,v=8\]accept请求。该accept请求会被所有acceptor丢弃，因为此时所有acceptor都保证不接受序号小于4的提议。

Proposer B 过后也收到了两个 Prepare 响应，因此也开始发送 Accept 请求。需要注意的是，**Accept 请求的 v 需要取它收到的最大提议编号对应的 v 值，也就是 8**。因此它发送 \[n=4, v=8\] 的 Accept 请求。

![1652742-20190705175245547-815492176.png][]

#### 3.Learn阶段 ####

Acceptor接收到Accept请求时，如果序号大于等于该Acceptor承诺的最小序号，那么就发送Learn提议给所有的Learner。当**learner发现有大多数acceptor接收了某个提议，那么该提议的提议值就被paxos选择出来**。

![1652742-20190705175330049-1153042032.png][]

#### 约束条件 ####

**1.正确性**

指**只有一个提议值会生效**。

因为Paxos协议要求每个生效的提议都会被Acceptor接收，并且Acceptor**不会接收两个不同的提议**，因此可以保证正确性。

**2.可终止性**

指最后总会有一个提议生效。

Paxos协议能够让Proposer发送的提议朝着能被大多数Acceptor接受的那个提议靠拢，因此能保证可终止性。

转载于:https://www.cnblogs.com/yjxyy/p/11139855.html

[1652742-20190705175033153-952247898.png]: /images/20211129/6e21581b4e9c4fa3893dab4a7e96cb2a.png
[1652742-20190705175101682-2091784006.png]: /images/20211129/326c8f9708c842048f2263b4bf05ce4c.png
[1652742-20190705175131250-720418786.png]: /images/20211129/295f5a0545634b94963d680c1276e455.png
[1652742-20190705175214562-2074984674.png]: /images/20211129/97ae36772f9642a1a3b9e3fd2c4683e6.png
[1652742-20190705175245547-815492176.png]: /images/20211129/05abd15674bd44438342b6cb05cc5cdd.png
[1652742-20190705175330049-1153042032.png]: /images/20211129/cc4d8b9ba46c4fa49e97f4a1ea490e1e.png