Implementation of load balancer — Consistent hashing

Photo by Ian Keefe on Unsplash

In this series, I want to cover about some popular load balancer algorithms. I will explain how they work, and most importantly, how it can be implemented, so that you get a better understanding of the technique inside.

What is Load Balancer

Load balancing refers to efficiently distributing incoming network traffic across a group of backend servers, also known as a server farm or server pool.

In the old days, load balancing, distributing system, they are not such a popular topic back then, mainly because the lack of internet users. My friend had started a tech company back in 2011, AWS, Azure is not a common thing at the time, I remember the day my friend give me a visit to their server room, it’s a rack of routers, switches, line, etc, all in one place. If the electricity goes down, or fire happens, it can be a horrible disaster, the server and the database will be gone forever.

As the user base grows, servers are distributed all around the world. The big tech company like facebook, airbnb, they have thousands of, millions of servers, if one goes down, it will be no problem at all.

In order to distribute all the network traffic to multiple servers, load balancer comes into the stage. It will deliver your network packets based on your load balancer’s algorithms to balance your network traffic.

Algorithms

There are several load balancing algorithms in the market.

Round robins: Client requests are distributed to application servers in a cyclic manner, for instance, the first request will go to the first server, second request will go to the second server…

Least connection: the client distribute the packets to server that has the least number of active connections.

IP hash: Combine the source IP and destination IP to generate a unique hash, so the same client will always contact to the same server.

Consistent Hash: a distributed hashing scheme that operates independently of the number of servers or objects in a distributed hash table by assigning them a position on an abstract circle, or hash ring. This allows servers and objects to scale without affecting the overall system.

Photo by veeterzy on Unsplash

We will talk about them all in this series, but now, we are focusing on consistent hash. I will explain the components, the process and the implementation of consistent hash from now, sit tight…

Components

Route table: A hash table to store the nodes of server, a circle ring, not a sequential array like table.

Hash function: A hash function to convert to the key of entry in the hash table.

Node: The server node.

Process

Create node -> Add node to route table

Request comes -> Hash function to key -> get the closest key match -> get node in this key -> return node

Implementation

Now comes to the fun part, we will implement this algorithms in Java.

First, we define the node template and the hash function interface.

Here is our hash function implementation. We will use MD5 algorithm to hash our key.

On the last part of the doHash function, after we generate the hash using MD5, we need to clip the data byte. Because we are creating the circle ring, the key is just an index inside the routing table, we cannot make it infinity large. We set the range of the key, which is 0 ~ 2147483647 (signed 32 bits), and return the data in long type.

Next is to create the route table.

private final SortedMap<Long, T> ring = new TreeMap<>();

We use SortedMap in our case, which is easy to sort our key.

Before request comes in, we need to set up our nodes first.

We first get the key from the node, do a hash function, push the key and node as value into the ring.

The last thing is to create a getNode function, get the closest key from the ring.

If you don’t know what tailMap does, it will create a new sorted map, where all the keys are greater or equal to the current hash. If the hash is greatest, we will then use the first key of the ring.

Here is the full implementation of routing table.

Great! Everything should work now.

But don’t forget to add VirtualNode too.

Let say you have a high performance server, it can handle more request than others, you want this server to get more traffic. In this case, simple approach might be add the same node of this server many times in the ring. But the ring does not allow duplicate key, so what is the solution?

VirtualNode is the best option. It basically a normal node to the ring, but it’s a wrapper of an actual physical node. So if we return this VirtualNode, it will map to the actual node.

Here is the implementation.

TEST

Let test this thing.

ublic final class LoadBalancer {
    public static final void main(String[] args) {
        List<INode> nodes = List.of(new INode[]{
            new Node("127.0.0.1", "80"), new Node("127.0.0.2", "80"),
                new Node("127.0.0.3", "80"), new Node("127.0.0.4", "80")

        });
        RouteTable table = new RouteTable(nodes);

        // get random server
        for (int i = 1; i < 10; ++i) {
            System.out.println("Server " + i + " : " + table.getNode("192.1.4." + i).getIp());
        }
    }
}

We add 4 servers to the ring, write a for loop to imitate the server request.

Here is the result:

Server 1 : 127.0.0.4
Server 2 : 127.0.0.1
Server 3 : 127.0.0.4
Server 4 : 127.0.0.1
Server 5 : 127.0.0.1
Server 6 : 127.0.0.1
Server 7 : 127.0.0.4
Server 8 : 127.0.0.1
Server 9 : 127.0.0.1

Congratulations! We had create a load balancer.

I highly recommend to practice this using your own language. Although nowadays, service like Nginx is able to do the same thing faster, the implementation is always fun and we will find the new things to learn.

My whole implementation is hosted on github, welcome to check it out.

GitHub - lau1944/Load-balancer-in-java: Implementation of popular load balancing algorithms in Java

Hope you enjoy this article, more series is coming up soon.