本文是对于以下项目的算法说明。

https://github.com/xnnyygn/xgossip

失败检测即Failure Detection，在xgossip中主要是指由于网络或者节点当机问题导致无法正常通讯的问题的检测。除此之外，检测到之后系统如何处理也是需要根据实际需求来决定的。以下主要针对这两方面进行讲解。

xgossip中采用的失败检测基于论文《On Scalable and Efficient Distributed Failure Detectors》，即直接ping失败之后会间接ping，两者都失败之后可以认为与节点之间无法正常通讯。为什么有间接ping？个人理解这里主要为了避免部分节点之间通讯不稳定导致成员频繁地被认为已下线。当然，网络分区导致的通讯失败无法通过间接ping解决。

算法步骤

1. 选取一个节点（以下叫测试节点）并尝试ping
2. 一定时间（ping timeout）内返回的话就认为ok，结束
3. 一定时间未返回的话，选择k个节点（不包括测试节点，以下叫做间接节点）要求它们去ping测试节点
4. 间接节点尝试ping测试节点
5. 一定时间内（proxy ping timeout）返回的话就认为ok，向发起节点返回间接ping成功的响应
6. 一定时间内未返回的话，不做任何处理
7. 发起节点收到间接ping成功的响应，认为节点在线，结束
8. 如果一定时间内收不到间接ping成功的响应的话，认为节点可能下线，结束

原论文里有一张sequence图，直接看的话可能更清楚，考虑到版权这里不贴了。

讲一下如何实现。

算法中看起来一个顺序过程，但是在间接ping的阶段如果顺序发送，顺序接受的话，最坏情况下会等待k个proxy ping timeout，并不合算。所以实际实现是异步模型。

这里的异步模型是指，在发送完ping请求或者proxy ping请求之后，不通过socket的timeout而是另外设定一个timeout，保存当前上下文，等待响应。当收到响应的时候，对照当前上下文和响应的内容，决定如何往下走。当然由于是异步，上下文之类的必须是线程安全的。

实际代码中设计了几种状态，把上下文保存在状态中，分别处理超时和收到响应。有点像设计模式中的state模型。

• NoPing
• Ping
• ProxyPing

这样的话，当你在等待ping响应的时候，突然收到之前发送的proxy ping响应的时候就不会出现奇怪的问题了（理想的处理方式是什么都不做）。

上下文中比较重要的参数是pingAt，即开始一次失败检测的第一个ping的时间。这个时间需要在所有之后的响应和请求中传递和检查，避免UDP的乱序包，延迟包等的影响。

算法中有几个结束点

• 正常ping
• 没有ping响应，超时，没有间接ping的节点
• 间接ping成功
• 没有间接ping响应

xgossip在这几个结束点的时候，所做的事情是记录延迟，ping失败记录为-1。为什么记录延迟而不是记录失败的节点，原因是失败的节点可以从延迟记录中计算出来，其次是可以作为加权数据传播的参考依据。理论上gossip没有考虑两个节点之前的通讯延迟，所以对于由不同datacenter的节点组成的集群来说，两两之间的任意通讯可能会导致datacenter间大量的传输。一个优化措施是在选择数据传播对象时，优先选择同一个datacenter内的，然后再是不同的datacenter，这种加权选择的方式可用依据之一就是节点之间的延迟。当然如果你有足够信息，在节点加入时提供datacenter和rack之类信息的话，也是可以做加权选择的。

至此失败检测已经结束，接下来是如何处理。

对于可能下线的节点，最好不要向这个节点传播数据，因为不会有响应。所以可以用失败节点列表来做数据传播对象的黑名单。

其次，每个节点维护自己的失败节点列表的话，可能有时间差。为了减少这个时间差，检测到的失败的节点可以通过gossip协议传播给其他节点。

注意，xgossip中并不认为所有节点需要维护一致的失败节点的视图，原因是个人认为特定节点之间不安定的网络可能导致失败节点视图的频繁更新。这块其实值得商榷，但是有一点是确认的，不是增减服务器导致的集群成员的列表的变更不应该被频繁传播，所以xgossip里面失败节点的视图和集群成员列表是分开的，节点本身没有suspected的状态，只有某个节点检测到的suspected的节点列表。

基于上述原则，可疑节点列表的更新会在周期性的gossip集群成员交换时一起传给其他成员。可疑节点列表整体不会被传输，因为每个节点最终会得到所有其他节点的延迟。可以节点列表更新采用blind/count策略，一定次数后不再传播。其他节点在收到可疑列表的更新后，查询自己的延迟记录表，如果自己的记录中此节点正常的话，不做任何处理，否则作为下一次失败检测的对象。

同样的，从失败中恢复的节点，也依赖于失败检测。xgossip虽然在数据传播时会避开可疑节点，但是在失败检测时，会尝试所有非正常下线的节点和优先处理来自其他节点告知的可疑节点或者已恢复节点。因为处理恢复节点的逻辑类似，这块就不展开了。

最后，成员事件中的suspected和backed是通过延迟记录表中当前记录和之前记录比较得出来的

• 之前失败，现在成功>恢复
• 之前成功，现在失败>可疑
• 没有之前记录，现在失败>可疑
• 其他

使用延迟记录可以避免多次检测失败导致的重复通知。

以上就是xgossip中关于失败检测的内容。失败检测的算法之外，如何处理失败和传播视图是按照个人的理解设计的，可能和实际情况并不相符。如果那样的话，欢迎评论并给予建议，谢谢。