Mitigating Interference of Microservices with a Scoring Mechanism in Large-scale Clusters

We analyze the task status of four types of BEJs in our cluster for 7 days, namely SQL, SQLRT, Algo and Dup. SQL are typical data processing jobs like Spark; SQLRT jobs require much more resources to ensure that they should be completed as soon as possible; Algo jobs are mainly related to machine learning, such as model training, inference, data normalization, and one-hot encoding; Dup jobs are responsible for data duplication.

The number of these four categories accounts for 99% of the total number of BE instances. For each BE task instance, we collect some performance metrics, such as CPU utilization, memory utilization, and makespan, to represent its resource requirements. These metrics are easy to monitor with low overhead. Meanwhile, the performance metrics of each task are aggregated from all its instances. We adopt a data-driven approach to classify the BE tasks into different categories and quantify the resource intensity of BE tasks from these performance metrics. For example, SQL jobs are normally CPU-intensive workloads, while Algo jobs are both CPU-intensive and memory-intensive workloads.

Encoding based on CPU Usage. To simplify the classification problem, we apply a histogram method to distinguish the intensive of resource usage. Figure 8(a) demonstrates the CPU usage of BE tasks, which can be divided into three buckets based on their CPU consumption. The workload is traditionally classified as low, medium, or high to represent the degree of CPU consumption. One interesting finding is that the low CPU usage bucket $[0,\alpha_{1})$ includes almost all Dup tasks, while the middle CPU usage bucket $[\alpha_{1},\alpha_{2})$ includes all tasks except for a portion of Algo tasks. The last bucket includes the remaining part of Algo tasks, which are CPU-intensive workloads that consume more CPU than $\alpha_{2}$. Note that we adopt the settings $\alpha_{1}=0.5$ and $\alpha_{2}=1.5$ based on the workload distribution in our experiment.

Encoding based on Memory Usage. As shown in Figure 8(b), the distribution of memory is more complex compared with CPU resources in our cluster. BE tasks can be divided into five buckets based on four memory thresholds. Specifically, bucket $[0,\beta_{1})$ contains all Dup tasks and includes all Algo tasks combining with buckets $[\beta_{1},\beta_{2})$. Next, bucket $[\beta_{2},\beta_{3})$ and bucket $[\beta_{3},\beta_{4})$ contain parts of SQL tasks and SQLRT tasks respectively. Finally, more than 90% of SQLRT’s Map tasks in Figure 9 require more than $\beta_{4}$ GB memory, which is typically memory-intensive. We find similar patterns in SQL tasks. In this way, the last bucket we set includes this part of map tasks whose memory usage is greater than $\beta_{4}$.

Encoding based on Makespan. As for the makespan shown in Figure 8(c), BE tasks can be divided into four buckets based on three thresholds. Specifically, SQLRT tasks take the least time to complete and can be put into bucket $[0,\gamma_{1})$. The makespan of Algo tasks vary widely. Inference or prediction tasks make up a large portion of Algo tasks, and tasks related to model training need to run for tens of minutes or more. So we set the last bucket to include part of the Algo tasks whose makespan is greater than $\gamma_{3}$. SQL and Dup tasks have similar CDFs, and most of these tasks are completed within $\gamma_{3}$ seconds. So bucket $[\gamma_{1},\gamma_{2})$ and bucket $[\gamma_{2},\gamma_{3})$ contain parts of SQL tasks and Dup tasks respectively.

Based on the characterization of BE tasks on the three dimensions, the category of BE tasks can be represented by a triple:

Specifically, CPU, MEM and makespan have 3, 5, and 4 classes respectively, as described above. So we get 60 BE task categories in total. We essentially categorize BE tasks based on their resource intensity. Note that this categorization scheme is not uniform, as certain categories of tasks (e.g., [1, 0, 0]) may account for the majority. This does not affect interference analysis from the perspective of BE composition.

Due to the high dynamics of production clusters, we study the impact of each task category on interference, rather than the effect of one task. All BE task instances co-located on the server can be expressed in the form of BE composition as:

where $n_{i}$ represents the number of BE instances of category $i$ on the server.

We compute the similarity of BEJs based on their DAG structures. A Graph Kernel is proposed to determine whether two DAGs are isomorphic. The core of the Graph Kernel is to map a graph structure to a vector in the Hilbert space and measure the similarity of two graphs by calculating the inner product of the two vectors. The Graph Kernel has high computational efficiency and is suitable for large-scale clusters that require frequent judgments.

We first cluster BEJs into different groups by computing the inner product matrix of BEJs. Note that each group corresponds to a DAG structure. After clustering, the inner product between any two BEJs in each group is exactly the same. We use this value as the tag of groups. Then, when a new BEJ arrives, we calculate the inner product between it and each of the existing groups (by randomly sampling a BEJ from each group). The new BEJ belongs to the group with a tag equal to the computed inner product. If there is no such group, the new BEJ itself represents a new group.

We combine the DAG tag and some job-level meta-data (e.g., submission time and instance number) as the features of BE tasks. We use these features to train the task classifier which is implemented as an ensemble of three support vector machine classification models based on CPU, MEM, and makespan respectively.

As listed in Table 2, we use six-day data to train the classifier and evaluate its accuracy with one-day data. On average, each DAG structure has about 200 BEJs. We measure classification accuracy on each dimension and overall accuracy (i.e., correct in all three dimensions). The results are shown in Figure 11. At the instance level, the number of instances of BE tasks with accurate classification accounts for about 76% of the total number of instances, and the accuracy on each dimension reaches 90%. Based on the evaluation results and Figure 11, we analyze from two aspects.

First, BE tasks with accurate classification usually have more instances. This is most evident in the MEM dimension, where 60% of tasks with accurate memory categorization account for 92% of the total instances. Tasks with more instances are more distinctive and stable, which is beneficial for achieving high prediction accuracy. Second, the classification error is mainly caused by the boundaries, this problem is more complex and is our future work. For example, a task with CPU usage around 0.5 cores may fluctuate between 0.4 and 0.6 cores when running on different servers, thus falling into different categories under the 0.5 threshold. Taking into account the boundary error, if we allow the classification for such tasks to fall to the left or right category of the boundary, then the instance-level classification accuracy is up to 99.8%, 99.8%, and 99.4% on CPU, MEM, and makespan, respectively.

In this section, we depict the details of our scoring model with an encoding approach. We evenly divide the RT of LCS instances into $k$ levels according to the corresponding percentile: the range of $[1,10)$ percentile maps to Level 1 score encoded as [1,0,…,0], the range of $[10,20)$ percentile maps to Level 2 score encoded as [0,1,…,0], and so on. In this way, we map the RT of different LCSs to interference scores in the range of $[1,k]$. Since the interference level corresponds to RT, it is not only influenced by BEJs, but may also be affected by other factors such as network congestion. When this happens on a server, the interference score of LCS instances on the server will be high, which can effectively prevent BE tasks from being scheduled to the server.

To achieve a balance between performance and accuracy in interference assessment, $k$ can be set to different values in different scenarios. If only interference needs to be detected, $k$ can be set to 2. In this case, the accuracy of the interference assessment can be high, but its value for scheduling is low. Conversely, if larger $k$ values are used to quantify interference with finer granularity, accuracy will decrease. We set $k=10$ in the performance evaluations in Section 6.

The level of server interference depends on the LCS instances running on the server. Observation 3 in Section 4 indicates that different LCSs have diverse sensitivity to interference. Based on the LCS interference scoring model, a key issue is how to weight each LCS instance on the server to comprehensively quantify server interference. Given the weight $w_{i}$ of each LCS instance, the server interference score can be aggregated by:

where $i$ iterates over all LCS instances on the server, and $Score_{i}$ is the interference level of the $i-th$ LCS at this server.

We evaluate 4 weighting schemes in Section 6.3. (1) Fair: all LCS instances have the same weight; (2) CPU-Quota: the weight of LCS instances is determined by their requested CPUs; (3) Corr: the correlation coefficient between the RT of LCS and the total CPU usage of BE tasks on the server; and (4) CV: the coefficient of variation of LCS instance RTs.

We collect BEJ scheduling traces on 600 servers over 1 week and conduct a simulation study by rescheduling these BE instances to evaluate the effectiveness of PISM. The CPU model of the servers is Intel(R) Xeon(R) Platinum 826X CPU @ 2.50GHz (Cascade Lake model). The base frequency is 3.2 GHz and the L3 cache size is 36608 KB. Non-uniform memory access (NUMA) is enabled to increase the overall bandwidth and reduce the latency to memory.

The workloads consist of hundreds of LCSs and $282194$ BEJs in 7 days. One important LCS is checkout, having more than 3500 instances and consuming almost 28000 CPU cores. For BEJs, there are almost $1456$ different DAGs, indicating an average of 200 identical or similar BEJs per DAG, which is general and reported in other production clusters such as Google [16].

The simulator contains the BE Task Classifier to infer the categories of tasks and the Interference Scorer to predict the interference score when scheduling, as described in Section 5. After predicting the category of each BE instance, the scheduler selects the candidate server with the lowest interference score for scheduling. The optimization goal of PISM is to ensure that the same BE instances are scheduled while reducing the average interference level of all servers.

Figure 12 shows the simulation results. In the original trace, there is not much difference in server interference scores, which is the Baseline method (without PISM) and is the default scheduling algorithm in our cluster. We implement our PISM algorithm by continuously scheduling BE instances to our cluster based on their submission time. Moreover, PISM reschedules BE instances that are originally assigned to servers with high interference to servers with low interference. We calculate the server interference score based on the formula in Section and classify the interference degree into ten buckets. The score in level-0 denotes the lowest interference, and the score in level-10 has the highest chance for resource contention. As a result, PISM increases the workloads of servers with the lowest interference from 8.3% to 32.3% in Figure 12. We also discover that our algorithm has the largest optimization to mitigate interference in level-10, reaching 82.1%. In summary, PISM reduces the server interference score from 5.468 to 3.197, mitigating performance interference by 41.5%. This means that PISM can effectively alleviate the long-tail phenomenon.

We also study the response time (RT) and throughput of 150 critical LCSs on 600 servers. To simplify the evaluation, we classify these LCSs into two categories: $tail-heavy$ and $tail-light$. We find that the P90 RT of $tail-heavy$ LCSs is 5x the average RT, and the rest are $tail-light$. Table 3 illustrates the percentage of LCSs in two categories and their respective throughput improvements. $Tail-light$ LCSs make up most of our cluster, with an average throughput increment of 17.2%. The throughput improvement on $tail-heavy$ LCSs is even more significant, reaching 76.4%. This suggests that PISM not only effectively reduces the percentage of P90 RT, but also benefits the LCSs with high tail latency.

We examine the generality and performance of PISM, which can be seamlessly integrated into other schedulers. First, we consider two basic schedulers: spread and stack, which are also used in Kubernetes¹¹1The scheduling architecture in our cluster is similar to Kubernetes., Spark, Docker Swarm, and other frameworks [27, 42, 43]. spread schedules tasks to the server with the lowest CPU utilization to balance the CPU utilization of the cluster, while stack selects the server with CPU utilization as close to the threshold as possible. We use 80% as the CPU threshold because there are very few servers in our cluster that have more than 80% CPU utilization, as shown in Figure 4.

Next, we employ both schedulers to select 10 candidate servers to replace one server. Subsequently, we predict their interference level with or without PISM, and then schedule task instances to the candidate server with the lowest interference score. As illustrated in Figure 13(a), PISM-based schedulers can effectively reduce the overall interference by 16.9% and 12.5% compared with spread and stack, respectively. spread focuses on load balancing, resulting in little difference in server CPU utilization, basically distributed between 40% and 50%, as shown in Figure 13(b). On the other hand, stack considers resource reservation, leading to polarized results. For stack, there are many servers with the lowest interference score, about 15% higher than spread, resulting in relatively low overall cluster interference. Figure 13(b) also shows that PISM does not change the goals of these two schedulers while significantly reducing interference.

To investigate the impact of PISM on the actual RT of LCSs, we set up a small-scale Kubernetes cluster consisting of 14 servers. Each server is equipped with an Intel(R) Xeon(R) Platinum 8269CY CPU model and 512GB of memory. We use Online Botique²²2Google’s open source e-commerce microservice platform, https://github.com/GoogleCloudPlatform/microservices-demo and Spark to simulate LCSs and BEJs. Their workloads are generated based on the production cluster trace. PISM is integrated into three schedulers, spread, stack, and random placement.

Figure 14 shows the average RT of two critical services of Online Botique, checkout and browse_product. PISM significantly reduces the RT of the two services with different schedulers. The maximum reduction is achieved when PISM is paired with stack, reducing the average RT of checkout from 436ms to 263ms, a decrease of 39.5%. Compared to browse_product, the RT improvement of checkout is more significant, because checkout has a more obvious long-tail latency.

Figure 15 shows five percentile RT values of checkout and browse_product. For the two services, there is little difference in the P0, P50, and P75 RT with or without PISM. However, there are significant improvements in the P90 and P99 RTs of checkout with PISM, especially for the P99 RT reduced from 8000ms to 3000ms. This demonstrates the effectiveness of PISM in improving service performance by alleviating the long-tail phenomenon. These results are consistent with the simulation results.

We collect a 2-day of trace from our cluster, one day as training set and another day as ground truth to evaluate the interference prediction model of LCSs. As shown in Figure 16, we evaluate the interference predictions of checkout. The predictions are centered around each true interference score. Since the interference score represents a trend and needs to be compared with each other when scheduling, we consider predictions to be accurate with an absolute error of no more than 2, calcuted as, $|predicted~{}score-true~{}score|\leq 2$. The results demonstrate that we can achieve a prediction accuracy of 87.2% for checkout.

We further focus on the case of relatively high interference and low interference (i.e., evenly divided into two categories). We treat those with large scores as BUSY, and the opposite as IDLE. This can be viewed as a simple binary classification problem of whether interference occurs. We then compute the precision, recall, and F1-score metrics, as listed in Table 4. Our model performs well on this binary classification problem with F1-scores above 0.9. The reason for the higher precision but lower recall of the BUSY class is that our model only considers BEJ, ignoring interference caused by other factors (such as other applications). The IDLE class is the opposite. Figure 16 also shows that when the true interference score is greater than 5, there are still a certain number of samples whose level is predicted to be 1. One possible explanation is that the interference might be caused by other LCSs on the same server, which cannot be reflected by BE composition.

When the real interference level is very high (e.g., score $>$ 8), it is harmful to predict it as a small value (e.g., score $<$ 3). In this case, the scheduler will continue to schedule tasks on such a heavy-loaded server, eventually degrading the performance of LCSs. Fortunately, the probability of this happening in our model is only 0.04%. Conversely, predicting a low level as a high level may result in missed scheduling opportunities, which is only a 0.006% chance for our model.

We then investigate the accuracy of interference prediction shown in Figure 18. Here we consider 150 crucial LCSs in our production cluster, and each one has more than 10 instances. The baseline method ($BEJsUtilization$) calculates the LCS interference score based on the CPU usage of all LCSs as observation 4 shows there is a linear relationship between the overall BEJ resource usage and LCS RT. Our method $BEJsComposition$ estimates the interference score according to the BEJs composition. Figure 18 shows the average accuracy of the BEJ utilization-based method is only 58.3%, while the BEJ composition-based method is 75.2%. This verifies that the BE task characterization method captures performance interference patterns. Notably, the BEJ composition-based method itself is simple and efficient, laying a good foundation for deployment in large-scale clusters. In contrast, if we want to predict the interference score of LCSs based on BEJ utilization, we need to collect the resource utilization of each server in real-time and predict the exact run-time utilization of BEJ task instances, which will incur high overhead and will be difficult to apply.

Similarly, we evaluate server interference predictions from three aspects: (1) the accuracy with an absolute error $\leq$ 2; (2) precision, recall, and F1-score for the BUSY category; and (3) severe prediction errors, especially the probability that a high interference level is predicted to be a low level. The four weighting schemes described in Section 6.1.2 are also evaluated. Figure 18 shows the prediction results of the 600 servers in our cluster. The $Corr$ weighting scheme performs best as it directly reflects the correlation between the interference level and the CPU usage of BE instances. The performance of $Fair$ and $CPU$-Quota schemes is nearly identical, although the number of CPUs required by LCSs varies from 1 to 32 cores. $CV$ is not only related to BE pressure, but also to many other factors, such as the business logic of LCSs.