Proxy cache key in Nginx - Time & Space Complexity

Time Complexity: Proxy cache key

O(1)

Understanding Time Complexity

We want to understand how the time to find or store a cached response grows as more requests come in.

How does the proxy cache key affect the speed of caching operations?

Scenario Under Consideration

Analyze the time complexity of this nginx proxy cache key configuration.

proxy_cache_key "$scheme://$host$request_uri";
proxy_cache my_cache;
proxy_cache_valid 200 10m;
proxy_pass http://backend;

This code sets the cache key to the full URL and uses it to store and retrieve cached responses.

Identify Repeating Operations

Look at what repeats when handling many requests.

• Primary operation: Hashing the cache key and checking the corresponding cache entry.
• How many times: Once per incoming request.

How Execution Grows With Input

As the number of cached items grows, finding the right cache entry takes constant work thanks to hashing.

Input Size (n)	Approx. Operations
10	About 1 hash + check
100	About 1 hash + check
1000	About 1 hash + check

Pattern observation: The number of operations stays roughly constant regardless of the number of cached items.

Final Time Complexity

Time Complexity: O(1)

This means the time to find a cached response stays constant as the cache size grows.

Common Mistake

[X] Wrong: "The cache lookup time grows linearly no matter what."

[OK] Correct: Nginx proxy cache hashes the key to compute a direct storage location (e.g., file path), enabling average O(1) lookups.

Interview Connect

Understanding how cache keys affect lookup time helps you explain how caching impacts performance in real systems.

Self-Check

"What if the cache used a hash table for keys? How would the time complexity change?"

Practice

1. What is the main purpose of the proxy_cache_key directive in nginx?

easy

A. To define how nginx identifies and stores cached content

B. To set the maximum size of the cache

C. To specify the cache expiration time

D. To enable SSL for proxy connections

Solution

1. Step 1: Understand the role of proxy_cache_key

   The proxy_cache_key tells nginx how to uniquely identify cached content by combining variables like scheme, host, and URI.

2. Step 2: Differentiate from other cache settings

   Other directives control cache size or expiration, but proxy_cache_key specifically defines the cache lookup key.

3. Final Answer:

   To define how nginx identifies and stores cached content -> Option A

4. Quick Check:

   proxy_cache_key = cache identifier [OK]

Hint: proxy_cache_key sets cache identity, not size or time [OK]

Common Mistakes:

• Confusing cache key with cache size or expiration
• Thinking it enables SSL
• Assuming it controls cache storage location

2. Which of the following is the correct syntax to set a proxy cache key using scheme, host, and request URI in nginx?

easy

A. proxy_cache_key $scheme$host$request_uri;

B. proxy_cache_key $scheme://$host$request_uri;

C. proxy_cache_key $scheme://host$request_uri;

D. proxy_cache_key "$scheme://$host$request_uri";

Solution

1. Step 1: Check syntax for proxy_cache_key

   The value must be a string, so it should be enclosed in double quotes if it contains special characters like ://.

2. Step 2: Verify variable usage

   Variables like $scheme, $host, and $request_uri must be concatenated properly inside quotes.

3. Final Answer:

   proxy_cache_key "$scheme://$host$request_uri"; -> Option D

4. Quick Check:

   Quotes needed for complex keys = proxy_cache_key "$scheme://$host$request_uri"; [OK]

Hint: Use quotes when combining variables with symbols like :// [OK]

Common Mistakes:

• Omitting quotes around the key string
• Missing $ before variables
• Incorrect concatenation without quotes

3. Given this nginx config snippet:

proxy_cache_key "$scheme://$host$request_uri";

What will be the cache key for a request to https://example.com/path/page?query=1?

medium

A. example.com/path/page?query=1

B. https://example.com/path/page?query=1

C. https://example.com/path/page

D. http://example.com/path/page?query=1

Solution

1. Step 1: Substitute variables with request values

   $scheme is 'https', $host is 'example.com', and $request_uri includes path and query: '/path/page?query=1'.

2. Step 2: Combine variables as per the key format

   Joining them gives 'https://example.com/path/page?query=1'.

3. Final Answer:

   https://example.com/path/page?query=1 -> Option B

4. Quick Check:

   Variables combined exactly = https://example.com/path/page?query=1 [OK]

Hint: Remember $request_uri includes query string [OK]

Common Mistakes:

• Ignoring the query string in $request_uri
• Using http instead of https for scheme
• Leaving out the scheme or host

4. You set proxy_cache_key "$scheme://$host$uri"; but nginx caches different query strings as the same content. What is the likely cause?

medium

A. You did not enable proxy_cache_path

B. You used $request_uri which already includes query string

C. You forgot to include $args in the cache key

D. You used double quotes instead of single quotes

Solution

1. Step 1: Understand $uri vs $request_uri

   $uri contains only the path (normalized), excluding the query string. $request_uri includes the query.

2. Step 2: Analyze the symptom

   Different query strings yield the same $uri, hence same cache key, causing shared cache content.

3. Final Answer:

   You forgot to include $args in the cache key -> Option C

4. Quick Check:

   $uri excludes query; add $args [OK]

Hint: $uri lacks query string; add $args [OK]

Common Mistakes:

• Confusing cache key with cache size or expiration
• Thinking it enables SSL
• Assuming it controls cache storage location

5. You want to cache content separately for mobile and desktop users. Which proxy cache key configuration achieves this if user agent contains 'Mobile' for mobile devices?

hard

A. proxy_cache_key "$scheme://$host$request_uri:$is_mobile"; # where $is_mobile is set by map

B. proxy_cache_key "$scheme://$host$request_uri:$http_user_agent ~* Mobile";

C. proxy_cache_key "$scheme://$host$request_uri:$http_user_agent";

D. proxy_cache_key "$scheme://$host$request_uri";

Solution

1. Step 1: Understand the need for conditional cache key

   We want to separate cache for mobile and desktop, so the key must include a variable indicating device type.

2. Step 2: Use a map to set $is_mobile variable

   nginx can use map to set $is_mobile to 'mobile' or 'desktop' based on $http_user_agent matching 'Mobile'. Including $is_mobile in cache key separates caches.

3. Step 3: Evaluate options

   proxy_cache_key "$scheme://$host$request_uri:$http_user_agent"; uses full user agent, which is too specific and causes cache fragmentation. proxy_cache_key "$scheme://$host$request_uri:$http_user_agent ~* Mobile"; is invalid syntax. proxy_cache_key "$scheme://$host$request_uri"; ignores device type. proxy_cache_key "$scheme://$host$request_uri:$is_mobile"; # where $is_mobile is set by map correctly uses $is_mobile set by map.

4. Final Answer:

   proxy_cache_key "$scheme://$host$request_uri:$is_mobile"; # where $is_mobile is set by map -> Option A

5. Quick Check:

   Use map variable for device type in cache key = proxy_cache_key "$scheme://$host$request_uri:$is_mobile"; # where $is_mobile is set by map [OK]

Hint: Use map to create $is_mobile variable for cache key [OK]

Common Mistakes:

• Using full user agent causing too many cache entries
• Trying regex inside proxy_cache_key (invalid)
• Ignoring device type in cache key