Distributed tracing in HLD - System Design Exercise

Design: Distributed Tracing System

Design covers trace data collection, storage, query, and visualization. Does not cover instrumentation libraries in detail or alerting systems.

Functional Requirements

FR1: Collect trace data from multiple microservices in a distributed system

FR2: Track requests as they flow through different services

FR3: Visualize the end-to-end request path with timing information

FR4: Support high throughput with minimal impact on service latency

FR5: Allow querying traces by trace ID, service name, or time range

FR6: Provide sampling to control data volume

FR7: Integrate with existing logging and monitoring tools

Non-Functional Requirements

NFR1: Handle up to 100,000 traces per second

NFR2: API response latency for trace queries under 500ms (p99)

NFR3: System availability of 99.9%

NFR4: Data retention for 7 days

NFR5: Minimal overhead on instrumented services (<5ms added latency per request)

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Instrumentation libraries for services

Trace context propagation mechanism

Trace collector or agent

Trace storage database

Indexing and query engine

Visualization UI/dashboard

Sampling and rate limiting module

Design Patterns

Context propagation pattern

Event logging and span creation

Sampling patterns (head-based, tail-based)

Data aggregation and indexing

Asynchronous data ingestion

Caching for query performance

Reference Architecture

Client --> Service A --> Service B --> Service C
  |          |           |           |
  |          |           |           +--> Trace Collector --> Trace Storage
  |          |           +--> Trace Collector
  |          +--> Trace Collector
  +--> Trace Collector

Trace Storage <--> Query Engine <--> Visualization UI

Components

Instrumentation Libraries

OpenTelemetry SDKs

Automatically capture trace spans and propagate trace context in each service

Trace Collector

gRPC/HTTP Collector Service

Receive trace data from services, batch and forward to storage

Trace Storage

Distributed NoSQL DB (e.g., Cassandra, Elasticsearch)

Store trace spans and indexes for efficient retrieval

Query Engine

Search and indexing system (e.g., Elasticsearch)

Support fast queries by trace ID, service, or time range

Visualization UI

Web Dashboard (React or similar)

Display trace timelines and service call graphs for developers

Sampling Module

In-process or Collector-based

Control volume of trace data collected to reduce overhead

Request Flow

1. 1. Client sends request to Service A with trace context headers.

2. 2. Service A instrumentation creates a span and propagates trace context to Service B.

3. 3. Service B creates its own span linked to the trace and calls Service C similarly.

4. 4. Each service sends collected spans asynchronously to the Trace Collector.

5. 5. Trace Collector batches spans and stores them in Trace Storage.

6. 6. Query Engine indexes trace data for fast retrieval.

7. 7. Developer queries traces via Visualization UI using trace ID or filters.

8. 8. UI displays the full trace timeline and service call graph.

Database Schema

Entities: - Trace: unique trace ID, start time, end time - Span: span ID, trace ID (foreign key), parent span ID, service name, operation name, start time, end time, tags/metadata Relationships: - One Trace has many Spans (1:N) - Spans linked by parent span ID forming a tree structure representing call hierarchy

Scaling Discussion

Bottlenecks

High volume of trace data causing storage and query slowdowns

Trace Collector becoming a bottleneck under heavy load

Network overhead from trace context propagation

Query latency increasing with data size

Sampling misconfiguration leading to too much or too little data

Solutions

Use scalable distributed storage like Cassandra or Elasticsearch clusters

Deploy multiple Trace Collector instances with load balancing

Optimize instrumentation to propagate minimal trace context data

Implement indexing strategies and caching in Query Engine

Apply adaptive sampling strategies to balance data volume and coverage

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing components and data flow, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Explain trace context propagation clearly with examples

Discuss trade-offs of sampling strategies

Justify technology choices for storage and query

Highlight how to minimize performance impact on services

Describe how visualization helps developers debug distributed systems

Practice

1. What is the main purpose of distributed tracing in a system?
TraceID and spans are used to:

easy

A. Balance load between servers automatically

B. Store user data securely in a database

C. Track requests as they move through multiple services

D. Encrypt communication between clients and servers

Solution

1. Step 1: Understand distributed tracing basics

   Distributed tracing helps track how a request flows through different parts of a system.

2. Step 2: Identify the role of TraceID and spans

   TraceID links all parts of a request, and spans represent each step or service involved.

3. Final Answer:

   Track requests as they move through multiple services -> Option C

4. Quick Check:

   Distributed tracing = Track requests [OK]

Hint: TraceID connects steps in request flow [OK]

Common Mistakes:

• Confusing tracing with data storage
• Mixing tracing with load balancing
• Thinking tracing encrypts data

2. Which of the following is the correct way to represent a span in distributed tracing data?

easy

A. "traceId:abc123;spanId:xyz789;operation:db_query"

B. { "traceId": "abc123", "spanId": "xyz789", "operation": "db_query" }

C. [ "traceId", "spanId", "operation" ]

D. abc123xyz789

Solution

1. Step 1: Identify correct data format for spans

   Spans are usually represented as structured data like JSON objects with keys and values.

2. Step 2: Compare options

   { "traceId": "abc123", "spanId": "xyz789", "operation": "db_query" } shows a JSON object with clear keys for traceId, spanId, and operation, which is standard.

3. Final Answer:

   { "traceId": "abc123", "spanId": "xyz789", "operation": "db_query" } -> Option B

4. Quick Check:

   Span = JSON object with keys [OK]

Hint: Spans use JSON key-value pairs [OK]

Common Mistakes:

• Using arrays instead of objects
• Using plain strings without structure
• Using XML tags incorrectly

3. Given the following trace data snippet:

{"traceId": "t1", "spans": [{"spanId": "s1", "parentId": null, "operation": "frontend"}, {"spanId": "s2", "parentId": "s1", "operation": "backend"}, {"spanId": "s3", "parentId": "s2", "operation": "db_query"}]}

What is the correct order of operations for this request?

medium

A. frontend -> backend -> db_query

B. db_query -> backend -> frontend

C. backend -> frontend -> db_query

D. frontend -> db_query -> backend

Solution

1. Step 1: Analyze parent-child relationships

   The span with parentId null is the root: frontend (s1). Backend (s2) is child of frontend, and db_query (s3) is child of backend.

2. Step 2: Determine operation order

   Request flows from frontend to backend to db_query following parent-child links.

3. Final Answer:

   frontend -> backend -> db_query -> Option A

4. Quick Check:

   Parent-child order = frontend to db_query [OK]

Hint: Follow parentId links from root span [OK]

Common Mistakes:

• Ignoring parentId null as root
• Reversing operation order
• Mixing span order in array with execution order

4. You notice that some spans in your distributed tracing system have missing traceId values. What is the most likely cause?

medium

A. The tracing library failed to propagate the traceId across services

B. The database storing traces is full

C. The network is too slow to send trace data

D. The user did not authenticate properly

Solution

1. Step 1: Understand traceId propagation

   TraceId must be passed along all services handling the request to link spans correctly.

2. Step 2: Identify cause of missing traceId

   If traceId is missing, it usually means the tracing library or instrumentation did not forward it properly.

3. Final Answer:

   The tracing library failed to propagate the traceId across services -> Option A

4. Quick Check:

   Missing traceId = propagation failure [OK]

Hint: Missing traceId means propagation error [OK]

Common Mistakes:

• Blaming storage or network issues
• Confusing authentication with tracing
• Assuming traceId is optional

5. You want to design a distributed tracing system for a microservices architecture with hundreds of services. Which approach best ensures scalability and minimal overhead?

hard

A. Store all trace data locally on each service without aggregation

B. Trace every request fully and store all spans in a single centralized database

C. Send trace data synchronously during each request to avoid data loss

D. Use sampling to trace only a subset of requests and store spans in a scalable backend

Solution

1. Step 1: Consider scalability challenges

   Tracing every request fully creates huge data and overhead, which is not scalable for hundreds of services.

2. Step 2: Evaluate best practices

   Sampling reduces data volume by tracing only some requests, and scalable backends handle storage efficiently.

3. Step 3: Assess other options

   Synchronous sending blocks requests, and local storage prevents global analysis.

4. Final Answer:

   Use sampling to trace only a subset of requests and store spans in a scalable backend -> Option D

5. Quick Check:

   Sampling + scalable storage = scalable tracing [OK]

Hint: Sample requests to reduce tracing load [OK]

Common Mistakes:

• Tracing all requests causing overload
• Synchronous sending blocking services
• Not aggregating trace data centrally