Welcome to pay attention to the public account “JAVA Front” to view more wonderful sharing articles, mainly including source code analysis, practical application, architecture thinking, workplace sharing, product thinking and so on, at the same time, welcome to add my personal wechat “JAVA_front” to communicate and learn together
1 Three groups of concepts
Load balancing, cluster fault tolerance, and service degradation are important concepts in DUBBO, as are other distributed frameworks that have the same or similar concepts.
From the perspective of call sequence analysis, the call sequence is load balancing, cluster fault tolerance, service degradation. From the perspective of problem solving, load balancing solves the problem of “which one to choose”, cluster fault tolerance solves the problem of “which one to change”, and service degradation solves the problem of “how to do everything wrong”.
Suppose there is a service consumer facing 10 providers, then the first problem is “which one to choose” to call, so the load balance is called first, suppose the service provider number 5 is selected to call the service.
Suppose the consumer calls the number 5 provider with a timeout exception, and then faces the second question of “which one” to call: should the number 5 timeout be changed to number 1 to try, or simply return without retry, so the cluster is fault-tolerant of the second call.
Suppose that providers 1, 3, and 6 have all timed out, and then face the third question of “What about all errors?”, then you can directly return a fixed value or prompt text, so the service degrades the third call.
Load balancing is very important as the first node of the whole call link. This paper analyzes the following seven load balancing strategies based on DUBBO source code:
- Simple random
- A weighted random
- A simple polling
- Simple weighted polling
- Smooth weighted polling
- Consistency hashing
- Minimum active number
2 Simple random
Simple randomness means that service consumers will access any service provider at a time, and from the perspective of probability, each provider will be accessed with the same probability, which can be achieved by specifying range random number. The first step is to write the server code
public class MyServer {
private String ip;
public MyServer(String ip) {
this.ip = ip;
}
public String getIp(a) {
return ip;
}
public void setIp(String ip) {
this.ip = ip; }}Copy the code
The second step is to write basic load balancing policies. Other policies can be reused
public abstract class AbstractLoadBalance {
public MyServer select(List<MyServer> serverList) {
return doSelect(serverList);
}
public abstract MyServer doSelect(List<MyServer> serverList);
}
Copy the code
Step 3 write a simple random strategy
public class RandomBalance extends AbstractLoadBalance {
@Override
public MyServer doSelect(List<MyServer> serverList) {
// Random number range [0,serverListSize]
int index = ThreadLocalRandom.current().nextInt(serverList.size());
returnserverList.get(index); }}Copy the code
Step 4 write the test code
public class LoadBalanceTest {
public static void main(String[] args) {
List<MyServer> serverList = buildData();
testRandomBalance(serverList);
}
public static void testRandomBalance(List<MyServer> serverList) {
AbstractLoadBalance randomBalance = new RandomBalance();
for (int i = 0; i < 10; i++) {
MyServer server = randomBalance.select(serverList);
System.out.println("RandomBalance route server="+ server); }}public static List<MyServer> buildData(a) {
List<MyServer> serverList = new ArrayList<MyServer>();
MyServer server1 = new MyServer("192.1.1.1");
MyServer server2 = new MyServer("192.1.1.2");
MyServer server3 = new MyServer("192.1.1.3");
serverList.add(server1);
serverList.add(server2);
serverList.add(server3);
returnserverList; }}Copy the code
The fifth step output results, the more cycles the more accurate the results
RandomBalance Route Server =MyServer(IP =192.1.1.2) RandomBalance Route Server =MyServer(IP =192.1.1.1) RandomBalance Route Server =MyServer(IP =192.1.1.3) RandomBalance Route Server =MyServer(IP =192.1.1.2) RandomBalance Route Server =MyServer(IP =192.1.1.1) RandomBalance Route Server =MyServer(IP =192.1.1.1) RandomBalance Route Server =MyServer(IP =192.1.1.2) RandomBalance Route Server =MyServer(IP =192.1.1.2) RandomBalance Route IP server = MyServer (= 192.1.1.3) RandomBalance route server = MyServer (IP = 192.1.1.3)Copy the code
3 Weighted random
3.1 Design Roadmap
The concept of weighting is added randomly. Assuming that the weight of server A is equal to 1 and that of server B is equal to 5, the probability of server B being accessed is 5 times higher than that of server A. There are many ways to implement access by weight, and we chose to use the idea of probability interval.
Suppose there are three servers, with weights of 3, 5 and 2 respectively, then the three constitute the probability interval as shown in the figure below:
The calculation steps of probability interval are as follows:
3.2 Code Examples
The first step is to write the server code
public class MyServer {
private String ip;
private int weight;
public MyServer(String ip) {
this.ip = ip;
}
public String getIp(a) {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public int getWeight(a) {
return weight;
}
public void setWeight(int weight) {
this.weight = weight; }}Copy the code
The second step is to write a weighted random strategy
public class RandomWeightBalance extends AbstractLoadBalance {
@Override
public MyServer doSelect(List<MyServer> serverList) {
// Total weight of all servers
int totalWeight = 0;
// The first server weight
int firstWeight = serverList.get(0).getWeight();
// All servers have equal weight
boolean sameWeight = true;
// Traverse all servers
for (MyServer server : serverList) {
// Calculate the total weight
totalWeight += server.getWeight();
// If any invoker weight is not equal to the first weight, set sameWeight=false
if(sameWeight && server.getWeight() ! = firstWeight) { sameWeight =false; }}// If the weights are not equal, select according to the weights
if(! sameWeight) {// Generate A random number in the total interval range [0,totalWeight]
Integer offset = ThreadLocalRandom.current().nextInt(totalWeight);
// Traverses all server ranges
for (MyServer server : serverList) {
// If A is in the server range, return it directly
if (offset < server.getWeight()) {
return server;
}
// If A is not in the server range subtract this range and continue to match other rangesoffset -= server.getWeight(); }}// All servers with equal weight will be randomly selected
returnserverList.get(ThreadLocalRandom.current().nextInt(serverList.size())); }}Copy the code
Step 3 write the test code
public class LoadBalanceTest {
public static void main(String[] args) {
List<MyServer> serverList = buildData();
testRandomWeightBalance(serverList);
}
public static void testRandomWeightBalance(List<MyServer> serverList) {
AbstractLoadBalance randomBalance = new RandomWeightBalance();
for (int i = 0; i < 10; i++) {
MyServer server = randomBalance.select(serverList);
System.out.println("RandomWeightBalance route server="+ server); }}public static List<MyServer> buildData(a) {
List<MyServer> serverList = new ArrayList<MyServer>();
MyServer server1 = new MyServer("192.1.1.1".3);
MyServer server2 = new MyServer("192.1.1.2".5);
MyServer server3 = new MyServer("192.1.1.3".2);
serverList.add(server1);
serverList.add(server2);
serverList.add(server3);
returnserverList; }}Copy the code
The fourth step output results, the more cycles the more accurate the results
RandomWeightBalance route server = MyServer (IP = 192.1.1.2, Weight = 2) RandomWeightBalance route server = MyServer (IP = 192.1.1.2, Weight = 3) RandomWeightBalance route server = MyServer (IP = 192.1.1.1, Weight = 3) RandomWeightBalance route server = MyServer (IP = 192.1.1.1, Weight = 3) RandomWeightBalance route server = MyServer (IP = 192.1.1.3, Weight = 2) RandomWeightBalance route server = MyServer (IP = 192.1.1.3, Weight = 2) RandomWeightBalance route server = MyServer (IP = 192.1.1.2, Weight = 5) RandomWeightBalance route server = MyServer (IP = 192.1.1.1, Weight = 3) RandomWeightBalance route server = MyServer (IP = 192.1.1.2, Weight =5) randomBalance Route Server =MyServer(IP =192.1.1.2, weight=5)Copy the code
3.3 DUBBO source
public class RandomLoadBalance extends AbstractLoadBalance {
public static final String NAME = "random";
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
/ / number of invoker
int length = invokers.size();
// Whether the ownership weights are equal
boolean sameWeight = true;
// Weight array
int[] weights = new int[length];
// The first weight
int firstWeight = getWeight(invokers.get(0), invocation);
weights[0] = firstWeight;
// Sum of weights
int totalWeight = firstWeight;
// Iterate over all invokers
for (int i = 1; i < length; i++) {
// Get the weight
int weight = getWeight(invokers.get(i), invocation);
weights[i] = weight;
// Calculate the total weight
totalWeight += weight;
// If any invoker weight is not equal to the first weight, set sameWeight=false
if(sameWeight && weight ! = firstWeight) { sameWeight =false; }}// If the weights are not equal, select according to the weights
if (totalWeight > 0 && !sameWeight) {
int offset = ThreadLocalRandom.current().nextInt(totalWeight);
for (int i = 0; i < length; i++) {
offset -= weights[i];
if (offset < 0) {
returninvokers.get(i); }}}// All services with equal weight are randomly selected
returninvokers.get(ThreadLocalRandom.current().nextInt(length)); }}Copy the code
4 Simple polling
Simple polling means that service consumers will visit one service provider at a time, and each provider will be accessed with the same probability from the perspective of probability, which can be achieved by adding atomic variables. The first step is to write a simple polling strategy
public class RoundRobinBalance extends AbstractLoadBalance {
private AtomicInteger atomicIndex = new AtomicInteger(0);
@Override
public MyServer doSelect(List<MyServer> serverList) {
// atomicIndex residuals when the number of servers increases
int index = atomicIndex.getAndIncrement() % serverList.size();
returnserverList.get(index); }}Copy the code
The second step is to write test code
public class LoadBalanceTest {
public static void main(String[] args) {
List<MyServer> serverList = buildData();
testRoundRobinBalance(serverList);
}
public static void testRoundRobinBalance(List<MyServer> serverList) {
AbstractLoadBalance roundRobinBalance = new RoundRobinBalance();
for (int i = 0; i < 10; i++) {
MyServer server = roundRobinBalance.select(serverList);
System.out.println("RoundRobinBalance route server="+ server); }}public static List<MyServer> buildData(a) {
List<MyServer> serverList = new ArrayList<MyServer>();
MyServer server1 = new MyServer("192.1.1.1");
MyServer server2 = new MyServer("192.1.1.2");
MyServer server3 = new MyServer("192.1.1.3");
serverList.add(server1);
serverList.add(server2);
serverList.add(server3);
returnserverList; }}Copy the code
The third step is to output the results
RoundRobinBalance Route Server =MyServer(IP =192.1.1.1) RoundRobinBalance Route Server =MyServer(IP =192.1.1.2) RoundRobinBalance Route Server =MyServer(IP =192.1.1.3) RoundRobinBalance Route Server =MyServer(IP =192.1.1.1) RoundRobinBalance Route Server =MyServer(IP =192.1.1.2) RoundRobinBalance Route Server =MyServer(IP =192.1.1.3) RoundRobinBalance Route Server =MyServer(IP =192.1.1.1) RoundRobinBalance Route Server =MyServer(IP =192.1.1.2) RoundRobinBalance Route Server =MyServer(IP =192.1.1.3) RoundRobinBalance Route Server =MyServer(IP =192.1.1.1)Copy the code
5 Simple weighted polling
It is assumed that the weight of server A is equal to 1 and the weight of server B is equal to 5. From the perspective of probability, the probability of server B being visited is 5 times higher than that of server A. We still use the idea of probability interval.
The first step is to write a simple weighted polling strategy
public class RoundRobinWeightBalance1 extends AbstractLoadBalance {
private AtomicInteger atomicIndex = new AtomicInteger(0);
@Override
public MyServer doSelect(List<MyServer> serverList) {
int totalWeight = 0;
int firstWeight = serverList.get(0).getWeight();
boolean sameWeight = true;
for (MyServer server : serverList) {
totalWeight += server.getWeight();
if(sameWeight && server.getWeight() ! = firstWeight) { sameWeight =false; }}if(! sameWeight) {// Calculate offset in auto-increment mode
int offset = atomicIndex.getAndIncrement() % totalWeight;
for (MyServer server : serverList) {
if (offset < server.getWeight()) {
returnserver; } offset -= server.getWeight(); }}int index = atomicIndex.getAndIncrement() % serverList.size();
returnserverList.get(index); }}Copy the code
The second step is to write test code
public class LoadBalanceTest {
public static void main(String[] args) {
List<MyServer> serverList = buildData();
testRoundRobinWeightBalance1(serverList);
}
public static void testRoundRobinWeightBalance1(List<MyServer> serverList) {
AbstractLoadBalance roundRobinBalance = new RoundRobinWeightBalance1();
for (int i = 0; i < 10; i++) {
MyServer server = roundRobinBalance.select(serverList);
System.out.println("RoundRobinWeightBalance1 route server="+ server); }}public static List<MyServer> buildData(a) {
List<MyServer> serverList = new ArrayList<MyServer>();
MyServer server1 = new MyServer("192.1.1.1".3);
MyServer server2 = new MyServer("192.1.1.2".5);
MyServer server3 = new MyServer("192.1.1.3".2);
serverList.add(server1);
serverList.add(server2);
serverList.add(server3);
returnserverList; }}Copy the code
The third step is to output the results
RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.1, Weight = 3) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.1, Weight = 3) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.1, Weight = 3) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.2, Weight = 5) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.2, Weight = 5) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.2, Weight = 5) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.2, Weight = 5) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.2, Weight = 5) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.3, RoundRobinWeightBalance1 route server=MyServer(IP =192.1.1.3, weight=2) RoundRobinWeightBalance1 route server=MyServer(IP =192.1.1.3, weight=2)Copy the code
6 Smooth weighted polling
6.1 Design Roadmap
What’s wrong with simple weighted polling? We analyzed the output and found that three consecutive accesses to server 1, five consecutive accesses to server 2, and two consecutive accesses to server 3, so a simple weighted polling strategy would result in request concentration problems.
RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.1, Weight = 3) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.1, Weight = 3) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.1, Weight = 3) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.2, Weight = 5) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.2, Weight = 5) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.2, Weight = 5) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.2, Weight = 5) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.2, Weight = 5) RoundRobinWeightBalance1 route server = MyServer (IP = 192.1.1.3, RoundRobinWeightBalance1 route server=MyServer(IP =192.1.1.3, weight=2) RoundRobinWeightBalance1 route server=MyServer(IP =192.1.1.3, weight=2)Copy the code
Therefore, the smooth-weighted polling strategy is used to evenly distribute requests to each server. The calculation procedure is as follows:
6.2 Code Examples
The first step is to write the server code
public class MyServer {
private String ip;
private int weight;
private int currentWeight = 0;
public MyServer(String ip) {
this.ip = ip;
}
public MyServer(String ip, int weight) {
this.ip = ip;
this.weight = weight;
}
public int getWeight(a) {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getCurrentWeight(a) {
return currentWeight;
}
public void setCurrentWeight(int currentWeight) {
this.currentWeight = currentWeight;
}
public String getIp(a) {
return ip;
}
public void setIp(String ip) {
this.ip = ip; }}Copy the code
The second step is to write a smooth weighted polling strategy
public class RoundRobinWeightBalance2 extends AbstractLoadBalance {
private AtomicInteger atomicIndex = new AtomicInteger(0);
@Override
public MyServer doSelect(List<MyServer> serverList) {
int totalWeight = 0;
int firstWeight = serverList.get(0).getWeight();
boolean sameWeight = true;
for (MyServer server : serverList) {
totalWeight += server.getWeight();
if(sameWeight && server.getWeight() ! = firstWeight) { sameWeight =false;
}
// Set dynamic weight -> currentWeight += weight
server.setCurrentWeight(server.getCurrentWeight() + server.getWeight());
}
if(! sameWeight) {// maximum dynamic weight server -> Max (currentWeight)
MyServer maxCurrentWeightServer = serverList.stream().max((s1, s2) -> s1.getCurrentWeight() - s2.getCurrentWeight()).get();
// Set the maximum dynamic weight -> Max (currentWeight) - totalWeight
maxCurrentWeightServer.setCurrentWeight(maxCurrentWeightServer.getCurrentWeight() - totalWeight);
// Returns the maximum dynamic weight server
return maxCurrentWeightServer;
}
// Polling in order with the same weight
int index = atomicIndex.getAndIncrement() % serverList.size();
returnserverList.get(index); }}Copy the code
Step 3 write the test code
public class LoadBalanceTest {
public static void main(String[] args) {
List<MyServer> serverList = buildData();
testRoundRobinWeightBalance2(serverList);
}
public static void testRoundRobinWeightBalance2(List<MyServer> serverList) {
AbstractLoadBalance roundRobinBalance = new RoundRobinWeightBalance2();
for (int i = 0; i < 10; i++) {
MyServer server = roundRobinBalance.select(serverList);
System.out.println("RoundRobinWeightBalance2 route server="+ server); }}public static List<MyServer> buildData(a) {
List<MyServer> serverList = new ArrayList<MyServer>();
MyServer server1 = new MyServer("192.1.1.1".3);
MyServer server2 = new MyServer("192.1.1.2".5);
MyServer server3 = new MyServer("192.1.1.3".2);
serverList.add(server1);
serverList.add(server2);
serverList.add(server3);
returnserverList; }}Copy the code
Step 4 Output the results
RoundRobinWeightBalance2 route server = MyServer (IP = 192.1.1.2, weight = 5, CurrentWeight =-5) RoundRobinWeightBalance2 Route server=MyServer(IP =192.1.1.1, weight=3, CurrentWeight = 4) RoundRobinWeightBalance2 Route server=MyServer(IP =192.1.1.3, weight=2, CurrentWeight = 4) RoundRobinWeightBalance2 Route server=MyServer(IP =192.1.1.2, weight=5, CurrentWeight =0) RoundRobinWeightBalance2 Route server=MyServer(IP =192.1.1.1, weight=3, CurrentWeight =-5) RoundRobinWeightBalance2 Route server=MyServer(IP =192.1.1.2, weight=5, CurrentWeight =0) RoundRobinWeightBalance2 Route server=MyServer(IP =192.1.1.2, weight=5, RoundRobinWeightBalance2 Route server=MyServer(IP =192.1.1.3, weight=2, CurrentWeight = 4) RoundRobinWeightBalance2 Route server=MyServer(IP =192.1.1.1, weight=3, RoundRobinWeightBalance2 Route Server =MyServer(IP =192.1.1.2, weight=5, currentWeight=0) RoundRobinWeightBalance2 route Server =MyServer(IP =192.1.1.2, weight=5, currentWeight=0)Copy the code
6.3 DUBBO source
public class RoundRobinLoadBalance extends AbstractLoadBalance {
public static final String NAME = "roundrobin";
private static int RECYCLE_PERIOD = 60000;
protected static class WeightedRoundRobin {
/ / weight
private int weight;
// Dynamic weight
private AtomicLong current = new AtomicLong(0);
// Update time
private long lastUpdate;
public int getWeight(a) {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
current.set(0);
}
public long increaseCurrent(a) {
return current.addAndGet(weight);
}
public void sel(int total) {
current.addAndGet(-1 * total);
}
public long getLastUpdate(a) {
return lastUpdate;
}
public void setLastUpdate(long lastUpdate) {
this.lastUpdate = lastUpdate; }}private ConcurrentMap<String, ConcurrentMap<String, WeightedRoundRobin>> methodWeightMap = new ConcurrentHashMap<String, ConcurrentMap<String, WeightedRoundRobin>>();
private AtomicBoolean updateLock = new AtomicBoolean();
protected <T> Collection<String> getInvokerAddrList(List<Invoker<T>> invokers, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
Map<String, WeightedRoundRobin> map = methodWeightMap.get(key);
if(map ! =null) {
return map.keySet();
}
return null;
}
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
ConcurrentMap<String, WeightedRoundRobin> map = methodWeightMap.get(key);
if (map == null) {
methodWeightMap.putIfAbsent(key, new ConcurrentHashMap<String, WeightedRoundRobin>());
map = methodWeightMap.get(key);
}
/ / total weight
int totalWeight = 0;
// Maximum current weight
long maxCurrent = Long.MIN_VALUE;
// The current time
long now = System.currentTimeMillis();
// Select the provider
Invoker<T> selectedInvoker = null;
// Select the provider weight object
WeightedRoundRobin selectedWRR = null;
// Walk through all the providers
for (Invoker<T> invoker : invokers) {
String identifyString = invoker.getUrl().toIdentityString();
WeightedRoundRobin weightedRoundRobin = map.get(identifyString);
// Get the weight
int weight = getWeight(invoker, invocation);
if (weightedRoundRobin == null) {
weightedRoundRobin = new WeightedRoundRobin();
weightedRoundRobin.setWeight(weight);
map.putIfAbsent(identifyString, weightedRoundRobin);
}
if(weight ! = weightedRoundRobin.getWeight()) { weightedRoundRobin.setWeight(weight); }// Select the dynamic weight maximum provider
long cur = weightedRoundRobin.increaseCurrent();
weightedRoundRobin.setLastUpdate(now);
if (cur > maxCurrent) {
maxCurrent = cur;
selectedInvoker = invoker;
selectedWRR = weightedRoundRobin;
}
// Calculate the total weight
totalWeight += weight;
}
// Update the load balancing container
if(! updateLock.get() && invokers.size() ! = map.size()) {if (updateLock.compareAndSet(false.true)) {
try {
ConcurrentMap<String, WeightedRoundRobin> newMap = new ConcurrentHashMap<String, WeightedRoundRobin>();
newMap.putAll(map);
Iterator<Entry<String, WeightedRoundRobin>> it = newMap.entrySet().iterator();
while (it.hasNext()) {
Entry<String, WeightedRoundRobin> item = it.next();
if (now - item.getValue().getLastUpdate() > RECYCLE_PERIOD) {
it.remove();
}
}
methodWeightMap.put(key, newMap);
} finally {
updateLock.set(false); }}}if(selectedInvoker ! =null) {
// Maximum dynamic weight minus total weight
selectedWRR.sel(totalWeight);
return selectedInvoker;
}
return invokers.get(0); }}Copy the code
7 Consistency hashing
The consistent hashing strategy has three features: first, the same client can always access the same provider without adding or deleting the provider. The second is that consistent hashing can effectively spread out the volatility of adding or removing providers. The third is that consistent hash virtual nodes can disperse the volatility of property two more effectively.
7.1 Feature Analysis
One (1) characteristics
The same client can always access the same provider without adding or deleting a provider. In the first step, the six providers are distributed in the hash ring. In the second step, Client1 initiates an access request, at which point the calculated client hash value is located in the hash ring. In the third step, it rotates clockwise along the hash ring to find the provider server5 that is closest to the client hash value. Client1 is always routed to Server5 when the hash ring structure does not change.
What data structure should be selected for the hash ring structure? We can choose TreeMap to build a hash ring with a red-black tree at the bottom.
public class TreeMapTest {
public static void main(String[] args) {
// Build the hash ring
TreeMap<Integer, MyServer> treeMap = new TreeMap<Integer, MyServer>();
treeMap.put(1.new MyServer("1"));
treeMap.put(2.new MyServer("2"));
treeMap.put(3.new MyServer("3"));
treeMap.put(4.new MyServer("4"));
treeMap.put(5.new MyServer("5"));
treeMap.put(6.new MyServer("6"));
// Find the first server whose value is greater than the client hash value
Integer clientHashCode = 5;
SortedMap<Integer, MyServer> tailMap = treeMap.tailMap(clientHashCode, false);
MyServer server = tailMap.get(tailMap.firstKey());
// MyServer(ip=6)System.out.println(server); }}Copy the code
Two (2) characteristics
Consistent hashing can effectively spread out the volatility of new or removed providers, such as server7, without affecting client1 routing results:
The server5 outage only affects the routing results of client1, but does not affect the routing results of other clients:
Three (3) characteristics
Consistent hash virtual nodes can spread out the volatility of feature 2 more effectively. For example, we can add a virtual node for each server node to spread the servers more evenly.
7.2 Code Examples
The first step is to write a basic load balancing policy
public abstract class AbstractConsistentHashLoadBalance {
public MyServer select(String clientIP, List<MyServer> serverList) {
return doSelect(clientIP, serverList);
}
public abstract MyServer doSelect(String clientIP, List<MyServer> serverList);
}
Copy the code
The second step is to write a consistent hashing strategy
public class ConsistentHashBalance1 extends AbstractConsistentHashLoadBalance {
private ConsistentHashSelector consistentHashSelector;
@Override
public MyServer doSelect(String clientIP, List<MyServer> serverList) {
initialConsistentHashSelector(serverList);
return consistentHashSelector.select(clientIP);
}
private class ConsistentHashSelector {
private Integer identityHashCode;
private TreeMap<Integer /* hashcode */, MyServer> serverNodes = new TreeMap<Integer, MyServer>();
// Build the hash ring
public ConsistentHashSelector(Integer identityHashCode, List<MyServer> serverList) {
this.identityHashCode = identityHashCode;
TreeMap<Integer, MyServer> newServerNodes = new TreeMap<Integer, MyServer>();
for (MyServer server : serverList) {
newServerNodes.put(hashCode(server.getIp()), server);
}
serverNodes = newServerNodes;
}
// Route by client IP
public MyServer select(String clientIP) {
// Calculate the client hash value
int clientHashCode = hashCode(clientIP);
// Find the first server whose value is greater than the client hash value
SortedMap<Integer, MyServer> tailMap = serverNodes.tailMap(clientHashCode, false);
if (CollectionUtils.isEmpty(tailMap)) {
Integer firstKey = serverNodes.firstKey();
return serverNodes.get(firstKey);
}
// Not found means between the last node and the first node -> select the first node
Integer firstKey = tailMap.firstKey();
return tailMap.get(firstKey);
}
// Compute the hash value
private int hashCode(String key) {
return Objects.hashCode(key);
}
// The provider list hash value -> changes if providers are added or deleted
public Integer getIdentityHashCode(a) {
returnidentityHashCode; }}private void initialConsistentHashSelector(List<MyServer> serverList) {
// Compute the provider list hash
Integer newIdentityHashCode = System.identityHashCode(serverList);
// There is no need to rebuild the hash ring if the provider list hash value does not change
if (null! = consistentHashSelector && (null! = consistentHashSelector.getIdentityHashCode() && newIdentityHashCode == consistentHashSelector.getIdentityHashCode())) {return;
}
// If the provider list hash value changes, rebuild the hash ring
consistentHashSelector = newConsistentHashSelector(newIdentityHashCode, serverList); }}Copy the code
Step 3 write the test code
public class LoadBalanceTest {
public static void main(String[] args) {
testConsistentHashBalance1();
}
public static void testConsistentHashBalance1(a) {
List<MyServer> serverList = new ArrayList<MyServer>();
MyServer server1 = new MyServer("1");
MyServer server2 = new MyServer("2");
MyServer server3 = new MyServer("3");
MyServer server4 = new MyServer("4");
MyServer server5 = new MyServer("5");
MyServer server6 = new MyServer("6");
serverList.add(server1);
serverList.add(server2);
serverList.add(server3);
serverList.add(server4);
serverList.add(server5);
serverList.add(server6);
AbstractConsistentHashLoadBalance consistentHashBalance = new ConsistentHashBalance1();
for (int i = 0; i < 10; i++) {
String clientIP = "5";
MyServer server = consistentHashBalance.select(clientIP, serverList);
System.out.println("clientIP=" + clientIP + ",consistentHashBalance1 route server="+ server); }}}Copy the code
Step 4 Output the results
clientIP=5,consistentHashBalance1 route server=MyServer(ip=6)
clientIP=5,consistentHashBalance1 route server=MyServer(ip=6)
clientIP=5,consistentHashBalance1 route server=MyServer(ip=6)
clientIP=5,consistentHashBalance1 route server=MyServer(ip=6)
clientIP=5,consistentHashBalance1 route server=MyServer(ip=6)
clientIP=5,consistentHashBalance1 route server=MyServer(ip=6)
clientIP=5,consistentHashBalance1 route server=MyServer(ip=6)
clientIP=5,consistentHashBalance1 route server=MyServer(ip=6)
clientIP=5,consistentHashBalance1 route server=MyServer(ip=6)
clientIP=5,consistentHashBalance1 route server=MyServer(ip=6)
Copy the code
See the following code if you add a virtual node
public class ConsistentHashBalance2 extends AbstractConsistentHashLoadBalance {
private ConsistentHashSelector consistentHashSelector;
@Override
public MyServer doSelect(String clientIP, List<MyServer> serverList) {
initialSelector(serverList);
return consistentHashSelector.select(clientIP);
}
private class ConsistentHashSelector {
private Integer identityHashCode;
private Integer VIRTUAL_NODES_NUM = 16;
private TreeMap<Integer /* hashcode */, MyServer> serverNodes = new TreeMap<Integer, MyServer>();
public ConsistentHashSelector(Integer identityHashCode, List<MyServer> serverList) {
this.identityHashCode = identityHashCode;
TreeMap<Integer, MyServer> newServerNodes = new TreeMap<Integer, MyServer>();
for (MyServer server : serverList) {
// Virtual node
for (int i = 0; i < VIRTUAL_NODES_NUM; i++) {
int virtualKey = hashCode(server.getIp() + "_" + i);
newServerNodes.put(virtualKey, server);
}
}
serverNodes = newServerNodes;
}
public MyServer select(String clientIP) {
int clientHashCode = hashCode(clientIP);
SortedMap<Integer, MyServer> tailMap = serverNodes.tailMap(clientHashCode, false);
if (CollectionUtils.isEmpty(tailMap)) {
Integer firstKey = serverNodes.firstKey();
return serverNodes.get(firstKey);
}
Integer firstKey = tailMap.firstKey();
return tailMap.get(firstKey);
}
private int hashCode(String key) {
return Objects.hashCode(key);
}
public Integer getIdentityHashCode(a) {
returnidentityHashCode; }}private void initialSelector(List<MyServer> serverList) {
Integer newIdentityHashCode = System.identityHashCode(serverList);
if (null! = consistentHashSelector && (null! = consistentHashSelector.getIdentityHashCode() && newIdentityHashCode == consistentHashSelector.getIdentityHashCode())) {return;
}
consistentHashSelector = newConsistentHashSelector(newIdentityHashCode, serverList); }}Copy the code
7.3 DUBBO source
public class ConsistentHashLoadBalance extends AbstractLoadBalance {
public static final String NAME = "consistenthash";
private finalConcurrentMap<String, ConsistentHashSelector<? >> selectors =newConcurrentHashMap<String, ConsistentHashSelector<? > > ();@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String methodName = RpcUtils.getMethodName(invocation);
String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;
int identityHashCode = System.identityHashCode(invokers);
ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
// If the provider list hash value changes, rebuild the hash ring
if (selector == null|| selector.identityHashCode ! = identityHashCode) { selectors.put(key,new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));
selector = (ConsistentHashSelector<T>) selectors.get(key);
}
return selector.select(invocation);
}
private static final class ConsistentHashSelector<T> {
private final TreeMap<Long, Invoker<T>> virtualInvokers;
private final int replicaNumber;
private final int identityHashCode;
private final int[] argumentIndex;
// Build the hash ring
ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
this.identityHashCode = identityHashCode;
URL url = invokers.get(0).getUrl();
this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes".160);
String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments"."0"));
argumentIndex = new int[index.length];
for (int i = 0; i < index.length; i++) {
argumentIndex[i] = Integer.parseInt(index[i]);
}
for (Invoker<T> invoker : invokers) {
String address = invoker.getUrl().getAddress();
// Add virtual nodes (default: 160)
for (int i = 0; i < replicaNumber / 4; i++) {
byte[] digest = md5(address + i);
for (int h = 0; h < 4; h++) {
longm = hash(digest, h); virtualInvokers.put(m, invoker); }}}}// Load balancing
public Invoker<T> select(Invocation invocation) {
String key = toKey(invocation.getArguments());
byte[] digest = md5(key);
return selectForKey(hash(digest, 0));
}
private String toKey(Object[] args) {
StringBuilder buf = new StringBuilder();
for (int i : argumentIndex) {
if (i >= 0&& i < args.length) { buf.append(args[i]); }}return buf.toString();
}
private Invoker<T> selectForKey(long hash) {
Map.Entry<Long, Invoker<T>> entry = virtualInvokers.ceilingEntry(hash);
if (entry == null) {
entry = virtualInvokers.firstEntry();
}
return entry.getValue();
}
// hash
private 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;
}
private 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 code
8 Minimum active number policy
Each provider maintains the number of tasks to be processed concurrently, and the greater the number of tasks, the higher the activity. DUBBO source code: DUBBO source code: DUBBO
public class LeastActiveLoadBalance extends AbstractLoadBalance {
public static final String NAME = "leastactive";
@Override
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
/ / number of invoker
int length = invokers.size();
// Minimum number of calls
int leastActive = -1;
// The number of invokers equals the minimum number of invokers
int leastCount = 0;
// The number of invoker subscripts equals the minimum number of invoker subscripts
int[] leastIndexes = new int[length];
// Weight per service provider
int[] weights = new int[length];
/ / total weight
int totalWeight = 0;
// The first caller weight
int firstWeight = 0;
// Check whether the weights are the same
boolean sameWeight = true;
/ / traverse invokers
for (int i = 0; i < length; i++) {
Invoker<T> invoker = invokers.get(i);
// Number of calls
int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive();
// Get the weight
int afterWarmup = getWeight(invoker, invocation);
// Set the weight
weights[i] = afterWarmup;
// The first invoker or invoker number is less than the minimum number of invokers
if (leastActive == -1 || active < leastActive) {
leastActive = active;
leastCount = 1;
leastIndexes[0] = i;
totalWeight = afterWarmup;
firstWeight = afterWarmup;
sameWeight = true;
}
// The current number of service provider invocations equals the minimum number of invocations
else if (active == leastActive) {
// Record the subscript
leastIndexes[leastCount++] = i;
// Add the total weight value
totalWeight += afterWarmup;
// Check whether the weights are the same
if (sameWeight && i > 0&& afterWarmup ! = firstWeight) { sameWeight =false; }}}Return only one invoker call equal to the minimum number of invoker calls
if (leastCount == 1) {
return invokers.get(leastIndexes[0]);
}
// The number of invoker calls equals the minimum number of invoker calls and the weight values are different -> select according to the weight values
if(! sameWeight && totalWeight >0) {
int offsetWeight = ThreadLocalRandom.current().nextInt(totalWeight);
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexes[i];
offsetWeight -= weights[leastIndex];
if (offsetWeight < 0) {
returninvokers.get(leastIndex); }}}// Multiple Invoker calls equal to the minimum number of invoker calls with the same weight -> random selection
returninvokers.get(leastIndexes[ThreadLocalRandom.current().nextInt(leastCount)]); }}Copy the code
9 Article Summary
First this article first analyzes the fault tolerance and load balancing, cluster service drop these three groups of concepts, the second in this paper, the code simple random, weighted random, simple polling, simple weighted polling, weighted polling, smooth consistency hash, the least active number seven kinds of load balancing strategy, which weights calculation, smooth weighted polling, consistent hashing algorithm it is worth noting that, I hope this article will be helpful.
Welcome to pay attention to the public account “JAVA Front” to view more wonderful sharing articles, mainly including source code analysis, practical application, architecture thinking, workplace sharing, product thinking and so on, at the same time, welcome to add my personal wechat “JAVA_front” to communicate and learn together