  Performance debugging in production is a fundamental activity in modern
service-based systems. The diagnosis of performance issues is often
time-consuming, since it requires thorough inspection of large volumes of
traces and performance indices. In this paper we present DeLag, a novel
automated search-based approach for diagnosing performance issues in
service-based systems. DeLag identifies subsets of requests that show, in the
combination of their Remote Procedure Call execution times, symptoms of
potentially relevant performance issues. We call such symptoms Latency
Degradation Patterns. DeLag simultaneously searches for multiple latency
degradation patterns while optimizing precision, recall and latency
dissimilarity. Experimentation on 700 datasets of requests generated from two
microservice-based systems shows that our approach provides better and more
stable effectiveness than three state-of-the-art approaches and general purpose
machine learning clustering algorithms. DeLag is more effective than all
baseline techniques in at least one case study (with p $\leq$ 0.05 and
non-negligible effect size). Moreover, DeLag outperforms in terms of efficiency
the second and the third most effective baseline techniques on the largest
datasets used in our evaluation (up to 22%).
