Part 0 -- PAXOS


ZooKeeper<零> Paxos 算法浅析

本文基于 Wiki Paxos 算法 成文

介绍

Paxos 算法由 Lamport 大神于 1990 年提出的一种基于消息传递且具有高度容错特性的共识算法。

Mike Burrows(Google Chubby 作者)曾说过:

there is only one consensus protocol, and that’s Paxos

我们知道,在分布式系统中,节点通信分为两种模型

  • 共享内存
  • 消息传递

基于消息传递模型的分布式系统,必然需要考虑如下问题

  • 消息丢失
  • 消息重复
  • 消息延迟

在不考虑拜占庭错误的情况下,Paxos 算法解决的问题就是

在一个可能发生上述异常的分布式场景中,如何就某一个值达成一致,

保证不论发生以上任何异常,都不会破坏决议的共识。

如在一个分布式数据库系统中,若各节点初始状态一致,每个节点都执行相同的

操作序列,那么最后能得到一个一致的状态。

为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“共识算法”

WIKI Paxos 算法

角色

在 Paxos 算法中,角色:

  • proposer : 负责提出提案,相当于 zk 中的 leader
  • acceptor: 负责接受提案,相当于 zk 中的 follower
  • learner:负责学习提案,相当于 zk 中的 learner

在具体的实现中,一个进程可能不止充当一种角色

本文中使用的名词:

  • quorum: 超过半数的 acceptor 组成的集合(最早称之为 majority,这里直接使用 quorun)

  • proposal: 提案,由 proposal 提出,包含编号和值: proposal(n,v)

  • value:决议,被批准的提案,同样包括编号和值:value(n,v)

基准约束

首先由 proposer 提出 proposal(n,v),acceptor 接到提案后,可以选择接受提案,当该 proposal 获得了 quorum (大多数 acceptor)的支持后,则该 proposal 被批准(chosen),成为 value,由 learner 进行学习。

那么, Paxos 要解决的问题可以归纳为:

  • 只有被 proposer 提出的提案(proposal)才能被选定
  • 一次 Paxos 执行,只能有一个值(v)被选定
  • learner 只能获得被批准的提案(value)

推导

Lamport 大神通过不断加强上述的三个约束(主要是第二个约束),获得了 Paxos 算法。

1. P1

当只有一个 acceptor 存在时,acceptor 会选择它收到的第一个 proposal 作为 value(选定的提案),提案流程结束。

然而,一个 acceptor 会导致单点问题,即这个 acceptor 挂掉后,整个分布式集群就无法工作(zk 通过 ZAB 协议解决了单点问题,不过在选举的过程中,仍然是多 acceptor)。

多 acceptor 时, proposer 向 acceptor 集合 (acceptors) 发送 proposal,当有足够多的 acceptor 接受时,这个 proposal 就被选定,成为决议(value)。

这里的足够多,我们认为是超过半数的 acceptor ,亦即前文的 quorun。

因为两组 quorum,必然至少包含同一个 acceptor, 如果一个 acceptor 最多只能通过一个提案,那么就能保证最终只有一个提案被选定。

我们希望在即使只有一个提案被提出的情况下,仍然能产生 value,由此我们得到 P1:

P1: 一个 acceptor 必须接受它第一次收到的提案

注意,这里的 P1 是不完备的。当 acceptor 个数为偶数,又恰好一半 acceptor 接受 A 提议,另一半接受 B 提议时,此时无法产生决议。

提案被选定需要半数以上 acceptor 通过,意味着,一个 acceptor 必须能通过不止一个提案。当一个具有 v 值的提案被 quorum 通过,我们就认为提案被选定。

2. P2

我们基于上文以及基准约束 2:

一次 Paxos 执行,只能有一个值(v)被选定

可以看到, Paxos 并不要求只批准一个 proposal,也就是说可能会批准多个提案。只要提案的值,即 proposal.v 一致,就不违背基准约束 2 ,于是我们得出

P2: 一旦一个具有 v 值的提案 proposal(n,v) 被批准,则之后批准的提案必须具有 v 值

这里的之后,一般都是通过一个全局序号(zk 中指 zxid),来进行判断

3. P2a

批准一个 value,意味着多个 acceptor 接受了这个 value,因此可以对 P2 进行加强:

P2a:一旦一个 proposal(n,v) 被批准,则之后任何 acceptor 再次接受的提案,必须也具有 v 值

满足 P2a ,即满足 P2

但是由于通信是异步的,当已经产生 value 后,一个 proposer 和 acceptor 刚苏醒,而这个 proposer 提出了一个新的 proposal(n1,v1) 提案,根据 P1 ,这个 acceptor 应该接受,但根据 P2a,又不应该接受!怎么办?

4. P2b

我们想到在 proposer 端进行限制:

P2b:一旦一个 proposal(n,v) 被批准,则之后任何 proposer 提出的提案,必须具有 v 值

一个提案被 acceptor 接受前,需要由 proposer 提出,因此, 满足 P2b ==> P2a ==> P2

如何保证 P2b 呢?

我们假设 proposal(m,v) 提案被选定,根据 P2b, 则有 proposal(n,v’),当 n > m 时, v’ = v .

那么,如何来保证 v’ = v 呢?

5. P2c

P2c:若 proposal(n,v) 被提出,则存在一个 quorum 满足以下中的任一条件:

​ a) quorum 中所有 acceptor 都未接受编号小于 n 的提案

​ b) quorum 中所有 acceptor 已经接受所有编号小于 n 的提案中,最大的那个提案 v 值

证明过程如下:

假设具有value v的提案m获得批准,当n=m+1时,采用反证法,假如提案n不具有value v,而是具有value w,根据P2c,则存在一个多数派S1,要么他们中没有人接受过编号小于n的任何提案,要么他们已经接受的所有编号小于n的提案中编号最大的那个提案是value w。由于S1和通过提案m时的多数派C之间至少有一个公共的acceptor,所以以上两个条件都不成立,导出矛盾从而推翻假设,证明了提案n必须具有value v;

若(m+1)..(N-1)所有提案都具有value v,采用反证法,假如新提案N不具有value v,而是具有value w’,根据P2c,则存在一个多数派S2,要么他们没有接受过m..(N-1)中的任何提案,要么他们已经接受的所有编号小于N的提案中编号最大的那个提案是value w’。由于S2和通过m的多数派C之间至少有一个公共的acceptor,所以至少有一个acceptor曾经接受了m,从而也可以推出S2中已接受的所有编号小于n的提案中编号最大的那个提案的编号范围在m..(N-1)之间,而根据初始假设,m..(N-1)之间的所有提案都具有value v,所以S2中已接受的所有编号小于n的提案中编号最大的那个提案肯定具有value v,导出矛盾从而推翻新提案n不具有value v的假设。根据数学归纳法,我们证明了若满足P2c,则P2b一定满足。

—- WIKI

为了维护 P2c 的不变性,当一个 proposer 提出 proposal(n,v) 时,必须要知道某一个将要或者已经被 quorum 通过的编号小于 n 的最大编号的提案值。

我们需要限定「将要通过」的情况,毕竟我们无法预测未来。这表示,proposer 会请求 acceptor 不再接受任何编号小于 n 的提案。

6. 算法

上面的分析,可以推出如下算法:

1. Proposer

1.1 prepare
  • proposer 提交 proposal(n,v) 给 acceptors
  • proposer 要求 acceptor 做出如下承诺:
    • 保证不再通过任何小于编号 n 的提案
    • 如果存在已通过的编号小于 n 的提案,将通过的小于 n 的最大编号提案返回
1.2 commit/propose
  • 收到超过半数的 ack 回复,则产生 proposal(n, v),这里的 v 是所有响应中编号最大的提案的 v 值,若响应中不包含,则由 proposer 自己选择

2. Acceptor

P1a: acceptor 可以接受一个编号为 n 的提案,只要它还未响应任何编号大于 n 的 prepare 请求

可以看出: P1a 蕴涵 P1

2.1 prepare
  • 收到 propser 的 prepare(n.v) 请求,如果编号 n > 所有响应中最大的提案编号,返回已经通过的最大编号的提案(没有可以返回 nil)
2.2 commit/accept
  • 收到 proposer 的 accept 请求后,如果没有对编号大于 n 的 prepare 请求做出过响应,就接受这个提案

3. 整体描述

3.1 prepare 阶段:
  • proposer 发送 prepare(n,v) 给 acceptors
  • acceptor 收到 prepare(n,v) 后,如果 n 大于它已经响应的所有 prepare 请求编号, 则保证不再 accept 任何编号小于 n 的提案,同时将已经通过的最大编号的提案(如果存在)回复。(这里已经通过,指的是该 acceptor 接受的提案,而不是 prepare 响应的提案)
3.2 propose 阶段:
  • proposer 在收到大多数 acceptors 的回复后,根据回复,获取回复中编号最大的 value(如果所有回复中,都没有,则 value 可自行确定),向 acceptors 发送 accept(n,v) 请求
  • 在不违背 acceptor 对其他 proposer 的承诺下,acceptor 接受这个提案,否则拒绝。换句话说,即 如果 acceptor 收到一个针对编号 n 的提案的 accept 请求,只要它还未对编号大于 n 的 prepare 请求作出响应,它就可以通过这个提案

7. 流程图

我们以两个 proposer 和 3 个 acceptor 为例。

prepare 阶段,主要有两个方法

  • prepare(n, expected_v) : 由 proposer 发起一个编号为 n,值为 expected_v 的请求
  • promise(ack, accepted_n, accepted_v):由 acceptor 返回,ack 为应答,accepted_n 为 acceptor 已经通过提案的最大编号,accepted_v 为对应的值,没有则为 nil

accept/propose 阶段,也是两个方法

  • propose(n,expected_v):在该 proposer 收到超过半数 ack 后,发起 propose(n,expected_v) 请求,expected_v 为收到的应答中,最大编号的值,如果没有,就是自己的值
  • accept(ack, error): 在不违背对其他 proposer 的承诺下,acceptor 接受这个提案,返回(ack, nil), 否则返回 (ack, error)

: 这里不违背对其他 proposer 的承诺 ,指的是

  • 不响应编号比 n 小的提案
  • 不接受编号比 n 小的提案

WIKI 中说

acceptor 收到 prepare 消息后,如果提案的编号大于它已经回复的所有 prepare 消息(回复消息表示接受accept),则 acceptor 将自己上次接受的提案回复给 proposer,并承诺不再回复小于 n 的提案

这里的承诺不再回复小于 n 的提案 ,即指上面的两个不。

在 acceptor 收到 accept 请求前,如果收到了 prepare(n+1, v’),那个这个 accept 请求则不会被应答,或者返回一个 error

prepare

prepare phrase

P1 和 P2 分别向 A1/A2, A2/A3 发送 prepare 请求,A1/A3 都是正常应答,同时将各自的应答记录修改。

A2 先收到 P1 prepare 请求,responsed_n 置为 1, 同时给与 P1 ack, 后收到 P2 prepare(2, 2),根据规则,P2 的提案编号 2 大于 P1 的编号 1,所以,A2 将 responsed_n 置为 2, 同时回复 ack。这里 A2 在此之前,并没有批准,即 accept 任何提案,所以回复的 promise 应该为 promise(ack, nil, nil)

那么此时 P1 和 P2 都得到了半数以上的 ack ,都可以进行 accept 请求。

propose/accept

accept phrase

在第二阶段

P1, 向 A1, A2, A3 发起 propose(1, 1) 请求, 其中:

  • A1: 在 P2 发送请求之前,收到了 P1 的 propose 请求,在此之前只收到过 P1 的 prepare 请求,未对编号大于 1 的 prepare 请求做出过回应,遵守承诺,接受了 P1 的请求,回复 ack, accept(ack, nil, nil)
  • A2/A3:已经收到过 P2 的 prepare 请求,且 P2 编号 2, 大于 1,不回复 P1 或回复 error

所以 P1 得到 A1 的 ack ,未超过半数

P2, 向 A1, A3 发起 propose(2, 2) 请求,其中:

  • A1: 未作出过大于 2 的 prepare 响应,接受 P2 的请求,修改 responsed_n,accepted_n/v 同时返回 accept(ack)
  • A3:同样未违背承诺,修改 responsed_n, accepted_n/v , 返回 accept(ack)

P2 收到半数以上的 ack ,提案被选中。

之后 A1 再次去发起提案的时候,此时 n 会递增到 3,在 prepare(3,1) 阶段,会收到 A1,A3 的 ack,形如 propose(ack, 2, 2), A1 收到半数请求后,从中挑出编号不大于 3 的最大编号,同时修改自己的值, 从 1 变为 2,再次发送 prepare(3,2),会得到超过半数的 ack , 提案被选中,结束。

本轮 paxos 中,最终选择的值为 2

8. Paxos 活锁(LiveLock)

我们以 P1, P2 + A 为例

prepare phrase LiveLock

如图示,每次 P1 或 P2 propose 时, 总是会发现更高的 prepare 编号,从而不断进行 prepare 。

一般这种情况很少见,可以通过 随即睡眠-重试 的方法避免

Multi-Paxos

Fast-Paxos

参考


文章作者: peifeng
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 peifeng !
 上一篇
Part 1 -- ZOOKEEPER 概要 Part 1 -- ZOOKEEPER 概要
ZooKeeper 作为一款为分布式应用而生的分布式协同服务,在很多分布式系统中都留下了它的身影。虽然现在出现了诸如 consul/etcd/doozerd 等各种竞品,但依旧活跃于各个分布式应用中。
2020-04-03
下一篇 
Build Your Own Blog Build Your Own Blog
某一天,突发奇想,想搭建一个 blog 来沉淀下自己。遂有该片。 本文主要介绍通过 hexo 搭建 blog,使用 github + jsDelivr 加速静态资源访问, 通过 nginx + https 代理 blog。
2020-03-31
  目录