【即见未来,为何不拜】聊聊分布式系统中的故障监测机制——Phi Accrual failure detector

前言

昨天在看tcp拥塞控制中的BBR(Bottleneck Bandwidth and Round-trip propagation time)算法时,发现了这一特点:
在BBR以前的拥塞控制算法中(如Reno、Cubic、Vegas),都依赖于丢包事件的发生,在高并发时则会看到网络波动的现象。

而在BBR诞生后,由于其基于数学模型的思想,BBR通过对包延迟的实时计算,持续对瓶颈带宽进行估算,使得网络又快又稳。
bbr

又看了些BBR的相关资料后,笔者内心有被其中的数学机制深深惊艳

BBR所涉及到的内容相对复杂,本文不进一步展开,本文记录一下与BBR核心思想类似的:Phi Accrual failure detector

这也是在我看了BBR后,所联想到的在平时项目中经常遇到一个技术。

存活探测机制

在了解Phi Accrual failure detector之前,一起回顾下在计算机中经常用到的一种技术:节点的存活探测。
speak

用《西游记》的片段来讲,节点的存活探测可以描述为:“我叫你一声,你敢答应吗?”

其对应的结果,只有以下两种情况:

  1. 答应了,则对方是存活的。
  2. 未应答,则对方可能挂了。

传统存活探测机制

存活探测机制在分布式集群应用中应用非常广泛,如spring cloudA服务调用B服务时,被调用的B服务一定是从注册中心中返回的存活(可用)实例。
nacos
亦或者,在开源SDN系统ONOS中,判断集群中的各兄弟节点是否存活,以判断是否需要触发设备的Master角色切换。
onos-atomix

对于时效性比较高的场景,我们都期望存活探测的判断能又快又准。毕竟慢了会导致资源不可用,误判则又会耗费额外的资源,这些问题,我们都希望能避免掉。

为此,在时效性准确性的综合考量下,多采用定时+多次确认的方式来实现对节点的存活监测
bfd

在计算机网络领域中,BFD(Bidirectional Forwarding Detection)则是存活探测机制中比较有代表性的技术,它的实现过程也成为了许多系统自实现存活检测的参考对象。

bfd2
一起回顾下BFD的故障监测机制,过程主要如下:

  1. 监听UDP:3784和3785端口
  2. 默认每1000毫秒发送一个ECHO包,用以探测对端(被监测方)是否存活
  3. 如果连续3个周期(1000ms*3,3s)未收到对端发来的ECHO包,则认为对端(被监测方)挂了

speak2
翻译成《西游记》中的场景,则为:
银角大王孙悟空(被检测者)叫了一次”孙行者“后,孙悟空没有理会他(紫金葫芦没有反应),银角大王会再次重叫:“者行孙”、“行者孙”

然而,网络通信是一个非常复杂的过程,一个看似简单的点对点通信中间可能会经过大量的设备,任何一个链路短板都可能造成各种问题,通常呈现出诸如:丢包、时延过长、包损坏等现象。

转为《西游记》的场景:孙悟空(被检测者)向银角大王回应说”爷爷在此”

  • 丢包:这时天空刮起了大风把声音吹跑了,银角大王处无法听到
  • 时延过大:刮起的大风是一个会弧形移动的风(龙卷风)转了一圈后才挂到银角大王的位置
  • 包损伤孙悟空(被检测者)和银角大王中间有很多小妖叽叽喳喳的喊叫,导致孙悟空说的”爷爷在此”在银角大王处只能依稀听到一个“爷”
    ye

举个链路延迟导致误判的例子:A节点检测B节点是否可达,在这两个节点并发不高的情况下,发送收到一个检测包的时延为5ms,当遇到这两个节点在传输大量数据(高并发)时,则可能会导致3000ms后才能收到这个检测包,则A节点会认为B节点已不可达,但实际情况是B节点是正常的,只是中间链路稍微慢了一点而已。
如果使用传统的链路检测机制,则无法识别出此种情况。

缺点
总结一下传统节点故障的缺点

  1. 在系统高并发或链路不佳时,容易误判
  2. 系统需要提前设置故障超时时间,周期过长会造成故障识别慢,周期过短容易误判

Phi Accrual failure detector

为了解决上面的情况,实现以下几点:

  • 存活探测的判断能又快又准
  • 降低节点故障误判的概率
  • 自动调整阈值周期

一种基于数学模型的故障检测机制便诞生了——Phi Accrual failure detector。

spring
在论文《Phi Accrual failure detector》中,描述了一种如何使用概率来表征被检测节点是否故障的方法。
其中,Phi也就是符号:φ,公式如下:
φ
用它代表:当前时刻(t now)被检测节点挂掉的概率。

  • phi的值越大,则当前时刻被检测节点挂掉的概率越大
  • -log10为对数计算,以将概率P later的概率值转为较大的正数,以方便计算
  • P later中的t now- T last的含义是:最后一次收到心跳当前时间时间间隔,一般使用的单位为毫秒

它的核心思想为:假设网络延迟符合某种概率分布(如正态分布或指数分布),当一个节点预期的心跳包没有按时到达时,随着时间的推移,phi 值会逐渐增加。

在具体的Phi Accrual failure detector方法实现中,一般采用指数分布来进行实现。

指数分布(扩展阅读)

ed
指数分布(Exponential Distribution)是一种连续概率分布,通常用于描述事件发生的时间间隔或等待时间。
假设某件事以一定的平均速率发生,指数分布就可以用来描述该事件发生前的时间长度。

以一个经典的包子铺场景为例:
假设你是一位卖包子的商家,包子店的客流量是随机的,即顾客的到来是无法提前预测的。如果我们要估计顾客之间的到达时间(比如两位顾客之间需要等待的时间),这就可以使用指数分布来建模。
baozi

故障检测中的具体实现

phi-content
在分布式系统的故障检测中,每个节点会定期发送心跳包到监控系统(通常是一个中央协调器或其他节点),系统通过记录每次心跳包的到达时间来计算心跳间隔时间(即两个心跳之间的时间差),而这个周期性的心跳间隔时间一般来讲都是服从指数分布的。

节点A监测节点B是否存活为例,节点B每间隔500ms向节点A发送一次心跳包,如节点A已经2000ms没有收到节点B的心跳包了,则会认为节点B大概率是挂了。
那么,节点A平均每500ms会收到节点B的心跳包,要预测节点A下一次收到节点B的心跳包的间隔,则可以用指数分布来预测。
ed-chart

指数分布概率密度函数是:pro

在节点存活监测场景中:

  • λ 是心跳到达的频率(即单位时间内预期有多少次心跳信号到达),如果心跳信号平均每 𝑇 秒发生一次,那么 𝜆=1/𝑇,即λ 是时间的倒数。如节点每500ms(即 0.5秒)发送一次心跳,则𝜆=1/0.5=2
  • t 为从上一次心跳到当前的时间间隔

从上面的例图可以看出,随着时间 𝑇 的增加,节点A还未节点B的心跳包的概率密度逐渐减小

也就是:未收到被监测点的心跳包时间越久,被监测节点已经挂了的概率就越大

将其换成函数则是指数分布中的累积分布函数(CDF),即计算时间 x 后还没有收到被监测节点的心跳包,被监测节点已经故障概率
down-pro

由于概率值它是一个百分数,在计算机中为了方便计算和处理,往往使用对数计算它这个概率值转为一个大一点的正数,再给这个数取个代号——Phi

最后得出Phi 值的计算公式为:
phi-final

  • P(T>t) 是在时间 t 时刻仍然没有收到心跳的概率
  • λ 是心跳到达的速率(即平均心跳频率的倒数)

因为log10(𝑒)≈0.4343,最后得 φ ≈ 0.4343⋅λ⋅T

Phi的参考值及含义:
phi = 0:刚收到心跳信号,节点正常
phi = 2-3:系统开始有轻微的怀疑,但仍然认为节点大概率正常
phi ≥ 8:系统高度怀疑节点已经失效

s-window
在实际应用中,λ 通常使用一个固定大小的滑动窗口中的平均值计算而来,滑动窗口中记录的是被监测节点心跳包间隔时长

使用滑动窗口来保存历史心跳间隔数据,这也是实现λ动态自适应调整的重要原因。

atomix中的具体实现

使用Phi Accrual failure detector机制实现的节点存活监测开源框架非常多,比较知名的有Apache Cassandra、Akka、Hazelcast等

这里以SDN开源框架onos中的atomix组件为例,看一下它在ONOS集群中判断ONOS兄弟节点是否存活的相关源码,本文只关注Phi Accrual failure detector的实现部分。

atomix中实现了Phi Accrual failure detector的类为PhiAccrualFailureDetector,代码如下:

import org.apache.commons.math3.stat.descriptive.DescriptiveStatistics;/*** Phi Accrual failure detector.* <p>* A modified version based on a paper titled:* "The φ Accrual Failure Detector" by Hayashibara, et al.*/
public class PhiAccrualFailureDetector {// Default value,窗口大小:250private static final int DEFAULT_WINDOW_SIZE = 250;// 最小窗口大小:25private static final int DEFAULT_MIN_SAMPLES = 25;// phi的计算因子:前文中提到的0.4343private static final double DEFAULT_PHI_FACTOR = 1.0 / Math.log(10.0);private final int minSamples;private final double phiFactor;// 历史心跳数据private final History history;/*** Creates a new failure detector with the default configuration.*/public PhiAccrualFailureDetector() {this(DEFAULT_MIN_SAMPLES, DEFAULT_PHI_FACTOR, DEFAULT_WINDOW_SIZE);}/*** Creates a new failure detector.** @param minSamples the minimum number of samples required to compute phi* @param phiFactor  the phi factor*/public PhiAccrualFailureDetector(int minSamples, double phiFactor) {this(minSamples, phiFactor, DEFAULT_WINDOW_SIZE);}/*** Creates a new failure detector.** @param minSamples the minimum number of samples required to compute phi* @param phiFactor  the phi factor* @param windowSize the phi accrual window size*/public PhiAccrualFailureDetector(int minSamples, double phiFactor, int windowSize) {this.minSamples = minSamples;this.phiFactor = phiFactor;this.history = new History(windowSize);}/*** 最后一个心跳到达的时间** @return the last time a heartbeat was reported*/public long lastUpdated() {return history.latestHeartbeatTime();}/*** Report a new heart beat for the specified node id.*/public void report() {report(System.currentTimeMillis());}/*** 上报一个最新的心跳到达时间* Report a new heart beat for the specified node id.** @param arrivalTime arrival time*/public void report(long arrivalTime) {checkArgument(arrivalTime >= 0, "arrivalTime must not be negative");long latestHeartbeat = history.latestHeartbeatTime();// 使用当前时间-上次接收时间,得到时间间隔history.samples().addValue(arrivalTime - latestHeartbeat);// 更新最后一次时间间隔history.setLatestHeartbeatTime(arrivalTime);}/*** phi计算,重点* Compute phi for the specified node id.** @return phi value*/public double phi() {long latestHeartbeat = history.latestHeartbeatTime();DescriptiveStatistics samples = history.samples();if (samples.getN() < minSamples) {//当样本数不足时,返回0.0,代表被监测节点是一定存活的return 0.0;}// 样本数充足,使用当前时间计算phi值return computePhi(samples, latestHeartbeat, System.currentTimeMillis());}/*** phi具体计算* Computes the phi value from the given samples.* <p>* The original phi value in Hayashibara's paper is calculated based on a normal distribution.* Here, we calculate it based on an exponential distribution.** @param samples       the samples from which to compute phi* @param lastHeartbeat the last heartbeat* @param currentTime   the current time* @return phi*/private double computePhi(DescriptiveStatistics samples, long lastHeartbeat, long currentTime) {// 获取出样本总数long size = samples.getN();// 计算出时间间隔long t = currentTime - lastHeartbeat;// samples.getMean()为样本的均值(平均间隔时间)// phi= 计算因子*时间间隔/心跳到达的速率return (size > 0)? phiFactor * t / samples.getMean(): 100;}/*** Stores the history of heartbeats for a node.*/private static class History {//存储样本的集合private final DescriptiveStatistics samples;long lastHeartbeatTime = System.currentTimeMillis();private History(int windowSize) {this.samples = new DescriptiveStatistics(windowSize);}DescriptiveStatistics samples() {return samples;}long latestHeartbeatTime() {return lastHeartbeatTime;}void setLatestHeartbeatTime(long value) {lastHeartbeatTime = value;}}
}

PhiAccrualFailureDetector 部分的源码和上文中的理论知识完全符合,总结起来就是:

phi = 计算因子 * 时间间隔 / 心跳到达的速率

再看一下atomix中调用phi计算的具体代码:

  @Overridepublic CompletableFuture<Void> join(BootstrapService bootstrap, NodeDiscoveryService discovery, Member member) {if (started.compareAndSet(false, true)) {// ……// 注册心跳处理器,handleHeartbeat函数bootstrapService.getMessagingService().registerHandler(HEARTBEAT_MESSAGE, this::handleHeartbeat, heartbeatScheduler);// 定时发送心跳,默认1000ms发送一次heartbeatFuture = heartbeatScheduler.scheduleAtFixedRate(this::sendHeartbeats, 0, config.getHeartbeatInterval().toMillis(), TimeUnit.MILLISECONDS);LOGGER.info("Started");}return CompletableFuture.completedFuture(null);}/*** 收到心跳包的处理逻辑* Handles a heartbeat message.*/private byte[] handleHeartbeat(Address address, byte[] message) {GossipMember remoteMember = SERIALIZER.decode(message);LOGGER.trace("{} - Received heartbeat: {}", localMember.id(), remoteMember);// 更新被监测节点的最后一次包到达时间failureDetectors.computeIfAbsent(remoteMember.id(), n -> new PhiAccrualFailureDetector()).report();updateMember(remoteMember, true);// Return only reachable members to avoid populating removed members on remote nodes from unreachable members.return SERIALIZER.encode(Lists.newArrayList(members.values().stream().filter(member -> member.isReachable()).collect(Collectors.toList())));}/*** Sends a heartbeat to the given peer.*/private CompletableFuture<Void> sendHeartbeat(GossipMember member) {return bootstrapService.getMessagingService().sendAndReceive(member.address(), HEARTBEAT_MESSAGE, SERIALIZER.encode(localMember)).whenCompleteAsync((response, error) -> {if (error == null) {Collection<GossipMember> remoteMembers = SERIALIZER.decode(response);for (GossipMember remoteMember : remoteMembers) {if (!remoteMember.id().equals(localMember.id())) {updateMember(remoteMember, remoteMember.id().equals(member.id()));}}} else {LOGGER.debug("{} - Sending heartbeat to {} failed", localMember.id(), member, error);// ……PhiAccrualFailureDetector failureDetector = failureDetectors.computeIfAbsent(member.id(), n -> new PhiAccrualFailureDetector());// 计算出当前phi值double phi = failureDetector.phi();// phi值大于阈值(8),或处于初始化时上次收到心跳包距离当前时间超过了最长间隔阈值(10s)if (phi >= config.getPhiFailureThreshold()|| (phi == 0.0 && System.currentTimeMillis() - failureDetector.lastUpdated() > config.getFailureTimeout().toMillis())) {// 认为被监测的节点已经挂了,触发节点已下线的事件if (members.remove(member.id()) != null) {failureDetectors.remove(member.id());post(new GroupMembershipEvent(GroupMembershipEvent.Type.MEMBER_REMOVED, member));}}}}, heartbeatScheduler).exceptionally(e -> null).thenApply(v -> null);}

atomix中监测兄弟节点是否正常的代码位于HeartbeatMembershipProtocol类中,其实现的行为与《Phi Accrual failure detector》中所描述的过程基本一致:

  1. 当新的onos节点加入到集群中时,定时(默认1s)向其发送心跳包
    • 当发送心跳包失败时(atomix中用的tcp方式发送),计算phi值
    • 所计算的phi值大于阈值(默认8),则判定对端不可达
    • phi值小于0但距离最后心跳包时间间隔过长(默认10秒),则判定对端不可达(用于处理采用数据不足的情况,类似于tcp拥塞控制中的慢启动
  2. 当收到兄弟节点的心跳包后,会持续更新采样数据
    • 更新间隔窗口数据
    • 更新最后心跳包最新接收时间

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/450682.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【含开题报告+文档+PPT+源码】基于SSM的景行天下旅游网站的设计与实现

开题报告 随着互联网的快速发展&#xff0c;旅游业也逐渐进入了数字化时代。作为一个旅游目的地&#xff0c;云浮市意识到了互联网在促进旅游业发展方面的巨大潜力。为了更好地推广云浮的旅游资源&#xff0c;提高旅游服务质量&#xff0c;云浮市决定开发一个专门的旅游网站。…

深入理解计算机系统--计算机系统漫游

对于一段最基础代码的文件hello.c&#xff0c;解释程序的运行 #include <stdio.h>int main() {printf ( "Hello, world\n") ;return 0; }1.1、信息就是位上下文 源程序是由值 0 和 1 组成的位&#xff08;比特&#xff09;序列&#xff0c;8 个位被组织成一组…

梯度下降算法优化—随机梯度下降、小批次、动量、Adagrad等方法pytorch实现

现有不足 现有调整网络的方法是借助成本函数的梯度下降方法&#xff0c;也就是给函数作切线&#xff0c;不断逼近最优点&#xff0c;即成本函数为零的点。 梯度下降的一般公式为&#xff1a; 即根据每个节点成本函数的梯度进行更新&#xff0c;使用该方法有一些问题&#xff…

探索OpenCV的人脸检测:用Haar特征分类器识别图片中的人脸

目录 简介 OpenCV和Haar特征分类器 实现人脸检测 1. 导入所需库 2. 加载图片和Haar特征分类器 3. 检测人脸 4. 标注人脸 5. 显示 6、结果展示 结论 简介 在计算机视觉和图像处理领域&#xff0c;人脸识别是一项重要的技术。它不仅应用于安全监控、人机交互&#xff0…

10秒钟用Midjourney画出国风味的变形金刚

上魔咒 Optimus Prime comes from the movie Transformers, Chinese style, Wu ShanMing, Ink Painting Halo Dyeing, Conceptual of the Digita Art, MasterComposition, Romantic Ancient Style, Inspired by traditional patterns and symbols, Minimalism, do not con…

day01 -- MybatisPlus

1. MybatisPlus简介 有基础的同学可结合资源中的代码一起看 MyBatis 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为简化开发、提高效率而生 特性 通用的 CRUD 操作&#xff1a;内置通用 Mapper、通用 Service&#xff0c;仅仅通过少量配置即可实…

私有化部署大模型最佳解决方案 Ollama (8B)模型

私有化部署大模型Ollama 为什么需要私有化部署大模型一、Ollama本地部署Llama3大模型二、Langchain4j调用Ollama本地部署模型API三、Ollama本地部署nomic向量模型四、Spring AI调用Ollama本地部署模型API 为什么需要私有化部署大模型 企业考虑成本和数据隐私问题&#xff0c;会…

021_Thermal_Transient_in_Matlab统一偏微分框架之热传导问题

Matlab求解有限元专题系列 固体热传导方程 固体热传导的方程为&#xff1a; ρ C p ( ∂ T ∂ t u t r a n s ⋅ ∇ T ) ∇ ⋅ ( q q r ) − α T d S d t Q \rho C_p \left( \frac{\partial T}{\partial t} \mathbf{u}_{\mathtt{trans}} \cdot \nabla T \right) \nab…

BM算法(手算版)

BM 算法 BM 算法是一种字符串匹配的算法。 与 KMP 相比&#xff0c;BM 算法不扫描全部输入字符&#xff0c;平均匹配时间 c・n, 常量 c <1 (随机或真实文本), 但最坏情况是 O (n・m). 可以将 BM 算法的最坏情况改进到 O (n)&#xff1a;通过记录文本后缀中最…

计算机系统简介

一、计算机的软硬件概念 1.硬件&#xff1a;计算机的实体&#xff0c;如主机、外设、硬盘、显卡等。 2.软件&#xff1a;由具有各类特殊功能的信息&#xff08;程序&#xff09;组成。 系统软件&#xff1a;用来管理整个计算机系统&#xff0c;如语言处理程序、操作系统、服…

群晖前面加了雷池社区版,安装失败,然后无法识别出用户真实访问IP

有nas的相信对公网都不模式&#xff0c;在现在基础上传带宽能有100兆的时代&#xff0c;有公网代表着家里有一个小服务器&#xff0c;像百度网盘&#xff0c;优酷这种在线服务都能部署为私有化服务。但现在运营商几乎不可能提供公网ip&#xff0c;要么自己买个云服务器做内网穿…

通过github创建自己网页链接的方法

文章目录 要使用GitHub创建静态网页链接&#xff0c;可以按照以下详细步骤进行操作&#xff1a;一、准备阶段二、创建仓库并配置三、准备并上传静态网站文件四、配置GitHub Pages五、访问和更新你的静态网页 要使用GitHub创建静态网页链接&#xff0c;可以按照以下详细步骤进行…

uniapp微信小程序调用百度OCR

uniapp编写微信小程序调用百度OCR 公司有一个识别行驶证需求&#xff0c;调用百度ocr识别 使用了image-tools这个插件&#xff0c;因为百度ocr接口用图片的base64 这里只是简单演示&#xff0c;accesstoken获取接口还是要放在服务器端&#xff0c;不然就暴露了自己的百度项目k…

Xshell使用密钥远程登录Ubuntu 22.04报错:所选的用户密钥未在远程主机上注册。请再试一次

报错截图如下&#xff1a; 问题原因&#xff1a; Ubuntu 22.04 不支持 Xshell使用的私钥。 查看系统支持的私钥&#xff1a;sudo sshd -T | egrep "pubkey" ~$ sudo sshd -T | egrep "pubkey" pubkeyauthentication yes pubkeyacceptedalgorithms ssh-ed…

基于SpringBoot+Vue的旅游服务平台【提供源码+答辩PPT+参考文档+项目部署】

&#x1f4a5; ① 前言&#xff1a;这两年毕业设计和毕业答辩的要求和难度不断提升&#xff0c;传统的JavaWeb项目缺少创新和亮点&#xff0c;往往达不到毕业答辩的要求&#xff01; ❗② 如何解决这类问题&#xff1f; 让我们能够顺利通过毕业&#xff0c;我也一直在不断思考、…

ROS 的 urdf 中 link 和 joint 的子标签中 origin 的含义

主要参考文章——主要文章&#xff0c;官方关于urdf的介绍和官方文档的翻译解析 link标签里面的origin含义 link标签里面有三个主要的子标签&#xff0c;分别是visual——连杆的外观和坐标系&#xff0c;collisoin——连杆的碰撞属性和inertial——连杆的惯性设置 首先&…

【AIGC】AI如何匹配RAG知识库: Embedding实践,语义搜索

引言 RAG作为减少模型幻觉和让模型分析、回答私域相关知识最简单高效的方式&#xff0c;我们除了使用之外可以尝试了解其是如何实现的。在实现RAG的过程中Embedding是非常重要的手段。本文将带你简单地了解AI工具都是如何通过Embedding去完成语义分析匹配的。 Embedding技术简…

低空经济发展迅猛,无人机设计制造技术详解

低空经济的迅猛发展&#xff0c;为无人机设计制造技术带来了新的机遇和挑战。无人机作为低空经济中的重要组成部分&#xff0c;其设计制造技术直接关系到无人机的性能、安全性和应用场景的拓展。以下是对无人机设计制造技术的详细解析&#xff1a; 一、无人机设计技术 1. 气动…

【HTML + CSS 魔法秀】打造惊艳 3D 旋转卡片

HTML结构 box 类是整个组件的容器。item-wrap 类是每个旋转卡片的包装器&#xff0c;每个都有一个内联样式–i&#xff0c;用于控制动画的延迟。item类是实际的卡片内容&#xff0c;包含一个图片。 <template><div class"box"><div class"item…

STM32L010F4 最小系统设计

画一个 STM32L010F4 的测试板子...... by 矜辰所致前言 最近需要用到一个新的 MCU&#xff1a; STM32L010F4 &#xff0c;上次测试的 VL53L0X 需要移植到这个芯片上&#xff0c;网上一搜 STM32L010F4&#xff0c;都是介绍资料&#xff0c;没有最小系统&#xff0c;使用说明等。…