paxos协议

Paxos算法是Lamport宗师1998提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。

1、paxos协议解决了什么问题？

Paxos算法解决的问题正是分布式一致性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成一致

2、paxos协议的实现原理？

Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner):

  • Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
  • Acceptor：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。
  • Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。
sequenceDiagram
  participant Proposer
  participant Acceptor
  participant Learner

  Proposer -> Acceptor: Prepare(n)
  Acceptor -> Proposer: Promise(n, v)
  Proposer -> Learner: Accept(n, v)
  Learner -> Learner: Ack(n, v)

  alt Ack(n, v) > 2/3
    Learner -> Learner: Stable(n, v)
  end

Paxos算法通过一个决议分为三个阶段（Learn阶段之前决议已经形成）：

  1. 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。
  2. 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。
  3. 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

两个承诺：

  1. 不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Prepare请求。

  2. 不再接受Proposal ID小于（注意：这里是< ）当前请求的Propose请求

一个应答：

不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。

3、paxos协议的优缺点？

优点：

  1. 保证强一致性

缺点：

  1. 较难理解，完整的paxos实现复杂
  2. 存在活锁问题

4、paxos协议在开源中的应用

zookeeper

Google的chubby

参考文章:

  1. https://mp.weixin.qq.com/s/aJoXSQo9-zmukN2RsiZ3_g