SWIM: scalable weakly-consistent infection-style process group membership protocol

[gaocegege]

https://www.cs.cornell.edu/projects/Quicksilver/public_pdfs/SWIM.pdf

来源：https://github.com/caicloud/ftlib/

相关项目：

• https://github.com/hashicorp/memberlist
• https://github.com/hashicorp/nomad

[gaocegege]

SWIM 是一个做 Process Group Membership 的协议。在一个分布式环境里，可能有多个进程，或者说 Member。如何能够让他们之间互相知道所有其他的 Member 的状态（健康，失败），是 Process Group Membership 想解决的问题。也就是说，每个 Member 都会有维护一个其他健康的 Member 的列表，同时支持动态地增加/减少 Member。

这是一个分布式一致性的问题。依靠一个中心化的组件，是一定可以解决问题的。但如果要求去中心化，问题就会变得复杂一些。而 SWIM 就是去中心化的，可以横向扩展的，基于弱一致性的协议，它面向的场景就是 Process Group Membership。

就像分布式系统有 CAP 理论一样，做 Membership 也有类似的 tradeoff 需要考虑，它需要的考虑的方面主要包括：

• Strong Completeness：一个 Member 的失效会被所有的 Member 得知
• 失效检查的速度：从失效到被检查出失效的时间间隔
• 准确性：失效被误报（本没有失效，但被认为失效）的概率
• 网络请求的负载：协议单位时间内的网络通信（Bytes per second）

其中准确率 100% 和 Strong Completeness 是不可能同时达成的。一般 Membership 的协议，都会保证 Strong Completeness，所以会有一定的误报，SWIM 也不例外。

[gaocegege]

首先，在介绍这一个协议之前，先介绍一下这一协议的系统模型：

• Member 所在的网络可能会出现丢包的情况
• 无论是丢包，还是 Member 出现了其他的问题，都会导致这个 Member 变成失效的

这样的假设可以很好地应用在互联网（TCP UDP / IP）上。

基于这样的系统假设，先来看下最简单的实现。在最简单的实现中，每个 Member 可以利用 IP 广播等方式（对组网有要求），每次给所有的 Member 发心跳。如果想在 T 时间内完成对 n 个 Member 组成的 Group 的错误的检查（检查是否有 Member 失效），那么每秒需要的心跳数是 n^2/T。

这样的实现肯定是不能接受的，那么我们先不看（优化版的） SWIM 的实现，看看他能做到什么：

• 每个 Member 只需要常数大小的信息数
• 在常数时间内检测是否有 Member 失效
• 对于每个 Member 来说，检测其他 Member 失效是可以在确定的时间区间内完成
• Member 状态的更新延迟，随着 Member 数量增加，是 Log 的增长速度
• 通过增加新的状态 Suspecting，来避免过高的误报率
• 不需要 Member 之间做时钟同步

[gaocegege]

在最朴素的 SWIM 协议中，一共有两个组件，分别是 failure detector component 和 dissemination component。第一个组件用来感知失败，第二个组件用来传播状态改变的事件。

朴素 SWIM 的 failure detector 非常巧妙，不需要 member 之间的时钟同步。它引入了两个操作原语，ping 和 ping-req。每次每个 member M_i 会随机选择一个 Member M_j，先发 ping。如果 ping 失败，再随机选择 k 个 member，发 ping-req。member 收到 ping-req 后，会去 ping 之前的 M-j，如果成功，会把 ack 转发给 M_i。ping-req 基本杜绝了网络拥堵导致 M_i 到 M_j 因短时间内丢包导致 M_j 被踢出集群的可能。

朴素 SWIM 的 dissemination component 大部分时候只是简单的广播状态变更。但在新的 Member 加入时，需要得知一个已经在集群中的 Member 的地址来加入。这也是为什么 https://github.com/hashicorp/memberlist 在 member join 的时候需要知道起码一个已经在集群中的 Member 的 IP

[gaocegege]

基于朴素的 SWIM，有两个优化可以做。一个是除了 Succeeded 和 Failed 状态之外，引入一个新的中间状态，Suspected。这样可以尽量避免误报的概率。当 ping 失效时，就先标注成 Suspected。在度过一个 time interval 后，再标注成失败。

由于朴素的 SWIM 的实现依赖一个广播的操作，如果没有在 IP layer 的广播可用，就很难实现。所以这里就有一个优化，来避免用广播来实现 dissemination，就是标题中的，infection-style dissemination。状态的更新可以复用 ping, ping-req 等信息的包。这一点在文章 4.1 中有详细介绍。大致的实现是，每个 Member M_i 会维护一个最近的 Membership 更新事件的 Buffer，每个更新事件都会有一个计数器。计数器记录的是目前已经有多少次传播这个事件了。这一计数器会被用来确定下一个包发出去来夹带哪个事件。如果一个 ping/ping-req/ack 包夹带的事件数量小于 Buffer 中的事件数，就会用到计数器来做排序决定带哪些事件。

论文中对它的 probabilistic reliability 没有过多论证，不过文章说到，其他论文已经得到了类似的结论。

[gaocegege]

目前，SWIM 提到的所有特性里，还有一个没有被支持：

• 对于每个 Member 来说，检测其他 Member 失效是可以在确定的时间区间内完成

目前由于选择发 Ping 是随机的，所以可能出现某个 Member 的失效一直被忽略。这里就提到了最后一个优化（在文章 4.3 节）：Round-Robin Probe Target Selection。

没有什么噱头，就是不按照随机，而是 Round-Robin 去发 probe。不过每次在循环完一轮后，会进行重排序（没搞清楚为什么）

[gaocegege]

SWIM 是一个 Application Layer 的协议，文中是基于 UDP 来实现的