Muti-Paxos 与 Fast-Paxos

Administrator

2021-09-03

paxos 分布式云原生数据一致

1298

导言

之前介绍的 Paxos 算法用于在一个集群中就一个不可变变量的取值达成共识。但在工程中，直接适用 Basic-Paxos 场景较少，同时其工程实现难度也较大，因此出现了两种 Paxos 的变种 Multi-Paxos 与 Fast-Paxos 。

资料：

Paxos算法 - 维基百科，自由的百科全书 (wikipedia.org)

《Paxos Made Simple》翻译 - 姚灯灯! - 博客园 (cnblogs.com)

Multi-Paxos

Paxos 的典型使用中，需要在集群中确定一组命令序列。如果每个命令都通过一个 Basic Paxos 算法实例来达到一致，则会产生大量开销，最终效率会变得十分低下。

Multi-Paxos 的核心在于，如果 Proposer 是相对稳定不变的，则在提案提出的两个阶段中，第一个阶段就变得不必要。系统可以在接下来的 Paxos 算法实例中，跳过第一个阶段。

为了实现这一目的，在同一个 Leader 执行每轮 Paxos 算法时，提案编号 I 每次递增一个值，并与每个值一起发送。Multi-Paxos 在没有故障发生时，将消息延迟(从 propose 阶段到 learn 阶段)从4次延迟降低为2次延迟。

Multi-Paxos中消息流的图形表示

Multi-Paxos 没有失败的情况

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |<---------X--X--X------>|->|  Accepted(N,I,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

跳过阶段1时的Multi-Paxos

在这种情况下，Basic Paxos 的后续实例 (由 I+1 表示) 使用相同的 Leader，因此，包含在 Prepare 和 Promise 的阶段1 (Basic Paxos 协议的这些后续实例) 将被跳过。注意，这里要求 Leader 应该是稳定的，即它不应该崩溃或改变。

Client   Proposer       Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Accepted(N,I+1,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Fast-Paxos

Fast-Paxos 将 Basic-Paxos 进行了推广，以减少端到端消息延迟。在 Basic-Paxos 中，从客户端发起请求开始，到 Learn 阶段结束的消息延迟是 3 个消息延迟。而 Fast-Paxos 允许 2 个消息延迟，但要求：

系统由 3f+ 1 个 Acceptor 组成，以容忍最多 f 个错误 ( 而不是 Basic-Paxos 的 2f+1) ；
客户端需要直接将请求发送到多个目标。

直观上，如果Leader没有提议任何value，那么客户端可以直接发送 Accept 消息到 Acceptor 。Acceptor 会像 Basic-Paxos 一样运行，向Leader 和每个 Learner 发送 Accepted 的消息，从而实现从客户端到 Learner 的两消息延迟。

如果 Leader 检测到冲突，它通过发起新一轮投票，并发送 Accept 消息来解决冲突，通常是一个 Accepted 消息。这种有协调者参与的冲突恢复机制需要 4 个从客户端到 Learner 的消息延迟。

如果 Leader 提前指定了一种冲突恢复机制，就可以实现另一种优化，它允许 Acceptors 自己执行冲突恢复。因此，无协调的冲突恢复可能实现三个消息延迟 ( 如果所有的 Learner 都是 Acceptor，那么只有两个消息延迟)。

消息流: Fast-Paxos ，无冲突

Client    Leader         Acceptor      Learner
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Any(N,I,Recovery)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Accept!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Accepted(N,I,W)
   |<------------------------------------X--X  Response(W)
   |         |          |  |  |  |       |  |

消息流: Fast-Paxos ，冲突的建议

有协调这参与的冲突恢复。注意:协议没有指定如何处理被丢弃的客户端请求。

Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      X------->|->|->|->|      |  |  Accept!(N+1,I,W)
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

无协调者参与的相冲突恢复：

Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      X------->|->|->|->|      |  |  Any(N,I,Recovery)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

消息流:无协调者的冲突恢复、角色崩溃的 Fast-Paxos

(合并的Acceptor/Learner)

Client         Servers
 |  |         |  |  |  |
 |  |         X->|->|->|  Any(N,I,Recovery)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Concurrent conflicting proposals
 |  |         |  |  |  |  !!   received in different order
 |  |         |  |  |  |  !!   by the Servers
 |  X--------?|-?|-?|-?|  Accept!(N,I,V)
 X-----------?|-?|-?|-?|  Accept!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Servers disagree on value
 |  |         X<>X->|->|  Accepted(N,I,V)
 |  |         |<-|<-X<>X  Accepted(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Detect collision & recover
 |  |         X<>X<>X<>X  Accepted(N+1,I,W)
 |<-----------X--X--X--X  Response(W)
 |  |         |  |  |  |

目录

导言