Sifter: Scalable Sampling for Distributed Traces, without Feature Engineering
Open accessThe DOI matches its Crossref record; 32 of the 35 references it cites were found in a registry or an index.
Abstract
Distributed tracing is a core component of cloud and datacenter systems, and provides visibility into their end-to-end runtime behavior. To reduce computational and storage overheads, most tracing frameworks do not keep all traces, but sample them uniformly at random. While effective at reducing overheads, uniform random sampling inevitably captures redundant, common-case execution traces, which are less useful for analysis and troubleshooting tasks. In this work we present Sifter, a general-purpose framework for biased trace sampling. Sifter captures qualitatively more diverse traces, by weighting sampling decisions towards edge-case code paths, infrequent request types, and anomalous events. Sifter does so by using the incoming stream of traces to build an unbiased low-dimensional model that approximates the system's common-case behavior. Sifter then biases sampling decisions towards traces that are poorly captured by this model. We have implemented Sifter, integrated it with several open-source tracing systems, and evaluate with traces from a range of open-source and production distributed systems. Our evaluation shows that Sifter effectively biases towards anomalous and outlier executions, is robust to noisy and heterogeneous traces, is efficient and scalable, and adapts to changes in workloads over time.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Figures















Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“high storage and runtime costs demand sampling strategies, where random head-based or selective tail-based sampling reduce overheads while preserving representative traces [75]”
From Anomaly detection and root-cause identification in microservices: a survey (2026) · cites this paper as [75]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Time, clocks, and the ordering of events in a distributed system
Lamport, L. (1978) · Communications of the ACM · doi:10.1145/359545.359563 · Cited by 8,488 · cited 1×
“Relationships Events alone tell some of the story, but the most important information in a trace is the causal ordering between events, defined by Lamport’s happened-before relation [16].”
BackgroundDistributed Representations of Sentences and Documents
Le, Q. V., & Mikolov, T. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1405.4053 · Cited by 4,934 · cited 6×
“We implement the model using the same architecture as the distributed memory paragraph vector model, using concatenation [18].”
BackgroundMethodInfluentialResilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing
Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J. H., McCauley, M., Franklin, M. J. M., Shenker, S. J., & Stoica, I. G. (2012) · UC Berkeley · Cited by 4,891
The Hadoop Distributed File System
Shvachko, K., Kuang, H., Radia, S., & Chansler, R. (2010) · 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST) · doi:10.1109/msst.2010.5496972 · Cited by 4,834
A Neural Probabilistic Language Model
Bengio, Y., Ducharme, R., Vincent, P., Jauvin, C., Jaz, K., Hofmann, T., Poggio, T., & Shawe-Taylor, J. S. (2000) · Cited by 3,479
Apache Hadoop YARN: yet another resource negotiator
Vavilapalli, V. K., Murthy, A. C., Douglas, C., Agarwal, S., Konar, M., Evans, R., Graves, T., Lowe, J., Shah, H., Seth, S., et al. (2013) · Proceedings of the 4th annual Symposium on Cloud Computing · doi:10.1145/2523616.2523633 · Cited by 1,848
Detecting large-scale system problems by mining console logs
Xu, W., Huang, L., Fox, A., Patterson, D., & Jordan, M. I. (2009) · Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles · doi:10.1145/1629575.1629587 · Cited by 1,332
Vishwanathan, S. V. N., Schraudolph, N. N., Kondor, R., & Borgwardt, K. M. (2010) · CaltechAUTHORS (California Institute of Technology) · Cited by 1,305
Dapper, a Large-Scale Distributed Systems Tracing Infrastructure
Sigelman, B. H., Barroso, L. A., Burrows, M., Stephenson, P., Plakal, M., Beaver, D., Jaspan, S., & Shanbhag, C. (2010) · Cited by 899
Gan, Y., Zhang, Y., Cheng, D., Shetty, A., Rathi, P., Katarki, N., Bruno, A., Hu, J., Ritchken, B., Jackson, B., et al. (2019) · Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3297858.3304013 · Cited by 665
Using magpie for request extraction and workload modelling
Barham, P., Donnelly, A., Isaacs, R., & Mortier, R. (2004) · Operating Systems Design and Implementation · Cited by 559
On a relation between graph edit distance and maximum common subgraph
Bunke, H. (1997) · Pattern Recognition Letters · doi:10.1016/s0167-8655(97)00060-3 · Cited by 530 · cited 1×
“Alternatives Sifter could have considered include frequent sub-graph mining [12]; maximal common subgraphs [4], and graph kernels [36].”
BackgroundNeural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection
Xu, X., Liu, C., Feng, Q., Yin, H., Song, L., & Song, D. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134018 · Cited by 530
X-trace: a pervasive network tracing framework
Fonseca, R., Porter, G., Katz, R. H., Shenker, S. J., & Stoica, I. G. (2007) · Cited by 438
A survey of frequent subgraph mining algorithms
Jiang, C., Coenen, F., & Zito, M. (2013) · The Knowledge Engineering Review · doi:10.1017/s0269888912000331 · Cited by 346
Mining invariants from console logs for system problem detection
Lou, J., Fu, Q., Yang, S., Xu, Y., & Li, J. (2010) · Cited by 302
Path-based faliure and evolution management
Chen, M. Y., Accardi, A., Kıcıman, E., Lloyd, J., Patterson, D., Fox, A., & Brewer, E. (2004) · Networked Systems Design and Implementation · Cited by 302
30th Conference on Neural Information Processing Systems (NIPS 2016)
Papamakarios, G., & Murray, I. (2016) · neural information processing systems · Cited by 296
Seer: Leveraging Big Data to Navigate the Complexity of Performance Debugging in Cloud Microservices
Gan, Y., Zhang, Y., Hu, K., Cheng, D., He, Y., Pancholi, M., & Delimitrou, C. (2019) · Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3297858.3304004 · Cited by 269
(2015) · doi:10.1145/2815400.2815415 · Cited by 202
Self-citationThe mystery machine: end-to-end performance analysis of large-scale internet services
Chow, M., Meisner, D., Flinn, J., Peek, D., & Wenisch, T. F. (2014) · Operating Systems Design and Implementation · doi:10.5555/2685048.2685066 · Cited by 166
Diagnosing performance changes by comparing request flows
Sambasivan, R. R., Zheng, A. X., Rosa, M. D., Krevat, E., Whitman, S., Stroucken, M., Wang, W. Y., Xu, L., & Ganger, G. R. (2011) · doi:10.5555/1972457.1972463 · Cited by 165
(2017) · doi:10.1145/3132747.3132749 · Cited by 144
Self-citationStardust: tracking activity in a distributed storage system
Thereska, E., Salmon, B., Strunk, J., Wachs, M., Abd-El-Malek, M., Lopez, J., & Ganger, G. R. (2006) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/1140103.1140280 · Cited by 129
Resilient Distributed Datasets
(2016) · doi:10.1145/2886107.2886110 · Cited by 122
lprof: a non-intrusive request flow profiler for distributed systems
Zhao, X., Zhang, Y., Lion, D., Ullah, M. F., Luo, Y., Yuan, D., & Stumm, M. (2014) · TSpace (University of Toronto) · doi:10.5555/2685048.2685099 · Cited by 101
Zhao, X., Rodrigues, K., Luo, Y., Stumm, M., Yuan, D., & Zhou, Y. (2017) · Proceedings of the 26th Symposium on Operating Systems Principles · doi:10.1145/3132747.3132778 · Cited by 101
Zhao, X., Rodrigues, K., Luo, Y., Yuan, D., & Stumm, M. (2016) · Operating Systems Design and Implementation · doi:10.5555/3026877.3026924 · Cited by 71
Whodunit: transactional profiling for multi-tier applications
Chanda, A., Cox, A. L., & Zwaenepoel, W. (2007) · Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007 · doi:10.1145/1272996.1273001 · Cited by 71
Zeno: Diagnosing Performance Problems with Temporal Provenance.
Wu, Y., Chen, A., & Phan, L. T. X. (2019) · Networked Systems Design and Implementation · Cited by 51
Universal context propagation for distributed system instrumentation
Mace, J., & Fonseca, R. (2018) · Proceedings of the Thirteenth EuroSys Conference · doi:10.1145/3190508.3190526 · Cited by 45 · cited 1×
“…be to sanitize traces ( i.e. , to identify and remove noise), but this is not a realistic solution as it either requires manual effort in postprocessing (aka feature engineering), or imposes unrealistic constraints on the developers doing instrumentation (constraints that are easily violated [22]).”
BackgroundSelf-citationWeighted Sampling of Execution Traces: Capturing More Needles and Less Hay
Las-Casas, P., Mace, J., Guedes, D., & Fonseca, R. (2018) · Proceedings of the ACM Symposium on Cloud Computing · doi:10.1145/3267809.3267841 · Cited by 36
Self-citation
Research works printed but not linked: 8
- M. P. Kasick, J. Tan, R. Gandhi, and P. Narasimhan. Black-Box Problem Diagnosis in Parallel File Systems. In 8th USENIX Conference on File and Storage Technologies (FAST '10). ( §9).
- J. Leavitt. End-to-End Tracing Models: Analysis and Unification. B.Sc. Thesis, Brown University, 2014. ( §4.1).
- J. Mace. Revisiting End-to-End Trace Comparison with Graph Kernels. M.Sc. Project, Brown University, 2013. ( §3.2, 4.3, and 9).
- G. Mann, M. Sandler, D. Krushevskaja, S. Guha, and E. Even-Dar. Modeling the Parallel Execution of Black-Box Services. In 3rd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud '11). ( §4.3, 4.4, and 9).
- T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed Repre- sentations of Words and Phrases and their Compositionality. In 27th Conference on Neural Information Processing Systems (NIPS '13). ( §5.1 and 9).
- K. Nagaraj, C. Killian, and J. Neville. Structured Comparative Analysis of System Logs to Diagnose Performance Problems. In 9th USENIX Conference on Networked Systems Design and Implementation (NSDI '12). ( §4.2 and 9).
- K. Ostrowski, G. Mann, and M. Sandler. Diagnosing Latency in Multi-Tier Black- Box Services. In 5th Workshop on Large Scale Distributed Systems and Middleware (LADIS '11). ( §9).
- H. Tian, M. Yu, and W. Wang. Continuum: A Platform for Cost-Aware, Low- Latency Continual Learning. In 10th ACM Symposium on Cloud Computing (SOCC '18). ( §9).
Cited by
Network-Centric Distributed Tracing with DeepFlow: Troubleshooting Your Microservices in Zero Code
Shen, J., Zhang, H., Xiang, Y., Shi, X., Li, X., Shen, Y., Zhang, Z., Wu, Y., Yin, X., Wang, J., et al. (2023) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/3603269.3604823 · Cited by 88
Automated Analysis of Distributed Tracing: Challenges and Research Directions
Bento, A., Correia, J., Filipe, R., Araujo, F., & Cardoso, J. (2021) · Journal of Grid Computing · doi:10.1007/s10723-021-09551-5 · Cited by 45
“approach in our suggestions to improve the usefulness of tracing for automated analysis—[25] propose Sifter, a trace sampler built to bias the sampling decision towards edge cases and rare work-flows.”
MethodHuang, L., & Zhu, T. (2021) · Proceedings of the ACM Symposium on Cloud Computing · doi:10.1145/3472883.3486994 · Cited by 37
TraceCRL: contrastive representation learning for microservice trace analysis
Zhang, C., Peng, X., Zhou, T., Sha, C., Yan, Z., Chen, Y., & Yang, H. (2022) · Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering · doi:10.1145/3540250.3549146 · Cited by 36
“The same authors [11] propose a neural network-based trace sampling approach which constructs trace vectors based on fixed-length operation sequences.”
BackgroundCloud Data Services: Workloads, Architectures and Multi-Tenancy
Narasayya, V. R., & Chaudhuri, S. (2021) · Foundations and Trends in Databases · doi:10.1561/9781680837759 · Cited by 38
Metadata
- Authors
- Las-Casas, P., Papakerashvili, G., Anand, V., & Mace, J.
- Affiliations
- Max Planck Institute for Software Systems (DE)
- Venue
- Proceedings of the ACM Symposium on Cloud Computing
- Publisher
- ACM
- Published
- 2019-11-20
- Pages
- 312-324
- OpenAlex
- W2988883278
- Cited by
- 42
- References
- 35
- Citations by year
- 2026: 3 · 2025: 12 · 2024: 4 · 2023: 10 · 2022: 5 · 2021: 7 · 2020: 1
- FWCI
- 2.81
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- ACM Symposium on Cloud Computing (SoCC) (publishedVersion, cc-by)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Software System Performance and Reliability
- Physical Sciences › Computer Science › Information Systems › Cloud Computing and Resource Management
- Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries
- Keywords
- distributed tracing, uniform random sampling, anomaly detection, low-dimensional models, SIFTER
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.