Load balancing algorithms (round robin, least connections) in HLD - System Design Exercise

Design: Load Balancer with Round Robin and Least Connections Algorithms

Design focuses on the load balancer component and its algorithms. Backend server internals and client implementations are out of scope.

Functional Requirements

FR1: Distribute incoming client requests evenly across multiple backend servers

FR2: Support at least two load balancing algorithms: round robin and least connections

FR3: Handle up to 10,000 concurrent client connections

FR4: Provide low latency routing with p99 response time under 100ms

FR5: Ensure high availability with 99.9% uptime

FR6: Allow dynamic switching between load balancing algorithms without downtime

Non-Functional Requirements

NFR1: System must handle sudden spikes in traffic gracefully

NFR2: Load balancer should not become a single point of failure

NFR3: Minimal overhead in decision making to keep latency low

NFR4: Backend servers may have different capacities (heterogeneous environment)

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Load balancer front-end to receive client requests

Health check module to monitor backend server status

Algorithm module implementing round robin and least connections

Backend server pool management

Metrics and logging for monitoring load distribution

Design Patterns

Round Robin load balancing pattern

Least Connections load balancing pattern

Health checking and failover pattern

Sticky session (if required)

Active-passive or active-active load balancer deployment

Reference Architecture

Client Requests
    |
    v
+-----------------+
|   Load Balancer  |
|  +------------+ |
|  | Algorithm  | |
|  | Module     | |
|  +------------+ |
|  | Health    |  |
|  | Check     |  |
+-----------------+
    |       |       
    v       v       
+-------+ +-------+
|Server1| |Server2|
+-------+ +-------+
    .         .    
    .         .    
+-------+ +-------+
|ServerN| |       |
+-------+ +-------+

Components

Load Balancer Front-end

Nginx or HAProxy or custom TCP/HTTP proxy

Receives client requests and forwards them to backend servers based on selected algorithm

Algorithm Module

Custom logic in load balancer software

Implements round robin and least connections algorithms to select backend server

Health Check Module

Periodic HTTP/TCP probes

Monitors backend server health and removes unhealthy servers from rotation

Backend Server Pool

Set of application servers

Handles actual client requests forwarded by load balancer

Metrics and Logging

Prometheus, Grafana, or built-in logging

Tracks load distribution, server health, and performance

Request Flow

1. Client sends a request to the load balancer.

2. Load balancer receives the request at its front-end.

3. Health check module confirms which backend servers are healthy.

4. Algorithm module selects a backend server based on the chosen algorithm:

5. - Round Robin: picks the next server in a circular order.

6. - Least Connections: picks the server with the fewest active connections.

7. Load balancer forwards the client request to the selected backend server.

8. Backend server processes the request and sends response back through load balancer.

9. Load balancer forwards the response to the client.

Database Schema

Not applicable as this design focuses on runtime load balancing logic without persistent storage.

Scaling Discussion

Bottlenecks

Load balancer becoming a single point of failure under high traffic

Algorithm module latency increasing with large number of backend servers

Health check overhead causing delays or false positives

Uneven load distribution if backend servers have different capacities

Solutions

Deploy multiple load balancer instances with DNS round robin or anycast IP for high availability

Use efficient data structures (e.g., indexed lists, min-heaps) to optimize algorithm selection

Tune health check frequency and timeout to balance accuracy and overhead

Implement weighted round robin or weighted least connections to account for server capacity differences

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing the architecture and algorithms, 10 minutes discussing scaling and trade-offs, and 5 minutes summarizing.

Explain the difference between round robin and least connections clearly

Discuss how health checks improve reliability

Mention how to handle server failures gracefully

Talk about scaling the load balancer itself to avoid bottlenecks

Highlight how algorithm choice affects load distribution and latency

Practice

1. Which load balancing algorithm sends requests to servers in a fixed, repeating order without considering current load?

easy

A. Round Robin

B. Least Connections

C. Random Selection

D. IP Hash

Solution

1. Step 1: Understand Round Robin behavior

   Round Robin cycles through servers one by one in order, ignoring current load or connections.

2. Step 2: Compare with other algorithms

   Least Connections considers active connections, Random Selection picks randomly, IP Hash uses client IP. Only Round Robin ignores load.

3. Final Answer:

   Round Robin -> Option A

4. Quick Check:

   Fixed order without load check = Round Robin [OK]

Hint: Round Robin cycles evenly, ignores load [OK]

Common Mistakes:

• Confusing Least Connections with Round Robin
• Thinking Random Selection is fixed order
• Assuming IP Hash ignores load

2. Which of the following is the correct pseudocode snippet for implementing Round Robin load balancing?

easy

A. server = server with minimum active connections

B. server = hash(client_ip) % total_servers

C. server = random.choice(servers)

D. server = servers[(current_index + 1) % total_servers]

Solution

1. Step 1: Identify Round Robin logic

   Round Robin selects the next server by incrementing an index and wrapping around using modulo.

2. Step 2: Match pseudocode to logic

   server = servers[(current_index + 1) % total_servers] uses (current_index + 1) % total_servers, which correctly cycles through servers.

3. Final Answer:

   server = servers[(current_index + 1) % total_servers] -> Option D

4. Quick Check:

   Modulo cycling index = Round Robin [OK]

Hint: Round Robin uses modulo to cycle servers [OK]

Common Mistakes:

• Choosing minimum connections for Round Robin
• Using random selection syntax
• Using hash function for Round Robin

3. Given 3 servers with active connections: Server A=5, Server B=2, Server C=4, which server will Least Connections algorithm select for the next request?

medium

A. Server B

B. Server C

C. Server A

D. Server A or Server C (tie)

Solution

1. Step 1: Identify server with fewest active connections

   Server B has 2 connections, fewer than A (5) and C (4).

2. Step 2: Apply Least Connections selection

   Least Connections chooses the server with the minimum active connections, so Server B is selected.

3. Final Answer:

   Server B -> Option A

4. Quick Check:

   Fewest connections = Server B [OK]

Hint: Least Connections picks server with minimum active connections [OK]

Common Mistakes:

• Picking server with most connections
• Choosing Round Robin instead of Least Connections
• Confusing ties with multiple servers

4. A load balancer using Least Connections algorithm always sends requests to Server A, even though Server B has fewer active connections. What is the most likely cause?

medium

A. Round Robin algorithm is being used instead

B. The connection count for Server B is not updated correctly

C. Server A has a lower IP address

D. The load balancer is using random selection

Solution

1. Step 1: Analyze behavior mismatch

   Least Connections should pick server with fewer active connections, but always picks Server A.

2. Step 2: Identify likely cause

   If Server B's connection count is stale or incorrect, the balancer wrongly thinks Server A has fewer connections.

3. Final Answer:

   The connection count for Server B is not updated correctly -> Option B

4. Quick Check:

   Incorrect connection tracking causes wrong Least Connections choice [OK]

Hint: Check if connection counts update properly for Least Connections [OK]

Common Mistakes:

• Assuming algorithm is Round Robin without checking
• Thinking IP address affects Least Connections
• Ignoring connection count accuracy

5. You have 4 servers with varying capacities and active connections: Server A (capacity 10, connections 5), Server B (capacity 20, connections 15), Server C (capacity 15, connections 10), Server D (capacity 10, connections 2). Which server should a capacity-aware Least Connections algorithm select to balance load best?

hard

A. Server C

B. Server B

C. Server D

D. Server A

Solution

1. Step 1: Calculate load ratio (connections/capacity) for each server

   Server A: 5/10 = 0.5, Server B: 15/20 = 0.75, Server C: 10/15 ≈ 0.67, Server D: 2/10 = 0.2

2. Step 2: Select server with lowest load ratio

   Server D has the lowest ratio (0.2), so it is selected in capacity-aware Least Connections.

3. Final Answer:

   Server D -> Option C

4. Quick Check:

   Lowest load ratio = Server D [OK]

Hint: Consider connections relative to capacity, not just counts [OK]

Common Mistakes:

• Picking server with fewest connections ignoring capacity
• Ignoring capacity differences
• Choosing server with lowest absolute connections only