本文主要是介绍分布式共识算法（故障容错算法）系列整理(二)：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：仅在所有节点都写入成功后，返回成功
参考
- 分布式协议与算法实战-极客时间
- 分布式技术原理与算法解析-极客时间
- 软件架构设计 大型网站技术架构与业务架构融合之道
这篇关于分布式共识算法（故障容错算法）系列整理(二)：Bully、Gossip、NWR的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
