Load Balancer Algorithms

Distributing the Load

A load balancer sits in front of a pool of servers and decides which server handles each incoming request. The choice of algorithm has significant implications for performance, fairness, and resilience — especially when servers are added or removed.

1. Round Robin

The simplest approach: cycle through servers in order.

class RoundRobinBalancer:
    def __init__(self, servers):
        self.servers = servers
        self.index = 0

    def get_server(self):
        server = self.servers[self.index]
        self.index = (self.index + 1) % len(self.servers)
        return server

• Pro: Zero overhead, perfectly fair request distribution.
• Con: Assumes all servers have equal capacity and all requests have equal cost. A single slow request on Server A doesn't prevent it from receiving the next request.

2. Least Connections

Send each new request to the server with the fewest active connections.

class LeastConnectionsBalancer:
    def __init__(self, servers):
        self.connections = {s: 0 for s in servers}

    def get_server(self):
        server = min(self.connections, key=self.connections.get)
        self.connections[server] += 1
        return server

    def release(self, server):
        self.connections[server] -= 1

• Pro: Naturally adapts to slow requests — a server handling a long-running WebSocket connection won't receive new requests until it frees up.
• Con: Requires tracking connection state. More complex to implement correctly in a distributed load balancer (requires shared state or gossip).

3. Consistent Hashing (The SRE Favorite)

This is the algorithm that appears most often in SRE interviews because it solves a subtle but critical problem in distributed systems.

The problem with naive hashing:

# Naive approach
server_index = hash(request_key) % num_servers

This works fine until you add or remove a server. When num_servers changes from 3 to 4, the modulo result changes for almost every key. Every cached item is suddenly mapped to the wrong server — a cache stampede that can bring down your origin servers.

The consistent hashing solution:

Map both servers and requests onto a conceptual ring (values 0 to 2³²). To find a request's server, walk clockwise on the ring until you hit a server.

import hashlib
import bisect

class ConsistentHashRing:
    def __init__(self, servers, replicas=100):
        self.replicas = replicas  # Virtual nodes per server
        self.ring = {}            # hash -> server name
        self.sorted_keys = []     # Sorted list of hashes on the ring

        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):
        # Add multiple virtual nodes to ensure even distribution
        for i in range(self.replicas):
            key = self._hash(f"{server}:{i}")
            self.ring[key] = server
            bisect.insort(self.sorted_keys, key)

    def remove_server(self, server):
        for i in range(self.replicas):
            key = self._hash(f"{server}:{i}")
            del self.ring[key]
            self.sorted_keys.remove(key)

    def get_server(self, request_key):
        if not self.ring:
            return None
        h = self._hash(request_key)
        # Find the first server hash >= request hash
        idx = bisect.bisect_right(self.sorted_keys, h) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[idx]]

Why virtual nodes (replicas)? With only 3 real servers on the ring, the distribution of requests is uneven — one server might own 60% of the ring by chance. Adding 100 virtual nodes per server (300 points total) distributes ownership much more evenly.

The key benefit: When you add or remove a server, only the requests that were mapped to that server's ring segment need to be remapped. All other requests are unaffected. In a 10-server cluster, adding one server remaps roughly 1/11 of requests — not all of them.