基于时间序列预测的动态负载均衡算法


基于时间序列预测的动态负载均衡算法 1 问题的提出 数据流计算 [1]是处理多信息源数据以实现实时计算,这类 信息包括:内存数据、传感器数据、Web 页面点击数据、IP 日志 等。 随着 Internet 不断发展,用户数量及网站访问量呈爆炸式增 长,服务器的处理能力和强度也相应增大,在这背景下,分布式 数据流处理已成为一大研究热点。 而传统的数据流计算已无法 满足高计算资源利用率、低集群耗电量的要求,应此高并发的分 布式环境下的资源调度就显得尤为重要。 负载均衡算法正因为能解决上诉问题, 在高性能、 高响应 比、低延迟的集群环境中被广泛应用。 常见的负载均衡算法有静 态加权轮转法(WRR)、基于请求数量的加权最小连接数优先法 (WLC)、基于响应时间的动态加权轮转法(DWRR)、临界加速递 减法(MDC)等,相比之下,本文提出一种基于时间序列预测的动 态负载均衡算法,在资源利用效率上具有明显的优势。 2 算法的设计与实现 本文根据两种信息决定节点分配策略。 一种是 2.2 中所述 的时间序列预测算法预测的输入数据, 另一种是从所有计算节 点中获得的滞后时间数据。 基于上述信息,节点分配组件最终决 定是否将每个节点分配到数据流处理或批量处理。 在基于数据输入速率的调整策略中, 首先用时间序列预测 算法预测数据输入率, 然后由预测得到的数据输入率除以单一 节点可处理的数据量决定最优的节点数。 为了减少转换计算节 点产出的额外成本, 同时避免可能因为预测算法得到的奇异值 而导致节点的资源过载, 我们的调度策略允许立即添加某个单 一节点。 每次数据输入率刷新时,节点分配都要被重新计算。 通过实时监控所有计算节点的延迟, 实时调整节点的分配。 但是,只有当延迟超过阈值时,这种策略才会生效。 如果超过阈值 的情况多次发生,节点分配组件将会忽略数据输入率,立即添加 一个额外的计算机节点。 我们约定将一个周期中延迟超过阈值的 计数称之为“超阈计数”,更改节点分配时,将重置超阈计数。 本文算法中,将超阈计数设置为 40,如果超阈计数太小或 延迟阈值太低,额外添加的节点数将会膨胀。 此外,我们在头节点中运行动态负载均衡组件,相比其他节 点处理往往可能过载或者滞后时间往往较高。 如果我们的算法 检测到头节点滞后时间接近临界值, 系统将控制头节点停止处 理传入的数据。 2.1 动态负载均衡算法 动态负载均衡算法决定了数据在各个节点的分配比例,这 个分配比例又有两个维度的参数决定: pj r :在第 r 个节点、第 j 个 tp 周期的分配比例 ε:节点增益 提出资源利用率的目的在于对空闲节点 br 采取惩罚机制, 得到表达式如下: ε=(1-lpj r )k 参数 k 表征惩罚的强弱程度,当 k=0 时,每个节点的增益 于 1,空闲率将不会影响下一次分配的效率;当 k=1 时,节点将 正比于资源利用率;当取极值时,ε 将成为很小的值,输入绝大 部分将分配到空闲率高的节点处理。 当输入相对稳定时,频率地调节节点资源分配比率将对整 个系统造成一些不良影响,如计算处理成本增加、计算延迟增大 等。 因为,本算法设置了路径空闲率的阀值 thres,当节点 br 的 预测是 lpr j 大于阀值时,该节点才被称为休眠节点。 如果没有任 何节点成为休眠节点, 则负载均衡组件将不会触发重新调整资 源分配比例的计算。 在某个周期内的分配算法详细过程如下: 1)初始状态时,每个节点的分配比例相等; 2)在预测周 期 j-1 时,每个节点的分配比例为邀pj-1 1 ,pj-1 2 , …,pj-1 r ,…妖,预测的空闲率为邀lpj 1 ,lpj 2 ,…,lpj r ,…妖; 3)对所有节点进行分析,若 lpj r <thres,则 j 周期的分配比例 与上一周期 j-1 相同; 4)若存在至少一个节点 lpj r ≥thres 的情况,则分配比例将 顾 伟 张云华 (浙江理工大学信息学院,浙江 杭州 310018) Dynamic Load Balancing Algorithm Using Time Series Prediction 摘 要 在分布式数据流计算系统中,负载均衡是必须解决的关键问题之一。 为了追求高资源利用率同时又保持接近临界值的 延迟时间,提出一种基于时间序列预测的动态负载均衡算法,算法根据时间序列预测算法预测的输入数据以及历史的延迟 时间数据,动态确定计算节点个数。 经性能测试表明,该算法在资源利用效率上具有明显的优势。 关键词:分布式数据流计算,负载均衡,时间序列预测 Abstract In the distributed data stream processing system,the load balance is one of the key problems that must be solved.In order to pursue the high resource utilization at the same time,keep close to the critical value of the delay time,this paper proposes a kind of based on time series prediction of the dynamic load balancing algorithm,the algorithm based on time series prediction algorithm forecast of input data and history of the delay time data,dynamic calculation to determine the number of the nodes.The performance test show that the algorithm has obvious advantages in the resources use efficiency. Keywords:data stream processing,dynamic load balancing,time series prediction 基于时间序列预测的动态负载均衡算法86 《工业控制计算机》2012 年第 25 卷第 12 期 按如下公式进行重新调节: pj r = pj-1 r ×εi-1 r n r = 1 Σpj-1 r ×εi-1 r εi-1 r =(1-lpj-1 r )k 且 pj 1 +pj 2 +…+pj r …=1 2.2 时间序列预测算法 定义 1 设邀Xt妖是时间序列,如果对于任意 N 个时刻 t1,t2,t3, t4,…序列邀Xt妖的分布函数满足 D 如下等式: D(x1 ,x2 ,x3 ,x4 ,…,xN ,t1 ,t2 ,t3 ,t4 ,…,tN )=D(x1 ,x2 ,x3 ,x4 ,…,x N ,t1+k ,t2+k ,t3+k ,t4+k ,…,tN+k ) 其中,k 为实数,N 为自然数,则称邀Xt妖为严平稳时间序列。 定义 2 设邀Xt妖是时间序列,如果序列邀Xt妖的均值为常数,自协 方差函数只是与时间间隔相关,而与具体时间点不相关,则称时 间序列邀Xt妖为宽平稳时间序列。 由上述定义可以看出, 宽平稳时间序列只要求随着时间的 不断变化,序列的一阶矩不变,二阶矩只与时间间隔有关,要求 满足的条件比严平稳序列有所放松。 自相关函数体现了序列中前后时刻值之间的依存关系,而 这种关系也可以通过使用自回归模型(AR)来表示。 自回归模型 其实是回归模型的延伸, 回归模型描述的是同一时刻的变量之 间的关系,是一个静态模型,而自回归模型描述了一个变量在不 同时刻的值之间存在的关系,是个动态模型。 如果一个时间序列邀Xt妖可以由如下公式描述: Xt =μ1 Xt-1 +μ2 Xt-2 +…+μn Xt-n +at (1) 并且 Xt 只是跟 Xt-1,Xt-2,…,Xt-n 相关,Xt 与 Xt-(n+1),Xt-(n+2),… 不相关,at 为白噪声序列,则称时间序列邀Xt妖可以用 n 阶自回归 模型来描述,即可以用 AR(n)模型描述。其中,μ1,μ2,…,μn 称为 自相关系数。 由公式(1)可以看出,对于满足一阶自回归模型的时间序 列, 当前时刻序列值只是跟其以前时刻序列值和当前时刻噪声 有关,而与以前时刻噪声无关。 将公式(1)进行简单变换,得到如 下公式: at =Xt -μ1 Xt-1 -μ2 Xt-2 -…-μn Xt-n (2) 可以通过公式(2)将原来的时间序列转化为白噪声[3]序列 邀at妖,这样就可以求出各时刻的噪声值。 经第 3 节算法性能测试得出,AR(n)[4]模型能满足我们的 需要。 3 算法性能测试 根据实验室现有条件,对负载均衡算法进行了性能测试。 3.1 测试环境 用 VMware 构建虚拟机集群,测试环境如下: 10 台虚拟机作为计算节点,配置为 CPU:2.66GHz,内存:512M, 操 作 系 统 Red Hat Linux 4.0 Enterprise,IP:192.168.1.100~ 192.168.1.110; 2 台虚拟机作为管理节点,配置为 CPU:2.66GHz,内存:1G, 操 作 系 统 Red Hat Linux 4.0 Enterprise,IP:192.168.1.10 ~ 192.168.1.11; 本文通过运行一个基于日志的 Web 打点分析程序,对总量 为 200G 大小的 20000 个日志文件进行处理,实时记录 CPU 使 用率 (本测试中为已分配的计算节点 CPU 利用率的加权平均 数)、处理延迟(本测试中为从管理节点分配到成功处理完成的 时间)、节点分配信息。 3.2 测试结果 我们的分配策略相比其他算法 CPU 利用率最高,而且仍能 保持低延迟时间。 表 1 各个分配策略性能结果对比 图 1 显示的是程序执行期间, 本文的动态负载均衡算法实 际分配的平均计算节点个数,最后算法为追求各节点的高 CPU 利用率,节点个数趋于稳定。 图 1 运行期间节点分配情况 参考文献 [1]Daniel J Abadi,Yanif Ahmad,Magdalena Balazinska,Ugur Cetintemel, Mitch Cherniack,Jeong -Hyon Hwang,Wolfgang Lindner,Anurag S Maskey,Alexander Rasin,Esther Ryvkina, Nesime Tatbul,Ying Xing and Stan Zdonik, The Design of the Borealis Stream Processing Engine, CIDR 2005 [2]Yang Wei, Zurbenko Igor. Nonstationarity[J]. Wiley Interdisci- plinary Reviews:Computational Statistics, 2010, 2(1): 107-115 [3]潘红宇.时间序列分析[M].北京:对外经济贸易大学出版社,2006: 69-71 [4]安鸿志.时间序列分析[M].北京:科学出版社,1992:1-344 [收稿日期:2012.10.22] 87
还剩1页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 1 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf