SWIM：弱一致性感染式进程组成员协议

概要

几个分布式p2p应用，在所有的参与过程中，需要进程组成员信息的弱一致性。SWM是一个泛用的软件模块它为大规模的进程组而服务。SWIN努力是传统协议心跳协议的不可扩展性，它们要么施加网络负载，使其与群体规模成二次增长，或者在进程检测程序崩溃时牺牲响应时间或者误报率。这篇论文报告了设计和实现以及SWIM子系统在大规模通用pc集群下的性能。

不同于传统的心跳协议，SWIM分离了成员协议故障探测和成员更新维度功能。通过有效的点对点随机探测协议进行监控。每个进程的失败时间和预期时间，以及每个成员的预期消息负载，不会随着组的规模而变化。成员的改变信息，比如进程假如，推出和故障，通过ping消息和确认来进行传播。这导致了一种健壮而又快速的感染方式（也称为传染病或者gossip风格）。

通过修改协议，可以降低SWIM系统中的误检率，允许组成员宣布流程失败之前对其进行怀疑-这允许系统发现并纠正错误的失败检测。最后协议保证了确定性的事件限制来探测故障。

给出了SWIM原型机的实验结果。我们讨论该设计向广域网扩展的可能性。

1 介绍

几个大规模的p2p分布式进程组运行在internet上依赖于分布式成员维护系统。利用成员协议中现有的中间件系统的例子包括可靠的多播，传染病风格的协议传播。这些以协议又被用于分布式数据库等需要协调最近断开连接更新程序的应用中。发布订阅信息，以及大规模的p2p系统。关键应用比如交互式游戏和其他写作分布式应用的性能，严重依赖于成员维护协议在其中使用的可扩展性和可靠性。

简而言之，成员协议为每个进程（“成员”）提供一个本地维护的其他非故障进程的列表。协议确保新成员列表加入或移除组（自愿或者失败）发生更新更改而更新。成员列表可以直接在应用程序的地址空间中或者回调接口或者api提供。应用程序可以根据需要自由使用列表中的内容，基于gossip传播协议将使用该列表定期挑选八卦的目标成员。

成员子系统的可靠性和扩展性可以通过几个性能指标进行衡量。在成员发生变更后，必须在组内进行迅速传播。底层网络的异步性和不可靠性可能导致消息丢失。因为消息丢失的进程与消息与进程的失败的进程无法区分。误报率必须很低。最后，协议需要p2p(不依赖中心化服务)，并且对网络和进程施加较低的消息和负载。

"Virtually synchronous multicast protocols"（虚拟同步多播协议）是一类在分布式系统中用于多播通信的协议。它们确保所有成员在逻辑上按顺序接收到相同的消息，即使在物理层面上可能存在延迟或部分成员因故障无法立即收到消息。

成员协议很难在超过几十个进程的组中扩展，从而影响它们的应用程序性能。在这些的组规模下，性能不加的主要症状是错误故障率的增加，或者探测故障的时间。将这种成员关系协议带来的消息的二次增长作为传统成员关系协议不可扩展性的一个症状。严重依赖于成员子系统应用程序的一个示例是虚拟同步多播协议类。在超过几十个成员时，这个规范的传统实现在性能和分区上上有很大的降低。

我们的论文提出了我们在SWIM项目中所做的工作，实现了一个成员子系统已提供稳定故障检测时间的成员子系统稳定的误报率和每个组成员的低负载，因此允许分布式应用可以很好的扩展。我们关注的是组成员关系的一个较弱的变体，不同成员的组成员关系列表不需要在同一（因果）时间点上保持统一。通过增加成员子系统来提供强有力的保证，例如：可以通过定期检查点成员列表的序列器进程提供虚拟同步风格的成员关系。然而与弱一致性问题不同，强一致性规范可能具有基本的可伸缩限制。

分布式成员关系算法的设计传统上是通过心跳技术来实现的。每个进程定期向外界发送一个增量心跳计数器。如果在一段时间内没有收到另一个进程的心跳，则检测到该进程失败。然而真实的心跳受到可扩展性的限制。将所有心跳发送到中心服务器将都是自热点创建。发送心跳到所有的成员（通过网络广播多播或者gossip）会导致网络和组上的消息负载随着组大小呈二次增长。不幸的是随着组规模的增加，同时出现多个失败者的可能性也在增加。

关于基于心跳的成员维护机制固有的不可伸缩性背后的原因的扩展讨论可以在[12]中找到。本文还提出了一种基于分布式成员之间的随机探测而不是心跳的随机分布式故障件检测协议。数学表明，随着群体的扩大，协议的（预期的）故障检测时间、误报率和每个成员的消息负载等属性都与组大小无关。这是对all-to-all基于心跳协议的改进，这些协议具有（随组大小）现行变化的故障检测时间或每个成员的网络带宽使用（误报率的增加）。我们在本文的工作受到（[12] On scalable and efficient distributed failure detectors）的启发。流行的全队全心跳协议不可扩性源于其中的俩个隐含决定，即融合成员问题规范的俩个主要功能1：成员更新广播：传播因加入、退出或失败过程产生的成员更新2：故障探测：检测现有成员的故障。通过设计高效的非组播故障检测器，并且仅在成员发生变化时使用传播组件，消除了多播心跳的开销。成员分发组件可以通过硬件多播或感染方式实现。

其中12提出了新的故障探测机制并且对它进行了分析，我们的工作在当前的论文着眼于将成员关系传播组件纳入构建一个成员关系子系统。此外生产的协议通过降低误报率的机制得到增强，并在单个进程的故障检测上提供更强的确定性保证。

我们的系统叫做SWIM，提供了成员关系基础：

1. 对每个组成员施加恒定的消息负载
2. 在（预期的）恒定时间内检测组中某些无故障进程的进程故障；
3. 提供一个本地的时间确定的边界（作为组大小的函数）该本地时间是非故障进程检测另一个进程故障所需时间
4. 广播成员更新，包括故障信息，在传染病形（也称为八卦形或者流行病）；群体中的传播延迟随着成员数量的增加而缓慢的增长；
5. 提供一个机制，通过在组内声明流程失败之前怀疑流程来降低误报率。其

中 1和2是故障探测协议的特性，3-5是我们在这篇论文中随后的工作。讨论了在PC集群上运行SWIM原型实现的实验结果。SWIM协议还可以扩展到在广域网（WAN）或虚拟专用网上工作，我们在第六章中简要的讨论这一点。

本文的其余部分组织如下。第2节总结了该领域以前的工作，以及[12]可扩展故障检测协议的基础知识。第3节介绍了基本的SWIM协议，第4节介绍了对协议的改进。第5节介绍了原型实现的实验结果。我们在第6节下结论。

2 之前的工作

在传统的分布式 all-to-all心跳故障探测算法中，所有的组成员定期发送心跳信息（伴随一个自增的计数器）到所有的其他组成员。通过没有故障的成员成员$M_j$，当它在连续的心跳周期时接受不到来自$M_i$的心跳,$M_i$被宣布故障。

分布式的心跳模式保证了，故障成员总是在任何非故障成员（在其故障检测的最后一段时间内）被检测到，因为成员的停止也会发送心跳新信息。然而这些协议的准确性和可伸缩性是不同的，取决于用于心跳的实际机制。

在最简单的实现中，每个心跳多次广播给所有的其他组成员。这导致了$\theta(\frac{n^2}{T})$信息的网络负载每分钟（即便使用IP多播），其中T是分布式系统中故障探测的事件需求。van Renesse等人提出心跳可以通过稳健的gossip协议进行传播。在这个协议中每个$t_{gossip}$时间单元，每个成员都随机对目标进行gossip，从其他成员收到最新的已知心跳计数器的$\theta(n)$个大小的列表。其中gossip减少了误报率，根据预期，新的心跳计数器通常需要$\theta[log(n)\times t_{gossip}]$的时间单元来到达任意的其他组节点。为了满足应用的监测时间，协议生成$\theta(\frac{n^2\times log(n)}{t_{gossip}})$字节每秒。使用消息批处理来解决这个问题受到udp数据包大小的限制，例如50个成员的5B心跳（IP地址和计数，已经占用了250B，而SWIM生层的数据包最多有135B大小，无论组的大小如何）。
网络负载平方的增加这个结果来自心跳通知给所有组成员。这可以通过故障检测工作与成员更新分发操作来避免。

几个分层的成员系统已经被提出了，即Congress。这属于一个更广泛解决方案的类别。这类协议需要仔细配置维护和维护成员信息流的覆盖层，协议的准确性依赖于图的鲁棒性。相比之下，SWIM的设计避免了虚拟图的开销。

SWIM对于上述不可扩展性问题的解决方案基于（a）分别设计检测和成员更新广播组件（b）使用不基于心跳的故障探测策略。

在继续描述SWIM协议内部的结构之前，我们首先理解分布式故障检测协议的效率和可伸缩性的关键特征奠定基础。一些研究[6,7,12,16]已经导致了分布式故障检测器协议的这些基本特性的识别。以及同时满足它们相关的不可能结果最终的权衡通常取决于分布式系统所需的安全性和活动性。

这些特性是：

1. 强完备性：任何组成员的崩溃故障都会被所有非故障成员检测到
2. 快速故障探测：从某个成员故障到某个非故障组成员检测到该成员故障之间的时间间隔
3. 准确性：故障检测的误报率。
4. 网络信息的负载，协议每秒生成的字节数

构建一个故障探测在异步的网络已经被证明是不可能的[6]。然而，由于典型的分布式应用依赖于强完整性保持始终（为了在动态数组中保持最新信息），大多数故障检测器（包括基于心跳的解决方案试图保持低误报率的同时保证这一属性）。

在[12]中，一个简单的计算确定了满足每个成员误检率的指定参数所需的最小总网络负载（记作$\mathcal{PM(T)}$）,并探测时间T在大小为n的组中。计算这个负载为$n\times\frac{log\mathcal{PM(T)}}{log(p_{ml})}$其中${P_{ml}}$是底层网络中的丢包率。

虽然这个计算是在每个消息$(p_{ml})$独立丢失概率的理想条件下完成的，它可以作为比较不同故障协议的可伸缩性的良好极限。例如，all-to-all的心跳协议会在第二章中讨论，其次优性因子随组的大小变化线性变化。

3 基础的SWIM方法

如前所属，SWIM方法有俩个组件

1. 故障探测组件，它探测成员的故障
2. 传播组件，它会传播有关加入或者离开组织或失败的其他成员的消息。现在我们通过描述基本的SWIM来奠定基础。基本协议基于随机探测的故障检测协议[12]（3.1章）并通过网络多播成员更新。在接下来的部分（第4节），将通过改进这个初始设计来开发SWIM协议

3.1 SWIM故障探测

SWIM故障探测算法使用了俩个参数：协议周期T'（在事件单位中）和整数k，故障探测的子组。这个协议不需要始终来进行跨成员同步，如果T'是小组成员的平均协议周期，协议的资源保持不变。

图1，SWIM 故障探测：在周期为$M_i$的例子。这显示了协议周期可能初始化的所有可能的消息。为了简单起见一些内容被排除了。

图1展示了在任意的成员$M_i$的工作。在每个长度为T'时间单位的协议周期($M_i$的本地时钟)$M_i$的成员列表中随机成员被选中，被发送ping消息。$M_i$然后等待回复从$M_j$的ack。如果在预先指定的超时时间内未收到此消息（由消息的往返时间确定，它被选为小于协议周期），$M_i$间接探查$M_j$。$M_i$选择k个成员，并且给每个人发送ping-req($M_j$)信息。在收到此消息时，每个成员依次ping$M_j$并且转发从$M_j$返回的响应(如果收到了)返回给$M_i$。在协议周期的结束，$M_i$检查，如果它接收到了任何的ack，直接来自$M_j$或者间接来自k个成员中之一。如果没有的话，它宣布$M_j$作为故障在它的本地成员关系表中并且把最新消息广播给传播组件。

在图1的例子中，k个成员中的一个没法完成这个事件循环，在协议的周期结束时，$M_i$不会认为$M_j$作为一个故障节点。

用于启动间接探测的余弦指定的超时是基于对网络内返回时间的估计，即能够被99百分位所用。记住协议周期T’只少是往返周期的三倍。在我们的经验中，我们用平均往返时间来设置超时，并且我们平均往返时间显著大于这个值。

协议的每条消息中包含的数据在发起者处被标记为协议周期唯一的序号($M_i$)。注意ping，ping-req，ack消息大小是被常量锁限定的，与群体的规模无关。

上述协议的第二部分使用成员的间接探测子组来中继ping和ack。使用整个方法，而不是直接发送k个ping到$M_i$，或者直接将中继返回的ack直接到$M_i$的根本原因，是为了避免任何在$M_i和M_j$之间拥塞对网络路径的影响，这可能会导致ping信息丢失或其返回的丢失。

故障探测协议已经在[12]中进行分析了，我们概要这个分析的结果。

• 如果每个成员有大小为n的成员关系列表，并且其中$q_f$是无故障的，在协议周期内选任意成员作为ping目标的可能性是$1-(1-\frac{1}{n}\times q_f)^{n-1}$它快速下降到$1-e^{-q_f}$(并且渐渐的n趋向于无穷)
• 因此，组中任意成员发生故障与被某个进程检测到故障之间的预期时间最多为$T'\times\frac{1}{1-e^{-q_f}}$。这根据应用程序指定的预期时间给出了协议周期长度的估计
• 如果$q_{ml}$是网络即时传输数据包的概率，独立于所有的数据包，任意一个协议周期，其概率为$q_f\times (1-q^2_{ml})\times (1-q_f\times q^4_{ml})^k\times \frac{e^qf}{e^{q_f}-1}$
• 根据应用程序所需的误报率，这里给出了一个可配置的值k
• 该故障检测器满足强完备性：该故障检测器满足强完备性：一个错误的成员最终会被选择ping目标每个非故障成员，并从成员列表中被删除。
• 协议施加的每个组成员的预期消息负载是一个常量，不随组大小而变化，并且在所有成员之间是对称的。这个负载可以被从k中进行计算。
• 这些属性都不依赖于组大小n（除了渐进情况外）

3.2传播组件和动态成员

一旦探测到了另一个组成员的异常，进程简单的多播failed($M_j$)消息到组中的其他。一个成员接受这个信息，从本地的成员列表中删除$M_j$。

关于新加入成员或自愿离开成员的信息以类似的方式进行多播。然而，为了进程加入组，它至少需要知道组中一个联系人的成员。这可以通过以下几种方式之一来实现：如果组与已知的服务器或IP多播丢只相关联，所有的加入可以直接定向到关联的地址。在没有这样基础设施的情况下，可以广播加入消息，并且听到消息的组成员可能会做出决定（通过跑硬币）是否回复。或者，为了避免多个成员回复，为了处理组连接请求，可以在租内维护静态协调器。事实上多个协调器的存在并不影响协议的准确性，并且只导致对连接请求的多个响应。随着时间的推移，可以通过传播组件发现和解决多个协调器。在当前版本的SWIM中我们选择维护协调器，尽管没有任何理由排除其他策略。

4 更健壮和有效SWIM

章节3描述了基本的SWIM协议，它广播成员关系更新（由成员的加入立刻引起的）使用网络多播。然而网络多播原理比如IP组播等，是尽力而为，在网络中的消息丢失会导致任意组的成员变更未收到。在4.1章中我们描述了广播组件的设计，它承载了成员资格更新在被故障探测协议发送的ping和ack消息上。这完全消除了由传播组件（即组播）产生的额外数据包。唯一由SWIM生成的数据包是ping，ping-req和ack，因此为每个成员提供一个恒定的预期消息。这个方法产生了一种感染式的传播，并具有对丢包的鲁棒性和低延迟的好处。

基础的SWIM故障探测协议，尽管具有可能性的准确性，它受制于进程的缓慢（即 缓冲区溢出导致的大量包丢失）将其他几个非故障过程声明为故障。也有可能一个进程在一小段时间内受到干扰，即在主机过载的时候。咋可能会导致进程错过同时收到ping发送及时回复的机会，并且被错误的宣称失败。章节2介绍了猜疑机制，其中进程对ping消息反应迟钝，由章节3中描述的SWIM故障检测器，并不立马宣布故障。相反，进程宣布可以，使用传播组件在组件中传播此消息。在预先制定的超时之后（我们讨论参数值在章节5中），被怀疑的过程被宣布为错误，并且将这一信息传播给组。然而，如果可以的进程回应了ping消息在超时之前，这个信息作为活的广播给组。然后在不同成员的成员列表中重新激活该过程，而无需离开或重新加入该组。因此，这种预先制定的超时有效牺牲了故障检测时间的增加，从而减少了错误故障检测的频率。

基础的SWIM故障探测协议保证了，在每个非故障组成员$M_j$任意进程$M_i$的故障会最终被探测，然而，他没有给出在任意成员$M_i$的故障和他探测另一个任意的成员$M_j$(根据本地协议在$M_j$中轮训的次数)确定性的时间保证。第4.3节描述了对原始SWIM故障检测器协议的修改，该协议保证了这种时间有界完整性属性。成员$M_j$在发生故障和探测到故障不超过组数量的俩倍（协议周期的数量）。

4.1 传染病风格的传播组件

基础的第三章SWIM协议传播成员关系更新使用组播源于在成员中传播。硬件组播和IP组播在大部分网络和操作系统上是有用的，但是很少启用，比如因为管理原因。基础的SWIM协议不得不使用昂贵的广播，或者低效的点对点消息模式，以便向所有小组成员广播成员资格更新。此外，由于多播是不可靠的，成员关系的变化只能尽最大努力的基础上传播到组中。

相反SWIM协议消除了额外的组播元语的使用。它通过承载在故障协议生成的ping、pung-req、和ack消息上传播的信息来实现这一点。我们称之为感染式传播机制，因为信息会类似于社会八卦或者传染病的的方式在一般群众传播，注意，这个传播的组件的实现不会产生任何额外的数据包（比如多播）- 传递给该组件的所有消息都是通过搭载故障检测组件的数据包来传播的。Bailey提出了一个流行病在具有一个初始感染成员的均匀混合群体中传播确定性分析。感染成员（预期）数量之间的关系x（最初为1）时间t，在每个时间单位下接触率为$\beta$,为

$$ \frac{dx}{dt}=\beta\cdot x\cdot (n-x)\implies x=\frac{n}{1+(n-1)e^{-\beta nt}} $$

在传染病风格的传播组件中，可以通过类似的方式分析通过ping和ack消息传播的成员更新。将协议视为周期时间单位，接触率$\beta$是一堆受感染的成员和未感染的成员之间接触的概率，并且等于$[1-(1-\frac{1}{n}^2)]=(\frac{2}{n}-\frac{1}{n^2})$这给了我们$x=\frac{n}{1+(n-1)e^{-2(2-\frac{1}{n})^t}}$。

这里的lambda是一个常量

这种流行过程在群体中呈指数级快速传播；在$t=\lambda$。协议的logn轮，其中$\lambda$是参数，受感染成员的预期数量是$
x = frac{n}{1 + (n-1)n^{-left(2 - frac{1}{n}right)lambda}} geq n cdot left(1 - frac{1}{n^{left(2 - frac{1}{n}right)lambda - 1}}right)
$。因此在$lambda$之后通过承载以感染方式传播的成员更新达到$(n-n^{-((2-frac{1}{n})lambda-2)})$组成员。为了简化，随着n的增加（并且趋向于无穷），对于x的估计趋向于$n-n^{-(2lambda-2)}$。设置$lambda$为一个小的常数足以可靠性地传播流行病-即使在较小的群体规模下也是如此，我们在第5张的实验中证明了这一点。

文献中还包括了对其他几种流行病的分析[4, 8, 13]，它们概率可靠性结论基本类似。这些分析也展示了感染病风格的传播是可靠的，能处理网络中的故障和信息丢失。就像传染病的感染性一样。我们的实现的实验结果也展示了这一点。

有必要对执行情况说几句。在每个组成员$M_i$的SWIM协议层维护一个最近更新成员的缓冲，以及每个缓冲区的元素的本地计数。元素到目前为止被$M_i$承载的次数在本地被特别的制定。它被用来选择要装在的元素。每个元素最多被搭载$\lambda$logn次，如果缓冲区的大小大于单个ping消息可以承载的最大元素数（或者ack），被八卦次数更少的元素更受青睐。这是必要的，因为协议的周期是固定的，成员的变更速度可能暂时超过传播速度。在这种情况下，首选更年期的缓冲元素可以确保所有的成员关系的更改至少感染几个成员 - 当成员变更时注入速率停止，这个更改将传播到组其他成员。

我们对于这个协议的实现维护俩个组成员略表 - 尚未在组中声明为失败的成员列表。第二份名单是最近失败的成员。目前，从这两个列表中选择相同数量的元素缓冲区进行承载，但该方案可以推广到适应过程加入率、离开率和故障率的相对变化。

4.2 特殊的机制：减少误报的频率

在之前描述的SWIM故障探测协议中，如果非故障组成员$M_j$是（错误的）探测了故障的成员，通过其他的组成员$M_i$,要么是因为由于网络丢包，要么是因为$M_j$睡了一会，或者因为$M_j$缓慢的处理，那么$M_j$就会在组中被宣布失败。换句话说，一个完全健康的机制$M_j$收到了很重的惩罚，当它在组中被错误检测为失败时，就会被强制退出组。这导致检测故障误报率很高。

我们通过重新定义SWIM以运行子协议来减少这个问题的影响，叫做怀疑子协议，当故障被基础的SWIM故障探测起检测到时，运行称之为猜疑的子协议。

猜疑子协议工作如下。考虑一个成员$M_i$它选择成员$M_j$做为ping的目标在当前的协议周期中，并且运行基础的SWIM故障探测协议周期。如果$M_i$没有收到直接或者间接的子组确认，它不声明$M_j$故障。相反，$M_i$将$M_j$标记为可疑成员在$M_i$本地的成员关系列表中。此外，一个$\{Suspect M_j:M_i\ suspects\ m_j\}$信息通过传播组件在组内传播(在我们的系统中的传染病模式)。任何组成员$M_l$收到这样的消息也标记$M_j$为可疑的。可以的成员保留在成员列表中，并且在SWIM故障检测器协议的ping目标选择操作方面与非故障成员类似。

如果成员$M_l$成功的ping到了可疑的成员$M_j$在适当的基础SWIM协议过程中，它取消标记之前可疑的在它成员列表中的$M_i$，然后通过广播组件（在我们的系统以感染的方式）在组内散播$\{Alive\ M_j:M_l\ knows\ M_j\ is\ alive\}$消息。这样的alve消息取消标记在$M_j$中的可疑成员。请注意，如果成员$M_j$接收到这样的怀疑消息，它可以开始广播一个Alive消息澄清自己没有故障。

成员关系列表中的可疑条目在指定超时过期。如果$M_j$在一些成员$M_h$中被怀疑，并且此条目在收到Alive消息之前消失，$M_h$选出$M_j$是故障的，从本地的成员列表中丢弃它，并且通过广播组件来传播信息$\{ Confirm\ M_j:M_h\ declares\ M_j\ as\ faulty\}$，这个消息覆盖任何先前的可疑或者Alive的消息，并且级联的从所有收件人的成员列表中删除$M_j$。

这个机制减少了（而不是消除）故障探测的误报率。要注意的是协议的强完备性保持不变。怀疑进程失败$M_j$的故障可能会延长探测时间，但是最终探测可以被保证。

在上述讨论中，Alive消息重写suspect信息，并且confirm消息重写可以和alive信息，在它们的作用下，局部成员列表中的元素对应于疑似成员$M_j$。然而一个成员在生命周期内可能被怀疑和未怀疑多次。多个版本的suspect和Alive信息（都属于同一个成员$M_j$）需要通过唯一标识进行区分。这些标识是通过对成员列表中每个元素使用虚拟化自身编号字段来提供的。自增字段是全局的。当加入组时，一个成员$M_i$的编号从0开始初始化，当它接收到消息（通过广播组件）关于它自己在当前花生中被怀疑才会自增 - $M_i$然后生成具有其标识符和递增的化身号的Alive消息通过消息广播组件传播到其他的组。

因此Suspect，Alive和Confirm消息包含成员的自增序号，除了它的标识符。这些消息优先级顺序对成员列表的影响如下所示

很容易看出执行的顺序和重写维护了孤航检测器组件需要的准确性。熟悉adhoc路由协议（如AODV[5]）的读者会注意到它们对目的地序列号的使用与我们的化身编号方案之间的相似性。

偏好规则和感染性传播的广播组件也通过多播给其他进程提供了进程合适的怀疑。偏好的规则不取决于怀疑的来源，如果有多个来源，感染式传播会更快地传播信息（怀疑、活着或确认），每个进程的开销与单个传染源的开销完全相同。

4.2 轮询探测目标选择：提供有限时间的强完备性

基础的SWIM故障探测协议在章节3中描述，在平均的协议周期内检测故障。尽管保证每个进程的故障最终在每个其他无故障的进程中被检测到（最终的强完整性），但是病态的在整个组中对ping目标的选择可能会导致首次探测组中任何位置的故障出现很大的延迟。在极端情况下，这个延迟可能是无限的，因为失败的进程可能永远不会被故障进程选择为ping目标。

这个可以通过对协议进行以下的修改来解决。成员$M_i$工作节点的故障探测协议，维护当前列表中已知元素的列表（直观来说是数组），并不使用随机的方式从列表中选择ping的目标，而是使用轮询的方式。相反新加入的成员插入到成员列表中随机选择的位置。完成整个列表的遍历，$M_i$将成员列表随机排列为随机重新顺序。

考虑SWIM协议的执行，在成员$M_i$经过上述的修改之后。一旦其他的成员$M_j$包括$M_j$成员关系列表，在遍历$M_i$的成员列表时，它只会被选中一次作为目标。如果成员列表的没有超过$n_i$,连续选择同意目标的次数最多$2\times n_i-1$。这限制了最差的情况下通过$M_i$任何成员探测进程失败的次数，因此满足时间有界完备性。

这个优化保留了原有协议的平均故障检测时间，由于整个组中不同成员的成员列表随机化导致每个成员ping目标选择分布相似。

5 执行协议评估

SWIM协议的实现在个Winsock 2 API，并在一大批运行Windows 2000的普通电脑上进行测试。PC集群包含16450兆的戴尔PII，16台1ghz IBM x220以及一组双节点和四节点（200 mhz至500 mhz的PII和PIII处理器），在没有外部负载的情况下，通过100mbps以太网进行通信。每个节点最多包含一个进程组成员。

实验参数设置如下。对于ping-req的选择的成员数量K=1，使用的协议周期为2秒。每次感染（成员更新）最多附带$3[log(N+1)]$个消息被发送到每个成员。有了这个值的设置，我们的实验运行中未观察到成员处存在永久性的部分成员列表或群组的非自愿分区的迹象。要声明失败的可以成员的怀疑超时也设置为此值。

我们比较了三种不同版本的协议：(1)（SWIM:Basic）第3节的基本SWIM协议，使用第4.3节中描述的Round-Robin方案进行修改。(2)(SWIM+正。)带有感染型传播组件的SWIM（如第4.1节所述），以及(3)(SWIM+正+ Susp)。游泳+正无穷。使用第4.2节中描述的猜疑子协议扩展

SWIM协议发送的所有点对点消息都是UDP报文。在SWIM:Basic中，最大的有效消息负载为15b，SWIM+Inf和SWIM+Inf.+Susp中最大为135B。协议（因为每条消息最多承载6个成员更新）。

5.1 消息负载

图2显示了SWIM故障检测器对任意组成员施加的消息发送和接收负载。读取的时间跨度超过40个协议周期。最多可达一组55个成员，平均开销保持在2.0左右。这与分析估计相匹配，在每个协议的周期中，一个组成员发送单个ping和接受对应的ack，以及接收一个ping消息（根据期望）并发送相应的返回。标准的偏差条表示典型的消息开销保持在较低水平，例如N=28个成员时，每个协议周期发送消息的开销小于5条消息的概率为0.99。

回想一下我们在第4节中的描述，该图显示了每个成员的总消息开销SWIM+INF。和SWIM+INF+Susp，其中SWIM:basic只有基本负载（额外的组播传播成员关系更新）。

5.2 探测成员更新的检测和传播延迟

略

5.3 故障探测误报

略

6 结论和相关工作

我们已经提出了设计实现以及执行了SWIM的评估，一个可扩展的弱一致性组成员协议。SWIM项目的动机是心跳协议的不可扩展性，它在分布式系统设计中很受欢迎。

SWIM的解决发难是基于拆解了问题的故障探测和成员更新广播组件。SWIM的项目动机是基于心跳协议的不可扩展性，并且通过进程之间随机的p2p探测进行替代。它给组成员带来了常数的开销，以及常数级别的故障探测。通过承载由故障检测器协议生成的数据包，成员更新以感染方式高效可靠地传播（流行病模式）。增加怀疑机制（与减少虚拟化身数）减少误报频率同时权衡故障检测时间。协议的最后一个扩展保证在每个非故障进程中有限的时间进行故障探测。

通过对ping目标选择和拓扑信息进行加权，SWIM可以被扩展到广域网或者虚拟私人网络，从而减少了网络内部核心网元素带宽的使用。我们目前正在评估此功能。

这篇论文描述SWIM在特殊上下文中的实现，但是没有更泛用的应用。虽然SWIM的是设计是针对于大的进程组，我们的分析和实验结果表明，这种方法可以替代对所有的分布式心跳，如果在中等规模的子组中应用，例如分布式哈希表中的复制组，可以降低开销一个数量级。例如Chord，Pastry，Opus。怀疑机制一般适用于任何具有不同失效检测和成员更新组件设计的成员系统。

在今天的网络中，大规模分布式应用程序的持续扩散程度将取决于在这些系统运行协议的可伸缩性和有效性设计。SWIM提供了这样的解决方案来给组成员组件应用。

[1] T. Anker, D. Breitgand, D. Dolev, and Z. Levy. CONGRESS: Connection-oriented group-address resolution service. In Proc. SPIE’97 on Broadband Networking Technologies, 1997.

[2] N. Bailey. The Mathematical Theory of Infectious Diseases and its Applications. Hafner Press, second edition, 1975. [3] K. P. Birman. The process group approach to reliable distributed computing. Comm. of the ACM, 36(12):37–53, 1993. [4] K. P. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Minsky. Bimodal multicast. ACM Trans. on Computer Systems, 17(2):41–88, 1999.

[5] C.E.Perkins and E. Royer. Ad hoc on-demand distance vector routing. In Proc. 2nd IEEE Workshop on Mobile Computing Systems and Applications, pages 90–100, 1999.

[6] T. D. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. Journ. of the ACM, 43(2):225– 267, 1996.

[7] W. Chen, S. Toueg, and M. K. Aguilera. On the quality of service of failure detectors. In Proc. 30th Intnl. Conf. on Dependable Systems and Networks, pages 191–200, 2000. [8] A. Demers, D. Greene, C. Hauser, W. Irish, and J. Larson. Epidemic algorithms for replicated database maintenance. In Proc. 6th Annual ACM Symp. Principles of Distributed Computing, pages 1–12. ACM Press, 1987.

[9] S. A. Fakhouri, G. Goldszmidt, I. Gupta, M. Kalantar, and J. A. Pershing. Gulfstream - a system for dynamic topology management in multi-domain server farms. In Proc. 3rd IEEE Intnl. Conf. on Cluster Computing, pages 55–62, 2001. [10] M.J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. Journ. of the ACM, 32(2):374–382, 1985.

[11] I. Gupta, K. Birman, and R. van Renesse. Fighting fire with fire: using randomized gossip to combat stochastic scalability limits. To appear in The Journ. of Quality and Reliability Engineering International, 2002.

[12] I. Gupta, T. D. Chandra, and G. S. Goldszmidt. On scalable and efficient distributed failure detectors. In Proc. 20th Annual ACM Symp. on Principles of Distributed Computing, pages 170–179. ACM Press, 2001.

[13] A.-M. Kermarrec, L. Massoulie, and A. Ganesh. Reliable probabilistic communication in large-scale information dissemination systems. Technical Report MMSR-TR-2000- 105, Microsoft Research, Cambridge, UK, 2000.

[14] K. Petersen, M. Spreitzer, D. Terry, M. Theimer, and A.J.Demers. Flexible update propagation for weakly consistent replication. In Proc. 16th ACM Symp. on Operating Systems Principles, pages 3–6. ACM Press, 1997.

[15] A. Rowstron and F. Kaashoek, editors. Proc. 1st Intnl. Workshop on Peer-to-Peer Systems. Springer-Verlag, 2002.

[16] R. van Renesse, Y. Minsky, and M. Hayden. A gossip-style failure detection service. In Proc. Middleware, pages 55–70, 1998.