每天净瞎搞

关注:CS/AI/数学/自我提升等

0%

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

导语

为什么要有分布式选举?

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

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

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

    什么是分布式共识?

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

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

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

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

  • 拜占庭将军问题描述的是最困难的,也是最复杂的一种分布式故障场景,除了存在故障行为,还存在恶意行为的一个场景。必须使用拜占庭容错算法(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:仅在所有节点都写入成功后,返回成功

参考

  • 分布式协议与算法实战-极客时间
  • 分布式技术原理与算法解析-极客时间
  • 软件架构设计 大型网站技术架构与业务架构融合之道