Introduction to Load balancing
1.1. Challenges faced by large sites
Large websites have to face the huge number of users, high concurrency, massive data and other challenges. To improve the overall performance of the system, two methods of vertical expansion and horizontal expansion can be adopted.
Vertical scaling: In the early days of web development, you can increase the server processing power from a standalone perspective by increasing hardware processing power, such as CPU processing power, memory capacity, disk, etc. However, the single machine is a performance bottleneck, once the bottleneck, and then want to improve, the cost and cost will be very high. This obviously cannot meet all the challenges of large distributed systems (websites) dealing with high traffic, high concurrency, massive data, etc.
Horizontal scaling: Sharing the traffic of large websites through clustering. Application servers (nodes) in a cluster are usually designed to be stateless, so users can request any one of them, and these nodes share the access pressure. Horizontal scaling has two main points:
-
Application cluster: An application is deployed on multiple machines to form a processing cluster to receive, process, and return data from the load balancing device.
-
Load balancing: Distributing user access requests to nodes in a cluster through an algorithm.
1.2. What is load balancing
Load Balance (LB) is an essential component of a high-concurrency, high-availability system. The goal is to evenly distribute network traffic 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: The load balancing algorithm adjusts the load to evenly distribute the workload among nodes in the application cluster to improve the concurrent processing capability (throughput) of the application cluster.
Scalability: Add or reduce the number of servers and then control the distribution by load balancing. This allows the application cluster to scale.
High availability: The load balancer can monitor candidate servers, and when a server is unavailable, it automatically skips and distributes requests to available servers. This makes the application cluster highly available.
Security protection: Some load balancing software or hardware provides security functions, such as blacklist and whitelist processing, firewall, and anti-ddos attacks.
Second, the classification of load balancing
There are many techniques that support load balancing, and we can classify them in different dimensions.
2.1 Carrier dimension classification
From the point of view of the carriers that support load balancing, load balancing can be divided into two types: hardware load balancing and software load balancing
2.1.1 Hardware LOAD Balancing
Hardware load balancers, typically independent load balancers running on custom processors, are expensive and exclusive to the rich. The main products of hardware load balancing are F5 and A10.
Hardware load balancing has the following advantages:
-
Powerful: Supports global load balancing and provides comprehensive and complex load balancing algorithms.
-
Strong performance: Hardware load balancing is run on dedicated processors, so it has high throughput and can support more than one million concurrent stand-alone machines.
-
High security: Security functions such as firewalls and anti-ddos attacks are provided.
Disadvantages of hardware load balancing:
-
Expensive: The cost of buying and maintaining hardware load balancing is high.
-
Poor scalability: When the access volume increases suddenly, the system cannot dynamically expand the capacity.
2.1.2 Software LOAD Balancing
Software load balancing, the most widely used, is used by both large and small companies.
Software LOAD balancing implements load balancing at the software level and can generally run on any standard physical device.
The mainstream software load balancing products are: Nginx, HAProxy, LVS.
-
LVS can be used 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 layer 4 or 7 load balancers.
Advantages of software load balancing:
-
Good scalability: It can adapt to dynamic changes and dynamically expand beyond the initial capacity by adding software load balancing instances.
-
Low cost: Software load balancing can run on any standard physical device, reducing the cost of purchase, operation and maintenance.
Disadvantages of software load balancing:
- Slightly poor performance: The performance of software LOAD balancers is slightly lower than that of hardware load balancers.
2.2 Network communication classification
From the perspective of communication level, software load balancing can be divided into four and seven layers of load balancing.
1) Layer 7 load balancing: The request can be forwarded to a specific host according to the HTTP request header and URL information of the user.
-
DNS redirect
-
HTTP redirection
-
The reverse proxy
2) Layer 4 load balancing: Requests are forwarded based on IP addresses and ports.
-
Changing an IP Address
-
Modifying a MAC Address
2.2.1 DNS load balancing
DNS load balancing is generally used by Internet companies and is not suitable for complex business systems. Large websites generally use DNS load balancing as the first level of load balancing, and then internally use other methods for the second level of load balancing. DNS load balancing belongs to layer 7 load balancing.
DNS is the OSI Layer 7 network protocol for domain name resolution. DNS is designed as a tree structure of distributed applications, top-down: root DNS server, level-1 DNS server, level-2 DNS server,… , local DOMAIN name server. Obviously, if all the data is stored at the root DNS server, the load and overhead of DNS queries can be enormous.
Therefore, THE DNS query is a reverse recursive process relative to the DNS hierarchy, in which the DNS client requests the local DNS server, the next-level DNS server, the next-level DNS server… , the root DNS server (also called the authoritative DNS server). Once a match is struck, the server returns immediately. To reduce the number of queries, the DNS query cache is configured on each level of the DNS server.
The working principle of DNS load balancing is to query the CACHE based on DNS and return IP addresses of different servers based on the load.
The advantages of DNS redirection are:
Simple to use: load balancing work, to the DNS server processing, save load balancing server maintenance trouble
Improved performance: The domain name can be resolved based on the address, which can be resolved into the server address nearest to the user (similar to the principle of CDN), which can speed up access and improve performance.
Disadvantages of DNS redirection:
Poor availability: DNS resolution is performed at multiple levels. The resolution takes a long time after a DNS is added or modified. During the resolution process, users will fail to access the website.
Low scalability: The DNS load balancing is controlled by the domain name vendor and cannot be improved or expanded.
Poor maintenance: It cannot reflect the current running status of the server. Few algorithms are supported; You cannot distinguish between servers (you cannot determine load based on the state of the system and services).
2.2.2 HTTP Load balancing
HTTP load balancing is implemented based on HTTP redirection. HTTP load balancing belongs to layer 7 load balancing.
The HTTP redirection mechanism is as follows: Based on the HTTP request, a real server address is calculated, and the server address is written into the HTTP redirection response, which is returned to the browser. Then the browser can access the server again.
Advantages of HTTP redirection: Simple solution.
Disadvantages of HTTP redirection:
Poor performance: Two requests to the server are required for each access, increasing the latency of access.
Lower search rankings: After using redirects, search engines will consider SEO cheating.
If the load balancer is down, the site cannot be accessed.
Because of its obvious disadvantages, this load balancing strategy is rarely used in practice.
2.2.3 Reverse proxy load balancing
In Reverse Proxy mode, a Proxy server receives network requests, forwards the requests to the Intranet server, and returns the results obtained from the Intranet server to the network request client. Reverse proxy load balancing belongs to seven layers of load balancing.
Mainstream products of reverse proxy services: Nginx, Apache.
What’s the difference between a forward proxy and a reverse proxy?
Forward proxy: Occurs on the client and is initiated by the user. Wall-climbing software is a typical forward proxy. The client accesses the proxy server actively so that the proxy server can obtain the required extranet data and then forward it back to the client.
Reverse proxy: Occurs on the server side and the user is unaware of the existence of the proxy.
How does a reverse proxy achieve load balancing? Take Nginx as an example.
First, load balancing rules are set up on the proxy server. Then, when a client request is received, the reverse proxy server intercepts the specified domain name or IP request and distributes the request to the candidate server based on a load-balancing algorithm. Second, if one of the candidate servers goes down, the reverse proxy server will be error-tolerant, such as failing to distribute requests more than three times and distributing the requests to other candidate servers.
Advantages of reverse proxy:
Multiple load balancing algorithms: Supports multiple load balancing algorithms to meet the requirements of different scenarios.
Servers can be monitored: Based on the HTTP protocol, the status of forwarding servers, such as system load, response time, availability, connection number, and traffic, can be monitored to adjust load balancing policies based on these data.
Disadvantages of reverse proxy:
- Additional forwarding costs: The reverse proxy forwarding operation itself has a performance cost, which may include creating a connection, waiting for the connection to respond, and analyzing the response.
- Increase system complexity: Reverse proxy is often used for horizontal expansion of distributed applications. However, the reverse proxy service has the following problems. To solve the following problems, additional complexity and operation and maintenance costs will be added to the system as a whole:
-
If the reverse proxy service breaks down, the site cannot be accessed. Therefore, a high availability solution is required. The common solutions are active/standby mode (one active/standby mode) and two active/standby mode (mutual active/standby mode).
-
Reverse proxy services also have performance bottlenecks of their own, requiring scalable solutions as the volume of requests to forward continues to rise.
2.2.4 IP load Balancing
IP load balancing is performed at the network layer by changing the destination address of the request.
As shown in the figure above, the IP balancing process is roughly as follows:
The client requests 192.168.137.10 and the load balancing server receives the packet.
The load balancing server selects a service node 192.168.0.1 based on the algorithm and changes the packet request address to the IP address of this node.
The real service node receives the request packet, processes it, and sends the response data to the load balancing server.
The load balancing server changes the source IP address of the response data to the IP address of the load balancing server and returns it to the client.
IP load balancing completes data distribution in the kernel process and has better secondary processing performance than reverse proxy load balancing. However, since all requests and responses pass through the load balancing server, the throughput of the cluster is limited by the bandwidth of the load balancing server.
2.2.5 Load balancing at the data link layer
Load balancing at the data link layer Refers to load balancing by modifying MAC addresses at the data link layer of communication protocols.
The best open source link-layer load balancing product on The Linux platform is Linux Virtual Server (LVS). LVS is a load balancing system based on NetFilter framework in Linux kernel. Netfilter is a kernel-mode Linux firewall mechanism, which can set several levels (hook functions) according to the rules to perform related operations in the process of packets flowing through.
The workflow of LVS is as follows:
When a user accesses www.sina.com.cn, the user data enters the NETWORK adapter of the LVS server through the layer-layer network, and finally enters the kernel network layer through the switch.
After entering PREROUTING, route lookups confirm that the destination VIP is the local IP address, so the packet goes to the INPUT chain
IPVS is working on the INPUT chain. It will determine whether the request is IPVS service according to the VIP +port accessed. If so, it will call the registered IPVS HOOK function, carry out the ipvS-related main process, and forcibly modify the data related to the data packet. And send the packet to the POSTROUTING chain.
After receiving a packet on POSTROUTING, the packet is sent to the back-end server through route selection according to the destination IP address (back-end server).
The open source LVS version has three working modes, and each mode has its own advantages and disadvantages, which are suitable for different application scenarios. However, the essence of the final function is to achieve balanced traffic scheduling and good scalability. There are three modes: DR mode, NAT mode, and Tunnel mode.
3. Load balancing algorithm
The implementation of a 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 core. There are various load balancing products, but the principle of various load balancing algorithms is common. There are many kinds of load balancing algorithms, which are applicable to different application scenarios. This paper introduces only the features and principles of the most common load balancing algorithms: polling, random, minimum active number, source address hash, and consistent hash.
Note: the implementation of the load balancing algorithm, it is recommended to read Dubbo official load balancing algorithm description, the source code is very detailed, it is worth referencing.
3.1 random
3.1.1 Random algorithm
The Random algorithm randomly distributes requests to candidate servers.
Random algorithms are suitable for scenarios where the server hardware is identical. Those who have studied probability theory know that the load may not be uniform when the amount of modulation is small. The more the amount of modulation, the more the load is balanced.
Example A random algorithm implementation example
Load balancing interface
public interface LoadBalance<N extends Node> {
N select(List<N> nodes, String ip);
}
Copy the codeLoad 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 there is only one node in the Nodes list, return the node directly without load balancing
if (nodes.size() == 1) {
return nodes.get(0);
}
return doSelect(nodes, ip);
}
protected abstract N doSelect(List<N> nodes, String ip);
}
Copy the codeServer node class
public class Node implements Comparable<Node> {
protected String url;
protected Integer weight;
protected Integer active;
// ...
}
Copy the codeRandom 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) {
// Select a node at random from the list
int index = random.nextInt(nodes.size());
returnnodes.get(index); }}Copy the code3.1.2 Weighted stochastic algorithm
Weighted Rando****m (Weighted Rando**** M) algorithm adjusts the weight according to the probability and distributes the load based on the stochastic 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 (N node : nodes) {
// Offset the random value minus the weight value
offset -= node.getWeight();
if (offset < 0) {
// Return the corresponding Node
returnnode; }}}// Return one randomly
returnnodes.get(random.nextInt(length)); }}Copy the code3.2 the polling
3.2.1 Polling Algorithm
The strategy of the Round Robin algorithm is to distribute requests to candidate servers in turn.
As shown in the figure below, the load balancer receives six requests from the client. (1, 3, 5) requests are sent to server 1 and (2, 4, 6) requests 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 is not different. If there is a large difference, the slower-processing server may backlog and end up unable to handle the load.
Example Example of a polling algorithm
Implement the polling load balancing algorithm
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();
returnnode; }}Copy the code3.2.2 Weighted polling algorithm
** Weighted Round Robbin ** algorithm on the basis of the polling algorithm, the weight attribute is added to adjust the number of requests of the forwarding server. Nodes with high performance and fast processing speed should have higher weights, so that requests are preferentially distributed to nodes with higher weights.
As shown in the figure below, if server A is set to weight 5 and server B is set to weight 1, the load balancer receives 6 requests from the client, then (1, 2, 3, 4, 5) requests will be sent to server A and (6) requests will be sent to server B.
[Example] Example of the weighted polling algorithm
The following implementation makes some simplifications based on the Dubbo weighted polling algorithm.
public class WeightRoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
/** * 60 seconds */
private static final int RECYCLE_PERIOD = 60000;
/** * Mapping Node hashcode to WeightedRoundRobin */
private ConcurrentMap<Integer, WeightedRoundRobin> weightMap = new ConcurrentHashMap<>();
/** * Atomic update lock */
private AtomicBoolean 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 several things:
// 1. Check whether the current Node has a WeightedRoundRobin. If not, create a WeightedRoundRobin
// 2. Check whether the Node weight changes. If yes, update the weight field of WeightedRoundRobin
// 3. Add weight to current field, equivalent to current += weight
// 4. Set the lastUpdate field, lastUpdate = now
// 5. Find the Node with the largest current and the corresponding WeightedRoundRobin,
// Save it for later
// 6. Calculate the sum of weights
for (N node : nodes) {
int hashCode = node.hashCode();
WeightedRoundRobin weightedRoundRobin = weightMap.get(hashCode);
int weight = node.getWeight();
if (weight < 0) {
weight = 0;
}
// Check whether the current Node has a WeightedRoundRobin. If not, create a WeightedRoundRobin
if (weightedRoundRobin == null) {
weightedRoundRobin = new WeightedRoundRobin();
// Set Node weight
weightedRoundRobin.setWeight(weight);
// Store the mapping that the URL uniquely identifies identifyString to weightedRoundRobin
weightMap.putIfAbsent(hashCode, weightedRoundRobin);
weightedRoundRobin = weightMap.get(hashCode);
}
// If the Node weight is not equal to the weight stored in WeightedRoundRobin, it indicates that the weight has changed
if(weight ! = weightedRoundRobin.getWeight()) { weightedRoundRobin.setWeight(weight); }// Add weight to current += weight
long current = weightedRoundRobin.increaseCurrent();
// Set lastUpdate to indicate recent update
weightedRoundRobin.setLastUpdate(now);
// Find the maximum current
if (current > maxCurrent) {
maxCurrent = current;
// Assign the Node with the maximum current weight to selectedNode
selectedNode = node;
// Assign selectedWRR to weightedRoundRobin for later use
selectedWRR = weightedRoundRobin;
}
// Calculate the sum of weights
totalWeight += weight;
}
// Check the weightMap to filter out nodes that have not been updated for a long time.
// The node may have died. Nodes does not contain this node, so the lastUpdate of this node cannot be updated for a long time.
// If the update duration exceeds the threshold, it is removed. The default threshold is 60 seconds.
if(! updateLock.get() && nodes.size() ! = weightMap.size()) {if (updateLock.compareAndSet(false.true)) {
try {
// Iterate over changes, that is, remove expired records
weightMap.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
} finally {
updateLock.set(false); }}}if(selectedNode ! =null) {
// Current -= totalWeight
selectedWRR.decreaseCurrent(totalWeight);
// Return the Node with the largest current
return selectedNode;
}
// should not happen here
return nodes.get(0);
}
protected static class WeightedRoundRobin {
// Service provider weights
private int weight;
// The current weight
private AtomicLong current = new AtomicLong(0);
// Last update time
private long lastUpdate;
public long increaseCurrent(a) {
// current = current + weight;
return current.addAndGet(weight);
}
public long decreaseCurrent(int total) {
// current = current - total;
return current.addAndGet(-1 * total);
}
public int getWeight(a) {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
// Current = 0
current.set(0);
}
public AtomicLong getCurrent(a) {
return current;
}
public void setCurrent(AtomicLong current) {
this.current = current;
}
public long getLastUpdate(a) {
return lastUpdate;
}
public void setLastUpdate(long lastUpdate) {
this.lastUpdate = lastUpdate; }}}Copy the code3.3 Minimum Active number
The Least Active algorithm distributes requests to the candidate server with the fewest connections/requests (the server currently processing the fewest requests).
-
Characteristics: Dynamic allocation based on the number of connections currently requested by the candidate server.
-
Scenario: Applicable to scenarios that are sensitive to system load or request connection time difference is large.
Because the connection duration of each request is different, if simple round-robin or random algorithms are used, some servers may have too many connections while others have too few, resulting in load imbalance. Although either the polling or the algorithm can adjust the load by weighting the weight attribute, the weighting method is difficult to cope with dynamic changes.
For example, in the figure below, (1, 3, 5) requests are sent to server 1, but (1, 3) is quickly disconnected, and only (5) requests to connect to server 1. (2, 4, 6) the request was sent to server 2, and only (2) was disconnected. While the system continues to run, server 2 is overloaded.
The minimum active number algorithm will record the number of connections that each candidate node is processing at the current moment, and then select the node with the smallest number of connections. This policy can reflect the current status of the server dynamically and in real time. It is suitable for scenarios that are sensitive to the current system load.
For example, in the figure below, server 1 has the smallest number of connections, so the incoming request 6 will be sent to server 1.
Weighted Least Connection Based on the minimum number of active servers, the system assigns weights to each server based on the server performance, and then calculates the number of connections that each server can process based on the weights.
Implementation points of the minimum active number algorithm: The smaller the number of active calls is, the higher the processing capacity of the service node is, and more requests can be processed per unit time, so the requests should be distributed to the service first. In the implementation, each service node corresponds to an active number, active. The initial number of active service providers is 0. Each time a request is received, the number of active requests is increased by one, and when the request is completed, the number of active requests is decreased by one. 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 a 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 is based on the Dubbo minimum active number load balancing algorithm with some changes.
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();
// Minimum active number
int leastActive = -1;
// The number of server providers (hereinafter called nodes) with the same "minimum active number"
int leastCount = 0;
// leastIndexs is used to record subindices of nodes with the same "minimum active number" in the nodes list
int[] leastIndexs = new int[length];
int totalWeight = 0;
// The weight of the first Node with the same minimum active number is used to compare the weight of other nodes with the same minimum active number.
// To check whether all nodes with the same minimum number of active nodes are equally weighted
int firstWeight = 0;
boolean sameWeight = true;
// Iterate through the Nodes list
for (int i = 0; i < length; i++) {
N node = nodes.get(i);
// Find a smaller number of activities and start again
if (leastActive == -1 || node.getActive() < leastActive) {
// Update the minimum active count leastActive with the current active count
leastActive = node.getActive();
// Update leastCount to 1
leastCount = 1;
// Record the current subtab value in leastIndexs
leastIndexs[0] = i;
totalWeight = node.getWeight();
firstWeight = node.getWeight();
sameWeight = true;
Node.getactive () is the same as leastActive
} else if (node.getActive() == leastActive) {
// Record the subscript of the current Node in the Nodes collection in leastIndexs
leastIndexs[leastCount++] = i;
// Add weights
totalWeight += node.getWeight();
// Check whether the current Node weight is equal to firstWeight,
If sameWeight is not equal, set sameWeight to false
if (sameWeight && i > 0&& node.getWeight() ! = firstWeight) { sameWeight =false; }}}// If only one Node has the minimum number of active nodes, return that Node directly
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) {
// Generate a random number between [0, totalWeight]
int offsetWeight = random.nextInt(totalWeight);
// Loop the random number minus the weight of the Node with the smallest active number,
// If offset is less than or equal to 0, the Node is returned
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexs[i];
// Get the weight value and subtract the weight value from the random number
offsetWeight -= nodes.get(leastIndex).getWeight();
if (offsetWeight <= 0) {
returnnodes.get(leastIndex); }}}// If the weights are the same or 0, return a random Node
returnnodes.get(leastIndexs[random.nextInt(leastCount)]); }}Copy the code3.4 Source address hashing
The IP Hash algorithm hashes a value based on the source IP address of the request and modulo the list of candidate servers using this value to obtain the selected server.
You can ensure that the request from the client with the same IP address will be forwarded to the same server, which is used to implement Sticky Session.
Features: Ensure that a specific user always sends requests to the same server. If the server goes 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) {
returnHashUtil.fnvHash(text); }}Copy the code3.5 Consistent Hashing
The goal of a Consistent Hash algorithm is that the same requests end up on the same server as much as possible.
Consistent hashing is a good solution to stability problems. You can arrange all storage nodes in a Hash ring that is connected from end to end. After calculating the Hash, each key will find the nearest storage node clockwise for storage. When a node joins or exits, only subsequent nodes that are clockwise adjacent to the node on the Hash ring are affected.
1) The same request is a request that specifies a key to be used for hash computation.
The user ID
The requester IP
Request service name, parameter list consisting of a string
2) As far as possible means: the server may go offline, a few server changes should not affect the majority of requests.
When a candidate server goes down, the requests originally sent to the server will be amortized to other candidate servers based on virtual nodes, without any drastic changes.
Advantage: Adding or deleting a node affects only the adjacent nodes in the clockwise direction of the hash ring.
Disadvantages: Adding or subtracting nodes will cause some data in the hash ring to fail to be hit. When using a small number of nodes, node changes will affect the data mapping in the hash ring in a large range, which is not suitable for the distributed scheme with a small number of data nodes. A common consistent hash partition doubles or halves the number of nodes to balance data and load.
Note: Because of these disadvantages of consistent hash partitioning, some distributed systems use virtual slots to improve consistent hash, such as Dynamo systems.
Example Consistent hash algorithm example
public class ConsistentHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
private finalConcurrentMap<String, ConsistentHashSelector<? >> selectors =new ConcurrentHashMap<>();
@SuppressWarnings("unchecked")
@Override
protected N doSelect(List<N> nodes, String ip) {
// Set the number of fragments to 4 times the number of nodes
Integer replicaNum = nodes.size() * 4;
// Get the original Hashcode of nodes
int identityHashCode = System.identityHashCode(nodes);
// If nodes is a new List object, it means that the number of nodes has changed
/ / at this point the selector identityHashCode! = identityHashCode
ConsistentHashSelector<N> selector = (ConsistentHashSelector<N>) selectors.get(ip);
if (selector == null|| selector.identityHashCode ! = identityHashCode) {// Create a new ConsistentHashSelector
selectors.put(ip, new ConsistentHashSelector<>(nodes, identityHashCode, replicaNum));
selector = (ConsistentHashSelector<N>) selectors.get(ip);
}
// Call the select method of ConsistentHashSelector to select Node
return selector.select(ip);
}
/** * Consistent hash selector */
private static final class ConsistentHashSelector<N extends Node> {
/** * Storage virtual node */
private final TreeMap<Long, N> virtualNodes;
private final int identityHashCode;
/** * constructor **@paramNodes Node list *@param identityHashCode hashcode
* @paramReplicaNum Number of fragments */
ConsistentHashSelector(List<N> nodes, int identityHashCode, Integer replicaNum) {
this.virtualNodes = new TreeMap<>();
this.identityHashCode = identityHashCode;
// Obtain the number of virtual nodes. The default value is 100
if (replicaNum == null) {
replicaNum = 100;
}
for (N node : nodes) {
for (int i = 0; i < replicaNum / 4; i++) {
// Run md5 on the URL to get a byte array of length 16
byte[] digest = md5(node.getUrl());
// Hash some bytes of digest four times to get four different positive long integers
for (int j = 0; j < 4; j++) {
// If h = 0, the 4 bytes with the subscript from 0 to 3 in digest are used for bit operation
// If h = 1, the four bytes with the subscript from 4 to 7 in digest are used for bit operation
// When h = 2 and h = 3, the process is the same as above
long m = hash(digest, j);
// Store the hash to Node mapping in virtualNodes,
// virtualNodes needs to provide efficient query operations, so TreeMap is selected as the storage structurevirtualNodes.put(m, node); }}}}public N select(String key) {
// Perform MD5 calculation on the parameter key
byte[] digest = md5(key);
// Hash the first four bytes of the digest array and pass the hash value to the selectForKey method.
// Find the right Node
return selectForKey(hash(digest, 0));
}
private N selectForKey(long hash) {
// Find the first node that is greater than or equal to the current hash
Map.Entry<Long, N> entry = virtualNodes.ceilingEntry(hash);
// If the hash is greater than the maximum location of the Node on the hashing ring, then entry = null,
// The header node of the TreeMap needs to be assigned to the entry
if (entry == null) {
entry = virtualNodes.firstEntry();
}
/ / returns the Node
returnentry.getValue(); }}/** * Compute the hash value */
public static long hash(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;
}
/** * Calculate the MD5 value */
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);
returnmd5.digest(); }}Copy the codeThe above example is based on Dubbo’s consistent hash load balancing algorithm with some simplification.
Iv. Reference materials
1. Comparing Load Balancing Algorithms
2. Technical Architecture for Large Web Sites: Core Principles and Case Studies
3. Large Web Architecture Series: Load Balancing in Detail (1)
4. What is load balancing
5. What Is Load Balancing
6. Description of the Dubbo official load balancing algorithm
7. Load balancing algorithm and means
8. Use DNS resolution to realize load balancing of websites
Author: Zhang Peng, Vivo Internet Team