（计算机应用技术专业论文）分布式系统负载均衡策略研究.pdf

中南大学硕士学位论文李登：分布式系统负载均衡策略研究 摘要 在计算机发展进入了网络计算的新阶段中，分布式系统已得到了越来越广泛 的研究和应用。显然，未来对计算速度、系统可靠性和成本实效性的要求必将促 使发展另外的计算机模型来替代传统的冯诺依曼结构的计算机。由于分布式系 统的并行性降低了处理的瓶颈，提供了更好的性能价格比，且具有在系统出现故 障的情况下继续运行的潜力，因而分布式系统将具备更大的发展空间。 而分布式系统的优化主要指的是负载均衡。虽然负载均衡研究至今已有近 2 0 年的研究历史，但由于负载均衡策略是n p 完全问题，真f 令人满意的实现系 统并不多。 本文首先讨论了分布式系统及分布式对象技术，然后分章节详细而全面地研 究了负载均衡的算法和模型，研究了产生额外开销的原因，负载均衡策略研究中 的困难。 本文的创新之处首先是在于提出了信息中心调度策略，该策略是在广泛研究 了目前典型的负载均衡策略诸如分散式、集中式、发送启动和接收启动的基础上， 综合其优点，克服其缺点，具备较大的适用性和实用性，可以作为企业化产品开 发的基础。 其次，针对目前国内外的研究都集中在策略的提出上，对实现模型的研究比 较少的情况，为此本文在综合各种负载均衡策略的基础上按照性能递增的顺序结 合网络拓扑结构构建了链式模型、网状模型和链网模型这几种实现模型，并对其 进行了系统的研究，对几种模型给出了各自相应的算法，并进行了评价，指出了 这几种模型各自的优缺点及适用范围，分析了链网模型在动态负载均衡实现方面 突出的优越性及高性能。这些模型以前面提及的策略为依据，将抽象的策略形象 化，有助于进一步研究的借鉴。 最后，不同于一般的并行分布式实验以p v m 进行实验，本文中对信息中心调 度策略实现模型是依托先进的j a v ar m i 技术，将分布式理论和分布式实现技术 有机的结合了起来，为后继的分布式理论产业化研究打下了基础。 关键词：分布式计算，负载均衡，动态负载均衡，阈值，r m i 中南大学硕士学位论文李登：分布式系统负载均衡策略研究 a b s t r a c t w i t ht h ec o 叩u t e rt e c h n o l o g ye n t e r i n gt h ep e r i o do fn e t w o r kc o m p u t i n g ， r e s e a r c h e sa n da p p l i c a t i o n so nd i s t r i b u t e ds y s t e mh a v eb e e nw i l d e ra n d w i l d e r a p p a r e n t l y ， t h e r e 叫s tb eo t h e rc o 皿p u t e rs t r u c t u r e ss u b s t i t u t e t h et r a d i t i o n a lv o nn e u m a n ns t r u c t u r e t h ed a r a l l e la n dd i s t r i b u t e d s y s t e md e p r e s s e st h eb o t t l e n e c ko fp r o c e s s i n ga n dp r o v i d e sb e t t e rr a t i o o fp e r f o 瑚a n c et op r i c e a n dd i s t r i b u t e ds y s t e mc a nc o n t i n u et of u c t i o n w h e nt h e r ea r ef a u l ti np a r t so ft h es y s t e ns ot h e r ea r e 叫c hm o r e d e v e l o p m e n ti nd i s t r i b u t e ds y s t 锄i nf u t u r et h a nt o d a y t h eo p t i i z a t i o no fd i s t r i b u t e ds y s t e r e f e r st ol o a db a l a n c i n g t h o u e h p e o p l eh a v er e s e a r c h e do n1 0 a db a l a n c i n gf o ra b o u t2 0y e a r s ， t h e r ea r e f e ws y s t e m sa r es a t i s f i e db e c a u s e1 0 a db a l a n c i n gi san pd r o b l e m t h ep a p e rp r e s e n t st h e o r vo fd i s t r i b u t e ds y s t e ma n dt e c h n o l o g yo f d i s t r i b u t e dc o m p u t i n ga tf i r s t ，t h e nr e s e a r c h e so na l g o r i t h sa n dm o d e l s o fl o a db a l a n c i n gp a r t i c u l a r l ya n dr o u n d l y i nt h i sp a p e r ，w ea n a l y z i s t h ec a u s a t i o n so ft h ee x t r as p e n d i n gi nd i s t r i b u t e ds v s t e ma n dt h e d i f f i c u l t i e si nt h e1 0 a db a l a n c i n gr e s e a r c h e s o u rf i r s ti n n o v a t i o ni sp r e s e n t san e 1 0 a db a l a n c i n gp o l i c yw h i c hi s b a s e do nt h er e s e a r c ho nt y p i c a l1 0 a db a l a n c i n gp o l i c i e ss u c ha s d i s t r i b u t e d 、c e n t r a l i z e d 、s e n d e r i n i t i a t e da n dr e c e i v e r i n i t i a t e dn o l i c v o u rl o a db a l a n c i n gp o l i c ys y n t h e s i z e sa b o v ep o l i c i e s m e r i t sa n dg e t s o v e rt h e i rs h o r t c o m i n g i t i sm o r ea p p l i c a b l ea n dp r a c t i c a b l e ，a n dc a n b et h eb a s i so ft h ed e v e l o p m e n to ft h ei n d u s t r i a lp r o d u c t s s e c o n d l y ， m o s tc u r r e n tr e s e a r c h e sh a v e b e e nc o n c e n t r a t i n go nt h e p r o p o s i n go ft h ep o l i c i e s r e s e a r c h e so nt h ei m p l e m e n t a t i o nm o d e lb a s e d o nt h ep o l i c ya r ef e w a f t e rr e s e a r c h i n gs e v e r a lc u r r e n tl o a db a l a n c i n g p o l i c y ， w eb u i l d ss e v e r a li p l e m e n t a t i o nm o d e l ss u c ha sc h a i nm o d e l ， r e t i c u l a t i o nm o d e la n dc h a i n r e t i c u l a t i o nm o d e li n c r e a s e db vd e r f o r 衄n c e a n dr e s e a r c h e st h e mc o m p r e h e n s i v e l vb a s e do nn e t w o r kt o p o l o g y e a c h o d e l i s g i v e nc o r r e s p o n d i n ga l g o r i t h ma n de s t i m a t i o n t h ea d v a n t a g e sa n d s h o r t c o m i n g sa n da p p l i c a b l er a n g e so fe a c h o d e la r ea l s og i v e n t h ep a p e r e s p e c i a l l ye m p h a s i z e dt h ec h a i n r e t i c u l a t i o nm o d e l ss u p e r i o r i t ya n d h i g hp e r f o r a n c eo nd y n a i cl o a db a l a n c i n g t h e s em o d e l sw ep r e s e n t e db a s e o na b o v ep 0 1 i c i e sa n dv i s u a l i z ea b s t r a c tp o l i c e s t h e yc a nb eu s e df o r r e f e r e n c eb yo t h e rr e s e a r c h e s a tl a s t ，o u re x p e r i m e n t a t i o nu s e sj a v ai 瑚ib u tn o tp v mu s e db y 叫c h 咖y p a r a l l e la n dd i s t r i b u t e de x p e r i m e n t a t i o n s w ec o m b i n ed i s t r i b u t e d t h e o r i e sw i t hr e a l i z a t i o nt e c h n 0 1 0 9 yt h a tw o u l db eb a s i so ft h e i n d u s t r i a l i z a t i o ni n 。f u t u r e k e y w o r d s ：d i s t r i b u t e dc o m p u t i n g ，l o a db a l a n c i n g ，d y n a m i c1 0 a db a l a j l c i n g t h r e s h o l d r m i 2 中南大学硕士学位论文李登：分布式系统负载均衡策略研究 第一章概论 1 1 本文研究所应用的技术 随着日益迫切的对计算速度、系统可靠性和成本实效性的要求，另外的计算 机模型必将出现而取代传统的冯诺依曼型结构的计算机。计算机网络的出现， 使分布式计算成为可能。当用户需要完成任何任务时，分布式计算提供对尽可能 多的计算机能力和数据的透明访问，同时实现高性能与高可靠性的目标。 1 1 1 分布式对象技术的产生 分布式对象技术是伴随网络而发展起来的一种面向对象的技术。以前的计算 机系统多是单机系统，多个用户是通过联机终端来访问的，没有网络的概念。网 络出现后，产生了c l i e n t ，s e r v c r 的计算服务模式，多个客户端可以共享数据库服 务器和打印服务器等等。随着网络的更进一步发展，许多软件需要在不同厂家的 网络产品、硬件平台、网络协议异构环境下运行，应用的规模也从局域网发展到 广域网。在这种情况下，c l i e 州s e r v e r 模式的局限性也就暴露出来了，于是中间 件应运而生。中间件是位于操作系统和应用软件之间的通用服务，它的主要作用 是用来屏蔽网络硬件平台的差异性和操作系统与网络协议的异构性，使应用软件 能够比较平滑地运行于不同平台上。同时中间件在负载平衡、连接管理和调度方 面起了很大的作用，使企业级应用的性能得到大幅提升，满足了关键业务的需求。 但是在这个阶段，客户端是请求服务的，服务器端是提供服务的，它们的关系是 不对称的。随着面向对象技术的进一步发展，出现了分布式对象技术。可以这么 说，分布式对象技术是随着网络和面向对象技术的发展而不断地完善起来的。 分布式对象计算中，通常参与计算的计算体( 分布对象) 是对称的。分布对 象往往又被称为组件( c 驴n e m ) ，组件是一些独立的代码的封装体，在分布 式计算的环境下可以是一个简单的对象，但大多数情况下是一组相关的对象复合 体，提供一定的服务。分布环境下，组件是一些灵敏的软件模块，它们可以位置 透明、语言独立和平台独立地互相发送消息，实现请求服务。 1 1 2 分布式对象技术与传统的面向对象的技术的不同 我们知道，传统的面向对象技术有两个基本的特点：封装性和继承性，通常 其强调的是代码复用，对象往往仅存在于一个程序中，程序的外界并不可能感知 和访问这些对象。而分布式对象技术主要使用了面向对象技术的封装性，组件可 以分布在网络的任何位置。对外界来说，它所需关心的只是组件的界面，至于内 部是如何实现的则无需考虑，远程客户通过方法调用来访问它。这是分布式对象 技术和传统的面向对象技术的最大的不同点。 此外，分布对象计算系统中都不支持跨站点的继承性，例如，假设对象1 是对象2 的一个特伊j ，而2 个对象将要分布在不同站点上，如果完全按照面向对 象的概念的话，对象1 可以继承对象2 的代码和数据；但是在分布式环境下，对 象1 要想继承对象2 的代码和属性是非常困难的，没有任何一个分布系统能够支 持这种继承性，因为实现代价太大。 中南大学硕士学位论文李登：分布式系统负载均衡策略研究 另外，在分布式对象里我们一般不提对象，而提组件( 或叫构件) 。那么， 组件和对象有什么区别昵? 我们知道，在面向对象技术里可以有很小的一个对 象，比如说一个邮政编码做一个对象；但在分布对象计算中，我们往往会把一些 小的相关的对象组合在一起，形成一个相对比较大的组件，通过这个组件来提供 一系列的服务。分布式对象技术的基本概念之一就是所谓构件( c o m p o n e n t ) 概 念。构件可以跨越平台、网络、语言、应用程序、工具、硬件而运行。随着i n t e r n e t 的发展，我们可以预见新型的应用体系结构正在产生，其生成、创建、开发、运 行和管理的方式及其功能都与局域网的应用程序不同。它将彻底改变生产软件的 传统模式，目前普遍认为在i n t e r n e t 网上开发未来的软件，应当以构件为基本 单位，软件开发者可以边在网上订购所需的构件，一边构造目标软件。而从网上 购得的构件，由c o m 和c 0 r b a 这样的标准软总线提供运行所需的各种服务。分布 式对象技术追求的目标是软件无缝连接，即插即用。构件不仅可重复使用和提高 效率，还可以节省硬件资源，如果采用了构件程序设计思想，可以随时更换有问 题的模块，以降低其维护成本。 1 1 3 目前分布式对象技术的3 种主流技术0 0 m 、j a v a 和c o b r a 目前国际上，分布式对象技术有三大流派_ c 0 b r a 、c 0 m d c 0 m 和j a v a 。 c o r b a 技术是最早出现的，1 9 9 1 年0 m g 颁布了c o b r a1 0 标准，在当时来说做得 非常漂亮；再有就是m i c r o s o f t 的c 0 m 系列，从最初的c 叫发展成现在的d c o m ， 形成了m i c r o s o f t 一套分布式对象的计算平台；而s u n 公司的j a v a 平台，在其 最早推出的时候，只提供了远程的方法调用，在当时并不能被称为分布式对象计 算，只是属于网络计算里的一种，接着推出的j a v a b e a n ，也还不足以和上述两 大流派抗衡，而其目前的版本叫j 2 e e ，推出了e j b ，除了语言外还有组件的标准 以及组件之间协同工作通讯的框架。于是，也就形成了目前的三大流派。 应该说，这三者之中，c o b r a 标准是做的最漂亮的。c o b r a 标准主要分为3 个层次：对象请求代理、公共对象服务和公共设施。最底层是对象请求代理o r b ， 规定了分布对象的定义( 接口) 和语言映射，实现对象问的通讯和互操作，是分 布对象系统中的“软总线”；在o r b 之上定义了很多公共服务，可以提供诸如并 发服务、名字服务、事务( 交易) 服务、安全服务等各种各样的服务；最上层的公 共设施则定义了组件框架，提供可直接为业务对象使用的服务，规定业务对象有 效协作所需的协定规则。总之，c 0 r b a 的特点是大而全，互操作性和开放性非常 好。目前c o r b a 的最新版本是2 3 。c o r b a3 o 也已基本完成，增加了有关i n t e r n e t 集成和q o s 控制等内容。c o 船a 的缺点是庞大而复杂，并且技术和标准的更新相 对较慢，c o b r a 规范从1 o 升级到2 0 所花的时间非常短，而再往上的版本的发 布就相对十分缓慢了。 相比之下，j a v a 标准的制订就快得多，j a v a 是s u n 公司自己定的，演变得 很快。j a v a 的优势是纯语言的，跨平台性非常好。j a v a 分布对象技术通常指远 程方法调用( 跚i ) 和企业级j a v a b e a n ( e j b ) 。蹦i 提供了一个j a v a 对象远程 调用另一j a v a 对象的方法的能力，与传统r p c 类似，只能支持初级的分布对象 互操作。s u n 公司于是基于蹦i ，提出了e j b 。基于j a v a 服务器端组件模型，e j b 框架提供了像远程访问、安全、交易、持久和生命期管理等多种支持分布对象计 算的服务。目前，j a v a 技术和c 0 r b a 技术有融合的趋势。 中南大学硕士学位论文 李登：分布式系统负载均衡策略研究 c o m 技术是m i c r o s o f t 独家做的，是在w i n d o w s3 1 中最初为支持复合文 档而使用o l e 技术上发展而来，经历了o l e2 c 0 m 、a c t i v e x 、d c o m 和c o m 十等几 个阶段，目前c 0 m + 把消息通讯模块m s m q 和解决关键业务的交易模块m t s 都加进 去了，是分布对象计算的一个比较完整的平台。m i c r o s o f t 的c o m 平台效率比较 高，同时它有一系列相应的开发工具支持，应用开发相对简单。但它有一个致命 的弱点就是c 伽的跨平台性较差，如何实现与第三方厂商的互操作性始终是它的 一大问题。从分布对象技术发展的角度来看，大多数人认为c o m 竞争不过c 0 b r a 。 目前我们经常谈到的分布式对象技术主要就是这3 种，涉及到它的模型、规 范、标准和实现。3 种分布对象技术的详细比较可参见附表。 附表3 种分布对象技术的比较 集成性：集成性主要反映在基础平台对应用程序互操作能力的支持上。它要 求分布在不同机器平台和操作系统上、采用不同的语言或者开发工具生成的各类 商业应用必须能集成在一起，构成一个统一的企业计算框架。这一集成框架必须 建立在网络的基础之上，- 并且具各对于遗留应用的集成能力； 可用性：要求所采用的软件构件技术必须是成熟的技术，相应的产品也必须 是成熟的产品，在至关重要的企业应用中能够稳定、安全、可靠地运行。另外， 由于数据库在企业计算中扮演着重要角色，软件构件技术应能与数据库技术紧密 集成： 可扩展性：集成框架必须是可扩展的，能够协调不同的设计模式和实现策 略，可以根据企业计算的需求进行裁剪，并能迅速反应市场的变化和技术的发展 趋势。通过保证当前应用的可重用性，最大程度地保护企业的投资。 中南大学硕士学位论文李登：分布式系统负载均衡策略研究 1 2 负载均衡概述 1 2 1 负载均衡产生原因及定义 对于一个分布式计算机系统，由于任务到达的随机性，以及各处理结点处理 能力上的差异，当系统运行一段时间后，某些结点分配的任务还很多( 称之为超 载) ，而另一些结点却是空闲的( 称之为轻载) 。一方面，使超载结点上的任务尽 可能快地完成是当务之急；另一方面，使某些结点空闲是一种浪费。如何避免这 种空闲与忙等待并存的情况，从而有效地提高系统的资源利用率，减少任务地平 均响应时间，这成为了负载均衡产生的原因。 负载均衡是这样一种方法，他设法对依分配给各结点的任务进行重新调度， 并通过进程迁移( 又称为任务迁移) ，是各结点负载大致相等。 负载均衡概念应和负载共享概念进行区别，两者都属于负载分配技术，其主 要目标在于结点机间分派负载，均衡各结点负载，进而实现并行计算，以减小任 务响应时间。 负载共享属于比较低层次地负载分配技术。它可以使用户能够用本地所缺少 的系统资源( c p u 、内存、功0 设备、软件等) ，把超载或低性能结点上的负载加 载到轻载或高性能结点上执行，使用户仿佛有一台高性能计算机。负载共享应具 有访问透明性、位置透明性、结果透明性、故障透明性，且不大影响远程结点上 原有的操作，但它一般不支持任务的动态迁移。 负载均衡是比负载共享更高一层的负载分配策略。它试图均衡所有结点上的 负载，以使得所有结点上的负载基本相等，这种相等并非简单的任务数目相等， 而是依据这些异构结点的性能分派的加权相等，为此需要根据系统负载的变化进 行任务的动态迁移，同时，负载均衡支持并行应用，它选取一些结点机作为并行 处理单元，来构造一台虚拟的并行机，并给它们分配一定的任务以实现并行计算。 因而，负载均衡系统可以作为传统的向量机和并行机的一种代替，给那些没有并 行机的用户提供一个研究并行机制和应用的环境。 1 2 2 负载均衡的分类 负载均衡有许多的分类方法，但是从整体上说可以分为静态负载均衡和动态 负载均衡两大类。另外，对于1 0 a db a l a n c i n g 的翻译法可以译为负载均衡，也 可译为负载平衡，在国内的刊物上两种用法都有，所以本文多这两种翻译法不加 区别。 静态负载均衡又称为状态无关均衡，就是根据以往的经验或系统本身信息的 收集，把外来的任务分配给各个结点，或对某些结点上的任务进行重新分配。例 如，随机平衡，把第i 个任务分配给第i dn 个结点( n 为系统中的结点总数) ； 概率均衡，按照概率p 。( 由任务的平均到达速率和结点的运行速率确定) 把任务 分配给第i 个结点。常用的静态负载均衡法，还有图论法，枚举搜索法，排队法， 启发法等。静态负载均衡方法的优点是实现简单，在一定的应用中有其优势，但 其效率取决于对系统本身以及交互的任务是否有充分的了解，如各任务的执行代 价和任务之间的通讯代价，处理机的性能以及硬件设置等。由于这些先验知识常 常是不可能得到的或不准确的，所以目前常用动态负载均衡方法。 动态负载均衡又称为状态相关平衡，其决策取决于系统当前的状态，也就是 说，系统可以根据当前的负载分布情况，对各个节点上的负载进行动态的调整， 中南大学硕士学位论文李登：分布式系统负载均衡策略研究 使已分配给超载结点上的任务，通过通讯设备，迁移到轻载的结点上去，从而达 到提高系统的资源利用率，减小任务的平均响应时间的目的。 导致负载不均衡的原因主要是由于： ( 1 ) 某些算法的迭代大小不是固定的。但迭代的大小在编译时却可以被求 得： ( 2 ) 某些算法的迭代大小不是固定的，并且迭代的大小依赖于被处理的数 据，在编译时无法求得； ( 3 ) 即使迭代大小是固定的，也会有许多不定因素导致计算速度的差异。 考察这三个原因，对第一种情况可在编译时估计各迭代的工作量，按照处理 结点的处理能力分布迭代，这就是静态负载均衡的方法。对第二、三种情况来说， 必须采用动态负载均衡的手段，在运行过程中根据各个处理结点完成任务的情 况，动态地迁移任务。实现动态负载平衡。 1 3 本课题主要研究内容 负载均衡问题是一个经典的优化组合难题之一，其难度与h 锄i l t o n u 题相 当，是一个n p 完全问题。人们对静态负载均衡和动态负载均衡都进行了深入的 研究，人们通过对静态任务划分“1 的研究，间接的实现了静态负载平衡。而对于 动态负载平衡，h u i 等人嘲在理论方面提出了一个水动力学模型来抽象的描述负 载平衡。c h e n 。1 给出了一个通用的模型综合了发送者驱动和接收者驱动这两种方 法的优点。z a k i 等人“研究了分布、集中、全局和局部的负载平衡方法，并对这 几种策略进行组合，通过试验总结了在不同的情况下哪种策略的效果最好。但是 尽管前人做了这么多研究，但是真正能令人满意的实现系统并不多，主要原因在 实现上存在以下问题： ( 1 ) 要在分布式系统中有效地实现负载平衡，往往必须对系统的负载情况 进行评价。然而，这是一个很复杂的问题。因为与一台机器的负载情况直接相关 的因素往往是多方面的，例如c p u 队列的长度( 常用进程数目表示) ；可用资源 ( 如内存、c p u 等) 的情况；上下文切换的速率；系统调用的速率：交付任务 的具体要求( 如通讯代价、执行代价以及资源的请求情况) 等。某些信息是得不 到的或不准确的( 如在任务没有真正运行以前，就不可能知道其通讯代价、执行 代价) 。至目前为止，负载评价问题还没有得到完满的解决。 ( 2 ) 要实现分布式系统的负载平衡，总要进行某些附加处理( 如系统内各 结点负载信息的收藏、存储、决策以及任务迁移) ，导致一定的额外开销，如果 处理不当，系统的性能不但得不到改善，而且可能降低。另外，负载均衡常常出 现的一个问题是，迁移的任务，在各结点间被不断迁移而得不到执行，这种现象 称为任务迁移的抖动问题，也有人称之为颠簸问题。 ( 3 ) 各结点之间通过网络相连，大的通讯延迟，很可能使迁移到其它结点 执行的任务的响应时间，比本地执行的时问还要长。结点之间的信息传输，总有 一定的延迟时间，这就使得任务的响应时间变为迁出时间，在远程结点的逗留时 间，以及结果的返回时间之和了。另外，通讯的延迟。导致所记录的其他结点的 有关信息与真实的信息不同，也就是说，结点使用过时信息进行决策，因而使系 统的性能降低。 ( 4 ) 系统各结点的硬件( 如处理机结构，指令集等) 或软件配置( 如操作 系统等) 可能不同。 中南大学硕士学位论文 李登：分布式系统负载均衡策略研究 ( 5 ) 负载平衡的性能，受网络拓扑结构和系统结点数目的影响，至目前为 止，还没出现与网络拓扑结构、机器数目完全无关的通用算法。 一个好的负载平衡算法，应该尽可能地满足如下的几条要求： ( 1 ) 有效性：就是说，算法的运行提高了系统的效率( 如降低了任务平均 响应时间) 。为提高算法的有效性，要求系统用于负载平衡的附加代价应尽可能 小，并改善通讯设备的性能。 ( 2 ) 稳定性：就是系统正常工作的能力。特别是当系统内大多数结点处于 超载状况时，算法的运行提高了系统的性能而不是使系统超载地情况进一步恶 化。为了提高系统负载平衡的稳定性，要求解决任务迁移的抖动问题。 ( 3 ) 可靠性：一个结点的崩溃，并不影响其它正常结点的工作。 ( 4 ) 用户透明性：用户不必知道交付的任务具体在哪台机器上执行，对用 户来说，任务的迁移及远程执行都是透明的。 ( 5 ) 通用性：算法应适用于各种不同类型的任务，且受网络拓扑结构、机 器数目的影响应尽可能小。 本文的目的就是要尽可能地解决负载平衡中存在的问题，尽力的满足一个好 的算法应具各地要求，本文的研究内容采用先进地分布式对象技术”，结合具备 极大普适性地负载均衡次优策略“”。，较好的实现了要求。 1 0 中南大学硕士学位论文 李登：分布式系统负载均衡策略研究 第二章分布式系统 2 1 分布式系统发展的推动因素 计算机技术的发展可以通过使用计算机的不同方式来描述。在5 0 年代，计 算机是串行处理机，一次运行一个作业直至完成。这些处理机通过一个操作员从 控制台操纵，而对于普通用户则是不可访问的。在6 0 年代，需求相似的作业作 为一个组以批处理的方式通过计算机运行以减少计算机的空闲时间。同一时期还 提出了其他一些技术，如利用缓冲、假脱机和多道程序等的脱机处理。7 0 年代 产生了分时系统，不仅作为提高计算机利用率的手段，也是用户离计算机更近了。 分时是迈向分布式系统的第一步：用户可以在不同的地点共享并访问资源。8 0 年代是个人计算的1 0 年：人们有了他们自己专用的机器。由于基于微处理器的 系统所提供的出色的性能价格比和网络技术的稳步提高，9 0 年代是分布式系统 的1 0 年。 分布式系统可以有不同的物理组成：一组通过通信网络互联的个人计算机， 一系列不仅共享文件系统和数据库系统而且恭喜c p u 周期的工作站( 而且在大部 分情况下本地进程比远程进程有更高的优先级，其中一个进程就是一个运行中的 程序) ，一个处理机池( 其中终端不隶属于任何一个处理机，而且不论本地进程 还是远程进程，所有资源得以真正的共享) 。分布式系统是无缝的，也就是说网 络功能单元间的接口很大程度上对用户不可见。分布式计算的思想还被应用在数 据库系统嘲州”，文件系统“”“”5 ，操作系统啪“”“”和通用环境“。另一 种表示同样思想的说法是用户把系统看成一个虚拟的单处理机而不是不同处理 机的集合。像分布式系统发展的主要推动因素或者说分布式系统的主要优点在 于： 1 固有的分布式应用。分布式系统以一种很自然的方式开始存在，例如，在我 们的社会中，人群在地理上是分布式的并且分布式地共享信息。一方面，一 个分布式数据库系统中的信息产生于不同的分支机构( 子数据库) ，因此本 地访问可以很快进行；另一方面，系统也提供了全局视图来支持各种全局操 作。 2 性能成本。分布式系统的并行性减少了处理瓶颈，全方位提高了性能，也 就是说，分布式系统提供了更好的性能价格比。 3 资源共享。分布式系统能有效地支持不同地方的用户对信息和资源( 硬件和 软件) 的共享。 4 灵活性和可扩展性。分布式系统可以增量扩展，并能方便地修改或扩展系统 以适应变化的环境而无需中断其运行。 5 实用性和容错性。依靠存储单元和处理单元的多重性，分布式系统具有在系 统出现故障的情况下继续运行的潜力。 6 可伸缩性。分布式系统容易扩大规模以包括更多的资源( 硬件和软件) 。 l e l 枷“”讨论了分布式系统的目的与目标，并通过区分物理的分布和逻辑的 分布解释了其中一些与众不同的特征。 可扩展性、逐渐增加的实用性和更好的资源共享被认为是最重要的目标。目 前对分布式系统“”。”的兴趣主要有两种刺激因素：技术上的变化和用户的需求。 中南大学硕士学位论文李登：分布式系统负载均衡策略研究 技术上的变化有两方面：微电子技术的进步生产出快速而廉价的处理器：通信技 术的进步使得高效的计算机网络进入实用阶段。 计算机间长距离而且相对慢速的通信链路长期以来存在着，然而就是最近出 现了快速、廉价而且可靠的局域网( l a n ) 技术。这些局域网通常以l o 1 0 0m b p s ( 兆比特每秒) 的速率运行。与此同时，城域网( m a n ) 和广域网( w a n ) 也 交得越来越快和更加可靠。通常情况下，局域网跨越的地域直径不超过几公里， 城域网可覆盖的直径达几十公里，广域网可扩展到整个世界。最近异步传输模式 ( a tm ) 被认为是未来的新兴技术，它可以为局域网和广域网提供高达1 2 g 1 ) p s ( 千兆比特每秒) 的数据传输速率。在用户需求上，很多企业实际上都是相互合 作的，例如办事处、跨国公司、大学计算中心等等，它们都要求共享资源和信息。 2 2 基本的计算机组织结构 冯诺依曼型的计算机包括c p u 、存储部件和i o 。c p u 是计算机的大 脑。它通过读取、检查并逐条执行指令来执行存储在存储器中的程序。存储器单 元存储指令( 指令的序列叫做程序) 和数据。i 0 负责指令和数据进出处理器。 两个基本的计算机组织结构如下： 1 物理共享式存储器结构( 图2 1 a ) 有一个被所有c p u 共享的单一存储 器地址空间。这样一个系统叫做紧耦合系统。在一个物理共享式存储器 系统中， cp u 间的通信通过读和写共享存储器的操作进行。 2 物理分布式存储器结构( 图2 1 b ) 没有共享存储器，每个c p u 有自己 的本地存储器。c p u 和本地存储器对被称做处理单元( p e ) 或简称处理 机。这样一个系统有时被称做松耦合系统。在一个物理分布式存储器系 统中，处理机间的通信通过互连网络上的消息传递来进行，发送处理机 发送命令，接收处理机接收命令。 在图2 1 中，互连网络用于连接系统的不同部件并支持数据和指令的传送。 i o 部件没有画出来，但并不说明它不重要。然而，通信模型的选择无需和物理 系统联系在一起。我们可以区分硬件呈现的物理共享( 图2 1 ) 和编程模型呈现 的逻辑共享。图2 2 表示了4 种可能的共享组合。 图2 2 中标有“共享存储器”的方格代表了单处理机并行程序设计和基于共 享存储器模型的共享存储器多处理机程序设计。进程问必须同步以保证对共享数 据访问的一致。在并发执行的进程间提供同步的编程结构包括信号量、管程、临 界区和屏蔽。标有“消息传递”的方格代表了分布式存储器系统，其中通信是通 过消息的传递进行的。显式发送和接收消息的命令经常被用到。“模拟消息传递” 用来在一个物理共享存储器体系结构上提供逻辑分布式编程模型。消息通过共享 存储器的缓冲区传递。图2 - 2 中标有“分布式共享存储器( d s m ) ”的方格也被 叫做共享虚拟存储器或分布式存储器系统。这个模型通过使分布式存储器系统对 程序员看来就像共享存储器系统一样，使得在分布式存储器环境下编程尽可能如 在共享存储器系统那样容易。 中南大学硕士学位论文李登：分布式系统负载均衡策略研究 lcpucpucpu l ll f 互联网络 1 lj i 全局存储器 p e ( a ) 物理共享式存储器结构 物理共享式 物理分布式 ( b ) 物理分布式存储器结构 图2 1 两种基本的计算机结构 逻辑共享式逻辑分布式 共享存储器模拟消息传递 分布式共享存储器消息传递 ( d s m ) 图2 2 物理和逻辑共享式份布式存储器的比较 2 3 定义分布式系统 2 3 1 几个常用的概念 当讨论分布式系统时，我们面临许多以下这些形容词所描述的不同类型：分 布式的、网络的、并行的、并发的和分散的。分布式处理是一个相对较新的领域， 所以还没有一致的定义。与顺序计算相比、并行的、并发的和分布式的计算包括 多个p e 间的集体协同动作。这些术语在范围上相互覆盖，有时也交换使用。在 中南大学硕士学位论文李登：分布式系统负载均衡策略研究 文献【2 1 】中，s e 池给出了每一个的定义来区分它们之间的不同含义： 1 “并行的”意味着从一个单一控制线程对数据集的锁步( 1 0 c b t e p ) 动作。 在并行计算机级别上，单指令多数据( s m m ) 计算机就是一个使用多 个数据处理单元在许多数据项上同时进行相同或相似操作的例子。 2 “并发的”意味着某些动作可以以任意次序执行。例如，在更高级别上 和在多指令多数据( m m d ) 并行计算机上进行部分独立的操作。 3 “分布式的”意味着计算的成本或性能取决于数据和控制的通信。 如果一个系统的部件局限在一个地方，它就是集中式的：如果它的部件在不 同地方，部件之间要么不存在或仅存在有限的合作，要么存在紧密的合作，它就 是分散式的。当一个分散式系统不存在或仅存在有限的合作时，它被称做网络的； 否则它就被称做分布式的，表示在不同地方的部件之间存在紧密的合作。在给出 分布式系统具体定义的模型中，e f l s l o w ”建议分布式系统可以用硬件、控制、数 据这三个维度加以检验，同时还要求资源的分布必须对用户透明。 分布式系统= 分布式硬件+ 分布式控制+ 分布式数据 s c h r o e d e r ”1 给出了分布式系统特征的列表。如果一个系统具有以下所有特 征，它很可能就是一个分布式系统： 1 多处理单元( p e ) 2 互连硬件 3 处理单元的故障无关 4 共享状态 一些研究人员还认为计算机网络和并行计算机是分布式系统的一部分 2 4 “2 5 ”腑1 。图2 3 表示了计算机网络的分类。 计算机网络 局域网城域网广域网 环型网络总线型网络全球性网络非全球性网络 图2 3 计算机网络的分类 在非冯诺依曼的模型中，数据流模型是基于贪心求值( g r e e d ye v a l u 撕) 的，一个函数( 程序) 只要它的输入数据一就绪就被马上执行。缩减模型是基于 懒惰求值( 1 a 巧e v a l 删d o n ) 的，只有需要函数的结果时才执行求值。大部分并 行计算机是建立在冯诺依曼的模型上的。分布式系统环境的显著特点是多c p u 。 对于不同的分布式环境，c p u 的组织形式是各不相同的，迄今为止，多c p u 的 分类方法很多，其中影响最广、采用最多的是f l y 衄于1 9 7 2 年提出的f l y 衄方 1 4 中南大学硕士学位论文李登：分布式系统负载均衡策略研究 法。f 咖n 分类法基于指令流和数据流的多重性 1 单指令单数据( s i s d ) 。这是典型的单处理机体系结构。它可能包括并 行机制，如：流水线操作、重叠的c p u 和i ，o 操作。 2 单指令多数据( s m ) 。每个处理机同时在各自不同的数据集上执行相 同的指令。典型情况下，多个p e 处于一个公共控制单元的管理之下。 3 多指令单数据( m i s d ) 。这种体系结构包括多个处理机，每个分别被各 自的控制单元控制。 4 多指令多数据( m i m d ) 。多个处理机同时对不同的数据执行不同的指令。 大部分分布式系统的物理结构属于这种类型。 图2 4 表示了分布式系统环境多c p u 的分类： 并葡懒。 食 m m m ) 如d 啦d黼身馘 图2 _ 4 分缸甥鞠多两眵a u 自盼类 图2 3 和图2 4 表示的分类几乎包括了技术文献讨论过的所有重要的体系结 构类型。连接类型的区别包括不同的互连拓扑类型，这将在互连网络部分详细讨 论。 2 3 2 本文采用的分布式系统定义 本文中采用的是w u ”1 所做的分布式系统的定义： 一个分布式系统是一个对用户看起来像普通系统，然而运行在一系列自治处 理单元( pe ) 上的系统，每个pe 有各自的物理存储器空间并且信息传输延迟 不能忽略不计。在这些p e 间有紧密的合作。系统必须支持任意数量的进程和p e 的动态扩展。 图2 5 从物理的和逻辑的观点表示了这样一个系统。 中南大学硕士学位论文 李登：分布式系统负载均衡策略研究 a ) 物理观点的系统结构b ) 逻辑观点的系统结构 图2 5 基于不同观点的系统结构图 以下是分布式系统要求的属性： 1 任意数目的进程。每个进程也被称做一个逻辑资源。 2 任意数目的p e 。每个p e 也被称做一个物理资源。 3 通过消息传递的通信。这提供了比主从方式更合适的合作式消息传递方 式。 4 合作式进程。进程问以一种合作的方式交互，或者说多个进程用于解决 一个共同的应用而不是几个独立的应用。 5 通信延迟。两个pe 间的通信延迟不可忽略。 6 资源故障独立。没有任何单个逻辑或物理的资源故障会导致整个系统的 瘫痪。 7 故障化解( 铲a c e f h ld e 孕a d a l i o n ) 。系统必须提供在资源故障的情况下重 新配置系统拓扑和资源分配的手段。 于以上定义，计算机网络( 局域网、城域网和广域网) 不被认为是分布式系 统。这是因为不同地点( 或站点) 的进程没有协同工作。一个物理共享存储器多 处理机不是分布式系统，因为它没有故障独立性。分布式共享存储器( d s m ) 是一个逻辑共享存储器系统，但它具有资源故障独立性并支持故障化解。d s m 系统一般被当做特殊的分布式系统。1 趾e n b a 啪嘲说明了计算机网络、分布式系 统和多处理机三种不同系统的几个主要特征，这些特征包括对虚拟单处理机的支 持、操作系统拷贝的类型和数目、运行队列的数目以及特别是文件共享的语义。 一般来说，网络系统不支持虚拟单处理机，而分布式系统和多处理机系统都支持。 网络系统支持多操作系统而分布式和多处理机操作系统都只使用一种操作系统。 区别在于多处理机系统使用操作系统的个拷贝而分布式系统使用同一操作系 统的多个拷贝。分布式和网络系统都有多个运行队列而多处理机系统只有一个。 通常，文件共享在多处理机和分布式系统中都被明确定义。 2 4 互连网络 分布式控制算法可以分为网络无关的和网络相关的。网络无关的算法是基于 通用目的的，但对特定的网络可能效率不高。网络相关的算法是为特定网络设计 的。这些算法通常有效地利用了特定网络的拓扑属性。 中南大学硕士学位论文李登：分布式系统负载均衡策略研究 一个互连网络的拓扑可以是动态的或静态的。静态网络是由固定的点到点直 接连接组成的。动态网络利用交换机实现动态配置来满足