负载均衡算法概述

2019/04/10 10:10
阅读数 7

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

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

常见的负载均衡算法

随机算法(伪随机)

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

在实现时,随机算法通常是通过⽣成⼀个随机数来实现,⽐如服务有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快节点,动态调整权重。

原文出处:https://www.cnblogs.com/LexMoon/p/fzjh.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部