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?