Load Balancing Algorithms

A load balancing algorithm is a method used by a load balancer to distribute incoming traffic and requests among multiple servers or resources. The primary purpose of a load balancing algorithm is to ensure efficient utilization of available resources, improve overall system performance, and maintain high availability and reliability.

Load balancing algorithms help to prevent any single server or resource from becoming overwhelmed, which could lead to performance degradation or failure. By distributing the workload, load balancing algorithms can optimize response times, maximize throughput, and enhance user experience. These algorithms can consider factors such as server capacity, active connections, response times, and server health, among others, to make informed decisions on how to best distribute incoming requests.

Here are the most famous load balancing algorithms:

1. Round Robin

This algorithm distributes incoming requests to servers in a cyclic order. It assigns a request to the first server, then moves to the second, third, and so on, and after reaching the last server, it starts again at the first.

Pros:

• Ensures an equal distribution of requests among the servers, as each server gets a turn in a fixed order.
• Easy to implement and understand.
• Works well when servers have similar capacities.

Cons:

• No Load Awareness: Does not take into account the current load or capacity of each server. All servers are treated equally regardless of their current state.
• No Session Affinity: Subsequent requests from the same client may be directed to different servers, which can be problematic for stateful applications.
• Performance Issues with Different Capacities: May not perform optimally when servers have different capacities or varying workloads.
• Predictable Distribution Pattern: Round Robin is predictable in its request distribution pattern, which could potentially be exploited by attackers who can observe traffic patterns and might find vulnerabilities in specific servers by predicting which server will handle their requests.

Use Cases

• Homogeneous Environments: Suitable for environments where all servers have similar capacity and performance.
• Stateless Applications: Works well for stateless applications where each request can be handled independently.

2. Least Connections

The Least Connections algorithm is a dynamic load balancing technique that assigns incoming requests to the server with the fewest active connections at the time of the request. This method ensures a more balanced distribution of load across servers, especially in environments where traffic patterns are unpredictable and request processing times vary.

Pros:

• Load Awareness: Takes into account the current load on each server by considering the number of active connections, leading to better utilization of server resources.
• Dynamic Distribution: Adapts to changing traffic patterns and server loads, ensuring no single server becomes a bottleneck.
• Adapts to Uneven Requests: Performs well when requests vary widely in how long they take, because slow requests hold connections open and new requests are steered to less busy servers.

Cons:

• Higher Complexity: More complex to implement compared to simpler algorithms like Round Robin, as it requires real-time monitoring of active connections.
• State Maintenance: Requires the load balancer to maintain the state of active connections, which can increase overhead.
• Potential for Connection Spikes: In scenarios where connection duration is short, servers can experience rapid spikes in connection counts, leading to frequent rebalancing.

Use Cases

• Uneven Request Durations: Suitable when requests vary widely in processing time, so counting active connections tracks real load. Note that plain Least Connections treats every server as equally capable; when server capacities differ, Weighted Least Connections is the right variant.
• Variable Traffic Patterns: Works well for applications with unpredictable or highly variable traffic patterns, ensuring that no single server is overwhelmed.
• Stateful Applications: Effective for applications where maintaining session state is important, as it helps distribute active sessions more evenly.

Comparison to Round Robin

• Round Robin: Distributes requests in a fixed, cyclic order without considering the current load on each server.
• Least Connections: Distributes requests based on the current load, directing new requests to the server with the fewest active connections.

3. Weighted Round Robin

Weighted Round Robin (WRR) is an enhanced version of the Round Robin load balancing algorithm. It assigns weights to each server based on their capacity or performance, distributing incoming requests proportionally according to these weights. This ensures that more powerful servers handle a larger share of the load, while less powerful servers handle a smaller share.

Pros

• Load Distribution According to Capacity: Servers with higher capacities handle more requests, leading to better utilization of resources.
• Flexibility: Easily adjustable to accommodate changes in server capacities or additions of new servers.
• Improved Performance: Helps in optimizing overall system performance by preventing overloading of less powerful servers.

Cons

• Complexity in Weight Assignment: Determining appropriate weights for each server can be challenging and requires accurate performance metrics.
• Increased Overhead: Managing and updating weights can introduce additional overhead, especially in dynamic environments where server performance fluctuates.
• Not Ideal for Highly Variable Loads: In environments with highly variable load patterns, WRR may not always provide optimal load balancing as it doesn't consider real-time server load.

Use Cases

• Heterogeneous Server Environments: Ideal for environments where servers have different processing capabilities, ensuring efficient use of resources.
• Scalable Web Applications: Suitable for web applications where different servers may have varying performance characteristics.
• Database Clusters: Useful in database clusters where some nodes have higher processing power and can handle more queries.

4. Weighted Least Connections

Weighted Least Connections is an advanced load balancing algorithm that combines the principles of the Least Connections and Weighted Round Robin algorithms. It takes into account both the current load (number of active connections) on each server and the relative capacity of each server (weight). This approach ensures that more powerful servers handle a proportionally larger share of the load, while also dynamically adjusting to the real-time load on each server.

Pros

• Dynamic Load Balancing: Adjusts to the real-time load on each server, ensuring a more balanced distribution of requests.
• Capacity Awareness: Takes into account the relative capacity of each server, leading to better utilization of resources.
• Flexibility: Can handle environments with heterogeneous servers and variable load patterns effectively.

Cons

• Complexity: More complex to implement compared to simpler algorithms like Round Robin and Least Connections.
• State Maintenance: Requires the load balancer to keep track of both active connections and server weights, increasing overhead.
• Weight Assignment: Determining appropriate weights for each server can be challenging and requires accurate performance metrics.

Use Cases

• Heterogeneous Server Environments: Ideal for environments where servers have different processing capacities and workloads.
• High Traffic Web Applications: Suitable for web applications with variable traffic patterns, ensuring no single server becomes a bottleneck.
• Database Clusters: Useful in database clusters where nodes have varying performance capabilities and query loads.

8. Least Bandwidth

The Least Bandwidth load balancing algorithm distributes incoming requests to servers based on the current bandwidth usage. It routes each new request to the server that is consuming the least amount of bandwidth at the time. This approach helps in balancing the network load more efficiently by ensuring that no single server gets overwhelmed with too much data traffic.

Pros

• Dynamic Load Balancing: Continuously adjusts to the current network load, ensuring optimal distribution of traffic.
• Prevents Overloading: Helps in preventing any single server from being overwhelmed with too much data traffic, leading to better performance and stability.
• Efficient Resource Utilization: Ensures that all servers are utilized more effectively by balancing the bandwidth usage.

Cons

• Complexity: More complex to implement compared to simpler algorithms like Round Robin, as it requires continuous monitoring of bandwidth usage.
• Overhead: Monitoring bandwidth and dynamically adjusting the load can introduce additional overhead.
• Short-Term Variability: Bandwidth usage can fluctuate in the short term, potentially causing frequent rebalancing.

Use Cases

• High Bandwidth Applications: Ideal for applications with high bandwidth usage, such as video streaming, file downloads, and large data transfers.
• Content Delivery Networks (CDNs): Useful for CDNs that need to balance traffic efficiently to deliver content quickly.
• Bandwidth-Bound Workloads: Best when the network link, not the CPU, is the resource that runs out first. For latency-sensitive traffic with small responses, Least Response Time is the better fit, because bandwidth usage says little about how quickly a small request completes.

9. Custom Load

Custom Load load balancing is a flexible and highly configurable approach that allows you to define your own metrics and rules for distributing incoming traffic across a pool of servers. Unlike standard load balancing algorithms that use predefined criteria such as connection count or response time, Custom Load load balancing enables you to tailor the distribution strategy based on specific requirements and conditions unique to your application or infrastructure.

How Custom Load Load Balancing Works

1. Define Custom Metrics: Determine the metrics that best represent the load or performance characteristics relevant to your application. These metrics can include CPU usage, memory usage, disk I/O, application-specific metrics, or a combination of several metrics.

2. Implement Monitoring: Continuously monitor the defined metrics on each server in the pool. This may involve integrating with monitoring tools or custom scripts that collect and report the necessary data.

3. Create Load Balancing Rules: Establish rules and algorithms that use the monitored metrics to make load balancing decisions. This can be a simple weighted sum of metrics or more complex logic that prioritizes certain metrics over others.

4. Dynamic Adjustment: Use the collected data and rules to dynamically adjust the distribution of incoming requests, ensuring that the traffic is balanced according to the custom load criteria.

Pros

• Flexibility: Allows for highly customized load balancing strategies tailored to the specific needs and performance characteristics of your application.
• Optimized Resource Utilization: Can lead to more efficient use of server resources by considering a comprehensive set of metrics.
• Adaptability: Easily adaptable to changing conditions and requirements, making it suitable for complex and dynamic environments.

Cons

• Complexity: More complex to implement and configure compared to standard load balancing algorithms.
• Monitoring Overhead: Requires continuous monitoring of multiple metrics, which can introduce additional overhead.
• Potential for Misconfiguration: Incorrectly defined metrics or rules can lead to suboptimal load balancing and performance issues.

Use Cases

• Complex Applications: Ideal for applications with complex performance characteristics and varying resource requirements.
• Highly Dynamic Environments: Suitable for environments where workloads and server performance can change rapidly and unpredictably.
• Custom Requirements: Useful when standard load balancing algorithms do not meet the specific needs of the application.

How to Choose

For most systems, the honest answer is that round robin or least connections is enough.

• Servers are the same size and requests are short: round robin.
• Servers are different sizes: weighted round robin.
• Requests take very different amounts of time, or connections stay open: least connections.
• Different sizes and uneven requests: weighted least connections.
• Responses are large files or video: least bandwidth.
• The same user must reach the same server: IP hash. It is usually better to move the session into a shared cache instead, and remove the need for stickiness.

In an interview, name the algorithm, then say what it does not know. That second part is what shows you understand it.

Key Takeaways

• The algorithm only picks between healthy servers. Health checks are a separate mechanism, so "ignores server health" is not a weakness of any algorithm.
• Round robin is simple and counts requests, not work. Weighted round robin adds server size, which you must configure by hand.
• Least connections reacts to real load with no configuration, but it is blind to server capacity. Weighted least connections fixes that.
• Least response time can be fooled by a server that fails quickly, because an error is fast.
• Least bandwidth measures the size of responses, not speed. It is for large downloads and video.
• IP hash gives stickiness. It does not route by location, it spreads load unevenly, and adding a server moves almost every client. Consistent hashing solves the last problem.
• Random of two choices is nearly as good as least connections and much cheaper to run.

The algorithm matters less than most people expect. Uneven load usually comes from somewhere else. Sessions kept in server memory, one very popular item, or requests that cost very different amounts. Fix those first.