负载均衡中间件

/

2019-6-23

更新中 2019-07-25

负载均衡的几种基本策略

首先介绍一些基本策略,根据是否获取服务运行状态我将其分为静态策略和动态策略两类

静态策略

1、轮询(Round Robin)法
轮询很容易实现,将请求按顺序轮流分配到后台服务器上,均衡的对待每一台服务器,而不关心服务器实际的连接数和当前的系统负载。使用轮询策略的目的是,希望做到请求转移的绝对均衡,但付出的代价性能也是相当大的。为了保证pos变量的并发互斥,引入了重量级悲观锁synchronized,将会导致该轮询代码的并发吞吐量明显下降。
轮询法适用于机器性能相同的服务,一旦某台机器性能不好,极有可能产生木桶效应,性能差的机器扛不住更多的流量。

2、随机法
通过系统随机函数,根据后台服务器列表的大小值来随机选取其中一台进行访问。由概率概率统计理论可以得知,随着调用量的增大,其实际效果越来越接近于平均分配流量到后台的每一台服务器,也就是轮询法的效果。
同样地,它也不适用于机器性能有差异的分布式系统。

3、随机轮询法
所谓随机轮询,就是将随机法和轮询法结合起来,在轮询节点时,随机选择一个节点作为开始位置index,此后每次选择下一个节点来处理请求,即(index+1)%size。
这种方式只是在选择第一个节点用了随机方法,其他与轮询法无异,缺点跟轮询一样。

4、源地址哈希法
源地址哈希法的思想是根据服务消费者请求客户端的IP地址,通过哈希函数计算得到一个哈希值,将此哈希值和服务器列表的大小进行取模运算,得到的结果便是要访问的服务器地址的序号。采用源地址哈希法进行负载均衡,相同的IP客户端,如果服务器列表不变,将映射到同一个后台服务器进行访问。该方法适合访问缓存系统,如果为了增强缓存的命中率和单调性,可以用一致性哈希算法,相关博文在https://blog.csdn.net/okiwilldoit/article/details/51352743

5、加权轮询(Weight Round Robin)法
不同的后台服务器可能机器的配置和当前系统的负载并不相同,因此它们的抗压能力也不一样。跟配置高、负载低的机器分配更高的权重,使其能处理更多的请求,而配置低、负载高的机器,则给其分配较低的权重,降低其系统负载,加权轮询很好的处理了这一问题,并将请求按照顺序且根据权重分配给后端。Nginx的负载均衡默认算法是加权轮询算法。

6、加权随机(Weight Random)法
加权随机法跟加权轮询法类似,根据后台服务器不同的配置和负载情况,配置不同的权重。不同的是,它是按照权重来随机选取服务器的,而非顺序。

动态策略

7、最小连接数法
前面我们费尽心思来实现服务消费者请求次数分配的均衡,我们知道这样做是没错的,可以为后端的多台服务器平均分配工作量,最大程度地提高服务器的利用率,但是,实际上,请求次数的均衡并不代表负载的均衡。因此我们需要介绍最小连接数法,最小连接数法比较灵活和智能,由于后台服务器的配置不尽相同,对请求的处理有快有慢,它正是根据后端服务器当前的连接情况,动态的选取其中当前积压连接数最少的一台服务器来处理当前请求,尽可能的提高后台服务器利用率,将负载合理的分流到每一台服务器。

一点测试

测试源:阿里天池比赛
https://code.aliyun.com/middlewarerace2019/adaptive-loadbalance/tree/master
比赛内容简述:修改负载均衡接口,提高负载

原Provider集群为三个节点,规格分别为大中小三种性能

原负载均衡接口代码:

  1. public class UserLoadBalance implements LoadBalance {
  2. @Override
  3. public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException {
  4. return invokers.get(ThreadLocalRandom.current().nextInt(invokers.size()));
  5. }
  6. }

容易看出demo实现了一个随机法负载策略,就是我们上面的 方法2
我们将随机法改为加权随机法,给高性能的节点分配更高的权值,代码如下

  1. public class UserLoadBalance implements LoadBalance {
  2. @Override
  3. public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException {
  4. ArrayList<Atom> atomList = new ArrayList<Atom>();
  5. atomList.add(new Atom(0, 10));
  6. atomList.add(new Atom(1, 20));
  7. atomList.add(new Atom(2, 30));
  8. // Atom atom;
  9. // atom = WeightedRandom.getWeightedRandomAtom(atomList);
  10. int id = 3;
  11. int weightSum = 0;//总权值
  12. for (Atom atom : atomList) {
  13. weightSum += atom.getWeight();
  14. }
  15. //获取总权值之间任意一随机数
  16. int random = ThreadLocalRandom.current().nextInt(weightSum); //random in [0, weightSum)
  17. //{.},{..},{...},{....}...根据权值概率区间,获得加权随机对象
  18. for (Atom atom : atomList) {
  19. random -= atom.getWeight();
  20. if (random < 0) {
  21. id = atom.getId();
  22. }
  23. }
  24. //return invokers.get(ThreadLocalRandom.current().nextInt(invokers.size()));
  25. return invokers.get(id);
  26. }
  27. }
  28. class Atom {
  29. /**
  30. * 对象标识参数
  31. */
  32. private int id;
  33. /**
  34. * 对象权重参数
  35. */
  36. private int weight;
  37. public Atom(int id, int weight) {
  38. this.id = id;
  39. this.weight = weight;
  40. }
  41. public int getWeight() {
  42. return this.weight;
  43. }
  44. public int getId() {
  45. return this.id;
  46. }
  47. }
  48. /**
  49. * 测试类
  50. *
  51. * @author Veiking
  52. */
  53. class WeightedRandom {
  54. /**
  55. * 获取加权随机对象
  56. *
  57. * @param atomList
  58. * @return Atom
  59. */
  60. public static Atom getWeightedRandomAtom(ArrayList<Atom> atomList) {
  61. if (atomList.isEmpty()) {
  62. return null;
  63. }
  64. int weightSum = 0;//总权值
  65. for (Atom atom : atomList) {
  66. weightSum += atom.getWeight();
  67. }
  68. //获取总权值之间任意一随机数
  69. int random = new Random().nextInt(weightSum); //random in [0, weightSum)
  70. //{.},{..},{...},{....}...根据权值概率区间,获得加权随机对象
  71. for (Atom atom : atomList) {
  72. random -= atom.getWeight();
  73. if (random < 0) {
  74. return atom;
  75. }
  76. }
  77. return null;
  78. }
  79. }

提交跑分,从demo的106w提升到了118w
再加上重试机制,从118w提升到了120w

分析

  1. 1. 纯随机负载+限流 情况下的瞬时流量分析

理想情况下的数据模拟如表


从图中可以很容易看出,在分给small-provider的流量中有一部分因为超载被限流卡死,而在large-provider中出现了资源浪费的情况

  1. 2. 加权随机 情况下的瞬时流量分析



提高了资源的利用率,最大限度的完成了请求响应

  1. 3. 失败重试策略 在一段时间内的流量分析


从流量图中我们看到,有的时间点流量超出了总负载能力(节点3附近),有的时间节点出现了资源浪费的情况(4节点),如果我们能把3节点附近的超出负载部分的流量向后平移1个时间节点单位,那么这些流量就可以成功响应,所谓平移,就是失败重试策略

Reproduced please indicate the author and the source, and error a link to this page.
text link: //sealbaby.cn/middleware

Say something...

Website
Username
Email