gossip 协议以及SWIM

gossip 协议

解决消息在分布式集群中的传递，保证数据在各个节点的一致性。这种场景的一个最大特点就是组成的网络的节点都是对等节点，是非结构化网络，或者说是去中心化的，期想法也就是来源于传染病的流行。所以也被称为流行病协议（Epidemic Protocol）。

问题描述

一个简化的模型（用户展示算法）

一个集群（P）由 N 个节点狗狗成，节点之间能够互相传递消息，消息可能传递失败或者丢失。
假设每一个节点存存在一个值value，当这个值发生变化的时候（产生一个Update），通过交换消息这个值是复制给所有的节点的。可能value会存在多个更新操作，所以每个更新（Update）会对应一个时间戳（可能是一个逻辑时间戳）。

算法的目标是通过传播更新操作，最终保证所有的节点会拥有一致的结果（相同的value值）。
一个节点可以处于以下三个状态

• Susceptible (S 未感染的): 节点不知道有跟新存在;
• Infected (I 感染的): 节点知晓更新，并且会传播这个更新;
• Removed (R 免疫的/移除的): 节点知晓这次跟新, 不过不会参与传播这个更新

分类算法

逆熵算法 （SI模型） （当集群中存在不一致的情况，努力改变这种不一致）

anti-entrpy

• 当前节点用节点p表示*

• 推模型
  以间隔时间执行， 随机选取节点 q，发送 push 消息，推送当前的 value 给节点q。节点q 收到消息之后比较时间搓，并更新当前的数据值value。

• 拉模型
  以间隔时间执行， 随机选取节点 q，发送 pull 消息（带上时间戳）给节点q。节点q 收到消息之后比较时间搓，如果自身的时间戳更大，则发送reply 消息返回节点自身的value 值。当p节点收到当前的value 值的时候则可以更新自己的value 值（需要比较时间戳）。

• 推拉模型
  结合推模型和拉模型，定时发送消息传递自身的value值给随机选取的节点q，如果q 节点value值的时间戳更大， 则返回reply 消息（类似拉模型），否则更新自己的value值。

推拉模型有最快的传播覆盖率，但是会付出更多的通讯成本。

• 广播消息 （SIR模型）

SI 模型中，消息轮询会永远运行，永远在保持集群中的节点一致。但是多数场景下更新是少量的，无限制的消息扩散大大提高了通讯的成本。以此为由SIR 模型被引入了，对比SI算法，节点多了一个 removed 状态。

SIR模型是基于推模型的（pull 模型也是可以的），当一个节点有更新发生时（第一个感染发生），其随机选取节点进行消息推送；未感染的节点收到消息之后变成了感染的节点，并且也开始传播（推送消息），最终在一个合适的时候所有的节点变成removed 状态。表示消息广播的过程的结束。和SI模型相比，SIR模型消息的传播是最终终止的。

其对应算法的关键点在于如何判断消息传播停止

主要的思路通过两个方面的因子确定停止传播的算法

• When
  • 每次消息推送之后（push 之后）即判断消息是否可以停止传递。
  • 每次消息传递之后通过对应节点的反馈消息确定是否需要停止传递。
• How
  • 通过消息传递的累计次数确定当前节点是否变为removed（免疫的）状态
  • 通过概率决定节点是否 （1/k）

两两组合可以实现免疫状态转换的算法。

SIR.jpg

现实中gossip 使用的情况

• SIR / SR 模型的结合，SIR 在一些极限的情况下会有消息无法覆盖的情况（消息发送失败，消息丢失）所以往往采用SIR 和 SR 模型结合的方法，即使消息传递的失败，SR 模型依然能保证集群状态的一致性，同时SR的触发频率可以大大降低，避免多国的SR模型的过多的通讯开销。

• 多值更新：每次push 所有的数据不可行，节点可以维护一个最近更新的update list，每次更新只传递最近更新的记录。（这个可以再了解一下）

• 容错
  小范围的节点故障依然能够保障集群的可用性。

gossip 协议的优势

• 可扩展性（Scalable）

gossip 协议是可扩展的，一般需要 O(logN) 轮就可以将信息传播到所有的节点，其中 N 代表节点的个数。每个节点仅发送固定数量的消息，并且与网络中节点数目无法。在数据传送的时候，节点并不会等待消息的 ack，所以消息传送失败也没有关系，因为可以通过其他节点将消息传递给之前传送失败的节点。系统可以轻松扩展到数百万个进程。

• 容错（Fault-tolerance）

网络中任何节点的重启或者宕机都不会影响 gossip 协议的运行。

• 健壮性（Robust）

gossip 协议是去中心化的协议，所以集群中的所有节点都是对等的，没有特殊的节点，所以任何节点出现问题都不会阻止其他节点继续发送消息。任何节点都可以随时加入或离开，而不会影响系统的整体服务质量（QOS）

gossip 协议与集群感知

SWIM: 可扩展成员协议（Scalable Weakly-consistent Infection-style Process Group Membership Protocol）

主要目的是解决维护一个集群列表

• 在新的节点加入和离开的时候通知各个集群节点
• 在集群中特定结点故障的时候感知并通知集群
• 去中心化，支持水平扩展

实现方式 -- 心跳（heartbeat）

• 判断特定的节点的存在状态
• 维护集群成员列表

image

每一个集群中的节点会随机的选取某一个节点N2，发送一个ping message，期望能够收到一个ack的返回消息。如果在一定的时候内没有收到ack消息，则会向另一个节点N3发送 一个 ping-req 消息，当第三个节点收到这个消息的时候会尝试ping N2 如果收到ack 也会给 N1 ack 消息。

如果ping-req 依然没有收到ack 消息，则可以将某个节点标示为 suspect （怀疑状态），并使用gossip 协议广播这个（N2 is suspected）消息，如果N2依然存活，则在节点中广播（走gossip 协议）自己状态是依然存活。否则一定时间之后，N2被N1 标记为死亡状态，并转广播这个消息（走gossip 协议）

gossip 消息的传递可以通过 ping 消息传递，可以节省通讯开销。但是由于ping消息发送的间隔无法过低，可能会有消息延时的情况。

consul 中的集群感知

完成集群感知的包是 serf

使用TCP 连接，定期全量地更新状态。gossip 协议只是用来传播变化的消息，这两者都是最终一致的。

serf 分离了gossip 层和，错误检测。这样的目的是gossip 的触发周期可以更频繁，而健康检测的频率会更低，（主要是因为通讯成本的问题）。

流程是这样的：

• 节点发送ping 消息，如果没有回应依照swim 算法会发送indirect ping ，请求另一个兄弟节点尝试再次ping消息，兄弟节点如果ping 失败之后会返回 nack 消息，这个消息会影响探测发起节点的awareness，这个逻辑是如果说自己ping另一个节点失败可能是自己的网络或者CPU负载较高，那这个时候就通过indirect ping去查询，如果没有收到nack 代表自己可能也会出问题了，这个时候就会提高下次的健康检查的超时时间（同时也降低自己健康检查的频率）
  。

• 动态的suspect 状态时常，动态的检测时常实现的逻辑是，当第一次发现suspect （可能是自己发现，也可能是别人发现）状态的时候，会使用一个较大的超时时间，下次每收到一个节点的suspect 广播就把suspect 的超时时间值调低。防止第一次自己误判断。

防止对于节点的误检测（Lifeguard）：

• 只是过高的CPU和 网络负载可能导致节点的假死，当一个探测的节点一致没有接收到 nack 消息，它会放慢自己错误探测的频率，直到下一个nack消息到来。

• 怀疑状态的超时时间的动态调整，开始会有一个很长的怀疑状态超时时间，当别的节点同时广播同一节点的怀疑消息的时候，这个怀疑状态超时时间就会缩短，防止仅仅因为网络隔离造成的节点死亡误判。

redis 中的集群感知

redis 中使用 gossip协议来感知集群成员，以及做健康检测。