（计算机软件与理论专业论文）基于cg树的分布式服务器集群的设计与实现.pdf

摘要摘要本文描述了一个基于c g 树的分布式服务器集群的设计和实现，主要内容有：l 、提出了一套较为简单可行的c g 树通信协议。该通信协议能在就绪状态下，能够维持集群的正常通信；在集群内节点失效时能及时发现并进行调整；在失效节点恢复时，能将失效节点重新加入，并将c g 树结构调整回失效前的状态，保证c g 树的一致性。通信协议包括初始化模块、心跳模块、象合并模块、调整模块和消息接收模块五个模块。接着还描述了c g 树在该通信协议下的几个相关性质及c g 树的实用背景。2 、剖析i p v s 技术及系统结构，重点研究了i p v s 在c g 树模型下的实现技术，成功地将i p v s 技术拓展到基于c g 树的分布式服务器集群。3 、提出一种在i p v s 下的基于内容调度的解决方案，有效减少了集群服务器中因资源冗余造成的浪费。这种方案的调度性能接近i p 层调度，特别适用于媒体服务器集群。4 、运用多线程和s o c k e t 技术构建了一个基于c g 树的分布式集群系统原型。技术分析和实验结果表明，该集群系统具有高可用性和高性能。关键词：分布式集群；c g 树；i p v s ；负载均衡a b s t r a c ta b s t r a c tt h i sp a p e rd e s c r i b e st h ed e s i g na n di m p l e m e n t a t i o no fac g t r e eb a s e dd i s t r i b u t e ds e r v e rc l u s t e r , t h ec o n t e n t so fw h i c hi n c l u d e ：1 w ep r o p o s eas i m p l eb u tf e a s i b l ep r o t o c 0 1 t h i sp r o t o c o lc a nm a i n t a i nt h en o r m a lc o m m u n i c a t i o no fc l u s t e ri nt h er e a d ys t a t e i nt h ef a i l u r es t a t e , t h ef a i l e dn o d ec a nb ei s o l a t e d , a n dt h ec l u s t e rc a l lb ea d j u s t e da u t o m a t i c a l l y w h e naf a i l e dn o d er e c o v e r e d ，t h ec g - t r e ew o u l db ea d j u s t e dt ot h es t a t u sj u s tb e f o r et h ef a i l u r es oa st ok e e pt h ec g t r e ec o n s i s t e n c y t h ep r o t o c o li n c l u d e si n i t i a lm o d u l e , h e a r t b e a tm o d u l e , c g t r e ei m a g em e r g i n gm o d u l e ，a d j u s t m e n tm o d u l ea n dm e s s a g er e c e i v i n gm o d u l e w ed e s c r i b es o m er e l a t i v ep r o p e r t i e so ft h ep r o t o c o la n dt h ep r a c t i c a lb a c k g r o u n do fc g - t r e e 2 w es t u d ya n da n a l y z ei p v st e c h n i q u ei nd e t a i l ，f o c u s i n go nh o wt oa p p l yi p v st e c h n i q u et oc g t r e em o d e l ，a n ds u c c e s s f u l l ye x t e n di p v st e c h n i q u et od i s t r i b u t e ds e r v e rc l u s t e rb a s eo nc g t r e e 3 w ep r o p o s eac o n t e n t - b a s e ds c h e d u l i n gs o l u t i o nw i t hi p t v ，w h i c hc a r lr e d u c et h er e s o u r c ew a s t ei nc l u s t e rs e r v e r s t h i sc l i e n t - s u p p o r t e ds o l u t i o nc a na p p r o a c ht ot h ep e r f o r m a n c eo fi p b a s e ds c h e d u l i n gs o l u t i o n ，a n di se s p e c i a l l ys u i t a b l ef o rm e d i as e r v e rd u s t e r 4 u s i n gm u l t i t h r e a da n ds o c k e tt e c h n o l o g i e sw ee s t a b l i s h e dap r o t o t y p eo fd i s t r i b u t e ds e r v e rc l u s t e rb a s e do nc g - t r e e o u rt e c h n i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l ts h o w st h a tt h i sc l u s t e rh a sh i 曲a v a i l a b i l i t ya n dh i g hp e r f o r m a n c e k e yw o r d s ：d i s t r i b u t e dc l u s t e r ；c gt r e e ；i p v s ；l o a db a l a n c e厦门大学学位论文原创性声明兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明确方式标明。本人依法享有和承担由此论文而产生的权利和责任。声明人( 签名) ：龛习才沙汐扩年多月，日厦门大学学位论文著作权使用声明本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。本学位论文属于1 、保密() ，在年解密后适用本授权书。2 、不保密()( 请在以上相应括号内打“ )咔醐2 坼川日卢名名签签者师作导第一章绪论1 1 集群回顾第一章绪论i n t e m e t 的飞速发展给网络带宽和服务器带来巨大的挑战。从网络技术的发展来看，网络带宽的增长远高于处理器速度和内存访问速度的增长。热门网站引发前所未有的访问流量，很多网络服务因为访问次数爆炸式地增长而不堪重负。一些新兴的网络技术如视频点播，动态网页，c g i 等带来更大的网络带宽需求。这时单一的计算机系统，如单处理器或者s m p 系统，往往因为巨大的网络负载而不堪重负，其存在着诸多的问题，主要表现在：扩展能力差并且扩展的代价昂贵；升级导致的服务中断会带来巨大的商业损失，并造成原有计算资源的浪费；单点故障发生的概率较高导致无法提供持续的可靠服务。解决网络服务的可伸缩性和可靠性已是非常紧迫的问题。通过高性能网络或局域网互联的服务器集群【1 1 正成为实现高可伸缩的、高可用网络服务的有效结构。这种松耦合结构的服务器集群系统有下列优点：性能网络服务的工作负载通常是大量相互独立的任务，通过一组服务器分而治之，可以获得很高的整体性能。性能价格比优势组成集群系统的p c 服务器或r i s c 服务器和标准网络设备因为大规模生产降低成本，价格低，具有最高的性能价格比。若整体性能随着节点数的增长而接近线性增加，该系统的性能价格比接近于p c 服务器。所以，这种松耦合结构比紧耦合结构的多处理器系统具有更好的性能价格比。可扩展性高集群系统中的节点数目可以增长到几千个，乃至上万个，其伸缩性远超过单台超级计算机。高可用性在硬件和软件上都有冗余，通过检测软硬件的故障，将故障屏蔽，由存基于c g 树的分布式服务器集群的研究与实现活结点提供服务，可实现高可用性。目前集群系统因其诸多的优点，已被广泛应用于w e b 服务，c a c h e 服务，媒体服务，科学计算及数据库等领域。1 2 研究背景当前集群的研究主要在现高可伸缩性、高可用性服务的负载均衡技术上，下面简述当前服务器集群使用的几种负载均衡技术，并分析了几种典型服务器集群及其存在的问题。1 2 1 服务器集群的负载均衡技术在网络服务中，一端是客户程序，另一端是服务程序，在中间可能有代理程序。由此看来，可以在不同的层次上实现多台服务器的负载均衡。用集群解决网络服务性能问题的现有技术主要有以下几类：1 ) 基于r r - d n s 的负载均衡技术n c s a 2 的可伸缩的w e b 服务器系统就是最早基于r r d n s ( r o u n d r o b i nd o m a i nn a m es y s t e m ) 的系统原型。其结构和工作流程是：有一组w e b 服务器，他们通过分布式文件系统a f s ( a n d r e wf i l es y s t e m ) 来共享所有的h t m l 文档。这组服务器拥有相同的域名( 如w w w n c s a u i u c e d u ) ，当用户按照这个域名访问时，r r d n s 服务器会把域名轮流解析到这组服务器的不同i p 地址，从而将访问负载分到各台服务器上。这种方法带来几个问题：第一，域名服务器是一个分布式系统，是按照一定的层次结构组织的。当用户将域名解析请求提交给本地的域名服务器，它会因不能直接解析而向上一级域名服务器提交，上一级域名服务器再依次向上提交，直到r r d n s 域名服器把这个域名解析到其中一台服务器的i p 地址。可见，从用户到r r d n s 间存在多台域名服务器，而它们都会缓冲已解析的名字到i p 地址的映射，这会导致该域名服务器组下所有用户都会访问同一w e b 服务器，出现不同w e b 服务器问严重的负载不平衡。为了保证在域名服务器中域名到i p 地址的映射不被长久缓冲，r r d n s 在域名到i p 地址的映射上设置一个t t l ( t i m et ol i v e ) 值，过了这一段时间，域名服务器将这个映射从缓冲中淘汰。当用户请求，它会再向上2第一章绪论一级域名服务器提交请求并进行重新映射。这就涉及到如何设置这个t r l 值，若这个值太大，在这个订l 期间，很多请求会被映射到同一台w e b 服务器上，同样会导致严重的负载不平衡。若这个值太小，会导致本地域名服务器频繁地向r r - d n s 提交请求，增加了域名解析的网络流量，同样会使r r d n s 服务器成为系统中一个新的瓶颈。第二，用户机器会缓冲从名字到口地址的映射，而不受t t l 值的影响，用户的访问请求会被送到同一台w e b 服务器上。由于用户访问请求的突发性和访问方式不同，例如有的人访问一下就离开了，而有的人访问可长达几个小时，所以各台服务器问的负载仍存在倾斜( s k e w ) 而不能控制。第三，系统的可靠性和可维护性差。若一台服务器失效，会导致将域名解析到该服务器的用户看到服务中断。系统管理员也不能随时地将一台服务器切出服务进行系统维护，如进行操作系统和应用软件升级，这需要修改r r d n s服务器中的口地址列表，把该服务器的i p 地址从中划掉，然后等上几天或者更长的时间，等所有域名服务器将该域名到这台服务器的映射淘汰，和所有映射到这台服务器的客户机不再使用该站点为止。2 ) 基于客户端的负载均衡技术基于客户端的解决方法需要每个客户程序都有一定的服务器集群的知识，进而以负载均衡的方式将请求发到不同的服务器。例如，n e t s c a p en a v i g a t o r 浏览器访问n e t s c a p e 的主页时，它会随机地从一百多台服务器中挑选第n 台，最后将请求送往w w w n n e t s c a p e t o m 。然而，这不是很好的解决方法，n e t s c a p e只是利用它的n a v i g a t o r 避免了r r d n s 解析的麻烦，当使用l e 等其他浏览器不可避免的要进行r r d n s 解析。3 ) 基于应用层负载均衡技术多台服务器通过高速的互联网络连接成一个集群系统，在前端有一个基于应用层的负载均衡器。当用户访问请求到达负载均衡器时，请求会提交给做负载均衡调度的应用程序，分析请求，根据各个服务器的负载情况，选出一台服务器，重写请求并向选出的服务器访问，取得结果后，再返回给用户。应用层负载均衡的典型代表有z e n u s 负载均衡3 1 、p w e b l 4 1 、r e v e r s e p r o x y t 5 1 和s w e b t 6 , t a i 。3基于c g 树的分布式服务器集群的研究与实现基于应用层负载均衡的多服务器解决方法也存在一些问题。第一，系统处理开销特别大，致使系统的伸缩性有限。请求到达负载均衡器至处理结束，负载均衡器需要进行四次从核心空问到用户空间或从用户空问到核心空问的上下文切换和内存复制；需要进行二次t c p 连接，一次是从用户到负载均衡器，另一次是从负载均衡器到真实服务器；需要对请求进行分析和重写。这些处理都需要不小的c p u 、内存和网络等资源开销，且处理时间长。所构成系统的性能不能接近线性增加，一般服务器组增至3 或4 台时，负载均衡器本身可能会成为新的瓶颈。所以，这种基于应用层负载均衡调度的方法的伸缩性极其有限。第二，基于应用层的负载均衡器对于不同的应用，需要写不同的负载均衡器。以上几个系统都是基于h t t p 协议，若对于f t p 、m a i l 、p o p 3 等应用，都需要重写负载均衡器。4 ) 基于i p 层负载均衡技术用户通过虚拟p 地址( v i r t u a li pa d d r e s s ) 访问服务时，访问请求的报文会到达负载均衡器，由它进行负载均衡调度，从一组真实服务器选出一个，将报文的目标地址v i r t u a li pa d d r e s s 改写成选定服务器的地址，报文的目标端口改写成选定服务器的相应端口，最后将报文发送给选定的服务器。真实服务器的回应报文经过负载均衡器时，将报文的源地址和源端口改为v i r t u a li pa d d r e s s和相应的端口，再把报文发给用户；或者真实服务器直接将回应报文的源地址和源端口改为v i r t u a li pa d d r e s s 和相应的端口，发给用户。基于p 层负载均衡技术的典型代表是l i n u x 的集群自由软件项目l v s 9 , 1 0 , 1 1 】。这种负载均衡技术的实现效率是最高的，但是也存在一个重要问题：在调度时无法获得请求的资源内容，无法做到基于请求内容的调度。1 2 2 几种典型的服务器集群1 ) l i n u xv i r t u a ls e r v e rl i n u x 虚拟服务器( l i n u xv i r t u a ls e r v e r ，简称l v s ) 是由国防科技大学于1 9 9 8 年主持开发的集群自由软件项目，作为一种高可用性集群解决方案现被许多企业，研究机构，学校采用，许多l i n u x 发行版如r e d h a t 、t u r b o l i n u x 、红旗l i n u x 和中软l i n u x 也都提供了基于l v s 的集群解决方案。l v s 构建于实际4第一章绪论服务器集群之上，用户看不到提供服务的多台实际服务器，而只能看到一台作为负载均衡器的服务器。实际服务器通过高速局域网或者地理分布的广域网连接。实际服务器的前端是一台负载均衡器，它将用户的请求调度到实际服务器上完成，这样看起来好像所有服务都通过虚拟服务器来完成l v s 能够提供良好的可升级性，可靠性和可用性。用户可以透明地增加或减少一个节点，可以对实际服务器进行检测，如果发现有节点失败就重新配置系统。l v s 的结构如图1 1 ：图1 - 1l v s 结构图2 ) k t c p v sk t c p v s 1 2 l ( k e m dt c pv i r t u a ls e r v e r ) 是l v s 开发者开发的一个基于内容分布的集群系统。k t c p v s 集群的体系结构如图1 2 所示，主要是由两部分组成：一是k t c p v s 交换机，进行根据内容的调度；二是后端服务器，运行不同的网络服务。k t c p v s 交换机和后端服务器通过l a n w a n 互联。5桀十c g 树的j 布代服务器集群的研兜，实现圈1 - 2k t c p v s 集群的体系结构r 圄鱼峒盈国回k t c p v s 交换机将不同类型的请求发送到不同的后端服务器，冉将结果返回给客户，后端服务器时客户是不可见的。k t c p v s 集群的结构对客户是透明的，客户访问集群提供的| 捌络服务就像访问一台高性能、高可用的服务器一样。3 ) 主动式集群主动式自调度集群服务器( a s a s ) 是由国防科技大学计算机学院并行与分布处理国家重点实验室针对现有服务器结构存在的不足推出的一种w e b 服务器体系结构，在该体系结构中，取消了传统的负载均衡机制和心跳机制，系统基本部分有前端的分发器、执行服务器、后端数据存储三部分组成，其体系结构如图卜3 所示。第一章绪论g，囝1 4主动式集群弼鲳服务器体系结构主动式集群中，由执行服务器主动向分发器索取用户请求，前端分发器在请求队列中获取执行服务器的请求并转发到执行服务器，最后由执行服务器直接对用户服务，该集群有效减少了前端分发器的通信负载，并解决了l j i 端分发器在高负载情况下的活锁问题。1 2 3 典型服务器集群的结构的缺点由上文几种服务器集群可以看出，它们普遍采用的结构如图l 一4 ：集群前端有一个或者多个负载均衡器i 】”( l o a db a l a n c e r ) ，后端有一个服务器池，由多台真实服务器, ( r e a ls e r v 啪构成。外界请求到达集群时，先通过l o a db a l a n c e r 按照某种调度算法均衡的把每个请求发送到服务器池的每台r e a ls e r v e r 上，然后出r e a ls e r v e r 把服务通过l o a db a l a n c e r 或者直接发给客户。集群内部问的节点通信对外是透明，整个集群系统对外像是一台高性能服务器在运行。婀基于c g 树的分布武服务# 集群的研究i i 宴r口口口_ _口i -图1 4服务器集群典型结构这种集群结构的缺点：1 ) 前端负载均衡器既要负责对外界请求修改并转发，又要对真实服务器进行定时检测以维持集群的健壮性。当真实服务器的数量达到一定规模时，山于服务器节点池采用的是单层线性结构，每个服务器都直接与负载均衡器相连，导致了前端负载均衡嚣与后端真实服务器的通信量会大大增加，这样会加重负载均衡器的负担，因此限制了集群的可扩展性和规模。2 1 由于在分布式环境中，不同网络节点的通信存在困难，因此现有的服务器集群大部分都足构建于局域网，不适合分布式网络。3 ) 无法按服务对象的地域分布特征，配置服务器集群，以改善服务质量，并统一管理整个集群。主动式集群虽然解决了前端负载均衡器负载过重的问题，但是在构建分布网络集群服务器仍然存在困难。第一章绪论1 3 研究工作文献【5 1 提出了一种适用于分布式集群的模型c g 树：将集群的节点分级分层，组织成以前端调度节点为根节点的树结构。该模型下前端负载均衡器不必跟服务器池的所有节点通信，有效减小了负载均衡器的负载。在构建跨网络集群时，可将集群节点分组，大大减少不同网络问的网络开销，是跨网络集群的一个较好的解决方案。然而该文献的实现上存在以下不足：使用m p i c h 1 6 】构建媒体服务器集群，系统大量使用s h d l 和p e r l 脚本，不适合跨平台的使用；通信方面使用高级的并行通信原语m p i ，整体性能不高；使用基于应用层的负载均衡技术，集群系统的调度效率不高，系统对外服务的吞吐量不高。本文的工作是在文献【1 5 】的基础上，对其实现的不足进行改进，主要工作如下：1 在c g 树模型下提出一套可行的，简化的通信协议。在该模型协议下，能保持集群模型的健壮性。通信协议的设计主要包括以下几个模块：1 ) 心跳模块：在就绪状态下，组员向组长发送心跳消息，告知组长自己的情况。2 ) 象合并模块：当组长收到某一组员发过来的象，执行该模块，保持象的统一。3 ) 调整模块：当某个节点出现故障时，c g 树调整到一个稳定的状态；当故障恢复时，能将c g 树调整回故障前的结构。2 应用高效s o c k e t 通信原语和多线程技术，结合口负载均衡技术构建一个集群原型。该集群原型在本文设计的通信协议下能实现集群节点的自动加入和删除，这些动作对于外面用户是透明的，因而能保持集群的高可用性。3 在i p 负载均衡技术下，结合客户端，实现一种基于内容的调度。1 4 论文的结构本论文共有六章。第一章为绪论。本章首先介绍了现有的负载均衡技术和几种典型服务器集群，并分析了典型服务器集群结构的缺点，引入课题的内容。第二章为系统模型。首先引入c g 树相关概念，然后在该模型下设计一种9基于c g 树的分布式服务器集群的研究j 实现新的通信协议，并给出了在此协议下模型的相关性质，并探讨了c g 树的使用背景。第三章为i p v s 分析及其在c g 树的拓展。分析了i p v s 技术，重点研究了i p v s 技术在c g 树的应用，提出两种c g 树的集群解决方案及c g 树的i p v s管理。第四章为基于内容调度。分析了基于内容调度的意义和已有的解决技术，提出一种在i p v s 技术下的基于内容调度方案。第五章为系统实现。主要介绍了系统的实现与设计，并分析了系统的各个模块的实现细节。第六章为实验部分，测试该系统的性能，并分析其优缺点。第七章为结束语，首先对本文的工作进行总结，然后提出了不足之处和今后的工作。1 0第二章集群模型第二章集群模型集群节点采用分级分层的结构，能有效减轻集群前端负载均衡器的负担，并能有效地减少跨网络集群节点间的通信开销。本章首先给出c g 树的定义，并在c g 树的结构下提出一套针对该模型的通信协议和算法，以增强系统的高可用性和容错能力。最后给出基于该通信协议下的c g 树模型的一些性质。2 1c g 树的定义c g 树是一种通用的适用于大范围网络的分布式集群结构模型。由于它不同于传统的树的概念，以下从集合和关系的角度入手给出这个结构的定义1 5 】：定义2 - 1 组关系设非空集合，定义上的关系r 具有如下特点：( 1 ) v b n ，3 a n ，使得 r( 2 ) 若 r ，贝i j r( 3 ) 若 r 且 r ，贝l ja = c则称关系尺为组关系，关系元素 中的a 称为组长。定义2 2 同组关系设非空集合和上的组关系尺，定义其上的关系q 具有如下特点：( 1 ) v a ，b n ，若 r ，贝q q( 2 ) v a ，b n ，若 q ，贝i j q( 3 ) v a ，b ，c n ，若 q 且 q ，贝l j q则称关系q 为在集合的组关系尺上的同组关系。定义2 - 3c g 森林( c l u s t e rg r o u pf o r e s t ) 、c g 树( c l u s t e rg r o u pt r e e )给定集合和关系序列局，马，局，其中蜀是定义在n 上的组关系，基于c g 树的分布式服务器集群的研究与实现r 川( 1sk ，一1 ) 是定义在r i 的所有组长集合上的组关系，记作r 一 ，并称r 为c g 森林，羁的下标f 称为c g 森林的层( 1 e v e l ) 。若马中只有一个元素，则称这样的c g 森林为c g 树。c g 树的象就是整棵c g树的结构。如图2 1 是一c g 树的结构图。2 2c g 树的状态2 2 1 象的状态图2 - 1c g 树结构图由于集群系统在运行过程中，可能由于某些节点出现故障或者有新节点加入，而导致集群一些节点的象发生改变，而节点的象必须往上通知其组长，才能保证最后顶端节点获得的象是一个正确的象。为了下文协议的设计，本文定义两种象的状态：1 ) 未确认的象：节点的象发生改变，还未通知组长，或者已通知组长但还未收到回复确认，此时节点的象为未确认的象。2 ) 已确认的象：反之，节点的象为已确认的象。1 2第二章集群模型2 2 2 集群的状态本文为典型的分布式集群系统定义了几种状态：初始、就绪、重组。从集群系统开始启动至各个节点初始化完成这一过程，为集群系统的初始状态。在此过程中，启动模块将按照c g 树所描述的结构将系统构建起来。之后，系统立刻进入就绪状态。当集群系统内部的个别节点出现故障，以致影响到c g 树的结构时，系统切换到重组状态。系统完成重组后，又重新回到就绪状态。以下定义了c g 树集群的两种状态：就绪状态：c g 树中所有节点的象都是已确认的象，称为c g 树处于就绪状态；重组状态：c g 树中至少有一个节点的象是未确认的象，称为c g 树处于重组状态。2 3c g 树通信协议的设计下文我们将设计一套基于c g 树的通信协议，目标是：正常情况下保证c g树的稳定通信；在某个节点出现故障时，c g 树能调整到一个稳定状态；当节点故障恢复时，c g 树能恢复到节点出现故障前的状态。考虑到通信协议的复杂性，我们在实现通信协议时，在已知c g 树结构的情况下，把c g 树的逻辑结构转化为物理结构，即传统的树结构。如图2 2 为一棵c g 树到传统树的转变。转化的规则为：保持树的父子节点关系不变，若父节点和子节点相同，则删除子节点。转变后组长和组员的关系不变。在传统树结构中，每个节点无需保存整棵树的象。本文定义每个节点的象为以该节点为根的子树结构，整棵树的树根为顶端节点。1 3基于c g 树的分布式服务器集群的研究j 实现2 3 1 消息包的设计图2 - 2c g 树到传统树的转变在分布式系统中，节点之间的通信是以消息为载体，且建立在基本的接收和发送原语基础上f l5 。以下给出了消息的定义：定义消息为包含了消息头部和消息主体的二元组，记为m = ( h ，c ) ，其中消息头部为一个三元组h = ( u ，s ，r ) ，且u 为消息类型，s 、r 分别为消息发送方和消息接收方的节点编号，消息主体c 为消息的具体内容。在考察分布式通信协议的算法和策略时，需定义消息类型，来区分不同操作。表2 1 是本文涉及到一些消息类型：表2 - 1c g 树消息类型及其描述消息类型描述内容与作朋标识心跳消息( 不带象)当组员的象是已确认的象时，组员定时向组长发送信息u l心跳消息( 带象)当组员的象是为已确认的象时，组员对组长发送信息u 2带象心跳确认组长对组员发送的带象心跳消息的答复u 3组长对组员发送消息，以请求组员发送带象心跳信息给组发象请求消息u 4长调整过程中组长发现其儿子节点出现故障时，对其孙子节组长更换消息u 5点发送组长更换消息，将其纳为自己的组员。故障现场恢复消息恢复过程中，将原来故障节点故障时的象发送给恢复节点u 61 4第二章集群模型2 3 2c g 树的通信模块基于c g 树的定义，以下按照不同的功能，将c g 树的通信模块分为以下几个模块：初始化模块，心跳模块，象合并模块，调整模块，消息接收模块。1 初始化模块集群后端的主机节点并不严格要求同构，其硬件条件可能不尽相同，可以是普通p c 机，也可以是专用服务器，同时，同一类体系结构的主机性能也存在差异。可依据主机节点的性能好坏以及网络结构配置一棵c g 树，尽可能让性能好的主机出现在组长位置上，承担较多任务。由于c g 树正常情况下的通信是组内的通信，所以尽可能让同一网络的节点同组，从而减少c g 树中不同网络间的通信开销。集群节点在加入集群之前，应该设置基本信息：组长和组员信息。初始化时，根据基本信息，完成象的初始化。该模块的算法描述如下：2 心跳模块心跳机制【1 7 1 是高可用集群的基础技术。心跳的功能是周期性地检测集群中节点机器的工作状态，当节点机器工作状态出现变化时，能够通知集群软件的其它部件。本集群模型将采用心跳机制来维持c g 树的高可用性，由各组员节点周期性地向组长发送心跳信息，已告知组长其最新的状态。心跳信息是c g通信中的主要消息，为了减少不必要的通信开销，我们将根据节点象的状态来1 5基于c g 树的分布式服务器集群的研究与实现决定心跳消息是否带象。该模块的算法描述如下：3 象合并模块c g 树集群系统中常常由于集群节点发生改变( 如节点失效，新节点加入，节点删除等) 而导致c g 树的象发生改变。当某一节点的象发生改变时，应及时通知组长告知其变化以保证象的j 下确性。其中象合并操作是c g 树通信协议的基本操作，算法描述如下：1 6第_ 二章集群模型算法2 - 3 象合并模块算法4 调整模块在描述c g 树调整算法之前，必须先给出失效节点的判定规则。集群中的节点失效可能与很多因素有关。从节点自身来看，如下原因均可能造成节点失效：节点自身的网络接口故障、节点正常或非正常关机或重启、节点因软件故障导致本节点失效；从网络方面来考察，也有多种原因：节点自身网络故障、节点所在组的网络接口断开、两个组之间的路由故障等。由于集群的网络结构可能比较复杂，如果其他节点没有应答，节点很难确定是自身故障还是其他节点出现问题。本文采用的办法是从节点自身出发来考察，在这种情况下，每个节点都认为是对方节点出现故障。这罩给出了节点失效的判定规则：节点a 在给定的时间内未收到组员节点b 的应答，则节点彳认为节点b 失效，并称这段时间为故障设定时间，记为t ，。为了以后故障节点恢复时能将c g 树的象恢复到故障前的状态，我们必须保存故障节点发生故障时的象，我们称该象为故障象。每个c g 树的节点都维护着一个故障象的队列，我们将这个队列声明为l i s tf i ；在判断出失效节点后，节点自身启动调整模块( 详细算法描述见下图) ，对c g 树进行重组。目前对c g 树的调整算法是基于以下四条原则：1 7基于c g 树的分布式服务器集群的研究j 实现调整模块是在以顶端节点不出故障的前提下能尽快将c g 树重组；必须把节点发生故障的损失减少到最小；将故障节点的组员交由其组长接管；便于保持故障前后象的一致性。5 消息接收模块c g 树的节点根据所接收到的消息的类型，做出相应的动作，详细算法描述如下：1 8第二章集群模型算法2 - 5 消息接收模块算法描述：消息接收过程。输入：节点i 及其象五，消息从输出：节点f 的象五。令消息胙饵c 上其中胙f ，u f a 则根据u 的类型做出不同的响应：1 ) 当泸们时a ) 若”不是f 的组员，查找队列l i s tf i 是否有节点“的象，若有则将”纳入i 的组员，将“以单独的分支添加入象五中f 节点下，并将象五设置为未确认状态，然后对节点u 发送故障现场恢复消息，设消息m = 一c ) ，其中h 一( ，阮z ”上c 为l i s tf i 中节点“的象厶；若l i s tf i 无节点u 的象，则将u 纳入i 的组员，将材以单独的分支添加入象五中f 节点下，并将象五设置为未确认状态，然后对节点“发送法象请求消息，设消息m = 一c ) ，其中h =亿m l u ) ，c 为空；b ) 若u 是i 的组员，则结束。2 ) 当u = u 2 时a ) 若u 不是i 的组员，查找队列l i s tf 1 是否有节点“的象，若有则执行象合并操作，然后对节点“发送故障现场恢复消息，设消息m = 商c ) ，其中h 一亿悔z “上c 为l i s t f i 中节点“的象厶；若l i s tf 1 无节点“的象，则执行象合并操作，然后对节点“发送带象确认消息，设消息m = 戤c ) ，其中h 一( ，观z 材上c 为空；b ) 若“是i 的组员，则执行象合并操作，然后对节点“发送带象确认消息，设消息m = 一c ：) ，其中h = ( ，如五”土c 为空。3 ) 当u = u 3 时，将节点f 的象五的状态设置为已确认状态。4 ) 当u = u 4 时，将节点f 的象五的状态设置为未确认状态。5 ) 当弘w 时，将节点f 的组长更新为”，并将节点f 的象五的状态设置为未确认状态。1 9基于c g 树的分布式服务器集群的研究0 实现6 结合例子考察c g 树的调整和恢复过程下面针对具体例子考察其调整过程和恢复过程：1 ) c g 树的初始状态如图2 - 3 ( a ) 假设节点2 失效，则顶端节点1 因t f 时间内未收到组员2 的心跳信息，触发调整过程；同理，由于节点2 自认为自己没故障，而认为其组员故障，也会触发调整过程。根据调整模块，节点l 将节点2 的象如图2 - 3 ( b ) 保存至故障象队列中，删除节点2 的象分支，然后向节点2 的组员4 发送组长变更消息。若节点4 未出现故障，将收到节点1 发送过来的组长变更消息，然后更新节点1 为自己的组长，向组长1 发送带象心跳。节点l收到节点4 发送而来的带象心跳消息后，将组员4 纳入自己的组员列表，并执行象合并操作后得到节点l 的象如图2 - 3 ( c ) 所示。同理节点2 也启用调整模块，经过一段时间达到就绪状态时如图2 4 ( d ) 。图2 3 ( a ) c g 树的初始状态图2 - 3 ( b ) 节点2 的故障象第一二章集群模型图2 1 3 ( c ) 节点1 的调整过程图2 - 3 ( d ) 节点2 的调整过程2 1o基于c g 树的分布式服务器集群的研究j 孑实现图2 - 3 ( e ) c g 树的恢复过程2 ) 由于节点2 不知道自身出现故障，一直都定时向其组长i 发送心跳消息，当故障恢复时，节点2 发送的心跳消息被节点1 接收，节点查找故障象队列l i s tf i ，发现l i s tf i 保存有节点2 的故障象如图2 - 3 ( b ) ，则象节点2 发送故障现场恢复消息。节点2 收到节点l 发送而来的故障现场恢复消息后，将其自身象更改为该故障象，然后向其组员发送组长变更消息，并继续向组长发送心跳消息( 带象) ，组长收到带象心跳消息后，执行象合并操作，完成整个调整过程，如图2 3 ( e ) 。第二章集群模型至此，图2 - 3 ( a ) 至图2 3 ( e ) 显示了当集群内部节点出现故障时，c g 树根据上文的调整算法进行重组。当节点故障恢复时，c g 树根据故障象进行重组。可以发现故障前后c g 树的象是一致的。上述算法都是在顶端节点不出问题的情况下进行调整的，由于大部分集群的顶端节点都是高性能服务器，并且一般都有备份服务器在其出现故障的情况下顶替顶端节点，因此顶端节点的故障是可以忽略的，可见我们上文的调整算法是比较简单，可取的。2 4c g 树的性质及实用背景2 4 1c g 树的相关性质下面给出c g 树模型在上述的通信协议下的相关性质：定义2 4 ：若c g 树集群系统处于就绪状态，且所有的组长和组员之间都可以相互通信，则称集群系统稳定。性质2 1 ：系统稳定时，项端节点的象是整个系统的全局象且保持不变。证明：由于每个组长的象都是由其组员的象构成，而顶端节点是c g 树的根，显然顶端节点的象是系统的全局象。由定义璺碍易知，c g 树处于就绪状态下，即所有节点的象都是已确认的象，故发送心跳消息时都不带象，不会引发组长节点收到象而使象发生改变，故项端节点的象保持不变。性质2 2 ：若c g 树中某一个节点出现故障，则在有限时间后，系统稳定。证明：设节点y 出现故障，即节点y 与其组长节点材无法通信。则节点u 向节点v 的所有组员发送组长变更消息，等待其发送心跳消息，若收到心跳消息，则将该节点加入节点“的组员中，更新节点”的自身象，所需时间乃2 然后节点厂逐层向上通知其象变化，所需时间乃2 x h x 2 r ：, h 为树高。此时c g树处于就绪状态，且组长与组员问皆可相互通信，即系统稳定。达到系统稳定的时间弘乃+ 乃2 x 砌4 - j 夕x 2 r ：, 其中h 1 0 9 叼+ j ，n 为节点数，则其通基于c g 树的分布式服务器集群的研究与实现性质2 3 ：当某一节点在发生故障和恢复期间没有其它节点发生故障或者加入，则恢复后达到稳定状态时的顶端节点的象和发生故障前的象保持一致。证明：设发生故障和恢复的节点为1 ，其父节点为”，则发生故障后，节点”调用调整模块，并保存节点“的故障象厶，若调整过程有节点y 的儿子节点m ，v 2 ，加入，调整后u 的象增加分支，l ，；故障恢复后，节点，从节点以获得故障象厶，l ，气，必定与l u 的分支相同，根据象合并操作，则删除，乇，分支，并增加分支厶，则恢复后“的象必和故障前“的象必保持一致。而期间过程其它节点未发生变化，根据性质2 1 ，则顶端节点的象恢复后的象和故障前的象保持一致。2 4 2c g 榭的实用背景至此，我们讨论了c g 树的通信协议及其相关性质。在实际应用中，c g 树可以应用于跨网络的集群环境。一般来说，距离越远的节点之间通信延迟越大，我们的原则是尽可能将临近的主机( 如同一个局域网) 放置于同一组内，然后按地区和地域分布再逐层划分。如果局域网的主机较多，可以在同一个局域网中再分为多个组，一般不将不同网络的节点放置同一组内。这样，节点问在进行跨网络通信时，只通过上层的组长节点进行转发，而不采用两两通信，整个集群系统的通信量将就会显著减小。此外集群可以对节点的故障检查并进行调整，保证了集群系统在顶端节点不出故障下的高可用性。2 5 本章小结本章首先引入适用于分布式集群，特别是跨网络集群的系统模型c g 树，介绍了其相关定义。针对该模型，提出一系列通信协议，包括初始化模块，心跳模块，象合并模块，调整模块和消息接收模块。在顶端节点不出故障的情况下，集群内部节点出现故障时能自动进行重组，减少集群故障的损失，保证集群的高可用性；并且在故障恢复时，能保证故障前后c g 树象的一致性。最后2 4第二章集群模型给出c g 树模型在该通信协议下的性质及实用的背景。特别地，传统的应用服务器集群结构，如l v s 集群，是c g 树单层结构的特例。c g 树的这种分层结构更具有普遍意义，可以较清晰地描述广义的分布式集群系统及其网络结构。同时，本章提出的针对c g 树的一系列操作和算法，也为构建分布式集群系统，特别是跨地域的大型集群系统的构建提供了通用的解决方案。第三章i p v s 分析及其在c g 树的拓展第三章i p v s 分析及其在c g 树的拓展3 1i p v s 技术计算机集群系统的核心问题是资源的共享和有效利用，只有平衡的负载才能达到最大的资源使用率。负载均衡【婚j 的任务是：当外界请求到达前端负载均衡器时，负载均衡器按照某一特定调度算法从一组真实服务器中选出一台服务器，然后将外界请求转发到该服务器。现有的负载均衡技术主要有：基于r r d n s 的负载均衡技术、基于客户端的负载均衡技术、基于应用层负载均衡技术和基于口层负载均衡技术。由于口负载均衡技术是通过对网络的i p 报文的修改和转发实现外界请求的调度，因此其效率是最高的。i p 虚拟服务( i pv i r t u a ls e r v i c e ，简称i p v s ) 是l v s 项目的核心模块，其实现了三种i p 负载均衡技术】，性能得到广泛的肯定。3 1 1v s n a t 方式n a t 技术【侈】是解决i p 短缺的一种技术，它允许内部网络使用保留的i p 地址连入i n t e m e t ，使得i n t e m e t 上的主机数可以大大多于可用的实际i p 地址。v s n a t 允许集群内部服务器使用内部地址，而前端的负载均衡器必须使用外部地址，他们是通过s w i t c h h u b 相连接的。其工作流程为：客户通过v i r t u a li p a d d r e s s ( 虚拟服务的i p 地址) 访问网络服务时，请求报文到达负载均衡器，负载均衡器根据连接调度算法从一组真实服务器中选出一台服务器，将报文的目标地址v i r t u a li pa d d r e s s 改写成选定服务器的地址，报文的目标端口改写成选定服务器的相应端口，最后将修改后的报文发送给选出的服务器。同时，负载均衡器在连接h a s h 表中记录这个连接，当这个连接的下一个报文到达时，从连接h a s h 表中可以得到原选定服务器的地址和端口，进行同样的改写操作，并将报文传给原选定的服务器。当来自真实服务器的响应报文经过负载均衡器时，负载均衡器将报文的源地址和源端口改为v i r t u a li pa d d r e s s 和相应的端口，再把报文发给用户。基于c g 树的分布式服务器集群的研究1 ；实现这样，客户所看到的只是在v i r t u a li pa d d r e s s 上提供的服务，而服务器集群的结构对用户是透明的。3 1 2v s t u n 方式在v s n a t 的集群系统中，请求和响应的数据报文都需要通过负载均衡器，当真实服务器的数目在l o 台到2 0 台之间时，负载均衡器将成为整个集群系统的新瓶颈。大多数i n t e m e t 服务都有这样的特点：请求报文较短而响应报文往往包含大量的数据。如果能将请求和响应分开处理，即在负载均衡器中只负责调度请求而响应报文直接从真实服务器返回给客户，将极大地提高整个集群系统的吞吐量。i p 隧道2 川( i pt u n n e l i n g ) 是将一个i p 报文封装在另一个i p 报文的技术，这可以使得目标为一个i p 地址的数据报文能被