1. Introduction

Load balancing refers to the balancing of loads (work tasks) among multiple operating units. For example, load balancing can be used to select the appropriate server to respond to a request.

2. Algorithm implementation

Customize a Server class

public class Server {
    private String ip;
    private int weight;
    private int currentWeight = 0;

    public Server(String ip) {
        this.ip = ip;
    }

    public Server(String ip, int weight) {
        this.ip = ip;
        this.weight = weight;
    }

    public String getIp(a) {
        return ip;
    }

    public void setIp(String ip) {
        this.ip = ip;
    }

    public int getWeight(a) {
        return weight;
    }

    public int getCurrentWeight(a) {
        return currentWeight;
    }

    public void setCurrentWeight(int currentWeight) {
        this.currentWeight = currentWeight;
    }

    @Override
    public String toString(a) {
        return "Server{" +
                "ip='" + ip + '\' ' +
                ", weight=" + weight +
                '} '; }}Copy the code

Define the following variables in the test class to simulate the weightless and weighted servers respectively

private static Server[] IP = {
    new Server("192.168.0.1"),
    new Server("192.168.0.2"),
    new Server("192.168.0.3"),
    new Server("192.168.0.4"),
    new Server("192.168.0.5"),
    new Server("192.168.0.6"),
    new Server("192.168.0.7"),
    new Server("192.168.0.8"),
    new Server("192.168.0.9"),
    new Server("192.168.0.10")};private static int TOTAL_WEIGHT = 0;
private static Server[] IP_WITH_WEIGHT = {
    new Server("192.168.0.1".5),
    new Server("192.168.0.2".1),
    new Server("192.168.0.3".1)};static {
    for (int i = 0; i < IP_WITH_WEIGHT.length; i++) { TOTAL_WEIGHT += IP_WITH_WEIGHT[i].getWeight(); }}Copy the code

2.1 Random Algorithm

2.1.1 not

public static Server random(a) {
    Random random = new Random();
    return IP[random.nextInt(10)];
}
Copy the code

2.1.2 have weight

The idea is as follows: Find the sum of ownership weights, a random number, when the random number falls in a certain range of the sum of weights, then return the CORRESPONDING IP address in that range. It is similar to randomly placing points on a line segment to obtain the interval of the point.

public static Server randomWithWeight(a) {
    int randomWeight = new Random().nextInt(TOTAL_WEIGHT);

    for (int i = 0; i < IP_WITH_WEIGHT.length; i++) {
        int weight = IP_WITH_WEIGHT[i].getWeight();
        if (randomWeight < weight) {
            return IP_WITH_WEIGHT[i];
        } else{ randomWeight -= weight; }}return null;
}
Copy the code

2.2 Polling algorithm

2.2.1 not

private static int INDEX = 0;
public static Server roundRobin(a) {
    if (INDEX == IP.length) {
        INDEX = 0;
    }
    return IP[INDEX++];
}
Copy the code

2.2.2 have weight

Default algorithm for Nginx.

public static Server roundRobinWithWeight(a) {
    // 1. CurrentWeight is added to all servers
    for (int i = 0; i < IP_WITH_WEIGHT.length; i++) {
        int currentWeight = IP_WITH_WEIGHT[i].getCurrentWeight();
        int weight = IP_WITH_WEIGHT[i].getWeight();
        IP_WITH_WEIGHT[i].setCurrentWeight(currentWeight + weight);
    }

    // 2. Find the server with the highest currentWeight and subtract the sum of all the weights from it
    Server max = IP_WITH_WEIGHT[0];
    for (int i = 1; i < IP_WITH_WEIGHT.length; i++) {
        if (max.getCurrentWeight() < IP_WITH_WEIGHT[i].getCurrentWeight()) {
            max = IP_WITH_WEIGHT[i];
        }
    }
    max.setCurrentWeight(max.getCurrentWeight() - TOTAL_WEIGHT);

    return max;
}
Copy the code

2.3 Consistent hash algorithm

The purpose of this algorithm is that the same user will only access the same server, the algorithm can be seen in this article.

public class ConsistentHash {

    private static Server[] IP = {
            new Server("192.168.0.1"),
            new Server("192.168.0.2"),
            new Server("192.168.0.3"),
            new Server("192.168.0.4"),
            new Server("192.168.0.5"),
            new Server("192.168.0.6"),
            new Server("192.168.0.7"),
            new Server("192.168.0.8"),
            new Server("192.168.0.9"),
            new Server("192.168.0.10")};private static TreeMap<Long, Server> virtualNode = new TreeMap<>();

    /** * Number of virtual nodes per server */
    private static final int NODE_SIZE = 100;

    static {
        for (Server server : IP) {
            for (int i = 0; i < NODE_SIZE; i++) {
                longhash = getHash(server.getIp() + i); virtualNode.put(hash, server); }}}public static void main(String[] args) {
        System.out.println(getServer("10.16.129.67"));
        System.out.println(getServer("100.19.129.68"));
        System.out.println(getServer("10.16.129.67"));
    }

    /** * gets the server to be accessed by the client */
    private static Server getServer(String client) {
        long clientHash = getHash(client);

        // Get the first node of the red-black tree whose value is greater than "client hash"
        SortedMap<Long, Server> subTree = virtualNode.tailMap(clientHash);
        Long firstKey;
        if (null == subTree) {
            firstKey = virtualNode.firstKey();
        } else {
            firstKey = subTree.firstKey();
        }
        return virtualNode.get(firstKey);
    }

    /** * calculates the hash value */
    private static long getHash(String str) {
        final int p = 16777619;
        long hash = 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);
        }
        returnhash; }}Copy the code

3. Related links

• Reference 1
• Resources 2