第２９卷第３期 文章编号：１００６—９３４８（２０１２）０３—０１８０—０４ 计算机仿真 ２０１２年３月 服务器集群负载均衡的建模与仿真研究 许海成．傅锦伟 （红河学院计算机科学系，云南蒙自６６１１００） 摘要：研究服务器集群负载优化调试问题，各服务器负载能力差异较大，要求尽可能使每一个服务器的负载均衡，传统方法 没有考虑负载动态变化特点，导致服务器集群负载极不均衡，系统性能差。为提高集群系统的整体性能，提出一种基于遗传 算法的服务器集群负载均衡算法。首先根据负载均衡目标建立数学模型，然后采用遗传算法模型进行求解。仿真结果表 明，遗传算法提高了服务器集群系统吞吐量，使系统负载更加均衡，使整个集群系统的资源得到充分利用。 关键词：集群服务器；数据挖掘；负载均衡；遗传算法 中图分类号：ＴＰ１８ 文献标识码：Ｂ Ｒｅｓｅａｒｃｈ ｏｎ Ｍｏｄｅｌ ａｎｄ Ｓｉｍａｔｉｏｎ ｏｆ Ｌｏａｄ Ｂａｌａｎｃｅ ｆｏｒ Ｓｅｒｖｅｒ Ｃｌｕｓｔｅｒ ｘｕ Ｈａｉ—ｃｈｅｎｇ．ＦＵ Ｊｉｎ－ｗｅｉ （Ｈｏｎｇｈｅ Ｕｎｉｖｅｒｓｉｔｙ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ Ｄｅｐａｒｔｍｅｎｔ，Ｍｅｎｇｚｉ Ｙｕｎｎａｎ ６６１ １００，Ｃｈｉｎａ） ＡＢＳＴＲＡＣＴ：Ｒｅｓｅａｒｃｈ ｏｆ ｓｅｒｖｅｒ ｃｌｕｓｔｅｒ ｌｏａｄ ｏｐｔｉｍｉｚａｔｉｏｎ ｄｅｂｕｇｇｉｎｇ ｐｒｏｂｌｅｍｓ．Ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｄｉｆｆｅｒｅｎｃｅｓ ｉｎ ｓｅｒｖｅｒ ｐｅｒｆｏｒｍａｎｃｅｓ，Ｉｔ ｉｓ ｄｉｆｆｉｃｕｈ ｆｏｒ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｅｎｕｍｅｒａｔｉｏｎ ｍｅｔｈｏｄ ｔｏ ａｃｃｕｒａｔｅｌｙ ｂａｌａｎｃｅ ｌｏａｄｓ，ｌｅａｄｉｎｇ ｔｏ ｔｈｅ ｕｎｂａｌ— ａｎｃｅｄ ｌｏａｄｓ ａｎｄ ｐｏｏｒ ｓｙｓｔｅｍ ｐｅｒｆｏｒｍａｎｃｅｓ．Ｉｎ ｏｒｄｅｒ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｗｈｏｌｅ ｐｅｒｆｏｒｍａｎｃｅｓ ｏｆ ｔｈｅ ｃｌｕｓｔｅｒ ｓｙｓｔｅｍ，ｔｈｅ ｐａ— ｐｅｒ ｐｕｔ ｆｏｒｗａｒｄ ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｓｅｒｖｅｒ ｃｌｕｓｔｅｒ ｌｏａｄ ｂａｌａｎｃｉｎｇ ａｌｇｏｒｉｔｈｍ．Ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ｓｅｒｖｅｒ ｌｏａｄ ｂａｌａｎｃｉｎｇ ｃｌｕｓｔｅｒ ｆｅａｔｕｒｅｓ，ｔｈｅ ｓｔａｎｄａｒｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｗａｓ ｉｍｐｒｏｖｅｄ，ａｎｄ ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔｓ ｗｅｒｅ ｉｍｐｌｅ． ｍｅｎｔｅｄ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｓｙｓｔｅｍ ｔｈｒｏｕｇｈｐｕｔ，ｓｈｏｆｌｅｎ ｔｈｅ ａｖｅｒａｇｅ ｓｙｓｔｅｍ ｔｉｍｅ，ＳＯ ｔｈａｔ ｔｈｅ ｗｈｏｌｅ ｃｌｕｓｔｅｒ ｓｙｓｔｅｍ ｒｅｓｏｕｒｃｅｓ ａｒｅ ｆｕｌｌｙ ｕｔｉｌｉｚｅｄ． ＫＥＹＷＯＲＤＳ：Ｓｅｒｖｅｒ ｃｌｕｓｔｅｒ；Ｄａｔａ ｍｉｎｉｎｇ；Ｌｏａｄ ｂａｌａｎｃｉｎｇ；Ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ １ 引言 随着网络技术飞速发展，服务器信息日益剧增．单一服 务器难以适应现代数据发展的要求，服务器集群将多个服务 器组合在一起，形成一个高性能的服务器。完成原先单个服 务器所不能完成的任务 １］。在服务器集群系统中。各服务器 负载能力差异较大，不能均匀承担用户发出的请求，如何使 各服务器之间负载均衡是集群系统首先要解决的问题ｌ２．３］。 大量研究表明，目前常用的负载均衡算法分为两类：静 态负载均衡算法和动态负载均衡算法Ｌ４］。静态负载均衡算 法如轮转法，没有考虑到负载节点的动态变化．简单容易实 工智能技术，具有群智能性、自组织搜索、自适应等特性，能 够根据环境变化来自动识别环境规律，十分适用于状态实时 变化的服务器负载集群应用 ］。 为了保证服务器集群负载均衡，提高系统资源利用率． 提出一种基于遗传算法的服务器集群负载均衡算法。首先 结合服务器集群系统的特点，建立负载优化的数学模型，然 后采用遗传算法通过个体之间信息交流．对负载进行动态分 配，尽量使每一个服务器的负载能力达到最大，从而提高整 个服务器集群负载的能力。最后通过具体仿真对负载均衡 算法性能进行测试 现，但是在实际应用中存在许多缺陷，不能有效保证各服务 器负载均衡＿５］。动态负载均衡算法根据服务器当前负载的 状况，动态地将用户请求分配给每台服务，主要有：加权最小 ２服务器集群负载均衡问题 ２．１服务器集群负载均衡工作原理 连接算法和最快连接算法。但是这些算法只适合于小型服 务器集群系统，对于大型服务器集群系统不能很好均衡负 服务器集群负载均衡是依据集群系统中各节点的处理 能力，采用某种分配算法将用户的请求尽可能均衡地分配给 每一个节点上进行处理。使每一台服务器都充分发挥自己最 大性能．提高整个集群系统的处理性能，有效减少用户的等 待时间，具体工作原理如图１所示ｌ８］。 载［６］。遗传算法（ＧＡ）是一种模拟自然界生物进化机制的人 收稿１３期：２０１１—１２—３０修回１３期：２０１２一Ｏｌ一０５ 一ｌ８０一 适度函数进行说价，其也是指导遗传算法的寻优方向。 ５）选择操作。通过选择操作将比较优的个体复制到下 一代。 ‘ ６）交叉、变异操作。通过交叉、变异操作产生新的个体， 使种群中的个体保持多样性，防止出现过早收敛现象。 ７）终止条件确定。当种群中最优个体的适应度值达到 预先设定的阈值．或者连续若干代最优个体适应度值没有改 负载增量队刿 进，或者迭代次数达到最大进化代数，那么就认为算法终 止。 如果直接采用标准遗传算法对服务器集群系统的负载 噩务器 均衡进行求解，容易产生早熟和收敛速度慢等缺点，因此本 图１ 服务器集群负载均衡工作原理 文结合负载均衡的特点，对标准遗传算法进行改进。 ３．２ 负载均衡算法设计 ２．２服务器集群负载均衡的数学模型 ３．２．１ 编码设计 为了能动态、自适应地进行服务集群系统负载均衡，必 标准遗传算法一般采用二进制编码方式，该方式容易产 须周期性地从各个节点中收集：ＣＰＵ利用率、内存利用率、磁 生早熟缺陷，为此，本文结合负载均衡的特点，采用的十进制 盘ＦＯ访问率和请求执行的时间。设集群系统中有ｎ台可用 编码方式，染色体长方度为等于用户请求数，简化编码形式， 的服务器：｛ｓ ，ｓ ，…，ｓ ｝，同一时间内，其有ｍ个并发请求， 为后继交叉和变异提供了方便．提高了求解速度。 那么第ｉ台服务器的负载指数就可以描述为： ３．２．２初始化群种群 Ｌｏａｄ（Ｎｉ）＝Ｒ１ （Ｌｃｐｕ（Ｎ ）＋Ｒ２ Ｌｍｅｒｍｏｒｙ（Ｎ ）＋ 标准遗传算法采用完全随机的方法产生初始种群，容易 Ｒ３ Ｌｉｏ（Ｎ ）＋Ｒ４ Ｌｑｔｉｍｅ（Ｎ。） （１） 早熟和局部最优缺陷，本文采用均匀设计产生初始种群，使 式中，权重值∑Ｒ ＝１。 负载均衡的初始解尽量均匀分布于解空间．使种群中的个体 具有多样性，加快遗传算法的收敛速度，同时降低迭代次 负载均衡目的是减少任务的响应时间，提高服务器集群 数。 系统资源的整体利用率，设 表示某台服务器处理Ｓ 个用户 ３．２．３适应度函数 请求所需要的时间，那负载最佳均衡方案就变成一个求 适应度函数也叫评价函数，是用来评判服务器集群系统 ∑Ｘ 的最小值，那么ｎ台服务器处理ｍ个用户并发请求的 负载分配方案解的优劣程度，通过适应度函数这一信息来指 最短执行时间： 导种群搜索方向，并作为遗传操作的依据，由于负载平衡方 Ｔ＝Ｍｉｎ｛、』 Ｘ． Ｉ｝，， ０＜ｉ ｎ （２） 案是一个求最小化问题，因此适应度函数应该与∑Ｘｉ有关， 其中，Ｘ ＝∑Ｔｊ ＋Ｒ４ （１—１／∑ 。 因此．适应度函数定义如下： １ 置）＝亡 （３） ３ 遗传算法对服务器集群负载数学模型求解 ｆ ３．１遗传算法 从式（３）可知 置）越大，表示服务器负载比较均衡， １９７５年，Ｊ．Ｈｏｌｌａｎｄ教授根据生物进行化理论提出了遗 反之，服务器负载越不平衡。 传算法（ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ＧＡ），不需要待解决问题的具体领 ３．２．４选择策略 域信息．在问题解空间中适应地调整搜索方向，具有内在隐 遗传算法主要通过选择策略选出最优解，本文采用轮盘 赌选择法进行服务器集群负载均衡方案选择，设群体大小为 并行性和全局寻优能力．是当前人工智能技术中的一个优化 ｎ，个体ｉ的适应度为 ，那么该个体被选择中进行下一代种 算法［９］。通常情况下，ＧＡ的具体执行步骤如下： 群的概率为： １）算法参数设置。主要包括种群大小、遗传操作的概 ｆ 率、最大执行代代数。 Ｐ ＝ （４） ２）问题解的编码。通常情况下，不能采用遗传算法对问 ∑ ｉ＝１ 题直接进行求解，需要采用某种编方式将其转换成计算机能 从式（４）可知，个体适应度越大。其被选择的概率就越 够识别的形式。 高。 ３）初始种群的产生。初始种群代表问题的最初可行解 ３．２．５交叉和变异操作 集。 在遗传算法的应用过程中，交叉概率Ｐ 和变异概率Ｐ ４）个体适应度函数构造。种群中的个体优劣程度通过 对算法收敛速度起着至关重要的作用。同时局部和全局搜 一１８１— 索能力都是通过交叉和变异操作来保证的。交叉概率Ｐ 越 大，新个体产生的速度就越快，同进对个体被破坏的可能性 ４仿真研究 ４．１仿真环境 就会增加，导致一些适度值较高个体很快就被破坏。然而交 叉概率Ｐ 太小，导致搜索速度缓慢，以至停滞不前。对于变 异概率Ｐ ，如果过小，不易产生新的个体，但是过大，同样要 破坏最优解，且容易出现局部最优缺陷＿１ 。 采用具体仿真对基于遗传算法的服务器集群负载均衡 性能进行测试，本实验其有８台服务器，一台作为测试客户 端，一台作为用户请求调度管理节点．其余６台作为真实服 务器，它们由交换机组成一个测试集群，具体构架如图３所 示，仿真测试用ＬｏａｄＲｕｌｍｅｒ作为测试工具，采用ＣＰＵ平均利 用率（％）、平均应答延迟（ｍＳ）和系统平均吞吐量（ｉｎ）作为 算法性能评价指标。采用加权最小连接算法和标准遗传算 法进行仿真对比实验。 大量研究表明，在遗传算法运行的初期，尽量保持种群 个体间差异性较大，此时，交叉概率要大，而变异概率要小， 从而种群的进化速度加快；随着算法的运行，特别是在后期， 就需要适当地增大变异概率，减小交叉概率，保证种群的多 样性，防止局部最优出现，因此本文根据这一思想，采用自适 应的交叉和变异概率进行交叉和变异操作，具体为： Ｐ ：＝｛ｆ Ｎ Ｎ…一 …一 （）５ ｌ Ｎ ＞ Ｐ ：＝｛…一ｆ Ｎ ，ｖｎ ～一Ⅳ （）６， Ｉ ｋ２ Ｎ＞ 式中，，ｖ。 为种群平均适应度值；Ⅳ 为种群最大的适应 度值； 。和ｋ：为一个（０，１）之间的随机数，Ⅳ 为交叉个体中 较大的适应度值：Ⅳ为要变异的个体适应度值。 ３．３遗传算法的负载均衡流程 综合上述可知．基于遗传算法的服务器集群负载均衡的 工作流程如图２所示。 图２服务器集群负载均衡流程 一１８２一 图３测试系统网络连接拓扑图 ＼＊隹ｆ霹霹 害 砷 ∞ ∞ 如 加 ｍ Ｏ ４．２ ＣＰＵ平均利用率 采用３种算法，对６台服务器ＣＰＵ利用以１ｓ的时间间 隔进行采集，共采集５组数据进对比，其结果如图４所示。 图４几种算法ＣＰＵ利用率对比 从图４可知，加权最小连接算法的ＣＰＵ利用率最低，主 要是由于其没有考虑每个处理器处理任务的差异，标准遗传 法低于本文算法．主要是由于标准遗传算法易陷入局部最 优，因此ＣＰＵ有时利用率比较低。 ４．３平均响应时间对比 基于加权最小连接算法、标准遗传算法和本文算法进行 服务器集群系统调度的平均响应时间如图５所示。 从图５可知。本文负载均衡算法的平均响应时间最短， 当客户请求数增加时，用户的平均应答延迟时间均延长，但 是本文算法延迟时间增长比较缓慢，说明本文负载均衡算法 的平均响应速度比对比算法要快，而且随着集群规模增大， 本文算法运行时间没有显著增长，仍然保持良好的性能。 ｌ／■蕾摊 果证明，随着用户请求数量的增加，本文算法比对比算法具 暑域雄 露 ７ ６ ５ ４ ３ ２ ｌ Ｏ 有更短的用户任务的平均响应时间，提高了ＣＰＵ的利用率 和系统吞吐量，是一种有效、可靠的集群系统负载均衡算法。 参考文献： ［１］刘同．负载均衡技术在数据库集群系统中的应用与实现［Ｄ］． 长沙：国防科技大学，２００９． 湖 姗 枷 枷 瑚 ｍ 。 ［２］ 马双良，张英敏，宋丽君．基于ＬＶＳ和计算任务的实时集群负 载均衡方法［＿，］．计算机工程与设计，２００７，２８（２Ｏ）：４９３４— 图５几种算法的平均应答延迟比较 ４９３７． ［３］ 薛军，李增智，王云岚．负载均衡技术的发展［．，］．小型微型计 ４．４ 系统的平均吞吐量 基于加权最小连接算法、标准遗传算法和本文算法的系 统吞吐量对比结果如图６所示。从图６可知，本文算法系统 吞吐量高于对比负载均衡算法。充分地利用整个系统的资 源．使整个服务器集群系统负载更加均衡。 算机系统，２００３，２４（１２）：２１００—２１０３． ［４］ 刘健，徐磊，张维明．基于动态反馈的负载均衡算法［．，］．计算 机工程与科学．２００３，２５（５）：６５—６８． ［５］刘安丰，等．基于ｃｏ，ｔｈｅ优化的ｗｅｂ集群负载均衡算法［，］．计 算机工程，２００４，３０（１０）：ｌ２一ｌ３． ［６］ 龚梅，王鹏，吴跃．一种集群系统的透明动态反馈负载均衡算 法［，］．计算机应用，２００７，２７（１１）：２６６２—２６６５． ［７］ 唐世洁，朱启疆．遗传算法中初始种群与交叉、变异率对解的 影响及其解决方案［，］．科技通报，２００１，／７（３）：１—７． ［８］ 黄江波，付志红．基于自适应遗传算法函数优化与仿真［Ｊ］． 计算机仿真，２０１１，２８（５）：２０８—２１２． ［９］ 巩敦卫，等．交互式遗传算法原理及应用［Ｍ］．北京：国防工 业出版社．２００７． ［１０］周宇鹏，张争气．基于改进遗传算法的波束形成方法［．，］．计 算机仿真，２０１０，２７（８）：２０８—２１２． 图６几种算法的服务器集群系统吞吐量对比 ［作者简介］ 许海成（１９６２．１２一），男（汉族），云南石屏人，副教 授，研究方向：信息系统集成； ６结束语 针对当前服务器集群算法在负载均衡过程存在的缺陷， 提出一种基于遗传算法的服务器集群负载均衡算法，实验结 傅锦伟（１９６４．４一），男（汉族），云南建水人，教授， 研究方向：信息安全。 ＿ ＿ ＿ Ｉ Ｉ● ｌ ｌ一－●＿ Ｉ － ● ●－＿ｌ Ｉ－ ＿ ＿ ＿ ＿ Ｉ＿ｌ Ｉ＿ ＿＿－Ｉ —ｌ－ ●＿ ＿＿ ＿●●＿Ｉ＿ 一１８３一
