Load balancing algorithms (round robin, least connections) in HLD - Scalability & System Analysis

Scalability Analysis - Load balancing algorithms (round robin, least connections)

Growth Table: Load Balancing Algorithms

Users / Traffic	Round Robin	Least Connections
100 users	Simple rotation, evenly distributes requests easily.	Tracks connections, slightly more CPU but balances well.
10,000 users	Still works well, but may cause uneven load if requests vary in length.	Better at balancing uneven loads by checking active connections.
1,000,000 users	Needs multiple load balancers; risk of uneven load if sessions are sticky.	More CPU overhead; requires efficient connection tracking and state sharing.
100,000,000 users	Single load balancer insufficient; must use distributed load balancers or DNS-based balancing.	High complexity; needs distributed state or stateless design to scale.

First Bottleneck

The load balancer itself becomes the first bottleneck as traffic grows.

Round Robin is simple but can cause uneven load if requests vary in duration.

Least Connections requires tracking active connections, increasing CPU and memory usage on the load balancer.

At high scale, the load balancer's CPU and memory limits, plus network bandwidth, break first.

Scaling Solutions

• Horizontal scaling: Add more load balancer instances behind a DNS or anycast layer.
• Load balancer clustering: Share connection state for least connections algorithm.
• Caching: Use session persistence or caching to reduce load balancer decisions.
• Algorithm choice: Use round robin for simple, uniform traffic; least connections for uneven loads.
• Offload: Use hardware load balancers or cloud-managed services to handle high throughput.
• Stateless design: Design backend to be stateless to simplify load balancing.

Back-of-Envelope Cost Analysis

Assuming 1 server handles ~3000 concurrent connections:

• At 10,000 users, 4 load balancers can handle traffic with round robin easily.
• At 1 million users, need ~350 load balancers to handle connections if least connections algorithm is used.
• Network bandwidth: 1 Gbps load balancer can handle ~125 MB/s; high traffic requires multiple load balancers or hardware acceleration.
• CPU usage on load balancer increases with least connections due to connection tracking.

Interview Tip

Start by explaining the two algorithms simply: round robin cycles through servers evenly; least connections sends requests to the server with the fewest active connections.

Discuss pros and cons: round robin is simple but may cause uneven load; least connections balances better but uses more resources.

Identify bottlenecks: load balancer CPU, memory, and network.

Suggest scaling solutions: horizontal scaling, clustering, algorithm choice based on traffic pattern.

Use real numbers to show understanding of limits and trade-offs.

Self Check

Your database handles 1000 QPS. Traffic grows 10x. What do you do first?

Answer: Since the load balancer is the first bottleneck for increased traffic, add more load balancer instances and use horizontal scaling to distribute the load. Also, consider switching to least connections if traffic is uneven.

Key Result

Load balancers become bottlenecks as traffic grows; horizontal scaling and algorithm choice (round robin vs least connections) are key to handle increasing load efficiently.

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