《分布式网络环境下的负载平衡原理及算法.doc》由会员分享，可在线阅读，更多相关《分布式网络环境下的负载平衡原理及算法.doc（5页珍藏版）》请在金锄头文库上搜索。
1、来源： 在Internet/ Intranet 环境下一般采用Web服务器来集成共享的资源,但随着Web 服务器连接数目的不断增长,开始面临WWW服务器超载的问题。为了增大吞吐能力,提高反应速度,人们不得不升级或更换服务器。这里有两种选择,一种是采用昂贵的高性能主机或SMP 计算机,另一种则是把多台服务器用局域网络联结成一个集群,通过并行处理来扩展性能。比较这两种方案,后者的成本较低,并且具有较大的灵活性和较高的可靠性,目前有许多著名的WWW站点已经转向此类计算平台。我们称这种平台为并行WWW 服务器集群或工作站机群系统(Network of Workstations ,NOW) 。它的特点是
2、各节点独立运行自己的操作系统,灵活性高;节点处理能力强,资源为多用户共享。机群系统中,计算节点是面向多用户的,计算的核心机制在于如何进行任务的分配和调度 ,而任务的分配则取决于各计算节点负载信息的获取和处理技术。如何获取、使用收集本地节点的负载信息及任务调度就成为负载平衡系统的重要研究方向。1 动态负载平衡调度驱动策略在下面的讨论中,假定每个节点上的任务是动态产生的,每个节点的负载大小是动态变化的,因而不考虑静态负载平衡调度方法,只考虑动态负载平衡调度策略。一般说来,动态负载平衡调度可分为集中式调度和分布式调度两大类。前者是由一个调度服务器负责搜集系统负载信息,并由它来决定负载平衡调度方案,它
3、的主要优点在于实现比较简单;后者是根据局部范围内的一些负载信息来进行负载平衡操作,每台计算机定期把它的负载信息广播给其它计算机,去更新那些局部维护的负载向量,它的最大优点在于具有良好的可扩放性。限于篇幅,主要讨论集中式调度原理己算法2 集中式负载平衡调度策略2. 1 集中式负载平衡调度原理请求分配是并行WWW服务器集群中采用的一种典型技术。其主要原理,是由一台特殊的计算机(一般称为请求分配器) 集中接收所有的HTTP 请求,然后依据一定的原则把它们分配到集群中的各台服务器上去进行处理。分配的主要目的是使各台服务器的负载分布比较均衡,从而获得较高的整体吞吐能力和较快的反应速度。目前常用的请求分配
4、算法主要有转轮法、最少连接法和最快连接法3 种。第1 种算法实现简单,但从本质上讲没有考虑负载均衡问题。第2 种算法对各个服务器的性能不加区分,而且不考虑请求的强度(请求文件的长度) 。第3 种算法虽然考虑了服务器的性能,但没有考虑请求强度。这些局限性使这些算法无法真正做到负载的“均衡”分配,因而无法较好地发挥系统的并行处理能力。为了有效地提高请求分配算法的效率,并使算法能够适应异构服务器集群,应使请求分配器能够知道每一台服务器的处理能力,并且可对集中接收的每一个HTTP 请求的内容进行分析,同时应能比较准确地跟踪各个服务器的负载情况。服务器的处理能力可以事先通过实测获得,分析HTTP 请求只
5、需分析它的请求头部分,而负载跟踪则可以通过在请求分配器上记录各服务器的应答进度来实现。基于以上考虑,本文实现了一个异构WWW服务器集群,设计了一种综合考虑HTTP 请求内容和各个服务器性能以及当前的负载情况的请求分配算法LTI(Least Time Increment) ,目标是使各个请求的应答时间总和尽可能短。为此,文中把应答总时间的增量作为LTI 算法的优化对象。为了避免服务器在连接数接近阈值时性能急剧下降,还设计了一种请求延迟策略。2. 2 集中式负载平衡系统结构形式目前常见的并行WWW服务器集群主要有两种组成方式,一种是以Cisco 的Local Director 为代表的隔离式,采用
6、最少连接法或最快连接法进行请求分配;另一种则是以NCSA 的Scalable Web Server 为代表的非隔离式,采用转轮法进行请求分配。无论哪一种方式,都要求各台服务器上所有Web 信息的访问路径和内容要完全一样(这一点可以通过网络文件系统或专用的文件服务器来实现) 。二者的区别在于这些服务器是否直接连接在Internet 上,对用户可见。隔离式集群采用类似于Proxy 的技术,只有请求分配器具有一个虚拟的IP 地址,所有的请求都发向此IP 地址,由请求分配器分配到集群中的各台服务器上去处理,返回的结果也经由请求分配器传回给用户;非隔离式集群中的每一台服务器都有独立的IP 地址,请求分配
7、是通过动态DNS ,HTTP Redi2rect 等技术实现的,服务器对请求的应答不通过请求分配器,而是由各台服务器直接传回给用户。图1 是两种不同结构集群的组成示意图。 图1 WWW服务器集群的组成结构2. 3 性能评价参数和影响性能的因素目前,评价WWW服务器的性能主要采用吞吐率和平均应答延迟两个参数。吞吐率RPS 定义为平均每秒处理的请求个数,平均应答延迟MRD 定义为从建立网络连接到应答结束拆除连接之间的时间的平均值。所采用的测试集由若干个大小不一的请求按照一定的分布规律组成。所谓请求的大小,是指请求读取的文件的长度或请求执行的Script 等程序在独占处理机时的执行时间。HTTP 协
8、议是一种无状态协议,每个请求都由客户程序发起建立一个独立的网络连接,应答结束后由服务器拆除该连接。请求由请求头和请求体两部分组成,请求头是一种具有行结构的文本,请求体是一种称为MIME 格式的复合文本。请求头指明该请求的目的,如,向服务器请求读取文件、验证文件是否更新或执行服务器上的Scripts 程序等。不同的HTTP 请求对服务器产生的负载存在着很大的差异。RPS 和MRD 由服务器的处理能力决定。对于WWW服务器集群来说,MRD 还和请求分配策略有密切的联系。下面来分析这些联系。完成一个应答的时间主要由以下3 部分组成:1) 请求分配器与服务器建立网络连接所需的时间TC 。在Intran
9、et 企业网内部,这个时间一般可以忽略;2) 读取并传输文件的时间TF。这段时间取决于文件读取和传输的速度。如果在一段时间内,网络连接数N 保持不变,则在这段时间内,可以近似地认为与N 成反比,即 = / N 。这里,为只有一个连接时的文件读取和传输速度。称 为应答速度,为机器速度;3) 在服务器上执行Scripts 程序的时间TE。由于情况比较复杂,这段时间很难事先估计。为了简化问题,在下面的讨论中暂时不考虑TE。这里需要说明:当网络连接数N 超过某一阈值NMax (取决于服务器的性能, 对不同的服务器, 数值可能不同) 时, TC 会突然直线上升,同时会突然急剧下降。我们称这种状态为临界状
10、态, 称NMax 为此服务器的临界连接数。这种现象可以这样来理解:这些处理要消耗服务器的缓冲区资源,当缓冲区总数接近或超过系统内存限度时,系统开始大量使用“换存”,如果此时仍不断有请求到来,则势必产生一种恶性循环,于是系统效率急剧下降。所以,为了保证系统的RPS 和MRD ,应设法避免N 达到NMax。下面分析有一台服务器时的应答时间。设在某一时刻该服务器共有N 个网络连接在同时传输文件, 这些文件的剩余长度分别为L1 ,L2 , . . . , LN 。此时,一个新的HTTP 请求到达该服务器,请求的文件长度为L 。不妨设L1 . . . L K L L K+1 . . . LN , 采用连
11、续模型(传输文件的时间与文件的长度成正比, 与机器速度成反比) 可以计算由于L 的引入而产生的应答时间的增量:3 请求分配算法的实现为了实现算法,在请求分配器上设置几个表。第1 个称为FLT ,其中的内容为服务器上WWW 空间中所有文件的路径和长度。第2 个称为TST ,其中存放的是各个服务器的机器速度。第3 个称为RCT ,存放各个服务器正在应答的请求个数。设集群中共有M 个服务器,为每个服务器设置一个表CFT( i) ,1 i M , 用来存放此服务器当前正在应答的各个请求所传输文件的长度和剩余长度。请求分配算法LTI 采用多线程技术,算法主干部分由两个线程组成,一个用于跟踪各服务器的应答
12、进度,一个用于请求分配。1) 请求分配算法LTI线程1 :负载跟踪每隔一个固定的小时间段进行如下操作:根据TST 和RCT 计算各个服务器的应答速度 ;将所有CFT( i) 中各个文件的剩余长度域减少3,1 i M;如某文件的剩余长度0 ,则删除相应CFT ( i )的对应项,并更新RCT 中此服务器的当前请求个数。线程2 :请求分配如果有请求到达,从请求头中的URL 部分取出请求文件的路径,从FLT 中查得其请求文件的长度L ;对每个服务器i ,根据TST ,RCT和CFT( i) ,采用式(1) 的方法计算将L 引入该服务器所引起的应答总时间的增量i ,1 i M;设K = Min (i)
13、 ,1 i M ,分配请求L 到第K 个服务器,同时更新RCT 中此服务器当前请求个数,并在CFT( i) 中增加一项,其中文件长度域和剩余长度域均为L 。LTI算法把应答总时间的增量作为优化的对象,关于它的性能,有以下定理。定理:对于优化MRD 来说,LTI 算法是一个局部最优算法。证明:设一个测试集共有n 个请求,由式(1) 和MRD 的定义,有其中, TC ( i) 为各个请求的连接建立时间,按上文讨论为固定值;( i) 为各个请求在以前所有请求的基础上引起的应答总时间的增量。在LTI 算法中,分配新到达的每一个请求时,都使相应的( i) 取得了当前状态下可能的最小值,从局部意义上讲,该
14、算法是最优的。但当连接数N 接近或超过某一阈值NMax 时,服务器的性能会急剧下降。上述算法没有考虑这个问题,其结果是在负载很重时,应答时间将大大超过预计值,于是算法的准确性就得不到保证。解决这个问题可以有几种方法。第1 种方法是拒绝新连接,直到有服务器退出临界状态。第2 种方法是将新到达的请求分配到另外一台服务器上去。第3 种方法是将新到达的请求延迟,等到有服务器退出临界状态时再予以处理。上述第1 种方法因为用户很难接受,在实际中是不可行的,故不予考虑。对第2 种按照LTI 算法选出的服务器达到连接阈值时,其他服务器也基本上都接近临界状态,因此这种方法效果不明显。因此结合第2 和第3 种方法
15、,对LTI 算法进行如下改进。修改表RCT ,其中除了存放各个服务器正在应答的请求个数N 以外,还存放它们的临界连接数。增加队列DRQ ,存放因临界状态而延迟的请求及其请求文件的长度。一个服务器接近临界状态是指它的连接数N 接近但还未达到临界连接数NMax ,此时,服务器的性能还没有急剧下降。2) 请求分配算法LTI +线程1 :负载跟踪,与LTI 算法相同。线程2 :请求分配如果有请求到达,从请求头中取出请求文件的路径,从FLT中查得其请求文件的长度L 。如果此时所有服务器都已接近临界状态,则将这个请求放入延迟队列DRQ 的队尾,并填入其请求文件的长度;否则:对所有未接近临界状态的服务器i
16、, 根据TST ,RCT和CFT( i) ,采用(1) 式的方法计算将L 引入该服务器引起的应答总时间的增量i ,1 i M;设K = Min (i) ,1 i M ,分配请求L 到第K 个服务器,同时更新RCT 中此服务器当前请求个数,并在CFT( i) 中增加一项,其中文件长度域和未传长度域均为L 。线程3 :处理被延迟的请求如果延迟队列DRQ 非空,每隔时间检查是否有服务器退出临界状态。如果有,则进行如下操作:取出DRQ 队首的请求,设其请求文件的长度为L ;对所有未接近临界状态的服务器i ,根据TST ,RCT和CFT( i) ,采用式(1) 的方法计算将L 引入该服务器所引起的应答总时
