分布式共识算法（故障容错算法）系列整理(二)：Bully、Gossip、NWR

本文主要是介绍分布式共识算法（故障容错算法）系列整理(二)：Bully、Gossip、NWR，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

五篇分布式共识系列文章合集：
分布式共识算法（拜占庭容错算法）的系列整理一：PBFT、PoW、PoS、DPos
分布式共识算法（故障容错算法）系列整理(二)：Bully、Gossip、NWR
分布式共识算法（故障容错算法）系列整理(三)：Paxos
分布式共识算法（故障容错算法）系列整理(四)：Raft
分布式共识算法（故障容错算法）系列整理(五)：ZAB

导语

为什么要有分布式选举？

主节点在一个分布式集群中负责对其它节点的协调和管理，它的存在可以保证其它节点的有序运行，以及数据库集群中的写入数据在每个节点上的一致性。（一致性是指，数据在每个集群节点中都是一样的，不存在不同的情况）

分布式选举问题的本质是什么？

传统的分布式共识方法，主要是基于多数投票策略实现的

什么是分布式共识？

在多个节点均可独自操作或记录的情况下，使得所有节点针对某个状态达成一致的过程
本质是“求同存异”

一致性和共识的区别是什么？

一致性：分布式系统中的多个节点之间，给定一系列的操作，在约定协议的保障下，对外界呈现的数据或状态时一致的
共识：分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程
一致性强调结果，共识强调达成一致的过程，共识算法是保障系统满足不同程度一致性的核心技术

拜占庭容错算法和非拜占庭容错算法

拜占庭将军问题描述的是最困难的，也是最复杂的一种分布式故障场景，除了存在故障行为，还存在恶意行为的一个场景。必须使用拜占庭容错算法（Byzantine Fault Tolerance，BFT）。还有：PBFT 算法，PoW 算法
在计算机分布式系统中，最常用的是非拜占庭容错算法，即故障容错算法（Crash Fault Tolerance，CFT）。CFT 解决的是分布式的系统中存在故障，但不存在恶意节点的场景下的共识问题。这个场景可能会丢失消息，或者有消息重复，但不存在错误消息，或者伪造消息的情况。常见的算法有 Paxos 算法、Raft 算法、ZAB 协议

Bully

选举原则

“长者为大”，在所有活着的节点中，选取ID最大的节点作为主节点

假设条件

集群中每个节点均知道其它节点的ID

节点有哪两种角色？初始角色和变化过程是怎样的？

普通节点和主节点
初始化时，所有节点都是平等的，都是普通节点，并且都有成为主节点的权利
当选主成功后，有且仅有一个节点成为主节点，其它节点都是普通节点。当且仅当主节点故障或与其它节点失去联系后，才会重新选主

选举过程中用到的3种消息是哪些？

Election消息：用于发起选举
Alive消息：对Election消息的应答
Victory消息：竞选成功的主节点向其它节点发送的宣誓主权的消息

选举过程是怎样？

1.集群中每个节点判断自己的ID是否为当前活着的节点中ID最大的，如果是，则直接向其它节点发送Victory消息，宣誓自己的主权
2.如果自己不是当前活着的节点中ID最大的，则向比自己大的所有节点发送Election消息，并等待其它节点的回复
3.若在给定的时间范围内，本节点没有收到其它节点回复的Alive消息，则认为自己成为主节点，并向其它节点发送Victory消息，宣誓自己成为主节点；若接收到来自比自己ID大的节点的Alive消息，则等待其它节点发送Victory消息
4.若本节点收到比自己ID小的节点发送的Election消息，则回复一个Alive消息，告知其它节点，我比你大，重新选举

优点

选举速度快、算法复杂度低、简单易实现

缺点

1.需要每个节点有全局的节点信息，因此额外信息存储较多
2.任意一个比当前主节点ID大的新节点或节点故障后恢复加入集群的时候，都可能会触发重新选举，成为新的主节点，如果该节点频繁退出、加入集群，就会导致频繁切主

应用例子

MongoDB的副本集故障转移功能：采用最后操作时间戳来表示ID，时间戳最新的节点其ID，时间戳最新的节点ID最大，即时间戳最新的、活着的节点是主节点

Gossip

定义

Gossip 协议，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致(实现最终一致性)，在极端情况下（比如集群中只有一个节点在运行）也能运行

三要素

直接邮寄(Direct Mail)
反熵(Anti-entropy)
谣言传播(Rumor mongering)

直接邮寄

直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。直接邮寄虽然实现起来比较容易，数据同步也很及时，但可能会因为缓存队列满了而丢数据。即只采用直接邮寄是无法实现最终一致性的

反熵

集群中的节点，每隔一段时间就随机选择某个其它节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性
如上图，节点A通过反熵的方式，修复了节点 D 中缺失的数据
注意，因为反熵熵需要节点两两交换和比对自己所有的数据，执行反熵时通讯成本会很高，不建议频繁执行，可通过引入校验和(Checksum)等机制，降低需要对比的数据量和通讯消息
执行反熵时相关的节点都是已知的，而且节点数量不能太多，如果是一个动态变化或节点数比较多的分布式环境，这时反熵就不适用了，该用谣言传播

反熵修复节点缺失数据的3种方式

以下图中，2 个数据副本的不一致为例
推：将自己的所有副本数据，推给对方，修复对方副本中的熵
拉：拉取对方的所有副本数据，修复自己副本中的熵
推拉：同时修复自己副本和对方副本中的熵

谣言传播

当一个节点有了新数据后，这个节点编程活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据
如图，节点 A 向节点 B、D 发送新数据，节点 B 收到新数据后，变成活跃节点，然后节点 B 向节点 C、D 发送新数据。谣言传播非常具有传染性，它适合动态变化的分布式系统

Quorum NWR

最终一致性和强一致性有什么区别

强一致性能保证写操作完成后，任何后续访问都能读到更新后的值
最终一致性只能保证如果对某个对象没有新的写操作了，最终所有后续访问都能读到相同的最近更新的值，即写操作完成后，后续访问可能会读到旧数据

三要素

N：副本数，又叫复制因子(Replication Factor)
W：写一致性级别(Write Consistency Level)，表示成功完成W个副本更新，才完成写操作
R：读一致性级别(Read Consistency Level)，表示读取一个数据对象时需要读R个副本，即，读取指定数据时，要读 R 副本，然后返回 R 个副本中最新的那份数据
注意：无论客户端如何执行读操作，哪怕它访问的是写操作未强制更新副本数据的节点（比如节点 B），但因为 W(2) + R(2) > N(3)，也就是说，访问节点 B，执行读操作时，因为要读 2 份数据副本，所以除了节点 B 上的 DATA-2，还会读取节点 A 或节点 C 上的 DATA-2，就像上图的样子（比如节点 C 上的 DATA-2），而节点 A 和节点 C 的 DATA-2 数据副本是强制更新成功的。这个时候，返回给客户端肯定是最新的那份数据

N、W、R 值的不同组合，会产生哪两种不同的一致性效果？

当 W + R > N 时，对于客户端来说，整个系统能保证强一致性，一定能返回更新后的那份数据
当 W + R < N 时，对于客户端来说，整个系统只能保证最终一致性，可能会返回旧数据

any、one、quorum、all 这4种写一致性级别，具体的含义

any：任何一个节点写入成功后，或者接收节点已将数据写入Hinted-handoff缓存(即写其他节点失败后，本地节点上缓存写失败数据的队列) 后，就会返回成功给客户端
one：任何一个节点写入成功后，立即返回成功给客户端，，不包括成功写入到 Hinted-handoff 缓存
quorum：当大多数节点写入成功后，就会返回成功给客户端。此选项仅在副本数大于 2 时才有意义，否则等效于 all
all：仅在所有节点都写入成功后，返回成功