Tracemesh: Scalable and Streaming Sampling for Distributed Traces

Zhuangbin Chen, Zhihan Jiang, Yuxin Su, Michael R. Lyu, Zibin Zheng

Introduction

In modern microservice architectures, distributed tracing serves as the "GPS" for developers, mapping a request's journey across thousands of services. However, this visibility comes at a massive cost; for instance, large-scale systems can generate upwards of 1,000 TB of raw traces daily.

To manage this volume, most systems employ head-based sampling, randomly selecting a small fraction (e.g., 0.1%) of traces at the start of a request. Unfortunately, this often misses "interesting" events—rare errors, tail-latency spikes, or novel service behaviors—which are statistically overwhelmed by "normal" traffic. While tail-based sampling waits for a trace to complete before deciding whether to retain it, existing methods face two major hurdles:

  1. The Curse of Dimensionality: Traces involve thousands of unique call paths, making real-time analysis computationally expensive.
  2. Dynamic Environments: Microservices evolve constantly. New service versions introduce new data dimensions, often requiring traditional models to be retrained or restructured.

Methods: The TraceMesh Pipeline

TraceMesh addresses these challenges with a three-phase pipeline optimized for high-velocity data streams.

The three-phase pipeline of TraceMesh: Encoding, Sketching, and Sampling.

1. Trace Vector Encoding

The system first converts a trace graph into a numerical vector using Breadth-First Search (BFS). This encoding captures both structural information (the call path) and temporal data (log-normalized duration of each span), ensuring that even structurally normal traces with unusual latencies can be identified.

2. Trace Sketching via Streaming LSH

The core innovation of TraceMesh is its use of StreamHash for dimensionality reduction. Instead of maintaining a massive, ever-growing feature vector, TraceMesh projects high-dimensional data into a low-dimensional "sketch"—a fixed-length bit-vector ($L$).

Detailed mechanism of Trace Sketching using Streaming Locality-Sensitive Hashing (LSH).

By utilizing a universal hashing family, TraceMesh can incorporate previously unseen call paths on-the-fly. This allows the model to handle new services or versions without changing its underlying structure or dimensionality.

3. Evolving Clustering

These sketches are processed by a density-based clustering algorithm (DenStream). The algorithm maintains Potential Micro Clusters (PMCs) for common traces and Outlier Micro Clusters (OMCs) for rare ones. A "fading function" with a decay factor ($\lambda$) allows the model to "forget" old patterns, adapting to "concept drift" as the system evolves. Sampling is biased toward OMCs, ensuring rare anomalies are always preserved while common traces are sampled at a much lower rate.

Evaluation and Results

The authors evaluated TraceMesh against three datasets: the open-source Train Ticket and Online Boutique benchmarks, and a massive Industry Dataset from a major cloud provider containing nearly 500,000 traces.

TraceMesh significantly outperformed state-of-the-art baselines like Sieve, Sifter, and Perch:

  • Superior Coverage: On the Industry dataset, TraceMesh achieved 93.6% coverage of labeled anomalies, compared to 61.1% for the next-best competitor. On benchmarks, it reached near-perfect 98-100% coverage.
  • High Efficiency: TraceMesh processed the Industry dataset in approximately 1,306 seconds—3x faster than Sieve and 5x faster than Perch.
  • Low Sampling Rate: It maintained high accuracy with a very low overall sampling rate (e.g., 0.83% on the Industry dataset), effectively finding "needles" in the haystack without excessive storage costs.

Key Insights

  • Adaptability through LSH: By hashing call paths directly into fixed-size sketches, the model avoids the need for retraining when new features appear.
  • Temporal Importance: Including span duration significantly improves the detection of unusual traces that might appear structurally normal.
  • Handling Concept Drift: The decay mechanism ensures that if a rare error becomes the new "normal," the sampler eventually stops over-sampling it, prioritizing truly novel anomalies.

Limitations and Future Work

While highly scalable, TraceMesh requires initial tuning for parameters like the cluster threshold ($\epsilon$) and sketch length ($L$). Additionally, it currently assumes a maximum call path length for hash initialization. Future work may involve integrating richer semantic data, such as HTTP status codes or specific log events, to further refine sampling accuracy.

Summary updated

BibTeX
@inproceedings{chen2024tracemesh,
  author = {Zhuangbin Chen and Zhihan Jiang and Yuxin Su and Michael R. Lyu and Zibin Zheng},
  title = {{Tracemesh: Scalable and Streaming Sampling for Distributed Traces}},
  booktitle = {CLOUD},
  year = {2024},
  doi = {10.1109/cloud62652.2024.00016},
}
Figure