一致性协议Paxos详解(二):Multi-Paxos协议流程详解

一致性协议Paxos详解(二):Multi-Paxos协议流程详解

前言

有关一致性协议的资料网上有很多,当然错误也有很多。笔者在学习的过程中走了不少弯路。现在回过头来看,最好的学习资料就是Leslie LamportDiego 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 summaryImplementing 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