跳转至

分布式系统之故障检测

如果一棵树在森林中倒下了,在它周围没有任何人,它会发出声音吗? -- 未知作者

为了让一个系统正确地应对故障,必须以及时的方式检测故障。一个故障的进程尽管不能应答,但可能还会被联系到,增加时延以及减少整个系统的可用性。

在异步分布式系统中检测故障(例如不加任何超时机制)非常困难,因为无法确定进程是否故障还是运行缓慢,并且需要无限长的时间进行响应。我们在“FLP 不可能”中讨论了与此相关的问题。

注:FLP 不可能,现实生活都是异步系统,因为系统中各个节点之间的延时,是否宕机都是不确定的,在最小化异步系统中,是否存在一个可以解决一致性问题的确定性共识算法?在网络可靠,但允许节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性共识算法。

FLP 是基于异步系统而做的证明,它假定确定性算法都不能使用任何时钟或者超时机制,如果算法可以使用超时或者其他方法来检测崩溃节点(即使怀疑可能是误报),那么可以实现稳定的共识方案。

因此,对于实际的分布式系统而言,通常达成共识是可行的。

分布式系统的系统中其它理论:CAP 和 BASE。

死亡,失败和崩溃等术语通常用于描述已完全停止执行其步骤的进程。 诸如无响应,故障和缓慢等术语用于描述可疑的过程,这些过程实际上可能已经失效。

故障可能发生在连接级别(进程之间的消息丢失或传递缓慢),也可能发生在进程级别(进程崩溃或运行缓慢),并且速度始终不能与故障区分开。这意味着在错误地将活动过程怀疑为已死(产生假阳性)与延迟将无响应过程标记为已死之间进行权衡,这给了它怀疑的好处并期望它最终做出响应(产生假阴性)。

故障检测器是一个本地子系统,负责识别失败或不可达的进程,以将其从算法中排除,并在保持安全性的同时保证活性。

活性安全性是描述算法解决特定问题的能力及其输出正确性的属性。更正式地说,活性是一种属性,可以保证必须发生特定的预期事件。例如,如果进程之一失败,则故障检测器必须检测到该故障。安全保证不会发生意外事件。例如,如果故障检测器将某个进程标记为已死,则该进程实际上必须是已死。

从实际的角度看,将故障进程排除出去可以避免不必要的工作,并防止错误传播和级联故障,同时在排除可疑活动进程时会降低可用性。

故障检测算法应表现出几个基本属性。首先,每个无故障的成员最终都应该注意到进程失败,并且算法应该能够取得进展并最终达到其最终结果。此属性称为完整性

我们可以通过其效率来判断算法的质量:故障检测器能够多快地识别过程故障。做到这一点的另一种方法是查看算法的准确性:是否精确地检测到过程故障。换句话说,如果算法错误地认为实时进程失败或无法检测到现有的失败,则该算法是不准确的。

我们可以将效率和准确性之间的关系视为一个可调参数:效率更高的算法可能精度较低,而精度更高的算法通常效率较低。建立一个既准确又高效的故障检测器,证明是不可能的。同时,允许故障检测器产生假阳性(即,错误地将活动进程标识为失败,反之亦然)。

故障检测器是许多共识和原子广播算法的必不可少的先决条件和组成部分,我们将在本书的后面部分对此进行讨论。

许多分布式系统通过使用心跳来实现故障检测器。这种方法因其简单性和强大的完整性而非常受欢迎。我们在这里讨论的算法假定不存在拜占庭式故障:进程不会试图故意使它们的状态或邻居状态处于说谎状态。

心跳和 ping

可以通过触发周期性流程查询远端进程的状态:

  • 触发一个 ping,发送消息给远端进程,检查是否活着,并且期望在特定的时间内返回应答。
  • 触发一个心跳,当进程活跃时,通知其他人其还存活。

在例子中,使用 ping,但是同样的问题可以通过心跳来解决,也可以产生类似的结果。

每个进程维护其他进程(活跃,死亡,可疑)的列表,并且用最后的响应来更新每个进程。如果一个进程长时间不能返回 ping 消息的应答,则将其标记为可疑的。

图 1 展示了正常的系统处理流程:进程 P1 查询邻近节点P2 的状态,P2 返回确认消息。

image-20200125000733021

图 1:使用 ping 故障检测,正常流程,没有延迟
相反,图 2 展示了确认消息延迟后,可能会导致将活跃的进程被标记为宕机。

image-20200125000829621

图 2:使用 ping 故障检测,响应有延迟,在下一个消息被发送后才收到
很多故障检测算法基于心跳和超时。例如,Akka,一个流行的用于构建分布式系统的框架,有一个到期失败检测器,该检测器使用心跳信号,如果在固定的时间间隔内没有注册,则报告进程故障。

这种方法有几个潜在的缺点:其精度取决于对ping频率和超时的谨慎选择,并且从其他进程的角度来看,它不能捕获进程可见性(请参阅“外包心跳”)。

无超时的故障检测器

一些算法避免了依靠超时来检测故障。例如,心跳(无超时故障检测器)是一种仅对心跳计数的算法,它允许应用程序根据心跳计数器向量中的数据检测进程故障。由于此算法没有超时限制,因此可以在异步系统假设下运行。

该算法假定任何两个正确的进程都通过一条公平的路径相互连接,该路径仅包含公平的链接(即,如果通过该链接无限次发送消息,那么它也将被无限次接收),并且每个进程都知道网络中所有其他进程的存在。

每个进程维护一个邻居列表和与其关联的计数器。进程从向其邻居发送心跳消息开始。每条消息都包含心跳迄今传播的路径。初始消息包含路径中的第一个发送者和一个唯一标识符,可用于避免多次广播同一消息。

当进程接收到新的心跳消息时,它会为路径中存在的所有参与者递增计数器,并将心跳发送到路径中不存在的参与者,并将自身附加到路径中。进程一旦看到所有已知进程已经接收到消息就停止传播消息(换句话说,进程ID出现在路径中)。

由于消息是通过不同的进程传播的,并且心跳路径包含从邻居接收到的汇总信息,因此即使两个进程之间的直接链接出现故障,我们也可以(正确)将不可达进程标记为活动。

心跳计数器代表系统的全局视图。此视图捕获了心跳如何相对于彼此传播,从而使我们可以比较进程。但是,此方法的缺点之一是解释心跳计数器可能非常棘手:我们需要选择一个可以产生可靠结果的阈值。除非我们能做到,否则该算法将错误地将活动进程标记为可疑进程。

外包心跳

如图3所示,进程P1向进程P2发送ping消息。 P2不响应该消息,因此P1通过选择多个随机成员(P3和P4)继续进行。 这些随机成员尝试将心跳消息发送到P2,如果响应,则将确认转发回P1。

image-20200125002035340

图 9-3:“外包“ 心跳
这样可以考虑直接和间接的可达性。 例如,如果我们有进程P1,P2和P3,则可以从P1和P2的角度检查P3的状态。

外包心跳通过分配负责在成员组中进行决策的职责来进行可靠的故障检测。 这种方法不需要将消息广播到广泛的对等组。 由于可以并行触发外包的心跳请求,因此这种方法可以快速收集有关可疑进程的更多信息,并允许我们做出更准确的决策。

φ-accrual 故障检测器

不把节点故障作为二元问题(该进程只能处于运行或者宕机状态),而是连续捕获受检视进程崩溃的可能性。

它通过保持滑动窗口,从对等进程收集最新心跳的到达时间来工作。该信息用于估计下一个心跳的到达时间,将该近似值与实际到达时间进行比较,并计算可疑级别φ:在当前网络条件下,故障检测器对故障的确定程度。

该算法通过收集和采样到达时间,创建一个可用于对节点运行状况做出可靠判断的视图来工作。 它使用这些样本来计算φ的值:如果该值达到阈值,则将该节点标记为down。 该故障检测器通过调整可将节点标记为可疑节点的配置比例来动态适应网络条件的变化。

从体系结构的角度来看,可以将φ故障检测器视为三个子系统的组合:

  • 监控:通过 ping,心跳,请求-应答来手机活动信息
  • 解释:决定 进程是否被标记为可疑的
  • 动作:一个被执行的回调,标记进程为可疑的

监视进程在心跳到达时间的固定大小的窗口中收集并存储数据样本(假定遵循正态分布)。新到达的消息将添加到窗口,最旧的心跳数据点将被丢弃。

通过确定样本的均值和方差,从样本窗口估计分布参数。该信息用于计算在前一个消息之后的t个时间单位内消息到达的概率。有了这些信息,我们就可以计算出φ,它描述了我们有可能对流程的活跃性做出正确的决定。换句话说,犯错误并收到与所计算的假设相矛盾的心跳的可能性有多大。

这种方法是由日本高级科学技术研究所的研究人员开发的,现已在许多分布式系统中使用。 例如,Cassandra 和 Akka(以及上述的截止日期故障检测器)。

Gossip 和故障检测

避免依赖单节点视图做出决定的另一种方法是 Gossip 风格的故障检测服务,它使用 Gossip(请参阅“Gossip分发”)来收集和分发相邻进程的状态。

每个成员维护其他成员信息,心跳计数器和时间戳列表,指定最后一次增加心跳计数器的时间。每个成员定期增加其心跳计数器,并将其列表分发给随机邻居。 收到消息后,邻居节点会将列表与其自身合并,从而为其他邻居更新心跳计数器。

节点还定期检查状态列表和心跳计数器。如果任何节点没有足够长时间更新其计数器,则视为失败。应谨慎选择此超时时间,以最大程度地减少误报的可能性。 成员之间相互通信的频率(换句话说,最坏情况的带宽)受到限制,并且最多可以随着系统中的多个进程线性增长。

图 4 展示三个通信的进程共享心跳计数器:

a) 三个进程互相通信更新他们的时间戳

b) P3 无法与 P1 通信,但是其时间戳 t6 可疑被 P2 传到 P2

c) P3 宕机,由于不再发送任何更新,

image-20200125074645771

图 9-4:被复制的心跳表用于故障检测
这样,我们可以检测到崩溃的节点以及其他任何群集成员无法访问的节点。 该决定是可靠的,因为群集的视图是来自多个节点的聚合。 如果两台主机之间存在链路故障,则心跳仍然可以通过其他进程传播。 使用 Gossip 传播系统状态会增加系统中消息的数量,但可使得信息更可靠地传播。

反向故障问题声明

由于传播信息并不总是可能的,并且通过通知每个成员传播信息的成本可能很高,因此一种名为FUSE(故障通知服务)的方法着重于可靠且低成本的故障传播,即使在某些网络分区的情况下。

为了检测流程故障,此方法将所有活动的进程按组排列。如果其中一个组不可用,则所有参与者都将检测到故障。换句话说,每次检测到单个进程故障时,都会将其转换并传播为组故障。这意味着可以对存在任何形式的断开连接,分区和节点故障的情况下检测故障。

群组中的进程会定期向其他成员发送ping消息,以查询它们是否仍然存在。如果成员之一由于宕机,网络分区或链接故障而无法响应此消息,则发起此ping的成员将依次停止响应ping消息本身。

图 5 显示了四个通信的进程:

a)初始状态:所有进程都处于活动状态并且可以通信。

b)P2 宕机并停止响应 ping 消息。

c)P4 检测到 P2 失败,并停止响应 ping 消息本身。

d)最终,P1和P3注意到P1和P2都没有响应,并且进程故障传播到整个组。

image-20200125075940920

图 9-5:FUSE 故障检测
所有故障都会从故障源传播到系统中的所有其他参与者。 参与者逐渐停止对ping做出响应,从单个节点故障转换为组故障。

在这里,我们将无法通信作为传播手段。使用此方法的优点是,可以确保每个成员都了解组故障并对其做出适当的反应。缺点之一是,将单个进程与其他进程分开的链接故障也可以转换为组故障,但这视情况而定,也可能是一种优势。应用程序可以使用自己的传播失败定义来解决这种情况。

总结

故障检测器是任何分布式系统的重要组成部分。如FLP不可能结果所示,没有协议可以保证异步系统中的共识。故障检测器有助于增强模型,使我们能够通过在准确性和完整性之间进行权衡来解决共识问题。论文 1中描述了该领域的重要发现之一,证明了故障检测器的实用性,该结果表明即使使用故障检测器产生无数次错误,也可以解决共识。

我们已经介绍了几种用于故障检测的算法,每种算法都使用不同的方法:一些算法侧重于通过直接通信检测故障,某些算法使用广播或 Gossip 来传播信息,而某些算法则通过使用安静退出(换句话说,通信)作为传播手段。现在,我们知道可以使用心跳或ping,严格的截止日期或连续比例。这些方法中的每一种都有其自身的优势:简单,准确或精度。

参考

注:本文翻译自 Database Internals Chapter 9. Failure Detection


  1. Unreliable failure detectors for reliable distributed systems:我们介绍了不可靠的故障检测器的概念,并研究了如何将其用于解决具有崩溃故障的异步系统中的共识。我们用两个属性(完整性和准确性)来描述不可靠的故障检测器。我们证明,即使使用不可靠的故障检测器(会产生无数个错误),也可以解决共识问题,并确定在发生任何数量的崩溃后仍可以使用哪些错误解决方案来解决共识问题,并且哪些错误需要大多数正确的处理过程。我们证明共识和原子广播在具有崩溃故障的异步系统中是等价的。因此,以上结果也适用于原子广播。论文也展示了,此处介绍的故障检测器之一是用于解决共识问题的最弱的故障检测器[Chandra等。1992]。