Implement Consistent Hashing for Load Balancing - Load Balancers

                      TASK
                    

Implementation

Consistent hashing for load balancing ensures that the same client always routes to the same backend. This is useful for caching layers where session state or cache locality matters.

Why consistent hashing for LB?

Problem: modulo hashing routes change when backends change
  client_1 → hash("client_1") % 3 = backend-1
  client_2 → hash("client_2") % 3 = backend-2

  Add backend-4:
  client_1 → hash("client_1") % 4 = backend-3 ❌ Different!
  All clients remap = cache cold miss

Solution: consistent hashing
  client_1 → hash ring → backend-1
  client_2 → hash ring → backend-2

  Add backend-4:
  client_1 → hash ring → backend-1 ✓ Same!
  Only 25% of clients remap

Algorithm:

function routeClient(clientId: string, backends: Backend[]): string {
  // Hash client ID to point on ring
  const clientPoint = hash(clientId) % 2^32;

  // Place backends on ring
  const backendPoints = backends.map(b => ({
    backend: b.name,
    point: hash(b.name) % 2^32
  }));

  // Sort by point
  backendPoints.sort((a, b) => a.point - b.point);

  // Find first backend clockwise from client point
  for (const bp of backendPoints) {
    if (bp.point >= clientPoint) {
      return bp.backend;
    }
  }

  // Wrap around to first backend
  return backendPoints[0].backend;
}

Example consistent hashing:

// Hash ring (simplified):
// 0°    : backend-1
// 120°  : backend-2
// 240°  : backend-3

// Client requests:
Request:  {"type": "http_request", "msg_id": 1, "client_id": "alice", "path": "/api/data", "algorithm": "consistent-hash"}
Response: {"type": "http_response", "in_reply_to": 1, "backend": "backend-2", "hash_ring_position": 45}

// Same client always routes to same backend:
Request:  {"type": "http_request", "msg_id": 2, "client_id": "alice", "path": "/api/data", "algorithm": "consistent-hash"}
Response: {"type": "http_response", "in_reply_to": 2, "backend": "backend-2", "hash_ring_position": 45}

// Different client routes to potentially different backend:
Request:  {"type": "http_request", "msg_id": 3, "client_id": "bob", "path": "/api/data", "algorithm": "consistent-hash"}
Response: {"type": "http_response", "in_reply_to": 3, "backend": "backend-1", "hash_ring_position": 300}

Sample Test Cases

Same client always routes to same backendTimeout: 5000ms

Input

{"src":"client","dest":"lb","body":{"type":"init","msg_id":1,"backends":["backend-1","backend-2","backend-3"],"algorithm":"consistent-hash"}}
{"src":"client","dest":"lb","body":{"type":"http_request","msg_id":2,"client_id":"alice"}}
{"src":"client","dest":"lb","body":{"type":"http_request","msg_id":3,"client_id":"alice"}}
{"src":"client","dest":"lb","body":{"type":"http_request","msg_id":4,"client_id":"alice"}}

Expected Output

{"src": "lb", "dest": "client", "body": {"type": "init_ok", "in_reply_to": 1}}

Backend addition causes minimal remappingTimeout: 5000ms

Input

{"src":"client","dest":"lb","body":{"type":"init","msg_id":1,"backends":["b1","b2","b3"],"algorithm":"consistent-hash"}}
{"src":"client","dest":"lb","body":{"type":"test_remap","msg_id":2,"new_backend":"b4","clients":["c1","c2","c3","c4","c5","c6","c7","c8","c9","c10"]}}

Expected Output

{"src": "lb", "dest": "client", "body": {"type": "init_ok", "in_reply_to": 1}}

Hints

Hint 1▾

Hash client_id or session_id to a point on the hash ring

Hint 2▾

Route to the first backend clockwise from that point

Hint 3▾

Same client always routes to same backend (sticky routing)

Hint 4▾

When backend added, only 1/N of clients remap

Hint 5▾

Use virtual nodes for better distribution

Resources

Consistent Hashing for Load Balancing

NGINX documentation on consistent hashing load balancing

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

consistent hashingsession affinitycache coherencyminimal disruptionbackend additions/removals

main.py

python