Mint: Cost-Efficient Tracing with All Requests Collection via Commonality and Variability Analysis

Haiyu Huang, Cheng Chen, Kunyi Chen, Pengfei Chen, Guangba Yu, Zilong He and 3 others

Big online systems record a trace of every request as it hops between services, which is invaluable for debugging but so voluminous — one Alibaba system makes about 20 pebibytes a day — that engineers keep only a sampled fraction and throw the rest away, then find that over a quarter of the traces they later need were among the discarded; this work from Sun Yat-sen University and Alibaba builds Mint, which keeps a cheap record of every single request by splitting each trace into a shared pattern and its varying parameters, storing patterns once and using a compact filter to remember all traces, cutting storage to under 3 percent while never dropping a request.

The argument in one glance

Problem

Tracing every request is invaluable but overwhelmingly voluminous

A distributed trace records the end-to-end path a request takes through a system's many services, and it is essential for debugging. But at scale the volume is staggering — one Alibaba system produces about 20 pebibytes of trace data per day — so collecting, storing, and processing it all is very expensive.
What people did

Sample: keep some traces, discard the rest

The standard fix is sampling. A system decides which traces to keep, stores those fully, and completely discards the unsampled ones — a keep-it-or-drop-it strategy, applied at various points and by various rules.
Why it fell short

Dropping loses what you did not predict, and shrinks nothing per trace

A study of real production traces shows two failures. First, engineers cannot predict which traces they will later need, so the discarded ones are often the ones queried during an incident — over a quarter of trace queries fail to find their trace. Second, sampling reduces the number of traces but never the size of each one, and generic compressors do poorly because a trace is a tree of service calls, not flat text.
This paper's idea

Keep a cheap record of every request via commonality and variability

Mint replaces keep-it-or-drop-it with a commonality-plus-variability approach. It splits each trace into a common pattern (its shared structure) and variable parameters (the differing values). Because millions of traces share few patterns, it stores each pattern once and uses a compact filter to remember every trace cheaply. Full parameter detail is kept only for sampled traces. Every request stays queryable, while storage drops to about 2.7 percent and network to about 4.2 percent.

Why this problem is worth solving

Tracing is how engineers see inside a sprawling system, but seeing everything is costly.

Modern applications are built from many small services that call one another over the network. When a user request arrives, it flows through a chain of these services, and to understand what happened — where time went, where an error arose — engineers use distributed tracing. As the request passes through each service, that service records a span: a small record of the work it did, with a start and end time and details like which database query ran. The spans belonging to one request are linked by a shared identifier into a trace, which forms a tree showing the request’s whole path through the system. Tracing frameworks like Jaeger, OpenTelemetry, and Zipkin collect these traces, and site reliability engineers query them to profile performance, detect anomalies, and diagnose failures. The trouble is volume. A large system serves enormous numbers of requests, and a trace is recorded for each, so the data piles up fast. The paper reports that one large-scale Alibaba e-commerce system generates roughly 18.6 to 20.5 pebibytes of trace data per day, at a storage cost of over a hundred thousand dollars a month for a single system spanning more than a million nodes. Collecting, transmitting, and storing all of it is a first-order expense, so the central design question for a tracing framework is how to keep the valuable information in traces while drastically cutting their volume.

The usual answer throws data away, and that turns out to backfire.

The dominant way to reduce trace volume is sampling: decide which traces to retain, keep those completely, and discard the rest entirely. The paper calls this the keep-it-or-drop-it strategy, and its variants differ only in when and how the keep-or-drop decision is made. An empirical study on real production traces reveals two serious flaws. The first is that discarding is dangerous because engineers cannot predict which traces they will need. Sampling rules try to keep the interesting traces, but the trace an engineer must inspect during an incident is often an ordinary-looking one that no rule flagged, and if it was discarded, the query simply fails. The study measures a query miss rate of about 27 percent — more than a quarter of the traces engineers went looking for had been thrown away, directly impeding diagnosis. The second flaw is that sampling only reduces the number of traces, never the size of each individual trace. Each trace can carry more detail than a debug log, so shrinking each one matters too, but general-purpose compressors and even log-specific compressors do poorly on traces, because a trace is not flat text — it is a tree of service calls with structured fields. Those tools cannot exploit the trace’s shape, so they compress it badly. Together, these flaws mean keep-it-or-drop-it fails to balance keeping information against cutting cost.

What people did before, and where it broke

Head sampling. Decide at the start of a request whether to keep its trace. Where it broke. The decision is made before anything interesting has happened, so it cannot target the traces that turn out to matter, and discarded traces are unrecoverable.
Tail and retroactive sampling. Wait until a request finishes (or later) to decide, using what happened to pick interesting traces. Where it broke. They still ultimately discard the unsampled traces, so a trace no rule flagged but an engineer later needs is gone, leaving the roughly 27 percent query miss rate.
Generic or log compression on the kept traces. Apply standard compressors to shrink the traces that are retained. Where it broke. Traces are tree-structured with typed fields, not flat text, so tools built for byte streams or logs cannot exploit their shape and compress them poorly.
The gap. No approach kept a useful record of every request while still slashing volume, both by reducing count and by shrinking each trace using its structure. Doing that, by separating each trace’s shared pattern from its varying parameters, is what Mint provides.

How Mint works

From discard-the-rest sampling to keep-everything-cheaply

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Store the shared pattern once for the millions of traces that share it. The engine of Mint is a fact about real traces: they are enormously repetitive, because most requests run the same code paths, so millions of traces collapse into a small number of distinct structural patterns and even the field values follow fixed templates. Mint separates each span into its pattern — the shape it always has, like the SQL template that only differs in a few values — and its parameters, the values that vary. The pattern is stored once and referenced by an identifier, so the shared structure of a vast number of traces costs almost nothing to keep. Recognizing that a structure repeats across a huge population and keeping a single copy that everything points to is the same deduplication the repeated-circuit-module work covered elsewhere on this site relies on, storing one copy of an identical block and referencing it wherever it recurs rather than paying for each occurrence.

Keep a cheap trace of everything instead of discarding to save space. The deep flaw of sampling is that it throws data away, and you cannot know in advance which trace you will need. Mint refuses to fully discard any request: for unsampled traces it still keeps the commonality — the pattern and a compact record that this trace existed — which is enough to answer many queries, and it keeps full detail only for the sampled ones. So every request stays on record, and the roughly one-in-four query failures disappear. Making an observability tool cheap enough that it can afford to capture every request rather than sample and hope is the same ambition the datacenter-tracing work covered elsewhere on this site pursues, driving the cost of recording so low that turning it off, or dropping most of the data, is no longer necessary.

Remember which traces exist with a tiny probabilistic filter. To keep every trace queryable without storing every trace, Mint needs a way to record, for each pattern, the set of trace identifiers that matched it, using almost no space. It uses a Bloom filter, a compact structure that answers whether an item is in a set using a fixed, small amount of memory, at the price of a small, one-sided error. That cheap, slightly-approximate membership record is what lets all requests be captured at negligible cost. Accepting a small, one-sided approximation in a compact structure in exchange for a large saving, while never being wrong in the dangerous direction, is the same trade the copy-on-write correctness work covered elsewhere on this site makes, using a conservative flag that may occasionally say too much but is always safe to act on.

Following a request through Mint

Recording one trace by pattern and parameters

Tracing one span and query shows how everything is kept cheaply.

Step 1 of 5

Split a span into pattern and parameters

A service emits a span for a database write whose text is like "INSERT INTO orders (city_id, ...) VALUES (...)". Mint's parser splits it into the pattern — the template "INSERT INTO orders (...) VALUES (...)" — and the parameters, the specific values that vary.

Spans from the same code always share the same template and differ only in values.

Why it works

Traces are enormous but repetitive. Because most requests run the same code paths → millions of traces collapse into a small number of distinct patterns → so storing each pattern once and referencing it captures the structure of all traces cheaply.
Dropping traces loses what you did not predict. Because which traces an engineer will need is unpredictable, and sampling discards the rest → over a quarter of trace queries fail to find their trace → so keeping at least the cheap commonality of every trace removes those failures.
Splitting pattern from parameter enables real compression. Because a trace is a tree with a fixed shape and a few varying values → separating the shared template from the differing parameters shrinks each trace far more than a generic compressor → so per-trace volume drops, not just the trace count.
A Bloom filter records all of them for almost nothing. Because a Bloom filter answers whether a trace exists in a tiny fixed space → the membership of every trace can be kept without storing the traces themselves → so all requests stay queryable at negligible cost.
Detail is spent only where it is asked for. Because full parameters are sent only for sampled traces while the rest keep just commonality → the expensive part of the data is paid for selectively → so storage falls to about 2.7 percent and network to about 4.2 percent while nothing is fully lost.

What it costs (trade-offs and scope)

Unsampled traces keep structure, not full detail. Every request stays recorded and queryable by its pattern and basic information, but the specific parameter values of an unsampled trace are not retained, so a query needing those exact values still depends on the trace having been sampled.
The Bloom filter has a small false-positive rate. A Bloom filter can occasionally report a trace as present when it is not. The error is one-sided and tunable, but it means membership answers are highly reliable rather than perfect.
It leans on traces being repetitive. Mint’s savings come from strong commonality across traces. A system whose requests are highly diverse, with few shared patterns, would offer less to deduplicate and see smaller gains.
Parsing runs on the agent and costs something. Splitting spans into patterns and parameters and maintaining the pattern library and filters consume some agent resources; the paper reports Mint is lightweight enough for production, but it is not free.
It needs a warm-up and pattern management. The span parser is warmed up offline and the pattern library grows as new patterns appear, which is machinery to build and maintain, and unusual new patterns are handled less efficiently until learned.
Reconstruction has limits. Mint can reconstruct trace information from patterns and parameters, but what can be recovered for an unsampled trace is bounded by the commonality that was kept, so it is not a full substitute for having stored the complete trace.

The evaluation

Three ways to control distributed-trace volume

Property	Sampling (keep or drop)	Generic compression
Captures every request		Yes
Trace query miss rate		Low
Shrinks each individual trace
Where reduction happens	At collection	After collection
Storage overhead	Fraction kept

Three ways to reduce the volume of distributed traces, evaluated on real-world production traces. Keep-it-or-drop-it sampling discards unsampled traces, so about 27 percent of later queries miss their trace, and it never shrinks each individual trace. Generic and log compressors keep every trace but compress poorly, because a trace is a tree of service calls with typed fields, not flat text. Mint splits each trace into a common pattern and variable parameters: it stores each pattern once, records the existence of every trace with a compact Bloom filter, and keeps full parameter detail only for sampled traces, doing all this on the agent so both network and storage shrink. Mint captures all requests while cutting total trace storage overhead to about 2.7 percent and network overhead to about 4.2 percent, and it has run in Alibaba production for over two months.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Mint is a practical, well-motivated systems contribution: it takes a real and expensive problem — one Alibaba system produces about 20 pebibytes of traces a day — and rethinks the standard response, which was to sample and discard. Its empirical finding that keep-it-or-drop-it sampling causes about a quarter of trace queries to miss is a strong argument, because it shows the usual approach fails exactly when an engineer needs a specific trace during an incident. The commonality-plus-variability idea is elegant and fits the data: traces are highly repetitive, so separating each one into a shared pattern and its varying parameters lets Mint store the structure of everything once, remember every trace with a compact filter, and keep full detail only where it is sampled. The reported results are excellent and, importantly, come from a real production deployment: storage cut to about 2.7 percent and network to about 4.2 percent, while capturing all requests, running for over two months at Alibaba. Read it with its scope. Unsampled traces retain their pattern and basic information but not their exact parameter values, so a query needing those specific values still relies on sampling. The Bloom filter trades a small, one-sided error for its tiny size, the savings depend on traces being repetitive, and the agent-side parsing and pattern management cost some resources. The durable lesson is that when data is voluminous but highly structured and repetitive, you do not have to choose between keeping it and affording it — separating the common structure from the variable detail can let you keep a useful record of everything cheaply.

Background

Why structure-aware reduction beats blind discarding

It helps to see Mint as part of a broader idea: the way to make a huge dataset affordable is often to exploit its structure rather than to throw parts of it away. Blind sampling treats every trace as an opaque blob and gambles on which ones matter; Mint instead reads the shape of the data and keeps what is cheap for all of it. The analytics-storage work covered elsewhere on this site makes a kindred move for query performance, arranging storage around the internal structure of the data files so the system does not waste work fighting a layout blind to what the data actually is. In both cases the win comes from refusing to treat structured data as a featureless stream: a trace is a tree with repeating templates, a data file has computable units, and honoring that structure unlocks efficiency that generic, structure-blind methods cannot reach. The general point is that as systems generate ever more data, the instinct to cope by sampling and discarding is often a false economy, because the discarded part is unpredictable in value. When the data is repetitive and structured, as observability data usually is, the better path is to compress by understanding it — keeping the common skeleton of everything and spending storage only on the details that truly vary.

If you remember only three things

1. Distributed tracing records the end-to-end path of every request through a system's services, which is essential for debugging, but the volume is enormous — one Alibaba system makes about 20 pebibytes of traces per day. The standard fix is sampling: keep some traces, discard the rest. An empirical study shows this fails two ways: engineers cannot predict which traces they will need, so about 27 percent of trace queries miss their (discarded) trace, and sampling never shrinks each individual trace, while generic compressors do poorly because a trace is a tree of service calls, not flat text.
2. Mint replaces keep-it-or-drop-it with a commonality-plus-variability approach. On the agent where traces are generated, it splits each span into a common pattern (its structural template) and variable parameters (the differing values). Because millions of traces share few patterns, it stores each pattern once by identifier and records which traces matched using a compact Bloom filter, so every trace's existence and structure is kept cheaply. Full parameter detail is sent to the backend only for sampled traces (and compressed); unsampled traces keep just the cheap commonality, so nothing is fully discarded and every request stays queryable.
3. On real production traces, Mint captures all requests while cutting total trace storage overhead to about 2.7 percent and network overhead to about 4.2 percent, and it has run in Alibaba production for over two months. Its limits: unsampled traces keep structure and basic information but not exact parameter values, the Bloom filter has a small one-sided false-positive rate, the savings depend on traces being repetitive, and agent-side parsing and pattern management cost some resources. The durable lesson is that highly structured, repetitive data can be kept in full-coverage cheaply by separating its common skeleton from its variable detail, instead of discarding.

Check yourself

Check your understanding

1. Why does the usual "keep-it-or-drop-it" trace sampling fail, according to the paper's study?
2. What is the "commonality plus variability" idea at the heart of Mint?
3. How does Mint keep every request queryable without storing every full trace?
4. A team runs a system whose requests are extremely diverse, with almost no repeated structure across traces. What does Mint's design imply?

Sources

The paper is “Mint: Cost-Efficient Tracing with All Requests Collection via Commonality and Variability Analysis” by Haiyu Huang, Cheng Chen, Kunyi Chen, Pengfei Chen, Guangba Yu, Zilong He, Yilun Wang, Huxing Zhang, and Qi Zhou, published at ASPLOS 2025, DOI 10.1145/3669940.3707287. The authors are at Sun Yat-sen University and the Alibaba Group; Pengfei Chen is the corresponding author.

This explainer is written from the full text of the paper, obtained from the authors’ arXiv preprint (2411.04605), which matches the ASPLOS 2025 proceedings. Everything above comes from the paper’s own sections: the introduction and motivation on distributed tracing and its cost (the figure of 18.6 to 20.5 pebibytes of trace data per day in an Alibaba system and its monthly storage expense) and the two shortcomings of the keep-it-or-drop-it sampling paradigm found by the empirical study (the roughly 27 percent query miss rate from discarding unpredictably-needed traces, and the failure of generic and log compressors on tree-structured traces); the commonality-plus-variability paradigm that parses traces into common patterns and variable parameters; the design of Mint (inter-span-level parsing into a pattern and parameters with a Pattern Library and pattern identifiers, inter-trace-level topology matching into sub-tree patterns, mounting trace metadata onto patterns with a Bloom filter, keeping only commonality for unsampled traces and full compressed detail for sampled ones, all performed on the agent side to save both network and storage); and the evaluation reporting total trace storage overhead reduced to about 2.7 percent and network overhead to about 4.2 percent while capturing all requests, along with a production deployment in Alibaba for over two months.