URL maps for routing in GCP - Time & Space Complexity

Time Complexity: URL maps for routing

O(n)

Understanding Time Complexity

When using URL maps for routing in cloud infrastructure, it's important to understand how the routing decisions scale as the number of URL rules grows.

We want to know how the time to find the right route changes when more URL rules are added.

Scenario Under Consideration

Analyze the time complexity of the following URL map routing setup.

resource "google_compute_url_map" "example" {
  name = "example-url-map"

  default_service = google_compute_backend_service.default.self_link

  host_rule {
    hosts = ["example.com"]
    path_matcher = "path-matcher-1"
  }

  path_matcher {
    name = "path-matcher-1"
    default_service = google_compute_backend_service.default.self_link

    path_rule {
      paths = ["/images/*"]
      service = google_compute_backend_service.images.self_link
    }

    path_rule {
      paths = ["/videos/*"]
      service = google_compute_backend_service.videos.self_link
    }
  }
}
    

This configuration routes requests based on host and path rules to different backend services.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Matching incoming request paths against path rules in the URL map.
• How many times: Once per incoming request, checking each path rule until a match is found.

How Execution Grows With Input

As the number of path rules increases, the routing system checks more rules to find the correct backend.

Input Size (n)	Approx. Path Rules Checked
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows roughly in direct proportion to the number of path rules.

Final Time Complexity

Time Complexity: O(n)

This means the time to route a request grows linearly with the number of path rules to check.

Common Mistake

[X] Wrong: "Routing time stays the same no matter how many path rules exist."

[OK] Correct: Each additional path rule adds more checks, so routing takes longer as rules increase.

Interview Connect

Understanding how routing scales helps you design efficient URL maps and anticipate performance as your app grows.

Self-Check

"What if the URL map used a tree structure for path matching instead of a list? How would the time complexity change?"

Practice

1. What is the main purpose of a URL map in Google Cloud Platform's load balancing?

easy

A. To store user data for web applications

B. To create virtual machines automatically

C. To route incoming web traffic to different backend services based on URL paths or hosts

D. To monitor network traffic usage

Solution

1. Step 1: Understand URL map role

   A URL map directs web traffic to backend services depending on URL patterns.

2. Step 2: Identify correct function

   Routing based on URL paths or hosts matches the description of URL maps.

3. Final Answer:

   To route incoming web traffic to different backend services based on URL paths or hosts -> Option C

4. Quick Check:

   URL maps route traffic = B [OK]

Hint: URL maps decide backend by URL pattern [OK]

Common Mistakes:

• Confusing URL maps with storage or VM services
• Thinking URL maps monitor traffic instead of routing
• Assuming URL maps create resources automatically

2. Which of the following is the correct syntax to define a path matcher in a GCP URL map configuration?

easy

A. "pathMatcher": {"name": "pm1", "defaultService": "backend1"}

B. "pathMatchers": [{"name": "pm1", "defaultService": "backend1"}]

C. "pathMatchers": {"name": "pm1", "defaultService": "backend1"}

D. "pathMatcher": [{"name": "pm1", "defaultService": "backend1"}]

Solution

1. Step 1: Identify correct key for multiple path matchers

   The key for multiple path matchers is plural: "pathMatchers" with an array value.

2. Step 2: Confirm value type

   The value must be an array of objects, so square brackets [] are needed.

3. Final Answer:

   "pathMatchers": [{"name": "pm1", "defaultService": "backend1"}] -> Option B

4. Quick Check:

   Multiple path matchers use "pathMatchers" array = A [OK]

Hint: Use plural "pathMatchers" with array brackets [OK]

Common Mistakes:

• Using singular "pathMatcher" for multiple entries
• Using object instead of array for pathMatchers
• Mixing singular/plural keys incorrectly

3. Given this URL map snippet, which backend service will handle the request to https://example.com/images/logo.png?

{
  "defaultService": "backend-default",
  "pathMatchers": [
    {
      "name": "pm-images",
      "defaultService": "backend-images",
      "pathRules": [
        {"paths": ["/images/*"], "service": "backend-images"}
      ]
    }
  ]
}

medium

A. backend-images

B. No backend matches, request fails

C. backend-logo

D. backend-default

Solution

1. Step 1: Check path rules for "/images/*"

   The path matcher "pm-images" has a path rule matching "/images/*" directing to "backend-images".

2. Step 2: Match request URL path

   The request path "/images/logo.png" matches the "/images/*" pattern, so it routes to "backend-images".

3. Final Answer:

   backend-images -> Option A

4. Quick Check:

   Path "/images/*" matches request = backend-images [OK]

Hint: Match URL path to pathRules first, else defaultService [OK]

Common Mistakes:

• Choosing defaultService without checking pathRules
• Assuming no match causes failure instead of default routing
• Confusing path patterns with exact matches

4. You have this URL map configuration snippet:

{
  "defaultService": "backend-default",
  "pathMatchers": [
    {
      "name": "pm1",
      "defaultService": "backend1",
      "pathRules": [
        {"paths": ["/app/*"], "service": "backend-app"}
      ]
    }
  ]
}

Why does a request to https://example.com/app go to backend-default instead of backend-app?

medium

A. The defaultService overrides all pathRules

B. The path matcher name "pm1" is invalid

C. The backend service "backend-app" is not defined

D. The path "/app" does not match the pattern "/app/*" which requires a trailing slash

Solution

1. Step 1: Understand path pattern matching

   The pattern "/app/*" matches paths starting with "/app/" but not "/app" exactly.

2. Step 2: Check request path against pattern

   The request path "/app" lacks the trailing slash, so it does not match "/app/*" and falls back to defaultService.

3. Final Answer:

   The path "/app" does not match the pattern "/app/*" which requires a trailing slash -> Option D

4. Quick Check:

   Trailing slash matters in path patterns = C [OK]

Hint: Path patterns with * need trailing slash to match [OK]

Common Mistakes:

• Assuming "/app" matches "/app/*" without slash
• Thinking defaultService always overrides pathRules
• Believing backend service must be explicitly defined to route

5. You want to route requests to https://example.com/api/v1/users to backend-v1 and requests to https://example.com/api/v2/users to backend-v2. Which URL map configuration correctly achieves this?

hard

A. {
"defaultService": "backend-default",
"pathMatchers": [
{
"name": "pm-api",
"defaultService": "backend-default",
"pathRules": [
{"paths": ["/api/v1/*"], "service": "backend-v1"},
{"paths": ["/api/v2/*"], "service": "backend-v2"}
]
}
]
}

B. {
"defaultService": "backend-default",
"pathMatchers": [
{
"name": "pm-api",
"defaultService": "backend-v1",
"pathRules": [
{"paths": ["/api/v1/*"], "service": "backend-v1"},
{"paths": ["/api/v2/*"], "service": "backend-v2"}
]
}
]
}

C. {
"defaultService": "backend-default",
"pathMatchers": [
{
"name": "pm-api",
"defaultService": "backend-v2",
"pathRules": [
{"paths": ["/api/v1/*"], "service": "backend-v1"}
]
}
]
}

D. {
"defaultService": "backend-default",
"pathMatchers": [
{
"name": "pm-api",
"defaultService": "backend-default",
"pathRules": [
{"paths": ["/api/*"], "service": "backend-v1"},
{"paths": ["/api/*"], "service": "backend-v2"}
]
}
]
}

Solution

1. Step 1: Check path rules for specific version routing

   { "defaultService": "backend-default", "pathMatchers": [ { "name": "pm-api", "defaultService": "backend-default", "pathRules": [ {"paths": ["/api/v1/*"], "service": "backend-v1"}, {"paths": ["/api/v2/*"], "service": "backend-v2"} ] } ] } defines two distinct path rules: "/api/v1/*" to "backend-v1" and "/api/v2/*" to "backend-v2" which matches requirements.

2. Step 2: Verify defaultService and pathRules consistency

   { "defaultService": "backend-default", "pathMatchers": [ { "name": "pm-api", "defaultService": "backend-default", "pathRules": [ {"paths": ["/api/v1/*"], "service": "backend-v1"}, {"paths": ["/api/v2/*"], "service": "backend-v2"} ] } ] } uses "backend-default" as defaultService, so unmatched paths go there, which is correct.

3. Step 3: Identify issues in other options

   { "defaultService": "backend-default", "pathMatchers": [ { "name": "pm-api", "defaultService": "backend-v1", "pathRules": [ {"paths": ["/api/v1/*"], "service": "backend-v1"}, {"paths": ["/api/v2/*"], "service": "backend-v2"} ] } ] } sets defaultService to "backend-v1" which may misroute unmatched paths. { "defaultService": "backend-default", "pathMatchers": [ { "name": "pm-api", "defaultService": "backend-v2", "pathRules": [ {"paths": ["/api/v1/*"], "service": "backend-v1"} ] } ] } misses "/api/v2/*" pathRule. { "defaultService": "backend-default", "pathMatchers": [ { "name": "pm-api", "defaultService": "backend-default", "pathRules": [ {"paths": ["/api/*"], "service": "backend-v1"}, {"paths": ["/api/*"], "service": "backend-v2"} ] } ] } duplicates "/api/*" paths causing conflict.

4. Final Answer:

   Option A correctly routes /api/v1/* and /api/v2/* to respective backends -> Option A

5. Quick Check:

   Distinct pathRules for versions = A [OK]

Hint: Use distinct pathRules for each version prefix [OK]

Common Mistakes:

• Setting defaultService to one version backend
• Missing pathRule for one version
• Duplicating same path pattern causing conflicts