光与影的个人博客

NEUCoder

0%

共识算法-Paxos

发表于 更新于 分类于 ，

分布式共识算法-Paxos

共识算法目的是通过一系列通信约束，使得依靠不可靠通信网络上的不同结点之间能够通过算法得到一致的结论（区别于分布式一致性这一概念）,共识算法是实现state machine replication 的基础，后者是分布式系统中较为重要的备份容错算法策略

分布式CAP

一个分布式系统只能满足一下三条性质中的两条

  1. Consistency(一致性)：每个客户端的读操作均能读取到最近的写入内容或者返回错误
  2. Availability(可用性): 客户端的每个请求均能收到非报错响应（回复不一定正确即不一定保证C）
  3. Partition Tolerance(分区容错性)：不同结点或分区之间的网络故障不会影响系统的正常运行

为什么说分布式系统只能保证其中两条？

  1. 分布式系统由于系统结点/分区分布于不同的网络环境，通过网络进行通信，不可避免地会出现结点由于网络故障下线问题，为了系统的可用性，必须保证Partition Tolerance
  2. 当部分结点出现网络故障时，面对客户端请求，系统有两种处理方式
    • 回退操作，相当于保证了C但舍弃了A
    • 继续执行操作，由于部分结点下线，此时执行操作无法保证C，但是保证了A

单机系统由于不会出现分布网络失效，所以也就不需要P，可以同时保证CA

Paxos

The Paxos protocol was first submitted in 1989 and named after a fictional legislative consensus system used on the Paxos island in Greece

Paxos是经典的基于消息传递共识算法，然而理解难度过高，简单整理以加深印象，算法中定义了四种不同的角色（一个结点可以有多个不同的角色）

  1. Client: 客户端向系统发送请求（例如：向分布式文件系统写入）
  2. Proposer: 提出提案
  3. Acceptor: 判断是否接受提案
  4. Learner: 当提案被接受时，执行具体操作（例如：执行写入操作）
  5. Leader: 唯一的Proposer

其他概念

  1. Proposal: 提案，每个提案由提案号n和提案值组成v:
  2. Quorums: 由大多数Accepter组成的集合，用来投票确定是否接受提案
  3. safety/liveness/fault tolerance: 共识算法的三个形式，类似于CAP三者只能满足其二
    • safety: “坏事”永远不会发生
    • liveness: “好事”终将发生
    • 没太理解和fault tolerance之间的关系和区别

Paxos保证safety+fault tolerance，不保证liveness

算法流程（Basic Paxos）

分为确定提案值+接受提案两个阶段

  1. 阶段1（prepare+promise）：该阶段用来收集历史提案信息
    • 由Proposer创建Prepare message，其中包括此次提案号n（n保证大于之前任何Prepare中的n），发送给至少Quorums数量的Acceptor
    • 接收到Prepare message的Acceptor，根据提案号n确定返回消息类型
      • 若当前提案号小于历史Prepare message和提交提案的提案号，不进行响应（过滤历史）
      • 若大于则根据是否存在历史提交提案，返回历史或者空的提案值+提案号（收集信息）
    • Proposer收到大多数Acceptor的响应信息，进入下一阶段

  2. 阶段2（accept+accepted）：提交提案

    • Proposer根据接收到的响应类型确定提案value，之后发送Accept message (n,v)到Acceptor
      • 若响应中包含提案号m+提案value，将当前提案value设置为最大m对应的value
      • 若只有Promise响应，将提案value设置为 originally wanted value
    • 若当前提案号小于Acceptor历史Prepare message和提交提案的提案号，不进行响应
    • 否则提交当前提案，返回信息
    • Proposer收到大多数Acceptor的响应信息，确认提交，将提案值发给所有Learner

只看算法流程很难理解paxos为什么要这么设计，结合以下几个设计出发点方便理解

  1. paxos整个流程只针对一个值达到共识（多个提案仅仅是不同Proposer对于当前值的提议，最终决定一个），与直觉上的一个提案对应一个共识不同
  2. 算法基于FIFO的原则，现提出提案的最先可能达成共识

根据对算法流程的分析，Proposer和Acceptor的行为可以理解为：

  • Acceptor：无条件接收更新的提案
  • Proposer：第一任务是继续提交之前未提交成功的提案值（第一阶段收集信息的作用），只有在没有历史的时候才能自己确定提交value

Paxos之所以能够保证safty，即保证得到共识，可以从以下角度理解：

  • 阶段1的存在，保证了不会出现split vote问题（一旦有过半的Acceptor提交了提案，后续继续提交提案的value只能从这些Acceptor中确定）
  • 提案号递增+多数提交，保证了一致性

Basic Paxos无法保证livness，即无法保证算法能够终止找到共识

  • 两个Proposer在Accept阶段争抢,如下
    • Proposer1此时提出提案1，即将走到Accept阶段时，Proposer2提出提案2，导致提案1的编号因为小于最新提案2，无法通过，Proposer1重新提交提案3，导致提案2小于提案3，无法通过
    • 最终导致无限的抢占，无法达共识
  • 通过Proposer的随机休眠避免抢占冲突发生

Multi Paxos

Paxos存在的如下问题，导致其只适合作为理论上的分布式共识算法模型

  1. 模型上只针对一个共识的实现，无法重复进行多次共识操作
  2. 两阶段流程在高并发情况下不仅存在livness问题，通信成本价高

为了解决Paxos算法上述问题，改进得到Multi Paxos算法

  1. 选举一个固定的Proposer,提案编号中变为 Proposer编号+提案编号
    • 通过一个和basic Paxos相同两阶段选举主Proposer
  2. 每次提出提案，直接进行第二阶段

Multi Paxos就和Raft以及Zab很接近了

参考

  1. Paxos (computer science) From Wikipedia)
  2. 知乎：Paxos算法详解