负载均衡算法原理解析（二）

分手后的思念是犯贱 2022-04-23 06:36 159阅读 0赞

上一篇文章中讲解了[加权随机和加权轮询算法][Link 1]，本文主要讲解剩余的两个，一致性哈希和最小活跃数算法的实现思想。

#### 一致性哈希-ConsistentHashLoadBalance ####

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

但是也有一个问题，因为客户端发起的请求情况是无穷无尽的，所以对于哈希值也是无穷大的，所以不可能把所有的哈希值都映射到服务端IP上，这里就需要用到**哈希环**。  
![hash环1][hash_1]

哈希值如果落在ip1和ip2之间，则应该选择ip2作为结果；如果落在ip2和ip3之间，则应该选择ip3作为结果，后面以此类推。 上面这是比较均匀的情况，如果ip4服务器不存在，就会变成下面这样：  
![哈希环2][2]  
此时会发现，ip3和ip1之间的范围比较大，会有更多的请求落在ip1上，这是**不公平**的，解决这个问题需要加入虚拟节点，像下面这样：  
![哈希环3][3]  
其中ip2-1,ip3-1是虚拟节点，并不能处理请求，等同于对应的ip2和ip3服务器。实际上，这只是处理这种不均衡性的一种思路，就算哈希环本身是均衡的，我们也可以增加更多的虚拟节点来使这个环更加平滑，像下面这样：  
![哈希环4][4]  
其中只有ip1、ip2、ip3、ip4是实际的服务器，其他的都是虚拟ip。

**实现如下：**

> 对于我们的服务端IP地址，我们肯定知道有多少个，需要多少个虚拟节点也由我们自己控制，虚拟节点越多流量越均衡，另外哈希算法也很关键，哈希算法越散列流量也将越均衡。

public class ConsistentHashLoadBalance {
        private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
        // 虚拟节点数
        private static final int VIRTUAL_NODES = 400;
    
        static {
            // 对每个真实节点添加虚拟节点，虚拟节点会根据哈希算法进行散列
            for (String ip : ServerIps.LIST) {
                for (int i = 0; i < VIRTUAL_NODES; i++) {
                    int vhash = getHash(ip + "VN" + i);
                    virtualNodes.put(vhash, ip);
                }
            }
        }
    
        private static String getServer(String client) {
            int hash = getHash(client);
            // 得到大于该Hash值的排好序的Map
            SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
    
            // 大于该Hash值的第一个元素的位置
            Integer nodeIndex = subMap.firstKey();
    
            // 如果不存在大于该Hash值的元素，则返回根节点
            if (nodeIndex == null) {
                nodeIndex = virtualNodes.firstKey();
            }
    
            // 返回对应的虚节点名称
            return subMap.get(nodeIndex);
        }
    
        // hash实现
        private static int getHash(String str) {
            final int p = 16777619;
            int hash = (int) 2166136261L;
            for (int i = 0; i < str.length(); i++) {
                hash = (hash ^ str.charAt(i)) * p;
            }
            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            // 如果算出来的值为附属则取其绝对值
            if (hash < 0) {
                hash = Math.abs(hash);
            }
            return hash;
        }
    }

#### 最小活跃数-LeastActiveLoadBalance ####

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

活跃调用数越小，表明该服务器处理请求越快，提供服务效率越高，单位时间内可处理更多的请求，此时应优先将请求分配给该服务提供者。

**实现思路：**  
每个服务提供者对应一个活跃数。初始情况下，所有服务提供者活跃数均为0，每收到一个请求，活跃数加1，完成请求后则将活跃数减1。在服务运行一段时间后，性能好的服务提供者处理请求速度更快，因此活跃数下降的也越快，此时这样的服务提供者能够优先获取到新的服务请求。

除了最小活跃数，最小活跃数算法在实现上还引入了权重值。所以准确来说，最小活跃数算法是基于加权最小活跃数算法实现的。

> 举个例子说明一下：假如有两个服务提供者，某一时刻它们的活跃数相同，则会根据他们那的权重去分配请求，权重越大，获取到新请求的概率越大。如果权重相同，则随机选择一个。

**实现如下：**  
因为活跃数是需要服务器请求处理相关逻辑配合，一次调用活跃数+1，结束时活跃数-1，这里直接使用一个上文中的`ACTIVITY_LIST`来模拟。

public class LeaseActiveLoadBalance {
        private static String getServer() {
            // 找出当前活跃最小的服务器
            Optional<Integer> minValues = ServerIps.ACTIVITY_LIST.values().stream().min(Comparator.naturalOrder());
    
            if (minValues.isPresent()) {
                List<String> minActivityIps = new ArrayList<>();
                ServerIps.ACTIVITY_LIST.forEach((ip, activity) -> {
                    if (activity.equals(minValues.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));
                        }
                    });
                    // 获取权重最大值的服务器IP
                    return getServerByMaxWeight(weightList);
                } else {
                    return minActivityIps.get(0);
                }
            } else {
                // 没配置活跃数，则走加权随机
                return getServerByWeight(ServerIps.WEIGHT_LIST);
            }
        }
    
        /**
         *  加权随机算法
         * @param weightList
         * @return
         */
        public static String getServerByWeight(Map<String, Integer> weightList) {
        	// 参考上一篇文章中加权随机算法实现
        }
    
        /**
         * 获取权重最大值
         * @param weightList
         * @return
         */
        public static String getServerByMaxWeight(Map<String, Integer> weightList) {
            int maxWeight = 0;
            String maxWeightIp = "";
            boolean sameWeight = true;
            Object[] ips = weightList.keySet().toArray();
    
            for (int i = 0; i < ips.length; i++) {
                Integer weight = (Integer) weightList.get(ips[i]);
                if (sameWeight && i > 0 && !weight.equals(weightList.get(ips[i - 1]))) {
                    sameWeight = false;
                }
                if (maxWeight < weight) {
                    maxWeight = weight;
                    maxWeightIp = (String) ips[i];
                }
            }
    
            if (!sameWeight) {
                return maxWeightIp;
            }
    
            // 如果所有权重相等,走普通随机
            return (String) weightList.keySet().toArray()[new Random().nextInt(weightList.size())];
        }
    }

这里因为活跃数是固定的，所以结果也是固定的，读者可进行自行扩展。

**注意**  
本文提到的算法以理解实现思想为主，实际生产环境要复杂很多，还需要做更多的处理。

**参考资料**  
[http://dubbo.apache.org/zh-cn/docs/source\_code\_guide/loadbalance.html][http_dubbo.apache.org_zh-cn_docs_source_code_guide_loadbalance.html]

--------------------

\------------本文结束感谢您的阅读------------

[Link 1]: https://blog.csdn.net/hzygcs/article/details/86622651
[hash_1]: /images/20220323/debfbd4865a5482f9ba494710e318d1a.png
[2]: /images/20220323/656a6aeb78e3407faadc1bf097217c75.png
[3]: /images/20220323/d8a8188f7efe4016a28e3e9fb9283fcf.png
[4]: /images/20220323/0751480c9dc040c4aabd1ebc594af7c0.png
[http_dubbo.apache.org_zh-cn_docs_source_code_guide_loadbalance.html]: http://dubbo.apache.org/zh-cn/docs/source_code_guide/loadbalance.html