谈谈对分布式一致性算法Paxos的理解

前言

最开始知道这个Paxos协议,是在研究MySQL的高可用的时候接触到的,从MySQL的复制机制了解到有基于semi-sync 的半同步复制,还有组复制MySQL Group Replication (MGR), 后来了解到这个MGR就是基于Paxos来实现的。 除了MGR,还有蚂蚁金服的OceanBase,Google的 Spanner 、chubby 都是基于Paxos协议(Multi-Paxos)的实现(复制状态机)。对于他们是怎么落地实现的,我还没有深入去研究,只是看过蚂蚁金服的中间件团队写的一本书有介绍到,所以这篇文章不是讲Paxos怎么应用(How),也不是讲Paxos的证明(Why),只是总结一下Paxos是什么(What)。

正文

Paxos算法是Lamport提出的一种基于消息传递的一致性算法,《Paxos Made Simple》,Paxos算法解决的是在分布式系统中对某个值达成一致的问题(就像CAS是并发环境下保证原子操作的一种手段,Paxos的这种保证也是分布式系统一致性的理论基础)。下面说的Paxos都是指Basic Paxos,除此之外还有一个优化的Multi-Paxos。

这里的分布式系统模型是非拜占庭将军模型,也就是消息或者命令可能丢失,但是不会有恶意消息/命令的情况。

Paxos 的特点

  • 只能确定一个值或者说单个事件的一致性,达成一致后无法修改
  • 任何节点都可以发起提案
  • 可容忍消息丢失、延时、乱序和重复。
  • 利用多数派Majority机制保障2F+1的容错能力,也就是说只要保证集群半数以上节点存活,集群能正常服务。

把Paxos当作一个理论来看,可能比较好理解,在看这部分的时候,我总想往实际场景套,发现很难套上去,Paxos算法只是解决了单个值的共识问题,实际场景上落地需要实现连续的复制状态机,总之有点难理解,等我看下OceanBase团队的博客系统文章后再来回顾一下,《Paxos Made Simple》这篇论文后面有提到一个状态机的实现。

Paxos算法中的角色

  • 提议者(Proposer):发起提案的节点
  • 接受者(Acceptor):参与决策,对提案进行承诺和接受的节点
  • 学习者(Learner): 不参与决策,对已经确定共识的提案进行学习记录的节点

Paxos算法流程

  1. Prepare阶段:

    • Proposer 准备一个提案(Proposal),只需要确定一个提案号N ,这个N是单调递增的 。

    • Proposer 将这个preapre消息 【Proposal Number (N)】 广播到所有的Acceptor节点,直到得到多数派的响应。

    • Acceptor 收到prepare消息后对N进行判断,然后作出响应。

      1.承诺不再响应编号小于N的提案

      2.如果存在已经通过的提案,则在响应内容中体现。

  2. Accept阶段:

    • 如果Proposer收到半数以上的Acceptor对它的编号为N的prepare请求的响应集合{(n,Vi)};那么,Proposer将在这个集合中挑选一个最大提案的value(如果不存在,也就是prepare阶段Acceptors的响应不包含提案,则这个值由当前Proposer决定)和 当前编号N 构造一个accept请求发给acceptors。

      如果发现有已经被accept的提案,当前的Proposer需要将自己的value修改为这个最大值,这很关键,因为accept 阶段可能只有部分acceptor成功了,但是acceptors中能在下一次prepare阶段反馈给Proposer完成一个"妥协"

    • Acceptor收到accept请求后,只要它还未对编号大于N的Prepare请求作出响应,则它就可以通过这个提案。

  3. Learn阶段:

    一个值被accept后,acceptor就要通知learner,哪个值被选定了。

图1. Paxos 提案表决时序图

Paxos 的一些缺点

  1. 实现难度大

  2. 效率低,需要2次RPC调用。

  3. 存在活锁问题(多个Proposer在Prepare阶段存在交替请求promise的情况,导致大家都冲突了)。

    可以使用随机休眠时间来缓解这个问题,当发生冲突的时候,各自休眠一段时间2~5s。

    或者使用一个主Proposer来发起提案,主Proposer的选举还是利用一次Paxos算法来决定。

Multi-Paxos

Multi-Paxos 针对Basic Paxos的一些缺点进行优化,主要改进如下

  1. 将2次RPC减少到1次(最开始还是需要2次),通过选出一个主Proposer来发起提案。
  2. 简化角色,集群中所有的节点既可以是Proposer也可以是acceptor。