引言

最近好多公司都在裁员，前几天跟一个朋友聊天，他也被裁了，不过比较幸运的是他很快就找到工作了，而且工资还涨了一点，虽然没有前几年跳槽涨的多，但是在疫情之下算比较可以的了。问了下他现在的的面试难度如何，卷不卷。他说现在面试基本上是需要背一背八股文，算法题还是需要去刷一刷的。说到算法题，肯定就是去🐂客或者letcode上去刷题了。不过，有些公司为了防止大家背答案，肯定不会出上面原封不动的题目，所以我们需要的是解题思路。我曾经面试过一个公司问了一个比较有意思的算法题"负载均衡有哪写算法？" 你能不能用你擅长的语言把这些算法分别实现下？当时我记得只实现了几个？我们可以简单回顾下有哪些负载均衡算法：

常见的几种负载均衡算法

随机法

通过系统的随机算法，根据后端服务器的列表大小值来随机选取其中的一台服务器进行访问。由概率统计理论可以得知，随着客户端调用服务端的次数增多，其实际效果越来越接近于平均分配调用量到后端的每一台服务器，也就是轮询的结果。

 public static List<String> list = Arrays.asList("127.0.0.1", "127.0.0.2", "127.0.0.3", "127.0.0.4");

    static Random random = new Random();

    public static String getRandomServer() {
        int number = random.nextInt(list.size());
        return list.get(number);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 20; i++) {
            System.out.println(getRandomServer());
        }
    }

这个是最简单的，别看简单一些中间件也采取了这种算法，比如分布式配置中心apollo的客户端获取服务端地址时也是采用的这种算法：

轮询法

将请求按顺序轮流地分配到后端服务器上，它均衡地对待后端的每一台服务器，而不关心服务器实际的连接数和当前的系统负载。

顺序轮询这个比较简单，可以通过list的下标从0到服务器列表size取值，也可以借助队列来实现，当然还有其他的方法可以实现。这里只是简单的介绍了

    public static List<String> list = Arrays.asList("127.0.0.1", "127.0.0.2", "127.0.0.3", "127.0.0.4");
    static AtomicInteger index = new AtomicInteger(0);

    public static String getRoundServer() {
        if (index.get() == list.size()) {
            index.set(0);
        }
        return list.get(index.getAndIncrement());
    }
   
    static {
        queue.addAll(list);
    }
    public static String getRoundServerV2() {
        String ip = queue.poll();
        queue.add(ip);
        return ip;
    }

#源地址哈希法

源地址哈希的思想是根据获取客户端的IP地址，通过哈希函数计算得到的一个数值，用该数值对服务器列表的大小进行取模运算，得到的结果便是客服端要访问服务器的序号。采用源地址哈希法进行负载均衡，同一IP地址的客户端，当后端服务器列表不变时，它每次都会映射到同一台后端服务器进行访问。

    public static List<String> list = Arrays.asList("127.0.0.1", "127.0.0.2", "127.0.0.3", "127.0.0.4");
 public static String getHashServerV2(String sourceIp) {
      return list.get(sourceIp.hashCode() % list.size());
    }

在以前刚学 Web应用开发的时侯，应用是基于 Session 进行用户鉴权的，用户进行登录后，会在登录时的服务器A的 Session 中设置用户信息，如果下一次请求被分配到服务器B上，那么此时因 Session 中没有用户信息而报错或者重新登陆。在这种场景下一般会使用源地址哈希法进行负载均衡，保证用户每次都可以访问到 Session 信息。现在的一般不会使用 Session 进行鉴权了，大都采用 redis、memcached 等缓存服务来解决 Session 不共享的问题。源地址哈希法有个缺点一旦某个服务器挂掉了，那么哈希到该服务器的所有源请求都会失败，直到服务恢复或者服务器列表中去掉该服务器。

加权轮询法

不同的后端服务器可能机器的配置和当前系统的负载并不相同，因此它们的抗压能力也不相同。给配置高、负载低的机器配置更高的权重，让其处理更多的请；而配置低、负载高的机器，给其分配较低的权重，降低其系统负载，加权轮询能很好地处理这一问题，并将请求顺序且按照权重分配到后端。

import java.util.*;

public class WeightedRoundRobin {

    private List<String> serverList = new ArrayList<>();
    private int currentIndex = -1;

    // 构造函数，传入带权重的服务器 Map
    public WeightedRoundRobin(Map<String, Integer> servers) {
        for (Map.Entry<String, Integer> entry : servers.entrySet()) {
            String server = entry.getKey();
            int weight = entry.getValue();

            // 按照权重重复添加服务器到列表中
            for (int i = 0; i < weight; i++) {
                serverList.add(server);
            }
        }
    }

    // 获取下一个服务器
    public String getNextServer() {
        if (serverList.isEmpty()) {
            return null;
        }

        currentIndex = (currentIndex + 1) % serverList.size();
        return serverList.get(currentIndex);
    }

    // 测试代码
    public static void main(String[] args) {
        Map<String, Integer> servers = new HashMap<>();
        servers.put("127.0.0.1", 3);
        servers.put("127.0.0.2", 1);
        servers.put("127.0.0.3", 2);
        servers.put("127.0.0.4", 4);

        WeightedRoundRobin wrr = new WeightedRoundRobin(servers);

        // 模拟调用10次
        for (int i = 0; i < 10; i++) {
            System.out.println("第 " + (i+1) + " 次请求分配到：" + wrr.getNextServer());
        }
    }
}

该方法适合权重较小的简单实现，如果权重过大比如上万，），则 serverList 会非常庞大，占用内存过多。这时候这种实现就不可取了。这时候可以使用平衡加权算法

/**公众号：java金融 */
public class SmoothWeightedRoundRobin {

    // 服务器节点类
    static class Server {
        String ip;
        int weight;       // 原始权重
        int currentScore; // 当前得分

        public Server(String ip, int weight) {
            this.ip = ip;
            this.weight = weight;
            this.currentScore = 0; // 初始时设置为0
        }
    }

    private List<Server> servers = new ArrayList<>();
    private int totalWeight = 0;

    // 添加服务器
    public void addServer(String ip, int weight) {
        servers.add(new Server(ip, weight));
        totalWeight += weight;
    }

    // 获取下一个服务器
    public String getNextServer() {
        if (servers.isEmpty()) return null;

        Server selected = null;
        for (Server server : servers) {
            server.currentScore += server.weight; // 更新当前得分
            if (selected == null || server.currentScore > selected.currentScore) {
                selected = server;
            }
        }

        if (selected != null) {
            selected.currentScore -= totalWeight; // 减去总权重
            return selected.ip;
        }

        return null;
    }

    // 测试代码
    public static void main(String[] args) {
        SmoothWeightedRoundRobin wrr = new SmoothWeightedRoundRobin();
        wrr.addServer("127.0.0.1", 3);
        wrr.addServer("127.0.0.2", 1);
        wrr.addServer("127.0.0.3", 2);
        wrr.addServer("127.0.0.4", 4);



        // 模拟调用 100 次
        for (int i = 1; i <= 100; i++) {
            String serverIp = wrr.getNextServer();
            System.out.println("第 " + i + " 次请求分配到：" + serverIp);


        }


    }
}

加权随机法

与加权轮询法一样，加权随机法也根据后端机器的配置，系统的负载分配不同的权重。不同的是，它是按照权重随机请求后端服务器，而非顺序。

最小连接数法

最小连接数算法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它是根据后端服务器当前的连接情况，动态地选取其中当前积压连接数最少的一台服务器来处理当前的请求，尽可能地提高后端服务的利用效率，将负责合理地分流到每一台服务器。

总结

以上是对负载均衡常见的一些算法的简单实现，大家也可以按照自己的擅长的语言，然后动手敲一敲。可能实际工作中并不需要你去写某个算法，但是面试的时候还是会经常被要求手敲算法题的。