1. Related concepts

When all nodes in a service cluster are active, each node shares the workload of the entire system. Load balancing clusters are generally used for web servers and database servers corresponding to network requests. Such a cluster can check for less busy servers that receive fewer requests and redirect requests to those servers as they come in. IP load balancing with DNS load balancing, load balancing, reverse proxy load balancing and other patterns, in the model also has A variety of load balancing algorithm, as shown in the figure below, in A cluster server A, B, C, they are each other, unrelated to any of the machine is down, will not affect the operation of other machines, when the user to A request, The load balancer algorithm determines which machine will process the load. If your algorithm uses the round algorithm, users A, B, and C send requests respectively, and server A, B, and C process the responses respectively.

2. Load balancing

2.1 Overall structure of load balancing

Dubbo framework built-in four load balancing algorithms, users can also expand, the default implementation is RandomLoadBalance(random load balancing), because the select method has @adaptive annotation, according to the URL with the loadBalance parameter at runtime dynamically specified load balancing algorithm.

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

AbstractLoadBalance is an abstract class that implements the LoadBalance interface method and has a variety of concrete load balancing strategies to implement classes.

Description of Dubbo load balancing policies:

  • RandomLoadBalance: random, according to the weight set random probability. The probability of collision on a node is high, but the larger the amount of call, the more uniform the distribution, and according to the probability of use weight is also more uniform, which is conducive to dynamic adjustment of provider weight;
  • RoundRobinLoadBalance: Sets the polling ratio based on the weights specified in the convention. There is the problem of slow provider accumulation of requests. For example: the second machine is very slow, but can still respond to requests, when the request to the second machine will be stuck here, over time, will be stuck in the second stage;
  • Leastactive VeloadBalance: minimum number of active calls. If the number of active calls is the same, the call will be random. Make slower providers receive fewer requests, because slower providers have a larger difference in counts before and after calls;
  • Hash ConsistentHashLoadBalance: consistency, always the same parameters request sent to the same provider. When one provider “hangs,” requests destined for that provider, based on virtual nodes, are spread out to other providers without causing dramatic fluctuations. By default, only the first parameter “Hash” is used. If you want to change it, configure hash.arguments. By default, 160 virtual nodes are used.

AbstractLoadBalance LoadBalance interface is achieved, and encapsulate some commonly used methods, RoundRobinLoadBalance/RandomLoadBalance inherited AbstractLoadBalance class, The Dubbo framework is optimized for the JIT compiler to trigger compilation optimizations. The JVM is optimized for the JIT compiler, and the Dubbo framework is optimized for the JIT compiler to trigger compilation optimizations. If the online time of the service provider is less than the warm-up time, recalculate the node weight.

public abstract class AbstractLoadBalance implements LoadBalance { ... int getWeight(Invoker<? > invoker, Invocation invocation) { int weight; URL url = invoker.getUrl(); if (REGISTRY_SERVICE_REFERENCE_PATH.equals(url.getServiceInterface())) { weight = url.getParameter(REGISTRY_KEY + "." + WEIGHT_KEY, DEFAULT_WEIGHT); } else {// Get the weights from the URL, If not, 100 weight = url.getmethodParameter (Invocation. GetMethodName (), WEIGHT_KEY, DEFAULT_WEIGHT); If (weight > 0) {timestamp = invoker.geturl ().getParameter(TIMESTAMP_KEY, 0L); If (timestamp > 0L) {long uptime = system.currentTimemillis () -timestamp; if (uptime < 0) { return 1; Int warmup = invoker.geturl ().getParameter(WARMUP_KEY, DEFAULT_WARMUP); // Obtain the warmup time of the service provider. The default value is 10 minutes. If (uptime > 0 && uptime < Warmup) {weight = calculateWarmupWeight((int)uptime, warmup, weight); } } } } return Math.max(weight, 0); }... <T> Invoker<T doSelect(List<Invoker<T>> Invokers, URL, URL, Invocation); }Copy the code

2.2 the Random

This class implements abstract AbstractLoadBalance interface and overwrites the doSelect method. It firstly traverses each machine providing services, obtains the weight of each service, and then accumulates the weight value to determine whether the weight of each service provider is the same. Finally, if the weight of each caller, and each weight greater than zero, then will according to the gross weight to generate a random number, then use the random Numbers, according to the number of the caller every time minus the weight of the caller, calculated until the current service provider random number less than zero, just choose the provider. In addition, if the weights of each machine are the same, then the weights will not participate in the calculation, and directly choose one of the choices generated by the random algorithm, completely random.

public class RandomLoadBalance extends AbstractLoadBalance { @Override protected <T> Invoker<T> DoSelect (List<Invoker<T>> Invokers, URL, URL, Invocation) {int length = invokers.size(); Boolean sameWeight = true; sameWeight = true; Int [] weights = new int[length]; Invocation AbstractLoadBalance#getWeight int firstWeight = Invocation (Invokers.get (0), Invocation); weights[0] = firstWeight; int totalWeight = firstWeight; For (int I = 1; i < length; i++) { int weight = getWeight(invokers.get(i), invocation); weights[i] = weight; totalWeight += weight; if (sameWeight && weight ! = firstWeight) { sameWeight = false; If (totalWeight > 0 &&! Diminishing sameWeight) {/ / random access values int offset = ThreadLocalRandom. The current () nextInt (totalWeight); Invoker for (int I = 0; i < length; i++) { offset -= weights[i]; if (offset < 0) { return invokers.get(i); }}} / / if the weight and no greater than 0 or service node weights are the same, random access return invokers. Get (ThreadLocalRandom. The current () nextInt (length)); }}Copy the code

Suppose there are four invokers with weights of 1, 2, 3, and 4, then the weight is 10. Note Each Invoker has a 1/10, 2/10, 3/10, and 4/10 chance of being selected. Then nextInt(10) will return an integer between 0 and 10, assuming that it is 5, and subtract. When it is reduced to 3, it will be less than 0. At this time, it will fall into the range of 3, and Invoker no.3 will be selected.

2.3 LeastActive

Minimum number of active calls Load balancing implementation, the framework will record the number of active invokers, each time only from the least number of active invokers selected one node, invokers with the same number of active invokers into the set, using the Random algorithm to select. The load balancing algorithm needs to work with the RpcStatus request status logging container and the ActiveLimitFilter to count the number of active methods per interface.

public class LeastActiveLoadBalance extends AbstractLoadBalance { @Override protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) { .... for (int i = 0; i < length; i++) { ... Int Active = rpcStatus.getStatus (Invocation.geturl ()).getActive(); . / / if it is the first time or find a smaller number of active if (leastActive = = 1 | | active < leastActive) {/ / previous count to start again, empty leastActive = active; leastCount = 1; leastIndexes[0] = i; totalWeight = afterWarmup; firstWeight = afterWarmup; sameWeight = true; } else if (active == leastActive) {// The number of invokers is the same as the number of invokers. // The number of invokers is the same as the number of invokers. Then randomly select leastIndexes[leastCount++] = I from this collection; totalWeight += afterWarmup; if (sameWeight && afterWarmup ! = firstWeight) { sameWeight = false; }}}... }}Copy the code

The minimum number of active calls requires a container RpcStatus that records the calls of each node, which mainly stores the corresponding relationship between URLS and RpcStatus objects, the corresponding relationship between urls and called methods, as well as various counters. In the beginCount method, you’re essentially incrementing the number of method calls.

Private static final ConcurrentMap<String, private static final ConcurrentMap<String, RpcStatus> SERVICE_STATISTICS = new ConcurrentHashMap<String, RpcStatus>(); Private static final ConcurrentMap<String, ConcurrentMap<String, RpcStatus>> METHOD_STATISTICS = new ConcurrentHashMap<String, ConcurrentMap<String, RpcStatus>>(); . public static boolean beginCount(URL url, String methodName, int max) { ... // CAS for (int I; ;) { i = methodStatus.active.get(); if (i + 1 > max) { return false; } if (methodStatus.active.compareAndSet(i, i + 1)) { break; } } appStatus.active.incrementAndGet(); . return true; }}Copy the code

The ActiveLimitFilter class has @Activate annotation. Due to the high performance loss in the case of high concurrency, statistics will be added to the Filter link only when the corresponding conditions are met. RpcStatus method is used in invoke to count the number of calls/time.

@Activate(group = CONSUMER, value = ACTIVES_KEY) public class ActiveLimitFilter implements Filter, Filter.Listener { @Override public Result invoke(Invoker<? > invoker, Invocation invocation) throws RpcException { ... if (! RpcStatus.beginCount(url, methodName, max)) { long timeout = invoker.getUrl().getMethodParameter(invocation.getMethodName(), TIMEOUT_KEY, 0); long start = System.currentTimeMillis(); long remain = timeout; synchronized (rpcStatus) { while (! RpcStatus.beginCount(url, methodName, max)) { try { rpcStatus.wait(remain); } catch (InterruptedException e) { ... }... }Copy the code

2.4 RoundRobin

Weight polling load balancing determines the polling ratio according to the set weight. The polling call process mainly maintains a map of local variables to store the corresponding relationship between the caller and the weight value. The doSelect method iterates through all available nodes (Invoker list), for each Invoker’s current=current+weight, and accumulates each Invoker’s weight into totalWeight. TotalWeight =totalWeight+weight, select the node with the highest current value as the selected node, and subtract totalWeight from its current value, i.e. current= current-totalweight, In this way, in each poll, the node with the highest weight will always be able to subtract the optional condition quickly, while the node with the lowest weight will have to subtract totalWeigth several times before reaching the optional condition.

public class RoundRobinLoadBalance extends AbstractLoadBalance { ... Protected static class WeightedRoundRobin {// private int weight; Private AtomicLong Current = new AtomicLong(0); Private long lastUpdate; Public void sel(int total) {current. AddAndGet (-1 * total); Private ConcurrentMap<String, ConcurrentMap<String, WeightedRoundRobin>> methodWeightMap = new ConcurrentHashMap<String, ConcurrentMap<String, WeightedRoundRobin>>(); . @override protected <T> Invoker<T> doSelect(List<Invoker<T>> Invokers, URL URL, Invocation) {// Initialize (Service interface name). Method name, node weight round query) cache... For (Invoker<T> Invoker: invokers) {String identifyString = invoker.geturl ().toidentityString (); Int weight = invocation (Invoker, Invocation); WeightedRoundRobin WeightedRoundRobin = map.computeIfAbsent(identifyString, k -> { WeightedRoundRobin wrr = new WeightedRoundRobin(); wrr.setWeight(weight); return wrr; }); / / update the weight record information long cur. = weightedRoundRobin increaseCurrent (); weightedRoundRobin.setLastUpdate(now); If (cur > maxCurrent) {// Update maxCurrent = cur; selectedInvoker = invoker; selectedWRR = weightedRoundRobin; } // Add weight to totalWeight += weight; Invokers.size () if (invokers.size()! = map.size()) { map.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD); } if (selectedInvoker! = null) { selectedWRR.sel(totalWeight); return selectedInvoker; } return invokers.get(0); }}Copy the code

2.5 Consistent Hash

Consistent Hash load balancing allows requests with the same parameters to be routed to the same machine each time. This load balancing approach allows requests to be relatively evenly distributed to other service nodes when some nodes go offline, rather than causing drastic changes, compared to using Hash directly. An example of a consistent Hash is shown below. A normal consistent Hash hashes each service node over the ring, and then hashes the requesting client over the ring. The first node found clockwise is the one to invoke. If node C goes down and goes offline, clients in area 2 are automatically migrated to node D, avoiding the problem of all rehashes.

Ordinary consistent Hash also has some limitations. Its Hash may not be uniform, which may cause heavy pressure on some nodes. Therefore, the Dubbo framework uses Ketama consistent Hash algorithm, which creates multiple virtual nodes for each real node, so that nodes are evenly distributed across the ring and subsequent calls are more even.

public class ConsistentHashLoadBalance extends AbstractLoadBalance { @Override protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, String methodName = rpCutils. getMethodName(Invocation); String key = invokers.get(0).geturl ().getServiceKey() + "." + methodName; Int invokersHashCode = invokers.hashCode(); ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors. if (selector == null || selector.identityHashCode ! = invokersHashCode) { selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, invokersHashCode)); selector = (ConsistentHashSelector<T>) selectors.get(key); } return selector.select(invocation); }}Copy the code

ConsistenHashSelector initialization hashes the nodes. The Hash ring is implemented using a TreeMap. All real and virtual nodes are put into TreeMap, where the key value is Hash(MD5(IP of the node + increasing number)), The value of value is the node being invoked. When used on the client, MD5 calculation is performed on the request parameters. The MD5 value may not accurately match the key in TreeMap. Therefore, selectForKey method uses cellingEntry method of TreeMap to return an entry that is at least greater than or equal to the key. The value of the entry is Invoker, so the search effect is clockwise forward.

Private static final class ConsistentHashSelector<T> {private static final class ConsistentHashSelector<T> {private final TreeMap<Long, Invoker<T>> virtualInvokers; . ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, Int identityHashCode) {// Initialize TreeMap this.virtualInvokers = new TreeMap<Long, Invoker<T>>(); This.replicanumber = url.getmethodParameter (methodName, HASH_NODES, 160); . for (Invoker<T> invoker : invokers) { String address = invoker.getUrl().getAddress(); for (int i = 0; i < replicaNumber / 4; Byte [] digest = MD5 (address + I); byte[] digest = MD5 (address + I); for (int h = 0; h < 4; H ++) {// "hash" the TreeMap key, Invoker is value long m = hash(digest, h); virtualInvokers.put(m, invoker); }}}} private Invoker<T> selectForKey(long Hash) {// Get an entry Map that is at least greater than or equal to the current given key.Entry< long, Invoker<T>> entry = virtualInvokers.ceilingEntry(hash); If (entry = = null) {/ / if null, it returns the first entry entry. = virtualInvokers firstEntry (); } return entry.getValue(); } public Invoker<T> select(Invocation) {// Emp md5 String key = toKey(Invocation. GetArguments ()); byte[] digest = md5(key); // Select Invoker return selectForKey(hash(digest, 0)) based on the md5 value; }}}Copy the code

3. Summary

This paper focuses on the relevant principle of services in the cluster load balancing, and the frame of the Dubbo Random consistency/RoundRobin/LeastActive/hash methods such as the main idea of load balancing.

reference

Blog.csdn.net/wfq78496769…

Blog.csdn.net/feelwing131… Dubbo preheating process

Blog.csdn.net/zhoufanyang… The JVM preheating