{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T03:20:14Z","timestamp":1784431214917,"version":"3.55.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"ISSTA","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Softw. Eng."],"published-print":{"date-parts":[[2025,6,22]]},"abstract":"<jats:p>Distributed tracing serves as a fundamental building block in the monitoring and testing of cloud service systems. To reduce computational and storage overheads, the de facto practice is to capture fewer traces via sampling. However, existing work faces a trade-off between the completeness of tracing and system overhead. On one hand, head-based sampling indiscriminately selects requests to trace when they enter the system, which may miss critical events. On the other hand, tail-based sampling first captures all requests and then selectively persists the edge-case traces, which entails the overheads related to trace collection and ingestion. Taking a different path, we propose Tracezip in this paper to enhance the efficiency of distributed tracing via trace compression. Our key insight is that there exists significant redundancy among traces, which results in repetitive transmission of identical data between services and the backend. We design a new data structure named Span Retrieval Tree (SRT) that continuously encapsulates such redundancy at the service side and transforms trace spans into a lightweight form. At the backend, the complete traces can be seamlessly reconstructed by retrieving the common data that are already delivered by previous spans. Tracezip includes a series of strategies to optimize the structure of SRT and a differential update mechanism to efficiently synchronize SRT between services and the backend. Our evaluation on microservices benchmarks, popular cloud service systems, and production trace data demonstrates that Tracezip can achieve substantial performance gains in trace collection with negligible overhead. We have implemented Tracezip inside the OpenTelemetry Collector, making it compatible with existing tracing APIs.<\/jats:p>","DOI":"10.1145\/3728888","type":"journal-article","created":{"date-parts":[[2025,6,22]],"date-time":"2025-06-22T10:52:56Z","timestamp":1750589576000},"page":"411-433","source":"Crossref","is-referenced-by-count":3,"title":["Tracezip: Efficient Distributed Tracing via Trace Compression"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5158-6716","authenticated-orcid":false,"given":"Zhuangbin","family":"Chen","sequence":"first","affiliation":[{"name":"Sun Yat-sen University, Zhuhai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8309-1384","authenticated-orcid":false,"given":"Junsong","family":"Pu","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7878-4330","authenticated-orcid":false,"given":"Zibin","family":"Zheng","sequence":"additional","affiliation":[{"name":"Sun Yat-sen University, Zhuhai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,22]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of HotOS\u201903: 9th Workshop on Hot Topics in Operating Systems","author":"Barham Paul","year":"2003","unstructured":"Paul Barham, Rebecca Isaacs, Richard Mortier, and Dushyanth Narayanan. 2003. Magpie: Online Modelling and Performance-aware Systems. In Proceedings of HotOS\u201903: 9th Workshop on Hot Topics in Operating Systems, May 18-21, 2003, Lihue (Kauai), Hawaii, USA, Michael B. Jones (Ed.). USENIX, 85\u201390. https:\/\/www.usenix.org\/conference\/hotos-ix\/magpie-online-modelling-and-performance-aware-systems"},{"key":"e_1_2_1_2_1","unstructured":"Protocol Buffers. 2024. Protocol Buffers: language-neutral platform-neutral extensible mechanisms for serializing structured data. https:\/\/protobuf.dev\/"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLOUD62652.2024.00016"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3417055"},{"key":"e_1_2_1_6_1","volume-title":"Lyu","author":"Chen Zhuangbin","year":"2021","unstructured":"Zhuangbin Chen, Jinyang Liu, Wenwei Gu, Yuxin Su, and Michael R. Lyu. 2021. Experience Report: Deep Learning-based System Log Analysis for Anomaly Detection. CoRR, abs\/2107.05908 (2021), arXiv:2107.05908. arxiv:2107.05908"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510085"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE51524.2021.9678746"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE-COMPANION.2019.00023"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134015"},{"key":"e_1_2_1_11_1","volume-title":"4th Symposium on Networked Systems Design and Implementation (NSDI","author":"Fonseca Rodrigo","year":"2007","unstructured":"Rodrigo Fonseca, George Porter, Randy H. Katz, Scott Shenker, and Ion Stoica. 2007. X-Trace: A Pervasive Network Tracing Framework. In 4th Symposium on Networked Systems Design and Implementation (NSDI 2007), April 11-13, 2007, Cambridge, Massachusetts, USA, Proceedings, Hari Balakrishnan and Peter Druschel (Eds.). USENIX. http:\/\/www.usenix.org\/events\/nsdi07\/tech\/fonseca.html"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304004"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/NOMS56928.2023.10154383"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3611643.3613881"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460345"},{"key":"e_1_2_1_16_1","volume-title":"Capturing and Enhancing In Situ System Observability for Failure Detection. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018","author":"Huang Peng","year":"2018","unstructured":"Peng Huang, Chuanxiong Guo, Jacob R. Lorch, Lidong Zhou, and Yingnong Dang. 2018. Capturing and Enhancing In Situ System Observability for Failure Detection. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018, Carlsbad, CA, USA, October 8-10, 2018, Andrea C. Arpaci-Dusseau and Geoff Voelker (Eds.). USENIX Association, 1\u201316. https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/huang"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICWS53863.2021.00063"},{"key":"e_1_2_1_18_1","volume-title":"2023 USENIX Annual Technical Conference, USENIX ATC 2023","author":"Huye Darby","year":"2023","unstructured":"Darby Huye, Yuri Shkuro, and Raja R. Sambasivan. 2023. Lifting the veil on Meta\u2019s microservice architecture: Analyses of topology and request workflows. In 2023 USENIX Annual Technical Conference, USENIX ATC 2023, Boston, MA, USA, July 10-12, 2023, Julia Lawall and Dan Williams (Eds.). USENIX Association, 419\u2013432. https:\/\/www.usenix.org\/conference\/atc23\/presentation\/huye"},{"key":"e_1_2_1_19_1","unstructured":"Jaeger. 2024. An open source distributed tracing platform. https:\/\/www.jaegertracing.io\/"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132749"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465529.2465753"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357223.3362736"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE48619.2023.00150"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3608129"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE56229.2023.00077"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2019.00085"},{"key":"e_1_2_1_27_1","unstructured":"Locust. 2024. An open source load testing tool. https:\/\/locust.io\/"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3472883.3487003"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815415"},{"key":"e_1_2_1_30_1","unstructured":"OpenTelemetry. 2024. High-quality ubiquitous and portable telemetry to enable effective observability. https:\/\/opentelemetry.io\/"},{"key":"e_1_2_1_31_1","unstructured":"OpenTelemetry. 2024. OpenTelemetry Traces. https:\/\/opentelemetry.io\/docs\/concepts\/signals\/traces\/#spans"},{"key":"e_1_2_1_32_1","unstructured":"OpenTelemetry. 2024. OpenTelemetry Zero-code Instrumentation. https:\/\/opentelemetry.io\/docs\/zero-code\/"},{"key":"e_1_2_1_33_1","volume-title":"Trace Semantic Conventions. https:\/\/opentelemetry.io\/docs\/specs\/semconv\/general\/trace\/","year":"2024","unstructured":"OpenTelemetry. 2024. Trace Semantic Conventions. https:\/\/opentelemetry.io\/docs\/specs\/semconv\/general\/trace\/"},{"key":"e_1_2_1_34_1","unstructured":"OpenTelemetry. 2024. Vendor-agnostic way to receive process and export telemetry data. https:\/\/opentelemetry.io\/docs\/collector\/"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3540250.3558951"},{"key":"e_1_2_1_36_1","unstructured":"Prometheus. 2024. Monitoring system & time series database. https:\/\/prometheus.io\/"},{"key":"e_1_2_1_37_1","volume-title":"CLP: Efficient and Scalable Search on Compressed Text Logs. In 15th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2021","author":"Rodrigues Kirk","year":"2021","unstructured":"Kirk Rodrigues, Yu Luo, and Ding Yuan. 2021. CLP: Efficient and Scalable Search on Compressed Text Logs. In 15th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2021, July 14-16, 2021, Angela Demke Brown and Jay R. Lorch (Eds.). USENIX Association, 183\u2013198. https:\/\/www.usenix.org\/conference\/osdi21\/presentation\/rodrigues"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3603269.3604823"},{"key":"e_1_2_1_39_1","volume-title":"Mike Burrows, Pat Stephenson, Manoj Plakal, Donald Beaver, Saul Jaspan, and Chandan Shanbhag.","author":"Sigelman Benjamin H","year":"2010","unstructured":"Benjamin H Sigelman, Luiz Andr\u00e9 Barroso, Mike Burrows, Pat Stephenson, Manoj Plakal, Donald Beaver, Saul Jaspan, and Chandan Shanbhag. 2010. Dapper, a large-scale distributed systems tracing infrastructure."},{"key":"e_1_2_1_40_1","volume-title":"Train Ticket: A Benchmark Microservice System. https:\/\/github.com\/FudanSELab\/train-ticket","author":"Ticket Train","year":"2024","unstructured":"Train Ticket. 2024. Train Ticket: A Benchmark Microservice System. https:\/\/github.com\/FudanSELab\/train-ticket"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3545008.3545026"},{"key":"e_1_2_1_42_1","volume-title":"18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24)","author":"Wang Rui","year":"2024","unstructured":"Rui Wang, Devin Gibson, Kirk Rodrigues, Yu Luo, Yun Zhang, Kaibo Wang, Yupeng Fu, Ting Chen, and Ding Yuan. 2024. uSlope: High Compression and Fast Search on Semi-Structured Logs. In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24). USENIX Association, Santa Clara, CA. 529\u2013544. isbn:978-1-939133-40-3 https:\/\/www.usenix.org\/conference\/osdi24\/presentation\/wang-rui"},{"key":"e_1_2_1_43_1","volume-title":"On the Feasibility of Parser-based Log Compression in Large-Scale Cloud Systems. In 19th USENIX Conference on File and Storage Technologies, FAST 2021","author":"Wei Junyu","year":"2021","unstructured":"Junyu Wei, Guangyan Zhang, Yang Wang, Zhiwei Liu, Zhanyang Zhu, Junchao Chen, Tingtao Sun, and Qi Zhou. 2021. On the Feasibility of Parser-based Log Compression in Large-Scale Cloud Systems. In 19th USENIX Conference on File and Storage Technologies, FAST 2021, February 23-25, 2021, Marcos K. Aguilera and Gala Yadgar (Eds.). USENIX Association, 249\u2013262. https:\/\/www.usenix.org\/conference\/fast21\/presentation\/wei"},{"key":"e_1_2_1_44_1","volume-title":"Zeno: Diagnosing Performance Problems with Temporal Provenance. In 16th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2019","author":"Wu Yang","year":"2019","unstructured":"Yang Wu, Ang Chen, and Linh Thi Xuan Phan. 2019. Zeno: Diagnosing Performance Problems with Temporal Provenance. In 16th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2019, Boston, MA, February 26-28, 2019, Jay R. Lorch and Minlan Yu (Eds.). USENIX Association, 395\u2013420. https:\/\/www.usenix.org\/conference\/nsdi19\/presentation\/wu"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449905"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3611643.3616249"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1002\/SMR.2413"},{"key":"e_1_2_1_48_1","volume-title":"The Benefit of Hindsight: Tracing Edge-Cases in Distributed Systems. In 20th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2023","author":"Zhang Lei","year":"2023","unstructured":"Lei Zhang, Zhiqiang Xie, Vaastav Anand, Ymir Vigfusson, and Jonathan Mace. 2023. The Benefit of Hindsight: Tracing Edge-Cases in Distributed Systems. In 20th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2023, Boston, MA, April 17-19, 2023, Mahesh Balakrishnan and Manya Ghobadi (Eds.). USENIX Association, 321\u2013339. https:\/\/www.usenix.org\/conference\/nsdi23\/presentation\/zhang-lei"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-981-16-8504-0","volume-title":"CRISP: Critical Path Analysis of Large-Scale Microservice Architectures. In 2022 USENIX Annual Technical Conference, USENIX ATC 2022","author":"Zhang Zhizhou","year":"2022","unstructured":"Zhizhou Zhang, Murali Krishna Ramanathan, Prithvi Raj, Abhishek Parwal, Timothy Sherwood, and Milind Chabbi. 2022. CRISP: Critical Path Analysis of Large-Scale Microservice Architectures. In 2022 USENIX Annual Technical Conference, USENIX ATC 2022, Carlsbad, CA, USA, July 11-13, 2022, Jiri Schindler and Noa Zilberman (Eds.). USENIX Association, 655\u2013672. https:\/\/www.usenix.org\/conference\/atc22\/presentation\/zhang-zhizhou"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2308.00393"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSRE59848.2023.00033"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2018.2887384"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338961"},{"key":"e_1_2_1_54_1","unstructured":"Zipkin. 2024. A distributed tracing system. https:\/\/zipkin.io\/"}],"container-title":["Proceedings of the ACM on Software Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3728888","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:52:01Z","timestamp":1752684721000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3728888"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,22]]},"references-count":54,"journal-issue":{"issue":"ISSTA","published-print":{"date-parts":[[2025,6,22]]}},"alternative-id":["10.1145\/3728888"],"URL":"https:\/\/doi.org\/10.1145\/3728888","relation":{},"ISSN":["2994-970X"],"issn-type":[{"value":"2994-970X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,22]]}}}