（计算机应用技术专业论文）linux集群负载调度机制的研究.pdf

捅要 随着网络快速发展和网络用户日益增加，单台服务器难以满足大量用户的需 求，而集群的出现缓解了这一问题。集群系统具有可伸缩性、高性价比、高可用 性的特点，因此得到了广泛的应用。负载均衡是集群性能提高的关键因素之一， 目前仍然是集群系统研究的一个热点，具有较高的研究价值和应用前景。 本文的研究内容作为大连市科学技术基金计划项目新型网络服务器的资源 管理与系统状态监控( 编号：2 0 0 5 j 2 2 j h 0 3 1 ) 的重要组成部分，主要研究了l i n u x 集群的负载均衡。首先介绍了集群负载均衡算法的模型、负载指标、调度算法、 负载均衡实现技术，然后详细介绍了l v s 的体系结构、软件层次，着重分析了 四种常用调度算法和基于口层的转发模式。l v s 集群的调度算法目前还是无反 馈节点信息的负载调度，适合少量用户的访问。对于大规模并发访问存在效率低， 稳定性差，可用性差和整体性能下降等问题。最后在分析原有调度算法存在不足 的基础上，本文提出并构建了带反馈的集群负载动态调度方案l b d w ，这种方 案通过收集负载信息，根据负载和节点固有性能计算动态权值，从而估测各服务 器的剩余处理能力，同时监测服务器的健康状况，然后选择一种加权的算法来实 现有反馈的负载动态调度。本文针对较优的有反馈的动态加权最小连接( d w l c ) 调度算法存在的不足进行了优化，改进为优化动态加权连接( o d w c ) 调度算法， 并将o d w c 调度算法应用到具有反馈的集群负载动态调度方案中。 通过测试工具s i e g e 对加权最小连接( w l c ) 、d w l c 和o d w c 调度算法进 行压力测试，大量实验表明，在相同负载情况下，本文提出带反馈的集群负载动 态调度中o d w c 算法性能比d w l c 要好，尤其是在短时间内更明显，而动态调 度算法d w l c 性能要比w l c 要好，特别在负载大的情况下。 关键词：集群；负载均衡；l v s ；负载指标；动态调度；l d ir e c t o r d a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fn e t w o r ka n di n c r e a s i n go fi n t e m e tu s e r s ，t h e s i n g l es e r v e rc a nn o ts a t i s f yt h er e q u i r e m e n t so fal a r g en u m b e ro fu s e r s a n dt h e e m e r g e n c eo fc l u s t e rs o l v e st h ep r o b l e m i ti ss e a l a b l e ，c o s t e f f e c t i v e ，h i g h a v a i l a b i l i t y , ， s oi th a sb e e nw i d e l yu s e d l o a db a l a n c ei st h ek e yf a c t o ri m p r o v i n gm ep e r f o r m a n c e o fc l u s t e r , a n di th a sah i g hr e s e a r c hv a l u ea n da p p l i c a t i o nf o r e g r o u n d ，w h i c hi sah o t s p o to fc l u s t e rr e s e a r c h t l l i sp a p e ri so n ei m p o r t a n tp a r to fp r o j e c t , w h i c hi ss u p p o r t e db yd a l i a ns c i e n c e a n dt e c h n o l o g yf u n d s an e ww e bs e r v e rr e s o u r c em a n a g e m e n ta n ds y s t e ms t a t u s m o n i t o r i n g ( n o ：2 0 0 5j 2 2 j h 0 31 ) t h ep a p e rm a i n l yr e s e a r c h e st h el o a db a l a n c i n go f l i n u xc l u s t e r f i r s t l y , i ti n t r o d u c e st h ec l u s t e rl o a db a l a n c i n ga l g o r i t h m sm o d e l ，l o a d i n d i c a t o r s ，s c h e d u l i n ga l g o r i t h m s ，l o a db a l a n c i n gt e c h n o l o g y s e c o n d l y ，i te x p o u n d s t h el v sa r c h i t e c t u r e ，s o f t w a r el e v e l ，a n df o c u s e so nt h ef o u rt y p e so fc o m m o n l yu s e d a l g o r i t h m sa n dt h ef o r w a r d i n go fi p - b a s e dl a y e r a tp r e s e n t ，t h el v sc l u s t e r s c h e d u l i n ga l g o r i t h mi s s t i l ll o a ds c h e d u l i n gw i t h o u tf e e d b a c k , w h i c hi sa d a p tt oa s m a l ln u m b e ro fu s e r sa c c e s s i n g b u tt ol a r g e s c a l ea c c e s s i n g l v sh a st h ep r o b l e m s o fl o we f f i c i e n c y , p o o rs t a b i l i t y ，p o o ra v a i l a b i l i t y , w h i c hm a k et h ew h o l ep e r f o r m a n c e d e c l i n e f i n a l l y , b a s i n g o nt h e a n a l y s e s o ft h e o r i 百n a ls c h e d u l i n ga l g o r i t h m s d e f i c i e n c i e s ，t h ep a p e rp r o p o s e sa n db u i l d sac l u s t e rl o a dd y n a m i cs c h e d u l i n g s c h e m e f l b d w ) w i t hf e e d b a c k l b d wc a l c u l a t e sd y n a m i cl o a dw e i g h tb yc o l l e c t i n g l o a di n f o r m a t i o n e s t i m a t e st h es e r v e r s r e m a i n d e rc a p a c i t y , m o n i t o r e st h es e r v e r s h e a l t hs t a t u s a n dt h e ns e l e c t so n ew e i g h t e ds c h e d u l i n ga l g o r i t h mt oa c h i e v ed y n a m i c l o a ds c h e d u l i n g t h i sp a p e l o p t i m i z e st h ed y n a m i cw e i g h t e dl e a s t c o n n e c t i o n ( d w l c ) a l g o r i t h m m a k e s d w l ci n t o o p t i m i z i n gd y n a m i cw e i g h t e d c o n n e c t i o n ( o d w c ) a l g o r i t h m , a n da p p l i e so d w c t ot h ec l u s t e rd y n a m i cs c h e d u l i n g p r o g r a m m e sw i t hf e e d b a c k t h et e s tt o o ls i e g et e s t st h es c h e d u l i n ga l g o r i t h m sw l c d w l ca n d0 d w c t h er e s u l t ss h o wt h a ti nt h ec a s eo ft h es a n l ec l u s t e rl o a d t h eo d w ca l g o r i t h mi s b e t t e rt h a nt h ed w l c ，e s p e c i a l l yi nas h o r tp e r i o do ft i m e ，t h ea d v a n t a g ei sm o r e o b v i o u s l y a n dt h ed y n a m i cs c h e d u l i n ga l g o r i t h md w l cp e r f o r m sb e t t e rt h a ns t a t i c s c h e d u l i n ga l g o r i t h mw l c e s p e c i a l l yi nt h ec a s eo fl a r g el o a d k e yw o r d s ：c l u s t e r ；l o a db a l a n c e ；l v s ；l o a di n d i c a t o r s ；d y n a m i cs c h e d u l i n g ； l d i r e c t o r d l i n u x 集群负载调度机制的研究 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文 中除特别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的 研究成果，其他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做 了明确的声明并表示谢意。 学位论文作者签名：殳智也 日 期：h 呸不二 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及 学校有权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借 阅。本文授权辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库 并进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密 的学位论文在解密后使用本授权书。 学位论文作者签名：互曾葱 耘“ 嘘卜 。哩 矿翟洲盼h 獬期 d y教 l i n u x 集群负载调度机制的研究 1 1 研究背景 第一章绪论 随着网络的快速发展，网络用户日益增加，导致网络流量迅速增长。网络 的快速发展给服务器和网络带宽带来了更多的挑战。超负荷的访问流量很容易 使服务器产生瓶颈导致服务器瘫痪，服务器面临着如何提供更高吞吐量、更快 响应时间和并发处理能力。在以前一般选择单服务器算法，要求该服务器具备 良好的硬件性能，如c p u 要求性能高，内存容量大，超大硬盘容量，l j o 速率 等，同时要求高的网络带宽。但是即使单服务器性能再好，也无法承受不断增 加的负载压力，单台服务器提供的能力很难满足当前日益增多的客户并发访问 的需求。基于这种状况，所以后来出现了服务器集群，服务器集群技术采用多 个服务器并行算法，不再是单一的服务器，而由多个服务器共同分担多个客户 的请求。 集群，又称n o w ( n e t w o r ko fw o r k s t a t i o n s ) 或c o w ( c l u s t e ro f w o r k s t a t i o n s ) ，是指独立的计算机，可以是普通p c 机、工作站或s m p 服务器， 通过高性能网络或局域网连接，每个节点保持各自独立的同时，还能够协同工 作完成给定任务【1 】【2 】【3 1 。集群系统具有可伸缩性，高可用性，可管理性，单一 系统映像和高性价比等特点【4 】【5 】【6 】。逐渐成为高性能计算机体系结构的发展趋 势。因此，集群技术成为当前研究的热点之一。为了提高系统资源的利用率， 使客户请求得到快速响应，实现一个高效集群系统需要解决的关键问题之一是 负载均衡。 集群负载均衡主要解决的是当某个请求到达集群时如何通过负载均衡算法 将请求合理地分配给各个服务器来提高集群的整体效率。负载是指一个处理机 上运行的所有任务占用资源的总量【7 1 。不同环境下负载不同，这里负载指的是 服务器的c p u 就绪队列长度、连接数、网络流量等。如果集群没有负载均衡功 能或负载均衡算法不合理，则可能出现某个服务器过忙导致该服务器瘫痪，而 其他服务器却闲置未充分利用，导致整个集群在处理并发请求时效率会降低。 本文在异构集群服务器的环境下，对l i n u x 集群的负载均衡调度算法进行相关 研究，对其负载调度算法进行了改进，提高了集群的整体效率。 l i n u x 集群负载调度机制的研究 1 2lin u x 集群 集群系统采用的操作系统主要有v m s 、u n i x 、w i n d o w s 、l i n u x 【引。由于 l i n u x 是开源代码，世界各地的程序员不断完善该系统并使其逐渐走向成熟， l i n u x 的健壮性和竞争力也不断增强。目前很多网络服务器采用了l i n u x 集群， 这在很大程度上推动了基于l i n u x 集群系统的快速发展。目前根据功能将集群 分为三类。第一类是高可用性集群，目的是在系统出现某些故障情况下，仍能 对外提供服务，最大限度减少服务中断时间。其中较著名的有t u r b o l i n u x 、 t u r b o h a 、h e a r t b e a t 、p i r a n h a 等。第二类是负载均衡集群，目的是提供和节点 个数成正比的负载处理能力，适合提供访问量大的w e b 服务，该类集群通常也 具有高可用性特点，较为典型的有l v s ，目前将第一类和第二类统称为高可用 集群。第三类是超级计算机集群或称高性能计算集群，侧重并行求解复杂的数 学算法。如天气预报处理，油减模拟等软件。在性能上数目庞大的计算机集群 胜过同等价值的单一处理器。如1 9 9 4 年n a s a 开始的b e o w u l f 【9 】计划，它使用 1 6 个节点的超级计算机构建了集群系统，价格是同等计算能力的单一计算机的 十分之一，这类软件还有e n f u s i o n 、s c o r e 、p v m 、m p i 等。 1 3 目前集群负载均衡的研究现状 集群系统的优势就是可以充分利用集群内每个节点的处理能力。为充分利 用集群的优势，通过负载均衡使集群处于高效状态，提高集群整体性能。负载 均衡有两方面的含义【l o 】，首先，大量的并发访问或数据流量分摊到多台节点机 上分别处理，减少用户等待时间；其次，单个重负载的运算分摊到多台节点机 上做并行处理，每个节点机处理结束后，将结果汇总，返回给用户，系统处理 能力得到大幅度提高。本文服务器集群负载均衡主要是指在服务器集群中所有 服务器之间分配负载的应用，是第一种情况。 目前无论在超级计算机还是在高可用性集群中，都考虑了负载均衡。集群 负载调度算法和负载均衡技术也在不断发展中。负载调度算法分为静态算法和 动态算法。对于负载均衡静态算法传统的有轮转算法、加权轮转算法，适用于 小规模访问量的系统。但对于有大规模访问量的集群，显然效率低稳定性差， 2 l i n u x 集群负载调度机制的研究 因此出现了动态算法。负载均衡动态调度算法有最小连接、加权最小连接等， 它们都是以连接为粒度，没有实现真正的动态调度，负载均衡效果并不理想。 负载调度静态与动态算法不同之处是动态需要服务器节点的实时负载状况。可 以将负载调度算法应用到负载均衡技术中。负载均衡实现技术有四种实现方式： 基于d n s 、基于客户端、基于应用服务器的特定方案、基于负载均衡器网络的 协议层。基于d n s 方式只能实现粗粒度的调度，不能准确反映实时负载和监控 服务器健康状况，基于客户端方式的不够灵活增加客户端负载，基于应用服务 器的特定方案使反向代理服务器成为瓶颈，基于负载均衡器的网络协议层弥补 了上述不足，是当今研究的热点。 国外有许多公司和高校推出了负载均衡集群产品。有c i s c o 开发的的l o c a l d i r e c t o r ，r a d w a r e 公司开发的w e bs e r v e rd i r e c t o r - - 系列产品，h p 公司开发的 a s a s 一系列产品。b e r k e l e y 的s m a r t c l i e n t ，p l a t f o r i l l 公司开发的l s f ，由j e r u s a l e m 的h e b r e w 大学开发的o p e n m o s i x ，w i s c o n s i n m a d i s o n 大学开发的c o n d o r 系统 等。 国内也有很多公司、科研机构和高校对集群的负载均衡进行了研究，有浪潮 公司、清华大学、国防科技大学、华中科技大学、中南大学等进行研制。有浪潮 公司的浪潮英信，清华大学实现了可扩展并行w e bs e r v e r 集群技术，国防科技大 学由章文嵩博士研发了较为典型的l v s 集群，是基于负载均衡器网络的协议层方 式实现的，实现了i p 层和应用层的负载均衡。 与国外公司生产的负载均衡产品相比，l v s 可以免费得到，其使用范围也较 广泛。目前很多负载均衡项目是基于l v s 开发的，如u l t r am o n k e y 扩展了l v s 项 目，提供心跳检测、节点监视功能；k e e p a l i v e d 为l v s 增加了健壮、自动的灾难 恢复功能，它监测各节点，当节点宕机时，负责通知内核把宕机服务器删除，保 证用户请求不会被错误分发；p i r a n h a 和f e e d b a c k d 也是完全基于l v s 的，p i r a n h a 只使用c p u 队列长度作为负载，而f e e d b a c k d 只使用c p u 利用率作为负载，它们都 仅反馈c p u 信息来实现简单的l v s 动态调度，算法并不理想。还有很多研究者都 设计了较为理想的调度算法，只进行了模拟测试，而在真实的集群系统中实现较 完善的动态算法并不容易。目前l v s 采用的是以连接为粒度的动态调度算法，还 不是很完善，内核调度算法仍然存在较大的优化空间。本文实现了l v s 带反馈的 l i n u x 集群负载调度机制的研究 负载动态调度，并对内核中调度算法进行了优化，得到较为理想的负载均衡效果。 1 4 本文主要工作内容和论文结构 本文是大连市科学技术基金计划项目新型网络服务器的资源管理与系统 状态监控( 编号：2 0 0 5 j 2 2 j h 0 3 1 ) 的重要组成部分，对集群负载均衡技术进行 了细致的研究，主要工作有以下几个方面： ( 1 ) 对目前l i n u x 集群的负载均衡问题进行细致的调研。 ( 2 ) 对l v s 内核己实现的调度算法、管理机制进行了深入研究，对l v s 实现的三种转发模式的思想进行了剖析。 ( 3 ) 分析了l v s 调度算法的不足，提出并构建了带反馈的集群负载动态 调度方案l b d w 。 ( 4 ) 本文针对较优的带反馈动态加权最小连接( d w l c ) 调度算法存在的不 足进行了优化，改进为优化动态加权连接( o d w c ) 调度算法。 ( 5 ) 通过测试工具s i e g e 对调度算法w l c ( 加权最小连接) 、带反馈的动 态调度算法d w l c 和o d w c 进行压力测试。 本文主要分为六部分： 第一部分对研究背景及当前l i n u x 集群负载均衡研究现状作了论述。 第二部分阐述了l i n u x 集群负载均衡理论，包括集群负载均衡模型、负载 均衡实现技术的概念和调度算法等。 第三部分分析了l v s 集群系统，包括l v s 结构、体系结构、核心软件调度 算法、实现l v s 三种转发模式。 第四部分对l v s 进行改进。本文提出了带反馈的集群负载动态调度方案 l b d w ，并对l v s 核心中的带反馈动态加权最小连接算法进行了优化。 第五部分对带反馈的动态调度算法进行测试并给出实验结果。 第六部分总结本文工作，并对下一步的工作提出了一些建议。 4 l i n u x 集群负载调度机制的研究 第二章集群负载均衡策略的关键技术 负载均衡是一种特殊的高可用性功能，它既提供了满足高可用性要求的节 点监测、恢复功能，还将服务请求均衡分布到集群中各节点，不仅减轻单服务 器的负载也缩短了集群服务的响应时间。已有的研究表明，在集群系统中采用 负载均衡技术可以显著地提高集群系统的性斛】。集群系统的负载均衡需要解 决好下面几个关键问题：一是构造负载均衡模型；二是负载指标的确定，它是 度量节点当前负载的方法，对负载均衡算法效果影响很大；三是调度算法，它 是通过某种策略来决定把用户请求分配给哪个服务节点；四是负载均衡实现技 术。 2 1 常用的集群负载均衡模型 当任务较多时，一个调度器要接收很多请求进行任务分配，造成调度器繁 忙导致瓶颈。因此很多研究者在研究调度算法的同时，为了减少网络开销，减 少调度器的任务，提高用户请求响应速度，需要构造更好的负载均衡模型。研 究者已经提出了许多不同的负载模型，有分布式、集中式、全局和局部等以及 对几种模型的组合。不同环境和应用选择不同模型，各有优缺点。 2 1 1 集中式模型 2 1 1 1 一级模式 集中式一级模型特点是由一个主控节点上的调度器直接负责负载信息收集 和运行负载分配算法并将任务分配给后台服务节点。 图2 1l v s 模型 l i n u x 集群负载调度机制的研究 国防科大l v s 模型如图2 1 ，调度器上执行负载均衡算法，根据算法将任 务分配给各个节点。为防止主节点失效，指定了一个备份节点。这个模型优点 是易于控制，但是调度器上任务过多，容易造成瓶颈。 华中科技大学【1 2 】的集群负载均衡系统模型。其负载信息是基于集中式管理 的，由一个调度器收集信息，控制分配任务。只是在何时收集、收集什么信息， 任务执行过程，主节点失效时实现调度器高可用性有所不同。为防止调度器瓶 颈，主控节点并没有保存所有节点信息，只保存轻载节点信息。当子节点状态 改变时主节点才收集。在执行中各个节点根据负载变化参与进程迁移，提高系 统效率，当主节点失效时，从普通节点中选出一个作为继任。 2 1 1 2 二级或双层模式 二级模型的共同特点是为减轻调度器上的过多任务，将原来一个调度器上 的任务分散到其他节点上。即不直接分配任务给真实服务器去执行，而是经过 中间分配器去分配或控制。每个二级模型集群系统都有其共性，但针对应用服 务的不同也各有其自身特点。 应用于w e b 服务器的集群，文献【】提出了双层请求分配服务器的模型如 图2 2 【1 3 】。有h r r p 请求时，请求分配服务器a 为避免瓶颈用轮转法快速将请 求分配到各个请求分配服务器b 上，b 上运行负载均衡算法。对负载信息进行 数据标准化后，分配任务给负载小的节点执行。该算法中负载指标之一为剩余 最大连接，较好地预测了负载信息，但由于各个请求分配器都有相同的负载信 息表，存在各个分配器间如何协调的问题，网络开销大。 图2 2 双层分配模型 四川大学的二级负载均衡模型【1 4 1 。这个模型有些特殊，因为看似好像调度 6 甲圈 l i n u x 集群负载调度机制的研究 器直接分配任务给服务器，而没有经过中间分配器，其实它是通过后台某节点 对调度器间接控制任务分配，有点幕后人操纵的感觉，如图2 3 【1 4 1 。第一级负 载调度器( 也可以称为负载均衡器) 上有一个后台服务器地址池，用轮转调度 从候选启动态的m a c 网卡物理地址选后台服务器，转发报文到服务器，因为 在数据链路层转发，转发效率高。第二级为服务器，将后台服务器的负载信息 当前任务数和m a c 反馈给c d s 用于计算数据的服务器，c d s 服务器上运行真 正的负载均衡算法。特点是收集负载信息少，减少了开销：c d s 上的决策进程 根据记录地址池状态，发送消息给均衡器，决定是否禁用或启动服务器m a c ， 从而间接控制了任务分配。该模型只有一个中间分配器，易于控制。 负载均衡器 图2 3 二级负载均衡模型 2 1 2 分布式模型 国防科技大学【l5 】提出的基于分布式调度机制的集群体系结构，与传统集中 分发调度方案最大的不同是，服务器不是被动的接收任务，而是主动去探询要 任务。调度器将新来的任务放到任务池中，当服务器上所有服务进程空闲时，向 调度器发出请求来承担任务，然后调度器用算法将任务分配给各个服务器，减 轻了调度器的负担。调度器也不用关心节点的退出和加入，监控和管理功能由 其他结点控制，不足之处是不利于集群的全局控制。 7 l i n u x 集群负载调度机制的研究 2 1 3 分布式和集中式结合 集中式容易管理，但易造成调度器瓶颈，易崩溃；而分布式中每个节点与 其他结点交换负载信息，可以实现局部好的平衡性，但又不易控制，网络开销 大。可以将分布式与集中式信息管理相结合，发挥各自优势，这方面已有不少 成果。 文献【1 6 】提出的基于主负载信息表的动态负载均衡模型如图2 4 【1 6 1 ，把所有 主机按相邻关系划分为n 个组，每组选一个处理能力最大的处理机为主负载信 息表的主机，其中主负载信息表包含组内所有节点负载指标、上下限和一级目 录地址。主负载信息表的主机负责被动的收集组内所有节点信息，而在相邻主 机上存有一个映像表，相邻节点不需相互交换信息。主负载信息表的主机也参 与负载的迁入与移出，由各个主机根据映象表依据自适应动态负载平衡算法来 决策，高于上限用发送者算法从本组中找负载最轻的节点迁移负载，如本组没 有轻负载则从上级目录找，若低于下限用接收者算法从本组中找负载最重的节 点。对主负载信息表的主机选择，超过上限或崩溃时选最轻负载作为主负载信 息表的主机，若原主负载信息表的主机低于上限或恢复时，恢复为原主负载信 息表的主机。 l2m ll2m 2l2i n n 图2 4 基于主负载信息表模型 上海大学【l7 】设计了基于多级资源池的负载均衡模型。该模型中的负载资源 维护如下：在主控节点上有一张一级全局资源表，进程p b ss e l v e r 负责各个节 点资源的接收，收集集群中所有不超载节点负载，按负载大小插入相应资源队 列。各个节点上有一张相关域的局部负载信息表为二级资源池，p b sm o m 探测 自身资源，各节点判断自身负载，如欠载则发送给其他节点和主控节点。其他 l i n u x 集群负载调度机制的研究 节点判断如果有该欠载节点负载信息并且在本节点相关域中则放入该局部负载 信息表。如节点负载超载，发送超载信号给其他节点和主控节点，其他节点判 断若在本节点相关域中，删除该超载节点信息并启动进程迁移模块。用进程局 部优先算法将正执行的进程迁移到相关域中欠载的节点上，若相关域中没有欠 载节点再到全局资源表中查找。分配任务时，主控节点上p b ss e i v g i 接收请求， 根据主控节点上的全局资源表选择负载较轻节点，然后进程p b ss c h e d 执行。 将通信密集的任务分配在同一相关域中节点执行，采用集中分配静态负载均衡。 在后台节点任务执行中，根据负载变化调节。如图2 5 【1 7 】所示。 集 群 管 理 系 统 竺一翌竺 l i n u x 【p b s s c h e a ： ，r、 p b ss e r v e r l r 7 i p b s _ m o m ( p b s ) 瞄磊均蟹警二 lj ： 【p b s _ m 。m l 彳t 7 动态负载均衡负载信息维护 节jl 一上一 动态负载均衡 旧荔徽k 级资源d 图2 5多级资源池的负载均衡模型 这两个模型的共同点是把后台服务节点都分成多个组，组内每个节点上都 有该组内节点的负载信息表，在执行过程中各个节点根据各自负载表进行负载 均衡。上海大学的节点管理更易于控制，因为在主控节点中有全局信息表包含 所有节点的信息，当后台节点在本节点负载表中查不到轻载节点时，可到全局 表中去找，查找的范围大。但是各个组内没有管理者，都是同等级别。文献【怕】 的各个组内有一个主负载信息表的主机，当本地节点负载表中查不到需要负载 信息时，只到上一级目录找，而上一级目录不是所有节点负载信息，查找范围 小，但是不易于全局管理。 2 2 负载指标 实现动态调度的前提是存在一个能正确反映系统当前负载情况的负载指 9 l i n u x 集群负载调度机制的研究 标。调度器收集到的负载信息用来衡量该节点的负载大小称为负载指标。负载 均衡的目标是提高系统性能，缩短请求响应时间，充分利用系统资源，使各个 服务器资源均衡。一个请求的响应时间依赖于负载，负载越重，响应时间越长。 针对不同的服务，有不同的负载指标，但没有统一的标准，较理想的负载指标 应当满足【1 8 】【1 9 l ： ( 1 ) 测量开销低，较易获得、易于计算，以满足频繁测量的需要； ( 2 ) 能客观体现所有竞争资源上的负载； ( 3 ) 各个负载指标在测量及控制上彼此独立。 负载指标通常包括： ( 1 ) 各种资源队列长度。有c p u 队列、f o 队列、请求任务队列、当前进 程数、运行队列中的任务数。使用较广泛的是c p u 队列长度，一般有两种：使 用当前瞬时的c p u 队列长度和使用一段时间内的平均c p u 队列长度。该指标 容易获得，但无法区分进程大小和性质。一个大进程可能花费的时间和占用的 资源比多个小进程要多。 ( 2 ) 资源利用率。包括c p u 利用率、内存利用率、f o 利用率等。 ( 3 ) 其他参数。当前连接数，响应时间，基于进程剩余运行时间等。 负载指标的选取很关键，选取不好就不能较全面的实时反映负载大小，会 影响整个负载均衡算法的效果。负载指标不仅考虑该指标能否客观体现当前节 点负载而且要考虑收集和处理这些信息所增加的负载。 2 3 调度算法 负载调度算法可分为两类，一类为静念算法，另一类为动态算法。静态算 法是指在各个节点上分配任务时，只使用系统的静态信息，不考虑节点当前负 载情况而进行的负载均衡。动态算法是根据集群中各个节点的当前负载状态进 行负载分配决策。静态算法实现简单，但是集群系统利用率低、性能差。动态 算法能利用当前服务器状态的短期起伏从而提高了系统的性能。但是存在收集、 分析计算系统状态时的额外开销。对于大规模集群系统，动态算法优于静态算 法。 l o l i n u x 集群负载调度机制的研究 2 3 1 静态算法 轮转法。是以轮转的方式依次请求调度不同的服务器，即将可用子节点放 在一个抽象的任务队列里，线性轮转选择每个节点。性能相同的服务器用该算 法好【2 0 】。 随机法。赋给各节点一个由伪随机算法产生的值，具有最小或最大随机数 的节点最有优先权。实际上相当于“无偏见的给节点产生权值，每个机器都 有可能获得最大的优先级，这也是一种“机会均等”的调度算法。和轮转法一 样，需要在相同的节点环境中，这种算法才能得到最好效果。 加权轮转法。解决服务器间性能不同情况，用相应的权值表示服务器的处 理性能，权值由管理员设定。根据服务器性能，按权值高低和轮转方式分配请 求到各服务器，权值高的服务器比权值低的服务器处理请求多f 2 i 】。 目标地址散列法( d h ) 。针对目标地址的负载均衡，是一种静态映射算法， 通过一个散列( h a s h ) 函数将一个目标i p 地址映射到一台服务器。先根据请求 的目标i p 地址，作为散列键( h a s hk e y ) 从静态分配的散列表中找出对应的服 务器，若该服务器是可用的且未超载，将请求发送到该服务器，否则返回空。 适用于w e bc a c h e 集群，指向同一个目标站点的访问请求都被负载调度器发送 到同一个c a c h e 服务节点上，以避免页面缺失而带来的更新c a c h e 问题。 源地址散列法( s h ) 。与目标地址散列调度算法相反，它根据请求的源i p 地 址作为散列键( h a s hk e y ) ，从静态分配的散列表找出对应的服务器，同时该服 务器是可用的且未超载，否则返回空。将具有相同源地址的数据包发给同一服 务器节点。 2 3 2 动态算法 2 3 2 1 无动态反馈节点负载信息 最小连接法( l c ) 。把新的连接请求分配到当前连接数最小的服务器。是 一种动态调度算法，它通过服务器当前活跃的连接数来估计服务器的负载情况 2 0 o l i n u x 集群负载调度机制的研究 最短队列法( s q f ) 。将请求分配给请求数最少的队列的节剧2 2 1 ，和最小连接 类似。 最低缺失法。调度器长期纪录各节点的请求情况，把下个请求发给历史上 处理请求最少的节点。与最小连接法不同的是，最低缺失记录的是过去的连接 数而不是当前的连接数【2 3 。 加权最小连接法( w l c ) 。最小连接调度的超集。各个服务器用相应的权 值表示其处理性能，由管理员设置权值，缺省权值为1 。在调度新连接时尽可 能使服务器的已建立连接数和其权值成比例。 基于局部性的最少链接调度法( l b l c ) 。目前主要用于c a c h e 集群系统。 针对请求报文的目标口地址的负载均衡调度，算法设计目标是在服务器的负载 基本平衡情况下，将相同目标口地址的请求调度到同一台服务器，提高各台服 务器的访问局部性和主存c a c h e 命中率。先根据请求的目标口地址找出该目标 i p 地址最近使用的服务器，若该服务器是可用的且没有超载，将请求发送到该 服务器。若服务器不存在，或者该服务器超载且有服务器处于其一半的工作负 载，则用“最少链接”的原则选出一个可用的服务器，将请求发送到该服务器。 带复制的基于局部性最少链接调度法( l b l c r ) 。 针对目标i p 地址的负载 均衡，目前主要用于c a c h e 集群系统。它与l b l c 算法的不同之处是它要维护 从一个目标p 地址到一组服务器的映射，而l b l c 算法维护从一个目标i p 地 址到一台服务器的映射。先根据请求的目标i p 地址找出该目标口地址对应的 服务器组，按“最少链接”原则从该服务器组中选出一台服务器，若服务器没有 超载，将请求发送到该服务器。若服务器超载，则按“最小连接”原则从整个集 群中选出一台服务器，将请求发送到该服务器，并将该服务器加入到服务器组 中。同时，当该服务器组有一段时间没有被修改，将最忙的服务器从服务器组 中删除，以降低复制的程度。 最短预期延时调度法( s e d ) 。分配请求给最短预期延时的服务器，预期 延时为( c i + 1 ) u i ，其中c i 为当前连接数，u i 为服务器权重，取所有服务器 中最小预期延时m i n ( c i + 1 ) u i ) 1 2 4 1 。 不排队调度法( n q ) 。用双速模型。当有空闲服务器即连接数为0 时，把 请求分配给空闲服务器：当没有空闲服务器时，把请求分配给预期延时最小的 l i n u x 集群负载调度机制的研究 服务器。 2 3 2 2 动态反馈节点负载信息 在无反馈节点状态信息的集群中加入监控软件，监控各个节点负载情况， 根据反馈的各项负载计算综合负载。 最快响应法。调度器记录自身到每一个集群节点的网络响应时间，并将下 一个到达的连接请求分配给响应时间最短的节点。这种方法要求使用i c m p 包 或基于u d p 包的专用技术来主动探测各节点。每个节点的响应时间为所有连接 的平均服务响应时剐2 5 1 。 自适应负载反馈。负载反馈不是周期性的，依据节点情况反馈负载【2 6 】。 最大权法或最小负载法。负载指标参数通过负载公式，计算出各个节点负 载，根据节点处理能力，将请求分配给最小负载的节点或将节点负载值通过某 个公式计算出节点权值，将请求分配给权值最大的节点。 以上几种算法组合或改进： 加权负载因子算法。m i n l i w i ，l i 为节点负载，w i 节点权值【2 7 1 。 最低利用率最小连接调度算法( l u c ) 。c ( s m ) x u ( s m ) = m i n c ( s i ) u ( s i ) ) ， o i n i t 调用某个算法对应分量函数；编辑或删除_service() i p v s e d i ts e r v i c e ( ) 1 9 l i n u x 集群负载调度机制的研究 i p v s _ e d i t o 服务时，通过s v o s c h e d u l e r d o n e ，e i c e ( ) 调用某个算法对应分量 函数。添加新的服务器i p v s _ a d d _ d e s t 或修改服务器i p v s _ e d i td e s t 时，通过 s v c , - s c h e d u l e r - u p d a t e s e r v i c e ( ) 调用某个算法对应分量函数。当有请求时，调 度器调用i p v s _ _ s c h e d u l e o 函数选择某个算法，即通过该函数里的s v c 7 - s c h e d u l e r 一 s c h e d u l e o j 盘择已配置好的调度算法处理请求。i p _ v s _ s e r v i c e 数据结构如表3 3 表3 3 i p _ v s _ s e r v i c e 数据结构 s t r u c ti p _ v s _ s c h e d u l c rs c h e d u l e r 调度算法 v o i d s c h c d _ d a t a ；调度算法应用数据 ( i ) 轮转调度算法( r o u n d r o b i n ，缩写r r ) 。 图3 3 轮转调度算法 以轮转的方式依次将请求调度到不同的服务器上，它无需记录服务器当前 2 0 l i n u x 集群负载调度机制的研究 所有连接的状态，所以它是一种静态调度，算法简洁，占用开销少，当权值为 0 不给分配任务。在内核实现的代码流程如图3 3 。 其中在调度开始前i rv si ti n i ts v c 函数和i pv si tu p d a t es v c 函数将 s v o - s c h e dd a t a 值设置为s v c - d e s t i n a t i o n ，即指向所有真实服务器链表的首地 址，当有任务时调用i p函数里不断改变值。vs i ts c h e d u l e s v c - s c h c dd a t a r r 算法中如果没有真实服务器则一直反复循环判断。 ( 2 ) 加权轮转调度算法( w e i g h t e c lr o u n d r o b i n ，缩写w r r ) 。该算法根 据权值的高低顺序按照轮转的方式将任务请求分配到各个节点，即节点任务的 分配是按照各个节点权值占权值总数的比例来进行分配。服务器缺省默认权值 是l 。内核代码实现流程如图3 4 。 2 l l i n u x 集群负载调度机制的研究 图3 4 加权轮转调度算法 图3 4 中m a r k 是i p _ v s _ w r r _ m a r k 结构体类型的变量，数据结构如图3 5 v s w r r i n i t s v c o v s w r ru p d a t e _ s v c ( ) s t r u c ti pv s _ _ w r r _ m a r k l i s t h e a d 奎d ；当前链表指针 i n tc w ；当前调度的权值 h a tm w ；所有服务器中的最大权值 i i l td i ； 所有服务器的最人公约数 图3 5 i p _ v s _ _ w r r _ m a r k 数据结构 l i n u x 集群负载调度机制的研究 其中在调度开始前i pv sw i ti n i ts v c 函数初始化一个将i pv s 、mm a r k 结 构体变量m a r k ，链表指针m a r k - c l 指向s v c 一 d e s t i n a t i o n ，即指向所有服务器链 表首地址，s v c - s c h e d d a t a 指向m a r k , i p _ v s _ w