Load balancing ensures that the incoming network traffic is efficiently distributed across multiple servers. This not only enhances the performance and reliability of applications but also provides scalability and fault tolerance. Load balancers use various algorithms to determine how traffic should be distributed. In this article, we will explore some of the most commonly used load balancer algorithms, including Round-Robin, Least-Connections, Weighted Round-Robin, Weighted Least-Connections, and Random. We will also implement the simulation of these algorithms.
In order to achieve the simulation of same code being deployed on different servers, I creating a server in python and then orchestrated to run it on 5 different random ports and saved the ports list for further processing by load balancing algorithm. This is usually done by Service Discovery and Service Registry in real life applications.
Create a Server
from http.server import SimpleHTTPRequestHandler
from socketserver import TCPServer
HOST = "localhost"
def run_server(port):
class MyServer(SimpleHTTPRequestHandler):
def do_GET(self):
if self.path == "/":
self.send_response(200, "OK")
self.send_header("Content-type", "text/html")
self.end_headers()
self.wfile.write(f"Welcome to the server. I'm hosted on {HOST}:{port}".encode())
else:
super().do_GET()
with TCPServer((HOST, port), MyServer) as httpd:
print(f"Serving on http://{HOST}:{port}")
try:
httpd.serve_forever()
except KeyboardInterrupt:
print(f"\nServer on {HOST}:{port} is shutting down.")
httpd.server_close()
Orchestrate server runs
from components.server import run_server
from multiprocessing import Process
import random
HOST = "localhost"
all_ports = []
processes = []
def start_multiple_servers():
for i in range(5): # Start 5 servers
PORT = random.randint(8000, 9000) # Pick a random port
while PORT in all_ports: # Ensure no duplicate ports
PORT = random.randint(8000, 9000)
all_ports.append(PORT)
# Start a new process for each server
process = Process(target=run_server, args=(PORT,))
process.start()
processes.append(process)
# Print message
print(f"Server started on http://{HOST}:{PORT}")
return [[port, process] for port, process in zip(all_ports, processes)]
# Shutdown all servers
def shutdown_servers(processes):
for process in processes:
print(f"Shutting down server on {process.pid}")
process.terminate()
process.join()
1. Round-Robin
Overview
Round-Robin is one of the simplest and most widely used load balancing algorithms. It distributes incoming requests sequentially across a list of servers. Once the end of the list is reached, the load balancer starts again from the beginning.
How It Works
The load balancer maintains a list of servers.
When a new request comes in, it is forwarded to the first server in the list.
The next request is forwarded to the second server, and so on.
After the last server is reached, the load balancer cycles back to the first server.
Advantages
Simplicity: Easy to implement and understand.
Fair Distribution: Ensures that each server gets an equal number of requests over time.
Disadvantages
No Consideration for Server Load: Does not account for the current load or capacity of the servers.
Uneven Distribution: If servers have different processing capabilities, some may become overloaded while others remain underutilised.
Implementation:
from utility import display_allocation
def round_robin(port_process_list, requests):
allocations = []
for request in requests:
# Get the next port from the cycle iterator
# We can also use cycle() feature in python to implement this
port, process = port_process_list.pop(0)
# assign the request to the port
allocations.append((request, port))
# Add the port back to the end of the list
port_process_list.append((port, process))
# Display the allocations
display_allocation(allocations)
Output
2. Least-Connections
Overview
The Least-Connections algorithm directs incoming requests to the server with the fewest active connections. This approach is more dynamic than Round-Robin, as it considers the current load on each server.
How It Works
The load balancer monitors the number of active connections to each server.
When a new request comes in, it is forwarded to the server with the least number of active connections.
Advantages
Dynamic Load Balancing: Adapts to the current load on each server.
Efficient Resource Utilisation: Helps prevent overloading of any single server.
Disadvantages
Overhead: Requires continuous monitoring of server connections, which can add overhead.
Complexity: More complex to implement compared to Round-Robin.
Implementation
import heapq
from utility import display_allocation, display_heap
def least_connections(port_process_list, requests):
# Create a heap with the least connection count at the top
least_connection_heap = [(0, port) for port,_ in port_process_list]
# Convert the list to a heapq. This is used to keep the queue in increasing order
heapq.heapify(least_connection_heap)
allocations = []
for request in requests:
# Get the port with the least connection count
conn_count, port = heapq.heappop(least_connection_heap)
# Add the request to the port
allocations.append((request,port))
# Increment the connection count for the port and add it back to the heap
heapq.heappush(least_connection_heap, (conn_count+1, port))
# Display the heap and the allocation
display_heap(least_connection_heap)
display_allocation(allocations)
Output
3. Weighted Round-Robin
Overview
Weighted Round-Robin is an extension of the Round-Robin algorithm that assigns a weight to each server based on its capacity. Servers with higher weights receive more requests than those with lower weights.
How It Works
Each server is assigned a weight, typically based on its processing power or capacity.
The load balancer distributes requests in a Round-Robin fashion but gives more requests to servers with higher weights.
Advantages
Customisable: Allows for fine-tuning based on server capabilities.
Improved Performance: Ensures that more powerful servers handle more requests.
Disadvantages
Static Weights: Weights are usually static and may not reflect real-time server conditions.
Complexity: More complex to configure and manage than standard Round-Robin.
Implementation
from itertools import cycle
import random
from utility import display_allocation
weighted_ports = []
# Allocate weights to ports
def allocate_weights(port_process_list):
for port, _ in port_process_list:
# Randomly assign a weight between 1 and 3, we are doing this to simulate the weights of the servers
weight = random.randint(1, 3)
weighted_ports.extend([port]*weight)
def weighted_round_robin(port_process_list, requests):
allocate_weights(port_process_list)
print('weighted_ports:', weighted_ports)
# Create a cycle iterator
weighted_ports_cycle = cycle(weighted_ports)
allocations = []
for request in requests:
# Get the next port from the cycle iterator
port = next(weighted_ports_cycle)
# Append the request and the port to the allocations list
allocations.append((request, port))
display_allocation(allocations)
Output
4. Weighted Least-Connections
Overview
Weighted Least-Connections combines the principles of Least-Connections and Weighted Round-Robin. It directs incoming requests to the server with the fewest active connections relative to its weight.
How It Works
Each server is assigned a weight based on its capacity.
The load balancer calculates the effective number of connections for each server by dividing the number of active connections by its weight.
The request is forwarded to the server with the lowest effective number of connections.
Advantages
Dynamic and Customisable: Considers both server capacity and current load.
Efficient Resource Utilisation: Ensures optimal use of server resources.
Disadvantages
Complexity: More complex to implement and manage.
Overhead: Requires continuous monitoring and calculation of effective connections.
Implementation
from itertools import cycle
import random
from utility import display_allocation
weighted_ports = []
# Allocate weights to ports
def allocate_weights(port_process_list):
for port, _ in port_process_list:
# Randomly assign a weight between 1 and 3, we are doing this to simulate the weights of the servers
weight = random.randint(1, 3)
weighted_ports.extend([port]*weight)
def weighted_round_robin(port_process_list, requests):
allocate_weights(port_process_list)
print('weighted_ports:', weighted_ports)
# Create a cycle iterator
weighted_ports_cycle = cycle(weighted_ports)
allocations = []
for request in requests:
# Get the next port from the cycle iterator
port = next(weighted_ports_cycle)
# Append the request and the port to the allocations list
allocations.append((request, port))
display_allocation(allocations)
Output
5. Random
Overview
The Random algorithm distributes incoming requests to servers randomly. This method is simple and can be effective in certain scenarios.
How It Works
- When a new request comes in, the load balancer randomly selects a server from the list and forwards the request to it.
Advantages
Simplicity: Easy to implement.
No Overhead: Does not require monitoring or complex calculations.
Disadvantages
Unpredictable Distribution: Can lead to uneven distribution of requests.
No Consideration for Server Load: Does not account for the current load or capacity of the servers.
Implementation
from itertools import cycle
import random
from utility import display_allocation
weighted_ports = []
# Allocate weights to ports
def allocate_weights(port_process_list):
for port, _ in port_process_list:
# Randomly assign a weight between 1 and 3, we are doing this to simulate the weights of the servers
weight = random.randint(1, 3)
weighted_ports.extend([port]*weight)
def weighted_round_robin(port_process_list, requests):
allocate_weights(port_process_list)
print('weighted_ports:', weighted_ports)
# Create a cycle iterator
weighted_ports_cycle = cycle(weighted_ports)
allocations = []
for request in requests:
# Get the next port from the cycle iterator
port = next(weighted_ports_cycle)
# Append the request and the port to the allocations list
allocations.append((request, port))
display_allocation(allocations)
Output
Putting it all together
In my main.py file, we started the server using orchestrator and then expected different algorithm to allocated the request. Results for the same are attached to each explanation above
from orchestrator import start_multiple_servers, shutdown_servers
from algos.roundrobin import round_robin
from algos.leastconnections import least_connections
from algos.weightedroundrobin import weighted_round_robin
from algos.weightedleastconnections import weighted_least_connections
from algos.random import random_load_balancer
requests = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
if __name__ == "__main__":
port_processes = start_multiple_servers()
print(port_processes)
processes = [process for _, process in port_processes]
round_robin(port_processes, requests)
least_connections(port_processes, requests)
weighted_round_robin(port_processes, requests)
weighted_least_connections(port_processes, requests)
random_load_balancer(port_processes, requests)
try:
while True:
user_input = input("Press 'Q' to shut down servers: ")
if user_input.lower() == 'q':
shutdown_servers(processes)
print("Servers have been shut down.")
break
except KeyboardInterrupt:
shutdown_servers(processes)
print("Servers have been shut down.")
Other Load Balancer Algorithms
6. IP Hash
Overview: The IP Hash algorithm uses the client's IP address to determine which server should handle the request. This ensures that requests from the same client are always directed to the same server.
Advantages: Useful for maintaining session persistence.
Disadvantages: Can lead to uneven distribution if many clients share the same IP address (e.g., behind a NAT).
7. Least Response Time
Overview: This algorithm directs requests to the server with the lowest response time, considering both the current load and the server's performance.
Advantages: Ensures that requests are handled by the fastest available server.
Disadvantages: Requires continuous monitoring of response times, adding overhead.
8. Resource-Based (Adaptive)
Overview: The Resource-Based algorithm distributes requests based on the actual resource usage (CPU, memory, etc.) of each server.
Advantages: Highly efficient and adaptive to real-time server conditions.
Disadvantages: Complex to implement and requires detailed monitoring of server resources.
9. Geographic
Overview: The Geographic algorithm directs requests to the server that is geographically closest to the client, reducing latency.
Advantages: Improves response times for geographically distributed users.
Disadvantages: Requires a geographically distributed server infrastructure.
10. Consistent Hashing
Overview: Consistent Hashing is used in distributed systems to minimize the number of keys that need to be remapped when a server is added or removed.
Advantages: Reduces the impact of server changes on the overall system.
Disadvantages: More complex to implement and manage.
Conclusion
Load balancer algorithms play a crucial role in ensuring the efficient distribution of network traffic across multiple servers. Each algorithm has its own strengths and weaknesses, making them suitable for different scenarios. Round-Robin and Random are simple and easy to implement, while Least-Connections and Weighted Least-Connections offer more dynamic and efficient load balancing. Weighted Round-Robin and Weighted Least-Connections provide additional customisation based on server capacity. Other algorithms like IP Hash, Least Response Time, Resource-Based, Geographic, and Consistent Hashing offer specialised solutions for specific needs.
Choosing the right load balancer algorithm depends on the specific requirements of your application, including factors like server capacity, traffic patterns, and desired performance characteristics. By understanding the different algorithms available, you can make an informed decision that optimizes the performance, reliability, and scalability of your system.