分布式的基石

分布式共识算法

前置知识：分布式的 CAP 问题，在事务一章中已有详细介绍。

正式开始探讨分布式环境中面临的各种技术问题和解决方案以前，我们先把目光从工业界转到学术界，学习两三种具有代表性的分布式共识算法，为后续分布式环境中操作共享数据准备好理论基础。下面从一个最浅显的场景开始，引出本章的主题：

假如你有一份很重要的数据，要确保它长期存储在电脑上不丢失，你会怎么做？

这不是脑筋急转弯，答案就是去买几块硬盘，把数据备份在不同硬盘上即可。假设一块硬盘每年损坏的概率是 5%，那把文件复制到另一块备份盘上，由于两块磁盘同时损坏而丢失数据的概率就只有 0.25%，如果四块是 0.000625%，换而言之，这已经保证了数据在一年内有超过 99.999% 的概率是可靠的。

在软件系统里，要保障系统的可靠性，采用的方法与刚刚备份硬盘并没有什么区别。单个节点的系统宕机无法访问数据的原因可能有很多，如程序出错、硬件损坏、网络分区、电源故障等，一年中出现系统宕机的概率也许还要高于 5%，这决定了软件系统也必须有多台机器能够拥有一致的数据副本，才有可能对外提供可靠的服务。

在软件系统里，要保障系统的可用性，面临的困难与硬盘备份却又有着本质的区别。硬盘之间是孤立的，不需要互相通信；备份数据是静态的，初始化后状态就不会发生改变，由人工进行的文件复制操作很容易就保障了数据在各个备份盘是一致的；然而在分布式系统里，我们必须考虑动态的数据如何在不可靠的网络通信条件下，依然能在各个节点之间正确复制的问题。将我们要讨论的场景作如下修改：

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

相信最容易想到的答案一定是“数据同步”：每当数据有变化，把变化情况在各个节点间的复制视作一种事务性的操作，只有系统里每一台机器都反馈成功地完成硬盘写入后，数据的变化才宣告成功（全局事务中，2PC/3PC 就可以实现这种同步操作）。同步的其中一种真实应用场景是数据库的主从全同步复制（Fully Synchronous Replication），如 MySQL Cluster，进行全同步复制时，会等待所有 Slave 节点的 Binlog 都完成写入后，Master 节点的事务才进行提交（这个场景中 Binlog 本身就是要同步的状态数据，不应将它看作是指令日志的集合）。然而这里有一个显而易见的缺陷，尽管可以确保 Master 和 Slave 节点中的数据是绝对一致的，但任何一个 Slave 节点因为任何原因未响应均会阻塞整个事务，每增加一个 Slave 风险就增加一分。

以同步为代表的数据复制方法，被称为状态转移（State Transfer，当状态发生变化后，应在主从状态同步一致后再接受新的外部输入），这类方法是较符合人类思维的可靠性保障手段，但通常要以牺牲可用性为代价。我们在建设分布式系统的时候，往往不能承受这样的代价，一些关键系统，必须保障正确可靠的前提下，对可用性的要求也非常苛刻，如系统要保证数据要达到 99.999999% 可靠，同时系统也要达到 99.99999%可用的程度，这就引出了我们的第三个问题：

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

可靠性与可用性的矛盾造成了增加机器数量反而带来可用性的降低，为缓解这个矛盾，在分布式系统里主流的数据复制方法是以操作转移（Operation Transfer）为基础的。我们想要改变数据的状态，除了直接将目标状态赋予它之外，还有另一种常用的方法是通过某种操作，令源状态转换为目标状态。能够使用确定的操作，促使状态间产生确定的转移结果的计算模型，在计算机科学中被称为状态机（State Machine）。

状态机复制

状态机有一个特性：任何初始状态一样的状态机，如果执行的命令序列一样，则最终达到的状态也一样。如果将此特性应用在多参与者进行协商共识上，可以理解为系统中存在多个具有完全相同的状态机（参与者），这些状态机能最终保持一致的关键就是起始状态完全一致和执行命令序列完全一致。

根据状态机的特性，要让多台机器的最终状态一致，只要确保它们的初始状态是一致的，并且接收到的操作指令序列也是一致的即可，无论这个操作指令是新增、修改、删除抑或是其他任何可能的程序行为，都可以理解为要将一连串的操作日志正确的广播给各个分布式节点。广播指令与指令执行期间，允许系统内部状态存在不一致的情况，即并不要求所有节点的每一条指令都是同时开始、同步完成的，只要求在此期间的内部状态不能被外部观察到，且当操作指令序列执行完毕时，所有节点的最终状态是一致的，这种模型就被称为状态机复制（State Machine Replication）。

考虑到分布式环境下网络分区现象是不可能消除的，甚至允许不再追求系统内所有节点在任何情况下的数据状态都一致，而是采用“少数服从多数”的原则，一旦系统中过半数的节点中完成了状态的转换，就任务数据的变化已经被正确地存储在系统当中，这样就可以容忍少数（通常是不超过半数）的节点失联，使得增加机器数量对系统整体的可用性变成是有益的，这种思想在分布式中被称为“Quorum 机制”。

根据上述讨论，我们需要设计出一种算法，能够让分布式系统内部暂时容忍存在不同的状态，但最终能够保证大多数节点的状态达成一致；同时，能够让分布式系统在外部看来始终表现出整体一致的结果。这个让系统各个节点不受局部的网络分区、机器崩溃、执行性能或者其他因素影响，都能最终表现出整体一致的过程，就被称为各个节点的协商共识（Consensus）。

最后，还要区别下共识（Consensus）与一致性（Consistency）的区别：一致性是指数据不同副本之间的差异，而共识是指达成一致性的方法与过程。如果看到“分布式一致性算法”，应明白其指的是“Distributed Consensus Algorithm”。

Paxos

Distributed Consensus Algorithm

There is only one consensus protocol, and that’s “Paxos” --all other approaches are just broken versions of Paxos

世界上只有一种共识协议，就是 Paxos，其他所有共识算法都是 Paxos 的退化版本。

Paxos 是由 Leslie Lamport（就是大名鼎鼎的 LaTex 中的 La）提出的一种基于消息传递的协商共识算法，现已是当今分布式系统最重要的理论基础，几乎就是“共识”二字的代名词。虽然笔者认为并没有 Mike Burrows（提出 Raft 算法）说的“世界上只有 Paxos 一种分布式共识算法”那么夸张，但是如果没有 Paxos，那后续的 Raft、ZAB 等算法，Zookeeper、Etcd 这些分布式协调框架、Hadoop、Consul 这些在此基础上的各类分布式应用都很可能会延后好几年面世。

为了解释清楚 Paxos 算法，Lamport 虚构了一个名为“Paxos”的希腊城邦，这个城邦按照民主制度制定法律，却又不存在一个中心化的专职立法机构，立法靠着“兼职议会”来完成，无法保证所有城邦居民都能够及时地了解新的法律提案、也无法保证居民会及时为提案投票。Paxos 算法的目的就是让城邦能够在每一位居民都不承诺一定会及时参与的情况下，依然可以按照少数服从多数原则，达成最终一致意见。但是 Paxos 算法并不考虑拜占庭将军问题，即假设信息可能丢失也可能延迟，但不会被错误传递。

算法流程：下面我们正式学习 Paxos 算法，Paxos 算法将分布式系统中的节点分为三类：

• 提案节点：称为 Proposer，提出对某个值进行设置操作的节点，设置值这个行为就被称为提案（Proposal）。值一旦设置成功，就是不会丢失也不可变的。请注意，Paxos 是典型的基于操作转移模型而非状态转移模型，这里的设置值不要类比为程序中变量赋值操作，应该类比成日志记录操作，在后面介绍的 Raft 算法就直接把提案叫做日志了。
• 决策节点：称为 Accepter，是应答提案的节点，决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受，即成该提案被批准（Accept），提案被批准即意味着该值不能再被更改，也不会丢失，且最终所有节点都会接受它。
• 记录节点：被称为 Learner，不参与提案，也不参与决策，只是单纯的从提案、决策节点中学习已经达成共识的提案，如少数派节点从网络分区中恢复时，将会进入这种状态。

使用 Paxos 算法的分布式系统里，所有的节点都是平等的，它们都可以承担以上一种或者多种的角色，不过为了便于确保有明确的多数派，决策节点的数量应该被设定为奇数个，且在系统初始化时，网络中每个节点都知道整个网络所有决策节点的数量、地址等信息。

在分布式环境下，如果我们说各个节点“就某个值（提案）达成一致”，指的是“不存在某个时刻有一个值为 A，另一个时刻又为 B 的情景”。解决这个问题的复杂度主要来源于以下两个方面因素的共同影响：

• 系统内部各个节点通信是不可靠的，不论对于系统中企图设置数据的提案节点抑或是决定是否批准设置操作的决策节点，其发出、收到的信息可能延迟送达、也可能丢失，但不考虑消息又传递错误的情况。
• 系统外部各个用户访问可能是并发的，如果系统只有一个用户，或者每次只对系统进行串行访问，那单纯的应用 Quorum 机制，少数节点服从多数节点，就已经足矣保证值被正确的读写。

第一点是网络通信中客观存在的现象，也是所有共识算法都要着重解决的问题。对于第二点，详细解释下：现在我们讨论的是“分布式环境下并发操作的共享数据”的问题，即使先不考虑是不是在分布式的环境下，只考虑并发操作，假设有一个变量 i 当前在系统中存储的数值为 2，同时又外部请求 A、B 分别对系统发送操作指令：“将 i 的值加 1”和“将 i 的值乘 3”，如果不加任何并发控制的话，可能得到的值为“（2+1）*3=9”与“2✖️3+1=7”两种可能。因此，对同一个变量的修改必须先加锁后操作，不能让 A、B 的请求被交替处理。而在分布式环境下，由于还要考虑到分布式系统内可能在任何时刻出现的通信故障，如果一个节点在取得锁之后，在释放锁之前发生崩溃失联，这将导致整个操作被无限期的等待所阻塞，因此算法中的加锁就不完全等同于并发控制中以互斥量来实现的加锁，还必须提供一个其他节点能抢占锁的机制，以避免因通信问题而出现死锁。

重要‼️

为了解决这个问题，分布式环境中的锁必须是可抢占的。Paxos 算法包括两个阶段，①其中，第一阶段“准备”（Prepare）就相当于上面抢占锁的过程。如果某个提案节点准备发起提案，必须先向所有的决策节点广播一个许可申请（称为 Prepare 请求）。提案节点的 Prepare 请求中会附带一个全局唯一的数字 n 作为提案 ID，决策节点收到后，将会给予提案节点两个承诺与一个应答。

两个承诺是：

1. 承诺不会再接受提案 ID 小于或等于 n 的 Prepare 请求。
2. 承诺不会再接受提案 ID 小于 n 的 Accept 请求。

一个应答是：

• 不违背以前做出的承诺的前提下，回复（返回）已批准过的提案中 ID 最大的那个提案所设定的值和提案 ID，如果该值从来没有被任何提案设定过，则返回空值。如果违反此前作出的承诺，即收到的提案 ID 并不是决策节点收到过的最大的，那允许直接对此 Prepare 请求不予理会。

②当提案节点收到了多数派决策节点的应答（称为 Promise 应答）后，可以开始第二阶段“批准”（Accept）过程，这时有如下两种可能结果：

1. 如果提案节点发现所有响应的决策节点此前都没有批准过该值（即为空），那说明它是第一个设置值的节点，可以随意决定要设置的值，将自己选定的值与提案 ID，构成一个二元组“(id, value)”，再次广播给全部的决策节点（称为 Accept 请求）。
2. 如果提案节点发现响应的决策节点中，已经至少一个节点的应答中包含有值了，那它就不能够随意取值了，必须无条件的从应答中找出提案 ID 最大的那个值并接受，构成一个二元组“(id, maxAcceptValue)”，再次广播给全部的决策节点（称为 Accept 请求）。

③当每一个决策节点收到 Accept 请求时，都会在不违背以前作出的承诺的前提下，接受并持久化对当前提案 ID 和提案附带的值。如果违反此前作出的承诺，即收到的提案 ID 并不是决策节点收到过的最大的，那允许直接对此 Accept 请求不予理会。

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

通俗易懂版：

Paxos算法通过一个决议分为两个阶段（Learn阶段之前决议已经形成）：

1. 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare（把…预备好）请求，Acceptors针对收到的Prepare请求进行Promise承诺。
2. 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise（承诺）后，向Acceptors发出Propose（提出、提议）请求，Acceptors针对收到的Propose请求进行Accept处理。
3. 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept（接受）之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

摘自

整个 Paxos 算法的工作流程到此结束。

事例

假设一个分布式系统有五个节点，分别命名为 S1，S2，S3，S4，S5，（这个例子中只讨论正常通信的场景，不涉及网络分区）。全部节点都同时扮演着提案节点和决策节点的身份。此时，有两个并发的请求分别希望将同一个值分别设定为 X（由 S1 作为提案节点提出）和 Y（由 S5 作为提案节点提出），以 P 代表准备阶段，以 A 代表批准阶段，这时候可能发生以下情况：

情况一：如 S1 选定的提案 ID 是 3.1（全局唯一 ID ➕ 节点编号），先取得了多数派决策节点的 Promise 和 Accepted 应答，此时 S5 选定提案 ID 是 4.5，发起 Prepare 请求，收到的多数派应答中至少会包含 1 个此前应答过 S1 的决策节点（假设是S3），那 S3 提供的 Promise 中必然包含 S1 已设定好的值 X，S5 就必须无条件地用 X 替换 Y 作为自己的提案的值，由此整个系统对“取值为 X”这一事实达成一致。

按照场景假设，S5是提案节点，S3是决策节点，提案节点会发出Prepare和Accept请求（抢锁），决策节点会响应Promise和Accepted应答。可见S3是不可能发出Accept消息的。

只关注S1、S3、S5的之间的交互，此场景的时间线顺序如下：

1. S1向S3提交Prepare(3.5)的请求
2. S3向S1返回Promise(3.5,null)的响应
3. S1收到Promise(3.5,null)后，提交Accept(3.5,X)的请求
4. S3收到Accept(3.5,X)后，向S5返回Accepted(3.5,X)的响应
5. S5向S3提交Prepare(4.5)的请求
6. S3收到后发现已有设置值X，向S5返回Promise(4.5,X)的响应
7. S5收到Promise(4.5,X)后，无条件接受X代替原本的Y作为自己的提案值，提交Accept(4.5,X)的请求
8. S3收到Accept(4.5,X)后，向S5返回Accepted(4.5,X)的响应

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

上图所示，S5 发起提案的 Prepare 请求时，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 使得准备节点成功，但是批准阶段失败的话，整个过程理论上可以无限持续下去，形成活锁，在算法实现中会引入随机超时时间来避免活锁。

虽然 Pacts 是以复杂著称的算法，但以上介绍都是基于 Basic Paxos、以正常流程（未出现网络分区）、通俗方式讲解的，并未涉及严谨的逻辑和数学原理。

Basic Paxos 的价值在于开拓了分布式共识算法的发展思路，但因它🈶️如下缺陷，一般不会直接用于实践：①只能对单个值形成决议，并且决议的形成至少需要两次网络请求和应答（准备和批准各一次），②高并发下将产生较大的网络开销，极端情况下甚至可能形成活锁。

总之，Basic Paxos 现在只用来做理论研究，实际的应用都是基于 Multi Paxos （Raft、ZAB等）和 Fast Paxos 算法的。

Multi Paxos

分布式共识的复杂性，主要来源于网络的不可靠性与请求的并发两大因素。

针对 Basic Paxos 的活锁问题（两个提案节点互不相让的提出自己的提案，抢占同一值的修改权限，导致整个系统在持续性的“反复横跳”，外部看起来就像被锁住了一样），Lamport 专门设计了一种 Paxos 的改进版本“Multi Paxos” 算法来解决这个问题。

活锁问题与许多 Basic Paxos 异常场景中所遭遇的麻烦，都可以看作是源于任何一个提案节点都能够完全平等的、与其他节点并发地提出提案而带来的复杂问题。

Multi Paxos 希望找到一种两全其美的办法，即不破坏 Paxos 中“众节点平等”的原则，又能在提案节点中实现主次之分，限制每个节点都有不受控的提案权利，这两个目标听起来似乎是矛盾的，但现实世界中的选举就很符合这种在平等节点中挑选意见领袖的情景。（解决了单点问题）

Multi Paxos 对 Basic Paxos 的核心改进是增加了“选主”的过程。

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

当选主完成之后，除非主节点失联之后重新发起竞选，否则从此往后，就只有主节点本身才能够提出提案。此时，无论哪个提案节点接收到客户端的操作请求，都会将请求转发给主节点来完成提案，而主节点提案的时候，也就无法再次经过准备过程，因为可以视作是经过选举时的那一次准备之后，后续的提案都是对相同提案 ID 的一连串的批准过程。也可以通俗理解为选主过后，就不会再有其他节点与他竞争，相当于是处于无并发的环境当中进行的有序操作，所以此时系统中要对某个值达成一致，只需进行一次批准的交互即可。

此时二元组(id, value) 变成了三元组(id, i, value)，这是因为需要给主节点增加一个“任期编号”，这个编号必须是严格单调递增的，以应付主节点陷入网络分区后重新恢复，但另外一部分节点仍有多数派，且已经完成了重新选主的情况，此时必须以任期编号大的主节点为主。当节点有了选主机制的支持，在整体看来，就可以进一步简化节点角色，统统以“节点”来代替，节点只有主（Leader）和从（Follower）的区别，如下图：

在此前的基础上，我们换一个角度来重新思考“分布式系统中如何对某个值达成一致”这个问题

可以把该问题划分为三个子问题来考虑，可以证明当以下三个问题同时被解决时，即等价于达成共识：

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

选主问题尽管还涉及许多工程上的细节，如心跳、随机超时、并行竞选等，但只论原理的话，Paxos 算法的操作步骤已经对选主有足够的介绍，下面我们直接来解决数据在网络各节点间的复制问题。（Paxos 中的提案、Raft 中的日志）

在正常情况下，当客户端向主节点发起一个操作请求，如提出“将某个值设置为 X”，此时主节点将 X 写入自己的变更日志，但先不提交，接着把变更 X 的信息在下一次心跳包中广播给所有的从节点，并要求从节点回复确认收到的消息，从节点收到信息后，将操作写入自己的变更日志，然后给主节点发送确认签收的消息，主节点收到过半数的签收消息后，提交自己的变更、应答客户端并且给从节点广播可以提交的消息，从节点收到提交消息后提交自己的变更，数据在节点间的复制宣告完成（2PC要求是所有参与者回复Prepared才能commit，而这里的数据复制过程只需要多数派回复签收）。

在异常情况下，网络出现了分区，部分节点失联，但只要仍能正常工作的节点的数据量能够满足多数（过半数）的要求，分布式系统就仍能正常工作，这时候数据复制过程如下：

• 假设有 S1、S2、S3、S4、S5 五个节点，S1 是主节点，由于网络故障，导致 （S1、S2 ）和 （S3、S4、S5 ）之间彼此无法通信，形成网络分区。
• 一段时间后，S3、S4、S5 三个节点中的一个（譬如 S3）最先达到心跳超时的阀值，获知当前分区中已经不存在主节点了，它向所有节点发出自己要竞选的广播，并收到了 S4、S5 节点的批准响应，加上自己一共三票，即得到了多数派的支持，竞选成功，此时系统中同时存在 S1 和 S3 两个主节点，但由于网络分区，它们不会知道彼此的存在。
• 这时，客户端发起操作请求：
  • 如果客户端连接到了 S1、S2 之一，都将由 S1 处理，但由于操作只能获得最多两个节点的响应，不构成多数派的批准，所以任何变更都无法成功提交；
  • 如果客户端连接到了 S3、S4、S5 之一，都将由 S3 处理，此时操作可以获得最多三个节点的响应，构成多数派的批准，是有效的，变更可以被提交，即系统可以继续提供服务；
  • 事实上，以上两种“如果”很少有机会能并存。网络分区是由于软、硬件或网络故障而导致的，内部网络出现了分区，但两个分区仍能分别与外部网络的客户端正常通信的情况甚为少见。更多的场景是算法能容忍网络里下线了一部分节点（更新系统？），按照这个例子来说，如果下线了两个节点，系统正常工作，下线了三个节点，那剩余的两个节点也不可能继续提供服务了。
• 假设现在故障恢复，分区解除，五个节点可以重新通信了：
  • S1和 S3 都向所有节点发送心跳包，从各自的心跳中可以得知两个主节点里的 S3 的任期编号更大，它是最新的，此时五个节点均只承认 S3 是唯一的主节点；
  • S1、S2 回滚它们所有未提交的变更；
  • S1、S2 从主节点发送的心跳包中获得它们失联期间的所有变更（how？是不是找到上次相同提交的语句，将之后的全部复制过来），将变更提交写入本地磁盘；
  • 此时分布式系统个节点的状态达成最终一致。

下面我们来看第三个问题：“如何保证过程是安全的？”选主、数据复制都是很具体的行为，但安全就比较模糊，什么算安全或不安全？

在分布式定理中，Safety 和 Liveness 两种属性是有预定义的术语，在专业的资料中一般翻译成“协定性”和“终止性”，这也是 Lamport 提出的，当时的定义是：

• 协定性(Safety):所有的坏事都不会发生。
• 终止性(Liveness):所有的好事都终将发生，但不知道是什么时候。

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

最后，以上这种把共识问题分解为"Leader Election"、“Entity Replication”、“Safety” 三个问题来思考、解决，即 Raft 算法，后来成为了 Etcd、LogCabin、Consul 等重要分布式程序的实现基础，Zookeeper 的 ZAB 算法与 Raft 的思路也非常类似，这些算法都是 Multi Paxos 的等价派生实现。

摘录问题与解答：

1. ZAB, Multi Paxos和Raft是等价的算法（解决同样问题），但是他们的区别到底在哪里？

   核心原理都是一样：通过随机超时来实现无活锁的选主过程，通过主节点来发起写操作，通过心跳来检测存活性，通过Quorum机制来保证一致性。

   具体细节上可以有差异：譬如是全部节点都能参与选主，还是部分节点能参与，譬如Quorum中是众生平等还是各自带有权重，譬如该怎样表示值的方式，等等。

Gossip 协议

Gossip(说闲话):Trying to squash a rumor is like trying to unring a bell. 试图压制谣言就像掩耳盗铃。

Paxos、Raft、ZAB 等分布式算法经常会被称作是“强一致性”的分布式共识协议，其实这样的抠细节的话是有语病的，它的意思是说尽管系统内部节点可以存在不一致的状态，但从系统外部看来，不一致的情况并不会被观察到，所以整体上看是强一致性的。与它们相对的，还有另外一类被冠以最终一致性的分布式共识协议，这表明系统中不一致的状态有可能会在一定时间内被外部直接观察到。一种典型且极为常见的最终一致性的分布式系统就是 DNS系统，在各节点缓存的 TTL 到期之前，都有可能与真实的域名翻译结果存在不一致。

在本节中，我们将介绍在比特币网络和许多重要分布式框架中都有应用的另一种具有代表性的“最终一致性”的分布式共识协议：Gossip 协议。

Gossip 最早由 施乐公司的 Palo Alto 提出的一种用于分布式数据库在多节点间复制同步数据的算法（似乎回到了本章开头，多数决定即可）。如其名一样，Gossip 的特点：要同步的信息如同留言一般传播、病毒一般扩散。

首先必须强调 Gossip 所解决的问题并不是直接与 Paxos、Raft 这些共识算法等价的。只是基于Gossip 之上可以通过某些方法去实现与 Paxos、Raft 相类似的目标而已。

如比特币网络中使用到了 Gossip 协议，用它来在各个分布式节点中互相同步区块头和区块体的信息，这是整个网络能够正常交换信息的基础，但并不能称作共识；

比特币使用工作量证明(Proof of Work,PoW)来对这个区块由谁来记账这一件事情在全网达成共识，这个目标才可以认为与 Paxos、Raft 的目标是一致的。

下面，我们来了解 Gossip 的具体工作过程。相比 Paxos、Raft 等算法，Gossip 的过程十分简单，它可以看作是以下两个步骤的简单循环：

• 如果有某一项信息需要在整个网络中所有节点中传播，那从信息源开始，选择一个固定的传播周期(如 1 秒)，随机选择它相连的 k 个节点（称为 Fan-Out）来传播信息。
• 每一个节点收到消息后，如果这个消息是它之前没有收到过的，将在下一个周期内，选择除了发送给它消息的那给节点外的其他相邻 k 个节点发送相同的消息，直到最终网络中所有节点都收到了消息，尽管这个过程需要一定时间，但是理论上最终网络中的所有节点都会拥有相同的消息。

根据示意图和 Gossip 的过程描述，我们很容易发现 Gossip 对网络节点的连通性和稳定性及户没有任何要求，它一开始就将网络某些节点只能与一部分节点部分连通(k 的含义是不是就是为了这个)，而不是全联通网络作为前提；能够容忍网络上节点的随意地增加或减少，随意的宕机或重启，新增或重启的节点状态最终会与其他节点同步达成一致(状态机的同步，又对应了本章开头的操作转移的状态机)。

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

同时我们也很容易找到 Gossip 的缺点，消息最终是通过多个轮次的散播而到达全网的，因此它必然会存在全网各节点状态不一致的情况，而且由于是随机选取发送消息的节点（可能重发或一个节点发多久呢——原来每个节点知道自己一共相邻的节点数量和信息），所以尽管可以在整体上测算出统计学意义上的传播速率，但对于个体消息来说，无法准确地预测多长时间才能达成全网一致。另外一个缺点是消息的冗余，同样是由于随机选取发送消息的节点，也就不可避免的发送同一节点的情况，增加了网络的传输压力，也给消息节点带来额外的处理负载。

达到一致性耗费的时间与网络传播中消息冗余量这两个缺点存在一定对立，如果要改善其中一个就会恶化另一个，由此，Gossip 设计了两种可能的消息传播模式：反熵和传谣。反熵代表着事物的混乱程度，反熵的意思就是反混乱，以提升网络各个节点之间的相似度为目标，所以在反熵模式下，会同步节点的全部数据，以消除节点间的差异，目标是整个网络节点的完全一致。但是在节点本身就会发生变动的前提下，这个目标使得整个网络中消息的数量非常庞大，给网络带来巨大的传输开销。而传谣模式是以传播消息为目标，仅仅发送新到达节点的数据，即只对外发送变更消息，这样消息数据量将显著缩减，网络开销也相对较小。