网络负载均衡算法

基本的网络负载均衡算法

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

负载均衡算法1 轮转法

轮转算法是所有调度算法中最简单也最容易实现的一种方法?在一个任务队列里,队列的每个成员(节点)都具有相同的地位,轮转法简单的在这组成员中顺序轮转选择?在负载均衡环境中,均衡器将新的请求轮流发给节点队列中的下一节点,如此连续?周而复始,每个集群的节点都在相等的地位下被轮流选择?这个算法在DNS域名轮询中被广泛使用?

轮转法的活动是可预知的,每个节点被选择的机会是1/N,因此很容易计算出节点的负载分布?轮转法典型的适用于集群中所有节点的处理能力和性能均相同的情况,在实际应用中,一般将他与其他简单方法联合使用时比较有效?

负载均衡算法2 散列法

散列法也叫哈希法(HASH),通过单射不可逆的HASH函数,按照某种规则将网络请求发往集群节点?哈希法在其他几类均衡算法不是很有效时会显示出特别的威力?例如,在前面提到的UDP会话的情况下,由于轮转法和其他几类基于连接信息的算法,无法识别出会话的起止标记,会引起应用混乱?

而采取基于数据包源地址的哈希映射可以在一定程度上解决这个问题:将具有相同源地址的数据包发给同一服务器节点,这使得基于高层会话的事务可以以适当的方式运行?相对称的是,基于目的地址的哈希调度算法可以用在Web Cache集群中,指向同一个目标站点的访问请求都被负载均衡器发送到同一个Cache服务节点上,以避免页面缺失而带来的更新Cache问题?

负载均衡算法3 最少连接法

在最少连接法中,均衡器纪录目前所有活跃连接,把下一个新的请求发给当前含有最少连接数的节点?这种算法针对TCP连接进行,但由于不同应用对系统资源的消耗可能差异很大,而连接数无法反映出真实的应用负载,因此在使用重型Web服务器作为集群节点服务时(例如Apache服务器),该算法在均衡负载的效果上要打个折扣?为了减少这个不利的影响,可以对每个节点设置最大的连接数上限(通过阈值设定体现)?

负载均衡算法4 最低缺失法

在最低缺失法中,均衡器长期纪录到各节点的请求情况,把下个请求发给历史上处理请求最少的节点?与最少连接法不同的是,最低缺失记录过去的连接数而不是当前的连接数?

负载均衡算法5 最快响应法

均衡器记录自身到每一个集群节点的网络响应时间,并将下一个到达的连接请求分配给响应时间最短的节点,这种方法要求使用ICMP包或基于UDP包的专用技术来主动探测各节点?

在大多数基于LAN的集群中,最快响应算法工作的并不是很好,因为LAN中的ICMP包基本上都在10 ms内完成回应,体现不出节点之间的差异;如果在WAN上进行均衡的话,响应时间对于用户就近选择服务器而言还是具有现实意义的;而且集群的拓扑越分散,这种方法越能体现出效果来?这种方法是高级均衡基于拓扑结构重定向用到的主要方法?

负载均衡算法6 加权法

加权方法只能与其他方法合用,是他们的一个很好的补充?加权算法根据节点的优先级或当前的负载状况(即权值)来构成负载均衡的多优先级队列,队列中的每个等待处理的连接都具有相同处理等级,这样在同一个队列里可以按照前面的轮转法或者最少连接法进行均衡,而队列之间按照优先级的先后顺序进行均衡处理?在这里权值是基于各节点能力的一个估计值?

---------------------------------------------------------------------------------------------------------------------

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

1.1负载平衡算法的需求

如下所示，我们认为一个好的负载平衡算法应该满足下列需求：

l        最小化客户请求的派发时间，使客户请求能够迅速地被派发给相应的服务副本，而不会因为低效的副本选择导致延迟；

l        最小化客户请求响应时间和最大化系统的吞吐量，使系统能够获得最高的性能和最大的资源利用率，最小化资源的空闲时间；

l        客户请求的响应时间具有可预期性；

l        保证副本间负载分配的平衡，从而降低发生过载的可能性，确保服务的可用性和系统的可靠性，同时能够在一定程度上抵御负载峰值的冲击；

l        具有好的可扩展性，不依赖于某种特定的资源或结构，也不对系统中结点或副本的数目做出任何假设；

l        最小化系统的通信开销。

1.2非自适应的负载平衡算法

当使用此类算法时，服务不要求从成员获得负载更新，每次客户请求时采用随机或轮转的方式选择成员，常见的非自适应负载平衡算法是随机（random）和轮转（round-robin）算法

随机算法依赖于相应的随机函数，在一个副本队列里，队列的每个成员（副本）都具有相同的地位，通过随机函数在这组成员中进行随机的选择。但随机算法在一定程度上具有盲目性，在某一时刻选中的恰好是重载结点，而其余轻载结点却处于空闲中，从而造成系统整体性能和吞吐率地下降。

轮转算法是所有调度算法中最简单也最容易实现的一种方法。在一个副本队列里，队列的每个成员（副本）都具有相同的地位，轮转算法简单的在这组成员中顺序轮转选择。在负载平衡环境中，均衡器将新的请求轮流发给副本队列中的下一副本，如此连续、周而复始，每个副本都在相等的地位下被轮流选择。轮转法的活动是可预知的，每个结点被选择的机会均等，因此很容易计算出结点的负载分布。轮转法比较适用于集群中所有结点的处理能力和性能均相同的情况，在实际应用中，一般将它与其他简单方法联合使用时比较有效。

随机算法和轮转算法虽然都隶属于非自适应的负载平衡算法，但因为随机算法副本选择的盲目性，虽然各副本被选中的总体概率相等，但不能避免选择的局部聚集性，因而在性能上逊色于轮转算法。

随机和轮转算法算法实现简单，不需要使用成员的负载信息，开销较小，但缺点是只能在某些特定条件下恰当地平衡负载：

l        专用主机

l        同类主机

l        客户产生同样的负载，连接同样长的时间或客户连接的时间很短

3.1.3自适应的负载平衡算法

使用此类算法时，负载平衡器通过感知副本的负载变化情况提高负载平衡的效果。负载平衡器周期性地收集各成员的负载信息，利用这些负载信息决定选择哪一个成员对客户的请求进行服务。自适应的策略适合大量的请求产生不同的负载又无法实现预测的情况，也可以实现负载重平衡（即在某个成员过载的情况下，将客户请求重新绑定到一个负载较轻的成员上。常见的自适应负载平衡算法包括最小负载算法和平均负载算法最小负载（Least Load）算法根据副本负载的大小进行任务的分配，负载较轻的副本将处理更多的任务请求。最小负载算法的基本原理可描述为：假设有一组副本 ， 表示副本 的负载，当副本初次投入系统中使用时，副本的负载值均为0。副本的负载根据负载度量方式的不同有不同的定义方式，如CPU资源，内存资源，当前进程数，响应时间等信息都可以作为负载计算的因子。对于不同类型的系统应用，各个参数的重要程度也有所不同。如典型的Web应用环境下，可用内存资源和响应时间就非常重要；如果用户以长的数据库事务为主，则CPU使用率和可用内存就相对重要一些。负载平衡器的动态监测程序周期性地运行，查询各副本负载参数，并计算出副本的动态负载值 。根据副本动态负载值的大小，选出负载值最小的副本响应客户端请求。有的最小负载算法还引入了阀值机制，如果副本的负载高于设定的阀值，则说明系统开始处于重载状况，负载平衡器将会减少对该副本分配的任务。在实际使用中，若发现所有副本的权值都高于设定的阀值，则说明当前集群处于过载状态，这时需要加入新的副本到集群中来处理部分负载。

平均负载（Min-dispersion）算法的目标是确保负载差异在一个设定的范围内，从而确保每个副本之间的负载的差异能够最小化。在这种按需自适应策略中使用了下面的步骤：

1.         每一次发生了一个负载平衡决策，一个给定对象组之间的所有副本之间的平均负载将进行更新。

2.         将每一个副本上的即时负载和平均负载进行比较。

3.         如果平均负载和即时负载之间的差异大于设定的差异值，负载平衡器将尝试降低差异使之小于设定值。

要注意的是，通过本算法达到平衡的副本集合并不需要均具有相同的负载，但经过一定时间，副本之间的负载差异将变得最小，从而使整个系统趋向平衡。