Paxos 算法 (解决分布式系统中多个节点之间一致性通信协议)

Paxos 算法 百科

Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人现在在微软研究院）于1990年提出的一种基于消息传递的一致性算法。这个算法被认为是类似算法中最有效的。

Paxos 算法作用

在分布式系统中，一致性问题是在节点宕机、消息无序等场景可能出现的情况下，相互独立的节点之间如何达成决议的问题，作为解决一致性问题的协议，Paxos的核心是节点间如何确定并只确定一个值

算法思想

• 角色：
  • client：产生议题者
  • proposer: 提案者(提交议题到决策者)
  • acceptor：决策者（决定提案者提交的议题是否被采纳）
  • learner：学习者（决策采用后学习者）
• 流程图：
  1.第一阶段：预提交
• Proposer做法
  1. 生成唯一的提案号 向 Acceptor提交该提案
• Acceptor：做法
  1. 如果Acceptor1未接收过提案记本地k==null则保存该次提案序号1，返回提案成功
  2. 如果Acceptor1本地k不为空且本地的提案号大于等于Proposer1本次提交的提案号，不做应答
  3. 若Acceptor1本地k不为空且Proposer1的值大于本地k 当Acceptor1已经承诺了其他Proposer的提案成功，返回本次预提案成功并且将承诺了其他Proposer的提案的***和值返回，当Acceptor1未承诺其他Proposer的提案，返回欲提案成功，并将本地k更新

2.第二阶段：提交确认阶段

• proposer做法： 根据1阶段返回的值决定这个阶段的处理

  1. 如果该Proposer没有得到半数的Acceptor响应，则重复1阶段的过程，重新请求
  2. 得到Acceptor半数的响应，判断Acceptor是否有同意了其他Proposer的提案，如果有取最大k和值，然后提交accept，否则提交自己的value和k

• Acceptor

  1. 如果proposer提交的k值大于等于本地的k值，则更新本地的k值和存储提交的值，同意提案，否则不回应

• 提交2阶段proposer返回值处理：

  1. 提交提案后如果接收到超过半数的Acceptor返回提案成功，通知所有learner ，表示该提案获胜，否则重新进入1阶段
  2. 直到最终一个提案获取到半数Acceptor通过，Paxos过程结束了，这样，一致性得到了保证