面试官：负载均衡的算法你了解不？

懿 Linux云计算网络 2021-12-21

上一篇文章我讲了关于负载均衡的三种算法，轮询法，随机法，最小连接法，这三种负载均衡的算法，但是关于负载均衡还有其他的算法，我们也需要你去看，而且在面试的过程中，很有可能是会问到的呦。

对于要实现高性能集群，选择好负载均衡器很重要，同时针对不同的业务场景选择合适的负载均衡算法也是非常重要的。之前已经罗列出几个了，接下来在说剩下的几个算法，

1. 源地址哈希算法

唯一不丢失策略的算法，但是负载均衡和源数据信息和哈希算法有很大关系。

源地址哈希法的思想是根据服务消费者请求客户端的 IP 地址，通过哈希函数计算得到一个哈希值，将此哈希值和服务器列表的大小进行取模运算，得到的结果便是要访问的服务器地址的序号。采用源地址哈希法进行负载均衡，相同的 IP 客户端，如果服务器列表不变，将映射到同一个后台服务器进行访问。

还是之前的操作，伪代码：

private static Map<String, Integer> serviceWeightMap = new HashMap<String, Integer>();

static {
    serviceWeightMap.put("192.168.1.100", 1);
    serviceWeightMap.put("192.168.1.101", 1);
    serviceWeightMap.put("192.168.1.102", 4);
    serviceWeightMap.put("192.168.1.103", 1);
   }

   public static String testConsumerHash(String remoteIp) {

       Map<String, Integer> serverMap = new HashMap<String, Integer>();
       serverMap.putAll(serviceWeightMap);

       //取得IP地址list
       Set<String> keySet = serverMap.keySet();
       ArrayList<String> keyList = new ArrayList<String>();
       keyList.addAll(keySet);

       int hashCode = remoteIp.hashCode();
       int pos = hashCode % keyList.size();

       return keyList.get(pos);
   }

这段代码来自 Will.Shun 所写，我当时看到的时候也不是很明白什么意思，后来看了一下，其实和它的解释很类似，通过哈希函数计算得到一个哈希值，将此哈希值和服务器列表的大小进行取模运算，得到的结果便是要访问的服务器地址的序号。

2. 加权轮询算法

再来看一下加权轮训算法，我们先看一下在 Nginx 里面进行的权重配置：

http {
upstream cluster {
server a weight=1;
server b weight=2;
server c weight=3;
}

假如 Nginx 每收到 6 个客户端的请求，会把其中的 1 个转发给后端 a，把其中的 2 个转发给后端 b，把其中的 3 个转发给后端 c。

加权轮询算法的结果，就是要生成一个服务器序列。每当有请求到来时，就依次从该序列中取出下一个服务器用于处理该请求。

加权轮训算法伪代码：

private static Map<String, Integer> serviceWeightMap = new HashMap<String, Integer>();

static {
    serviceWeightMap.put("192.168.1.100", 1);
    serviceWeightMap.put("192.168.1.101", 1);
    serviceWeightMap.put("192.168.1.102", 4);
    serviceWeightMap.put("192.168.1.103", 1);
   }


    public static String testWeightRoundRobin() {

        // 重新创建一个map，避免出现由于服务器上线和下线导致的并发问题
        Map<String, Integer> serverMap = new HashMap<String, Integer>();
        serverMap.putAll(serviceWeightMap);

        //取得IP地址list
        Set<String> keySet = serverMap.keySet();
        Iterator<String> it = keySet.iterator();

        List<String> serverList = new ArrayList<String>();

        while (it.hasNext()) {
            String server = it.next();
            Integer weight = serverMap.get(server);
            for (int i=0; i<weight; i++) {
                serverList.add(server);
            }
        }

        String server = null;

        synchronized (pos) {
            if (pos > serverList.size()) {
                pos = 0;
            }

            server = serverList.get(pos);
            pos++;
        }

        return server;
}

其实在加权轮训算法中，是有缺陷的，在某些特殊的权重下，加权轮询调度会生成不均匀的实例序列，这种不平滑的负载可能会使某些实例出现瞬时高负载的现象，导致系统存在宕机的风险。而为了解决这个调度的缺陷，后边就有平滑加权轮训调度，有兴趣的同学一定要去看一下这个平滑加权轮训。

3. 加权随机算法

加权随机法跟加权轮询法类似，根据后台服务器不同的配置和负载情况，配置不同的权重。不同的是，它是按照权重来随机选取服务器的，而非顺序。

    private static Map<String, Integer> serviceWeightMap = new HashMap<String, Integer>();

    static {
        serviceWeightMap.put("192.168.1.100", 1);
        serviceWeightMap.put("192.168.1.101", 1);
        serviceWeightMap.put("192.168.1.102", 4);
        serviceWeightMap.put("192.168.1.103", 1);
       }

    public static String testWeightRandom() {
        // 重新创建一个map，避免出现由于服务器上线和下线导致的并发问题
        Map<String, Integer> serverMap = new HashMap<String, Integer>();
        serverMap.putAll(serviceWeightMap);

        //取得IP地址list
        Set<String> keySet = serverMap.keySet();
        List<String> serverList = new ArrayList<String>();
        Iterator<String> it = keySet.iterator();

        while (it.hasNext()) {
            String server = it.next();
            Integer weight = serverMap.get(server);
            for (int i=0; i<weight; i++) {
                serverList.add(server);
            }
        }

        Random random = new Random();
        int randomPos = random.nextInt(serverList.size());

        String server = serverList.get(randomPos);

        return server;
    }

这里不同的地方就是服务器是通过随机算法获取。

其实我们可以想一个实例：比如说在以下场景：有一个集合 S，里面比如有 A,B,C,D 这四项。这时我们想随机从中抽取一项，但是抽取的概率不同，比如我们希望抽到 A 的概率是 50%,抽到 B 和 C 的概率是 20%,D 的概率是 10%。一般来说，我们可以给各项附一个权重，抽取的概率正比于这个权重。