基于在线负载预测的动态集群节能配置策略

第３６卷　第２４期　ＶＯ１．３６　ＮＯ．２４　计算机工程　２０１０年ｌ２月　Ｄｅｃｅｍｂｅｒ　２０１０　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　・网络与通信・　文章编号：１０ｏｏ—３４２８（２ｏｌｏ）２４—ＩｌＩｌ９６＿一ｌ３　文献标识码：Ａ　中图分类号：ＴＰ３９３　基于在线负载预测的动态集群节能配置策略　刘斌　，杨坚　，赵宇　（１中国科学技术大学自动化系，合肥２３００２７；２．中国科学院上海微系统与信息技术研究所，上海２０００５０）　摘要：动态集群配置中的调节方式大多基于特定的物理实验模型而非数学模型描述。针对上述问题，提出基于预测的动态集群配置策略，　根据网络中服务请求的历史信息，采用最小均方误差预测未来时刻服务请求情况，根据负载请求与集群处理能力决定服务器规模的增减，　动态调节服务器集群中计算机的开启与关断。实验结果证明了该调度策略的可行性和优越性。　关链词：服务器集群；动态集群配置；预测算法；ＬＭＳ算法；节能　Ｄｙｎａｍｉｃ　Ｃｌｕｓｔｅｒ　Ｃｏｎｆｉｇｕｒａｔｉｏｎ　Ｓｔｒａｔｅｇｙ　ｆｏｒ　Ｅｎｅｒｇｙ　Ｃ０ｎｓｅｒｖａｔｉＯｎ　Ｂａｓｅｄ　ｏｎ　Ｏｎｌｉｎｅ　Ｌｏａｄ　Ｐｒｅｄｉｃｔｉｏｎ　ＬＩＵ　Ｂｉｎ　．ＹＡＮＧ　Ｊｉａｎ　．ＺＨＡＯ　Ｙｕ　（ｊ＿Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ａｕｔｏｍａｔｉｏｎ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　Ｃｈｉｎａ　Ｈｅｆｅｉ　２３００２７，Ｃｈｉｎａ：　２　Ｓｈａｎｇｈａｉ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｍｉｃｒｏ—ｓｙｓｔｅｍ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｓｈａｎｇｈａｉ　２０００５０，Ｃｈｉｎａ）　［Ａｂｓｔｒａｃｔ］Ｐｒｅｖｉｏｕｓ　ｄｙｎａｍｉｃ　ｃｌｕｓｔｅｒ　ｃｏｎｆｉｇｕｒａｔｉｏｎ　ｍｅｔｈｏｄｓ　ａｒｅ　ｂａｓｅｄ　０１１　ｔｈｅ　ｓｐｅｃｉｉｆｃ　ｐｈｙｓｉｃａｌ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｍｏｄｅｌｓ　ｗｉｔｈｏｕｔ　ｔｈｅ　ｄｅｓｃｒｉｐｔｉｏｎ　ｏｆ　ｍａｔｈｅｍａｔｉｃａｌ　ｍｏｄｅｌｓ．Ａｉｍｉｎｇ　ａｔ　ｔｈｅ　ｐｒｏｂｌｅｍ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｐｔｅｄｉｃｔｉｏｎ—ｂａｓｅｄ　ｄｙｎａｍｉｃ　ｃｌｕｓｔｅｒｓ　ｃｏｎｆｉｇｕｒａｔｉｏｎ　ｓｔｒａｔｅｇｙ，ｗｈｉｃｈ　ｕｓｅｓ　ｌｅａｓｔ　ｍｅａｎ　ｓｑｕａｒｅ　ｔｏ　ｐｒｅｄｉｃｔ　ｔｈｅ　ｓｉｔｕａｔｉｏｎ　ｏｆ　ｓｅｒｖｉｃｅ　ｒｅｑｕｅｓｔｓ　ｉｎ　ｔｈｅ　ｆｕｔｕｒｅ　ｔｉｍｅ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｎｅｔｗｏｒｋ　ｈｉｓｔｏｒｉｃａｌ　ｉｎ％ｒｍａｔｉｏｎ　ｏｆ　ｓｅｒｖｉｃｅ　ｒｅｑｕｅｓｔｓ．Ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ｔｈｅ　ｌｏａｄ　ｒｅｑｕｅｓｔｓ　ａｎｄ　ｔｈｅ　ｃｌｕｓｔｅｒｓ　ｐｒｏｃｅｓｓｉｎｇ　ｐｏｗｅｒ，ｉｔ　ｄｅｃｉｄｅｓ　ｔｈｅ　ｓｅｒｖｅｒｓ’ｓｃａｌｅ　ａｎｄ　ｄｙｎａｍｉｃａｌｌｙ　ａｄｊｕｓｔｓ　ｔｈｅ　ｏｐｅｎｉｎｇ　ａｎｄ　ｓｈｕｔｄｏｗｎ　ｏｆ　ｔｈｅ　ｃｏｍｐｕｔｅｒｓ　ｉｎ　ｔｈｅ　ｓｅｒｖｅｒ　ｃｌｕｓｔｅｒ．Ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔ　ｖｅｒｉｆｉｅｓ　ｔｈｅ　ｆｅａｓｉｂｉｌｉｔｙ　ａｎｄ　ｓｕｐｅｒｉｏｒｉｔｙ　ｏｆ　ｔｈｅ　ｓｃｈｅｄｕｌｅ　ｓｔｒａｔｅｇｙ．　［Ｋｅｙ　ｗｏｒｄｓｌ　ｓｅｒｖｅｒ　ｃｌｕｓｔｅｒ：ｄｙｎａｍｉｃ　ｃｌｕｓｔｅｒ　ｃｏｎｆｉｇｕｒａｔｉｏｎ；ｐｒｅｄｉｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ；ＬＭＳ　ａｌｇｏｒｉｔｈｍ：ｅｎｅｒｇｙ　ｃｏｎｓｅｒｖａｔｉｏｎ　１概述　动态集群配置策略的目的是在最小的系统功耗下实现最　优的服务性能，既做到集群的节能环保，又能保证系统的服　系统自上而下分为３层：最上层为用户层；中间层为调　度服务器（Ｓｃｈｅｄｕｌｉｎｇ　Ｓｅｔ‘ｖｅｒ，ＳＳ），由其判断及实施系统中服　务节点的加入或删除；最下层为服务节点层，包括活动节点　（Ａｃｔｉｖｅ　Ｎｏｄｅ，ＡＮ）和备用节点（Ｓｔａｎｄｂｙ　Ｎｏｄｅ，ＳＢＮ）。当系统中　活动节点的服务性能不能满足ＱｏＳ时，增加系统中活动节点　数，当系统中活动节点性能高于ＱｏＳ时，减少活动节点数，　以降低能耗。　务质量。在服务器集群层次上还没有成熟、通用的集群配置　方法，也没有准确的数学模型描述，很多研究人员通过物理　实验仿真现实网络环境中的集群”‘　，这种调节方式受物理实　验环境的影响很大，通用性不强。　本文提出一种基于负载在线预测的服务器规模调节策　本文的思想是：通过在线预测网络中服务请求的数量确　定集群中计算机开启、关断的数量，以达到节能的目的。这　里的关键问题是如何准确预测网络中的服务请求数并且及时　凋整集群规模。本文使用ＬＭＳ算法估计负载请求，根据系统　中服务请求与整个集群处理能力的关系，设定了３个集群规　模调整的判定区间，在这３个区问里分别增加、维持、减小　略，它可以根据网络中负载请求的波动情况，动态地开启、　关断集群中的服务节点。利用ＬＭＳ算法预测未来的负载请　求　，由此提出一个调整服务器规模的算法，并通过对应服　务请求的活动服务器节点数和服务拒绝率２个指标检验算法　性能。另外，本文设定集群中的服务器、服务请求均是同　构的。　当前服务器规模。由ｓｓ判定当前服务请求与集群处理能力处　于卜述哪个判定区间，进而决定如何调整服务节点。　２服务器集群系统模型　图１为网络中服务器集群系统的结构。　３动态集群配置算法　３．１　基于ＬＭＳ算法的负载在线预测策略　在实际系统中可以获得当前的服务请求数，但是必然存　基金项Ｈ：国家“８６３”计划基金资助项目（２００６ＡＡ０１Ｚ１１４）；国家　自然科学基金资助项目（６０８０２０３７）；新世纪优秀人才支持计划基金资　助项目（ＮＣＥ％０８—０５２２）；中科院优秀博士论文获得者启动基金资助　项目　作者简介：刘斌（１９８４－－Ｉ，男，硕士研究生，主研方向：服务器集群　节能，无线通信；杨图１集群系统结构　坚，副教授、博士；赵宇，副研究员　收稿丑期：２０１０．０６—２０　Ｅ—ｍａｉｌ：ｍｏｂｉｌｅｉｃｅ＠ｍａｉｌ．ｕｓｔｃ．ｅｄｕ．ｃｎ　９６一　在一个时延，再进行相关的配置凋　，时延将大大增加，这　会对服务质蕈造成重大的影响　为了解决这个问题，本文引　入了在线负载预测方法　０。　用ｘ（ｎ）表示ｔｌ时刻集群系统中的服务请求数，　．表示　Ｉ１时刻预测器的更新系数向　，　｛（ｏ（０）山ｆ１），…　一１）】　，　由一步Ｐ阶线性预测关系可得　。　：　，、　Ｅ　１　ｘ（ｎ＋】）＝　ｆ，Ｊ　（ｎ　（，　，）　（１ｊ　／＝ｌ　　Ｊ预测的误差函数为：　Ｐ（，！）＝　（Ｉ１＋ｌ　Ｊ一　（，ｚ＋１ｊ　（２）　ＬＭＳ算法利用误差函数进行反馈凋节，对系数向量ｒ，Ｊ，，　进行如下迭代更新：　（－０　Ｊ＝　十，ｕｅＯｚ）Ｘ（¨）　（３　Ｊ　其中，Ｘ　＝【　（”）　（ｆｆ＿１）．…，ｘ（ｎ—　）＋１）Ｊ　；』　是常数，其值决定了　权向量迭代步长的大小，对整个ＬＭＳ预测算法的收敛速度有　很大影响，　值取得太小，收敛速度很慢，取得太大，可能　使算法不收敛。ＬＭＳ是一种梯度搜索算法，预测系数向量　，　随时间变化，其自适应调节依赖于误差ｅｉｎ）的反馈。上述推　理表明，可以利用，　时刻之前一段时问的服务请求数　㈣，　ｉ＝ｎ－　＋１来预测｝ｆ十ｔ时刻的服务请求数　（舯１）。　３．２集群服务器调节算法　假设当前系统中有ｋ台服务器，每台服务器具有相同的　服务能力　即每个服务节点最多可以同时响应ｃ’个服务请　求，集群系统总体处理能力是　ｘｒｅｑ—ｌｌｌｔｎｌ　，表示在Ⅲ时刻　系统中的服务请求数，且：　ｒｅｑ一，ｚ“，ｎ　（川）　（４）　其中，．ｖ（，＂）可通过３　１节的预测算法得到。　本文把服务请求数ｒｅｑ一川　与ｋ—Ｊ台服务器的服务能力　（　一１）ｃ做比较，并引入一个集群处理能力裕量△ｆ。把集群总　体处理能力分为３个判定区问，由低到高分别是（Ｏ，（　—ｌ】（。）、　Ｉ（　一１　ｔｋ一１）ｃ＋Ａｃ）及Ｉ（　一１）ｃ＋Ａｃ．＋。ｃ），在这３个判定区间　分　别减小、维持、增加服务器规模。　在ｍ时刻，新节点开启或关断的判定算法如下：　当ｒｅｑ一，ｌ　Ｌｔｌｌｌ　≥（　一１　Ｊ（‘＋Ａｃ时，表明系统中负载数量已经超　过当前系统中服务　点的处理能力，需要增加服务器规模。　当（ｋ—Ｊ）ｃ≤　ｇ—ＩｌｌｌｌＨ　＜（　一Ｊ）ｒ＋Ａｃ时，表明系统中负载数量　在当前系统中节点的处理能力内，不需要增减服务器规模。　当ｒｅｑ—ｉｌｌｌｍ　＜（ｋ一１）ｃ。时，表明系统中负载数量低于当前系　统中节点的处理能力，应当减小服务器规模，以减少不必要　的功耗。　综上，服务器规模判定方法如下：　ｆｋ十Ｉ　ｉｆ　ｅｑ—ｔｌｌｉ！”　｝（　一１）（＋△（　｛ｊ　ｉ　‘　一　Ｊ‘　＼　（／……　＜（　一。）　’十△　‘　Ｊ　Ｉｋ一１　ｉｆ　ｉ＇ｅｑ一，！ｊ１１１ｌ　＜（Ａ—Ｊ】［’　其中，ｋ表示当前系统一÷｝＿Ｉ服务节点的数量；ｃ’表示每个服务节　点的处理能力；ｒｅｑ—ｌｌｌＩＨ１　表示Ⅲ时刻系统中负载的数量；　Ａｃ＝ｑｃ，表示服务器集群的处理能力裕量，０＜　＜１，『７为裕量　参数。本文称式（５）的调节算法为慢速调整算法。　在负载请求急剧变化的网络环境中，式ｔ５）的调整算法调　节作用有些滞后。在短时间内有大量负载请求到达系统的情　况下，节点逐个增加不能满足服务要求，此时可以采｝｝ｊ同时　增加多台服务器的方式更快速地增ＪＪｆＩ服务器规模。同理，在　短时间内有大量负载离开系统的情况下，可以采取同时减少　多台服务器的方法避免大量活动节点处于空闲状态，减少不　必要的能耗。而同时增减活动节点的数目可以根据当前系统　ｑｊ服务请求来决定。　本文对式ｆ５　Ｊ的算法进行如Ｆ改进：　ｆｔ十　ｉｆ　ｒｅｑｚｔⅢｆ，”≥（　—Ｉ）（－｝△（・　矗＝｛ｋ　ｉｆ（七一Ｊ）　≤ｒｅｑ　川　，盯　＜（止一１）　十△ｆ　（６）　ｌ　ｋｉｆ，．ｅｑｔｌｌｌｌｌｌ　＜（　一）ｆ　其中，￣＝ｒｅｑ一１ｌｉ１１１１　，（（　一１）Ｈ△　，　称为白适应递增　子，用　来快速增加集群规模；　＝（女一１）（－／ｒｅｑ—ＩＩ　ＬＩｌ￣ｌ　，ｆ７称为自适应递减　子，用来快速减小服务器规模。　该算法可以根据系统负载和集群处理能力动态地调整服　务器规模增减的幅度，使系统规模的调整更灵活、快速。本　文称式（６）所示算法为快速调整算法。　另外，定义『７１时刻服务拒绝率的ｉ｛‘算表达式为：　，　ｉ＇ａ［ｅ　＝，’　’ｎ　ｆⅢ　／ｒｅｑ一，？￡Ｉｉｌｌ　（７）　其中，，　ｌｌｌｔｍ　表示ｍ时刻在集群调整时被拒绝的服务数；　，ｅＬ—　表示某时刻系统中的实时拒绝率，由其可以对比快、　慢２种调整算法的优缺点。实验中的平均拒绝率即系统总体　的拒绝率，它涔现算法的总体性能，表征调整算法的可靠性。　４仿真实验　４．１基于ＬＭＳ算法的在线负裁预测　ＬＭＳ算法不受服务请求模型的限制，本仿真实验设定：　在ｆＯ，　Ｊ时间内负载请求到达的总数Ｍ，），ｆ≥０是一个服从平均　纠达率为ｌ的Ｐｏｉｓｓｏｎ过程，服务请求在系统中的停留时问服　从均值为　的指数分布。实验仿真数据如表ｊ所示。　表ｌ　实验仿真模型及参数　４．２慢速调整算法的仿真　如图２所示，左边纵坐标表示对应各时刻集群中开启的　服务节点数，右边纵坐标表示对应各时刻集群中的服务请求　数。住图３中，左边纵坐标表示对应各时刻的服务拒绝率。　从图中叮以看出，集群规模随着服务请求的增加（减少）而增　加ｆ减少１。实验中设置集群的调整时间为１２０　ｓ，每隔１２０　Ｓ，　ｓｓ汁算集群中服务请求数，再根据慢速算法，对服务器规模　进行调整。图３表示请求拒绝率及服务请求与服务时间的对　应关系，服务拒绝率町由式（７）求出。　鼎　蛭　蠊　嵫　仿真刚州　图２　慢速调整算法开启的服务器节点与服务请求的关系　＊　磐　摩　图３慢速调整算法服务拒绝率与服务请求的关系　出于节能的考虑，当集群中服务请求较少时，大量的服　务节点处于等待状态。负载请求大量增加时，ｓｓ及时增加集　群规模，但服务节点的启动需要一个时延△ｆ，在△　时间里　到达的服务请求由于超过系统的服务能力而被拒绝。从图中　可见，当服务请求大量增加时，系统的拒绝率较高，这是因　为负载大量增加，要求服务器规模大量增加，在大量服务器　启动的过程中会拒绝更多的服务请求；当服务请求大量离开　系统时，系统的拒绝率基本为０，这是由本文算法的保守性　决定的。由ｒｅｑ—ｎｕｍ　＜（　一１）ｃ可以看出，只有当服务请求低于　一个阀值时，ｓｓ才会减少服务节点数，以尽可能地保证服务　质量，但是系统的能耗会增加。　４．３快速调整算法的仿真　从图３、图４可以看出，短时间内大量请求到达系统时，　直到大约第２　０００　Ｓ，服务节点的调节才达到稳定。在此期问，　大量请求由于集群服务能力不足而被拒绝。在较长一段时问　内服务拒绝率在０．４％左右，系统的平均拒绝率为　９．９１９　３ｘ１０。大量服务请求突然离开集群时，ｓｓ不能及时减　ｄ，Ｎ务器规模，造成不必要的能耗增加。为了提高集群的调　整速度、降低拒绝率，本文引入　和Ｏ－，使算法可以根据系　统中负载请求自动调节服务器增减幅度。　图４、图５为相应的快速调整算法仿真结果。　图４快速调整算法开启的服务器节点与服务请求的关系　图５快速调整算法服务拒绝率与服务请求的关系　从图４、图５可以看出，当系统中有大量服务请求到达　时，使用快速算法集群的调整时间仅为２００　Ｓ左右，是慢速　算法的１／１０；当大量服务请求离开系统时，快速算法也能够　很好地跟踪服务离开情况，及时地减小服务器规模。系统拒　绝率在较长时问内维持在０．２％左右，其平均拒绝率为　８．１０４　２ｘ１０～。由此可见，在ＡＮ数目、服务拒绝率上，快速　调整算法的效果好于慢速调整算法。　５结束语　ＬＭＳ算法的应用不需要特定的服务请求模型，通用性很　强，仿真结果证明，预测的结果与理论值的误差较小。本文　提出了集群规模调整的快速算法和慢速算法。实验结果证明，　这２种调整算法均能根据网络中的请求情况很好地调整集群　规模，一方面保证了较好的服务质量，另一方面使系统的能　耗维持在较低的水平。慢速调整算法的调节作用有些滞后，　导致服务拒绝率较高。快速调整算法对系统负载的跟踪效果　较好，即时性更好，能够更快、更灵活地调整集群的配置。　参考文献　【１］Ｔｓａｉ　Ｃｈａｎｇ—Ｈａｏ，Ｓｈｉｎ　Ｋ　Ｇ　Ｒｅｕｍａｎｎ　Ｊ，ｅｔ　ａ１．Ｏｎｌｉｎｅ　Ｗｅｂ　Ｃｌｕｓｔｅｒ　Ｃａｐａｃｉｔｙ　Ｅｓｔｉｍａｔｉｏｎ　ａｎｄ　Ｉｔｓ　Ａｐｐｌｉｃａｔｉｏｎ　ｔＯ　Ｅｎｅｒｇｙ　Ｃｏｎｓｅｒｖａｔｉｏｎ［Ｊ】　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｓｙｓｔｅｍｓ，２００７，　ｌ　８ｆ７１：９３２—９４５．　［２】Ｈｅａｔｈ　Ｌ　Ｄｉｎｉｚ　Ｂ，Ｃａｒｒｅｒａ　Ｅ　Ｖ．ｅｔ　ａ１．Ｅｎｅｒｇｙ　Ｃｏｎｓｅｒｖａｔｉｏｎ　ｉｎ　Ｈｅｔｅ　ｒ（１ｇｅｎｅｏｕｓ　Ｓｅｒｖｅｒ　Ｃｌｕｓｔｅｒｓ［Ｃ］／／Ｐｒｏｃ．ｏｆ　ＡＣＭ　ＳＩＧＰＬＡＮ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｐｒｉｎｃｉｐｌｅｓ　ａｎｄ　Ｐａｒａｌｌｅｌ　Ｐｒｏｇｒａｍｍｉｎｇ．［Ｓ．１．］：ＡＣＭ　Ｐｒｅｓｓ．２００５：１８６一ｌ９５．　ｆ３】Ｅｇｙｈａｚｙ　Ｍ　ｗ，Ｌｉａｎｇ　Ｙａｏ．Ｐｒｅｄｉｃｔｅｄ　Ｓｕｍ：Ａ　Ｒｏｂｕｓｔ　Ｍｅａｓｕｒｅ—　ｂａｓｅｄ　Ａｄｍｉｓｓｉｏｎ　Ｃｏｎｔｒｏｌ　ｗｉｔｈ　Ｏｎｌｉｎｅ　Ｔｒａｆｉｆｃ　Ｐｒｅｄｉｃｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｌｅｔｔｅｒｓ，２００７，１　ｌ（７）：２０４—２０６．　高文字，李绍华．基于ＬＭＳ的网络流量预测　现代计算机，　２００８．ｆ１２　：７８—８１．　［５】倪锦根，李锋．变步长ＮＬＭＳ自适应滤波算法研究…．计算　机应用与软件，２００９，２６（１）：２４８—２５０．　［６】王心一，沈庭芝，王晓华，数字可视电话系统中的Ｇ．１６８回声消　除技术［Ｊ１．计算机工程，２００８，３４（１　５）：２５０—２５２．　编辑张帆