API versioning with routing in Nginx - Time & Space Complexity

Time Complexity: API versioning with routing

O(n)

Understanding Time Complexity

When using nginx to route API requests based on version, it is important to understand how the routing decisions scale as more versions or routes are added.

We want to know how the time to find the correct route grows when the number of API versions increases.

Scenario Under Consideration

Analyze the time complexity of the following nginx configuration snippet for API version routing.

server {
    listen 80;

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

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

    location /api/v3/ {
        proxy_pass http://backend_v3;
    }
}
    

This configuration routes requests to different backend servers based on the API version in the URL path.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: nginx checks each location block in order to find a matching prefix for the request URL.
• How many times: It compares the request path against each version prefix until it finds a match or exhausts the list.

How Execution Grows With Input

As the number of API versions (and thus location blocks) increases, nginx must check more prefixes to find the right route.

Input Size (n)	Approx. Operations
3 versions	Up to 3 prefix checks
10 versions	Up to 10 prefix checks
100 versions	Up to 100 prefix checks

Pattern observation: The number of prefix checks grows linearly with the number of API versions configured.

Final Time Complexity

Time Complexity: O(n)

This means the time to route a request grows linearly as more API versions are added.

Common Mistake

[X] Wrong: "nginx instantly finds the correct API version route regardless of how many versions exist."

[OK] Correct: nginx checks each location prefix in order, so more versions mean more checks before matching.

Interview Connect

Understanding how routing scales with configuration size helps you design efficient API gateways and shows you can reason about system performance beyond code.

Self-Check

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

Practice

1. What is the main purpose of using API versioning with routing in nginx?

easy

A. To block all API requests except the latest version

B. To combine all API versions into a single endpoint

C. To run multiple API versions side by side and route requests accordingly

D. To disable routing and serve static files only

Solution

1. Step 1: Understand API versioning concept

   API versioning allows different versions of an API to coexist, so clients using older versions still work.

2. Step 2: Role of nginx routing

   nginx uses location blocks to route requests to the correct API version based on the URL path.

3. Final Answer:

   To run multiple API versions side by side and route requests accordingly -> Option C

4. Quick Check:

   API versioning = multiple versions side by side [OK]

Hint: API versioning means routing requests to different versions [OK]

Common Mistakes:

• Thinking API versioning disables old versions
• Assuming all versions merge into one endpoint
• Confusing routing with blocking requests

2. Which nginx configuration snippet correctly routes requests to API version v1 at path /api/v1/?

easy

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

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

C. location /api/v1/* { proxy_pass http://backend_v1; }

D. location /api/v1$ { proxy_pass http://backend_v1; }

Solution

1. Step 1: Understand nginx location matching

   Using location /api/v1/ matches all requests starting with /api/v1/, including subpaths.

2. Step 2: Check syntax correctness

   location /api/v1/ { proxy_pass http://backend_v1; } uses correct syntax without wildcards or regex, which nginx does not support in this form.

3. Final Answer:

   location /api/v1/ { proxy_pass http://backend_v1; } -> Option A

4. Quick Check:

   Trailing slash in location matches subpaths [OK]

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

Common Mistakes:

• Using wildcards (*) in location which nginx does not support
• Missing trailing slash causing partial matches
• Using regex syntax without ~

3. Given this nginx config snippet, what backend will handle a request to /api/v2/users?

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

medium

A. http://backend_v2

B. No backend, 404 error

C. http://backend_v1

D. Both backends in round-robin

Solution

1. Step 1: Match request path to location blocks

   The request path /api/v2/users starts with /api/v2/, so it matches the second location block.

2. Step 2: Determine proxy backend

   The matching location proxies to http://backend_v2, so this backend handles the request.

3. Final Answer:

   http://backend_v2 -> Option A

4. Quick Check:

   Request path prefix matches location prefix [OK]

Hint: Match URL prefix to location prefix to find backend [OK]

Common Mistakes:

• Choosing backend_v1 for /api/v2/ path
• Assuming nginx load balances both backends automatically
• Thinking unmatched paths cause proxy to backend_v1

4. Identify the error in this nginx config for API versioning:

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

medium

A. proxy_pass must use IP address, not hostname

B. proxy_pass URLs must include trailing slash

C. location blocks cannot be adjacent

D. Missing trailing slash in first location causes incorrect routing

Solution

1. Step 1: Check location path consistency

   The first location uses /api/v1 without trailing slash, which matches only exact path or prefix differently than /api/v1/.

2. Step 2: Understand routing impact

   Requests like /api/v1/users won't match the first location correctly, causing routing errors.

3. Final Answer:

   Missing trailing slash in first location causes incorrect routing -> Option D

4. Quick Check:

   Trailing slash in location matters for prefix matching [OK]

Hint: Always use trailing slash in location for API version prefixes [OK]

Common Mistakes:

• Ignoring trailing slash difference in location paths
• Thinking proxy_pass URL must have trailing slash
• Believing location blocks cannot be next to each other

5. You want to support API versions v1 and v2 in nginx, but also redirect any request to /api/ without version to v2 by default. Which config snippet achieves this correctly?

hard

A. location /api/ { proxy_pass http://backend_v2; }
location /api/v1/ { proxy_pass http://backend_v1; }

B. location /api/v1/ { proxy_pass http://backend_v1; }
location /api/v2/ { proxy_pass http://backend_v2; }
location /api/ { return 301 /api/v2/; }

C. location /api/ { proxy_pass http://backend_v1; }
location /api/v2/ { proxy_pass http://backend_v2; }

D. location /api/v1/ { proxy_pass http://backend_v1; }
location /api/v2/ { proxy_pass http://backend_v2; }
location /api/ { proxy_pass http://backend_v2; }

Solution

1. Step 1: Define explicit version locations

   Locations for /api/v1/ and /api/v2/ proxy requests to respective backends.

2. Step 2: Redirect base /api/ to default version

   Using return 301 /api/v2/; in /api/ location sends clients to v2 URL, ensuring default version usage.

3. Final Answer:

   location /api/v1/ { proxy_pass http://backend_v1; } location /api/v2/ { proxy_pass http://backend_v2; } location /api/ { return 301 /api/v2/; } -> Option B

4. Quick Check:

   Redirect base path to default version with return 301 [OK]

Hint: Use return 301 to redirect base API path to default version [OK]

Common Mistakes:

• Proxying /api/ directly instead of redirecting
• Overlapping location blocks causing conflicts
• Using proxy_pass in /api/ without redirect