负载均衡算法概述

我们查询注册中心获得了某个服务的可用节点列表，我们需要从可用节点列表中选择一个发起调用，这就是负载均衡的所用了。

需要考虑两个因素，⼀个是要考虑调⽤的均匀性，也就是要让每个节点都接收到调⽤，发挥所有节点的作⽤，另⼀个是要考虑调⽤的性能，也就是哪个节点响应最快，优先调⽤哪个节点。

常见的负载均衡算法

随机算法(伪随机)

随机算法，顾名思义就是从可⽤的服务节点中，随机挑选⼀个节点来访问。

在实现时，随机算法通常是通过⽣成⼀个随机数来实现，⽐如服务有10个节点，那么就每⼀次⽣成⼀个1～10之间的随机数， 假设⽣成的是2，那么就访问编号为2的节点。

采⽤随机算法，在节点数量⾜够多，并且访问量⽐较⼤的情况下，各个节点被访问的概率是基本相同的。

改算法的核心就是获取一个不超过服务节点列表大小的随机整数。

int idx = (int) (ThreadLocalRandom.current().nextDouble() * servicesList.size());

如何实现真随机

霍金有句名言：“谁跟我提薛定谔的猫，我就去拿我的枪”。因为在我们的宏观世界中薛定谔的猫其实是一个很荒谬的真理，这只猫既是活着的又是死的，在没有开箱之前，一切都是不确定的，同时，我觉得这才是真随机，不同于计算机中的随机数生成，因为大多数语言的随机数生成是基于时钟的，例如c中的srand就是与计算机目前的时刻与1970年1月1日0时0分0秒之间的时间差有关。

假如说我对于时间的掌控足够强大，我就可以在某个特定时刻发起调用，这样使用随机调用的负载均衡算法到底调用了哪个节点，当然就在我的掌控之中了。

所以说在我们的宏观世界，一切所谓的随机都是不存在的，拉普拉斯妖可以根据现有的状态得到我们所谓的随机值。

那么在微观世界呢？ 记得在高中物理中，我们学到过光的波粒二象性，光既是波又是粒子，仔细一想，细思极恐，你既是男人又是女人，没有验身之前你有男女太监三种状态，就好像薛定谔的猫，没有开箱前有死活两种状态。这是爱因斯坦发现的，记得课本上说的是使用了双缝实验。在探测仪观察的情况下光是粒子，只通过单缝，在没观察的情况下是波，通过双缝。至于粒子到底通过哪一夹缝，这才是真正的随机。

对于物理学家来说，这种量子随机性是宇宙唯一的随机性，是物理定律不能预测的结果。

建议各位妄图调度方便而使用随机算法的人，先去搞一个光子发射设备，放在计算机里面用来实现随机算法。

轮询算法

轮询算法，顾名思义就是按照固定的顺序，把可⽤的服务节点，挨个访问⼀次。

在实现时，轮询算法通常是把所有可⽤节点放到⼀个数组⾥，然后按照数组编号，挨个访问。

⽐如服务有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。

最少活跃连接算法

最少活跃连接算法，顾名思义就是每⼀次访问都选择连接数最少的节点。

因为不同节点处理请求的速度不同，使得同⼀个服务消费者同每⼀个节点的连接数都不相同。

连接数⼤的节点，可以认为是处理请求慢，⽽连接数小的节点，可以认为是处理请求快。所以在挑选节点时，可以以连接数为依据，选择连接数最少的节点访问。

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

⼀致性hash算法

⼀致性hash算法，是通过某个hash函数，把同⼀个来源的请求都映射到同⼀个节点上。⼀致性hash算法最⼤的特点就是同⼀个来源的请求，只会映射到同⼀个节点上，可以说是具有记忆功能。只有当这个节点不可⽤时，请求才会被分配到相邻的可⽤节点上。

总结

上面五种负载均衡算法分别可以应用在不同的场景，最近正好在写Zeus的负载均衡策略，考虑之后决定使用改造后的加权轮询算法，在每一个client中会有一个定时任务，去获取所有节点的近期访问的性能统计，根据性能快慢，把服务节点按照二八分为20%慢节点80快节点，动态调整权重。