Dubbo Series (07-3) Cluster fault tolerance – load balancing

Dubbo series (07-3) cluster fault tolerance-load balancing

Spring Cloud Alibaba Series Catalog-Dubbo Chapter

1. Background Introduction

Recommended documents:< /p>

1. Dubbo official website source code interpretation-load balancing

In Dubbo’s entire cluster fault tolerance process, first go through the Directory to get all the Invoker lists, and then go through the Routers according to the route The rule filters the Invoker, and the last surviving Invoker also needs to go through the load balancing LoadBalance level to select the final invoked Invoker. In the previous article, the basic principles of service dictionary and service routing have been analyzed, and then continue to analyze LoadBalance.

1.1 Load Balancing Algorithm

Dubbo-2.7.3 provides 4 load balancing implementations, namely:

1. Weighted random algorithm: RandomLoadBalance. When there are fewer requests, the random numbers generated may be more concentrated. At this time, most requests will fall on the same server, which can be ignored in most cases. The more requests, the more evenly distributed. RandomLoadBalance is Dubbo’s default load balancing algorithm.
2. Weighted polling algorithm: RoundRobinLoadBalance. The slow processing node will become a bottleneck.
3. Consistency Hash: ConsistentHashLoadBalance. For sticky connections, try to make the client always make calls to the same service provider, unless the provider hangs up.
4. Least ActiveLoadBalance algorithm: LeastActiveLoadBalance. Add 1 before processing the request, and subtract 1 after processing, so that the number of active calls of slow-processing nodes will increase. In the end, nodes that process faster will take on more requests.

1.2 Inheritance system

Summary: Four All load balancing implementation classes inherit from AbstractLoadBalance. This class implements the LoadBalance interface and also encapsulates some common logic, such as service provider weight calculation logic.

Dubbo defaults to RandomLoadBalance based on the weighted random algorithm, and the load balancing algorithm can be specified according to the loadbalance parameter. The interface is defined as follows:

@SPI(RandomLoadBalance.NAME) public interface LoadBalance {@Adaptive("loadbalance")  Invoker select(List> invokers, URL url, Invocation invocation) throws RpcException;}

2. Source code analysis

2.1 AbstractLoadBalance

In addition to implementing the LoadBalance interface, AbstractLoadBalance also provides service provider weight calculation logic.

2.1.1 LoadBalance entrance

Let’s first look at the load balancing entrance method select, as follows:

@Overridepublic  Invoker select(List> invokers, URL url, Invocation invocation) {if (CollectionUtils.isEmpty(invokers)) {return null;} // if only invokers list An Invoker can return directly without load balancing if (invokers.size() == 1) {return invokers.get(0);} // call the doSelect method for load balancing. This method is an abstract method, The class implements return doSelect(invokers, url, invocation);}

Summary: The logic of select itself is very simple, and the specific load balancing algorithm is delegated to the subclass doSelect to implement.

2.1.2 Weight calculation

AbstractLoadBalance also provides service provider weight calculation logic. The specific implementation is as follows:

protected int getWeight(Invoker invoker, Invocation invocation) {// Obtain the weight configuration value of the specified method from the url, the default value is 100 int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), WEIGHT_KEY, DEFAULT_WEIGHT); if (weight> 0) {// Get service provider startup timestamp long timestamp = invoker.getUrl().getParameter(REMOTE_TIMESTAMP_KEY, 0L) ; if (timestamp> 0L) {// Calculate service provider running time int uptime = (int) (System.currentTimeMillis()-timestamp); // Get service warmup time, the default is 10 minutes int warmup = invoker.getUrl ().getParameter(WARMUP_KEY, DEFAULT_WARMUP); // If the service running time is less than the warm-up time, recalculate the service weight, that is, reduce the weight if (uptime> 0 && uptime = 0? weight: 0;}

Summary: The weight calculation is divided into two steps: one is to obtain the specified method The weight parameter, the default value is 100; the second is if the service startup time is less than the warm-up time, the weight is recalculated according to the ratio (uptime/warmup), which is usually called cold start .

The purpose of the cold start is to lower the power of the service, so as to avoid the service being in a high load state at the beginning of the start. Service warm-up is an optimization method, similar to this is JVM warm-up. The main purpose is to allow the service to run at “low power” for a period of time after it is started, so that its efficiency is slowly improved to the best state.

static int calculateWarmupWeight(int uptime, int warmup, int weight) {// Calculate the weight, the following code is logically similar to (uptime / warmup) * weight. // As the service running time uptime increases, the weight calculation value ww will slowly approach the configuration value weight int ww = (int) ((float) uptime / ((float) warmup / (float) weight)); return ww < 1? 1: (ww> weight? Weight: ww);}

2.2 RandomLoadBalance

RandomLoadBalance is a specific implementation of a weighted random algorithm, and its algorithmic thinking is very simple. Suppose we have a set of servers = [A, B, C], their corresponding weights are weights = [5, 3, 2], and the total weight is 10. Now spread these weight values ​​on the one-dimensional coordinate values, [0, 5) interval belongs to server A, [5, 8) interval belongs to server B, and [8, 10) interval belongs to server C. Next, use a random number generator to generate a random number in the range [0, 10), and then calculate which interval this random number will fall into. For example, the number 3 will fall into the interval corresponding to server A, and then return to server A.

@Overrideprotected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {// 1. Construct the weight corresponding to each Invoker Array weights[] int length = invokers.size(); // 1.1 sameWeight indicates whether all Invokers have the same weight value boolean sameWeight = true; int[] weights = new int[length]; int firstWeight = getWeight(invokers. get(0), invocation); weights[0] = firstWeight; int totalWeight = firstWeight; // 1.2 Calculate the total weight totalWeight, and check whether the weight of each service provider is the same sameWeight for (int i = 1; i  0 && !sameWeight) {// Get a random number in the interval [0, totalWeight) int offset = ThreadLocalRandom.current().nextInt(totalWeight) ); // Loop to subtract the weight of the service provider from the offset number. When the offset is less than 0, return the corresponding Invoker. // For example, we have servers = [A, B, C], weights = [5, 3, 2], offset = 7. // In the first loop, offset-5 = 2> 0, that is, offset> 5, // indicates that it will not fall on the interval corresponding to server A. // In the second loop, offset-3 = -1 <0, that is, 5 
Summary: The algorithm of RandomLoadBalance is relatively simple, roughly divided into There are three steps:

Calculate the weight array weights corresponding to each Invoker[]
When the weight values ​​are not equal, calculate which interval the random number falls on
 < li>The weight value is the same. At this time, it will directly return a random 

RandomLoadBalance After multiple requests, the call request can be "evenly" distributed according to the weight value. It is a simple and efficient load balancing implementation, so Dubbo chose it as the default implementation. 
2.3 LeastActiveLoadBalance
LeastActiveLoadBalance translates to minimum active load balance. The smaller the number of active calls, the higher the efficiency of the service provider, and more requests can be processed per unit time. At this time, the request should be assigned to the service provider first. 
LeastActiveLoadBalance needs to be used in conjunction with ActiveLimitFilter. This filter records the active number of each interface method. When load balancing is performed, only one Invoker with the least active number is selected for execution each time. 
LeastActiveLoadBalance can be seen as an enhanced version of RandomLoadBalance, because if multiple invokers with the smallest active number are selected, the logic after that is exactly the same as RandomLoadBalance. 
2.3.1 Algorithm implementation
@Overrideprotected  Invoker doSelect(List> invokers, URL url, Invocation invocation) {// 1. Initialize various counters int length = invokers.size(); int leastActive = -1; int leastCount = 0; int[] leastIndexes = new int[length]; int[] weights = new int[length]; int totalWeight = 0; int firstWeight = 0; boolean sameWeight = true; // 2. pk gets the smallest number of active invokers for (int i = 0; i  invoker = invokers.get(i); // 2.1 core, get the number of active int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive(); int afterWarmup = getWeight(invoker, invocation ); // weight value weights[i] = afterWarmup; // 2.2 pk gets the new minimum active number (the first one, the previous minimum active number is cleared) if (leastActive == -1 || active  0 && afterWarmup != firstWeight) {sameWeight = false;}}} // 3. If There are multiple invokers with the smallest active count at the same time, which is equivalent to RandomLoadBalance if (leastCount == 1) {return invokers.get(leastIndexes[0]);} if (!sameWeight && totalWeight> 0) {int offsetWeight = ThreadLocalRandom.current( ).nextInt(totalWeight); for (int i = 0; i 
Summary: Finally, you can see that LeastActiveLoadBalance has one more minimum than RandomLoadBalance Except for the comparison of active numbers, the rest seem to be basically the same. 
int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive();
2.3.2 Statistics of the minimum active number
In ActiveLimitFilter, the counter is +1 before the request is processed, and the counter is -1 after the request is processed (regardless of success or failure or exception). This counter is the minimum active number. It is equivalent to the following simulation code. Of course, the real Filter processing is more complicated than this. 
try {RpcStatus.beginCount(url, methodName, max); ... RpcStatus.endCount(url, methodName, getElapsed(invocation), true)} catch(Exception e) { RpcStatus.endCount(url, methodName, getElapsed(invocation), false);}
2.4 ConsistentHashLoadBalance

Contents


Spring Cloud Alibaba series catalog-Dubbo articles
1. Background introduction< ul>
1.1 Load balancing algorithm
1.2 Inheritance system


2. Source code analysis

2.1 AbstractLoadBalance
2.2 RandomLoadBalance
2.3 LeastActiveLoadBalance
2.4 ConsistentHashLoadBalance





Spring Cloud Alibaba series catalog-Dubbo articles
1. Background introduction

1.1 Load balancing algorithm
1.2 Inheritance system


2. Source code analysis

2.1 AbstractLoadBalance
2.2 RandomLoadBalance
2.3 LeastActiveLoadBalan ce
2.4 ConsistentHashLoadBalance