顿搜
飞过闲红千叶，夕岸在哪
类目归类
01. Paxos共识算法——分布式算法专题
10/07
一、相关论文
| 作者 | 时间 | ||
|---|---|---|---|
| Lamport | 1990未通过 | The Part-Time Parliament | |
| Lampson | 1996 | How to Build a Highly Availability System using Consensus | |
| Lampson | 1997 | Revisiting the PAXOS algorithm | |
| Lamport | 1998正式发表 | The Part-Time Parliamen | |
| Lamport | 2001 | Paxos Made Simple | |
| 2006 | 关于Chubby的论文 |
二、算法组成
Paxos是一种算法，它包含两部分，其中一部分是核心算法；另一部分是基于核心算法扩展的完整算法。
| - | 核心算法 | 完整算法 |
|---|---|---|
| The Part-Time Parliament | 单法令议会（Single-Decree Synod） | 多法令国会（Multi-Decree Parliament） |
| Revisiting the PAXOS algorithm | basic-paxos | multi-paxos |
| Paxos Made Simple | 共识算法（Paxos Consensus Algorithm） | 实现一个状态机（Implementing a State Machine） |
三、共识算法
3.1 共识问题
共识问题就是多个进程对一个值达成一致。
每个进程都可以提议（propose）一个自己想要的值，但是最终只有一个值会被选中，并且所有进程对这个选中的值达成一致。
共识问题中的值（value）可以是非常简单的，比如一个整型数字，也可以是任何非常复杂的信息。
3.1.1 两个要求
consensus算法有两个要求，即安全要求和存活要求。
- 安全（safety）要求是指：
（1）只有一个被提议的值可能被选中。
（2）只有唯一的一个值被选中。
（3）只有一个值实际上已经被选中，一个进程才能学习到这个值。
- 存活（liveness）要求是指：
（1）某个被提议的值最终一定会被选中，并且如果一个值被选中，那么一个进程最终能够学习到这个值。
3.1.2 三个角色
Paxos consensus算法中有3个角色，分别是
- 提议者（proposer）：负责提出一个值。
- 接受者（acceptor）：负责选择一个值（acceptor一般是奇数个）
- 学习者（learner）：负责学习到被选中的值。
这些角色是逻辑角色，它们完成算法中的不同功能。一个进程可以容纳多个角色
3.1.3 基本概念
- 提议（proposal），提议是包含一个提议编号和一个值的值对。我们用{n，v}表示一个提议，其中n是提议编号；v是一个任意值。
例如{1，x}表示编号为1、要提议的值为x的一个提议
Basic Paxos算法分为两个过程，即选择一个值和学习一个值
- 提议编号（proposal number）
这个提议编号是唯一且递增的，更准确地说，提议编号在一组进程中是全局唯一且递增的。
Lamport给出了一种简单且有效的方法来生成这个提议编号：每个进程都被分配一个唯一的进程标识（processid）（假设为32位），每个进程都维护一个计数器（counter）（假设为32位），每发出一个提议都把计算器加1。这个64位的组合值作为提议编号
3.2 共识过程
3.2.1 选择值过程
选择一个值的过程是Paxos consensus算法的核心，
而Paxos consensus算法又是Paxos算法的核心，所以选择值可谓是核心中的核心
| 阶段 | 描述 |
|---|---|
| 1(a) | 一个proposer 选择一个提议编号 n，并且发送编号为n 的prepare 请求给大多数 acceptor。 |
| 1(b) | 如果-个acceptor 收到一个编号为n 的 prepare 请求，并日n 比它之前已经回复的任何 prepare 请求中的编号都大，那么它给出回复，承诺不再接受任何编号比n 小的提议，并且在回复中携带（如果有的话）已经接受的编号最大的提议 |
| 2(a) | 如果 proposer 收到大多数 acceptor 回复的一个其编号为 n 的prepare 请求，那么它给这些 acceptor 中的每个都发送一个accept 请求，这个请求携带一个编号为 n 的提议，提议的值是所有回复中编号最大的提议中的值，如果回复中没有提议，则这个值可以是任何值。 |
| 2(b) | 如果一个acceptor 收到一个编号为n的accept 请求，那么除非它已经回复了一个编号比n大的 prepare 请求，否则它会接受这个提议。 |
消息分解
| 阶段 | 消息 | 消息说明 |
|---|---|---|
| 1(a) | prepare(n) | 这个消息携带一个参数n，n 是提议编号。简写成 PP(n) |
| 1(b) | promise(n, (n1,v}) | 在Lamport 的描述中没有对 prepare 的回复消息起名，只是将这个消息称为 “对 prepar的回复”。这里将这个消息命名为 promise. promise 消息携带两个参数，即n和{n1, v}, 其中n是承诺的提议编号，{n1,v}是一个提议，这个提议的编号是n1，值是v。简写成 PM(n,{n1,v}) |
| 2(a) | accept({n,v}) | 这个消息携带一个参数口{n, v},{n, v}是一个提议，这个提议的编号是n，值是v。简写成 A({n,v}) |
| 2(b) | 无消息 | - |
需要持久化存储的信息
| 持久化存储的信息名 | 简写 | 持有者 | 说明 |
|---|---|---|---|
| Tried Number | tn | proposer | 上次使用过的提议编号，记成 p.tn，表示存储在 proposer中的 Tried Number |
| Promised Number | pn | acceptor | 承诺过的提议编号，记成 a.pn，表示存储在 acceptor 中的Promised Number |
| Accepted Proposal | {an,av} | acceptor | 己接受的一个提议，提议编号是a，提议的值是 v，记成a.{an.av}，表示存储在 acceptor 中的 Accepted Proposal |
具体化过程
| 阶段 | 具体描述 |
|---|---|
| 1(a) | 一个proposer生成一个新的提议编号n,n＞p.tn,将n记录到p.tn中,并且发送prepare(n)消息给大多数 acceptor |
| 1(b) | 如果一个 acceptor 收到一个prepare(n)消息，并且n＞a.pn，则将n记录到a.pn 中。如果有接受过的提议a.{an,av}，则回复 promise(n,a.{an,av})消息；如果没有，则回复 promise(n,null)消息 |
| 2(a) | 如果 proposer 收到大多数 acceptor 回复的承诺编号为n的promise 消息，则构建一个新的提议，提议编号是n，值v按下面的规则确定：(1)如果在所有这些 prornise 消息中有携带提议的，则用提议编号最大的提议中的值 (2)如果在所有这此 promise 消息中没有任何一个携带提议的，则可以用 proposer 自己要提议的值, 这个proposer 给这些 acceptor 中的每一个都发送一个 accept(n,v)消息 |
| 2(b) | 如果—个acceptor 收到accept(n.v)消息，且n>=a.pn. 则把a.{an.av}赋值成 {n.v} |
- 承诺（promise）一个提议编号就具体体现为将一个提议编号持久化存储
- 接受（accept）一个提议就具体体现为将一个提议持久化存储。
综合消息与存储的具体化过程
| 阶段 | 执行者 | 收到消息 | 执行条件 | 持久化存储 | 发送消息 | 发送目标 |
|---|---|---|---|---|---|---|
| 1(a) | proposer | - | n> p.tn | p.tn=n | PP(n) | 大多数 acceptor |
| 1(b) | acceptor | PP(n) | n> a.pn | a.pn=n | PM(n,a.{an, av}) | 发送消息的 proposer |
| 2(a) | proposer | PM(n,{n1, v}) | 从大多数acceptor 收到消息 | - | A({n.v}) | 1(a)中同一批大多数acceptor |
| 2(b) | accentor | A({n.v}) | n >= a.pn | a.{an.av}= {n,v} | - | - |
3.2.2 progress保证
选择值过程的progress保证选择值的过程不能完全保证progress，也就是不能保证最终会达成共识。
举个活锁例子
proposer1发送给acceptor3的accept消息被proposer2发出的prepare消息取消，
proposer2发出的accept消息又被proposer1发出的第二轮prepare消息取消，
如此往复进行下去，存在永远都不会达成共识的可能，也就是出现了活锁。
为了避免出现这种情况，可以选出一个proposer，作为distinguished proposer，
只有这个distinguished proposer才能发起提议，从而避免了活锁情况的发生
3.3 学习过程
3.3.1 学习值必要性
既然共识问题已经得到解决，那么Paxos算法还需要有学习值的过程吗？
当然需要，因为选择值的过程有两个问题没有得到解决：
- 需要进行多次投票，所有进程才能达成一致。需要优化这个达成一致的过程，在有值被选中后，尽快让所有进程达成一致。
- 更重要的一个问题是，即便所有进程已经对选中的值达成一致，进程也无法知道这个状态已经达到。
即便某个acceptor接受了多个提议，并且每个提议中的值都是同一个值，这个acceptor也不能确定这个值就是被选中的值。
3.3.2 学习值过程
| 阶段 | 描述 |
|---|---|
| 1(a) | 当acceptor接受一个提议后，向所有的 learner 通知这个提议 |
| 1(b) | 如果 learner收到 acceptor 的通知，则接受这个提议。如果 learner 接受从大多数 acceptor 收到的某个提议，则这个learer 接受提议中的值 |
当learner接受（accept）一个值后，这个进程就知道这个值被选中了，如果所有进程都接受了一个值，那么所有进程也就达成了一致。
3.3.3 减少消息数量
每个接受提议的acceptor向每一个learner都发送一个learn消息，earn消息的数量是acceptor的数量与learner的数量的乘积。
为了减少learn消息的数量，可以指定一个learner作为distinguished learner，acceptor接受提议后，向distinguished learner发送learn消息，distinguished learner收到learn消息后，向其他learner发送learn消息
- ALearn: 将acceptor发送给distinguished learner的learn消息称为
ALearn消息, ALearn简写成AL - LLearn: 将distinguished learner发送给其他learner的消息称为
LLearn消息, LLearn简写成LL
与distinguished proposer一样，distinguished leaner并不要求唯一，多个distinguished leaner并不影响Paxos算法的正确性。
具有distinguished leaner的学习值过程:
| 阶段 | 描述 |
|---|---|
| 1 | 将接受的提议通过 ALcarn 消息发送给 distinguished learner |
| 2(a) | distinguished learner 收到大多数 acccptor 的 ALcarn 消息后，接受提议中的值，并向其他 learner 发送 LLearn消息 |
| 2(b) | 其他 learner 收到 LLearn 消息后，接受这个值 |
综合消息与存储的具体化过程
| 阶段 | 执行者 | 收到消息 | 执行条件 | 持久化存储 | 发送消息 | 发送目标 |
|---|---|---|---|---|---|---|
| 1 | acceptor | - | - | - | AL({n,v}) | distinguished learner |
| 2(a) | distinguished learner | AL({n,v}) | 从大多数 acceptor 收到消息 | - | LL(v) | 其他所有 learner |
| 2(b) | learner | LL(v) | - | - | - | - |
承担distinguished learner角色的进程可能会发生宕机，因此可以指定多个learner作为distinguished learner，这样可以提高系统的可靠性，但同时也增加了通信成本，也就是有更多的消息发送。
一般只选择一个learner作为distinguished learner。
但是无论哪种学习值的过程，都不能保证消息丢失后仍然能够学习到最终的值。没有收到LLearn消息的进程可以重新发起一个提议，学习到最终的值。
3.4 两个过程合并
共识过程有2个阶段4个步骤，学习值的过程有2个阶段3个步骤
Paxos consensus算法是由这两个过程组合而成的。
在完整的Paxos consensus算法中，选择值的第4个步骤和学习值的第1个步骤是一个步骤，选择值的第4个步骤是这个步骤的前半部分，学习值的第1个步骤是这个步骤的后半部分
最终共识算法如下
| 阶段 | 执行者 | 收到消息 | 执行条件 | 持久化存储 | 发送消息 | 发送目标 |
|---|---|---|---|---|---|---|
| 1(a) | proposer | - | n> p.tn | p.tn=n | PP(n) | 大多数 acceptor |
| 1(b) | acceptor | PP(n) | n> a.pn | a.pn=n | PM(n,a.{an, av}) | 发送消息的 proposer |
| 2(a) | proposer | PM(n,{n1, v}) | 从大多数acceptor 收到消息 | - | A({n.v}) | 1(a)中同一批大多数acceptor |
| 2(b) | accentor | A({n,v}) | n >= a.pn | a.{an,av}= {n,v} | AL({n,v}) | distinguished learner |
| 3(a) | distinguished learner | AL({n,v}) | 从大多数 acceptor 收到消息 | - | LL(v) | 其他所有 learner |
| 3(b) | learner | LL(v) | - | - | - | - |
Paxos consensus算法是一个三阶段算法
四、完整算法
Paxos consensus算法可以确定一个值，如果运行多个Paxos consensus算法，就可以确定多个值，将这些值排列成一个序列，这就是完整的Paxos算法。
Paxos完整算法，或者叫作Multi Paxos算法，就是多次运行Paxos consensus算法，形成多个实例的算法。
其中一种是独立实例运行的完整Paxos算法；另一种是只运行一次prepare消息的完整Paxos算法。
无论哪种方式，Paxos算法都会产生这样一个结果：
类似于每个进程都会形成一个数组，数组中的每个元素都是一个达成一致的值。
4.1 独立实例运行
4.1.1 算法简述
在Paxos consensus算法的消息中添加一个实例编号，也就是instanceid参数，简写成i
| 阶段 | 执行者 | 发送消息 |
|---|---|---|
| 1(a) | proposer | prepare(i,n) |
| 1(b) | acceptor | promise(i,n, {n1,v}) |
| 2(a) | proposer | accept(i, {n,v}) |
| 2(b) | acceptor | alearn(i,{n,v}) |
| 3(a) | distinguished learner | llearn(i.v) |
| 3(b) | learner | - |
添加了instanceid的Paxos consensus算法
| 阶段 | 执行者 | 收到消息 | 执行条件 | 持久化存储 | 发送消息 | 发送目标 |
|---|---|---|---|---|---|---|
| 1(a) | proposer | - | n > p.tn[i] | p.tn[i]=n | PP(i, n) | 大多数 acceptor |
| 1(b) | acceptor | PP(i,n) | n> a.pn[i] | a.pn[i]=n | PM(i,n,a.{an, av}[i]) | 发送消息的 proposer |
| 2(a) | proposer | PM(n,{n1, v}) | 从大多数acceptor 收到消息 | - | A(i,{n.v}) | 1(a)中同一批大多数acceptor |
| 2(b) | accentor | A(i,{n,v}) | n >= a.pn[i] | a.{an,av}[i]= {n,v} | AL(i,{n,v}) | distinguished learner |
| 3(a) | distinguished learner | AL(i,{n,v}) | 从大多数 acceptor 收到消息 | a.{an,av}[i]= {n,v} | LL(i,v) | 其他所有 learner |
| 3(b) | learner | LL(i,v) | - | - | - | - |
4.1.2 脑裂处理
Paxos consensus算法会保证即便有多个进程认为自己是leader，也就是出现脑裂的行为，每个实例最终也只能有一个值被选中
4.1.3 空洞处理
在每个实例中，提议编号都是重新开始的，这也就意味着每个实例都是相互独立的。
一个leader可以同时发起对多个实例的值的提议。
也就是说，leader不必等第一个实例的值确定后，再开始第二个实例，各实例之间是可以并发执行的。
这可能会导致出现一种情况：如果在第一个实例的值的确定过程中出现消息丢失，或者某个消息延时，导致最终第一个实例的值没有确定，同时，leader开始了第二个实例，并且第二个实例的值成功确定，那么第一个实例的值是空的，而第二个实例的值是确定的。这种情况被称为空洞。
如果leader发现某个消息在一定的时间内没有得到回复，那么leader可以重发这个消息，重复的消息对Paxos的正确性是没有影响的。
通过重发机制，空洞最终会被填补上。
如果在leader重发消息前，另一个进程成为新的leader，则情况会有所不同。
- 如果旧的leader的提议已经被接受，那么新的leader会继续保持这个提议；
- 如果旧的leader的提议还没有被接受，则新的leader可以提议一个新的值。
不管怎样，这个空洞都会被填补上。
4.2 只运行一次prepare消息
在没有多个leader出现的情况下，每个实例都要经历3个阶段（其中有5个消息的传递），其值才能成功确定。
在有多个进程都认为自己是leader的情况下，实例都要经历超过3个阶段，使用更多的消息才能确定实例的值。
4.2.1 算法简述
分析前面所讲的独立实例运行的完整Paxos算法，可以总结出这样一条规律：
每个实例都是相互独立的，且从头开始编号运行，而且到第二阶段才开始提议具体的值，相当于每个实例的prepare阶段都是相同的，所以leader可以为所有的实例发送一个共同的prepare消息，也就是所有的实例共用第一阶段。
4.2.2 脑裂处理
每个进程成为leader后都会重新执行第一阶段，在第一阶段会重新生成一个新的提议编号，只要进程一直认为自己是leader，就会保持提议编号不变。
在第二阶段，如果accept消息失败，则进程要么放弃认为自己是leader，要么继续认为自己是leader，选择一个新的提议编号，重新执行第一阶段。
4.2.3 空洞处理
可以通过重试把空洞填补上。
如果有新的leader出现，则新的leader要么替旧的leader完成剩下的工作，也就是继续提议旧的leader要提议的值；要么提议一个新值。到底执行两者中的哪一个，要看新的leader在什么时间点执行prepare阶段。
五、算法应用于状态机
在实际中，Paxos算法的一种应用就是实现复制状态机。
在Lamport的“Paxos Made Simple”论文中，就使用了“实现状态机”作为完整Paxos算法这部分的标题。
5.1 状态机概念
- 状态机（state machine）
状态机是构建服务的一种常见方法。服务具有一个初始状态，服务接受动作（action），服务每接受一个action，内部状态就发生一次迁移，达到一个新的状态。
- 确定状态机（deterministic state machine）
确定状态机中所有的命令都会产生确定的输出结果，并且把状态机带入一个确定的状态。
- 复制状态机（replicated state machine）
为了达到高可用、故障容忍，服务冗余是常见的手段，采用状态机模式的服务，实现冗余的方式就是在多台机器上部署这个服务，也就是可以使用一组server，每一个server都独立部署一个状态机，每个状态机都会以相同的顺序执行所有客户端的命令
如果所有的server都执行相同序列的命令，那么它们会产生相同序列的状态和结果，让这些服务具有相同的状态。
我们称这样的状态机为复制确定状态机（replicated deterministic state machine），一般简称为复制状态机（replicated state machine）。复制状态机是分布式领域常用的一种技术。
5.2 状态机应用
客户端（client）连接server1，向server1发送命令，server1按照接收到的顺序在状态机上执行所有命令。
并且服务器之间存在一种机制——把server1上的所有命令复制到其他服务器上，其他服务器也会按照同样的顺序在自己的状态机上执行所有命令。
当server1发生宕机后，客户端可以转而连接server2，从server2的状态机上取得结果。
服务器之间的这种复制机制的实现方法有很多，可以采用Paxos算法，也可以采用Raft算法和Zab算法
5.3 Paxos实现复制状态机
为了保证所有的服务器都执行相同序列的状态机命令，我们实现一系列Paxos consensus算法的实例，其中第i个实例所选择的值就是第i个状态机的命令。
一台服务器被选出作为leader，客户端发送命令给leader，leader决定每一个命令应该出现在什么位置。
例如，如果leader决定某个客户端命令应该是第135个命令，那么leader会试图让这个命令被选成Paxos算法的第135个实例的值。
5.3.1 空洞处理
Paxos算法允许多个实例同时运行，这会导致空洞的出现，但是算法可以保证在后面的执行中把空洞填补上。
然而，这种填补仍然会影响复制状态机的执行，如果采用Paxos算法实现复制状态机，还需要对并发实例和空洞做进一步的处理。
因为状态机要按照顺序执行所有命令，所以我们可以采用最粗暴的串行方式，leader严格按顺序执行Paxos算法，也就是在没有确认上一个Paxos实例成功时，不开始执行下一个Paxos实例。
但是，即便严格按顺序执行Paxos算法，也仍然不能完全避免空洞的出现，因为空洞可能出现在非leader的进程上。
例如，在某个非leader的进程上，关于某个实例的所有消息都丢失了，而下一个实例的所有消息又都收到了，那么就会出现空洞。
所以，即便leader严格按顺序执行Paxos算法，非leader的进程也仍然需要一种机制处理空洞。
这种处理空洞的机制非常简单，就是所有进程都要严格按照命令序列执行每一个命令，如果在某个命令序列位置未发现值，也就是出现了空洞，则状态机不会继续执行，它会一直等待这个位置被填入值，即便在这个空洞之后的位置上有命令，状态机也不会继续执行。
在具体的算法实现中，对于上面这种情况，新的leader往往是向这个空洞里填入一个空操作命令，这个空操作是不会对状态机产生任何影响的，有了这个空操作，状态机就可以继续执行空洞后面的操作了。
另外，实例的并发执行也并不是没有任何条件，如果想要并发执行，所有命令之间就不能有任何关系。
比如后一个命令依赖前一个命令的成功执行，在这种情况下，最好还是严格按照顺序来执行Paxos实例。
六、 算法应用于原子广播
6.1 原子广播
原子广播也是一种非常常见的分布式技术
原子广播（atomic broadcast）协议用于把消息（message）向广播对象进行广播，并且保证消息能够被可靠地收到，且所有广播对象以相同的顺序收到。
6.1.1 原子广播的模型
原子广播可以用来构建分布式系统，这类分布式系统有很多不同的进程，如果其中某个进程希望广播一条消息，这条消息被抽象成一个值（value），其他进程能接收到这个值。
也可以说，这个值被投递（deliver）到其他进程上，或者说一个进程希望提交自己的值，并且能够同时接收其他进程提交的值。
原子广播可以被看作一个黑盒，这些进程通过这个黑盒完成值的提交和接收。我们将这些进程称为客户端（client）。
原子广播协议通常被定义为包含以下两个动作（action）原语（primitive）。
- ABroadcast（v）：广播动作，当客户端想广播值v时，它可以调用这个动作。
- v=ADeliver()：投递动作，客户端通过这个动作接收其他客户端提交的值。
这个动作一般是一个回调，当有值要被接收时，客户端会被回调。
6.1.2 原子广播的特性
从原子广播的定义可以看出，原子广播保证：如果有一个进程调用了广播动作（即ABroadcast），那么所有客户端的投递动作（即ADeliver）一定会被调用，并且调用ADeliver动作的顺序一定与调用ABroadcast动作的顺序相同。
6.2 Paxos实现复制状态机
我们可以使用Paxos算法来实现原子广播，当然，原子广播协议也可以不基于Paxos算法来实现。
与基于Paxos算法的复制状态机的实现，基于Paxos算法的原子广播的实现与其类似。
基于Paxos算法的原子广播也是通过执行一个Paxos consensus实例序列来实现的，每个实例都使用一个唯一且单调递增的编号来标识，这个编号被称为实例编号（instance identificator，iid）。
每个Paxos consensus实例都是一个要广播的值，Paxos consensus算法保证广播是原子的，所有客户端一定会收到同一个值。
按照实例的顺序投递值能保证全局有序
为了保证progress，也要保证在同一时刻最好只有一个proposer在向acceptor提交值。为了这个目的，把其中一个proposer认命为coordinator或者leader
七、业界应用
业界采用Paxos算法的实际案例有Chubby、MegaStore、Spanner、DynamoDB、S3、ZooKeeper等。
- Spanner：使用Paxos进行副本间的数据复制
