负载均衡的原理与算法介绍（转）

服务器负载均衡算法有很多（持续性的和非持续性的），包括轮循算法、最少连接算法、响应时间算法、散列算法、最少连接失误算法，链路带宽算法等等。此外实际服务器(Real Server)可以被分配不同的加权值来调整被分配的流量。比如性能高的大型服务器可配置较大的加权值，而为性能较低的小型服务器设置较小的加权值。为了避免服务器因过载而崩溃，可为实际服务器指定最大连接阈值来避免该服务器过载。任何服务器可被指定为另一台服务器的备份服务器或溢出服务器，从而进一步保证了应用可用性。

非持续性算法（Non-Persistent）：

一个客户端的不同的请求可能被分配到一个实际服务组中的不同的实服务器上进行处理。主要有轮循算法、最少连接算法、响应速度算法等。

－轮循算法（Round Robin）：

说明：

每一次来自网络的请求轮流分配给内部中的每台服务器，从1至N然后重新开始。

举例：

此种均衡算法适合于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况；

－最少连接算法（Least Connection）：

说明：

客户端的每一次请求服务在服务器停留的时间都可能会有较大的差异，随着工作时间的加长，如果采用简单的轮循或随机均衡算法，每一台服务器上的连接进程可能会产生极大的不同，这样的结果并不会达到真正的负载均衡。最少连接数均衡算法对内部中有负载的每一台服务器都有一个数据记录，记录的内容是当前该服务器正在处理的连接数量，当有新的服务连接请求时，将把当前请求分配给连接数最少的服务器，使均衡更加符合实际情况，负载更加均衡。

举例：此种均衡算法适合长时间处理的请求服务。

－响应速度算法（Response Time）：

说明：

负载均衡设备对内部各服务器发出一个探测请求（例如Ping），然后根据内部中各服务器对探测请求的最快响应时间来决定哪一台服务器来响应客户端的服务请求。

举例:

此种均衡算法能较好地反映服务器的当前运行状态，但最快响应时间仅仅指的是负载均衡设备与服务器间的最快响应时间，而不是客户端与服务器间的最快响应时间。

持续性算法（Persistent）：

从一个特定的客户端发出的请求都被分配到一个实服务组中的同一个实服务器上进行处理。主要包括：

A．基于IP的算法

－Persistent IP (pi)：基于用户IP地址来选择服务器。

－Hash IP (hi) ：基于用户IP地址的HASH值，来选择服务器

－Consistent Hash IP (chi)：

B．基于报头/请求的算法

－Hash Header (hh)：基于用户请求报中HTTP报头来选择服务器；

－Persistent Hostname (ph) ：基于用户请求报中HTTP报头的Hostname的HASH值，来选择服务器；

－Persistent URL (pu)：基于对URI Tag 和值的静态对应关系来选择服务器。

－SSL Session ID (sslsid)：基于SSL会话ID来选择服务器。

C．基于Cookie的算法

－Persistent Cookie (pc) ： 选择服务器基于用户请求包用Cookie Name / Value 的静态对应关系；

－Hash Cookie (hc) ：选择服务器基于用户请求包用Cookie Name / Value 的Hash 值对应关系；

－Insert Cookie (ic) ：选择服务器基于负载均衡器 向服务器响应包中插入Cookie；

－Re-write Cookie (rc)：选择服务器基于负载均衡器向服务器响应包中重写Cookie值。

（必须为重写指定Cookie值的偏移量）

负载均衡的基本算法

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

1 轮转法：

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

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

2 散列法

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

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

3 最少连接法

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

4 最低缺失法

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

5 最快响应法

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

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

6 加权法

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