手把手教你写出 6 种负载均衡算法

常见的负载均衡算法，大概有 7 种。它们分别是：完全随机算法、加权随机算法、完全轮询算法、加权轮询算法、平滑加权轮询算法、哈希算法、最小压力算法。本文结合我个人的理解，给大家从头来写出 6 种负载均衡算法。

负载均衡算法，虽然你平时可能用不到，但是面试中可能会被问到。比如，面试 Dubbo，就可能问问你了解不了解 Dubbo 的负载均衡算法。还有 Nginx 等，这些都和并发编程存在着一些关联。了解它们，能让我们避免很多坑。

完全随机算法

随机就是没有规律的，随便从负载中获得一台，通常我相信大家第一时间会想到随机数。完全随机算法就和随机数有些关系。看下面的实现代码：

public static List<String> list = new ArrayList<String>() {
    {
        add("a");
        add("b");
        add("c");
    }
};
static Random random = new Random();
public static String go() {
    int number = random.nextInt(list.size());
    return list.get(number);//随机获取服务器
}
public static void main(String[] args) {
    for (int i = 0; i < 15; i++) {
        System.out.println(go());
    }
}

代码非常的简单，我就不在详细的解释。下面再看加权随机算法。

随机算法有一个缺点就是，所有的服务器被访问到的概率都是相同的。如果我某台服务器性能比较好，需要随机的权重高一些，那该怎么办？加权随机算法就是解决这个问题的。

##　加权随机算法代码如下：

public static HashMap<String, Integer> map = new HashMap<String, Integer>() {
    {
        put("a", 2);
        put("b", 7);
        put("c", 1);
    }
};
static Random random = new Random();
public static String go() {
    List<String> ipList = new ArrayList<String>();
    for (Map.Entry<String, Integer> item : map.entrySet()) {
        for (int i = 0; i < item.getValue(); i++) {
            ipList.add(item.getKey());
        }
    }
    int allWeight = map.values().stream().mapToInt(a -> a).sum();
    int number = random.nextInt(allWeight);
    return ipList.get(number);
}
public static void main(String[] args) {
    for (int i = 0; i < 15; i++) {
        System.out.println(go());
    }
}

代码也非常的简单。就是根据每个服务器的权重，添加对应权重数量的服务器到集合中。然后产生随机算法，获取服务器列表。构建一个服务器的 List，如果 a 服务器的权重是 2，那么往 List 里面 Add 两次 a 服务器，如果“b”服务器的权重是 7，那么我往 List 里面 Add 7次“b”服务器，以此类推，然后我再生成一个随机数，随机数的上限就是权重的总和，也就是 List 的 Size。这样权重越大的，被选中的概率当然越高。权重大的服务器获得的概率大一些，权重小的服务器获得的概率小一些。

这个算法，虽然解决了权重问题。但是，在我的权重设置过大的时候，比如上万，上千万。那么你的 List 就会被撑爆。所以，还有另外一种写法。代码如下：

public static HashMap<String, Integer> map = new HashMap<String, Integer>() {
    {
        put("a", 2);
        put("b", 7);
        put("c", 1);
    }
};
static Random random = new Random();
public static String go1() {
    int allWeight = map.values().stream().mapToInt(a -> a).sum();
    int number = random.nextInt(allWeight);
    for (Map.Entry<String, Integer> item : map.entrySet()) {
        if (item.getValue() >= number) {
            return item.getKey();
        }
        number -= item.getValue();
    }
    return "";
}
public static void main(String[] args) {
    for (int i = 0; i < 15; i++) {
        System.out.println(go1());
    }
}

算法原理：如果 a 服务器的权重是 2，“b”服务器的权重是 7，“c”服务器的权重是 1。

如果我生成的随机数是 1，那么落到 a 服务器，因为 1<=2（ a 服务器的权重）
如果我生成的随机数是 5，那么落到”b”服务器，因为 5>2（大于 a 服务器的权重），5-2（ a 服务器的权重）= 3，3<7（“b”服务器的权重）
如果我生成的随机数是 10，那么落到“c”服务器，因为 10>2（ a 服务器的权重），10-2（ a 服务器的权重）=8，8>7（“b”服务器的权重），8-7（“b”服务器的权重）=1，1<=1（“c”服务器的权重）。

随机算法有一个缺点就是，有时候有些机器可能很长一段时间都随机不到。所以，就又有了轮询算法。

完全轮询算法，非常的简单，从头到尾，到尾了后，再从头开始。代码如下：

public static List<String> list = new ArrayList<String>() {
    {
        add("a");
        add("b");
        add("c");
    }
};
static int index;
public static String go() {
    if (index == list.size()) {
        index = 0;
    }
    return list.get(index++);
}
public static void main(String[] args) {
    for (int i = 0; i < 15; i++) {
        System.out.println(go());
    }
}

但这里还涉及到一个权重问题。因此就又有了加权轮询算法。代码如下：

public static HashMap<String, Integer> map = new HashMap<String, Integer>() {
    {
        put("a", 2);
        put("b", 7);
        put("c", 1);
    }
};
static Random random = new Random();
static int index;
public static String go() {
    int allWeight = map.values().stream().mapToInt(a -> a).sum();
    int number = (index++) % allWeight;
    for (Map.Entry<String, Integer> item : map.entrySet()) {
        if (item.getValue() > number) {
            return item.getKey();
        }
        number -= item.getValue();
    }
    return "";
}
public static void main(String[] args) {
    for (int i = 0; i < 15; i++) {
        System.out.println(go());
    }
}

加权轮询，看起来并没什么问题，但是在实际中，可能某个服务器权重大，长时间执行。遇到耗时大的请求，压力非常的大。存在着不合理性。因此就诞生了一种叫平滑加权轮询算法。

代码稍微多一点，先看一个权重类。

public class SmoothWeightServer {
    private int weight;
    private int currentWeight;
    private String ip;
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
    public int getCurrentWeight() {
        return currentWeight;
    }
    public void setCurrentWeight(int currentWeight) {
        this.currentWeight = currentWeight;
    }
    public String getIp() {
        return ip;
    }
    public void setIp(String ip) {
        this.ip = ip;
    }
    public SmoothWeightServer(int weight, int currentWeight, String ip) {
        this.weight = weight;
        this.currentWeight = currentWeight;
        this.ip = ip;
    }
}

核心代码如下：

public static HashMap<String, SmoothWeightServer> serverMap = new HashMap<String, SmoothWeightServer>() {
    {
        put("a", new SmoothWeightServer(5,5,"a"));
        put("b", new SmoothWeightServer(1,1,"b"));
        put("c", new SmoothWeightServer(1,1,"c"));
    }
};
public static String go() {
    SmoothWeightServer maxWeightServer = null;
    int allWeight = serverMap.values().stream().mapToInt(SmoothWeightServer::getWeight).sum();
    for (Map.Entry<String, SmoothWeightServer> item : serverMap.entrySet()) {
        SmoothWeightServer currentServer = item.getValue();
        if (maxWeightServer == null || currentServer.getCurrentWeight() > maxWeightServer.getCurrentWeight()) {
            maxWeightServer = currentServer;
        }
    }
    assert maxWeightServer != null;
    maxWeightServer.setCurrentWeight(maxWeightServer.getCurrentWeight() - allWeight);
    for (Map.Entry<String, SmoothWeightServer> item : serverMap.entrySet()) {
        SmoothWeightServer currentServer = item.getValue();
        currentServer.setCurrentWeight(
            currentServer.getCurrentWeight() + currentServer.getWeight());
    }
    return maxWeightServer.getIp();
}
public static void main(String[] args) {
    for (int i = 0; i < 15; i++) {
        System.out.println(go());
    }
}

算法的原理是：每个服务器都有两个权重变量。weight，配置文件中指定的该服务器的权重，这个值是固定不变的；current_weight，服务器目前的权重。一开始为 0，之后会动态调整。每次当请求到来，选取服务器时，会遍历数组中所有服务器。对于每个服务器，让它的 current_weight 增加它的 weight；同时累加所有服务器的 weight，并保存为 total。遍历完所有服务器之后，如果该服务器的 current_weight 是最大的，就选择这个服务器处理本次请求。最后把该服务器的 current_weight 减去 total。

上面的算法虽好，但是在集群环境下，我想让同一个用户的访问，分流到固定的一台机器上，怎么办？所以就又有了哈希负载均衡算法。

public static List<String> list = new ArrayList<String>() {
    {
        add("a");
        add("b");
        add("c");
    }
};
private static String go(String client) {
    int nodeCount = 20;
    TreeMap<Integer, String> treeMap = new TreeMap();
    for (String s : list) {
        for (int i = 0; i < nodeCount; i++)
            treeMap.put((s + "—业余草---" + i).hashCode(), s);
    }
    int clientHash = client.hashCode();
    SortedMap<Integer, String> subMap = treeMap.tailMap(clientHash);
    Integer firstHash;
    if (subMap.size() > 0) {
        firstHash = subMap.firstKey();
    } else {
        firstHash = treeMap.firstKey();
    }
    String s = treeMap.get(firstHash);
    return s;
}
public static void main(String[] args) {
    for (int i = 0; i < 15; i++) {
        System.out.println(go("用户来访问" + i));
    }
}

上面的 6 种负载均衡算法是非常常见的，很可能在面试中被问到。我这里只是实现，实际应用中还要结合各种设计模式。另外可能把几种算法组合起来用。

本文由创作，采用知识共享署名4.0 国际许可协议进行许可。本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。最后编辑时间为: 2021/04/19 08:59