分布式共识算法_分布式的共识算法

1.前言

问题提出：

如果有一份随时变动的数据，要确保它能够正确的存储在网络中几台不同的机器上，怎么处理？

在分布式系统中，必须考虑动态的数据如何在不可靠的网络通讯的条件下，依然能在各个节点之间正确复制。

• 数据同步 （状态转移(State Transfer)） 性能损耗

每当数据又变化，就把变化情况在各个节点之间的复制看成是一种事务性的操作，只有系统的每一台机器都反馈成功完成磁盘写入后，数据的变化才能宣布成功。那么这个操作其实通过 2PC、3PC就可以实现这种同步操作。比如，MySQL Cluster进行全同步复制时，所有Slave节点的的Binlog都完成写入后，Master的事务才会进行提交。

以同步为代表的数据复制方法，叫做状态转移（State Transfer）。这类方法属于比较符合人类思维的可靠性保障手段，但通常要以牺牲可用性为代价

问题升级：

如果你有一份会随时变动的数据，要确保它正确地存储于网络中的几台不同机器之上，并且要尽可能保证数据是随时可用的，你会怎么做

共识算法

这个让系统各节点不受局部的网络分区、机器崩溃、执行性能或者其他因素影响，能最终表现出整体一致的过程，就是各个节点的协商共识（Consensus）。

我们需要设计出一种算法，能够达成两个目标

• 能够让分布式系统内部可以暂时容忍存在不同的状态，但最终能够保证大多数节点的状态能够达成一致；
• 同时，能够让分布式系统在外部看来，始终表现出整体一致的结果。

共识（Consensus）与一致性（Consistency）是有区别的：一致性指的是数据不同副本之间的差异，而共识是指达成一致性的方法与过程。

状态机 + 操作转移

系统高可用和高可靠之间的矛盾，是由于增加机器数量反而降低了可用性带来的。为缓解这个矛盾，在分布式系统里主流的数据复制方法，是以操作转移（Operation Transfer）为基础的。比如(x=x+1)

能够使用确定的操作，促使状态间产生确定的转移结果的计算模型，在计算机科学中被称为状态机（State Machine）

状态机有一个特性：任何初始状态一样的状态机，如果执行的命令序列一样，那么最终达到的状态也一样。要让多台机器的最终状态一致，只要确保它们的初始状态和接收到的操作指令都是完全一致的就可以。广播指令与指令执行期间，允许系统内部状态存在不一致的情况，也就是不要求所有节点的每一条指令都是同时开始、同步完成的，只要求在此期间的内部状态不能被外部观察到，且当操作指令序列执行完成的时候，所有节点的最终的状态是一致的。这种模型，就是状态机复制（State Machine Replication）

Quorum 机制

在分布式环境下，考虑到网络分区现象是不可能消除的，而且可以不必去追求系统内所有节点在任何情况下的数据状态都一致，所以采用的是“少数服从多数”的原则。

也就是说，一旦系统中超过半数的节点完成了状态的转换，就可以认为数据的变化已经被正确地存储在了系统当中。这样就可以容忍少数（通常是不超过半数）的节点失联，使得增加机器数量可以用来提升系统整体的可用性。

2.Paxos 算法

Paxos算法的工作流程

主要概念：

• 提案节点：Proposer，提出对某个值进行设置操作的节点，设置值这个行为就是提案(Proposal)。值一旦设置成功，就是不会丢失也不可改变的。
• 决策节点：Acceptor，是应答提案的节点，决定该提案是否可以被投票、是否可以被接受。提案一旦得到过半数决策节点的接受，就意味着这个提案被批准(Accept)。提案被批准，就意味着该值不能再被更改，也不会丢失，且最终所有的节点都会接受它。
• 记录节点：Learner，不参与提案，也不参与决策，只是单纯的从提案、决策节点中学习已经达成共识的提案。比如，少数节点刚从网络分区中恢复时，将会进入这种状态。

要求

• 为了便于确保有明确的多数派，决策节点的数量应该被设定为奇数个
• 在系统初始化时，网络中每个节点都知道整个网络所有决策节点的数量、地址等信息

分布式环境下并发操作的共享数据

假设有一个变量 i 当前在系统中存储的数值为 2，同时有外部请求 A、B 分别对系统发送操作指令，“把 i 的值加 1”和“把 i 的值乘 3”。如果不加任何并发控制的话，将可能得到“(2+1)×3=9”和“2×3+1=7”这两种结果。因此，对同一个变量的并发修改，必须先加锁后操作，不能让 A、B 的请求被交替处理。

但是，在分布式的环境下，还要同时考虑到分布式系统内，可能在任何时刻出现的通讯故障。如果一个节点在取得锁之后、在释放锁之前发生崩溃失联，就会导致整个操作被无限期的等待所阻塞。

解决方案

主要包括 “准备（Prepare）”和“批准（Accept）”两个阶段

• 准备（Prepare）阶段，相当于抢锁的过程。如果某个提案节点准备发起提案，那必须先向所有的决策节点(必须提前知道)广播一个许可申请(称为Prepare请求)。提案节点的Prepare请求中会携带一个全局唯一的数字N作为提案ID，决策节点收到后，会给天街店两个承诺和一个应答。

两个承诺：

• • 承诺不会再接受提案ID小于或等于N的Prepare请求
  • 承诺不会再接受提案ID小于N的Accept请求。

一个应答是：

再不违背以前做出的承诺前提下，回复已经批准过的提案中ID最大的那个提案锁设定的值和提案ID。如果该值从来没有被任何提案设定过，则返回空值。如果违反此前做出的承诺，也就是收到的提案ID不是决策节点收到过的最大的，那就可以直接不理会这个Prepare请求。

• 批准（Accept）

当提案节点收到了多数派决策节点的应答(Promise应答)后，可以开始第二阶段“批准（Accept）”的过程。此时有两种可能：

• • 如果提案节点发现所有响应的决策节点此前都没有批准过这个值（即为空），就说明它是第一个设置值的节点，那就可以随意决定要设置的值；并将自己选定的值与提案ID。构成一个二元组（ID,VALUE），再次广播给全部的决策节点(称为Accept请求)
  • 如果提案节点发现响应的决策节点中，已经有至少一个节点的应答中包含有值了，那就必须从应答中找到提案ID最大的那个值并接受，构成一个二元组（ID,maxAcceptValue）,然后再次广播给全部的决策节点（称为Accept请求）。

那么每个决策节点收到Accept请求时，都会在不违背以前做出的承诺前提下，接受并持久化当前提案ID和携带的数值。但是如果收到的提案ID并不是收到过的最大的，那对Accept请求将不予理会。

记录节点：

当提案节点收到了多数派决策节点的应答(Acceptd应答)后，协商结束，共识决议形成，将决议发送给所有记录节点进行学习。

Basic Paxos 协商过程-时序图

---

几个典型的场景：

背景：假设一个分布式系统中有五个节点：S1、S2、S3、S4、S5；那他们同时扮演着提案节点和决策节点。此时有两个并发的请求希望将同一个值分别设置为X和Y；用P表示准备阶段，用A表示批准阶段。

• 场景一： （其实就是在对变量X协商的过程中，谁先获得了多数节点的支持或者先在Promise中返回决议值，谁就是本次决议的最终值，在协商结束之前，无论有多少次新的提案都不在进行处理）

S1选定的提案ID是3.1（全局唯一ID 3 加上节点标号 1），先取得了多数派决策节点的Promise和Accept应答；此时S5的提案ID是4.5，发起Prepare请求，收到的多数派应答中至少会包含一个此前应答过S1的决策接节点，假设是S3。那么S3提供的Premise中必定将S1已经决议好的值X，S5就必须无条件的使用X而不是Y作为自己的提案值。（即使S5的提案ID更大，但是已经有了Accept）

• 场景二：

事实上，对于情况一，X被选定为最重值是必然的结果，但是从图中可以看出，X被选定为最重值并不一定是要多数派的共同批准，二只取决于S5提案时Promise应答中是否已经包含了批准过X的决策节点。

比如下图所示，S5发起提案的Prepars请求时，X并未获取多数派批准，但由于S3已经批准的原因，最终共识的结果依然是X

• 场景三：

另外一种可能的结果是，S5在提案的时候Promise应答中并没有包含批准过X的决策节点。比如，应答S5提案时，节点S1已经批准了X，节点S2、S3并未批准但是返回了Promise应答，那此时S5以更大的提案ID获得了S3、S4、S5的Promise。这三个节点均为批准过任何值，那么S3将不会再接受来自S1的Accept请求，因为它的提案ID已经不是最大的。所以这三个节点将批准Y的取值，整个系统将会对取值为Y达成一致。

• 场景四：

其实从情况三可以分析出一种更极端的例子，如果两个提案节点交替使用最大的提案ID，使得准备阶段成功，但是批准阶段失败的话，那这个过程理论上可以无限延续下去，形成活锁（Live Lock）。但是再实际的算法中会引入随机超时时间来避免活锁产生。

3.Multi Paxos (Raft)

Basic Paxos 的活锁问题：

两个提案节点互不相让地提出自己的提案，抢占同一个值的修改权限，导致整个系统再持续的“反复横跳”，从外部来看就像是被锁住了。

那活锁问题和许多BasicPaxos异常场景中(网络的不可靠、请求的并发)所遇到的麻烦，都可以看作是源于任何一个提案节点都能够完全平等的与其他节点并发的提出提案而带来的问题。

那MultiPaxos对BasicPaxos的核心改进是，选择。

3.1选主

• 提案节点会通过心跳，确定当前网络中所有的节点里是否存在一个主提案节点
• 一旦发现没有主节点，节点就会再心跳超时后(不存在主节点立即)使用BasicPaxos中定义的准备、批准的两轮网络过程，向所有其他节点广播自己 希望竞选主节点的请求，希望整个分布式系统对“由我做主节点”这件事情协商达成一致共识
• 如果得到了决策结点中多数派的批准，便宣告竞选成功

当选主完成后，只有主节点本身才能提出提案。此时，无论是哪个提案节点接收到客户端的请求操作，都会将请求转发给主节点完成提案，而主节点提案的时候，也就无需再次经过准备过程，因为可以视作，经过选举时的那一次准备后，后续的提案都是对相同提案ID的一连串批准过程。

可以理解为：选主后，就不会再有其他节点与主节点竞争，相当于时处于无并发的环境中进行的有序操作，所以此时系统中要对某个值达成一致，只需要进行一次批准的交互即可。

Multi Paxos 协商过程-时序图

3.2任期和分区

原本的（id，value）二元组已经变成了三元组（id，i，value），这是因为需要给主节点增加一个"任期编号"，这个编号必须是严格单调递增的，以应对主节点陷入网络分区后重新恢复，但是另外一部分节点仍然有多数派，且已经完成了重新选主的过程，此时必须以任期编号大的节点为准。

raft算法中 面对网络分区后“双主问题”解决方案

从整体来看，当节点有了选主机制后，可以进一步简化为 主节点（Leader）和从节点(Follower)，也就不必区分提案节点、决策节点和记录节点了。

---

4.重新思考分布式协商

那到此为止呢，在这个理解的基础上，可以换一个角度重新思考“分布式系统中如何对某个值达成一致这个问题，可以把它分为下面三个子问题来考虑”：

• 如何选主（Leader Election）
• 如何把数据复制到各个节点上（Entity Replication）
• 如何保证过程是安全的（Safety）

4.1如何选主

关于“如何选主”，虽然选主问题会涉及到许多工程上的细节，比如心跳、随机超时、并行竞选等，但从原理上来说，只要你能够理解 Paxos 算法的操作步骤，就不会有啥问题了。因为，选主问题的本质，仅仅是分布式系统对“谁来当主节点”这件事情的达成的共识而已。Basic Paxos 其实就已经解决了“分布式系统该如何对一件事情达成共识”这个问题。

4.2如何把数据复制到各个节点上

继续来解决数据（Paxos 中的提案、Raft 中的日志）在网络各节点间的复制问题。

场景：提出“将某个值设为X”，那数据复制的过程：

• 主节点将X写入到自己的变更日志上，但先不提交，接着把变更X的信息在下一次心跳包中广播给所有的从节点，并要求从节点回复“确认收到”的消息
• 从节点收到信息后，将操作写入自己的变更日志，然后给主节点发送“确认签收”的消息；
• 主节点收到过半数的签收消息后，提交自己的变更、应答客户端并且给从节点广播“可以提交”的消息
• 从节点收到提交消息后，提交自己的变更，数据在节点之间的复制宣告完成

异常情况：

网络出现了分区，部分节点失联，但只要任然能正常工作的节点数量能够满足多数派（过半）的要求，分布式系统就仍然可以正常工作。假设有S1、S2、S3、S4、S5共5个节点，复制过程：

• 假设由于网络故障，形成了S1、S2和S3、S4、S5两个分区

• 一段时间后，S3、S4、S5三个节点中的某一个比如S3，最先达到心跳超时的阈值，获知当前分区中已经不存在主节点了；于是，S3向所有节点发出自己要竞选主节点的广播，并收到了S4和S5的批注回应，加上自己的一票一共三票，竞选成功！此时，系统中同时存在着S1和S3两个主节点，但是由于网络分区，它们互相不知道对方的存在。

• 在这种情况下，客户端发起操作请求的话，可能出现两种情况：
  • 第一：如果客户端连接上了S1、S2中的一个，都将由S1处理，但是由于操作只能获得最多两个节点的响应，无法构成多数派的批准，所以任何变更都无法成功提交
  • 第二：如果客户端连接上了S3、S4、S5其中的一个，都由S3处理，此时操作可以获得最多三个节点的响应，构成多数派的批准，变更就可以有效提交，可以继续对外提供服务。

• 假设现在网络恢复了，分区解除，五个节点可以再次正常通讯了：
  • S1和S3都向所有节点发送心跳包，从他们的心跳中可以得知S3的任期编号更大、是最新的，所以五个节点均只承认S3是唯一的主节点。
  • S1、S2回滚他们所有未提交的变更。
  • S1、S2从主节点发送的心跳包中获得它们失联期间发生的所有变更，将变更提交写入本地磁盘。
  • 此时分布式系统各个节点的状态达成最终一致。

4.3如何保证过程是安全的（Safety）

选主和数据复制这两个问题都是很具体的行为，但“安全”这个表述很模糊啊，怎么判断什么是安全或者不安全呢？

在专业资料中，Safety 和 Liveness 通常会被翻译为“协定性”和“终止性”。

它们也是由 Lamport 最先提出的，定义是：

• 协定性（Safety）：所有的坏事都不会发生（Something "bad" will never happen）。
• 终止性（Liveness）：所有的好事都终将发生，但不知道是啥时候（Something "good" will must happen, but we don't know when）。

还是以选主问题为例，Safety 保证了选主的结果一定是有且只有唯一的一个主节点，不可能同时出现两个主节点；而 Liveness 则要保证选主过程是一定可以在某个时刻能够结束的。

我们再回想一下活锁的内容的话，可以发现，在 Liveness 这个属性上，选主问题是存在理论上的瑕疵的，可能会由于活锁而导致一直无法选出明确的主节点。所以，Raft 论文中只写了对 Safety 的保证，但由于工程实现上的处理，现实中是几乎不可能会出现终止性的问题

5.Gossip协议

与Paxos、Raft、ZAB相比的"最终一致性"的分布式共识协议。DNS系统也是最终一致性协议。

按照习惯，会把 Gossip 叫做“共识协议”，但首先必须强调它所解决的问题并不是直接与 Paxos、Raft 这些共识算法等价的，只是基于 Gossip 之上可以通过某些方法去实现与 Paxos、Raft 相类似的目标而已。

一个最典型的例子是，比特币网络中使用到了 Gossip 协议，用来在各个分布式节点中互相同步区块头和区块体的信息。这是整个网络能够正常交换信息的基础，但并不能称作共识。比特币使用工作量证明（Proof of Work，PoW），来对“这个区块由谁来记账”这一件事儿在全网达成共识。这个目标才可以认为与 Paxos、Raft 的目标是一致的。

5.1Gossip协议协商工作过程

gossip协议十分简单，主要由两个步骤的简单循环：

• 如果有某一项信息需要在整个网络中所有的节点中传播，那从信息源开始，选择一个固定的传播周期（比如1秒），随机选择与它连接的K个节点（称为Fan-out）来传播消息。
• 如果一个节点收到消息后发现这条消息之前还没有收到过，就会在下一个周期内，把这条消息发送给除了给它发消息的那个节点外，相邻的K个节点

如此循环上述过程，直到网络中所有的节点都收到了这条消息。尽管这个过程需要一定时间，但是理论上网路的所有节点最终都会拥有相同的消息。

Gossip 传播过程的示意图如下所示：

Gossip 传播示意图

5.2Gossip的特点

• Gossip一开始就将某些节点只能与一部分节点部分联通（Partially Connected Network）而不是全连通网络（Fully Connected Network）
• 能够容忍网络上节点的随意增加或减少、随意宕机或重启，新增加的或重启的节点状态，最终会在与其他节点同步达成一致。

5.3Gossip的缺点

• （无法估算传播时间）消息通过多轮的散播而达到全网，因此必然会存在各个节点状态不一致的情况。而且，因为是随机选取的发送消息的节点，所以尽管可以在整体上测算出统计学意义上传播速率，但是还是没办法准确评估出单挑消息的传播，需要多久才能达成全网一致。
• （消息冗余）因为随机选取发送消息的节点，会不可避免的存在消息重复发送同一节点的情况。这种冗余会增加网络的传输压力，也会给消息节点带来额外的处理负担。

达到一致性耗费的时间与网络传播中消息冗余量这两个缺点存在一定的对立关系，如果要改善其中一个，就会恶化另外一个。

也就是说，Gossip 把网络上所有节点都视为平等而普通的一员，没有中心化节点或者主节点的概念。这些特点使得 Gossip 具有极强的鲁棒性，而且非常适合在公众互联网（WAN）中应用

5.4Gossip传播模式

Gossip 传播消息时，有两种可能的方式：反熵（Anti-Entropy）和传谣（Rumor-Mongering）

反熵模式下，为了达成全网各节点的完全一致的目标，会同步节点的全部数据，来消除各节点之间的差异。但是，在节点本身就会发生变动的前提下，这个目标将使得整个网络中消息的数量非常庞大，给网络带来巨大的传输开销。

传谣模式是以传播消息为目标，仅仅发送新到达节点的数据，即只对外发送变更信息，这样消息数据量将显著缩减，网络开销也相对较小。

#END