负载均衡算法

 

负载均衡算法

 

据目前的知识水平，并行可以分为数据并行与任务并行。
数据并行是将数据分发，按块或者不同的流在每个进程或者每个线程中进行处理，
这种并行对数据的独立性要求比较明显。任务并行则是将一个任务分为可以同时
进行的几个子任务，进行处理。
让人头疼的是如何在不同的机器或者核中使其任务平均。这就引入了负载均衡相关的算法。
负载均衡算法主要分为两种，持续性和非持续性的负载均衡。
持续性是指特定客户端发出的请求将由同一服务器服务。
非持续性相比于持续性的区别是客户端发出的请求由不用的服务器提供服务。

 

1. 无需调用各个服务器信息的均衡方法
随机（Random）：
负载均衡方法随机的把负载分配到各个可用的服务器上，
通过随机数生成算法选取一个服务器，然后把连接发送给它。

散列法（Hash）：通过单射不可逆的HASH函数，按照某种规则将网络请求发往集群节点。

2. 需要各个服务器信息的均衡方法
 循环询（Round Robin）：
轮询算法按顺序把每个新的连接请求分配给下一个服务器，
最终把所有请求平分给所有的服务器。如果负载均衡的设备在处理速度、连接速度
和内存等方面是完全均等的，那么效果会更好。

加权轮询（Weighted Round Robin）：每个机器接受的连接数量是按权重比例分配的。
这是对普通lun询算法的改进，比如你可以设定：第三台机器的处理能力是第一台机器的两倍，
那么负载均衡器会把两倍的连接数量分配给第3台机器。

 

动态轮询（Dynamic Round Robin）：类似于加权轮询，但是，权重值基于对各个服务器的
持续监控，并且不断更新。这是一个动态负载均衡算法，基于服务器的实时性能分析分配连接，
比如每个节点的当前连接数或者节点的最快响应时间等。

最快算法（Fastest）：最快算法基于所有服务器中的最快响应时间分配连接。
该算法在服务器跨不同网络的环境中特别有用。

 

最少连接（Least Connections）：系统把新连接分配给当前连接数目最少的服务器。
该算法在各个服务器运算能力基本相似的环境中非常有效。

观察算法（Observed）：
该算法同时利用最小连接算法和最快算法来实施负载均衡。
服务器根据当前的连接数和响应时间得到一个分数，分数较高代表性能较好，会得到
更多的连接。

 

预判算法（Predictive）：
该算法使用观察算法来计算分数，但是预判算法会分析分数的
变化趋势来判断某台服务器的性能正在改善还是降低。具有改善趋势的服务器会得到更多的连接。
该算法适用于大多数环境。

 

最少连接数慢启动时间(Least Connection Slow Start Time)：
对最少连接数和带权重的
最小连接数调度方法来说，当一个服务器刚加入线上环境时，可以为其配置一个时间段，
在这段时间内连接数是有限制的而且是缓慢增加的。这为服务器提供了一个‘过渡时间’
以保证这个服务器不会因为刚启动后因为分配的连接数过多而超载。

基于代理的自适应负载均衡(Agent Based Adaptive Balancing)：
负载主机包含一个自适用逻辑用来定时监测服务器状态和该服务器的权重。
对于非常强大的“基于代理的自适应负载均衡”方法来说，负载主机以这种方式来定时
检测所有服务器负载情况：每台服务器都必须提供一个包含文件，这个文件包含一个0~99
的数字用来标明改服务器的实际负载情况(0=空前，99=超载，101=失败，102=管理员禁用)，
而服务器通过http get方法来获取这个文件;同时对集群中服务器来说，以二进制文件形式
提供自身负载情况也是该服务器工作之一，然而，并没有限制服务器如何计算自身的负载
情况。根据服务器整体负载情况，有两种策略可以选择：在常规的操作中，调度算法通过
收集的服务器负载值和分配给该服务器的连接数的比例计算出一个权重比例。因此，如果
一个服务器负载过大，权重会通过系统透明的作重新调整。和加权轮循调度方法一样，不
正确的分配可以被记录下来使得可以有效的为不同服务器分配不同的权重。然而，在流量
非常低的环境下，服务器报上来的负载值将不能建立一个有代表性的样本;那么基于这些值
来分配负载的话将导致失控以及指令震荡。因此，在这种情况下更合理的做法是基于静态的
权重比来计算负载分配。当所有服务器的负载低于管理员定义的下限时，负载主机就会自动
切换为加权轮循方式来分配请求;如果负载大于管理员定义的下限，那么负载主机又会切换
回自适应方式。