1、paxos算法

1.1 基本定义

算法中参与者主要分为三个角色，同时每个参与者又可兼领多个角色

  • proposer 提出议案，提案信息包括提案编号和提议的value

  • acceptor 收到提案后可以接受（accept）提案

  • learner 只能“学习”被批准的提案

算法保证一致性的基本语义：

  • 决议（value）只有在被proposers提出后才能被批准（未经批准的决议称为“提案”）

  • 在一次paxos算法的执行实例中，只批准（chosen）一个value

  • learners 只能获得被批准的（chosen）的value

由上面三个语义可演化为四个约束：

  • P1：一个acceptor必须接受（accept）第一次收到的提案

  • P2：一旦一个具有value v的提案被批准（chosen），那么之后任何acceptor再次接受（accept）的提案必须具有value v

  • P3：一旦一个具有value v的提案被批准（chosen），那么以后任何proposer提出的提案必须具有value v；

  • P4：如果一个编号为n的提案具有value v，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于n的任何提案，要么他们已经接受（accept）的所有编号小于n的提案中编号足底啊的那个提案具有value v

1.2 基本算法（basic paxos）

算法（决议的提出与批准）主要分为两个阶段

  1. prepare阶段：

    1. 当proposer希望提出方案V1，prepare请求序列号S1

    2. 当acceptor接收到prepare请求S1，检查自身上次回复过的prepare请求的序列号Sx

      1. 如果Sx>S1，则忽略此请求，直接结束本次批准过程。

      2. 否则检查上次批准的accept请求paxos算法 - 图1，并且回复paxos算法 - 图2，如果之前没有进行过批准，则简单回复OK

  2. accept批准阶段

    1. 经过一段时间，收到一些acceptor回复，回复可分为以下几种

      1. 回复数量满足多数派，并且所有的回复都是，则proposer发出accept请求，请求内容为议案paxos算法 - 图3

      2. 回复数量满足多数派，但是有的回复为：paxos算法 - 图4……则proposer找到所有回复中超过半数的那个，假设为paxos算法 - 图5，则发出accept请求，请求内容为议案paxos算法 - 图6

      3. 回复数量不满足多数派，proposer尝试增加序列化为S2，转1继续执行

    2. 经过一段时间，收到一些Acceptor回复，回复可分为以下几种:

      1. 回复数量满足多数派，则确认V1被接受

      2. 回复数量不满足多数派，V1未被接受，proposer增加序列化为S2，转1继续执行

      3. 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即接受并回复这个请求

1.3 算法优化（fast paxos）

paxos算法在出现竞争的情况下，其收敛速度很慢，甚至可能出现活锁的情况，例如当有三个及以上的proposer在发送prepare请求后，很难有一个proposer收到半数以上的回复而不断地执行第一阶段的协议。因此，为了避免竞争，加快收敛速度，在算法中引入了一个Leader这个角色，在正常情况下同时应该最多只能有一个参与者扮演Leader角色，而其他参与者则扮演acceptor的角色，同时所有人又都扮演learner的角色
在这种优化算法中，只有Leader可以提出议案，从而避免了竞争使得算法能够快速地收敛而趋于一致，此时的paxos算法在本质上就退变为两阶段提交协议。但在异常情况下，系统可能会出现多个Leader的情况，但这并不会破坏算法对一致性的保证，此时多个Leader都可以提出自己的提案，优化算法就退化成了冤死的paxos算法。
一个Leader的工作流程主要有分为三个阶段：

  • 学习阶段 向其他的参与者学习自己不知道的数据（决议）

  • 同步阶段 让绝大多数参与者保持数据的一致性

  • 服务阶段 为客户端服务，提议案

paxos算法 - 图7

学习阶段

当一个参与者成为了Leader之后，它应该需要知道绝大多数的paxos实例，因此就会马上启动一个主动学习过程。假设当前的新Leader早就知道了1-134、138和139的paxos实例，那么他会执行135-137和大于139的paxos实例的第一阶段。如果只检测到135和140的paxos实例有确定的值，那它最后就会知道1-135以及138-140的paxos实例

同步阶段
此时的Leader已经知道了1-135/138-140的paxos实例，那么它就会重新执行1-135的paxos实例，所以保证绝大多数参与者在1-135的pasos实例上是保持一致的。至于138-140的paxos实例，它并不马上执行138-140的paxos实例，而是等到在服务阶段填充了136、137的paxos实例之后再执行。这里之所以要填充间隔，视为了避免以后的Leader总是要学习这些间隔中的paxos实例，而这些paxos实例又没有对应的确定值。

服务阶段
Leader将用户的请求转化为对应的paxos实例，当然，它可以并发的执行多个paxos实例，当这个Leader出现异常之后，就很有可能造成paxos实例出现间隔。