分布式系统之故障检测设计

分布式系统 - 故障检测设计

Multicast

在一个集群中向多个节点发送消息称为 Multicast。（向所有节点发送消息称为 Broadcast）

要做到向集群中指定的多个节点的发送消息，有以下几种方式：

Centralized Multicast ：

向一个中央节点发送消息，再由它发向指定的多个节点。这种方式会造成中央节点的负载较大；

Tree-Based Multicast：

整个集群由多个树形的节点群构成，将消息发送到节点的根节点。这种方式的负载均衡，但因为复杂程度使可扩展性受损。

Gossip/”Epidemic” Multicast：

使用 Gossip 的方式发送信息：在每个时间间隔，向一个随机的节点发送消息，收到消息的节点亦随机发出消息，数学证明，消息会在 clog(n) 轮时间间隔后抵达所有节点，n 代表时间间隔轮数。

故障检测

故障检测是指发现集群中不能正常工作的节点的能力，它由两个属性：

1. 完整性：确保集群中任一出现故障的节点都能检测到；
2. 准确性：没有故障误报。

在可能有损的介质中传递消息时，以上两点只能保证其中一点，一般选择保证完整性。

心跳

通过心跳消息实现故障检测机制：节点定时向其他节点发送心跳信息，标明自己运行正常，当其他节点在一定时间内未收到心跳信息，证明该节点出现故障。

心跳的形式为一个自增的数。

Centralized Heartbeating:

一个中央节点负责接受所有心跳信息。

Ring Heartbeating:

环状拓扑的节点沿着环发送心跳信息。

All-To-All Heartbeating:

所有节点互相发送信息。

Gossip-Style Heartbeating:

使用 Gossip Multicast 的方式进行 All-To-All Heartbeating。

Gossip-Style Heartbeating 可以保持负载均衡并且保证故障检测的完全完整性。

MemberList

MemberList 是 All-To-All Heartbeating 的自然延申，既然所有节点以 Gossip 的形式互相发送心跳信息，那么就需要在本地进行心跳信息的汇总维护。

在节点维护的 MemberList，其中记录有集群中所有节点的心跳情况，并且对每个节点进行计时，超时而未收到心跳信息的节点被判定未故障节点。

MemberList 表的类型

1. 完整的表（强一致）

   MemberList 中维护了所有节点的运行信息。

2. 几乎完整的表（弱一致）

   MemberList 中维护了几乎所有节点的运行信息。由于采用的 Gossip Multicast 协议的限制，不能保证绝对的所有节点，但已经很接近，并且有速度的优势。

MemberList 表的设计

| ------------- | ------------- | ---------------- |
|    node id    |   heartbeat   | last update time |
| ------------- | ------------- | ---------------- |

三种场景

节点加入

当一个新节点加入时，会向集群中的一个节点发送加入消息，此时该节点要向新加入节点发送其 MemberList。

节点故障

在每个节点上设置一个节点故障检测超时时钟 T，当 MemberList 中某个节点超时时还未更新，则将其标记为待删除，在 T 时间间隔内，收到心跳消息时忽略表中标记为删除的节点，再经过 T 事件后，将其从 MemberList 中删除。

节点心跳

每个节点按照一定的时间间隔，以 Gossip-Style 的形式，随机在 MemberList 中选取一个节点发送自己的 MemberList，收到的节点将 heartbeat 比自己高的条目合并进自己的 MemberList。