您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

手写微服务核心技术——负载均衡算法

时间:2020-07-31 10:49:20  来源:  作者:

转至小眼睛聊技术

概述

「负载均衡」是指,通过一定的算法使请求可以均匀的宠幸服务提供方,做到雨露均沾。市面上,软件硬件产品一大把,解决的最最核心的问题都是选谁

手写微服务核心技术——负载均衡算法

 

分类

按实现方式,可以分为硬件负载均衡(如 F5 、A10)、软件负载均衡(如 LVS、Nginx、HAProxy)、DNS 负载均衡。硬件负载均衡和DNS 负载均衡我们不过多关注,重点看一下软件负载均衡。

软件负载均衡又分四层和七层负载均衡,四层负载均衡就是在网络层利用 IP 地址端口进行请求的转发,基本上就是起个转发分配作用。而七层负载均衡就是可以根据访问用户的 HTTP 请求头、URL 信息将请求转发到特定的主机。LVS 为四层负载均衡。Nginx、HAProxy 可四可七。

除了专用硬件和 Nginx 这种专业软件提供负载均衡外,在代码中直接实现也是种常见的方式。比如 Spring Cloud 体系中的 Ribbon 组件提供了轮询、随机、根据响应时间加权几种负载策略,比如使用 Memcached 集群时通常会在 client 中采用 hash 取模或者一致性哈希来使数据均匀分布。

常见算法

最常见的负载均衡算法有随机、加权随机、轮询、最小连接数、一致性哈希这几种,我们分别看看用 JAVA 代码如何实现。为了方便对比,我们定义了 Balanceable 接口,假定所有参与负载均衡处理的 server 都实现了 Balanceable 接口。

1. 随机(Random)

根据后端服务器列表的大小值来随机选择其中一台进行访问,代码如下:

 public Balanceable choice(Balanceable[] servers) {
     int index = (int) (Math.random() * servers.length);
     return servers[index];
 }

优点:实现简单,通过系统随机函数随机选择其中一台进行访问

缺点:不适用后端机器承载能力不一致的情况

2. 权重随机(Weighted Random)

各个节点带有不同的权重,虽然随机选择但是期望不同权重的节点被选择的几率不一样, 权重高的被选中的几率大,权重低的被选中的几率小。代码如下:

 public Balanceable choice(Balanceable[] servers) {
     int seed = 0;
     for (Balanceable server : servers) {
         seed += server.getWeight();
     }
     int random = r.nextInt(seed);
     Collections.sort(Arrays.asList(servers));
     int tmp = 0;
     for (Balanceable server : servers) {
         tmp += server.getWeight();
         if (tmp >= random) {
             return server;
         }
     }
     return null;
 }

假设有三个节点 A、B、C 它们的权重分别是 3、2、4 ,那么就可以这样表示

手写微服务核心技术——负载均衡算法

 

取直线上的任意一个点,这个点属于直线上哪个节点的区域内就是选择了哪个节点:

  • 所有权重相加得到 S(其实就是直线的长度)
  • 从 [0, S) 的区间内取一个随机数 R(直线中随机选择一个点)
  • 遍历节点列表,把访问过的节点的权重相加得到 V,比较 V 与 R 的值,如果 V > R 当前节点即为选中的节点。(查找 R 在直线中的位置属于哪个节点所在的区域)

优点:实现简单,采用权重改变了被选中的概率

缺点:不适用后端机器承载能力不一致的情况

3. 轮询(Round Robin)

轮询指的是从已有的后端节点列表中按顺序依次选择一个节点出来提供服务。代码如下:

 
 Integer pos = 0;
 
 public Balanceable choice(Balanceable[] servers) {
     Balanceable result = null;
     synchronized(pos) {
         if (pos >= servers.length){
             pos = 0;
         }
         result = servers[pos];
         pos++;
     }
     return result;
 }

把所有待选择的机器看做是一个个的点,所有点串起来一个圆。想象一下,轮询就是对圆上的每一个点,顺时针遍历,在每个节点上停留一下。我们通过请求的次数 pos ,来实现顺时针选择。需要修改 pos 的线程,只有获取到锁才能对该值做修改,当该值大于等于服务器列表长度时,重新从 0 开始遍历,达到循环一周的目的。

手写微服务核心技术——负载均衡算法

 

优点:相对来说请求可以做到绝对平衡

缺点:为了绝对平衡,需要保证 pos 修改时的互斥性,引入了同步锁会带来性能下降

4. 最小连接数(Least Connections)

从已有的后端列表中,选择正在处理的连接数 / 请求数最少的节点出来提供服务。既然要判断连接数 / 请求数,那么每个节点都需要保存一个正在处理的连接数 / 请求数的信息,然后选取节点的时候判断一下, 选择连接数最少的那个节点。代码如下:

 public Balanceable choice(Balanceable[] servers) {
     int length = servers.size();                                                                                      
     int leastActive = -1;
     int leastCount = 0;
     int[] leastIndexs = new int[length];
     int totalWeight = 0;
     int firstWeight = 0;
     boolean sameWeight = true;
     for (int i = 0; i < length; i++) {                                                                                                                            
         Balanceable invoker = servers[i];
         int active = status.getStatus(servers).getActive();
         int weight = server.getWeight();
         
         if (leastActive == -1 || active < leastActive) {
             leastActive = active;
             leastCount = 1;
             leastIndexs[0] = i;
             totalWeight = weight;
             firstWeight = weight;
             sameWeight = true;
         } else if (active == leastActive) {
             leastIndexs[leastCount++] = i;
             totalWeight += weight;
             if (sameWeight && i > 0
                     && weight != firstWeight) {
                 sameWeight = false;
             }
         }
     }
     
     if (leastCount == 1) {    
         return servers[leastIndexs[0]];
     }
     if (!sameWeight && totalWeight > 0) {    
         int offsetWeight = random.nextInt(totalWeight);
         for (int i = 0; i < leastCount; i++) {
             int leastIndex = leastIndexs[i];
             offsetWeight -= getWeight(servers[leastIndex]);
             if (offsetWeight <= 0)
                 return servers[leastIndex];
         }
     }
     
     return servers[leastIndexs[random.nextInt(leastCount)]];
 }

首先找到服务提供者当前最小的活跃连接数,如果一个服务提供者的服务连接数比其他的都要小,则选择这个活跃连接数最小的服务提供者发起调用,如果存在多个服务提供者的活跃连接数,并且是最小的,则在这些服务提供者之间选择加权随机算法选择一个服务提供者。

优点:根据服务器当前的请求处理情况,动态分配

缺点:算法实现相对复杂,需要监控服务器请求连接数

5. 一致性哈希(Consistent Hash)

根据后端节点的某个固定属性计算 hash 值,然后把所有节点计算出来的 hash 值组成一个 hash 环。请求过来的时候根据请求的特征计算该特征的 hash 值(使用跟计算后端节点 hash 值相同的 hash 函数进行计算), 然后顺时针查找 hash 环上的 hash 值,第一个比请求特征的 hash 值大的 hash 值所对应的节点即为被选中的节点。

手写微服务核心技术——负载均衡算法

 

某一部分节点发生故障时,或者新的节点动态的增加进来时都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。

手写微服务核心技术——负载均衡算法

 

  • 构造哈希环
 public static TreeMap<Long, String> populateConsistentBuckets(
    String... servers) {
 // store buckets in tree map
     TreeMap<Long, String> consistentBuckets = new TreeMap<Long, String>();
 
     MessageDigest md5 = MD5.get();
     int totalWeight = servers.length;
 
     for (int i = 0; i < servers.length; i++) {
         int thisWeight = 1;
 
         double factor = Math
             .floor(((double) (40 * servers.length * thisWeight))
                    / (double) totalWeight);
 
         for (long j = 0; j < factor; j++) {
             byte[] d = md5.digest((servers[i] + "-" + j).getBytes());
             for (int h = 0; h < 4; h++) {
                 Long k = ((long) (d[3 + h * 4] & 0xFF) << 24)
                     | ((long) (d[2 + h * 4] & 0xFF) << 16)
                     | ((long) (d[1 + h * 4] & 0xFF) << 8)
                     | ((long) (d[0 + h * 4] & 0xFF));
 
                 consistentBuckets.put(k, servers[i]);
             }
         }
     }
     return consistentBuckets;
 }

上面的 hash 还有一个问题,就是节点的 hash 值不一定是均匀的分布在 hash 环上的,这样就会导致部分节点上承受太多的请求。解决办法是引入虚拟节点:每个节点重复 n 次,把这些虚拟节点的 hash 值(跟实际节点的 hash 值不一样,也就是说需要在节点属性中加点东西保证每个虚拟节点跟实际节点的 hash 值不一样,互相之间也要不一样)也加入到 hash 环中以此来保证分布更均匀。

  • 从环中找到合适的节点:
 public static final Long getBucket(TreeMap<Long, String> buckets, Long hv) {
     SortedMap<Long, String> t = buckets.tailMap(hv);
     return (t.isEmpty()) ? buckets.firstKey() : t.firstKey();
 }

这里有一个需要注意的点那就是临界值的处理问题:可能会有部分请求处在 hash 环上最后一个点的后面,即 hash 环上找不到一个比请求特征的 hash 值更大的一个 hash。对于这种无法在 hash 环上找到对应的下一个节点的情况,一般是把 hash 环上的第一个 hash 值作为被选中的点,即进行第二圈的顺时针查找。

优点:具有较好的容错性和可扩展性,节点加入或者去除,只有少量数据需要迁移

缺点:没有解决热点问题,会出现部分节点需要处理大量请求

总结

  • 负载均衡,目的是让每台服务器获取到适合自己处理能力的负载
  • 可以采用硬件、软件的方式进行实现
  • 常见的几种负载均衡算法,各自有优缺点,选择不同场景使用


Tags:负载均衡算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
负载均衡是将客户端请求访问,通过提前约定好的规则转发给各个server。其中有好几个种经典的算法,下面我们用Java实现这几种算法。 轮询算法轮询算法按顺序把每个新的连接请求...【详细内容】
2021-09-27  Tags: 负载均衡算法  点击:(51)  评论:(0)  加入收藏
「负载均衡」是指,通过一定的算法使请求可以均匀的宠幸服务提供方,做到雨露均沾。市面上,软件硬件产品一大把,解决的最最核心的问题都是选谁。...【详细内容】
2020-07-31  Tags: 负载均衡算法  点击:(46)  评论:(0)  加入收藏
1.Ribbon介绍因为微服务是目前互联网公司比较流行的架构,所以spring就提供了一个顶级框架-spring cloud,来解决我们在开发微服务架构中遇到的各种各样的问题,今天的主角是sprin...【详细内容】
2020-07-23  Tags: 负载均衡算法  点击:(97)  评论:(0)  加入收藏
1、完全随机算法缺点:所有服务器的访问概率都是相同的。package com.example.demo.core.random; import java.util.Arrays;import java.util.List;import java.util.Random;...【详细内容】
2020-03-04  Tags: 负载均衡算法  点击:(54)  评论:(0)  加入收藏
在分布式系统设计当中,一般会对服务进行集群部署,集群中的多个节点提供相同的服务,所以可以将对该服务的请求分发给集群的任意一个节点来处理。为了将请求合理分发给集群的节点...【详细内容】
2019-09-26  Tags: 负载均衡算法  点击:(122)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条