乐趣区

聊聊SWIM-Protocol

本文主要研究一下 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
退出移动版