Load Balancing Algorithms

Load balancing is an important aspect of any system architecture designed to handle a significant volume of requests. Without it, a single server could become overwhelmed, leading to slowdowns, outages, and an overall degraded user experience. Load balancing distributes incoming traffic across multiple servers, ensuring that no single server is overloaded while maximizing resource utilization and minimizing latency. This post goes into the various algorithms employed in load balancing, explaining their strengths and weaknesses with illustrative examples.

Types of Load Balancers

Before diving into algorithms, it’s important to understand the different types of load balancers:

• Hardware Load Balancers: Dedicated physical devices that manage traffic distribution. They are typically more expensive but offer high performance and reliability.

• Software Load Balancers: Run as software on servers, offering flexibility and cost-effectiveness but potentially lower performance than hardware solutions. They can be cloud-based or on-premise.

Load Balancing Algorithms

Several algorithms are used to distribute traffic effectively. Here are some of the most common:

1. Round Robin

This is the simplest algorithm. It distributes requests sequentially to each server in a predefined order.

Diagram:

graph LR
    C[Client]
    LB((Load Balancer))
    S1[Server 1]
    S2[Server 2]
    S3[Server 3]
    
    C --> LB
    LB -->|1st Request| S1
    LB -->|2nd Request| S2
    LB -->|3rd Request| S3

The round-robin load balancer diagram shows:

1. Components:

• Client : Source of requests
• Load Balancer : Central circular node handling distribution
• Servers 1-3 : Backend servers handling requests

2. Request Flow:

• All requests first hit the load balancer
• Requests are distributed sequentially:
  • 1st request → Server 1
  • 2nd request → Server 2
  • 3rd request → Server 3
  • 4th request would go back to Server 1

This pattern ensures even distribution of traffic across all servers.

2. Least Connections

This algorithm directs requests to the server with the fewest active connections.

Diagram:

graph LR
    C[Client]
    LB((Load Balancer))
    
    subgraph "Server Pool"
        S1["Server 1
        2 connections"]
        S2["Server 2
        1 connection"]
        S3["Server 3
        5 connections"]
    end
    
    C --> LB
    LB -->|New Request| S2
    LB -.-> S1
    LB -.-> S3

The least connections load balancer diagram shows:

Components:

• Client : Request source
• Load Balancer : Traffic distributor
• Servers : Backend servers with connection counts
  • Server 1: 2 connections
  • Server 2: 1 connection
  • Server 3: 5 connections

Traffic Flow:

• Solid line: New request routed to Server 2 (lowest connections)
• Dotted lines: Alternative paths not chosen
• Selection based on minimum active connections (1 < 2 < 5)

This demonstrates how the load balancer prioritizes less busy servers for better resource utilization.

3. Weighted Round Robin

Similar to Round Robin, but each server is assigned a weight reflecting its capacity. Servers with higher weights receive proportionally more requests.

Diagram:

flowchart LR
    C[Client]
    LB((Load Balancer))
    
    subgraph "Server Pool"
        S1["Server 1
        Weight: 2"]
        S2["Server 2
        Weight: 1"]
        S3["Server 3
        Weight: 3"]
    end
    
    C --> LB
    LB -->|2 of 6 requests| S1
    LB -->|1 of 6 requests| S2
    LB -->|3 of 6 requests| S3

The weighted round robin diagram illustrates:

Components:

• Client sending requests
• Load balancer distributing traffic
• Three servers with different weights:
  • Server 1: Weight 2 (handles 33% of traffic)
  • Server 2: Weight 1 (handles 17% of traffic)
  • Server 3: Weight 3 (handles 50% of traffic)

Traffic Distribution:

• Server 3 receives most traffic (3/6)
• Server 1 receives moderate traffic (2/6)
• Server 2 receives least traffic (1/6)
• Weights determine proportion of requests each server handles

4. IP Hash

This algorithm uses the client’s IP address to hash it to a specific server. This ensures that requests from the same client always go to the same server, which can be beneficial for applications requiring session persistence.

Diagram:

graph LR
A[Client IP: 192.168.1.10] --> B(Load Balancer);
B -- IP Hash --> C{Server 1};
A[Client IP: 192.168.1.11] --> B;
B -- IP Hash --> D{Server 2};
style B fill:#f9f,stroke:#333,stroke-width:2px

5. Source IP Hash

Similar to IP Hash, but uses a hash function to map client IP addresses to servers. More than simple modulo-based hashing.

flowchart LR
    subgraph "Clients"
        C1["Client IP: 192.168.1.1
        Hash: 2"]
        C2["Client IP: 10.0.0.1
        Hash: 1"]
        C3["Client IP: 172.16.0.1
        Hash: 3"]
    end

    LB{{"Hash Function
    server = hash(IP) % n"}}

    subgraph "Server Pool"
        S1["Server 1"]
        S2["Server 2"]
        S3["Server 3"]
    end

    C1 --> LB
    C2 --> LB
    C3 --> LB
    
    LB -->|Hash=2| S2
    LB -->|Hash=1| S1
    LB -->|Hash=3| S3

The Source IP Hash diagram shows:

Components:

• Three clients with different IP addresses
• Hash function in load balancer using formula: server = hash(IP) % n
• Three backend servers

Traffic Flow:

• Client 192.168.1.1 → Hash 2 → Server 2
• Client 10.0.0.1 → Hash 1 → Server 1
• Client 172.16.0.1 → Hash 3 → Server 3

Key Benefits:

• Consistent mapping (same client always goes to same server)
• Session persistence
• Distributed load across servers

6. Consistent Hashing

A more advanced technique that minimizes the impact of adding or removing servers. It uses a hash function to map both servers and clients to a ring, distributing clients across servers more evenly.

graph TD
    subgraph "Hash Ring (0-360°)"
        Ring((("Hash Ring
        ↻")))
    end
    
    S1[Server 1]
    S2[Server 2]
    S3[Server 3]
    
    C1[Client A]
    C2[Client B]
    C3[Client C]
    
    Ring -->|90°| S1
    Ring -->|210°| S2
    Ring -->|330°| S3
    
    Ring -->|45°| C1
    Ring -->|180°| C2
    Ring -->|300°| C3
    
    C1 -.->|"Clockwise to
    nearest server"| S1
    C2 -.->|"Clockwise to
    nearest server"| S2
    C3 -.->|"Clockwise to
    nearest server"| S3

The consistent hashing diagram illustrates:

Components:

• Hash ring representing 0-360° space
• Servers at 90°, 210°, 330°
• Clients at 45°, 180°, 300°

Request Flow:

• Client A (45°) → Server 1 (90°)
• Client B (180°) → Server 2 (210°)
• Client C (300°) → Server 3 (330°)

Key Benefit:

• If a server fails, only its immediate clockwise clients redistribute
• Adding/removing servers affects minimal clients
• Natural load balancing through ring distribution

Choosing the Right Algorithm

The choice of load balancing algorithm depends on the specific needs of the application.