（计算机软件与理论专业论文）web内容服务器负载均衡机制的研究与实现.pdf

w e b内容服务器负载均衡机制的研究与实现 摘 要 工 n t e r n e t主机数和用户数的飞速增长以及日 益复杂的电子商务、多媒体等 网络应用的普及给 w e b 服务器提出了巨大挑战。 单一节点的w e b 服务器体系结构 己经无法满足可伸缩性、 高可用性、 易管理性和价格有效性等要求， 在这样的背 景下， w e b 服务器集群系统应运而生。 它是由一组高速互连的服务器节点和一个 决定请求由哪个节点来处理的调度器组成的w e b 服务器系统。 w e b 集群中的每个 服务器节点都拥有独立的软硬件资源， 它们和调度器一起协同工作， 对外构成一 个单一系统映像。 所有到达的w e b 请求都通过调度器被尽可能均匀的分配到各服 务器节点， 从而提高系统的总体吞吐率并减少用户的平均应答延迟。 本文首先研 究了w e b 服务器集群系统的两大关键技术， 即路由机制和调度策略。 随后详细分 析了几个有代表性的基于内容的负载均衡调度算法。在此基础上，本文提出了 w e b内容服务器 w c s的概念和体系结构。w c s 是 w e b 集群的一种，它和传统 w e b 集群的区别在于:w c s 根据服务类型 ( 静态、动态、多媒体)对整个站点的内容 进行划分， 使得一个后端服务器节点总是提供一种类型的服务。 与此同时， 设计 了一个适用于 w c s的负载均衡调度算法 c s l b ，分析了它的时间和空间复杂度。 本文接着介绍了us 项目的进展， 并指出了将 w c s 与us 集成需要考虑的几个关 键问题。最后对w c s 系统进行了模拟设计与实现，通过对w c s 及c s l b 算法的分 析、实验和比较，可以得出:c s l b是一个以提高用户满意程度即减少客户端等 待时间为主要贡献的、基于内容的w e b 集群调度算法，而w c s 则为c s l b 的运行 提供了体系结构和平台上的支持。 关键词: w e b 服务器集群系统， w e b内容服务器，路由机制， 负载均衡调度策略， 基于内容调度，请求类型，总体吞吐率，平均应答延迟 we b内容服务器负载均衡机制的研究与实现 ab s t r a c t t h e r a p id in c r e a s e o f i n t e rn e t h o s t s a n d u s e r s as w e l l a s t h e e v e r m o r e c o m p l i c a t e d n e t w o r k a p p l ic a t i o n s s u c h a s e - b u s i n e s s a n d mu l t i m e d i a s e r v i c e h a s p o s e d g r e a t c h a l l e n g e s t o we b s e r v e r . t h e a r c h i t e c t u r e o f s i n g l e n o d e s e r v e r i s n o t a b l e t o f u l f i l l t h e r e q u i r e m e n t s o f s c a l a b i l i t y , h i g h - a v a i l a b i l i t y , m a n a g e a b i l i t y a n d c o s t - e ff e c t i v e n e s s . u n d e r s u c h c i r c u m s t a n c e , w e b s e r v e r c l u s t e r s y s t e m h a s b e e n p u t f o r w a r d . i t c o n s i s t s o f a g r o u p o f i n t e r c o n n e c t e d s e r v e r n o d e s a n d a s w i t c h e r a c t i n g as t h e d e c i s i o n m a k e r a s t o w h i c h b a c k e n d n o d e w i l l s e r v e t h e c o m i n g r e q u e s t . e a c h n o d e i n a we b c l u s t e r h as i t s o w n s o ft w a r e a n d h a r d w a r e r e s o u r c e s , w o r k i n g c o o p e r a t i v e l y w i t h t h e s w i t c h e r t o p r o v i d e a s i n g l e s y s t e m i m a g e t o t h e o u t s i d e . a l l c o m i n g r e q u e s t s a r e f o r w a r d e d t o s e r v e r n o d e s b y t h e s w i t c h e r w i t h t h e g o a l o f l o a d b a l a n c i n g a m o n g a l l n o d e s s o t h a t h i g h o v e r a l l t h r o u g h p u t a n d l o w a v e r a g e r e s p o n s e la t e n c y c a n b e r e a c h e d . t h i s p a p e r f i r s t m a k e s r e s e a r c h i n t o t w o k e y t e c h n o l o g i e s o f w e b c l u s t e r , i .e . r o u t i n g m e c h a n i s m a n d s c h e d u l i n g p o l i c y w it h t h e a n a l y s i s o f s o m e t y p i c a l c o n t e n t - b a s e d s c h e d u l i n g a l g o r i t h m s . t h e n t h e c o n c e p t o f we b c o n t e n t s e r v e r h as b e e n p r o p o s e d a s o n e k in d o f we b c l u s t e r a n d w h a t d if f e r e n t i a t e s wc s f r o m c o n v e n t i o n a l t y p e s o f w e b c l u s t e r i s t h a t i t p a r ti t i o n s t h e c o n t e n t o f th e w h o l e w e b s it e a c c o r d i n g t o t h e s e r v i c e t y p e s u c h a s s t a t i c , d y n a m i c a n d m u l t i m e d i a t o m a k e s u r e t h a t e a c h n o d e p r o v i d e s o n l y o n e k i n d o f s e r v i c e . i n a d d i t i o n , a l o a d b a l a n c i n g s c h e d u l i n g a l g o r it h m n a m e d c s l b i s d e s ig n e d f o r wc s a r c h i t e c t u r e w i t h i t s t i m e 即使在发展中国家，巴西也已 经拥有 1 4 0 0 万上网用户。 中国互联网 络信息中心 ( c n n i c ) 2 0 0 4 年1 月发布的第1 3 次统计报告13 1 显示， 到2 0 0 3 年年底， 中国网民人数已经达到了7 9 5 0 万， 连网主机数达到3 0 8 9 万台， c n下 注册的域名数、 w e b 站点数分别达到了3 4 万和5 9 .6 万。从下图0 1 可以 看 出，以we b 应用为中心的 i n t e rne t 在经历了2 1 世纪最初几年泡沫破灭的短暂冬 天后再一次跃入高速增长期。 w e b 站点数 5 0 .0 0 0 . 0 0 0 4 5 ,0 0 0 ,0 0 0 4 0 ,0 0 0 ,0 0 0 3 5 , 0 0 0 , 0 0 0 3 0 , 0 0 0 ,0 0 0 2 5 , 0 0 0 ,0 0 0 2 0 ,0 0 0 ,0 0 0 1 5 ,0 0 0 ,0 0 0 1 0 ,0 0 0 ,0 0 0 5 ,0 0 0 , 0 0 0 0 日期 图 1 . 1 w e b 站点数量的增长 ( 1 9 9 6 / 0 1 - 2 0 0 3 / 1 2 ) w e b 内 容服务器负载均衡机制的 研究与 实现 i n t e rn e t 的无所不在和大量潜在客户的存在为企业创造另一个更直接面向客 户的电子商务市场提供了条件， 而这个市场的直接性、 广阔性和方便快捷的特点 正吸引着越来越多的企业将重要的业务转移到w e b上来。 据统计2 1 ，全球b 2 c ( b u s i n e s s t o c o n s u m e r ) 电子商务年收入己经接近2 亿美元， 并继续以每年5 0 % 的速度递增。同时，b 2 b ( b u s i n e s s t o b u s i n e s s )的交易量每年成倍增加，预计 到2 0 0 6 年， 全球将有超过 1 / 3 的企业开展b 2 b电子商务。 电子商务的繁荣使c p u 密集型 ( 即耗费大量c p u资源来处理)的动态网页数量骤增，对w e b 服务器的 处理能力提出了巨大挑战。 随着多媒体技术的蓬勃发展， i n t e rn e t 上的多媒体应用和服务层出不穷，多 媒体信息的数量与日 俱增。 m f a 15 1 等研究显示， 各种带宽密集型 即耗费大量网 络带宽来传输)的多媒体文件 ( 如图像、音频、视频等)已经占到了w e b请求 的5 0 %以上。 各种. e b 请求的比 较 暑: l t母 耸聋 聋聋幸 二 1, s 0曰 i-月攀 旧卜一一一一一一升拼一斗份一， 二二 二应箱。 im 7 0目沁 卜 一月旧 险井共牛一一一一一一一一一一一.叫 1 m is 7 e g 3 rx s 8 : 姐不 。目 探 i m翔睡 升 燕 共共一 一抽奋 芬杀升 书一- 拼 j . 一 c-6口 皿 l 止 i 声“ ， a 、 请求类型 秘 题 1一 口请求个数 .传输数据量 : 娜1一奋粗、 .1 舟. 图 1 .2各种we b 请求的比较 1 . 1 . 2对w e b 服务器提出的挑战 工 n t e r n e t的飞速发展和日 益复杂的w e b 应用服务给网络带宽和w e b服务器 都带来了巨大挑战。 服务器延迟越来越成为用户所感受到的w e b 服务性能的主导 因素， 对y a h o o 这样访问 量极大的网站来说更是如此 e w e b 服务器必须具备提 供大量并发访问的能力，如果客户的增多导致通信量超出了服务器能承受的范 围，那么其结果必然是系统瘫痪。伴随着 i n t e r n e t的服务角色由单一的数据传 输网向数据、 语音、图像等多媒体信息的综合传输网转变， 相应的w e b 服务模式 也由传统的数据通信与信息浏览向电子交易与在线服务演化，网络应用向 w e b 服务器施加的计算负载日 益增加。1 9 9 5 年时曾有人预测， 在未来2 5 年内，网络 带宽将以每年3 倍的速度增加。 从目 前网络技术的发展来看， 这一预测基本正确 w e b内容服务器负载均衡机制的研究与 实现 : 、 百兆以太网、a t m及千兆以太网等相继涌现，i o g以太网即将就绪，密集 波分复用 ( d w d m )将成为宽带 i p 的主流技术，8 0 0 c 的光纤也已经研制成功。相 比之下，根据莫尔定律，c p u及存储器的性能每 1 8个月才翻一番。因此，网络 带宽的发展速度几乎达到了服务器发展速度的2 倍。 我们有理由相信， 越来越多 的系统瓶颈将会出现在服务器端。 同时，在 工 n t e r n e t 这样一个完全分布的控制系统中，w e b站点是唯一能够 被内容服务提供商完全控制的组件。而网络客户端、工 n t e r n e t 主干网、路由器、 域名服务器及代理服务器等都不是由单个组织或机构所掌握的， 任何试图对这些 组件所做的修改往往由于各方无法达成一致而难以实现。 基于上述两点考虑， 如何提高w e b 服务器系统的性能成了国内外研究领域的 一大热点问题，对w e b 服务器提出了如下的要求。 . 可伸缩性 所谓 “ 可伸缩性” 是指:当服务负载增加时， 能够扩展系统来满足需求， 同时又不降低服务质量。 如今， 热门的站点会吸引前所未有的访问流量。 根据y a h o 。 的 新闻 发布i9 , y a h o 。 每天发 送6 . 2 5 亿个页面， a o l 的w e b c a c h e 系统每天处理 5 0 . 2 亿个访问请求。与此同时，很多站点因为访问 次数爆炸式增长而不堪重负，不能及时处理用户请求，导致用户长时间 等待，大大降低了服务质量。因此，如何建立可伸缩的网络服务来满足 不断增长的负载需求己成为迫在眉睫的问题。 . 高可用性 所谓 “ 高可用性”是指:尽管部分硬件和软件会发生故障，但是整个系 统的服务是终年全天候可用的。现在大部分网站都需要提供每天 2 4小 时、每星期了 天的服务，这一点对电子商务类型的网站尤为突出，任何 服务的中断或关键性数据的丢失都会造成直接的经济损失。例如，根据 d e l l 的新闻发布 0 1 , d e l l 现在每天来自 于网站的交易收入为1 4 0 0 万美 元， 一小时的服务中断会造成平均5 8 万美元的损失。 所以， 这对网络服 务的可靠性提出了极其严格的要求。 . 易管理性 所谓 “ 易管理性”是指:整个系统在物理上虽然很大，但应该像单一系 统那样容易管理。 在理想状况下， 软硬件模块的插入能够做到即插即用。 . 价格有效性 所谓 “ 价格有效性”是指:整个系统的实现是经济的，能够以较低的花 费获得服务器性能的增加，具有良 好的性能价格比。 w e b 内 容服务器负 载均衡机制的研究与实现 系统整体性能随着节点数的增加而接近线性上升，使系统的性价比接近 于p c 服务器。 所以， 这种松祸合多节点结构比单台超级计算机或者紧祸 合多处理器系统具有更好的性能价格比。 1 . 3本文的研究内容和主要成果 本文的研究工作隶属于国家 8 6 3 项目 “ 基于w e b 服务的数据库新技术” 。研 究 w e b集群及内容服务器这一课题的最初想法来自 于国家自 然科学基金重点项 目“ 电子图书馆的相关关键技术研究” 。作者希望通过本人的工作，为数字图书 馆中的“ 多媒体信息检索” 模块提供内容服务器的架构、 算法和技术支撑， 以提 高多媒体服务的质量。 本文首先研究了w e b 服务器集群系统的两大核心技术， 即路由机制和调度策 略。 随后详细分析了几个有代表性的基于内容的负载均衡调度算法( s i t a - e , c a p , l a r d , a r f ) 。在此基础上，本文提出了“ w e b内容服务器” ( 简称w c s )的概念和 体系结构，设计了一个适用于w c s的负载均衡调度算法 c s l b ，分析了它的时间 和空间复杂度。 接着介绍了us 项目的进展， 并指出了将w c s 与l v s 集成需要考 虑的几个关键问题。最后对w c s 系统进行了模拟设计与实现，并将c s l b 算法与 传统的l c 算法和r r 算法在“ 总体吞吐率” 和 “ 平均响应延迟” 这两个指标上进 行了比较。通过对w c s 及c s l b 算法的分析、实验和比较，我们提出的方案具有 以下特点和贡献: 1 )支持静态、动态、多媒体等各种w e b内容。 2 ) 支持专用服务器，每个节点可以根据内容的特点来配置它的软硬件， 提 高服务器的性能。 3 )避免了单点失效，因为同类服务器节点具有相同的内容， 这种冗余使得 单个节点的故障不会影响整个系统的正常服务， 使得高可用性的实现成 为可能。 4 )相对较低的时间和空间复杂度减轻了调度器的负担， 有效降低了调度器 成为系统瓶颈的可能性。 5 )对多媒体请求庞大的应答数据给予了特别考虑， 同时又不影响其它类型 请求的正常调度。 通过考虑服务器的传输负载来降低请求的平均应答延 迟，是c s l b 算法的创新点。 w e b 内 容服务器负载均衡机制的 研究与 实现 1 . 4本文的组织结构 本文共分 7 章，将讨论以下几方面的研究工作: 1 )作为w e b 服务器集群系统的产生背景，第一章对 i n t e r n e t 和w w w的发 展历史、现状、趋势和引发的问题做了调查、研究和分析，随后介绍了 w e b 集群的特点和通用体系结构。 2 )第二章研究了w e b 服务器集群系统的几大关键技术， 并比较了w e b 集群 的两种主要的路由机制和两类主要的调度策略， 并对己有的主要商业产 品和原型系统做了简单的介绍和分析。 3 ) 第三章详细讨论了几个有代表性的基于内容的负载均衡调度算法， 并比 较了它们的优缺点。 4 ) 第四章提出了 “ w e b内容服务器”即w c s的概念和体系结构，设计了一 个适用于 w c s的负载均衡调度算法 c s l b ( c o n t e n t s e r v e r l o a d b a l a n c i n g ) ，分析了 它的复杂度，并总结了w c s 的特点。 5 )第五章介绍了us ( l i n u x v i r t u a l s e r v e r )项目的进展，并提出了如 何将 w c s与 us 集成。 6 )第六章对 w c s系统进行了模拟设计与实现，并将c s l b算法与传统的最 少活动连接算法l c 和轮转调度算法r r 在 “ 总体吞吐率”和 “ 平均响应 延迟”这两个指标上进行了实验结果的比较和分析。 7 ) 第七章是结束语，总结了本文的工作，并对将来的研究工作做了展望。 w e b 内 容服务器负载均衡机制的研究与实现 第二章 w e b 集群及相关关键技术 2 . 1 w e b 集群的核心技术 在w e b 集群的通用体系结构下，又有很多分类和扩展。但是，we b 集群的 关键技术不外乎以下4 个方面: 1 )透明集群技术 所谓 “ 透明性”是指 we b 集群系统对外具有唯一的虚拟 i p地址，客户 端在与集群系统交互时就好像在使用单个高性能、 高可用的服务器一样， 不必关心集群中各服务器节点的命名、位置等信息，而且客户端应用程 序也无需做任何修改。透明集群技术所要解决的问题就是:如何高效地 使由多个独立计算机组成的松祸合集群系统构成一个虚拟服务器，所有 集群主机如同一个统一的计算资源联合体提供服务，而且部分服务器的 切入和切出也不会中断服务， 对用户也是透明的。实现we b 集群的透明 性是目 前该领域研究的一个方向。 2 )集群伸缩技术 伸缩性好的集群可以根据需要增加主机到集群中，提高系统的整体处理 能力， 且we b 集群整体性能的增加接近新加入节点的性能。一个设计良 好的we b 集群的结点数目 可以增加到几千、 甚至上万个。 集群伸缩技术 就是要实现在系统中灵活的增减服务器数量使系统可以任意伸缩来满足 不断变化的负载需求，使系统达到较高的性价比。 3 )负载均衡技术 所谓 “ 负载均衡”就是在多个设备之间实现工作量的合理分配，使整个 系统不会出 现有的设备过忙、 而有的设备却未充分发挥处理能力的情况。 负载均衡技术是w e b 集群的核心技术， 是该领域内最为热门的研究方向， 同时也是本文的研究重点。负载均衡一般通过调度器实现。调度器对每 个接收到的请求进行负载均衡计算，根据调度策略从服务器池中选择一 个服务器来处理该请求。这种细粒度的负载控制方法使系统负载能够均 匀的分布到各节点上，降低单个节点负载瓶颈的发生，从而获得理想的 整体性能。w e b 集群的负载均衡技术主要包括以下2 个方面: 路由 机制 w e b 集群的“ 路由” 是指对请求进行分析、 并将其转发到某个服务器 节点的 过程。根据分析和转发请求发生的o s i 七层模型 i s 协议栈的 w e b 内 容服务器负载均街机制的研究与 实现 不同层次， 可以 将w e b 集群的 路由 机制分为两大类: l a y e r - 4 路由 和 l a y e r - 7 路由，两者又可以 继续细分 ( 详细讨论见2 2 ? 。路由 机制的 选择对于负载均衡调度算法有很大的影响， 因为在o s i 的不同层次实 现的请求路由，调度器能够使用的请求信息是不同的。 调度策略与算法 we b 集群的调度策略与算法指的是: 调度器依据什么标准和流程来选 择处理当 前请求的服务 器节点。 根据不同的 分类标准 1 5 1 ， 调 度策 略又 可以分为静态还是动态调度、 内容无关还是基于内容调度、 基于客户 端还是基于服务器端调度等等 ( 详细讨论见2 .3 ) o 4 )可 靠性技术 高可靠/ 高可用的 we b集群能够保证系统不会因为某台服务器的故障而 造成整体瘫痪。可靠性技术是指:当服务器池中的某个节点出现软硬件 故障时，如何发现、定位、修复故障服务器并合理调整负载均衡算法来 自 动适应系统状态的变化;当故障节点的错误被修复而重新进入集群中 时，系统能够再一次探测到并开始进行正常的负载收集工作。高可靠性 要求系统在软硬件上都有冗余，通过检测软硬件将故障屏蔽，由存活节 点提供服务。它的实现需要良 好的系统资源和故障的监测处理系统。当 发现一个模块失败时，要将该模块上提供的服务迁移到其它模块上。在 理想状况下，这种迁移是即时的、自动的。目前此类问题的研究已有较 为成熟的成果 1 6 1 2 . 2 w e b 集群的路由机制 w e b 集群的路由 机制也就是调度器的请求转发机制， 对集群系统的性能具有 重要影响，也是导致系统瓶颈的直接因素。根据其位于 o s i 层次的不同，可以 分为两大类: l a y e r - 4 路由 和l a y e r - 7 路由。 . l a y e r - 4 路由 ( 传输层路由) 调度器执行的是与请求内容无关的转发， 也叫“ 直接绑定” 。因为客户端 为了和服务器端建立t c p 连接的第一个数据包t c p s y n一到达调度器， 就能决定由哪个服务器节点来处理该请求。由于客户端数据包尚未到达 应用层，这种路由机制总体上来说是高效的， 但是相应的调度策略无法 利用请求的内容信息。 令 l a y e r - 7 路由( 应用层路由) 调度器执行的是基于请求内容的转发， 也叫“ 延迟绑定” 。 调度器首先和 w e b 内容服务器负载均衡机制的研究与 实现 客户端建立一个完整的t c p 连接， 然后在应用层检查请求的内容， 最后 才把请求转发给目 标服务器。显然，这种路由机制的效率相对低一些， 但是它可以支持更加复杂的调度策略。 在l a y e r - 4 / l a y e r - 7 的分类下， w e b 集群的体系结构还可以 根据客户端与 目 标服务器之间的数据流做进一步的划分， 主要的区别在于从服务器节点返回 到客户端的数据流。 事实上， 为了 满足集群系统的透明性要求， 所有的请求都 必须经过调度器转发; 但是目 标服务器既可以直接把应答数据发回客户端 ( 即 “ 单向结构” ) ，也可以把应答发给调度器， 再由调度器转发给客户端 ( 即“ 双 向结构” ) 。 通常来说， 单向结构效率更高， 因为调度器只需要处理进来的数据， 但是它的实现也相对复杂; 而双向结构则正好相反， 调度器需要处理进、出两 个方向的数据，容易成为系统瓶颈，但是实现相对简单。 2 . 2 . 1 l a y e r - 4 路由 l a y e r - 4 路由 调度器工作在t c p 级， 属于同 一个t c p 连接的 数据包必须被发 送到同一个服务器节点来保证会话 ( s e s s i o n )的完整性。为此， 调度器需要维护 一个 “ 绑定表”来管理每个 t c p会话到后端节点的映射。具体过程如下:调度 器每接收到一个请求，就检查它的t c p头，根据标志域中相关位的信息来决定 当前的数据包是属于一个新连接、已经建立的旧连接还是两者皆非。 如果该包是 一个新连接 设置了标志位s y n) ， 那么调度器就根据具体的调度策略选择一个 目 标服务器， 并在绑定表中建立一个新连接与服务器的映射记录， 然后把数据包 转发到目 标节点。如果该数据包不是一个新 t c p连接，调度器就通过查询绑定 表来确定该包是否属于某个已经建立的连接。 如果是的话， 调度器就把包转发到 相应的服务器; 如果不是， 则丢弃该包。 为了提高调度器的工作效率， 绑定表通 常以h a s h 表的形式放在内存里， 表中每条记录的格式为 ，以及其它一些和调度算法有关的信息， 如:连接的 开始时间 等。 根据从服务器节点返回客户端的 数据流， l a y e r - 4路由又可以细分 为双向结构和单向结构。 2 . 2 . 1 . 1双向结构 在双向结构中， 每个服务器节点都有唯一的私有 i p地址，进、出的数据包 都由 调度器在t c p 级重写 ( 见图2 . 1 ) 。 包重写这一方法基于n a t e t 7 1 ( 即网 络地 址转换) 机制。 调度器具有一个虚拟i p 地址 ( 称为v i p ) ， 它是整个w e b 集群系 统对外的统一接口。在对进来的数据包进行重写时，调度器将包头中的目 标 i p 地址由v i p 替换为选中服务器节点的私有i p 地址;类似地， 在对返回到客户端 的数据包进行重写时， 调度器将包头中的源i p 地址由 后端节点的i p 转换成v i p , we b 内容服务器负载均衡机制的研究与实现 器私有地址位于o s i 的第二层即数据链路层或者叫ma c层。 2 . 2 . 2 l a y e r - 7 路由 l a y e r - 7 路由 调度器工作在o r的 应用层，因此允许基于内 容的调度。 但是 l a y e r - 7 路由比l a y e r - 4 更加复杂， 因为 它在决定将请求转发给哪个服务器节点之 前需要检查h t t p请求的内容。因此，调度器必须先与客户端建立一个t c p连 接即必须完成建立连接阶段的“ 3 次握手” 过程， 然后在应用层接收h t t p 请求。 容户端 a ff il 4 目 标双务器容户堵 钻 i n 日 标服务器 图2 . 3 l a y e r - 4 路由 ( 左) 和l a y e r - 7 路由( 右) 的 操作过程 相比 之下， 采用l a y e r - 4 路由的调度器在一收到t c p s y n包、客户端还未发出 h t t p 请求之前就选定了目 标服务器节点。图2 .3 显示了两者的不同操作过程。 和l a y e r - 4 路由 相似， l a y e r - 7 路由 也可以 根据应答数据包的发送方式细分 为双向结构和单向结构。 2 . 2 . 2 . 1双向结构 在l a y e r - 7 双向 路由 结构中， 应答数据必须要经过调度器发给客户端。 它也 有几种具体的路由机制。 r t c p网关 在t c p网关结构中， 调度器上运行着一个应用层的代理程序， 作为客户 端和后端节点通讯的中介。这个代理接收客户端连接，并与所有服务器 节点保持持续的t c p 连接。当某个客户端连接上有h t t p 请求达到时， 代理通过相应的t c p 持续连接将请求转发给服务器; 当有应答从服务器 的持续连接上到来时， 代理程序又通过其它连接将应答数据传给客户端。 r t c p 粘合 由 于t c p 网关的代理程序运行在o s i 应用层， 所以 其计算代价大、 效率 低。为了克服这一缺点， t c p 粘合机制试图使包的转发发生在网络层， w e b 内 容服务器负载均衡机制的 研究与实现 介于网络接口驱动程序和 t c p / i p协议栈之间，并由操作系统直接执行 2 0 1 。 一旦 客 户 端 和调 度 器之 间 的t c p 连 接被 建立 并 且调 度器 和目 标 服务 器之间的持续t c p连接被选好，两个连接就被粘合为一个。这样一来， i p 数据包从客户端传送到服务器节点， 无须在调度器上穿越从t c p 层( 传 输层)到应用层的4 个o s i 层。客户端到服务器节点的绑定被确定下来 以后，调度器只需修改i p和 t c p包的头来处理后续的数据包，这样无 论是客户端还是后端节点，都感觉这些数据包是发给自己的。t c p 粘合 机制也可以由 硬件方法来实现2 t 2 . 2 . 2 . 2单向结构 r t c p迁移 一旦调度器与客户端建立了t c p 连接并且选中了某个服务器节点后， 它 就把这一连接的 尾部传递给该服务器2 2 1 。该 迁移协议位于t c p 层之上， 并且在调度器和后端节点主机上都要运行，因此需要两者的操作系统都 作相应的修改。t c p 迁移机制对于客户端也是透明的，因为从服务器节 点发出的数据就如同从调度器发出一样。任何由客户端发给调度器的 a c k包 ( 即确认包) 都被一个运行在调度器协议栈底部的模块转发给服 务器节点。 t c p 迁移机制还可以通过将同一个t c p 连接中的h t t p 请求 分发给不同的服务器节点来支持持续的h t t p 连接2 4 1 j t c p 连接跳跃 这是由r e s o n a t e 2 3 1 提出的一个方法。 一旦调度器和客户端建立了t c p 连 接并选好了目标服务器，它就把i p报文封装在一个r p x报文中转发给 该服务器2 3 1 。 由 于所有的服务器节点都共享同一个虚拟i p 地址， 它们可 以直接将应答数据传送回客户端。 a c k包和持续的会话信息则由调度器 统一管理。 2 . 2 . 3 w e b 集群路由机制的比 较 图 2 . 4对 w e b集群的各种路由机制做了详细分类总结。本节随后将会对 l a v e r - 4 路由 和l a y e r - 7 路由机制做分析和比较口 w e b 内容服务器负载均衡机制的研究与实现 l a y e r - 4 路由 l a y e r - t 路 由 单向结构 ! 双向结构单 向 结 构! 双 向 结 构 包封装i 包直接转发r c p 迁移曰 ! c p 连接 翻跃 t c p 网 关 t c p 枯合 图2 . 4 w e b 集群路由 机制的详细分类 2 . 2 . 3 . 1 l a y e r - 4 路由 机制小结 在双向结构中， 各服务器节点可以位于不同的局域网中， 唯一的限制就是请 求和应答数据都要经过调度器转发。双向结构的主要问题就在于调度器要处理 进、出两个方向的数据流，而且应答数据包往往比请求数据包大很多。因此， we b 集群的伸缩性( 即总体吞吐率) 受到了调度器重写数据包并计算校验和的处 理能力的限 制。 相比 之下， 单向结构的l a y e r - 4 调度在出 现系统瓶颈之前可以 保 持很大的吞吐率， 整个系统的性能仅仅受到调度器建立、 查询和删除绑定表记录 的处理能力的影响。 对于单向结构的各种具体路由机制， 单一包重写和双重包重写的计算代价是 一样的， 但是单一包重写大大减少了调度器的操作， 因为数量巨大的应答数据包 由服务器而不是调度器来重写。 但是， 单一包重写需要修改服务器的操作系统内 核，在实现上相对较为复杂。 包直接转发机制旨 在降低包重写的计算开销。 由于调度器仅仅处理请求数据 包， 而且m a c层操作无需进行代价昂贵的校验和重计算， 整个集群的伸缩性主 要受到集群到i n t e r n e t 的网络带宽的限制。包直接转发的缺点在于它需要调度器 和所有服务器节点位于同一个物理网段上。 但是， 这一限制在实际应用中的影响 很小，因为大部分情况下，调度器和后端节点确实是通过同一个局域网互连的。 使用包封装的路由机制也具有良 好的伸缩性，但是比包直接转发稍差一些。 它的主要问题在于需要服务器支持 i p隧道，这对于目 前的操作系统而言还不是 w e b 内 容服务器负载均衡机制的研究与实现 一个标准。 2 . 2 . 3 . 2 l a y e r - 7 路由 机制小结 l a y e r - 7 双向路由结构的 优点在于调度器上可以实现缓存， 这样， 某些请求 就可以直接由调度器从缓存中应答，而无需转发给后端服务器节点。 对于t c p 网关方法来说，实现简单、适用于任何操作系统是它的主要优点。 而它的主要缺点在于计算代价大， 因为请求和应答数据流都要经过调度器的应用 层。 t c p 粘合方法降低了t c p 网关所需的系统开销，因为它免去了使用应用层代 理时所需的用户空间到核心空间的切换以及内存复制这些计算代价昂贵的操作。 但是，即使使用了t c p 粘合方法，调度器需要修改t c p / i p 头，仍然很容易成为 整个系统的瓶颈。 使用单向路由结构的 l a y e r - 7调度器允许服务器节点直接将应答数据发送 给客户端，因此比 双向结构具有更高的系统伸缩性。文献12 5 牲 匕 较了t c p迁移和 t c p 粘合方法， 前者比 后者的 伸缩性好。 单向结构的主要问 题在于调度器和服务 器的操作系统都需要修改，实现的难度和复杂性相对较高。 2 . 2 . 3 . 3 l a y e r - 4 与l a y e r - 7 路由的比较 l a y e r - 7 相对于l a y e r - 4 路由 机制的主要优点 在于l a y e r - 7 调度器可以 使用基 于内容的调度策略和算法。从2 .3 .2中我们将会看到，这些基于内容的调度策略 能够达到更高的磁盘缓存命中率，能够把 we b服务内容划分到不同的服务器节 点，能 够使用专用服务器，能够将后续的s s l ( s e c u r e s o c k e t l a y e r ) 会话分配 到同一个服务器，能够实现h t t p 连接的细粒度控制等等。 另 一方 面， l a y e r - 7路由 机制也给调度器带来了 较重的 计算负 载， 使调度 器 可能成为严重限制集群伸缩性的因素2 5 2 6 1 。 举例来说， a r o n e t a l . 等2 5 通过实验 显示: 一个使用t c p 迁移方法的l a y e r - 7 调度器所能达到的最高系统吞吐率不会 超过每秒3 5 0 0 个连接， 而在同一个硬件上实现的l a y e r - 4调度器能够达到每秒 2 0 0 0 0 个连接的吞吐率。为了克服这一问题， 有人提出了将内容无关调度和基于 内容调度结合起来以实现可伸缩w e b 集群， 这一问题会在7 . 2 中作为将来的工作 展望做简要介绍。 表2 . 1 总结了we b 集群各种调度机制的特性和优缺点。 w e b 内容服务括负 载均衡机制的 研究与实现 路由 机制调度策略调度器数据流优点缺点 l a y e r - 4 双向内 容无关请求/ 应答灵活 容易移植 吞吐率低 无t c p 连接粒度控制 l a y e r - 4 单向内 容无关请求简单 高效 网络拓扑复杂 无t c p 连接粒度控制 l a y e r - 7 双向基于内 容 请求/ 应答简单 缓存 专用服务器 h t t p 粒度控制 内容分布 s s l会话重用 调度器瓶颈 速度最慢 l a y e r - 7 单向基于内 容 一 请 求 专用服务器 h t t p粒度控制 内容分布 s s l会话重用 调度器瓶颈 调度策略复杂 表2 . 1 we b 集群系统的调度机制总结 2 . 3 w e b 集群的调度策略 we b 集群的调度策略是指调度器选择目 标服务器的标准和方法， 它对系统的 伸缩性 ( 总体吞吐率) 和用户所感受到的系统性能 ( 平均响应延迟) 都有很大影 a h 1 0 根 据 不同 的 标 准p 5 1 19 2 7 2 8 1 ， 调 度 策 略 又可以 分为 负 载 共享 还是 负 载 平 均、 集中式还是分布式调度、静态还是动态调度。但是，对于 we b集群的体系结构 而言， 只有其中一部分调度方法是可以采纳的。 对于具有透明性的、 单一调度器 的w e b 集群而言 ，必须采用集中式调度。另外，负载共享的目 标是消除系统总 体的瞬间负载高峰， 而负载平均算法则追求负载在所有服务器节点之间绝对均匀 分 布2 7 2 9 1 。 显 然， 调 度器的目 标 应当 是 共享 而 不是 平 均化系 统负 载。 绝对的 平 均和稳定并非必要，而且在高度动态的we b 集群系统中，几乎不可能做到。 w e b 内容服务器负载均衡机制的 研究与实现 因此， 真正的选择就在于使用静态还是动态调度算法。 静态算法的快速性能 够有效防止调度器成为系统瓶颈， 因为它在做决策时不需要依赖系统当前的状态 信息。 但是， 静态算法的结果往往不够理想。 动态算法则由于使用了状态信息而 有更准确的结果。 然而它需要收集和分析状态信息， 导致了较高的系统开销。以 下是对一个好的调度算法的几点限制。 1 )计算复杂度低，因为调度算法的结果具有很强的实时性。 2 )与 现有w e b 标准和协议完全 兼容， 保 证算法的实 用性。 3 )调度算法需要的所有状态信息必须是调度器能够得到的。 也就是说， 调 度器和服务器组是唯一收集和交换负载信息的组件， 而不应考虑任何需 要与不属于内容服务提供商的其它组件进行交互才能获得的状态信息。 静态调度算法不考虑任何状态信息， 相比之下， 动态算法需要考虑各种状态 信息，其种类多少取决于调度器在 o s i 协议栈的哪个层次上进行调度操作。鉴 于这一因素的重要性， 本节将主要把调度算法分为“ 内容无关调度” ( 工作在t c p 级) 和 “ 基于内容调度” ( 工作在应用层) 。显然， 静态调度算法一定是内容无 关的。 根据调度器所使用的系统状态信息的位置， 又可以将动态算法进一步分为 以下三类。 . 基于客户端 即调度器根据一些客户端信息来选择服务器。使用 l a y e r - 4路由 机制的 调度器 ( 简称 “ l a y e r - 4调度器” ) 只能使用诸如客户端 i p地址和 t c p 端口 号 等网 络层客户端信息。 而使用 l a y e r - 7路由 机制的 调 度器 ( 简 称 l a y e r - 7 调度器” ) 可以 检查h t t p 请求的完整内 容，从而根据这些详 细信息做决策。 令 基于服务器端 即调度器根据一些服务器状态信息来选择后端节点。这些信息包括:当 前和过去的负载状况、响应延迟以及节点可用性等。而且，在基于请求 内容的调度中，调度器还可以考虑服务器磁盘缓存的相关信息。 . 基于客户及服务器端 即调度器将客户端和服务器端的信息综合考虑来选择日 标节点。 实际上， 大部分现有的基于客户端状态的调度策略也应该属于这一分类，因为它 们或多或少的使用了一些服务器的信息 ( 至少要知道服务器的可用性) 。 w e b 内 容服务器负载均衡机制的 研究与实现 本节后面将根据图2 . 5中的分类方法来研究各种调度策略及相应的代表 性调度算法。基于内容调度的几个典型算法将在第三章中具体分析。 内容无关 调度 态度 静调 基于 客户端 图2 . 5 w e b 集群调度策略的分类 2 . 3 . 1 2 . 3 . 1 . 内容无关调度 1静态调度 静态调度策略不考虑任何系统状态信息。 典型的例子就是随机算法和轮转调 度算法 ( 简称 r r ) a随机算法将请求以均匀分布的概率随机分配到各服务器节 点。r r算法使用一个循环链表和一个指向最后一个被选中的服务器节点的指针 来执行调度:如果 s ; 是最后一个被选中的节点，那么新的请求将被分配到节点 s (i+ 1j m o d ,%