2019, Vol. 51
2. 江苏省宽带无线通信和物联网重点实验室 (南京邮电大学)，南京 210003
2. Jiangsu Key Laboratory for Broadband Wireless Communication and Internet of Things(Nanjing University of Posts and Telecommunications), Nanjing 210003, China
云计算通过组织成百上千台计算和存储服务器利用互联网为用户提供计算资源[1-2].如此大的规模，结合不断增加的系统复杂性，使服务器的失效变得不可避免[3].因此，为使系统能够在一些部件失效的情况下提供可靠和持续的服务，云计算采用了容错的设计架构[4-5].失效检测器(Failure Detector, FD)是构成云计算容错架构的基础模块[6].一个理想的失效检测器应当同时提供可接受的服务质量(QoS)以及满足多个云计算应用的不同的QoS需求[7].
由defago[8]提出的accrual检测器十分适合服务于大规模分布式系统.它以连续怀疑值作为最终的输出结果，将监测权与解释权相分离.在accrual检测器中，怀疑值的计算依靠历史心跳消息到达时间间隔的概率分布.以往的实现中，通常假设心跳消息到达时间间隔的概率分布符合一些稳定的或变化缓慢的概率分布(如正态分布和指数分布[9-10])，缺少对网络环境突然变化的考虑.在云计算中，服务器可能处于活跃、忙碌、过载、离线甚至崩溃状态[11]，这些情况造成网络行为的突然改变.并且，通过对云计算中网络行为的分析，发现其网络环境容易发生突然变化[12].”
在本文中，提出一种能够适应云计算环境中网络环境突然变化的accrual失效检测器—2WA-FD.2WA-FD使用两个滑动窗口去分别存储不同数量的心跳消息到达时间，较大的滑动窗口处理网络环境的稳定期，而较小的滑动窗口处理网络环境的突然改变.同时，通过对两种不同环境(WAN和云计算环境)的实际数据的分析，结果显示威布尔分布是一种对心跳消息到达时间间隔更加合适的分布假设.因此，使用威布尔分布对2WA-FD的历史心跳消息到达时间间隔作为分布概率假设.
为评价2WA-FD的性能，选择了5个著名的失效检测器通过检测时间、平均错误发生概率以及查询准确率进行了比较.所有参与比较的失效检测器均被实现在同样的WAN和云计算数据之上.最终的实验结果显示，2WA-FD在不稳定的网络环境(特别是云计算)中，能够拥有更加优秀的检测性能.
1 心跳消息行为分析为找到一种更加合理的心跳消息到达时间间隔的概率分布假设，选择两组不同平台(WAN和云计算)的数据进行分析.一组数据是曾经被φ检测器使用的来自WAN平台的经典的实验数据.这组数据的采集时间超过一周，并且有500多万条心跳消息.其平均到达时间间隔为103.9 ms，标准差为104.1 ms.另一组数据来自租用亚马逊EC2平台产生的云计算实验数据.这组数据的采集时间超过3个月，并且有300万条心跳消息.其平均到达时间间隔为2.07 s，标准差为1.94 s.
通过MATLAB中的dfittool工具对来自WAN平台的数据的累积分布进行了分析.设定置信区间为95%，利用3种不同的分布(正态分布，指数分布以及威布尔分布)进行数据拟合.如图 1所示，曲线显示威布尔分布是最接近真实数据的分布.类似的结果也出现在云计算平台的数据拟合后，如图 2所示.根据实验结果，可以得知威布尔分布是一种更加接近真实数据分布的概率分布.因此，在不稳定的网络环境中，威布尔分布是一种更加合理的描述心跳到达时间间隔的概率分布.
|
图 1 WAN数据拟合结果 Fig. 1 Fitting result in WAN |
|
图 2 云计算数据拟合结果 Fig. 2 Fitting result in cloud computing |
考虑一个部分同步的系统由有限个进程Π={p1, p2, …, pn}组成.每一个进程正常工作直到崩溃，并且崩溃后不能恢复.任意两个进程可以被一条不可靠的链路连接.因为多数的失效检测器是用UDP协议实现的，所以假设进程之间的连接链路是fair-lossy链路(即没有消息被复制或修改，而且没有新的消息被创造).如果一个进程p持续发送心跳消息m到q，q最终会收到心跳消息m.
假设存在一些全局时间，这些全局时间被定义为全局稳定时间(GST).在到达全局稳定时间后，消息的传输时间和进程的处理速度都是有界的，但是这个界限及GST是未知的.
为简化描述，考虑一个系统中仅包含两个进程p和q，进程q正在检测进程p.进程p每隔时间Δt(发送间隔)发送一条心跳消息到进程q.如果进程q没有在一个时间周期内收到进程p的消息，就会考虑进程p已经失效.
2.2 2WA-FD检测器的实现基于以上对心跳消息到达时间间隔的分析，能够假设心跳消息的到达时间间隔符合威布尔分布.因此，2WA-FD的怀疑值wd可通过以下公式.
| $ w_{\mathrm{d}}\left(T_{\mathrm{now}}\right)=F\left(T_{\mathrm{now}}-T_{\mathrm{last}}\right). $ | (1) |
式中F(t)为威布尔分布的累积分布函数，因此
| $ F(t)=1-\mathrm{e}^{-(t / \alpha) \beta}. $ | (2) |
式中t>0，且参数α和β能够通过最小二乘法进行估算[13].
为适应网络环境的突然变化，用两个滑动窗口(Ws和Wb)去保存历史心跳消息到达的时间.较小的滑动窗口Ws被用来存储少量的最近的心跳消息，用来处理网络环境的突然改变(可能由于服务器失效引起).而较大的滑动窗口Wb能够存储更多的心跳消息的到达时间，用来应对稳定的网络环境.
作为一个accrual失效检测器，其实现方法相对简单.预热期过后，当新的心跳消息到达，其到达时间被分别存储到不同的滑动窗口.同时，滑动窗口中最早的心跳消息到达时间被删除.然后，滑动窗口中的心跳消息的到达时间被用来计算威布尔分布的参数α和β.接下来，基于式(15)和(16)，能够分别计算当前的怀疑值(ws和wb)，两者之间较小的值作为最后2WA-FD的输出值wd.最后，应用程序比较自己设定的阈值Wd与输出值wd，它会根据比较结果执行相关的操作或者开始怀疑被检测进程.详细的2WA-FD实现信息可以见图 5.它是容易证明的，2WA-FD是一个最终完美失效检测器◇Pac.
|
图 5 WAN环境中不同尺寸滑动窗口下查询准确率与检测时间 Fig. 5 Query accuracy vs. detection time of different sliding windows in WAN |
在每次失效检测过程中，如果检测器在规定时间内，没有收到心跳消息，怀疑值将会增长，如算法1所示，Increased wd，其时间复杂度为O(1).如果检测器接收到心跳消息并且心跳消息的序号大于目前滑动窗口中心跳消息的最大序号，那么将会计算新的怀疑值.在此过程中，频度最高的语句是利用最小二乘法计算威布尔分布的参数(Compute parameters αs and βs以及Compute parameters αb and βb)，其他语句的频度为常数值.计算威布尔分布的参数的时间复杂度分别为O(Ws)和O(Wb).那么，根据时间复杂度的求和法则，可知2WA-FD执行一次失效检测的时间复杂度为O(Wb).综上所述，在n次失效检测过程中，2WA-FD算法的时间复杂度为O(Wb·n).同时，由于2WA-FD中滑动窗口值为常数(通常Wb设定为常数值，本文实验中设定为103和104)，也可认为2WA-FD的算法复杂度为O(n).
算法1 2WA-FD检测器算法
Initialization:
Δt:sending interval
snl←0;/*keep the largest sequence number*/
Ws=Wb=⊥; /*empty sliding windows for inter-arrival times*/
Tlast←0;/*last arrival time of heartbeat*/
Process p:
For alli>0, at time (i·Δt): send hartbeat mi to q;
Process q:
Task 1 : if q did not receive heartbeat during a certain time
Period of q’s clock
Increase wd; /*suspect p*/
Task 2 : upon receiving heartbeat mj from p
If j>snl then
Ws←(Tnow-Tlast);
Wb←(Tnow-Tlast);
Compute parameters αs and βs;
Compute parameters αb and βb;
ws←1-e-((Tnow-Tlast)/αs)βs;
wb←1-e-((Tnow-Tlast)/αb)βb;
wd←min(ws, wb);
Tlast←Tcurrent；
snl←j;
Application k:
Compare wd with the threshold Wdk (from application requirement);
Carry out some actions or start to suspect p;
3 实验验证及分析对采用不同尺寸滑动窗口的2WA-FD性能进行了评估，并且找出Ws和Wb理想的参数配置.其次，把2WA-FD和自适应失效检测器进行比较分析.所有实验均执行在来自WAN平台和云计算实验平台的传输日志文件之上.实验参考了文献[11]的方法，利用传输日志文件对各个失效检测器进行重演，这样能够保证所有失效检测器的实现在同样的网络环境下.
在WAN环境中，实验包括两台计算机：一台位于日本，而另一台位于瑞士.两台计算机通过正常的洲际互联网连接进行通信.一台计算机负责周期性地发送心跳消息，而另一台计算机负责记录每一条心跳消息到达的时间.在实验过程中没有计算机发生失效.心跳消息的实际发送频率是每103.501 ms发送一条心跳消息.在实验中，心跳消息的往返时间以较低的概率进行测量，平均RTT时间是283.3 ms(标准差为207.3 ms，最小值为270.2 ms以及最大值为717.8 ms).超过500万条心跳消息被接收，且丢失率约为0.4%.
在云计算环境中，通过租用亚马逊EC2的服务器搭建实验平台.云端服务器分别位于东京、新加坡以及俄勒冈(美国)的3个节点上.3个服务器节点都可以对用户提供一个相同的基于Web的查询服务，为便于测试，并没有设置前端处理机，假设用户客户端已经知道3个服务器的网络地址，当前服务节点失效后，会自动连接新的服务器.这些服务器配有2.5 GHz的Intel Xeon的处理器，1 GHz内存以及搭载Red Hat Linux 7.2操作系统.实验环境如图 3所示.在实验中，位于哈尔滨的客户端首先连接位于俄勒冈的服务器获取服务.通过故障注入的方法使服务器停止服务(同时终止检测模块的运行)，客户端依次访问新加坡和东京的服务器.实验进行近3个月，发送间隔被设定为2 s，而实际测量的发送频率为2.092 s(标准差为0.019 s，最小值为1.964 s以及最大值为5.239 s).在实验中，平均RTT时间为0.179 2 s，标准差为0.008 6 s，最小值为0.118 7 s以及最大值为14.505 s.超过300万条心跳消息被接收，丢失率大约为0.72%.
|
图 3 云计算实验环境 Fig. 3 Experiment of cloud computing |
在实验中，检测时间，平均错误发生概率以及查询准确率作为主要的失效检测器的性能指标.对于2WA-FD，其阈值设定范围为Wd∈(0, 1)(如Wd=0.01代表设定的检测器的平均错误发生概率为10-2).根据相应的阈值设定检测器参数，在每次实验中能获取不同的检测时间，平均错误发生概率以及查询准确率.
在所有的实验中，可以通过估计来计算检测时间的均值[9].假设一个进程刚好在发送完一条心跳消息后崩溃(最糟糕的情况)，可以测量此刻到检测器发出怀疑的时间.对于文中所提到的失效检测器，根据阈值的设定去反向求取心跳消息的超时值Δto.此外，根据心跳消息的平均RTT时间，可以得知心跳消息单程传输的时间Δtr.那么，就可以计算平均检测时间的值[9, 11]
| $ T_{\mathrm{D}} \approx \Delta_{\mathrm{tr}}+\Delta_{\mathrm{to}}. $ | (3) |
此实验检测滑动窗口尺寸对2WA-FD检测性能的影响.通过改变滑动窗口的尺寸从而获取不同的准确性.为了更加清楚的观察实验结果，仅截取了最明显的部分进行描述.
图 4中显示了WAN环境下平均错误发生概率与检测时间的关系.X坐标轴表示检测时间，Y坐标轴表示平均错误发生概率.图 5中显示了WAN环境下检测时间与查询准确率的关系.当Wb=104，Ws=10时，2WA-FD能够获得最低的平均错误发生概率.当Wb=104，Ws=10和Wb=103，Ws=10时，2WA-FD能够获得最高的查询准确率.
|
图 4 WAN环境中不同尺寸滑动窗口下平均错误发生概率与检测时间 Fig. 4 Mistake rate vs. detection time of different sliding windows in WAN |
图 6和7显示了云计算中的实验结果.从实验结果可知，当Wb=104，Ws=10时，2WA-FD能够获得最好的性能.
|
图 6 云计算环境中不同尺寸滑动窗口下平均错误发生概率与检测时间 Fig. 6 Mistake rate vs. detection time of different sliding windows in cloud computing |
|
图 7 云计算环境中不同尺寸滑动窗口下查询准确率与检测时间 Fig. 7 Query accuracy vs. detection time of different sliding windows in cloud computing |
以上的实验证明2WA-FD的性能会受到滑动窗口尺寸的影响.根据平均错误发生概率和查询准确率，本文所提出的失效检测器随着Wb的增长和Ws的降低而表现的更好.同时，在实验结果中，同时注意到，当Wb的尺寸相同时，更小的Ws带来更好检测性能.而当Ws固定时，随着Wb的增长，检测器性能改善不明显.考虑与其他检测器的性能比较，对于2WA-FD，选用Wb=103，Ws=10配置进行实验.
3.2 不同的失效检测器的比较在此实验中，选用5个著名的失效检测器与2WA-FD进行比较，并且选择了不同的检测参数来获得每一个失效检测器的性能.不同于其他失效检测器，Bertier失效检测器没有调整参数，因此它的性能在图中只有一个点表示.各个失效检测器的配置参数如下：对于Chen失效检测器，参数设置如文章[9]中，α∈[0, 103]；对于SFD，其参数设置如文章[11]中，SM1=α；对于φ失效检测器，其参数设置如文章[9]中，Φ∈[0.5, 16]；对于ED FD，其参数设置如文章[10]为Ed∈[10-4, 10].这4种失效检测器的滑动窗口都设置为103.
图 8显示了WAN环境下的平均错误发生概率与检测时间的关系.X坐标轴代表检测时间，Y坐标轴代表平均错误发生概率.图 9显示了WAN场景下查询准确率与检测时间的关系.
|
图 8 WAN环境下平均错误发生概率与检测时间的关系 Fig. 8 Mistake rate vs. detection time in WAN |
|
图 9 WAN环境下查询准确率与检测时间的关系 Fig. 9 Query accuracy vs. detection time in WAN |
实验结果显示所有的失效检测器都遵循相同的趋势.随着检测时间的增长，平均错误发生概率呈现下降的趋势，而查询准确率呈现上涨的趋势.但是，在WAN环境中，当TD < 0.4 s时，2WA-FD的性能优于其他失效检测器.在平均错误发生概率方面，2WA-FD相对于ED FD有最多40%的提升.而且，在大多数检测时间上，2WA-FD获得了最好的查询准确率.
图 10和11显示了在云计算环境中平均错误发生概率，查询准确率与检测时间的关系.类似于WAN环境中的结果，2WA-FD在云计算环境中获得了最低的平均错误发生概率和最高的查询准确率.当2.5 s < TD < 4 s时，2WA-FD的平均错误发生概率明显低于其他失效检测器(有大约45%的提升).在云计算环境中，2WA-FD受益于双滑动窗口，在不稳定的网络环境中获得了良好的性能.
|
图 10 云计算环境下平均错误发生概率与检测时间的关系 Fig. 10 Mistake rate vs. detection time in cloud computing |
|
图 11 云计算环境下查询准确率与检测时间的关系 Fig. 11 Query accuracy vs. detection time in cloud computing |
从实验中，可以推断出2WA-FD在不稳定和动态的网络环境(例如WAN和云计算)中相较于其他失效检器获得了最好的检测性能.在2WA-FD中，两个滑动窗口能更好的适应网络环境的变化.但是，更大的Wb并不能明显的提升2WA-FD的性能(如图 5、6、7和8所示).滑动窗口尺寸的大小应该取决于用户的特殊需求与配置.
4 结论失效检测器在可靠的分布式系统中扮演了非常重要的角色.在本文中，提出了双窗口的accrual失效检测器2WA-FD.通过采用双滑动窗口存储心跳消息到达时间，以及更加合理的心跳到达时间间隔的分布假设，2WA-FD能够更好的应对网络环境的突然变化，并且能够很好的适应云计算的网络环境.通过对比实验，结果显示本文所提出的失效检测器在检测时间，平均错误发生概率以及查询准确率方面表现出更好的性能.因此，2WA-FD适合于部署在云计算中提供失效检测服务.
| [1] |
PANNU H S, LIU Jianguo, GUAN Qiang, et al. AFD: Adaptive failure detection system for cloud computing infrastructures[C]//Proc 31st IEEE International Performance Computing and Communications Conference. Austin, Texas, USA: IEEE Press, 2012: 71. DOI: 10.1109/PCCC.2012.6407740
|
| [2] |
DABBAGH M, HAMDAOUI B, GUIZANI M, et al. Toward energy-efficient cloud computing: Prediction, consolidation, and overcommitment[J]. IEEE network, 2015, 29(2): 56. DOI:10.1109/MNET.2015.7064904 |
| [3] |
ZHOU Ao, WANG Shangguang, ZHEN Zibin, et al. On cloud service reliability enhancement with optimal resource usage[J]. IEEE Transactions on Cloud Computing, 2016, 4(4): 452. DOI:10.1109/TCC.2014.2369421 |
| [4] |
FETZER C, RAYNAL M, TRONEL F. An adaptive failure detection protocol[C]// Proc the 2001 Pacific Rim International Symposium on Dependable Computing. Seoul, Korea: IEEE Press, 2001: 146. DOI: 10.1109/PRDC.2001.992691
|
| [5] |
DING Yongsheng, YAO Guang shun, HAO Kuangrong. Fault-tolerant elastic scheduling algorithm for workflow in Cloud systems[J]. Information Sciences, 2017, 393: 47. DOI:10.1016/j.ins.2017.01.035 |
| [6] |
LIN Rongsheng, WU Budan, YANG Fangchun, et al. An efficient adaptive failure detection mechanism for cloud platform based on volterra series[J]. China Communications, 2014, 4(11): 1. DOI:10.1109/CC.2014.6827564 |
| [7] |
LAVINIA A, DOBRE C, Pop F, et al. A failure detection system for large scale distributed systems[C]// Proc the 2010 International Conference on Complex, Intelligent and Software Intensive Systems. Krakow, Poland: IEEE Press, 2010: 482. DOI: 10.1109/CISIS.2010.29
|
| [8] |
DEFAGO X, URBAN P, HAYASHIBARA N, et al. Definition and specification of accrual failure detectors[C]// Proc the International Conference on Dependable Systems and Networks. Yokohama, Japan: IEEE Press, 2005: 206. DOI: 10.1109/DSN.2005.37
|
| [9] |
HAYASHIBARA N, DEFAGO X, YARED R, et al. The φ accrual failure detector[C]// Proc the 23rd IEEE International Symposium on Reliable Distributed Systems. Florianpolis, Brazil: IEEE Press, 2004: 66. DOI: 10.1109/RELDIS.2004.1353004
|
| [10] |
TOMSIC A, SENS P, GARCIA J, et al. 2W-FD: a failure detector algorithm with QoS[C]//Proc the 29th International Parallel and Distributed Processing Symposium. Hyderabad, India: IEEE Press, 2015: 885-893. DOI: 10.1109/IPDPS.2015.7410.1109/IPDPS.2015.74
|
| [11] |
XIONG Naixue, VASILAKOS A V, WU Jie, et al. A self-tuning failure detection scheme for cloud computing service[C]// Proc the 26th International Parallel and Distributed Processing Symposium. Shanghai, China: IEEE Press, 2012: 668. DOI: 10.1109/IPDPS.2012.126
|
| [12] |
DALMAZO B L, VILELA J P, CURADO M. Online traffic prediction in the cloud[J]. International Journal of Network Management, 2016, 26(4): 269. DOI:10.1002/nem.1934 |
| [13] |
BHATTACHARYA P, BHATTACHARJEE R. A study on Weibull distribution for estimating the parameters[J]. Journal of Applied Quantitative Methods, 2010, 5(2): 234. DOI:10.1109/TR.1981.52265 |