分布式原理

Paxos原理简介

一、理论基础

由Leslie Lamport撰写的两篇论文

  • 《The Part-Time Parliament》1990
  • 《Paxos Made Simpe》2001

第一篇论文标题直译为“兼职议会”,寓意是

  • 将一致性协议类比为 议会达成决议的方法
  • 将分布式系统中的节点故障类比为 议会参与者均为兼职身份,可能随时退出决议流程

第一篇论文以故事的形式提出理论,第二篇论文给出了更为清晰的算法描述。

以下算法介绍按照第二篇论文的内容进行描述。

二、基本思想

三种角色

  • Proposer
  • Acceptor
  • Learner

Learner用于决议的传播,本文仅讨论如何达成决议,因此仅涉及Proposer和Acceptor。

两个阶段

  • 准备阶段(Prepare)
  • 提交阶段(Commit / Accept)

名词解释

  • 提案 / Proposal:Proposer提出的备选结果,包含编号n和值v
  • 响应 / Respond:Acceptor通过Proposer的Prepare请求
  • 提出 / Issued:Proposer将提案(Accept请求)正式发出
  • 批准 / Accepted:Acceptor在第二阶段接受提案
  • 决议 / 选定 / Chosen:一次Paxos过程最后达成的一致结果
  • 编号 / 版本:每个提案产生时获取一个全局递增的编号(编号的生成方式本文不做讨论)

设计理念

  1. 就某一事件达成一致
    • 如果有不同的提案,无论最终选择哪个提案都是正确的,重点不在于选择哪个结果,在于达成一致
  2. 在达成一致结果的过程中避免产生冲突
  3. 谨慎原则:如果有产生冲突的风险,选择使用已有决议重新发起提案来避免冲突

应用场景

多节点选主

如选主的场景,a、b、c三个Proposer均提议自己为主,此时提案分别为,master=a、master=b、master=c,Paxos保证最终所有节点达成一致的结果,如master=a。

此时无论最后的master是a、b、c都是正确的结果。

数据更新

一个集群有三节点副本,假设v的原始值是10,此时有并发的a操作v=20和b操作v=v+1。在这种场景下,不同的提案内容是先执行a还是先执行b,而不是执行a或者执行b。

正确的应用方式

  • 提案1,id为2的操作记为a操作v=20
  • 提案2,id为2的操作记为b操作v=v+1

对应的结果

  • 如果提案1胜出,先执行v=20再执行v=v+1,最后v是21
  • 如果提案2胜出,先执行v=v+1再执行v=20,最后v是20

无论哪种结果,写操作都没有丢失,只是由于先后顺序产生了不一样的结果,无论哪种结果都是正确的,有操作日志与之对应。

错误的应用方式

  • 提案1,执行a操作v=20
  • 提案2,执行b操作v=v+1

对应的结果

  • 如果提案1胜出,执行v=20,最后v是20
  • 如果提案2胜出,执行v=v+1,最后v是11

第2种结果是明显错误的结果,因为丢失了一次更新操作。

三、必要条件(Requriements)

保证算法能够成功运作的条件,以命题(Proposition)的方式提出。

P1:处理第一个提案

原文

An acceptor must accept the first proposal that it receives.

翻译

一个Acceptor必须批准它收到的第一个提案。

解读

处理初始状态的方式。

P2:避免产生冲突决议

原文

If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

翻译

如果编号为n、值为v的提案(即[n, v])被选定了,那么有比编号n更高的,且被选定的提案,其值必须也是v。

解读

如果已经选定一个值为v的提案,就不能再选定有冲突的提案(编号更高但值不为v)。

P2a:避免Acceptor批准冲突提案

#####原文
If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

翻译

如果编号为n、值为v的提案(即[n, v])被选定了,那么有比编号n更高的,且被Acceptor批准的提案,其值必须也是v。

解读

如果已经选定一个值为v的提案,Acceptor就不能再批准有冲突的提案(编号更高但值不为v)。

P2是针对最终决议的要求,P2a为针对单个Acceptor的要求。

P2b:避免Proposer提出冲突提案

原文

If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

翻译

如果一个提案[n, v]被选定后,那么之后任何Proposer产生的编号更高的提案,其值都是v。

解读

如果已经选定一个值为v的提案,Proposer就不应该再提出有冲突的提案(编号更高但值不为v)。

P2b将P2a针对单个Acceptor的要求,前置为对Proposer的要求。

P2c:避免提出冲突提案的具体场景

原文

For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either

(a) no acceptor in S has accepted any proposal numbered less than n, or

(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

翻译

对于任意的n和v,如果提案[n,v]被提出,那么肯定存在一个由半数以上的的Acceptor组成的集合S,满足以下两个条件中的任意一个

  • S中的所有Acceptor都未批准过编号小于n的提案。
  • 选取S中所有Acceptor批准的编号小于n的提案,其中编号最大的那个提案其值是v。
解读

说明:P2c以当前最大编号提案的视角来描述约束条件。

此命题为Proposer提出提案的详细要求,假设当前提案编号为n、值为v,如果需要保证此提案不会带来冲突(提出一个编号更高,但值不为已产生决议的值),有以下两种情况

  1. 决议尚未产生,可以提出任何提案
  2. 决议已经产生,提案值需与决议值相同

决议尚未产生

对应P2c的第1种情况,因为多数Acceptor没有批准过小于n的提案,即没有批准过任何提案,此时相当于决议尚未产生(至少未完成多数Accept),可以提出一个全新的值。

  • 如果后续自己的提案通过,其他Proposer会与自己保持一致
  • 如果没通过更不会对决议产生影响

决议已产生

对应P2c的第2种情况,能够从一些Acceptor得知已经批准过提案,此时应将自己的提案替换已有决议的值(谨慎原则:使用现有决议)。
为了在多个已批准提案中选取决议值有统一的规则,约定选取已批准提案中编号最大的提案。

  • 假设已产生的决议编号为m、值为v
  • 存在一个多数派集合C,其中所有的Acceptor都批准过编号为m、值为v的提案
  • 提案m+1选取的多数派集合S与C必定存在交集,如果从交集Acceptor中选取编号最大的已批准的提案是m,使用该值生成的提案值为v
  • 以此类推可得[m+1 ... n]的提案值均为v,因此不会产生冲突的提案

P1a: 避免Acceptor处理提案冲突

原文

An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

翻译

一个Acceptor可以批准编号为n的提案,当且仅当该Acceptor尚未响应过任何编号大于n的Prepare请求。

解读

Proposer需要向Acceptor了解已批准的提案,如果询问的那一刻还没有批准,但询问之后又批准了怎么办?
为了避免产生这种情况,Proposer需要Acceptor作出承诺,不批准比自己编号更低的提案。

Prepare请求的职能是结合了P1a(承诺不批准低版本提案)和P2c(询问已批准提案的情况)。

命题间的关系

  • P1、P2是算法运作的必要条件(requirements)
  • P2a(Acceptor约束)能够必然推导出(implies)P2(决议约束),P2b(Proposer约束)能够必然推导出P2a(Acceptor约束)
  • 能够通过保证P2c(使用已有的决议、在安全的状态下提出新值)来满足P2b(Proposer约束)(satisfy P2b by maintaining the invariance of P2c)
  • P1a(何时Accept提案)包含(subsumes)P1,即P1a也适用于第一个提案的处理

四、算法流程

流程优化

  • 根据P1a,一个Acceptor如果当前完成Prepare的编号是n,就不会再Accept编号小于n的提案,因此也没必要Prepare编号小于n的提案
  • 对于Prepare请求,如果编号小于当前Prepare编号,Acceptor可以直接拒绝该请求

第一阶段:Prepare

  1. Proposer发起Prepare请求
    • 发送包含编号n但不包含值的Prepare请求
  2. Acceptor处理Prepare请求
    • 如果n > preparedProposalNum,记录当前Prepare提案编号preparedProposalNum = n
    • 反馈已批准过的提案[acceptedProposalNum, acceptedValue](P2c)
    • 如果n >= preparedProposalNum反馈Prepare成功,否则反馈失败(流程优化)
  3. Proposer收集Prepare反馈、选定提案值v
    • 如果Acceptor均未Accept过提案,Proposer指定自己期望的值(P2c)
    • 如果有Acceptor Accept过提案,Proposer使用收集到的acceptedProposalNum最大的acceptedValue作为提案值(P2c)
第二阶段:Accept
  1. Proposer发起Accept请求
    • 以编号n与选定的值v发起Accept请求
  2. Acceptor处理Accept请求
    • 如果n >= preparedProposalNum接受该Accept请求,否则拒绝(P1a)
    • 记录acceptedProposalNum = n, acceptedValue = v,反馈accept结果

五、总结

算法原理

当有不同的Proposer提出不同的提案,Paxos的执行过程实际是高版本提案低版本提案的竞争过程。
假设v=a、v=b两个提案,b的编号大于a。a和b都尝试征得一个多数派集合的批准,而任何两个多数派集合都存在交集,交集中的Acceptor接收到请求的先后顺序,决定了最后的结果。

这些请求包括:a的Prepare、a的Accept、b的Prepare、b的Accept,接收顺序只包含以下3种情况:

  1. b完成Prepare,此时a无法再完成Prepare,a的流程结束,v=b
  2. a完成Prepare,尚未完成Accept,此时b完成Prepare并替换了a的Prepare,使得a的Accept无法完成,v=b
  3. a完成Prepare,也完成Accept,此时b在Prepare过程中学习到已批准提案,将自己提案的值改为a,最终v=a

    其中1、2是b作为最大编号的完整流程,3是a作为最大编号的完整流程,适用于P2c中编号最大的要求(满足P2c并提出一个没有冲突的提案)。

算法流程

  1. 两阶段流程
    • Proposer先发送Prepare请求询问现状,再发送Accept请求进行赋值
  2. 已批准优先
    • 若发现已批准的提案,提交其中版本最高的值,否则提交新值
  3. 高版本优先
    • Acceptor已Prepare的编号为m,仅响应、批准编号大于等于m的提案

参考资料

  1. 《Paxos Made Simple》,Leslie Lamport,2011
  2. 《从Paxos到ZooKeeper:分布式一致性原理与实践》,倪超
  3. 《Paxos的应用场景》https://www.jianshu.com/p/dbb7da189b51

© 2018, 高飞航.cn. 版权所有.

About gaofeihang

开发工程师,本站的作者。欢迎留下您宝贵的意见!

发表评论

电子邮件地址不会被公开。 必填项已用*标注