Design an Application Performance Monitoring System

You're asked to design an application performance monitoring system like Datadog APM, New Relic, or Honeycomb. A single user request touches a dozen microservices on its way through the system, and when it takes four seconds instead of two hundred milliseconds, an engineer needs to see exactly where that time went. The system should also aggregate across millions of such requests to answer "which service regressed after Tuesday's deploy?"

Logs tell you what one service did. Metrics tell you how a service behaved in aggregate. Neither can tell you that this specific slow request spent 3.4 seconds waiting on a database call three services deep, and reconstructing that path across process boundaries is what makes this problem distinct.

Clarifying the requirements

• What's the unit of analysis? A trace, meaning one request's full path across services. Establishing this early frames everything that follows.
• Do we trace every request? At scale this is the central cost question, and the answer is almost always no. Ask what fraction is acceptable.
• How deep does instrumentation go? Service-to-service calls at minimum, and usually database queries and external API calls too, since that's where the time usually is.
• What's the query pattern? Two very different ones: find one specific slow trace, and aggregate latency percentiles across many. They need different storage.
• How fresh? A minute or two is fine for investigation. Nobody debugs a production incident on second-old trace data.

Assume: full traces including database calls, sampled rather than complete, both single-trace and aggregate queries, and minute-level freshness.

Back-of-envelope numbers

• Requests: $100\text{k requests/sec}$ across the fleet
• Spans per request: $20 \text{ services and calls}$, so $100\text{k} \times 20 = 2\text{M spans/sec}$ if you traced everything
• Span size: $\approx 500\text{ B}$, so unsampled ingest is $2\text{M} \times 500\text{ B} = 1\text{ GB/sec} \approx 86\text{ TB/day}$
• At 1% sampling: $\approx 860\text{ GB/day}$, which is a workable number
• Aggregates are computed from every request regardless of sampling, and cost a few hundred gigabytes a month

Those two figures explain the entire design. Storing every span is roughly a hundred times too expensive, so the question becomes which one percent to keep, and how to still get accurate aggregate numbers from a sample.

High-level architecture

Deep dive 1: the trace and span model

The data model is small, and getting it right is most of the battle.

A span is one unit of work: a service handling a request, a database query, an outbound HTTP call. It carries a start time, a duration, a name, and a set of tags. A trace is the set of spans belonging to one original request, and the structure comes from three identifiers on every span:

• trace_id, identical across every span in the request, generated once at the entry point.
• span_id, unique to this span.
• parent_span_id, pointing at the span that caused this one.

Those three fields make a tree, and the tree is what the waterfall visualization renders. A span with no parent is the root, and each child's offset from the root's start time is where it appears on the timeline.

Two details worth raising unprompted. Spans are emitted independently and out of order, since a deeply nested database span often arrives before the parent service span that's still waiting on it, so the backend assembles the tree at query time from the IDs rather than expecting ordered arrival. And spans should be enriched with the tags you'll want to filter on later: service, version, host, endpoint, customer tier. Tags you didn't attach at emission time cannot be recovered afterward.

Deep dive 2: propagating context across process boundaries

The tree only exists if trace_id and parent_span_id survive every hop between services, and that propagation is the mechanism candidates most often skip.

Across HTTP, the identifiers travel as headers, and the W3C traceparent header is the standard, and naming it signals familiarity with real systems. Across a message queue, they travel in the message metadata, which matters because an asynchronous hop otherwise silently breaks the trace into two disconnected fragments.

Within a process, the current span has to be available to code that never received it as an argument, which is what thread-local storage or an async context variable provides. This is why tracing libraries are language-specific rather than a simple HTTP client wrapper.

Deep dive 3: sampling, and why head sampling isn't enough

Storing one percent of traces is affordable. The question is which one percent, and the naive answer throws away the traces you actually needed.

Head-based sampling decides at the entry point, before the request runs, typically by hashing the trace ID against a rate. The decision propagates with the context so every service agrees, which means you always get complete traces. It's cheap and simple, and its flaw is decisive: it can't know whether the request will be slow or fail, so a 1% rate keeps 1% of your errors and discards the rest.

Tail-based sampling decides after the request finishes, once you can see the outcome. That lets you keep every trace that errored, every trace above a latency threshold, and a small random sample of normal ones, which is precisely the set an engineer would ask for. The cost is real: the system has to buffer all spans for a trace until it completes, and because spans for one trace arrive at different collectors, they must first be routed to a common place. Consistent hashing on trace_id does that routing, and a time window bounds how long a trace is held before a decision is forced.

The answer that lands well combines them. Use head sampling to discard obviously uninteresting traffic cheaply, such as health checks and static assets, then tail sampling on what remains, so the stored set is biased toward the traces with something to say.

Deep dive 4: aggregate metrics from a sampled stream

If you store one percent of traces, you cannot compute p99 latency from stored traces. The percentile of a biased sample is not the percentile of the population, and a tail-sampled set is biased toward slow requests by construction.

The resolution is to separate the two paths. Every span contributes to aggregates, whether or not its trace is stored. The collector computes per-service, per-endpoint counts, error rates, and latency distributions from the full stream, and only the trace storage path is sampled. Aggregates are exact; traces are exemplars.

Latency distributions need a mergeable representation rather than a precomputed percentile, since percentiles from different hosts cannot be averaged. Sketches, meaning t-digest or HDR histograms, merge correctly across hosts and across time buckets, which is what makes a fleet-wide p99 meaningful.

One feature ties the two paths together: attach a few stored trace IDs as exemplars to each latency bucket, so an engineer looking at a p99 spike on a dashboard can click through to an actual slow trace that produced it. That link between aggregate and instance is what makes an APM tool useful rather than merely informative.

Common pitfalls

• No context propagation plan. Without it there are no traces, only disconnected spans.
• Breaking the trace at async boundaries. Queue hops need the context in message metadata, or the trace splits in two.
• Head sampling alone. A 1% rate keeps 1% of your errors, which are the traces you needed.
• Computing percentiles from sampled traces. The sample is biased by design, so the number is wrong.
• Averaging percentiles across hosts. Merge sketches instead; the mean of p99s is not a p99.

Leveling the answer

Related lessons