云环境下节点失效检测机制研究

刘艾侠

(宝鸡职业技术学院 计算机系， 宝鸡 721013)

云环境下节点失效检测机制研究

刘艾侠

(宝鸡职业技术学院 计算机系， 宝鸡 721013)

针对云计算系统的可靠性问题，设计云环境下基于拜占庭容错模型的节点失效检测机制。当云环境系统中发生节点失效或者节点超时，利用设计的拜占庭容错算法，自动检测出系统的失效节点并且隔离，提高系统的检测精度。算法通过构造节点矩阵检测出失效节点。仿真实验表明，该模型能够有效的隔离云环境中失效节点和超时节点，大大提高了系统的可靠性。该模型还提供了反向恢复，当所有节点通过拜占庭容错模块，若失效节点数大于总节点数的1/3，系统将反向恢复到输入缓冲器。

云计算； 失效检测； 容错算法； 缓冲器

0 引言

云计算(cloud computing)是基于互联网的相关服务的增加、使用和交付模式，具有资源共享的特性。在云环境下由于使用了大量廉价的服务器集群，节点失效不可避免。因此如何处理节点失效，提高云计算系统的容错能力，是云计算学术研究中的一个热点[1-2]。传统的拜占庭算法有OM算法和SM算法，但是这些算法都是有前提条件[3]，像OM算法需要发令者将他的命令发给每一个副官并且每个副官采用他从发令者发来的命令，如果没有收到任何命令，那么使用撤退命令。像SM算法需要忠诚将军的签名是不能伪造的，内容修改可检测并且每个人都可以分辨将军的签名，叛徒可以伪造叛徒司令的签名[4]。文献[5]中，为了保证应用系统7×24的可用性，提出了ECA(Event Condition--Action)模式：通过持续监视系统的异常行为，执行所对应容错、调度操作。通过定位失效节点，方便系统运维人员准确地了解系统行为，也能够避免由于错误触发相关容错、调度机制给系统带来的扰动。文献[6]中，针对传统拜占庭容错算法Quorum算法存在的系统存储空间利用率低的问题，提出了一种纠错码拜占庭容错Quorum(Erasure-code Byzantine Fault-tolerance Quorum，E-BFQ)方法，通过采用纠错码来作为系统的冗余策略，可以提高系统的可靠性，且占用系统存储空间更少。文献[7]中，为提高无线Mesh网络(WMN)的可靠性，构建一个WMN拜占庭容错网络结构，并提出一种拜占庭算法，用以改进现有WMN路由协议，能对异常节点信息进行容错处理，增强网络的容错能力。

针对不同类型云计算节点失效的问题，本文设计一种基于拜占庭容错模型的节点失效检测机制。通过该模型，系统能够自动检测出失效节点并隔离，从而提高了系统的可靠性，具备更高的失效检测精确度。在此基础上提出基于该模型的节点失效检测算法，最后通过仿真实验验证该算法的正确性和有效性。

1 拜占庭容错模型设计

如图1所示，在云计算系统中，设置M个节点(VM1,VM2,…,VMm)，每个节点从输入缓冲器中获取数据，拜占庭容错模型(以下简称BFT模型)如图1所示。拜占庭容错模块是负责对节点输出结果进行拜占庭算法，防止失效节点对系统输出的干扰。输出结果通过时间计算模块，时间计算模块是用来计算每个非失效节点上进程的运行时间。在此基础上，可靠性计算模块负责计算每个节点的可靠性。然后，所有的结果都转发到选择模块，选择模块用于选择可靠性最高的结果。具有最高可靠性的结果就是系统的输出结果。下面对BFT模型的每一个模块进行描述。

图1 BFT容错模型

拜占庭容错模块(BFT)收集每个虚拟机发送的信息，通过设计的拜占庭算法，找出失效节点并且隔离，将正确结果输出到时间计算模块，如果节点是失效节点，其结果不通过时间计算模块。

时间计算模块(TC)是计算每个模块产生输出结果所需要的时间。TC模块将结果传递给可靠性计算模块，它只通过正确结果。如果某一节点的运行时间超过限定时间，该节点将不通过下一模块进行可靠性计算。如果TC模块限定时间太小，所有的节点不能产生结果，那么TC模块进行反向恢复，恢复到输入缓冲器，TC模块提高自身的限定时间。

可靠性计算模块(RC)负责评估每个节点的可靠性。在开始时，每个节点的可靠性假设为1。如果一个处理节点能够在限定时间内产生正确的结果，其可靠性会提高，未能在限定时间内产生正确的结果，可靠性降低。系统设有一个最小和最大的可靠性水平，如果任何处理节点的可靠性低于最低可靠性水平或者大于最大可靠性水平，RC停止该节点的进一步工作，并隔离它。如果所有节点的可靠性低于最低可靠性水平或者大于最大可靠性水平，系统停止进一步工作，恢复到输入缓冲器，重新设置最小最大可靠性水平。

选择模块(SM)选择在一个计算周期内具有最高可靠性的节点作为最终输出。如果两个节点具有相同的最高可靠性水平，那么具有较小的IP地址的节点被选定为输出。设置一个系统可靠性水平(sl)，这是实现通过结果的最小可靠性水平。SM比较最佳的可靠性与sl的大小，最佳的可靠性水平应大于或等于sl。如果没有达到sl的值，执行反向恢复，恢复到输入缓冲器。在检查点的帮助下向后进行。

BFT模型提供了一种自动向前恢复机制。如果一个节点不能产生输出或时间超时，系统将不会失效，它在其余的节点上继续运作。这种机制会产生输出直到所有的节点都失效，恢复到初始位置。

2 节点失效检测算法实现

在失效节点数小于m/3的前提下(m是云计算节点总数)，设计了云环境下基于拜占庭容错模型的节点失效检测算法(以下简称BFT算法)。该算法在节点相互传递信息时，构造了一维矩阵(m*1，m是节点数)，然后将m个一维矩阵构造成m*m的节点矩阵。通过对节点矩阵的列由少数服从多数判断出是否有失效节点，有失效节点删除。下面举例四个节点中出现一个失效节点(方便模型的分析)，通过对拜占庭问题的研究，设计了一种矩阵算法，能够将拜占庭两种情况结合为一种算法，假设A、B、C、D是四个云计算中的节点，其中C节点失效，现在要检测出C节点是失效节点，假设A发送1为正确消息，B发送2为正确消息，D发送4为正确消息，C向其它节点发送不同的错误消息，如图2所示：

图2 云环境下基于四个节点的拜占庭容错模型原理

每个节点将自己的有效消息和收到其它的节点的消息，构成一个4*1的一维消息矩阵，则A(1，2，x，4)，B(1，2，y，4)，C(1，2，3，4)，D(1，2，z，4)，可以看出C节点向其他3个节点发送了不一样的数据，但是有效的节点还不能够判定哪个节点发生了故障，因此每个节点将收到的一维信息矢量再发送给其他节点，如图3所示：

图3 云环境下基于四个节点的拜占庭矩阵算法原理

这样每一个节点就会生成一个矩阵，如下所示：

最后，对矩阵的每一列进行选择，每个节点按照少数服从多数的规则，如果节点矩阵的某一列中某一个数占多数(如矩阵A中第二列2最多，表示2为B正确消息)，那么我们选择这个值作为正确的结果。如果某一列中没有某个数占多数，则该列表为error，由此可以得到A、B、D三个节点为有效节点，C节点发生了故障，那么各个节点收到的消息为A(1，2，error，4)，B(1，2，error，4)，D(1，2，error，4)。在判断C节点的时候，虽然没有某个数占多数，但A、B、C三个节点判断的数是一样的，都是(x，y，z)，那么各个节点得出的结果也是一致的。可见，A、B、D三个节点实现了协调容错，得出了共同的正确结果。

该拜占庭矩阵容错模型，通过构造矩阵传递信息，可以准确并且有效的检测出失效节点的位置，大大提高了效率。

可靠性计算模块(RC)算法是评估每个有效节点的可靠性。最初节点的可靠性被设置为1。该算法需要输入三个变量:f，minR，maxR。f是一个可靠性因子，即增加或减少节点的可靠性。minR是最小可靠性水平，如果一个节点达不到这个水平，它被停止执行进一步的操作。maxR是最大可靠性水平，节点的可靠性不能超过这一水平。变量的值(f，minR，maxR，sl)依赖于实时应用，用户决定每个变量的值。这些变量的计算不在此研究范围中。

3 实验测试

在CloudSim环境下，模拟云计算环境中的用户、代理、资源信息服务等对象，用XML语言进行描述，并将所有的云计算模拟信息存放在config.xml配置文件中,在startEntity方法中调用扩展的拜占庭容错等算法[7-8]。

设置环境变量[9]：reliability=1.000，f=0.3，sl=0.8，maxR=1.180，minR=0.940。创建虚拟机，在虚拟机上建立资源代理，仿真步骤如下[10]：初始化CloudSim库、创建数据中心、创造代理Broker、创建虚拟机、创建云任务、调用算法、启动仿真、结果统计。创建了4个节点，这是因为拜占庭问题的前提是失效节点数小于m/3(m是云计算节点总数)，因此这里设置4个虚拟机，这样当有1个节点失效的时候，BFT模块能够通过算法找出失效节点并且隔离，这样对后续的模块计算可靠性不会产生失效。该实验具有6个计算周期，在这个实验中，我们有一个输入缓冲器，该输入缓冲器提供节点的输入。BFT模块收集每个虚拟机发送的信息，通过设计的拜占庭算法，找出失效节点，将正确结果输出到TC模块，如果某节点是失效节点，其结果不通过TC模块。TC模块检查每个虚拟机结果的时效性，然后通过结果到可靠性计算模块。RC计算三个模块的可靠性后，将结果传递到选择模块SM，在所有的结果中选择最佳的可靠性。

表1是节点1的实验测试数据，如表1所示。

系统设置的各个节点初始的可靠性是1.000。在第1个周期后，节点1是有效节点，其可靠性增加了3%，为1.030。在第2个周期后，由于节点1运行超时，可靠性降低了3%，为0.999。第3个周期，由于拜占庭容错算法，检测出节点1为故障节点，节点可靠性降低，为0.969。第4个周期类似第2个周期，第5个周期类似于第3个周期的情况，第六个周期，节点1为有效节点，节点的可靠性增加到0.939。图1是节点1在6个计算周期中可靠性的变化图，其中在周期4,5,6中节点的可靠性低于系统设置的最小可靠性，如果最终它们是系统的输出结果，不符合要求，那么系统将反向恢复，如图4所示：

表1 节点1测试数据

图4 节点1可靠性示意图

表2是节点2的实验测试数据，如表2所示。

表2 节点2测试数据

系统设置的各个节点初始的可靠性是1.000。其中在周期1,2,3中节点2都是有效节点，节点的可靠性依次增加3%。周期4节点超时，可靠性降低。在周期5中，节点2发生故障，可靠性降低。在第六个周期中，节点是有效节点，可靠性增加为1.059。图2是节点2在6个计算周期中可靠性的变化图，如图5所示。

表3是节点3的实验测试数据，如表3所示。

表4是节点4的实验测试数据，如表4所示。

因为节点3和节点4在6个周期中都是有效节点并且没有超时，所以它们的可靠性逐渐递增，如图6所示。

在第1个周期中，4个节点都是有效节点，通过RC模块后，产生的可靠性都是1.030，由于VM4具有最小的IP，因此SM选择最高可靠性节点VM4。在周期2中，VM1运行时间超过限定时间，但是不影响其他节点的正常运行，VM2、VM3、VM4的可靠性相等，SM选择IP最小的节点VM4。

图5 节点2可靠性示意图

节点3测试数据周期限定时间BFTTCTimeR12500PassPass23381.03023700PassPass35991.06133000PassPass20841.09343800PassPass32561.12653200PassPass18921.16062800PassPass26531.195

表4 节点4测试数据

图6 节点3和节点4可靠性示意图

在周期3中，VM1失效，通过BFT模块，能够找出失效节点并且隔离，VM1不通过后续模块，其余三个节点的可靠性相等，SM选择IP最小的节点VM4。在周期4中,VM1和VM2都超时，但是不影响其他节点的正常运行,VM3、VM4的可靠性相等，SM选择IP最小的节点VM4。在周期5中，VM1和VM2都失效，这个违背了拜占庭模型的前提，因此SM选择的VM4是有问题的，这种情况不符合模型的理论依据，参照模型，系统执行反向恢复，恢复到输入缓冲器。在周期6中，4个节点都有效，且均为超过限定时间，但是最高可靠性是VM4的1.195，超过了maxR的1.180，系统执行反向恢复，恢复到输入缓冲器，重新设置maxR。

4 总结

与传统的云计算系统模型相比，本文方法具有较高的节点失效检测精度，并能够有效屏蔽节点超时失效，从而提高了系统的容错能力。本文设计的模型较以往的容错模型具有以下几处优点：基于传统的拜占庭算法，本文设计了拜占庭容错算法没有局限性，通过构造矩阵的方式，化繁为简，更具有普遍性和适用性；该模型具有反向恢复系统，当系统的失效节点数超过总节点数的1/3，或者由于系统设置的参数导致系统未能找出最终输出的最高可靠性的节点，系统可以反向恢复，重新设置参数，恢复系统，找出系统的最高可靠性。模型中加入这种机制，提高了系统的可靠性，当系统出现超时节点过多或者节点可靠性过大过小，系统可以通过反向恢复，通过改变参数，重新正向执行，找出系统的最高可靠性的节点。

[1] 邹立新, 丁建立. 基于拜占庭协议的入侵容忍系统模型设计[J]. 计算机工程, 2005, 31(s1):88-90.

[2] 孙周军, 易锋, 肖文名,等. 基于拜占庭协议构建具有入侵容忍能力的Web服务研究[J]. 微电子学与计算机, 2008, 25(3):35-37.

[3] 吴雄飚, 林建人, 进 王,等. 基于信任的IP网络两阶段容错容侵路由机制:, CN 101296181 A[P]. 2008.

[4] 齐平, 李龙澍, 李学俊. 具有失效恢复机制的云资源调度算法[J]. 浙江大学学报(工学版), 2015, 49(12):2305-2315.

[5] 田冠华, 孟丹, 詹剑锋. 云计算环境下基于失效规则的资源动态提供策略[J]. 计算机学报, 2010, 33(10):1859-1872.

[6] 程仕伟, 潘郁. 云计算环境下基于可信性的动态资源分配策略[J]. 计算机工程, 2011, 37(11):45-48.

[7] 付小青, 沈剑. 能容纳拜占庭错误的身份认证协议[J]. 华中科技大学学报(自然科学版), 2005, 33(5):22-25.

[8] 王吉喆, 赵蕴龙, 吴静. WMN中拜占庭容错网络结构及算法[J]. 计算机工程, 2011, 37(20):83-86.

[9] 陆正福, 晁巍. 具有长时安全性的高性能异或秘密共享协议的研究[J]. 云南大学学报:自然科学版, 2014(3):321-328.

[10] Liu Haijiao, Jing Jiwu, Lin Jingqiang,等. Building an Intrusion Tolerant Repository[J]. 中国科学院大学学报, 2006, 23(1):46-51.

[11] 荆继武, 王晶, 林璟锵,等. 基于门限签名方案的BQS系统的服务器协议[J]. 软件学报, 2010, 21(10):2631-2641.

Research of Node Failure Detection Mechanism in Cloud Environment

Liu Aixia

(Baoji Professional Technology Institute， Baoji 721013, China)

In view of the problem of reliability of cloud computing system, node failure detection mechanism based on Byzantine fault-tolerant model in cloud environment is designed. When the node failure or time-out occurs in cloud environment system, the designed Byzantine fault-tolerant algorithm is utilized to automatically detect and isolate system failure node, and improve the test accuracy. The failure node is detected by constructing node matrix. Simulation experiments show that the model can effectively isolate node failure or timeout in cloud environment, greatly improving the reliability of the system. The model also provides a reverse recovery. When all the nodes go through the Byzantine fault-tolerant module, if the failure node number is more than one third of the total number of nodes, the system will reverse back to the input buffer.

Cloud computing; Failure detection; Fault-tolerant algorithm; Buffer

刘艾侠(1982-)，女，陕西周至人，大学本科，讲师，研究方向：计算机技术。

1007-757X(2017)05-0059-04

TP311

A

2016.11.20)