Prefix match in Nginx - Time & Space Complexity

Time Complexity: Prefix match

O(n)

Understanding Time Complexity

We want to understand how the time to find a prefix match in nginx changes as the number of prefixes grows.

How does nginx handle many prefix rules efficiently?

Scenario Under Consideration

Analyze the time complexity of the following nginx prefix match configuration.

location /images/ {
    # serve images
}
location /images/thumbnails/ {
    # serve thumbnails
}
location /images/icons/ {
    # serve icons
}

This snippet shows multiple prefix locations nginx checks to find the best match for a request URL.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: nginx compares the request URI against each prefix location.
• How many times: It checks prefixes one by one until it finds the longest matching prefix.

How Execution Grows With Input

As the number of prefix locations increases, nginx must check more prefixes to find the best match.

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

Pattern observation: The number of checks grows linearly with the number of prefix locations.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a prefix match grows directly with how many prefix rules there are.

Common Mistake

[X] Wrong: "nginx finds prefix matches instantly no matter how many prefixes exist."

[OK] Correct: nginx checks prefixes one by one, so more prefixes mean more checks and longer time.

Interview Connect

Understanding how prefix matching scales helps you explain real-world server behavior clearly and confidently.

Self-Check

"What if nginx used a tree structure to store prefixes? How would the time complexity change?"

Practice

1. What does prefix match in nginx do when routing requests?

easy

A. It matches requests based on the start of the URL path.

B. It matches requests only if the full URL matches exactly.

C. It matches requests based on the file extension.

D. It matches requests randomly to any location block.

Solution

1. Step 1: Understand prefix match concept

   Prefix match means nginx checks if the URL path starts with a specific string.

2. Step 2: Compare with other matching types

   Exact match requires full URL match, file extension match is unrelated, random match is invalid.

3. Final Answer:

   It matches requests based on the start of the URL path. -> Option A

4. Quick Check:

   Prefix match = start of URL path [OK]

Hint: Prefix match checks URL start, not full or random [OK]

Common Mistakes:

• Confusing prefix match with exact match
• Thinking prefix match checks file extensions
• Assuming prefix match is random

2. Which of the following is the correct syntax for a prefix match location in nginx?

easy

A. location = /images/ { }

B. location ^~ /images/ { }

C. location /images/ { }

D. location ~ /images/ { }

Solution

1. Step 1: Identify prefix match syntax

   Prefix match uses plain location /prefix/ { } without modifiers.

2. Step 2: Understand other modifiers

   = is exact match, ^~ is prefix but with higher priority, ~ is regex match.

3. Final Answer:

   location /images/ { } -> Option C

4. Quick Check:

   Plain location = prefix match [OK]

Hint: Plain location block means prefix match [OK]

Common Mistakes:

• Using = or ^~ modifiers for simple prefix match
• Confusing regex (~) with prefix match
• Missing trailing slash in prefix

3. Given this nginx config snippet:

location /app/ {
  proxy_pass http://backend1;
}
location /app/api/ {
  proxy_pass http://backend2;
}

Which backend will handle a request to /app/api/users?

medium

A. Both backends in round-robin

B. http://backend2

C. No backend, 404 error

D. http://backend1

Solution

1. Step 1: Understand prefix match selection

   nginx selects the location with the longest matching prefix for plain prefix locations (no modifiers).

2. Step 2: Compare prefixes

   Both /app/ (length 5) and /app/api/ (length 9) match /app/api/users, but /app/api/ is longer, so it wins.

3. Final Answer:

   http://backend2 -> Option B

4. Quick Check:

   Longest prefix wins [OK]

Hint: Longest matching prefix wins [OK]

Common Mistakes:

• Thinking config order (first match) wins instead of longest prefix
• Thinking regex or exact match applies here
• Believing nginx load balances both backends

4. You wrote this nginx config:

location /static {
  root /var/www/html;
}

Requests to /static/css/style.css return 404. What is the likely error?

medium

A. root directive path is incorrect

B. location block should use = modifier

C. Missing trailing slash in location prefix

D. proxy_pass is missing

Solution

1. Step 1: Understand root directive behavior

   root appends the full request URI (/static/css/style.css) to /var/www/html, looking for /var/www/html/static/css/style.css.

2. Step 2: Identify likely cause

   If static files are at /var/www/html/css/style.css (without static/), root path doesn't strip prefix, causing 404. (Use alias /var/www/html; to strip.)

3. Final Answer:

   root directive path is incorrect -> Option A

4. Quick Check:

   root + full URI (no prefix strip) [OK]

Hint: root appends full URI; alias strips prefix [OK]

Common Mistakes:

• Confusing root (full URI) with alias (strips prefix)
• Thinking trailing slash strips prefix for root
• Adding unnecessary modifiers like =

5. You want nginx to route all requests starting with /api/ to http://backend_api and all others to http://backend_web, ensuring the /api/ prefix has priority even if regex locations follow. Which config correctly uses prefix match for this?

hard

A. location ~ /api/ {
proxy_pass http://backend_api;
}
location / {
proxy_pass http://backend_web;
}

B. location /api/ {
proxy_pass http://backend_api;
}
location / {
proxy_pass http://backend_web;
}

C. location = /api/ {
proxy_pass http://backend_api;
}
location / {
proxy_pass http://backend_web;
}

D. location ^~ /api/ {
proxy_pass http://backend_api;
}
location / {
proxy_pass http://backend_web;
}

Solution

1. Step 1: Use ^~ for prefix priority

   The ^~ modifier tells nginx to stop searching if prefix matches, ensuring /api/ routes to backend_api even over later regex.

2. Step 2: Default location for others

   The plain location / { } catches all other requests to backend_web.

3. Final Answer:

   location ^~ /api/ { proxy_pass http://backend_api; } location / { proxy_pass http://backend_web; } -> Option D

4. Quick Check:

   ^~ prefix match for priority routing [OK]

Hint: Use ^~ to prioritize prefix match over regex [OK]

Common Mistakes:

• Not using ^~ causes regex or exact match to override
• Using = modifier limits to exact /api/ only
• Using ~ makes it regex, not prefix match