浅析负载均衡的算法

本文共2900字，预计阅读时间8分

负载均衡的算法

负载均衡的算法很多，而且可以根据一些业务特性进行定制化开发，抛开细节上的一些差异，根据算法所期望能够达到目的，大体上可以分为以下几种负载均衡算法。

• 任务评分类：负载均衡系统将接收到的任务平均的分配每个服务并进行处理，这里的平等可以是绝对的平均，也可以是比例或者权重上的平均。
• 负载均衡类：负载均衡系统根据服务器的负载能力进行分配，这里的负载并不一定是通常意义上的的CPU负载，而是通过系统当前的压力，可以用CPU负载来衡量，也可以用连接数、IO使用率、网卡吞吐量等来衡量系统的压力。
• 性能最优：负载均衡系统根据服务器的响应时间来进行任务的分配，优先将新任务分配给响应时间最短（最快）的服务器。
• Hash类：负载均衡系统根据日任务中的某些关键字信息进行hash运算，将算出来的相同hash值得请求分发给同一台服务器。比如：目标地址hash、session id hash、原地址hash、用户id(userId) hash 等方式来计算hash值。

常用负载均衡算法

轮训

负载均衡系统接收到请求后，按照一定顺序将请求分发给服务器上。轮训是一种简单的负载均衡算法策略，不回去关注服务器状态。

优点：如果服务器都是正常的，那么轮训是最理想的，因为它会使得每个服务都得到相等量的请求，可以用"雨露均沾"来形容。

缺点：上面的有点事理想状态的，但是现实往往不是那样的，现实还是很骨感滴，线上系统往往出现各种各样的问题，比如：当有一台服务器挂了，轮训算法不会管服务器状态，就是会导致大量的请求到一台已经挂掉的服务器上，从而导致系统不可用，进而造成用户流失。另外一种常见的问题就是有的服务器响应快，有的响应慢（比如32核的服务器和16核的服务器），轮训算法也不关注相应快慢，所以会导致很多服务请求响应时间慢，简单的导致用户体验不好，由于响应时间慢甚至可能拖垮其他系统。

加权轮训

负载均衡系统根据服务器权重进行请求任务分派到对应的服务器上，这里的权重一般是根据系统硬件配置进行静态配置的，采用动态的方式计算会更加适合业务，但是复杂度相比简单的轮训就高很多。

加权轮训是轮训的一种特殊方式，主要目的是解决服务器处理能力的差异问题，比如：集群中有的服务器是32核，有的老系统却是16核，那么理论上我们可以对其进行权重配置值，即就是32核服务器的处理能力是16核的两倍，负载均衡算范权重比例调整为2:1，让更多的请求分发给32核的服务器。

加权轮训解决了轮训算法中误服根据服务器的配置的差异任务进行更好的分配的问题，其实还是会存在无法根据服务器的状态差异性进行请求人物分配的问题。

负载最低优先

敷在系统将请求分配给当前负载最低的服务器，这里的负载根据不同请求类型和业务处理场景，可以用不同的指标来衡量。比如以下几个场景，

• LVS这种4层网络负载均衡设备，可以以连接数来判断服务器的状态，服务器连接数量越大，表明服务器压力就越大。
• Nginx这种7层网络负载均衡系统，可以以HTTP请求书量判断服务器的状态（Nginx内置的负载均衡算范不支持这种方式，需要自行进行扩展）。
• 如果我们是自己研发负载均衡系统，可以根据业务特点来选择衡量系统压力的指标。如果CPU是密集型，可以以CPU负载来衡量系统的压力；如果是IO密集型，则可以以IO负载来衡量系统压力。

复杂你最低优先算法解决了轮训算法中无法感知服务器状态的问题，但是由此带来的代价是复杂度增加很多，比如：

• 最少链接数优先的算法要求敷在系统统计每个服务器当前简历的链接，其应用场景仅限于负载均衡接收的任何请求都会转发给服务器进行处理，否则如果负载均衡系统和服务之间是固定的连接池方式，就不适合采取这种算法。LVS可以采取这种算法进行负载均衡，而一个通过连接池的方式链接数据库Mysql集群的负载均衡系统就不适合采取这种算法进行负载均衡了。
• CPU负载均衡最低优先的算法要求负载均衡系统以某种方式收集每个服务器的CPU的具体负载情况，同时要确定是以一分钟的负载标准，还是以10分钟、15分钟的负载标准，不存在1分钟肯定比15分钟的好或差。不同业务最优的时间间隔也是不一样的，时间间隔太短容易造成频繁波动，时间太长可能造成峰值来临时响应缓慢。

负载最低优先的算法基板上能够很完美解决了轮训算法的缺点，也因为采用负载最低优先算法后，负载均衡系统需要感知服务器当前运行状态，此时，同样造成代价上升很多。对于开发者来说也许轮训算法只要简短的代码就可以实现，然而负载最低优先算法需要大量的代码来实现。

负载最低优先看起来是解决了轮训中的缺点，然后由于其复杂度的提升，导致真正使用中比例还不如轮训或者轮训加权算法。

性能最优

负载最低优先算法是站在服务器的角度来进行请求分配的，而性能最优算法是站在客户端的角度进行分配的，优先将请求分配给处理速度快的服务器，通过这种方式达到了最快响应给客户端。

性能优先其实也负载最低优先有点类似，都是需要感知服务器的状态，与之不同的是性能最优是通过响应时间这个标准，在外部进行感应服务器状态而已，同样的实现复杂度也很高，主要体现在以下方面：

• 负载均衡系统需要收集每次请求的响应时间，如果在大量请求处理的场景下，这种收集再加上响应时间的统计本身也会消耗系统的性能。
• 为了减少这种统计上的消耗，可以采取采样的方式进行统计，即就是不用很完全的去统计所有服务器的所有请求时间，而是抽样统计部分任务的响应时间来估算整体请求所花的响应时间。采样统计虽然能减轻性能的消耗，但使得实现的复杂度增加了很多，因为要确定合适的采样率，采样率太低会导致数据的正确性，采样率高同样会造成性能的消耗，要找到一个合适的采样率的复杂度也是可想而知的。
• 无论全部统计，还是采样统计，都需要选择合适的周期，是30秒性能最优还是1分钟最优？目前是没有标准的周期，都是需要具体业务场景进行决策，是不是感觉到了其复杂性，尤其是线上系统需要不断的调试，然后找出相对合适的标准。

Hash类

负载均衡系统根据请求中没写关键字进行hash运算，得到的相同值得分发到同一台服务器上去，这样做的目的主要是为了满足特定的也无需求，比如：

• 源地址Hash：将来源于同一个IP地址的请求分配给同一个服务器进行处理，适合于存在事务、会话的业务。例如：当我们通过浏览器登录网上银行时，会生成一个会话信息，这个会话是临时的，关闭浏览器后就会失效。网上银行后台无须持久会话信息，只需要在某台服务器临时保留这个会话就可以了，但需要保证用户在会话存在期间，额米茨请求都能访问在同一个服务器，这种业务场景就是通过源地址hash来实现的。
• ID hash ：将某个ID表示的业务分配到同一台服务器上进行处理，比如：userId session id。上述的网上银行登录的例子，用session id hash可以实现同一个会话期间，用户每次都是访问同一台服务器上的目的。

Dubbo中的负载均衡算法

Dubbo提供了4种均衡策略，如：

• Random LoadBalance(随机算法)
• RoundRobin LoadBalance(权重轮循算法)
• LeastAction LoadBalance(最少活跃调用数算法)
• ConsistentHash LoadBalance(一致性Hash法) 缺省时为Random随机调用

Dubbo 还可以自定义负载均衡算法。

参考：《从零开始学架构》