如何选型微服务架构的负载均衡算法？

1 负载均衡的产生

假设你订阅了一个别人的服务，从注册中心查询得到了这个服务的可用节点列表，而这个列表里包含了几十个节点，这个时候你该选择哪个节点发起调用呢？这就是客户端负载均衡算法的问题。

2 负载均衡算法的意义

考虑调用的均匀性，也就是要让每个节点都接收到调用，发挥所有节点的作用
考虑调用的性能，也就是哪个节点响应最快，优先调用哪个节点

不同负载均衡算法也就是在这两个方面的考虑不同。

3 常见的负载均衡算法

random（随机）

dubbo默认。

从可用的服务节点中，随机挑选一个节点来访问。实现时，随机算法通常通过生成一个随机数来实现，比如服务有10个节点，那么就每一次生成一个1～10之间的随机数，假设生成的是2，那么就访问编号为2的节点。采用随机算法，在节点数量足够多，并且访问量比较大的情况下，各个节点被访问的概率基本相同。

适用场景

实现简单，在请求量远超可用服务节点数量的情况下，各个服务节点被访问的概率基本相同，主要应用在各个服务节点的性能差异不大时。

roundrobin（轮询）

均匀地将流量打到各个机器上去，但如果各个机器的性能不一样，容易导致性能差的机器负载过高。所以此时需要调整权重，让性能差的机器承载权重小一些，流量少一些。

按固定顺序，把可用的服务节点，挨个访问一次。

适用场景

类似随机算法，各个服务节点被访问的概率也基本相同，也主要应用在各个服务节点性能差异不大。

实现

通常把所有可用节点放到一个数组，挨个访问。比如服务有10个节点，放到数组里就是一个大小为10的数组，这样的话就可以从序号为0的节点开始访问，访问后序号自动加1，下一次就会访问序号为1的节点，以此类推。

轮询算法能保证所有节点被访问到的概率相同。一个轮询算法的代码实现，可以参考这个示例。

加权轮询

轮询能够保证所有节点被访问的概率相同，而加权轮询算法是在此基础上，给每个节点赋予一个权重，从而使每个节点被访问到的概率不同，权重大的节点被访问的概率就高，权重小的节点被访问的概率就小。

实现

加权轮询算法是生成一个节点序列，该序列里有n个节点，n是所有节点的权重之和。在这个序列中，每个节点出现的次数，就是它的权重值。比如有三个节点：a、b、c，权重分别是3、2、1，那么生成的序列就是{a、a、b、c、b、a}，这样的话按照这个序列访问，前6次请求就会分别访问节点a三次，节点b两次，节点c一次。从第7个请求开始，又重新按照这个序列的顺序来访问节点。

要尽可能保证生产的序列的均匀，如果生成的不均匀会造成节点访问失衡，比如刚才的例子，如果生成的序列是{a、a、a、b、b、c}，就会导致前3次访问的节点都是a。

适用场景

主要用在服务节点性能差异比较大的情况。比如新的服务节点的性能往往要高于旧的节点，这个时候可以给新的节点设置更高的权重，让它承担更多的请求，充分发挥新节点的性能优势。

leastactive（最少活跃连接）

自动感知一下，如果某个机器性能越差，那么接收的请求越少，越不活跃，此时就会给不活跃的性能差的机器更少的请求

每次访问都选择连接数最少的节点。因为不同节点处理请求的速度不同，使得同一个服务消费者同每一个节点的连接数都不相同。连接数大的节点，可以认为是处理请求慢，而连接数小的节点，可以认为是处理请求快。所以在挑选节点时，可以以连接数为依据，选择连接数最少的节点访问。

在实现时，需要记录跟每一个节点的连接数，这样在选择节点时，才能比较出连接数最小的节点。

适用场景

客户端同服务端节点的连接数是在时刻变化的，理论上连接数越少代表此时服务端节点越空闲，选择最空闲的节点发起请求，能获取更快的响应速度。特别是当：

服务端节点性能差异较大
不好做到预先定义权重

采用该算法很不错。

consistanthash（一致性 hash）

一致性Hash算法，相同参数的请求一定分发到一个provider上去，provider挂掉的时候，会基于虚拟节点均匀分配剩余的流量，抖动不会太大。

通过某个hash函数，把同一个来源的请求都映射到同一个节点上。同一个来源的请求，只会映射到同一个节点上，可以说是具有记忆功能，不会有分布式会话的困扰。只有当该节点不可用时，请求才会被分配到相邻的可用节点上。

适用场景

如果你需要的不是随机负载均衡，是要一类请求都到一个节点，那就走这个一致性hash策略。

因为它能够保证同一个客户端的请求始终访问同一个服务节点，所以适合服务端节点处理不同客户端请求差异较大的场景。比如服务端缓存里保存着客户端的请求结果，如果同一客户端一直访问一个服务节点，那么就可以一直从缓存中获取数据。

这五种负载均衡算法是业界最常用的，不光在RPC调用中被广泛采用，在一些负载均衡组件比如Nginx中也有应用，所以说是一种通用的负载均衡算法，但是不是所有的业务场景都能很好解决呢？

如果：

服务节点数量众多，且性能差异比较大
服务节点列表经常发生变化，增加节点或者减少节点时有发生
客户端和服务节点之间的网络情况比较复杂，有些在一个数据中心，有些不在一个数据中心需要跨网访问，而且网络经常延迟或者抖动

这时：

随机、轮询，第一个情况就不满足
加权需要预先配置服务节点的权重，在节点列表经常变化的情况下不好维护，所以也不适合
最少活跃连接算法是从客户端自身维度去判断的，在实际应用时，并不能直接反映出服务节点的请求量大小，尤其是在网络情况比较复杂的情况下，并不能做到动态的把请求发送给最合适的服务节点
一致性hash显然也不适合这种场景

针对上面这种场景，有一种算法更加适合，这种算法就是

自适应最优选择算法

在客户端本地维护一份同每一个服务节点的性能统计快照，每隔一段时间更新该快照。发起请求时，根据“二八原则”，把服务节点分成两部分，找出20%响应最慢的节点，降低权重。这样客户端就能够实时的根据自身访问每个节点性能的快慢，动态调整访问最慢的那些节点的权重，来减少访问量，从而可以优化长尾请求。

自适应最优选择算法是对加权轮询算法的改良，可以看作是一种动态加权轮询算法:

每隔一段时间获取客户端同每个服务节点之间调用的平均性能统计需要在内存中开辟一块空间记录客户端同每一个服务节点之间调用的平均性能，并每隔一段固定时间去更新。这个更新的时间间隔不能太短，太短的话很容易受瞬时的性能抖动影响，导致统计变化太快，没有参考性；同时也不能太长，太长的话时效性就会大打折扣，效果不佳。根据我的经验，1分钟的更新时间间隔是个比较合适的值。
按这个性能统计对服务节点进行排序，对排在性能倒数20%的那部分节点赋予一个较低的权重，其余的节点赋予正常的权重关键是设定权重值，即使服务节点之间的性能差异较大，也不适合把权重设置得差异太大，可能导致性能较好的节点与性能较差的节点之间调用量相差太大，这样也不是一种合理的状态。在实际设定时，可以设置20%性能较差的节点权重为3，其余节点权重为5。

这些都属于软件层面的负载均衡算法。