精华内容
下载资源
问答
  • 负载均衡算法

    万次阅读 2019-10-10 17:11:02
    负载均衡算法 负载均衡算法说明 负载均衡介绍 负载均衡,英文名称为Load Balance,指由多台服务器以对称的方式组成一个服务器集合,每台服务器都具有等价的地位,都可以单独对外提供服务而无须其他服务器的辅助...

    负载均衡算法

    负载均衡算法说明
    • 负载均衡介绍
    • 负载均衡,英文名称为Load Balance,指由多台服务器以对称的方式组成一个服务器集合,每台服务器都具有等价的地位,都可以单独对外提供服务而无须其他服务器的辅助。
    • 通过某种负载分担技术,将外部发送过来的请求均匀分配到对称结构中的某一台服务器上,而接收到请求的服务器独立地回应客户的请求。
    • 负载均衡能够平均分配客户请求到服务器阵列,借此提供快速获取重要数据,解决大量并发访问服务问题,这种集群技术可以用最小的投资获得接近于大型主机的性能。
    • 负载均衡方式

    软件负载硬件负载

    • 软件负载均衡
    • 常见的负载均衡软件有:nginx,LVS,HAproxy
    • 资料:

    这三大软件负载均衡器优缺点:http://www.ha97.com/5646.html
    这三大软件负载均衡器的对比:http://www.21yunwei.com/archives/5824

    • 硬件负载均衡
    • 常见的负载均硬件件有:Array,F5
    • 负载均衡算法

    随机算法,加权轮询,一致性hash,最小活跃数算法

    负载均衡算法模拟
    • 数据支持
    • 在这里插入图片描述
    (1) 随机算法
    1、简单随机算法
    • 在这里插入图片描述

    这个简单随机算法使用与每天机器的性能差不多的时候,实际上,生产中可能某些机器的性能更高一点,它可以处理更多的情况,所以,我们可以对每台服务器设置一个权重。

    2、加权随机算法——V1
    • 在这里插入图片描述

    这个V1版本的加权随机算法的思路比较简单,每个服务器按它所对应的的权重进行复制。
    这种实现方法在遇到权重之和特别大的时候就会比较消耗内存,因为需要对ip地址进行复制,权重之和越大那么上文中的ips就需要越多的内存。

    3、加权随机算法——V2

    下面,介绍另一种实现思路。
    假设有一组服务器servers=[A,B,C],对应的权重weights=[5,3,2],权重总和为10。
    (1)现在把这些权重平铺在一维坐标上,那么就会有[0,5]区间属于服务器A,[5,8]区间属于服务器B,[8,10]区间属于服务器C。
    (2)接下来通过随机数生成一个范围在[0,10]之间的随机数,然后计算该随机数落在哪个区间上即可。

    • 在这里插入图片描述
    (2) 轮询算法
    1、简单轮询算法
    • 在这里插入图片描述

    这种简单轮询算法,很公平,每台服务器轮流来进行服务,但是有的机器性能好,所以能者多劳,和随机算法一样,所以,我们可以对每台服务器设置一个权重。

    2、加权轮询算法
    • 在这里插入图片描述

    加权轮询算法:
    思想:

    1. 例如有服务器servers=[A,B,C],对应权重weights=[2,5,1],总权重为8。
    2. 我们可以理解为有8台服务器,2台A,5台B,1台C,一次调用过来的时候,需
    3. 要按顺序访问,如有10次调用,调用顺序为AABBBBBCAA。

    步骤:

    1. 因为调用次数会越来越大,而服务器是固定,需要将调用次数“缩小”,取余
    2. 将权重值平铺在一维坐标值上:[0,2]为A,[2,7]为B,[7,8]为C
    3. 接下来获取该次是第几次请求,需要对总权重做取余运算,获取offset

    这种算法有一个缺点:一台服务器的权重特别大的时候,他需要连续的处理请求,但是实际上我们想达到的效果是,对于100次请求,只要有有100*8/50=16次就够了,这16次不一定要连续的访问,比如假设我们有三台服务器servers=[A,B,C],对应权重weights=[2,5,1],总权重为7,那么上述这算法的结果是AAAAABC,那么如果能够是这么一个结果呢:AABACAA,把B和C平均插入到5个A中间,这样是比较均衡的。

    3、平滑加权轮询算法

    那么就引出了平滑加权轮询
    思路:

    1. 每个服务器对应两个权重,分别为weight和currentWeight。其中weight是固定的,currentWeight会动态调整,初始值为0
    2. 当有新的请求进来时,遍历服务器列表,让它的currentWeight加上自身权重,遍历完成后,找到最大的currentWeight。
    3. 并将最大的currentWeight减去权重总和,然后返回相应的服务器即可。

    假设:
    测试数据:

    WEIGHT_LIST.put(“A”, 5);
    WEIGHT_LIST.put(“B”, 1);
    WEIGHT_LIST.put(“C”, 1);

    运算过程如下:

    次数 当前currentWeight数组 (currentWeight+=weight) 选择结果max(currentWeight) 减去权重总和后的currentWeight数组 (max(currentWeight)-=sum(weight))
    1 [5,1,1] A [-2,1,1]
    2 [3,2,2] A [-4,2,2]
    3 [1,3,3] B [1,-4,3]
    4 [6,-3,4] A [-1,-3,4]
    5 [4,-2,5] C [4,-2,-2]
    6 [9,-1,-1] A [2,-1,-1]
    7 [7,0,0] A [0,0,0]
    8 [5,1,1] A [-2,1,1]

    如表所示,经过平滑行处理后,得到的服务器序列为[A,A,B,A,C,A,A],相比之前的序列[A,A,A,A,A,B,C],分布性要好一些。初始情况下currentWeight=[0,0,0] ,在第7个请求处理完后,currentWeight再次变回[0,0,0]。
    你会惊讶的发现在第8次的时候,当前currentWeight数组又变回了[5,1,1] !!!

    • 具体代码实现如下图:
    • 在这里插入图片描述
    (3) 一致性哈希算法

    服务器集群接收到一次请求调用时,可以根据请求的信息,比如客户端的ip地址,或请求路径与参数等信息进行哈希,可以得出一个哈希值,特点是对于相同的ip地址,或请求路径和请求参数哈希出来的值是一样,只要能再增加一个算法,能够把这个哈希值映射成一个服务端ip的地址,就可以使相同的请求落到同一服务器上。

    因为客户端发起的请求情况是无穷大的,所以对于哈希值也是无穷大的,所以不能把所有的哈希值都进行映射到服务器ip上,所以这里需要用到哈希环。如下图:

    • 在这里插入图片描述

    上面的情况是比较均匀,如果出现ip4服务器宕机了,那就是这样的了:

    • 在这里插入图片描述

    会发现ip3和ip1直接的范围是比较大的,会有更多的请求落到ip1上,这是不公平的,解决这个问题需要加入虚拟节点:

    • 在这里插入图片描述

    其中ip2-1,ip3-1就是虚拟结点,并不能处理节点,而是等同于对应的ip2和ip3服务器。
    实际上,这只是处理这种不均衡性的一种思路,实际上就算哈希环本身是均衡的,你也可以增加更多的虚拟节点来使这个环更加平衡,比如:

    • 在这里插入图片描述

    这个彩环也是公平的,并且只有ip1,ip2,ip3,ip4是实际的服务器ip,其他的都是虚拟ip。
    那么我们怎么实现呢?

    1. 对于我们的服务器ip地址,我们肯定是知道共有多少个,需要多少个虚拟节点也是我们自己控制,虚拟节点多则流量越均衡,另外哈希算法也是很关键的,哈希算法越散列流量也将越均衡。
    2. 这种环,可以使用TreeMap来存储;当一次请求过来,获取该请求的hash值,根据hash值从TreeMap中,拿大于该hash值的子树。
    3. 再从得到的子树中,拿第一个元素即可。
    • 具体代码实现:
    • 在这里插入图片描述
    (4) 最小活跃数算法

    前面几种方法主要目标是使服务端分配到的调用次数尽量均衡,但是实际情况是这样吗?
    调用次数相同,服务器的负载就均衡吗?
    当然不是,这里还要考虑每次调用的时间,而最小活跃数算法则是解决这种问题的。

    活跃调用数越小,表明该服务提供者效率越高,单位时间内可处理更多的请求。此时应优先将请求分配给该服
    务提供者。在具体实现中,每个服务提供者对应一个活跃数。初始情况下,所有服务提供者活跃数均为0。每
    收到一个请求,活跃数加1,完成请求后则将活跃数减1。在服务运行一段时间后,性能好的服务提供者处理请
    求的速度更快,因此活跃数下降的也越快,此时这样的服务提供者能够优先获取到新的服务请求、这就是最小
    活跃数负载均衡算法的基本思想。除了最小活跃数,最小活跃数算法在实现上还引入了权重值。所以准确的来
    说,最小活跃数算法是基于加权最小活跃数算法实现的。举个例子说明一下,在-一个服务提供者集群中,有两
    个性能优异的服务提供者。某一时刻它们的活跃数相同,则会根据它们的权重去分配请求,权重越大,获取到
    新请求的概率就越大。如果两个服务提供者权重相同,此时随机选择一个即可。

    实现:
    因为活跃数是需要服务器请求处理相关逻辑配合的,- -次调用开始时活跃数+1,结束是活跃数-1, 所以这里就
    不对这部分逻辑进行模拟了,直接使用一个map来进行模拟。

    • 具体代码实现:
    //最小活跃算法
    public class LeastActive {
        private static String getServer() {
            //找出当前活跃数最小的服务器
            Optional<Integer> minValue = ServerIps.ACTIVITY_LIST.values().stream().min(Comparator.naturalOrder());
            if (minValue.isPresent()) {
                List<String> minActivityIps = new ArrayList<>();
                ServerIps.ACTIVITY_LIST.forEach((ip, activity) -> {
                    if (activity.equals(minValue.get())) {
                        minActivityIps.add(ip);
                    }
                });
                //最小活跃数的ip有多个,则根据权重来选,权重大的优先
                if (minActivityIps.size() > 1) {
                    //过滤出对应的ip和权重
                    Map<String, Integer> weightList = new LinkedHashMap<>();
                    ServerIps.WEIGHT_LIST.forEach((ip, weight) -> {
                        if (minActivityIps.contains(ip)) {
                            weightList.put(ip, ServerIps.WEIGHT_LIST.get(ip));
                        }
                    });
                    int totalWeight = 0;
                    boolean sameWeight = true;
                    Object[] weights = weightList.values().toArray();
                    //计算出总的权重,判断所有权重是否一样
                    for (int i = 0; i < weights.length; i++) {
                        Integer weight = (Integer) weights[i];
                        totalWeight += weight;
                        if (sameWeight && i > 0 && !weight.equals(weights[i - 1])) {
                            sameWeight = false;
                        }
                    }
                    //生成一个在[0,totalWeight]区间内的随机数
                    java.util.Random random = new java.util.Random();
                    int randomPos = random.nextInt(totalWeight);
                    if (!sameWeight) {
                        for (String ip : weightList.keySet()) {
                            Integer weight = weightList.get(ip);
                            if (randomPos < weight) {
                                return ip;
                            }
                            randomPos = randomPos - weight;
                        }
                    }
                    //如果所有权重都一样,就使用随机算法
                    randomPos = random.nextInt(weightList.size());
                    return (String) weightList.keySet().toArray()[randomPos];
                } else {
                    return minActivityIps.get(0);
                }
            } else {
                java.util.Random random = new java.util.Random();
                int randomPos = random.nextInt(ServerIps.WEIGHT_LIST.size());
                return (String) ServerIps.WEIGHT_LIST.keySet().toArray()[randomPos];
            }
        }
        public static void main(String[] args) {
            for (int i=0; i<10; i++){
                System.out.println(getServer());
            }
        }
    }
    

    负载均衡总结:

    • 在这里插入图片描述
    • 参考资料:http://dubbo.apache.org/zh-cn/docs/source_code_guide/loadbalance.html
    展开全文
  • 几种负载均衡算法本地流量管理技术主要有一下几种负载均衡算法:静态负载均衡算法包括:轮询,比率,优先权几种负载均衡算法本地流量管理技术主要有一下几种负载均衡算法:静态负载均衡算法包括:轮询,比率,优先权...

    几种负载均衡算法本地流量管理技术主要有一下几种负载均衡算法:静态负载均衡算法包括:轮询,比率,优先权

    几种负载均衡算法

    本地流量管理技术主要有一下几种负载均衡算法:

    静态负载均衡算法包括:轮询,比率,优先权

    动态负载均衡算法包括: 最少连接数,最快响应速度,观察方法,预测法,动态性能分配,动态服务器补充,服务质量,服务类型,规则模式。

    静态负载均衡算法

    ◆轮询(Round Robin):顺序循环将请求一次顺序循环地连接每个服务器。当其中某个服务器发生第二到第7 层的故障,BIG-IP 就把其从顺序循环队列中拿出,不参加下一次的轮询,直到其恢复正常。

    ◆比率(Ratio):给每个服务器分配一个加权值为比例,根椐这个比例,把用户的请求分配到每个服务器。当其中某个服务器发生第二到第7 层的故障,BIG-IP 就把其从服务器队列中拿出,不参加下一次的用户请求的分配, 直到其恢复正常。

    ◆优先权(Priority):给所有服务器分组,给每个组定义优先权,BIG-IP 用户的请求,分配给优先级最高的服务器组(在同一组内,采用轮询或比率算法,分配用户的请求);当最高优先级中所有服务器出现故障,BIG-IP 才将请求送给次优先级的服务器组。这种方式,实际为用户提供一种热备份的方式。

    动态负载均衡算法

    ◆最少的连接方式(Least Connection):传递新的连接给那些进行最少连接处理的服务器。当其中某个服务器发生第二到第7 层的故障,BIG-IP 就把其从服务器队列中拿出,不参加下一次的用户请求的分配, 直到其恢复正常。

    ◆最快模式(Fastest):传递连接给那些响应最快的服务器。当其中某个服务器发生第二到第7 层的故障,BIG-IP 就把其从服务器队列中拿出,不参加下一次的用户请求的分配,直到其恢复正常。

    ◆观察模式(Observed):连接数目和响应时间以这两项的最佳平衡为依据为新的请求选择服务器。当其中某个服务器发生第二到第7 层的故障,BIG-IP就把其从服务器队列中拿出,不参加下一次的用户请求的分配,直到其恢复正常。

    ◆预测模式(Predictive):BIG-IP利用收集到的服务器当前的性能指标,进行预测分析,选择一台服务器在下一个时间片内,其性能将达到最佳的服务器相应用户的请求。(被BIG-IP 进行检测)

    ◆动态性能分配(Dynamic Ratio-APM):BIG-IP 收集到的应用程序和应用服务器的各项性能参数,动态调整流量分配。

    ◆动态服务器补充(Dynamic Server Act.):当主服务器群中因故障导致数量减少时,动态地将备份服务器补充至主服务器群。

    ◆服务质量(QoS):按不同的优先级对数据流进行分配。

    ◆服务类型(ToS): 按不同的服务类型(在Type of Field中标识)负载均衡对数据流进行分配。

    ◆规则模式:针对不同的数据流设置导向规则,用户可自行。

    本文由来源 21aspnet,由 system_mush 整理编辑,其版权均为 21aspnet 所有,文章内容系作者个人观点,不代表 Java架构师必看 对观点赞同或支持。如需转载,请注明文章来源。

    展开全文
  • 负载均衡算法可以分为两类:静态负载均衡算法和动态负载均衡算法,另外还可以自定义负载均衡算法。 静态负载均衡算法 轮询(Round Robin):服务器按照顺序循环接受请求。 随机(Random):随机选择一台服务器...

    负载均衡算法可以分为两类:静态负载均衡算法和动态负载均衡算法,另外还可以自定义负载均衡算法。

    静态负载均衡算法

    1. 轮询(Round Robin):服务器按照顺序循环接受请求。
    2. 随机(Random):随机选择一台服务器接受请求。
    3. 权重(Weight):给每个服务器分配一个权重值,根据权重来分发请求到不同的机器中。
    4. IP哈希(IP Hash):根据客户端IP计算Hash值取模访问对应服务器。
    5. URL哈希(URL Hash):根据请求的URL地址计算Hash值取模访问对应服务器。
    6. 一致性哈希(Consistent Hash ):采用一致性Hash算法,相同IP或URL请求总是发送到同一服务器。

    动态负载均衡算法

    1. 最少连接数(Least Connection):将请求分配给最少连接处理的服务器。
    2. 最快响应(Fastest Response):将请求分配给响应时间最快的服务器。
    3. 观察(Observed):以连接数和响应时间的平衡为依据请求服务器。
    4. 预测(Predictive):收集分析当前服务器性能指标,预测下个时间段内性能最佳服务器。
    5. 动态性能分配(Dynamic Ratio-APM):收集服务器各项性能参数,动态调整流量分配。
    6. 服务质量(QoS):根据服务质量选择服务器。
    7. 服务类型(ToS): 根据服务类型选择服务器。

    自定义负载均衡算法

    1. 灰度发布:平滑过渡的发布方式,可以降低发布失败风险,减少影响范围,发布出现故障时可以快速回滚,不影响用户。
    2. 版本隔离:为了兼容或者过度,某些应用会有多个版本,保证1.0版本不会调到1.1版本服务。
    3. 故障隔离:生产出故障后将出问题的实例隔离,不影响其他用户,同时也保留故障信息便于分析。
    4. 定制策略:根据业务情况定制跟业务场景最匹配的策略。

    PS:上面的算法还能组合成新算法,如:

    • 轮询+权重=加权轮询。
    • 最快响应+权重,可以根据响应时间动态调整服务器的权重,达到负载均衡。

    中间件使用的负载均衡算法

    • Nginx
    1. RoundRobin:轮询。
    2. WeightedRoundRobin:加权轮询。
    3. IPHash:按访问IP的Hash选择服务器。
    4. URLHash:按请求URL的Hash选择服务器。
    5. Fair:根据后端服务器的响应时间判断负载情况,从中选出负载最轻的机器进行分流。
    • Dubbo
    1. RandomLoadBalance:加权随机。
    2. RoundRobinLoadBalance:加权轮询。
    3. LeastActionLoadBalance:最少链接数。
    4. ShortestResponseLoadBalance:最短响应时间。
    5. ConsistentHashLoadBalance:一致性Hash。
    • Ribbon
    1. RoundRobinRule:轮询。
    2. RandomRule:随机。
    3. WeightedResponseTimeRule:根据响应时间来分配权重的方式,响应的越快,分配的值越大。
    4. BestAvailableRule:会先过滤掉由于多次访问故障而处于断路器跳闸状态的服务,然后选择一个并发量最小的服务。
    5. RetryRule:先按照轮询策略获取服务,如果获取服务失败则在指定时间内进行重试,获取可用的服务。
    6. ZoneAvoidanceRule:根据性能和可用性选择服务。
    7. AvailabilityFilteringRule:会先过滤掉由于多次访问故障而处于断路器状态的服务,还有并发的连接数量超过阈值的服务,然后对剩余的服务列表按照轮询策略进行访问。

     

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,253
精华内容 3,701
关键字:

负载均衡算法