# Optimizing Service Placement for Microservice Architecture in Clouds
## 4 Placement Algorithm
### Application Partition
#### 4.1.2 K Partition  
The idea of the k partition algorithm is to directly partition the application into \(k\) parts. By iteratively increasing \(k\), it terminates when the resource demands from each part do not exceed \(\alpha\) or no part contains more than one service. The pseudocode is shown in Algorithm 3. The basic process can be described as follows. The algorithm first constructs a graph \(G=(V,E)\) based on the application \(\mathcal{S}\) and then continuously checks the resource demands of each part in current application partition \(P\) where \(P=\{\mathcal{S}\}\) initially. If the total resource demands of a part \(\mathcal{S}_{i}\) in \(P\) exceeds the threshold \(\alpha\) and part \(\mathcal{S}_{i}\) contains more than one service, it increases \(k\), which is the number of partitioned parts. As mentioned in Section 3, in order to obtain a minimum k-cut with high probability, we have to perform the contraction algorithm independently \(n^{2k-2}\log n\) times. However, the time complexity increases exponentially with \(k\), which is prohibitively high. Thus, we make the time complexity consistent with the binary partition algorithm by sacrificing some probability of finding a minimum k-cut. It also performs the contraction algorithm \(n\) times. Then, according to the minimum k-cut \(G_{min}\) we get from the contraction algorithm, it partitions the application into \(k\) parts \(P=\{\mathcal{S}_{1},\mathcal{S}_{2},...,\mathcal{S}_{k}\}\). Similarly, this process would be repeatedly performed until the resource demands from each part do not exceed threshold \(\alpha\) or no part contains more than one service.  
Figure 3: An example of an application partition with threshold \(\alpha=0.5\).  
```
Input: service-based application \(\mathcal{S}\), threshold \(\alpha\) Output: a partition of the application \(P=\{\mathcal{S}_{1},\mathcal{S}_{2},...,\mathcal{S}_{N^{\prime}}\}\), \(N^{\prime}\) is number of parts after partition
1\(P\leftarrow\{\mathcal{S}\}\);
2 whileexists part \(\mathcal{S}_{i}\) in \(P\) that the total resource demands exceed \(\alpha\), and part \(\mathcal{S}_{i}\) contains more than one servicedo
3\(P\gets P-\{\mathcal{S}_{i}\}\);
4 Construct a graph \(G=(V,E)\) based on \(\mathcal{S}_{i}\);
5\(n\leftarrow|V|\);
6\(\mathcal{G}_{min}\gets G\);
7\(t\gets 0\);
8 repeat
9 Perform the contraction algorithm (\(k=2\)) to get a cut \(G^{\prime}\);
10\(G_{min}\leftarrow\min(G_{min},G^{\prime})\) ; // Store the smaller cut in \(G_{min}\)
11\(t\gets t+1\);
12
13 until\(t>n\);
14 Get a partition \(\{\mathcal{S}_{x},\mathcal{S}_{y}\}\) of part \(\mathcal{S}_{i}\) according to \(G_{min}\);
15\(P\gets P\cup\{\mathcal{S}_{x},\mathcal{S}_{y}\}\);
16
17 end while return\(P\);
```  
**Algorithm 2**Binary Partition  
```
Input: service-based application \(\mathcal{S}\), threshold \(\alpha\) Output: a partition of the application \(P=\{\mathcal{S}_{1},\mathcal{S}_{2},...,\mathcal{S}_{N^{\prime}}\}\), \(N^{\prime}\) is number of parts after partition
1\(P\leftarrow\{\mathcal{S}\}\);
2 Construct a graph \(G=(V,E)\) based on \(\mathcal{S}\);
3\(n\leftarrow|V|\);
4\(k\gets 1\);
5 whileexists part \(\mathcal{S}_{i}\) in \(P\) that the total resource demands exceed \(\alpha\) and part \(\mathcal{S}_{i}\) contains more than one servicedo
6\(G_{min}\gets G\);
7\(k\gets k+1\);
8\(t\gets 0\);
9 repeat
10 Perform the contraction algorithm until \(k\) nodes remain to get a k-cut \(G^{\prime}\);
11\(G_{min}\leftarrow\min(G_{min},G^{\prime})\) ; // Store the smaller k-cut in \(G_{min}\)
12\(t\gets t+1\);
13 until\(t>n\);
14 Get a partition \(\{\mathcal{S}_{1},\mathcal{S}_{2},...,\mathcal{S}_{k}\}\) of the application \(\mathcal{S}\) according to \(G_{min}\);
15\(P\leftarrow\{\mathcal{S}_{1},\mathcal{S}_{2},...,\mathcal{S}_{k}\}\);
16
17 end while return\(P\);
```  
**Algorithm 3**K Partition