分布式共识算法分布式共识算法

背景分布式共识算法主要目的是为了保证同一份数据在多个节点上的一致性，以满足CP要求。
共识（Consensus）与一致性（Consistency）的区别：一致性是指数据不同副本之间的差异，而共识是指达成一致性的方法与过程。由于翻译的关系，很多中文资料把 Consensus 同样翻译为一致性，导致网络上大量的“二手中文资料”将这两个概念混淆起来，如果你在网上看到“分布式一致性算法”，应明白其指的其实是“Distributed Consensus Algorithm”。
如果你有一份很重要的数据，想要确保它不会丢失，你会怎么做？
你可能会买几块硬盘或U盘，把数据复制上去。
而在分布式系统中，我们做法也是一样的，通过备份，但是这种环境下，数据是动态的，各个备份系统之间的网络是不可靠的，也就是复制可能会失败。所以引出了以下问题：
如果你有一份随时变动的数据，要确保它正确地存储在网络中的几台不同的机器上，你会怎么做？
你可能会想到数据同步：每当有数据变化，把变化的数据在各个节点之间复制视作一种事务操作，所有机器都成功写入硬盘后，才宣告数据同步完成。这种可以保证节点间的数据是绝对一致的，但可用性大大降低。这种以同步为代表的数据复制方法，称为状态转移(State Transfer)，通常要牺牲可用性。
如果你有一份随时变动的数据，要确保它正确地存储在网络中的几台不同的机器上，并且要尽可能保证数据随时可用时，你会怎么做？
为了缓解C和A之间的矛盾，在分布式系统里主流的数据复制方法是以操作转移(Operation Transfer)为基础的。能够使用确定的操作，促使状态间产生确定的转移结果的计算模型，在计算机科学中称为状态机：任何初始状态一致的状态机，如果执行命令序列一样，最终的状态也一样。根据状态机的特性，要让多台机器的最终状态一致，只要确保它们的初始状态是一致的，并且接收到的操作指令序列也是一致的即可。
考虑到分布式环境下网络分区现象是不可能消除的，甚至允许不再追求系统内所有节点在任何情况下的数据状态都一致，而是采用“少数服从多数”的原则，一旦系统中过半数的节点中完成了状态的转换，就认为数据的变化已经被正确地存储在系统当中，这样就可以容忍少数（通常是不超过半数）的节点失联，使得增加机器数量对系统整体的可用性变成是有益的，这种思想在分布式中被称为Quorum 机制
拜占庭将军问题
拜占庭将军问题(The Byzantine Generals Problem)提供了对分布式共识问题的一种情景化描述，由Leslie Lamport等人在1982年首次发表。拜占庭将军问题是分布式系统领域最复杂的容错模型，它描述了如何在存在恶意行为(如消息篡改或伪造)的情况下使分布式系统达成一致。是我们理解分布式一致性协议和算法的重要基础。
拜占庭将军问题描述了一个如下的场景，有一组将军分别指挥一部分军队，每一个将军都不知道其它将军是否是可靠的，也不知道其他将军传递的信息是否可靠，但是它们需要通过投票选择是否要进攻或者撤退（少数服从多数原则）。
当里面存在叛徒时候，将会扰乱作战计划。图展示了General C为叛徒的一种场景，他给General A和General B发送了不同的消息，在这种场景下General A通过投票得到进攻：撤退=1:2，最终将作出撤退的行动计划；General B通过投票得到进攻：撤退=2:1，最终将作出进攻的行动计划。结果只有General B发起了进攻并战败。

文章图片

在分布式系统领域, 拜占庭将军问题中的角色与计算机世界的对应关系如下:
将军, 对应计算机节点；忠诚的将军, 对应运行良好的计算机节点；叛变的将军, 被非法控制的计算机节点；信使被杀, 通信故障使得消息丢失；信使被间谍替换, 通信被攻击, 攻击者篡改或伪造信息。
根据此问题，将分布式共识算法分为两类：

文章图片

这里主要介绍非拜占庭容错算法。
Paxos Google Chubby的作者Mike Burrows说过：There is only one consensus protocol, and that's Paxos. All other approaches are just booked versions of Paxos. 所有的其他一致性算法都是Paxos的不完整版。
这么说是因为一方面它出现的很早，另一方面Paxos解决的其实是在分布式环境下所有服务达成一次某个值的共识的过程，而这一个过程，可以说每种共识算法都是绕不开的。
Paxos算法存在两个很明显的问题：

特别复杂，难以理解
缺失很多细节，难以实现

Paxos采取我们非常熟悉的达成共识的方法：少数服从多数，即Quorum机制，它将分布式系统中的节点分为三类，这些角色只是在不同时间下逻辑上的划分。

Proposer：提案节点，提出对某个值进行设置操作的节点，就是接受客户端写操作的节点。请注意，Paxos 是典型的基于操作转移模型而非状态转移模型来设计的算法，这里的“设置值”不要类比成程序中变量赋值操作，应该类比成日志记录操作。
Acceptor：决策节点，Acceptor 从含义上来说就是除了当前Proposer以外的其他机器，他们之间完全平等和独立，Proposer需要争取超过半数（N/2+1）的 Acceptor 批准后，其提案才能通过，它倡导的“value”操作才能被所有机器所接受。
Learner：记录节点，不参与提案，也不参与决策，只是单纯地从提案、决策节点中学习已经达成共识的提案，譬如少数派节点从网络分区中恢复时，将会进入这种状态。

算法流程
Paxos有两个阶段：

prepare请求阶段：proposer告诉acceptor我有一个提案，询问是否支持
accept请求阶段：当proposer收到超过半数的acceptor回复支持时，正式通知大家提案生效。

看起来挺简单的，当有多个proposer时，每个proposer都收到了数量一致的acceptor时，算法就会陷入死锁状态。此时Paxos加上一条规则：给每个提案加上一个编号，acceptor如果还没有正式通过提案（即还没有accept使操作生效），就可以接受编号更大的Prepare请求。为了提高效率：如果一个Prepare请求，到达Acceptor时，发现该Acceptor已经接受生效了另一个提案，那么它除了回复提案被拒绝外，还会带上Acceptor已经通过的编号最大的那个提案的内容回到Proposer。Proposer收到带内容的拒绝后，需要修改自己的提案为返回的内容。
所以需要保证编号全剧唯一且递增。
一些异常情况及解决办法：

当某一个proposer进入accept阶段时挂掉了，所有Acceptor就会陷入持续的等待，而其他的Proposer也会一直重试然后一直失败。为了解决这个，Paxos决定允许proposer在拒绝时更新自己的提案编号重新发起prepare请求。
每个Proposer都在被拒绝时，增大自己的编号，然后每个Proposer在新的编号下又争取到了小于半数的Acceptor，都无法进入Accept，又重新加大编号发起提案，一直这样往复循环，就成了活锁。
1、可以让proposer引入一个随机延迟去更新编号
2、或者设置一个proposer的leader，全部由它来进行提案，这是共识算法常见的套路。
如果算法进行中新增或下线了机器，此时一些Proposer知道机器数变了，一些Proposer不知道，那么大家对半数的判断就会不一致，导致算法出错。因此在实际运行中，机器节点数的变动，也需要作为一条要达成共识的请求提案，通过Paxos算法本身，传达到所有机器节点上。

完善后的两阶段：

Prepare准备阶段：Proposer会尝试告诉所有acceptor一个提案，请求得到支持。Acceptor如果已经支持编号为N的提案，则会拒绝编号小雨N的提案，如果生效了编号为N的提案，回复时还会告知当前已生效的提案编号和内容。
Accept提交阶段：Proposer会根据上一阶段的回复来决定行为。
如果收到超过半数的支持，则正式通知所有机器生效。如果没有收到超过半数回复，提案取消。
如果收到它们已经接收了其他编号更大的提案，那么proposer会更新一个更大的编号去重试（随机延迟）
如果回复已经生效其他编号的提案，那么proposer接受此提案，并成为使其生效proposer的帮手，告诉其他acceptor生效信息。
接受其他提案以及提案取消情况下，proposer直接告诉客户端该次请求失败，等待客户端重试即可。

文章图片

Multi-Paxos
上面算法过程每次只更新一个值，被称为Basic-Paxos。每次更新多个值称为Multi-Paxos，作者并没有给出具体的实现细节。
这种情况下使用Basic-Paxos一遍遍去执行也是可以的，但是效率很低。Lamport给出的解法是：
先选择一个Leader来担当Proposer的角色，取消多Proposer，只有一个Leader来提交提案，这样就没有了竞争（也没有了活锁）。同时，由于无需协商判断，有了Leader后就可以取消Prepare阶段，两阶段变一阶段，提高效率。对于每一次要确定的值/操作，使用唯一的一个标识来区分，保证其单调递增即可。
对于选择Leader的过程，简单的做法很多，复杂的也只需要进行一次Basic-Paxos即可。选出Leader后，直到Leader挂掉或者到期，都可以保持由它来进行简化的Paxos协议。
如果有多个机器节点都由于某些问题自认为自己是Leader，从而都提交了提案，也没关系，可以令其退化成Basic-Paxos，也可以在发现后再次选择Leader即可。
Raft 和Paxos算法几乎是一个纯理论算法不同，Raft算法就是为了工程实践而设计的，“可理解性”称为Raft设计的首要目标。
Raft算法给出了大量实现细节，基本上对照论文就能实现，代码量也不大，论文中只用了2k+行代码就实现了Raft算法。
Raft协议需要选举出Leader的，从这里也能看到，共识算法大都会走向选举出一个Leader的方向，来提升效率和稳定性。（不在需要两阶段提交了）不同之处可能只在于选举的方式，以及消息同步的方式。
算法流程
每个节点有三种状态：Follower、Candidate、Leader。
每个节点都有一个倒计时器（Election Timeout），时间在150ms到300ms之间。当收到选举请求或收到Leader的Heartbeat时候会重设。
在 Raft 运行过程中，最主要进行两个活动：
选主 Leader Election

节点一开始状态是Follower。
当倒计时结束或者没有收到leader的心跳，就会成为candidate，并给其他节点发送RequestVote节点选举请求。
成为candidate后，会重新开启一个计时器，过期时会重新发起投票请求。
当有多个follower同时timeout成为candidate时，并得到了相同的选票，此时就会僵持，但他们的倒计时仍然在运行，先timeout的candidate会重新发起新一轮的投票请求，follower还没有在新一轮投过票，就会返回ok。这个candidate就会成为leader。
如果超过一半节点投支持票，该节点将会成为leader，并每隔一小段时间给follower发送一个心跳以重设计时器，此后所有对系统的修改都经过leader来完成。

当leader出故障时候，新一轮的选举就会进行，每轮选举都是有记录的，当之前的leader恢复后，会自觉的降级为follower。
选主的过程和Basic-Paxos很像。
复制日志 Log Replication

当客户端发送请求给leader更新数据时，leader现将数据操作记录在本地日志中，这时候数据是Uncommited状态。
然后给follower发送AppendEntries请求，将数据操作写在本地日志中，返回ok。
leader收到超过半数ok回复后，将数据改为committed状态，Leader 再次通知 Follower 数据已经提交，收到请求后，Follower 将本地日志里 Uncommitted 数据改成 Committed并更新数据。

当存在网络分区情况时，raft也能保证数据的一致性。被分割出的非多数派集群将无法达到共识，即脑裂。当集群再次连通时，将只听从最新任期Leader的指挥，旧Leader将退化为Follower，如图中B节点的Leader（任期1）需要听从D节点的Leader（任期2）的指挥，此时集群重新达到一致性状态
ZAB ZAB全称是Zookeeper Atomic Broadcast，也就是Zookeeper的原子广播，顾名思义是用于Zookeeper的。ZAB也是对Multi Paxos算法的改进，大部分和raft相同。
ZAB理解起来很简单，在协议中有两种角色：

Leader节点：有任期的领导节点，负责作为与客户端的连接点接受读写操作，然后将其广播到其他节点去。
Follower节点：主要是跟随领导节点的广播消息进行同步，并关注领导节点的健康状态，好随时取而代之。

和raft算法的主要区别：

对于Leader的任期，raft叫做term，而ZAB叫做epoch
在状态复制的过程中，raft的心跳从Leader向Follower发送，而ZAB则相反。

Gossip Paxos、Raft、ZAB 等分布式算法经常会被称作是“强一致性”的分布式共识协议，其实这样的描述抠细节概念的话是很别扭的，会有语病嫌疑，但我们都明白它的意思其实是在说“尽管系统内部节点可以存在不一致的状态，但从系统外部看来，不一致的情况并不会被观察到，所以整体上看系统是强一致性的”。与它们相对的，还有另一类被冠以“最终一致性”的分布式共识协议，这表明系统中不一致的状态有可能会在一定时间内被外部直接观察到。在比特币网络和许多重要分布式框架中都有应用的另一种具有代表性的“最终一致性”的分布式共识协议：Gossip 协议。
今天 Gossip 这个名字已经用得更为普遍了，除此以外，它还有“流言算法”、“八卦算法”、“瘟疫算法”等别名，这些名字都是很形象化的描述，反应了 Gossip 的特点：要同步的信息如同流言一般传播、病毒一般扩散。
Gossip算法每个节点都是对等的，即没有角色之分。Gossip算法中的每个节点都会将数据改动告诉其他节点（类似传八卦）。有话说得好："最多通过六个人你就能认识全世界任何一个陌生人"，因此数据改动的消息很快就会传遍整个集群。(被感染)

文章图片

优点：

我们很容易发现 Gossip 对网络节点的连通性和稳定性几乎没有任何要求，它一开始就将网络某些节点只能与一部分节点部分连通（Partially Connected Network）而不是以全连通网络（Fully Connected Network）作为前提
能够容忍网络上节点的随意地增加或者减少，随意地宕机或者重启，新增加或者重启的节点的状态最终会与其他节点同步达成一致。
Gossip 把网络上所有节点都视为平等而普通的一员，没有任何中心化节点或者主节点的概念，这些特点使得 Gossip 具有极强的鲁棒性，而且非常适合在公众互联网中应用。

同时我们也很容易找到 Gossip 的缺点：

消息最终是通过多个轮次的散播而到达全网的，因此它必然会存在全网各节点状态不一致的情况
而且由于是随机选取发送消息的节点，所以尽管可以在整体上测算出统计学意义上的传播速率，但对于个体消息来说，无法准确地预计到需要多长时间才能达成全网一致。
另外一个缺点是消息的冗余，同样是由于随机选取发送消息的节点，也就不可避免的存在消息重复发送给同一节点的情况，增加了网络的传输的压力，也给消息节点带来额外的处理负载。

可以看到，共识算法基本都需要解决两个基本问题：