Least connections in Nginx - Time & Space Complexity

Time Complexity: Least connections

O(n)

Understanding Time Complexity

We want to understand how the time to pick a server grows as the number of servers increases in nginx's least connections load balancing.

How does nginx find the server with the fewest active connections efficiently?

Scenario Under Consideration

Analyze the time complexity of this nginx configuration snippet using least connections:

upstream backend {
    least_conn;
    server backend1.example.com;
    server backend2.example.com;
    server backend3.example.com;
}

server {
    location / {
        proxy_pass http://backend;
    }
}
    

This config tells nginx to send each request to the server with the fewest active connections.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: nginx checks the active connections count of each server in the upstream list.
• How many times: Once per incoming request, it compares all servers to find the one with the least connections.

How Execution Grows With Input

As the number of servers (n) grows, nginx must check each server's connection count to pick the least busy one.

Input Size (n)	Approx. Operations
10	10 comparisons
100	100 comparisons
1000	1000 comparisons

Pattern observation: The number of operations grows directly with the number of servers.

Final Time Complexity

Time Complexity: O(n)

This means the time to pick a server grows linearly as the number of servers increases.

Common Mistake

[X] Wrong: "nginx instantly knows the least connected server without checking all servers."

[OK] Correct: nginx must compare all servers' connection counts each time to find the least busy one, so it takes longer with more servers.

Interview Connect

Understanding how load balancers pick servers helps you explain real-world system behavior and shows you can think about efficiency in infrastructure.

Self-Check

"What if nginx used a priority queue to track servers by active connections? How would the time complexity change?"

Practice

1. What does the least_conn directive do in an nginx upstream block?

easy

A. Sends new requests to the server with the fewest active connections

B. Sends new requests to the server with the fastest response time

C. Sends new requests to servers in a round-robin order

D. Sends new requests to the server with the most active connections

Solution

1. Step 1: Understand the purpose of least_conn

   The least_conn directive is used to balance load by sending requests to the server with the fewest active connections.

2. Step 2: Compare with other load balancing methods

   Other methods like round-robin or fastest response time differ; least_conn focuses on active connections count.

3. Final Answer:

   Sends new requests to the server with the fewest active connections -> Option A

4. Quick Check:

   Least connections = fewest active connections [OK]

Hint: Least connections means pick server with fewest active users [OK]

Common Mistakes:

• Confusing least connections with round-robin
• Thinking it picks fastest server instead
• Assuming it sends to server with most connections

2. Which of the following is the correct syntax to enable least connections load balancing in nginx?

easy

A. upstream backend { least_conn; server 192.168.1.1; }

B. upstream backend { least_connections; server 192.168.1.1; }

C. upstream backend { least_conn_load; server 192.168.1.1; }

D. upstream backend { leastconn; server 192.168.1.1; }

Solution

1. Step 1: Recall the exact directive name

   The correct directive to enable least connections is least_conn inside the upstream block.

2. Step 2: Verify syntax correctness

   Options A, B, and D use incorrect directive names or misspellings.

3. Final Answer:

   upstream backend { least_conn; server 192.168.1.1; } -> Option A

4. Quick Check:

   Correct directive = least_conn [OK]

Hint: Use exact directive name 'least_conn' inside upstream block [OK]

Common Mistakes:

• Using 'least_connections' instead of 'least_conn'
• Misspelling the directive as 'leastconn' or 'least_conn_load'
• Placing directive outside the upstream block

3. Given this nginx upstream configuration:
<pre>upstream backend { least_conn; server 10.0.0.1; server 10.0.0.2; } If 10.0.0.1 has 5 active connections and 10.0.0.2 has 3 active connections, where will the next request be sent?

medium

A. To 10.0.0.1 because it is listed first

B. To both servers equally

C. To 10.0.0.2 because it has fewer active connections

D. To 10.0.0.1 because it has more active connections

Solution

1. Step 1: Identify the load balancing method

   The least_conn method sends requests to the server with the fewest active connections.

2. Step 2: Compare active connections of servers

   10.0.0.1 has 5 connections, 10.0.0.2 has 3 connections, so the next request goes to 10.0.0.2.

3. Final Answer:

   To 10.0.0.2 because it has fewer active connections -> Option C

4. Quick Check:

   Least connections picks server with 3 connections [OK]

Hint: Pick server with smallest active connections count [OK]

Common Mistakes:

• Choosing server listed first instead of fewest connections
• Assuming equal distribution regardless of connections
• Picking server with more connections by mistake

4. You configured nginx with least_conn but all requests keep going to the same server. What is the most likely cause?

medium

A. The servers have equal active connections, so nginx picks the first server always

B. The least_conn directive is misspelled in the config

C. The upstream block is missing the server directives

D. The nginx service was not reloaded after configuration change

Solution

1. Step 1: Check if configuration changes are active

   If nginx is not reloaded after config changes, old settings remain active causing unexpected behavior.

2. Step 2: Consider other causes

   Misspelling or missing servers cause errors or no load balancing, but requests going to one server usually means config not applied.

3. Final Answer:

   The nginx service was not reloaded after configuration change -> Option D

4. Quick Check:

   Reload nginx after config changes [OK]

Hint: Always reload nginx after config edits to apply changes [OK]

Common Mistakes:

• Ignoring the need to reload nginx after config update
• Assuming equal connections cause all traffic to one server
• Not verifying server directives exist in upstream block

5. You have three backend servers with varying response times and active connections:

• Server A: 2 active connections, slow response
• Server B: 5 active connections, fast response
• Server C: 2 active connections, medium response

Using least_conn load balancing, which server will receive the next request and why?

hard

A. Requests will be evenly distributed among all servers

B. Server A, because it has the fewest active connections and slow response is ignored

C. Server C, because it has the fewest active connections and better response than A

D. Server B, because it has the fastest response time despite more connections

Solution

1. Step 1: Understand least_conn prioritizes active connections

   It sends requests to servers with the fewest active connections, ignoring response time.

2. Step 2: Compare servers with fewest connections

   Server A and C both have 2 connections, but least_conn does not consider response speed, so it picks the first with fewest connections, Server A.

3. Final Answer:

   Server A, because it has the fewest active connections and slow response is ignored -> Option B

4. Quick Check:

   Least connections ignores speed, picks fewest active connections [OK]

Hint: Least connections ignores speed; picks server with fewest active connections [OK]

Common Mistakes:

• Assuming fastest response server is chosen with least_conn
• Thinking least_conn balances by response time
• Expecting even distribution regardless of connections