服务器集群负载均衡技术研究及算法比较


计 算 机 与 现 代 化 2009年第 8期 JISUANJI YU XIANDA IHUA 总第 168期 文章编号: 1006-2475( 2009) 08-0007-04 收稿日期: 2008-08-13 作者简介: 李坤 ( 1985-), 女, 陕西西安人, 西安电子科技大学计算机学院硕士研究生, 研究方向: 计算机网络与信息处理; 王 百杰 ( 1984-) , 男, 山东菏泽人, 硕士研究生, 研究方向: 盲源分离, 统计信号处理, 计算机网络。 服务器集群负载均衡技术研究及算法比较 李 坤, 王百杰 (西安电子科技大学计算机学院, 陕西 西安 710071) 摘要: 简要介绍了负载均衡技术的分类及其发展, 重点介绍了服务器集群负载均衡技术及应用。并对评价负载均衡优劣 的重要标准之一 负载均衡算法的种类做了详细介绍及优缺点比较。对近年来一些新的负载均衡算法做了介绍。最 后, 对服务器集群负载均衡技术的发展前景做出了展望和预测。 关键词: 服务器集群; 负载均衡; 负载均衡算法 中图分类号: TP301. 6 文献标识码: A do:i 10. 3969 / .j issn. 1006-2475. 2009. 08. 003 Research on Load Balancing ofW eb-server System and Com parison of A lgorithm s LIKun, WANG Ba-i jie ( School of Com puter Science, X idian University, X i an 710071, Ch ina) Abstract: This paper sim ply introduces the types of load balancing strategy, and m ainly describes the concept of load balancing of W eb-server system. It also includes a detailed presentation of the algorithm s of load balancing, w hich is a key point of judging load balancing strategy, and a com parison of these algorithm s. Besides, an introduction of som e new load balancing algorithm s is presented in the paper. A t the end of th is paper, the prospect of load balancing on W eb-server system is show ed. Key w ords: W eb-server system; load balancing; load balancing algorithm s 0 引 言 随着 In ternet不断发展的应用需求, 网络信息资 源的日益丰富, 用户数量及对网络访问量呈爆炸式增 长, 网络核心设备的处理能力和计算强度也相应增 大, 给传统的单一网络设备带来沉重的压力。而仅依 靠硬件升级会造成大量的资源浪费、随着业务量的不 断提升使设备陷入不断循环的硬件升级, 最重要的是 性能再卓越的设备也并不一定能满足当前业务量的 需求, 于是多设备的集群系统由于其高性能、低价格、 可扩展性强等特点, 正被得到广泛使用。如何在处理 能力相当的多台网络设备之间进行合理的业务量分 配, 使得集群系统不至于出现一部分设备过忙而另一 部分设备却未充分发挥处理能力的情况, 就成为一个 急需解决的问题, 这样, 负载均衡机制应运而生。 本文主要对服务器集群的负载均衡机制进行研 究, 并对负载均衡的重要因素 均衡算法进行详细 介绍和比较。 1 负载均衡的分类 负载均衡建立在现有网络结构上, 提供一种廉 价、有效、透明的方法扩展网络设备和服务器带宽、增 加吞吐量、加强网络数据处理能力、提高网络的灵活 性和可靠性。服务器集群负载均衡指服务器群中所 有服务器和应用程序之间流量负载的应用。负载均 衡技术除了可根据使用设备分为软件负载均衡和硬 件负载均衡以外还有其它分法, 下面分别从不同的应 用需求对现有集群负载均衡技术进行分类。 1. 1 根据应用的地理结构分类 ( 1)本地负载均衡。 本地负载均衡是指对本地的服务器群做负载均 衡, 充分利用现有设备, 避免服务器单点故障造成数 据流量的损失。其有灵活多样的均衡策略把数据流 量合理地分配给服务器群内的服务器共同负担。即 8 计 算 机 与 现 代 化 2009年第 8期 使是再给现有服务器扩充升级, 也只是简单地增加一 个新的服务器到服务群中, 而不需改变现有网络结 构、停止现有的服务。 ( 2)全局负载均衡。 全局负载均衡是指对分别放置在不同的地理位 置、有不同网络结构的服务器群间作负载均衡。全局 负载均衡主要用于在一个多区域拥有自己服务器的 站点, 为了使全球用户只以一个 IP地址或域名就能 访问到离自己最近的服务器, 从而获得最快的访问速 度, 也可用于子公司分散站点分布广的大公司通过 Intranet(企业内部互联网 )来达到资源统一合理分配 的目的。 1. 2 根据应用的网络层次 ( OSI参考模型 ) ( 1)链路聚合技术 (第二层负载均衡 )。 链路聚合技术将多条物理链路当作一条单一的 聚合逻辑链路使用, 网络数据流量由聚合逻辑链路中 所有物理链路共同承担, 由此在逻辑上增大了链路的 容量, 使其能满足带宽增加的需求。 ( 2)现代负载均衡技术。 现代负载均衡技术通常操作于网络的第四层或 第七层。第四层负载均衡将一个 Internet上合法注册 的 IP地址映射为多个内部服务器的 IP地址, 对每次 TCP连接请求动态使用其中一个内部 IP地址。在第 四层交换机中, 根据源端和目的 IP地址、TCP或 UDP 端口号和一定的负载均衡策略, 在服务器 IP 和 V IP 间进行映射。 第七层负载均衡控制应用层服务的内容, 提供了 一种对访问流量的高层控制方式, 通过检查流经的 HTTP报头, 根据报头内的信息来执行负载均衡任 务。第七层负载均衡受到其所支持的协议限制 (一 般只有 HTTP), 并且检查 HTTP报头会占用大量的系 统资源, 在大量连接请求的情况下, 负载均衡设备自 身容易成为网络整体性能的瓶颈。 2 常用的负载均衡算法 影响负载均衡有 3个关键因素, 分别是负载均衡 算法、网络拓扑和负载均衡的粒度, 本文中主要讨论 算法。负载均衡算法从大体上可分为无状态调度和 有状态调度两种, 无状态调度是指不考虑当前所有连 接状态及各节点之间当前的负载情况。 2. 1 无状态调度 ( 1)轮循算法 ( Round Rob in)。 将来自网络中的请求按顺序依次分配给集群中 的每台服务器, 如图 1所示。 图 1 轮循算法 从图 1 中可以看出轮循算法的明显优点是简单 易实现。但其缺点也是显而易见的, 由于集群中服务 器的处理能力各不相同, 这种绝对公平的算法会使处 理能力强的服务器得不到充分利用, 而处理能力较弱 的服务器任务堆积, 严重的可能造成个别服务器瘫 痪。所以轮循算法适合在各个服务器处理能力相当 且网络中请求相对均衡的情况下使用。 ( 2)带有权重的轮循算法 (W eighted Round Robin)。 带有权重的轮循算法是在轮循算法的基础上为 每台服务器增加了一个权值, 这个权值表示的是服务 器的处理能力。分配任务的时候就可以依照权值的 不同轮循为每台服务器分配不同数量的任务。如图 2所示, 服务器 1、2、3、4的权值为 2: 1: 1: 1, 所以在轮 循时服务器 1的任务分配量即为另外 3台服务器的 两倍。 图 2 带权重的轮循算法 从图 2中易得, 该算法改进了轮循算法的弱点, 保证了处理能力强的服务器可以得到更多的连接任 2009年第 8期 李坤等: 服务器集群负载均衡技术研究及算法比较 9 务, 从一定程度上避免了出现处理能力低的服务器由 于任务堆积而瘫痪的情况。但该算法没有考虑处理 请求的时间变化, 可能导致服务器间负载的不均衡。 2. 2 有状态调度 上述无状态调度可能造成集群间负载不均衡甚 至单台故障。为了克服这个缺陷, 有状态调度算法使 用一张表记录当前所有连接情况, 按照一定规则分配 任务。 ( 1)最小连接数 ( Least Connection)。 最小连接数算法使用一张表记录当前每台服务 器的连接数, 新的服务请求将被分配到当前连接数最 少的服务器上。如图 3所示, 当新请求到达时, 根据 表中记录的连接数分配至 3号服务器。 图 3 最小连接数算法 由于充分考虑当前每台服务器的连接情况, 最小 连接数算法能把请求平滑分配到各个服务器上, 实现 连接数量的负载均衡。但是要考虑 TCP连接的响应 时间, 当服务器处理能力不相同时, 可能出现处理能 力不等的服务器的负载不均衡现象。 ( 2)带权重的最小连接数 (W eighted Least Con- nection)。 该算法是对最小连接数算法的改进, 每台服务器 用一个权值来表示其处理能力, 在调度请求时应尽可 能地使服务器的连接数与其权值成比例。服务器群 1、2、3、4的权值比例为 2: 1: 1: 1, 当前连接数如下所 示, 请求调度如图 4所示。 与带权重的轮循算法相同, 服务器的权值代表了 服务器的处理能力, 但是在实际应用中, 权值的设置 与很多因素相关, 仅仅靠经验确定会带来很大误差。 图 4 带权重的最小连接数算法 ( 3)最快响应速度 ( Fastest)。 最快响应速度算法记录每台服务器的请求连接 响应时间, 当新请求到来时, 分配至响应时间最短的 服务器上, 使其能最快获得处理, 如图 5所示。 图 5 最快响应速度算法 最快响应速度算法确保了最短的服务器响应时 间, 使任务能很快得到分配处理, 而不会因为响应时 间过长使任务延时。此种均衡算法能较好地反映服 务器的当前运行状态, 但最快响应时间仅仅指的是负 载均衡设备与服务器间的最快响应时间, 而不是客户 端与服务器间的最快响应时间。 3 新的负载均衡算法 从文中研究可得, 动态调度由于考虑到服务器的 负载和自身处理能力, 比静态调度优越, 可是仍存在 一定问题, 比如: 由于各个连接请求不同, 当前连接数 并不能真实反映服务节点的负载情况; 由于响应时间 的不同, 负载均衡器对各节点连接数的记录与节点真 实的连接数量之前可能会存在误差; 随着并发连接数 10 计 算 机 与 现 代 化 2009年第 8期 量的增加, 负载均衡器本身可能成为服务的瓶颈。 近年来, 新的、更有效的负载均衡算法已成为国 内外研究机构的研究热点之一, 本文对其中一些研究 成形并证明有效的算法加以概要介绍。 3. 1 基于多参数的负载均衡算法 文献 [ 8]提出了一种基于多参数的负载均衡算 法, 与传统算法只考虑 CPU 排队情况不同, 该算法基 于分布式服务器集群, 其中每个节点使用了一些不同 的参数, 如 CPU 负载、网络负载以及内存使用。根据 当前负载情况把节点分为 4个等级: 空置 ( idle)、闲 ( low )、中等 ( normal)和忙 ( h igh)。对每个节点来说, CPU 利用率 ( cpu- u), CPU 队列长度 ( nr), 内存利用 率 ( mem- u)和网络负载 ( net- u)都要被考虑到, 用 来决定该节点是处于 4个等级中的哪一个。 当有新请求到来时, 如果当前节点空置, 则由当 前节点接收并处理请求。下一个选择是其它任何一 个空置的节点。如果当前节点处于忙的状态, 下一个 选择是一个低负载的节点。如果上述条件没有选择 出来一个节点, 这个请求将由当前节点接收。 文献 [ 8]经过测试得到, 文中算法的总体性能比 单纯基于 CPU队列长度的算法优越 43. 5%。仅仅在 三个参数, CPU 利用率、网络负载和内存利用率都很 低的情况下基于 CPU 队列长度的算法才优于文中提 出的算法。当网络中有较大负载和 /或者内存使用较 大时, 文中提出的算法有较好的性能。 3. 2 基于内容请求的负载均衡算法 文献 [ 9 ] 提出的 LARD ( Locality-Aw are R equest D istribution)是一种基于内容请求的负载均衡算法, 该算法中, 所有的服务器被认为配置及处理能力相 当, 唯一不同的是各个节点的当前负载状况。 图 6 LARD算法 如图 6所示, 前端分配器根据用户请求的 URL 解析出具体的服务类型, 按照规则选择最近的服务节 点接收请求。算法定义了两个阈值作为衡量节点空 闲与否的标准, T low (当前活跃的连接数 ) 和 Th igh, 当 节点负载低于 T low时, 认为节点空闲可以接收新的请 求; 当节点负载高于 Th igh时, 则认为当前节点忙并可 能引起延时及拥塞, 于是该节点在当前时刻不接收新 的连接请求。 由分析可得, 基于内容识别的负载均衡算法是一 种细粒度的算法, 能有效提高集群的性能。经过测 试, 文献 [ 9]得出 LARD在 CPU 及磁盘速度方面都比 带权值的轮循算法 (W RR )优越。 3. 3 基于遗传算法的负载均衡策略 遗传算法是一种基于遗传和基因的搜索算法, 通 过对问题的求解对象过去和现在的变化, 最终求得问 题的最优解。文献 [ 11]提出的遗传算法用于动态负 载均衡策略中时, W eb服务器负载均衡可以描述为: 有 N 个新到的任务分到 M 个服务器节点, 各服务器 负载状况不同, 目标是要找到一个最优的调度方法, 使得整个任务处理的时间最短。 设服务器节点 i所分配的任务数为 ki, 则整个分 配方案的基因编码为: k1, k2, k3, , kM。按照随机的 方式产生初始种群。文献 [ 11]中以节点处理请求的 时间的倒数作为适应度, 选取个体进行复制。即对以 概率被选中的分配方案中的两个服务器上分配的任 务数进行交叉操作, 从而产生新的分配方案。在选中 的个体内, 任意选取个体的两个各不相同字符, 对其 有效位进行交换操作, 产生新的个体。由于遗传算法 本身是一种反复迭代的搜索算法, 必须确立一个收敛 条件保证算法及时终止。文献 [ 11]预先设定一个最 大的繁殖代数 Nmax。 经过测试可得, 文献 [ 11]提出的基于遗传算法 的负载均衡策略使得各个服务器节点的 CPU 利用率 相对均衡, 在客户机任务请求数量大的情况下, 这个 优势会明显地表现出来。 3. 4 基于动态反馈的负载均衡算法 文献 [ 12]提出了一种透明动态反馈负载均衡技 术, 该算法引入一个负载冗余, 既考虑服务器节点的剩 余节点处理能力, 又考虑各个后台服务器的当前实际 负载, 还考虑了在某个时间段之间负载均衡。系统采 用一个主 L inux服务器 ( L inux V irtual Server, LVS)与 每一个服务器节点建立长期稳定的 TCP连接, 并维护 着一张记录各节点负载信息表。LVS除了具有客户请 求队列外, 还有负载信息和冗余信息两个队列, 前者按 各服务器节点的负载轻重, 降序存放各服务器节点号 ( ID)和权值 W i; 后者用来存放两个时间片之间的某个 时刻来了新任务请求后, 按各个服务器节点负载冗余 量 Di 降序排列服务器节点号和对应的负载冗余量, 便 于算法动态调整在两个时间片之间新来任务请求的分 配和各个服务器节点的负载均衡性。该算法综合 CPU 负载、内存负载及 I/O 使用率得到节点的真实负载 Bi real。反馈调节根据节点的负载情况及反馈进行负载 调节, 提高集群利用率。 (下转第 15页 ) 2009年第 8期 秦亮等: 软件可靠性 J-M 模型的特性分析 15 了数值实验证明了模型方程解的有效性与正确性。 但是, 上述方法还存在一些不足, 模型应用的通用性 还不是很强, 解的精度仍有待提高, 这都是在以后工 作中要继续努力解决的地方。 参考文献: [ 1] 徐仁佐, 郑人杰. 软件可靠性模型与应用 [ M ]. 北京: 清 华大学出版社, 1994: 8-9. [ 2 ] Lyu M R. H andbook of Software Reliability Engineering [M ]. M c Graw-H il,l 1996. [ 3] 蔡开元. 软件可靠性工程基础 [ M ]. 北京: 清华大学出版 社, 1995: 53-54. [ 4] 黄锡滋. 软件可靠性、安全性与质量保证 [ M ]. 北京: 电 子工业出版社, 2002: 36. [ 5] 陆民燕. 软件可靠性参数研究 [ J]. 北京航空航天大学 学报, 2001, 27( 2) : 241-244. [ 6] Jelinsk i Z, Moranda P L. Software reliab ility research[ J]. Sta- tistical Computer Perform ance Evaluation, 1972( 2): 10-12. [ 7] 方木云, 李锐. 软件可靠性评估研究 [ J]. 微机发展, 2002, 12( 1): 11-13. [ 8 ] Littlewood B, V errall J L. A Bayesian reliab ility grow th m odel for compu ter software[ J]. IEEE Trans. on Softw are Engineering, 1973, 22: 332-346. [ 9] 徐仁佐, 等. 软件可靠性专家系统 ( SRES)中经验模型的 奇异性问题与参数估计方法 [ J]. 计算机学报, 1998, 21 ( 2): 145-153. [ 10] 宋晓秋. 软件可靠性 J-M 增长模型的特性分析 [ J]. 系统 工程与电子技术, 1997( 9) : 44-46, 70. [ 11] 丛珉, 陆民燕, 等. 软件可靠性预计方法研究及实现 [ J]. 北京航空航天大学学报, 2002, 28( 1): 34-38. [ 12] 韩成宇, 侯朝桢, 徐勇. 带失效因子的 J-M 软件可靠性预 计模型 [ J]. 火力与指挥控制, 2006, 31( 3) : 18-20. [ 13] T ian J. M essurem ent and continuous improvem ent of sof-t w are reliability throughout software life-cycle[ J]. Journal of System s and Softw are, 1999, 47( 2-3): 189-195. [ 14] 方木云, 屈玉贵, 赵宝华. 软件可靠性 JM 模型完全排错假 设的修改 [ J]. 小型微型计算机系统, 2001, 22( 2): 199-200. ( 上接第 10页 ) 经过测试可得, 文献 [ 12]提出的基于动态反馈的 负载均衡算法使各个节点的负载趋于稳定, 能有效地 减少平均应答时延, 提高了系统资源利用率和服务器 的性能。 4 结束语 近年来, 负载均衡的研究取得了很大的成就, 但 是随着应用和体系结构的发展, 研究需继续进行。负 载均衡算法仍然是国内外研究者的研究热点, 现有的 负载均衡算法须被改进以适应更加复杂的应用。在 设计负载均衡算法的时候, 要考虑到应用的不同, 如 一些负载均衡算法适用于大的并行处理, 一些算法在 处理短小的任务时较有优势。另外, 在集中式的服务 器集群中, 即负责处理负载均衡的是一台服务器, 还 需解决的是负责处理负载均衡的服务器成为瓶颈 ( bottleneck)和单点故障 ( one-node failure)的问题。 参考文献: [ 1] Valeria Cardellin,i M ichele Colajann,i Ph ilip S Yu. Dynam- ic load balancing on W eb-server system [ J]. IEEE Internet Com puting, 1999, 3( 3): 28-39. [ 2] Andresen D, Tao Yang, Ibarra O H. SWEB: Tow ards a scala- bleWorldW ideW eb server on multicom puters[ C ] / /Proceed- ing of the 10th International Parallel Processing Symposium. H onolulu, H I, USA, 1996: 850-856. [ 3] Sandeep S ingh Waraich. C lassification of dynam ic load balan- cing strategies in a network ofworkstations[ C] / /F ifth Interna- tional Conference on Inform ation Technology. Washington, USA, 2008: 1263-1265. [ 4] 刘高峰. 负载均衡技术全攻略 [ EB /OL]. h ttp: / /www. yesky. com /20010626 /187006. shtm ,l 2001-06-26. [ 5] 王霜, 修保新, 肖卫东. W eb服务器集群的负载均衡算法 研究 [ J]. 计算机工程与应用, 2004, 40( 25): 78-80, 99. [ 6] 李红瑞, 胡子飞, 潘清. 基于集群的 W eb服务器关键技 术研究 [ J]. 计算机科学, 2002, 29( 9): 209-212. [ 7] Kerdlapanan D, Khunk itti A. Content-based load balancing w ith m ulticast and TCP-handoff[ J]. IEEE Xp lore, 2003, 2 ( 25-28): 348-351. [ 8] PaulWerstein, Hailing S itu, ZhiyiHuang. Load balancing in a cluster computer[ C ] / /Seventh International Conference on Parallel and Distributed Com puting, App lications and Techno-l ogies. Taipe,i Taiwan, 2006: 569-577. [ 9] 魏臻, 王雪辉,周霞. 基于内容识别的 Web集群负载均衡算法 的研究 [ J]. 计算机工程与设计, 2006, 27( 18): 3410-3412. [ 10] 孙林, 罗大庸, 张航. 基于遗传算法的 W eb服务器集群负载 均衡研究[ J]. 计算机测量与控制, 2006, 14( 10): 1364-1365. [ 11] 龚梅, 王鹏, 吴跃. 一种集群系统的透明动态反馈负载均 衡算法 [ J]. 计算机应用, 2007, 27( 11): 2662-2665. [ 12] 田绍亮, 左明, 吴绍伟. 一种改进的基于动态反馈的负载均 衡算法 [ J]. 计算机工程与设计, 2007, 28( 3): 572-573, 728.
还剩4页未读

继续阅读

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

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

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

下载pdf

pdf贡献者

adamchen

贡献于2013-09-05

下载需要 2 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf