Implement Consistent Hashing for Load Balancing - Load Balancers

                      TASK
                    

Implementation

Implement consistent hashing for stateful load balancing:

Assign servers to positions on hash ring
Hash each request key to ring position
Route to server clockwise from hash position
When servers join/leave, only nearby keys move

This maintains cache locality - same user always hits same server, maximizing cache hits.

Sample Test Cases

Consistent routingTimeout: 5000ms

Input

{
  "src": "c0",
  "dest": "n1",
  "body": {
    "type": "init",
    "msg_id": 1,
    "node_id": "n1",
    "node_ids": [
      "n1"
    ]
  }
}

Expected Output

{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}

Minimal redistributionTimeout: 5000ms

Input

{
  "src": "c0",
  "dest": "n1",
  "body": {
    "type": "init",
    "msg_id": 1,
    "node_id": "n1",
    "node_ids": [
      "n1"
    ]
  }
}

Expected Output

{"src":"n1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}

Hints

Hint 1▾

Hash request key to server

Hint 2▾

Same key always goes to same server

Hint 3▾

Minimal redistribution on server changes

                      OVERVIEW
                    

Theoretical Hub

Consistent Hashing for LB

For stateful services or caching, you want related requests to hit the same server. Consistent hashing routes based on a key (user ID, session), ensuring same key -> same server while minimizing redistribution.

Virtual Nodes

With few servers, distribution can be uneven. Virtual nodes map each server to many ring positions, smoothing the distribution.

Key Concepts

consistent hashingkey affinitycache locality

main.py

python

#!/usr/bin/env python3
import sys
import json
import hashlib
import bisect
class ConsistentHashLB:
    def __init__(self, servers, replicas=100):
        self.replicas = replicas
        self.ring = {}
        self.sorted_keys = []
        self.servers = set()
        
        for server in servers:
            self.add_server(server)
    
    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)
    
    def add_server(self, server):
        # TODO: Add server with virtual nodes
        pass
    
    def remove_server(self, server):
        # TODO: Remove server from ring
        pass
    
    def get_server(self, key):
        # TODO: Find server for key
        pass
if __name__ == "__main__":
    pass