（计算机应用技术专业论文）linux虚拟服务器动态负载平衡算法的分析与改进.pdf

武汉理工大学硕士学位论文 摘要 随着i n t e r n e t 的爆炸性增长以及其在我们生活中日益增长的重要作用，越 来越多的网络上的服务器显得负担沉重，尤其一些提供w w w 服务及f t p 服务 的知名网站，每天浏览网站的访客更是门庭若市，非常拥挤，有时还会出现服 务器超载的隋况。为了解决服务器超载的问题，我们有两种解决方案。一种是 单服务器解决方案，即提高服务器的配备，但就实际情况来看，网络服务需求 增长如此之快，倘若为了让服务器能应付与日俱增的服务而不断更换服务主机 设备，不但相当耗用经费，而且也加重维护服务器的软件成本。 另一种则是多处理器解决方案，假设能就目前现有的设备，在无须添购新 设备的情况下，将服务器的数量扩增，让多部低级服务器分担单部高级服务器 的负担，以达到服务器的负载平衡( l o a d - b a i a n c i n g ) ，那么将可节省购置新服务 器的费用。这种以设备、效率较低的多部服务器取代单独一部设备、效率较高 的服务器的方式，称之为”群集系统”( c i u s t e rs y s t e m ) 。在这种多处理器解决 方案中，我们可以简单的增加或减少集群中服务器节点的数目以达到负载平衡， 从而充分发挥服务器的性能与利用率。由于群集系统的可升级性与较好的效益， 我们通常视其为更好的网络解决方案。 在群集系统里，之所以篚够将工作流量分配给几部服务主机分担，主要是 靠一部导引主机( d i r e c t o r ) 做分配工作。当然，导引主机不允许有死机的情况发 生。“备用系统”可有效地支持导引主机，如果导引主机意外死机后，可以由另一 部随时待命的备用主机立即取代导引主机的服务，成为群集系统里的导引主机。 l i n u x 虚拟服务器是一种比较实用的群集系统技术，各大服务器都可采用这 一新兴技术以解决服务器超载问题。但当前的l j n u 虚拟服务器技术并不是很 完善，基于这种状况，在对其核心动态负载平衡算法进行了详尽的分析后，我 对其中较常用的加权最小连接调度算法提出了改进算法一加权负载因子调度 算法，并在l i n u x 内核中实现了该算法，从而使l i n u x 虚拟服务器集群的效率 得以改进，具有较强的实用价值。 关键词：负载平衡、l i n u x 虚拟服务器、加权最小连接调度、加权负载因子调度 i i 武汉理工大学硕士学位论文 a d s t r a c t w i mt l = l ee x p l o s i v eg r o w mo ft h eh l t e m e ta n di t si n c r e a s i n g l yi i n p o r t 锄tr o l ei n o u rl i v e s ，t h et r a 丘l co nt h ei n t e m e ti si n c r e a s i n gd 1 _ a r n a t i c a l ly ，w h j c hh a sb e e n 掣d w i n ga to v e rl o o a 1 1 n u a lr a t e t h ew o r l d o a do nm es e r v e r si si n c r e a s i n gr 印i d l y s ot h a ls e r v e r sw i l lb ee a s i l yo v e r l o a d e df o ras h o r tt i m e ，e s p e c i a l l yf o rap o p u l a rw e b s j t ew i l i c hp r o v i d e sw w f 硒s e r v i c e t bo v e r c o m e 廿1 eo v 芒m o a d i n gp r o b l 锄o fm e s e r v e r s ，m e r ca r et w os o l u t i o i l s o n ei st h es i n g l es e r v e rs o l u t i o n ，i e t ou p 昏a d et l e s e n r e rt oa h j g h e rp e r f b r n l a n c es e r v e r ，b u ti tw i l is o o nb eo v e r l o a d e dw h c nr e q u e s t s i n c r e a s e ss o 恤a tw eh a v et ou p 铲a d e “a g a i n ，t h eu p f a d i n gp r o c e s si sc o m p l e xa i l d 1 ec o s ti s l l i 曲 t h eo t l e ri st h em u l t i p l es e e rs o l u t i o n ，i e t ob u i l das c a la _ b l en c t w o r ks e r v i c e s y s t e mo nac l u s t e ro fs e n ，e r s w h e nl o a di n c r e a s e s ，w ec a l ls i n l p l ya d dan e ws e r v e r 0 rm o f ei n l oc l u s t e rt om e e tm ei n c r e a s i n g ”q u e s t s ，a n dc o m m o d i t ys e c ri so f h j g h e s tp 耐b r i n a n c e c o s tr a t i o t h e r e f o r e ，i fi sm o r es c a l a b l ea 1 1 dm o r ec o s t e f r e c t i v e t ob u i l ds e n ，e rc l u s t e rs y s t e mf o rn e 晰o r ks e i c e s 1 1 1c l u s t 仃s y s t e m ，由ed i r e c t o rd o e st h e j o bt 0 船s i g t l 血ew o r k1 0 a dt oe a c hs e f v e rw i mt l l e s u p p o r to f 廿1 eb 8 c k l l ps y s t e m w h e nd i r e c t o rb r e a k sd o w n ，吐i eb a c k u ps y s t e mc a n i n l m e d i a t e l yr c p l a c em ec u r r e ms e r v i c ew i t hab a c k i l ps e n ，e r l i n i v i r m a ls e r v e ri sm et e c l l n o l o g yb u i l to nac i u s t e rs y s t e mw h i c hc a nb el l s e dt o o v e r c o m em ed v e r l o 删r 培p r o b l e f no fm es e r v e f s s i n c e 也et e c h n 0 1 0 9 yo f1 i n u xv i m l a ls e n ，e rl s n o tp 曲c 01w o u l dl i l el ob 血gf b l w 删l h en e w8 l g 枷t 1 1 i nf c rw e i g h t e d1 e a s t 嵋o n n e c n o n s c h e d u l i n gw h i c hc a l l e dw 唾r h t e dl o a d f a c t o rs c h e 血1 i n ga l g o 血b i l lt l | 0 u 吐ac o m p l e t e da n a l y s i s f 研l v sd y n a i n i ci o a d _ b a i 柚c i n ga l g o r i 恤m n l c nir e a h z c d l yi d e ai nl i n l l ) 【k e m e ls oa st 0 i m p r o v e 血ee f n c i e n c yo f l i m v i n u a ls e e rc i u s t e rs y s t 咖 k e y w o r d s ：l 0 a d - b a l a n c i n g 、l i n l l 】【r t l l a ls e r v e r 、w e i g l l t e dl e a s t _ c o n n e c 如ns c h e d i l l i n 卧 w e i g h t c dl o a d f a c t o rs c h e d u l i n g i i i 武汉理工大学硕士学位论文 第1 章引言 1 1 本论文的研究背景、目标与意义 当今计算机技术已进入以网络为中心的计算时期。由于客户朋匣务器模型的 简单性、易管理性和易维护性，客户月艮务器计算模式在网上被大量采用。在九 十年代中期，万维网( w o r l dw i d ew e b ) 的出现以其简单操作方式将图文并 茂的网上信息带给普通大众，w e b 也正在从一种内容发送机制成为一种服务平 台，大量的服务和应用( 如新闻服务、网上银行、电子商务等) 都是围绕着w e b 进行。这促进i n t e m e t 用户剧烈增长和i n t e m e t 流量爆炸式地增长，图1 1 显示了1 9 9 5 至2 0 0 0 年与i n t e m e t 连接主机数的变化情况【1j ，可见增长趋 势较以往更迅猛。 型鳖她紫 ，互3 ，基0 9 2 i _ t t - k； ? l _ f t 非 _ _ t _ _ 目 幺 # l ，v d i 4 ， r _ 一一 - w u m 9 * f 埘曲 t 锄舯啪 拍加 瑚鲫 5 a 舯旺0 棚叩 伽n o 细瑚 1 a 觚o 0 j 柙_ 抽n 硼出h 盯j 排嗣山n _湘椭 图1 一l1 9 9 s 至2 0 0 0 年i n t e m e t 主机数的变化 i n t e m e t 的飞速发展给网络带宽和服务器带来巨大的挑战。从网络技术的 发展来看，网络带宽的增长远高于处理器速度和内存访问速度的增长，越来越 多的网络上的服务器显得负担沉重，尤其一些提供w w w 服务及f t p 服务的知 名网站，每天浏览网站的访客更是门庭若市，非常拥挤，有时还会出现服务器 超载的情况。身为网站的经营者欣喜来客不断，但也面临着提高网络服务品质 武汉理工大学硕士学位论文 的压力。就这种情况而言，一般会选择单服务器解决方案，即提高服务器的配 备，但就实际情况来看，网络服务需求增长如此之快，倘若为了让服务器能应 付与同俱增的服务而不断更换服务主机设备，不但相当耗用经费，而且也加重 维护服务器的软件成本。 假设能就目前现有的设备，在无须添购新设备的情况下，将服务器的数量 扩增，让多部低级服务器分担单部高级服务器的负担，以达到服务器的负载平 衡( l o a d - b a l a n c i n g ) ，那么将可节省购置新服务器的费用。这种以设备、效率较 低的多部服务器取代单独一部设备、效率较高的服务器的方式，称之为”群集系 统”( c i u s t e rs y s t e m ) 。在这种多处理器解决方案中，我们可以简单的增加或减 少集群中服务器节点的数目以达到负载平衡，而且当这些提供服务的主机中有 部( 或多部) 死机后，群集系统会避开这部已停止服务的服务主机而改用其它正 常的主机，继续做负载平衡的工作。 在群集系统里，之所以能够将工作流量分配给几部服务主机分担，主要是 靠一部导引主机( d j r e c t o r ) 做分配工作。当然，导引主机不允许有死机的情况发 生。“备用系统”可有效地支持导引主机，如果导引主机意外死机后，可以由另一 部随时待命的备用主机立即取代导引主机的服务，成为群集系统里的导引主机。 l l n u x 虚拟服务器( l v s ) 就是在r e d h a tl i n u 下实现群集系统的技术。以 章文嵩博士为首的开放源码及l | n u x 内核的开发者们给出了基于i p 层和基于内 容请求分发的负载平衡调度解决方法，并在l n u 内核中实现了这些方法，将 组服务器构成一个实现可伸缩的、高可用网络服务的虚拟服务器l 2 】。l i n u x 虚拟服务器技术的应用价值很大，我们可采用这新兴技术以解决服务器超载问 题，尤其在大型网站服务中可有突出表现，使用l i n u 虚拟服务器技术来构建 服务器群集系统是将来的必然趋势。但是当前的l i n u x 虚拟服务器技术并不是 很完善，基于这种状况，对于l v s 动态负载平衡算法进行优化，使之具有更强 的效率和实用性，是非常具有现实意义的。 1 2 论文的章节安排 本文内容章节安排如下： 第2 章介绍了l j n u x 虚拟服务器基本技术，包括l j n u x 虚拟服务器的基本 概念、通用体系结构以及工作原理 武汉理工大学硕士学位论文 第3 章通过对l i n u 内核源代码分析后，给出了8 种常用动态负载平衡调 度算法：轮叫调度、加权轮叫调度、最小连接调度、加权最小连接调度、基于 局部性的最少链接、带复制的基于局部性最少链接、目标地址散列调度和源地 址散列调度算法的工作原理和算法流程。 第4 章对应用最广泛的加权最小连接调度算法提出改进方案- 加权负载因子 调度算法，并在l n u x 内核源代码中得以实现。 第5 章构建了一个l i n u x 虚拟服务器群集系统来测试改进后的动态负载平 衡算法。 武汉理工大学硕士学位论文 第2 章l i n u x 虚拟服务器技术概述 2 1l n u x 虚拟服务器的基本概念 l i n u x 虚拟服务器的体系结构如图2 - 1 所示，一组服务器通过高速的局域 网或者地理分布的广域网相互连接，在它们的前端有个负载调度器( l o a d b a j a n c e r ) 。负载调度器能无缝遗将网络请求调度到真实服务器上，从而使得 服务器集群的结构对客户是透明的，客户访问集群系统提供的网络服务就像访 问一台高性能、高可用的服务器样。客户程序不受服务器集群的影响不需作 任何修改。系统的伸缩性通过在服务机群中透明地加入和删除一个节点来达到， 通过检测节点或服务进程故障和正确地重置系统达到高可用性。由于负载调度 技术是在l i n u x 内核中实现的，因此称之为u n u x 虚拟服务器( l i n u xv i r 七u a s e n 悒r ) 。 图2 1 虚拟服务器的结构 4 武汉理工大学硕士学位论文 l n u v i r t u a is e r v e r 项目l ”j 的目标：使用集群技术和l i n u x 操作系统实 现一个高性能、高可用的服务器，它具有很好的可伸缩性( s c a j a b i i i t y ) 、可 靠性( r e l i a b i l i t y ) 和可管理性( m a n a q e a b i l ；t v ) 。 目前，l v s 项目已提供了一个实现可伸缩网络服务的l i n u x v i r 七u a i s e r v e r 框架，如图2 2 所示。在l v s 框架中，提供了含有三种i p 负载均衡技术的i p 虚拟服务器软件i p v s 、基于内容请求分发的内核l a y e 卜7 交换机k t c p v s 和 集群管理软件。可以利用l v s 框架实现高可伸缩的、高可用的w e b 、c a c h e 、 m a i l 和h e d i a 等网络服务；在此基础上，可以开发支持庞大用户数的、高可伸 缩的、高可用的电子商务应用。 l i 冉u xv i 舢捌s 聿r v 螺rf r 枷咐r k 图2 - 2l i n u x 虚拟服务器框架 2 2l i n u 虚拟服务器的通用体系结构 l v s 集群 1 4 【1 5 】采用i p 负载均衡技术和基于内容请求分发技术。调度器 具有很好的吞吐率，将请求均衡地转移到不同的服务器上执行，且调度器自动 屏蔽掉服务器的故障，从而将一组服务器构成一个高性能的、高可用的虚拟服 务器。整个服务器集群的结构对客户是透明的，而且无需修改客户端和服务器 端的程序。 武汉理工大学硕士学位论文 。、 r e 3 w n 。 一 l o a d 豳i a n c e rs 时v e rc i u s t e r s t o r g e 图2 3l v s 集群的体系结构 为此，在设计时需要考虑系统的透明性、可伸缩性、高可用性和易管理性。 一股来说，l v s 集群采用三层结构，其体系结构如图2 - 3 所示，三层主要组成 部分为： 负载调度器( i o a db a i a n c e r ) ，它是整个集群对外面的前端机，负责 将客户的请求发送到一组服务器上执行，而客户认为服务是来自一个i p 地址( 我们可称之为虚拟i p 地址) 上的。 服务器池( s e e rp o o i ) ，是一组真正执行客户请求的服务器，执行 的服务有w e b 、m a i l 、f t p 和d n s 等。 6 画厘删量 武汉理工大学硕士学位论文 共享存储( s h a r e d 髓o r a g e ) ，它为服务器池提供一个共享的存储区， 这样很容易使得服务器池拥有相同的内容，提供相同的服务。 调度器是服务器集群系统的唯一入口点( s j n g i ee n t r yp o i n t ) ，它可以采 用i p 负载均衡技术、基于内容请求分发技术或者两者相结合。在i p 负载均衡 技术中，需要服务器池拥有相同的内容提供相同的服务。当客户请求到达时， 调度器只根据服务器负载情况和设定的调度算法从服务器池中选出一个服务 器，将该请求转发到选出的服务器，并记录这个调度；当这个请求的其他报文 到达，也会被转发到前面选出的服务器。在基于内容请求分发技术中，服务器 可以提供不同的服务，当客户请求到达时，调度器可根据请求的内容选择服务 器执行请求。因为所有的操作都是在l i n u x 操作系统核心空间中将完成的，它 的调度开销很小，所以它具有很高的吞吐率。 服务器池的结点数目是可变的。当整个系统收到的负载超过目前所有结点 的处理能力时，可以在服务器池中增加服务器来满足不断增长的请求负载。对 大多数网络服务来说，请求间不存在很强的相关性，请求可以在不同的结点上 并行执行，所以整个系统的性能基本上可以随着服务器池的结点数目增加而线 性增长。 共享存储通常是数据库、网络文件系统或者分布式文件系统。服务器结点 需要动态更新的数据一般存储在数据库系统中，同时数据库会保证并发访问时 数据的一致性。静态的数据可以存储在网络文件系统( 如n f s c r f s ) 中，但 网络文件系统的伸缩能力有限，一般来说，n f s c i f s 服务器只能支持3 6 个 繁忙的服务器结点。对于规模较大的集群系统，可以考虑用分布式文件系统， 如a f s f 3 1 、g f s f 4 】【5 】、c o d a 6 】和i n t e r m e z z o f 7 等。分布式文件系统可为 各服务器提供共享的存储区，它们访问分布式文件系统就像访问本地文件系统 一样，同时分布式文件系统可提供良好的伸缩性和可用性。此外，当不同服务 器上的应用程序同时读写访问分布式文件系统上同一资源时，应用程序的访问 冲突需要消解才能使得资源处于一致状态。这需要一个分布式锁管理器 ( d i s t 广b u 七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 ch o n i t o r 是为系统管理员提供整个集群系统的监视器，它可以监 视系统的状态。g r a 口h i ch o n i t o r 是基于浏览器的，所以无论管理员在本地还 是异地都可以监测系统的状况。为了安全的原因，浏览器要通过h t t p s ( s e c u r e h 丁r p ) 协议和身份认证后，才能进行系统监测，并进行系统的配置和管理。 2 3l i n u 虚拟服务器的工作原理 2 3 1 负载平衡的实施方式 实施负载平衡【1 6 【1 7 】n 8 】【1 9 】的方式可分为两种：一个是在”应用 层”( a p p “c a t i o n - l e v e l ) 实行，另一个在”i p 层”( i p l e v e l ) 实行。 在应用层实行负载平衡的实施方式是：多台服务器通过高速的互联网络连 接成一个集群系统，在前端有一个基于应用层的负载调度器。当用户访问请求 到达调度器时，请求会提交给作负载均衡调度的应用程序，分析请求，根据各 个服务器的负载情况，选出一台服务器，重写请求并向选出的服务器访问，取 得结果后，再返回给用户。由于h t t p 请求与回复封包的改写发生在t c p i p 机制里的a p p c a t i o n - l e v e l ，故称为”应用层负载平衡”。应用层负载均衡调度 的典型代表有z e u s 负载调度器f 8 1 、p w e b 9 1 、r e v e r s e p r o y 1 0 增口s w e b 1 1 】 等。 基于应用层负载均衡调度的多服务器解决方法存在许多问题。第一，系统 处理开销特别大，致使系统的伸缩性有限。当请求到达负载均衡调度器至处理 结束时，调度器需要进行四次从核心到用户空间或从用户空间到核心空间的上 下文切换和内存复制；需要进行二次t c p 连接，一次是从用户到调度器，另一 次是从调度器到真实服务器；需要对请求进行分析和重写。这些处理都需要不 少的cpu 、内存和网络等资源开销，且处理时间长。所构成系统的性能不能 接近线性增加的，一般服务器组增至3 或4 台时调度器本身可能会成为新的 瓶颈。所以，这种基于应用层负载均衡调度的方法的伸缩性极其有限。第二， 基于应用层的负载均衡调度器对于不同的应用，需要写不同的调度器。以上几个 武汉理工大学硕七学位论文 系统都是基于h 丌p 协议，若对于f t p 、ma i | 、p o p 3 等应用，都需要重写调度器。 而在i p 层负载平衡的实施方式则是：用户通过虚拟i p 地址( v i r t u a li p a d d r e s s ) 访问服务时，访问请求的报文会到达负载调度器，由它进行负载均 衡调度，从一组真实服务器选出一个，将报文的晷标地址v l r t u a li pa d d r e s s 改写成选定服务器的地址，报文的目标端口改写成选定服务器的相应端口，最 后将报文发送给选定的服务器。真实服务器的回应报文经过负载调度器时，将 报文的源地址和源端口改为v i r 七u a ii pa d d r e s s 和相应的端口，再把报文发给 用户。由于h t t p 请求与回复封包的改写发生在t c p i p 机制里的i p i e v e l ，故 称为“i p 层负载平衡”。b e r k e l e y 的m a 9 l c r o u t e r l “j 、c j s c o 的 l o c a i d i r e c t o r 、 a i t e o n 的a c e d i r e c t o r 和f 5 的b i g i p 等都是使用网络地 址转换方法。由于i p 层负载平衡接受与响应速度极快，后端的真实服务器节点 数可达到2 5 甚至超过1 0 0 ，相当适用于大型或超大型网站使用，例如： h j c r o s o 代、i b m 、y a h o o 等。 我们发现，”i p 层负载平衡，优于”应用层负载平衡”，通常实施应用层负载 平衡须配合n a t 路由器实现，而实施i p 层负载平衡则可通过n a t 路由器、i p t u n n e i i n g 或d i r e c t o rr o u t i n g 实现。以下就这几种实际的负载平衡方式作逐 一说明。 2 3 2 通过n a t 实现虚拟服务器( v s n a t ) 由于i p v 4 中i p 地址空间的日益紧张和安全方面的原因，很多网络使用保 留i p 地址( 1 0 0 0 0 2 5 5 o 0 0 、1 7 2 1 6 0 0 2 5 5 1 2 8 0 o 和 1 9 2 1 6 8 0 0 2 s 5 2 5 s 0 0 ) 。这些地址不在i n t e m e t 上使用，而是专门为 内部网络预留的。当内部网络中的主机要访问i n t e r n e t 或被i n t e m e t 访问时， 就需要采用网络地址转换( n e t w o r k a d d r e s s t r a n s i a t i o n ，以下简称n a t ) ， 将内部地址转化为i n t e r n e t s 上可用的外部地址。n a t 的工作原理是报文头( 目 标地址、源地址和端口等) 被正确改写后，客户相信它们连接一个i p 地址，而 不同i p 地址的服务器组也认为它们是与客户直接相连的。由此，可以用n a t 方法将不同i p 地址的并行网络服务变成在一个i p 地址上的一个虚拟服务。 v s n a t 的体系【2 0 结构如图2 - 4 所示。在一组服务器前有一个调度器， 它们是通过s w j t c h h u b 相连接的。这些服务器提供相同的网络服务、相同的 武汉理_ r 大学硕士学位论文 内容，即不管请求被发送到哪台服务器，执行结果是一样的。服务的内容可 以复制到每台服务器的本地硬盘上，可以通过网络文件系统( 如n f s ) 共享， 也可以通过一个分布式文件系统来提供。 一一一一一一。7 图2 4v s n a t 的体系结构 客户通过v i r t u a ii pa d d r e s s ( 虚拟服务的i p 地址) 访问网络服务时，请 求报文到达调度器，调度器根据连接调度算法从一组真实服务器中选出一台服 务器，将报文的目标地址v i r t u a ii pa d d r e s s 改写成选定服务器的地址，报文 的目标端口改写成选定服务器的相应端口，最后将修改后的报文发送给选出的 服务器。同时，调度器在连接h a s h 表中记录这个连接，当这个连接的下一个 报文到达时，从连接h a s h 表中可以得到原选定服务器的地址和端口，进行同 样的改写操作，并将报文传给原选定的服务器。当来自真实服务器的响应报文 经过调度器时，调度器将报文的源地址和源端口改为v j r t u a ii pa d d r e s s 和相 武汉理工大学硕士学位论文 应的端口，再把报文发给用户。这样，客户所看到的只是在v i r t u a i i p a d d r e s s 上提供的服务，而服务器集群的结构对用户是透明的。 2 3 3 通过ip 隧道实现虚拟服务器( v s t u n ) 在v s n a t 的集群系统中，请求和响应的数据报文都需要通过负载调度 器，当真实服务器的数目在1 0 台和2 0 台之间时，负载调度器将成为整个集群 系统的新瓶颈。大多数i n t e m e t 服务都有这样的特点：请求报文较短而响应报 交往往包含大量的数据。如果能将请求和响应分开处理，即在负载调度器中只 负责调度请求而响应直接返回给客户，将极大地提高整个集群系统的吞吐量。 i p 隧道( i p t u n n e l n g ) m l j 是将一个i p 报文封装在另一个i p 报文的技术， 这可以使得目标为个i p 地址的数据报文能被封装和转发到另一个i p 地址。i p 隧道技术亦称为i p 封装技术( i pe n c a p s u i a t i o n ) 。i p 隧道主要用于移动主 机和虚拟私有网络( v i r t u a lp r i v a t en e t w o r k ) ，在其中隧道都是静态建立的， 隧道一端有个i p 地址，另一端也有唯一的i p 地址。 我们利用i p 隧道技术将请求报文封装转发给后端服务器，响应报文能从后 端服务器直接返回给客户。但在这里，后端服务器有一组而非一个，所以我们 不可能静态地建立对应的隧道，而是动态地选择一台服务器，将请求报文 封装和转发绘选出的服务器。这样，我们可以利用i p 隧道的原理将一组服务器 上的网络服务组成在一个i p 地址上的虚拟网络服务。v s 仃u n 的体系结构如图 2 5 所示，各个服务器将v i p 地址配置在自己的i p 隧道设备上。 武汉理工大学硕士学位论文 v i r t u 丑| s e r v r v f af pt u n n l i n g 一，一 图2 5v s 厂丁u n 的体系结构 v s 厂t u n 的工作流程如图2 6 所示：它的连接调度和管理与v s n a t 中 的一样，只是它的报文转发方法不同。调度器根据各个服务器的负载情况，动 态地选择一台服务器，将请求报文封装在另一个i p 报文中，再将封装后的i p 报文转发绘选出的服务器；服务器收到报文后，先将报文解封获得原来目标地 址为v i p 的报文，服务器发现v i p 地址被配置在本地的i p 隧道设备上，所以就 处理这个请求，然后根据路由表将响应报文直接返回给客户。 】2 武汉理工大学硕士学位论文 e t sv i p j “ l 雠a p s “耐啦 8 f pv f p l _ _ 砖 厂一；j “。，一一，一“、 f：必獬嘲。i 。： 弋。乏! = = 袋：，夕y 8 1 pv 1 p 1 铺c a 口s u l 甜n q 一 v j p u n u d i r e c t o r ：兮e l e c fo n er e a fs e n ，e r ：e n c a 口8 u f a t e ：a n df o n r a f t t o 廿1 er e a s e er 。l f n u x 0 i r e c c 0 r s0 nf h ec | i e n t 0 一 s e 九，e 1 a 忏c o n n e e 甜0 n l ，一一。 - - 一。一 _ t h er e a fs e e r t ：d e c a p s u l a f ef h ep a c k e f a n d ：p r o c e s st h ep a c k e ff o c a a n d ! s e n dr e s p o n s e 口a c k e t t 0t h ec f f e n f d f r e c 埘 l 一一一一一一一一一一一一一一一 图2 6v s 丌u n 的工作流程 2 3 ，4 通过直接路由实现虚拟服务器( v s d r ) 跟v s 厂t u n 方法相同，v s dr l “1 利用大多数i n t e m e t 服务的非对称特 点，负载调度器中只负责调度请求，而服务器直接将响应返回给客户，可以极 大地提高整个集群系统的吞吐量。v s d r 的体系结构如图2 - 7 所示：调度器 和服务器组都必须在物理上有一个网卡通过不分断的局域网相连，如通过高速 的交换机或者h u b 相连。v i p 地址为调度器和服务器组共享，调度器配置的 v i p 地址是对外可见的，用于接收虚拟服务的请求报文；所有的服务器把v i p 地址配置在各自的n o n a r p 网络设备上，它对外面是不可见的，只是用于处理 目标地址为v i p 的网络请求。 武汉理工大学硕士学位论文 图2 7v s d r 的体系结构 v s d r 的工作流程如图2 8 所示：它的连接调度和管理与v s n a t 和 v s 丌u n 中的一样，它的报文转发方法又有不同，将报文直接路由给目标服务 器。在v s d r 中，调度器根据各个服务器的负载情况，动态地选择一台服务 器，不修改也不封装i p 报文，而是将数据帧的m a c 地址改为选出服务器的m a c 地址，再将修改后的数据帧在与服务器组的局域网上发送。因为数据帧的m a c 地址是选出的服务器，所以服务器肯定可以收到这个数据帧，从中可以获得该 i p 报文。当服务器发现报文的目标地址p 是在本地的网络设备上，服务器处 理这个报文，然后根据路由表将响应报文直接返回给客户。 武汉理_ 大学硕士学位论文 i pp a c 托e t 蜊毒f a m e v i p 。i 画r e c r o 城嗽 i s 件 辘0磁产 s 耕a cv p 一“ ” v i p 图2 8v s d r 的工作流程 2 3 5 三种i p 负载均衡技术的比较 三种i p 负载均衡技术的优缺点归纳在下表中： l j n 愀0 坞n o r s e i e c o n e 塘a i8 剀v e r d i r e c t j p 0 州a 州娃t 0t h e 蟪a is e n 陀r l l b 珏x l 纯# 地rl s0 靠撕e 州e n 0 一 s e 掰e fh a 辑秘n o e 越0 n 丁h ef e 捧 s e w 耵 ：8 i n e # h ev l p 8 棼杓n gi o o 嚣b a c k ：a h a si m 最讦a e e 聃稿r o c e s s e s 讯e ：p a c k e ti o e a f | ya n d8 e n dr e s p o n s o ! p a c k e l1 0t h ec | i e n ld l r e c t i v i 一一一。 以上三种方法所能支持最大服务器数目的占计是假设调度器使用1 0 0 m 网 卡，调度器的硬件配置与后端服务器的硬件配置相同，而且是对一般w e b 服务。 使用更高的硬件配置( 如千兆网卡和更快的处理器) 作为调度器，调度器所能 调度的服务器数量会相应增加。当应用不同时，服务器的数目也会相应地改变。 所以，以上数据估计主要是为三种方法的伸缩性进行量化比较。 v i r t u a is e r v e rv j an a t v s n a t 的优点是服务器可以运行任何支持t c p i p 的操作系统，它只需 要一个i p 地址配置在调度器上，服务器组可以用私有的i p 地址。缺点是它的 武汉理工大学硕士学位论文 伸缩能力有限，当服务器结点数目升到2 0 时，调度器本身有可能成为系统的新 瓶颈，因为在v s n a t 中请求和响应报文都需要通过负载调度器。 基于v s n a t 的的集群系统可以适合许多服务器的性能要求。如果负载调 度器成为系统新的瓶颈，可以有三种方法解决这个问题：混合方法、v s t u n 和v s d r 。在d n s 混合集群系统中，有若干个v s n 卢汀负载调度器，每个负 载调度器带自己的服务器集群，同时这些负载调度器又通过r r - d n s 组成简单 的域名。但v s 丌u n 和v s d r 是提高系统吞吐量的更好方法。 对于那些将i p 地址或者端口号在报文数据中传送的网络服务，需要编写相 应的应用模块来转换报文数据中的i p 地址或者端口号。这会带来实现的工作量， 同时应用模块检查报文的开销会降低系统的吞吐率。 v i r t u a is e n ，e rv i ai pt u n n e i i n g 在v s 仃u n 的集群系统中，负载调度器只将请求调度到不同的后端服务 器，后端服务器将应答的数据直接返回给用户。这样，负载调度器就可以处理 大量的请求，它甚至可以调度百台以上的服务器( 同等规模的服务器) ，而它不 会成为系统的瓶颈。即使负载调度器只有1 0 0 m b p s 的全双工网卡，整个系统 的最大吞吐量可超过1 g b p s 。所以，v s t u n 可以极大地增加负载调度器调度 的服务器数量。v s 厂r u n 调度器可以调度上百台服务器，而它本身不会成为系 统的瓶颈，可以用来构建裹性能的超级服务器。 v s 丌u n 技术对服务器有要求，即所有的服务器必须支持”i pt u n n e i n q ” 或者”i pe n c a p s u l a t i o n “协议。目前，v s 厂丁u n 的后端服务器主要运行l l n u x 操作系统，我们没对其他操作系统进行测试。因为”i pt u n ne l _ n q ”正成为各个 操作系统的标准协议，所以v s 厂u n 应该会适用运行其他操作系统的后端服务 器。 v i r t u a is e r v e rv i ad i r e c tr o u t i n g 跟v s 厂丁u n 方法一样，v s d r 调度器只处理客户到服务器端的连接，响应 数据可以直接从独立的网络路由返回给客户。这可以极大地提高l v s 集群系统 的伸缩性。 跟v s 玎u n 相比，这种方法没有i p 隧道的开销，但是要求负载调度器与实 际服务器都有一块网卡连在同一物理网段上，服务器网络设备( 或者设备别名) 不作a r p 响应，或者能将报文重定向( r e d i r e c t ) 到本地的s o c k e t 端口上。 武汉理工大学硕士学位论文 第3 章l in u x 虚拟服务器动态负载平衡算法分析 l p v s 在内核中的负载均衡调度是以连接为粒度的。在h t t p 协议( 非持久) 中，每个对象从w e b 服务器上获取都需要建立一个t c p 连接，同一用户的不 同请求会被调度到不同的服务器上，所以这种细粒度的调度在一定程度上可以 避免单个用户访问的突发性引起服务器间的负载不平衡。在内核中的连接调度 算法上，i p v s 己实现了以下八种调度算法： 轮叫调度( r o u n d - r o b i ns c h e d u l h 培) 加权轮叫调度( w e i g 灿e d r 0 1 l i i d - r 0 b i ns c h e d n l h 培) 最小连接调度( l e a s t c o 衄e 嘶o ns c h e d l l l i n g ) 加权最小连接讽良( w 啦曲t c dl e a s t c o n n e c t i o ns c h e d m i n g ) 基于局部性的最少链接( l 0 c a l i t y b a s e dh a s tc o 蛐e c t i o n ss c h e d u l i n g ) 带复制的基于局部性最少链接( l o c a l i t ) r b a s e dl c tc o 仰e c t i o n sw i 也 r e p l i c a t i o ns c b e d u l i n g ) 目标地址散列调度( d e s t i n a t i o nh a s h i n gs c h e d u l i n g ) 源地址散列调度( s o l l r c eh a s h i | 1 9s c h e d u l i n g ) 通过对“n 1 1 ) 【内核源代码1 i n u x - 2 4 3 0 。饥b z 2 源代码关于l s 部分的分析后， 在这里我给出这些常用动态负载平衡调度算法的工作原理和算法流程，并打算 在此基础之上对应用最广泛的加权最小连接调度算法进行改进。 3 1 轮叫调度算法分析 轮叫调度( r o u n dr 0 b i ns c h e d u l i i l g ) 算法就是以轮叫的方式依次将请求调 度不同的服务器，即每次调度执行i ：“+ 1 ) m o dn ，并选出第i 台服务器。算法 的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调 度。在此算法中赋予服务器权值，当服务器的权值为零时，表示该服务器不可 用而不被调度。这样做的目的是将服务器切出服务( 如屏蔽服务器故障和系统 维护) ，其算法流程如下： 武汉理工大学硕士学位论文 轮叫调度算法流程： 假设有一组服务器s = s o ，s 1 ，s n 一1 ，一个指示变量i 表示上一次选择 的服务器，w ( s i ) 表示服务器s i 的权值。变量i 被初始化为n 一1 ，其中n 0 。 j = l ； d of j = ( j + 1 ) m o d n ； i f ( w ( s j ) o ) 1 = j ； r e n l ms i w m l e ( i ! = i ) ； 代息1 mn u l l ： 轮叫调度算法假设所有服务器处理性能均相同，不管服务器的当前连接数 和响应速度。该算法相对简单，因此不适用于服务