Weighted round-robin in Nginx - Time & Space Complexity

Time Complexity: Weighted round-robin

O(n)

Understanding Time Complexity

We want to understand how the time needed to pick a server grows as the number of servers increases in weighted round-robin load balancing.

How does the selection process scale when more servers with different weights are added?

Scenario Under Consideration

Analyze the time complexity of the following nginx weighted round-robin snippet.

upstream backend {
    server backend1.example.com weight=3;
    server backend2.example.com weight=1;
    server backend3.example.com weight=2;
}

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

This configuration distributes requests to servers based on their weights, cycling through them proportionally.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Iterating through the list of servers to select the next one based on weights.
• How many times: Once per request, cycling through all servers in weighted order.

How Execution Grows With Input

As the number of servers increases, the selection process checks more servers to find the next one according to weights.

Input Size (n)	Approx. Operations
3	3 checks per cycle
10	10 checks per cycle
100	100 checks per cycle

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

Final Time Complexity

Time Complexity: O(n)

This means the time to select a server grows directly in proportion to the number of servers configured.

Common Mistake

[X] Wrong: "Selecting a server in weighted round-robin is always constant time regardless of server count."

[OK] Correct: The selection process must check servers in order to respect weights, so more servers mean more checks.

Interview Connect

Understanding how load balancing scales helps you design systems that handle more traffic smoothly. This skill shows you can think about efficiency in real setups.

Self-Check

"What if nginx used a different algorithm that stored precomputed weighted lists? How would the time complexity change?"

Practice

1. What does the weight parameter control in nginx's weighted round-robin load balancing?

easy

A. The maximum number of connections a server can handle

B. The timeout duration for server responses

C. The order in which servers are listed in the config

D. The number of requests sent to a server relative to others

Solution

1. Step 1: Understand the role of weight in load balancing

   The weight defines how many requests a server receives compared to others.

2. Step 2: Relate weight to request distribution

   Higher weight means more requests go to that server, balancing load by capacity.

3. Final Answer:

   The number of requests sent to a server relative to others -> Option D

4. Quick Check:

   Weight controls request share [OK]

Hint: Weight sets request share per server [OK]

Common Mistakes:

• Confusing weight with timeout
• Thinking weight limits connections
• Assuming weight sets server order

2. Which of the following is the correct syntax to assign weights to servers in nginx for weighted round-robin?

easy

A. server backend1.example.com weight:3;

B. server backend1.example.com weight 3;

C. server backend1.example.com weight=3;

D. server backend1.example.com weight(3);

Solution

1. Step 1: Recall nginx upstream server syntax

   Weights are assigned using weight=number with an equal sign and semicolon.

2. Step 2: Check each option's syntax

   Only server backend1.example.com weight=3; uses the correct weight=3; format.

3. Final Answer:

   server backend1.example.com weight=3; -> Option C

4. Quick Check:

   Correct syntax uses equal sign and semicolon [OK]

Hint: Use weight=number; syntax for servers [OK]

Common Mistakes:

• Omitting equal sign
• Using colon instead of equal sign
• Using parentheses incorrectly

3. Given this nginx upstream block:

upstream backend {
  server backend1.example.com weight=3;
  server backend2.example.com weight=1;
}

If 8 requests arrive, how many requests will backend2 receive approximately?

medium

A. 2

B. 6

C. 4

D. 1

Solution

1. Step 1: Calculate total weight

   backend1 weight=3, backend2 weight=1, total = 4.

2. Step 2: Calculate requests for backend2

   Requests for backend2 = (1/4) * 8 = 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Requests proportional to weight [OK]

Hint: Requests split by weight ratio [OK]

Common Mistakes:

• Ignoring total weight sum
• Assigning equal requests despite weights
• Miscounting total requests

4. You configured nginx with weighted round-robin but all servers receive equal requests. What is the most likely cause?

medium

A. nginx does not support weighted round-robin

B. Weights were not specified correctly in the config

C. The servers have identical IP addresses

D. The upstream block is missing the weight directive

Solution

1. Step 1: Understand weighted round-robin requires correct weight syntax

   If weights are missing or incorrect, nginx defaults to equal distribution.

2. Step 2: Analyze the options

   Weights were not specified correctly in the config states weights not specified correctly, which explains equal requests.

3. Final Answer:

   Weights were not specified correctly in the config -> Option B

4. Quick Check:

   Incorrect weights cause equal load [OK]

Hint: Check weight syntax if load is equal [OK]

Common Mistakes:

• Assuming nginx lacks weighted support
• Confusing IP issues with load balancing
• Missing weight directive entirely

5. You have three servers with weights 5, 3, and 2. You want to add a fourth server but keep the total weight sum at 10. What weight should you assign to the new server to maintain the same total weight and keep the relative proportions of the first three servers?

hard

A. 0 (do not add the server)

B. 5

C. 2

D. 1

Solution

1. Step 1: Calculate current total weight

   Sum of existing weights = 5 + 3 + 2 = 10.

2. Step 2: Determine weight for new server

   To keep total sum at 10 when adding a fourth server, assign weight=0 to it.

3. Step 3: Verify proportions

   Weight=0 means no requests to the new server, so first three retain exact proportions (5:3:2 out of total 10).

4. Final Answer:

   0 (do not add the server) -> Option A

5. Quick Check:

   Weight=0 keeps total and proportions unchanged [OK]

Hint: Assign weight=0 to keep total sum and proportions [OK]

Common Mistakes:

• Assigning positive weight that increases total sum
• Forgetting to maintain exact total of 10
• Ignoring impact on relative proportions