Monolith to Microservices: Representing Application Software through Heterogeneous Graph Neural Network

1 Introduction

Monolith architecture is the traditional unified model for designing software applications. It encapsulates multiple business functions into a single deployable unit. But such applications become difficult to understand and hard to maintain as they age, as developers find it difficult to predict the change impact [Kuryazov et al., 2020]. Therefore, microservice [Th¨ones, 2015] architectures are seen as an alternative. It aims to represent the application as a set of small services where each service is responsible for a single functionality. It brings multiple benefits like efficient team structuring, independence in development & deployment, enables flexible scaling and less restriction on technology or programming language preference. But migrating from monolith to microservices is a labour intensive task. It often involves domain experts, microservices architects and monolith developers working in tandem to analyze the application from multiple views and identify the components of monolith applications that can be turned into a cohesive, granular service.

∗The work was done when Sambaran was affiliated to IBM Research prior to joining Amazon

†Utkarsh is currently at Google

They also need to work with constraints like the exact number of microservices to be exposed and components that should definitely be part of a particular microservice.

The software engineering community refers to this migration process as a software decomposition task. Many works [Tzerpos and Holt, 2000; Harman et al., 2002; Mazlami et al., 2017; Mahouachi, 2018; Mancoridis et al., 1999] leverage the syntactical relationships between the programs and treated this decomposition as an optimization problem to improve different quality metrics like cohesion, coupling, number of modules, amount of changes etc. While the accuracy of these approaches has been evolving over time, they have their drawbacks such as 1) reliance on external artifacts like logs, commit history etc. 2) focus on only a subset of the programs 3) less attention to non program artifacts like the tables, files 4) minimal consideration for transactional data. Recently [Jin et al., 2019; Kalia et al., 2020] executed test cases to extract runtime traces. Each execution is considered as a business function and they try to cluster business functions. But this work relies on access to runtime traces and complete coverage of test cases which cannot always be guaranteed. Also, these works did not consider data entities for decomposition.

Graphs are a natural choice to represent the application's structural and behavioral information [Mancoridis et al., 1998; Desai et al., 2021]. The structural information consisting of different application entities such as programs, files, database tables can be represented as nodes and their different relationships such as calls, extends, implements between program to program and different CRUD operations that happen from program to data resources (table, file) can be represented as edges in the graph. Figure 1 captures the construction of a heterogeneous graph from a sample java code. The behavioral information of the application identified through the sequence of programs and data resources that come together to support a business function can be captured as node/edge attributes. The monolith to microservices task can thus be viewed as a graph based clustering task which involves 1) Representation learning of application implementation from the graph structure and 2) Using this learnt representation for clustering. Graph neural networks have achieved state of the art results for multiple graph-based downstream tasks such as node classification and graph classification [Kipf and Welling, 2017; Xu et al., 2019; Veliˇckovi´c et al., 2018]. Most graph neural networks follow

.

message passing mechanisms where the vector representation of a node is updated by combining its own features and aggregated features from its neighborhood. Recently [Desai et al., 2021] showed how the programs and its relationships in the application can be represented as a graph and proposed a multi-objective graph convolution network that combined node representation & node clustering by diluting outliers. But since the framework did not consider application's data resources like database tables, files and the different relationships that exists between programs & resources in the graph construction, the functional independence property of microservices is not completely satisfied. In addition, application architects have a functional view of the application, so they decide on the target number of microservices and identify the core representative programs or tables from the monolith for each microservice. The solution should therefore accept the architect inputs as constraints and form clusters to maximize functional alignment.

In this work, we propose a novel graph neural network based solution to refactor monolith applications into a desired number of microservices. The main contributions of our paper are listed below.

1. We translate the application software's structural and behavioral properties into a heterogeneous graph through nodes, edges and node/edge attributes.
2. We introduce CHGNN - a novel heterogeneous graph neural network (GNN), that enables the representation of both data resources and programs. For the first time in literature, we perform a constraints-based clustering jointly in the framework of heterogeneous GNN.
3. We show that inclusion of heterogeneous information generates better quality microservices recommendations through four publicly available monolith applications.

2 Methodology

Given a monolith application and constraints Slist - the list of K seed sets from the subject matter experts (SMEs), we want to partition the monolith into K fairly distributed clusters where each cluster is a group of programs and resources that perform a well-defined functionality.

2.1 Converting Applications to Graph

We now describe our approach to represent an application as a graph. The primary programming construct in different languages is different - a class in Java and a program in COBOL. Hence, in the rest of this work, we refer to classes or programs as simply programs for consistency. Consider a simple Java application as shown in Figure 1. Each class or program in the application can be represented as a Program node in the graph. Certain programs might also access resources such as database tables, files or other data structures. These can be represented as Resource nodes in the graph. We denote the combined set of Program and Resource nodes as V , the set of all nodes. We establish an undirected CALLS edge from Program node A to Program node B if there is a method in the program A that calls a method from program B. We also identify resource usage and create a CRUD edge from Program node X to Resource node R, if the program X accesses resource R. Static analysis tools can analyze the application code and identify the call chains and resource usage. E denotes the combined set of all edges between the various nodes in the graph. Multiple method calls or resource usages between two nodes are still represented by a single unweighted edge.

We now generate the node attribute matrix, corresponding to the Program and Resource nodes of the graph. APIs exposed by applications are referred as EntryPoint Specifications [Dietrich et al., 2018], or simply, Entrypoints (EPs). The methods invoked through these APIs are annotated with tags such as @Api as shown in Figure 1. We refer to such methods as entrypoint methods and the corresponding programs as entrypoint programs. Each entrypoint program can thus be associated with multiple entrypoints due to different entrypoint methods. From an entrypoint method, we can obtain a sequence of invoked methods and their corresponding programs using the execution traces of that Entrypoint. If EP is the set of Entrypoints in an application and VP , is the set of Program nodes, we can define a matrix A|VP |×|EP | , such that A(i, p) = 1 if program i is present in the execution trace of entrypoint p, else 0. Additionally, we define another matrix C |VP |×|VP | such that C(i, j) is the number of Entrypoint execution traces that contain both programs i and j. If a program is not invoked in an execution trace for any Entrypoint, we remove the corresponding non-reachable Program node from the graph. Finally, classes or programs may also inherit from other classes or programs or implement Interfaces. In Figure 1, class A inherits from class S. Although this establishes a dependency between the programs, it is not a direct method invocation. Hence, this dependency is not included as an edge in the graph, but as a Program node attribute. Therefore, we define a matrix I |VP |×|VP | and set I(i, j) = I(j, i) = 1 if programs i and j are related via an inheritance relationship and 0 otherwise. The attribute matrix for Program nodes is the concatenation of A, C and I, and denoted as XP .

For Resource nodes, the Inheritance features are not applicable. The A and P matrices are obtained by summing up the corresponding rows from the respective XP matrices. The relationship between Program nodes and Resource nodes is many-to-many and this formulation simply aggregates features from all related programs into the resource to form the resource attribute matrix XR. Each constituent matrix of XP and XR is row-normalized individually. The final set of node attributes are denoted as XV = {XP ,XR}. The Edge attributes for CALLS edges is simply the vector [1, 0] and there are no additional features. For CRUD edges, the attribute vector represents the type of resource access performed. Since a program can access a resource in more than one fashion, this is a 1 × 4 vector, where each attribute represents the associated access type - [Create, Read, Update, Delete]. Hence a program that reads and updates a Resource node will have [0, 1, 1, 0] as the edge feature. The edge attribute matrix is represented as XE.

Thus, an application can be represented by a heterogeneous graph as G = (V,E,XV ,XE). Let us assume that ϕ(v) and ψ(e) denote the node-type of v and edge-type of e respectively. Let us use xv ∈ RDϕ(v) to denote the attribute vector for the node v which belongs to Dϕ(v) dimensional space. Similarly, xe ∈ RDψ(e) is the edge attribute of the edge e.

2.2 Proposed Heterogeneous Graph Neural Network

In this subsection, we aim to propose a graph neural network (GNN) which can (i) handle different node and edge types in the graph, (ii) obtain vector representation of both nodes and edges by jointly capturing both the structure and attribute information, (iii) output community membership of all the nodes in the graph in a unified framework. We refer the proposed architecture as CHGNN (Community aware Heterogeneous Graph Neural Network). There are different steps in the design of CHGNN as described below.

Mapping Entities to a Common Vector Space

Due to heterogeneity from different software artifacts, attributes associated with nodes and edges of the input graph are not of same types and they can have different dimensions. Such heterogeneity can be addressed in the framework of message passing heterogeneous graph neural networks in two ways: (i) Map the initial attributes to a common vector space using trainable parameter matrices at the beginning [Wang et al., 2019]; (ii) Use different dimensional parameter matrices while aggregating and combine information at each step of message passing [Vashishth et al., 2020]. We choose the first strategy since that makes the subsequent design of the GNN simpler and helps to add more layers in the GNN. So, we introduce type specific trainable matrices Wϕ(v) ∈ RF (0)×Dϕ(v)

for nodes and Wψ(e) ∈ RF (0)×Dψ(e) for edges ∀v ∈ V and ∀e ∈ E.

where σ is a nonlinear activation function. xv and xe are the initial attribute vectors of node v and edge e respectively. h(0) v and h(0) e are considered as 0th layer embeddings for v and e respectively. They are fed to the message passing framework as discussed below.

Message Passing Layers for Nodes and Edges

Message passing graph neural networks have achieved significant success for multiple node and graph level downstream tasks. In this framework, we obtain vector representation for both nodes and edges of the heterogeneous graph. There are L ≥ 1 message passing layers. We define the lth layer (1 ≤ l ≤ L) of this network as follows.

As the first step of a message passing layer, features from the neighborhood are aggregated for each node. In recent literature, it has been shown that obtaining both node and edge representation improves the downstream performance for multiple applications [Jiang et al., 2019; Bandyopadhyay et al., 2019]. Following that, we also design the GNN to exchange features between nodes and edges, and update the vector representation for both. In each layer, we use two parameter matrices W (l) 1 ∈ RF (l)×F (l-1) and W (l) 2 ∈ RF (l)×F (l-1) to handle node and edge embeddings respectively. For a node v ∈ V , its neighborhood information is aggregated as:

where du and dv are the degrees of the nodes u and v respectively. 1 √du√dv is used to symmetrically normalize the degrees of the nodes in the graph [Kipf and Welling, 2017]. σ() is a nonlinear activation function and ∗ is Hadamard (element-wise) product. Next, the aggregated information z(l) v is combined with the embedding of node v to update it as follows.

h(l) v is considered as the node embedding of node v at lth layer. To update the embedding of an edge (u, v), we use the updated embeddings of two end point nodes and the existing embedding of the edge as follows (||: concatenation of vectors):

where W (l) 3 ∈ RF (l)×(F (l)+F (l-1) ) is a parameter matrix. This completes the definition of the layer l of the message passing network. Please note that the dimensions of the trainable matrices W (l) 1 , W (l) 2 and W (l) 3 determine the dimension of the embedding space of the nodes and edges.

To build the complete network, we first map the heterogeneous nodes and edges to a common space using Equation 1. Subsequently, we use 2 message passing layers (l = 1, 2) as encoders (compressing the feature space) and next 2 message passing layers (l = 3, 4; L = 4) as decoders (decompressing the feature space), with F (0) > F (1) > F (2) < F (3) = F (1) < F (4) = F (0) . To map the node and edge features to their respective input attribute space RDϕ(v) and RDψ(e) , we again use linear transformations followed by activation functions as shown below.

These reconstructed node and edge attributes are used to design the loss functions as discussed next.

Design of the Loss Functions and Joint Clustering of Heterogeneous Nodes

We use three types of unsupervised reconstruction losses.

Node Attribute Reconstruction: We try to bring the initial node features xv and the reconstructed node features ˆxv close to each other by minimizing ∑ ||xv - ˆxv||22 .

Edge Attribute Reconstruction: With similar motivation as above, we minimize ∑ e∈E ||xe - ˆxe||22 .

Link Reconstruction: Above two loss components do not capture anything about the link structure of the heterogeneous graph. Let us introduce the binary variables au,v ∀u, v ∈ V such that au,v = 1 if (u, v) ∈ E and au,v = 0 otherwise. We want to ensure that embeddings of two nodes are close to each other if there is an edge between them by minimizing (au,v - xu · xv )22 .

Unifying Node Clustering: After we map the monolith to a heterogeneous graph, we cluster the nodes of the graph to form microservices. As the nodes are represented in the form of vectors through the heterogeneous GNN encoder as discussed in Section 2.2, we unify the clustering objective with the heterogeneous GNN as follows.

The node embeddings at the end of encoding layers (i.e., L/2 layers) are h(L/2) v , ∀v ∈ V . We design a k-means++ objective [Arthur and Vassilvitskii, 2006] by introducing two parameter matrices M ∈ {0, 1}|V |×K and C ∈ RK×F (L/2) . M is the binary cluster assignment matrix where each row sums up to 1. We assume to know the number of clusters K. Mvk = 1 if node v belongs to kth cluster and Mvk = 0 otherwise 1 . kth row of C, denoted as Ck, is the center of kth cluster in the embedding space. Node clusters and the corresponding cluster centers can be obtained by minimizing

Allowing seed constraints : As motivated in Section 1, real-world applications generally have constraints provided by SMEs in the form of clustering seeds. To incorporate such constraints, we take a list of seed sets Slist = [S1, · · · , SK] as input, where each Si is a set of seed nodes that must belong to the corresponding cluster Ci.

With Slist as input, we need to ensure two requirements - 1) In the final output, every seed set (Si) must belong to a predetermined cluster (Ci) and 2) the embeddings of the seed sets in different clusters must be as far apart as possible. To address the first requirement we add hard constraints to our cluster assignment algorithm . This can be seen in Algorithm 1 (Lines 15-17), where for each seed artifact, we assign the

1 To avoid cluttering of notations, we use Mvk instead of Mindex(v)k, where 1 ≤ index(v) ≤ |V |

Algorithm 1 CHGNN

Input: Class dependencies and Slist (list of K seed sets)

• 1: Convert the application to a graph representation as defined in Section 2.1 and obtain the V , E and XV and XE.
• 2: Let Slist be [S1, · · · , SK]. Hence each cluster (Ck) has a mandatory set of seeds (Sk).
• 3: Let the list of clusters be [C1, · · · , CK] and the list of centers for each cluster be [C1, · · · ,CK].
• 4: Pre-train the heterogeneous GNN encoder and decoder (refer Training Procedure in our extended paper 2 )
• 5: % Initialize the cluster centers as follows %
• 6: Ck = ∑ k∈Sk hL/2 k /|Sk|, ∀k ∈ [1, · · · ,K] 7: for T iterations do 8: %Assign a cluster to each node % 9: for v ∈ V do 10: if v not in Slist then 11: % Find closest centres for non-seeds % 12: Find the closest center (Ck) with Equation 9 13: Add v to the corresponding cluster (Ck) 14: else 15: % Fix the cluster for seeds % 16: Find Sk such that v ∈ Sk 17: Add v to the corresponding cluster (Ck) 18: end if 19: end for 20: Update cluster centers with Equation 10. 21: Update the parameters of the heterogeneous GNN encoder and decoder by minimizing Eq. 8 using ADAM. 22: end for Output: Clusters and Cluster Centers

cluster manually. To address the second requirement we add soft constraints to our clustering loss function. This is captured by measuring the distance between the seed set centers (SCk) as shown in Equation 7. As the distance should be maximised, we negate this distance to maintain a minimization objective.

Hence, the total loss to be minimized by CHGNN is:

where W contains the trainable parameters of the GNN described in Section 2.2. α1, α2, α3 and α4 are non-negative weights. In our algorithm, we set them such that the sum of these non-negative weights always sum up to one.

2.3 Training and Analysis

First, we pre-train the parameters of the GNN without including the clustering loss component, i.e., setting α4 = 0 in Equation 8. We use ADAM optimization technique to update the parameters of the GNN. Once the pre-training is completed, we use alternating optimization techniques to update each of clustering parameters M and C, and parameters of GNN W, while keeping others fixed. Using Lloyd's update rule for k-means, we update M and C as:

where Nk = ∑ v∈V Mvk. Due to the presence of clustering

loss component in Equation 8, updating the parameters W of GNN can pull the node embeddings close to their respective cluster centers further, along with reconstructing initial node and edge attributes and the link structure.

3 Experimental Evaluation

To study the efficacy of our approach, we chose four publiclyavailable monoliths namely Daytrader, PlantsbyWebsphere (PBW), Acme-Air and GenApp. Together, these applications show a good diversity in terms of the programming paradigms, languages and technologies used. Details of each monolith are provided in Table 1. We did not include DietApp (used in baseline [Desai et al., 2021]), as the public repository does not expose the code used for interfacing between programs and tables. Hence DietApp reduces to a homogeneous graph (only programs). As expected, upon experimentation, we observe that CHGNN gets the same output as the baseline.

3.1 Constraints to Clustering

For each application, we get the target number of microservices (K clusters) and constraints of what entities each microservice (K seed sets) should contain as inputs from the SMEs. Naturally, the seed sets cannot be shared/overlap with each other. Typically, the constraints include tables and program entities that are central to the cluster. They act as a means to guarantee functional alignment.

3.2 Quantitative Metrics

To quantitatively evaluate the clusters, we use four established graph metrics. We briefly touch upon these below.

1. Modularity (Mod) : The Modularity metric [Newman and Girvan, 2004] is widely used to evaluate the quality of generated graph partitions. It computes the difference between the actual intra-edges of a cluster and the expected intra-edges of the cluster in a randomly re-wired graph. Higher the modularity - the better the partitions.
2. Non-Extreme Distribution (NED) : The NED metric [Wu et al., 2005] examines if the graph partitions are tiny, large or of an acceptable size. Rather than fixing the low and high limits to 5 and 20 [Wu et al., 2005], we take the average cluster size as input and check if the cluster size lies within the 50% tolerance bandwidth of the average. This change helps NED generalise well to small and large sized applications.

where N and K are the number of graph nodes and the number of clusters respectively. Here, we set ϵ to 0.5.

1. Coverage : Coverage [Fortunato, 2010] tries to measure cohesion by computing the ratio of the number of intra-cluster edges to the total number of edges in the graph. Higher coverage implies higher cohesion which results in better clusters.
2. S-Mod : S-Mod [Jin et al., 2019] is another quantitative approach that measures the quality of generated partitions. It is computed by subtracting coupling from cohesion. More cohesion implies more intra-cluster edges and more coupling implies more inter-cluster edges. For microservices, it is ideal to have high cohesion and low coupling. Hence, higher SMod values are favourable.

3.3 CombinedMetric

However in our experiments, we observe that a few boulder (very large) clusters and many dust (very small) clusters can increase intra-cluster edges and decrease inter-cluster edges. This improves S-Mod and Coverage considerably, but leads to a poor NED score - which penalises for size imbalance. Hence, instead of relying on a single metric, we calculate MetricSum (summing all metrics) and rank our approaches accordingly. MetricSum ∈ [-2, 4] as Mod ∈ [-1, 1], NED ∈ [0, 1], S-Mod ∈ [-1, 1] and Coverage ∈ [0, 1]. In all our experiments, we observe that every metric is positive for all the algorithms considered.

3.4 Baseline Algorithms and Experimental Setup

As converting monoliths to heterogeneous GNNs and applying them for clustering is a novel direction, we have designed most of the baselines with motivations from existing works on graph representation learning. They are discussed below.

COGCN++ : [Desai et al., 2021] introduced COGCN, wherein, the monolith application (having programs and resources) is converted to a homogeneous graph. Subsequently, COGCN, which has GCN layers trained on reconstruction and clustering loss, is applied on the homogeneous graph to obtain the micro-services. When running vanilla COGCN, we noticed that it does not ensure the mutual exclusivity of seed sets. Hence we add the seed constraint loss (Equation 7) to fulfill this requirement. We refer to this model as COGCN++. Note : COGCN++ does not consider edge embeddings/attributes - it only considers node embeddings.

HetGCNConv: Here, we create the heterogeneous graph as discussed in Section 2.1, but consider all the edges as of similar types. We map the heterogeneous nodes to a common vector space as done in Section 2.2 by using node-type specific parameter matrices Wϕ(v)'s. We then use the GCN convolution model and train it by setting α2 to 0.

CHGNN-EL : A variant of our proposed CHGNN where we drop the edge feature re-construction loss from the optimization procedure by setting α2 = 0 in Equation 8.

CHGNN : This is our final model proposed in this work.

Please note that COGCN++ is a homogeneous graph based approach. HetGCNConv and CHGNN-EL are two variants of our proposed heterogeneous model CHGNN. HetGCNConv only uses heterogeneous nodes but homogeneous edges. CHGNN-EL uses both heterogeneous nodes and edges, but sets α2 to 0.

3.5 Qualitative and Quantitative Results

For our qualitative analysis, we study our predictions for the PBW application and compare our results with COGCN++. As seen in Figure. 2b, we observe that CHGNN using the seed inputs (Slist) has identified five functional clusters - Customer, Order, Inventory, BackOrder and Supplier. The programs in each cluster have very close dependencies within the cluster and contribute majorly to a common business function. This is also evident from the similar names of artifacts in a cluster (like OrderItem, Order-table, Orderitem-table in the Order service). Associated with each cluster is a group of data nodes (dashed circled) that interact closely with the programs in their cluster. As seen, the Supplier cluster has supplier-table, Supplier, SupplierBean and Populate nodes. In Figure 2a, we observe that COGCN++ is successful at separating seed sets, as it leverages the seed constraint loss. However, we notice the following differences.

1. Unlike CHGNN that creates evenly sized clusters, COGCN++ creates a few boulder clusters like the Order cluster (having 19 artifacts) and many dust clusters like Supplier, BackOrder and Customer (having atmost 3 artifacts). As explained in Section 3.3, this strategy helps COGCN++ outperform on S-Mod and Coverage but dramatically underperform on NED. For the task of microservices partitioning, having skewed cluster sizes may result into few over-utilized services and many under-utilized services - which is not desired.

2. We also find that COGCN++ wrongly associates many artifacts that actually belong to the Customer service (like AccountBean, LoginInfo and EmailMessage) with the Order and Inventory service. This is not the case for CHGNN.

All of the above observations have been validated by one of our SMEs (R1) - "CHGNN is better. Reason : The clusters are more evenly distributed. Customer service came out well with account management (AccountBean, LoginInfo, EmailMessage) contained in it which is desired."

We depict our quantitative results in terms of MetricSum in Table 1 and explain two trends that we have observed.

(i) COGCN++ scores lower values for MetricSum consistently in every application. Hence, on an average, the heterogeneous graph formulations outperform COGCN++.

(ii) In all the applications, either CHGNN or CHGNN-EL appear in the top two results for MetricSum. Hence, on an average, both models are relatively consistent across the varying application topologies.

Summary: From this, it is evident that (1) Heterogeneous graph formulations always guarantee better performance as can be seen in the three HET-GNN variations in Table 1. (2) Clusters in CHGNN are evenly distributed and more meaningful in nature when compared to COGCN++.

For extensive qualitative and metric-specific quantitative analysis of each application, architecture specifications and hardware requirements, please refer to our extended paper 2 .

4 Conclusion

We proposed a novel heterogeneous GNN that enables representation of application data resources and programs jointly for recommending microservices. Both quantitative and qualitative studies show the effectiveness of heterogeneous graph formulations. In the future, we aim to study the decomposition task at a more granular level from programs to functions and tables to columns.

2 https://arxiv.org/abs/2112.01317