Scalable Load Balancing with Consistent Hashing

In the world of micro-services, load balancing is a cornerstone to achieve scalability. There are various load balancing algorithms that distributes incoming traffic to multiple servers. This prevents a single server from becoming a bottleneck and ensuring quick response time and less outage. Among multiple load balancing algorithms consistent hashing is an powerful technique of load balancing

Traditional Load balancing algorithms

Imagine a simple scenario with three servers (A, B, C) and a traditional load balancer using a round-robin or modulo-based approach. When a request comes, it is directed to a server based on a simple algorithm. This works fine until you need to add a new server (D), remove an existing one or a server crashes down due to some technical issue.

With traditional methods, adding or removing a server often needs a complete remapping of requests. This can lead to:

• Cache Invalidation: If your servers cache data, a remapping means a large portion of your cache becomes invalid, leading to a surge of requests to the backend database as server did not find any cache for remapped request. So, Many requests simultaneously hitting the database can overwhelm it.
• Downtime/Low performance: The remapping process can introduce latency or even brief periods of unavailability.

These issues become amplified in microservices architectures and cloud environments where services are constantly being scaled up and down.

Hello! Consistent hashing

Consistent Hashing is a special kind of hashing that minimizes the impact of adding or removing a server on the overall distribution of request over hash of servers. Instead of remapping every request only a small fraction of requests are affected.

How it works

Think of a a ring, that represents your hash space for servers and requests. Both server and requests are mapped to the hash ring using a hash function.

• Server Placement: Our first task is to place the servers on the hash ring. Each server is hashed using a hash algorithm and placed on the specific position on the ring

• Placement of requests: For incoming requests too we hash them and place them on the ring. Request and server may/may not point to same position on the ring.

• Server assignment: Once both server and request is mapped to the ring, each request gets the next available server on the ring, your direction or traversal may be clockwise or anticlockwise. The first server we encounter while traversing that server gets allocated to the request.

Lets take reference to above image, it has a ring with hash space of n = 100 and four servers (A,B,C,D), number within them represent the index/hash where are located on the ring and we are traversing in clockwise direction on the ring.

So, if any incoming request with hash 10 will be allocated to just next server in clockwise direction, in this case its Server B.

Note: Hash space should be large enough to avoid collision based on your hashing algorithm.

How this makes the difference

Now, let us see what happens when we add or remove a server:

• Adding a Server: When a new server is added to the ring, it only takes over a portion of the requests from its neighbour. The vast majority of other requests remain mapped to their original servers. For example, if we add a Server E which has value 40 between Server B and Server C. Only requests of value greater that hash value 20 and less that equal to 40 will be remapped to Server E, rest all mapping will remain same.

• Removing a Server: When a server is removed, its requests are simply re-mapped to next clockwise neighbour. Again, only a localized change occurs. Again, if we remove Server E all the request getting assigned to E will automatically get re-mapped to Server C.

This localized remapping is the core benefit of Consistent Hashing.

Benefits for Load Balancing:

• Reduced re-mapping: This reduces the number of requests that need to be re-mapped when servers are added or removed.

• Improved Cache Utilization: Preserves a significant amount of cached data, reducing the load on backend systems.

• Enhanced Scalability: Allows for seamless scaling up and down of server capacity without significant performance issues.

• Reduced Thundering Herd: Prevents a sudden surge of requests to the database.

• Better Availability: Contributes to more stable and available systems during scaling events.

Drawbacks of Consistent Hashing

• Uneven distribution: With the distribution of requests on the ring may not be even, it may happen that a server in ring gets most of the requests and other does not get any traffic at all. To mitigate this we use virtual nodes. Instead of mapping physical server directly on the ring we map multiple virtual nodes on the ring that point to the same physical. This helps a single physical server to appear at multiple places on the ring, and thus avoid uneven distribution of requests. The quality of hash function used also has a significant affect on distribution.

• Performance overhead: Repeated hashing of requests and traversing the ring even with using best data structures and optimised algorithms may introduce slight performance overhead as compared to simple hashing techniques.

• Cold start issue: When a new server is added to the ring, it is likely to have an empty cache for that hash in the backend, so this may increase load on backend databases/cache for quite some time.

Implementation of Consistent Hashing

While the concept is straightforward, implementing a robust Consistent Hashing solution often involves libraries or frameworks that handle the complexities of managing the hash ring, virtual nodes, and server discovery, but for better understanding we will implement a simple consistent hash scheduler.

• Create a class in java ConsistantHashScheduler

public class ConsistantHashScheduler{
    private static final Logger logger = LogManager.getLogger(ConsistantHashScheduler.class);

    private ArrayList<Server> nodes;
    private ArrayList<Integer> keys;
    private ArrayList<Server> servers;
    private int maxPoolSize;

    public ConsistantHashScheduler(ArrayList<Server> servers, int maxPoolSize) {
            logger.info("Initializion a consistent hash scheduler with pool size: {}",maxPoolSize);
        this.maxPoolSize = maxPoolSize;
        this.servers = servers;
            this.keys = new ArrayList<>();
        this.nodes = new ArrayList<>();
    }
}

• Add hash function of your choice

private int getHash(String ip) throws NoSuchAlgorithmException {
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
            byte[] hashBytes = digest.digest(ip.getBytes(StandardCharsets.UTF_8));

            int hash = 0;
            for (int i = 0; i < 4; i++) {
                hash <<= 8;
                hash |= (hashBytes[i] & 0xFF);
            }
            return (hash & Integer.MAX_VALUE) % this.maxPoolSize;
    }

This method hashes an IP using SHA-256, extracts a 32-bit integer, and scales it for pool size, ensuring even distribution.

• Now, implement addServer method.

public void addServer(Server server) throws Exception {
        if(keys.size() == this.maxPoolSize) {
            throw new Exception("Max server pool size overflow");
        }

        logger.info("adding new server: {}",server.toString());

        int key = this.getHash(server.getUrl());
        int index = Collections.binarySearch(this.keys, key);



        if(index > 0 && this.keys.get(index) == key) {
            throw new Exception("Collosion occured for server "+ server.toString());
        }

        int insertionPoint = -(index+1);

        this.keys.add(insertionPoint,key);
        this.nodes.add(insertionPoint,server);

        return;
    }

This addServer method adds a new server to a Consistent Hashing ring. It calculates the hash of server, finds its insertion point in a sorted list of keys to maintain the ring order, and then inserts both the hash and the server. It handles pool size limits and hash collisions.

• Add removeServer method.

public void removeServer(Server server) throws Exception {

        if(this.keys.size() == 0) {
            throw new Exception("No nodes in the server pool");
        }

        int key = this.getHash(server.getUrl());

        int index = Collections.binarySearch(this.keys, key);

        if(index < 0) {
            throw new Exception("Unknown server, not present in nodes");
        }

        this.keys.remove(index);
        this.nodes.remove(index);

        return;

    }

This removeServer function deletes a server from the Consistent Hashing ring. It hashes the URL of server, finds its position via binary search, and removes its key and the server object from the sorted lists. It validates against an empty pool or unknown servers.

• Let's schedule some requests.

public Server schedule(HttpExchange exchange) throws NoSuchAlgorithmException {
        int key = this.getHash(exchange.getRemoteAddress().getHostName());
        int index = Collections.binarySearch(keys, key);

        int nodePoint;

        if(index >= 0) {
            nodePoint = index;
        }else {
            nodePoint = ((-(index+1))%this.keys.size());
        }
        return this.servers.get(nodePoint);

    }

This schedule method is core logic of a load balancer. It hashes the incoming request's client IP, then uses binary search on the sorted hash ring (keys) to find the appropriate server. If no exact match, it calculates the next clockwise server using modulo, returning the chosen Server object.

The summary of the above implementation can be found here.

At last

Consistent Hashing offers an efficient approach to load balancing. By minimising the impact of frequent changes, it ensures greater stability and availability, allowing the systems to scale better. If you are building or optimizing a distributed system, understanding and implementing Consistent Hashing is an important tool in your skill set.