跳到主要内容

Paxos 算法

Paxos 算法（CP）​

少数服从多数，最终达成一致。

基本概念​

  1. Proposer: 提案人
    • Proposal:提案
      • proposal id
      • value 决策
  2. acceptor 决策者
  3. learner 学习者

约束​

  1. 决策(value)只有被提案人(proposer)提出之后才能被批准(chosen)
  2. 一次 paxos 算法执行的实例中，只批准(chosen)一个值(value)
  3. 学习者(learners)只能获得被批准(chosen)的提案(value)

paxos 算法就是对上面的约束不断加强得到的。

情景一：一个分布式系统，存在多个提案人同时提出提案，多个决策者接收提案。

proposer1 --> 提出 value=A

proposer2 --> 提出 value=B

acceptor1

acceptor2

acceptor3

注意：这些提案中，只有一个提案会被接收

一个提案必须被半数以上的 acceptor 接收

P1 约束

一个 acceptor 必须接收第一次收到的提案

P2 约束

如果某个 value 为 v 的提案被批准，那么之后批准的提案必须具有 value v

P2a

一旦一个具有 value v 的提案被批准，那么之后任何 acceptor 再次接收的提案必须具有 value v

P2b

一旦一个具有 value v 的提案被批准，那么以后任何 proposer 提出的提案必须具有 value v

p2c

如果一个编号为 n 的提案具有 value v，该提案被提出，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于 n 的任何提案(这里指的是 n 是 acceptor 接收到第一个提案)，要么他们已经接受（accept）的所有编号小于 n 的提案中编号最大的那个提案具有 value v（这里指的是在接收编号 n 提案之前，已经接收到了其他编号小于 n 的提案）。

p1a

当且仅当 Acceptor 没有回应过编号大于 n 的 prepare 请求时，Acceptor 接受（accept）编号为 n 的提案。

paxos 算法的 2 个阶段​

Prepare(N) ：表示 proposer 向 acceptor 发起一个编号为 N 的准备(prepare)请求。只有编号，没有值

Promise(N,I,V)

  1. acceptor 向 proposer 承诺，不再接收(accept)编号小于 N 的请求
  2. 此时 acceptor 还是会接收任何 prepare 请求的。
  3. 向 proposer 返回已接收的最大提案（编号为 I，值为 V） I/V 可以为 null

Accept(N,V) 表示 proposer 向 acceptor 发起提案。

Accepted(N,V) 表示 acceptor 已接收编号为 N，值为 V 的提案了。

Reject(maxN) 表示 acceptor 已经承诺不在接收编号小于 maxN 的提案。

paxos 算法的核心：如果(在 prepare 阶段发现)某个值已经被选定，那么后续所有被选定的提案都必须是同一个值

准备阶段(发现已有共识)​

  1. proposer 在提出一个提案前，要与超过半数的 acceptor 进行通信，向它们发送编号为 N 的 Prepare 请求。 （Prepare(N)）

  2. acceptor 在接收到编号为 N 的 prepare 请求后，会进行判断

    • 如果之前没有响应过任何 Prepare 请求，那么会接收编号为 N 的请求，同时向 proposer 承诺不会再接收编号小于 N 的 Prepare 请求 （Promise(N,null,null)）
    • 如果编号 N 小于已经响应过的 Prepare 请求的编号，则拒绝提案。 Reject(maxN)
    • 如果编号 N 大于自身已经响应过的所有 Prepare 请求的编号，那么它会将它以前接收过的编号最大的提案作为响应反馈给 proposer，同时承诺不再接收任何编号小于 N 的提案 （Promise(N,M,Vm)）

批准阶段(达成新共识)​

  1. 对 prepare 阶段的响应结果进行分析：

    • 如果没有超过半数的节点 promise，则增加编号，并等到一段时间之后，再进入 prepare 阶段。
    • 有超过半数的节点 promise
      • 如果发现有 acceptor 已经接受过其他编号的提案（编号为 M, 值为 Vm），那么 proposer 会将要值修改为 Vm accept(N,Vm)
      • 如果没有发现 acceptor 获取到其他提案 accept(N,V)

  2. 向过半数的 Acceptor 发送 accept(N,V) 或 accept(N,Vm) 取决于 prepare 阶段是否有收到其他 acceptor 响应的其他编号的值。

  3. acceptor 接收到请 accept 请求后会进行判断

    • 如果没有响应过编号大于 N 的 prepare 请求---> 接收提案。

    • 如果已经响应过编号大于 N 的 prepare 请求---> 拒绝

    • 过半数 acceptor 同意，accepted(N,V), proposer 会向 learner 广播

    • 没有过半数的 acceptor 同意，增大提案编号，等待一段时间，重新进入准备阶段。

proposer                     acceptor
      -----> prepare(N)
                              1. maxN == null ,value ==null{
                                   maxN = n
                             <-----return promise(N)
                              }

                              2. maxN != null, value ==null
                                2.1 maxN > N
                             <-----return reject(maxN)
                                2.2 maxN <= N
                                    maxN = n
                            <-----return promise(N)
                              3. maxN != null, value != null
                                  3.1 maxN > N
                              <-----return reject(maxN)
                                  3.2 maxN <= N
                              <-----return promise(N,maxN,value)
                                            承诺不在响应编号 < N 的 prepare
                                            不在接受编号 < N  的 accept

活锁问题​

multi-paxos 算法​

multi-paxos 针对多值序列。

Multi-paxos 首先会选取出一个 leader 节点。

选取 leader 的方式：通过一个 prepare 阶段，获取多数节点 promise 的节点成为 leader。

后续客户端所有的请求都由 leader 节点处理。

multi-paxos 性能相对于 paxos 提升了 1 倍（多值序列，只用一次 prepare 阶段）。

multi-paxos 避免了活锁问题。

面试准备​

解释下 paxos 算法是什么？ 它主要解决分布式系统中的什么问题？​

paxos 算法是一个分布式一致性共识算法，主要解决在分布式系统中多个节点对某个值达成一致的问题。 即使在网络故障，节点宕机，消息延迟或丢失等异常情况下，paxos 也能保证所有节点最终对同一个提案达成一致， 不会出现不同节点选择不同值的情况。只要有过半数节点存活，系统就能继续工作。

paxos 算法有哪些角色？ basic paxos 分为哪几个阶段？请描述每个阶段的作用。​

paxos 中有三个角色，分别是 proposer，acceptor，learner

proposer 发起提案，请求 acceptor 接受某个值 acceptor 对提案进行投票决策，决定是否接收提案 learner 学习最终被选定的值。

两个阶段：准备阶段和批准阶段 准备阶段：

  1. proposer 选择一个提案编号 n，向超过半数的 acceptor 发送 Prepare(n) 请求。注意：这里携带的是编号，并没有携带具体的值
  2. acceptor 的响应
    • 如果 n 大于 acceptor 之前见过的所有提案编号 acceptor 对 proposer 承诺，不在接收编号小于 n 的提案 promise(n,null,null) 如果之前已接收过提案，则返回已接收过的提案， promise(n,m,v)
    • 如果 n 小于等于已承诺的编号：决绝请求， reject(n)

接收阶段

  1. proposer 发起 accept 请求(理论上只有向超过半数的 accepter 节点发送即可，实际上会向所有 accepter 节点发送)
    • 如果收到超过半数的 promise 响应
      • 确定 value
        • 如果响应中有已接收的提案，选择编号最大的提案的 value
        • 如果都没有已接收的提案，可以选择自己的 value
      • 向 这些 acceptor 发送 accept(n,value) 请求
  2. acceptor 决策，如果没有违反之前的 promise，接收提案, 否则拒绝
  3. 广播给 learner
    • 如果超过半数的 acceptor 接收了提案，该值被选定
    • acceptor 将选定的值广播给所有的 learner

假设在一个 5 个节点的集群中，有 2 个 proposal 同时发起提案，可能会发生什么情况？paxos 如何处理这种冲突？​

可能会出现活锁问题。

P1,P2 同时发起提案。 P1 的提案(id=100)获得过半数节点的承诺，P2 的提案(id=101)也获得了过半数节点的承诺。 注意这时，部分节点对 P1 的承诺会被覆盖。因为 P2 提案的 ID 大于 P1 提案的 ID。P1 发送 Accept(100,v1) 请求，会被拒绝。此时 P1 会增大提案的 ID（改为 102），继续向超过半数的 acceptor 节点发送 Prepare(102)请求,这就覆盖了 P2 的 Prepare(101) 请求。然后 P2 会增大提案 ID。这就会出现了一个死循环。我们称这个问题为活锁问题。

如果解决 paxos 算法的活锁问题？

  1. 在冲突后，等待一个随机的时间。
  2. paxos 本身不能解决活锁问题，需要用到 multi-paxos 算法。（选举一个唯一的 leader，只有 leader 才能发起提案）

为什么 paxos 需要“过半数“机制？ 如果降低这个要求会有什么问题？​

paxos 采用过半数机制，是为了保证数据一致性问题。

假设同时发起了 2 个提案（5 个节点集群）。

P1 提案 (n1，v1) 被节点 1，2，3 接受 P2 提案 (n2, v2) 会被节点 3 拒绝。

如果降低标准

P1 提案 (n1，v1) 被节点 1，2 接受 P2 提案 (n2，v2) 被节点 4，5 接受

此时，如果 P3 提案(n3,v3) 被发送给 2，3，4 那么就会出现

  • 节点 2 告诉 P3,它接收了 v1
  • 节点 4 告诉 P3,它接收了 v2

此时，P3 就无法确定应该使用哪个值了。

multi-paxos 相比 basic paxos 做了哪些优化？ 在实际工程中为什么要更常用 multi-paxos 或 raft 而不是 basic paxos？​

multi-paxos 引入了一个稳定的 leader，避免了多个 proposer 竞争导致的活锁问题。

multi-paxos 只用通过一次 prepare 阶段就能选取出一个稳定的 leader， 在多值序列时（假设 100 条），节省了 99 次 prepare 阶段。性能提升 1 倍。

最后于 更新