I remember, when I just started working, my colleague told me a story: when he just started working, his colleague rushed to the company excitedly one day and said, you know, the company hired a big bull. Daniel? Yeah, that guy can write AJAX! Wow, it’s a big bull. You can learn a lot from him. I listened to laugh, but it is a little difficult to understand, because now almost as long as a development, will write AJAX, how to write AJAX is big? Later I came to understand that the unfathom technology three years ago has now become common and not surprising, just like the load balancing we are going to talk about today. At some time, only the big bull can play load balancing, but today, even a small development can talk about a few words. Now, let’s take a quick look at load balancing.

From the perspective of load balancing devices, load balancing devices can be divided into hardware load balancing and software load balancing:

  • Hardware load balancing: such as the most common F5, and Array, etc., the load balance is the commercial load balancer, performance is better, after all, they is born for load balancing, behind also has a very mature team, can provide various solutions, but the price is more expensive, so there is no sufficient reason, plenty of RMB is not considered.
  • Software load balancing: including the familiar Nginx, LVS, Tengine, etc. The advantage is that the cost is relatively low, but it also needs a professional team to maintain, to step on the pit, to DIY.

In terms of load balancing technology, it can be divided into server side load balancing and client side load balancing:

  • The server load balancing: when we visit a service, the request will go to another server, then the server will be given out the request to the server that can provide this service, if only a single server, of course, that to say, the request directly to the server is ok, but if you have multiple servers? In this case, a server will be selected according to a certain algorithm.
  • Client load balancing: Client service concept of equilibrium seems to have service governance to produce, simple, is on a single server maintains all the IP service, the information such as name, when we are in the code to access a service that is accessed through a component, the component will be from the server to get all information to provide the service server, Then through a certain algorithm, select a server to request.

From the point of view of the load balancing algorithm, and divided into random, polling, hash, minimum pressure, of course, may also add the concept of weight, load balancing algorithm is the focus of this paper.

random

Random is random, randomly obtained from the load, divided into complete random and weighted random:

Completely random

Public class Servers {public List<String> List = new ArrayList<>() {{add("192.168.1.1"); Add (" 192.168.1.2 instead "); Add (" 192.168.1.3 "); }}; }Copy the code
public class FullRandom { static Servers servers = new Servers(); static Random random = new Random(); public static String go() { var number = random.nextInt(servers.list.size()); return servers.list.get(number); } public static void main(String[] args) { for (var i = 0; i < 15; i++) { System.out.println(go()); }}}Copy the code

Running results:Although it does not feel so random now, some servers are frequently obtained, and some servers are less frequently obtained, but when there are enough requests, it will be more and more average, which is a feature of random number.

Completely random is the simplest load balancing algorithm, but the disadvantage is obvious, because there are good and bad servers, the processing capacity is different, we want the good server to handle more requests, the poor server to handle less requests, so we have weighted random.

A weighted random

Weighted random, although the random algorithm is still used, but the weight is set for each server, the probability of the heavy weight of the server is greater, the probability of the small weight of the server is smaller.

There are two ways to implement the weighted randomness algorithm:

One, which is circulated on the Internet, has a simpler code: If the weight of server A is 2, Add server A to the List twice. If the weight of server B is 7, Add server B to the List 7 times, and so on. Then I generate A random number, the upper limit of which is the sum of the weights, that is, the Size of the List. In this way, the higher the weight, the higher the probability of being selected, the code is as follows:

Public Class Servers {public HashMap<String, Integer> map = new HashMap<>() {{put("192.168.1.1", 2); Put (" 192.168.1.2 instead, 7); Put (" 192.168.1.3 ", 1); }}; }Copy the code
public class WeightRandom { static Servers servers = new Servers(); static Random random = new Random(); public static String go() { var ipList = new ArrayList<String>(); for (var item : servers.map.entrySet()) { for (var i = 0; i < item.getValue(); i++) { ipList.add(item.getKey()); } } int allWeight = servers.map.values().stream().mapToInt(a -> a).sum(); var number = random.nextInt(allWeight); return ipList.get(number); } public static void main(String[] args) { for (var i = 0; i < 15; i++) { System.out.println(go()); }}}Copy the code

Running results:

It is clear that the probability of a server with a small weight being selected is relatively low.

Of course, I’m only here to demonstrate that, in general, you can move the code that builds a server List into a static code block instead of building it every time.

This implementation is relatively simple and easy to think of, but it also has disadvantages. If I set the weight of several servers to be very large, such as thousands or tens of thousands, then the server List also has tens of thousands of data, which is not a waste of memory, right?

So smart programmers came up with a second approach:

For the sake of explanation, let’s take the example above:

If server A’s weight is 2, server B’s weight is 7, and server C’s weight is 1:

  • If I generate A random number of 1, it falls on server A, because 1<=2.
  • If I generate A random number 5, it will fall on server B, because 5>2 (the weight of server A), 5-2 (the weight of server A) = 3,3 <7 (the weight of server B)
  • If I generate A random number of 10, it will fall on server C, because 10>2 (the weight of server A), 10-2 (the weight of server A) =8, 8>7 (the weight of server B), 8-7 (the weight of server B) =1,

1<=1 (weight of C server)

I don’t know if blogs have any special treatment for greater than or less symbols, so I’ll take another screenshot:

If the description isn’t clear enough, consider the following ugly pictures:

  • If the random number generated is 5, it falls to the second block
  • If the generated random number is 10, it falls into the third block

The code is as follows:

public class WeightRandom { static Servers servers = new Servers(); static Random random = new Random(); public static String go() { int allWeight = servers.map.values().stream().mapToInt(a -> a).sum(); var number = random.nextInt(allWeight); for (var item : servers.map.entrySet()) { if (item.getValue() >= number) { return item.getKey(); } number -= item.getValue(); } return ""; } public static void main(String[] args) { for (var i = 0; i < 15; i++) { System.out.println(go()); }}}Copy the code

Running results:

Although this implementation method is more “round” than the first implementation method, but it is a better implementation method, there is no waste of memory, weight Size and server List Size is not related.

polling

Polling is divided into three types: 1. Full polling 2. Weighted polling 3

Completely polling

public class FullRound { static Servers servers = new Servers(); static int index; public static String go() { if (index == servers.list.size()) { index = 0; } return servers.list.get(index++); } public static void main(String[] args) { for (var i = 0; i < 15; i++) { System.out.println(go()); }}}Copy the code

Running results:

Full polling, again, is relatively simple, but the problem is the same as completely random, so we have weighted polling.

Weighted polling

There are two common implementations of weighted polling, which are the same as weighted random. Here, I’ll show you what I think is the better one:

public class WeightRound { static Servers servers = new Servers(); static int index; public static String go() { int allWeight = servers.map.values().stream().mapToInt(a -> a).sum(); int number = (index++) % allWeight; for (var item : servers.map.entrySet()) { if (item.getValue() > number) { return item.getKey(); } number -= item.getValue(); } return ""; } public static void main(String[] args) { for (var i = 0; i < 15; i++) { System.out.println(go()); }}}Copy the code

Running results:

Weighted polling, it seems, is fine, but there are a few flaws: one server may suddenly get stressed, while the other is “sitting back, drinking coffee and watching the news.” We hope that although according to the polling, but the middle can have the best crossover, so the third polling algorithm: smooth weighted polling.

Smooth weighted polling

Smooth weighting is an algorithm, it’s an amazing algorithm, and we need to explain it first. For example, the weight of server A is 5, the weight of server B is 1, and the weight of server C is 1. This weight, we call “fixed weight”, since this is called “fixed weight”, then there must be “non-fixed weight”, yes, “non-fixed weight” will change according to certain rules every time.

  1. First visit, ABC’s “the fixed weight”, 1 (initial), May 1 for 5 is one of the biggest, 5 corresponding is A server, so choose this time to the server is A, then we use the weight of the current selected server – the sum of the weight of each server, also is the weight of A server – the sum of the weight of each server. That is, 5-7=-2. The “unfixed weight” of the unselected server does not change. Now the “unfixed weight” of the three servers is -2, 1, 1 respectively.
  2. Second visit, the first visit to finally get fixed weight “” +” fixed weight “, “without A fixed weight” of three servers now is 3,2,2, because 3 is one of the biggest, 3 corresponding is A server, so choose this time to the server is A, then we use the weight of the current selected server – the sum of the weight of each server, That’s the weight of server A – the sum of the weights of each server. That is, 3-7=-4. The “unfixed weight” of the unselected server does not change. Now the “unfixed weight” of the three servers is -4, 2, 2 respectively.
  3. Third visit, the second visit to finally get fixed weight “” +” fixed weight “, “without a fixed weight” of three servers now is 1 filling, although this time 3 is one of the biggest, but the two, we choose the first, the first 3 corresponding server is B, so choose this time to the server is B, And then we take the weight of the currently selected servers – the sum of the weights of each server, which is the weight of server B – the sum of the weights of each server. That is, 3-7=-4, the “unfixed weight” of the unselected server does not change, now the “unfixed weight” of the three servers is 1-4 3 respectively.

. And so on, you end up with a table like this:

request Get the unfixed weights before the server Selected server The unfixed weight after obtaining the server
1 {5, 1, 1} A {2, 1, 1}
2 {3, 2, 2} A {4, 2, 2}
3 {1, 3, 3} B {1, 4, 3}
4 {6, 3, 4} A {1, 3, 4}
5 {4, 2, 5} C {4, 2, 2}
6 {9, 1, 1} A {2, 1, 1}
7 {7, 0, 0} A {0, 0, 0}
8 {5, 1, 1} A {2, 1, 1}

By the eighth time, the “unfixed weight” is back to the original 5, 1, 1, isn’t it amazing? Maybe the algorithm is still more convoluted, but the code is much simpler:

public class Server { public Server(int weight, int currentWeight, String ip) { this.weight = weight; this.currentWeight = currentWeight; this.ip = ip; } 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; }}Copy the code
Public class Servers {public HashMap<String, Server> serverMap = new HashMap<>() {{put("192.168.1.1", The new Server (5, 5, "192.168.1.1")); Put (" 192.168.1.2 instead, "the new Server (1, 1," 192.168.1.2 instead ")); Put (" 192.168.1.3 ", the new Server (1, 1, "192.168.1.3")); }}; }Copy the code
public class SmoothWeightRound { private static Servers servers = new Servers(); public static String go() { Server maxWeightServer = null; int allWeight = servers.serverMap.values().stream().mapToInt(Server::getWeight).sum(); for (Map.Entry<String, Server> item : servers.serverMap.entrySet()) { var currentServer = item.getValue(); if (maxWeightServer == null || currentServer.getCurrentWeight() > maxWeightServer.getCurrentWeight()) { maxWeightServer = currentServer; } } assert maxWeightServer ! = null; maxWeightServer.setCurrentWeight(maxWeightServer.getCurrentWeight() - allWeight); for (Map.Entry<String, Server> item : servers.serverMap.entrySet()) { var currentServer = item.getValue(); currentServer.setCurrentWeight(currentServer.getCurrentWeight() + currentServer.getWeight()); } return maxWeightServer.getIp(); } public static void main(String[] args) { for (var i = 0; i < 15; i++) { System.out.println(go()); }}}Copy the code

Running results:

This is smooth weighted polling, clever use of clever algorithm, both polling effect, and avoid a server pressure suddenly increased, not bad.

The hash

The hash algorithm in the load balancing algorithm, is to generate a hash value based on a value, and then corresponding to a server, of course based on the user, based on the request parameters, or based on whatever you want to do. If the problem of Session sharing under load balancing is solved by users, the user xiaoming always goes to server A, and the user xiaoming always goes to server B.

So how to use the code to achieve it, here needs to lead to a new concept: hash ring.

What? I’ve only heard of the Olympic rings, and “ah five rings you have one more than the fourth ring, ah five rings you have one less than the sixth ring”, what is this hash ring? Let me take my time.

Hash ring, it’s a ring! This is… As if… It’s a little hard to explain, but let’s draw a picture.

A circle is composed of an infinite number of points, this is the simplest mathematical knowledge, I believe you can understand it, hash ring is the same, hash ring is also composed of an infinite number of “hash points,” of course, there is no such thing as “hash points”, just for the sake of understanding.

We first compute the server’s hash, say by IP, and then put the hash into the ring, as shown in the figure above.

A request comes in, and we hash based on some value, and if the hash comes in between A and B, the request goes clockwise to server B.

The ideal is full, the reality is very skinny, it is possible that the size of the “area” controlled by three servers are very different, or simply one of the servers is broken, the following situation will occur:

It can be seen that THE “area” of A is too large, while B can be said to be “relaxing, drinking coffee and watching movies”. In this case, it is called “hash tilt”.

So how do you avoid this? Virtual nodes.

What is a virtual node? In plain English, it is a virtual node. As if… No explanation… Let’s go back to the one that exploded in ugliness:Among them, the square is real node, or the real server, the pentagon is virtual node, or virtual server, when a request to come over, fell between A1 and B1, then according to the rules of the clockwise, should by the B1 server for processing, but B1 server is virtual, it comes from the B server mapping, Therefore, it is sent to server B for processing.

To achieve this load balancing algorithm, we need to use a Map: TreeMap, which is not commonly used in ordinary times. If you do not know TreeMap, you can first understand TreeMap. The following code is released:

private static String go(String client) { int nodeCount = 20; TreeMap<Integer, String> treeMap = new TreeMap(); for (String s : new Servers().list) { for (int i = 0; i < nodeCount; I++) treeMap. Put ((s + "- - - -" + I). The 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) {system.out.println (go(" Today is nice ")); System. The out. Println (go) (" 192.168.5.258 ")); System.out.println(go("0")); System.out.println(go("-110000")); System.out.println(go(" rain ")); }Copy the code

Running results:

This is the end of the hash load balancing algorithm.

Minimum pressure

Minimum pressure load balancing algorithm is to choose A current most “leisurely” server, if A server has 100 requests, B server has 5 requests, and C server only 3 requests, then there is no doubt will choose C server, this load balancing algorithm is more scientific. Unfortunately, the “original” minimum pressure load balancing algorithm cannot be simulated in the current scenario.

Of course, in the actual load balancing, multiple load balancing algorithms may be combined to achieve, for example, according to the minimum pressure algorithm, when there are several servers with the same small pressure, then take out a server according to the weight, if the weight is the same, then take out a random one, and so on.

That’s all for today. Thank you.