API routing with location blocks in Nginx - Time & Space Complexity

Time Complexity: API routing with location blocks

O(n)

Understanding Time Complexity

When nginx receives a request, it checks location blocks to find the best match. Understanding how this matching grows with more locations helps us see how fast nginx can route requests.

We want to know: how does the time to find the right location change as we add more routes?

Scenario Under Consideration

Analyze the time complexity of the following nginx location routing snippet.

server {
    listen 80;

    location /api/v1/ {
        proxy_pass http://backend_v1;
    }

    location /api/v2/ {
        proxy_pass http://backend_v2;
    }

    location /api/ {
        proxy_pass http://backend_default;
    }
}
    

This configuration routes requests to different backends based on the URL path prefix.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: nginx checks each location block in order to find the best match.
• How many times: It compares the request path against each location until it finds the best fit.

How Execution Grows With Input

As the number of location blocks grows, nginx must check more entries to find the right route.

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

Pattern observation: The number of checks grows roughly in direct proportion to the number of location blocks.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the right location grows linearly as you add more location blocks.

Common Mistake

[X] Wrong: "nginx instantly finds the right location no matter how many routes there are."

[OK] Correct: nginx checks locations one by one until it finds the best match, so more routes mean more checks and longer matching time.

Interview Connect

Understanding how routing scales helps you design efficient server configs and shows you think about performance in real systems. This skill is useful when working with web servers or APIs.

Self-Check

"What if nginx used a hash map for location matching instead of checking each location in order? How would the time complexity change?"

Practice

1. What does a location block in an nginx configuration do?

easy

A. Sets the maximum file upload size

B. Defines server IP addresses

C. Specifies the server's operating system

D. Routes incoming requests based on URL paths

Solution

1. Step 1: Understand the purpose of location blocks

   Location blocks in nginx are used to match parts of the URL path to decide how to handle requests.

2. Step 2: Identify what location blocks control

   They control routing of requests to different handlers or backends based on the URL.

3. Final Answer:

   Routes incoming requests based on URL paths -> Option D

4. Quick Check:

   Location blocks = URL routing [OK]

Hint: Location blocks match URL paths to route requests [OK]

Common Mistakes:

• Confusing location blocks with server IP settings
• Thinking location blocks set server OS
• Assuming location blocks control upload size

2. Which of the following is the correct syntax to define a location block that matches exactly the path /api/v1/users?

easy

A. location = /api/v1/users { ... }

B. location /api/v1/users { ... }

C. location ~ /api/v1/users { ... }

D. location ^~ /api/v1/users { ... }

Solution

1. Step 1: Recall nginx location modifiers

   The = modifier means exact match of the URL path.

2. Step 2: Match the exact path syntax

   Using location = /api/v1/users matches only that exact path.

3. Final Answer:

   location = /api/v1/users { ... } -> Option A

4. Quick Check:

   Exact match uses = modifier [OK]

Hint: Use '=' for exact path match in location [OK]

Common Mistakes:

• Using no modifier for exact match
• Using regex (~) when exact match needed
• Using ^~ which is prefix but not exact

3. Given this nginx config snippet:

location /api/ {
  proxy_pass http://backend-service/;
}

What happens when a client requests /api/users?

medium

A. Request is forwarded to http://backend-service/users

B. Request is forwarded to http://backend-service/api/users

C. Request is served locally from /api/users directory

D. Request returns 404 Not Found

Solution

1. Step 1: Understand proxy_pass with trailing slash

   When proxy_pass URL ends with a slash, nginx replaces the matching part of the request URI.

2. Step 2: Apply to the request path

   The matching prefix /api/ is replaced by / from proxy_pass, so /api/users becomes /users at backend.

3. Final Answer:

   Request is forwarded to http://backend-service/users -> Option A

4. Quick Check:

   proxy_pass with trailing slash replaces prefix [OK]

Hint: Trailing slash in proxy_pass replaces matched prefix [OK]

Common Mistakes:

• Assuming proxy_pass appends full original URI
• Confusing local serving with proxying
• Ignoring trailing slash effect in proxy_pass

4. Identify the error in this nginx location block:

location /api {
  proxy_pass http://backend-service/;
}

medium

A. Missing trailing slash in location path causes wrong proxying

B. location path should end with a slash to match subpaths

C. proxy_pass URL must not have a trailing slash

D. No error; configuration is correct

Solution

1. Step 1: Check location path matching behavior

   Without a trailing slash, location /api matches only the exact path /api and not subpaths like /api/users.

2. Step 2: Correct usage for subpath matching

   To match /api and all subpaths, use location /api/ with trailing slash.

3. Final Answer:

   location path should end with a slash to match subpaths -> Option B

4. Quick Check:

   Trailing slash in location matches subpaths [OK]

Hint: Add trailing slash in location to match subpaths [OK]

Common Mistakes:

• Thinking proxy_pass trailing slash is wrong here
• Assuming location without slash matches subpaths
• Believing config is error-free without checking path

5. You want to route all requests starting with /api/v2/ to http://v2-backend/ but requests exactly to /api/v2/status should return a static JSON response locally. Which nginx config achieves this?

hard

A. location /api/v2/status { return 200 '{"status":"ok"}'; }
location ^~ /api/v2/ { proxy_pass http://v2-backend/; }

B. location /api/v2/status { proxy_pass http://v2-backend/status; }
location /api/v2/ { proxy_pass http://v2-backend/; }

C. location = /api/v2/status { return 200 '{"status":"ok"}'; }
location /api/v2/ { proxy_pass http://v2-backend/; }

D. location /api/v2/ { proxy_pass http://v2-backend/; }
location = /api/v2/status { proxy_pass http://v2-backend/status; }

Solution

1. Step 1: Use exact match for static response

   Use location = /api/v2/status to match exactly that path and return static JSON.

2. Step 2: Use prefix match for all other /api/v2/ requests

   Use location /api/v2/ to proxy all other requests to backend.

3. Final Answer:

   location = /api/v2/status { return 200 '{"status":"ok"}'; } location /api/v2/ { proxy_pass http://v2-backend/; } -> Option C

4. Quick Check:

   Exact match first, then prefix proxy [OK]

Hint: Exact match location before prefix for special cases [OK]

Common Mistakes:

• Placing prefix location before exact match causing override
• Using proxy_pass for static JSON response
• Not escaping JSON properly in return directive