Paxos算法

Published: 26 Oct 2019 Category: ZooKeeper

一、什么是paxos算法?

1.1 简介

Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的”La”)于1990年提出的一种基于消息传递的一致性算法。

节点通信存在两种模型:共享内存(Shared memory)(需要锁)和消息传递(Messages passing)。

为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中,是分布式计算中的重要问题。

Paxos主要用于保证分布式存储中副本(或者状态)的一致性。副本要保持一致, 那么,所有副本的更新序列就要保持一致。

如果不是分布式,那么可以利用加锁的方法,谁先申请到锁,谁就先操作。但是在分布式条件下,存在多个副本,如果依赖申请锁+副本同步更新完毕再释放锁,那么需要有分配锁的这么一个节点(如果是多个锁分配节点,那么又出现分布式锁管理的需求,把锁给哪一个客户端又成为一个难点),这个节点又成为单点,岂不是可靠性不行了,失去了分布式多副本的意义,同时性能也很差,另外,还会出现死锁等情。

1.2 适用情况

Paxos 算法适用的几种情况:

  1. 一台机器中多个进程/线程达成数据一致;
  2. 分布式文件系统或者分布式数据库中多客户端并发读写数据;
  3. 分布式存储中多个副本响应读写请求的一致性。

二、算法原理

Paxos原命题: 如果一个提议{n0,v0}被大多数Acceptor接受,那么不存在提议{n1,v1}被大多数Acceptor接受,其中n0 < n1,v0 != v1。

2.1 一些角色

在paxos算法中,分为4种角色:

  • Proposer :提议者->处理客户端请求,将客户端的请求发送到集群中,以便决定这个值是否可以被批准。不同的 Proposer 可以提出不同的 value,例如某个Proposer 提议“将变量 X 设置为 1”,另一个 Proposer 提议“将变量 X 设置为 2”,但对同一轮 Paxos过程,最多只有一个 value 被批准。

  • Acceptor:决策者->Acceptor 有 N 个,Proposer 提出的 value 必须获得超过半数(N/2+1)的 Acceptor批准后才能通过。Acceptor 之间完全对等独立。(两个多数派之间必有交集)

  • Client:产生议题者(可以忽略)

  • Learner:最终决策学习者->上面提到只要超过半数accpetor通过即可获得通过,那么learner角色的目的就是把通过的确定性取值同步给其他未确定的Acceptor。

proposer将发起提案(value)给所有accpetor,超过半数accpetor获得批准后,proposer将提案写入accpetor内,最终所有accpetor获得一致性的确定性取值,且后续不允许再修改。

2.2 原则和阶段

两个原则:

  • 1) 安全原则—保证不能做错的事

    a) 针对某个实例的表决只能有一个值被批准,不能出现一个被批准的值被另一个值覆盖的情况;(假设有一个值被多数Acceptor批准了,那么这个值就只能被学习)

    b) 每个节点只能学习到已经被批准的值,不能学习没有被批准的值。

  • 2) 存活原则—只要有多数服务器存活并且彼此间可以通信,最终都要做到的下列事情:

    a)最终会批准某个被提议的值;

    b)一个值被批准了,其他服务器最终会学习到这个值

协议分为两大阶段,每个阶段又分为A/B两小步骤:

  • 准备阶段(prepare阶段)

    • 第一阶段A:Proposer选择一个提议编号n,向所有的Acceptor广播Prepare(n)请求。

    • 第一阶段B:Acceptor接收到Prepare(n)请求,若提议编号n比之前接收的Prepare请求都要大,则承诺将不会接收提议编号比n小的提议,并且带上之前Accept的提议中编号小于n的最大的提议(注意:或者叫最近一次被accept的提议);否则不予理会。

  • 接受阶段(提交阶段/接收阶段)

    • 第二阶段A:整个协议最为关键的点:Proposer得到了Acceptor响应(且响应内容中,编号n和本地的一致)

      • 如果未超过半数accpetor响应,直接转为提议失败;
      • 如果超过多数Acceptor的承诺,又分为不同情况:

        • 如果所有Acceptor都未接收过值(都为null),那么向所有的Acceptor发起自己的值和提议编号n,记住,一定是所有Acceptor都没接收过值;
        • 如果有部分Acceptor接收过值,那么从所有接受过的值中选择对应的提议编号最大的值作为提议的值,提议编号仍然为n。但此时Proposer就不能提议自己的值,只能信任Acceptor通过的值,维护一但获得确定性取值就不能更改原则;
    • 第二阶段B:Acceptor接收到提议后,如果该提议版本号不等于自身保存记录的版本号(第一阶段记录的),不接受该请求;相等则写入本地。

至于编号N和数据Value的传递关系,可以参见:https://my.oschina.net/coderluo/blog/3102632

2.3 活锁问题

上面的流程可能会引发活锁问题,那么什么是活锁呢?

活锁指的是任务或者执行者没有被阻塞,由于某些条件没有满足,导致一直重复尝试—失败—尝试—失败的过程。处于活锁的实体是在不断的改变状态,活锁有可能自行解开。

那么上面的行为是怎么会引发活锁呢?接下来我们一起来分析下:

在整个选举过程中,每个人谁先来谁后到,“接受者”什么时间能够接到“提议者”的信息,是完全不可控的;

假设,第一个提案者A(Proposal)已经成功过了prepare阶段,准备向Acceptors广播发送Accept时,有一个更有钱土豪提案者B也向决议者(Acceptors)广播了prepare请求并在A的accept请求到之前发送给了决议者,这时毫无疑问,决议者会接收该请求,并记录在册。这时候,A的accept请求姗姗来迟,决议者对比此proposal的贿赂金额已经小于当前记录的prepare最大编号,因此不响应给提议者A,则提议者A收到的响应为过半,此提案废弃。这时它又用大于Proposer A的贿赂金额重新发起 preapre广播请求,这时提议者B的accept请求还没有到达决议者(Acceptors),因此Acceptor也接受了该prepare请求,将其记录在案,在之后提议者B发出的accept请求到达,决议者发现贿赂金额已经小于当前prepare的最大贿赂金额,因此拒绝响应,这样就会形成活锁问题。

三、其他

关于Paxos说的一致性,有人理解其指冗余副本(或状态等,但都是因为存在冗余)的一致性。这与关系型数据库中ACID的一致性说的不是一个东西。在关系数据库里,可以连副本都没有,何谈副本的一致性?按照经典定义,ACID中的C指的是在一个事务中,事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。那么,什么又是一致性状态呢,这跟业务约束有关系,比如经典的转账事务,事务处理完毕后,不能出现一个账户钱被扣了,另一个账户的钱没有增加的情况,如果两者加起来的钱还是等于转账前的钱,那么就是一致性状态。

“与其预测未来,不如限制未来”,这应该是Paxos协议的核心思想。

REF

初探|Zookeeper基础之Paxos算法详解
Paxos算法
Paxos协议超级详细解释+简单实例
分布式事务一致性协议paxos的分析
微信PaxosStore:深入浅出Paxos算法协议