Load balancing algorithm in dubbo
When there are multiple service providers in dubbo, there is a cluster of services. There are some algorithms for how to allocate service calls in the cluster to select appropriate services to provide services.
Polling load balancing algorithm roundrobin loadbalance
As the name suggests, polling is to provide services one by one. Suppose there are three services 1, 2 and 3. First execute service 1, then 2, then 3, followed by service 1
-
Direct code
// Define a similar counter private static AtomicInteger atomicIndexDirect = new AtomicInteger(0); private List<String> appServerAddress = Arrays.asList("http://localhost:1000/1","http://localhost:1001/1","http://localhost:1001/1") // Polling calls in the service provider cluster if (appServerAddressList.size() == 1) { appServerAddress = appServerAddressList.get(0); } else { // Counter plus one int index = atomicIndexDirect.incrementAndGet(); // Judge whether to cross the boundary and return to the origin if (index > appServerAddressList.size() - 1) { index = 0; atomicIndexDirect.set(index); } appServerAddress = appServerAddressList.get(index); }
RandomLoadBalance of weight random algorithm
Suppose there are three servers [A, B and C], we set the weights to be 5, 3 and 2 respectively, and the total weight is 10. For these three servers, it can be considered that server A is [0,5], server B is [5,8], and server C is [8,10], At this time, A random number generator is provided (here, it is considered that the algorithm of the random number generator is good enough and the generated data is random enough), so let it generate A [0,10) random number, and the data will fall in one section. At this time, the request will be distributed to the corresponding section
The idea is to assign weight to each service, then obtain the total weight, take the total weight to generate a random number less than the total weight, and then compare the random number with the weight of each service to whether it is in the changed service interval
-
dubbo source code
package org.apache.dubbo.rpc.cluster.loadbalance; import org.apache.dubbo.common.URL; import org.apache.dubbo.rpc.Invocation; import org.apache.dubbo.rpc.Invoker; import java.util.List; import java.util.concurrent.ThreadLocalRandom; /** * random load balance. */ 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) { // Dubbo multiple nodes will be packaged in the form of invoker model int length = invokers.size(); boolean sameWeight = true; // Weight of each invoker int[] weights = new int[length]; // Try to get the weight of the first invoker int firstWeight = getWeight(invokers.get(0), invocation); weights[0] = firstWeight; // The sum of weights int totalWeight = firstWeight; for (int i = 1; i < length; i++) { int weight = getWeight(invokers.get(i), invocation); // save for later use weights[i] = weight; // Sum totalWeight += weight; if (sameWeight && weight != firstWeight) { sameWeight = false; } } if (totalWeight > 0 && !sameWeight) { // Based on the total weight, a random data is generated int offset = ThreadLocalRandom.current().nextInt(totalWeight); // Find the interval in which the random data falls for (int i = 0; i < length; i++) { offset -= weights[i]; if (offset < 0) { return invokers.get(i); } } } //If the weights are equal, a random number is obtained return invokers.get(ThreadLocalRandom.current().nextInt(length)); } }Weighted polling load balancing algorithm weightroundrobin loadbalance
Idea: save the number of all requests to the map set. key is the interface, method and parameter type of the call, and value is the number of calls. Obtain the maximum weight, minimum weight and total weight according to the weight of each service, and save the request address and weight of each service to the map set by traversing the total weight, Use the number of interface calls to balance the total weight (distribute the request in the weight), and then traverse the saved address and weight. If the conditions are met, it will return. If not, the number of calls will be reduced
When the weights of all services are the same, it becomes a polling call
-
Direct code
package com.yu.dubbo.core.cluster.loadbalance; import java.util.LinkedHashMap; import java.util.List; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentMap; import java.util.concurrent.atomic.AtomicLong; public class WeightRoundRobinLoadBalance extends AbstractLoadBalance { public static final String NAME = "weightroundrobin"; protected static class WeightedRoundRobin { private AtomicLong current = new AtomicLong(0); private long getAndIncrement() { return current.getAndIncrement(); } } private ConcurrentMap<String, WeightedRoundRobin> methodWeightMap = new ConcurrentHashMap<>(); @Override protected String doSelect(List<String> providers, String interfaceName, String methodName) { String key = interfaceName + "." + methodName; int length = providers.size(); int maxWeight = 0; int minWeight = Integer.MAX_VALUE; final LinkedHashMap<String, IntegerWrapper> invokerToWeightMap = new LinkedHashMap<>(); int weightSum = 0; //Initialize maxWeight, minWeight, weightSum, invokerToWeightMap for (int i = 0; i < length; i++) { int weight = getWeight(providers.get(i)); maxWeight = Math.max(maxWeight, weight); // Choose the maximum weight minWeight = Math.min(minWeight, weight); // Choose the minimum weight if (weight > 0) { invokerToWeightMap.put(providers.get(i), new IntegerWrapper(weight)); weightSum += weight; } } // Get the number of auto increment calls WeightedRoundRobin weightedRoundRobin = methodWeightMap.get(key); if (weightedRoundRobin == null) { methodWeightMap.putIfAbsent(key, new WeightedRoundRobin()); weightedRoundRobin = methodWeightMap.get(key); } // Total number of current interface calls long currentSequence = weightedRoundRobin.getAndIncrement(); //When the weights are different, the invoker is obtained through weighted polling. The greater the weight, the greater the probability of being selected if (maxWeight > 0 && minWeight < maxWeight) { long mod = currentSequence % weightSum; for (int i = 0; i < maxWeight; i++) { //Number of invoker s traversed for (Map.Entry<String, IntegerWrapper> each : invokerToWeightMap.entrySet()) { final String k = each.getKey(); //Weight of invoker final IntegerWrapper v = each.getValue(); if (mod == 0 && v.getValue() > 0) { return k; } if (v.getValue() > 0) { //The number of callable times of the current invoker is reduced by 1 v.decrement(); mod--; } } } } // When the Round robin weight is the same, the invoker is obtained by taking the remainder return providers.get((int) (currentSequence % length)); } private static final class IntegerWrapper { private int value; public IntegerWrapper(int value) { this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public void decrement() { this.value--; } } }consistent hashing algorithm
While using the hash algorithm, the new service node needs to remap the mapping relationship of all service nodes, which has a great impact. All are determined by the consistency hash algorithm. When adding a service node, it will only have a small impact to re-establish the mapping relationship. You can also add virtual nodes to disperse the requests as much as possible
Minimum active number algorithm
The minimum active number is the service with the fastest response time. Whichever response request is fast, it will be processed by which server