PaperlayerView exact revision on arXiv

Source-linked AI summary

A Microservice Graph Generator with Production Characteristics

Fanrong Du, Jiuchen Shi, Quan Chen, Li Li, Minyi Guo

arXiv:2412.19083v1cs.SE

TL;DR

Production traces are too large for experiments, and existing benchmarks lack important production characteristics. DGG constructs and clusters trace-based graphs, then generates dependency graphs using random models of downstream calls. Its generated graphs resemble real traces, while resource efficiency rises by up to 44.8% with QoS ensured.

  • Problem

    Production traces are too large for experiments, while existing benchmarks and trace analyses lack production characteristics including dynamic interfaces and service-graph variation.

    Source: §I · p. 1

  • Method

    DGG constructs fine-grained call graphs from traces, merges and clusters dependency graphs, then uses random graph models to generate production-characteristic service dependency graphs.

    Source: §I · p. 2

  • Results

    DGG-generated dependency graphs closely resemble real traces, and resource management based on its fine-grained call-graph construction increases resource efficiency by up to 44.8% while ensuring QoS.

    Source: §VII · pp. 10–11

  • Takeaways & Limitations

    The case studies support using DGG to generate production-characteristic benchmark graphs and investigate resource scaling under dynamic loads.

    Source: §I · p. 2

Abstract

from arXiv · show

A production microservice application may provide multiple services, queries of a service may have different call graphs, and a microservice may be shared across call graphs. It is challenging to improve the resource efficiency of such complex applications without proper benchmarks, while production traces are too large to be used in experiments. To this end, we propose a Service Dependency Graph Generator (DGG) that comprises a Data Handler and a Graph Generator, for generating the service dependency graphs of benchmarks that incorporate production-level characteristics from traces. The data handler first constructs fine-grained call graphs with dynamic interface and repeated calling features from the trace and merges them into dependency graphs, and then clusters them into different categories based on the topological and invocation types. Taking the organized data and the selected category, the graph generator simulates the process of real microservices invoking downstream microservices using a random graph model, generates multiple call graphs, and merges the call graphs to form the small-scale service dependency graph with production-level characteristics. Case studies show that DGG's generated graphs are similar to real traces in terms of topologies. Moreover, the resource scaling based on DGG's fine-grained call graph constructing increases the resource efficiency by up to 44.8% while ensuring the required QoS.

I. INTRODUCTION

Production traces are too large for experiments, while existing benchmarks and generators miss important service-specific call-graph characteristics. DGG builds production-informed dependency graphs, and case studies report similarity to real call graphs and resource-efficiency gains while maintaining QoS.

I. INTRODUCTION

  • Production traces are too large for experiments, and existing benchmarks lack characteristics such as dynamic interfaces, despite much larger and more varied production services.HotelReservation has 8 call graphs and 22 microservices, whereas Alibaba services can have over 40 call graphs, depth exceeding 15, and over 500 microservices.Source: §I · p. 1
  • Existing trace analysis and generators overlook service-graph variation, interrelated call graphs, repeated calls, sibling relationships, and individual microservice interfaces.These characteristics matter for resource scaling because they can lead to heterogeneous microservice computing-resource demand.Source: §I · pp. 1–2
  • DGG is motivated by production observations of repeated downstream calls, dynamic interfaces, varying graph topology and invocation patterns, and sibling-influenced children-set choices.The paper also identifies in-depth trace analysis and production-characteristic graph generation as contributions.Source: §I · p. 2
  • DGG’s Data Handler constructs fine-grained call graphs from production traces, merges them into dependency graphs, and clusters them by topology and invocation features.Its Graph Generator models downstream calls as sibling-influenced children sets, generates simulated call graphs, and merges them into a final dependency graph.Source: §I · p. 2
  • DGG-generated call graphs are reported as similar to real-world graphs, and fine-grained call-graph construction increases resource efficiency by up to 44.8% while ensuring QoS.The case studies examine graph similarity and resource scaling under dynamic loads.Source: §I · p. 2

II. RELATED WORK

Prior work covers cloud workloads, microservice benchmarks, and graph generation, but leaves gaps in production characteristics and interrelated call graphs. The paper also defines the graph and microservice concepts used in its analysis.

II. RELATED WORK

  • Prior microservice studies analyze call graphs but leave service-dependency variation, inter-microservice relationships, and individual interfaces underexplored.Earlier cloud workload analyses addressed runtime performance or resource use, rather than microservice architecture.Source: §II · p. 2
  • Existing benchmarks can have few call graphs and microservices, limited communication modes, and little microservice sharing compared with production applications.µsuit has four services with two microservices each and uses only gRPC for inter-microservice communication.Source: §II · p. 2
  • A prior call-graph generator models overall service distributions but does not capture dependency-graph variation or interconnect generated call graphs; it also omits sharing, communication modes, and sibling effects.Developer customization tools do not automatically capture production characteristics.Source: §II · pp. 2–3

III. BACKGROUND AND TERMINOLOGY

  • A service dependency graph comprises the call graphs formed by queries, which may access different subsets of microservices and share microservices across graphs.The paper calls microservices accessed by multiple call graphs “shared microservices.”Source: §III · p. 3
  • Graph topology is described by depth and width; microservices are classified by downstream behavior, and communication may use IPC, RPC, or MQ.Depth is the longest path from the entry microservice, width the maximum number of microservices at any depth layer; RELAY must call downstream services, LEAF does not, and NORMAL does so probabilistically.Source: §III · p. 3

IV. MICROSERVICE TRACE ANALYSIS

The trace analysis examines Alibaba and Meta production data and finds dynamic call-graph proportions alongside substantial variation among dependency graphs. It also reports long-tailed service activity and changing query volumes over time.

A. Overview of Alibaba and Meta Traces

B. Characterizing Dependency Graphs

  • Alibaba dependency graphs are dynamic: their constituent call graphs change in proportion over time, and topological and invocation patterns vary across graphs.The study identifies these as its two major observations about production dependency graphs.Source: B. Characterizing Dependency Graphs · p. 3

1) Dynamic Service Dependency Graphs:

  • Service and call-graph occurrences are long-tailed; after retaining the top 90% of occurrences, the analysis includes 72,942 call graphs and averages more than 45 call graphs per dependency graph.The excluded 10% of services average 8.5 requests per day, and 92.6% of them receive only one query per day.Source: 1) Dynamic Service Dependency Graphs · pp. 3–4
  • For Alibaba service S 130831269, both total queries and queries accessing individual call graphs vary over time.The figure plots total query counts and call-graph query counts over time.Source: Figure 2 · p. 3, 1) Dynamic Service Dependency Graphs · p. 4

2) Topological Differences in Dependency Graphs:

Production dependency graphs vary in topology and invocation patterns, while call graphs share children, include repeated calls, and show sibling-set influence. These characteristics motivate category-aware graph modeling.

2) Topological Differences in Dependency Graphs:

  • Depth and width vary widely across production graphs, and some invocation patterns occur only in particular services.Examples include self-invocation in top-1, 8, and 11, and depths of 2 for top-4 and 7 versus 6 for top-8 and 11.Source: 2) Topological Differences in… · p. 4

3) Insights from Characterizing Dependency Graphs:

C. Characterizing Call Graphs:

  • Across the traces, children sets overlap, repeated calls occur, and sibling microservices influence downstream-call probabilities.These are the three key observations reported from the call-graph characterization.Source: C. Characterizing Call Graphs · p. 4

1) Characteristics of Children Sets:

2) Sibling Set Influence:

  • 55.7% of Alibaba services are influenced by sibling sets, with influence rates of 92.7%, 64.8%, and 76.2% at call depths 3, 4, and 5.The variation relates to the number of microservices at each depth and the sibling-set combinations affecting children-set calls.Source: 2) Sibling Set Influence · p. 4
  • Sibling sets can change which children set a microservice invokes, and related services may be candidates for merging to reduce call overhead.For example, B calls E with sibling set {C} and F with sibling set {D}; the paper suggests merging B, C, and E or B, D, and F.Source: 2) Sibling Set Influence · pp. 4–5

3) Insights from Characterizing Call Graphs:

Production microservices differ in interface counts and interface-calling patterns across call graphs. The characterization also points to modeling repeated calls, sibling influence, and interface-level behavior in simulated graphs and resource management.

3) Insights from Characterizing Call Graphs:

  • Simulated graphs should model children sets, repeated calls, and sibling-set influence; fine-grained tracing and resource management of repeated calls are also important for scaling.Source: 3) Insights from Characterizing Call… · p. 5

1) Types of Microservice Interfaces:

  • 88.31% of Alibaba microservices have fewer than 10 interfaces, while memcached and http-called have more interfaces than other services.Interface counts vary across communication modes, with HTTP-type microservices notably higher.Source: 1) Types of Microservice Interfaces · p. 5

2) Interface Calling Patterns:

  • Shared microservices may be called through different interfaces by different call graphs, with five observed interface-calling patterns.Patterns include one graph using different interfaces, different graphs using the same interface, and different graphs using different interfaces.Source: 2) Interface Calling Patterns · p. 5

3) Insights from Characterizing Individual Microservices:

DGG organizes trace-derived dependency graphs and generates simulated service graphs using category-specific random models. It constructs and merges fine-grained call graphs, clusters dependency graphs, then generates and merges multiple call graphs.

A. Overview of DGG

  • DGG’s data handler constructs fine-grained call graphs from traces, merges them into dependency graphs, and clusters those graphs by topology and invocation characteristics.Source: A. Overview of DGG · p. 5
  • The data handler also obtains each service’s occurrence probability within each category, which guides model selection during generation.Source: A. Overview of DGG · p. 6
  • For a selected category, the graph generator builds a random graph model for each service, generates n call graphs using service occurrence probabilities, and merges them into a dependency graph.Source: A. Overview of DGG · pp. 5–6

1) Fine-grained Call Graph Constructing:

DGG preserves interface-specific and repeated-call structure in fine-grained graphs, clusters dependency graphs by topology and invocation properties, and learns a random graph model for generating call graphs. The model conditions downstream-call choices on sibling sets and depth.

1) Fine-grained Call Graph Constructing:

2) Dependency Graph Clustering:

  • On the Alibaba trace, clustering produced 6 classes, with 3.4X higher intra-cluster than inter-cluster similarity.Graph-kernel similarity and K-means group graphs by topology and invocation properties; K is selected by the highest silhouette coefficient.Source: 2) Dependency Graph Clustering · p. 6

1) Random Graph Modeling:

  • For each trace service, DGG establishes a random graph model from its real dependency graph.The model represents vertices with microservice name, interface, and label, and edges with source, destination, repeat count, and communication mode.Source: 1) Random Graph Modeling · pp. 6–7
  • A possible children set records downstream vertices and call edges, including interface, label, repeat count, and communication mode.The model includes empty children sets for microservices with no downstream calls.Source: 1) Random Graph Modeling · p. 7
  • DGG models the probability of a microservice calling a children set conditional on its sibling set and call depth.The average time to establish a model was 4 ms in the experiments.Source: 1) Random Graph Modeling · p. 7

2) Call Graph Generation Algorithm:

The call-graph generator expands a query from an entry vertex, selecting downstream children sets from the random graph model until no further vertices can be added. DGG merges the requested generated call graphs into a service dependency graph.

2) Call Graph Generation Algorithm:

  • The generator queues an entry vertex, adds children and call edges for normal or relay vertices, and iteratively expands newly added vertices until the queue is empty.The resulting call graph is stored as a list of call relationships.Source: 2) Call Graph Generation Algorithm · p. 7
  • Call-graph generation takes O(|V| · k) time and O(|E|) space, with an average generation time of 0.7 ms in the experiments.Here, |V| is the number of vertices, k the average children-set size, and |E| the number of edges.Source: 2) Call Graph Generation Algorithm · p. 7
  • After the user-specified number of call graphs is generated, DGG merges them into a service dependency graph.The generator uses actual microservice names, managing shared microservices and cases with multiple parents or depths.Source: 2) Call Graph Generation Algorithm · p. 7

D. Theoretical analysis

The theoretical analysis argues that the random graph model reproduces real call-graph distributions for width, depth, and total microservice count. The case studies then evaluate generated dependency graphs against real-world graphs and examine resource scaling.

D. Theoretical analysis

  • The analysis establishes similarity between generated and real call-graph distributions for layer width, total depth, and total microservice count.It proceeds from width to depth and then total microservice number, using the relationship between layer widths and call-graph depth.Source: D. Theoretical analysis · pp. 7–8

VI. CASE STUDIES

  • The case studies compare DGG-generated service dependency graphs with real-world graphs and also investigate resource-scaling efficiency under dynamic loads.The theoretical analysis states that its detailed proof is available separately.Source: §VI · p. 8, D. Theoretical analysis · p. 8

A. Dependency Graph Similarity of DGG

On Alibaba trace data, DGG-generated call graphs more closely match real-world distributions than CGG across depth, microservice count, microservice types, and communication modes. The comparison uses Jensen-Shannon divergence for probability distributions.

2) Graph Topology Similarity:

3) Microservice and Communication Similarity:

  • DGG’s microservice-type distributions match real call graphs more closely, while CGG has fewer relay and normal services and excess memcached, database, and leaf services.The paper relates CGG’s mix to earlier termination because relay and normal services may continue calls while the other listed types terminate sooner.Source: 3) Microservice and Communication… · pp. 8–9, Figure 9 · p. 9
  • DGG’s communication-mode distributions closely approximate real-world patterns, and its call graphs have more similar type and communication distributions than CGG’s.CGG does not specify how it determines communication modes, so that comparison is made between DGG and the real-world dataset.Source: 3) Microservice and Communication… · p. 9, Figure 10 · p. 9

B. Resource Efficiency with DGG’s Call Graph Constructor

The section evaluates integrating DGG’s fine-grained call-graph construction into online resource scaling. It describes the scaling baselines and the benchmarks and workload conditions used for evaluation.

B. Resource Efficiency with DGG’s Call Graph Constructor

1) Scaling Strategy and Baselines:

  • MAX-Scale and MIN-Scale use coarse-grained call graphs, allocating resources from each microservice’s maximum or minimum modeled demand, respectively.The baselines map fine-grained call graphs to the same coarse graph; prior strategies use aggressive maximum-demand or conservative minimum-demand scaling.Source: 1) Scaling Strategy and Baselines · p. 9

2) Investigation Setup:

  • Evaluation uses six DGG-generated benchmarks, six benchmarks drawn from Alibaba traces, and an enhanced SocialNetwork benchmark with four added microservices and six call graphs.Each benchmark runs for one hour; QoS is set to its 95th-percentile latency without resource constraints, and the figures report normalized latency and CPU core-hour usage.Source: 2) Investigation Setup · pp. 9–10, Figure 11 · p. 10, Figure 12 · p. 10
  • Simulated benchmark loads use query rates from the top-accessed call graphs in the corresponding trace clustering set, while real-world benchmark loads use trace rates.SocialNetwork uses the six most-queried call-graph rates from the trace.Source: 2) Investigation Setup · p. 9

3) Tail Latency and Resource Allocation:

FineGrained-Scale uses less CPU than MAX-Scale while maintaining QoS, whereas MIN-Scale violates QoS. The paper attributes the scaling differences to call-graph detail and reports that construction overhead fits within the monitoring interval.

3) Tail Latency and Resource Allocation:

  • 25.3% average and 44.8% maximum CPU core-hour reductions versus MAX-Scale accompany QoS guarantees; MIN-Scale violates QoS by 2.5X on average.MIN-Scale uses the least resources but has serious QoS violations.Source: 3) Tail Latency and Resource Allocation · p. 10
  • Fine-grained call graphs distinguish interfaces and repeated calls, enabling just-enough allocation; coarse graphs lead MIN-Scale to QoS violations and MAX-Scale to excess allocation.FineGrained-Scale identifies different call graphs, unlike the coarse mapping used by both baselines.Source: 3) Tail Latency and Resource Allocation · p. 10

4) Diving into High Scaling Efficiency:

5) Overhead of the FineGrained-Scale:

  • At 30,000 queries per minute, fine-grained call-graph construction takes approximately 2100ms, within the one-minute monitoring interval.Its time complexity is O(Nm) for N queries with m inter-microservice calls per query.Source: 5) Overhead of the FineGrained-Scale · p. 10

VII. CONCLUSION

  • DGG-generated dependency graphs closely resemble real traces, and resource management using fine-grained construction improves efficiency by up to 44.8% while ensuring QoS.Source: §VII · pp. 10–11
Loading 2412.19083v1…