一种分布式并行服务器节点故障检测算法.doc

一种分布式并行服务器节点故障检测算法第36卷第1期2007年2月电子科技大学JournalofUniversityofElectronicScienceandTechnologyofChina,lI36No.1Feb.2007一种分布式并行服务器节点故障检测算法左朝树,刘心松2,邱元杰2,陈小辉2,李可2(1.中国电子科技集团公司第30研究所成都61004l2.电子科技大学计算机科学与工程学院成都610054)【摘要】故障检测技术是实现分布式并行服务器容错的基础.为了尽可能减小故障检测算法对系统通信开销的增加,寄生式自适应故障检测算法被提了出来.该算法依靠系统内部固有的信息交换进行故障检测,而通过自回归型预测消息的传输时间和处理时间,并以此自动调整故障检测的阈值,达到自适应系统运行状况的目的,最后通过伪代码的形式描述了该算法的实现.该算法已被应用于分布式并行数据库系统DPSQL,较好地实现了节点故障检测.关键词分布式并行服务器:故障检测:自适应:寄生中图分类号TP302.8文献标识码AANodeFaultDetectionAlgorithminDistributedParallelServerZUOChao.shu,LIUXin.song,QiUYuan-jie,CHENXiao-hui,LIKe(1.TheNo.30InstituteofChinaElectronicTechnologyGroupCoorationChengdu610041;2.SchoolofComputerScienceandEng/ncering,UniofElectron.Sci.&Tech.ofChinaChengdu610054)AbstractFaultdetectiontechnologyiSthebaseoffault.toleranceindistributedparallelserver.Toreducethecommunicationcostthatfaultdetectionalgorithmbringstothegreatestextent,AutoeciousAdaptiveFaultDetection(AFD)algorithmisproposed.Dependingontheexchangeofinherentinformationprocessedbysystem,thealgorithmcarriesoutfaultdetection.Toachievethegoalthatitadaptsitselftosystemstatus.thealgorithmadjuststhekeyvalueoffaultdetectionaccordingtotransmissionandtransactiontimeofthemessagepredictedbyAutoRegression(AR)mode1.Finally,therealizationofthealgorithmiSdescribedwitl1thepseudocode.Thealgorithmhasbeenappliedtodistributedparalleldatabasesystem-DPSQL,whichhasrealizednodefaultdictionwel1.Keywordsdistributedparallelserver:faultdetection;adaptive;autoeciousness随着计算机和网络技术的发展,人们对各种服务器系统提出了高可靠及高可用性的要求.为了满足这些要求,采用容错技术的分布式并行服务器系统得到大量的应用.故障检测技术是实现容错的基础,多年来,故障检测技术研究取得了丰硕的成果.在国外,文献【l】采用WATCHDOG硬件检测故障;文献【2】提出了随机分布式故障检测算法;而文献【3】提出利用周期性消息检测节点故障.在国内,文献【4】建立非线程PCA模型实现故障检测:而文献【5】则采用虚拟令牌检测节点故障,并保证故障检测时间的可预测性.上述文献从不同角度,不同层面对故障检测技术进行研究,为故障检测技术的发展奠定了基础.但是这些研究所涉及的算法都需要额外增加故障检测的通信开销或硬件,并且这些研究对故障的确定讨论较少.文献【6】指出故障检测技术存在阈值选取等问题.为此,该文基于分布式并行服务器的特点提出了寄生式自适应故障检测(AutoeciousAdaptiveFaultDetection,A2FD)算法,借助系统固有的信息交换,利用自回归AR模型预测消息的传输和处理时间,并以此作为故障检测的阈值判断节点是否出现故障.该算法不仅实现了故障检测阈值的动态自适应变化,而且不额外增加故障检测的通信开销.1分布式并行服务器模型分布式并行服务器都可以抽象为二元组(,脂所有节点共享的具有一定带宽的内部通信网络,负责所有服务器节点之间的信息交换;),表示编号为棚勺服务器节点,通常是一台高性能PC服务器,其中n=l,2,.系统的模型如图l所示.每个节点都驻留一个内部通信系统,专门负责本服务器节点与其他服务器节点之间的消息传收稿日期:20050613作者简介:左朝树(1972一),男,博士,主要从事分布式计算机方面的研究.120电子科技大学第36卷递.由于软硬件等原因,节点以及与节点相联的通信网络都可能出现故障,导致节点不能正常提供服务,统称为节点故障.若节点出现故障那么该服务器节点不能工作,而S(s-)的C,将不能正确发送消息到,同时也不会从收到任何消息.在分布式并行服务器中,为了完成用户的任务和维持系统的正常运转,所有节点间存在大量的需要交换的信息,因此通信是系统必不可少的一部分.图1分布式并行服务器2A2FD算法AFD算法利用系统固有的消息交换完成对节点的故障检测,从而避免额外的通信开销.2.1基本思想节点故障可以分为节点通信故障和节点崩溃两种情况.由于分布式并行服务器是通过高速网络连接的多个节点,节点间需要进行频繁的信息交换.如果某些节点出现故障,就会在通信上有所反映,因此可以利用通信系统反馈的信息,判断节点故障.另外,为了不额外增加系统的通信开销,可利用系统本身的消息交换实现节点故障检测.系统中可作为故障检测的消息有两类:(1)只需可靠发送到对方而不需返回结果的消息,用A标识;(2)需可靠发送到对方且处理后需返回结果的消息,用标识.如果节点需要发i羞类消g*JJ节点,可以通过Socket提供的机制检测消息是否成功发送到S.若发送失败,认为S发生了节点故障,则在系统中广播故障消息;若发送成功,则记录发送时间.如果节点需要发送类消息到,分别取阈值为和,并将附带在消息中一起发送到节点S,同时启动定时器,设置定时器的值为.若定时器超时,表明节点出现故障;若在定时器未超时情况下收到f返回的结果消息,就终止定时器.节点f在收到消息后同样启动一个定时器,设置时间为.在定时器超时时,故障检测模块检测节点的服务是否崩溃.若节点S没有崩溃,就发送保活消息到,而S收到该消息就重置定时器的值为.为了确定和的值,系统分别以每个或作为一个周期.每个周期计算一次平均值或元,并作为时间序列和的最后一项.若序列超过尸项时,就删除最左边的一项.每当序列更新都重新计算阈值和.其中和尸由通信量,处理能力等确定为常数.2.2阈值的确定系统中的A和两类消息的交换过程如图2所示,图中虚线表示节点的保活消息,可以是0到数个.为了尽可能减少保活消息死和死一,以及为了得到和的值,根据序列)和元),利用自回归AR模型预测和死的值.令时间序列为向量,.由向量阿以得到均值和自相关函数值(k=-O,l,尸),即:=1P1Pkj一一.-s西(一)()()=(一)尤尔一沃克方程为:Za,一,lkP(2)由式(2)可以得到向量口=(1,a2,T,且有:口=,b(3)式中厂=:yP一1:yP一2,b=(,)计算式(1)的函数值并代入式(3)就可得到向量a,且向量a确定了AR预测模型的相关参数.根据向量a可以预测下一个周期的值T:|DT=li=1分别对序列)和)使用AR模型可得下一个周期的和死.考虑到网络负载等的影响,并减少误判率,可引入修正系数(1.0,1.5),则,死=死,lJT,-=a死,砰=(死一).SS图2节点间消息交换过程3算法实现及仿真3.1实现A2FD算法中,每个节点位于紧邻内部通信系统一一0第1期左朝树等:一种分布式并行服务器节点故障检测算法121的上层,所有消息通过它利用进行交换.根据消息的方向性,将该算法得到的消息分为发送消息和接收消息.发送消息包括A和B两种类型.接收消息可以分为三类:(1)表示对方正常的保活消息:(2)返回结果的消息;(3)对方的点对点的通知消息.根据AFD算法的基本思想,每种消息都应该具有不同的处理措施,可用伪代码描述AFD算法的处理过程如下.PROCAutoecious_Adaptive_Fault_Detection0;故障检测处理过程FORMessageWait_Message0IFIs_Send_Message(Message)有消息需要发送)【IFMessageATHEN【IF!ID=GetIDFrom_Message(Message)THEN得IID表示该消息是返回结果)Message=Message+ID;ID消息标号ELSE【Stop(Timer(劢,ID);Timer(劢函数如果不终止,在时间后将检测节点是否正常,如果正常将发送Keep消息,重启动定时器.Alive】IFMessageBTHENMesage=Message+ID+:Start(Timer(Ti,ID);Timer(T,函数如果不终止,在时间后执行Broadcast(.ault)>】Send(Message);并监测是否发送成功;通过发送IFSuccessTHEN=+GetSendJime0;ELSEBroadcast(Sj_Fault);通知系统中所有节点与出现故障,IFMessageMessageeBTHENStop(Timer(Ti,ID);】ELSE表示收到消息ID=GetIDFrom_Message(Message);IFGeLType_Of_Message(MessageKeepAliveTHEN收到正常的消息>Reset(Timer(T,ID);ELSEIFGetJ.ype_Of_Message(Message)-=ResultTHEN收到执行结果消息)【Stop(Tef(死),JD);Ts=TBHGetHandle_TimeO;】ELSE收到需要执行的消息)【eLrom_Message(Message);Start(Timer(,ID);】ENDP;Autoeciodaptive_Fault_Detection3.2仿真在分布式并行数据库系统DPSQL开发中,本文采用c语言基于Linux平台实现了AFD算法.通过100M交换机连接10台ecJl务器构成同构系统,而由连接到系统的客户数量模拟系统的工作负载进行仿真测试.在测试过程中,利用测试程序人为关闭一个或几个服务器节点的网卡,或者直接关闭一台或几台服务器的电源,以模拟系统节点故障测试AFD算法的可用性,并得到故障检测时间.通过测试发现,不论是哪种情况,系统都能正确检测到节点故障.在不同任务负载情况下的测试表明,系统任务越多,AFD算法的故障检测时间越短,没有任务时,故障检测时间最长,但都能在一定时间内发现故障.系统任务越多,系统内的通信量越大,节点间交换信息的时间间隔越短,因此故障检测时间越短.当系统中不存在任务时,节点间不存在为完成任务而进行的信息交换,只存在维护系统正常运转的管理信息,而这些信息大多是周期性发出的,具有固定的周期时间,因此故障检测时间最长,并且比较固定.AFD算法已成功应用于分布式并行数据库系统DPSQL,并在视频点播等多个应用领域中得到使用.4结束语为实现分布式并行服务器节点故障检测,根据系统特点,提出了寄生式自适应故障检测算法.该算法利用系统节点间固有的消息交换,实现了节点故障检测.同时为了适应系统的运行状况,该算法利用自回归AR模型预测消息的传输和处理时间,并以此动态更新故障检测的阈值即响应时间.最后利(下转第125页)第l期姜文彬等:数字多路选择器树形嬲络设计理论和算法i25X4瓢f图2函数厂用M(2)实现的最小树形网络3结束语本文利用多路选择器网络可以实现任意逻辑函数的原理和布尔代数运算,提出了基于逻辑函数的DRSOP形式的数字多路选择器树形网络设计的一(上接第121页)用伪代码描述TA2FD算法的实现,此算法不仅达到了节点故障检测的目的,而且不额外增加系统的通信开销,并动态适应系统运行状况的变化.A2FD算法已被应用于分布式并行数据库系统DPSQL.为了实现分布式并行服务器节点容错,可进一步就节点容错算法等进行深入研究.参考文献【1】LYUMMENDIRATTAVB.Softwarefaulttoleranceinaclusteredarchitecture:techniquesandreliabilitymodeling【c/In:Proc.IEEEAerospaceApplicationsConference,1999,5:141-150.种代数方法,这种方法可以使待设的MUX网络达到最小树彤网络.然后给出了设计实例,从给出的设计实例可以看出,这种设计方法是有效的.并且由于使用的方法为一种解析方法因而容易实现多路选择器网络的自动综合.参考文献fl】TOSSERAJ,AOUAD-SYADD.Cascadenetworksoflogicfunctionsbuiltinmultiplexerurtsj.1EEProcPtE,l980,l27(2):64-68.2】2LLOYDAM.Designofmultiplexer1】ersallogicmodulenetworksusingspectraltechniquesJ.IEEProcPtE,1980127(1):31-36.【3】VOITHREULMimplicantsforInini!nizatonofuniversallogicmodulecircuits【J】.IEEETransComput,l977,C一26(5):4l7424.4】ALMAIN/AEMILLERjEXuLAutomatedsDathesisofdigialmultilexernetworksJ.IEEProcPtEl992l39(4)329334【5】SHANNONCE