手写负载均衡算法

 关注
发布于: 2020 年 06 月 22 日
 
概述﻿
「负载均衡」是指，通过一定的算法使请求可以均匀的宠幸服务提供方，做到雨露均沾。市面上，软件硬件产品一大把，解决的最最核心的问题都是选谁。
﻿
﻿
分类﻿
按实现方式，可以分为硬件负载均衡（如 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 值作为被选中的点，即进行第二圈的顺时针查找。
﻿
优点：具有较好的容错性和可扩展性，节点加入或者去除，只有少量数据需要迁移
缺点：没有解决热点问题，会出现部分节点需要处理大量请求
总结﻿
负载均衡，目的是让每台服务器获取到适合自己处理能力的负载
可以采用硬件、软件的方式进行实现
常见的几种负载均衡算法，各自有优缺点，选择不同场景使用
﻿
﻿
关于我本次分享先到这里，欢迎随时指出各种错误和不足，也欢迎关注我一起交流更多的技术内容。
﻿
﻿