MyBlog

【Paper】SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol

last modified: 2021-01-31 01:02

Dynamo论文中引用了《On Scalable and Efficient Distributed Failure Detectors》这篇分布式系统中失败检测的论文，没有描述其实现细节。

SWIM论文也引用和参考了这篇论文，并提供了工程实现的细节，同时Uber Ringpop项目有对其完整实现。

一、Protocol

SWIM是通过Gossip实现的Membership保持协议，也就是维护分布式系统节点的状态。Notes中，将每个Member称为一个Node.

二、Component

SWIM由2个模块构成，分别是： 1. Failure Detector 模块，用于Node失败检测 2. Dissemination 模块，用于将Node主动加入、退出或失败的信息传播出去

2.1 Failure Detector

概念：

  • T’: 协议周期，2次探测的时间间隔
  • k: k个节点

该协议中，若Mi检测Mj状态，则先发一个ping包到Mj，若Mj未在超时时间内ack，则Mi随机选择k个节点，发送间接探测ping-req包，k个节点如Mh收到ping-req请求，将会ping Mj并将结果返回给Mi。若任意一个ping-req返回Mj存活，则Mj存活。

上述过程，包含3个round-trip的网络过程，Mi->Mj, Mi->Mh, Mh->Mj，所以T’ 要大于3个超时；如T’=1s, timeout=200ms

Figure 1

2.2 Dissemination and Dynamic Membership

当Mi检测到Mj失败，会利用IP多播等方式，发送一条 failed(Mj) 的消息，收到消息的Node，会把Mj从本地Node表中踢除。

SWIM实现中，有更优的方式进行消息传播，下面介绍。

三、A More Robust and Efficient SWIM

3.1 Suspicion Mechanism: Reducing the Frequency of False Positive

有些Node，可能临时掉线，如果检测到其失败直接踢掉，会导致很重的数据搬移操作。因此SWIM设计了一种方式，称为Suspicion机制。

现在节点有3种状态，Alive，Suspected, Faulty

当Mi检测到Mj失败时，不直接将其标记为Faulty，而是传播一条Suspected消息，Suspected状态的节点依然被认为存活。当超过一个指定的timeout后，才最终转为Faulty状态，从集群踢除。这是一种在”失败发现速度”与”False positive”错误检测之间的trade-off。

当Mi节点下一个协议周期又探测到Mj存活，则会传播一条 alive(Mj) 的消息，alive会覆盖suspected消息。Mj收到自己被suspected的消息也会主动发送一条alive消息。

当处于Suspected的节点超过一定时间，会被标记成Faulty，发送 confirm(Mj faulty) 消息，Confirm消息会覆盖Suspect和Alive消息。

设想一下，Mj的生命周期内，会存在不断的Suspect和UnSuspect的消息，如何区分先后顺序呢？SWIM使用了一个虚拟incarnation number.

Mj的incarnation number是全局的，在加入集群后初始化为0. 它只能被Mj节点自己修改，当他收到自己被Suspect的消息，会将number+1并发送一条Alive消息。

Suspect, Alive, Confirm之间覆盖关系：

{Alive Ml, inc=i} overrides
    - {Suspect Ml, inc=j}, i>j
    - {Alive Ml, inc=j}, i>j
{Suspect Ml, inc=i} overrides
    - {Suspect Ml, inc=j}, i>j
    - {Alive Ml, inc=j}, i>=j
{Confirm Ml, inc=i} overrides
    - {Alive Ml, inc=j}, any j
    - {Suspect Ml, inc=j}, any j

3.2 Infection-Style Dissemination Component

SWIM描述了一种 Piggybacking 的机制，要传播的节点加入退出、失败等信息，不使用单独的消息和广播，而是直接附加到ping, ping-req, ack3种请求消息之上进行传播。

这样系统中只存在这3种消息，降低了复杂度和网络负载。

3.3 Round-Robin Probe Target Selection: Providing Time-Bounded Strong Completeness

Failure Detection协议的一个基本要求是Completeness：节点A的失败能被任意一个其它节点检测到。关键是检测时间要有界。

SWIM提供了一种轮询的检测方式，Node A将本地Membership的节点做shuffle，每个协议周期遍历发送ping探测包，期间新加入的节点，在当前检测节点之前随机插入。这样保证最坏情况下，2N-1个协议周期成所有节点检测。

检测完成后，重新shuffle，重复此过程。