Service discovery via DNS in Kubernetes - Time & Space Complexity

Time Complexity: Service discovery via DNS

O(n)

Understanding Time Complexity

When Kubernetes uses DNS for service discovery, it needs to find the right service address quickly.

We want to understand how the time to find a service changes as the number of services grows.

Scenario Under Consideration

Analyze the time complexity of the following Kubernetes DNS lookup process.

apiVersion: v1
kind: Service
metadata:
  name: my-service
spec:
  selector:
    app: my-app
  ports:
  - protocol: TCP
    port: 80
    targetPort: 9376

This defines a service that Kubernetes exposes and can be found via DNS by pods.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DNS query searches through the list of services in the cluster.
• How many times: The DNS server checks service records one by one until it finds a match.

How Execution Grows With Input

As the number of services increases, the DNS lookup takes longer because it checks more records.

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

Pattern observation: The time grows roughly in direct proportion to the number of services.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a service grows linearly as the number of services increases.

Common Mistake

[X] Wrong: "DNS lookup time stays the same no matter how many services exist."

[OK] Correct: DNS must check service records to find the right one, so more services mean more checks and longer lookup time.

Interview Connect

Understanding how service discovery scales helps you design systems that stay fast as they grow.

Self-Check

"What if Kubernetes used a caching system for DNS lookups? How would the time complexity change?"

Practice

1. What does Kubernetes use to help applications find each other without hardcoding IP addresses?

easy

A. Manual IP configuration

B. DNS-based service discovery

C. Static routing tables

D. Load balancer IPs only

Solution

1. Step 1: Understand service discovery basics

   Kubernetes provides a way for apps to find each other by name instead of IP, which can change.

2. Step 2: Identify the mechanism Kubernetes uses

   Kubernetes automatically creates DNS entries for services, enabling DNS-based discovery.

3. Final Answer:

   DNS-based service discovery -> Option B

4. Quick Check:

   Service discovery = DNS-based [OK]

Hint: Kubernetes uses DNS names, not fixed IPs, for service discovery [OK]

Common Mistakes:

• Thinking IPs are fixed and manually configured
• Confusing load balancers with service discovery
• Assuming static routing is used

2. Which of the following is the correct DNS name format to access a Kubernetes service named myapp in namespace prod?

easy

A. prod.myapp.svc.cluster.local

B. myapp.svc.prod.cluster.local

C. myapp.prod.svc.cluster.local

D. svc.myapp.prod.cluster.local

Solution

1. Step 1: Recall Kubernetes DNS naming convention

   The format is <service>.<namespace>.svc.cluster.local.

2. Step 2: Match the service and namespace

   For service myapp in namespace prod, the DNS name is myapp.prod.svc.cluster.local.

3. Final Answer:

   myapp.prod.svc.cluster.local -> Option C

4. Quick Check:

   Service.Namespace.svc.cluster.local = B [OK]

Hint: Service DNS = service.namespace.svc.cluster.local [OK]

Common Mistakes:

• Swapping service and namespace order
• Omitting 'svc' in the DNS name
• Using incorrect domain suffix

3. Given a pod in namespace dev trying to reach a service named backend, what DNS name should the pod use to connect to the service?

medium

A. backend.dev.svc.cluster.local

B. backend.svc.dev.cluster.local

C. dev.backend.svc.cluster.local

D. backend.dev.cluster.local

Solution

1. Step 1: Understand the DNS naming pattern

   Kubernetes services are accessible via service.namespace.svc.cluster.local.

2. Step 2: Apply the pattern for service backend in namespace dev

   The correct DNS name is backend.dev.svc.cluster.local.

3. Final Answer:

   backend.dev.svc.cluster.local -> Option A

4. Quick Check:

   Service.Namespace.svc.cluster.local = A [OK]

Hint: Use service.namespace.svc.cluster.local for full DNS name [OK]

Common Mistakes:

• Mixing up namespace and service order
• Leaving out 'svc' in the DNS name
• Using incomplete domain suffix

4. A pod tries to connect to db.prod.svc.cluster.local but fails. Which of these is the most likely cause?

medium

A. The pod is using the IP address instead of DNS name

B. The pod is in the same namespace as the service

C. The cluster DNS is disabled but service exists

D. The service db does not exist in namespace prod

Solution

1. Step 1: Check if the service exists in the namespace

   If the service db is missing in prod, DNS lookup fails.

2. Step 2: Consider DNS and pod namespace

   Using DNS name requires the service to exist; pod namespace or IP usage doesn't cause DNS failure.

3. Final Answer:

   The service db does not exist in namespace prod -> Option D

4. Quick Check:

   Missing service = DNS failure [OK]

Hint: Check service existence in namespace if DNS lookup fails [OK]

Common Mistakes:

• Assuming DNS is always enabled
• Confusing pod namespace with service namespace
• Thinking IP use breaks DNS resolution

5. You have a multi-namespace Kubernetes cluster with services named api in namespaces dev and prod. How can a pod in dev namespace connect to the api service in prod namespace using DNS?

hard

A. Use the full DNS name api.prod.svc.cluster.local

B. Use just api since it resolves across namespaces

C. Use api.dev.svc.cluster.local and specify namespace in config

D. Use the IP address of the prod service directly

Solution

1. Step 1: Understand cross-namespace DNS resolution

   Within a namespace, service names resolve locally; cross-namespace requires full DNS name.

2. Step 2: Apply full DNS name for cross-namespace access

   To reach api in prod from dev, use api.prod.svc.cluster.local.

3. Final Answer:

   Use the full DNS name api.prod.svc.cluster.local -> Option A

4. Quick Check:

   Cross-namespace = full DNS name [OK]

Hint: Cross-namespace access needs full DNS name service.namespace.svc.cluster.local [OK]

Common Mistakes:

• Assuming service name alone resolves across namespaces
• Using wrong namespace in DNS name
• Relying on IP addresses which can change