A brief introduction to load balancing

1.1. Challenges faced by large websites

Large websites have to face the huge number of users, high concurrency, massive data and other challenges. In order to improve the overall performance of the system, two ways of vertical expansion and horizontal expansion can be adopted.

Vertical scaling: In the early stages of a website’s development, it is possible to increase the processing power of the server from a single machine perspective by increasing the hardware processing power, such as CPU processing power, memory capacity, disk capacity, etc. However, the single machine is a performance bottleneck, once hit the bottleneck, and then want to improve, the cost and cost will be extremely high. This obviously cannot meet all of the challenges of large distributed systems (websites) dealing with high traffic, high concurrency, large amounts of data and so on.

Horizontal scaling: Clustering to share traffic with large sites. Application servers (nodes) in a cluster are usually designed to be stateless, and users can request any node, which shares the access burden. Horizontal scaling has two main points:

Application cluster: Deploy the same application to multiple machines to form a processing cluster, receive requests distributed by load balancing devices, process them, and return corresponding data.
Load balancing: Distribute user access requests to nodes in the cluster through an algorithm.

1.2. What is load balancing

Load Balance (LB for short) is an essential component of high concurrency and high availability system. The goal is to distribute network traffic evenly to multiple servers to improve the overall response speed and availability of the system.

The main functions of load balancing are as follows:

High concurrency: load balancing adjusts the load through the algorithm and tries its best to evenly distribute the workload of each node in the application cluster, so as to improve the concurrent processing capacity (throughput) of the application cluster.

Scalability: Add or reduce the number of servers, and distribution is controlled by load balancing. This allows application clustering to scale.

High availability: The load balancer can monitor candidate servers, automatically skip servers when they are unavailable, and distribute requests to available servers. This makes application clustering highly available.

Security protection: some load balancing software or hardware to provide security functions, such as: black and white list processing, firewall, anti-DDoS attacks, etc.

Second, the classification of load balancing

There are many technologies to support load balancing, and we can classify them through different dimensions.

2.1 Classification of carrier dimensions

From the point of view of the carrier supporting load balancing, the load balancing can be divided into two categories: hardware load balancing and software load balancing

2.1.1 Hardware load balancing

Hardware load balancing is usually an independent load balancing server running on a custom processor, which is expensive and exclusive to the tuhao. The mainstream hardware load balancing products are :F5 and A10.

Advantages of hardware load balancing:

Powerful function: support global load balancing and provide a more comprehensive, complex load balancing algorithm.
Strong performance: hardware load balancing because it is run on the dedicated processor, so the throughput is large, can support a single machine more than one million concurrent.
High security: often have a firewall, anti-DDoS attack and other security functions.

Disadvantages of hardware load balancing:

Expensive: Hardware load balancing is expensive to buy and maintain.
Expansibility is poor: when the traffic volume increases suddenly, the dynamic capacity cannot be expanded over the limit.

2.1.2 Software load balancing

Software load balancing, the most widely used, both large and small companies will use.

Software load balancing from the software level to achieve load balancing, generally can run on any standard physical equipment.

The mainstream products of software load balancing include: Nginx, HAProxy and LVS.

The LVS can act as a four-tier load balancer. Its load balancing performance is better than that of NGINX.
HAProxy can act as an HTTP and TCP load balancer.
Nginx and HAProxy can be used as four-tier or seven-tier load balancers.

Advantages of software load balancing:

Good scalability: Adapt to dynamic changes and can be dynamically expanded beyond the initial capacity by adding software load balancing instances.
Low cost: Software load balancing can be run on any standard physical device, reducing the cost of purchase and operation.

Disadvantages of software load balancing:

Slightly poor performance: Software load balancing has slightly lower performance than hardware load balancing.

2.2 Network communication classification

From the communication level, software load balance can be divided into four layers and seven layers of load balance.

1) Seven layers of load balancing: the request can be forwarded to a specific host according to the HTTP request header and URL information of the visiting user.

DNS redirect
HTTP redirection
The reverse proxy

2) Four-layer load balancing: request forwarding based on IP address and port.

Change IP address
Change MAC address

2.2.1 DNS load balancing

DNS load balancing is generally used in Internet companies, complex business systems are not suitable for use. Large websites generally use DNS load balancing as the first level of load balancing, and then use other methods to do the second level of load balancing internally. DNS load balancing belongs to seven layers of load balancing.

DNS, or Domain Name Resolution Service, is the OSI Layer 7 network protocol. DNS is designed as a distributed application in a tree structure, from top to bottom: root DNS, primary DNS, secondary DNS… , the local domain name server. Obviously, if all the data is stored at the root domain name server, the load and overhead of DNS queries can be very large.

Therefore, DNS query is a reverse recursive process relative to the DNS hierarchy, in which a DNS client requests a local DNS server, then a DNS server, then a DNS server… , the root DNS server (also known as the authoritative DNS server). Once hit, it returns immediately. To reduce the number of queries, the DNS query cache is set at each level of the DNS server.

The working principle of DNS load balancing is: based on DNS query cache, according to the load situation to return the IP address of different servers.

Advantages of DNS redirection:

Easy to use: the load balancing work is handed over to the DNS server, which saves the trouble of the load balancing server maintenance

Improved performance: can support address based domain name resolution, parsing into the nearest server address from the user (similar to the principle of CDN), can speed up access, improve performance;

Disadvantages of DNS redirection:

Poor availability: DNS parsing is multi-level parsing, after adding/modifying DNS, parsing time is longer; The user will fail to access the site during the parsing process.

Low scalability: the control of DNS load balancing is in the domain name provider, which cannot be further improved and expanded;

Poor maintainability: does not reflect the current running state of the server; Less supported algorithms; You can’t differentiate between servers (you can’t judge the load based on the state of the system and the service).

2.2.2 HTTP load balancing

HTTP load balancing is implemented based on HTTP redirection. HTTP load balancing belongs to seven levels of load balancing.

HTTP redirect principle is: according to the user’s HTTP request to calculate a real server address, the server address is written in the HTTP redirect response, returned to the browser, the browser re-access.

Advantage of HTTP redirection: The scheme is simple.

Disadvantages of HTTP redirection:

Poor performance: Each access requires two requests to the server, increasing the latency of the access.

Lower Search Rank: By using a redirect, search engines will consider SEO cheating.

If the load balancer is down, you will not be able to access the site.

Because of its obvious disadvantages, this kind of load balancing strategy is seldom applied in practice.

2.2.3 Reverse proxy load balancing

Reverse Proxy means that the Proxy server accepts the network request, forwards the request to the server in the internal network, and returns the result obtained from the server in the internal network to the client of the network request. Reverse proxy load balancing belongs to seven layers of load balancing.

Main products of reverse proxy service: Nginx, Apache.

What is the difference between a forward proxy and a reverse proxy?

Forward Proxy: Occurs on the client side and is initiated by the user. Over the wall software is a typical forward proxy. The client accesses the proxy server to get the required extranet data, and then forwards it back to the client.

Reverse proxy: occurs on the server side and the user is unaware of the existence of the proxy.

How is the reverse proxy load balanced? Take Nginx as an example, as follows:

First, load balancing rules are set up on the proxy server. Then, when the client request is received, the reverse proxy server intercepts the specified domain name or IP request and distributes the request to the candidate server according to the load balancing algorithm. Second, if a candidate server goes down, the reverse proxy server will be fault-tolerant, such as failing to distribute requests more than 3 times and distributing them to other candidate servers.

Advantages of reverse proxy:

Multiple load balancing algorithms: Support a variety of load balancing algorithms to respond to different scene requirements.

Can monitor the server: based on the HTTP protocol, can monitor the forwarding server status, such as: system load, response time, availability, connection number, traffic, etc., so as to adjust the load balancing strategy according to these data.

Disadvantages of reverse proxy:

Additional forwarding overhead: The forwarding operation of a reverse proxy has its own performance overhead, which may include creating a connection, waiting for a connection response, analyzing the response result, and so on.

Increasing System Complexity: Reverse Proxies are often used for horizontal scaling of distributed applications. However, the reverse proxy service has the following problems. To solve the following problems will add additional complexity and operation cost to the system as a whole:

If the reverse proxy service itself is down, it cannot access the site, so it needs to have a high availability scheme, the common schemes are: main and standby mode (one main and standby), double main mode (each main and standby).
The reverse proxy service also has its own performance bottlenecks, requiring a scalable solution as the volume of requests that need to be forwarded continues to climb.

2.2.4 IP load balancing

IP load balancing is carried out by modifying the destination address of the request in the network layer.

As shown in the figure above, the IP balancing process is roughly as follows:

The client requests 192.168.137.10 and the load balancer receives the packet.

The load balancing server selects a service node 192.168.0.1 according to the algorithm, and then changes the packet request address to the IP of the node.

The real service node receives the request message, processes it, and returns the response data to the load balancing server.

The load balancing server will change the source address of the response data to the load balancing server address and return it to the client.

IP load balancing completes data distribution in the kernel process and has better slave processing performance than reverse proxy load balancing. However, since all requests and responses go through the load balancing server, the throughput of the cluster is limited by the bandwidth of the load balancing server.

2.2.5 Data link layer load balancing

Data link layer load balancing refers to modifying MAC address in data link layer of communication protocol to carry out load balancing.

The best open source link-layer load balancing product on the Linux platform is LVS (Linux Virtual Server). LVS is a load balancing system based on Netfilter framework in Linux kernel. Netfilter is a kernel Linux firewall mechanism, which can set several checkpoints (hook functions) according to the rules to perform relevant operations during the process of packet flowing through.

The workflow of LVS is as follows:

When a user accesses www.sina.com.cn, the user data passes through the network layers, and finally enters the LVS server network card through the switch, and enters the kernel network layer.

Upon entering PREROUTING, a routing lookup determines that the destination of the visit, VIP, is the native IP address, so the packets go on the INPUT chain

IPVS works on the INPUT chain, and will judge whether the request is IPVS service according to the VIP +port visited. If so, the registered IPVS HOOK function will be called to carry out the main process related to IPVS and forcibly modify the relevant data of the packet. The packets are sent to the POSTROUTING chain.

After receiving the packets at POSTROUTING, according to the target IP address (back-end server), the packets will be finally sent to the back-end servers through routing selection.

The open source version of LVS has three working modes, each of which works in distinct principles. Each mode has its own advantages and disadvantages, and is suitable for different application scenarios, but the ultimate essential function is to achieve balanced traffic scheduling and good scalability. There are mainly three modes: DR mode, NAT mode and Tunnel mode.

Third, load balancing algorithm

The implementation of load balancer can be divided into two parts:

Select a server from the list of candidate servers according to the load balancing algorithm;

Send the request data to the server.

Load balancing algorithm is the core of load balancing service. There are many kinds of load balancing products, but the principle of various load balancing algorithms is common. There are many kinds of load balancing algorithms, which are suitable for different application scenarios. This paper only introduces the characteristics and principles of the most common load balancing algorithms: polling, randomness, minimum active number, source address hash, and consistent hash.

Note: the implementation of the load balancing algorithm, recommended to read the DUBBO official load balancing algorithm description, source code explanation is very detailed, very worthy of reference.

3.1 random

3.1.1 Random algorithm

Random algorithm randomly distributes requests to candidate servers.

The random algorithm is suitable for scenarios where the server hardware is identical. Those who have studied probability theory know that when the amount of adjustment is small, the load may not be uniform. The larger the amount of adjustment, the more balanced the load is.

【 Example 】 Random algorithm implementation example

Load balancing interface

public interface LoadBalance<N extends Node> {

    N select(List<N> nodes, String ip);

}

Load balancing abstract class

public abstract class BaseLoadBalance<N extends Node> implements LoadBalance<N> { @Override public N select(List<N> nodes, String ip) { if (CollectionUtil.isEmpty(nodes)) { return null; } if (nodes.size() == 1) {return nodes.get(0); return nodes.get(0); } return doSelect(nodes, ip); } protected abstract N doSelect(List<N> nodes, String ip); }

Server node class

public class Node implements Comparable<Node> {

    protected String url;

    protected Integer weight;

    protected Integer active;

    // ...
}

Random algorithm implementation

public class RandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> { private final Random random = new Random(); Override protected N doSelect(List<N> nodes, String IP) {int index = random.nextInt(nodes.size()); return nodes.get(index); }}

3.1.2 Weighted random algorithm

Weighted Random algorithm adjusts the weight according to the probability to distribute the load on the basis of the Random algorithm.

【 Example 】 Weighted random algorithm implementation example

public class WeightRandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> { private final Random random = ThreadLocalRandom.current(); @Override protected N doSelect(List<N> nodes, String ip) { int length = nodes.size(); AtomicInteger totalWeight = new AtomicInteger(0); for (N node : nodes) { Integer weight = node.getWeight(); totalWeight.getAndAdd(weight); } if (totalWeight.get() > 0) { int offset = random.nextInt(totalWeight.get()); For (node.getWeight(); for (node.getWeight(); for (node.getWeight); If (offset < 0) {return Node; }}} // return nodes.get(random.nextInt(length)); }}

3.2 the polling

3.2.1 Polling algorithm

The strategy of the Round Robin algorithm is to distribute the requests to the candidate servers in turn.

As shown in the figure below, the load balancer receives 6 requests from the client, requests (1, 3, 5) are sent to server 1, and requests (2, 4, 6) are sent to server 2.

This algorithm is suitable for scenarios where the processing capacity of each server is similar, and the workload of each transaction does not differ much. If there is a big difference, a slower server may get backlogged and ultimately cannot handle the excessive load.

【 Example 】 An example of polling algorithm

Polling load balancing algorithm implementation

public class RoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> { private final AtomicInteger position = new AtomicInteger(0); @Override protected N doSelect(List<N> nodes, String ip) { int length = nodes.size(); // If the position value is already equal to the number of nodes, reset to 0 position.compareAndSet(length, 0); N node = nodes.get(position.get()); position.getAndIncrement(); return node; }}

3.2.2 Weighted polling algorithm

On the basis of the polling algorithm, Weighted Round Robbin algorithm adds weight attribute to adjust the number of requests of forwarding server. Nodes with high performance and high processing speed should be set with higher weights so that requests are distributed to nodes with higher weights in priority during distribution.

As shown in the figure below, server A sets the weight to 5, server B sets the weight to 1, the load balancer receives 6 requests from the client, then (1, 2, 3, 4, 5) the request will be sent to server A, (6) the request will be sent to server B.

【 Example 】 Weighted polling algorithm implementation example

The following implementation is somewhat simplified based on the Dubbo weighted polling algorithm.

public class WeightRoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> { /** * / private static final int RECYCLE_PERIOD = 60000; /** * Node HashCode to WeightDLoundroBin */ private ConcurrentMap<Integer, WeightedRoundRobin> weightMap = new ConcurrentHashMap<>(); /** * Atom UpdateLock = new AtomicBoolean(); @Override protected N doSelect(List<N> nodes, String ip) { int totalWeight = 0; long maxCurrent = Long.MIN_VALUE; // Get the current time long Now = System.currentTimeMillis(); N selectedNode = null; WeightedRoundRobin selectedWRR = null; // The following loop does the following things: // 1. Loop through the Node list, check whether the current Node has the corresponding weighteDRoundroBin, if not create // 2. Check if the Node weight has changed, and if so, update the Weight field of WeightDroundroBin // 3. Current += weight // 4. Set lastUpdate = now // 5. Find the Node with the largest current and the WeightedRoundRobin corresponding to it. For (N node: nodes) {int hashCode = node.hashCode(); WeightedRoundRobin weightedRoundRobin = weightMap.get(hashCode); int weight = node.getWeight(); if (weight < 0) { weight = 0; } // Check if the current Node has the corresponding weighteDRoundroBin, If (WeighteDroundroBin == null) {WeighteDroundroBin = new WeighteDroundroBin (); / / set the Node weight weightedRoundRobin. SetWeight (weight); WeightMap.putiFab (hashCode, weightRoundDrobin); // store the URL that uniquely identifies the mapping of the IdentifyString to the weightRoundDrobin; weightedRoundRobin = weightMap.get(hashCode); } // Node weights are not equal to the WeightedRoundRobin WeightedRoundRobin WeightedRoundRobin WeightedRoundRobin WeightedRoundRobin = weightedRoundRobin.getWeight()) { weightedRoundRobin.setWeight(weight); } / / let the current combined with its own weight, equivalent to the current + = weight long current = weightedRoundRobin. IncreaseCurrent (); / / set the lastUpdate, said the recent updated weightedRoundRobin. SetLastUpdate (now); Current if (current > maxCurrent) {maxCurrent = current; SelectedNode = SelectedNode; selectedNode = SelectedNode; SelectedWrr = SelectedWrr; SelectedWrr = SelectedWrr; SelectedWrr = SelectedWrr; } // Calculate totalWeight += Weight; } // Check the weightMap to filter out nodes that have not been updated for a long time. // The node may be down and the nodes do not contain the node, so the lastUpdate of the node cannot be updated for a long time. // If the unupdated time exceeds the threshold, it will be removed. The default threshold is 60 seconds. if (! updateLock.get() && nodes.size() ! = weightMap.size()) {if (updateLock.com PareAndSet (false, true)) {try {// WeightMap.entrySet ().removeIf(item-> now-item.getValue ().getLastUpdate() > Recycle_Period); } finally { updateLock.set(false); } } } if (selectedNode ! = null) {/ / let the current minus the weighting sum, equivalent to the current - = totalWeight selectedWRR. DecreaseCurrent (totalWeight); // return selectedNode with the largest current; } // should not happen here return nodes.get(0); } protected static class WeightRoundDrobin {private int weight; Private AtomicLong Current = new AtomicLong(0); private AtomicLong Current = new AtomicLong(0); // private Long LastUpdate; Public long increaseCurrent() {// current = current + weight; return current.addAndGet(weight); } public long decreaseCurrent(int total) { // current = current - total; return current.addAndGet(-1 * total); } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; // Current = 0 Current. Set (0); } public AtomicLong getCurrent() { return current; } public void setCurrent(AtomicLong current) { this.current = current; } public long getLastUpdate() { return lastUpdate; } public void setLastUpdate(long lastUpdate) { this.lastUpdate = lastUpdate; }}}

3.3 Minimum active number

The Least Active algorithm distributes requests to the candidate server with the lowest number of connections/requests (the server currently processing the fewest requests).

Feature: According to the candidate server current request connection number, dynamic allocation.
Scenarios: Suitable for scenarios that are sensitive to system load or where the duration of the request connection varies greatly.

Because each request has a different connection duration, using a simple round-robin or random algorithm, it is possible to have too many connections on some servers and too few connections on others, resulting in a load imbalance that is not true. While either polling or an algorithm can be used to adjust the load by weighting the attributes, the weighting method is difficult to handle dynamic changes.

For example, in the figure below, (1, 3, 5) the request is sent to server 1, but (1, 3) is soon disconnected, so only (5) requests are connected to server 1; (2, 4, 6) The request is sent to server 2 and only the connection to (2) is broken. As the system continues to run, server 2 is under too much load.

The minimum active number algorithm will record the number of connections being processed by each candidate node at the current moment, and then select the node with the smallest number of connections. This strategy can reflect the current status of the server dynamically and in real time, distribute the responsibility reasonably and evenly, and is suitable for the scene that is sensitive to the current system load.

For example, in the figure below, when server 1 has the minimum number of connections, the new incoming request 6 will be sent to server 1.

Weighted Least Connection (Weighted Least Connection) is used to calculate the number of connections each server can handle based on the weight assigned to each server based on its performance.

Implementation points of the minimum active number algorithm: the smaller the number of active calls, the higher the processing capacity of the service node, the more requests can be processed in unit time, and the request should be distributed to the service first. In the concrete implementation, each service node corresponds to an active number. In the initial case, the number of active service providers is 0. Each time a request is received, the number of activations is increased by 1, and the number of activations is decreased by 1 when the request is completed. After the service runs for a period of time, the service provider with good performance can process the request faster, so the active number decreases faster. At this time, such service provider can get the new service request first, which is the basic idea of the minimum active number load balancing algorithm.

[Example] Minimum active number algorithm implementation

The following implementation makes some changes based on the Dubbo minimum-active load balancing algorithm.

public class LeastActiveLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> { private final  Random random = new Random(); @Override protected N doSelect(List<N> nodes, String ip) { int length = nodes.size(); Int leastActive = -1; int leastActive = -1; Int leastCount = 0; int leastCount = 0; int leastCount = 0; int leastCount = 0; Int [] LeastIndexs = new int[length]; // LeastIndexs = new int[length]; int totalWeight = 0; Int firstWeight = 0; int firstWeight = 0; int firstWeight = 0; int firstWeight = 0; boolean sameWeight = true; // Nodes for (int I = 0; i < length; i++) { N node = nodes.get(i); // find a smaller active number, Restart the if (leastActive = = 1 | | node. GetActive () < leastActive) {/ / use the current number of active update the minimum number of active leastActive leastActive = node.getActive(); // update leastCount to 1; LeastIndexs [0] = I; totalWeight = node.getWeight(); firstWeight = node.getWeight(); sameWeight = true; } else if (Node.getActive () == LeastActive) {// In LeastIndexs In the nodes collection leastIndexs[leastCount++] = I; // TotalWeight += Node.getWeight (); // Set sameWeight to false if (sameWeight && I > 0 && node.getWeight()! = firstWeight) { sameWeight = false; }}} if (leastCount == 1) {return nodes.get(leastIndexs[0]); } // There are multiple nodes with the same minimum active number, but they have different weights if (! SameWeight && TotalWeight > 0) {// Randomly generate a [0, Int offsetWeight = Random.nextInt (totalWeight); // If the random number is subtracted from the Node with the minimum active number, then offset is less than or equal to 0. Return Node for (int I = 0; I < leastCount; I ++) {int leastIndexs = leastIndexs[I]; GetWeight (); if (offsetWeight <= 0) {return nodes.get(LeastIndex);}} } return nodes.get(LeastIndexs [Random.nextInt (LeastCount)]);}} return nodes.get(LeastIndexs [Random.nextInt (LeastCount)]);

3.4 Source address hash

According to the request source IP, the IP Hash algorithm obtains a value through the Hash calculation, and uses this value to carry out modulo operation in the list of candidate servers, and the result is the selected server.

The client request of the same IP can be guaranteed to be forwarded to the same server, which is used to achieve Sticky Session.

Features: ensure that a specific user always requests to the same server, if the server is down, the session will be lost.

[Example] Source address hash algorithm implementation example

public class IpHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {

    @Override
    protected N doSelect(List<N> nodes, String ip) {
        if (StrUtil.isBlank(ip)) {
            ip = "127.0.0.1";
        }

        int length = nodes.size();
        int index = hash(ip) % length;
        return nodes.get(index);
    }

    public int hash(String text) {
        return HashUtil.fnvHash(text);
    }

}

3.5 Consistent hashing

The goal of a Consistent Hash algorithm is that the same request lands on the same server as far as possible.

Consistent hashing is a good solution to the stability problem. All storage nodes can be arranged on the end to end Hash ring, and each key will find the adjacent storage node to store clockwise after calculating the Hash. When a node joins or exits, it only affects the subsequent nodes that are clockwise adjacent to the node on the Hash ring.

(1) A hash key is used to compute the hash. (2) A hash key is used to compute the hash.

The user ID

The requester IP

Request the name of the service, a string of parameter lists

2) As far as possible means: servers may be offline, changes to a few servers should not affect the majority of requests.

When a candidate server goes down, requests to that server are amortized to other candidate servers based on virtual nodes without causing drastic changes.

Advantages: Adding and removing nodes affects only the neighboring nodes in the hash ring in the clockwise direction, not the other nodes.

Disadvantages: Adding and subtracting nodes will cause some data in the hash ring to miss the hit. When a small number of nodes are used, node changes will greatly affect the data mapping in the hash ring, which is not suitable for the distributed scheme with a small number of data nodes. A normal consistent hash partition needs to double or subtract half the number of nodes in order to balance the data and load.

Pay attention toBecause of these shortcomings of consistent hash partition, some distributed systems adopt virtual slots to improve the consistent hash, such as Dynamo system.

【 Example 】 Consistent hash algorithm example

public class ConsistentHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> { private final ConcurrentMap<String, ConsistentHashSelector<? >> selectors = new ConcurrentHashMap<>(); @SuppressWarns ("unchecked") @Override protected N DosElect (List<N> nodes, String IP) {// Nodes for partition numbers, Integer replicaNum = nodes.size() * 4; // Returns the nodes' original HashCode int IdentityHashCode = System. IdentityHashCode (nodes); / / if the nodes is a new List object, means that the node number changed / / selector. At this time identityHashCode! = IdentityHashCode condition is consistentconsistenthHashSelector <N consistenthHashSelector = (consistenthHashSelector <N>) selectors. Get (IP); if (selector == null || selector.identityHashCode ! = IdentityHashCode) {// Create new consistentHashSelector selectors. Put (IP, new consistentHashSelector <>(nodes, consistentHashSelector) {// consistentHashSelector <>(nodes, consistentHashSelector); identityHashCode, replicaNum)); selector = (ConsistentHashSelector<N>) selectors.get(ip); } // The call is consistentHashSelector's select method selects Node return selector. Select (IP); } /** * Private static final class consistenthHashSelector <N extends Node> {/** * Stalls virtual nodes */ Private final TreeMap<Long, N> virtualNodes; private final int identityHashCode; /** * Constructor ** @Param Nodes Node List * @Param IdentityHashCode hashCode * @Param Replicanum Shard Number */ ConsistentHashSelector(List<N> nodes, int identityHashCode, Integer replicaNum) { this.virtualNodes = new TreeMap<>(); this.identityHashCode = identityHashCode; If (replicaNum == null) {replicaNum = 100; } for (N node : nodes) { for (int i = 0; i < replicaNum / 4; I++) {byte[] digest = md5(node.getUrl()); For (int j = 0; for (int j = 0; j < 4; J++) {// when h = 0, select * from Digest where h = 0 and select * from Digest where h = 1. Long m = hash(digest, j); long m = hash(digest, j); // Store the hash to node mapping in VirtualNodes. // VirtualNodes needs to provide efficient query operation, so TreeMap is selected as the storage structure VirtualNodes. Put (m, node); }}}} public N select(String key) {byte[] digest = md5(key); Select (hash(digest, 0)); select (hash(digest, 0)); } private N selectForKey(long hash) {// Find the first node that is greater than or equal to the current hash. N> entry = virtualNodes.ceilingEntry(hash); // If the hash is greater than the Node's maximum position on the hash ring, then entry = null, // We need to assign the header node of the TreeMap to entry if (entry == null) {entry = VirtualNodes.FirstEntry (); } // return Node return entry.getValue(); Public static long hash(byte[] Digest, byte[] Digest, int number) { return (((long) (digest[3 + number * 4] & 0xFF) << 24) | ((long) (digest[2 + number * 4] & 0xFF) << 16) | ((long) (digest[1 + number * 4] & 0xFF) << 8) | (digest[number * 4] & 0xFF)) & 0xFFFFFFFFL; } public static byte[] MD5 (String value) {MessageDigest MD5; try { md5 = MessageDigest.getInstance("MD5"); } catch (NoSuchAlgorithmException e) { throw new IllegalStateException(e.getMessage(), e); } md5.reset(); byte[] bytes = value.getBytes(StandardCharsets.UTF_8); md5.update(bytes); return md5.digest(); }}

The above example is a simplification based on Dubbo’s consistent hash load balancing algorithm.

4. Reference materials

1. Comparing Load Balancing Algorithms

2. “Technical Architecture of Large Websites: Core Principles and Case Studies”

3. Large website architecture series: load balancing detail (1)

4. What is load balancing

5. What Is Load Balancing

6. Dubbo official load balancing algorithm description

7. Load balancing algorithm and means

8. Use DNS parsing to achieve load balancing of the website

Author: Vivo Internet team -Zhang Peng

Load balancing