（计算机软件与理论专业论文）linux集群系统任务调度策略的研究与设计.pdf

河海大学硕十研究生毕业论文l i n u x 集群系统任务调度策略的研究与设计 摘要 互联网用户数和网络流量的迅速增长，对网络服务器的可扩展性和可用性提 出了更高的要求。解决这方面的问题，便是本文研究和探讨的目的。 传统的单服务器模式己经不能应对不断增长的负载。高性能服务器集群系统 将成为实现高可扩展、高可用网络服务的有效体系。 l i n u x 是当今发展最为迅速并引起相当关注的操作系统之一。随着人们对 l i n u ) ( 服务器依赖的加深，用“n u x 集群技术构建网络服务器就成为了未来网络 服务器的发展的一个方向。 用集群技术构建网络服务器的基本思路就是把原先独立的服务器通过网络 技术连接起来，作为一个整体( 集群系统1 对外提供服务，并且要把到达的服务请 求分配到集群中的各台服务器上，让它们均衡的分摊负载，缩短对访问的响应时 间。在集群系统的构建中其核心问题是实现服务器问的负载均衡，它直接关系到 集群系统的系统性能和可扩展性及可用性。 本文主要研究了l i n u x 下负载均衡集群系统的原理、技术、思想，并对现有 的l i n u x 负载均衡算法进行改进，使之能更好地应用于生产实践。 本文阐述了集群l v s 集群框架下负载均衡的概念、原理及其体系结构。并 深入分析基于i p 层的l v s 转发结构及其调度算法，在l v s 集群软件的基础上提 出一种新的具有良好适应性的动态反馈负载均衡算法。目前，l s 软件共有八种 调度算法，它们均属于静态调度算法，由于静态调度算法在很大程度上依赖于调 度任务和服务器的静态属性，显然，任务具有负载非均衡性，且外界环境也在不 断变化，因此通常静态算法未能很好地实现负载的均衡。为了将任务更均衡地分 配给各后端服务器，作者提出了动态反馈负载均衡算法。动态反馈算法通过监视 和评估各个服务器的当前负载，然后由此选择最适合的服务器去处理新的任务。 论文具体阐述了算法的设计思想、框架，细致地论述了动态反馈负载均衡算 法、及其实现方法。并实现了对整个系统的冗余保护。 最后，通过负载压力测试工具进行了大量负载均衡测试。测试结果表明，本 论文所提出的动态反馈负载均衡算法在负载均衡的过程中具有比原来负载均衡 算法更好的调度性能。同时它具备容错特性，因此系统可靠性也得到提高。 关键词：动态反馈，负载均衡，虚拟服务器( l s ) ，集群，高可用性，压力测试 河海大学硕士研究生毕业论文l 岫u x 集群系统任务调度策略的研究与设计 a b s t r a c t t h e e x p l o s i v eg r o w t ho f t l l ei m e m e ta p p l i c a t i o n sr e q u i r e st h a t 、v e bs e r v e r ss h o u i d h a v em o r es c a l a b i l i t ya n dm o r ea v a i l a b i l i t yi t i st h ep u r p o s eo ft h j sp a p e rt of i n do u t s o m ew a yt os o l v et i l o s ep m b l e m s as j n g l es e r v e rc a l l n o ts a t i s 母t 1 ei n c r e a s i n gd e m a n d t h es e r v e rc l u s t e r ，w l l i c hi s a e to fa u t o n o m o u ss e r v e r sc o r u l e c t e db yah i 2 hp e r f o r m a n c en e t w o r k ，b e c o m e st h e e f f b c t i v ew a yt or e a l i z em eh i g hs c a l a b i l i t ya n d l i g ha v a i l a b i l i t yo fw e bs e r v e r s y s t e m l i n u xi so n eo ft h eo p e r a t m gs y s t e m s ，w h i c hh a sb e e nr a p i d l yd e v e l o p p e d r e c e n t l y ，w i mm o r ed e p e n d e n c eo nl i 眦xs e r v e r s ，b u i l d i n gu pw e bs e r v e r sb yu s i n g c l u s t 甜n gt e c h n o l o g yb a s e do nl i n u xi so n eo r i e n t a t i o no ff u t u r ew e bs e r v e r s t h e p r i n c i p l e o f c l u s t e r i n g i s t oc o n n e c tas e t o f a u t o n o m o u ss e n e r s b va n e “v o r l ( a saw h o l e ，w h i c ho 仃e r ss e r “c e st ot l l ea p p l i c a t i o nr e q u e s t sa n dd i s t r i b u t e st h o s e r e q u e s t st ot h ei i l d i v i d u a ls e r v e r si nt 1 1 ec l u s t e rs oa st om a k ew o r k l o a db a l a l l c e d 锄d t os h o r t e nt l er e s p o n s et i n l e t h ew o r k l o a db a i a i l c i n gi sr e l a t e dt o 山ep e r f b r 玎衄n c ea s w e l la st h es c a l a b i l 埘a n da v a i l a b i l i t yo ft 1 1 ec l u s t e rs y s t e m i ti sm ek e yi s s u eo f b u i l d i n gu pa s e r v e rc l u s t e r t h ep r i n c i p l ea 1 1 dt e c h n 0 1 0 9 yo fl i n l l ) w o 删0 a db a l a n c i n gw e r ei n 仃o d u c e da 1 1 d s o m ei m p r o v e da l g o r i m mw a sd e s i g n e db a s e do ne x i s t i n go n e si nt l l ep 印e r t h ec o n c e p t i o n ，p r i n c i p l ea 1 1 da r c h i t e c t u r eo fl i n u xw o r k l o a db a l a n c i l l gw e r e a 1 1 a l y z e di nd e t a i l b a s e do nm ea n a l v s i so fe x i s t i n gt e c h n 0 1 0 9 i e s ，aw o r k l o a db a l a n c e dl i n u x s y s t e mc o u l db eb u i l tu pb yu s i n gaf e e d b a c ks c h e d u l i n ga l g o r i t h i na sa i le x t e r l s i o nt o 【s ，w m c hi m p m v e de x i s t i n ge i g h ts t a t i cs c h e d u l i n ga l g o r i t h m s a si ti sw e l lk n o w n ， m es t a t i cs c h e d u l i n ga l g o r i t l l m s ，w h i c hd e p e n dg r e a t l yo nm et a s k s lo rs e r v e r s s t a t i c a t t r i b u t e s ，c o u l d n l td i s t r i b u t et h ew o f l 【1 0 a de v e i l l y 锄o n gac l u s t e ro fb a c k e n ds e r v e r s ， d u et ot h et a s k s u n b a l a j l c i n 2a n dt l l ed y n 锄i ce i i r o m n e n t t h ed v n 锄i c b e d b a c k s c h e d u l i n gr e q u i r e ss o m em e c h a i l i s mf o rm o n i t o n ga n de v a l u a t i n gt l l ep r e s e n t w o r k l o a do ne a c hs e r v e r s ot h a ti tc o u l ds e l e c tt l l er i g h ts e r v e rt ou n d e n a l ( et h e i n c o m i n gt a s k 1 1 1 e 厅啪e w o r ka 1 1 di m p l e m e n t “o no ft h ed y n 帅i cf e e d b a c ks c h e d u l 啦w c r e i n c l u d e di nt h ep 印e r f i n a l ly t 1 1 ew o r k l o a db a l a n c i n gt e s t sh a db e e nc a r r i e do u tw i t hm eh e l po fl o a d t e s t i n gt o o l s t h et e s tr e s u l ts h o w e dt h a tt i l ed y n a m i cf e e d b a c kw o r k l o a db a l a n c i n g s c h e d u l i n gp r o p o s e di nt 1 1 ep a p e rh a db e t t e rp e r f b m l a n c ei nt h ew o r “o a db a l a n c i n g p m c e s st 1 1 a i lt h o s eo ft l l ee x i s d n ga l g o r i m m s i na d d i t i o n ，i tw a s 扬吡l tt o l e r a n t a n d t h e r e f o r et h es y s t e mr e l i a b i l i t yc o u l da l s ob ei m p r o v e d k e y w o r d ：d y n 锄i cf e e d b a c k ，w o r k l o a db a l a l l c e ，l v s ，c l u s t e lh i g ha v a i l a b i l i t y lw o 棚o a dt e s t 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一 同工作的同事对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 毒乒自再一 2 0 0 6 年5 月1 5 日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术 期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件 或电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论 文外，允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊 登) 授权河海大学研究生院办理。 论文作者( 签名) ：2 0 0 6 年5 月1 5 日 河海大学硕士研究生毕业论文l i n u x 集群系统任务调度簧略的研究与设计 1 1 引言 第一章绪论 众所周知，当今计算机技术已进入以网络为中心的发展时期。由于b s 模型 的简单性、易管理性和易维护性，b s 计算模式在网上被大量采用。在九卜年代 中期，万维网( w o r l dw i d ew e b ) 的出现以其简单操作方式将图文并茂的网上信息 带给普通大众，w e b 也正在从一种内容发送机制成为一种服务平台，大量的服务 和应用( 如新闻服务、网上银行、电子商务等) 都是围绕着w e b 进行。这不仅促使 i n t e r n e t 用户剧烈增长，同时导致i n t e r n e t 流量爆炸式地增长。 i n t e r n e t 技术和应用的飞速发展给网络带宽和服务器带来巨大的挑战。从网 络技术的发展来看，网络带宽的增长伴随处理器速度和内存访问速度的增长，如 1 0 0 me t h e r n e t 、a t m 、g i g a b i te t h e r n e t 等不断地涌现，1 0 g i g a b ne t h e r n e t 即将面世，在主干网上密集波分复用( d w d m ) 将成为宽带i p 的主流技术1 1 】 2 】， l u c e n t 已经推出在一根能够支持8 0 0 g i g a b i t 的w a v e s t a r0 l s8 0 0 g 光纤产品【3 】o 所以，可以相信越来越多的瓶颈会出现在服务器端。很多研究显示g i g a b i t e t h e r n e t 在服务器上很难使得其吞吐率达到1 g b s 的原因是协议栈( t c p i p ) 和 操作系统的低效，以及处理器的低效，这需要对协议的处理方法、操作系统的调 度和i 0 的处理做更深入的研究，在高速网络上，重新设计服务器上的网络服务 程序也是个重要课题。 比较热门的站点会吸引前所未有的访问流量，例如根据y a h o o 的新闻发布， y a h o o 已经每天发送6 2 5 亿页面口j 。一些网络服务也收到巨额的流量，如 a e r i c a n0 n l i n e 的w e bc a c h e 系统每天处理5 0 2 亿个用户访问w e b 的请求， 每个请求的平均响应长度为5 5 k b y t e s 。与此同时，很多网络服务因为访问次数 爆炸式地增长而不堪重负，不能及时处理用户的请求，导致用户需要长时间的等 待，因而大大降低了服务质量。如何建立可伸缩的网络服务来满足不断增长的负 载需求己成为迫在眉睫的问题。 大部分网站都需要提供每天2 4 小时、每星期7 天的服务，对电子商务等网 站尤为突出，任何服务中断和关键性的数据丢失都会造成直接的商业损失。例如， 根据d e l l 的新闻发布l ，d e l l 现在每天在网站上的交易收入为一千四百万美 元，个小时的服务中断都会造成平均五十八万美元的损失。所以，这对网络服 务的可靠性提出了越来越高的要求。 现在w e b 服务中越来越多地使用c g i 、动态主页等c p u 密集型应用，这对服 河海大学硕士研究生毕业论文 l i n u x 集群系统任务调度策略的研究与设计 务器的性能有较高要求。未来的网络服务会提供更丰富的内容、更好的交互性、 更高的安全性等，需要服务器具有更强的c p u 和i 0 处理能力。例如，通过 h t t p s ( s e c u r eh t t p ) 取一个静态页面需要的处理性能比通过h t t p 的高一个数量 级，h t t p s 正在被电子商务站点广泛使用。所以，网络流量仅仅是问题的一个方 面，应用本身的发展也需要越来越强的处理性能。 想要解决上述问题，简单的通过提高单个硬件性能并不是一个行之有效的途 径，因为单台服务器的性能总是有极限的，而对称多处理s m p f 5 】结构的计算机， 在性能上会受到c p u 数量、主存和总线带宽的制约，可扩展性好的大规模并行处 理机m p p s 则存在使用困难、支撑软件少、应用领域窄等问题。集群( c l u s t e r ) 是由普通p c 服务器或工作站通过高速网络连接而成，结合了 ：作站集群( n o w ) 系统、 l p p 技术及s m p 技术的特点，充分利用了网络及单机性能优势，成为高性 能计算机体系结构的发展趋势。作为新兴的并行计算机的一种，集群( c l u s t e r ) 系统还具有性能价格比高、可扩展性好等特点。集群系统实现的目的就是让系统 中的各个节点协同工作，从而提供更高的性能。在目前的集群解决方案中，已经 能够从性能、可用性、并行处理、并行网络服务的多方面实现多节点间的协同工 作，因此，集群技术成为了高性能计算领域令人瞩目的焦点1 6 】1 7 】1 8 j 。 1 。2 集群系统简介 一、集群系统的基本概念和特点 把多台同构或异构的计算机通过网络连接起来，用于完成特定的任务的系统 称为集群系统。集群系统中的计算机称为“节点”。因此，也可以蜕，集群系统 是通过高性能网络所组成的节点的集合。 堙 性能 超级计算帆系统性价比曲线 堙 虫 性能 集群系统性价比曲线 图1 1 超级计算机系统和集群系统的性能价格比曲线图 个集群系统应该具有以下的几个特点【9 】： i ) 高性价比对于能够提供相同计算能力的集群系统与传统的超级计算机来说，前 河海大学硕士研究生毕业论文l i n u x 集群系统任务调度策略的研究与设计 者的价格远远低于后者。对于传统的超级计算机来说，性能的提升意味着价格的 急剧上升，而集群系统仅仅需要增加相应的计算节点，就可以获得性能的提升而 不需要大笔的投资。超级计算机系统和集群系统的性价比曲线如图1 1 所示。 2 ) 资源共享集群系统能有效地支持不同位置的用户对信息和资源( 硬件和软件) 的共享。 3 ) 灵活性和可扩展性。集群系统i = j 丁以增量扩展，并能方便地修改或扩展系统以适 应变化的环境而无需中断其运行。 4 ) 实用性和容错性。依靠存储单元和处理单元的多重性，集群系统具有在系统出 现故障的情况一下继续运行的潜力。 5 ) 可伸缩性。集群系统能容易地扩充以包括更多的资源( 硬件和软件) 。 二、集群系统的分类 通常情况下，将集群分为两大类，高可用集群和高性能集群i l l 】。 高可用性集群的主要功能就是提供不间断的服务。有许多应用程序都必须一 天二十四小时地不停运转，例如所有的w e b 服务器、工业控制器、a t m 、远程通 讯转接器、医学与军事监测仪以及股票处理机等。对这些应用程序而言，暂时的 停机都会导致数据的丢失和灾难性的后果。对于这类应用，主要关注的是集群的 可靠性特性。 高性能集群通过将多台机器连接起来同时处理复杂的计算问题。天气预报的 数值计算、模拟星球附近的磁场、预测龙卷风的出现、定位石油资源的储藏地等 情况都需要对大量的数据进行处理。 三、集群系统所采用的操作系统 美国d e c 公司( d i g i t a le q u i p m e n tc o r p o r a t i o n ) 的v m s c l u s t e r 系统开发的 最早，技术成熟，应用也很广泛，但由于v m s 操作系统只能在d e c 公司的v a x 系列和a l p h a 系列服务器上运行，v m s c l u s t e r 的应用受到很大限制。u n i x 系统 是服务器或工作站上普遍使用的操作系统，它运行稳定、安全性也比较好，因此 许多大的公司都采用了基于u n i x 的集群系统解决方案，如d e c 、h p 、s u n 、i b m 、 n c r 和d g 等公司，其中在国内影响比较大的主要有d e c 、h p 、s u n 和i b m 。其中 d e c 公司的t r u c l u s t e r 系统提供了由4 台d i g i t a la l p h as e r v e r 组成的集群系 统，它集高可靠性、高可用性和易管理性于一身，是关键业务计算机系统的理想 解决方案。 基于w i n d o w sn t 的集群系统解决方案厂商主要有m i c r o s o f t 和d e c 。 m i c r o s o f t 于1 9 9 5 年就开始了集群系统的开发工作。w i n d o w s2 0 0 0 中增加了集 群功能，该高可用性集群叫做w 。l f p a c k ，也叫做m i c r o s o f tc l u s t e rs e r v e r ( m c s ) 叫。它主要是在企业级对基于w in d o w sn t 服务器的应用程序提供高可用性和可 河海大学硕上研究生毕业论文 l i n u x 集群系统任务调度策略的研究与没 卜 升级性。w o lf p a c k 现在支持两个服务器，个用来对用户提供服务，另一个作 为备份服务器使用。m i c r o s o f t 下一步的日标是将w o l f p a c k 支持的节点数扩展 到1 6 个。w o l f p a c k 的缺陷在于：它只提供了两个节点的失败恢复功能，而没有 采用复杂的应用程序资源管理功能，因此在一定程度上影响了系统的高可用性、 高可靠性和可升级性。w o l f p a c k 未能支持多种操作系统，而只能运行于w i n d o w s n t 操作系统上。由于w i n d o w sn t 操作系统本身在稳定性、大型并行计算上与u n i x 系统存在较大差距，目前主要在中小型系统上应用。 随着l i n u x 操作系统的流行，目前出现了基于l i n u x 、基于p c 服务器的集群 解决方案，如i s 。l i n u x 自问世以来，就受到了人们的关注，并得到了迅猛 的发展。特别是近年来，l i n u x 已经发展成为一个高性能、高可靠性的操作系统， 可以与各种商业操作系统分庭抗礼。l i n u x 的开放源代码使得它在中小型服务器 领域成为性价比最佳的选择，有越来越多的用户选择使用l i i l u x 构建w 曲，m a i l ， p r o x y 等各种应用服务器。因此，在l i n l l ) 【平台下，研制具有自主知识产权，具 有一定通用性，满足高性能、高可用性和可伸缩性等要求的服务器集群系统软件 具有重大的研究和实用意义。另外，在l i n u x 平台上己经有一些优秀的开源代码 软件可以利用，所以，可以在前人研究的基础上做进一步的研究开发。 1 3目前集群技术的研究情况 1 3 1 集群技术的应用与发展 历史上，计算模式被明显地分为具有特定应用领域的三个范型：一是桌面工 作站或p c s ，主要用于交互式工作；二是采用对称多处理( s m p ) 结构的集中式计 算服务器【1 ，多用于计算集中或i o 集中的批处理作业；三是大规模并行处理 机( m p p s ) 1 1 4 】i ”j ，应用于科学计算和大规模的并行处理任务中。随着应用的不断 深入，用户对计算机性能提出了越来越高的需求。为此，国际上兴起了研究集群 技术的热潮。集群技术旨在把组计算机( 如工作站、微型机、大型机等) 用网络 以某种结构互连起来，充分利用各计算机资源，统一调度、协调处理，实现高效 率并行计算。集群计算的应用主要分为两大类：超级计算和事务处理。超级计算 机并行执行复杂的数学算法来求解方程，这样的集群系统常被用在基因工程、天 气预报、等需要高性能计算的领域。事务处理中的事务广义上包括数据库查询、 金融指令和常见的w e h 浏览器对文件和图像数据的请求。在这个领域中，可以在 执行事务级别上使用并行方式来获得性能提高。 1 3 2 目前集群技术研究的问题 对集群技术的研究主要集中在解决以下二类问题： 河海大学硕士研究生毕业论文n u x 集群系统任务调度策略的研究与设计 ( 1 )如何在高负载情况下保持系统性能的稳定? ( 2 ) 如何在突发系统故障情况下保证系统不停机? ( 3 )如何在需要扩展系统能力时能够既方便又保护原有的投资? 所采取的相应解决技术方案为： ( 1 ) 使用多种优化分配算法和转发机制实现负载均衡，将用户请求均衡分配 到各个节点进行处理，结果回送用户： 。 ( 2 ) 容错机制负责自动监测故障，当监测到某一节点发生故障时，将其从集 群中暂时移出，并不再向该节点分配用户请求，当此节点恢复正常后， 再将其恢复加入集群中； ( 3 ) 保证高扩展性，当添加一或若干新的节点到集群网络中时，只用修改配 置文件和状态文件，不必对系统作太多的修改。 负载均衡技术的目标在于在各节点间分配负载，均衡各节点负载，进而实现 并行计算，以减小任务响应时间。根据任务粒度的大小，负载均衡技术主要分为 两个层次：任务级和进程级，即分配和转发的是一个作业任务还是一个进程。由 于进程级负载均衡需要对进程进行切换，因而对网络通信速度和系统并行性要求 较高，现阶段实际应用较少。目前对负载均衡技术的研究主要都是针对任务级负 载均衡进行研究和开发。 1 3 3 目前成熟的集群产品介绍 t u r b o l i n u x 公司推出了能够显著地提高基于t c p i p 协议的多种网络服务的 服务质量的高可用性集群系统t u r b o c l u s t e r 【1 6 】。r e dh a t 也提供了基于l i n u x v i r t u a ls e r v e r 思想构建的高可用性集群系统p i r a n h a 。r be r i c s s o n 软件工程 研究中心开发的高可用性集群系统e d d i e 的主要目的是提供一个商业级的，具有 较好服务质量的w e b 服务器的解决方案。p l a t f o r m 公司开发的高可用性集群系 统l s f 提供了分布式集群系统的解决方案，通过将物理上分散的多个集群系统连 接在一起，使多个同构或异构的计算机能够通过局域网或广域网共享计算资源， 并能够为用户提供对资源的透明访问。 高性能集群系统m o s i x 为l i n u x 核心增添了集群计算的功能。在m o s i x 集群 环境中，用户无需对应用程序进行修改，或将应用程序与库连接起来，或将应用 程序分配到不同的节点上运行。m o s i x 会自动将这些1 作透明地交给别的节点来 执行。 日本的f 5 公司开发出了高可用性集群b i g i p ，它是应用于本地网络站点或 数据中心的高可用的、智能化的负载平衡产品，它提供了对网络流量的自动和智 能的管理。与前几种集群系统不同的是，b i g i p 向用户提供的是一个即插即用 设备，而其它产品提供的都是软件方法。 河海大学硕士研究生毕业论文l i n u x 集群系统任务调度策略的研究与设l f i b m 、m i c r o s o f t 和i n t e l 于2 0 0 0 年7 月联合发布了种高可用性服务器集 群软件包及硬件，这种服务器集群的配置包括3 2 台i b mn e t f i n i t y8 5 0 0 r 及 i n t e lp e n t i u mi i ix e o n 处理器，运行i b m 的d b zu n i v e r s a ld a t a b a s e 和 m i c r o s o f tw i n d o w s2 0 0 0a d v a n c e ds e r v e r 操作系统，每分钟可以执行4 4 0 8 7 9 次交易。这套系统面向数据密集的应用，特别是b 2 b 、电子商务和企业资源规划 领域。 在科学计算领域中，比较成功的例子是高性能集群系统r e o w u lf ，它最初是 由n a s a 的g o d d a r df l i g h tc e n t e r 进行开发的，主要目的是支持大规模的科学 计算问题，如地球和太空技术涉及的些计算问题。 1 4 本课题的研究背景和意义 随着l i n u x 操作系统的迅速发展，对l i n u x 上的集群系统的研究也成为集群 技术研究的热点。l in u x 操作系统从k e r n e l2 o 3 6 版本开始增加了对集群技术 的支持，利用伪装技术实现虚拟服务器l v s ( l i n u xv i r t u a ls e r v e r ) 。随后l v s 快速发展，分配算法从最先的只有循环法和权值循环法两种负载均衡算法，发展 到目前的循环法、权值循环法、最少连接法和权值最少连接法、基于局部性的最 少链接、带复制的基于局部性最少链接、目标地址散列调度、源地址散列调度八 种负载均衡算法：转发机制也由网络地址转换一种机制，发展到实现网络地址转 换、i p 隧道和直接路由三种机制。但是，由于l i n u x 集群技术的研究历史还不 长，l v s 还没有考虑到不同类型的请求所耗用服务器资源和网络带宽不同的情 况，而且当服务器系统繁忙时，没有对随后而来的用户请求进行缓冲处理，造成 作业频繁换进换出，系统性能下降，服务器效率降低。本文针对l i n u x 内核模块 l v s 集群在实现负载均衡方面上的不足，通过详细剖析l v 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 上应用的进一步发展有着实际意义。 1 5 内容的组织和安排 第一章：绪论。介绍了奉课题的背景和研究现状，说明了本文所做工作的意 义，最后列出了论文的各章节简介。 第二章l i n u xv i n u a ls e r v e r 集群。首先介绍了l v s 集群的概念、特点， 然后描述了l v s 集群体系结构和软件结构，并且详细分析和研究了l v s 集群的 i p 负载均衡技术。 河海大学硕士研究生毕业论文 l i n u x 集群系统任务调度策略的研究与设计 第三章动态反馈负载均衡算法的提出与设计。在分析现有调度算法性能的 基础上，提出一种新的负载均衡算法，该算法具有动态反馈机制，能够实时地反 映各实际服务器的负载状况，给出了该算法的详细设计过程。 第四章动态反馈负载均衡算法的实现。详细地介绍了动态反馈负载均衡算 法的实现方法，并对各个了模块的实现方法及设计过程进行了洋细说明。对于编 程实现过程中遇到的难点及此特殊的接口函数进行了注解。 第五章实验环境与测试结果。主要针对动态反馈负载均衡算法的性能进行 评测分析，给出了系统测试的洋细过程，包括系统测试环境的构建、测试工具、 测试内容、测试结果。最后还给出了系统冗余保护的方法。 第六章是对本文研究工作的一个总结并提出今后进一步研究的问题。 河海大学硕士研究生毕业论文l j n u x 集群系统任务调度策略的研究与设汁 第二章l i n u xv i r t u a ls e r v e r 集群 l v s 集群由一个或两个路由节点和数量很多的网络服务器组成。l v s 路由节 点称作虚拟服务器，网络服务器的汇集称作实际服务器。虚拟服务器同时连接着 内部网络和外部公共网络。把虚拟服务器与内部网络、外部公共网络连接起来的 适配器，可以是任何设备，但是每个路由上的设备必须是相同的。外面用户对 l v s 集群的服务请求，将被寻址到一个虚拟的服务器( 即主路由器或任务分配器) 上。主路由器把收到的服务请求，通过任务分配算法，均衡地分配给集群系统里 所有的实际服务器。 在同一时刻，仪有一个路由节点是激活的。激活的路由节点将虚拟服务器上 的服务请求重定向到实际服务器上，并动态地监视实际服务器的状态情况和每个 服务器的工作量。如果某一个实际服务器失效了，在工作的路由节点将停止向这 台服务器发送任务，直到此服务器恢复正常运转。 2 1l v s 集群的体系结构 l v s 集群采用i p 负载均衡技术和基于内容请求分发技术。调度器具有很好 的吞吐率，将请求均衡地转移到不同的服务器上执行，且调度器自动屏蔽掉服务 器的故障，从而将一组服务器构成一个高性能的、高可用的虚拟服务器。整个服 务器集群的结构对客户是透明的，而且无需修改客户端和服务器端的程序。 图2 1l v s 集群的体系结构 河海大学硕士研究生毕业论文l l n u x 集群系统任务调度策略的研究与设计 为此，在设计时需要考虑系统的透明性、可伸缩性、高可用性和易管理性。一般 来说，l v s 集群采用三层结构，其体系结构如图2 1 所示，三层主要组成部分为： 负载调度器( w o r k l o a d b a l a n c e r ) ，它是整个集群对外面的前端机，负责 将客户的请求发送到一组服务器上执行。它也是集群系统的唯一入口。从客户端 的角度看，集群系统通过这层的服务体现为一个基于i p 地址的单一系统映像一 s s i ( s i n g l es y s t e mi m a g e ) ，整个集群共用这个虚拟地址一v i p ，通过它客户端 可以把整个集群看作一个独立的具有合法1 p 地址的主机系统，客户端的所有访 问都发往这个虚拟l p 地址。 服务器池( s e r v e rp 0 0 1 ) ，是一组真正执行客户请求的服务器，客户端发 出的服务请求经过均衡器分折处理以后，转交到服务器集群，由具体的服务器响 应请求并返回数据。通常在服务器集群上提供w e b 、f t p 、t e l n e t 、数据库或者 视频点播等服务。由于单一系统无法应付高峰值的数据访问，那么通过多台服务 器分担这些负载就比较经济可行了。 共享存储( s h a r e ds t o r a g e ) ，它为服务器池提供一个共享的存储区，为 整个集群内部运行提供稳定、一致的文件存取服务。这一层作为l v s 集群的扩展， 可以为集群节点池提供单一的文件系统入口，即在每一台服务节点上都共用同一 个根( ) ：并且自动完成不同结点访问文件系统所引发的文件锁定、负载均衡、容 错、内容一致、读写事务等底层功能，对应用层提供一个透明的文件访问层。 调度器是服务器集群系统的唯一入口点( s i n 9 1 ee n t r yp o i n t ) ，它可以采 用i p 负载均衡技术、基于内容请求分发技术或者两者相结合。在i p 负载均衡技 术中，需要服务器池拥有相同的内容提供相同的服务。当客户请求到达时，调度 器只根据服务器负载情况和设定的调度算法从服务器池中选出一个服务器，将该 请求转发到选出的服务器，并记录这个调度；当这个请求的其他报文到达，也会 被转发到前面选出的服务器。在基于内容请求分发技术中，服务器可以提供不同 的服务，当客户请求到达时，调度器可根据请求的内容选择服务器执行请求。因 为所有的操作都是在l j n u x 操作系统核心空间中将完成的，它的调度开销很小， 所以它具有很高的吞吐率7 j 。 服务器池的节点数目是可变的。当整个系统收到的负载超过目前所有节点的 处理能力时，可以在服务器池中增加服务器来满足不断增长的负载。对大多数网 络服务来说，请求间不存在很强的相关性，请求可以在不同的节点上并行执行， 所以整个系统的性能基本一卜可以随着服务器池的节点数目增加而近似线性增长。 共享存储通常是数据库、网络文件系统或者分布式文件系统。服务器节点需 要动态更新的数据一般存储在数据库系统中，同时数据库会保证并发访问时数据 的一致性。静态的数据呵以存储在网络文件系统( 如n f s c i f s ) 中，但网络文 件系统的伸缩能力有限，一般来说，n f s c i f s 服务器只能支持3 “6 个繁忙的服 河海大学硕士研究生毕业沦文l i n u x 集群系统任务调度策略的研究与设计 务器节点。对于规模较大的集群系统，可以考虑用分布式文件系统，如a f s 、g f s 、 c o d a 和i n t e r m e z z o 等。分布式文件系统可为各服务器提供共享的存储区，它们 访问分布式文件系统就像访问本地文件系统一样，同时分布式文件系统可提供良 好的伸缩性和可用性。此外，当不同服务器上的应用程序同时读写访问分布式文 件系统上同一资源时，应用程序的访问冲突需要消解才能使得资源处于一致状 态。这需要一个分布式锁管理器( d i s t r i b u t e dl o c km a n a g e r ) 驯，它可能是 分布式文件系统内部提供的，也可能是外部的。开发者在写应用程序时，可以使 用分布式锁管理器来保证应用程序在不同节点上并发访问的一致性。 负载调度器、服务器池和共享存储系统通过高速网络相连接，如1 0 0 m b p s 交换网络、m y r i n e t 和g i g a b i t 网络等。使用高速的网络，主要为避免当系统规 模扩大时互联网络成为整个系统的瓶颈。 g r a p h i cm o n i t o r 是为系统管理员提供整个集群系统的监视器，它可以监视 系统的状态。g r a p h i cm o n n o r 是基于浏览器的，所以无论管理员在本地还是异 地都可以监测系统的状况。为了安全的原因，浏览器要通过h t t p s ( s e c u r eh t t p ) 协议和身份认证后，才能进行系统监测，并进行系统的配置和管理。 2 2l v s 软件结构 l s 软件大致可分为i p 包处理模块、调度算法模块、各类链表结构、配置 管理模块和i p v s a d m 用户程序五个部分，如图2 2 。这五部分协同上作，实现数 据报文的改写、分发，以达到负载均衡的效果。这也是l v s 的核心部分。 i p 包 i p 包处理模块l l l 调度算法模块 l t 1 _ _ j 攀 上_ l 一 墓 各类链表 量 f i p 包 配置管理信息 l v s 当前情况 ，l，：一：一 配置管理模块乍二二爿i p v s a d m 图2 2l v s 软件结构 河海大学硕士研究生毕业论文 l i n u x 集群系统任务调度策略的研究与设t f 2 3l v s 集群中的i p 负载均衡技术 在负载分配器的实现技术中，j p 负载均衡技术是效率最高的| l ”。在已有的 i p 负载均衡技术中，主要有通过网络地址转换( n e t w o r ka d d r e s st r a n s l a t i o n ) 将组服务器构成一个高性能的、高可用的虚拟服务器，称之为v s n a t 技术 ( v i r t u a ls e r v c rv i an e t w o r ka d d r e s st r a n s l a t i o n ) 。通过i p 隧道实现虚拟 服务器的方法v s t u n ( v i r t u a ls e r v e rv i ai pt u n n e l i n g ) ，和通过直接路由实 现虚拟服务器的方法v s d r ( v jr l u a ls e r v e rv i ad i r e c tr o u t i n g ) ，它们可以 极大地提高系统的伸缩性。 2 3 1 通过n a t 实现虚拟服务器s ，n a t ) 由于i p v 4 中i p 地址空间的日益紧张和安全方面的原因，很多网络使用保留 i p 地址( 1 0 o o o 2 5 5 0 o o、1 7 2 1 6 o o 2 5 5 1 2 8 o o和 1 9 2 1 6 8 o 0 2 5 5 2 5 5 0 o ) 。这些地址不在i n t e r n e t 上使用，而是专门为内部 网络预留的。当内部网络中的主机要访问i n t e r n e t 或被i n t e r n e t 访问时，就需 要采用网络地址转换( n e t w o r ka d d r e s st r a n s l a t i o n ，以下简称n a t ) 1 2 0 1 ，将 内部地址转化为i n t e r n e t 上可用的外部地址。n a t 的工作原理是报文头( 目标地 址、源地址和端口等) 被正确改写后，客户相信它们连接一个i p 地址，而不同 1 p 地址的服务器组也认为它们是与客户直接相连的。由此，可以用n a t 方法将 不同i p 地址的并行网络服务变成在一个i p 地址上的一个虚拟服务。 v s n a t ( 2 1 1 的体系结构如图2 3 所示。在一组服务器前有一个分配器。这些 服务器提供相同的网络服务、相同的内容，即不管请求被发送到哪一台服务器， 执行结果是一样的。服务的内容可以复制到每台服务器的本地硬盘上，可以通过 网络文件系统( 如n f s ) 共享，也可以通过一个分布式文件系统来提供。 客户通过v i n u a li pa d d r e s s ( 虚拟服务的i p 地址) 访问网络服务时，请求 报文到达分配器，分配器根据连接调度算法从一组真实服务器中选出一台服务 器，将报文的目标地址v i r t u a li pa d d r e s s 改写成选定服务