Decodes / Post

Load Balancer Algorithms: Decoded

How traffic is distributed across homogeneous and heterogeneous backends, and when each routing strategy fails.

Vishal Yadav18 min read

The Traffic Dispatcher

In the world of distributed systems, no single server can withstand the brunt of internet-scale traffic. To scale horizontally, we introduce a fleet of servers and place a Load Balancer (LB) at the gateway.

The load balancer's task is simple to state but complex to execute: distribute incoming requests across a pool of backend servers in a way that maximizes throughput, minimizes latency, and prevents any single server from becoming a bottleneck.

Under the hood, the load balancer must make routing decisions in microseconds. The strategy it uses is defined by its Load Balancing Algorithm. These algorithms are generally divided into two classes:

  1. Static Algorithms: Hardcoded rules based purely on server identity, IP addresses, or weights, without querying the actual live performance state of the backends.
  2. Dynamic Algorithms: Stateful decisions based on real-time feedback loops, tracking active connection counts, latencies, or CPU load.

Here is the deep dive into the four foundational routing strategies, their mathematical formulations, and how to implement them.

1. Weighted Round Robin

Standard Round Robin is the simplest load balancing algorithm: it distributes requests sequentially (S1,S2,S3,…S_1, S_2, S_3, \dots) down the line. However, it operates under a flawed assumption: that all backend servers are identical in hardware capacity (homogeneous).

In real production environments, you often have a mix of instance types. If you route traffic equally between a 2-core VPS and a 64-core bare-metal machine, you will underutilize the giant and crash the small instance.

Weighted Round Robin solves this by assigning an integer weight WiW_i to each server representing its capacity.

Weighted Round Robin Diagram

Mathematical Formulation

Implementation: Smooth Weighted Round Robin

A naive implementation might send W1W_1 requests to S1S_1, then W2W_2 requests to S2S_2. This creates "bursty" traffic patterns, where S1S_1 is bombarded with back-to-back requests while others sit idle.

To prevent this, production balancers like Nginx use a Smooth Weighted Round Robin algorithm, which interleaves the requests.

Java Implementation

import java.util.List;
import java.util.ArrayList;
import java.util.Map;
 
class Server {
    String id;
    int weight;
    int currentWeight;
 
    Server(String id, int weight) {
        this.id = id;
        this.weight = weight;
        this.currentWeight = 0;
    }
}
 
public class SmoothWeightedRoundRobin {
    private final List<Server> servers = new ArrayList<>();
 
    public SmoothWeightedRoundRobin(Map<String, Integer> serverWeights) {
        serverWeights.forEach((id, weight) -> servers.add(new Server(id, weight)));
    }
 
    public synchronized String next() {
        int totalWeight = 0;
        Server selectedServer = null;
 
        // Step 1: Add effective weight to currentWeight of each server
        for (Server server : servers) {
            server.currentWeight += server.weight;
            totalWeight += server.weight;
 
            // Step 2: Find the server with the maximum currentWeight
            if (selectedServer == null || server.currentWeight > selectedServer.currentWeight) {
                selectedServer = server;
            }
        }
 
        if (selectedServer == null) {
            throw new IllegalStateException("No backend servers available.");
        }
 
        // Step 3: Decrement the selected server's currentWeight by totalWeight
        selectedServer.currentWeight -= totalWeight;
 
        return selectedServer.id;
    }
}

TypeScript Implementation

interface Server {
  id: string;
  weight: number;
  currentWeight: number;
}
 
class SmoothWeightedRoundRobin {
  private servers: Server[];
 
  constructor(serverWeights: { [id: string]: number }) {
    this.servers = Object.entries(serverWeights).map(([id, weight]) => ({
      id,
      weight,
      currentWeight: 0,
    }));
  }
 
  public next(): string {
    let totalWeight = 0;
    let selectedServer: Server | null = null;
 
    // Step 1: Add effective weight to currentWeight of each server
    for (const server of this.servers) {
      server.currentWeight += server.weight;
      totalWeight += server.weight;
 
      // Step 2: Find the server with the maximum currentWeight
      if (!selectedServer || server.currentWeight > selectedServer.currentWeight) {
        selectedServer = server;
      }
    }
 
    if (!selectedServer) {
      throw new Error("No backend servers available.");
    }
 
    // Step 3: Decrement the selected server's currentWeight by totalWeight
    selectedServer.currentWeight -= totalWeight;
 
    return selectedServer.id;
  }
}
 
// Example usage:
// Servers: A (w=4), B (w=2), C (w=1)
const balancer = new SmoothWeightedRoundRobin({ A: 4, B: 2, C: 1 });
const sequence = Array.from({ length: 7 }, () => balancer.next());
console.log(sequence); // Output: [ 'A', 'B', 'A', 'C', 'A', 'B', 'A' ] (Interleaved and smooth!)

When it Fails

Weighted Round Robin is ideal for state-free web applications with homogeneous query complexities. It fails when request processing times are highly variable. If Server A receives three lightweight static asset requests and Server B receives three heavy database-reporting queries, Server B will lock up, even if their weights are identical.

2. Least Connections

To handle workloads where requests take varying times to complete, the load balancer must become dynamic. It needs to track active state.

The Least Connections algorithm routes incoming requests to the server with the fewest active transaction channels at that exact moment.

Least Connections Diagram

Mathematical Formulation

Implementation

Tracking active connections requires the load balancer to intercept both the request and the response lifecycle to increment and decrement counter states.

Java Implementation

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.List;
 
public class LeastConnectionsBalancer {
    private final Map<String, Integer> activeConnections = new ConcurrentHashMap<>();
    private final List<String> servers;
 
    public LeastConnectionsBalancer(List<String> servers) {
        this.servers = servers;
        for (String server : servers) {
            activeConnections.put(server, 0);
        }
    }
 
    public String selectServer() {
        String selectedServer = servers.get(0);
        int minConnections = Integer.MAX_VALUE;
 
        for (String server : servers) {
            int connections = activeConnections.getOrDefault(server, 0);
            if (connections < minConnections) {
                minConnections = connections;
                selectedServer = server;
            }
        }
 
        activeConnections.put(selectedServer, minConnections + 1);
        return selectedServer;
    }
 
    public void releaseServer(String serverId) {
        activeConnections.computeIfPresent(serverId, (k, v) -> v > 0 ? v - 1 : 0);
    }
}

TypeScript Implementation

class LeastConnectionsBalancer {
  private activeConnections: Map<string, number> = new Map();
 
  constructor(private servers: string[]) {
    for (const server of servers) {
      this.activeConnections.set(server, 0);
    }
  }
 
  public selectServer(): string {
    let minConnections = Infinity;
    let selectedServer = this.servers[0];
 
    for (const server of this.servers) {
      const connections = this.activeConnections.get(server) || 0;
      if (connections < minConnections) {
        minConnections = connections;
        selectedServer = server;
      }
    }
 
    // Simulate opening connection
    this.activeConnections.set(selectedServer, minConnections + 1);
    return selectedServer;
  }
 
  public releaseServer(serverId: string): void {
    const current = this.activeConnections.get(serverId) || 0;
    if (current > 0) {
      this.activeConnections.set(serverId, current - 1);
    }
  }
}

Best Use Cases

  • Long-Lived Connections: Ideal for WebSockets, chat servers, SSH tunnels, or database connection pools where sessions stay open for minutes or hours.
  • Varying Workloads: Prevents server starvation when requests have highly variable computational complexity.

When it Fails

Least Connections assumes all servers process requests at the same speed. If you have an instance pool with a slow server (e.g. 1 CPU core) and a fast server (e.g. 16 CPU cores), the slow server will queue up requests because it cannot flush them out fast enough. Despite being overloaded, its connection count might drop slower, or worse—if it crashes and rejects requests instantly, its connection count drops to zero, causing the balancer to flood it with even more traffic (the Dead Server Black Hole trap).

3. IP Hash

There are times when a client's state must remain bound to a specific backend server. For instance, if user session state is stored in server memory (rather than a shared Redis cache), a client must hit the same server for every subsequent API call. This is known as Session Stickiness or Sticky Sessions.

IP Hash accomplishes this by hashing the client's IP address and using it to map them to a specific backend slot.

IP Hash Diagram

Mathematical Formulation

The Catastrophe of Modulo: The Need for Consistent Hashing

While the modulo-based mapping is fast (O(1)O(1)) and stateless, it suffers from a fatal flaw: scalability instability.

If you have N=4N = 4 servers and add a 5th server (N=5N = 5), the divisor changes. Almost every client IP will resolve to a different index:

H(IP)(mod4)≠H(IP)(mod5)H(IP) \pmod 4 \neq H(IP) \pmod 5

This causes nearly 100% of all sessions or caches to be invalidated and shifted, causing database thrashing as millions of users re-authenticate.

To solve this, modern production balancers implement Consistent Hashing using a Hash Ring.

Java Implementation

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.List;
 
public class ConsistentHashRing {
    private final TreeMap<Long, String> ring = new TreeMap<>();
    private final int virtualNodes;
 
    public ConsistentHashRing(List<String> servers, int virtualNodes) {
        this.virtualNodes = virtualNodes;
        for (String server : servers) {
            addServer(server);
        }
    }
 
    private long hash(String key) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] digest = md.digest(key.getBytes(StandardCharsets.UTF_8));
            // Read first 4 bytes as an unsigned 32-bit integer (stored in long)
            return ((long) (digest[3] & 0xFF) << 24) |
                   ((long) (digest[2] & 0xFF) << 16) |
                   ((long) (digest[1] & 0xFF) << 8)  |
                   ((long) (digest[0] & 0xFF));
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("MD5 algorithm not found", e);
        }
    }
 
    public void addServer(String server) {
        for (int i = 0; i < virtualNodes; i++) {
            String virtualNodeKey = server + "-vn-" + i;
            ring.put(hash(virtualNodeKey), server);
        }
    }
 
    public void removeServer(String server) {
        for (int i = 0; i < virtualNodes; i++) {
            String virtualNodeKey = server + "-vn-" + i;
            ring.remove(hash(virtualNodeKey));
        }
    }
 
    public String getServer(String clientIp) {
        if (ring.isEmpty()) {
            throw new IllegalStateException("Hash ring is empty.");
        }
        long hashVal = hash(clientIp);
        SortedMap<Long, String> tailMap = ring.tailMap(hashVal);
        long nodeHash = tailMap.isEmpty() ? ring.firstKey() : tailMap.firstKey();
        return ring.get(nodeHash);
    }
}

TypeScript Implementation

import * as crypto from "crypto";
 
class ConsistentHashRing {
  private ring: Map<number, string> = new Map();
  private sortedKeys: number[] = [];
 
  constructor(servers: string[], private virtualNodes: number = 100) {
    for (const server of servers) {
      this.addServer(server);
    }
  }
 
  private hash(key: string): number {
    const hash = crypto.createHash("md5").update(key).digest();
    // Read first 4 bytes as a 32-bit unsigned integer
    return hash.readUInt32BE(0);
  }
 
  public addServer(server: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const virtualNodeKey = `${server}-vn-${i}`;
      const hashVal = this.hash(virtualNodeKey);
      this.ring.set(hashVal, server);
      this.sortedKeys.push(hashVal);
    }
    this.sortedKeys.sort((a, b) => a - b);
  }
 
  public removeServer(server: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const virtualNodeKey = `${server}-vn-${i}`;
      const hashVal = this.hash(virtualNodeKey);
      this.ring.delete(hashVal);
    }
    this.sortedKeys = this.sortedKeys.filter(k => this.ring.has(k));
  }
 
  public getServer(clientIp: string): string {
    if (this.ring.size === 0) {
      throw new Error("Hash ring is empty.");
    }
    const hashVal = this.hash(clientIp);
    
    // Find the first virtual node with a hash value >= client's hash
    let idx = this.sortedKeys.findIndex(k => k >= hashVal);
    
    // If we reach the end of the ring, wrap around to index 0
    if (idx === -1) {
      idx = 0;
    }
    
    return this.ring.get(this.sortedKeys[idx])!;
  }
}

By placing servers on a circular ring of 232−12^{32}-1 points, adding or removing a server only invalidates a fraction (≈1/N\approx 1/N) of keys, keeping the system stable.

4. Least Response Time

The most advanced dynamic balancing strategy is Least Response Time (also referred to as Least Processing Time or Least Time).

Instead of relying purely on connection counts, this algorithm monitors two parameters:

  1. Active concurrent connections.
  2. The response latency (usually calculated as a moving average of recent request-response cycles).

It routes incoming traffic to the server that yields the lowest expected latency coefficient.

Least Response Time Diagram

Mathematical Formulation

Using Ci×TiC_i \times T_i strikes a perfect balance. If a server has low latency but a massive queue of connections, the product rises, diverting traffic. If a server has few connections but is extremely slow, the product also rises, protecting it.

Implementation

Here is a logic engine showing how the balancer tracks connection counts and exponentially decays response time measurements:

Java Implementation

import java.util.List;
import java.util.ArrayList;
 
class ServerPerformance {
    String id;
    int activeConnections;
    double ewmaLatencyMs;
 
    ServerPerformance(String id) {
        this.id = id;
        this.activeConnections = 0;
        this.ewmaLatencyMs = 50.0; // Default baseline latency assumption
    }
}
 
public class LeastResponseTimeBalancer {
    private final List<ServerPerformance> servers = new ArrayList<>();
    private final double alpha = 0.2; // EWMA decay factor (20% weight to new measurement)
 
    public LeastResponseTimeBalancer(List<String> serverIds) {
        for (String id : serverIds) {
            servers.add(new ServerPerformance(id));
        }
    }
 
    public synchronized String selectServer() {
        double bestMetric = Double.MAX_VALUE;
        ServerPerformance selected = null;
 
        for (ServerPerformance server : servers) {
            double metric = server.activeConnections * server.ewmaLatencyMs;
            if (metric < bestMetric) {
                bestMetric = metric;
                selected = server;
            }
        }
 
        if (selected == null) {
            selected = servers.get(0);
        }
 
        selected.activeConnections++;
        return selected.id;
    }
 
    public synchronized void recordResponse(String serverId, double actualLatencyMs) {
        for (ServerPerformance server : servers) {
            if (server.id.equals(serverId)) {
                if (server.activeConnections > 0) {
                    server.activeConnections--;
                }
                // Calculate new EWMA latency
                server.ewmaLatencyMs = (alpha * actualLatencyMs) + ((1 - alpha) * server.ewmaLatencyMs);
                break;
            }
        }
    }
}

TypeScript Implementation

interface ServerPerformance {
  id: string;
  activeConnections: number;
  ewmaLatencyMs: number; // Exponentially Weighted Moving Average
}
 
class LeastResponseTimeBalancer {
  private servers: ServerPerformance[];
  private alpha = 0.2; // EWMA decay factor (gives 20% weight to the latest measurement)
 
  constructor(serverIds: string[]) {
    this.servers = serverIds.map(id => ({
      id,
      activeConnections: 0,
      ewmaLatencyMs: 50, // Start with a default baseline latency assumption
    }));
  }
 
  public selectServer(): string {
    let bestMetric = Infinity;
    let selected: ServerPerformance | null = null;
 
    for (const server of this.servers) {
      const metric = server.activeConnections * server.ewmaLatencyMs;
      if (metric < bestMetric) {
        bestMetric = metric;
        selected = server;
      }
    }
 
    if (!selected) {
      selected = this.servers[0];
    }
 
    selected.activeConnections++;
    return selected.id;
  }
 
  public recordResponse(serverId: string, actualLatencyMs: number): void {
    const server = this.servers.find(s => s.id === serverId);
    if (server) {
      // Decrement the active connection count
      if (server.activeConnections > 0) {
        server.activeConnections--;
      }
      // Calculate new EWMA latency
      server.ewmaLatencyMs = (this.alpha * actualLatencyMs) + ((1 - this.alpha) * server.ewmaLatencyMs);
    }
  }
}

Why it is the Best Defense Against Cascading Failures

In distributed systems, a failing server often slows down before crashing (due to memory leaks, database connection pool exhaustion, or CPU throttling).

  • In Round Robin, traffic keeps hammering the slow server, worsening its condition.
  • In Least Connections, if requests stack up on the slow server, it eventually stops receiving traffic, but only after its queue fills up.
  • In Least Response Time, the moment a server's latency spikes from 20ms to 800ms, the routing metric increases by 40x, routing traffic away immediately. It isolates degraded servers in real-time.

Summary Comparison

AlgorithmDecision StateSession StickyBest Used ForPrimary Downfall
Round RobinStatic (none)NoHomogeneous nodes, uniform workloadsSlow nodes get overloaded
Weighted Round RobinStatic (static weights)NoHeterogeneous nodes, uniform workloadsVulnerable to varying query complexity
Least ConnectionsDynamic (connection counts)NoLong-lived TCP/WebSocket sessionsSlow nodes build queues
IP Hash / Consistent HashStatic (client IP)YesStateful applications, caching layersHard to balance if clients sit behind NAT/VPNs
Least Response TimeDynamic (connections + latency)NoDynamic microservices, cloud deploymentsHigh tracking and monitoring overhead

By selecting the right load balancer algorithm, you align your traffic distribution with the physical capacity and logical requirements of your infrastructure.