今天我们讨论的是常见的负载均衡算法，小伙伴们如果有机会看到这篇博客，如果有什么建议欢迎评论和留言。

刚刚接触分布式或者集群的小伙伴可能会问负载均衡是个什么东东呢？

引用百度百科的解释就是

负载均衡建立在现有网络结构之上，它提供了一种廉价有效透明的方法扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性。
负载均衡（Load Balance）其意思就是分摊到多个操作单元上进行执行，例如Web服务器、FTP服务器、企业关键应用服务器和其它关键任务服务器等，从而共同完成工作任务。

负载均衡包括软件负载均衡和硬件负载均衡，作为一个程序猿，我们此处讨论的当然是软件负载均衡了。
不管什么负载均衡实现都是使用一些负载均衡算法来实现的，那么常见的负载均衡算法到底有什么呢？

常见的负载均衡算法包括：**随机、轮询、ip_hash、url_hash、最小响应时间。**比如常用的Nginx反向代理服务器也能实现负载均衡功能，其中常用的负载均衡就包括这几种算法。

随机

随机就是没有规律的，随便从所有的负载中选择一台，又分为完全随机和加权随机。

完全随机

首先我们想要负载均衡到一个集群中，那么肯定要知道这些集群的ip地址、端口号等等信息，这样才能发请求过去。那么集群中这么多机器，我们不可能将他们的信息都硬编码到程序中吧，另外也不可能每次增加机器或者机器信息改变（比如端口号、IP地址）都去修改我们的负载均衡算法吧，这个问题可以利用服务注册和服务发现来解决。具体的知识不在这里赘述了，可以自行度娘。

言归正传，完全随机是个啥呢？完全随机应该算是负载均衡算法中最简单的了，完全随机简单的实现可以将所有的ip信息都存到一个list或者数组中，我们每次去遍历这个数组或者list拿到ip地址信息就可以了。

但是这个算法有没有问题？对于每个服务器来说，他们的性能是不一样的，可能有的服务器性能好，有的服务器性能比较差，我们想将更多的请求负载到性能好的服务器怎么办呢？

带有权值的加权随机算法应运而生。

加权随机

加权随机，虽然还是采用的随机算法，但是为每台服务器设置了权重，权重大的服务器获得的概率大一些，权重小的服务器获得的概率小一些。

关于加权随机的算法，有两种实现方式：

一种是网上流传的，代码比较简单：构建一个服务器的List，如果A服务器的权重是2，那么往List里面add两次A服务器，如果B服务器的权重是7，那么我往List里面Add7次B服务器，以此类推，然后我再生成一个随机数，随机数的上限就是权重的总和，也就是List的Size。这样权重越大的，被选中的概率当然越高.

但是这样的话，如果我们的权值非常大呢？如果几千或者几万呢？我们要建一个几万容量的list吗？这显然白白占用了内存。

所以第二种方法效果更佳：
可以用两个数组或者map来存储ip信息和相应的权值。

• 如果A服务器的权重是2，B服务器的权重是7，C服务器的权重是1：
  如果我生成的随机数是1，那么落到A服务器，因为1<=2（A服务器的权重）

• 如果我生成的随机数是5，那么落到B服务器，因为5>2（A服务器的权重），5-2（A服务器的权重）=3，3<7（B服务器的权重）

• 如果我生成的随机数是10，那么落到C服务器，因为10>2（A服务器的权重），10-2（A服务器的权重）=8，8>7（B服务器的权重），8-7（B服务器的权重）=1，
  1<=1（C服务器的权重）

此处使用两个数组来实现，使用第一个数组存储ip信息，第二个数组在相同的索引处存储该服务器所占的权值。这样我们只需要遍历第二个数组，看看此时的随机值落到那个索引处，然后再去相同的索引查看对应的ip就可以了。

轮询

有了上边的随机负载均衡算法，那么类似的也有完全轮询和加权轮询，实现方法和随机一样。

但是如果使用和加权随机相同的算法实现加权轮询的话可能还有一点小瑕疵，试想一下上边的实现是我们的每个服务器的访问都是相邻的，什么意思呢？如果一个服务器的权值是10000，那么最近的10000次请求都会负载到这台服务器上，只有当10001个请求过来之后才会负载到下一台服务器。这样可能就导致有的服务器忙的不可开交，而此时有的服务器却优哉游哉闲得很：饱的撑死，饿的饿死。

那么如何解觉呢？可以使用平滑加权轮询算法。

平滑加权轮询算法

什么是平滑加权轮询算法呢？平滑加权是一个很神奇的算法，我们有必要先对这个算法进行讲解。

比如A服务器的权重是5，B服务器的权重是1，C服务器的权重是1。这个权重，我们称之为“固定权重”，既然这个叫“固定权重”，那么肯定还有叫“非固定权重的”，没错，“非固定权重”每次都会根据一定的规则变动。

• 第一次访问，ABC的“非固定权重”分别是 5 1 1（初始），因为5是其中最大的，5对应的就是A服务器，所以这次选到的服务器就是A，然后我们用当前被选中的服务器的权重-各个服务器的权重之和，也就是A服务器的权重-各个服务器的权重之和。也就是5-7=-2，没被选中的服务器的“非固定权重”不做变化，现在三台服务器的“非固定权重”分别是-2 1 1。

• 第二次访问，把第一次访问最后得到的“非固定权重”+“固定权重”，现在三台服务器的“非固定权重”是3，2，2，因为3是其中最大的，3对应的就是A服务器，所以这次选到的服务器就是A，然后我们用当前被选中的服务器的权重-各个服务器的权重之和，也就是A服务器的权重-各个服务器的权重之和。也就是3-7=-4，没被选中的服务器的“非固定权重”不做变化，现在三台服务器的“非固定权重”分别是-4 1 1。

• 第三次访问，把第二次访问最后得到的“非固定权重”+“固定权重”，现在三台服务器的“非固定权重”是1，3，3，这个时候3虽然是最大的，但是却出现了两个，我们选第一个，第一个3对应的就是B服务器，所以这次选到的服务器就是B，然后我们用当前被选中的服务器的权重-各个服务器的权重之和，也就是B服务器的权重-各个服务器的权重之和。也就是3-7=-4，没被选中的服务器的“非固定权重”不做变化，现在三台服务器的“非固定权重”分别是1 -4 3。
  …
  以此类推，最终得到这样的表格：
  当第8次的时候，“非固定权重“又回到了初始的5 1 1，是不是很神奇，也许算法还是比较绕的，但是能帮我们解决上边的问题呀。

通过观察表格来说，他确实是按照相应的权值来选择负载服务器的。A:B:C=5:1;1，而且还能帮我们把这些服务器很好地隔离开来。

ip-hash

ip_hash算法就是源地址hash，源地址哈希的思想是根据获取客户端的IP地址，通过哈希函数计算得到的一个数值，用该数值对服务器列表的大小进行取模运算，得到的结果便是客服端要访问服务器的序号。采用源地址哈希法进行负载均衡，同一IP地址的客户端，当后端服务器列表不变时，它每次都会映射到同一台后端服务器进行访问。

这是最简单的一致性hash算法，其中存在很多问题。

比如某台服务器挂了，3个服务器变成了2个服务器，那么此时在负载数量改变之后会有很多服务器去重新负载到其他服务器上，比如用户已经登录了，那么还需要重新登录才可以。这显然是不合理的。

那么可以使用hash环来解决，基于hash环的一致性hash算法在我的另一篇博客做了详细的介绍，此处不再赘述。想了解的可以参考：
添一致性Hash

url_hash

url_hash和ip_hash是类似的，只不过ip_hash是根据源地址去进行hash计算，然后根据原地址的hash值进行负载均衡。而url_hash算法是根据用户请求的url地址去进行hash计算，然后根据url的hash值去负载均衡。

最小响应时间

根据后台响应时间来分发请求，响应时间短的分发的请求多。