序
本文主要研究一下 SWIM Protocol
SWIM Protocol
SWIM 的全称是 Scalable, Weakly-Consistent, Infection-Style, Processes Group Membership Protocol
heartbeats
传统的诸如 heartbeats 这种 membership protocols，每个 node 周期性地向网络中的所有其他节点发送 heartbeat 来表示自己是 alive 的，如果 peer 超过指定 interval 没有收到 node 的 heartbeart 则该 node 被认定为 dead。这种方式适用于小型网络，其发送的 heartbeart 数量为 O(n^2)，当网络中有成千上万的 node 时则会造成巨大的网络负担；SWIM 采用 Infection-Style dissemination 来解决这个问题
tasks
与传统的 heartbeats 相比，SWIM 将整个过程分为 Failure Detection 及 Membership update Dissemination 两个 task
Completeness 与 Accuracy
对于 failure detection 来，有几个衡量标准：
- Completeness
是否每个 failed node 最终都会被检测到
- Speed of failure detection
一个 node 从 failed 到被检测到 failed 的平均耗时
- Accuracy
false positive rate，即一个 node 被误判为 failed 的概率
- Message Load
在检测中每个 node 的 network load 是多少，是否均匀分布
Unreliable Failure Detectors for Reliable Distributed Systems 一文中指出对于异步的网络来说，100% 的 Completeness 与 Accuracy 无法同时保证，因而 SWIM 权衡之下选择了 Completeness，同时尽可能减少 false positive rate 以提升 Accuracy
Failure Detection
SWIM 的 failure detection 过程分为两个部分，一个是 direct ping，一个是 indirect ping
- direct ping
local node 从 alive nodes 中随机选择 N 个 node 来进行 detect；如果 direct ping 中有的 node 没有在 timeout 时间内返回 ack 则会进行 indirect ping
- indirect ping
local node 从 alive nodes 中随机选择 K 个 node 来对 direct ping 目标 node 进行 indetect ping，这 K 个 node 会把结果 forwards 给这个 local node，最后 local node 检查如果这个 K 个 node 没有一个返回 ack，则将该目标 node 标记为 failed，然后通过 Membership update Dissemination 将该 node 的 FAILED 信息传播到网络中的其他 node
Membership update Dissemination
Membership update Dissemination 可以将 messages 分为 JOINED、FAILED 两类：
- JOINED
当一个 node 加入到该网络时，需要通知其他 node 更新 local membership 新增该 node
- FAILED
当一个 node 被检测为 failed 时，需要通知其他 node 更新 local membership 移除该 node
这个过程可以使用 multicast 来实现
改进
- Infection-Style Dissemination
multicast 实现的 Dissemination 是不可靠的而且低效的，一个更加 robust 版本的 SWIM 采用 Infection-Style 的方式进行 dissemination，即利用 Failure Detection 的 ping 机制，将需要 dissemination 的消息 piggyback 在 ping/ack 上，来实现类似 gossip 的消息传播，从而减少额外的单独信息传递开销
- Suspicion Mechanism
为了更好地减少 false positive rate 以提升 Accuracy，可以引入 Suspicion Mechanism，即当 local node 检测到该 node failed 时将其标记为 suspected；被标记为 suspected 的 node 在最终被确认为 failed 之前被当做是 alive；其他 node 如果检测到该 node 是 alive 则对该 node 取消 suspected，恢复 alive；如果在指定时间该 node 没有被恢复为 alive 则被标记为 failed
- Time bound failure detection
随机选择 node 进行 ping 可能会造成一定的延时，可以使用 round robin 的方式来取代随机选择, 当所有 node 都选择过了之后再重新 shuffle 该 node list
小结
- SWIM 的全称是 Scalable, Weakly-Consistent, Infection-Style, Processes Group Membership Protocol；与传统的 heartbeats 相比，SWIM 将整个过程分为 Failure Detection 及 Membership update Dissemination 两个 task
- SWIM 的 failure detection 过程分为两个部分，一个是 direct ping，一个是 indirect ping
- Infection-Style 的方式进行 dissemination，即利用 Failure Detection 的 ping 机制，将需要 dissemination 的消息 piggyback 在 ping/ack 上，来实现类似 gossip 的消息传播，从而减少额外的单独信息传递开销
doc
- cornel edu SWIM.pdf
- SWIM Protocol explained
- THE SWIM MEMBERSHIP PROTOCOL
- Feel the Cloud with SWIM protocol
- random-probing based failure detector algorithm