Java Load Balancer Simulator Based on Random Array Queue

Thinking of there are hundreds of thousands of users request a website at the same time, we must have multiple servers to make sure our service is stable and won't out of usage. You may ask how could we distribute requests to these different servers, the answer is Load Balancer. Load Balancer is a service to distribute network traffic across multiple servers.

Question

The load balancer simulation maintains a random queue of queues and builds the computation around an inner loop where each new request for service goes on the smallest of a sample of queues, using the sample() method from RandomQueue to randomly sample queues.

Implementing Steps

Different load balancing algorithms have different application scenarios, such as Round Robin, IP Hash, Least Connections. This time we are going to use a random queue, an easy implementation of Least Connections, to simulate load balancer. Let's create a Load Balancer Simulator based on a random queue.

1. Use the code snippets on RandomArrayQueue.java
2. Create a random queue with a specified size to maintain the servers
3. Dequeue a server randomly
4. Dequeue other servers with a specified sample-times until pick out the server with the minimum requests passed to.
5. passing a request to this server

Solution

/******************************************************************************
 *  Compilation:  javac LoadBalance.java
 *  Execution:    java LoadBalance 5 5000 0
 *  Dependencies:  RandomArrayQueue.java @link https://mrtan.me/post/22.html
 *
 *  Passing m requests to n servers with a limited random picking times.
 *
 *  % java LoadBalance 5 5000 0
 *   total Servers: 5
 *   total Reqeusts: 5000
 *   Sample Time: 0
 *   [956.0, 995.0, 959.0, 1080.0, 1010.0]
 *
 ******************************************************************************/

import java.util.Arrays;

public class LoadBalance {
    public static void main(String[] args) {
        int totalServers= Integer.parseInt(args[0]);
        int totalRequests = Integer.parseInt(args[1]);
        int sampleTime = Integer.parseInt(args[2]);

        System.out.println("total Servers: " + totalServers);
        System.out.println("total Reqeusts: " + totalRequests);
        System.out.println("Sample Time: " + sampleTime);

        // Create server queues.
        RandomArrayQueue<Queue<Integer>> servers;
        servers = new RandomArrayQueue<Queue<Integer>>();
        for (int i = 0; i < totalServers; i++) {
            servers.enqueue(new Queue<Integer>());
        }

        // Passing reqeusts to servers  
        for (int j = 0; j < totalRequests; j++) {
            Queue<Integer> min = servers.sample();
            for (int k = 1; k < sampleTime; k++) {
                // Pick a sample
                Queue<Integer> queue = servers.sample();
                if (queue.size() < min.size()) min = queue;
            }

            // min surpposed to be the shortest server queue.
            min.enqueue(j);
        }

        int i = 0;
        double[] lengths = new double[totalServers];
        for (Queue<Integer> queue : servers)
            lengths[i++] = queue.size();

        System.out.println(Arrays.toString(lengths));
    }
}

Output

-> java LoadBalance 5 5000 0
total Servers: 5
total Reqeusts: 5000
Sample Time: 0
[956.0, 995.0, 959.0, 1080.0, 1010.0]

-> java LoadBalance 5 5000 2
total Servers: 5
total Reqeusts: 5000
Sample Time: 2
[999.0, 1000.0, 1000.0, 1001.0, 1000.0]

image - result 1

image - result 2

The second output gets a well-balanced result, seems like the 2 is a good sample value for 5000 / 5.

The time complexity of this implementation is Θ(n) because it's an array-based queue which the BIG O of access item isΘ(1), so the total complexity depends on sample-times in the implementation steps.