一致性协议Paxos详解（二）：Multi-Paxos协议流程详解

2024-02-16 17:25:40

一致性协议Paxos详解（二）：Multi-Paxos协议流程详解

前言

有关一致性协议的资料网上有很多，当然错误也有很多。笔者在学习的过程中走了不少弯路。现在回过头来看，最好的学习资料就是Leslie Lamport和Diego Ongaro的数篇论文、Ongaro在youtube上发的三个视频讲解，以及何登成的ppt。

本系列文章是只是笔者在学习一致性协议过程中的摘抄和总结，有疏漏之处敬请谅解，欢迎讨论。

Multi-Paxos

  • Consensus Module：从Basic Paxos的决策单个Value，到连续决策多个Value。同时确保每个Servers上的顺序完全一致
  • 相同顺序执行命令，所有Servers状态一致
  • 只要多数节点存活，Server能提供正常服务

什么是Multi-Paxos

针对每一个PaxosInstance使用完整的Paxos算法，确保系统中的每一个Server，Server上的每一个PaxosInstance都完全一致，注意，Multi-Paxos not specified pricisely in literature.

Multi-Paxos 介绍

Multi-Paxos的描述主要来自Ongaro博士的两篇文章：Paxos summary和Implementing Replicated Logs with Paxos和对应视频，还有何登成老师的ppt，这些是最好的学习资料，本文内容基本上就是对这些资料的片面摘抄再加上自己的理解。

注意，Multi-Paxos not specified pricisely in literature。

Multi-Paxos中，所有的节点既是proposer，又是acceptor，外部client发给任意一个Multi-Paxos节点写日志的请求，由该节点负责propose该请求到Multi-Paxos集群中。做出这种集群方式的假设只是为了方便后面的讲解（同时也是Ongaro视频使用的方法），不同的系统可以由不同的实现。

accpector

负责接收和处理来自proposer的proposal

acceptor持久化状态
  1. LastLogIndex：已经accept的最大log entry index
  2. minProposal：最小的接收到但是没有accept的ProposalId。如果是0则表示未收到人格Proposal request

所有accpetor需要存储日志LogEntry，对每个LogEntry i ∈ [ 1 , l a s t L o g I n d e x ] i \in [1, lastLogIndex] i∈[1,lastLogIndex]，其存储以下信息：

  1. acceptProposal[i]：i号LogEntry收到的proposal的数量，0代表这个LogEntry从没有收到过提案， + ∞ +\infty +∞代表当前LogEntry的value已经被选定已经被选定（accept）（这点意味着acceptor需要有方法知道这个logEntry的value是否被选定了）。
  2. acceptedValue[i]：i号LogEntry最后收到的proposal的value，0代表这个LogEntry从未收到过提案。

并且，我们使用firstUnchosenIndex代表最小的i且满足 i > 0 ∪ a c c e p t e d P r o p o s a l [ i ] < + ∞ i > 0 \cup acceptedProposal[i] < +\infty i>0∪acceptedProposal[i]<+∞，意思是i之前的所有logEntry的value已经被chosen了。（当一个acceptor收到client的一个proposal后，它会使用这个index向所有的acceptor执行proposal/accept,然后一直推进firstUnchosenIndex直到满足client的需求。）

proposer

负责对某条LogEntry发起提案（可以是写，也可以是读）

proposer持久化的状态
  • maxRound：当前proposer所经历的最大轮次
proposer存储的易失状态
  1. nextIndex：下一个proposal对应的LogEntry
  2. prepared：True代表当前proposal已经prepare成功了（大部分acceptor已经promise了该proposal，也就是说给proposer回复了noMoreAccepted）

rpc流程及优化

1. prepare

首先proposer发送新的proposal request，包含以下内容：

  1. n：proposalId，Ongaro博士说最简单的方法可以用round number + server id组成
  2. index：表明该条proposal request对应哪条LogEntry，就算有多个proposer同时向acceptor提议，只要index不同，acceptor是可以并行处理的。但是并行处理的log还是要顺序的apply进RSM中。

acceptor收到proposal request之后，如果request.n >= minProposal，设置minProposal = request.n，然后回复proposer，这个response中包含一个promise，含义是拒绝所有request.n < numProposal的proposal request。response包含以下内容：

  1. acceptedProposal：当前acceptor的acceptedProposal[index]
  2. acceptedValue：当前acceptor的acceptedValue[index]
  3. noMoreAccepted：如果acceptor从未accept过在当前高于request index的request。
2. accept

proposer发出的accept rpc包含以下内容：

  1. n：ProposalID，和之前对应的proposal相同
  2. index：对应的LogEntry index
  3. v：value，如果preposal response中有值，选取对应proposalID最大的，如果response中没有值，可以*选择。
  4. firstUnchosenIndex，这个是为了方便acceptor追平log

acceptor收到accept rpc之后：

  1. 如果n>=numProposal
    1. acceptedProposal[index]=n
    2. acceptedValue[index]=v
    3. minProposal=n
  2. else：拒绝更新日志
  3. 无论n怎样，下面的事情都要做：
    1. 对每个index<=request.firstUnchosenIndex，设置 a c c e p t e d P r o p o s a l [ i n d e x ] = ∞ acceptedProposal[index]=\infty acceptedProposal[index]=∞
    2. 回复:
      1. minProposal
      2. firstUnchosenIndex，这个是为了方便刚当选的leader追平log
3. Success

Success rpc的作用是刚当选的leader处理之前term的LogEntry

proposer会发送success rpc，包含以下内容：

  1. index：某LogEntry
  2. v：value for index

acceptor收到Success rpc之后，将对应的LogEntry设置为chosen状态：

  1. 设置 a c c e p t e d P r o p o s a l [ i n d e x ] = ∞ acceptedProposal[index]=\infty acceptedProposal[index]=∞
  2. 设置acceptedValue[index]=v
  3. 回复自己的firstUnchosenIndex，方便proposer判断是否需要继续发送Success rpc

Multi-Paxos系统消息流程 write(inputValue) → bool

  1. （首先client发送rpc请求给Multi-Paxos系统的某个节点）如果该节点不是leader或者leader还未初始化好，返回false
  2. 如果该节点是leader并且如果prepared==true：
    • index = nextIndex; nextIndex++;
    • goto 步骤6，主要确定v到底用哪个，如果leader已经prepared==true，应该可以直接从日志中看出v是什么。
  3. 如果prepared!=true:：index = firstUnchosenIndex; nextIndex = index + 1;，开始走leader初始化prepare的流程
  4. 通过某种方式找到proposalID n，可以使用上面proposer持久化的状态一节讲到的maxRound
  5. leader开始向所有节点广播prepare(n,index)
  6. 当从大多数acceptor节点收到Prepareresponses(reply.acceptedProposal,reply.acceptedValue,reply.noMoreAccepted)后：
    • 如果收到恢复的最大reply.acceptedProposal非零，则使用最大reply.acceptedProposal对应的reply.acceptedValue作为提案的v，否则v使用client传来的inputValue。
    • 如果大部分acceptor返回了reply.noMoreAccepted==true，设置prepared = true。
  7. 向所有acceptor发送Accept(index, n, v)
  8. 收到回复acceptResponse(reply.n, reply.firstUnchosenIndex)：
    • 如果reply.n > n，设置maxRound=reply.n，并且设置prepared = false. 返回步骤1
    • 如果reply.firstUnchosenIndex ≤ lastLogIndex并且 a c c e p t e d P r o p o s a l [ r e p l y . f i r s t U n c h o s e n I n d e x ] = ∞ acceptedProposal[reply.firstUnchosenIndex] = \infty acceptedProposal[reply.firstUnchosenIndex]=∞说明该acceptor中有LogEntry需要更新为chosen状态。向acceptor发送Success(index = reply.firstUnchosenIndex, value = acceptedValue[reply.firstUnchosenIndex])
  9. 当收到大部分acceptor对于LogEntry n的回复之后：
    • Set a c c e p t e d P r o p o s a l [ i n d e x ] = ∞ acceptedProposal[index]=\infty acceptedProposal[index]=∞ 和 acceptedValue[index] = v。
  10. 如果v == inputValue，对client返回true
  11. 返回步骤2，向后找一个新的index继续提交。

集群变动 Reconfiguration

集群变动需要保证在整个集群变动的过程中，不会形成多个多数派

Leslie Lamport建议paxos使用LogEntry来管理集群变动，configuration changes LogEntry指明了集群的配置变动会在当前LogEntry的α条entry之后生效，这个值是由Paxos系统指定的。

两点值得注意：

  1. multi-paxos系统根据选定的α决定其大的日志并发度（concurrency）：如果系统中i日志没有被chosen，那么i+α则不允许被chosen
  2. 如果希望系统快速进入新的配置状态，可以发一系列no-op
上一篇：一致性算法（一）：Paxos


下一篇：分布式系统理论基础4：Paxos