Least Connections Algorithm

1. One-Liner

The Least Connections algorithm routes each new request to the backend server that currently has the fewest active connections.

2. The Problem It Solves

You have multiple backend servers behind a load balancer. If you use Round Robin (send requests in order: Server 1, 2, 3, 1, 2, 3...), it seems fair. But what if:

Server 1 is processing a heavy database query (takes 10 seconds).

Server 2 finished its request in 50ms and is now idle.

Round Robin still sends the next request to Server 1, which is already overloaded!

The problem: Not all requests take the same time. Some are fast, some are slow. Round Robin ignores this completely.

Least Connections fixes this by always picking the server that is least busy right now.

3. The Core Idea

Imagine you’re at a supermarket with 4 checkout counters. Each counter has a line of customers:

Counter 1: 5 people waiting

Counter 2: 2 people waiting

Counter 3: 7 people waiting

Counter 4: 1 person waiting

Which counter do you go to? Obviously Counter 4 — the one with the shortest line.

That’s exactly what Least Connections does. The "line" is the number of active connections (requests being processed). The load balancer always sends you to the server with the shortest line.

4. How It Works (Step-by-Step)

Step	What Happens
1. Request arrives	A new request comes to the load balancer
2. Lock	Acquire a lock (thread safety in concurrent systems)
3. Find minimum	Scan all servers, find the one with the fewest active connections
4. Break ties	If multiple servers are tied, pick the first one (or random)
5. Increment	Add 1 to that server’s active connection count
6. Route	Forward the request to the chosen server
7. On completion	When the request finishes, decrement that server’s count by 1

Key insight: The count goes UP when a request is routed, and DOWN when processing finishes. This means slow servers naturally accumulate more connections and get fewer new requests.

5. Dry Run Example

Setup: 3 servers, all start at 0 connections

Request #	S1 Conns	S2 Conns	S3 Conns	Routed To	Why
1	0	0	0	S1	All tied, pick first
2	1	0	0	S2	S2 has min (0)
3	1	1	0	S3	S3 has min (0)
4	1	1	1	S1	All tied, pick first
—	—	—	—	—	S2 finishes request #2
5	2	0	1	S2	S2 has min (0)
—	—	—	—	—	S1 finishes request #1
6	1	1	1	S1	All tied again

Notice how when S2 finishes early, it immediately gets the next request. Slow servers naturally get less traffic.

6. Key Properties

Property	Value
Adapts to server speed?	Yes — slow servers get fewer requests
Handles unequal hardware?	Yes — faster machines finish quicker, get more work
Needs connection tracking?	Yes — must track active count per server
Thread-safe?	Needs locking (mutex) for concurrent access
Weighted variant?	Yes — Weighted Least Connections adds server capacity factors

7. Where It Is Used

Company / System	How They Use It
Nginx	`least_conn` directive in upstream blocks
HAProxy	`balance leastconn` in backend config
AWS ALB	Least Outstanding Requests (similar concept)
Envoy Proxy	Built-in least request load balancing
F5 BIG-IP	Least Connections as default LB method
Kubernetes	Available in service mesh (Istio, Linkerd)

8. Interview Tips

What interviewers want to hear:

1. You understand the weakness of Round Robin (ignores processing time differences)

2. You can explain with the supermarket checkout analogy

3. You know it needs connection tracking (counter per server)

4. You can discuss thread safety — what if two requests arrive at the exact same time?

5. You know about Weighted Least Connections for heterogeneous servers

Common follow-up questions:

"When would Round Robin be better?" → When all requests take roughly the same time and servers are identical. Simpler, no counter tracking needed.

"What’s Weighted Least Connections?" → Each server has a weight (e.g., based on CPU cores). The formula becomes connections / weight. A powerful server with weight 4 and 8 connections is preferred over a weak server with weight 1 and 3 connections.

"How do you handle server failure?" → Health checks. Remove failed servers from the pool. Their connections will eventually time out and decrement.

"What about session stickiness?" → Use Least Connections for initial routing, then use cookies/hashing for subsequent requests from the same user.

9. Comparison with Other Algorithms

Algorithm	Adapts to Load?	Complexity	Needs Tracking?	Best For
Least Connections	✅ Yes	O(n)	Yes — active count	Varying request durations
Round Robin	❌ No	O(1)	No	Uniform requests, identical servers
Weighted Round Robin	⚠️ Partial	O(1)	No	Different server capacities
IP Hash	❌ No	O(1)	No	Session affinity
Random	❌ No	O(1)	No	Simple, stateless
Least Response Time	✅ Yes	O(n)	Yes — latency	Latency-sensitive workloads

10. Complexity

Metric	Value
Time Complexity	O(n) per request — where n = number of servers
Space Complexity	O(n) — one counter per server
Connection Update	O(1) — increment/decrement

Implementation Example (PYTHON)

import threading

class LeastConnectionLB:
    def __init__(self, servers):
        self.servers = servers
        self.connections = {s: 0 for s in servers}
        self.lock = threading.Lock()

    def get_server(self):
        with self.lock:
            min_conn = min(
                self.connections.values())
            candidates = [
                s for s, c in self.connections.items()
                if c == min_conn]
            server = candidates[0]
            self.connections[server] += 1
            return server

    def release(self, server):
        with self.lock:
            self.connections[server] -= 1
            self.connections[server] = max(
                0, self.connections[server])