Several algorithms of Loadbalance and its use in ribbon

Load Balancing is an algorithm used to solve the problem that one machine (one process) can’t handle all requests.

Load balancing is used in many places like nginx to distribute traffic, ribbon to provide load balancing for clients, load balancing in dubbo service calls, etc.

The benefits of using load balancing are obvious.

when one or more servers in the cluster go down, the remaining servers that are not down can keep the service running
more machines are used to ensure the benign use of machines, so that the system cpu does not rise sharply due to a peak moment

There are several implementation strategies for load balancing, the common ones are.

Random
RoundRobin
ConsistentHash
Hash
Weighted

Let’s take the implementation of ribbon as a basis to see how some of these algorithms are implemented.

The ribbon is a service that provides load balancing functionality for clients. It provides an internal interface called ILoadBalance to represent the operations of the load balancer, such as adding a server operation, selecting a server operation, getting a list of all servers, getting a list of available servers, and so on.

An interface called IRule is also provided to represent the load balancing policy.

public interface IRule{
    public Server choose(Object key);
    public void setLoadBalancer(ILoadBalancer lb);
    public ILoadBalancer getLoadBalancer();    
}

The IRule interface has the following implementation classes.

Among them, RandomRule means random strategy, RoundRobin means polling strategy, WeightedResponseTimeRule means weighted strategy, BestAvailableRule means least number of requests strategy, etc.

The random policy is very simple, it is a random selection of a server from the servers, the code to implement RandomRule is as follows.

public Server choose(ILoadBalancer lb, Object key) {
    if (lb == null) {
        return null;
    }
    Server server = null;

    while (server == null) {
        if (Thread.interrupted()) {
            return null;
        }
        List<Server> upList = lb.getReachableServers();
        List<Server> allList = lb.getAllServers();
        int serverCount = allList.size();
        if (serverCount == 0) {
            return null;
        }
        int index = rand.nextInt(serverCount); // Use jdk's internal Random class to get the index value randomly
        server = upList.get(index); // Get the server instance

        if (server == null) {
            Thread.yield();
            continue;
        }

        if (server.isAlive()) {
            return (server);
        }

        server = null;
        Thread.yield();
    }
    return server;
}

The RoundRobin polling policy means that the next server is taken each time, for example, if there are 5 servers, the first one is taken for the first time, the second one for the second time, the third one for the third time, and so on.

public Server choose(ILoadBalancer lb, Object key) {
    if (lb == null) {
        log.warn("no load balancer");
        return null;
    }

    Server server = null;
    int count = 0;
    while (server == null && count++ < 10) { // Retry 10 times
        List<Server> reachableServers = lb.getReachableServers();
        List<Server> allServers = lb.getAllServers();
        int upCount = reachableServers.size();
        int serverCount = allServers.size();

        if ((upCount == 0) || (serverCount == 0)) {
            log.warn("No up servers available from load balancer: " + lb);
            return null;
        }

        int nextServerIndex = incrementAndGetModulo(serverCount); // The incrementAndGetModulo method internally uses the nextServerCyclicCounter AtomicInteger property to increment the serverCount atomically to get the index value.
        server = allServers.get(nextServerIndex); // Get the server instance

        if (server == null) {
            Thread.yield();
            continue;
        }

        if (server.isAlive() && (server.isReadyToServe())) {
            return (server);
        }

        server = null;
    }

    if (count >= 10) {
        log.warn("No available alive servers after 10 tries from load balancer: "
                + lb);
    }
    return server;
}

The BestAvailableRule policy is used to select the server with the least number of concurrent requests.

public Server choose(Object key) {
    if (loadBalancerStats == null) {
        return super.choose(key);
    }
    List<Server> serverList = getLoadBalancer().getAllServers(); // Get a list of all servers
    int minimalConcurrentConnections = Integer.MAX_VALUE;
    long currentTime = System.currentTimeMillis();
    Server chosen = null;
    for (Server server: serverList) { // Iterate through each server
        ServerStats serverStats = loadBalancerStats.getSingleServerStat(server); // Get the status of each server
        if (!serverStats.isCircuitBreakerTripped(currentTime)) { // Continue if no circuit breaker is triggered
            int concurrentConnections = serverStats.getActiveRequestsCount(currentTime); // Get the number of requests from the current server
            if (concurrentConnections < minimalConcurrentConnections) { // Compare the number of requests between servers, then select the server with the lowest number of requests and put it in the chosen variable
                minimalConcurrentConnections = concurrentConnections;
                chosen = server;
            }
        }
    }
    if (chosen == null) { // If not selected, call the parent class ClientConfigEnabledRoundRobinRule's choose method, that is, use RoundRobinRule polling for load balancing        
        return super.choose(key);
    } else {
        return chosen;
    }
}

Example to verify the LoadBalance function in Ribbon

There are 3 instances provided in ServerList, which are.

1
2
3

compute-service:2222
compute-service:2223
compute-service:2224

Then use the different IRule policies to see the load balancing implementation.

Start by using the LoadBalanced annotation provided by ribbon on top of the RestTemplate, which automatically constructs the implementation class of the LoadBalancerClient interface and registers it in the Spring container.

@Bean
@LoadBalanced
RestTemplate restTemplate() {
    return new RestTemplate();
}

Next, when using RestTemplate for rest operation, it will automatically use the load balancing policy, and it will internally add LoadBalancerInterceptor as an interceptor in RestTemplate.

In the example, the name of our instance is called compute-service, which provides a method add for adding 2 values of type Integer.

The specific operation of loadbalance.

public String loadbalance() {
    ServiceInstance serviceInstance = loadBalancerClient.choose("compute-service");
    StringBuilder sb = new StringBuilder();
    sb.append("host: ").append(serviceInstance.getHost()).append(", ");
    sb.append("port: ").append(serviceInstance.getPort()).append(", ");
    sb.append("uri: ").append(serviceInstance.getUri());
    return sb.toString();
}

RandomRule

@Configuration
public class RibbonConfiguration {

    @Autowired
    private SpringClientFactory springClientFactory;

    @Bean
    public IRule ribbonRule() {
        return new RandomRule();
    }

}

The test results are as follows, which are indeed obtained randomly.

host: 192.168.31.113, port: 2222, uri: http://192.168.31.113:2222
host: 192.168.31.113, port: 2222, uri: http://192.168.31.113:2222
host: 192.168.31.113, port: 2222, uri: http://192.168.31.113:2222
host: 192.168.31.113, port: 2224, uri: http://192.168.31.113:2224
host: 192.168.31.113, port: 2224, uri: http://192.168.31.113:2224
host: 192.168.31.113, port: 2222, uri: http://192.168.31.113:2222
host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
host: 192.168.31.113, port: 2222, uri: http://192.168.31.113:2222
host: 192.168.31.113, port: 2222, uri: http://192.168.31.113:2222
host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223

RoundRobinRule

@Bean
public IRule ribbonRule() {
    return new RoundRobinRule();
}

The test results are as follows, which do poll each server.

host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
host: 192.168.31.113, port: 2222, uri: http://192.168.31.113:2222
host: 192.168.31.113, port: 2224, uri: http://192.168.31.113:2224
host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
host: 192.168.31.113, port: 2222, uri: http://192.168.31.113:2222
host: 192.168.31.113, port: 2224, uri: http://192.168.31.113:2224
host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
host: 192.168.31.113, port: 2222, uri: http://192.168.31.113:2222
host: 192.168.31.113, port: 2224, uri: http://192.168.31.113:2224
host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
host: 192.168.31.113, port: 2222, uri: http://192.168.31.113:2222
host: 192.168.31.113, port: 2224, uri: http://192.168.31.113:2224

BestAvailableRule

@Bean
public IRule ribbonRule() {
    return new BestAvailableRule();
}

If the browser is accessed directly, the test results are as follows (because the number of requests becomes 0 after each visit, and the next traversal will always be an instance of port 2223).

host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
host: 192.168.31.113, port: 2223, uri: http://192.168.31.113:2223
..

Simulating concurrent requests using wrk results in multiple instances of.

`1`	`wrk -c 1000 -t 10 -d 10s http://localhost:3333/test`

Reference https://fangjian0423.github.io/2017/01/29/loadbalance/

Table of Contents

Example to verify the LoadBalance function in Ribbon

RandomRule

RoundRobinRule

BestAvailableRule