Paxos协议

太过爱你忘了你带给我的痛 2021-10-19 17:48 289阅读 0赞

### Paxos协议 ###

*  概念
 *  执行过程
 *   *  Prepare 阶段
     *  Accept 阶段
     *  Learn 阶段
 *  约束条件
 *   *  正确性
     *  可终止性

# 概念 #

用于达成共识性问题，即对多个节点产生的值，该算法能保证只选出唯一一个值。  
主要有三类节点：  
提议者（Proposer）：提议一个值；  
接受者（Acceptor）：对每个提议进行投票；  
告知者（Learner）：被告知投票的结果，不参与投票过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70]

# 执行过程 #

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

## Prepare 阶段 ##

下图演示了两个 Proposer 和三个 Acceptor 的系统中运行该算法的初始过程，每个 Proposer 都会向所有 Acceptor 发送 Prepare 请求。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70 1]

当 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 类似。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70 2]  
  如果 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 类似。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70 3]

## Accept 阶段 ##

当一个 Proposer 接收到超过一半 Acceptor 的 Prepare 响应时，就可以发送 Accept 请求。  
  Proposer A 接收到两个 Prepare 响应之后，就发送 \[n=2, v=8\] Accept 请求。该 Accept 请求会被所有 Acceptor 丢弃，因为此时所有 Acceptor 都保证不接受序号小于 4 的提议。  
  Proposer B 过后也收到了两个 Prepare 响应，因此也开始发送 Accept 请求。需要注意的是，Accept 请求的 v 需要取它收到的最大提议编号对应的 v 值，也就是 8。因此它发送 \[n=4, v=8\] 的 Accept 请求。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70 4]

## Learn 阶段 ##

Acceptor 接收到 Accept 请求时，如果序号大于等于该 Acceptor 承诺的最小序号，那么就发送 Learn 提议给所有的 Learner。当 Learner 发现有大多数的 Acceptor 接收了某个提议，那么该提议的提议值就被 Paxos 选择出来。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70 5]

# 约束条件 #

## 正确性 ##

指只有一个提议值会生效。因为 Paxos 协议要求每个生效的提议被多数 Acceptor 接收，并且 Acceptor 不会接受两个不同的提议，因此可以保证正确性。

## 可终止性 ##

指最后总会有一个提议生效。Paxos 协议能够让 Proposer 发送的提议朝着能被大多数 Acceptor 接受的那个提议靠拢，因此能够保证可终止性。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70]: /images/20211019/e0b08cca0ef94bf19e76e37acf836906.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70 1]: /images/20211019/b6475280203148af813c97e580b70db8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70 2]: /images/20211019/c3618c3fb2134c188d18c9e41df39a44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70 3]: /images/20211019/69269731f5124d7fa5cd75d291a1fdb9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70 4]: /images/20211019/d67d7557a90e406a85a72b1c972bc1e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lqbjE5OTU_size_16_color_FFFFFF_t_70 5]: /images/20211019/226f2b761bcd4129b7748ae72a420169.png