集群的可扩展性及其分布式体系结构(6)

网络负载平衡基本算法与进阶

 

级别： 初级

林凡 (), 研发部经理, 辰讯软件工作室

2002 年 4 月 29 日

本节主要介绍网络负载均衡的几类基本的算法，以及在这些算法基础上所构建的复杂的网载均衡体系。这些负载均衡体系都针对了实际应用中的某些特殊需要进行了优化处理，有着各自的适用面。

一般的平衡算法主要任务是选择一个集群节点，然后将新请求发给它。有些简单平衡方法可以独立使用，有些必须和其它简单或高级方法组合使用。平衡算法设计的好坏直接决定了集群在负载均衡上的表现，设计不好的算法，会导致集群的负载失衡。而一个好的负载均衡算法也并不是万能的，它一般只在某些特殊的应用环境下才能发挥最大效用。因此我们在考察负载均衡算法的同时，也要注意算法本身的适用面，并在采取集群部署的时候根据集群自身的特点进行综合考虑，把不同的算法和技术结合起来使用。

• 轮转法
  轮转算法是所有调度算法中最简单也最容易实现的一种方法。在一个抽象的任务队列里（常常在操作系统任务调度中见到），队列的每个成员（节点）都具有相同的地位，轮转法简单的在这"串"成员中线性轮转选择。
  在负载平衡环境中，均衡器将新的请求轮流发给节点表（节点队列）中的下一节点，如此连续、周而复始，每个集群的节点都在相等的地位下被轮流选择，是一种绝对的"平均主义"。这个算法在DNS域名轮询中被广泛使用。
  轮转法的活动是可预知的，每个节点被选择的机会是1/N，因此很容易计算出节点的负载分布。轮转法典型的适用于集群中所有节点的处理能力和性能均相同的情况，在实际应用中，一般将它与其他简单方法联合使用时比较有效。

  Cisco的LocalDirector是一种运行在局域网内，为私有网络提供集群支持的产品。LocalDirector有2个网络接口，一个对内一个对外，采用 NAT技术，整个系统对外只有一个IP地址，通过IP地址变换将HTTP请求分配到群集中不同的Web Server，这些Web服务器最好是培植相同的同构环境，并且必须保证每台节点上的信息一致。本质上，他是一个基于网络流量历史数据分析而后进行负载平衡的产品。在请求分配上实现了4种不同的基本负载均衡算法：最少连接法，最快响应法，轮转法和加权百分比，用户在配置时可以选择使用其中一种。此外，LocalDirector还支持动态改变群集规模的大小，即在不停机的情况下增加或减少服务器。 它具有很强的吞吐能力，自身延迟也小，因而能够支持较大规模的系统，并且可以通过级联进一步扩大系统的规模。它能够支持每秒240 Mbps 的吞吐量和每秒 20000 多个连接的性能，可以应付高速网络流量和突然出现高峰的访问情况。单个系统可以配置 64000 个虚拟和真实服务器，提供足够的域名和网络配置灵活性。

• 随机法
  首先需要明确的一点是，计算机系统生成的随机数永远是伪随机。随机法赋给各节点一个由伪随机算法产生的值，具有最小或最大随机数的节点最有优先权。随机法实际上相当于"无偏见"的给节点产生权值，每个机器都有可能获得最大的优先级，这也是一种"机会均等"的调度算法。因此和轮转法一样，需要在相同的节点环境中，这种算法才能运行得最好。
  随机法与轮转法不同在于，你无法精确的预制调度队列里的活动。因此使用随机法的调度算法原则上不需要设定调度队列，而是使用类似HASH表的结构来记录节点的连接情况。
• 散列法
  散列法也叫哈希法（HASH），通过单射不可逆的HASH函数，按照某种规则将网络请求发往集群节点。哈希法在其他几类平衡算法不是很有效时会显示出特别的威力。例如，在前面提到的UDP会话的情况下，由于轮转法和其他几类基于连接信息的算法，无法识别出会话的起止标记，会引起应用混乱。
  而采取基于数据包源地址的哈希映射可以在一定程度上解决这个问题：将具有相同源地址的数据包发给同一服务器节点，这使得基于高层会话的事务可以以适当的方式运行。
  相对称的是，基于目的地址的哈希调度算法可以用在Web Cache集群中，指向同一个目标站点的访问请求都被负载平衡器发送到同一个Cache服务节点上，以避免页面缺失而带来的更新Cache问题。
• 最少连接法
  在最少连接法中，平衡器纪录目前所有活跃连接，把下一个新的请求发给当前含有最少连接数的节点。这种算法针对TCP连接进行，但由于不同应用对系统资源的消耗可能差异很大，而连接数无法反映出真实的应用负载，因此在使用重型Web服务器作为集群节点服务时（例如Apache服务器），该算法在平衡负载的效果上要打个折扣。为了减少这个不利的影响，可以对每个节点设置最大的连接数上限（通过阈值设定体现）。
• 最低缺失法
  在最低缺失法中，平衡器长期纪录到各节点的请求情况，把下个请求发给历史上处理请求最少的节点。与最少连接法不同的是，最低缺失记录过去的连接数而不是当前的连接数。
• 最快响应法
  平衡器记录自身到每一个集群节点的网络响应时间，并将下一个到达的连接请求分配给响应时间最短的节点，这种方法要求使用ICMP包或基于UDP包的专用技术来主动探测各节点。
  在大多数基于LAN的集群中，最快响应算法工作的并不是很好，因为LAN中的ICMP包基本上都在10ms内完成回应，体现不出节点之间的差异；如果在WAN上进行平衡的话，响应时间对于用户就近选择服务器而言还是具有现实意义的；而且集群的拓扑越分散这种方法越能体现出效果来。这种方法是高级平衡基于拓扑结构重定向用到的主要方法。
• 加权法
  加权方法只能与其他方法合用，是它们的一个很好的补充。加权算法根据节点的优先级或当前的负载状况（"权值"）来构成负载平衡的多优先级队列，队列中的每个等待处理的连接都具有相同处理等级，这样在同一个队列里可以按照前面的轮转法或者最少连接法进行均衡，而队列之间按照优先级的先后顺序进行均衡处理。在这里权值是基于各节点能力的一个估计值。

回页首

前面描述的只是负载均衡的基本算法，在实际设计负载均衡集群时，需要将他们进行组合，针对特定的应用或者特定的系统进行优化，以提供更有用、更实际的网络负载平衡。考虑主要的优化面有：优化网络流量、节点负载公平分布、路由优化（拓扑优化）、响应时延最小化、管理或安全优化、特定应用性能优化等等。

多数复杂的负载均衡算法是几个优化方案的组合。在核心网络的负载均衡设备中，主要考虑流量优化、路由优化和响应延时；在一般的商务集群中，主要考虑响应延时和安全、管理方面的优化；如果是针对特定应用的负载均衡器（第七层交换），就要考虑特定应用的性能问题。下面是典型的网络负载均衡高级方法的例子：

• 基于源网络流量的平衡
  这种方法要求平衡器主动监视不同来源的流量，根据以往历史预测从一个网络源地址过来的流量大小，并进行负载分配。最简单的处理形式就是在查找表中保留有特定源地址的流量计数。分配可基于简单加权，根据节点的负载能力分配，（也就是说，预测新来的流量越高，被分配的节点权值应该越大，是一种"最优适应"的算法）。分配算法可以使用前面的任意一种简单算法，但与节点的当前负载情况无关，适用于节点的配置和处理能力比较接近的情况。
• 基于节点信息的平衡
  这是一种基于预测的系统，根据节点的"运行情况"（可用缓冲区、可用内存、CPU占空比等等）获取节点在网络流量处理、应用负载能力等方面的信息，借此判断节点将来（到下一次预测前）可用的性能，并根据性能的高低进行优先级的划分以提供基于权值（通过性能指标计算而来）的负载调度算法，它可以和最低缺失法、轮转法和最快响应法合用，但主要搭配的方法是最少连接法。
  • 基于节点流量
    在这种方法中，进入集群的访问请求是根据能够反映各节点流量程度的可用网络缓冲区大小来分配的，这与基于源网络流量的技术恰恰相反（它是基于源流量的历史数据）。为了获得每个节点的网络缓存信息，平衡器要在节点上先设一个软件代理来记录网络缓存状态，然后分配流量到拥有"最可用"缓存的结点上。这种方法受网络接口卡的影响比较大，低端的网络接口卡缺少大的缓冲区，同时存在内存通道访问技术上的不足，会引起节点频繁处于中断处理例程中，降低节点CPU的处理效率。而高端网卡不但具有独立处理内存数据的能力，而且还具有端口带宽聚合的功能，可以大大提高节点处理流量的绝对速度。
  • 基于节点负载
    这种方法将流量分配到处理器负载最小的节点上。平衡器在节点上维护一个反映当前负载状况的监视程序，定时从各个节点获取必要的信息。反映机器的CPU使用率或系统的负载是很主观的。在UNIX系统中，平均负载不是由硬盘或网络状态单方面决定，而是由系统的综合状况来反映的。这种方法要求节点运行在相似配置和相同的操作系统中；或者针对不同类型的操作系统采用不同的反映负载的代理软件。就目前的操作系统而言，Windows2000的性能监视软件可以比较精确的反映负载情况；而在类UNIX和Linux系统中，就需要针对各个参数设计出能够反映负载状况的采集程序了；而如何准确反映系统真实的负载情况并据此做出合理的预测，是集群技术领域里一直的热点和难点。

  英特尔网擎系列中的7190多址负载均衡器可用于远程负载均衡服务。这一设备针对拥有多个网站地址的企业进行专门设计，能够根据单个URL地址将通信路由到方便可用的站点，从而实现广域网范围的负载平衡。为了提高响应速度，7190采用 "快速响应模式"，使所有的站点都能对同一用户的访问请求作出响应，响应最快的站点将接受并完成这一访问任务，而不是在发生用户请求时计算"最快"的路由因而产生额外的延迟时间。管理员可以采用这种模式确保很短的服务器响应时间，也可以选择对用户满意度产生更大影响的其他算法。系统在后台收集多站点状态信息，如服务器响应时间、通信量、本地系统状态，从而使7190能够立即确定每个数据中心的状态，并将访问导向最佳站点。

• 基于拓扑结构的重定向
  这种方法对网络中存在多个集群，或者集群的节点分布在一个范围比较大的远程网络时很有效，它根据网络拓扑结构将流量重定向到离用户"最近"的集群节点或者集群分组上， 有两种方法测算用户与集群节点间的距离：跳计数法和网络延迟法。
  跳计数就是包到达目的地需要经过的路由器数。数值越大，距离越远；网络延迟，以毫秒为单位，是网络包在用户与集群平衡器之间通过的时间。Linux下的trace就是跟踪路由信息的一个很方便的工具。多数的路由信息是静态的，因而跳计数往往是稳定的，除非有多个路由可供选择；而网络延迟则随某时刻网络流量、路由器负载而相差很大。延迟有助于测量网速，因为它不仅考虑了路由器，还考虑了当前网络带宽。
  要想获得某一时刻集群中针对某个用户请求的"最佳"路由并进行拓扑重定向操作，需要均衡器收集所有集群节点或者分组的响应延迟并做出最短路径判定。典型使用一种叫做Ping三角法来动态地确定用户和集群之间的拓扑信息。
  可以看出，这是广域网模型中采用的最快响应法，这种方法有时根据节点参数使用动态加权，每次用户产生新的连接，也许分配给相同的节点。由于网络拓扑结构随连接而变化，所以这种分配也会变化，在这里平衡器维护了必要的节点可达性和用户响应时间的全局表。
• 基于策略的重定向
  这种方法是一套决定加权平衡规则的数学或函数集。规则集可简可繁，简单的可以用IP地址和用户帐号作为规则匹配的关键字；复杂些的可以借助有针对性的扩展分析程序进行语法分析或特制的ASIC（特定应用集成电路）进行处理。不过一般来说，规则集越简单，处理和负载平衡越快。策略需要人工配置，网络管理员可以改变策略，将高权值依次赋给优先项目。
  • 安全策略
    大多数的安全系统都是基于密钥加密技术进行可靠数据传输的。现有的安全Web服务使用HTTPS协议。当客户访问HTTPS服务时，会在服务和客户端之间先建立一个SSL连接，来交换对称公钥加密的证书并协商一个SSL Key，来加密以后的会话。在SSL Key的生命周期内，后续的所有HTTPS连接都使用这个SSL Key，所以同一客户的不同HTTPS连接也存在相关性。平衡器在工作的时候就需要能够识别这类安全会话，并根据其关键信息将请求分配到生产初始密钥的站点，以保证客户在使用上的一致性。
  • 带宽分配策略
    这种方法根据新来的流量的类型建立优先级，为高优先级的流量分配更多的带宽和节点，比如网络中管理控制信息和安全控制信息的优先级就要高于其他类型的数据。实质上这是QoS的实现，现在我们可以通过自己扩展的软件来弥补IPv4在这方面的不足。它一般使用最快响应和最少连接算法来决定最可用的节点。

  Cisco CSS系列交换机可以根据完整的URL、Cookie及资源可用性信息选择最佳的站点和服务器，提供高速智能Web内容交付；具有防火墙负载均衡功能,可为后台数据库和应用系统提供可伸缩的安全保护。透明Cache代理、反向Cache代理及智能Cache旁路功能可使Web高速缓存效率提高400%。Cisco CSS配备了Cisco WebNS软件，在分配Web站点资源和实现最佳电子商务等方面为企业提供完善的解决方案。

• 特定应用的重定向
  这种方法依赖于应用类型或用户试图访问的资源，由于在TCP/IP 协议体系中没有统一的独立会话层， 一些应用建立了自已的会话系统，因而平衡器厂商不得不在产品可能结构中加入对这些会话类型的支持。
  数据库和web负载平衡是最通用的特定应用的重定向。在数据库中，数据信息可能分散在多台节点上，当新的查询到来时，平衡器能够分解这个查询，在每个节点上获得部分数据后再合并成最终的应答返回给用户。
  静态的Web访问通常都是读取HTML文件，而每个Web页面内可能包含多个互相独立、类型不同的文件。比如，一个带有Frame（框架）的页面里，包含多个独立的HTML源文件和多个独立的Gif图片文件或者其他媒体文件。平衡器可以分解用户的请求URL，识别出存放在不同节点上的文件，将负载分散到多个服务器上。
  较复杂的情况是脚本访问。一些web 脚本需要按顺序在同样用户和服务器上执行。如果连续的脚本每次被分送到不同的节点上，就可能会由于多个副本在集群上传输而破坏脚本。一种解决方法是让所有节点访问后端的一个独立数据库，但这又产生了数据库瓶颈，妨碍了负载平衡。另一种较好的方法是记录用户与一个特定节点间的web会话，即使节点重载了，也要维持二者之间的流量，而不是重分配负载。

回页首

网络负载平衡系统有独立的平衡器来监视网络请求，并按某种规则将请求分配到本地或其他分布式网络的集群节点上。这里介绍了一些基本的用于构建平衡系统的算法，这些算法基本上都基于多任务的队列模型，并配合相关技术以解决TCP/IP集群节点相关的问题。这些方法尽管独自开发，但却有很多相似的形式和作用，几个方法可以组合产生更复杂的负载平衡，其中典型的internet域名轮转系统在过去的负载平衡中起着重要作用。TCP/IP协议体系中，主要在两层进行平衡：网络层和传输层，由于没有独立的会话层，产生了给予特定应用协议的平衡方法。现在最大热点是在本地或分布结构中构建web服务器负载平衡系统。

		林凡，现于厦门大学从事Linux相关的科研工作。于集群技术由很大的兴趣，希望能与志同道合的朋友一起交流。您可以通过电子邮件 和他联系。