Wildcard and regex server names in Nginx - Time & Space Complexity

Time Complexity: Wildcard and regex server names

O(n)

Understanding Time Complexity

When nginx receives a request, it matches the server name to find the right configuration. This matching can use wildcards or regular expressions.

We want to understand how the time to find the matching server grows as the number of server names increases.

Scenario Under Consideration

Analyze the time complexity of the following nginx server name matching snippet.

server {
    server_name example.com *.example.com ~^www\d+\.example\.com$;
    # ... other config ...
}

server {
    server_name api.example.com;
    # ... other config ...
}

server {
    server_name ~^blog\.(.+)\.example\.com$;
    # ... other config ...
}

This snippet shows server blocks with exact names, wildcard names, and regex names nginx uses to match incoming requests.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: nginx checks each server block's server_name patterns one by one.
• How many times: It repeats this check for each server block until a match is found or all are checked.

How Execution Grows With Input

As the number of server blocks grows, nginx must check more names to find a match.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows directly with the number of server names to test.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a matching server grows linearly as more server names are added.

Common Mistake

[X] Wrong: "nginx matches server names instantly no matter how many there are."

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

Interview Connect

Understanding how nginx matches server names helps you reason about performance in real systems. This skill shows you can think about how configuration size affects response time.

Self-Check

What if nginx used a hash table for exact server names instead of checking each one? How would the time complexity change?

Practice

1. What does a wildcard server name like *.example.com match in nginx?

easy

A. Any domain ending with example.com, including example.com itself

B. Only the exact domain example.com

C. Any subdomain of example.com, like blog.example.com or shop.example.com

D. Only domains starting with a star character

Solution

1. Step 1: Understand wildcard usage in server names

   A wildcard * before a domain matches any subdomain part, but not the root domain itself.

2. Step 2: Apply to *.example.com

   This matches domains like blog.example.com or shop.example.com, but not example.com alone.

3. Final Answer:

   Any subdomain of example.com, like blog.example.com or shop.example.com -> Option C

4. Quick Check:

   Wildcard * matches subdomains only [OK]

Hint: Wildcard * matches subdomains, not the root domain [OK]

Common Mistakes:

• Thinking wildcard matches the root domain
• Confusing wildcard with regex syntax
• Assuming wildcard matches any domain ending

2. Which of the following is the correct syntax to define a regex server name in nginx?

easy

A. server_name /www\d+\.example\.com/;

B. server_name *example.com;

C. server_name ^www\d+\.example\.com$;

D. server_name ~^www\d+\.example\.com$;

Solution

1. Step 1: Recall regex server name syntax in nginx

   Regex server names start with a tilde ~ followed by the regex pattern.

2. Step 2: Check each option

   server_name ~^www\d+\.example\.com$; uses ~^www\d+\.example\.com$ which is correct regex syntax. Others either miss the tilde or use invalid delimiters.

3. Final Answer:

   server_name ~^www\d+\.example\.com$; -> Option D

4. Quick Check:

   Regex server names start with ~ [OK]

Hint: Regex server names always start with ~ in nginx [OK]

Common Mistakes:

• Omitting the ~ before regex pattern
• Using * instead of ~ for regex
• Using slashes / / as regex delimiters

3. Given this nginx config snippet:

server {
  server_name ~^www\d+\.example\.com$;
  return 200 'Matched regex server name';
}

What will be the response for a request to www12.example.com?

medium

A. Matched regex server name

B. 500 Internal Server Error

C. 404 Not Found

D. Default nginx welcome page

Solution

1. Step 1: Understand the regex pattern

   The regex ^www\d+\.example\.com$ matches domains starting with 'www' followed by one or more digits, then '.example.com'.

2. Step 2: Check if 'www12.example.com' matches

   'www12.example.com' matches the pattern because '12' are digits after 'www'.

3. Final Answer:

   Matched regex server name -> Option A

4. Quick Check:

   Regex matches www12.example.com [OK]

Hint: Check if domain fits regex pattern exactly [OK]

Common Mistakes:

• Assuming regex matches partial strings
• Ignoring start ^ and end $ anchors
• Confusing regex with wildcard matching

4. You wrote this nginx config:

server {
  server_name ~www\d+\.example\.com$;
  return 200 'Hello';
}

Why is this regex server_name directive incorrect?

medium

A. Missing ^ anchor at start of regex

B. Regex server name must start with ~ and pattern must start with ^

C. Regex pattern missing delimiters like / /

D. Regex server name must start with ~ and pattern must be valid

Solution

1. Step 1: Check regex server_name syntax

   Regex server names must start with ~ and the pattern should start with ^ to match from the beginning.

2. Step 2: Identify missing ^ anchor

   The pattern www\d+\.example\.com$ lacks the ^ anchor, causing partial matches rather than full hostname matches.

3. Final Answer:

   Regex server name must start with ~ and pattern must start with ^ -> Option B

4. Quick Check:

   Regex patterns need ^ anchor at start [OK]

Hint: Regex patterns should start with ^ for nginx server_name [OK]

Common Mistakes:

• Omitting ^ anchor in regex pattern
• Thinking delimiters like / / are needed
• Ignoring nginx error messages about regex

5. You want nginx to serve requests for any subdomain of example.com except www.example.com. Which server_name config achieves this?

hard

A. server_name ~^(?!www\.)[^.]+\.example\.com$;

B. server_name *.example.com www.example.com;

C. server_name ~^www\d+\.example\.com$;

D. server_name example.com *.example.com;

Solution

1. Step 1: Understand the requirement

   We want to match any subdomain except 'www.example.com'. This requires a regex with negative lookahead.

2. Step 2: Analyze options

   server_name ~^(?!www\.)[^.]+\.example\.com$; uses ~^(?!www\.)[^.]+\.example\.com$ which matches any subdomain not starting with 'www.'. Others either include 'www' or don't exclude it.

3. Final Answer:

   server_name ~^(?!www\.)[^.]+\.example\.com$; -> Option A

4. Quick Check:

   Negative lookahead excludes www subdomain [OK]

Hint: Use negative lookahead in regex to exclude specific subdomains [OK]

Common Mistakes:

• Using wildcard that includes www.example.com
• Not using regex for exclusion
• Confusing wildcard and regex syntax